李玉萍 陳麗娜

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

2.1 基本說明

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

表1 符號(hào)說明

2.2 算法基本原理

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

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

虛擬機(jī)合并中，每個(gè)主機(jī)p上可寄宿多個(gè)虛擬機(jī)v。至少寄宿一個(gè)虛擬機(jī)的主機(jī)稱為潛在源主機(jī)，主機(jī)和虛擬機(jī)均具有資源利用率屬性，包括CPU利用率和內(nèi)存利用率。MOACS算法還引入了主機(jī)鄰居概念。鄰居表示相互排斥的P的子集。一個(gè)鄰居是一個(gè)抽象實(shí)體，代表數(shù)據(jù)中心中位于鄰近位置的主機(jī)集合，那么，數(shù)據(jù)中心的主機(jī)可以構(gòu)成主機(jī)的一個(gè)鄰居。一個(gè)虛擬機(jī)可被遷移至任意鄰居N的其他主機(jī)上。因此，源主機(jī)的鄰居內(nèi)的和以外的其他主機(jī)也是一個(gè)潛在目標(biāo)主機(jī)，也具有資源利用率屬性?；诖?，MOACS算法建立一個(gè)元組集合T，每個(gè)元組t∈T由三個(gè)元素組成：源主機(jī)pso、虛擬機(jī)v及目標(biāo)主機(jī)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的時(shí)間復(fù)雜性分析。算法的計(jì)算時(shí)間主要取決于元組|T|的數(shù)量，為了降低計(jì)算時(shí)間，MOACS設(shè)計(jì)了三種約束，可通過移除部分元組降低搜索空間。第一重約束確保僅未充分利用的主機(jī)可作為源主機(jī)，第二重約束僅允許未充分利用主機(jī)可作為目標(biāo)主機(jī)，即排除從利用充分的主機(jī)上遷移和遷移至充分利用的主機(jī)上兩種情況，這可以防止已利用充分的主機(jī)出現(xiàn)超載。而從利用充分主機(jī)上進(jìn)行虛擬機(jī)遷移也不可能導(dǎo)致源主機(jī)的終止，進(jìn)而不會(huì)降低總主機(jī)請求數(shù)量。第三重約束通過防止鄰居內(nèi)遷移進(jìn)一步限制|T|的大小。因此，作為通用規(guī)則，一個(gè)虛擬機(jī)僅能被遷移至其源主機(jī)的鄰居內(nèi)的主機(jī)上。該規(guī)則唯一例外是一個(gè)鄰居僅有一個(gè)主機(jī)，此時(shí)，該主機(jī)上的虛擬機(jī)可被遷移至任意鄰居的任意主機(jī)上。通過這三種規(guī)則的定義與利用，可以在不降低解質(zhì)量的同時(shí)極大地縮短算法的計(jì)算時(shí)間。

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

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

(2)

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

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

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

maxf(Φ)=|PR|

(3)

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

pde∈P|pde?PR

(4)

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

PR={p∈P|Vp=?}

(5)

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

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

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

(7)

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

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

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

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

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

(11)

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

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

(12)

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

算法2ACS|PR|算法

2.t∈T|τt=τ0

//元組信息素初始化

3. fori∈[1,nI] do

4. fork∈[1,nA] do

7. computeprobsby using (7)

//計(jì)算螞蟻的穿越概率

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)致主機(jī)超載

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

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

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

maxg(Φ)=(nM)-1

(13)

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

ACSnM中的螞蟻同樣利用式(6)和式(7)的偽隨機(jī)比例規(guī)則選擇需穿越的下一元組。且式(8)中的啟發(fā)值更偏向于擁有更多的已利用能力向量的虛擬機(jī)Uv。這樣，更可能導(dǎo)致虛擬機(jī)遷移量降低的虛擬機(jī)遷移操作將得到更高的啟發(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)

//計(jì)算螞蟻的穿越概率

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)致主機(jī)超載

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的時(shí)間復(fù)雜度分析。ACSnM的時(shí)間復(fù)雜度與ACS|PR|相似，由于ACSnM與ACS|PR|兩個(gè)群體均是同步且獨(dú)立運(yùn)行。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)說明

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

表2 場景設(shè)計(jì)

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

圖3 虛擬機(jī)遷移量

場景參數(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í)行時(shí)間與可擴(kuò)展性。

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

圖4 算法運(yùn)行時(shí)間

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

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

4) 結(jié)論分析。

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

4 結(jié) 語

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