Low-complexity network coding algorithms for energy efficient information exchange

The use of network coding in wireless networks has been proposed in the literature for energy efficient broadcast. However, the decoding complexity of existing algorithms is too high for low-complexity devices. In this work we formalize the all-to-all information exchange problem and shows how to optimize the transmission scheme in terms of energy efficiency. Furthermore, we prove by construction that there exists O(1)-complexity network coding algorithms for grid networks which can achieve such op-timality. We also present low-complexity heuristics for random-topology networks. Simulation results show that network coding algorithms outperforms forwarding algorithms in most cases.