PaperlayerView exact revision on arXiv

Source-linked AI summary

Age of Information: Whittle Index for Scheduling Stochastic Arrivals

Yu-Pin Hsu

arXiv:1801.03422v2math.OCcs.ITcs.NI

TL;DR

The paper studies how to minimize long-run average information age when a base station schedules stochastic updates to many users but can update only one per slot. It applies Whittle’s restless-bandit framework, deriving a closed-form index and an index-based scheduling policy. The resulting algorithm is reported to nearly minimize average age in numerical studies.

  • Problem

    The paper seeks a low-complexity way to schedule stochastic information arrivals in a wireless broadcast network under a one-user-per-slot transmission constraint while minimizing long-run average age.

  • Method

    The problem is transformed into a relaxed restless multi-armed bandit, whose decoupled sub-problems are analyzed as infinite-horizon average-cost Markov decision processes.

  • Results

    The analysis derives the Whittle index in closed form, proves indexability, and establishes stationary deterministic threshold policies for the sub-problems.

  • Takeaways & Limitations

    A Whittle-index scheduling algorithm provides a low-complexity policy that numerical studies show almost minimizes average age.

Abstract

from arXiv · show

Age of information is a new concept that characterizes the freshness of information at end devices. This paper studies the age of information from a scheduling perspective. We consider a wireless broadcast network where a base-station updates many users on stochastic information arrivals. Suppose that only one user can be updated for each time. In this context, we aim at developing a transmission scheduling algorithm for minimizing the long-run average age. To develop a low-complexity transmission scheduling algorithm, we apply the Whittle's framework for restless bandits. We successfully derive the Whittle index in a closed form and establish the indexability. Based on the Whittle index, we propose a scheduling algorithm, while experimentally showing that it closely approximates an age-optimal scheduling algorithm.

I. INTRODUCTION

The paper formulates freshness-aware scheduling for stochastic information arrivals in a wireless broadcast network where the base station can update only one user per opportunity. It uses Whittle’s restless-bandit framework to derive a low-complexity policy and establish its theoretical properties.

  • I. INTRODUCTION: The scheduling problem allocates wireless transmissions among users with randomly generated information to minimize long-run average age.The base station updates many users but can transmit to at most one user per transmission opportunity.
  • I. INTRODUCTION: The work addresses the unexplored need for a low-complexity scheduling algorithm in this wireless broadcast model.Earlier related work used a similar model, while this paper investigates age-optimal scheduling through restless bandits.
  • I. INTRODUCTION: The problem is transformed into decoupled average-cost Markov decision processes within a relaxed restless multi-armed bandit formulation.The analysis proves an optimal stationary deterministic threshold policy for each sub-problem.
  • I. INTRODUCTION: The paper derives the Whittle index in closed form, proves indexability, and uses the index to construct a scheduling algorithm.The closed-form derivation exploits the threshold policy and post-action age to simplify average-cost calculations.
  • I. INTRODUCTION: The proposed algorithm is intended for stochastic information arrivals, distinguishing this work from studies with queued, periodic, or on-demand updates.The related-work discussion identifies stochastic arrivals as the setting targeted by the paper’s low-complexity scheduling contribution.

II. SYSTEM OVERVIEW

The system is a discrete-time wireless broadcast network with one base station, N users, and independent Bernoulli packet arrivals from corresponding information sources. The base station transmits at most one unbuffered arriving packet per slot.

  • II. SYSTEM OVERVIEW: A base station serves N wireless users, each interested in a distinct information type generated by a corresponding source.Packets are sent over a noiseless broadcast channel.
  • II. SYSTEM OVERVIEW: Packets arrive at the base station at slot beginnings, independently across users and identically across slots according to Bernoulli processes.For user i, Λ_i(t)=1 denotes an arrival and P[Λ_i(t)=1]=p_i.
  • II. SYSTEM OVERVIEW: The base station can update at most one user per slot and does not buffer packets that are not transmitted in their arrival slot.This no-buffer assumption is motivated by earlier work.
  • II. SYSTEM OVERVIEW: A scheduling algorithm specifies whether no user or which user is updated in every slot.The decision is represented by D(t)=0 for no update or D(t)=i for updating user i.

B. Age of information model

The age model tracks each user’s information freshness before each scheduling decision. A successful transmission resets the user’s next-slot age to one; otherwise, age increases by one.

  • B. Age of information model: Each arriving packet starts with age zero, while a user’s received information has age one because transmission takes one slot.X_i(t) denotes user i’s age before the scheduling decision in slot t.
  • B. Age of information model: Age increases linearly across slots unless the user receives newly arrived information.The next-slot age is one after an update and X_i(t)+1 otherwise.
  • B. Age of information model: Because at most one user is updated per slot, all user ages remain positive and distinct.The model states X_i(t)≥1 and X_i(t)≠X_j(t) for i≠j.
  • B. Age of information model: The total age is therefore bounded below by 1+2+⋯+N at every slot.This lower bound follows from the positive, pairwise-distinct age values.

