Age Optimal Information Gathering and Dissemination on Graphs

We consider the problem of timely exchange of updates between a central station and a set of ground terminals V, via a mobile agent that traverses across the ground terminals along a mobility graph G = (V, E). We design the trajectory of the mobile agent to minimize average-peak and average age of information (AoI), two recently proposed metrics for measuring timeliness of information. We consider randomized trajectories, in which the mobile agent travels from terminal i to terminal j with probability P-i,P-j. For the information gathering problem, we show that a randomized trajectory is average-peak age optimal and factor -87-average age optimal, where 7-is the mixing time of the randomized trajectory on the mobility graph G. We also show that the average age minimization problem is NP-hard. For the information dissemination problem, we prove that the same randomized trajectory is factor -O(7-) average-peak and average age optimal. Moreover, we propose an age-based trajectory, which utilizes information about current age at symmetric setting.

Automated summary

In this study, we investigate the timely exchange of updates between a central station and a set of ground terminals. We design a trajectory for a mobile agent to minimize the average-peak and average age of information. Through analysis, we demonstrate the optimal performance of randomized trajectories for both information gathering and dissemination problems, and propose an age-based trajectory strategy.