边缘计算环境下的任务调度综述

邓勇琛，胡忠波，王素贞

(河北经贸大学信息技术学院，河北 石家庄 050061)

0 引言

随着5G、物联网与人工智能技术的发展，涌现出了大量计算密集型与时延敏感型应用(例如智能家居、无人驾驶等)，客户端产生的数据呈指数增长[1]。虽然云计算具有超大规模的计算能力，支持海量数据运算，但云计算采取集中式处理模式[2-3]，海量数据上传至云中心将会面临网络抖动和核心网络阻塞[4]的风险。而且如果终端设备距离云中心很遥远，数据上传至云中心需要花费大量的时间，难以满足时延敏感型应用的需求，边缘计算能够较好地解决这一问题。终端设备产生的数据只需要上传至具有计算能力的边缘节点，节省了传输时延与能耗。边缘计算研究的关键技术为边缘层的资源管理方法、边缘层的计算任务卸载、边缘层的存储基础服务与边缘层的任务调度等。

本文围绕边缘层的任务调度问题，首先介绍了边缘计算三层系统架构，其次介绍了任务调度概念及流程，最后针对不同目标优化的任务调度策略进行了分析并对比了各自的优缺点。

1 “云-边-端”三层系统架构

“云-边-端”三层架构模式充分发挥了边缘节点与云中心各自的优势，利用云中心大量的存储与计算资源对任务调度起到宏观调控的作用。云中心与边缘层优势互补，共同参与任务调度，使终端任务可以合理地部署到边缘节点或云中心。“云-边-端”协同架构示意图如图1所示。基于“云-边-端”纵向融合的思想，整个系统可以划分为终端层、边缘层和云中心层。边缘层位于云中心和终端设备之间，边缘层主要包含两部分：边缘节点与边缘节点管理器。其中边缘节点是硬件实体(具有计算能力的小型基站等)，可提供各种计算资源，边缘节点管理器对边缘节点进行统一管理。

图1 “云-边-端”三层架构示意图

基于“云-边-端”三层架构，周博文等人[5]针对无人机配送系统，为了解决云计算中出现的高传输时延问题，提出了基于最短响应时间改进的任务调度算法，并且为了预防网络的不稳定性引入参数α。最后实验证明，此算法可以有效解决因网络波动而产生调度算法不稳定的问题。苏命峰等人[6]为了将云计算能力下沉至边缘节点，设计了一种云边协同的计算框架，并且重新定义了系统服务效用的目标函数。实验结果表明，此算法可以使云计算能力有效地下沉至边缘节点，减少了任务处理的时延，缓解了核心网络带宽的压力。

2 任务调度技术分析

由于边缘节点计算资源的异构性、差异性以及服务器地理位置的分散性[7]，任务调度成为了边缘计算研究的重要问题之一。任务调度策略影响资源是否能够有效使用以及满足用户体验[8]。通过将任务合理地部署到云中心或边缘节点，给任务分配合理的计算资源从而实现了云中心与边缘节点以及边缘节点之间的高效协同，能够有效解决边缘节点资源负载不均衡的问题，而且提高了有限的边缘资源利用效率，保证了计算结果和服务请求的及时响应。

2.1 任务调度技术概念及流程

基于“云-边-端”三层系统架构下的边缘计算任务调度技术是指通过一定规则，将终端任务合理地部署到边缘服务器或云中心的过程。任务调度流程如图2所示，其步骤为：

(1)将终端任务所需计算资源种类及数量等信息上传至任务调度管理器(部署在云中心)，并将任务信息存储至任务调度队列。

(2)任务调度管理器接收边缘服务器的资源数量及种类。

(3)判断边缘服务器是否满足任务所需资源，若满足则将任务部署至合理的边缘节点，否则判断将任务上传至云中心的时延是否在可接受范围内。若时延可承受，则将任务上传至云中心，否则任务执行失败。

(4)判断任务调度队列是否为空，若不为空，重复(3)过程，若为空则将任务调度策略返回至终端设备。

图2 任务调度流程图

2.2 任务划分

2.2.1 基于粗粒度的任务调度

若终端设备产生的任务不可被切割为数据量更小的子任务，则直接对任务进行调度部署。其优点在于不必考虑任务切割模型，直接将任务传输至任务调度队列中，等待合理部署。其缺点为当遇到任务数据量差别较大的时候，不能很好地利用边缘节点之间的并行性，进而使边缘服务器不易达到负载均衡状态。

