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

張陶，于炯，楊興耀，廖彬

新疆大學信息科學與工程學院，烏魯木齊 830046

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

張陶，于炯，楊興耀，廖彬

新疆大學信息科學與工程學院，烏魯木齊 830046

1 引言

IBM公司于2007年底宣布了云計算計劃[1-2]后，云計算吸引了眾多人的關注，并迅速成為產業界和學術界研究的熱點。眾多云計算供應商都根據自己企業業務推出相關的云計算戰略，投入巨資部署各自的云計算基礎架構。研究機構也提出各種原型系統[3-4]，并提出了超過20種以上的“云”的定義[5]。當前，云計算服務可分為3個層次：（1）基礎設施即服務（IaaS）。如IBM的“藍云”計算平臺，Amazon的彈性云計算（EC2）服務、存儲服務（S3）和SimpleDB[6]，以及Sun的云基礎設施平臺（IAAS）。（2）平臺即服務（PaaS）。如Google AppEngine[7]、Apache Hadoop、Microsoft Azure等。（3）軟件即服務（SaaS）。如Salesforce公司的客戶關系管理服務。

云計算是網格計算、分布式計算、并行計算、效用計算、網絡存儲、虛擬化等先進計算機技術和網絡技術發展融合的產物，具有普遍適用性。云計算技術的發展，一直與大規模任務調度密切相關。因此，依靠云計算環境如何對大規模任務進行高效調度，是一個非常重要的研究方向。本文提出了一種基于雙適應度粒子群算法（Double Fitness Particle Swarm Optimization，DFPSO）的云計算任務調度算法，并設計了適用于云環境下任務調度問題的編碼、適應度函數、位置速度更新策略。仿真實驗取得了理想的調度結果，表明了本文算法在該問題中具有較好的應用前景。

在云計算環境中，一個大規模的計算任務的處理必須進行分布式并行處理。首先要將一個邏輯上完整的大任務分解成若干個子任務，系統根據任務的信息采用適當的策略把不同的任務分配到不同資源節點上去運行。當所有子任務處理結束，則完成整個大任務的一次處理，最后將處理結果傳給用戶。目前的云計算環境中大部分采用Google提出的MapReduce[8-10]編程模型。如圖1，一個并行處理任務由多個Map任務和多個Reduce任務組成，任務的執行分為Map階段和Reduce階段。在Map階段，每個Map任務對分配給它的數據進行計算，然后按照Map的輸出key值將結果數據映射到對應的Reduce任務中；在Reduce階段，每個Reduce任務對接收到的數據做進一步聚集處理，得到輸出結果。

圖1 MapReduce運行機制

由于云計算可擴展性和動態性的特點，任務量和資源的數量是相當龐大的，系統每時每刻都要處理海量的任務。因此在MapReduce編程模型下，如何對眾多的子任務進行調度是個復雜的問題。不好的任務分配策略勢必會增加任務的執行時間，降低整個云的性能以及用戶的使用滿意度。目前的一些較為典型的任務調度算法多是以總任務完成時間作為調度目標（makespan），沒有太多地考慮任務的平均完成時間，這樣勢必會造成許多潛在的優良粒子的丟失。因為當任務平均完成時間較小時，使找到更小的任務總完成時間成為了可能。因此，本文提出了DFPSO，對云計算中的任務調度策略進行了改進，較大限度地提高了云計算任務調度的效率和用戶滿意度。

本文主要討論當子任務數量遠大于資源數量時的調度策略，如何獲取資源信息、子任務的分解方法不在討論范圍內，不做詳細論述。在同一個資源上執行的子任務遵循FCFS原則。

2 采用雙適應度粒子群算法的任務調度

和遺傳算法（Genetic Algorithm）、蟻群（Ant Colony Algorithm）一樣，作為一種群智能算法[11]的粒子群優化PSO算法[12]，是1995年由美國社會心理學家Kennedy和電氣工程師Eberhart提出來的仿生優化算法，來源于對鳥類和魚類覓食過程的模擬。傳統PSO算法在求解云計算任務調度這個大規模的、實時的問題上有著天然的優勢。參照MapReduce編程模型，為得到任務總完成時間和任務平均完成時間都較短的調度結果，本文在傳統粒子群優化算法基礎上做了一些改進，增加了一個適應度，用兩個適應度來選擇種群，即雙適應度粒子群算法——DFPSO。

2.1 問題編碼

目前粒子的編碼方式可以分為直接編碼（基于問題直接對粒子的位置速度進行編碼，一個粒子對應問題的一個可行解）和間接編碼兩類。本文采用間接編碼方式，對每個子任務占用的資源進行編碼，編碼長度取決于子任務數量，這樣一個粒子實際上對應著一個任務分配策略。

