基于改进的蝗虫算法的云计算任务调度研究

陈 暄 程宏兵

1(浙江工业职业技术学院 浙江 绍兴 312000)2(浙江工业大学 浙江 杭州 310023)

0 引 言

云计算是分布式计算、并行计算、网格计算、网络存储、虚拟化等技术的发展融合,是目前已经实现的一种商业服务模式。它以高效、便捷的服务受到了当前人们的欢迎。云计算中的软硬件都是资源,它将计算任务分布在大量的计算机组成的资源池上,以网络服务的方式提供给用户。随着云计算的发展和数据规模不断扩大,传统的调度算法已经无法满足当前的需求,因此为用户提供更为合理的资源分配方式、减少任务完成时间、设计高效负载均衡等问题是目前云计算中的研究方向。

云任务中的任务调度本质就是一个NP完全问题[1],很多传统的元启发式算法用于解决此类问题,比如遗传算法[2-3]、粒子群算法[4-5]、蚁群算法[6-7]、人工蜂群算法[8-9]，都取得了不错的效果。一些学者将改进的传统启发式算法用于云计算任务调度[10-15]，取得了一定的效果。一些学者将两种传统的元启发式算法进行融合用于云计算任务调度，例如：文献[16]提出了基于ACO和PSO融合的云计算的任务资源调度算法;文献[17]提出了基于GA和ACO融合的用于云计算任务资源调度算法，该算法能够降低任务调度时间和成本，但缺乏与较新的元启发式算法对比效果；文献[18]提出了基于ABC和PSO融合的云计算任务调度算法；文献[19]提出了基于SFLA和GA融合的云计算资源算法；文献[20]提出了基于SFLA和PSO融合的用于云计算中可信任资源的调度算法。这些融合后的算法都能吸收各自算法的优点，确实提高了云计算任务调度效率,但增加了整个调度算法的复杂度。另外一些学者专注于较新的算法用于云计算任务调度,例如：文献[21]提出了一种基于烟花算法的云计算任务调度方案,仿真实验说明该算法能够优化调度效率,但缺乏与其他较新的算法进行对比;文献[22]提出在云计算中使用鸡群算法用于云计算资源任务调度,仿真实验说明该算法在虚拟机负载、时间和成本方面具有较好的调度效果,但缺乏对能耗指标进行考虑；文献[23]提出将共生共物算法用于云计算任务调度中，仿真实验说明该算法能够提高调度效率，但增加了算法的复杂度。文献[24]提出将细菌觅食的算法用于云计算的资源调度中，取得了不错的效果。

蝗虫算法[25]是2016年诞生的一种新的元启发式算法,性能优于部分传统元启发式算法,具有很强的开发能力。目前将该算法用于云计算相关调度的文献非常少，文献[26]将其用于云计算资源调度，取得了较好的调度效果。本文将改进的蝗虫算法用于云计算任务调度,仿真实验中通过与蚁群算法、粒子群算法以及基本蝗虫算法在完成时间、成本消耗以及负载均衡三个指标的对比,说明了改进的蝗虫算法在云计算中具有良好的调度效果。

1 云计算任务调度模型

在云计算中任务调度策略将直接影响底层系统的资源使用效率，因此如何分配任务成为云计算调度的关键问题。图1展示了云计算系统中典型任务调度过程的逻辑视图。本文中主要关注不同调度算法的性能，因此假设用户提交的所有任务在逻辑上都是相互独立的，云环境下的任务调度过程可以概括为以下三个步骤。首先，输入任务的详细信息和可用计算资源；其次将根据某些策略来映射任务和资源，按照映射进行操作，控制层的任务计划将生成优化的任务执行计划，以满足某些已分配的要求(即优化目标)；最后将优化后的计划交付给底层任务处理层以供执行，并将输出结果发送给用户。采用这样的模式优势在于能够降低计算时延、降低计算成本，提高了用户体验效果。

图1 云计算任务调度逻辑过程

本文将负载均衡、完成成本、执行时间作为用户评价云计算(Quality of Service,QoS)服务的参考依据。

设有N个任务{T1,T2，…，Tn}和M个资源节点{N1,N2，…，NM}, 其中N>M,云计算下的任务调度可以通过如下矩阵表示:

