PaperlayerView exact revision on arXiv

Source-linked AI summary

Age of Information in Random Access Channels

Xingran Chen, Konstantinos Gatsis, Hamed Hassani, Shirin Saeedi Bidokhti

arXiv:1912.01473v6cs.NIcs.IT

TL;DR

High-rate communication does not guarantee timely information in remote sensing, estimation, and control over random access channels. The paper develops decentralized age-based thinning policies that select transmissions by packet age-gain and analyzes them alongside slotted ALOHA and AoI bounds. For large M, slotted ALOHA is asymptotically optimal below 1/eM, while the proposed policies reduce age as arrival rates increase beyond that threshold.

  • Problem

    The paper addresses minimizing age of information over decentralized random access channels, where centralized scheduling requires impractical communication and coordination.

  • Method

    The paper derives AoI lower bounds, analyzes slotted ALOHA, and proposes adaptive and stationary decentralized thinning policies that retain packets with sufficiently large age-gains.

  • Results

    For large M, slotted ALOHA is asymptotically optimal below 1/eM, whereas the proposed age-based policies decrease AoI beyond that operating threshold.

  • Takeaways & Limitations

    Increasing the sampling rate can be beneficial when transmissions are selectively thinned according to age-gain rather than sent indiscriminately.

Abstract

from arXiv · show

In applications of remote sensing, estimation, and control, timely communication is not always ensured by high-rate communication. This work proposes distributed age-efficient transmission policies for random access channels with $M$ transmitters. In the first part of this work, we analyze the age performance of stationary randomized policies by relating the problem of finding age to the absorption time of a related Markov chain. In the second part of this work, we propose the notion of \emph{age-gain} of a packet to quantify how much the packet will reduce the instantaneous age of information at the receiver side upon successful delivery. We then utilize this notion to propose a transmission policy in which transmitters act in a distributed manner based on the age-gain of their available packets. In particular, each transmitter sends its latest packet only if its corresponding age-gain is beyond a certain threshold which could be computed adaptively using the collision feedback or found as a fixed value analytically in advance. Both methods improve age of information significantly compared to the state of the art. In the limit of large $M$, we prove that when the arrival rate is small (below $\frac{1}{eM}$), slotted ALOHA-type algorithms are asymptotically optimal. As the arrival rate increases beyond $\frac{1}{eM}$, while age increases under slotted ALOHA, it decreases significantly under the proposed age-based policies. For arrival rates $θ$, $θ=\frac{1}{o(M)}$, the proposed algorithms provide a multiplicative factor of at least two compared to the minimum age under slotted ALOHA (minimum over all arrival rates). We conclude that, as opposed to the common practice, it is beneficial to increase the sampling rate (and hence the arrival rate) and transmit packets selectively based on their age-gain.

I. INTRODUCTION

This paper studies timely information delivery over decentralized random access channels, where high communication rates do not necessarily ensure fresh receiver information. It derives age bounds and analyzes slotted ALOHA before proposing distributed age-based thinning policies that selectively transmit packets according to their age-gain.

  • Motivation: AoI measures receiver-side information freshness through both packet transmission frequency and communication delay.The metric is relevant to remote sensing, monitoring, estimation, and control applications where stale information matters.
  • System setting: The paper considers symmetric wireless systems with M transmitters, each generating packets independently with arrival rate θ over a shared channel.New packets replace undelivered older packets at each source, consistent with Markovian monitored processes.
  • Bounds: Two general AoI lower bounds model idealized immediate delivery and continuously available fresh packets, with different bounds active at small and near-one arrival rates.The small-rate bound is governed by inter-arrival time, while the other becomes active as θ approaches 1.
  • Slotted ALOHA: Slotted ALOHA becomes unstable above sum arrival rate 1/e, while below 1/e its normalized age is approximately 1/(Mθ) and asymptotically optimal for large M.Its normalized age explodes as the sum arrival rate exceeds the critical point.
  • Proposed policies: Age-based thinning selectively transmits packets with large age-gains, using either an adaptive feedback-driven threshold or a predetermined stationary threshold.The thresholds aim to impose an effective arrival rate of 1/eM per transmitter, matching the channel’s useful operating point.
  • Generalization: The stationary thinning mechanism also extends to other random access technologies, attaining normalized age 1/(2C) for a technology with throughput C and approaching order-optimality as M grows.The paper reports numerical comparisons with centralized policies, lower bounds, and distributed schemes, including moderate network sizes.

