Ad-hoc multicast routing on resource-limited sensor nodes

ABSTRACT

Many emerging sensor network applications involve mobile nodes with communication patterns requiring any-to-any routing topologies. We should be able to build upon the MANET work to implement these systems. However, translating these protocols into real implementations on resource-constrained sensor nodes raises a number of challenges. In this paper, we present the lessons learned from implementing one such protocol, Adaptive Demand-driven Multicast Routing (ADMR), on CC2420-based motes using the TinyOS operating system. ADMR was chosen because it supports multicast communication, a critical requirement for many pervasive and mobile applications. To our knowledge, ours is the first non-simulated implementation of ADMR. Through extensive measurement on Motelab, we present the performance of the implementation, TinyADMR, under a wide range of conditions. We highlight the real-world impact of path selection metrics, radio link asymmetry, protocol overhead, and limited routing table size.

REFERENCES

• 1: CC2420 Product Information. http://www.chipcon.com/index.cfm?katid=2&subkat_id=12&dok_id=115.
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 3: A. Cerpa, N. Busek, and D. Estrin. SCALE: a tool for Simple Connectivity Assessment in Lossy Environments. Technical report, September 2003.
• 4: 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]
• 5: Deepak Ganesan , Deborah Estrin , John Heidemann, Dimensions: why do we need a new data handling architecture for sensor networks?, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.143-148, January 2003 [doi>10.1145/774763.774786]
• 6: 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, Feburary 2002.
• 7: 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
• 8: 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]
• 9: Jorjeta G. Jetcheva , David B. Johnson, Adaptive demand-driven multicast routing in multi-hop wireless ad hoc 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/501422.501423]
• 10: D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 11: W. Kaiser, G. Pottie, M. Srivastava, G. Sukhatme, J. Villasenor, and D.Estrin. Networked Infomechanical Systems (NIMS) for Ambient Intelligence. Invited contribution to Ambient Intelligence, Springer-Verlag, 2004.
• 12: Aman Kansal , Arun A. Somasundara , David D. Jea , Mani B. Srivastava , Deborah Estrin, Intelligent fluid infrastructure for embedded networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990080]
• 13: S.-J. Lee, M. Gerla, and C.-C. Chiang. On-demand multicast routing protocol. In IEEE Wireless Communications and Networking Conference, WCNC'99, pages 1298--1304, September 1999.
• 14: Ting Liu , Christopher M. Sadler , Pei Zhang , Margaret Martonosi, Implementing software on resource-constrained mobile sensors: experiences with Impala and ZebraNet, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990095]
• 15: Konrad Lorincz , David J. Malan , Thaddeus R. F. Fulford-Jones , Alan Nawoj , Antony Clavel , Victor Shnayder , Geoffrey Mainland , Matt Welsh , Steve Moulton, Sensor Networks for Emergency Response: Challenges and Opportunities, IEEE Pervasive Computing, v.3 n.4, p.16-23, October 2004 [doi>10.1109/MPRV.2004.18]
• 16: 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]
• 17: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 18: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 19: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 20: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 21: Yogesh Sankarasubramaniam , Özgür B. Akan , Ian F. Akyildiz, ESRT: event-to-sink reliable transport in wireless sensor networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778437]
• 22: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 23: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 24: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 25: Robert Szewczyk , Eric Osterweil , Joseph Polastre , Michael Hamilton , Alan Mainwaring , Deborah Estrin, Habitat monitoring with sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990704]
• 26: 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]
• 27: 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]
• 28: P. Wright et al. Fire information & rescue equipment. http://fire.me.berkeley.edu/indexmain.php?main=home.php&title=FIRE\%20Project:\%20Overview.
• 29: Jasmeet Chhabra , Brent Elliott, Real-World Experiences with an Interactive Ad Hoc Sensor Network, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.143, August 18-21, 2002
• 30: Geoffrey Werner-Allen , Patrick Swieskowski , Matt Welsh, MoteLab: a wireless sensor network testbed, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 31: Bor-rong Chen, Kiran-Kumar Muniswamy-Reddy, and Matt Welsh. Lessons Learned from Implementing Ad-Hoc Multicast Routing in Sensor Networks. Harvard University Technical Report TR-22-05, November 2005.

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
multicast, routing, sensor networks