包簇映射框架下的云資源分配優(yōu)化算法研究

徐 陽(yáng) 陳世平,2

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

0 引 言

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

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

1 包簇框架的描述

由文獻(xiàn)[9]可知，包和簇是樹(shù)形結(jié)構(gòu)。最底層的虛擬機(jī)組合成一個(gè)包，而多個(gè)包又組合成一個(gè)更高級(jí)的包。虛擬機(jī)或包所需的資源就是用戶(hù)對(duì)云資源的需求。其中用戶(hù)對(duì)資源需求包括CPU、RAM、寬帶和緩存等。同理，簇是由多個(gè)服務(wù)器或子簇組成。簇?fù)碛邪鼘?duì)資源的需求量。

本文定義有N個(gè)子簇(或服務(wù)器)。p為子簇標(biāo)號(hào)，1≤p≤N。有M個(gè)子包(或虛擬機(jī))組成，標(biāo)號(hào)為v，1≤v≤M。本文的關(guān)鍵是將M個(gè)子包分配給N個(gè)子簇，將同一個(gè)包中包分配給同一個(gè)簇中簇，同一個(gè)算法遞歸調(diào)用把子包分配給子簇，直到虛擬機(jī)分配給服務(wù)器。

由文獻(xiàn)[10]可知資源約束：

(1)

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

由文獻(xiàn)[10]可知簇的運(yùn)營(yíng)成本：

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

2 基于混沌擾動(dòng)遺傳算法調(diào)度策略

2.1 設(shè)計(jì)思想

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

圖1 算法流程圖

2.2 個(gè)體之間的差異性

種群在初始化時(shí)會(huì)有很大的機(jī)率產(chǎn)生很多相似的個(gè)體，導(dǎo)致大量迭代計(jì)算，為了解決此問(wèn)題，本文引出差異性。

差異性是指特征空間中對(duì)象之間的差異，將特征空間中不同的對(duì)象進(jìn)行分類(lèi)。本文用0-1編碼來(lái)對(duì)兩個(gè)個(gè)體的基因串進(jìn)行評(píng)估，其中兩個(gè)對(duì)象相同的位置編碼相同，則為0，不同則為1。0越多表示兩個(gè)對(duì)象越相同，編碼情況越相同。在算法中，限定0的個(gè)數(shù)來(lái)避免非常相似的個(gè)體。

2.3 自適應(yīng)交叉方式

設(shè)種群虛擬機(jī)的規(guī)模為M，虛擬機(jī)的任務(wù)資源需求種類(lèi)為J，種群虛擬機(jī)的編碼長(zhǎng)度為L(zhǎng)。第i位編碼為0的個(gè)體數(shù)為Si,0，為1的個(gè)體數(shù)為Si,1，則定義第i位的相似度[12]為：

(2)

則群體的相似度定義為：

(3)

根據(jù)θ的大小來(lái)判斷種群虛擬機(jī)的收斂程度，θ越大，表示種群虛擬機(jī)越相似，虛擬機(jī)所需要的資源也就越相同。種群虛擬機(jī)的交叉概率也是依據(jù)θ的大小動(dòng)態(tài)調(diào)整。算法初期，設(shè)定較大的交叉概率值，以此加快種群繁衍和收斂。當(dāng)種群虛擬機(jī)的θ比較大時(shí)，相應(yīng)地調(diào)小交叉概率。參照文獻(xiàn)[11]給出相應(yīng)的自適應(yīng)調(diào)整公式：

Pc=t1et2θ

(4)

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

2.4 種群初始化和混沌擾動(dòng)的確定

混沌相關(guān)的的內(nèi)容可以參考文獻(xiàn)[12-13],混沌的主要思想是利用自身的特點(diǎn)進(jìn)行搜索，防止陷入局部最優(yōu)[14-15]，本文采取Logistic映射系統(tǒng)，映射關(guān)系如下:

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

(5)

式中：u∈[0,4]，當(dāng)u=4時(shí)為完全混沌狀態(tài)。

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

為了增加解的多樣性，本文用混沌序列對(duì)虛擬機(jī)種群進(jìn)行混沌擾動(dòng)，提高搜索精度，混沌擾動(dòng)方程如下：

(6)

α的取值會(huì)根據(jù)搜索的范圍進(jìn)行調(diào)整，在種群初期時(shí)，搜索較大范圍，α選取較大的值。到后期時(shí)，解已經(jīng)逐步優(yōu)化，搜索的范圍變小，此時(shí)需要選取較小的α，以便在較小范圍內(nèi)變動(dòng)。本文按下式確定α的值：

(7)

式中：m為參加擾動(dòng)解的個(gè)數(shù)；k為擾動(dòng)次數(shù)，k=1,2,…。

2.5 加速收斂變異法

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

2.6 適應(yīng)度函數(shù)和解的修正

包簇資源分配問(wèn)題，就是需要求出簇中資源分配到包的最低耗費(fèi)，使其成本最低。

參照文獻(xiàn)[16-17],把解的懲罰值引入適應(yīng)度函數(shù)設(shè)計(jì)中。

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

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

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

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

2.7 算法具體步驟

Step1設(shè)定種群虛擬機(jī)的編碼和各個(gè)參數(shù)。

Step2種群進(jìn)行初始化。

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

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

Step5對(duì)剩余的其他個(gè)體進(jìn)行精英保留選擇，自適應(yīng)交叉和收斂變異操作來(lái)產(chǎn)生新的個(gè)體。

Step6計(jì)算出新個(gè)體所需資源總量是否超過(guò)該簇?fù)碛械馁Y源總量，如果超過(guò)了則需要通過(guò)貪心修正。

