OVERVIEW

Little concern has been given thus far to how to program wireless sensor networks, which is the topic of this project. Most of the time, application algorithms are written as a set of carefully tuned, interconnected systems components and are hard-coded into the memory of each node. Components are hand-wired to one another to form cohesive and efficient applications. In some platforms, the application developer can use a node-level OS (e.g. TinyOS) to craft the application, which has the advantages of modularity, multi-tasking, a hardware abstraction layer, and low-level control.  Nevertheless, the developer still has to create a single executable image to be downloaded into each node. Such nodal programming runs counter to the promise of large-scale wireless sensor networks. Clearly, there is a need for efficiently programming sensor networks as an aggregate – we call this “macroprogramming”. Heretofore, sensor network software has been architected for efficiency at the component or service level. However, as a result of the development of useful macroprogramming primitives with non-trivial substructure, the structure of applications has become more complex. This points in the direction for macrocompiler support for structural optimization of applications. Moreover, often sensor networks will have long-deployment cycles and serve multiple transient users with dynamic needs over their lifetime. This points in the direction of a dynamic programming environment.

APPROACH

Our vision is to make sensor network programming easy without sacrificing efficiency. This has led to two distinct subprojects: one focused on compile-time support for macroprogramming, and the other on dynamic programming at runtime.

One way to provide the user with an easy way to collect meaningful data is to view a sensor network as a distributed database. This is done by systems such as Berkeley’s TinyDB and Cornell’s Cougar. A user query is expressed in a suitable relational language (usually enhanced with spatio-temporal primitives) and is resolved by using techniques such as aggregation trees. While fine for many monitoring tasks, such an approach falls apart for more complex tasks involving collaborative signal processing (as opposed to computation expressed over relations), computational loops, and event processing. For example, tracking a spatially mobile phenomenon ends up putting the user in the loop. The problem here is that such an approach focuses on the expressiveness of the task, and not on how the computation to perform that task via in-network processing should be structured.

Sensor network applications of arbitrary complexity can be designed as a set of interconnected components. This is part of the design philosophy of TinyOS. The difficulty with component systems is that as applications become more complicated, the configuration and wiring of components becomes tough to express and intractable to hand-optimize. Our first subproject, proposes a flexible configuration language with macrocompiler support for optimization. We call this project SNACK, a sensor network application construction kit.

SNACK is a composition language for sensor network applications built on top of, and leveraging, TinyOS and nesC. SNACK makes it possible to write smart libraries that weave themselves together into efficient applications.

Our goal is to make it easier to program an efficient sensor network application. To make this more concrete, imagine our application that samples light and temperature, and forwards this data up a routing tree to a sink. Again, we want the description of this application to be two lines long:

TempSampler  -> [collect::Put16] RoutingTree;
LightSampler -> [collect::Put16] RoutingTree;

But TempSampler, LightSampler, and RoutingTree are too high-level to be written in nesC or some other systems programming language. Instead, they should be services -- combinations of components -- taken from a service library.

TinyOS's component model was intended more for the connection of primitive components than for the construction of smart services like these. SNACK therefore adds four features to TinyOS's component model; together, these features make smart libraries relatively easy to write.  They are:

• Instances. The TinyOS model requires that every component used occurs exactly once. This makes some kinds of optimization easier (inlining in particular). But say that temperature and light samplers each wanted to average their sample values. Software engineering principles would suggest using a component, such as a “EWMA” (exponentially weighted moving average), to implement this averaging. EWMA could be optimized and debugged once, then used inside both TempSampler and LightSampler. Unfortunately, TinyOS requires either separate Temp-EWMA and Light-EWMA components -- preventing code sharing -- or it requires the two sampler services to explicitly cooperate. Either mechanism prevents the implementation of pluggable, reusable services. SNACK implements instances on top of TinyOS: each sampler contains a EWMA, simplifying and clarifying the program.
• Parameterization. The TinyOS component encapsulation model lacks support for tunable parameters. Application parameters such as timer values are specified in code. To change the timer frequency within some service, you must change its initialization code -- thus you must understand its initialization code. SNACK lets a service or component author expose specific tunable initialization knobs to the service user.
• Controlled Sharing. Strict memory limitations on sensor nodes require us to avoid any unnecessary instance duplication. (TinyOS doesn't have this problem, since there are no instances: any component occurs at most once.) The SNACK compiler is smart enough to combine components when possible. Service authors can control this sharing with (1) loose parameter constraints (“this timer frequency is at least 10 Hz”, which lets this timer be combined with any other timer with frequency >= 10 Hz); (2) connectedness constraints (“this interface can be used at most once”); and (3) explicitly marked exclusivity (“this component must not be shared”, because it's used to store private state, for example).
• Default components. A service can specify some default components that the application can override. For example, a routing tree might include a default link estimation algorithm.
• Service weaving. Finally, SNACK allows the construction of self-weaving services, whose components weave themselves together with other services into a small configuration.  The key part of a self-weaving service is the transitive connection. Where a conventional component connection says “A and B are directly connected using interface I”, a transitive connection says “A and B are connected via some path using interface I”. Service weaving lets multiple services automatically join together to create a minimal, shared path for messages or events. This in turn reduces asynchrony and memory cost. The main benefit of service weaving, however, is that simple service interfaces can compile into efficient implementations.  Without service weaving, services would have to provide more complex hooks by which the user would perform weaving herself.

These features in turn inspire different kinds of components than have been common in TinyOS. Together, these language features and components encourage the construction of smart services, which in turn make two-line applications a reality.

Below is a figure depicting application specification and compilation using self-weaving services. An application is specified by connecting a few application-level services. These application-level services – light and temperature samplers and two declarations of tree dispatch – are expanded into their composite services. The partial expansion shows a one level expansion of the tree dispatch and the samplers. The further expansion shows the expansion of the tree service and link estimator. The full expansion (not shown) is a wiring containing the maximum set of component instances required to realize the application. Our compiler generates this full expansion, identifies component declarations that are compatible and can be realized with a single instance, and constructs the application with the minimum number of instances required to do so. White components are derived from the light sampling half of the application; light grey components are from the temperature sampling half; and dark grey components are the result of the compiler merging compatible components from the full expansion into single instances.

Our second subproject focuses on efficient mechanisms to realize in-network processing, and adopts the model of information-driven computation whereby the computation unfolds in response to the evolution of the physical state of the environment. In particular, computation agents propagate virally within the network to nodes as dictated by the sensed state of the worked – e.g. as a target moves, the computation moves along with it to nearby nodes. Working towards this vision, we propose a framework to define and support lightweight and mobile control scripts that allow the computation, communication, and sensing resources at the sensor nodes to be efficiently harnessed in an application-specific fashion. The replication/ migration of such scripts in several sensor nodes allows the dynamic deployment of distributed algorithms into the network.

A specific instantiation of our approach is the SensorWare systems, which defines, creates, dynamically deploys, and supports sensor node functions in the form of mobile scripts. The SensorWare architecture is based on a scriptable lightweight run-time environment, optimized for sensor nodes that have limited energy and memory. This environment securely hosts one or more simple, compact, and platform- independent sensor-node control scripts. The sensing, communication, and signal-processing resources of a node are exposed to the control scripts that orchestrate the dataflow to assemble custom protocol and signal processing stacks. SensorWare has to also promote the creation of distributed proactive algorithms based on the scripting language described above. For this reason the scripts are made mobile using special language commands and directives. A script can replicate or migrate its code and data to other nodes, directly affecting their behavior. A usage scenario can be like the following: A user sends a query to the sensor network. The query is a script, a state machine in its simplest form, which is injected to one or more sensor nodes. The script will describe among other things how it is going to populate itself to other nodes. The process of population can continue depending on events and the current state. For example as the events of interest are moving to a different area, the scripts can move along with them, possibly trying to predict their next move. The populated scripts will collaborate among themselves in order to extract the information needed by the user, and when this information is acquired it is sent back to the user. The figure below shows the SensorWare architecture:

A new effort has focused on dynamically binding modules of code at runtime. There are generally two approaches to flexible tasking and re-tasking. One is to design a high-level language and its runtime environment; the other is to design a low-level general-purpose virtual machine. There are drawbacks to both approaches. The former lacks runtime flexibility. The latter lacks efficiency because instructions are interpreted. We explore the tradeoff between flexibility and efficiency and propose an environment in which instructions are executed as native code in resource constrained sensor nodes, but are interpreted in nodes with faster processors. We insert modules of native code into the operating systems of tiny sensor nodes during runtime. On higher class devices (e.g. iPaqs, PCs), we emulate these modules. The result is a general purpose interpreter that is very efficient for low class devices.

