PaperlayerView exact revision on arXiv

Source-linked AI summary

The Age of Information in Networks: Moments, Distributions, and Sampling

Roy D. Yates

arXiv:1806.03487v4cs.IT

TL;DR

The paper asks how to analyze timeliness and stationary age distributions in networked status-update systems. It uses stochastic hybrid systems to derive moment and MGF equations, then applies them to preemptive line and status sampling networks. The resulting age distributions are sums of independent exponential or renewal-process age variables under the corresponding network models.

  • Problem

    The paper addresses the challenge of analyzing time-average AoI and stationary age distributions in networks carrying status updates.

  • Method

    The paper models finite-state network dynamics and age vectors as stochastic hybrid systems, deriving linear differential equations for age moments and MGFs.

  • Results

    For preemptive memoryless line networks, node age has the distribution of a sum of independent exponential variables; for renewal-based sampling networks, it is a sum of independent renewal-process age variables.

  • Takeaways & Limitations

    The MGF framework provides explicit stationary age-distribution results for multihop routes and supports a status-sampling interpretation of linear networks.

Abstract

from arXiv · show

A source provides status updates to monitors through a network with state defined by a continuous-time finite Markov chain. An age of information (AoI) metric is used to characterize timeliness by the vector of ages tracked by the monitors. Based on a stochastic hybrid systems (SHS) approach, first order linear differential equations are derived for the temporal evolution of both the moments and the moment generating function (MGF) of the age vector components. It is shown that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the stationary MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal point process. For each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.

I. INTRODUCTION

The paper develops SHS-based tools for analyzing AoI moments and stationary distributions in networked status-update systems. It applies these tools to preemptive line networks and generalizes the resulting structure to status sampling networks.

  • AoI measures the timeliness of the freshest update received by a monitor as the elapsed time since its timestamp.
  • The paper addresses the difficulty of analyzing time-average AoI by deriving SHS equations for higher-order moments and the MGF of an age vector.
  • The analysis generalizes beyond memoryless service to status sampling networks, where neighboring nodes receive samples through renewal point processes.
  • For line networks with preemptive memoryless servers, the stationary age at a node is distributed as a sum of independent exponential random variables.
  • In a status sampling line, each node’s stationary age is the independent sum of the preceding node’s stationary age and the renewal-process age associated with sampling.

D. Notation

The paper represents AoI networks as stochastic hybrid systems combining a finite-state continuous-time Markov chain with continuously evolving age variables. Age assignment matrices encode how transitions reset monitor ages.

  • Between discrete transitions, every age component grows at unit rate, producing sawtooth age processes.
  • At a transition, a binary age assignment matrix maps the pre-transition age vector to the reset vector.
  • A reset can copy a fresher monitor age or set an age to zero when a fresh update is observed.
  • An AoI SHS uses a finite-state continuous-time Markov chain with transitions occurring at specified rates.
  • The bookkeeping formulation tracks conditional age moments and MGF quantities by partitioning expectations according to the discrete Markov state.
  • The resulting differential-equation framework underlies the paper’s stationary moment, MGF, line-network, and sampling-network analyses.

III. STATIONARY MOMENTS AND THE STATIONARY MGF

Under ergodicity, fixed points of the SHS differential equations characterize stationary age moments and the stationary MGF. A non-negative first-moment fixed point is sufficient for convergence of all higher moments and a positive MGF region.

  • Ergodicity of the discrete-state Markov chain is required for stationary age moments to be meaningful.
  • The moment equations may be unstable for some reset-map collections, so stability depends on the specific age assignments.
  • Fixed points are obtained by setting the time derivatives in the moment and MGF equations to zero and solving the resulting systems.
  • A non-negative fixed point for the first-moment equations guarantees convergence of all higher-order age moments.
  • The same condition yields a region around zero in which the stationary MGF exists and converges.

A. Example: The M/M/1/1 queue with abandonment

This example studies an M/M/1/1 queue with abandonment using a two-state Markov model. The stated objective is to determine the limiting MGF of the destination age.

  • Updates arrive at rate λ, receive service at rate µ, and are abandoned while in service at rate α.
  • When the server is occupied, new arrivals are blocked and cleared, leaving queue occupancy as the two-state discrete process.
  • The example’s analysis seeks the limiting destination-age MGF E[e^sx2] as time tends to infinity.
  • The stationary Markov-state probabilities are first obtained from the balance equations and normalization condition.

0 A1 + ¯v(0) 0 ˆA1