Step7首先計(jì)算出每個(gè)包或者虛擬機(jī)的適應(yīng)度函數(shù)值，并將之與上一代中的最大適應(yīng)度個(gè)體進(jìn)行比較，若新一代適應(yīng)度函數(shù)值較大，則將該值保存、輸出轉(zhuǎn)step 3。否則直接轉(zhuǎn)step 3。

Step8循環(huán)step 3到step 7操作直至進(jìn)化代數(shù)達(dá)到設(shè)定值，輸出最優(yōu)解。

Step9在包最優(yōu)解的情況下，類(lèi)似于包的求解，求出包中包的最優(yōu)資源分配解。一直遞歸求出最底層虛擬機(jī)映射到簇或者服務(wù)器的解。

3 仿真實(shí)驗(yàn)

本文設(shè)計(jì)的算法目標(biāo)有兩個(gè)，一是降低成本消耗；二是減少資源分配完成時(shí)間，提高資源分配效率。為了對(duì)算法進(jìn)行驗(yàn)證，本文在基于包簇映射的框架下設(shè)計(jì)了3組實(shí)驗(yàn)，分別是基于混沌擾動(dòng)遺傳算法、簡(jiǎn)單遺傳算法和粒子群算法進(jìn)行對(duì)比實(shí)驗(yàn)。

三種算法在CloudSim云仿真平臺(tái)上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為Sun Java SE 7。仿真參數(shù)設(shè)置：設(shè)置種群虛擬機(jī)數(shù)為I，每個(gè)虛擬機(jī)有J個(gè)任務(wù)資源需求。每q個(gè)虛擬機(jī)組合成一個(gè)一級(jí)包，每q個(gè)一級(jí)包，則生成一個(gè)二級(jí)包，依次遞歸生成，直到生成一個(gè)最高級(jí)的包。

虛擬機(jī)的任務(wù)資源需求矩陣如下：

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

最高級(jí)包的總資源需求矩陣如下：

設(shè)虛擬機(jī)的二進(jìn)制編碼為L(zhǎng)；二進(jìn)制編碼初始化生成。

設(shè)有H個(gè)服務(wù)器，每個(gè)服務(wù)器有J個(gè)任務(wù)的種類(lèi)資源。每p個(gè)服務(wù)器組合成一個(gè)一級(jí)簇，每p個(gè)一級(jí)簇，則生成一個(gè)二級(jí)簇，依次遞歸生成，直到生成一個(gè)最高級(jí)的簇。

服務(wù)器資源矩陣如下：

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

最高級(jí)簇總資源如下：

首先將最高級(jí)包先分配給最底層服務(wù)器，如果服務(wù)器資源不滿(mǎn)足包資源的需求，則依次往上分配給一級(jí)簇，如果一級(jí)簇依舊不滿(mǎn)足，則繼續(xù)遞歸往上一級(jí)簇分配，直到滿(mǎn)足包的資源需求為止。這時(shí)最高級(jí)包的下一級(jí)包，開(kāi)始分配到該簇的下一級(jí)簇，依次遞歸，找到滿(mǎn)足需要的最少資源簇即可。類(lèi)似這種分配，直到虛擬機(jī)分配到具體的某個(gè)簇或者服務(wù)器上即可停止分配。

算法主要是以簇的運(yùn)營(yíng)成本U(x,y)為目標(biāo)，分別用基于混沌擾動(dòng)遺傳算法、簡(jiǎn)單遺傳算法和粒子群算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)具體參數(shù)如表1所示。

表1 GACD、PSO和GA算法參數(shù)設(shè)置表

小規(guī)模數(shù)據(jù)實(shí)驗(yàn)的結(jié)果如表2所示。

表2 小規(guī)模實(shí)驗(yàn)結(jié)果表

大規(guī)模數(shù)據(jù)實(shí)驗(yàn)的結(jié)果如表3所示。

表3 大規(guī)模實(shí)驗(yàn)結(jié)果表

收斂速度對(duì)比如表4所示。令虛擬機(jī)數(shù)量I=100，其他參數(shù)如表1所示。

表4 算法收斂速度實(shí)驗(yàn)對(duì)比表

為了實(shí)驗(yàn)的準(zhǔn)確性，避免偶然情況，本文實(shí)驗(yàn)的每個(gè)算法都執(zhí)行15次，然后對(duì)實(shí)驗(yàn)結(jié)果取平均值。圖2、圖3和圖4是對(duì)三種算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。

圖2 小規(guī)模任務(wù)的完成時(shí)間比較

圖3 大規(guī)模任務(wù)完成時(shí)間比較

圖4 三種算法的收斂速度對(duì)比

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

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

在時(shí)間上，通過(guò)圖2和圖3可知，GACD算法在資源分配的過(guò)程中，所需要時(shí)間最少，搜索速度最快，PSO算法次之。這是因?yàn)镚ACD算法采用混沌進(jìn)行種群初始化，利用參數(shù)擾動(dòng)策略進(jìn)行快速搜索和資源分配。

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

在任務(wù)規(guī)模上，由圖2和圖3可得，GACD算法效率在小規(guī)模任務(wù)上略?xún)?yōu)于GA算法和PSO算法，但差距不明顯，但是隨著任務(wù)規(guī)模的不斷擴(kuò)大，在一定的任務(wù)范圍之內(nèi)GACD算法明顯比PSO算法和GA算法效率更高。這是因?yàn)镻SO算法和GA算法總是盡量把滿(mǎn)足條件的資源分配給當(dāng)前任務(wù)，當(dāng)可用的資源較多時(shí)，完成的時(shí)間也較快。一旦任務(wù)量較大時(shí)，此時(shí)PSO算法和GA算法的缺陷也就開(kāi)始顯現(xiàn)出來(lái)。

4 結(jié) 語(yǔ)

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