網(wǎng)格資源管理的研究與發(fā)現(xiàn)

摘 要:提出一種采用分布式動(dòng)態(tài)層次結(jié)構(gòu)的資源管理模型方法。依據(jù)資源之間的網(wǎng)絡(luò)通信性能使資源組織成帶層次的樹型組織結(jié)構(gòu)，根據(jù)網(wǎng)格資源類別在邏輯上劃分多個(gè)社區(qū)，使得資源的組織方式能夠反映實(shí)際的網(wǎng)絡(luò)拓?fù)?，為?jì)算任務(wù)在資源上的合理分配提供了依據(jù)，避免了資源選擇的盲目性。在該資源管理模型中的資源發(fā)現(xiàn)與定位，采用資源樹查找算法，多種請(qǐng)求定位策略，可以快速地找到目標(biāo)結(jié)點(diǎn)，提高相應(yīng)查找時(shí)間。資源定位的效率仿真表明這種方法可以提高查找速度和性能。關(guān)鍵詞:網(wǎng)格技術(shù); 資源管理; 動(dòng)態(tài)層次; 資源定位

中圖分類號(hào):TN915-34文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

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

1 資源管理的動(dòng)態(tài)層次結(jié)構(gòu)

本文采用的資源管理模型是基于社區(qū)的分布式的動(dòng)態(tài)層次結(jié)構(gòu)，其主要思想是在邏輯上將網(wǎng)格按類別劃分為多個(gè)社區(qū)，信息結(jié)點(diǎn)即注冊(cè)的結(jié)點(diǎn)內(nèi)部都配有本地資源管理器，用來對(duì)資源進(jìn)行管理和調(diào)度。社區(qū)中的任何信息結(jié)點(diǎn)都可以作為社區(qū)的出口，社區(qū)的出口可以同其他社區(qū)的資源管理系統(tǒng)進(jìn)行交互，每個(gè)信息結(jié)點(diǎn)的資源管理器中都有用來儲(chǔ)存鄰近結(jié)點(diǎn)信息的信息表。為了使網(wǎng)格社區(qū)系統(tǒng)和外部連通，每個(gè)社區(qū)資源管理系統(tǒng)和其他的社區(qū)資源管理系統(tǒng)的任務(wù)管理器之間采用路由器連接構(gòu)造更大的資源管理系統(tǒng)，并在任務(wù)管理器之間實(shí)現(xiàn)任務(wù)遷移，達(dá)到負(fù)載平衡，保證用戶提交的任務(wù)在資源比較密集的環(huán)境下運(yùn)行，減少任務(wù)內(nèi)部之間的通信代價(jià)，提高任務(wù)的處理時(shí)間和效率，這就形成了對(duì)整個(gè)網(wǎng)格資源的管理。

把整個(gè)資源管理系統(tǒng)分為若干功能層，較高層次的組件利用較高層次組件提供的服務(wù)實(shí)現(xiàn)自身的功能。它的內(nèi)部結(jié)構(gòu)分為用戶層、網(wǎng)格安全層、資源管理層、資源層四層。整個(gè)資源管理的流程說明如下:

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

(2) 用戶進(jìn)入網(wǎng)格后，向網(wǎng)格提交作業(yè)，請(qǐng)求被任務(wù)管理器接收;

(3) 任務(wù)管理器查詢網(wǎng)格資源管理器中的網(wǎng)格信息表，根據(jù)作業(yè)請(qǐng)求和資源狀態(tài)進(jìn)行匹配;

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

(5) 資源管理器將作業(yè)執(zhí)行狀態(tài)及最終結(jié)果向網(wǎng)格監(jiān)控器匯報(bào);

(6) 網(wǎng)格監(jiān)控器負(fù)責(zé)將作業(yè)執(zhí)行狀態(tài)通過網(wǎng)格入口報(bào)告給用戶，并最終顯示在GUI界面或者Web瀏覽器上。

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

