包簇映射框架下的云資源分配優化算法研究

徐 陽 陳世平,2

1(上海理工大學光電信息與計算機工程學院 上海 200093)2(上海理工大學信息化辦公室 上海 200093)

0 引 言

近年來，隨著云計算[1-4]取得了巨大成功，大量高科技公司涌入云服務市場。隨著云計算市場規模越來越大，用戶群體變得更加復雜，相對應的業務需求也在不斷變化。云數據中心資源調度的一個關鍵目標，是將云數據中心的資源快速充分利用分配給用戶。目前主要用的啟發式算法有：粒子群算法(PSO)[5]、蟻群算法(ACO)[6]、遺傳算法(GA)[7-8]等。這些算法主要目的是減少成本，提高資源利用率，以至于滿足用戶各方面的要求。但是這些算法都有各自的優缺點，如蟻群算法局部搜索能力較強，但是初始信息素匱乏、初始搜索速度慢等。

當前云資源分配調度方案依然是云計算最關鍵的技術。為了提高云資源分配效率，減少資源分配的時間，滿足用戶的使用需求。本文引入包簇理論[9]，在包簇映射框架下，提出基于混沌擾動遺傳算法GACD(Genetic Algorithm based on Chaotic Disturbance)。該算法是在遺傳算法的基礎上引入混沌搜索機制、改進種群個體選擇、交叉和變異等操作，提高算法的搜索速度和收斂效率。最后采用CloudSim進行實驗，以檢測算法的正確性。仿真結果表明，基于混沌擾動遺傳算法解決了傳統遺傳算法存在的局部收斂、收斂速度慢和資源分配效率低等缺點，在一定程度上加快了云計算資源分配效率，縮短了任務的完成時間。

1 包簇框架的描述

由文獻[9]可知，包和簇是樹形結構。最底層的虛擬機組合成一個包，而多個包又組合成一個更高級的包。虛擬機或包所需的資源就是用戶對云資源的需求。其中用戶對資源需求包括CPU、RAM、寬帶和緩存等。同理，簇是由多個服務器或子簇組成。簇擁有包對資源的需求量。

本文定義有N個子簇(或服務器)。p為子簇標號，1≤p≤N。有M個子包(或虛擬機)組成，標號為v，1≤v≤M。本文的關鍵是將M個子包分配給N個子簇，將同一個包中包分配給同一個簇中簇，同一個算法遞歸調用把子包分配給子簇，直到虛擬機分配給服務器。

由文獻[10]可知資源約束：

(1)

式中：xv,p[t]是二進制0-1變量：當且僅當在時間t時包v被分配給簇p，則xv,p[t]=1；否則，xv,p[t]=0。Rv,i[t]表示包v在時間t對資源i的需求總量。1≤i≤J，1≤t≤T。Ap,i[t]表示簇p在時間t時對資源i的可用總量。1≤p≤N。

由文獻[10]可知簇的運營成本：

本文在基于包簇映射的框架下，以減少成本U(x,y)為目標，通過混沌擾動遺傳算法進行資源分配，提高分配效率，減少分配時間。

2 基于混沌擾動遺傳算法調度策略

2.1 設計思想

基于混沌擾動遺傳算法是將遺傳算法和混沌搜索機制相結合。首先求出個體之間的差異和適應度值，利用遺傳算法進行搜索，混沌機制來避免陷入局部最優，通過精英保留選擇法，把優秀的個體作為父代，然后采用改進的交叉和變異操作。算法的主要流程如圖1所示。

圖1 算法流程圖

2.2 個體之間的差異性

種群在初始化時會有很大的機率產生很多相似的個體，導致大量迭代計算，為了解決此問題，本文引出差異性。

差異性是指特征空間中對象之間的差異，將特征空間中不同的對象進行分類。本文用0-1編碼來對兩個個體的基因串進行評估，其中兩個對象相同的位置編碼相同，則為0，不同則為1。0越多表示兩個對象越相同，編碼情況越相同。在算法中，限定0的個數來避免非常相似的個體。

2.3 自適應交叉方式

設種群虛擬機的規模為M，虛擬機的任務資源需求種類為J，種群虛擬機的編碼長度為L。第i位編碼為0的個體數為Si,0，為1的個體數為Si,1，則定義第i位的相似度[12]為：

(2)

則群體的相似度定義為：

(3)

根據θ的大小來判斷種群虛擬機的收斂程度，θ越大，表示種群虛擬機越相似，虛擬機所需要的資源也就越相同。種群虛擬機的交叉概率也是依據θ的大小動態調整。算法初期，設定較大的交叉概率值，以此加快種群繁衍和收斂。當種群虛擬機的θ比較大時，相應地調小交叉概率。參照文獻[11]給出相應的自適應調整公式：

