边缘环境下计算密集型任务调度研究综述

刘炎培，朱运静，宾艳茹，陈宁宁，王丽萍

郑州轻工业大学 计算机与通信工程学院，郑州 450001

根据最新的思科年度互联网报告显示，到2023年，5G将支持超过10%的全球移动网络连接，连接到IP网络的设备数量将是全球人口的三倍以上，平均5G速度将达到575 Mbit/s，比平均移动网络连接快13倍。凭借强大的功能，5G将为人工智能和新兴物联网应用提供更灵活的移动基础设施，如自动驾驶汽车、智慧城市、远程医疗和全景视频。为了不断发展5G无线技术并使网络传输具有超高数据速率，低延迟，低能耗，高品质质量体验和用户数据的安全性[1]。近年来，在实时应用和智能通信的愿景驱动下，集中式云计算向分布式边缘计算的范式转变。边缘计算的主要特性是将云服务拖向网络边缘，大幅减少延迟，同时提高网络和计算设备的资源利用率。边缘计算作为云计算的自然延伸，延续了各种研究挑战，也提出了不同的新问题需要解决。任务调度[2]是边缘计算的一个关键的环节，是任务经过优化后可以映射到合适的资源池上执行的一个过程，且调度算法策略旨在优化各种QoS参数，如成本、完工时间、可扩展性、可靠性、资源利用率以及能耗等性能指标。

由于边缘环境存在当用户数据请求过于频繁时，会导致网络卡顿和延迟，边缘调度技术是减少时延和视频传播任务的延迟敏感性的重要方法，所以边缘计算调度和分配技术作为移动边缘计算技术的热点，为5G发展的需求提供了可能。随着5G和边缘计算的结合满足了自动驾驶的需求，无论是在面对高性能计算的需求还是对计算密集型应用服务网络延迟的需求[3]，当用户发送大量的任务请求时，会给边缘端服务器带来巨大负担和能耗，车辆或路测单元使用边缘调度技术可以满足用户服务质量的需求，并且可以为车辆用户提供更好的服务质量体验。在边缘计算中，任务调度不仅影响用户的时间和成本，同时对边缘平台的性能起到很大的作用，因此实现高效的调度用户任务，成了边缘云研究领域的一个重要问题。边缘计算调度在物联网（IoT）中应用的场景：（1）人脸识别。由于目前现存的基于中心云人脸识别系统远离终端设备，并且大量图像数据会给云服务器带来高计算负载和低实时性的问题，于是边缘服务器可以对人脸进行实时性检测以及特征提取，并根据深度强化学习训练的中间结果对鲁棒的人脸特征进行快速处理和响应，对于无法处理的人脸识别任务，实施人脸识别任务调度算法。（2）车联网（internet of vehicles，IoV）。车联网环境中车载终端中的实时任务卸载到路边单元RSU使用调度技术，可以有效缓解车辆终端计算力低下、资源匮乏或者资源抢占等困境。（3）虚拟现实（virtual reality，VR）。目前已提出了构建云计算数据中心资源采样模型，并结合虚拟现实（VR）互动装置输出、转换、调度中心资源，提取中心资源的关联规则特征量，采用模糊聚类融合分析方法重构中心资源，建立虚拟化云计算数据中心资源的信息融合中心，使用分析方法实现对数据中心资源调度，可以实现虚拟化云计算数据中心资源实时节能调度。

任务调度在提高资源利用率和为用户提供优质服务方面发挥着重要作用，并且计算调度技术也成为边缘计算领域中的热门话题之一。一个好的任务调度策略可以灵活地适应边缘和云计算的动态环境，有效地减少用户提交任务所需的时间，提高资源利用效率。文献[4]研究了节点到节点/设备到设备（N2N/D2D）通信和任务调度的备用频谱，并比较了不同的网络参数和服务条件下的性能增益。文献[5]研究了将任务卸载到网络边缘的设备，边缘计算减少了服务延迟和带宽消耗，于是通过任务调度提升网络的性能。并比较了各种优化算法之间的能耗、成本和安全性方面。文献[6]研究了任务调度在移动云计算平台面临着设备移动性、工作负载分布、连接选择、成本估算和能量限制等影响因素。虽然上述研究取得了一定成果，到目前为止，由于边缘服务器上任务调度的资源分配不合理不仅会降低任务的计算效率增加计算时间，还会造成任务排队产生排队时延，由一些服务器资源枯竭进而导致其他服务器资源浪费的情况，从而使得边缘网络出现整体资源利用率不高、性能差等问题。为了克服这些问题，本文通过对目前最新任务调度方法进行系统的分析、整理和归纳，总结当前基于SDN的MEC框架和计算密集型应用任务调度执行过程，以及应用场景进行了详细的论述，通过考虑时间和成本、能耗和资源利用率、负载均衡和吞吐量对当前调度策略技术的研究成果进行分析、对比和总结，并介绍了适合5G环境下最新的计算密集型调度优化策略。最后讨论了边缘调度策略的研究趋势。

1 边缘环境下计算密集型任务调度概述

欧洲电信标准协会（European Telecommunications Standards Institute，ETSI）通过将边缘计算融合到移动网络的架构，提出了移动边缘计算[6]。边缘计算的主要特点是：（1）支持异构资源集；（2）地理分布；（3）支持时延敏感的应用；（4）提供可靠的无线通信，支持计算密集型终端设备可移动；（5）以最小延迟的位置感知。调度技术应用于边缘云环境使得网络数据传输更加高效，本章主要介绍边缘云环境下的调度框架、执行过程、应用场景以及影响调度策略的性能指标。

