李艷鵬 鐘軍凱 魏 慧

濟(jì)寧職業(yè)技術(shù)學(xué)院 山東濟(jì)寧 272037

P2P網(wǎng)絡(luò)中基于本體驅(qū)動的網(wǎng)格資源發(fā)現(xiàn)的研究

李艷鵬 鐘軍凱 魏 慧

濟(jì)寧職業(yè)技術(shù)學(xué)院 山東濟(jì)寧 272037

提出了一種新的語義網(wǎng)格資源發(fā)現(xiàn)方法。P2P網(wǎng)絡(luò)用來分發(fā)和查找資源目錄，每個點(diǎn)能夠提供資源描述和背景知識，能夠查找網(wǎng)絡(luò)中存在的資源信息。每個點(diǎn)都有自己的本體，該本體由網(wǎng)絡(luò)上知識傳播來完成，因此不需要一個中心本體來描述和匹配資源，具有很好的擴(kuò)展性。

網(wǎng)格；資源管理；語義；本體；查找；分配

語義網(wǎng)格的目的是把語義本體和邏輯描述應(yīng)用到網(wǎng)格中間設(shè)備中去。把本體應(yīng)用到資源匹配中去，要求資源提供者和請求者必須具有相同的背景知識，且資源代理程序必須具有訪問本體域的權(quán)利。

資源代理程序訪問本體域需要相應(yīng)的結(jié)構(gòu)與之對應(yīng)。筆者采用了基于本體的P2P網(wǎng)絡(luò)查找網(wǎng)格資源，該網(wǎng)絡(luò)利用傳統(tǒng)語義知識來處理分布式網(wǎng)格中的資源請求，并利用P2P網(wǎng)絡(luò)傳播概念知識。除了具有一般P2P網(wǎng)絡(luò)的分散化、易擴(kuò)展、耐攻擊、高容錯及隱私性能好的優(yōu)點(diǎn)外，該網(wǎng)絡(luò)還具有智能性，因為把本體引入到網(wǎng)格中，使資源之間能夠相互理解，從而能夠根據(jù)用戶的需求有效、動態(tài)、智能地聚合各種資源來滿足用戶的需要。

1 資源匹配算法

1.1 模型

文中采用的資源發(fā)現(xiàn)模型如圖1所示。

圖1 資源發(fā)現(xiàn)模型

該模型分為上下兩層，上層是P2P層，由多個PS服務(wù)組成，每個PS服務(wù)對應(yīng)一個虛擬組織（VO），主要實現(xiàn)2個方面的功能：跨VO的資源發(fā)現(xiàn)和覆蓋網(wǎng)絡(luò)。下層是網(wǎng)格層，由多個VO組成，實現(xiàn)的功能有：資源聚合、VO內(nèi)的資源發(fā)現(xiàn)、建立在PKI基礎(chǔ)上的身份認(rèn)證和授權(quán)機(jī)制。

當(dāng)用戶有查詢請求時，先向本地VO提出請求，本地VO根據(jù)用戶請求在本地的索引服務(wù)中查找，若找到匹配的資源則對資源進(jìn)行分配和預(yù)約。否則，由本地VO中作業(yè)應(yīng)用代理把請求提交到P2P層對應(yīng)的節(jié)點(diǎn)，在此節(jié)點(diǎn)保存著鄰居節(jié)點(diǎn)的資源信息。在P2P層進(jìn)行跨不同VO的資源查找，并把最終的結(jié)果返回到請求資源的應(yīng)用代理處，根據(jù)情況做進(jìn)一步處理。

1.2 模型中存在的問題及解決方法

上述模型需要解決如下兩個方面的問題：

(1)不知道哪個節(jié)點(diǎn)有資源匹配請求。

(2)節(jié)點(diǎn)可能自己也不知道是否具有匹配的資源，因為它們?nèi)鄙俦倔w域中信息的重要部分。

