蔡柳萍,俞 龍

(1.廣東技術(shù)師范學(xué)院天河學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院， 廣州 510540；2.華南農(nóng)業(yè)大學(xué) 電子工程學(xué)院， 廣州 510642)

云計(jì)算將服務(wù)器端的物理資源通過(guò)虛擬化技術(shù)模擬為若干個(gè)獨(dú)立且互不干擾的虛擬服務(wù)器[1]，從而滿(mǎn)足用戶(hù)的資源請(qǐng)求。云計(jì)算為用戶(hù)提供了安全、可靠的計(jì)算能力與存儲(chǔ)容量，成為了許多網(wǎng)絡(luò)應(yīng)用的首選[2]。云計(jì)算的資源分配[3]主要分為2個(gè)階段，其中第1個(gè)階段按照用戶(hù)任務(wù)所需的計(jì)算能力、存儲(chǔ)容量、內(nèi)存大小、網(wǎng)絡(luò)帶寬等資源將任務(wù)分配到合適的虛擬機(jī)；第2階段將不同的虛擬機(jī)分配到合適的物理服務(wù)器，一個(gè)物理服務(wù)器可以容納多個(gè)虛擬機(jī)[4]。目前，服務(wù)器管理虛擬機(jī)的工具主要有Xen與KVN等虛擬機(jī)管理軟件。雖然云計(jì)算提高了物理服務(wù)器的利用率，有效降低了硬件成本與管理成本，但是各個(gè)應(yīng)用程序與任務(wù)之間競(jìng)爭(zhēng)共享資源池的資源為云計(jì)算資源的合理分配帶來(lái)了新的難題[5]。

許多研究人員將云計(jì)算的資源分配問(wèn)題建模為經(jīng)典的多維裝箱問(wèn)題[6]，問(wèn)題的每個(gè)維度對(duì)應(yīng)一種資源類(lèi)型，例如CPU資源、內(nèi)存資源、磁盤(pán)資源、帶寬資源等。當(dāng)前的云計(jì)算資源分配研究主要有幾個(gè)目標(biāo)，包括提高資源利用率、提高能量效率與實(shí)現(xiàn)負(fù)載均衡等[7-9]。本文的研究重點(diǎn)是提高云計(jì)算資源分配算法的資源利用率。

在提高資源利用率的算法中，文獻(xiàn)[10]設(shè)計(jì)了以任務(wù)完成時(shí)間較短且成本最低為約束條件的調(diào)度模型。該資源分配算法能有效地兼顧完成時(shí)間和成本，在縮短任務(wù)完成時(shí)間的同時(shí)保證成本最小，提高了資源利用率。文獻(xiàn)[11]設(shè)計(jì)了虛擬化的異構(gòu)云計(jì)算體系結(jié)構(gòu)，并提出了該體系結(jié)構(gòu)下基于占優(yōu)資源的多資源聯(lián)合公平分配算法。該算法獲得了更高的系統(tǒng)資源利用率，使需求與供給更加匹配，進(jìn)而使用戶(hù)獲取更多的占優(yōu)資源，提高了服務(wù)質(zhì)量。文獻(xiàn)[12]提出一種基于蟻群優(yōu)化算法的任務(wù)調(diào)度方法，結(jié)合排序螞蟻系統(tǒng)和最大最小螞蟻系統(tǒng)的設(shè)計(jì)思想完成信息素更新，有效地提高了云資源的利用率。文獻(xiàn)[6,11-12]通過(guò)優(yōu)化算法搜索資源分配的最優(yōu)解，該類(lèi)算法一般將資源利用率作為首要優(yōu)化目標(biāo)，將能量效率、帶寬利用率等作為次要優(yōu)化目標(biāo)，通過(guò)兼顧多個(gè)性能指標(biāo)獲得理想的分配方案。

