許 彪 高 坤

1(湖南科技職業(yè)學(xué)院人工智能學(xué)院 湖南 長(zhǎng)沙 410004) 2(湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院 湖南 長(zhǎng)沙 410205)

0 引 言

數(shù)字時(shí)代的云計(jì)算服務(wù)正在逐年穩(wěn)步增加。目前的云計(jì)算服務(wù)形式包括平臺(tái)即服務(wù)PaaS、軟件即服務(wù)SaaS和基礎(chǔ)設(shè)施即服務(wù)IaaS，它們以按需即付即用的方式提供給終端用戶[1]。云數(shù)據(jù)中心基于終端用戶的需求進(jìn)行建立，數(shù)據(jù)中心充分利用各種存儲(chǔ)元素、處理器和網(wǎng)絡(luò)交換機(jī)為用戶提供服務(wù)[2]。目前，來(lái)自用戶的服務(wù)需求的增加已經(jīng)轉(zhuǎn)向虛擬機(jī)方向[3]。需要注意的一點(diǎn)是，目前美國(guó)境內(nèi)的云數(shù)據(jù)中心的能源消耗已經(jīng)達(dá)到30億kWh[4-5]。數(shù)據(jù)中心的能耗在未來(lái)幾年仍會(huì)以每年10%的速度增加，這不僅產(chǎn)生了使得全球氣候變暖的溫室氣體，還會(huì)增加數(shù)據(jù)中心的運(yùn)營(yíng)成本[6-7]。

為了實(shí)現(xiàn)云系統(tǒng)高能效的負(fù)載均衡，本文將設(shè)計(jì)一種基于能效的虛擬機(jī)遷移算法。算法的主要依據(jù)是利用蜻蜓算法和烏鴉算法的融合優(yōu)化和支持向量回歸SVR模型設(shè)計(jì)高效的虛擬機(jī)遷移決策機(jī)制。算法主要考慮兩個(gè)主要問(wèn)題：(1) 系統(tǒng)的負(fù)載預(yù)測(cè)問(wèn)題；(2) 最優(yōu)化的虛擬機(jī)部署問(wèn)題。基于蜻蜓算法和烏鴉算法的融合算法用于實(shí)現(xiàn)最優(yōu)的虛擬機(jī)遷移決策，支持向量回歸模型則用于預(yù)測(cè)虛擬機(jī)的負(fù)載狀況和資源利用狀況。算法的主要過(guò)程由三個(gè)步驟構(gòu)成。首先，在考慮不同資源參數(shù)類(lèi)型的情況下，需要計(jì)算主機(jī)的資源利用率，包括CPU數(shù)量、內(nèi)存、指令執(zhí)行性能MIPS和虛擬機(jī)的負(fù)載，這些參數(shù)直接決定了資源利用率。其次，利用支持向量回歸SVR模型預(yù)測(cè)每個(gè)主機(jī)的資源利用率和負(fù)載，預(yù)測(cè)資源利用率和未來(lái)主機(jī)負(fù)載之后，即需要通過(guò)負(fù)載均衡算法作出虛擬機(jī)遷移決策。此時(shí)，虛擬機(jī)在超載主機(jī)向其他主機(jī)間的遷移是一個(gè)優(yōu)化問(wèn)題，該問(wèn)題最后通過(guò)提出的融合烏鴉和蜻蜓算法的能效虛擬機(jī)遷移算法得到。

1 相關(guān)研究分析

