Contention Resolution for Coded Radio Networks
Contention Resolution for Coded Radio Networks
复制标题
DOI：
10.1145/3490148.3538573
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
M. A. Bender;Seth Gilbert;F. Kuhn;John Kuszmaul;M. Médard
中科院分区：
文献类型：
--
作者：
M. A. Bender;Seth Gilbert;F. Kuhn;John Kuszmaul;M. Médard
随机回退协议，例如指数回退，是管理对共享资源（通常是无线通信通道（例如[1]））访问的强大工具。为了使无线设备成功传输，它使用回退协议来确保对信道的独占访问。然而，现代无线电不需要独占信道来通信；特别是，即使有多个设备同时传输，它们也有能力接收有用的信息。这些功能已经被许多系统利用多年，这些系统依赖于干扰消除、物理层网络编码和模拟网络编码来提高效率。例如，Zigzag解码[56]演示了基站如何解码由多个设备同时发送的消息。在本文中，我们解决了以下问题：当不需要独占通道访问时，我们能否设计一个比指数回退更好的回退协议？我们定义了编码无线网络模型，它概括了传统的无线网络模型（例如，[30]）。然后，我们介绍了可解码回退算法，这是一种随机回退协议，可实现1 - 0(1)的最佳吞吐量。（吞吐量1是最佳的，因为同时接收不会增加信道容量。）该算法打破了传统无线网络的恒定吞吐量下限[47-49]，显示了这些新硬件功能的强大。
Randomized backoff protocols, such as exponential backoff, are a powerful tool for managing access to a shared resource, often a wireless communication channel (e.g., [1]). For a wireless device to transmit successfully, it uses a backoff protocol to ensure exclusive access to the channel. Modern radios, however, do not need exclusive access to the channel to communicate; in particular, they have the ability to receive useful information even when more than one device transmits at the same time. These capabilities have now been exploited for many years by systems that rely on interference cancellation, physical layer network coding and analog network coding to improve efficiency. For example, Zigzag decoding [56] demonstrated how a base station can decode messages sent by multiple devices simultaneously. In this paper, we address the following question: Can we design a backoff protocol that is better than exponential backoff when exclusive channel access is not required. We define the Coded Radio Network Model, which generalizes traditional radio network models (e.g., [30]). We then introduce the Decodable Backoff Algorithm, a randomized backoff protocol that achieves an optimal throughput of 1 - o (1). (Throughput 1 is optimal, as simultaneous reception does not increase the channel capacity.) The algorithm breaks the constant throughput lower bound for traditional radio networks [47-49], showing the power of these new hardware capabilities.