云環(huán)境下基于DPSO的任務調度算法

鄔開俊，魯懷偉

(蘭州交通大學 a.電子與信息工程學院；b.數(shù)理與軟件工程學院，蘭州 730070)

1 概述

網絡帶寬的不斷增長使得通過網絡訪問非本地的計算服務變成可能，助推了云計算技術的出現(xiàn)。它是將計算任務分布在大量計算機構成的資源池上，使用戶能夠按需獲取計算能力、存儲能力和信息服務[1-2]。云計算透過網絡將龐大的計算處理程序自動拆分成多個較小子任務，然后按照適當?shù)乃惴ǚ峙涞教摂M計算資源上處理，再將分析、整合處理結果回傳給用戶。其面向的用戶類型多樣、計算任務數(shù)量巨大，并且各分布式的虛擬計算資源的處理能力各不相同，因此，如何將眾多任務進行調度，滿足用戶對服務質量的要求且資源利用率較高變得十分困難。

目前云計算平臺實際使用的調度算法有：單隊列調度，簡單但資源利用率低；公平調度，支持作業(yè)分類調度，但不考慮節(jié)點的實際負載狀態(tài)，導致節(jié)點負載實際不均衡；容量調度，支持多作業(yè)并行執(zhí)行，但隊列設置和隊列選擇無法自動進行[3]。

為了解決現(xiàn)有調度算法的不足，一些新的調度算法被提出：文獻[4]提出了基于優(yōu)先級的加權輪轉調度算法(PBWRR)，文獻[5]提出了優(yōu)先級加權的滑動窗口算法(PWSW)，文獻[6]提出了基于優(yōu)先權的自適應作業(yè)調度算法。文獻[7]提出了一種云計算環(huán)境下科學任務流的調度方法。此外，智能優(yōu)化方法也逐漸被引入。文獻[8]提出了一種基于遺傳算法(Genetic Algorithm, GA)的云計算環(huán)境下任務調度算法。文獻[9]提出了一種基于GA的滿足QoS需求的云計算任務調度方法。文獻[10]提出了基于蟻群算法的云計算任務調度算法。但目前這方面的研究剛起步并不完善，因此，在該領域做一些有益的探索具有現(xiàn)實意義。

本文通過對云環(huán)境編程模型及任務調度問題的分析，并結合粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法，提出一種基于離散粒子群優(yōu)化(Discrete Particle Swarm Optimization, DPSO)的任務調度算法。

2 云環(huán)境任務調度模型

現(xiàn)有的大部分云計算平臺均采用 Google提出的MapReduce編程模型，它是一種分布式計算模型，用于大規(guī)模數(shù)據集的并行計算[11]。MapReduce作業(yè)就是一系列Map和Reduce函數(shù)，它們被提交給調度系統(tǒng)，并被調度到可用的計算資源上，其執(zhí)行過程如圖1所示。

圖1 MapReduce執(zhí)行過程

Map操作將較大的任務分割成多個小的子任務，然后將這些子任務指派到若干計算資源上執(zhí)行。之后，通過Reduce操作，得到最終結果。

云計算的資源有處理器、存儲器、網絡等，是按需使用、按使用量付費的。本文將這些資源統(tǒng)一視為計算資源，并假設：子任務所需運算量已知，計算資源的運算能力(速度)已知，子任務在每個計算資源上運行完成所需的時間已知，即：子任務的運算量與計算資源運算能力的比值。

假設子任務數(shù)記為M，計算資源數(shù)記為N，用M×N的矩陣ETC(Expect Time to Complete)來表示各計算資源上任務運行完成所需的時間，其中，ETC(i, j)表示第i個子任務在第j個計算資源上運行完成所需的時間。

在以上假設前提下，云計算任務調度問題可以簡化為：如何將多個任務合理分配到各計算資源，使得所有任務的總完成時間最短。

3 標準PSO簡介

粒子群算法是由美國心理學家Kennedy和電氣工程師Eberhart于1995年提出的一種模擬鳥類群體覓食行為的仿生智能優(yōu)化方法，它是一種基于群體智能的隨機尋優(yōu)算法，該算法利用鳥類群體個體對信息的共享機制，使整個群體的運動在問題的解空間中產生從無序到有序的演化過程，從而獲得最優(yōu)解[12-13]。

