A Scalable Multi-Target Tracking Algorithm for Wireless Sensor Networks

Abstract

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.

1. Introduction

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 [3], distributed control [4], spatiotemporal data collection, and other location-based services [5]. Two well-known multi-target tracking algorithms are joint probabilistic data association (JPDA) filter [6] 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 [13]. The NNF [6] 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 [27].

Markov chain Monte Carlo data association (MCMCDA) presented in [9] 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) [7] and outperforms MHT with heuristics (i.e., pruning, gating, clustering, N-scan-back logic and k-best hypotheses) under extreme conditions, such as a large number of targets in a dense environment, low detection probabilities, and high false alarm rates [9]. 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 [29], gateway nodes such as Stargate, Intrinsyc Cerfcube, and PC104 [29], and the Tier-2 nodes used in the experiment of [27]. 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 [30].

As mentioned earlier, the algorithm presented in this paper is used in [27]. Although the overview of the algorithm is described in [27], the focus of [27] 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 [27]. 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 $N_s$ be the number of sensor nodes, including both supernodes and regular nodes, deployed over the surveillance region $ℛ\subset {ℝ}^{\mathrm{2}}$ . We assume that each supernode can communicate with its neighboring supernodes. Let $s_i\in ℛ$ be the location of the ith sensor node and let $S=\{s_i:\mathrm{1}\le i\le N_s\}$ . Let $G=(S,E)$ be a communication graph such that $(s_i,s_j)\in E$ if and only if node i can communicate with node j. Let $N_{ss}\ll N_s$ be the number of supernodes and let $s_j^s\in S$ be the position of the jth supernode, for $j=\mathrm{1},\dots ,N_{\text{ss}}$ . Let $g:\{\mathrm{1},\dots ,N_s\}\to \{\mathrm{1},\dots ,N_{\text{ss}}\}$ be the assignment of each sensor to its nearest supernode such that $g(i)=j$ if $\parallel s_i-s_j^s\parallel ={\min \hspace{0.17em}}_{k=\mathrm{1},\dots ,N_{\text{ss}}}\parallel s_i-s_k^s\parallel$ . For a node i, if $g(i)=j$ , the shortest path from $s_i$ to $s_j^s$ in G is denoted by $\text{sp}(i)$ . For each supernode j, its tracking group contains a set of nodes $\{s_i\in S:g(i)=j\}$ .

Let $R_s\in ℝ$ be the sensing range. If there is an object at $x\in ℛ$ , a sensor can detect the presence of the object. Each sensor records the sensor's signal strength,

$$\begin{array}{cc}& z_i=\{\begin{array}{cc}\frac{\beta }{\mathrm{1}+\gamma {\Vert s_i-x\Vert }^{\alpha }}+w_i^s,\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{if\hspace{0.17em}\hspace{0.17em}}\Vert s_i-x\Vert \le R_s,\hfill \\ w_i^s,\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}\Vert s_i-x\Vert >R_s,\hfill \end{array}\end{array}$$

(1)

where α, β, and γ are constants specific to the sensor type, and we assume that $z_i$ are normalized such that $w_i^s$ 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 i, if $z_i\ge \eta$ , where η is a threshold set for appropriate values of detection and false-positive probabilities, the node transmits $z_i$ to its neighboring nodes, which are at most $\mathrm{2}{R}_s$ away from $s_i$ , and listens to incoming messages from its $\mathrm{2}{R}_s$ neighborhood. Note that this approach is similar to the leader election scheme in [18] and we assume that the transmission range of each node is larger than $\mathrm{2}{R}_s$ . However, this approach may cause some missing observations if there is more than one object in this disk of radius $\mathrm{2}{R}_s$ . A better approach to fuse local data is required and we will address this issue in our future work. For the node i, if $z_i$ is larger than all incoming messages, $z_{i_{\mathrm{1}}},\dots ,z_{i_{k-\mathrm{1}}}$ , and $z_{i_k}=z_i$ , then the position of an object is estimated as

$$\begin{array}{cc}& {\widehat{z}}_i=\frac{{\sum }_{j=\mathrm{1}}^k{z}_{i_j}{s}_{i_j}}{{\sum }_{j=\mathrm{1}}^k{z}_{i_j}}.\end{array}$$

(2)

