利用蟻群算法完成虛擬機放置的優化

陳 艷，周天綺，徐勝超

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

0 引 言

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

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

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

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

(4)

(5)

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

(6)

2 ACO-VMP相關術語描述

2.1 資源的利用效率的啟發式信息

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

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

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

(7)

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

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

(8)

2.3 云數據中心的能量消耗

(9)

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

(10)

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

3.1 ACO-VMP自適應性

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

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

τ0∶=PEFFDL1Norm

(11)

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

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

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

(12)

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

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

3.2 ACO-VMP算法描述

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

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

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

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

ACO-VMP優化算法中，信息素強度變量值主要體現在虛擬機-物理主機的映射過程中，并且處于全局最優解中。接下來，整個搜索新的局部最優解的過程不斷重復，該算法在達到一定的循環次數nCycleTerm或者時間后，或者一直沒有更優的全局最優解出現后結束(代碼第(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算法開始在每個虛擬機-物理主機映射對中，螞蟻按照一個固定的信息素強度變量進行尋優，由于ACO-VMP沿用了早期的蟻群優化算法，采用一個局部最優解的質量評價辦法，即強度基礎算法(reference baseline algorithm，RBA)，它也是基于L1均值評測的首次適用遞減算法，RBA用來計算初始化的信息素強度變量τ0。PE稱為裝箱的效率,那么就有

(13)

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

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

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

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

(14)

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

(15)

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

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

(16)

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

(17)

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

(18)

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

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

(19)

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

(20)

4 仿真實驗與性能分析

4.1 仿真環境與性能比較對象

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

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

表1 物理主機的硬件情況

表2 虛擬機的配置條件

表3 蟻群優化虛擬機放置算法參數設置

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

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

經過實驗測試，得到了表4的實驗結果，它顯示了400個物理主機在1000個虛擬機個數情況下24小時內的ACO-VMP蟻群優化的虛擬機放置算法與4個優化算法的性能比較結果：

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

表4 各類虛擬機放置優化算法的性能比較

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

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

4.3 物理資源利用情況比較

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

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

5 結束語

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