RANC: Relay-aided network coding in multi-hop wireless networks

This paper proposes a relay-aided network coding (RANC) scheme that considers how to improve the performance gain of network coding by exploiting the physical layer multi-rate capability in multi-hop wireless networks. In RANC, nodes are allowed to transmit at different rates according to the channel condition. Different from the recently proposed opportunistic overhearing and coding schemes by COPE [S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, XORs in the air: practical wireless network coding, in: Proc. of ACM SIGCOMM’06, September 2006.], each node may either send its own packet or relay the packets received from its neighbors in form of a coded packet. Since the relayed packets can usually be transmitted at a high rate, the total packets that are necessary for decoding can be delivered to each destination node much faster than direct transmissions. We conduct rigorous analysis to find the design principles and study the tradeoff in the performance gain of RANC. Based on the analytical results, we provide a practical solution by decomposing the original design problem into two sub-problems, which are the flow partition problem and the scheduling problem. The performance of RANC is also evaluated via simulations. The simulation results show that, compared to COPE, RANC can significantly improve the performance gain of network coding.