基于家族遺傳算法的虛擬機放置策略

周 震，王 輝，李俊峰

(1.洛陽師范學院 信息技術學院，河南 洛陽 471934；2.河南廣播電視大學 信息技術中心，河南 鄭州 450001；3.中電科信息產業有限公司 安防事業部，河南 鄭州 450001)

0 引 言

綠色云數據中心的構造是近年來政府與云服務提供商越來關注的問題，它們通過虛擬機遷移策略使云平臺中的所有物理資源高效的利用、負載均衡和降低能量消耗[1-3]。虛擬機放置是虛擬機遷移的一個重要步驟[4-7]，云數據中心模擬器Cloudsim工具包中把它稱為多目標優化問題或者裝箱問題，該過程也有很多智能算法進行優化[8-10]。

本文著重考慮采用遺傳算法的方式來優化虛擬機放置過程。普通的遺傳算法由于早熟問題的出現，會使多目標優化存在局部最優解；由于收斂速度慢，普通遺傳算法在尋找最優解的過程中需要消耗大量的時間在各代個體的進化。本文提出的基于家族遺傳算法的虛擬機放置方法FGA-VMP(family genetic algorithm based virtual machine placement)克服了上述早熟和收斂速度慢的問題。在虛擬機放置優化過程中涉及的物理資源描述的維度方面，FGA-VMP考慮了物理主機的處理器、內存大小、磁盤大小和網絡帶寬等多個因素。

仿真結果表明，FGA-VMP優化策略形成新的虛擬機遷移模型之后可以更好節省云數據中心的能量消耗，提高物理資源利用效率。

1 虛擬機放置優化算法的相關工作

虛擬機放置是一種多目標優化問題。Cloudsim開發工具中使用了遞減經典裝箱問題(best-fit-decreasing bin packing problem，BPP)來完成虛擬機的放置過程[4]。虛擬機放置中近年來不同的文獻主要涉及到兩個方面的研究進展：能量消耗模型的變化和智能算法的改進。

在能量消耗模型研究方面，早期的文獻在設計云數據中心物理主機的能量消耗模型時考慮的物理資源維度比較單一[11]；后續考慮問題的維度擴展到了多維；

智能算法的改進方面，近年來提出了大量的新型智能算法進行虛擬機放置階段的優化，例如有蟻群優化算法、穩定匹配[12]等的虛擬機放置策略。大部分優化策略的目的是在云數據中心的總體能量消耗、虛擬機遷移次數、SLA違規率等目標指標上取平衡。

由于目前以Anton Beloglazov博士等為團隊開發的Cloudsim項目處于世界領先地位，所以本文的家族遺傳算法的虛擬機放置策略FGA-VMP依托了Cloudsim云平臺，FGA-VMP是一種既考慮了硬件因素，也考慮了軟件因素的虛擬機放置策略，以充分提高資源使用率為目標函數。FGA-VMP與普通的遺傳算法優化的虛擬機放置策略的優點是克服了早熟問題和收斂速度慢的問題。在普通遺傳算法中，大部分算法是以云數據中心的能量消耗為目標函數，還有少量策略是以降低SLA違規率為目標函數，它們與FGA-VMP區別在于目標函數不同。

2 FGA-VMP工作場景與建模

2.1 FGA-VMP工作場景

圖1顯示了FGA-VMP虛擬機放置策略的工作場景，這是一個典型的云客戶端對云數據中心的服務請求場景。由于FGA-VMP依托了Cloudsim各個運行模塊，在Cloudsim中主要由3個模塊組成：全局代理Global Broker、本地代理Local Broker、虛擬機管理器Virtual Machine Manager。

在Cloudsim中每個物理主機上都運行有一個本地代理Local Broker，FGA-VMP優化策略的實現主要在此模塊中完成，這個工作場景在大部分的文獻都有描述[4]。

圖1 FGA-VMP虛擬機放置策略的工作場景

2.2 FGA-VMP虛擬機放置建模

假設有n個虛擬機的集合{vi,i=1,…,n}在虛擬機放置階段要重新分配到云數據中心的m個物理主機{pj,j=1,…,m}上運行，vi表示云數據中心在虛擬機遷移的前兩個階段已經選擇好的大量侯選遷移虛擬機，pj表示云數據中心的大量物理主機。給虛擬機放置問題定義一個單一的決策變量yij。如果vi被重新放置到pj,則yij=1，否則yij=0。云數據中心的所有物理主機和所有的虛擬機分別用P和V來表示，根據這種定義，每個物理主機可以通過下面的向量來表示

pj=(idj,cpuj,memj,bwj)

(1)

idj表示了物理主機的標識符，cpuj表示了物理主機的處理器大小，memj表示了物理主機的可用內存大小，bwj表示了物理主機所擁有的網絡帶寬大小，每個虛擬機也可以通過下面的向量來表示

