非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中基于節(jié)點的MQR算法設(shè)計與實現(xiàn)

謝 晃,張 昱,王云凱

(1.中國科學(xué)技術(shù)大學(xué)軟件學(xué)院,江蘇蘇州215123;2.西南財經(jīng)大學(xué)經(jīng)濟信息工程學(xué)院,成都611130)

非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中基于節(jié)點的MQR算法設(shè)計與實現(xiàn)

謝 晃1,張 昱1,王云凱2

(1.中國科學(xué)技術(shù)大學(xué)軟件學(xué)院,江蘇蘇州215123;2.西南財經(jīng)大學(xué)經(jīng)濟信息工程學(xué)院,成都611130)

在非結(jié)構(gòu)化P2P搜索中,由于缺少全局性的管理機制,網(wǎng)絡(luò)節(jié)點無法獲得整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)及目標數(shù)據(jù)的定位信息,因此查詢消息的路由過程具有較高的隨機性,不僅查詢性能低,而且寬帶消耗大。為在有效控制網(wǎng)絡(luò)冗余消息規(guī)模的同時提高數(shù)據(jù)的搜索范圍,在分析現(xiàn)有2類典型非結(jié)構(gòu)化P2P路由算法的基礎(chǔ)上,提出一種基于節(jié)點的MQR算法。利用網(wǎng)絡(luò)節(jié)點的狀態(tài)信息及搜索過程中查詢消息的TTL值狀態(tài)信息,從數(shù)據(jù)的搜索范圍與網(wǎng)絡(luò)使用情況2個方面來提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索性能。仿真實驗結(jié)果表明,與傳統(tǒng)的P2P路由算法APS和Random Walk相比,該算法在搜索準確率、網(wǎng)絡(luò)利用率及召回率方面有更好的表現(xiàn)。

對等網(wǎng)絡(luò);資源定位;路由算法;非結(jié)構(gòu)化;MQR算法

1 概述

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中,由于網(wǎng)絡(luò)節(jié)點的動態(tài)增減、網(wǎng)絡(luò)規(guī)模的不確定性,在進行信息搜索時,容易產(chǎn)生大量的隨機路由消息,給網(wǎng)絡(luò)帶來沉重的負載,惡化網(wǎng)絡(luò)的性能,引起帶寬消耗和查詢性能方面的嚴重問題。在采用非結(jié)構(gòu)化P2P技術(shù)進行信息檢索[1]時,尤其是在對互聯(lián)網(wǎng)中規(guī)模巨大的Web數(shù)據(jù)進行檢索時,如何降低查詢處理所產(chǎn)生的冗余消息規(guī)模,同時提高數(shù)據(jù)的搜索范圍,以保證查詢結(jié)果較好的準確度和召回率,是非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索的路由機制所要重點考慮并解決的問題。

基于此問題,目前學(xué)術(shù)上已有的非結(jié)構(gòu)化P2P路由算法根據(jù)其實現(xiàn)原理主要分為兩大類[2]。一類是不利用任何網(wǎng)絡(luò)狀態(tài)信息的盲搜索式算法[3-6],另一類是利用網(wǎng)絡(luò)中節(jié)點信息、文檔分布、查詢記錄等狀態(tài)信息的啟發(fā)式路由算法[7-11]。前者可以抽象為如何從一個隨機圖中的任意一個節(jié)點出發(fā)搜索目標節(jié)點,使得整個搜索過程中遍歷的網(wǎng)絡(luò)節(jié)點數(shù)目最少。后者的特點是在網(wǎng)絡(luò)中根據(jù)每個節(jié)點記錄的狀態(tài)信息來動態(tài)決策后續(xù)查詢的路由過程。

