AF: Small: Adversarial Models for Wireless Communication

从算法的角度来看，基于无线通信的系统提出了标准网络中不存在的独特挑战。无线设备可能会四处移动，这些设备之间的通信可能会因多种原因而中断，包括障碍物、背景噪声、来自自身无线网络传输的干扰问题、试图破坏通信的恶意干扰者以及使用相同频段的共存网络。寻找合适的模型，一方面允许严格的设计和分析协议，另一方面在实践中是有用的，是一个重大的挑战，值得大量的研究工作。我们将研究无线通信的模型，这些模型涵盖了广泛的物理层现象，并且足够简单，因此它们在理论和实践中都很有用。与之前的算法方法相比，我们的方法将是在对手的帮助下，对物理层问题（如背景噪声、障碍物、干扰器等）引起的通信问题进行建模，并开发可证明对这些对手具有鲁棒性的介质访问（MAC）协议。这种方法有许多有趣的应用。首先，与以前的方法相比，它允许更一般的背景噪音场景，因为它涵盖了可能由于一些临时障碍或机器操作产生干扰而导致的突发情况。其次，对抗性模型还允许我们确定协议对无线干扰攻击的鲁棒性，这是对标准协议的真正威胁，例如802.11家族或简单传感无线设备网络（传统物理层技术无法成功应用）。最后，对抗性模型可以使我们从无线网络中由于远距离设备传输而产生的干扰问题中抽象出来。此外，我们还将重点关注领导人选举和广播等重要应用。由于无线网络是许多广泛和/或关键系统的组成部分，因此拟议的研究将在几个方面产生影响，包括紧急服务、军事和危险区域局域网络的直接应用。此外，拟议的研究还将对巩固与德国帕德博恩大学的国际合作以及促进教育和增强多样性产生影响。

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.