Random Access: An Information-Theoretic Perspective

This paper considers a random access system where each sender is in one of two possible states, active or not active, and the states are only known to the common receiver. Active senders encode data into independent information streams, a subset of which is decoded depending on the collective interference. An information-theoretic formulation of the problem is presented and the set of achievable rates is characterized with a guaranteed gap to optimality. Inner and outer bounds on the capacity region of a two-sender system are tight in the case of a binary-expansion deterministic channel and differ by less than one bit in the case of a Gaussian channel. In systems with an arbitrary number of senders, the symmetric scenario of equal access probabilities and received power constraints is studied and the system throughput, i.e., the maximum achievable expected sum rate, is characterized. It is shown that a simple coding scheme where active senders transmit a single message is optimum for a binary-expansion deterministic channel and achieves within one bit of the optimum in the case of a Gaussian channel. Finally, a comparison with the slotted ALOHA protocol is provided, showing that encoding rate adaptation at the transmitters achieves constant (rather than zero) throughput as the number of users tends to infinity.