鄧?yán)颉∫αΑ〗痂?/p>

摘要：

目前，云平臺(tái)的大多數(shù)動(dòng)態(tài)資源分配策略只考慮如何減少激活物理節(jié)點(diǎn)的數(shù)量來(lái)達(dá)到節(jié)能的目的，以實(shí)現(xiàn)綠色計(jì)算，但這些資源再配置方案很少考慮到虛擬機(jī)放置的穩(wěn)定性。針對(duì)應(yīng)用負(fù)載的動(dòng)態(tài)變化特征，提出一種新的面向多虛擬機(jī)分布穩(wěn)定性的基于多目標(biāo)優(yōu)化的動(dòng)態(tài)資源配置方法，結(jié)合各應(yīng)用負(fù)載的當(dāng)前狀態(tài)和未來(lái)的預(yù)測(cè)數(shù)據(jù)，綜合考慮虛擬機(jī)重新放置的開(kāi)銷(xiāo)以及新虛擬機(jī)放置狀態(tài)的穩(wěn)定性，并設(shè)計(jì)了面向虛擬機(jī)分布穩(wěn)定性的基于多目標(biāo)優(yōu)化的遺傳算法（MOGANS）進(jìn)行求解。仿真實(shí)驗(yàn)結(jié)果表明，相對(duì)于面向節(jié)能和多虛擬機(jī)重分布開(kāi)銷(xiāo)的遺傳算法（GANN），MOGANS得到的虛擬機(jī)分布方式的穩(wěn)定時(shí)間是GANN的10.42倍；同時(shí)，MOGANS也較好權(quán)衡了多虛擬機(jī)分布的穩(wěn)定性和新舊狀態(tài)轉(zhuǎn)換所需的虛擬機(jī)遷移開(kāi)銷(xiāo)之間的關(guān)系。

關(guān)鍵詞：

云計(jì)算；多目標(biāo)優(yōu)化；遺傳算法；動(dòng)態(tài)資源分配；虛擬機(jī)遷移

中圖分類(lèi)號(hào)：

TP319

文獻(xiàn)標(biāo)志碼：A

Abstract：

Currently， most resource reallocation methods in cloud computing mainly aim to how to reduce active physical nodes for green computing， however， node stability of virtual machine placement solution is not considered. According to varying workload information of applications， a new virtual machine placement method based on multiobjective optimization was proposed for node stability， considering both the overhead of virtual machine reallocation and the stability of new virtual machine placement， and a new MultiObjective optimization based Genetic Algorithm for Node Stability （MOGANS） was designed to solve this problem. The simulation results show that， the stability time of Virtual Machine （VM） placement obtained by MOGANS is 10.42 times as long as that of VM placement got by GANN （Genetic Algorithm for greeN computing and Numbers of migration）. Meanwhile， MOGANS can well balance stability time and migration overhead.

英文關(guān)鍵詞Key words：

cloud computing； multiobjective optimization； genetic algorithm； dynamic resource allocation； migration of virtual machine

0引言

云平臺(tái)[1]借助于虛擬化技術(shù)使得應(yīng)用資源的動(dòng)態(tài)按需配置成為可能[2-3]，可以同時(shí)為多個(gè)用戶(hù)提供共享資源池[4]，既極大地改善了資源的有效使用，又增加了云服務(wù)提供商的收益[5-6]。云環(huán)境中的資源分配可以分為兩個(gè)層次：粗粒度資源分配和細(xì)粒度資源分配。粗粒度資源分配是將各應(yīng)用虛擬機(jī)映射到不同的物理節(jié)點(diǎn)上，多個(gè)應(yīng)用虛擬機(jī)共享同一個(gè)物理節(jié)點(diǎn)上的硬件資源。粗粒度資源分配解決的是多個(gè)應(yīng)用虛擬機(jī)與多個(gè)物理節(jié)點(diǎn)之間的映射關(guān)系[7-8]。細(xì)粒度資源分配是在某一物理節(jié)點(diǎn)上調(diào)整每個(gè)應(yīng)用虛擬機(jī)的具體資源配置，細(xì)粒度資源配置解決的是確定單一物理節(jié)點(diǎn)上的資源在其上不同虛擬機(jī)間的分配配額，以保證各應(yīng)用虛擬機(jī)的服務(wù)級(jí)目標(biāo)[9]。由于細(xì)粒度資源分配的局限性，它對(duì)云平臺(tái)整個(gè)資源使用效率的影響有限，粗粒度資源分配方法決定了整個(gè)云平臺(tái)系統(tǒng)資源使用的有效性。目前大多數(shù)云平臺(tái)資源分配調(diào)度研究都是針對(duì)于粗粒度資源分配，本文所討論的動(dòng)態(tài)資源配置問(wèn)題主要針對(duì)粗粒度資源調(diào)度。

