云计算中的基于改进的粒子群算法资源调度的研究

陈南岳

摘要：该文主要针对由于云计算动态功能而造成的不均衡资源集群情况，提出一些改善策略，主要是利用虚拟机技术，实现云计算资源的动态迁移。在迁移的过程中主要是利用引入窗口的相关指数来分析负载的热点。在选择虚拟机的时候，要充分考虑迁移效果和速度，利用退火逻辑中的粒子群算法，得到最好的虚拟机放置。然后利用轮盘思想完成平台资源的高效优化。之后就是利用云仿真技术CloudSim把云计算系统中的等级协议（SLA）有关的违背率、集群耗能、虚拟机的迁移次数、剩余资源等问题进行试验，之后将各种算法和本文的算法进行比较。得出的结果很显然说明了本文的算法比较有优势。

关键词：云计算；粒子群算法；动态迁移；虚拟机

在IT领域中云计算是非常受欢迎的，对于当今时代各个行业对大型数据处理的需求越来越多，云计算作为一种新型计算机技术，它将网格式计算、并行式计算、分布式计算等实现了进一步的发展，充分的适应了现代社会的需求。它包括的服务层次主要有三种：首先是基础设施层，其次是平台层，最后就是应用层，这三层的功能都可以通过服务的形式表现出来。云计算的调度任务是指在云配置的环境中，利用相关的资源策略，根据用户对资源的不同需求进行分析，从而是实现资源的合理配置，总之这些任务调配基本上都是在基础设施层（IaaS）进行。目前使用的资源调度策略基本上都是在虚拟机上进行，如何在云计算环境中是实现更加高效的任务调度，为用户提供更加精确的数据，是当下主要考虑的问题。

粒子群算法（PS0）是在模拟鸟群进行觅食行为试验中逐渐发展起来的，它是一种群体协作方式的智能算法，它的优势在于简单实用、容易理解，由于这些特点该算法被广泛应用。这种算法主要是由Eberhart等提出，之后又将群体智能算法进行完善。粒子算法的计算过程比较简单，参数设置比较少，同时收敛速度也是非常快，所以该算法的应用价值比较高。但是，标准的PSO算法在实际进化中，逐渐降低了种群多样性，从而也造成该算法出现收敛早熟的情况。之后Zhang等对粒子群算法的速度重新进行初始化，从而保持了该算法的种群多样性。Riget等人利用种群多样性继续进行测量，在试验中将粒子群进行交替的排斥和吸引操作。

1资源调度中初始化虚拟机的放置

首先就是建立云计算平台并实现运行，把系统运行中原有的平台移动到现在的云计算系统中。在实现这个环节之前，还有对该平台进行虚拟化，还有对每个虚拟平台进行初始化，然后建立云平台。想要顺利的实现移动原有的业务，这里可以使用动态迁移的技术进行完成，把虚拟机进行初始化之后按照物理点进行分配，这样是为了在平台的运行中减少虚拟机的迁移次数。

1.1资源调度中使用退火思想

把虚拟机反映到物理节点上，能够实现负载的均衡和减少能耗的优化目标，这里主要使用的是启发式的搜索算法。因为传统的粒子群算法在搜索过程中容易出现局部优解的情况，所以，专业人士根据启发式算法的优劣进行分析，最后得出将退火思想和粒子群算法相结合实现对多种表目标进行计算。利用退火思想将搜索过程中的可能出现局部最优解的跳出概率进行分析，从而找出整体的最优解，这样可以防止传统粒子出现局部最优的情况造成搜索的失败，最后就可以实现全局搜索功能的提高，同時也能提高最有解计算的准确度和效率。

1.2粒子群相关算法的建模

首先对虚拟机相关的编号n进行队列排序，然后根据相关的搜索算法把物理节点m与其的映射关系计算出来，之后根据物理节点合理放置虚拟机，从而实现优化的目的。在群体粒子中每个粒子的速度和位置可以表示为：

在公式（1）中x表示在第k轮迭代中，参数是i的粒子在数值j个虚拟机的物理节点所放置的编号。在公式（2）中u：表示在k轮迭代中，参数为i的粒子出现在第j维相关的速度；D则是一个常量，它主要是对粒子飞行的范围进行控制，避免出现偏移过渡的情况给算法的收敛造成影响。根据经验总结将设置为10%-20%的问题空间。

