Distributed Tracking using Selective Gossip

Project overview and publications:

In this project, we study distributed target tracking problem where the nodes of a sensor network track a moving object collaboratively. We propose an efficient decentralized particle filter implementation. Results of numerical experiments demonstrate that our method requires lower communication overhead while achieving similar accuracy as compared to the state-of-the-art distributed particle fi ltering approaches. 

Üstebay, D.M. J. Coates, and M. G. Rabbat"Distributed auxiliary particle filters using selective gossip", IEEE Int. Conf. on Acoustics, Speech, and Signal Proc. (ICASSP), Prague, Czech Republic, pp. 3296-3299, May 2011.

Üstebay, D.R. Castro, and M. G. Rabbat"Efficient decentralized approximation via selective gossip", IEEE Journal on Selected Topics in Signal Processing, vol. 5, no. 4, pp. 805-816, Aug. 2011. 

Project description:

Target tracking refers to sequentially estimating the state of a moving object or person. With prior information on the dynamics of the target as well as the noise characteristics of the measurements, we can obtain good estimators of the target state. For nonlinear and non-Gaussian problems, the state-of-the-art method of estimation is particle filtering.



In a wireless sensor network setting, sensor nodes take measurements related to the target. The processing of these measurements can be done at a fusion center or by the nodes of the network collaboratively. The centralized method requires formation and maintanence of routes and introduces a single point of failure to the network. Thus we are interested in decentralized methods. The main challenge for distributed processing in wireless sensor networks is preserving network resources such as lifetime and bandwidth. The tracking method should be efficient in using these resources for communication between nodes in the network. In our setting, nodes maintain a shared particle filter to sequentially estimate the state of the target. The measurements taken by sensor nodes are fused by reaching a consensus on the likelihood associated with each particle. To save on communication, we propose using selective gossip which is a distributed approximation algorithm.


Selective gossip is based on gossip algorithms which are decentralized methods studied extensively for scalar network data. In essence, gossip algorithms utilize iterative information exchange between pairs of nodes and asymptotically all nodes reach consensus on a network aggregate. Selective gossip applies the idea of iterative information exchange to vectors of data, i.e. likelihoods associated with particles of the filter. Instead of communicating on the entire vector and wasting network resources, our method adaptively identifies likelihoods with the largest magnitude and focuses communication resources on computing these important likelihoods.


We demonstrate the performance of our method through numerical experiments. In the simulation setup we have 50 sensor nodes distributed uniformly at random on unit square. The communication topology is a random geometric graph. The sensor nodes track a single target for a duration of 50 seconds during which the target makes a full clockwise turn. The sensors are capable of measuring one of four  different features: bearing, received signal strength, range and radial velocity. To compare the performance of our proposed scheme, we implemented a centralized particle filter as well as the distributed Gaussian approximation particle filter scheme of Oreshkin and Coates (2010).


Numerical simulations indicate that the algorithm provides advantages compared to other state-of-the-art approaches; either it provides a substantial improvement in accuracy at the expense of a small increase in communication overhead or it provides comparable accuracy with much less communication overhead.