An Efficient Active Set Algorithm for Covariance Based Joint Data and Activity Detection for Massive Random Access with Massive MIMO

Ziyue Wang, Zhilin Chen, Ya-Feng Liu, Foad Sohrabi, Wei Yu

Abstract

This paper proposes a computationally efficient algorithm to solve the joint data and activity detection problem for massive random access with massive multiple-input multiple-output (MIMO). By formulating the detection as a maximum likelihood estimation (MLE) problem and exploiting the inherent sparsity of device activity, we design a novel iterative active set algorithm. At each iteration, the algorithm focuses on a small subset of likely active sequences, significantly reducing complexity. Simulation results demonstrate that the proposed algorithm achieves superior computational efficiency compared to state-of-the-art methods.

Introduction

In the era of 5G and the Internet of Things (IoT), base stations must manage "massive random access" from thousands of devices transmitting sporadic, small data bursts. Traditional grant-based protocols are inefficient due to high signaling overhead. Grant-free access, where devices transmit unique signature sequences, offers a solution but introduces a complex joint data and activity detection problem. While covariance-based MLE is a robust approach, existing solvers like Coordinate Descent (CD) scale poorly as the number of potential devices grows into the tens of thousands.

The Active Set Spectral Projected Gradient Algorithm

The proposed approach leverages the fact that only a small fraction of devices are active at any time. The algorithm, termed Active Set Spectral Projected Gradient (PG), operates through three main stages:

  1. Active Set Selection: Instead of updating all potential device sequences, the algorithm selects an "active set" based on current power estimates and first-order optimality conditions (gradients).
  2. Subproblem Optimization: The optimization is restricted to this active set and solved using a Spectral PG method. This incorporates Barzilai-Borwein (BB) stepsizes to approximate second-order information, accelerating convergence without high computational costs.
  3. Iterative Refinement: The active set is dynamically updated until global first-order optimality conditions are satisfied.
Active set size ratio and iteration count vs. total number of users.

As shown in the performance metrics, the ratio of the active set size to the number of truly active devices remains consistently low (between 1.5 and 2.5), and the algorithm typically converges within just 4 to 7 iterations.

Performance Evaluation

Numerical simulations were conducted in a single-cell system with $M=256$ antennas and $L=150$ length signature sequences. The total number of devices $N$ ranged up to 10,000, with a constant 10% activity ratio.

The results highlight a significant reduction in CPU time. For $N=10,000$, the Active Set PG algorithm requires approximately 4 seconds, compared to over 10 seconds for standard Random Coordinate Descent. Furthermore, the algorithm's performance closely tracks "ideal" benchmarks where activity is known a priori.

CPU time comparison between the proposed Active Set PG and other algorithms.

Conclusion

The proposed active set algorithm effectively utilizes sparsity to solve large-scale joint detection problems in mMTC. By focusing computational effort on the most relevant variables, it provides a scalable and efficient solution for future massive MIMO systems. Future work will focus on providing global optimality guarantees and testing under diverse channel conditions.

Summary updated

Abstract

This paper proposes a computationally efficient algorithm to solve the joint data and activity detection problem for massive random access with massive multiple-input multiple-output (MIMO). The BS acquires the active devices and their data by detecting the transmitted preassigned nonorthogonal signature sequences. This paper employs a covariance based approach that formulates the detection problem as a maximum likelihood estimation (MLE) problem. To efficiently solve the problem, this paper designs a novel iterative algorithm with low complexity in the regime where the device activity pattern is sparse $\unicode{x2013}$ a key feature that existing algorithmic designs have not previously exploited for reducing complexity. Specifically, at each iteration, the proposed algorithm focuses on only a small subset of all potential sequences, namely the active set, which contains a few most likely active sequences (i.e., transmitted sequences by all active devices), and performs the detection for the sequences in the active set. The active set is carefully selected at each iteration based on the current detection result and the first-order optimality condition of the MLE problem. Simulation results show that the proposed active set algorithm enjoys significantly better computational efficiency (in terms of the CPU time) than the state-of-the-art algorithms.
BibTeX
@inproceedings{wang2021efficient,
  author = {Ziyue Wang and Zhilin Chen and Ya-Feng Liu and Foad Sohrabi and Wei Yu},
  title = {{An Efficient Active Set Algorithm for Covariance Based Joint Data and Activity Detection for Massive Random Access with Massive MIMO}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=wqpejLcnBBs},
}
Figure