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

摘要：

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

關(guān)鍵詞：

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

中圖分類號：

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引言

云平臺[1]借助于虛擬化技術(shù)使得應(yīng)用資源的動(dòng)態(tài)按需配置成為可能[2-3]，可以同時(shí)為多個(gè)用戶提供共享資源池[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ù)級目標(biāo)[9]。由于細(xì)粒度資源分配的局限性，它對云平臺整個(gè)資源使用效率的影響有限，粗粒度資源分配方法決定了整個(gè)云平臺系統(tǒng)資源使用的有效性。目前大多數(shù)云平臺資源分配調(diào)度研究都是針對于粗粒度資源分配，本文所討論的動(dòng)態(tài)資源配置問題主要針對粗粒度資源調(diào)度。

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

本文就是針對上述現(xiàn)象而提出的一種新的考慮物理節(jié)點(diǎn)穩(wěn)定性的粗粒度資源調(diào)度方法?；趹?yīng)用負(fù)載的預(yù)測信息，采用遺傳算法尋找各物理節(jié)點(diǎn)較為穩(wěn)定的虛擬機(jī)分布狀態(tài)，同時(shí)兼顧考慮舊虛擬機(jī)分布狀態(tài)到新虛擬機(jī)分布狀態(tài)之間的轉(zhuǎn)換開銷[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ù)來評判各種虛擬機(jī)分布方式的優(yōu)劣；3）實(shí)現(xiàn)了算法MOGANS，將它和文獻(xiàn)[7]提出的算法——面向節(jié)能和多虛擬機(jī)重分布開銷的遺傳算法（Genetic Algorithm for greeN computing and Numbers of migration， GANN）進(jìn)行了性能比較，并分析了它的運(yùn)行開銷。仿真實(shí)驗(yàn)結(jié)果表明，MOGANS得到的虛擬機(jī)分布方式的穩(wěn)定時(shí)間是GANN的10.42倍；同時(shí)，MOGANS也較好權(quán)衡了多虛擬機(jī)分布的穩(wěn)定性和新舊狀態(tài)轉(zhuǎn)換所需的虛擬機(jī)遷移開銷之間的關(guān)系。

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

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

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

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

云平臺中，物理節(jié)點(diǎn)的狀態(tài)可以分成如下三種：熱狀態(tài)、溫狀態(tài)和冷狀態(tài)。熱狀態(tài)下，該物理節(jié)點(diǎn)上所有應(yīng)用虛擬機(jī)的總負(fù)載量超過了它所能承載的限度，出現(xiàn)了資源熱點(diǎn)，資源競爭頻繁，應(yīng)用服務(wù)質(zhì)量有所下降，這時(shí)需要?jiǎng)討B(tài)擴(kuò)大應(yīng)用虛擬機(jī)的資源配置。熱狀態(tài)下的物理節(jié)點(diǎn)稱為熱節(jié)點(diǎn)，熱節(jié)點(diǎn)需要通過虛擬機(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)是相對于資源供給，資源的需求量相對較低，大多數(shù)資源處于空閑狀態(tài)，造成資源和能源的浪費(fèi)。

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

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

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

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

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

因此，云平臺的動(dòng)態(tài)資源分配問題可以模型化如下：已知各虛擬機(jī)負(fù)載的動(dòng)態(tài)變化（包括現(xiàn)在的狀況和預(yù)測的未來負(fù)載信息），尋找多虛擬機(jī)在物理節(jié)點(diǎn)上的最佳放置方案，使其具有最長的穩(wěn)定時(shí)間和最少的虛擬機(jī)遷移次數(shù)。問題的目標(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)資源配置問題有兩個(gè)目標(biāo)：第一個(gè)是使得新的虛擬機(jī)分布具有最長的穩(wěn)定時(shí)間（max TDk），這個(gè)目標(biāo)意味著，熱節(jié)點(diǎn)不會在較短的時(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ài)（用X′=（xij′）M×N表示）的轉(zhuǎn)換具有最小的遷移開銷。其中，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ī)的處理器資源請求總和不會超過該節(jié)點(diǎn)所能提供的相應(yīng)資源總和；式（4）表示

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

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

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

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

2.1編碼和初始代的生成

編碼是將云平臺的動(dòng)態(tài)資源配置問題的求解數(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)開始迭代生成若干子代，在子代中尋找求解問題的近似最優(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è)體則代表著云平臺動(dòng)態(tài)資源分配的一種可能的解決方案——多個(gè)虛擬機(jī)在物理節(jié)點(diǎn)上的一種分布方式。

遺傳算法要解決的是云平臺的動(dòng)態(tài)資源配置問題，多虛擬機(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)前分布方式對應(yīng)的組編碼作為初始代的一個(gè)個(gè)體。而初始代的其他個(gè)體則隨機(jī)產(chǎn)生，隨機(jī)方式可以提供問題求解更大的搜索空間。

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

2.2主要操作算子

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

2.2.1交叉

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

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

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