Pc=t1et2θ

(4)

式中：t1和t2的值由Pc和θ的取值范圍共同決定。

2.4 種群初始化和混沌擾動的確定

混沌相關的的內容可以參考文獻[12-13],混沌的主要思想是利用自身的特點進行搜索，防止陷入局部最優[14-15]，本文采取Logistic映射系統，映射關系如下:

δn+1=uδn(1-δn)n=0,1,2，…

(5)

式中：u∈[0,4]，當u=4時為完全混沌狀態。

首先，隨機產生一個L維向量δ1=[δ1,1,δ1,2,δ1,l,…,δ1,L]，δ1,l∈[0,1]，δ1作為初始向量進行迭代。根據式(5)將得到的各混沌變量映射到優化變量的各維取值空間，然后計算目標函數值，對其值進行排序，從中選取M個較好的個體作為初始種群。

為了增加解的多樣性，本文用混沌序列對虛擬機種群進行混沌擾動，提高搜索精度，混沌擾動方程如下：

(6)

α的取值會根據搜索的范圍進行調整，在種群初期時，搜索較大范圍，α選取較大的值。到后期時，解已經逐步優化，搜索的范圍變小，此時需要選取較小的α，以便在較小范圍內變動。本文按下式確定α的值：

(7)

式中：m為參加擾動解的個數；k為擾動次數，k=1,2,…。

2.5 加速收斂變異法

生物在進化的過程中，一些個體的某些基因位以一定的幾率發變異，由原本的1變成0，或者由0變成1，促進了生物群體的進化。然而當兩個對象基因相同時，只能依靠基因變異產生新的基因和個體。本文提出一種加速收斂變異法，令個體的基因串前50%為高位，后50%為低位。在算法初期，首先在全局搜索出適應度高的優秀個體，設置其高位為高變異率，低位為低變異率。在尋找適應度高的優秀個體過程中，高位的變異率逐漸降低至0，低位的變異率慢慢增加，以此增加解的多樣性。

2.6 適應度函數和解的修正

包簇資源分配問題，就是需要求出簇中資源分配到包的最低耗費，使其成本最低。

參照文獻[16-17],把解的懲罰值引入適應度函數設計中。

懲罰值：該值等于分配到包的總資源與該簇總資源之差的絕對值和二者中較大者的比值。如果被分配到包的總資源與該簇的總資源相差越大，即包需求的總資源越大于或者越小于簇中所擁有的資源，此時懲罰值越大。則構造包簇資源分配的適應度函數如下：

式中：U(x,y)為成本函數。

設定成本密度函數ω為簇i的總成本與總資源的比值：

解的貪心修正：首先計算出簇的成本密度值并從小到大進行排序，然后在算出分配給簇的包所需要的總資源，如果超出該簇或服務器所擁有的資源。則需要重新匹配一個簇或服務器。如此循環直到滿足包和簇的資源約束為止，得到符合條件的解。

2.7 算法具體步驟

Step1設定種群虛擬機的編碼和各個參數。

Step2種群進行初始化。

Step3根據相似度定義，求出每個個體的相似度值，然后按照從小到大排序。

Step4選取序列中前10%的解，把解轉換為十制數，然后除以2n-1得到小數后，進行混沌擾動，得到10%的新個體(且盡量保證個體的適應度值超過上一代)，若超過，則轉下一步，若未超過則進行迭代，擾動次數加1，達到設定值轉下一步。

Step5對剩余的其他個體進行精英保留選擇，自適應交叉和收斂變異操作來產生新的個體。

Step6計算出新個體所需資源總量是否超過該簇擁有的資源總量，如果超過了則需要通過貪心修正。

Step7首先計算出每個包或者虛擬機的適應度函數值，并將之與上一代中的最大適應度個體進行比較，若新一代適應度函數值較大，則將該值保存、輸出轉step 3。否則直接轉step 3。

Step8循環step 3到step 7操作直至進化代數達到設定值，輸出最優解。

Step9在包最優解的情況下，類似于包的求解，求出包中包的最優資源分配解。一直遞歸求出最底層虛擬機映射到簇或者服務器的解。

3 仿真實驗

本文設計的算法目標有兩個，一是降低成本消耗；二是減少資源分配完成時間，提高資源分配效率。為了對算法進行驗證，本文在基于包簇映射的框架下設計了3組實驗，分別是基于混沌擾動遺傳算法、簡單遺傳算法和粒子群算法進行對比實驗。

