Batched Point Location in SINR Diagrams via Algebraic Tools
Batched Point Location in SINR Diagrams via Algebraic Tools
复制标题
通过代数工具在 SINR 图中批量定位点
DOI：
10.1145/3209678
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. J. Katz
中科院分区：
文献类型：
--
作者：
B. Aronov;M. J. Katz
用于无线连接质量的SINR（信号与干扰加噪声比）模型已经成为最近广泛研究的主题。它试图预测在由n个同时发射器和背景噪声组成的设置中，特定发射器是否在特定位置被听到。SINR模型产生了一个自然的几何对象，即SINR图，它将空间划分为n个区域，在这些区域中，每个发射机都可以被听到，而剩余的空间中没有发射机可以被听到。SINR图中的有效点位置，即，能够构建数据结构，该数据结构便于确定对于查询点是否在那里听到任何发射机，以及如果是，则确定是哪一个，这在最近的几篇文章中已经被研究。这些平面数据结构在时间上至少是在n中的二次构造的，并且支持并行时间近似查询。此外，所提出的一些结构的性能不仅强烈地依赖于发射器的数量n和近似参数ε，而且还依赖于一些几何参数，这些几何参数不能作为n或ε的函数先验地被限制。在这篇文章中，我们解决了批量点位置查询的问题，即，同时回答多个问题。具体来说，在一维中，我们可以在每个查询的摊销多对数时间内准确地回答n个查询，而在平面中，我们可以近似地做到这一点。在另一个结果中，我们展示了如何在每个查询的摊销多对数时间内准确地回答n2个查询，假设查询位于可能不均匀的n × n网格上。所有这些结果可以处理任意的功率分配给发射机。此外，这些结果中的分摊查询时间仅取决于n和ε。我们还展示了如何加快预处理在以前提出的点位置结构中的SINR图均匀功率的网站，几乎一个完整的数量级。为此，我们得到的结果的敏感性的接收区域的轻微变化的接收阈值，这是独立的利益。最后，这些结果表明（迄今未充分利用）的权力相结合的代数工具与计算几何和其他领域。
The SINR (Signal to Interference plus Noise Ratio) model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard. Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several articles. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter ε, but also on some geometric parameters that cannot be bounded a priori as a function of n or ε. In this article, we address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. In another result, we show how to answer n2 queries exactly in amortized polylogarithmic time per query, assuming the queries are located on a possibly non-uniform n × n grid. All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and ε. We also show how to speed up the preprocessing in a previously proposed point-location structure in SINR diagram for uniform-power sites, by almost a full order of magnitude. For this, we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest. Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.