PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Information Freshness in Wireless Networks under General Interference Constraints

Rajat Talak, Sertac Karaman, Eytan Modiano

arXiv:1803.06467v2cs.ITcs.NI

TL;DR

The paper asks how to minimize average and peak information age in wireless networks when general interference constraints limit simultaneous transmissions. It analyzes stationary scheduling for always-fresh sources and separates scheduling from packet-generation rate control for buffered sources. The resulting policy is peak-age optimal for active sources, within a factor of two for average age, and the discrete-time FIFO G/Ber/1 queue is analyzed for the first time.

  • Problem

    The paper addresses limited theoretical understanding of average and peak Age of Information minimization in wireless networks with general interference constraints.

  • Method

    The paper designs stationary link-scheduling policies and, for buffered sources, combines active-source scheduling with independently controlled Bernoulli or periodic packet-generation rates.

  • Results

    Stationary scheduling is peak-age optimal for active sources and within a factor of two of optimal average age; buffered sources admit a near-optimal separation of scheduling and rate control, with discrete-time FIFO G/Ber/1 age derived.

  • Takeaways & Limitations

    Scheduling can be designed assuming fresh information while packet-generation rate control ignores interference, matching the separation of protocol-stack functions.

Abstract

from arXiv · show

Age of information (AoI) is a recently proposed metric for measuring information freshness. AoI measures the time that elapsed since the last received update was generated. We consider the problem of minimizing average and peak AoI in a wireless networks, consisting of a set of source-destination links, under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: the optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time, which may be of independent interest.

I. INTRODUCTION

The paper studies information freshness in wireless networks, where interference limits simultaneous transmissions and prior theoretical work under such constraints was limited. It develops age-minimizing scheduling and rate-control policies for active and buffered sources, using average and peak age as performance metrics.

  • Motivation: Age of Information measures freshness from the destination’s perspective, unlike packet-centric delay or throughput.AoI is the elapsed time since the generation of the most recently received update; it drops upon reception and grows linearly otherwise.
  • Motivation: Wireless interference restricts simultaneous link activations, while age minimization under general interference constraints had received little theoretical attention.Earlier work included an NP-hard finite-packet problem, broadcast networks, and preliminary slotted ALOHA-like analysis.
  • Problem formulation: The paper minimizes average and peak age for source-destination links under general interference constraints and time-varying links.Only feasible subsets of links can transmit simultaneously, motivating simple scheduling policies that are optimal or nearly optimal.
  • Source models: Active sources always have fresh updates available, whereas buffered sources control packet-generation rates while packets wait in MAC-layer FIFO queues.The paper analyzes Bernoulli and periodic generation for buffered sources.
  • Main contributions: For active sources, a stationary scheduling policy is peak-age optimal and achieves average age within a factor of two of optimal.The policy activates links according to a stationary probability distribution and can be obtained through convex optimization.
  • Main contributions: For buffered sources, separating rate control from scheduling yields age close to the jointly optimized policy, while discrete-time FIFO G/Ber/1 peak and average age are derived for the first time.The separation performs rate control as if no other link existed and schedules as in the active-source case.

A. Scheduling Policies

The paper characterizes stationary scheduling under general interference constraints and shows that stationary policies achieve optimal or near-optimal age. For active sources, peak-age optimization reduces to choosing feasible activation frequencies, while buffered sources require joint rate control and scheduling.

  • Policy model: A scheduling policy selects the feasible set of links activated at each time, potentially using activation history, channel observations, and age information.The scheduler determines m(t) from available system history; current channel state is not observed before the decision.
  • Stationary policies: Stationary policies activate links independently across time according to a fixed distribution over feasible activation sets.A centralized stationary policy assigns probabilities to feasible activation sets, while distributed policies attempt individual links independently.
  • Active sources: For active sources, every transmission opportunity produces a fresh update, and peak age depends on each link’s successful activation frequency.Policies with zero successful activation frequency for any link have unbounded average and peak age.
  • Buffered sources: For buffered sources, the policy jointly controls update-generation rates and stationary scheduling, with a separation principle yielding age close to the joint optimum.Rate control can be designed assuming no other links, while scheduling follows the active-source policy.
  • Active sources: A stationary centralized policy is peak-age optimal, and its average age is within a factor of 2 of the optimal average age.The result follows because every policy has a stationary policy with the same peak age, while stationary policies have equal average and peak age.
  • Optimization: The peak-age optimization is a convex problem over activation probabilities of feasible activation sets, which determine the link activation frequencies.Its solution defines a stationary centralized policy that minimizes peak age and remains within a factor of 2 of optimal average age.