其中，ω稱為慣性權重，其大小決定了對粒子當前速度繼承的多少，用于平衡PSO的探索能力和開發(fā)能力，較大的ω使粒子在原來方向飛的更遠，具有更好的探索能力，但收斂較慢，較小的ω使粒子擁有更好的開發(fā)能力，但可能導致陷入局優(yōu)；c1和c2是學習因子，分別表示粒子向自己歷史最優(yōu)點和群體最優(yōu)點靠近的程度；1r和r2是在[0,1]區(qū)間內均勻分布的隨機數(shù)；為了減少迭代過程中微粒離開搜索空間的可能性，vij通常限定在一定范圍內，即vij∈[- vmax,vmax]，如果問題的搜索空間限定在 [- xmax,xmax]內，則可設定 vmax=k· xmax,0.1 ≤ k≤1。

4 基于DPSO的云環(huán)境任務調度算法

目前，關于粒子群算法的離散方面的研究還很有限，并沒有一個很好的解決方案，離散變量進行加法和乘法時，需要專門的變通定義或者合法化處理[14]。因此，粒子群算法應用于離散的云環(huán)境任務調度時需要進行必要改進。

4.1 粒子編碼

采用資源-任務間接編碼方式：子任務順序編碼法[15]，編碼長度為子任務個數(shù)，編碼每一位的值為占用的資源編號。假設有 5個子任務(T1,T2,T3,T4,T5)，3個可用資源(R1,R2,R3)，個體編碼長度則為 5，每一位都在集合{1,2,3}中取值。如個體編碼[3,2,3,1,2]，其第1位編碼是3表示T1在R3上運行，第2位是2表示T2在R2上運行，依此類推，第5位是2表示T5在R2上運行。解碼結果即為：R1運行T4；R2運行T2,T5；R3運行T1,T3。

4.2 適應度定義

根據ETC矩陣和解碼結果，可計算出各計算資源運行對應任務的完成時間。設分配到計算資源j上的子任務集合為Mj，則計算資源j的任務完成時間為EachRTime(j)為：

所有任務完成的時間AllRTime為各個計算資源任務完成時間的最大值：

適應度函數(shù)定義為：

4.3 種群初始化

設種群規(guī)模為NP，子任務數(shù)為M，資源數(shù)為N，則隨機初始化描述為：粒子初始位置為由系統(tǒng)隨機產生NP個長度為 M 的個體，每個個體的每一位隨機從集合{1,2,…,N}中取值。設 k=0.5、 vmax= 0.5N，則粒子初始速度為系統(tǒng)隨機產生 NP個長度為 M 的向量，向量中每一位值vij∈[-0.5 N ,0.5 N]。

4.4 慣性權重的調整

為了讓粒子在迭代初期具有較好的探索能力，在后期具有較好的開發(fā)能力，則需要隨著迭代動態(tài)調整 ω。本文采用線性減小的變化方式：設最大迭代次數(shù)為 Imax，ω∈[ωmin,ωmax]，則第i次迭代時的慣性權重ωi為：

4.5 速度與位置更新及合法化處理

速度的更新按式(1)進行。位置的更新方法如下：首先，按式(2)的定義進行運算，得到含非法編碼的一個新的編碼序列。然后，對上面得到的新的非法編碼進行合法化處理。本文定義的處理方法主要包含取絕對值、向上取整、求余等運算，記為：絕對值取整求余映射法，具體方法如下：

4.6 DPSO算法流程

DPSO算法具體步驟如下：

Step1 初始化參數(shù)：設置最大迭代次數(shù)Imax，種群規(guī)模NP，慣性權重取值范圍 [ωmin,ωmax]，學習因子c1、c2等參數(shù)。

Step2 隨機初始化種群：對粒子群的隨機位置和速度進行初始設定。

Step3 按式(5)計算所有粒子的適應度值。

Step4 對每個粒子xi，將其適應度值與所經歷過的最好位置pi的適應度值進行比較，若較好，則將xi記錄為該粒子經歷過的最好位置pi。

Step5 對每個粒子xi，將其適應度值與全局最好位置pg的適應度值進行比較，若較好，則將xi作為當前的全局最好位置pg。

Step6 對每個粒子，按式(1)更新速度，按式(2)和式(7)更新位置。

Step7 若迭代次數(shù)大于最大迭代次數(shù)，則結束并輸出結果，否則跳轉到Step3繼續(xù)下一次迭代。

5 仿真實驗與結果分析

為評價和分析本文 DPSO算法的性能，在云計算模擬平臺CloudSim-3.0.2中[16]，通過改寫DatacenterBroker類中的bindCloudletToVm方法，添加基于DPSO的調度算法，并且使用 Ant工具對平臺進行重編譯，從而將基于 DPSO的任務調度算法加入到模擬平臺的任務單元調度中，進行模擬實驗。同理，進行PSO和GA算法的環(huán)境配置。

設置計算資源節(jié)點數(shù)為10，待調度的子任務數(shù)為300，計算資源的計算能力和子任務的計算量使用Matlab隨機產生。在此實驗數(shù)據條件下，將DPSO與PSO、GA進行對比。

