VMSTAR: synthesizing scalable runtime environments for sensor networks

ABSTRACT

Sensor networks are being deployed at massive scales, containing a range of platforms. Programming paradigms for sensor networks should meet the attendant challenges of scale and heterogeneity. Researchers have considered virtual machines as a means to address these challenges. However, in order to satisfy the resource limitations of sensor nodes, they export only a minimal set of services to the application programmer. This makes applications of even moderate complexity difficult to implement. We present VMSTAR --- a framework for building resource-efficient virtual machines that scale and export comprehensive service suites on a per-application basis. We advocate the use of fine-grained software synthesis to build resource-efficient system software, and facilitate both application changes and system software upgrades at runtime through an efficient incremental update scheme. We have used our framework to build virtual machines on the Mica platform and describe how virtual machines are effective in meeting the difficult demands of heterogeneity and reprogrammability.

REFERENCES

• 1: H. Abrach , S. Bhatti , J. Carlson , H. Dai , J. Rose , A. Sheth , B. Shucker , J. Deng , R. Han, MANTIS: system support for multimodAl NeTworks of in-situ sensors, 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.941358]
• 2: Atmel Corporation. ATMega128 Datasheet.
• 3: John Aycock, A brief history of just-in-time, ACM Computing Surveys (CSUR), v.35 n.2, p.97-113, June 2003 [doi>10.1145/857076.857077]
• 4: G. Bracha, N. Cohen, C. Kemper, M. Odersky, D. Stoutamire, K. Thorup, and P. Wadler. Adding generics to the Java programming language. Java Community Process JSR-000014, September 2004.
• 5: Crossbow Technology Inc. Mica Motes. http://www.xbow.com.
• 6: M. Anton Ertl , David Gregg, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.403-412, August 28-31, 2001
• 7: 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
• 8: 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]
• 9: Jason Hill , Mike Horton , Ralph Kling , Lakshman Krishnamurthy, The platforms enabling wireless sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990705]
• 10: 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
• 11: 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]
• 12: J. Jong and D. Culler. Incremental Network Programming for Wireless Sensors. In Proceedings of the International Conference on Sensor and Ad Hoc Communications and Networks, Santa Clara, California, October 2004.
• 13: J. Wu and R. Pandey. BOTS: A Constraint-Based Component System for Synthesizing Scalable Software Systems. Technical Report CSE-2005-18, University of California, Davis, August 2005.
• 14: J. Koshy and R. Pandey. Remote Incremental Linking for Energy-Efficient Reprogramming of Sensor Networks. In Proceedings of the European Workshop on Sensor Networks, pages 354--365, Istanbul, Turkey, January 2005.
• 15: 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
• 16: P. Levis and D. Culler. Active Sensor Networks. In Proceedings of the Symposium on Networked Systems Design and Implementation, Boston, MA, May 2005.
• 17: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 18: J. Mulder, S. Dulman, L. van Hoesel, and P. Havinga. PEEROS --- System Software for Wireless Sensor Networks. Preprint, August 2003.
• 19: R. Pandey, J. Kottalam, Y. Ramin, I. Wirjawan, and J. Koshy. OSSTAR: A Scalable Component-Based Operating System for Sensor Networks (in preparation), 2005.
• 20: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 21: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 22: 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]
• 23: Frank Tip , Peter F. Sweeney , Chris Laffra , Aldo Eisma , David Streeter, Practical extraction techniques for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.625-666, November 2002 [doi>10.1145/586088.586090]
• 24: Ben L. Titzer , Jens Palsberg, Nonintrusive precision instrumentation of microcontroller software, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 25: Ankush Varma , Shuvra S. Bhattacharyya, Java-through-C Compilation: An Enabling Technology for Java in Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30161, February 16-20, 2004
• 26: Mark Weiser, Some computer science issues in ubiquitous computing, Communications of the ACM, v.36 n.7, p.75-84, July 1993 [doi>10.1145/159544.159617]
• 27: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

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

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

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

Keywords:
network reprogramming, operating systems, programming languages, software synthesis, virtual machines, wireless sensor networks