云計算資源的動態(tài)隨機擾動的粒子群優(yōu)化策略

喻德曠，楊 誼，錢 俊

(南方醫(yī)科大學(xué) 生物醫(yī)學(xué)工程學(xué)院，廣州 510515)(*通信作者電子郵箱yiyang20110130@163.com)

0 引言

云計算通過虛擬化技術(shù)將網(wǎng)絡(luò)計算資源整合在一起，組成一個龐大的計算節(jié)點池，用戶通過瀏覽器按需獲得資源，完成數(shù)據(jù)處理任務(wù)[1]。網(wǎng)絡(luò)計算資源龐大且分散，要根據(jù)用戶請求將資源動態(tài)地分配給各個任務(wù)，就需要進(jìn)行合理的資源調(diào)度。任務(wù)調(diào)度策略對用戶任務(wù)的執(zhí)行效率、系統(tǒng)資源的使用效率、任務(wù)執(zhí)行成本、負(fù)載均衡、系統(tǒng)穩(wěn)定性等均有直接的影響[2]。云計算環(huán)境中的資源具有動態(tài)性和異構(gòu)性，對大規(guī)模任務(wù)進(jìn)行資源分配和調(diào)度時，不僅需要最小化完成時間和提高系統(tǒng)使用率，而且要考慮資源負(fù)載均衡、服務(wù)質(zhì)量，是一個非確定性多項式(Non-deterministic Polynomial, NP )問題[3]。

針對云計算資源調(diào)度問題，國內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了許多調(diào)度策略，根據(jù)算法原理可分為三大類。第一類是靜態(tài)資源調(diào)度策略[4]，如數(shù)學(xué)規(guī)劃、專家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)和模糊邏輯策略，這類方法的優(yōu)點是規(guī)則嚴(yán)密、邏輯清晰，但是規(guī)則較為復(fù)雜，只適合小規(guī)模資源的靜態(tài)調(diào)度。第二類是傳統(tǒng)動態(tài)資源調(diào)度策略，包括基于貪心思想的策略(Min-min算法、Max-min算法、Sufferage算法等)[5]和基于操作系統(tǒng)調(diào)度的策略，如FIFO(First In First Out)算法、公平調(diào)度算法、計算能力調(diào)度算法等[6]。這些策略可以實現(xiàn)資源動態(tài)調(diào)度，但由于參與操作的因子很多，用于大規(guī)模任務(wù)調(diào)度計算復(fù)雜度太高。第三類是啟發(fā)式策略，主要包括遺傳算法和粒子群算法[7]。例如，文獻(xiàn)[8]提出了一種基于模擬退火思想的改進(jìn)遺傳算法，在退火過程中以一定概率接受劣質(zhì)解從而避免調(diào)度早熟現(xiàn)象；文獻(xiàn)[9]在遺傳算法基礎(chǔ)上,提出了一種考慮多維約束的任務(wù)調(diào)度算法MCGA(Multiple Constraints based on Genetic Algorithm)，在算法的編碼與解碼、適應(yīng)度函數(shù)、交叉變異等操作環(huán)節(jié)上進(jìn)行了改進(jìn)；文獻(xiàn)[10]建立了多目標(biāo)優(yōu)化模型，并結(jié)合最新的徑向基函數(shù)(Radial Basis Function,RBF)神經(jīng)網(wǎng)絡(luò)和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法對其求解；文獻(xiàn)[11]改進(jìn)了PSO的搜索方向、適應(yīng)度函數(shù)等方面；文獻(xiàn)[12]將粒子群算法和差分遺傳算法結(jié)合求解；文獻(xiàn)[13]設(shè)計了雙向搜索的改進(jìn)粒子群算法等。

1 動態(tài)隨機擾動PSO策略的基本思路

