數(shù)據(jù)云中基于啟發(fā)式反向蜂群的虛擬機(jī)選擇節(jié)能算法

姜建華, 劉 渝, 王麗敏, 陳 堅(jiān), 黃 娜,3, 魏曉輝

(1.吉林財(cái)經(jīng)大學(xué) 物流產(chǎn)業(yè)經(jīng)濟(jì)與智能物流實(shí)驗(yàn)室, 長(zhǎng)春 130117； 2.吉林財(cái)經(jīng)大學(xué) 管理科學(xué)與信息工程學(xué)院, 長(zhǎng)春 130117；3.上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院, 上海 200433; 4.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

數(shù)據(jù)云中基于啟發(fā)式反向蜂群的虛擬機(jī)選擇節(jié)能算法

姜建華1,2, 劉 渝2, 王麗敏2, 陳 堅(jiān)1, 黃 娜1,3, 魏曉輝4

(1.吉林財(cái)經(jīng)大學(xué) 物流產(chǎn)業(yè)經(jīng)濟(jì)與智能物流實(shí)驗(yàn)室, 長(zhǎng)春 130117；
2.吉林財(cái)經(jīng)大學(xué) 管理科學(xué)與信息工程學(xué)院, 長(zhǎng)春 130117；
3.上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院, 上海 200433; 4.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

結(jié)合數(shù)據(jù)中心中數(shù)據(jù)密集型作業(yè)的頻繁讀寫(xiě)數(shù)據(jù)特點(diǎn), 綜合考慮CPU使用率和RAM使用率兩個(gè)影響因素構(gòu)建服務(wù)器能耗評(píng)價(jià)模型, 并引入人工蜂群算法及啟發(fā)式反向思想, 將其應(yīng)用于數(shù)據(jù)中心虛擬機(jī)遷移策略中的虛擬機(jī)選擇環(huán)節(jié), 實(shí)現(xiàn)云計(jì)算中數(shù)據(jù)中心節(jié)能問(wèn)題的優(yōu)化.在CloudSim 3.0云計(jì)算模擬器中的仿真實(shí)驗(yàn)結(jié)果表明： 該啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS)與最大最小時(shí)間(MMT)、隨機(jī)選擇(RS)和最小使用率(MU)3種經(jīng)典虛擬機(jī)選擇算法相比節(jié)能20%～25%, 虛擬機(jī)遷移頻率減少至5%以下.

云計(jì)算; 虛擬機(jī)遷移; 虛擬機(jī)選擇; 人工蜂群算法

由于云計(jì)算數(shù)據(jù)中心能耗巨大, 因此如何在數(shù)據(jù)中心中進(jìn)行節(jié)能和減少環(huán)境危害已成為當(dāng)前的研究熱點(diǎn)問(wèn)題之一.云數(shù)據(jù)中心的節(jié)能策略主要包括硬件節(jié)能策略和軟件節(jié)能策略[1-5].數(shù)據(jù)云(data cloud)是建立在網(wǎng)絡(luò)附加存儲(chǔ)(NAS)、存儲(chǔ)區(qū)域網(wǎng)絡(luò)(SAN)等基礎(chǔ)上, 可通過(guò)互聯(lián)網(wǎng)設(shè)備對(duì)數(shù)據(jù)進(jìn)行實(shí)時(shí)交換、隨時(shí)隨地使用的無(wú)限量數(shù)據(jù)集合.數(shù)據(jù)云環(huán)境下數(shù)據(jù)密集型作業(yè)成為數(shù)據(jù)中心的主要作業(yè)類型.數(shù)據(jù)密集型作業(yè)以數(shù)據(jù)處理為主要處理任務(wù), 導(dǎo)致大量?jī)?nèi)存讀寫(xiě)操作.目前, 單個(gè)服務(wù)器能耗評(píng)估模型主要考慮CPU、內(nèi)存、網(wǎng)絡(luò)及硬盤讀寫(xiě)等因素， 但數(shù)據(jù)云環(huán)境下數(shù)據(jù)中心主要以計(jì)算處理、內(nèi)存讀寫(xiě)操作為主， 因此, 單個(gè)服務(wù)器的能耗評(píng)估模型本文只考慮CPU計(jì)算和內(nèi)存讀寫(xiě)兩個(gè)主要影響因素.虛擬機(jī)遷移是當(dāng)前軟件節(jié)能領(lǐng)域中最重要的節(jié)能策略.虛擬機(jī)遷移主要涉及源主機(jī)選擇、虛擬機(jī)選擇、虛擬機(jī)分配和虛擬機(jī)遷移機(jī)制等.現(xiàn)有的虛擬機(jī)遷移策略核心聚焦于虛擬機(jī)分配問(wèn)題, 而虛擬機(jī)選擇恰是降低能耗最關(guān)鍵的一環(huán).因?yàn)樘摂M機(jī)選擇的結(jié)果將直接影響虛擬機(jī)分配策略的好壞, 并最終導(dǎo)致數(shù)據(jù)中心的能耗優(yōu)化效果.虛擬機(jī)選擇(VM selection)問(wèn)題通常存在局部較優(yōu)、選擇反復(fù)等現(xiàn)象, 難以獲得最優(yōu)解.人工蜂群(artificial bee colony, ABC)[6]算法具有通過(guò)自組織、分工協(xié)作的運(yùn)作模式實(shí)現(xiàn)快速收斂獲取全局最優(yōu)的優(yōu)點(diǎn).本文結(jié)合蜂群算法對(duì)虛擬機(jī)選擇進(jìn)行優(yōu)化, 主要思想： 首先對(duì)計(jì)算節(jié)點(diǎn)的負(fù)載情況進(jìn)行判斷, 負(fù)載過(guò)高或過(guò)低的計(jì)算節(jié)點(diǎn)需進(jìn)行虛擬機(jī)遷移, 通過(guò)蜂群思想選擇出導(dǎo)致數(shù)據(jù)中心能耗最優(yōu)的被遷移虛擬機(jī).

