面向边缘计算平台的半线上任务动态调度方法

赵 辉，冯南之，王 泉，万 波，王 静

(1.西安电子科技大学 计算机科学与技术学院，陕西 西安 710071；2.陕西省智能人机交互与可穿戴技术重点实验室，陕西 西安 710071)

近年来，在云计算的发展与普及基础之上，由于边缘计算将处理过程先放在边缘计算节点完成，然后将处理结果传给云端，可以大大提升处理效率，减轻云端的负荷，因此，边缘计算广泛应用于具有实时性、安全与隐私保护等需求的领域，如物联网、智慧交通、智慧城市等。

边缘计算，尤其是移动边缘计算，在能效方面存在很大挑战。针对该挑战，许多研究尝试通过合理的任务调度策略来尽可能地利用系统资源、降低功耗。一般地，任务调度模式可分为线上或线下调度[1-4]。前者是指所有任务只有在被执行后才能得到它们的处理时间；后者则是处理器的速度和作业长度提前已知。然而实际应用中，由于网络路由不稳定、隐私保护等条件限制，人们通常只能获取边缘计算平台中部分节点的性能，存在部分节点性能未知的情况。此时，线上或线下的调度算法就无法有效地感知系统资源，可能导致任务执行时间或传输时间过长，不但降低效率，还会使边缘计算平台高能耗的问题更加突出。

当边缘计算平台中存在部分已知性能节点和部分未知性能节点时，这样的任务调度方法称为半线上任务调度方法。半线上任务调度模型可以看作是很多实际系统的抽象，例如对于单个本地设备来说，自身的多个CPU核可被看作已知性能的计算节点，而远端或是云端的服务器可以被视为是未知性能的计算节点；在涉及隐私保护的云存储中，未知性能节点可以是用来加密重要数据的私有云；在云计算中，未知性能节点可以是弹性云服务器或者共享虚拟机。但是，目前有关半线上任务调度的研究很少，甚至对半线上也没有统一的定义。文献[5]考虑了半在线调度时服务器之间通信时间，根据通信延迟与远程处理器的速度之间的大小关系分别设计了两种算法，但是讨论的情景是只有一台本地处理器和一台未知远程处理器，并且通信延迟和处理速度的关系在现实各种情况下很难是固定的。文献[6]还考虑将任务分配给m+m′个处理器来最小化完成时间，m是指已知速度的处理单元，m′是指未知速度的处理单元，当任务的处理时间为长尾分布时该文章提出的方法有显著的效果，但是该方法没有考虑任务在处理器之间的路由延迟，且存在再分配开销，没有充分利用到系统资源。文献[7]提出了用于多用户卸载的高效半在线算法，该算法分两种情况，分别对应已知服务器空闲时间和已知任务完成时间。文献[8]总结了半线上调度实际上是在线上调度算法的基础上添加了额外的已知条件，在不同工作中这个已知额外信息可以是最大作业大小、作业到达顺序或是执行总时间。在文献[9]的工作中这一额外信息指的是任务执行的总时间已知。在文中，这一额外信息是指任务长度已知，以及只有部分计算节点的处理速度和任务分配到该节点时的路由延迟已知。在这种条件下，需要研究如何有效地调度任务来优化系统的能耗。

