Exploiting the computational heterogeneity of mobile devices and edge nodes,
mobile edge computation (MEC) provides an efficient approach to achieving
real-time applications that are sensitive to information freshness, by
offloading tasks from mobile devices to edge nodes. We use the metric
Age-of-Information (AoI) to evaluate information freshness. An efficient
solution to minimize the AoI for the MEC system with multiple users is
non-trivial to obtain due to the random computing time. In this paper, we
consider multiple users offloading tasks to heterogeneous edge servers in a MEC
system. We first reformulate the problem as a Restless Multi-Arm-Bandit (RMAB)
problem and establish a hierarchical Markov Decision Process (MDP) to
characterize the updating of AoI for the MEC system. Based on the hierarchical
MDP, we propose a nested index framework and design a nested index policy with
provably asymptotic optimality. Finally, the closed form of the nested index is
obtained, which enables the performance tradeoffs between computation
complexity and accuracy. Our algorithm leads to an optimality gap reduction of
up to 40%, compared to benchmarks. Our algorithm asymptotically approximates
the lower bound as the system scalar gets large enough.

本篇论文提出了一种优化移动边缘计算系统中信息鲜度的算法，使用了多层次 MDP 和嵌套索引框架，并设计了一种带有可证明渐近最优性的嵌套索引策略，与基准相比，我们的算法优化间隙缩小了高达 40％，并且当系统纲量足够大时，渐进地逼近了下限。