Minimum cost opportunistic routing with intra-session network coding

Opportunistic routing with intra-session network coding (NCOR) is a promising communication paradigm in wireless multi-hop networks with lossy links. Unlike traditional routing protocols, which use a single path to route traffic between node pairs, NCOR broadcasts data packets to a set of forwarding candidates. Each candidate combines the overheard packets to generate linearly independent packets, which are then forwarded to the destination. The focus of this paper is on the fundamental problem of how to select the candidate forwarder set (CFS) and how to allocate traffic among candidate forwarders to achieve optimal routing. In current literature, CFS selection and traffic allocation have typically been addressed separately. In this paper, we take an integrated approach and propose a minimum cost NCOR model, MIC-NCOR, which addresses the two aspects of the problem jointly. Based on the optimal substructure of MIC-NCOR, we derive a provable algorithm that can be implemented in a distributed fashion, to compute both the optimal CFS and traffic portion for each candidate. An extensive simulation study indicates that MIC-NCOR accurately predicts the quality of NCOR routes. The simulation results also show that the MIC-NCOR algorithm achieves significant throughput improvement over existing NCOR routing schemes, especially in networks with low NCOR cost and high node density.