本節(jié)對(duì)有關(guān)能效的虛擬機(jī)部署與遷移問(wèn)題進(jìn)行概述性研究，重點(diǎn)分析相關(guān)算法的思路和優(yōu)缺點(diǎn)，最后給出本文算法解決的主要問(wèn)題。文獻(xiàn)[8]為了建立虛擬機(jī)遷移模型，提出了時(shí)間感知的需求模型和多組件構(gòu)成的功耗模型，可以通過(guò)擁塞控制方法最小化任務(wù)的執(zhí)行代價(jià)，同時(shí)降低總體執(zhí)行能耗。然而，該模型缺乏導(dǎo)致確定調(diào)度時(shí)間窗口的靈活起始時(shí)間。文獻(xiàn)[9]通過(guò)修正遺傳算法GA提出了一種混合遺傳算法HGA實(shí)現(xiàn)云數(shù)據(jù)中心的能效虛擬機(jī)部署。HGA可以提供更好的開(kāi)發(fā)能力，并改進(jìn)收斂性能，但是得到的虛擬機(jī)部署方案會(huì)導(dǎo)致網(wǎng)絡(luò)負(fù)載的劇增。文獻(xiàn)[10]提出了一種虛擬機(jī)分配的優(yōu)化方法，該方法可以確保多維度資源下無(wú)死鎖的資源分配，但在沒(méi)有負(fù)載均衡策略時(shí)其網(wǎng)絡(luò)負(fù)載依然過(guò)高。文獻(xiàn)[11]提出了一種基于預(yù)測(cè)模型的虛擬機(jī)合并方法，可以預(yù)測(cè)云系統(tǒng)的未知負(fù)載，基于預(yù)測(cè)負(fù)載和資源的未來(lái)需求可以將虛擬機(jī)部署至最優(yōu)的目標(biāo)位置。即使該方法有效可行，但其擴(kuò)展性和網(wǎng)絡(luò)資源的利用率方面顯得不足。文獻(xiàn)[12]基于蜂群算法FA設(shè)計(jì)了能效虛擬機(jī)遷移算法FFO-EVMM，該算法集中于虛擬機(jī)的動(dòng)態(tài)遷移決策并可降低總體執(zhí)行功耗。但是，在復(fù)雜云環(huán)境中算法的魯棒性沒(méi)有得到討論。文獻(xiàn)[13]為了實(shí)現(xiàn)虛擬機(jī)遷移提出了基于虛擬機(jī)合并的蟻群算法ACS-VMC。算法通過(guò)增加虛擬機(jī)遷移次數(shù)最小化服務(wù)等級(jí)協(xié)議SLA的違例。但是文中沒(méi)有對(duì)算法的性能做出量化評(píng)估。文獻(xiàn)[14]為了實(shí)現(xiàn)高能效虛擬機(jī)遷移在混合云環(huán)境中，設(shè)計(jì)了基于QoS感知的部署算法，可同步實(shí)現(xiàn)功耗和SLA違例的降低，但算法實(shí)施中在不同主機(jī)間的虛擬機(jī)遷移過(guò)程忽略了網(wǎng)絡(luò)開(kāi)銷(xiāo)的優(yōu)化。文獻(xiàn)[15]結(jié)合模糊邏輯策略提出了能效感知的虛擬機(jī)遷移算法，算法利用虛擬機(jī)部署和超低載主機(jī)的識(shí)別將虛擬機(jī)負(fù)載進(jìn)行了有效合并，通過(guò)維持當(dāng)前SLA實(shí)現(xiàn)了功耗的最小化。

實(shí)現(xiàn)能效的虛擬機(jī)遷移模型的最優(yōu)化問(wèn)題所面臨的主要問(wèn)題包括：

1) 將云系統(tǒng)的空閑主機(jī)轉(zhuǎn)換為節(jié)能模式可以改善虛擬機(jī)的合并過(guò)程，但這會(huì)導(dǎo)致超載主機(jī)和低載主機(jī)的不可靠特征，即執(zhí)行虛擬機(jī)動(dòng)態(tài)遷移也會(huì)影響與虛擬機(jī)相關(guān)的任務(wù)執(zhí)行。

2) 云系統(tǒng)中執(zhí)行虛擬機(jī)遷移，需要考慮到每個(gè)虛擬機(jī)的資源利用，而為了實(shí)現(xiàn)負(fù)載均衡，最佳虛擬機(jī)的選擇必須在遷移過(guò)程中得到優(yōu)化決策。

