龔炳江，馮謙謙，趙曉峰

(1.河北工程大學(xué) 信息與電氣工程學(xué)院，河北 邯鄲 056038；2.河北工程大學(xué) 管理與工商學(xué)院，河北 邯鄲 056038)

0 引 言

云數(shù)據(jù)中心的虛擬機(jī)資源異構(gòu)性和物理機(jī)規(guī)格的不一致性，導(dǎo)致了服務(wù)器內(nèi)部和云數(shù)據(jù)中心的資源負(fù)載不均衡[1]。因此，如何定義虛擬機(jī)和物理節(jié)點(diǎn)之間的映射關(guān)系對(duì)系統(tǒng)的性能產(chǎn)生重要的影響。一些學(xué)者采用傳統(tǒng)的啟發(fā)式算法或者改進(jìn)的啟發(fā)式算法來進(jìn)行全局化搜索，解決虛擬機(jī)的放置問題[2-4]。盡管傳統(tǒng)啟發(fā)式算法簡單易行，但是容易產(chǎn)生局部最優(yōu)解，無法獲得全局最優(yōu)解。文獻(xiàn)[5,6]采用蟻群算法和粒子群算法求解虛擬機(jī)部署問題具有較好的效果，但是仍存在收斂速度慢、容易陷入局部最優(yōu)等缺陷；文獻(xiàn)[7]采用基于虛擬機(jī)的編碼方式，存在編碼冗余等缺點(diǎn)，并沒有將遺傳算法的效率發(fā)揮到最大。本文在分組遺傳算法的基礎(chǔ)上，采用資源利用率多維標(biāo)準(zhǔn)差控制參量，設(shè)計(jì)適應(yīng)度函數(shù)引導(dǎo)搜索解空間。此外，采用輪盤賭方式選擇參與交叉過程的染色體，比較定義的基因評(píng)估參數(shù)值，確定較優(yōu)的基因進(jìn)行交叉，使得子代染色體能夠較大可能繼承父類染色體的優(yōu)秀基因。而變異采用隨機(jī)刪除較差基因來改變子代的染色體編碼，提高最優(yōu)解的收斂速度。通過實(shí)驗(yàn)分析，提出的虛擬放置算法能夠有效減少資源浪費(fèi)，提高數(shù)據(jù)中心的整體能效。

1 調(diào)度算法模型

1.1 多維資源模型

假設(shè)物理機(jī)集合P={p1,p2,…,pn}，數(shù)據(jù)中心的物理機(jī)總數(shù)為n，物理機(jī)提供的資源容量集合Qi={qi,1,qi,2,…,qi,d}(1≤i≤n)，其中qi,d表示物理機(jī)i能提供的d類型資源的容量(比如CPU、內(nèi)存、磁盤和帶寬的容量)；虛擬機(jī)集合V={v1,v2,…,vm}，需要放置的虛擬機(jī)總數(shù)為m，虛擬機(jī)請(qǐng)求的資源大小集合Ri={ri,1,rj,2,…,rj,d}(1≤j≤m)，其中rj,d表示虛擬機(jī)j所需求的d類型資源的大小。本節(jié)主要符號(hào)定義見表1。

表1 主要的符號(hào)定義和含義

虛擬機(jī)放置算法為找到一個(gè)激活較少的物理機(jī)，以獲得盡量大的資源利用率的虛擬機(jī)到物理機(jī)的映射方案?？梢宰鋈缦旅枋?/p>

(1)

(2)

(3)

其中，目標(biāo)函數(shù)式(2)中數(shù)據(jù)中心物理機(jī)的所有資源平均利用率u，通過式(7)～式(9)推導(dǎo)而來。第一條約束條件表示物理機(jī)分配的資源不超過其容量限制，第二條約束條件表示每個(gè)虛擬機(jī)只能放置到唯一的物理機(jī)上，第三條約束條件表示pi，vi,j的取值范圍為0或1。

1.2 服務(wù)器能耗模型

假設(shè)數(shù)據(jù)中心有n臺(tái)服務(wù)器組建而成，服務(wù)器i上的能耗為Ei。服務(wù)器作為數(shù)據(jù)中心能耗的主要來源，服務(wù)器的負(fù)載受到其所負(fù)載的虛擬機(jī)數(shù)目和虛擬機(jī)內(nèi)負(fù)載的影響，所以虛擬機(jī)數(shù)量越多、負(fù)載越大，則服務(wù)器的負(fù)載越大。根據(jù)文獻(xiàn)[8]的研究，物理服務(wù)器的功率能耗Pmax與服務(wù)器利用率u呈現(xiàn)一種線性關(guān)系，表示為

P(u)=cPmax+(1-c)Pmax

