基于多目標(biāo)沖突度網(wǎng)格任務(wù)調(diào)度策略

(1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001;2.黑龍江科技學(xué)院計(jì)算機(jī)與信息工程學(xué)院， 哈爾濱 150027）

摘 要：針對(duì)網(wǎng)格計(jì)算中多目標(biāo)之間存在沖突的獨(dú)立任務(wù)調(diào)度問題，應(yīng)用多目標(biāo)線性規(guī)劃為系統(tǒng)建模，通過求解多目標(biāo)線性規(guī)劃的梯度向量來確定多目標(biāo)之間的沖突度，形成多目標(biāo)沖突度網(wǎng)格獨(dú)立任務(wù)調(diào)度模型。提出該模型預(yù)處理算法和多目標(biāo)沖突度遺傳算法，這兩個(gè)算法確保網(wǎng)格用戶在多目標(biāo)維度下的效用值最大化。實(shí)驗(yàn)結(jié)果表明，在時(shí)間、安全性、可靠性維度和丟棄任務(wù)數(shù)等指標(biāo)方面，該算法的綜合性能優(yōu)于Max-min和T-Sufferage算法。

關(guān)鍵詞：網(wǎng)格計(jì)算；任務(wù)調(diào)度；線性規(guī)劃；沖突度；遺傳算法

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

文章編號(hào)：1001-3695(2009)04-1491-03

Grid tasks scheduling strategy based on degree of multi-objective conflict

QIAO Fu1，2，ZHANG Guo-yin1，LIU Zhong-yan2

(1.College of Computer Science Technology， Harbin Engineering University， Harbin 150001， China;2.College of Computer Information Engineering， Heilongjiang Institute of Science Technology， Harbin 150027， China)

Abstract:Multi-objective contradictory problem of independent tasks scheduling exits in grid computing systems， where resources were heterogeneous.Presented multi-objective linear programming model for this problem. Using the model，found multi-objective degree of conflict with gradient vector.This paper proposed model processing and multi-objective degree of conflict generation algorithm.Using the two algorithms， multi-objective dimension utility could obtain max value. The experimental results show that the proposed algorithms for scheduling problem obtain better performance than Max-min and T-Sufferage algorithm in time-dimension， security-dimension， reliability-dimension and dropped task numbers.

Key words:grid computing; tasks scheduling; linear programming; degree of conflict; generation algorithm

0 引言

在資源異構(gòu)高效的網(wǎng)格計(jì)算中，網(wǎng)格環(huán)境涉及網(wǎng)格用戶、網(wǎng)格資源管理者、虛擬組織管理者等多個(gè)實(shí)體，不同實(shí)體間對(duì)管理機(jī)制、安全策略、費(fèi)用等目標(biāo)都不盡相同，有的甚至相互抵觸。因此，如何通過資源管理與調(diào)度算法協(xié)調(diào)不同種實(shí)體間和同類實(shí)體內(nèi)部的目標(biāo)要求是當(dāng)前網(wǎng)格計(jì)算中的熱點(diǎn)問題[1]，該問題已經(jīng)被證明是NP難問題。

當(dāng)前的網(wǎng)格任務(wù)調(diào)度算法研究主要是基于圖論的分配算法、整數(shù)規(guī)劃方法和啟發(fā)式方法來構(gòu)造最終的調(diào)度方案[2]。其中啟發(fā)式算法方法簡(jiǎn)單有效，文獻(xiàn)[3~5]的研究者做了大量工作， 雖然提出一些考慮任務(wù)多需求的啟發(fā)式調(diào)度策略， 將多個(gè)目標(biāo)函數(shù)聚合成單一目數(shù)，具有時(shí)間復(fù)雜度低、便于實(shí)現(xiàn)的特點(diǎn)。但這些算法均采用單目標(biāo)優(yōu)化策略，較多目標(biāo)策略而言存在明顯的缺陷。這些文獻(xiàn)中有代表性的如文獻(xiàn)[6]提出一種面向多QoS約束網(wǎng)格作業(yè)調(diào)度問題的多目標(biāo)演化算法，盡可能協(xié)調(diào)不同用戶的目標(biāo)要求，保障網(wǎng)格用戶在多個(gè)目標(biāo)維度下的效用值最大化；但其在系統(tǒng)建模時(shí)，處理多目標(biāo)沖突上只是采用簡(jiǎn)單的加權(quán)法，使得相互沖突的目標(biāo)不能得到有效處理。本文應(yīng)用多目標(biāo)線性規(guī)劃對(duì)系統(tǒng)建模時(shí)，不同于文獻(xiàn)[7]的建模方法是基于梯度上升法求解模型中多目標(biāo)間的沖突度來確定各個(gè)目標(biāo)的權(quán)重，這種建模方式的優(yōu)點(diǎn)在于系統(tǒng)模型時(shí)，就可以解決多目標(biāo)間的相互沖突問題，然后再應(yīng)用多目標(biāo)沖突度遺傳算法（Mul-Obj-Ga）解決該模型下網(wǎng)格獨(dú)立任務(wù)調(diào)度問題。實(shí)驗(yàn)表明，Mul-Obj-Ga算法的性能優(yōu)于現(xiàn)有的Max-min和T-Sufferage算法[3，4]。

1 調(diào)度模型

為方便描述調(diào)度模型，介紹下面一些定義。

定義1 由集合R={r1，r2，r3，…，rm}表示具有m個(gè)異構(gòu)的計(jì)算節(jié)點(diǎn)構(gòu)成的網(wǎng)格環(huán)境。

定義2 由集合J={j1，j2，j3，…，jn}表示具有n個(gè)獨(dú)立任務(wù)構(gòu)成的任務(wù)集合。

定義3 集合X={x1，x2，…，xn}表示由映射方案構(gòu)成的映射空間集合。一個(gè)映射方案為一個(gè)二元組x=(a，s)。其中:a： R→J表示計(jì)算節(jié)點(diǎn)調(diào)度任務(wù)的映射，a(ru)=ji表示計(jì)算節(jié)點(diǎn)ru調(diào)度任務(wù)ji到其上并執(zhí)行； s(ji，rk)=h，表示在計(jì)算節(jié)點(diǎn)ru上第h個(gè)執(zhí)行的任務(wù)為ji。

定義4 集合QoS(xi)=(Q1，Q2，…，Qp)={(q1，q2，…，qp)|qy∈Qy}表示p維約束空間。其中：Qy表示在映射方案xi下，第y個(gè)QoS維上所有取值；qy表示任務(wù)在第y個(gè)QoS約束空間上的一個(gè)約束值。

定義5 網(wǎng)格任務(wù)調(diào)度模型由式(1)表示：

best(f k)=pj=1ckjxj=Kj=1Kk=1Wkckjxj s.t.x∈X

pj=1Qj(x)≥qminj(1)

其中:k=1，2，…，K為目標(biāo)的個(gè)數(shù)；j=1，2，…，p為QoS約束空間的維數(shù)；qminj為任務(wù)的最小QoS需求；ckj為常數(shù)，表示不同任務(wù)具有不同的約束量化值，由任務(wù)被輸入時(shí)確定或采用預(yù)測(cè)的方法。若x={x1，x2，…，xp}滿足式(1)，即x={x1，x2，…，xp}∈X，則其為一個(gè)可行調(diào)度方案。為確定最佳調(diào)度方案，采用梯度上升法給不同的目標(biāo)賦予不同的權(quán)重。各個(gè)目標(biāo)的權(quán)重求解由多目標(biāo)線性規(guī)劃模型式(2)求出。

best(f k)=pj=1ckjxj s.t.x∈X(2)

梯度可由式(3)表示

Gk=（fk/x1，

fk/x2，…，fk/xp）T=(ck1，ck2，…，ckp)T(3)

因此，目標(biāo)y與z之間的沖突程度可以用這兩個(gè)目標(biāo)的梯度方向夾角θyz來度量：

cos θyz=pi=1cyiczi/pi=1(cyi)2pi=1(czi)2 y，z=1，2，…，K

(4)

當(dāng)θyz=0時(shí)，目標(biāo)y與z的梯度方向一致，即這兩個(gè)目標(biāo)函數(shù)在相同的方向上，兩個(gè)目標(biāo)沒有沖突；當(dāng)θyz≠0時(shí)，目標(biāo)y與z的梯度方向不一致，兩個(gè)目標(biāo)沒有沖突，且隨著θyz的增大，沖突逐漸增大；當(dāng)θyz=π時(shí)，目標(biāo)y與z的梯度方向相反，此時(shí)沖突最大。

由模糊集合理論，定義如下函數(shù)作為目標(biāo)之間的沖突函數(shù)：

hyz=(π-θyz)/π；0≤θyz≤π；y，z=1， 2， … ，K(5)

矩陣H表示所有目標(biāo)之間的非沖突程度，如式(6)表示：

H=(hyz)K×K=

1h12…h(huán)1K

h211…h(huán)2K



hK1hK2…1(6)

其中：第k行的元素表示第k個(gè)目標(biāo)與其他所有目標(biāo)之間的非沖突程度。設(shè)Uk表示第k個(gè)目標(biāo)與所有目標(biāo)之間的非沖突程度的總和由式(7)表示，在一定程度上能夠反映所有目標(biāo)對(duì)第k個(gè)目標(biāo)的支持程度。

Uk=Kj=1hkj(k=1，2，…，K)(7) 

令第k個(gè)目標(biāo)的權(quán)重為

Wk=Uk/Kk=1Uk(k=1，2，…，K)(8) 

2 算法描述

2.1 模型預(yù)處理算法描述

通過模型預(yù)處理PREmodel算法，確定該模型的目標(biāo)沖突度，形成遺傳算法下的調(diào)度模型。

PREmodel算法描述如下：

Procedure PREmodel()//模型預(yù)處理算法開始

Initial()//初始化參數(shù)K、ckj

for k=1toK

Gk=(ck1，ck2，…，ckp)T//求第k個(gè)目標(biāo)的梯度

end for

for y=1 to K

for z=1 to K

if y◇z then

θyz=arccos(pi=1cyiczi/pi=1(cyi)2pi=1(czi)2)

//求目標(biāo)y與z之間的沖突程度

end if

H(y，z)=π-θyz/π//求沖突矩陣H

end for

end for

for k=1 to K

for j=1 to K

Uj=Kk=1hjk

end for

Wk=Uk/Kk=1Uk//第k個(gè)目標(biāo)的權(quán)重

end for

end//模型預(yù)處理算法結(jié)束

2.2 多目標(biāo)沖突度遺傳算法描述

多目標(biāo)沖突度遺傳算法的染色體編碼采用圖1所示的雙層染色體編碼，染色體上層為任務(wù)層。其中，ji代表第i個(gè)被調(diào)度的任務(wù)，下層為網(wǎng)格節(jié)點(diǎn)，行的方向表示了任務(wù)的調(diào)度順序，列的方向表示pj與ji之間的調(diào)度關(guān)系，兩者構(gòu)成一個(gè)基因。在本算法中，適應(yīng)度函數(shù)取決于調(diào)度的完成時(shí)間。算法的適應(yīng)度函數(shù)表示為

fit(xi)=1/f(xi)(9)

2.2.1 生成初始種群

生成初始種群采用如下算法描述：

Procedure Gen_Initial()//算法開始

PREmodel()//模型預(yù)處理算法

Initial(N， N′， Gmax，Cmax，Pc，Pm，Wk，ETC，QoS(x))/*初始化控制參數(shù)：群體規(guī)模大小N，外部?jī)?yōu)勢(shì)集規(guī)模大小N′，遺傳代數(shù)Gmax，迭代次數(shù)Cmax，交叉概率Pc，變異概率Pm，各子目標(biāo)權(quán)重Wk*/

Do UntilEmpty(J) 

if pj=1Qj(x)≥qminj then；//滿足最小QoS約束

add_quene(pj，ji)

//將任務(wù)ji的加入到網(wǎng)格節(jié)點(diǎn)pj的調(diào)度隊(duì)列尾；

Delete(J，ji)//從J中刪除ji；

end if

end Until

end//算法結(jié)束

2.2.2 遺傳算子

對(duì)染色體進(jìn)行遺傳遺傳操作包括三個(gè)基本的算子：

a)選擇算子。采用輪盤賭的方式對(duì)染色體進(jìn)行選擇，某個(gè)體被選中的概率為