云平臺(tái)的粗粒度資源調(diào)度大多關(guān)注于合并物理節(jié)點(diǎn)上的虛擬機(jī)負(fù)載，或者縮短各任務(wù)的完成時(shí)間[10-11]，以減少激活物理節(jié)點(diǎn)的數(shù)量，從而達(dá)到節(jié)能目的，實(shí)現(xiàn)綠色計(jì)算；還有一些研究側(cè)重于通過(guò)資源調(diào)度來(lái)提升云服務(wù)提供商的服務(wù)收益[12]。文獻(xiàn)[7]和文獻(xiàn)[8]分別采用遺傳算法、約束規(guī)劃的方法來(lái)尋找虛擬機(jī)在物理節(jié)點(diǎn)上的最佳分布，最終使得已使用的物理節(jié)點(diǎn)數(shù)量最少；文獻(xiàn)[10]和文獻(xiàn)[11]分別提出改進(jìn)的基于多目標(biāo)免疫系統(tǒng)的任務(wù)調(diào)度算法和離散人工蜂群算法來(lái)縮短任務(wù)完成時(shí)間、降低任務(wù)執(zhí)行費(fèi)用、實(shí)現(xiàn)資源負(fù)載均衡等。然而，這些粗粒度資源調(diào)度方法忽略了云環(huán)境中應(yīng)用負(fù)載的動(dòng)態(tài)性，沒(méi)有考慮到各物理節(jié)點(diǎn)狀態(tài)的穩(wěn)定性。盡管各應(yīng)用虛擬機(jī)在當(dāng)前分布狀態(tài)中使用了比較少的物理節(jié)點(diǎn)，但是隨著應(yīng)用負(fù)載的變化，這些物理節(jié)點(diǎn)的狀態(tài)可能在不久的將來(lái)又會(huì)重新出現(xiàn)資源熱點(diǎn)，激發(fā)新一輪動(dòng)態(tài)資源的配置需求。

本文就是針對(duì)上述現(xiàn)象而提出的一種新的考慮物理節(jié)點(diǎn)穩(wěn)定性的粗粒度資源調(diào)度方法?；趹?yīng)用負(fù)載的預(yù)測(cè)信息，采用遺傳算法尋找各物理節(jié)點(diǎn)較為穩(wěn)定的虛擬機(jī)分布狀態(tài)，同時(shí)兼顧考慮舊虛擬機(jī)分布狀態(tài)到新虛擬機(jī)分布狀態(tài)之間的轉(zhuǎn)換開(kāi)銷(xiāo)[13-14]比較小。

本文的工作主要有以下三個(gè)方面：1）提出面向物理節(jié)點(diǎn)穩(wěn)定性或者虛擬機(jī)分布穩(wěn)定性的動(dòng)態(tài)資源分配方法；2）設(shè)計(jì)了基于穩(wěn)定時(shí)間、遷移次數(shù)等面向虛擬機(jī)分布穩(wěn)定性的多目標(biāo)優(yōu)化的遺傳算法（MultiObjective Genetic Algorithm for nOde Stability， MOGANS），采用組編碼的方式，并基于非支配排序遺傳算法Ⅱ（Nondominated Sorting Genetic Algorithm Ⅱ， NSGAⅡ）定義適應(yīng)度函數(shù)來(lái)評(píng)判各種虛擬機(jī)分布方式的優(yōu)劣；3）實(shí)現(xiàn)了算法MOGANS，將它和文獻(xiàn)[7]提出的算法——面向節(jié)能和多虛擬機(jī)重分布開(kāi)銷(xiāo)的遺傳算法（Genetic Algorithm for greeN computing and Numbers of migration， GANN）進(jìn)行了性能比較，并分析了它的運(yùn)行開(kāi)銷(xiāo)。仿真實(shí)驗(yàn)結(jié)果表明，MOGANS得到的虛擬機(jī)分布方式的穩(wěn)定時(shí)間是GANN的10.42倍；同時(shí)，MOGANS也較好權(quán)衡了多虛擬機(jī)分布的穩(wěn)定性和新舊狀態(tài)轉(zhuǎn)換所需的虛擬機(jī)遷移開(kāi)銷(xiāo)之間的關(guān)系。

1動(dòng)態(tài)資源配置問(wèn)題

在云環(huán)境中，各應(yīng)用被封裝部署在不同虛擬機(jī)中[15-16]，多個(gè)虛擬機(jī)可以共享同一個(gè)物理節(jié)點(diǎn)的計(jì)算資源。由于系統(tǒng)虛擬化技術(shù)的去耦合性，各虛擬機(jī)可以在不同的物理節(jié)點(diǎn)之間平滑無(wú)縫遷移[14]。虛擬機(jī)遷移是云平臺(tái)下粗粒度動(dòng)態(tài)資源配置的重要方式。動(dòng)態(tài)資源配置是隨著虛擬機(jī)應(yīng)用負(fù)載的變化，實(shí)時(shí)調(diào)整應(yīng)用的資源配置。

本文討論的動(dòng)態(tài)資源配置問(wèn)題假定云平臺(tái)是同構(gòu)環(huán)境，即每個(gè)物理節(jié)點(diǎn)的資源配置參數(shù)是一樣的，且物理節(jié)點(diǎn)和虛擬機(jī)數(shù)量固定，所有物理節(jié)點(diǎn)提供的資源也能夠滿(mǎn)足所有應(yīng)用虛擬機(jī)的需求。應(yīng)用虛擬機(jī)的資源請(qǐng)求只考慮兩類(lèi)資源——內(nèi)存和處理器。

為便于討論，在表1中給出了一些符號(hào)定義。

云平臺(tái)中，物理節(jié)點(diǎn)的狀態(tài)可以分成如下三種：熱狀態(tài)、溫狀態(tài)和冷狀態(tài)。熱狀態(tài)下，該物理節(jié)點(diǎn)上所有應(yīng)用虛擬機(jī)的總負(fù)載量超過(guò)了它所能承載的限度，出現(xiàn)了資源熱點(diǎn)，資源競(jìng)爭(zhēng)頻繁，應(yīng)用服務(wù)質(zhì)量有所下降，這時(shí)需要?jiǎng)討B(tài)擴(kuò)大應(yīng)用虛擬機(jī)的資源配置。熱狀態(tài)下的物理節(jié)點(diǎn)稱(chēng)為熱節(jié)點(diǎn)，熱節(jié)點(diǎn)需要通過(guò)虛擬機(jī)遷移方式減少其上應(yīng)用虛擬機(jī)的負(fù)載。溫狀態(tài)下，該物理節(jié)點(diǎn)上的資源供給和需求大致相當(dāng)，能保證應(yīng)用服務(wù)質(zhì)量。物理節(jié)點(diǎn)處于溫狀態(tài)是一種比較理想的狀態(tài)，資源得到有效使用，避免浪費(fèi)。冷狀態(tài)是相對(duì)于資源供給，資源的需求量相對(duì)較低，大多數(shù)資源處于空閑狀態(tài)，造成資源和能源的浪費(fèi)。

