一種新的蟻群算法優化的虛擬機放置策略

(廣州華商學院 數據科學學院, 廣州 511300)

0 引言

大數據中心的構造與建設是近年來政府與云服務提供商越來越關注的問題，為了節省企業成本，這類數據中心的構造主要目標是綠色節能與物理資源的充分利用[1]。為了達到這2個目標，云計算中大多都使用了虛擬機遷移技術[2-3]。目前以Cloudsim云模擬器工具包及其研究思路為背景的大部分文獻在虛擬機遷移研究方面處理世界領先地位，它將虛擬機遷移過程劃分為物理主機狀態檢測、虛擬機選擇、虛擬機放置3個步驟[4]，這3個步驟既具有獨立性又互相關聯，而且都可以通過算法進行優化[5-8]。

本文著重考慮采用智能算法的方式來優化虛擬機放置過程。虛擬機放置有些文獻把它稱為多目標優化問題或者裝箱問題[9]，該過程有很多智能算法進行優化，例如遺傳算法[10]、貪心算法[11]、粒子群優化算法[12]、螢火蟲群優化算法[13]、蛙跳算法[14]等。本文依托于Cloudsim云平臺工具包，在物理主機狀態檢測和虛擬機選擇過程都采用Cloudsim中默認的優化策略；然后著重考慮采用蟻群算法的方式來優化虛擬機放置過程[15]。提出一種新型蟻群算法優化的虛擬機放置方法ACA-VMP。

ACA-VMP虛擬機放置優化策略參考了蟻群算法的思路，在自適應的蟻群算法中假設有大量的蟻群覓食的行為，在尋找最優解的過程中不斷的交換一種稱為信息素強度的參數，這樣在一定程度上可以避免多目標優化算法中的局部最優解的“早熟”問題[16-17]。

ACA-VMP虛擬機放置策略考慮了物理主機的處理器、內存大小、網絡帶寬等多個資源維度的因素。與其他的虛擬機放置優化的智能算法比較起來，ACA-VMP的目標函數綜合考慮整個大數據中心的總體能量消耗和云服務器端的服務質量Qos提高等目標[18-20]。

1 ACA-VMP建模與工作場景

1.1 虛擬機放置的問題描述

物理主機的描述向量如下：Pj=(idj,cpuj,memj,networkj)，M表示了物理主機的標識符，cpuj表示了物理主機的處理器的計算能力，有時候也用(Millions of Instructions Per Second, MIPS)來表示，memj表示了物理主機的可用內存大小，networkj表示了物理主機所擁有的網絡帶寬大小，每個虛擬機也可以通過下面的向量來表示：Vi=(idi,cpui,memi,networki)，idi表示了虛擬機的標識符，cpui表示了虛擬機的表示了對處理器的需求能力，memi表示了虛擬機對內存的需求能力，networki表示了虛擬機對網絡帶寬的需求能力。

虛擬機放置問題的含義是尋找一個最優的虛擬機到物理主機的映射，就把虛擬機遷移過程中前一虛擬機選擇階段的大量的虛擬機重新分配到大量物理主機之上，圖1描述了這種在云客戶端訪問大數據中心的時候平臺的虛擬機遷移機制開始工作后的場景。在這種最優映射條件下滿足物理主機的資源利用效率是最高；或者整個云數據中心的能量消耗最小；或者是保證云數據中心的服務質量Qos較好，最好的情況是達到Pareto最優解。

圖1 云數據中心虛擬機放置問題描述

1.2 ACA-VMP的工作場景

ACA-VMP依托了Cloudsim模擬器工具包，該工具包在運行模塊中主要包括：全局代理Global Broker、本地代理Local Broker、虛擬機管理器Virtual Machine Manager[5]。

圖2 ACA-VMP蟻群虛擬機放置優化策略實現模塊

2 ACA-VMP的虛擬機放置過程描述

