PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things

Liang Liu, Erik G. Larsson, Wei Yu, Petar Popovski, Cedomir Stefanovic, Elisabeth De Carvalho

arXiv:1804.03475v3cs.IT

TL;DR

Massive IoT access must detect a small, unknown active subset among many devices and decode their data with low latency. The paper applies compressed sensing, AMP, and MMV methods to grant-free access, showing that massive MIMO can drive device-detection error to zero asymptotically while also supporting short-message embedding and coded random access.

  • Problem

    Massive IoT connectivity requires dynamically identifying active devices and receiving their data despite sporadic activity.

  • Method

    The paper formulates activity detection as compressed sensing and uses AMP with MMV compressed sensing enabled by massive MIMO.

  • Results

    Massive MIMO with MMV-based AMP can achieve asymptotically perfect device activity detection accuracy.

  • Takeaways & Limitations

    Grant-free access mitigates contention-resolution delay, while short information messages can be embedded in the activity-detection process.

Abstract

from arXiv · show

The next wave of wireless technologies will proliferate in connecting sensors, machines, and robots for myriad new applications, thereby creating the fabric for the Internet of Things (IoT). A generic scenario for IoT connectivity involves a massive number of machine-type connections. But in a typical application, only a small (unknown) subset of devices are active at any given instant, thus one of the key challenges for providing massive IoT connectivity is to detect the active devices first and then to decode their data with low latency. This article outlines several key signal processing techniques that are applicable to the problem of massive IoT access, focusing primarily on advanced compressed sensing technique and its application for efficient detection of the active devices. We show that massive multiple-input multiple-output (MIMO) is especially well-suited for massive IoT connectivity in the sense that the device detection error can be driven to zero asymptotically in the limit as the number of antennas at the base station goes to infinity by using the multiple-measurement vector (MMV) compressed sensing techniques. The paper also provides a perspective on several related important techniques for massive access, such as embedding of short messages onto the device activity detection process and the coded random access.

I. INTRODUCTION

Massive IoT connectivity must support many devices even though only a small, random subset is active at each time. The paper motivates grant-free random access to reduce latency and address collision-limited grant-based access.

  • Motivation: mMTC must transmit data from a massive number of devices efficiently and timely despite sporadic activity.Only a small and random fraction of devices is active at any given time.
  • Grant-Based Random Access: Grant-based access uses staged preamble selection, grants, connection requests, and subsequent data transmission.Devices selecting the same preamble collide and may restart after a timer expires.
  • Grant-Based Random Access: Grant-based random access is limited by collisions, so many users may remain unable to access the network in massive IoT scenarios.The procedure is described as an instance of classical ALOHA with a limit on active devices receiving grants.
  • Grant-Based Random Access: In the example, guaranteeing 90% success requires L = 470 pilot symbols with contention resolution and L = 930 without it.The comparison uses a 100-device active population among 2000 users and a 1000-symbol coherence block.
  • Grant-Free Random Access: Grant-free random access is presented as a low-latency alternative based on advanced compressed sensing techniques.It avoids waiting for a grant before data transmission.

B. Grant-Free Random Access Scheme

Grant-free access lets active devices transmit metadata and data without waiting for permission, but activity detection becomes harder when pilots cannot be orthogonal for all devices. The paper formulates detection as sparse signal processing and develops AMP- and MMV-based approaches, including short-message embedding.

  • Grant-Free Operation: Each device in grant-free access is assigned a unique pilot that also serves as its user ID across time slots.The base station detects used pilots, estimates channels from metadata, and then decodes data.
  • Grant-Free Operation: Metadata and data are transmitted in one step, reducing access latency compared with grant-based access.The active device transmits directly without waiting for permission.
  • Detection Challenge: Activity detection is challenging because massive device populations and limited channel coherence prevent assigning orthogonal pilots to all devices.The resulting large-population activation problem is placed in the realm of sparse signal processing.
  • Compressed-Sensing Approach: The paper casts activity detection as compressed sensing, introduces random pilot design, and proposes AMP for detecting active devices.Massive MIMO enables MMV compressed sensing for asymptotically perfect detection accuracy.
  • Short Messages: A small number of information bits can be embedded in short packets and decoded during the activity-detection process.Devices select pilots from a predefined set, and the base station detects the selected pilots using AMP.