p(xi)=fit(xi)/Ni=1fit(xi)(10)

其中：N為種群的規(guī)模。

b)交叉算子。采用兩點(diǎn)交叉，對(duì)由選擇算子選出的兩個(gè)父?jìng)€(gè)體x1和x2，隨機(jī)生成兩個(gè)交叉點(diǎn)c1和c2，在交叉生成的子個(gè)體中，在c1之前及c2之后的網(wǎng)格節(jié)點(diǎn)的任務(wù)隊(duì)列由x1繼承得到，而在c1與c2之間的網(wǎng)格節(jié)點(diǎn)的任務(wù)隊(duì)列由x2繼承得到。

c)變異算子。對(duì)由交叉算子產(chǎn)生的子個(gè)體，以概率q對(duì)其進(jìn)行變異。隨機(jī)選擇其上的兩個(gè)網(wǎng)格節(jié)點(diǎn)p1和p2，在它們對(duì)應(yīng)的任務(wù)隊(duì)列上分別隨機(jī)選擇一個(gè)任務(wù)，得到j(luò)1和j2，交換它們的位置得到經(jīng)過變異產(chǎn)生的子個(gè)體。

多目標(biāo)沖突度遺傳算法描述如下：

Procedure Mul-Obj-Ga()//算法開始

Gen_Initial()

