云计算资源的动态随机扰动的粒子群优化策略

喻德旷，杨 谊，钱 俊

(南方医科大学 生物医学工程学院，广州 510515)(*通信作者电子邮箱yiyang20110130@163.com)

0 引言

云计算通过虚拟化技术将网络计算资源整合在一起，组成一个庞大的计算节点池，用户通过浏览器按需获得资源，完成数据处理任务[1]。网络计算资源庞大且分散，要根据用户请求将资源动态地分配给各个任务，就需要进行合理的资源调度。任务调度策略对用户任务的执行效率、系统资源的使用效率、任务执行成本、负载均衡、系统稳定性等均有直接的影响[2]。云计算环境中的资源具有动态性和异构性，对大规模任务进行资源分配和调度时，不仅需要最小化完成时间和提高系统使用率，而且要考虑资源负载均衡、服务质量，是一个非确定性多项式(Non-deterministic Polynomial, NP )问题[3]。

针对云计算资源调度问题，国内外学者进行了大量的研究，提出了许多调度策略，根据算法原理可分为三大类。第一类是静态资源调度策略[4]，如数学规划、专家系统、神经网络和模糊逻辑策略，这类方法的优点是规则严密、逻辑清晰，但是规则较为复杂，只适合小规模资源的静态调度。第二类是传统动态资源调度策略，包括基于贪心思想的策略(Min-min算法、Max-min算法、Sufferage算法等)[5]和基于操作系统调度的策略，如FIFO(First In First Out)算法、公平调度算法、计算能力调度算法等[6]。这些策略可以实现资源动态调度，但由于参与操作的因子很多，用于大规模任务调度计算复杂度太高。第三类是启发式策略，主要包括遗传算法和粒子群算法[7]。例如，文献[8]提出了一种基于模拟退火思想的改进遗传算法，在退火过程中以一定概率接受劣质解从而避免调度早熟现象；文献[9]在遗传算法基础上,提出了一种考虑多维约束的任务调度算法MCGA(Multiple Constraints based on Genetic Algorithm)，在算法的编码与解码、适应度函数、交叉变异等操作环节上进行了改进；文献[10]建立了多目标优化模型，并结合最新的径向基函数(Radial Basis Function,RBF)神经网络和粒子群优化(Particle Swarm Optimization, PSO)算法对其求解；文献[11]改进了PSO的搜索方向、适应度函数等方面；文献[12]将粒子群算法和差分遗传算法结合求解；文献[13]设计了双向搜索的改进粒子群算法等。

1 动态随机扰动PSO策略的基本思路

从以上分析可知，相对于传统任务调度策略，启发式任务调度策略在求解NP类问题时具有更高的自适应性和灵活性：实验表明，模拟退火算法体现了贪心(Greedy)策略，在搜索到局部最优解后，会进行扰动，以一定的概率接受一个比当前解要差的解，进而有可能跳出局部最优解，找到一个比当前解更好的解。但贪心策略往往不能达到全局最优解，扰动幅度和时机不容易控制，并且在并行性方面较弱。PSO算法具有参数设置少、全局搜索能力强等优点，其并行性和分布式的特点能够处理海量数据，较为适合作为云计算资源调度策略。但PSO在迭代后期随着种群多样性的降低，往往陷入局部最优而错失全局最优解。遗传算法(Genetic Algorithm, GA)从问题解集开始搜索，而不是从单个解开始，通过对不同解的组成进行交叉或修改，能够有效地提高解的组成的多样性，利于全局择优，且具有并行优势，覆盖面大。GA采用概率规则来指导搜索方向，比确定性规则具有更好的自适应和自学习性，但是概率筛选规则存在机会风险，获得的解是不稳定的。从这些分析可以知道，采用单一算法处理大规模计算资源分配，得到的结果往往不是最优或稳定的。本文利用PSO与遗传算法本身的优点和对大量资源调度的适应性，将二者结合起来，设计了基于随机扰动的优化技术的群体智能混合策略，来提高云计算任务调度的综合效率，减少任务执行时间、降低计算成本，并改善负载平衡。

