面向云數據中心能效優化的虛擬機放置算法

2018-03-16 06:35:22龔炳江馮謙謙趙曉峰

計算機工程與設計 2018年2期

龔炳江，馮謙謙，趙曉峰

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

0 引言

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

1 調度算法模型

1.1 多維資源模型

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

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

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

(1)

(2)

(3)

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

1.2 服務器能耗模型

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

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

(4)

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

(5)

數據中心的能耗E，可以表示為

(6)

1.3 負載均衡度量指標

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

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

(7)

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

(8)

數據中心資源的綜合利用率

(9)

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

(10)

云數據中心的整體負載不均衡度

(11)

Ni作為單個物理機內部資源負載均衡度量的指標，N作為數據中心的物理機負載均衡度量指標。可見，負載不均衡度的值越小，表示系統負載越均衡，系統的性能越好。

2 算法實現

2.1 染色體編碼

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

圖1 染色體編碼

2.2 選擇

2.3 交叉

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

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

圖2 交叉過程

2.4 變異

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

2.5 適應度函數

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

(12)

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

3 仿真實驗結果及分析

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

3.1 實驗仿真環境

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

表2 虛擬機參數信息

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

3.2 仿真實驗結果與分析

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

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

圖3 激活物理機數目比較

圖4 資源綜合利用率比較

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

圖5 系統能耗比較

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

圖6 負載不均衡度比較

4 結束語

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

[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).[趙君,馬中,劉馳,等.一種修改的多目標蟻群系統虛擬機放置算法[J].西安電子科技大學學報(自然科學版),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].計算機應用,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).[黃兆年,李海山,趙君.基于雙適應度遺傳算法的虛擬機放置的研究[J].計算機科學,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].電子與信息學報,2017,39(1):198-205.]