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

　　關鍵詞： 數據中心；虛擬機；動態部署；低能耗；動態遷移

0 引言

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

　　目前數據中心常用的節能技術有：動態電壓頻率調整（Dynamic Voltage and Frequency Scaling，DVFS）和虛擬化技術[4]。其中虛擬化技術能夠將一個服務器虛擬成多個服務器，提高資源的利用率，降低成本[5]。

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

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

1 虛擬機動態部署

　　1.1 虛擬機部署問題

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

　　以上描述等價為：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技術的主機，開啟時可根據參考文獻[8]提出的能耗模型計算powi：

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

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

　　1.2 基于回溯法的虛擬機動態部署算法

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

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

2 虛擬機動態遷移

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

　　2.1 觸發遷移

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

　　2.2 選擇虛擬機

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

　　其中，uj（cpu）是虛擬機j使用的CPU和主機總CPU的比值[7]，mtj是遷移時間，用虛擬機內存與所在主機空閑帶寬的比值衡量[3]。式（3）具有最優子結構性質，能夠使用貪心和動態規劃算法來解決。

　　2.2.1 貪心選擇策略

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

　　2.2.2 動態規劃選擇策略

　　動態規劃將問題分解成若干子問題，通過結合子問題的解得到最終解[9]。假設F（j，ri）是子問題的最優解，則可以建立如下遞歸關系：

　　F（j，ri）=max{F（j-1，ri），F（j-1，ri-mj）+mtj}，ri≥mjF（j-1，ri），                     ri<mj（4）

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

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

　　2.3 虛擬機遷移算法

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

3 仿真實驗和分析

　　3.1 實驗環境

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

　　首先在仿真系統中建立1個數據中心和20臺主機，主機的資源根據表1隨機配置。

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

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

　　3.2 實驗結果

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

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

4 結論

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

參考文獻

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

　　[2] 王肇國，易涵，張為華.基于機器學習特性的數據中心能耗優化方法[J].軟件學報，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] 王加昌，曾輝，何騰蛟，等.面向數據中的虛擬機部署及優化算法[J].計算機應用，2013，33（10）：2772-2777.

　　[5] 高林，宋相倩，王潔萍.云計算及其關鍵技術研究[J].微型機與應用，2011，30（10）：5-7.

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

　　[7] 董健康，王洪波.IaaS環境下改進能源效率和網絡性能的虛擬機放置方法[J].通信學報，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] 王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2012.