A. Optimal Stationary Policy πC

The peak-age problem is formulated as a convex optimization over activation-set probabilities, whose solution defines the stationary centralized policy πC. Optimality is characterized by equal Ω_m(x)-weights on positively selected sets, while non-maximal activation sets receive zero probability.

  • Convex formulation: The peak age minimization problem is optimized over x, the probabilities assigned to feasible activation sets in A.The induced link activation frequencies are determined by x.
  • Convex formulation: The resulting solution x defines a probability distribution over activation sets and a stationary centralized policy πC that minimizes peak age.The same policy achieves average age within a factor of 2 of the optimal average age.
  • Optimality characterization: An activation-probability vector x is optimal if positively selected sets have equal Ω_m(x)-weights, while zero-probability sets have weights no larger than the common value.The probabilities must also be nonnegative and sum to one; the common Ω value equals the optimal peak age.
  • Optimality characterization: Only maximal feasible activation sets receive positive probability in an optimal solution, eliminating non-maximal sets from the active support.For any non-maximal set, a strict superset has a larger Ω_m(x)-weight, contradicting positive probability for the smaller set.
  • Computational scope: Although the optimization is convex, its |A|-dimensional variable space can have computational complexity that grows exponentially in |V| and |E|.Efficient solution methods are available in certain specific cases, including interference graphs where feasible sets form matchings.

2) K-Link Activation Network:

This section models buffered updates through discrete-time FIFO queues and develops stationary scheduling and rate-control policies for minimizing peak and average age. It shows that discrete-time age can differ substantially from continuous-time benchmarks, while convex optimization and separation-based controls provide near-optimal designs.

  • A. Discrete Time G/Ber/1 Queue: A discrete-time FIFO G/Ber/1 queue has renewal packet arrivals with rate λ=E[X]^-1<µ and Bernoulli service at rate µ.The packet inter-arrival time X has a general distribution.
  • A. Discrete Time G/Ber/1 Queue: Discrete-time FIFO Ber/Ber/1 and D/Ber/1 peak and average ages differ from their continuous-time counterparts and are derived as special cases of G/Ber/1.The paper analyzes discrete-time FIFO G/Ber/1 age for the first time.
  • A. Discrete Time G/Ber/1 Queue: The system time T is geometrically distributed with rate α*, which depends on the inter-arrival distribution FX.Peak and average age are then computed from this system-time characterization.
  • A. Discrete Time G/Ber/1 Queue: Age differences between continuous- and discrete-time queues can be very large, especially when server utilization ρ approaches 1.Figure 2 compares peak and average age versus ρ=λ/µ with µ=0.8.
  • B. Bernoulli Generation of Update Packets: For buffered sources, the separation principle schedules as in the active-source case while controlling packet generation independently of contending links.Under stationary policies, this separated design is close to jointly optimal for peak and average age.

C. Periodic Generation of Update Packets

For periodic packet generation, the paper derives age expressions and uses continuous-time D/M/1 upper bounds to select queue occupancies independently of link activation frequency. The resulting separation policy is nearly optimal, with the age gap remaining below one in the analyzed comparison.

  • C. Periodic Generation of Update Packets: Periodic sources generate packets with link-specific period De, equivalently rate λe=1/De, jointly optimized with scheduling.The analysis considers stationary scheduling policies and periodic update generation.
  • C. Periodic Generation of Update Packets: The periodic discrete-time queue uses σ* satisfying σ=1−(1−γefeσ)^De, with σ*=α*/(γefe).This variable connects the periodic formulation to the G/Ber/1 system-time result.
  • C. Periodic Generation of Update Packets: The upper-bound minimizers ρp≈0.594 and ρave≈0.515 are independent of link activation frequency fe.The bounds correspond to continuous-time D/M/1 peak- and average-age expressions.
  • C. Periodic Generation of Update Packets: The peak and average ages at ρe=ρp and ρe=ρave, respectively, are each at most one unit from the optimum for all fe∈(0,1).The age difference is evaluated as a function of successful activation frequency γefe.
  • C. Periodic Generation of Update Packets: The periodic-generation separation policy uses active-source scheduling with rate controls ρe=ρp for peak age or ρe=ρave for average age.The resulting bounds follow from the one-unit comparison with the optimum.

V. PERFORMANCE BOUNDS FOR SPP

