一種新的蟻群算法優(yōu)化的虛擬機(jī)放置策略

(廣州華商學(xué)院 數(shù)據(jù)科學(xué)學(xué)院, 廣州 511300)

0 引言

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

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

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

ACA-VMP虛擬機(jī)放置策略考慮了物理主機(jī)的處理器、內(nèi)存大小、網(wǎng)絡(luò)帶寬等多個(gè)資源維度的因素。與其他的虛擬機(jī)放置優(yōu)化的智能算法比較起來，ACA-VMP的目標(biāo)函數(shù)綜合考慮整個(gè)大數(shù)據(jù)中心的總體能量消耗和云服務(wù)器端的服務(wù)質(zhì)量Qos提高等目標(biāo)[18-20]。

1 ACA-VMP建模與工作場景

1.1 虛擬機(jī)放置的問題描述

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

虛擬機(jī)放置問題的含義是尋找一個(gè)最優(yōu)的虛擬機(jī)到物理主機(jī)的映射，就把虛擬機(jī)遷移過程中前一虛擬機(jī)選擇階段的大量的虛擬機(jī)重新分配到大量物理主機(jī)之上，圖1描述了這種在云客戶端訪問大數(shù)據(jù)中心的時(shí)候平臺(tái)的虛擬機(jī)遷移機(jī)制開始工作后的場景。在這種最優(yōu)映射條件下滿足物理主機(jī)的資源利用效率是最高；或者整個(gè)云數(shù)據(jù)中心的能量消耗最?。换蛘呤潜ＷC云數(shù)據(jù)中心的服務(wù)質(zhì)量Qos較好，最好的情況是達(dá)到Pareto最優(yōu)解。

圖1 云數(shù)據(jù)中心虛擬機(jī)放置問題描述

1.2 ACA-VMP的工作場景

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

圖2 ACA-VMP蟻群虛擬機(jī)放置優(yōu)化策略實(shí)現(xiàn)模塊

2 ACA-VMP的虛擬機(jī)放置過程描述

對(duì)于一個(gè)上面容納了多個(gè)虛擬機(jī)的物理主機(jī)，它隨時(shí)都可能成為源主機(jī)Pso。所有的源主機(jī)和源虛擬機(jī)都通過它們自身的物理資源利用效率進(jìn)行描述：比如處理器、內(nèi)存大小、網(wǎng)絡(luò)帶寬大小。類似的每個(gè)虛擬機(jī)都也可能成為潛在的源虛擬機(jī)，根據(jù)它自身的資源利用率情況，每個(gè)物理主機(jī)也可能成為潛在的目標(biāo)物理主機(jī)Pde。所以ACA-VMP優(yōu)化算法給每一次虛擬機(jī)放置動(dòng)作都設(shè)計(jì)了一個(gè)元組，該元組由3個(gè)參數(shù)組成。

T=(pso,v,pde)

(1)

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

(2)

(3)

根據(jù)蟻群覓食尋優(yōu)路徑的分析，ACA-VMP優(yōu)化算法的目標(biāo)函數(shù)是：

(4)

M表示的是整個(gè)虛擬機(jī)遷移過程，Ps表示的是在執(zhí)行虛擬機(jī)遷移過程M后，可以轉(zhuǎn)入睡眠模式的所有物理主機(jī)的集合，根據(jù)|M|，γ是與睡眠數(shù)量Ps的相關(guān)的參數(shù)，它可以設(shè)置為常量。由于最終的目標(biāo)是降低活動(dòng)物理主機(jī)的個(gè)數(shù)，ACA-VMP的目標(biāo)函數(shù)的定義可以根據(jù)睡眠主機(jī)數(shù)|Ps|來確定。

在ACA-VMP優(yōu)化算法快結(jié)束的時(shí)候，它可以通過把虛擬機(jī)遷移到已經(jīng)存在的正常狀態(tài)的活動(dòng)物理主機(jī)上從而降低整個(gè)云數(shù)據(jù)中心的物理主機(jī)數(shù)量，因?yàn)檫@個(gè)時(shí)候睡眠模式的物理主機(jī)可以進(jìn)入關(guān)閉狀態(tài)。這里有一個(gè)新的約束條件：

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

(9)

(10)

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

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

(11)

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

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

(12)