在每轮迭代中每个粒子的位置和速度通过公式（3）（4）进行更新。

在该公式中，i是群体中的每个粒子编号；d则是每个粒子的相关维数，它是根据虚拟机的个数来确定取值范围；P则是迭代在个体i中最佳的位置向量；P是在整个群体中最佳的位置向量。

其中r1、r2表示0～1的随机均匀分布数；c1、c2则是学习因子，他们会在0-4之间取相等的数值；W则是惯性的权重。

1.3惯性权重的设计和分析

对粒子群算法相关的结果和收敛速度造成影响的主要因素是粒子群的惯性权重，如果惯性权重的值比较大，那么粒子群相关算法就具有了较高性全局搜索能力，在所有的解中此时所计算出的值则是具有适应度函数的最小解；如果惯性权重比较小的话，那么此时的粒子群算法则是局部搜索功能最好的，此时算法就能够在一定的小范围内实现局部搜索。所以，在对粒子群迭代过程进行计算的时候，前提就是先做好粒子权重有关最大值的设置，这样可以更加方便在全局范围内进行最优值的搜索，之后在利用最小的惯性权重，在这个小范围内进行最优值的搜索，如此才能在搜索算法中获得较快的收敛性与更好的搜索结果。

通过将惯性权重的值从最大变成最小，来提高粒子群搜索的效率。其中关于惯性权值的设置可以根据公式（5）进行：

在该公式中m表示W值只在范围内变化；t表示当前的迭代相关次数；k值主要是对惯性权重进行影响以此来减少速度；num则是总迭代的次数。在迭代次数呈现增加的状况时，这时候的惯性权重则是减少的，而且速度的减少也在变缓，这样可以方便从全局搜索转变成局部搜索，同时也能够限制算法收敛的速度。

1.4引入模拟退火思想

根据公式（3）（4）可以看出，在进行粒子群算法时，是将每个粒子飞行的速度人为控制在一定的范围内，避免粒子出现较大的偏差，从而影响搜索的结果和收敛的速度。如果没有对每个粒子运动位置进行限制，那么当粒子移动到一个对于局部来说是较优值时，之后继续的迭代都会在这个值上进行，这样将会对搜索算法的性能造成影响。

这里可以使用退火思想和粒子群算法相结合的方式，对计算过程出现的局部最优解的问题。Metropolis相关准则表明，当粒子的温度在T时，这时它趋于平衡的概率则是exp（AE/kT），其中E表示在温度T时有关的内能，AE是它变化的量，k则属于Bohzmann常数。首先把这个概率值代人到粒子群算法中，利用目标函数把内能E模拟出来，用控制参数t来模拟温度T。另外，在进行退火算法模拟的时候，先对i进行初始解并对参数t进行控制，之后根据当前的解通过迭代得出新的解，将其代人到目标函数中，之后计算出函数相关的变化量，然后分析这个结果是否拒绝或是接受，在每个次迭代过程结束的时候，根据相关的比例逐渐减少t的相关值，计算需要的退火公式如下：

该式中a是模拟退火中被冷却而衰减的因子，它的取值一般是小于1.00的正常数。

在获得每个粒子的新位置后，把适应度的值也计算出来，假如适应度的值比当前的位置好，那么此时的粒子就要移动到新的位置，如果是相反的，那么粒子要根据exp（AE/kT）概率进行移动。通过利用退火思想进行的模拟计算得出，每个粒子在粒子群中都会经过退火计算，而且每个粒子会按照相应的概率值来改变自己的位置，其中每粒子都是根据粒子群相关的优化公式进行移动的而不是随机的，这样在迭代的过程中才能更好对其进行控制，避免出现局部最优解。通过在粒子群算法中使用退火思想，然后对每个经过的粒子进行退火分析，这样可以对每个粒子更新的位置进行控制。

1.5目标物理节点使用轮盘赌思想进行选择

