Random Access over Multi-Packet Reception Channels: A Mean-Field Approach

Thesis (Ph.D.)--University of Washington, 2016-06

This thesis addresses the problem of Multi-Packet Reception (MPR) for random access scenarios in Wireless LAN type infrastructure network. Our results builds on a recently proposed physical-layer network coding mechanism – Compute-and-Forward (C&F); we embed this within slotted ALOHA and Carrier Sense Multiple Access (CSMA) protocols for operational scenarios where multiple simultaneous transmissions are likely to occur. A mean-field approach is used to understand the impact of multi-packet reception in random access networks. By focusing on a special family of MPR channels – the all-or-nothing model, stability conditions are derived for slotted ALOHA and CSMA systems under the above assumption. Interestingly, a number of physical-layer network coding schemes such as compute-and-forward, successive compute-and-forward (SCF) and successive interference cancellation can be viewed as special cases of all-or-nothing symmetric MPR model. In addition, the problem is analyzed under the general symmetric MPR channels which turns out not to be fundamentally different from the all-or-nothing MPR. The primary outcome is a deeper understanding of the behavior of random access schemes over general symmetric MPR channels. Due to the interaction among users and the challenges emanating from such interactions, random access can be more readily analyzed if the state of users are assumed decoupled and an approximate stability region obtained for the system. Nonetheless, the approximate stability region computation based on the decoupling assumption is still complicated for even small (few clients) networks. By a mean-field approach, the random access problem is studied in the large number of clients regime. As a result, the evolution of the system state in the limit can be well approximated by a deterministic dynamical system. The stability conditions for the limiting system then paves the way for a better understanding of a known/observed phenomenon called meta-stability whereby (finite) random-access networks undergo a phase transition: from stability to meta-stability. In the thesis, we first present results for slotted ALOHA with all-or-nothing MPR model. An approximate stability region is characterized which is then used for system performance evaluation in terms of throughput and delay. These results are then extended to the case of general symmetric MPR channels. Next, the stability of persistent CSMA systems is analyzed similar to slotted ALOHA analysis and throughput and delay results are obtained. Meta-stability is discussed for CSMA systems and system design guidelines are outlined to guarantee certain quality-of-service requirements, i.e., avoidance of meta-stable behavior. By adding a back-off mechanism, the stationary behavior of a saturated system is studied, again through mean-field analysis. Finally, we propose a novel extension to the cooperating multiple AP scenario for dense networks, where we present new algorithms for MPR-capable systems and present some initial analysis.