多個(gè)虛擬機(jī)在物理節(jié)點(diǎn)上最理想的分布方式，是每個(gè)物理節(jié)點(diǎn)都處于溫狀態(tài)，而且這種狀況保持盡可能長(zhǎng)的時(shí)間。為闡述多虛擬機(jī)分布的穩(wěn)定性，我們引入以下幾個(gè)概念。

定義1多虛擬機(jī)在物理節(jié)點(diǎn)上的分布方式Dk，是指虛擬機(jī)和物理節(jié)點(diǎn)的映射方式，可以用布爾矩陣X=（xij）M×N來(lái)表示。

定義2物理節(jié)點(diǎn)node1的穩(wěn)定時(shí)間Tnode1，是指該節(jié)點(diǎn)從某個(gè)時(shí)刻開(kāi)始保持溫狀態(tài)或冷狀態(tài)的時(shí)間間隔。顯然，熱節(jié)點(diǎn)的穩(wěn)定時(shí)間為0。

定義3多虛擬機(jī)分布方式Dk的穩(wěn)定時(shí)間TDk，是指從某個(gè)時(shí)刻開(kāi)始，每個(gè)節(jié)點(diǎn)都保持溫狀態(tài)或冷狀態(tài)的時(shí)間間隔。TDk和物理節(jié)點(diǎn)穩(wěn)定時(shí)間的關(guān)系如下所示：

TDk=min{Tnode1，Tnode2，…，TnodeM}

因此，云平臺(tái)的動(dòng)態(tài)資源分配問(wèn)題可以模型化如下：已知各虛擬機(jī)負(fù)載的動(dòng)態(tài)變化（包括現(xiàn)在的狀況和預(yù)測(cè)的未來(lái)負(fù)載信息），尋找多虛擬機(jī)在物理節(jié)點(diǎn)上的最佳放置方案，使其具有最長(zhǎng)的穩(wěn)定時(shí)間和最少的虛擬機(jī)遷移次數(shù)。問(wèn)題的目標(biāo)和約束條件定義如下：

max TDk

min∑Nj=1mj（1）

s.t. ∑Mi=1xij=1； j=1，2，…，N（2）

Ci≥∑Nj=1xijC′j； i=1，2，…，M（3）

Memi≥∑Nj=1xijMem′j； i=1，2，…，M（4）xij∈{0，1}，mi∈{0，1}； i=1，2，…，M， j=1，2，…，N（5）

動(dòng)態(tài)資源配置問(wèn)題有兩個(gè)目標(biāo)：第一個(gè)是使得新的虛擬機(jī)分布具有最長(zhǎng)的穩(wěn)定時(shí)間（max TDk），這個(gè)目標(biāo)意味著，熱節(jié)點(diǎn)不會(huì)在較短的時(shí)間內(nèi)出現(xiàn)在新的映射狀態(tài)中；另一個(gè)目標(biāo)是從當(dāng)前狀態(tài)到新的分布狀態(tài)只需要遷移最小數(shù)量的虛擬機(jī)（min∑Nj=1mj）。第二個(gè)目標(biāo)要求虛擬機(jī)從當(dāng)前狀態(tài)（用X=（xij）M×N表示）向新?tīng)顟B(tài)（用X′=（xij′）M×N表示）的轉(zhuǎn)換具有最小的遷移開(kāi)銷(xiāo)。其中，mj的定義如下：

mj=0，xij=x′i′j=1 and i=i′

1，xij=x′i′j=1 and i≠i′

約束條件中：式（2）表示每個(gè)虛擬機(jī)只在一個(gè)物理節(jié)點(diǎn)上；式（3）表示一個(gè)節(jié)點(diǎn)上的所有虛擬機(jī)的處理器資源請(qǐng)求總和不會(huì)超過(guò)該節(jié)點(diǎn)所能提供的相應(yīng)資源總和；式（4）表示

一個(gè)節(jié)點(diǎn)上的所有虛擬機(jī)的內(nèi)存資源請(qǐng)求總和不會(huì)超過(guò)該節(jié)點(diǎn)所能提供的相應(yīng)資源總和；式（5）說(shuō)明變量xij和mi是布爾變量。

2基于多目標(biāo)的遺傳算法MOGANS

云平臺(tái)中的動(dòng)態(tài)資源分配問(wèn)題是非確定多項(xiàng)式完全（Nondeterministic Polynomial Complete， NPC）問(wèn)題，很難在多項(xiàng)式時(shí)間內(nèi)找到其最優(yōu)解。遺傳算法借助于生物學(xué)領(lǐng)域的進(jìn)化學(xué)說(shuō)和遺傳學(xué)理論，通過(guò)計(jì)算機(jī)模擬自然生物進(jìn)化過(guò)程與機(jī)制來(lái)求解問(wèn)題，可以在多項(xiàng)式時(shí)間內(nèi)找到云平臺(tái)動(dòng)態(tài)資源配置問(wèn)題的近似最優(yōu)解[17]。遺傳算法可以在較大問(wèn)題解空間內(nèi)進(jìn)行全局多方向隨機(jī)搜索，不需要了解問(wèn)題域的先驗(yàn)知識(shí)[18]。

