Geometric Algorithms for Local Routing and Interference Minimization

用于本地路由和干扰最小化的几何算法

• 批准号: RGPIN-2015-05773
• 负责人: Durocher, Stephane
• 金额: $ 1.75万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679754
• 关键词: Geometric; Algorithms; Local; Routing; Interference

This research proposal seeks to develop algorithms for solving problems on geometric models for wireless networks. The topology of a wireless network is determined by the positions of its nodes and their transmission ranges. That is, many aspects of the network can be modelled geometrically. The proposed research seeks to address how this geometry can be leveraged to find efficient solutions to important algorithmic problems in wireless networks. The primary focus will be on two classes of problems: local routing and interference minimization. In addition to developing new exact and approximate algorithms, the proposed work includes identifying bounds on the feasibility of solving these problems to better understand their complexity, as well as defining, extending, and analyzing new and existing models to represent these problems realistically.***Communication in a computer network is achieved by routing a message (e.g., a packet) along a connected path (a route) through the network to its destination. When nodes have positional information, capitalizing on a network's geometric properties can enable a routing algorithm to orient itself and guarantee delivery to the destination node, where each forwarding decision is determined by the geometry of the local subgraph. Stateless routing algorithms are known that guarantee delivery in triangulations, and O(log n)-bit routing algorithms are known that guarantee delivery in planar and near-planar graphs, and in more general classes of non-geometric graphs. My proposed research seeks to bridge this gap by identifying good bounds on the memory requirements (the number of dynamic state bits in the message header), defining new algorithms for, and characterizing broad classes of geometric graphs on which local geometric routing is possible using only simple computation and few state bits.***Establishing connectivity in a wireless network can be a complex task for which various (sometimes conflicting) objectives must be optimized. Unlike problems in which the network is assumed to exist (such as in routing), the problem of interference minimization is to construct a connected network on a given set of nodes while minimizing interference in the resulting network. The interference created by each node is measured as a function of its transmission amplitude, and the number and positions of other nodes that lie within its range of transmission, resulting in a challenging geometric combinatorial optimization problem. This problem is known to be NP-hard in many settings, leading to the examination of approximation algorithms. My proposed research seeks to determine the problem's complexity in settings for which it remains unknown, provide improved approximation algorithms, explore natural generalizations, and examine interference minimization using models for wireless networks that consider physically based representations for interference.

本研究旨在开发解决无线网络几何模型问题的算法。无线网络的拓扑结构由其节点的位置及其传输范围决定。也就是说，网络的许多方面都可以用几何模型来模拟。拟议的研究旨在解决如何利用这种几何形状来找到有效的解决方案，在无线网络中的重要算法问题。主要重点将放在两类问题：本地路由和干扰最小化。 除了开发新的精确和近似算法外，拟议的工作还包括确定解决这些问题的可行性界限，以更好地理解其复杂性，以及定义，扩展和分析新的和现有的模型，以现实地表示这些问题。计算机网络中的通信是通过路由消息（例如，分组）沿着连接的路径（路由）通过网络到达其目的地。当节点具有位置信息时，利用网络的几何属性可以使路由算法能够定向自身并保证递送到目的地节点，其中每个转发决策由局部子图的几何形状确定。无状态路由算法是已知的，保证在三角形的交付，和O（log n）位路由算法是已知的，保证在平面和近平面图，并在更一般的类的非几何图形的交付。我提出的研究旨在通过确定内存需求（消息报头中动态状态位的数量）的良好界限来弥合这一差距，定义新的算法，并描述仅使用简单计算和少量状态位就可以实现局部几何路由的广泛几何图类别。在无线网络中建立连接可能是一项复杂的任务，必须优化各种（有时是冲突的）目标。与假设网络存在的问题（如路由）不同，干扰最小化问题是在给定的节点集上构建一个连通网络，同时最小化所产生网络中的干扰。每个节点产生的干扰被测量为其传输幅度的函数，以及位于其传输范围内的其他节点的数量和位置，从而导致具有挑战性的几何组合优化问题。这个问题在许多情况下都是NP难的，这就导致了对近似算法的研究。我提出的研究旨在确定问题的复杂性，它仍然是未知的设置，提供改进的近似算法，探索自然的概括，并检查干扰最小化使用模型的无线网络，考虑基于物理的干扰表示。