多ＱｏＳ約束的雙目標(biāo)最優(yōu)的網(wǎng)格工作流調(diào)度研究

摘 要:針對當(dāng)前網(wǎng)格工作流調(diào)度算法中大多只考慮DAG結(jié)構(gòu)的網(wǎng)格工作流，涉及QoS參數(shù)較少或?qū)⒍郠oS參數(shù)聚合成一個單目標(biāo)函數(shù)進(jìn)行優(yōu)化調(diào)度，提出了一種多QoS約束的雙目標(biāo)最優(yōu)的網(wǎng)格工作流調(diào)度算法。該算法是基于AGWL網(wǎng)格工作流模型和改進(jìn)的MOPSO算法，其目標(biāo)是在滿足可靠性、可利用性和聲譽這三維QoS參數(shù)約束下，同時最小化兩個沖突目標(biāo)，即響應(yīng)時間和服務(wù)費用。通過與原MOPSO所設(shè)計的網(wǎng)格工作流調(diào)度算法比較，該算法能獲得更優(yōu)的優(yōu)化解。

關(guān)鍵詞:服務(wù)質(zhì)量; 網(wǎng)格工作流; 調(diào)度; 多目標(biāo)粒子群算法

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2009)09-3472-03

doi:10.3969/j.issn.1001-3695.2009.09.076

Research on dual-objective optimal grid workflowscheduling with multiple QoS constraints

LI Jin-zhong， XIA Jie-wu， ZENG Jin-tao， ZHU Bing， LENG Ming

(School of Information Science Media， Jinggangshan University， Ji’an Jiangxi 343009， China)

Abstract:Existing grid workflow scheduling algorithms commonly suffer by one or several of the following drawbacks:most only considered grid workflow of DAG model， involved less QoS parameters or multidimensional QoS parameters would be aggregated into a single objective function for optimal scheduling. The paper presented an algorithm of dual-objective optimal grid workflow scheduling with multiple QoS constraints. The algorithm is based on AGWL grid workflow modeling and improved MOPSO algorithm， its goal is to simultaneously minimize two conflicting objectives- response time and service cost while mee-ting the three-dimensional QoS Constraints of reliability， availability and reputation. The proposed algorithm is compared with a grid workflow scheduling algorithm based on the original MOPSO algorithm， the experimental results show the better Pareto optincal solutions of algorithm.

Key words:quality of service(QoS); grid workflow; scheduling; multiobjective particle swarm optimization (MOPSO)

0 引言

在網(wǎng)格服務(wù)組成的工作流中，服務(wù)與資源間的映射關(guān)系組成了網(wǎng)格服務(wù)的調(diào)度方案。作為一個NP完全問題，借助典型算法很難解決網(wǎng)格工作流調(diào)度。人們嘗試用各種啟發(fā)式方法進(jìn)行求解，如遺傳算法(GA)[1，2]、 粒子群算法(PSO)[3]、禁忌搜索(TS)算法[4]、差分進(jìn)化(DE)算法[5] 、 Sufferage算法[6]以及一些算法的融合[7，8]等。

以上所設(shè)計的調(diào)度算法存在一個或多個以下缺陷:只考慮了DAG網(wǎng)格工作流模型， 缺乏如循環(huán)、并行、選擇等結(jié)構(gòu);至多考慮了響應(yīng)時間和服務(wù)費用二維QoS屬性，對于如可靠性、可利用性、聲譽等QoS屬性并未涉及;將多維QoS參數(shù)的多目標(biāo)轉(zhuǎn)換為一個單目標(biāo)函數(shù)進(jìn)行優(yōu)化，所產(chǎn)生的最優(yōu)調(diào)度方案是滿足約束條件的單目標(biāo)單一最優(yōu)解，不能從真正意義上解決多目標(biāo)的優(yōu)化問題。

