PaperlayerView exact revision on arXiv

Source-linked AI summary

Age of Information: An Introduction and Survey

Roy D. Yates, Yin Sun, D. Richard Brown, Sanjit K. Kaul, Eytan Modiano, Sennur Ulukus

arXiv:2007.08564v1cs.ITcs.NI

TL;DR

Cyberphysical systems need timely status updates despite limited resources, motivating metrics and analysis methods for information age. This survey synthesizes AoI models and optimization results across queues, networks, wireless systems, estimation, control, and applications, emphasizing system-matched updating and processing of novel information.

  • Problem

    Cyberphysical systems require timely status updates, but limited resources make freshness a constrained design objective.

  • Method

    The survey develops and synthesizes AoI metrics, analytical methods, and optimization results across queueing, networking, wireless, estimation, control, and cyberphysical applications.

  • Results

    The survey reports that updating should match the handling system, while systems should process new updates and avoid sufficiently non-novel ones.

  • Takeaways & Limitations

    Age-based optimization applies across network layers and system components, including sources, service facilities, base stations, uplinks, and edge-cloud processing.

Abstract

from arXiv · show

We summarize recent contributions in the broad area of age of information (AoI). In particular, we describe the current state of the art in the design and optimization of low-latency cyberphysical systems and applications in which sources send time-stamped status updates to interested recipients. These applications desire status updates at the recipients to be as timely as possible; however, this is typically constrained by limited system resources. We describe AoI timeliness metrics and present general methods of AoI evaluation analysis that are applicable to a wide variety of sources and systems. Starting from elementary single-server queues, we apply these AoI methods to a range of increasingly complex systems, including energy harvesting sensors transmitting over noisy channels, parallel server systems, queueing networks, and various single-hop and multi-hop wireless networks. We also explore how update age is related to MMSE methods of sampling, estimation and control of stochastic processes. The paper concludes with a review of efforts to employ age optimization in cyberphysical applications.

I. INTRODUCTION

AoI measures the timeliness of a monitor’s freshest received status update in end-to-end updating systems. The survey develops metrics and analysis methods, beginning with queueing models and extending to networks and application-oriented settings.

  • I. INTRODUCTION: Low-latency applications send time-stamped status updates from sources through networks to monitors that need timely knowledge of remote processes.Examples include vehicular point clouds, labeled video, anomaly detection, and remote surgery.
  • I. INTRODUCTION: Timely updating differs from maximizing utilization or minimizing delivery delay because sending updates too quickly can backlog stale packets.AoI optimization balances update generation and service congestion.
  • I. INTRODUCTION: AoI defines the age of a freshest received update with timestamp u at time t as Δ(t) = t − u.Fresh updates have current timestamp t and age zero.
  • I. INTRODUCTION: The survey organizes AoI analysis around age metrics, single-server queues, queueing networks, multi-source scheduling, and broader wireless systems.It focuses on contributions that followed early single-source, single-server queue analyses.
  • I. INTRODUCTION: In a canonical network, an input monitor resets its age to zero when fresh updates arrive, while the destination resets to each delivered update’s age and otherwise grows at unit rate.These dynamics produce sawtooth age processes at monitors.
  • I. INTRODUCTION: Time-average age analysis decomposes the area under the sawtooth process, but exact evaluation can be difficult because interarrival and system times tend to be negatively correlated.This correlation complicates evaluating E[T_nY_n].

B. Peak Age