(1)

矩阵A中的aij为1表示任务i在资源j上执行,否则aij为0，i∈[1,N]，j∈[1,M]。本文定义每个资源节点的属性包括处理能力(即处理时间)、初始内存(即反映处理所承受的负荷)、资源带宽(即反映了处理所需要的成本)。因此,构建虚拟机资源三个向量分别是处理能力向量En、负载能力向量Sn、资源带宽向量Cn。与此同时每个任务对应也具有三个矩阵,分别是处理能力向量Et、负载能力向量St、资源带宽向量Ct,P为单位价格。因此时间目标函数time、负载目标函数load和成本目标函数cost表示如下：

(2)

(3)

(4)

式中：Et,i表示第i个任务的Et的值；En,j表示第j个虚拟机的En值；St,i表示第i个任务的St的值Sn,j表示第j个虚拟机的Sn值；Ct,i表示i个任务的Ct值；Cn,j表示第j个虚拟机的Cn值。

由于资源节点和任务节点的三个矩阵中所表示的结果具有不同的标准,因此需要进行归一化处理,因此上述三个目标函数表达为如下形式:

(5)

(6)

(7)

2 改进的蝗虫算法的云计算任务调度

2.1 蝗虫算法

Saremi等根据蝗虫的群体行为提出了蝗虫优化算法(Grasshopper optimization algorithm,GOA),该算法分为探索和开发两个部分组成,其中探索部分对应蝗虫的幼虫阶段,开发部分对应蝗虫的成虫阶段。幼虫阶段中,蝗虫群体跳跃性运动的行为,主要进行全局搜索;成虫阶段中,蝗虫在小范围内移动,有利于局部搜索。蝗虫种群在繁衍、觅食、迁移的时候,其个体位置会受到来自种群交互力、引力和风力的影响,因此采用数学模型对其位置更新行为描述如下:

Xi=r1Si+r2Gi+r3Ai

(8)

式中：Xi表示第i只蝗虫的位置；Si表示第i只蝗虫受到其他蝗虫的交互力的影响；Gi为第i只蝗虫受到引力的影响力；Ai为第i只蝗虫受到风力的影响力；r1、r2、r3分别为随机数且取值为[0,1]。其中：

(9)

(10)

当s(r)大于0的时候,蝗虫之间会相互吸引,因此r的取值范围称作吸引域；当s(r)小于0的时候,蝗虫之间相互排斥,因此r的取值范围称作排斥域;当s(r)为0的时候,蝗虫之间既不吸引又不排斥,因此r为舒适的距离。另外,f和l分别表示吸引强度参数和尺度参数,它们的取值情况影响到吸引域,排斥域和适度的分布距离,一般l取值为1.5,f取值为0.5。

Gr=-geg

(11)

Ai=uew

(12)

式中：g表示引力常数；eg表示指向地心的单位向量;u表示风向常数；ew表示风向单位向量。因此蝗虫个体位置更新如下:

(13)

虽然式(13)是用来对蝗虫群体进行模拟的,但是从实际应用的方面进行考虑,通常不考虑引力因素,认定风向指向目标位置,因此求出最佳的蝗虫个体位置即为求解最优化问题。公式如下所示：

(14)

(15)

式中：ubd和lbd分别对应第i只蝗虫在第d维度变量的上界和下界；Td为蝗群的目标位置；c为递减系数，一方面用于平衡全局搜索和局部开发能力,另一方面用于排斥域及吸引域；t为当前迭代次数；cmax和cmin分别为最大值和最小值。

2.2 改进的蝗虫算法

像其他的元启发式算法一样，蝗虫算法也存在易陷入局部最优、全局搜索能力不足的问题。文献[27]提出在蝗虫算法中引入自适应策略来优化参数，提高了算法的收敛速度,但增加了算法运行时间;文献[28]提出了曲线自适应和模拟退火蝗虫优化算法,提高了蝗虫算法的收敛精度，但增加了算法复杂度;文献[29]提出了一种基于量子计算思想的混合蝗虫优化算法,具有更强的全局搜索能力,更好的收敛精度,能够有效跳出局部最优,但增加了算法运行时间。