本文算法采用蜂群思想對(duì)虛擬機(jī)選擇策略進(jìn)行新解讀, 實(shí)現(xiàn)一個(gè)啟發(fā)式反向蜂群優(yōu)化虛擬機(jī)選擇算法, 具有自組織、分工協(xié)作和快速收斂的特征； 結(jié)合數(shù)據(jù)密集型作業(yè)特點(diǎn)和服務(wù)器能耗模型考慮CPU使用率和內(nèi)存利用率兩個(gè)主要影響因素, 構(gòu)建適合數(shù)據(jù)密集型作業(yè)的能耗評(píng)估模型.實(shí)驗(yàn)結(jié)果表明： 啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS)較其他3種虛擬機(jī)選擇算法(最大最小時(shí)間(MMT), 隨機(jī)選擇(RS), 最小使用率(MU))能級(jí)數(shù)級(jí)降低虛擬機(jī)遷移次數(shù)----從數(shù)萬(wàn)次降到一千多次, 并在可容忍服務(wù)水平協(xié)議違反率(SLAV)下, 能有效降低云計(jì)算數(shù)據(jù)中心的能耗(節(jié)約20%～25%), 從而減少CO2的排放, 節(jié)約云計(jì)算數(shù)據(jù)中心的運(yùn)營(yíng)成本.

1 人工蜂群算法

圖1 傳統(tǒng)人工蜂群采蜜行為算法示意圖Fig.1 Workflow of ABC algorithm

人工蜂群算法[7]是一種建立在Seeley自組織模型上的群智能算法, 主要分為基于繁殖行為和基于采蜜行為兩類算法[6].本文采用基于采蜜行為的人工蜂群算法思想, 如圖1所示.由圖1可見(jiàn): 蜜蜂在采蜜過(guò)程中分為雇傭蜂(employed foragers)和未雇傭蜂(unemployment foragers).(W1)采蜜前需從未雇傭蜂中派出蜜蜂, 使之成為偵察蜂(scout bees)對(duì)蜜源(foods)進(jìn)行探查, 并根據(jù)閾值對(duì)蜜源進(jìn)行判斷.如果該蜜源質(zhì)量好, 探測(cè)該蜜源的偵查蜂即變?yōu)楣蛡蚍? 并對(duì)該優(yōu)質(zhì)蜜源進(jìn)行采集; 反之, 尋找其他蜜源.(W2)雇傭蜂采集蜂蜜后返回蜂巢, 將蜂蜜卸下, 并將蜜源信息帶回.(W3)卸下蜂蜜的雇傭蜂有3種選擇： 1) (W[3,1])成為未雇傭蜂； 2) (W[3,2])到舞池中跳舞, 并將蜜源信息傳遞給其他蜜蜂, 招募未雇傭蜂成為雇傭蜂, 并引領(lǐng)它們到優(yōu)質(zhì)蜜源采蜜； 3) (W[3,3])繼續(xù)作為雇傭蜂到優(yōu)質(zhì)蜜源采蜜.而未雇傭蜂有兩種選擇： 1) (W1)成為偵查蜂尋找蜜源； 2) (W4)到舞池中接受招募成為雇傭蜂, 跟隨引領(lǐng)蜂到蜜源采蜜.當(dāng)某一蜜源質(zhì)量下降到一定程度, 而不需要較多的雇傭蜂時(shí), 則將該蜜源上一定量的雇傭蜂通過(guò)舞池轉(zhuǎn)移到其他蜜源.當(dāng)蜜源質(zhì)量低于閾值時(shí), 則放棄該蜜源, 轉(zhuǎn)移到其他蜜源.蜜蜂采蜜行為的偽代碼如下.

算法1人工蜂群采蜜行為算法.

輸入： 未探測(cè)蜜源區(qū)U={u1,u2,…,um}, 蜂群B={b1,b2,…,bn};

輸出： 最優(yōu)蜜源區(qū)uj.

步驟如下：

1) 從蜂群B中派出未雇傭蜂b1,b2,…,bj, 使它們成為偵查蜂, 探測(cè)未探測(cè)蜜源區(qū)u1,u2,…,um;

2) 偵查蜂b1,b2,…,bj探測(cè)到優(yōu)質(zhì)蜜源則成為雇傭蜂, 采蜜返回蜂巢卸蜜, 否則放棄該蜜源到鄰近蜜源探測(cè);

3) 某雇傭蜂bk卸蜜后, 得到該雇傭蜂偵查過(guò)蜜源區(qū)的蜜源質(zhì)量, 并得到一個(gè)局部最優(yōu)蜜源區(qū)uk, 之后該雇傭蜂可成為未雇傭蜂或繼續(xù)作為雇傭蜂;

4) 當(dāng)該雇傭蜂bk成為未雇傭蜂時(shí), 可返回步驟1)成為偵查蜂探測(cè)蜜源區(qū), 或跟隨舞池中的引領(lǐng)蜂到該蜜源區(qū)采蜜;

5) 當(dāng)該雇傭蜂bk繼續(xù)作為雇傭蜂時(shí), 可直接返回該蜜源采蜜, 或作為引領(lǐng)蜂在舞池跳舞以招募未雇傭蜂;

6) 返回的局部最優(yōu)蜜源區(qū), 如uk,uj,um, 并最終得到一個(gè)全局最優(yōu)的蜜源區(qū);

7) 算法結(jié)束.

由圖1和算法1可見(jiàn), 人工蜂群采蜜行為是一種群體智能行為.雇傭蜂、偵查蜂、未雇傭蜂之間相互協(xié)作以提升采蜜效率和質(zhì)量.在傳統(tǒng)ABC算法中, 食物源的位置表示待優(yōu)化問(wèn)題的一個(gè)可行解, 食物源的質(zhì)量表示解的質(zhì)量, 即適應(yīng)度; 種群初始化時(shí), 首先隨機(jī)產(chǎn)生sn個(gè)可行解, 并計(jì)算其適應(yīng)度, 然后根據(jù)適應(yīng)度進(jìn)行排序, 前50%的蜂為雇傭蜂, 后50%的蜂為跟隨蜂.隨機(jī)產(chǎn)生的可行解公式為