Peak age summarizes the maxima reached by an AoI process and can be easier to evaluate than time-average age. The survey also presents SHS as a systematic framework for deriving stationary age moments.

  • B. Peak Age: Peak age is introduced as an alternate, generally more tractable metric because average-age analysis requires evaluating E[TY].PAoI avoids this computation under mild ergodicity assumptions.
  • B. Peak Age: For single-server queues, each age peak decomposes as A_n = Y_n + T_n, so PAoI equals E[Y] + E[T].Here Y is the interarrival time between delivered updates and T is the delivered packet’s system time.
  • B. Peak Age: The sequence of system-time and peak-age pairs is sufficient to reconstruct the AoI process, making age peaks a fundamental characterization.This follows from the relationship between inter-departure, peak, and system times.
  • B. Peak Age: SHS represents network operation with a discrete Markov state and a real-valued age vector whose components evolve continuously and reset on transitions.Transition-specific reset maps produce jumps in the continuous state.
  • B. Peak Age: For finite-state systems, ergodicity and suitable nonnegative balance conditions yield convergence of expected age vectors or stationary age moments.The framework provides theorem-based conditions for limiting averages.

D. Nonlinear Age Functions

AoI need not map linearly to application degradation, so the survey uses nonlinear age penalties and utilities. These functions connect information age to estimation, channel freshness, and update models.

  • D. Nonlinear Age Functions: Stable Gaussian LTI systems can have estimation error that saturates with age, whereas unstable systems can have error that increases exponentially with age.Thus the same AoI may have different application-level consequences depending on system dynamics.
  • D. Nonlinear Age Functions: A non-decreasing penalty p(Δ(t)) models increasing dissatisfaction with stale information, while a non-increasing utility u(Δ(t)) models decreasing freshness.The functions can be selected according to the source and application.
  • D. Nonlinear Age Functions: For stationary sources, the magnitude of the auto-correlation function can serve as an age utility that decreases as AoI grows.In stationary ergodic Gauss-Markov block-fading channels, channel aging affects both autocorrelation and data rate.
  • D. Nonlinear Age Functions: Mean-squared estimation error is an age penalty when sampling times are independent of a Markov source, but not necessarily when sampling uses causal source knowledge.The same independence boundary also appears in state-estimation formulations.

Mutual Information based Freshness Metrics:

The survey extends freshness beyond elapsed age by relating received information to mutual information, uncertainty, and nonlinear update effects. These measures require explicit assumptions about source dynamics and sampling.

  • Mutual Information based Freshness Metrics:: Mutual information I(X_t; W_t) measures how much delivered samples W_t reveal about the current source value X_t.It is high when received samples are informative and low when they are obsolete.
  • Mutual Information based Freshness Metrics:: For a stationary Markov source with source-independent sampling, mutual information is a non-negative, non-increasing function of AoI.The received information preserved for inference declines as age grows.
  • Mutual Information based Freshness Metrics:: If sampling times depend causally on the source, mutual information and conditional entropy are not necessarily functions of AoI alone.The timing information itself may then contribute to freshness.
  • Mutual Information based Freshness Metrics:: Hard updates reduce age instantaneously after service, whereas soft updates begin taking effect during delivery and may produce exponential or linear decay.Soft-update models represent information arriving in pieces with varying importance and relevance.
  • Mutual Information based Freshness Metrics:: Age penalty functionals aggregate dissatisfaction over an age process using non-decreasing penalties, but peak age and peak-age penalty are not age penalty functionals.This distinction separates functional measures from metrics based on individual peaks or threshold events.

III. AGE IN ELEMENTARY QUEUES

