陳 艷，周天綺，徐勝超

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

0 引 言

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

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

1 ACO-VMP虛擬機(jī)放置建模

(1)

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

(2)

(3)

圖1顯示了ACO-VMP虛擬機(jī)放置策略的工作場(chǎng)景。

圖1 ACO-VMP虛擬機(jī)放置策略的工作場(chǎng)景

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

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

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

(4)

(5)

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

(6)

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

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

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

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

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

(7)

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

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

(8)

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

(9)

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

(10)

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

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

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

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

τ0∶=PEFFDL1Norm

(11)

PEFFDL1Norm可以稱為裝箱的效率，當(dāng)裝箱效率高的時(shí)候，虛擬機(jī)的尺寸比較小，也就是說一個(gè)物理主機(jī)上容納了很多個(gè)虛擬機(jī)。

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

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

(12)

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

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

3.2 ACO-VMP算法描述

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

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

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

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

ACO-VMP優(yōu)化算法中，信息素強(qiáng)度變量值主要體現(xiàn)在虛擬機(jī)-物理主機(jī)的映射過程中，并且處于全局最優(yōu)解中。接下來，整個(gè)搜索新的局部最優(yōu)解的過程不斷重復(fù)，該算法在達(dá)到一定的循環(huán)次數(shù)nCycleTerm或者時(shí)間后，或者一直沒有更優(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

下面詳細(xì)分析該算法主要4個(gè)階段：

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

(13)

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

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

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

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

(14)

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

(15)

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

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

(16)

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

(17)

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

(18)

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

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

(19)

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

(20)

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

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

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

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

表1 物理主機(jī)的硬件情況

表2 虛擬機(jī)的配置條件

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

實(shí)驗(yàn)中比較了3個(gè)主要性能指標(biāo)：①云數(shù)據(jù)中心的活動(dòng)物理主機(jī)個(gè)數(shù)nActivePM； ②獲得的裝箱效率PE； ③云數(shù)據(jù)中心的能量消耗情況Etotal。

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

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

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

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

4.3 物理資源利用情況比較

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

表5 活動(dòng)物理主機(jī)的資源消耗比例性能比較/%

5 結(jié)束語

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