其中,j∈{1,2,…,Q}為Q維解向量的某個(gè)分量.

蜜蜂記錄自己到目前為止的最優(yōu)解, 并在當(dāng)前蜜源附近展開(kāi)領(lǐng)域搜索, 產(chǎn)生一個(gè)新位置替代前一個(gè)位置, 公式為

其中:k隨機(jī)產(chǎn)生且k≠i,k∈{1,2,…,Sn};φij為[-1,1]間的隨機(jī)數(shù).

蜜蜂采蜜采用貪婪原則.算法將當(dāng)前最優(yōu)解與領(lǐng)域搜索所得的解進(jìn)行比較.若所得解更優(yōu), 則替換當(dāng)前最優(yōu)解.其中, 跟隨蜂根據(jù)蜜源信息以一定的概率追隨引領(lǐng)蜂, 其概率為

2 ABCS算法

2.1虛擬機(jī)選擇問(wèn)題

在云計(jì)算的數(shù)據(jù)中心中, 虛擬機(jī)實(shí)時(shí)遷移有利于優(yōu)化計(jì)算節(jié)點(diǎn)的負(fù)載平衡, 提升處理效率, 降低能耗.虛擬機(jī)遷移主要涉及源主機(jī)選擇、虛擬機(jī)選擇、目標(biāo)主機(jī)選擇及實(shí)時(shí)遷移過(guò)程等.其中, 虛擬機(jī)選擇是其中的關(guān)鍵環(huán)節(jié), 因?yàn)樘摂M機(jī)選擇的好壞將直接影響虛擬機(jī)遷移的次數(shù)、負(fù)載的平衡和能源的消耗等.

虛擬機(jī)選擇問(wèn)題可描述為： 從某個(gè)需遷移源主機(jī)上的眾多虛擬機(jī)中選擇出當(dāng)前最佳被遷移虛擬機(jī)的過(guò)程, 如圖2所示.虛擬機(jī)選擇問(wèn)題可描述為： 云計(jì)算資源池由異構(gòu)服務(wù)器集群組成, 集合H={h1,h2,…,hj,…,hn}表示服務(wù)器集群, 其中hj表示任一服務(wù)器.設(shè)集合HCPU={hc1,hc2,…,hcj,…,hcn}和HRAM={hr1,hr2,…,hrj,…,hrn}分別表示服務(wù)器集群中各主機(jī)的CPU使用率和RAM使用率, 集合Hselection={hs1,hs2,…,hsj,…,hsn}表示候選待遷移主機(jī)隊(duì)列, 其中hsj為H集合中通過(guò)對(duì)HCPU和HRAM的綜合閾值篩選出的某個(gè)服務(wù)器, 集合V={vm1,vm2,…,vmj,…,vmn}表示某個(gè)候選待遷移主機(jī)中虛擬機(jī)(VM)隊(duì)列的集合,vmj表示某個(gè)候選待遷移主機(jī)hsk上的某個(gè)虛擬機(jī).

圖2 虛擬機(jī)選擇問(wèn)題示意圖Fig.2 Diagram of VM selection issue

2.2虛擬機(jī)能耗評(píng)估模型

由于云計(jì)算中數(shù)據(jù)中心的主要作業(yè)為數(shù)據(jù)密集型作業(yè), 該類型作業(yè)在處理過(guò)程中以數(shù)據(jù)處理為主, 即頻繁進(jìn)行RAM讀寫(xiě)操作, 因此, 虛擬機(jī)能耗評(píng)估模型不能僅以CPU使用率為影響因素, 而應(yīng)綜合考慮內(nèi)存使用情況等.但在實(shí)際模擬實(shí)驗(yàn)中, CloudSim 3.0實(shí)驗(yàn)環(huán)境未提供內(nèi)存讀寫(xiě)能耗評(píng)價(jià)模型.同時(shí), 在構(gòu)建虛擬機(jī)能耗評(píng)價(jià)模型中, 應(yīng)考慮懲罰能耗V-SLA問(wèn)題, 即不及時(shí)遷移的懲罰能耗.設(shè)ECP表示懲罰能耗, 且其為常數(shù).本文實(shí)驗(yàn)中, 假設(shè)V-SLA具有Poisson分布的特點(diǎn).此外, 虛擬機(jī)固有能耗(某個(gè)時(shí)間段t)應(yīng)與服務(wù)器節(jié)點(diǎn)進(jìn)行能耗比例劃分.因此, 虛擬機(jī)能耗主要包括三方面： CPU能耗、內(nèi)存能耗和懲罰能耗.基于文獻(xiàn)[8]中的算法, 并作出調(diào)整, 計(jì)算公式如下：

1) 主機(jī)CPU的能耗

其中,αCPU和γCPU表示模型的特定常數(shù), 可通過(guò)訓(xùn)練獲得;

2) 虛擬機(jī)A的CPU能耗

3) 主機(jī)RAM的能耗

其中:αRAM表示內(nèi)存RAM利用率的參數(shù);γRAM表示常數(shù),αRAM和γRAM可通過(guò)訓(xùn)練獲得；

4) 虛擬機(jī)A中RAM的能耗

5) 虛擬機(jī)懲罰能耗

6) 虛擬機(jī)能耗計(jì)算模型

7) 適應(yīng)度

（10）

2.3虛擬機(jī)選擇節(jié)能算法

本文虛擬機(jī)選擇節(jié)能算法包括候選源主機(jī)隊(duì)列選擇算法和虛擬機(jī)選擇節(jié)能算法兩部分.候選源主機(jī)隊(duì)列選擇算法主要從云計(jì)算數(shù)據(jù)中心中的眾多主機(jī)中篩選出需要遷移的候選主機(jī)隊(duì)列； 而虛擬機(jī)選擇節(jié)能算法則是從候選主機(jī)中選擇最佳需遷移的虛擬機(jī).

