Geographic gossip: efficient aggregation for sensor networks

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/n^ausing O(n^1.5√log n) radio transmissions, which reduces the energy consumption by a √nover log n factor over standard gossip algorithms.

REFERENCES

• 1: M. Alanyali, V. Saligrama, and O. Savas, A random-walk model for distributed computation in energy-limited networks, In Proc. of 1st Workshop on Information Theory and its Applications,San Diego, 2006.
• 2: Boulat A. Bash , John W. Byers , Jeffrey Considine, Approximately uniform random sampling in sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052206]
• 3: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Analysis and optimization of randomized gossip algorithms. In Proceedings of the 43rd Conference on Decision and Control (CDC 2004), 2004.
• 4: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms : Design, analysis and applications. In Proceedings of the 24th Conference of the IEEE Communications Society (INFOCOM 2005), 2005.
• 5: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 6: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 7: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-off in wireless networks. In Proceedings of the 24th Conference of the IEEE Communications Society (INFOCOM 2004), 2004.
• 8: P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, March 2000.
• 9: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 10: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 11: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 12: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 13: Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
• 14: C. Moallemi and B. V. Roy. Consensus propagation. Technical report, Stanford University, June 2005.
• 15: D. Mosk-Aoyama and D. Shah. Information dissemination via gossip: Applications to averaging and coding. http://arxiv.org/cs.NI/0504029, April 2005.
• 16: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 17: M. Penrose. Random Geometric Graphs. Oxford studies in probability. Oxford University Press, Oxford, 2003.
• 18: M. Rabbat, R. Nowak, and J. Bucklew, Robust Decentralized Source Localization via Averaging In IEEE International Conference on Acoustics, Speech and Signal processing (ICASSP), Philadelphia, PA, March 2005.
• 19: Demetri P. Spanos , Reza Olfati-Saber , Richard M. Murray, Approximate distributed Kalman filtering in sensor networks with quantifiable performance, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 20: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 21: Lin Xiao , Stephen Boyd , Sanjay Lall, A scheme for robust distributed sensor fusion based on average consensus, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms

Keywords:
distributed aggregation, distributed consensus, gossip algorithms, random geometric graphs, sensor networks