Overview

The main goal of this project is to produce abstractions and mechanisms necessary to develop a macroprogramming environment that enables a developer to easily and robustly specify and program the global behavior of a distributed computation in sensor networks. The main novelty of this macroprogramming environment, Kairos, is that an entire sensor network is taskable as a single entity within a centralized, sequential program, thereby easing the complexity of sensor networks programming. Kairos consists of three major components that encapsulate such abstractions and mechanisms: a high level (C-like) programming language; a compilation environment to translate such programs into distributed versions that execute on individual motes; and a runtime system that transparently orchestrates such execution for correctness, high performance, and robustness. We will also deliver a usable implementation of Kairos on the mote platform for researchers and users both within and outside CENS.

Approach

We expose a centralized programming view of the sensor network, over which programmers can then write programs that access the resources of the sensor network as a single entity. We do this by providing simple abstractions for a sensor node, for a collection of sensor nodes, and for the memory, sensors and actuators available at a sensor node. We also provide language-level abstractions that let a programmer write code that is very nearly sequential in nature. Currently, Kairos provides a dialect of C that is augmented with straightforward language constructs and code annotations for the above notions.

We then take such a centralized program, and convert it into a collection of fine-grained distributable sub-programs, so that such a sub-program can execute anywhere in the network. We provide this ability primarily in order to aggressively exploit opportunities for in-network processing, and thereby reducing the energy cost of sensor data movement at runtime, since radio transmissions are the chief consumer of energy in many wireless sensor networks. Other important benefits of such execution flexibility include the ability to dynamically parallelize sub-program executions on nodes in order to minimize latency, and to efficiently tolerate and overcome network and node failures by isolating and restarting sub-programs that were executing on faulty nodes.

As part of our compilation framework, we provide mechanisms to generate such sub-programs, called node cuts for any given centralized Kairos program. As part of our runtime framework, we implement the runtime facility to determine and schedule the set of nodes on which sub-programs should execute for optimal network economy, latency, and robustness. We also provide efficient runtime mechanisms so that the data manipulated by such distributed instances of sub-programs is consistent, so that global correctness properties can be guaranteed.

Systems/Experiments

We tested an early prototype of Kairos on a medium-scale testbed consisting of Stargates and Mica2/MicaZ nodes over programs written in Python. We simulated the sensor inputs and multi-hop network configurations, and matched the results against experimental outputs to make sure that our basic premise is sound.

We are now developing an exclusively mote-based implementation of Kairos so that we can conduct experiments on a large scale (~ 100 notes) multi-hop mote testbed that is operating under realistic noise and interference conditions. We would also be shortly performing large, real-world experiments such as a “Pursuer-Evader” game, in which a mobile pursuer robot tracks an evader robot, with realistically-modeled sensors. We intend to program such a system completely in Kairos, and compare the performance (application accuracy and fidelity, and program brevity, efficiency, and flexibility) against a manually coded and explicitly distributed version of the Pursuer-Evader game. While many applications, such as the Pursuer-Evader experiment, in wireless sensor networks can exploit loose notions of data consistency and reliability, there seem to be other important applications, such as distributed street parking, that have stringent notions of data reliability and consistency. We shortly plan to implement such a “model app” for testing the reliability properties of our system.

Accomplishments

1. Ramakrishna Gummadi, Omprakash Gnawali, Ramesh Govindan, Macro-programming Wireless Sensor Networks using Kairos , In Proceedings of the International Conference on Distributed Computing in Sensor Systems (DCOSS), June 2005.
2. Ramakrishna Gummadi, Omprakash Gnawali, Ramesh Govindan, Todd Millstein, Failure Recovery in a Macroprogrammed Sensor Network System , USC Technical Report 05-872.

Future Directions

We are currently implementing an “alpha” version of Kairos for the MicaZ/Telos motes. This version will incorporate the main language features designed so far, the compilation strategy of building node cuts that are close to the theoretic optima, and the implementation strategy of executing such node cuts correctly, efficiently, and concurrently. We hope to release this version for early testers in summer ’06.

We will then look into incorporating failure recovery components into our implementation. We have a “pre-alpha” prototype of the recovery system for a Stargate-based implementation, and we will first develop and improve efficient recovery algorithms centered on the node cut abstraction, and then implement the recovery facility for the motes.

Sensor networks have the interesting property that they operate primarily on numeric data, and the challenging constraint that they are bandwidth-starved. We will exploit this property to build more network-efficient algorithms that still guarantee correctness while working on locally inconsistent data that will be made globally consistent eventually. We will also explore how to make the runtime messaging more network efficient over a given deployment topology.

People

• Prof. Ramesh Govindan (USC), and Todd Millstein (UCLA)

• Ph.D. Students: Ramakrishna Gummadi (USC) and Nupur Kothari (USC)