Diss. ETH Nr. 17397 A State-Based Programming Model for Wireless Sensor Networks Oliver Kasten 2007 Abstract Sensor nodes are small, inexpensive, and programmable devices that combine an autonomous power supply with computing, sensing, and wireless communication capabilities. Networks of sensor nodes can be deployed in the environment at a large scale to unobtrusively monitor phenomena of the real world. Wireless sensor networks are an emerging field of research with many potential applications. So far, however, only few applications have actually been realized. This is in part due to the lack of appropriate programming support, which makes the development of sensor-network applications tedious and error prone. This dissertation contributes a novel programming model and development environment for the efficient, modular, and well structured programming of wireless sensor nodes. Today there are two principal programming models used for sensor nodes, the multi-threaded model and the event-driven model. The multi-threaded model requires system support that is often considered too heavy for sensor nodes that operate at the low end of the resource spectrum. To cope with this issue, the event-driven model has been proposed. It requires very little runtime support by the system software and can thus be implemented even on the most constrained sensor nodes. The simple and lightweight approach to system software, however, tends to make event-driven applications in turn quite memory inefficient: Since the event-driven model limits the use of local variables, programmers need to store temporary data in global variables. The memory of global variables, however, cannot easily and automatically be reused, hence the memory inefficiency. To counter this effect, programmers can resort to manual memory management, though this significantly affects program correctness and code modularity. In addition to its drawback of memory inefficiency, event-driven programming requires developers to manually keep track of the current program-state, which makes code modularization and debugging difficult, and leads to unstructured code. The key contribution of this dissertation is to show that the inadequacies of the event-driven model can be remedied without impairing its positive aspects, particularly its memory-efficient realization in sensor-node system software. Concretely, we present the Object State Model (OSM), a programming model that extends the event-driven programming paradigm with a notion of hierarchical and concurrent program states. Our thesis is that such a state-based model allows to specify well-structured, modular, and memory-efficient programs, yet requires as few runtime-resources as the event-driven model. To support this claim, we also present a programming environment based on the OSM model (including a programming language and compiler), as well as a sensor-node operating system capable of executing OSM programs. The main idea behind OSM is to explicitly model sensor-node programs as state machines, where variables are associated with states and computational operations are associated with state transitions. In OSM, states serve three purposes. Firstly, states are used as scoping mechanism for variables. The scope and lifetime of variables attached to a state is confined to that state and all of its substates. The memory for storing a state's variables is automatically reclaimed by the runtime system as the program leaves the corresponding state. State variables can be thought of as the local variables of OSM. As such they represent a great advancement over event-driven programming, where the majority of variables effectively have global scope and lifetime. By modeling temporary data with state variables, the use of OSM can significantly increase a program's memory efficiency. Secondly, the explicit notion of program states allows to model the structure and control flow of a program on a high abstraction level. Specifically, programs can be initially specified in terms of coarse modules (i.e., states), which can be subsequently refined (with substates), leading to modular and readable program code. The third purpose of states is to provide a context for computational operations. States clearly define which variables are visible, and at what point in the control flow the program resides when an operation is executed. In the event-driven model, in contrast, the program's context has to be maintained manually, which typically constitutes a significant fraction of the code, thus making the program hard to read and error prone. The OSM programming language captures the three concepts described above in order to foster memory efficient, modular, and well-structured programs. A compiler for the proposed language transforms state-based OSM programs back into an event-driven program notation, adding code for automatic memory management of state variables and code for automatic control-flow management. The compiler-generated code is very lean and does not impose additional requirements on the system software, such as dynamic memory management. Rather, the transformed programs are directly executable on our event-driven system software for resource-constrained sensor nodes. Our language, compiler, and sensor-node system software form the basis of our thesis and constitute a complete state-based programming environment for resource-constrained sensor nodes based on OSM.