Throughput and stability of digital and analog network coding for wireless networks with single and multiple relays

We evaluate the throughput and stability properties of digital and analog network coding for wireless terminals exchanging broadcast traffic with the assistance of relay nodes. For stochastically varying traffic, the stable operation is compared under the different schemes of plain routing, and digital and analog network coding, at the packet and the signal levels, respectively. For each network coding scheme, the queue dynamics are specified for the terminal and relay nodes, and the maximum throughput region is optimized over all transmission schedules. We then give generalizations of the well-known back-pressure policy for each scheme, which accounts for the coupling of the queues due to network coding and is throughput optimal, i.e., it stabilizes the network whenever this is possible. Our initial analysis focuses on a network with a single relay node. We then discuss extensions of this to arbitrary terminal-relay configurations in a general multihop network. A general framework is established to construct the maximum throughput region and throughput optimal scheduling is jointly designed with network coding for relay networks with general channel rates. For any achievable rates in the maximum throughput region the dynamic scheduling and coding ensure that the average queue lengths at the terminal and relay nodes are asymptotically bounded.