自適應動態調整粒子群的云計算任務調度

侯 歡 歡

(太原工業學院計算機工程系 山西 太原 030008)

0 引 言

云計算是一種新型的商業計算模式，它是并行計算、分布式計算和網格計算融合發展的結果。云計算的發展一直與大數據密切相關，正是依靠云計算技術才使龐大的數字資源得以高效的分析處理[1]。為提高數據處理的高效性，云計算將每個任務分成若干個相互獨立的任務，通過任務調度將任務分配給計算資源進行處理。隨著用戶需求的日益提高，如何滿足用戶請求,提高云計算任務調度效率已經成為云計算研究領域的關鍵問題之一。傳統任務調度算法很難均衡云計算環境下的多維約束調度，粒子群優化算法(Partical Swarm Optimization，PSO)是一種群體智能全局尋優的算法[2]。該智能優化算法在優化組合、多目標尋優、聚類分析等領域應用廣泛且效果突出[3-5],利用智能優化算法在多維度多任務方面的尋優優勢引起了越來越多學者的研究與關注，已成為云計算任務調度的新工具。文獻[6]在分組遺傳算法的基礎上，提出了基于多維資源協同聚合的虛擬機調度策略，對均衡資源分配具有一定的優勢；文獻[7]提出了基于改進遺傳算法的云計算任務調度，通過兩個適應度來選擇種群，縮短了總任務和平均任務完成時間；文獻[8]綜合考慮遺傳算法和蟻群算法的優勢,提出一種遺傳-蟻群算法的云計算任務調度優化算法,提高云計算任務求解效率；文獻[9]把改進的蟻群算法應用到云計算任務調度中，實現了虛擬機的負載均衡和調度時間的優化；文獻[10]針對用戶滿意度和云提供商利益需求，提出一種融合粒子群和遺傳算法的PSOGA改進算法;文獻[11]在遺傳算法基礎上,提出了一種考慮時間、成本、CPU、內存和帶寬等多維約束的任務調度算法MCGA；文獻[12]針對標準量子粒子群優化算法收斂速度慢、求解效率低的缺陷,提出一種基于改進量子粒子群算法的云計算資源調度方法;文獻[13]提出了一種基于非占優排序的混合多目標粒子群優化的工作流調度算法HPSO,使調度解的空間分布更加一致，云環境工作流調度更優化；文獻[14]綜合考慮任務截止時間、調度預算和可靠性，提出一種多QOS約束離散粒子群優化的任務調度算法,有效解決了多約束任務調度。本文融合改進的分數階達爾文粒子群算法和多目標函數構造，提出了一種新的云計算任務調度算法。

1 粒子群優化算法及其衍化

1.1 粒子群算法

粒子群優化算法與其他智能優化算法一樣，易陷入局部最優、搜索精度不高、后期收斂慢等問題。針對這些問題，國內外學者提出了多種改進算法。文獻[15]將達爾文進化理論引入粒子群優化算法中，提出了一種達爾文粒子群優化算法(Darwinian Partical Swarm Optimization,DPSO)。文獻[16]將分數階微分理論引入粒子群優化算法中，提出了分數階粒子優化算法(Fractional Order Partical Swarm Optimization,FOPSO),通過重排原始速度來修正速度導數以便控制優化算法的收斂速度，取得了不錯的效果。受文獻[16]的啟發，學者Micael將分數階微分和達爾文進化理論相結合，集中兩者的優點應用于粒子群優化算法中，提出了分數階達爾文粒子群算法(Fractional Order Darwinian Partical Swarm Optimization,FODPSO)。實驗結果表明，與其他智能優化算法相比，該算法通過分數階次α來控制計算精度與收斂速度，由于過度依賴分數階次α，容易造成局部最優[17]。恰當的權重系數ω不僅能提高尋優能力還能加速收斂速度。但現實中對權重系數ω的設置往往是手動設置固定值，這不利于粒子群對最優解的搜索。

在一個M維目標空間中，Nnum個粒子組成群落，每個粒子的速度和位置更新：

(1)

(2)

第i個粒子位置向量為Xi=(xi1,xi2,…,xiD)，速度向量為Vi=(vi1,vi2,…,viD)，第i個粒子經歷過的位置中最優位置Wi=(wi1,wi2,…,wiD)，整個粒子群最優位置Wg=(wg1,wg2,…,wgD)。式(1)中：ω表示慣性系數；c1、c2表示加速系數；R1d、R2d為[0,1]間的隨機數；wid表示粒子個體最優值；wgd表示粒子群整體最優值。