(4)

式中：Pmax是服務(wù)器滿負(fù)載時(shí)的最大功耗，c是服務(wù)器空載與滿載時(shí)的功耗比，一般Pmax取值為175w，c的取值為0.7。則在特定時(shí)間T內(nèi)，服務(wù)器i的功耗可以表示為

(5)

數(shù)據(jù)中心的能耗E，可以表示為

(6)

1.3 負(fù)載均衡度量指標(biāo)

物理機(jī)內(nèi)部資源的不充分利用和物理機(jī)配置的差異性，導(dǎo)致物理機(jī)內(nèi)部的負(fù)載不均衡和不同物理機(jī)間的負(fù)載不均衡。這種負(fù)載分配不均的情況直接影響云數(shù)據(jù)中心整體能效，需要合理的虛擬機(jī)部署策略和負(fù)載均衡度量指標(biāo)保持物理機(jī)的負(fù)載均衡。為了得到度量指標(biāo)，考慮以下參數(shù)。

物理機(jī)i上l類型資源利用率

(7)

物理機(jī)i上資源平均資源利用率

(8)

數(shù)據(jù)中心資源的綜合利用率

(9)

物理機(jī)i的資源負(fù)載不均衡度

(10)

云數(shù)據(jù)中心的整體負(fù)載不均衡度

(11)

Ni作為單個(gè)物理機(jī)內(nèi)部資源負(fù)載均衡度量的指標(biāo)，N作為數(shù)據(jù)中心的物理機(jī)負(fù)載均衡度量指標(biāo)?？梢?，負(fù)載不均衡度的值越小，表示系統(tǒng)負(fù)載越均衡，系統(tǒng)的性能越好。

2 算法實(shí)現(xiàn)

2.1 染色體編碼

裝箱問題已經(jīng)提出3種表示方式：基于箱子的表示，基于物品的表示，基于分組的表示[9]。前面兩種編碼方式，是面向單個(gè)項(xiàng)的，具有高度冗余和重復(fù)編碼等缺點(diǎn)，不適合這類問題的費(fèi)用函數(shù)優(yōu)化。本文采用基于分組的表示方式，如圖1所示，染色體編碼BCDA(B={3,6}，C={5}，D={4,2}，A={1})，表示6臺(tái)虛擬機(jī)映射到4臺(tái)物理機(jī)上。這種的表示方式的特別之處是遺傳算子對(duì)分組部分進(jìn)行操作，相較于前兩種表示方式，不易造成染色體過長而影響計(jì)算的效率。

圖1 染色體編碼

2.2 選 擇

2.3 交 叉

交叉算子盡量使得后代繼承父類染色體中較優(yōu)秀的基因，以此得到更優(yōu)秀的后代。將單個(gè)物理機(jī)的資源利用率和資源負(fù)載均衡度的比值作為基因的評(píng)估參數(shù)gi=ui/N。評(píng)估參數(shù)值的大小取決于物理機(jī)上資源的利用率和資源負(fù)載情況，資源的利用率越高以及資源負(fù)載越均衡，評(píng)估參數(shù)gi的值越大。根據(jù)評(píng)估參數(shù)gi在父類的整個(gè)評(píng)估參數(shù)和中所占的比重，選擇參與交叉的基因。這樣，在交叉過程中子代繼承到優(yōu)秀基因即虛擬機(jī)放置合理的物理機(jī)的可能性越大，有效避免因?yàn)殡S機(jī)選擇遺傳基因而使得算法效率過低的情況。

假設(shè)參與交叉的兩個(gè)父類染色體分別為X、Y，從父類X中選擇較優(yōu)秀的基因即評(píng)估參數(shù)較高的基因插入到父類Y中的隨機(jī)交叉點(diǎn)中，而產(chǎn)生新的子代染色體。在交叉的過程中，可能出現(xiàn)在不同的物理機(jī)中出現(xiàn)重復(fù)虛擬機(jī)的情況，這時(shí)需要?jiǎng)h除出現(xiàn)重復(fù)虛擬機(jī)的物理機(jī)。而由于刪除操作所產(chǎn)生的孤立的虛擬機(jī)采用FFD算法回填。具體的交叉過程，如圖2所示。

圖2 交叉過程

2.4 變 異

變異操作是遺傳算法中不可或缺的一部分，有利于增加種群多樣性。算法的期望目標(biāo)是激活較少的物理機(jī)獲得較大的資源利用率進(jìn)而降低能耗。因此，變異算子采用消除一個(gè)已使用的物理機(jī)及變異后沒有依賴的虛擬機(jī)即解中缺少某些虛擬機(jī)需要采用FFD算法回填的方式。選擇基因評(píng)估參數(shù)gi作為衡量被消除物理機(jī)的標(biāo)準(zhǔn)，基因評(píng)估參數(shù)gi越大表示該物理機(jī)中虛擬機(jī)放置越合理，其被刪除的可能性越小，使變異向著較優(yōu)的方向發(fā)展。以此增強(qiáng)算法局部的隨機(jī)搜索能力，逼近最優(yōu)解。