本文采用AGWL建模網(wǎng)格工作流，同時考慮如循環(huán)、并行、選擇等結(jié)構(gòu)的網(wǎng)格工作流，提出了一種多QoS約束的雙目標(biāo)最優(yōu)的網(wǎng)格工作流調(diào)度算法。該調(diào)度算法在滿足可靠性R、可提供性Av、聲譽Re各QoS參數(shù)約束條件下同時優(yōu)化響應(yīng)時間T和服務(wù)費用C這二維QoS參數(shù)，最終產(chǎn)生一組Pareto優(yōu)化解集，決策者可從中選取T或C最優(yōu)或T和C綜合最優(yōu)的一個精確解，克服了現(xiàn)有調(diào)度算法中網(wǎng)格工作流結(jié)構(gòu)表達(dá)不足、考慮QoS參數(shù)較少及單目標(biāo)優(yōu)化調(diào)度的缺陷。

1 網(wǎng)格工作流調(diào)度模型

采用抽象網(wǎng)格工作流語言AGWL[9]建模網(wǎng)格工作流GW。 AGWL描述的GW包含活動、控制流結(jié)構(gòu)、數(shù)據(jù)流鏈、屬性和約束。其活動可為原子活動和復(fù)合活動。控制流結(jié)構(gòu)可分為:a)基本控制流結(jié)構(gòu)，即順序(sequence)、條件(if、switch)、循環(huán)(while、dowhile、for、forEach)、有向無環(huán)圖(dag);b)高級控制流結(jié)構(gòu)，即并行部分(parallel)、并行循環(huán)(parallelFor、parallel ForEach)。

網(wǎng)格工作流所支持的QoS參數(shù)取決于網(wǎng)格服務(wù)所支持的QoS參數(shù)。本文選擇五個通用QoS參數(shù)(T、C、R、Av、Re)構(gòu)建一個五元組模型(依據(jù)該模型可擴充評價更多維QoS參數(shù))，即QoSGS=(TGS，CGS，RGS，AvGS，ReGS)衡量網(wǎng)格服務(wù)的QoS，則活動A和網(wǎng)格工作流GW的QoS參數(shù)模型可分別對應(yīng)設(shè)計為QoSA=(TA，CA，RA，AvA，ReA)和QoSGW=(TGW，CGW，RGW，AvGW，ReGW)。GW的各維QoS參數(shù)的效益函數(shù)定義為:Up(F)=Ωp(A1，A2，…，Am)。其中:F代表T、C、R、Av、Re;Ω表示加性、乘性、最大化等運算的復(fù)合;p為某一調(diào)度方案。 假設(shè)一個抽象網(wǎng)格工作流由m個活動{A1，A2，…，Am}組成，每個活動對應(yīng)于一個抽象網(wǎng)格服務(wù)，則m個活動對應(yīng)于m個抽象服務(wù){(diào)AS1，AS2，…，ASm}，假設(shè)對ASi，存在ni個候選網(wǎng)格服務(wù){(diào)GSi1，GSi2，…，GSini}。網(wǎng)格工作流調(diào)度過程就是控制網(wǎng)格工作流中各活動的執(zhí)行順序，并從各活動對應(yīng)的候選網(wǎng)格服務(wù)集中選擇合適的服務(wù)進(jìn)行執(zhí)行過程，使得能夠滿足約束:Up(R)≥Rel、Up(Av)≥Ava和Up(Re)≥Rep，希望追求的優(yōu)化目標(biāo)，即最小化Up(T)和Up(C)。其中Rel、Ava、Rel分別為整個網(wǎng)格工作流的可靠性、可利用性和聲譽約束值。

2 多QoS約束的雙目標(biāo)最優(yōu)的網(wǎng)格工作流調(diào)度算法(IPSO)

求解多約束多目標(biāo)優(yōu)化的目的是在滿足各約束條件下，求出Pareto優(yōu)化解集，然后再由決策者根據(jù)個性需求確定一個均衡解。多目標(biāo)調(diào)度優(yōu)化模型最后的結(jié)果不是單一解，而是得到一組滿足約束條件的Pareto優(yōu)化解。MOPSO [10]算法是一種處理帶約束多目標(biāo)優(yōu)化問題的擴展PSO算法，它合并擁擠距離機制于PSO算法中，解決了全局最優(yōu)值的選擇以及非支配解集的歸檔集的刪減問題，并且與變異操作相結(jié)合，保證了歸檔集中非支配解的多樣性，還采用約束處理機制以解決約束優(yōu)化問題。