1.1 计算密集型任务的分类

任务调度算法是云计算中的一个重要问题，因为它会影响边缘云的性能；按照文献[7]可以将任务划分为计算密集型[8]和数据密集型[9]。科学和工程领域的复杂模拟通常包含大量计算密集型的数值任务，这些任务占用了大量的求解时间，并且这类应用程序对CPU计算的需求不同，与问题实例相关的数据量无关。数据密集型任务会发出大量的数据I/O，因此数据I/O通常占主导地位，并分布在整个任务中。同时，计算密集型作业/任务只执行有限的数据I/O，但大部分时间花在计算上。在计算密集型应用中，有基于仿真的应用，其目的是最大化系统资源来处理用于仿真的大型计算[10]，并且典型的用法之一是运行参数扫描实验，其中研究模型的参数空间，以获得一般行为的概述。其中计算密集型和数据密集型任务的不同影响如表1所示。

表1 计算密集型和数据密集型任务的不同影响Table 1 Differential impact of compute-intensive and data-intensive tasks

对于本文主要研究计算密集型任务数据处理，在其基础上任务调度可分为以下几类：

（1）即时任务调度：当新任务到达时，它们将直接调度到VM。

（2）批量任务调度：任务在发送前分组为一个批次；这种类型也称为映射事件。

（3）静态任务调度：它基于系统全局状态的先验信息，不考虑虚拟机的当前状态，然后以类似的方式如循环和随机调度算法在所有虚拟机之间等效地划分所有流量。

（4）动态任务调度：考虑到虚拟机的当前状态，不需要系统全局状态的先验信息，并根据所有可用虚拟机的容量分配任务。

（5）抢占式任务调度：每个任务在执行过程中被中断，可以移动到另一个资源以完成执行。

（6）非抢占式任务调度：在完成已调度任务的执行之前，不会将VM重新分配给新任务。

1.2 计算密集型任务调度框架

边缘计算支持分布式架构，其中计算设备被放置在本地，并且分布在离最终用户更近的地方。边缘计算的主要利益相关者是边缘服务提供商、云服务提供商和最终用户。边缘框架与本地端设备之间的通信距离最小，可以最大限度地减少边缘服务提供商的延迟和能耗。根据文献[11-12]的研究，边缘计算由一组无处不在的去中心化边缘设备组成，这些设备可以使用不同的无线通信模式在本地处理和存储数据，而不需要第三方的干预。图1描述了边缘环境下计算密集型应用的任务调度的框架，其中三个部分组成了调度整个框架：云服务提供商（CSP）、边缘服务提供商（ESP）和用户设备。对资源有需求的用户设备可以用包含相关任务的请求来表示。假设一个分时系统，在任何时间段，一个用户都会带着包含在请求中的各种任务出现，并通过付费将该请求发送给ESP。用户的目标是减少响应和处理时间，以获得满意的任务结果。众所周知，边缘计算被认为是云和用户之间的枢纽，它是通过将计算传递到靠近这些用户的普及网络的边缘来提出的。一方面，每个边缘中心都配备了许多不同的边缘移动设备，即资源。另一方面，EP在日程安排中起着重要的作用。主要功能如下：首先，根据处理历史数据方面的预测，为未来需求储备资源。其次，以获取更多利润为动机，匹配任务和边缘移动设备，然后将这些任务尽可能分配给与不同边缘中心关联的相关边缘移动设备。最后，它将超出其能力的任务发送到云上进行处理，并为这项工作付费。相应地，云处理EP交付的任务并从中获利。

图1 边缘环境下计算密集型应用的任务调度框架Fig.1 Task scheduling framework for computing-intensive applications in edge environments

1.3 计算密集型任务调度的执行过程

当计算量和网络资源有限时，最大限度地利用资源变得至关重要，在用户移动过程中，进行任务调度，选择最优的边缘服务器为用户提供服务，从而实现MEC系统的最低能耗，移动边缘调度是减少时延和视频传播任务的延迟敏感性的重要方法，根据各种用户参数对任务进行调度，如到达时间、系统负载、执行时间和截止日期，在边缘环境中任务调度算法的目的是在用户和虚拟机之间，找到一个最优映射，以使在满足用户的需求前提下，提高边缘云的使用效率以及降低能耗。图2描述了边缘环境下计算密集型任务调度的执行过程。

图2 边缘环境下计算密集型任务调度的执行过程Fig.2 Execution process of computing-intensive task scheduling in edge environments

在该过程中假设有K个移动终端，每个移动终端上有一个具有一定优先级的待处理任务，即共有K个待处理的任务。用T={T1,T2,T3,…,Tn,…,Tk}表示K个待执行计算任务调度到边缘服务器端进行处理，要将K个任务分配给n个边缘资源节点，资源节点用S={S1,S2,S3,…,Sn}表示，当移动端发送任务请求，调度策略通过考虑QoS资源监控的信息，将任务分配给匹配的边缘端资源节点来完成任务调度。

1.4 计算密集型任务调度的应用场景