本文提出动态随机扰动的PSO(Dynamic Random Distribution PSO, DRDPSO)策略如下：首先建立云计算资源调度模型；改进PSO算法，将其惯性权重常数修改为变量，使得求解过程的搜索不是匀速而是可控变速的；在每次迭代中以局部范围代替全局范围，减少盲目搜索操作；在PSO算法内引入遗传算法的选择操作，筛选出更优质的个体并传递到下一代，并引入变异操作实现随机扰动，试图改善粒子组成，提高粒子多样性；结束条件体现了多重约束的合理运用。

1.1 建立云计算资源模型

云计算的系统资源是有限的，如何为用户任务合理地分配资源，使各个计算节点达到负载均衡，是整个服务过程中需要考虑的问题。为了突出调度问题而减少其他因素干扰，本文约定：所有任务都具有原子性(不再可分)；多个任务可以同时在数据中心的计算节点(虚拟机)上执行；每个计算节点都可分配给任何一个任务(任务没有计算特殊性)；根据计算能力一个计算节点可以只接受一个任务或同时接受多个任务；不考虑任务切换、传输等时间耗费。对模型参数进行如下定义：

1)任务集合T={t1,t2,…,tm}，由m个相互独立的原子任务组成。

2)计算节点集合CN={cn1,cn2,…,cnn}，由n个计算节点组成，每个计算节点采用如下属性线性表形式描述：cni={CPU,MEM,DISK,…}，CPU表示内核数，MEM表示内存大小，DISK表示磁盘空间大小，可根据需要增加或删除属性元素。

3)决策矩阵D={dij},i=1,2,…,m,j=1,2,…,n,dij∈{0,1}，dij=1 表示第i个任务在第j个计算资源上执行；dij=0 表示第i个任务不在第j个计算资源上执行。

4)执行时间矩阵ExeTime={etij},i=1,2,…,m,j=1,2,…,n,etij表示第i个任务在第j个计算资源上完成所需要的时间。

5)计算成本矩阵CalCost={calcij},i=1,2,…,m,j=12,…,n,calcij表示第i个任务在第j个计算资源上完成所消耗的资源成本(CPU、内存、外存)。

6)总时间成本(Execute Time Cost, ETC)和总计算资源成本(Calculate Resource Cost, CRC)。

(1)

(2)

云计算资源调度目标包括：所有任务完成时总的执行时间最小，总的资源占用最少，即使得式(1)和/或式(2)取最小值。实际应用中，式(1)、(2)同时获得最小值的概率较小，可以根据实际需要赋予总时间成本和总计算成本以不同的权重如式(3)：

TotalCost=μ1ETC+μ2CRC

(3)

如侧重时间成本，则μ1取较大值；若侧重计算成本，则μ2取较大值，目标是综合代价TotalCost最小。

在本文实验中，云计算资源模拟环境下ETC和CRC为同一数量级，如果在其他应用场景下这两个变量不是同一数量级，则应当进行归一化处理后再加权累加。

1.2 动态随机扰动PSO策略

PSO算法初始化为一群随机粒子，代表随机解。所有的粒子都具有速度属性，在每一次迭代中，每个粒子通过跟踪两个值来更新自己的速度和位置：一个是粒子本身所找到的最优解lBest，另一个是整个种群目前的最优解gBest。每个粒子根据适应度函数来判断自己当前是否到达最优解的位置。粒子之间利用信息共享进行从无序到有序的演化，从而获得全局最优解。

1.2.1 简化的编码设计

通常粒子群算法和遗传算法可以采用两种编码方法：实数编码法和二进制编码法。前者表示形式容易理解，解码简单；后者能够表示多样化的种群，但占用存储空间较大，解码过程难以理解。为了提高策略可读性和一致性，本文采用实数编码法对粒子进行编码。每个粒子表示任务与资源的对应关系，如粒子{(1,3)，(2,2)，(3,4)，(4,3)，(5,1)}表示任务1分配到资源(计算节点)3上、任务2分配到资源2上、任务3分配到资源4上等。在同一时间窗口内的任务的数量决定了编码的长度，上例中的粒子的长度为5。

1.2.2 改进的粒子更新策略为“前快后慢”

设群体粒子集合(即解的集合)为X={x1,x2,…,xs}，s为解空间规模，粒子xi(i∈[1,s])在t时刻的位置为pi(t)，此时单个粒子的最佳位置为lbest_p(t), 当前群体的最佳位置为gbest_p(t)，粒子xi运动的速度公式为：