基于上述模型和思想，本文應(yīng)用改進(jìn)的MOPSO算法，設(shè)計了一種多QoS約束的雙目標(biāo)優(yōu)化的網(wǎng)格工作流調(diào)度算法(IPSO)，通過同時優(yōu)化T和C這二維QoS參數(shù)，最終產(chǎn)生一組同時滿足R、Av和Re這三個參數(shù)約束條件的Pareto最優(yōu)解，用戶可根據(jù)需要選擇自己滿意的調(diào)度方案;未被選中的方案可作為備用，在調(diào)度發(fā)生失效時啟用。

2.1 IPSO調(diào)度算法描述

算法IPSO描述如下:

a)Initialize multidimentional QoS parameters for grid services(GS)

b)Filter the GS which not satisfied with the QoS constraints of the local GS for the corresponding activity through the constrained properties of activ-ity in AGWL model workflow to reduce the encoding and searching space of the algorithm

c)Initialize the maximum number of iterations(MAXG)，the population size(N)，the archive size(Ar)， the inertia weight(W)，the two objective functions and three constraints， the probability of mutation(PMUT)， and so on

d)For each particle

(a)Initialize population with improved algorithm of initial position(P)(see I_pop algorithm for section 2.2)and velocity(V) vectors， pbest=P

(b)Evaluate P

(c)if P is better than gbest， gbest=P

e)Initialize the iteration counter G=0

f)Insert nondominated P into Ar.

g)Compute crowding distance of each Ar.

h)Sort Ar in descending crowding distance value.

i)For each particle

(a)Randomly select gbest from Ar

(b)Update velocity and position，P=P+V

(c)Keep particle within the search space boundaries

(d)Perform mutation by PMUT

(e)Evaluate fitness

(f)Next particle

j)Update contents of Ar(nondominated solutions)

k)Update each pbest，if pbest is dominated by P， pbest=P

l)if (G==MAXG)output Ar， else，G++，goto g)

2.2 改進(jìn)的種群初始化算法I_pop

為了使得種群分布更加均勻，采用兩步產(chǎn)生初始種群:先利用貪婪法生成兩個個體，分別是挑選候選網(wǎng)格服務(wù)中參數(shù)T和C最優(yōu)而組成的兩個個體;再利用隨機方式產(chǎn)生N-2個滿足約束條件的個體。

I_Pop()

