PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Status Sampling and Updating for Minimizing Age of Information in the Internet of Things

Bo Zhou, Walid Saad

arXiv:1807.04356v2cs.ITcs.NI

TL;DR

The paper addresses keeping destination information fresh while minimizing average AoI under an average energy constraint. It formulates the problem using a constrained Markov decision process, derives threshold-type single-device policies, and develops a distributed learning policy for multiple devices.

  • Problem

    The paper seeks to minimize average AoI at destination nodes while keeping information fresh under an average energy constraint for IoT devices.

  • Method

    The approach formulates the problem as a constrained Markov decision process, uses structure-aware policy iteration, and develops semi-distributed per-device online learning.

  • Results

    The single-device optimal sampling and updating policy is threshold type, while the proposed learning algorithm for multiple devices converges almost surely to the proposed suboptimal policy.

  • Takeaways & Limitations

    The threshold structure exposes a tradeoff between average AoI and sampling and updating costs, while channel gain and scattering affect AoI performance.

Abstract

from arXiv · show

The effective operation of time-critical Internet of things (IoT) applications requires real-time reporting of fresh status information of underlying physical processes. In this paper, a real-time IoT monitoring system is considered, in which the IoT devices sample a physical process with a sampling cost and send the status packet to a given destination with an updating cost. This joint status sampling and updating process is designed to minimize the average age of information (AoI) at the destination node under an average energy cost constraint at each device. This is formulated as an infinite horizon average cost constrained Markov decision process (CMDP) and transformed into an unconstrained MDP using a Lagrangian method. For the single IoT device case, the optimal policy for the CMDP is shown to be a randomized mixture of two deterministic policies for the unconstrained MDP, which is of threshold type. Then, a structure-aware optimal algorithm to obtain the optimal policy of the CMDP is proposed and the impact of the wireless channel dynamics is studied while demonstrating that channels having a larger mean channel gain and less scattering can achieve better AoI performance. For the case of multiple IoT devices, a low-complexity distributed suboptimal policy is proposed with the updating control at the destination and the sampling control at each device. Then, an online learning algorithm is developed to obtain this policy, which can be implemented at each IoT device and requires only the local knowledge and small signaling from the destination. The proposed learning algorithm is shown to converge almost surely to the suboptimal policy. Simulation results show the structural properties of the optimal policy for the single IoT device case; and show that the proposed policy for multiple IoT devices outperforms a zero-wait baseline policy, with average AoI reductions reaching up to 33%.

I. INTRODUCTION

The paper studies joint status sampling and updating for IoT monitoring, where both operations consume energy and must minimize destination AoI. It develops structural and learning-based policies for single- and multiple-device systems.

  • Motivation: Existing AoI studies generally assume negligible status-packet generation costs, unlike newer IoT devices performing on-device feature extraction and classification.Sophisticated sensing can incur sampling energy, while richer packets can also require greater transmission energy and delay.
  • Problem formulation: The open problem is to jointly control sampling and packet updating to minimize destination AoI under per-device average energy constraints.The objective accounts for energy used both to generate and transmit status packets.
  • Single-device contributions: For one device, the paper formulates an average-cost CMDP, applies a Lagrangian transformation, and derives threshold-based unconstrained policies.The CMDP optimum is a randomized mixture of two deterministic unconstrained-MDP policies.
  • Single-device contributions: The single-device analysis identifies a tradeoff between destination AoI and sampling or updating costs, while larger mean channel gain and less scattering yield better AoI performance.The paper also proposes a structure-aware optimal algorithm for obtaining the constrained policy.
  • Multiple-device contributions: For multiple devices, a low-complexity semi-distributed policy approximates global Q-factors with per-device factors and uses local online learning with destination signaling.The learning algorithm converges almost surely to the proposed suboptimal policy.
  • Numerical findings: Average AoI reductions reach up to 33% against a zero-wait baseline in the multiple-device simulations.The paper also reports non-decreasing optimal sampling and updating thresholds with their respective costs.

II. OPTIMAL SAMPLING AND UPDATING CONTROL FOR A SINGLE IOT DEVICE

