Multiflows in multi-channel multi-radio multihop wireless networks
Multiflows in multi-channel multi-radio multihop wireless networks
复制标题
DOI：
10.1109/infcom.2011.5935308
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
P. Wan;Yu Cheng;Zhu Wang;F. Yao
中科院分区：
文献类型：
--
作者：
P. Wan;Yu Cheng;Zhu Wang;F. Yao
本文研究802.11干扰模型或协议干扰模型下多信道多无线电多跳无线网络中的最大多流（MMF）和最大并发多流（MCMF）。我们引入了多通道多无线电多跳无线网络的细粒度网络表示，并提出了其相关冲突图的一些基本拓扑属性。通过利用这些特性，我们为 MMF 和 MCMF 开发了实用的多项式逼近算法，无论通道和无线电的数量如何，都具有恒定的逼近界限。在802.11干扰模型下，它们的近似范围一般最多为20，在均匀干扰半径下最多为8；在协议干扰模型下，如果每个节点的干扰半径至少是其通信半径的c倍，则它们的近似界限至多为2(⌈π/arcsin c−1 over 2c⌉+1)。此外，我们还证明，如果信道数量受常数限制（这在实际网络中很常见），MMF 和 MCMF 都承认在 802.11 干扰模型或具有一些附加温和条件的协议干扰模型下的多项式时间近似方案。
This paper studies maximum multiflow (MMF) and maximum concurrent multiflow (MCMF) in muliti-channel multi-radio multihop wireless networks under the 802.11 interference model or the protocol interference model. We introduce a fine-grained network representation of multi-channel multi-radio multihop wireless networks and present some essential topo-logical properties of its associated conflict graph. By exploiting these properties, we develop practical polynomial approximation algorithms for MMF and MCMF with constant approximation bounds regardless of the number of channels and radios. Under the 802.11 interference model, their approximation bounds are at most 20 in general and at most 8 with uniform interference radii; under the protocol interference model, if the interference radius of each node is at least c times its communication radius, their approximation bounds are at most 2 (⌈π / arcsin c−1 over 2c⌉ + 1). In addition, we also prove that if the number of channels is bounded by a constant (which is typical in practical networks), both MMF and MCMF admit a polynomial-time approximation scheme under the 802.11 interference model or under the protocol interference model with some additional mild conditions.