Age Optimal Information Gathering and Dissemination on Graphs
Age Optimal Information Gathering and Dissemination on Graphs
复制标题
DOI：
10.1109/tmc.2021.3076755
复制
发表时间：
2023-01
影响因子：
7.9
通讯作者：
Vishrant Tripathi;Rajat Talak;E. Modiano
中科院分区：
文献类型：
--
作者：
Vishrant Tripathi;Rajat Talak;E. Modiano
我们考虑通过一个移动代理在中心站和一组地面终端$V$之间及时交换更新的问题，该移动代理沿着移动图$G=(V,E)$遍历地面终端。我们设计移动代理的轨迹以最小化平均峰值和信息平均年龄（AoI），这是最近提出的两个用于衡量信息及时性的指标。我们考虑随机轨迹，其中移动代理从终端$i$以概率$P_{i,j}$移动到终端$j$。对于信息收集问题，我们表明随机轨迹在平均峰值年龄方面是最优的，并且在平均年龄方面是$8\mathcal{H}$因子最优的，其中$\mathcal{H}$是随机轨迹在移动图$G$上的混合时间。我们还表明平均年龄最小化问题是NP难的。对于信息传播问题，我们证明相同的随机轨迹在平均峰值和平均年龄方面是$O(\mathcal{H})$因子最优的。此外，我们提出一种基于年龄的轨迹，它利用终端当前年龄的信息，并表明在对称设置下它在平均年龄方面是2因子最优的。
We consider the problem of timely exchange of updates between a central station and a set of ground terminals $V$V, via a mobile agent that traverses across the ground terminals along a mobility graph $G = (V, E)$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$i to terminal $j$j with probability $P_{i,j}$Pi,j. For the information gathering problem, we show that a randomized trajectory is average-peak age optimal and factor-$8\mathcal {H}$8H average age optimal, where $\mathcal {H}$H is the mixing time of the randomized trajectory on the mobility graph $G$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})$O(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.