通過模擬實驗結(jié)果和應(yīng)用效果來看,因為盲搜索式算法的路由過程是完全隨機的,該類算法將在網(wǎng)絡(luò)中產(chǎn)生大量的冗余消息,對于網(wǎng)絡(luò)帶寬的消耗非常巨大,網(wǎng)絡(luò)的有效利用率很低。相比之下,傳統(tǒng)啟發(fā)式路由算法對查詢消息引入類似于IP數(shù)據(jù)包的TTL機制,在節(jié)點的遍歷規(guī)模、檢索的數(shù)據(jù)集規(guī)模以及網(wǎng)絡(luò)使用情況的適應(yīng)性上都有較好的表現(xiàn)。但該類算法主要的不足在于,只考慮了鄰居節(jié)點的影響,忽略了查詢消息所可能到達的其他節(jié)點,在一定程度上限制了查詢消息對其TTL值范圍內(nèi)其他節(jié)點狀態(tài)信息的有效利用。此外,在實際的資源搜索過程中,查詢消息的TTL值狀態(tài)信息對于提高搜索性能是有所幫助的。

本文針對盲搜索式算法和傳統(tǒng)啟發(fā)式路由算法的不足,提出一種基于節(jié)點的MQR(Mixed Query Routing)算法,旨在通過綜合考慮節(jié)點的狀態(tài)信息及查詢消息的TTL值狀態(tài)信息,提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索的性能。

2 MQR算法設(shè)計與實現(xiàn)

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中,查詢路由一直是一個核心的問題,它是指查詢消息經(jīng)過一系列節(jié)點的轉(zhuǎn)發(fā),最終到達目標節(jié)點(滿足查詢條件的節(jié)點)的過程。查詢路由的效率和開銷對搜索系統(tǒng)的性能起著直接的決定性作用,一個性能良好的查詢路由機制能夠保證系統(tǒng)產(chǎn)生較少的無用查詢消息、較高的查詢準確度和較好的結(jié)果召回率。

由于非結(jié)構(gòu)化P2P系統(tǒng)缺乏全局性的信息搜集維護機制,查詢路由機制的性能主要依賴于系統(tǒng)利用網(wǎng)絡(luò)局部特征信息的方式,這些網(wǎng)絡(luò)的局部特征信息是由節(jié)點自身的數(shù)據(jù)信息以及查詢過程中產(chǎn)生的網(wǎng)絡(luò)狀態(tài)信息構(gòu)成。節(jié)點自身的數(shù)據(jù)信息一般可以直接在本地經(jīng)過處理得到,而查詢過程中產(chǎn)生的網(wǎng)絡(luò)狀態(tài)信息可以劃分為:節(jié)點進行本地數(shù)據(jù)檢索時產(chǎn)生的歷史處理記錄以及節(jié)點傳遞查詢消息所產(chǎn)生的歷史轉(zhuǎn)發(fā)記錄,查詢消息的狀態(tài)信息。在網(wǎng)絡(luò)中,能夠從某一節(jié)點比較直接地獲得該節(jié)點及其鄰居節(jié)點的狀態(tài)信息,而鄰居節(jié)點之外的節(jié)點信息較難直接獲取。因此,需要通過記錄查詢過程中所產(chǎn)生的有用信息,來預(yù)測這些遠處節(jié)點可能含有的數(shù)據(jù)信息。

在對這些網(wǎng)絡(luò)狀態(tài)信息進行分析的時候:一方面,節(jié)點自身存儲的數(shù)據(jù)信息以及節(jié)點在本地檢索數(shù)據(jù)的記錄,反映了由節(jié)點所提供的數(shù)據(jù)對于整個網(wǎng)絡(luò)數(shù)據(jù)系統(tǒng)的重要程度;另一方面,節(jié)點傳遞查詢消息所產(chǎn)生的轉(zhuǎn)發(fā)記錄,表征了節(jié)點與其他節(jié)點之間的數(shù)據(jù)訪問關(guān)系的強弱。因此,本文將從這兩方面出發(fā),著手研究提高查詢性能的方法。

2.1 基本定義

