AF: Small: Adversarial Models for Wireless Communication

点击翻译按钮获取中文摘要

From an algorithmic point of view, systems based on wireless communication pose unique challenges that are not present in standard networks. Wireless devices may move around and communication between these devices can be disrupted for several reasons including obstacles, background noise, and interference problems due to transmissions from the own wireless network, from a malicious jammer trying to disrupt communication, as well as coexisting networks using the same frequency band. Finding suitable models that on one hand allow the rigorous design and analysis of protocols and on the other hand are useful in practice is a major challenge and deserves significant research efforts.We will investigate models for wireless communication that cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory and practice. In contrast to prior algorithmic approaches, our approach will be to model communication problems due to physical layer issues (such as ackground noise, obstacles, jammers, etc.) with the help of an adversary, and to develop medium access (MAC) protocols that are provably robust against these adversaries. Such an approach has many interesting applications. First, it allows for more general scenarios for the background noise than previous approaches as it covers bursty situations that might be due to some temporary obstacle or operation of a machine that creates interference. Second, the adversarial model would also allow us to determine how robust a protocol is against wireless jamming attacks, which are a real threat to standard protocols such as the 802.11 family or networks of simple sensing wireless devices (where traditional physical layer techniques cannot be successfully applied). Finally, the adversarial model may allow us to abstract from interference problems due to transmissions of far away devices in the wireless network. In addition, we will also focus on important applications such as leader election and broadcasting. Since wireless networks are a component of many widespread and/or critical systems, the proposed research will have an impact in several respects, including immediate applications to emergency services, the military, and local area networks in hazardous areas. Moreover, the proposed research will also have an impact in solidifying the international collaboration with the U. of Paderborn, Germany, and in advancing education and enhancing diversity.