云計算環境下基于改進粒子群算法的任務調度

張照勝，李蜀瑜

（陜西師范大學 計算機科學學院，陜西 西安 710119）

云計算環境下基于改進粒子群算法的任務調度

張照勝，李蜀瑜

（陜西師范大學 計算機科學學院，陜西 西安 710119）

為了優化云計算環境下任務調度，考慮調度過程中任務的最短完成時間、系統的負載均衡和經濟成本3個目標約束，然而3個目標約束之間存在沖突，因此提出了一種使用改進粒子群優化算法來解決云計算任務調度中多目標優化問題，達到同時兼顧3個目標約束的目的。選擇慣性權重的模糊自適應策略對粒子群算法進行改進，從而能很好的平衡粒子的全局搜索能力和局部搜索能力，盡量避免過早收斂和陷入局部極值，并且引入移動子和負載因子的概念，用于實現算法對云計算環境下的任務調度。仿真結果表明，該算法對多目標優化問題，具有較好的尋優能力。

云計算；任務調度；粒子群算法；最短完成時間；負載均衡；經濟成本

云計算[1]是分布式計算的一種，是網格計算[2]和并行計算的發展，是這些計算科學概念的商業實現。其最基本的概念是，龐大的計算處理任務透過網絡被自動拆分成很多較小的子任務，再交由多部服務器所組成的龐大系統經搜尋、計算分析之后將處理結果回傳給用戶。

由于云計算所面對的計算任務數量十分龐大，任務調度和資源分配問題是決定云計算效率的重點與難點。文獻[3]中對云計算的優點和面臨的問題進行了綜述；文獻[4]中基于文化算法和粒子群算法的混合，進行云計算資源的調度，提高了系統資源的利用率，保持了系統的負載均衡；文獻[5]中引入動態多群體協作和變異粒子逆向飛行的思想與PSO結合，進行云計算服務集群資源調度，優化系統的負載均衡；文獻[6]中基于對粒子群算法的慣性權重進行改進和引入個體最優位置的平均值的概念，依據云計算中的任務分配建模過程，優化云計算在調度中任務派發速度和資源利用率；文獻[8]中通過對云計算環境下的數據部署進行問題描述和建模，構造粒子群算法適應度函數，優化了傳輸和處理所需的時間和費用；文獻[9]中采用粒子群算法，對云計算任務調度中的最小任務完成時間和最快任務響應時間這兩個目標約束進行優化；文獻基于魚群算法中的聚群行為有較強的跳出局部極值的能力，能表現出全局收斂性好等特點，在粒子群算法中建立粒子中心的概念，利用聚群特性進行優化，進而改進粒子群算法的全局收斂能力；文獻[10]引入粒子的搜索中心概念，分析搜索中心在全局最優解和局部最優解之間均勻分布，優化粒子群算法的收斂速度和穩定性；文獻[11]構造了一種對慣性權重進行調整的非線性函數，在速度更新公式中增加了動態的隨機數，并引入在一定條件下對粒子位置重新擴散機制，提高群體后期的多樣性，很好的改善了算法的尋優性能；文獻[12]引入人工免疫系統中的克隆變異選擇機制和精英粒子學習機制（柯西分布的精英學習策略），增加粒子種群的多樣性和增強粒子逃離局部極值，提高多峰值函數優化時全局尋優能力；文獻[13]中基于改進的粒子群算法，對云計算環境下任務調度中最短完成時間、經濟成本和能耗3個目標約束進行優化，但沒有考慮負載均衡這一重要目標約束。鑒于以上文獻對云計算的任務調度目標約束的優化僅限于單個或兩個，或未考慮負載均衡這一重要目標約束，以及對粒子群算法改進策略的分析研究。

因此，本文中我們考慮3個目標約束，即任務的最短完成時間、負載均衡和傳輸處理的經濟成本，并采用改進的粒子群算法優化多目標約束條件下的任務調度。

1 問題模型

在這個部分，用形式化的方式描述了系統模型。最終期望達到的目標是，既滿足用戶對服務質量的要求，又滿足云服務提供商的要求。因此，首先描述了云計算任務調度模型，其次描述了云計算任務調度的最小完成時間、負載均衡和經濟成本3個目標約束。通過對云計算任務調度模型和3個目標約束的描述，得出要解決的是一個多目標優化問題。

1.1 云計算任務調度

目前，云計算環境下，Google提出的Map/Reduce編程模式是主流，該模式分為Map（映射）和Reduce（規約）兩個階段，把一個大任務拆分成多個較小的子任務，然后再將子任務進行分配，本文只考慮子任務相互獨立的情況。通過將子任務合理的分配到資源結點上，從而使得任務的完成時間達到最小，系統的負載達到均衡，經濟成本最少。

