劉丹，隋欣，2，李莉

（1.長(zhǎng)春理工大學(xué)　計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春　130022；

2.吉林省教育學(xué)院　職業(yè)與成人教育教研培訓(xùn)學(xué)院，長(zhǎng)春　130022）

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

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

（1.長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春130022；

2.吉林省教育學(xué)院職業(yè)與成人教育教研培訓(xùn)學(xué)院，長(zhǎng)春130022）

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

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

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

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

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

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

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

表1　放置虛擬機(jī)限制條件表

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

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

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

F是本文想達(dá)到的目標(biāo)值。

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

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

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

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

2.1編解碼

在編碼過程中，假定虛擬機(jī)的數(shù)量為m，服務(wù)器的數(shù)量為n，所以染色體長(zhǎng)度為m?n。編碼中每m個(gè)為一組，共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ī)j分配到服務(wù)器i上，P（i，j）=0表示虛擬機(jī)j沒有分配到服務(wù)器i上。

2.2種群初始化

由上文可知，一個(gè)虛擬機(jī)只能分配到一臺(tái)物理機(jī)上，可以根據(jù)這個(gè)規(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交叉算子

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

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

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

表2　交叉過程向量變化表

2.4變異算子

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

P′=P；

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

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

Ifa＜=Pm

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

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

Endif

Endfor

2.5修正算子

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

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

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

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

Endif

Endfor

2.6局部搜索算子

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

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

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

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

3　仿真實(shí)驗(yàn)與結(jié)果分析

3.1參數(shù)設(shè)置

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

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

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

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

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

3.2實(shí)驗(yàn)結(jié)果與討論

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

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

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

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

圖2　CPU利用率示意圖

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

圖3　能耗示意圖

4　結(jié)束語(yǔ)

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

［1］ 師雪霖，徐恪.云虛擬機(jī)資源分配的效用最大化模型［J］.計(jì)算機(jī)學(xué)報(bào)，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］ 從立鋼，郭利菊.云存儲(chǔ)系統(tǒng)安全技術(shù)研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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-）；女，博士，教授，博士生導(dǎo)師，E-mail：ll@cust.edu.cn