Broadcasting in Noisy Radio Networks
Broadcasting in Noisy Radio Networks
复制标题
在嘈杂的无线电网络中广播
DOI：
10.1145/3087801.3087808
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Zuzic, Goran
中科院分区：
文献类型：
--
作者：
Censor-Hillel, Keren;Haeupler, Bernhard;Hershkowitz, D. Ellis;Zuzic, Goran
被广泛研究的无线电网络模型[Chlamtac和Kutten，1985]是一种基于图形的描述，它捕获了无线通信中冲突的固有影响。在这个模型中，强烈的假设是，节点v接收到来自邻居的消息，当且仅当恰好是它的邻居之一广播。我们放宽这一假设，通过引入一个新的嘈杂的无线电网络模型，随机故障发生在接收机或。具体地说，对于一个常数噪声参数p ∈ [0，1），要么每个发送者都有概率p发送噪声，要么每个接收者都有概率p接收噪声。我们首先研究了噪声无线电网络中的单消息广播算法，并证明了衰减算法[Bar-Yehuda et al.，1992]在噪声模型中保持鲁棒性，而Gasieniec等人的直径线性算法，2007年没有。我们给出了Gasieniec等人的算法的修改版本，2007提出的算法对发送端和接收端的故障具有鲁棒性，并将该算法和Decay算法扩展到鲁棒的多消息广播算法，每轮分别广播Ω（1/log n log log n）和Ω（1/log n）条消息。特别是，我们研究了编码帽-编码的路由的吞吐量的比率-在嘈杂的无线电网络。我们解决了Alon等人2014年之前令人困惑的结果，即最坏情况下的编码吞吐量并不比最坏情况下的路由吞吐量更好，直到常数：我们表明，编码的最坏情况吞吐量性能实际上上级路由-通过Θ（log（n））间隙-提供接收器故障。然而，我们发现发送方故障对吞吐量的影响很小。特别是，我们表明，任何编码或路由方案的无噪声设置可以被转换为强大的发送方故障，只有一个恒定的吞吐量开销。这些变换意味着Alon等人的结果，2014年结转到嘈杂的无线电网络与发送器故障以及。因此，如果引入发送器故障，则存在0（log log n）间隙的拓扑，但是对于编码和路由，所有拓扑的最差情况吞吐量都是0（1/log n）。
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 newnoisy radio network modelin 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 studysingle-message broadcastalgorithms 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 sender and receiver faults, and extend both this modified algorithm and the Decay algorithm to robustmulti-message broadcastalgorithms, 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 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 Θ(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 Alon et al., 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.
登录
查看更多内容
DOI：
10.1109/sfcs.2005.48
发表时间：
2005
期刊：
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
影响因子：
--
作者：
Navin Goyal;Guy Kindler;Michael E. Saks
通讯作者：
Michael E. Saks
噪声无线电网络中的计算
DOI：
10.1137/s0895480103434063
发表时间：
2005
期刊：
ArXiv
影响因子：
--
作者：
E. Kushilevitz;Y. Mansour
通讯作者：
Y. Mansour
无线电网络中的高效广播：回顾
DOI：
--
发表时间：
2007
期刊：
International Conference on Distributed Computing and Internet Technology
影响因子：
--
作者：
D. Peleg
通讯作者：
D. Peleg
DOI：
--
发表时间：
2011
期刊：
Theory of Randomized Search Heuristics
影响因子：
--
作者：
Benjamin Doerr
通讯作者：
Benjamin Doerr
DOI：
10.1109/ccc.2004.1313813
发表时间：
2004
期刊：
Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004.
影响因子：
--
作者：
I. Newman
通讯作者：
I. Newman