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.
