摘要：介紹了信任關(guān)系量的化方法，然后根據(jù)任務(wù)的安全性要求設(shè)置任務(wù)的優(yōu)先級，對已有的信任驅(qū)動(dòng)的網(wǎng)格調(diào)度算法進(jìn)行改進(jìn)，改進(jìn)算法在不增加時(shí)間復(fù)雜度的同時(shí)提高了調(diào)度的信任效益:最后通過仿真證明算法的有效性，并對仿真結(jié)果進(jìn)行分析。

關(guān)鍵詞：網(wǎng)格計(jì)算；任務(wù)調(diào)度；網(wǎng)格安全；信任模型；信任驅(qū)動(dòng)

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)14-20944-03

網(wǎng)格計(jì)算的目的是通過分布式環(huán)境下異構(gòu)組織間動(dòng)態(tài)的資源共享和協(xié)作來求解復(fù)雜的計(jì)算問題。由于網(wǎng)格環(huán)境下的資源的跨組織性、異構(gòu)和動(dòng)態(tài)性的特點(diǎn)，使得在網(wǎng)格環(huán)境下的資源管理和調(diào)度都非常困難。一直以來網(wǎng)格調(diào)度問題都是人們關(guān)注的重點(diǎn)，也提出了Min-min、Max-min、GA等經(jīng)典算法。網(wǎng)格計(jì)算的集成程度更高、應(yīng)用領(lǐng)域

更廣、使用更方便、資源的利用更加充分和有效。但網(wǎng)格比傳統(tǒng)網(wǎng)絡(luò)環(huán)境復(fù)雜得多，因此提出了更高更廣泛的安全需求。安全性問題的研究將是影響網(wǎng)格應(yīng)用的一個(gè)關(guān)鍵性因素，而實(shí)體之間的信任關(guān)系是安全性的一個(gè)重要方面。因此將信任融入到網(wǎng)格資源調(diào)度中的研究具有重要的現(xiàn)實(shí)意義。

本文重點(diǎn)是在傳統(tǒng)的Min-min資源調(diào)度算法研究基礎(chǔ)上，提出一種基于優(yōu)先級的信任驅(qū)動(dòng)調(diào)度算法，使其更具有安全性。

1 信任調(diào)度模型

1.1 信任模型

信任是一個(gè)非常復(fù)雜的主觀概念，目前沒有一致的定義。文獻(xiàn)[3]提出了自己的信任模型，量化了資源和任務(wù)的信任屬性，提出了在不同信任關(guān)系下的信任效益函數(shù)，擴(kuò)展了傳統(tǒng)的批模式下任務(wù)調(diào)度算法，本文采用文獻(xiàn)[3]中定義的信任模型，具體如下：

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

資源信任屬性包含兩方面：(1) 安全性。衡量網(wǎng)格資源對任務(wù)和數(shù)據(jù)的真實(shí)性、保密性和完整性的保障程度。本文采用資源安全級別(resource security value)量化資源安全屬性；(2) 可靠性。長時(shí)間執(zhí)行的任務(wù)有可能因?yàn)槟硞€(gè)資源失效導(dǎo)致運(yùn)行失敗甚至重啟，造成系統(tǒng)資源浪費(fèi)和系統(tǒng)性能低下。本文量化資源可靠性(resource reliability value)為單位時(shí)間內(nèi)失效概率。

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

1.2 信任效益函數(shù)

根據(jù)調(diào)度過程中任務(wù)對資源信任值的要求，任務(wù)與資源間的信任關(guān)系可以分為強(qiáng)(strong)信任關(guān)系、弱(weak)信任關(guān)系與無(no)信任關(guān)系3類。

以確保安全性效益在任務(wù)可降低信任需求時(shí)其效益值隨之下降。

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

可以定義任務(wù)ti在資源mj上所獲得的信任效益函數(shù)如式(8)所示，其中，w和(1-w)是安全性和可靠性上的重要性權(quán)值。可知，信任效益函數(shù)值越大，任務(wù)映射后執(zhí)行越穩(wěn)定，執(zhí)行結(jié)果愈加可信。

