無結構P2P網絡中一種高效的資源搜索機制*

趙佩章，張同光

（新鄉學院計算機與信息工程學院 新鄉 453003）

1 引言

近來P2P網絡飛速發展，已成為互聯網中最流行的應用之一。作為一個分布式的網絡，其效率在很大程度上依賴于資源搜索的機制。盡管近年來關于P2P資源搜索的研究很多，但是在資源搜索方面一直存在很多需要解決的問題[1]。通常情況下，結構化P2P網絡更傾向于采用DHT（distributed hash table，分布式散列表)的搜索方式；對于無結構P2P網絡來說，例如Gnutella[2]，資源搜索主要是使用洪泛（flooding）或者有一定控制的洪泛來進行，如隨機走（random walk）[3]，由于這樣會在資源搜索過程中訪問大量不相關的節點，因此造成較低的搜索效率。為了提高無結構P2P網絡資源搜索效率，研究人員提出了許多搜索機制[4～7]，但是這些搜索機制都沒有考慮到節點之間語義的相關性，因此這些搜索機制仍然具有較高的搜索開銷。

在語義相關的P2P網絡中，相關的節點連接在一起，形成一個語義組。GES[8]和CSS[9]兩種搜索機制都使用VSM（vector space mode，向量空間模型）[10]來計算節點的語義相關度。GES首先會對每一個節點進行矢量抽取，然后借助于VSM來計算節點間語義相關度，并依據計算出來的語義相關度數值生成網絡拓撲，最后采用語義目標節點定位和洪泛相結合的搜索方式。CSS在GES的基礎上，將每個節點按照所含內容的不同種類再細分為更小的虛擬節點，此法雖然可以提高資源查詢的精準度，但是虛擬節點的引入卻極大地增加了網絡的開銷。

在本文中，提出了一種新穎高效的資源搜索機制SKIP。在GES和CSS中，當通過biased walk（偏好查找）方法找到一個語義目標節點后，使用洪泛的方式在語義組中進行查詢。本文提出的SKIP搜索機制將使用K-層迭代優先選擇的方法來取代GES和CSS中的洪泛方式，同時，在整個拓撲結構的維護中，SKIP與GES所產生的開銷相同，SKIP在查準率和查詢開銷上的表現要優于GES，而CSS卻要產生更大的虛擬節點開銷。

2 相關研究

一般來說，P2P網絡分為結構化P2P網絡和無結構P2P網絡兩種。對于結構化P2P網絡來說，通常使用DHT技術，例如CAN[11]、Pastry[12]和Chord[13]都是使用DHT對資源進行搜索。DHT方法盡管有著較高的搜索效率，但是它只能對關鍵字進行精確匹配，無法進行語義相關的查詢。無結構P2P網絡，例如Gnutella，能夠使用語義相關信息來進行資源搜索，但是其搜索的效率卻比較低。

當前無結構P2P網絡被廣泛應用，對于無結構P2P網絡的搜索來說，主要有盲目搜索和非盲目搜索。盲目搜索算法,是不依靠任何提示信息而對其所有鄰居節點或者部分鄰居節點進行盲目的消息轉發，直到滿足停止的條件，如洪泛、random walk、BFS（breadth first search,寬度優先搜索）[14]等。非盲目搜索算法主要是路由索引[15]的方式。

為了減少洪泛的使用和提高搜索效率，一些搜索算法引入了歷史查詢信息。參考文獻[16,17]所述算法是基于興趣定位的搜索算法，假設節點A中有節點B需要的某一類內容，那么節點A中的另外一些類的內容也是節點B所感興趣的，在節點B發起搜索查詢時，首先會將查詢請求消息發送到節點A中。參考文獻[18]提出了一種SON（semantic overlay network，語義覆蓋網絡）的搜索機制，對網絡中的每個節點所包含的內容進行分類，并向全網絡廣播。每一個新加入的節點都需要廣播，這樣極大地增加了網絡開銷。

還有一些P2P搜索機制，如SETS（search enhanced by topic segmentation,話題分割搜索）[9]，它是采用超級節點方式，每個超級節點負責一類的內容，同時根據普通節點所含不同的內容連接到不同的超級節點上。SETS的搜索路由分為全局路由和本地路由。全局路由就是在不同的超級節點之間進行路由，尋找不同類的內容；本地路由就是主要在某一個超級節點的范圍內進行洪泛查詢。由于采用超級節點的方式，因此單點失效是SETS機制的一個致命問題。GES[5]采用分布式的方法，并且通過語義相關性建立連接，形成語義組。在進行資源搜索時，GES使用biased walk算法找到目標語義節點，通過目標語義節點在語義組中進行洪泛查詢。在GES的基礎上，有研究人員提出了CSS[15]，CSS把每一個節點里面不同種類的內容再分成不同的虛擬節點，這樣提高了查詢的效率，但是卻忽略了分割虛擬節點的開銷。

