摘  要： 為提高數(shù)據(jù)中心的資源利用率并降低能耗，提出了面向低能耗的虛擬機部署和遷移策略，包括虛擬機初始部署算法BT-MPA和虛擬機動態(tài)遷移算法MMT-MMA。BT-MPA算法基于回溯法實現(xiàn)虛擬機集合和主機集合的最優(yōu)初始映射，MMT-MMA算法基于最小遷移時間策略實現(xiàn)虛擬機動態(tài)遷移。仿真驗證了所提出策略能夠在降低數(shù)據(jù)中心總能耗的同時避免了不必要的遷移開銷。

　　關(guān)鍵詞： 數(shù)據(jù)中心；虛擬機；動態(tài)部署；低能耗；動態(tài)遷移

0 引言

　　隨著云計算的快速發(fā)展，數(shù)據(jù)中心能源成本不斷上漲[1]。在2011年，我國數(shù)據(jù)中心總耗電量已經(jīng)占到全社會用電量的1.5%[2]。高能耗的主要原因在于設(shè)備數(shù)量增加和資源使用率低[3]。

　　目前數(shù)據(jù)中心常用的節(jié)能技術(shù)有：動態(tài)電壓頻率調(diào)整（Dynamic Voltage and Frequency Scaling，DVFS）和虛擬化技術(shù)[4]。其中虛擬化技術(shù)能夠?qū)⒁粋€服務(wù)器虛擬成多個服務(wù)器，提高資源的利用率，降低成本[5]。

　　目前有許多關(guān)于虛擬機部署和遷移算法的研究。參考文獻(xiàn)[4]提出了一種面向系統(tǒng)能耗優(yōu)化的虛擬機部署算法，該算法能夠有效降低能耗，但最終部署結(jié)果不是最優(yōu)結(jié)果。參考文獻(xiàn)[6]為了降低能耗給出了一種節(jié)能算法，并提到遷移時間的概念，但在遷移虛擬機時沒有考慮遷移時間。參考文獻(xiàn)[7]提出一種虛擬機放置方案，該方案能夠優(yōu)化能源效率，但沒有涉及遷移問題。

　　基于當(dāng)前研究，本文提出了面向低能耗的虛擬機部署和遷移策略，目的是在最小化數(shù)據(jù)中心能耗的同時保證服務(wù)質(zhì)量。該策略一方面利用回溯法部署虛擬機，使開啟物理機的數(shù)量最??；另一方面為了適應(yīng)虛擬機的動態(tài)變化和避免資源過度聚合，根據(jù)最小遷移時間策略動態(tài)遷移虛擬機，最小遷移時間策略通過貪心算法和動態(tài)規(guī)劃算法實現(xiàn)。

1 虛擬機動態(tài)部署

　　1.1 虛擬機部署問題

　　可將虛擬機部署問題描述為：數(shù)據(jù)中心有n臺主機和m臺等待部署的虛擬機，每臺主機和虛擬機均配置k種資源，目標(biāo)是完成部署后總能耗最小，其中虛擬機的資源總和不能超越主機的資源上限，虛擬機最多只能被部署到一個主機上。

　　以上描述等價為：D=（H1，…，Hn），Hi=（hri1，…，hrik），V=（vm1，…，vmm），vmj=（vrjl，…，vrjk），其中1≤i≤n，1≤j≤m。

　　其中，h（j）是虛擬機j被分配到的主機，vrjl是虛擬機j的第l種資源量，hril是主機i的第l種資源量，powi是主機i的能耗。對于集成DVFS技術(shù)的主機，開啟時可根據(jù)參考文獻(xiàn)[8]提出的能耗模型計算powi：

　　powi=pmin+（pmax-pmin）×ui（2）

　　其中，ui是主機i的CPU利用率，pmin是空閑狀態(tài)下的能耗，pmax是ui最大時的能耗。

　　1.2 基于回溯法的虛擬機動態(tài)部署算法