對于一個上面容納了多個虛擬機的物理主機，它隨時都可能成為源主機Pso。所有的源主機和源虛擬機都通過它們自身的物理資源利用效率進行描述：比如處理器、內存大小、網絡帶寬大小。類似的每個虛擬機都也可能成為潛在的源虛擬機，根據它自身的資源利用率情況，每個物理主機也可能成為潛在的目標物理主機Pde。所以ACA-VMP優化算法給每一次虛擬機放置動作都設計了一個元組，該元組由3個參數組成。

T=(pso,v,pde)

(1)

由于虛擬機放置這里元組可以類似于分布式旅行商問題中的連接各個城市的邊。為了降低ACA-VMP優化算法的運行時間，必須降低的|T|值。所以在構造元組的時候，必須注意兩個約束條件為真：

(2)

(3)

根據蟻群覓食尋優路徑的分析，ACA-VMP優化算法的目標函數是：

(4)

M表示的是整個虛擬機遷移過程，Ps表示的是在執行虛擬機遷移過程M后，可以轉入睡眠模式的所有物理主機的集合，根據|M|，γ是與睡眠數量Ps的相關的參數，它可以設置為常量。由于最終的目標是降低活動物理主機的個數，ACA-VMP的目標函數的定義可以根據睡眠主機數|Ps|來確定。

在ACA-VMP優化算法快結束的時候，它可以通過把虛擬機遷移到已經存在的正常狀態的活動物理主機上從而降低整個云數據中心的物理主機數量，因為這個時候睡眠模式的物理主機可以進入關閉狀態。這里有一個新的約束條件：

Ps={?p∈P|Vp=φ}

(5)

該條件可以保證當所有的虛擬機都被遷移出去之后，物理主機將被切換到睡眠模式。

ACA-VMP算法中蟻群的信息素被分解成元組。每個螞蟻使用一個狀態比例規則完成對下一個元組的選擇，該原則在蟻群算法中稱為偽隨機比例規則。蟻群算法中根據這個規則，第k個螞蟻根據下面的公式選擇一個元組：

(6)

q是均勻分布在區間[0,1]之間的隨機數，q0是在區間[0,1]的一個參數。τ描述了信息素變量，η是與元組T=(pso,v,pde)相關的當前啟發式參數值。β是一個用來確定信息素變量和啟發式參數值的相關性的一個非負參數。Tk?T表示了經過了第k螞蟻路徑尋優之后的剩余的元組的集合。S是一個根據公式(6)的概率分布來確定的隨機變量。第k個螞蟻選擇元組s的概率表示為ps，它可以通過公式(7)來計算：

(7)

一個元組的啟發式參數值ηs可以根據蟻群算法[21-22]中的規則定義如下公式(8)：

(8)

Cpde表示了目標物理主機的整體資源提供能力；Upde表示了目標物理主機的整體資源利用效率；Uv表示了元組s上的虛擬機的利用效率；這里ηs是一個多維物理資源利用效率向量，它支持通過虛擬機遷移的方式完成低負載物理主機數量的降低。Upde+Uv≤Cp de這個約束條件可以避免虛擬機遷移之后目標物理主機的超負載。ACA-VMP優化算法中包括3個維度的物理資源：處理器、內存大小和網絡帶寬大小，根據螞蟻群算法的公式(6)和公式(7)的條件完成優化之后，基本可以保證高信息素變量的集中和大量的物理主機資源釋放。

在公式(7)中，指數函數有利于局部最優路徑的快速收斂，保證了一個廣泛的搜索路徑。根據經典的蟻群優化算法，ACA-VMP采用了全局最優解和局部信息素更新規則，全局最優解采用更新規則，經過多次迭代后，螞蟻路徑的多次尋優，保證這個虛擬機放置優化策略的完成。信息素強度變量的更新規則如下：

(9)

(10)

變量α的含義是全局信息素延遲參數，0<α<1，M+表示了蟻群算法的虛擬機放置全局最優解。局部最優解也采用更新規則，規則如下：

