基于螞蟻群體智能的多目標(biāo)虛擬機合并優(yōu)化

李玉萍 陳麗娜

(商丘師范學(xué)院信息技術(shù)學(xué)院 河南 商丘 476000)

0 引 言

數(shù)據(jù)中心由數(shù)以萬計的物理主機PM組成，這些物理資源會導(dǎo)致大量能耗，不僅會增加運營成本，還會導(dǎo)致巨大的碳排放[1]。同時，數(shù)據(jù)中心的高能耗主要是由資源利用不充分導(dǎo)致的[2]。虛擬化使性能獨立的虛擬機VM可共享同一主機，以改善資源利用率，而虛擬機合并及空閑主機的休眠或低功耗轉(zhuǎn)換則可以進(jìn)一步改善資源利用率和能耗。虛擬機合并是改善數(shù)據(jù)中心能效的最有效方式[3]，利用動態(tài)的虛擬機遷移的合并技術(shù)可以將虛擬機部署于數(shù)量更少的主機上。虛擬機合并主要通過遷移手段實現(xiàn)，在不同主機間的虛擬機遷移可以關(guān)閉閑置主機[4]。虛擬機合并的性能度量指標(biāo)主要包括：釋放的主機數(shù)量(需最大化)、虛擬機遷移次數(shù)(需最小化)以及算法運行時間(需最小化)。虛擬機合并問題本身是NP問題，求解技術(shù)如混合整數(shù)線性規(guī)化方法[5]，但其尋優(yōu)時間達(dá)到指數(shù)級。其次是元啟發(fā)式方法，可在多項式時間復(fù)雜度內(nèi)有效搜索可行解空間。

自適應(yīng)元啟發(fā)式螞蟻群體智能優(yōu)化方法是求解虛擬機合并的有效方法，已有的研究多集中于通過單目標(biāo)單群體的聚合目標(biāo)函數(shù)AOF來聯(lián)立多目標(biāo)[6]，AOF方法的好處在于可以降低時間復(fù)雜度，通過限制可行解的子空間搜索來改善算法運行效率。然而，該方法的不妥之處在于無法準(zhǔn)確地賦予各個目標(biāo)需要考慮的權(quán)重，僅能通過主觀意識賦值。且AOF可能無法以恰當(dāng)?shù)姆绞铰?lián)立優(yōu)化目標(biāo)。已有的螞蟻群體虛擬機合并算法的AOF均未對優(yōu)化目標(biāo)進(jìn)行優(yōu)先關(guān)系排序。

本文設(shè)計了一種最大化主機釋放量且虛擬機遷移量最小的虛擬機遷移方法實現(xiàn)虛擬機合并，其主要貢獻(xiàn)在于：1) 實現(xiàn)了多目標(biāo)多群體優(yōu)化。算法擴(kuò)展已有虛擬機合并單目標(biāo)單群體優(yōu)化思想，實現(xiàn)多目標(biāo)多群體的螞蟻群體優(yōu)化。2) 降低了搜索空間。算法通過設(shè)置約束在未降低解質(zhì)量前提下排除了合并過程中的部分遷移方案，使得算法更快收斂，可擴(kuò)展性增強。

1 相關(guān)工作

螞蟻群體優(yōu)化ACO啟發(fā)式方法受螞蟻覓食行為啟發(fā)，其從食物源至螞蟻巢的食物運輸會跟隨路徑上的信息素這類化學(xué)物質(zhì)進(jìn)行追蹤。該方法允許螞蟻之間直接通信以尋找起始點最優(yōu)的路徑。雖然每個螞蟻可以找到一個可行解，但高質(zhì)量解是來源于間接通信和螞蟻之間的全局協(xié)作得到的結(jié)果。ACO算法的類型包括螞蟻系統(tǒng)AS、螞蟻群體系統(tǒng)ACS以及最大最小螞蟻系統(tǒng)MMAS，其中，ACS是當(dāng)前最優(yōu)的解決方案。已有虛擬機部署和合并研究中，文獻(xiàn)[7]利用ACO解決了非線性資源分配問題，得到受限資源下任務(wù)的最優(yōu)分配。文獻(xiàn)[8]利用改進(jìn)的ACO進(jìn)行多目標(biāo)資源分配求解。文獻(xiàn)[9]利用單目標(biāo)單群體MMAS算法求解虛擬機合并問題。文獻(xiàn)[10]將向量代數(shù)機制整合到ACS中，優(yōu)化了資源利用率。文獻(xiàn)[11-12]設(shè)計了單目標(biāo)單群體ACS算法進(jìn)行虛擬機合并求解。文獻(xiàn)[13]利用多目標(biāo)ACS解決兩個目標(biāo)優(yōu)化問題：能耗最小和資源浪費最小，但方法并沒有進(jìn)行虛擬機遷移，僅在初始部署考慮優(yōu)化目標(biāo)。

