包簇映射框架下的云资源分配优化算法研究

徐 阳 陈世平,2

1(上海理工大学光电信息与计算机工程学院 上海 200093)2(上海理工大学信息化办公室 上海 200093)

0 引 言

近年来，随着云计算[1-4]取得了巨大成功，大量高科技公司涌入云服务市场。随着云计算市场规模越来越大，用户群体变得更加复杂，相对应的业务需求也在不断变化。云数据中心资源调度的一个关键目标，是将云数据中心的资源快速充分利用分配给用户。目前主要用的启发式算法有：粒子群算法(PSO)[5]、蚁群算法(ACO)[6]、遗传算法(GA)[7-8]等。这些算法主要目的是减少成本，提高资源利用率，以至于满足用户各方面的要求。但是这些算法都有各自的优缺点，如蚁群算法局部搜索能力较强，但是初始信息素匮乏、初始搜索速度慢等。

当前云资源分配调度方案依然是云计算最关键的技术。为了提高云资源分配效率，减少资源分配的时间，满足用户的使用需求。本文引入包簇理论[9]，在包簇映射框架下，提出基于混沌扰动遗传算法GACD(Genetic Algorithm based on Chaotic Disturbance)。该算法是在遗传算法的基础上引入混沌搜索机制、改进种群个体选择、交叉和变异等操作，提高算法的搜索速度和收敛效率。最后采用CloudSim进行实验，以检测算法的正确性。仿真结果表明，基于混沌扰动遗传算法解决了传统遗传算法存在的局部收敛、收敛速度慢和资源分配效率低等缺点，在一定程度上加快了云计算资源分配效率，缩短了任务的完成时间。

1 包簇框架的描述

由文献[9]可知，包和簇是树形结构。最底层的虚拟机组合成一个包，而多个包又组合成一个更高级的包。虚拟机或包所需的资源就是用户对云资源的需求。其中用户对资源需求包括CPU、RAM、宽带和缓存等。同理，簇是由多个服务器或子簇组成。簇拥有包对资源的需求量。

本文定义有N个子簇(或服务器)。p为子簇标号，1≤p≤N。有M个子包(或虚拟机)组成，标号为v，1≤v≤M。本文的关键是将M个子包分配给N个子簇，将同一个包中包分配给同一个簇中簇，同一个算法递归调用把子包分配给子簇，直到虚拟机分配给服务器。

由文献[10]可知资源约束：

(1)

式中：xv,p[t]是二进制0-1变量：当且仅当在时间t时包v被分配给簇p，则xv,p[t]=1；否则，xv,p[t]=0。Rv,i[t]表示包v在时间t对资源i的需求总量。1≤i≤J，1≤t≤T。Ap,i[t]表示簇p在时间t时对资源i的可用总量。1≤p≤N。

由文献[10]可知簇的运营成本：

本文在基于包簇映射的框架下，以减少成本U(x,y)为目标，通过混沌扰动遗传算法进行资源分配，提高分配效率，减少分配时间。

2 基于混沌扰动遗传算法调度策略

2.1 设计思想

基于混沌扰动遗传算法是将遗传算法和混沌搜索机制相结合。首先求出个体之间的差异和适应度值，利用遗传算法进行搜索，混沌机制来避免陷入局部最优，通过精英保留选择法，把优秀的个体作为父代，然后采用改进的交叉和变异操作。算法的主要流程如图1所示。

图1 算法流程图

2.2 个体之间的差异性

种群在初始化时会有很大的机率产生很多相似的个体，导致大量迭代计算，为了解决此问题，本文引出差异性。

差异性是指特征空间中对象之间的差异，将特征空间中不同的对象进行分类。本文用0-1编码来对两个个体的基因串进行评估，其中两个对象相同的位置编码相同，则为0，不同则为1。0越多表示两个对象越相同，编码情况越相同。在算法中，限定0的个数来避免非常相似的个体。

2.3 自适应交叉方式

设种群虚拟机的规模为M，虚拟机的任务资源需求种类为J，种群虚拟机的编码长度为L。第i位编码为0的个体数为Si,0，为1的个体数为Si,1，则定义第i位的相似度[12]为：

(2)

则群体的相似度定义为：

(3)

根据θ的大小来判断种群虚拟机的收敛程度，θ越大，表示种群虚拟机越相似，虚拟机所需要的资源也就越相同。种群虚拟机的交叉概率也是依据θ的大小动态调整。算法初期，设定较大的交叉概率值，以此加快种群繁衍和收敛。当种群虚拟机的θ比较大时，相应地调小交叉概率。参照文献[11]给出相应的自适应调整公式：