本文設(shè)計(jì)了一種云資源的貪婪分配算法，將資源利用率作為唯一的優(yōu)化目標(biāo)，最小化云計(jì)算物理服務(wù)器的數(shù)量，并最小化每個(gè)服務(wù)器的資源浪費(fèi)量。本文將云計(jì)算的資源分配問(wèn)題建模為文獻(xiàn)[6]的多維裝箱問(wèn)題，采用遺傳算法搜索最優(yōu)的虛擬機(jī)順序，設(shè)計(jì)了一種貪婪算法最小化物理服務(wù)器的數(shù)量與每個(gè)物理服務(wù)器的資源浪費(fèi)量。

1 總體架構(gòu)

1.1 多維裝箱問(wèn)題模型

多維裝箱問(wèn)題描述為如下模型[6]：假設(shè)1個(gè)集合B包含m個(gè)相同的箱子，每個(gè)箱子各元素的容量表示為1個(gè)向量C=(C1,C2,…,Cd)。假設(shè)1個(gè)包含n個(gè)項(xiàng)的集合為L(zhǎng)={X1,X2,X3,…,Xn}，L的各項(xiàng)是需要裝箱的元素，將各項(xiàng)表示為包含d個(gè)元素的向量Xj={Xj,1,Xj,2,Xj,3,…,Xj,d}，式中Xj,k是第j項(xiàng)、第k個(gè)元素，其中0

將多維裝箱問(wèn)題的1個(gè)解表示為B={B1,B2,Bi,…,Bm}，表示將n個(gè)項(xiàng)目裝入m個(gè)箱子中，每個(gè)箱子可容納S個(gè)項(xiàng)目。裝箱的決策表示為Bi={X2,i,X7,i,X5,i,…,X5,i}，約束條件為：

(1)

(2)

?B,XBi+Xj≤C

(3)

約束(1)說(shuō)明每個(gè)項(xiàng)目必須裝進(jìn)1個(gè)箱子中，約束(2)說(shuō)明每個(gè)維度中需求的項(xiàng)目不應(yīng)超過(guò)箱子的容量，約束(3)說(shuō)明將1個(gè)新項(xiàng)目裝入1個(gè)箱子中，不應(yīng)超過(guò)箱子的總?cè)萘俊６嗑S裝箱問(wèn)題是NP-hard問(wèn)題[9]，因此云計(jì)算資源分配問(wèn)題的計(jì)算成本極大，本文設(shè)計(jì)了啟發(fā)式貪婪算法來(lái)實(shí)現(xiàn)理想的計(jì)算成本。

1.2 云計(jì)算資源分配的問(wèn)題模型

首先對(duì)云計(jì)算資源分配問(wèn)題做以下假設(shè)：

假設(shè)1每個(gè)任務(wù)均為用戶(hù)預(yù)定義，即僅考慮靜態(tài)的云計(jì)算資源分配情況。

假設(shè)2每個(gè)任務(wù)僅可分配到1個(gè)虛擬機(jī)中。

假設(shè)3每個(gè)任務(wù)請(qǐng)求定量的CPU與內(nèi)存資源，即屬于靜態(tài)的調(diào)度問(wèn)題。為了便于描述，僅考慮CPU與內(nèi)存兩個(gè)資源。

假設(shè)4云端均為相同的物理服務(wù)器。

假設(shè)5每個(gè)虛擬機(jī)僅能分配至1個(gè)服務(wù)器。

基于上述5點(diǎn)假設(shè)，將云數(shù)據(jù)中心的多維虛擬機(jī)部署問(wèn)題建模為一個(gè)多維裝箱問(wèn)題。任務(wù)的數(shù)量決定了向量的元素?cái)?shù)量，即需要裝箱的項(xiàng)目數(shù)量。圖1描述了將資源分配與虛擬機(jī)部署問(wèn)題轉(zhuǎn)化為一個(gè)二維向量的裝箱問(wèn)題。在第1階段將請(qǐng)求所需的資源量(CPU與內(nèi)存)映射至不同的虛擬機(jī)，在第2階段將虛擬機(jī)部署至不同的可用物理服務(wù)器中。

