基于QPSFLA算法的云计算环境资源调度策略

贺智明　张扬　高林

摘要：针对云计算环境下的资源调度优化问题，提出了一种基于量子粒子群策略的混洗蛙跳改进算法（简称QPSFLA算法），旨在引入量子粒子群搜索策略防止传统混洗蛙跳算法容易陷入局部最优的问题。在CloudSim平台上的模拟试验结果表明，QPSFLA算法能够达到预期效果，而且比平台自带算法和传统混洗蛙跳算法效率更高。

关键词：云计算；量子粒子群；混洗蛙跳；资源调度

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）02-0311-04

云计算是在分布式计算（Distributed Computing）、并行计算（Parallel Computing）和网格计算（Grid Computing）的基础之上，通过整合虚拟化和效用计算等理论后形成的一种新的计算模式[1]。通过网络，云计算将复杂的大规模处理任务拆分为若干个小任务，然后分配给网络中多个任务中心进行处理，完成后再将各任务中心的处理结果反馈给用户。提供这些服务的网络和任务中心即是所谓的云。云计算提供了一种新的模式，这种模式把本地的服务转移到网络上以减少软硬件的管理成本[2-3]。云计算资源调度通过一定的策略将用户请求合理的分配到各个计算资源上，使用户请求得到满意的计算服务。

1 云计算资源调度及调度模型

云资源调度包括用户请求、计算资源及分配策略几个部分。假设任务数为M，资源数为N，用T表示用户请求，T={T1 ，T2，…，Tm}，计算资源P={P1，P2，…，Pn}。云计算资源调度模型可描述为将M个用户请求按照一定的策略调度分配给N个计算资源执行，以获取最优的资源分配。如图1所示。

由图1可知，云资源调度包含两层。第一层调度从用户层到虚拟机层，第二层从虚拟机层到服务层。在这二次调度模型中，第一层创建一个虚拟机，其中包括计算资源、网络资源和存储资源，并且根据一定的规则描述虚拟机的每个任务。通过两层结构，任务可以获取所需的资源，但高等级请求可能会占用服务器多余的资源，从而增加低等级任务的等待时间而造成资源浪费。

2 QPSO算法

3 SFLA算法

混洗蛙跳算法是一种启发式的群体进化算法，该算法最先由Eusuff和Lansey于2003年提出。SFLA算法是一种新型的仿生物学智能优化算法，SFLA 集成了模因演算法（MA，memeticalgorithm）和粒子群算法（PSO，particle swarm optimization）的优点。SFLA算法概念简单、参数少、计算效率高，全局搜索能力强，易于实现。混合蛙跳算法主要应用于解决多目标优化问题。

3.1 算法原理

混合蛙跳算法（Shuffled Frog Leaping Algorithm， SFLA）模拟了不同青蛙族群在寻找食物时进行信息交流的过程[5]。混合蛙跳算法先将青蛙个体按照一定的方法分成若干个子群，将全局搜索策略与局部搜索策略相结合，每只青蛙在子群中交换思想，而算法中的混合策略使各子群间的思想得到交换。其中，子群是由相同特征的青蛙组成，不同的子群是由具有不同的思想的青蛙组成。子群中青蛙按照一定的方法进行局部寻优。在局部寻优达到给定条件后再执行混合策略，直到达到最优解。全局混合策略与局部寻优策略可以使蛙跳算法跳出局部最优解，这是混合跳算法的主要优点。

3.2 算法基本流程

1）初始化各参数，随机产生青蛙种群粒子（即SFLA种群粒子）；

2）用适应度函数对粒子个体进行降序排列选择；

3）将降序排列的粒子分配到每个族群中；

4）利用预设的迭代次数进行局部寻优；

5）将各青蛙族群进行混洗。在每个族群都进行过一轮进化后，将各个族群中的蛙重新进行排序和族群划分并记录全局最优解；

6）判断迭代是否结束，如果满足收敛条件，算法迭代停止并且输出粒子，否则转到第二步继续执行。

4 改进SFLA算法

本文提出改进的SFLA算法在局部搜索时使用QPSO搜索策略的QPSO - SFLA算法（QPSFLA），算法局部搜索使用QPSO搜索策略，得到局部最优解后使用SFLA算法可以得到精确结果。算法流程如下：

1） 参数：群体大小，群体大小，迭代的最大数量的局部搜索，迭代和等的整体数量。

2） 生成初始种群粒子。

3） 确定适应度函数F（x）用来评估青蛙粒子的优点。

4） 青蛙在按降序排列，并确定Qbest（全局最优解） ，如果满足收敛条件，则停止执行；否则，下一个步骤。

5）青蛙种群划分：将青蛙粒子分配到M个种群中，第一只进入第一个种群，第二只进入第二个种群，以此类推，第m个进入第m种群，m+1进入第一种群，m+2进入第二个，直至所有的青蛙粒子划分完毕。

5 仿真实验

本文使用澳大利亚墨尔本大学推出的cloudsim3.3平台[6-7]进行云计算资源调度仿真实验，通过扩展DataCenterBroker类来模拟改进的资源调度算法。

实验分别选择CloudSim自带的轮循算法、混洗蛙跳算法及量子粒子群混洗蛙跳算法模拟资源调度。实验所需的数据如表1所示。模拟的任务数量分别为5、60、140、290，任务长度为10000至20000，仿真实验次数为300次，取平均值作为实验结果。

6 结束语

本文针对云计算资源调度的特点，分析了混洗蛙跳算法在云计算资源调度中应用的不足，提出一种改进的混洗蛙跳算法，对局部搜索进行改进。并将此算法应用在资源调度策略上，实验证明该算法不但避免了原有算法易陷入局部最优，而且提高了资源调度的整体性能。

参考文献：

[1] AnIlbmst M，Fox A，Gmth R，et a1.A view of cloud computing[J].Communications of the ACM，2009，53（4）：50-58.

[2] Brian Hayes.Cloud computing[J].Communications of the ACM，2008（7）：9-11.

[3] 李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，30（1）：184-186.

[4] 李爱国.多粒子群协同优化算法[J].复旦学报：自然科学版，2004，43（5）：923-925.

[5] Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Joumal of Water Sources Planning and Management，2003，129（3）：210-225.

[6] The Could Lab.Cloudsim[EB/OL].[2011-08-15].http：//www.cloudbus.org/cloudsim.

[7] Buyya R，Ranjan R，Calheiros R N.Modeling and simulation of scalable cloud computing environments and the CloudSim Toolkit：chanllenges and opportunities[C]//proceedings of the 7th High Performance Computing and Simulation Conference.New York，USA：IEEE Press，2009：21-24.