徐華　張庭

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無(wú)錫 214122)

云計(jì)算環(huán)境下基于改進(jìn)離散粒子群的并行調(diào)度算法*

徐華張庭

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 江蘇 無(wú)錫 214122)

摘要：針對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度優(yōu)化問(wèn)題和傳統(tǒng)離散粒子群優(yōu)化(DPSO)算法早熟、精度低等缺點(diǎn),提出了一種適合云計(jì)算環(huán)境下動(dòng)態(tài)調(diào)整慣性權(quán)重因子的方法,并給出了云計(jì)算環(huán)境下改進(jìn)后的離散粒子群優(yōu)化算法.該算法能快速確定合適的并行任務(wù)分配方案,使其達(dá)到調(diào)度長(zhǎng)度最短的優(yōu)化目標(biāo).仿真結(jié)果表明:文中改進(jìn)的DPSO算法的收斂性、前期全局搜索和后期局部探索性能均優(yōu)于傳統(tǒng)的DPSO算法和遺傳算法;在任務(wù)數(shù)較大的情況下,采用改進(jìn)DPSO算法的并行任務(wù)調(diào)度算法的調(diào)度長(zhǎng)度明顯優(yōu)于采用傳統(tǒng)DPSO算法和遺傳算法的并行任務(wù)調(diào)度算法.

關(guān)鍵詞：云計(jì)算;并行算法;離散粒子群優(yōu)化

隨著系統(tǒng)虛擬化和網(wǎng)絡(luò)技術(shù)的發(fā)展,云計(jì)算已經(jīng)成為一種新的計(jì)算平臺(tái).云計(jì)算作為一種新興的并行計(jì)算技術(shù),是分布式計(jì)算、網(wǎng)格計(jì)算和并行計(jì)算等計(jì)算機(jī)技術(shù)的商業(yè)實(shí)現(xiàn),從其誕生開(kāi)始就具有巨大的商機(jī)[1-2].云計(jì)算的主要目的是為了更好地利用分布式資源和解決大規(guī)模計(jì)算問(wèn)題.在“云”中如何對(duì)任務(wù)進(jìn)行高效合理的調(diào)度,實(shí)現(xiàn)系統(tǒng)全局最優(yōu)化,成為云計(jì)算研究的重點(diǎn)與難點(diǎn)[3].

一般來(lái)說(shuō),云計(jì)算可以分為3種主要類(lèi)型的服務(wù):基礎(chǔ)設(shè)施、平臺(tái)和軟件,這些服務(wù)可以通過(guò)網(wǎng)頁(yè)瀏覽器和移動(dòng)應(yīng)用等云客戶(hù)端進(jìn)行訪問(wèn)[4].云計(jì)算的透明性、可擴(kuò)展性、冗余性、可用性和經(jīng)濟(jì)性使得任務(wù)調(diào)度的地位更重要[5-6].

在云計(jì)算環(huán)境中,任務(wù)調(diào)度是一個(gè)NP完全問(wèn)題[7],其主要目的是優(yōu)化總調(diào)度長(zhǎng)度.目前,求解NP完全問(wèn)題的主要智能優(yōu)化算法有模擬退火算法、遺傳算法和粒子群算法等.并行任務(wù)調(diào)度是指將任務(wù)分成更多、更小的子任務(wù),并將資源分配給這些符合條件的子任務(wù)使用,沒(méi)有依賴(lài)關(guān)系的子任務(wù)可以并行執(zhí)行.云計(jì)算環(huán)境下任務(wù)量和資源量是非常龐大的,系統(tǒng)時(shí)刻都在處理著海量的任務(wù).考慮到大量的任務(wù)是在分散的地理資源上執(zhí)行,因此云計(jì)算環(huán)境下高效的任務(wù)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)是一個(gè)具有挑戰(zhàn)性的問(wèn)題.

針對(duì)傳統(tǒng)離散粒子群優(yōu)化(DPSO)算法早熟、精度低等缺點(diǎn),文中提出了一種適合云計(jì)算并行任務(wù)調(diào)度的改進(jìn)離散粒子群優(yōu)化算法,并通過(guò)實(shí)驗(yàn)分析該改進(jìn)離散粒子群優(yōu)化算法的前期全局搜索和后期局部探索能力、收斂性能.

1云計(jì)算并行任務(wù)調(diào)度數(shù)學(xué)模型

