高 楊,馬賀男,劉曉菲

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

1 引言

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

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

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

2 云計(jì)算虛擬資源分配模型

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

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

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

全部資源分配最短時(shí)間跨度Tmin的運(yùn)算解析式為

Tmin=Cj-Di

(1)

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

資源分配的空閑分配時(shí)間Tfree的運(yùn)算解析式為

Tfree=Tmin-Di

(2)

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

(3)

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

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

c=[c1,c2,…ci]

(4)

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

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

GAi=ci×Gi

(5)

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

(6)

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

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

圖1 云計(jì)算虛擬資源分配模型示意圖

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

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

(7)

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

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

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

(8)

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

(9)

(10)

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

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

(11)

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

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

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

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

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

(13)

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4.2 資源分配性能測(cè)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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