基于IPSO_CS的云资源调度算法仿真研究

李新飞, 谢晓兰,b

(桂林理工大学 a.信息科学与工程学院; b.广西嵌入式技术与智能系统重点实验室， 广西 桂林 541006)

0 引 言

云计算是大规模分布式计算和并行处理的一个新的视角，它以按使用付费的方式提供服务[1]，是一种从任务集中的云计算模式[2]发展，可以提供大规模分布式资源并进行协同计算的超级计算服务。网络“云”将分解后的小块计算机程序数据使用在多部服务器组上，在处理和分析后服务于用户，而任务调度的效率成了云计算中最迫切需要解决的问题。

随着应用程序计算需求以及用户需求的快速增长，计算资源不断增多，任务调度作为组合优化问题在考虑如何及时、高效地进行任务分配以及合理利用资源、提高资源利用率方面起着十分关键的作用。任务调度就是综合考虑任务完成时间、负载均衡和服务质量等因素，将用户任务匹配给合适的虚拟计算资源，所选用的任务调度优化算法直接影响着任务分配的效率，算法的优劣程度影响着减少总任务执行时间。智能优化算法在解决任务调度问题方面非常有效，可以显著降低搜索复杂度，增大搜索空间，在模拟自然过程中解决全局最优解问题。粒子群算法以及其各种优化算法作为智能优化算法的典型，虽然应用领域纷杂、起源很久但由于其简单容易实现且没有许多参数而被广泛使用。

在考虑到粒子群及其优化算法的优势和云计算环境下巨大的资源数量，以及种群初始化和莱维飞行搜索的随机性造成不稳定性而产生的结果随机性，对任务的执行时间进行算法稳定性分析判断，从执行时间和成本出发提出了一种改进的粒子群布谷鸟算法(Improved particle swarm cuckoo algorithm，IPSO_CS)，采用非线性自适应惯性权重代替提高种群多样性；引入布谷鸟搜索(cuckoo search)中模拟捕食者狩猎的莱维飞行机制增加粒子位置变化的活力，调整搜索范围的步长因子，增大靠近精英解的概率，以及tent混沌扰动打破局部最优的状态。仿真结果表明，其可以很好的解决算法的早熟收敛、搜索效率低、结果随机等问题，相较与其他 PSO 具有更优的性能。

1 研究背景

云计算环境下的任务调度作为数学七大难题之一的NP完全问题[3]，最优解的获取适合如灰狼算法、粒子群算法、禁忌搜索[4]、烟花算法等相关智能改进算法来逼近最优解。文献[5]中在编码方式采用间接编码进行改进，优化相关参数设置且在任务调度的效率方面有所进步。文献[6]中为加快搜索速度以及减少云计算任务执行时间引入局部及全局信息深度更新的方法来改进蚁群算法。文献[7]中的双适应度遗传算法 (Double fitness genetic algorithm，DFGA) 考虑任务完成时间和任务平均完成时间双适应度。文献[8]中提出一种优化的多目标粒子群算法(Optimize multi-objective task scheduling particle swarm algorithm，MOTS-PSO) ，分别给予任务总执行时间、总传输时间和单节点执行代价不同的权重建立多目标优化模型，解决传统粒子群算法收敛速度慢和精度低等问题，实验证明算法效果更优。文献[9]中在多目标方面提出一种遗传与粒子群算法融合多目标任务调度算法，将粒子群和遗传算法的优势结合起来，针对调度策略不能满足用户需求的问题进行多目标优化。文献[10]中在tent映射的自适应混沌粒子群的任务调度问题研究中引入混沌优化策略，以其混沌运动的随机遍历优势解决粒子群(PSO)算法迭代后期易陷入局部最优的缺陷。文献[11]中将蚁群算法优势、多维服务质量约束、遗传算法优势相结合提出了一种云计算多QoS约束云计算任务调度算法(Multi-QoS with genetic and ant colony optimization algorithm，MQoS-GAAC)，将用户的服务质量作为适应度函数，采用动态融合策略确定蚁群算法和遗传算法的最佳融合时间，不仅提高了用户服务质量，而且保持了资源负载均衡。文献[12]中研究证明粒子群算法与遗传算法相比在云计算环境中调度效果更好。以上工作考虑到的目标单一、早熟收敛或多目标优化等问题，可以看出PSO 更适合云计算中的资源调度。本文在考虑到以上工作各方的优势后提出一种结合粒子群算法和布谷鸟搜索的(IPSO_CS)改进粒子群算法进行任务调度，经仿真结果证明比其他PSO算法调度效果更优。