在任务粒度不进行划分的情况下，Yi 等人[9]为了解决各种计算密集型应用在超密集网络中爆炸式增长从而导致计算设备负荷高的问题，通过构建通信模型，严格控制任务卸载的数量，有效减小了计算设备的负荷。

2.2.2 基于细粒度的任务调度

图3 具有依赖关系的子任务

若终端设备产生的任务可以被切割，则需根据任务切割模型将任务切割为相互独立或具有依赖关系的子任务。根据不同的任务类型可以使用不同的任务划分模型，文献[10]使用图论法与分层划分方法，将任务划分为具有依赖关系的子任务,如图3所示。其中A、B为起始子任务， H为结束子任务。

3 基于不同优化目标的任务调度策略

任务调度策略通常以性能、能耗[11]和系统效用[12]作为优化指标。其中性能指标包含任务调度时延和任务完成截止时间。任务调度时延直接影响用户服务质量，任务完成截止时间可以表示任务的紧急程度，用于确定任务的优先级。系统效用主要指边缘服务器之间的负载均衡状态。若边缘节点之间负载不均衡，有的边缘服务器任务过于繁忙，而有的边缘服务器又过于空闲，则会导致边缘节点整体资源利用率降低，因此系统效用也是优化目标之一。本节主要以提高性能、降低能耗和提高边缘服务器的系统效用为目标进行分析。

3.1 基于优化性能的任务调度策略

当面临时延敏感性任务需要被快速响应时，此时的任务调度策略需要以优化性能为目标。本小节梳理了不同调度策略的应用场景、关键研究点，并对比了各自的优缺点。

张翀宇等人[13]为了解决物联网中的数据流任务的调度问题，将时间定义切割为时间帧，并在设备端构建了数据流准许输入层、任务积压层，从而搭建了实时数据调度模型。由于数据流任务是随机的且易发生动态变化，因此使用李雅普诺夫(Lyapunov)方程来定义当前系统的负载状态集合，并使用贪心算法寻找最优设备。仿真结果表明，算法达到了98.3%的性能。但是其假设系统环境干扰为固定值，造成算法的鲁棒性低。章新川等人[14]针对淤地坝实时监测问题，为了使预警系统具有较强的时效性，提出了基于模拟退火的边缘计算协作式任务调度算法。其模型构建主要包含三部分：获取计算任务信息(任务计算量、任务总数量、任务数据量计算能力、通信带宽与服务器的数量等)、建立时间模型(传输时间、等待时间与上传时间)、应用模拟退火算法寻找最优解。最后模拟仿真实验表明，此种调度方式达到了预期的效果。缺点在于此种任务调度只适用于任务没有优先级的场景，适用范围具有局限性。

刘泽宁等人[15]分析了物联网的发展需要多层次算力资源来满足任务需求，且如何进行合理的资源调度是发展多层次算力的关键，为此本文提出了一种分布式的任务调度算法，通过构建通信模型(见公式(1))、计算模型(见公式(2))以及付费模型(见公式(3))，从而使用户获取更多收益。

(1)

(2)

cnm=cf(1-a(nm(a)-1))znYn

(3)

Yuan等人[16]为了降低平均任务响应时延，减少任务饥饿，将在线学习和深度强化学习技术相结合，提出了一种在线任务调度和公平调度方法。其采用线上学习方法，实时评估网络状况和服务器负载，然后动态地将任务分配给最优的边缘服务器。同时在每个边缘服务器上，通过结合循环机制和深度强化学习机制，可以为时延敏感型任务分配适当的资源，实现调度算法的高效率与公平性。仿真实验表明，公平的任务调度机制可以有效地减少整体时延，且使边缘节点之间达到负载均衡状态。Zhang 等人[17]为了满足任务的敏感延迟要求、资源的合理分配要求、资源交易的可靠性要求，提出了以智能合约的形式在区块链上实现的任务卸载与资源分配算法。仿真实验表明，此算法具有优于传统算法的用户满意度与系统实用性。