定義1 通過節(jié)點i能夠訪問到的有效數(shù)據(jù)由節(jié)點的本地數(shù)據(jù)Di以及到其他節(jié)點的訪問數(shù)據(jù)Ni組成。其定義為:

定義2 假定在查詢路徑path=(p1,p2,…,pn)的路徑節(jié)點pj上發(fā)現(xiàn)查詢的目標數(shù)據(jù),則認為節(jié)點pi(i＜j)與節(jié)點pj具有一定的數(shù)據(jù)訪問。將節(jié)點pi到節(jié)點的訪問數(shù)據(jù)定義為:

定義3 假設(shè)在節(jié)點pi上發(fā)現(xiàn)目標數(shù)據(jù)的歷史查詢消息數(shù)為A,接收的歷史查詢消息總數(shù)為B,本地文檔規(guī)模為Objects,則節(jié)點pi的本地數(shù)據(jù)Di為:

其中,k=TTL-hops-1。

定義5 節(jié)點pj接收到來自其鄰居節(jié)點pi的查詢消息的轉(zhuǎn)發(fā)概率為:

其中,d為節(jié)點pi的鄰居節(jié)點數(shù),即節(jié)點pi的度。

2.2 算法描述

在MQR算法中,使用的查詢消息Q數(shù)據(jù)表示格式為:＜id,source,key,path,hops,hit＞。id是一個全局唯一的消息標識,source記錄查詢的起始節(jié)點,key表示查詢的關(guān)鍵詞。在path中,按順序記錄了查詢消息經(jīng)過的路徑節(jié)點,可以防止環(huán)路查詢的出現(xiàn)。hops保存了消息已經(jīng)到達的節(jié)點數(shù),當hops達到上限值TTL時,消息就終止傳遞。hit標識消息是否成功返回目標數(shù)據(jù)的狀態(tài)。

節(jié)點 Node的數(shù)據(jù)表示格式為:＜hitNum, recNum,sendNum,effectNum,objects＞。hitNum表示在節(jié)點Node上發(fā)現(xiàn)目標數(shù)據(jù)的歷史查詢消息數(shù), recNum為接收到的歷史查詢消息總數(shù),sendNum為轉(zhuǎn)發(fā)的查詢消息總數(shù),effectNum為節(jié)點Node訪問數(shù)據(jù),objects為節(jié)點的本地數(shù)據(jù)。

偽算法步驟如下:

(1)節(jié)點pi接收到查詢消息Q,對本地數(shù)據(jù)進行檢索;

(2)若發(fā)現(xiàn)目標數(shù)據(jù),則沿查詢路徑path返回查詢結(jié)果并更新路徑節(jié)點的訪問數(shù)據(jù)effectNum;

(3)檢查查詢消息Q的hops值。當hops值到達上限值TTL時,終止查詢;

(5)選擇當前查詢未經(jīng)過的n個最大轉(zhuǎn)發(fā)概率鄰居節(jié)點,轉(zhuǎn)發(fā)查詢消息;

(6)重復(fù)步驟(1),直至查詢消息的hops值達到上限TTL,終止查詢。

偽代碼表示如下:

2.3 路由過程

在網(wǎng)絡(luò)節(jié)點上,需要保存節(jié)點進行本地數(shù)據(jù)查找時產(chǎn)生的歷史處理記錄以及節(jié)點傳遞查詢消息所產(chǎn)生的歷史轉(zhuǎn)發(fā)記錄。這些記錄的信息主要包括發(fā)現(xiàn)目標數(shù)據(jù)的歷史查詢消息數(shù)hitNum、接收到的歷史查詢消息總數(shù)recNum、轉(zhuǎn)發(fā)的查詢消息總數(shù)sendNum、節(jié)點本地數(shù)據(jù)objects及訪問數(shù)據(jù)effectNum。

圖1 查詢消息Q1和Q2的路由示意圖

