Program Placement Optimization for Storage-constrained Mobile Edge Computing Systems: A Multi-armed Bandit Approach

摘要

Mobile edge computing (MEC) is a promising technology to support computationally intensive mobile applications with stringent delay requirements. As MEC applications become much more diverse and complex, it becomes more challenging for an edge node (EN) with limited storage to keep the program codes of all tasks. In this paper, we investigate the problem of program placement and user association in storage-limited MEC systems. Formulating the problem as a sequential decision-making problem, we first derive the solution for a single EN by transforming the formulation into a multi-armed bandit (MBA) problem and solving it via a Thompson sampling (TS) algorithm. We then propose a solution framework for the multi-EN scenario, where we decompose the original problem into three subproblems and solve them with low-complexity approaches. The first subproblem is to learn the task popularity, which we also formulate as a MAB problem and solve it via a TS algorithm. The second subproblem is optimizing program placement under a given user association and we propose a greedy algorithm to solve it. The last subproblem relates to user association, which is solved by a dual decomposition-based approach. Simulation results show that the average latency achieved by our proposed schemes is 30% to 100% lower than two benchmark schemes and is on average less than 10% higher than a lower bound.