在云計算環境下，將N個相互獨立的子任務分配給M個資源結點。其中，任務集表示為 T={t1，t2，…，tN}，tj（j=1，2…，N）表示第j個子任務。資源結點集表示為VM={{vm11，vm12，…，vm1k}，{vm21，vm22，…，vm2k}，…，{vmm1，vmm2，…，vmmk}}vmij（i= 1，2，…，m；j=1，2，…，k）表示第i個虛擬機上的第j個資源結點，每個子任務只能在一個資源結點上執行。任務集T與虛擬機上資源結點集VM的分配關系可用矩陣X表示為：

1.2 云計算任務調度的目標約束

1.2.1 最短完成時間

最短完成時間是從提交所有子任務開始，直到最后一個子任務執行完成所需要的時間。N個子任務t1，t2，…，tN，可能分布在空間不同的位置，N個子任務是相互獨立的，m個虛擬機VM1、VM2、...、VMm，分布在空間不同的位置。N個子任務發出請求，任務調度器首先會根據每個任務當前的位置，將任務分配到距離該任務最近的一個虛擬機，該距離表示發出該任務請求的用戶與響應該任務請求的虛擬機之間的地理位置距離。一個虛擬機表示一個Logical cluster，一個Logical cluster由若干個物理機組成，一個物理機表示一個資源結點[14]，一個子任務對應一個資源結點。假設一個虛擬機包含k個資源結點，虛擬機個數m，系統資源結點總數M=m*k。

每個子任務的數據量映射為百萬條指令，order1表示任務ti需要處理的數據量。receivek：k={1，2，...，m}表示虛擬機k每小時可接收多少百萬條指令，sendk：k={1，2，...，m}表示虛擬機k每小時可發送多少百萬條指令，processk：k= {1，2，...，m}表示虛擬機 k每小時可處理多少百萬條指令。

初始分配傳輸時間：初始時刻子任務j分配到虛擬機p上的傳輸時間

轉移時間：如果子任務j所分配的虛擬機p過載，那么需要將該任務從虛擬機p轉移到未過載的虛擬機q，轉移時間為

執行時間：子任務j在虛擬機q上的執行時間

子任務j在虛擬機q上期望完成時間為ECTqj=TTpj+MTpqj+ ETqj，那么max{ECTqj}為總任務的完成時間，Cmax=max{ECTqj}，優化目標是總任務的完成時間最短。

1.2.2 負載均衡

當分配到某個虛擬機上的任務過多，而有些虛擬機上分配的任務可能又太少，這就會造成整個系統的資源負載不均衡、系統的性能下降和資源的浪費。因此，為了使得整個系統負載均衡，本文給出的策略是，將已分配任務但未過載的虛擬機和未分配任務的虛擬機（任務數為0）按分配的任務量從小到大排列，將過載虛擬機上多余的任務移動到未過載或未分配的虛擬機上。為了表示每個虛擬機的負載情況，定義了負載因子的概念。

虛擬機vmi上分配的子任務數為α，承載子任務的上限為β，定義負載因子θi，其中θi=α-β，如果θi>0，那么虛擬機i就處于過載狀態，如果θi<0，那么虛擬機i就處于未過載狀態。

Then 1.負載不均衡；2.將過載虛擬機（θi>0）上多余的子任務向未過載虛擬機（θi<0）上轉移；3.整個虛擬機系統的負載因子

優化的目標是整個虛擬機系統的負載因子θ的值最小。

1.2.3 經濟成本

在負載均衡模型中，將過載的虛擬機上的多余的任務重新分配到未過載的虛擬機上，在重新分配的過程中，如果采用優先選擇未分配或已經分配任務量最少的虛擬機策略，可能出現的情況是，待分配的任務與該虛擬機的距離較遠，這樣就會增加傳輸時間和傳輸成本，從而增加任務的總完成時間，同時也增加了經濟成本。基于經濟成本因素的考慮，再重新分配時，優先選擇離該任務最近的虛擬機。

定義：總成本=處理成本+移動成本

子任務j在虛擬機q上處理的費用pcqj，處理時間為ETqj，單位時間的處理費用為pl，其中l∈{1，2，…，m}

子任務的處理成本：

所有任務的處理成本：

子任務的移動成本：

所有任務的移動成本：

總成本AC=PC+TC，優化的目標是完成全部任務的總成本AC最少。

2 模糊自適應粒子群算法

