Efficient Algorithms for Multi-Component Application Placement in Mobile Edge Computing
Tayebeh Bahreini, Daniel Grosu
Abstract
In this article, we address the Multi-Component Application Placement Problem ( <inline-formula><tex-math notation="LaTeX">${\sf MCAPP}$</tex-math></inline-formula> ) in Mobile Edge Computing (MEC) systems. We formulate this problem as a Mixed Integer Non-Linear Program (MINLP) with the objective of minimizing the total cost of running the applications. In our formulation, we take into account two important and challenging characteristics of MEC systems, the mobility of users and the network capabilities. We analyze the complexity of <inline-formula><tex-math notation="LaTeX">${\sf MCAPP}$</tex-math></inline-formula> and prove that it is <inline-formula><tex-math notation="LaTeX">$NP$</tex-math></inline-formula> -hard, that is, finding the optimal solution in reasonable amount of time is infeasible. We design two algorithms, one based on matching and local search and one based on a greedy approach, and evaluate their performance by conducting an extensive experimental analysis driven by two types of user mobility models, real-life mobility traces and random-walk. The results show that the proposed algorithms obtain near-optimal solutions and require small execution times for reasonably large problem instances.