3) 如文獻(xiàn)[9]，基于虛擬機(jī)遷移的負(fù)載均衡策略忽略了云系統(tǒng)的能耗問(wèn)題，而這是云計(jì)算系統(tǒng)效率的一個(gè)重要衡量指標(biāo)。

4) 虛擬機(jī)遷移必須全局考慮，它會(huì)影響任務(wù)的服務(wù)質(zhì)量，可能造成服務(wù)等級(jí)協(xié)議的違例。在超載主機(jī)與低載主機(jī)間進(jìn)行虛擬機(jī)遷移不應(yīng)該違背服務(wù)等級(jí)協(xié)議SLA[15]。

針對(duì)以上問(wèn)題，本文設(shè)計(jì)基于能效的虛擬機(jī)遷移算法。算法的出發(fā)點(diǎn)是利用蜻蜓算法和烏鴉算法的融合優(yōu)化和支持向量回歸模型設(shè)計(jì)虛擬機(jī)遷移決策機(jī)制，利用支持向量回歸模型預(yù)測(cè)虛擬機(jī)的負(fù)載狀況和資源利用狀況，利用蜻蜓算法和烏鴉算法的融合實(shí)現(xiàn)最優(yōu)的虛擬機(jī)遷移與部署。算法的主要技術(shù)優(yōu)勢(shì)在于：首先，算法綜合考慮不同資源類(lèi)型的負(fù)載問(wèn)題，包括CPU數(shù)量、內(nèi)存、指令執(zhí)行性能MIPS和網(wǎng)絡(luò)帶寬的負(fù)載，這些參數(shù)直接決定了資源利用率；其次，算法利用支持向量回歸模型實(shí)現(xiàn)了主機(jī)資源利用率和負(fù)載的預(yù)測(cè)，對(duì)于超載問(wèn)題可以通過(guò)負(fù)載均衡模型做出虛擬機(jī)遷移；最后，融合烏鴉和蜻蜓算法的能效虛擬機(jī)遷移則有效解決了前一步驟中的主機(jī)超載問(wèn)題，實(shí)現(xiàn)了更均衡和高能效的虛擬機(jī)部署方案。

2 云計(jì)算中的虛擬機(jī)遷移模型

本節(jié)建立實(shí)現(xiàn)負(fù)載均衡時(shí)相關(guān)虛擬機(jī)遷移的基本云計(jì)算模型。如圖1所示為本文所討論的虛擬機(jī)遷移模型與框架。云計(jì)算模型由解決云用戶需求的不同類(lèi)型的主機(jī)PM構(gòu)成，主機(jī)為了動(dòng)態(tài)地處理用戶任務(wù)，可部署虛擬機(jī)VM集合。云系統(tǒng)中的虛擬機(jī)可以動(dòng)態(tài)創(chuàng)建以減少系統(tǒng)負(fù)載的瓶頸問(wèn)題，同時(shí)通過(guò)虛擬化操作可以改進(jìn)系統(tǒng)處理速率。用戶請(qǐng)求以任務(wù)形式進(jìn)入系統(tǒng)，每個(gè)用戶任務(wù)可根據(jù)輪轉(zhuǎn)方式分配在一個(gè)虛擬機(jī)上執(zhí)行。主機(jī)控制其虛擬機(jī)集合，而云系統(tǒng)可以實(shí)現(xiàn)監(jiān)測(cè)系統(tǒng)中主機(jī)上的負(fù)載。若主機(jī)負(fù)載超過(guò)設(shè)定的閾值，即認(rèn)為該主機(jī)為超載主機(jī)，負(fù)載均衡模塊會(huì)選擇遷移該主機(jī)上的虛擬機(jī)至其他低載的主機(jī)上，從而均衡整個(gè)系統(tǒng)的負(fù)載，實(shí)現(xiàn)負(fù)載均衡。

