When to preempt? Age of information minimization under link capacity constraint

Boyu Wang, Songtao Feng, Jing Yang

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


In this paper, we consider a scenario where a source continuously monitors an object and sends time-stamped status updates to a destination through a rate-limited link. We assume updates arrive randomly at the source according to a Bernoulli process. Due to the link capacity constraint, it takes multiple time slots for the source to complete the transmission of an update. Therefore, when a new update arrives at the source during the transmission of another update, the source needs to decide whether to skip the new arrival or to switch to it, in order to minimize the expected average age of information (AoI) at the destination. We start with the setting where all updates are of the same size, and prove that within a broadly defined class of online policies, the optimal policy should be a renewal policy, and has a sequential switching property. We then show that the optimal decision of the source in any time slot has threshold structures, and only depends on the age of the update being transmitted and the AoI at the destination. We then consider the setting where updates are of different sizes, and show that the optimal Markovian policy also has a multiple-threshold structure. For each of the settings, we explicitly identify the thresholds by formulating the problem as a Markov Decision Process (MDP), and solve it through value iteration. Special structural properties of the corresponding optimal policy are utilized to reduce the computational complexity of the value iteration algorithm.

Original languageEnglish (US)
Article number8764466
Pages (from-to)220-232
Number of pages13
JournalJournal of Communications and Networks
Issue number3
StatePublished - Jun 2019

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'When to preempt? Age of information minimization under link capacity constraint'. Together they form a unique fingerprint.

Cite this