基于小世界現象的P2P網絡搜索研究

劉艷艷等

摘 要：本文依據小世界特性提出了一種P2P網絡搜索引擎系統模型，并給出了系統模型中對等網絡節點的拓撲結構，提出了一種搜索機制，使查詢消息更高效的傳播，實驗數據說明本文搜索機制與洪泛算法相比更加有效。

關鍵詞：小世界； P2P網絡；搜索；簇

中圖分類號： TP393.2 文獻標識碼：A

1 引言（Introduction）

非結構化P2P[1]在搜索方面的優勢，引導人們開發基于對等網絡的強大的搜索工具。其廣泛采用的洪泛（Flooding）搜索機制[2]，查詢從一個節點以廣播方式傳播到其他節點，直到查找到查詢結果，從而導致每次查詢都產生大量的網絡流量，對網絡造成很大的負擔，影響了非結構化P2P系統的擴展性。本文依據P2P網絡的小世界現象，提出一種搜索機制，以提高查詢效率。

2 小世界現象（Small-world）

小世界[3，4]（SW：Small-world）現象簡單地講就是社會網絡中任意兩個陌生人之間，經過較少的中間相識者就有可能建立起聯系。這種現象在社會科學中發展成為一個重要的研究領域以后，經過許多次成功實驗，證實在一個成功的通信鏈中，中間步驟的平均數總在5和6之間，稱為“6度原理”。一些文獻表明，P2P網絡有時會自動演進到一個小世界[5]。

基于小世界現象構造的模型稱為小世界模型，小世界模型基于這樣一個原則：每個節點都表現出某些可以捕捉到的興趣，興趣相近的節點所保存的內容和提交的查詢呈現出一定的相關性，通過挖掘每個節點的興趣，使得相關性高的節點在網絡中比較接近。這種按照節點間相關性組成的網絡所表現出和社會網絡相近的特性——具有較高的聚集度和存在短鏈，即所謂的小世界特性，小世界特性被證明對于提高檢索效率是非常有效的。

3 基于小世界現象的P2P網絡搜索引擎模型（P2P

network search engine model based on small

world phenomenon）

P2P網絡的搜索引擎關鍵是對共享內容的深度挖掘，在對等節點之間進行信息檢索時快速高效地進行信息反饋，要求尋找網絡中對等節點之間的短路徑。

在P2P網絡搜索引擎系統模型設計時，考慮小世界模型簇聚合以及存在短鏈特點。簇聚合意味著具有度數較高的對等節點，這類對等節點在網絡中的連通性較好，作為搜索引擎中的索引服務器保存文檔的索引信息。存在短鏈意味著能夠通過短鏈進行信息的檢索和作為反饋路由。同時還考慮網絡中資源信息本地化管理，資源信息搜索由本地網絡發起進行全局檢索，結合小世界模型構建如圖1所示的小世界P2P網絡搜索引擎系統模型。

圖1描述的搜索引擎系統模型以P2P小世界網絡為中樞，將信息搜索和對等點中共享的資源信息聯系起來，整個系統模型分為三個層次：用戶層（用戶界面）、網絡層（緩存、P2P網絡、信息搜索和文件傳輸）以及文件處理層（文件處理和共享）。系統模型中信息搜索模塊采用語義檢索算法進行文檔資源的信息搜索；文件傳輸模塊主要是把文檔進行分組傳送和一般的網絡數據傳輸相同；界面模塊主要是采集用戶查詢請求。

5 實驗分析（Experimental analysis ）

5.1 實驗條件

模擬實驗在自行構造小世界網絡拓撲中進行文檔的中文文檔主題搜索，即搜索符合查詢請求的文檔主題信息，網絡拓撲和文檔主題數具體實驗參數如表1所示，在構造的網絡拓撲上實現泛洪式的Query Routing算法和本文提出的使用小世界網絡中度數較高的節點進行關鍵字查詢搜索，從查全率和查詢產生的消息量兩個方面對兩種搜索方式進行比較。

實驗中按照關鍵字進行查詢，將文檔主題進行簡單分詞處理，并對分詞得到的關鍵字在每個節點中建立索引，在小世界網絡中度數較高的節點對本簇中所有節點的關鍵字建立索引關聯文件，將關鍵字、文檔ID源文檔IP地址和源文檔端口號建立聯系，實現快速定位，索引關聯文件結構如表2所示。

5.2 實驗結果及分析

實驗1控制TTL值，隨機選擇20個節點發起查詢，統計每次查詢產生的查詢消息量，最后計算平均值，實驗結果如圖3所示。

實驗結果表明在相同TTL值的條件下本文提出的搜索機制搜索產生的查詢消息量比Query Routing算法泛洪式搜索產生的查詢消息量少。

實驗2控制TTL值，隨機選擇20個節點發起查詢，統計每次查詢返回的文檔主題數量，最后計算平均值，實驗結果如圖4所示。

實驗結果表明在相同TTL值的條件下本文提出的搜索機制查詢返回的文檔主題數量比Query Routing算法泛洪式搜索返回查詢結果數量多。

從實驗中可以得出如下結論：在自行構造的小世界網絡中，在相同TTL相同的情況下，本文使用度數較高節點搜索查詢產生的消息量是使用全分布式無結構P2P網絡的Query Routing算法泛洪式搜索的50%—60%，而進行關鍵字查詢返回的結果文檔主題數平均是Query Routing算法泛洪式搜索的1.37倍，即查全率為Query Routing算法的1.37倍。

6 結論（Conclusion）

本文在研究分析小世界模型特性的基礎上提出了基于小世界模型的P2P網絡搜索引擎系統模型，在此基礎上提出了一種搜索機制，即使用小世界網絡中度數高的節點進行消息傳遞的步驟數會減少，從而查詢產生的消息量少，通過實驗進一步驗證了這一機制。但是由于進行的是關鍵字的查詢，查詢結果中存在非查詢意圖的搜索結果，查詢的滿意度有待提高。

參考文獻（References）

[1] 羅杰文.Peer to Peer綜述.中科院計算技術研究所，2005：2-3.

[2] 楊天路，等.P2P網絡技術原理與系統開發案例[M].北京：人民

郵電出版社.

[3] （德）Ralf Steinmetz，等.王玲芳，等，譯.P2P系統及其應用[M].北

京：機械工業出版社，2008.

[4] 周晉，等.基于Small-World網絡的非結構化DHT算法.國家自

然科學基金項目（60003004），2005：109-117.

[5] 雷勇，李薇.基于小世界與興趣相關度的P2P網絡搜索研究

[D].微型機與應用，2012（18）：42-44.

[6] 杜麗娟，史定華，陳倩.增長的可導航網絡模型[D].上海大學

學報（自然科學版），2009，15（1）：20-25.

作者簡介：

劉艷艷（1982-），女，碩士，工程師.研究領域：軟件工程.

李洪建（1981-），男，學士，高級工程師.研究領域：軟件

技術及網絡工程.

代興義（1981-），男，碩士，高級工程師.研究領域：計算

機應用及軟件開發.