τs=(1-ρ)*τs+ρ*τ0

(11)

變量ρ的含義是全局信息素參數α類似的參數，0<ρ<1，τ0是初始信息素級別變量，計算的公式如下：

τ0=(|M|*|P|)-1

(12)

ACA-VMP虛擬機放置優化算法的偽隨機比例規則和全局信息素強度變量更新法則的目的都是要使得螞蟻的搜索更加直接，偽隨機比例規則更趨向于使虛擬機-物理主機元組T能夠獲得更高的信息素級別和高的啟發式參數值。因此，螞蟻就可以在更加鄰近的區域尋找它們的全局最優解。

另外一個方面，局部信息素強度參數更新可以補充螞蟻其他局部最優路徑的尋找，這樣也可以使得ACA-VMP虛擬機放置優化算法更快的接近全局最優解。這是因為無論何時蟻群在利用元組尋優的過程中，元組將失去它們自己的信息素，同時對其他的螞蟻缺少更多的吸引力。因此這樣它就有利于避免對局部最優解的”早熟”的情況。

ACA-VMP虛擬機放置優化算法的偽代碼如下面的Algorithm1所示:

Algorithm 1 ACA-based VM placement

1:M+=φ,MS=φ

2: ?t∈T|τt=τ0

3: fori∈[1,nI] do

4: fork∈[1,nA] do

6: fort∈Tdo

7: generate a random variableqwith a uniform

Distribution between 0 and l

8: ifq>q0then

9: computeps?s∈T by using (7)

10: end if

11: choose a tuplet∈Tkto traverse by using (6)

13: apply local update rule in (11) ont

14: update used capacity vectorsUpsoandUpdeint

17:Mk=Mk∪{t}

18: else

20: end if

21: end for

22:MS=MS∪{Mk}

23: end for

24:M+=argmaxMk∈MS{f(Mk)}

25: apply global update rule in (9) on alls∈T

26: end for

最后在迭代過程中當所有的螞蟻完成它們的路徑尋優步驟后，程序將轉入到MS虛擬機遷移過程中。每一次循環，Mk∈MS都要經過公式(4)的目標函數進行評估；M+表示了全局最優的虛擬機放置步驟。全局信息素參數規則根據公式(9)和公式(10)完成更新，當所有的迭代完成或者運行特定的時間之后結束，算法將輸出全局最優問題解M+。為了描述方便，算法Algorithm1中涉及到的公式與符號都在表1中詳細列出。

表1 ACA-VMP虛擬機放置策略的相關符號描述

3 仿真實驗與性能分析

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

因為ACA-VMP基于蟻群算法優化的虛擬機放置是在虛擬機遷移過程中運用的，所以進行ACA-VMP實驗分析，必須構造云數據中心的虛擬機遷移場景，本文參考了Cloudsim3.0工具包，同時依據圖2中的功能模塊，實現了基于Java語言的局部代理，根據Algorithm1在該代理中實現了蟻群算法的優化的代碼。

ACA-VMP依托于Cloudsim云平臺工具，在物理主機狀態檢測和虛擬機選擇過程都采用Cloudsim中默認的優化策略:魯棒局部回歸物理主機狀態檢測(local regression robust, LRR)策略和最短時間虛擬機選擇策略(minimum migration time，MMT)；

為了體現蟻群智能優化虛擬機放置策略的高效性與優秀性能，與ACA-VMP同時做性能比較的虛擬機放置的智能優化算法包括如下：

1)遺傳算法GA優化的虛擬機放置[10]；

2)粒子群算法PSO優化的虛擬機放置[12];

3)螢火蟲群算法GSO優化的虛擬機放置[13]；

4)自適應的最大最小蟻群算法MMVMC[24]；

被模擬的云數據中心物理服務器總數為800個，物理服務器配置如表2所顯示。

表2 云數據中心物理服務器硬件配置

虛擬機遷移周期設置為10分鐘一次，一共運行24個小時,每次統計一天內的能量消耗,在一周內重復運行五次取平均值，一周內每天虛擬機請求的個數如表3。

