A Group Testing Approach to Random Access for Short-Packet Communication

We propose a grant-free random access scheme for short-packet communication on a collision channel without feedback, where user identities are conveyed through their activity patterns. We show that this problem is inherently related to the non-adaptive group testing problem, where the goal is to identify a small subset of defective items within a larger population, using as few (pre-determined) tests as possible. In the frame-synchronous case, where users' transmissions are aligned, we find that any solution to the non-adaptive group testing problem is also a solution to the random access problem. Similar connections to group testing are identified in the asynchronous variant of the problem, in which case users' transmissions within a frame are received with arbitrary and unknown delays at the receiver. We show that such delays can be accommodated without any additional penalty with respect to the scaling of the transmission length, and that in the regime where the data payload is small, the performance of the proposed random access scheme comes close to that of fully coordinated access schemes.