基于遺傳算法的大數據資源分配算法

蔡柳萍,俞 龍

(1.廣東技術師范學院天河學院 計算機科學與工程學院， 廣州 510540；2.華南農業大學 電子工程學院， 廣州 510642)

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

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

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

本文設計了一種云資源的貪婪分配算法，將資源利用率作為唯一的優化目標，最小化云計算物理服務器的數量，并最小化每個服務器的資源浪費量。本文將云計算的資源分配問題建模為文獻[6]的多維裝箱問題，采用遺傳算法搜索最優的虛擬機順序，設計了一種貪婪算法最小化物理服務器的數量與每個物理服務器的資源浪費量。

1 總體架構

1.1 多維裝箱問題模型

多維裝箱問題描述為如下模型[6]：假設1個集合B包含m個相同的箱子，每個箱子各元素的容量表示為1個向量C=(C1,C2,…,Cd)。假設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)說明每個項目必須裝進1個箱子中，約束(2)說明每個維度中需求的項目不應超過箱子的容量，約束(3)說明將1個新項目裝入1個箱子中，不應超過箱子的總容量。多維裝箱問題是NP-hard問題[9]，因此云計算資源分配問題的計算成本極大，本文設計了啟發式貪婪算法來實現理想的計算成本。

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

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

假設1每個任務均為用戶預定義，即僅考慮靜態的云計算資源分配情況。

假設2每個任務僅可分配到1個虛擬機中。

假設3每個任務請求定量的CPU與內存資源，即屬于靜態的調度問題。為了便于描述，僅考慮CPU與內存兩個資源。

假設4云端均為相同的物理服務器。

假設5每個虛擬機僅能分配至1個服務器。

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

圖1 將資源分配與虛擬機部署問題轉化為一個二維向量的裝箱問題

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

目標：

(4)

(5)

(6)

約束條件為：

(7)

(8)

(9)

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

2 遺傳算法搜索最優的虛擬機順序

2.1 算法設計

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

本算法分為3個主要的函數：init_VM函數、Resource_optimize函數與deploy_VM函數。init_VM函數根據輸入的請求負載量初始化虛擬機；Resource_optimize函數生成虛擬機的部署決策，將一個啟發式貪婪算法作為遺傳算法的目標函數；deploy_VM函數按照裝箱決策結果將虛擬機分配至云服務器中。

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

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

2.2 染色體編碼

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

每個染色體的長度等于需要裝箱的虛擬機數量N，圖2所示是染色體的結構實例。

圖2 染色體編碼實例

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

圖3 染色體與云計算資源的對應關系

2.3 目標函數與適應函數

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

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

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

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

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

目標函數為適應度函數提供了部分參數，例如服務器數量值。目標函數的輸出結果為最優的裝箱解與對應的染色體，決定了各個虛擬機分配至指定物理服務器的結果。

大多數基于遺傳算法的云資源分配機制[13]使用啟發式算法初始化云計算資源的資源池，然而，這些啟發式算法導致染色體編碼不充分，為遺傳算法的交叉操作與交換操作帶來了極大困難。本算法將啟發式算法作為目標函數的一部分，將交換的染色體作為目標函數的輸入參數，從而極大地降低了染色體編碼與交叉操作的復雜度。本算法的目標是最小化物理服務器的總數量，建模為以下各式：

f(O)=TS·Rtotal

(10)

Rtotal=RCPU+RMEM

(12)

(13)

(14)

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

2.4 選擇策略

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

(15)

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

(16)

2.5 交叉操作與變異操作

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

3 實驗環境與參數設置

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

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

表1 本算法的參數設置

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

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

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

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

圖5 3種算法分配的服務器數量

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

RGG[14]是另一種基于遺傳算法的云計算資源分配算法，DDMOO[17]則是近年來性能表現優異的云計算資源分配算法。將本文算法與這兩種算法進行比較，綜合評估本算法對云計算資源的分配性能。實驗采用文獻[14]中10個不同規模的數據集。圖6所示是本文算法、RGG與DDMOO 3種算法的計算結果。圖6顯示：數據集規模較小時，本算法、RGG與DDMOO的結果較為接近；隨著數據集規模的增加，DDMOO算法的結果明顯高于本算法，對于第10個數據集，DDMOO算法的服務器數量比本算法大約多40個，而RGG的服務器數量則比本算法多4個?？梢钥闯觯疚乃惴▽τ?0個問題均優于RGG與DDMOO。

圖6 3種云計算資源分配算法對文獻[19]的10個數據集的實驗結果

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

4 結束語

本文設計了一種云資源的貪婪分配算法，將資源利用率作為唯一的優化目標，最小化云計算物理服務器的數量，并最小化每個服務器的資源浪費量。本文將云計算的資源分配問題建模為文獻的多維裝箱問題，采用遺傳算法搜索最優的虛擬機順序，設計了一種貪婪算法最小化物理服務器的數量與每個物理服務器的資源浪費量。該算法存在的不足之處在于，遺傳算法的迭代尋優程序對于大規模問題的計算時間較長，對計算機的處理能力有較高的要求。

未來將關注網絡帶寬、存儲資源等更多維度資源分配的貪婪算法，提高云計算資源分配算法的計算效率。