候選源主機(jī)選擇主要采用靜態(tài)雙閾值(T1,T2)對(duì)云計(jì)算數(shù)據(jù)中心中的主機(jī)進(jìn)行篩選, 選出候選遷移主機(jī)隊(duì)列.靜態(tài)雙閾值計(jì)算公式為

圖3 T1和T2的內(nèi)涵示意圖Fig.3 Diagram of T1 and T2 meaning

圖3為T1和T2的內(nèi)涵示意圖.由圖3可見(jiàn), 閾值T1可表示為矩形面積S,S由CPU利用率和RAM利用率確定.當(dāng)CPU利用率和RAM利用率均較高, 或CPU利用率和RAM利用率均較低時(shí), 則表現(xiàn)出面積S過(guò)大或過(guò)小.根據(jù)多次模擬實(shí)驗(yàn)結(jié)果可知, 可設(shè)置T1的閾值上下限為(0.1,0.6).若某個(gè)主機(jī)T1值在該范圍外, 則將其添加到候選遷移主機(jī)隊(duì)列中.結(jié)合數(shù)據(jù)中心的作業(yè)處理特點(diǎn), 若某個(gè)主機(jī)RAM利用率相對(duì)過(guò)高, 則反映出該主機(jī)在一段時(shí)間內(nèi)進(jìn)行密集的數(shù)據(jù)讀寫(xiě)操作, 這將影響系統(tǒng)的作業(yè)處理效率, 也需進(jìn)行虛擬機(jī)遷移操作.對(duì)于處于T1閾值內(nèi)主機(jī)所形成的主機(jī)集合, 需進(jìn)一步根據(jù)T2(多次模擬實(shí)驗(yàn)所得數(shù)據(jù), 設(shè)T2=2.5)繼續(xù)篩選.T2表示RAM利用率和CPU利用率的比例關(guān)系.若T2過(guò)高, 則表明該主機(jī)中的RAM利用率相對(duì)過(guò)高, 可將該主機(jī)也置于虛擬機(jī)遷移候選主機(jī)隊(duì)列.

算法2候選源主機(jī)隊(duì)列選擇算法.

輸入： 所有主機(jī)隊(duì)列H={h1,h2,…,hn};

輸出： 候選遷移主機(jī)隊(duì)列CMQ={hj,hk,…,hm}.

步驟如下：

1) 將所有主機(jī)H={h1,h2,…,hn}都被標(biāo)記為未被選擇狀態(tài);

2) 遍歷未被選擇主機(jī)隊(duì)列H={h1,h2,…,hn}, 判斷某主機(jī)h的閾值, 若hT1T1_max, 則將該主機(jī)放入候選遷移主機(jī)隊(duì)列CMQ中; 反之, 其他未滿足條件的候選主機(jī)則放入非遷移主機(jī)隊(duì)列UMQ中;

3) 再次遍歷非遷移主機(jī)隊(duì)列UMQ, 若主機(jī)h的閾值hT2>T2, 則將主機(jī)h放入候選遷移主機(jī)隊(duì)列CMQ中, 并將h從非遷移主機(jī)隊(duì)列中移除;

4) 得到最終的候選遷移主機(jī)隊(duì)列, 如CMQ={hj,hk,…,hm};

5) 算法結(jié)束.

圖4 ABCS算法流程示意圖Fig.4 Workflow of ABCS algorithm

ABCS算法流程如圖4所示.其核心思想就是將蜂群采蜜智能思想應(yīng)用于虛擬機(jī)選擇問(wèn)題的求解過(guò)程中, 并對(duì)引領(lǐng)蜂、跟隨蜂和偵查蜂賦予啟發(fā)式智能.虛擬機(jī)選擇是指從已選擇出的候選源主機(jī)中按一定度量選擇滿足負(fù)荷條件的候選虛擬機(jī).本文通過(guò)蜂群算法的思想對(duì)需遷移的虛擬機(jī)進(jìn)行選擇, 實(shí)現(xiàn)數(shù)據(jù)密集型作業(yè)下的虛擬機(jī)最優(yōu)選擇策略.

算法3ABCS算法.

輸入: 虛擬機(jī)隊(duì)列VM={vm1,vm2,…,vmn};

輸出： 返回最佳待遷移虛擬機(jī)vmj.

步驟如下：

1) 將所有虛擬機(jī)隊(duì)列VM={vm1,vm2,…,vmn}都標(biāo)記為未探測(cè);

2) 設(shè)置循環(huán)次數(shù)為5次;

3) 判斷未探測(cè)虛擬機(jī)的數(shù)量, 如果未探測(cè)虛擬機(jī)的數(shù)量小于10, 則直接遍歷探測(cè)所有虛擬機(jī), 找出最優(yōu)解;

4) 如果未探測(cè)虛擬機(jī)的數(shù)量大于10, 則使用蜂群算法, 每次返回一個(gè)局部最優(yōu)解vmk;

5) 通過(guò)局部最優(yōu)解vmk,…,vmi得到全局最優(yōu)解vmj, 即全局最佳待遷移虛擬機(jī);

6) 算法結(jié)束.

圖5 ABCS中的3個(gè)列表結(jié)構(gòu)Fig.5 Data structure of 3 lists in ABCS

