Ephremides and colleagues consider Age of Information scheduling problem for interconnected sensors

In recent years, sensor and wireless communication advances have led to the emergence of new applications for monitoring, tracking, and even controlling operations in the physical world. More than 25 billion Internet of Things devices are forecasted to be installed by the end of 2020, mainly through wireless networks. Sensors can be interconnected to report environmental conditions or provide crucial data, such as velocity and position in networks of vehicles. These applications heavily rely on the timely delivery of data to perform at their best.

A relatively new concept, the Age of Information (AoI), quantifies this notion of timeliness. AoI measures information time-lag at the monitor side; its minimization is regarded as a way to achieve fresher information at the receiver side.

Because so many applications require timely information, AoI has captured a lot of research attention in recent years. Since its inception, AoI has been investigated in typical First-Come First-Served queuing settings, and packet management and the discard of stale packets have been shown to further reduce AoI. Priority-based queuing has also been extensively studied and is still gaining research attention. Additionally, scheduling problems, which aim to minimize AoI, have been widely explored. Specifically, back-off timers have been optimized to minimize the average age in CSMA environments.

In a new paper, On the Optimality of the Whittle’s Index Policy for Minimizing the Age of Information, Distinguished University Professor Tony Ephremides (ECE/ISR) and Ali Maatouk, Saad Kriouile, and Mohamad Assaad of the Laboratoire des Signaux et Systemes, CentraleSupélec, Gif-sur-Yvette, France consider an important version of one of these scheduling problems with a wide range of applications. The problem is, “If N users communicate with a central entity over unreliable channels where at most M users can transmit simultaneously, what is the age-optimal strategy?”

Previously the same authors showed that a greedy algorithm is optimal when users have identical channel statistics. In this paper, they explore the simple and high-performing Whittle’s index policy. This policy involves assigning an index to each user based on its age and channel statistics, and scheduling the M users with the highest indices. It has been previously adopted for a large variety of scenarios such as delay minimization and throughput maximization.

However, the analysis of its performance is known to be challenging and remains elusive in the average age minimization framework. The authors overcome these difficulties and provide rigorous analytical results on its performance, proving that the Whittle’s index policy is age-optimal for the general asymmetrical case in the burgeoning many-users regime of Internet of Things interconnected devices.

Published January 23, 2020