The paper extends its separation principle beyond stationary scheduling to policies using age and queue histories. For Bernoulli generation, the proposed stationary policy remains within constant factors of the broader optimum, independent of network size, while periodic generation yields smaller factors.

  • V. PERFORMANCE BOUNDS FOR SPP: The stationary analysis is extended to scheduling policies that condition decisions on link ages or buffer backlogs.These policies use queue-history information and form a larger policy space than stationary policies.
  • V. PERFORMANCE BOUNDS FOR SPP: For Bernoulli generation, the proposed separation principle policy is compared with the optimum jointly over update rates and queue-history-based scheduling.The comparison allows policies in ΠQ rather than only stationary policies.
  • V. PERFORMANCE BOUNDS FOR SPP: The Bernoulli separation policy’s peak-age guarantee is at most a factor of 4 from optimality.This uses rate control ρe=0.5γefe, since ρp=1/2.
  • V. PERFORMANCE BOUNDS FOR SPP: The Bernoulli separation policy’s average-age guarantee is at most a factor of 2√7 from optimality, approximately 5.29.The rate control uses λe=ρaveγefe with ρave≈0.53.
  • V. PERFORMANCE BOUNDS FOR SPP: The constant optimality factors for Bernoulli generation are independent of network size.Periodic update generation yields much smaller optimality factors than Bernoulli generation.

B. Periodic Generation of Update Packets

The paper evaluates periodic packet generation and scheduling under heterogeneous channel conditions, showing strong peak-age performance and near-optimal separation-based control for buffered sources.

  • Periodic Generation of Update Packets: The separation principle policy (SPP) jointly uses rate control and scheduling designed separately, with numerical bounds of ≈2.15 for peak age and ≈4.51 for average age.These factors compare SPP with the optimal policy over stationary scheduling policies and rate control.
  • Periodic Generation of Update Packets: For active sources with K = 1, weighted peak and average age increase as θ, the fraction of bad-channel links, increases.The evaluation uses N = 50, γgood = 0.9, and γbad = 0.1 or 0.2.
  • Periodic Generation of Update Packets: With γbad = 0.1, πC achieves minimum peak age, while its average age improves over round robin and uniform stationary scheduling when channel statistics are asymmetric.When channel statistics are more symmetric, round robin can have slightly smaller average age.
  • Periodic Generation of Update Packets: For K = 10, πC remains peak-age optimal and outperforms the other simple scheduling policies in average age.Figure 5 varies θ under the same channel parameters as Figure 4, except that K = 10 links can be activated simultaneously.
  • Periodic Generation of Update Packets: For buffered sources, SPP nearly attains optimal peak age across three network cases, while buffered-node peak age can be about four times the active-source optimum.The gap reflects the cost of being unable to control the MAC-layer queue.
  • Periodic Generation of Update Packets: The paper concludes that stationary scheduling is peak-age optimal for active sources, within a factor of two for average age, while SPP is nearly indistinguishable from optimal numerically.It also derives peak and average age for a discrete-time FIFO G/Ber/1 queue.

APPENDIX

The appendix characterizes peak age through successful-activation intervals and establishes stationary-policy constructions and average-age bounds using activation frequencies and convex optimization.

  • APPENDIX: Peak age is represented by the inter-successful-activation time of each link.For link e, Se(i) = Te(i) − Te(i−1), where Te(i) is the time of the ith successful activation.
  • APPENDIX: A stationary centralized policy can reproduce any feasible link-activation frequency vector by randomizing over interference-free activation sets.The construction uses activation-set frequencies x and the relation f(πst) = Mx = f(π).
  • APPENDIX: Cauchy–Schwarz yields a factor-two upper bound relating average age to peak age for each link and hence for the weighted network objective.The argument assumes finite peak age for the policies under consideration.
  • APPENDIX: Under stationary scheduling, successful activations have geometrically distributed inter-arrival times with rate p, enabling closed-form peak and average age expressions.Here p is the probability that link e is successfully activated in a slot.
  • APPENDIX: The peak-age optimization is reformulated over activation-set frequencies and solved through feasibility and KKT conditions.Positive-frequency activated sets satisfy equalized optimality conditions, while all feasible sets satisfy the corresponding upper bound.

E. Derivation of Peak and Average Age for D/Ber/1 Queue

For periodic packet generation, the appendix specializes the update-arrival distribution to a deterministic inter-arrival time and substitutes its moment generating function into the age analysis.

  • E. Derivation of Peak and Average Age for D/Ber/1 Queue: Periodic generation makes the inter-arrival time equal to D with probability one.The deterministic arrival distribution is P[X = D] = 1 and P[X = k] = 0 for k ≠ D.
  • E. Derivation of Peak and Average Age for D/Ber/1 Queue: The corresponding moment generating function is M_X(t) = e^Dt.Its derivative is M′_X(t) = De^Dt.