通過式(3)計算節(jié)點B和節(jié)點D對于不同查詢消息Q1、Q2的動態(tài)有效速數(shù)據(jù),如表1與表2所示。進一步可以計算得到:節(jié)點B接收查詢消息Q1的概率為2/(2+2.5)=44%,接收查詢消息Q2的概率為1.75/(1.75+1.5)=54%。節(jié)點D接收消息Q1的概率2.5/(2+2.5)=56%,接收查詢消息Q2的概率為1.5/(1.5+1.75)=46%。因此,節(jié)點A選擇節(jié)點D傳遞查詢消息Q1,選擇節(jié)點B傳遞查詢消息Q2。

表1 節(jié)點數(shù)據(jù)信息

表2 節(jié)點動態(tài)有效數(shù)據(jù)

3 模擬實驗與分析

為了更為準確地對算法的性能進行分析,本文在PeerSim仿真平臺上進行模擬實驗。實驗選擇盲搜索的代表算法Random Walk、啟發(fā)式路由的代表算法APS同本文提出的 MQR在隨機圖網(wǎng)絡(luò)和Power-Law網(wǎng)絡(luò)2類網(wǎng)絡(luò)中進行實驗對比。并根據(jù)實驗結(jié)果對比三者的查詢成功率、有效查詢率和查詢召回率,分析三者在查找準確性、帶寬利用率、響應(yīng)速度上的性能表現(xiàn)。

3.1 實驗網(wǎng)絡(luò)模型

在實際生活中,廣泛存在著隨機圖網(wǎng)絡(luò)和Power-Law網(wǎng)絡(luò)。因此,在本文實驗中,采用該2類網(wǎng)絡(luò)模型進行算法的性能對比實驗。

(1)隨機圖網(wǎng)絡(luò)

隨機圖網(wǎng)絡(luò)[12]是一種最基本的網(wǎng)絡(luò)模型,最早是由Erd?s和Rényi于1959年提出,主要特點是通過增加一定的網(wǎng)絡(luò)連接,可以使得松散網(wǎng)絡(luò)快速轉(zhuǎn)變?yōu)槌砻芫W(wǎng)絡(luò)。經(jīng)常被用于模擬典型的規(guī)則網(wǎng)絡(luò)。圖2即本文仿真實驗中所生成10 000個節(jié)點的隨機圖網(wǎng)絡(luò)節(jié)點度的分布示意。

圖2 隨機圖網(wǎng)絡(luò)節(jié)點度分布

(2)Power-Law網(wǎng)絡(luò)

Power-Law網(wǎng)絡(luò)[12]也被稱為 Scale-Free網(wǎng)絡(luò),該網(wǎng)絡(luò)模型是在1999年Albert-Laszlo Barabasi和他的研究小組對互聯(lián)網(wǎng)結(jié)構(gòu)進行研究時發(fā)現(xiàn)的。研究[13-14]表明,實際應(yīng)用中的大量P2P網(wǎng)絡(luò)都是具有這類特征的Power-Law網(wǎng)絡(luò)。圖3即本文仿真實驗采用10 000個節(jié)點的Power-Law網(wǎng)絡(luò)節(jié)點度的分布示意圖。

圖3 Power-Law網(wǎng)絡(luò)節(jié)點度分布

3.2 模擬環(huán)境與參數(shù)設(shè)置

本文模擬實驗采用PeerSim-1.0.5仿真平臺,利用Java實現(xiàn)。實驗和主要參數(shù)及設(shè)置如表3所示。

表3 實驗參數(shù)設(shè)置