1.2 粒子群算法的衍化

DPSO將自然選擇理論引入算法中，對粒子群的壽命進行動態縮減。設SC為粒子搜索計數器用以追蹤粒子群適應值沒有改變次數。當粒子群適應度沒有提高時，其中的粒子被刪除后，該粒子群的搜索計數器不置為0，而以下式進行設置：

(3)

式中：Nkill表示粒子群適應值沒變化期間被刪除的粒子數；SCmax表示最大計數值。若粒子群中所有粒子被刪除，且當前粒子群數沒有超過種群設置數，新建粒子群概率為：

p=r/Nnum

(4)

式中：r為[0,1]間隨機數；Nnum表示種群粒子數。文獻[17]給出了分數階次α調整公式：

(5)

通過大量實驗可知分數階次α在[0.5,0.8]之間時，FODPSO算法可取得較快的收斂速度。但是通過式(5)可以看出：隨著迭代次數的加大，分數階次α會線性減小，這勢必會使粒子群陷入局部最優和低速收斂。同時根據式(1)可以看出：權重系數ω越大，速度v就大，這有利于擴大最優解的搜索空間；當權重系數ω越小，速度v就小，這會在當前解空間中挖掘更好解，因此權重系數ω的設置不能拘泥于定值。對此，本文通過改變分數階次α和慣性權重系數ω的調整方式和陷入局部最優的跳出方式，對分數階達爾文粒子群算法進行改進。

2 改進分數階達爾文粒子群算法

2.1 基于自適應動態調整權重系數

研究學者統計實驗發現，動態的權重系數要比固定設置的能獲得更好的尋優結果[18]。借鑒前人研究，將粒子的適應度值引入慣性權重系數ω的調整中，提出了一種基于自適應度動態調整權重系數的方法。設favg為粒子群平均適應度，fbest為粒子群最佳適應度，第i個粒子的適應度為fi，慣性權重系數ω的調整如下：

(6)

式中：ωmin、ωmax表示慣性權重系數ω的最小、最大值。通過式(6)我們可以看出當前粒子適應度與平均適應度差值越大，慣性權重系數ω越小，這有利于局部搜索；反之，當前粒子適應度與平均適應度差值越小，慣性權重系數ω越大，有利于粒子跳出局部進行范圍更廣的搜索最優解。

2.2 基于進化信息調整分數階次α

(7)

(8)

(9)

(10)

(11)

基于粒子進化因子fev∈[0,1]，利用高斯圖函數得出分數階次α的調整公式：

(12)

通過式(12)可知，分數階次α的調整不再依賴迭代次數，而是依據粒子自身的進化信息，這可避免算法因分數階次α線性減小而引起的局部最優和收斂緩慢。

根據分數階微分方程的格林瓦德-列特尼科夫(G-L)定義，粒子速度更新策略變為：

(13)

粒子的位置更新依據式(2)進行，其中加速系數滿足3≤c1+c2≤4。

2.3 基于Levy飛行特征的局部最優

本文將Levy飛行特性引入改進的分數階達爾文粒子群算法中，利用Levy飛行特性擴展搜索空間，根據局部最優概率因子popt對算法取得局部最優wg進行位置擾動。

定義局部最優概率因子popt：

(14)

wgd=wgd(1+levy(ξ)tanh(fev))

(15)

式中:Levy(ξ)是隨機搜索路徑，步長的大小通過levy分布隨機數產生且1≤ξ≤3，0≤fev≤1，0≤tanh(·)≤1。

3 云計算任務調度

云計算是利用并行計算來處理大數據，是按需服務的模式，資源調度與網格計算的任務調度相差無幾，但云計算以資源虛擬化為前提，通常采用Map/Reduce分布處理技術[19]。云計算任務調度數學模型可表示為：

Model={T,VM,F,A}

(16)

式中：任務集合T={T1,T2,…，Tn}；n表示任務的個數；每個任務都有屬性TAi=,sTi、eTi、dTi,TLi分別表示任務的大小、最早開始時間、最遲完成時間和任務執行總時間。虛擬機集合VM={VM1,VM2,…，VMm}，其中m表示虛擬機個數。每個虛擬機都有屬性：VAj=,Vcompj、Vcpuj、Vramj、Vbwj分別表示虛擬機j的處理能力、CPU、內存、帶寬。

3.1 任務調度的多目標

