Discrete optimization with applications in wireless networks

无线网络应用的离散优化

• 批准号: RGPIN-2015-04163
• 负责人: Benkoczi, Robert
• 金额: $ 1.31万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612812
• 关键词: Discrete; optimization; applications; 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.

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