A semidefinite relaxation approach for the offloading problem in edge computing. (March 2022) - Han, Xinxin; Gao, Guichen; Ning, Li; Wang, Yang; Zhang, Yong
Abstract: In traditional cloud computing, tasks will be offloaded to the could, which often leads to high latency and low quality of service. To avoid this disadvantage, edge computing was introduced. The fundamental issue in edge computing is selecting some tasks to be computed in the edge, which is called the offloading problem. In most previous studies, the communication cost between any two tasks is often assumed to be symmetric in different sides and is often ignored within the same side. In this paper, we consider a heterogeneous offloading model, where the communication cost exists everywhere and is asymmetric. With the help of semidefinite relaxation, we give an algorithm for the offloading problem. If the Laplacian matrix with respect to the offloading problem is positive semidefinite, the theoretical guarantee can be proved to be 2 π . The performance of the proposed algorithm is also evaluated via numerical analysis. The experimental results show that the algorithm is very effective. Graphical abstract: Highlights: Edge computing can avoid long delay between the cloud and users. A deep theoretical analysis for the offloading problem. Design a semidefinite relaxation based approximation algorithm.