3 VSM的背景介紹

VSM[10]是一種使用節點所包含的關鍵詞來表示節點內容的方法。在VSM方法中，使用關鍵詞的矢量來表示每一個文檔或者查詢消息，通過余弦內積和的計算方法來判斷是否語義相關，對于一個文檔D和查詢消息Q來說，其計算方法為：

在式（1）中，t是在文檔D和查詢消息 Q中同時出現的關鍵詞，fD,t是關鍵詞t在文檔 D中的權重，fQ，t是關鍵詞t在查詢消息Q中的權重。

4 SKIP設計

在這一部分中，將詳細闡述SKIP，分為節點矢量、拓撲構建和搜索協議3個子部分。

4.1 節點矢量

對于每一個節點來說，把它的關鍵詞按照權重抽取出來，形成節點矢量，使用節點矢量來表示這個節點的內容。使用VSM來計算節點矢量間的語義相關度。首先，對于一個節點中的每一個文檔按權重抽取出關鍵詞，每一個關鍵詞的權重根據該關鍵詞在文檔中出現的頻率來確定；其次，對于一個節點來說，將節點中每個文檔的帶權重關鍵詞加起來，便得到該節點的權重關鍵詞，其計算方法為在這里，n是該節點中文檔數目，t是各個文檔相同的關鍵詞。最后，把所有按照上述方法計算出來的帶權重關鍵詞組合在一起，便形成了該節點的節點矢量。

以節點X和節點Y為例，它們的節點間語義相關度用節點矢量的計算方式如下：

在式（2）中，t是在節點X的節點矢量和節點Y的節點矢量中共同擁有的關鍵詞。fX,t是關鍵詞t在節點X中的權重，fY，t是關鍵詞t在節點Y中的權重。如果通過式（2）計算出來的相關度數值大于或等于某一個門限值，那么這兩個節點被認為是語義相關，反之，則不相關。

同樣，可以用如下的式子來計算節點X和查詢消息Q之間的相關度：

4.2 拓撲構建

每一個節點有兩類鄰居：一類是隨機鄰居，即是通過式（2）計算出來的語義相關度數值小于設定的相關度門限值REL_THRESHOLD；一類是語義鄰居，即通過式（2）計算出來的語義相關度數值大于或等于設定的相關度門限值REL_THRESHOLD。拓撲構建的目標有兩個，一是把語義相關的節點通過語義連接組成語義組，二是每個節點保持一定數目的隨機連接以便于發現新的語義連接。拓撲構建算法包含兩個部分，一個是鄰居發現部分，另一個是鄰居維持部分。

在鄰居發現部分，起始節點會發起一個消息，該消息包含有本節點的節點矢量信息、語義相關度門限值REL_THRESHOLD、TTL（time-to-live，生命周期）等，該消息將隨機地發送給其他節點。當消息到達一個節點后，該節點將會用式 （2）計算與起始節點的語義相關度，然后把TTL的數值減去1，再隨機地發送出去，直到TTL的數值等于0，這條消息將會被丟棄。

MAX_SEM_LINKS是每個節點允許的最大語義鄰居連接數，MAX_RND_LINKS是每個節點允許的最大隨機鄰居連接數。同時，每個節點有2個鄰居候選cache：一個是隨機鄰居cache；一個是語義鄰居cache。根據式（2）計算出來的語義相關度數值，該節點將會被起始節點按照是否語義相關分別放入隨機鄰居cache和語義鄰居cache中，起始節點將會從語義鄰居cache中選擇語義相關度最高的前MAX_SEM_LINKS個語義相關節點作為它的語義鄰居；同時從隨機鄰居cache中隨機選擇MAX_RND_LINKS個節點作為隨機鄰居。對于語義鄰居，起始節點會將它們按照語義相關度的數值從高到低進行排序。