圖1 將資源分配與虛擬機(jī)部署問(wèn)題轉(zhuǎn)化為一個(gè)二維向量的裝箱問(wèn)題

假設(shè)云計(jì)算系統(tǒng)包含N個(gè)任務(wù)，對(duì)應(yīng)N個(gè)虛擬機(jī)、M個(gè)服務(wù)器、R個(gè)資源，將不同的虛擬機(jī)裝箱至一個(gè)物理服務(wù)器中。算法的目標(biāo)是最小化所用物理服務(wù)器的數(shù)量(見(jiàn)式(4))，并最小化各個(gè)服務(wù)器的資源浪費(fèi)量(見(jiàn)式(5))，問(wèn)題的目標(biāo)與約束條件建模為以下各式：

目標(biāo)：

(4)

(5)

(6)

約束條件為：

(7)

(8)

(9)

式中：Wj,i(i∈[1,…,M],j∈[1,…,R])表示所有物理服務(wù)器的總資源浪費(fèi)量；[SRCi,…,SRMi](i∈[1,…,M])表示第i個(gè)服務(wù)器的容量向量，SRC與SRM分別表示CPU資源與內(nèi)存資源；[Ck,i,Mk,i](K∈[1,…,A],i∈[1,…,M])表示第k個(gè)虛擬機(jī)所需的CPU與內(nèi)存；Pj,i∈[0,1](i∈[1,…,M],j∈[1,…,N])表示裝箱的決策結(jié)果。式(5)表示資源分配的結(jié)果應(yīng)當(dāng)最小化所有服務(wù)器的資源浪費(fèi)量。式(6)為計(jì)算資源浪費(fèi)的方法。式(7)表示每個(gè)虛擬機(jī)僅被分配到一個(gè)服務(wù)器中。式(8)、(9)表示虛擬機(jī)的分配結(jié)果不能超過(guò)物理服務(wù)器的容量。

2 遺傳算法搜索最優(yōu)的虛擬機(jī)順序

2.1 算法設(shè)計(jì)

本文設(shè)計(jì)了一種改進(jìn)的遺傳算法，以提高遺傳算法對(duì)裝箱問(wèn)題的求解效果。裝箱問(wèn)題的目標(biāo)是最小化裝載一組項(xiàng)目的箱子數(shù)量。首先，需要搜索一個(gè)項(xiàng)目排序的最優(yōu)解，并且尋找向量裝箱問(wèn)題中項(xiàng)目需求之間的關(guān)系。

本算法分為3個(gè)主要的函數(shù)：init_VM函數(shù)、Resource_optimize函數(shù)與deploy_VM函數(shù)。init_VM函數(shù)根據(jù)輸入的請(qǐng)求負(fù)載量初始化虛擬機(jī)；Resource_optimize函數(shù)生成虛擬機(jī)的部署決策，將一個(gè)啟發(fā)式貪婪算法作為遺傳算法的目標(biāo)函數(shù)；deploy_VM函數(shù)按照裝箱決策結(jié)果將虛擬機(jī)分配至云服務(wù)器中。

算法1 基于遺傳算法的資源分配算法主程序1.初始化:J=0;VM=0;T=0; Optimized_Solution=NULL;//初始化任務(wù)數(shù)量、虛擬機(jī)數(shù)量、終端條件與最優(yōu)解;2.建立一個(gè)描述文件,其中包含服務(wù)器數(shù)量、服務(wù)器容量、任務(wù)數(shù)量、每個(gè)任務(wù)所需的資源量;3.調(diào)用init_VM函數(shù);4.調(diào)用Resource_optimize函數(shù);5.調(diào)用deploy_VM函數(shù)

