田苗苗，李 ?。ㄖ袊茖W(xué)技術(shù)大學(xué) 自動化系，安徽 合肥 230026）

面向低能耗的虛擬機部署和遷移策略

田苗苗，李 俊
（中國科學(xué)技術(shù)大學(xué) 自動化系，安徽 合肥 230026）

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

數(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)于虛擬機部署和遷移算法的研究。參考文獻［4］提出了一種面向系統(tǒng)能耗優(yōu)化的虛擬機部署算法，該算法能夠有效降低能耗，但最終部署結(jié)果不是最優(yōu)結(jié)果。參考文獻［6］為了降低能耗給出了一種節(jié)能算法，并提到遷移時間的概念，但在遷移虛擬機時沒有考慮遷移時間。參考文獻［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≤其中，h（j）是虛擬機 j被分配到的主機，vrjl是虛擬機 j的第l種資源量，hril是主機 i的第 l種資源量，powi是主機i的能耗。對于集成DVFS技術(shù)的主機，開啟時可根據(jù)參考文獻［8］提出的能耗模型計算powi：其中，ui是主機 i的 CPU利用率，pmin是空閑狀態(tài)下的能耗，pmax是 ui最大時的能耗。

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

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

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

3 仿真實驗和分析

3.1 實驗環(huán)境

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

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

表1 主機配置

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

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

表2 虛擬機配置

表3 應(yīng)用負載

3.2 實驗結(jié)果

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

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

圖1 虛擬機部署算法比較

圖2 虛擬機遷移算法比較

4 結(jié)論

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

［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)境下改進能源效率和網(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.

圖6 服務(wù)器測試視頻數(shù)據(jù)

其中圖6（a）是移動監(jiān)控設(shè)備對采集的視頻數(shù)據(jù)經(jīng)過電子穩(wěn)像處理過的連續(xù)3幀視頻數(shù)據(jù)，圖6（b）是與圖（a）相對應(yīng)的未經(jīng)過設(shè)備端穩(wěn)像處理的視頻數(shù)據(jù)。由圖6可以看出電子穩(wěn)像操作解決了拍攝視頻時的抖動問題。將前端移動監(jiān)控設(shè)備在不同的地方進行測試，系統(tǒng)都可以穩(wěn)定運行。本系統(tǒng)可以廣泛地應(yīng)用于一些無法鋪設(shè)線路的偏遠地區(qū)，解決了傳統(tǒng)監(jiān)控系統(tǒng)中難以鋪設(shè)線路的問題。

參考文獻

［1］何岳.移動監(jiān)控系統(tǒng)研究［J］.信息通信，2012（5）：126-127.

［2］姚楠，余勁.基于云的電力監(jiān)控視頻故障管理系統(tǒng)設(shè)計［J］.電子技術(shù)應(yīng)用，2014，40（6）：140-142.

［3］楊陽，胡永輝.移動監(jiān)控終端無線傳輸系統(tǒng)的設(shè)計與實現(xiàn)［J］.時間頻率學(xué)報，2011，34（1）：27-32.

［4］梁振濤，樊澤明，任永亮，等.基于單片機的移動監(jiān)控系統(tǒng)硬件設(shè)計［J］.微型機與應(yīng)用，2014，33（2）：25-30.

［5］葛虎龍，李安平.高清抖動視頻的實時穩(wěn)像算法［J］.信息通信，2013（6）：41-43.

［6］黃九林.基于塊匹配和直線特征的視頻穩(wěn)像方法研究［D］.大連：大連理工大學(xué)，2014.

（收稿日期：2015-03-28）

作者簡介：

楊云龍（1988-），男，碩士研究生，主要研究方向：多媒體數(shù)字通信。

孟利民（1963-），女，博士，教授，主要研究方向：無線通信與網(wǎng)絡(luò)、智能信息系統(tǒng)、網(wǎng)絡(luò)管理、多媒體數(shù)字通信與網(wǎng)絡(luò)。

Virtual machine deployment and migration strategy for saving energy

Tian Miaomiao，Li Jun
（Department of Automation，University of Science and Technology of China，Hefei 230026，China）

To improve data center′s resources utilization and reduce energy costs，a virtual machine deployment and migration strategy for saving energy has been proposed.The strategy includes a virtual machine deployment algorithm named BT-MPA and migration algorithm named MMT-MMA.BT-MPA achieves initial map from virtual machines to hosts optimally based on backtracking algorithm，MMT-MMA migrates virtual machines dynamically by using the minimum migration time strategy.Simulation results prove the strategy can reduce total energy consumption of data center and avoid unnecessary migration overhead.

data center；virtual machine；dynamic deployment；low energy consumption；dynamic migration

TP391.9

A

1674-7720（2015）18-0023-03

田苗苗，李俊.面向低能耗的虛擬機部署和遷移策略［J］.微型機與應(yīng)用，2015，34（18）：23-25，31.

2015-04-20）

田苗苗（1991-），女，碩士研究生，主要研究方向：云計算。

李俊（1973-），男，博士，副教授，主要研究方向：網(wǎng)絡(luò)控制。