Lead Investigators

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

Overview

Wireless sensor networks consist of a system of distributed sensors embedded in the physical world. Building practical and reliable sensor network systems is a considerable challenge. The state of the art in today's sensornet programming is centered on a component-based language called nesC. nesC is a node-level language, and programs written in nesC use the services of a component-based operating system called TinyOS, which only supports node-level programs. We are pursuing an approach to programming sensor networks that significantly raises the level of abstraction over this practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node in the network, programmers implement a central program that conceptually has access to the entire network. This approach makes programs more readable, reliable, robust, and efficient, and pushes to the compiler the task of producing node-level programs that implement the desired behavior.

Approach

Current practice in sensor network programming uses a component-based language called nesC.  nesC and TinyOS provide abstractions and libraries that enable node-level sensor-network application programming, but ensuring the efficiency and reliability of sensor network applications is still tedious and error prone. For example, the programmer must manually decompose a high-level distributed algorithm into programs for each individual sensor node that efficiently communicate with one another, implement any necessary data consistency and control-flow synchronization protocols among these node-level programs, and explicitly manage resources at each node.

We are pursuing an alternative approach to programming sensor networks that significantly raises the level of abstraction over current practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node in the network, programmers implement a central program that conceptually has access to the entire network. This change allows a programmer to focus attention on the higher-level algorithmics of an application, and the compiler automatically generates the node-level programs that properly and efficiently implement the application on the network. This style of programming sensor networks is commonly called macroprogramming.

Kairos, our macroprogramming flavor, is a modest extension to C. Kairos augments C with constructs for addressing the nodes in a network and accessing local state from individual nodes. These features allow programmers to naturally express the global intent of their sensor-network programs without worrying about the low-level details of inter-node communication and node-level resource management.

By default, a Kairos program is defined to have a sequential thread of control, which provides a simple semantics for programmers to understand and reason about. However, Kairos includes a novel language construct for parallel iteration called cfor, which can be used, for example, to iterate concurrently over all the nodes in the network or all one-hop neighbors of a particular node.

The Kairos compiler translates Kairos programs into node-level nesC programs that can be directly linked with standard TinyOS components and the Kairos runtime system, and then run over a network of sensor motes.

The key technical challenge for Kairos is the need to automatically implement high-level centralized programs in an efficient and reliable manner on the nodes in the network.   The Kairos compiler and runtime system cooperate to meet this challenge in a practical manner.

Systems/Experiments

We have implemented Kairos for the mote platform. The Kairos implementation consists of the Kairos compiler and the Kairos runtime.

The Kairos compiler is built as an extension to the CIL infrastructure for C analysis and transformation.  Our compiler accepts a Kairos program as input and produces node-level nesC code that can be linked with standard TinyOS components and the Kairos runtime system.  The Kairos runtime system is a collection of TinyOS modules that orchestrates the execution of the compiler-generated nesC code across the nodes in the network.

The Kairos compiler and runtime cooperate to tackle two key technical challenges.  First, they must partition a Kairos program into chunks that can be executed on individual nodes and determine at which node to run each chunk, striving to minimize communication costs.  Second, they must provide concurrent but serializable execution of cfors.  We discuss each challenge in turn.

The Kairos compiler performs a dataflow analysis in order to partition a Kairos program into a set of nodecuts. The Kairos compiler converts each nodecut into a nesC task, to be executed by the Kairos runtime system on a single node in the network. A nodecut can include any number of statements, but it must have the property that just before it is to be executed, the runtime system can determine the location of all the node-local variables needed for the nodecut's execution. The algorithm used by the compiler to partition a program into nodecuts is depicted in Figure 1.

Figure 1. Algorithm for determining nodecuts.

The Kairos runtime system is responsible for sequentially (ignoring cfor for the moment) executing each nodecut produced by the compiler across the sensor network.  When execution of a nodecut C completes at some node n, that node's runtime system determines an appropriate node n' at which to run the subsequent nodecut C' and migrates the thread of control to n’.   Because of the special property of nodecuts, the runtime system knows exactly which node-local variables are required by C', so these variables are also concurrently fetched to n' before execution of C' is begun.

To determine where the next nodecut should be executed, the runtime uses the overall migration cost as the metric. The runtime knows the number of node-local variables needed from each node for executing the next nodecut, as well as the distances (the number of radio hops) of these nodes relative to each other according to the current topology. The runtime chooses the node that minimizes the cost of transfers from within this set.

To execute a cfor loop, the kairos runtime system forks a separate thread for each iteration of the loop.  We call the forking thread the cfor coordinator.  Program execution following the cfor only continues once all the forked threads have joined.  Each forked thread is initially placed at the node representing the value of the variable the cfor iterates over, and any subsequent nodecuts in the thread are placed using the migration algorithm for nodecuts described before. A forked thread may execute a cfor statement, in which case the thread itself becomes the coordinator for the inner cfor, forking threads and awaiting their join.

To provide reliability in the face of concurrency, Kairos ensures serializability of cfor loops.  This allows programmers to correctly understand their Kairos programs in terms of sequential execution semantics. The Kairos compiler and runtime ensure serializability by transparently locking variables accessed in each cfor body. We have implemented a novel distributed locking scheme. The use of locking has the potential to cause deadlocks, and we have also implemented a low-overhead distributed deadlock detection scheme.

We evaluate the Kairos implementation for a number of applications, with Kairos running on TelosB Tmote Sky motes. We compare a Kairos implementation of a pursuit-evasion game against a hand-coded node-level nesC implementation of the same application written by others on a 40 node mote testbed. Figure 2 shows how both implementations compare as far as application error and detection latency are concerned. This figure shows that the correctness of Kairos is comparable to a hand-coded version.

Figure 2. Correctness of Kairos-PEG with a mote-native implementation (Mote-PEG).

We also implement a simple street-parking application in Kairos and evaluate the locking and deadlock detection algorithms on it. We execute the application on a 10 node chain topology, with 10 requests for free spots coming in sequentially at the node in the center. Figure 3 depicts the performance of two versions of the street-parking application (one with a deadlock, one without) with various versions of Kairos (without locking, without deadlock detection).

Figure 3. Performance of a street-parking app (SP), SP without locking (SP-NL), SP with artificially induced deadlock and no deadlock recovery (SP-NR), SP with artificially induced deadlock and deadlock recovery (SP-ID).  Both SP and SPID function correctly as expected, unlike SP-NL and SPID-NR. Furthermore, both SP and SPID have similar performance to a scheme with no locking (SP-NL).\

As expected, the Kairos implementation without locking (SP-NL) fails to correctly allocate free spots, while the implementation without deadlock detection and recovery (SP-NR) hangs in the middle due to a deadlock, while the other two (SP, SP-ID) perform correctly. As expected, Kairos with deadlock detection and recovery (SP-ID) has a higher message overhead than the other versions.

Accomplishments

We developed the necessary language abstractions and algorithms that provide us efficiency and reliability. We wrote a compiler to implement these abstractions in nesC. The compiler also generates an application-specific runtime to implement the necessary data and control communication. We evaluated this system on a network of up to 40 motes on various experiments mentioned above. We also developed and implemented our declarative failure recovery algorithms in Python for Stargate-hosted motes, and evaluated them on a testbed of up to 36 motes.

Future Directions

We are interested in developing and evaluating various relaxed consistency programming models. We are also interested in implementing simpler and more efficient reliability mechanisms based on the idea of transactional memories.

People  

Faculty:

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

Graduate Students:

• Ramakrishna Gummadi, Nupur Kothari