Collision Resolution for Random Access

As a building block toward a simple and scalable solution for massive random access, we introduce collision-resolution algorithms using successive interference cancellation (SIC) based on the received signals, with no need for any coordination or codebook differentiation. We first consider two-user multiple access with the ZigZag algorithm. We prove that the original ZigZag and a modified version of it, called double-zipper ZigZag, attain the same performance as the optimal coordinated time-sharing in the high signal to noise ratio (SNR) regime, even in the presence of channel state information (CSI) errors. We then extend the results to the case of arbitrary number of users employing delay-domain processing. Specifically, we introduce delay-domain zero forcing and its regularized version, which are able to cancel and suppress the interference among users, respectively. By obtaining a post-processing system model and characterizing the accumulated noise during the decoupling process, we also derive bounds on the achievable sum-rates of the proposed algorithm for both cases of perfect and imperfect CSI. Simulation results show that the newly proposed approach have comparable performance with coordinated time-sharing at high SNRs.