Geographic gossip: Efficient aggregation for sensor networks

Alexandros G. Dimakis, Anand D. Sarwate, Martin J. Wainwright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

122 Scopus citations

Abstract

Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy 1/na using O(n 1.5√log n) radio transmissions, which reduces the energy consumption by a √n/log n factor over standard gossip algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the Fifth International Conference on Information Processing in Sensor Networks, IPSN '06
Pages69-76
Number of pages8
DOIs
StatePublished - 2006
Externally publishedYes
EventFifth International Conference on Information Processing in Sensor Networks, IPSN '06 - Nashville, TN, United States
Duration: Apr 19 2006Apr 21 2006

Publication series

NameProceedings of the Fifth International Conference on Information Processing in Sensor Networks, IPSN '06
Volume2006

Other

OtherFifth International Conference on Information Processing in Sensor Networks, IPSN '06
CountryUnited States
CityNashville, TN
Period4/19/064/21/06

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Distributed aggregation
  • Distributed consensus
  • Gossip algorithms
  • Random geometric graphs
  • Sensor networks

Fingerprint Dive into the research topics of 'Geographic gossip: Efficient aggregation for sensor networks'. Together they form a unique fingerprint.

Cite this