網格資源管理的研究與發現

摘 要:提出一種采用分布式動態層次結構的資源管理模型方法。依據資源之間的網絡通信性能使資源組織成帶層次的樹型組織結構，根據網格資源類別在邏輯上劃分多個社區，使得資源的組織方式能夠反映實際的網絡拓撲，為計算任務在資源上的合理分配提供了依據，避免了資源選擇的盲目性。在該資源管理模型中的資源發現與定位，采用資源樹查找算法，多種請求定位策略，可以快速地找到目標結點，提高相應查找時間。資源定位的效率仿真表明這種方法可以提高查找速度和性能。關鍵詞:網格技術; 資源管理; 動態層次; 資源定位

中圖分類號:TN915-34文獻標識碼:A

文章編號:1004-373X(2010)16-0029-03

Grid Resource Management and Finding

LIU Lei

(School of City Construction， Jilin Architecture and Civil Engineering Institute， Changchun 130111， China)

Abstract: A resource management model with distributed dynamic hierarchical structure is proposed. The resources are organized into a tree structure with the hierarchy based on the performance of network communication between the resources. Multi-communitiesare logically divided according to the type of grid resources to make the organization mode of the resources to reflect the actual network topology to provide the basis for the resources′rational allocation of computing tasks， which avoids the blindness of resource selection. In this way， the local strategies of the resources can be respect and the best scheduling can be carried out in the global sense. The lookup algorithm of the resource tree is adopted for the resource discovery and location in the resource management model. The positioning strategies of a number of requests can quickly find the target node， and save the search time. The simulation results show that the method can improve the search speed and performance.Keywords: grid technology; resource management; dynamic hierarchical structure; resource location

0 引 言

網格計算被譽為繼Internet和Web之后的“第三個信息技術浪潮”，有望提供下一代分布式應用和服務，對研究和信息系統發展有著深遠的影響。要實現高性能計算和共享異構網格資源，必須提供高效的資源管理機制，建立統一和高效的資源管理模型，負責用戶與網格計算環境的交互，提高網格計算系統資源的查找速度。本文采用分布式動態層次結構的資源管理模型，采用分類社區的方法使得便于管理，更快捷的查詢，提高查詢效率。與傳統的網格資源管理模型相比，它可以有效地對資源進行管理，能夠在分布式環境中資源共享，大大提高協同工作的工作效率。采用了一種類似于搜索引擎機制的資源目錄樹形式組織資源，使用基于數據庫查詢的方法來查找資源目錄樹的邏輯資源信息。解決了單個資源請求和多個資源請求問題的算法。

1 資源管理的動態層次結構

本文采用的資源管理模型是基于社區的分布式的動態層次結構，其主要思想是在邏輯上將網格按類別劃分為多個社區，信息結點即注冊的結點內部都配有本地資源管理器，用來對資源進行管理和調度。社區中的任何信息結點都可以作為社區的出口，社區的出口可以同其他社區的資源管理系統進行交互，每個信息結點的資源管理器中都有用來儲存鄰近結點信息的信息表。為了使網格社區系統和外部連通，每個社區資源管理系統和其他的社區資源管理系統的任務管理器之間采用路由器連接構造更大的資源管理系統，并在任務管理器之間實現任務遷移，達到負載平衡，保證用戶提交的任務在資源比較密集的環境下運行，減少任務內部之間的通信代價，提高任務的處理時間和效率，這就形成了對整個網格資源的管理。

把整個資源管理系統分為若干功能層，較高層次的組件利用較高層次組件提供的服務實現自身的功能。它的內部結構分為用戶層、網格安全層、資源管理層、資源層四層。整個資源管理的流程說明如下:

(1) 用戶通過用戶界面，如GUI或者Web瀏覽器登錄網格，在網格入口處要進行安全身份確認及權限確認，確認通過后用戶進入網格;

(2) 用戶進入網格后，向網格提交作業，請求被任務管理器接收;

(3) 任務管理器查詢網格資源管理器中的網格信息表，根據作業請求和資源狀態進行匹配;

(4) 匹配成功后將資源信息和搜集執行結果返回給資源管理器;