vi(t+1)=w×vi(t)+c1×(lbest_p(t)-pi(t))+

c2×(gbest_p(t)-pi(t))

(4)

位置公式为：

pi(t+1)=pi(t)+vi(t+1)

(5)

其中:w为惯性权重常数;c1和c2为常系数。

在实验中发现，由于速度更新率即式(4)中的惯性权重c1和c2设置为常数，使得求解过程中收敛速度保持不变。而实际的解搜索往往需要在早期进行快速的大致定位，在后期放慢速度在确定的候选区域内进行比较仔细的搜索，因此本文将惯性权重修改为变量，根据经验设计如下：

(6)

其中:IterNum为算法的总迭代次数;IterNow为当前迭代次数;k1和k2为常数，一般取值在1～2，其比例关系为1∶1;fit(t)为t时刻群体的适应度函数值。惯性权重的初始值默认为1。

式(6)体现了对粒子运动变化速率的合理控制，惯性权重变化受到两个因素的影响：

一是迭代次数。迭代过程中粒子的更新速度应当是前快后慢，这是由于起始点是随机解，应当尽快收敛到全局最优解可能处在的小区域中，所以收敛速度要快；而后期则应当在确定的小区域内进行较为细致的搜索，所以收敛速度要慢。按照经典算法，收敛速度一直是常量，将不利于提高收敛速度，也不利于在最可能产生最优解的区域细致搜索。

二是适应度(综合代价TotalCost)。根据前面分析的云计算资源调度目标和所涉及的衡量指标，本文策略的适应度函数主要由式(3)决定，即同时考虑总的执行时间和总的资源开销。此外，各台服务器节点的负载平衡度不应差异过大，否则会造成某些节点压力重，容易出现瓶颈，而某些节点的资源得不到有效利用，因此本文定义了负载均衡指标。云平台中某个计算节点j的负载均衡因子LBj定义为：

(7)

其中μ1和μ2为权重参数，其他参数含义同前面介绍。

负载均衡度反映了调度策略对计算资源利用的公平性和均衡性。定义负载均衡度τ为：

(8)

由于τ和适应度函数值TotalCost在数值上往往不是同一数量级，在不同类型的任务中也难以归一化，所以解的优良性的判断规则为两个：优先依据TotalCost选择局部最优解；如果存在多个局部最优解，则根据负载均衡度τ判断，取τ最小的解。也就是说在综合代价最小的前提下兼顾负载均衡。

1.2.3 缩小搜索范围

由于粒子在上一时刻的最佳位置直接影响到下一时刻的最佳位置的选择，不必每次迭代都重新搜索整个种群，所以本文用t-1时刻gbest_p(t-1)粒子的若干个邻居中的最佳位置(邻居数量NeighNum根据经验设置，通常为总粒子数量的1/3)，取代t时刻整个种群的最佳粒子位置作为gbest_p(t)的值，从而减少大量无效的搜索和比较，降低计算代价，提高计算效率。如果最佳位置确实需要发生大的偏移，则可以通过适应度函数控制，函数值的改变能够调整粒子运动的范围(发散或收敛)，越靠近当前最佳位置的粒子下一步的搜索范围应当收敛，反之应当发散。

1.2.4 引入遗传算法的选择和变异操作

遗传算法也属于搜索启发式算法，从完全随机个体的种群开始，选择多个适应度较高的个体，通过选择、交叉和突变产生新的生命个体，构成下一代种群。选择运算的作用是把优质的个体基因直接遗传到下一代；交叉运算则交换两个个体的若干基因，产生新的个体；变异运算是对个体的某些基因位点作修改，产生新的个体。迭代结束时，以进化过程中所得到的具有最大适应度个体作为最优解输出。

资源调度求解的搜索过程中也会出现某些时刻粒子的相似度高，而不利于发现更优解的现象。因此本文在改进的PSO过程中引入遗传算法的选择和变异操作。在每一代中选择一定比例的优质粒子，即Ntop个适应度最高的粒子即优质粒子(Ntop根据经验设置为粒子总数的1/10)，直接进入下一代。对于其他的粒子则执行随机变异操作，具体做法是对t时刻随机选取的非优质粒子xi的第j个分量xij(t)按照随机概率φ(i,j,t)进行随机变异，变异率定义如下：