設有Task個任務，Resource個資源，每個任務又分為若干個子任務（SubTask），且任務劃分的子任務總數SubTask大于資源數Resource，即SubTask＞Resource。

式（1）是子任務的總數量，其中TaskNum(t)為第t個任務所含子任務的個數。

式（2）是對子任務的編碼，此時采用順序法，即按任務順序進行編碼。第i個Task中的第j個SubTask的序號是m[i，j]。

當Task=3，Resource=3，SubTask=10時，粒子（3，2，2，1，3，2，3，1，1，2）即為一個可行的調度策略。如表1的粒子編碼所示，其中任務、子任務對（2，5）表示第2個任務中的第3個子任務序號是5；子任務、資源對（1，3）表示把子任務1分配到資源3上執行。

表1 粒子編碼示例

表2 粒子解碼示例

之后是對粒子的解碼，得到資源上的SubTask分布情況。如表2所示，其中資源1上執行的子任務是{4，8，9}，資源2上執行的子任務是{2，3，6，10}，資源3上執行的子任務是{1，5，7}。

本文使用ETC[13]矩陣記錄任務的執行時間，ETC[i，j]表示子任務i在第j個資源上執行的時間。

式（3）是完成所有任務的總時間，其中，Resource(r，i)是第r個資源執行該資源上第i個子任務所用的時間，n為分配到此資源上的子任務個數。

式（4）是第t個任務完成的時間。其中，res(j，i)是子任務i分配的資源上執行該資源第j個子任務所用的時間，k為第t個任務的第i個子任務在被分到的資源中的位置。

式（5）是每個任務平均完成時間。

2.2 粒子群體初始化

2.3 適應度函數

對應每個粒子的分配方案，都有一個用于衡量粒子優劣的適應度。代表任務分配最優解的粒子具有最優的適應度，而適應度函數作為相應的評價函數要能有效地反映出每一個粒子與問題最優解粒子之間的差距。

任務調度較為典型的多是以任務總完成時間作為調度目標，傳統的PSO算法用任務總完成時間來定義適應度函數。為了提高算法的收斂精度，也是找到實際最優解所必需的，DFPSO算法考慮任務總完成時間的同時也考慮到了任務的平均所用時間。即定義兩個適應度函數：

TaskTime(t，i)為在第i個粒子中完成第t個任務所用的時間。

本文采用類似遺傳算法中選擇（Selection）的思想，優選適應度高的粒子。任務總完成時間和任務平均所用時間越短的粒子，適應度值越大，越容易被選擇。通過這樣的選擇，種群中即有總任務完成時間較短的粒子，又有任務平均所用時間較短的粒子，為進化出下一代較優秀的粒子提供了優良的基礎。

2.4 粒子位置與速度的更新

粒子群算法中，只有當粒子的當前位置與所經歷的最好位置相比具有更好的適應值時，其粒子所經歷的最好位置才會唯一地被該粒子當前的位置所替代[14-15]。第i個粒子經歷過的最好位置（有最好適應度）記為pbi=(pbi1，pbi2，…，pbin)，在整個群體中，所有粒子經歷過的最好位置記為gb=(gb1，gb2，…，gbn)。s代表群體的大小。分別用式（6）、（8）得出的兩個適應度計算pb、gb：

每一代粒子根據下面公式更新自己的速度和位置，首先利用粒子自身的最佳飛行位置pb[16]作用于當前位置，然后根據群體最佳位置gb對當前粒子位置進行調整。

其中，t表示迭代次數；ω為慣性權重，使粒子保持運動慣性，防止算法的早熟收斂；c1和c2是學習因子[17]；Rand為[0，1]之間的隨機數。迭代過程中，粒子的速度和位置都限制在特定的范圍內[18-19]，同時pb和gb不斷更新，最后輸出的gb就是全局最優解。

3 仿真實驗與分析

3.1 仿真實驗環境及算法設置

為了評價和分析本文算法的性能，實驗是采用Matlab產生ETC[13]矩陣，首先用CloudSim[20]對傳統PSO算法和具有雙適應度的PSO算法進行了云環境下的仿真實驗，繼而在相同的仿真平臺下對此兩種算法進行橫向對比。實驗測試各運行100次，取100次實驗的平均結果作為作圖的數據。

表3 算法主要參數

通過多次實驗并參考文獻[21-22]的參數調整策略，兩種算法參數按表3設置，可以在較短的時間內取得優質解。

其中，每個任務劃分成的子任務個數范圍為[30，70]，各個子任務的預計完成時間在[1，60]區間上隨機產生，單位為s。算法終止條件為：（1）達到最大迭代次數tmax；（2）連續60次總任務完成時間與任務平均完成時間都沒有變化。

3.2 實驗結果和性能分析

圖2～圖7為云計算環境下，基于傳統PSO的任務調度算法和本文提出的基于DFPSO的任務調度算法在任務總完成時間和任務平均完成時間兩個方面的對比。

