基于本體的P2P網(wǎng)絡(luò)資源檢索算法研究

雷 申，劉方愛

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟南250014；2.山東省分布式計算機軟件新技術(shù)重點實驗室，山東 濟南250014）

0 引 言

P2P（peer－to－peer）系統(tǒng)的應(yīng)用都依賴于系統(tǒng)的搜索效率，而P2P網(wǎng)絡(luò)中資源如何被高效的定位仍然是P2P應(yīng)用面臨的巨大挑戰(zhàn)［1］。P2P網(wǎng)絡(luò)可以分為非結(jié)構(gòu)化P2P網(wǎng)絡(luò)和結(jié)構(gòu)化P2P網(wǎng)絡(luò)［2］。非結(jié)構(gòu)化P2P網(wǎng)絡(luò)基于洪泛等算法進行路由，路由效率低且擴展性差［3］。而結(jié)構(gòu)化P2P網(wǎng)絡(luò)（如 Chord［4］、CAN［5］等）通過 DHT （distributed hash table）進行路由，相對無結(jié)構(gòu)化P2P網(wǎng)絡(luò)具有查詢速度快、路由延遲低、擴展性能好［6］等優(yōu)點。而DHT網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)不僅僅是節(jié)點之間的位置關(guān)系，更重要的是為節(jié)點中原本沒有位置關(guān)系的資源賦予了與節(jié)點拓?fù)湎嗨频年P(guān)系［7］。因此，在結(jié)構(gòu)化P2P中，資源可以被高效的定位，同時DHT也使查詢請求只能根據(jù)資源的關(guān)鍵字進行精確的匹配，并且不支持語義關(guān)聯(lián)檢索，缺乏模糊搜索能力，使部分查詢結(jié)果在內(nèi)容上匹配程度不高。因此，如何在基于DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)中實現(xiàn)語義層次的檢索是結(jié)構(gòu)化P2P網(wǎng)絡(luò)面臨的主要問題之一。

文獻(xiàn) ［8］構(gòu)建了一個P2P網(wǎng)絡(luò)環(huán)境下的文獻(xiàn)檢索系統(tǒng)SemreX，并提出一種基于語義相似度的P2P拓?fù)涔芾砗筒樵兟酚伤惴▉硖岣呦到y(tǒng)的搜索效率。文獻(xiàn) ［9］結(jié)合向量空間模型VSM、本體 （Ontology）與DHT技術(shù)將相似文檔聚集在臨近位置，減少了路由跳數(shù)，在一定程度上加快了檢索的速度，擴大了檢索的范圍。但是系統(tǒng)中特征向量產(chǎn)生的高維矩陣增加了計算復(fù)雜度。文獻(xiàn) ［10］針對P2P網(wǎng)格，提出了一種基于分布式網(wǎng)格本體的P2P網(wǎng)格資源匹配模型。在該模型中，全局本體由各個節(jié)點的獨立的本地網(wǎng)格資源本體構(gòu)成。網(wǎng)格資源匹配操作完全分布式地由節(jié)點自主控制。文獻(xiàn) ［11］劃分了網(wǎng)絡(luò)中資源的主題，提出了一種語義覆蓋網(wǎng)絡(luò)SSON，其基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)路由，具有可靠、高效等特點。

本文在以往研究的基礎(chǔ)上，提出一種基于DHT和本體的搜索方法SOC （semantic ontology chord），將類似文檔聚集在一起、使相同興趣的節(jié)點趨近于鄰近位置來改善搜索效率，同時支持模糊查詢。該方法具有較好的實用性和擴展性，為有組織的P2P系統(tǒng)提供了一種高效的數(shù)據(jù)查詢方法。

1 基于本體的P2P網(wǎng)絡(luò)搜索方法

1.1 本體的應(yīng)用

本體的概念來源于哲學(xué)，目前被廣泛接受的定義由Gruber給出［12］，即 “本體是概念模型的明確的規(guī)范說明”。本體就是通過對某特定領(lǐng)域內(nèi)的知識用公認(rèn)的規(guī)范進行定義，并描述這些定義與定義之間的關(guān)系，使人和機器都可處理和交流的一種知識模型。它可以包括這個領(lǐng)域都有哪些概念、這些概念都有什么屬性以及概念間的層次和關(guān)系等。本體的應(yīng)用廣泛，目前已被應(yīng)用于電子工程、化學(xué)、電子商務(wù)和數(shù)據(jù)挖掘等領(lǐng)域。