我們構(gòu)造了一個能夠解決上述問題的P2P網(wǎng)絡(luò)（如圖2所示）。在該網(wǎng)絡(luò)中，所有節(jié)點(diǎn)的概念和信息都將在網(wǎng)絡(luò)中進(jìn)行傳播。PS和CS服務(wù)的功能和前面模型中的功能一致，我們主要對VO內(nèi)的節(jié)點(diǎn)進(jìn)行設(shè)置。第一個節(jié)點(diǎn)的IP地址為192.168.0.45，根據(jù)處理器廠家的不同進(jìn)行分類（如圖3所示）；第二個節(jié)點(diǎn)根據(jù)字節(jié)長度進(jìn)行分類（如圖4所示）；第三個節(jié)點(diǎn)根據(jù)AMD子類對CPU進(jìn)行分類（如圖5所示）。第一個節(jié)點(diǎn)包括一個資源且處理器的類型是賽揚(yáng)ID8，這說明圖3中IP地址為192.168.0.45[8]的賽揚(yáng)框中資源ID8是這個概念的一個事例（其中ID指標(biāo)識符）。

圖2 P2P網(wǎng)絡(luò)

圖3 根據(jù)廠家對CPU進(jìn)行分類

圖4 根據(jù)單詞長度對CPU進(jìn)行分類

圖5 根據(jù)AMD子類對CPU進(jìn)行分類

通過網(wǎng)絡(luò)來傳播當(dāng)?shù)谼AGS類型，具體的結(jié)果如圖6所示，網(wǎng)絡(luò)也傳送有關(guān)資源消息。在192.168.0.45[8]顯示的CELERON，INTEL，32位和PROC框都說明IP地址為192.168.0.45節(jié)點(diǎn)ID8是這些概念的一個事例。

假設(shè)查詢需要32位的處理器。盡管節(jié)點(diǎn)1有一個匹配的資源，由于它不知道自己的處理器是32位的，所以并不能滿足自己的需要。通過查找網(wǎng)絡(luò)，使用虛擬類DAG發(fā)現(xiàn)IP地址為192.168.0.45中的資源8能滿足需要。

1.3 消息傳播

消息傳播是指在點(diǎn)到點(diǎn)網(wǎng)絡(luò)中傳播事例檢查、T-Box和A-Box。DHT算法能夠?qū)崿F(xiàn)概念在網(wǎng)絡(luò)中傳播。對每一個概念來說，T-Box和A-Box都要被存儲。T-Box是子概念目錄，這些目錄能夠在網(wǎng)絡(luò)中進(jìn)行傳播，形成虛擬的DAG。A-Box包含每個點(diǎn)的資源列表，這些資源是符合該概念的事例（把它叫做事例列表）。對每個資源來說，節(jié)點(diǎn)的IP地址和資源在節(jié)點(diǎn)上具有的ID都將被存儲，具體表示為“IP1[Resources of IP1],IP2[Resources of IP2],...,IPn[Resources of IPn]”，這個列表越大所包括的資源就越多。

把事例列表存儲在哈希表中，通過IP地址進(jìn)行檢索，以矢量形式存儲資源ID。因此，要對每個節(jié)點(diǎn)的資源進(jìn)行線性編號。采用這種數(shù)據(jù)結(jié)構(gòu)，事例列表能夠根據(jù)所需內(nèi)存和所要求操作進(jìn)行有效的存儲。

1.4 網(wǎng)絡(luò)中節(jié)點(diǎn)的加入和離開

從兩個角度來分析節(jié)點(diǎn)的加入和離開：網(wǎng)格層和P2P層。其中網(wǎng)格層主要指VO內(nèi)部節(jié)點(diǎn)的變化，P2P層主要是PS服務(wù)節(jié)點(diǎn)的變化。PS服務(wù)節(jié)點(diǎn)的變化由CS服務(wù)實現(xiàn)，當(dāng)有新的PS節(jié)點(diǎn)加入時首先向CS注冊，同時獲得幾個其他PS的GSH，這些PS成為其鄰居節(jié)點(diǎn)，在網(wǎng)絡(luò)中找到該位置完成加入；離開時要向已注冊的CS發(fā)消息，使CS去掉該節(jié)點(diǎn)的地址信息。VO內(nèi)部節(jié)點(diǎn)的變化可以通過服務(wù)數(shù)據(jù)的通知機(jī)制來實現(xiàn)，基本原理可參照文獻(xiàn)[4,5]。

