CIF: Small: Information and Coding Theory for Random Access

WiFi热点和蜂窝基站等接入点对于无线设备来说是网络的网关。因此，接入点也是网络最关键的瓶颈。阻塞点在上行链路中尤其严重，其中来自潜在未知数量的发射机的潜在干扰接收信号的混沌混合必须在跨网络传输之前被解纠缠。挑战是多方面的：接入点是随机接入信道，但是只有当发射机的数量和身份是固定的并且已知时，多发射机信道才在信息理论中被很好地理解。接入点必须高效且高速地运行，但即使对于固定数量的发射机，最优多址码也太复杂而难以实现，并且高效码是未知的。随着越来越多的不同设备变得依赖于网络，通信设备的数量和它们的通信需求的多样性都在增长，但是关于如何在通信器的数量和种类的高度变化下编码却知之甚少。目前的协议不适合应对这些挑战。大多数依赖于冲突避免，这是通过通信设备之间的协调和调度或通过使用随机传输时间和退避调度来实现的，当避免冲突的尝试失败时进行重新传输。这些策略是已知的是严重次优，但随机接入信道的一般理论和低复杂度的代码，以实现该理论在实践中目前是不可用的。本文的目标是建立一个通用的随机接入信道的理论和实用码，主要包括三个方面：（1）随机接入的编码理论方法，其目标是设计低复杂度的随机接入码，使其在有和没有信道状态信息的情况下都能达到理论所承诺的性能;（2）随机接入的信息论方法，其目的是将现有的理论从多路接入推广到随机接入信道码，特别关注无速率码和对未知或变化的信道特性的鲁棒性;以及（3）桥接信息和编码理论，它汇集了信息理论工具和新的编码策略，在前两个推力开发低复杂度的可变速率码，并使信息理论分析的代码与约束的复杂性和/或延迟。该奖项反映了NSF的法定使命，并且通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Access points like WiFi hot spots and cellular base stations are, for wireless devices, the gateway to the network. Accordingly, access points are also the network's most critical bottleneck. The choke point is especially severe in the uplink, where a chaotic mix of potentially interfering received signals from a potentially unknown number of transmitters must be disentangled prior to transmission across the network. The challenges are myriad: an access point is a random access channel, but multiple-transmitter channels are well understood in information theory only when the number and identity of transmitters is fixed and known. Access points must run efficiently and at high speed, but even for a fixed number of transmitters optimal multiple access codes are too complex to implement, and efficient codes are unknown. As more and different devices become network-reliant, both the number of communicating devices and the diversity of their communication needs grow, yet little is known about how to code under high variation in the number and variety of communicators. The protocols currently in place are ill-suited to handling these challenges. Most rely on collision avoidance, which is achieved either through coordination and scheduling among communicating devices or by using random transmission times and back-off schedules for re-transmission when attempts to avoid collisions fail. These strategies are known to be grossly suboptimal, but both a general theory for random access channels and low-complexity codes to implement that theory in practice are currently unavailable. The goal of this work to build a generalized theory and practical codes for random access channels.The work is organized into three thrusts: (1) a coding-theoretic approach to random access, whose goal is to design low-complexity codes for random access that approach the performance promised by the theory, with and without channel state information; (2) an information-theoretic approach to random access, which aims to generalize existing theory from multiple access to random access channel codes, with particular focus on rateless codes and robustness to unknown or varying channel characteristics; and (3) bridging information and coding theories, which brings together the information theoretic tools and new coding strategies developed in the previous two thrusts to develop low-complexity variable-rate codes and to enable information theoretic analysis of codes with constraints on complexity and/or delay.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.