R3: Optimizing relocatable code for efficient reprogramming in networked embedded systems

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.