摘　要：任務(wù)調(diào)度是云計(jì)算實(shí)現(xiàn)高效計(jì)算的關(guān)鍵技術(shù)。本文采用粒子群算法進(jìn)行任務(wù)調(diào)度求解，對(duì)每個(gè)子任務(wù)占用的資源采用間接編碼方式，考慮時(shí)間和成本定義合理的初始化參數(shù)，選擇合適的適應(yīng)度函數(shù)，盡量避免陷入局部最優(yōu)。仿真結(jié)果表明，改進(jìn)算法具有尋優(yōu)能力強(qiáng)、耗時(shí)少等優(yōu)點(diǎn)，實(shí)現(xiàn)較為理想的任務(wù)調(diào)度結(jié)果。
關(guān)鍵詞：云計(jì)算　任務(wù)調(diào)度　粒子群優(yōu)化算法
      在云環(huán)境中面對(duì)巨大的計(jì)算型任務(wù)，目前的任務(wù)調(diào)度策略還不能達(dá)到所要求的調(diào)度效果^[[1]]。例如，遺傳算法、分層調(diào)度算法、蟻群優(yōu)化算法、種群初始化方法、與能效相關(guān)的耗感知的任務(wù)調(diào)度算法等，它們都不能達(dá)到較好地兼顧調(diào)度執(zhí)行時(shí)間最少與成本最低問(wèn)題，主要原因在于云計(jì)算模型中，任務(wù)執(zhí)行所需要的成本也是一個(gè)不可忽略的因素?？紤]了所有任務(wù)完成時(shí)間與所有任務(wù)完成的總成本這兩個(gè)方面，設(shè)計(jì)了基于改進(jìn)粒子群的任務(wù)調(diào)度算法，兼顧了任務(wù)執(zhí)行時(shí)間和效率，實(shí)現(xiàn)執(zhí)行時(shí)間最少的情況下還能使成本最低，從而達(dá)到節(jié)能的效果。
 
1　任務(wù)調(diào)度問(wèn)題
在云計(jì)算中處理龐大的計(jì)算型任務(wù)常采用分布式并行處理的方式進(jìn)行。云服務(wù)器在接收到一個(gè)完整的大任務(wù)后，采取恰當(dāng)?shù)姆椒ú鸱譃槿舾蓚€(gè)子任務(wù)，并將自任務(wù)合理分配到計(jì)算節(jié)點(diǎn)上去，當(dāng)子任務(wù)處理完成后，匯總結(jié)果給云服務(wù)器回傳給客戶。云計(jì)算環(huán)境普遍采用是谷歌公司設(shè)計(jì)開(kāi)發(fā)的Map/Reduce編程模型^[[2]]，工作原理是Map函數(shù)將用戶提交的任務(wù)分解為多個(gè)子任務(wù)，并將這些子任務(wù)按照調(diào)度算法分配到虛擬機(jī)節(jié)點(diǎn)，待子任務(wù)執(zhí)行完，再有Reduce函數(shù)將產(chǎn)生的中間結(jié)果進(jìn)行匯總處理，圖1表示其執(zhí)行流程。


圖1　Map/Reduce模型執(zhí)行流程
 
2　粒子群算法
粒子群優(yōu)化算法(Particle Swarm Optimization，簡(jiǎn)稱PSO)是模擬鳥(niǎo)群覓食行為而發(fā)展起來(lái)的一種群體協(xié)作的隨機(jī)搜索算法，屬于群體智能算法的一種。PSO算法是由J.Kennedy博士和R.C.Eberhart于1995年共同提出的，因其算法程序結(jié)構(gòu)簡(jiǎn)單、需要調(diào)節(jié)的參數(shù)較少、高效等特點(diǎn)，得到了眾多學(xué)者的重視和研究^[[3]]。

2.1　間接編碼

根據(jù)設(shè)計(jì)的要求采用粒子間接編碼方式，每個(gè)任務(wù)需要占用的計(jì)算資源都要給出編碼。本文假設(shè)R個(gè)任務(wù)，Z個(gè)資源，并且把每個(gè)任務(wù)又分成了若干個(gè)較小的子任務(wù)。子任務(wù)的總數(shù)量表示為：                                              （1）
其中，RNum(s)表示第s個(gè)任務(wù)所含子任務(wù)個(gè)數(shù)。對(duì)子任務(wù)的編碼如下：
                                          （2）
根據(jù)任務(wù)的順序進(jìn)行編碼，第j個(gè)任務(wù)中的第i個(gè)序號(hào)是N[j，i]。假設(shè)R=3、Z=3、SR=10，粒子(2,3,1,2,3,3,2,1,2,1)是一個(gè)可行的調(diào)度策略。
對(duì)于任務(wù)的執(zhí)行時(shí)間，根據(jù)設(shè)計(jì)的要求本文利用矩陣來(lái)記錄，元素[j,i]表示子任務(wù)j在第i個(gè)資源上執(zhí)行的時(shí)間。按單位時(shí)間計(jì)算資源，任務(wù)執(zhí)行的成本費(fèi)用利用RWCB數(shù)組來(lái)表示。RWCB[z]表示第z個(gè)計(jì)算資源單位時(shí)間，任務(wù)運(yùn)行的成本費(fèi)用。
第z個(gè)資源執(zhí)行該資源上第j個(gè)子任務(wù)，所用的時(shí)間用r(z,j)來(lái)表示；分配到此資源上的子任務(wù)，其數(shù)量用m來(lái)表示。完成所有任務(wù)花費(fèi)的總時(shí)間可以表達(dá)為：     
                                           （3）
