Joint Optimization of Path Planning and Resource Allocation in Mobile Edge Computing

作     者：Liu, Yu Li, Yong Niu, Yong Jin, Depeng 

作者机构：Tsinghua Univ Dept Elect Engn Beijing Natl Res Ctr Informat Sci & Technol BNRis Beijing 100084 Peoples R China Beijing Jiaotong Univ Beijing Engn Res Ctr High Speed Railway Broadband State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China Beijing Jiaotong Univ Sch Elect & Informat Engn Beijing 100044 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON MOBILE COMPUTING》 (IEEE移动计算汇刊)

年 卷 期：2020年第19卷第9期

页      面：2129-2144页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Research and Development Program of China [2017YFE0112300] National Nature Science Foundation of China [61861136003, 61621091, 61673237] Beijing National Research Center for Information Science and Technology Tsinghua University -Tencent Joint Laboratory for Internet Innovation Technology 

主　　题：Task analysis Resource management Edge computing Path planning Optimization Processor scheduling Mobile computing Mobile edge computing vehicles computation task offloading path planning piecewise linear approximation 

摘      要：With the rapid development of mobile applications, mobile edge computing (MEC), which provides various cloud resources (e.g., computation and storage resources) closer to mobile and IoT devices for computation offloading, has been broadly studied in both academia and industry. However, due to the limited coverage of static edge servers, the traditional MEC technology performs badly in a nowadays environment. To adapt the diverse demands, in this paper, we propose a novel mobile edge mechanism with a vehicle-mounted edge (V-edge) deployed. Aiming at maximizing completed tasks of V-edge with sensitive deadline, the problem of joint path planning and resource allocation is formulated into a mixed integer nonlinear program (MINLP). By utilizing the piecewise linear approximation and linear relaxation, we transform the MINLP into a mixed integer linear program (MILP). To obtain the near-optimal solution, we further develop a gap-adjusted branch & bound algorithm, also called GA-B&B algorithm. Moreover, we propose a low-complexity L-step lookahead branch scheme (referred to as L-step scheme) for efficient scheduling in large-scale scenarios. Extensive evaluations demonstrate the superior performance of the proposed scheme compared with the traditional static edge mechanism. Furthermore, the proposed L-step scheme achieves close performance to the near-optimal solution, and significantly improves the task completion percentage of state-of-the-art schemes by over 10 percent.