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

喻德曠，楊 誼，錢(qián) 俊

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

0 引言

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

針對(duì)云計(jì)算資源調(diào)度問(wèn)題，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了許多調(diào)度策略，根據(jù)算法原理可分為三大類(lèi)。第一類(lèi)是靜態(tài)資源調(diào)度策略[4]，如數(shù)學(xué)規(guī)劃、專(zhuān)家系統(tǒng)、神經(jīng)網(wǎng)絡(luò)和模糊邏輯策略，這類(lèi)方法的優(yōu)點(diǎn)是規(guī)則嚴(yán)密、邏輯清晰，但是規(guī)則較為復(fù)雜，只適合小規(guī)模資源的靜態(tài)調(diào)度。第二類(lèi)是傳統(tǒng)動(dòng)態(tài)資源調(diào)度策略，包括基于貪心思想的策略(Min-min算法、Max-min算法、Sufferage算法等)[5]和基于操作系統(tǒng)調(diào)度的策略，如FIFO(First In First Out)算法、公平調(diào)度算法、計(jì)算能力調(diào)度算法等[6]。這些策略可以實(shí)現(xiàn)資源動(dòng)態(tài)調(diào)度，但由于參與操作的因子很多，用于大規(guī)模任務(wù)調(diào)度計(jì)算復(fù)雜度太高。第三類(lèi)是啟發(fā)式策略，主要包括遺傳算法和粒子群算法[7]。例如，文獻(xiàn)[8]提出了一種基于模擬退火思想的改進(jìn)遺傳算法，在退火過(guò)程中以一定概率接受劣質(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)算法對(duì)其求解；文獻(xiàn)[11]改進(jìn)了PSO的搜索方向、適應(yīng)度函數(shù)等方面；文獻(xiàn)[12]將粒子群算法和差分遺傳算法結(jié)合求解；文獻(xiàn)[13]設(shè)計(jì)了雙向搜索的改進(jìn)粒子群算法等。

1 動(dòng)態(tài)隨機(jī)擾動(dòng)PSO策略的基本思路

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

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

1.1 建立云計(jì)算資源模型

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

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

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

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

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

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

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

(1)

(2)

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

TotalCost=μ1ETC+μ2CRC

(3)

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

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

1.2 動(dòng)態(tài)隨機(jī)擾動(dòng)PSO策略

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

1.2.1 簡(jiǎn)化的編碼設(shè)計(jì)

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

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

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

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ù)。

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

(6)

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

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

一是迭代次數(shù)。迭代過(guò)程中粒子的更新速度應(yīng)當(dāng)是前快后慢，這是由于起始點(diǎn)是隨機(jī)解，應(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)度(綜合代價(jià)TotalCost)。根據(jù)前面分析的云計(jì)算資源調(diào)度目標(biāo)和所涉及的衡量指標(biāo)，本文策略的適應(yīng)度函數(shù)主要由式(3)決定，即同時(shí)考慮總的執(zhí)行時(shí)間和總的資源開(kāi)銷(xiāo)。此外，各臺(tái)服務(wù)器節(jié)點(diǎn)的負(fù)載平衡度不應(yīng)差異過(guò)大，否則會(huì)造成某些節(jié)點(diǎn)壓力重，容易出現(xiàn)瓶頸，而某些節(jié)點(diǎn)的資源得不到有效利用，因此本文定義了負(fù)載均衡指標(biāo)。云平臺(tái)中某個(gè)計(jì)算節(jié)點(diǎn)j的負(fù)載均衡因子LBj定義為：

(7)

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

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

(8)

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

1.2.3 縮小搜索范圍

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

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

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

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

(9)

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

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

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

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

1.2.6 DRDPSO策略流程

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

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

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

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

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

Step6 對(duì)當(dāng)前群體Ntop個(gè)適應(yīng)度最高的優(yōu)質(zhì)粒子直接進(jìn)入下一代。按照式(9)概率對(duì)非優(yōu)質(zhì)粒子進(jìn)行選擇和隨機(jī)變異操作，生成下一代群體；轉(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è)每個(gè)粒子每一次迭代需要的運(yùn)算時(shí)間為T(mén)i，則經(jīng)典PSO算法總的運(yùn)行時(shí)間為O(Nc*Ti*m)。本文DRDPSO策略將群體搜索范圍控制在NeighNum而不是所有粒子(NeighNum根據(jù)經(jīng)驗(yàn)設(shè)置，通常為總粒子數(shù)量的1/3)，即搜索范圍縮小至原來(lái)的1/3，且隨著迭代的進(jìn)行，后期符合條件的粒子的數(shù)量還會(huì)逐漸減少(非單調(diào))。設(shè)每個(gè)粒子每一次迭代需要的運(yùn)算時(shí)間為T(mén)i，則本文DRDPSO策略總的運(yùn)行時(shí)間為O(Ni*Ti*m)，其中Ni≤1/3Nc。比經(jīng)典PSO算法增加的計(jì)算式(6)、(8)、(9)均為常數(shù)級(jí)計(jì)算，對(duì)時(shí)間復(fù)雜度帶來(lái)的增量遠(yuǎn)遠(yuǎn)小于搜索范圍帶來(lái)的減量，可以忽略。本文DRDPSO策略改進(jìn)的效果在運(yùn)行時(shí)間方面主要體現(xiàn)在:每一次迭代中的搜索范圍大大減少,參與下一步運(yùn)算的粒子數(shù)大大減少，使得運(yùn)行時(shí)間減少。而增加的計(jì)算部分使得對(duì)資源調(diào)度的評(píng)估標(biāo)準(zhǔn)更合理，解的多樣性更好。

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

2.2 任務(wù)類(lèi)型單變量實(shí)驗(yàn)結(jié)果

為了比較對(duì)不同類(lèi)型任務(wù)的處理效果，將任務(wù)劃分為三類(lèi)：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)。實(shí)驗(yàn)結(jié)果表明，三種算法各自在相同任務(wù)規(guī)模下的性能基本保持一定的規(guī)律。以任務(wù)規(guī)模500為例，三種算法對(duì)三種類(lèi)型任務(wù)的平均總執(zhí)行時(shí)間、平均總的資源成本、平均迭代次數(shù)和平均資源負(fù)載均衡度如表1所示。

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

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

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

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

3 結(jié)語(yǔ)

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