面向云计算的云计算负载均衡优化算法

面向云计算的云计算负载均衡优化算法

0云计算负载均衡技术云计算已经成为一种非常流行的商业计算模式。它是计算合并、分布计算和网络计算的发展。云计算的“云”是一些可以自我维护和管理的虚拟计算资源。这些资源的自由组合和用户任务的随机性很容易使整个系统负载不平衡。因此，云计算的实施机制的重要组成部分是用户任务与适当资源的映射关系。也就是说，合理的任务需要调整，动态有效地管理资源，根据服务协议满足服务需求。虚拟化技术在云资源的管理和动态配置中起关键作用,通过虚拟化技术可以将底层的各种硬件资源进行封装,以虚拟机为基本资源单位向用户提供服务.对用户而言,所有底层资源均透明.理论上,每个用户都有为其量身定制的虚拟机,而且相互之间不受影响.每个物理主机会加载一个或多个虚拟机,这样就能够保证用户应用程序运行的独立性.所以,云计算中的任务调度实质上是在虚拟机之间进行,保持整个虚拟机群的负载均衡是算法研究需要进行的工作.云计算的任务调度模型如图1所示.目前关于负载均衡方面的研究多针对物理机群.云计算虚拟机群的负载均衡优化方面的研究工作还刚刚起步,文献给出一种云计算环境下基于双适应度遗传算法的任务调度方法,但是其优化目标只考虑了任务的响应时间,通过该算法实现的只是总任务完成时间最短和平均任务完成时间最短.由于云计算的中心思想就是实现廉价的高效运算,所以除了任务响应时间,整个计算过程中的资源利用率、能耗等方面也是对整个系统进行负载均衡研究中需要继续深入研究的问题.智能算法通过模拟或揭示某些自然现象或过程而得到发展,其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面,为解决复杂问题提供了新的思路和手段.如文献引入了动态联盟思想,提出一种基于PSO的任务分配算法,通过该算法有效地实现网络环境的负载均衡.在组合优化的问题中,遗传算法(geneticalgorithm,GA)得到了广泛的应用.GA于1975年由J.Holland教授提出,它是一类借鉴生物界的进化规律演化而来的随机化搜索方法.GA算法的主要特点是可以直接对结构对象进行操作,并具有内在的隐并行性和更好的全局寻优能力.另外,GA算法采用概率化的寻优方法,能自动获取和指导优化的搜索空间,从而自适应地调整搜索方向,不需要确定的规则.为有效解决云计算虚拟机群下的负载均衡问题,本研究考虑任务响应时间和虚拟机资源利用率两个优化目标,充分利用遗传算法的优化能力,设计并提出一种基于遗传算法的负载均衡优化算法,最后通过仿真实验验证所提算法的有效性.1主机资源调度虚拟化技术最大限度地使用户的基础架构得到充分应用.因此,存储虚拟化和服务器虚拟化得到越来越多人的关注和利用.为了实现各种信息、服务和资源的高可用性,必须采用负载均衡设备来协调大量虚拟设备的管理,而研究云计算虚拟机群负载均衡的最终目标是能够公平有效地提高计算资源的利用率.高效的负载均衡算法要求系统能够按照实际响应时间,在性能不同的虚拟机之间进行负载的智能分配,从而充分利用服务器群中的每一台服务器,防止出现瓶颈和闲置资源浪费问题.云环境中对虚拟机资源进行调度与传统的资源调度,既有相似之处,也有很多不同.首先,调度目标不同,传统的资源调度目标是在实体资源上运行的线程和任务,属于细粒度调度;而云计算环境下的调度目标是虚拟机资源,属于粗粒度调度,而且传输的数据量也较大.针对此类问题已有不少研究,研究人员已经提出了多种静态、动态和混合形式的资源调度策略[8,9,10,11,12,13,14,15,16].静态调度算法有:ISH算法,MCP算法和ETF算法,这些算法是基于BNP(boundednumberprocessors)的,比较适合于具有高性能网络的分布式环境中,但是由于云计算虚拟机群面向的应用需求复杂多样,以及服务成本也要求按需分配,这些算法就失去了实际意义.此外,也有许多研究者针对该问题进行相应的启发式算法的设计研究,但是当问题规模不断扩大,启发式算法就显得不那么有效了.本研究给出一种自适应变异的遗传算法用于解决虚拟机群的负载均衡问题,以便快速有效地确定任务与虚拟机之间的对应关系,并找到一个最优或近优的调度方案,从而不但使任务执行时间最短,又能使虚拟机群的资源利用率最高.仿真结果表明,该算法收敛速度快,运行效率高,具有实际应用价值.2资源费和所费时间节点城市图2用户任务集合如图1所示,云计算环境中的负载均衡问题主要包括虚拟机群内部任务调度和资源池中的虚拟机分配.在实际大型的云应用中,还需要解决多个云之间的负载均衡.本研究主要考虑单个云中虚拟机群的负载均衡问题.假定虚拟机群中虚拟机数量为m,任务数量为n.模型的任务调度目标就是在满足用户水平协议的基础上,以最小的代价建立用户任务—虚拟机之间的映射关系,这个代价包括所有用户任务完成后的资源耗费和所花费的时间.1)用户任务集合表示为:Q[q1,q2,…,qn],qi(i∈[1,n])表示编号为i的任务,描述为qi{qt,qcpu,qmem},任务的属性定义为:qt表示完成该任务所需的时间;qcpu表示任务的处理器需求;qmem表示任务的内存需求;2)虚拟机集合表示为:V[v1,v2,…,vm],vi(i∈[1,m])表示编号为i的虚拟机,描述为vi{vmaxcpu,vmaxmen},虚拟机的属性定义为:vmaxcpu表示虚拟机的最大处理能力,vmaxmem表示虚拟机的最大内存;3)定义分配方案矩阵:x(m,n).元素xi,j={0,1},当xi,j=1时,表示任务j被分配到虚拟机i上,且有4)根据以上模型,虚拟机vi的执行时间、已用CPU及已用内存依次为:分配方案中要满足如下约束关系:虚拟机群的执行时间可以表示为:虚拟机vi的资源占用率:其中:k1,k2为权重系数,k1+k2=1.虚拟机群的平均资源占用率:综合以上的模型描述,虚拟机群的负载均衡优化模型的的优化目标为:其中:c1,c2为权重系数,c1+c2=1.3基于遗传统计法的负载平衡算法3.1利用虚拟机号码进行求解采用整数编码方式.染色体的长度为n,每个基因代表一个任务,基因值为执行该任务的虚拟机编号.假设,m=6,n=20,即有6个虚拟机,20个任务,产生如下长度为20的染色体:然后对染色体进行解码,得到多组以虚拟机编号的任务队列,上述染色体可以解码为:根据染色体解码后的结果,可计算VCR和pVsre.3.2群体规模的影响种群规模的选取对遗传算法的收敛性能具有很大的意义,太大或是太小都会很大程度上影响算法性能.根据经验,群体规模一般取10~160.令种群规模SIZE,由系统随机产生SIZE个染色体,染色体的初始长度为n,基因的取值范围[1,m],在其中随机取值.3.3优化算法性能遗传算法是根据适应度来测度个体优劣的,适应度函数就是问题中全体对象与其适用度之间的对应关系.在本研究的负载均衡优化算法中,有如下目标:1)虚拟机群的执行时间最短,即min(VCR);2)能耗最小.本研究用资源利用率来量化虚拟机群的能耗,虚拟机资源利用得越充分则能耗越小,同时这项指标也能够提高系统的负载均衡度,即max(pVsre);由于遗传算法在进化初期会出现超常个体,这些个体的突出竞争力会影响算法的全局优化性能;而进化后期,种群内的个体差异性变小,会导致某个局部最优解.因此,这里根据以上两个优化指标,直接将式(5)作为适用度函数的构造,具体可表示为:3.4算法4添加多个种类变异1)个体选择.选择操作是模拟生物界优胜劣汰的自然选择的一种染色体运算,就是从种群中选择适用度较高的染色体进行复制,以生成下一代种群.则个体i被选中的概率函数为:采用轮盘赌的选择方式,计算个体i的累积概率:2)交叉操作.交叉操作模仿生物界有性繁殖的基因重组过程,即编码的交叉重组,类似于染色体的交叉重组,从而产生具有更优良基因的染色体,交叉概率一般为0.4~0.99之间.采用顺序交叉方法(orderedcrossover)的交叉操作.例如,假设两个父代个体:若随机投点投到第5个基因,则p1的交叉区域原基因串tp1=,p2的交叉区域原基因串tp2=.在父代个体p1中按序查找tp2中的各基因值,并向前移位使查找出的基因顺序与tp2一致,得到新个体,np1=[1,1,6,2,2,3,5,5,3,4,5,4,3,1,5,6,6,5,3,3].同样,对父代个体p2和交叉基因串tp1进行同样的操作,得到np2=[2,3,5,5,3,1,1,6,2,4,2,1,6,4,3,3,2,4,4,4].3)变异操作.变异操作是编码按小概率扰动产生的变化,类似于基因突变,变异概率一般为0.0001~0.1.采用整数变异,即随机取点,并用不同于所选基因值的整数替换该基因,该整数取值范围为:[1,m].例如对父代个体p1进行变异操作,若随机投点投到第8个基因,该点基因值为1,在范围内随机取不等于1的数,假设随机数取值为2,则对p1进行变异后得新个体np1=[2,3,5,5,3,4,5,2,4,1,3,2,6,1,5,6,6,5,3,3].为了保证算法的空间搜索性能,并有效地提高算法的收敛性能,引入自适应变异概率.为每个个体添加一个变异概率属性:pmk表示个体k的变异概率,假设当前最佳个体的适用度为fbest,个体k的适用度为f(k),则:4算法性能分析应用MATLAB进行仿真实验,虚拟机群规模为128,任务数为320.经过试验分析,算法的最终最大进化代数设定为200.优化模型中的任务执行时间、处理器和内存资源在算法实现过程中均以随机性的进行量化.由于遗传算法批量化的优化方式,每次处理的是整个等待队列中的所有任务,当任务队列发生变动时整个解空间将随之改变,所以本研究只针对静态的任务队列进行试验验证.此外,令目标函数中处理器和内存的权重相等,即k1=k2=0.5.为验证所提算法在收敛速度和收敛稳定性上的进步,将其与固定变异概率的遗传算法进行比较,两者取相同的初始变异概率以保证公平性.从图2可以看出,本算法在收敛速度和收敛的稳定性上都有较大进步.所建模型同时对虚拟机群的执行时间和资源利用率进行了双目标优化.事实上,资源利用率的提升一定会不同程度地牺牲执行时间的优化效果,但是对于一个实用性的系统,更侧重的是其综合性能的提高.所以,云计算环境中的虚拟机群应在满足用户需求的基础上尽可能提高资源利用率,从而发挥云服务的低成本运营优势.为验证所建模型的综合性能优势,将优化结果与以执行时间为目标的单目标优化结果进行比较.提出RUincrease(资源利用率提升度)和TMextend(执行时间延长度)两个概念,以便于进行模型评估,并有如下定义:假定单目标优化得到的资源利用率和虚拟机群执行时间分别为Sru和Stm,按本模型的双目标优化得到的资源利用率和虚拟机群执行时间分别为Dru和Dtm;优化过程中资源利用率和执行时间所占比重不同,会导致不同的优化结果.随着执行时间所占比重c1的增加,如果RUincrease和TMextend同时随之减小但始终都大于0,则说明模型的可用性;而在同一组c1和c2的优化过程中,RUincrease越大,TMextend越小,则越能说明模型的有效性.分别令c1=0.3,c2=0.7;c1=0.5,c2=0.5;c1=0.7,c2=0.3进行实验对比,图3显示了所提模型的可用性和有效性.5负载均衡优化算法仿真环境传统负载均衡研究中的任务调度是直接把任务调度到主机资源上,这种模式不能很好地满足用户任务对计算资源的动态需求.基于云计算的基础架构虚拟化这