(5) 資源管理器將作業執行狀態及最終結果向網格監控器匯報;

(6) 網格監控器負責將作業執行狀態通過網格入口報告給用戶，并最終顯示在GUI界面或者Web瀏覽器上。

該系統模型通過實驗對不同模型進行比對，克服了其他模型分工不明確、查找效率低的缺點，它既尊重資源擁有者的本地策略，又能夠在全局意義上進行最佳資源分配。

2 資源發現算法

2.1 算法思想

在該資源管理模型基礎上提出了分層樹型結構網格資源發現方法。資源發現請求轉發以及資源信息的擴散都在相應的社區內，從而改善了資源發現的性能。資源根據特定的限制被分在不同的社區，形成樹型結構，社區入口與社區入口之間是由路由器連接的。在社區內部搜索中引入了將少數較好的結果返回給用戶的資源定位機制，節省了用戶比較選擇的時間。在資源管理器中，資源信息表是記錄關于子網格資源信息的重要數據結構。分層樹結構中的每個分枝就是子網格，為了確定哪個子網格能夠提供特定的資源，資源管理器要收集關于這些子網格的最新資源信息并記錄在信息表中。對于給定的子網格，資源管理器負責收集該子網格中結點信息，對于非葉子結點收集的是父親結點和子結點的信息，葉子結點收集的是父親結點信息。子網格中任意的結點信息都可以作為這個子網格的入口點。

資源樹主干建立后，可以按人為或自動的構造相應的邏輯樹，并對相應的信息進行存儲;

(1) 每個結點只有一個條目;

(2) 每個結點保存其所有子結點、父結點的信息;

(3) 每個結點保存目前該子樹相關狀態與歷史信息;

(4) 每個結點保存自身的安全策略。

為了在查找時可以快速找到目標節點，提高響應時間。這里查找目標的信息是以樹的形式存儲，每個社區是一棵子樹，各個社區之間是一個對等的實體，同時為了提高匹配效率，需將這棵樹轉換成有序樹，將各個主機結點按照結構或者操作系統分類。例如將所有的Unix操作系統的主機作為一棵子樹，然后在這棵樹下又分為多棵子樹，每一棵子樹中的結點又可以按照作業個數、CPU使用率，計算能力等來排序。

2.2 算法分析

下面以一個實例來說明以上各種查找目標的意義。假設資源樹形態如圖1所示，每個結點中的數字表示該結點上的參數值(資源計算能力參數)。給定參數的參考值為10，查找條件是“計算能力不小于參考值”。則從源結點NS出發尋找目標結點，其滿意解為S，局部最優解為L，全局最優解為G。后面將給出各種查找目標的查找過程及時間復雜度分析。設資源樹中葉子結點數為N，下面給出各種查找目標的查找過程，并分析其查找過程時間復雜度(與N的關系)。

圖1 在資源樹上進行資源的查找

滿意解 計算能力不滿足要求，則將查找需求發送到父結點。根據資源樹的計算能力向上聚集的原則可知，如果滿意解存在，則必然在從源結點到根結點的路徑上。設查找需求被從一個結點發送到其父結點為1個查找步，最好的情況是源結點本身的參數就滿足條件，查找步數目為0，在最壞的情況下，查找過程要從資源樹最底層結點進行到根結點，查找步數為資源樹的深度log N，因此其時間復雜度為O(log N)，平均情況下的時間復雜度也為O(log N)。在圖1中求解滿意解時，NS上的資源管理器先判斷本結點參數9不滿足條件，于是將查找需求發送給父結點S，S判斷本結點參數20滿足條件，返回結點S，查找過程結束。這種方法的優點是簡單，可以快速找到匹配結果，缺點是有可能不是最佳的結果。

局部最優解 求局部最優解分為2步:第1步是找到滿意解;第2步是在滿意解所在結點上的資源子樹中的最優解。資源樹的計算能力向上聚集保證了任何一個結點的計算能力參數不小于其所有子結點的計算能力。過程如下:

(1) 子樹的根結點上記錄了孩子結點的信息，可以查找它的另一個孩子結點(除去因為不滿足匹配而轉到該子樹的那個孩子結點)的信息，看是否滿足匹配條件。

