A semidefinite relaxation approach for the offloading problem in edge computing. (March 2022)

• Record Type: Journal Article
• Authors: Han, Xinxin; Gao, Guichen; Ning, Li; Wang, Yang; Zhang, Yong
• Is Part Of: Computers & electrical engineering. Volume 98(2022)
• Publication Date: 2022-03
• Subjects: Edge computing -- Offloading -- Approximation algorithm -- Semidefinite relaxation -- Performance ratio; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.107728
• Languages: English
• ISSNs: 0045-7906

Abstract

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.