C. Problem formulation

The optimization objective is the expected long-run time average of the total age across all users under a scheduling algorithm.

  • C. Problem formulation: The objective minimizes the long-run average total age induced by scheduling decisions.The expectation is conditional on the employed algorithm θ, and the formulation can extend to weighted age sums.

III. SCHEDULING ALGORITHM DESIGN

The paper designs a scheduling algorithm by modeling the network as a restless multi-armed bandit problem, deriving Whittle indices, and using them to select updates.

  • The network problem is cast as a restless multi-armed bandit problem and developed through Whittle’s framework.
  • The approach derives the Whittle index explicitly using a post-action age formulation.
  • The resulting Whittle-index policy is used to construct the transmission scheduling algorithm.

A. Restless bandits and Whittle’s approach

Whittle’s relaxation treats users as restless bandits, replaces the per-slot activation constraint with an expected constraint, and decouples the problem into user-specific sub-problems.

  • A restless bandit can evolve under a passive action differently from its evolution under an active action.
  • The original problem is relaxed by replacing the per-slot active-bandit constraint with a constraint on the expected number of active bandits.
  • Each user is modeled as a restless bandit, allowing the network problem to be decomposed into N single-user sub-problems.
  • Each sub-problem balances the updating cost against age-related cost, with the updating cost represented by a scalar Lagrange multiplier C.

B. Decoupled sub-problem

The decoupled sub-problem is an average-cost MDP whose state combines age and arrival information, whose binary action controls updating, and whose transitions and costs describe the user dynamics.

  • The sub-problem is formulated as a Markov decision process for average-cost optimization.
  • The state is s(t) = (X(t), Λ(t)), where age can make the MDP’s state space infinite.
  • The binary action a(t) indicates whether the base station updates the user or idles.
  • The transition probabilities specify how age and arrival information evolve under idle and update actions.
  • The immediate cost C(s(t), a(t)) is assigned to each state-action pair, while the objective minimizes long-run average cost.
  • Policies may be history dependent, stationary, randomized, or deterministic, and an optimal policy minimizes the average cost.

C. Characterizing a cost-optimal policy

The section establishes that an average-cost-optimal policy exists in stationary deterministic form and can be represented by a threshold rule. It then characterizes the threshold policy through a post-action-age Markov chain and its average cost.

  • A stationary and deterministic policy is cost-optimal, independently of the initial state.
  • When C ≥ 0, a cost-optimal policy of threshold type exists.The policy idles without an arrival and updates when an arrival occurs at an age at least the threshold.
  • The threshold structure follows from the monotonicity of the discounted cost in age for a fixed arrival indicator.If updating is optimal at age x with an arrival, it remains optimal at age x+1.
  • The post-action-age DTMC yields the steady-state distribution and average cost for a given threshold.The section derives the average cost by associating cost C + 1 with post-action age 1 and cost y with other post-action ages.
  • The post-action age Y(t) differs from the pre-action age X(t) and forms a DTMC under a threshold-type policy.This representation associates each state with a cost determined by the post-action age.
  • The post-action-age formulation avoids difficulties associated with solving an average-cost equation or a multidimensional DTMC directly.For the pre-action age, cost depends on both state and action, whereas post-action age determines cost by state alone.

D. Deriving the Whittle index

The paper defines the Whittle index as the update cost making both actions equally desirable, derives the optimal threshold from it, and proves indexability.

  • The Whittle index I(s) is the cost that makes updating and idling equally desirable in state s.
  • For state (x, 0), the Whittle index is I(x, 0) = 0 because both actions have identical immediate and next-slot age costs.
  • The optimal threshold is x when I(x −1, 1) ≤C < I(x, 1), for x = 1, 2, · · ·.
  • The threshold increases monotonically with updating cost C, with ties broken in favor of idling.
  • The sub-problem is indexable because the states where idling is optimal expand monotonically from the empty set to the entire state space as C increases.

E. Scheduling algorithm design

The proposed scheduler observes each user's age and arrival indicator, then updates the user with the highest Whittle index. In a two-user, 100,000-slot comparison, it almost achieves the minimum average age.

  • At each slot, the base station updates the user with the highest Whittle index I(Xi(t), Λi(t)).
  • The index can be interpreted as the cost of updating a user, prioritizing the most valuable packet.
  • 100,000 slots: for two users, the simple index algorithm almost achieves the minimum average age of the age-optimal scheduler.

IV. CONCLUSION

The paper proposes a low-complexity Whittle-based scheduling algorithm for minimizing average information age in a constrained wireless broadcast network. Numerical studies show that it almost minimizes average age, while identifying optimality in another regime as future work.

  • The study addresses transmission scheduling for age of information in a wireless broadcast network with a transmission constraint.
  • The proposed low-complexity algorithm leverages Whittle's methodology and almost minimizes average age in numerical studies.
  • Identifying a regime in which the proposed algorithm is optimal remains an interesting extension.
Loading 1801.03422v2…