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.
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.
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