2 資源發(fā)現(xiàn)算法

2.1 算法思想

在該資源管理模型基礎(chǔ)上提出了分層樹型結(jié)構(gòu)網(wǎng)格資源發(fā)現(xiàn)方法。資源發(fā)現(xiàn)請(qǐng)求轉(zhuǎn)發(fā)以及資源信息的擴(kuò)散都在相應(yīng)的社區(qū)內(nèi)，從而改善了資源發(fā)現(xiàn)的性能。資源根據(jù)特定的限制被分在不同的社區(qū)，形成樹型結(jié)構(gòu)，社區(qū)入口與社區(qū)入口之間是由路由器連接的。在社區(qū)內(nèi)部搜索中引入了將少數(shù)較好的結(jié)果返回給用戶的資源定位機(jī)制，節(jié)省了用戶比較選擇的時(shí)間。在資源管理器中，資源信息表是記錄關(guān)于子網(wǎng)格資源信息的重要數(shù)據(jù)結(jié)構(gòu)。分層樹結(jié)構(gòu)中的每個(gè)分枝就是子網(wǎng)格，為了確定哪個(gè)子網(wǎng)格能夠提供特定的資源，資源管理器要收集關(guān)于這些子網(wǎng)格的最新資源信息并記錄在信息表中。對(duì)于給定的子網(wǎng)格，資源管理器負(fù)責(zé)收集該子網(wǎng)格中結(jié)點(diǎn)信息，對(duì)于非葉子結(jié)點(diǎn)收集的是父親結(jié)點(diǎn)和子結(jié)點(diǎn)的信息，葉子結(jié)點(diǎn)收集的是父親結(jié)點(diǎn)信息。子網(wǎng)格中任意的結(jié)點(diǎn)信息都可以作為這個(gè)子網(wǎng)格的入口點(diǎn)。

資源樹主干建立后，可以按人為或自動(dòng)的構(gòu)造相應(yīng)的邏輯樹，并對(duì)相應(yīng)的信息進(jìn)行存儲(chǔ);

(1) 每個(gè)結(jié)點(diǎn)只有一個(gè)條目;

(2) 每個(gè)結(jié)點(diǎn)保存其所有子結(jié)點(diǎn)、父結(jié)點(diǎn)的信息;

(3) 每個(gè)結(jié)點(diǎn)保存目前該子樹相關(guān)狀態(tài)與歷史信息;

(4) 每個(gè)結(jié)點(diǎn)保存自身的安全策略。

為了在查找時(shí)可以快速找到目標(biāo)節(jié)點(diǎn)，提高響應(yīng)時(shí)間。這里查找目標(biāo)的信息是以樹的形式存儲(chǔ)，每個(gè)社區(qū)是一棵子樹，各個(gè)社區(qū)之間是一個(gè)對(duì)等的實(shí)體，同時(shí)為了提高匹配效率，需將這棵樹轉(zhuǎn)換成有序樹，將各個(gè)主機(jī)結(jié)點(diǎn)按照結(jié)構(gòu)或者操作系統(tǒng)分類。例如將所有的Unix操作系統(tǒng)的主機(jī)作為一棵子樹，然后在這棵樹下又分為多棵子樹，每一棵子樹中的結(jié)點(diǎn)又可以按照作業(yè)個(gè)數(shù)、CPU使用率，計(jì)算能力等來排序。

2.2 算法分析

下面以一個(gè)實(shí)例來說明以上各種查找目標(biāo)的意義。假設(shè)資源樹形態(tài)如圖1所示，每個(gè)結(jié)點(diǎn)中的數(shù)字表示該結(jié)點(diǎn)上的參數(shù)值(資源計(jì)算能力參數(shù))。給定參數(shù)的參考值為10，查找條件是“計(jì)算能力不小于參考值”。則從源結(jié)點(diǎn)NS出發(fā)尋找目標(biāo)結(jié)點(diǎn)，其滿意解為S，局部最優(yōu)解為L(zhǎng)，全局最優(yōu)解為G。后面將給出各種查找目標(biāo)的查找過程及時(shí)間復(fù)雜度分析。設(shè)資源樹中葉子結(jié)點(diǎn)數(shù)為N，下面給出各種查找目標(biāo)的查找過程，并分析其查找過程時(shí)間復(fù)雜度(與N的關(guān)系)。

