云計算中基于多目標優(yōu)化的動態(tài)資源配置方法

鄧莉　姚力　金瑜

摘要：

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

關(guān)鍵詞：

云計算；多目標優(yōu)化；遺傳算法；動態(tài)資源分配；虛擬機遷移

中圖分類號：

TP319

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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）

動態(tài)資源配置問題有兩個目標：第一個是使得新的虛擬機分布具有最長的穩(wěn)定時間（max TDk），這個目標意味著，熱節(jié)點不會在較短的時間內(nèi)出現(xiàn)在新的映射狀態(tài)中；另一個目標是從當前狀態(tài)到新的分布狀態(tài)只需要遷移最小數(shù)量的虛擬機（min∑Nj=1mj）。第二個目標要求虛擬機從當前狀態(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）表示每個虛擬機只在一個物理節(jié)點上；式（3）表示一個節(jié)點上的所有虛擬機的處理器資源請求總和不會超過該節(jié)點所能提供的相應(yīng)資源總和；式（4）表示

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

2基于多目標的遺傳算法MOGANS

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

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

2.1編碼和初始代的生成

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

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

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

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

2.2主要操作算子

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

2.2.1交叉

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

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

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

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

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

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

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

2.2.2變異

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

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

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

（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ù)經(jīng)驗值設(shè)定qm值為0.05。

2.2.3選擇

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

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

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

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

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

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

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

3性能評估

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

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

3.1MOGANS和其他算法的比較

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

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

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

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

3.2MOGANS的運行時間開銷分析

還通過實驗分析了算法MOGANS的運行時間開銷。

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

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

4結(jié)語

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

李強，郝沁汾，肖利民，等. 云計算中虛擬機放置的自適應(yīng)管理與多目標優(yōu)化[J].計算機學報，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]

段凱蓉，張功萱. 基于多目標免疫系統(tǒng)算法的云任務(wù)調(diào)度策略[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]. 計算機應(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]

陳冬林，姚夢迪，鄧國華.多實例云計算資源市場下超額預(yù)訂決策方法[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.