1.5 概念查詢

概念查詢分為簡單概念查詢和復(fù)雜概念查詢兩種。簡單概念查詢中最主要的問題是怎樣找到請求者所需求的概念事例節(jié)點(diǎn)。首先，要看決定節(jié)點(diǎn)簡單概念定義的主要因素。其次，使用基本函數(shù)功能（一般指并、交和差）來提供查詢的定義。根據(jù)概念名稱在哈希表中的值來選擇查詢所需要的節(jié)點(diǎn)，找到的節(jié)點(diǎn)具有該概念的事例。

復(fù)雜概念查詢是在簡單概念并、交和差的基礎(chǔ)上根據(jù)概念定義形成的。在網(wǎng)絡(luò)中連續(xù)訪問復(fù)雜概念定義中包含的每個簡單概念，并在此基礎(chǔ)上從底向上構(gòu)造復(fù)雜概念的事例列表。當(dāng)概念進(jìn)行聯(lián)合或交操作時，可以對每個概念進(jìn)行或和與操作。復(fù)雜概念查詢中邏輯非的處理有兩種不同的方式：如果非和與一起出現(xiàn)，例如A∩?B，事例列表就可以被刪除；如果非單獨(dú)出現(xiàn)或和邏輯或一起連用，例如A∪?B，B就將從Resource的事例列表中刪除，因為Resource事例列表已包括了所有節(jié)點(diǎn)有關(guān)B的列表。非操作無效，無論資源的類型是什么，Resource事例列表中都會包括該資源的事例。根據(jù)復(fù)雜概念事例列表和上述規(guī)則可以實現(xiàn)復(fù)雜概念查詢。

2 實驗結(jié)果

通過模擬幾種網(wǎng)絡(luò)情況，得出了該方法的執(zhí)行圖，解決了下面的問題：

(1)一個查找請求需要多長時間才能找到滿足需要的資源？

(2)新消息公布的過程中網(wǎng)絡(luò)能傳播多少信息？

模擬產(chǎn)生了一個隨機(jī)的分類DAG，該圖能夠在節(jié)點(diǎn)中傳播，因此每個節(jié)點(diǎn)都擁有DAG的子圖和該圖的一些事例。根據(jù)這種情況，通過改變節(jié)點(diǎn)個數(shù)、DAG大小和事例個數(shù)，模擬了網(wǎng)絡(luò)中信息的傳播情況，計算出不同大小的DAG下，隨著節(jié)點(diǎn)個數(shù)的增加消息的迭代次數(shù)和消息傳送量。在保持每個固定節(jié)點(diǎn)事例個數(shù)不變情況下，增加了總的事例個數(shù)，如圖7和8所示。X軸表示節(jié)點(diǎn)的個數(shù)，它由相應(yīng)事例的個數(shù)決定，Y軸分別表示的是迭代次數(shù)和消息傳送量，需要注意的是節(jié)點(diǎn)個數(shù)不是線性變化的。每種情況運(yùn)行10次，為了避免隨機(jī)產(chǎn)生DAG所帶來的特殊影響，圖中的值是10次運(yùn)行的平均值，因此迭代次數(shù)和消息傳送量可能不是整數(shù)。

圖7 迭代次數(shù)

