Grant: Discovery Grants Program - Individual
University of Manitoba
$30,000.00
Geometric algorithms for wireless networks and mobile computing
FY 2014-15
Summary
Wireless communications and wireless networks have become a critical component of nearly every industry in Canada. Yet many fundamental problems in wireless networking remain open and require further research to provide efficient solutions that meet the needs of evolving technologies and applications. The field of algorithms in theoretical computer science plays a key role in addressing these issues.The topology of a wireless network is determined by the positions of its nodes and their transmission range. That is, the network is defined geometrically. This project seeks to determine how this geometry can be leveraged to find efficient solutions to common problems in wireless networks and, in particular, to problems of facility location and local routing, in both static and mobile settings. Specifically, positioning facilities (such as gateways or base stations) in a wireless network involves a combination of geometric and graph-theoretic constraints to which previous facility location solutions do not apply. With respect to local routing, efficient algorithms that guarantee delivery in three-dimensional wireless networks remain to be discovered. In particular, bounds on memory requirements for position-based local routing algorithms remain to be established. Answering questions such as these is the goal of the proposed research program.In addition to developing new algorithmic solutions, the types of techniques proposed include identifying bounds on the existence and quality of approximation of feasible solutions, as well as defining and analyzing new models to represent these problems effectively. The proposed research will be carried out in collaboration with graduate students, postdoctoral fellows, and undergraduate research assistants.
Program
Discovery Grants Program - Individual
Recipient
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
386496-2010
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
2014
Competition year année de concours
2010
Award amount
30000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
Partie
5
Nb partie
5
Application title
Geometric algorithms for wireless networks and mobile computing
Keyword
NSERC
Application summary
Wireless communications and wireless networks have become a critical component of nearly every industry in Canada. Yet many fundamental problems in wireless networking remain open and require further research to provide efficient solutions that meet the needs of evolving technologies and applications. The field of algorithms in theoretical computer science plays a key role in addressing these issues.The topology of a wireless network is determined by the positions of its nodes and their transmission range. That is, the network is defined geometrically. This project seeks to determine how this geometry can be leveraged to find efficient solutions to common problems in wireless networks and, in particular, to problems of facility location and local routing, in both static and mobile settings. Specifically, positioning facilities (such as gateways or base stations) in a wireless network involves a combination of geometric and graph-theoretic constraints to which previous facility location solutions do not apply. With respect to local routing, efficient algorithms that guarantee delivery in three-dimensional wireless networks remain to be discovered. In particular, bounds on memory requirements for position-based local routing algorithms remain to be established. Answering questions such as these is the goal of the proposed research program.In addition to developing new algorithmic solutions, the types of techniques proposed include identifying bounds on the existence and quality of approximation of feasible solutions, as well as defining and analyzing new models to represent these problems effectively. The proposed research will be carried out in collaboration with graduate students, postdoctoral fellows, and undergraduate research assistants.