信任驅(qū)動(dòng)的資源調(diào)度算法*

王 磊，解 福

（山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014）

當(dāng)前計(jì)算網(wǎng)格中存在調(diào)度機(jī)制與信任機(jī)制分離。將信任機(jī)制與資源調(diào)度機(jī)制有效融合，可以為網(wǎng)格資源安全管理提供保障，使得資源調(diào)度更好地在動(dòng)態(tài)、異構(gòu)、開放的真實(shí)網(wǎng)格環(huán)境中有效運(yùn)行。

目前相關(guān)的研究中對(duì)信任的定義還沒(méi)有形成一致的見解，在信任的計(jì)算方法中不同的作者有不同的思路。其中具有代表性的研究包括：AZZEDIN與MAHESWARAN[1]等人首次將“信任”融入網(wǎng)格資源管理，提出考慮信任因素的作業(yè)調(diào)度會(huì)引入額外負(fù)載并設(shè)計(jì)了負(fù)載最小化算法。HUMPHREY[2]等人對(duì)具有安全意識(shí)的網(wǎng)格計(jì)算模型進(jìn)行了深入研究。ABAWAJY[3]等人提出的DFTS分布式失效容忍調(diào)度策略，通過(guò)復(fù)制作業(yè)的多個(gè)副本到不同站點(diǎn)保證作業(yè)在網(wǎng)格環(huán)境下可靠進(jìn)行。DOGAN[4]和SONG Shan Shan[5]提出了最小化失效率的網(wǎng)格信任調(diào)度框架和調(diào)度算法。唐小勇[6]等人在Buyya設(shè)計(jì)的GRACE網(wǎng)格資源管理框架下，提出反映信任值動(dòng)態(tài)變化規(guī)律的信任函數(shù)，建立基于行為的網(wǎng)格信任機(jī)制，并將其應(yīng)用到網(wǎng)格經(jīng)濟(jì)模型中的DBC調(diào)度算法中。

本文采用參考文獻(xiàn)[7]中給出的信任定義，將信任效益值和最小完成時(shí)間作為調(diào)度目標(biāo)函數(shù)，對(duì)資源進(jìn)行分配，提出了基于信任的網(wǎng)格資源調(diào)度算法Trust Mintime Min-Min算法。

1 概念與問(wèn)題描述

1.1 信任模型

本文采用的信任定義為：

定義1信任：由信任值表征的客觀實(shí)體的身份和行為的可信度評(píng)估，信任值取決于實(shí)體可靠性、誠(chéng)信和性能等。計(jì)算網(wǎng)格信任模型主要由資源信任屬性、任務(wù)信任屬性及其相互間信任關(guān)系構(gòu)成。資源信任屬性包含兩方面：

（1）安全性。衡量網(wǎng)格資源對(duì)任務(wù)和數(shù)據(jù)的真實(shí)性、保密性和完整性的保障程度。采用資源安全級(jí)別量化資源安全屬性。

（2）可靠性。長(zhǎng)時(shí)間執(zhí)行的任務(wù)有可能因?yàn)槟硞€(gè)資源失效導(dǎo)致運(yùn)行失敗甚至重啟，造成系統(tǒng)資源浪費(fèi)和系統(tǒng)性能低下。本文量化資源可靠性為單位時(shí)間內(nèi)失效概率。

任務(wù)信任屬性指網(wǎng)格用戶提交任務(wù)請(qǐng)求時(shí)，對(duì)任務(wù)運(yùn)行的安全性和可靠性要求。分別采用任務(wù)安全級(jí)別與可靠性級(jí)別量化任務(wù)信任屬性。

1.2 信任效益函數(shù)

本文采用參考文獻(xiàn)[8]定義信任關(guān)系為 strong、weak、no的任務(wù)Ti在資源Rj上執(zhí)行的原始安全性效益函數(shù)為：

同理，將信任關(guān)系為 strong、weak、no的任務(wù) Ti在資源Rj上執(zhí)行的原始可靠性效益函數(shù)定義為：

其中，任務(wù)可靠性需求 JRi∈（0，1），而資源可靠性 RRij由任務(wù)Ti和資源Rj共同決定。設(shè)調(diào)度開始時(shí)每個(gè)計(jì)算資源固有失效率為FRj。隨著時(shí)間增加，失效的概率逐漸增大，可靠度減小。任務(wù) Ti在 Rj上的完成時(shí)間為 CTij，則可靠度為 RRij=exp（-CTij×FRj）。

可以定義任務(wù)Ti在資源Rj上所獲得的信任效益函數(shù)如式（7）所示，其中，w1和 w2是安全性和可靠性上的重要性權(quán)值?？芍?，信任效益函數(shù)值越大，任務(wù)映射后執(zhí)行越穩(wěn)定，執(zhí)行結(jié)果愈加可信。

