查安民，譚文安,2

(1.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016；2.上海第二工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，上海 201209)

融合粒子群與蟻群的云計算任務(wù)調(diào)度算法

查安民1，譚文安1,2

(1.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016；2.上海第二工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，上海 201209)

在云計算環(huán)境中用戶數(shù)量眾多，用戶提交的任務(wù)總量非常龐大，如何調(diào)度這些海量任務(wù)使其高效合理地完成成為云計算研究的關(guān)鍵。針對云計算環(huán)境的特點，對粒子群和蟻群算法進(jìn)行改進(jìn)，提出一種融合二者的任務(wù)調(diào)度算法。該算法采用粒子群算法進(jìn)行前期迭代，迭代完成后選取一定數(shù)量的優(yōu)良粒子生成蟻群算法的初始信息素，蟻群算法利用已生成的初始信息素進(jìn)行后期迭代，并求得最終的任務(wù)調(diào)度結(jié)果。仿真結(jié)果表明，該算法優(yōu)于粒子群算法和蟻群算法，任務(wù)的總完成時間明顯減少，是一種高效的調(diào)度算法。

云計算；任務(wù)調(diào)度；粒子群優(yōu)化；蟻群優(yōu)化

0 引 言

自從云計算概念提出之后，云計算技術(shù)就獲得了飛速發(fā)展。IBM、Google、Amazon等大公司紛紛投入巨資打造自己的云計算產(chǎn)品。云計算作為一種技術(shù)和商業(yè)模式，實現(xiàn)了對共享、可配置計算資源的方便、按需訪問。云計算可為用戶提供3類服務(wù)：

(1)基礎(chǔ)設(shè)置即服務(wù)(Infrastructure as a Service,IaaS)，如IBM Blue Cloud、Amazon S3。

(2)平臺即服務(wù)(Platform as a Service,PaaS)，如Google App Engine、Apache Hadoop。

(3)軟件即服務(wù)(Software as a Service,SaaS)，如Google Apps、Salesforce CRM。

云計算技術(shù)的發(fā)展總是伴隨著大規(guī)模任務(wù)調(diào)度的研究。因此，如何對云計算環(huán)境中的大規(guī)模任務(wù)進(jìn)行高效調(diào)度，成為了一個亟待解決且具有挑戰(zhàn)性的問題。

云計算環(huán)境中的任務(wù)調(diào)度是一個難點[1]。傳統(tǒng)調(diào)度算法，如先進(jìn)先出、短作業(yè)優(yōu)先等，存在諸多問題[2]。智能優(yōu)化算法成為求解此類問題的新工具。文獻(xiàn)[3]運用遺傳算法調(diào)度云計算任務(wù)，取得了較好的實驗效果。文獻(xiàn)[4]分析并改進(jìn)粒子群算法，在一定程度上減少了任務(wù)完成時間。文獻(xiàn)[5]也以減少任務(wù)完成時間為目的，對蟻群算法進(jìn)行改進(jìn)，同樣取得了較好的實驗效果。智能優(yōu)化算法有其優(yōu)點，但是也有不足之處。如何取長補(bǔ)短，將兩種或多種智能算法進(jìn)行融合，成為研究智能算法的一個重要方面。一些專家和學(xué)者不但給出智能算法融合的實際應(yīng)用，而且給出了它們?nèi)诤系睦碚摶A(chǔ)，這些都成為運用智能算法調(diào)度云任務(wù)的堅實基礎(chǔ)。

眾所周知，粒子群算法具有前期收斂速度快但后期收斂精度低的特點，而蟻群算法具有全局尋優(yōu)能力強(qiáng)但需要花費較長迭代時間的特點。基于此，文中提出一種融合二者優(yōu)點的任務(wù)調(diào)度算法，大大減少了任務(wù)的完成時間。

1 云計算任務(wù)調(diào)度的描述

云計算任務(wù)的執(zhí)行是建立在“分解”與“調(diào)度”基礎(chǔ)上的[6]。即將一個較大的任務(wù)分解為若干較小的子任務(wù)，然后為這些子任務(wù)分配一定數(shù)量的資源節(jié)點使其并行執(zhí)行，最后將運行結(jié)果返回給用戶[7]。假設(shè)任務(wù)之間相互獨立運行。任務(wù)調(diào)度所要追求的就是對各個任務(wù)合理分配資源，使得總的任務(wù)完成時間最小。

1.1 粒子編碼

為了運用粒子群和蟻群算法，首先需要對粒子進(jìn)行編碼。為簡單起見，可選擇直接法。

