We present a holistic reprogramming system called R3. R3 has two salient features. First, the binary differencing algorithm within R3 (R3diff) ensures an optimal result in terms of the delta size under a configurable cost measure. Second, the similarity preserving method within R3 (R3sim) optimizes the binary code format for achieving a large similarity with a small metadata overhead. Overall, R3 achieves the smallest delta size compared to other incremental approaches such as Rsync [11], RMTD [9], Zephyr/Hermes [17], [18], and R2 [2], e.g., 50%–99% reduction compared to Stream and about 20%–40% reduction compared to R2. R3's implementation on TelosB/TinyOS is lightweight and efficient. We release our code at http://code.google.com/p/r3-dongw.

Wireless reprogramming is a crucial technique for managing large-scale wireless sensor networks (WSNs). It is, however, energy intensive to disseminate the code to enable reprogramming. Incremental reprogramming is a promising approach to reduce the dissemination cost. In incremental reprogramming, only the delta between the new code and the old code needs to be disseminated, resulting much less energy consumption. The differencing algorithm plays a key role in incremental reprogramming. It takes inputs of two successive versions of codes and generates a small delta script for dissemination. Existing incremental algorithms have several limitations. First, they do not ensure the smallest delta size for dissemination. Second, some of them may incur a large overhead in terms of execution time and memory consumption. To address these issues, we propose DASA, an efficient differencing algorithm based on suffix array. DASA performs byte-level comparison and ensure the optimal result in terms of the delta size. Moreover, DASA has a low execution overhead. The time complexity and space complexity of DASA are O(n log n) and O(n), respectively. To the best of our knowledge, DASA is the optimal algorithm with the lowest time and space complexity for reprogramming WSNs.