采用遺傳-諧振算法求解網(wǎng)格依賴任務(wù)安全調(diào)度問(wèn)題

王洪峰，　朱　海

(1　華中科技大學(xué)　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，　湖北　武漢　430079;

2　周口師范學(xué)院　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，　河南　周口　466001)

?

采用遺傳-諧振算法求解網(wǎng)格依賴任務(wù)安全調(diào)度問(wèn)題

王洪峰1,2，朱海2

(1華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢430079;

2周口師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南周口466001)

摘要：針對(duì)異構(gòu)網(wǎng)格環(huán)境下任務(wù)調(diào)度面臨的安全性問(wèn)題，考慮網(wǎng)格節(jié)點(diǎn)的系統(tǒng)安全控制策略與歷史行為表現(xiàn)，構(gòu)建了網(wǎng)格節(jié)點(diǎn)安全評(píng)估模型，并在此基礎(chǔ)上提出了一種安全可信的網(wǎng)格依賴任務(wù)調(diào)度優(yōu)化模型。為求解該模型，結(jié)合遺傳算法全局尋優(yōu)能力較強(qiáng)的特性，同時(shí)克服其局部尋優(yōu)不足的缺點(diǎn)，引入諧振算法，從而設(shè)計(jì)了一種新的遺傳-諧振算法(GASHO)。首先,針對(duì)DAG任務(wù)圖基于啟發(fā)式思想設(shè)計(jì)遺傳進(jìn)化算子和量子諧振算子等操作以產(chǎn)生任務(wù)調(diào)度優(yōu)先隊(duì)列，解決離散解非法的問(wèn)題；然后,采用安全約束下的最早完成時(shí)間算子操作實(shí)現(xiàn)任務(wù)集到網(wǎng)格節(jié)點(diǎn)的映射，提高算法收斂效率；最后,對(duì)算法的時(shí)間復(fù)雜度和收斂性進(jìn)行分析證明。仿真實(shí)驗(yàn)結(jié)果表明，在同等條件下與同類算法相比，GASHO算法在收斂性、調(diào)度長(zhǎng)度、安全效益值等方面具有明顯的優(yōu)勢(shì)。 同理，網(wǎng)格資源節(jié)點(diǎn)可依據(jù)其采用的提取(Hash函數(shù))和身份認(rèn)證機(jī)制(如數(shù)字簽名技術(shù))的類型，得到節(jié)點(diǎn)完整性和真實(shí)性水平值分別為和。

關(guān)鍵詞:網(wǎng)格計(jì)算；依賴任務(wù)；安全調(diào)度；遺傳-諧振算法

MRsubjectclassification:68M20

網(wǎng)格以統(tǒng)一框架將互聯(lián)網(wǎng)中閑置的計(jì)算資源、存儲(chǔ)資源、網(wǎng)絡(luò)資源等組成一個(gè)超級(jí)計(jì)算系統(tǒng)[1]，為超大型復(fù)雜應(yīng)用任務(wù)提供計(jì)算服務(wù)。如何將計(jì)算任務(wù)調(diào)度配置到各類資源，使網(wǎng)格應(yīng)用系統(tǒng)獲得高性能成為研究的關(guān)鍵問(wèn)題之一。相對(duì)傳統(tǒng)任務(wù)調(diào)度，網(wǎng)格系統(tǒng)對(duì)任務(wù)調(diào)度策略提出了更高的要求[2-3]。近年來(lái)，該問(wèn)題吸引了不少學(xué)者的關(guān)注，如文獻(xiàn)[4]將安全因素融入同構(gòu)網(wǎng)格即時(shí)任務(wù)調(diào)度場(chǎng)景，但其尚未關(guān)注真實(shí)網(wǎng)格場(chǎng)景所體現(xiàn)的異構(gòu)與動(dòng)態(tài)等特征。文獻(xiàn)[5]在充分考慮網(wǎng)格節(jié)點(diǎn)動(dòng)態(tài)性的基礎(chǔ)上，借鑒社交網(wǎng)絡(luò)模型，融合歷史信譽(yù)度和自我評(píng)價(jià)信譽(yù)度兩個(gè)方面，建立節(jié)點(diǎn)信譽(yù)度評(píng)價(jià)機(jī)制，但沒(méi)有考慮網(wǎng)格資源節(jié)點(diǎn)本身的安全性。文獻(xiàn)[6]對(duì)網(wǎng)格資源信任機(jī)制和任務(wù)調(diào)度機(jī)制相互分離的不足提出了建設(shè)性意見，但沒(méi)有量化網(wǎng)格資源安全信任值，要在網(wǎng)格具體應(yīng)用環(huán)境中實(shí)施，還需進(jìn)一步研究。另外，網(wǎng)格調(diào)度研究主要針對(duì)元任務(wù)的簡(jiǎn)化應(yīng)用場(chǎng)景[7-11]，限制了網(wǎng)格應(yīng)用場(chǎng)景。本文針對(duì)網(wǎng)格環(huán)境靜態(tài)依賴任務(wù)調(diào)度問(wèn)題，結(jié)合網(wǎng)格節(jié)點(diǎn)歷史行為信譽(yù)度(動(dòng)態(tài)信譽(yù)度)和自我認(rèn)知信譽(yù)度(靜態(tài)信譽(yù)度)兩個(gè)方面，建立網(wǎng)格用戶任務(wù)模型和資源節(jié)點(diǎn)拓?fù)淠Ｐ?，并基于此提出網(wǎng)格可信調(diào)度優(yōu)化模型。該模型將網(wǎng)格系統(tǒng)任務(wù)調(diào)度長(zhǎng)度性能、安全性能等需求結(jié)合起來(lái)，使網(wǎng)格任務(wù)調(diào)度在滿足任務(wù)依賴關(guān)系的前提下，任務(wù)調(diào)度長(zhǎng)度和安全效益值達(dá)到最優(yōu)。