設(shè)有a個任務(wù)，r個資源，并且a>r。當(dāng)a=10，r=3時，編碼序列(3,2,2,1,3,2,3,1,1,2)即為一個粒子。其中，每個任務(wù)對應(yīng)一個資源。例如，任務(wù)3對應(yīng)資源1。

接著對粒子進(jìn)行解碼，獲取每個資源運行的所有任務(wù)。例如，資源1上運行的所有任務(wù)為{4,8,9}。

使用矩陣ETCij保存任務(wù)i在資源j上的期望執(zhí)行時間：

使用矩陣RTCij保存任務(wù)i在資源j上的實際執(zhí)行時間：

(1)

taskTime=max(resourceTime(j)) (j=1,2,…,r)

(2)

式(1)表示資源j上完成所有任務(wù)的總時間。其中，i表示資源j上執(zhí)行的第i個任務(wù)；a表示資源j上執(zhí)行的任務(wù)總數(shù)。

式(2)表示所有任務(wù)完成后的總時間。

1.2 適應(yīng)度函數(shù)

每個粒子都有一個用于衡量其優(yōu)劣的適應(yīng)度。適應(yīng)度函數(shù)的選取并不是固定不變的，需要根據(jù)待求問題、優(yōu)化目標(biāo)、計算成本等要求合理選擇。一般來說，適應(yīng)度函數(shù)應(yīng)盡量滿足單調(diào)、非負(fù)、最大化等特點。

文中需要優(yōu)化任務(wù)總的完成時間，因此將適應(yīng)度函數(shù)定義為：

(3)

式中，i表示第i個粒子；s表示種群規(guī)模。

2 云計算任務(wù)調(diào)度的設(shè)計

粒子群算法[8]的基本思想是，每個粒子在尋找最優(yōu)解過程中會充分考慮兩個極值。第一個是粒子自身所能找到的位置極值，也叫個體最優(yōu)解；第二個則是整個種群所能找到的位置極值，也叫全局最優(yōu)解。即每個粒子在一定范圍的尋優(yōu)過程中，不但考慮了自身的局部認(rèn)知，而且考慮了社會的全局認(rèn)知。

蟻群算法[9]的基本思想是，讓每只螞蟻在一定范圍內(nèi)獨立尋找最優(yōu)解，當(dāng)螞蟻遇到一個帶有多條路徑的路口時，如果以前從來沒有其他螞蟻走過，就任意選擇一條作為當(dāng)前路徑繼續(xù)進(jìn)行搜索，并且釋放一定數(shù)量的信息素。隨著迭代次數(shù)的增多，代表最優(yōu)解的路徑上信息素會越來越多，其他路徑上則會越來越少，最終蟻群算法趨向于穩(wěn)定。

粒子群算法的最大特點是前期收斂速度快但后期收斂精度低；而蟻群算法的最大特點是全局尋優(yōu)能力強(qiáng)但系統(tǒng)開銷大?；趦煞N算法的特點，文中提出一種融合二者優(yōu)點的任務(wù)調(diào)度算法(PSACO2)。該算法的基本思想是，將迭代過程分為兩個部分，前期使用粒子群算法，后期使用蟻群算法。這樣既可實現(xiàn)云計算任務(wù)調(diào)度的快速收斂，又可提高云計算任務(wù)調(diào)度對資源的尋優(yōu)能力。

2.1 粒子群算法

2.1.1 粒子群初始化

設(shè)種群規(guī)模為s，任務(wù)總數(shù)為a，資源總數(shù)為r，則初始化描述為：系統(tǒng)隨機(jī)產(chǎn)生s個粒子，向量xi表示粒子i的位置，定義xi={xi1,xi2,…,xin}(1≤n≤a,1≤i≤s)。其中，xij表示任務(wù)i分配到資源j上執(zhí)行(1≤xij≤r)。向量vi表示粒子i的速度，定義vi={vi1,vi2,…,vin}(1≤n≤a,1≤i≤s)。其中-r≤vij≤r。粒子初始位置為[1,r]之間的隨機(jī)整數(shù)，粒子速度隨機(jī)取[-r,r]內(nèi)的整數(shù)。

2.1.2 粒子位置與速度更新

根據(jù)式(4)、(5)更新粒子的位置和速度。

vid(t+1)=ωvid(t)+c1r1(pid(t)-xid(t))+c2r2(pgd(t)-xid(t))

(4)

xid(t+1)=xid(t)+vid(t+1)

(5)

其中，ω為慣性權(quán)重；c1和c2為加速系數(shù)；r1和r2為隨機(jī)因子。

