利用蟻群算法完成虛擬機放置的優(yōu)化

陳 艷，周天綺，徐勝超

(1.桂林航天工業(yè)學院 計算機科學與工程學院，廣西 桂林 541004；2.浙江醫(yī)藥高等?？茖W校 醫(yī)療器械學院，浙江 寧波 315100；3.北部灣大學 電子與信息工程學院，廣西 欽州 535011)

0 引 言

物理資源利用效率充分利用與低能量消耗是云數(shù)據(jù)中心構(gòu)造的2個主要目標[1-3]，目前主要靠虛擬機遷移技術(shù)來實現(xiàn)。在虛擬機遷移過程中，最重要的是虛擬機放置策略[4-6]，該過程有很多智能算法進行優(yōu)化，例如增強學習算法[7]、花授粉算法[8]、基于數(shù)據(jù)依賴的優(yōu)化算法[9]、基于溫度感知群優(yōu)化算法[10]、基于任務(wù)映射的優(yōu)化算法[11]、基于螢火蟲群的優(yōu)化算法等[12]、蟻群算法[13]、家族遺傳算法[14]、混合遺傳算法、改進的遺傳算法[15]。

本文依托于Cloudsim云平臺工具，在物理主機狀態(tài)檢測和虛擬機選擇過程都采用Cloudsim中默認的優(yōu)化策略；著重考慮采用蟻群算法的方式來優(yōu)化虛擬機放置過程[13]。提出一種基于蟻群算法優(yōu)化的虛擬機放置方法ACO-VMP(ant colony optimization based virtual mac-hine placement)。在虛擬機放置優(yōu)化過程中涉及的物理資源描述的維度方面，ACO-VMP考慮了物理主機的處理器、內(nèi)存大小、網(wǎng)絡(luò)帶寬等多個因素。與其它的虛擬機放置優(yōu)化算法比較起來，ACO-VMP采用向量代數(shù)的方式描述云數(shù)據(jù)中心的多維的物理資源，綜合考慮整個大數(shù)據(jù)中心的總體能量消耗和多維物理資源的充分利用這2個目標。

1 ACO-VMP虛擬機放置建模

(1)

這里x表示虛擬機v到物理主機p的放置矩陣xi,j， 定義如下：如果第j個虛擬機vj被重新放置到第i個物理主機pi, 則xi,j=1， 否則xi,j=0。 這里也描述了物理主機分配向量y， 如果yi上面至少有一個虛擬機放置，則yi=1， 否則yi=0， 公式如下

(2)

(3)

圖1顯示了ACO-VMP虛擬機放置策略的工作場景。

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

ACO-VMP虛擬機放置優(yōu)化策略的最終的目標如下：

(1)活動物理主機的資源利用效率最大化，而且這種最大化應(yīng)該是在處理器、內(nèi)存、磁盤空間等多個維度的。

(2)物理主機的能量消耗最小化。這也是大部分虛擬機遷移研究的文獻上指出的關(guān)鍵問題，所以這里我們把目標函數(shù)f定義為單一變量的最小化函數(shù)

(4)

(5)

下面的公式可以保證每個虛擬機vj至少可以分配到一個物理主機之上

(6)

2 ACO-VMP相關(guān)術(shù)語描述

2.1 資源的利用效率的啟發(fā)式信息

在虛擬機放置過程中，建立云數(shù)據(jù)中心的物理主機在多個維度的物理資源描述模型及資源利用效率模型是一個關(guān)鍵因素。如果只有一個維度的資源利用效率提高(比如處理器或內(nèi)存大小)而其它維度的資源處于空閑，也不能算是充分利用資源。為了平衡好各個維度的物理資源利用，在ACO-VMP中提出了基于向量代數(shù)的多維資源描述。

在ACO-VMP中認為處理器、內(nèi)存大小與網(wǎng)絡(luò)帶寬都是可用物理資源的一部分，在向量代數(shù)中，資源能力通過一個單元立方體來表示，該立方體有3個方面的維度，分別表示了3個不同類型的物理資源。RCV和RUV分別表示資源提供能力和資源利用效率情況。這里為了獲得整個主機物理資源的利用效率的平衡，定義一個資源平衡向量(resource imbalance vector，RIV)，RIV表示了RCV和RUV之間的關(guān)聯(lián)性。

這里H=(C+M+I)/3。 當放置一個虛擬機到物理主機上時，虛擬機會讓magRIV的取值最小，這樣就可以平衡各個維度的物理資源。magRIV的計算公式如下

(7)

