Broadcasting in Noisy Radio Networks
March 29, 2017
The widely-studied classic radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this model a message is received by a node v if and only exactly one of its neighbors broadcasts. However, this is a strong assumption of guaranteed message delivery.
We relax this assumption by introducing a new noisy radio network model in which random faults occur at senders and receivers. Specifically, for a given noise parameter p in [0,1), any sender has a probability of p of transmitting noise or any receiver of a single transmission in its neighborhood has a probability p of receiving noise.
We first study single-message broadcast algorithms in noisy radio networks and show that the Decay algorithm [Bar-Yehuda et al., 1992] remains robust in the noisy model, while the diameter-linear algorithm of~[Gasieniec et al., 2007] does not. We give a modified version of the algorithm of~[Gasieniec et al., 2007] that is robust to faults, and extend both this modified algorithm and the Decay algorithm to robust multi-message broadcast algorithms, broadcasting Omega(1 / (log n loglog n)) and Omega(1/ log n) messages per round, respectively.
We next investigate the extent to which (network) coding improves throughput in noisy radio networks. In particular, we study the coding cap -- the ratio of the throughput of coding to that of routing -- in noisy radio networks. We address the previously perplexing result of [Alon~et~al.~2014] that worst case coding throughput is no better than worst case routing throughput up to constants: we show that the worst case throughput performance of coding is, in fact, superior to that of routing -- by a Theta(log n) gap -- provided receiver faults are introduced. However, we show that sender faults have little effect on throughput. In particular, we show that any coding or routing scheme for the noiseless setting can be transformed to be robust to noise at senders with only a constant throughput overhead. These transformations imply that the results of [Alon et al., 2014] carry over to noise at senders as well. As a result, if sender faults are introduced then there exist topologies for which there is a Theta(loglog n) gap, but the worst case throughput across all topologies is Theta(1 / log n) for both coding and routing.