Throughput Analysis for Parallel Decoding of Irregular Repetition Slotted ALOHA With Noise

Due to its simplicity and scalability, the Irregular Repetition Slotted ALOHA (IRSA) system that uses the successive interference cancellation (SIC) technique is a promising solution for uncoordinated multiple access of a massive number of Internet-of-Things (IoT) devices. In this paper, we propose two parallel decoding algorithms for IRSA in an additive white Gaussian noise channel. Our first algorithm is limited to SIC-decoupling matrices that correspond to the SIC decoding process in IRSA. For this, we propose a message-passing algorithm to find the optimal SIC-decoupling matrix that can minimize the accumulated noise power when the induced user-slot bipartite graph of an IRSA system is acyclic. This includes the Contention Resolution Diversity Slotted ALOHA (CRDSA) system that sends exactly two copies for each packet as a special case. Our second algorithm extends the first one by finding the optimal decoupling matrix for CRDSA through an optimal combination of two SIC-decoupling matrices. Using a random graph analysis, we derive the throughput for the two parallel decoding algorithms of CRDSA in a threshold-based decoding model. We then conduct various numerical experiments to illustrate the tradeoffs between sequential decoding with a limited number of iterations and parallel decoding with a predefined signal-to-noise ratio (SNR) threshold. Finally, we demonstrate how to extend our parallel decoding scheme to bipartite graphs with cycles.