圖1 云系統(tǒng)中的虛擬機(jī)遷移模型

(1)

3 融合烏鴉搜索算法和蜻蜓算法的能效虛擬機(jī)遷移

圖2所示為本文提出的融合烏鴉算法和蜻蜓算法的能效虛擬機(jī)遷移算法的整體框架。虛擬機(jī)遷移模型利用負(fù)載均衡策略持續(xù)檢測(cè)主機(jī)的負(fù)載狀況。若主機(jī)負(fù)載超過(guò)用戶設(shè)置的閾值，模型將選擇最佳的虛擬機(jī)在超載主機(jī)與低載主機(jī)時(shí)進(jìn)行遷移，從而平衡負(fù)載狀況。圖2中的虛擬機(jī)遷移模型假設(shè)主機(jī)PM2是超載主機(jī)，因此，需要從中選擇一個(gè)最佳的虛擬機(jī)遷移至低載的主機(jī)PMM上。本文算法模型中，利用支持向量回歸SVR模型進(jìn)行主機(jī)未來(lái)負(fù)載的預(yù)測(cè)，并通過(guò)負(fù)載均衡思想作出虛擬機(jī)遷移決策。

圖2 算法整體框架

3.1 虛擬機(jī)遷移模型

本文在虛擬機(jī)遷移模型中考慮了系統(tǒng)負(fù)載、能量和遷移代價(jià)三種因素，虛擬機(jī)對(duì)于主機(jī)資源占用的屬性包括CPU數(shù)量、內(nèi)存、網(wǎng)絡(luò)帶寬和MIPS數(shù)量四種，這些屬性均會(huì)影響系統(tǒng)負(fù)載狀況。因此，算法需要尋找最佳的遷移虛擬機(jī)進(jìn)行重新部署，從而優(yōu)化負(fù)載、能量、遷移代價(jià)。以下對(duì)這三種模型分別進(jìn)行說(shuō)明與定義。

3.1.1負(fù)載模型

系統(tǒng)的負(fù)載直接決定于處理來(lái)自用戶的任務(wù)時(shí)虛擬機(jī)占用的資源情況，虛擬機(jī)利用的資源主要包括CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、MIPS，則可將第n個(gè)虛擬機(jī)的負(fù)載定義為：

(2)

(3)

式中：QA(a)、QB(a)、QC(a)和QD(a)分別表示時(shí)間周期a時(shí)虛擬機(jī)所占用的CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和MIPS資源；R表示資源占用量，可定義為：

R=QA+QB+QC+QD

(4)

資源占用QA(a)、QB(a)、QC(a)和QD(a)可以表示為可變時(shí)間周期變量a內(nèi)的資源利用率，定義為：

(5)

(6)

虛擬機(jī)n在內(nèi)存資源上的資源占用可定義為：

(7)

(8)

同樣的道理，虛擬機(jī)n在網(wǎng)絡(luò)帶寬資源上的資源占用可定義為：

(9)

(10)

虛擬機(jī)n在MIPS資源上的資源占用可定義為：

(11)

式中：a-1和a-2代表過(guò)去的時(shí)間周期間隔內(nèi)的資源占用。

(12)

主機(jī)包含一個(gè)虛擬機(jī)集合，因此，主機(jī)負(fù)載直接取決于資源占用和虛擬機(jī)負(fù)載。主機(jī)負(fù)載和主機(jī)的資源占用分別表示為：

(13)

(14)

(15)

(16)

3.1.2遷移代價(jià)模型

