Energy-Efficient Joint Offloading and Resource Allocation for Deadline-Constrained Tasks in Multi-Access Edge Computing

This paper addresses the deadline-constrained task offloading and resource allocation problem in multi-access edge computing. We aim to determine where each task is offloaded and processed, as well as corresponding communication and computation resource allocations, to maximize the total saved energy for IoT devices, while considering task deadline and system resource constraints. Especially, our system allows each task to be offloaded to one of its accessible access points (APs) and processed on a server that is not co-located with its offloading AP. We formulate this problem as an Integer Nonlinear Programming problem and show it is NP-Hard. To address this problem, we propose a Graph-Matching-based Approximation Algorithm ($\mathtt{GMA}$), the first approximation algorithm of its kind. $\mathtt{GMA}$ leverages linear relaxation, tripartite graph construction, and a Linear Programming rounding technique. We prove that $\mathtt{GMA}$ is a $\frac{1-\alpha}{2+\epsilon}$-approximation algorithm, where $\epsilon$ is a small positive value, and $\alpha$ ($0$$\le$$\alpha$$<$$1$) is a system parameter that ensures the resource allocated to any task by an AP or a server cannot exceed $\alpha$ times its resource capacity. Experiments show that, in practice, $\mathtt{GMA}$'s energy saving achieves $97\%$ of the optimal value on average.