2 云资源调度问题

云任务调度采用映射/规约模式将任务分配到资源节点上，达到任务完成总时间短、服务质量好等需求。云任务被分解为若干个相互独立的子任务[13]后，各子任务随机分配给并行的资源计算节点上执行、整合、输出，适合于大规模数据的处理，工作效率高。

调度模型及适应度函数

作为云计算环境下的任务集合T={t1，t2，…，tm}，表示在当前时刻共有m个执行过程中不可阻断的相互独立任务。VM虚拟机资源集合VM={vmm1，vmm2，…，vmmn} ，n为虚拟机资源数量。在资源节点上预期完成时间的完成情况：

(1)

式中,etcij为相应虚拟机处理速度下任务长度的完成时间。本文云计算任务调度目标旨在尽可能使任务完成时间time最短，任务分配到虚拟机上的总完成时间模型

(2)

任务在虚拟机上占用各种资源的执行成本模型如下：

(3)

式中：Time(i,j)为虚拟机i上任务j的执行时间;k为任务个数;Ci为单位时间虚拟资源的费用。这里的费用包括3个方面：带宽、内存、CPU，单位为MB。

本模型为使任务完成时间Time和执行成本C最小，采用线性加权计算的适应度函数，分配不同指标不同权重：

Fitness=f1Time+f2C,f1+f2=1

(4)

Fitness作为本文优化目标也作为适应度函数，其值越小，算法性能越好，在实际应用中，任务调度作为实际问题，还需要考虑负载均衡、能耗等因素。

由于种群初始化和莱维飞行搜索的随机性会造成结果的不稳定性，对任务的执行时间进行算法稳定性的分析判断。方差D(n)作为样本偏离程度即数据波动程度可以判断结果的稳定性：

(5)

从执行时间、执行成本、稳定性进行多方面分析作为本文任务调度模型的判别标准。

3 IPSO_CS算法

3.1 基本粒子群算法

标准粒子群算法[14]是在动物集群活动行为的基础上，通过最佳个体体验(pbest)和群体中最佳群体体验(gbest)在问题求解空间中进行演化，使得种群逐步趋于最优。基本粒子群算法由于其简单，易实现等优点被广泛应用。在n维搜索空间算法模仿m个粒子的群体以基于自己和其他粒子最优位置的基础上进行搜索飞行和位置更新，Xi=(xi1，xi2，…，xin)为第i个粒子的位置，速度Vi=(vi1，vi2，…，vin)。制定相应适应度函数后计算群体内各粒子的适应度值，以最佳个体体验(pbest)和群体中最佳群体体验(gbest)对群体内每颗粒子的速度和位置进行更新:

vi,j(t+1)=Wvi,j(t)+c1rand1[pi,j(t)-xi,j(t)]+

c2rand2[pg,j(t)-xi,j(t)]

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1),

(7)

j=1,2,…,n

式中：W为惯性权重，用于提高算法的收敛性;c1、c2为加速度常数控制个体和全局最佳粒子效果的特定参数；rand1、rand2为随机数函数，用于在粒子运动时提供在[0，1]范围内的随机量[15]，以控制粒子在搜索空间中的运动。

3.2 粒子编码