　　虛擬機部署問題大多是基于貪心算法進(jìn)行優(yōu)化，但該問題不具有貪心選擇性質(zhì)，通過一系列局部最優(yōu)選擇并不能得到整體最優(yōu)解。為了最小化能耗，本文基于回溯法提出了一個虛擬機部署算法BT-MPA?；厮莘ㄔ谔摂M機部署問題的解空間子集樹中按照深度優(yōu)先策略搜索，若搜索過程中當(dāng)前的擴展節(jié)點不滿足不等式（1）則跳過，否則進(jìn)入該子樹繼續(xù)搜索，直至找到最優(yōu)解[9]。

　　BT-MPA的步驟是：首先將主機按照開啟關(guān)閉狀態(tài)排序，相同狀態(tài)的主機按照可用資源大小降序排列；接著依次選擇主機，用回溯法從虛擬機集合中選出最優(yōu)子集部署到主機中；然后從集合中移除已被部署的虛擬機，繼續(xù)以上步驟直至虛擬機集合為空。

2 虛擬機動態(tài)遷移

　　虛擬機遷移問題可分為兩個子問題：何時觸發(fā)遷移和選擇哪些虛擬機遷移。

　　2.1 觸發(fā)遷移

　　本文設(shè)定資源利用率上限閾值Tup和下限閾值Tdown，當(dāng)主機處于以下情況時觸發(fā)遷移：（1）資源利用率大于Tup，說明主機處于過載狀態(tài)，需遷出某些虛擬機，以避免降低用戶體驗；（2）資源利用率小于Tdown，需遷出所有虛擬機并關(guān)閉主機，以降低能耗。由于虛擬機對CPU的競爭最為激烈，故遷移時僅考慮CPU資源，用MIPS指標(biāo)來衡量。

　　2.2 選擇虛擬機

　　過載主機中虛擬機的選擇有隨機和最小遷移時間（Minimum Migration Time，MMT）兩種策略。MMT策略是選擇遷移時間最小的虛擬機集合遷出，它等價于選擇一組總遷移時間最大的虛擬機集合留在主機上：

　　其中，uj（cpu）是虛擬機j使用的CPU和主機總CPU的比值[7]，mtj是遷移時間，用虛擬機內(nèi)存與所在主機空閑帶寬的比值衡量[3]。式（3）具有最優(yōu)子結(jié)構(gòu)性質(zhì)，能夠使用貪心和動態(tài)規(guī)劃算法來解決。

　　2.2.1 貪心選擇策略

　　使用貪心算法解決MMT問題的步驟是：首先將虛擬機按照遷移時間與MIPS的比值非降序排列，然后依次選擇虛擬機加入遷出隊列，直至主機的CPU利用率不大于Tup。該算法的時間復(fù)雜度為O（nlogn）[9]。

　　2.2.2 動態(tài)規(guī)劃選擇策略

　　動態(tài)規(guī)劃將問題分解成若干子問題，通過結(jié)合子問題的解得到最終解[9]。假設(shè)F（j，ri）是子問題的最優(yōu)解，則可以建立如下遞歸關(guān)系：

　　F（j，ri）=max{F（j-1，ri），F(xiàn)（j-1，ri-mj）+mtj}，ri≥mjF（j-1，ri），                     ri<mj（4）

　　其中，F(xiàn)（j，ri）指的是當(dāng)主機CPU值為ri，虛擬機集合為1，…，j時的最大遷移時間，mj是虛擬機j的CPU資源值。

　　該策略能得到式（3）的最優(yōu)解，最優(yōu)解對應(yīng)的虛擬機就是留在主機上的最優(yōu)集合。該算法的時間復(fù)雜度是O（2n）[9]。

　　2.3 虛擬機遷移算法

　　本文基于以上策略提出了虛擬機遷移算法MMT-MMA，具體步驟是：周期性地檢測開啟主機的CPU利用率，如果大于Tup，則使用虛擬機選擇策略得到遷出虛擬機集合，將其加入遷出隊列；如果小于Tdown，則將其上的虛擬機全部加入遷出隊列，最后將遷出的虛擬機隊列按照BT-MPA算法重新部署。

3 仿真實驗和分析