我們把magRIV定義為ACO-VMP優(yōu)化策略中的多維物理資源利用效率的啟發(fā)式信息。

2.2 物理資源利用效率的消耗

(8)

2.3 云數(shù)據(jù)中心的能量消耗

(9)

Eidle和Efull分別表示物理主機在CPU的空閑和滿負載時候的能量消耗，同時也認為在物理主機在關(guān)閉狀態(tài)或睡眠狀態(tài)的能量消耗為0。通過上面的計算，那么整個云數(shù)據(jù)中心的能量消耗為

(10)

3 ACO-VMP的虛擬機放置過程描述

3.1 ACO-VMP自適應(yīng)性

ACO-VMP虛擬機放置優(yōu)化策略參考了蟻群算法的思路，在蟻群算法中假設(shè)有大量的蟻群覓食的行為，在尋找最優(yōu)解的過程中不斷交換一種稱為信息素的參數(shù)。

ACO-VMP具體參考了蟻群算法的后續(xù)改進版本，并且把每個虛擬機-物理主機的映射對(VM-to-PM pairs)作為一個問題解的組成部分。信息素的級別與所有虛擬機-物理主機的映射對都相關(guān)，并且信息素表示了一個期待的最優(yōu)的虛擬機-物理主機的映射方法，例如式(11)和式(12)，這里信息素強度變量為τ0

τ0∶=PEFFDL1Norm

(11)

PEFFDL1Norm可以稱為裝箱的效率，當裝箱效率高的時候，虛擬機的尺寸比較小，也就是說一個物理主機上容納了很多個虛擬機。

τv,p是虛擬機-物理主機映射對中相關(guān)的當前信息素變量

τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(12)

變量δ的含義是全局信息素延遲參數(shù)，0<δ<1， Δτv,p是應(yīng)用到每個虛擬機-物理主機映射對的信息素強度參數(shù)。

在每個虛擬機-物理主機的映射中，這些啟發(fā)式的值被動態(tài)更新，并且考慮到了式(14)中的整個云數(shù)據(jù)中心的多維物理資源的負載均衡與充分利用。

3.2 ACO-VMP算法描述

ACO-VMP優(yōu)化策略的總體算法的偽代碼如下算法1所示：信息素級別的實現(xiàn)通過一個n*m的矩陣的τ來實現(xiàn)，每個螞蟻都通過一個空的尋優(yōu)辦法開始，一組物理主機和一組虛擬機隨機的初始化(代碼第(6)行-第(12)行)。

在循環(huán)的過程中，根據(jù)式(16)中的概率比例規(guī)則，在大量所有可能的虛擬機中，一個螞蟻被隨機選擇出來并允許被選擇一個虛擬機放置其到它當前的物理主機之上(代碼第(11)行-第(22)行)。如果當前的物理主機是充分利用或者沒有更多的物理資源來容納虛擬機，系統(tǒng)將重新啟動一個新的物理主機(代碼第(14)行-第(16)行)。

當所有的螞蟻都已經(jīng)完成對它的路徑尋優(yōu)，即完成局部最優(yōu)解的獲取，循環(huán)中所有的局部最優(yōu)解將與全局最優(yōu)解(global-best-solution，GBS)進行比較，判斷其是否達到式(4)中提到的目標函數(shù)條件，所有的這些局部最優(yōu)解如果能夠使得f的值最小，那么該辦法將作為全局最優(yōu)解(代碼第(23)行-第(28)行)。

信息素強度變量(pheromone reinforcement amount)通過式(19)完成統(tǒng)計，每個虛擬機-物理主機的映射的信息素級別完成更新，經(jīng)過式(18)，它可以模擬信息素的進化和分解過程(代碼第(29)行-第(34)行)。

ACO-VMP優(yōu)化算法中，信息素強度變量值主要體現(xiàn)在虛擬機-物理主機的映射過程中，并且處于全局最優(yōu)解中。接下來，整個搜索新的局部最優(yōu)解的過程不斷重復(fù)，該算法在達到一定的循環(huán)次數(shù)nCycleTerm或者時間后，或者一直沒有更優(yōu)的全局最優(yōu)解出現(xiàn)后結(jié)束(代碼第(35)行)。

算法1： The ACO-VMPAlgorithm.

(1)Input:SetofPMs,setofVMs,setofantsantSet,Setofparameters

(2)Output:Global-best-solutionGBS

(3)Initialize,setpheromonevalueτv,ptoτ0,GBS∶=Φ，;nCycle∶=0

(4)repeat

(5)forallant∈antSetdo

