PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling for Data Freshness Optimization: Non-linear Age Functions

Yin Sun, Benjamin Cyr

arXiv:1812.07241v4eess.SYcs.ITeess.SP

TL;DR

The paper addresses how to sample data for freshness when linear age does not capture source dynamics and application value. It models the design as a constrained MDP and shows that optimal policies have computable threshold structures across broad settings. Numerically, these policies can outperform zero-wait and uniform sampling.

  • Problem

    Linear age metrics do not fully capture source dynamics and application-specific data value, while efficient policies for non-linear age metrics remain largely unexplored.

  • Method

    The paper formulates freshness-aware sampling as a constrained MDP and characterizes deterministic or randomized threshold policies computed using bisection search.

  • Results

    Optimal sampling policies can be much better than zero-wait sampling and classic uniform sampling across the studied freshness metrics and system settings.

  • Takeaways & Limitations

    The threshold-policy characterization provides a structured, computationally tractable solution for freshness optimization under broad age metrics and sampling constraints.

Abstract

from arXiv · show

In this paper, we study how to take samples at a data source for improving the freshness of received data samples at a remote receiver. We use non-linear functions of the age of information to measure data freshness, and provide a survey of non-linear age functions and their applications. The sampler design problem is studied to optimize these data freshness metrics, even when there is a sampling rate constraint. This sampling problem is formulated as a constrained Markov decision process (MDP) with a possibly uncountable state space. We present a complete characterization of the optimal solution to this MDP: The optimal sampling policy is a deterministic or randomized threshold policy, where the threshold and the randomization probabilities are characterized based on the optimal objective value of the MDP and the sampling rate constraint. The optimal sampling policy can be computed by bisection search, and the curse of dimensionality is circumvented. These age optimality results hold for (i) general data freshness metrics represented by monotonic functions of the age of information, (ii) general service time distributions of the queueing server, (iii) both continuoustime and discrete-time sampling problems, and (iv) sampling problems both with and without the sampling rate constraint. Numerical results suggest that the optimal sampling policies can be much better than zero-wait sampling and the classic uniform sampling.

I. INTRODUCTION

The paper argues that age alone cannot capture application-specific freshness, motivating non-linear age metrics and sampling policies optimized through a constrained MDP. It characterizes optimal deterministic or randomized threshold policies across broad system settings and reports improvements over zero-wait and uniform sampling.

  • Motivation: Age alone cannot fully describe freshness because sources vary at different rates and applications value fresh data differently.The paper motivates metrics that account for both source dynamics and application context.
  • Freshness metrics: Non-linear utility and penalty functions of age represent application-specific freshness and staleness metrics.The functions may include utility, temporal autocorrelation, estimation error, or other performance measures, and penalties may be non-convex or discontinuous.
  • Problem formulation: The sampling problem is formulated as a constrained Markov decision process with a possibly uncountable state space.The formulation supports sampling-rate constraints while optimizing monotonic age metrics.
  • Optimal policies: Optimal sampling policies are deterministic or randomized threshold policies, with thresholds computed by bisection search and randomization selected to satisfy rate constraints.The solution exploits MDP structure to circumvent the curse of dimensionality.
  • Scope: The results cover monotonic age metrics, general queueing-server service distributions, continuous- and discrete-time sampling, and settings with or without rate constraints.The system model uses a single-server FIFO queue with i.i.d. service times and supports both continuous and discrete time.
  • Results: Optimal sampling policies can be much better than zero-wait and classic uniform sampling, although zero-wait is not necessarily age-optimal.Prior work on age also includes queueing, scheduling, energy, coding, wireless, and game-theoretic settings.

1) Auto-correlation Function of the Source:

The paper surveys how source autocorrelation and related information measures can represent freshness as age-dependent utility or penalty functions. For Markov sources with source-independent sampling, mutual information decreases as sample age increases, while source-dependent sampling can break this age-only characterization.

  • Auto-correlation Function of the Source:: Source autocorrelation can serve as an age utility because it typically decreases as the sample age grows.For stationary sources, the absolute autocorrelation is non-negative and non-increasing with age.
  • Estimation Error of Real-time Source Value:: Mean-squared estimation error can be represented as an age penalty when sampling times are independent of the observed Markov source.The corresponding penalty depends on the source and system assumptions.
  • Information based Data Freshness Metric:: Mutual information measures how much received samples reveal about the current source value, with larger information indicating fresher data.Values near the source entropy indicate substantial information, whereas values near zero indicate obsolescence.
  • Information based Data Freshness Metric:: For stationary Markov sources and source-independent sampling, mutual information is a non-negative, non-increasing function of age.The result follows from the Markov structure and applies to continuous-time and discrete-time chains.
  • Information based Data Freshness Metric:: If sampling times depend causally on the source, mutual information need not be a function of age alone.The paper identifies exploiting timing information under source-dependent sampling as a future research direction.
  • Information based Data Freshness Metric:: For a Gauss-Markov source with a ∈(−1, 1), mutual information is positive and decreases with age.At zero age, the Gaussian source entropy is infinite, so the mutual information is also infinite.

