The Cost of Global Broadcast Using Abstract MAC Layers
The Cost of Global Broadcast Using Abstract MAC Layers
复制标题
使用抽象 MAC 层的全局广播的成本
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Khabbazian
中科院分区：
文献类型：
--
作者：
N. Lynch;F. Kuhn;D. Kowalski;M. Khabbazian
我们使用基于插槽的模型分析了整个多跳无线网络的贪婪算法，其中包括消息碰撞而无需碰撞检测。用于竞争管理，我们使用MAC层的抽象版本来封装参数管理。我们的争论管理算法具有很高的概率，而有问题的算法则是我们的争夺管理算法，我们的争论管理算法精确地实现了以下方法，我们获得了以下复杂性范围：使用基本的摘要MAC层来实现。 ，花时间O（D log（）log（∆））以概率为1-到处传递消息，其中d是网络直径，n是节点的数量，∆是最大值节点度。使用基本层和o（（d+ k'∆ log（））log（log（∆））使用概率层，在大多数k处存在的情况下，到处传递一条消息'并发消息。
We analyze greedy algorithms for broadcasting messages throughout a multi-hop wireless network, using a slot-based model that includes message collisions without collision detection. Our algorithms are split formally into two pieces: a high-level piece for broadcast and a low-level piece for contention management. We accomplish the split using abstract versions of the MAC layer to encapsulate the contention management. We use two different abstract MAC layers: a basic non-probabilistic one, which our contention management algorithm implements with high probability, and a probabilistic one, which our contention management algorithm implements precisely. Using this approach, we obtain the following complexity bounds: Single-message broadcast, using the basic abstract MAC layer, takes time O(D log( ) log(∆)) to deliver the message everywhere with probability 1 − , where D is the network diameter, n is the number of nodes, and ∆ is the maximum node degree. Single-message broadcast, using the probabilistic abstract MAC layer, takes time only O((D + log( )) log(∆)). For multi-message broadcast, the bounds are O((D+ k′∆) log( ) log(∆)) using the basic layer and O((D+ k ′∆ log( )) log(∆)) using the probabilistic layer, for the time to deliver a single message everywhere in the presence of at most k′ concurrent messages.