Geometric Algorithms for Local Routing and Interference Minimization

点击翻译按钮获取中文摘要

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.