Publications - with abstracts

Sensornet protocols periodically broadcast beacons for neighborhood information advertisement, but beacon transmissions are costly when power-saving radio duty cycling mechanisms are used. We show that piggybacking multiple beacons in a single transmission significantly reduces transmission costs and argue that this shows the need for a new layer in the sensornet stackan announcement layerthat coordinates beacons across upper layer protocols. An announcement layer piggybacks beacons and coordinates their transmission so that the total number of transmissions is reduced. With an announcement layer, new or mobile nodes can quickly gather announcement information from all neighbors and all protocols by issuing an announcement pull operation. Likewise, protocols can quickly disseminate new announcement information to all neighbors by issuing an announcement push operation. We have implemented an announcement layer in the Contiki operating system and three data collection and dissemination protocols on top of the announcement layer. We show that beacon coordination both improves protocol performance and reduces power consumption.

As sensor networks move towards increasing heterogeneity, the number of link lay ers, MAC protocols, and underlying transportation mechanisms increases. System developers must adapt their applications and systems to accommodate a wid e range of underlying protocols and mechanisms. However, existing communication architectures for sensor networks are not design ed for this heterogeneity and therefore the system developer must redevelop thei r systems for each underlying communication protocol or mechanism. To remedy this situation, we present a communication architecture that adapts to a wide range of underlying communication mechanisms, from the MAC layer to the transport layer, without requiring any changes to applications or protocols. We show that the architecture is expressive enough to accommodate typical sensor network protocols. Measurements show that the increase in execution time over a non-adaptive architecture is small.

Event-driven programming is a popular model for writing programs for tiny embedded systems and sensor network nodes. While event-driven programming can keep the memory overhead down, it enforces a state machine programming style which makes many programs difficult to write, maintain, and debug. We present a novel programming abstraction called protothreads that makes it possible to write event-driven programs in a thread-like style, with a memory overhead of only two bytes per protothread. We show that protothreads significantly reduce the complexity of a number of widely used programs previously written with event-driven state machines. For the examined programs the majority of the state machines could be entirely removed. In the other cases the number of states and transitions was drastically decreased. With protothreads the number of lines of code was reduced by one third. The execution time overhead of protothreads is on the order of a few processor cycles.

From experience with wireless sensor networks it has become apparent that dynamic reprogramming of the sensor nodes is a useful feature. The resource constraints in terms of energy, memory, and processing power make sensor network reprogramming a challenging task. Many different mechanisms for reprogramming sensor nodes have been developed ranging from full image replacement to virtual machines. We have implemented an in-situ run-time dynamic linker and loader that use the standard ELF object file format. We show that run-time dynamic linking is an effective method for reprogramming even resource constrained wireless sensor nodes. To evaluate our dynamic linking mechanism we have implemented an application-specific virtual machine and a Java virtual machine and compare the energy cost of the different linking and execution models. We measure the energy consumption and execution time overhead on real hardware to quantify the energy costs for dynamic linking. Our results suggest that while in general the overhead of a virtual machine is high, a combination of native code and virtual machine code provide good energy efficiency. Dynamic run-time linking can be used to update the native code, even in heterogeneous networks.

In this paper we present a method for experimental lifetime measurements of sensor networks. Despite the importance of experimental validation, none of the lifetime models proposed so far has been validated experimentally. One of the reasons for the absence of practical validations might be the long lifetime of batteries which make the validation of the proposed models non-trivial and time consuming. Our solution enables validation of lifetime models within a reasonable amount of time. We also use our method to validate a simple mathematical model that provides bounds on the lifetime of sensor networks.

Wireless sensor networks are composed of large numbers of tiny networked devices that communicate untethered. For large scale networks it is important to be able to dynamically download code into the network. In this paper we present Contiki, a lightweight operating system with support for dynamic loading and replacement of individual programs and services. Contiki is built around an event-driven kernel but provides optional preemptive multithreading that can be applied to individual processes. We show that dynamic loading and unloading is feasible in a resource constrained environment, while keeping the base system lightweight and compact.

