Discrete optimization with applications in wireless networks

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

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.**