算法2 init_VM函數(shù)1.初始化VM;//初始化虛擬機(jī)2.WHILE J<任務(wù)數(shù)量;//描述文件3.J=J+1;4.根據(jù)任務(wù)需求為任務(wù)分配虛擬機(jī);5.VM=VM+1算法3 Resource_optimize函數(shù)1.初始化終端條件與資源池大小;2.C_Length=VM;//染色體長(zhǎng)度設(shè)為虛擬機(jī)數(shù)量3.WHILE (T < 終端條件)4.N=資源池大小;5.T=T+1;6.WHILE (N≠0)7.遍歷每個(gè)服務(wù)器與虛擬機(jī)的需求,使用啟發(fā)式貪婪算法、按照遺傳算法搜索的最優(yōu)虛擬機(jī)順序?qū)⑻摂M機(jī)分配至物理服務(wù)器;8.使用將染色體對(duì)應(yīng)的虛擬機(jī)順序轉(zhuǎn)化為裝箱解;9.使用適應(yīng)度函數(shù)計(jì)算染色體適應(yīng)度;10.N=N-1;11.Best_Solution=search_optimal_order(資源池);//搜索資源池的最優(yōu)順序12.FOREACH i FROM 1 TO(資源池大小/2);13.[染色體1,染色體2]=輪盤(pán)賭機(jī)制;14.[子代1,子代2]=crossover(染色體1,染色體2);15.save(新資源池,子代1,子代2);//將子代保存至新資源池內(nèi);16.資源池=新資源池;//更新當(dāng)前的資源池算法4 deploy_VM函數(shù)IF((Optimized_Solution == NULL) || fitness(Optimized_Solution)

2.2 染色體編碼

多維裝箱問(wèn)題是一個(gè)排序優(yōu)化問(wèn)題，遺傳算法的染色體編碼代表了虛擬機(jī)的順序，每個(gè)染色體(一個(gè)數(shù)組)代表了序列中的一個(gè)位置。

每個(gè)染色體的長(zhǎng)度等于需要裝箱的虛擬機(jī)數(shù)量N，圖2所示是染色體的結(jié)構(gòu)實(shí)例。

圖2 染色體編碼實(shí)例

將染色體編碼為N個(gè)整數(shù)的數(shù)組(一維陣列)，染色體基因是一個(gè)虛擬機(jī)的序號(hào)，如圖3所示。

圖3 染色體與云計(jì)算資源的對(duì)應(yīng)關(guān)系

2.3 目標(biāo)函數(shù)與適應(yīng)函數(shù)

將啟發(fā)式貪婪裝箱算法封裝于遺傳算法的適應(yīng)度函數(shù)中。每個(gè)裝箱解對(duì)應(yīng)一個(gè)染色體，因此需要評(píng)估每個(gè)裝箱解的性能。在目標(biāo)函數(shù)中輸入上述染色體，使用啟發(fā)式貪婪算法根據(jù)輸入的資源請(qǐng)求搜索最優(yōu)的裝箱解，目標(biāo)函數(shù)的操作如下所示：

步驟1將虛擬機(jī)的實(shí)際需求與染色體順序中的虛擬機(jī)匹配，該操作將一維數(shù)組形式的染色體轉(zhuǎn)化為矩陣形式，矩陣的元素描述了請(qǐng)求所需的虛擬機(jī)資源。

步驟2使用裝箱函數(shù)搜索裝箱的順序，裝箱解的每個(gè)元素包含2個(gè)值，第1個(gè)值是裝箱虛擬機(jī)的數(shù)量，第2個(gè)值是物理服務(wù)器的編號(hào)。圖4所示是裝箱解的編碼格式。

圖4 裝箱問(wèn)題解的編碼格式

步驟3計(jì)算容納給定虛擬機(jī)序列所需的物理服務(wù)器數(shù)量，計(jì)算各個(gè)服務(wù)器的資源浪費(fèi)量。

目標(biāo)函數(shù)為適應(yīng)度函數(shù)提供了部分參數(shù)，例如服務(wù)器數(shù)量值。目標(biāo)函數(shù)的輸出結(jié)果為最優(yōu)的裝箱解與對(duì)應(yīng)的染色體，決定了各個(gè)虛擬機(jī)分配至指定物理服務(wù)器的結(jié)果。

