數據云中基于啟發式反向蜂群的虛擬機選擇節能算法

姜建華, 劉 渝, 王麗敏, 陳 堅, 黃 娜,3, 魏曉輝

(1.吉林財經大學 物流產業經濟與智能物流實驗室, 長春 130117； 2.吉林財經大學 管理科學與信息工程學院, 長春 130117；3.上海財經大學 信息管理與工程學院, 上海 200433; 4.吉林大學 計算機科學與技術學院, 長春 130012)

數據云中基于啟發式反向蜂群的虛擬機選擇節能算法

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

(1.吉林財經大學 物流產業經濟與智能物流實驗室, 長春 130117；
2.吉林財經大學 管理科學與信息工程學院, 長春 130117；
3.上海財經大學 信息管理與工程學院, 上海 200433; 4.吉林大學 計算機科學與技術學院, 長春 130012)

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

云計算; 虛擬機遷移; 虛擬機選擇; 人工蜂群算法

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

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

1 人工蜂群算法

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

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

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

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

輸出： 最優蜜源區uj.

步驟如下：

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

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

3) 某雇傭蜂bk卸蜜后, 得到該雇傭蜂偵查過蜜源區的蜜源質量, 并得到一個局部最優蜜源區uk, 之后該雇傭蜂可成為未雇傭蜂或繼續作為雇傭蜂;

4) 當該雇傭蜂bk成為未雇傭蜂時, 可返回步驟1)成為偵查蜂探測蜜源區, 或跟隨舞池中的引領蜂到該蜜源區采蜜;

5) 當該雇傭蜂bk繼續作為雇傭蜂時, 可直接返回該蜜源采蜜, 或作為引領蜂在舞池跳舞以招募未雇傭蜂;

6) 返回的局部最優蜜源區, 如uk,uj,um, 并最終得到一個全局最優的蜜源區;

7) 算法結束.

由圖1和算法1可見, 人工蜂群采蜜行為是一種群體智能行為.雇傭蜂、偵查蜂、未雇傭蜂之間相互協作以提升采蜜效率和質量.在傳統ABC算法中, 食物源的位置表示待優化問題的一個可行解, 食物源的質量表示解的質量, 即適應度; 種群初始化時, 首先隨機產生sn個可行解, 并計算其適應度, 然后根據適應度進行排序, 前50%的蜂為雇傭蜂, 后50%的蜂為跟隨蜂.隨機產生的可行解公式為

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

蜜蜂記錄自己到目前為止的最優解, 并在當前蜜源附近展開領域搜索, 產生一個新位置替代前一個位置, 公式為

其中:k隨機產生且k≠i,k∈{1,2,…,Sn};φij為[-1,1]間的隨機數.

蜜蜂采蜜采用貪婪原則.算法將當前最優解與領域搜索所得的解進行比較.若所得解更優, 則替換當前最優解.其中, 跟隨蜂根據蜜源信息以一定的概率追隨引領蜂, 其概率為

2 ABCS算法

2.1虛擬機選擇問題

在云計算的數據中心中, 虛擬機實時遷移有利于優化計算節點的負載平衡, 提升處理效率, 降低能耗.虛擬機遷移主要涉及源主機選擇、虛擬機選擇、目標主機選擇及實時遷移過程等.其中, 虛擬機選擇是其中的關鍵環節, 因為虛擬機選擇的好壞將直接影響虛擬機遷移的次數、負載的平衡和能源的消耗等.

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

圖2 虛擬機選擇問題示意圖Fig.2 Diagram of VM selection issue

2.2虛擬機能耗評估模型

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

1) 主機CPU的能耗

其中,αCPU和γCPU表示模型的特定常數, 可通過訓練獲得;

2) 虛擬機A的CPU能耗

3) 主機RAM的能耗

其中:αRAM表示內存RAM利用率的參數;γRAM表示常數,αRAM和γRAM可通過訓練獲得；

4) 虛擬機A中RAM的能耗