SOC可以利用 SWRC （semantic web research community ontology）［13］等 已 設(shè) 計 好 的 本 體 來 構(gòu) 建 節(jié) 點 本 體。SWRC是學(xué)術(shù)科研領(lǐng)域的一個本體，用與描述科研機構(gòu)、科研項目和出版物等概念以及它們之間的關(guān)系。利用SWRC將節(jié)點本體細(xì)化為文獻(xiàn)本體和主題分類本體兩部分。其中文獻(xiàn)本體由文獻(xiàn)的概念、屬性以及各種關(guān)系等組成；而主題分類本體則包含了對領(lǐng)域內(nèi)各種主題的分類和主題之間的關(guān)系，例如 “軟件工程”與 “計算機科學(xué)”之間是subTopicof和superTopicof的關(guān)系等。

通過節(jié)點本體，能夠較好的解決因關(guān)鍵詞精確匹配帶來的資源內(nèi)容不符等問題，使查詢請求和節(jié)點間能建立較強的語義關(guān)系，使檢索上升到語義層。對于有查詢請求的節(jié)點：可以對用戶的檢索請求進行處理和規(guī)范，根據(jù)關(guān)鍵詞對要查詢的資源進行歸類，判斷需要查詢的資源屬于哪個類別，以獲得更好的查詢效果；對于收到查詢請求的節(jié)點：可以通過請求消息計算出相近似的資源并返回，使網(wǎng)絡(luò)能夠最大限度的滿足查詢請求。

本體中兩個主題之間在語義上的相似度可以通過文獻(xiàn)［14］介紹的相似性函數(shù) （見式 （1））來計算，其通過計算兩個主題t1、t2在主題層中的位置來計算它們之間的距離，當(dāng)距離較近并高于某一個閾值時則認(rèn)為兩個主題相似。

其中α，β≥0。l是在本體的層次結(jié)構(gòu)中主題t1、t2之間的最短路徑。h是第一個包含t1、t2的父主題的層次位置。顯然l越大或h越小，t1、t2之間的相似度越??；反之亦然。α和β是參數(shù)，分別決定了最短路徑長度l和父主題層次h的影響比重，文獻(xiàn) ［14］經(jīng)過實驗表明α和β的值分別在0.2和0.6時最佳。由式 （1）可知，當(dāng)不同的主題通過計算即t1≠t2時，Sim的值越大，則t1、t2之間的相似度就越大。

1.2 SOC基本設(shè)計

Chord是MIT提出的一種典型的結(jié)構(gòu)化P2P網(wǎng)絡(luò)模型，具有映射簡單、搜索速度快等優(yōu)點。它通過一致性散列 （consistent hashing）運算將節(jié)點和文檔映射到值域為［0，2m－1］的環(huán)形結(jié)構(gòu)中，并在此基礎(chǔ)上利用DHT實現(xiàn)資源定位。SOC是從Chord模型調(diào)整而來，其網(wǎng)絡(luò)中每個節(jié)點共享一個相同的領(lǐng)域本體，并利用該本體來進行查詢請求的優(yōu)化。在Chord原有的結(jié)構(gòu)基礎(chǔ)上改進了節(jié)點維護的資源索引，使查詢時可以返回更多相近主題的結(jié)果，進而提高查全率。

Chord模型中，文件被關(guān)聯(lián)到＜Key，Value＞對，節(jié)點標(biāo)識符也采用節(jié)點名字 （如IP地址）的散列值，節(jié)點的每個資源對應(yīng)的＜Key，Value＞對被保存到與Key相近的節(jié)點標(biāo)識符的機器中，使查詢消息所代表的資源對象與節(jié)點地址相關(guān)聯(lián)。當(dāng)有新節(jié)點加入網(wǎng)絡(luò)或者有新的資源關(guān)聯(lián)到＜Key，Value＞對時，將對應(yīng)的＜Key，Value＞對轉(zhuǎn)移到更相近的節(jié)點上，節(jié)點離開時其保存的＜Key，Value＞也會轉(zhuǎn)移到相鄰的節(jié)點。

SOC保持原有放置機制不變，將＜Key，Value＞對改進為＜Class，Key，Value＞，Class是節(jié)點通過共享的領(lǐng)域本體對資源進行規(guī)范和處理后的分類信息的散列值，資源文件將會由Class和Key確定。此時節(jié)點的每個資源對應(yīng)的＜Class，Key，Value＞信息將被保存到與Class相近的節(jié)點標(biāo)識符的機器中，而原本散列關(guān)鍵詞得到的Key因查詢需求不進行散列。在查詢的過程中，節(jié)點將包含Class和Key的請求發(fā)送到與Class鍵值最接近的節(jié)點上，目標(biāo)節(jié)點將同一Class下與Key相近的＜Class，Key，Value＞返回。源節(jié)點根據(jù)返回的Value信息找到放置資源的節(jié)點進行資源傳輸。