边缘计算调度的应用不仅可以克服现有主机网络的限制，而且在实现调度任务分配方面发挥了重要的作用。目前对绿色IoV的研究主要集中在电池供电的RSU或电动汽车的能量管理上。由于传感器和智能车辆的快速发展，车联网（IoV）正在成为智能交通系统的基础技术，要求提高道路车辆的机动性和安全性。图3描述了边缘环境下计算密集型任务调度的应用场景。

图3中，IoV支持各种通信模式，例如车辆到车辆（V2V）、车辆到基础设施（V2I）和车辆到传感器（V2S），车辆连接到匹配的MEC服务器的RSU，以执行实时或重要的计算任务，车辆和终端等服务用户能够从位于用户附近的基站（BS）的边缘计算服务器（ECS）访问计算和存储服务，当车辆用户发送任务由基站进行调度，调度算法决定将计算任务调度到基站节点端的服务队列或车辆的服务队列中，然后由边缘服务器对任务实施调度策略，最终返回到用户。通过将服务从核心网络推送到边缘网络，这大大减少了网络延迟。目前，现有的大多数工作仅仅考虑车辆之间的调度，而忽略了RSUs之间的对应关系。如何利用有限的RSU数量来应对不断增长的车辆交通需求是一个非常具有挑战性的问题。

图3 边缘环境下计算密集型任务调度的应用场景Fig.3 Application scenarios of computing-intensive task scheduling in edge environments

1.5 计算密集型任务调度的性能指标

边缘计算中调度的评价标准影响调度技术的设计和方法，大多数任务调度技术是多目标的，在边缘计算调度中时间和成本大多都是一起考虑的，为了达到更好的调度效能，需要依赖于时间、成本、可靠性、能耗、资源利用率以及负载均衡等不同的指标：

（1）时间：包括最大完成时间、总执行时间、截止时间以及等待时间。在边缘计算环境下任务调度中，其中完成时间是任务从提交到执行完成的整个调度时间；执行时间是指资源被分配到完成的时间；截止时间是指任务要求的最终完成时间，等待时间是任务执行开始到提交之间的时间。

（2）成本：任务执行产生的成本包括计算成本、数据传输成本以及用户为使用边缘计算平台向供应商所付出的费用。

（3）能耗：指应用程序在处理计算设备内的数据（计算能量）和通过可靠的网络传输数据（传输能量）期间消耗的能量。

（4）资源利用率：计算设备的资源利用率取决于重新调度和处理实时应用程序的资源数量，是指用户在进行边缘调度的过程所占用边缘环境中的CPU、存储、内存和应用各类的软硬件的资源利用率。

（5）负载均衡：是指用户请求的边缘任务在不同的虚拟机、虚拟机不同的节点上分配的调度。负载均衡不仅可以改善资源的利用率，还可以通过低载资源的合并以及迁移能够降低能耗。

（6）可靠性：是指任务执行的可靠性，确保在计划中选择的资源并可能会完成为其安排的任务。任务执行失败通常通过重新启动和复制任务来处理。任务的可靠性执行可以降低时间和计算资源的浪费。

2 边缘计算环境下计算密集型任务调度技术现状

边缘计算调度策略的根本目的是提高资源的利用率，降低负载均衡以及能耗，进而提高用户体验。本文为了增加可读性、可靠性，根据优化目标的不同，将目前的调度优化策略分为：时间和成本的优化调度策略、能耗和资源利用率的优化调度策略、负载均衡和吞吐量的优化调度策略；这些将有助于边缘计算调度领域的研究人员探索高效的调度策略，表2总结了近几年来相关的边缘环境下计算密集型任务调度方案。

表2 边缘环境下计算密集型任务调度方案总结Table 2 Summary of computing-intensive task scheduling in edge environments

2.1 时间和成本的优化调度策略

在网络的边缘部署使用合适的调度策略不仅可以降低云边端的计算复杂度，并且可以延长用户主机设备的寿命。其中，时间和成本是影响用户体验的关键指标之一，因此综合考虑时间和成本是设计高效调度策略的重要参考因素。

针对如何提高在作业分配过程中数据的处理能力，文献[13]总体技术路线是基于成本的作业调度。该方法的优点是可以缩短提交作业的相应时间，并考虑了抖动因素以改善QoS和网络状态，缺点是在计算成本的过程中忽略了由等待所产生的成本以及数据返回产生的成本。文献[14]使用了新的动态调度技术，该技术随着时间的推移管理云资源，以处理工作流中的数据速度变化，同时保持用户定义的实时数据分析要求并最小化执行成本，减少执行时间。

针对如何解决多QoS的优化约束问题，文献[15]基于混合蜘蛛猴优化算法解决任务调度问题。总体在满足预算和期限约束的同时，优化了完工时间和成本。文献[16]利用遗传算法（genetic algorithm，GA）将异构任务调度到异构处理器上的调度策略，以减少总执行时间。文献[17]研究了在结合边缘处理和集中式云处理的云边协作架构适用于流媒体的放置缓存调度，并基于邻域搜索的缓存感知调度模型，如图4所示。具体执行流程为：首先，朴素贝叶斯理论将工作分为三类。其次，根据不同作业类型的操作，为节点分配不同的资源来执行不同的作业，并监控作业执行情况以调整资源。最后，采用缓存感知方法延迟调度作业，并将作业调度到满足缓存局部性的节点。根据邻域搜索结果，调度不满足节点局部性的作业在具有相似能力的节点上执行。该方法有效地减少内容传输延迟，缩短作业执行时间，提高云数据中心的处理能力。

