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.