基于粒子群优化算法的虚拟机部署策略-杨靖.pdf
《基于粒子群优化算法的虚拟机部署策略-杨靖.pdf》由会员分享,可在线阅读,更多相关《基于粒子群优化算法的虚拟机部署策略-杨靖.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Joumal of Computer Applications计算机应用,2016,36(1):117一12lISSN 1001908lCODEN JYIIDU20160110http:wwwjocacn文章编号:10019081(2016)01011705 DOI:lO11772jissn100190812016010117基于粒子群优化算法的虚拟机部署策略杨靖。,张宏军,赵水宁,占栋辉(解放军理工大学仿真与数据中心,南京210007)(通信作者电子邮箱262986127qqcom)摘要:针对云计算基础设施即服务(Iaas)中的虚拟机部署问题。提出一种基于粒子群优化(PsO)算法的部署策略。
2、由于Ps0算法在处理虚拟机部署这类大规模复杂问题时,具有收敛速度慢且容易陷入局部最优的缺点,首先,引入多种群进化模式提高算法收敛速度,并在此基础上加入高斯学习策略避免局部最优,提出了一种多种群高斯学习粒子群优化(MGLPS0)算法;然后,根据部署模型,使用轮询(RR)算法对MGLPs0进行初始化,进而提出了一种以负载均衡为目标的虚拟机部署策略。通过在C10udsim中进行仿真实验,验证了在解决虚拟机部署问题时,MGLPs0相比PS0算法,具有更快的收敛速度,并且负载不均衡度降低了131。在两种实验场景下,所提算法相比随机负载均衡(0LB)算法,其负载不均衡度分别平均降低了25和15;相比贪婪算
3、法(GA),使负载不均衡度分别平均降低了19和7。关键词:虚拟机部署;粒子群优化;负载均衡;高斯学习;多种群进化中图分类号:TP31l;TPl8 文献标志码:AVirtuaI machine depIoyment strategy based on parHcle swam optimizati衄algorithmYANG Jing 1,zHANG Hon舀un,ZHA0 Shuining,ZHAN Donghui(ce眈,矿muf加口以Dn眠JP“眈m毋&如n口材死cM如彩胞彬昭肋懈210007,im)AbstrIact:To solve the virtual machine deploy
4、ment problem in 111fhstmcture as a Service(IaaS)of cloud computill昏 avirtual machine deployment stmlegy based on Particle Swa珊0ptimiza舶n(PS0)algorithm was proposed Since fbe PSOalgorithm has weaknesses of having a slow convergence speed and fal】ing jnto kcal optimum easi】y when dealir垮with 1arge-sca
5、le and complex pmblems like vjrtual machine deployment,nrstly,a Multiplepopulation Gaussian Lleaming Particle Swa珊0ptimization(MGLPS0) algorithm was pmposed,with using the model of multiple population eVolution to accelerate tIlealgorithm convergence,as weU as adding Gaussian leaming stmte盱to avoid
6、local optimumThen according to the deploymentmodel,wjth using Round Robin(RR)algorithm to in谢alize the MGLPS0,a vinual machjne deployment strateg),aiming to10ad balancing was proposed ,Ilrou曲the simulation experiment in cloudsim, it validates that MGLPs0 has a higherconvergence speed and load imbala
7、nce degree is Ieduced by 13殇 compared with PSO algorithm In the two experimentalsituations,compared with the 0pportunistic Load Balancing(0LB)algori山m,the 10ad imbalance de黟ees of the pmposedalgorifhm decrease by 25and 15respectively,and compared with the Greedy Algorithm(GA)the load imbalance degre
8、esdecrease by 19and 7respectivelyKey worEls: virtual machine deployment;f)anicle Swa珊0ptimization(PSO); load balancing; Gaussian 1e哪ing;muhiple population evolution0 引言基础设施即服务(Infrastmcture as a Seice,IaaS)是云计算中最为基础的服务类型。用户向Iaas服务商提出服务申请,Iaas服务商通过把cPu、内存、硬盘存储等资源通过虚拟化技术封装在虚拟机中,并以虚拟机为单位提供给用户。云数据中心(clo
9、ud Data centre,cDc)大量使用这种虚拟化技术,使多台虚拟机能同时部署在一台物理机中,然而由于虚拟机和物理机配置存在差异性,所以建设云数据中心需要解决虚拟机部署问题。云计算是一种通过提供服务而获取利益的商业化模式,并通过云数据中心提供高质量服务从而满足用户需求。wickremasinghe等2 3证明,通过使用负载均衡调度策略可以改善服务质量,并且负载均衡策略的好坏决定改善的程度。I(1einbe职等o证明,当只考虑考虑单一cPu资源的负载均衡调度时,这种负载均衡词度问题(L0adbalance SchedulingPmblem,LsP)可在一个多项式时间内被规约成子集求和问题。
10、文献4提出在实际环境中,需要被考虑的资源不只cPu一种,问题就会变得更加复杂,因此,在部署虚拟机时,如何平衡物理机资源的负载是一个NPHard组合优化问题。目前,Eucalyptus、0penNebulao等,大多开源的IaaS解决方案只是简单地使用贪婪算法进行虚拟机部署,由于贪婪算法没收稿日期:2015一07-27;修回日期:20150915。作者简介:杨靖(199l一),男,江西鹰潭人,硕士研究生,主要研究方向:服务计算、计算机网络;张宏军(1963一),男,江苏泰州人,教授,博士,主要研究方向:军用数据与知识工程;赵水宁(1971一),男,江西南昌人,副教授,博士,主要研究方向:服务计算
11、、计算机网络; 占栋辉(1988一),男,江西上饶人,博士研究生,主要研究方向:智能算法、数据挖掘。万方数据n8 计算机应用 第36卷有考虑虚拟机和物理机的差异性,为了平衡物理机负载,在实际使用这些解决方案时通常由使用者自己编写算法。迄今为止,已有研究者使用智能优化算法来解决虚拟机部署问题并取得了较好的效果,文献7提出一种基于蚁群优化算法的虚拟机部署策略;文献8提出一种基于遗传算法的虚拟机部署策略。粒子群优化(Panicle swanIl0ptimization,PS0)算法一。相比其他几种智能优化算法,具有概念简单、易于实现、参数较少以及无需梯度信息等优势,因此,也有研究者使用PsO算法解决
12、虚拟机部署问题。例如,文献10提出一种以节能为目标的基于PS0算法虚拟机部署策略;文献11提出一种多目标的基于PSo算法虚拟机部署策略,但Ps0算法在处理复杂的问题时,仍然存在收敛速度慢、容易陷入局部最优等缺陷,因此,本文提出多种群高斯学习粒子群优化(Multiplepopulation Gaussian k锄ing PaIticleswanIl 0ptimization,MGLPS0)算法,并与轮询(Round Robin,RR)算法结合得到一种以物理机负载均衡为目标的基于粒子群算法的虚拟机部署策略。最后,通过仿真实验,MGLPs0算法相比PSO算法在处理虚拟机部署问题时,收敛速度和搜索精度
13、有显著提升,并且MGLPSO算法在物理机负载均衡方面优于随机负载均衡(0pponunistic IJ0ad Balancing,OLB)算法和贪婪算法(Greedy Algorithm,GA)两种经典的负载均衡算法。1 虚拟机部署模型11部署模型针对云环境下的虚拟机部署,通过使用n个虚拟机和m个物理机组成的五元组来描述:Q=(y,P,D,A,s。)。其中:I,表示几个虚拟机组成的虚拟机集合:P表示m个物理机所组成的物理机集合;D表示虚拟机部署问题的优化目标;A表示使用的优化算法;s。表示虚拟机映射到物理机的资源部署向量。部署模型的具体特征描述如下:1)虚拟机集合I,=。,:,。,表示一个云数据
14、中心需要进行部署的虚拟机,还可以进一步细化为CPU、内存、硬盘存储、网络带宽4种资源。,=i忧P(,蹦em。仞蠡后,阽(,=1,2,凡),其中:,为虚拟机编号,阳P、聊帆,、旧厶,、阳夥分别表示虚拟机需要的cPu大小、内存大小、存储大小和网络带宽。2)物理机资源集合P=Pm。,Pm:,Pm。,每个物理机相互独立,物理机资源还可以进一步细化为CPu、内存、硬盘存储和网络带宽4种资源。Pm。=PcPU,删em。,PD;5Jj。,P嚣夥(t=l,2,m),其中:i表示物理机编号,ycP。、m如m。、仞is后。、馏阢分别表示物理机自身的cPu大小、内存大小、存储大小和网络带宽。3)资源部署向量S。=(
15、s:)(j=1,2,R),表示虚拟机j部署在物理机0上。若S。=(4 2 4 1 3),表示l号虚拟机部署在4号物理机上,2号虚拟机部署在2号物理机上,5号虚拟机部署在3号物理机上。4)由资源部署向量可以得到资源使用矩阵E。:(8#)(i=1,2,m;j=1,2,n),当;=s,且s,s。时,e。,=l,其余为0。当e。=l表示虚拟机J部署在物理机i上。5)由资源使用矩阵得到虚拟机部署约束条件如下y(阳PU,e。)PcPu一、 , v,=l(啪em,ei)尸讹m。”1; i=j,2,m (1)n(阳咄e。)肋姚J 2l(馏夥e。)P8形。其含义是在物理机i上部署的所有虚拟机需要的cPu大小、内
16、存大小、存储大小和网络带宽不能超过物理机i所能提供的大小。12负载均衡度量指标由于虚拟机和物理机配置的差异性,云数据中心容易出现负载不均的情况,部分物理枧上部署了过多的虚拟机,物理机会达到性能瓶颈,并且影响虚拟机的性能,而另一些物理机则可能负载较轻,物理机没有得到充分的利用。这种负载不均的情况直接影响云数据中心物理机的高效利用,造成IaaS服务商提供服务的质量下降。为了避免这种情况,需要通过合理的虚拟机部署策略保持物理机负载均衡。文献1213提出了一些负载均衡调度的度量指标本文通过参考这些度量指标,使用一种综合考虑cPu、内存、硬盘存储、网络带宽4种物理机资源的度量指标来比较物理机负载均衡效果
17、。为了得到度量指标,根据部署模型,考虑以下参数。1)当所有虚拟机部署完成时,由资源使用矩阵E物理机可以得到Pm。的cPu利用率:尸cP畔=I(脚q x ei)lPc尸玑 (2),2I其中:P他内存利用率P胁m?,存储利用率PD触?和带宽利用率P日孵都可以用相同方式计算。2)所有虚拟机部署完成时,云数据中心物理机cPu平均利用率:尸cPu。=(PcP畔)m (3)2l云数据中心物理机内存平均利用率删em:。,存储平均利用率PD越:。和带宽平均利用率p曰联。可以用相同方式计算。3)云数据中心物理机的CPu负载不均衡度:脚,cr。=f(PcP蝶。一PcP畔)2 Im (4)其中抛嚣jc,。表示云数据
18、中心物理机的cPu负载不均衡度,其值越小表示物理机的cPu负载越均衡。物理机的内存负载不均衡度曰,存储负载不均衡度舰曰,。i矗和带宽负载不均衡度舭8,。可以用相同方式计算。4)云数据中心物理机综合负载不均衡度:NLBf呲d=INLBI。Pu+m2NLBlM。+m3NLBID。妇+u。LBjBw (5)其中:,、:、叫。分别表示物理机的cPu负载不均衡度的权值、内存负载不均衡度的权值、存储负载不均衡度的权值以及带宽负载不均衡度的权值。本文中。、:、甜,、。的初始值万方数据第l期 杨靖等:基于粒子群优化算法的虚拟机部署策略 119为l,根据实际情况的不同,通过加大或者减小这些权值,从而增强或者减弱
19、权值对应的资源的负载性能。舭B,。就是本文用来比较物理机负载均衡效果的度量指标,其值越小表示物理机的综合负载均衡效果越好。5)本文虚拟机部署问题就是就求最小负载不均衡度的问题,目标函数可以描述为:DB吲(5)=min(LB,f。l(s);sS (6)其中:所有满足约束条件(1)的部署方案s组成部署方案域s,z口,I。“(s)为部署方案s的综合负载不均衡度。2 改进粒子群优化算法21算法原理PSO算法是一种基于迭代的启发式优化算法。算法原理可以简单描述为:由个没有体积和质量的粒子个体组成的粒子群在维度为D的空间进行搜索,每一个粒子都有速度和位置两个属性,算法通过速度来更新粒子位置,而每个粒子位置
20、代表了搜索空间中的一个解。本文算法考虑这些参数:第i个粒子当前位置,z。=(石彳。,戈。);第i个粒子的速度,口i=(n口,口。D);粒子的历史最优位置,p。=(pp。,加)(|p6郎。),以及粒子的全局最优位置,段=(p加p92,p加)(96倒)。在搜索过程中,粒子每一次更新都必须参照两个最优位置,一个是粒子个体当前发现的个体历史最优位置p6删i,另一个是群体当前发现的全局最优位置96es,如此重复更新,直到满足条件,最后找出最优解。具体更新公式表示如下:”譬1=cu口:+cl ro玎d1:(p0一石名)+c2 rnnd2:(p二一工:d)(7)石譬1=z0+譬1 (8)其中:i=l,2,;
21、d=l,2,D;f为迭代次数;山表示惯性权重;c。和c:为加速常数;rondl乙和r。n以:是。到1之间均匀分布的随机数;”0表示当前粒子i的速度;”譬1表示更新后粒子i的速度;戈0表示当前粒子i的位置;z譬1表示更新后粒子i的位置。22多种群进化模式MGLPS0算法使用多种群进化模式,将粒子分为大小相等的P“m个子群进行进化,并且通过在粒子速度更新中加入所有子群的整体全局最优粒子以提高算法的收敛速度。MGLPS0算法的具体更新公式表示如下:甜茹1=D秽0+clm丹d1(p之一茗)+c2r口露垃乞卢I(p一戈:d)+c3r口nd3名肛2(p:一z:“) (9)戈翁=石0+F茹1 (10)其中文
22、j、#分别表示子群编号、粒子编号、迭代次数;p乏表示在次迭代后第i个子群中第j个粒子的历史最优位置;P厶表示在f次迭代后第i个子群的历史最优位置;正表示在次迭代后所有子群的整体历史最优位置。式(9)与PS0算法速度更新式(7)相比,增加了第4部分整体历史最优反馈。其主要目的是为了使多个子群中的全部粒子都能向整体历史最优位置移动,从而提高算法的收敛速度,并且为了降低当前历史最优粒子的影响,保持粒子的多样性,避免陷入局部最优同时避免粒子速度过大增加影响因子pl和p2,p1=05,心=025。23高斯学习机制文献14通过采用高斯学习机制对全局最优粒子进行调整,保持粒子的多样性避免陷入局部最优。MGL
23、PSO算法通过采用高斯学习机制在多种群进化模式的基础上对每个子群的历史最优位置进行调整,保持每个子群的粒子多样性,避免子群陷入局部最优。McLPsO算法随机选择每个子群历史最优位置其中的一维P:进行高斯学习得到新的子群历史最优位置,如果新的历史最优位置优于聪,则更新它;否则保留。每一维都有相同的概率被选中,所以在统计学上可以认为这一学习机制作用于每个子群历史最优位置的每一维。具体的高斯学习公式如下:心=露+(M。xM抽)Gaussian(p,盯2) (11)其中:i=random(1,Pum),d=random(1,D),P:表示第i个子群的历史最优位置,d表示随机选择的某一维度,施忍,讹戈为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 粒子 优化 算法 虚拟机 部署 策略 杨靖
限制150内