  Mobile edge computing is a new computing paradigm, which pushes cloud
computing capabilities away from the centralized cloud to the network edge.
However, with the sinking of computing capabilities, the new challenge incurred
by user mobility arises: since end-users typically move erratically, the
services should be dynamically migrated among multiple edges to maintain the
service performance, i.e., user-perceived latency. Tackling this problem is
non-trivial since frequent service migration would greatly increase the
operational cost. To address this challenge in terms of the performance-cost
trade-off, in this paper we study the mobile edge service performance
optimization problem under long-term cost budget constraint. To address user
mobility which is typically unpredictable, we apply Lyapunov optimization to
decompose the long-term optimization problem into a series of real-time
optimization problems which do not require a priori knowledge such as user
mobility. As the decomposed problem is NP-hard, we first design an
approximation algorithm based on Markov approximation to seek a near-optimal
solution. To make our solution scalable and amenable to future 5G application
scenario with large-scale user devices, we further propose a distributed
approximation scheme with greatly reduced time complexity, based on the
technique of best response update. Rigorous theoretical analysis and extensive
evaluations demonstrate the efficacy of the proposed centralized and
distributed schemes.