在云环境中应用粒子群算法时，待分配子任务作为离散值需要对粒子进行编码，通过编码结合任务调度与粒子位置和速度，对粒子个体采用自然数编码。设有m个任务，分配给n台虚拟机，粒子种群规模为NP，每个粒子的位置由向量Z表示，则第i个粒子可编码为m维向量Zi=[zi1，zi2，…，zim]，zij的取值在0～n+1之间的随机整数，每一维分量表示分配给此任务的虚拟机，比如最优解若为(2,5,3,…)，则表示虚拟机2接受任务1，虚拟机5接受任务2，虚拟机3接受任务3等。粒子速度则由向量v表示，第i个粒子的速度表示为vi=[vi1，vi2，…，vim]，vij为-n到n之间的随机数。

3.3 算法改进策略

(1) 非线性自适应惯性权重。粒子群算法的惯性权重W作为重要的进化参数是由Shi等提出，也叫惯性因子，决定了先前状态粒子对当前状态的影响。通常采用的典型线性递减[16]策略。在迭代前期由于需要较大的全局搜索能力，需要赋予较大的惯性因子，用以丰富种群多样性和搜索的随机性，而后期需要较小的惯性因子聚焦局部搜索能力。在平衡优化粒子搜索能力时，本文采用随迭代次数自适应的非线性惯性权重策略，对比实验结果表明，改进后的自适应非线性惯性权重效果更好，且随着算法不断迭代，惯性权重值动态改变：

(8)

式中：W为惯性因子,其最大最小值分别为0.9、0.4；d作为迭代次数，最大值为dmax。改进后的自适应惯性权重从最大的惯性因子随迭代次数自适应降到最小惯性因子，不仅解决了后期收敛速度慢的问题，前期更是扩大了搜索的随机性。

(2) 布谷鸟搜索。Yang等提出的布谷鸟搜索算法是一种受布谷鸟繁殖行为和levy飞行策略启发的元启发式全局优化方法，是一种模拟自然界布谷鸟提高生存机率的繁育行为和莱维飞行特性形成的有效搜索策略。莱维飞行机制是通过随机游动和偏好随机游动的短步长与长步长相间行走用以达到平衡整体和局部寻优有效性的方式，在平衡寻优方面，Long等在莱维飞行中加入了动态自适应步长因子[17]。改进后算法全局搜索位置和路径的更新

(9)

式中：Xt，Xt+1为t时刻和下一时刻粒子i位置；“⊕”为点对点乘法；ɑ为改进步长因子。改进的随粒子变化自适应调整搜索范围的步长因子，引导粒子靠近种群最优解即精英解：

(10)

服从λ的莱维分布的随机搜索路径：

Levy～u=t-λ

(11)

Mantegna算法模拟随机步长十分复杂且难实现的莱维飞行，其数学表达如下：

(12)

式中：s为步长;u、v为服从正态分布的两个随机数;β通常取1.5。

(13)

Г(x)定义如下：

(14)

服从莱维飞行的粒子运动轨迹模仿动物的捕猎行为，这种行为为其随机广泛的搜索能力奠定了基础。

(3) tent混沌改进。为避免早熟收敛且高效优化此改进算法，引入tent混沌扰动，这种自然界看似很普遍的非线性混沌现象，以其随机性特点不重复遍历所有状态达到解决收敛速度慢、寻优精度差等问题，在保证多样的种群的条件下，增强了其跳出局部最优的情况，平衡了全局和局部的搜索能力。单梁等[18]研究表明，Tent 映射的遍历均匀性和收敛速度均优于 Logistic 映射，引入tent混沌扰动粒子，当粒子全局最优收敛到某个值持续不变超过设置的监测值limit时，对粒子的速度进行扰动，改变其搜索方向和距离，引入混沌跳出局部最优解[19]，避免陷入早熟的僵局。本文采用以下tent混沌公式：

(15)

将产生的混沌扰动量载入到粒子速度的更新中。

(16)

式中：Vi+1为扰动后的新的个体速度;rand为服从正态分布的随机数；Si+1为产生的混沌扰动量；S为随机产生的(0,1)内的初值。设定粒子最大飞行速度Vmax代替超出上限的速度值。利用混沌函数将产生的新的扰动变量附加到迭代到监测值limit时的粒子速度上，改变粒子的运动方向，得到新的扰动后的粒子状态。

(4) IPSO_CS算法描述。IPSO_CS算法步骤如下