A. Notation

The paper introduces notation for transmitters, time horizons, deliveries, age evolution, and random-access capacity. It also uses age-gain to characterize age-based scheduling decisions.

  • M denotes the number of transmitters, K the time horizon, and C the channel capacity.
  • The mth delivered packet arrives at time Ti(m), after experiencing delay Di(m), and the receiver age drops to Di(m).
  • Γi(m) sums the age function hi(k) over the interval between consecutive delivery times Ti(m) and Ti(m + 1).
  • The normalized age analysis uses transmitter delivery counts Ni(K) and the random-access channel sum-capacity CRA.
  • The lower bound Jπ(M) ≥ 1 2CRA + 1 2M relates age performance to channel capacity and the number of transmitters.
  • Age-gain δi(k) measures the reduction in instantaneous receiver age produced by successful delivery from transmitter i.

V. DECENTRALIZED AGE-BASED POLICIES

The paper develops decentralized age-based policies for random access channels by selecting transmissions according to packet age-gains. The policies use threshold-based thinning to target an effective arrival rate that matches slotted ALOHA’s supportable rate.

  • Age-based thinning: The proposed policies prioritize transmissions using each packet’s age-gain, enabling decentralized age-aware access decisions.Transmitters with age-gains at least T(k) become active, while those below the threshold remain inactive or discard their fresh packets.
  • Operating regimes: For large M, the analysis separates infrequent arrivals θ ≤ 1/(eM) from frequent arrivals θ > 1/(eM).This division follows the throughput behavior of stabilized slotted ALOHA.
  • Slotted ALOHA baseline: Slotted ALOHA is stable below θ < 1/(eM), with asymptotic per-slot delivery probability 1/e, collision probability 1 − 2/e, and idle probability 1/e.When Mθ < 1/e, the expected total number of delivered packets per slot is Mθ.
  • Slotted ALOHA baseline: When θ approaches 1/(eM), stabilized slotted ALOHA’s normalized age approaches e, while increasing θ beyond this point sharply increases normalized age.Beyond the throughput limit, the estimated active population and backoff probability become mismatched to the optimal transmission probability.
  • Threshold design: Thresholds can be adapted from collision feedback or fixed analytically, with adaptive estimation proceeding through arrival, threshold-selection, and feedback-update stages.The adaptive procedure estimates the age-gain node distribution, chooses T(k), and updates that estimate using collision feedback.
  • Threshold design: The thinning policies retain high-age-gain packets and aim to impose an effective per-transmitter arrival rate of 1/(eM).Rates below 1/(eM) underuse the channel, whereas larger rates create a packet pool exceeding slotted ALOHA’s support.

C. Estimating the node distribution

The adaptive policy estimates the age-gain distribution from arrivals and collision feedback, then updates transmission probabilities and thresholds accordingly. Numerical results report substantial age reductions beyond slotted ALOHA’s throughput limit, alongside estimation inaccuracies caused by integer thresholds.

  • Distribution estimation: The end-of-slot estimate updates the age-gain node distribution using whether the slot was idle, successful, or collided.The update is used to compute the next slot’s threshold and treats c(k)=0 and c(k)=1 separately.
  • Distribution estimation: Conditioned on no collision, a packet is delivered with probability 1/2 for large M, and active nodes have symmetric delivery chances.The expected number of delivered packets from m-order nodes is then incorporated into the distribution update.
  • Performance: Algorithm 1 significantly reduces normalized age beyond sum arrival rate 1/e, reaching an NAAoI almost equal to 1 as θ approaches 1.The reported improvement comes from selecting and delivering packets with large age-gains, and its throughput exceeds standard slotted ALOHA in the comparison.
  • Adaptive policy: Algorithm 1 transmits from transmitter i only when δ_i(k+) ≥ T(k), using the stabilized ALOHA transmission probability p_b(k).Its update replaces Mθ by min(Mθ, e^-1) when calculating the next backoff probability.
  • Estimation caveat: The adaptive estimates are not exact because the threshold is integer-valued and may produce an effective arrival rate larger than 1/(eM).The update equations assume an effective arrival rate of 1/e, which creates inaccuracies in the estimated node distributions.
  • Adaptive policy: The adaptive threshold is distinguished from the fixed-threshold method because its distribution estimate is updated using collision feedback.Without conditioning on collision feedback, the analysis yields a fixed limiting threshold T* instead.