從以上分析可知，相對于傳統(tǒng)任務(wù)調(diào)度策略，啟發(fā)式任務(wù)調(diào)度策略在求解NP類問題時具有更高的自適應(yīng)性和靈活性：實驗表明，模擬退火算法體現(xiàn)了貪心(Greedy)策略，在搜索到局部最優(yōu)解后，會進(jìn)行擾動，以一定的概率接受一個比當(dāng)前解要差的解，進(jìn)而有可能跳出局部最優(yōu)解，找到一個比當(dāng)前解更好的解。但貪心策略往往不能達(dá)到全局最優(yōu)解，擾動幅度和時機不容易控制，并且在并行性方面較弱。PSO算法具有參數(shù)設(shè)置少、全局搜索能力強等優(yōu)點，其并行性和分布式的特點能夠處理海量數(shù)據(jù)，較為適合作為云計算資源調(diào)度策略。但PSO在迭代后期隨著種群多樣性的降低，往往陷入局部最優(yōu)而錯失全局最優(yōu)解。遺傳算法(Genetic Algorithm, GA)從問題解集開始搜索，而不是從單個解開始，通過對不同解的組成進(jìn)行交叉或修改，能夠有效地提高解的組成的多樣性，利于全局擇優(yōu)，且具有并行優(yōu)勢，覆蓋面大。GA采用概率規(guī)則來指導(dǎo)搜索方向，比確定性規(guī)則具有更好的自適應(yīng)和自學(xué)習(xí)性，但是概率篩選規(guī)則存在機會風(fēng)險，獲得的解是不穩(wěn)定的。從這些分析可以知道，采用單一算法處理大規(guī)模計算資源分配，得到的結(jié)果往往不是最優(yōu)或穩(wěn)定的。本文利用PSO與遺傳算法本身的優(yōu)點和對大量資源調(diào)度的適應(yīng)性，將二者結(jié)合起來，設(shè)計了基于隨機擾動的優(yōu)化技術(shù)的群體智能混合策略，來提高云計算任務(wù)調(diào)度的綜合效率，減少任務(wù)執(zhí)行時間、降低計算成本，并改善負(fù)載平衡。

本文提出動態(tài)隨機擾動的PSO(Dynamic Random Distribution PSO, DRDPSO)策略如下：首先建立云計算資源調(diào)度模型；改進(jìn)PSO算法，將其慣性權(quán)重常數(shù)修改為變量，使得求解過程的搜索不是勻速而是可控變速的；在每次迭代中以局部范圍代替全局范圍，減少盲目搜索操作；在PSO算法內(nèi)引入遺傳算法的選擇操作，篩選出更優(yōu)質(zhì)的個體并傳遞到下一代，并引入變異操作實現(xiàn)隨機擾動，試圖改善粒子組成，提高粒子多樣性；結(jié)束條件體現(xiàn)了多重約束的合理運用。

1.1 建立云計算資源模型

云計算的系統(tǒng)資源是有限的，如何為用戶任務(wù)合理地分配資源，使各個計算節(jié)點達(dá)到負(fù)載均衡，是整個服務(wù)過程中需要考慮的問題。為了突出調(diào)度問題而減少其他因素干擾，本文約定：所有任務(wù)都具有原子性(不再可分)；多個任務(wù)可以同時在數(shù)據(jù)中心的計算節(jié)點(虛擬機)上執(zhí)行；每個計算節(jié)點都可分配給任何一個任務(wù)(任務(wù)沒有計算特殊性)；根據(jù)計算能力一個計算節(jié)點可以只接受一個任務(wù)或同時接受多個任務(wù)；不考慮任務(wù)切換、傳輸?shù)葧r間耗費。對模型參數(shù)進(jìn)行如下定義：

1)任務(wù)集合T={t1,t2,…,tm}，由m個相互獨立的原子任務(wù)組成。

2)計算節(jié)點集合CN={cn1,cn2,…,cnn}，由n個計算節(jié)點組成，每個計算節(jié)點采用如下屬性線性表形式描述：cni={CPU,MEM,DISK,…}，CPU表示內(nèi)核數(shù)，MEM表示內(nèi)存大小，DISK表示磁盤空間大小，可根據(jù)需要增加或刪除屬性元素。

3)決策矩陣D={dij},i=1,2,…,m,j=1,2,…,n,dij∈{0,1}，dij=1 表示第i個任務(wù)在第j個計算資源上執(zhí)行；dij=0 表示第i個任務(wù)不在第j個計算資源上執(zhí)行。

4)執(zhí)行時間矩陣ExeTime={etij},i=1,2,…,m,j=1,2,…,n,etij表示第i個任務(wù)在第j個計算資源上完成所需要的時間。

5)計算成本矩陣CalCost={calcij},i=1,2,…,m,j=12,…,n,calcij表示第i個任務(wù)在第j個計算資源上完成所消耗的資源成本(CPU、內(nèi)存、外存)。

