AF: Small: Algorithms for Wireless Networks with Dynamic Links

Georgetown University, Washington DC

Investigators

Abstract

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.