边缘计算系统中延时敏感型任务调度策略  

Delay-sensitive tasks scheduling strategy in edge computing system

作　　者：王星[1] 于炯[1] 杜旭升 张姗姗 杨少智 WANG Xing;YU Jiong;DU Xu-sheng;ZHANG Shan-shan;YANG Shao-zhi(Department of Information Science and Engineering,Xinjiang University,Urumqi 830046,China)

机构地区：[1]新疆大学信息科学与工程学院,新疆乌鲁木齐830046

出　　处：《计算机工程与设计》2022年第7期1949-1954,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(61862060、61462079、61562086、61562078)。

摘　　要：为降低边缘计算系统中卸载任务的调度代价,以满足任务延时需求和系统代价最小为目标,建立边缘计算系统代价优化模型。证实该问题是NP-hard问题,提出一种基于两阶段代价优化任务调度算法TTSCO。根据改进BF算法求解初步任务调度方案,降低首阶段的非必要代价,生成调度最终解。分析算法时间复杂度,通过仿真实验验证了算法性能,实验结果表明,与LINGO理论最优解相比,调度解的近似比在95%情况下均小于1.2,该算法可以进一步降低系统代价。To reduce the scheduling cost of offloaded tasks in edge computing system,for satisfying the tasks delay and minimizing the system cost,the cost optimization model based on edge computing system cost was established.This problem was proved to be NP hard problem,and a cost optimization tasks scheduling based on two-stage was put forward,namely TTSCO.An initial tasks scheduling strategy based on best fit algorithm was generated.The unnecessary cost in the first stage was reduced to generate the final scheduling solution.The time complexity of the algorithm was analyzed,and the algorithm perfor-mance was verified using simulation experiments.The results show that,the approximation ratio of the scheduling solution is less than 1.2 for 95%of cases compared with the theory of optimal solution under LINGO.And the algorithm can further reduce the cost of edge of computing systems.

关 键 词：边缘计算 延时敏感型任务 代价优化 任务调度 延时需求 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]