基于改进QPSO算法的云计算资源调度策略研究

赵昱，惠晓滨，高杨军，郭庆

（空军工程大学装备管理与安全工程学院，西安710051）

基于改进QPSO算法的云计算资源调度策略研究

赵昱，惠晓滨，高杨军，郭庆

（空军工程大学装备管理与安全工程学院，西安710051）

资源调度问题是云计算研究的一个重要方向。针对传统量子粒子群算法的不足，提出了一种改进量子粒子算法，并将其应用于云计算资源调度策略。首先，建立了云计算资源调度问题的模型，并将资源调度任务完成的时间作为适应度函数。随后采用自适应机制，通过改变粒子位置更新的惯性权值，提高了算法的全局搜索能力，加快了收敛速度。最后通过实验仿真对该算法进行了测试。实验表明，该算法能更好更快地找到云计算资源调度方案，使资源分配更加合理高效。

云计算，资源调度，量子粒子群算法，惯性权值

0 引言

近年来，随着互联网网络规模的不断扩大，互联网所需要处理的业务量也随之快速增长。人们对计算服务质量要求越来越高，单一计算平台难以满足人们的要求，在此背景下云计算应运而生［1-2］。云计算集成了分布式计算和网格计算等多种技术，可以将分布于不同物理域的服务器通过逻辑维连接成一个巨大的资源池，通过虚拟技术等将实现用户任务的快速完成。资源管理是云计算的核心技术，其效率的高低直接影响云计算服务质量，因此，云计算资源调度一直是云计算研究领域中的重点和难点［3］。

针对云计算资源调度优化问题，国内外学者进行了大量深入的研究。云计算资源调度实际上是一种多约束、多目标优化问题，是一类NP难题。为此，学者们提出了许多算法。如文献［4］提出采用遗传算法求解云计算资源调度问题，相对于传统调度算法，其获得了较好的服务质量；文献［5］以任务完成时间、系统吞吐量作为目标构建云计算资源调度模型，然后采用蚁群算法进行求解，取得了不错的调度效果。在这些算法中，粒子群算法具有参数设置少，全局搜索能力强等优点，成为了云计算资源调度研究中的一个重要的方向，然而其易陷入局部最优和出现“早熟”的现象是其在计算诸多优化问题中难以克服的缺点。量子粒子群算法是将量子力学概念与粒子群算法相结合，通过解薛定谔方程和蒙特卡罗估计等方法，以波函数的形式描述粒子在空间内的运动状态，通过波函数塌缩来确定粒子的位置。实验证明，量子粒子群算法相对于标准粒子群算法具有更好的计算性能，在寻找最优解和避免陷入局部最优等方面更加适合求解优化问题。

1 云计算资源调度模型

云计算系统在保证满足用户高质量服务的同时，尽可能地减少服务时间，使用户可以在较短的时间内获得计算结果或数据。从服务提供者角度来看，云计算的系统资源是有限的，资源竞争是不可避免的，如何能够减少资源竞争，或者使各个计算节点达到负载均衡，是整个服务过程中需要考虑的问题。因此，只有通过资源调度将用户的需求任务分配到合适的计算资源上，才能满足以上两方面的要求。在资源调度的过程中，模型可由以下几个要素组成:

（1）任务集合S={s1，s2，…，sn}，表示n个相互独立且不可再分的任务组成的集合。

（2）虚拟资源集合V={v1，v2，…，vn}，表示云计算资源池中所包含的虚拟计算资源，其中每个计算资源vi采用如下形式描述:

式中，CPU表示内核数，MEMORY表示内存大小，DISK表示磁盘空间大小。

基于以上要素，计算资源调度的目标是通过对任务集中的各个任务进行合理的分配资源，并且对各个任务的执行进行排序，从而使得总任务的执行达到最优。为简化模型，本文对模型进行如下简化:

①虚拟机的性能满足任一任务的要求；

②每个任务只能由一个虚拟计算资源执行；

③不考虑任务传输时间对模型优化的影响。

由于云计算系统的计算并行性，多个任务可以同时在数据中心的各个节点上执行，对于一个调度方案D，完成n个任务的时间为执行时间最长的虚拟机，其数学表达式为:

其中，n为任务数量；m为云计算资源的数量。

2 量子粒子群算法（QPSO）

粒子群优化算法具有简单易行、易于理解等优点，从而受到了众多学者的关注。但在实际应用中也表现出了容易早熟、全局寻优能力差等特点。2004年，Sun等从量子力学的角度出发，提出了一种新的粒子进化模型，由于粒子是以概率波的形式出现在空间，使得算法可以在整个可行区域内搜索最佳解，所以它的全局搜索能力远胜于标准粒子群算法。