網(wǎng)格具有很多區(qū)別于其他分布式并行計(jì)算系統(tǒng)的特征，其任務(wù)調(diào)度模型相對(duì)比較復(fù)雜[12-16]。例如張偉哲等人建立了多目標(biāo)約束的網(wǎng)格任務(wù)調(diào)度模型，基于多目標(biāo)最優(yōu)化理論及現(xiàn)代智能算法，設(shè)計(jì)并提出了一種多Qos約束[17]的網(wǎng)格任務(wù)調(diào)度算法[16]，從時(shí)間、可靠性和安全性三個(gè)維度仿真網(wǎng)格計(jì)算環(huán)境及任務(wù)調(diào)度，并取得預(yù)期效果，但該算法中并未明確給出安全性、可靠性等量化定義。Xu等人針對(duì)異構(gòu)計(jì)算系統(tǒng)中依賴任務(wù)調(diào)度問(wèn)題，基于啟發(fā)式遺傳算法生成任務(wù)調(diào)度優(yōu)先次序，同時(shí)采用EFT算法實(shí)現(xiàn)任務(wù)到網(wǎng)格的節(jié)點(diǎn)映射，對(duì)實(shí)時(shí)網(wǎng)格依賴任務(wù)調(diào)度具有較好的調(diào)度效果[18]，但文章僅考慮了調(diào)度長(zhǎng)度要素，未考慮安全等因素。Yalda等人針對(duì)異構(gòu)分布式計(jì)算系統(tǒng)中的動(dòng)態(tài)依賴任務(wù)調(diào)度問(wèn)題，設(shè)計(jì)并提出了HSGA算法[19]，該算法通過(guò)任務(wù)優(yōu)先評(píng)價(jià)函數(shù)確定任務(wù)優(yōu)先隊(duì)列，同時(shí)考慮調(diào)度長(zhǎng)度、調(diào)度失敗率和負(fù)載均衡等性能指標(biāo)，建立調(diào)度方案評(píng)估函數(shù)，融合啟發(fā)式和遺傳算法完成任務(wù)調(diào)度，仿真結(jié)果證明該算法在系統(tǒng)綜合性能指標(biāo)方面具有優(yōu)勢(shì)，但也未融入安全性因素。本文針對(duì)具有依賴關(guān)系的網(wǎng)格任務(wù)調(diào)度問(wèn)題，提出了一種新的遺傳-諧振算法。該算法在實(shí)數(shù)編碼的基礎(chǔ)上，基于啟發(fā)式遺傳算法思想重新設(shè)計(jì)改進(jìn)了遺傳算子，同時(shí)將遺傳算法的結(jié)果作為諧振算法初始參數(shù)進(jìn)行局部尋優(yōu)，提高搜索精度，最后對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)，其結(jié)果表明該算法具有較好的綜合性能。

1網(wǎng)格節(jié)點(diǎn)安全模型

網(wǎng)格節(jié)點(diǎn)安全性主要包括身份安全與行為安全兩個(gè)方面。身份安全主要衡量網(wǎng)格節(jié)點(diǎn)的安全性，即對(duì)信息保密性、完整性、真實(shí)性等屬性的支持度[20]，行為安全則主要衡量網(wǎng)格用戶對(duì)節(jié)點(diǎn)的評(píng)價(jià)。

定義1節(jié)點(diǎn)保密水平度量。假定網(wǎng)格系統(tǒng)限定采用加密算法類型N，則可通過(guò)理論分析與仿真實(shí)驗(yàn)得出每種加密算法的執(zhí)行性能Pi，加密算法的最差性能為Pb，則可定義節(jié)點(diǎn)保密水平值為

(1)

定義2節(jié)點(diǎn)的安全效益。若僅考慮網(wǎng)格保密性、真實(shí)性、完整性等性能，則網(wǎng)格節(jié)點(diǎn)ru的安全值RS(ru)可通過(guò)如下公式計(jì)算：

(2)

(2)式中ω1、ω2、ω3代表不同安全性能的權(quán)重。

網(wǎng)格節(jié)點(diǎn)在調(diào)度系統(tǒng)中的可信度直接影響網(wǎng)格調(diào)度系統(tǒng)的效率。本文借鑒社交網(wǎng)絡(luò)安全信任機(jī)制，依據(jù)網(wǎng)格節(jié)點(diǎn)的歷史服務(wù)行為表現(xiàn)優(yōu)劣來(lái)確定其安全可信度。

定義3節(jié)點(diǎn)可信度度量。用來(lái)定義網(wǎng)格節(jié)點(diǎn)的可信賴程度，該度量標(biāo)準(zhǔn)主要由網(wǎng)格資源提供者節(jié)點(diǎn)靜態(tài)評(píng)估PS(ru)和歷史行為評(píng)估PD(ru)，網(wǎng)格節(jié)點(diǎn)的可信度PC(ru)可由公式定義：

PC(ru)=PS(ru)+PD(ru)。

(3)

靜態(tài)評(píng)估值PS(ru)主要受網(wǎng)格節(jié)點(diǎn)的安全水平RS(ru)、計(jì)算性能RP(ru)、可持續(xù)服務(wù)能力RC(ru)等因素影響，可由如下公式來(lái)定義：

PS(ru)=α·RS(ru)+β·RP(ru)+γ·e-RC(ru)。

(4)

公式中，α、β、γ表示權(quán)重系數(shù)，計(jì)算性能RP(ru)是依據(jù)實(shí)驗(yàn)測(cè)試網(wǎng)格節(jié)點(diǎn)執(zhí)行不同類型任務(wù)的綜合能力評(píng)價(jià)值，可持續(xù)服務(wù)能力RC(ru)是網(wǎng)格節(jié)點(diǎn)平均執(zhí)行時(shí)長(zhǎng)。

動(dòng)態(tài)評(píng)估值PD(ru)主要受網(wǎng)格任務(wù)調(diào)度成功率AW(ru)、累計(jì)使用率AU(ru)、綜合信任評(píng)價(jià)值A(chǔ)C(ru)等影響，可由如下公式定義：

PD(ru)=δ·AW(ru)+φ·AU(ru)+

θ·AC(ru)。

(5)

其中δ、φ、θ表示權(quán)重系數(shù)，AW(ru)代表網(wǎng)格節(jié)點(diǎn)i得到調(diào)度后，累計(jì)執(zhí)行成功次數(shù)占總調(diào)度次數(shù)的比率，反映了網(wǎng)格節(jié)點(diǎn)的穩(wěn)定性；AU(ru)代表網(wǎng)格節(jié)點(diǎn)成功執(zhí)行任務(wù)總時(shí)長(zhǎng)/網(wǎng)格待機(jī)服務(wù)總時(shí)長(zhǎng)，反映了網(wǎng)格節(jié)點(diǎn)的可用性；AC(ru)代表網(wǎng)格節(jié)點(diǎn)ru累計(jì)執(zhí)行任務(wù)獲得的信任評(píng)價(jià)，包含平均執(zhí)行長(zhǎng)度、安全匹配情況和信譽(yù)度等因素，具體計(jì)算可參照文獻(xiàn)[21]。

定義4節(jié)點(diǎn)安全模型。節(jié)點(diǎn)安全模型由節(jié)點(diǎn)安全效益和節(jié)點(diǎn)可信度組合而成，代表了該節(jié)點(diǎn)安全的綜合效益值，若將任務(wù)ti分配到網(wǎng)格節(jié)點(diǎn)ru，則該任務(wù)執(zhí)行時(shí)獲取的安全總效益值可由下列公式計(jì)算：

Q(ti,ru)=μ1·RS(ti,ru)+μ2·PC(ti,ru),

(6)

式中μ1、μ2分別代表屬性安全和行為安全的權(quán)重，而RS(ti,ru)和PC(ti,ru)可在任務(wù)ti固定的情況下分別由公式(2)和(3)計(jì)算獲得。

2網(wǎng)格依賴任務(wù)調(diào)度模型

2.1　網(wǎng)格資源與任務(wù)表示模型

