Distributed algorithm for computation offloading in mobile edge computing considering user mobility and task randomness

Recent years have witnessed substantial research efforts on computation offloading for mobile edge computing (MEC) systems. User mobility is an intrinsic trait of many MEC applications, which has posed significant challenges for realizing reliable computing. However, existing works studying this problem mainly focus on the movements of users while another high-dynamic behavior due to the randomness of computation task is largely ignored. To fill this gap, in this paper, we formulate the computation offloading decision problem in MEC system as a combinatorial optimization problem, and then we use Log-Sum-Exp function to approximate the optimal objective. Thereafter, we construct a Markov chain with steady-state distribution specifying to our problem in a distributed manner, such that the user mobility problem is transformed into the state transition problem. Moreover, this Markov chain is further extended to consider a dynamic scenario where the number of active users in the MEC system changes due to the random arrivals of new computation task or completions of old tasks. Numerical results show that our proposed computation offloading distributed algorithm can converge very fast to the optimal solution, and has a provable performance with a guaranteed loss bound.