基于遗传蚁群算法的雾计算任务调度研究

2021-08-12王志刚赵传信

计算机应用与软件 2021年8期

王志刚赵传信

(安徽师范大学计算机与信息学院安徽芜湖 241000)

0 引言

为了减轻云计算中心的压力，雾计算作为云计算的扩展被提了出来，主要为了解决需要低延迟、移动支持、地理分布和基于位置信息的问题。雾计算利用位于云计算网络边缘的设备为就近的用户提供服务，促进了云计算中心和用户之间的任务处理，那些不适合云计算的应用可以交给雾计算执行，例如需要减少延迟的视频会议、智能交通等。

雾计算作为一种分布式计算平台，节点们通过相互协作的方式来执行用户提交的计算任务，这些节点将本地可以利用的资源整合在一起，利用近距离低延迟的优势为用户提供实时处理服务。同时作为云计算的补充，雾计算还可以使用云计算中心强大的计算能力和存储能力，并将云计算的计算服务扩展到网络边缘。相比于云计算中心的设备，靠近用户的雾计算节点设备通常是资源受限的设备，如基站、接入点、路由器等。目前基于雾计算的研究还属于发展阶段，研究人员为了更好地使用雾计算服务引入了任务调度，任务调度的目的就是将雾节点执行的经济高效的服务提供给请求服务的终端。

在雾计算的初步研究中，包括任务调度与分配、雾计算参考架构、功耗时延优化等，国内外学者对任务调度的研究相对较少。文献[1]提出云雾架构下的任务请求分配模式。Gupta等[2]提出设计一个高效的任务调度和资源管理的重要性。Zeng等[3]研究了如何平衡工作负载以及如何放置任务；何秀丽等[4]提出多设备分布式计算方法；程冬梅等[5]提出智能前端化的雾计算参考框架；Sarkar等[6]证明了在物联网应用程序需要实时低延迟服务情况下，雾计算平均能耗比常规云计算低。Deng等[7]提出云雾计算系统分配工作负载时功耗和计算延迟权衡问题，通过现有技术分解后采用He等[8]提出的凸优化技术来处理雾计算子系统优化功耗和延迟，采用Li等[9]提出的非线性规划问题来寻找功耗和计算延迟的折衷点，最后采用Kuhn[10]提出的匈牙利方法解决从雾节点到云服务器的数据传输延迟，但是该研究不适合雾计算基础设备，负责工作的中心节点容易出现性能瓶颈。Song等[11]提出了一种基于任务分配的图形划分的雾计算负载均衡机制，但是其缺点是频繁的图形重新划分来处理雾的变化，性能对于动态雾负载均衡不是最佳的。Cardellini等[12]评估了在雾计算环境中运行的数据流分析的分布式服务质量感知调度程序，然而复杂的雾拓扑结构可能导致一些不稳定性，从而降低程序的可用性。Oueis等[13]讨论了雾计算的负载均衡问题以提高用户体验质量，但是不适用大规模雾计算基础设施，会出现高复杂性。Intharawijitr等[14]提出了一种雾计算架构，以帮助计算系统通过确保最佳任务调度来实现最大功率，结果发现使用一个特定策略可能不是整个系统的最佳解决方案。Bitam等[15]针对雾计算的调度问题，提出了新的生物启发式优化方法蜜蜂生活算法(BLA)，在可用雾节点中寻找最优分配，实验验证了BLA在雾计算环境下解决任务调度问题的有效性。

1 问题描述

1.1 雾计算模型

本文研究的雾计算架构是三层网络结构，如图1所示。顶层是云层，由远端的云计算服务器组成，这些服务器有很强的计算和存储能力；中间层是雾层，由靠近用户的相对较弱的计算和存储设备组成，这些设备大部分都是单片微型计算机、路由器、无线路由器、智能网关等雾节点设备，小部分是专门部署的雾计算服务器；底层是终端层，比通用的雾计算构架多了感知执行层，感知执行层包括传感器和执行器，属于终端层的一部分。很多文献中的雾计算框架图中都没有传感器和执行器，这就让人很容易忽略传感器和执行器，使人误以为终端层只有移动用户使用的手机、PC等设备，但是传感器和执行器才是雾计算不可缺少的一部分，例如：在智能交通的雾计算环境下，道路上的传感器(摄像头等)和执行器(指示灯等)才是整个智能交通雾计算环境中参与度最高的设备。

图1 雾计算架构图

1.2 任务调度问题

如图2所示，雾计算环境下的视频分析平台是由N个雾节点和若干智能摄像头组成。智能摄像头收集到足够多的视频信息后便向就近的雾计算节点发出服务请求，提交视频分析任务给雾计算节点，该节点接受任务之后传递给管理节点，管理节点汇总请求后进行任务调度分析。

图2 雾计算视频分析平台

这里使用遗传蚁群算法进行任务调度，由管理节点执行，以找到最佳的顺序调度雾节点执行，调度模型如图3所示。首先终端发送服务请求并提交任务(①)；接着雾节点们传递任务到管理节点(②)；然后管理节点执行调度算法，分配任务给节点们(③)；最后汇总结果响应给终端(④)。

