PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded Slotted ALOHA: A Graph-Based Method for Uncoordinated Multiple Access

Enrico Paolini, Gianluigi Liva, Marco Chiani

arXiv:1401.1626v2cs.IT

TL;DR

The paper addresses reliable random access on a collision channel without feedback, where retransmissions cannot ensure recovery and user coordination may be difficult. It introduces CSA, combining randomly selected local erasure-correcting codes with SIC and a graph-based density-evolution analysis. The resulting designs support rates approaching 1 in principle, tightly approach the capacity bound across rates, and reach throughput as high as 1 packet per slot with sufficiently low component-code rates.

  • Problem

    Reliable recovery from collisions is needed on a collision channel without feedback, especially when large user populations make coordination or retransmissions problematic.

  • Method

    CSA splits packets into segments, encodes them with randomly selected local component codes, and analyzes SIC through a bipartite graph and density evolution.

  • Results

    Throughput as high as 1 packet per slot is tightly approachable, while designed component-code distributions approach the capacity bound over the whole range of rates.

  • Takeaways & Limitations

    CSA provides retransmission-free random access with rates arbitrarily close to 1 in principle and retains IRSA as its repetition-code special case.

  • Takeaways & Limitations

    The paper leaves open whether CSA configuration sequences achieving the capacity bound exist for every rate and conjectures that increasing component-code dimension may be required.

Abstract

from arXiv · show

In this paper, a random access scheme is introduced which relies on the combination of packet erasure correcting codes and successive interference cancellation (SIC). The scheme is named coded slotted ALOHA. A bipartite graph representation of the SIC process, resembling iterative decoding of generalized low-density parity-check codes over the erasure channel, is exploited to optimize the selection probabilities of the component erasure correcting codes via density evolution analysis. The capacity (in packets per slot) of the scheme is then analyzed in the context of the collision channel without feedback. Moreover, a capacity bound is developed and component code distributions tightly approaching the bound are derived.

I. INTRODUCTION

CSA extends random access by encoding each user's segments with randomly selected local component codes and recovering collisions through SIC. Its graph-based density-evolution analysis supports reliable retransmission-free operation, broader rate choices than IRSA, and designs approaching a capacity bound.

  • Scheme and analysis: CSA extends IRSA by splitting packets into segments and encoding them with randomly selected local component codes before transmission.The receiver combines local-code decoding with successive interference cancellation.
  • Scheme and analysis: A bipartite graph representation of the SIC process enables density-evolution equations and asymptotic analysis on the collision channel.The analysis defines the scheme's capacity in a retransmission-free setting.
  • Performance and scope: Vanishing packet loss is guaranteed asymptotically for channel loads not greater than the asymptotic throughput when frame length and user population grow with constant ratio.This reliability result applies without retransmissions.
  • Performance and scope: CSA permits access-scheme rates between 0 and 1 in principle, overcoming IRSA's reliable-operation rate limit of 1/2 without retransmissions.IRSA is recovered as the special case in which all local component codes are repetition codes.
  • Performance and scope: For rates between 1/3 and 1/2, CSA remarkably outperforms IRSA because its broader component-code choices allow more flexible selection probabilities.At very low rates, the reported advantage is small enough that IRSA is preferred for design and operational simplicity.
  • Capacity and applications: An upper bound on sustainable traffic for a given scheme rate is developed, with component-code distributions designed to approach it closely.The paper also identifies dense-user applications where reliability without retransmissions is useful, including sensor networks, RFID, and satellite networks.

B. Encoding and Decoding Procedures

CSA divides each active burst into k data segments, encodes them using a randomly selected local linear block code, and transmits the encoded segments over randomly chosen frame slices. The receiver uses clean segments, erasure decoding, and interference cancellation under explicit collision-channel assumptions.

  • Encoding: Each active burst is divided into k equal information segments and encoded into n_h equal-length segments using a randomly selected (n_h, k) component code.Users independently choose codes from a receiver-known set without coordination.
  • Encoding: Component code C_h has length n_h, dimension k, rate R_h = k/n_h, minimum distance d_h ≥ 2, and no idle symbols.The same code-selection p.m.f. is used by all users.
  • Transmission: Each encoded segment is transmitted in a uniformly random slice, with k slices per slot and kM slices per MAC frame.The segment transmission duration is T_segment = T_slot/k.
  • Rate and assumptions: CSA's burst-energy increment relative to pure slotted ALOHA is Δ_E = 10 log10(n̄/k) = −10 log10 R, while rates 0 < R < 1 are possible in principle.IRSA corresponds to k = 1 with repetition codes and supports only 0 < R ≤ 1/2.
  • Transmission: The example uses k = 2, with user i employing a (4, 2) code and users j and l employing (3, 2) codes.Darkened encoded rectangles represent parity segments in the systematic encoders.
  • Decoding: Clean slices are decoded first, then local code erasure decoding can recover missing segments whose interference is subsequently cancelled.The receiver is assumed to detect silence, unique signals, and collisions, while collision contents remain unavailable.