Wireless sensor networks are based on the collaborative efforts of many small wireless sensor nodes, which collectively are able to form networks through which sensor information can be gathered. Such networks usually cannot operate in complete isolation, but must be connected to an external network to which monitoring and controlling entities are connected. As TCP/IP, the Internet protocol suite, has become the de-facto standard for large-scale networking, it is interesting to be able to connect sensornets to TCP/IP networks. In this paper, we discuss three different ways to connect sensor networks with TCP/IP networks: proxy architectures, DTN overlays, and TCP/IP for sensor networks. We conclude that the methods are in some senses orthogonal and that combinations are possible, but that TCP/IP for sensor networks currently has a number of issues that require further research before TCP/IP can be a viable protocol family for sensor networking.

The TCP/IP protocol suite, which has proven itself highly successful in wired networks, is often claimed to be unsuited for wireless micro-sensor networks. In this work, we question this conventional wisdom and present a number of mechanisms that are intended to enable the use of TCP/IP for wireless sensor networks: spatial IP address assignment, shared context header compression, application overlay routing, and distributed TCP caching (DTC). Sensor networks based on TCP/IP have the advantage of being able to directly communicate with an infrastructure consisting either of a wired IP network or of IP-based wireless technology such as GPRS. We have implemented parts of our mechanisms both in a simulator environment and on actual sensor nodes, and preliminary results are promising.

We describe two small and portable TCP/IP implementations fulfilling the subset of RFC1122 requirements needed for full host-to-host interoperability. Our TCP/IP implementations do not sacrifice any of TCP's mechanisms such as urgent data or congestion control. They support IP fragment reassembly and the number of multiple simultaneous connections is limited only by the available RAM. Despite being small and simple, our implementations do not require their peers to have complex, full-size stacks, but can communicate with peers running a similarly light-weight stack. The code size is on the order of 10 kilobytes and RAM usage can be configured to be as low as a few hundred bytes.

Wireless sensor networks are composed of large numbers-up to thousands-of tiny radio-equipped sensors. Every sensor has a small microprocessor with enough power to allow the sensors to autonomously form networks through which sensor information is gathered. Wireless sensor networks makes it possible to monitor places like nuclear disaster areas or volcano craters without requiring humans to be immediately present. Many wireless sensor network applications cannot be performed in isolation; the sensor network must somehow be connected to monitoring and controlling entities. This thesis investigates a novel approach for connecting sensor networks to existing networks: by using the TCP/IP protocol suite in the sensor network, the sensors can be directly connected to an outside network without the need for special proxy servers or protocol converters. Bringing TCP/IP to wireless sensor networks is a challenging task, however. First, because of their limited physical size and low cost, sensors are severely constrained in terms of memory and processing power. Traditionally, these constraints have been considered too limiting for a sensor to be able to use the TCP/IP protocols. In this thesis, I show that even tiny sensors can communicate using TCP/IP. Second, the harsh communication conditions make TCP/IP perform poorly in terms of both throughput and energy efficiency. With this thesis, I suggest a number of optimizations that are intended to increase the performance of TCP/IP for sensor networks. The results of the work presented in this thesis has had a significant impact on the embedded TCP/IP networking community. The software developed as part of the thesis has become widely known in the community. The software is mentioned in books on embedded systems and networking, is used in academic courses on embedded systems, is the focus of articles in professional magazines, is incorporated in embedded operating systems, and is used in a large number of embedded devices.

Over the last years, interest for connecting small devices such as sensors to an existing network infrastructure such as the global Internet has steadily increased. Such devices often has very limited CPU and memory resources and may not be able to run an instance of the TCP/IP protocol suite. In this thesis, techniques for reducing the resource usage in a TCP/IP implemen- tation is presented. A generic mechanism for o²oading the TCP/IP stack in a small device is described. The principle the mechanism is to move much of the resource demanding tasks from the client to an intermediate agent known as a proxy. In par- ticular, this pertains to the bu®ering needed by TCP. The proxy does not require any modi¯cations to TCP and may be used with any TCP/IP implementation. The proxy works at the transport level and keeps some of the end to end semantics of TCP. Apart from the proxy mechanism, a TCP/IP stack that is small enough in terms of dynamic memory usage and code footprint to be used in a minimal system has been developed. The TCP/IP stack does not require help from a proxy, but may be con¯gured to take advantage of a supporting proxy.