(9)

其中，σ取值范围是(0,1)，一般取[0.6,0.8]。例如，σ取值为0.7，对于粒子{(1,3)，(2,4)，(3,4)，(4,3)，(5,1)}，某个时刻的j=3的分量的变异概率rand为0.8，变异后的新的对应资源编号为资源集合中的随机值(假设计算得到1)，如果编号1的资源能够满足任务3的需求，则实施变异为{(1,3)，(2,4)，(3,1)，(4,3)，(5,1)}，否则不执行变异操作。通过变异操作，改变粒子的基因组成，从而有可能将适应度较低的粒子进行优化，但是也不排除变异操作导致粒子的适应度降低的情况。以上的变异操作实质上也是一种随机扰动技术，可以防止算法过早地陷入局部最优解。

遗传算法中的交叉操作也能够提高基因的多样性，减少陷入局部最优的可能，但粒子之间基因的交叉可能导致多个任务需求与资源的连锁不匹配，而判断更新后的任务和资源是否匹配，会大大增加算法的复杂性，所以本文没有盲目采用遗传算法的交叉操作，而是用随机变异的扰动技术来达到目的。

1.2.5 算法结束条件综合考虑多个指标

本文把分配成功的指标(TotalCost，运行时间少，计算资源占用少)和计算公平指标(τ，节点的负载均衡度)结合起来，这使得本文策略的综合性能更好。实际上这些指标不可能同时达到最优，因为它们之间存在相互冲突性。在解决实际问题时，往往达到需要的综合最优就可以了。结束条件表示为：当t时刻粒子集的适应度函数与上一时刻相比不再增加(近似)，或者迭代次数到达了一个上限，就令算法结束。形式化设置为：(presumption1)t时刻的适应度(综合代价)TotalCost与t-1时刻相比，增加率小于阈值εc，且t时刻的负载均衡度τ与t-1时刻相比，降低率小于阈值ετ；(presumption2)达到最大迭代次数IterNum。

1.2.6 DRDPSO策略流程

Step1 初始化种群，随机生成符合任务-资源约束条件的粒子编码，设置最大迭代次数、解规模等参数的初值。

Step2 初始化粒子局部最优和全局最优值。

Step3 根据式(3)、(6)，更新式(4)、(5)，即更新所有粒子的速度和位置。

Step4 根据适应度函数式(3)计算各个粒子的适应度和群体适应度(群体搜索范围控制在NeighNum而不是所有粒子)，根据式(8)计算负载均衡权值。

Step5 若满足结束条件(presumption1)，则输出当前解，并结束；否则，若满足条件(presumption2)，则输出当前解，并结束；若不满足条件(presumption1)，也不满足条件(presumption2)，转到Step6。

Step6 对当前群体Ntop个适应度最高的优质粒子直接进入下一代。按照式(9)概率对非优质粒子进行选择和随机变异操作，生成下一代群体；转到Step3。

1.2.7 算法复杂度分析

经典PSO算法每一次迭代中的粒子数量不变，记为Nc。设第i次迭代中粒子的数量为Ni(i= 1, 2, …,m) ，m为最大迭代次数，则有Ni=Nc。设每个粒子每一次迭代需要的运算时间为Ti，则经典PSO算法总的运行时间为O(Nc*Ti*m)。本文DRDPSO策略将群体搜索范围控制在NeighNum而不是所有粒子(NeighNum根据经验设置，通常为总粒子数量的1/3)，即搜索范围缩小至原来的1/3，且随着迭代的进行，后期符合条件的粒子的数量还会逐渐减少(非单调)。设每个粒子每一次迭代需要的运算时间为Ti，则本文DRDPSO策略总的运行时间为O(Ni*Ti*m)，其中Ni≤1/3Nc。比经典PSO算法增加的计算式(6)、(8)、(9)均为常数级计算，对时间复杂度带来的增量远远小于搜索范围带来的减量，可以忽略。本文DRDPSO策略改进的效果在运行时间方面主要体现在:每一次迭代中的搜索范围大大减少,参与下一步运算的粒子数大大减少，使得运行时间减少。而增加的计算部分使得对资源调度的评估标准更合理，解的多样性更好。