本文針對(duì)云平臺(tái)的動(dòng)態(tài)資源分配問(wèn)題，設(shè)計(jì)了面向虛擬機(jī)分布穩(wěn)定性的基于多目標(biāo)優(yōu)化的遺傳算法MOGANS，算法的設(shè)計(jì)主要考慮以下幾個(gè)方面：編碼和初始代生成、主要操作算子和適應(yīng)度函數(shù)。編碼是將云平臺(tái)的動(dòng)態(tài)資源配置問(wèn)題中各個(gè)因素和生物進(jìn)化、遺傳學(xué)中的染色體、基因等要素對(duì)應(yīng)起來(lái)，將實(shí)際應(yīng)用的求解問(wèn)題模擬成自然物種進(jìn)化演變過(guò)程；初始代是遺傳算法模擬生物進(jìn)化演變過(guò)程的源頭，初始代生成是在虛擬機(jī)的當(dāng)前分布狀態(tài)的基礎(chǔ)上隨機(jī)進(jìn)行的；遺傳算法的主要操作算子包括交叉、變異和選擇，而適應(yīng)度函數(shù)則主要用來(lái)量化染色體或個(gè)體的某個(gè)屬性或?qū)傩越M，并由此來(lái)評(píng)判染色體或個(gè)體的優(yōu)劣。

2.1編碼和初始代的生成

編碼是將云平臺(tái)的動(dòng)態(tài)資源配置問(wèn)題的求解數(shù)據(jù)轉(zhuǎn)換為遺傳空間的基因型結(jié)構(gòu)數(shù)據(jù)，是遺傳算法的重要部分。為了準(zhǔn)確描述云環(huán)境中虛擬機(jī)和物理節(jié)點(diǎn)之間的映射關(guān)系，本文采用組編碼方式。組編碼方式[19]將每個(gè)物理節(jié)點(diǎn)及其上承載的虛擬機(jī)共同描述為一個(gè)基因，多個(gè)基因形成的序列構(gòu)成染色體或個(gè)體，popSIZE個(gè)個(gè)體構(gòu)成一個(gè)群體。遺傳算法以這popSIZE個(gè)個(gè)體作為初始點(diǎn)開(kāi)始迭代生成若干子代，在子代中尋找求解問(wèn)題的近似最優(yōu)解。

圖1給出了組編碼的實(shí)例。在圖1中，6個(gè)虛擬機(jī)被部署在三個(gè)物理節(jié)點(diǎn)上。相應(yīng)地，在染色體里包含三個(gè)基因，每個(gè)基因?qū)?yīng)一個(gè)物理節(jié)點(diǎn)及其上的虛擬機(jī)集合。一個(gè)染色體或者個(gè)體則代表著云平臺(tái)動(dòng)態(tài)資源分配的一種可能的解決方案——多個(gè)虛擬機(jī)在物理節(jié)點(diǎn)上的一種分布方式。

遺傳算法要解決的是云平臺(tái)的動(dòng)態(tài)資源配置問(wèn)題，多虛擬機(jī)已經(jīng)分布在各物理節(jié)點(diǎn)上，由于應(yīng)用虛擬機(jī)負(fù)載的變化，當(dāng)前的虛擬機(jī)分布方式變得不再適合，需要調(diào)整虛擬機(jī)在物理節(jié)點(diǎn)上的分布方式。因此，遺傳算法的初始代應(yīng)該包含虛擬機(jī)的當(dāng)前分布方式信息，虛擬機(jī)的當(dāng)前分布方式對(duì)應(yīng)的組編碼作為初始代的一個(gè)個(gè)體。而初始代的其他個(gè)體則隨機(jī)產(chǎn)生，隨機(jī)方式可以提供問(wèn)題求解更大的搜索空間。

群體規(guī)模影響著遺傳算法的最終結(jié)果及其執(zhí)行效率：當(dāng)群體規(guī)模popSIZE太小時(shí)，遺傳算法容易陷入局部最優(yōu)解，性能一般不會(huì)理想；而群體規(guī)模popSIZE太大時(shí)，算法復(fù)雜度較高。popSIZE一般為10～160[20]。

2.2主要操作算子

遺傳算法主要有三個(gè)重要的操作算子：交叉、變異和選擇。

2.2.1交叉

交叉是兩個(gè)父體產(chǎn)生后代并從父代那里遺傳更多有意義的信息的操作，是遺傳算法的主要操作。由于組編碼模式可能造成不同染色體的長(zhǎng)度各異，交叉操作應(yīng)能夠在具有不同長(zhǎng)度的染色體上進(jìn)行。

如圖2所示，交叉算子主要有以下4個(gè)步驟：

1）在兩個(gè)父?jìng)€(gè)體A、B中分別隨機(jī)選擇交叉點(diǎn)。交叉點(diǎn)即為染色體中的某個(gè)基因，如圖2（a）所示的node4{v2，v7}和node2{v5}。

2）相互交換兩個(gè)父?jìng)€(gè)體中交叉點(diǎn)上的虛擬機(jī)。交換后，同一個(gè)父?jìng)€(gè)體中會(huì)出現(xiàn)包含相同虛擬機(jī)的不同基因，如圖2（b）所示的個(gè)體A，基因node3{v5，v8}和基因node4{v5}，個(gè)體B的基因node2{v2，v7}、基因node3{v2，v6}和基因node4{v7，v8}。而在實(shí)際的云平臺(tái)中，同一個(gè)虛擬機(jī)只能出現(xiàn)在一個(gè)物理節(jié)點(diǎn)上，相應(yīng)地，這些包含相同虛擬機(jī)的基因需要被調(diào)整，保證同一個(gè)虛擬機(jī)只能包含在一個(gè)基因中。

