Tracking Moving Targets in a
`Smart Sensor Network
`
`Rahul Gupta
`Department of ECECS
`University of Cincinnati
`Cincinnati, OH 45221-0030
`
`Samir R. Das
`Computer Science Department
`SUNY at Stony Brook
`Stony Brook, NY 11794-4400
`
`Abstract— Networks of small, densely distributed wireless
`sensor nodes are capable of solving a variety of collaborative
`problems such as monitoring and surveillance. We develop a sim-
`ple algorithm that detects and tracks a moving target, and alerts
`sensor nodes along the projected path of the target. The algorithm
`involves only simple computation and localizes communication
`only to the nodes in the vicinity of the target and its projected
`course. The algorithm is evaluated on a small-scale testbed of
`Berkeley motes using a light source as the moving target. The
`performance results are presented emphasizing the accuracy of
`the technique, along with a discussion about our experience in
`using such a platform for target tracking experiments.
`
`I. INTRODUCTION
`Rapid advances in miniaturization in computing and sen-
`sor technologies and advent of low-power short-range radios
`recently have given rise to strong interest in smart sensor
`networks [1], [2]. The idea is to be bring together sensor nodes
`with on-board processing capability and radio interface into a
`large network to enable them to process higher level sensing
`tasks in a co-operative fashion. Several new design themes
`have emerged for such networks. For example, the network
`must be fully self-configuring and highly fault-tolerant as the
`sensors may be deployed in an “ad hoc” fashion. The network
`must minimize battery power usage; this enables untethered
`and unattended operations for an extended time. A corollary
`of the latter property is that the system must leverage data
`processing and decision making ability inside the network as
`much as possible, instead of shipping the data to a central
`controller to make decisions. This is because with current
`day technology, the power budget for communication is many
`times more than that for computation.
`An emerging application area for smart sensor networks is
`intelligent surveillance or monitoring. Sensors are distributed,
`likely randomly, in a geographic area to be monitored. The
`goal is to track and predict the movement of an appropriate
`target and alert the sensors which are close to the predicted
`path of the target. The target can be a moving vehicle, for
`example, or can be a phenomenon such as an approaching
`fire. It is assumed that each individual sensor node is equipped
`with appropriate sensory device(s) to be able to detect the
`target as well as to estimate its distance based on the sensed
`data. The sensors that are triggered by the target collaborate to
`localize the target in the physical space to predict its course [3].
`Then the sensor nodes that lie close to the predicted course
`
`of the target are alerted. This alert is meant to serve as a
`trigger for these nodes to activate additional on-board sensors.
`For example, these additional sensors may be of a different
`modality (e.g., alerts coming from heat sensors activating
`vibration sensors) that are ordinarily turned off or not sampled
`to conserve power. The alert can also serve as a trigger to
`actuate certain on-board devices, depending on the capability
`of the nodes and the application.
`The goal of this paper is to develop techniques for the above
`moving target tracking problem and report our experience
`in testing them in a live low-cost sensor network testbed
`using Berkeley motes [4]. Variations of these motes have
`been used in several experimental testbeds recently. See, for
`example, [5], [6], [7], [8]. We will demonstrate the feasibility
`of our approach. We will also discuss performance results,
`and several practical problems a designer/implementor must
`be aware of.
`The paper is organized as follows. In the next section we
`describe the tracking algorithm, experimental evaluation is
`reported in Section III. In Section IV, we discuss the problems
`we faced in our experiments and some ways to alleviate them.
`We conclude in Section V.
`
`II. TRACKING MOVING TARGETS
`
`Our testbed comprises of 17 Berkeley motes [4] based
`on the MICA platform and manufactured by Crossbow tech-
`nology [9]. We assume that the sensor nodes are scattered
`randomly in a geographical region. Each node is aware of its
`location. Location information can be gathered using an on-
`board GPS receiver. Absolute location information is, however,
`not needed. It is sufficient for the nodes to know their location
`with respect to a common reference point. Many localizing
`techniques, e.g. [8], [10], can be used with varying degree of
`hardware complexity and accuracy. In our model, the sensor
`nodes are stationary and we have directly encoded the location
`information into the sensor nodes to eliminate the possibility
`of any localization error. Thus, we do not emphasize any
`particular localization technique.
`The sensors must be capable of estimating the distance of
`the target to be tracked from the sensor readings. It is assumed
`that
`the sensor has already learned the sensor reading to
`distance mapping. We conducted a separate set of experiments
`
`0-7803-7954-3/03/$17.00 ©2003 IEEE.
`
`3035
`
`Authorized licensed use limited to: Worcester Polytechnic Institute. Downloaded on January 17,2022 at 21:16:55 UTC from IEEE Xplore. Restrictions apply.
`
`Petitioners' Ex. 1033, Page 1 of 5
`Hewlett Packard Enterprise Co. et al. v. BillJCo, LLC
`IPR2022-00420
`
`

`

`to determine this mapping and encoded the mapping directly
`as a table in the application component.
`Tracking a target involves three distinct steps:
`(cid:127) Detecting the presence of the target.
`(cid:127) Determining the direction of motion of the target.
`(cid:127) Alerting appropriate nodes in the network.
`These steps are discussed in detail in the following subsec-
`tions.
`
`A. Detection
`Each node periodically (every 1 sec in our experiments)
`polls its sensor module to detect the presence of any target
`to be tracked. Sensor reading above a particular threshold
`indicates the presence of a target in the vicinity. As soon as this
`threshold is crossed, a TargetDetected message is broadcast by
`the node. Each TargetDetected message contains the location
`of the originating node and its distance from the target, as
`determined from the sensor reading. When this message is
`received by a neighboring node, it stores the coordinates of
`the originator and the target’s distance from the originator
`in a table. Table entries expire after a timeout (4 sec in our
`experiments) unless refreshed.
`
`B. Tracking
`The next step is estimating the location of the target. A
`minimum of three nodes sensing the target are needed to
`apply the commonly used triangulation method [11]. When a
`node that has already detected the target hears two additional
`TargetDetected messages from two different neighbors, it com-
`putes a location estimate via triangulation. Note that any node
`that hears three TargetDetected messages from three different
`neighbors can estimate the location of the target. However,
`we limit this computation only to the nodes that themselves
`have detected the target, and hears from two other neighbors
`that also detected the target. This limits the estimation to be
`done only in nodes within a close vicinity of the target, thus
`localizing the computation.
`In order to estimate the trajectory of the target, its location
`must be estimated at a minimum of two instants of time. A
`straight line through these two points defines the trajectory
`in the direction of the latest location estimate. We found that
`with only two estimates, the impact of any estimation error
`was significant. Three or more estimates, however, worked
`significantly better. In the experimental results that follow we
`used three estimates with linear regression to compute a best-
`fit straight line. This line defines the estimated trajectory of
`the target. Note that more estimates, along with a higher-order
`curve fitting, will improve accuracy further. More estimates,
`however, will require a larger network to experiment with.
`For better accuracy, location estimates are used for trajectory
`estimation only when they are separated by at least a minimum
`distance (3 inches in our experiments).
`
`C. Alerting
`After estimating the trajectory, the network must alert nodes
`that lie near the trajectory (specifically, within a perpendicular
`
`Region R1
`
`Region R2
`
`Node Receiving
`Warning
`Message
`
`d
`
`E3
`
`Trajectory of
`Object
`
`E2
`
`E1
`
`= Sensor Node
`
`Sensor network with a moving target. E1 − E2 − E3 defines the
`Fig. 1.
`trajectory of the moving target.
`
`distance d from it, d being 5 inches in our experiments)
`by sending them a Warning message so that they are aware
`of the approaching target and can take appropriate actions.
`Any node that is able to estimate the trajectory by using
`three location estimates broadcasts a Warning message. The
`message contains the location of the sender and parameters
`describing the equation of the straight line trajectory. Any node
`receiving the Warning message rebroadcasts it, if it is located
`within a distance d from the trajectory.
`Care must be taken to prevent propagation of this warning
`message in the direction opposite to the direction of motion
`of the target. This is done via some simple geometric con-
`siderations. The node receiving a Warning message computes,
`through itself, a line perpendicular to the trajectory. The line
`divides the geographic area into two regions R1 and R2,
`R2 being towards the direction of motion. A node forwards
`the Warning message if (i) it lies within a distance d from
`the trajectory, and (ii) the Warning message is received from
`a node in region R1. See Figure 1. This ensures that only
`the nodes within d distance from trajectory and towards
`the direction of motion forward the warning. This localizes
`message propagation only in the relevant part of the network.
`Note that the above technique assumes that the network has
`enough density such that the subset of the sensor network
`nodes, that lie in the region where warning message must be
`propagated, must form a connected graph among themselves.
`This condition is needed as the warning message propagation
`is suppressed outside this region. Without this assumption,
`simply larger regions need to be flooded with warning mes-
`sages.
`Note that multiple nodes may originate Warning messages
`for the same detected target. This is because any node de-
`tecting an target independently attempts to carry out location
`and trajectory estimations. To conserve bandwidth and power,
`we stipulate that a node refrain from forwarding a Warning
`
`0-7803-7954-3/03/$17.00 ©2003 IEEE.
`
`3036
`
`Authorized licensed use limited to: Worcester Polytechnic Institute. Downloaded on January 17,2022 at 21:16:55 UTC from IEEE Xplore. Restrictions apply.
`
`Petitioners' Ex. 1033, Page 2 of 5
`Hewlett Packard Enterprise Co. et al. v. BillJCo, LLC
`IPR2022-00420
`
`

`

`Sensor 1
`Sensor 2
`Sensor 3
`
`1000
`
`900
`
`800
`
`700
`
`600
`
`500
`
`400
`
`Photo sensor reading (arbitrary units)
`
`300
`
`0
`
`12
`10
`8
`6
`4
`2
`Distance of base of light source from sensor node (inches)
`Fig. 2. Relationship of the “average” sensor readings with the distance of
`the light source. Three different sensors are shown to point out the difference
`in sensor characteristics.
`
`14
`
`message for some time (20 sec in our experiments) after it
`has forwarded one. This also implicitly assumes the presence
`of only one source in the network at any time. Detecting
`the presence of multiple sources and tracking them on an
`individual basis will require sophisticated sensing and signal
`processing algorithms [3] that is beyond the scope of our
`current work.
`
`III. EXPERIMENTAL EVALUATION
`In our experiments the moving target is a light source (bulb
`of a flashlight, taken out of the casing to minimize shadows
`and operated using four AA batteries). The experimental
`platform is a 60 inch × 60 inch square area with 16 motes
`placed at random locations in a dark room. A small area is
`chosen intentionally so that the experiments can be performed
`on a table top; this keeps the experiments manageable. A
`threshold of 15 inches is used for the distance of the light
`source; beyond this distance the sensor reading is assumed
`too low to be reliable. The target must be closer than this
`distance for a sensor to be able to detect it.
`A probe mote is suitably placed to capture all packets
`transmitted in the network for debugging and tracing functions.
`The probe does not participate in the algorithm. All packets
`gathered by the probe are transmitted via a serial interface to
`a laptop computer for analysis.
`
`A. Characteristics of the Photo Sensor
`We first performed a set of experiments to determine the
`relationship of the sensor reading with the distance of light
`source. This relationship would later be used to estimate
`the target distance from sensor readings. We faced several
`complications here. First, different sensors generated different
`readings for the same distance of the light source. The readings
`was variant enough that we felt some calibration would be
`necessary to reduce errors. While statistical methods using
`parameter estimation techniques such as reported recently in
`[8] could be used, we chose to determine the exact sensor
`reading versus distance relation for each individual sensor.
`This was feasible as we were dealing with a small number
`of sensors. Second, we found that light falling on the photo-
`sensor at an angle made the reading sensitive to the direction of
`the light source relative to the sensor. To reduce this sensitivity,
`we experimented with the light source at an elevated plane (at
`a height of 9 inches). This also resolved shadowing problems
`at small heights caused by the hardware components on the
`mote. The light source was always kept at the same height
`as we are interested in solving the tracking problem in two
`dimensions only.
`Figure 2 shows the average sensor reading vs. distance plots
`for three different sensors. Notice the differences in sensor
`characteristics. We tested all individual sensors and encoded
`the sensor reading versus distance function in their application
`components.
`
`B. Target Tracking
`In the first set of experiments, we evaluate the location
`estimation error. To evaluate the error, the light source is
`
`Placement
`
`1
`2
`3
`
`Avg. estimation error
`(inches)
`2.32
`2.06
`2.23
`
`Std. dev. of error
`(inches)
`1.82
`1.23
`1.53
`
`TABLE I
`LOCATION ESTIMATION ERROR STATISTICS FOR THREE DIFFERENT
`RANDOM MOTE PLACEMENTS.
`
`placed at approximately 5 inch intervals spanning the whole
`region in a grid-like fashion, and its location is estimated
`by three sensors exactly as described previously. The error
`(i.e., distance) between the actual and estimated location is
`computed. The average and standard deviation of the error is
`presented in Table I. Note that the average error is small (less
`than 2.5 inches), while the standard deviation of the error is
`relatively high. This is due to the fact that the error due to
`orientation of the light source relative to the photo sensor is
`not completely eliminated even with the elevated light source.
`A secondary reason is the inherent variability of the sensor
`data.
`The next set of experiments evaluates the performance of
`the tracking algorithm itself. Here, for each random placement
`of the motes, we perform a series of experiments where the
`light source is dragged slowly along a straight line path in the
`experimental region. The network responds by predicting the
`trajectory and lighting the LEDs in the motes which receive
`Warning messages. The nature of these experiments is such
`that it is hard to present the results in a quantitative fashion
`for readers to get a fair idea of the performance. So we have
`chosen to present the results in a visual fashion in Figures 3
`and 4. These figures are automatically generated by a script
`running on the trace of the packets gathered by the probe node.
`Small rectangles indicate the position of sensor nodes. The
`light source representing the moving target is actually moved
`from point P1 to point P2 in the experiments, indicated by
`a line. Circles around some nodes indicate the distance at
`which the light source is being sensed by the corresponding
`
`0-7803-7954-3/03/$17.00 ©2003 IEEE.
`
`3037
`
`Authorized licensed use limited to: Worcester Polytechnic Institute. Downloaded on January 17,2022 at 21:16:55 UTC from IEEE Xplore. Restrictions apply.
`
`Petitioners' Ex. 1033, Page 3 of 5
`Hewlett Packard Enterprise Co. et al. v. BillJCo, LLC
`IPR2022-00420
`
`

`

`nodes. Circles are drawn only for the last time any node
`“sees” the source and sends out TargetDetected message. The
`line through E1 and E2 (in the direction of E2) denotes the
`estimated trajectory. Thus, the difference between P1P2 and
`E1E2 denotes the estimation error. The following notations
`are used to designate nodes participating in warning message
`propagation:
`(cid:127) “WO” denotes the node that originates the Warning
`message.
`(cid:127) “WR” denotes the node that receives a Warning message
`and lies within distance d of the estimated trajectory,
`but does not forward the message because it lies in the
`direction opposite to the direction of motion.
`(cid:127) “WF” denotes the node that receives a Warning message,
`lies within distance d of the estimated trajectory and
`also forwards the message. WF nodes are highlighted by
`drawing a rectangle around them.
`While many experiments were performed with different
`placements of motes and different movement paths of the light
`source, for brevity only two sample results are shown in Fig-
`ures 3 and 4. In Figure 3, note that even though several motes
`originate a warning message, they all compute the same path.
`In a few experiments, we noted that the predicted direction of
`motion was somewhat off from the actual direction. This was
`because of a large error in one or more of the three location
`samples that are used in estimating the trajectory. The accuracy
`of the prediction can be improved naturally by taking many
`more samples, which will, however, require “observing” the
`target (light source) for longer time. This will also require
`larger experimental area and a larger number of motes.
`We have noted several interesting scenarios in the cases we
`studied. One example is presented in Figure 4 where different
`trajectories are estimated by two originating nodes, because
`they “heard” different sets of nodes that detected the target.
`The accuracies of the two estimates are very different. We
`looked carefully into the traces of this scenario, and found that
`the location estimation errors are not very high (maximum 3
`inches); but biased errors for one estimation resulted in a very
`different trajectory. Once again, larger number of samples with
`a larger network should improve such situations significantly.
`The second problem in Figure 4 is that no warning message is
`ever propagated. The reason is simply that there are no sensors
`within distance d of either of the predicted trajectory. This
`situation will trivially improve by choosing a denser network
`to experiment with or choosing larger value of d.
`
`IV. DISCUSSIONS
`It is worthwhile to outline here briefly the problems we
`faced in our experimental work using low-cost sensor nodes,
`not capable of sophisticated signal processing.
`The photo sensor used in MICA motes is sensitive to the
`angle at which light rays are incident on the sensor. Thus,
`very small changes in the distance influenced sensor readings
`significantly when the light source is near the sensor because
`relative changes in the angle is more significant at closer
`distance. An elevated source of light reduces this problem,
`
`Fig. 3. Tracking moving target: experimental scenario.
`
`Fig. 4. Tracking moving target: an interesting experimental scenario.
`
`but does not completely eliminate it – one reason for large
`variations in the errors in location estimates reported in Table
`I. We also observed variations in sensor readings in different
`directions even when elevation (and hence angle) and the
`distance of the light source were kept constant. We conjectured
`that either the light source or the sensor (or both) have some
`directional properties, which we ignored and relied on average
`properties to predict distance from sensor readings. We believe
`some of these problems will also confront designers when
`other signals and sensors (e.g., acoustic or magnetic) are used.
`To ensure that the light source always emits light with
`the same power, we used freshly recharged batteries for all
`experiments. This will be impossible in real scenarios. So we
`conjecture that estimating distance of the target from a set of
`sensor readings will be difficult to impossible in general set-
`tings, as the source signal cannot be always expected to be of a
`consistent strength. Unless the sensors are very sophisticated,
`
`0-7803-7954-3/03/$17.00 ©2003 IEEE.
`
`3038
`
`Authorized licensed use limited to: Worcester Polytechnic Institute. Downloaded on January 17,2022 at 21:16:55 UTC from IEEE Xplore. Restrictions apply.
`
`Petitioners' Ex. 1033, Page 4 of 5
`Hewlett Packard Enterprise Co. et al. v. BillJCo, LLC
`IPR2022-00420
`
`

