Network Design under General Wireless Interference
Network Design under General Wireless Interference
复制标题
DOI：
10.1007/s00453-021-00866-z
复制
发表时间：
2021-08
期刊：
影响因子：
1.1
通讯作者：
M. Halldórsson;G. Kortsarz;Pradipta Mitra;Tigran Tonoyan
中科院分区：
文献类型：
--
作者：
M. Halldórsson;G. Kortsarz;Pradipta Mitra;Tigran Tonoyan
我们引入了寻找生成树以及将树边划分为最少数量的可行集的问题，其中对边的约束定义了可行性。动机来自无线网络，我们试图对实际无线环境中出现的不规则现象进行建模。并非所有节点对都能够通信，即使地理位置很近，因此，可用链接图指定可用的对。此外，信号衰减不需要遵循良好的几何公式，因此，干扰是通过链路上的冲突（超）图来建模的。目标是最大化通信效率，或者同等地，最小化着色形式的树边的调度的长度。我们发现，尽管具有所有这些普遍性，但该问题可以根据通用参数（冲突图的归纳独立性）来线性近似。具体来说，我们给出了一个获得 a 近似的简单算法，其中 是 节点数， 是 归纳独立性。对于 Steiner 树的扩展，对多播进行建模，我们获得了 a 近似值。我们还考虑了当只有长于阈值的链接不可用时的自然几何设置，并分析几何最小生成树的性能。
We introduce the problem of finding a spanning tree along with a partition of the tree edges into the fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close—thus, the available pairs are specified with a link graph. Also, signal attenuation need not follow a nice geometric formula—hence, interference is modeled by a conflict (hyper)graphon the links. The objective is to maximize the efficiency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the conflict graph. Specifically, we give a simple algorithm that attains a-approximation, wherenis the number of nodes andis the inductive independence. For an extension to Steiner trees, modeling multicasting, we obtain a-approximation. We also consider a natural geometric setting when only links longer than a threshold can be unavailable, and analyze the performance of a geometric minimum spanning tree.