3）處理和交叉點(diǎn)包含相同虛擬機(jī)的基因以及由于交叉操作而丟失的虛擬機(jī)。兩個(gè)交叉點(diǎn)相互交換虛擬機(jī)后，同一個(gè)個(gè)體中會(huì)出現(xiàn)包含相同虛擬機(jī)的不同基因。刪除和交叉點(diǎn)含有相同虛擬機(jī)的基因上重復(fù)的虛擬機(jī)，該基因所包含的剩下的虛擬機(jī)需要被重新放置，而該基因?qū)?yīng)的物理節(jié)點(diǎn)的狀態(tài)由“已使用”變?yōu)椤拔词褂谩薄Ｈ鐖D2（c）中，個(gè)體A的基因node3{v5，v8}中的v5因?yàn)楹徒徊纥c(diǎn)上的虛擬機(jī)重復(fù)，需要被刪除，node3上的v8需要被重新放置，插入到待放置的虛擬機(jī)隊(duì)列中，等待被重新放置。另外，兩個(gè)交叉點(diǎn)相互交換虛擬機(jī)后，會(huì)丟失一些虛擬機(jī)，如圖2（c）中，個(gè)體A少了虛擬機(jī)v2和v7，這些丟失的虛擬機(jī)也需要被插入到待重新放置的虛擬機(jī)隊(duì)列中。

4）使用首次適應(yīng)探索法將上一步得到的需要重新放置的各虛擬機(jī)插入到染色體中。物理節(jié)點(diǎn)分為兩種狀態(tài)：“已使用”和“未使用”，將兩種不同狀態(tài)的物理節(jié)點(diǎn)分別按節(jié)點(diǎn)序號(hào)進(jìn)行排列，形成兩個(gè)隊(duì)列。首先，根據(jù)虛擬機(jī)的資源請(qǐng)求使用首次適應(yīng)探索法在“已使用”隊(duì)列上找到合適的物理節(jié)點(diǎn)，該物理節(jié)點(diǎn)必須有足夠的空閑資源容納該虛擬機(jī)。如果“已使用”隊(duì)列上沒(méi)有任何物理節(jié)點(diǎn)有足夠的空閑資源來(lái)承載該虛擬機(jī)，則在“未使用”隊(duì)列上選擇一個(gè)節(jié)點(diǎn)。圖2（d）顯示了重新放置虛擬機(jī)的最后結(jié)果。這樣，兩個(gè)父節(jié)點(diǎn)（node1{v1，v6}，node2{v3，v4}，node3{v5，v8}，node4{v2，v7}）和（node1{v1，v3，v4}，node2{v5}，node3{v2，v6}，node4{v7，v8}）經(jīng)過(guò)交叉操作，得到兩個(gè)子個(gè)體：（node1{v1，v6，v7}，node2{v3，v4，v8}，node4{v5，v2}）和（node1{v1，v3，v4}，node2{v2，v7，v6}，node3{v5，v8}）。

交叉并不一定在任意兩個(gè)父?jìng)€(gè)體之間進(jìn)行，該操作的發(fā)生有一定的概率。交叉概率qc控制著交叉操作被使用的頻率。若交叉概率qc設(shè)置過(guò)大，遺傳算法開(kāi)辟新的搜索區(qū)域的能力會(huì)增強(qiáng)，但高性能模式遭到破壞的可能性也會(huì)增大；若交叉概率設(shè)置太低，遺傳算法搜索可能陷入遲鈍狀態(tài)。一般地，交叉概率qc設(shè)在0.25～1.00之間[20]。

2.2.2變異

變異操作可以使得個(gè)體變得和其父代個(gè)體不一樣，它以任意的方式增加新的信息以擴(kuò)大搜索空間并避免陷入局部?jī)?yōu)化。變異是遺傳算法中輔助性的操作，其主要作用是維持群體的多樣性。

在算法MOGANS中，變異操作是按照首次適應(yīng)探索法重新放置隨機(jī)選擇的變異點(diǎn)上的虛擬機(jī)，并將該變異點(diǎn)對(duì)應(yīng)的物理節(jié)點(diǎn)的狀態(tài)由“已使用”變?yōu)椤拔词褂谩?，變異點(diǎn)即為染色體中的一個(gè)基因。

圖3給出了一個(gè)變異的例子。如圖3（a）所示，在染色體中隨機(jī)選擇變異點(diǎn)node2{v5}。虛擬機(jī)v5被插入到待放置的虛擬機(jī)隊(duì)列中，物理節(jié)點(diǎn)node2的狀態(tài)由“已使用”變?yōu)椤拔词褂谩薄5按照首次適應(yīng)算法重新放置后，即得到一個(gè)變異后的染色體，如圖3（c）所示。經(jīng)過(guò)變異操作，個(gè)體由

（node1{v1，v3，v4}，node2{v5}，node3{v2，v7}，node4{v6，v8}）變成（node1{v1，v3，v4}，node3{v2，v7}，node4{v6，v8，v5}）。

變異操作也是按一定概率qm進(jìn)行的。一般而言，較低的變異概率可防止群體中重要而單一的基因的可能丟失，而較高的變異概率會(huì)使得遺傳算法趨于純粹的隨機(jī)搜索。本文根據(jù)經(jīng)驗(yàn)值設(shè)定qm值為0.05。

2.2.3選擇