The single-device model represents sampling and transmission as energy-consuming controls over bounded device and destination AoI states. It explains why immediate resampling may waste energy and motivates joint AoI-aware control.

  • System model: The device monitors a physical process, generates status packets through sampling, and transmits currently available packets through a wireless channel.Sampling and updating are distinct device operations.
  • System model: Unlike simple temperature or humidity sensing, the model allows feature extraction and pre-classification using machine-learning and neural-network tools.The sampling process therefore represents computational work, not only sensor reading.
  • Model scope: The analytical framework can extend to packet generation or transmission requiring more than one slot by modifying the AoI dynamics.The stated model otherwise assumes one-slot sampling and time-slotted operation.
  • Control actions: Sampling generates a packet at cost C_s, takes one slot, and replaces the older locally stored packet.The update action sends only the packet currently available at the device, with transmission cost depending on channel state.
  • Age dynamics: The system uses bounded device and destination AoI states, with sampling resetting device AoI to one and otherwise increasing it by one.Destination AoI similarly resets according to the device packet age after a successful update and otherwise increases by one.
  • Control objective: Immediate resampling after an update may waste energy because a newly generated packet can become stale when poor channels delay its transmission.This motivates jointly controlling sampling and updating to minimize destination AoI under an energy constraint.

B. CMDP Formulation and Optimality Equation

The paper formulates joint sampling and updating as an infinite-horizon average-cost CMDP, then uses a Lagrangian transformation and Bellman analysis to characterize optimal policies. The CMDP optimum is obtained through a randomized mixture of two deterministic stationary policies for suitable Lagrange multipliers.

  • 1) CMDP Formulation:: A stationary policy maps the system AoI and channel states (A, h) to a device sampling and updating action w.
  • 1) CMDP Formulation:: Under i.i.d. channel states and the stated AoI dynamics, the process {(A(t), h(t))} is a controlled Markov chain, with attention restricted to stationary unichain policies.
  • 1) CMDP Formulation:: The objective is to minimize average destination AoI under an average energy-cost constraint at the device.
  • 1) CMDP Formulation:: The resulting problem is an infinite-horizon average-cost CMDP, which is challenging because of the curse of dimensionality.
  • 2) Optimality Equation:: The CMDP is transformed into a parameterized unconstrained MDP by introducing a Lagrangian cost and minimizing its average value for a given λ.
  • 2) Optimality Equation:: The optimal CMDP policy is a randomized mixture of two deterministic stationary policies associated with Lagrange multipliers.
  • 2) Optimality Equation:: For each λ, an optimal policy is obtained by solving a Bellman equation involving the optimal value θλ and a state value function V(A, h; λ).
  • 2) Optimality Equation:: The Bellman equation generally has no closed-form solution, and conventional value or policy iteration can be computationally impractical for IoT systems.

C. Structural Analysis and Algorithm Design

The paper derives structural properties of the single-device optimal policy and uses them to develop a structure-aware policy-iteration algorithm. The resulting threshold structure separates idle, sampling, and updating decisions according to the two AoI states and channel state.

  • Algorithm Design: The authors propose a structure-aware optimal algorithm based on monotone policy iteration to obtain the CMDP policy.
  • Structural Analysis: The value function V(A, h; λ) is non-decreasing in both local and destination AoI states for every channel state.
  • Structural Analysis: The action-difference function has monotonicity properties in A_l and A_r that support threshold-based comparisons among sampling and updating actions.
  • Structural Analysis: The optimal policy partitions AoI states into action regions defined through the sets Φ_w and Ψ_w, where one action dominates the alternatives.
  • Optimality Properties: When the AoI state lies in the idle region A0(h; λ), the device neither samples the physical process nor sends a status update.
  • Optimality Properties: Updating actions are threshold-based in destination AoI A_r, while sampling is threshold-based in device AoI A_l.
  • Optimality Properties: The policy structure reflects a tradeoff between destination AoI and sampling and updating costs, making immediate transmission after sampling potentially detrimental under the energy constraint.
  • Limitations: The coupled AoI states and special AoI dynamics make the threshold structures difficult to prove and prevent complete characterization of some dependencies and thresholds.

2) Algorithm Design:

The paper exploits structural properties of the single-device optimal policy to design a structure-aware policy iteration algorithm, then analyzes how channel distributions affect optimal AoI.

  • Structure-aware optimal algorithm: The optimal action structure allows minimization over selected states rather than all states, reducing policy-computation effort.The reduction uses monotonicity and stochastic-dominance properties, without requiring exact threshold values.
  • Structure-aware optimal algorithm: The structure-aware policy iteration algorithm is monotone and converges to the optimal policy.It determines some optimal actions immediately when Algorithm 1 conditions are satisfied.
  • Structure-aware optimal algorithm: Each iteration saves O(|M|(|A||H|)2) computation, with savings growing exponentially with the state space.The algorithm avoids unnecessary minimizations by exploiting structural relations among states.
  • Structure-aware optimal algorithm: The CMDP policy is obtained by combining policies associated with two nearby Lagrange multipliers and selecting a randomization parameter.The multipliers are set around the optimal multiplier λ∗ using perturbation η.
  • Effects of wireless channel dynamics: First-order stochastic dominance of one channel over another implies a smaller optimal average AoI under the same resource constraint.Thus, larger mean channel gain is associated with smaller optimal AoI.
  • Effects of wireless channel dynamics: With equal mean gain, less channel scattering can achieve smaller optimal AoI under the same resource constraint when the updating cost satisfies the corollary conditions.The stated conditions include updating cost decreasing and convex in channel state.

III. SEMI-DISTRIBUTED SUBOPTIMAL SAMPLING AND UPDATING CONTROL FOR MULTIPLE IOT DEVICES

For multiple IoT devices, the exponentially growing joint state space and collision constraint make centralized optimal control difficult, motivating a low-complexity deterministic suboptimal policy.

  • Motivation and formulation: The multiple-device state space grows exponentially with the number of devices, hindering structural analysis and low-complexity optimal-algorithm design.Different devices also cannot update concurrently because collisions would prevent successful transmission.
  • Motivation and formulation: The objective remains minimizing destination average AoI subject to an average energy-cost constraint for every IoT device.Sampling and updating costs are jointly represented in each device’s energy cost.
  • Lagrangian formulation: The constrained problem is transformed into an unconstrained MDP through a vector of Lagrange multipliers and Q-factor optimization.For a fixed multiplier vector, the optimal action depends on the system Q-factor and the multipliers.
  • Limitations of centralized control: The centralized optimal Q-factor suffers from dimensionality and requires destination knowledge of all AoI and channel states each slot.The resulting randomized stationary policy may also be unsuitable for practical implementation.
  • Proposed policy: The paper therefore introduces a semi-distributed deterministic suboptimal policy for jointly controlling sampling and updating.Existing restless multi-armed-bandit solutions are not applicable because the problem jointly controls two action types.

B. Algorithm Design

The proposed policy approximates the joint Q-factor by per-device Q-factors, assigning updating coordination to the destination and reducing complexity from exponential to linear in device count.

  • Per-device decomposition: The joint Q-factor is approximated by the sum of per-device Q-factors, enabling a semi-distributed sampling and updating policy.Each per-device Q-factor is defined through its own fixed-point equation.
  • Semi-distributed control: The destination determines updating actions using the per-device Q-factors, while each device selects its sampling action from local AoI and channel observations.Devices report their two updating-action Q-factor values to the destination.
  • Complexity: The proposed policy decreases complexity from exponential with K to linear with K.This reduction follows from replacing the joint Q-factor calculation with K per-device calculations.
  • Complexity: The proposed suboptimal policy requires per-device computations rather than solving the full joint Q-factor problem.Its per-device construction avoids the exponential state-space computation required by centralized optimization.

2) Online Stochastic Learning and Convergence Analysis:

An online semi-distributed learning algorithm jointly updates per-device Q-factors and Lagrange multipliers using local observations and destination signaling, with almost-sure convergence to the proposed policy.

  • Limitations: The approximation error of the feature-based linear Q-factor architecture remains an open problem, so evaluation is limited to numerical comparisons.This is an author-stated scope limitation for the CMDP setting.
  • Online stochastic learning: Each device learns its per-device Q-factor and Lagrange multiplier using locally observed AoI and channel states plus the destination’s updating action.The destination exchanges only the updating control needed by each device.
  • Online stochastic learning: The algorithm updates Q-factors and Lagrange multipliers concurrently on two different timescales.The Q-factor is treated as nearly equilibrated during the multiplier update.
  • Convergence analysis: The per-device Q-factor converges almost surely to the solution of its fixed-point equation under any initial per-device Q-factor.This is established for the specified step-size conditions.
  • Convergence analysis: The Lagrange-multiplier vector converges almost surely to a value whose policy satisfies the energy-cost constraints.The convergence is stated as limt→∞λt = λ∞ a.s.
  • Convergence analysis: The combined algorithm converges with probability one to the per-device fixed-point solution and a constraint-satisfying sampling and updating policy.The resulting implementation requires local knowledge and simple signaling from the destination.

IV. SIMULATION RESULTS AND ANALYSIS