D. Fixed Threshold

The fixed-threshold policy selects a threshold analytically in advance, avoiding collision-feedback adaptation while targeting an effective arrival rate near 1/e. In the large-system regime, it substantially lowers normalized age relative to stabilized slotted ALOHA.

  • The fixed threshold T* is designed from the stationary node distribution, making the policy analytically tractable but unable to use collision feedback.The resulting stationary age-based thinning policy is described as Algorithm 2.
  • The threshold targets an effective sum arrival rate approximately equal to 1/e by selectively thinning packets according to age-gain.Larger arrival rates require more thinning, while smaller rates underuse the channel.
  • For 0 < θ < 1/(eM), the closed-form threshold satisfies T* ≤ 0, so the proposed policy reduces to slotted ALOHA.
  • 2 is the asymptotic normalized age attained by SAT for θ = 1/o(M), a factor of 2 below the minimum stabilized slotted-ALOHA age.
  • The SAT proof partitions sources by age-gain threshold: sources below threshold dominate the asymptotic age, while sources above threshold contribute vanishingly.

E. Extensions to Other Random Access Technologies

The age-based thinning framework extends from slotted ALOHA to stationary random access technologies that do not code across packets. For a prescribed technology, the generalized policy uses a technology-dependent threshold and achieves an asymptotic age determined by its throughput.

  • The generalized framework applies to stationary random access policies without coding across packets, including ALOHA and CSMA.It preserves only each transmitter’s most recent packets before applying the prescribed access technology.
  • The fixed threshold has a simple closed-form expression and can be derived analytically for the generalized setting.
  • Algorithm 3 applies a decentralized age-based threshold to any given stationary random access technology.Transmitters remain silent below the threshold and use the selected technology when their age-gain exceeds it.
  • The generalized stationary policy reduces normalized age to 1/(2Cπ(1)) as θ increases, with lim M→∞ JGSAT(M) = 1/(2Cπ(1)).
  • Compared with prior work, the framework provides an explicit threshold, an analytical asymptotic normalized age, and applicability beyond CSMA.
  • The framework also applies to other multi-access technologies with sum capacity 1, whose normalized age tends to 1/2 as M becomes large.

VI. NUMERICAL RESULTS

Simulations evaluate adaptive and stationary age-based policies across transmitter counts, arrival rates, and random access technologies. They show substantial age gains beyond the slotted-ALOHA threshold, while also revealing regimes where adaptive thresholding underperforms the fixed policy.

  • For stationary age-based policies, normalized age converges to e/2 as M grows, validating the asymptotic result for M = 50, 100, 500.
  • The adaptive policy can achieve throughput beyond 1/e because it is not a slotted-ALOHA scheme and uses estimated age-gain distributions for coordination.
  • Adaptive thinning performs worse than stationary thinning for 1/(eM) ≤ θ ≤ 1/M, partly because integer thresholding can underestimate the adaptive threshold.
  • When θ exceeds 1/(eM), age-based thinning provides significant gains over randomized stationary and slotted-ALOHA schemes.
  • Under perfect CSMA, stationary thinning approximately attains the normalized age of centralized Max-Weight, while related sleep-wake policies show similar performance in the energy-adequate regime θ ≥ 0.1.
  • Policies that maximize throughput without packet management can have exploding NAAoI above the throughput threshold, whereas the proposed methods use channel capacity while minimizing NAAoI.
  • The conclusion notes that extending the framework to asymmetric arrival rates requires a more general estimation method, while dynamic known rates can be handled by time-varying parameters.

APPENDIX A SUFFICIENCY OF UNIT BUFFER SIZE

The appendix shows that larger buffers do not improve age: a unit-buffer policy can match the actions of a larger-buffer policy using only its newest packet. It also characterizes delivery and collision probabilities under slotted ALOHA.

  • Buffer sufficiency: A unit-buffer policy can emulate any larger-buffer policy by transmitting the newer packet whenever the latter transmits.If no packet is delivered, both ages increase equally; if delivery succeeds, the newer packet yields no larger age.
  • Random access channel: At most one packet can be delivered in a slot, while simultaneous transmissions collide and deliver nothing.The collision-channel analysis distinguishes idle slots, successful singleton transmissions, and collisions.
  • Slotted ALOHA: For large M, an attempted-transmission rate G gives delivery probability Ge^−G, maximized at G = 1 with probability 1/e.At G = 1, the corresponding collision and idle probabilities are 1−2/e and 1/e.