由圖4和算法3可見(jiàn), 該算法首先從待遷移候選主機(jī)隊(duì)列中選出某個(gè)源主機(jī)Hostk, 對(duì)該源主機(jī)Hostk初始化, 將Hostk中可遷移的虛擬機(jī)(VMs)按照RAM利用率進(jìn)行排序.然后判斷未被探測(cè)的虛擬機(jī)數(shù)量, 當(dāng)其小于某一閾值時(shí), 遍歷所有未探測(cè)虛擬機(jī), 得到最優(yōu)解.若未探測(cè)虛擬機(jī)的數(shù)量大于一定數(shù)量時(shí), 則采用蜂群算法思想選擇最優(yōu)解.主要思想是： 采用啟發(fā)式派雇傭蜂和跟隨蜂, 并采用啟發(fā)式反向派偵查蜂, 得到局部最優(yōu)解.其中: 啟發(fā)式派雇傭蜂指通過(guò)對(duì)雇傭蜂賦予一定智能進(jìn)行蜜源的初始選擇探測(cè), 得到一個(gè)當(dāng)前最優(yōu)解； 啟發(fā)式派跟隨蜂指根據(jù)當(dāng)前最優(yōu)解的左右近鄰派出跟隨蜂； 啟發(fā)式反向派偵查蜂指根據(jù)不同區(qū)域最優(yōu)解可能性的大小, 派偵查蜂到較小概率區(qū)域中.通過(guò)多次循環(huán)派出雇傭蜂、跟隨蜂和偵查蜂, 若可能的解遍歷完則直接得出最優(yōu)解, 反之則在循環(huán)次數(shù)內(nèi), 獲得當(dāng)前最優(yōu)解中的全局最優(yōu)解.因此, 算法能快速選出最優(yōu)的虛擬機(jī)進(jìn)行遷移.從而實(shí)現(xiàn)虛擬機(jī)遷移效率, 減少遷移次數(shù), 有效節(jié)省能耗.

本文通過(guò)蜂群算法思想選擇最優(yōu)解, 主要包括啟發(fā)式派雇傭蜂、跟隨蜂和啟發(fā)式反向派出偵查蜂.為實(shí)現(xiàn)算法需要, 本文分別設(shè)計(jì)了3個(gè)列表, 如圖5所示, 分別為虛擬機(jī)總表(TotalVmList, 列表1)、虛擬機(jī)分段列表(VmGroupLinkList, 列表2)和未探測(cè)虛擬機(jī)表(UncheckedVmList, 列表3).其中列表1包含了所有虛擬機(jī)的信息, 包括虛擬機(jī)的編號(hào)(VmId)、該虛擬機(jī)的能耗指標(biāo)(EnergyCost, 即EA)及用于標(biāo)記該虛擬機(jī)是否被探測(cè)的標(biāo)記(Check_Flag).列表2則是用于存放經(jīng)蜂群算法探測(cè)后所得的虛擬機(jī)隊(duì)列片段, 其中主要包含了虛擬機(jī)隊(duì)列片段的4個(gè)屬性, 分別為該片段的編號(hào)(LinkId)、該片段的起始虛擬機(jī)位置(Start_Index)、該片段的結(jié)束位置(End_Index)及該片段適應(yīng)度(Fitness).列表3中只有一項(xiàng)屬性, 記錄該虛擬機(jī)隊(duì)列的編號(hào).

當(dāng)啟發(fā)式派出雇傭蜂進(jìn)行探測(cè)后, 先在列表1中根據(jù)探測(cè)結(jié)果對(duì)EnergyCost更新, 并將Check_Flag設(shè)為1, 再在列表3中將該虛擬機(jī)編號(hào)設(shè)為-1.同理, 啟發(fā)式派出跟隨蜂探測(cè)后也先分別對(duì)列表1和列表3進(jìn)行更改, 再根據(jù)列表3中虛擬機(jī)編號(hào)為-1的點(diǎn)對(duì)虛擬機(jī)隊(duì)列進(jìn)行分段, 找出各段的Start_Index和End_Index, 根據(jù)兩端點(diǎn)虛擬機(jī)的能耗指標(biāo)計(jì)算該段的適應(yīng)度(Fitness), 并利用LinkId記錄各段編號(hào), 將各段的信息填入列表2中.最后通過(guò)虛擬機(jī)隊(duì)列各段的Fitness篩選適應(yīng)度概率較小的幾段啟發(fā)式反向派出偵查蜂, 根據(jù)探測(cè)結(jié)果更新列表1～列表3.

本文在整個(gè)ABCS算法過(guò)程中, 設(shè)計(jì)了一個(gè)主算法----派送蜜蜂算法, 它包含了啟發(fā)式派送雇傭蜂算法、啟發(fā)式派送跟隨蜂算法和啟發(fā)式反向派送偵查蜂算法3個(gè)子算法.

算法4派送蜜蜂主算法.

輸入: 未探測(cè)虛擬機(jī)隊(duì)列VM={vm1,vm2,…,vmn}, 蜂群B={b1,b2,…,bn};

輸出： 全局最優(yōu)虛擬機(jī)vmall.

步驟如下：

1) 對(duì)未探測(cè)虛擬機(jī)隊(duì)列VM={vm1,vm2,…,vmn}根據(jù)內(nèi)存利用率從大到小排序, 得到新的虛擬機(jī)隊(duì)列VM={vmi,vmj,…,vmk};

2) 啟發(fā)式派送雇傭蜂, 選擇幾個(gè)點(diǎn)派送雇傭蜂b1,b2,…,bs, 得到一個(gè)局部最優(yōu)解vmj;

3) 啟發(fā)式派跟隨蜂, 根據(jù)派送出的雇傭蜂得到當(dāng)前最優(yōu)解vmj的左右緊鄰vmp和vmq, 派送跟隨蜂進(jìn)行探測(cè), 并找出當(dāng)前最優(yōu)解vmi;

4) 啟發(fā)式反向派偵查蜂, 計(jì)算各段虛擬機(jī)隊(duì)列的適應(yīng)度大小, 向出現(xiàn)最優(yōu)解概率較小虛擬機(jī)隊(duì)列中的某個(gè)虛擬機(jī)隨機(jī)派出偵查蜂進(jìn)行探測(cè), 得到當(dāng)前最優(yōu)解vml;

