PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis of Slotted ALOHA with an Age Threshold

Orhan Tahir Yavascan, Elif Uysal

arXiv:2007.09197v2cs.IT

TL;DR

The paper addresses how to improve information freshness in slotted random access without sacrificing throughput. It analyzes threshold-ALOHA, which delays transmissions until AoI reaches Γ and then uses probability τ, deriving its steady-state behavior and optimizing these parameters. The resulting AoI scales as 1.4169n—nearly half the slotted-ALOHA benchmark—while throughput loss stays below 1%.

  • Problem

    The paper studies the need to balance frequent transmission attempts against avoiding simultaneous attempts in distributed random access to control average AoI.

  • Method

    The paper derives the steady-state active-user distribution and average AoI for threshold-ALOHA, then optimizes its age threshold Γ and transmission probability τ.

  • Results

    1.4169n is the optimal AoI scaling, while throughput loss relative to the maximum e^-1 remains below 1%.

  • Takeaways & Limitations

    Threshold-ALOHA nearly halves average AoI while maintaining near-optimal throughput and converging to slotted ALOHA with fewer active sources.

Abstract

from arXiv · show

We present a comprehensive steady-state analysis of threshold-ALOHA, a distributed age-aware modification of slotted ALOHA proposed in recent literature. In threshold-ALOHA, each terminal suspends its transmissions until the Age of Information (AoI) of the status update flow it is sending reaches a certain threshold $Γ$. Once the age exceeds $Γ$, the terminal attempts transmission with constant probability $τ$ in each slot, as in standard slotted ALOHA. We analyze the time-average expected AoI attained by this policy, and explore its scaling with network size, $n$. We derive the probability distribution of the number of active users at steady state, and show that as network size increases the policy converges to one that runs slotted ALOHA with fewer sources: on average about one fifth of the users is active at any time. We obtain an expression for steady-state expected AoI and use this to optimize the parameters $Γ$ and $τ$, resolving the conjectures in \cite{doga} by confirming that the optimal age threshold and transmission probability are $2.2n$ and $4.69/n$, respectively. We find that the optimal AoI scales with the network size as $1.4169n$, which is almost half the minimum AoI achievable with slotted ALOHA, while the loss from the maximum throughput of $e^{-1}$ remains below $1\%$. We compare the performance of this rudimentary algorithm to that of the SAT policy that dynamically adapts its transmission probabilities.

I. INTRODUCTION

This paper develops a steady-state analysis of threshold-ALOHA, an age-aware slotted ALOHA policy, and characterizes its scaling, optimal parameters, and comparison with related access policies. The analysis shows that threshold-ALOHA substantially improves AoI while retaining near-optimal throughput.

  • Threshold-ALOHA converges to slotted ALOHA with fewer users as network size grows, while requiring lower computational complexity than age-thinning.
  • The paper derives the steady-state distribution of active users and an expression relating average AoI to network size, threshold Γ, and transmission probability τ.
  • 1.4169n is the optimal time-average AoI scaling, nearly half the minimum achievable with ordinary slotted ALOHA.
  • The AoI-optimized operating point loses less than 1% relative to maximum throughput.
  • Compared with SAT, threshold-ALOHA achieves similar near-e^-1 throughput with lower feedback, power, and computational requirements, while SAT has a 4% asymptotic age advantage.

II. SYSTEM MODEL

The system models synchronized users sending fresh status updates over slotted random access, where collisions lose all packets and successful transmissions reset flow age. Threshold-ALOHA suppresses transmissions below an age threshold and applies fixed-probability slotted ALOHA afterward.

  • The network has n synchronized sources using slotted time, generate-at-will updates, and a common access point.
  • Collisions cause all simultaneous transmissions to fail, while a collision-free transmission succeeds within one slot and generates a fresh packet.
  • AoI equals the elapsed slots since the freshest received packet was generated and resets to 1 after successful transmission.
  • Threshold-ALOHA keeps a source idle until its age reaches Γ, then transmits in each slot with probability τ.
  • The analysis truncates active-source ages at Γ, yielding a finite-state Markov chain with a unique steady-state distribution.

A. Steady State Solution

