The topology of wireless communication
The topology of wireless communication
复制标题
无线通信的拓扑结构
DOI：
10.1145/1993636.1993688
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Erez Kantor;Zvi Lotker;M. Parter;D. Peleg
在本文中，我们研究了无线通信地图的拓扑性质及其在算法设计中的可用性。我们考虑SINR模型，该模型将接收器处的信号的接收功率与其他干扰信号加上背景噪声的强度之和进行比较。为了描述多站网络的行为，我们使用接收图的方便表示。在SINR模型中，所得到的SINR图将平面划分为接收区，每个站一个，以及平面的没有站可以被听到的补充区域。在[3]中已经针对所有站使用相同功率的特定情况研究了SINR图。它示出的接收区是凸的（因此连接）和脂肪，这是用来设计一个有效的算法的基本问题的点定位。在这里，我们考虑更一般（和常见）的情况下，传输能量是任意的（或不均匀的）。在该设置下，接收区不一定是凸的或者甚至是连接的。这提出了针对非均匀设置设计有效的点定位技术的算法挑战，以及理解SINR图的几何结构的理论挑战（例如，它们可能具有的连接分量的最大数目）。我们在两个方向上都取得了一些成果。我们建立了一种形式的较弱的凸性的情况下，站对齐的一条线，并使用此导出一个紧界的连接组件的数量在这种情况下。此外，我们的一个关键结果涉及（d+1）维映射的行为，即，在比其中嵌入站的维度高的一个维度中的地图。具体来说，虽然d维地图可能是高度断裂的，但在一维更高的地方绘制地图可以“修复”区域，这些区域变得连接起来（实际上是双曲线连接）。此外，作为一个步骤，建立一个较弱的形式的凸性的d维映射，我们研究的干扰函数，并证明它满足最大值原理。这是通过一种分析技术来完成的，该技术基于观察由密集放置的弱站组成的系统的行为，因为站的数量趋于无穷大，保持其总传输能量固定。最后，我们转而考虑算法应用，并提出了一个新的变种的近似点定位。
In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a reception map. In the SINR model, the resulting SINR diagram partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. SINR diagrams have been studied in [3] for the specific case where all stations use the same power. It is shown that the reception zones are convex (hence connected) and fat, and this is used to devise an efficient algorithm for the fundamental problem of point location. Here we consider the more general (and common) case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques for the non-uniform setting, as well as the theoretical challenge of understanding the geometry of SINR diagrams (e.g., the maximal number of connected components they might have). We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line and use this to derive a tight bound on the number of connected components in this case. In addition, one of our key results concerns the behavior of a (d+1)-dimensional map, i.e., a map in one dimension higher than the dimension in which stations are embedded. Specifically, although the d-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected (in fact hyperbolically connected). In addition, as a step toward establishing a weaker form of convexity for the d-dimensional map, we study the interference function and show that it satisfies the maximum principle. This is done through an analysis technique based on looking at the behavior of systems composed on lines of densely placed weak stations, as the number of stations tends to infinity, keeping their total transmission energy fixed. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.