在鄰居維持部分，其任務就是從鄰居候選cache中選擇新的鄰居以及保持現有符合要求的鄰居。每個節點會周期性地從它的語義鄰居cache中選擇新的語義鄰居來更新它的語義鄰居連接，其算法為adapt_sem_neighbors()，需要注意的是，當語義相關度數值大于或等于門限值REL_THRESHOLD的節點數大于最大語義鄰居連接數MAX_SEM_LINKS時，起始節點將選擇相關度最高的前MAX_SEM_LINKS作為新的語義鄰居。同理，節點的隨機鄰居數也不能超過MAX_RND_LINKS。節點的鄰居重新連接后，每個節點根據語義相關度的數值從高到低對語義鄰居進行排序。在圖1中，給出了鄰居拓撲調整與維持的偽代碼。

圖1 鄰居調整與維持的偽代碼

4.3 搜索協議

SKIP資源搜索定位查詢算法的主要思想簡言之就是：優先搜索查詢語義相關度最高的那部分節點。

當一個節點發起查詢請求時，首先使用biased_walk()函數找到語義目標節點，然后再發起SKIP查詢，具體如下。

用M（M≤MAX_SEM_LINKS）來表示某一個節點的語義鄰居個數，然后將該節點的所有語義鄰居按照之前網絡拓撲構建時計算出來的節點之間的語義相關度數值進行排序，排序的規則是按節點之間語義相關度數值從高到低進行排序。排完序之后，將這些語義鄰居按照語義相關度數值由高到低平均分成m個子組。當查詢消息找到語義目標節點后，就是從目標節點語義相關度最高的一個子組，即語義相關度數值最高的[M/m]個語義鄰居（在這里[]表示高斯取整函數）開始繼續進行資源搜索定位查詢。

資源搜索定位查詢消息每轉發一次，其生命周期TTL的數值將被減去1，當TTL=0時，資源搜索定位查詢消息將不再轉發，而被直接丟棄。如果通過第一個子組的語義最相關的[M/m]個語義鄰居的查詢后，仍然沒有滿足要求，那么目標節點將會從第二個語義子組開始轉發資源搜索定位查詢消息，直到搜索查詢到的滿足要求；若仍然無法滿足源節點的資源搜索查詢請求，將從第3個子組繼續往下搜索查詢；以此類推。

值得注意的是，資源搜索定位查詢消息每往下轉發一次，相當于往下一層迭代了一次，因為在下一層的每一個節點，同樣地將會把自己的語義鄰居節點按照語義鄰居節點之間的語義相關度數值進行排序，排序的規則是從高到低。在對該節點的所有語義鄰居按照之前網絡拓撲構建時計算出來的節點之間的語義相關度數值排完序之后，將這些語義鄰居按語義相關度數值由高到低平均分成m個子組。資源搜索定位查詢消息將會按照語義相關度數值最高的[M/m]個語義鄰居優先選擇的機制，在下一層語義鄰居節點中繼續查找，一旦找到滿足源節點要求數量的語義相關資源時，查詢立即終止。圖2是biased_walk()和SKIP資源搜索定位查詢算法的偽代碼。

如圖3所示，以語義子組數m=2，最大語義鄰居鏈接數MAX_SEM_LINKS=4為例，介紹一下搜索路徑。圓形節點為語義相關的語義鄰居，方形節點為語義不相關的隨機鄰居。當查詢消息找到語義相關的目標節點X后，該資源搜索定位查詢消息將會用式（3）、（4）計算節點X中的每一個資源文檔與這個資源搜索定位查詢消息的語義相關度。虛線是語義相關度最高的子組，黑體實線是語義相關度次高的子組，首先會從虛線子組開始查詢，若查詢到的結果滿足要求，查詢終止；若不滿足，則從黑體實線子組繼續查詢。

圖2 搜索協議偽代碼

5 仿真結果

在測試數據的選取上，使用TREC[19]作為仿真實驗中的測試數據。TREC是一個在信息資源檢索領域廣泛使用的標準數據集。在仿真實驗中，主要采用查準率（即最大相關資源數/獲取總的相關資源數）和查詢開銷（即訪問節點數）作為實驗的性能指標來衡量SKIP搜索算法的優勢。

表1中列出了相關實驗參數的設置。

表1 搜索策略仿真實驗參數

仿真實驗結果如圖4、圖5所示。GES方式只對應m=1時情況。SKIP搜索方式對應m=1,2,3,4時的情況

從圖4中可以清楚地看到，對于同樣的資源搜索定位查詢消息生命周期TTL值，當語義子組參數m的值從1遞增到4時，GES搜索查詢算法的查準率是最低的。而對于SKIP資源搜索定位查詢算法來說，m的值越大，查準率越高。換句話說，隨著語義子組數的增加，也就是m值的增加，SKIP資源搜索定位查詢算法將使用更小的粒度來進行優先選擇搜索，因此，其資源的查準率也將越高。