粒子群算法是1995年Eberhart博士和Kennedy博士受鳥類族群覓食訊息傳遞的啟發，提出的一種基于群體協作的隨機搜索算法，該算法優點是實現容易、收斂速度快、求解精度高。但是，標準粒子群算法在搜索過程中，容易過早收斂和陷入局部極值。基于ω起著權衡局部最優能力和全局最優能力的作用，本文使用模糊技術，借鑒文獻[15]提出的慣性權重模糊自適應策略，使用不同的慣性權重更新同一代種群。

2.1 移動子和操作符

本文采用順序編碼，即虛擬機的序列編號作為粒子的編碼規劃，子任務的數量決定編碼長度，一個粒子對應虛擬機上子任務的一個分配序列。假設子任務數N為18，虛擬機個數m為4時，粒子（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）可為一個可行的調度策略。為了更好地將該算法應用于云計算任務調度，本文引入了移動子的概念，并對粒子群算法的速度和位置更新公式中的操作符賦予了新的含義。

定義1（移動子），（j，p，q），j∈{1，2，…，N}，p，q∈{1，2，…，m}，if（p=q），doNothing，表示將p號虛擬機上的子任務j移動到q號虛擬機上。

定義2（減法操作（X1-X2））

設pi，pj為粒子i和j的位置，則pi-pj為粒子i和j的位置減法操作，結果為一組移動序列。A=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4），B=（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4），由于A（4）=4，B（4）=1，第一個移動子為（4，1，4），所以最后得 到 的移動 序 列 為 {（4，1，4），（6，1，3），（14，1，4，），（16，1，3），（17，1，2）}

定義3（加法操作（X+V））

將一組移動序列V作用于某個粒子位置X得到新位置。

例如：（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）+{（4，1，4），（6，1，3），(14，1，4)，（16，1，3），（17，1，2）}=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4）

定義4（乘法操作（r×V））

r為實數，取值范圍為[0，1]，k表示速度V的移動子的個數，r×V表示選取速度V的前r×k（取整）個移動子

例如：0.5×{(4，1，4)，（6，1，3），（14，1，4），（16，1，3）}={（4，1，4），（6，1，3）}

定義5（合并操作（v1⊕v2））

速度v1與v2合并為一個新的速度v。

例 如 ：{（4，1，4），（6，1，3）}⊕{（14，1，4），（16，1，3）}= {（4，1，4），（6，1，3），（14，1，4），（16，1，3）}

根據上述定義，本文使用如下公式更新粒子

速度更新公式：

位置更新公式：

2.2 自適應調整慣性權值

為了很好的平衡粒子的全局搜索能力和局部搜索能力，使其不至于過早收斂和陷入局部極值，借鑒文獻[15]慣性權重的模糊自適應策略，應用到粒子群優化算法中。

隸屬函數：

其中，di表示第i個粒子的佳粒子距，N為種群規模，S1、S2為控制參數，α、β為調整參數，滿足條件S10，β>0。

慣性權重自適應調整函數：

其中，cIter為當前迭代次數，MaxIter為最大迭代數，ws、we分別為w的初始值和結束值。

2.3 適應度函數

本文考慮了任務調度過程中的3個目標，即最短完成時間、負載均衡和經濟成本。用改進的pso來解決多目標優化問題，適應度函數Fitness（i）定義為：

式中，α+β+γ=1，α=0.5，β=0.3，γ=0.2。其中α、β、γ分別表示各目標的權重。

2.4 模糊自適應PSO算法

模糊自適應PSO的云計算任務調度算法的基本執行步驟如下：

圖1 模糊自適應PSO算法流程

3 實驗與分析

3.1 仿真環境及算法設置

建立仿真環境，測試硬件為：Intel（R）Core（TM）i5-2400 3.10GHz，4.00G RAM，采用亞馬遜EC2的處理定價模式和亞馬遜CloudFront的數據傳輸定價模式，實驗采用CloudSim云計算仿真工具對標準PSO算法和M-PSO算法進行仿真實驗，并對實驗結果進行分析和對比。表1為實驗初始時的參數取值。

表1 本文算法主要參數設置

其中，達到最大迭代次數MaxIter或全局最優值連續50次沒有變化為算法的終止條件。

3.2 實驗結果與性能分析

我們依據亞馬遜的收費方式對10個虛擬機進行模擬，用PSO方法和M—PSO方法分別對云計算任務進行調度，仿真結果如圖2，圖3所示。圖2表示30個粒子，分別使用PSO方法和M—PSO方法，經過1000次的迭代后，3個目標約束在三維空間中粒子的分布情況，從圖中可以看出，M—PSO方法在系統負載均衡、最短完成時間和費用方面與PSO方法比較，都表現出了較優的效果，且粒子分布比較集中，更能找到全局最優解。圖3表示PSO方法和M—PSO方法隨著迭代次數的增加適應度值的收斂情況，從圖中可以看到，PSO收斂過早，并且陷入了局部極值，而M—PSO收斂的效果比PSO更好。