5) 虛擬機懲罰能耗

6) 虛擬機能耗計算模型

7) 適應度

（10）

2.3虛擬機選擇節能算法

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

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

圖3 T1和T2的內涵示意圖Fig.3 Diagram of T1 and T2 meaning

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

算法2候選源主機隊列選擇算法.

輸入： 所有主機隊列H={h1,h2,…,hn};

輸出： 候選遷移主機隊列CMQ={hj,hk,…,hm}.

步驟如下：

1) 將所有主機H={h1,h2,…,hn}都被標記為未被選擇狀態;

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

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

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

5) 算法結束.

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

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

算法3ABCS算法.

輸入: 虛擬機隊列VM={vm1,vm2,…,vmn};

輸出： 返回最佳待遷移虛擬機vmj.

步驟如下：

1) 將所有虛擬機隊列VM={vm1,vm2,…,vmn}都標記為未探測;

2) 設置循環次數為5次;

3) 判斷未探測虛擬機的數量, 如果未探測虛擬機的數量小于10, 則直接遍歷探測所有虛擬機, 找出最優解;

4) 如果未探測虛擬機的數量大于10, 則使用蜂群算法, 每次返回一個局部最優解vmk;

5) 通過局部最優解vmk,…,vmi得到全局最優解vmj, 即全局最佳待遷移虛擬機;

6) 算法結束.

圖5 ABCS中的3個列表結構Fig.5 Data structure of 3 lists in ABCS

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

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

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

本文在整個ABCS算法過程中, 設計了一個主算法----派送蜜蜂算法, 它包含了啟發式派送雇傭蜂算法、啟發式派送跟隨蜂算法和啟發式反向派送偵查蜂算法3個子算法.

算法4派送蜜蜂主算法.

輸入: 未探測虛擬機隊列VM={vm1,vm2,…,vmn}, 蜂群B={b1,b2,…,bn};

輸出： 全局最優虛擬機vmall.

步驟如下：

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

2) 啟發式派送雇傭蜂, 選擇幾個點派送雇傭蜂b1,b2,…,bs, 得到一個局部最優解vmj;

3) 啟發式派跟隨蜂, 根據派送出的雇傭蜂得到當前最優解vmj的左右緊鄰vmp和vmq, 派送跟隨蜂進行探測, 并找出當前最優解vmi;

4) 啟發式反向派偵查蜂, 計算各段虛擬機隊列的適應度大小, 向出現最優解概率較小虛擬機隊列中的某個虛擬機隨機派出偵查蜂進行探測, 得到當前最優解vml;

5) 判斷是否得到全局最優解, 若提前遍歷完整個虛擬機隊列, 則跳出循環, 得到全局最優解； 否則轉2), 直至循環次數結束, 得到全局最優解vmall;

6) 算法結束.

主算法4包含如下3個子算法.

算法5啟發式派送雇傭蜂子算法.

輸入： 未探測虛擬機隊列VM={vmi,vmj,…,vmk}, 雇傭蜂Bemployed={bi,bj,…,bk};

輸出： 當前最優解vmj及其左右鄰居虛擬機vmp,vmq.

步驟如下：

1) 根據當前虛擬機列表VM={vmi,vmj,…,vmk}, 啟發式選擇幾個點派出雇傭蜂bi,bj,…,bk進行探測;

2) 根據虛擬機能耗計算模型, 計算各個所探測虛擬機的能耗指標, 獲得當前探測點中的最優解vmj;

3) 獲得當前最優解左右鄰居虛擬機vmp,vmq(若當前最優解為隊列的最左端或最右端, 則左鄰居為其自身, 或右鄰居為自身);

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

5) 算法結束.

算法6啟發式派跟隨蜂子算法.

輸入： 當前最優解vmj的左右緊鄰虛擬機vmp,vmq位置, 跟隨蜂Bonlooker={bi,bj};

輸出： 當前最優解vmi.

步驟如下：