6)總時間成本(Execute Time Cost, ETC)和總計算資源成本(Calculate Resource Cost, CRC)。

(1)

(2)

云計算資源調(diào)度目標(biāo)包括：所有任務(wù)完成時總的執(zhí)行時間最小，總的資源占用最少，即使得式(1)和/或式(2)取最小值。實際應(yīng)用中，式(1)、(2)同時獲得最小值的概率較小，可以根據(jù)實際需要賦予總時間成本和總計算成本以不同的權(quán)重如式(3)：

TotalCost=μ1ETC+μ2CRC

(3)

如側(cè)重時間成本，則μ1取較大值；若側(cè)重計算成本，則μ2取較大值，目標(biāo)是綜合代價TotalCost最小。

在本文實驗中，云計算資源模擬環(huán)境下ETC和CRC為同一數(shù)量級，如果在其他應(yīng)用場景下這兩個變量不是同一數(shù)量級，則應(yīng)當(dāng)進(jìn)行歸一化處理后再加權(quán)累加。

1.2 動態(tài)隨機擾動PSO策略

PSO算法初始化為一群隨機粒子，代表隨機解。所有的粒子都具有速度屬性，在每一次迭代中，每個粒子通過跟蹤兩個值來更新自己的速度和位置：一個是粒子本身所找到的最優(yōu)解lBest，另一個是整個種群目前的最優(yōu)解gBest。每個粒子根據(jù)適應(yīng)度函數(shù)來判斷自己當(dāng)前是否到達(dá)最優(yōu)解的位置。粒子之間利用信息共享進(jìn)行從無序到有序的演化，從而獲得全局最優(yōu)解。

1.2.1 簡化的編碼設(shè)計

通常粒子群算法和遺傳算法可以采用兩種編碼方法：實數(shù)編碼法和二進(jìn)制編碼法。前者表示形式容易理解，解碼簡單；后者能夠表示多樣化的種群，但占用存儲空間較大，解碼過程難以理解。為了提高策略可讀性和一致性，本文采用實數(shù)編碼法對粒子進(jìn)行編碼。每個粒子表示任務(wù)與資源的對應(yīng)關(guān)系，如粒子{(1,3)，(2,2)，(3,4)，(4,3)，(5,1)}表示任務(wù)1分配到資源(計算節(jié)點)3上、任務(wù)2分配到資源2上、任務(wù)3分配到資源4上等。在同一時間窗口內(nèi)的任務(wù)的數(shù)量決定了編碼的長度，上例中的粒子的長度為5。

1.2.2 改進(jìn)的粒子更新策略為“前快后慢”

設(shè)群體粒子集合(即解的集合)為X={x1,x2,…,xs}，s為解空間規(guī)模，粒子xi(i∈[1,s])在t時刻的位置為pi(t)，此時單個粒子的最佳位置為lbest_p(t), 當(dāng)前群體的最佳位置為gbest_p(t)，粒子xi運動的速度公式為：

vi(t+1)=w×vi(t)+c1×(lbest_p(t)-pi(t))+

c2×(gbest_p(t)-pi(t))

(4)

位置公式為：

pi(t+1)=pi(t)+vi(t+1)

(5)

其中:w為慣性權(quán)重常數(shù);c1和c2為常系數(shù)。

在實驗中發(fā)現(xiàn)，由于速度更新率即式(4)中的慣性權(quán)重c1和c2設(shè)置為常數(shù)，使得求解過程中收斂速度保持不變。而實際的解搜索往往需要在早期進(jìn)行快速的大致定位，在后期放慢速度在確定的候選區(qū)域內(nèi)進(jìn)行比較仔細(xì)的搜索，因此本文將慣性權(quán)重修改為變量，根據(jù)經(jīng)驗設(shè)計如下：

(6)

其中:IterNum為算法的總迭代次數(shù);IterNow為當(dāng)前迭代次數(shù);k1和k2為常數(shù)，一般取值在1～2，其比例關(guān)系為1∶1;fit(t)為t時刻群體的適應(yīng)度函數(shù)值。慣性權(quán)重的初始值默認(rèn)為1。

式(6)體現(xiàn)了對粒子運動變化速率的合理控制，慣性權(quán)重變化受到兩個因素的影響：

