鄔開(kāi)俊，魯懷偉

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

1 概述

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

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

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

本文通過(guò)對(duì)云環(huán)境編程模型及任務(wù)調(diào)度問(wèn)題的分析，并結(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)有的大部分云計(jì)算平臺(tái)均采用 Google提出的MapReduce編程模型，它是一種分布式計(jì)算模型，用于大規(guī)模數(shù)據(jù)集的并行計(jì)算[11]。MapReduce作業(yè)就是一系列Map和Reduce函數(shù)，它們被提交給調(diào)度系統(tǒng)，并被調(diào)度到可用的計(jì)算資源上，其執(zhí)行過(guò)程如圖1所示。

圖1 MapReduce執(zhí)行過(guò)程

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

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

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

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

3 標(biāo)準(zhǔn)PSO簡(jiǎn)介

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

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

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

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

4.1 粒子編碼

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

4.2 適應(yīng)度定義

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

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

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

4.3 種群初始化

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

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

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

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

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

4.6 DPSO算法流程

DPSO算法具體步驟如下：

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

根據(jù)文獻(xiàn)[14]的參數(shù)調(diào)整原則和多次實(shí)驗(yàn)情況，確定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é)果如下：在進(jìn)行 200次迭代后，所有任務(wù)的最終調(diào)度時(shí)間：GA為472.41 s，PSO為467.90 s，DPSO為457.69 s。具體進(jìn)化過(guò)程對(duì)比結(jié)果如圖2所示。從中可以看出，DPSO算法的迭代過(guò)程體現(xiàn)了均衡的探索能力和開(kāi)發(fā)能力，在進(jìn)化過(guò)程中不斷優(yōu)化調(diào)度結(jié)果，最終得到 3種對(duì)比算法中的最優(yōu)調(diào)度結(jié)果457.69 s。比較而言，標(biāo)準(zhǔn)PSO在進(jìn)化過(guò)程的后期，探索能力不足，在進(jìn)化前期迅速地探索到局部最優(yōu)解467.90 s后就沒(méi)能再跳出。然而，GA雖然在整個(gè)進(jìn)化過(guò)程中優(yōu)化能力比較均衡，但是性能較差，直到200次迭代結(jié)束，才優(yōu)化到472.41 s，是3種比較算法中最差的調(diào)度結(jié)果。因此，無(wú)論是進(jìn)化的收斂速度還是進(jìn)化的最終結(jié)果，本文提出的DPSO算法都優(yōu)于PSO和GA算法。

圖2 所有任務(wù)完成時(shí)間的進(jìn)化過(guò)程對(duì)比

6 結(jié)束語(yǔ)

針對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題，本文提出一種基于離散粒子群優(yōu)化的任務(wù)調(diào)度算法。在該算法中，采用隨機(jī)方法初始化種群，利用時(shí)變方式調(diào)整慣性權(quán)重，并在位置更新中通過(guò)絕對(duì)值取整求余映射法進(jìn)行合法化修復(fù)。適應(yīng)度函數(shù)定義為各計(jì)算資源任務(wù)完成時(shí)間的最大值的倒數(shù)。通過(guò)對(duì)比實(shí)驗(yàn)可驗(yàn)證，本文提出的 DPSO算法能夠有效地解決云計(jì)算環(huán)境下任務(wù)調(diào)度問(wèn)題，并且算法收斂速度優(yōu)于 GA和標(biāo)準(zhǔn)PSO算法，能夠在較小的進(jìn)化代數(shù)下取得良好的調(diào)度效果，為求解云環(huán)境下的任務(wù)調(diào)度問(wè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ì)算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究, 2010, 27(2): 429-433.

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

[4]鄧自立.云計(jì)算中的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)和Hadoop平臺(tái)研究[D].合肥: 中國(guó)科學(xué)技術(shù)大學(xué), 2009.

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

[6]陳艷金.MapReduce模型在Hadoop平臺(tái)下實(shí)現(xiàn)作業(yè)調(diào)度算法的研究和改進(jìn)[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ì)算需求彈性算法[J].計(jì)算機(jī)應(yīng)用, 2011, 31(1): 1-7.

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

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

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

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

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