C. Formulation of Optimal Sampling Problems

The paper formulates continuous- and discrete-time freshness optimization as constrained MDPs balancing age penalty against sampling cost. It characterizes the resulting optimal policies and addresses the analytical difficulty caused by continuous or high-dimensional state spaces.

  • C. Formulation of Optimal Sampling Problems: The sampling policy is restricted to causal policies based on channel idle/busy history, with inter-sampling times forming a regenerative process.This structure supports the long-run average objectives used in the formulation.
  • C. Formulation of Optimal Sampling Problems: The paper assumes source-independent sampling times, policy-independent queue service times, and finite expected age penalties after service.These assumptions define the setting in which the optimization problems are analyzed.
  • C. Formulation of Optimal Sampling Problems: The objective is to minimize average age penalty or maximize average age utility subject to an average sampling-rate constraint.The continuous-time and discrete-time cases are formulated separately.
  • C. Formulation of Optimal Sampling Problems: Sampling-rate constraints capture a tradeoff between data staleness and the cost of generating updates.The paper notes that update cost increases with average sampling rate.
  • C. Formulation of Optimal Sampling Problems: The resulting problems are constrained MDPs with either uncountable or countable state spaces.The continuous-time problem has an uncountable state space, whereas the discrete-time problem has a countable one.
  • C. Formulation of Optimal Sampling Problems: Because the curse of dimensionality makes analytical solutions rare, the paper seeks explicit, arbitrarily accurate solutions for these MDPs.The formulation motivates the structural characterization developed in the main results.

A. Continuous-time Sampling without Rate Constraint

Without a sampling-rate constraint, the paper characterizes optimal continuous-time sampling through threshold rules tied to the optimal age penalty. It also identifies when zero-wait sampling is or is not optimal and provides bisection-based computation.

  • A. Continuous-time Sampling without Rate Constraint: When fmax = ∞, an optimal policy is parameterized by β under non-decreasing penalties and i.i.d. service times with finite positive mean.Theorem 1 provides the continuous-time solution under these assumptions.
  • A. Continuous-time Sampling without Rate Constraint: β equals the optimal objective value of the continuous-time problem.Thus, the threshold parameter directly represents the minimum achievable time-average expected age penalty.
  • A. Continuous-time Sampling without Rate Constraint: The next sample is generated at the earliest time after delivery of the previous sample when expected future age penalty reaches threshold β.The rule combines queue delivery with a penalty-threshold condition.
  • A. Continuous-time Sampling without Rate Constraint: The threshold equation has a unique solution that can be found by bisection, with expectations evaluated through Monte Carlo simulation or importance sampling.The paper presents this as an efficient numerical procedure.
  • A. Continuous-time Sampling without Rate Constraint: Zero-wait sampling is throughput- and delay-optimal but is not necessarily age-optimal for non-linear age penalties.The paper develops necessary and sufficient optimality conditions for zero-wait sampling.
  • A. Continuous-time Sampling without Rate Constraint: If service time is constant, zero-wait sampling is optimal under the stated assumptions.This is the complementary case given by Corollary 2(a).
  • A. Continuous-time Sampling without Rate Constraint: If service times have essential infimum zero and p(·) is strictly increasing, zero-wait sampling is not optimal.This applies to several common service-time distributions, including exponential, Erlang, and hyperexponential distributions.

B. Continuous-time Sampling with Rate Constraint

With a sampling-rate constraint, the continuous-time problem admits optimal deterministic or randomized threshold policies. The threshold is computed from the objective and constraint, with deterministic policies arising under a monotonicity condition.

  • Continuous-time rate-constrained sampling: Theorem 2 characterizes the rate-constrained optimum as either a deterministic or randomized threshold policy.The deterministic case applies when the threshold bounds coincide; otherwise, randomization can satisfy the sampling-rate constraint.
  • Continuous-time rate-constrained sampling: The threshold parameter β is determined by the policy equations, while randomization probabilities are selected to meet the sampling-rate constraint.The policy uses β together with the bounds and mixing probability specified in the theorem.
  • Computation: A bisection algorithm computes the unique β, after which the sampling time and randomization probability are obtained from the threshold formulas.Reducing numerical tolerance or improving expectation estimates can increase solution accuracy.
  • Deterministic specialization: If E[p(t + Y_i+1)] is strictly increasing, the optimal policy reduces almost surely to a deterministic threshold policy.This condition holds for a broad class of strictly increasing age penalties or sufficiently smooth service-time distributions.
  • Relation to prior work: The continuous-time result corrects a prior theorem by requiring strict increase of E[p(t + Y_i+1)] and provides a simpler specialized solution.The paper identifies the missing condition in the earlier result and notes that the linear penalty is a special case.

