论文标题
$ 2 $ -HOP干扰模型下无线网络中的分布式算法的性能分析
Performance analysis of a distributed algorithm for admission control in wireless networks under the $2$-hop interference model
论文作者
论文摘要
网络中的一个普遍开放问题是：一定数量的资源可以实现的性能的基本限制是什么？更具体地说，如果网络中的每个节点都有有关其$ 1 $ hop社区的信息，那么性能的限制是什么？对于无线网络，考虑了此问题，在该网络中，每个通信链接都有最小的带宽服务质量（QoS）要求。相同附近的链接是共享无线介质的争夺。冲突图捕获了链接对彼此干扰的，并取决于MAC协议。在IEEE 802.11基于Mac协议的网络中，当进行节点$ i $和$ j $之间的通信时，$ i $和$ j $的邻居保持沉默。这种干扰模型称为$ 2 $ -HOP干扰模型，因为任何两个链接之间的网络图中的距离至少是$ 2 $。在入院控制问题中，目的是仅使用本地信息确定一组流速是否可行。 在目前的工作中，为此问题提出了分布式算法，每个节点都有有关其$ 1 $ hop社区的信息。分布式算法最差的性能，即该分布式算法的性能与最佳，集中算法的性能相比，通过该算法的最大因素。获得了分布式算法的次级临时和上限，并且两个边界都显示为紧密。对于某些环形拓扑结构，获得了确切的最坏情况。虽然已经分析了$ 1 $ -HOP干扰模型的距离-D $分布式算法，但文献中的一个开放问题是将这些结果扩展到$ K $ -HOP干扰模型，而本工作将概括启动到$ K $ -HOP-HOP干扰模型。
A general open problem in networking is: what are the fundamental limits to the performance that is achievable with some given amount of resources? More specifically, if each node in the network has information about only its $1$-hop neighborhood, then what are the limits to performance? This problem is considered for wireless networks where each communication link has a minimum bandwidth quality-of-service (QoS) requirement. Links in the same vicinity contend for the shared wireless medium. The conflict graph captures which pairs of links interfere with each other and depends on the MAC protocol. In IEEE 802.11 MAC protocol-based networks, when communication between nodes $i$ and $j$ takes place, the neighbors of both $i$ and $j$ remain silent. This model of interference is called the $2$-hop interference model because the distance in the network graph between any two links that can be simultaneously active is at least $2$. In the admission control problem, the objective is to determine, using only localized information, whether a given set of flow rates is feasible. In the present work, a distributed algorithm is proposed for this problem, where each node has information only about its $1$-hop neighborhood. The worst-case performance of the distributed algorithm, i.e. the largest factor by which the performance of this distributed algorithm is away from that of an optimal, centralized algorithm, is analyzed. Lower and upper bounds on the suboptimality of the distributed algorithm are obtained, and both bounds are shown to be tight. The exact worst-case performance is obtained for some ring topologies. While distance-$d$ distributed algorithms have been analyzed for the $1$-hop interference model, an open problem in the literature is to extend these results to the $K$-hop interference model, and the present work initiates the generalization to the $K$-hop interference model.