1) 根據雇傭蜂獲得的當前最優解vmj確定左右近鄰虛擬機vmp,vmq在列表中的位置;

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

3) 派送跟隨蜂bi,bj, 通過適應度函數計算近鄰虛擬機vmp,vmq的遷移適應度;

4) 利用函數EnergyCost對虛擬機近鄰能耗遷移成本進行計算, 得到一個局部最優解vmi;

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

6) 算法結束.

算法7啟發式反向派送偵查蜂子算法.

輸入： 成為最優解概率較低虛擬機片段的虛擬機隊列VMscouter={vms,vml,…,vmn}, 偵查蜂Bscouter;

輸出： 局部最優解vml.

步驟如下：

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

2) 隨機選擇其中一個虛擬機, 派出偵查蜂Bscouter探測, 得到該虛擬機的能耗指標;

3) 與當前最優解比較, 得到一個局部最優解vmm;

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

5) 算法結束.

3 實驗數據與分析

3.1實驗環境

CloudSim[9]云計算模擬器適用于云計算環境的模擬, 相比于其他云計算模擬器(如SimGrid[10]和GangSim[11]等), CloudSim對數據資源的管理更有效, 同時提供相關能耗的模擬.因此, 本文選擇CloudSim云計算模擬器作為模擬平臺.在實驗數據上, 本文選擇PlanetLab項目中的實驗數據.PlanetLab項目[12]由分布于全球的計算機群組成, 目前有1 160臺機器, 由547個站點托管, 分布于25個國家.它的實驗數據具有數據量巨大、數據類型繁多、價值密度低和處理速度快等特點.本文選擇PlanetLab項目云計算環境中的某10 d樣本數據作為實驗數據, 結果列于表1.仿真中的數據中心由800個異構物理節點組成, 1/2為HP ProLiant ML100 G4服務器, 另1/2為HP ProLiant ML110 G5服務器.這兩種服務器在不同負載下的能耗特征列于表2.服務器的CPU頻率用MIPS表示, HP ProLiant ML100 G4服務器為1 860 Mips, 而HP ProLiant ML110 G5服務器為2 660 Mips.同時, 每個服務器均擁有1 Gb/s的網絡帶寬.服務器中的虛擬機被設定為單核虛擬機, 內存RAM也根據虛擬機的多少進行劃分.虛擬機的主要類型有： 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的不同負載特征Table 1 Workload characteristics of some 10 d in PlantLab

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

3.2模擬結果與分析

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

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

其中每個虛擬機分配策略對應4個選擇策略, 通過ABCS分別與虛擬機選擇策略IQR,THR,MAD結合所得的實驗結果用紅色線框與黃色方塊表示, 其他3個虛擬機選擇策略所得結果則用黑色線框與灰色方塊表示.通過Boxplot展示同一分配策略與不同選擇策略匹配使用的運行結果.

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

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

[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]韓制坤.基于虛擬化技術的集群自適應功耗管理 [D].上海: 上海交通大學, 2012.(HAN Zhikun.The Application of Virtualization in the Cluster Adaptive Power Management [D].Shanghai: Shanghai Jiaotong University, 2012.)

[6]張超群, 鄭建國, 王翔.蜂群算法研究綜述 [J].計算機應用研究, 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—), 男, 漢族, 博士, 副教授, 從事云計算和商務智能的研究, E-mail: jianhuajiang@foxmail.com.通信作者： 王麗敏(1975—), 女, 漢族, 博士, 教授, 從事智能計算的研究, E-mail: wlm_new@163.com; 魏曉輝(1972—), 男, 漢族, 博士, 教授, 博士生導師, 從事云計算的研究, E-mail: weixh@jlu.edu.cn.

國家自然科學基金(批準號： 61170004; 61202306)、吉林省教育廳基金(批準號： 2012188)和吉林財經大學科研項目(批準號: XJ2012007； 2013006).

TP316

A

1671-5489(2014)06-1239-10

10.13413/j.cnki.jdxblxb.2014.06.26

韓 嘯)