從圖5中可以清楚地看到，當TTL的值較小（TTL=1以及TTL=2）時，SKIP算法與GES算法的查詢開銷的差別不是太大。但是，當TTL的值增加時，GES的開銷迅速上升，而SKIP算法的查詢開銷卻仍然保持在一個較低的狀態。換句話說，GES查詢消息在資源搜索時，訪問了大量的節點，造成了巨大的開銷；反觀SKIP查詢算法，在完成相同的查詢任務的情況下，極大地減少了查詢消息對于節點的訪問量，減小了搜索查詢的開銷。

綜上所述，SKIP查詢算法與GES查詢算法相比，優先選擇語義相關度更高的部分語義鄰居節點進行搜索定位查詢，具有更好的資源查準率和更低的查詢開銷。

6 結束語

在本文中，提出了SKIP資源搜索算法，由于其采用優先選擇與層層迭代的方式，具有很高的查詢效率和較低的查詢開銷。仿真實驗也顯示了SKIP在查準率和查詢開銷方面優于GES。將來，筆者還要考慮異構環境下的拓撲構建和搜索策略。

1 Risson J,Moors T. Survey of research towards robust peer-to-peernetworks:search methods.ComputerNetworks,2006,50(17):3 485～3 521

2 Gnutella 0.6.http://rfc-gnutella.sourceforge.net/src/rfc-06-draft.html

3 Yang B,Garcia-Molina H.Improving search in peer-to-peer networks.Proceedings of the ICDCS 2002,Vienna,Austria,2002:5～14

4 Lv Q,Cao P,Cohen E.Search and replication in unstructured peer-to-peer networks.Proceedings of 16th ACM Ann Int’l Conf Supercomputing(ICS),New York,USA,2002:84～95

5 Cohen E,Kaplan H,Fiat A.Associative search in peer-to-peer networks:harnessing latent semantics.Proceedings of IEEE INFOCOM,2003,2(4):1 261～1 271

6 SpripanidkulchaiK,MaggsB,Zhang H.Efficientcontent location using interest-based locality in peer-to-peer systems.Proceedings of IEEE INFOCOM,2003,3(3):2 166～2 176

7 Bawa M,Manku G,Raghavan P.SETS:search enhanced by topic segmentation.Proceedings of26th Ann Int’l ACM SIGIR Conf,Toronto,Canada,2003:306～313

8 Zhu Y,Hu Y.Enhancing search performance on gnutella-like P2P systems.IEEE Transactions on Parallel and Distributed Systems,2006,17(12):1 482～1 495

9 Guo L,Jiang S,Xiao L,et al.Exploiting content localities for efficient search in P2P systems.Proceedings of 18th Ann Conf Distributed Computing (DISC’04),Amsterdam,Netherlands,2004

10 Berry M W,Drmac Z,Jessup E R.Matrices,vector spaces,and information retrieval.SIAM Review,1999,41(2):335～362

11 Ratnasamy S,Francis P,Handley M,et al.A scalable content addressablenetwork.ProceedingsofACM SIGCOMM,San Diego,CA,USA,2001:161～172

12 Rowstron A,Druschel P.Pastry:scalable,distributed object location and routing for large-scale peer-to-peer systems.Proceedings of the 18th IFIP/ACM International Conference on Distributed System Platforms (Middleware), Heidelberg,Germany,2001:329～350

13 Stoica I,MorrisR,KargerD,etal.Chord:a scalable peer-to-peer lookup protocol for internet applications.IEEE/ACM Transactions on Networking,2003,11(1):17～32

14 Crespo A,Garcia-Molina H.Routing indices for peer-to-peer systems.Proceedings of the 22nd International Conference on Distributed Computing(IEEE ICDCS’02),Vienna,Austria,2002

15 Crespo A,Garcia-Molina H.Semantic Overlay Networks for P2P Systems.Technical Report,University of Stanford,May 2004

16 Risson J, Moors T.Survey of research towards robust peer-to-peernetworks:search methods.ComputerNetworks,2006,50(17):3 485～3 521

17 HuangJ,LiX,Wu J.A class-based search system in unstructured P2P networks.Proceedingsofthe IEEE 21st International Conference on Advanced Information Networking and Applications,2007:76～83

18 Guo L,Jiang S,Xiao L,et al.Fast and low cost search schemes by exploiting localities in P2P networks.Parallel and Distributed Computing,2005,65(6):729～742

19 Text REtrieval Conference(TREC).http://trec.nist.gov