不确定性感知的边缘计算任务调度算法  

Uncertainty-aware task scheduling algorithm in edge computing environments

作　　者：尹璐 周俊龙 孙晋[1] 吴泽彬[1] YIN Lu;ZHOU Jun-long;SUN Jin;WU Ze-bin(School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China)

机构地区：[1]南京理工大学计算机科学与工程学院,南京210094

出　　处：《控制与决策》2024年第7期2405-2413,共9页Control and Decision

基　　金：江苏省重点研发计划项目(BE2022065-2);江苏省创新支撑计划项目(BZ2023046);教育部产学研创新基金项目(2020ITA03002,2021ITA01004);国家自然科学基金项目(62172224,U23B2006);江苏省自然科学基金项目(BK20220138)。

摘　　要：任务执行时长的不确定性是设计任务调度算法时的一个重要问题,关系到调度方案能否满足任务的截止时间要求.鉴于此,研究不确定性感知的边缘计算任务调度问题,以最小化边缘提供商开销为优化目标建立任务调度问题的优化模型.该模型将任务执行时长建模为随机变量并推导出任务完成时间的完整概率分布,引入关于任务截止时间的概率约束,以可调节的概率阈值保证任务按时完成.为求解该问题,进一步提出基于蝙蝠算法搜索策略的元启发式算法,包含两个关键的算法组件,映射算子实现蝙蝠空间与调度解空间的关联,评估算子实现候选解可行性的判定和优化目标值的计算.基于对比实验的仿真结果表明,所提出算法能够得到高质量的任务调度方案.When designing task scheduling algorithms,the uncertainty of task execution duration is an important concern,which impacts whether the task completion time can meet its deadline constraint.In this paper,we study the uncertainty-aware task scheduling problem in edge computing systems and formulate a scheduling optimization model with the objective of minimizing the edge provider’s monetary cost.By modeling the task execution duration as a random variable and deriving the complete probability distribution of the task completion time,the formulated model introduces a probabilistic constraint on the task’s deadline to guarantee the task is completed on time with an adjustable probability threshold.To solve this problem,this paper further proposes a metaheuristic algorithm that is built upon the bat algorithm’s search strategy.The proposed algorithm contains two key algorithmic components.The mapping operator enables the connection between the bat space and the scheduling solution space,and the evaluation operator enables the determination of the candidate solution’s feasibility and the calculation of the optimization objective value.Simulation results based on comparative experiments demonstrate that the proposed algorithm is capable of obtaining high-quality task scheduling solutions.

关 键 词：边缘计算 任务调度 不确定性 概率约束 随机优化 蝙蝠算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]