Universal opportunistic routing scheme using network coding

Recent research has shown that the performance of opportunistic routing and network coding in wireless networks is greatly impacted by the correlation among the links. However, it is difficult to measure the correlation among the links, especially because of the time-varying behavior of the wireless links. Therefore, it is crucial to design a distributed algorithm that does not require the explicit knowledge of the channels' states and can adapt to the varying channel conditions. In this paper, we formulate the problem of maximizing the throughput while achieving fairness under arbitrary channel conditions, and we identify the structure of its optimal solution. As is typical in the literature, the optimal solution requires a large amount of immediate feedback messages, which is unrealistic. We propose the idea of performing network coding on the feedback messages and show that if the intermediate node waits until receiving only one feedback message from each next-hop node, the optimal level of network coding redundancy can be computed in a distributed manner. The coded feedback messages require a small amount of overhead as they can be integrated with the packets. Our approach is also oblivious to losses and correlations among the links as it optimizes the performance without the explicit knowledge of these two factors.