根據文獻[14]的參數(shù)調整原則和多次實驗情況，確定DPSO的參數(shù)設置如下：最大迭代次數(shù)Imax=200，種群規(guī)模NP=300，慣性權重的取值范圍 [ωmin,ωmax]=[0.4,0.9]，學習因子c1=c2= 2。

調度結果如下：在進行 200次迭代后，所有任務的最終調度時間：GA為472.41 s，PSO為467.90 s，DPSO為457.69 s。具體進化過程對比結果如圖2所示。從中可以看出，DPSO算法的迭代過程體現(xiàn)了均衡的探索能力和開發(fā)能力，在進化過程中不斷優(yōu)化調度結果，最終得到 3種對比算法中的最優(yōu)調度結果457.69 s。比較而言，標準PSO在進化過程的后期，探索能力不足，在進化前期迅速地探索到局部最優(yōu)解467.90 s后就沒能再跳出。然而，GA雖然在整個進化過程中優(yōu)化能力比較均衡，但是性能較差，直到200次迭代結束，才優(yōu)化到472.41 s，是3種比較算法中最差的調度結果。因此，無論是進化的收斂速度還是進化的最終結果，本文提出的DPSO算法都優(yōu)于PSO和GA算法。

圖2 所有任務完成時間的進化過程對比

6 結束語

針對云計算任務調度問題，本文提出一種基于離散粒子群優(yōu)化的任務調度算法。在該算法中，采用隨機方法初始化種群，利用時變方式調整慣性權重，并在位置更新中通過絕對值取整求余映射法進行合法化修復。適應度函數(shù)定義為各計算資源任務完成時間的最大值的倒數(shù)。通過對比實驗可驗證，本文提出的 DPSO算法能夠有效地解決云計算環(huán)境下任務調度問題，并且算法收斂速度優(yōu)于 GA和標準PSO算法，能夠在較小的進化代數(shù)下取得良好的調度效果，為求解云環(huán)境下的任務調度問題提供了一種新思路。

[1]Armbrust M, Fox A, Griffith R, et al.Above the Clouds: A Berkeley View of Cloud Computing[EB/OL].[2009-02-10].http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html.

[2]張建勛, 古志民, 鄭 超.云計算研究進展綜述[J].計算機應用研究, 2010, 27(2): 429-433.

[3]劉 鵬.云計算[M].2版.北京: 電子工業(yè)出版社, 2011.

[4]鄧自立.云計算中的網絡拓撲設計和Hadoop平臺研究[D].合肥: 中國科學技術大學, 2009.

[5]張密密.MapReduce模型在Hadoop實現(xiàn)中的性能分析及改進優(yōu)化[D].成都: 電子科技大學, 2010.

[6]陳艷金.MapReduce模型在Hadoop平臺下實現(xiàn)作業(yè)調度算法的研究和改進[D].廣州: 華南理工大學, 2011.

[7]Lin Cui.Scheduling Scientific Workflows Elastically for Cloud Computing[C]//Proc.of International Conference on Cloud Computing.Washington D.C., USA: IEEE Press, 2011:746-747.

[8]Ge Yujia, Wei Guiyi.GA-based Task Scheduler for the Cloud Computing Systems[C]//Proc. of 2010 International Conference on Web Information Systems and Mining.Sanya,China: [s.n.], 2010: 181-186.

[9]Dutta D, Joshi R C.A Genetic: Algorithm Approach to Costbased Multi-QoS Job Scheduling in Cloud Computing Environment[C]//Proc.of International Conference and Workshop on Emerging Trends in Technology.Mumbai, India:ACM Press, 2011: 422-427.

[10]范 杰, 彭 艦, 黎紅友.基于蟻群算法的云計算需求彈性算法[J].計算機應用, 2011, 31(1): 1-7.

[11]雷葆華, 饒少陽, 江 峰, 等.云計算解碼: 技術架構和產業(yè)運營[M].北京: 電子工業(yè)出版社, 2011: 132-135.

[12]汪定偉, 王俊偉, 王洪峰, 等.智能優(yōu)化方法[M].北京:高等教育出版社, 2007: 217-223.

[13]張維存.蟻群粒子群混合優(yōu)化算法及應用[D].天津: 天津大學, 2007.

[14]段海濱, 張祥銀, 徐春芳.仿生智能計算[M].北京: 科學出版社, 2011: 63-85.

[15]李建鋒, 彭 艦.云計算環(huán)境下基于改進遺傳算法的任務調度算法[J].計算機應用, 2011, 31(1): 184-186.

[16]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, 2011, 41(1):23-50.