因此，以能耗优化为目标，笔者提出了一种面向边缘计算平台的半线上任务动态调度方法。首先，边缘计算平台的能耗主要由3部分构成：任务被执行时的功耗、任务在路由传输时的功耗以及计算节点空闲时的能耗。半线上任务调度场景下，由于路由延迟的不确定性，可能导致数据传输时间过长，不仅消耗较多的传输能耗，还会降低整个系统的运行效率，从而加重能源开销。以往的研究很少考虑因路由延迟导致的任务传输能耗，而在边缘计算平台中，由路由延迟导致的能耗不可忽略。从边缘节点的处理速度、路由延迟和队列长度三个角度，引入边缘节点的任务执行能耗、任务传输能耗和空闲能耗，建立了能耗优化的边缘计算平台任务调度模型。该模型既能更客观地反映边缘计算平台的实际能耗，也是下一步任务调度算法的基础。其次，提出了一种基于动态映射的半线上任务调度算法。该算法分为两个步骤：① 假定未知节点的性能等于某个已知节点的性能，建立未知-已知节点之间的映射，再不断感知映射双方的任务队列长度来动态调整映射关系。其原理是对于性能相近的两个节点，调度算法大体上会分配类似的任务量，若一段时间后，它们的任务队列差异过大，则说明这两个节点的映射关系不合理，需要进行重新映射和调整；② 在未知-已知节点映射基础上，有效利用系统中已知节点性能这一先验知识，利用改进的Power-of-two，或称Power-of-D算法[10]来完成任务调度。针对每一个任务，根据节点处理速度、路由延迟和队列长度，考虑节点的执行、传输、空闲能耗来选择处理节点，从而降低整个边缘计算系统的能耗。最后，在CloudSim实验平台中对比了笔者所提方法和其他的任务调度方法，结果表明所提出的方法在能耗优化上优于其他算法。笔者的主要贡献如下：

(1)针对存在部分已知性能和部分未知性能节点的边缘计算平台任务调度的高能耗问题，首次提出了一种面向边缘计算平台的半线上任务动态调度方法。

(2)针对边缘计算平台中任务传输路由延迟导致的能耗问题，考虑边缘计算节点的处理速度、路由延迟等，分别计算边缘计算节点的任务执行能耗、任务传输能耗和空闲能耗，从而建立更加细致的边缘计算平台任务调度能耗优化模型；

(3)通过动态感知未知-已知节点的任务队列长度，建立未知-已知节点之间的动态映射关系，充分利用已有先验知识，提出了一种基于动态映射的半线上任务调度算法，实现能耗优化的半线上任务调度算法。

1 建立能耗模型

文中的任务调度算法以最小化系统能耗为目标。每个任务是独立且非抢占式的，分别从它们的执行时间、路由延迟和排队时间出发，研究对系统能耗的影响，建立能耗优化的任务调度模型。

对于节点k∈K，用kr表示它的队列容量，kv表示处理速度；对于任务m∈M，用mr，ml分别表示它占用的队列资源和数据长度。因此，当任务生成并在t时刻被分配给k时，需要满足

(1)

(2)

使用pmk表示m在k上的处理时间，pmk=ml/kv。任务被分配时需要经历路由传输的延迟emk=umk+u′mk。等式后面分别代表了m路由到节点k被处理和m从节点k路由到目的地之间的延迟。将节点资源量kr、处理速度kv和任务到它的延迟emk三者统称为节点的性能。

(3)

其中，

(4)

因为整个系统是并行工作的，所以系统的总工作时长等于节点中工作时长最大的，即

TG=max(Tk)，k∈K。

(5)

(6)

因此，边缘计算平台总系统能耗为

(7)

最终，得到边缘平台能耗优化目标为

(8)

2 任务调度算法

并行处理器中的任务调度问题已被证明是NP难[11]的，很难在多项式时间内求出最优解，更何况当系统中出现未知性能的计算节点时，无论是在线算法还是离线算法都无法有效利用已知部分节点性能这一先验知识，导致资源利用率不高。笔者提出一种半线上任务调度算法，来求解该实时调度问题。首先，采用一种动态映射思想，根据已知节点性能这一先验知识来想办法确定未知节点的性能，实现未知-已知节点的映射；其次，在动态映射基础上，充分利用系统已知先验知识，提出一种基于动态映射的半线上任务调度算法。

2.1 未知节点性能映射

在任务开始被分配之前，需要根据已知的节点性能这一先验知识来确定未知节点的性能。文中采用了一种映射思想，具体做法是通过将未知节点的性能映射为已知的节点；这里的性能不仅仅指的是计算节点的处理速度kv和队列容量kr，还包括路由延迟emk，∀m∈M。

