BSF:2014170: SINR-Governed Wireless Networks: Geometric Analysis and Algorithms

BSF:2014170：SINR 管理的无线网络：几何分析和算法

• 批准号: 1540656
• 负责人: Boris Aronov
• 金额: $ 4万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540656&HistoricalAwards=false
• 关键词: BSF; 2014170; SINR; Governed; Wireless

Among many different models used to describe wireless networks, the PIs will focus on the one commonly called the SINR (Signal-to-Noise-and-Interference Ratio) model. It attempts to model the reception or non-reception of a wireless transmitter signal in the presence of interference from other transmitters and ambient noise. Much recent work has been devoted to analyzing the SINR model and using it to predict the behavior of real-life wireless networks. One simple aspect of this model is the construction of a SINR reception map, which associates with every transmitter the region where it can be received and also contains a region where no signal can be received due to interference of multiple transmitters. The exact map is difficult to compute due to the complexity of the so-called SINR inequality that determines whether or not a signal is received. Previous work has been done on approximating the reception map. The methods for this computation suffer from slow construction times (so-called preprocessing times) and from the fact that, for transmitters of unequal power, the preprocessing time depends not only on the number of transmitters and the accuracy of the approximation, but on other parameters of the problem that can not be expressed in terms of these two. The PIs will develop methods to overcome these by speeding up the preprocessing times.More specifically, the PIs will develop batch preprocessing for SINR-diagram point location queries. They will then use these tools to speed up existing algorithms for SINR-governed wireless networks. The PIs will study fundamental problems arising in SINR-governed wireless networks, combining algebraic tools with techniques of computational geometry and combinatorial optimization. The PIs will investigate a diverse suite of problems, including how to cope with directional antennas, problems arising when successive interference cancellation is enabled, combinatorial problems concerning SINR diagrams, and combinatorial optimization problems such as scheduling under a restricted, more practical version of the SINR model. The PIs will also investigate further applications of the underutilized combination of computer algebra and computational geometry tools in a more general context.Understanding the geometric properties of SINR-governed networks and being able to analyze such networks and predict their behavior is extremely important. Moreover, efficient solutions to the problems of this family, as well as to problems that PIs intend to study from a more practical point of view, will benefit the motivating application domain of wireless communication. These solutions are essential in the planning stages of such networks (e.g., determining where to locate the devices), for examining existing networks, and for utilizing them efficiently. In this respect, the proposed project has the potential for substantial socioeconomic impact, as the popularity of such networks is rapidly increasing.The project incorporates an educational mission, through training of graduate students and reciprocal visits among students and participants from the two institutions.

在用于描述无线网络的许多不同模型中，PI将集中在通常称为SINR（信号与噪声和干扰比）模型的模型上。 它试图在存在来自其他发射机和环境噪声的干扰的情况下对无线发射机信号的接收或未接收进行建模。最近的许多工作都致力于分析SINR模型，并使用它来预测现实生活中的无线网络的行为。 该模型的一个简单方面是SINR接收图的构造，其将每个发射机与其可以被接收的区域相关联，并且还包含由于多个发射机的干扰而不能接收信号的区域。 由于确定是否接收到信号的所谓SINR不等式的复杂性，难以计算精确的映射。以前的工作已经做了近似的接收地图。 用于该计算的方法遭受缓慢的构造时间（所谓的预处理时间）和以下事实：对于不等功率的发射机，预处理时间不仅取决于发射机的数量和近似的精度，而且取决于不能用这两个来表示的问题的其他参数。 PI将开发通过加快预处理时间来克服这些问题的方法。更具体地说，PI将开发针对SINR图点位置查询的批处理预处理。 然后，他们将使用这些工具来加速SINR管理的无线网络的现有算法。PI将研究SINR管理的无线网络中出现的基本问题，将代数工具与计算几何和组合优化技术相结合。PI将研究一系列不同的问题，包括如何科普定向天线，启用连续干扰消除时出现的问题，关于SINR图的组合问题，以及组合优化问题，例如在受限的，更实用的SINR模型版本下的调度。 PI还将研究计算机代数和计算几何工具在更一般的上下文中未充分利用的组合的进一步应用。理解SINR控制网络的几何特性，并能够分析此类网络并预测其行为是非常重要的。 此外，这个家庭的问题，以及PI打算从更实际的角度研究的问题的有效解决方案，将有利于激励无线通信的应用领域。这些解决方案在此类网络的规划阶段是必不可少的（例如，确定设备的位置），用于检查现有网络，以及用于有效地利用它们。在这方面，拟议的项目有可能产生重大的社会经济影响，因为这类网络正在迅速普及，该项目包括一项教育使命，通过培训研究生以及两个机构的学生和参与者之间的互访。

项目成果

Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

动态近似乘法加权最近邻

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Aronov, Boris;Katz, Matthew J.
• 通讯作者: Katz, Matthew J.

Geometric Pattern Matching Reduces to k -SUM

几何图案匹配简化为 k -SUM

• DOI: 10.1007/s00454-021-00324-1
• 发表时间: 2021
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Aronov, Boris;Cardinal, Jean
• 通讯作者: Cardinal, Jean

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

• DOI: 10.48550/arxiv.2203.10241
• 发表时间: 2022-03
• 作者: P. Agarwal;B. Aronov;Esther Ezra;M. J. Katz;M. Sharir

Time and space efficient collinearity indexing

• DOI: 10.1016/j.comgeo.2022.101963
• 发表时间: 2022-11
• 期刊: Comput. Geom.
• 作者: B. Aronov;Esther Ezra;M. Sharir;Guy Zigdon

Computing in Geometry and Topology

几何和拓扑计算

• DOI: 10.57717/cgt.v2i1.14
• 发表时间: 2023
• 期刊: Computing in Geometry and Topology
• 作者: Aronov, Boris;Basit, Abdul;de Berg, Mark;Gudmundsson, Joachim
• 通讯作者: Gudmundsson, Joachim