步骤1初始化种群大小及各项参数等。

步骤2依据改进式(8)改进迭代的自适应权重参数w。

步骤3计算可行粒子执行时间适应度值，确定最佳个体体验pbest和群体最佳群体体验gbest。

步骤4将当前适应度值进行比较更新pbest、gbest。

步骤5粒子迭代过程开始，依据式(7)、(9)进化粒子群位置。

步骤6全局最优收敛值迭代次数超过监测值limit，依据式(16)改进粒子速度。

步骤7判断是否满足终止条件，否则转步骤3。

4 仿真实验分析

4.1 仿真实验过程

本文采用云仿真软件cloudsim工具包对该调度策略进行仿真，任务数设置为[50，100，200]，迭代次数[200，500]，将改进后的(IPSO_CS)算法与(PSO)算法、(SAPSO)算法仿真比较。表1、2分别为本文硬件实验环境配置参数和调度算法参数配置。

表1 硬件实验环境配置

表2 调度算法参数配置

4.2 仿真结果及分析

将3个算法从任务调度策略和最终结果进行仿真对比分析。

(1) 任务调度策略分析。为确保数据的可靠性，对每组任务进行仿真后取平均值得到最终的结果。不同任务数下任务完成时间随迭代次数的变化如图1(a)～(c)所示。

由仿真结果可见，IPSO_CS在3种不同的任务数量下收敛能力和调度寻优能力都比PSO和SAPSO更好。SAPSO算法完成任务总时间比IPSO_CS和PSO相差较多，图1(a)所示在任务数量较少迭代次数200内，SAPSO没有趋于稳定，算法收敛和寻优效果差，PSO和IPSO_CS总体的任务完成时间非常贴近，迭代初期100次左右IPSO_CS趋于平缓，PSO在迭代140时趋于平缓。在结合了CS搜索后粒子位置活力更活跃，加快了寻优的能力。图1(b)为改进算法在后期较好的寻优能力，在迭代次数250之前与PSO算法接近，但SAPSO算法效果整体较差。图1(c)展示了在较大规模下，3种算法的收敛和寻优能力，在迭代300次左右，3种算法都趋于平稳，在粒子搜索增加CS的动物捕猎行为的模仿后IPSO_CS除了在较早的迭代初期调度效果不佳之外，总体优势在迭代50次后体现出来。

(a) 任务数50完成时间

不同任务数量下任务完成成本对比如图2所示。

执行成本的相差不是太大，尤其是IPSO_CS与PSO，但是IPSO_CS在总的费用上要优于PSO和SAPSO，也就可以看出其分配方案更合理，效果更好。

(2)仿真结果稳定性分析。除任务完成时间和费用对比，对50个任务和200个任务的完成时间选取8组值绘出图3、4所示的稳定性对比[20]，观察得出IPSO_CS曲线波动较小且总体值小于PSO和SAPSO，说明种群初始化和莱维飞行搜索的随机性对IPSO_CS的影响较小，本文方案在执行时间上相对稳定。

图3 任务数50执行时间稳定性对比

图4 任务数200执行时间稳定性对比

综上，通过不同规模条件下的仿真，本文的优化IPSO_CS调度算法相比于PSO和SAPSO缩短了系统任务调度完成总时间和费用，在算法收敛、搜索能力、稳定性、调度效果方面都取得了较好效果，总体上保证了样本多样性，在资源调度方面寻优更好。

5 结 语

传统PSO在进行云资源调度时容易出现早熟收敛、搜索效率低、结果随机等问题。本文提出的一种基于标准粒子群算法改进的资源调度算法(IPSO_CS)，在增加粒子位置变化活力搜索精英解以及打破局部最优的状态，缩短任务执行时间和成本上，比标准 PSO 算法和SAPSO算法更好，调度策略上更优。仿真结果表明，其可以很好地解决算法的早熟收敛、搜索效率低、结果随机等问题，相较与其他 PSO 具有更优的性能。本文所提出的调度策略能够较好的解决云计算中资源调度分配问题。