綜合評價云計算任務調度的優良需要從客戶最短等待時間、虛擬機資源負載均衡程度及任務完成所耗費用等不同角度進行。

(1) 客戶最短等待時間WFi:

(17)

式中：timeij表示任務Ti在所分配的虛擬機VMj上執行所需時間；sum(VMj)表示分配到虛擬機VMj上的任務總數。綜上可知客戶最短等待時間WFi表示各個虛擬機處理完成分配到的任務Ti的最遲完成時間的最大值。這里需要特別說明，任務的處理時間等于任務指令長度除以運行該任務虛擬機的執行速度：

timeij=TAi/VAj

(18)

(2) 虛擬機資源負載均衡程度?:

(19)

(3) 任務完成所耗費用Cost:

(20)

式(20)體現了虛擬機VMj上處理任務的費用所耗，所用費用與虛擬機的CPU、內存、帶寬性能有關。

本文從客戶最短等待時間、虛擬機資源負載均衡程度及任務完成所耗費用等三個目標出發綜合衡量云計算任務調度的優良，數學模型如下：

minWF,min?,minCost

(21)

式中: 目標函數minWF、min?、minCost表示客戶最短等待時間、虛擬機資源負載均衡程度及任務完成所耗費用等三個目標要同時取得最小值，并且約束條件是任務只能被一個虛擬機執行。

3.2 任務調度多目標函數構造

任務調度的好壞不僅僅由一個目標函數決定，本文將最短等待時間、虛擬機資源負載均衡程度及任務完成所耗費用等三個目標以基于先驗偏好[20]構造任務調度滿意度函數，再將任務調度的多目標問題轉化成單目標問題。設客戶最短等待時間的區間為[WFmin,WFmax]，虛擬機資源負載均衡程度滿意區間[?min,?max]，任務完成所耗費用區間[Costmin,Costmax]，引入極小值ε，三個目標的計算如下：

(22)

(23)

(24)

利用幾何平均法將以上三個目標進行融合，任務調度綜合滿意度評價為：

(25)

通過式(25)可知，利用幾何平均法將三個評價目標轉換為綜合滿意度CS，并且只有當且僅當三個評價目標同時滿意度為1時，綜合滿意度CS才為1。

3.3 粒子編碼規則

粒子編碼有兩種，一是直接編碼，另一種是間接編碼。本文采用間接編碼方式即對每個子任務所對應的虛擬機進行編碼，也就是說一個粒子對應著一個任務的分配策略。比如任務數n=3，虛擬機數m=3,任務分解后的子任務數mall=10，粒子編碼(2,3,1,2,3,3,2,1,2,1)即為一種可行的任務調度方案。粒子編碼如表1所示。

表1 粒子編碼

續表1

表1中，任務序號、子任務序號對(3,9)表示第3個任務中的第4個子任務序號為9；子任務序號、虛擬機序號對(2,3)表示把子任務2分配到虛擬機3上去執行。

4 仿真實驗

為了驗證本文改進算法的優越性，從兩個方面進行對比分析：一是利用四種測試函數對比尋優效果；二是通過任務調度對比分析算法的調度性能。采用Cloudsim 3.0云平臺軟件對算法的實際調度性能進行仿真對比，仿真是在Windows 7系統下，CPU：i5-4460T@2.7 GHz, RAM:4 GB。

4.1 尋優效果對比分析

將本文算法、FOPSO和FODPSO在表2所示的四個標準函數上[17]對比尋優效果。三種粒子群優化算法的參數設置如表3所示。種群規模設為50，最大迭代次數為1 000次。三種粒子群優化算法運行100次取平均。

表2 四個標準函數

表3 參數設置

圖1為三種智能優化算法對表2四個標準函數的尋優收斂曲線。

圖1 三種粒子群優化算法尋優收斂曲線

由圖1可以看出：FOPSO和FODPSO對Rastrigin標準函數的尋優效果一般，過早陷入了局部最優；隨著迭代次數的增加，FOPSO和FODPSO在多峰Ackley函數、單峰Sphere、Rosenbrock函數上，收斂速度緩慢，尋優精度不精。而本文改進算法無論是對Sphere、Rosenbrock兩種單峰函數還是對Rastrigin、Ackley多峰函數都能在若干次迭代后迅速從局部最優中跳出，并快速搜尋到最優值，擴大了對最優值的全局搜索能力。

4.2 任務調度對比分析

