周 震，王 輝，李俊峰

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

0 引 言

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

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

仿真結(jié)果表明，F(xiàn)GA-VMP優(yōu)化策略形成新的虛擬機(jī)遷移模型之后可以更好節(jié)省云數(shù)據(jù)中心的能量消耗，提高物理資源利用效率。

1 虛擬機(jī)放置優(yōu)化算法的相關(guān)工作

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

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

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

由于目前以Anton Beloglazov博士等為團(tuán)隊(duì)開發(fā)的Cloudsim項(xiàng)目處于世界領(lǐng)先地位，所以本文的家族遺傳算法的虛擬機(jī)放置策略FGA-VMP依托了Cloudsim云平臺，F(xiàn)GA-VMP是一種既考慮了硬件因素，也考慮了軟件因素的虛擬機(jī)放置策略，以充分提高資源使用率為目標(biāo)函數(shù)。FGA-VMP與普通的遺傳算法優(yōu)化的虛擬機(jī)放置策略的優(yōu)點(diǎn)是克服了早熟問題和收斂速度慢的問題。在普通遺傳算法中，大部分算法是以云數(shù)據(jù)中心的能量消耗為目標(biāo)函數(shù)，還有少量策略是以降低SLA違規(guī)率為目標(biāo)函數(shù)，它們與FGA-VMP區(qū)別在于目標(biāo)函數(shù)不同。

2 FGA-VMP工作場景與建模

2.1 FGA-VMP工作場景

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

在Cloudsim中每個物理主機(jī)上都運(yùn)行有一個本地代理Local Broker，F(xiàn)GA-VMP優(yōu)化策略的實(shí)現(xiàn)主要在此模塊中完成，這個工作場景在大部分的文獻(xiàn)都有描述[4]。

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

2.2 FGA-VMP虛擬機(jī)放置建模

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

pj=(idj,cpuj,memj,bwj)

(1)

idj表示了物理主機(jī)的標(biāo)識符，cpuj表示了物理主機(jī)的處理器大小，memj表示了物理主機(jī)的可用內(nèi)存大小，bwj表示了物理主機(jī)所擁有的網(wǎng)絡(luò)帶寬大小，每個虛擬機(jī)也可以通過下面的向量來表示

vi=(idi,cpui,memi,bwi)

(2)

idi表示了虛擬機(jī)的標(biāo)識符，cpui表示了虛擬機(jī)的表示了對處理器的需求能力，memi表示了虛擬機(jī)對內(nèi)存的需求能力，bwi表示了虛擬機(jī)對網(wǎng)絡(luò)帶寬的需求能力。

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

(3)

包括下面這些約束條件

(4)

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

(5)

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

(6)

2.3 FGA-VMP的工作流程

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

步驟1 基于魯棒局部回歸LRR方法完成物理主機(jī)狀態(tài)檢測，當(dāng)然這個是Cloudsim中默認(rèn)的方式，形成侯選遷移物理主機(jī)列表MigratedHostList；

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

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

步驟4 重復(fù)上述步驟1～步驟3；

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

圖2 FGA-VMP策略運(yùn)用到虛擬機(jī)遷移過程

3 FGA-VMP的虛擬機(jī)放置過程實(shí)現(xiàn)

3.1 FGA-VMP實(shí)現(xiàn)的功能模塊

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

圖3 FGA-VMP虛擬機(jī)放置策略的實(shí)現(xiàn)模塊

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

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

(7)

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

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

(8)

式中：N表示種群的規(guī)模。

3.2 FGA-VMP的實(shí)現(xiàn)算法

下面是FGA-VMP家族遺傳算法的虛擬機(jī)放置過程的偽代碼，該代碼通過少量修改即可利用Java語言來實(shí)現(xiàn)，如下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

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

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

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

對于種群中的每個個體，F(xiàn)GA-VMP中通過適應(yīng)度fitness函數(shù)來評價個體的質(zhì)量，在普通遺傳算法中，適應(yīng)度函數(shù)通過算法所追求的目標(biāo)函數(shù)來產(chǎn)生，在FGA-VMP中，我們所考慮的目標(biāo)函數(shù)是整個云數(shù)據(jù)中心的物理資源的利用效率。下面的算法 Algorithm 2詳細(xì)表示了每個遺傳個體計算適應(yīng)度函數(shù)的方法，也是偽代碼的形式。

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的偽代碼描述了家族基因的方式如何來完成虛擬機(jī)放置這種多目標(biāo)優(yōu)化問題。它必須保證所有的染色體滿足約束條件，為了保證這個條件，F(xiàn)GA-VMP設(shè)計了新的獨(dú)立函數(shù)來處理每個遺傳個體是如何滿足這種約束條件。如果發(fā)現(xiàn)遺傳個體是不可行的，該函數(shù)能將其轉(zhuǎn)移到個體是可行的狀態(tài)之下。

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 實(shí)驗(yàn)與性能分析

4.1 測試環(huán)境

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

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

表2 一周內(nèi)不同的虛擬機(jī)請求個數(shù)

表3 虛擬機(jī)類型配置

4.2 測試結(jié)果與性能分析

(1)負(fù)載均衡結(jié)果分析

圖4顯示了通過Cloudsim工具包里的默認(rèn)虛擬機(jī)分配策略來完成虛擬機(jī)放置的情況。圖5顯示了通過FGA-VMP策略優(yōu)化后的虛擬機(jī)的放置情況。

圖4 Cloudsim工具的虛擬機(jī)分配優(yōu)化之前的效果

圖5 FGA-VMP虛擬機(jī)放置優(yōu)化之后的效果

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

(2)總體能量消耗分析

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

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

(3)虛擬機(jī)遷移次數(shù)

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

(4)SLA在線時間分析

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

表5 遷移次數(shù)比較/次

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

(5)物理資源利用效率

圖6顯示了FGA-VMP虛擬機(jī)放置優(yōu)化策略在100個～600個虛擬機(jī)個數(shù)情況下的物理資源利用效率的比較結(jié)果。

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

圖6中實(shí)驗(yàn)結(jié)果表明，F(xiàn)GA-VMP優(yōu)化算法可以很好減少物理資源的消耗的比例，這是因?yàn)镕GA-VMP一直試圖改善多個維度的物理資源利用效率，在6個不同虛擬機(jī)個數(shù)的情況下，所有維度的資源消耗都不超過21%，大部分物理資源都充分利用起來了。

5 結(jié)束語

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