CCF-AF: Abstract Medium Access Control Layers

无线网络算法和下界的研究由于网络行为假设的多样性和复杂性而变得复杂，例如，关于时间同步、设备可靠性和移动性、信号传播特性和传输冲突。本项目将通过定义无线网络中介质访问控制（MAC）层的简单抽象模型来简化本研究。这些层将提供可靠的本地广播通信，其延迟受本地争用功能的限制。算法设计者应该能够根据这些抽象层开发和分析算法，独立于物理网络行为和MAC层实现，但在物理网络方面获得真实的结果。同样，理论家应该能够使用这些层来证明简单但有意义的下界。具体来说，该项目将定义和评估几个可能的抽象MAC层，根据它们的保证是最坏情况还是概率，它们如何模拟信号传播特性，以及它们在故障和其他网络变化的存在下确保什么而变化。它将演示如何在物理无线网络中实现这些层，使用各种竞争管理方法，如载波感知、碰撞检测、随机传输和回退以及网络编码。它将利用这些层来研究无线网络中的许多问题，包括邻居发现和区域领导者选举等基本问题；中间问题，如全网通信、网络结构维护和资源分配；以及机器人控制和数据管理应用中出现的高级问题。

The study of algorithms and lower bounds for wireless radio networks is complicated by the diversity and complexity of assumptions about network behavior, for example, about time synchronization, device reliability and mobility, signal propagation characteristics, and transmission collisions. This project will simplify this study by defining simple abstract models for Medium Access Control (MAC) layers in wireless networks. These layers will provide reliable local broadcast communication, with delays that are bounded by functions of the local contention. Algorithm designers should be able to develop and analyze algorithms in terms of these abstract layers, independently of the physical network behavior and the MAC layer implementation, yet obtain results that are realistic in terms of the physical networks. Likewise, theoreticians should be able to use these layers to prove simple but meaningful lower bounds.Specifically, the project will define and evaluate several possible abstract MAC layers, varying according to whether their guarantees are worst case or probabilistic, how they model signal propagation characteristics, and what they ensure in the presence of failures and other network changes.It will demonstrate how these layers can be implemented in physical radio networks, using a variety of contention-management methods such as carrier-sensing, collision detection, random transmission and backoff, and network coding. It will use these layers to study many problems in wireless networks,including basic problems such as neighbor discovery and regionalleader election; intermediate problems such as network-wide communication, maintenance of network structures, and resource allocation; and high-level problems that arise in robot control and data-management applications.