面向云計(jì)算的云計(jì)算負(fù)載均衡優(yōu)化算法

面向云計(jì)算的云計(jì)算負(fù)載均衡優(yōu)化算法

0云計(jì)算負(fù)載均衡技術(shù)云計(jì)算已經(jīng)成為一種非常流行的商業(yè)計(jì)算模式。它是計(jì)算合并、分布計(jì)算和網(wǎng)絡(luò)計(jì)算的發(fā)展。云計(jì)算的“云”是一些可以自我維護(hù)和管理的虛擬計(jì)算資源。這些資源的自由組合和用戶任務(wù)的隨機(jī)性很容易使整個系統(tǒng)負(fù)載不平衡。因此，云計(jì)算的實(shí)施機(jī)制的重要組成部分是用戶任務(wù)與適當(dāng)資源的映射關(guān)系。也就是說，合理的任務(wù)需要調(diào)整，動態(tài)有效地管理資源，根據(jù)服務(wù)協(xié)議滿足服務(wù)需求。虛擬化技術(shù)在云資源的管理和動態(tài)配置中起關(guān)鍵作用,通過虛擬化技術(shù)可以將底層的各種硬件資源進(jìn)行封裝,以虛擬機(jī)為基本資源單位向用戶提供服務(wù).對用戶而言,所有底層資源均透明.理論上,每個用戶都有為其量身定制的虛擬機(jī),而且相互之間不受影響.每個物理主機(jī)會加載一個或多個虛擬機(jī),這樣就能夠保證用戶應(yīng)用程序運(yùn)行的獨(dú)立性.所以,云計(jì)算中的任務(wù)調(diào)度實(shí)質(zhì)上是在虛擬機(jī)之間進(jìn)行,保持整個虛擬機(jī)群的負(fù)載均衡是算法研究需要進(jìn)行的工作.云計(jì)算的任務(wù)調(diào)度模型如圖1所示.目前關(guān)于負(fù)載均衡方面的研究多針對物理機(jī)群.云計(jì)算虛擬機(jī)群的負(fù)載均衡優(yōu)化方面的研究工作還剛剛起步,文獻(xiàn)給出一種云計(jì)算環(huán)境下基于雙適應(yīng)度遺傳算法的任務(wù)調(diào)度方法,但是其優(yōu)化目標(biāo)只考慮了任務(wù)的響應(yīng)時間,通過該算法實(shí)現(xiàn)的只是總?cè)蝿?wù)完成時間最短和平均任務(wù)完成時間最短.由于云計(jì)算的中心思想就是實(shí)現(xiàn)廉價的高效運(yùn)算,所以除了任務(wù)響應(yīng)時間,整個計(jì)算過程中的資源利用率、能耗等方面也是對整個系統(tǒng)進(jìn)行負(fù)載均衡研究中需要繼續(xù)深入研究的問題.智能算法通過模擬或揭示某些自然現(xiàn)象或過程而得到發(fā)展,其思想和內(nèi)容涉及數(shù)學(xué)、物理學(xué)、生物進(jìn)化、人工智能、神經(jīng)科學(xué)和統(tǒng)計(jì)力學(xué)等方面,為解決復(fù)雜問題提供了新的思路和手段.如文獻(xiàn)引入了動態(tài)聯(lián)盟思想,提出一種基于PSO的任務(wù)分配算法,通過該算法有效地實(shí)現(xiàn)網(wǎng)絡(luò)環(huán)境的負(fù)載均衡.在組合優(yōu)化的問題中,遺傳算法(geneticalgorithm,GA)得到了廣泛的應(yīng)用.GA于1975年由J.Holland教授提出,它是一類借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法.GA算法的主要特點(diǎn)是可以直接對結(jié)構(gòu)對象進(jìn)行操作,并具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力.另外,GA算法采用概率化的尋優(yōu)方法,能自動獲取和指導(dǎo)優(yōu)化的搜索空間,從而自適應(yīng)地調(diào)整搜索方向,不需要確定的規(guī)則.為有效解決云計(jì)算虛擬機(jī)群下的負(fù)載均衡問題,本研究考慮任務(wù)響應(yīng)時間和虛擬機(jī)資源利用率兩個優(yōu)化目標(biāo),充分利用遺傳算法的優(yōu)化能力,設(shè)計(jì)并提出一種基于遺傳算法的負(fù)載均衡優(yōu)化算法,最后通過仿真實(shí)驗(yàn)驗(yàn)證所提算法的有效性.1主機(jī)資源調(diào)度虛擬化技術(shù)最大限度地使用戶的基礎(chǔ)架構(gòu)得到充分應(yīng)用.因此,存儲虛擬化和服務(wù)器虛擬化得到越來越多人的關(guān)注和利用.為了實(shí)現(xiàn)各種信息、服務(wù)和資源的高可用性,必須采用負(fù)載均衡設(shè)備來協(xié)調(diào)大量虛擬設(shè)備的管理,而研究云計(jì)算虛擬機(jī)群負(fù)載均衡的最終目標(biāo)是能夠公平有效地提高計(jì)算資源的利用率.高效的負(fù)載均衡算法要求系統(tǒng)能夠按照實(shí)際響應(yīng)時間,在性能不同的虛擬機(jī)之間進(jìn)行負(fù)載的智能分配,從而充分利用服務(wù)器群中的每一臺服務(wù)器,防止出現(xiàn)瓶頸和閑置資源浪費(fèi)問題.云環(huán)境中對虛擬機(jī)資源進(jìn)行調(diào)度與傳統(tǒng)的資源調(diào)度,既有相似之處,也有很多不同.首先,調(diào)度目標(biāo)不同,傳統(tǒng)的資源調(diào)度目標(biāo)是在實(shí)體資源上運(yùn)行的線程和任務(wù),屬于細(xì)粒度調(diào)度;而云計(jì)算環(huán)境下的調(diào)度目標(biāo)是虛擬機(jī)資源,屬于粗粒度調(diào)度,而且傳輸?shù)臄?shù)據(jù)量也較大.針對此類問題已有不少研究,研究人員已經(jīng)提出了多種靜態(tài)、動態(tài)和混合形式的資源調(diào)度策略[8,9,10,11,12,13,14,15,16].靜態(tài)調(diào)度算法有:ISH算法,MCP算法和ETF算法,這些算法是基于BNP(boundednumberprocessors)的,比較適合于具有高性能網(wǎng)絡(luò)的分布式環(huán)境中,但是由于云計(jì)算虛擬機(jī)群面向的應(yīng)用需求復(fù)雜多樣,以及服務(wù)成本也要求按需分配,這些算法就失去了實(shí)際意義.此外,也有許多研究者針對該問題進(jìn)行相應(yīng)的啟發(fā)式算法的設(shè)計(jì)研究,但是當(dāng)問題規(guī)模不斷擴(kuò)大,啟發(fā)式算法就顯得不那么有效了.本研究給出一種自適應(yīng)變異的遺傳算法用于解決虛擬機(jī)群的負(fù)載均衡問題,以便快速有效地確定任務(wù)與虛擬機(jī)之間的對應(yīng)關(guān)系,并找到一個最優(yōu)或近優(yōu)的調(diào)度方案,從而不但使任務(wù)執(zhí)行時間最短,又能使虛擬機(jī)群的資源利用率最高.仿真結(jié)果表明,該算法收斂速度快,運(yùn)行效率高,具有實(shí)際應(yīng)用價值.2資源費(fèi)和所費(fèi)時間節(jié)點(diǎn)城市圖2用戶任務(wù)集合如圖1所示,云計(jì)算環(huán)境中的負(fù)載均衡問題主要包括虛擬機(jī)群內(nèi)部任務(wù)調(diào)度和資源池中的虛擬機(jī)分配.在實(shí)際大型的云應(yīng)用中,還需要解決多個云之間的負(fù)載均衡.本研究主要考慮單個云中虛擬機(jī)群的負(fù)載均衡問題.假定虛擬機(jī)群中虛擬機(jī)數(shù)量為m,任務(wù)數(shù)量為n.模型的任務(wù)調(diào)度目標(biāo)就是在滿足用戶水平協(xié)議的基礎(chǔ)上,以最小的代價建立用戶任務(wù)—虛擬機(jī)之間的映射關(guān)系,這個代價包括所有用戶任務(wù)完成后的資源耗費(fèi)和所花費(fèi)的時間.1)用戶任務(wù)集合表示為:Q[q1,q2,…,qn],qi(i∈[1,n])表示編號為i的任務(wù),描述為qi{qt,qcpu,qmem},任務(wù)的屬性定義為:qt表示完成該任務(wù)所需的時間;qcpu表示任務(wù)的處理器需求;qmem表示任務(wù)的內(nèi)存需求;2)虛擬機(jī)集合表示為:V[v1,v2,…,vm],vi(i∈[1,m])表示編號為i的虛擬機(jī),描述為vi{vmaxcpu,vmaxmen},虛擬機(jī)的屬性定義為:vmaxcpu表示虛擬機(jī)的最大處理能力,vmaxmem表示虛擬機(jī)的最大內(nèi)存;3)定義分配方案矩陣:x(m,n).元素xi,j={0,1},當(dāng)xi,j=1時,表示任務(wù)j被分配到虛擬機(jī)i上,且有4)根據(jù)以上模型,虛擬機(jī)vi的執(zhí)行時間、已用CPU及已用內(nèi)存依次為:分配方案中要滿足如下約束關(guān)系:虛擬機(jī)群的執(zhí)行時間可以表示為:虛擬機(jī)vi的資源占用率:其中:k1,k2為權(quán)重系數(shù),k1+k2=1.虛擬機(jī)群的平均資源占用率:綜合以上的模型描述,虛擬機(jī)群的負(fù)載均衡優(yōu)化模型的的優(yōu)化目標(biāo)為:其中:c1,c2為權(quán)重系數(shù),c1+c2=1.3基于遺傳統(tǒng)計(jì)法的負(fù)載平衡算法3.1利用虛擬機(jī)號碼進(jìn)行求解采用整數(shù)編碼方式.染色體的長度為n,每個基因代表一個任務(wù),基因值為執(zhí)行該任務(wù)的虛擬機(jī)編號.假設(shè),m=6,n=20,即有6個虛擬機(jī),20個任務(wù),產(chǎn)生如下長度為20的染色體:然后對染色體進(jìn)行解碼,得到多組以虛擬機(jī)編號的任務(wù)隊(duì)列,上述染色體可以解碼為:根據(jù)染色體解碼后的結(jié)果,可計(jì)算VCR和pVsre.3.2群體規(guī)模的影響種群規(guī)模的選取對遺傳算法的收斂性能具有很大的意義,太大或是太小都會很大程度上影響算法性能.根據(jù)經(jīng)驗(yàn),群體規(guī)模一般取10~160.令種群規(guī)模SIZE,由系統(tǒng)隨機(jī)產(chǎn)生SIZE個染色體,染色體的初始長度為n,基因的取值范圍[1,m],在其中隨機(jī)取值.3.3優(yōu)化算法性能遺傳算法是根據(jù)適應(yīng)度來測度個體優(yōu)劣的,適應(yīng)度函數(shù)就是問題中全體對象與其適用度之間的對應(yīng)關(guān)系.在本研究的負(fù)載均衡優(yōu)化算法中,有如下目標(biāo):1)虛擬機(jī)群的執(zhí)行時間最短,即min(VCR);2)能耗最小.本研究用資源利用率來量化虛擬機(jī)群的能耗,虛擬機(jī)資源利用得越充分則能耗越小,同時這項(xiàng)指標(biāo)也能夠提高系統(tǒng)的負(fù)載均衡度,即max(pVsre);由于遺傳算法在進(jìn)化初期會出現(xiàn)超常個體,這些個體的突出競爭力會影響算法的全局優(yōu)化性能;而進(jìn)化后期,種群內(nèi)的個體差異性變小,會導(dǎo)致某個局部最優(yōu)解.因此,這里根據(jù)以上兩個優(yōu)化指標(biāo),直接將式(5)作為適用度函數(shù)的構(gòu)造,具體可表示為:3.4算法4添加多個種類變異1)個體選擇.選擇操作是模擬生物界優(yōu)勝劣汰的自然選擇的一種染色體運(yùn)算,就是從種群中選擇適用度較高的染色體進(jìn)行復(fù)制,以生成下一代種群.則個體i被選中的概率函數(shù)為:采用輪盤賭的選擇方式,計(jì)算個體i的累積概率:2)交叉操作.交叉操作模仿生物界有性繁殖的基因重組過程,即編碼的交叉重組,類似于染色體的交叉重組,從而產(chǎn)生具有更優(yōu)良基因的染色體,交叉概率一般為0.4~0.99之間.采用順序交叉方法(orderedcrossover)的交叉操作.例如,假設(shè)兩個父代個體:若隨機(jī)投點(diǎn)投到第5個基因,則p1的交叉區(qū)域原基因串tp1=,p2的交叉區(qū)域原基因串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進(jìn)行同樣的操作,得到np2=[2,3,5,5,3,1,1,6,2,4,2,1,6,4,3,3,2,4,4,4].3)變異操作.變異操作是編碼按小概率擾動產(chǎn)生的變化,類似于基因突變,變異概率一般為0.0001~0.1.采用整數(shù)變異,即隨機(jī)取點(diǎn),并用不同于所選基因值的整數(shù)替換該基因,該整數(shù)取值范圍為:[1,m].例如對父代個體p1進(jìn)行變異操作,若隨機(jī)投點(diǎn)投到第8個基因,該點(diǎn)基因值為1,在范圍內(nèi)隨機(jī)取不等于1的數(shù),假設(shè)隨機(jī)數(shù)取值為2,則對p1進(jìn)行變異后得新個體np1=[2,3,5,5,3,4,5,2,4,1,3,2,6,1,5,6,6,5,3,3].為了保證算法的空間搜索性能,并有效地提高算法的收斂性能,引入自適應(yīng)變異概率.為每個個體添加一個變異概率屬性:pmk表示個體k的變異概率,假設(shè)當(dāng)前最佳個體的適用度為fbest,個體k的適用度為f(k),則:4算法性能分析應(yīng)用MATLAB進(jìn)行仿真實(shí)驗(yàn),虛擬機(jī)群規(guī)模為128,任務(wù)數(shù)為320.經(jīng)過試驗(yàn)分析,算法的最終最大進(jìn)化代數(shù)設(shè)定為200.優(yōu)化模型中的任務(wù)執(zhí)行時間、處理器和內(nèi)存資源在算法實(shí)現(xiàn)過程中均以隨機(jī)性的進(jìn)行量化.由于遺傳算法批量化的優(yōu)化方式,每次處理的是整個等待隊(duì)列中的所有任務(wù),當(dāng)任務(wù)隊(duì)列發(fā)生變動時整個解空間將隨之改變,所以本研究只針對靜態(tài)的任務(wù)隊(duì)列進(jìn)行試驗(yàn)驗(yàn)證.此外,令目標(biāo)函數(shù)中處理器和內(nèi)存的權(quán)重相等,即k1=k2=0.5.為驗(yàn)證所提算法在收斂速度和收斂穩(wěn)定性上的進(jìn)步,將其與固定變異概率的遺傳算法進(jìn)行比較,兩者取相同的初始變異概率以保證公平性.從圖2可以看出,本算法在收斂速度和收斂的穩(wěn)定性上都有較大進(jìn)步.所建模型同時對虛擬機(jī)群的執(zhí)行時間和資源利用率進(jìn)行了雙目標(biāo)優(yōu)化.事實(shí)上,資源利用率的提升一定會不同程度地犧牲執(zhí)行時間的優(yōu)化效果,但是對于一個實(shí)用性的系統(tǒng),更側(cè)重的是其綜合性能的提高.所以,云計(jì)算環(huán)境中的虛擬機(jī)群應(yīng)在滿足用戶需求的基礎(chǔ)上盡可能提高資源利用率,從而發(fā)揮云服務(wù)的低成本運(yùn)營優(yōu)勢.為驗(yàn)證所建模型的綜合性能優(yōu)勢,將優(yōu)化結(jié)果與以執(zhí)行時間為目標(biāo)的單目標(biāo)優(yōu)化結(jié)果進(jìn)行比較.提出RUincrease(資源利用率提升度)和TMextend(執(zhí)行時間延長度)兩個概念,以便于進(jìn)行模型評估,并有如下定義:假定單目標(biāo)優(yōu)化得到的資源利用率和虛擬機(jī)群執(zhí)行時間分別為Sru和Stm,按本模型的雙目標(biāo)優(yōu)化得到的資源利用率和虛擬機(jī)群執(zhí)行時間分別為Dru和Dtm;優(yōu)化過程中資源利用率和執(zhí)行時間所占比重不同,會導(dǎo)致不同的優(yōu)化結(jié)果.隨著執(zhí)行時間所占比重c1的增加,如果RUincrease和TMextend同時隨之減小但始終都大于0,則說明模型的可用性;而在同一組c1和c2的優(yōu)化過程中,RUincrease越大,TMextend越小,則越能說明模型的有效性.分別令c1=0.3,c2=0.7;c1=0.5,c2=0.5;c1=0.7,c2=0.3進(jìn)行實(shí)驗(yàn)對比,圖3顯示了所提模型的可用性和有效性.5負(fù)載均衡優(yōu)化算法仿真環(huán)境傳統(tǒng)負(fù)載均衡研究中的任務(wù)調(diào)度是直接把任務(wù)調(diào)度到主機(jī)資源上,這種模式不能很好地滿足用戶任務(wù)對計(jì)算資源的動態(tài)需求.基于云計(jì)算的基礎(chǔ)架構(gòu)虛擬化這