Aggregation methods for large-scale sensor networks

ABSTRACT

The ability to efficiently aggregate information—for example compute the average temperature—in large networks is crucial for the successful employment of sensor networks. This article addresses the problem of designing truly scalable protocols for computing aggregates in the presence of faults, protocols that can enable million node sensor networks to work efficiently. More precisely, we make four distinct contributions. First, we introduce a simple fault model and analyze the behavior of two existing protocols under the fault model: tree aggregation and gossip aggregation. Second, since the behavior of the two protocols depends on the size of the network and probability of failure, we introduce a hybrid approach that can leverage the strengths of the two protocols and minimize the weaknesses; the new protocol is analyzed under the same fault model. Third, we propose methodology for determining the optimal mix between the two basic protocols; the methodology consists in formulating an optimization problem, using models of the protocol behavior, and solving it. Fourth, we perform extensive experiments to evaluate the performance of the hybrid protocol and show that it usually performs better, sometimes orders of magnitude better, than both the tree and gossip aggregation.

REFERENCES

• 1: Amis, A. D., Prakash, R., Huynh, D., and Vuong, T. 2000. Max-min d-cluster formation in wireless ad hoc networks. In Proceedings of IEEE INFOCOM (Tel Aviv, Israel). 32--41.
• 2: Bandyopadhyay, S. and Coyle, E. 2003. An energy efficient hierarchical clustering algorithm for wireless sensor networks. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom 2003). Vol. 3. Springer-Verlag, San Franciso, CA, 1713--1723.
• 3: Bawa, M., Garcia-Molina, H., Gionis, A., and Motwani, R. 2003. Estimating aggregates on a peer-to-peer network. Tech. rep. Computer Science Department, Stanford University, Stanford, CA.
• 4: Chen, J.-Y., Pandurangan, G., and Xu, D. 2005. Robust aggregates computation in wireless sensor networks. In Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN). IEEE Computer Society Press, Los Alamitos, CA.
• 5: Ding, M., Cheng, X., and Xue, G. 2003. Aggregation tree construction in sensor networks. In Proceedings of the Vehicular Technology Conference (Orlando, FL).
• 6: Fiedler, M. 1973. Algebraic connectivity of graphs. Czechoslovak Math. J. 23, 98, 298--305.
• 7: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 8: 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]
• 9: Lewis Girod , Jeremy Elson , Alberto Cerpa , Thanos Stathopoulos , Nithya Ramanathan , Deborah Estrin, EmStar: a software environment for developing and deploying wireless sensor networks, Proceedings of the annual conference on USENIX Annual Technical Conference, p.24-24, June 27-July 02, 2004, Boston, MA
• 10: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, Scalable Fault-Tolerant Aggregation in Large Process Groups, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.433-442, July 01-04, 2001
• 11: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, A Probabilistically Correct Leader Election Protocol for Large Groups, Proceedings of the 14th International Conference on Distributed Computing, p.89-103, October 04-06, 2000
• 12: Hu, Y. 2005. A guided simulation methodology for dynamic probabilistic risk assessment of complex systems. Ph.D. dissertation. Department of Mechanical Engineering, Univeristy of Maryland, College Park, College Park, MD.
• 13: Jia, L., Noubir, G., Rajaraman, R., and Sundaram, R. 2006. Group-independent spanning tree for data aggregation in dense sensor networks. In Proceedings of the International Conference on Distributed Computing in Sensor Systems (DCOSS). San Francisco, CA.
• 14: 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]
• 15: 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
• 16: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 17: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 18: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 19: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 20: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 21: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 22: Enric Pastor , Marco A. Pena, Combining Simulation and Guided Traversal for the Verification of Concurrent Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.11158, March 03-07, 2003
• 23: Polley, J., Blazakis, D., McGee, J., Rusk, D., and Baras, J. S. 2004. Atemu: A fine-grained sensor network simulator. In SECON'04, The First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (Santa Clara, CA).
• 24: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 25: Shao, J. 2003. Mathematical Statistics, 2 ed. Springer Texts in Statistics, Springer, Berlin, Germany.
• 26: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 27: Sundar Subramanian , Sanjay Shakkottai, Geographic routing with limited information in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 28: Geoffrey Werner-Allen , Patrick Swieskowski , Matt Welsh, MoteLab: a wireless sensor network testbed, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 29: Jiangchuan Liu , Ming Zhou, Tree-assisted gossiping for overlay video distribution, Multimedia Tools and Applications, v.29 n.3, p.211-232, June 2006 [doi>10.1007/s11042-006-0013-7]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
In-network processing and aggregation, fault tolerance, modeling faults, sensor fusion and distributed inference