`

`they will at best be programmed to simply detect presence
`or absence of a signal (and not to estimate any distance),
`and then collaborate with neighboring sensors to increase the
`confidence that an event or phenomenon has occurred in the
`vicinity. The strength of the signal can be gathered indirectly
`by determining how many sensors can detect the signal and
`how spread out they are geographically. We feel that this
`would be a reasonable approach to pursue, which will not be
`dependent on omnidirectional signals of consistent strength.
`However, this simple technique, for all practical usage, will
`require a large number of densely disposed sensors. This will
`be a direction we plan to pursue in our future work.
`To decrease the variability in sensor readings, we had to
`calibrate each sensor individually. This will be difficult to
`do for a very large number of sensors. Thus, sophisticated
`statistical methods, such as reported in [8], will need to be
`adopted. Also, we have preprogrammed the sensor with its
`location. But in real applications, they need to be localized.
`While many methods have been reported in recent literature
`[10], [12], [8],
`they will all
`introduce their own sources
`of error. A statistical analysis of errors has been done in
`[8]. It will be interesting to analyze the combined effect of
`localization errors of the sensor themselves and errors in
`location estimates and trajectory computation of the moving
`target.
`As discussed previously, a large number of location samples
`has a strong potential
`to reduce errors in estimating the
`trajectory. However, this will require a larger testbed. Also, the
`times at which different sensor nodes are sampling the signal
`are not synchronized. Thus, errors could be introduced when
`signals sampled at different times are combined for locating
`the moving target, as the actual location of the target could
`change. This error can be minimized by sampling sensors at a
`much higher rate relative to the maximum speed of the target.
`Of course, time synchronization can also be introduced at the
`cost of higher design complexity or possible power usage.
`
`V. CONCLUSIONS
`We have developed a simple algorithm for tracking moving
`targets in a smart sensor network. The sensor nodes detect and
`track the moving target in a collaborative fashion and alert the
`nodes near the predicted path of the target. The algorithm lo-
`calizes the communication in the vicinity of the location of the
`target and its estimated trajectory. This is critical as the sensor
`nodes usually run on a low power budget. The strength of our
`work is that we implemented and evaluated the algorithm in
`a real sensor network testbed using Berkeley motes. We used
`a moving light source as target. We described several factors
`that influence the accuracy of target tracking using low-cost
`sensor nodes such as the motes, and the potential problems
`a designer can face. The accuracy in our experiments has
`been fairly good, but not excellent. The accuracy is greatly
`influenced by the number of location estimation samples the
`designer can work with. With a small number of motes and
`a small experimental area, we could use only a small number
`of such samples. Thus, our experiments have a higher error
`
`margin than is possible to achieve. However, our experience
`demonstrates strong potential for this approach for large and
`dense sensor networks. We are in the process of acquiring
`a larger testbed that will make such large-scale experiments
`feasible.
`Experimental research using distributed networks of smart
`sensors is in its infancy. While research groups are working
`on algorithmic and performance aspects of collaborative signal
`processing in the target tracking arena [13], [3], experimental
`work focusing on localized communication has not yet ap-
`peared in mainstream literature in our knowledge. We expect
`that our experience will be useful to researchers pursuing
`research in this direction.
`
`ACKNOWLEDGMENT
`This work was partially supported by NSF grant ANI-
`0308631.
`
`REFERENCES
`[1] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next century
`challenges: Scalable coordination in sensor networks,” in Proceedings
`of the Fifth Annual International Conference on Mobile Computing and
`Networks (MobiCom), 1999.
`[2] D. Estrin, L. Girod, and G. P. M. Srivastava, “Instrumenting the world
`with wireless sensor networks,” in Proceedings of the International
`Conference on Acoustics, Speech and Signal Processing (ICASSP), Salt
`Lake City, May 2001.
`[3] D. Li, K. Wong, Y. H. Hu, and A. Sayeed, “Detection, classification
`and tracking of targets in distributed sensor networks,” IEEE Signal
`Processing Magazine, vol. 19, no. 2, 2002.
`[4] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister,
`“System architecture directions for networked sensors,” in Architectural
`Support for Programming Languages and Operating Systems, November
`2000, pp. 93–104.
`[5] W. Conner, L. Krishnamurhty, and R. Want, “Making everyday life easier
`using dense sensor networks,” in International Conference on Ubiquitous
`Computing (UbiComp ’01), October 2001, pp. 49–55.
`[6] Q. Li, M. D. R. Peterson, and D. Rus, “Reactive behavior in self-
`configuring sensor networks,” in CDROM Proceedings of the Eighth
`Annual International Conference on Mobile Computing and Networks
`(MobiCom), 2002, pp. CD–15–CD–16, poster paper.
`[7] A. M. et. al., “Wireless sensor networks for habitat monitoring,” in
`Proceedings of
`the First ACM International Workshop on Wireless
`Sensor Networks and Applications (WSNA), 2002, pp. 88–97.
`[8] K. Whitehouse and D. Culler, “Calibration as parameter estimation
`in sensor networks,” in Proceedings of the First ACM International
`Workshop on Wireless Sensor Networks and Applications (WSNA), 2002,
`pp. 59–67.
`[9] “Crossbow Technology, Inc.” http://www.crossbow.com.
`[10] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less low cost outdoor
`localization for very small devices,” IEEE Personal Communications,
`Special Issue on ”Smart Spaces and Environments”, vol. 7, no. 5, pp.
`28–34, 2000.
`[11] J. C. Jr., “A new approach to the geometry of toa location,” in IEEE
`Vehicular Technology Conference (VTC), September 2000, pp. 1943–
`1949.
`[12] J. Hightower and G. Borriello, “Location systems for ubiquitous com-
`puting,” IEEE Computer Magazine, vol. 34, no. 8, pp. 57–66, 2001.
`[13] R. Brooks, C. Griffin, and D. S. Friedlander, “Self-organized distributed
`sensor network entity tracking,” International Journal of High Perfor-
`mance Computing Applications, 2002, special Issue on Sensor Networks;
`to appear.
`
`0-7803-7954-3/03/$17.00 ©2003 IEEE.
`
`3039
`
`Authorized licensed use limited to: Worcester Polytechnic Institute. Downloaded on January 17,2022 at 21:16:55 UTC from IEEE Xplore. Restrictions apply.
`
`Petitioners' Ex. 1033, Page 5 of 5
`Hewlett Packard Enterprise Co. et al. v. BillJCo, LLC
`IPR2022-00420
`
`