大多數(shù)基于遺傳算法的云資源分配機(jī)制[13]使用啟發(fā)式算法初始化云計(jì)算資源的資源池，然而，這些啟發(fā)式算法導(dǎo)致染色體編碼不充分，為遺傳算法的交叉操作與交換操作帶來(lái)了極大困難。本算法將啟發(fā)式算法作為目標(biāo)函數(shù)的一部分，將交換的染色體作為目標(biāo)函數(shù)的輸入?yún)?shù)，從而極大地降低了染色體編碼與交叉操作的復(fù)雜度。本算法的目標(biāo)是最小化物理服務(wù)器的總數(shù)量，建模為以下各式：

f(O)=TS·Rtotal

(10)

Rtotal=RCPU+RMEM

(12)

(13)

(14)

式中：f(O)是確定染色體順序的染色體；TS是可用服務(wù)器的總數(shù)量；S是所需的物理服務(wù)器數(shù)量；Rtotal是服務(wù)器的總歸一化剩余容量；RCPU表示歸一化的CPU剩余容量，通過(guò)最小化每個(gè)服務(wù)器的剩余資源減少每個(gè)服務(wù)器的資源浪費(fèi)量[14]。

2.4 選擇策略

選擇策略從父代種群選出適應(yīng)度較高的個(gè)體，生成后代種群，本算法采用輪盤(pán)賭選擇策略。將種群的每個(gè)個(gè)體映射至輪盤(pán)的一片，其中輪盤(pán)片的大小與每個(gè)個(gè)體的適應(yīng)度成正比關(guān)系F(i)。P(i)是染色體被選擇的概率，P(i)與F′(i)成比例關(guān)系。P(i)定義如下：

(15)

F′(i)=1/F(i)

(16)

2.5 交叉操作與變異操作

遺傳算法的交叉操作選擇2個(gè)或多個(gè)父代染色體進(jìn)行置換操作，生成新的子代。當(dāng)前有許多染色體的交叉操作方法，例如順序交叉、部分匹配交叉、位置交叉與單性交叉。本文測(cè)試了上述所有的交叉操作，順序交叉與單性交叉獲得了最優(yōu)的效果，因此本文選擇這兩種交叉操作。

3 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