定義2 信任驅(qū)動(dòng)的網(wǎng)格任務(wù)調(diào)度問題：給定m個(gè)異構(gòu)計(jì)算資源組成的網(wǎng)格環(huán)境M={m1，m2，...，mm}，n個(gè)獨(dú)立任務(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，使得：Maximize TrustUtil (map)。

2 基于優(yōu)先級的信任驅(qū)動(dòng)調(diào)度算法

信任驅(qū)動(dòng)的網(wǎng)格任務(wù)調(diào)度是NP完全問題，本文借鑒傳統(tǒng)min-min的思想，提出了基于優(yōu)先級的任務(wù)驅(qū)動(dòng)調(diào)度算法。

基于優(yōu)先權(quán)的信任驅(qū)動(dòng)調(diào)度算法(PTD-min-min )的基本思想是根據(jù)任務(wù)的任務(wù)安全性設(shè)定其優(yōu)先級，利用文獻(xiàn)[4]提出的分段Min-min的思想，這里根據(jù)任務(wù)的優(yōu)先級對所有任務(wù)進(jìn)行分段。任務(wù)的安全性級別決定其對資源安全性的要求，安全性要求越高表示其對資源的性能要求越高，優(yōu)先分配高優(yōu)先級的任務(wù)可以避免因滿足條件的資源被占用而分配失敗，使得效益值為0。由文獻(xiàn)[4]可知，任務(wù)被分成4段或5段能取得較好的效果，本文任務(wù)優(yōu)先級恰好可分為{poor，low，medium，high}四級。

算法根據(jù)任務(wù)的優(yōu)先級先選出所有任務(wù)中優(yōu)先級最高的任務(wù)，然后再從這些任務(wù)中選擇擁有最高信任效益的任務(wù)進(jìn)行映射。當(dāng)高優(yōu)先級的任務(wù)映射完后，選擇優(yōu)先級次高的任務(wù)段繼續(xù)分配。由于算法優(yōu)先級與任務(wù)的安全性要求有關(guān)，優(yōu)先調(diào)度安全性要求高的任務(wù)可以避免任務(wù)取到最小的信任效益值，因此增加了任務(wù)總的信任效益。

PTD-min-min算法的實(shí)現(xiàn)步驟如下：

(1)對任務(wù)集合T中每個(gè)待分配的任務(wù)t，獲取其安全性級別、可靠性級別;

(2)對資源集合M中的每個(gè)計(jì)算資源，獲取其安全性級別，可靠性級別;

(3)根據(jù)任務(wù)的安全性級別設(shè)定任務(wù)的優(yōu)先級，根據(jù)任務(wù)的優(yōu)先級對任務(wù)進(jìn)行分段;獲取優(yōu)先級最高的分段s;

(4)對分段中的任務(wù)集合T中每一個(gè)等待分配的任務(wù)ti分配到n個(gè)計(jì)算資源上，根據(jù)任務(wù)與資源之間的不同的信任關(guān)系，利用安全性效益函數(shù)計(jì)算每個(gè)任務(wù)一資源對的信任效益值，利用可靠性效益函數(shù)計(jì)算任務(wù)一資源對的可靠性效益值(具體函數(shù)見(2));

(5)設(shè)定w值，根據(jù)公式(8)計(jì)算信任效益值，構(gòu)造任務(wù)信任效益矩陣。

(6)假設(shè)任務(wù)ti在第k個(gè)計(jì)算資源上的信任效益值為最大，記為MaxTrust(i)=TrustUtil(i，k)，可得到一個(gè)含有m個(gè)元素的一維數(shù)組MaxTrust;

(7)從MaxTrust中找到信任效益最大的任務(wù)a及對應(yīng)的計(jì)算資源b;

(8)將任務(wù)a映射到計(jì)算資源b上;

(9)從s分段中把本次映射的任務(wù)a刪除，同時(shí)更新TrustUtil矩陣。即將任務(wù)a刪除，同時(shí)更新所有未分配任務(wù)在計(jì)算資源b上的信任效益值;

(10)重復(fù)步驟4)～9)直到分段s為空;

(11)判斷是否存在下一優(yōu)先級段，取下一分段轉(zhuǎn)(4)，否則結(jié)束映射。當(dāng)任務(wù)的安全性級別較為單一時(shí)，即所有任務(wù)對安全性要求都很高，級別均為high，或者安全性要求都屬于medium級別，此時(shí)算法退化為文獻(xiàn)的TD-min-min算法。

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

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

仿真實(shí)驗(yàn)中，任務(wù)執(zhí)行時(shí)間矩陣ETC由計(jì)算機(jī)模擬生成，ETC矩陣生成算法根據(jù)文獻(xiàn)[5]利用garmma函數(shù)產(chǎn)生，取μtask=μmatch=100，其中Vtask和Vmatch分別代表任務(wù)和計(jì)算資源的異構(gòu)性。m為機(jī)器數(shù)，n為任務(wù)數(shù)。Vtask和Vmatch取值為0～1，取值越大，異構(gòu)性越高。

