Geographic Gossip: Efficient Averaging for Sensor Networks
- 12 February 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 56 (3), 1205-1216
- https://doi.org/10.1109/tsp.2007.908946
Abstract
Gossip algorithms for distributed computation are attractive due to their simplicity, distributed nature, and robustness in noisy and uncertain environments. However, using standard gossip algorithms can lead to a significant waste of energy by repeatedly recirculating redundant information. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is related to the slow mixing times of random walks on the communication graph. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing geographic routing combined with a simple resampling method, we demonstrate substantial gains over previously proposed gossip protocols. For regular graphs such as the ring or grid, our algorithm improves standard gossip by factors of n and radicn, respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy e using O((n1.5radiclogn) logisin-1) radio transmissions, which yields a radicn/ log n factor improvement over standard gossip algorithms. We illustrate these theoretical results with experimental comparisons between our algorithm and standard methods as applied to various classes of random fields.Keywords
This publication has 21 references indexed in Scilit:
- Consensus PropagationIEEE Transactions on Information Theory, 2006
- Distributed Detection in Sensor Networks With Packet Losses and Finite Capacity LinksIEEE Transactions on Signal Processing, 2006
- Robust Decentralized Source Localization via AveragingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Decentralized compression and predistribution via randomized gossipingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Gossip algorithms: design, analysis and applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A scheme for robust distributed sensor fusion based on average consensusPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Gossip-based computation of aggregate informationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Analysis and optimization of randomized gossip algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- Reaching a ConsensusJournal of the American Statistical Association, 1974