Matching data dissemination algorithms to application requirements

ABSTRACT

A distinguishing characteristic of wireless sensor networks is the opportunity to exploit characteristics of the application at lower layers. This approach is encouraged by device resource constraints, and acceptable because devices are inexpensive and numerous enough that they can be dedicated to specific applications. Many data dissemination protocols have been proposed for multi-hop communication in sensor networks, each evaluated in some scenario. The premise of this paper is that, if protocols are designed to exploit application requirements, then no one protocol can be optimized for all applications.Instead, a family of protocols are needed, with guidance to match protocol to application. We show through field experiments with two tracking applications that choice of diffusion algorithm can affect application performance by 40--60%. These applications motivate the design of two new diffusion algorithms: push and one-phase pull diffusion. We describe these algorithms in comparison to previous algorithms, then systematically explore their performance as the number of sinks and sources, the traffic rate and node placement varies, and with and without geographic proximity in node placement and with and without geographically scoped communication. We characterize algorithm performance and highlight the effect of the choice of algorithm parameters. The end result of this work are guidelines to help application developers to match dissemination algorithms to application performance requirements.

REFERENCES

• 1: Chris Barrett , Achla Marathe , Madhav V. Marathe , Martin Drozda, Characterizing the interaction between routing and MAC protocols in ad-hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513812]
• 2: Philippe Bonnet, Johannes Gehrke, and Praveen Seshadri. Querying the physical world. IEEE Personal Communications Magazine, 7(5):10--15, October 2000.
• 3: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 4: 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]
• 5: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 6: Maurice Chu, Horst Haussecker, and Feng Zhao. Scalable information-dirven sensor querying and routing for ad hoc hetereogeneous sensor networks. International Journal on High-Performance Computing Applications, 16(3), Fall 2002.
• 7: Dan Coffin, Dan Van Hook, Ramesh Govindan, John Heidemann, and Fabio Silva. Network routing application programmer's interface (API) and walk through 8.0. Technical Report 01-741, USCISI, March 2001.
• 8: Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, Proceedings of the conference on Communications architectures, protocols and applications, p.126-135, August 31-September 02, 1994, London, United Kingdom
• 9: Stephen Deering , Deborah L. Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, The PIM architecture for wide-area multicast routing, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.153-162, April 1996 [doi>10.1109/90.490743]
• 10: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 11: J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B. Greenstein, T. Schoellhammer, T. Stathopoulos, and D. Estrin. EmStar: An environment for developing wireless embedded systems software. Technical Report CENS-TR-9, University of California, Los Angeles, Center for Embedded Networked Computing, March 2003. (Also submitted to SOSP-19).
• 12: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 13: Deepak Ganesan , Ramesh Govindan , Scott Shenker , Deborah Estrin, Highly-resilient, energy-efficient multipath routing in wireless sensor networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501452]
• 14: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 15: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: John Heidemann, Fabio Silva, Yan Yu, Deborah Estrin, and Padmaparma Haldar. Diffusion filters as a flexible architecture for event notification in wireless sensor networks. Technical Report ISI-TR-556, USCInformation Sciences Institute, April 2002.
• 17: 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]
• 18: 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]
• 19: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 20: Bhaskar Krishnamachari and John Heidemann. Application-specific modelling of information routing in sensor networks. under submission, April 2003.
• 21: S. Kumar , C. Alaettinglu , D. Estrin, Scalable object-tracking through unattended techniques (SCOUT), Proceedings of the 2000 International Conference on Network Protocols, p.253, November 14-17, 2000
• 22: Juan Liu, Jie Liu, James Reich, Patrick Cheung, and Feng Zhao. Distributed group management for track initiaition and maintenance in target localization applications. In Proceedings of the IEEE International Workshop on Information Processing in Sensor Networks, page to appear, Palo Alto, California, USA, April 2003. IEEE.
• 23: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 24: 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]
• 25: 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]
• 26: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 27: Kung Yao, Ralph E. Hudson, Chris W. Reed, Daching Chen, and Flavio Lorenzelli. Blind beamforming on a randomly distributed sensor array system. IEEE Journal of Selected Areas in Communication, 16(8):1555--1567, October 1998.
• 28: Wei Ye, John Heidemann, and Deborah Estrin. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the IEEE Infocom, pages 1567--1576, New York, NY, USA, June 2002. USCInformation Sciences Institute, IEEE.
• 29: Wei Ye, John Heidemann, and Deborah Estrin. A flexible and reliable radio communication stack on motes. Technical Report ISI-TR-565, USCInformation Sciences Institute, September 2002.
• 30: Yan Yu, Ramesh Govindan, and Deborah Estrin. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks. Technical Report TR-01-0023, University of California, Los Angeles, Computer Science Department, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
application performance, data dissemination, directed diffusion, network routing, sensor networks