Source-linked AI summary
Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks
Igor Kadota, Abhishek Sinha, Elif Uysal-Biyikoglu, Rahul Singh, Eytan Modiano
TL;DR
The paper asks how to minimize the expected weighted sum Age of Information when a base station sends periodic updates over unreliable broadcast channels. It formulates a discrete-time scheduling problem, proves Greedy optimality for symmetric networks, and develops low-complexity alternatives with guarantees for general networks. Simulations find Max-Weight and Whittle’s Index comparable to optimal performance and outperform Greedy and randomized policies in general settings.
Problem
The paper addresses AoI minimization for periodically generated updates sent to multiple clients over unreliable broadcast channels, where delivery regularity matters beyond throughput.
Method
The paper formulates a discrete-time weighted-sum AoI scheduling problem and analyzes Greedy, randomized, Max-Weight, and Whittle’s Index policies.
Results
Max-Weight and Whittle’s Index are comparable to optimal performance in every simulated network setting and outperform Greedy and randomized policies in general networks.
Takeaways & Limitations
Greedy provides an optimal low-complexity policy for symmetric networks, while Max-Weight and Whittle’s Index provide strong performance across the simulated settings.
Abstract
from arXiv · showhide
We consider a wireless broadcast network with a base station sending time-sensitive information to a number of clients through unreliable channels. The Age of Information (AoI), namely the amount of time that elapsed since the most recently delivered packet was generated, captures the freshness of the information. We formulate a discrete-time decision problem to find a transmission scheduling policy that minimizes the expected weighted sum AoI of the clients in the network. We first show that in symmetric networks a Greedy policy, which transmits the packet with highest current age, is optimal. For general networks, we develop three low-complexity scheduling policies: a randomized policy, a Max-Weight policy and a Whittle's Index policy, and derive performance guarantees as a function of the network configuration. To the best of our knowledge, this is the first work to derive performance guarantees for scheduling policies that attempt to minimize AoI in wireless networks with unreliable channels. Numerical results show that both Max-Weight and Whittle's Index policies outperform the other scheduling policies in every configuration simulated, and achieve near optimal performance.
I. INTRODUCTION
The paper studies Age of Information minimization for periodically generated packets sent over unreliable broadcast channels. It establishes Greedy optimality in symmetric networks and develops low-complexity policies with guarantees for general networks.
- I. INTRODUCTION: AoI captures information freshness at the destination, and good performance requires both low packet delay and regular packet deliveries.Equal throughput can still produce different freshness when delivery regularity differs.
- I. INTRODUCTION: The paper develops Greedy, randomized, Max-Weight, and Whittle’s Index scheduling policies to reduce the computational burden of dynamic programming.Dynamic programming can be computationally demanding for networks with many clients because of the curse of dimensionality.
- I. INTRODUCTION: For general networks, the paper compares policies with the optimal AoI and derives performance guarantees, addressing unreliable-channel scheduling.The authors identify this as the first work to derive such guarantees for AoI-minimizing policies in unreliable wireless networks.
- I. INTRODUCTION: The model considers a base station that periodically generates one packet per client and transmits selected packets over unreliable wireless channels.Each frame contains newly generated client packets, while transmission success depends on the selected client’s channel.
- I. INTRODUCTION: Greedy is AoI-optimal in symmetric networks, where clients have equal channel reliabilities and weights.For error-free channels, Greedy reduces the highest ages to unity each frame and follows a Round Robin delivery pattern.
IV. AGE OF INFORMATION GUARANTEES
The paper derives a universal lower bound for long-term expected AoI and uses it to evaluate four low-complexity scheduling policies. The bound is based on inter-delivery statistics and supports performance guarantees, including evidence that it can be tight.
- Dynamic programming is computationally demanding because the network state space grows exponentially with the number of clients.The state vector has at least k^M possible values after k frames.
- The analysis considers Greedy, Randomized, Max-Weight and Whittle’s Index policies and derives performance guarantees for each.These policies provide lower-complexity alternatives to directly optimizing the objective.
- A universal lower bound LB is established for the limiting expected objective of every admissible policy.The proof uses a sample-path characterization, algebraic manipulation of the infinite-horizon objective, and Fatou’s lemma.
- The infinite-horizon analysis expresses AoI through moments of clients’ inter-delivery times and excludes policies that starve clients.Starving a client makes its expected objective diverge, so such policies are excluded without loss of optimality.
- For the Greedy policy, the lower bound is tight in symmetric networks with large M and also appears tight in other configurations numerically.Under the stated symmetric large-network condition, the Greedy performance guarantee satisfies ρG = 1.
B. Greedy Policy
The Greedy policy prioritizes the client with the highest current age among clients whose packets remain undelivered. Its closed-form guarantee reaches optimality for symmetric networks as the number of clients grows.
- The Greedy performance guarantee ρG is expressed using statistics of the clients’ inverse channel-success probabilities.The coefficient of variation measures dispersion in the values {1/pi} across clients.
- The Greedy policy minimizes expected sum AoI in any symmetric network as M →∞.Greedy uses current client ages but does not account for differences in weights or channel reliabilities.
- ρG = 1 if and only if all clients have equal weights αi = α and equal success probabilities pi = p.Equality requires both inequalities used in the guarantee derivation to hold with equality.
C. Stationary Randomized Policy
The Stationary Randomized policy selects clients using fixed probabilities, without using current or past network states. Its analysis yields a closed-form guarantee and a 2-optimal result for one-slot frames.
- The Randomized policy selects client i in each slot with probability βi divided by the sum of all clients’ β values.The parameters βi are fixed and positive.
- The policy uses no current or past network-state information and may idle while clients still have undelivered packets.This occurs because the selected client may already lack an undelivered packet.
- Under Randomized scheduling, packet deliveries form a renewal process with geometric inter-delivery times.The inter-delivery-time distribution is independent of the delivery index m.
- For T = 1 slot per frame, a Randomized policy using only αi and pi knowledge achieves 2-optimal performance across network setups.The section derives the guarantee under T = 1 and states the broader derivation for general T is in the appendix.
D. Max-Weight Policy
The Max-Weight policy minimizes Lyapunov drift by prioritizing clients using channel reliability, weight, and current age. It coincides with Greedy in symmetric networks and has a provable performance guarantee for general networks.
- Policy derivation: The Max-Weight policy minimizes one-frame Lyapunov drift using a weight based on each client’s age and importance.Its weight function is G_i(h_k,i) = α_i h_k,i(h_k,i + 2).
- Policy derivation: In each slot, Max-Weight transmits to the eligible client maximizing p_i α_i h_k,i(h_k,i + 2).Ties are broken arbitrarily.
- Optimality and guarantees: When all clients share the same weight and channel reliability, Max-Weight is identical to Greedy and is AoI-optimal.For general networks, the paper derives a performance guarantee ρ_MW.
- Performance: Numerical results show that Max-Weight outperforms Greedy and Randomized in every simulated network setup and is comparable to Dynamic Programming.The policy uses channel reliabilities, client weights, and current ages when scheduling.
- Analysis: The Max-Weight analysis is less tight because the policy lacks the simplifying structure needed for Renewal Theory.Unlike Greedy and Randomized, Max-Weight cannot be evaluated using Renewal Theory or fixed selection patterns.
B. Frame-Based Decoupled Model
The Frame-Based Decoupled Model reformulates the single-client problem over whole frames, preserving the relevant scheduling policies and enabling infinite-horizon analysis. Its optimal stationary policy is threshold-based.
- Model formulation: The frame-level decision u_k selects either idling throughout a frame or repeated transmission until delivery or frame termination.The model represents the system state by the age h_k at the beginning of each frame.
- Model formulation: The Frame-Based Decoupled Model is equivalent to the Decoupled Model over the restricted policy class Γ and therefore has the same optimal policy.A frame transmission incurs expected service charge Ĉ = C(1 − (1 − p)^T)/p.
- Dynamic programming: The infinite-horizon Bellman equation compares idling with transmitting until delivery or frame end.The two actions differ through the service charge and the transition probability after attempted transmission.
- Threshold policy: The optimal stationary policy is a threshold policy: transmit when h > H − 1 and idle when 1 ≤ h ≤ H − 1.The threshold H is determined by the service charge and model parameters.
- Threshold policy: The threshold behavior reflects a trade-off between reducing high age and avoiding the transmission service charge.The paper notes that higher age favors transmission, whereas lower age favors idling.
C. Indexability and Index Policy
The paper establishes indexability of the decoupled AoI problem, derives Whittle’s Index, and uses it to prioritize the most valuable undelivered packet. Simulations show strong performance across network configurations, while extensions remain open.
- Indexability: Indexability follows because the idling set grows monotonically from the empty set to the full state space as service charge C increases.The threshold H increases with C, establishing indexability for every client’s decoupled model.
- Index definition: Whittle’s Index C(h) is the smallest service charge making idling and transmission equally desirable in state h.The closed-form index is obtained by setting the threshold to H = h + 1.
- Index policy: Whittle’s Index schedules the eligible client with the highest index value, interpreting that index as the service charge worth paying for transmission.This policy is similar to Max-Weight despite being derived through a different method.
- Simulation results: Max-Weight and Whittle’s Index are comparable to optimal Dynamic Programming performance in every two-user setting evaluated.Figures 5 and 6 cover symmetric and non-symmetric two-user networks.
- Simulation results: For larger and general networks, Max-Weight and Whittle’s Index outperform Greedy and Randomized in the simulated configurations.All examined policies require low computational resources even with many clients.
- Scope and extensions: The model assumes periodic packet generation and could be extended to stochastic arrivals, time-varying channels, and multi-hop networks.A polling network with on-demand generation is represented by the special case T = 1.
APPENDIX A PROOF OF LEMMA 2
The appendix shows that Greedy serves clients in a Round Robin pattern, including with unreliable channels, and proves optimality in symmetric networks under the stated conditions.
- Round Robin structure: Greedy delivers packets to clients in the index sequence (1,2,···,M,1,2,···), following a Round Robin pattern.For error-free channels, the schedule is established through repeated frame-level cyclic shifts.
- Round Robin structure: With unreliable channels, Greedy retransmits to the same client after failures, so transmission failures do not change delivery order.Thus, Greedy follows a Round Robin pattern regardless of the network setup.
- Optimality: In symmetric error-free networks, Greedy attains the minimum sum AoI among admissible policies.The result assumes equal channel reliabilities p_i = 1 and equal positive weights α_i = α.
- Optimality: The proof establishes optimality by showing that Greedy minimizes the objective in every frame through properties of circular ordering.The relevant terms are minimized using the coverage and ordering properties of Greedy, while the remaining term is constant.
Supplementary Material for the paper “Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks”
The supplementary proof extends Greedy’s symmetric-network optimality result to unreliable channels using stochastic dominance and stochastic coupling.
- Optimality theorem: Theorem 5 states that Greedy minimizes expected sum AoI in symmetric networks with common reliability p and common positive weight α.The conclusion holds over the class of admissible policies Π.
- Stochastic-dominance proof: The proof compares Greedy with an arbitrary policy through stochastic dominance of the processes representing cumulative age.Stochastic coupling places the processes on a common probability space to establish the required ordering.
- Stochastic-dominance proof: The coupling assigns Greedy the channel outcome observed by the client selected by the arbitrary policy in each slot.This preserves the relevant channel-state distribution while enabling a pathwise comparison.
- Stochastic-dominance proof: Slots with channel state OFF can be removed from the comparison because they cannot change the relationship between the two cumulative-age processes.The error-free-channel result then applies to the remaining slots, yielding the required stochastic ordering.
APPENDIX D PROOF OF THEOREM 8
The appendix derives Greedy’s performance guarantee by modeling packet deliveries as renewal processes and bounding their inter-delivery moments.
- Performance guarantee: Theorem 8 states that Greedy is ρG-optimal as M →∞ for a network specified by clients, frame length, reliabilities, and weights.The guarantee is obtained from an upper bound on Greedy’s objective divided by a universal lower bound.
- Renewal-process analysis: Greedy’s Round Robin behavior decomposes each inter-delivery interval into packet transmissions and possible idle slots.The idle-slot count satisfies 0 ≤ W_i[m] < T.
- Renewal-process analysis: Under Greedy, each client’s packet deliveries form a renewal process with i.i.d. inter-delivery times.The analysis uses a renewal-reward theorem to evaluate the long-run objective.
- Performance guarantee: The resulting upper bound yields the closed-form performance guarantee ρG after division by the universal lower bound.The appendix notes that the guarantee equals one for symmetric networks with large M.
APPENDIX F PROOF OF THEOREM 12
The appendix derives Max-Weight’s performance guarantee by bounding its Lyapunov drift and relating the bound to randomized-policy throughput.
- Performance guarantee: Theorem 12 states that MaxWeight is ρMW-optimal for an infinite-horizon network characterized by M, T, p_i, and α_i.The guarantee is expressed as a function of the network configuration.
- Lyapunov-drift analysis: The proof bounds the one-frame Lyapunov drift by analyzing its left- and right-hand terms separately.Jensen’s inequality and further algebraic bounds are applied during this derivation.
- Lyapunov-drift analysis: The resulting Max-Weight bound is expressed using expected client delivery quantities and an inequality previously derived for the randomized policy.A randomized policy assignment with β_i = α_i/p_i converts the bound into a function of network parameters.
- Performance guarantee: Dividing the final upper bound by the universal lower bound gives the performance guarantee ρMW.This completes the stated guarantee for Max-Weight.
APPENDIX G PROOF OF PROPOSITION 14
The appendix verifies that the Bellman-equation solution is a threshold policy: transmit when h ≥ H and idle when 1 ≤ h < H. It derives closed-form expressions for the differential cost-to-go, threshold, and optimal average cost, then checks consistency.
- Threshold policy: The optimal stationary policy transmits when h ≥ H and idles when 1 ≤ h < H.This threshold structure is the proposition’s central claim.
- Bellman-equation solution: Assuming the threshold structure, the proof solves the Bellman equations separately for states h ≥ H and 1 ≤ h < H.The two state regions yield separate recursions for the differential cost-to-go S(h).
- Bellman-equation solution: The resulting expressions determine S(h) as a function of H and the optimal average cost λ.The proof uses the expressions from both state regions to solve for the unknown threshold and average cost.
- Threshold identification: Monotonicity of S(h) around the threshold establishes a unique integer-valued threshold H through a parameter γ∗ ∈ [0,1).H decreases monotonically with γ, and a unique γ∗ makes H integer-valued.
- Consistency check: The proof confirms consistency by showing the Bellman inequalities hold for both regions, so the derived solution indeed has threshold-policy form.Monotonicity of S(H + j+) implies the required condition, completing the verification.
APPENDIX H PROOF OF THEOREM 17
The appendix derives the Whittle Index performance guarantee by bounding its one-frame Lyapunov drift. Because the Whittle policy minimizes this drift bound, the resulting guarantee matches the upper-bound form obtained for Max-Weight.
- Policy comparison: The Whittle Index policy selects the action that maximizes the relevant sum, differing from Max-Weight only in its final term.The proof isolates this final term before constructing the drift bound.
- Drift bound: An upper bound on the one-frame Lyapunov drift is constructed with the Whittle Index policy as its minimizer.The proof then applies arguments analogous to those used for the Max-Weight guarantee.
- Drift bound: Any other policy, including the Randomized Policy, yields a higher or equal drift bound under this construction.The Randomized Policy has expected throughput that is constant across frames and independent of the network state.
- Performance bound: The Whittle Index performance upper bound is expressed as a function of E[d_i] and uses an auxiliary variable eα_i.The derivation applies Jensen’s inequality and Cauchy-Schwarz to bound the relevant terms.
- Performance guarantee: The Whittle Index upper bound is identical to the Max-Weight upper bound, and dividing by the lower bound in (7) yields ρ_WI.This completes the stated performance guarantee for the Whittle Index policy.