定義2信任驅(qū)動(dòng)的網(wǎng)格資源調(diào)度問(wèn)題[7]：給定m個(gè)異構(gòu)計(jì)算資源組成的網(wǎng)格環(huán)境 M={m1，m2，…，mm}，n個(gè)元任務(wù)構(gòu)成的任務(wù)集合 T={t1，t2，…，tn}，求映射方案map=(a，s)(其中 a：T→M為表示資源分配的映射，a(i)=j表示將 ti分配到 mj上，s：{(i，a(i))|i∈T}→N={1，2，3，…}表示在資源上的任務(wù)調(diào)度函數(shù)，s(i，j)=k表示在計(jì)算資源mj上第k個(gè)執(zhí)行的任務(wù)是 ti），使得：

比如傅雷翻譯巴爾扎克的長(zhǎng)篇小說(shuō)的書名《La Cousine Bette》、《Le Pere Goriot》，本來(lái)，前者應(yīng)譯為《表妹貝德》或《堂妹貝德》,后者譯為《高里奧老爹》或《高里奧大伯》。傅雷考慮到中文名字的特點(diǎn)，仔細(xì)揣摩了全書內(nèi)容后，把前者譯為《貝姨》，后者譯為《高老頭》，改譯后在文字表達(dá)上符合中文讀者的文化背景，從而縮短了譯語(yǔ)讀者與譯作的距離，而且還傳遞了主人公在作品中扮演的特定角色，堪稱有意識(shí)誤譯的成功佳例。

定義3信任關(guān)系：根據(jù)調(diào)度過(guò)程中任務(wù)對(duì)資源信任值的要求，二者之間的信任關(guān)系可以分為強(qiáng)信任關(guān)系、弱信任關(guān)系和無(wú)信任關(guān)系。

（1）強(qiáng)信任關(guān)系指調(diào)度時(shí)任務(wù)的安全性和可靠性需求級(jí)別必須高于所分配資源的固有屬性值。如果不存在滿足條件的資源，則此任務(wù)將被放棄。其最終效益值或者為最大，或者為零。

（2）弱信任關(guān)系指調(diào)度算法盡量保證任務(wù)信任屬性值高于資源的信任屬性值，此時(shí)可獲得最大效益；否則，可以降低任務(wù)的信任需求，但是其信任效益值隨之下降。

（3）無(wú)信任關(guān)系指在調(diào)度過(guò)程中不考慮任務(wù)和資源間的信任關(guān)系，僅以完成時(shí)間最小為目標(biāo)。

定義4資源調(diào)度的最小完成時(shí)間計(jì)算：在網(wǎng)格環(huán)境中，考慮任務(wù)之間沒(méi)有通信和數(shù)據(jù)依賴的集合，即元任務(wù)。那么要將 m個(gè)資源 M={m1，m2，…，mm}以合理的方式調(diào)度到 n個(gè)元任務(wù) T={t1，t2，…，tn}的過(guò)程中，目的是得到盡可能小的總執(zhí)行時(shí)間(makespan)。n個(gè)元任務(wù)在m個(gè)資源的預(yù)測(cè)執(zhí)行時(shí)間ETC(Expected Time to Compute)是一個(gè)m×n的矩陣，矩陣中的每一行代表某一個(gè)任務(wù)在m個(gè)資源上的不同時(shí)間，每一列代表某一資源上的m個(gè)任務(wù)的不同執(zhí)行時(shí)間。

第i個(gè)任務(wù)在第j個(gè)資源上的預(yù)測(cè)最小完成時(shí)間(Minimum Completion Time)記 為 MCT(i，j)， 則 n 個(gè) 元 任務(wù)在m個(gè)資源上的預(yù)測(cè)最小完成時(shí)間也是一個(gè) m×n的矩陣，筆者僅考慮以下決定因素：

(1)ETC(i，j)：任務(wù) i在資源 j上的預(yù)測(cè)執(zhí)行時(shí)間。

以上這些數(shù)據(jù)可以通過(guò)網(wǎng)格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)組件來(lái)獲取。

定義 MCT(i，j)的計(jì)算公式為：

2 算法

首先將具有強(qiáng)信任關(guān)系和弱信任關(guān)系的任務(wù)各分為一類，把無(wú)信任關(guān)系的任務(wù)歸為第三類；然后，先對(duì)有信任關(guān)系的任務(wù)進(jìn)行調(diào)度，計(jì)算有信任關(guān)系的每個(gè)任務(wù)在各網(wǎng)格計(jì)算資源上的最大信任效益函數(shù)值，選擇信任效益最大的任務(wù)—資源對(duì)進(jìn)行映射；再計(jì)算無(wú)信任關(guān)系的任務(wù)在各網(wǎng)格計(jì)算資源上的最小完成時(shí)間，選擇完成時(shí)間最小的任務(wù)―資源對(duì)進(jìn)行映射。算法描述為：

Trust Mintime Min-Min()

輸入：任務(wù)和資源信任信息，ETC矩陣

輸出：任務(wù)映射方案map

初始化：令T為所有任務(wù)的集合，M為所有資源的集合，集合TR=?保存任務(wù)―資源對(duì)，變量k用于計(jì)數(shù)。