vi=(idi,cpui,memi,bwi)

(2)

idi表示了虛擬機的標識符，cpui表示了虛擬機的表示了對處理器的需求能力，memi表示了虛擬機對內存的需求能力，bwi表示了虛擬機對網絡帶寬的需求能力。

虛擬機放置問題可以通過下面的模型進行表示：發現一個最優的虛擬機到物理主機的映射，大量的虛擬機到一個物理主機的映射，在這種最優映射條件下滿足物理主機的資源利用效率是最高。根據上面的這種描述，虛擬機放置的目標是最大程度提高物理資源的利用效率，這個目標可以分解成3個子目標

(3)

包括下面這些約束條件

(4)

這些約束條件可以保證一個虛擬機只被重新放置到一個物理主機之上，一個物理主機可以容納多個虛擬機。還可以保證每個主機都足夠的物理資源能力來承擔這些虛擬機的需求。同時定義每個物理主機的各個維度的資源的使用邊界，包括上邊界和下邊界。第j個物理主機在被分配了第i個虛擬機vi之后,它的物理資源的利用效率可以描述如下

(5)

那么整個物理主機的資源使用效率表示如下

(6)

2.3 FGA-VMP的工作流程

FGA-VMP依托于Cloudsim，前面提到Cloudsim中虛擬機遷移過程包括3個步驟：物理主機狀態檢測、虛擬機選擇、虛擬機放置。針對上述思路，本文的FGA-VMP工作流程具體包括下面4個步驟：

步驟1 基于魯棒局部回歸LRR方法完成物理主機狀態檢測，當然這個是Cloudsim中默認的方式，形成侯選遷移物理主機列表MigratedHostList；

步驟2 針對侯選遷移物理主機列表上的虛擬機，基于最小遷移時間選擇MMT算法完成虛擬機選擇[4]，這也是Cloudsim中默認的選擇優化方法，形成侯選遷移虛擬機列表VmsToMigrateList；

步驟3 基于FGA-VMP方法完成虛擬機重新放置；

步驟4 重復上述步驟1～步驟3；

圖2顯示了FGA-VMP虛擬機放置策略在整個虛擬機遷移過程中的工作流程。本文的最小化遷移時間及最大化資源使用效率兩個不同目標是不會互相沖突的，因為最小化遷移時間是一種虛擬機選擇而不是放置策略，它的功能是從物理主機MigratedHostList中選擇出即將遷移的虛擬機，輸出為侯選遷移虛擬機列表VmsToMigrateList，是第二個步驟；在接下來第三個步驟中再把VmsToMigrateList作為輸入重新放置到其它正常的物理主機之上，此時再考慮最大化資源使用效率作為目標函數，這2個步驟是獨立的過程。

圖2 FGA-VMP策略運用到虛擬機遷移過程

3 FGA-VMP的虛擬機放置過程實現

3.1 FGA-VMP實現的功能模塊

FGA-VMP虛擬機放置策略的體系結構如圖3所示：家族遺傳算法模塊被集成了Cloudsim項目的模塊中。在Cloudsim開發模塊中有由物理主機組成的數據中心，每個物理主機有一個或者多個處理單元(processing elements，PE)，在這些物理主機中，有大量的虛擬機正在運行。每個虛擬機上層有一個或者多個朵云Cloudlets在運行。在Cloudsim中，云客戶端直接被朵云的形式來表示，每個朵云有不同的需求。每個朵云的處理需求通過每秒百萬條指令(million instructions per second，MIPS)來表示。在FGA-VMP中，家族遺傳算法模塊來處理大量虛擬機到物理主機的映射，也即虛擬機放置操作。

圖3 FGA-VMP虛擬機放置策略的實現模塊

家族遺傳算法模塊把整個虛擬機放置過程劃分為多個不同的家族過程，使得這些放置過程可以并行的處理。FGA-VMP試圖克服普通遺傳算法的一些缺點，在變異操作過程中可以避免早熟現象，所以FGA-VMP采用一個自調節的變異算子(mutation operator)來避免早熟問題。一般來說，在普通遺傳算法中變異率(mutation probability)也就是變異的概率是靜態的，這個變異率在普通遺傳算法開始的步驟中已經定義好,在整個算法過程中固定不變，大部分普通遺傳算法設置為80%。如果把變異率設置為變量，從而可以提出改進的遺傳算法。本文FGA-VMP在這里也把變異率設置為動態的，它的變化依賴于一個參數，稱為種群差異(population differentia，PD)。

種群差異是一個表示了不同的個體之間和種群的差異的比率。種群差異PD這個參數體現了變異率，變異率這個參數的自調整的使用可以保證沒有早熟現象的出現。在FGA-VMP中，兩個不同的個體A和個體B的差異程度通過d(A,B)來表示

