云計算虛擬資源差分進(jìn)化分配方法仿真

高 楊,馬賀男,劉曉菲

(1. 中國刑事警察學(xué)院公安信息技術(shù)與情報學(xué)院,遼寧 沈陽 110034;2. 沈陽航空航天大學(xué),遼寧 沈陽 110136)

1 引言

云計算為并行計算、分布式計算、虛擬化等技術(shù)的演變,作為一種全新的商業(yè)計算模型,可以把大量的軟件資源、存儲資源匯集在一起,給用戶提供了更為方便與安全的網(wǎng)絡(luò)服務(wù)[1-2]。但云平臺集群規(guī)模較大,集群節(jié)點之間存在一定的差異性,在此背景下,用戶的服務(wù)請求各不相同,資源類別的科學(xué)劃分和云計算虛擬資源的高效率分配成為云計算領(lǐng)域研究的重點課題[3]。

相關(guān)學(xué)者從不同角度,就上述內(nèi)容給出如下解決方案:倪思源[4]等把不同類別的資源擬作不同維度矢量,利用計算裝箱問題達(dá)到負(fù)載均衡,給各虛擬機(jī)設(shè)置駐留時長,輪換計算服務(wù)器負(fù)載情況,實現(xiàn)資源分配工作。王鎮(zhèn)道[5]等構(gòu)建涵蓋時間、功耗和負(fù)載均衡的適應(yīng)度函數(shù),運用混沌優(yōu)化生成初始化粒子,代入高斯變異更新勝利粒子方位,找出最優(yōu)資源分配模式。但上述方法在處理海量云計算虛擬資源分配時無法達(dá)到預(yù)期效果,且對外部環(huán)境影響因素考慮較為單一,導(dǎo)致資源分配極易產(chǎn)生偏差。

為此,本文提出一種云計算虛擬資源差分進(jìn)化分配方法。構(gòu)建云計算虛擬資源分配模型,引入差分進(jìn)化算法進(jìn)行全局最優(yōu)搜索,并在仿真實驗中也進(jìn)一步驗證了方法的可行性,獲得科學(xué)合理的虛擬資源分配方案。

2 云計算虛擬資源分配模型

用戶向云服務(wù)中心遞交服務(wù)請求時,資源分配中心會把描述的服務(wù)請求變換成云任務(wù)需求[6-7],為資源任務(wù)類型的準(zhǔn)確分類,從分配能耗與時間兩方面入手,通過動態(tài)能量感知技術(shù)構(gòu)建云計算虛擬資源分配模型。

考慮動態(tài)能量損耗[8],資源分配問題被定義成:存在相同類型資源分配需求(涵蓋帶寬分配需求、可信度分配需求等)的n個不具備相互關(guān)聯(lián)的獨立資源A={a1,a2,…,an}和滿足上述資源分配需求對應(yīng)服務(wù)器內(nèi)m個分配資源B={b1,b2,…,bm}。虛擬資源分配任務(wù)要同時符合最短時間跨度和最小能耗總值條件,這樣能在提高資源分配速率的同時,減少資源分配運行成本。