在模擬實驗中,本文采用基于離散事件的Event-based模擬模式來模擬P2P網(wǎng)絡(luò)的消息轉(zhuǎn)發(fā)處理過程。通過提供模擬的網(wǎng)絡(luò)傳輸層,確保較高的模擬精度。同時,忽略實際網(wǎng)絡(luò)中傳輸層的數(shù)據(jù)延時、丟失等情況,降低了實驗的復(fù)雜程度,以便于對實驗結(jié)果進行更為直觀的對比分析。在節(jié)點提交查詢的過程中,本文采用Cycle-based模擬方式,以保證能夠支持較大規(guī)模的查詢請求。實驗將模擬的查詢總數(shù)設(shè)定為406 927,隨機圖網(wǎng)絡(luò)及Power-Law網(wǎng)絡(luò)包含的節(jié)點設(shè)定為10 000,平均節(jié)點的度設(shè)定為10,所有算法在搜索過程中執(zhí)行的walker數(shù)量設(shè)為3。

同時,在模擬實驗中,MQR算法使用式(2)和式(3)計算各節(jié)點的訪問數(shù)據(jù),使用式(5)計算各節(jié)點的動態(tài)有效數(shù)據(jù)值。其中,TTL影響因子α=1,網(wǎng)絡(luò)距離影響因子λ=3。

3.3 實驗結(jié)果分析

為了對比分析3種算法在查找準確性、帶寬利用率、響應(yīng)速度上的性能表現(xiàn),實驗結(jié)果主要采用查詢成功比率、有效查詢召回率、查詢召回率3種評價指標進行評價[15]。

(1)查詢成功率

在圖4(a)中,可以看出在隨機圖網(wǎng)絡(luò)中,APS算法與MQR算法均表現(xiàn)出優(yōu)于Random Walk算法的查詢成功比率。在TTL值不超過9時,MQR算法具有比APS算法更高的成功比率。將TTL值設(shè)置為較大值時,這2種算法的查詢成功比率均接近了100%。由此可見,該2種算法均具有一定的學(xué)習能力,能夠?qū)Σ樵兿⑦M行啟發(fā)式路由,并且MQR算法在TTL值較小時也保持了較好的路由性能。

圖4 隨機圖和Power-Law網(wǎng)絡(luò)中的查詢成功比率

在圖4(b)中,可以發(fā)現(xiàn)Random Walk算法在Power-Law網(wǎng)絡(luò)中的表現(xiàn)有所下降,這是由于Power-Law網(wǎng)絡(luò)中大部分節(jié)點具有較小的度,而少量節(jié)點具有極高的度。APS算法與MQR算法在Power-Law網(wǎng)絡(luò)中表現(xiàn)出與隨機圖網(wǎng)絡(luò)類似的性能,由此可見,兩者對于網(wǎng)絡(luò)結(jié)構(gòu)的適應(yīng)能力都較好。在Power-Law網(wǎng)絡(luò)中,MQR算法也維持了較高的查詢成功比率。

在圖4中,當TTL=1時,APS算法與Random Walk算法的查詢成功比率相近,這是由于查詢消息只傳播一跳的距離,APS算法所能累計的查詢經(jīng)驗非常有限,不能對查詢路由進行啟發(fā)。在隨著TTL值遞增的過程中,APS算法表現(xiàn)出了較好的學(xué)習能力,因此其查詢成功比率上升較快,在TTL值達到7時表現(xiàn)出了與MQR算法相近的性能。但通過比較,可以發(fā)現(xiàn)MQR算法維持了較高的平均性能,即使在TTL=1時,其查詢成功比率也接近了60%,APS算法和Random Walk算法分別為36%與32%。

(2)有效查詢率

通過圖5(a)、圖5(b)的對比,可以看出3種算法在隨機圖網(wǎng)絡(luò)與Power-Law網(wǎng)絡(luò)中表現(xiàn)出類似的網(wǎng)絡(luò)性能。在2種網(wǎng)絡(luò)中,3種算法對網(wǎng)絡(luò)帶寬的有效利用情況較為穩(wěn)定,MQR算法維持在45%附近,APS算法保持了30%左右的有效查詢比率,Random Walk算法表現(xiàn)在15%附近。MQR算法與APS算法隨著TTL值的增加體現(xiàn)出小幅度的波動,在TTL值為1時有效查詢比率稍低,分別為37%與21%,這2類算法之間的差值穩(wěn)定在15%左右。Random Walk算法對TTL值的變化不敏感,這也反映了該算法采用隨機選擇的路由策略具有較低的網(wǎng)絡(luò)利用率。從實驗結(jié)果的分析中,可以得到結(jié)論:MQR算法對于網(wǎng)絡(luò)的有效利用程度較高,反映了其在網(wǎng)絡(luò)搜索過程中能夠產(chǎn)生較少的冗余消息,對查詢消息的路由效率較高。

