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

徐華　張庭

(江南大學 物聯(lián)網工程學院, 江蘇 無錫 214122)

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

徐華張庭

(江南大學 物聯(lián)網工程學院, 江蘇 無錫 214122)

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

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

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

一般來說,云計算可以分為3種主要類型的服務:基礎設施、平臺和軟件,這些服務可以通過網頁瀏覽器和移動應用等云客戶端進行訪問[4].云計算的透明性、可擴展性、冗余性、可用性和經濟性使得任務調度的地位更重要[5-6].

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

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

1云計算并行任務調度數(shù)學模型

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

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

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

2并行任務調度算法

2.1　粒子編碼與解碼

采用DPSO算法求解任務調度問題的關鍵是建立有效的粒子編碼結構,粒子編碼可以采用直接編碼和間接編碼方式.文中采用間接編碼方式對每個子任務占用的資源進行編碼,編碼長度為子任務的個數(shù),這樣一個編碼對應著一個并行任務調度策略,通過對粒子解碼產生調度方案.

2.2　適應度函數(shù)

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

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

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

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

求解云計算并行任務調度問題有如下操作：

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

(2)加法算子(⊕)分為速度和速度相加、位置和速度相加.速度和速度相加表示把后一個速度的置換序列依次加入到前一個置換序列列表的結尾.如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)減法算子(-)在云計算環(huán)境下只有1種情況,即全局最優(yōu)解或者個體最優(yōu)解位置減去個體位置,結果為置換序列.如A=(3,1,2,4,5,6),B=(1,2,4,3,6,5),那么A-B=(4,1,2,3,6,5).

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

根據(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為慣性權重,Pm,t為個體當前最優(yōu)值,Pg,t為全局當前最優(yōu)值,Pt為粒子的當前位置,c1、c2為學習因子.

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

2.4　慣性權重的調整

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

(3)

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

2.5　算法流程圖

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

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

3仿真實驗

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

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

表1　3種算法的實驗結果比較Table 1　Comparison of experimental results among three algorithms

為進一步分析文中算法的全局搜索能力和收斂性特性,對文中算法和傳統(tǒng)DPSO算法在400次迭代過程中的任務調度長度進行仿真,結果如圖2所示.

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

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

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

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

4結論

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

參考文獻:

[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].計算機工程與應用,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]陳自郁,何中市,何靜媛.一種求解集合組合問題的離散粒子群優(yōu)化模型 [J].華南理工大學學報:自然科學版,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

中圖分類號：TP301

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

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

*基金項目：國家留學基金委資助項目(201308320030)；江蘇省自然科學基金資助項目(BK20140165)

收稿日期：2014-09-28

文章編號：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)