The estimate ${\widehat{z}}_i$ corresponds to the computation of a center of mass of the sensing nodes weighed by measured signal strengths. The node i transmits ${\widehat{z}}_i$ to the supernode $g(i)$ via the shortest path $\text{sp}(i)$ . If $z_i$ is not the largest compared to the incoming messages, the node i 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.

Figure 1

The single target position estimation error as a function of $R_s$ . See Section 4 for the sensor network setup used in simulations (Monte Carlo simulation of 1000 samples, unity corresponds to the separation between sensors).

A transmission along the edge $(s_i,s_j)$ fails independently with probability $p_{\text{te}}$ 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 k is the number of hops required to relay data from a sensor node to its supernode, the probability of successful transmission decays exponentially as k increases. To overcome this problem, we use k independent paths to relay data if the reporting sensor node is k hops away from its supernode. The probability of successful communication $p_{ts}$ from the reporting node i to its supernode $g(i)$ can be computed as

$$\begin{array}{cc}& p_{\text{ts}}\left(k;p_{\text{te}}\right)=\mathrm{1}-{\left(\mathrm{1}-{\left(\mathrm{1}-p_{\text{te}}\right)}^k\right)}^k,\end{array}$$

(3)

where $k=|\text{sp}(i)|$ . 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 $p_{\text{te}}$ .

We assume each node has the same probability $p_{\text{de}}$ of delaying a message. If $d_i$ is the number of (additional) delays on a message originating from the sensor i, that is, the number of sampling intervals elapsed since the required arrival time at the supernode $g(i)$ , $d_i$ is distributed as

$$\begin{array}{cc}& p\left(d_i=d;p_{\text{de}\mathrm{\hspace{0.17em}\hspace{0.17em}}}\right)=\left(\begin{array}{c}\left|\text{sp}\left(i\right)\right|+d-\mathrm{1}\\ d\end{array}\right){\left(\mathrm{1}-p_{\text{de}}\right)}^{\left|\text{sp}\left(i\right)\right|}{\left(p_{\text{de}}\right)}^d.\end{array}$$

(4)

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 $|\text{sp}(i)|$ 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 $p_{\text{de}}$ .

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 $T\in {\mathbb{Z}}^{+}$ be the duration of surveillance. Let K be the number of targets that appear in the surveillance region ℛ during the surveillance period. Each target k moves in ℛ for some duration $[t_{i\mathrm{\hspace{0.17em}\hspace{0.17em}}}^k,t_{f\mathrm{\hspace{0.17em}\hspace{0.17em}}}^k]\subset [\mathrm{1},T]$ . Notice that the exact values of K and $\{t_i^k,t_f^k\}$ are unknown. Each target arises at a random position in ℛ at $t_i^k$ , moves independently around ℛ until $t_f^k$ , and disappears. At each time, an existing target persists with probability $\mathrm{1}-p_z$ and disappears with probability $p_z$ . The number of targets arising at each time over ℛ has a Poisson distribution with a parameter ${\lambda }_{b}V$ where ${\lambda }_b$ is the birth rate of new targets per unit time, per unit volume, and V is the volume of ℛ. The initial position of a new target is uniformly distributed over ℛ.

Let $F^k:{ℝ}^{n_x}\to {ℝ}^{n_x}$ be the discrete-time dynamics of the target k, where $n_x$ is the dimension of the state variable, and let $x^k(t)\in {ℝ}^{n_x}$ be the state of the target k at time t for $t=t_i^k,\dots ,t_f^k$ . The target k moves according to

$$\begin{array}{cc}& x^k\left(t+\mathrm{1}\right)=F^k\left(x^k\left(t\right)\right)+w^k\left(t\right),\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}t=t_i^k,\dots ,t_f^k-\mathrm{1},\end{array}$$

(5)

