MOERA: Mobility-Agnostic Online Resource Allocation for Edge Computing
MOERA: Mobility-Agnostic Online Resource Allocation for Edge Computing
复制标题
DOI：
10.1109/tmc.2018.2867520
复制
发表时间：
2019-08
影响因子：
7.9
通讯作者：
Lin Wang;Lei Jiao;Jun Li;Julien Gedeon;M. Mühlhäuser
中科院分区：
文献类型：
--
作者：
Lin Wang;Lei Jiao;Jun Li;Julien Gedeon;M. Mühlhäuser
为了更好地支持新兴的交互式移动应用，例如基于VR / ar的应用，云计算正在迅速演变成一种新的计算范式，称为边缘计算。边缘计算有望将云资源带到网络边缘，以增强靠近用户的移动设备的能力。边缘计算面临的一大挑战是在用户移动性带来的高动态环境下，如何有效地分配和适应边缘资源。本文对这一问题进行了形式化的研究。通过综合成本模型表征各种静态和动态性能指标，提出了一个混合非线性优化问题的在线边缘资源分配问题。本文提出了一种基于“正则化”技术的移动不可知在线算法MOERA，该算法可将问题分解为具有正则化目标函数的独立子问题，并使用凸规划进行求解。通过严格的分析，我们能够证明MOERA可以保证参数化的竞争比，而不需要任何关于输入的先验知识。我们对各种现实世界数据进行了广泛的实验，结果表明MOERA可以实现小于1.2的经验竞争比，与静态方法相比，总成本降低了4× 4，并且比在线贪婪一次性解决方案高出70%。此外，我们验证了即使是未来不可知的，MOERA也可以达到与具有完全部分未来知识的方法相当的性能。我们还讨论了有关在实际边缘计算系统中实现我们的算法的实际问题。
To better support emerging interactive mobile applications such as those VR-/AR-based, cloud computing is quickly evolving into a new computing paradigm called edge computing. Edge computing has the promise of bringing cloud resources to the network edge to augment the capability of mobile devices in close proximity to the user. One big challenge in edge computing is the efficient allocation and adaptation of edge resources in the presence of high dynamics imposed by user mobility. This paper provides a formal study of this problem. By characterizing a variety of static and dynamic performance measures with a comprehensive cost model, we formulate the online edge resource allocation problem with a mixed nonlinear optimization problem. We propose MOERA, a mobility-agnostic online algorithm based on the “regularization” technique, which can be used to decompose the problem into separate subproblems with regularized objective functions and solve them using convex programming. Through rigorous analysis we are able to prove that MOERA can guarantee a parameterized competitive ratio, without requiring any a priori knowledge on input. We carry out extensive experiments with various real-world data and show that MOERA can achieve an empirical competitive ratio of less than 1.2, reduces the total cost by $4 \times$4× compared to static approaches, and outperforms the online greedy one-shot solution by 70 percent. Moreover, we verify that even being future-agnostic, MOERA can achieve comparable performance to approaches with perfect partial future knowledge. We also discuss practical issues with respect to the implementation of our algorithm in real edge computing systems.