圖2 粒子目標約束空間的分布

圖3 適應度值收斂過程

4 結論

文中研究了云計算環境下任務調度模型，定義了最短完成時間、負載均衡和經濟成本3個目標約束的模型，采用標準粒子群算法和改進的粒子群算法對云計算環境下多目標約束的任務調度問題進行優化，仿真結果顯示，3個有互相沖突的目標約束最終達到了一種均衡擇中狀態，并且改進的粒子群算法表現的性能優于標準粒子群算法。本文只考慮了云計算環境下任務調度的3個目標約束和切割后的子任務間相互獨立的情況，而在實際應用中情況比較復雜，還有其他因素需要考慮，比如QoS約束，節能約束等，并且子任務之間并非相互獨立，而是存在密切聯系的，因此下一步研究的目標是在考慮更多的目標約束條件和子任務之間并不是相互獨立的情況下，如何繼續不斷提高云計算任務調度的綜合性能。

[1]李喬，鄭嘯．云計算研究現狀綜述[J]．計算機科學，2011，38（4）：32-37．

[2]許元飛．網格計算中任務調度算法的仿真研究[J]．計算機仿真，2011，28(8)：75-78．

[3]Armbrust M，Fox A，Griffith R，et al.Above the Clouds:A Berkeley view of cloud computing[J].Eecs Department University of California Berkeley，2009，53(4):50-58.

[4]孟令璽，李洪亮．基于CA-PSO算法的云計算資源調度策略[J]．計算機仿真，2013，30(10)：406-410．

[5]劉萬軍，張孟華，郭文越．基于MPSO算法的云計算資源調度策略[J]．計算機工程，2011，37(11)：43-45．

[6]李媛媛，曲雯毓，栗志揚，等．一種快速收斂粒子群優化算法在云計算中應用[J]．華中科技大學學報：自然科學版，2012:34-37．

[7]郭力爭，耿永軍，姜長源，等．云計算環境下基于粒子群算法的多目標優化[J]．計算機工程與設計，2013，34(7)：2358-2362．

[8]Anju Baby.Load balancing in cloud computing environment using pso algorithm[J].International Journal For Research In Applied Science and Engineering Technology，2014，2（4）：156-163.

[9]李榮鈞，常先英．一種新的混合粒子群優化算法[J]．計算機應用研究，2009，26（5）：1700-1702．

[10]吳曉軍，楊戰中，趙明．均勻搜索粒子群算法[J]．電子學報，2011，39（6）：1261-1266．

[11]任小波，楊忠秀．一種動態擴散粒子群算法[J]．計算機應用，2010，30（1）：159-161．

[12]林國漢，章兢，劉朝華．免疫綜合學習粒子群優化算法[J]．計算機應用研究，2014，31（11）：3229-3233．

[13]Yassa S，Chelouah R，et al.Multi-objective approach for energy-aware workflow scheduling in cloud computing environments.[J].Scientific world journal，2013，pp:1-13.

[14]E.Pacini，C.Mateos，et al.Dynamic scheduling based on particle swarm optimization for cloud-based scientific experiments[J].Clei Electronic Journal，2014，14（1）：1-14.

[15]郭文忠，陳國龍．求解TSP問題的模糊自適應粒子群算法[J]．計算機科學，2006，33（6）：161-163．

Task scheduling based on improved particle swarm optimization in cloud computing environment

ZHANG Zhao-sheng，LI Shu-yu
（School of Computer Science，Shaanxi Normal University，Xi’an 710119，China）

For optimizing the task scheduling of cloud computing environment，it processes to consider the shortest completion time，load balancing，system constraints and economic costs of the three objectives，however，there is still have a conflict between these three objectives of constraints，thus we propose a method of using improved Particle swarm optimization（PSO）algorithms to solve the purpose of cloud computing task scheduling for multi-objective optimization problem to consider the three objectives constraints.Improving the global search ability and local search capability by using Fuzzy Adaptive Inertia Weight PSO strategy so that the particles can be well balanced to avoid premature convergence and local extremum，introducing the concept of the moving element and the load factor for the realization of task scheduling algorithm for cloud computing environments.Simulation results show that the algorithm for multi-objective optimization problem has better search capability.

cloud computing；task scheduling；PSO；the shortest completion time；load balancing；economic costs

TN602

A

1674－6236（2016）15-0005-04

2016-01-05 稿件編號：201601020

國家自然科學基金（41271387）

張照勝（1989—），男，湖北黃岡人，碩士。研究方向：云計算。