基于小世界現(xiàn)象的P2P網(wǎng)絡(luò)搜索研究

劉艷艷等

摘 要：本文依據(jù)小世界特性提出了一種P2P網(wǎng)絡(luò)搜索引擎系統(tǒng)模型，并給出了系統(tǒng)模型中對(duì)等網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，提出了一種搜索機(jī)制，使查詢消息更高效的傳播，實(shí)驗(yàn)數(shù)據(jù)說(shuō)明本文搜索機(jī)制與洪泛算法相比更加有效。

關(guān)鍵詞：小世界； P2P網(wǎng)絡(luò)；搜索；簇

中圖分類號(hào)： TP393.2 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

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

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

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

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

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

network search engine model based on small

world phenomenon）

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

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

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

5 實(shí)驗(yàn)分析（Experimental analysis ）

5.1 實(shí)驗(yàn)條件

模擬實(shí)驗(yàn)在自行構(gòu)造小世界網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行文檔的中文文檔主題搜索，即搜索符合查詢請(qǐng)求的文檔主題信息，網(wǎng)絡(luò)拓?fù)浜臀臋n主題數(shù)具體實(shí)驗(yàn)參數(shù)如表1所示，在構(gòu)造的網(wǎng)絡(luò)拓?fù)渖蠈?shí)現(xiàn)泛洪式的Query Routing算法和本文提出的使用小世界網(wǎng)絡(luò)中度數(shù)較高的節(jié)點(diǎn)進(jìn)行關(guān)鍵字查詢搜索，從查全率和查詢產(chǎn)生的消息量?jī)蓚€(gè)方面對(duì)兩種搜索方式進(jìn)行比較。

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

5.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

6 結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

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

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

郵電出版社.

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

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

[4] 周晉，等.基于Small-World網(wǎng)絡(luò)的非結(jié)構(gòu)化DHT算法.國(guó)家自

然科學(xué)基金項(xiàng)目（60003004），2005：109-117.

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

[D].微型機(jī)與應(yīng)用，2012（18）：42-44.

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

學(xué)報(bào)（自然科學(xué)版），2009，15（1）：20-25.

作者簡(jiǎn)介：

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

李洪建（1981-），男，學(xué)士，高級(jí)工程師.研究領(lǐng)域：軟件

技術(shù)及網(wǎng)絡(luò)工程.

代興義（1981-），男，碩士，高級(jí)工程師.研究領(lǐng)域：計(jì)算

機(jī)應(yīng)用及軟件開(kāi)發(fā).