Geometric Algorithms for Local Routing and Interference Minimization

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

• 批准号: RGPIN-2015-05773
• 负责人: Durocher, Stephane
• 金额: $ 1.75万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=649814
• 关键词: 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(Logn)位路由算法。我提出的研究试图通过确定内存需求的良好界限(消息报头中的动态状态位的数量)、定义新的算法和表征广泛的几何图形类别来弥合这一差距，在这些几何图形上可以使用简单的计算和少量的状态位进行局部几何路由。*在无线网络中建立连通性可能是一项复杂的任务，必须对各种(有时相互冲突的)目标进行优化。与假设网络存在的问题不同(例如在路由中)，干扰最小化问题是在给定的一组节点上构建连接网络，同时最小化所得到的网络中的干扰。每个节点产生的干扰是作为其传输幅度以及位于其传输范围内的其他节点的数量和位置的函数来测量的，这导致了一个具有挑战性的几何组合优化问题。这个问题在许多情况下都是NP难的，这导致了对近似算法的研究。我提议的研究试图确定问题在未知环境中的复杂性，提供改进的近似算法，探索自然概括，并使用考虑干扰的物理表示的无线网络模型来检查干扰最小化。