云計(jì)算中虛擬機(jī)放置多目標(biāo)優(yōu)化

李碩碩+孫紅

摘 要：提高云計(jì)算系統(tǒng)資源利用率一直是云計(jì)算研究的重點(diǎn)內(nèi)容之一。 基于此，將傳統(tǒng)的多目標(biāo)蟻群算法進(jìn)行改進(jìn)，并結(jié)合排除法解決虛擬機(jī)放置的多目標(biāo)優(yōu)化的問題，該算法可以通過信息素的不斷更新，最終收斂得到最優(yōu)解。主要考慮了服務(wù)級(jí)合約違背率（S）、資源損耗（W）、電源消耗（P）3個(gè)因素。 實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的啟發(fā)式方法和遺傳算法相比，該算法有利于并行計(jì)算，能夠在多個(gè)相互沖突的目標(biāo)間實(shí)現(xiàn)最優(yōu)權(quán)衡和折衷，在服務(wù)級(jí)合約違背率較少的情況下，系統(tǒng)資源浪費(fèi)和電源消耗最少，具有可行性。

關(guān)鍵詞關(guān)鍵詞：云計(jì)算；虛擬機(jī)放置；多目標(biāo)優(yōu)化；蟻群算法；排除法

DOIDOI：10.11907/rjdk.162036

中圖分類號(hào)：TP302

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011000103

基金項(xiàng)目基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目（61170277；61472256）；上海市教委科研創(chuàng)新重點(diǎn)項(xiàng)目（12zz137）；滬江基金項(xiàng)目（C14002）

作者簡介作者簡介：李碩碩（1989-），男，山東菏澤人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)通信與云計(jì)算；孫紅（1964-），女，上海人，博士，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)通信與云計(jì)算、控制科學(xué)與工程、模式識(shí)別與智能系統(tǒng)。

0 引言

云計(jì)算作為一種新技術(shù)，近年來成為信息領(lǐng)域的研究熱點(diǎn)。如今，云計(jì)算已經(jīng)成為通過互聯(lián)網(wǎng)提供訪問和服務(wù)的新型模式。如果資源分布不合理，那么必然會(huì)導(dǎo)致資源浪費(fèi)。實(shí)現(xiàn)虛擬機(jī)放置的多目標(biāo)優(yōu)化具有重要意義。現(xiàn)有研究大多采用傳統(tǒng)的啟發(fā)式方法[1]或者遺傳算法[2]等算法進(jìn)行虛擬機(jī)的放置。雖然這些算法都可以在一定程度上解決虛擬機(jī)放置問題，但是存在各自的局限性。例如，啟發(fā)式方法雖然可以在虛擬機(jī)放置中解決局部最優(yōu)解問題，但該方法缺乏全局尋優(yōu)能力；遺傳算法雖然在多目標(biāo)優(yōu)化方面有一定優(yōu)勢(shì)，但無法充分利用反饋信息，致使搜索具有盲目性，求解到一定范圍時(shí)求解最優(yōu)解的效率比較低。

本文引入本地管理層和全局管理層的管理框架，通過這種管理框架有利于對(duì)虛擬機(jī)的放置和資源的分配作出更好的決策。本文所用方法是對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，并且與排除法相結(jié)合，有利于并行計(jì)算，效率更高。能夠在服務(wù)級(jí)合約違背率（S）、資源損耗（W）、電源消耗（P）3個(gè)相互沖突的目標(biāo)間得到最優(yōu)的權(quán)衡，在服務(wù)級(jí)合約違背率較少的情況下，系統(tǒng)資源浪費(fèi)和電源消耗最少。

1 虛擬機(jī)放置

1.1 管理框架

云計(jì)算中基礎(chǔ)設(shè)施節(jié)點(diǎn)數(shù)量非常龐大，使得建立架構(gòu)非常困難，本文管理框架為兩層管理，分別為本地管理和全局管理，如圖1所示。本地管理管理主機(jī)等云基礎(chǔ)設(shè)全局管理運(yùn)行在一個(gè)主節(jié)點(diǎn)上，其通過監(jiān)控收集來自本地管理中的各種信息，包括用戶服務(wù)質(zhì)量、資源消耗和電源消耗等，然后對(duì)虛擬機(jī)的放置和資源分配作出決策。

圖1 系統(tǒng)管理結(jié)構(gòu)

1.2 虛擬機(jī)放置數(shù)學(xué)模型

虛擬機(jī)放置問題一直是云計(jì)算研究的重點(diǎn)，其為典型的裝箱問題。文獻(xiàn)[3]證明了虛擬機(jī)放置屬于NP-hard問題。根據(jù)圖1中系統(tǒng)管理框架可知，本文在虛擬機(jī)初始化放置問題上實(shí)施全局管理需要考慮以下3個(gè)因素：服務(wù)級(jí)合約違背率（S）、資源損耗（R）、電源消耗（P）。其中m、n分別表示物理節(jié)點(diǎn)和虛擬機(jī)的數(shù)量，cj表示第j個(gè)物理節(jié)點(diǎn)擁有的相應(yīng)資源容量，ri表示第i個(gè)虛擬機(jī)請(qǐng)求的資源容量。其數(shù)學(xué)模型描述如下：