维护一个未知节点到已知节点的映射表B，并且感知节点任务队列不断动态调整映射的节点。映射表的元素bij表示将节点i映射为节点j。初始化时，先将已知节点集K+按照处理速度kv的升序排列，然后让未知节点映射到K+的中位元素，该中位元素记为z；之后执行任务调度算法，在基于概率的分配下，理论上所有的未知节点和所映射的节点应当被分配几乎相同数量的任务。如果一段时间后发现任务队列长度差异明显，则根据不同情况调整映射表。具体来说，如果未知节点的任务队列长于所映射的已知节点上的任务队列，说明对其性能期待过高，需将该未知节点映射为更低性能的已知节点，反之亦然。该动态映射过程如图1所示。

图1 动态映射表工作原理

在实际应用中，影响映射双方的任务队列可能受到延迟等不稳定因素的影响，需要式(9)来抵消可能存在的误差，增加算法鲁棒性，即

(9)

其中，ε是阈值参数，如果映射双方任务队列长度之差没有超过某个阈值则不会更新映射关系。

通过这样的动态映射，不同性能的未知节点会被映射到一个较为合理的已知节点，于是就能够实现利用已知性能这一先验知识去推测未知性能，高效利用系统的计算资源调度任务。具体伪代码如算法1所示。

算法1未知节点映射算法。

输入：mapping tableB。

输出：updated mapping tableB。

① ∥Initializing

② if first time running then

③ SortK+in the ascending order ofkv；

④ Let all elements inBequal to 0；

⑤z=u/2；

⑥ for alliinvdo

⑦biz=1；

⑨ end for

⑩ end if

2.2 任务调度

在经过算法1动态映射后，当调度算法遇到未知节点时，就能通过查询映射表找到它所映射的已知节点，接下来用到的所有节点性能数据都参考该已知节点。Power-of-D算法的原理是先让任务随机选d(d通常等于2)个处理单元，再选择其中队列最短的那个，这种随机性让Power-of-D算法在实际应用表现良好。除了考虑计算节点存在任务队列长度外，还需要考虑其处理速度和路由延迟。

首先，用k′v来重新定义节点的处理速度，它表示在边缘节点受到路由延迟的影响后的处理速度：

(10)

根据每个节点的k′v计算并归一化，得到选中概率，即

(11)

这样那些低延迟、高速度的节点就会有更高的概率被选中。当任务m在t时刻生成后，按照概率F(k)选取d个节点，这些处理节点用集合D表示，最终m会被分配给其中一个节点并满足：

(12)

其中，α，β，γ是3个权重参数且β为负数，即m要在候选的d个节点中进一步选择队列短、速度快、延迟低的节点。以上3步既考虑了节点的速度和延迟，又考虑了任务队列的长度，对应于第1节功耗模型中的3项参数。其伪代码如算法2所示。因为算法中有任务在所有节点上求k′v的步骤，因此算法复杂度为O(mn)，m、n分别为任务和节点总数。

3 实验及结果分析

文中面向的是半线上边缘计算环境，但实际在大型的边缘计算网络中进行可重复任务调度实验是非常困难的。因此，采用云仿真平台CloudSim[12]对算法的性能进行评估，该平台能够对云计算系统和应用程序供应环境进行建模和仿真，支持云计算的资源管理和调度模拟，同时提供了多种可扩展接口。通过扩展部分模块将云计算模拟转变为对边缘计算模拟。

算法2半线上动态调度策略。

输入：task m，mapping tableB。

① for allkinKdo

② ifki∈K-

③ Findjthatbij==1；

⑤ end if

⑧ end for

⑨ for allkinKdo

3.1 实验环境与设置

因为现有的线上、线下和半在线方法并不完全适用于文中所讨论的场景(即存在若干已知和未知的性能节点，伴有不断变化的路由延迟)。文中选择一些通用的任务调度方法与提出的方法进行性能对比：

半线上动态调度策略(DSS)：即文中所采用的任务调度策略。

贪心算法(Greedy)：每个任务都分配给当前任务队列最短的节点。

