面向云數(shù)據(jù)中心能效優(yōu)化的虛擬機放置算法

龔炳江，馮謙謙，趙曉峰

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

0 引 言

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

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

1.1 多維資源模型

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

表1 主要的符號定義和含義

虛擬機放置算法為找到一個激活較少的物理機，以獲得盡量大的資源利用率的虛擬機到物理機的映射方案。可以做如下描述

(1)

(2)

(3)

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

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

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

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

(4)

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

(5)

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

(6)

1.3 負載均衡度量指標

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

物理機i上l類型資源利用率

(7)

物理機i上資源平均資源利用率

(8)

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

(9)

物理機i的資源負載不均衡度

(10)

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

(11)

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

2 算法實現(xiàn)

2.1 染色體編碼

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

圖1 染色體編碼

2.2 選 擇

2.3 交 叉

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

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

圖2 交叉過程

2.4 變 異

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

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

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

(12)

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

3 仿真實驗結(jié)果及分析

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

3.1 實驗仿真環(huán)境

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

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

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

3.2 仿真實驗結(jié)果與分析

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

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

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

圖4 資源綜合利用率比較

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

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

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

圖6 負載不均衡度比較

4 結(jié)束語

實現(xiàn)低能耗和負載均衡的云數(shù)據(jù)中心至關(guān)重要，如何提高數(shù)據(jù)中心的整體能效是值得人們關(guān)注的問題。本文通過建立多維資源模型、服務(wù)器能耗模型和負載均衡度量指標并結(jié)合傳統(tǒng)啟發(fā)式算法對分組遺傳算法選擇、交叉、變異等方面進行了更好的優(yōu)化，提出了一種面向云數(shù)據(jù)中心能效優(yōu)化虛擬機放置算法。仿真實驗表明，改進的算法能夠有效降低啟用物理機的數(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).[趙君,馬中,劉馳,等.一種修改的多目標蟻群系統(tǒng)虛擬機放置算法[J].西安電子科技大學(xué)學(xué)報(自然科學(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].計算機應(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].計算機科學(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].電子與信息學(xué)報,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).[魏亮,黃韜,陳建亞,等.基于工作負載預(yù)測的虛擬機整合算法[J].電子與信息學(xué)報,2013,35(2):1271-1276.]