SOC中每個節(jié)點除維護原有的路由信息外還維護著一張興趣節(jié)點表，其保存了提供資源的節(jié)點的歷史傳輸信息，即通過Class查詢后得到的Value中成功提供資源的節(jié)點信息。事實上，若同一個節(jié)點在一定時間范圍內(nèi)總是能滿足另一個節(jié)點的查詢請求，那么這兩個節(jié)點有可能具有較為相似的興趣；另一方面，如果節(jié)點在查詢時優(yōu)先向有相同興趣的節(jié)點發(fā)送請求，那么得到匹配資源的幾率會增大。節(jié)點在查詢時可以先向興趣節(jié)點表中記錄的節(jié)點發(fā)送查詢請求，目標(biāo)節(jié)點在收到請求時通過一定算法計算出與請求最接近的資源信息后返回。

1.3 SOC中的路由

SOC初始時路由算法與Chord模型類似，在SOC中節(jié)點同樣需要保存m個其它節(jié)點的信息，這些信息的集合稱為查詢表，表格中節(jié)點的間距以2k－2的關(guān)系排列 （k是表中的數(shù)組下標(biāo)）。節(jié)點將自身資源的＜Class，Key，Value＞保存到標(biāo)識符與Class鍵值相近的節(jié)點上并維護，在查詢時將包含Class和Key的請求信息發(fā)送給對應(yīng)節(jié)點即可。節(jié)點在查詢到需要的資源后，記錄提供資源節(jié)點信息到興趣節(jié)點表，在下一次查詢時先向興趣節(jié)點表中的節(jié)點發(fā)送查詢請求，這樣將有較大幾率獲得期望結(jié)果。下面是路由算法的詳細(xì)過程：

（1）當(dāng)節(jié)點A有查詢請求時，通過節(jié)點本體處理查詢關(guān)鍵詞，得到關(guān)鍵詞在相關(guān)領(lǐng)域內(nèi)的分類信息，然后將分類信息散列為Class鍵值。

（2）如果節(jié)點的興趣節(jié)點表為空，則根據(jù)查詢表將包含Class和Key的請求信息發(fā)送到與Class鍵值最接近的節(jié)點A’上，跳至 （3）；否則還需要向興趣節(jié)點表中的節(jié)點發(fā)送請求，并在請求中附加信息以證明此請求為一個興趣查詢請求，除步驟 （3）外還需要進行步驟 （4）。

（3）收到查詢請求的節(jié)點X根據(jù)Class鍵值與自身存儲鍵值比較，如果吻合，則通過本體計算出自身維護的與Key相同或相似的資源索引，并返回結(jié)果，否則返回已知與Class最相近的節(jié)點信息；重復(fù)這一步驟，直到找到相對應(yīng)的節(jié)點為止。

（4）收到帶有附加信息查詢請求的節(jié)點，根據(jù)式 （1）計算自身資源與Key對應(yīng)主題的相似度并在大于某一閾值時返回對應(yīng)結(jié)果。

（5）節(jié)點A查詢到＜Class，Key，Value＞時根據(jù)Value信息找到存儲資源的節(jié)點B并傳輸資源，并記錄節(jié)點B的地址等信息。

查詢過程的偽代碼如下：

A.Search（reqStr）｛//節(jié)點A發(fā)起發(fā)起查詢，reqStr為處理后的查詢信息

while（hasResult＝＝0）｛//無查詢結(jié)果返回時

A’＝A.find ＿matched ＿node （reqStr）；//查 找 與reqStr最匹配的節(jié)點

A.send（reqStr）； //向匹配節(jié)點發(fā)送查詢請求

if（A’.match （reqStr））｛//如果目標(biāo)節(jié)點匹配

hasResult＝1；

return result； //返回結(jié)果

｝else｛ //否則重復(fù)直到有結(jié)果返回

A＝A’；

｝

｝

if（interestTable.length＞0）｛//如果興趣節(jié)點表不為空

A.Send （reqInterestStr）；//向興趣節(jié)點發(fā)送請求

｝

｝

如圖1所示為SOC中一個節(jié)點查詢數(shù)據(jù)的過程。

圖1 SOC中節(jié)點查詢示例

1.4 節(jié)點信息維護

1.4.1 節(jié)點的加入