The survey analyzes age in elementary queues, showing how arrival processes, service variability, queue disciplines, and packet management shape freshness. Across FCFS systems, age is minimized at an intermediate load, while preemption and blocking can improve high-load behavior under specific service assumptions.

  • Queue models: Elementary queue models include M/M/1, M/D/1, and D/M/1 systems, plus variants with preemption or blocked arrivals.The survey uses these models to examine how arrival rates, queue disciplines, and packet-management schemes influence age.
  • FCFS queues: ρ∗≈0.53 minimizes average age in the FCFS M/M/1 queue for fixed service rate, leaving the server idle approximately 47% of the time.The optimum satisfies ρ^4 −2ρ^3 + ρ^2 −2ρ + 1 = 0.
  • FCFS queues: For FCFS queues, deterministic arrivals or service outperform M/M/1, with D/M/1 better than M/D/1 at each offered load.At low load, interarrival randomness dominates; at high load, deterministic arrivals or service reduce the average queue length.
  • FCFS queues: Each FCFS queue has a unique age-minimizing offered load because update frequency must be balanced against congestion.The survey contrasts this objective with throughput maximization, which favors load near one, and delay minimization, which favors low load.
  • Packet management: At high loads, M/M/1/2∗, M/M/1/1, and M/M/1∗ can have average age that decreases with offered load through packet management.For M/M/1∗, bombarding the server lets a fresh update enter the waiting room just before each service completion, approaching the 2/µ lower bound as λ →∞.
  • Preemption: Preemption always helps with memoryless service, but this conclusion does not hold generally; deterministic-service preemptive queues can behave differently.D/M/1∗ age decreases monotonically with load, whereas M/D/1∗ is minimized at ρ = 1 and diverges for ρ > 1.

B. Zero-wait updates

The survey derives age lower bounds using zero-wait updates that arrive when the preceding update departs. It also describes blocking and packet-management behavior, including a tight deterministic-service bound and challenges in multi-source stochastic-service analysis.

  • Packet management: Blocking prevents M/M/1/2 age from diverging at high load, but its age is minimized at ρ = 1.427 with ∆ = 2.61 before increasing.At large ρ, the queue admits its next update too quickly.
  • Zero-wait updates: A queue-observing generator that sends each update when the previous one departs produces an age lower bound for independent stochastic update generation.Each delivered update is as fresh as possible because it has zero waiting time.
  • Zero-wait updates: In the zero-wait system, update interarrival time equals the preceding service time, while each update’s system time equals its own service time.The construction uses i.i.d. service times and establishes the moment relationships needed for the age calculation.
  • Lower bounds: For memoryless service with E[S] = 1/µ, the zero-wait construction yields the minimum average age.The survey presents this as the minimum achievable age for the stated service model.
  • Lower bounds: For any service-time distribution with E[S] = 1/µ, nonnegative service-time variance produces a general age lower bound.The bound follows from E[S^2] ≥ (E[S])^2 and is tight when service times are deterministic.
  • Multiple sources: AoI analysis becomes challenging for multiple sources with stochastic service times, although prior work studies Poisson sources, heterogeneous users, and corrected FCFS results.The survey notes relatively few contributions for the stochastic-service setting and reviews several multi-source queue analyses.

IV. AGE IN QUEUEING NETWORKS

The survey extends AoI analysis from single-server queues to parallel-server and queueing-network settings, where congestion, out-of-order delivery, and scheduling determine freshness. It also summarizes policies that achieve optimal or near-optimal age under stated service and buffering assumptions.

  • Parallel-server systems: Parallel-server systems introduce out-of-order delivery because a packet in service can become obsolete when a newer packet is delivered.The survey considers one queue with buffer size B feeding c servers, including packet dropping or replacement when a finite buffer is full.
  • Parallel-server systems: M/M/2 service can reduce AoI by approximately a factor of 2 relative to M/M/1, despite congestion and obsolete updates remaining in service.The M/M/2 system has infinite buffers, so waiting updates still create congestion-related age penalties.
  • Scheduling policies: P-LGFS minimizes the age process and every non-decreasing age functional under i.i.d. exponential service times for arbitrary generation and arrival times, buffer sizes, and server counts.The result includes time-average age and time-average age penalty, and permits out-of-order arrivals.
  • AoI analysis tools: Age of Served Information Ξ(t) lower-bounds monitor age ∆(t) because it measures freshness at service entrance rather than at server exit.The packet timing relation is S_i ≤ C_i ≤ V_i ≤ D_i.
  • Scheduling policies: For i.i.d. NBU service times with B ≥1, NP-LGFS is within an additive gap E[S] of the optimal expected time-average age.The gap is invariant to packet generation and arrival times, the number of servers, and the buffer size.