具體來(lái)說(shuō)，網(wǎng)格計(jì)算就是將一個(gè)大任務(wù)依據(jù)某種標(biāo)準(zhǔn)劃分為N個(gè)子任務(wù)，然后將子任務(wù)按照某種策略調(diào)度到網(wǎng)格節(jié)點(diǎn)執(zhí)行，最后匯總各節(jié)點(diǎn)執(zhí)行結(jié)果形成最終結(jié)果。網(wǎng)格依賴任務(wù)模型[9]一般采用有向無(wú)環(huán)圖(DAG)來(lái)表示，它是根據(jù)劃分后的具有數(shù)據(jù)約束關(guān)系的網(wǎng)格任務(wù)業(yè)務(wù)處理流程建立的任務(wù)模型。DAG圖中節(jié)點(diǎn)表示網(wǎng)格任務(wù)劃分后的子任務(wù)，有向邊表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系。頂點(diǎn)的權(quán)值表示網(wǎng)格應(yīng)用子任務(wù)的屬性，如計(jì)算量和安全需求，而邊的權(quán)值包括節(jié)點(diǎn)間的依賴關(guān)系，如通信數(shù)據(jù)傳輸量、數(shù)據(jù)在網(wǎng)格環(huán)境傳輸時(shí)的安全需求等。具體的網(wǎng)格任務(wù)圖表示模型如圖1所示。

圖1　一個(gè)網(wǎng)格依賴任務(wù)圖模型Fig.1　An　example　of　dependent　tasks　graph　model　in　grid

在DAG圖中，沒(méi)有父節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)稱為根節(jié)點(diǎn)，沒(méi)有孩子的任務(wù)節(jié)點(diǎn)稱為終端節(jié)點(diǎn)。若圖中存在多個(gè)根節(jié)點(diǎn)，則可通過(guò)虛擬節(jié)點(diǎn)和無(wú)依賴關(guān)系的邊將其轉(zhuǎn)換為單入口圖。同理,也可將多終端節(jié)點(diǎn)的圖轉(zhuǎn)換為單出口圖。任意任務(wù)節(jié)點(diǎn)的執(zhí)行，必須在其所有父節(jié)點(diǎn)結(jié)果信息到達(dá)之后才能開始。

定義5依賴任務(wù)需求表示模型。依賴任務(wù)模型可表示為三維向量TD=(V,E,W),V是頂點(diǎn)集合，ti表示第i個(gè)子任務(wù)，|V|表示子任務(wù)的個(gè)數(shù)；E為邊的集合且滿足條件E={eti,j|ti∈V,tj∈V,i≠j},描述子任務(wù)之間的數(shù)據(jù)依賴關(guān)系集合；W為頂點(diǎn)權(quán)值集合，由Wti=(ati,sti)表示，ati和sti分別代表網(wǎng)格子任務(wù)ti的計(jì)算量和安全需求。

定義6網(wǎng)格資源表示模型。本文所研究的異構(gòu)網(wǎng)格模型可由集合R={ru|u∈[0,m)}表示，對(duì)任一網(wǎng)格節(jié)點(diǎn)為一個(gè)三元組ru=(δu,ρu,τu)，其中δu代表節(jié)點(diǎn)的計(jì)算能力，ρu表示節(jié)點(diǎn)的安全服務(wù)向量，τu代表網(wǎng)格節(jié)點(diǎn)的可持續(xù)服務(wù)能力。

2.2　可信依賴任務(wù)調(diào)度優(yōu)化模型

基于網(wǎng)格資源與任務(wù)的建模表示，網(wǎng)格任務(wù)調(diào)度策略可體現(xiàn)為任務(wù)-資源映射圖[2](如圖2所示)。

定義7網(wǎng)格任務(wù)-資源映射方案。網(wǎng)格任務(wù)資源分配映射圖可以用一個(gè)向量TRG={l0,l1,…,l|V|}表示，其中l(wèi)x={(ti,ru)|0≤i<|V|,0≤u

圖2　網(wǎng)格任務(wù)-資源分配圖模型Fig.2　Scheduling　graph　model　for　mapping　tasks　to　grid　nodes

定義8任務(wù)調(diào)度安全評(píng)估函數(shù)。該函數(shù)用來(lái)評(píng)價(jià)網(wǎng)格用戶應(yīng)用任務(wù)執(zhí)行安全滿意度，可由下式獲得：

(7)

很明顯，S(Gk)∈(0,1),另Q(ti,ru)可由(6)式計(jì)算獲取，Xiu是任務(wù)到資源的映射矩陣，為決策變量，即當(dāng)任務(wù)ti分配到資源ru上執(zhí)行則Xiu為1，否則為0。

定義9任務(wù)調(diào)度長(zhǎng)度評(píng)價(jià)標(biāo)準(zhǔn)。任務(wù)調(diào)度長(zhǎng)度TL(Gk)是指從網(wǎng)格任務(wù)開始執(zhí)行時(shí)刻到最后一個(gè)子任務(wù)在網(wǎng)格系統(tǒng)中執(zhí)行完成時(shí)刻之間的時(shí)間間隔，主要由任務(wù)的等待時(shí)間twti,ru、執(zhí)行時(shí)間teti,ru和獲取安全效益所花費(fèi)時(shí)間tsti,ru組成(暫不考慮網(wǎng)格節(jié)點(diǎn)其他時(shí)間代價(jià)，如通信時(shí)間代價(jià)等)，可由下式描述：

TL(Gk)=twti,ru+teti,ru+tsti,ru。

(8)

顯然，DAG圖中出口任務(wù)節(jié)點(diǎn)一定是調(diào)度長(zhǎng)度最長(zhǎng)的，DAG圖深度為m，則可通過(guò)每一層最長(zhǎng)調(diào)度的遞歸求和獲得出口節(jié)點(diǎn)的等待時(shí)間twti,ru，而teti,ru和tsti,ru可通過(guò)公式(9)和(10)計(jì)算獲得。

tei,u=ati/δru,

(9)

(10)

其中，(10)式計(jì)算方法可查閱文獻(xiàn)[22]。

定義10網(wǎng)格可信調(diào)度優(yōu)化模型。本文網(wǎng)格可信調(diào)度優(yōu)化目標(biāo)是尋找依賴任務(wù)描述模型到網(wǎng)格節(jié)點(diǎn)模型之間的映射，使得網(wǎng)格系統(tǒng)執(zhí)行任務(wù)時(shí)調(diào)度長(zhǎng)度最短的同時(shí)，用戶獲得盡可能安全的網(wǎng)格執(zhí)行環(huán)境。其數(shù)學(xué)模型表示如下：

min(Z)=w1·TL(Gk)+w2(1-S(Gk)),

(11)

f(tj,rv)-f(ti,ru)≥a(tj)/δ(rv)+ts(tj,rv)。

在(11)式中，Z={z1,z2,…,zk},zk為第k個(gè)分配調(diào)度方案，即任務(wù)到資源的映射方案；TL(Gk)和S(Gk)為網(wǎng)格任務(wù)的調(diào)度長(zhǎng)度和安全總效益值，可分別由(8)式和(7)式獲得；w1、w2為調(diào)度長(zhǎng)度與安全效益值的重要性權(quán)重，根據(jù)任務(wù)特性，適當(dāng)調(diào)整權(quán)重wk(k=1,2)，對(duì)任意目標(biāo)進(jìn)行重新優(yōu)化以滿足不同網(wǎng)格用戶的傾向性需求。

3遺傳-諧振算法設(shè)計(jì)

遺傳算法和模擬諧振算法[23]都是指數(shù)級(jí)信息處理而提出的智能算法。遺傳算法以全局并行搜索能力較強(qiáng)而著稱，但卻存在局部搜索能力較差等問(wèn)題，容易陷入局部最優(yōu)解。1994年，Rudolph詳細(xì)分析了該現(xiàn)象的原因：遺傳算法主要體現(xiàn)的是進(jìn)化過(guò)程中父代和子代之間的繼承和延續(xù)關(guān)系，可能存在不理想的組合，導(dǎo)致最終無(wú)法產(chǎn)生理想解。諧振操作具有較強(qiáng)的局部搜索能力，且收斂速度極快，但是卻很難準(zhǔn)確確定諧振系統(tǒng)的運(yùn)行參數(shù)(一般是隨機(jī)或者經(jīng)驗(yàn)確定)，從而影響解的質(zhì)量。從算法運(yùn)行機(jī)理上來(lái)看，兩種算法互補(bǔ)性高。

因此，針對(duì)網(wǎng)格依賴任務(wù)調(diào)度NP難問(wèn)題，本文充分利用遺傳算法的宏觀并行全局尋優(yōu)能力，提高收斂速度；同時(shí)引入諧振操作增加種群個(gè)體的多樣性以及提高局部尋優(yōu)能力，以獲得盡可能接近問(wèn)題最優(yōu)解的Pareto最優(yōu)解，提高收斂質(zhì)量。

3.1　解質(zhì)量評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)主要用來(lái)評(píng)估新解優(yōu)劣以決定取舍。針對(duì)本文異構(gòu)網(wǎng)格依賴任務(wù)可信調(diào)度問(wèn)題，采用可信調(diào)度優(yōu)化模型中的適應(yīng)度評(píng)估函數(shù)，基于高效低能時(shí)間復(fù)雜度EFT(EarliestFinishTime)算法，實(shí)現(xiàn)任務(wù)到網(wǎng)格節(jié)點(diǎn)的映射(由于本文引入安全要素，因此將基于EFT的算法稱為安全約束下的EFT算法，簡(jiǎn)稱SEFT)。網(wǎng)格系統(tǒng)依據(jù)歷史行為等信息實(shí)時(shí)維護(hù)網(wǎng)格節(jié)點(diǎn)安全綜合效益值，并按照降序排列得到網(wǎng)格節(jié)點(diǎn)序列RQ。具體任務(wù)節(jié)點(diǎn)映射到網(wǎng)格節(jié)點(diǎn)的算法如下：