张帆等人[18]提出了包含接入点AP，边缘服务器，层调度，与层控制器的云边协同框架，将时延敏感型任务分配至合理的边缘节点。简琤峰等人[19]针对优化边缘服务器各项资源，提出了添加二维扰动因子与混沌因子的改进蝙蝠群算法，提高了跳出局部最优的能力。查满霞等人[20]将调度任务划分为独立任务与单个DAG任务和多个DAG任务两大类，将任务抽象为马尔科夫(Markov)模型，并分别提出了近端策略优化与在线DAG调度算法。其缺点在于任务调度策略不适用于具有依赖关系的任务。

综上所述，针对延迟敏感的应用场景，降低时延仍然是需要重点关注的问题，表1对以性能为目标优化的任务调度策略进行了总结。

3.2 基于优化能耗的任务调度

终端设备的能耗过高会造成资源浪费。表2对以降低能耗为目标的任务调度算法进行了总结。

赵辉等人[21]针对边缘计算平台存在未知性能的计算节点，构建任务调度模型，将未知性能节点假设为已知性能节点，建立其之间的动态映射，通过感知已知与未知节点之间的任务队列长度来动态调整映射关系，提出了一种基于动态映射的半线上任务调度算法。最后通过CloudSim平台实验表明，此算法使系统资源利用率提高且降低了平台的能耗。

表1 性能优化任务调度策略

马璐等人[22]为了解决6G在网络架构方面所遇到的问题，引入“云-边-端”三层系统架构。并在此基础上将任务调度建模为计算资源约束下的系统最小化开销问题。设计了基于雅可比(Jacobi)交替方向乘子法的任务调度算法。仿真实验表明此任务调度算法可以降低成本，提高任务的执行效率。秦志威等人[23]在“云边端”三层框架的基础之上，首先对任务的优先级进行划分，再利用改进的粒子群算法寻找最优解。鲁厅厅等人[24]在物联网的环境下，为了使各个设备之间资源达到负载均衡状态，提出了基于近端策略优化(Proximal Policy Optimization，PPO)的实时调度算法。算法在稳定的基础上，最大程度上优化了时延与能耗。

表2 能耗优化任务调度策略

3.3 基于优化系统效用的任务调度

除了以时延和能耗为优化目标之外，研究人员还针对边缘节点之间的系统效用(主要包含边缘节点负载均衡、应对任务之间存在的严重的依赖关系、应对边缘节点故障等)展开研究。表3对以系统效用为优化的任务调度策略进行总结。张云飞等人[25]针对边缘云中各节点计算资源差距过大且负载不均等问题，通过设置启发式因子与更新信息素，利用蚁群算法(Ant Colony Optimization，ACO)来优化任务调度。模拟仿真表明此算法可以有效降低边缘云节点之间的负载不均衡问题。其缺点在于默认任务之间不存在依赖关系且每个任务的需求已知、不间断执行，具有较大的局限性。

陈乔鑫等人[26]在车联网的环境下，为了解决数据依赖、资源异构、传输时延等问题，提出了一种推理任务实时调度策略。其使用有向无环图来构建推理任务模型，其次运用深度Q学习算法(Deep Q-Learn，DQN)为任务选择合理的资源节点。实验表明其收敛性能得到了优化。蔡凌峰等人[27]在边缘节点故障的场景下，提出了一种依赖关系感知的任务重调度方法。对受故障的任务重新调度从而避免了任务失败。但是其未考虑时延约束，不适用于延迟敏感型任务。

表3 系统效用优化任务调度策略

4 总结与展望

合理的任务调度策略可以有效降低任务执行时延，减少能耗，使边缘服务器能够达到负载均衡状态，从而提高用户服务质量，提高资源利用率。本文聚焦于“云-边-端”协同三层架构模式，在此基础上将任务进行粒度划分，并针对不同的优化目标及适用场景，总结分析了研究人员提出的任务调度策略。

边缘计算任务调度的研究方向主要为使用优化的传统算法或使用启发式算法，并结合一定的应用场景，针对优化目标给出合理的任务调度策略。目前随着5G技术、区块链技术与人工智能的不断发展与完善，其均可以融入到边缘计算当中，构造出更加高效的调度策略。边缘计算的发展与新一代信息技术、互联网、大数据以及人工智能等发展高度耦合，今后可能从操作系统、算网融合、6G应用、新的应用场景开发运维、人工智能等方面有力地推动边缘计算的发展。