AF: Small: Algorithms for Wireless Networks with Dynamic Links

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

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.