劉丹，隋欣，2，李莉

（1.長春理工大學　計算機科學技術學院，長春　130022；

2.吉林省教育學院　職業(yè)與成人教育教研培訓學院，長春　130022）

基于云計算的虛擬機放置節(jié)能優(yōu)化算法

劉丹1，隋欣1，2，李莉1

（1.長春理工大學計算機科學技術學院，長春130022；

2.吉林省教育學院職業(yè)與成人教育教研培訓學院，長春130022）

多數(shù)企業(yè)都會將數(shù)據(jù)部署到云數(shù)據(jù)中心，這使得能耗問題變得突出。本文針對數(shù)據(jù)中心的能耗問題進行討論研究，通過對虛擬機放置模型的改進，實現(xiàn)了全局遺傳算法的優(yōu)化。全局遺傳算法的實現(xiàn)過程包括編解碼、種群初始化、交叉算子等遺傳算子。實驗結果表明，優(yōu)化后的全局遺傳算法能夠有效的降低云數(shù)據(jù)中心的耗能，具有一定的應用價值。

云計算；遺傳算法；虛擬機；節(jié)能

云計算是一種新興的服務技術，主要通過互聯(lián)網(wǎng)向用戶提供動態(tài)易擴展的虛擬化資源，完成存儲、計算等服務。與傳統(tǒng)技術相比，云計算具有卓越的優(yōu)點，尤其表現(xiàn)在超大規(guī)模、虛擬化、高可靠性、通用性、高可擴展性、按需服務及極其廉價等方面。越來越多的企業(yè)開始關注、使用云計算平臺，這就使得云數(shù)據(jù)中心的規(guī)模不斷擴大，數(shù)據(jù)中心的運營成本逐步增加，能耗問題日益突出。

數(shù)據(jù)中心能耗成本與服務器資源利用率，兩者之間有著密切的聯(lián)系。如何提高資源利用率、降低能耗，最終降低云數(shù)據(jù)中心的運營成本，是一個值得探討的問題。虛擬化技術可以較好地解決高性能的物理機產(chǎn)能過剩和老舊物理機能效過低的問題。通過虛擬化技術可以有效提高數(shù)據(jù)中心資源，使得服務器資源得以充分利用。

云數(shù)據(jù)中心普遍利用虛擬化技術，將一臺物理機可以實例化多個虛擬機；同樣，也可將多臺物理機可以虛擬化成一臺虛擬機［1，2］，這使得虛擬機放置模型成為云數(shù)據(jù)中心資源分配的關鍵問題。目前，關于虛擬化放置模型的算法有很多，但是其中都存在著一些不足之處。本文提出一種改進的虛擬機靜態(tài)放置模型，擬采用全局優(yōu)化遺傳算法（記為CVMGA）解決云數(shù)據(jù)中心虛擬機靜態(tài)放置問題。

1　能耗優(yōu)化模型

數(shù)據(jù)中心的主要能耗集中在服務器。構成服務器的部件包括CPU、硬盤、內(nèi)存、網(wǎng)卡等。其中，由于CPU是能耗消耗的主要部件，因而其利用率與服務器利用率之間，有著較密切的關系。根據(jù)文獻顯示，兩者之間可以近似看成是線性關系。如公式（1）所示：

表1　放置虛擬機限制條件表

服務器在某時間間隔的能耗可以表示為如公式（2）所示：

其中，P（u）為物理服務器的功率；c為物理服務器空載與滿載時的功率比；Pmax為物理服務器滿載時的功率；u為物理服務器CPU使用率；E為物理服務器在時間［t1，t2］間的能耗。

假設數(shù)據(jù)中心有n臺服務器組建而成，故整個數(shù)據(jù)中心能耗總值應為各服務器能耗之和。因而可得：

F是本文想達到的目標值。

物理服務器能耗與虛擬機的放置策略存在著較大的關系。同一臺服務器在同一時間間隔里，會因虛擬機的配置參數(shù)的不同，所消耗的能量也不同。考慮到物理服務器中，主要能耗部件有CPU、內(nèi)存、硬盤等，故在放置虛擬機的時候，增加一些限制條件，如表1所示。

在表1中m代表請求的虛擬機數(shù)量，n為物理服務器數(shù)量，V（cpu，j）、V（mem，j）、V（store，j）是虛擬機j對CPU、內(nèi)存和硬盤的請求大小，C（cpu，i）、C（mem，i）、C（store，i）是物理服務器i的CPU、內(nèi)存和硬盤實際大小。

2　全局優(yōu)化遺傳算法

為了對目標值F進行求解，本文建立了大規(guī)模虛擬機放置模型。通過編解碼方法、種群初始化等，改進了全局優(yōu)化遺傳算法。