表3 ACA-VMP虛擬機放置策略測試環境

虛擬機的放置中有一個裝箱效率的概念[19]，可以認為是虛擬機粒度，我們設置為至少4個，一共4個類型，裝箱效率分別為10，6.75，5，4，這樣設置的原因是為了體現云平臺有不同資源需求大小尺寸的虛擬機來訪問云數據中心。例如裝箱效率如果為10，這樣說明這個虛擬機尺寸比較小，一個物理主機上最多可以容納10個虛擬機，那么最理想裝箱效率就為10。ACA-VMP蟻群算法的其他參數初始化設置如表4。

這里比較了4個主要性能指標：1)云數據中心的能量消耗；2) 裝箱效率；3)虛擬機遷移次數；4)云數據中心的SLA違規率；

3.2 仿真結果與性能分析

3.2.1 云數據中心的能量消耗和裝箱效率

為了實驗測試的需要，表5顯示了在1 000個虛擬機個數情況下ACA-VMP蟻群優化的虛擬機放置算法與4個優化算法的能量消耗、裝箱效率的性能比較結果：從表5可以但是隨著虛擬機粒度參數的變化，在比較小(粒度為10和6.75)的資源需求參數情況下，ACA-VMP優化算法優化的性能超過MMVMC優化算法和GSO算法，性能提高比例比較大。在比較大的資源需求參數情況下(粒度為5和4)，ACA-VMP優化算法性能超過粒子群優化PSO算法的比例比較大。

表4 ACA-VMP虛擬機放置優化策略參數設置

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

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

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

3.2.2 虛擬機遷移次數和SLA違規率

表6顯示了在4種虛擬機粒度下ACA-VMP的虛擬機優化策略的遷移次數低于PSO策略、GSO遷移策略、MMVMC策略，隨著粒度的增強，虛擬機遷移次數逐漸減少；而遺傳算法GA優化的策略虛擬機遷移次數在某些條件下還要小于ACA-VMP策略。

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

原因是ACA-VMP策略中設計的能量消耗模型考慮問題的維度比較廣泛，包括處理器、內存、磁盤和網絡帶寬，局部和全局的信息素強度更新變量可以使得虛擬機放置過程不斷優化，提高了資源的利用效率，使得負載比較均勻的放置在各個活動物理主機之上，遷移次數降低。但是在這個過程中也不一定是最優的，ACA-VMP優化策略立足于能量消耗最小而不是立足于遷移次數最小，所以遺傳算法GA的遷移次數少于ACA-VMP優化策略也是可以接受的。

當一個云客戶端提交作業到云計算平臺的時候，如果云平臺沒有提供合適的物理資源，就會出現服務等級協議(Service Level Agreement,SLA)違規。從表6可以看出，不同虛擬機粒度條件下，ACA-VMP優化策略的SLA違規率比PSO優化策略、GSO優化策略、MMVMC策略要低，隨著粒度的增強，SLA違規率逐漸減少；有這樣的實驗結果的原因是ACA-VMP中的各類資源約束條件在物理主機狀態檢測階段盡量避免物理資源使用率超過100%的情況，從而間接的避免SLA違規事情的發生。大粒度虛擬機訪問一次需要穩定的資源，云服務器虛擬機遷移次數少，SLA違規率自然降低。

4 結束語

本文采用蟻群優化啟發式智能算法，針對云數據中心的綠色節能和高服務質量兩個目標，提出了一種新的蟻群算法優化的虛擬機放置方法ACA-VMP。實驗結果表明和常見的智能優化的虛擬機放置策略比較起來， ACA-VMP在總體能量消耗、裝箱效率、虛擬機遷移次數，SLA違規率等方面性能較好。ACA-VMP 策略的目前只是在虛擬機放置階段，它還可以和虛擬機選擇階段的優化策略結合起來使用，這個是本文的后續工作。