三種算法在CloudSim云仿真平臺上進行實驗。實驗環境為Sun Java SE 7。仿真參數設置：設置種群虛擬機數為I，每個虛擬機有J個任務資源需求。每q個虛擬機組合成一個一級包，每q個一級包，則生成一個二級包，依次遞歸生成，直到生成一個最高級的包。

虛擬機的任務資源需求矩陣如下：

ri,j表示虛擬機i對資源j的需求量。1≤i≤I，1≤j≤J。

最高級包的總資源需求矩陣如下：

設虛擬機的二進制編碼為L；二進制編碼初始化生成。

設有H個服務器，每個服務器有J個任務的種類資源。每p個服務器組合成一個一級簇，每p個一級簇，則生成一個二級簇，依次遞歸生成，直到生成一個最高級的簇。

服務器資源矩陣如下：

ah,j表示服務器h擁有資源j的量。1≤h≤H，1≤j≤J。

最高級簇總資源如下：

首先將最高級包先分配給最底層服務器，如果服務器資源不滿足包資源的需求，則依次往上分配給一級簇，如果一級簇依舊不滿足，則繼續遞歸往上一級簇分配，直到滿足包的資源需求為止。這時最高級包的下一級包，開始分配到該簇的下一級簇，依次遞歸，找到滿足需要的最少資源簇即可。類似這種分配，直到虛擬機分配到具體的某個簇或者服務器上即可停止分配。

算法主要是以簇的運營成本U(x,y)為目標，分別用基于混沌擾動遺傳算法、簡單遺傳算法和粒子群算法進行實驗。實驗具體參數如表1所示。

表1 GACD、PSO和GA算法參數設置表

小規模數據實驗的結果如表2所示。

表2 小規模實驗結果表

大規模數據實驗的結果如表3所示。

表3 大規模實驗結果表

收斂速度對比如表4所示。令虛擬機數量I=100，其他參數如表1所示。

表4 算法收斂速度實驗對比表

為了實驗的準確性，避免偶然情況，本文實驗的每個算法都執行15次，然后對實驗結果取平均值。圖2、圖3和圖4是對三種算法的實驗結果進行比較。

圖2 小規模任務的完成時間比較

圖3 大規模任務完成時間比較

圖4 三種算法的收斂速度對比

從圖2可以得出，在一定任務范圍內，GACD、PSO、GA算法完成任務的時間差別不大。但從圖3可以看出，在任務量比較多的情況下，GACD的任務完成時間最短，優勢明顯。從圖4可以看出，本文改進的遺傳算法收斂速度明顯比較快，算法在迭代300次后快速收斂，開始趨向穩定。GACD算法形成的任務調度方案，對執行包簇映射下的資源分配所需要總時間較少，基本達成了最優化解決方案。

由實驗可知，在包簇映射的框架下，基于混沌擾動遺傳算法引入混沌擾動機制，利用混沌的遍歷性和參數擾動策略，擴大了虛擬機種群的多樣性，避免遺傳算法陷入局部極小值，增強了遺傳算法的全局搜索能力，并且在一定程度上使得該算法具有較高的搜索速度和收斂速度。

在時間上，通過圖2和圖3可知，GACD算法在資源分配的過程中，所需要時間最少，搜索速度最快，PSO算法次之。這是因為GACD算法采用混沌進行種群初始化，利用參數擾動策略進行快速搜索和資源分配。

在收斂速度上，通過圖4可知，隨著進化代數的增加，GACD算法采用了自適應交叉方式和加速收斂變異法，提高了算法的收斂速度，使得該算法的收斂速度快于PSO算法和GA算法。

在任務規模上，由圖2和圖3可得，GACD算法效率在小規模任務上略優于GA算法和PSO算法，但差距不明顯，但是隨著任務規模的不斷擴大，在一定的任務范圍之內GACD算法明顯比PSO算法和GA算法效率更高。這是因為PSO算法和GA算法總是盡量把滿足條件的資源分配給當前任務，當可用的資源較多時，完成的時間也較快。一旦任務量較大時，此時PSO算法和GA算法的缺陷也就開始顯現出來。

4 結 語

本文主要是在基于包簇映射的框架下，通過改進遺傳算法對云資源分配調度進行深入研究，引用混沌擾動機制對遺傳算法的搜索操作進行了改進，并且對選擇、交叉和變異操作進一步完善，詳細地描述了算法實現步驟和原理。通過實驗可以看出，該方法以耗費成本最低為目標，快速找到合適的云資源來進行分配，減少了任務調度的時間，提高了效率，具有較好的效果，實現了較為合理的任務調度方案。