Energy-Efficient Admission of Delay-Sensitive Tasks for Mobile Edge Computing
Energy-Efficient Admission of Delay-Sensitive Tasks for Mobile Edge Computing
复制标题
移动边缘计算的延迟敏感任务的节能准入
DOI：
10.1109/tcomm.2018.2799937
复制
发表时间：
2018-06-01
影响因子：
8.3
通讯作者：
Liu, Ren Ping
中科院分区：
文献类型：
--
作者：
Lyu, Xinchen;Tian, Hui;Liu, Ren Ping
任务准入对于移动边缘计算中的延迟敏感应用程序至关重要，但由于其组合混合性质以及因此限制的可扩展性，在技术上具有挑战性。我们提出了一种渐近最优的任务准入方法，该方法能够保证任务延迟并实现 <inline-formula> <tex-math notation="LaTeX">$(1-\epsilon)$ </tex-math></inline-formula> - 在与设备的时间复杂度线性缩放的情况下，近似计算上禁止的最大节能。 <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> 与能量的量化区间呈线性关系。其关键思想是通过预先接纳资源受限设备，将任务接纳的混合整数规划转化为具有最优子结构的整数规划（IP）问题。另一个重要方面是我们开发的新的量化动态规划算法，用于利用最优子结构并求解 IP。对能量的量化区间进行优化，以实现 <inline-formula> <tex-math notation="LaTeX">$[\mathcal {O}(\epsilon),\mathcal {O}(1/\epsilon)]$ </tex-math></inline-formula> - 算法的最优性损失和时间复杂度之间的权衡。模拟表明，与最优分支定界方法相比，我们的方法能够以额外能量的边际成本显着提高任务准入的可扩展性，并且可以有效地实现在线编程。
Task admission is critical to delay-sensitive applications in mobile edge computing, but is technically challenging due to its combinatorial mixed nature and consequently limited scalability. We propose an asymptotically optimal task admission approach which is able to guarantee task delays and achieve <inline-formula> <tex-math notation="LaTeX">$(1-\epsilon)$ </tex-math></inline-formula>-approximation of the computationally prohibitive maximum energy saving at a time-complexity linearly scaling with devices. <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> is linear to the quantization interval of energy. The key idea is to transform the mixed integer programming of task admission to an integer programming (IP) problem with the optimal substructure by pre-admitting resource-restrained devices. Another important aspect is a new quantized dynamic programming algorithm which we develop to exploit the optimal substructure and solve the IP. The quantization interval of energy is optimized to achieve an <inline-formula> <tex-math notation="LaTeX">$[\mathcal {O}(\epsilon),\mathcal {O}(1/\epsilon)]$ </tex-math></inline-formula>-tradeoff between the optimality loss and time complexity of the algorithm. Simulations show that our approach is able to dramatically enhance the scalability of task admission at a marginal cost of extra energy, as compared with the optimal branch and bound method, and can be efficiently implemented for online programming.