Sensornet protocols periodically broadcast beacons for neighborhood information advertisement, but beacon transmissions are costly when power-saving radio duty cycling mechanisms are used. We show that piggybacking multiple beacons in a single transmission significantly reduces transmission costs and argue that this shows the need for a new layer in the sensornet stackan announcement layerthat coordinates beacons across upper layer protocols. An announcement layer piggybacks beacons and coordinates their transmission so that the total number of transmissions is reduced. With an announcement layer, new or mobile nodes can quickly gather announcement information from all neighbors and all protocols by issuing an announcement pull operation. Likewise, protocols can quickly disseminate new announcement information to all neighbors by issuing an announcement push operation. We have implemented an announcement layer in the Contiki operating system and three data collection and dissemination protocols on top of the announcement layer. We show that beacon coordination both improves protocol performance and reduces power consumption.

The open-source Contiki operating system brings IP, the Internet Protocol, to sensor networks through the uIP (micro Internet Protocol), uIPv6 protocol stacks and the SICSlowpan IPv6-over-802.15.4 adaptation layer.

The emerging application space for smart objects requires scalable and interoperable communication mechanisms that support future innovation as the application space grows. IP has proven itself a long-lived, stable, and highly scalable communication technology that supports both a wide range of applications, devices, and underlying communication technologies. The IP stack is lightweight and runs on tiny, battery operated embedded devices. IP therefore has all the qualities to make The Internet of Things a reality, connecting billions of communicating devices.

Being able to estimate the energy consumption of sensor nodes is essential both for evaluating existing sensor network mechanisms and for constructing new energy-aware mechanisms. We present a software-based mechanism for estimating the energy consumption of sensor node at run-time. Unlike previous energy estimation mechanisms, our mechanism does not require any additional hardware components or add-ons. Our demonstration shows the energy estimation in practice on a small network of Tmote Sky motes running the Contiki operating system. A PC connected to one of the motes shows the real-time energy estimation of the network nodes and where the energy is spent: CPU active, CPU sleeping, radio transmitting, radio listening, and LEDs

As sensor networks move towards increasing heterogeneity, the number of link lay ers, MAC protocols, and underlying transportation mechanisms increases. System developers must adapt their applications and systems to accommodate a wid e range of underlying protocols and mechanisms. However, existing communication architectures for sensor networks are not design ed for this heterogeneity and therefore the system developer must redevelop thei r systems for each underlying communication protocol or mechanism. To remedy this situation, we present a communication architecture that adapts to a wide range of underlying communication mechanisms, from the MAC layer to the transport layer, without requiring any changes to applications or protocols. We show that the architecture is expressive enough to accommodate typical sensor network protocols. Measurements show that the increase in execution time over a non-adaptive archit ecture is small.

Event-driven programming is a popular model for writing programs for tiny embedded systems and sensor network nodes. While event-driven programming can keep the memory overhead down, it enforces a state machine programming style which makes many programs difficult to write, maintain, and debug. We present a novel programming abstraction called protothreads that makes it possible to write event-driven programs in a thread-like style, with a memory overhead of only two bytes per protothread. We show that protothreads significantly reduce the complexity of a number of widely used programs previously written with event-driven state machines. For the examined programs the majority of the state machines could be entirely removed. In the other cases the number of states and transitions was drastically decreased. With protothreads the number of lines of code was reduced by one third. The execution time overhead of protothreads is on the order of a few processor cycles.

