雾计算平台的任务调度算法研究

(浙江工业大学 信息工程学院，杭州 310023)

0 引言

雾计算是一个高度虚拟化的计算平台，在传统的云计算数据中心与终端设备间，提供计算、存储和网络服务，以提高物联网计算性能。雾计算利用附件设备完成数据处理，而将数据上传至“遥远”的云端进行处理，可节约远程传输带宽，降低计算延时，缓解云端计算压力。同时，雾计算技术的位置感知能力更强，延迟更低，适用于多节点部署，因此在车联网等物联网和交通指挥系统等互联网系统中广泛应用[1]。

云计算模式中的资源高度集中，导致数据中心远离用户端，容易造成传输拥塞与传输延迟。而雾计算通过将云计算的部分功能转移到网络边缘，在更靠近终端的地方，为用户提供实时交互、移动性支持和外置感知等服务，减少了系统内部数据流量，提高终端的响应能力。但是，由于不同终端、不同任务的资源需求不同，需要雾计算有适当的任务调度策略对海量的雾计算节点资源进行分配与调度。因此，构建合理的资源管理、任务调度体系，可进一步提高雾计算服务质量，在信息技术领域具有重要的理论意义以及现实应用价值。

当前，这对雾计算特点的任务调度算法研究较少。汪成亮利用Rete算法构造推理网络，将推理节点优化分配至各计算节点，提高了节点的资源利用率[2]。汤琳煜基于稳定匹配的思想，解决任务与服务设备的分配问题[3]。韩奎奎提出一种改进的遗传算法，进行任务调度与分配[4]。熊凯采用强化学习算法有效提高异构车联雾架构下的资源优化[1]。从雾计算任务调度的研究现状来看，其研究较少，缺少一种较广泛应用的雾计算任务调度算法。为此，本文提出一种基于改进蜂群算法，为雾计算的任务调度提供一种新的思路[5]。

1 雾计算概述

雾计算是由Cisco公司所提出的一种分布式计算结构，自2011年被提出以来，这种技术被广泛地应用于智能服务机器人、智能家居、智能电网、智能交通等领域。雾计算的整体架构如图1所示。

图1 雾计算平台整体结构

如图1所示，雾计算利用雾集群中的边缘闲散计算资源，为终端用户提供计算服务。无集群的整体结构设计如图2所示。

其中，雾中心节点负责整个雾集群节点的任务内编排与控制，雾服务节点负责提供Docker容器和雾计算能力，雾网络节点负责网络拓扑发现与数据转发。雾服务节点均基于Docker引擎，运行不同数量的容器，而这些容器构成了容器集群，提供雾计算服务。

雾计算体系内的调度问题，其实质为任务请求过程中的重叠问题。在雾计算为用户请求任务分配计算资源时，每个任务的处理必然会持续一段时间，而任务请求时间及其后的持续时间段，会导致任务处理时间重叠。而雾计算任务的角度的目的为：对于处理时间上有重叠的任务集合，制定合理的资源、任务调度方案，以保证所有任务处理的总体时间最短。

2 雾计算任务调度模型

2.1 任务调度流程

雾计算任务调度过程如图3所示，由雾中心节点在调度任务与计算资源的约束下，通过调度算法，选择合适的雾服务节点，在雾服务节点的Pod容器内进行任务计算。

图3 任务调度过程

调度服务不断向雾中心节点查询待调度的Pod列表，以及当前雾节点集群中的可用雾服务节点Node列表，根据调度策略，优选雾服务节点资源进行任务处理[6]。

默认的调度流程为以下两个步骤：

1)根据雾中心节点与雾服务节点的通信，了解雾服务节点的可用状态，构建可用服务节点Node列表；

2)按照改进人工蜂群算法对可用的雾服务节点进行评价，选择最合适的雾服务节点，完成雾服务节点的调度。

2.2 任务调度数学模型

雾计算任务调度模型的描述可使用五元组G=(V,P,E,W,C)来描述。

其中，V= {vi| 1≤i≤n}表示待处理的任务集合；P= {pi| 1≤i≤m}为可用的雾服务节点；E={eii| 1≤i≤n, 1≤j≤m}为DAG图中的有向边集合，表示任务vj是否需要任务vi的处理结果；W为式(1)所示的一个n×m的矩阵。

