PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing Age of Information with Power Constraints: Multi-user Opportunistic Scheduling in Multi-State Time-Varying Channels

Haoyue Tang, Jintao Wang, Linqi Song, Jian Song

arXiv:1912.05947v4cs.IT

TL;DR

The paper asks how to minimize average AoI when IIoT sensors have power limits, channels vary according to Markov dynamics, and scheduling is bandwidth-constrained. It decomposes the problem into single-sensor CMDPs, solves their threshold policies by linear programming, and builds a truncated policy for the hard constraint. The resulting policy is asymptotically optimal and approaches the AoI lower bound, while exploiting favorable channels for power-limited sensors and timely updating sufficiently powered sensors.

  • Problem

    The paper asks how to minimize average Age of Information for power-constrained IIoT sensors over Markov time-varying channels subject to bandwidth constraints.

  • Method

    The paper relaxes the hard bandwidth constraint, decomposes scheduling into single-sensor CMDPs, solves threshold policies by linear programming, and constructs a truncated policy.

  • Results

    The truncated policy is asymptotically optimal and achieves average AoI close to the lower bound, with nearly 40% average AoI decrease as the number of sensors increases for M = {2, 5}.

  • Takeaways & Limitations

    Small AoI is obtained by scheduling power-limited sensors in good channels and updating sensors with sufficient power in a timely manner.

Abstract

from arXiv · show

This work is motivated by the need of collecting fresh data from power-constrained sensors in the industrial Internet of Things (IIoT) network. A recently proposed metric, the Age of Information (AoI) is adopted to measure data freshness from the perspective of the central controller in the IIoT network. We wonder what is the minimum average AoI the network can achieve and how to design scheduling algorithms to approach it. To answer these questions when the channel states of the network are Markov time-varying and scheduling decisions are restricted to bandwidth constraint, we first decouple the multi-sensor scheduling problem into a single-sensor constrained Markov decision process (CMDP) through relaxation of the hard bandwidth constraint. Next we exploit the threshold structure of the optimal policy for the decoupled single sensor CMDP and obtain the optimum solution through linear programming (LP). Finally, an asymptotically optimal truncated policy that can satisfy the hard bandwidth constraint is built upon the optimal solution to each of the decoupled single-sensor. Our investigation shows that to obtain a small AoI performance: (1) The scheduler exploits good channels to schedule sensors supported by limited power; (2) Sensors equipped with enough transmission power are updated in a timely manner such that the bandwidth constraint can be satisfied.

I. INTRODUCTION

The paper studies minimizing Age of Information in IIoT networks where time-varying wireless channels, sensor power limits, and bandwidth constraints jointly shape scheduling. It develops a CMDP-based decomposition and truncated policy to address this problem.

  • I. INTRODUCTION: The paper targets fresh data collection from power-constrained sensors transmitting over time-varying wireless links in IIoT networks.AoI is used to measure data freshness at the central controller, which supports time-sensitive industrial applications.
  • I. INTRODUCTION: The framework addresses a cross-layer optimization challenge in which channel randomness and power and bandwidth constraints occur across communication layers.The paper motivates joint physical- and data-link-layer design because these constraints and randomness interact in stochastic networks.
  • I. INTRODUCTION: The scheduling problem jointly considers average power consumption, multi-state Markov channels, and a hard per-slot bandwidth constraint.Different transmission power levels are used across channel states, while no more than M sensors can be scheduled in each slot.
  • I. INTRODUCTION: The multi-sensor problem is relaxed and decomposed into single-sensor constrained Markov decision processes, whose optimal policies have a threshold structure and admit linear-programming solutions.The decomposition uses a Lagrange multiplier after relaxing the hard bandwidth constraint.
  • I. INTRODUCTION: A dual-method searches for Lagrange multipliers, and an asymptotically optimal truncated policy is constructed to satisfy the original hard bandwidth constraint.The paper states that the policy is built from the solutions of the decoupled single-sensor problems.

B. Age of Information

