Download

IEEE Explore Version (official) [Link]
California Digital Library postprint (free) [Link]
Adobe Portable Document Format (local) [PDF]

Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 $\sqrt{n}$, respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy e using $O((n^{1.5} \sqrt{\log n}) \log \epsilon^{-1}$ radio transmissions, which yields a $\sqrt{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.

Notes

Expanded version of IPSN 2006 paper with a similar title and same auhors.

More recent than any versions on ArXiV.

Links

Alex Dimakis's homepage

Anand Sarwate's homepage

Martin Wainwright's homepage

Reference

A.D.G. Dimakis, A.D. Sarwate, and M. Wainwright, Geographic Gossip : Efficient Averaging for Sensor Networks, IEEE Transactions on Signal Processing, vol. 56, no. 3, pp. 1205--1216, March 2008.

BibTeX

@ARTICLE(DimakisSW:08gossip,
   AUTHOR = "A.D.G. Dimakis and A.D. Sarwate and M. Wainwright",
   TITLE = "Geographic Gossip : Efficient Averaging for Sensor Networks",
   JOURNAL = "IEEE Transactions on Signal Processing",
   VOLUME = "56",
   NUMBER = "3",
   PAGES = "1205--1216",
   MONTH = "March",
   YEAR = "2008",
   )