Scheduling to Minimize Age of Information with Multiple Sources

Finding an optimal/near-optimal scheduling algorithm to minimize the age of information (AoI) in a multi-source G/G/1 system is well-known to be a hard problem, more so if there is a transmission (energy) cost. In this paper, we consider a multi-source G/G/1 system and the goal is to minimize a weighted sum of the AoI of all sources, subject to an energy cost constraint. We propose a novel doubly randomized non-preemptive scheduling algorithm and show that in the non-preemptive setting, where an update under transmission cannot be preempted, the competitive ratio of the proposed algorithm is at most 3 plus the maximum of the ratio of the variance and the mean of the update inter-generation time distribution of sources. Notably, the competitive ratio is independent of the number of sources, or their service time distributions, and is at most 4 for several common update inter-generation time distributions such as exponential, uniform and Rayleigh. For preemptive setting, where an update under transmission can be preempted, we consider a multi-source G/M/1 system and show that the proposed non-preemptive algorithm has competitive ratio at most 5 plus the maximum of the ratio of the variance and the mean of the update inter-generation time distribution of sources. © 2020 IEEE.