Grant: Discovery Grants Program - Individual
University of Manitoba
$24,000.00
Geometric Algorithms for Local Routing and Interference Minimization
FY 2019-20
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-05773
Name nom
Durocher, Stephane
Department département
Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2015
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Installment
inst:5 - 5
Partie
5
Nb partie
5
Application title
Geometric Algorithms for Local Routing and Interference Minimization
Keyword
NSERC
Application summary
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.