Rateless Deluge

Abstract:

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 (in terms of communication and energy) to high network density.

Full Paper:

Read the paper from IPSN 2008, here.

Implementation:

Implementation of Rateless Deluge, which uses Random Linear Codes for the transfer of program images. Code developed for Tmote Sky motes.

To configure the java tools to work with Rateless Deluge do the following:

1. Copy all the rateless *.h files to TOS/lib/Deluge/ for tinyos-1.x and moteiv.

2. In directory .../java/net/tinyos/deluge/, first "make clean" and then "make"

3. In directory .../java/net/tinyos/tools/, first "make clean" and then "make"

Note that if you change the constants you will need to repeat the process so that the changes are reflected in the java tools.