(7)

l表示了遺傳算法中染色體的長度。

有了這個定義，每個種群中的個體在剩下的整個種群中的差異程度PD可以定義為

(8)

式中：N表示種群的規模。

3.2 FGA-VMP的實現算法

下面是FGA-VMP家族遺傳算法的虛擬機放置過程的偽代碼，該代碼通過少量修改即可利用Java語言來實現，如下Algorithm 1：

Algorithm 1：OutlineoftheFamilyGenealgorithm

Input：ListsofhostsandVMs

Output：VMplacementdecision(true/false)

(1)InitializethelistofhostsandVMs.

(2)InitializethevaluesofparametersofGA.

(3)Initializethenumberoffamiliestobeconstructed.

(4)Randomlyinitializethepopulation.

(5)Computethefitnessvaluesofeachchromosomeinthepopulation.

(6)Calculatethepopulationdifferentia.

(7)Performcrossoverandmutation.

(8)Selectthefamilyheadsasthebestindividualsfromthecurrentpopulation.

(9)forallFamily∈Populationdo

(10)repeat

(11)Performmutationonthefamilyheadandinsertmutatedchromosomeintofamily.

(12)Computethefitnessvalueofthechromosomeobtainedaftermutation.

(13)iffitnessofthemutatedchromosomeisgreaterthen

(14)addthemutatedchromosometothepopulation.

(15)Setflagastrue

(16)endif

(17)untilfamilysizek

(18)repeatPerformcrossoverandmutationonthecurrentfamilytogetthenextgenerationofthecurrentfamily.

(19)until‘k’times

(20)ifflag=trueelse‘w’times

(21)ifflag=false

(22)Selectthefittestindividualfromthepopulationtogetthebestsolution.

(23)endfor

(24)Returnflag

家族遺傳算法的基本思想是把整個種群劃分為多個家族，在普通遺傳算法中采用的是一整個種群,把這些家族的進化操作并行處理，這樣可以極大提高普通遺傳算法的速度。

在家族中往往通過相鄰區域來進行構建。在FGA-VMP中的虛擬機放置過程中并沒有定義這種相鄰區域，為了構建家族，采用了動態的種群差異PD變量變異辦法，見Algorithm 1中的代碼(6)～(12)行。在結果染色體中，如果有變化，盡管互相之間只有輕微的變化就將其放置到相同的家族之中。在這種情況下，通過破壞那些對家族沒有好處的進化個體優勢的家族信息，整個遺傳算法的處理時間可以得到很好的降低。

每個家族信息通過k次處理，如果一直沒有遇到更加優質的個體，我們將破壞家族信息，換成下一個家族，見Algorithm 1中的代碼(13)～(18)行。在當前的家族信息處理過程中，如果至少產生了一個比較好的個體信息，家族算法將繼續處理該家族信息，完成w次迭代處理，這里的參數k和參數w在系統測試過程中都可以進行設置。

對于種群中的每個個體，FGA-VMP中通過適應度fitness函數來評價個體的質量，在普通遺傳算法中，適應度函數通過算法所追求的目標函數來產生，在FGA-VMP中，我們所考慮的目標函數是整個云數據中心的物理資源的利用效率。下面的算法 Algorithm 2詳細表示了每個遺傳個體計算適應度函數的方法，也是偽代碼的形式。

Algorithm 2：Calculationofthefitnessvalueofeachchromosome

Input：Chromosome

Output：Fitnessofthechromosome

(1)forallpJ∈Pdo

(2)Initializeutilizationvalues

(3)forallVI∈Vdo

(4)ifVMisassignedtocurrenthostthen

(6)endif

(7)endfor

(8)endfor

算法Algorithm 3的偽代碼描述了家族基因的方式如何來完成虛擬機放置這種多目標優化問題。它必須保證所有的染色體滿足約束條件，為了保證這個條件，FGA-VMP設計了新的獨立函數來處理每個遺傳個體是如何滿足這種約束條件。如果發現遺傳個體是不可行的，該函數能將其轉移到個體是可行的狀態之下。

Algorithm 3：Checkthefeasibilityofanindividual

Input：Chromosome

Output：FeasibleSolution

(1)Initializelistoffreehoststocontainallhosts

(2)InitializethecapacitiesofProcessingElements

(3)InitializethenumberofProcessingElements

(4)forallVI∈Vdo

(5)Removefromfreehostwhichthehostassignedinchromosome.

(6)endfor

(7)forallPJ∈Pdo

(8)forallVI∈Vdo

(9)ifvIisassignedtopjthen

(11)Updatetheremainingcapacityofthehost

(12)endif

(13)ifthehostisover-utilizedthen

(14)Assignanynon-freehostthatcanaccepttheVM.

(15)ifnoallocatedhostscanaccepttheVMthen