在虛擬映射原則下,考慮服務(wù)器電路能耗,通過調(diào)節(jié)服務(wù)器電壓與分配頻率來降低全局能耗[9]。服務(wù)器電壓與分配頻率增大的情況下,能耗會慢慢降低。K={kj,1

全部資源分配最短時間跨度Tmin的運算解析式為

Tmin=Cj-Di

(1)

式中,Cj代表資源實現(xiàn)調(diào)度的總時長,Di代表實現(xiàn)資源分配的總時長。

資源分配的空閑分配時間Tfree的運算解析式為

Tfree=Tmin-Di

(2)

計算時,若以最短時間跨度Tmin實現(xiàn)服務(wù)器虛擬資源分配,則Tfree值等于0。將全部資源分配生成的能耗總值G表示為

(3)

式中,Gi代表分配資源時耗損的動態(tài)能量。

考慮到資源分配時間和資源分配能量具有一定的內(nèi)在關(guān)聯(lián),為了方便研究資源分配時序規(guī)律,引入能量消耗時間變換因子,把實現(xiàn)資源分配需要的能量值均變換為時間參數(shù)[10],將能量消耗時間變換因子定義為

c=[c1,c2,…ci]

(4)

式中,ci代表實現(xiàn)資源分配時能量消耗和時間之間的變換因子。

由此,將實現(xiàn)資源分配產(chǎn)生能量消耗變換的時間向量GAi與資源分配時間矩陣GAL分別定義成

GAi=ci×Gi

(5)

GAL=[GAL[i,j]]n×m

(6)

式中,GAL[i,j]代表實現(xiàn)資源分配需要的執(zhí)行時間。

云計算虛擬資源分配模型的關(guān)鍵是處理云計算資源分配過程中的工作負(fù)載問題。使用二元組H={A,B}描述云計算資源分配模型,并將資源分配模型表示成圖1。

圖1 云計算虛擬資源分配模型示意圖

3 云計算虛擬資源分配實現(xiàn)

差分進(jìn)化算法作為一種種群進(jìn)化優(yōu)化方法[11],具有穩(wěn)定性與實用性特點,涵蓋三個基礎(chǔ)步驟:變異操作、交叉操作與選擇操作,在諸多領(lǐng)域得到了大量應(yīng)用。本文將差分進(jìn)化算法引入云計算虛擬資源分配模型,運用其強(qiáng)大的搜索能力,找出最符合當(dāng)下環(huán)境的虛擬資源分配策略,完成資源合理調(diào)度。

(7)

使用式(7)的選擇操作判斷個體最優(yōu)解,利用變異概率自主調(diào)節(jié)完善差分進(jìn)化算法性能,運算步驟為:

第一,染色體編碼。融合云計算虛擬資源分配特征,運用資源-任務(wù)的間接編碼模式[14],用戶虛擬任務(wù)總值為染色體長度,基因代表虛擬任務(wù),基因位的位值表示虛擬任務(wù)被分配至對應(yīng)資源編碼。假設(shè)pi是任務(wù)編碼,uj是資源編碼,則相應(yīng)的染色體解碼為p1:{u1},p2:{u2},…,pn:{un}。由此看出,每條染色體均對應(yīng)一種資源分配方案。

第二,初始化最高迭代數(shù)量、迭代終止條件、種群規(guī)模等參數(shù),并設(shè)置云計算虛擬機(jī)適應(yīng)度函數(shù)[15]。倘若在第l臺虛擬機(jī)上分配了v個任務(wù),那么第l臺虛擬機(jī)實現(xiàn)任務(wù)分配的迭代周期為

(8)

第三,種群評估,推算全部個體適應(yīng)度,分析每個個體的優(yōu)劣水平,保存當(dāng)代種群的最優(yōu)個體。將虛擬資源集合的負(fù)載均值LB與負(fù)載均衡標(biāo)準(zhǔn)差LCT依次記作:

(9)

(10)

式中,o代表虛擬機(jī)個數(shù)。

將個體適應(yīng)度函數(shù)進(jìn)一步表示成

(11)

式中,Qb代表全部虛擬資源分配的迭代周期。

第四,評估是否滿足迭代終止條件,若不滿足則使用輪盤賭選擇策略挑選優(yōu)良個體,并把優(yōu)質(zhì)基因傳遞至下一代,采取精英保存措施[16],防止優(yōu)良個體在進(jìn)化過程中丟失。

第五,多點交叉操作當(dāng)前種群個體,更改基因排列模式,產(chǎn)生全新個體,保證種群多樣化。交叉操作計算過程為:

(12)

式中,rand[0,1]代表[0,1]區(qū)間內(nèi)挑選的隨機(jī)值,CR代表[0,1]區(qū)間中的常數(shù),命名為交叉因子,CR值越高,交叉概率越高,j＿rand代表在[0,1]區(qū)間內(nèi)隨機(jī)挑選的整數(shù)。

第六,隨機(jī)擇取若干個體,依照變異概率自主調(diào)節(jié)進(jìn)行變異操作。變異概率可自主調(diào)整臨界值,任意挑選個體基因?qū)嵤┬》秶儺悺?/p>

隨機(jī)迭代過程自主調(diào)節(jié)的變異概率Ro為

(13)

式中,g代表自主調(diào)節(jié)時間。

第七,評估種群狀態(tài),推算全部個體的適應(yīng)度值,找出最優(yōu)個體,如果新個體適應(yīng)度高于原始最優(yōu)個體適應(yīng)度,則用新個體替換舊個體。

第八,確認(rèn)是否滿足循環(huán)終止條件,若滿足就輸出最終結(jié)果,反之跳轉(zhuǎn)至第四步繼續(xù)計算,直至搜索到最優(yōu)云計算虛擬資源分配方法為止。

4 仿真實驗

為證明本文方法的實用性,對其進(jìn)行仿真實驗,把文獻(xiàn)[4]輪換策略法與文獻(xiàn)[5]競爭粒子群算法擬作對比目標(biāo),實驗所用數(shù)據(jù)來自data.gov數(shù)據(jù)庫(http:∥www.data.gov/),實驗仿真平臺為MATLAB 7.0。通過更改任務(wù)參數(shù)值檢驗不同計算任務(wù)數(shù)量下不同方法的性能,創(chuàng)建2個實驗?zāi)Ｊ?

1)使用Sphere測試函數(shù)分析方法的尋優(yōu)性能。

2)通過負(fù)載均衡、執(zhí)行能耗等指標(biāo)驗證三種方法在虛擬資源分配方面的可靠性。

4.1 資源分配方法尋優(yōu)測驗

Sphere測試函數(shù)下三種方法云計算虛擬資源分配尋優(yōu)運行結(jié)果如圖2所示。

圖2 三種方法尋優(yōu)收斂曲線圖