III. BIPARTITE GRAPH MODEL AND DENSITY EVOLUTION ANALYSIS

CSA represents active users and transmitted segments as a bipartite graph, enabling iterative interference subtraction and local erasure decoding to be analyzed as message passing.

  • Each active user is represented by a burst node, each slice by a slice node, and each transmitted encoded segment by an edge.
  • A type-h user encoded with an (n_h, k) component code appears as a degree-n_h burst node, while a slice with d collisions appears as a degree-d slice node.
  • Clean slices provide known segments, after which MAP erasure decoding at burst nodes recovers additional segments for interference subtraction.
  • The four-slice, three-user example uses repetition codes and illustrates how collision patterns map to graph connections during iterative interference subtraction.
  • The iterative interference subtraction process is equivalent to iterative decoding of doubly-generalized low-density parity-check codes over the erasure channel.

A. Asymptotic Analysis of Iterative Interference Subtraction

The asymptotic analysis models CSA’s iterative interference subtraction through density evolution, combining slice-node interference cancellation with MAP decoding at burst nodes. The resulting threshold determines when all collisions are resolved without retransmissions.

  • As M tends to infinity with constant normalized population size, density evolution analyzes CSA assuming local MAP erasure decoding at each burst node.
  • The probabilities p_l and q_l track persistent collisions at slice nodes and uncancellable interference from burst nodes after MAP decoding.
  • The burst-node update is an EXIT function averaged over code types, while the slice-node update follows the graph’s slice-degree distribution.
  • Theorem 3.1 gives a density-evolution recursion based on the component codes’ un-normalized information functions.
  • The recursion captures both iterative interference cancellation at slices and local MAP decoding at burst nodes, specializing to IRSA when all component codes are repetitions.
  • For G < G*(C, Λ), throughput is S = G because all collisions are resolved without retransmissions; G*(C, Λ) is the conditional CSA capacity.
  • Below capacity, an open EXIT tunnel drives the probabilities toward (0, 0), whereas above capacity a nonzero fixed point remains.
  • CSA performance depends on the component codes’ information functions, not on the specific generator-matrix representations.

B. Stability of Iterative Interference Subtraction Collision-Free Point

The collision-free fixed point is studied through recursion stability, yielding necessary bounds on successful decoding and identifying conditions under which those bounds are attained.

  • Local stability of the collision-free point p_hat = 0 is determined by the derivative condition for the density-evolution recursion.
  • For component codes with minimum distance at least two, the stability condition depends on the expected number of weight-2 codewords in the selected-code ensemble.
  • When the minimum distance parameter r is at least 3, the collision-free fixed point is stable for any channel load G.
  • Stability is necessary but generally insufficient for successful decoding, because loads can satisfy the stability bound while exceeding CSA capacity.
  • For IRSA, the stability upper bound is G*(C, Λ) ≤ 1/(2Λ_2), where Λ_2 is the probability of selecting the length-2 repetition code.
  • When all users employ a (k + 1, k) single-parity-check code, the stability bound is achieved with equality.

C. Asymptotic Analysis Under a Random Component Code Hypothesis

The random component-code hypothesis averages CSA’s density evolution over ensembles of binary linear codes with selected lengths and uniformly random generator matrices. This provides an expected asymptotic threshold for the resulting ensemble.

  • Users randomly select codeword lengths from an ensemble and encode k information segments with uniformly random full-rank generator matrices.
  • The random-code setting restricts codes to have no idle bits and minimum distance at least two.
  • The rate and slice-degree expressions remain unchanged, while the burst-node recursion is replaced by an expectation over the random-code ensemble.
  • Expected information functions are computed using recursively evaluable counts of full-rank binary matrices satisfying the ensemble constraints.
  • The expected asymptotic threshold G*(N, Λ) is the supremum of loads for which the random-code density-evolution recursion converges to zero.
  • Under the random-code hypothesis, the stability upper bound retains the same form, with B_2 equal to the expected number of weight-2 codewords.