已有ACO的虛擬機合并方法與本文算法的不同在于：已有方法趨向于利用AOF的單目標(biāo)單群體ACO算法嘗試聯(lián)立多目標(biāo)，而本文算法直接利用相互獨立的兩個螞蟻群體設(shè)計多目標(biāo)的ACS算法。群體一最大化釋放主機數(shù)量，群體二最小化虛擬機遷移量。并且在解空間的搜索上通過設(shè)計三種約束進(jìn)行了優(yōu)化，極大地降低了最優(yōu)解的搜索時間。

2 多目標(biāo)虛擬機合并螞蟻算法MOACS

2.1 基本說明

本文提出一種多目標(biāo)虛擬機合并螞蟻算法MOACS，算法的第一個目標(biāo)是最大化釋放主機的數(shù)量|PR|，第二個目標(biāo)是最小化虛擬機遷移數(shù)量nM。由于擁有更大主機釋放數(shù)量的全局最優(yōu)遷移方案Φ+總是優(yōu)于較低主機釋放量的遷移方案Φ+的，即使該方案中的虛擬機遷移量大于后一遷移方案，即最大化|PR|優(yōu)先于最小化nM。本文用到的其他相關(guān)符號及說明如表1所示。

表1 符號說明

2.2 算法基本原理

MOACS算法結(jié)構(gòu)如圖1所示，算法通過協(xié)調(diào)兩個不同單目標(biāo)優(yōu)化種群的運行，實現(xiàn)最終雙目標(biāo)的同步優(yōu)化。優(yōu)化主機釋放量通過群體ACS|PR|進(jìn)行優(yōu)化，優(yōu)化虛擬機遷移量通過群體ACSnM進(jìn)行優(yōu)化。兩個群體獨立運行并利用獨立的信息素和啟發(fā)值，但兩個群體會協(xié)作產(chǎn)生全局最優(yōu)遷移方案Φ+。

圖1 算法結(jié)構(gòu)

虛擬機合并中，每個主機p上可寄宿多個虛擬機v。至少寄宿一個虛擬機的主機稱為潛在源主機，主機和虛擬機均具有資源利用率屬性，包括CPU利用率和內(nèi)存利用率。MOACS算法還引入了主機鄰居概念。鄰居表示相互排斥的P的子集。一個鄰居是一個抽象實體，代表數(shù)據(jù)中心中位于鄰近位置的主機集合，那么，數(shù)據(jù)中心的主機可以構(gòu)成主機的一個鄰居。一個虛擬機可被遷移至任意鄰居N的其他主機上。因此，源主機的鄰居內(nèi)的和以外的其他主機也是一個潛在目標(biāo)主機，也具有資源利用率屬性。基于此，MOACS算法建立一個元組集合T，每個元組t∈T由三個元素組成：源主機pso、虛擬機v及目標(biāo)主機pde。

T=(pso,v,pde)

(1)

算法1Multi-objective Ant Colony System-MOACS算法

1. While until a stopping criterion is met do

2.Φ+=?

//全局最優(yōu)遷移解賦空集

10. consolicate VMs according to Φ+and terminate released PM

11. end while