觀察圖2結(jié)果可知,本文方法僅需迭代35次即可完成尋優(yōu),輪換策略法和競爭粒子群算法分別在83、112次完成尋優(yōu)。由此證明,本文方法在迭代周期內(nèi)展現(xiàn)出了良好運算性能,目標(biāo)函數(shù)曲線下降速率快,尋優(yōu)正確率高,進(jìn)一步避免方法陷入局部最優(yōu),由此可以從側(cè)面反映出本文方法的云計算虛擬資源分配效率更高。

4.2 資源分配性能測驗

一個好的資源分配方法需要使用更少的服務(wù)器完成對應(yīng)的任務(wù)調(diào)度工作,節(jié)省云計算服務(wù)運行成本。設(shè)定某云計算平臺包含50臺物理服務(wù)器,需要創(chuàng)建的虛擬主機(jī)總數(shù)為120,驗證不同方法下服務(wù)器個數(shù)伴隨虛擬主機(jī)數(shù)量增多的變化情況,實驗結(jié)果如圖3所示。

圖3 服務(wù)器伴隨虛擬主機(jī)數(shù)量的變化趨勢

由圖3可以看出,伴隨需要創(chuàng)建的虛擬主機(jī)個數(shù)的增多,三種方法使用的服務(wù)器數(shù)量均呈現(xiàn)出上升趨勢,相較于輪換策略法與競爭粒子群算法,本文方法在同樣實驗環(huán)境下,需要投入使用的物理服務(wù)器數(shù)量最少,說明其能夠最大程度上節(jié)省投資開銷,降低資源分配成本。原因在于該方法充分考慮資源分配時間和資源分配能量具有一定的內(nèi)在關(guān)聯(lián),引入能量消耗時間變換因子,將實現(xiàn)資源分配需要的能量值均變換為時間參數(shù),降低能耗,使資源分配成本得到降低。

以負(fù)載均衡標(biāo)準(zhǔn)差作為衡量標(biāo)準(zhǔn),標(biāo)準(zhǔn)差越小,證明云計算虛擬資源分配處理能力越好,方法的靈活性與魯棒性越強(qiáng)。設(shè)定虛擬機(jī)為100臺,任務(wù)數(shù)以50個為基礎(chǔ)疊加,實驗對比結(jié)果如圖4所示。

圖4 三種方法資源分配負(fù)載均衡情況對比

由圖4可以看出,虛擬機(jī)數(shù)量一定時,本文方法在負(fù)載均衡方面得到較優(yōu)的運算結(jié)果。伴隨任務(wù)數(shù)量不斷上升,本文方法負(fù)載均衡標(biāo)準(zhǔn)差保持在10以內(nèi),輪換策略法與競爭粒子群算法的負(fù)載均衡標(biāo)準(zhǔn)差均高于本文方法。

設(shè)定待分配虛擬資源數(shù)量為700,在相同虛擬主機(jī)個數(shù)下,三種方法資源分配時間與能耗的實驗結(jié)果如圖5、6所示。

圖5 不同任務(wù)數(shù)量下資源分配時間對比

從圖5看出,計算資源不變的狀態(tài)下,任務(wù)數(shù)量較少時,三種方法資源分配耗時差距較小,但隨著任務(wù)個數(shù)的增多,資源分配復(fù)雜度逐步提升,兩個文獻(xiàn)方法需要消耗大量時間完成資源分配任務(wù),本文方法優(yōu)勢越發(fā)顯著,仍舊能以較短時間實現(xiàn)用戶預(yù)期服務(wù)請求。這是由于本文方法采用差分進(jìn)化算法中變異與選擇等操作,實現(xiàn)高精度全局搜索尋優(yōu),自適應(yīng)獲取最合理的資源分配策略,大幅縮減分配耗時。

從圖6看出,本文方法的資源分配能耗控制水平遠(yuǎn)遠(yuǎn)高于兩個文獻(xiàn)方法,相同虛擬主機(jī)下具備更少能耗,能耗增幅比較為平緩,擁有更好的節(jié)能性,可以最大限度延長云平臺數(shù)據(jù)中心服務(wù)器壽命。

圖6 不同任務(wù)數(shù)量下資源分配能耗對比

綜合實驗結(jié)果能得到以下結(jié)論:本文方法在任務(wù)數(shù)量龐大、復(fù)雜度高的環(huán)境下依舊具備極強(qiáng)的資源分配能力。

5 結(jié)論

為探究怎樣在確保計算性能的基礎(chǔ)上減少云計算數(shù)據(jù)中心能耗這一問題,提出一種云計算虛擬資源差分進(jìn)化分配方法。差分進(jìn)化算法具備優(yōu)秀的全局搜索能力,能很好地應(yīng)用于云計算虛擬資源分配中。使用動態(tài)能量感知技術(shù)創(chuàng)建云計算虛擬資源分配模型,確定虛擬資源類型,通過選擇、變異、交叉三種操作得到資源分配策略。在仿真實驗中,利用不同驗證指標(biāo)驗證了該方法的有效性。在今后工作中會深入考慮服務(wù)器開關(guān)機(jī)代價等更復(fù)雜的因素,提升方法適用性,為增強(qiáng)云計算服務(wù)水平提供參考借鑒。