2.1編解碼

在編碼過程中，假定虛擬機的數(shù)量為m，服務器的數(shù)量為n，所以染色體長度為m?n。編碼中每m個為一組，共n組，編碼表示為P=｛［P（1，1），P（1，2），…，P（1，j），…，P（1，m）］，［P（2，1），P （2，2），…，P（2，j），…，P（2，m）］，…，［P（i，1），P（i，2），…，P（i，j），…，P（i，m）］，…，［P（n，1），P（n，2），…，P（n，j），…，P（n，m）］｝。其中P（i，j）=1表示虛擬機j分配到服務器i上，P（i，j）=0表示虛擬機j沒有分配到服務器i上。

2.2種群初始化

由上文可知，一個虛擬機只能分配到一臺物理機上，可以根據(jù)這個規(guī)則初始化種群，種群初始化規(guī)則如下：

Fori=1；i＜=n；i++；

Forj=1；j＜=m；j++；

P（i，j）=1；

根據(jù)限定條件：P（1，j）+P（2，j）+…+ P（n，j）=1；P（i，j）=0或1；其中i=1，2，…，n；

j=1，2，…，m，將其余的P（i，j）置為0；

Endfor

Endfor

2.3交叉算子

交叉算子的具體步驟如下所示，其輸入為兩個父代種群個體P1和P2，輸出為兩個后代種群個體P1′和P2′。需要注意的是，由該交叉算子產(chǎn)生的放置策略可能是不可行方案，通過修正算子將其修正為可行的方案。

隨機生成四個整數(shù)a、b和c、d，a、c∈［1，N］，b、d∈［1，M］且a＜=c。

按照下面的方式交叉向量P1和P2，生成P1′和P2′，如表2所示。

表2　交叉過程向量變化表

2.4變異算子

變異算子算法如下所示，其輸入為種群個體P和變異概率Pm，其輸出為變異后代種群個體P′。需要注意的是，由該變異算子產(chǎn)生的放置策略可能是不可行方案，通過修正算子將其修正為可行的。

P′=P；

Forj=1；j＜=m；j++；

隨機生成一個實數(shù)a∈［0，1］；

Ifa＜=Pm

從種群P′中隨機選擇一個P（i，j）=1，隨機生成一個整數(shù)b∈［1，N］且b≠i；

令P（b，j）=1，P（i，j）=0；

Endif

Endfor

2.5修正算子

根據(jù)上文可知，放置在一臺物理服務器上的全部虛擬機的CPU總量、內(nèi)存總量、硬盤總量不能超過該臺服務器的CPU、內(nèi)存和硬盤大小。但是，無論是種群初始化、交叉算子、變異算子所產(chǎn)生的后代種群個體都不能保證方案全部是可行的，所以需要將產(chǎn)生的后代種群個體修正為可行的方案。修正算子的實現(xiàn)具體步驟如下所示，其中輸入為種群個體P，輸出為修正后的種群個體P′，滿足公式（4）、（5）、（6）的約束條件。

從種群P'中隨機選擇一個P（i，j）=1，隨機生成一個整數(shù)a∈［1，N］且a≠i，

令P（a，j）=1，P（i，j）=0；

轉(zhuǎn)到本算法第2行；

Endif

Endfor

2.6局部搜索算子

增加局部搜索算子，目的是為了加速算法的收斂速度。由公式（3）可知，虛擬機放置到服務器后，耗能越小說明個體越優(yōu)。因此，本算法將耗能大的放置策略進行重新分配。如果重新分配后的種群優(yōu)于當前種群，則更新當前種群，進入下一次迭代循環(huán)，否則終止局部搜索。局部搜索算子的具體實現(xiàn)過程如下所示，其輸入為種群個體P，輸出為局部優(yōu)化后的種群個體P′。

從種群列表P中找出∑i=1nEi值最大的種群個體P，令P′=P；

從種群P′中隨機選擇一個P（i，j）=1，隨機生成一個整數(shù) a∈［1，N］且 a≠i，令 P（a，j）=1，P（i，j）=0；

轉(zhuǎn)到本算法第一行；

3　仿真實驗與結果分析

3.1參數(shù)設置

在實驗過程中，通過仿真100臺服務器構成了數(shù)據(jù)中心，其中物理服務器有三種類型，具體配置參數(shù)如表3所示。

表3　物理服務器具體配置參數(shù)信息表

同樣，假定放置的虛擬機也有三種類型，具體參數(shù)如表4所示。

表4　虛擬機參數(shù)信息表

在本實驗中，具體參數(shù)設定為c=0.7，種群規(guī)模為100，交叉概率Pc=0.5，變異概率Pm=0.03，終止條件t=1000。

