Introduction

Sensor networks present a number of novel programming challenges for application developers. Their inherent limitations of computational power, communication bandwidth, and energy demand new approaches to programming that shield the developer from low-level details of resource management, concurrency, communication, and in-network processing, or at least separate these concerns from application logic.

Regiment is a high level language for declarative querying of sensor data that abstracts over the network by using a data model based on regions. Regions represent spatially distributed, time-varying sets of objects usually sets of nodes sharing a property of interest. The user constructs or discovers regions of interest and uses these set-like objects in a global Regiment program. Regions support operations such as data parallel maps, filters, and folds (e.g. reduction/aggregation). They can be used for collecting or aggregating data within from part or all of the sensor network. Further, Regiment supports triggered events which allow reactive programs on regions, for example, switching collection strategy when the quality of results falls below a threshold (e.g. fewer nodes responding).

Goals

Regiment has the following goals:

• Implicit coordinated node activity.
• Resilience to node and communication failure.
• Resource efficient and resource aware operation.

There are many challenges standing in the way of the above goals. Regions are distributed in space; for energy e ciency they should be operated on in place (rather than retrieving their data to a central location). Further, even keeping track of the membership of regions at a central location requires unacceptable communication. Energy e ciency demands that computation and communication happen in-network and with maximal locality. Unfortunately, regions such as the region consisting of all nodes with a particular sensor reading may be unpredictable and disconnected.

Methodology

Regiment is a purely functional language that does not permit input, output, or direct manipulation of program state. Regiment is based on the Functional Reactive Programming model, and uses monads [6] to encapsulate time-varying values such as sensor readings. Thus the Regiment programmer works with first class signals, a special case of which are regions signals of distributed collections. This approach allows a clean separation between Regiment s semantics and those of the time-varying signals.

The Regiment compiler must have as much knowledge as possible about the global program s control and data flow. To this end we ve made Regiment a multi-stage language [7]. That is, the compiler uses 1 partial evaluation [5] techniques to evaluate parts of the program at compile time. This is similar to macro expansion [3], or to static elaboration in hardware description languages [1]. In Regiment s case, the most computationally unpredictable portions of its computation happen during the compile time. The residual program is more akin to a query circuit as used in distributed stream processing systems [8]. In essence, the users program executes, constructing a query circuit as output.

The Regiment compiler operates by analyzing the query circuit to infer network topological relationships between regions in the program. For example, a region resulting from mapping an operation over another region will have the same spatial extent as the original. The compiler then uses this information to automatically generate the node-level program corresponding to the high level query circuit. In essence, the individual nodes run two threads for each region in the program one that assists in the formation and maintenance of the region in question, and one that carries out the task associated with that region (forming other regions, reading sensors, forwarding data).

In reality, thread abstractions are too heavy weight for weak sensor nodes such as the Mica2 mote. The Regiment compiler instead targets an intermediate language we have designed the Token Machine Language (TML). The notable feature of TML is its unification of unification of communication, control, and storage around the concept of a token. Tokens are small objects that can be disseminated across the network. A token causes computation upon its arrival at a node by invoking an atomic token handler. The e ect of the computation is to atomically change the token s own state as well as the state of other tokens held at the same node. Tokens are named by virtual addresses that are consistent across the network, which eases the management of distributed phenomena. We use this basic abstract machine to build up a threads using a continuation passing style transformation [2]. We further build a gradient service for doing directed-di usion-like communication [4]. The intermediate language, augmented in this way, provides all the functionality necessary to generate node-level programs corresponding to original Regiment program.

Progress

We constructed a prototype Regiment compiler targeting TML. We have tested our programs using a sensor network simulator that directly implements the TML abstract machine. We have begun preliminary experiments in implementing TML in TinyOS.

Future

We will focus on obtaining deeper insight into implementing advanced features of Regiment (events, nested regions, region joins, etc) e ciently. We further hope to understand which high level features cannot be implemented with any guarantee of locality or communication e ciency. At the same time, we will continue our work on the backend, completing our implementation of TML on TinyOS, and looking to improve our implementations of data dissemination, aggregation, and leader election.

References:

[1] Arvind, Rishiyur S. Nikhil, Daniel L. Rosenband, and Nirav Dave. High-level Synthesis: An Essential Ingredient for Designing Complex ASICs. In Proceedings of ICCAD 04, San Diego, CA, 2004.

[2] Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. The essence of compiling with continuations. SIGPLAN Notice 39(4):502 514, 2004.

[3] M. Flatt. Composable and compilable macros: You want it when? In Proceedings of ACM SIGPLAN International Conference on Functional Programming, 2002.

[4] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed difusion: A scalable and robust communication paradigm for sensor networks. In Proc. International Conference on Mobile Computing and Networking, August 2000.

[5] N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. International Series in Computer Science., 1993.

[6] Eugenio Moggi. Computational lambda-calculus and monads. In Proceedings 4th Annual IEEE Symp. on Logic in Computer Science, LICS 89, Pacific Grove, CA, USA, 5 8 June 1989, pages 14 23. >IEEE Computer Society Press, Washington, DC, 1989.

[7] Tim Sheard. Accomplishments and research challenges in meta-programming. Lecture Notes in Computer Science, 2196:2, 2001.

[8] S. Zdonik, M. Stonebraker, M. Cherniack, U. Cetintemel, M. Balazinska, and H. Balakrishnan. The aurora and medusa projects. Bulletin of the Technical Committee on Data Engineering, 2001.