Throughput optimal control for relay-assisted wireless broadcast with network coding

We consider the problem of exchanging packets from the individual queues at multiple wireless terminals with the assistance of a single relay node. In an earlier paper, we studied this for a backlogged traffic model, where each node always had packets to transmit. Here, we consider stochastically varying packet traffic and compare the stable operation under plain routing, and digital and analog network coding. For each scheme, we specify the queue dynamics at the terminal and relay nodes, and evaluate the maximum throughput region optimized over all transmission schedules. We then give throughput optimal policies, which involve maximizing an appropriate differential backlog for each scheme. The analysis leads to the extension of the classical backpressure algorithms for plain routing to digital and analog network coding. Any achievable rates in the maximum throughput region can be stabilized by dynamic scheduling such that the average queue lengths are asymptotically bounded.