MOERA: Mobility-Agnostic online resource allocation for edge computing

Lin Wang, Lei Jiao*, Jun Li, Julien Gedeon, Max Muhlhauser

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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 \times4× 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.

Original languageEnglish
Article number8449107
Pages (from-to)1843-1856
Number of pages14
JournalIEEE Transactions on Mobile Computing
Volume18
Issue number8
DOIs
Publication statusPublished - 1 Aug 2019
Externally publishedYes

Funding

The authors thank the anonymous reviewers for their constructive comments. This work was partially funded by the German Research Foundation (DFG) under Grant No. 392046569, the National Natural Science Foundation of China (NSFC) under Grant No. 61761136014, the DFG Collaborative Research Center (CRC) 1053 – MAKI, and partially by the US National Science Foundation under Grant No. 1564348. Any opinions, findings, and conclusions expressed in this material are those of the authors and do not necessarily reflect the views of the funding organizations.

FundersFunder number
US National Science Foundation1564348
Deutsche Forschungsgemeinschaft392046569
National Natural Science Foundation of China61761136014

    Keywords

    • competitive analysis
    • Edge computing
    • online optimization
    • resource allocation

    Fingerprint

    Dive into the research topics of 'MOERA: Mobility-Agnostic online resource allocation for edge computing'. Together they form a unique fingerprint.

    Cite this