C. Discrete-time Sampling

The discrete-time problem has threshold-policy solutions with integer sampling times, both without and with sampling-rate constraints. Unlike continuous time, randomization may remain necessary even when the expected penalty is strictly increasing.

  • Discrete-time threshold policies: Theorems 3 and 4 give optimal discrete-time threshold policies without and with sampling-rate constraints, respectively.The service times are i.i.d., the age penalty is non-decreasing, and the expected service time is finite.
  • Without a rate constraint: β equals the optimal objective value in the unconstrained discrete-time problem.The theorem identifies β as the root of the discrete-time optimality equation.
  • Zero-wait sampling: The zero-wait policy is optimal without a rate constraint if and only if the condition stated in Corollary 4 holds.This characterization applies under non-decreasing penalties and i.i.d. service times with finite positive mean.
  • Continuous- versus discrete-time sampling: Discrete-time threshold bounds are restricted to integers, so randomized threshold policies may be needed to satisfy the sampling-rate constraint.This can occur even when E[p(t + Y_i+1)] is strictly increasing, marking a key difference from continuous-time sampling.
  • Mutual-information example: The discrete-time formulation also yields an optimal policy for maximizing time-average expected mutual information in the stated Markov-chain example.The optimal value is represented by β through the specialization p(∆t) = −u(∆t).

E. Alternative Expressions of the Threshold Sampling Policy

The threshold policy can be rewritten as a water-filling rule for post-delivery waiting time. This form shows that waiting decreases with service time and becomes zero beyond a threshold.

  • Threshold and water-filling forms: The threshold policy can be expressed directly in terms of age and rewritten using a water level w(β).The resulting waiting time is measured from sample delivery to the next sample generation.
  • Threshold and water-filling forms: The post-delivery waiting time decreases linearly with service time until it reaches zero.The water-filling expression is Zi(β) = Di(β) + max{w(β) − Yi, 0} in the displayed policy representation.
  • Relation to age minimization: The water-filling solution is age-optimal for the special linear penalty p(∆t) = ∆t and comes close to optimal age performance in symmetric multi-source simulations.The latter observation is reported as a simulation finding rather than a general optimality result.
  • No sampling during service: It is suboptimal to sample before the previous sample is delivered, so the optimal queue remains empty.A queued sample becomes stale while waiting for transmission, whereas sampling when the server becomes idle yields a smaller sample-path age process.
  • Policy representation: The admissible policy class therefore generates each sample after delivery, with Zi representing the waiting time before the next generation.The policy is equivalently represented by the sequence of waiting times under the empty-queue restriction.

B. Reformulation of Problem (55)

The paper reformulates the fractional sampling objective through a parameterized MDP and Lagrangian duality. A sufficient-statistic reduction then decomposes the problem into convex per-sample optimizations whose solutions yield threshold policies.

  • Parameterized MDP reformulation: The fractional objective is transformed into a parameterized MDP whose optimum can be located through the sign of h(c).The Dinkelbach-style relation states that the original optimum is above, equal to, or below c according to whether h(c) is positive, zero, or negative.
  • Lagrangian duality: Although the MDP has a continuous state space, the Lagrangian dual approach establishes strong duality with no duality gap.The dual problem is used to solve the parameterized MDP at the optimal objective value.
  • Per-sample decomposition: A sufficient-statistic argument reduces the dual problem to independent per-sample optimization problems.For i.i.d. service times, the current service time Y_i is sufficient for determining the optimal waiting time Z_i.
  • Convex per-sample optimization: Each per-sample optimization is convex because the relevant functions of waiting time are convex under a non-decreasing age penalty.The optimal waiting times form an interval bounded by zmin and zmax.
  • Threshold characterization: The resulting optimal policy selects Zi from [zmin(Yi, α), zmax(Yi, α)], producing the threshold structure used by the sampling solution.At the optimal objective parameter, the duality gap remains zero and a lower-bound endpoint provides an optimal solution in the stated theorem.

E. Zero Duality Gap and Optimal Solution to (57)