為了提高PSO算法的智能性，提出了很多關(guān)于慣性權(quán)重ω的改進(jìn)方法。例如，文獻(xiàn)[10-13]分別提出了線性遞減權(quán)重、線性微分遞減權(quán)重、帶閾值的非線性遞減權(quán)重、帶控制因子的非線性遞減權(quán)重等思想。此處將ω定義為[14]：

ω(t)=ωmin+(ωmax-ωmin)·exp(-k(t/tmax)2)

(6)

其中，k為控制因子；ωmin與ωmax分別為最小與最大慣性權(quán)重；t為迭代次數(shù)；tmax為最大迭代次數(shù)。

針對學(xué)習(xí)因子c1、c2的改進(jìn)主要集中在兩個方面：一個是線性調(diào)整策略，另一個是非線性調(diào)整策略。此處將c1、c2分別定義為[15]：

c1=c1s+(c1e-c1s)×(t/tmax)

(7)

c2=c2s+(c2e-c2s)×(t/tmax)

(8)

其中，c1s為c1的初始迭代值；c1e為c1的最終迭代值；c2s為c2的初始迭代值；c2e為c2的最終迭代值。

為了進(jìn)一步提高初始信息素的生成質(zhì)量和后期蟻群算法的收斂速度，可對前期粒子群算法進(jìn)行部分雜交優(yōu)化[16]。具體做法是，根據(jù)適應(yīng)值大小給每個粒子一定大小的選擇概率，將選擇出來的粒子進(jìn)行雜交變異。經(jīng)雜交操作產(chǎn)生的子代位置為：

xchild,1(t)=pxparent,1(t)+(1.0-p)xparent,2(t)

(9)

xchild,2(t)=pxparent,2(t)+(1.0-p)xparent,1(t)

(10)

其中，xchild為子代粒子的位置；xparent為父代粒子的位置；p為[0,1]之間的隨機(jī)數(shù)。

子代粒子的速度為：

(11)

(12)

其中，vchild為子代粒子的速度；vparent為父代粒子的速度。

變異操作則采用逆轉(zhuǎn)變異方法。

2.2 蟻群算法

為了使用蟻群算法調(diào)度云計算任務(wù)，需要將所有的資源節(jié)點抽象成一個有向完全圖。假設(shè)云計算環(huán)境中有4個資源，6個任務(wù)，則由資源抽象而成的有向完全圖見圖1。

圖1 資源節(jié)點組成的有向完全圖

圖中，每個節(jié)點都有入度與出度和入度邊與出度邊，每條邊上的權(quán)值表示與入度節(jié)點相關(guān)的信息素值。調(diào)度開始時，將所有任務(wù)隨機(jī)放置在資源節(jié)點上。

2.2.1 信息素初始化

信息素的初值設(shè)為：

τs=τc+τg

(13)

其中，τc是一個給定的信息素常數(shù)；τg是一個根據(jù)前期粒子群算法的調(diào)度結(jié)果轉(zhuǎn)換而來的信息素值。

具體做法是，選取粒子群算法終止時種群中適應(yīng)值最好的前10%個體作為優(yōu)化解集合。開始時，設(shè)置τg為0，對于優(yōu)化解集合中的每個解，τg自加常數(shù)k。

2.2.2 路徑選擇

第k只螞蟻在t時刻從資源節(jié)點i轉(zhuǎn)移到資源節(jié)點j的概率設(shè)為：

(14)

ηij的取值為：

(15)

2.2.3 更新信息素

當(dāng)螞蟻k從一個節(jié)點i轉(zhuǎn)移到另一個節(jié)點j時，節(jié)點的信息素會發(fā)生變化。及時更新信息素有利于提高蟻群算法的收斂精度。式(16)和式(17)給出了局部更新信息素的方法：

(16)

(17)

當(dāng)所有螞蟻完成一次循環(huán)，需對信息素進(jìn)行全局更新，公式如下：

(18)

(19)

2.3 算法流程

下面給出PSACO2算法的詳細(xì)描述。

輸入：隨機(jī)產(chǎn)生的初始種群；

輸出：全局最優(yōu)解。

(1)給出算法中相關(guān)參數(shù)的值;

(2)根據(jù)要求對粒子進(jìn)行編碼并初始化種群;

(3)將種群隨機(jī)分成兩個等量的子群,并分別編號為1和2;

(4)針對當(dāng)前子群是1號還是2號分別進(jìn)行不同處理;

(5)如果是1號子群,使用粒子群算法更新粒子的位置和速度;

(6)如果是2號子群,使用遺傳算法更新粒子的位置和速度;

(7)將兩個子群重新合并成一個種群;