APPENDIX F PROOF OF THEOREM 1.

The proof derives asymptotic age bounds for symmetric slotted ALOHA systems by decomposing age into delivery and queue-related components. It then shows that slotted ALOHA attains the lower bound when θ ≤ 1/(eM).

  • NAAoI decomposition: The proof decomposes NAAoI into terms associated with source age, delivery timing, and residual queue-related age.It analyzes these terms using stationarity, geometric inter-arrival times, throughput, and large-time limits.
  • Large-system limit: The queue-related contribution vanishes as M grows because the fraction of sources with positive excess age tends to zero.Although conditional excess age is O(M), the probability of positive excess age vanishes in the large-M limit.
  • Optimality regime: Slotted ALOHA reaches the universal lower bound 1/η when θ ∈ (0, 1/(eM)], and is therefore asymptotically optimal there.The result follows by matching the slotted-ALOHA age expression to the lower bound for any scheme.

APPENDIX G PROOF OF LEMMA 1.

The lemma tracks how source-node orders evolve after packet arrivals. A new arrival strictly increases the order of any node that already has positive order, while zero-order nodes become higher-order nodes after receiving an arrival.

  • Order transitions: A zero-order node has equal source and destination ages before an arrival, so receiving a new packet changes its excess age from zero to positive.Thus, a zero-order source becomes a higher-order source after a new arrival.
  • Order transitions: For every m-order node with m ≥ 1, a new arrival increases its order because the new packet resets source age while destination age remains unchanged.The resulting excess age is m + wi(k−), which is strictly greater than m.
  • Recursive characterization: The fractions of nodes entering each order can be computed recursively from arrival probability θ and the geometric distribution of source age.The proof establishes the resulting expressions by induction over the order index.

APPENDIX I PROOF OF THEOREM 2.

The proof evaluates NAAoI in the large-system regime by separating source-age and excess-age terms under symmetric arrivals. It uses the threshold scaling to characterize the limiting populations of inactive and active nodes.

  • Asymptotic decomposition: The analysis treats all sources symmetrically and uses the common distribution of wi(k+) to evaluate the source-age contribution.Stationarity and the Cesàro mean lemma are used to obtain long-run averages.
  • Threshold regime: When θ = 1/o(M) and θ > 1/(eM), the threshold satisfies T* = floor(eM − o(M) + 1).This scaling is used in the large-M evaluation of the excess-age terms.
  • Node populations: The expected numbers of inactive and active nodes are respectively MsT* and M(1 − sT*).These quantities describe the limiting population split induced by the threshold.

APPENDIX K PROOF OF THEOREM 4.

The proof derives the theorem by summing prior relations and applying the threshold definition together with established bounds.

  • The argument sums equation (29) on both sides.
  • The threshold T∗ is analyzed using its definition in (19).
  • The proof invokes prior results, including (85), (37), and (87), while using that T∗ is integer.

APPENDIX L PROOF OF THEOREM 5.

The proof of Theorem 5 follows the structure of Theorem 3, replacing the channel’s sum arrival rate with Cπ(1) and deriving delay and age bounds.

  • Theorem 5’s proof is almost identical to Theorem 3’s, with e−1 replaced by Cπ(1).The replacement is made in the corresponding proof parts.
  • The delay bound supports the proof because the post-threshold age increment has expectation O(M).The argument bounds the relevant peak age using the threshold, inter-arrival time, and delivery delay.
  • lim M→∞E[JGSAT (M)] = 1 2Cπ(1) .The limit follows after summing J1, J21, and J22.
  • E[Ii] = M Cπ(1)(M) relates the expected inter-delivery time to the sum throughput.The argument uses statistical identity among nodes to obtain this relation.
  • For any ϵ > 0, sufficiently large M satisfies Cπ(1)(M) ≥ Cπ(1) −ϵ, yielding E[Di] ≤ M Cπ(1) −ϵ ≜c′M.The constant c′ depends on the employed transmission policy.
Loading 1912.01473v6…