虛擬機(jī)的動(dòng)態(tài)遷移允許虛擬機(jī)在不同主機(jī)之間進(jìn)行轉(zhuǎn)移，雖然不存在暫停且只有較短停機(jī)時(shí)間，但動(dòng)態(tài)遷移本身對(duì)于運(yùn)行在虛擬機(jī)上的應(yīng)用會(huì)在性能上帶來(lái)負(fù)面影響。而性能下降和停機(jī)時(shí)間均取決于應(yīng)用執(zhí)行過(guò)程中磁盤(pán)讀寫(xiě)頁(yè)面數(shù)量。因此，虛擬機(jī)的遷移代價(jià)可以系統(tǒng)中發(fā)生的虛擬機(jī)移動(dòng)次數(shù)進(jìn)行衡量。初始情況下，可將云計(jì)算系統(tǒng)的遷移代價(jià)考慮為最高，值為1。將整體的虛擬機(jī)遷移代價(jià)定義為：

(17)

式中：J表示遷移常量；o表示虛擬機(jī)的移動(dòng)次數(shù)；N表示虛擬機(jī)總量；M表示主機(jī)數(shù)量。

3.1.3能量模型

系統(tǒng)能耗取決于數(shù)據(jù)處理和遷移過(guò)程中每個(gè)虛擬機(jī)所利用的功耗，因此，云計(jì)算系統(tǒng)的能量直接決定于虛擬機(jī)上不同類(lèi)型資源產(chǎn)生的功耗，而該功耗又由對(duì)應(yīng)資源的負(fù)載和資源利用率決定。將云計(jì)算系統(tǒng)的能耗定義為：

(18)

式中：Ht表示系統(tǒng)中時(shí)間t時(shí)虛擬機(jī)相關(guān)網(wǎng)絡(luò)元素的功耗(本文考慮的元素包括CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和MIPS)。該功耗表示為：

(19)

3.2 基于支持向量回歸SVR的負(fù)載預(yù)測(cè)

虛擬機(jī)的負(fù)載在每個(gè)任務(wù)到達(dá)均可能出現(xiàn)變化，因此，有必要考慮虛擬機(jī)上的未來(lái)負(fù)載值從而選擇合適的虛擬機(jī)目標(biāo)。本文采用一種基于支持向量回歸模型SVR的未來(lái)負(fù)載預(yù)測(cè)方法。SVR模型利用一個(gè)非線性函數(shù)集合用于將已知負(fù)載值映射為未知負(fù)載值。將主機(jī)的負(fù)載值作為回歸模型的輸入值，基于該值預(yù)測(cè)未來(lái)負(fù)載值。SVR模型需要的訓(xùn)練集合定義為：

S={(u1,v1),(u2,v2),…,(uN,vN)}

(20)

式中：u屬于輸入集合U；v屬于輸出的預(yù)測(cè)集合V。模型輸入和輸出間的映射可形式化為以下的最優(yōu)化問(wèn)題：

(21)

式中：L表示輸出估算值的代價(jià)。最優(yōu)化問(wèn)題的約束條件為：

〈〈p,φ(un)〉+q〉-vn≤α+α+

(22)

vn-〈〈p,φ(un)〉+q〉≤α+α-

(23)

式中：α+和α-分別表示預(yù)定義的誤差和高維度特征集合G中的p值；φ表示分離超平面的符號(hào)函數(shù)。SVR利用回歸函數(shù)定義輸出估算值的上限和下限，其回歸函數(shù)定義為：

f(u)=〈p,φ(u)〉+q

(24)

此外，SVR模型利用拉格朗日對(duì)偶最大化問(wèn)題進(jìn)行估算值的預(yù)測(cè)，可將其表示為：

(25)

式中：βn表示拉格朗日乘子,W表示對(duì)偶函數(shù)。

以上定義的最大化問(wèn)題的約束條件為：

對(duì)于拉格朗日對(duì)偶最大化問(wèn)題的回歸估算可表示為：

(26)

3.3 負(fù)載預(yù)測(cè)算法

本節(jié)給出負(fù)載均衡算法，通過(guò)虛擬機(jī)遷移完成均衡的負(fù)載分配。算法的主要步驟如下：