參考文獻(xiàn)[16]設(shè)置了實(shí)驗(yàn)的遺傳算法參數(shù)，如表1所示。C語(yǔ)言編程實(shí)現(xiàn)本算法，采用LibGA動(dòng)態(tài)庫(kù)(http://lancet.mit.edu/ga/)。LibGA是一個(gè)遺傳算法的C語(yǔ)言編程開(kāi)發(fā)庫(kù)。操作系統(tǒng)為Ubuntu 14.04，硬件環(huán)境為Intel 酷睿i7 4770處理器，8 GB內(nèi)存。

由于本算法的目標(biāo)是優(yōu)化云計(jì)算的資源利用率，因此直接將所需的服務(wù)器數(shù)量作為算法的性能評(píng)價(jià)指標(biāo)。本文進(jìn)行2組實(shí)驗(yàn)，第1組實(shí)驗(yàn)將本算法與其他多維裝箱啟發(fā)式算法比較，評(píng)估本算法對(duì)于多維裝箱啟發(fā)式算法的改進(jìn)效果；第2組實(shí)驗(yàn)將本算法與其他云計(jì)算資源分配算法比較，評(píng)估本算法對(duì)于計(jì)算資源分配算法的改進(jìn)效果。

表1 本算法的參數(shù)設(shè)置

3.1 與其他多維裝箱算法比較

本算法的目標(biāo)是快速、高效地求解多維裝箱問(wèn)題。將本算法與兩種多維裝箱算法進(jìn)行比較，兩種算法分別為BONJRA[15]與MFFD[16]。MFFD是一種傳統(tǒng)的啟發(fā)式多維裝箱問(wèn)題求解算法，BONJRA是近年的一種性能較好的多維裝箱問(wèn)題求解算法。

圖5所示是本算法、BONJRA[15]與MFFD[16]的結(jié)果比較，可清晰地看出本算法對(duì)于不同數(shù)量的虛擬機(jī)均實(shí)現(xiàn)了服務(wù)器數(shù)量最少。說(shuō)明本算法適用于不同的問(wèn)題規(guī)模，且優(yōu)于其他兩種多維裝箱算法。

本文算法計(jì)算的服務(wù)器數(shù)量平均結(jié)果比MFFD與BONJRA分別減少了約34%與39%，與MFFD最大的差別在于本算法引入了改進(jìn)的遺傳算法。因此，可以說(shuō)明本算法通過(guò)遺傳算法提高了多維裝箱算法的求解性能。

圖5 3種算法分配的服務(wù)器數(shù)量

3.2 與其他云計(jì)算資源分配算法比較

RGG[14]是另一種基于遺傳算法的云計(jì)算資源分配算法，DDMOO[17]則是近年來(lái)性能表現(xiàn)優(yōu)異的云計(jì)算資源分配算法。將本文算法與這兩種算法進(jìn)行比較，綜合評(píng)估本算法對(duì)云計(jì)算資源的分配性能。實(shí)驗(yàn)采用文獻(xiàn)[14]中10個(gè)不同規(guī)模的數(shù)據(jù)集。圖6所示是本文算法、RGG與DDMOO 3種算法的計(jì)算結(jié)果。圖6顯示：數(shù)據(jù)集規(guī)模較小時(shí)，本算法、RGG與DDMOO的結(jié)果較為接近；隨著數(shù)據(jù)集規(guī)模的增加，DDMOO算法的結(jié)果明顯高于本算法，對(duì)于第10個(gè)數(shù)據(jù)集，DDMOO算法的服務(wù)器數(shù)量比本算法大約多40個(gè)，而RGG的服務(wù)器數(shù)量則比本算法多4個(gè)?？梢钥闯觯疚乃惴▽?duì)于10個(gè)問(wèn)題均優(yōu)于RGG與DDMOO。

圖6 3種云計(jì)算資源分配算法對(duì)文獻(xiàn)[19]的10個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

此外，RGG的適應(yīng)度評(píng)估總次數(shù)為7 500，而本文算法的適應(yīng)度評(píng)估總次數(shù)僅為1 700，適應(yīng)度函數(shù)計(jì)算總次數(shù)比RGG減少約77.33%。因此，本文算法對(duì)不同規(guī)模的問(wèn)題均可獲得最優(yōu)的資源分配結(jié)果，且具有較高的計(jì)算效率。

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

本文設(shè)計(jì)了一種云資源的貪婪分配算法，將資源利用率作為唯一的優(yōu)化目標(biāo)，最小化云計(jì)算物理服務(wù)器的數(shù)量，并最小化每個(gè)服務(wù)器的資源浪費(fèi)量。本文將云計(jì)算的資源分配問(wèn)題建模為文獻(xiàn)的多維裝箱問(wèn)題，采用遺傳算法搜索最優(yōu)的虛擬機(jī)順序，設(shè)計(jì)了一種貪婪算法最小化物理服務(wù)器的數(shù)量與每個(gè)物理服務(wù)器的資源浪費(fèi)量。該算法存在的不足之處在于，遺傳算法的迭代尋優(yōu)程序?qū)τ诖笠?guī)模問(wèn)題的計(jì)算時(shí)間較長(zhǎng)，對(duì)計(jì)算機(jī)的處理能力有較高的要求。

未來(lái)將關(guān)注網(wǎng)絡(luò)帶寬、存儲(chǔ)資源等更多維度資源分配的貪婪算法，提高云計(jì)算資源分配算法的計(jì)算效率。