1Throughput Optimal Network Coding and Scheduling in Wireless Networks

Recently, network coding (NC) emerged as a promising technology for significantly improving throughput and energy efficiency of wireless networks, even for unicast communication. Often, NC schemes are designed as an autonomous layer, independent of the underlying Phy and MAC capabilities and algorithms. Consequently, these schemes are greedy, in the sense that all opportunities of broad-casting combinations of packets are exploited. We demonstrate that this greedy design principle may in fact reduce the network throughput. This begets the need for adaptive NC schemes. We further show that designing appropriate MAC scheduling algorithms is critical for achieving the throughput gains expected from NC. In this paper, we propose a general framework to develop optimal and adaptive joint NC and scheduling schemes. Optimality is shown for various Phy and MAC constraints. We apply this framework to two different NC architectures: COPE, a scheme recently proposed in [11], and XOR-Sym, a new scheme we present here. XOR-Sym is designed to achieve a lower implementation complexity than that of COPE, and yet to provide similar throughput gains. Index Terms Multi-hop wireless networks, network coding, throughput optimality I