(8)判斷前期迭代是否滿足停止條件或達(dá)到迭代次數(shù);

(9)若否,則返回步驟(3);若是,則執(zhí)行步驟(10);

(10)從步驟(7)中選取適應(yīng)值最好的前10%個體,并根據(jù)式(13)生成蟻群算法的初始信息素;

(11)建立蟻群算法任務(wù)調(diào)度模型,并初始化算法參數(shù);

(12)每只螞蟻根據(jù)式(14)選擇轉(zhuǎn)移節(jié)點,根據(jù)式(16)和(17)進(jìn)行局部信息素更新,并將所選節(jié)點加入禁忌表中;

(13)當(dāng)所有螞蟻完成一次循環(huán)后,根據(jù)式(18)和(19)進(jìn)行全局信息素更新;

(14)判斷后期迭代是否滿足停止條件或達(dá)到迭代次數(shù);

(15)若否,則返回步驟(12);若是,則輸出全局最優(yōu)解。

PSACO2算法的流程圖如圖2所示。

圖2 PSACO2算法流程圖

2.4 PSACO2算法的復(fù)雜度分析

PSACO2算法分為兩個階段，第一階段使用帶遺傳算子的粒子群算法，第二階段使用蟻群算法。設(shè)m為任務(wù)數(shù)量，n為資源數(shù)量，s為粒子數(shù)量，N1為第一個階段的迭代次數(shù)，第一個階段的最大迭代次數(shù)為N1max，N2為第二個階段的迭代次數(shù)，第二個階段的最大迭代次數(shù)為N2max。為了分析PSACO2算法的時間復(fù)雜度，首先分析粒子群算法的時間復(fù)雜度，見表1。

遺傳算法的時間復(fù)雜度的分析過程同粒子群算法，下面分析蟻群算法的時間復(fù)雜度，見表2。

表1 粒子群算法時間復(fù)雜度

表2 蟻群算法時間復(fù)雜度

由于在云計算環(huán)境中，任務(wù)的數(shù)量要大于節(jié)點的數(shù)量，所以PSACO2算法的時間復(fù)雜度約為O(n)=O(N1×m×s)+O(N2×n2m)。

3 實驗與分析

實驗以Cloudsim[17]作為仿真平臺、Eclipse作為開發(fā)工具以及Java作為開發(fā)語言，將提出的PSACO2算法與標(biāo)準(zhǔn)ACO算法、標(biāo)準(zhǔn)PSO算法進(jìn)行對比分析。實驗需要設(shè)置的參數(shù)如表3所示。

表3 PSACO2算法參數(shù)

續(xù)表3

蟻群算法與粒子群算法所需的參數(shù)來源表3。每種算法的迭代次數(shù)為200。實驗結(jié)果見圖3和圖4。

圖3 a=50時的任務(wù)總完成時間

圖4 a=500時的任務(wù)總完成時間

從實驗結(jié)果可知，PSACO2調(diào)度算法充分吸收了PSO算法和ACO算法的優(yōu)點，達(dá)到了預(yù)期的實驗效果。在迭代之初，PSACO2算法的調(diào)度效果優(yōu)于ACO算法，完成一定數(shù)量任務(wù)所需的執(zhí)行時間小于ACO算法；在迭代后期，PSACO2算法的調(diào)度效果同時優(yōu)于PSO和ACO算法，完成一定數(shù)量任務(wù)所需的執(zhí)行時間最少。同時還可得出，相比PSO算法和ACO算法，PSACO2算法能在相對較小的迭代次數(shù)內(nèi)找到最優(yōu)解。

4 結(jié)束語

文中通過分析PSO算法和ACO算法的優(yōu)缺點，提出一種融合二者優(yōu)點的PSACO2算法。仿真結(jié)果表明，該算法優(yōu)于其中每種算法在單獨使用時的效果，是一種高效可行的任務(wù)調(diào)度算法。

PSACO2算法只是優(yōu)化了任務(wù)完成時間，而在真實環(huán)境中還需考慮其他因素，比如平均完成時間、經(jīng)濟(jì)效益、負(fù)載均衡等。因此有必要進(jìn)一步研究和改進(jìn)PSACO2算法，以便拓寬算法的應(yīng)用場景。

[1]ArfeenMA,PawlikowskiK,WilligA.Aframeworkforresourceallocationstrategiesincloudcomputingenvironment[C]//ProcofIEEE35thannualcomputersoftwareandapplicationsconference.[s.l.]:IEEE,2011:261-266.

[2] 李千目,張晟驍,陸 路,等.一種Hadoop平臺下的調(diào)度算法及混合調(diào)度策略[J].計算機(jī)研究與發(fā)展,2013,50(S1):361-368.