SOC中節(jié)點p的加入步驟與Chord類似。一般的，新節(jié)點p加入網(wǎng)絡(luò)的過程是通過網(wǎng)絡(luò)中已存在的節(jié)點p’完成的，具體情況如下：①根據(jù)Chord規(guī)則更新p的前向節(jié)點、后繼節(jié)點、網(wǎng)絡(luò)中已存在的其它節(jié)點和自身的指針表信息；②將網(wǎng)絡(luò)中歸屬于p的＜Class，Key，Value＞信息轉(zhuǎn)移到節(jié)點p上并由p維護。

一般情況下，一個節(jié)點加入網(wǎng)絡(luò)需要影響的節(jié)點數(shù)為O（logN），更新這些節(jié)點的信息需要的時間為O（log2N）。

1.4.2 節(jié)點的離開

節(jié)點的離開分為正常離開和異常離開。正常離開時會將自身保存的＜Class，Key，Value＞信息轉(zhuǎn)移到后繼節(jié)點上，然后由后繼節(jié)點負(fù)責(zé)其它節(jié)點的更新，更新策略與節(jié)點加入時相同。當(dāng)節(jié)點因特殊原因異常離開網(wǎng)絡(luò)時，會導(dǎo)致通過該節(jié)點的信息無法路由。為此，網(wǎng)絡(luò)中每個節(jié)點維護一張后繼節(jié)點表，其中包含已在網(wǎng)絡(luò)中的r個后繼節(jié)點信息。當(dāng)節(jié)點的后繼異常離開時，將后繼節(jié)點表中第一個正常節(jié)點當(dāng)作自己的后繼節(jié)點，并由它負(fù)責(zé)其它節(jié)點的更新。

1.4.3 信息的更新

節(jié)點除維護查詢表、后繼節(jié)點表和屬于自己的＜Class，Key，Value＞信息外，還需要維護一張興趣節(jié)點表。興趣節(jié)點表中保存了m個提供資源的節(jié)點與自身的歷史傳輸記錄，通常如表1所示。

表1 興趣節(jié)點表示例

表1中興趣節(jié)點地址即網(wǎng)絡(luò)中節(jié)點標(biāo)識符，查找成功率為查找成功的次數(shù)與向該節(jié)點發(fā)送查詢請求的次數(shù)的比值。另外，節(jié)點在收到興趣查詢請求時，若自身資源不能滿足請求，可以將興趣節(jié)點表中查找成功率較高的節(jié)點地址返回。興趣節(jié)點表根據(jù)提供資源節(jié)點的查詢歷史與查詢成功率來不斷更新，查詢成功率高的節(jié)點將被排在表的更上面位置。

2 仿真與分析

根據(jù)SOC的特點，基于PeerSim［15］模擬器建立實驗仿真環(huán)境，評估和分析了SOC中性能相關(guān)的參數(shù)。下面主要針對節(jié)點的查全率來測試模型的性能，并與傳統(tǒng)Chord模型相應(yīng)性能進行對比。

實驗設(shè)置了1000個節(jié)點的網(wǎng)絡(luò)規(guī)模，將含有56個主題類別的3000篇文檔隨機分配給節(jié)點，每個節(jié)點擁有文檔數(shù)量最多不超過5篇。圖2顯示了隨著模擬次數(shù)的變化，SOC與Chord的查全率的變化和比較情況。

圖2 查全率比較

圖3顯示了SOC與Chord中隨著節(jié)點的增多查全率的變化情況，這里的查全率是綜合3次實驗的平均值?？梢钥闯?，SOC相比Chord在查全率上有更好的效率。這是因為，SOC利用本體使節(jié)點支持模糊查詢，并且使興趣相近節(jié)點在網(wǎng)絡(luò)中處于臨近位置，因此實驗中相比Chord具有更高的查全率。

3 結(jié)束語

圖3 隨著節(jié)點的增多時算法查全率比較

本文基于Chord模型，針對DHT網(wǎng)絡(luò)只能進行精確關(guān)鍵詞匹配查詢的缺陷，介紹了一種基于DHT和本體的網(wǎng)絡(luò)資源檢索方法SOC （semantic ontology chord），該方法改進了DHT網(wǎng)絡(luò)中的資源標(biāo)識符，使目標(biāo)節(jié)點能夠返回更多的相關(guān)資源；利用全局共享的節(jié)點本體實現(xiàn)了模糊查詢；同時使相近興趣節(jié)點趨于臨近位置，使節(jié)點在查詢時有較大幾率獲得匹配結(jié)果。最后通過對模型進行仿真，測試了模型的性能，結(jié)果表明，該方法相比較Chord模型提高了5%－10%的查全率。