選擇操作是從子代中選擇較優(yōu)個(gè)體作為新一代父體，繼續(xù)重復(fù)迭代過(guò)程。個(gè)體的優(yōu)劣是通過(guò)定義適應(yīng)度函數(shù)來(lái)衡量的，而適應(yīng)度函數(shù)是以個(gè)體的屬性（比如：個(gè)體的穩(wěn)定時(shí)間、遷移次數(shù)等）為基礎(chǔ)的。本文中，個(gè)體的適應(yīng)度函數(shù)的定義是借助于NSGAⅡ的分級(jí)排序思想。算法NSGAⅡ先根據(jù)個(gè)體之間的支配與非支配關(guān)系將個(gè)體分成若干等級(jí)，同一級(jí)別內(nèi)個(gè)體再通過(guò)定義擁擠距離來(lái)排序。適應(yīng)度函數(shù)的具體定義見(jiàn)第2.3節(jié)。

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

適應(yīng)度函數(shù)主要是用來(lái)衡量個(gè)體的優(yōu)劣性，其定義是基于個(gè)體的某個(gè)屬性或者屬性組，其目標(biāo)是將多個(gè)個(gè)體按照優(yōu)劣進(jìn)行線性排序。本文采用非支配排序遺傳算法NSGAⅡ[21]來(lái)定義適應(yīng)度函數(shù)。NSGAⅡ根據(jù)個(gè)體之間的支配與非支配關(guān)系分層實(shí)現(xiàn)，適合于多目標(biāo)優(yōu)化問(wèn)題，非劣最優(yōu)解分布均勻，算法的計(jì)算復(fù)雜度適中[21]。

適應(yīng)度函數(shù)的計(jì)算分成兩個(gè)步驟：1）首先根據(jù)每個(gè)個(gè)體的穩(wěn)定時(shí)間、遷移次數(shù)等計(jì)算個(gè)體的非支配等級(jí)，同一等級(jí)內(nèi)可能包含多個(gè)個(gè)體；2）在同一等級(jí)內(nèi)，計(jì)算每個(gè)個(gè)體的擁擠距離來(lái)體現(xiàn)每個(gè)個(gè)體的優(yōu)劣。

非支配等級(jí)的計(jì)算是基于優(yōu)化的多個(gè)目標(biāo)判斷個(gè)體之間的支配關(guān)系或非支配關(guān)系。遍歷所有個(gè)體，計(jì)算每個(gè)個(gè)體被支配的個(gè)體數(shù)及其支配的個(gè)體集合。支配關(guān)系判斷dominate（ch1，ch2）的偽代碼如下所示，如果相對(duì)于個(gè)體ch2，個(gè)體ch1的穩(wěn)定時(shí)間長(zhǎng)并且遷移次數(shù)少（第1）行），則個(gè)體ch1支配ch2，否則，個(gè)體ch1不能支配ch2。任意兩個(gè)個(gè)體a、b的支配關(guān)系只可能是以下三種情形之一：a支配b；b支配a；a、b相互不能支配。

如果沒(méi)有其他任何個(gè)體支配個(gè)體a，則個(gè)體a的等級(jí)設(shè)為1為最高級(jí)，也是最優(yōu)等級(jí)，即個(gè)體等級(jí)值越低，級(jí)別越高，個(gè)體越優(yōu)；其他個(gè)體的等級(jí)是基于支配個(gè)體的等級(jí)計(jì)算的，個(gè)體a的等級(jí)為支配a的級(jí)別最低的個(gè)體的級(jí)別加1。計(jì)算個(gè)體等級(jí)non_dominatedsort （CH）的偽代碼如下所示。偽代碼中，從第1）行到第15）行是計(jì)算每個(gè)個(gè)體ch1支配的個(gè)體集dSet[ch1]以及被支配的個(gè)體數(shù)量ddn[ch1]。如果ddn[ch1]值為0，則ch1的等級(jí)為1；第16）行到第30）行是計(jì)算除等級(jí)1之外的個(gè)體的等級(jí)，個(gè)體的等級(jí)取決于支配該個(gè)體的最低等級(jí)。

在同一等級(jí)內(nèi)，不同個(gè)體的優(yōu)劣使用擁擠距離來(lái)衡量，擁擠距離值越大，該個(gè)體越優(yōu)。為了保證遺傳后代的多樣性，避免陷入局部搜索，擁擠距離的計(jì)算基于個(gè)體屬性值的分布狀況：若個(gè)體的屬性值分布密集，則該個(gè)體的擁擠距離較低；反之，若個(gè)體的屬性值分布稀疏，則該個(gè)體的擁擠距離較高，提供保留該個(gè)體更多的幾率。擁擠距離計(jì)算crowdingdistance （CHSet[i]）的偽代碼如下所示：

3性能評(píng)估

本章主要評(píng)估面向物理節(jié)點(diǎn)穩(wěn)定性的多目標(biāo)優(yōu)化遺傳算法MOGANS的性能。首先將MOGANS和其他算法在得到的虛擬機(jī)放置方案穩(wěn)定時(shí)間、遷移次數(shù)和激活物理節(jié)點(diǎn)數(shù)量等方面的表現(xiàn)進(jìn)行對(duì)比；接著，對(duì)MOGANS的運(yùn)行時(shí)間開(kāi)銷(xiāo)進(jìn)行分析。

實(shí)驗(yàn)均在Dell optiplex上進(jìn)行，Dell optiplex配置有第四代Intel Core i5 CPU、8GB內(nèi)存和1TB硬盤(pán)。根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)，遺傳算法的交叉概率qc設(shè)為0.75，變異概率qm設(shè)為0.05。

3.1MOGANS和其他算法的比較

