The emergence of a networking primitive in wireless sensor networks

ABSTRACT

The wireless sensor network community approached networking abstractions as an open question, allowing answers to emerge with time and experience. The Trickle algorithm has become a basic mechanism used in numerous protocols and systems. Trickle brings nodes to eventual consistency quickly and efficiently while remaining remarkably robust to variations in network density, topology, and dynamics. Instead of flooding a network with packets, Trickle uses a "polite gossip" policy to control send rates so each node hears just enough packets to stay consistent. This simple mechanism enables Trickle to scale to 1000-fold changes in network density, reach consistency in seconds, and require only a few bytes of state yet impose a maintenance cost of a few sends an hour. Originally designed for disseminating new code, experience has shown Trickle to have much broader applicability, including route maintenance and neighbor discovery. This paper provides an overview of the research challenges wireless sensor networks face, describes the Trickle algorithm, and outlines several ways it is used today.

REFERENCES

• 1: Arch Rock Corporation. An IPv6 Network Stack for Wireless Sensor Networks. http://www.archrock.com.
• 2: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 3: Crossbow, Inc. Mote in Network Programming User Reference. http://webs.cs.berkeley.edu/tos/tinyos-1.x/doc/Xnp.pdf.
• 4: 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]
• 5: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 6: Fonseca, R., Gnawali, O., Jamieson, K., and Levis, P. Four bit wireless link estimation. Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), 2007.
• 7: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 8: 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
• 9: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 10: 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]
• 11: Philip Levis , David Gay , David Culler, Active sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.343-356, May 02-04, 2005
• 12: 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]
• 13: Philip Levis , Neil Patel , David Culler , Scott Shenker, Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.2-2, March 29-31, 2004, San Francisco, California
• 14: Kaisen Lin , Philip Levis, Data Discovery and Dissemination with DIP, Proceedings of the 7th international conference on Information processing in sensor networks, p.433-444, April 22-24, 2008 [doi>10.1109/IPSN.2008.17]
• 15: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 16: Mao, Y., Wang, F., Qiu, L., Lam, S., and Smith, J. S4: small state and small stretch routing protocol for large wireless sensor networks. Proceedings of the Fourth USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2007.
• 17: 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]
• 18: Jeongyeup Paek , Ramesh Govindan, RCRT: rate-controlled reliable transport for wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322293]
• 19: Sumit Rangwala , Ramakrishna Gummadi , Ramesh Govindan , Konstantinos Psounis, Interference-aware fair rate control in wireless sensor networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 20: Sun Microsystems Laboratories. Project Sun SPOT: Small Programmable Object Technology. http://www.sunspotworld.com/.
• 21: TinyOS Network Protocol Working Group. TEP 123: The Collection Tree Protocol. http://www.tinyos.net//tinyos-2.x/doc/txt/tep123.txt, 2007.
• 22: Tolle, G. and Culler, D. Design of an application-cooperative management system for wireless sensor networks. Proceedings of the Second European Workshop of Wireless Sensor Netw orks (EWSN), 2005.
• 23: Limin Wang, MNP: multihop network reprogramming service for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031538]
• 24: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 25: Jing Yang , Mary Lou Soffa , Leo Selavo , Kamin Whitehouse, Clairvoyant: a comprehensive source-level debugger for wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322282]

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
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Performance