一是迭代次數(shù)。迭代過程中粒子的更新速度應(yīng)當(dāng)是前快后慢，這是由于起始點是隨機解，應(yīng)當(dāng)盡快收斂到全局最優(yōu)解可能處在的小區(qū)域中，所以收斂速度要快；而后期則應(yīng)當(dāng)在確定的小區(qū)域內(nèi)進(jìn)行較為細(xì)致的搜索，所以收斂速度要慢。按照經(jīng)典算法，收斂速度一直是常量，將不利于提高收斂速度，也不利于在最可能產(chǎn)生最優(yōu)解的區(qū)域細(xì)致搜索。

二是適應(yīng)度(綜合代價TotalCost)。根據(jù)前面分析的云計算資源調(diào)度目標(biāo)和所涉及的衡量指標(biāo)，本文策略的適應(yīng)度函數(shù)主要由式(3)決定，即同時考慮總的執(zhí)行時間和總的資源開銷。此外，各臺服務(wù)器節(jié)點的負(fù)載平衡度不應(yīng)差異過大，否則會造成某些節(jié)點壓力重，容易出現(xiàn)瓶頸，而某些節(jié)點的資源得不到有效利用，因此本文定義了負(fù)載均衡指標(biāo)。云平臺中某個計算節(jié)點j的負(fù)載均衡因子LBj定義為：

(7)

其中μ1和μ2為權(quán)重參數(shù)，其他參數(shù)含義同前面介紹。

負(fù)載均衡度反映了調(diào)度策略對計算資源利用的公平性和均衡性。定義負(fù)載均衡度τ為：

(8)

由于τ和適應(yīng)度函數(shù)值TotalCost在數(shù)值上往往不是同一數(shù)量級，在不同類型的任務(wù)中也難以歸一化，所以解的優(yōu)良性的判斷規(guī)則為兩個：優(yōu)先依據(jù)TotalCost選擇局部最優(yōu)解；如果存在多個局部最優(yōu)解，則根據(jù)負(fù)載均衡度τ判斷，取τ最小的解。也就是說在綜合代價最小的前提下兼顧負(fù)載均衡。

1.2.3 縮小搜索范圍

由于粒子在上一時刻的最佳位置直接影響到下一時刻的最佳位置的選擇，不必每次迭代都重新搜索整個種群，所以本文用t-1時刻gbest_p(t-1)粒子的若干個鄰居中的最佳位置(鄰居數(shù)量NeighNum根據(jù)經(jīng)驗設(shè)置，通常為總粒子數(shù)量的1/3)，取代t時刻整個種群的最佳粒子位置作為gbest_p(t)的值，從而減少大量無效的搜索和比較，降低計算代價，提高計算效率。如果最佳位置確實需要發(fā)生大的偏移，則可以通過適應(yīng)度函數(shù)控制，函數(shù)值的改變能夠調(diào)整粒子運動的范圍(發(fā)散或收斂)，越靠近當(dāng)前最佳位置的粒子下一步的搜索范圍應(yīng)當(dāng)收斂，反之應(yīng)當(dāng)發(fā)散。

1.2.4 引入遺傳算法的選擇和變異操作

遺傳算法也屬于搜索啟發(fā)式算法，從完全隨機個體的種群開始，選擇多個適應(yīng)度較高的個體，通過選擇、交叉和突變產(chǎn)生新的生命個體，構(gòu)成下一代種群。選擇運算的作用是把優(yōu)質(zhì)的個體基因直接遺傳到下一代；交叉運算則交換兩個個體的若干基因，產(chǎn)生新的個體；變異運算是對個體的某些基因位點作修改，產(chǎn)生新的個體。迭代結(jié)束時，以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出。

資源調(diào)度求解的搜索過程中也會出現(xiàn)某些時刻粒子的相似度高，而不利于發(fā)現(xiàn)更優(yōu)解的現(xiàn)象。因此本文在改進(jìn)的PSO過程中引入遺傳算法的選擇和變異操作。在每一代中選擇一定比例的優(yōu)質(zhì)粒子，即Ntop個適應(yīng)度最高的粒子即優(yōu)質(zhì)粒子(Ntop根據(jù)經(jīng)驗設(shè)置為粒子總數(shù)的1/10)，直接進(jìn)入下一代。對于其他的粒子則執(zhí)行隨機變異操作，具體做法是對t時刻隨機選取的非優(yōu)質(zhì)粒子xi的第j個分量xij(t)按照隨機概率φ(i,j,t)進(jìn)行隨機變異，變異率定義如下：