Power-of-D[10]算法(PoD)：随机挑选D个节点，之后从这些节点中再选一个任务队列最短的节点，将任务分配给它。可以看到PoD和Greedy是在某些地方比较相似，但由于文中讨论的情景中存在路由延迟，当延迟波动较大时，PoD的随机性可以为它带来一定的优势。

轮循算法(RR)：任务依次顺序地被分配给所有的节点，是CloudSim的默认调度算法。

由于Greedy和PoD本身无法适用于半线上情景，所以在其中也添加了静态映射表来处理未知节点。实验设置了共16个边缘节点，它们按照处理速度(单位MIPS)被分为4组：250，350，450，550；每组4个节点，包括3个已知节点和1个未知节点；未知节点的性能在实验中对算法是隐藏的，但真实性能如表1的12，13，14，15所示。

表1 边缘节点的处理速度分布

实验过程中CloudSim每经过一段时间会采集各边缘节点的CPU利用率，根据利用率计算出这段时间的能耗，最后将所有时间段的功耗累加就得到了整个边缘计算平台的能耗。表2为不同CPU利用率下处理节点的能耗，具体数值设置参照了HP ProLiant ML110 G4的能耗模型。

表2 边缘节点的不同负载情况下的能耗

在任务设置方面，基于高斯分布分别生成了6 000、12 000、18 000、24 000、30 000、36 000，42 000，48 000条不同长度的任务，接着采用分批到达来实现持续的调度，每一批设定为300个任务。

3.2 结果分析

由于实验过程中有许多随机变量，如不断变化的路由延迟、算法的随机调度等，为了尽量减少误差，需要将实验中每个算法都重复执行数次再取结果的平均值。不同算法的调度结果如图2和图3所示。图2为不同调度算法的执行时长结果，图3为不同的调度算法的系统能耗结果。从图中均可以明显地看出，文中所提算法在所有数据规模下表现都是最佳的，在所有任务规模下都优于其他算法，显著降低了边缘计算平台的能耗。这是因为文中算法在基于PoD算法随机性优势的同时，考虑了边缘节点的处理速度、路由延迟、任务队列的长度，并且结合了动态映射的思想，建立未知-已知节点的动态映射，能够充分地利用未知节点的资源。PoD算法的结果是第二好的，略微优于Greedy算法。这是因为文中所设定的情景还包含任务到节点的路由延迟，尽管这两个算法都没有考虑路由延迟，但PoD算法因为具备随机性，当任务量足够且延迟较为波动时能够在一定程度上缓解这方面的缺点。RR算法只是简单的将任务一个个轮询分配在节点上，并没有进行任何的优化，所以其消耗的能耗也就最多。

图2 各方法的任务完成时间对比

图3 各方法能耗对比

图4和图5分别显示了对PoD和Greedy算法添加动态映射机制后性能提升的对比。从中可以看出，通过维护一个动态的映射表，合理假设出未知节点的性能后，两种算法的性能都得到了提升。这是因为在系统中存在未知节点，由此导致路由延迟不可忽略，在这种情况下，如何有效利用节点的资源，对于实现高效的任务调度是十分关键的。这也体现了笔者提出的动态映射思想在半线上情景中的有效性。

图4 使用动态映射后各方法的任务完成时间对比

图5 使用动态映射后各方法能耗对比

4 结束语

以能耗优化为目标，笔者提出了一种面向边缘计算平台半线上任务动态调度方法。首先，建立面向边缘计算平台的任务调度模型，该模型将总能耗划分为处理、传输和空闲三段能耗进行建模，更加细致地表示边缘计算平台的能耗；其次，对建立的任务调度优化模型，提出了基于动态映射的任务调度算法。对于系统中的未知节点，通过动态映射算法将其性能假设为某个已知节点，从而形成已知-未知节点之间的映射关系，之后不断感知映射双方的任务队列长度来动态调整映射关系，从而充分利用已有先验知识，提出了一种基于动态映射的半线上任务调度算法；最后，在CloudSim平台完成对比试验，结果表明文中所提方法能够有效利用系统的资源，有助于降低边缘计算平台的能耗。