IntroductionBackgroundDesignScheduler: Execution ModelConcurrency Manager: ParallelismCapsule Store: PropagationPropagation and SecurityBuilding a Maté VMCustomizing a VM to an application domainEvaluationLanguagesCPU OverheadPropagationRegionsPursuer-Evader TrackingRegionsVMPegVMComparisonTinyDBDiscussionRelated WorkConclusionREFERENCES -3ptIn submission to OSDI 2004.Bridging the Gap: Programming Sensor Networks withApplication Specific Virtual MachinesPhilip Levis†, David Gay‡, and David Culler†{pal,culler}@cs.berkeley.edu, [email protected]†EECS Department‡Intel Research BerkeleyUniversity of California, Berkeley 2150 Shattuck AvenueBerkeley, CA 94720 Berkeley, CA 94703ABSTRACTWe propose application specific virtual machines as amethod to safely and efficiently program sensor networks.Although sensor networks encompass a wide range ofapplication domains, any given network supports a sin-gle one. A VM tailored to a particular deployment canprovide retasking flexibility within its application classwhile keeping programs efficient. We present Mat´e, anarchitecture for customizing VMs over a wide range ofsensor network applications. Customizing the instruc-tion set and triggering events allows for language flex-ibility, provides very high code density, and enables awide range of applications.We evaluate Mat´e by comparing custom built VMs totwo existing proposals for user-level sensor network pro-gramming, abstract regions and tree-based aggregation(TinyDB). We show that a VM implemented in our ar-chitecture can provide equivalent functionality to the cur-rent implementations of these proposals while improvingefficiency. Additionally, by decomposing application do-mains into a set of reusable, fine-grained software com-ponents, implementing new user-level programming ab-stractions is greatly simplified.1. INTRODUCTIONOperating systems research has a long history of de-signing flexible abstractions. Sensor networks provide anew set of challenges and opportunities in this area: eachdeployment features specific hardware features and pro-cessing capabilities and, once deployed, networks mustbe reprogrammable in response to observed data or evolv-ing needs. As each deployment targets at a specific ap-plication domain (e.g., habitat monitoring or tracking),the system environment can be tailored to the domain’sneeds.In-situ reprogramming should be efficient and safe. En-ergy is the limiting resource in a sensor network: in-stalling new programs and executing them must be en-ergy efficient. As sensor networks are typically densefields of small nodes embedded in the environment, re-covering from a program-induced crash or failure – throughrebooting, for example – is difficult or impossible. A pro-gramming system must be able to safely recover frombuggy or badly conceived programs.The need for higher-level sensor network programminghas led to several proposed programming models. Forexample, abstract regions showed how data-parallel op-erators can concisely represent applications that requireinter-node data aggregation [25], and TinyDB demon-strated the effectiveness of declarative SQL-like queriesfor data collection [18]. While these proposals are stepsin the right direction, they address a limited set of ap-plication domains, and do not address all of the aboverequirements. TinyDB (SQL) is not a very general pro-gramming model and its query interpretation (i.e., pro-gram execution) is inefficient. Abstract regions compilesprograms into an full TinyOS image and installs the en-tire executable (tens of kilobytes); program installationis inefficient and there is no safety.Application specific virtual machines provide a wayof capturing application building blocks while allowingflexible and dynamic composition at the operating sys-tem level. In this paper, we propose using applicationspecific virtual machines as an intermediate layer betweenan application domain and the mote operating system(TinyOS). To further this goal, we have built Mat´e, a gen-eral architecture for application specific VMs. A usertailors a Mat´e VM to a specific application domain byselecting a programming language (in which end-userswill program) and a set of domain-specific extensions(e.g., support for planar feature detection). The Mat´eframework compiles programs to the generated VM’s in-struction set (bytecodes), and the VM runtime automati-cally propagates code through the network. Installation-time code analysis allows a VM to provide race-free andFigure 1: A layered decomposition of in-situ repro-gramming.deadlock-free execution parallelism.The separation between the three layers – user pro-gram, in-network representation, and the execution en-gine – is shown schematically in Figure 1. Using byte-codes as a transmission layer provides safety; tuning thelevel of abstraction (by selecting an appropriate languageand set of extensions) to a particular application’s re-quirements leads to efficient execution, as overhead canbe minimized; compiling to application-specific bytecodesmakes programs small (tens or a few hundred bytes),keeping propagation efficient.Mat´e is general enough to support existing proposalsfor sensor network programming models. We have builta VM with extensions for region-based operations, inwhich typical programs are on the order of seventy bytes(Section 4.4), a 99.5% reduction in size over the origi-nally proposed regions implementation. We have builta VM for performing similar sensor network queries toTinyDB (Section 4.5), with 11-30% energy savings. Wehave implemented two languages on top of Mat´e, TinyScript,a simple BASIC-like language, and motlle, a Scheme-like language, and believe the engine general enough tosupport other programming languages, such as TinySQL(our querying VM’s language is motlle). These increasesin efficiency come from separating the three layers inFigure 1. Separating the transmission layer from theexecution layer reduces the cost of installing a regionsprogram; separating the transmission layer from the pro-gramming layer reduces the cost of query execution.In earlier work, we proposed a particular virtual ma-chine as a mechanism to reprogram sensor networks [14],but it imposed draconian limitations that ultimately madeit unusable. This paper extends the work to a generalframework that supports multiple languages, program-ming models, and can be applied to a wide range of ap-plications.Section 3 covers the design of the Mat´e