在空间存储方面，本文DRDPSO策略比经典PSO算法在每次迭代中增加了常量数量级的中间变量如fit(t)、τ、φ(i,j,t)等，以及与之相关的临时变量的存储，但每次迭代搜索范围相比经典算法缩小至原来的1/3，使得临时粒子的保存量也大为减少，所以空间复杂度有所降低。

需要明确的是，本文策略属于启发式搜索算法，这一类算法所获得的解都并不是理论上的最优解。对于诸多 NP-hard 问题，使用确定性算法时间复杂度的代价极大，到不能接受的程度(运行时间很长)，有时候需要保存的中间变量数量也很大，导致空间复杂度也较高。而求解实际问题往往并不需要理论上的最优解，只需要一个满足一定条件、符合工程需求的次最优解就能解决问题。

2 实验结果与分析

本文采用云计算仿真工具CloudSim 进行实验仿真，首先创建数据中心、用户代理和计算节点(虚拟资源)，其次将用户代理与计算节点进行映射，生成云任务集合，在此基础上使用不同的调度策略将任务分配给计算节点。文献[8] 的模拟退火遗传算法(Simulated Annealing Genetic Algorithm, SAGA)和文献[12] 的GA+PSO算法分别对云计算的资源调度问题对标准遗传算法和标准PSO算法作了有特色的改进，并提供了较详细的实现过程，因此作为本文策略的对照算法。在相同环境和条件下将本文DRDPSO策略与SAGA、GA+PSO进行对比实验。计算机仿真实验环境的配置为：Windows 7操作系统，CPU 4核，内存16 GB，硬盘2 TB。

2.1 任务规模单变量实验结果

在任务类型相同的条件下，以任务规模为单变量，分别生成m=100,200,…,1 000个模拟的用户任务，计算资源n取50。本文DRDPSO策略中的参数初始化为：种群规模Size(即粒子的个数，或候选解的个数)初始化为100，Ntop=Size/10=10，NeighNum=Size/3=33，最大迭代次数IterNum=2 000。μ1=4，μ2=1，表示本文更重视总执行时间的优化，而把资源成本放在较次要的位置。c1=c2=1，k1=k2=1，σ=0.7。为了挖掘最优值，体现每次迭代与上一次的细微改变，设置为较小的门限值：εc=0.01，ετ=0.01(实际运行时，根据具体问题域的变化幅度不同，或者为了避免迭代次数过多，总是超过上限，可以根据经验调整为小于等于0.05的值)。SAGA和GA+PSO的公共参数与本文算法相同，其各自的局部变量大部分按原文献设置参数值，但为了在本实验中获取最好的结果，对部分参数值作了适当调整。三种算法在处理不同任务规模下的CPU型任务的性能如图1所示。由于本文算法中多处使用了随机技术，所以同样参数的实验多次运行结果在数值上不完全相同，但是多次实验结果反映出的规律是基本一致的。

图1 不同算法在不同任务规模下的性能比较Fig．1 Performance comparison of different algorithms under different task scales

从图1(a) 可以看出，在任务规模比较小的情况下(规模为100)，本文算法DRDPSO比SAGA、GA+PSO 的最优调度方案所需的总执行时间略大。而随着任务规模的增加，三种调度策略的总执行时间都有增加，本文DRDPSO策略的增加率明显小于GA+PSO，而GA+PSO则略小于SAGA。DRDPSO的总执行时间比SAGA少13.7%～37.0%，比GA+PSO少13.6%～31.6%。上述结果表明本文调度方案能够适应大规模任务调度，在较短的时间内完成用户任务。

由图1(b)可以看出，本文DRDPSO策略与SAGA 在任务规模增加时，资源耗费近似于线性增长，表明这两种策略在任务-计算节点匹配的适应性和稳定性均较好，而GA+PSO的资源耗费波动较大。在大多数情况下DRDPSO的资源耗费比其他两种算法少，随任务规模不同，本文DRDPSO策略的资源耗费比SAGA少9.8%～17.1%，比GA+PSO少0.6%～31.1%。