2.5 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的選取直接影響到算法的收斂速度和能否找到最優(yōu)解。適應(yīng)度函數(shù)值是算法衡量種群中個(gè)體染色體搜索的標(biāo)準(zhǔn)，也就是算法迭代過程中通過其對(duì)個(gè)體染色體優(yōu)劣程度進(jìn)行評(píng)價(jià)。所以，當(dāng)適應(yīng)度函數(shù)值越大，個(gè)體染色體基因越優(yōu)秀被遺傳的可能性越大，最終得到的解也最好。為了達(dá)到激活最少的物理機(jī)以獲得最大的資源利用率的目標(biāo)，適應(yīng)度函數(shù)的設(shè)計(jì)綜合考慮激活物理機(jī)的數(shù)目和資源的利用情況。因此采用式(12)作為算法的適應(yīng)度函數(shù)

(12)

式中：Z為個(gè)體中激活的物理機(jī)的總數(shù)目，U為個(gè)體中物理機(jī)的平均資源利用率，N為個(gè)體中物理機(jī)的資源負(fù)載不均衡度。

3 仿真實(shí)驗(yàn)結(jié)果及分析

本文算法采用Cloudsim云仿真平臺(tái)[10]作為實(shí)驗(yàn)仿真工具，對(duì)其進(jìn)行了擴(kuò)展，改寫了Host類、VMAllocationPolicy類和Datacenter類等相關(guān)類，實(shí)現(xiàn)虛擬機(jī)放置算法。

3.1 實(shí)驗(yàn)仿真環(huán)境

仿真了500臺(tái)物理機(jī)構(gòu)成了數(shù)據(jù)中心，為了方便算法性能的測(cè)試，設(shè)置了10 000 MIPS的CPU、50 GB的內(nèi)存、1 TB的存儲(chǔ)和10 G的帶寬。具體設(shè)置的虛擬機(jī)參數(shù)，見表2。

表2 虛擬機(jī)參數(shù)信息

為分析算法在不同的虛擬機(jī)請(qǐng)求規(guī)模時(shí)的性能，同時(shí)將工作負(fù)載規(guī)模分別為100、200、300、400、500個(gè)虛擬機(jī)實(shí)例運(yùn)行10次，將10次實(shí)驗(yàn)數(shù)據(jù)的平均值作為實(shí)驗(yàn)評(píng)估的最終數(shù)據(jù)。

3.2 仿真實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文所提出的虛擬機(jī)放置算法(IGGA)的性能和有效性，與基于降序適應(yīng)算法(FFD)的虛擬機(jī)放置策略和基于傳統(tǒng)的遺傳算法(GA)的虛擬機(jī)放置策略進(jìn)行了比較。

如圖3和圖4所示，在同一虛擬機(jī)請(qǐng)求規(guī)模下，IGGA算法在物理機(jī)激活數(shù)目和資源的綜合利用率方面都明顯優(yōu)于FFD算法和GA算法。而且激活物理機(jī)的數(shù)目與虛擬機(jī)請(qǐng)求規(guī)模有著密切聯(lián)系。隨著虛擬機(jī)請(qǐng)求規(guī)模的增大，激活的物理機(jī)數(shù)目也隨之增加。同時(shí)，虛擬機(jī)的請(qǐng)求規(guī)模也影響著資源的綜合利用率，資源的綜合利用率在某一區(qū)間內(nèi)波動(dòng)。

圖3 激活物理機(jī)數(shù)目比較

圖4 資源綜合利用率比較

如圖5所示，IGGA算法在系統(tǒng)能耗方面優(yōu)于FFD算法和GA算法，其啟動(dòng)的物理機(jī)數(shù)目最少，資源綜合利用率最高，所需系統(tǒng)能耗也最小。因而，系統(tǒng)啟動(dòng)物理機(jī)數(shù)目越少，資源利用率越高，進(jìn)而可以降低系統(tǒng)的能耗。

圖5 系統(tǒng)能耗比較

