On optimal link scheduling with min-max peak age of information in wireless systems

Abstract

Freshness of information is of critical importance for a host of applications of wireless communications. In order to deliver information from multiple sources in a timely and fair fashion through a wireless channel, we propose optimizing the link scheduling strategy in respect of age of information, which is a newly introduced metric that measures how fresh information is. Specifically, we consider a set of co-channel links, each having a number of packets to be delivered, and address the problem that aims to find the optimal scheduling solution, such that the maximum peak age of information is minimized. We mathematically formulate this so-called min-max peak age scheduling problem (MPASP), and prove it is NP-hard. Theoretical insights including tractable cases and optimality properties are derived. For problem solution, an integer linear programming (ILP) formulation is proposed. We also develop a sub-optimal, but fast, algorithm to solve the problem with better scalability. Numerical study shows that, by employing the optimal schedule, the maximum peak age is significantly reduced in comparison to other classic scheduling strategies such as minimum-time scheduling.