The paper measures data freshness with AoI and formulates multi-sensor scheduling under bandwidth and per-sensor average-power constraints. It relaxes the hard bandwidth constraint, decomposes the problem into single-sensor CMDPs, and uses their solutions to construct a truncated policy satisfying the original constraint.

  • B. Age of Information: AoI measures the slots elapsed since the freshest delivered information was generated, with successful generate-at-will updates resetting the age to 1 in the next slot.The network objective is the expected long-run average AoI across sensors.
  • B. Age of Information: The problem seeks a non-anticipated scheduling policy minimizing network-wide average AoI while satisfying each sensor’s average-power constraint and the hard per-slot bandwidth constraint.Scheduling decisions use current and past AoI and channel information rather than future states.
  • B. Age of Information: The hard bandwidth constraint is first relaxed into an average constraint, enabling decomposition into single-sensor power-constrained optimization problems through a Lagrange multiplier.The multiplier acts as a penalty for scheduling more users than allowed by the relaxed constraint.
  • B. Age of Information: The decoupled solutions provide a lower bound for the original problem, while a truncated scheduling policy is proposed to satisfy the hard bandwidth constraint.The truncated policy is built from the solutions of the decoupled single-sensor problems.

B. Constrained Markov Decision Process Formulation

Each decoupled sensor is modeled as a CMDP whose state combines current AoI and channel state. Its binary scheduling action changes AoI evolution, incurs AoI and scheduling costs, and must satisfy an average-power constraint.

  • B. Constrained Markov Decision Process Formulation: The CMDP state is the pair of a sensor’s current AoI x and channel state q, yielding a countably infinite state space.The channel state evolves according to its Markov dynamics.
  • B. Constrained Markov Decision Process Formulation: The two actions are scheduling an update or keeping the sensor idle, distinct from the network-level decision subject to the strict bandwidth constraint.The action s(t)=1 schedules transmission, whereas s(t)=0 leaves the sensor idle.
  • B. Constrained Markov Decision Process Formulation: If idle, AoI increases by one; if scheduled, AoI resets to 1, while the channel state transitions independently according to its Markov process.This transition structure captures both freshness evolution and time-varying channel conditions.
  • B. Constrained Markov Decision Process Formulation: The CMDP minimizes infinite-horizon average AoI and scheduling cost subject to an average-power constraint.The one-step cost includes AoI growth and a scheduling penalty, while transmission consumes state-dependent power.

C. Characterization of the Optimal Policy

The optimal decoupled policy has a threshold structure in AoI for each channel state. Under the power constraint, it can be represented as a mixture of at most two stationary deterministic policies obtained from Lagrangian optimization.

  • C. Characterization of the Optimal Policy: The optimal stationary randomized policy is a mixture of no more than two stationary deterministic policies.This follows from relaxing one average-power constraint and solving the associated Lagrange problem.
  • C. Characterization of the Optimal Policy: For a fixed Lagrange multiplier, the power constraint is incorporated into the objective, producing an unconstrained MDP with an average-cost Bellman equation.The multiplier penalizes power use while preserving the threshold characterization.
  • C. Characterization of the Optimal Policy: For each channel state q, the optimal deterministic policy schedules when AoI x reaches threshold τq and remains idle below that threshold.Thus s*(x,q)=1 for x≥τq and s*(x,q)=0 for x<τq.
  • C. Characterization of the Optimal Policy: The threshold behavior reflects scheduling when information is stale or when the channel state is favorable.The paper describes this as scheduling when x is large or q is small.

D. Probabilistic Scheduling Policy for Single Sensor Case