5) 判斷是否得到全局最優(yōu)解, 若提前遍歷完整個(gè)虛擬機(jī)隊(duì)列, 則跳出循環(huán), 得到全局最優(yōu)解； 否則轉(zhuǎn)2), 直至循環(huán)次數(shù)結(jié)束, 得到全局最優(yōu)解vmall;

6) 算法結(jié)束.

主算法4包含如下3個(gè)子算法.

算法5啟發(fā)式派送雇傭蜂子算法.

輸入： 未探測(cè)虛擬機(jī)隊(duì)列VM={vmi,vmj,…,vmk}, 雇傭蜂Bemployed={bi,bj,…,bk};

輸出： 當(dāng)前最優(yōu)解vmj及其左右鄰居虛擬機(jī)vmp,vmq.

步驟如下：

1) 根據(jù)當(dāng)前虛擬機(jī)列表VM={vmi,vmj,…,vmk}, 啟發(fā)式選擇幾個(gè)點(diǎn)派出雇傭蜂bi,bj,…,bk進(jìn)行探測(cè);

2) 根據(jù)虛擬機(jī)能耗計(jì)算模型, 計(jì)算各個(gè)所探測(cè)虛擬機(jī)的能耗指標(biāo), 獲得當(dāng)前探測(cè)點(diǎn)中的最優(yōu)解vmj;

3) 獲得當(dāng)前最優(yōu)解左右鄰居虛擬機(jī)vmp,vmq(若當(dāng)前最優(yōu)解為隊(duì)列的最左端或最右端, 則左鄰居為其自身, 或右鄰居為自身);

4) 分別更新列表1和列表3;

5) 算法結(jié)束.

算法6啟發(fā)式派跟隨蜂子算法.

輸入： 當(dāng)前最優(yōu)解vmj的左右緊鄰虛擬機(jī)vmp,vmq位置, 跟隨蜂Bonlooker={bi,bj};

輸出： 當(dāng)前最優(yōu)解vmi.

步驟如下：

1) 根據(jù)雇傭蜂獲得的當(dāng)前最優(yōu)解vmj確定左右近鄰虛擬機(jī)vmp,vmq在列表中的位置;

2) 根據(jù)位置信息判斷其是否越出虛擬機(jī)列表的范圍, 并確保其不越界;

3) 派送跟隨蜂bi,bj, 通過(guò)適應(yīng)度函數(shù)計(jì)算近鄰虛擬機(jī)vmp,vmq的遷移適應(yīng)度;

4) 利用函數(shù)EnergyCost對(duì)虛擬機(jī)近鄰能耗遷移成本進(jìn)行計(jì)算, 得到一個(gè)局部最優(yōu)解vmi;

5) 更新列表1、列表2和列表3, 其中列表2中存儲(chǔ)了虛擬機(jī)列表的各段信息;

6) 算法結(jié)束.

算法7啟發(fā)式反向派送偵查蜂子算法.

輸入： 成為最優(yōu)解概率較低虛擬機(jī)片段的虛擬機(jī)隊(duì)列VMscouter={vms,vml,…,vmn}, 偵查蜂Bscouter;

輸出： 局部最優(yōu)解vml.

步驟如下：

1) 從未處理的虛擬機(jī)列表片段中找出適應(yīng)度較小的虛擬機(jī)片段, 并形成虛擬機(jī)隊(duì)列VMscouter={vms,vml,…,vmn};

2) 隨機(jī)選擇其中一個(gè)虛擬機(jī), 派出偵查蜂Bscouter探測(cè), 得到該虛擬機(jī)的能耗指標(biāo);

3) 與當(dāng)前最優(yōu)解比較, 得到一個(gè)局部最優(yōu)解vmm;

4) 更新列表1、列表2和列表3;

5) 算法結(jié)束.

3 實(shí)驗(yàn)數(shù)據(jù)與分析

3.1實(shí)驗(yàn)環(huán)境

CloudSim[9]云計(jì)算模擬器適用于云計(jì)算環(huán)境的模擬, 相比于其他云計(jì)算模擬器(如SimGrid[10]和GangSim[11]等), CloudSim對(duì)數(shù)據(jù)資源的管理更有效, 同時(shí)提供相關(guān)能耗的模擬.因此, 本文選擇CloudSim云計(jì)算模擬器作為模擬平臺(tái).在實(shí)驗(yàn)數(shù)據(jù)上, 本文選擇PlanetLab項(xiàng)目中的實(shí)驗(yàn)數(shù)據(jù).PlanetLab項(xiàng)目[12]由分布于全球的計(jì)算機(jī)群組成, 目前有1 160臺(tái)機(jī)器, 由547個(gè)站點(diǎn)托管, 分布于25個(gè)國(guó)家.它的實(shí)驗(yàn)數(shù)據(jù)具有數(shù)據(jù)量巨大、數(shù)據(jù)類型繁多、價(jià)值密度低和處理速度快等特點(diǎn).本文選擇PlanetLab項(xiàng)目云計(jì)算環(huán)境中的某10 d樣本數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù), 結(jié)果列于表1.仿真中的數(shù)據(jù)中心由800個(gè)異構(gòu)物理節(jié)點(diǎn)組成, 1/2為HP ProLiant ML100 G4服務(wù)器, 另1/2為HP ProLiant ML110 G5服務(wù)器.這兩種服務(wù)器在不同負(fù)載下的能耗特征列于表2.服務(wù)器的CPU頻率用MIPS表示, HP ProLiant ML100 G4服務(wù)器為1 860 Mips, 而HP ProLiant ML110 G5服務(wù)器為2 660 Mips.同時(shí), 每個(gè)服務(wù)器均擁有1 Gb/s的網(wǎng)絡(luò)帶寬.服務(wù)器中的虛擬機(jī)被設(shè)定為單核虛擬機(jī), 內(nèi)存RAM也根據(jù)虛擬機(jī)的多少進(jìn)行劃分.虛擬機(jī)的主要類型有： High-CPU Medium Instance (2 500 Mips, 0.85 Gb), Extra Large Instance (2000 Mips, 3.75 Gb), Small Instance(1 000 Mips, 1.7 Gb), 和Micro Instance (500 Mips, 613 Mb).