C. Scheduling for Multiple Hops and Multiple Sources

The survey extends age-optimal scheduling from single flows to multi-hop networks and multiple sources. These results cover exponential and NBU service times, age penalties, multiple servers, and heterogeneous flow priorities.

  • Multiple hops: For a single packet flow in multi-hop networks, P-LGFS is optimal with i.i.d. exponential service times and NP-LGFS is near age-optimal with i.i.d. NBU service times.The exponential-service result applies to age processes at all network nodes.
  • Multiple sources: P-MAF-LGFS minimizes stochastic age penalties for synchronized multiple flows with i.i.d. exponential service times and one server.The penalty is time-dependent, symmetric, and non-decreasing in the vector of flow ages.
  • Multiple sources: With i.i.d. NBU service times and multiple servers, NP-MASIF-LGFS is within a small additive gap of the optimum for total time-average age.The policy serves the last-generated packet from the flow with the maximum age of served information.
  • Multiple sources: Lex-age-optimal scheduling first minimizes AoI for high-priority flows, then minimizes the metrics of lower-priority flows among policies optimal for the higher-priority flows.This framework addresses multiple flows with diverse priority levels.

V. RESOURCE CONSTRAINED UPDATING

Resource-constrained updating studies how sensors should schedule transmissions when energy availability limits updates. Across battery settings, the survey emphasizes spreading updates over time rather than transmitting greedily whenever energy is available.

  • Motivation: Energy harvesting sensors cannot transmit continuously because exhausting stored energy can leave monitors with overly stale status information.The central design question is how to manage harvested energy for timely updates.
  • Scope: The survey covers generate-at-will policies across finite and infinite batteries, noiseless and erasure channels, and settings with or without servers.It also reviews feedback, reinforcement learning, wireless energy transfer, and related extensions.
  • Infinite batteries: For an infinite battery, best-effort uniform updating is optimal and achieves ∆∗(∞) = 1/2 under the normalized noiseless model.The model uses unit-rate Poisson energy arrivals, unit energy per update, and negligible transmission time.
  • Finite batteries: For finite batteries, optimal policies have threshold structure: transmit only when AoI exceeds an energy-dependent threshold, with thresholds decreasing as available energy increases.The finite-battery results include renewal-policy characterizations.

C. Energy Harvesting Erasure Channels

AoI optimization over erasure channels must account for missing feedback, retransmissions, and finite energy storage. The survey reports optimal uniform, renewal, threshold, and threshold-greedy structures under different feedback and battery conditions.

  • System model: The erasure-channel model uses independent transmission erasures with probability q and distinguishes no-feedback from instantaneous perfect-feedback operation.The optimization chooses feasible transmission times to minimize long-term average AoI as a function of battery size.
  • Infinite batteries: With infinite battery and erasures, BU is optimal without feedback, while BUR is optimal with perfect feedback.Both optimality results are obtained by evaluating a lower bound and showing the corresponding policy achieves it.
  • Unit battery: For B = 1, the optimal policy is a renewal policy whose actual inter-update times are i.i.d. under both feedback conditions.The single-unit battery is completely depleted by one update.
  • No feedback: Without feedback, the B = 1 optimum is an erasure-dependent threshold policy whose threshold is non-increasing in q.Higher erasure probability makes the sensor more eager to send new updates.
  • Perfect feedback: With perfect feedback, optimal threshold-greedy policies use a threshold for the first attempt and greedy retransmissions after failure.The two-stage structure is characterized as an equilibrium within the considered policy class.
  • Takeaway: The survey’s broader takeaway is that update spacing should be adapted to energy availability and energy causality rather than sending greedily whenever energy is available.Best-effort policies apply for infinite batteries, while threshold policies apply for finite batteries.

D. Energy Harvesting Channels with Servers