3.2實驗結果與討論

為了驗證改進算法的有效性，與Simulated Annealing算法和Min-Min算法進行了對比實驗。在實驗過程中，主要是從物理服務器啟動數(shù)量、處理器利用率和能量消耗這幾方面進行對比實驗。在本小節(jié)中，S代表Simulated Annealing算法，M代表Min-Min算法，C代表全局優(yōu)化遺傳算法CVMGA。

物理服務器的啟動數(shù)量與虛擬機請求量，兩者之前存在著必然的聯(lián)系。虛擬機請求數(shù)量越多，所需要啟動的物理服務器的數(shù)量也隨之增加。當虛擬機發(fā)出等量的請求，在不同放置算法下，需要啟動的物理服務器數(shù)量，如圖1所示。

圖1　物理服務器啟動數(shù)量示意圖

同樣，虛擬機的請求量也影響著物理服務器的CPU利用率。如圖2所示，隨著請求量的不斷變化，不同算法下的CPU利用率，都在一個區(qū)間內(nèi)波動著。其中，同等虛擬機請求量下，CPU利用率越高，需要啟動的物理機服務器越少，從而減少了能量的消耗。

圖2　CPU利用率示意圖

由于虛擬機的請求數(shù)量，影響著CPU的利用率，與此同時，CPU的利用率與能耗之間存在著關系。因而，可以建立虛擬機的請求數(shù)量與能耗之間的關系，如圖3所示。從圖中不難看出，改進后的算法，在虛擬機請求數(shù)量相同的情況下，所需能耗較小。

圖3　能耗示意圖

4　結束語

數(shù)據(jù)中心的能量消耗問題，是一個值得人們關注的問題。本文通過在虛擬機放置策略上，添加約束條件，提高物理服務器的資源利用率，最終達到減少能源消耗的目的。通過仿真實驗表明，改進后的算法，在同等虛擬機請求數(shù)量上，與其他算法相比，能夠有效減少物理服務器的啟動數(shù)量，從而減少了能量消耗。

［1］ 師雪霖，徐恪.云虛擬機資源分配的效用最大化模型［J］.計算機學報，2013，36（2）：252-256.

［2］ Cardosa M，Korupolu M，Singh A.Shares and utilities based power consolidation in virtualized server environments［C］.In proceedings of the 11th IFIP/ IEEE Integrated Network Management（IM 2009），Long Island，NY，USA，2009：327-334.

［3］Kusic D，Kephart J O，Hanson J E，et al.Power and performancee management of virtualized computing environments via lookahead control［J］.Cluster Computing，2009，12（1）：1-15.

［4］ Gargi Dasgupta，Amit Sharma，Akshat Venna，et al. Workload management for power efficiency in virtualized data centers［J］.Communications of the ACM，2011，54（7）：131-141.

［5］ChenGong，HeWenbo，LiuJie，etal.Energy-aware server provisioning and load dispatching for connection-intensive internet services［C］.In proceeding of the 5th USENIX Symposium on Networked Systems Design and Implementation（NSDI’08），San Francisco，2008：337-350.

［6］ Fan Xiaobo，Weber Wolf-Dietrich，Luiz Andre Barroso.Powerprovisioningforawarehouse-sized computer［J］.ACM SIGARCH Computer Architecture News，2007，35（2）：l3-23.

［7］Anton Beloglazov，Jemal Abawajy，Rajkumar Buyya. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing［J］.FutureGenerationComputerSystems，2012，28（5）：755-768.

［8］ 從立鋼，郭利菊.云存儲系統(tǒng)安全技術研究［J］.長春理工大學學報：自然科學版，2014，37（3）：132-134.

Engry-conservation Placement Algorithm for Virtual Machines Based on Cloud Computing

LIU Dan1，SUI Xin1，2，LI Li1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；2.College of Vocational and Adult Education，Jinlin Provincial Institute of Education，Changchun 130022）

Most of companies will upload their data to Cloud Data Centers，which makes the problem of energy consumption become more and more prominent.However，by discussing and researching the problem，there is way to improve the genetic algorithm by means of optimizing the model of how Virtual Machine placed.The implementation process of global genetic algorithm includes codecs，population initialization，crossover and other genetic operators.The experiment result indicates that the genetic algorithm has much more superiority than traditional algorithm in reducing energy consumption of Cloud Data Centers，which proves its practical application value.

cloud computing；genetic algorithm；virtual machine；energy conservation

P315.69

A

1672-9870（2015）06-0150-04

2015-11-05

劉丹（1983-），女，博士研究生，講師，E-mail：ld_1983@hotmail.com

李莉（1963-）；女，博士，教授，博士生導師，E-mail：ll@cust.edu.cn