(9)

其中，σ取值范圍是(0,1)，一般取[0.6,0.8]。例如，σ取值為0.7，對于粒子{(1,3)，(2,4)，(3,4)，(4,3)，(5,1)}，某個時刻的j=3的分量的變異概率rand為0.8，變異后的新的對應(yīng)資源編號為資源集合中的隨機值(假設(shè)計算得到1)，如果編號1的資源能夠滿足任務(wù)3的需求，則實施變異為{(1,3)，(2,4)，(3,1)，(4,3)，(5,1)}，否則不執(zhí)行變異操作。通過變異操作，改變粒子的基因組成，從而有可能將適應(yīng)度較低的粒子進(jìn)行優(yōu)化，但是也不排除變異操作導(dǎo)致粒子的適應(yīng)度降低的情況。以上的變異操作實質(zhì)上也是一種隨機擾動技術(shù)，可以防止算法過早地陷入局部最優(yōu)解。

遺傳算法中的交叉操作也能夠提高基因的多樣性，減少陷入局部最優(yōu)的可能，但粒子之間基因的交叉可能導(dǎo)致多個任務(wù)需求與資源的連鎖不匹配，而判斷更新后的任務(wù)和資源是否匹配，會大大增加算法的復(fù)雜性，所以本文沒有盲目采用遺傳算法的交叉操作，而是用隨機變異的擾動技術(shù)來達(dá)到目的。

1.2.5 算法結(jié)束條件綜合考慮多個指標(biāo)

本文把分配成功的指標(biāo)(TotalCost，運行時間少，計算資源占用少)和計算公平指標(biāo)(τ，節(jié)點的負(fù)載均衡度)結(jié)合起來，這使得本文策略的綜合性能更好。實際上這些指標(biāo)不可能同時達(dá)到最優(yōu)，因為它們之間存在相互沖突性。在解決實際問題時，往往達(dá)到需要的綜合最優(yōu)就可以了。結(jié)束條件表示為：當(dāng)t時刻粒子集的適應(yīng)度函數(shù)與上一時刻相比不再增加(近似)，或者迭代次數(shù)到達(dá)了一個上限，就令算法結(jié)束。形式化設(shè)置為：(presumption1)t時刻的適應(yīng)度(綜合代價)TotalCost與t-1時刻相比，增加率小于閾值εc，且t時刻的負(fù)載均衡度τ與t-1時刻相比，降低率小于閾值ετ；(presumption2)達(dá)到最大迭代次數(shù)IterNum。

1.2.6 DRDPSO策略流程

Step1 初始化種群，隨機生成符合任務(wù)-資源約束條件的粒子編碼，設(shè)置最大迭代次數(shù)、解規(guī)模等參數(shù)的初值。

Step2 初始化粒子局部最優(yōu)和全局最優(yōu)值。

Step3 根據(jù)式(3)、(6)，更新式(4)、(5)，即更新所有粒子的速度和位置。

Step4 根據(jù)適應(yīng)度函數(shù)式(3)計算各個粒子的適應(yīng)度和群體適應(yīng)度(群體搜索范圍控制在NeighNum而不是所有粒子)，根據(jù)式(8)計算負(fù)載均衡權(quán)值。

Step5 若滿足結(jié)束條件(presumption1)，則輸出當(dāng)前解，并結(jié)束；否則，若滿足條件(presumption2)，則輸出當(dāng)前解，并結(jié)束；若不滿足條件(presumption1)，也不滿足條件(presumption2)，轉(zhuǎn)到Step6。

Step6 對當(dāng)前群體Ntop個適應(yīng)度最高的優(yōu)質(zhì)粒子直接進(jìn)入下一代。按照式(9)概率對非優(yōu)質(zhì)粒子進(jìn)行選擇和隨機變異操作，生成下一代群體；轉(zhuǎn)到Step3。

1.2.7 算法復(fù)雜度分析

