謝 晃,張 昱,王云凱

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

2.1 基本定義

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

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

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

其中,k=TTL-hops-1。

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

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

2.2 算法描述

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

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

偽算法步驟如下:

(1)節(jié)點(diǎn)pi接收到查詢消息Q,對(duì)本地?cái)?shù)據(jù)進(jìn)行檢索;

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

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

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

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

偽代碼表示如下:

2.3 路由過程

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

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

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

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

表2 節(jié)點(diǎn)動(dòng)態(tài)有效數(shù)據(jù)

3 模擬實(shí)驗(yàn)與分析

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

3.1 實(shí)驗(yàn)網(wǎng)絡(luò)模型

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

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

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

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

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

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

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

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

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

表3 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

(1)查詢成功率

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

圖4 隨機(jī)圖和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é)點(diǎn)具有較小的度,而少量節(jié)點(diǎn)具有極高的度。APS算法與MQR算法在Power-Law網(wǎng)絡(luò)中表現(xiàn)出與隨機(jī)圖網(wǎng)絡(luò)類似的性能,由此可見,兩者對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的適應(yīng)能力都較好。在Power-Law網(wǎng)絡(luò)中,MQR算法也維持了較高的查詢成功比率。

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

(2)有效查詢率

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

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

(3)查詢召回率

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

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

4 結(jié)束語

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

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

[1] 方啟明,楊廣文,武永衛(wèi),等.基于P2P的Web搜索技術(shù)[J].軟件學(xué)報(bào),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-),男,碩士研究生,主研方向:對(duì)等網(wǎng)絡(luò),信息檢索;張 昱,副教授、博士;王云凱,碩士研究生。

2013-08-19

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

(MQR)alogorithm