(16)Assignasuitablehostfromthefreehosts.

(17)Updatethecapacitiesoftheassignedhost.

(18)endif

(19)endif

(20)endfor

(21)endfor

(22)Updatethechromosomewiththenewassignments.

(23)returnUpdatedchromosome

4 實驗與性能分析

4.1 測試環境

進行FGA-VMP實驗分析，必須構造云數據中心的虛擬機遷移場景，本文參考了Cloudsim3.0工具包，同時依據圖1中的運行場景，實現基于Java語言的局部代理。Cloudsim3.0工具包自帶了5種能量感知的虛擬機分配策略[4]，本節中把FGA-VMP各個性能指標的實驗結果與它們進行比較。表1為測試的硬件環境：表2為運行時間與虛擬機個數。虛擬機類型見表3。

表1 FGA-VMP的硬件測試配置

表2 一周內不同的虛擬機請求個數

表3 虛擬機類型配置

4.2 測試結果與性能分析

(1)負載均衡結果分析

圖4顯示了通過Cloudsim工具包里的默認虛擬機分配策略來完成虛擬機放置的情況。圖5顯示了通過FGA-VMP策略優化后的虛擬機的放置情況。

圖4 Cloudsim工具的虛擬機分配優化之前的效果

圖5 FGA-VMP虛擬機放置優化之后的效果

從實驗結果可以看出，當云平臺只有10個物理主機在運行的時候，經過本文的策略優化在虛擬機放置后，活動物理主機的數量相對減少， 虛擬機被均衡地放置到各個物理主機之上，該結果初步表明FGA-VMP策略使得虛擬機的分配使用了最少數量的物理主機，同時滿足了云平臺的虛擬機的請求。

(2)總體能量消耗分析

利用FGA-VMP虛擬機放置算法之后，當云平臺的虛擬機的個數從100到600個請求之后，運行一天24小時，周一到周五取平均值，各個策略的總體能量消耗見表4。從表4可以看出，有了虛擬機放置FGA-VMP優化后，比Cloudsim中已有的策略在總體能量消耗上要節約25%到30%，能量消耗基本呈線性變化，整體趨勢是FGA-VMP策略最節省云數據中心的能量消耗。分析原因是雖然云數據中心的整體物理主機個數為800個，但是隨著虛擬機個數的變化，在虛擬機比較少的時候，大部分物理主機的可以切換到關閉狀態，能量消耗自然降低了。

表4 各類策略總體能量消耗性能比較/Kwh

(3)虛擬機遷移次數

在Cloudsim模擬器中，如果云數據中心的物理資源不能滿足大量云客戶端的請求，將進入到虛擬機遷移過程。虛擬機遷移次數也是體現虛擬機分配策略是否優越的一個重要指標。表5顯示了FGA-VMP策略優化后整個云數據中心的虛擬機遷移情況，從表中可以看出當虛擬機的個數從100 VMs到600 VMs，與其它的策略比較起來，FGA-VMP的遷移次數一直處于比較低的水平。

(4)SLA在線時間分析

在虛擬機分配過程中，一個重要性能指標就是每個物理主機的SLA在線時間(SLA time per host)，它體現了物理主機具有高服務質量的在線時間情況。表6列出了FGA-VMP虛擬機放置優化策略后物理主機的SLA在線時間實驗結果，該結果明顯表示了FGA-VMP虛擬機放置優化策略比THR、IQR、MAD等策略性能優秀。

表5 遷移次數比較/次

表6 活動物理主機的SLA在線時間的比例/%

(5)物理資源利用效率

圖6顯示了FGA-VMP虛擬機放置優化策略在100個～600個虛擬機個數情況下的物理資源利用效率的比較結果。

圖6 整體物理資源利用效率比較/%

圖6中實驗結果表明，FGA-VMP優化算法可以很好減少物理資源的消耗的比例，這是因為FGA-VMP一直試圖改善多個維度的物理資源利用效率，在6個不同虛擬機個數的情況下，所有維度的資源消耗都不超過21%，大部分物理資源都充分利用起來了。

5 結束語

基于多目標優化的虛擬機放置策略是云數據中心的一個關鍵技術。本文通過改進遺傳算法，提出了基于家族遺傳算法的虛擬機放置方法FGA-VMP，它克服了普通遺傳算法的早熟和收斂速度慢的問題。和常見的能量感知的虛擬機分配策略比較起來，實驗結果表明FGA-VMP在負載均衡、總體能量消耗、虛擬機遷移次數、在線活動主機服務質量等性能有提高，FGA-VMP可以為企業構造節能的綠色大數據中心提供參考。下一步的工作是將FGA-VMP與其它的更加多的智能優化的虛擬機分配策略進行性能比較，調整遺傳算法中的參數繼續提高系統性能。