For the single-sensor problem, the stationary randomized policy is analyzed through state-transition probabilities and a finite-state steady-state representation. Introducing occupation variables converts the optimization into a linear program.

  • D. Probabilistic Scheduling Policy for Single Sensor Case: The stationary randomized policy schedules in state (x,q) with probability ξx,q, and its transition graph tracks AoI increases, resets, and Markov channel changes.Forward transitions occur when the sensor is not scheduled, while scheduled transmissions reset AoI to 1.
  • D. Probabilistic Scheduling Policy for Single Sensor Case: The steady-state distribution is represented over bounded AoI and channel states using a probability-transfer matrix and normalization constraints.The construction uses forward and backward transition matrices for the truncated state space.
  • D. Probabilistic Scheduling Policy for Single Sensor Case: The decoupled power-constrained cost problem is equivalent to a linear program over state probabilities µx,q and scheduled-state probabilities yx,q=µx,qξx,q.The LP includes flow, normalization, probability, and average-power constraints.
  • D. Probabilistic Scheduling Policy for Single Sensor Case: The LP objective combines AoI cost with scheduling penalty, while scheduled transmissions consume channel-state-dependent power.The variables yx,q quantify the probability that the sensor occupies a state and is scheduled there.
  • D. Probabilistic Scheduling Policy for Single Sensor Case: The optimal scheduling probability is nondecreasing in AoI for every channel state and equals one once AoI exceeds the largest threshold.A finite bound Xmax can therefore be chosen so that states above it have zero steady-state probability.

V. MULTI-SENSOR OPPORTUNISTIC SCHEDULING

The relaxed multi-sensor problem is decomposed into single-sensor CMDPs, whose Lagrangian solutions are obtained through LPs and combined to satisfy average bandwidth. A subgradient-based multiplier search and policy randomization produce the relaxed optimum and its AoI lower bound.

  • A. Determination of Lagrange Multiplier: The multiplier W is searched iteratively by subgradient descent until the relaxed bandwidth constraint is satisfied or convergence criteria are met.The update uses the difference between total average scheduling demand and the available bandwidth.
  • A. Determination of Lagrange Multiplier: The multi-sensor scheduling problem is relaxed into decoupled single-sensor CMDPs, and each CMDP is solved through an equivalent LP.The dual function separates across sensors, with average AoI and scheduling probability evaluated for each multiplier.
  • A. Determination of Lagrange Multiplier: The optimum relaxed solution can mix two policies associated with neighboring Lagrange multipliers to achieve the required average bandwidth.The two policies are obtained as one-sided limits around the multiplier satisfying the bandwidth condition, then combined using a mixing coefficient.
  • A. Determination of Lagrange Multiplier: When the initial unconstrained scheduling demand does not exceed available bandwidth, the resulting AoI is the relaxed problem’s minimum and a lower bound for the primal problem.This case requires no further consideration of the relaxed bandwidth constraint.
  • A. Determination of Lagrange Multiplier: The resulting per-sensor scheduling probabilities are computed from current AoI and channel state and implemented through the proposed algorithm.Algorithm 1 initializes and repeatedly solves the sensor LPs while updating the multiplier.

B. Multi-sensor opportunistic scheduling with hard bandwidth constraint

The truncated policy converts the relaxed per-sensor decisions into a feasible hard-bandwidth schedule. It serves all requested sensors when capacity suffices and randomly selects the available number otherwise, with asymptotic optimality as the network grows.

  • B. Multi-sensor opportunistic scheduling with hard bandwidth constraint: The truncated policy satisfies the hard bandwidth constraint by scheduling all requested sensors when their number is at most M and randomly selecting M otherwise.The requested set is formed by sensors whose relaxed policies indicate that they should be scheduled in the current slot.
  • B. Multi-sensor opportunistic scheduling with hard bandwidth constraint: With M/N = θ fixed, the proposed truncated policy is asymptotically optimal for the primal problem with hard bandwidth constraint.The theorem states that its deviation from the optimal scheduling policy decreases at order O(1/√N).

VI. SIMULATIONS

The simulations evaluate the proposed scheduling policy in a four-state Markov channel with identical sensor channel dynamics. Power-budget effects are represented through each sensor’s normalized average power ratio.

  • VI. SIMULATIONS: The simulations use a Q = 4-state Markov channel with a specified state-evolution matrix and steady-state distribution η = [0.2368, 0.2632, 0.2632, 0.2368].All sensors share these channel dynamics, and results are collected over T = 10^6 slots.
  • VI. SIMULATIONS: Power consumption is measured by ρ_n = E_n/E_RR, where smaller ρ_n denotes a smaller average power budget for sensor n.The reference E_RR is the minimum power consumption associated with the no-packet-loss round-robin setting.