II. DEVICE ACTIVITY DETECTION AS A COMPRESSED SENSING PROBLEM

Sporadic activity creates a sparse recovery problem: the base station must recover effective channels from noisy, underdetermined pilot observations. The paper studies pilot design and compressed-sensing algorithms, emphasizing practical random constructions and AMP.

  • Problem Formulation: Sporadic IoT traffic makes device activity detection a central challenge in grant-free access.The base station must identify active devices while receiving their data.
  • Problem Formulation: The effective channel vector is sparse because each device is active only intermittently.Activity indicators are modeled as Bernoulli variables with device-dependent activation probabilities ϵ_n.
  • Problem Formulation: The base station recovers effective channels from noisy pilot observations to detect active devices and estimate their channels.The observation uses the pilot matrix A, transmit energy ξ, and additive white Gaussian noise.
  • Compressed-Sensing Structure: Because L ≪ N, the system is underdetermined, but sparse structure permits nonlinear compressed-sensing recovery.Limited channel coherence constrains pilot-sequence length.
  • Pilot Design and Algorithms: Pilot design and signal recovery are coupled: carefully designed sensing matrices can make sparse recovery easier.The paper focuses on simple, implementable constructions, including i.i.d. Gaussian sensing matrices and AMP.
  • Pilot Design and Algorithms: Optimizing sensing-matrix design remains challenging, so the article emphasizes simple pilot constructions that are easy to implement.Other choices include sparse-graph sensing and coded slotted ALOHA.

III. AMP-BASED DEVICE ACTIVITY DETECTION

AMP is an efficient iterative thresholding method for large-scale compressed sensing and device activity detection in massive IoT connectivity. Its Gaussian-pilot formulation supports convergence and asymptotic analytical characterization of detection performance.

  • AMP applies iterative thresholding to estimate sparse device activity in large-scale compressed sensing problems.The algorithm updates estimates and residuals, then promotes sparsity through a designed denoiser.
  • State evolution makes AMP detection metrics, including missed detection and false alarm probabilities, analytically characterizable asymptotically.The characterization applies in the asymptotic regime associated with the Gaussian sensing matrix.
  • i.i.d. complex Gaussian pilots with variance 1/L are chosen because they support AMP convergence and established state evolution.The pilot design uses zero-mean entries and variance 1/L.
  • At each iteration, AMP forms an estimate using a denoiser and updates a residual with an Onsager correction.The estimate and residual are indexed by iteration, and the denoiser has a first-order derivative.

2) State Evolution:

State evolution models AMP's effective observations statistically and tracks a scalar state across iterations. This model guides denoiser design and enables performance analysis for different signal distributions.

  • State Evolution: In the asymptotic regime, AMP's denoiser input is statistically equivalent to a signal-plus-Gaussian-noise model.The equivalence applies as L, K, and N grow with fixed limiting ratios.
  • State Evolution: State evolution tracks the scalar state τ_t through an iterative MSE function determined by the signal distribution and denoiser.The random variables X_n describe channel distributions, while V_n is independent complex Gaussian noise.
  • State Evolution: The AMP statistical model supports denoiser design and quantifies algorithm performance.The model is used to design η_t,n(·) and evaluate its behavior.
  • Minimax Framework for Denoiser Design: The minimax framework yields soft thresholding for sparsity when the prior distribution of x is unknown.This design targets the worst-case or least-favorable distribution rather than a particular known distribution.
  • Bayesian Framework for Denoiser Design: For a known signal distribution, the Bayesian MMSE denoiser minimizes estimation MSE through a conditional expectation.Under Rayleigh fading with known β_n, the effective channel follows a Bernoulli-Gaussian distribution.
  • Bayesian Framework for Denoiser Design: For Bernoulli-Gaussian signals, the MMSE denoiser is thresholding-based but softer near the threshold than soft thresholding.Its threshold is selected by minimizing MSE for the particular distribution, whereas soft thresholding uses a minimax design.

5) Analytical Performance Characterization:

State evolution provides analytical missed-detection and false-alarm probabilities for AMP. In the numerical setup, MMSE-based AMP achieves high activity-detection accuracy with shorter pilots than the comparison scheme.

  • Analytical Performance Characterization: State evolution tracks τ_t and yields analytical missed-detection and false-alarm probabilities after AMP convergence.These probabilities are derived from the distribution of the effective observation and the selected denoiser.
  • Analytical Performance Characterization: The system-level error measures aggregate per-device missed-detection and false-alarm probabilities into average event counts per time slot.The aggregate counts are ϵNP_MD and (1−ϵ)NP_FA for a system with N devices.
  • Analytical Performance Characterization: 90% of active devices are detected with MMSE-denoiser AMP when the pilot length satisfies L > 220.The result uses the numerical setup with 2000 devices and 100 active devices on average.
  • Analytical Performance Characterization: The comparison random-access scheme requires pilot length longer than 470 to achieve the same performance, even with contention resolution.This comparison is made against the performance reported for Example 1.
  • Analytical Performance Characterization: MMSE-based AMP outperforms soft-thresholding-based AMP for device activity detection when the MMSE denoiser is carefully designed.The thresholds in both AMP variants are selected so that missed-detection and false-alarm probabilities are equal.

IV. FROM SMV TO MMV: MASSIVE MIMO FOR MASSIVE IOT CONNECTIVITY

Massive MIMO casts device activity detection as an MMV compressed sensing problem, where shared support across antennas provides group-sparsity information. The paper develops an MMV-based AMP framework and examines its asymptotic behavior and detection accuracy.

  • MMV formulation: Massive MIMO turns device activity detection into an MMV problem with jointly sparse signal vectors sharing a common support.The received-signal model uses measurements across the base station’s antennas, while active users determine the common row support.
  • Motivation and scope: The section investigates how massive MIMO affects massive IoT connectivity and quantifies its improvement over a single-antenna base station.The paper positions multi-antenna compressed sensing as a mechanism for accurate activity detection in massive IoT systems.
  • MMV formulation: Row sparsity supplies additional information because zero activity for one entry implies zeros across the corresponding row.This shared structure distinguishes the MMV model from the single-measurement-vector model and can improve user detection.
  • AMP algorithm: The MMV AMP algorithm modifies the denoiser to map M-dimensional vectors and exploit the multi-antenna observation structure.Soft-thresholding and MMSE denoisers can be designed using the MMV state evolution.
  • AMP algorithm: MMV AMP state evolution holds asymptotically as L, K, and N grow with fixed ratios N/L → ω and K/N → ϵ.The effective scalar-plus-Gaussian characterization supports analytical design and evaluation of the denoisers.

B. Asymptotically Perfect Device Activity Detection

The paper analyzes AMP-based activity detection with massive MIMO and shows that detection can become perfect asymptotically as the antenna count increases. Numerical results further show very low error probabilities with moderate pilot lengths.

  • Asymptotic result: As M → ∞, missed detection and false alarm probabilities converge to zero when device-detection thresholds are properly selected.This establishes asymptotically perfect device activity detection in the massive-MIMO regime.
  • Numerical example: The MIMO result requires several orders of magnitude fewer pilot symbols than the SMV case at the same error level and L.The comparison is reported for the MMSE-denoiser-based AMP algorithm and antenna counts M = 16, 32, and 64.
  • Broader system implications: AMP state evolution analytically characterizes channel-estimation performance and permits user achievable rates to be quantified with activity-detection effects included.The section focuses primarily on activity detection but connects the analysis to subsequent channel estimation and decoding.

V. AMP-BASED DEVICE ACTIVITY DETECTION WITH EMBEDDED INFORMATION

The paper considers embedding very short messages into the activity-detection process rather than decoding them in a separate coherent-data stage. This targets settings where messages contain only a few bits and conventional capacity-oriented analysis is inadequate.

  • Embedded information: A modified AMP algorithm performs non-coherent detection of information bits embedded in pilot transmission.The approach is presented as an alternative to the two-phase grant-free scheme for very short messages.
  • Use cases: The embedded-bit strategy is intended for messages containing one or several bits, including acknowledgments or concise requests to the base station.These examples motivate integrating message information with activity detection.
  • Motivation: Very short packets are difficult because error protection is expensive and capacity is irrelevant when only error probability matters.For a single bit, repetition coding is described as the only possible strategy; finite-block-length theory may also become inapplicable for extremely short blocks.
  • Motivation: Control-plane transmissions commonly use short data blocks, whereas much academic work emphasizes long coded blocks and Shannon capacity.The paper identifies a mismatch between common theoretical metrics and short-message control signaling.