针对蝗虫算法中的种群无初始化以及线性递减参数需优化的问题，本文提出了采用反向学习和柯西分布分别进行优化的策略。

(1) 种群初始化。蝗虫算法中初始解是随机产生的,因此容易导致算法产生最优解无法均匀地分布在空间中,从而限制了算法的求解效率,降低了算法的性能。反向学习[30]是一种适合种群优化的机器学习策略,它通常在算法的每一次迭代中得到这些当前解的反向解,并从每一次的当前解和反向解中选择出有利于进化的解,进一步降低算法的盲目性,扩大了搜索空间,提高算法的全局搜索能力。算法过程如下:

步骤1随机生成初始种群。随机生成蝗虫算法的初始种群NP1={x1(t),x2(t),…，xW(t)},其中对应的个体的解计算为：

(16)

(17)

(18)

由式(18)可知反向学习法使得算法能在更大的搜索空间中进行搜寻,且能够引导个体向着最优值方向进化,从而提高了算法的整体收敛速度。

(2) 线性递减系数优化。线性递减参数的作用主要用于平衡局部和全局开发能力,其表达式中除迭代变量k以外,其余都是固定的数值。因此该线性递减参数的数值随着迭代次数的变大而逐渐变小,如果递减参数数值过小或者过大都不利于局部和全局能力的平衡,因此需要对迭代递减系数进行优化,使得该系数能够很好地进行平衡。柯西分布[31]是一种具有两翼均衡特性的函数,公式如下：

(19)

在线性递减表达式中对迭代次数引入柯西分布,能够更好平衡和全局之间的能力,因此,线性递减参数表达式优化如下:

(20)

2.3 个体编码

本文将改进后的蝗虫算法用于云计算任务调度中,对蝗虫个体进行编码,将任务调度与蝗虫个体的位置结合起来,对蝗虫个体采用自然数编码方式,该方式简单易懂，能够在操作过程中降低算法的复杂度。蝗虫个体位置的编码长度为子任务的数量,蝗虫个体的维度等于调度的任务数。设有task个任务,划分为m个子任务,云计算下n个资源,因此蝗虫编码表示为n维向量：

P={p1,p2,…，pm}

(21)

式中：pi∈[1,n],蝗虫个体每一维纵坐标表示一个子任务的编号,pi表示分配给此子任务的资源编号。设定task=4,m=10,n=5,即4个任务被划分为10个子任务,分配到5个资源上时,蝗虫个体的编码为(1,2,5,3,3,4,2,1,5,4)。如表1所示,该蝗虫个体代表了一个可行的调度方案,因此对蝗虫个体的解码能够知道任务分配情况,如表2所示。

表1 蝗虫个体编码示例

表2 蝗虫个体解码示例

2.4 优化目标函数设计

(22)

(23)

(24)

由于本文所求的云计算任务目标函数要获得最小值，因此需要个体的适应度函数越大(即优秀的个体)，本文的目标的适应度函数值如下：

(25)

该目标函数强调了虚拟机负载、成本和时间三个指标在云计算任务中具有相等的作用，因此能够较为客观地反映出用户对云计算任务调度服务进行评价，通过求解最优的蝗虫个体位置而获得最优的云计算任务调度方案。

2.5 调度流程

步骤1初始化蝗虫算法及其他相关参数,将云计算任务调度方案与蝗虫个体进行一一对应,设定最大的迭代次数。

步骤2对蝗虫算法的种群按照反向学习进行初始化。

步骤3对蝗虫算法的递减系数采用柯西分布思想进行更新。

步骤4计算蝗虫个体对应的任务的目标函数值。

步骤5将任务目标函数值和上一次迭代中的目标函数值进行对比，如果小于上一次迭代的结果则取代原来蝗虫个体位置，否则保持不变。

步骤6当迭代次数小于最大迭代次数,转步骤3,否则转步骤7。

步骤7输出最优适应度蝗虫个体位置,即为最佳的云计算任务方案。

3 仿真实验

