Maté: a tiny virtual machine for sensor networks

Abstract

Composed of tens of thousands of tiny devices with very limited resources ("motes"), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.

References

1. Smart buildings admit their faults. Lab Notes: Research from the College of Engineering, UC Berkeley. http://cos.berkeley.edu/labnotes/1101.smartbuildings.html, 2001.
2. Small Times: Big News in Small Tech. http://www.smalltimes.com
3. Edouard Bugnion, Scott Devine, and Mendel Rosenblum. Disco: Running Commodity Operating Systems on Scalable Multiprocessors. In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, 1997.
4. David Culler, Anurag Sah, Klaus Schauser, Thorsten von Eicken and John Wawrzynek. Fine-grain Parallelism with Minimal Hardware Support: A Compiler-Controlled Threaded Abstract Machine. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 1991.
5. Lloyd I. Dickman. Small Virtual Machines: A Survey. In Proceedings of the Workshop on Virtual Computer Systems, 1973.
6. Wolfgang Emmerich, Cecilia Mascolo, and Anthony Finkelstein. Implementing Incremental Code Migration with XML. In Proceedings of the 22nd International Conference on Software Engineering, 2000.
7. Deborah Estrin, Ramesh Govindan, John Heidemann, and Satish Kumar. Next Century Challenges: Scalable Coordination in Sensor Networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, 1999.
8. Virginie Galtier, Kevin L. Mills, Yannick Carlinet, Stefan Leigh, and Andrew Rukhin. Expressing Meaningful Processing Requirements Among Heterogeneous Nodes in an Active Network. In Proceedings of the Second International Workshop on Software and Performance, 2000.
9. John Heidemann, Fabio Silva, Shalermek Intanagonwiwat, Ramesh Govindan (USC/ISI), Deborah Estrin, Deepak Ganesan (UCLA). Building Efficient Wireless Sensor Networks with Low-Level Naming. In Proceedings of the 18th ACM Symposium on Operating System Principles, 2001.
10. Jason Hill and David Culler. A wireless embedded sensor architecture for system-level optimization. Intel Research IRB-TR-02-00N, 2002.
11. Jason Hill, Robert Szewczyk, Alec Woo, Seth Hollar, David Culler, and Kristofer Pister. System Architecture Directions for Networked Sensors. In the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, 2000.
12. Victor Hsu, Joseph M. Kahn, and Kristofer Pister. Wireless Communications for Smart Dust. Electronics Research Laboratory Technical Memorandum Number M98/2, 1998.
13. Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan, and John Heidemann. Impact of Network Density on Data Aggregation in Wireless Sensor Networks. Technical Report 01-750, University of Southern California Computer Science Department, 2001.
14. Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, 2000.
15. Java 2 Platform Micro Edition (J2ME) Technology for Creating Mobile Devices White Paper. http://java.sun.com/j2me/docs/
16. Java Card Technology. http://java.sun.com/products/javacard/
17. Richard K. Johnsson, John D. Wick. An Overview of the Mesa Processor Architecture. In Proceedings of the Symposium on Architectural Support for Programming Languages and Operating Systems, 1982.
18. Joseph M. Kahn, Randy H. Katz, Kristofer Pister. Next Century Challenges: Mobile Networking for "Smart Dust." In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, 1999.
19. Philip J. Koopman, Jr. Modern Stack Computer Architecture. In System Design and Network Architecture Conference, 1990.
20. Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification, Second Edition. Addison-Wesley, 1999.
21. Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: A Tiny AGgregation Service for Ad-Hoc Sensor Networks. In submission.
22. Samuel R. Madden, Mehul A. Shah, Joseph M. Hellerstein, and Vijayshankar Raman. Continuously Adaptive Continuous Queries over Streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2002.
23. Alan Mainwaring, private communication, 2002.
24. Dejan S. Milojicic, Fred Douglas, Yves Paindaveine, Richard Wheeler, and Songnian Zhou. Process Migration. In ACM Computing Surveys, Volume 32, Issue 3, September 2000.
25. Charles H. Moore and Geoffrey C. Leach. FORTH - A Language for Interactive Computing. 1970.
26. Michael Noakes, Deborah Wallach, and William J. Dally. The J-Machine Multicomputer: An Architectural Evaluation. In Proceedings of the 20th International Symposium on Computer Architecture, 1993.
27. Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan, James Eric Tilton, Jason Flinn and Kevin R. Walker. Agile application-aware adaptation for mobility. In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, 1997.
28. Charles E. Perkins, Elizabeth M. Belding-Royer, and Samir Das. Ad Hoc On Demand Distance Vector (AODV) Routing. IETF Internet draft, draft-ietf-manet-aodv-09.txt, November 2001 (Work in Progress).
29. Adrian Perrig, Robert Szewczyk, Victor Wen, David Culler and J. D. Tygar. SPINS: Security Protocols for Sensor Networks. In The Proceedings of Mobicom 2001, 2001.
30. Phillip Stanley-Marbell and Liviu Iftode. Scylla: A Smart Virtual Machine for Mobile Embedded Systems. In Proceedings of The 3rd IEEE Workshop on Mobile Computing Systems and Applications, 2000.
31. Robert Szewczyk, private communcation, 2002.
32. David L. Tennenhouse and David J. Wetherall. Towards an Active Network Architecture. In Computer Communication Review, Vol. 26, No. 2, April 1996.
33. Thorsten von Eicken, David Culler, Seth Goldstein, and Klaus Schauser. Active Messages: A Mechanism for Integrated Communication and Computation. In Proceedings of the 19th International Symposium on Computer Architecture, 1992.
34. David J. Wetherall, John V. Guttag and David L. Tennenhouse. ANTS: A Toolkit for Building and Dynamically Deploying Network Protocols. IEEE OPENARCH '98, 1998.
35. Alexander L. Wolf, Dennis Heimbigner, John Knight, Premkumar Devanbu, Michael Gertz, and Antonio Carzaniga. Bend, Don't Break: Using Reconfiguration to Achieve Survivability. Third Information Survivability Workshop, October 2000.

Index Terms

• Networks

  • Network types

    • Mobile networks