边缘计算中基于节点服务能力评价的多层级任务调度方法研究

陈 顺，刘 刚，熊 原

国家批准第五代移动通信网络（5G）正式商用更加速了万物互联、智慧互联、实时响应时代的到来。随着这些技术的日渐成熟，网联的终端设备不断增多，需要处理的数据也呈指数级增长趋势。同时，终端用户也要求信息服务的质量越来越高，响应时间越来越短。这些新趋势给传统的云计算架构带来了极大的挑战。在云计算模式下，由于应用终端的计算能力和资源有限，需要将数据上传到云中心去处理，但这些云中心与终端之间的距离往往较远，用户请求服务的时候往往得不到及时的响应，同时也极大的增加了云中心和网络负载的压力。边缘计算正是在此背景下应运而生。

1 边缘计算概述

边缘计算是指在云中心和终端设备之间，更靠近用户的一侧设置一些边缘服务节点来替代云中心的功能,由这些边缘节点来直接处理终端产生的任务，提供相应的服务。这种方式相对于将任务提交到远端的云中心处理，产生的传输时延更小，因此在很大程度上能提高任务处理的及时性。相较传统的云计算，边缘计算的优势主要体现在以下几点[1]：

1）隔离性：边缘服务节点一般由位于本地的服务器集群组成，在运行时可以与其他网络隔离，访问本地资源速度更快。

2）低延迟：由于边缘服务节点更靠近终端设备，因此终端与服务端的通信延迟大大缩小，可带来更好的用户体验，也减小了线网数据，缓解了通信拥塞。

3）位置感知：当边缘网络为无线网络时，无论是Wi-Fi、蓝牙或者蜂窝网络，本地服务都可以利用低级别的信令信息来确定每个连接设备的位置。

2 任务调度方法的研究现状

边缘计算理论的出现，解决了计算密集型与时延敏感性的任务对计算资源与响应时间两方面的要求。但边缘服务节点自身的资源相对于云中心是有限的,而且各边缘服务节点之间的计算和存储资源也不尽相同，多并发任务之间还存在资源竞争。因此边缘计算中的任务调度方法具有举足轻重的作用。任务调度就是使边缘服务节点用自身有限的资源来处理更多的任务，又要保证用户的服务体验。

目前,边缘计算环境下的调度问题主要围绕以下几方面来研究：从边缘节点的体系结构考虑任务调度策略，如Liang T，Li Y，Gao W 等[2]提出了一种层次边缘云的结构，可以在任务高峰时期平衡边缘节点的负载，提高任务处理的效率，但该方法忽略了实际应用中任务处理需求的动态性。Ha K,Pillai P,Richter W 等[3]提出了一种在相关终端设备控制下，快速有效地支持时间敏感性任务的边缘云结构，但该方法没有将资源开销纳入评价体系中。Su 等[4]使用了PSO-HH 算法来优化边缘云的结构参数来为任务设计一个自适应分配规则，但该算法会造成较长的运行时间，降低调度的实时性。有些学者从边缘服务节点的负载均衡角度来考虑调度策略，如Wang 等[5]使用JLGA 算法,不但缩短了各服务器处理任务的时间,而且提高了服务器的资源利用率，但该方法没有研究任务间的联系与调度的动态性。Li 等[6]基于博弈论的思想提出了一种在移动终端间（Ad-Hoc 组网）进行任务转移的策略，但未考虑任务优先级次序。有些学者从缩短任务的响应时间方面考虑调度策略，如Alicherry 等[7]提出了一种智能虚拟机布局来缩短数据传输时间，但这种布局需要随着网络和任务数量的动态变化及时调整，自适应性较差。

上述方法仅从某一个角度来考虑任务调度的研究，未能从全方位考虑各种任务调度的影响因素。在个别边缘环境中，节点之间的计算能力和计算资源差异较大，而且处于网络弱连接环境下，通信质量很不稳定。在这种情况下，如何综合多方面因素，使任务调度满足现实应用是一个非常重要的技术挑战。因此，本文提出了一种基于节点服务能力评价的多层级任务调度方法，从边缘节点的体系结构、负载均衡、网络质量等方面来综合评估任务完成效率，大大提升了边缘节点的处理能力。

3 基于节点服务能力评价的多层级任务调度方法

基于综合节点服务能力评价的多层级任务调度方法，是指将节点通信质量、节点运动状况、计算能力、节点负荷等因素统一纳入任务调度计算模型，将不同任务调度到最优的边缘信息服务节点上运行，确保服务整体响应时间最短，且各节点间负载均衡，满足边缘受限环境下的任务快速调度的需要。本文将从节点上下文、节点服务能力和节点选择算法3 个方面研究多层级任务调度算法。