經(jīng)典PSO算法每一次迭代中的粒子數(shù)量不變，記為Nc。設(shè)第i次迭代中粒子的數(shù)量為Ni(i= 1, 2, …,m) ，m為最大迭代次數(shù)，則有Ni=Nc。設(shè)每個粒子每一次迭代需要的運算時間為Ti，則經(jīng)典PSO算法總的運行時間為O(Nc*Ti*m)。本文DRDPSO策略將群體搜索范圍控制在NeighNum而不是所有粒子(NeighNum根據(jù)經(jīng)驗設(shè)置，通常為總粒子數(shù)量的1/3)，即搜索范圍縮小至原來的1/3，且隨著迭代的進(jìn)行，后期符合條件的粒子的數(shù)量還會逐漸減少(非單調(diào))。設(shè)每個粒子每一次迭代需要的運算時間為Ti，則本文DRDPSO策略總的運行時間為O(Ni*Ti*m)，其中Ni≤1/3Nc。比經(jīng)典PSO算法增加的計算式(6)、(8)、(9)均為常數(shù)級計算，對時間復(fù)雜度帶來的增量遠(yuǎn)遠(yuǎn)小于搜索范圍帶來的減量，可以忽略。本文DRDPSO策略改進(jìn)的效果在運行時間方面主要體現(xiàn)在:每一次迭代中的搜索范圍大大減少,參與下一步運算的粒子數(shù)大大減少，使得運行時間減少。而增加的計算部分使得對資源調(diào)度的評估標(biāo)準(zhǔn)更合理，解的多樣性更好。

在空間存儲方面，本文DRDPSO策略比經(jīng)典PSO算法在每次迭代中增加了常量數(shù)量級的中間變量如fit(t)、τ、φ(i,j,t)等，以及與之相關(guān)的臨時變量的存儲，但每次迭代搜索范圍相比經(jīng)典算法縮小至原來的1/3，使得臨時粒子的保存量也大為減少，所以空間復(fù)雜度有所降低。

需要明確的是，本文策略屬于啟發(fā)式搜索算法，這一類算法所獲得的解都并不是理論上的最優(yōu)解。對于諸多 NP-hard 問題，使用確定性算法時間復(fù)雜度的代價極大，到不能接受的程度(運行時間很長)，有時候需要保存的中間變量數(shù)量也很大，導(dǎo)致空間復(fù)雜度也較高。而求解實際問題往往并不需要理論上的最優(yōu)解，只需要一個滿足一定條件、符合工程需求的次最優(yōu)解就能解決問題。

2 實驗結(jié)果與分析

本文采用云計算仿真工具CloudSim 進(jìn)行實驗仿真，首先創(chuàng)建數(shù)據(jù)中心、用戶代理和計算節(jié)點(虛擬資源)，其次將用戶代理與計算節(jié)點進(jìn)行映射，生成云任務(wù)集合，在此基礎(chǔ)上使用不同的調(diào)度策略將任務(wù)分配給計算節(jié)點。文獻(xiàn)[8] 的模擬退火遺傳算法(Simulated Annealing Genetic Algorithm, SAGA)和文獻(xiàn)[12] 的GA+PSO算法分別對云計算的資源調(diào)度問題對標(biāo)準(zhǔn)遺傳算法和標(biāo)準(zhǔn)PSO算法作了有特色的改進(jìn)，并提供了較詳細(xì)的實現(xiàn)過程，因此作為本文策略的對照算法。在相同環(huán)境和條件下將本文DRDPSO策略與SAGA、GA+PSO進(jìn)行對比實驗。計算機仿真實驗環(huán)境的配置為：Windows 7操作系統(tǒng)，CPU 4核，內(nèi)存16 GB，硬盤2 TB。

2.1 任務(wù)規(guī)模單變量實驗結(jié)果