步驟1初始化云計(jì)算系統(tǒng)，包括M個(gè)系統(tǒng)主機(jī)PM和N個(gè)虛擬機(jī)VM。

步驟2初始階段將主機(jī)的遷移代價(jià)設(shè)置為最大值，即遷移代價(jià)為1。

步驟3在時(shí)間周期t時(shí)，根據(jù)輪轉(zhuǎn)方法將到達(dá)的任務(wù)分配至虛擬機(jī)。

步驟5根據(jù)以下標(biāo)準(zhǔn)，選擇最佳的虛擬機(jī)(基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署算法中得到)在低載主機(jī)和超載主機(jī)間進(jìn)行虛擬機(jī)遷移，并更新遷移代價(jià)：

(27)

步驟6尋找系統(tǒng)負(fù)載值Zt、能耗、資源利用率、系統(tǒng)的遷移代價(jià)。

步驟7重復(fù)步驟3-步驟6進(jìn)行算法迭代，直到達(dá)到終止迭代條件h。

3.4 基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署算法

3.4.1解的編碼

考慮以下場(chǎng)景：主機(jī)PM1部署3個(gè)虛擬機(jī)，主機(jī)PM2部署2個(gè)虛擬機(jī)，到達(dá)的任務(wù)根據(jù)輪轉(zhuǎn)方式分配至每個(gè)虛擬機(jī)上執(zhí)行。當(dāng)主機(jī)PM1超載時(shí)，PM1上的虛擬機(jī)需要遷移至PM2上，算法的目標(biāo)即是選擇最佳的虛擬機(jī)進(jìn)行遷移。如圖3所示即為解的編碼方式。

圖3 解的編碼

3.4.2適應(yīng)度評(píng)估

適應(yīng)度函數(shù)用于選擇合適的虛擬機(jī)在低載主機(jī)和超載主機(jī)間遷移。本文定義了基于負(fù)載、能量和遷移代價(jià)的適應(yīng)度函數(shù)，并以適應(yīng)度值最大化為目標(biāo)。具體將適應(yīng)度函數(shù)定義為：

(28)

3.4.3算法具體過(guò)程

基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署的目標(biāo)是選擇最佳的虛擬機(jī)進(jìn)行遷移，具體過(guò)程如下：

步驟1種群初始化。首先，隨機(jī)初始化種群，生成種群規(guī)模為O的解集，并將其表示為：

I={I1,I2,…,Ii,…,IO}

(29)

式中：Ii表示第i個(gè)解，1≤i≤O。

步驟2適應(yīng)度評(píng)估。根據(jù)式(28)的適應(yīng)度函數(shù)，評(píng)估每個(gè)解的適應(yīng)度。由于算法應(yīng)用的適應(yīng)度是最大化函數(shù)，包括最大適應(yīng)度值的解被保留，可進(jìn)入下一輪的迭代更新。

步驟3位置更新。蜻蜓算法DA考慮的種群元素為蜻蜓，在蜻蜓更新位置過(guò)程中，其具體屬性包括：分離、隊(duì)列、凝聚、食物源、敵人。DA的位置更新模式如下：

I(z+1)=I(z)+(b1X1+b2X2+

b3X3+b4X4+b5X5)+rΔI(z)

(30)

式中：X1、X2、X3、X4和X5分別表示以上5個(gè)屬性上解的位置；b1、b2、b3、b4和b5分別對(duì)應(yīng)于5個(gè)屬性影響解的質(zhì)量的權(quán)重；r表示解的慣性權(quán)重；ΔI(z)表示以上參數(shù)的位置變化。

烏鴉搜索算法CSA也是一種類(lèi)似于DA的智能種群算法，其考慮的種群是烏鴉，每個(gè)解的更新取決于烏鴉的行為。CSA中位置更新方式為：

I(z+1)=I(z)+c·l(z)·(e(z)-I(z))

(31)