{Population P0=∮;

Generate two individuals PT and PC by using greedy algorithm， namely the best selection of the QoS parameter T and C for candidate grid services， and put into P0;

while(︱P0︱≤N)

{for(i=0;i

Determine if the individual satisfies QoS constraints， if true， it is incorporated into the P0; }

Output P0;}

2.3 算法復(fù)雜度分析

IPSO的時間復(fù)雜度主要由QoS參數(shù)初始化、種群初始化、擁擠距離計算、非支配排序等操作所決定。假設(shè)種群規(guī)模為N、迭代次數(shù)為MAXG、網(wǎng)格工作流中原子活動的數(shù)量為GA，以及分別對應(yīng)的候選網(wǎng)格服務(wù)的數(shù)量為GS，Ar為歸檔集大小。則該算法總的時間復(fù)雜度=O(GA*GS)+O(¤*GA)+(O(N)+O(Ar*logAr)+O(N2))*MAXG=O(GA*GS+¤*GA+MAXG*(Ar*logAr+N2))。其中，¤的值依約束條件的變化而取值不同，其大小為N≤¤≤pow(GA， GS)。約束條件越苛刻，則¤的值越大。

3 實驗及分析

3.1 實驗設(shè)計

實驗環(huán)境為P4 2.80 GHz的CPU，512 MB內(nèi)存。 給定一個有代表性的網(wǎng)格工作流實例，如圖1所示。該工作流由三個活動組成:順序、選擇、循環(huán)活動各一個。其中選擇復(fù)合活動還包含一個并行子復(fù)合活動，共包含七個原子活動。

3.1.1 編碼策略

采用非負(fù)整數(shù)定長編碼方式，每個粒子代表一個調(diào)度方案，由D維組成，表示網(wǎng)格工作流的D個原子活動。粒子位置X[i]表示活動Ai所選擇的對應(yīng)候選網(wǎng)格服務(wù)集中的編號。

3.1.2 QoS參數(shù)和函數(shù)的設(shè)定

各候選網(wǎng)格服務(wù)的各維QoS參數(shù)值在一定區(qū)間內(nèi)以隨機方式生成，且服務(wù)費用C=常數(shù)D/響應(yīng)時間T+隨機擾動RND。依圖1所示的網(wǎng)格工作流結(jié)構(gòu)，設(shè)置網(wǎng)格工作流中QoS參數(shù)T和C的全局目標(biāo)函數(shù)分別為

obj[0]=t1+0.4*(t2+t3)+0.6*t4+0.6*max(t5，t6)+5*t7;

obj[1]=c1+0.4*(c2+c3)+0.6*(c4+c5+c6)+5*c7;

QoS參數(shù)R，Av，Re全局約束條件分別為

r1*(0.4*r2*r3+0.6*r4*r5*r6)*pow(r7，5)≥Rel;

Av1*(0.4*Av2*Av3+0.6*Av4*Av5*Av6)*pow(Av7，5) ≥Ava;

(2*Rel+0.4*(Re2+Re3)+0.3*(2*Re4+Re5+Re6)+2*Re7)/6≥Rep;

其中:可靠性約束Rel=Rmin+k*(Rmax-Rmin);可利用性約束Ava =Avmin+k*(Avmax-Avmin);聲譽約束Rel=Remin+k*(Remax-Remin)。上式中各參數(shù)中的max和min分別表示執(zhí)行整個網(wǎng)格工作流所有方案中所需R、Av和Re的最大、最小值; 約束比值k∈[0，1]。

3.2 實驗分析

表1是k、GS、MAXG不同時，算法IPSO和基于原MOPSO[10]設(shè)計調(diào)度算法OPSO求解該問題的CPU時間開銷的比較。從表1中可知。隨著k、GS、MAXG的增加，在k∈[0.2，0.6]時IPSO所需時間慢速遞增且優(yōu)于OPSO，而OPSO所需時間有所波動，其主要原因是受歸檔集中解的個數(shù)的影響。在k∈[0.7，0.75]時IPSO所需時間以較快速度增長且遠(yuǎn)超于OPSO，主要是受改進(jìn)的種群初始化方法的影響，但從圖2中可看出IPSO在k=0.75時能找到Pareto優(yōu)化解而OPSO卻沒找出。則IPSO是可行的。

表1 執(zhí)行時間(s)的比較

參數(shù)IPSOOPSO

k=0.2，GS=32，MAXG=1000.196 63.568 6

k=0.3，GS=64，MAXG=2000.265 81.484 4

k=0.4，GS=100，MAXG=5000.481 42.365 4

k=0.5，GS=200，MAXG=1 0000.793 61.543 8

k=0.6，GS=300，MAXG=5 0004.237 47.409 2

k=0.7，GS=300，MAXG=10 000188.618 610. 878 2

k=0.75，GS=300，MAXG=10 00046 894.37516.718 8

圖2是根據(jù)表1中不同k、GS、MAXG下兩算法求解該問題所產(chǎn)生的滿足R、Av、Re參數(shù)約束條件的Pareto優(yōu)化解集中參數(shù)T和C的平均值。理論上，k、MAXG的漸增，會使各QoS參數(shù)不斷優(yōu)化，而GS的漸增增加了可選網(wǎng)格服務(wù)，在一定程度上也可能會使各QoS參數(shù)不斷優(yōu)化。從圖2中可知，隨著k、GS、MAXG的增大，兩算法產(chǎn)生的T和C均值雖顯些許波動但總體趨向減小，不斷優(yōu)化中，其波動主要是隨機初始化網(wǎng)格服務(wù)QoS參數(shù)和初始化種群所致。 總體上看，IPSO要優(yōu)于OPSO，說明IPSO解決多QoS約束的雙目標(biāo)全局優(yōu)化的網(wǎng)格工作流調(diào)度問題是更有效的。

4 結(jié)束語

實驗結(jié)果和理論分析表明了IPSO算法的可行性和有效性。與類似算法比對，該算法的優(yōu)勢在于:

a)基于表達(dá)結(jié)構(gòu)豐富的AGWL語言，考慮了循環(huán)、并行、選擇等結(jié)構(gòu)的網(wǎng)格工作流。

