AF: Small: Algorithms for Wireless Networks with Dynamic Links

AF：小型：具有动态链接的无线网络算法

• 批准号: 1320279
• 负责人: Calvin Newport
• 金额: $ 31.95万
• 依托单位: Georgetown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320279&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Wireless; Networks

With the increasing quantity and diversity of wireless devices, the study of network algorithms that communicate over radio links has received renewed interest. Most of the models used to analyze these algorithms assume static links (i.e., link quality is fixed over time). In real wireless networks, by contrast, it is common to encounter links that exhibit dynamic behavior (e.g., rapid, unpredictable changes in quality) due to changing environmental conditions and/or interference from unrelated protocols in shared spectrum. This project aims to reduce this gap between theory and practice by studying wireless models that include varying degrees of dynamic behavior -- seeking new algorithm strategies for solving fundamental problems efficiently and proving new lower bounds that establish the limits of such efforts.In more detail, this project focuses on dynamic variants of both graph-based and Signal-to-Noise-and-Interference-Ratio models of wireless communication. In both settings, it seeks new upper and lower bounds for fundamental communication problems under varying degrees of dynamic behavior. There are three goals for the lower bounds: (a) to determine the threshold of dynamism at which existing solutions fail; (b) to determine the (presumably greater) threshold at which no efficient solutions are possible; and (c) to develop new general methods for proving fundamental limits in this setting. The project also seeks new upper bounds that are more robust than existing solutions in dynamic settings, including an exploration of the power of the recently introduced link detector formalism -- an abstraction that captures the low-level link probing services common in real wireless networks.This project will impact both the theory and practice of wireless networks. On the theory side, it introduces new models that include precisely-bounded amounts of dynamic behavior, and develops new upper and lower bound techniques for these settings. On the practice side, it will lead to new, provably correct and efficient communication algorithms that are robust to significant amounts of unpredictable link behavior. Such algorithms are crucial for the migration of mission-critical tasks (e.g., as required in healthcare, first responder, military, and coordination/control applications) to wireless platforms.

随着无线设备的数量和多样性不断增加，通过无线电链路进行通信的网络算法的研究重新引起了人们的兴趣。大多数用于分析这些算法的模型都假设静态链接（即链接质量随时间推移而固定）。相比之下，在真实的无线网络中，由于环境条件的变化和/或共享频谱中不相关协议的干扰，经常会遇到表现出动态行为的链路（例如，快速、不可预测的质量变化）。该项目旨在通过研究包括不同程度的动态行为的无线模型来缩小理论与实践之间的差距，寻找新的算法策略来有效地解决基本问题，并证明确定此类努力的限制的新下限。更详细地说，该项目重点关注无线通信的基于图的模型和信噪比模型的动态变体。在这两种情况下，它都在不同程度的动态行为下寻求基本通信问题的新上限和下限。下限有三个目标： (a) 确定现有解决方案失败的动态阈值； (b) 确定不可能有有效解决方案的阈值（可能更大）； (c) 开发新的通用方法来证明这种情况下的基本限制。该项目还寻求比动态环境中现有解决方案更稳健的新上限，包括探索最近引入的链路检测器形式主义的强大功能，这是一种捕获真实无线网络中常见的低级链路探测服务的抽象。该项目将影响无线网络的理论和实践。在理论方面，它引入了包含精确限制的动态行为量的新模型，并为这些设置开发了新的上限和下限技术。在实践方面，它将带来新的、可证明正确且高效的通信算法，这些算法对大量不可预测的链路行为具有鲁棒性。此类算法对于将关键任务（例如医疗保健、急救人员、军事和协调/控制应用程序所需的任务）迁移到无线平台至关重要。