Maté: Building Application-Specific Sensor Network Language Runtimes

Composed of tens of thousands of tiny motes with very limited resources, 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, primarily due to code size. Reprogramming a node must not cause it to fail; in long-term, remote deployments, replacing dead nodes can range from expensive to impossible.

Virtual machines are a compelling solution to these challenges. In sensor networks, communication is the greatest energy cost; reducing the traffic necessary to reprogram a mote can allow more frequent reprogrammings, a longer network lifetime, or both. By abstracting high-level operations into VM bytecodes, a VM program can be very short, on the order of bytes instead of kilobytes. Additionally, a VM can provide a safe program execution environment; buggy programs cannot irrevocably crash a mote.

One issue that arises is a tension between flexibility and efficiency. The more tailored a VM is to a specific application, the more efficient it can be; however, this tailoring comes at a cost of flexibility to changing requirements. Approaches such as the Java Language provide a general computational VM and provide flexibility through class libraries; our goal is to provide a more customizable system, allowing the user to decide where on the flexibility-efficiency spectrum to place their VM at the bytecode level.

A virtual architecture is, by itself, of limited use. Users must be able to write code in a programming language that compiles (or interprets) to the virtual bytecodes. The choice of language can be considered part of the customization of a VM; a LISP-machine-like architecture will support a LISP-like language much more efficiently (in terms of code size) than a JVM-like architecture will.

Maté is general architecture that allows users to build a wide range of virtual machines. It is an event-driven stack-based architecture, for which a user can select the bytecodes and execution events. A user builds a Maté VM in three steps:

1. Selecting a language, which defines a set of VM bytecodes that express the basic language functionality. For example, in the case of TinyScript, a BASIC-like language, these bytecodes include operations such as loading and storing variables, arithmetic operations, and branches.
2. Selecting the desired execution events. Each event has its own execution context, which runs when the event is triggered. Each event has its own code image. They can be bound to periodic events such as Timers, stimuli such as packet reception, or even the execution of a certain bytecode.
3. Selecting the desired primitives. These primitives are operations beyond what the language inherently provides, such as taking a square root, sampling a sensor, or applying a filter to a buffer of data. Languages may have different ways to access them. In TinyScript, for example, primitives appear as function calls.

Figure 1: Constructing a Maté Virtual Machine

This generates a set of files, some of which build a TinyOS application for the desired VM. Others configure a Scripter program, telling it which language is being used and what primitives were selected.

Figure 2: The Resulting TinyOS Application and Scripter

The user can then write programs in the Scripter, which will compile down to the VM-specific binary code. These codes can then be sent over the network to a VM, which executes it.

Figure 3: Compiling and Running a Program

A Maté VM provides the advantages of concise code and safe execution, but also simplies network programming. Programs virally propagate through a network. Reprogramming a network merely requires adding a single mote running a new propagating capsule. When a mote hears a new capsule, it installs it, then begins forwarding it. After a short amount of time, every mote in the network runs the new code, with no effort or management by the user.

The event-driven nature of sensor networks can make writing race-free code very difficult. Initial versions of Maté avoided race conditions by severely restricting shared state between concurrent event executions. Current versions use a different approach; whenever Maté installs a new piece of code, it performs a full program analysis to compute the shared variables each event handler might access. Before running an event handler, Maté implicitly locks all of the necessary variables, and releases them when done. Programmers can add explicit lock yields in programs. Maté's locking algorithm is deadlock-free. In the absence of erroneus unlocks, it is also race-free, even though code might be propagating through the network, resulting in many different transient program versions.

Maté is in active development; a recent version and documentation are included in the standard TinyOS 1.1 release. The 1.1 release only includes a specific Maté VM, named Bombilla, and does not support constructing VMs. Bombilla follows the Maté architecture, however. We are currently working on making the Maté build process available to the general public.

We are currently working on three aspects of Maté. The first is code propagation. We have developed propagation algorithms that scale and perform very well for small pieces of code (single packets). We are working on extending this to larger code images. These propagation techniques are not constrained to code; they can just as easily be used for data.

The second area of work on Maté is security. Viral code raises a host of security issues. We are currently working on signing algorithms to safely distribute code in a manner that is resilient to physical mote compromise. Unfortunately, traditional public-key systems are not feasible, due to the data size requirements and computational complexity. We are primarily concerned with integrity over confidentiality.

Finally, we are developing simple scripting languages that can compile to a Maté VM. We currently have one, a BASIC-like language named TinyScript. To evaluate the expressiveness of the Maté architecture, we need to examine several language classes.

Phil Levis and Neil Patel are the principal developers of Maté; please contact them if you have any questions or problems.