Run-time dynamic linking for reprogramming wireless sensor networks

ABSTRACT

From experience with wireless sensor networks it has become apparent that dynamic reprogramming of the sensor nodes is a useful feature. The resource constraints in terms of energy, memory, and processing power make sensor network reprogramming a challenging task. Many different mechanisms for reprogramming sensor nodes have been developed ranging from full image replacement to virtual machines.We have implemented an in-situ run-time dynamic linker and loader that use the standard ELF object file format. We show that run-time dynamic linking is an effective method for reprogramming even resource constrained wireless sensor nodes. To evaluate our dynamic linking mechanism we have implemented an application-specific virtual machine and a Java virtual machine and compare the energy cost of the different linking and execution models. We measure the energy consumption and execution time overhead on real hardware to quantify the energy costs for dynamic linkin.Our results suggest that while in general the overhead of a virtual machine is high, a combination of native code and virtual machine code provide good energy efficiency. Dynamic run-time linking can be used to update the native code, even in heterogeneous networks.

REFERENCES

• 1: Athanassios Boulis , Chih-Chieh Han , Mani B. Srivastava, Design and implementation of a framework for efficient and programmable sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.187-200, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066121]
• 2: Chipcon AS. CC2420 Datasheet (rev. 1.3), 2005. http://www.chipcon.com/
• 3: TIS Committee. Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification Version 1.2, May 1995.
• 4: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 5: A. Dunkels, B. Grönvall, and T. Voigt. Contiki - a lightweight and flexible operating system for tiny networked sensors. In Proceedings of the First IEEE Workshop on Embedded Networked Sensors, Tampa, Florida, USA, November 2004.
• 6: Adam Dunkels , Oliver Schmidt , Thiemo Voigt , Muneeb Ali, Protothreads: simplifying event-driven programming of memory-constrained embedded systems, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182811]
• 7: National Research Council Staff, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Academy Press, Washington, DC, 2001
• 8: Guilio Ferrari , Jurgen Stuber , Andy Gombos , Dario Laverde, Programming Lego Mindstorms with Java with CD-ROM, Syngress Publishing, 2002
• 9: Chien-Liang Fok , Gruia-Catalin Roman , Chenyang Lu, Rapid Development and Flexible Deployment of Adaptive Wireless Sensor Network Applications, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.653-662, June 06-10, 2005 [doi>10.1109/ICDCS.2005.63]
• 10: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 11: J.A. Gutierrez, M. Naeve, E. Callaway, M. Bourgeois, V. Mitter, and B. Heile. IEEE 802.15.4: A developing standard for low-power low-cost wireless personal area networks. IEEE Network, 15(5):12--19, September/October 2001.
• 12: Chih-Chieh Han , Ram Kumar , Roy Shea , Eddie Kohler , Mani Srivastava, A dynamic operating system for sensor nodes, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067188]
• 13: 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
• 14: 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]
• 15: J. Jeong and D. Culler. Incremental network programming for wireless sensors. In Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks IEEE SECON (2004), October 2004.
• 16: J. Jeong, S. Kim, and A. Broad. Network reprogramming. TinyOS documentation, 2003. Visited 2006-04-06. http://www.tinyos.net/tinyos-1.x/doc/NetworkReprogramming.pdf
• 17: J. Koshy and R. Pandey. Remote incremental linking for energy-efficient reprogramming of sensor networks. In Proceedings of the second European Workshop on Wireless Sensor Networks, 2005.
• 18: Joel Koshy , Raju Pandey, VMSTAR: synthesizing scalable runtime environments for sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098945]
• 19: 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
• 20: P. Levis, D. Gay, and D Culler. Active sensor networks. In Proc. USENIX/ACM NSDI'05, Boston, MA, USA, May 2005.
• 21: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In Proc. NSDI'04, March 2004.
• 22: J. Lilius and I. Paltor. Deeply embedded python, a virtual machine for embedded systems. Web page. 2006-04-06. http://www.tucs.fi/magazin/output.php?ID=2000.N2.LilDeEmPy
• 23: Hongzhou Liu , Tom Roeder , Kevin Walsh , Rimon Barr , Emin Gün Sirer, Design and implementation of a single system image operating system for ad hoc networks, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067187]
• 24: 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]
• 25: Geoff Mainland , Laura Kang , Sebastien Lahaie , David C. Parkes , Matt Welsh, Using virtual markets to program global behavior in sensor networks, Proceedings of the 11th workshop on ACM SIGOPS European workshop: beyond the PC, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133587]
• 26: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 27: P. José Marrón, M. Gauger, A. Lachenmann, D. Minder, O. Saukh, and K. Rothermel. Flexcup: A flexible and efficient code update mechanism for sensor networks. In European Workshop on Wireless Sensor Networks, 2006.
• 28: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 29: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 30: Nithya Ramanathan , Eddie Kohler , Deborah Estrin, Towards a debugging system for sensor networks, International Journal of Network Management, v.15 n.4, p.223-234, July 2005 [doi>10.1002/nem.570]
• 31: Niels Reijers , Koen Langendoen, Efficient code distribution in wireless sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941359]
• 32: RF Monolithics. 868.35 MHz Hybrid Transceiver TR1001, 1999. http://www.rfm.com
• 33: Jochen Schiller , Achim Liers , Hartmut Ritter , Rolf Winter , Thiemo Voigt, ScatterWeb - Low Power Sensor Nodes and Energy Aware Routing, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 9, p.286.3, January 03-06, 2005 [doi>10.1109/HICSS.2005.529]
• 34: T. Stathopoulos, J. Heidemann, and D. Estrin. A remote code update mechanism for wireless sensor networks. Technical Report CENS-TR-30, University of California, Los Angeles, Center for Embedded Networked Computing, November 2003.
• 35: M. Welsh and G. Mainland. Programming sensor networks using abstract regions. In Proc. USENIX/ACM NSDI'04, San Francisco, CA,, March 2004.
• 36: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
dynamic linking, embedded systems, operating systems, virtual machines, wireless sensor networks