为了进一步说明IGOA在云计算任务调度下的效率,选择与基本GOA、PSO、ACO进行对比。一方面对比了任务适应评价函数值中的优劣,另一方面对比了不同任务数量下的虚拟机负载、花费时间和成本花费等指标。硬件选择CPU为酷睿i3,内存为4 GB/DDR3,硬盘容量为1 000GB,软件环境为Windows 7系统,MATLAB 2012仿真软件。设置最大迭代次数为200,种群规模为20,搜索维度为90,对比算法的主要参数如表3所示。设定两种任务集合,分别是大任务数量为[1 000,10 000],小任务数量为[10,100]。

表3 对比算法的参数

3.1 云计算任务调度评价函数对比

图2显示了四种算法的云计算任务调度评价函数的对比结果。IGOA相比于其他三种算法首先趋于稳定,这说明了IGOA具有良好的性能,同时在评价函数结果的对比上，IGOA明显低于其他三种算法,这说明IGOA用于云计算下的任务调度具有良好的效果。

图2 四种算法的任务评价函数值

3.2 实验结果

(1) 虚拟机负载。本文设定10个资源对应分别处理两种情况下的任务,四种算法使用虚拟机的负载对比情况如图3-图4所示。图3中的四种算法在不同的资源节点的情况下负载率数值几乎相差不大,甚至在有些资源节点的调度中,IGOA并不具备十分明显的优势,这说明小任务情况下的四种算法虚拟机负载差别不大。图4中的四种算法在不同资源节点下的负载比例相差比较大,IGOA相对于GOA、PSO和ACO的负载率比例分别提高了9.06%、24.2%和26.7%,这说明经过种群初始化和递减系数优化的IGOA的性能明显优于以上三种算法,能够在处理大任务的时候能够发挥虚拟机的性能,提高任务调度效率。

图3 小任务下的四种算法虚拟机负载对比

图4 大任务下的四种算法虚拟机负载对比

(2) 完成时间对比。图5-图6显示了四种算法在不同任务数量下完成时间的对比结果。图5中的四种算法的执行时间都会随着任务数量的增加而呈现上升趋势,四条曲线总体上比较平稳,而且相互之间时间差别不大,IGOA占据微弱的优势。图6显示了大任务下的四种算法的完成时间对比,可以发现IGOA的时间曲线的增加趋势相比于其他三种算法更加平缓,完成时间明显优于其他三种算法,这说明递减系数采用了柯西分布优化后,提高了局部搜索和全局搜索能力,因此在完成时间具有一定的优势,IGOA相比于GOA、PSO和ACO时间分别节省了17.15%、37.8%和54.8%,这说明IGOA在大任务调度中的完成时间上获得比较满意的结果。

图5 小任务下的四种算法完成时间对比

图6 大任务下的四种算法完成时间对比

(3) 成本消耗对比。图7-图8显示了四种算法在不同任务数量下的成本消耗结果,图7中四种算法的成本消耗曲线随着任务数量的增加而逐渐上升,四种算法之间成本消耗数值相差不大。图8中四种算法的成本消耗曲线随着任务数量不断增大而逐步上升,IGOA在任务数量的初期与其他三种算法相差不大,随着任务数量不断地增加,IGOA成本消耗曲线数值上升趋势低于其他三种算法,这说明IGOA通过种群初始化后提高了算法性能,降低了自身的成本消耗，相比于GOA、PSO、ACO分别降低了9.13%、12.4%和24.6%,这说明IGOA在大任务条件下具有一定的成本优势。

图7 小任务下的四种算法消耗成本对比

图8 大任务下的四种算法消耗成本对比

4 结 语

针对云计算中任务调度存在效率低的问题,本文提出了采用改进的蝗虫算法进行调度。从实验结果来看,相比于蚁群算法、粒子群算法和基本蝗虫算法而言,IGOA在均衡负载、完成时间和消耗成本上都具有一定的优势,尤其是在大任务方面的优势比较明显。这主要是由于在种群初始化和线性递减系数两个方面进行了优化使得算法性能得到了提高。但是当任务数量较小的时候,IGOA在成本消耗上处于一定的劣势,这将是下一步研究突破的重点,纵观整个调度过程,本文提出改进的蝗虫算法比较适合大任务下的云计算任务调度。