IntroductionBackgroundTinyOS/nesCMote NetworksMaté v1.0RequirementsDesignData ModelScheduler: ExecutionConcurrency Manager: ParallelismCapsule Store: PropagationBuilding an ASVMActive Sensor NetworkingEvaluationConcurrencyPropagationFlexibility: LanguagesFlexibility: ApplicationsEfficiency: MicrobenchmarksEfficiency: ApplicationEfficiency: InterpretationRelated WorkDiscussion and Future WorkConclusionREFERENCES -3ptActive Sensor NetworksPhilip 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 using application specific virtual machines(ASVMs) to reprogram deployed wireless sensor networks.ASVMs provide a way for a user to define an application-specific boundary between virtual code and the VM en-gine. This allows programs to be very concise (tens tohundreds of bytes), making program installation fast andinexpensive. Additionally, concise programs interpretfew instructions, imposing very little interpretation over-head. We evaluate ASVMs against current proposals fornetwork programming runtimes and show that ASVMsare more energy efficient by as much as 20%. We alsoevaluate ASVMs against hand built TinyOS applicationsand show that while interpretation imposes a significantexecution overhead, the low duty cycles of realistic ap-plications make the actual cost effectively unmeasurable.1. INTRODUCTIONWireless sensor networks have limited resources andtight energy budgets. These constraints make in-networkprocessing a prerequisite for scalable and long-lived ap-plications. However, as sensor networks are embeddedin uncontrolled environments, a user often does not knowexactly what the sensor data will look like, and so mustbe able to reprogram sensor network nodes after deploy-ment. Proposals for domain specific languages — stillan area of open investigation [5, 7, 19, 21, 23, 28] —present possible programming models for writing theseprograms. TinySQL queries, for example, declare hownodes should aggregate data as it flows to the root of acollection tree.This wide range of programming abstractions has ledto a similarly wide range of supporting runtimes, rangingfrom in-network query processors [19] to native thread li-braries [28] to on-node script interpreters [5]. However,each is a vertically integrated solution, making them allmutually incompatible with each other. Additionally, theyall make implementation assumptions or simplificationsthat lead to unnecessary inefficiencies.Rather than propose a new programming approach toin-network processing, in this paper we propose an archi-tecture for implementing a programming model’s under-lying runtime. We extend our prior work on the Mat´e vir-tual machine (a tiny bytecode interpreter) [15], generaliz-ing its simple VM into an architecture for building appli-cation specific virtual machines (ASVMs). Our experi-ences showed that Mat´e’s harsh limitations and complexinstruction set precluded supporting higher level program-ming. By carefully relaxing some of these restrictionsand allowing a user to customize both the instruction setand execution triggering events, ASVMs can support dy-namically reprogramming for a wide range of applicationdomains.Introducing lightweight scripting to a network makesit easy to process data at, or very close to, its source.This processing can improve network lifetime by reduc-ing network traffic, and can improve scalability by per-forming local operations locally. Similar approaches haveappeared before in other domains. Active disks proposedpushing computation close to storage as a way to dealwith bandwidth limitations [1], active networks arguedfor introducing in-network processing to the Internet toaid the deployment of new network protocols [27], andactive services suggested processing at IP end points [2].Following this nomenclature, we name the process of in-troducing dynamic computation into a sensor networkactive sensor networking. Of the prior efforts, active net-working has the most similarity, but the differing goalsand constraints of the Internet and sensor networks leadto very different solutions. We defer a detailed compari-son of the two until Section 6.Pushing the boundary toward higher level operationsallows application level programs to achieve very highcode density, which reduces RAM requirements, inter-pretation overhead, and propagation cost. However, ahigher boundary can sacrifice flexibility: in the most ex-treme case, an ASVM has a single bytecode, “run pro-gram.” Rather than answer the question of where theboundary should lie — a question whose answer dependson the application domain — ASVMs provide flexibilityto an application developer, who can pick the right levelof abstraction based on the particulars of a deployment.Generally, however, we have found that very densebytecodes do not sacrifice flexibility, because ASVMsare customized for the domain of interest. RegionsVM,presented in Section 4, is an ASVM designed for ve-hicle tracking with extensions for regions based opera-tions [28]; typical vehicle tracking programs are on theorder of seventy bytes long, 1/200th the size of the origi-nally proposed regions implementation. A second ASVMwe have built, QueryVM, supports an SQL interface to asensor network at 5–20% lower energy usage than theTinyDB system [19], and also allows adding new aggre-gation functions dynamically.This paper has two contributions. First, it shows away to introduce a flexible boundary between dynamicand static sensor network code, enabling active sensornetworking at a lower cost than prior approaches whilesimultaneously gaining improvements in safety and ex-pressiveness. Second, this paper presents solutions toseveral technical challenges faced by such an approach,which include extensible type support, concurrency con-trol, and code propagation. Together, we believe theseresults suggest a general methodology for designing andimplementing runtimes for in-network processing.In the next section, we describe background informa-tion relevant to this work, including mote network re-source constraints, operating system structure, and thefirst version of Mat´e. From these observations, we de-rive three ways in which Mat´e is insufficient, establish-ing them as requirements for in-network processing run-times to be effective. In Section 3, we present