The widely-studied 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, the strong assumption is made that node v receives a message from a neighbor if and only if exactly one of its neighbors broadcasts. We relax this assumption by introducing a new noisy radio network model in which random faults occur at senders or receivers. Specifically, for a constant noise parameter p ∈ [0,1), either every sender has probability p of transmitting noise or every receiver of a single transmission in its neighborhood has probability p of receiving noise. We first study single-message broadcast algorithms in noisy radio networks and show that the Decay algorithm [Bar-, 1992] remains robust in the noisy model while the diameter-linear algorithm of , 2007 does not. We give a modified version of the algorithm of , 2007 that is robust to sender and receiver faults, and extend both this modified algorithm and the Decay algorithm to robust multi-message broadcast algorithms, broadcasting Ω(1 log n log log n) and Ω(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 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 Θ(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 sender faults with only a constant throughput overhead. These transformations imply that the results of , 2014 carry over to noisy radio networks with sender faults as well. As a result, if sender faults are introduced then there exist topologies for which there is a Θ(log log n) gap, but the worst case throughput across all topologies is Θ(1 log n) for both coding and routing.
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors, where a processor receives a message in a given step if and only if it is silent in this step and precisely one of its neighbors transmits. In this paper we prove the existence of a family of radius-2 networks on n vertices for which any broadcast schedule requires at least Omega((log n log log n)2) rounds of transmissions. This almost matches an upper bound of O(log2 n) rounds for networks of radius 2 proved earlier by Bar-Yehuda, Goldreich, and Itai. We consider distributed computation of functions of distributed data in random planar networks with noisy wireless links. We present a new algorithm for computation of the maximum value which is order optimal in the number of transmissions and computation time. We also adapt the histogram computation algorithm of [1] to make the histogram computation time optimal. We consider a wireless sensor network consisting of n sensors, each having a recorded bit, the sensor’s measurement, which has been set to either “0” or “1”. The network has a special node called the fusion center whose goal is to compute a symmetric function of these bits; i.e., a function that depends only on the number of sensors that have a “1.” The sensors convey information to the fusion center in a multi-hop fashion to enable the function computation. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint that this computation is correct with high probability. We assume the wireless channels are binary symmetric channels with a probability of error p, and that each sensor uses rαunits of energy to transmit each bit, where r is the transmission range of the sensor. The main result in this paper is an algorithm whose energy usage is Θ (n(loglogn)(√logn n)α), and we also show that any algorithm satisfying the performance constraints must necessarily have energy usage Ω (n(√logn n)α). Then, we consider the case where the sensor network observes N events, and each node records one bit per event, thus having N bits to convey. The fusion center now wants to compute N symmetric functions, one for each of the events. We show a tight lower bound of Omega(N N) on the number of transmissions required to compute several functions (including the parity function and the majority function) in a network of N randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. This result considerably simplifies and strengthens an earlier result of Dutta, Kanoria Manjunath and Radhakrishnan (SODA 08) that such networks cannot compute the parity function reliably with significantly fewer than N N transmissions, thereby showing that the protocol with O(N N) transmissions due to Ying, Srikant and Dullerud (WiOpt 06) is optimal. We also observe that all the lower bounds shown by Evans and Pippenger (SIAM J. on Computing, 1999) on the average noisy decision tree complexity for several functions can be derived using our technique simply and in a unified way. A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(lnN)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication. >   