2）相互交換兩個(gè)父個(gè)體中交叉點(diǎn)上的虛擬機(jī)。交換后，同一個(gè)父個(gè)體中會出現(xiàn)包含相同虛擬機(jī)的不同基因，如圖2（b）所示的個(gè)體A，基因node3{v5，v8}和基因node4{v5}，個(gè)體B的基因node2{v2，v7}、基因node3{v2，v6}和基因node4{v7，v8}。而在實(shí)際的云平臺中，同一個(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è)體中會出現(xiàn)包含相同虛擬機(jī)的不同基因。刪除和交叉點(diǎn)含有相同虛擬機(jī)的基因上重復(fù)的虛擬機(jī)，該基因所包含的剩下的虛擬機(jī)需要被重新放置，而該基因?qū)?yīng)的物理節(jié)點(diǎn)的狀態(tài)由“已使用”變?yōu)椤拔词褂谩?。如圖2（c）中，個(gè)體A的基因node3{v5，v8}中的v5因?yàn)楹徒徊纥c(diǎn)上的虛擬機(jī)重復(fù)，需要被刪除，node3上的v8需要被重新放置，插入到待放置的虛擬機(jī)隊(duì)列中，等待被重新放置。另外，兩個(gè)交叉點(diǎn)相互交換虛擬機(jī)后，會丟失一些虛擬機(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)序號進(jìn)行排列，形成兩個(gè)隊(duì)列。首先，根據(jù)虛擬機(jī)的資源請求使用首次適應(yīng)探索法在“已使用”隊(duì)列上找到合適的物理節(jié)點(diǎn)，該物理節(jié)點(diǎn)必須有足夠的空閑資源容納該虛擬機(jī)。如果“已使用”隊(duì)列上沒有任何物理節(jié)點(diǎn)有足夠的空閑資源來承載該虛擬機(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)過交叉操作，得到兩個(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è)父個(gè)體之間進(jìn)行，該操作的發(fā)生有一定的概率。交叉概率qc控制著交叉操作被使用的頻率。若交叉概率qc設(shè)置過大，遺傳算法開辟新的搜索區(qū)域的能力會增強(qiáng)，但高性能模式遭到破壞的可能性也會增大；若交叉概率設(shè)置太低，遺傳算法搜索可能陷入遲鈍狀態(tài)。一般地，交叉概率qc設(shè)在0.25～1.00之間[20]。

2.2.2變異

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

在算法MOGANS中，變異操作是按照首次適應(yīng)探索法重新放置隨機(jī)選擇的變異點(diǎn)上的虛擬機(jī)，并將該變異點(diǎn)對應(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)椤拔词褂谩?。將v5按照首次適應(yīng)算法重新放置后，即得到一個(gè)變異后的染色體，如圖3（c）所示。經(jīng)過變異操作，個(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)行的。一般而言，較低的變異概率可防止群體中重要而單一的基因的可能丟失，而較高的變異概率會使得遺傳算法趨于純粹的隨機(jī)搜索。本文根據(jù)經(jīng)驗(yàn)值設(shè)定qm值為0.05。

2.2.3選擇

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

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

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

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

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

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

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

3性能評估

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

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

3.1MOGANS和其他算法的比較

我們將本文提出的面向虛擬機(jī)分布穩(wěn)定性的多目標(biāo)遺傳算法MOGANS和對比算法包括面向多虛擬機(jī)分布穩(wěn)定性的遺傳算法（Genetic Algorithm for Stability， GAS）、面向多虛擬機(jī)重分布開銷的遺傳算法（Genetic Algorithm for Numbers of migration， GAN）、面向節(jié)能和多虛擬機(jī)重分布開銷的遺傳算法（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)換所需的遷移開銷為優(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)用在未來的資源需求預(yù)測信息。在虛擬機(jī)的初始分布狀態(tài)中，設(shè)定約6%的物理節(jié)點(diǎn)出現(xiàn)資源過熱的狀態(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ī)遷移開銷之間作了較好的平衡，保證新的多虛擬機(jī)分布狀態(tài)不僅具有較長的穩(wěn)定時(shí)間，而且從虛擬機(jī)的當(dāng)前分布狀態(tài)變換到新的虛擬機(jī)分布狀態(tài)需要的虛擬機(jī)遷移次數(shù)也相對較少。雖然GAN只需經(jīng)過最少次數(shù)的虛擬機(jī)遷移就可以變換到新虛擬機(jī)分布狀態(tài)，但該新虛擬機(jī)分布狀態(tài)只能保持較短時(shí)間的穩(wěn)定性，一旦虛擬機(jī)分布變得不穩(wěn)定，將會激發(fā)新的動(dòng)態(tài)資源配置請求而造成新一輪的虛擬機(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倍。這說明，GANN得到的新虛擬機(jī)分布狀態(tài)盡管更節(jié)能，但這種節(jié)能狀態(tài)并不能長久保持，一旦分布狀態(tài)變得不穩(wěn)定，將會額外增加新的動(dòng)態(tài)資源配置開銷，節(jié)能效果也會大打折扣。

3.2MOGANS的運(yùn)行時(shí)間開銷分析

還通過實(shí)驗(yàn)分析了算法MOGANS的運(yùn)行時(shí)間開銷。

MOGANS中影響算法運(yùn)行時(shí)間的因素主要有兩個(gè)：種群大小和種群總代數(shù)。不斷變換種群大小和種群總代數(shù)的值，分別測量算法的運(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í)間近似于呈幾何級數(shù)增長。就目前的運(yùn)算規(guī)模，MOGANS的執(zhí)行時(shí)間開銷還在可承受的范圍之內(nèi)，不影響整個(gè)云平臺動(dòng)態(tài)資源配置進(jìn)程。當(dāng)算法的運(yùn)算規(guī)模繼續(xù)增加時(shí)，可考慮并行化遺傳算法的運(yùn)行過程，不同的交叉操作或變異操作具有較好的獨(dú)立性，比較適合并行化，可以充分利用現(xiàn)有多核計(jì)算機(jī)的性能，降低算法的時(shí)間開銷。

4結(jié)語

本文針對云計(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)換所需的遷移開銷為優(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ī)遷移開銷之間的關(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]

陳冬林，姚夢迪，鄧國華.多實(shí)例云計(jì)算資源市場下超額預(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.