如圖6所示，反映了3種算法在不同的虛擬機(jī)規(guī)模下的負(fù)載不均衡度波動(dòng)情況。在同一虛擬機(jī)的請(qǐng)求規(guī)模下，IGGA算法的負(fù)載不均衡度小于FFD算法和GA算法，表明改進(jìn)的算法在負(fù)載均衡方面的性能優(yōu)于它們。FFD算法性能在負(fù)載均衡和能耗方面最差，該算法較大程度的減少激活物理機(jī)的數(shù)目，使個(gè)別主機(jī)的負(fù)載過高，負(fù)載不均衡造成了資源浪費(fèi)和能源損耗。傳統(tǒng)的GA算法具有高度冗余和重復(fù)編碼的缺點(diǎn)，造成算法性能并不理想。本文改進(jìn)的算法對(duì)各方面進(jìn)行了的優(yōu)化，在能耗和負(fù)載均衡方面具有更好的性能，能夠提高云數(shù)據(jù)中心的整體能效。

圖6 負(fù)載不均衡度比較

4 結(jié)束語

實(shí)現(xiàn)低能耗和負(fù)載均衡的云數(shù)據(jù)中心至關(guān)重要，如何提高數(shù)據(jù)中心的整體能效是值得人們關(guān)注的問題。本文通過建立多維資源模型、服務(wù)器能耗模型和負(fù)載均衡度量指標(biāo)并結(jié)合傳統(tǒng)啟發(fā)式算法對(duì)分組遺傳算法選擇、交叉、變異等方面進(jìn)行了更好的優(yōu)化，提出了一種面向云數(shù)據(jù)中心能效優(yōu)化虛擬機(jī)放置算法。仿真實(shí)驗(yàn)表明，改進(jìn)的算法能夠有效降低啟用物理機(jī)的數(shù)目，最小化數(shù)據(jù)中心的能耗，提高了數(shù)據(jù)中心整體能效。

[1]Anam Sultana Moheet Khan,Prajakta P Chapke.Cloud computing:Comparison with grid computing,cloud service mo-dels,architecture,components,and virtualization[J].International Journal of Advanced Research in Computer Science and Software Engineering,2015,5(1):1087-1093.

[2]Gao Yongqiang,Guan Haibing,Qi Zhengwei,et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud conmputing[J].Journal of Computer and System Sciences,2013,79(8):1230-1242.

[3]Beloglazoy A,Abawajy J,Buyya R.Energy efficient resource allocation heuristics for efficient management of data centers for cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[4]Xu Bo,Peng Zhiping,Xiao Fangxiong,et al.Dynamic deployment of virtual machine in cloud computing using multi-objective optimization[J].Soft Computing,2015,19(8):2265-2273.

[5]ZHAO Jun,MA Zhong,LIU Chi,et al.Multi-objective ant colony optimization algorithm for virtual machine placement[J].Journal of Xidian University(Natural Science),2015,42(3):191-197(in Chinese).[趙君,馬中,劉馳,等.一種修改的多目標(biāo)蟻群系統(tǒng)虛擬機(jī)放置算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,42(3):191-197.]

[6]YANG Jing,ZHANG Hongjun,ZHAO Shuining,et al.Virtual machine deployment strategy based on particle swarm optimization algorithm[J].Journal of Computer Applications,2016,36(1):117-121(in Chinese).[楊靖,張宏軍,趙水寧,等.基于粒子群算法的虛擬機(jī)部署策略[J].計(jì)算機(jī)應(yīng)用,2016,36(1):117-121.]

[7]HUANG Zhaonian,LI Haishan,ZHAO Jun.Virtual machine placement algorithm based on improved genetic algorithm[J].Scientific Journal of Computer Science,2015,42(11A):406-407(in Chinese).[黃兆年,李海山,趙君.基于雙適應(yīng)度遺傳算法的虛擬機(jī)放置的研究[J].計(jì)算機(jī)科學(xué),2015,42(11A):406-407.]

[8]Xiong F,Zhou C.Virtual machine selection and placement for dynamic consolidation in cloud computing environment[J].Frontiers of Computer Science,2015,9(2):322-330.

[9]WANG Yongzhen,CHEN Yan,YU Yingying.Improved grouping genetic algorithm for solving multiple traveling salesman problem[J].Journal of Electronics & Information Technology,2017,39(1):198-205(in Chinese).[王勇臻,陳燕,于瑩瑩.求解多旅行商問題的改進(jìn)分組遺傳算法[J].電子與信息學(xué)報(bào),2017,39(1):198-205.]

[10]WEI Liang,HUANG Tao,CHEN Jianya,et al.Workload prediction-based algorithm for consolidation of virtual machines[J].Journal of Electronics & Information Technology,2013,35(2):1271-1276(in Chinese).[魏亮,黃韜,陳建亞,等.基于工作負(fù)載預(yù)測(cè)的虛擬機(jī)整合算法[J].電子與信息學(xué)報(bào),2013,35(2):1271-1276.]