算法1的時間復(fù)雜性分析。算法的計算時間主要取決于元組|T|的數(shù)量，為了降低計算時間，MOACS設(shè)計了三種約束，可通過移除部分元組降低搜索空間。第一重約束確保僅未充分利用的主機可作為源主機，第二重約束僅允許未充分利用主機可作為目標(biāo)主機，即排除從利用充分的主機上遷移和遷移至充分利用的主機上兩種情況，這可以防止已利用充分的主機出現(xiàn)超載。而從利用充分主機上進(jìn)行虛擬機遷移也不可能導(dǎo)致源主機的終止，進(jìn)而不會降低總主機請求數(shù)量。第三重約束通過防止鄰居內(nèi)遷移進(jìn)一步限制|T|的大小。因此，作為通用規(guī)則，一個虛擬機僅能被遷移至其源主機的鄰居內(nèi)的主機上。該規(guī)則唯一例外是一個鄰居僅有一個主機，此時，該主機上的虛擬機可被遷移至任意鄰居的任意主機上。通過這三種規(guī)則的定義與利用，可以在不降低解質(zhì)量的同時極大地縮短算法的計算時間。

算法1的空間復(fù)雜度分析。MOACS算法空間復(fù)雜度為O(|T|)。而且，最差空間復(fù)雜度對應(yīng)于具體的虛擬機合并場景，與主機的利用程度無關(guān)。此時，每個主機可視為一個目標(biāo)主機。最差情況下元組的最大數(shù)量計算為：

max|T|=|P||V|(|N|-1)

(2)

式中：|P|為主機數(shù)量，|V|為虛擬機數(shù)量，|N|為鄰居大小。由于實際的虛擬機合并場景中通常包括一個或多個充分利用的主機，而所提算法可以排除從該類主機進(jìn)行的遷移，故元組數(shù)量|T|通常小于最差場景中的數(shù)量。

2.3 基于PM釋放量最大化的優(yōu)化算法ACS|PR|

ACS|PR|的目標(biāo)是優(yōu)化主機釋放量|PR|，即算法目標(biāo)函數(shù)為：

maxf(Φ)=|PR|

(3)

由于虛擬機合并的首要目標(biāo)是最小化活動主機的數(shù)量，目標(biāo)函數(shù)的定義將根據(jù)主機釋放量進(jìn)行定義。且當(dāng)執(zhí)行遷移方案時，將利用一種約束，通過將遷移限制在僅為釋放主機PR集合以外的主機上，以降低虛擬機遷移量nM，即：

pde∈P|pde?PR

(4)

算法中，當(dāng)其上的所有虛擬機被遷移后，該主機才視為已釋放主機。因此，釋放主機集合PR可定義為：

PR={p∈P|Vp=?}

(5)

式中：Vp表示運行于主機p上的虛擬機集合。因此，當(dāng)不再寄宿任意虛擬機時，一個主機僅包含于釋放主機集合PR中。

虛擬機合并問題中，螞蟻根據(jù)式(1)定義的元組存放信息素。nA個螞蟻中的任一螞蟻利用隨機狀態(tài)轉(zhuǎn)換規(guī)則選擇可穿過的下一個元組，ACS|PR|中的狀態(tài)轉(zhuǎn)換規(guī)則即為偽隨機比例規(guī)則。根據(jù)該規(guī)則，螞蟻k選擇下一元組的規(guī)則為：

式中：argmax返回[τ][η]β得到其最大值的元組，q∈[0,1]為均勻分布隨機變量，q0∈[0,1]為一個參數(shù)，S為根據(jù)式(7)的概率分布選擇的隨機變量，螞蟻k選擇元組s穿越的概率probs定義為：

(7)

元組s的啟發(fā)值ηs定義為：

可知，擁有最小未利用能力的目標(biāo)主機將獲得最高啟發(fā)值。因此，啟發(fā)值偏向于導(dǎo)致主機利用不足降低的虛擬機遷移，而Upde+Uv≤Cpde可防止虛擬機遷移帶來目標(biāo)主機pde的超載。