在任務(wù)類型相同的條件下，以任務(wù)規(guī)模為單變量，分別生成m=100,200,…,1 000個模擬的用戶任務(wù)，計算資源n取50。本文DRDPSO策略中的參數(shù)初始化為：種群規(guī)模Size(即粒子的個數(shù)，或候選解的個數(shù))初始化為100，Ntop=Size/10=10，NeighNum=Size/3=33，最大迭代次數(shù)IterNum=2 000。μ1=4，μ2=1，表示本文更重視總執(zhí)行時間的優(yōu)化，而把資源成本放在較次要的位置。c1=c2=1，k1=k2=1，σ=0.7。為了挖掘最優(yōu)值，體現(xiàn)每次迭代與上一次的細(xì)微改變，設(shè)置為較小的門限值：εc=0.01，ετ=0.01(實際運行時，根據(jù)具體問題域的變化幅度不同，或者為了避免迭代次數(shù)過多，總是超過上限，可以根據(jù)經(jīng)驗調(diào)整為小于等于0.05的值)。SAGA和GA+PSO的公共參數(shù)與本文算法相同，其各自的局部變量大部分按原文獻(xiàn)設(shè)置參數(shù)值，但為了在本實驗中獲取最好的結(jié)果，對部分參數(shù)值作了適當(dāng)調(diào)整。三種算法在處理不同任務(wù)規(guī)模下的CPU型任務(wù)的性能如圖1所示。由于本文算法中多處使用了隨機技術(shù)，所以同樣參數(shù)的實驗多次運行結(jié)果在數(shù)值上不完全相同，但是多次實驗結(jié)果反映出的規(guī)律是基本一致的。

圖1 不同算法在不同任務(wù)規(guī)模下的性能比較Fig．1 Performance comparison of different algorithms under different task scales

從圖1(a) 可以看出，在任務(wù)規(guī)模比較小的情況下(規(guī)模為100)，本文算法DRDPSO比SAGA、GA+PSO 的最優(yōu)調(diào)度方案所需的總執(zhí)行時間略大。而隨著任務(wù)規(guī)模的增加，三種調(diào)度策略的總執(zhí)行時間都有增加，本文DRDPSO策略的增加率明顯小于GA+PSO，而GA+PSO則略小于SAGA。DRDPSO的總執(zhí)行時間比SAGA少13.7%～37.0%，比GA+PSO少13.6%～31.6%。上述結(jié)果表明本文調(diào)度方案能夠適應(yīng)大規(guī)模任務(wù)調(diào)度，在較短的時間內(nèi)完成用戶任務(wù)。

由圖1(b)可以看出，本文DRDPSO策略與SAGA 在任務(wù)規(guī)模增加時，資源耗費近似于線性增長，表明這兩種策略在任務(wù)-計算節(jié)點匹配的適應(yīng)性和穩(wěn)定性均較好，而GA+PSO的資源耗費波動較大。在大多數(shù)情況下DRDPSO的資源耗費比其他兩種算法少，隨任務(wù)規(guī)模不同，本文DRDPSO策略的資源耗費比SAGA少9.8%～17.1%，比GA+PSO少0.6%～31.1%。

從圖1(c)可以看出，在達(dá)到收斂所需的迭代次數(shù)方面，文本算法DRDPSO明顯少于其他兩個算法，且不易受任務(wù)規(guī)模變化的影響，而另外兩種算法在任務(wù)規(guī)模增大時迭代次數(shù)也顯著增加，直到任務(wù)規(guī)模增大到一定程度才停止大幅增加。DRDPSO的迭代次數(shù)比SAGA少15.7%～60.2%，比GA+PSO少1.4%～54.7%。文本算法DRDPSO迭代次數(shù)出現(xiàn)波動的原因主要來自于φ(i,j,t)的值和每次實驗隨機產(chǎn)生的任務(wù)序列的情況(子任務(wù)大小、子任務(wù)出現(xiàn)順序等)，由于適應(yīng)度函數(shù)和負(fù)載均衡度等多種指標(biāo)的共同制約，使得迭代次數(shù)較少。同時也看到，在大部分情況下，本文DRDPSO策略的時間耗費沒有與迭代次數(shù)的減少幅度成線性關(guān)系，是每次迭代中增加了用于改進(jìn)的多個計算導(dǎo)致的。

從圖1(d)可以看出，在不同的任務(wù)規(guī)模條件下，本文算法DRDPSO的負(fù)載均衡度總體來看最小，比SAGA減小8.1%～18.5%，大部分情況下比GA+PSO減少2.7%～15.3%，且變化最小。GA+PSO雖然有時獲得比DRDPSO更好的負(fù)載均衡度，但它的整體性能不夠穩(wěn)定，而SAGA的負(fù)載均衡度偏大，表明其對計算節(jié)點的利用不夠均衡。

2.2 任務(wù)類型單變量實驗結(jié)果