首先假定系统是一个量子粒子系统，假设粒子的运动空间为N维，m为种群数量，t为迭代次数。在搜索空间中，第i个粒子的位置是xi=（xi1，xi1，…xiN），其中i=1，2…m。将xi代入目标函数即可算出其适应值。记第i个粒子在第t次迭代中搜索到的局部最优位置为，整个粒子群搜索到的最优位置为其中g代表处于全局最好位置粒子的下标。

在量子空间中，利用波函数ψ（x，t）描述粒子的状态，通过求解薛定谔方程得到粒子的概率密度函数和概率分布函数，而粒子在空间中的具体位置则由蒙特卡罗反变换得到，有

最后，得到量子粒子群算法的进化方程为:

ξ为惯性权值，也是QPSO算法中唯一的一个收敛参数，其取值可以固定不变，也可引入自适应机制动态调节，一般按照下式取值:

式中，tmax为最大迭代次数，t表示当前迭代次数。

因此，标准的量子粒子群算法流程如下:

步骤1:初始化群体规模、最大迭代次数、解空间维数以及粒子位置；

步骤2:分配初始化粒子局部最优和全局最优值；

步骤3:优化过程，按照式（3）～式（5）更新QPSO算法中的所有粒子；

步骤4:计算群体当前的全局最优位置，即更新pi和pg；

步骤5:根据约束条件进行判断，当前所求的解是否满足，若满足输出最优解，否则跳到步骤2继续搜索直到满足条件或达到最大迭代次数为止。

3 基于改进QPSO算法的云计算资源调度策略

通过上节粒子更新计算公式可知，惯性权值ξ的选择关系到整个算法的收敛性和搜索能力，因此，如何选择ξ成为QPSO算法的关键。对于一个确定的粒子来说，进化速度的快慢，说明粒子越靠近或越远离粒子群的当前最佳位置，即粒子的搜索范围也随之缩小或增加了。所以为了提高算法性能，对于靠近粒子群当前最佳位置的点，ξ应该增大以使粒子尽量发散；对于远离当前最佳位置的点，ξ应该减小使粒子收敛。为此本文提出了一种自适应机制的ξ选取方法，即:

f（t）由下式确定:

考虑云计算调度策略的任务完成时间，本文定义所有任务完成时间为适应度函数，其数学表达式如下:

因此，基于改进QPSO算法的云计算资源调度策略流程为:

步骤1:初始化群体规模、最大迭代次数、解空间维数以及粒子位置；

步骤2:计算各个粒子的适应度函数值，并且确定初始位置各个粒子的局部最优值和全局最优值；

步骤3:优化过程，按照式（6）确定迭代惯性权值的大小，并通过式（3）～式（5）更新QPSO算法中的所有粒子；

步骤4:计算群体当前的全局最优位置和各个粒子局部最优位置的适应度函数值，与前一次迭代的适应度函数比较，根据比较结果更新pg和pi值；

步骤5:根据约束条件进行判断，当前所求的解是否满足，若满足输出最优解，否则跳到步骤2，继续搜索直到满足条件或达到最大迭代次数为止。

综上可知，改进QPSO算法的云计算资源调度流程图，如图1所示。

图1 本文算法的云计算资源调度模型求解流程

4 实验与仿真

为了测试改进后的QPSO算法在云计算资源调度中的应用效果，本文采用Cloudsim作为实验模拟平台，在一台处理器为Inter（R）Core（TM）i7-4710MQ，内存为8 G，操作系统为Windows 8的计算机上进行仿真实验。

实验中，选择标准粒子群算法（PSO）、量子粒子群算法（QPSO）和本文算法进行了对比。在相同实验条件下，3种算法的参数设置为:种群规模为10，PSO算法中c1和c2都为2，所有算法迭代次数为500次。

当云计算资源数量为8个时，将10个～100个不同的任务分配到资源节点进行计算，其中，虚拟机参数为:ram=512 MB；imagesSize=10 000 MB，不同虚拟机MIPS为250～2 000之间的随机整数。任务通过不同大小的待处理数据来设定。采用PSO、QPSO和本文算法对资源调度方案进行求解，各种方案的任务完成时间如图2所示。

图2 任务数量增加的任务完成时间

对图2任务完成时间进行分析，可以得到如下结论:当任务数量较少时，3种算法完成任务的时间差距很小；随着任务数量的增加，3种算法得到的最优调度方案完成时间差距逐步增大。当任务数量达到100时，QPSO算法与本文算法相差400 ms，而标准粒子群算法与本文相差700 ms。从以上趋势分析，对于固定计算资源数量的数据中心，本文算法较传统算法更具优势，同时任务数量越多，优势越明显。

