A Competitive Approximation Algorithm for Data Allocation Problem in Heterogenous Mobile Edge Computing
Xun Shao, Zhi Liu, Mianxiong Dong, Hiroshi Masui, Yusheng Ji · 2019
In recent years, the fast development of mobile computing has substantially promoted the mobile edge computing (also known as multi-access edge computing, MEC). Placing content in edges is one of the most important uses of MEC for that it can benefit a variety of service and applications such as video streaming and VR/AR. Currently, most of the existing researches are application specified, and the heterogeneities in data allocating devices and content have not been sufficiently explored. Aiming at developing a general optimal data allocating decision algorithm for MEC, in this work, we carry out in-depth study on the interaction of data allocating and fetching in heterogenous edge computing networks, showing the NP-hardness of the optimal decision problem. We then present polynomial algorithms with 1 - 1/e-approximation factor. Our algorithms has reasonable performance guarantee with low computation complexity. We verify the proposed approach with analysis and simulations.