圖2和圖3中任務數Task=50，其迭代過程可看出PSO算法和DFPSO算法的前期迭代過程基本一致，得出的任務總完成時間和任務平均完成時間相差不大。隨著粒子迭代更新次數的增大，兩種算法所得到的任務總完成時間和任務平均完成時間都在不斷地減小，且DFPSO算法所得調度結果在任務總時間和任務平均完成時間上要小于傳統PSO算法。

圖2 Task=50時的任務總完成時間

圖3 Task=50時的任務平均完成時間

圖4 Task=100時的任務總完成時間

圖5 Task=100時的任務平均完成時間

圖6 Task=500時的任務總完成時間

圖7 Task=500時的任務平均完成時間

圖8 優化效果總體對比圖

當任務數Task增加到100時，通過比較圖4與圖5，可以看出兩種算法所得到的任務總完成時間和任務平均完成時間的差距拉大。

其中傳統PSO算法收斂速度很快，迭代到40次后，由于任務總完成時間和任務平均完成時間都沒有任何變化，傳統PSO算法收斂于自己的最優調度結果，但所得任務調度結果的任務總完成時間和任務平均完成時間都較大。DFPSO算法所得任務調度結果的任務總完成時間和任務平均完成時間，分別比傳統PSO算法所得調度結果優化了14 s和11 s，從而驗證了在傳統PSO算法中多加入一個適應度的有效性。

計算資源數量Resource不變，任務數Task繼續增加到500，從圖6和圖7可以看出，兩種算法所得調度結果的任務總完成時間和任務平均完成時間的差距隨之達到30 s和28 s。隨著任務數量加大，通過DFPSO算法進行任務調度，得到了任務總完成時間和任務平均完成時間都更小的調度結果，充分地利用了現有云資源，提高了任務調度的效率。

通過圖8可以得出結論，采用DFPSO算法對云中任務進行調度，有效地減少了任務總完成時間和任務平均完成時間，提高了用戶的滿意度。在云中資源不增加的情況下，隨著用戶任務數量不斷的增加，DFPSO算法的綜合調度性能也呈現上升趨勢，進一步驗證了DFPSO算法的有效性。

從以上實驗結果反映出，傳統PSO算法因為只重視總任務的完成時間，造成了一些潛在優良的粒子丟失。雖然提高了自己的收斂速度，但該算法在運行過程中由于無法有效跳出局部最優的搜索狀態而過早地收斂到局部最優的任務調度結果上，得到的任務調度結果不論是任務總完成時間還是任務平均完成時間都較大。本文在傳統的PSO算法的基礎上增加一個適應度，最終形成了DFPSO算法。該算法由于同時考慮任務總完成時間和任務平均完成時間，需對每個任務進行計算，盡管在收斂速度上比PSO算法有所下降，但該算法的調度結果不但任務總完成時間短，任務的平均所用時間也短。因此，對于DFPSO算法和傳統PSO算法的比較，從以一定收斂速度的損失來換取能夠得到明顯更優的調度結果的能力方面來說，DFPSO算法優于傳統PSO算法。通過DFPSO算法進行任務調度可以找到明顯更小的任務總完成時間，是一種云計算環境下的有效任務調度算法。

4 總結

在粒子群優化算法的基礎上，針對云計算的編程模型，提出了一種具有雙適應度的粒子群（DFPSO）算法的任務調度算法。本文算法在進行任務調度時不僅考慮總任務完成時間，同時也考慮到了任務的平均完成時間。仿真實驗結果表明，本文算法對云計算環境下這種編程模式可以實現較為理想的任務調度結果。下一步工作，是如何在保證任務調度效率的同時提高此算法的收斂速度。

[1]Sims K.IBM introduces ready-to-use cloud computing collaboration services get clients started with cloud computing[EB/OL].（2007）[2011-12].http：//www.ibm.com/press/us/en/pressrelease/ 22613.wss.

[2]Boss G，Malladi P，Quan D，et al.Cloud computing.IBM White Paper[EB/OL].（2007）[2011-12].http：//download.boulder.ibm.com/ ibmdl/pub/software/dw/wes/hipods/Cloud_computing_wp_final_ 8Oct.pdf.

[3]Rochwerger B，Breitgand D，Levy E，et al.The reservoir model and architecture for open federated cloud computing[J].IBM Journal of Research and Development，2009，53（4）：1-17.

[4]Nurmi D，Wolski R，Grzegorczyk C，et al.The eucalyptus opensource cloud-computing system[C]//Proceeding of the Crid，2009：124-131.

[5]Armbrust M，Fox A，Griffith R，et al.Above the clouds：a berkeley view of cloud computing，Technical Report No.UCB/EECS-2009-28[R].USA：UC Berkley，2009：1-25.