式(6)和式(7)中的隨機狀態(tài)轉(zhuǎn)換規(guī)則偏向于選擇擁有更高信息素濃度的元組。式(6)中q≤q0的第一種情況選擇能夠得到[τ][η]β最大值的元組，而第二種情況則根據(jù)式(7)選擇元組。第一種情況有助于螞蟻快速的收斂于高質(zhì)量解，而第二種情況則有助于螞蟻通過基于寬度的搜索空間拓展避免螞蟻的搜索停滯。除了隨機狀態(tài)轉(zhuǎn)換規(guī)則，ACS|PR|還利用了全局和局部信息素蹤跡蒸發(fā)規(guī)則。全局信息素蹤跡蒸發(fā)規(guī)則利用于所有螞蟻完成其遷移的一次迭代的結(jié)束時，定義為：

局部信息素蹤跡更新規(guī)則應(yīng)用于當(dāng)螞蟻穿越該元組做出自身的遷移方案時的元組，定義為：

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

(11)

式中：ρ∈(0,1]類似于α，τ0表示初始信息素，計算為主機數(shù)量|P|與近似最優(yōu)解|Φ|的乘積的逆值，即：

τ0=(|Φ|·|P|)-1

(12)

ACS|PR|中偽隨機比例規(guī)則和全局信息素蹤跡更新規(guī)則可以使搜索更有指向性，偽隨機比例規(guī)則偏向于選擇更高信息素和更高啟發(fā)值的元組，因此，螞蟻可以在迄今全局最優(yōu)解的極鄰近區(qū)域搜索高質(zhì)量解。此外，局部信息素蹤跡更新規(guī)則可補充搜索與全局最優(yōu)解相距較遠(yuǎn)區(qū)域中的其他高質(zhì)量解。這是由于無論何時螞蟻穿越一個元組，應(yīng)用局部信息素更新規(guī)則，元組信息素均會損耗，對于其他螞蟻的吸引會變差。因此，這有助于避免所有螞蟻停滯于搜索相同解或過早收斂于子最優(yōu)解。

算法2ACS|PR|算法

2.t∈T|τt=τ0

//元組信息素初始化

3. fori∈[1,nI] do

4. fork∈[1,nA] do

7. computeprobsby using (7)

//計算螞蟻的穿越概率

8. choose a tuplet∈Tto traverse by using (6)

10. apply local update rule in (11) ont

//更新元組

11. if the migration intdoes not overload destination PMpdethen

//元組的遷移未導(dǎo)致主機超載

12. update used capacity vectorsUpsoandUpdeint

15.Φk=Φk∪{t}

//更新螞蟻k的遷移方案

16.M=M∪{Φk}

18. apply global update rule in (9) on alls∈T

//更新所有元組

算法2的時間復(fù)雜度分析。ACS|PR|的時間復(fù)雜度為O(nI×|T|2)，nI表示螞蟻代數(shù)，|T|表示元組數(shù)量。從算法2可知，步驟3的主循環(huán)需要迭代nI次，步驟4的第二重循環(huán)并不會增加時間復(fù)雜度，由于螞蟻會同步建立其遷移方案。步驟5的循環(huán)需要迭代|T|次，步驟7的概率計算需要在|T|上進(jìn)行迭代。綜上可得算法的時間復(fù)雜度為O(nI×|T|2)。

2.4 基于VM遷移量最小化的優(yōu)化算法ACSnM

ACSnM的目標(biāo)尋找虛擬機遷移量更少且至少與Φ+中主機釋放量PR相當(dāng)?shù)倪w移方案，即算法目標(biāo)函數(shù)為：

maxg(Φ)=(nM)-1

(13)

由于虛擬機遷移是資源密集型操作，ACSnM的目標(biāo)函數(shù)可定義為遷移量的逆值。

ACSnM中的螞蟻同樣利用式(6)和式(7)的偽隨機比例規(guī)則選擇需穿越的下一元組。且式(8)中的啟發(fā)值更偏向于擁有更多的已利用能力向量的虛擬機Uv。這樣，更可能導(dǎo)致虛擬機遷移量降低的虛擬機遷移操作將得到更高的啟發(fā)值。因此，式(8)中的啟發(fā)值支持ACSnM中式(13)定義的目標(biāo)函數(shù)。

ACSnM群體同樣利用式(11)中的局部信息素蹤跡更新規(guī)則，然而，全局信息素蹤跡更新規(guī)則需要重新定義為：

算法3ACSnM算法

2.t∈T|τt=τ0