(1)

wij表示采用节点pj处理任务vi时的系统开销。C为如式(2)所示的一个m×m的矩阵。

(2)

cij表示，若eij≠0时，vi完成后，到vj开始处理前的通信开销。若vi和vj在同一个节点上完成，或eij=0时，cij=0。

综上，雾计算的任务调度过程看作是如图4所示的一个有向无环图。

图4 任务调度过程

在雾服务节点集合P={p1,p2,…,pi,…,pm}上，执行任务集合V= {vi| 1≤i≤n}的过程，是一个在任务模型DAG图上，具有时间有限约束的调度函数f，函数f以特定的开始时间，将任务映射到处理单元上，一个任务的调度可描述如式(3)所示：

f:T→{1,2,…,m}×[0, ∞)

(3)

若，有v∈T，且f(v)=(i,t)，表示任务v在时间t，被分配到雾服务节点pi上执行。

任务调度函数f，可通过Gantt图(甘特图)来表示。在Gantt 中，存储了一个处理单元表，对于每一个处理单元，每个任务都有处理单元与之相对，可直观地表示任务的开始时间与结束时间，按照分配到该雾服务节点上的所有任务，按照先后执行的顺序进行排列。

Gantt图可使用如式(4)所示的四元表来表示：

Gant(pi,vj,ST(vi,pi),FT(vj,pi))

(4)

其中:ST(vj,pi)表示在任务vj，在雾服务节点pi上的开始执行时间，FT(vj,pi)表示在任务vj，在雾服务节点pi上的结束执行时间。

在任务调度系统中，所有雾节点上的最大调度长度SL定义为：

(5)

而雾计算任务调度策略的目标即为：最大调度长度SL的最小化。

3 雾计算任务调度算法设计与优化

3.1 算法思路

在以性能优先的雾计算平台中，其调度的目标就是在雾计算平台的资源和待处理任务的约束下，使得如图4所示的有向无环图的遍历时间最短。已有的研究成果表明，DAG图的遍历问题是一个NP-完全问题，在多项式时间复杂度内，无法找到问题精确解。对此本文将采用人工蜂群(artifical bee colony，ABC )算法，将任务分配给雾服务节点的过程，模拟为派遣蜜蜂前往蜜源采蜜的过程，以求解雾计算任务调度数学问题，在较短时间内，找到较优的雾计算任务调度策略，以提高任务的调度和处理效率[7]。

ABC模拟蜂蜜的觅食采蜜机制，将觅食的蜂群划分为侦查蜂、观察蜂、雇佣蜂3个类型。雇佣蜂的数量与环境中食物点(蜜源)数量相同，雇佣蜂在环境区域内随机搜索蜜源，存储所找到的蜜源信息；雇佣蜂在完成区域搜索后，与观察蜂分享区域内的蜜源地址信息；观察蜂在蜂巢内，接收侦查蜂传递的信息，确定环境内蜜源。若蜜源长时间内没有进化，则暂时放弃该蜜源，随机搜索新的、更具价值的蜜源，以取代没有进化的蜜源[8]。

ABC通过模拟蜂蜜的觅食采蜜机制，将觅食的蜂群划分为侦查蜂、观察蜂、雇佣蜂3个类型，其具体步骤如下所示。

1)初始化阶段：初始化蜜源数量N，观察蜂数量和雇佣蜂数量N，蜜源最大开采次数Limit，最大迭代次数Maxcycle。在初始阶段，侦查蜂随机搜索N个蜜源，采用N个D维向量表示搜索所得的N个蜜源，蜜源的产生公式如式(5)所示：

xij=xminj+α(xmaxj-xminj)

(5)

其中:xij表示蜜源i∈{1,2,…,N}的第j∈{1,2,…,D}个维度，α为(0,1)间的随机数，xminj和xmaxj分别表示第j个维度空间内的最小值和最大值。

