Decomposing broadcast algorithms using abstract MAC layers
Decomposing broadcast algorithms using abstract MAC layers
复制标题
使用抽象 MAC 层分解广播算法
DOI：
10.1145/1860684.1860690
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Khabbazian M
中科院分区：
文献类型：
--
作者：
Khabbazian M
在许多关于无线算法的理论文献中，消息传播的问题与争用管理的问题一起被考虑。这种结合导致复杂的算法和分析，并使其难以扩展到更难的通信问题的工作。在本文中，我们目前的一个项目，旨在简化这些算法和分析分解成两个层次的治疗，使用抽象的“MAC层”规范封装的争用管理的结果。我们使用两个不同的抽象MAC层：[14，15]的基本层和一个新的概率层。我们首先提出了一个标准的基于图的无线电网络模型的典型随机竞争管理算法，我们证明了它实现了两个抽象MAC层。我们将该算法与贪婪算法相结合，用于单消息和多消息全局广播，并分析了组合，使用两个抽象的MAC层作为中间层。利用基本的MAC层，我们证明了以1 - ∈的概率在任何地方传递单个消息的时间的界为O（Dlog（n/∈）log Δ），其中D是网络直径，n是节点数，Δ是最大节点度。使用概率层，我们证明了O（（D+ log（n/∈））log Δ）的一个界，该界与物理网络模型上单消息广播的最佳界相匹配。对于多消息广播，在最多k个并发消息的情况下，我们得到了在任意位置传递消息的时间的极限为O（（D + kΔ）log（n/∈）log Δ）（使用基本层）和O（（D+kΔ log（n/∈））log Δ）（使用概率层）.
In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate the contention management. We use two different abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer.We first present a typical randomized contention-manageent algorithm for a standard graph-based radio network model We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound ofO(Dlog(n/∈) log Δ) for the time to deliver a single message everywhere with probability 1 -- ∈, whereDis the network diameter,nis the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound ofO((D+ log(n/∈)) log Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds ofO((D+kΔ) log(n/∈) log Δ) using the basic layer andO((D+kΔ log(n/∈)) log Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at mostkconcurrent messages.
无线电网络中的高效广播：回顾
DOI：
--
发表时间：
2007
期刊：
International Conference on Distributed Computing and Internet Technology
影响因子：
--
作者：
D. Peleg
通讯作者：
D. Peleg
使用抽象 MAC 层的全局广播的成本
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
N. Lynch;F. Kuhn;D. Kowalski;M. Khabbazian
通讯作者：
M. Khabbazian
论无线电网络中的有效八卦
DOI：
--
发表时间：
2009
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
L. Gąsieniec
通讯作者：
L. Gąsieniec