云計(jì)算并行任務(wù)調(diào)度是指將N個(gè)任務(wù)通過(guò)某種調(diào)度策略調(diào)度到R個(gè)資源上并行執(zhí)行,使調(diào)度長(zhǎng)度最短.其中,N個(gè)任務(wù)可以分為S個(gè)子任務(wù),T={T1,T2,…,TN}表示任務(wù)集,r={r1,r2,…,rR}表示資源集.Tsub是一個(gè)S×N的矩陣,表示任務(wù)與子任務(wù)之間的依賴(lài)關(guān)系,第i個(gè)任務(wù)的第j個(gè)子任務(wù)Tsub,ij(i=1,2,…,N;j=1,2,…,S)沒(méi)完成之前,第k(k>j)個(gè)子任務(wù)Tsub,ik(k=1,2,…,S)不能執(zhí)行.

在并行執(zhí)行過(guò)程中,te是一個(gè)R×S的矩陣,其元素te,p j表示第j(j=1,2,…,S)個(gè)子任務(wù)在資源rp(p=1,2,…,R)上的執(zhí)行時(shí)間,

臨時(shí)資源池st是一個(gè)S×6的矩陣,它總是存放正在執(zhí)行或即將執(zhí)行的子任務(wù).st中第1至第6列分別表示資源集合、執(zhí)行的子任務(wù)集合、執(zhí)行對(duì)應(yīng)資源的任務(wù)數(shù)量集合、任務(wù)集合、子任務(wù)在任務(wù)中的位置集合、任務(wù)執(zhí)行時(shí)間集合.每個(gè)子任務(wù)只能在一個(gè)資源上執(zhí)行;一個(gè)資源上如果有一個(gè)子任務(wù)在執(zhí)行,則該資源不再接受其他子任務(wù).ts,i為任務(wù)Ti執(zhí)行的起始時(shí)刻,tex,pi(p=1,2,…,R;i=1,2,…,N)為T(mén)i在資源rp上執(zhí)行完成的時(shí)刻,tpi=max(tex,pi-ts,i),則tpi為任務(wù)Ti在資源rp上執(zhí)行所需的時(shí)間.優(yōu)化目標(biāo)是使tpi最小.

2并行任務(wù)調(diào)度算法

2.1　粒子編碼與解碼

采用DPSO算法求解任務(wù)調(diào)度問(wèn)題的關(guān)鍵是建立有效的粒子編碼結(jié)構(gòu),粒子編碼可以采用直接編碼和間接編碼方式.文中采用間接編碼方式對(duì)每個(gè)子任務(wù)占用的資源進(jìn)行編碼,編碼長(zhǎng)度為子任務(wù)的個(gè)數(shù),這樣一個(gè)編碼對(duì)應(yīng)著一個(gè)并行任務(wù)調(diào)度策略,通過(guò)對(duì)粒子解碼產(chǎn)生調(diào)度方案.

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

2.3　離散粒子群優(yōu)化算法

PSO算法是一種隨機(jī)優(yōu)化算法,它源于對(duì)鳥(niǎo)群捕食行為的研究[8].在粒子群優(yōu)化算法中,粒子m在進(jìn)化的過(guò)程中有兩個(gè)向量,分別是位置向量xm=[xm,1,xm,2,…,xm,D]和速度向量vm=[vm,1,vm,2,…,vm,D],其中D為求解問(wèn)題的維度.粒子的速度決定了粒子運(yùn)動(dòng)的方向和速率,位置代表了粒子解在解空間中的位置.PSO算法適用于計(jì)算連續(xù)的搜索空間,故其研究也主要集中在連續(xù)函數(shù)方面.然而許多實(shí)際工程應(yīng)用問(wèn)題是離散的,變量也是有限的,為了使PSO算法能夠解決離散優(yōu)化問(wèn)題,Kennedy等[9]提出了離散二進(jìn)制粒子群優(yōu)化(BPSO)算法.在BPSO算法中,一個(gè)二進(jìn)制空間表示為一個(gè)超立方體,每個(gè)粒子用一個(gè)二進(jìn)制變量來(lái)表示,通過(guò)變量的某些位在0或1之間的變化來(lái)實(shí)現(xiàn)粒子的移動(dòng).之后BPSO算法廣泛應(yīng)用于離散優(yōu)化問(wèn)題,如經(jīng)濟(jì)規(guī)劃、圖形圖像、旅行商問(wèn)題、背包問(wèn)題和工作流調(diào)度問(wèn)題等[10-15].