我們將本文提出的面向虛擬機(jī)分布穩(wěn)定性的多目標(biāo)遺傳算法MOGANS和對(duì)比算法包括面向多虛擬機(jī)分布穩(wěn)定性的遺傳算法（Genetic Algorithm for Stability， GAS）、面向多虛擬機(jī)重分布開(kāi)銷(xiāo)的遺傳算法（Genetic Algorithm for Numbers of migration， GAN）、面向節(jié)能和多虛擬機(jī)重分布開(kāi)銷(xiāo)的遺傳算法（Genetic Algorithm for greeN computing and Numbers of migration， GANN）分別作了比較。其中GANN是基于文獻(xiàn)[3]提出的算法思想而實(shí)現(xiàn)的，以使用的物理節(jié)點(diǎn)數(shù)量（即激活物理節(jié)點(diǎn)數(shù)量）和新舊狀態(tài)轉(zhuǎn)換所需的遷移開(kāi)銷(xiāo)為優(yōu)化目標(biāo)。這些算法均用Java實(shí)現(xiàn)。

在實(shí)驗(yàn)中，我們仿真了32個(gè)物理節(jié)點(diǎn)和86個(gè)虛擬機(jī)，各應(yīng)用虛擬機(jī)的動(dòng)態(tài)資源需求信息均隨機(jī)生成，假定各應(yīng)用的資源需求信息已知，包括各應(yīng)用在未來(lái)的資源需求預(yù)測(cè)信息。在虛擬機(jī)的初始分布狀態(tài)中，設(shè)定約6%的物理節(jié)點(diǎn)出現(xiàn)資源過(guò)熱的狀態(tài)。目前，虛擬機(jī)的資源需求只考慮了二維資源——處理器和內(nèi)存。各遺傳算法中每代的規(guī)模大小均設(shè)置為48（popSIZE=48），種群總代數(shù)設(shè)為32（MAX_GEN=32）。

在相同的初始條件（相同的虛擬機(jī)分布初始狀態(tài)和相同的各應(yīng)用虛擬機(jī)的負(fù)載變化）下，運(yùn)行上述四種算法，分別得到各自的虛擬機(jī)的新分布狀態(tài)，這些新分布狀態(tài)的穩(wěn)定時(shí)間、遷移次數(shù)和空閑物理節(jié)點(diǎn)數(shù)量如表2所示。

從表2中可以發(fā)現(xiàn)，MOGANS在虛擬機(jī)分布的穩(wěn)定性和新舊狀態(tài)所需的虛擬機(jī)遷移開(kāi)銷(xiāo)之間作了較好的平衡，保證新的多虛擬機(jī)分布狀態(tài)不僅具有較長(zhǎng)的穩(wěn)定時(shí)間，而且從虛擬機(jī)的當(dāng)前分布狀態(tài)變換到新的虛擬機(jī)分布狀態(tài)需要的虛擬機(jī)遷移次數(shù)也相對(duì)較少。雖然GAN只需經(jīng)過(guò)最少次數(shù)的虛擬機(jī)遷移就可以變換到新虛擬機(jī)分布狀態(tài)，但該新虛擬機(jī)分布狀態(tài)只能保持較短時(shí)間的穩(wěn)定性，一旦虛擬機(jī)分布變得不穩(wěn)定，將會(huì)激發(fā)新的動(dòng)態(tài)資源配置請(qǐng)求而造成新一輪的虛擬機(jī)遷移。GANN由于考慮了綠色計(jì)算，得到的新虛擬機(jī)分布狀態(tài)使用了最少的激活物理節(jié)點(diǎn)，剩下的空閑物理節(jié)點(diǎn)個(gè)數(shù)最多，是MOGANS的空閑物理節(jié)點(diǎn)數(shù)目的8倍左右；但是，GANN得到新虛擬機(jī)分布方式的穩(wěn)定時(shí)間只有MOGANS的0.096倍，即MOGANS得到新虛擬機(jī)分布方式的穩(wěn)定時(shí)間是GANN的10.42倍。這說(shuō)明，GANN得到的新虛擬機(jī)分布狀態(tài)盡管更節(jié)能，但這種節(jié)能狀態(tài)并不能長(zhǎng)久保持，一旦分布狀態(tài)變得不穩(wěn)定，將會(huì)額外增加新的動(dòng)態(tài)資源配置開(kāi)銷(xiāo)，節(jié)能效果也會(huì)大打折扣。

3.2MOGANS的運(yùn)行時(shí)間開(kāi)銷(xiāo)分析

還通過(guò)實(shí)驗(yàn)分析了算法MOGANS的運(yùn)行時(shí)間開(kāi)銷(xiāo)。

MOGANS中影響算法運(yùn)行時(shí)間的因素主要有兩個(gè)：種群大小和種群總代數(shù)。不斷變換種群大小和種群總代數(shù)的值，分別測(cè)量算法的運(yùn)行時(shí)間，結(jié)果如圖4所示。

圖4中，當(dāng)種群大小從40增加到130（上升幅度為225%）、總代數(shù)從100增加到400（上升幅度為300%）時(shí)，算法的執(zhí)行時(shí)間從1.46s增加到7.67s（上升幅度為425%）。當(dāng)種群大小從750增加到800（上升幅度為6.67%）、總代數(shù)從2600增加到3000（上升幅度為15.38%）時(shí)，算法的執(zhí)行時(shí)間從1015s增加到1566s（上升幅度為54.29%）。可以看出，當(dāng)種群大小和總代數(shù)上升到一定數(shù)量時(shí)，算法運(yùn)行時(shí)間的上升幅度是種群大小增幅的若干倍，算法運(yùn)行時(shí)間近似于呈幾何級(jí)數(shù)增長(zhǎng)。就目前的運(yùn)算規(guī)模，MOGANS的執(zhí)行時(shí)間開(kāi)銷(xiāo)還在可承受的范圍之內(nèi)，不影響整個(gè)云平臺(tái)動(dòng)態(tài)資源配置進(jìn)程。當(dāng)算法的運(yùn)算規(guī)模繼續(xù)增加時(shí)，可考慮并行化遺傳算法的運(yùn)行過(guò)程，不同的交叉操作或變異操作具有較好的獨(dú)立性，比較適合并行化，可以充分利用現(xiàn)有多核計(jì)算機(jī)的性能，降低算法的時(shí)間開(kāi)銷(xiāo)。