The steady-state analysis reduces the Markov chain to recurrent states with distinct below-threshold ages and characterizes their probabilities by the number of active sources. States sharing the same active-source count are equiprobable, enabling an explicit distribution for that count.

  • Steady-state characterization: The truncated Markov chain has a unique steady-state distribution over its recurrent class, whose transition equations fully characterize all recurrent-state probabilities.The steady-state equations account for all incoming and outgoing transitions among recurrent states.
  • Recurrent state space: States with distinct users sharing a below-threshold age are transient, so recurrent states can be restricted to those whose only repeated age is Γ.Any such initial state is left within at most Γ slots and never revisited.
  • State classification: A recurrent state is typed by M, the number of active sources at age Γ, and the set of n−M ages below the threshold.This representation separates the active-source count from the specific below-threshold ages.
  • Steady-state symmetry: States of the same type have equal steady-state probabilities, and for fixed M the below-threshold age set does not affect that probability.The result follows from user symmetry and reduces state probabilities to a function of the active-source count.
  • Active-source distribution: The total probability P_m of having m active sources is obtained by multiplying the common state probability for active count m by the number of corresponding recurrent states.Lemma 1 gives an explicit expression for P_m in terms of m, τ, Γ, and n.

B. Pivoted MC

The pivoted Markov chain isolates one source whose age may exceed Γ while all other sources remain truncated. Its steady-state behavior is well defined, and the active-source count among non-pivot users is independent of the pivot age once the pivot is active.

  • Pivoted chain construction: The pivoted chain has a unique steady-state distribution because every state can reach an unlucky state through sufficiently many slots without a successful transmission.The pivot is truncated at s+1 while other sources are truncated at Γ.
  • Relation to the truncated chain: For pivot ages below Γ, pivoted-chain states correspond one-to-one with truncated-chain states and retain identical steady-state and transition probabilities.This correspondence extends the truncated-chain solution to the pivot representation.
  • Pivot independence: When the pivot is active, the number of active non-pivot sources is independent of the pivot state s.The result follows because each pivot age observes the same active-user distribution.
  • Pivot state evolution: The pivot evolution is represented by a state diagram whose transition probabilities q_s are the probabilities that the pivot successfully transmits.For large n, q_s converges to a common value q_o for all active pivot states.

C. Large network asymptotics

The large-network analysis studies the active-source fraction through a scaled function f(k). Its roots determine concentration points of the active-user distribution, and in the single-peak case the fraction converges to the unique root.

  • Asymptotic scaling: The function f(k) controls how P_m changes with the active-user fraction, so its roots identify candidate concentration points for the steady-state active-source count.The scaled parameters replace τ and Γ to analyze behavior as n grows.
  • Active-source distribution: Roots of f(k) where f is decreasing correspond to local maxima of the probability mass function P_m.Because f has at most three roots, P_m can have at most two local maxima.
  • Single-peak asymptotics: The active-source fraction k converges in probability to the unique root k_0 of f(k) when f has one root.Thus threshold-ALOHA asymptotically behaves like slotted ALOHA with approximately nk_0 active users.
  • Performance implication: In the large-network limit, threshold-ALOHA keeps channel throughput close to e^-1 while optimal parameters can substantially improve average age.The supplied analysis states that this behavior follows from converting the system to one with fewer active sources.

D. Double Peak Case

When f(k) has three roots, the active-source fraction can concentrate near either of two stable roots. The smaller-root outcome is preferred because larger active-user fractions can congest the channel, especially at finite network sizes.

  • Asymptotic alternatives: The active-user ratio converges to k_0 or k_2 depending on the sign of an integral constraint, with the larger root corresponding to more simultaneous active users.The smaller-root regime is the desired outcome for benefiting from the age threshold.
  • Finite-network behavior: For finite networks, probabilities of intermediate and larger-root state sets may remain substantial, producing too many simultaneous transmissions and congestion.These state sets have larger active-user fractions than the smaller-root set.
  • Comparison with single-peak cases: Single-peak cases converge more quickly because they lack the intermediate and larger-root state sets.Double-peak cases require an additional integral constraint for the smaller-root conclusion.
  • Initialization: In large networks, unsuitable initial conditions can slow convergence or make transitions from the larger-root set to the smaller-root set nearly impossible within a reasonable time.Randomizing initial user states is suggested to prevent initial congestion.
  • Overall implication: Despite these convergence concerns, double-peak cases produce asymptotically optimal values and become preferable as network size increases.The result is stated for the asymptotic regime rather than all finite network sizes.

E. Steady state average AoI in the large network limit

The large-network analysis derives steady-state active-user behavior and average AoI for threshold-ALOHA, then optimizes its threshold and transmission probability. The optimized policy nearly preserves maximum slotted-ALOHA throughput while reducing AoI to almost half the slotted-ALOHA value.

  • The steady-state derivation computes the single-source distribution from q0, obtains an expected time-average AoI expression, and optimizes it over threshold and transmission parameters.
  • 0.3644 is the throughput at the AoI-optimized operating point, whose loss from the e^-1 upper bound is below 1%.
  • The threshold policy converges to a system with a limiting active-user population m0, and optimized m0τ is close to 1.