第s個(gè)任務(wù)完成時(shí)間表示可描述為：
                                      （4)
完成所有任務(wù)的總成本可以表示為：
                                                     (5)

2.2　粒子位置和速度的更新

PSO算法中粒子的速度和位置的計(jì)算更新公式表示如下：
                           (6)
                                                                                   (7)
其中，表示第個(gè)粒子在第代的位置；表示第個(gè)粒子在第代的速度；表示第個(gè)粒子在第代所經(jīng)歷的歷史最優(yōu)位置；代表全局最優(yōu)位置；表示算法的慣性權(quán)重，在經(jīng)典算法中它的取值一般為0.942，用于衡量舊的速度對(duì)新速度的影響；和為加速常數(shù)，一般情況下取值為1；和是相互獨(dú)立的隨機(jī)數(shù)。對(duì)慣性權(quán)重進(jìn)一步優(yōu)化，提出一種小阻尼隨機(jī)擾動(dòng)的改進(jìn)方法，慣性權(quán)重計(jì)算公式如下所示：
                             （8）
式中，為引入的小阻尼振動(dòng)函數(shù)，利用小阻尼振動(dòng)來(lái)非線性地控制算法中的慣性權(quán)重編號(hào)情況，使其隨著迭代次數(shù)的增加而出現(xiàn)非線性隨機(jī)擾動(dòng)現(xiàn)象。在慣性權(quán)重中加入了小阻尼隨機(jī)擾動(dòng)策略，既增強(qiáng)了種群的多樣性，而且還拓展了PSO算法的開(kāi)拓能力^[3]，有效地避免了停滯現(xiàn)象的發(fā)生。圖2表示了改進(jìn)粒子群優(yōu)化算法的執(zhí)行流程。


圖2  改進(jìn)PSO算法流程圖

3　實(shí)驗(yàn)仿真結(jié)果及分析

在Matlab R2009b上實(shí)現(xiàn)該算法仿真，并將算法應(yīng)用到云計(jì)算平臺(tái)的資源調(diào)度模塊中。利用云計(jì)算仿真平臺(tái)CloudSim對(duì)兩個(gè)算法進(jìn)行了相同云環(huán)境下的仿真實(shí)驗(yàn)，并進(jìn)行比較，實(shí)驗(yàn)迭代運(yùn)行200次，根據(jù)參考文獻(xiàn)[[4]]，算法參數(shù)設(shè)定為：粒子群規(guī)模150，迭代次數(shù)t_max=200，學(xué)習(xí)因子c1=c2=0.926，權(quán)重參數(shù)w=0.9。把任務(wù)數(shù)設(shè)置為100，則改進(jìn)PSO算法和標(biāo)準(zhǔn)PSO算法的收斂曲線和任務(wù)完成時(shí)間分別如圖3和圖4所示。


圖3　改進(jìn)PSO算法與標(biāo)準(zhǔn)PSO算法總?cè)蝿?wù)完成時(shí)間對(duì)比
             

圖4　高任務(wù)強(qiáng)度下算法的任務(wù)完成對(duì)比情況
從仿真結(jié)果可以看出，粒子在前期迭代過(guò)程中，經(jīng)典粒子群算法與本文改進(jìn)的粒子群在任務(wù)總完成時(shí)間和成本相差不太大，但隨著粒子迭代更新數(shù)量的增大，本文改進(jìn)的粒子群算法所得到的任務(wù)完成時(shí)間和成本都在不斷的減小，明顯小于傳統(tǒng)的粒子群算法。傳統(tǒng)的粒子群算法丟失了一些潛在優(yōu)良粒子，雖然提高了收斂速度，但是無(wú)法有效跳出局部最優(yōu)狀態(tài)，過(guò)早收斂到局部最優(yōu)的調(diào)度結(jié)果上^[4]。本文算法設(shè)計(jì)了合適的適應(yīng)度函數(shù)，不僅考慮所有任務(wù)完成的時(shí)間，也考慮所有任務(wù)完成所需要的成本費(fèi)用，該算法任務(wù)調(diào)度結(jié)果表明，所有任務(wù)完成所需要的時(shí)間縮短了，執(zhí)行效率也較傳統(tǒng)PSO算法提高了。

 

4　結(jié)語(yǔ)

對(duì)于任務(wù)調(diào)度算法，一般采用總?cè)蝿?wù)完成時(shí)間作為度量標(biāo)準(zhǔn)，卻沒(méi)考慮任務(wù)完成所需成本，本文針對(duì)云計(jì)算的任務(wù)調(diào)度模型，在改進(jìn)粒子群算法的基礎(chǔ)上，提出了一種改進(jìn)的任務(wù)調(diào)度算法，既考慮了所有任務(wù)完成的總時(shí)間，也考慮了任務(wù)完成所需要的總成本。今后將從參數(shù)設(shè)置、慣性權(quán)重等方面進(jìn)一步研究IPSO算法對(duì)任務(wù)調(diào)度效率的影響，從而進(jìn)一步提高執(zhí)行效率，實(shí)現(xiàn)更為理想的調(diào)度效果和負(fù)載均衡。
 
參考文獻(xiàn)：
[[1]]駱劍平,