Pc=t1et2θ

(4)

式中：t1和t2的值由Pc和θ的取值范围共同决定。

2.4 种群初始化和混沌扰动的确定

混沌相关的的内容可以参考文献[12-13],混沌的主要思想是利用自身的特点进行搜索，防止陷入局部最优[14-15]，本文采取Logistic映射系统，映射关系如下:

δn+1=uδn(1-δn)n=0,1,2，…

(5)

式中：u∈[0,4]，当u=4时为完全混沌状态。

首先，随机产生一个L维向量δ1=[δ1,1,δ1,2,δ1,l,…,δ1,L]，δ1,l∈[0,1]，δ1作为初始向量进行迭代。根据式(5)将得到的各混沌变量映射到优化变量的各维取值空间，然后计算目标函数值，对其值进行排序，从中选取M个较好的个体作为初始种群。

为了增加解的多样性，本文用混沌序列对虚拟机种群进行混沌扰动，提高搜索精度，混沌扰动方程如下：

(6)

α的取值会根据搜索的范围进行调整，在种群初期时，搜索较大范围，α选取较大的值。到后期时，解已经逐步优化，搜索的范围变小，此时需要选取较小的α，以便在较小范围内变动。本文按下式确定α的值：

(7)

式中：m为参加扰动解的个数；k为扰动次数，k=1,2,…。

2.5 加速收敛变异法

生物在进化的过程中，一些个体的某些基因位以一定的几率发变异，由原本的1变成0，或者由0变成1，促进了生物群体的进化。然而当两个对象基因相同时，只能依靠基因变异产生新的基因和个体。本文提出一种加速收敛变异法，令个体的基因串前50%为高位，后50%为低位。在算法初期，首先在全局搜索出适应度高的优秀个体，设置其高位为高变异率，低位为低变异率。在寻找适应度高的优秀个体过程中，高位的变异率逐渐降低至0，低位的变异率慢慢增加，以此增加解的多样性。

2.6 适应度函数和解的修正

包簇资源分配问题，就是需要求出簇中资源分配到包的最低耗费，使其成本最低。

参照文献[16-17],把解的惩罚值引入适应度函数设计中。

惩罚值：该值等于分配到包的总资源与该簇总资源之差的绝对值和二者中较大者的比值。如果被分配到包的总资源与该簇的总资源相差越大，即包需求的总资源越大于或者越小于簇中所拥有的资源，此时惩罚值越大。则构造包簇资源分配的适应度函数如下：

式中：U(x,y)为成本函数。

设定成本密度函数ω为簇i的总成本与总资源的比值：

解的贪心修正：首先计算出簇的成本密度值并从小到大进行排序，然后在算出分配给簇的包所需要的总资源，如果超出该簇或服务器所拥有的资源。则需要重新匹配一个簇或服务器。如此循环直到满足包和簇的资源约束为止，得到符合条件的解。

2.7 算法具体步骤

Step1设定种群虚拟机的编码和各个参数。

Step2种群进行初始化。

Step3根据相似度定义，求出每个个体的相似度值，然后按照从小到大排序。

Step4选取序列中前10%的解，把解转换为十制数，然后除以2n-1得到小数后，进行混沌扰动，得到10%的新个体(且尽量保证个体的适应度值超过上一代)，若超过，则转下一步，若未超过则进行迭代，扰动次数加1，达到设定值转下一步。

Step5对剩余的其他个体进行精英保留选择，自适应交叉和收敛变异操作来产生新的个体。

Step6计算出新个体所需资源总量是否超过该簇拥有的资源总量，如果超过了则需要通过贪心修正。

Step7首先计算出每个包或者虚拟机的适应度函数值，并将之与上一代中的最大适应度个体进行比较，若新一代适应度函数值较大，则将该值保存、输出转step 3。否则直接转step 3。

Step8循环step 3到step 7操作直至进化代数达到设定值，输出最优解。

Step9在包最优解的情况下，类似于包的求解，求出包中包的最优资源分配解。一直递归求出最底层虚拟机映射到簇或者服务器的解。

3 仿真实验

本文设计的算法目标有两个，一是降低成本消耗；二是减少资源分配完成时间，提高资源分配效率。为了对算法进行验证，本文在基于包簇映射的框架下设计了3组实验，分别是基于混沌扰动遗传算法、简单遗传算法和粒子群算法进行对比实验。