IV. CAPACITY LIMITS OF CSA SCHEMES

The section derives an upper bound on CSA capacity at a given rate R. This bound applies to any component-code set and selection distribution, even with genie-aided Gaussian-elimination decoding.

  • Theorem 4.1 bounds the CSA capacity G∗(C, Λ) by G(R), for any component-code set and p.m.f. corresponding to rate R.G(R) is defined as the unique positive solution associated with R in the stated equation.
  • A successful-decoding open tunnel between the BN and SN EXIT curves necessarily imposes the area inequality used to derive the bound.The recursion evolves through qℓ = f_b(pℓ−1) and pℓ = f_s(qℓ).
  • The Area Theorem step assumes MAP erasure decoding at the burst node, and the area inequality is necessary but not sufficient for successful decoding.The Area Theorem equates the area below a linear block code’s MAP EXIT function with its code rate.
  • G(R) depends solely on the scheme rate R, whereas G∗(C, Λ) also depends on the component codes and their selection distribution.The monotonicity of y = −x/log(1 − x) yields the rate-only upper bound.
  • The upper bound remains valid even when decoding solves the resulting linear system by Gaussian elimination with genie-aided assistance.Thus, the bound is not restricted to the iterative decoding procedure.

V. DESIGN AND ANALYSIS OF CSA RANDOM ACCESS SCHEMES

This section presents numerical design and validation of CSA schemes. It compares dimension-k component codes with IRSA and examines whether asymptotic analysis remains useful for finite MAC frames.

  • Numerical experiments compare CSA schemes using simple component codes of dimensions k = 2 and k = 3 with IRSA schemes.

A. Performance Analysis of Finite-Length CSA Schemes

The section designs CSA distributions using asymptotic threshold analysis, validates them in finite frames, and compares their thresholds and throughput with IRSA across rates and component-code choices.

  • Design methodology: Density-evolution tools calculate thresholds for fixed component codes or random-code ensembles and optimize the corresponding user-selection distributions Λ.
  • Design methodology: Table I reports IRSA and random-code CSA p.m.f.s Λ for rates 1/3, 2/5, 1/2, and 3/5, with CSA dimensions k = 2 and k = 3.
  • Design methodology: Table II evaluates k = 2 CSA thresholds using specific component codes and the same p.m.f.s Λ used for the corresponding designs.
  • Component-code choices: For rate R = 1/3, CSA combines three different (5, 2) component codes whose total selection probability is 0.447058.
  • Comparison with IRSA: CSA supports any rate 0 < R < 1, while IRSA supports only 0 < R ≤ 1/2 unless some users transmit without repetition.
  • Comparison with IRSA: For R = 1/3, the best found k = 3 CSA threshold is G∗(N, Λ) = 0.9143 versus 0.8792 for IRSA; for R = 1/2, values are 0.6868 and 0.5000.
  • Comparison with IRSA: Increasing component-code dimension k improves asymptotic thresholds, although the improvement is almost negligible at low rates.At rates below 1/3, IRSA can approach the upper bound with simpler repetition-code designs.
  • Finite-length validation: Finite-frame simulations follow the asymptotic peak-throughput trend, with CSA slightly higher for the tested configuration; Fig. 7 compares finite-frame curves for M = 100, 500, and 2500 slots.

B. Approaching the Capacity Bound

