NeTS: Small: Control of Partially Observable Wireless Networks: Fundamental Limits, Optimal Algorithms and Practical Implementation

NeTS：小型：部分可观测无线网络的控制：基本限制、最优算法和实际实现

• 批准号: 1262329
• 负责人: Lei Ying
• 金额: $ 33万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-16 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1262329&HistoricalAwards=false
• 关键词: NeTS; Small; Control; Partially; Observable

State dependent resource allocation is critical for improving the network efficiency. Over the past two decades, remarkable progress has been made on the design of wireless networks with maximum throughput and low latency by using state dependent resource allocation algorithms. However, most of these works assume the network is fully observable and the network state information is perfectly known. This assumption is becoming increasingly questionable because of the multi-carrier technology, which makes it extremely expensive to obtain the complete network state information, and transmission delays and measurement errors, which make it impossible to know the exact network state. With wireless networks become pervasive in our daily life, new theories and algorithms are needed for partially observable wireless networks.In this project, the PI models a partially observable wireless network as a partially observable Markov process, and then applies the framework of Markov decision processes (MDP). While important structure properties may be discovered using the MDP framework, finding optimal solutions in general is an NP-hard problem. To overcome this difficulty, this project uses drift-based competitive analysis and drift-based large-deviations analysis for quantifying fundamental limits and deriving optimal or near optimal algorithms. The project is expected to lead to breakthroughs in managing partially observable wireless networks. Fundamental limits of partially observable wireless networks, novel resource allocation algorithms with provable throughput and latency guarantees, and implementations on a real-world test bed will have a significant impact on the design and implementation of future wireless networks.

状态相关的资源分配是提高网络效率的关键。在过去的二十年里，利用状态相关的资源分配算法在设计具有最大吞吐量和低延迟的无线网络方面取得了显著的进展。然而，这些工作大多假设网络是完全可观测的，并且网络状态信息是完全已知的。由于多载波技术使得获取完整的网络状态信息变得极其昂贵，以及传输延迟和测量误差使得无法知道准确的网络状态，这一假设变得越来越令人怀疑。随着无线网络在日常生活中的普及，对部分可观测的无线网络提出了新的理论和算法要求。在本项目中，PI将部分可观测的无线网络建模为部分可观测的马尔可夫过程，然后应用马尔可夫决策过程的框架。虽然使用MDP框架可以发现重要的结构属性，但寻找最优解通常是一个NP-Hard问题。为了克服这一困难，本项目使用基于漂移的竞争分析和基于漂移的大偏差分析来量化基本极限，并得出最优或接近最优的算法。该项目有望在管理部分可观测到的无线网络方面取得突破。部分可观测无线网络的基本限制、具有可证明的吞吐量和延迟保证的新型资源分配算法以及在真实世界试验台上的实现将对未来无线网络的设计和实现产生重大影响。