Simulations examine how sampling and updating costs shape the optimal policy for a single IoT device. The policy uses threshold rules over channel state and destination age to exploit favorable transmission opportunities.

  • Simulation setup: The simulations evaluate the structural effects of sampling and updating costs on the optimal sampling and updating policy.The setup uses specified channel states and probabilities, updating cost Cu(h) = Cu/h with Cu = 0.2, sampling cost Cs = 0.2, and age upper limits of 10.
  • Cost effects: Sampling becomes less likely as the sampling cost Cs increases.The relationship between the sampling threshold and Cs is non-decreasing, indicating reluctance to sample when sampling is expensive.
  • Cost effects: High updating costs make the IoT device less willing to send a status packet to the destination.The simulations examine the relationship between the updating threshold and the updating cost Cu for fixed channel state and Lagrangian parameter.
  • Policy structure: Actions (0, 1) and (1, 1) are scheduled according to thresholds in the channel state h.The two updating actions are threshold-based with respect to h, as illustrated by the optimal-policy structure.
  • Policy structure: When the channel state is poor, sending the status packet is inefficient because it incurs a high updating cost.The policy therefore exploits the random wireless channel by seizing good transmission opportunities.
  • Policy structure: Actions (0, 1) and (1, 1) do not concurrently appear for a given Al because their decisions are threshold-based in Ar and h.This threshold structure is observed near the upper-right corners of the policy plots.

B. Case of Multiple IoT Devices

For multiple IoT devices, the paper develops a low-complexity semi-distributed policy and online learning algorithm for joint sampling and updating. The policy converges almost surely and improves average AoI over zero-wait baselines, with reductions reaching 33%.

  • Performance evaluation: 20% reduction of average AoI is achieved over the zero-wait baseline with similar energy costs.The comparison uses average per-device AoI and average per-device energy cost.
  • Performance evaluation: 33% is the largest reported average AoI gain over the baseline as the maximum energy cost varies.For both policies, increasing the number of devices raises average per-device AoI and lowers average energy cost because transmission opportunities decrease.
  • Policy design: The semi-distributed policy approximates optimal Q-factors using per-device Q-factors learned from local AoI and channel states.Updating control is handled at the destination, while sampling control is handled at each device.
  • Learning and convergence: The proposed semi-distributed learning algorithm converges almost surely to the proposed suboptimal policy.The algorithm can be implemented using local observations and signaling from the destination.

APPENDIX

The appendix establishes convergence and structural properties of the optimal policy using value iteration, induction, and comparisons of state-action costs across AoI states and channel conditions.

  • Value iteration: The proof of Lemma 3 uses value iteration and induction to establish monotonicity of the value function across AoI states.The induction starts from V_0(A, h) = 0 and passes from iteration m to m + 1.
  • Value iteration: Value iteration generates value functions that converge to V(A, h) under any initialization.The convergence is stated for all states (A, h) in the state space.
  • Policy structure: The appendix relates differences in state-action costs to value-function comparisons and proves their monotonicity across AoI states.These relations are then used to complete the remaining structural properties of the policy.
  • Policy structure: Theorem 1 derives threshold-type policy properties by showing that action dominance persists across ordered AoI states.The proof separately verifies properties for actions including (0, 0) and (0, 1).

D. Proof of Theorem 2

The proof of Theorem 2 compares value functions under stochastically ordered channels using induction and value iteration, then connects the result to the channel-dependent policy properties.

  • Channel comparison: For channels I and J with hI first-order stochastically dominating hJ, the proof compares their value functions through induction and value iteration.The comparison is established first for finite iterations and then extended using convergence.
  • Channel comparison: The induction step uses the channel ordering, monotonicity of C_u(h), and the value-iteration recursion to preserve the comparison.The proof then invokes the limiting relation for the value functions.
  • MDP conditions: Under the stated unichain condition, the induced process has a single recurrent class and possibly transient states.This condition supports the average-cost MDP analysis used in the appendix.
  • Proof scope: The detailed proof of Lemma 6 is omitted due to page limitations.The appendix explicitly identifies the omission rather than presenting the full derivation.
  • Learning convergence: The separated timescales yield an ODE for the Lagrange-multiplier update whose limit satisfies the average-cost constraint.The limiting policy under (Q∞, λ∞) has zero limiting Lagrangian gradient and satisfies constraint (26b).
  • MDP conditions: The proof relies on standard unichain and weak-accessibility results for state-independent average cost and convergence of policy iteration.The cited results require finite state and action sets for finite-iteration policy-iteration convergence.
Loading 1807.04356v2…