图4 边缘环境下基于邻域搜索的缓存感知调度模型Fig.4 Cache-aware scheduling model based on neighborhood search in edge environment

针对多目标优化和工作流任务调度问题，文献[18]在云工作流应用中生成帕累托最优解的进化多目标优化算法，并将其用于多目标调度问题。该策略的优点在于根据混沌理论在云环境下通过贪婪算法和使用随机数来提高搜索性能，与其他算法相比，该算法具有更好的收敛性和更均匀的节间距离，并解决了原算法总是陷入局部最优的问题。文献[19]应用了基于模糊的任务调度，该方法的优势是在能量消耗方面优于微遗传算法，其最终的目标是在高负载条件下，在总执行时间、最大完工时间、不平衡度和安全价值等方面都优于其他同类调度方法。文献[20]定义了云边缘网络体系结构中任务调度的最小化延迟优化问题。将该问题描述为一个马尔可夫决策过程，通过无模型DRL算法来训练系统的状态，以解决云服务器存在长延迟和巨大的带宽需求问题。在该过程中，各优化目标被量化为：

2.2 能耗和资源利用率的优化调度策略

在网络的边缘部署调度不仅可以降低服务器端的能耗和并且还可以降低服务器资源枯竭和其他服务器浪费的情况。能源和资源利用率是影响用户体验的关键指标之一，因此综合考虑能耗和资源利用率是设计高效调度策略的重要参考因素。

针对克服调度优化问题以获取更高的资源利用率为目标，文献[21]对工作流调度问题进行了研究，提出了基于服务质量的资源分配和调度，利用基于群体的蚁群优化提供更可预测的结果。实验结果已经与其他策略进行了比较，结果表明该策略较其他算法策略在能耗和资源利率方面有所提高。文献[22]利用一种基于订单级需求的实时边缘调度模型，该模型考虑了订单的实时插入，在满足单个客户需求的同时实时插入到货单。所提策略在顾客满意度等订单级指标上具有显著优势，在资源利用率、能耗和完工时间等车间级指标上表现较好。文献[23]解决了以节能的方式在一组专用私有软件定义的广域网连接的数据中心上调度由数据驱动的工业工作流应用程序的问题，并同时管理云提供商收入的权衡。与基于成本的工作流调度方法相比，该文献提出的方法可以将工业工作流执行的绿色能源利用率提高3倍，并降低了能耗。

针对为给定的输入任务找到最优的资源，文献[24]引入了一种能量-最大完工时间多目标优化调度策略，目的是找到这些冲突的目标之间的折衷降低能源消耗和最大完工时间，它分两个阶段工作。首先，引入加权双目标代价函数。其次，通过应用期限约束的频率缩放来进一步减少能源消耗。建议的工作确保在建议的期限内完成工作流应用，同时也减少了能源消耗。文献[25]通过考虑多云的完工时间、负载均衡、资源利用率和成本等参数来改善任务调度行为。该方法结合了遗传算法和电搜索算法的优点。遗传算法提供最佳局部最优解，而电搜索算法提供最佳全局最优解。由实验结果来看，该算法优于混合粒子群优化算法、遗传算法、专家系统和蚁群算法等现有调度算法。

2.3 负载均衡和吞吐量的优化调度策略

边缘计算环境下边缘节点间资源差距过大且任务分配的负载不均衡，平衡负载可以降低总体能耗和防止某个边缘云超载，负载均衡和吞吐量是影响用户体验的关键指标之一，因此综合考虑负载均衡和吞吐量是设计高效调度策略的重要参考因素。

为了克服现有关于负载均衡的困难，优化动态资源调度。在文献[26]中利用基于端口的源路由地址的特性和胖树拓扑的规律性，设计了一种极其简单的路由机制，该方法适用于云数据中心网络和边缘计算，可以降低交换机的复杂度和整个网络的功耗，显著减少了完成时间，提高了平均吞吐量，并在服务器上实现负载均衡。文献[27]通过基站学习和交换信息获得的环境知识用于分布式资源块分配。该资源分配方案可以在较短的学习时间内获得最优的资源分配策略，并可以根据不同服务的延迟要求随时终止学习过程。与传统的资源分配方案相比，它能有效提高系统吞吐量。文献[28]使用量子启发的二进制混沌群算法来调度多处理器系统中的任务，以实现负载的均匀分散。充分的负载平衡和高效的调度机制增强了整体性能，并显著提高了服务质量指标，如计算系统的吞吐量、资源利用率、可扩展性、可靠性和响应时间，较鸟群优化、改进粒子群优化、JAYA和标准SSA（二进制数相乘）算法在性能方面有所提高。文献[29]基于粒子群优化的多目标调度，用于对大量任务进行优化分配。该算法旨在通过调度任务来减少每个粒子上的剩余工作量。在利用粒子群优化（particle swarm optimization，PSO）调度算法得到每个集群的问题答案之后，IPSO尝试调整资源上的负载。该算法减少了所有任务的完成时间，同时还平衡了框架负载，提高了整个云阶段的详尽度。

