Frameless ALOHA Protocol for Wireless Networks

I. INTRODUCTION

• Classical slotted ALOHA uses singleton slots and reaches maximum expected throughput T = 1/e ≈0.37 at G = 1.Terminals receive feedback after each slot; framed ALOHA instead organizes slots into a frame and returns feedback at its end.Source: §I · p. 1
• With two random repetitions per user, SIC-based framed ALOHA achieves throughput T ≈0.55, and related work connects SIC to iterative belief-propagation decoding.Generalized repetition strategies analyzed with and-or tree arguments resemble left-irregular LDPC distributions and can approach asymptotic throughput 1.Source: §I · p. 1
• In the SIC example, resolving user 2 in slot 4 removes its replica from slot 1, enabling user 3 and then user 1 to be resolved.The figure illustrates how resolution and replica removal can propagate across slots.Source: Figure 1 · p. 1
• Frameless ALOHA applies rateless principles to slotted ALOHA, adding slots until a sufficiently high fraction of users is resolved and adapting feedback timing to contention.The authors report high simulated throughput and describe the scheme as simple to implement.Source: §I · p. 1

A. Background: Rateless codes

• Rateless codes adapt their rate to channel conditions by sending encoded symbols until feedback reports decoding; LT codes form symbols by XOR-ing randomly sampled source symbols.The LT symbol degree is selected from distribution Ψ(d).Source: A. Background: Rateless codes · p. 1
• LT codes admit a sparse-graph representation with source and encoded symbols as left- and right-side nodes, and iterative belief-propagation decoding.The graph edges represent combining source symbols into encoded symbols.Source: A. Background: Rateless codes · p. 1
• Unlike LT-code design, which optimizes the right degree distribution, random-access user behavior controls only the left degree distribution, constraining LT-like design in slotted ALOHA.The accompanying figure identifies a graph representation of slotted ALOHA with repetitions.Source: A. Background: Rateless codes · p. 2, Figure 2 · p. 2

B. Terminology and notation

• User degree |u| and slot degree |s| count the edges incident to a user and a slot, respectively.The user- and slot-degree distributions are denoted Λ(x) and Ψ(x).Source: B. Terminology and notation · p. 2
• The edge-perspective distributions λ(x) and ρ(x) describe the degrees of users and slots encountered by a randomly selected edge.λ_j and ρ_k are the probabilities that an edge is incident to a user of degree j and a slot of degree k, respectively.Source: B. Terminology and notation · p. 2
• SIC starts from degree-one slots, resolves their connected users, removes those users’ replica edges, and repeats as new degree-one slots appear.Replica removal lowers incident slot degrees and can expose further unresolved users.Source: B. Terminology and notation · p. 2

C. System model

• A beacon synchronizes slot timing and numbering, and each user attempts transmission with a predefined, slot-dependent probability shared across users.The round ends when a predefined fraction of users is resolved, signaled by the next beacon.Source: C. System model · p. 2
• The degree distribution of each slot is controlled indirectly through its access probability, rather than optimized directly as in LT codes.The expected slot degree G_m is its expected load; its actual degree is binomial and can be approximated by Poisson for the ranges considered.Source: C. System model · p. 2
• The user-degree distribution is Poisson with mean depending on the total slots M and average slot degree G.Resolving all users requires M ≥ N, written M = (1 + ε)N, with ε the slot overhead relative to M = N.Source: C. System model · p. 2
• The model evaluates probability of user resolution P_R and throughput T, which measures slot-use efficiency.Both P_R and T depend on Ψ(x) and ε.Source: C. System model · p. 3

D. Analysis

• Increasing average slot degree G or overhead ε lowers the upper bound on P_R derived from the probability that a user is idle throughout the round.The bound is a special instance of the bound in.Source: D. Analysis · p. 3
• Increasing expected slot degree G_m reduces slot idleness but also reduces low-degree slots, which can adversely affect SIC progress.A substantial fraction of low-degree slots is required to drive SIC.Source: D. Analysis · p. 3
• Fig. 5 relates the optimal degree β* for maximal P*_R to the ratio M/N.The supplied figure description specifies this relationship but gives no plotted values.Source: Figure 5 · p. 3
• And-or tree analysis tracks edge survival across SIC iterations, and varying M yields expected P_R as the contention-round length changes.The expected resolution probability after iteration i is P_R = 1 − q_i; this captures a round length that is not set a priori.Source: D. Analysis · p. 3
• With constant expected slot degree G_m = β, all slots share Ψ(x) = e^(−β(1−x)), and the slot-side update simplifies to r_i = 1 − e^(−βq_i).The corresponding user-degree distribution is Λ(x) = e^(−(1+ε)β(1−x)).Source: D. Analysis · p. 3

• The results focus on constant expected slot degree to minimize coordination, with simulations averaging 1,000 runs across five user counts and abstracting physical-layer issues.Source: §III · p. 3
• P*_R rises steeply beyond a threshold that moves closer to 1 as N grows, then saturates at its upper bound; larger N approaches the and-or-tree asymptote.Source: §III · pp. 3–4
• For realistic N, maximal throughput consistently exceeds ’s distribution while average user degree stays below 3.3 versus 3.6 for ’s example; the asymptotic maximum is approximately 0.87.Source: Figure 6 · p. 4, §III · p. 4
• T* peaks shortly after M/N exceeds 1, then decreases as resolution saturates while M/N continues to grow.Source: Figure 6 · p. 4, §III · p. 4
• The optimal expected slot degree β* grows steadily with M/N, while smaller N yields a lower β* than its asymptotic value at the same ratio.Source: §III · p. 4

IV. DISCUSSION AND PRACTICAL CONSIDERATIONS

• A pseudorandom generator tailored to p_m and N determines each user's silent-or-transmit slots from that user's identifier.Each transmitted packet carries the user identifier, allowing the base station to recover that user's past and future transmission slots after decoding.Source: §IV · p. 4
• The optimized slot access probability depends on N, estimated from batch arrivals or from λτ plus retrying users for continuous arrivals.The authors note that β* varies slowly with N, but say this observation requires further study.Source: §IV · p. 4
• The contention round ends when the resolved-user fraction reaches a predetermined threshold selected to maximize throughput.Fig. 7 depicts the scheme's operation over contention rounds.Source: §IV · p. 4, Figure 7 · p. 4
• For N=1000, threshold P_R≈0.923 and p=2.9·10^-3 yield simulated average M≈1100 slots and throughput T≈0.83.The threshold and access probability are selected to maximize throughput.Source: §IV · p. 4
• A beacon is triggered at the resolved-user threshold and carries ACK feedback; practical downlink arrangements are left for further work.The passage describes a dedicated downlink channel for FDD and possible precedence techniques for TDD.Source: §IV · p. 4