A. Average AoI performance

The proposed truncated policy approaches the lower-bound average AoI under fixed bandwidth and improves freshness as sensor count grows. It allocates opportunities to power-limited sensors while timely updating sensors with sufficient power to satisfy bandwidth constraints.

  • Nearly 40% average AoI decrease is achieved for M = {2, 5} with N = 50 sensors under the proposed truncated policy.The comparison uses fixed available bandwidth as the number of sensors increases.
  • The proposed truncated scheduling achieves average AoI close to the lower bound as the number of sensors increases with fixed M = {2, 5}.
  • The difference between the proposed strategy and the lower bound decreases with N in the asymptotic average AoI evaluation.Simulation results verify the asymptotic performance.
  • For N = 8 and M = 2, the proposed algorithm reduces AoI by about 40% for sensors with very limited power, ρ1 = 0.2 and ρ2 = 0.4.The reduction is partly achieved through more reasonable transmission-opportunity allocation to these sensors.
  • The scheduler exploits good channel states for power-constrained sensors, while sufficiently powered sensors receive timely updates that satisfy the bandwidth constraint.
  • The network model uses an ergodic Markov channel and decouples multi-sensor scheduling into single-sensor constrained Markov decision processes.The paper develops a threshold-based policy and a truncated policy for the hard bandwidth constraint.

APPENDIX A PROOF OF LEMMA 1

The proof establishes a threshold structure for the optimal single-sensor policy by analyzing discounted costs and passing to the time-average limit. The resulting threshold depends on the channel state.

  • The value function is monotone in age, so if scheduling is optimal at age x, it remains optimal at any larger age x′ > x.
  • The proof compares expected discounted costs of idling and scheduling through their value-function difference for each channel state.
  • The optimal policy has a threshold τq for each channel state q, scheduling the sensor when the age exceeds that threshold.
  • The discounted-cost threshold structure converges to the policy minimizing time-average cost as the discount factor approaches one.

APPENDIX B PROOF OF LEMMA 2

The appendix proves that the discounted value function is non-decreasing in age for every fixed channel state. This monotonicity supports the threshold characterization of the optimal policy.

  • The monotonicity proof uses value iteration and induction over iterations before taking the limit to Vα(x, q).
  • For x1 < x2, the one-step age cost is smaller at x1 while the channel-state cost is unchanged, supporting monotonicity of the iterated value functions.
  • The discounted value function Vα(x, q) increases monotonically with age x for each fixed channel state q.

APPENDIX C PROOF OF THEOREM 2

The proof bounds the AoI cost introduced by truncating the relaxed policy and shows that this cost vanishes asymptotically, establishing asymptotic optimality under the hard bandwidth constraint.

  • The relaxed optimum provides a lower bound for the original bandwidth-and-power constrained problem, while round robin supplies a separate performance lower bound without power constraints.The round-robin bound is used as a comparison, not as the proposed policy.
  • When the relaxed policy satisfies the average constraint, the expected number of sensors waiting to transmit can be bounded, supporting the truncation-gap analysis.This waiting-set bound is combined with the per-sensor AoI-growth bound.
  • A sensor missed by truncation incurs extra AoI only while it waits for a future scheduling opportunity, with the waiting probability controlled by the bandwidth fraction and threshold spread.The bound uses the activation-threshold difference Γn and a probability term involving (1 − θ).
  • The relaxed single-sensor policy has finite activation thresholds, so each sensor's AoI remains bounded by its largest channel-state threshold during the comparison.The proof explicitly uses maxq τn,q as an upper bound on the sensor AoI.
  • The proposed truncated policy is asymptotically optimal because its AoI gap from the relaxed optimum is upper bounded and vanishes as the network grows.The proof compares the truncated policy with the relaxed policy and bounds the additional cost caused by limited bandwidth.
Loading 1912.05947v4…