//生成N個(gè)個(gè)體的初始種群X0和空的外部?jī)?yōu)勢(shì)集X′；

g=0

for g++

do until C=0

用ELECTRE法對(duì)X0中的個(gè)體排序，產(chǎn)生的最小優(yōu)勢(shì)集拷貝至X′；

將X′中的劣解刪去；

if外部存儲(chǔ)的優(yōu)勢(shì)個(gè)體超過規(guī)定數(shù)值Nthen

對(duì)X′實(shí)施聚類處理(平均關(guān)聯(lián)法)，使其個(gè)體總數(shù)不超過N′

end if

按照式(9)，計(jì)算X0和X′中個(gè)體的適應(yīng)度；

從X0和X′兩集合中使用二進(jìn)制聯(lián)賽規(guī)則選擇優(yōu)勢(shì)個(gè)體形成配對(duì)池，產(chǎn)生的N個(gè)優(yōu)勢(shì)個(gè)體賦給X0；

使用交叉概率Pc和變異概率Pm進(jìn)行交叉和變異；

end until；

end for

end//算法結(jié)束

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證Mul-Obj-Ga算法的性能，與同類算法中性能較好的Max-min和T-Sufferage算法進(jìn)行比較。在Max-min和T-Sufferage中也使用該模型下的預(yù)處理算法PREmodel，以證明Mul-Obj-Ga算法的性能優(yōu)劣。

