Order-optimal Joint Transmission and Identification in Massive Multi-User MIMO via Group Testing

Abstract

The number of wireless devices which are connected to a single Wireless Local Area Network continues to grow each year. As a result, the orchestration of so many devices becomes a daunting, resource–consuming task, especially when the resources available at the single access point are limited, and it is hard to anticipate which devices will request access at any given time. On the other hand, the number of antennas on both the devices and the access point grows as well, facilitating advanced joint scheduling and coding techniques.

In this paper, we leverage the large number of antennas and suggest a massive multiple-user multiple-input-multiple-output (MU-MIMO) scheme using sparse coding based on Group Testing (GT) principles. The scheme allows for a small subset of devices to transmit simultaneously, without a preceding scheduling phase or coordination, thus reducing overhead and complexity. Specifically, we show that out of a population of $N$ devices, it is possible to jointly identify and decode $K$ devices, unknown in advance, simultaneously and without any scheduling. The scheme utilizes minimal knowledge of channel state, uses an efficient (in both run-time and space) decoding algorithm, and requires $O(K\log NC)$ antennas, where $C$ is the number of messages per device. In fact, we prove that this scheme is order–optimal in the number of users and messages. This is done by deriving sufficient conditions for a vanishing error probability (a direct result), bounding the minimal number of antennas necessary for any such scheme (a converse result), and showing that these results are asymptotically tight.