SYSTEMS / EXPERIMENTS

An initial version of SNACK components and compiler have been implemented and can build applications for any platform supported by ncc and TinyOS. As an example, we implemented an application using SNACK that collects light and temperature values and forwards them up a routing tree. We compared this SNACK forwarder to the Surge application (part of the TinyOS release) on the mica2 platform. Despite the composability of SNACK services, we found that the SNACK forwarder does not require more RAM than the Surge application. Furthermore, its ROM consumption, while larger than Surge, is reasonably larger, and is nowhere near the limit of the platform.

An initial version of SensorWare is functional on a variety of StrongArm and Intel processor based platforms under Linux and eCos operating systems. Porting to other processors (e.g. StrongThumb) and operating systems (e.g. uC/OS) is in progress. Under Linux, SensoWare can run on top of the sensor node hardware abstraction layer provided by the EmStar system discussed later, and is therefore available to CENS class nodes. Functions available to SensorWare scripts include those relating to sensing, networking, and actuation (with several robots).

Our implementation of SensorWare on StrongArm occupies less than 180Kbytes of code memory and thus easily fits into several sensor node platforms. Extensive delay measurements on our iPAQ-based prototype sensor node platform reveal the small overhead of SensorWare to the algorithms (less than 0.3msec in most high-level operations). In return the programmer of the sensor network receives compactness of code, abstraction services for all of the node’s modules, and in-built multi-user support.

Our vision of dynamically inserting native sensor node code at runtime has led to the beginning of an implementation of a new operating system, SOS, on Berkeley Mica2. SOS allows modules written in native instructions to be inserted during runtime and uses a proxy to dynamically bind functions from one module to another.

The above diagram gives a high-level overview of SOS. The communication between components is made by passing fixed sized messages through two functions, call and post, that are situated in well-known memory locations. The SOS kernel dispatches messages to addressed destinations.  The function “call” emulates a synchronous function call, and “post” is used for asynchronous function calls.

ACCOMPLISHMENTS

Paper Submissions:

Greenstein, B., Kohler, E., Culler, D., Estrin, D., “Distributed Techniques for Area Computation in Sensor Networks”.
Greenstein, B., Kohler, E., Estrin, D., “A Sensor Network Application Construction Kit (SNACK)”.

A functional version of SensorWare has been publicly released via SourceForge.

FUTURE DIRECTIONS

In the future we will continue to expand the library of components available to the SNACK end-user from which to develop applications. We will develop services that are comprised of these components that can be snapped together to facilitate application development. We will continue to add macrocompiler support to further optimize the structure of applications. As our component library grows in scope down to the level of hardware interrupts, we will port our code to various platforms such as the Mica2 motes, Stargates, and iPaqs. We will write sample applications with the goal of testing the level of complexity that systems developers can control. We will also ask non-programmers to write applications to examine the ease of application construction. Furthermore, we will take these applications and compare efficiency in terms of code footprint, memory allocation, and energy consumed by the CPU and radio. Finally, we hope to use SNACK to develop applications robust enough to deploy. For instance, we envision deploying the macroprogramming environment for the experimental sensing system (ESS) test-bed at James Reserve for use by scientists, students, and educators.

In future we also seek to evolve SensorWare towards a complete macroprogramming environment that a developer may use to describe an application computation requirement, which will then be decomposed into in-network processing and back-end processing. The former itself will be expressed in terms of interacting nodal behaviors and mobile agent behaviors. There are many challenges in designing such an environment. One is to provide ability to express data collection and processing in a manner that makes sense to an end user, but also provides a rich enough interface to have sufficient control over underlying primitives to optimize execution. Another is providing the associated mapping and code activation logic to invoke the most useful of the available primitives to produce the results desired by the application.

PEOPLE

Faculty:

Prof. Deborah Estrin
Prof. Mani Srivastava

Graduate Students:

Athanassios Boulis
Ben Greenstein
Chih-Chieh Han
Andrew Parker
Roy Shea