The M/M/1/1 queue with abandonment is represented by an SHS Markov chain whose transitions and reset maps are specified in Table I. The resulting equations are simplified using β = µ + α and γ = λ + µ + α.

  • The SHS Markov chain includes self-transitions in which the discrete state is unchanged but the continuous age state is reset.
  • Table I lists the SHS transitions for the Markov chain shown in Figure 2.The transition set contains links l ∈ {1, 2, 3}.
  • β = µ + α and γ = λ + µ + α provide compact notation for simplifying the queue’s age equations.

B. Matrix Formulation of the Age Moments

The matrix formulation recasts the age-moment differential equations and their fixed points in vector form. Under ergodicity and a non-negative stationary first moment, all higher-order moments converge.

  • B. Matrix Formulation of the Age Moments: The matrix representation expresses the age-moment equations and fixed points using long row vectors.This formulation supports computational treatment of systems with larger state spaces.
  • B. Matrix Formulation of the Age Moments: Equations (33) and (34) restate the probability and age balance relations in matrix form, enabling direct characterization of fixed points.
  • B. Matrix Formulation of the Age Moments: A non-negative solution for the stationary first moment implies that R − D has eigenvalues with strictly negative real parts.Consequently, the first-moment differential equation is stable and converges to its stationary value.
  • B. Matrix Formulation of the Age Moments: If q(t) is ergodic with positive stationary distribution and the first-moment fixed point is non-negative, every age moment converges to its stationary value.The result applies to the stationary mth moment for each m.
  • B. Matrix Formulation of the Age Moments: The matrix moment equations provide an explicit closed-form characterization of stationary higher-order moments.Theorem 2 is the matrix version of the earlier age-moment theorem.

C. Matrix Formulation of the Age MGF

The MGF formulation gives a matrix differential equation and establishes stationary convergence near zero under a stationary first-moment condition. It is then applied to preemptive line networks, whose ages admit a sampling-based interpretation.

  • C. Matrix Formulation of the Age MGF: The MGF analysis constructs a matrix version of the age-distribution result from the SHS equations.
  • C. Matrix Formulation of the Age MGF: Under stationarity and a non-negative stationary first moment, some s0 > 0 exists such that v^(s)(t) converges for all s < s0.The condition follows because R − D + sI retains eigenvalues with strictly negative real parts in that region.
  • C. Matrix Formulation of the Age MGF: Successive derivatives of the stationary MGF recover the stationary higher-order age moments.
  • C. Matrix Formulation of the Age MGF: The first stationary age moment guarantees existence and convergence of the stationary MGF vector, making it pivotal for the distributional analysis.
  • IV. PREEMPTIVE LINE NETWORKS: The preemptive line network uses rate µi M/M/1/1 servers, immediately forwarding departures and discarding preempted updates.Although nodes have no queues, losses, aged arrivals, correlations, and survivor bias make the delivery process complex.
  • IV. PREEMPTIVE LINE NETWORKS: Fake updates keep each node perpetually busy and yield an equivalent interpretation in which nodes forward their current updates as Poisson processes.This removes the need to track each node’s idle/busy state.

A. Age Moments on the Line Network

For the n-node line network, the SHS framework derives stationary age moments and an MGF, revealing distributions built from independent exponential terms and motivating a renewal-sampling interpretation.

  • Line-network SHS model: The SHS transition model resets node 1 to age zero on fresh-update arrivals and resets node l+1 to node l’s age when updates traverse a link.All other age components remain unchanged during these transitions.
  • Stationary age moments: Theorem 4 provides the stationary mth-moment age vector for the n-node line network.The result follows by constructing the transition matrices and applying the fixed-point moment equations.
  • Stationary age MGF: The stationary MGF of the line-network age vector is obtained by applying the SHS MGF theorem with the line-network transition representation.Because the discrete state space is Q = {0}, the MGF calculation uses the corresponding reduced form.
  • Distributional interpretation: At node k, the stationary age has the distribution of a sum of independent exponential random variables associated with the preceding links.This distributional result generalizes an earlier average-age sum result.
  • Sampling interpretation: The line-network result is interpreted as status sampling, where each node samples its predecessor through a Poisson process and renewal sampling generalizes this structure.Under sampling, the downstream age is the independent sum of the upstream stationary age and the renewal-process age.

A. Status Sampling Renewal Processes