式中：c表示CSA更新的常量；l(z)表示迭代z時(shí)解的飛行長(zhǎng)度因子；e(z)表示記憶。

由于DA和CSA兩種算法的位置更新等式均取決于種群特征和隨機(jī)初始化的種群位置，可將CSA的位置更新應(yīng)用于DA的位置更新中。因此，可以尋找CSA中的l(z)值，并用于取代CSA中的位置更新值。修改式(31)得到l(z)的值，可將其表示為：

(32)

將式(32)代入式(31)中，算法得到的位置更新為：

(b1X1+b2X2+b3X3+b4X4+b5X5)+rΔI(z)

(33)

式(34)表示算法的位置更新的最終等式：

(34)

步驟4基于適應(yīng)度尋找最優(yōu)解。計(jì)算每個(gè)更新解的適應(yīng)度，擁有最高適應(yīng)度的解保留為算法的最優(yōu)解。

步驟5算法終止。算法迭代結(jié)束，返回最優(yōu)解。最大迭代限制定義為Y。

算法1給出了基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署算法的偽代碼，算法目標(biāo)是在主機(jī)到達(dá)超載條件時(shí)尋找最佳的遷移虛擬機(jī)，遷移虛擬機(jī)需要從超載主機(jī)上遷移至低載主機(jī)上。最優(yōu)化過(guò)程利用了基于負(fù)載、遷移代價(jià)和能耗的適應(yīng)度來(lái)決策遷移虛擬機(jī)的選擇。

算法1基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署

輸入:population I

//輸入初始種群

輸出:best solution

//輸出虛擬機(jī)最優(yōu)部署解

1.begin

2. randomly initialize the population of our algorithm

//對(duì)算法的種群進(jìn)行隨機(jī)初始化，得到初始解

3.ifz≤Y

//當(dāng)前迭代次數(shù)未超過(guò)最大迭代次數(shù)

4. find the fitness value of each solution based on Equ.(28)

//根據(jù)式(28)計(jì)算每個(gè)解的適應(yīng)度

5. update the position of the solution based on Equ.(34)

//根據(jù)式(34)更新解的位置

6. recompute the fitness of each solution

//重新計(jì)算每個(gè)解的適應(yīng)度值

7.endif

8.ifz=Y

//到達(dá)最大迭代次數(shù)

9.returnthe optimal solution

//返回最優(yōu)部署解

10.endif

11.end

4 仿真實(shí)驗(yàn)評(píng)測(cè)

4.1 實(shí)驗(yàn)環(huán)境與評(píng)價(jià)指標(biāo)

通過(guò)CloudSim[16]構(gòu)造仿真環(huán)境對(duì)算法的可行性和有效性進(jìn)行驗(yàn)證，仿真實(shí)驗(yàn)中建立5臺(tái)主機(jī)和20臺(tái)虛擬機(jī)的部署環(huán)境，用戶到達(dá)任務(wù)設(shè)置為100和500，以此度量算法在不同運(yùn)行規(guī)模下的效率。算法的評(píng)價(jià)選擇為能耗、遷移代價(jià)和負(fù)載，三個(gè)指標(biāo)分別由文中式(18)、式(17)和式(15)定義，優(yōu)化目標(biāo)是盡可能最小化三個(gè)指標(biāo)值。