一旦云计算平台完成建设，那么在长期的运行中，总会因为用户的不同需求进行虚拟机的移动，造成平台中的虚拟机出现不定时的迁移。在给虚拟机进行物理机的选择时，对于长期运行云平台来说，利用退火模拟进行粒子群算法计算得出的只会是一个局部最优解，这时如果搜索任务增多或是虚拟机出现迁移，那么下一刻的集群情况可能就是次优状态，如果频繁进行虚拟迁移的话，则会出现资源被占用的情况。所以利用粒子群进行虚拟机相关的位置放置时，首先要选择好对应的物理机，利用轮盘赌算法进行计算，这样集群才能长期处于优化状态。

在进行轮盘赌思想的计算时，是在多组解中考虑到可能解的个数，之后随机选择一组解进行计算。在多组可能解中使用轮盘赌的思想，可以在相对的概率范围内实现当前最有解，或是得出当前的次优状态。

在粒子群算法中使用轮盘赌思想是要将迭代过程中得到的N组解保存起来，以此得到虚拟机准确的放置最优解。然后把这些解分成N组，然后组间一个Nxn的矩阵，这样就可以获得虚拟机迁移需要的物理节点了。之后使用概率相关算法，在根据每个解在相关解集中所占的比例，计算出每个解相关的标号，然后将虚拟机牵动需要的可能解和相关的标准差计算出来。如果出现的期望值和可能解的绝对值之间的差值比标准的差大，那么这个解则是不可能解，就不予考虑了。最后使用概率算法在最优解和次优解之间进行物理节点的选择，这样就可以对粒子群算法中获得的结果进行优化，从而实现长期优化的目的。

1.6适应度的函数

在进行云平台资源的调度时，要充分考虑节点、能耗、负载和服務等级协议（SLA）等问题，实现平台的高性能和高资源利用率，从而减少能耗。

4）服务等级协议主要受物理节点有关CPU的使用率的影响。其中在SLA评价函数中有关CPU的使用率，用公式表示为：

在该公式中Ucev是物理节点中有关CPU的使用率，P是保证SLA相关的阈值范围。在公式（7）中选择最小的CPU使用节点。

5）在对使用率资源进行评价的时候，可以利用剩余资源的利用率相关算法进行。把CPU、内存、剩余资源、网络、硬盘等分别与总资源比值计算出来，之后就可以得到标准的剩余资源了。在最小的标准化资源和各维之间的剩余资源中去差值，然后将计算出的最小值作为最优解。计算剩余资源有关使用率的公式如下：

在该公式中Ri表示在第i维处的标准化剩余资源，R表示标准化剩余资源中的最小只，根据公式（6）计算出利用率约均衡f值越是小，在各维中使用该节点的几率就越不均衡，如果值是不断增大的，那么在各维中该节点的使用率就会越低，则该节点可以作为防止节点。

3）节点的能耗包括两部分内容，一是运行的能耗，而是基础能耗。因为电源能耗和利用的CPU率之间是存在一定的线性关系，所以，这里可以使用通过CPU的相关使用率计算节点处的能耗。计算节点能耗的相关公式如下：

该公式中P表示满载电能的相关消耗，P是空载电能的有关消耗，根据公式得出最低耗能的相关节点作为搜索解。

6）根据不同的目标优化要求进行权值的设置，从而实现多目标的优化。综合的适应度函数表示为：

2虚拟机的迁移过程

2.1利用负载预测获得物理热点

首先是通过窗口的思想，按照时间相关顺序利用预测指数的算法来确定相应的热点。根据历史数值对某一时刻的CPU使用率进行计算：

该公式中a表示平滑指数相关的预测数值（其范围是整数且a≤1），它是对下一个时间段CPU的使用率受窗口影响的预测；a1。是正太随机分布变量，主要是确保预测的值有一定的随机性。

2.2选择迁移虚拟机

将CPU使用率和虚拟机相关的内存大小策略相结合，同时提高迁移质量，相关函数是：

该式中R是虚拟机的相关内存。如果CPU的使用率高而且内存是小的时候，Q的值就是最大，虚拟机的迁移可以很快的消除热点，如果CPU有关场景数据和内存数据非常少，这时可以减少迁移的时间。

3结论

本文主要是对云平台有关资源调度的SLA和能耗，以及资源利用与迁移次数等问题进行分析，通过退火思想对虚拟机进行了初始化放置，分析了虚拟机迁移相关的动态变化过程，使能耗和资源利用，以及迁移次数等问题实现了均衡的目的。