資源安全級別RS設(shè)置為四個(gè)級別{poor，low，medium，high}，每個(gè)資源的安全級別在此區(qū)間內(nèi)隨機(jī)生成。資源的單位時(shí)間失效率FR在區(qū)間[0.0001，0.0015]上隨機(jī)生成。任務(wù)安全需求級別JS設(shè)置與資源安全級別設(shè)置相同，每個(gè)任務(wù)安全需求級別在此區(qū)間內(nèi)隨機(jī)生成。任務(wù)安全需求級別JR在強(qiáng)、弱信任關(guān)系的情況下根據(jù)公式JR=(0.9+0.1*rand*exp{10-4*(任務(wù)數(shù)/主機(jī)數(shù))}生成。其中rand均勻分布在[0，1]。任務(wù)在計(jì)算資源上的預(yù)期執(zhí)行時(shí)間ETC，每個(gè)任務(wù)隨機(jī)設(shè)置優(yōu)先級Pi∈{low，media，high}。設(shè)置變量1≤Vq≤4控制任務(wù)與資源間的信任關(guān)系。生成一個(gè)[0，1]間隨機(jī)數(shù)，如果該數(shù)小于0.25Vq，則稱兩者具有強(qiáng)信任關(guān)系；該數(shù)小于0.5Vq，具有弱信任關(guān)系；否則，為無信任關(guān)系。信任效益函數(shù)(8)中w取值均為0.5。Vq值越大，任務(wù)與資源間的強(qiáng)信任關(guān)系越多，當(dāng)Vq值為4時(shí)，任務(wù)與資源之間的信任關(guān)系均為強(qiáng)信任關(guān)系。

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

每個(gè)任務(wù)的信任效益中不僅反應(yīng)了任務(wù)在某個(gè)資源上運(yùn)行的安全性、可靠性，而且包含了任務(wù)的完成時(shí)間，取得高信任效益是信任驅(qū)動(dòng)的調(diào)度算法的目標(biāo)，平均信任效益是所有任務(wù)所獲的信任效益的平均值?？捎梢韵鹿接?jì)算PTD-min-min算法與Min-min算法相比性能提高的程度：

從圖1可以看出改進(jìn)的算法PTD-min-min在算法所獲得的平均信任效益要明顯優(yōu)于TD-min-min算法。由于隨著任務(wù)的分配，后分配的任務(wù)在機(jī)器上執(zhí)行的可靠性效益下降，因此隨著分配的任務(wù)數(shù)增加調(diào)度的平均信任效益呈下降趨勢。PTD-min-min算法穩(wěn)定性好，對任務(wù)數(shù)的變化敏感度較低。

根據(jù)具體的數(shù)據(jù)值和公式(9)計(jì)算可得，與TD-min-min算法相比PTD-min-min調(diào)度性能提高了43.15%。

在Vq取值為3，其它參數(shù)不變的情況下，仿真結(jié)果如圖2所示。隨著Vq值的增大，任務(wù)與資源之間強(qiáng)信任關(guān)系的比重增大，弱信任關(guān)系比重降低，而無信任關(guān)系比重則為0?？梢钥闯鲈赩q=3的情況下PTD-min-min算法性能也遠(yuǎn)超出TD-min-min。同樣，TD-min-min算法平均信任效益隨著任務(wù)數(shù)的增加下降較為明顯，即調(diào)度性能受調(diào)度任務(wù)數(shù)影響較為明顯，PTD-min-min算法調(diào)度性能相對較穩(wěn)定(圖2)，可見，PTD-min-min算法比TD-min-min算法具有更高的穩(wěn)定性。

利用公式(9)計(jì)算圖2中的算法的實(shí)際性能提升程度，最后計(jì)算結(jié)果為：22.5%，與Vq=2相比優(yōu)越性有所下降。這是由于任務(wù)與資源之間不同的信任關(guān)系比例不均引起的。可見算法的性能不僅與任務(wù)安全性級別有關(guān)，還和任務(wù)與資源之間的信任關(guān)系有關(guān)。

4 結(jié)束語

信任就是由信任值表征的客觀實(shí)體的身份和行為的可信度評估，信任值取決于實(shí)體可靠性、誠信和性能等，將信任機(jī)制與任務(wù)調(diào)度機(jī)制有效融合是真實(shí)網(wǎng)格環(huán)境中大規(guī)模分布式資源管理的難題之一。本文提出了信任驅(qū)動(dòng)的網(wǎng)格任務(wù)調(diào)度新算法PTD-max-min。在相同的仿真實(shí)驗(yàn)條件下，通過調(diào)節(jié)機(jī)器異構(gòu)和任務(wù)異構(gòu)性，變動(dòng)強(qiáng)、弱信任關(guān)系的任務(wù)數(shù)目，對其進(jìn)行了仿真分析和比較研究。

參考文獻(xiàn)：

[1] Braun R D，Siegel H J，Beck N，et al. A Comparison Study of Static Mapping Heuristics for a Class of Meta-tasks on Heterogeneous Computing Systems[C].Proceedings of the 8th Heterogeneous Computing Workshop. San Juan， Facrto Rico: [s.n.]， 1999:15-29.

[2] Foster I.A security architecture for computationalgrids[A]. Proceedings of the 5th ACM Conference on Computer and Communications Security Conference[C].New York: ACM Press，1998.83-92.

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

[4] u Min-You，Shu Wei，Zhang Hong. Segmented Min-Min:A Static Mapping Algorithm for Meta-Tasks on Heterogeneous Computing Systems[A].In 9th IEEE Heterogeneous Computing Workshop (HCW' 2000)[C].Washington:IEEE Computer Society Press， 2000， 375-385.

[5] S.Ali，H.J.Siegel，M.Maheswaran，etal. Representing-task and machine heterogeneities for heterogeneous computing systems [J].Tamkang Journal of Science and Engineering 2000，3(3):195-207.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文