Joint Task Offloading and Service Placement for Mobile Edge Computing: An Online Two-Timescale Approach

Abstract

As a new computing paradigm, mobile edge computing (MEC) pushes the centralized cloud resources close to the edge network, which significantly reduces the pressure of the backbone network and meets the requirements of emerging mobile applications. To achieve high performance of the MEC system, it is essential to design efficient task offloading and service placement schemes, which are responsible for offloading tasks to the edge servers while considering the heterogeneity and diversity of computation services. Our MEC system aims to maximize the long-term average network utility while maintaining the stability of the edge network. Considering that synchronous manner overlooks the scenarios endowed with asymmetric update frequencies for service placement and task offloading, we propose an online algorithm based on the two-timescale Lyapunov optimization in a stochastic network environment without requiring the future information. By making asynchronous decisions on service placement and task offloading with different control parameters <inline-formula><tex-math notation="LaTeX">$V$</tex-math></inline-formula> , we can achieve a time-average sub-optimal solution that is close to the offline optimum. In addition, we introduce the varying control parameter <inline-formula><tex-math notation="LaTeX">$V(t)$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\Omega$</tex-math></inline-formula> -additive approximation to enhance the robustness of the proposed algorithm within an error <inline-formula><tex-math notation="LaTeX">$\Omega$</tex-math></inline-formula> . Finally, rigorous theoretical analysis and extensive trace-driven experimental results show that the proposed algorithm achieves the <inline-formula><tex-math notation="LaTeX">$[O(1/V), O(V)]$</tex-math></inline-formula> performance-backlog tradeoff and is more competitive than benchmarks.