4結(jié)語(yǔ)

本文針對(duì)云計(jì)算的應(yīng)用負(fù)載動(dòng)態(tài)變化的特征，提出了考慮虛擬機(jī)分布穩(wěn)定性的動(dòng)態(tài)資源調(diào)度方法，以多虛擬機(jī)分布狀態(tài)的穩(wěn)定時(shí)間和新舊狀態(tài)轉(zhuǎn)換所需的遷移開(kāi)銷(xiāo)為優(yōu)化目標(biāo)，采用遺傳算法找到多虛擬機(jī)分布的近似最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明， MOGANS得到的虛擬機(jī)分布方式的穩(wěn)定時(shí)間是GANN的10.42倍；同時(shí)，MOGANS也較好權(quán)衡了多虛擬機(jī)分布的穩(wěn)定性和新舊狀態(tài)轉(zhuǎn)換所需的虛擬機(jī)遷移開(kāi)銷(xiāo)之間的關(guān)系。然而，多虛擬機(jī)分布的穩(wěn)定性和綠色計(jì)算是兩個(gè)相互矛盾的因素，較好的多虛擬機(jī)的穩(wěn)定分布往往以增加能耗為代價(jià)。因此，多虛擬機(jī)的穩(wěn)定分布和綠色計(jì)算之間關(guān)系的權(quán)衡將是下一步的研究工作。

參考文獻(xiàn)：

[1]

ARMBRUST M， FOX A， GRIFFITH R， et al. Above the clouds： a Berkeley view of cloud computing [R]. Department Electrical Engineer and Computer Sciences， University of California， Berkely， 2009.

ARMBRUST M， FOX A， GRIFFITH R， et al. Above the clouds： a Berkeley view of cloud computing [EB/OL]. [20160103]. http：//www.csc.villanova.edu/～nadi/csc8580/S11/CloudComputing.pdf.

[2]

RAI A， BHAGWAN R， GUHA S. Generalized resource allocation for the cloud [C]// SoCC 12： Proceedings of the 3rd ACM Symposium on Cloud Computing. New York： ACM， 2012：Article No. 15.

[3]

CHEN L， SHEN H. Consolidating complementary VMs with spatial/temporalawareness in cloud datacenters [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 1033-1041.

[4]

WANG W， LI B， LIANG B. Dominant resource fairness in cloud computing systems with heterogeneous servers [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 583-591.

[5]

ZHANG L， LI Z， WU C. Dynamic resource provisioning in cloud computing： a randomized auction approach [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway： NJ： IEEE， 2014： 433-441.

[6]

ZHOU Z， LIU F， LI Z， et al. When smart grid meets geodistributed cloud： an auction approach to datacenter demand response [C]// Piscataway of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 2650-2658.

[7]

李強(qiáng)，郝沁汾，肖利民，等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（12）：2253-2264.（LI Q， HAO Q F， XIAO L M， et al. Adaptive management and multiobjective optimization for virtual machine placement in cloud computing [J]. Chinese Journal of Computers， 2011， 34（12）： 2253-2264.）

[8]

HERMENIER F， LORCA X， MENAUD J M， et al. Entropy： a consolidation manager for clusters [C]// VEE 09： Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. New York： ACM， 2009： 41-50.

[9]

ADAMS K， AGESEN O. A comparison of software and hardware techniques for x86 virtualization [J]. ACM Sigplan Notices， 2006， 41（11）： 2-13.

[10]

段凱蓉，張功萱. 基于多目標(biāo)免疫系統(tǒng)算法的云任務(wù)調(diào)度策略[J].計(jì)算機(jī)應(yīng)用，2016，36（2）：324-329.（DUAN K R， ZHANG G X. Multiobjective immune system algorithm for task scheduling in cloud computing [J]. Journal of Computer Applications， 2016， 36（2）： 324-329.）

[11]

倪志偉，李蓉蓉，方清華，等. 基于離散人工蜂群算法的云任務(wù)調(diào)度優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用，2016，36（1）：107-112.（NI Z W， LI R R， FANG Q H， et al. Optimization of cloud task scheduling based on discrete artificial bee colony algorithm [J]. Journal of Computer Applications， 2016， 36（1）： 107-112.）

[12]

陳冬林，姚夢(mèng)迪，鄧國(guó)華.多實(shí)例云計(jì)算資源市場(chǎng)下超額預(yù)訂決策方法[J].計(jì)算機(jī)應(yīng)用，2016，36（1）：113-116.（CHEN D L， YAO M D， DENG G H. Overbooking decisionmaking method of multiple instances under cloud computing resource market [J]. Journal of Computer Applications， 2016， 36（1）： 113-116.）

[13]

XU F， LIU F， JIN H， et al. Managing performance overhead of virtual machines in cloud computing： a survey， state of the art， and future directions [J]. Proceedings of the IEEE， 2014， 102（1）： 11-31.

[14]

JIN H， DENG L， WU S， et al. MECOM： Live migration of virtual machines by adaptively compressing memory pages [J]. Future Generation Computer Systems， 2014， 38（3）： 23-35.

[15]

CHE J， SHI C， YU Y， et al. A synthetical performance evaluation of openVZ， Xen and KVM [C]// APSCC 10： Proceedings of the 2010 IEEE AsiaPacific Services Computing Conference. Washington， DC： IEEE Computer Society， 2010： 587-594.