The survey reviews AoI optimization for energy-harvesting sources with server delays, unreliable updates, and resource constraints. Results include policies that exploit service timing, characterize energy–packet interactions, and adapt transmission or sampling decisions.

  • Stochastic service delays: Energy-harvesting sources with stochastic service delays can time updates relative to service completions, including policies that may deliberately leave the server idle.A policy was shown to outperform “best effort” and “fixed delay” policies.
  • Energy and packet arrivals: The average age can be invariant to exchanging normalized energy and packet arrival rates, despite their different server-handling mechanisms.The normalized rates are β = η/µ and ρ = λ/µ.
  • Preemption: Preemption decreases average age in energy-rich regimes but increases it in energy-starved regimes because preempted updates waste energy.The benefit depends on whether the server typically has a full battery.
  • Losses and retransmissions: TARQ retransmission can achieve lower average AoI than classical ARQ when updates may be erased without feedback.TARQ retransmits the current status until a time threshold is exceeded or a new update becomes available.
  • Resource-constrained control: Transmission policies trade energy expenditure against delivery reliability, while sleep–wake and wireless-energy-transfer systems incorporate battery, channel, and age states.MDP-based policies select sensors, transmission modes, or whether to harvest energy or transmit.
  • Generate-at-will sampling: 1.85 seconds is the time-average age for ε = 0.5, compared with 2 seconds for zero-wait sampling in the example.The zero-wait policy can be far from optimal for rapidly growing nonlinear age penalties or heavy-tailed service times.

B. Sampling for AoI Minimization

The survey develops threshold-based sampling for minimizing time-average age and compares it with remote-estimation objectives. Optimal policies wait until delivery and an age or estimation-error threshold is reached, with exact threshold solutions for several signal models.

  • Sampling for AoI Minimization: The optimal age-minimizing sampler generates sample i+1 after sample i is delivered and expected future age penalty reaches threshold β.The threshold β equals the optimal objective value and has a unique root computable by numerical methods.
  • Sampling for AoI Minimization: β is exactly the optimal value of the time-average age-penalty problem.The threshold policy is optimal for non-decreasing penalty functions with i.i.d. service times of finite positive mean.
  • Sampling for AoI Minimization: Energy-harvesting age-optimal samplers use a threshold β(E(t)) that decreases with battery level, so sampling becomes more frequent as energy increases.For a full battery, β(B) equals the optimal objective value.
  • Sampling and Remote Estimation: Continuous-time sampling and estimation form challenging continuous-state MDPs, but exact optimal solutions are available for Wiener and Ornstein–Uhlenbeck signals.These models correspond respectively to a Wiener process and the continuous-time analogue of an AR(1) process.
  • Sampling and Remote Estimation: Remote estimation replaces the age threshold with an instantaneous estimation-error threshold determined by the signal model and service-time distribution.The next sample is generated after delivery when |εX(t)| reaches the threshold v(β).
  • Sampling and Remote Estimation: The sampling policy and MMSE estimator are jointly optimal for a class of continuous-time Markov signals.Threshold-type samplers remain optimal in several discrete-time joint sampling-and-estimation settings.

AoI and Signal-agnostic Sampling:

