Energy-Efficient Computation Offloading for Mobile Edge Networks: A Graph Theory Approach

Computation offloading is deemed as a promising technology for ensuring user experience and realizing load balance. However, it is challenging to utilize network resources efficiently due to lack of collaborative management ability of isolated edge devices. In this paper, we propose a computation offloading scheme to minimize the total energy consumption for mobile edge networks. Specifically, we formulate the problem as a mixed integer non-linear program and transform it to two sub-problems, namely task offloading sub-problem and resource allocation sub-problem. We leverage the improved graph theory algorithm to figure out the computation offloading subproblem, and use the binary search algorithm along with priority assignment to solve the resource allocation sub-problem. The numerical results reveal that maximum-alternative-differences-first Gale Sherply (MADF-GS) algorithm performs the best among all GS algorithms, which combines low time complexity with excellent performance, and it saves at least 66.7% energy consumption in comparison with the conventional scheme.