Towards optimal forwarding in wireless networks: Opportunistic routing meets network coding

In wireless networks, transmissions can generally be overheard by unintended nodes in the vicinity of the sender and receiver, potentially causing interference to their own communications. Much of the related research has considered this as a nuisance and resulted in various proposals for overcoming the interference using scheduling, channel assignment, and many other mechanisms. In recent years, there has been growing attention to methods that aim to take advantage of the broadcast nature of the wireless medium and the ability of nodes to overhear their neighbors´ transmissions. Two of the most important such methods are opportunistic routing (OR) and wireless network coding (NC), exemplified by the ExOR and COPE protocols, respectively. In this paper, we study the potential benefits (in terms of reducing transmissions) of forwarding schemes that combine elements from both the OR and NC approaches, when traffic on a bidirectional unicast connection between two nodes is relayed by multiple common neighbors. We present a dynamic programming algorithm to find the optimal scheme as a function of link error probabilities, and demonstrate that it can achieve up to 20% reduction in the number of transmissions compared to either OR or NC employed alone, even in a simple scenario of two common neighbors between the connection endpoints.