[3]ZhaoChenhong,ZhangShanshan,LiuQingfeng,etal.Independenttasksschedulingbasedongeneticalgorithmincloudcomputing[C]//ProcofIEEE5thinternationalconferenceonwirelesscommunications,networkingandmobilecomputing.Beijing:IEEE,2009:1-4.

[4]GuoLizheng,ZhaoShuguang,ShenShigen,etal.Taskschedulingoptimizationincloudcomputingbasedonheuristicalgorithm[J].JournalofNetworks,2012,7(3):547-553.

[5]LiJianfeng,PengJian,CaoXiaoyang,etal.Ataskschedulingalgorithmbasedonimprovedantcolonyoptimizationincloudcomputingenvironment[J].EnergyProcedia,2011(13):6833-6840.

[6]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[C]//Proceedingsofthe6thsymposiumonoperatingsystemdesignandimplementation.NewYork:ACM,2004:137-150.

[7] 周墨頌,朱正東,董小社,等.采用資源劃分的云環(huán)境下Hadoop資源許可調(diào)度方法[J].西安交通大學(xué)學(xué)報,2015,49(8):69-74.

[8]KennedyJ,EberhartRC.Particleswarmoptimization[C]//ProcofIEEEinternationalconferenceonneuralnetworks.Piscataway,NJ:IEEEServiceCenter,1995:1942-1948.

[9]DorigoM,ManiezzoV,ColorniA.Theantsystem:optimizationbyacolonyofcooperatingagent[J].IEEETransactionsonSystems,Man,andCybernetics,PartB,1996,26(1):29-41.

[10]ShiY,EberhartRC.Amodifiedparticleswarmoptimizer[C]//Procofthe1998IEEEECP.Piscataway,NJ:IEEE,1998:67-93.

[11] 胡建秀,曾建潮.微粒群算法中慣性權(quán)重的調(diào)整策略[J].計算機(jī)工程,2007,33(11):193-195.

[12] 王 麗,王曉凱.一種非線性改變慣性權(quán)重的粒子群算法[J].計算機(jī)工程與應(yīng)用,2007,43(4):47-48.

[13] 李會榮,高岳林,李濟(jì)民.一種非線性遞減慣性權(quán)重策略的粒子群算法優(yōu)化算法[J].商洛學(xué)院學(xué)報,2007,21(4):16-20.

[14] 李 麗,牛 奔.粒子群優(yōu)化算法[M].北京:冶金工業(yè)出版社,2009.

[15]RatnawecraA,HalgamugeS.Self-organizinghierarchicalparticleswarmoptimizerwithtime-varyingaccelerationcoefficients[J].EvolutionaryComputation,2004,8(3):240-255.

[16] 紀(jì) 震,廖惠連.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社,2009.

[17]CalheirosRN,RanjanR,RoseCAFD,etal.CloudSim:anovelframeworkformodelingandsimulationofcloudcomputinginfrastructuresandservices[EB/OL].[2009-09-03].http://arxiv.org/abs/0903.2525.

A Task Scheduling Algorithm of Cloud Computing Merging Particle Swarm Optimization and Ant Colony Optimization

ZHA An-min1,TAN Wen-an1,2

(1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China;2.School of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

In cloud computing environment,there are a large number of users and tasks to be submitted by users.In order to make these tasks to be completed efficiently,how to schedule the tasks becomes the key of cloud computing.According to characteristics of cloud computing environment,improving Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO),a task scheduling algorithm combining PSO with ACO.It uses PSO to carry out the previous iteration,and selects a certain number of fine particles to generate the initial pheromone of ACO which carries out the post iteration by it,and then the final task scheduling result is obtained.The simulation shows that the algorithm is better than PSO and ACO,and decreases the total task completion time.It is an effective task scheduling algorithm．

cloud computing;task scheduling;PSO;ACO

2015-11-27

2016-03-08

時間：2016-08-01

國家自然科學(xué)基金資助項目(6127036)；上海第二工業(yè)大學(xué)重點學(xué)科(XXKZD1301)

查安民(1987-)，男，碩士研究生，研究方向為云計算、工作流調(diào)度與服務(wù)計算；譚文安，博士，教授，CCF高級會員，通訊作者，研究方向為軟件構(gòu)架技術(shù)、協(xié)同計算、服務(wù)計算與知識管理、信息化工程及其支持環(huán)境研究等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.032.html

TP301.6

A

1673-629X(2016)08-0024-06

10.3969/j.issn.1673-629X.2016.08.005