圖1 在資源樹上進(jìn)行資源的查找

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

局部最優(yōu)解 求局部最優(yōu)解分為2步:第1步是找到滿意解;第2步是在滿意解所在結(jié)點(diǎn)上的資源子樹中的最優(yōu)解。資源樹的計(jì)算能力向上聚集保證了任何一個(gè)結(jié)點(diǎn)的計(jì)算能力參數(shù)不小于其所有子結(jié)點(diǎn)的計(jì)算能力。過程如下:

(1) 子樹的根結(jié)點(diǎn)上記錄了孩子結(jié)點(diǎn)的信息，可以查找它的另一個(gè)孩子結(jié)點(diǎn)(除去因?yàn)椴粷M足匹配而轉(zhuǎn)到該子樹的那個(gè)孩子結(jié)點(diǎn))的信息，看是否滿足匹配條件。

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

(3) 滿足匹配條件，就把該孩子結(jié)點(diǎn)當(dāng)作下一層子樹的根。在依次執(zhí)行過程(1)，用過程(2)來判斷。

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

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

3 仿真結(jié)果及性能分析

圖2為兩種算法的響應(yīng)時(shí)間比較。從圖中可以看出在資源請(qǐng)求數(shù)目比較小時(shí)，傳統(tǒng)的窮舉查找算法響應(yīng)時(shí)間較短，隨著任務(wù)數(shù)量的增加，響應(yīng)時(shí)間增長(zhǎng)速度較慢，在40個(gè)任務(wù)以后，時(shí)間明顯低于本算法，事實(shí)上，該查找算法與傳統(tǒng)的查找算法相比擴(kuò)大了搜索范圍，基于該模型的查找算法的信息存儲(chǔ)處理雖然占用部分處理時(shí)間，但對(duì)于大量的查找任務(wù)來說存儲(chǔ)處理時(shí)間可以忽略不計(jì)。這種方式在多任務(wù)，復(fù)雜結(jié)構(gòu)更具有優(yōu)勢(shì)。

圖2 基于本模型的查找算法和傳統(tǒng)模型下的

窮舉查找算法的響應(yīng)時(shí)間比較

4 結(jié) 語

網(wǎng)格計(jì)算是一個(gè)正在迅速發(fā)展的研究領(lǐng)域，本文給出基于動(dòng)態(tài)的分層資源管理模型，引入了社區(qū)概念對(duì)同類的資源進(jìn)行分類，并通過基于本模型下的關(guān)聯(lián)算法描述，這種方式在多任務(wù)，復(fù)雜結(jié)構(gòu)下更具有優(yōu)勢(shì)。這種方法與傳統(tǒng)的網(wǎng)格資源管理模型相比，可以有效地對(duì)資源進(jìn)行管理，能夠在分布式環(huán)境中對(duì)資源共享，大大提高協(xié)同工作的工作效率。仿真特性顯示了這種方法優(yōu)良性能。進(jìn)一步的工作是擴(kuò)充網(wǎng)格資源的信息表的描述功能，完善智能算法設(shè)計(jì)，提高系統(tǒng)計(jì)算效率，探討它在服務(wù)中的廣泛應(yīng)用。

參考文獻(xiàn)

[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服務(wù)選擇[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(7):1029-1037.

[8]王勇，蔡自興，曾威，等.求解約束優(yōu)化問題的一種新的進(jìn)化算法[J].中南大學(xué)學(xué)報(bào)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.