圖7說明迭代次數(shù)隨節(jié)點(diǎn)個數(shù)的增加變化不明顯，由于實驗中事例是隨機(jī)傳送的，所以當(dāng)節(jié)點(diǎn)個數(shù)增加時，要重新計算迭代次數(shù)。迭代次數(shù)隨著概念個數(shù)的增加，變化也不明顯。從圖中可以看出，552個概念下，計算迭代次數(shù)的平均值大約為9.3，而50733概念下迭代次數(shù)的平均值大約為15.3。把迭代次數(shù)為1.6所對應(yīng)的節(jié)點(diǎn)個數(shù)和節(jié)點(diǎn)個數(shù)為90兩種情況進(jìn)行比較發(fā)現(xiàn)，當(dāng)概念以DAG形式組織時，僅當(dāng)最長路徑和迭代次數(shù)相關(guān)時，結(jié)果才很明顯。

圖8 消息量

圖8表明消息傳送量的增長和節(jié)點(diǎn)個數(shù)的增加很協(xié)調(diào)。從圖中可以看出，552個概念時，隨著節(jié)點(diǎn)個數(shù)的增加，消息傳送量的變化很??；50733個概念時，消息傳送量隨節(jié)點(diǎn)個數(shù)的變化就很明顯，而且基本上是成比例的，這說明概念個數(shù)越多，消息傳送量的增長和節(jié)點(diǎn)個數(shù)的增加越協(xié)調(diào)。

3 結(jié)束語

本文提出一種動態(tài)網(wǎng)格環(huán)境中資源查找方法，通過本體來描述資源，在分布式哈希表的基礎(chǔ)上實現(xiàn)節(jié)點(diǎn)之間信息傳播。如果資源提供者不在網(wǎng)格范圍內(nèi)，可以結(jié)合可傳輸?shù)腄AG圖內(nèi)所有節(jié)點(diǎn)的知識來實現(xiàn)資源查找。通過模擬獲得了網(wǎng)絡(luò)傳播新信息時系統(tǒng)的行為和當(dāng)概念個數(shù)發(fā)生變化時系統(tǒng)數(shù)值的變化范圍。但該方法的使用范圍還受到以下因素的限制：完備性、查找的表示、容錯情況、垃圾的收集和傳遞的優(yōu)化，所以將進(jìn)一步改進(jìn)使它不再受這些條件的限制。

[1]A. Vidal, and S. Kofuji, “Semantics-Based Grid resource Management”[C]. In Procedings of5th International Workshop on Middleware for Grid Computing-MGC’07, Newport Beach, CA, USA, Nov26, 2007

[2]P. Wieder, W.Ziegler, “Bringing Knowledge to Midleware –Grid Scheduling Ontology”[C]. In Proceedings of the Workshop on Future Generation Grids, Nov. 1-5,2004, Dagstuhl, Germany, Springer, 2006:47～59

[3]Borja Sotomayor.The Globus Toolkit 4 Programmer’s Tutorial[EB/OL].http://www.casa-sotomayor.net/gt4- tutorial-wo-rking/, 2005

[4]Domenico Talia, Paolo Trunfio.Web Services for Peer-to-Peer Resource Discovery on the Grid[C].DEIS,University of Calabria’s, Rende, Italy

[5]Professional Open Source Middleware for Parallel,Distributed, Multithreaded Programming[EB/OL].http://proactive.inr- ia.fr

[6]孫帥，董小社，楊凡，等.基于三層P2P結(jié)構(gòu)的網(wǎng)格資源發(fā)現(xiàn)模型[J].微電子學(xué)與計算機(jī)，2005，8：127～129

Abstract: We present a new approach to semantic resource discovery in the grid in this paper. A peer-to-peer network is used to distribute and query the resource catalogue. Each peer can provide resource descriptions and background knowledge, and each peer can query the network for existing resources. We do not require a central ontology for resource description and matching. Each peer may have its own ontology, which will be completed by the knowledge distributed over the network. And it can be argued that this network has excellent scalability.

Key words: grid; resource management; semantic; ontology; query; location

Research for grid resource discovery in P2P network based on ontology-driven

Li Yanpeng, Zhong Junkai, Wei Hui
Jining vocational technology college, Jining, 272037, China

2010-08-16

李艷鵬，碩士，助教。鐘軍凱，碩士，助教。魏慧，本科，助教。