王洪峰，　朱　海

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

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

?

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

王洪峰1,2，朱海2

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

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

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

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

MRsubjectclassification:68M20

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

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

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

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

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

(1)

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

(2)

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

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

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

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

(3)

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

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

(4)

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

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

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

θ·AC(ru)。

(5)

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

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

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)計算獲得。

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

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

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

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

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

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

定義6網(wǎng)格資源表示模型。本文所研究的異構(gòu)網(wǎng)格模型可由集合R={ru|u∈[0,m)}表示，對任一網(wǎng)格節(jié)點為一個三元組ru=(δu,ρu,τu)，其中δu代表節(jié)點的計算能力，ρu表示節(jié)點的安全服務(wù)向量，τu代表網(wǎng)格節(jié)點的可持續(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ù)資源分配映射圖可以用一個向量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)度安全評估函數(shù)。該函數(shù)用來評價網(wǎng)格用戶應(yīng)用任務(wù)執(zhí)行安全滿意度，可由下式獲得：

(7)

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

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

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

(8)

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

tei,u=ati/δru,

(9)

(10)

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

定義10網(wǎng)格可信調(diào)度優(yōu)化模型。本文網(wǎng)格可信調(diào)度優(yōu)化目標是尋找依賴任務(wù)描述模型到網(wǎng)格節(jié)點模型之間的映射，使得網(wǎng)格系統(tǒng)執(zhí)行任務(wù)時調(diào)度長度最短的同時，用戶獲得盡可能安全的網(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個分配調(diào)度方案，即任務(wù)到資源的映射方案；TL(Gk)和S(Gk)為網(wǎng)格任務(wù)的調(diào)度長度和安全總效益值，可分別由(8)式和(7)式獲得；w1、w2為調(diào)度長度與安全效益值的重要性權(quán)重，根據(jù)任務(wù)特性，適當調(diào)整權(quán)重wk(k=1,2)，對任意目標進行重新優(yōu)化以滿足不同網(wǎng)格用戶的傾向性需求。

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

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

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

3.1　解質(zhì)量評價函數(shù)

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

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

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

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

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

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

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

Step4基于Min(Z)與Max(Z)值，分別將任務(wù)t(i)分配到網(wǎng)格節(jié)點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ù)序號定長組合編碼。為生成符合條件的初始解群體，首先將應(yīng)用網(wǎng)格任務(wù)圖(DAG)中的所有子任務(wù)節(jié)點按深度值劃分成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針對DAG[i]中的所有任務(wù)，隨機生成一個序列進行編碼，并將編碼值追加到Pop[PopNo]編碼后邊；

Step6i++；

Step7endfor

Step8PopNo=PopNo+1；

Step9endwhile

Step10return初始化種群Pop[Popsize]。

3.3　算子設(shè)計

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

算法3.交叉操作

輸入：雙親個體編碼Fa、Ma

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

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

Step2以交叉位p為斷點，將父個體Fa和Ma分別分割為前后段，具體表示為Fa_L、Fa_R、Ma_L、Ma_R；

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

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

Step5returnC1，C2。

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

算法4.變異操作

輸入：父個體Fa

輸出：子個體Child

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

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

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

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

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

Step6returnChild。

3.3.3諧振算子設(shè)計

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

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

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

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

算法5.諧振操作算子

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

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

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

Step2f(s)=f(Init)；

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

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

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

3.4　算法流程描述

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

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

3.5　算法收斂性分析

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

證明(1)在算法中，對于任意兩個個體p和q，q可由p通過進化生成。

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

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

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

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

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

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

即對于可行解空間Q中任意兩個個體p和q，q可由p進化所得。

(2)由GASHO算法的解個體更新過程可知，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)度問題的最優(yōu)解。

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

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

4仿真實驗與結(jié)果分析

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

4.1　算法的收斂性分析

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

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

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

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

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

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

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

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

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

實驗隨機產(chǎn)生了60個異構(gòu)網(wǎng)格節(jié)點，并通過TaskProc隨機產(chǎn)生了任務(wù)數(shù)量規(guī)模為50、100、150、200、250、300、350、400的DAG圖各20組，每類DAG圖的最大并行度、深度、安全需求等都不相同。分析實驗結(jié)果時，將任務(wù)數(shù)量相同的20組仿真結(jié)果求均值作為衡量標準，具體仿真結(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)度長度都有所增加。相對來說，GA算法相對于SEFT算法有約10%的性能提升，而GASHO算法相對于GA算法又提升約3%，算法性能提升較小主要是因為GA和GASHO算法均以啟發(fā)式SEFT算法為基礎(chǔ)，基礎(chǔ)解都較優(yōu)秀所致。另外，通過分析實驗數(shù)據(jù)來看，隨著任務(wù)規(guī)模的不斷擴大，三種算法的折線圖開口越來越大，相對優(yōu)勢也越來越明顯，因此GASHO算法更適于應(yīng)用大規(guī)模任務(wù)情況。從圖6b看出，在不同任務(wù)規(guī)模的情況下，由于SEFT算法側(cè)重于強調(diào)調(diào)度長度最優(yōu)，導(dǎo)致安全效益值相對最差；GA算法安全效益值相對SEFT算法較優(yōu)，但比GASHO算法差。這體現(xiàn)在兩個方面：一是GASHO算法的安全效益值更優(yōu)，二是GASHO算法的安全效益值相對更穩(wěn)定，這主要是因為增加了諧振搜索算子后，能搜索到性價比更好的解。

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

5結(jié)語

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

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

參考文獻:

[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)度雙目標優(yōu)化模型及算法[J].軟件學(xué)報,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]馬艷,龔斌,鄒立達.網(wǎng)格環(huán)境下基于復(fù)制的能耗有效依賴任務(wù)調(diào)度研究[J].計算機研究與發(fā)展,2013,50(2):420-429.

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

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

[12]殷國富,羅陽,龍紅能,等.并行設(shè)計子任務(wù)調(diào)度的遺傳算法原理與實現(xiàn)方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,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)度問題的多目標演化算法[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].西北工業(yè)大學(xué)學(xué)報,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ā)堂,張民倉.一類新的環(huán)狀非有心諧振子勢的精確解[J].陜西師范大學(xué)學(xué)報:自然科學(xué)版,2011,39(4):29-33.

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

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

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

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

〔責任編輯宋軼文〕

第一作者：姚洪興，男，教授，博士生導(dǎo)師，研究方向為經(jīng)濟系統(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

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

收稿日期：2014-10-10

doi:10.15983/j.cnki.jsnu.2015.02.221

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

中圖分類號：TP393

文獻標志碼：A