李 萌 ，刘 鑫

(1.陕西科技大学镐京学院，陕西 西安 712046;2.中南大学商学院，湖南 长沙 410083)

1 引言

为了实现大规模数据的存储管理，云计算作为新型计算框架被广泛应用于各类互联网业务场景中。它能够根据使用者的意图及时可靠的提供按需分配的服务与资源[1]。随着使用者与业务的增加，云计算框架需要管理大量的软硬件资源。目前主要通过虚拟化技术，结合调度策略调整任务与资源的对应分配[2]。但是由于系统的动态特性显著，影响调度性能的因素具有非线性，设计一种高效可靠的资源调度路径优化算法成为该领域的难点[3]。如今很多学者致力于云计算资源调度的研究，也提出了一些较好的调度算法。

文献[4]设计了AC-SFL调度算法，采用回馈系数改善蚁群的收敛性能，同时优化蛙跳改善最优解搜索性能。该算法具有较好的网络吞吐量和成本利用率，但是过于关注算法的收敛和寻优效果，没有过多考虑资源调度模型本身的优化。文献[5]设计了BA-LBRSA调度算法，在负载模型的基础上采用蚁群进行任务分配。该算法具有较好的负载利用率，但是模型构造过程中没有充分考虑效率问题。文献[6]设计了一种ACO优化算法，调度效率较好，但是在负载率和大规模任务处理方面还存在欠缺。文献[7]设计了ACO-GA调度算法，通过混合算法增强最优策略的搜索。文献[8]设计了IACO调度算法，分析了基于最大完成时间的调度模型，并考虑了收敛过程中的负载均衡性。这些算法在某些性能方面取得了不错的效果，但是整体的动态适应性有待提高。

本文首先构造资源调度模型，并分析影响调度模型的目标约束，具体包括任务时间、成本和负载率，从而确保调度模型求解的综合性能。然后将改进PSO算法引入调度模型计算，并针对PSO的初始化和参数更新等操作进行优化设计。最后通过CloudSim平台对调度算法的任务延时、任务成本，以及资源负载率进行仿真实验，验证了本文所提算法的有效性。

2 资源调度模型

云计算需要处理大量动态任务，且很多任务必须满足时效性。为符合应用需求，调度管理中心应该提高资源调度的规模和使用率，这需要依赖资源调度模型来实现。假定系统中部署的虚拟机数量是n，则对应集合可以描述为V={v1，v2，…，vn}。系统中到达的任务经过划分后形成的子任务数量是m，对应集合可以描述为R={r1，r2，…，rm}。处理任务时调度中心会把所有的子任务分配到当前可用的虚拟机。由于虚拟机在任意时刻仅可以处理一个任务，所以可以将虚拟机与任务存在的关系描述成如下矩阵

(1)

元素gij描述的是任务ri和虚拟机vj的映射。任务映射分配的有效性决定了资源调度的合理性，因此在映射过程中，应该最大限度保证任务处理的时间、成本，以及网络均衡性。

3 目标约束分析

3.1 任务时间约束

假定任务ri分配给虚拟机vj处理，则ri的完成时间可以描述如下

(2)

(3)

(4)

其中，k表示分配给vj的任务数量。根据Wj、Cj、Mj、Fj参量得到虚拟机的任务处理性能，将最高和最低的分别标记为max(vj)和min(vj)。将任务最优和最差的处理时间描述如下

(5)

(6)

于是，可以将时间约束定义如下

Tc=(ttotal-Tmin)/(Tmax-Tmin)

(7)

系统任务完成的越快，Tc结果越小，意味资源调度对时间越有利。

3.2 任务成本约束

虽然有效的资源调度会降低任务时间，但是，单独的时间最优不代表资源调度整体性能的合理，于是，这里进一步考虑任务成本问题。设定vj执行任务时单位时间所需成本是costj。则系统任务全部处理完的累计成本可以描述如下

(8)

虚拟机处理任务的最优与最差成本分别记为min(costj)、max(costj)，结合Tmin与Tmax可得全部任务处理完成所需的最优和最差成本消耗如下

Cmin=Tmin×min(costj)

(9)

Cmax=Tmax×max(costj)

(10)

于是，可以将任务成本约束定义如下

CC=(Ctotak-Cmin)/(Cmax-Cmin)

(11)

3.3 负载及综合约束

资源与任务的调度管理都是动态的，任意资源上的负载情况都在不断变化，从而形成不同资源上的负载均衡问题。在分析任务时间时，考虑了虚拟机的Wj、Cj、Mj、Fj四个参数，如果通过计算发现某些虚拟机的参数较好，便会有大量的任务被分配过来，导致网络资源产生空洞或者热点。因此，即便是虚拟机性能参与了时间约束计算，仍然不能有效保证负载的均衡分配。于是根据参数Wj、Cj、Mj、Fj，将负载公式描述如下

Lj=a1Wj+a2Cj+a3Mj+a4Fj

(12)

a1～a4代表对应参数的权重，且a1+a2+a3+a4=1。

将任务时间与任务成本采取加权合并，结合资源负载情况得到综合目标如下

(13)

λ1与λ2代表权重系数，且λ1+λ2=1；Lc代表负载约束，其值越小，意味着该虚拟机性能越差，被选择的可能性越小。

