AF: Small: Algorithms for Wireless Networks with Dynamic Links

随着无线设备数量的增加和多样性的增加，通过无线链路进行通信的网络算法的研究已经重新受到关注。用于分析这些算法的大多数模型都假设静态链路（即，链路质量随时间固定）。相比之下，在真实的无线网络中，经常遇到表现出动态行为的链路（例如，快速的、不可预测的质量变化），这是由于变化的环境条件和/或来自共享频谱中的不相关协议的干扰。本项目旨在通过研究包含不同程度动态行为的无线模型来缩小理论与实践之间的差距--寻求新的算法策略以有效地解决基本问题，并证明新的下限以建立此类努力的极限。更详细地说，本项目侧重于无线通信的基于图的模型和信号噪声干扰比模型的动态变体。在这两种情况下，它寻求新的上限和下限的基本通信问题下不同程度的动态行为。下限有三个目标：（a）确定现有解决方案失败的动态阈值;（B）确定不可能有有效解决方案的（可能更大的）阈值;（c）开发新的通用方法来证明这种设置中的基本极限。该项目还寻求新的上限，是更强大的比现有的解决方案在动态设置，包括最近推出的链路检测器形式主义的权力的探索-一个抽象，捕捉低层次的链路探测服务常见的真实的wireless network.This项目将影响无线网络的理论和实践。在理论方面，它引入了新的模型，包括精确有界量的动态行为，并为这些设置开发了新的上限和下限技术。在实践方面，它将导致新的，可证明是正确的和有效的通信算法，是强大的大量不可预测的链接行为。这样的算法对于关键任务（例如，如在医疗保健、第一响应者、军事和协调/控制应用中所需要的）到无线平台。

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.