Throughput and Stability for Relay-Assisted Wireless Broadcast with Network Coding

The throughput and stability properties of wireless network coding are evaluated for an arbitrary number of terminals exchanging broadcast traffic with the aid of a relay. First, coding and scheduling schemes are derived that minimize the number of transmissions needed for each node to broadcast one packet. For stochastically varying traffic, the stable throughput is then compared under both digital and analog network coding schemes. The initial analysis focuses on a network with a single relay. Extensions to arbitrary terminal-relay configurations are then outlined for a general multihop network. Backpressure-like algorithms for jointly achieving throughput optimal scheduling and network coding are given for each network coding scheme.