式（1）中的3個(gè)目標(biāo)分別是服務(wù)級(jí)合約違背率（S）、資源損耗（R）、電源消耗（P）。公式（2）～（4）約束了每個(gè)物理節(jié)點(diǎn)上分配的CPU、內(nèi)存和網(wǎng)絡(luò)帶寬等資源不會(huì)超過其自身的容量。其中，公式（5）約束了每一個(gè)虛擬機(jī)只可分配到一臺(tái)物理節(jié)點(diǎn)上。

2 基于蟻群算法的多目標(biāo)優(yōu)化虛擬機(jī)放置策略

蟻群算法是一種可以用來尋找最優(yōu)解決方案的技術(shù)，該算法在虛擬機(jī)放置問題上應(yīng)用比較廣泛，并且在處理組合優(yōu)化問題上具有一定優(yōu)勢(shì)。具體設(shè)計(jì)步驟和處理過程如下：

2.1 適宜度函數(shù)

適應(yīng)度函數(shù)的選取在遺傳算法中具有重要意義，本文根據(jù)公式（1）分別定義了3個(gè)子適宜度函數(shù)，取值[0，1]。SLA違背率函數(shù)（fSLA）、資源利用函數(shù)（fresource）、電源消耗函數(shù)（fpower），如公式（6）、（7）：

2.3 概率轉(zhuǎn)移函數(shù)

2.4 最優(yōu)解集的構(gòu)建

利用排除法[4]構(gòu)造非支配集在多目標(biāo)遺傳算法中是比較常用的方法，本文利用排除法并對(duì)其適當(dāng)改進(jìn)來處理蟻群算法搜索過程中得到的解，由此實(shí)現(xiàn)對(duì)于Paxeto解集的構(gòu)建過程，過程如下：

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

本文實(shí)驗(yàn)在C1oudSim[4]上實(shí)現(xiàn)完成，cloudsim是澳大利亞墨爾本大學(xué)的網(wǎng)格實(shí)驗(yàn)室和Gridbus項(xiàng)目宣布推出的云計(jì)算仿真軟。本文運(yùn)用蟻群算法對(duì)資源分配，和其它一些算法進(jìn)行了實(shí)驗(yàn)對(duì)比。

實(shí)驗(yàn)設(shè)定80個(gè)物理節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的配置均為10GB的內(nèi)存、1TB的存儲(chǔ)和1Gbps的帶寬，而CPU的能力等價(jià)為1 000，2 000和3 000MIPS。虛擬機(jī)的請(qǐng)求數(shù)量為200個(gè)，其中對(duì)CPU的請(qǐng)求分別為250，500，750和1 000MIPS，內(nèi)存為4GB，存儲(chǔ)為200GB，帶寬為200Mbps。物理結(jié)點(diǎn)在CPU利用率為0%和100%時(shí)所消耗的電源分別為175W和250W。實(shí)驗(yàn)結(jié)果如圖2、圖3、圖4所示。

4 結(jié)語

本文采用的算法是一種改進(jìn)的分布式多目標(biāo)優(yōu)化蟻群算法，該算法是將傳統(tǒng)的多目標(biāo)蟻群算法進(jìn)行改進(jìn)，選取了服務(wù)級(jí)合約違背率（S）、資源損耗（W）、電源消耗（P）3個(gè)目標(biāo)，并結(jié)合排除法解決虛擬機(jī)放置中這3個(gè)目標(biāo)優(yōu)化的問題。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的啟發(fā)式方法和遺傳算法相比，本文提出的算法能夠在服務(wù)級(jí)合約違背率較少的情況下，有效減少系統(tǒng)資源浪費(fèi)和電源消耗，具有可行性。本文已將電源消耗作為管理目標(biāo)之一，接下來將考慮如何兼顧數(shù)據(jù)中心網(wǎng)絡(luò)流量等其它方面，從而使其更加完善。

參考文獻(xiàn)：

[1] HYEAR C，MCKEE B， GARDNER R，et al.Autonomic virtual machine placement in the data center[J].Hewlett Packard Laboratories，Tech.Rep，2007：2007189.

[2] 李進(jìn)超，陳靜怡，吳杰，等.基于改進(jìn)分組遺傳算法的虛擬機(jī)放置研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（5）：20532056..

[3] CAREY M R，JOHNSON D S.Computers and lntractability：a guide to NPcompleteness[J].1979.

[4] CALHEIROS R N，RANJAN R，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2011，41（1）：2350.

（責(zé)任編輯：陳福時(shí)）