表1 PlantLab中某10 d的不同負(fù)載特征Table 1 Workload characteristics of some 10 d in PlantLab

表2 HP G4和HP G5在不同負(fù)載下的能耗Table 2 Power consumption distribution of HP G4 and HP G5 by different workload

3.2模擬結(jié)果與分析

為了評(píng)估云計(jì)算數(shù)據(jù)中心中各種節(jié)能調(diào)度算法, 云計(jì)算模擬器采用幾個(gè)重要參數(shù)進(jìn)行評(píng)估.這些參數(shù)包括總能耗、服務(wù)水平協(xié)議違反率(SLAV)、虛擬機(jī)遷移頻率等[12].其中最重要的是物理節(jié)點(diǎn)能耗和服務(wù)水平協(xié)議違反率.但這兩者是矛盾存在的, 很難同時(shí)得到滿足.要使總能耗得以降低, 勢(shì)必會(huì)降低服務(wù)質(zhì)量, 從而導(dǎo)致服務(wù)水平協(xié)議違反率的值升高.本文的主要目標(biāo)是在服務(wù)水平協(xié)議違反率可容忍的情況下進(jìn)行高效節(jié)能.因此, 一個(gè)由能耗(EC)和服務(wù)水平協(xié)議違反率組成的新參數(shù)可在一定程度上評(píng)估調(diào)度算法的效果.評(píng)估模型如下：

根據(jù)云計(jì)算數(shù)據(jù)中心中虛擬機(jī)動(dòng)態(tài)遷移需要進(jìn)行選擇和分配的特點(diǎn), CloudSim云計(jì)算模擬器中也有自身的虛擬機(jī)選擇策略及分配策略.本文選擇云計(jì)算模擬器CloudSim中自帶的虛擬機(jī)分配策略(THR,IQR,MAD)與虛擬機(jī)選擇策略(MMT,MU,RS), 并結(jié)合啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS), 將3個(gè)虛擬機(jī)分配策略與4個(gè)虛擬機(jī)選擇策略相互組合, 模擬云計(jì)算數(shù)據(jù)中心在10 d不同負(fù)載情況下選擇不同選擇和分配策略組合的運(yùn)行狀況, 得到整個(gè)數(shù)據(jù)中心在不同選擇和分配策略組合下每天的能耗指標(biāo)及其他相關(guān)指標(biāo), 實(shí)驗(yàn)結(jié)果如圖6～圖9所示.

其中每個(gè)虛擬機(jī)分配策略對(duì)應(yīng)4個(gè)選擇策略, 通過(guò)ABCS分別與虛擬機(jī)選擇策略IQR,THR,MAD結(jié)合所得的實(shí)驗(yàn)結(jié)果用紅色線框與黃色方塊表示, 其他3個(gè)虛擬機(jī)選擇策略所得結(jié)果則用黑色線框與灰色方塊表示.通過(guò)Boxplot展示同一分配策略與不同選擇策略匹配使用的運(yùn)行結(jié)果.

a.IQR_ABCS_1.5; b.IQR_MMT_1.5; c.IQR_RS_1.5; d.IQR_MU_1.5; e.THR_ABCS_0.8; f.THR_MMT_0.8; g.THR_RS_0.8; h.THR_MU_0.8; i.MAD_ABCS_2.5; j.MAD_MMT_2.5; k.MAD_RS_2.5; l.MAD_MU_2.5.

a.IQR_ABCS_1.5; b.IQR_MMT_1.5; c.IQR_RS_1.5; d.IQR_MU_1.5; e.THR_ABCS_0.8; f.THR_MMT_0.8; g.THR_RS_0.8; h.THR_MU_0.8; i.MAD_ABCS_2.5; j.MAD_MMT_2.5; k.MAD_RS_2.5; l.MAD_MU_2.5.

a.IQR_ABCS_1.5; b.IQR_MMT_1.5; c.IQR_RS_1.5; d.IQR_MU_1.5; e.THR_ABCS_0.8; f.THR_MMT_0.8; g.THR_RS_0.8; h.THR_MU_0.8; i.MAD_ABCS_2.5; j.MAD_MMT_2.5; k.MAD_RS_2.5; l.MAD_MU_2.5.

a.IQR_ABCS_1.5; b.IQR_MMT_1.5; c.IQR_RS_1.5; d.IQR_MU_1.5; e.THR_ABCS_0.8; f.THR_MMT_0.8; g.THR_RS_0.8; h.THR_MU_0.8; i.MAD_ABCS_2.5; j.MAD_MMT_2.5; k.MAD_RS_2.5; l.MAD_MU_2.5.

由圖6可見(jiàn), 通過(guò)ABCS得到的虛擬機(jī)遷移數(shù)量(VM migration)相比于其他3種虛擬機(jī)選擇算法(MMT,RS,MU)在不同的分配策略(IQR,THR,MAD)中都得到大幅度降低.本文所提出的ABCS算法在1 d的運(yùn)行中遷移次數(shù)約為1 000次, 而其他3種選擇算法則為20 000～80 000次, 極大減少了云計(jì)算數(shù)據(jù)中心中網(wǎng)絡(luò)帶寬的占用率, 優(yōu)化了資源管理.由圖7可見(jiàn), 在CloudSim3.0云計(jì)算模擬器中, 3種虛擬機(jī)選擇算法(MMT,RS,MU)與不同分配策略結(jié)合, 云計(jì)算數(shù)據(jù)中心中所產(chǎn)生總能耗總體持平.但采用啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS)在不同分配策略中較其他3種選擇算法極大地降低了云計(jì)算數(shù)據(jù)中心的能耗(節(jié)省能耗20%～25%), 從而降低了數(shù)據(jù)中心的運(yùn)營(yíng)成本.由圖8可見(jiàn), 啟發(fā)式反向蜂群虛擬機(jī)選擇算法(ABCS)所得的平均服務(wù)水平協(xié)議違反率(ASLAV)相比虛擬機(jī)選擇算法RS和MMT偏高, 相比虛擬機(jī)選擇算法MU偏低, 表明本文提出的ABCS算法仍具有較好的競(jìng)爭(zhēng)力.由圖9可見(jiàn), 啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS)在ESV指標(biāo)上, 仍具有較高的競(jìng)爭(zhēng)力.

