Five Significant Publications

[5] Rajesh Krishna Panta, Saurabh Bagchi, and Samuel P. Midkiff, “Zephyr: Efficient Incremental Reprogramming of Sensor Nodes using Function Call Indirections and Difference Computation,” At the USENIX Annual Technical Conference (USENIX '09), June 14-19, 2009, pp. 411-424, San Diego, CA. (Acceptance rate: 32/191 = 16.8%)

[ Paper in pdf ]

Problem Statement: Wireless reprogramming of embedded wireless networks is an essential requirement for long-lived networks since the software functionality changes over time. The amount of information that needs to be wirelessly transmitted during reprogramming should be minimized since reprogramming time and energy depend chiefly on the amount of radio transmissions. In practice, software running on a node evolves, with incremental changes to functionality, or modification of the parameters that control current functionality. Thus the difference between the currently executing code and the new code is often much smaller than the entire code. This makes incremental reprogramming attractive because only the changes to the code need to be transmitted and the entire code can be reassembled at the node from the existing code and the received changes. The goal of incremental reprogramming is to transfer a small delta (difference between the old and the new software) so that reprogramming time and energy can be minimized. However, incremental programming was considered challenging for the target class of wireless networks because of limited support for dynamic linking or position independent code.

Contribution of Paper: In this paper, we presented a multi-hop incremental reprogramming protocol called Zephyr that transfers the delta between the old and the new software and lets the wireless nodes rebuild the new software using the received delta and the old software. It reduces the delta size by using application-level modifications to mitigate the effects of function shifts. Then it compares the binary images at the byte-level with a novel method to create small delta, that is then sent over the wireless network to all the nodes. For a wide range of software change cases that we experimented with, we find that Zephyr transfers 1.83 to 1987 times less traffic through the network than Deluge, the standard reprogramming protocol for TinyOS, and 1.14 to 49 times less than an existing incremental reprogramming protocol by Jeong and Culler. This was thus the first practically realizable incremental reprogramming protocol for resource-constrained multi-hop wireless networks and remains to this date the most efficient such protocol. We were later awarded a US patent for the innovation described in this paper.