The analysis establishes zero duality gap and characterizes optimal solutions for the constrained optimization problem. The resulting threshold can be computed using the MDP objective and Lagrangian dual variable.

  • Zero duality gap: Theorem 5 establishes zero duality gap under non-decreasing penalties, finite expected penalty, and i.i.d. service times with finite positive mean.It also provides an optimal solution under the stated condition involving E[Yi + zmin(Yi, 0)].
  • Optimal solution: An optimal solution is given by Zi = zmin(Yi, 0) when E[Yi + zmin(Yi, 0)] > 1.
  • Optimal solution: Otherwise, the sequence (Z1, Z2, . . .) provides an optimal solution to both optimization formulations.
  • Proof relationship: Theorem 2 follows from Theorem 5, while the proof uses a geometric multiplier to establish the zero duality gap.
  • Threshold computation: The threshold β equals the MDP optimum objective value plus the optimal Lagrangian dual variable, enabling bisection-search computation.The paper states that this structure also circumvents the curse of dimensionality.

F. Proofs of Other Continuous-time Sampling Results

The section connects continuous-time results to discrete-time analogues and reports numerical comparisons among uniform, zero-wait, and optimal sampling. The experiments show substantial advantages for the optimal policy, especially with rapidly growing penalties or highly random service times.

  • Continuous-time results: Theorem 1 is a special case of Theorem 2, with the optimal objective value characterized using the i.i.d. service-time assumption.The uniqueness of the relevant root is also noted.
  • Discrete-time results: Discrete-time proofs parallel the continuous-time proofs, replacing the continuous convex optimization problem with an integer optimization problem.The discrete-time optimal-solution set is characterized through zmin and zmax.
  • Numerical setup: The numerical comparison includes uniform sampling, zero-wait sampling, and the theorem-based optimal policy.Zero-wait sampling is infeasible when fmax < 1/E[Yi].
  • Mutual-information experiments: For the Gauss-Markov source, the experiments vary source correlation through a and sampling capacity through fmax, using service times equal to 1 or 21 with probability 0.5.The setting has E[Yi] = 11, so zero-wait sampling is infeasible when fmax < 1/11.
  • Penalty experiments: For exponential age penalties with discretized log-normal service times, zero-wait sampling is far from optimal when the penalty grows quickly or service times are highly random.These regimes correspond to relatively large α or highly variable service times.
  • Conclusion: The conclusion reports that optimal policies are easy to compute, structurally simple, and can be much better than zero-wait and classic uniform sampling.

APPENDIX A PROOF OF LEMMA 1

The appendix proves the mutual-information age representation and derives optimality conditions using convexity, threshold bounds, and geometric multipliers. These steps establish the structure needed for an optimal policy and zero duality gap.

  • Mutual-information representation: For a Markov source with source-independent sampling, the freshest delivered sample is a sufficient statistic for estimating the current source value.The resulting mutual information depends on the age of information.
  • Convex optimization: Convexity of h(z) permits one-sided derivative conditions that characterize optimal solutions to the continuous optimization problem.The proof uses monotone convergence to interchange limits and integration.
  • Threshold characterization: For non-decreasing penalties, optimal z values satisfy lower and upper threshold conditions defined by zmin(yi, α) and zmax(yi, α).The expected penalty is below the threshold for smaller t and above it for larger t.
  • Duality argument: A policy and multiplier satisfying the stated conditions establish optimality and zero duality gap through the geometric-multiplier argument.The construction uses the set Γ(α⋆) of optimal solutions and separates cases for selecting α⋆.
  • Multiplier construction: The threshold bounds increase with α, allowing the expected bounds to grow without limit and supporting the multiplier construction.

APPENDIX D PROOF OF COROLLARY 1

The appendix characterizes when zero-wait sampling is optimal using a penalty threshold condition. It also shows that constant service times guarantee optimality, whereas strictly increasing penalties with service-time variability can make zero-wait suboptimal.

  • Characterization: Zero-wait sampling can be written as the threshold policy in (17) when E[p(ess inf Yi + Yi+1)] ≥ β.
  • Characterization: Zero-wait sampling is optimal if and only if the root defining β satisfies the corresponding penalty-threshold condition.The proof establishes both directions by substituting the condition into the threshold policy and the root equation.
  • Constant service times: When service time Yi is constant almost surely, zero-wait sampling is optimal for every non-decreasing penalty function.
  • Variable service times: If ess inf Yi = 0 and p is strictly increasing, zero-wait sampling is not optimal.The proof uses a positive-probability interval on which the penalty exceeds p(Yi).
  • Discrete-time extension: The discrete-time proof uses the integer optimization formulation and shows that the interval from zmin(yi, α) through zmax(yi, α) contains all optimal solutions.
Loading 1812.07241v4…