ACA-VMP虛擬機(jī)放置優(yōu)化算法的偽隨機(jī)比例規(guī)則和全局信息素強(qiáng)度變量更新法則的目的都是要使得螞蟻的搜索更加直接，偽隨機(jī)比例規(guī)則更趨向于使虛擬機(jī)-物理主機(jī)元組T能夠獲得更高的信息素級(jí)別和高的啟發(fā)式參數(shù)值。因此，螞蟻就可以在更加鄰近的區(qū)域?qū)ふ宜鼈兊娜肿顑?yōu)解。

另外一個(gè)方面，局部信息素強(qiáng)度參數(shù)更新可以補(bǔ)充螞蟻其他局部最優(yōu)路徑的尋找，這樣也可以使得ACA-VMP虛擬機(jī)放置優(yōu)化算法更快的接近全局最優(yōu)解。這是因?yàn)闊o論何時(shí)蟻群在利用元組尋優(yōu)的過程中，元組將失去它們自己的信息素，同時(shí)對(duì)其他的螞蟻缺少更多的吸引力。因此這樣它就有利于避免對(duì)局部最優(yōu)解的”早熟”的情況。

ACA-VMP虛擬機(jī)放置優(yōu)化算法的偽代碼如下面的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

最后在迭代過程中當(dāng)所有的螞蟻完成它們的路徑尋優(yōu)步驟后，程序?qū)⑥D(zhuǎn)入到MS虛擬機(jī)遷移過程中。每一次循環(huán)，Mk∈MS都要經(jīng)過公式(4)的目標(biāo)函數(shù)進(jìn)行評(píng)估；M+表示了全局最優(yōu)的虛擬機(jī)放置步驟。全局信息素參數(shù)規(guī)則根據(jù)公式(9)和公式(10)完成更新，當(dāng)所有的迭代完成或者運(yùn)行特定的時(shí)間之后結(jié)束，算法將輸出全局最優(yōu)問題解M+。為了描述方便，算法Algorithm1中涉及到的公式與符號(hào)都在表1中詳細(xì)列出。

表1 ACA-VMP虛擬機(jī)放置策略的相關(guān)符號(hào)描述

3 仿真實(shí)驗(yàn)與性能分析

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

因?yàn)锳CA-VMP基于蟻群算法優(yōu)化的虛擬機(jī)放置是在虛擬機(jī)遷移過程中運(yùn)用的，所以進(jìn)行ACA-VMP實(shí)驗(yàn)分析，必須構(gòu)造云數(shù)據(jù)中心的虛擬機(jī)遷移場景，本文參考了Cloudsim3.0工具包，同時(shí)依據(jù)圖2中的功能模塊，實(shí)現(xiàn)了基于Java語言的局部代理，根據(jù)Algorithm1在該代理中實(shí)現(xiàn)了蟻群算法的優(yōu)化的代碼。

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

為了體現(xiàn)蟻群智能優(yōu)化虛擬機(jī)放置策略的高效性與優(yōu)秀性能，與ACA-VMP同時(shí)做性能比較的虛擬機(jī)放置的智能優(yōu)化算法包括如下：

1)遺傳算法GA優(yōu)化的虛擬機(jī)放置[10]；

2)粒子群算法PSO優(yōu)化的虛擬機(jī)放置[12];

3)螢火蟲群算法GSO優(yōu)化的虛擬機(jī)放置[13]；

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

被模擬的云數(shù)據(jù)中心物理服務(wù)器總數(shù)為800個(gè)，物理服務(wù)器配置如表2所顯示。

表2 云數(shù)據(jù)中心物理服務(wù)器硬件配置

虛擬機(jī)遷移周期設(shè)置為10分鐘一次，一共運(yùn)行24個(gè)小時(shí),每次統(tǒng)計(jì)一天內(nèi)的能量消耗,在一周內(nèi)重復(fù)運(yùn)行五次取平均值，一周內(nèi)每天虛擬機(jī)請(qǐng)求的個(gè)數(shù)如表3。

表3 ACA-VMP虛擬機(jī)放置策略測(cè)試環(huán)境

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

這里比較了4個(gè)主要性能指標(biāo)：1)云數(shù)據(jù)中心的能量消耗；2) 裝箱效率；3)虛擬機(jī)遷移次數(shù)；4)云數(shù)據(jù)中心的SLA違規(guī)率；

3.2 仿真結(jié)果與性能分析

3.2.1 云數(shù)據(jù)中心的能量消耗和裝箱效率

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

表4 ACA-VMP虛擬機(jī)放置優(yōu)化策略參數(shù)設(shè)置

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

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

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

3.2.2 虛擬機(jī)遷移次數(shù)和SLA違規(guī)率

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

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

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

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

4 結(jié)束語

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