在Cloudsim 3.0平臺中將云計算任務調度算法添加到DatacenterBroker類中；通過重置Cloudlet類和VM類進行虛擬機和任務的參數設置。將本文改進算法與文獻[10，13，21]進行云計算任務調度，使用最大完成時間、截止時間違背率和虛擬機資源利用率三個云計算任務調度評價指標定量分析調度結果。本文粒子群參數設置詳見表3，任務數n=200，資源數m=50，其他算法的參數設置參照對應參考文獻。

(1) 最大完成時間。最大完成時間是評價任務調度的重要指標，最大完成時間越小表示任務完成的速度越快，算法的調度性能越好。通過設置不同的任務量，對比各算法的最大完成時間，結果如圖2所示。

圖2 四種任務調度算法最大完成時間

圖2顯示了在不同任務總數參與調度的情況下，各調度算法最大完成時間的趨勢。隨著任務數的增多，各算法完成任務調度的最大完成時間隨之增大。文獻[13]不僅改進了粒子算法固有的尋優劣勢，還綜合了任務調度的多目標，將最晚完成時間作為任務調度的考核目標之一，任務完成的最大時間與其他兩種算法相比較小。文獻[10，21]對粒子群算法的改進并不徹底，粒子群算法任然存在陷入局部最優和收斂過慢的毛病，并且調度考核的目標單一，任務完成最大時間隨著任務數的增大而不斷增大。本文算法通過調整分數階次α系數以加速收斂，利用Levy飛行隨機擾動以擺脫局部最優，自適應動態調整權重系數來收縮自如地尋找最優值，較為全面地改進分數階達爾文粒子群算法，并將最短等待時間、資源負載均衡程度及任務完成所耗費用等三個目標規劃為單一目標評價函數，以作為任務調度的評價目標，取得了較好的調度效果。

(2) 截止時間未完成率。截止時間是任務調度最根本的要求，也是考量任務調度的基本指標。調度算法對大量任務進行調度時，很難萬無一失地在截止時間前完成所有數據處理。截止時間未完成率就是在截止時間未完成的任務數與總任務數的間比值。通過設置不同的任務量，對比各算法的截止時間未完成率，結果如圖3所示。

圖3 四種任務調度算法截止時間未完成率

圖3顯示了不同任務總數與截止時間未完成率的關系。隨著任務數的增多，本文任務調度算法與文獻[13]都維持在較低的截止時間未完成率，兩者相比較而言，本文調度算法的未完成率較低，一直保持在5%以下，這是由于本文的目標函數中有客戶最短等待時間這一評價約束目標。文獻[21]單以截止時間為約束，粒子群優化算法改進不到位，制約了最終的調度結果。文獻[10]主要考慮任務與資源的負載率，并沒有將任務完成截止時間作為任務調度的約束條件，致使任務截止時間未完成率較高。

(3) 虛擬機資源利用率。虛擬機資源利用率表示虛擬機資源的整體利用程度[22]。公式為:

(26)

式中：tj.stime表示任務j的開始時間；tj.etime表示任務j的結束時間；Δij為布爾變量，若Δij=1表示任務j被分配到虛擬機i上執行，反之亦然；Tetime表示所有任務完成總時間。在任務數n=100的情況下，隨機選取10個虛擬機(5,10,18,27,39,46,55,63,72,80)，對比分析各算法在虛擬機上的資源利用率，結果如圖4所示。

圖4 各算法虛擬機資源利用率對比

圖4顯示了各算法在不同虛擬機上的資源利用率，在任務數一定的情況下，本文算法的任務調度較為均衡，虛擬機資源利用較為充分，資源利用率始終保持在95%以上。文獻[13]綜合任務執行代價和執行能耗，以此均衡各虛擬機間的負載，也獲得了不錯的效果，資源利用率始終保持在90%以上。文獻[10]和文獻[21]以截止時間或執行綜合能耗為評價目標，虛擬機均衡無法圓滿地兼顧，資源利用率波動較大，各虛擬機間的負載不夠均衡。

5 結 語

本文提出了一種基于分數階達爾文粒子群的多目標云計算任務調度算法。通過改變分數階次α和慣性

權重系數ω的調整方式和陷入局部最優的跳出方式，對分數階達爾文粒子群算法進行改進，融合最短等待時間、資源負載均衡及任務完成所耗費用等三個目標構造任務調度滿意度函數，以此搜索任務調度最優解。仿真實驗表明，本文改進的調度算法與其他三種調度算法相比，本文調度算法不僅有最低的任務最大完成時間和截止時間未完成率，還較好地完成了虛擬資源的均衡負載。