2)雇佣蜂阶段：当雇佣蜂在区域内搜集到新的蜜源后，根据贪婪规则更新区域内的蜜源，若新蜜源的适应度，较原蜜源的适应度更高，则将新蜜源替代原有蜜源，其更新的公式如式(6)所示：

vij=xij+φij(xik-xkj)

(6)

其中:xij为原有的蜜源位置，vij为雇佣蜂所搜索到的新的蜜源位置，φij为一个[0,1]间的随机数，xkj为不同于当前蜜源的另一蜜源，k≠i，且k∈[1,N]。

3)观察蜂阶段：侦查蜂发现新蜜源后，通过适应度函数计算蜜源的适应度值，以衡量蜜源的质量，蜜源适应度的计算公式如式(7)所示：

(7)

其中:fi为蜜源xi的适应度值观察蜂通过雇佣蜂的所传递的信息，用于判断新蜜源位置，与新蜜源质量。新蜜源质量越高，前往采蜜的观察蜂越多，并采用轮盘赌概率，派遣前驱采蜜的观察蜂，观察蜂选择新蜜源的概率公式如式(8)所示：

(8)

4)侦查蜂阶段：在Limit次循环后，若蜜源仍未被更新，则选择放弃该蜜源。 此时，雇佣蜂就会变为侦查蜂，重回侦查蜂阶段，寻找新的蜜源。

最终，在寻找到适应度值满足预设要求，或者当迭代次数超出了预设的最大迭代次数后，将适应度值最高的蜜源作为算法结果，并退出人工蜂群算法的迭代。

3.2 人工蜂群算法改进与优化

虽然ABC算法有较好的收敛性。但对初始值质量的要求较高，若初始方案的质量较低，将影响ABC算法的收敛精度与收敛速度等问题。但在雾计算的任务调度过程中，初始的任务分配方案是随机的，可能影响ABC算法效果。

针对该问题，本文主要通过在初始阶段引入正弦映射，以提高初始值质量，和在迭代过程中，引入混沌思想，以提高搜索范围的方式，进行ABC算法的优化[9]。

混沌具有非线性动力系统的固有特性，混沌空间中的变化过程看似是杂乱无章，但在这个看似杂乱无章的混乱过程中，又体现了精致的内在规律性，其数学描述如下所示：

xk+1=τ(xk)

(9)

其中:k=0,1,2,…，τ为一个非线性的映射，0

如式(10)所示的正弦非线性映射，通过正弦变化，可得到所需的混沌序列。

xn+1=asin(bxn)

(10)

其中:a和b为正弦非线性映射模型的相关参数。

在人工蜂群算法的初始化阶段，采用正弦非线性映射，引入到人工蜂群的初始化过程。基于正弦变化的人工蜂群的种群变量初始化如式(11)所示：

Chk+1=sin(πChk)

(11)

其中:k为迭代计数器，k=0,1,2,…,m，m为最大混沌迭代次数，Chk∈(0,1)。将式(11)引入到人工蜂群的初始化过程，采用混沌变量后的种群变量转换公式如式(12)所示：

xij=xminj+Chkj(xmaxj-xminj)

(12)

其中:xminj和xmaxj分别表示第j个维度空间内的最小值和最大值。

3.3 资源调度算法流程

基于改进人工蜂群算法，快速实现任务与雾计算资源间的匹配，实现雾计算任务的快速调度。为了让改进人工蜂群算法适用于雾计算资源的调度分配，还需要算法中的解和适应度函数进行重构[10]。

1)解的重新构造：假设雾计算层的可用雾服务节点数为m，待任务数为n。任务调度的目的就是将n个计算任务分配到m个雾服务节点上进行处理。因此，蜂群解描述如式(13)所示：

Xi=(xi1,xi2,…,xin),i=1,2,…,m

(13)

例如，将任务(t0,t1,t2,t3)分配到雾计算虚拟资源(p0,p1)上，最终的解表述为X0=(1,0,0,1)，X1=(0,1,1,0)，即将任务t0和t3分配到雾服务节点p0上进行处理，在雾服务节点p1上计算资源v1上计算任务t1和t2。

2)适应度函数的计算：对蜜源质量进行评价的适应度函数设计如式(13)所示：

(13)