where $w^k(t)\in {ℝ}^{n_x}$ 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 $p_d$ . Notice that, with probability $\mathrm{1}-p_{d\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ , 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 ${\lambda }_{f}V$ , where ${\lambda }_f$ is the false alarm rate per unit time, per unit volume. Let $n(t)$ be the number of observations at time t, including both noisy observations and false alarms. Let $y^j(t)\in {ℝ}^{n_y}$ be the jth observation at time t for $j=\mathrm{1},\dots ,n(t)$ , where $n_y$ is the dimension of each observation vector. Each target generates a unique observation at each sampling time if it is detected. Let $H^j:{ℝ}^{n_x}\to {ℝ}^{n_y}$ be the observation model. Then the observations are generated as follows:

$$\begin{array}{cc}& y^j\left(t\right)=\{\begin{array}{cc}{H}^j\left(x^k\left(t\right)\right)+v^j\left(t\right),\hfill & \text{if}{\hspace{0.17em}y}^j\left(t\right)\text{\hspace{0.17em}is\hspace{0.17em}from\hspace{0.17em}}{x}^k\left(t\right),\hfill \\ u_f\left(t\right),\hfill & \text{otherwise,}\hfill \end{array}\end{array}$$

(6)

where $v^j(t)\in {ℝ}^{n_y}$ are white noise processes and $u_f(t)~\text{Unif}(ℛ)$ 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 [32].

The main objective of the multi-target tracking problem is to estimate K, $\{t_i^k,t_f^k\}$ and $\{x^k(t):t_i^k\le t\le t_f^k\}$ , for $k=\mathrm{1},\dots ,K$ , from noisy observations.

Let $Y(t)=\{y^j(t):j=\mathrm{1},\dots ,n(t)\}$ be all measurements at time t and $Y=\{Y(t):\mathrm{1}\le t\le T\}$ be all measurements from $t=\mathrm{1}$ to $t=T$ . Let $\mathrm{\Omega }$ be a collection of partitions of Y such that, for $\omega \in \mathrm{\Omega }$ , $\omega =\{{\tau }_{\mathrm{0}},{\tau }_{\mathrm{1}},\dots ,{\tau }_K\}$ , where ${\tau }_{\mathrm{0}}$ is a set of false alarms and ${\tau }_k$ is a set of measurements from target k for $k=\mathrm{1},\dots ,K$ . Note that ω is also known as a joint association event in literature. More formally, ω is defined as follows:

• (1)

$\omega =\{{\tau }_{\mathrm{0}},{\tau }_{\mathrm{1}},\dots ,{\tau }_K\}$ ;

(2)

${\bigcup }_{k=\mathrm{0}}^K‍{\tau }_k=Y$ and ${\tau }_i\cap {\tau }_j=\varnothing$ for $i\ne j$ ;

(3)

${\tau }_{\mathrm{0}}$ is a set of false alarms;

(4)

$|{\tau }_k\cap Y(t)|\le \mathrm{1}$ for $k=\mathrm{1},\dots ,K$ and $t=\mathrm{1},\dots ,T$ ;

(5)

$|{\tau }_k|\ge \mathrm{2}$ for $k=\mathrm{1},\dots ,K$ .

An example of a partition is shown in Figure 2. Here, K is the number of tracks for the given partition $\omega \in \mathrm{\Omega }$ . We call ${\tau }_k$ a track when there is no confusion although the actual track is the set of estimated states from the observations ${\tau }_k$ . 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 ${\lambda }_f>\mathrm{0}$ . For special cases in which $p_d=\mathrm{1}$ or ${\lambda }_f=\mathrm{0}$ , the definition of $\mathrm{\Omega }$ can be adjusted accordingly.

Figure 2

(a) An example of observations Y (each circle represents an observation and numbers represent observation times). (b) An example of a partition ω of Y.

Let $n_e(t-\mathrm{1})$ be the number of targets at time $t-\mathrm{1}$ , $n_z(t)$ be the number of targets terminated at time t and $n_c(t)=n_e(t-\mathrm{1})-n_z(t)$ be the number of targets from time $t-\mathrm{1}$ that have not terminated at time t. Let $n_b(t)$ be the number of new targets at time t, $n_d(t)$ be the number of actual target detections at time t, and $n_u(t)=n_c(t)+n_b(t)-n_d(t)$ be the number of undetected targets. Finally, let $n_f(t)=n(t)-n_d(t)$ be the number of false alarms. Using the Bayes rule, it can be shown that the posterior of ω is:

$$\begin{array}{l}P\left(\omega \mid Y\right)\propto P\left(\omega \right)\cdot P\left(Y\mid \omega \right)\\ \propto \prod _{t=\mathrm{1}}^T‍p_z^{n_z\left(t\right)}{\left(\mathrm{1}-p_z\right)}^{n_c\left(t\right)}{p}_d^{n_{d\mathrm{\hspace{0.17em}\hspace{0.17em}}}\left(t\right)}{\left(\mathrm{1}-p_d\right)}^{n_{u\left(t\right)}}\\ \times {\left({\lambda }_{b}V\right)}^{n_b\left(t\right)}{\left({\lambda }_{f}V\right)}^{n_f\left(t\right)}\cdot P\left(Y\mid \omega \right),\end{array}$$

(7)

where $P(Y\mid \omega )$ is the likelihood of observations Y given ω, which can be computed based on the chosen dynamic and measurement models. For example, the computation of $P(Y\mid \omega )$ for the linear dynamic and measurement models can be found in [9]. Our formulation of (7) is similar to MHT [28], and the derivation of (7) can be found in [28]. The parameters $p_z$ , $p_d$ , ${\lambda }_b$ , and ${\lambda }_f$ 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 [9]: maximum a posteriori (MAP) and Bayesian approaches. The MAP approach finds a partition of observations such that $P(\omega \mid Y)$ 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, $𝔼(x^k(t)\mid Y)$ is the MMSE estimate for the state $x^k(t)$ of target k. However, when the number of targets is not fixed, a unique labeling of each target is required to find $𝔼(x^k(t)\mid Y)$ 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 $\pi (\omega )$ . If we are at state $\omega \in \mathrm{\Omega }$ , we propose $\omega \prime \in \mathrm{\Omega }$ following the proposal distribution $q(\omega ,\omega \prime )$ . The move is accepted with an acceptance probability $A(\omega ,\omega \prime )$ where

$$\begin{array}{cc}& A\left(\omega ,{\omega }^{\prime }\right)=\min \left(\mathrm{1},\frac{\pi \left({\omega }^{\prime }\right)q\left({\omega }^{\prime },\omega \right)}{\pi \left(\omega \right)q\left(\omega ,{\omega }^{\prime }\right)}\right),\end{array}$$

(8)

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 [33].

The MCMC data association (MCMCDA) algorithm is described in Algorithm 1. MCMCDA is an MCMC algorithm whose state space is $\mathrm{\Omega }$ 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 [9]. The inputs for MCMCDA are the set of all observations Y, the number of samples $n_{\text{mc}}$ , and the initial state ${\omega }_{\text{init}}$ . The acceptance probability $A(\omega ,\omega \prime )$ is defined in (8) where $\pi (\omega )$ = $P(\omega \mid Y)$ 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.

Algorithm 1: MCMCDA.

Input: $Y,n_{\text{mc}},{\omega }_{\text{init}}$

Output:   $\widehat{\omega }$

    $\widehat{\omega }=\omega \leftarrow {\omega }_{\text{init}}$

   for   $n=1$ to $n_{\text{mc}}$   do

      propose ${\omega }^{\prime }$ based on ω (see [9])

      sample U from Unif[ $\mathrm{0,1}$ ]

       $\omega \leftarrow {\omega }^{\prime }$ if $U<A(\omega ,{\omega }^{\prime })$

       $\widehat{\omega }\leftarrow \omega$ if $p(\omega \mid Y)/p(\widehat{\omega }\mid Y)>1$

end for

Figure 3

A graphical illustration of MCMCDA moves. Associations are indicated by dotted lines, and hollow circles are false alarms.

In addition, the memory requirement of the algorithm is at its bare minimum. Instead of keeping all $\{\omega (n){\}}_{n=\mathrm{1}}^{n_{\text{mc}}}$ , we simply keep the partition with the maximum posterior, $\widehat{\omega }$ . Notice that, in MCMC, the construction of $\omega \prime$ is done on the fly according to the proposal distribution $q(\omega ,\omega \prime )$ and there is no need to store previously visited states.

The Markov chain designed by Algorithm 1 is irreducible and aperiodic [9]. 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 [33].

3.3. Online Hierarchical MCMCDA

At each supernode, we implement the online MCMCDA algorithm with a sliding window of size $w_s$ 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 $a\in \{\mathrm{1},\dots ,N_{\text{ss}}\}$ maintains a set of observations $Y_a=\{y_a^j(t):\mathrm{1}\le j\le n(t),\hspace{0.17em}\hspace{0.17em}{t}_{\text{curr}\mathrm{\hspace{0.17em}\hspace{0.17em}}}-w_{s\mathrm{\hspace{0.17em}\hspace{0.17em}}}+\mathrm{1}\le t\le t_{\text{curr}}\}$ , where $t_{\text{curr}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ is the current time and $y_a^j(t)$ is the jth fused measurement received by supernode a. At time $t_{\text{curr}\mathrm{\hspace{0.17em}\hspace{0.17em}}}+\mathrm{1}$ , the observations at time $t_{\text{curr}\mathrm{\hspace{0.17em}\hspace{0.17em}}}-w_{s\mathrm{\hspace{0.17em}\hspace{0.17em}}}+\mathrm{1}$ are removed from $Y_a$ and a new set of observations is appended to $Y_a$ . 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 $Y_a$ . 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 ${\omega }_a$ be the set of tracks maintained by supernode a. Let $Y_c=\{{\tau }_i(t)\in {\omega }_a:\mathrm{1}\le t\le T,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le i\le |{\omega }_a|,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le a\le N_{\text{ss}}\}$ be the combined observations only from the established tracks. We form a new set of tracks ${\omega }_{\text{init}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ from $\{{\tau }_i\in {\omega }_a:\mathrm{1}\le i\le |{\omega }_a|,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le a\le N_{\text{ss}}\}$ while making sure that constraints defined in Section 3.1 are satisfied. Then we run Algorithm 1 on this combined observation set $Y_c$ with the initial state ${\omega }_{\text{init}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ . 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, $ℛ=[\mathrm{0,100}{]}^{\mathrm{2}}$ . The state vector is $x=[x_{\mathrm{1}},x_{\mathrm{2}},{\dot{x}}_{\mathrm{1}},{\dot{x}}_{\mathrm{2}}{]}^T$ , where $(x_{\mathrm{1}},x_{\mathrm{2}})$ is a position in ℛ along the usual x and y axes and $({\dot{x}}_{\mathrm{1}},{\dot{x}}_{\mathrm{2}})$ is a velocity vector. The linear dynamic and measurement models are used

$$\begin{array}{cc}& x\left(t+\delta \right)=A_{\delta }x\left(t\right)+G_{\delta }w\left(t\right),\\ y\left(t\right)=Cx\left(t\right)+v\left(t\right),\end{array}$$

(9)

where δ is a sampling interval, $w(t)$ and $v(t)$ are white Gaussian noises with zero mean and covariance $Q=\text{dia}g(\mathrm{0.1}{\mathrm{5}}^{\mathrm{2}},\mathrm{0.1}{\mathrm{5}}^{\mathrm{2}})$ and R (set according to Figure 1), respectively, and

$$\begin{array}{cc}& A_{\delta }=\left[\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \delta & \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \delta \\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right],\hspace{1em}{G}_{\delta }=\left[\begin{array}{cc}\frac{{\delta }^{\mathrm{2}}}{\mathrm{2}}& \mathrm{0}\\ \mathrm{0}& \frac{{\delta }^{\mathrm{2}}}{\mathrm{2}}\\ \delta & \mathrm{0}\\ \mathrm{0}& \delta \end{array}\right],\end{array}$$

(10)

$$\begin{array}{cc}& C=\left[\begin{array}{cccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\end{array}\right].\end{array}$$

(11)

We assume a $\mathrm{100}\times \mathrm{100}$ 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, $n_{\text{mc}\mathrm{\hspace{0.17em}\hspace{0.17em}}}=\mathrm{1000}$ and $w_s=\mathrm{10}$ . For the sensor model, we use $\alpha =\mathrm{2}$ , $\gamma =\mathrm{1}$ , $\eta =\mathrm{2}$ , and $\beta =\mathrm{3}(\mathrm{1}+\gamma R_s^{\alpha })$ .

Since the number of targets K 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 ${ϵ}_K$ , and the estimation error in position ${ϵ}_X$ . Let $K^{*}(t)$ be the number of targets at time t and $K(t)$ be the estimated number of targets at time t. We define ${ϵ}_K$ as

$$\begin{array}{cc}& {ϵ}_K=\frac{\mathrm{1}}{\sum ‍K^{*}\left(t\right)}\sum _{t=\mathrm{1}}^T‍\left|K\left(t\right)-K^{*}\left(t\right)\right|.\end{array}$$

(12)

The computation of ${ϵ}_X$ is done when it makes sense. At any t, there can be at most $M(t)=\min \hspace{0.17em}(K(t),K^{*}(t))$ common tracks. We find $M(t)$ matches between true tracks and estimated tracks based on positions at $t-\mathrm{1},t,t+\mathrm{1}$ . For each match i, let $x_i^{*}(t)$ and $x_i(t)$ be the position of the true track and the estimated track at time t, respectively. We define ${ϵ}_X$ as

$$\begin{array}{cc}& {ϵ}_X^{\mathrm{2}}=\frac{\mathrm{1}}{\sum ‍M\left(t\right)}\sum _{t=\mathrm{1}}^T‍\sum _{i=\mathrm{1}}^{M\left(t\right)}‍{\Vert x_i\left(t\right)-x_i^{*}\left(t\right)\Vert }^2.\end{array}$$

(13)

Both ${ϵ}_K$ and ${ϵ}_X$ 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 $R_s$ 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 ${ϵ}_K$ and ${ϵ}_X$ when 10 targets appear and disappear at random times and $T=\mathrm{50}$ . For slow-speed vehicles, $|{\dot{x}}_{\mathrm{1}}|,|{\dot{x}}_{\mathrm{2}}|\in [\mathrm{0,1}]$ ; $|{\dot{x}}_{\mathrm{1}}|,|{\dot{x}}_{\mathrm{2}}|\in [\mathrm{1,2}]$ for medium-speed vehicles; $|{\dot{x}}_{\mathrm{1}}|,|{\dot{x}}_{\mathrm{2}}|\in [\mathrm{2,5}]$ for high-speed vehicles. For each vehicle type, five different scenarios are used. When $R_s=\mathrm{0.5}$ , 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 $R_s$ beyond $\mathrm{1.0}$ , 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 $R_s=\mathrm{1.5}$ is a good range for all types of vehicles and it is used in simulations below. Notice that when $R_s=\mathrm{1.5}$ , for each sensor $s_i$ , there are 28 neighboring sensors which are at most $\mathrm{2}{R}_s$ away from $s_i$ . We can also interpret this result in terms of sensor density for a fixed value of $R_s$ . Hence, once the surveillance region is fully covered by sensors, a further increase in density does not improve the estimation error.

Figure 4

(a) The estimation error in the number of targets ${ϵ}_K$ as a function of sensing range $R_s$ . (b) The estimation error in position ${ϵ}_X$ as a function of sensing range $R_s$ . Unity corresponds to the separation between sensors.

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 [34]. Hence, an algorithm which utilizes sensor positions needs to be robust against the sensor localization error. Suppose that the true position of sensor node i is $s_i^{*}$ and $s_i=s_i^{*}+w_i^l$ , where $w_i^{l\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ are Gaussian noises with zero mean and covariance $\Sigma =\text{dia}g({\sigma }^{\mathrm{2}},{\sigma }^{\mathrm{2}})$ . 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 $\sigma \le \mathrm{0.5}$ , the algorithm performs as if there is no sensor localization error. This is remarkable since $\sigma \le \mathrm{0.5}$ corresponds to the case in which the average localization error is 0.707 times the separation between sensors. Notice that ${ϵ}_K$ is always under 0.18, so the algorithm finds most tracks for all σ. But ${ϵ}_X$ gets larger at high σ, since the target position estimates are based on incorrect node positions. Considering the fact that ${ϵ}_X$ is computed from the norm of a vector in ${ℝ}^{\mathrm{2}}$ , ${ϵ}_X$ is mostly due to the sensor localization error.

Figure 5

(a) The estimation error in the number of targets ${ϵ}_K$ as a function of the localization error (σ). (b) The estimation error in position ${ϵ}_X$ as a function of the localization error (σ).

Figure 6

(a) Ratio between the number of lost packets and the number of total packets. (b) The estimation error in the number of targets ${ϵ}_K$ as a function of $p_{\text{te}}$ . (c) The estimation error in position ${ϵ}_X$ as a function of $p_{\text{te}}$ .

Figure 7

(a) Ratio between the number of delayed packets and the number of total packets. (b) The estimation error in the number of targets ${ϵ}_K$ as a function of $p_{\text{de}}$ . (c) The estimation error in position ${ϵ}_X$ as a function of $p_{\text{de}}$ .

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 $p_{\text{te}}$ . As $p_{\text{te}\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ increases, we lose more packets and, at $p_{\text{te}}\approx \mathrm{0.9}$ , we lose all packets. Figure 6 shows the estimation errors and the algorithm performs well for $p_{\text{te}}\le \mathrm{0.4}$ . The estimation error ${ϵ}_X$ is low at high $p_{\text{te}}$ since most of packets are lost at high $p_{\text{te}}$ , making the data association problem easier. Notice that when $p_{\text{te}}=\mathrm{0.4}$ 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 $p_{\text{te}}$ , we can find the maximum radius $k_{\text{max}}$ of a tracking group, measured by the number of hops from a supernode, such that $p_{\text{ts}}(k_{\max \hspace{0.17em}};p_{\text{te}})\ge \mathrm{0.5}$ , sustaining the performance of the algorithm. For example, if $p_{\text{te}\mathrm{\hspace{0.17em}\hspace{0.17em}}}=\mathrm{0.1}$ , $k_{\max \hspace{0.17em}}=\mathrm{38}$ , 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 $p_{\text{de}}$ . As $p_{\text{de}}$ increases to 1, all packets are delayed. Since $w_s=\mathrm{10}$ , 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 $p_{\text{de}\mathrm{\hspace{0.17em}\hspace{0.17em}}}\le \mathrm{0.6}$ . At $p_{\text{de}\mathrm{\hspace{0.17em}\hspace{0.17em}}}=\mathrm{0.6}$ , 90% of packets are delayed and 72% of packets have delays less than $w_s$ . 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 $p_{\text{te}}=\mathrm{0.3}$ , $p_{\text{de}\mathrm{\hspace{0.17em}\hspace{0.17em}}}=\mathrm{0.3}$ , and $\eta =\mathrm{2}$ . The surveillance duration is increased to $T=\mathrm{100}$ . 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.

Figure 8

(a) A scenario used in Section 4.5 (numbers are target appearance and disappearance times, initial positions are marked by circles). (b) Accumulated observations received by supernodes with delayed observations circled. (c) Tracks estimated locally by supernodes superimposed. (d) Tracks estimated by the track-level data association step.

5. Experiments

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).

Figure 9

(a) A mica2dot sensor node (attached to an eMote). (b) The sensor network testbed used in experiments.

The sensor node platform used for our experiment was the mica2dot [35], an embedded, low-power, wireless platform running TinyOS [36] 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 [37], 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

$$\begin{array}{cc}& \frac{\mathrm{1}}{W}\sum _{i=t-W+\mathrm{1}}^t‍\sqrt{{\left(x_i-x_{i-\mathrm{1}}\right)}^2+{\left(y_i-y_{i-\mathrm{1}}\right)}^2}>\eta ,\end{array}$$

(14)

where t is the current detection time, $x_i$ and $y_i$ are the x, and y-axis magnetometer readings, and W 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 [38] for more details). We used $W=\mathrm{5}$ and $\eta =\mathrm{80}$ in our experiments.

We used the minimum-transmission-routing protocol [39] 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.

Figure 10

(a)–(c) Snapshots from the experiment of crossing tracks, proceeding left to right. We are looking at the grid of nodes from the bottom right corner. (d)–(f) Corresponding tracks found by the MCMCDA algorithm at each time step. Reporting sensor nodes are circled in red, postulated tracks are represented by dashed lines, while established tracks are represented by red solid lines. Note that the algorithm makes a bad association at $t=\mathrm{25.3}$  sec, but corrects for it by $t=\mathrm{29.7}$  sec.

Figure 11

(a) Trajectories of targets from the experiment. (b) Estimated tracks from the algorithm with observations (circles).

5.2. Outdoor Experiments

In this section, we present an outdoor demonstration described in [27] 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 $\mathrm{12}\times \mathrm{12}$ 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.

Figure 12

Hardware for the sensor nodes. (a) Triosensor node on a tripod. On top is the microphone, buzzer, solar panel, and user and reset buttons. On the sides are the windows for the passive infrared sensors. (b) A live picture from the two-target PEG experiment. The targets are circled.

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.

Figure 13

LochNess: a hierarchical real-time control system architecture using wireless sensor networks for multi-target tracking and multiagent coordination.

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 [42] 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 [27].

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)).

Figure 14

(a) Estimated tracks of targets at time 70 from the experiment with three people walking in the field. (upper left) Detection panel. Sensors are marked by small dots and detections are shown in large disks. (lower left) Fusion panel shows the fused likelihood. (right) Estimated tracks. (b) Estimated tracks of targets from the experiment with two people walking in the field before crossing. (c) Estimated tracks of targets from the experiment with two people walking in the field after crossing.

6. Conclusions

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.