Grant: Discovery Grants Program - Individual
University of Lethbridge
$18,000.00
Discrete optimization with applications in wireless networks
EF 2016-17
Résumé
Discrete optimization is essential in telecommunication. The ability of a network to serve its demand depends on how well network operators deploy and manage their resources. Facility location problems are of particular interest as they are concerned with the placement of facilities to optimize an objective function such as providing equitable service to clients, minimizing the transportation cost, etc. In wireless networks, facilities are the nodes that form the network backbone and the objective function represents qualitative network parameters.
This proposal aims at advancing the research on discrete optimization and facility location to support the development of cutting edge wireless technologies. One such area of application is the design of Cognitive Wireless Networks (CWN). CWN are characterized by dense and overlapping network deployments that co-operate to use the scarce radio spectrum more efficiently. For example, WiFi deployments and cellular networks could co-operate to deliver the data packets for a telephone conversation in the best and most efficient way possible. As the nodes themselves must decide on the best strategy for co-operation (the nodes are ""cognitive""), advances in discrete optimization algorithms for problems modeling the physical characteristics of wireless networks, become indispensable.
Three concrete research areas are identified.
1) Algorithms for weighted colouring (WCP) - investigating the impact of interference and channel assignment in time division multiple access (TDMA) networks: a common approach to modellng interference in wireless networks uses network flow problems in communication graphs with edge costs and capacities. Although extensively used in routing protocols, network flow problems are not as expressive as WCP when modelling one of the most precious resources in TDMA networks, time. There is a surprisingly small number of different strategies to solve WCP.This proposal identifies a series of algorithms that target special graph topologies and employ powerful techniques such as linear and integer programming. Dealing with uncertainty is a third aspect overlooked, so far, in the literature that this proposal addresses (see also point 3 below).
2) Covering with variable capacity is a new problem that emerged from my earlier work on multi-hop cellular networks concerning code division multiple access networks. The proposal contains several directions that expand my current research, including specialized algorithms for restricted network topologies and using more general radio interference models.
3) Robust facility location deals with problems with uncertain input, a common occurrence in networks. At present, very little is known about robust problems with multiple facilities. I propose to begin the research on multiple facility location problems by considering the 2 facility case with different objective functions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2015-04163
Name nom
Benkoczi, Robert
Department département
Mathematics and Computer Science - Mathematics and Computer Science
Organization id
12
Institution établissement
University of Lethbridge
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2015
Award amount
18000
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
2
Nb partie
5
Application title
Discrete optimization with applications in wireless networks
Keyword
NSERC
Application summary
Discrete optimization is essential in telecommunication. The ability of a network to serve its demand depends on how well network operators deploy and manage their resources. Facility location problems are of particular interest as they are concerned with the placement of facilities to optimize an objective function such as providing equitable service to clients, minimizing the transportation cost, etc. In wireless networks, facilities are the nodes that form the network backbone and the objective function represents qualitative network parameters.
This proposal aims at advancing the research on discrete optimization and facility location to support the development of cutting edge wireless technologies. One such area of application is the design of Cognitive Wireless Networks (CWN). CWN are characterized by dense and overlapping network deployments that co-operate to use the scarce radio spectrum more efficiently. For example, WiFi deployments and cellular networks could co-operate to deliver the data packets for a telephone conversation in the best and most efficient way possible. As the nodes themselves must decide on the best strategy for co-operation (the nodes are ""cognitive""), advances in discrete optimization algorithms for problems modeling the physical characteristics of wireless networks, become indispensable.
Three concrete research areas are identified.
1) Algorithms for weighted colouring (WCP) - investigating the impact of interference and channel assignment in time division multiple access (TDMA) networks: a common approach to modellng interference in wireless networks uses network flow problems in communication graphs with edge costs and capacities. Although extensively used in routing protocols, network flow problems are not as expressive as WCP when modelling one of the most precious resources in TDMA networks, time. There is a surprisingly small number of different strategies to solve WCP.This proposal identifies a series of algorithms that target special graph topologies and employ powerful techniques such as linear and integer programming. Dealing with uncertainty is a third aspect overlooked, so far, in the literature that this proposal addresses (see also point 3 below).
2) Covering with variable capacity is a new problem that emerged from my earlier work on multi-hop cellular networks concerning code division multiple access networks. The proposal contains several directions that expand my current research, including specialized algorithms for restricted network topologies and using more general radio interference models.
3) Robust facility location deals with problems with uncertain input, a common occurrence in networks. At present, very little is known about robust problems with multiple facilities. I propose to begin the research on multiple facility location problems by considering the 2 facility case with different objective functions.