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

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

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.