On the Delay and Throughput of Digital and Analog Network Coding for Wireless Broadcast

Abstract — We address the problem of exchanging broadcast packets among multiple wireless terminals through a single relay node. The objective is to evaluate the delay and throughput gains of network coding over plain routing. We compare digital network coding at the packet level with analog network coding based on scheduled or random access of terminal transmissions that are forwarded by the relay node. For error-free channels, the performance gain of both types of network coding scales with the number of terminals, if they can overhear each other’s transmissions. For channels with noise or packet erasures, we formulate network coding as a multiuser communication problem. The multi-dimensional performance measures involve the packet delay, the throughput rate and the probability of decoding error or decoding failure that are optimized either by plain routing, digital or analog network coding depending on the number of terminals and channel properties. Our results open up new questions regarding the use of wireless network coding and illustrate the delay, throughput and reliability trade-offs. I