From experience with wireless sensor networks it has become apparent that dynamic reprogramming of the sensor nodes is a useful feature. The resource constraints in terms of energy, memory, and processing power make sensor network reprogramming a challenging task. Many different mechanisms for reprogramming sensor nodes have been developed ranging from full image replacement to virtual machines. We have implemented an in-situ run-time dynamic linker and loader that use the standard ELF object file format. We show that run-time dynamic linking is an effective method for reprogramming even resource constrained wireless sensor nodes. To evaluate our dynamic linking mechanism we have implemented an application-specific virtual machine and a Java virtual machine and compare the energy cost of the different linking and execution models. We measure the energy consumption and execution time overhead on real hardware to quantify the energy costs for dynamic linking. Our results suggest that while in general the overhead of a virtual machine is high, a combination of native code and virtual machine code provide good energy efficiency. Dynamic run-time linking can be used to update the native code, even in heterogeneous networks.

With sensor networks starting to get mainstream acceptance, programmability is of increasing importance. Customers and field engineers will need to reprogram existing deployments and software developers will need to test and debug software in network testbeds. Script languages, which are a popular mechanism for reprogramming in general-purpose computing, have not been considered for wireless sensor networks because of the perceived overhead of interpreting a script language on tiny sensor nodes. In this paper we show that a structured script language is both feasible and efficient for programming tiny sensor nodes. We present a structured script language, SCript, and develop an interpreter for the language. To reduce program distribution energy the SCript interpreter stores a tokenized representation of the scripts which is distributed through the wireless network. The ROM and RAM footprint of the interpreter is similar to that of existing virtual machines for sensor networks. We show that the interpretation overhead of our language is on par with that of existing virtual machines. Thus script languages, previously considered as too expensive for tiny sensor nodes, are a viable alternative to virtual machines.

Protothreads are a extremely lightweight, stackless threads designed for use in severely memory constrained systems such as embedded systems. Software for memory constrained embedded systems sometimes are based on an event-driven model rather than on multi-threading. While event-driven systems allow for reduced memory usage, they require programs to be developed as explicit state machines. Since implementing programs as explicit state machines is hard, developing, maintaining, and debugging programs for event-driven systems is difficult. Protothreads simplify implementation of high-level functionality on top of event-driven systems, without significantly increasing the memory requirements. Protothreads can be implemented in in the C programming language using 10 lines of code and 2 bytes of RAM per protothread.

In this paper we present a method for experimental lifetime measurements of sensor networks. Despite the importance of experimental validation, none of the lifetime models proposed so far has been validated experimentally. One of the reasons for the absence of practical validations might be the long lifetime of batteries which make the validation of the proposed models non-trivial and time consuming. Our solution enables validation of lifetime models within a reasonable amount of time. We also use our method to validate a simple mathematical model that provides bounds on the lifetime of sensor networks.

Wireless sensor networks are composed of large numbers of tiny networked devices that communicate untethered. For large scale networks it is important to be able to dynamically download code into the network. In this paper we present Contiki, a lightweight operating system with support for dynamic loading and replacement of individual programs and services. Contiki is built around an event-driven kernel but provides optional preemptive multithreading that can be applied to individual processes. We show that dynamic loading and unloading is feasible in a resource constrained environment, while keeping the base system lightweight and compact.

We present an experimental deployment of an IPbased wireless sensor network that is intended to operate as an intrusion monitoring system. This network is the rst actual deployment of a fully IP-based wireless sensor network with small and computationally constrained sensor nodes. The intrusion monitoring system detects motion in a building which should be empty. The detected events are transmitted to an external monitoring entity, as well as logged inside the network. The logged events are distributed throughout the network and can be collected with a PDA inside the monitored building. We have also learned that the software development process is very time consuming unless support for over-the-air reprogramming is implemented, and that the unpredictability of radio conditions make sensor node placement hard.

This paper describes a prototype sensor networking platform and its associated development environment. Key elements of the system are the ESB sensor hardware, the Contiki operating system, and the communication stack, which includes a MAC layer and a highly optimized TCP/IP. Because the work is driven by prototype applications being developed by project partners, particular attention is paid to the development environment and to practical deployment issues. Three prototype applications are also presented.