為了比較對不同類型任務(wù)的處理效果，將任務(wù)劃分為三類：1)CPU型任務(wù)，占用CPU的比例遠(yuǎn)大于IO比例(比值大于3∶1)；2)混合型任務(wù)，占用CPU和IO比例大致相當(dāng)(比值介于3∶1和1∶3之間)；3)IO型任務(wù)，占用CPU的比例遠(yuǎn)小于IO的比例(比值小于1∶3)。實驗結(jié)果表明，三種算法各自在相同任務(wù)規(guī)模下的性能基本保持一定的規(guī)律。以任務(wù)規(guī)模500為例，三種算法對三種類型任務(wù)的平均總執(zhí)行時間、平均總的資源成本、平均迭代次數(shù)和平均資源負(fù)載均衡度如表1所示。

從表1可以看出，在總執(zhí)行時間方面，三種調(diào)度策略表現(xiàn)相似，都是對于CPU型任務(wù)的總執(zhí)行時間最多，混合型任務(wù)次之，IO型任務(wù)最少，顯然，這是由于本文定義的適應(yīng)度函數(shù)為綜合代價TotalCost，而TotalCost只考慮執(zhí)行時間和資源占用情況，未考慮任務(wù)傳輸時間(而實際應(yīng)用也往往不計入任務(wù)傳輸時間，或者認(rèn)為任務(wù)可以預(yù)傳輸，傳輸時間為常量)。在總執(zhí)行時間方面，本文策略DRDPSO表現(xiàn)最好。類似的，在占用資源數(shù)量方面，三種調(diào)度策略對于三種類型任務(wù)的總資源成本也呈現(xiàn)與總執(zhí)行時間相似的規(guī)律。在收斂迭代次數(shù)方面，本文算法DRDPSO在各類型任務(wù)都是最少的，GA+PSO算法適合快速求解混合型任務(wù)，SAGA則適合快速求解IO型任務(wù)。在負(fù)載均衡度方面，本文算法DRDPSO和GA+PSO算法的負(fù)載均衡度對于三種類型的任務(wù)的表現(xiàn)相似，即處理CPU型任務(wù)的均衡性最弱，處理IO型任務(wù)的均衡性最好，而SAGA則適合于混合型任務(wù)的均衡調(diào)度。

多次實驗結(jié)果表明，本文DRDPSO策略在大部分情況下在多個指標(biāo)上比其他兩種算法均有更好的表現(xiàn)。但由于算法的隨機性本質(zhì)，不能保證在每次運行時在各個方面(執(zhí)行時間、資源成本、迭代次數(shù))都優(yōu)于對比算法。

表1 在任務(wù)規(guī)模500條件下,三種算法對三種類型任務(wù)的性能比較Tab. 1 Performance comparison of three algorithms for three types of task under task scale of 500

以上實驗結(jié)果表明，本文DRDPSO策略有較為顯著的效果：將慣性系數(shù)由常量修改為變量，使得過程前期搜索速度快而后期搜索精度高，實現(xiàn)對迭代過程的合理控制；以局部最優(yōu)位置代替全局最優(yōu)位置，減少了大量的無效搜索；引入遺傳算法的選擇操作，篩選出優(yōu)質(zhì)個體并傳遞到下一代；引入變異操作實現(xiàn)隨機擾動，改善非優(yōu)質(zhì)粒子的組成，提高了全局最優(yōu)解出現(xiàn)的概率；綜合約束條件使得結(jié)束點更為合理。這些改進(jìn)操作都促進(jìn)了總的執(zhí)行時間、資源成本、迭代次數(shù)的降低，資源-任務(wù)匹配度升高,以及資源負(fù)載均衡度減小。

3 結(jié)語

基于云計算的資源調(diào)度目標(biāo)和要求，本文通過對現(xiàn)有調(diào)度策略的總體分析得出群體智能算法具有較好的處理能力。本文結(jié)合兩種表現(xiàn)較為突出的群體智能算法PSO與遺傳算法優(yōu)勢，并加入了多種改進(jìn)方式，形成了混合式群體智能調(diào)度策略DRDPSO。在CloudSim 平臺上進(jìn)行了兩類仿真測試，大量實驗統(tǒng)計結(jié)果表明，與對比算法SAGA和GA+PSO相比， DRDPSO能夠較為明顯地縮短總的任務(wù)執(zhí)行時間，提高了不同類型任務(wù)下的資源利用率，并適當(dāng)兼顧計算節(jié)點的負(fù)載均衡，能夠較好地解決云計算資源的動態(tài)調(diào)度問題。