OVERVIEW

The nature of sensor networks dictates that, once deployed, they are expected to operate for a prolonged period of time and often without any human intervention. In several deployment scenarios, physically reaching all nodes is either impractical (e.g., nodes on treetops) or detrimental to the sensing process (e.g., nodes inside nests). On the other hand, there is a real need to add or upgrade the software running on the nodes, post deployment. We have developed MOAP (Multihop Over the Air Programming). MOAP is useful to both sensor network users and researchers.

Users need over-the-air programming to:

• Add new functionality to existing code
• Facilitate runtime debugging
• Extend the usefulness of the network
• Program nodes that are not physically reached
• Automate the process to support large network sizes

Over-The-Air Programming is also useful to researchers:

• It is a special case of data dissemination. It must transfer a large volume of data and must reach all nodes in the network
• It has strict reliability requirements. Everything must be received
• It must operate with limited resources, like low-power radios, limited memory and storage
• It helps explore sensor net design space for reliable communications

APPROACHes

Since the target platform is the Crossbow Mote, our approach is customized for this specific platform. The three main aspects of the design are:

• Dissemination protocol: There are two main approaches to the question of data propagation. The first is to send the data to all nodes concurrently, using a dissemination mechanism like flooding. The second approach is to transfer the data in a neighborhood-by-neighborhood basis. At each neighborhood, only a small subset of the nodes is the ‘source’ while the rest are the receivers. When the receivers have the entire image, they can become potential sources themselves for their own neighborhoods. A publish-subscribe interface is used to prevent nodes from becoming sources if there are no receivers that require the code update. Using this method, one hopes to leverage the nature of the broadcast medium, where only one transmission can reach all nodes within range (in the absence of losses). Compared to flooding, this mechanism, which we call Ripple, achieves a significant reduction in energy consumption (by limiting transmissions) but at the cost of increased latency.
• Reliability mechanism: In code distribution, we cannot afford to lose any data. We consider three aspects of the reliability question: loss detection responsibility (sender or receiver), scope of repairs (local or global) and retransmission policy. Since we are trying to optimize our system for low energy consumption, a NACK-based approach is a suitable choice. Therefore loss detection is done at the receivers which then request a retransmission from the sender(s). The choice of the neighborhood-by-neighborhood dissemination protocol means that our repairs are local (a single hop away). This provides a considerable reduction in complexity and energy consumption, since both requests and replies don’t need to be routed through a long multihop path. The cost again is latency.
• Segment management: The last question is how to organize the segments of the code image in order to find which of them are missing. The goal is again energy optimization as well as RAM usage. There are two main options that we consider. The first is to treat RAM+EEPROM as a memory hierarchy and apply different memory management schemes (optimized for reads, writes or both). The other option is to use a sliding-window method, where a receiver only keeps track of the last few segments. Segments before the beginning of the window have been successfully received in order. Segments inside the window can be received out of order and the node can then ask for a retransmission. This method, unlike the memory hierarchy one, does not involve any EEPROM I/O (which is expensive in terms of energy). However, its out-of-order tolerance is limited to the size of the window.

SYSTEMS / EXPERIMENTS

Using the approaches presented in the previous section, we have implemented MOAP on the Crossbow MICA2 platform. In its current instantiation, MOAP needs 700 bytes of RAM and 4.5Kbytes of program memory. It has been successfully used to repeatedly reprogram motes up to four hops away from the basestation, using code images of various sizes, ranging from 600 up to 30K bytes.

As Figure 1 shows, the energy savings of using the Ripple dissemination protocol are quite considerable (up to 70%) as opposed to flooding. In addition the difference between the sliding window method and the full indexing (memory hierarchy) one are not substantial. The penalty for the substantial energy savings is, as noted, latency. This is shown in Figure 2.

ACCOMPLISHMENTS

One technical report publication as shown on the publications list

FUTURE DIRECTIONS

• Sending differences between versions. Currently MOAP sends the entire image when a new version is found. By sending only the differences between versions, we can hope to achieve even further reductions in energy usage.
• Support for selective node updates. The current version updates every node in the network to the same image. However, this isn’t always desirable. We are in the process of identifying the pieces of the dissemination protocol and the reliability mechanism that will need to be modified in order to make this possible.
• Adding a verification mechanism to the system. A verification mechanism is needed to discover whether the update operation has completed. Besides the simple solution which is to flood information back to the basestation, we are interested in exploring other, more energy-saving options.
• Deploying MOAP. We are currently deploying MOAP at the 60-mote ISI testbed, as part of the ‘Followme’ application. In the future, we are planning to use MOAP to reprogram even larger systems, such as the Extensible Sensing System at James Reserve.
• Creating a ‘lightweight’ version of MOAP. For ‘small’ deployments, where the distance from any mote to a microserver isn’t greater than 3-4 hops, we can trade off scalability for memory usage, by having only a single source (the microserver). The ‘lightweight’ version is currently in the early design phase

PEOPLE

Faculty:

Prof. Deborah Estrin
Dr. John Heidemann

Graduate Students:

Thanos Stathopoulos