即完成所有任务的时间越短，该调度策略的适应度函数值越大，以确保找到最优的任务调度策略[11]。

基于改进蜂群算法的雾计算资源优化调度策略流程如图5所示。

图5 基于改进人工蜂群的任务调度

1)蜂群规模初始化，采用混沌映射初始化人工蜂群的种群，产生初始解，根据将n个计算任务分配到m个虚拟雾服务中心上，构成人工蜂群算法的初始解，并设置人工蜂群算法的最大迭代次数Maxcycle等初始化参数。

2)雇佣蜂按照贪婪规则，搜寻区域内的新蜜源位置，基于适应度函数计算新蜜源适应度，通过新蜜源适应度值与当前解适应度值的对比，选择适应度更优的蜜源位置，获得更优的雾计算资源分配方案。

3)在迭代过程中引入混沌思想，让适应度函数越高的蜜源，能招募到更多的观察蜂，通过新蜜源的不断更新，保留条件最优蜜源。

4)若某蜜源超过了预设临界值Limit，则将观察蜂转换为侦查蜂，产生新的蜜源，替代被放弃的蜜源。

5)当人工蜂群的迭代次数超过了最大迭代次数Maxcycle时，算法结束，将适应度最高的蜜源，作为雾计算任务调度策略；否则继续执行第2)步。

4 基于改进人工蜂群的资源调度策略

在基于改进人工蜂群算法的雾计算平台任务调度过程如图6所示。

图6 基于改进算法的资源调度过程

雾计算平台终端通过雾计算将服务提交到FMDC雾中心节点，设置资源监控器，监测当雾层的资源使用状况，并将资源信息存储到雾中心节点，将待处理任务进行集中管理，通改进人工蜂群的资源调度算法，制定任务调度策略，最终完成待处理任务的计算。

基于改进人工蜂群的任务调度过程具体实现如下所示：

算法： 改进人工蜂群的任务调度

输入： 人工蜂群初始化参数(N, D, Maxcycle)

输出： 资源调度方案

Step 1. 在初始化阶段引入正弦映射

Step 2. fori=1:N

Step 3. forj=1:D

Step 4. ch(1,j) = rand

Step 5. fork= 1:cmax

Step 6. ch(k+1,j) = sin(pi×ch(k,j))

Step 7. end

Step 8.xij=xminj+chkj(xmaxj-xminj)

Step 9. 计算适应度值

Step 10. end

Step 11. end

5 仿真实验分析

为证明本文所研究的改进人工蜂群算法在任务调度中的有效性，采用Matlab工具，对ABC人工蜂群算法和改进人工蜂群算法进行对比仿真实验。

仿真实验过程中相关参数设置如下：蜜源停留最大次数Limit=100，蜜源数目N=20，最大迭代次数Maxcycle=2 500，随机生成100～700个不同的任务，对比分析不同任务数量下，两种不同算法的任务完成时间。为确保算法实验结果的精确性，对分别使用两种算法分别独立运行20次，取其平均值作为算法的执行结果[12]。

在不同任务数量下，两种不同算法的任务完成时间对比情况如图7所示。

如图7所示，当任务量较少时，两种算法的优化效果并未有明显区别，根据不同调度算法完成所有任务的时间也相差不大，但是随着任务数量的不断增长，改进人工该算法完成所有任务的时间明显更优。究其原因，主要是因为随着任务数量的增加，人工蜂群算法容易陷入局部最优解，从而消耗较长时间也难以获得全局最优解，而在改进人工蜂群算法中，通过引入混沌策略，极大地提高了算法的全局寻优能力，提高了任务调度效率，以优化雾计算资源使用更优，和提高雾计算平台的任务处理效率与性能。

6 结束语

雾计算资源的任务调度策略是雾计算技术的研究重点之一，通过任务调度策略的优化，有助于雾计算资源的应用优化，进一步提升雾计算性能。本文所采用的改进人工蜂群算法，不仅能在多项式时间内找到较优解，提高了任务调度性能，同时通过在初始阶段引入混沌思想，提高了初始值质量，扩大了搜索范围，提高了解的质量，优化了任务调度策略，有利于雾计算性能的进一步提升。