算法1.任務(wù)-網(wǎng)格節(jié)點(diǎn)映射及效益評(píng)估算法SEFT

輸入：任務(wù)調(diào)度優(yōu)先隊(duì)列

輸出：最優(yōu)和最差的任務(wù)調(diào)度方案及其效益值

Step1while調(diào)度隊(duì)列SQ=?，do

Step2取隊(duì)首任務(wù)t(i)，并從SQ中移除t(i)；

Step3針對(duì)RQ隊(duì)列的每一網(wǎng)格節(jié)點(diǎn)r(u)，依次計(jì)算t(i)分配r(u)上的可信調(diào)度優(yōu)化的綜合效益值，獲取Min(Z)與Max(Z)；

Step4基于Min(Z)與Max(Z)值，分別將任務(wù)t(i)分配到網(wǎng)格節(jié)點(diǎn)rmin(u)rmax(u)，并記錄到映射方案GoodMap、BadMap；

Step5endwhile

Step6返回GoodMap、BadMap、Min(Z)、Max(Z)。

3.2　初始種群生成

依據(jù)算法步驟概述，初始種群主要任務(wù)是產(chǎn)生符合任務(wù)依賴關(guān)系的任務(wù)調(diào)度序列。為便于解碼，染色體編碼采用任務(wù)序號(hào)定長(zhǎng)組合編碼。為生成符合條件的初始解群體，首先將應(yīng)用網(wǎng)格任務(wù)圖(DAG)中的所有子任務(wù)節(jié)點(diǎn)按深度值劃分成h層，第i層中的子任務(wù)構(gòu)成集合DAG(i),0≤i

算法2.初始化種群InitPopulation

輸入：依賴任務(wù)關(guān)系約束圖DAG

輸出：生成初始種群Pop[PopSize]

Step1依據(jù)任務(wù)關(guān)系約束圖按照深度值生成DAG(i)任務(wù)集合；

Step2PopNo=1

Step3whilePopNo

Step4fori=0;i

Step5針對(duì)DAG[i]中的所有任務(wù)，隨機(jī)生成一個(gè)序列進(jìn)行編碼，并將編碼值追加到Pop[PopNo]編碼后邊；

Step6i++；

Step7endfor

Step8PopNo=PopNo+1；

Step9endwhile

Step10return初始化種群Pop[Popsize]。

3.3　算子設(shè)計(jì)

3.3.1遺傳交叉算子設(shè)計(jì)遺傳算法的優(yōu)越性能主要取決于交叉算子設(shè)計(jì)。本文借鑒文獻(xiàn)[24-25]采用啟發(fā)式單點(diǎn)交叉原則實(shí)現(xiàn)交叉操作，既保證了任務(wù)依賴關(guān)系，也保證了交叉操作的正確性。啟發(fā)式交叉的正確性原則：針對(duì)已有的任務(wù)調(diào)度序列，任意刪除部分任務(wù)節(jié)點(diǎn)不影響原調(diào)度隊(duì)列中任務(wù)節(jié)點(diǎn)間的依賴關(guān)系。具體交叉操作實(shí)現(xiàn)算法如下：

算法3.交叉操作

輸入：雙親個(gè)體編碼Fa、Ma

輸出：交叉后的兩個(gè)子個(gè)體編碼C1、C2

Step1隨機(jī)產(chǎn)生雙親交叉位p∈(1,|V|)；

Step2以交叉位p為斷點(diǎn)，將父?jìng)€(gè)體Fa和Ma分別分割為前后段，具體表示為Fa_L、Fa_R、Ma_L、Ma_R；

Step3針對(duì)子個(gè)體C1：從Ma的任務(wù)基因組合中刪除Fa_L包含的任務(wù)基因生成Ma′；將Fa_L和Ma′合并構(gòu)成C1基因；

Step4針對(duì)子個(gè)體C2：從Fa的任務(wù)基因組合中刪除Ma_L包含的任務(wù)基因生成Fa′；將Ma_L和Fa′合并構(gòu)成C2基因；

Step5returnC1，C2。

