劉艷艷等

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

關鍵詞：小世界； P2P網(wǎng)絡；搜索；簇

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

1 引言（Introduction）

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

2 小世界現(xiàn)象（Small-world）

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

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

3 基于小世界現(xiàn)象的P2P網(wǎng)絡搜索引擎模型（P2P

network search engine model based on small

world phenomenon）

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

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

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

5 實驗分析（Experimental analysis ）

5.1 實驗條件

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

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

5.2 實驗結果及分析

實驗1控制TTL值，隨機選擇20個節(jié)點發(fā)起查詢，統(tǒng)計每次查詢產(chǎn)生的查詢消息量，最后計算平均值，實驗結果如圖3所示。

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

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

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

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

6 結論（Conclusion）

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

參考文獻（References）

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

[2] 楊天路，等.P2P網(wǎng)絡技術原理與系統(tǒng)開發(fā)案例[M].北京：人民

郵電出版社.

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

京：機械工業(yè)出版社，2008.

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

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

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

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

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

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

作者簡介：

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

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

技術及網(wǎng)絡工程.

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

機應用及軟件開發(fā).