根據(jù)信任關(guān)系（strong、weak、no）將任務(wù)集合 T分為三個(gè)不相交的子集合class1，class2，classno

令k=1;

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)內(nèi)容與設(shè)置

仿真試驗(yàn)考察了20～50個(gè)計(jì)算資源組成的網(wǎng)格系統(tǒng)對(duì)1～200個(gè)獨(dú)立任務(wù)構(gòu)成集合調(diào)度的情況。

資源安全級(jí)別JR和任務(wù)安全級(jí)別JS在這4個(gè)級(jí)別{poor，low，medium，high}內(nèi)隨機(jī)產(chǎn)生。資源的單位時(shí)間失效率FR在區(qū)間[0.000 1，0.001 5]上隨機(jī)生成。任務(wù)需求級(jí)別JR在強(qiáng)、弱信任關(guān)系的情況下根據(jù)公式JR=(0.9+0.1×rand)×exp(10-4×任務(wù)數(shù)/主機(jī)數(shù))生成。 根據(jù)參考文獻(xiàn)[8]中方案取 μtask=μmach=100，Vtask=Vmach=0.6。 設(shè)置變量1≤Vq≤4控制任務(wù)與資源間的信任關(guān)系，生成一個(gè)[0，1]間隨機(jī)數(shù)，如果該數(shù)小于 0.25 Vq，則稱兩者具有強(qiáng)信任關(guān)系；該數(shù)小于0.5 Vq為弱信任關(guān)系；否則為無(wú)信任關(guān)系。信任效益函數(shù)式(7)中w1和w2均取值為0.5。

3.2 實(shí)驗(yàn)結(jié)果和性能分析

設(shè)置200個(gè)獨(dú)立任務(wù)在50個(gè)異構(gòu)資源進(jìn)行調(diào)度。如圖1所示，顯示了30個(gè)資源負(fù)載情況，可以看出本文提出的Trust Mintime Min-Min算法負(fù)載平衡性明顯優(yōu)于傳統(tǒng)的Min-Min算法。

圖1 資源負(fù)載平衡

由于考慮了信任關(guān)系，將任務(wù)提交到信任度較高的資源上執(zhí)行，如圖2所示，Trust Mintime Min-Min算法大大提高了任務(wù)提交的成功率，資源也得到有效的利用。

圖2 任務(wù)提交成功率

圖3和圖4分別給出了在網(wǎng)格環(huán)境中正常運(yùn)行和有10%的任務(wù)存在惡意請(qǐng)求的情況下的兩種算法的Makespan。從圖中可以明顯看出，隨著任務(wù)數(shù)目的增加，本文提出的Trust Mintime Min-Min算法在任務(wù)總的執(zhí)行時(shí)間越來(lái)越少于Min-Min算法，特別是在網(wǎng)格環(huán)境中存在惡意行為的情況下更為明顯。

仿真結(jié)果證明Trust Mintime Min-Min算法在資源負(fù)載、任務(wù)總的執(zhí)行時(shí)間等方面較經(jīng)典的Min-Min算法有所提高。考慮到信任關(guān)系，在一定程度上提高了網(wǎng)格系統(tǒng)的安全性和可靠性，保證了網(wǎng)格系統(tǒng)的正常運(yùn)行。

圖3 不存在惡意任務(wù)請(qǐng)求的Makespan

圖4 存在10%的惡意任務(wù)請(qǐng)求的Makespan

[1]AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems[C].2002 International Conference on Parallel Processing(ICPP 2002).Canada：IEEE Press 2002：47-54.

[2]HUMPHREY M，THOMPSON M R.Security implication of typical grid computing usage scenario[C].IEEE Proc HPDC.USA：IEEE Press，2001：95-103.

[3]ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems[C].Proc IPDPS 2004.USA：IEEE Press，2004：50-58.

[4]DOGAN A，OZGUNER F.Matching and scheduling algorithms for minimizing execution time and failure probalitity of applications in heterogeneous computing[J].IEEE Trans on Parallel and Distributed Systems，2002，13(3)：308-323.

[5]SONG S，KWOK Y K，HWANG K.Trusted job scheduling in open computional grids：Security-driven heuristics and a fast genetic algorithm[C].proceedings of the 19thIEEE International parallel&Distributed Proceessing Symposium(IPDPS-2005).Denver，CO，USA：IEEE Press，2005：33-40.

[6]唐小勇，李肯立.網(wǎng)格經(jīng)濟(jì)模型中基于信任機(jī)制的調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2008，25(8)：2357-2361.

[7]張偉哲，劉欣然，云小春，等.信任驅(qū)動(dòng)的網(wǎng)格作業(yè)調(diào)度算法[J].通信學(xué)報(bào)，2006，27(2)：73-79.

[8]SHOUKAT A，HOWARD J S，MUTHUCUMARU M，et al.Task execution time modeling for heterogeneous computing systems[C].IPDPS Workshop on Heterogeneous Computing.Cancun，Mexic：IEEE Press，2000：185-199.