A Competitive Approximation Algorithm for Data Allocation Problem in Heterogenous Mobile Edge Computing

摘要

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.