IV. EXTENSION TO EXOGENOUS ARRIVALS

The exogenous-arrival extension separates packet-generation and transmission processes and bounds the resulting AoI using a relaxed threshold policy. Under sufficiently frequent arrivals, its optimal age has the same asymptotic scaling as the original analysis.

  • The extension assumes independent packet arrivals across users and time, with nλ_i tending to infinity.
  • The relaxed policy permits transmission after Γ slots to obtain a lower bound, while forcing transmissions without fresh packets gives an upper-bound argument.
  • When no new packet has arrived, retransmitting the previously delivered packet cannot improve age; analyzing this case therefore yields an upper bound on optimal age.
  • Transmission decisions are independent of arrival times, so packet-generation and delivery times remain independent.
  • 1.4169n is both an asymptotic upper and lower bound on optimal age under sufficiently frequent exogenous arrivals.

V. NUMERICAL RESULTS AND DISCUSSION

Threshold-ALOHA nearly halves average AoI relative to slotted ALOHA while retaining near-optimal throughput, with optimal AoI scaling linearly as 1.4169n. Its steady-state analysis explains this improvement through a reduction in active users to about one-fifth of the network and identifies optimal threshold and transmission parameters.

  • Simulations compare threshold-ALOHA and SAT with slotted ALOHA across network sizes from 50 to 1000 using 10^7 time slots and randomized initial states.
  • Less than 1% throughput loss: threshold-ALOHA achieves 0.3658 versus slotted ALOHA’s e^-1 maximum, while nearly halving average AoI.
  • The policy suspends transmissions until age exceeds Γ, then attempts with constant probability τ as in standard slotted ALOHA.
  • About one-fifth of users remain active at steady state, effectively making threshold-ALOHA resemble slotted ALOHA with fewer sources.
  • The analysis confirms optimal settings Γ = 2.2n and τ = 4.69/n for the threshold-ALOHA policy.
  • 1.4169n: threshold-ALOHA’s optimal average AoI scales with network size at roughly half the slotted-ALOHA slope, matching SAT closely.

APPENDIX A

This appendix establishes steady-state probability relations for threshold-ALOHA states, using predecessor-state transitions and induction across pivot-source ages.

  • APPENDIX A: The proof handles pivot-source ages below and above Γ, extending the stated properties for all s ≥ Γ by induction.The induction assumes the properties for smaller pivot-source ages and proves them for the next age.
  • APPENDIX A: For states with and without a particular active-user index, the predecessor configurations differ and yield corresponding steady-state probability expressions.The two cases are analyzed separately, including transitions that change the number of active sources.
  • APPENDIX A: Steady-state probabilities are derived by enumerating predecessor states and combining their transition probabilities.The derivation treats cases according to whether the relevant user index belongs to the active-source set.

APPENDIX B

This appendix analyzes the roots of a continuous function used in the steady-state analysis, proving existence and bounding the number of possible roots before deriving asymptotic bounds.

  • APPENDIX B: f(k) has at least one root in (0,1) because its endpoint limits are +∞ and −∞.Continuity on the interval supplies the existence result.
  • APPENDIX B: f(k) has at most 3 roots because the derivative-based formulation permits at most three candidate values satisfying the root condition.The argument first bounds the roots of a derivative-related expression and then transfers that bound to f(k).
  • APPENDIX B: The resulting bounds establish the stated asymptotic property through separate estimates on the relevant probability expressions.The proof derives an explicit bound before concluding the corresponding property.
  • APPENDIX B: Taylor expansion around k0 linearizes f(k0 + ϵ), enabling bounds for sequences whose perturbations shrink with n.The appendix uses ϵn = cn^-1/3 and combines positive- and negative-side arguments.

APPENDIX D

This appendix shows that, as network size grows, probability mass concentrates in region S0 while the probabilities of regions S1 and S2 vanish.

  • APPENDIX D: Pr(S2) → 0 as n grows, using bounds around the local maximum and ratios of probability estimates.The argument shows that the ratio Pr(S2)/(1−Pr(S2)) tends to zero.
  • APPENDIX D: Pr(S1) → 0 because its region corresponds to a local-minimum valley whose probability becomes negligible asymptotically.Endpoint probabilities are used to bound the probability mass over S1.
  • APPENDIX D: Pr(S0) → 1 because the three regions partition the probability mass and both Pr(S1) and Pr(S2) vanish.The appendix then uses Pr(S0) → 1 in subsequent bounds.
Loading 2007.09197v2…