4 改进PSO算法

经过云资源调度模型和目标约束分析，采用一种改进PSO算法来解决此资源调度NP问题。根据PSO算法需要先确定粒子及相应参数，这里选择将每个子任务看做一个粒子。由于子任务是非连续的[9]，所以对粒子采取自然数编码为Q={q1，q2，…，qm}。对于任意粒子，可能对应的虚拟机有n种选择，于是其维度为n。其中qij即代表任务映射到资源上。将粒子i的位置参数描述为向量Qi=(qi1，qi2，…，qiu)T，速度参数描述为Si=(si1，si2，…，siu)T。假定粒子所在空间表示为R=(xmax-xmin，ymax-ymin，zmax-zmin)，粒子起始位置为Ps(xstart，ystart，zstart)，最终位置为Pt(xtarg et，ytarg et，ztarg et)，则粒子的位置参数初始化为

(14)

(15)

在根据位置和速度的更新迭代搜索得到最优粒子时，粒子位置参数更新过程表示如下

qi(k+1)=qi(k)+(1-ηi(k))si(k+1)

(16)

qi(k+1)为第k+1次迭代后得到的最新位置；ηi(k)为调整因子，其计算方式表示为

(17)

粒子的速度更新公式表示如下

si(k+1)=ε(k)si(k)+a1b1(q′i(k)-qi(k))+

a2b2(q′(k)-qi(k))

(18)

式中a1和a2均表示(0，1)范围内随机数，用于提高粒子群多样性；b1和b2是加速系数，用于控制粒子的训练性。ε(k)表示惯性系数，它会直接影响寻优效果，应该在迭代过程中实时进行调整，使其保持最优。在参数更新过程中，PSO存在前期搜索过快，容易出现可行解被略过的现象。为避免该缺陷对算法收敛的影响，在迭代前期，应该使用较大的ε(k)值，控制PSO收敛速度。随着迭代次数的增加，逐渐逼近最优解，降低ε(k)值以提高收敛速度。这样做的同时，也可以有效防止PSO早熟。基于以上思想，ε(k)的调整公式描述为

(19)

因为粒子具有趋向性，使得PSO在多样性方面存在缺陷。为此，在每一轮的迭代更新时，粒子都在当前位置上通过随机方式移动一步，比较移动前后的适应性。若移动后的适应性变好，则以移动后的位置作为最新位置，继续更新；若移动后的适应性变差，则退回移动前的位置，继续更新。更新过程中的适应性计算公式如下

(20)

式中μ和ω表示(0，1)范围内的衡量系数；适应性与负载约束成正比，与时间成本约束成反比。

5 仿真与结果分析

基于CloudSim仿真环境，将本文提出的资源调度算法添加至Datacenter Broker类中。同时将改进蚁群实现的资源调度算法(LACO)[8]也添加至Datacenter Broker类中，与改进PSO调度算法进行对比。算法中给定参数costj∈[1，10]，b1=b2=1，εmax=0.9，εmin=0.3，移动步长为0.05R。仿真实验参数给定如表1所示。

表1 实验参数给定

图1 任务延时曲线

在任务规模为100、300和500三种情况下，得到两种算法的任务延时，结果如图1所示。从任务延时曲线比较可知，改进PSO调度算法在迭代初期为避免最优解被忽略，对粒子速度采取抑制，虽然初期收敛速度没有改进蚁群算法快，但是到了中后期，由于更新方式和惯性系数等优化，收敛性能显著优于LACO算法。任务规模为100时，完成最优解搜索时比LACO迭代少了25次，任务延时少了10ms；任务规模为300时，完成最优解搜索时比LACO迭代了45次，任务延时少了23ms；任务规模为500时，完成最优解搜索时比LACO迭代了82次，任务延时少了53ms。另外可以看出，任务数量的增加对本文算法的影响较LACO算法小，表明本文算法的寻优和收敛效果更好，对于大规模任务具有更好的处理能力。

任务规模从100增加至500时，仿真得到两种算法的任务成本消耗，结果如图2所示。比较发现，任务规模为100时，两种算法的成本消耗相差无几。但是随着任务规模的增加，成本消耗相差越来越大。当任务规模为500时，本文算法的成本消耗较LACO算法节省了13.81%。本文算法在资源调度过程中考虑了成本约束，任务规模越大，成本节约越显著。

图2 任务成本消耗比较

仿真得到两种算法的负载情况，结果如图3所示。根据对比发现，在任务规模为100时，两种算法的负载率差别不大，随着任务规模增加，两种算法都表现出较好的负载率，整个过程负载率均保持在50%以下，但是本文算法的负载率较LACO算法更好。这是由于本文算法考虑了负载约束，同时在时间约束过程中也考虑了负载因素影响。

图3 负载率结果比较

6 结束语

为了有效实现云计算资源调度路径优化，本文提出了基于改进PSO调度算法。首先分析了资源与任务的映射模型，然后对映射过程中的各类条件约束进行具体分析。最后引入PSO算法，并对PSO粒子初始化、更新，以及适应性做了相应优化。通过仿真实验结果，证明本文算法能够明显降低云计算任务完成时间，有效节约任务成本，并且具有良好的资源负载率。