Discrete optimization with applications in wireless networks

离散优化在电信中是必不可少的。网络满足其需求的能力取决于网络运营商如何部署和管理其资源。设施选址问题是特别感兴趣的，因为他们关心的设施的位置，以优化目标函数，如提供公平的服务，客户端，最小化的运输成本等，在无线网络中，设施的节点，形成网络骨干和目标函数表示定性的网络参数。 该建议旨在推进离散优化和设施选址的研究，以支持尖端无线技术的发展。一个这样的应用领域是认知无线网络（CWN）的设计。CWN的特点是密集和重叠的网络部署，合作更有效地使用稀缺的无线电频谱。例如，WiFi部署和蜂窝网络可以合作，以尽可能最好和最有效的方式为电话会话提供数据包。由于节点本身必须决定合作的最佳策略（节点是“认知”的），因此，在离散优化算法的问题建模的无线网络的物理特性的进步，成为不可或缺的。 确定了三个具体的研究领域。 1)加权着色算法（WCP）-调查时分多址（TDMA）网络中干扰和信道分配的影响：无线网络中建模干扰的常用方法使用具有边缘成本和容量的通信图中的网络流问题。虽然广泛用于路由协议，网络流问题是没有表现力的WCP时，在TDMA网络中最宝贵的资源之一，时间建模。有一个令人惊讶的少数不同的策略来解决WCP。这个建议确定了一系列的算法，目标特殊的图形拓扑结构，并采用强大的技术，如线性和整数规划。处理不确定性是本建议所涉及的文献迄今为止所忽视的第三个方面（另见下文第3点）。 2)可变容量覆盖是我早期研究码分多址多跳蜂窝网络时遇到的一个新问题。该提案包含几个扩展我当前研究的方向，包括针对受限网络拓扑的专用算法和使用更通用的无线电干扰模型。 3)鲁棒设施选址问题处理的不确定输入，在网络中常见的。目前，很少有人知道多设施的鲁棒问题。我建议开始多设施选址问题的研究，考虑两个设施的情况下，不同的目标函数。

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.