Discrete optimization with applications in wireless networks

离散优化在电信领域中是必不可少的。网络满足其需求的能力取决于网络运营商如何部署和管理其资源。设施选址问题是一个特别有意义的问题，因为它涉及到设施的布置，以优化目标函数，如为客户提供公平的服务，最小化运输成本等。在无线网络中，设施是构成网络主干的节点，目标函数代表定性的网络参数。*本建议旨在推进离散优化和设施选址的研究，以支持尖端无线技术的发展。认知无线网络(CWN)的设计就是这样一个应用领域。CWN的特点是密集和重叠的网络部署，以更有效地利用稀缺的无线电频谱。例如，WiFi部署和蜂窝网络可以合作，以尽可能最佳和最高效的方式为电话交谈提供数据分组。由于节点本身必须决定最佳的协作策略(节点是“认知的”)，因此，为无线网络的物理特征建模问题的离散优化算法的进步变得必不可少。*确定了三个具体的研究领域。*1)加权着色(WCP)算法--研究时分多址(TDMA)网络中干扰和信道分配的影响：无线网络中的干扰建模的一种常见方法是在通信图中使用具有边成本和容量的网络流问题。虽然在路由协议中广泛使用，但在对TDMA网络中最宝贵的资源之一时间进行建模时，网络流问题并不像WCP那样具有表现力。解决WCP.p的不同策略数量少得惊人。该提案确定了一系列针对特殊图形拓扑的算法，并使用了强大的技术，如线性规划和整数规划。到目前为止，在本提案所涉及的文献中，处理不确定性是被忽略的第三个方面(也参见下面的点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.**