从图1(c)可以看出，在达到收敛所需的迭代次数方面，文本算法DRDPSO明显少于其他两个算法，且不易受任务规模变化的影响，而另外两种算法在任务规模增大时迭代次数也显著增加，直到任务规模增大到一定程度才停止大幅增加。DRDPSO的迭代次数比SAGA少15.7%～60.2%，比GA+PSO少1.4%～54.7%。文本算法DRDPSO迭代次数出现波动的原因主要来自于φ(i,j,t)的值和每次实验随机产生的任务序列的情况(子任务大小、子任务出现顺序等)，由于适应度函数和负载均衡度等多种指标的共同制约，使得迭代次数较少。同时也看到，在大部分情况下，本文DRDPSO策略的时间耗费没有与迭代次数的减少幅度成线性关系，是每次迭代中增加了用于改进的多个计算导致的。

从图1(d)可以看出，在不同的任务规模条件下，本文算法DRDPSO的负载均衡度总体来看最小，比SAGA减小8.1%～18.5%，大部分情况下比GA+PSO减少2.7%～15.3%，且变化最小。GA+PSO虽然有时获得比DRDPSO更好的负载均衡度，但它的整体性能不够稳定，而SAGA的负载均衡度偏大，表明其对计算节点的利用不够均衡。

2.2 任务类型单变量实验结果

为了比较对不同类型任务的处理效果，将任务划分为三类：1)CPU型任务，占用CPU的比例远大于IO比例(比值大于3∶1)；2)混合型任务，占用CPU和IO比例大致相当(比值介于3∶1和1∶3之间)；3)IO型任务，占用CPU的比例远小于IO的比例(比值小于1∶3)。实验结果表明，三种算法各自在相同任务规模下的性能基本保持一定的规律。以任务规模500为例，三种算法对三种类型任务的平均总执行时间、平均总的资源成本、平均迭代次数和平均资源负载均衡度如表1所示。

从表1可以看出，在总执行时间方面，三种调度策略表现相似，都是对于CPU型任务的总执行时间最多，混合型任务次之，IO型任务最少，显然，这是由于本文定义的适应度函数为综合代价TotalCost，而TotalCost只考虑执行时间和资源占用情况，未考虑任务传输时间(而实际应用也往往不计入任务传输时间，或者认为任务可以预传输，传输时间为常量)。在总执行时间方面，本文策略DRDPSO表现最好。类似的，在占用资源数量方面，三种调度策略对于三种类型任务的总资源成本也呈现与总执行时间相似的规律。在收敛迭代次数方面，本文算法DRDPSO在各类型任务都是最少的，GA+PSO算法适合快速求解混合型任务，SAGA则适合快速求解IO型任务。在负载均衡度方面，本文算法DRDPSO和GA+PSO算法的负载均衡度对于三种类型的任务的表现相似，即处理CPU型任务的均衡性最弱，处理IO型任务的均衡性最好，而SAGA则适合于混合型任务的均衡调度。

多次实验结果表明，本文DRDPSO策略在大部分情况下在多个指标上比其他两种算法均有更好的表现。但由于算法的随机性本质，不能保证在每次运行时在各个方面(执行时间、资源成本、迭代次数)都优于对比算法。

表1 在任务规模500条件下,三种算法对三种类型任务的性能比较Tab. 1 Performance comparison of three algorithms for three types of task under task scale of 500

以上实验结果表明，本文DRDPSO策略有较为显著的效果：将惯性系数由常量修改为变量，使得过程前期搜索速度快而后期搜索精度高，实现对迭代过程的合理控制；以局部最优位置代替全局最优位置，减少了大量的无效搜索；引入遗传算法的选择操作，筛选出优质个体并传递到下一代；引入变异操作实现随机扰动，改善非优质粒子的组成，提高了全局最优解出现的概率；综合约束条件使得结束点更为合理。这些改进操作都促进了总的执行时间、资源成本、迭代次数的降低，资源-任务匹配度升高,以及资源负载均衡度减小。

3 结语

基于云计算的资源调度目标和要求，本文通过对现有调度策略的总体分析得出群体智能算法具有较好的处理能力。本文结合两种表现较为突出的群体智能算法PSO与遗传算法优势，并加入了多种改进方式，形成了混合式群体智能调度策略DRDPSO。在CloudSim 平台上进行了两类仿真测试，大量实验统计结果表明，与对比算法SAGA和GA+PSO相比， DRDPSO能够较为明显地缩短总的任务执行时间，提高了不同类型任务下的资源利用率，并适当兼顾计算节点的负载均衡，能够较好地解决云计算资源的动态调度问题。