一种去中心化的在线边缘任务调度与资源分配方法  

A Decentralized Online Edge Task Scheduling and Resource Allocation Approach

作　　者：彭青蓝 夏云霓[1] 郑万波 吴春蓉 庞善臣 龙梅 蒋宁 PENG Qing-Lan;XIA Yun-Ni;ZHENG Wan-Bo;WU Chun-Rong;PANG Shan-Chen;LONG Mei;JIANG Ning(Software Theory and Technology Chongqing Key Lab,College of Computer Science,Chongqing University,Chongqing 400044;Data Science Research Center,Kunming University of Science Technology,Kunming 650500;College of Computer Science and Technology,China University of Petroleum,Qingdao,Shandong 266510;ZBJ Networks Co.,Ltd,Chongqing 401123;MSXF Networks Co.,Ltd,Chongqing 401121)

机构地区：[1]重庆大学计算机学院软件与理论重庆市重点实验室,重庆400044 [2]昆明理工大学数据科学研究中心,昆明650500 [3]中国石油大学计算机科学与技术学院,山东青岛266510 [4]重庆猪八戒网络科技有限公司,重庆401123 [5]马上消费金融股份有限公司,重庆401121

出　　处：《计算机学报》2022年第7期1462-1477,共16页Chinese Journal of Computers

基　　金：国家自然科学基金项目(62172062,62162036);重庆市重点研发计划项目(cstc2019jscx-xyd0385)资助.

摘　　要：创新移动应用迅速发展和5G通讯技术的成熟落地引发了终端用户对计算资源下沉至边缘的巨大需求,从而推动了多接入边缘计算(Multi-access Edge Computing,MEC)概念的提出和发展.在MEC环境中,用户可以将移动任务卸载到周围部署的边缘服务器上来加速移动应用.尽管边缘服务器可以在近用户端提供低时延、高响应性的服务,但其仍面临计算资源有限和用户请求多样带来的挑战,因此需要效率高、实时性强的任务调度与资源分配策略来合理地利用边缘资源.然而,目前针对MEC环境下任务调度和资源分配的方法大多基于中心化架构,并以批处理的方式对某个时间段到达任务进行统一调度与资源分配,因此在面对异构复杂的MEC资源网络和高时延敏感用户需求时具有一定的局限性,此外传统方法还缺少对任务多样性和优先级的考量.针对上述问题,本文提出了一种去中心化的在线任务调度与资源分配方法D-TSRA,该方法以任务优先级加权的卸载响应时间为评价指标,由实时任务调度策略、边缘资源分配策略、和运行时任务迁移策略组成.基于真实边缘环境下数据集的实验表明本文所提出的D-TSRA方法与传统任务调度与资源分配方法相比最多能够减少34.21%的加权任务卸载响应时间.The rapid development of novel mobile applications and advanced communication technologies have created a huge demand for mobile computing resources,which promotes the emergence of Multi-access Edge Computing(MEC)paradigm.In MEC environments,edge users are allowed to offload their mobile tasks to nearby edge servers to relieve the shortage of mobile resources.Through edge servers could provide low-latency services with high-responsible computing capabilities,they are still faced with the challenge of limited computing resources and the massive offloading requests.Thus,smart task scheduling and resource provision strategies with high real-time property are in high demand for better resource utilization.Traditional approaches are usually based on the centralized architecture and batch-processing scheduling mode,which might suffer from low efficiency and high communication overhead.In this paper,we target at the online edge task scheduling and resource allocation problem,propose a decentralized approach,and prove it is O(1/ε2)-competitive when augmented with ε additional computing power.Experiments based on real-world edge environments have demonstrated that the proposed approach could achieve at most 34.21%reduction on the average weighted offloading response time.

关 键 词：多接入边缘计算 移动任务卸载 去中心化调度 在线资源分配 边缘任务迁移 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]