Overcoming Unreliable Radios in Sensor Networks with Network Coding

D. Petrović, K. Ramchandran, J. Rabaey

IEEE Workshop on Network Coding, Theory and Applications (NetCod) 2005

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultra-low-cost and low-power nodes. While the digital subsystems of the nodes are still riding Moore's Law, there is no such trend regarding the performance of analog components. This work presents a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size and power consumption of the overall node. While such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e.

This work makes use of known results from network coding theory that show that throughput equal to the max-flow in a graph is achievable. However, the challenge here is finding the max-flow of the random graph corresponding to the network.