Neighborhood Gossip: Concurrent Averaging through Local Interference

• Presented at: IEEE International Conference on Acoustics, Speech and Signal Processing, Taipei, TAIWAN, Apr 19-24, 2009
• Published in: 2009 Ieee International Conference On Acoustics, Speech, And Signal Processing, Vols 1- 8, Proceedings (ISBN: 978-1-4244-2353-8), p. 3657-3660
• Series: International Conference on Acoustics Speech and Signal Processing ICASSP
• Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa, 2009

In this paper, we study a gossip algorithm for distributed averaging over a wireless sensor network. The usual assumption is that, through properly chosen codes, the physical layer is reduced to a set of reliable bit pipes for the distributed averaging algorithm. However, with a new channel coding technique, computation coding, we can exploit the interference property of the wireless medium for efficient averaging. This then provides a new abstraction for the physical layer: reliable linear equations instead of reliable bit pipes. The "neighborhood gossip" algorithm operates modularly on top of this abstraction. We will show that for certain regimes, such an approach can lead to energy savings that are exponential in the network size and time savings that are polynomial.

Keywords: Distributed algorithms ; linear codes ; distributed estimation ; Algorithms

Reference

• EPFL-CONF-169550
• View record in Web of Science

Record created on 2011-10-17, modified on 2017-05-12