圖5 隨機圖和Power-Law網(wǎng)絡(luò)中的有效查詢率

(3)查詢召回率

如圖6所示,MQR算法表現(xiàn)出了比APS算法與Random Walk算法更高的性能。在相同的路由距離內(nèi),APS算法所能查詢到的目標數(shù)據(jù)略高于Random Walk算法,但MQR算法表現(xiàn)出了極好的查詢召回率性能。在路由距離為8時,MQR算法單個查詢返回的結(jié)果數(shù)接近70,近似于APS算法與Random Walk算法的3.5倍。在需要返回給定數(shù)量的查詢結(jié)果時,APS算法與Random Walk算法也需要更大的路由距離,遍歷更多的網(wǎng)絡(luò)節(jié)點以獲得足夠的目標數(shù)據(jù)。因此,MQR算法具有很好的查詢召回率,處理用戶查詢并返回目標數(shù)據(jù)所需要的響應(yīng)時間更短。

圖6 隨機圖和Power-Law網(wǎng)絡(luò)中的查詢召回率

4 結(jié)束語

本文提出一種基于節(jié)點的MQR算法,通過利用網(wǎng)絡(luò)節(jié)點的狀態(tài)信息及搜索過程查詢消息的TTL值狀態(tài)信息,從數(shù)據(jù)的搜索范圍及網(wǎng)絡(luò)的使用情況2個方面著手,對非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索技術(shù)進行了改進。通過仿真實驗與盲搜索的代表算法 Randon Walk、啟發(fā)式路由的代表算法APS進行了對比,并從查詢準確度、網(wǎng)絡(luò)帶寬使用情況、查詢召回率等多個方面對MQR算法進行了分析評估。結(jié)果表明,與其他典型非結(jié)構(gòu)化P2P搜索算法相比,MQR算法在節(jié)點規(guī)?？刂啤⑺阉鳒蚀_率、帶寬利用率、響應(yīng)速度上都有更好的表現(xiàn)。

但另一方面,在對節(jié)點與其他網(wǎng)絡(luò)節(jié)點之間的數(shù)據(jù)訪問關(guān)系的評估方式上,MQR算法所采用的數(shù)學(xué)計算方法還不夠完善,存在一定程度的誤差。如何對其進行更為準確的數(shù)學(xué)表示,是下一步研究工作所要重點解決的問題。

[1] 方啟明,楊廣文,武永衛(wèi),等.基于P2P的Web搜索技術(shù)[J].軟件學(xué)報,2008,19(10):2706-2719.

[2] 徐 玉.P2P網(wǎng)絡(luò)中資源搜索算法的研究[D].南京:南京郵電大學(xué),2011.

[3] Jiang Hongbo, Jin Shudong. Exploiting Dynamic Querying like Flooding Techniques in Unstructured Peerto-PeerNetworks[C]//Proc.ofthe 13th IEEE International Conference on Network Protocols.[S.l.]: IEEE Press,2005.

[4] Kalogeraki V,Gunopulos D,Zeinalipouryazti D.A Local Search Mechanism for Peer-to-Peer Networks[C]// Proc.of the 11th International Conference on Information and Knowledge Management.New York,USA:ACM Press,2002:300-307.

[5] Yang B,GarciaMolina H.Improving Search in Peer-to-Peer Networks[C]//Proc.of the 22nd International Conference on Distributed Computing Systems.[S.l.]: IEEE Press,2002:5-14.