實(shí)驗(yàn)?zāi)M平臺(tái)為一臺(tái)PC機(jī)，P4 2.8 GHz、1 GB內(nèi)存，Windows XP操作系統(tǒng)，在不運(yùn)行任何其他應(yīng)用程序下，采用Gridsim作為網(wǎng)格模擬器。在時(shí)間、可靠性、安全性維度和丟棄任務(wù)數(shù)指標(biāo)方面對(duì)算法進(jìn)行評(píng)價(jià)。實(shí)驗(yàn)方案：a)網(wǎng)格節(jié)點(diǎn)數(shù)相同，任務(wù)數(shù)不同對(duì)四個(gè)評(píng)價(jià)指標(biāo)進(jìn)行測(cè)試，節(jié)點(diǎn)數(shù)n=15個(gè)節(jié)點(diǎn)，任務(wù)數(shù)為500、1 000、2 000；b)網(wǎng)格節(jié)點(diǎn)不同，任務(wù)數(shù)相同對(duì)四個(gè)評(píng)價(jià)指標(biāo)進(jìn)行測(cè)試，節(jié)點(diǎn)數(shù)20、30、40，任務(wù)數(shù)為m=3 000。圖2時(shí)間維度上的測(cè)試統(tǒng)計(jì)結(jié)果；圖3為安全性維度上的測(cè)試統(tǒng)計(jì)結(jié)果；圖4為可靠性維度上的測(cè)試統(tǒng)計(jì)結(jié)果；圖5為丟棄任務(wù)數(shù)維度上的測(cè)試統(tǒng)計(jì)結(jié)果。