3.3.2遺傳變異算子設(shè)計(jì)通過(guò)突變因子，遺傳算法一方面可使種群結(jié)構(gòu)多樣，另一方面可跳出局部最優(yōu)解，并加速向全局最優(yōu)解收斂。本文為保證變異操作產(chǎn)生解的合法性，只需要DAG任務(wù)圖中任意子任務(wù)進(jìn)行變異操作后滿足條件：某子任務(wù)節(jié)點(diǎn)在新解中的相對(duì)位置不能置于其所有前驅(qū)節(jié)點(diǎn)之前，也不能置于其所有后繼節(jié)點(diǎn)之后。在該條件下，變化任意兩個(gè)子節(jié)點(diǎn)的位置都是合法的調(diào)度。因此本文采用啟發(fā)式變異算子實(shí)現(xiàn)變異操作，即針對(duì)染色體中的任意變異點(diǎn)q，向前搜索第一個(gè)前驅(qū)節(jié)點(diǎn)pri(q)，其位置為pq；向后搜索第一個(gè)后繼節(jié)點(diǎn)suc(q)，其位置為sq；則在(pq，sq)之間任意選擇一個(gè)位置都可與q進(jìn)行交換實(shí)現(xiàn)個(gè)體變異操作，且不會(huì)因?yàn)樽儺惒僮鞲淖內(nèi)蝿?wù)依賴關(guān)系。具體變異操作實(shí)現(xiàn)算法如算法4所示：

算法4.變異操作

輸入：父?jìng)€(gè)體Fa

輸出：子個(gè)體Child

Step1隨機(jī)選擇1個(gè)任務(wù)基因位pos；

Step2從pos+1開始直到|V|，查找t(pos)的第一個(gè)后繼節(jié)點(diǎn)位置late_pos；若沒(méi)有，則late_pos=pos；

Step3從pos-1開始逐步遞減至1，查找t(pos)的第一個(gè)前驅(qū)節(jié)點(diǎn)位置pror_pos；若沒(méi)有找到，則pror_pos=pos；

Step4在[pror_pos+1，late_pos-1]之間產(chǎn)生隨機(jī)整數(shù)rand_pos≠pos；

Step5交換pos和rand_pos位置的任務(wù)基因信息，產(chǎn)生新個(gè)體Child；

Step6returnChild。

3.3.3諧振算子設(shè)計(jì)

(1)模擬諧振算法的基本流程

模擬諧振算法(SHO)即仿生物理學(xué)中簡(jiǎn)諧振動(dòng)原理搜索問(wèn)題最優(yōu)解的現(xiàn)代智能啟發(fā)式算法。若將諧振系統(tǒng)運(yùn)動(dòng)點(diǎn)的位置坐標(biāo)映射問(wèn)題的解，振幅映射為解空間，采用系統(tǒng)的彈性勢(shì)能作為適應(yīng)度評(píng)價(jià)函數(shù)F，諧振基態(tài)(勢(shì)能為0)映射為問(wèn)題的最優(yōu)解。模擬諧振算法具體流程請(qǐng)參閱文獻(xiàn)[26]。

(2)諧振算子設(shè)計(jì)

諧振算法具有較強(qiáng)的搜索能力，但由于無(wú)法準(zhǔn)確確定平衡點(diǎn)和端點(diǎn)等參數(shù)，從而影響解的質(zhì)量與收斂速度。因此，首先將遺傳算法獲取的最優(yōu)解和最差解作為諧振算法的平衡點(diǎn)和端點(diǎn)，消除初始解的隨意性或人為因素，然后基于諧振算法進(jìn)行解尋優(yōu)，具體算法流程如下：

算法5.諧振操作算子

輸入：GA的最優(yōu)解、最差解的調(diào)度方案及其效益值

輸出：最優(yōu)調(diào)度方案及其效益值

Step1系統(tǒng)運(yùn)行基本參數(shù)的初始化：將遺傳算法運(yùn)行獲得的最優(yōu)解和最劣解及其作為諧振系統(tǒng)的平衡點(diǎn)f(Init)和端點(diǎn)f(End)；將計(jì)算資源的數(shù)目乘以任務(wù)的數(shù)量作為諧振系統(tǒng)的振幅A和初始步長(zhǎng)L0(系統(tǒng)的能級(jí))、基態(tài)步長(zhǎng)Ls取值為2；

Step2f(s)=f(Init)；

Step3首先采用2-opt產(chǎn)生新解s′，步長(zhǎng)L∈[Ls,L0]，計(jì)算適應(yīng)度函數(shù)增量Δf=f(s′)-f(s)；若Δf≤0，則接受新解s′為當(dāng)前解，并記憶最小解；若Δf>0，且(Ls/L0)2-Δf/(f(End)-f(s))≥0，則接受新解s′為當(dāng)前解，否則拋棄此新解[27]；變化當(dāng)前步長(zhǎng)L，循環(huán)執(zhí)行本步驟直到完成指定的計(jì)算步驟；

Step4量子諧振操作階段：步長(zhǎng)范圍為L(zhǎng)∈[1,Ls]，采用隨機(jī)插入法(步長(zhǎng)為1)產(chǎn)生新解；接受準(zhǔn)則為：若Δf≥0，則接受新解s′為當(dāng)前解，否則不接受；直至滿足局部搜索終止策略；

Step5打印當(dāng)前最優(yōu)解并退出算法。

3.4　算法流程描述

本文的遺傳諧振算法(GASHO)總框架如下：(1)依據(jù)DAG任務(wù)圖中的數(shù)據(jù)依賴關(guān)系，基于啟發(fā)式思想設(shè)計(jì)遺傳進(jìn)化算子和諧振算子等操作，產(chǎn)生不同的任務(wù)調(diào)度隊(duì)列，提高搜索能力和搜索精度；(2)基于HEFT算法思想[27]，采用安全約束下的最早完成時(shí)間算子操作，實(shí)現(xiàn)任務(wù)集到網(wǎng)格節(jié)點(diǎn)的映射，提高算法收斂速度和調(diào)度性能。GASHO算法流程如圖3所示。

圖3　GASHO算法流程圖Fig.3　Algorithm　flow　chart　of　GASHO

3.5　算法收斂性分析

定理1(全局收斂性)算法以概率1收斂到問(wèn)題的全局最優(yōu)解。

證明(1)在算法中，對(duì)于任意兩個(gè)個(gè)體p和q，q可由p通過(guò)進(jìn)化生成。

假設(shè)個(gè)體w=(w1,w2,…,wn)是由p=(p1,p2，…，pn)通過(guò)進(jìn)化作用產(chǎn)生的任一后代，由進(jìn)化過(guò)程可知，從pi產(chǎn)生wi的概率為1/(n-1)，由此可得

P{E(p)=w}=(n-1)-1(n-1)-1…

(n-1)-1=(n-1)-n>0。

由于個(gè)體參與進(jìn)化的概率，則個(gè)體通過(guò)基因更新產(chǎn)生個(gè)體的概率為

P{E(p)=q}≥P(E(p)=w)·P(E(w)=q)=

pg·(n-1)-n>0。

即對(duì)于可行解空間Q中任意兩個(gè)個(gè)體p和q，q可由p進(jìn)化所得。