選擇的對(duì)比算法包括ACO算法[13]、LR算法[11]、MEGSA-VMM算法[17]和DA[18]。ACO算法執(zhí)行虛擬機(jī)的分配是基于螞蟻的搜索行為，LR算法進(jìn)行虛擬機(jī)合并則是通過(guò)系統(tǒng)中CPU和內(nèi)存利用的預(yù)測(cè)方式實(shí)現(xiàn)，MEGSA-VMM算法則利用了指數(shù)遷移平均模型EWMA和引力搜索算法GSA進(jìn)行虛擬機(jī)的優(yōu)化部署過(guò)程，DA則是傳統(tǒng)的蜻蜓算法過(guò)程。

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)1測(cè)試了100個(gè)用戶預(yù)測(cè)任務(wù)到達(dá)時(shí)算法的性能表現(xiàn)，結(jié)果如圖4所示。在首次算法迭代中，ACO、LR、MEGSA-VMM和DA得到的負(fù)載指標(biāo)值分別為0.57、0.29、0.07和0.075。本文算法得到的負(fù)載指標(biāo)值為0.07，是所有算法中最低的。同樣，在能耗方面，本文算法在首次迭代中得到了所有算法中最小的能耗值為0.016。而在遷移代價(jià)方面，本文算法同樣是最優(yōu)的。換言之，負(fù)載、能耗、遷移代價(jià)三個(gè)指標(biāo)值上，本文算法均得到了最小值，則適應(yīng)度相應(yīng)是所有算法中最大的，性能表現(xiàn)是最好的。原因在于：支持向量回歸機(jī)制可以利用非線性函數(shù)集合將所取樣的已知負(fù)載值映射為未知負(fù)載值，以主機(jī)負(fù)載值作為回歸模型的輸入值，可以較為準(zhǔn)確地對(duì)主機(jī)的未來(lái)負(fù)載作出決策，預(yù)防出現(xiàn)熱點(diǎn)而導(dǎo)致性能下降，為優(yōu)化虛擬機(jī)的具體部署打好了基礎(chǔ)。而融合入蜻蜓算法和烏鴉算法的虛擬機(jī)部署策略則在超載情況下的虛擬機(jī)遷移選擇上作出了最優(yōu)決策，通過(guò)融合兩種算法在局部開(kāi)發(fā)和全局搜索上的優(yōu)勢(shì)可以使得虛擬機(jī)遷移在滿足負(fù)載均衡的同時(shí)得到最小化系統(tǒng)能耗。

(a) 負(fù)載狀況

圖5是將任務(wù)量增加至500時(shí)得到的算法性能表現(xiàn)?？梢钥闯?，增大任務(wù)規(guī)模并沒(méi)有對(duì)本文算法的執(zhí)行效率產(chǎn)生反轉(zhuǎn)式影響，其在負(fù)載、能耗和遷移代價(jià)三個(gè)指標(biāo)上依然穩(wěn)定地優(yōu)于另外四種對(duì)比算法，這說(shuō)明所采用的支持向量回歸的負(fù)載預(yù)測(cè)機(jī)制和融合入蜻蜓算法和烏鴉算法的虛擬機(jī)部署策略依然是有效可行的，不僅可以對(duì)虛擬機(jī)遷移選擇做出正確決策，而且能夠使得虛擬機(jī)遷移在滿足負(fù)載均衡的同時(shí)最小化系統(tǒng)能耗，具有全局最優(yōu)的執(zhí)行效率。

(a) 負(fù)載狀況

5 結(jié) 語(yǔ)

綜合考慮系統(tǒng)負(fù)載、能耗和遷移代價(jià)等指標(biāo)，提出一種能效虛擬機(jī)遷移算法。算法主要工作包括：首先，設(shè)計(jì)一種基于支持向量回歸SVR的負(fù)載預(yù)測(cè)方法，該方法可以利用非線性函數(shù)集合將已知負(fù)載值映射為未知負(fù)載值，通過(guò)回歸模型準(zhǔn)確預(yù)測(cè)系統(tǒng)負(fù)載；其次，將烏鴉搜索算法融入蜻蜓算法中，設(shè)計(jì)一種基于烏鴉搜索和蜻蜓優(yōu)化算法的虛擬機(jī)最優(yōu)部署算法，從而完成高能效負(fù)載均衡。進(jìn)一步的工作可以增加更多的參數(shù)在虛擬機(jī)的優(yōu)化部署中，如網(wǎng)絡(luò)帶寬、服務(wù)質(zhì)量的考量等。