The erasure resilience of rateless codes, such as Luby-Transform (LT) codes, makes them particularly suitable to a wide variety of loss-prone wireless and sensor network applications, ranging from digital video broadcast to software updates. Yet, traditional rateless codes usually make no use of a feedback communication channel, a feature available in many wireless settings. As such, we generalize LT codes to situations where receiver(s) provide feedback to the broadcaster. Our approach, referred to as Shifted LT (SLT) code, modifies the robust soliton distribution of LT codes at the broadcaster, based on the number of input symbols already decoded at the receivers. While implementing this modification entails little change to the LT encoder and decoder, we show both analytically and through real experiments, that it achieves significant savings in communication complexity, memory usage, and overall energy consumption. Furthermore, we show that significant savings can be even achieved with a low number of feedback messages (on the order of the square root of the total number of input symbols) transmitted at a uniform rate. The practical benefits of Shifted LT codes are demonstrated through the implementation of a real over-the-air programming application for sensor networks, based on the Deluge protocol.

Over-the-air programming (OAP) is a fundamental service in sensor networks that relies upon reliable broadcast for efficient dissemination. As such, existing OAP protocols become decidedly inefficient (with respect to energy, communication or delay) in unreliable broadcast environments, such as those with relatively high node density or noise. In this paper, we consider OAP approaches based on rateless codes, which significantly improve OAP in such environments by drastically reducing the need for packet rebroadcasting. We thus design and implement two rateless OAP protocols, rateless Deluge and ACKless Deluge, both of which replace the data transfer mechanism of the established OAP Deluge protocol with rateless analogs. Experiments with Tmote Sky motes on single-hop networks with packet loss rates of 7% show these protocols to save significantly in communication over regular Deluge (roughly 15-30% savings in the data plane, and 50-80% in the control plane), and multi-hop experiments reveal similar trends. Simulations further shows that our new protocols scale better than standard Deluge (in terms of communication and energy) to high network density. TinyOS code for our implementation can be found at http://nislab.bu.edu.

We consider the problem of efficiently broadcasting incremental updates to multiple terminals that contain outdated (and possibly different) initial copies of the data. This situation occurs, for example, with the broadcast of Short Messaging Service [SMS] or Multimedia Messaging Service [MMS] cellphone messages to various clients whose phones are sometimes unavailable. We propose an efficient protocol for effecting such broadcast based on a novel combination of recent work on rate less coding and set reconciliation. Our approach is non-interactive, in that terminal nodes need not send any messages to the source, and stateless, in that the source need not know (or store) any information about the terminals. It also minimizes communication complexity and energy expenditure at the terminal nodes, at the expense of added computation. In support of our work, we provide several energy usage measurements on MICA2 sensor motes that clearly highlight the advantages of random linear decoding over wholesale data transfer.

This paper discusses the use of rateless codes to increase performance in wireless sensor networks.