在云計(jì)算環(huán)境下,并行任務(wù)調(diào)度問(wèn)題是離散優(yōu)化問(wèn)題,將DPSO算法應(yīng)用到并行任務(wù)調(diào)度中,數(shù)學(xué)中的加、減、乘、除運(yùn)算不再適用,需要重新定義.在DPSO算法中,粒子的位置為一個(gè)S維向量,表示為x=[x1,x2,…,xj,…,xS],粒子的速度被定義為粒子位置改變的概率,是一個(gè)S維向量,表示為v=[v1,v2,…,vj,…,vS],位置與速度的加法運(yùn)算實(shí)現(xiàn)了粒子位置的移動(dòng),即粒子進(jìn)入新的位置.

云計(jì)算環(huán)境下位置減去位置等于速度,速度加速度等于速度,位置加速度等于位置,μ(μ∈R)乘以速度等于速度.

求解云計(jì)算并行任務(wù)調(diào)度問(wèn)題有如下操作：

(1)假設(shè)粒子的位置為x,置換序列(f,g)的操作為交換x中的第f和第g個(gè)元素.

(2)加法算子(⊕)分為速度和速度相加、位置和速度相加.速度和速度相加表示把后一個(gè)速度的置換序列依次加入到前一個(gè)置換序列列表的結(jié)尾.如A=(1,9,3,7,5,6)⊕(3,5)=(1,9,5,7,3,6),B=A⊕(1,6)=(1,9,5,7,3,6)⊕(1,6)=(6,9,5,7,3,1).

(3)減法算子(-)在云計(jì)算環(huán)境下只有1種情況,即全局最優(yōu)解或者個(gè)體最優(yōu)解位置減去個(gè)體位置,結(jié)果為置換序列.如A=(3,1,2,4,5,6),B=(1,2,4,3,6,5),那么A-B=(4,1,2,3,6,5).

(4)乘法算子(?)在云計(jì)算環(huán)境下只有1種情況,即w(w∈R)與速度相乘,表示以概率w保留粒子的速度.

根據(jù)上面的操作,在云計(jì)算環(huán)境下粒子i的速度和位置更新公式為

vt+1=w?vt⊕c1?(Pm,t-Pt)⊕c2?(Pg,t-Pt)

(1)

xt+1=xt⊕w?vt+1

(2)

式中,w為慣性權(quán)重,Pm,t為個(gè)體當(dāng)前最優(yōu)值,Pg,t為全局當(dāng)前最優(yōu)值,Pt為粒子的當(dāng)前位置,c1、c2為學(xué)習(xí)因子.

隨機(jī)產(chǎn)生粒子種群的初始位置和速度,然后按照式(1)和(2)進(jìn)行迭代,直到滿(mǎn)足終止條件為止,此時(shí)的全局最優(yōu)值就是優(yōu)化運(yùn)算后的近似最優(yōu)解.

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

慣性權(quán)重w是粒子群算法中很重要的一個(gè)參數(shù),它平衡了粒子群體的全局搜索能力和局部探索能力.為了使算法在初期能進(jìn)行較強(qiáng)的全局搜索、而在后期進(jìn)行較強(qiáng)的局部搜索,文中采用指數(shù)增長(zhǎng)的慣性權(quán)重計(jì)算公式,即

(3)

式中:K=wmax-wmin,wmax和wmin分別為慣性權(quán)重的最大值、最小值;M=I/Imax,I為當(dāng)前迭代次數(shù),Imax為最大迭代次數(shù);a(a∈[0.6,1.2])、b(b∈[10,25])為調(diào)節(jié)因子.調(diào)節(jié)因子a和b的取值由經(jīng)驗(yàn)決定,經(jīng)過(guò)a、b的調(diào)整,隨著進(jìn)化次數(shù)的增加,慣性權(quán)重w加速減小,前期有利于全局搜索,后期有利于局部探索.

2.5　算法流程圖

文中提出的改進(jìn)離散粒子群優(yōu)化算法的流程圖如圖1所示.

圖1　文中算法流程圖Fig.1　Flowchart of the proposed algorithm

3仿真實(shí)驗(yàn)

為測(cè)試文中算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用效果,采用CloudSim平臺(tái)進(jìn)行測(cè)試,在Matlab 2012中進(jìn)行仿真.本實(shí)驗(yàn)的硬件環(huán)境為:內(nèi)存8 GB,硬盤(pán)500 GB;軟件環(huán)境為:Windows 7操作系統(tǒng),Eclipse kepler開(kāi)發(fā)工具.模擬仿真了8個(gè)虛擬資源、40個(gè)不同的子任務(wù),在相同的實(shí)驗(yàn)條件下對(duì)傳統(tǒng)DPSO算法[8]、遺傳算法[16]和文中算法的性能進(jìn)行比較與分析.實(shí)驗(yàn)參數(shù)設(shè)置如下:種群規(guī)模為500,最大迭代次數(shù)為400,慣性權(quán)重最大值和最小值分別為0.96、0.36,學(xué)習(xí)因子c1=0.1、c2=0.3.

