Age Optimal Information Gathering and Dissemination on Graphs
Vishrant Tripathi, Rajat Talak, Eytan Modiano · IEEE Transactions on Mobile Computing · 2019
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,j}$. For the information gathering problem, we show that a randomized trajectory is average-peak age optimal and factor-$8\mathcal {H}$average age optimal, where$\mathcal {H}$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(\mathcal {H})$average-peak and average age optimal. Moreover, we propose an age-based trajectory, which utilizes information about current age at terminals, and show that it is factor-2 average age optimal in a symmetric setting.