(2)由GASHO算法的解個(gè)體更新過(guò)程可知，X(0)，X(1)，…，X(k)是單調(diào)的，即滿足?t，有

min{f(x)|x∈X(t+1)}≤

min{f(x)|x∈X(t)}。

因此，由證明(1)和(2)可知，GASHO算法以概率1收斂到依賴任務(wù)可信調(diào)度問(wèn)題的最優(yōu)解。

3.6　算法時(shí)間復(fù)雜度分析

設(shè)m為網(wǎng)格節(jié)點(diǎn)數(shù)目，n為DAG圖中任務(wù)總數(shù)，遺傳算法種群個(gè)數(shù)為p，迭代次數(shù)為q，諧振過(guò)程的迭代次數(shù)為r。本算法的時(shí)間復(fù)雜度計(jì)算主要包括遺傳過(guò)程和諧振過(guò)程兩個(gè)部分。GA種群初始化的時(shí)間復(fù)雜度為o(np)；遺傳交叉和變異算子都是針對(duì)種群中的個(gè)體進(jìn)行基因的遍歷操作，因此時(shí)間復(fù)雜度為o(np)；評(píng)價(jià)函數(shù)基于EFT算法，其時(shí)間復(fù)雜度為o(mn)；故遺傳過(guò)程的總時(shí)間復(fù)雜度為o(npq+mn)。由于諧振算法主要是針對(duì)1個(gè)解不斷進(jìn)化，其算法時(shí)間復(fù)雜度主要和進(jìn)化過(guò)程(主要是評(píng)價(jià)函數(shù)計(jì)算)和進(jìn)化次數(shù)相關(guān)，其時(shí)間復(fù)雜度為o(rmn)。因此，本算法的總體時(shí)間復(fù)雜度為o(mnp+npq+rmn)。

4仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的GASHO算法的效性，首先采用VMWarevSphere5.0將4臺(tái)IBMSystemx3850X5(每臺(tái)8顆CPU，每顆CPU8核心，內(nèi)存256GB)、1臺(tái)IBMDS5020光纖存儲(chǔ)(8GB光纖數(shù)據(jù)帶寬、20TB存儲(chǔ)容量)、萬(wàn)兆內(nèi)部光纖網(wǎng)絡(luò)等資源組建成集群。其次基于Java語(yǔ)言設(shè)計(jì)開發(fā)了網(wǎng)格仿真實(shí)驗(yàn)平臺(tái)，該平臺(tái)由組件GridProc、TaskProc和GridManager組成。其中組件GridProc主要負(fù)責(zé)模擬生成網(wǎng)格環(huán)境，具體依據(jù)設(shè)定的網(wǎng)格性能集合、網(wǎng)格安全策略效益集合(仿真環(huán)境網(wǎng)格節(jié)點(diǎn)安全值分布于{0.2，0.4，0.5，0.6，0.8，1.0})等隨機(jī)產(chǎn)生具有不同性能、不同安全策略的網(wǎng)格資源節(jié)點(diǎn)；組件TaskProc主要依據(jù)用戶需求生成計(jì)算量不同、安全水平要求不同的具有依賴關(guān)系的任務(wù)集合；GridManager則負(fù)責(zé)網(wǎng)格任務(wù)調(diào)度管理工作。下面分別從算法的收斂性能、任務(wù)的調(diào)度長(zhǎng)度、安全效益等指標(biāo)進(jìn)行仿真實(shí)驗(yàn)，并將結(jié)果與SEFT算法、GA算法進(jìn)行對(duì)比分析。

4.1　算法的收斂性分析

為比較算法的收斂性，圖4給出了算法在60個(gè)網(wǎng)格節(jié)點(diǎn)、500個(gè)任務(wù)在500代迭代過(guò)程中的調(diào)度長(zhǎng)度變化曲線。由于SEFT算法是啟發(fā)式算法，圖中顯示了GA算法和GASHO算法的收斂性。

圖4　GASHO和GA算法收斂性比較Fig.4　Convergence　comparison　between　GAalgorithm　and　GASHO　algorithm

由于GA算法和GASHO算法初始種群都是采用由啟發(fā)式算法產(chǎn)生的同一種群，因此圖4中曲線起始點(diǎn)相同，算法初始運(yùn)行階段，兩類算法性能表現(xiàn)不相上下，但隨著進(jìn)化代數(shù)的增加，GASHO算法優(yōu)勢(shì)充分體現(xiàn)出來(lái)，其收斂速度和調(diào)度長(zhǎng)度都明顯優(yōu)于GA算法。

4.2　隨機(jī)產(chǎn)生任務(wù)DAG圖

為了進(jìn)一步驗(yàn)證GASHO算法針對(duì)隨機(jī)DAG任務(wù)圖的調(diào)度性能，從兩個(gè)方面進(jìn)行了仿真：(1)任務(wù)數(shù)量固定但網(wǎng)格節(jié)點(diǎn)規(guī)模可變；(2)任務(wù)數(shù)量可變但網(wǎng)格節(jié)點(diǎn)規(guī)模固定。

(1)任務(wù)數(shù)量固定但網(wǎng)格節(jié)點(diǎn)規(guī)模可變。

為了驗(yàn)證算法的有效性和任務(wù)的多樣性，實(shí)驗(yàn)隨機(jī)產(chǎn)生了規(guī)模為200的DAG圖共20組，并通過(guò)GridProc隨機(jī)產(chǎn)生了規(guī)模為20、40、60、80、100、120、140、160的網(wǎng)格環(huán)境，每組網(wǎng)格環(huán)境的計(jì)算性能和安全策略都有所不同。實(shí)驗(yàn)針對(duì)同一網(wǎng)格環(huán)境下20組DAG圖的調(diào)度效果進(jìn)行均值分析，具體實(shí)驗(yàn)效果如圖5所示。

從圖5(a)中可以看出，在任務(wù)規(guī)模一定的情況下，隨著網(wǎng)格節(jié)點(diǎn)規(guī)模的增加，任務(wù)調(diào)度長(zhǎng)度都呈遞減趨勢(shì)，尤其是當(dāng)網(wǎng)格節(jié)點(diǎn)數(shù)量較多時(shí)，調(diào)度長(zhǎng)度性能幾乎不分上下，這主要是因?yàn)殡S著網(wǎng)格節(jié)點(diǎn)數(shù)量的增加，在滿足安全策略要求的前提下，任務(wù)在調(diào)度時(shí)可選擇性能更好的網(wǎng)格節(jié)點(diǎn)執(zhí)行，降低了調(diào)度長(zhǎng)度，且總體來(lái)說(shuō)GASHO算法的調(diào)度長(zhǎng)度性能最好，尤其是任務(wù)數(shù)量相對(duì)網(wǎng)格節(jié)點(diǎn)數(shù)量較多時(shí)。從圖5(b)看出，隨著網(wǎng)格節(jié)點(diǎn)的增加，安全效益值都有所增加，這主要是網(wǎng)格節(jié)點(diǎn)數(shù)相對(duì)任務(wù)的并行度達(dá)到一定的倍數(shù)時(shí)，任務(wù)對(duì)網(wǎng)格節(jié)點(diǎn)的競(jìng)爭(zhēng)趨緩。但是，同等條件下GASHO算法的安全效益值相對(duì)較穩(wěn)定，而SEFT算法的安全效益值提升幅度更明顯。