//元組信息素初始化

3. fori∈[1,nI] do

4. fork∈[1,nA] do

7. computeprobsby using (7)

//計算螞蟻的穿越概率

8. choose a tuplet∈Tto traverse by using(6)

10. apply local update rule in (11) ont//更新元組

11. if the migration in t does not overload destination PMpdethen

//元組的遷移未導(dǎo)致主機超載

12. update used capacity vectorsUpsoandUpdeint

15.Φk=Φk∪{t}

//更新螞蟻k的遷移方案

16.M=M∪{Φk}

//基于式(13)得到全局最優(yōu)方案

18. apply global update rule in (14) on alls∈T

//更新所有元組

算法3的時間復(fù)雜度分析。ACSnM的時間復(fù)雜度與ACS|PR|相似，由于ACSnM與ACS|PR|兩個群體均是同步且獨立運行。

3 仿真實驗

3.1 實驗說明

本節(jié)測試MOACS的性能，對比算法選取同為蟻群系統(tǒng)的優(yōu)化，包括單目標(biāo)單群體的虛擬機合并算法Feller-ACO[9]及ACS[8]算法。虛擬機合并的輸入?yún)?shù)包括：主機數(shù)量、合并虛擬機的數(shù)量、虛擬機的CPU利用率、虛擬機的內(nèi)存需求以及每個虛擬機的當(dāng)前位置。為了觀察算法可擴(kuò)展性和適應(yīng)性，在主機上建立四種不同場景測試：1) 低CPU低內(nèi)存請求；2) 高CPU大內(nèi)存請求；3) 高CPU小內(nèi)存請求；4) 低CPU大內(nèi)存請求。實驗利用隨機負(fù)載、同質(zhì)虛擬機和同質(zhì)主機進(jìn)行測試。實驗參數(shù)見表2和表3。對于場景1)，合并的虛擬機數(shù)量設(shè)置為1 000，主機數(shù)量為100，比例為10∶1，其他三種場景設(shè)置1 000個虛擬機和200個主機，比例為5∶1。鄰居規(guī)模設(shè)置為5，鄰居隨機選擇。表3是與蟻群智能優(yōu)化過程相關(guān)的參數(shù)設(shè)置。實驗中需要考慮的指標(biāo)包括：合并后最大化的釋放主機數(shù)量、包裝效率(釋放的主機數(shù)量與總主機數(shù)量的比值)、合并后最小化的虛擬機遷移量以及算法的求解時間。

表2 場景設(shè)計

表3 螞蟻群體參數(shù)設(shè)置

3.2 實驗結(jié)果

1) 釋放主機量與包裝效率。

圖2是算法在不同實驗下得到的釋放主機數(shù)量的箱形圖，表4是相應(yīng)的數(shù)值結(jié)果，包括包裝效率。結(jié)果表明，MOACS算法可以比Feller-ACO多釋放25%～37%的主機。在場景1中，MOACS釋放了15個主機(10次測試的中位值)，而Feller-ACO僅釋放11個主機。由于包裝效率需由釋放主機量推導(dǎo)，該指標(biāo)也具有類似的趨勢。

圖2 釋放主機數(shù)量

場景參數(shù)ACSMOACSFeller-ACOChangep-value1中位值91511136%0.005標(biāo)準(zhǔn)差0.630.520.82--包裝效率9%15%11%--2中位值7118137%0.005標(biāo)準(zhǔn)差0.670.670.99--包裝效率3.5%5.5%4%--3中位值7108125%0.004標(biāo)準(zhǔn)差0.670.520.82--包裝效率3.5%5%4%--4中位值7118137%0.005標(biāo)準(zhǔn)差0.880.880.74--包裝效率3.5%5.5%4%--

2) VM遷移量。

圖3是算法得到虛擬機遷移量結(jié)果，表5同步給出數(shù)值結(jié)果?？梢钥闯?，MOACS在此目標(biāo)上也是優(yōu)于Feller-ACO的，MOACS僅利用Feller-ACO 虛擬機遷移量的82%即可得到更好的包裝效率。在場景1中，MOACS擁有189次虛擬機遷移，而Feller-ACO擁有226次遷移。