针对考虑请求调度的资源故障率问题，以便为所请求的服务提供可靠性，文献[30]引入了一种可靠的负载平衡服务调度方法，用于将客户的请求分配给云-雾环境的资源。通过将请求任务按实时性、重要性和时效性进行分类，在分配请求时考虑了资源之间的负载均衡，该方法可以将客户的请求任务分布在不同的计算资源上，具有高度的负载平衡。文献[31]基于深度强化学习（DRL）的服务水平协议约束下的动态负载平衡任务调度策略。使用DRL方法为任务选择合适的虚拟机，然后确定在选定的虚拟机上执行任务是否违反服务级别协议。如果违反了服务水平协议，任务将被拒绝，并反馈DRL训练的负面奖励；否则，接收并执行任务，并在任务执行后根据虚拟机负载的平衡反馈奖励。该策略在平衡虚拟机负载、降低任务拒绝率、提高系统吞吐量，提高云计算服务整体水平方面表现最佳。

从以上优化目标的角度出发，通过对目前边缘计算调度的分析和对比可知，将用户请求的任务调度到边缘服务器端处理确实在一定程度上提高了网络的性能和用户体验。但是目前仍然面临一系列的问题：如用户请求任务的多样性对调度策略有严重影响，如何准确预测用户的任务分类来最大化调度的资源利用率是一项复杂的任务；此外，用户不愿为了提高网络性能而消耗他们的时间和成本，所以用户在云端执行任务调度，以利用D2D通信是困难的；因为对于调度任务的分类和特性难以确定，所以设计的调度策略应该能够准确观察用户任务的特性、用户任务请求的方式、移动性、网络状态。因此，综合考虑边缘设备的移动性、异构边缘计算服务器的资源以及任务的计算需求，可以利用深度强化学习以及来跨层的方式解决调度任务处理速度，缩短任务超时时间。因为深度学习具有生物相关性和学习自主性，可以通过尝试错误将状态和动作与环境进行最佳匹配，以获得最大的资源利用率，且未来边缘计算调度技术希望利用智能的调度机制来最大限度地提高网络性能。

3 边缘计算环境下面向5G的计算密集型任务调度的发展趋势

第1章和第2章所描述的调度技术主要都是应用在4G传统的MEC网络。然而5G的应用背景下，通过在云上部署强大的计算和存储能力，可以有效地处理物联网计算密集型应用产生的数据，从而确保物联网应用向最终用户提供有效的服务。本章将分析边缘环境下面向计算密集型应用的任务调度技术策略，目前正在发展的几个热点方向，如边缘环境下基于SND下的调度策略，基于深度强化学习的调度策略，以及在车联网环境中的跨层调度策略的实施。

3.1 面向5G边缘环境下基于SDN的计算密集型数据包调度策略

边缘计算通过提供分布式处理能力来支持移动计算和物联网技术分布式开放架构[32]。为了支持高扩展性、超低延迟、高吞吐量和可靠的数据传输，软件定义网络（SDN）被认为是合适的解决方案之一，这使得边缘计算更加可行[33]。考虑到SDN技术通过将网络解耦为控制平面和数据平面来实现动态、编程高效的网络配置的特点，能够提高边缘服务器的性能和低延迟。SDN的这些特性和边缘计算一起使用，可以实现各种附加功能以及性能的提升。使用OpenFlow协议，SDN控制器可以控制底层网络组件[34-35]。图5描述了边缘环境下基于SDN的边缘计算架构，其中架构中主要包括网络应用、MEC系统水平、MEC主机水平、网络层。在SDN支持的 边缘架构中，MECs部署在边缘接入网中，减少了接入终端与计算资源和网络资源的距离，增加了终端对资源的访问[36-37]。

图5 边缘环境下基于SDN的边缘计算架构Fig.5 SDN-based edge computing architecture in edge environment

图6描述了基于SDN的计算密集型数据包调度方案。当边缘中心接收到紧急数据，它会像其他正常数据包一样遵循一般的OpenFlow操作。边缘中心将紧急数据以地址为源地址打包，发送到目的地。同时发送packet-in消息，通知控制器发生紧急报文，控制器收到入包消息后，检查并发送一个出包消息。接收分组输出消息的边缘中心更改或添加接收到的消息的流表，并传送到合适的输出端口。在基于OpenFlow的功能之后，在边缘中心检查数据，来确定是将入队的数据转移到优先级队列还是普通队列。在工业物联网环境产生的数据中，假设应急数据只用EQ处理，其他所有情况如周期性传感数据都用NQ处理。传入数据包由M/G/1排队模型处理，调度模型侧重于网络延迟的排队延迟，该方案从数据包的角度出发，通过分析用户的数据包的紧急性优化调度策略，并将SDN合并到MEC边缘中，以最大化命中率，最小化传输能耗为优化目标。

图6 基于SDN的计算密集型数据包调度方案Fig.6 Computing-intensive packet scheduling scheme based on SDN

图7描述了不同调度策略下的任务平均时间响应情况，在单个服务器中，资源利率ρ表示为ρ=λ×c×Sˉ，λ表示为，其中p为任务的优先级，Sˉ指处理一个数据包所需的服务时间，在计算平均等待时间时，将到达率λ的方差设为0.01～0.09，从图中可以看出，当系统利用率为低情况时，可以更快地处理应急数据，反之处理应急数据的时间更长。基于SDN的边缘调度策略具有的性能优于现有的基于优先级（FCFS）的调度方法。SDN下的任务调度策略不同之处在于：不同于现有的基于优先级的技术，提出的方案使用两个队列而不是多个队列来管理边缘计算服务器的资源；为了减少传输延迟，边缘计算服务器和边缘计算主机采用SDN概念。