b)文獻(xiàn)[1]中采用簡單遺傳算法，將多個QoS參數(shù)簡單優(yōu)化組合轉(zhuǎn)換為一個單目標(biāo)函數(shù)，只能得到一個滿足約束條件的優(yōu)化解，用戶沒有選擇的余地，缺乏靈活性。IPSO算法采用改進(jìn)的MOPSO算法，將多維QoS參數(shù)作為目標(biāo)函數(shù)和約束條件，通過同時優(yōu)化多個目標(biāo)函數(shù)產(chǎn)生一組滿足約束條件的Pareto優(yōu)化解集。這些解具有多樣性且在不同的目標(biāo)上各占優(yōu)勢，決策者可依實際的偏好信息選擇最合適的Pareto優(yōu)化解，沒有被選用的Pareto優(yōu)化解可作為失效時恢復(fù)。

c)同時考慮了局部和全局約束，先對不滿足各活動的QoS參數(shù)局部約束的侯選網(wǎng)格服務(wù)進(jìn)行過濾，縮小了算法的編碼和搜索空間。

由于設(shè)計IPSO算法時，對粒子位置的更新采用取整的方式進(jìn)行離散化處理，這樣往往達(dá)不到理想的最優(yōu)值。探索更好的離散化處理策略從而獲取更優(yōu)的調(diào)度方案是筆者下一步的研究目標(biāo)。

參考文獻(xiàn):

[1]王勇，胡春明，杜宗霞.服務(wù)質(zhì)量感知的網(wǎng)格工作流調(diào)度[J].軟件學(xué)報，2006，17(11):2341-2351.

[2]YU J， BUYYA R. Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms[J]. Scientific Programming， 2006，14:217-230.

[3]HU Chun-hua， WU Min， LIU Guo-ping， et al. QoS scheduling algorithm based on hybrid particle swarm optimization strategy for grid workflow[C]//Proc of the 6th International Conference on Grid and Cooperative Computing(GCC2007). 2007: 330-337.

[4]BENEDICT S， VASUDEVAN V. Improving scheduling of scientific workflows using tabu search for computational grids[J]. Information Technology Journal， 2008，7 (1):91-97.

[5]KHALED AHSAN TALUKDER A K M， KIRLEY M， BUYYA R. Multiobjective differential evolution for workflow execution on grid[C]//Proc of MGC’07. 2007.

[6]胡志剛，陳俊.網(wǎng)格工作流中一種擴展的QD-Sufferage調(diào)度算法[J].計算機應(yīng)用研究， 2008，25(5):1504-1506.

[7]于明遠(yuǎn)，朱藝華，梁榮華.基于混合微粒群算法的網(wǎng)格服務(wù)工作流調(diào)度[J].華中科技大學(xué)學(xué)報， 2008，36(4):45-47.

[8]丁一鳴，孫瑞志.基于遺傳退火算法的網(wǎng)格工作流調(diào)度研究[J].計算機應(yīng)用， 2007， 27(s1):89-91.

[9]FAHRINGER T， QIN S， HAINZER S. Specification of grid workflow applications with AGWL: an abstract grid workflow language[C]//Proc of IEEE International Symposium on Cluster Computing and the Grid 2005(CCGrid2005). Cardiff， UK: IEEE Computer Society Press， 2005: 676 - 685.

[10]RAQUEL C R， NAAL P C. An effective use of crowding distance in multiobjective particle swarm optimization[C]//Proc of Genetic And Evolutionry Computation Conf(GECCO’05). Washington DC:[s.n.]， 2005:257-264.