The paper models status sampling as equilibrium renewal processes and shows that downstream stationary ages are sums of independent renewal-process age variables. Simulations illustrate the resulting convolution distributions and their Gaussian approximation for longer lines.

  • Renewal-process characterization: When inter-sampling times are exponential, the renewal-process age is exponential, recovering the line-network result for preemptive memoryless servers.The status-sampling network generalizes the memoryless-server line network but is not itself a queueing network with defined customer service times.
  • Renewal-process characterization: Theorem 6 shows that sampling a stationary age process with an independent equilibrium renewal process produces a downstream age identical in distribution to the sum of the two ages.The result requires stationarity of the sampled process and independence from the renewal process controlling sampling.
  • Renewal-process characterization: For a line network, the stationary age at node k is distributed as the sum of the source age and the stationary renewal-process ages accumulated along preceding nodes.The source node’s age is always zero, and stationarity propagates from each node to the next.
  • Simulation and distributions: For uniform inter-update times, each node’s age density is an iterated convolution of the renewal-age density, and simulations match the predicted PDFs for the first two nodes.The sample construction forwards age samples successively along the line to generate downstream age processes.
  • Simulation and distributions: Under uniform inter-update times, the mean and variance grow linearly with node position as E[Xk] = kb/3 and Var[Xk] = kb^2/18.For larger n, the simulated distributions are compared with Gaussian PDFs having the same mean and variance; the approximation is reasonable even for small n.

VI. STOCHASTIC HYBRID SYSTEMS FOR AOI ANALYSIS

The paper embeds AoI tracking in a general stochastic hybrid systems framework with discrete Markov states and continuous age states. This formulation supports differential-equation analysis of age evolution while retaining linear reset structure.

  • SHS formulation: The AoI-tracking model is formulated as a special case of a general stochastic hybrid system.The generalization uses established SHS notation and enables direct application of Dynkin’s formula.
  • SHS formulation: An SHS combines a finite discrete state q(t), continuous state x(t), independent Brownian-motion inputs, mappings f and g, and a set of transitions.The continuous state is an n-dimensional age vector, while the discrete state evolves through transitions with specified intensities and reset maps.
  • SHS dynamics: Each transition has an intensity that determines its occurrence probability and may cause a discontinuous reset of the continuous state.The counting process for each transition records occurrences over time.
  • SHS dynamics: For AoI tracking, the continuous state increases at unit rate in every discrete state, while transitions follow fixed rates and linear reset maps.The discrete component is a continuous-time finite-state Markov chain, and the reset map has the form x′ = xA_l.

B. SHS test functions

The SHS framework uses time-invariant test functions to derive differential equations for age moments and the MGF. These equations support evaluation of stationary age statistics when their fixed points exist.

  • Extended generator: The extended generator maps each test function to its expected rate of change, yielding a differential equation for its expectation.For each test function, the resulting equation describes the temporal evolution of the corresponding performance measure.
  • Test-function construction: Time-invariant test functions are applied to age processes to derive differential equations for their expected values.The test functions are organized by age-process moments and MGF-related quantities, with expectations defined as weighted conditional expectations.
  • Resulting equations: The derived first-order linear differential equations describe the temporal evolution of age moments and the MGF for finite-state continuous-time Markov network models.The framework is applied to an age-process vector tracked across network states.
  • Convergence: A non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher-order moments and a region of convergence for the stationary MGF vector.This establishes the fixed-point condition as the central stability criterion for the hierarchy of age statistics.
  • Distributional characterization: For line networks with preemptive memoryless servers, the stationary age distribution is represented through the MGF and corresponds to a sum of independent renewal-process age variables.In the memoryless case, these variables are exponentially distributed; the observation extends to equilibrium renewal processes with continuous inter-update distributions.

APPENDIX

The appendix derives the SHS moment equations by evaluating the extended generator on selected test functions and assembling the resulting state-indexed equations. It then establishes stability and applies the results to network-specific claims.

  • Lemma 1: The proof of Lemma 1 evaluates the extended generator on the selected test functions and gathers the resulting equations into vector form.The construction produces the differential-equation blocks stated in Lemma 1.
  • Lemma 2: The proof of Lemma 2 uses non-negative reset matrices and a dominant eigenvalue argument to show that the relevant system matrix has stable eigenvalues.The argument introduces σ so that σI − D is strictly positive diagonal, then bounds the dominant eigenvalue.
  • Theorem 2: Theorem 2 is proved by induction, beginning with first-moment convergence and extending the stability conclusion to higher-order moment equations.The base case follows from Lemma 2, while subsequent cases use the induction hypothesis and the established matrix stability.
  • Theorem 4: Theorem 4 constructs network transition matrices and uses the resulting matrix expressions to establish its claim.The appendix derives the matrices from the network description and associated shorthand parameters.
  • Theorem 5: Theorem 5 derives the matrices R and D − R for the line network and obtains the claim from the resulting parameter definitions.The proof uses the transition matrices and the relation ˆR = diag[µ0, 0, · · ·, 0].
Loading 1806.03487v4…