圖3 虛擬機遷移量

場景參數(shù)ACSMOACSFeller-ACOChangep-value1中位值91511136%0.005標(biāo)準(zhǔn)差0.630.520.82--包裝效率9%15%11%--2中位值7118137%0.005標(biāo)準(zhǔn)差0.670.670.99--包裝效率3.5%5.5%4%--3中位值7108125%0.004標(biāo)準(zhǔn)差0.670.520.82--包裝效率3.5%5%4%--4中位值7118137%0.005標(biāo)準(zhǔn)差0.880.880.74--包裝效率3.5%5.5%4%--

3) 執(zhí)行時間與可擴(kuò)展性。

該指標(biāo)度量算法搜索全局最優(yōu)解的執(zhí)行時間。圖4是基于場景2三種算法得到的結(jié)果，此時設(shè)置的主機數(shù)量由50至500以步長50遞增，虛擬機數(shù)量由250至2 500以步長250遞增?？梢钥闯?，MOACS優(yōu)于Feller-ACO，而ACS是優(yōu)于MOACS的，由于其僅是單目標(biāo)優(yōu)化，搜索時間更短，而MOACS需要在兩個目標(biāo)上進(jìn)行搜索。

圖4 算法運行時間

進(jìn)一步，實驗在場景1下利用|P|=1 000和|V|=1 000進(jìn)行了比較分析，如表6所示。該場景下，ACS得到的時間多少1分鐘，比較而言，MOACS幾乎運行2分種，而Feller-ACO需要6分種。同時還觀察到，時間變量的標(biāo)準(zhǔn)差均是較小的，前兩種算法的時間差則差別較大。

表6 場景1下的算法執(zhí)行時間

4) 結(jié)論分析。

總體來看，MOACS在所有測試指標(biāo)下均優(yōu)于Feller-ACO，包括釋放的主機量、包裝效率以及虛擬機遷移量和執(zhí)行時間。Feller-ACO利用單目標(biāo)單群體下AOF，聯(lián)合了兩種不同的目標(biāo)，包括釋放主機量和虛擬機遷移量，MOACS利用多目標(biāo)算法，考慮的是兩個獨立的螞蟻群體分別進(jìn)行優(yōu)化。Feller-ACO中的AOF利用多個參數(shù)決定全局優(yōu)化過程兩個目標(biāo)的相對重要性，該方法的不足在于：1) 無法準(zhǔn)確找到AOF中合適的參數(shù)值；2) AOF可能無法做到不同目標(biāo)間的合理聯(lián)立。例如：MOACS中最大化釋放主機量是占優(yōu)于最小化虛擬機遷移量的，而Feller-ACO中的AOF不支持目標(biāo)間的占優(yōu)關(guān)系。此外，MOACS采用了搜索空間的約束機制(三種約束)，可以極大地降低算法的運行時間，且不會影響到解的質(zhì)量。同時，MOACS與ACS相比，擁有更多的主機釋放量和更少的虛擬機遷移量，但其運行較ACS更慢。比較ACS與Feller-ACO，ACS更慢且虛擬機遷移量更少，盡管該算法沒有實現(xiàn)相同的包裝效率。

4 結(jié) 語

本文提出了一種新的多目標(biāo)螞蟻群體算法進(jìn)行數(shù)據(jù)中心的虛擬機合并，算法可以建立虛擬機遷移方案，通過利用不充分的主機上的虛擬機遷移和合并降低物理主機的請求量。在此過程中，目標(biāo)函數(shù)設(shè)置為最大化主機釋放量與最小化虛擬機遷移量。以大量的實驗對算法進(jìn)行了驗證，并與兩種已有的螞蟻優(yōu)化算法作對比，所提算法在多種實驗場景下的性能均是較優(yōu)的。進(jìn)一步研究算法實際的能效，本文僅從優(yōu)化主機使用數(shù)量與虛擬機遷移次數(shù)上著手優(yōu)化虛擬機合并，但虛擬機的具體部署結(jié)果也會對能效產(chǎn)生影響，此時需要計算具體的部署時的能效問題，然后再設(shè)計能效更高的部署算法。