- About this Journal ·
- Abstracting and Indexing ·
- Advance Access ·
- Aims and Scope ·
- Annual Issues ·
- Article Processing Charges ·
- Articles in Press ·
- Author Guidelines ·
- Bibliographic Information ·
- Citations to this Journal ·
- Contact Information ·
- Editorial Board ·
- Editorial Workflow ·
- Free eTOC Alerts ·
- Publication Ethics ·
- Reviewers Acknowledgment ·
- Submit a Manuscript ·
- Subscription Information ·
- Table of Contents
International Journal of Distributed Sensor Networks
Volume 2012 (2012), Article ID 938521, 16 pages
A Scalable Multi-Target Tracking Algorithm for Wireless Sensor Networks
School of Electrical Engineering and Computer Science, ASRI, Seoul National University, Seoul 151-744, Republic of Korea
Received 21 March 2012; Accepted 31 May 2012
Academic Editor: Hasan Cam
Copyright © 2012 Songhwai Oh. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Multi-target tracking is a representative real-time application of sensor networks as it exhibits different aspects of sensor networks such as event detection, sensor information fusion, multihop communication, sensor management, and real-time decision making. The task of tracking multiple objects in a wireless sensor network is challenging due to constraints on a sensor node such as short communication and sensing ranges, a limited amount of memory, and limited computational power. In addition, since a sensor network surveillance system needs to operate autonomously without human operators, it requires an autonomous real-time tracking algorithm which can track an unknown number of targets. In this paper, we develop a scalable real-time multi-target tracking algorithm that is autonomous and robust against transmission failures, communication delays, and sensor localization error. The algorithm is based on a rigorous probabilistic model and an approximation scheme for the optimal Bayesian filter. In particular, an extensive simulation study shows that there is no performance loss up to an average localization error of 0.7 times the separation between sensors and the algorithm tolerates up to 50% lost-to-total packet ratio and 90% delayed-to-total packet ratio. The proposed algorithm has been successfully applied to real-time multi-target tracking problems using wireless sensor networks.
In wireless sensor networks, many inexpensive and small sensor-rich devices are deployed to monitor and control our environment [1, 2]. Each device, called a sensor node, is capable of sensing, computation, and communication. Sensor nodes form a wireless adhoc network for communication. The limited supply of power and other constraints, such as manufacturing costs and limited package sizes, limit the capabilities of each sensor node. For example, a typical sensor node has short communication and sensing ranges, a limited amount of memory, and limited computational power. However, the abundant number of spatially spread sensors will enable us to monitor changes in our environment accurately despite the inaccuracy of each sensor node.
Multi-target tracking is a representative real-time application of sensor networks as it exhibits different aspects of sensor networks such as event detection, sensor information fusion, communication, sensor management, and real-time decision making. The applications of tracking using sensor networks include surveillance, search and rescue, disaster response system, pursuit evasion games , distributed control , spatiotemporal data collection, and other location-based services . Two well-known multi-target tracking algorithms are joint probabilistic data association (JPDA) filter  and multiple hypothesis tracker (MHT) [7, 8]. But, considering the limited computational power and memory space of each sensor node, they are not feasible for sensor networks due to their exponential time and space complexities. As a result, many new tracking algorithms for sensor networks have been developed recently.
Many target tracking algorithms developed for sensor networks are designed for single-target tracking [10–21] and some of these algorithms are applied to track multiple targets using classification [10–12] or heuristics, such as the nearest-neighbor filter (NNF) used in . The NNF  processes the new measurements in some predefined order and associates each with the target whose predicted position is closest, thereby selecting a single association. Although effective under benign conditions, the NNF gives order-dependent results and breaks down under more difficult circumstances. Some algorithms are designed for multi-target tracking [22–24] where the complexity of the data association problem inherent to multi-target tracking is avoided by classification [22, 23] or heuristics [22, 24]. The associations between measurements and targets are not generally known in multi-target tracking. The data association problem is to determine which measurements were generated by which targets. When tracking targets of a similar type or when reliable classification information is not available, the classification-based tracking algorithm behaves as the NNF. Considering the fact that the complexity of the data association problem is NP-hard [25, 26], a heuristic approach breaks down under difficult circumstances. Furthermore, the measurement inconsistencies common in sensor networks, such as false alarms and missing measurements due to missing detection or packet loss, are not fully addressed in many algorithms. On the contrary, the multi-target tracking algorithm developed in this paper is based on a rigorous probabilistic model and based on a true approximation scheme for the optimal Bayesian filter.
We can categorize a target tracking algorithm for sensor networks by its computational structure: centralized [11, 14, 15], hierarchical [16, 17], or distributed [10, 12, 13, 18–24]. Since each sensor can only sense a small region around it, and its measurements are noisy and inconsistent, measurements only from a single sensor and its neighboring sensors are not sufficient to initiate, maintain, disambiguate, and terminate tracks of multiple targets. It requires measurements from distant sensors to initiate, maintain, disambiguate, and terminate tracks of multiple targets. But considering the communication load and delay when exchanging measurements between distant sensors, a completely distributed approach is not feasible for real-time applications. On the other hand, a completely centralized approach is not robust and scalable. Hence, we consider a hierarchical architecture to minimize the communication load and delay while being robust and scalable. In fact, our algorithm has been successfully demonstrated using a large-scale outdoor sensor network deployment and used to solve a real-time control problem .
Markov chain Monte Carlo data association (MCMCDA) presented in  can track an unknown number of targets in real-time and is an approximation to the optimal Bayesian filter. It has been shown that MCMCDA is computationally efficient compared to the multiple hypothesis tracker (MHT)  and outperforms MHT with heuristics (i.e., pruning, gating, clustering, -scan-back logic and -best hypotheses) under extreme conditions, such as a large number of targets in a dense environment, low detection probabilities, and high false alarm rates . MCMCDA is suitable for sensor networks since it can autonomously initiate and terminate tracks. Since transmission failure is another form of missing observation, MCMCDA is robust against transmission failures. MCMCDA performs data association based on both current and past observations, so delayed observations, that is, out-of-sequence measurements, can be easily combined with previously received observations to improve the accuracy of estimates. Furthermore, MCMCDA requires less memory as it maintains only the current hypothesis and the hypothesis with the highest posterior. It does not require the enumeration of all or some of hypotheses as in [7, 28]. In this paper, we extend the MCMCDA algorithm to sensor networks in a hierarchical manner so that the algorithm becomes scalable. To our knowledge, the algorithm presented in this paper is the first general real-time scalable multi-target-tracking algorithm for sensor networks which can systematically track an unknown number of targets in the presence of false alarms and missing observations and is robust against transmission failures, communication delays, and sensor localization error.
We consider a simple shortest-path routing scheme on a sensor network. The transmission failures and communication delays of the network are characterized probabilistically. We assume the availability of a small number of special nodes, supernodes, that are more capable than regular nodes in terms of computational power and communication range. Examples of a supernode include high-bandwidth sensor nodes such as iMote and BTnode , gateway nodes such as Stargate, Intrinsyc Cerfcube, and PC104 , and the Tier-2 nodes used in the experiment of . Each node is assigned to its nearest supernode and nodes are grouped by supernodes. We call the group of sensor nodes formed around a supernode a “tracking group”. When a node detects a possible target, it communicates with its neighbors and observations from the neighboring sensors are fused and sent to its supernode. Each supernode receives the fused observations from its tracking group and executes the tracking algorithm. Each supernode communicates with neighboring supernodes when a target moves away from its range. Lastly, the tracks estimated by supernodes are combined hierarchically. Although a specific sensor network model is used for the performance evaluation, the algorithm is applicable for different routing algorithms and sensor models, for example, distributed air traffic control .
As mentioned earlier, the algorithm presented in this paper is used in . Although the overview of the algorithm is described in , the focus of  is to describe a new control system architecture using sensor networks and an outdoor experiment. In this paper, we describe the algorithm in detail and study the characteristics of the algorithm under different conditions in simulation. The paper also includes experimental results from an indoor experiment with 45 sensors and ourdoor experiments described in . While a wireless sensor network generates noisy, inconsistent, and bursty measurements, the algorithm described in this paper successfully estimated the number of targets and tracks of targets in real-time.
The remainder of this paper is structured as follows. The sensor network model assumed in this paper is described in Section 2. In Section 3, the multi-target tracking problem, the MCMCDA algorithm, and the hierarchical extension of MCMCDA are described. The simulation and experiment results are given in Sections 4 and 5. Frequently appearing symbols are listed in Abbreviations section.
2. Sensor Network Model
Let be the number of sensor nodes, including both supernodes and regular nodes, deployed over the surveillance region . We assume that each supernode can communicate with its neighboring supernodes. Let be the location of the th sensor node and let . Let be a communication graph such that if and only if node can communicate with node . Let be the number of supernodes and let be the position of the th supernode, for . Let be the assignment of each sensor to its nearest supernode such that if . For a node , if , the shortest path from to in is denoted by . For each supernode , its tracking group contains a set of nodes .
Let be the sensing range. If there is an object at , a sensor can detect the presence of the object. Each sensor records the sensor's signal strength, where , , and are constants specific to the sensor type, and we assume that are normalized such that has the standard Gaussian distribution. This signal-strength based sensor model (1) is general for sensors available in sensor networks, such as acoustic and magnetic sensors, and has been used frequently [18, 23, 31]. For each , if , where is a threshold set for appropriate values of detection and false-positive probabilities, the node transmits to its neighboring nodes, which are at most away from , and listens to incoming messages from its neighborhood. Note that this approach is similar to the leader election scheme in  and we assume that the transmission range of each node is larger than . However, this approach may cause some missing observations if there is more than one object in this disk of radius . A better approach to fuse local data is required and we will address this issue in our future work. For the node , if is larger than all incoming messages, , and , then the position of an object is estimated as The estimate corresponds to the computation of a center of mass of the sensing nodes weighed by measured signal strengths. The node transmits to the supernode via the shortest path . If is not the largest compared to the incoming messages, the node does nothing and goes back to the sensing mode. Although each sensor cannot give an accurate estimate of object's position, as more sensors collaborate, the accuracy of estimates improves as shown in Figure 1. The collaboration of sensors makes the system more robust against node failures and we can increase the detection probability and decrease the false alarm rate by collaboration.
A transmission along the edge fails independently with probability and the message never reaches a supernode. Notice that the transmission failure includes failures from retransmissions. We can consider transmission failure as another form of a missing observation. If is the number of hops required to relay data from a sensor node to its supernode, the probability of successful transmission decays exponentially as increases. To overcome this problem, we use independent paths to relay data if the reporting sensor node is hops away from its supernode. The probability of successful communication from the reporting node to its supernode can be computed as where . See Figure 6(a) for an example of the ratio between the number of lost packets and the number of total packets as a function of the transmission failure rate .
We assume each node has the same probability of delaying a message. If is the number of (additional) delays on a message originating from the sensor , that is, the number of sampling intervals elapsed since the required arrival time at the supernode , is distributed as We are modeling the number of (additional) delays by the negative binomial distribution. A negative binomial random variable represents the number of failures before reaching the fixed number of successes from Bernoulli trials. In our case, it is the number of delays before successful delay-less transmissions. See Figure 7(a) for an example of the ratio between the number of delayed packets, and the number of total packets as a function of the communication delay rate .
When the network is heavily loaded, the independence assumptions on transmission failure and communication delay may not hold. However, the model is realistic under the moderate conditions, and we have chosen it for its simplicity.
3. Multi-Target Tracking
3.1. Problem Formulation
Let be the duration of surveillance. Let be the number of targets that appear in the surveillance region during the surveillance period. Each target moves in for some duration . Notice that the exact values of and are unknown. Each target arises at a random position in at , moves independently around until , and disappears. At each time, an existing target persists with probability and disappears with probability . The number of targets arising at each time over has a Poisson distribution with a parameter where is the birth rate of new targets per unit time, per unit volume, and is the volume of . The initial position of a new target is uniformly distributed over .
Let be the discrete-time dynamics of the target , where is the dimension of the state variable, and let be the state of the target at time for . The target moves according to where are white-noise processes. The white-noise process is included to model nonrectilinear motions of targets. When a target is present, a noisy observation (or measurement) of the state of the target is measured with a detection probability . Notice that, with probability , the target is not detected and we call this a missing observation. There are also false alarms, and the number of false alarms has a Poisson distribution with a parameter , where is the false alarm rate per unit time, per unit volume. Let be the number of observations at time , including both noisy observations and false alarms. Let be the th observation at time for , where is the dimension of each observation vector. Each target generates a unique observation at each sampling time if it is detected. Let be the observation model. Then the observations are generated as follows: where are white noise processes and is a random process for false alarms. We assume that the targets are indistinguishable in this paper, but if observations include target type or attribute information, the state variable can be extended to include target type information as done in .
The main objective of the multi-target tracking problem is to estimate , and , for , from noisy observations.
Let be all measurements at time and be all measurements from to . Let be a collection of partitions of such that, for , , where is a set of false alarms and is a set of measurements from target for . Note that is also known as a joint association event in literature. More formally, is defined as follows: (1); (2) and for ; (3) is a set of false alarms; (4) for and ; (5) for . An example of a partition is shown in Figure 2. Here, is the number of tracks for the given partition . We call a track when there is no confusion although the actual track is the set of estimated states from the observations . This is because we assume there is a deterministic function that returns a set of estimated states given a set of observations. A track is assumed to contain at least two observations since we cannot distinguish a track with a single observation from a false alarm, assuming . For special cases in which or , the definition of can be adjusted accordingly.
Let be the number of targets at time , be the number of targets terminated at time and be the number of targets from time that have not terminated at time . Let be the number of new targets at time , be the number of actual target detections at time , and be the number of undetected targets. Finally, let be the number of false alarms. Using the Bayes rule, it can be shown that the posterior of is: where is the likelihood of observations given , which can be computed based on the chosen dynamic and measurement models. For example, the computation of for the linear dynamic and measurement models can be found in . Our formulation of (7) is similar to MHT , and the derivation of (7) can be found in . The parameters , , , and have been widely used in many multi-target-tracking applications [6, 28]. Our experimental and simulation experiences show that our tracking algorithm is not sensitive to changes in these parameters in most cases. In fact, we used the same set of parameters for all our experiments.
There are two major approaches to solve the multi-target-tracking problem : maximum a posteriori (MAP) and Bayesian approaches. The MAP approach finds a partition of observations such that is maximized and estimates the states of the targets based on this partition. A Bayesian approach called minimum mean square error (MMSE) finds an estimate which minimizes the expected square error. For instance, is the MMSE estimate for the state of target . However, when the number of targets is not fixed, a unique labeling of each target is required to find under the MMSE approach. In this paper, we take the MAP approach to the multi-target-tracking problem for its convenience.
3.2. Markov Chain Monte Carlo Data Association Algorithm
In this section, we explain an MCMC sampler designed to solve the multi-target-tracking problem. MCMC is a general method to generate samples from a distribution by constructing a Markov chain whose states are and whose stationary distribution is . If we are at state , we propose following the proposal distribution . The move is accepted with an acceptance probability where otherwise the sampler stays at , so that the detailed balance is satisfied. If we make sure that is irreducible and aperiodic, then converges to its stationary distribution by the ergodic theorem .
The MCMC data association (MCMCDA) algorithm is described in Algorithm 1. MCMCDA is an MCMC algorithm whose state space is described in Section 3.1, and whose stationary distribution is the posterior (7). The proposal distribution for MCMCDA consists of five types of moves. They are (1) birth/death move pair; (2) split/merge move pair; (3) extension/reduction move pair; (4) track update move; and (5) track switch move. The MCMCDA moves are graphically illustrated in Figure 3. For a detailed description of each move, see . The inputs for MCMCDA are the set of all observations , the number of samples , and the initial state . The acceptance probability is defined in (8) where = from (7). In Algorithm 1, we use MCMC to find a solution to a combinatorial optimization problem. So it can be considered as simulated annealing at a constant temperature.
In addition, the memory requirement of the algorithm is at its bare minimum. Instead of keeping all , we simply keep the partition with the maximum posterior, . Notice that, in MCMC, the construction of is done on the fly according to the proposal distribution and there is no need to store previously visited states.
The Markov chain designed by Algorithm 1 is irreducible and aperiodic . In addition, the transitions described in Algorithm 1 satisfy the detailed balance condition since it uses the Metropolis-Hastings kernel (8). Hence, by the ergodic theorem, the chain converges to its stationary distribution .
3.3. Online Hierarchical MCMCDA
At each supernode, we implement the online MCMCDA algorithm with a sliding window of size using Algorithm 1. This online implementation of MCMCDA is suboptimal because it considers only a subset of past measurements. But since the contribution of older measurements to the current estimate is much less than recent measurements, it is still a good approximation. At each time step, we use the previous estimate to initialize MCMCDA and run MCMCDA on the observations belonging to the current window. Supernode maintains a set of observations , where is the current time and is the th fused measurement received by supernode . At time , the observations at time are removed from and a new set of observations is appended to . Any delayed observations are inserted into the appropriate slots. Then, each supernode initializes the Markov chain with the previously estimated tracks and executes Algorithm 1 on . Once a target is found, the next state of the target is predicted. If the predicted next state belongs to the surveillance area of another supernode, the target's track information is passed to the corresponding supernode. These newly received tracks are then incorporated into the initial state of MCMCDA for the next time step.
Since each supernode maintains its own set of tracks, there can be multiple tracks of a single object maintained by different supernodes. To make the algorithm fully hierarchical, we do track-level data association to combine tracks from different supernodes. Let be the set of tracks maintained by supernode . Let be the combined observations only from the established tracks. We form a new set of tracks from while making sure that constraints defined in Section 3.1 are satisfied. Then we run Algorithm 1 on this combined observation set with the initial state . An example of hierarchical tracking and track-level data association is shown in Section 4.5.
4. Simulation Results
For simulations below, we consider the surveillance over a rectangular region on a plane, . The state vector is , where is a position in along the usual and axes and is a velocity vector. The linear dynamic and measurement models are used where is a sampling interval, and are white Gaussian noises with zero mean and covariance and (set according to Figure 1), respectively, and We assume a sensor grid, in which the separation between sensors is normalized to 1. So the unit length in simulation is the length of the sensor separation. In all simulations, and . For the sensor model, we use , , , and .
Since the number of targets is not fixed, it is difficult to measure the performance of an algorithm using a standard criterion such as the mean square error. Hence, we use two separate metrics to measure performance: the estimation error in the number of targets , and the estimation error in position . Let be the number of targets at time and be the estimated number of targets at time . We define as The computation of is done when it makes sense. At any , there can be at most common tracks. We find matches between true tracks and estimated tracks based on positions at . For each match , let and be the position of the true track and the estimated track at time , respectively. We define as Both and are normalized with respect to the number of targets for easier comparison.
We first evaluate the effect of the sensing range and empirically find that there is an optimal value at which the estimation error is minimized. Then we illustrate the robustness of our algorithm against sensor localization error, transmission failures, and communication delays. We then give an example of surveillance using wireless sensor networks and demonstrate how the hierarchical MCMCDA algorithm works.
4.1. Sensing Range
When localizing a single target, we can minimize the localization error by allowing more sensors to collaborate, which is equivalent to increasing as shown in Figure 1. But when there is more than one target, this is no longer true, since observations from different targets can collide, giving missing observations and observations away from target positions. Figure 4 shows the estimation errors and when 10 targets appear and disappear at random times and . For slow-speed vehicles, ; for medium-speed vehicles; for high-speed vehicles. For each vehicle type, five different scenarios are used. When , the sensors do not completely cover the surveillance region and do not detect targets at all times, hence the estimation error is higher. But as we increase beyond , estimation errors increase, since there are more collisions among observations of different targets. The estimation errors are low for high-speed vehicles since it is easier to disambiguate crossing targets. From Figure 4, we find that is a good range for all types of vehicles and it is used in simulations below. Notice that when , for each sensor , there are 28 neighboring sensors which are at most away from . We can also interpret this result in terms of sensor density for a fixed value of . Hence, once the surveillance region is fully covered by sensors, a further increase in density does not improve the estimation error.
4.2. Sensor Localization Error
The localization of sensor nodes in an adhoc wireless sensor network, without expensive hardware such as the global positioning system (GPS), is a challenging problem . Hence, an algorithm which utilizes sensor positions needs to be robust against the sensor localization error. Suppose that the true position of sensor node is and , where are Gaussian noises with zero mean and covariance . Figure 5 shows the estimation errors from tracking 10 targets as functions of the sensor localization error . It shows that the algorithm is robust against the sensor localization error and, for , the algorithm performs as if there is no sensor localization error. This is remarkable since corresponds to the case in which the average localization error is 0.707 times the separation between sensors. Notice that is always under 0.18, so the algorithm finds most tracks for all . But gets larger at high , since the target position estimates are based on incorrect node positions. Considering the fact that is computed from the norm of a vector in , is mostly due to the sensor localization error.
4.3. Transmission Failures
To assess the effects of transmission failures alone, we assume that there are no delayed observations, no false alarms, and no missing detections. A single supernode is placed at the center. As mentioned earlier, transmission failures are missing observations and Figure 6(a) shows the ratio between the number of lost packets and the number of total packets as a function of the transmission failure rate . As increases, we lose more packets and, at , we lose all packets. Figure 6 shows the estimation errors and the algorithm performs well for . The estimation error is low at high since most of packets are lost at high , making the data association problem easier. Notice that when more than 50% of packets are lost (see Figure 6(a)). It shows that our algorithm is very robust against transmission failures and tolerates up to 50% lost-to-total packet ratio. Hence, for given , we can find the maximum radius of a tracking group, measured by the number of hops from a supernode, such that , sustaining the performance of the algorithm. For example, if , , that is, the most distant node can be 38 hops away from a supernode. But one must consider the communication delay which increases with the number of hops.
4.4. Communication Delays
To assess the effects of communication delays alone, we assume that there are no transmission failures, no false alarms, and no missing observations. Figure 7(a) shows the ratio between the number of delayed packets and the number of total packets as a function of the communication delay rate . As increases to 1, all packets are delayed. Since , we do not receive all the delayed packets and the ratio between the number of delayed packets that are eventually received and the number of packets is shown in a dotted line in Figure 7(a). The estimation errors are shown in Figure 7. It shows a good performance for . At , 90% of packets are delayed and 72% of packets have delays less than . Hence, the system tolerates up to 90% delayed-to-total packet ratio.
4.5. An Example of Surveillance with Sensor Networks
In this section, we give an example of surveillance with sensor networks. The surveillance region is divided into four quadrants and sensors in each quadrant form a tracking group, where a supernode is placed at the center of each quadrant. The scenario is shown in Figure 8(a). We used , , and . The surveillance duration is increased to . Figure 8(b) shows the observations received by supernodes. There were a total of 1,174 observations and 603 observations were false alarms. A total of 319 packets out of 1,174 packets were lost due to transmission failures and 449 packets out of 855 received packets were delayed. The tracks estimated by the algorithm are shown in Figure 8(c). Figure 8(c) shows the tracks estimated locally by supernodes while Figure 8(d) shows the tracks estimated by the track-level data association step. Figure 8(d) shows that the track-level data association step corrects mistakes made by supernodes due to missing observations at the tracking group boundaries. The ability to correct mistakes made by a supernode is another strength of our algorithm. The algorithm is written in C++ and MATLAB and run on a PC with a 2.6-GHz Intel Pentium 4 processor. It takes less than 0.06 seconds per supernode, per simulation time step.
5.1. Indoor Experiments
As a proof of concept, we implemented a scaled down tracking scenario on a 9-by-5 sensor network testbed (see Figure 9). The tracking scenario was that of two crossing targets moving at constant speed. Due to the small physical size of the network, there is a single supernode and hence no track-level data association. Also, to retain enough distinct data points to form meaningful tracks, we did not aggregate sensor readings as in (2).
The sensor node platform used for our experiment was the mica2dot , an embedded, low-power, wireless platform running TinyOS  which had a 4 MHz ATMega128 processor with 4 kB of RAM and 128 kB of program memory, and a CC1000 radio that provided up to 38.4 kbps transmission rate. Each node was equipped with a Honeywell HMC1002 2-axis magnetometer to sense moving targets. See Figure 9(a). Our moving targets were modified RC-cars called COTSBOTs , which had a 1-inch (2.54 cm) diameter, 0.125-inch (3.175 mm) thick neodymium magnet strapped to the top of the car.
The sensor nodes trigger a detection event when where is the current detection time, and are the , and -axis magnetometer readings, and is the window size. We chose this detection function because of its low computation requirement and robust performance, despite a tendency for the bias to drift on the magnetometers (see  for more details). We used and in our experiments.
We used the minimum-transmission-routing protocol  to route the sensor readings back to the supernode for calculations. This algorithm has better end-to-end reliability than shortest path routing, ensuring fewer packets are dropped from transmission errors. We performed multiple experiments with different target trajectories and velocities, all with comparable performance. The result from one of these experiments is shown in Figure 11 and snapshots are shown in Figure 10. The experiments showed that the algorithm performed well in the presence of false alarms and missing observations.
5.2. Outdoor Experiments
In this section, we present an outdoor demonstration described in  which is based on the proposed hierarchical multi-target-tracking algorithm for solving the multi-target-tracking problem. In addition to outdoor experiments shown here, the MCMCDA algorithm has been successfully applied to track vehicles, people, and ground robots in urban environments [40, 41]. The experiment was performed on a large-scale, long-term, outdoor sensor network testbed deployed on a short grass field at UC Berkeley's Richmond Field Station (see Figure 12). A total of 557 sensor nodes were deployed and 144 of these nodes were allotted for the tracking and PEG experiments. However, six out of the 144 nodes used in the experiment were not functioning on the day of the demo, reflecting the difficulties of deploying large-scale, outdoor systems. The sensor nodes were deployed at approximately 4- to 6-meter spacing in a grid. Each sensor node was elevated using a camera tripod to prevent the passive infrared (PIR) sensors from being obstructed by grass and uneven terrain (see Figure 12(a)). The true locations of the nodes were measured during deployment using differential GPS and stored in a table at the base station for reference. However, in the experiments the system assumed the nodes were placed exactly on a 5-meter spacing grid to highlight the robustness of the system against localization error.
In order to solve the multi-target tracking and pursuit-evasion game, we have proposed a hierarchical real-time control system LochNess which is shown in Figure 13. LochNess is composed of seven layers: the sensor networks, the multisensor fusion (MSF) module, the multi-target tracking (MTT) modules, the multi-track-fusion (MTF) module, the multi-agent coordination (MAC) module, the path planner module, and the path follower modules.
Under this architecture, sensors are spread over the surveillance region and form an adhoc network. The sensor network detects moving objects in the surveillance region and the MSF module converts the sensor measurements into target position estimates (or reports) using spatial correlation. We consider a hierarchical sensor network and the Tier-2 nodes are supernodes considered in this paper. Fused measurements are delievered to the Tier-2 nodes and the MTT module in each Tier-2 node estimates the number of evaders, the positions and velocities of the evaders, and the estimation error bounds. Each Tier-2 node communicates with its neighboring Tier-2 nodes when a target moves away from the region monitored by its tracking group. Lastly, the tracks estimated by the Tier-2 nodes are combined hierarchically by the MTF module at the base station.
The estimates computed by the MTF module are then used by the MAC module to estimate the expected capture times of all pursuer-evader pairs. Based on these estimates, the MAC module assigns one pursuer to one evader by solving the bottleneck assignment problem  such that the estimated time to capture the last evader is minimized. Once the assignments are determined, the path planner module computes a trajectory for each pursuer to capture its assigned evader in the least amount of time without colliding into other pursuers. Then, the base station transmits each trajectory to the path-following controller of the corresponding pursuer. The path-following controller modifies the pursuer's trajectory on the fly to avoid any obstacles sensed by the pursuer's on-board sensors. The MTT and MTF modules are based on the proposed hierarchical multi-target-tracking algorithm. For more detail about the description about the system used in the experiments, see .
We demonstrated the system on one, two, and three human targets, with targets entering the field at different times. In all three experiments, the tracking algorithm correctly estimated the number of targets and produced correct tracks. Furthermore, the algorithm correctly disambiguated crossing targets in the two-target and three-target experiments without classification labels on the targets. Figure 14(a) shows an example with three humans walking through the field. The three humans entered and exited the field around time 10 and 80, respectively. During the experiment, the algorithm correctly rejected false alarms and compensated for missing detections. There were many false alarms during the span of the experiments. Though not shown in the figures, the algorithm dynamically corrected previous track hypotheses as it received more sensor readings. A live picture of this experiment is shown in Figure 12(b). Figures 14(b) and 14(c) show the multi-target-tracking results with two persons walking through the field. Note that the MTT module is able to correctly disambiguate the presence of two targets (right panel of Figure 14(c)) using past measurements, despite the fact that the MSF module reports the detection of a single target (upper left panel of Figure 14(b)).
In this paper, a scalable hierarchical multi-target-tracking algorithm for wireless sensor networks is presented. The algorithm is based on the efficient MCMCDA algorithm, and it is suitable for autonomous real-time surveillance in sensor networks. This new multi-target-tracking algorithm can initiate and terminate tracks and requires a small amount of memory. The task of tracking is done hierarchically for real-time operation by forming a tracking group around a supernode and later combining tracks from different supernodes. In order to reduce the communication overhead, observations are first fused locally and then transmitted to its supernode. The algorithm is robust against sensor localization error and there is no performance loss up to the average localization error of 0.7 times the separation between sensors. The algorithm is also robust against transmission failures and communication delays. In particular, the algorithm tolerates up to 50% lost-to-total packet ratio and 90% delayed-to-total packet ratio. The extensive simulation and experimental results show that the algorithm is well suited for wireless sensor networks where transmission failures and communication delays are frequent.
AbbreviationsList of Symbols
|:||Assignment of node to supernode|
|:||Number of targets|
|:||Number of steps in MCMCDA|
|:||Number of sensor nodes|
|:||Number of supernodes|
|:||Target detection probability|
|:||Probability of delaying a message|
|:||Transmission failure probability|
|:||Probability of successful end-to-end communication|
|:||Target disappearance probability|
|:||Sensing range of a sensor node|
|:||Shortest path from node to|
|:||Time duration of surveillance|
|:||Volume of the surveillance region|
|:||Sliding window size for online MCMCDA|
|:||Birth rate of new targets per unit time and volume|
|:||False alarm rate per unit time and volume|
|:||Set of measurements from target|
|:||Collection of joint association events|
|:||Joint association event|
|:||Initial state for MCMCDA.|
The author would like to thank Phoebus Chen for his contribution to the indoor experiment. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2010-0013354). A preliminary version of this work was presented at the IEEE International Conference on Robotics and Automation, 2005 .
- D. Culler, D. Estrin, and M. Srivastava, “Overview of sensor networks,” Computer, vol. 37, no. 8, pp. 41–49, 2004.
- D. Estrin, D. Culler, K. Pister, and G. Sukhatme, “Connecting the physical world with pervasive networks,” IEEE Pervasive Computing, vol. 1, no. 1, pp. 59–69, 2002.
- L. Schenato, S. Oh, S. Sastry, and P. Bose, “Swarm coordination for pursuit evasion games using sensor networks,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2493–2498, Barcelona, Spain, April 2005.
- B. Sinopoli, C. Sharp, L. Schenato, S. Schaffert, and S. S. Sastry, “Distributed control applications within sensor networks,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1235–1245, 2003.
- J. Hightower and G. Borriello, “Location systems for ubiquitous computing,” Computer, vol. 34, no. 8, pp. 57–66, 2001.
- Y. Bar-Shalom and T. Fortmann, Tracking and Data Association, Academic Press, San Diego, Calif, USA, 1988.
- D. B. Reid, “An algorithm for tracking multiple targets,” IEEE Transactions on Automatic Control, vol. 24, no. 6, pp. 843–854, 1979.
- C. Chong, S. Mori, and K. Chang, “Distributed multitarget multisensor tracking,” in Multitarget-Multisensor Tracking: Advanced Applications, Y. Bar-Shalom, Ed., pp. 247–295, Artech House, Norwood, Mass, USA, 1990.
- S. Oh, S. Russell, and S. Sastry, “Markov chain Monte Carlo data association for multi-target tracking,” IEEE Transactions on Automatic Control, vol. 54, no. 3, pp. 481–497, 2009.
- D. Li, K. D. Wong, Y. H. Hu, and A. M. Sayeed, “Detection, classification, and tracking of targets,” IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 17–29, 2002.
- A. Arora, P. Dutta, S. Bapat et al., “A line in the sand: a wireless sensor network for target detection, classification, and tracking,” Computer Networks, vol. 46, no. 5, pp. 605–634, 2004.
- S. Oh and S. Sastry, “Tracking on a graph,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05), pp. 195–202, Los Angeles, Calif, USA, April 2005.
- R. Brooks, D. Friedlander, J. Koch, and S. Phoha, “Tracking multiple targets with self-organizing distributed ground sensors,” Journal of Parallel and Distributed Computing, vol. 64, no. 7, pp. 875–884, 2004.
- C. Sharp, S. Schaffert, A. Woo et al., “Design and implementation of a sensor network system for vehicle tracking and autonomous interception,” in Proceedings of the 2nd European Workshop onWireless Sensor Networks (EWSN '05), pp. 93–107, February 2005.
- J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko, and D. Rus, “Tracking a moving object with a binary sensor network,” in Proceedings of the ACM 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 150–161, November 2003.
- W. Chen, J. Hou, and L. Sha, “Dynamic clustering for acoustic target tracking in wireless sensor networks,” in Proceedings of the 11th IEEE International Conference on Network Protocols, pp. 284–294, November 2003.
- M. Coates, “Distributed particle filters for sensor networks,” in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04), pp. 99–107, April 2004.
- J. Liu, J. Liu, J. Reich, P. Cheung, and F. Zhao, “Distributed group management for track initiation and maintenance in target localization applications,” in Proceedings of the 2nd workshop on Information Processing in Sensor Networks, pp. 113–128, April 2003.
- F. Zhao, J. Liu, J. Liu, L. Guibas, and J. Reich, “Collaborative signal and information processing: an information-directed approach,” Proceedings of the IEEE, vol. 91, no. 8, pp. 1199–1209, 2003.
- J. Liu, J. Reich, and F. Zhao, “Collaborative in-network processing for target tracking,” Eurasip Journal on Applied Signal Processing, vol. 2003, no. 4, pp. 378–391, 2003.
- D. McErlean and S. Narayanan, “Distributed detection and tracking in sensor networks,” in Proceedings of the 36th Asilomar Conference on Signals Systems and Computers, pp. 1174–1178, November 2002.
- J. Shin, L. Guibas, and F. Zhao, “A distributed algorithm for managing multi-target identities in wireless ad-hoc sensor networks,” in Proceedings of the 2nd workshop on Information Processing in Sensor Networks, pp. 223–238, April 2003.
- J. Liu, M. Chu, J. Liu, J. Reich, and F. Zhao, “Distributed state representation for tracking problems in sensor networks,” in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN '04), pp. 234–242, April 2004.
- M. Chu, S. Mitter, and F. Zhao, “Distributed multiple target tracking and data association in ad hoc sensor networks,” in Proceedings of the 6th International Conference on Information Fusion, pp. 447–454, July 2004.
- J. B. Collins and J. K. Uhlmann, “Efficient gating in data association with multivariate Gaussian distributed states,” IEEE Transactions on Aerospace and Electronic Systems, vol. 28, no. 3, pp. 909–916, 1992.
- A. Poore, “Multidimensional assignment and multitarget tracking,” in Partitioning Data Sets, I. J. Cox, P. Hansen, and B. Julesz, Eds., pp. 169–196, American Mathematical Society, Providence, RI, USA, 1995.
- S. Oh, L. Schenato, P. Chen, and S. Sastry, “Tracking and coordination of multiple agents using sensor networks: system design, algorithms and experiments,” Proceedings of the IEEE, vol. 95, no. 1, pp. 234–254, 2007.
- T. Kurien, “Issues in the design of practical multitarget tracking algorithms,” in Multitarget-Multisensor Tracking: Advanced Applications, Y. Bar-Shalom, Ed., Artech House, Norwood, Mass, USA, 1990.
- J. Hill, M. Horton, R. Kling, and L. Krishnamurthy, “The platforms enabling wireless sensor networks,” Communications of the ACM, vol. 47, no. 6, pp. 41–46, 2004.
- S. Oh, I. Hwang, and S. Sastry, “Distributed multitarget tracking and identity management,” Journal of Guidance, Control, and Dynamics, vol. 31, no. 1, pp. 12–29, 2008.
- S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure in wireless ad-hoc sensor networks,” in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 139–150, July 2001.
- H. Pasula, S. Russell, M. Ostland, and Y. Ritov, “Tracking many objects with many sensors,” in Proceedings of the International Joint Conference on Artificial Intelligence, Stockholm, Sweden, July 1999.
- G. Roberts, “Markov chain concepts related to sampling algorithms,” in Markov Chain Monte Carlo in Practice, W. Gilks, S. Richardson, and D. Spiegelhalter, Eds., Interdisciplinary Statistics, Chapman and Hall, New York, NY, USA, 1996.
- K. Whitehouse, F. Jiang, A. Woo, C. Karlof, and D. Culler, “Sensor field localization: a deployment and empirical analysis,” Tech. Rep. UCB//CSD-04-1349, University of California, Berkeley, Calif, usa, 2004.
- Berkeley, “Mica2dot hardware design files,” 2003, motes manufactured by Crossbow Technology Inc., http://www.tinyos.net/scoop/special/hardware.
- J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, “System architecture directions for networked sensors,” in Proceedings of the 9th Internatinal Conference Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX '00), pp. 93–104, Cambridge, Mass, USA, November 2000.
- S. Bergbreiter and K. S. J. Pister, “Cotsbots: an off-the-shelf platform for distruted robotics,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '03), pp. 27–31, Las Vegas, Nev, USA, October 2003.
- Honeywell, “1- and 2- axis magnetic sensors,” http://www.ssec.honeywell.com/magnetic/datasheets/hmc1001-2&1021-2.pdf.
- A. Woo, T. Tong, and D. Culler, “Taming the underlying challenges of reliable multihop routing in sensor networks,” in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 14–27, Los Angeles, Calif, USA, November 2003.
- M. Kushwaha, S. Oh, I. Amundson, X. Koutsoukos, and A. Ledeczi, “Target tracking in urban environments using audio-video signal processing in heterogeneous wireless sensor networks,” in Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers (ASILOMAR '08), pp. 1606–1610, Pacific Grove, Calif, USA, October 2008.
- M. Meingast, M. Kushwaha, S. Oh, X. Koutsoukos, A. Ledeczi, and S. Sastry, “Fusion-based localization for a heterogeneous camera network,” in Proceedings of the 2nd ACM/IEEE International Conference on Distributed Smart Cameras (ICDSC '08), Pacific Grove, Calif, USA, September 2008.
- R. Burkard and R. Cela, “Linear assignment problem and extensions,” Tech. Rep. 127, Karl-Franzens University of Graz, Graz, Austria, 1998.
- S. Oh, S. Sastry, and L. Schenato, “A hierarchical multiple-target tracking algorithm for sensor networks,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2197–2202, Barcelona, Spain, April 2005.