一種基于信任的網格資源調度算法

摘要：介紹了信任關系量的化方法，然后根據任務的安全性要求設置任務的優先級，對已有的信任驅動的網格調度算法進行改進，改進算法在不增加時間復雜度的同時提高了調度的信任效益:最后通過仿真證明算法的有效性，并對仿真結果進行分析。

關鍵詞：網格計算；任務調度；網格安全；信任模型；信任驅動

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

網格計算的目的是通過分布式環境下異構組織間動態的資源共享和協作來求解復雜的計算問題。由于網格環境下的資源的跨組織性、異構和動態性的特點，使得在網格環境下的資源管理和調度都非常困難。一直以來網格調度問題都是人們關注的重點，也提出了Min-min、Max-min、GA等經典算法。網格計算的集成程度更高、應用領域

更廣、使用更方便、資源的利用更加充分和有效。但網格比傳統網絡環境復雜得多，因此提出了更高更廣泛的安全需求。安全性問題的研究將是影響網格應用的一個關鍵性因素，而實體之間的信任關系是安全性的一個重要方面。因此將信任融入到網格資源調度中的研究具有重要的現實意義。

本文重點是在傳統的Min-min資源調度算法研究基礎上，提出一種基于優先級的信任驅動調度算法，使其更具有安全性。

1 信任調度模型

1.1 信任模型

信任是一個非常復雜的主觀概念，目前沒有一致的定義。文獻[3]提出了自己的信任模型，量化了資源和任務的信任屬性，提出了在不同信任關系下的信任效益函數，擴展了傳統的批模式下任務調度算法，本文采用文獻[3]中定義的信任模型，具體如下：

定義1 由信任值表征的客觀實體的身份和行為的可信度評估，信任值取決于實體可靠性、誠信和性能等。計算網格信任模型主要由資源信任屬性、任務信任屬性及其相互間信任關系構成。

資源信任屬性包含兩方面：(1) 安全性。衡量網格資源對任務和數據的真實性、保密性和完整性的保障程度。本文采用資源安全級別(resource security value)量化資源安全屬性；(2) 可靠性。長時間執行的任務有可能因為某個資源失效導致運行失敗甚至重啟，造成系統資源浪費和系統性能低下。本文量化資源可靠性(resource reliability value)為單位時間內失效概率。

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

1.2 信任效益函數

根據調度過程中任務對資源信任值的要求，任務與資源間的信任關系可以分為強(strong)信任關系、弱(weak)信任關系與無(no)信任關系3類。

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

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

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

定義2 信任驅動的網格任務調度問題：給定m個異構計算資源組成的網格環境M={m1，m2，...，mm}，n個獨立任務構成的任務集合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，...}表示在資源上的任務調度函數；s(i，j)=k表示在計算資源mj上第k個執行的任務是ti，使得：Maximize TrustUtil (map)。

2 基于優先級的信任驅動調度算法

信任驅動的網格任務調度是NP完全問題，本文借鑒傳統min-min的思想，提出了基于優先級的任務驅動調度算法。

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

算法根據任務的優先級先選出所有任務中優先級最高的任務，然后再從這些任務中選擇擁有最高信任效益的任務進行映射。當高優先級的任務映射完后，選擇優先級次高的任務段繼續分配。由于算法優先級與任務的安全性要求有關，優先調度安全性要求高的任務可以避免任務取到最小的信任效益值，因此增加了任務總的信任效益。

PTD-min-min算法的實現步驟如下：

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

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

(3)根據任務的安全性級別設定任務的優先級，根據任務的優先級對任務進行分段;獲取優先級最高的分段s;

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

(5)設定w值，根據公式(8)計算信任效益值，構造任務信任效益矩陣。

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

(7)從MaxTrust中找到信任效益最大的任務a及對應的計算資源b;

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

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

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

(11)判斷是否存在下一優先級段，取下一分段轉(4)，否則結束映射。當任務的安全性級別較為單一時，即所有任務對安全性要求都很高，級別均為high，或者安全性要求都屬于medium級別，此時算法退化為文獻的TD-min-min算法。

3 仿真實驗與分析

3.1 實驗內容與設置

仿真實驗中，任務執行時間矩陣ETC由計算機模擬生成，ETC矩陣生成算法根據文獻[5]利用garmma函數產生，取μtask=μmatch=100，其中Vtask和Vmatch分別代表任務和計算資源的異構性。m為機器數，n為任務數。Vtask和Vmatch取值為0～1，取值越大，異構性越高。

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

3.2 實驗結果與性能分析

每個任務的信任效益中不僅反應了任務在某個資源上運行的安全性、可靠性，而且包含了任務的完成時間，取得高信任效益是信任驅動的調度算法的目標，平均信任效益是所有任務所獲的信任效益的平均值?？捎梢韵鹿接嬎鉖TD-min-min算法與Min-min算法相比性能提高的程度：

從圖1可以看出改進的算法PTD-min-min在算法所獲得的平均信任效益要明顯優于TD-min-min算法。由于隨著任務的分配，后分配的任務在機器上執行的可靠性效益下降，因此隨著分配的任務數增加調度的平均信任效益呈下降趨勢。PTD-min-min算法穩定性好，對任務數的變化敏感度較低。

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

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

利用公式(9)計算圖2中的算法的實際性能提升程度，最后計算結果為：22.5%，與Vq=2相比優越性有所下降。這是由于任務與資源之間不同的信任關系比例不均引起的?？梢娝惴ǖ男阅懿粌H與任務安全性級別有關，還和任務與資源之間的信任關系有關。

4 結束語

信任就是由信任值表征的客觀實體的身份和行為的可信度評估，信任值取決于實體可靠性、誠信和性能等，將信任機制與任務調度機制有效融合是真實網格環境中大規模分布式資源管理的難題之一。本文提出了信任驅動的網格任務調度新算法PTD-max-min。在相同的仿真實驗條件下，通過調節機器異構和任務異構性，變動強、弱信任關系的任務數目，對其進行了仿真分析和比較研究。

參考文獻：

[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] 張偉哲，劉欣然，云曉春，等. 信任驅動的網格任務調度算法[J].通信學報，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.

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