Brief announcement: locality-based aggregate computation in wireless sensor networks

ABSTRACT

We present DRR-gossip, an energy-efficient and robust aggregate computation algorithm in sensor networks. We prove that the DRR-gossip algorithm requires O(n) messages and O(n^3/2/log^1/2 n) one-hop wireless transmissions to obtain aggregates on a random geometric graph. This reduces the energy consumption by at least a factor of 1/log n over the standard uniform gossip algorithm. Experiments validate the theoretical results and show that DRR-gossip needs much less transmissions than other gossip-based schemes.

REFERENCES

• 1: Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006 [doi>10.1109/TIT.2006.874516]
• 2: Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust Computation of Aggregates in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis, IEEE Transactions on Parallel and Distributed Systems, v.17 n.9, p.987-1000, September 2006 [doi>10.1109/TPDS.2006.128]
• 3: J.-Y. Chen, G. Pandurangan, and J. Hu, "http://www.cs.purdue.edu/homes/gopal/locality-sensor-agg.pdf."
• 4: Alexandros G. Dimakis , Anand D. Sarwate , Martin J. Wainwright, Geographic gossip: efficient aggregation for sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127791]
• 5: Srinivas Kashyap , Supratim Deb , K. V. M. Naidu , Rajeev Rastogi , Anand Srinivasan, Efficient gossip-based aggregate computation, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142395]
• 6: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
aggregate computation, distributed algorithm, gossip, random geometric graph, randomized algorithm, wireless sensor networks