云環(huán)境下基于DPSO的任務(wù)調(diào)度算法

鄔開俊，魯懷偉

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

1 概述

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

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

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

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

2 云環(huán)境任務(wù)調(diào)度模型

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

圖1 MapReduce執(zhí)行過程

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

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

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

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

3 標準PSO簡介

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

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

4 基于DPSO的云環(huán)境任務(wù)調(diào)度算法

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

4.1 粒子編碼

采用資源-任務(wù)間接編碼方式：子任務(wù)順序編碼法[15]，編碼長度為子任務(wù)個數(shù)，編碼每一位的值為占用的資源編號。假設(shè)有 5個子任務(wù)(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上運行。解碼結(jié)果即為：R1運行T4；R2運行T2,T5；R3運行T1,T3。

4.2 適應(yīng)度定義

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

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

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

4.3 種群初始化

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

4.4 慣性權(quán)重的調(diào)整

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

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

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

4.6 DPSO算法流程

DPSO算法具體步驟如下：

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

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

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

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

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

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

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

5 仿真實驗與結(jié)果分析

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

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

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

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

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

6 結(jié)束語

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

[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].計算機應(yīng)用研究, 2010, 27(2): 429-433.

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

[4]鄧自立.云計算中的網(wǎng)絡(luò)拓撲設(shè)計和Hadoop平臺研究[D].合肥: 中國科學(xué)技術(shù)大學(xué), 2009.

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

[6]陳艷金.MapReduce模型在Hadoop平臺下實現(xiàn)作業(yè)調(diào)度算法的研究和改進[D].廣州: 華南理工大學(xué), 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].計算機應(yīng)用, 2011, 31(1): 1-7.

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

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

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

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

[15]李建鋒, 彭 艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用, 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.