[6]Amazon SimpleDB[EB/OL].（2011-08-10）[2011-12].http：//aws. smazon.com/simpledb/.

[7]Barroso L A，Dean J，Holzle U.Web search for a planet：The Google cluster architecture[J].IEEE Micro，2003，23（2）：22-28.

[8]Jeffrey D，Sanjay G.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[9]Dean J，Ghemawat S.Distributed programming with MapReduce[M]//Oram A，Wilson G.Beautiful Code.Sebastopol：O’Reilly Media，Inc，2007：371-384.

[10]Jeffrey D，Sanjay G.MapReduce：simplifed data processing on large clusters[C]//Proceedings of the Conference on Operating System Design and Implementation（OSDI），San Francisco，USA，2004：137-150.

[11]Eberhart R C，Kennedy J.A new optimizer using particles swarm theory[C]//Proc of the 6th Int’1 Symp on Micro Machine and Human Science.Nagoya：IEEE Inc，1995：39-43.

[12]Bratton D，Kennedy J.Defining a standard for particle swarm optimization[C]//ProceedingsoftheIEEESwarmIntelligence Symposium，Honolulu，HI，2007：120-127.

[13]Ali S，Siegel H J，Maheswaran M，et al.Representing task and machine heterogeneities for heterogeneous computing systems[J].Journal of Science and Engineering，2000，3（3）：195-207.

[14]Clerc M，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space[J].IEEE Trans on Evolutionary Computation，2002，6（1）：58-73.

[15]Li N，Sun D B，Zou T，et al.An analysis for a particle’s trajectory of PSO based on difference equation[J].Chinese Journal of Computers，2006，29（11）：2052-2061.

[16]Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Trans on Evolutionary Computation，2004，8（3）：240-255.

[17]Parsopoulos K E，Vrahatis M N.Recent approaches to global optimization problems through particle swarm optimization[J]. Natural Computing，2002，1（2/3）：235-306.

[18]Eberhart R，Shi Y.Particle swarm optimization：developments，applications，and resource[C]//Proceedings of the IEEE International Conference on Evolutionary Computation，Piscataway，NJ，2001：81-86.

[19]Said M，Ahamed A.Hybrid periodic boundary condition for particle swarm optimization[J].IEEE Transactions on Antennas and Propagation，2007，55（11）：3251-3256.

[20]Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2010，41（1）：23-50.

[21]Chen G L，Guo W Z，Chen Y Z.A PSO-based intelligent decision algorithm for VLSI floor planning[J].Soft Computing，2010，14（12）：1329-1337.

[22]李曉東，張慶紅，葉瑾琳.基于仿真的優化的粒子群算法參數選取研究[J].計算機工程與應用，2011，47（33）：30-35.

ZHANG Tao,YU Jiong,YANG Xingyao,LIAO Bin

School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

How to schedule tasks efficiently is one of the key issues to be resolved in cloud computing environment.A Double Fitness Particle Swarm Optimization algorithm（DFPSO）based on conventional Particle Swarm Optimization（PSO）is brought up for the programming framework of cloud computing.Through this algorithm,the better task scheduling not only shortens total task completion time and also has shorter average task completion time.Simulation results show that DFPSO is better than PSO, and the integrated scheduling performance is excellent,especially when the number of tasks increases.

task scheduling;cloud computing;Particle Swarm Optimization（PSO）algorithm;double-fitness

如何對任務進行高效合理的調度是云計算需要解決的關鍵問題之一，針對云計算的編程模型框架，在傳統粒子群優化算法（PSO）的基礎上，提出了一種具有雙適應度的粒子群算法（DFPSO）。通過該算法不但能找到任務總完成時間較短的調度結果，而且此調度結果的任務平均完成時間也較短。仿真分析結果表明，在相同的條件設置下，該算法優于傳統的粒子群優化算法，當任務數量增多時，其綜合調度性能優點明顯。

任務調度；云計算；粒子群算法；雙適應度

A

TP311

10.3778/j.issn.1002-8331.1201-0022

ZHANG Tao,YU Jiong,YANG Xingyao,et al.Improved Particle Swarm Optimization algorithm for cloud computing task scheduling.Computer Engineering and Applications,2013,49（19）：68-72.

國家自然科學基金（No.60863003，No.61063042）；新疆大學博士科研啟動基金（No.BS090153）。

張陶（1988—），女，碩士研究生，主要研究領域為云計算，網格與分布式計算；于炯（1964—），男，教授，博士，主要研究領域為網絡安全，網格與分布式計算；楊興耀（1984—），男，博士研究生，主要研究領域為數據庫，網格與分布式計算；廖彬（1986—），男，博士研究生，主要研究領域為網格與分布式計算。E-mail：zt59921661@126.com

2012-01-09

2012-03-21

1002-8331（2013）19-0068-05