B. Algorithm Design

The algorithm jointly detects activity and embedded bits by assigning multiple possible pilots while enforcing that at most one pilot per device is active. A modified soft denoiser uses likelihood-based weights, but the proposed denoiser is not known to be optimal.

  • System model: Embedding J bits enlarges the sensing matrix and effective-channel dimensions by a factor of 2^J, using one pilot among 2^J device-specific options.Each pilot corresponds to a bit string through the mapping 1 + b1 + 2b2 + 4b3 + ··· + 2^(J−1)bJ.
  • System model: The model constrains each active device to transmit at most one of its assigned pilots at a time.For J = 1, the receiver distinguishes silence, activity with bit 0, and activity with bit 1.
  • Joint detection: The modified AMP denoiser jointly detects activity and embedded information by incorporating the one-active-pilot constraint.The resulting activity variable represents both terminal activity and the communicated J-bit string.
  • Denoiser design: Likelihood-ratio weights from a modified sigmoid softly favor one candidate pilot while suppressing the other.Soft decisions are preferred to avoid premature incorrect bit decisions propagating through later iterations.
  • Limitation: The modified denoiser yields good numerical results but is not optimal in any known sense.Improved denoisers could better exploit the constraint that at most one candidate channel is nonzero.
  • Trade-off: Embedding information requires storing more pilot sequences and allocating more pilot resources to maintain the same error probability.The paper nevertheless reports efficiency for very short messages relative to conventional pilot-based channel estimation followed by coherent detection.

VI. OTHER COMPRESSED SENSING TECHNIQUES FOR DEVICE ACTIVITY DETECTION

The paper surveys compressed sensing methods for device activity detection, emphasizing sparse-graph designs that enable iterative recovery through singleton measurements. It also connects this procedure to coded random access and identifies practical criteria for comparing algorithms.

  • Algorithm comparison: Compressed sensing algorithms for device activity detection should be compared by pilot design complexity, required pilot length, detection errors, and channel estimation performance.The paper mentions AMP, LASSO, OMP, and group-sparse MMV formulations among the available approaches.
  • Sparse-graph compressed sensing: Sparse-graph compressed sensing designs the sensing matrix with zero patterns guided by sparse-graph codes.The design disperses the signal into singleton measurements that contain one non-zero element.
  • Sparse-graph compressed sensing: The peeling procedure removes decoded components from collided measurements, allowing additional non-zero entries to be recovered.The example explicitly detects x6 after x3 is removed from y3.
  • Sparse-graph compressed sensing: In a noiseless example with N = 7 and L = 3, singleton measurements successively reveal x1, x3, and x6.After detecting x1 from y1, subtracting it from other measurements creates new singletons for decoding.
  • Sparse-graph compressed sensing: Density evolution tracks the average density of undecoded edges across peeling iterations, with convergence toward zero guaranteeing algorithmic convergence.This provides a coding-theoretic tool for analyzing the recovery process.
  • Coded random access: The successive interference cancellation principle parallels coded slotted ALOHA, where detecting one packet replica enables removal of its other replicas.Removing replicas lowers collisions in affected slots and can initiate further cancellation rounds.

VII. CONCLUSIONS

The conclusion advocates grant-free access for massive IoT, using compressed sensing to detect active devices while reducing contention-resolution delay. It highlights massive MIMO with MMV-based AMP as especially effective and points to embedding short messages into activity detection.

  • Motivation: Massive IoT connects many sensors and actuators with sporadic traffic, creating stringent low-latency signal-processing challenges.Only a subset of devices is active in each time slot.
  • Grant-free access: Grant-free access lets devices transmit without the contention-resolution delay of current random access, with compressed sensing supporting activity detection.The article advocates this scheme and outlines a compressed-sensing-based approach for making it work.
  • Massive MIMO: Massive MIMO, aided by an MMV-based AMP algorithm, can substantially improve device activity detection accuracy in massive IoT connectivity.The conclusion identifies this as a principal benefit of applying massive MIMO beyond human-type communications.
  • Additional capabilities: The paper also discusses decoding short messages together with device activity detection.This extends the activity-detection process beyond identifying which devices are active.
Loading 1804.03475v3…