The dynamic behavior of a data dissemination protocol for network programming at scale

ABSTRACT

To support network programming, we present Deluge, a reliable data dissemination protocol for propagating large data objects from one or more source nodes to many other nodes over a multihop, wireless sensor network. Deluge builds from prior work in density-aware, epidemic maintenance protocols. Using both a real-world deployment and simulation, we show that Deluge can reliably disseminate data to all nodes and characterize its overall performance. On Mica2-dot nodes, Deluge can push nearly 90 bytes/second, one-ninth the maximum transmission rate of the radio supported under TinyOS. Control messages are limited to 18% of all transmissions. At scale, the protocol exposes interesting propagation dynamics only hinted at by previous dissemination work. A simple model is also derived which describes the limits of data propagation in wireless networks. Finally, we argue that the rates obtained for dissemination are inherently lower than that for single path propagation. It appears very hard to significantly improve upon the rate obtained by Deluge and we identify establishing a tight lower bound as an open problem.

REFERENCES

• 1: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 2: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical Report UCLA/CSD-TR 02-0013, UCLA, 2002.
• 3: J. Jeong, S. Kim, and A. Broad. Network Reprogramming. University of California at Berkeley, Berkeley, CA, USA, August 2003.
• 4: Sneha Kumar Kasera , Gísli Hjálmtýsson , Donald F. Towsley , James F. Kurose, Scalable reliable multicast using multiple multicast channels, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.294-310, June 2000 [doi>10.1109/90.851976]
• 5: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417]
• 6: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 7: 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]
• 8: P. Levis, N. Patel, S. Shenker, and D. Culler. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. Technical report, University of California at Berkeley, 2004.
• 9: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 10: F. Stann and J. Heidemann. RMST: Reliable data transport in sensor networks. In Proceedings of the First International Workshop on Sensor Net Protocols and Applications, pages 102--112, Anchorage, Alaska, USA, April 2003. IEEE.
• 11: T. Stathopoulos, J. Heidemann, and D. Estrin. A remote code update mechanism for wireless sensor networks. Technical report, UCLA, Los Angeles, CA, USA, 2003.
• 12: R. Szewczyk, J. Polastre, A. Mainwaring, and D. Culler. Lessons from a sensor network expedition. In Proceedings of the First European Workshop on Sensor Networks (EWSN), Berlin, Germany, Jan. 2004.
• 13: University of California, Berkeley. Smote testbed. http://smote.cs.berkeley.edu/.
• 14: University of California, Berkeley. Mica2-dot schematics.
• 15: http://webs.cs.berkeley.edu/tos/hardware/design/ORCAD_FILES/MICA2/6310-%0306-01ACLEAN.pdf, March 2003.
• 16: University of California, Berkeley. Tinyos. http://www.tinyos.net/, 2004.
• 17: Chieh-Yih Wan , Andrew T. Campbell , Lakshman Krishnamurthy, PSFQ: a reliable transport protocol for wireless 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.570740]

INDEX TERMS

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

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

General Terms:
Design, Experimentation, Measurement, Performance, Reliability

Keywords:
dissemination protocols, network programming, wireless networks, wireless sensor networks