Building efficient wireless sensor networks with low-level naming

ABSTRACT

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are external to the network topology and relevant to the application. When combined with dense deployment of nodes, this kind of named data enables in-network processing for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.186-201, December 12-15, 1999, Charleston, South Carolina, United States
• 2: Elan Amir , Steven McCanne , Randy Katz, An active service framework and its application to real-time multimedia transcoding, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.178-189, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 3: F. Bennett, D. Clarke, J. B. Evans, A. Hopper, A. Jones, and D. Leask. Piconet: Embedded mobile networking. IEEEPersonal Communications Magazine, 4(5):8-15, Oct. 1997.
• 4: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 5: Philippe Bonnet , Johannes Gehrke , Tobias Mayr , Praveen Seshadri, Query Processing in a Device Database System, Cornell University, Ithaca, NY, 1999
• 6: Mic Bowman , Saumya K. Debray , Larry L. Peterson, Reasoning about naming systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.795-825, Nov. 1993 [doi>10.1145/161468.161471]
• 7: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 8: Richard R. Brooks , S. Sitharama Iyengar, Robust Distributed Computing and Sensing Algorithm, Computer, v.29 n.6, p.53-60, June 1996 [doi>10.1109/2.507632]
• 9: Nicholas Carriero , David Gelernter, The S/Net's Linda kernel (extended abstract), Proceedings of the tenth ACM symposium on Operating systems principles, p.160, December 1985, Orcas Island, Washington, United States
• 10: CCITT. The directory: Overview of concepts, models and service. Recommendation X.500, CCITt, 1988.
• 11: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 12: Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
• 13: D. Coffin, D. V. Hook, R. Govindan, J. Heidemarm, and F. Silva. Network Routing Application Programmer's Interface (API) and Walk Through. Mrr/LL and USC/ISI, Dec. 2000.
• 14: D.A. Coffin, D. J. V. Hook, S. M. McGarry, and S. R. Kolek. Declarative ad-hoe sensor networking. In Proceedings of the SPIE Integrated Command Environments Conference, San Diego, California, USA, July 2000. SPIE. (part of SPIE International Symposium on Optical Science and Technology).
• 15: Steven E. Czerwinski , Ben Y. Zhao , Todd D. Hodes , Anthony D. Joseph , Randy H. Katz, An architecture for a secure service discovery service, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.24-35, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313462]
• 16: Random, Ephemeral Transaction Identifiers in Dynamic Sensor Networks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.459, April 16-19, 2001
• 17: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 18: V. Fuller, T. Li, J. Yu, and K. Varadhan. Classless inter-domain routing (CIDR): an address assignment and aggregation strategy. RFC 1519, Internet Request For Comments, Sept. 1993.
• 19: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 20: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 21: 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
• 22: T. Imielinski and S. Goel. DataSpace: QueryIng and Monitoring Deeply Networked Collections in Physical Space. 1EEE Personal Communications. Special Issue on Smart Spaces and Environments, 7(5):4--9, October 2000..,
• 23: 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]
• 24: V. Jacobson. Compressing TCP/1P headers for low-speed serial finks. RFC 1144, Internet Request For Comments, Feb. 1990.
• 25: S. Michel, K. Nguyen, A. Rosenstein, L. Zhang, S. Floyd, and V. Jaeobson. Adaptive web caching: Towards a new global caching architecture. In Proceedings of the 3rd International Worm Wide Web Conference, Manchester, England, June 1998.
• 26: P. Moekapetris. Domain names--concepts and facilities. RFC 1034, Internet Request For Comments, Nov. 1987.
• 27: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 28: L. L. Peterson, A yellow-pages service for a local-area network, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.235-242, August 11-13, 1987, Stowe, Vermont, United States
• 29: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 30: Y. Rekhter, P. Lothberg, R. I-linden, S. Deoring, and J. Postel. An IPv6 provider-based unieast address format. RFC 2073, Internet Request For Comments, Jan. 1997.
• 31: Puneet Sharma , Deborah Estrin , Sally Floyd , Van Jacobson, Scalable Timers for Soft State Protocols, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.222, April 09-11, 1997
• 32: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 33: K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie. A self-organizing sensor network. In Proceedings of the 37th Allerton Conference on Communication, Control, and Computing, Monticello, ill., USA, Sept. 1999.
• 34: D.L. Tennenhonse, J. M. Smith, W. D. Sincoskie, D. J. Wetherall, and G. J. Minden. A survey of active network research. IEEE Communications Magazine, 35(1):80-86, Jan. 1997.
• 35: Jim Waldo, The Jini architecture for network-centric computing, Communications of the ACM, v.42 n.7, p.76-82, July 1999 [doi>10.1145/306549.306582]
• 36: Lan Wang , Andreas Terzis , Lixia Zhang, A New Proposal for RSVP Refreshes, Proceedings of the Seventh Annual International Conference on Network Protocols, p.163, October 31-November 03, 1999
• 37: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 38: W. Yeong, T. Howes, and S. Kille. Lightweight directory access protocol. RFC 1777, Internet Request For Comments, Mar. 1995.
• 39: Y. Yu, D. Estrin, and R. Govindan. Geographical and energy-aware routing for wireless sensor networks: A recursive data dissemination protocol. Work in Progress, Mar. 2001.
• 40: Y. Zhao, R. Govindan, and D. Estrin. Residual energy scans for monitoring wireless sensor networks. Technical Report 01-745, May 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Design, Performance