Optimal Link Scheduling for Age Minimization in Wireless Systems

Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.

I. Introduction

For a wireless system with applications that require availability of fresh information, such as a monitoring system, which obtains information from environmental sensors, or a cellular system where channel information needs to be periodically acquired, freshness of the received information is important. The information generated by the source reflects the most recent status value. However, the reception of the information is delayed and hence aged due to the time spent in queueing and transmission. To measure the freshness of information, the concept of age of information at a given time has been defined as the difference between the current time and the time when the latest received information sample was generated [1].