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


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

2.1　間接編碼

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

2.2　粒子位置和速度的更新

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


圖2  改進PSO算法流程圖

3　實驗仿真結果及分析

在Matlab R2009b上實現該算法仿真，并將算法應用到云計算平臺的資源調度模塊中。利用云計算仿真平臺CloudSim對兩個算法進行了相同云環境下的仿真實驗，并進行比較，實驗迭代運行200次，根據參考文獻[[4]]，算法參數設定為：粒子群規模150，迭代次數t_max=200，學習因子c1=c2=0.926，權重參數w=0.9。把任務數設置為100，則改進PSO算法和標準PSO算法的收斂曲線和任務完成時間分別如圖3和圖4所示。


圖3　改進PSO算法與標準PSO算法總任務完成時間對比
             

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

 

4　結語

對于任務調度算法，一般采用總任務完成時間作為度量標準，卻沒考慮任務完成所需成本，本文針對云計算的任務調度模型，在改進粒子群算法的基礎上，提出了一種改進的任務調度算法，既考慮了所有任務完成的總時間，也考慮了任務完成所需要的總成本。今后將從參數設置、慣性權重等方面進一步研究IPSO算法對任務調度效率的影響，從而進一步提高執行效率，實現更為理想的調度效果和負載均衡。
 
參考文獻：
[[1]]駱劍平,