[6] Gkantsidis C,Mihail M,Saberi A.RandomWalks on Peerto-Peer Networks[C]//Proc.of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]:IEEE Press,2004:241-263.

[7] Tsoumakos D,Roussopoulos N,Adaptive Probabilistic Search for Peer-to-Peer Networks[C]//Proc.of the 3rd International Conference on Peer-to-Peer Computing. [S.l.]:IEEE Press,2003:102-109.

[8] Michlmayr E. Ant Alogorithms for Search in Unstructured Peer-to-Peer Networks[C]//Proc.of the 22nd InternationalConference on Data Engineering Workshops.[S.l.]:IEEE Press,2006.

[9] Sripanidkulchai K,Maggs B,Zhang Hui.Efficient Content Location Using Interest-based Locality in Peerto-Peer Systems[C]//Proc.of the 22nd Annual Joint Conference of IEEE Computer and Communications. [S.l.]:IEEE Societies,2003:2166-2176.

[10] Akavipat R,Wu Le,MenczerF,etal.Emerging Semantic Communities in Peer Web Search[C]//Proc. of International Workshop on Information Retrieval in Peer-to-Peer Networks.[S.l.]:ACM Press,2006:1-8.

[11] Bisnik N,AbouzeidA A.OptimizingRandom Walk Search Alogorithms in P2P Networks[J].Computer Networks,2007,51(6):1499-1514.

[12] Lv Qin,Cao Pei,Cohen E,et al.Search and Replication in Unstructured Peer-to-Peer Networks[C]//Proc.of the 16th InternationalConference on Supercomputing. [S.l.]:ACM Press,2002:84-95.

[13] Sripanidkulchai K.The Popularity of Gnutella Queries and Its Implications on Scalability[EB/OL].(2001-02-11).http://www.openp2p.com.

[14] Almeida V,Bestavros A,Crovella M,et al.Characterizing Reference Locality in the WWW[C]//Proc.of the 4th InternationalConference on Paralleland Distributed Information Systems.[S.l.]:IEEE Press,1996:92-103. [15] Gummadi P K,Saroiu S,Gribble S D.A Measurement Study of Peer-to-Peer File Sharing Systems[J].ACM SIGCOMM Computer Communication Review,2002,32 (1):82-96.

編輯 任吉慧

Design and Implementation of Node-based MQR Alogorithm in Unstructured P2P Networks

XIE Huang1,ZHANG Yu1,WANG Yun-kai2
(1.College of Software,University of Science and Technology of China,Suzhou 215123,China;
2.College of Economic Information Engineering,Southwestern University of Finance and Economics,Chengdu 611130,China)

Due to the lack of global governance mechanisms in the unstructured Peer-to-Peer(P2P)network,network nodes do not know the entire network topology and target data location information.So the query message routing process has a high randomness,not only query performance is low,but also bandwidth consumption is large.Based upon the analysis of two typical categories of unstructured P2P routing alogorithms,this paper proposes a node-based Mixed Query Routing(MQR)alogorithm to deal with the scale problem of redundant messages and to improve the search scope of data.By means of the status information about the nodes and the TTL values of the queries,it can improve the search performance both in the aspect of data's search scope and network efficiency.Simulation experimental results show that compared with the typical alogorithms APS and Random Walk,the MQR alogorithm can reach higher accuracy rate,better network efficiency and recall rate.

Peer-to-Peer(P2P)network;resource location;routing alogorithm;unstructured;Mixed Query Routing

1000-3428(2014)09-0111-06

A

TP393.02

10.3969/j.issn.1000-3428.2014.09.023

謝 晃(1987-),男,碩士研究生,主研方向:對等網(wǎng)絡(luò),信息檢索;張 昱,副教授、博士;王云凱,碩士研究生。

2013-08-19

2013-09-23E-mail:xiehuang2010@yeah.net

(MQR)alogorithm