Source-linked AI summary
Minimizing the Age of Information in Wireless Networks with Stochastic Arrivals
Igor Kadota, Eytan Modiano
TL;DR
The paper asks how to minimize information age in wireless networks with stochastic arrivals, per-stream queues, and unreliable channels. It derives a discipline-independent lower bound and develops randomized and Max-Weight policies across three queueing disciplines. Simulations show that Age-Based Max-Weight for LIFO queues performs close to the analytical lower bound.
Problem
The central problem is minimizing destination information age when stochastic packet arrivals and queueing determine which fresh packets are available.
Method
The paper derives a universal AoI lower bound and develops Optimal Stationary Randomized and Age-Based Max-Weight policies for three queueing disciplines.
Results
Age-Based Max-Weight for LIFO queues performs close to the analytical lower bound in simulation results.
Takeaways & Limitations
The framework enables evaluation of the combined impact of stochastic arrivals, queueing discipline, and scheduling policy on AoI.
Takeaways & Limitations
The model assumes Bernoulli arrivals that are independent across streams and over time.
Abstract
from arXiv · showhide
We consider a wireless network with a base station serving multiple traffic streams to different destinations. Packets from each stream arrive to the base station according to a stochastic process and are enqueued in a separate (per stream) queue. The queueing discipline controls which packet within each queue is available for transmission. The base station decides, at every time t, which stream to serve to the corresponding destination. The goal of scheduling decisions is to keep the information at the destinations fresh. Information freshness is captured by the Age of Information (AoI) metric. In this paper, we derive a lower bound on the AoI performance achievable by any given network operating under any queueing discipline. Then, we consider three common queueing disciplines and develop both an Optimal Stationary Randomized policy and a Max-Weight policy under each discipline. Our approach allows us to evaluate the combined impact of the stochastic arrivals, queueing discipline and scheduling policy on AoI. We evaluate the AoI performance both analytically and using simulations. Numerical results show that the performance of the Max-Weight policy is close to the analytical lower bound.
1 INTRODUCTION
The paper studies Age of Information minimization in wireless networks where stochastic arrivals, queueing disciplines, and unreliable channels jointly shape scheduling decisions. It derives a universal lower bound, develops policies under three queueing disciplines, and finds that Age-Based Max-Weight for LIFO is close to that bound.
- Motivation: AoI measures how fresh information is from the destination’s perspective.The metric tracks elapsed time since the generation of the freshest packet received by a destination.
- Challenge: Random packet arrivals can leave the base station without a fresh packet for every stream, so scheduling must consider both destination AoI and available packet timestamps.The paper contrasts this setting with systems where fresh packets are always available.
- Challenge: Designing freshness-aware scheduling is challenging because packet arrivals, queueing discipline, and wireless-channel conditions interact.The paper frames these factors as jointly relevant to transmission decisions.
- Contributions: The framework derives a lower bound valid for any network operating under any queueing discipline.This lower bound is used to assess the performance of the proposed policies.
- Contributions: The authors develop Optimal Stationary Randomized and Age-Based Max-Weight policies for three common queueing disciplines.The framework evaluates the combined effects of stochastic arrivals, queueing discipline, and scheduling policy on AoI.
- Results: The Age-Based Max-Weight policy for LIFO queues performs close to the analytical lower bound in simulations.Single packet queues are treated as equivalent to LIFO queues from the perspective of AoI.
2 SYSTEM MODEL
The system is a slotted wireless network with Bernoulli arrivals, per-stream queues, unreliable channels, and one possible transmission per slot. AoI evolves according to successful deliveries and the system age of the transmitted head-of-line packet, while FIFO instability can make AoI diverge.
- Network model: At each slot, stream i receives a Bernoulli packet independently over time and across streams, with arrival probability λ_i.The arrival indicator is a_i(t), and P(a_i(t) = 1) = λ_i.
- Queueing disciplines: Packets are stored in separate per-stream queues, whose discipline determines which head-of-line packet is available for transmission.The base station can select at most one stream in each slot.
- Queueing disciplines: FIFO serves the oldest packet, Single packet queues retain the freshest packet by dropping older same-stream packets, and No queues permit transmission only upon arrival.Single packet queues are equivalent to LIFO queues from the AoI perspective.
- Transmission model: A successful reception occurs when the selected head-of-line packet is transmitted over an ON channel, with d_i(t) = c_i(t)u_i(t).Channel states are independent across destinations and over time, and the base station does not know them before scheduling.
- Age dynamics: AoI increases by one when no fresher packet is delivered and resets to the delivered packet’s system time plus one after a successful delivery.This gives h_i(t + 1) = z_i(t) + 1 after delivery and h_i(t + 1) = h_i(t) + 1 otherwise.
- Queue stability: If FIFO is unstable, backlog and packet system times grow indefinitely, causing Expected Weighted Sum AoI to diverge.The policies therefore seek stability whenever arrival rates lie within the network’s stability region.
3 LOWER BOUND
The paper rewrites the AoI objective using packet delays and inter-delivery times, then derives a lower bound valid for arbitrary queueing disciplines and scheduling policies. The resulting optimization depends only on long-term throughput, and its unique solution is characterized analytically.
- AoI reformulation: The AoI objective is expressed in terms of packet delay and inter-delivery times for each destination.Inter-delivery time measures the interval between successive packet deliveries, while packet delay is the delivered packet’s system time.
- Lower-bound solution: The lower-bound optimization depends only on the network’s long-term throughput, and its unique solution is obtained using KKT conditions and Algorithm 1.The paper then develops Optimal Stationary Randomized policies for different queueing disciplines using this lower-bound framework.
- AoI reformulation: The reformulation shows that AoI depends on service regularity and on the interaction between packet delays and inter-delivery times.The packet-delay contribution is a weighted sample mean, so high-delay packets should be followed by prompt delivery when possible.
- Lower-bound derivation: Applying Jensen’s inequality to the reformulated objective yields a lower-bound optimization problem over policies and long-term throughput constraints.The throughput constraints include limits imposed by packet arrival rates and network operating conditions.
- Lower-bound derivation: The lower bound applies to any given network operating under an arbitrary queueing discipline.Theorem 3 states the bound as LB ≤ E[J*].
4 STATIONARY RANDOMIZED POLICIES
Stationary Randomized policies select streams using fixed probabilities, and their AoI depends on the queueing discipline and network parameters. The paper derives discipline-specific optimal probabilities and compares their performance.
- Stationary Randomized policies choose streams using fixed probabilities and do not account for ages, timestamps, or queue backlogs.They may idle even when head-of-line packets are available.
- Properly tuned scheduling probabilities achieve performance within a factor of 4 from the AoI-optimal.The probabilities are tuned according to network parameters including reliabilities, arrival rates, and priorities.
- Single packet queues: For Single packet queues, the optimal scheduling probabilities depend only on priorities and channel reliabilities, not arrival rates.This separates arrival-rate design from scheduling-probability design for this discipline.
- No queues and FIFO queues: For No queues and FIFO queues, the optimal scheduling probabilities vary with the arrival rates.No-queue packets are available only in their arrival slots, while FIFO performance is also affected by backlog and stability.
- FIFO queues: For FIFO queues, the optimal policy stabilizes the network whenever arrival rates lie within the stability region.A naive policy can fail to stabilize the network despite the arrival rates being stabilizable.
5 AGE-BASED MAX-WEIGHT POLICIES
Age-Based Max-Weight policies use current destination ages and available-packet timestamps to choose transmissions. They minimize a Lyapunov-drift objective, provide analytical bounds for two disciplines, and outperform Randomized policies in numerical comparisons.
- The Max-Weight policy minimizes the expected drift of a Lyapunov function to keep network AoI small.The Lyapunov function increases with network age, and its drift represents the expected one-slot increase.
- In each slot, Max-Weight serves the stream with a head-of-line packet having the highest value of β_i p_i(h_i(t) − z_i(t)).The policy is work-conserving and idles only when all queues are empty.
- The quantity h_i(t) − z_i(t) represents the AoI reduction from a successful packet delivery to destination i.This quantity motivates prioritizing packets with greater potential age reduction.
- Analytical performance bounds are established for Max-Weight policies under Single packet and No queue disciplines.The corresponding bounds use the optimal randomized scheduling probabilities and their attained EWSAoI values.
- Max-Weight policies outperform Randomized policies because they use current ages and timestamps rather than fixed stream-selection probabilities.The paper notes that deriving tight guarantees is challenging for policies without renewal-interval properties.
6 NUMERICAL RESULTS
The numerical evaluation compares randomized, Max-Weight, and Whittle’s Index policies across queueing disciplines as arrival rates increase. Max-Weight performs best among corresponding policies, while FIFO becomes unstable beyond λ > 12/77.
- Policy comparisons: The evaluation compares randomized, Max-Weight, and Whittle’s Index policies across Single packet, No queues, and FIFO disciplines.The lower bound is also displayed for comparison.
- Simulation setup: The simulations use T = 2 × 10^6 slots, N = 4 traffic streams, specified priorities and channel reliabilities, and λ values from 0.01 to 0.35.Max-Weight and Whittle’s Index results average 10 simulation runs.
- Results: Max-Weight outperforms the corresponding Randomized and Whittle’s Index policies for every value of λ.This comparison is made within the same queueing discipline.
- Results: Single packet queues outperform the other queueing disciplines under the same scheduling-policy class for every value of λ.The paper reports this ordering as expected.
- Results: FIFO queues become unstable when λ > 12/77, which the results identify as a major disadvantage of that discipline.
7 CONCLUDING REMARKS
The paper studies Expected Weighted Sum AoI in wireless networks with Bernoulli arrivals and three queueing disciplines. It derives a lower bound, develops two policies per discipline, and evaluates their combined effects analytically and numerically.
- System model: The network uses separate FIFO, Single packet, or No queues for traffic streams with Bernoulli packet arrivals.Single packet queues are equivalent to LIFO queues from the perspective of AoI.
- Contributions: The paper derives a lower bound on AoI performance for any network and queueing discipline.
- Contributions: It develops an Optimal Stationary Randomized policy and a Max-Weight policy under each queueing discipline.
- Evaluation: The study evaluates how stochastic arrivals, queueing discipline, and scheduling policy jointly affect AoI using analytical and numerical results.
- Findings: The Optimal Stationary Randomized policy for Single packet queues is insensitive to packet arrival rates.
A PROOF OF PROPOSITION 2
The proof expresses time-average AoI through inter-delivery times, packet delays, and residual horizon terms, then takes a long-horizon limit under finite-delay assumptions.
- Long-horizon limit: The proof substitutes the finite-horizon expression into a sample-mean formulation before taking the limit T → ∞.
- Finite-horizon decomposition: For each sample path, the proof tracks deliveries, packet delays, inter-delivery times, and slots remaining after the final delivery.
- Finite-horizon decomposition: AoI evolves linearly between deliveries, starting from the previous delivered packet’s delay and increasing across each inter-delivery interval.
- Finite-horizon decomposition: The time-average AoI expression includes squared inter-delivery terms, packet-delay contributions, and residual-horizon terms.
- Long-horizon limit: It assumes the head-of-line packet delay remains finite with probability one; otherwise, the expected objective diverges.
B PROOF OF THEOREM 3
Theorem 3 establishes an AoI lower bound through a throughput optimization problem and obtains its unique solution using KKT conditions and an iterative algorithm.
- Lower-bound derivation: The optimization problem in (14a)–(14c) lower-bounds the optimal expected AoI for any network and queueing discipline.
- Algorithmic solution: Algorithm 1 decreases γ until the throughput constraint is met or γ reaches the specified boundary, then computes the associated solution.
- Lower-bound derivation: The proof derives the bound from a valid AoI inequality, throughput constraints, and minimization over all admissible policies.
- Lower-bound derivation: The resulting bound depends only on the network’s long-term throughput and remains valid for every admissible policy.
- KKT solution: KKT conditions characterize the unique throughput solution and the associated multiplier γ* for the lower-bound optimization.
- Algorithmic solution: The proposed procedure yields an existing and unique KKT solution for any given network parameters and arbitrary queueing discipline.
C PROOF OF PROPOSITION 4
The proof models each stream under the Single packet queue discipline as a countable-state two-dimensional Markov Chain and derives its stationary distribution from categorized transitions.
- The optimal EWSAoI for Single packet queues over ΠR is characterized in Proposition 4.
- Each stream’s state is represented by a countably infinite two-dimensional Markov Chain involving hi(t) and zS_i(t).
- The proof separates state evolution into three transition categories and derives the associated probability distributions.
- The transition categories include successful transmission without arrival, packet arrival, and uneventful evolution to states with h > z.
- Substituting the stationary probability expression into the objective function yields Proposition 4.
- The resulting countable-state Markov Chain is irreducible, has a unique stationary distribution, and is positive recurrent.
D PROOF OF THEOREM 10
The proof establishes a performance bound for Age-Based Max-Weight under Single packet queues by comparing Lyapunov drift with the Optimal Stationary Randomized policy.
- Theorem 10 gives a performance bound for Max-Weight under Single packet queues with βi = wi/piµS_i.
- Dummy packets decouple packet transmissions from queue backlog without changing the associated AoI.
- After dummy packets are introduced, the system time zS_i(t) is defined at every slot, producing an equivalent system for analysis.
- Age-Based Max-Weight minimizes the Lyapunov drift, so every other policy has a higher or equal drift value.
- The proof obtains the upper bound by substituting the randomized scheduling probability into the drift expression and taking expectations and time averages.
E PROOF OF THEOREM 11
The proof derives a Max-Weight performance bound for the No queues discipline by treating successful arrivals as transmissions of always-fresh packets over virtual channels.
- Theorem 11 gives a performance bound for Max-Weight under No queues with βi = wi/piµN_i.
- Under No queues, a successful transmission requires packet arrival, stream selection, and an ON channel.
- Because every delivered packet has zN_i(t) = 0, the system is equivalent to one with always-fresh packets and virtual channels ON with probability piλi.
- Max-Weight selects a stream with a HoL packet having the highest value of β̂iλipihi(t), with ties broken arbitrarily.
- The upper bound follows by applying the Lyapunov-drift argument to the equivalent system and comparing it with the randomized policy.