［1］WANG J Z，Bhulawala V.Design and implementation of a P2P cooperative proxy cache system ［J］.Journal of Interconnection Networks，2007，8 （2）：147－162.

［2］LAI Q.Technology of peer－to－peer network ［J］.China Science and Technology Information，2005，106 （15）：52 （in Chinese）.［賴慶.計算機對等網(wǎng)P2P技術(shù) ［J］.中國科技信息，2005，106 （15）：52.］

［3］DENG ZM.Research on P2Psearch technology ［D］.Xi’an：University of Electronic Science and Technology of China，2007（in Chinese）.［鄧祖明.P2P搜索技術(shù)研究 ［D］.西安：電子科技大學(xué)，2007.］

［4］Stoiea I，Morrs R，Karger D，et al.Chord：A scalable peer－to－peer lookup service for Internet applications ［C］.San Diego，CA，USA：ACM SIGCOMM Computer Communication Review－Proceedings of the SIGCOMM Conference，2001：149－160.

［5］Ratnasamy S，F(xiàn)rancis P，Handley M，et al.A Scalable content－addressable network ［C］.San Diego，CA，USA：ACM SIGCOMM Computer Communication Review－Proceedings of the SIGCOMM Conference，2001：161－172.

［6］HUANG QF.Performance analysis and search algorithm improvement of structured P2Pnetwork ［D］. Wuhan：Huazhong University of Science and Technology，2008 （in Chinese）.［黃慶鳳.結(jié)構(gòu)化P2P網(wǎng)絡(luò)性能分析與搜索算法研究［D］.武漢：華中科技大學(xué)，2008.］

［7］ZHOU XB，ZHOU J，LU HC，et al.A layered interest based topology organizing model for unstructured P2P ［J］.Journal of Software，2007，18 （12）：3131－3138 （in Chinese）.［周曉波，周健，盧漢成，等.一種基于層次化興趣的非結(jié)構(gòu)化P2P拓?fù)湫纬赡Ｐ?［J］.軟件學(xué)報，2007，18 （12）：3131－3138.］

［8］CHEN HH，JIN H，NING XM，et al.SemreX：A semantic similarity based P2Poverlay network ［J］.Journal of Software，2006，17 （5）：1170－1181 （in Chinese）. ［陳漢華，金海，寧小敏，等.SemreX：一種基于語義相似度的P2P覆蓋網(wǎng)絡(luò)［J］.軟件學(xué)報，2006，17 （5）：1170－1181.］

［9］WANG ZX，ZHANG DL，LIU L，et al.P2Pcomplex search based on ontology ［J］.Computer Applications，2007，27（4）：780－783 （in Chinese）.［王志曉，張大陸，劉雷，等.基于本體的P2P復(fù)雜搜索 ［J］.計算機應(yīng)用，2007，27 （4）：780－783.］

［10］LU GM，GU XF，SUN SX，et al.Ontology based resource matching in the P2Pgrid ［J］.Computer Science，2006，33（4）：75－79 （in Chinese）. ［盧國明，顧小豐，孫世新，等.基于本體的網(wǎng)格資源匹配算法研究 ［J］.計算機科學(xué)，2006，33 （4）：75－79.］

［11］YU J，WANG BQ.SSON：A Semantic overlay network structure based on the routing mechanism of structured P2P network ［J］.Computer Science，2007，134 （16）：4－6 （in Chinese）.［于婧，汪斌強.SSON：一種基于結(jié)構(gòu)化P2P網(wǎng)絡(luò)路由的語義覆蓋網(wǎng)絡(luò)結(jié)構(gòu) ［J］.計算機科學(xué)，2007，134（16）：4－6.］

［12］DU XY，LI M，WANG S.A survey on ontology learning research ［J］.Journal of Software，2006，17 （9）：1837－1847（in Chinese）. ［杜小勇，李曼，王珊.本體學(xué)習(xí)研究綜述［J］.軟件學(xué)報，2006，17 （9）：1837－1847.］

［13］York Sure，Stephan Bloehdorn，Peter Haase，et al.The SWRC ontology－semantic web for research communities ［C］.Springer，Covilha，Portugal：Proceedings of the 12th Portuguese Conference on Artificial Intelligence，2005.

［14］Liy，Mclean ZAD.An approach for measuring semantic similarity between words using multiple information sources ［J］.IEEE Transaction on Knowledge and Data Engineering，2003，15 （4）：871－882.

［15］Márk Jelasity，Alberto Montresor，Gian Paolo Jesi，et al.PeerSim P2Psimulator ［EB/OL］. ［2011－05－08］.http：//peersim.sourceforge.net.