The section designs CSA component-code distributions to approach the capacity bound across rates, comparing repetition-based IRSA with higher-dimensional CSA codes and finite-frame performance.

  • Design methodology: CSA distributions are optimized by searching for the probability mass function that maximizes the asymptotic threshold for fixed component codes and target rate.The search uses differential evolution and focuses on component codes of moderate-low length.
  • IRSA comparison: For low rates, repetition-based configurations approach the capacity bound tightly, but their gap becomes visible near rate 1/2.At rate R = 5/11, Λ5 achieves G∗(C5, Λ5) = 0.625 versus G(5/11) = 0.843; at R = 1/2, repetition coding is limited to threshold 0.5.
  • Finite-frame validation: For Λ1 with M = 5000 slots, packet loss near 2 × 10^-3 occurs at G = 0.94 packets/slot, only 0.05 packets/slot below the theorem bound.The simulation compares frame sizes M = 5000, 1000, and 500 slots against G∗(C1, Λ1) = 0.977.
  • MDS-based CSA: The reported CSA distributions use MDS component codes with dimensions k = 2, 3, and 4, while the corresponding p.m.f.s are represented compactly as polynomials.Each MDS component code has length h + k and dimension k.
  • MDS-based CSA: For k = 2 and R = 0.4, the MDS-based CSA distribution Λ6 reaches threshold G∗(C6, Λ6) = 0.830, exceeding the best IRSA threshold 0.791.The best binary-code CSA configuration at the same rate reaches G∗(C, Λ) = 0.8229.

VI. CONCLUSIONS

The conclusions present CSA as a graph-based coding approach for collision channels without feedback and report reliable, high-throughput operation without retransmissions. They also identify capacity-achieving sequences and related extensions as open directions.

  • Conclusions: CSA splits each packet into segments and encodes them with randomly selected local component codes, extending IRSA beyond simple repetition.The graphical representation connects CSA interference cancellation with erasure decoding and yields density evolution equations.
  • Conclusions: CSA without retransmissions is asymptotically reliable, and its capacity is defined for the collision channel without feedback.The result concerns the proposed scheme under a setting where retransmissions are forbidden.
  • Conclusions: Throughput as high as 1 packets/slot is tightly approachable with sufficiently low component-code rates.A design technique also allows high-rate CSA schemes to approach the capacity bound over the whole rate range.
  • Future directions: The paper proposes further study of CSA sequences, spatial coupling, multiple receivers, and spatial diversity.The authors conjecture that capacity-bound sequences may require increasing component-code dimension k.

APPENDIX A RESULTS ON SUCCESSIVE INTERFERENCE CANCELLATION

The appendix models realistic SIC with random synchronization offsets and evaluates whether sequential cancellation leaves recoverable residual signals. Simulations test collision levels using a coded QPSK waveform.

  • SIC validation: The realistic-SIC validation tests whether removing l − 1 interferers from an l-way collision leaves the remaining segment decodable with high probability.The analysis specifically examines residual interference caused by imperfect channel estimation.
  • Signal model: Each received contribution includes random delay, frequency offset, and phase offset, and the matched-filter output combines all users with Gaussian noise.The model assumes small frequency shifts relative to signal bandwidth and uses a raised-cosine pulse shape.
  • Cancellation procedure: SIC reconstructs and subtracts recovered interferers serially, leaving the desired contribution, noise, and residual phase-estimation interference.Recovered codeword symbols are used to estimate channel parameters and reconstruct canceled signals.
  • Cancellation procedure: The data-aided SIC procedure depends on low average cross-correlation among users’ encoded symbol sequences.This condition is associated with modeling segment bits as independent and identically distributed random variables.
  • Simulation: Simulations use a (512, 256) cycle code over F256 with QPSK and evaluate collisions of l = 2, 4, 6, and 8 segments.The resulting block error rate is plotted against Eb/N0 and compared with the no-collision AWGN case.

APPENDIX B AN ALTERNATIVE PROOF OF THE CAPACITY BOUND (23)

The alternative proof models collided encoded segments as finite-field sums and interprets decoding as solving a linear system. Counting available equations and unknowns yields the capacity upper bound.

  • Equivalent channel model: The appendix introduces an equivalent channel model in which collisions produce sums of symbols over GF(2^l), while the decoder distinguishes silence, singleton symbols, and collisions.This model is described as similar to an F-adder channel, with detectable collisions.
  • Equivalent channel model: Interference cancellation in the finite-field model adds the corresponding recovered segment symbol to the current slice symbol.This replaces a collided observation with the residual contribution after cancellation.
  • Capacity-bound proof: The proof treats active users’ information segments as unknowns and non-empty slices as known equations in a linear system.Each encoded segment is a linear combination of its associated information segments.
  • Capacity-bound proof: A unique solution is impossible when the number of unknowns exceeds the number of available equations.As M tends to infinity, the expected fraction of non-empty slices is 1 − exp{−G/R}, while the expected number of unknowns per slice equals G.
Loading 1401.1626v2…