1）把网络节点上下文构建为一个节点上下文元素的集合，被选择用于任务调度决策的节点上下文元素主要包括节点标识CitemI、节点负载系数CitemL、节点的通信质量CitemC。（1）节点负载系数CitemL 用节点中待执行的任务数来衡量；（2）节点的处理能力CitemP 用节点的CPU 的占用率来衡量，在边缘信息服务节点环境下，各个节点之间存在一定的异构性，各服务节点的处理能力有可能不同；（3）通信服务质量CitemC 包括传输延迟RTT(Round Trip Times)和网络传输丢包率PLR(Packet Loss Rate)，RTT 指从发起传输的节点到接收节点的网络传输延迟时间，网络传输丢包率PLR 指由于信道带宽有限及网络拥塞导致的发送数据包在到达接收端时产生包丢失的比例。

在边缘中心环境下，由于节点受网络环境的影响较大，因此在执行任务调度的时候需要考虑到节点的通信服务质量，因为它影响到了边缘中心和云中心的通讯交互能力以及对终端节点的服务响应能力。而丢包率在媒体服务中尤为重要，直接影响音视频媒体的服务质量，所以将节点的扩展了丢包率的通信服务质量纳入上下文元素中，对边缘计算中心下的任务调度决策发挥了重要的作用。

2）边缘节点服务能力评价方法，对本区域内所有节点做出综合服务能力评价，为任务调度做决策支撑。针对上述每项上下文元素，进一步转化，由上下文要素转化为调度决策因子，针对每个调度决策因子我们定义了一项有效权值，并建立以下公式进行服务质量Q 的计算：

Q=M’*k1+L*k2+C1*k3+C2*k4

M’=log(M)

M’为归一化的已分配的任务数量，代表边缘节点当前的负载状态；

L 为CPU 的当前占用率，代表边缘信息服务节点的处理能力；C1 为传输延迟RTT；C2 为通信丢包率PLR。k1、k2、k3、k4 为调度决策要素的加权值。因为任务数的量级以及处理器工作频率比其他的大，所以使用对数函数对它们做归一化处理。对于以上计算结果，本文创新性的定义了统一的QT作为阀值，当Q＜QT 时，该节点作为调度节点，将该节点加入可调度节点集合。

3）有中心网络和无中心网络的服务节点选择算法。（1）有中心网络。在有中心的网络中，采用上下文集中管理模式，由中心管理节点承担全局节点上下文信息的集中管理，当中心管理节点接收到调度任务时，中心管理节点会根据各边缘信息服务节点的上下文计算节点综合服务能力的Q 值评价，并基于最小Q 值原则找到相应的边缘节点，将任务下达到该节点。（2）无中心网络。将无中心的网络转化为准中心网络，即集群式区域管理，每个区域的边缘信息服务节点，纳入区域中心管理节点统一管理，区域中心管理节点作为准中心进行任务接入和调度。

当某个中心管理节点接收到任务调度请求时，该中心管理节点根据当前区域节点的上下文数据集，综合评价本区域的平均Q 值Qav，如下式所示：

Qav=Sum(Q0+…+Qi+…+Qn)/N

其中：Qi=Nodes 集合中第i 节点的Q 值。

被转移到的准中心管理节点一旦接收到任务调度申请，将在本区域内对所有边缘节点的综合服务能力进行Q 值计算并计算平均值Qav，用以评估本区域边缘节点的综合负载状况。如果当前区域的Qav 大于调度转移阀值Qtran，则随机选取S 个周边准中心候选节点做区域负载调查。区域负载调查的方法是发送负载查询消息到这S 个候选中心节点中的一个，并获取Qav。

当Qav＜Qtran 时，向其发送调度转移申请，并由该节点安排区域内调度，调度算法按照有中心的动态调度算法。

如果Qav＞Qtran，继续发送负载查询消息到下个候选节点。

当所有节点的Qav 均大于 Qtran，那么选取Qav 最小的那个区域向其发送调度转移申请。

采用这种算法可保证在整个边缘网络环境下，既能保持负载均衡，也能保证服务质量，任务总能找到接近最优处理能力的节点进行服务处理。

4 结语

本文分析了边缘计算环境中任务调度问题的起因,对现有的一些调度算法进行了充分的分析，针对存在问题提出了基于节点服务能力评价的多层级任务调度算法，并在湖南移动直播信息系统上进行了应用验证，运行效果良好。后续的研究工作主要考虑在边缘服务节点故障或网络连接断续的情况下，如何保证服务能够顺利迁移到正常节点上，并能恢复故障前或断连之前的状态。