图7 不同调度策略下的任务平均时间响应情况Fig.7 Average time response of tasks under different scheduling strategies

3.2 基于深度强化学习的计算密集型任务调度策略

为了解决边缘环境中任务如何进行调度的问题，以及用户请求任务密集和资源的合理分配，启发式算法目前在任务调度问题方面应用研究广泛，基本原型如蚁群算法（ant colony optimization，ACO）、粒子群优化（particle swarm optimization，PSO）、遗传算法（genetic algorithm，GA）等。这类算法可在约束条件下寻找到符合条件的可行解，但是由于无法预计可行解与最优解之间的偏差，收敛速度比较慢，在求解过程中往往陷入局部最优解，较难满足低时延的任务要求。因此在此背景下，利用强化学习[38]方法优秀的决策能力来解决复杂边缘环境中的调度问题，通过不断矫正可行解和更优解的偏差，可以加快收敛速度。但是由于自身的局限性，它无法处理高维和连续性问题。深度学习方法侧重于感知和输入的表达，善于发现数据的特征。由于深度学习可以弥补强化学习的缺点，因此深度强化学习（deep reinforcement learning，DRL）利用深度神经网络捕捉环境特征的能力和RL的决策能力来解决复杂的系统控制问题[39]，并且可以使用边缘节点作为智能代理学习调度策略，不需要全局有关环境的信息。

边缘云任务调度结合深度强化学习的内容，并按照任务调度模型构建合理的部署的方法，相比于传统的方法[40]更有优势。边缘环境下基于深度强化学习的任务调度模型如图8所示，当用户发送视频任务请求时，调度决策器根据目前的边缘计算系统环境状态即时回报的结果，使用强化学习模型通过大量的学习训练，使得调度决策器按照经验策略将视频任务接入到最合适的服务器。并使用深度卷积神经网络进行确定性策略梯度进行神经网络训练，最后根据服务器的负载状态信息，通过视频的迁移策略，来执行新的任务请求。

图8 边缘环境下基于深度强化学习的任务调度模型Fig.8 Task scheduling model based on deep reinforcement learning in edge environments

强化学习主要用到的是行为策略选择，定义函数μ，通过使用卷积神经网络对μ函数进行模拟，该网络即为策略网络，如果都按照策略μ选择动作，能够产生Q值，该值为期望值。通过使用卷积神经网络对Q函数进行模拟，在训练的过程中，采用目标网络方法，建立策略网络和Q网络来计算目标值，然后通过比例缓慢更新网络。通过该学习方法，使学习过程更加稳定，收敛更有保障。图9描述了不同负载情况下的任务处理时间以及算法的收敛性比较。

图9 不同策略任务处理时间和算法收敛性比较Fig.9 Comparison of processing time and algorithm convergence of different strategy tasks

从图9可以看出其他算法与深度强化学习调度策略的运行时间，无论是低负载还是高负载，深度学习算法的运行时间均优于DTAMS（dynamic threshold allocated migration strategy，DTAMS）以及PSO算法，对于平均运行时间缩短了54.54%。这是因为在用户请求访问的过程中，需要通过DTAMS算法不断更新会话分配阈值，计算量大。为了找到最优解，采用的深度强化学习方法只需要通过训练好的策略网络进行调度决策，计算复杂度较低，提高了调度效率。几种算法的收敛曲线如图9（b）所示。深度强化学习算法以比其他两种算法更快的速度实现了最优策略。此外，随着迭代时间步长的增加，该算法比其他算法有更高的回报，这表明该算法是有优势的。

3.3 计算资源协同的跨层任务调度策略

车联网（internet of vehicles，IoV）是物联网在汽车行业的典型应用，被认为是一种具有巨大潜力的下一代智能交通系统，由于每个边缘节点的计算和存储资源有限，以及物联网设备产生的数据规模庞大，即使在网络边缘节点之间实施资源调度，也无法满足物联网的计算需求。因此，有必要实施跨层资源调度（cross-layer task scheduling，CLTS），利用云中的资源来补充边缘节点的需求，有效解决边缘计算能力不足的问题。跨层资源调度方法[41]，可以实现物联网应用完成时间、资源利用率和能耗的联合优化。基于特征分析的结果，设计了一个新的跨层云计算系统多计算机任务调度框架，该框架具有动态定制的能力，通过该调度策略，跨层云计算系统中的计算机任务可以动态选择合适的算法，更有效地利用资源。图10描述了5G边缘环境下计算资源协同的跨层任务调度过程，具体步骤为：

图10 5G边缘环境下计算资源协同的跨层任务调度Fig.10 Cross-layer task scheduling of computing resource coordination in 5G edge environment

步骤1将不同物联网服务和应用的需求分解为不同的计算机任务类型，其中任务之间的关系由有向图描述。

步骤2任务分析器分析计算机任务的特征，并将各种标签赋予它们，包括任务调度目标、任务类型等。

步骤3任务分析器将任务快照分发给调度管理目标（SMO）分析器和任务调度器。此外，任务也被分配到任务调度器。