綜上可見(jiàn), 啟發(fā)式反向蜂群虛擬機(jī)選擇節(jié)能算法(ABCS)較其他3種虛擬機(jī)選擇算法(MMT,RS,MU)通過(guò)能級(jí)數(shù)級(jí)降低虛擬機(jī)遷移次數(shù), 并在可容忍服務(wù)水平協(xié)議違反率(SLAV)下, 能有效降低云計(jì)算數(shù)據(jù)中心的能耗, 減少了CO2的排放, 節(jié)約了云計(jì)算數(shù)據(jù)中心的運(yùn)營(yíng)成本.

[1]Kosar T.A New Paradigm in Data Intensive Computing: Stork and the Data-Aware Schedulers [C]//Challenges of Large Applications in Distributed Environments.Paris: IEEE, 2006: 5-12.

[2]Kosar T, Balman M.A New Paradigm: Data-Aware Scheduling in Grid Computing [J].Future Generation Computer Systems, 2009, 25(4): 406-413.

[3]LIU Liang, WANG Hao, LIU Xue, et al.GreenCloud: A New Architecture for Green Data Center [C]//Proceedings of the 6th International Conference Industry Session on Autonomic Computing and Communications Industry Session.New York: ACM, 2009: 29-38.

[4]Bohrer P, Elnozahy E N, Keller T, et al.Power Aware [M].[S.l.]: Springer, 2002: 261-289.

[5]韓制坤.基于虛擬化技術(shù)的集群自適應(yīng)功耗管理 [D].上海: 上海交通大學(xué), 2012.(HAN Zhikun.The Application of Virtualization in the Cluster Adaptive Power Management [D].Shanghai: Shanghai Jiaotong University, 2012.)

[6]張超群, 鄭建國(guó), 王翔.蜂群算法研究綜述 [J].計(jì)算機(jī)應(yīng)用研究, 2011, 28(9): 3201-3205.(ZHANG Chaoqun, ZHENG Jianguo, WANG Xiang.Overview of Research on Bee Colony Algorithms [J].Application Research of Computers, 2011, 28(9): 3201-3205.)

[7]Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization [R].Erciyes: Erciyes University, 2005.

[8]Kansal A, ZHAO Feng, LIU Jie, et al.Virtual Machine Power Metering and Provisioning [C]//Proceedings of the 1st ACM Symposium on Cloud Computing.New York: ACM, 2010: 39-50.

[9]Calheiros R N, Ranjan R, Beloglazov A, et al.CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms [J].Software: Practice and Experience, 2011, 41(1): 23-50.

[10]Casanova H.Simgrid: A Toolkit for the Simulation of Application Scheduling [C]//Proceedings First IEEE/ACM International Symposium on Cluster Computing and the Grid.Brisbane: IEEE, 2001: 430-437.

[11]Dumitrescu C L, Foster I.GangSim: A Simulator for Grid Scheduling Studies [C]//IEEE International Symposium on Cluster Computing and the Grid.Washington DC: IEEE, 2005: 1151-1158.

[12]Boglazov A.Energy-Efficient Management of Virtual Machines in Data Centers for Cloud Computing [D].Melbourne: The University of Melbourne, 2013.

VMSelectionEnergy-EfficiencyAlgorithmBasedonHeuristicBackwardArtificialBeeColonyMethodinDataClouds

JIANG Jianhua1,2, LIU Yu2, WANG Limin2, CHEN Jian1, HUANG Na1,3, WEI Xiaohui4
(1.LaboratoryofLogisticsIndustryEconomyandIntelligentLogistics,JilinUniversityofFinanceandEconomics,Changchun130117,China; 2.SchoolofManagementScienceandInformationEngineering,
JilinUniversityofFinanceandEconomics,Changchun130117,China; 3.SchoolofInformationManagementandEngineering,ShanghaiUniversityofFinanceandEconomics,Shanghai
200433,China; 4.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)

Energy-efficiency is a crucial issue in data center.Since data-intensive jobs have the characteristics of frequently reading and writing operations, CPU and RAM utilization rates are considered as two important influencing factors to make energy-efficiency evaluation model.Artificial bee colony algorithm and heuristic backward thinking were applied to VM selection phase in VM migration policy to save energy.Compared with MMT,RS and MU algorithms in CloudSim, the proposed VM selection algorithm, ABCS, made energy 20%—25% saved and VM migration frequency less than 5%.

cloud computing; VM migration; VM selection; artificial bee colony algorithm

2014-03-21.

姜建華(1979—), 男, 漢族, 博士, 副教授, 從事云計(jì)算和商務(wù)智能的研究, E-mail: jianhuajiang@foxmail.com.通信作者： 王麗敏(1975—), 女, 漢族, 博士, 教授, 從事智能計(jì)算的研究, E-mail: wlm_new@163.com; 魏曉輝(1972—), 男, 漢族, 博士, 教授, 博士生導(dǎo)師, 從事云計(jì)算的研究, E-mail: weixh@jlu.edu.cn.

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào)： 61170004; 61202306)、吉林省教育廳基金(批準(zhǔn)號(hào)： 2012188)和吉林財(cái)經(jīng)大學(xué)科研項(xiàng)目(批準(zhǔn)號(hào): XJ2012007； 2013006).

TP316

A

1671-5489(2014)06-1239-10

10.13413/j.cnki.jdxblxb.2014.06.26

韓 嘯)