Low-Complexity Block Coordinate Descend Based Multiuser Detection for Uplink Grant-Free NOMA

Pengyu Gao, Zilong Liu, Pei Xiao, Chuan Heng Foh, Jing Zhang

Abstract

Grant-free non-orthogonal multiple access (NOMA) is considered a promising candidate for enabling massive connectivity and reduced signaling overhead for Internet of Things (IoT) applications in massive machine-type communication (mMTC) networks. Exploiting the inherent nature of sporadic transmissions in grant-free NOMA systems, compressed sensing-based multiuser detection (CS-MUD) has been deemed a powerful solution to user activity detection (UAD) and data detection (DD). In this paper, the block coordinate descent (BCD) method is employed in CS-MUD to reduce computational complexity. We propose two modified BCD-based algorithms: enhanced BCD (EBCD) and complexity reduction enhanced BCD (CR-EBCD). By incorporating a novel candidate set pruning mechanism into the original BCD framework, our proposed EBCD algorithm achieves remarkable CS-MUD performance improvement. Furthermore, the proposed CR-EBCD algorithm ameliorates EBCD by eliminating redundant matrix multiplications during the iteration process. Compared with EBCD, the CR-EBCD algorithm enjoys a two-order-of-magnitude complexity saving without any performance degradation, rendering it a viable solution for future mMTC scenarios.

Introduction

In the era of 5G and 6G, the industry is shifting toward massive Machine-Type Communication (mMTC), where millions of IoT devices transmit small packets sporadically. Traditional grant-based protocols—where a device requests permission to send data—are too slow and create massive signaling overhead for such tiny bursts. Grant-free Non-Orthogonal Multiple Access (NOMA) allows devices to transmit whenever they want, sharing the same frequency resources.

However, this creates a significant challenge for the Base Station (BS). The BS receives a collision of signals and must simultaneously solve two problems: User Activity Detection (UAD) to identify which devices are active, and Data Detection (DD) to decode the actual message. This is typically treated as a Compressed Sensing (CS) problem. While existing greedy algorithms like Subspace Pursuit (SP) work, they often require heavy matrix inversions, making them computationally expensive for real-time use.

Uplink grant-free NOMA system model with sporadic user activity.

Proposed Methodology

The authors propose a solution based on Block Coordinate Descent (BCD), an optimization technique that updates variables sequentially rather than all at once. They introduce two specific algorithms to refine this process:

Enhanced BCD (EBCD)

EBCD introduces a candidate set pruning mechanism. During the initial iterations, the algorithm identifies users with very low estimated signal power and "prunes" them (sets their values to zero). This removes interference early on, allowing the algorithm to focus its computational resources on the truly active users. This pruning acts as a form of interference mitigation, as estimating the signal of an inactive user is essentially trying to reconstruct noise.

Complexity Reduction Enhanced BCD (CR-EBCD)

CR-EBCD is the refined version of EBCD designed for ultra-low complexity. The authors observed that standard BCD involves redundant matrix-vector multiplications in every iteration. They derived a recursive update rule that allows the BS to update the "residual" signal using simple vector additions and subtractions, avoiding large-scale matrix math entirely. This transforms a high-order complexity problem into a much simpler linear update.

Key Results and Discussion

The proposed algorithms were tested in a simulation environment with $K=200$ potential users and $N=100$ subcarriers, where only 18–20 users were active at any given time. The results demonstrate that the CR-EBCD algorithm achieves Symbol Error Rate (SER) performance that nearly matches the "Oracle LS" bound—the theoretical limit where the base station already knows exactly which users are active.

Performance comparison: (a) SER vs SNR and (b) Computational complexity of various algorithms.

As shown in the figures above, CR-EBCD provides a two-order-of-magnitude (100x) reduction in computational complexity compared to the EBCD version and is significantly lighter than other popular benchmarks like TA-BSASP or SA-BGP. Unlike greedy algorithms whose complexity explodes as more users become active, CR-EBCD remains relatively stable, making it "future-proof" for denser IoT environments.

Conclusion

This research introduces a highly efficient multiuser detection framework for grant-free NOMA systems. By combining BCD with a novel pruning mechanism and recursive updates, the authors achieve near-optimal detection accuracy while drastically reducing computational overhead. Future work will focus on relaxing synchronization assumptions and integrating deep learning to handle high-mobility IoT scenarios and non-ideal channel conditions.

Summary updated

Abstract

Grant-free non-orthogonal multiple access (NOMA) scheme is considered as a promising candidate for the enabling of massive connectivity and reduced signalling overhead for Internet of Things (IoT) applications in massive machine-type communication (mMTC) networks. Exploiting the inherent nature of sporadic transmissions in the grant-free NOMA systems, compressed sensing based multiuser detection (CS-MUD) has been deemed as a powerful solution to user activity detection (UAD) and data detection (DD). In this paper, block coordinate descend (BCD) method is employed in CS-MUD to reduce the computational complexity. We propose two modified BCD based algorithms, called enhanced BCD (EBCD) and complexity reduction enhanced BCD (CR-EBCD), respectively. To be specific, by incorporating a novel candidate set pruning mechanism into the original BCD framework, our proposed EBCD algorithm achieves remarkable CS-MUD performance improvement. In addition, the proposed CR-EBCD algorithm further ameliorates the proposed EBCD by eliminating the redundant matrix multiplications during the iteration process. As a consequence, compared with the proposed EBCD algorithm, our proposed CR-EBCD algorithm enjoys two orders of magnitude complexity saving without any CS-MUD performance degradation, rendering it a viable solution for future mMTC scenarios. Extensive simulation results demonstrate the bound-approaching performance as well as ultra-low computational complexity.
BibTeX
@article{gao2022low,
  author = {Pengyu Gao and Zilong Liu and Pei Xiao and Chuan Heng Foh and Jing Zhang},
  title = {{Low-Complexity Block Coordinate Descend Based Multiuser Detection for Uplink Grant-Free NOMA}},
  journal = {IEEE Transactions on Vehicular Technology},
  year = {2022},
  doi = {10.1109/tvt.2022.3177784},
}
Figure