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.