图3 雾计算任务调度模型

m个终端提交任务表示为：

Tasks={T1,T2,…,Ti,…,Tm} 1≤i≤m

(1)

n个雾节点表示为：

Fogs={F1,F2,…,Fj,…,Fn} 1≤j≤n

(2)

为了方便雾计算节点执行任务Ti，将任务Ti进行分块，分块数为l时表示为：

Ti={TBi1,TBi2,…,TBik,…,TBil} 1≤k≤l

(3)

Ti={TBi1,TBi2,…,TBik,…,TBil} 1≤k≤l

(4)

式中：1≤x1,x2,…,xk,…,xl≤n。

雾节点Fj上被分配的任务为：

(5)

式中：1≤y1,y2,…,yq,yp≤m；1≤z1,z2,…,zq,…,zp≤l。

雾节点Fj的CPU执行时间定义为：

(6)

雾节点Fj的内存消耗定义为：

(7)

任务调度的首要目的就是尽可能满足终端的请求，参考基于服务水平协议(SLA)的云计算调度，可以定义雾计算的违规花费为：

Penalty(Ti)=basePenalty(Ti)+β(Ti)×delayTime(Ti)

(8)

式中：Ti因为服务超时而发生违规；basePenalty(Ti)表示Ti的基本违规花费；β(Ti)表示单位时间违规花费;delayTime(Ti)表示延迟时间。定义违规任务集合为VTasks，因此目标的违规花费定义为：

(9)

其次，最小化所有雾节点的CPU执行时间和消耗内存也就是雾计算的花费，定义为：

(10)

CostFunc(FjTasks)=w1Exec(FjTasks)+w2Mem(FjTasks)

(11)

式中：w1和w2是权重因子，用于强调CPU执行时间和内存消耗两个评估目标的重要性。

综上所述，雾计算任务调度的目标函数为：

func=Cost(FogsTasks)+PenaltyCost(Tasks)

(12)

2 算法设计

针对雾计算的任务调度研究仍是一个比较重要的问题。现有的调度算法都是单独使用遗传算法或者蚁群算法，无法获取较好的结果。通过对遗传算法与蚁群算法的研究与实验发现，遗传算法在搜索的初期寻找最优解的速度比较快，但是在一段时间后速度明显下降。而蚁群算法在初期搜索最优解的速度特别缓慢，当搜索产生的信息素浓度变高时寻找最优解的速度迅速提高。因此本文提出一种针对雾计算任务调度的遗传蚁群算法，在遗传算法性能出现下降的时间点生成蚁群所需要的信息素，并随后使用蚁群算法求最优解。

2.1 遗传算法

传统的遗传算法用于解决穷举耗费时间过长的解空间比较庞大的问题。遗传算法的思想就是要模拟自然选择，因此遗传算法必须同时满足遗传、突变、选择这三个要素。遗传算法有并行、高效、全局搜索的优点，但是也存在局部搜索能力差和过早陷于最优的缺点。

2.2 蚁群算法

蚁群算法通过模拟自然界蚂蚁寻找食物过程的优化算法，与真实蚂蚁通过信息素的留存、跟随行为进行间接通信相似，蚁群算法中一群简单的人工蚂蚁利用代码中的信息素数据进行间接通信，不断利用该信息来构建问题的解。蚁群算法优点包括并行、自组织、正反馈、易与别的优化算法结合，但是也存在前期需要较长的搜索时间和容易出现停止现象的不足。

2.3 遗传蚁群算法

遗传算法和蚁群算法的相互融合是指前期使用遗传算法先进行搜索并在合适的时候停止，可以避免蚁群算法前期比较耗时的搜索过程，再使用蚁群算法，把遗传算法得到的解作为蚁群算法的初始值，利用蚁群算法的正反馈更好地找到问题的解。

遗传算法编码有很多种，本文采用直接编码，假设有n个雾节点和m个任务，任务分块后为w个，则染色体的长度为w，假设m=5、w=10、n=5，单个染色体解释如下：

“5324415243”：任务块1、7分配给雾节点5；任务块2、10分配给雾节点3；任务块3、8分配给雾节点2；任务块4、5、9分配给雾节点4；任务块6分配给雾节点1。

遗传算法群体规模一般选择为10～200之间，这样既不会导致计算复杂度较高又不会很快陷入局部最优。遗传算法的适应度函数的选择可以直接使用雾计算调度的目标函数。遗传算法的交叉操作采用两点交叉，如图4所示，交叉的概率控制在0.25～1.00之间，避免迟钝的同时也可增加搜索能力。遗传突变操作采用单点突变，如图5所示，变异的概率控制在0.001～0.1之间，防止重要基因丢失和避免趋向纯粹的随机搜索。遗传算法的终止进化代数是运行结束的参数，可以通过判断子代进化率来确定，当进化率低于1%的时候，结束遗传算法进入蚁群算法。

图5 遗传算法单点变异