APPENDIX

The appendix derives discrete-time FIFO queue age expressions by analyzing geometric arrivals, geometric service, queue occupancy, and recursive system time.

  • APPENDIX: The queue analysis models inter-arrival times and queue occupancy at each update arrival, with service capacity represented by the number of service times fitting between arrivals.This produces a recursion for the queue state.
  • APPENDIX: At steady state, queue occupancy is geometric, and system time is obtained by summing independent geometric service times over the packets present.The resulting system time is also geometrically distributed with a rate determined by the queue state and service rate.
  • APPENDIX: The system-time recursion combines residual prior system time, inter-generation time, and the current packet’s service time.It has the form T_n = max{T_{n−1} − X_n, 0} + S_n.
  • APPENDIX: Independence between system time and inter-generation time permits evaluation of the required expectations for the age formulas.The derivation uses conditional expectations and geometric-distribution properties.
  • APPENDIX: Substitution into the recursive expressions yields the stated discrete-time peak and average age results.The final steps use moment-generating-function identities and steady-state geometric distributions.

H. Derivation of Peak and Average Age for Ber/Ber/1 Queue

The section derives peak and average age expressions for a Bernoulli-generated update process and establishes a common bound through the difference function Δ(μ).

  • Queue analysis: Bernoulli packet generation with rate λ makes the inter-generation time X geometrically distributed.The derivation uses the moment-generating function and its derivatives for X.
  • Model reduction: The service rate at link e is μ_e = γ_e f_e, so the age expressions depend on activation frequency through this product.The analysis consequently reduces the argument to μ_e ∈ (0, 1).
  • Optimization setup: Both F(ρ) and B(μ, ρ) have unique minimizers because they are strictly convex over a bounded domain.The functions H and G satisfy monotonicity, convexity, differentiability, and boundary-growth assumptions.
  • Age bounds: Lemma 1 bounds the difference function as Δ(μ) ≤ H(ρ̂) − H(1), and the peak- and average-age results follow from this bound.The section applies the bound separately to the peak-age and average-age formulations.
  • Peak and average age: For the peak-age and average-age objectives, the relevant minimizing load values are ρ̂_p = 1/2 and ρ̂_ave ≈ 0.53, respectively.The average-age bound uses ρ̂_ave > 1/2 to obtain a bound below 1.

J. Proof of Lemma 1

The proof shows that the difference function Δ(μ) is non-decreasing by characterizing the optimizer ρ(μ) and differentiating the associated first-order condition.

  • Optimizer properties: ρ(μ) is non-decreasing and differentiable in μ.Differentiating the first-order condition and using the monotonicity and strong convexity assumptions yields the result.
  • Boundary behavior: The optimizer satisfies lim_{μ→0} ρ(μ) = ρ̂, ρ(1) = 1, and ρ̂ ≤ ρ(μ) ≤ 1.Continuity and the strict decrease of H establish the endpoint behavior.
  • Optimizer characterization: The optimizer ρ(μ) is defined as arg min over ρ of H(ρ) + (1 − μ)G(ρ).The objective varies linearly with μ, while assumptions A1–A4 support differentiability of the optimizer.
  • Monotonicity argument: The proof reduces Lemma 1 to showing that Δ(μ) is non-decreasing.It establishes this by showing that the first derivative of Δ is non-negative.
  • Conclusion: These properties provide the ingredients for the upper bound on Δ(μ).The proof then uses the monotonicity of Δ to obtain the stated bound.

K. Proof of Theorem 6

Theorem 6 is proved by comparing buffered-source age with the active-source case and applying the stationary policy’s objective bounds for peak and average age.

  • Peak age: The stationary policy π_C minimizes the peak-age objective after the derived expression is matched to the objective in (18).Its link activation frequencies are then used in the subsequent bound.
  • Peak age: Substituting the stationary policy’s activation frequencies and using the normalization of activation probabilities yields the peak-age result.The average-age proof follows the same line of argument.
  • Peak age: The peak-age proof begins by lower-bounding buffered-source peak age with the minimum peak age in the active-source case.The comparison holds because fresh information is generated at the beginning of every slot for active sources.
  • Average age: The average-age proof likewise lower-bounds buffered-source age by the active-source minimum because fresh packets are available in every slot.Corollary 1 and the stated upper bound are then applied to obtain the result.
Loading 1803.06467v2…