当任务数量为100时，将这100个任务分配给10个～30个计算资源进行计算，虚拟机参数、任务参数和算法参数同上，采用PSO、QPSO和本文算法对资源调度方案进行求解，各种方案的任务完成时间如图3所示。

图3 资源数量增加的任务完成时间

从图3可知，当任务数量相同时，通过3种算法的资源调度来完成任务，随着计算资源的增加，QPSO算法与本文算法明显优于标准粒子群算法，而本文算法略优于QPSO，因此，本文算法更适合于云计算资源调度。

最后，统计了100个任务在分配给8个计算资源时的节点负载，3种算法分配任务的负载图如图4。图4表明，PSO算法在进行资源分配时节点负载最不均衡，其次是QPSO，本文算法相对与前两种算法性能更优；对比算法均不同程度地出现了处理能力强的资源分配到较少的任务，而处理能力弱的资源分配到了较多任务的现象。本文算法具有易于实现、不易陷入局部最优的特点，因此，获得了更为理想的调度方案。

图4 计算资源负载情况

5 结论

针对云计算环境下资源调度的NP难题，提出了一种改进的量子粒子群算法，通过在迭代中更新唯一的参数惯性权值，加强了QPSO算法的全局搜索能力。实验结果表明，改进的QPSO在性能上优于粒子群算法和标准量子粒子群算法，可以快速找到云计算资源调度方案，提高了资源利用率，为云计算资源调度策略提供了一个新的方法。

［1］RAJKUMAR B，CHEE S Y，SRIKUMAR V，et al.Cloud computing and emerging IT platforms:vision，hype，and reality for delivering computing as the 5th utility［J］.Future Generations Computer Systems，2009，25（6）:599-616.

［2］MICHAEL A，ARMANDO F，REAN G.Above the clouds:a berkeley view of cloud computing［R］.EECS，2009.

［3］袁浩，李昌兵.基于社会力群智能优化算法的云计算资源调度［J］.计算机科学，2015，42（4）:206-208，243.

［4］林伟伟，齐德昱.云计算资源调度研究综述［J］.计算机科学，2012，39（10）:1-6.

［5］肖明清，杨召，薛辉辉，等.云计算及其在测试领域的应用探索［J］.空军工程大学学报（自然科学版），2015，16（1）:50-55.

［6］刘静，须文波，孙俊，等.基于量子粒子群算法求解整数规划［J］.计算机应用研究，2007，24（3）:79-81，105.

［7］苑帅，沈西挺，邵娜娜，等.引入人工蜂群搜索算子的QPSO算法的改进实现［J］.计算机工程与应用，2016，52（15）:29-33.

［8］徐文忠，彭志平，左敬龙，等.基于遗传算法的云计算资源调度策略研究［J］.计算机测量与控制，2015，23（5）:1653-1656.

［9］周文俊，曹健.基于预测及蚁群算法的云计算资源调度策略［J］.计算机仿真，2012，29（9）:239-242，246.

［10］刘卫宁，靳洪兵，刘波，等.基于改进量子遗传算法的云计算资源调度［J］.计算机应用，2013，33（8）:2151-2153.

［11］杨单，李超锋，杨健，等.基于改进混沌萤火虫算法的云计算资源调度［J］.计算机工程，2015，41（2）:17-20.

［12］黄宇，韩璞，刘长良，等.改进量子粒子群算法及其在系统辨识中的应用［J］.中国电机工程学报，2011，31（20）:114-120.

Research on Cloud Computing Resource Scheduling Strategy Based on Improved QPSO Algorithm

ZHAO Yu，HUI Xiao-bin，GAO Yang-jun，GUO Qing
（Material Management and Safety Engineering College，Air Force Engineering University，Xi’an 710051，China）

Resource scheduling problem is an important direction of cloud computing research. Aiming at the shortcomings of the traditional quantum particle swarm optimization algorithm，this paper proposes a quantum particle swarm algorithm based on improved.Cloud computing resource scheduling model is established firstly，and then the fitness function of the model is defined.Soon afterwards，by using the adaptive mechanism，the inertia of particle position update weights to improve the global search ability of the algorithm is changed，and the convergence speed is accelerated.Finally the simulation of the algorithm is tested by experiments.And the experimental results show that this method can better and faster to find cloud computing resource scheduling scheme，make resource allocation more reasonable and efficient.

cloud computing，resource scheduling，quantum particle swarm optimization，inertia weight

TP393

A

1002-0640（2017）04-0014-04

2016-02-05

2016-03-28

国家自然科学青年基金资助（71501184）

赵昱（1993-），男，山西运城人，硕士研究生。研究方向：信息系统工程与智能决策。