Signal-agnostic sampling restricts sampling times to be independent of the observed signal, converting remote-estimation design into an age-penalty problem. Under Markov signals and i.i.d. service times, the resulting optimal sampler has a threshold structure.

  • AoI and Signal-agnostic Sampling: Signal-agnostic policies choose sampling times without causal knowledge of the signal, making those times independent of the signal process.They form a subset Πagnostic of the broader policy class Π.
  • AoI and Signal-agnostic Sampling: Restricting policies to Πagnostic turns the remote-estimation problem into an instance of the age-penalty problem solved by Theorem 9.The resulting design can therefore use the same threshold-policy framework.
  • AoI and Signal-agnostic Sampling: For continuous-time homogeneous Markov chains with i.i.d. finite-mean service times, the optimal signal-agnostic sampler is threshold-based.The delivery time is Di(β) = Si(β) + Yi, with β determined by the corresponding root equation.
  • AoI and Signal-agnostic Sampling: Signal-aware sampling thresholds instantaneous estimation error, whereas signal-agnostic sampling thresholds expected estimation error at delivery.Both threshold parameters equal their respective optimal objective values.
  • AoI and Signal-agnostic Sampling: The framework extends to discrete-time systems, maximum sampling-rate constraints, two-way delays, multiple sources, and packet-erasure channels.Related work also applies age-based sampler design to discrete-time feedback control systems.
  • Wireless extensions: AoI research in wireless settings spans erasure channels, interference-constrained scheduling, decentralized access, broadcast networks, and multi-source multi-hop systems.Some scheduling problems under physical interference constraints were shown to be NP-hard, while other work develops distributed or age-based policies.

B. Updates Through Erasure Channels

AoI studies wireless updating under unreliable channels, contention, energy limits, and scheduling constraints, emphasizing policies that balance freshness, transmission success, and resource use.

  • Coding redundancy improves successful delivery probability but increases transmission time, creating an age trade-off between reliability and duration.Finite redundancy sends a fixed number of coded symbols, whereas infinite incremental redundancy continues until enough symbols are successfully received.
  • ARQ and HARQ studies optimize codeword length or transmission policies to minimize age under transmission-budget constraints.
  • ALOHA can produce worse age than scheduled access over unreliable channels, while load thinning can reduce average AoI relative to typical slotted ALOHA.
  • RR-ONE, which retains only the latest packet and enforces round robin access, is asymptotically optimal among decentralized non-interfering policies.
  • Maximum Age First is optimal for symmetric links but can perform arbitrarily poorly when link success probabilities or weights differ.
  • Max-Weight and Whittle’s Index policies achieve 2-optimal performance across network configurations and are close to optimal in simulations, generally outperforming MAF and randomized policies.

E. General Wireless Networks

General wireless-network AoI optimization models feasible activation sets, unreliable links, and source generation, then extends the framework to buffering, channel-state information, multihop networks, and freshness-sensitive applications.

  • Wireless interference restricts simultaneous transmissions to feasible activation sets, while independent time-varying channel errors determine whether scheduled links succeed.
  • For active sources, randomized scheduling assigns probabilities to feasible activation sets and determines each link’s activation frequency.
  • A convex optimization over activation-set probabilities minimizes average and peak age among stationary randomized policies.
  • Although the optimization is convex, its variable dimension can grow exponentially with the network size; single-hop interference permits polynomial-time solution through the matching polytope.
  • With Bernoulli packet arrivals, AoI optimization decouples into link scheduling using the active-source policy and a separate packet-generation-rate optimization.
  • The survey also covers channel-state-aware transmission, multihop topology and contention, and applications involving freshness, adversarial interference, and strategic power selection.

B. Age and Learning

AoI research increasingly uses learning and age-aware application models to optimize updating, mobility, caching, computation, and control, while leaving broad practical and multidimensional problems open.

  • Model-free learning methods optimize update scheduling across error-prone channels, sensor networks, ad hoc networks, and UAV information-collection tasks.
  • Age-aware computation assigns older work to servers less likely to straggle, while model staleness control applies Q-learning to edge machine-learning models.
  • Learning algorithms include SARSA for unknown channel statistics, A3C for sensor selection, deep Q-learning for transmit power, and deep reinforcement learning for UAV trajectories and scheduling.
  • AoI is combined with popularity, request history, service latency, and cache management to control freshness in caching systems.
  • The survey concludes that AoI optimization spans network layers and system components, with updating processes matched to service systems and preference for new information over stale updates.
  • Open problems include multidimensional correlated or non-Markovian signals, age-distortion trade-offs, age-optimal network services, and practical deployment across application domains.
Loading 2007.08564v1…