三种算法在CloudSim云仿真平台上进行实验。实验环境为Sun Java SE 7。仿真参数设置：设置种群虚拟机数为I，每个虚拟机有J个任务资源需求。每q个虚拟机组合成一个一级包，每q个一级包，则生成一个二级包，依次递归生成，直到生成一个最高级的包。

虚拟机的任务资源需求矩阵如下：

ri,j表示虚拟机i对资源j的需求量。1≤i≤I，1≤j≤J。

最高级包的总资源需求矩阵如下：

设虚拟机的二进制编码为L；二进制编码初始化生成。

设有H个服务器，每个服务器有J个任务的种类资源。每p个服务器组合成一个一级簇，每p个一级簇，则生成一个二级簇，依次递归生成，直到生成一个最高级的簇。

服务器资源矩阵如下：

ah,j表示服务器h拥有资源j的量。1≤h≤H，1≤j≤J。

最高级簇总资源如下：

首先将最高级包先分配给最底层服务器，如果服务器资源不满足包资源的需求，则依次往上分配给一级簇，如果一级簇依旧不满足，则继续递归往上一级簇分配，直到满足包的资源需求为止。这时最高级包的下一级包，开始分配到该簇的下一级簇，依次递归，找到满足需要的最少资源簇即可。类似这种分配，直到虚拟机分配到具体的某个簇或者服务器上即可停止分配。

算法主要是以簇的运营成本U(x,y)为目标，分别用基于混沌扰动遗传算法、简单遗传算法和粒子群算法进行实验。实验具体参数如表1所示。

表1 GACD、PSO和GA算法参数设置表

小规模数据实验的结果如表2所示。

表2 小规模实验结果表

大规模数据实验的结果如表3所示。

表3 大规模实验结果表

收敛速度对比如表4所示。令虚拟机数量I=100，其他参数如表1所示。

表4 算法收敛速度实验对比表

为了实验的准确性，避免偶然情况，本文实验的每个算法都执行15次，然后对实验结果取平均值。图2、图3和图4是对三种算法的实验结果进行比较。

图2 小规模任务的完成时间比较

图3 大规模任务完成时间比较

图4 三种算法的收敛速度对比

从图2可以得出，在一定任务范围内，GACD、PSO、GA算法完成任务的时间差别不大。但从图3可以看出，在任务量比较多的情况下，GACD的任务完成时间最短，优势明显。从图4可以看出，本文改进的遗传算法收敛速度明显比较快，算法在迭代300次后快速收敛，开始趋向稳定。GACD算法形成的任务调度方案，对执行包簇映射下的资源分配所需要总时间较少，基本达成了最优化解决方案。

由实验可知，在包簇映射的框架下，基于混沌扰动遗传算法引入混沌扰动机制，利用混沌的遍历性和参数扰动策略，扩大了虚拟机种群的多样性，避免遗传算法陷入局部极小值，增强了遗传算法的全局搜索能力，并且在一定程度上使得该算法具有较高的搜索速度和收敛速度。

在时间上，通过图2和图3可知，GACD算法在资源分配的过程中，所需要时间最少，搜索速度最快，PSO算法次之。这是因为GACD算法采用混沌进行种群初始化，利用参数扰动策略进行快速搜索和资源分配。

在收敛速度上，通过图4可知，随着进化代数的增加，GACD算法采用了自适应交叉方式和加速收敛变异法，提高了算法的收敛速度，使得该算法的收敛速度快于PSO算法和GA算法。

在任务规模上，由图2和图3可得，GACD算法效率在小规模任务上略优于GA算法和PSO算法，但差距不明显，但是随着任务规模的不断扩大，在一定的任务范围之内GACD算法明显比PSO算法和GA算法效率更高。这是因为PSO算法和GA算法总是尽量把满足条件的资源分配给当前任务，当可用的资源较多时，完成的时间也较快。一旦任务量较大时，此时PSO算法和GA算法的缺陷也就开始显现出来。

4 结 语

本文主要是在基于包簇映射的框架下，通过改进遗传算法对云资源分配调度进行深入研究，引用混沌扰动机制对遗传算法的搜索操作进行了改进，并且对选择、交叉和变异操作进一步完善，详细地描述了算法实现步骤和原理。通过实验可以看出，该方法以耗费成本最低为目标，快速找到合适的云资源来进行分配，减少了任务调度的时间，提高了效率，具有较好的效果，实现了较为合理的任务调度方案。