Contention resolution on a fading channel
Contention resolution on a fading channel
复制标题
DOI：
10.1007/s00446-018-0323-9
复制
发表时间：
2016-07
影响因子：
1.3
通讯作者：
Jeremy T. Fineman;Seth Gilbert;F. Kuhn;Calvin C. Newport
中科院分区：
文献类型：
--
作者：
Jeremy T. Fineman;Seth Gilbert;F. Kuhn;Calvin C. Newport
在本文中，我们研究了上界和下界的竞争解决单跳衰落信道，即，其中接收行为由信号干扰噪声比（SINR）等式确定的信道。以前最著名的解决方案解决了这个问题，在O（log2nlog logn）轮，在系统大小n的概率很高。我们描述和分析的算法，解决了问题，在O（logn+ logR）轮，其中R是最长和最短的链接之间的比率，是一个值上限的多项式在n最可行的部署。我们用一个Ω（logn）下界来补充这个结果，证明了对于合理的R，这个下界是紧的。我们注意到，在经典的无线电网络模型（不包括信号衰落）中，高概率竞争解决需要Ω（log2n）轮。因此，我们的算法，肯定的猜想，即衰落使频谱重用应该允许分布式算法，以实现显着改善这个log2nspeed限制。此外，我们认为，新的技术需要证明我们的上限和下限是一般用于分析其他分布式算法，在这个日益深入研究的衰落信道设置。
In this paper, we study upper and lower bounds for contention resolution on a single hop fading channel; i.e., a channel where receive behavior is determined by a signal to interference and noise ratio (SINR) equation. The best known previous solution solves the problem in this setting inO(log2nlog logn) rounds, with high probability in the system size n. We describe and analyze an algorithm that solves the problem inO(logn+ logR) rounds, whereRis the ratio between the longest and shortest link, and is a value upper bounded by a polynomial in n for most feasible deployments. We complement this result with an Ω(logn) lower bound that proves the bound tight for reasonable R. We note that in the classical radio network model (which does not include signal fading), high probability contention resolution requires Ω(log2n) rounds. Our algorithm, therefore, affirms the conjecture that the spectrum reuse enabled by fading should allow distributed algorithms to achieve a significant improvement on this log2nspeed limit. In addition, we argue that the new techniques required to prove our upper and lower bounds are of general use for analyzing other distributed algorithms in this increasingly well-studied fading channel setting.