Lightweight sensing and communication protocols for target enumeration and aggregation

ABSTRACT

The development of lightweight sensing andcommunication protocols is a key requirement for designing resource constrained sensor networks. This paper introduces a set of efficient protocols and algorithms, DAM, EBAM, and EMLAM, for constructing and maintaining sensor aggregates that collectively monitor target activity in the environment. A sensor aggregate comprises those nodes in a network that satisfy a grouping predicate for a collaborative processing task. The parameters of the predicate depend on the task and its resource requirements. Since the foremost purpose of a sensor network is to selectively gather information about the environment, the formation of appropriate sensor aggregates is crucial for optimally allocating resources to sensing and communication tasks.This paper makes minimal assumptions about node onboard processing and communication capabilities so as to allow possible implementations on resource-constrained hardware. Factors affecting protocol performance are discussed. The paper presents simulation results showing how the protocol performance varies as key network and task parameters are varied. It also provides probabilistic analyses of network behavior consistent with the simulation results. The protocols have been experimentally validated on a sensor network testbed comprising 25 Berkeley MICA sensor motes.

REFERENCES

• 1: P. Bonnet, J. E. Gehrke, and P. Seshadri. "Querying the Physical World." IEEE Personal Comm., 7(5):10--15, October 2000.
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: D. Ganesan, D. Estrin, "DIMENSIONS: Why Do We Need A New Data Handling Architecture for Sensor Networks?" First workshop on Hot Topics in Networks, October 2002.
• 4: L.J. Guibas, "Sensing, tracking, and reasoning with relations." IEEE Signal Processing Magazine, March 2002.
• 5: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 6: IEEE Signal Processing Magazine special issue on Collaborative Signal and Information Processing for Microsensor Networks, S. Kumar, F. Zhao, D. Shepherd (eds.), vol. 19, no. 2, March 2002.
• 7: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 8: 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]
• 9: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 10: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 11: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 12: Y. Yu, R. Govindan and D. Estrin, "Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks." UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023, May 2001.
• 13: F. Zhao, C. Bailey-Kellogg, and M. Fromherz, "Physics-Based Encapsulation in Embedded Software for Distributed Sensing and Control Applications." Proceedings of the IEEE, 91(1):40--63, Jan. 2003.
• 14: F. Zhao, J. Shin, J. Reich, "Information-Driven Dynamic Sensor Collaboration for Tracking Applications." IEEE Signal Processing Magazine, March 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

General Terms:
Algorithms, Experimentation

Keywords:
applications for ad hoc networks, distributed algorithms for ad hoc networks, processing and fusion of data in sensor networks, self-configuration in ad hoc networks