(6)an.solution∶=Φ;ant.pmList∶=p

(7)ant.p∶=1;ant.vmList∶=v

(8)Shuffleant.vmList

(9)endfor

(10)antList∶=antSet;nCycle∶=nCycle+1

(11)whileantList≠Φdo

(12)pickanantatrandomfromantList

(13)ifant.vmList≠Φthen

(14)ifFVant(ant.p)≠Φthen

(15)ant.p∶=ant.p+1

(16)endif

(17)ChooseaVMvfromFVant(ant.p)accord.toEq(15)

(18)ant.solution.xp,v∶=1;ant.vmList.remove(v)

(19)else

(20)ant:solution.f∶=p;antList.remove(ant)

(21)endif

(22)endwhile

(23)forallant∈antSetdo

(24)ifant.solution.f

(25)GBS∶=ant.solution

(26)nCycle∶=0

(27)endif

(28)endfor

(29)ComputeΔτ

(30)forallp∈pdo

(31)forallv∈vdo

(32)τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(33)endfor

(34)endfor

(35)untilnCycle=nCycleTerm

下面詳細分析該算法主要4個階段：

(1)信息素與初始信息素強度變量定義階段:在ACO-VMP算法開始在每個虛擬機-物理主機映射對中，螞蟻按照一個固定的信息素強度變量進行尋優(yōu)，由于ACO-VMP沿用了早期的蟻群優(yōu)化算法，采用一個局部最優(yōu)解的質(zhì)量評價辦法，即強度基礎(chǔ)算法(reference baseline algorithm，RBA)，它也是基于L1均值評測的首次適用遞減算法，RBA用來計算初始化的信息素強度變量τ0。PE稱為裝箱的效率,那么就有

(13)

nVM標識了n個虛擬機，nActivePM表示了n個活動物理主機。裝箱的效率就是所有虛擬機數(shù)和活動物理主機的個數(shù)的比值，裝箱的效率有時候和虛擬機的尺寸密切相關(guān)，當裝箱效率高的時候，虛擬機的尺寸比較小，也就是說一個物理主機上容納了很多個虛擬機。

(2)啟發(fā)式信息定義階段:在全局最優(yōu)解的尋找過程中，啟發(fā)式的參數(shù)值ηv,p表示了局部最優(yōu)解的每個虛擬機-物理主機對的映射質(zhì)量評價情況。

在ACO-VMP算法的一個目標是通過平衡每個箱子中物品的個數(shù)，從而對物理主機進行虛擬機均衡放置，所以這里我們可以定義一個支持多維物理資源充分利用和物理資源平衡使用的參數(shù)ηv,p

ηv,p=w*|log10magRIVp(v)|+(1-w)Utilizationp(v)

(14)

這里magRIVp(v) 表示物理主機p在容納了虛擬機v后的式(7)中提到的多維物理資源利用效率的啟發(fā)式信息。magRIVp(v) 的對數(shù)函數(shù)Log10magRIVp(v) 是為降低magRIVp(v) 函數(shù)的取值范圍。Utilizationp(v)表示物理主機p在容納了虛擬機v后的多維的物理資源利用效率情況

(15)

w表示了權(quán)重，用來平衡多維物理資源利用效率的啟發(fā)式信息和多維的物理資源利用效率。

(3)偽隨機比例規(guī)則:當在構(gòu)造一個局部最優(yōu)解的時候，一個螞蟻k選擇一個虛擬機s放置到物理主機p， 它們采用的是下面的偽隨機比例法則

(16)

q是均勻分布在區(qū)間[0,1]之間的隨機數(shù)，q0是在區(qū)間[0,1]的一個參數(shù)。τv,p是與式(18)中的虛擬機-物理主機映射對相關(guān)的當前信息素變量。β是一個用來確定信息素和啟發(fā)式參數(shù)值的相關(guān)性的一個非負參數(shù)。FVk(p) 定義了蟻群算法中第k個螞蟻分配給物理主機的可能的虛擬機列表

(17)

當q≤q0的時候，虛擬機-物理主機映射對將出現(xiàn)最高的τv,p*[ηv,p]β值并且被選擇出來作為局部最優(yōu)解，否則的話一個虛擬機v將按照下面的隨機比例法則以概率Pk(v,p) 被重新放置

(18)

(4)全局信息素強度變量更新:為了支持局部尋優(yōu)操作，模擬螞蟻信息素的揮發(fā)過程，不斷循環(huán)迭代接近全局最優(yōu)解，在虛擬機-物理主機映射對中，ACO-VMP提出了全局更新規(guī)則來完成信息素強度變量的更新，規(guī)則如下

τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(19)

變量δ的含義是全局信息素延遲參數(shù)， 0<δ<1， Δτv,p是應(yīng)用到每個虛擬機-物理主機映射對的信息素強度參數(shù)， Δτv,p的計算公式如下

(20)

4 仿真實驗與性能分析

4.1 仿真環(huán)境與性能比較對象

參考了Cloudsim3.0工具包，在對應(yīng)的代理中實現(xiàn)了蟻群算法的優(yōu)化的代碼。與ACO-VMP同時做性能比較的虛擬機放置的智能優(yōu)化算法包括下面的：①遺傳算法GA優(yōu)化的虛擬機放置；②粒子群算法PSO優(yōu)化的虛擬機放置；③螢火蟲群算法GSO優(yōu)化的虛擬機放置[12]；④自適應(yīng)的最大最小蟻群算法MMVMC。

被模擬的云數(shù)據(jù)中心物理服務(wù)器總數(shù)為400個，物理服務(wù)器配置見表1：云數(shù)據(jù)中心的虛擬機的設(shè)置見表2。

表1 物理主機的硬件情況

表2 虛擬機的配置條件

表3 蟻群優(yōu)化虛擬機放置算法參數(shù)設(shè)置

實驗中比較了3個主要性能指標：①云數(shù)據(jù)中心的活動物理主機個數(shù)nActivePM； ②獲得的裝箱效率PE； ③云數(shù)據(jù)中心的能量消耗情況Etotal。

4.2 總體能量消耗情況與裝箱效率

經(jīng)過實驗測試，得到了表4的實驗結(jié)果，它顯示了400個物理主機在1000個虛擬機個數(shù)情況下24小時內(nèi)的ACO-VMP蟻群優(yōu)化的虛擬機放置算法與4個優(yōu)化算法的性能比較結(jié)果：

從表4可以看出，ACO-VMP優(yōu)化算法在各個方面都優(yōu)于其它4個算法。ACO-VMP優(yōu)化算法的裝箱效率PE最接近理想值，這也是物理主機負載均衡的一個重要體現(xiàn)，相對于其它智能優(yōu)化算法，ACO-VMP優(yōu)化可以節(jié)省大約10%-20%左右的能量消耗。

表4 各類虛擬機放置優(yōu)化算法的性能比較

但是隨著資源需求參數(shù)的變化(10%-25%)，在比較小(小VM尺寸)的資源需求參數(shù)情況下，ACO-VMP優(yōu)化算法性能超過了MMVMC優(yōu)化算法和GSO算法比例比較大。在比較大的資源需求參數(shù)情況下(大VM尺寸)，ACO-VMP優(yōu)化算法性能超過粒子群優(yōu)化PSO算法的比例比較大。

分析原因是ACO-VMP啟發(fā)式虛擬機放置算法具有很好的靈活度，很容易把虛擬機尺寸比較小的多個虛擬機放置到同一個物理主機上，如果虛擬機尺寸太大，反而效果不明顯。另一方面，在虛擬機尺寸比較大的情況下，螢火蟲群優(yōu)化GSO算法也可以獲得比較高的整體物理資源利用效率，需求的活動物理主機個數(shù)比較少。

4.3 物理資源利用情況比較

表5顯示了ACO-VMP虛擬機放置優(yōu)化算法在1000個虛擬機個數(shù)情況下和其它4個智能優(yōu)化算法的活動物理主機總體資源消耗比例Wastagep結(jié)果。表中實驗結(jié)果表明，ACO-VMP優(yōu)化算法可以很好減少物理資源的消耗的比例，這是因為ACO-VMP同其它4個算法比較起來，一直試圖改善多個維度的物理資源利用效率，在整個4個不同虛擬機尺寸的情況下，所有維度的資源消耗都不超過21%，那么利用率就超過了79%，這樣大部分物理資源都充分利用起來了。

表5 活動物理主機的資源消耗比例性能比較/%

5 結(jié)束語

本文提出了基于蟻群優(yōu)化算法的虛擬機放置方法ACO-VMP。仿真結(jié)果表明，ACO-VMP具有很好的節(jié)能性能與資源利用效率。ACO-VMP可以作為企業(yè)構(gòu)造節(jié)能的綠色大數(shù)據(jù)中心的參考。下一步的工作是將ACO-VMP與其它的更加多的智能優(yōu)化的虛擬機分配策略進行性能比較，調(diào)整蟻群算法中的參數(shù)繼續(xù)提高系統(tǒng)性能。