從時(shí)間維度上分析，從圖2可以看出Mul-Obj-Ga算法在時(shí)間效用值上最優(yōu)；Max-min算法最差，隨著任務(wù)數(shù)的增加，這一趨勢(shì)更為明顯，T-Sufferage算法的性能介于兩者之間。

從安全性維度上分析，從圖2可以看出Mul-Obj-Ga算法在安全性效用值上最優(yōu)，在任務(wù)數(shù)較小時(shí)，Max-min與T-Sufferage算法相差不大，隨著任務(wù)數(shù)增多，Max-min算法的劣勢(shì)更為明顯。

從可靠性維度上分析， Mul-Obj-Ga算法在時(shí)間效用值上最優(yōu)， Max-min算法最差，T-Sufferage算法的性能介于兩者之間，隨著任務(wù)數(shù)的和節(jié)點(diǎn)數(shù)的增加，這一趨勢(shì)更為明顯，如圖3所示。

從丟棄作業(yè)數(shù)上分析，T-Sufferage算法丟棄的作業(yè)最多，這是由該算法本身的啟發(fā)式調(diào)度思想決定的。同等條件下的Mul-Obj-Ga算法丟棄的作業(yè)數(shù)最少，三個(gè)算法都是隨著節(jié)點(diǎn)數(shù)的增多，而使丟棄的作業(yè)數(shù)減少。

4 結(jié)束語

針對(duì)網(wǎng)格計(jì)算中多目標(biāo)間存在沖突的獨(dú)立任務(wù)調(diào)度問題，應(yīng)用多目標(biāo)線性規(guī)劃對(duì)系統(tǒng)進(jìn)行建模，通過梯度上升法解決多目標(biāo)間的沖突度來確定各個(gè)目標(biāo)間的權(quán)重，本文提出該模型的預(yù)處理算法和任務(wù)調(diào)度算法。實(shí)驗(yàn)證明，該算法的綜合性能較優(yōu)于同類算法。下一步的研究?jī)?nèi)容是多約束依賴任務(wù)的調(diào)度策略。

參考文獻(xiàn)：

［1］

ABRAHAM A，BUYYA R，NATH B.Nature’s heuristics for scheduling jobs on computational grids[C]//Proc of the 8th Int’l Conf on Advanced Computing and Communications.New Delhi:Tata McGraw-Hill Publishing，2000:45-52.

[2]陳宏偉，王汝傳，韓光法.基于移動(dòng)代理網(wǎng)格計(jì)算中任務(wù)調(diào)度的研究[J].計(jì)算機(jī)應(yīng)用研究，2004，21（12）:45-46.

[3]BRAUN T D，SIEGEL H J，BECK N，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing，2001，61(6):810-837.

[4]FUJIMOTO N，HAGIHARA K.A comparison among grid scheduling algorithms for independent coarse-grained tasks[C]//Proc of Symp on Applications and the Internet-Workshops.Los Alamitos，CA:IEEE Computer Society Press，2004:674-680.

［5］ 張偉哲，方濱興，胡銘曾，等.基于信任QoS增強(qiáng)的網(wǎng)格服務(wù)調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(7):1157-1165.

[6]丁丁，羅四維，高瞻.網(wǎng)格環(huán)境下一種可調(diào)目標(biāo)的啟發(fā)式調(diào)度策略[J].計(jì)算機(jī)研究與發(fā)展，2007，44(9):1572-1578.

[7]張偉哲，胡銘曾，張宏莉，等.多QoS約束網(wǎng)格作業(yè)調(diào)度問題的多目標(biāo)演化算法[J].計(jì)算機(jī)研究與發(fā)展，2006，43(11):1855-1862.