(2) 不滿足匹配條件，則子樹的根就是局部最優解。

(3) 滿足匹配條件，就把該孩子結點當作下一層子樹的根。在依次執行過程(1)，用過程(2)來判斷。

最壞的情況應該是原來時間復雜度的2倍，為2O(log N)。圖1中求解局部最優解時，在找到滿意解S后，在S上維護的資源子樹中查找與10最近的且不小于10的結點，在9，11，5，6中查找到11，返回結點L，查找過程結束。

全局最優解 求全局最優解也分為2步:第1步是將查找需求沿資源樹向上發送到根結點;第2步是在根結點上的資源樹中尋找最優解。它的平均時間復雜度應該為局部最優解最壞的時間復雜度。圖1中求解全局最優解時，查找需求先從NS向上發送直到根結點，然后在根結點上維護的資源樹中查找與10最近而且不小于10的結點，在50，20，30，9，11，10，20，5，6，5，5中查找到10，返回結點G，查找過程結束。

3 仿真結果及性能分析

圖2為兩種算法的響應時間比較。從圖中可以看出在資源請求數目比較小時，傳統的窮舉查找算法響應時間較短，隨著任務數量的增加，響應時間增長速度較慢，在40個任務以后，時間明顯低于本算法，事實上，該查找算法與傳統的查找算法相比擴大了搜索范圍，基于該模型的查找算法的信息存儲處理雖然占用部分處理時間，但對于大量的查找任務來說存儲處理時間可以忽略不計。這種方式在多任務，復雜結構更具有優勢。

圖2 基于本模型的查找算法和傳統模型下的

窮舉查找算法的響應時間比較

4 結 語

網格計算是一個正在迅速發展的研究領域，本文給出基于動態的分層資源管理模型，引入了社區概念對同類的資源進行分類，并通過基于本模型下的關聯算法描述，這種方式在多任務，復雜結構下更具有優勢。這種方法與傳統的網格資源管理模型相比，可以有效地對資源進行管理，能夠在分布式環境中對資源共享，大大提高協同工作的工作效率。仿真特性顯示了這種方法優良性能。進一步的工作是擴充網格資源的信息表的描述功能，完善智能算法設計，提高系統計算效率，探討它在服務中的廣泛應用。

參考文獻

[1]SHENG Q Z， BENATALLAH B， DUMAS M， et al. SELF-SERV: a platform for rapid composition of Web services in a peer to peer environment[C]//Demo Session of the 28th International Conference on Very Large Databases. Hong Kong: [s.n.] 2002: 1051-1054.

[2]SIRIN E， PARSIA B， WU D， et al. HTN planning for Web service composition using SHOP2[J]. Journal of Web Semantics: Science， Services and Agents on the World Wide Web， 2004， 1(4): 377-396.

[3]SYCARA K， PAOLUCCI M， SOUDRY J， et al. Dynamic discovery and coordination of agent-based semantic Web services[J]. IEEE Internet Computing， 2004， 8(3): 66-73.

[4]ZHUGE Hai. The future interconnection environment[J]. IEEE Computer， 2005， 38(4): 27-33.

[5]CANFORA G， PENTA M Di， ESPOSITO R， et al. A lightweight approach for QoS-aware service composition[C]//Proceedings of the 2nd International Conference on Service Oriented Computing. New York， USA:[s.n.]， 2004: 36-47.

[6]ZHANG L J， LI B， CHAO T， et al. On demand Web services-based business process composition[C]//IEEE International Conference on System， Man， and Cybernetics. Washington， USA: IEEE， 2003: 4057-4064.

[7]張成文，蘇森，陳俊亮.基于遺傳算法的QoS感知的Web服務選擇[J].計算機學報，2006，29(7):1029-1037.

[8]王勇，蔡自興，曾威，等.求解約束優化問題的一種新的進化算法[J].中南大學學報2006，37(1):119-121.

[9]ZENG L Z， BENATALLAH B. NGU A H H， et al. QoS-aware middleware for service composition[J]. IEEE Trans. on Software Engineering， 2004， 30(5): 311-327.