　　3.1 實驗環(huán)境

　　為驗證本文提出算法的有效性，進(jìn)行了兩組仿真實驗，每組實驗均進(jìn)行15次，取平均值作為最終結(jié)果。實驗設(shè)置Tup為0.8，Tdown為0.2。

　　首先在仿真系統(tǒng)中建立1個數(shù)據(jù)中心和20臺主機，主機的資源根據(jù)表1隨機配置。

　　系統(tǒng)中需部署的虛擬機數(shù)量范圍是[10，80]，增加步長為10，虛擬機的資源根據(jù)表2隨機配置。

　　虛擬機上運行的應(yīng)用負(fù)載按照占用虛擬機資源的比例可分為輕、中、重三型，不同型號虛擬機上運行負(fù)載的概率空間相同，如表3所示。

　　3.2 實驗結(jié)果

　　圖1是使用本文提出的BT-MPA算法與基于貪心算法的Greedy-MPA進(jìn)行虛擬機部署后的能耗比較圖，從圖可知BT-MPA在節(jié)能方面優(yōu)于常用的Greedy-MPA，數(shù)據(jù)中心總能耗相對于Greedy-MPA算法平均降低9.7%，達(dá)到了更好的節(jié)能效果。

　　圖2是使用不同的虛擬機選擇策略進(jìn)行動態(tài)遷移的結(jié)果。從圖可看出，基于MMT選擇策略的遷移時間遠(yuǎn)遠(yuǎn)低于RC策略，貪心選擇策略的遷移時間相對于RC策略平均減少48%，動態(tài)規(guī)劃選擇策略相對于RC策略平均降低57%，動態(tài)規(guī)劃相對于貪心選擇策略平均降低18%。這也與理論相符合，動態(tài)規(guī)劃較貪心選擇策略結(jié)果更優(yōu)，但時間復(fù)雜度更大，因此數(shù)據(jù)中心可綜合考慮遷移時間和計算時間來選擇具體策略。

4 結(jié)論

　　為降低數(shù)據(jù)中心的能耗，本文提出了虛擬機部署算法BT-MPA和虛擬機遷移算法MMT-MMA。通過仿真驗證了BT-MPA能夠有效降低數(shù)據(jù)中心總能耗，實現(xiàn)節(jié)能減排的目的，同時表明了MMT-MMA能夠有效減少虛擬機遷移時間，避免不必要的遷移開銷。本文在觸發(fā)遷移時使用的是固定閾值，為了更靈活地應(yīng)對負(fù)載變化，接下來將針對自適應(yīng)閾值展開研究。

參考文獻(xiàn)

　　[1] SCHULZ G. 綠色虛擬數(shù)據(jù)中心[M].韓毅剛，李亞娜，王歡，譯.北京：人民郵電出版社，2010.

　　[2] 王肇國，易涵，張為華.基于機器學(xué)習(xí)特性的數(shù)據(jù)中心能耗優(yōu)化方法[J].軟件學(xué)報，2014，25（7）：1432-1447.

　　[3] BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computat-ion： Practice and Experience， 2012（24）：1397-1420.

　　[4] 王加昌，曾輝，何騰蛟，等.面向數(shù)據(jù)中的虛擬機部署及優(yōu)化算法[J].計算機應(yīng)用，2013，33（10）：2772-2777.

　　[5] 高林，宋相倩，王潔萍.云計算及其關(guān)鍵技術(shù)研究[J].微型機與應(yīng)用，2011，30（10）：5-7.

　　[6] 周舟，胡志剛.云環(huán)境下面向能耗降低的虛擬機部署算法[J].華南理工大學(xué)學(xué)報，2014，42（5）：109-114.

　　[7] 董健康，王洪波.IaaS環(huán)境下改進(jìn)能源效率和網(wǎng)絡(luò)性能的虛擬機放置方法[J].通信學(xué)報，2014，35（1）：72-81.

　　[8] BELOGLAZOV A， ABAWAJY J， BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing[J]. Future Generation Computer Systems， 2012（28）：755-768.

　　[9] 王曉東.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社，2012.