A General Packet Coding Scheme for Multi-Hop Wireless Networks

Current implementations of multi-hop wireless networks suffer from a severe throughput limitation and do not scale well with an increasing number of nodes. A promising architecture COPE [12], which exploits the physical-layer broadcast property and network coding technique, was recently proposed to significantly improve the throughput of multi-hop wireless networks. In this paper, we will improve the packet coding scheme in COPE to further reduce the number of bytes transmitted by a network node for forwarding its incoming packets to the respective neighbors. We first propose a more general packet coding framework, which covers the one in COPE as a special case and can offer us more coding opportunities. We then formulate the optimal packet coding problem under this general coding framework as an integer programming problem, and prove that it is NP-complete. Finally, we present an efficient algorithm to find the optimal coding solution for the proposed general packet coding framework.