在不同迭代次數(shù)下反復(fù)進(jìn)行50次實(shí)驗(yàn),并對(duì)實(shí)驗(yàn)結(jié)果取平均值,結(jié)果如表1所示.從表中可以看出:文中算法在求解并行任務(wù)調(diào)度問(wèn)題時(shí),找到的最優(yōu)解遠(yuǎn)遠(yuǎn)小于DPSO算法和遺傳算法,且其最優(yōu)解精度分別比DPSO算法、遺傳算法提高了2.96%、6.65%;對(duì)于最優(yōu)解中的最差解,文中算法略大于DPSO算法和遺傳算法,表明文中算法的全局搜索能力強(qiáng)于DPSO算法和遺傳算法;文中算法找到最優(yōu)解的平均迭代次數(shù)大于其他兩種算法,表明文中算法有較好的收斂性能.

表1　3種算法的實(shí)驗(yàn)結(jié)果比較Table 1　Comparison of experimental results among three algorithms

為進(jìn)一步分析文中算法的全局搜索能力和收斂性特性,對(duì)文中算法和傳統(tǒng)DPSO算法在400次迭代過(guò)程中的任務(wù)調(diào)度長(zhǎng)度進(jìn)行仿真,結(jié)果如圖2所示.

圖2　不同迭代次數(shù)下兩種算法的調(diào)度長(zhǎng)度對(duì)比Fig.2　Comparison of scheduling length between two algorithms under different iteration times

從圖中可以看出,傳統(tǒng)DPSO算法因只重視總完成時(shí)間而造成了一些潛在的優(yōu)良粒子丟失,很快陷入局部極優(yōu),進(jìn)入收斂狀態(tài),并最終收斂于最優(yōu)解301.文中改進(jìn)算法在迭代次數(shù)小于50時(shí),粒子一直處于搜索狀態(tài),多次跳出局部極優(yōu),這表明文中算法在迭代前期具有較強(qiáng)的全局搜索能力;在此之后粒子慢慢局部探索,逐步尋找到全局最優(yōu)解,與傳統(tǒng)DPSO算法相比,文中算法在迭代后期具有較強(qiáng)的局部探索性能.文中改進(jìn)算法在迭代50次時(shí),粒子開(kāi)始收斂,最終靠近全局最優(yōu)解289.表1和圖2表明,文中算法的收斂性、全局探索能力和局部探索能力圴優(yōu)于傳統(tǒng)DPSO算法和遺傳算法.

文中算法、傳統(tǒng)DPSO算法和遺傳算法在不同任務(wù)數(shù)量(20、40、60、80、100)下的適應(yīng)度如圖3所示.從圖中可以看出,在任務(wù)數(shù)量較小的情況下,3種算法的適應(yīng)度差別并不明顯,但隨著任務(wù)的增多,文中算法的調(diào)度長(zhǎng)度明顯優(yōu)于其他兩種算法,并且任務(wù)越多這個(gè)趨勢(shì)越明顯.

圖3　3種算法在不同任務(wù)數(shù)下的適應(yīng)度值Fig.3　Fitness values of three algorithms with different numbers of tasks

4結(jié)論

文中提出了一種適用于云計(jì)算環(huán)境下的并行任務(wù)調(diào)度算法,首先定義了云計(jì)算環(huán)境下的并行任務(wù)調(diào)度數(shù)學(xué)模型,然后進(jìn)行粒子的編碼與解碼并定義操作算子,最后采用改進(jìn)的DPSO算法對(duì)任務(wù)調(diào)度方案進(jìn)行并行調(diào)度迭代尋優(yōu).仿真結(jié)果表明,文中算法獲得的最優(yōu)解、前期全局搜索能力和后期探索性能均優(yōu)于傳統(tǒng)DPSO算法和遺傳算法,并且在迭代后期具有良好的收斂性能.

參考文獻(xiàn):

[1]Sadiku M N O,Musa S M,Momoh O D.Cloud computing:opportunities and challenges [J].IEEE Potentials,2014,33(1):34-36.

[2]Stieninger Mark,Nedbal Dietmar.Characteristics of cloud computing in the business context:a systematic literature review [J].Global Journal of Flexible Systems Management,2014,15(1):59- 68.

[3]董麗麗,黃賁,介軍.云計(jì)算中基于差分進(jìn)化算法的任務(wù)調(diào)度研究 [J].計(jì)算機(jī)工程與應(yīng)用,2014,50(5):90-95.