步骤4 SMO分析器可以区分每个任务目标之间的差异。调度管理目标分析器决策可以从任务性质、资源状态和系统层次结构三个方面进行推导。调度管理目标分析器创建相应的目标控制器窗体。目标控制器根据目标控制器窗体从目标池中选择目标。

步骤5目标控制器监控任务调度器，以确保每个任务的输出都是可接受的。

步骤6任务调度器使用算法池中的算法执行算法功能。然后，它将来自资源监视器的信息和相关算法的结果发送给资源调度器。

步骤7资源调度器根据任务调度器的算法结果为这些任务分配资源。

其中通过考虑完成时间、资源利用率和能耗的联合优化指标模型，因此，任务的完成时间分为任务转移时间DTm、任务完成时间TEm和结果返回时间DFm，由TCm=DTm+TEm+DFm表示。利用一系列方法推导出边缘节点的资源利用率AU。因此，综合要解决的问题定义为：

将θ(tnm)表示为一个二元变量，旨在估计tnm是否部署在enn上。所有边缘节点的能量消耗通过以下公式计算：ES=BCS+FCS+NCS,BCS代表边缘节点的基本运行能耗，FCS代表满载VMs的能耗，NCS代表空载VMs的能耗。图11描述了不同策略在不同任务数量下的性能，从中可以看出跨层资源调度（CLTS）相较于PSO和LC（least-connection scheduling）在任务数量大的情况下平均作业完成时间和平均消耗总能耗最优，在处理大量任务的作业时跨层资源调度相比较PSO和LC算法具有一定的优势。

图11 不同策略在不同任务数量下的性能指标比较Fig.11 Performance comparison of different strategies under different number of tasks

4 问题与挑战

4.1 容错调度机制

由于移动用户的移动性和复杂的云环境，在移动应用的执行过程中可能会出现故障和不确定性。在执行过程中，可能会违反资源和应用程序之间的契约。因此，容错动态调度对于在线修改是必要的，以处理执行过程中的故障和不确定性，特别是在边缘计算环境中。在此基础上，一种基于分层移动边缘云架构的容错动态调度方法被研究。它旨在为移动应用程序执行期间提供动态和优化的调度策略。容错调度已经在网格、多处理器系统和一般云中进行了研究。移动云环境下的容错调度问题很少受到关注。在这些容错技术中，重叠技术是最流行的一种。此外，还有两个重叠的模型：主备份（表示为PB）模型和备份（表示为BB）模型。在PB模型中，允许主拷贝与其他后拷贝重叠。在BB模式中，允许不同的备份副本相互重叠[42]。除了重叠技术，还有其他容错调度技术。文献[43]针对异构分布式嵌入式系统上的可靠并行应用，提出了两种节能容错调度算法。通过结合重提交和复制技术，文献[44]提出了一种容错工作流调度方法，其中提出了一种在线预留调整机制来调整容错策略和一些未执行任务的子线索。文献[45]使用一种不确定感知的容错调度方法来处理执行过程中的不确定性，从而纠正延迟。文献[46]研究了云计算中期限约束任务调度容错策略的建模与分析。由于，用户请求的多样性可能需要不同的资源类型，例如VM、带宽和存储。因此，保持动态制定容错策略的能力至关重要，可用于控制任务的容错模式（主动或被动），从而满足云应用的可靠性和实时性要求。边缘云应用的容错过程可能涉及多个资源，资源调度的并发性和不确定性将增加模型验证的复杂性。很难证明所提出的方法能够提供关于容错过程行为的模型的可靠性和完整性检查。并且，边缘云计算的故障非常复杂，相关故障可能满足概率分布[47]。此外，如何提供能够满足所需QoS的容错调度，对于边缘云应用程序也是一个具有挑战性的问题。

4.2 动态微服务调度

为边缘计算平台设计一种高效、最优的动态微服务调度机制是一项具有挑战性的工作，因为每个微服务都有异构的资源需求来执行边缘用户的可用任务。除此之外，每个边缘用户都有严格的延迟要求，以从微服务获取可执行结果。在边缘平台中，边缘服务器启动多个微服务以满足边缘用户的需求。于是动态微服务调度被研究，在微服务之间调度任务，最大化网络吞吐量和QoS[48]。调度框架应该考虑需要执行的可用任务的数量，动态地将微服务从顶部队列移至底部队列。关键的微服务被认为是在顶级队列中执行的，因此它应该比正常的微服务具有更高的优先级，动态微服务调度框架的主要目标是最小化平均服务质量，需要优化服务质量，以应对底层网络条件和基础设施的突然变化。因此，如此快速的增长和发展导致了面向微服务的边缘计算平台的出现[49-52]。并且在微服务之间分配公平的资源，可以提高网络中的资源利用率。微服务的最新进展，文献[53]中的微服务多样性的服务器优化方案，试图找出最佳卸载解决方案，以最大限度地减少总体延迟。文献[54]设计了一种异构云边缘环境下的微服务调度模型，其新颖之处在于面向微服务的方法。文献[55]设计了基于微服务的三层性能模型应用程序，制定基于微服务的应用程序工作流调度问题。文献[56]基于模型的强化学习方案，用于科学工作流上的微服务资源分配。文献[57]应用了微服务的服务布局方案，并设计了一种自动扩展资源的算法。文献[58]在基于强化学习的边缘平台延迟感知微服务协调方案。以上文献对比之后发现，微服务调度框架在总网络延迟、平均价格、满意度、能耗率、故障率和网络吞吐量方面显著提高了性能指标。但是，其缺点是如何设计高效并且最优的动态服务调度机制是一个难点。

