基于遺傳算法的大數(shù)據(jù)資源分配算法

蔡柳萍,俞 龍

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

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

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

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

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

1 總體架構(gòu)

1.1 多維裝箱問題模型

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

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

(1)

(2)

?B,XBi+Xj≤C

(3)

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

1.2 云計算資源分配的問題模型

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

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

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

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

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

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

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

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

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

目標(biāo)：

(4)

(5)

(6)

約束條件為：

(7)

(8)

(9)

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

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

2.1 算法設(shè)計

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

本算法分為3個主要的函數(shù)：init_VM函數(shù)、Resource_optimize函數(shù)與deploy_VM函數(shù)。init_VM函數(shù)根據(jù)輸入的請求負(fù)載量初始化虛擬機(jī)；Resource_optimize函數(shù)生成虛擬機(jī)的部署決策，將一個啟發(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.建立一個描述文件,其中包含服務(wù)器數(shù)量、服務(wù)器容量、任務(wù)數(shù)量、每個任務(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;//染色體長度設(shè)為虛擬機(jī)數(shù)量3.WHILE (T < 終端條件)4.N=資源池大小;5.T=T+1;6.WHILE (N≠0)7.遍歷每個服務(wù)器與虛擬機(jī)的需求,使用啟發(fā)式貪婪算法、按照遺傳算法搜索的最優(yōu)虛擬機(jī)順序?qū)⑻摂M機(jī)分配至物理服務(wù)器;8.使用將染色體對應(yīng)的虛擬機(jī)順序轉(zhuǎn)化為裝箱解;9.使用適應(yīng)度函數(shù)計算染色體適應(yīng)度;10.N=N-1;11.Best_Solution=search_optimal_order(資源池);//搜索資源池的最優(yōu)順序12.FOREACH i FROM 1 TO(資源池大小/2);13.[染色體1,染色體2]=輪盤賭機(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 染色體編碼

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

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

圖2 染色體編碼實例

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

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

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

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

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

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

圖4 裝箱問題解的編碼格式

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

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

大多數(shù)基于遺傳算法的云資源分配機(jī)制[13]使用啟發(fā)式算法初始化云計算資源的資源池，然而，這些啟發(fā)式算法導(dǎo)致染色體編碼不充分，為遺傳算法的交叉操作與交換操作帶來了極大困難。本算法將啟發(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剩余容量，通過最小化每個服務(wù)器的剩余資源減少每個服務(wù)器的資源浪費量[14]。

2.4 選擇策略

選擇策略從父代種群選出適應(yīng)度較高的個體，生成后代種群，本算法采用輪盤賭選擇策略。將種群的每個個體映射至輪盤的一片，其中輪盤片的大小與每個個體的適應(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個或多個父代染色體進(jìn)行置換操作，生成新的子代。當(dāng)前有許多染色體的交叉操作方法，例如順序交叉、部分匹配交叉、位置交叉與單性交叉。本文測試了上述所有的交叉操作，順序交叉與單性交叉獲得了最優(yōu)的效果，因此本文選擇這兩種交叉操作。

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

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

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

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

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

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

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

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

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

3.2 與其他云計算資源分配算法比較

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

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

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

4 結(jié)束語

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

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