Dong Li-li,Huang Ben,Jie Jun.Task scheduling based on differential evolution algorithm in cloud computing [J]. Computer Engineering and Applications,2014,50(5):90-95.

[4]Chong H Y,Wong J S,Wang X.An explanatory case study on cloud computing applications in the built environment [J].Automation in Construction,2014,44:152-162.

[5]Deng Qian-ni,Chen Quan.Cloud computing and key technology [J].Development & Application of High Perfor-mance Computing,2009,26(1):2- 6.

[6]Lin Weiwei,Liang Chen,James Z,et al.Bandwidth-aware divisible task scheduling for cloud computing [J].Software:Particle and Experience,2014,44(2):163-174.

[7]Arfeen M A,Pawlikowski K,Willig A.A framework for resource allocation strategies in cloud computing environment [C]∥Proceeddings of 2011 IEEE the 35th Annual Computer Software and Applications Conference Workshops.Munich:IEEE,2011:261-266.

[8]Kennedy J,Eberhart R.Particle swarm optimization [C]∥Proceedings of IEEE International Conference on Neural Networks.Piscataway:IEEE,1995:1942-1948.

[9]Kennedy J,Eberhart R.A discrete binary version of the particle swarm algorithm [C]∥Proceedings of the World Multiconference on Systemics,Cybernetics and Informa-tics.Piscataway:IEEE,1997:4104-4109.

[10]Shao X Y,Liu W Q,Liu Q,et al.Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem [J].The International Journal of Advanced Manufacturing Technology,2013,67(9/10/ 11/12):2885-2901.

[11]Iman Z,Gerard L,Arindam G.A new technique for optimal allocation and sizing of capacitors and setting of LTC [J].International Journal of Electrical Power & Energy Systems,2013,46:250-257.

[12]Wang Xiao-hua,Mu Ai-qin,Zhu Shi-song.ISPO:a new way to solve traveling salesman problem [J].Intelligent Control and Automation,2013,4(2):122-125.

[13]Amira G,Abdesslem L,Salim C.Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm [J].International Journal of Bio-Inspired Com-putation,2012,4(4):229-236.

[14]Cao J F,Chen J J,Zhao Q S.An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm [J].Cybernetics and Information Technologies,2014,14(1):25-39.

[15]陳自郁,何中市,何靜媛.一種求解集合組合問(wèn)題的離散粒子群優(yōu)化模型 [J].華南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2010,38(4):141-146.

Chen Zi-yu,He Zhong-shi,He Jing-yuan.Discrete particle swarm optimization model for set-based combinatorial optimization problems [J].Journal of South China University of Technology:Natural Science Edition,2010,38(4):141-146.

[16]Fogel D B.An introduction to simulated evolutionary optimization [J].IEEE Transactions on Neural Networks, 1994,5(1):3-14.

Improved Discrete Particle Swarm-Based Parallel Schedule Algorithm in Cloud Computing Environment

XuHuaZhangTing

(School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, Jiangsu, China)

Abstract:Aiming at the optimization problem of task scheduling in the cloud computing environment and the defects of prematurity and low precision of traditional discrete particle swarm optimization (DPSO) algorithms, a method of dynamically adjusting the inertia weight factor is proposed in a cloud computing environment, and an improved discrete particle swarm optimization algorithm is put forward. This algorithm can determine the appropriate parallel task allocation scheme quickly, and makes the scheme achieve the shortest scheduling length. Simulation results show that the improved DPSO algorithm is superior to the traditional DPSO algorithm and the genetic algorithm in terms of the convergence, the previous global search capability and the late local exploration performance, and that, in the case of a large number of tasks, the parallel task scheduling algorithm using the improved DPSO algorithm is superior to those using the traditional DPSO algorithm or the genetic algorithm in terms of scheduling length.

Key words:cloud computing; parallel algorithms; discrete particle swarm optimization

中圖分類(lèi)號(hào)：TP301

doi：10.3969/j.issn.1000-565X.2015.09.015

作者簡(jiǎn)介：徐華(1978-)，女，博士，副教授，主要從事人工神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)、水污染等研究.E-mail: joanxh2003@163.com

*基金項(xiàng)目：國(guó)家留學(xué)基金委資助項(xiàng)目(201308320030)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20140165)

收稿日期：2014-09-28

文章編號(hào)：1000-565X(2015)09-0095-05

Foundation items： Supported by the National Scholarship Fund Program(201308320030) and the Natural Science Foundation of Jiangsu Province(BK20140165)