4.3 人群感知调度

人群感知有效地解决了大多数数据驱动应用面临的海量数据采集困境。移动人群感知通过无处不在的智能终端和网络接入，将感知任务从集中式平台跨时空维度迁移到分布式计算终端[59]，为大规模高精度实时感知问题提供了新思路[60]。由于任务调度过程中需要考虑数据的冗余性和协同性，并且网络环境的不确定性、用户的多样性、任务需求的多样性等因素会严重影响感知。因此，当传感器分配的任务不能满足不同任务的质量要求时，移动人群感知应具有良好的适应性，以便快速适应各种异构物理传感器的部署[61]。文献[62]构建了一个基于摄影的移动人群感知系统。在选择参与者时，参与者与监控对象之间的距离是影响任务分配的主要因素之一，因为道路上的车辆需要及时跟踪。文献[63]利用总线载波覆盖范围大和传感器节点自主聚合的优势进行任务分配，并通过实验验证了分配的准确性。文献[64]提出了一种新的任务分配框架，通过将现有的任务序列与用户的移动规律尽可能地对齐。将传统的任务分配问题转化为满足资源效率和感知质量的模式匹配问题。文献[65]是在基于任务异质性兴趣点（如不同的空间-时间需求）的移动性预测模型。它获得传感器完成任务的可能性。实验结果表明，该框架具有较好的效率。文献[66]对任务的地理位置进行集群，将一组传感器分配给一组任务，同时，最大限度地提高了任务的服务质量，缩短了完成任务的时间。目前，对不同阶段的响应时延和运行成本进行了深入分析，并设计了分阶段调度算法，共同优化总时延和成本。在混合人群感知系统中[67]，有多种类型的资源可用于执行人群感测任务，例如像云服务器这样的云资源，边缘设备和边缘服务器这样的边缘资源。最重要的问题是找到一种合适的方法在这些资源中安排任务。尽管有工作[68]已经探索了面向边缘计算的任务卸载，但是很少有工作能够直接应用于解决人群感知场景中的任务调度问题。当人群感知系统中处理任务调度时，有三个主要挑战：（1）与为特定应用目的而设置的边缘服务器不同，边缘设备通常由个人拥有，并且这些专用设备不专用于执行传感任务。（2）在将结果返回到云中之前，需要在边缘设备和边缘服务器上执行检测任务。这种执行逻辑在边缘使能的人群感知系统中是独特的，其中两种类型的资源上的任务调度是高度耦合的。（3）此外，大多数人群感应应用程序必须循环执行任务。任务调度的长期目标使得这个问题更具挑战性。

4.4 安全和隐私

与传统云计算相比，边缘节点更接近用户设备，并且边缘计算可以提供更好的隐私保护措施。传统的云调度策略中，数据的安全可以通过加密以及用户和调度节点的认证来保证。隐私保护和数据安全是边缘云工作流调度中需要解决的重要问题。许多黑客试图在用户中心或者边缘云卸载和处理任务时中断或窃取数据。安全和隐私是一套基于控制的技术和策略，旨在保护敏感信息、数据、应用程序和基础架构[69]。由于分布式环境中的资源虚拟化和多样化；在边缘云计算中，安全成为一个复杂的过程。因此，资源监控、资源管理和资源安全已经成为云边计算领域的突出问题。有研究人员采用离散PSO方法来解决安全威胁对工作流调度的影响[70]，在这种方法中，使用云模型来量化任务和虚拟机资源的安全性。此外，一般通过度量安全云的相似度来估计用户对虚拟资源任务分配过程的安全性满意度。同样，调度策略也可以通过某种方式来保护提交的应用程序的机密和私有信息[71]。文献[72]考虑移动边缘计算环境下位置隐私保护的车联网计算资源协同调度策略，以用来保护车辆用户位置隐私泄露的问题。在文献[73]应用多目标隐私感知工作流调度，是为了解决数据隐私保护约束下调度工作流，同时最小化云上大数据应用的执行时间和成本。文献[74]用于物联网任务调度的隐私体系结构，并在此基础上提出了一种多目标算法，以最小化服务时间和服务成本。以上文献综合考虑了调度过程中的安全问题，但是在将来仍然需要研究移动设备的调度工作流任务所导致的额外延迟的安全问题。

5 结束语

为了全面地了解边缘调度技术，本文重点对边缘计算调度框架、执行过程和评价性能指标进行相关描述，对最新的任务调度策略以不同性能目标分类并进行了分析和总结。通过对比不同移动边缘调度策略，对面向5G环境下边缘调度技术进行研究，分析5G环境下SDN支持的边缘计算架构并提出了面向5G环境下计算密集型任务调度优化策略，研究了基于深度强化学习的计算密集型任务调度策略以及基于5G IoV计算资源协同的跨层任务调度策略。最后，根据本文调查的调度方案，总结出了边缘调度策略的研究挑战。目前边缘计算研究的重点是根据QoS需求如何将请求任务和协同资源实现最优匹配，这是实现边缘计算技术快速发展的关键点之一。通过该综述研究的领域和方法，总结出该边缘计算调度领域的研究思路，从而为相关领域的研究人员提供参考和帮助。