Geographic Gossip: Efficient Averaging for Sensor Networks

Details Geographic Gossip: Efficient Averaging for Sensor Networks Geographic Gossip: Efficient Averaging for Sensor Networks

2007-09-25

arxiv.org/abs/0709.3921v1

Computer Science

Information Theory

To appear, IEEE Transactions on Signal Processing

Scientific paper

10.1109/TSP.2007.908946

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 in 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 $\epsilon$ using $O(\frac{n^{1.5}}{\sqrt{\log n}} \log \epsilon^{-1})$ radio transmissions, which yields a $\sqrt{\frac{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.

Affiliated with

Also associated with

No associations

Rating

Geographic Gossip: Efficient Averaging for Sensor Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Geographic Gossip: Efficient Averaging for Sensor Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geographic Gossip: Efficient Averaging for Sensor Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-626209