Source-linked AI summary
High Throughput Random Access via Codes on Graphs: Coded Slotted ALOHA
Enrico Paolini, Gianluigi Liva, Marco Chiani
TL;DR
Repetition-based random access can improve throughput, but it increases average transmitted power, motivating power-efficient alternatives. This paper introduces CSA, which locally codes burst segments and combines decoding with iterative interference cancellation, then analyzes and designs schemes using density evolution. Its threshold comparisons favor CSA at some rates and IRSA at the lowest rate considered, while simulations closely match the asymptotic analysis.
Problem
Repetition-based access schemes improve throughput but increase average transmitted power, leaving a need for power-efficient random access.
Source: §I · p. 1Method
CSA encodes burst segments with local codes and combines local decoding with iterative interference cancellation, analyzed through density evolution.
Source: §I · p. 1, §II · p. 2Results
CSA has better thresholds than IRSA at rates R = 1/2 and R = 2/5, while IRSA has a better threshold at R = 1/3; simulations closely match asymptotic analysis.
Source: §V · p. 6Takeaways & Limitations
CSA is promising when power efficiency is required, and its rate can exceed 1/2, unlike IRSA under the stated scheme assumptions.
Source: §VI · p. 6, §V · p. 6
Abstract
from arXiv · showhide
In this paper, coded slotted ALOHA (CSA) is introduced as a powerful random access scheme to the MAC frame. In CSA, the burst a generic user wishes to transmit in the MAC frame is first split into segments, and these segments are then encoded through a local a packet-oriented code prior to transmission. On the receiver side, iterative interference cancellation combined with decoding of the local code is performed to recover from collisions. The new scheme generalizes the previously proposed irregular repetition slotted ALOHA (IRSA) technique, based on a simple repetition of the users' bursts. An interpretation of the CSA interference cancellation process as an iterative erasure decoding process over a sparse bipartite graph is identified, and the corresponding density evolution equations derived. Based on these equations, asymptotically optimal CSA schemes are designed for several rates and their performance for a finite number of users investigated through simulation and compared to IRSA competitors. Throughputs as high as 0.8 are demonstrated. The new scheme turns out to be a good candidate in contexts where power efficiency is required.
I. INTRODUCTION
Random-access schemes improve throughput through burst repetition and interference cancellation, but repetition can increase average transmitted power. CSA replaces simple repetition with local coding and combines local-code decoding with iterative interference cancellation.
I. INTRODUCTION
- DSA transmits each burst twice, slightly improving throughput over slotted ALOHA while doubling average transmitted power at the same peak power.Source: §I · p. 1
- CRDSA uses pointers to locate burst replicas and iteratively cancels interference after a clean burst is decoded.The procedure may recover all bursts in a MAC frame.Source: §I · p. 1
- IRSA improves throughput over CRDSA through a judiciously designed variable repetition rate, but performance gains come with increased average transmitted power.Source: §I · p. 1
- CSA encodes bursts with local codes and combines their decoding with iterative interference cancellation to recover collisions.The paper derives density-evolution equations and uses them to design access schemes.Source: §I · p. 1
II. SYSTEM MODEL
CSA splits each burst into information segments, encodes them with a randomly selected local code, and sends the resulting encoded segments in randomly selected slots. The receiver models transmissions as a bipartite graph and iteratively combines interference cancellation with local erasure decoding.
II. SYSTEM MODEL
- Each burst is split into k information segments and encoded into n_h segments by a randomly chosen packet-oriented binary linear block code.Each encoded segment has duration T_CSA = T_SA/k.Source: §II · p. 2
- Encoded segments are sent in randomly selected slots; CSA's rate is R = k/ n̄, and its average-power increment over pure slotted ALOHA is ΔP = 1/R.IRSA is the special case k = 1 with repetition codes, while slotted ALOHA is the case n_h = 1 for all users.Source: §II · p. 2
- In the bipartite graph, burst nodes represent users, slot nodes represent slots, and edges represent transmitted encoded segments.A burst-node degree is the local code length; a slot-node degree is the number of colliding encoded segments.Source: §II · p. 2, Figure 1 · p. 2
- The analysis assumes high SNR, ideal channel estimation, and destructive collisions, treating collided segments as erasures.Under the first two assumptions, clean segments are known and ideal interference cancellation is possible.Source: §II · p. 2
- Local erasure decoding recovers unknown segments, whose interference is cancelled so that other collided segments may become known in subsequent iterations.The resulting process is equivalent to iterative decoding of a D-GLDPC code over an erasure channel.Source: §II · p. 2
- The normalized throughput S is the probability of successful packet transmission per time slot.Source: §II · p. 2
III. DENSITY EVOLUTION, THRESHOLD, AND STABILITY
The paper derives density-evolution updates for the iterative decoding process and defines the asymptotic threshold as the largest offered traffic for which decoding succeeds. That threshold equals the asymptotic peak throughput.
III. DENSITY EVOLUTION, THRESHOLD, AND STABILITY
- The slot-degree distribution is obtained from random slot selection and expressed from node and edge perspectives.The probability that a slot has degree d is Ψ_d; the edge-perspective distribution is denoted ρ_d.Source: §III · p. 3
- The burst-node update is derived for MAP decoding using the local code's information functions.The analysis considers the asymptotic setting as the number of users grows without bound.Source: §III · p. 3
- The slot-node update follows density evolution for irregular LDPC codes over the erasure channel.Source: §III · p. 3
- Density evolution tracks average edge-erasure probabilities between burst and slot nodes across decoding iterations.The iteration starts with p0 = 1; the update uses the slot-degree distribution and burst-node decoding behavior.Source: §III · pp. 3–4
- The asymptotic threshold G* is the supremum offered traffic for which decoding erasures vanish and normalized throughput equals offered traffic.For G < G*, all offered traffic becomes useful throughput, making G* the asymptotic peak throughput.Source: §III · p. 4
A. Stability
The stability analysis studies when successful decoding is a locally stable fixed point of the iterative process. Its condition is necessary but generally not sufficient for successful decoding; when minimum distance is at least 3, the fixed point is stable for any logical load.
A. Stability
- For minimum distance d_min ≥ 3, the successful-decoding fixed point p = 0 is stable for any logical load G.When d_min = 2, stability instead depends on the average number of weight-2 codewords and a condition on G.Source: A. Stability · p. 4
- The stability condition is necessary, but in general not sufficient for successful decoding.Source: A. Stability · p. 4
- In the IRSA case k = 1, the stability upper bound depends on P2, the probability of selecting a length-2 repetition code.Source: A. Stability · p. 4
- For a single (k + 1, k) single-parity-check code used by all users, the stability bound is achieved with equality.The proof identifies the threshold at which the system's equations have a solution and shows no smaller G does.Source: A. Stability · p. 4
IV. CSA FROM RANDOM LINEAR BLOCK CODES
This section considers users that randomly choose a codeword length and a linear block code from an ensemble, rather than selecting from a fixed set of candidate codes. It derives the ensemble quantities needed to calculate the average threshold and applies the stability analysis to random codes.
IV. CSA FROM RANDOM LINEAR BLOCK CODES
- Random code selection avoids analyzing a specific set of candidate codes, while the codeword length is also drawn randomly from a specified distribution.The selected binary linear block code has no idle bits and minimum distance at least 2.Source: §IV · pp. 4–5
- The random-code analysis updates the density-evolution recursion by averaging the code-dependent term over the ensemble.The average threshold is obtained from the updated simultaneous equations.Source: §IV · p. 5
- The ensemble expectation is calculated using counts of rank-k binary matrices, including counts conditioned on the rank of selected columns.The passage defines J and K as counts of matrices with specified rank and column properties.Source: §IV · p. 5
- The stability bound retains its form when the average number of weight-2 codewords is taken over the random-code ensemble.Source: §IV · p. 5
V. NUMERICAL THRESHOLD OPTIMIZATION AND COMPARISON WITH IRSA
The paper optimizes threshold-maximizing IRSA and CSA distributions, then compares their asymptotic thresholds and finite-user throughput. CSA has better thresholds at rates 1/2 and 2/5, while simulations also show a higher peak for CSA at rate 1/3 with selected component codes.
V. NUMERICAL THRESHOLD OPTIMIZATION AND COMPARISON WITH IRSA
- The analysis tools calculate thresholds and optimize distributions for specified component codes or random-code lengths and their respective probability distributions.The reported profiles use differential evolution and require each user's smallest local rate to be 1/6.Source: §V · p. 5
- Finite-user simulations closely match the asymptotic analysis, and CSA has a larger peak throughput than IRSA even at rate 1/3 with the selected component codes.The comparison uses k = 2 for CSA and equal frame duration, with NCSA = 1000 and NSA = 500.Source: Figure 2 · p. 6, §V · p. 6
- CSA achieves better thresholds than IRSA at rates 1/2 and 2/5, while IRSA has the better threshold at rate 1/3.The optimized CSA threshold is an average under the random-code hypothesis; particular component-code choices can yield larger thresholds.Source: §V · pp. 5–6
- CSA supports overall rates above 1/2, whereas IRSA is limited to rates at or below 1/2 unless some users transmit without repetition, which gives G* = 0.The paper associates CSA with higher power efficiency requirements and IRSA with lower rates.Source: §V · p. 6
VI. CONCLUSION
The conclusion presents CSA as a high-throughput random-access scheme, with derived density-evolution equations, optimized designs at several rates, and finite-user simulations; it is promising where power efficiency is required.
VI. CONCLUSION
- CSA is presented as a high-throughput random-access scheme whose density-evolution analysis supports rate-specific designs and finite-user simulations, with promise where power efficiency is required.Source: §VI · p. 6