蚁群算法中蚂蚁找到的路径就是任务调度的一个解，因此蚂蚁每次需要选择的就是雾节点。蚂蚁每次从原点出发，第一次选择的雾节点就是给第一个任务分块选择的，以此类推。当所有的任务分块都有对应的雾节点时，蚂蚁完成使命回到原点。蚂蚁会根据路径上的信息素量和启发式信息独立选择下一个雾节点，在t时刻蚂蚁a从一个雾节点i转移到另一个雾节点j的概率为：

(13)

式中：Jk(i)={1,2,…,j,…,n}表示下一步可以取的雾节点编号集合。禁忌数tabuNumber记录了蚂蚁a选择雾节点的数目。当tabuNumber达到任务分块总数时就代表所有任务分块都分配完毕，蚂蚁a便完成一次周游，此时蚂蚁a选择的雾节点序列就是雾计算任务调度的一个可行解。ηij是启发式因子，表示蚂蚁从雾节点i选择下一个到雾节点j的期望程度，在任务调度问题中取选择后需要的花费。α和β分别表示信息素量和期望启发式因子的相对重要程度，一般α取1～4之间，β取3～5之间，为了避免过早停滞和陷入局部最优，必须在两者选取一个平衡点。当所有的蚂蚁完成一次周游后，需要更新各个路径上的信息素量，公式如下：

τij(t+n)=(1-ρ)τij(t)+Δτij

(14)

式中：ρ(0<ρ<1)表示路径上信息素量的蒸发系数，则1-ρ表示信息素的保留系数。为了避免固定不变的更新信息量采用自适应改变ρ的值，即:

(15)

式中：ρmin是防止ρ过小降低算法收敛速度的最小值；Δτij表示每次迭代中雾节点i到雾节点j路径上的信息素量的增量，先采用最大最小蚂蚁系统控制信息素量的范围在[τmin,τmax]内，采用精英蚂蚁系统和基于排序的蚁群算法，精英蚂蚁也就是解的目标函数最小的蚂蚁释放最多的信息素，在每次循环中，排名前x名的蚂蚁和精英蚂蚁才允许释放信息素，精英蚂蚁起到最大的作用需要和系数x+1相乘，排名第y名的蚂蚁乘以系数x-y-1，即：

(16)

(17)

取遗传算法得到的解结果的10%用作蚁群算法信息素量的初始化，这里不同于其他文献中直接转换成信息数值，采用蚂蚁进行信息素量初始化，从低到高有目的地进行选择周游，这样经过蚂蚁根据用于初始化的解结果执行完周游后，初始化就完成了，这里的蚂蚁数量需要根据用于初始化的解结果数量进行合理取值。初始化完成后蚁群算法进行探索的蚂蚁数目应该控制在10～50之间，最大进化代数应该控制在100～500之间，这样的蚁群算法的性能相对比较均衡。图6为遗传蚁群算法流程。

图6 遗传蚁群算法流程

3 仿真实验

3.1 实验设定

实验环境设置：仿真软件iFogSim；处理器AMD Athlon(tm) X4 860K Quad Core Processor 3.9 GHz；内存16.0 GB；操作系统Windows 7 旗舰版 64位 SP1；开发工具Eclipse Java Oxygen(JDK1.8.0_144)、Visual Studio 2015(.NET Framework 4.5.2)；开发语言Java、C#。

雾节点的参数设置如表1所示，任务参数设置如表2所示，算法的参数设置如表3所示，计算资源参数如表4所示，额外需要的算法参数如表5所示。

表1 雾节点的参数设置

续表1

表2 任务参数设置

表3 算法参数设置

表4 计算资源参数

表5 算法参数列表

3.2 结果分析

为了证明遗传蚁群算法相比较于传统的遗传算法和蚁群算法在任务调度上更有效，在C#中实现遗传算法、蚁群算法、遗传蚁群算法并进行任务调度比较。算法中雾计算节点的设置依据表1，任务分块大小设置依据表2，算法的参数依据表3。图7为遗传蚁群算法、遗传算法、粒子群算法的CPU执行时间结果；图8为消耗内存结果；图9为雾计算花费结果。可以看出，遗传蚁群算法与遗传算法、粒子群算法相比，能得到最佳的效果。

图7 执行时间对比图

图8 消耗内存对比图

图9 花费对比图

验证过遗传蚁群算法的有效性后，就可以进行遗传蚁群算法在仿真平台上的实验。iFogsim仿真平台是Cloudsim团队编写的雾计算仿真平台，在iFogsim上的仿真实验主要针对云雾协作的雾计算，终端产生的任务由随机程序模拟产生，请求数量分别设置为100、300、500、700、900；请求的任务大小为500～15 000 MI之间；资源参数依据表4；惩罚使用的参数依据表5。从图10和图11所示的时延与SLO违规率对比可知，与雾-遗传算法相比，雾-遗传蚁群算法不仅在时延上有优势而且违规率更低。这是因为雾-遗传蚁群算法融合了遗传算法和蚁群算法的优点，在问题解空间里能够更快更好地找到分配结果。与云雾-遗传蚁群算法相比，由于雾-遗传蚁群算法将部分任务分配到可行的雾节点上，有效缩短响应时间，所以降低了SLO违规率。