TY - JOUR
T1 - Geographic gossip
T2 - Efficient averaging for sensor networks
AU - Dimakis, Alexandros D.G.
AU - Sarwate, Anand D.
AU - Wainwright, Martin J.
N1 - Funding Information:
Manuscript received October 25, 2006; revised July 12, 2008. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Zhi Tian. The work of A. D. G. Dimakis was supported by NSF Grants CCR-0219722, CCR-0330514 and DMS-0528488. The work of A. D. Sarwate was supported in part by the NSF Grant CCF-0347298. The work of M. J. Wainwright was supported by NSF grants DMS-0605165 and CCF-0545862. Some of these results were presented at the Fifth International Conference on Information Processing in Sensor Networks (IPSN)Nashville, TN, April 2006.
PY - 2008/3
Y1 - 2008/3
N2 - 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 √n, respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy ε using O((n1.5/√log n) log ε-1) radio transmissions, which yields a √n/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.
AB - 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 √n, respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy ε using O((n1.5/√log n) log ε-1) radio transmissions, which yields a √n/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.
KW - Aggregation problems
KW - Consensus problems
KW - Distributed signal processing
KW - Gossip algorithms
KW - Message-passing algorithms
KW - Random geometric graphs
KW - Sensor networks
UR - http://www.scopus.com/inward/record.url?scp=40749127156&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=40749127156&partnerID=8YFLogxK
U2 - 10.1109/TSP.2007.908946
DO - 10.1109/TSP.2007.908946
M3 - Article
AN - SCOPUS:40749127156
SN - 1053-587X
VL - 56
SP - 1205
EP - 1216
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 3
ER -