Many applications of wireless sensor networks are useful only when connected to an external network. Previous research on transport layer protocols for sensor networks has focused on designing protocols speci cally targeted for sensor networks. The deployment of TCP/IP in sensor networks would, however, enable direct connection between the sensor network and external TCP/IP networks. In this paper we focus on the performance of TCP in the context of wireless sensor networks. TCP is known to exhibit poor performance in wireless environments, both in terms of throughput and energy ef ciency. To overcome these problems we introduce a mechanism called Distributed TCP Caching (DTC). The DTC mechanism uses segment caching and local retransmissions to avoid expensive end-to-end retransmissions.We show by simulation that DTC signi cantly improves TCP performance so that TCP can be useful even in wireless sensor networks.

Wireless sensor networks enable numerous advanced monitoring and control applications. In this project scientists at SICS are connecting sensor networks with the Internet.

Energy is one of the most important resources in wireless sensor networks. We use an idealized mathematical model to study the impact of routing on energy consumption. We find explicit bounds on the minimal and maximal energy routings will consume, and use them to bound the lifetime of the network. The bounds are sharp and can be achieved in many situations of interest. Our results apply to sensor networks with a continuous data delivery model, in which all sensors transmit with the same power. Within this class, the results are very general as they apply to arbitrary topologies, routings and radio energy models. We illustrate the theory with some examples. Among these, there is one contradicting the popular belief that it is always the nodes deployed nearest to base nodes that are the most heavily loaded and, hence, the ones that die first.

Wireless sensor networks are based on the collaborative efforts of many small wireless sensor nodes, which collectively are able to form networks through which sensor information can be gathered. Such networks usually cannot operate in complete isolation, but must be connected to an external network to which monitoring and controlling entities are connected. As TCP/IP, the Internet protocol suite, has become the de-facto standard for large-scale networking, it is interesting to be able to connect sensornets to TCP/IP networks. In this paper, we discuss three different ways to connect sensor networks with TCP/IP networks: proxy architectures, DTN overlays, and TCP/IP for sensor networks. We conclude that the methods are in some senses orthogonal and that combinations are possible, but that TCP/IP for sensor networks currently has a number of issues that require further research before TCP/IP can be a viable protocol family for sensor networking.

The TCP/IP protocol suite, which has proven itself highly successful in wired networks, is often claimed to be unsuited for wireless micro-sensor networks. In this work, we question this conventional wisdom and present a number of mechanisms that are intended to enable the use of TCP/IP for wireless sensor networks: spatial IP address assignment, shared context header compression, application overlay routing, and distributed TCP caching (DTC). Sensor networks based on TCP/IP have the advantage of being able to directly communicate with an infrastructure consisting either of a wired IP network or of IP-based wireless technology such as GPRS. We have implemented parts of our mechanisms both in a simulator environment and on actual sensor nodes, and preliminary results are promising.

We describe two small and portable TCP/IP implementations fulfilling the subset of RFC1122 requirements needed for full host-to-host interoperability. Our TCP/IP implementations do not sacrifice any of TCP's mechanisms such as urgent data or congestion control. They support IP fragment reassembly and the number of multiple simultaneous connections is limited only by the available RAM. Despite being small and simple, our implementations do not require their peers to have complex, full-size stacks, but can communicate with peers running a similarly light-weight stack. The code size is on the order of 10 kilobytes and RAM usage can be configured to be as low as a few hundred bytes.

In contrast with work focusing on routing problems in mobile ad hoc networks, this work addresses the problem of system configuration in such networks. In particular, we are interested in ways to instantiate the configuration infrastructure - naming, addressing, authentication, and key distribution - needed to establish small-to-medium scale ad hoc networks supporting collaborative applications. We argue that, in such spontaneous networks,much of the necessary infrastructure can be derived from the face-to-face human interactions that these networks are intended to facilitate. This approach has the additional advantage of being intuitive for the non-expert user.