(2)網(wǎng)格節(jié)點(diǎn)固定但任務(wù)數(shù)量可變。

實(shí)驗(yàn)隨機(jī)產(chǎn)生了60個(gè)異構(gòu)網(wǎng)格節(jié)點(diǎn)，并通過(guò)TaskProc隨機(jī)產(chǎn)生了任務(wù)數(shù)量規(guī)模為50、100、150、200、250、300、350、400的DAG圖各20組，每類DAG圖的最大并行度、深度、安全需求等都不相同。分析實(shí)驗(yàn)結(jié)果時(shí)，將任務(wù)數(shù)量相同的20組仿真結(jié)果求均值作為衡量標(biāo)準(zhǔn)，具體仿真結(jié)果如圖6所示。

圖5任務(wù)數(shù)量固定、網(wǎng)格環(huán)境可變情形下性能比較
Fig.5Performancecomparisonintheconditionthatfixedtasksnumberandvariablegridenvironment

圖6　網(wǎng)格環(huán)境固定，任務(wù)規(guī)?？勺兦樾蜗滦阅鼙容^Fig.6　Performance　comparison　in　the　condition　that　fixed　grid　environment　and　variable　tasks　number

從圖6a可以看出，在網(wǎng)格環(huán)境一定的情況下，隨著任務(wù)規(guī)模的增加，任務(wù)調(diào)度長(zhǎng)度都有所增加。相對(duì)來(lái)說(shuō)，GA算法相對(duì)于SEFT算法有約10%的性能提升，而GASHO算法相對(duì)于GA算法又提升約3%，算法性能提升較小主要是因?yàn)镚A和GASHO算法均以啟發(fā)式SEFT算法為基礎(chǔ)，基礎(chǔ)解都較優(yōu)秀所致。另外，通過(guò)分析實(shí)驗(yàn)數(shù)據(jù)來(lái)看，隨著任務(wù)規(guī)模的不斷擴(kuò)大，三種算法的折線圖開口越來(lái)越大，相對(duì)優(yōu)勢(shì)也越來(lái)越明顯，因此GASHO算法更適于應(yīng)用大規(guī)模任務(wù)情況。從圖6b看出，在不同任務(wù)規(guī)模的情況下，由于SEFT算法側(cè)重于強(qiáng)調(diào)調(diào)度長(zhǎng)度最優(yōu)，導(dǎo)致安全效益值相對(duì)最差；GA算法安全效益值相對(duì)SEFT算法較優(yōu)，但比GASHO算法差。這體現(xiàn)在兩個(gè)方面：一是GASHO算法的安全效益值更優(yōu)，二是GASHO算法的安全效益值相對(duì)更穩(wěn)定，這主要是因?yàn)樵黾恿酥C振搜索算子后，能搜索到性價(jià)比更好的解。

通過(guò)仿真實(shí)驗(yàn)可以看出：SEFT算法依據(jù)任務(wù)到達(dá)次序找到每個(gè)任務(wù)的局部最優(yōu)調(diào)度長(zhǎng)度，但不一定是全局最優(yōu)解；GA算法雖然針對(duì)問(wèn)題最優(yōu)解具有較強(qiáng)的全局搜索能力，但容易陷入局部最優(yōu)解；諧振算法不僅具有很好的全局收斂性，而且局部搜索能力也較強(qiáng)，但是很難確定初始運(yùn)行參數(shù)；GA算法與諧振算法相結(jié)合，優(yōu)缺點(diǎn)互補(bǔ)性高，獲得了更好的收斂速度和全局收斂性。

5結(jié)語(yǔ)

本文首先針對(duì)網(wǎng)格依賴任務(wù)調(diào)度問(wèn)題，結(jié)合網(wǎng)格節(jié)點(diǎn)的安全策略控制與歷史行為表現(xiàn)，建立了網(wǎng)格資源節(jié)點(diǎn)安全模型，并以此為基礎(chǔ)構(gòu)建了可信調(diào)度優(yōu)化模型，某些方面補(bǔ)充了相關(guān)研究工作。其次，利用遺傳算法與諧振算法解尋優(yōu)過(guò)程中優(yōu)勢(shì)互補(bǔ)的特征，結(jié)合EFT算法快速映射任務(wù)到處理機(jī)的思想，提出了一種針對(duì)異構(gòu)分布式計(jì)算系統(tǒng)中DAG任務(wù)調(diào)度的遺傳諧振算法GASHO，并從收斂性和時(shí)間復(fù)雜度方面進(jìn)行了證明或分析。GASHO算法采用啟發(fā)式策略控制遺傳算子和諧振算子操作，在任務(wù)依賴約束條件下，可以更快更好地產(chǎn)生新的任務(wù)調(diào)度隊(duì)列，達(dá)到全局與局部尋優(yōu)的目的。最后，通過(guò)對(duì)隨機(jī)DAG任務(wù)圖和真實(shí)應(yīng)用DAG圖等進(jìn)行實(shí)驗(yàn)，驗(yàn)證了GASHO算法在收斂速度、調(diào)度質(zhì)量(包括調(diào)度長(zhǎng)度、安全效益值滿意度等)等方面具有較好的綜合性能。

未來(lái)，將進(jìn)行兩個(gè)方面的工作：一是將相關(guān)研究工作遷移到云計(jì)算環(huán)境中，以期在用戶SLA需求與系統(tǒng)運(yùn)營(yíng)策略(尤其是成本控制)等方面尋求最佳平衡點(diǎn)；二是進(jìn)一步探討云環(huán)境下服務(wù)定價(jià)機(jī)制與底層資源映射相結(jié)合的資源調(diào)度優(yōu)化問(wèn)題。

參考文獻(xiàn):

[1]Shin-YeuL,Shih-ChengH,Cheng-ZihL.Expandingservicecapacitiesandincreasingservicereliabilitiesforthegrid-basedutilitycomputing[J].IEEETransactionsonSystems,Man,andCybernetics-PartA:SystemsandHumans,2011,41(1):149-160.

[2]朱海,王宇平.融合安全的網(wǎng)格依賴任務(wù)調(diào)度雙目標(biāo)優(yōu)化模型及算法[J].軟件學(xué)報(bào),2011,22(11):2729-2748.

[3]SarkarV,KhapardeSA.Improvingdemandresponseandbid-consistencyofpriceoutcomeinthesecurity-constraineddispatchscheduling[J].IEEETransactionsonPowerSystems,2013,28(8):2433-2445.

[4]GongChen,WangXiaodong,XuWeiqiang,etal.Distributedreal-timeenergyschedulinginsmartgridstochasticmodelandfastoptimization[J].IEEETransactionsonSmartGrid,2013,4(9):1476-1489.

[5]YuanLL,ZengGS,JiangLL,etal.Dynamiclevelschedulingbasedontrustmodelingridcomputing[J].ChineseJournalofComputers,2006，29(7)：1217-1224.

[6]ZhangWZ,LiuXR,HuMZ,etal.Trust-drivenjobschedulingheuristicsforcomputinggrid[J].JournalonCommunication,2006,27(2):73-79.

[7]BraunTD,SlegelHJ,BecjN.Acomparisonofelevenstaticheuristicsformappingaclassofindependenttasksontoheterogeneousdistributedcomputingsystems[J].JournalofParallelandDistributedComputing,2001,61(6):810-837.

[8]XiaoP,HuZG.Co-schedulingmodelforindependenttaskswithdeadlineconstraintincomputationalgrid[J].ActaElectronicSinica,2011,39(8):1852-1857.

[9]馬艷,龔斌,鄒立達(dá).網(wǎng)格環(huán)境下基于復(fù)制的能耗有效依賴任務(wù)調(diào)度研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50(2):420-429.

[10]閻朝坤,胡志剛,李璽,等.面向可靠性-費(fèi)用優(yōu)化的網(wǎng)格任務(wù)調(diào)度模型及算法研究[J].計(jì)算機(jī)科學(xué),2013,40(5):136-141.

[11]DuXL,JiangCJ,XuGR.AgridDAGschedulingalgorithmbasedonfuzzyclustering[J].JournalofSoftware,2006,17(11):2277-2288.

[12]殷國(guó)富,羅陽(yáng),龍紅能,等.并行設(shè)計(jì)子任務(wù)調(diào)度的遺傳算法原理與實(shí)現(xiàn)方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(8):1122-1126.

[13]HeXS,SunXH,vonLaszewskiG.QoSguidedmin-minheuristicforgridtaskscheduling[J].JournalofComputerScienceandTechnology,2003,18(4):442-451.

[14]WengC,LuX.Heuristicschedulingforbag-of-tasksapplicationsincombinationwithQoSinthecomputationalgrid[J].FutureGenerationComputerSystems,2005,21(2):271-280.

[15]ChenJ,KongL,PanX.ResearchongridresourceschedulingalgorithmintegratingforecastmechanismwithQoSconstraint[J].JournalofComputerResearchandDevelopment.2008,45:11-16.

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

[17]AbdelzaherTF,AtkinsEM,ShinKG.QoSnegotiationinreal-timesystemsanditsapplicationtoautomatedflightcontrol[J].IEEETransactionsonComputers,2000,49(6):1170-1183.

[18]XuYuming,LiKenli,HuJingtong,etal.Ageneticalgorithmfortaskschedulingonheterogeneouscomputingsystemsusingmultiplepriorityqueues[J].InformationSciences,2014,270(2):255-287.

[19]YaldaAryan.HSGA:Ahybridheuristicalgorithmforworkflowschedulingincloudsystems[J].ClusterComputing,2014,17(5):129-137.

[20]袁文成,朱怡安,陸偉.面向虛擬資源的云計(jì)算資源管理機(jī)制[J].西北工業(yè)大學(xué)學(xué)報(bào),2010,28(5):704-708.

[21]ZhuH，WangYP.Security-driventaskschedulingbasedonevolutionaryalgorithm[C]//Proceedingsofthe2008ComputationalIntelligenceandSecurity,Washington:IEEEComputerSociety,2008:451-456.

[22]ZhuH,WangYP.GriddependenttaskssecurityschedulingmodelandDPSOalgorithm[J].JournalofNetworks,2011,6(6):850-857.

[23]陳發(fā)堂,張民倉(cāng).一類新的環(huán)狀非有心諧振子勢(shì)的精確解[J].陜西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2011,39(4):29-33.

[24]徐雨明,朱寧波,歐陽(yáng)艾嘉,等.異構(gòu)系統(tǒng)中DAG任務(wù)調(diào)度的雙螺旋結(jié)構(gòu)遺傳算法[J].計(jì)算機(jī)研究與發(fā)展,2014,51(6):1240-1252.

[25]JinXu,AlbertYSLam,VictorOKLi,etal.Chemicalreactionoptimizationfortaskschedulingingridcomputing[J].IEEETransactionsonParallelandDistributedSystems,2011,22(10):1624-1631.

[26]朱思峰,劉芳,柴爭(zhēng)義,等.簡(jiǎn)諧振子免疫優(yōu)化算法求解異構(gòu)無(wú)線網(wǎng)絡(luò)垂直切換判決問(wèn)題[J].物理學(xué)報(bào),2012,61(9):096401.

[27]TopcuogluH,HaririS,WuMinyou.Performanceeffectiveandlow-complexitytaskschedulingforheterogeneouscomputing[J].IEEETransactionsonParallelandDistributedSystems,2002,13(3):260-274.

〔責(zé)任編輯宋軼文〕

第一作者：姚洪興，男，教授，博士生導(dǎo)師，研究方向?yàn)榻?jīng)濟(jì)系統(tǒng)復(fù)雜性建模與分析。E-mail：hxyao@ujs.edu.cn

Usinggenetic-harmonicalgorithmtosolvesecurityschedulingproblem

ofdependenttasksinheterogeneousgridsystem

WANGHongfeng1,2,ZHUHai2

(1SchoolofComputerScienceandTechnology,HuazhongUniversityofScienceand

Technology,Wuhan430079,Hubei,China;

2SchoolofComputerScienceandTechnology,ZhoukouNormalUniversity,

Zhoukou466001,Henan,China)

Abstract:Aimedatthesecurityproblemoftasksschedulinginheterogeneousgridsystem,asecurityevaluationmodelispresentedbasedonsecuritycontrolstrategyandhistorybehaviorofgridnodes,andonthisbasisakindofsafeandtrustedoptimizationmodelfordependenttasksschedulingisputforwardundergridenvironment.Tosolvethemodel,anewgenetic-harmonicalgorithmcalledGASHOisdesigned,whichtaksfulladvantageofthecharacteristicofglobaloptimizationofgeneticalgorithmandintroducestheharmonicoperatortoovercometheshortageoflocaloptimization.BasedonthedependenciesofaDAGtaskgraph,theheuristicmethodisemployedtodesigntheoperatorofgeneticandquantumharmonic,thustheGASHOproducesabettertaskschedulingqueuetoavoidtheoccurenceofillegalsolutionsindiscretespaces.Then,toimprovetheconvergenceefficiency,theearliestfinishtimeoperatorwhichisconstrainedtosecurityfactorsisusedtomapfromtasksettogridnodes.Atlast,theconvergencepropertyandtimecomplexityisanalyzed.Comparedwithothersimilaralgorithmunderthesamecondition,thesimulationresultsshowthattheproposedalgorithmhastheadvantagesontheconvergenceproperty,schedulinglengthandsecurityefficiency.

Keywords:gridcomputing;dependenttask;securityscheduling;genetic-harmonicalgorithm

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(71271103,71371087,71271107)

收稿日期：2014-10-10

doi:10.15983/j.cnki.jsnu.2015.02.221

文章編號(hào)：1672-4291(2015)02-0024-04

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A