非結構化P2P網絡中基于節點的MQR算法設計與實現

謝 晃,張 昱,王云凱

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

非結構化P2P網絡中基于節點的MQR算法設計與實現

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

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

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

對等網絡;資源定位;路由算法;非結構化;MQR算法

1 概述

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

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

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

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

2 MQR算法設計與實現

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

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

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

2.1 基本定義

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

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

定義3 假設在節點pi上發現目標數據的歷史查詢消息數為A,接收的歷史查詢消息總數為B,本地文檔規模為Objects,則節點pi的本地數據Di為:

其中,k=TTL-hops-1。

定義5 節點pj接收到來自其鄰居節點pi的查詢消息的轉發概率為:

其中,d為節點pi的鄰居節點數,即節點pi的度。

2.2 算法描述

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

節點 Node的數據表示格式為:＜hitNum, recNum,sendNum,effectNum,objects＞。hitNum表示在節點Node上發現目標數據的歷史查詢消息數, recNum為接收到的歷史查詢消息總數,sendNum為轉發的查詢消息總數,effectNum為節點Node訪問數據,objects為節點的本地數據。

偽算法步驟如下:

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

(2)若發現目標數據,則沿查詢路徑path返回查詢結果并更新路徑節點的訪問數據effectNum;

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

(5)選擇當前查詢未經過的n個最大轉發概率鄰居節點,轉發查詢消息;

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

偽代碼表示如下:

2.3 路由過程

在網絡節點上,需要保存節點進行本地數據查找時產生的歷史處理記錄以及節點傳遞查詢消息所產生的歷史轉發記錄。這些記錄的信息主要包括發現目標數據的歷史查詢消息數hitNum、接收到的歷史查詢消息總數recNum、轉發的查詢消息總數sendNum、節點本地數據objects及訪問數據effectNum。

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

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

表1 節點數據信息

表2 節點動態有效數據

3 模擬實驗與分析

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

3.1 實驗網絡模型

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

(1)隨機圖網絡

隨機圖網絡[12]是一種最基本的網絡模型,最早是由Erd?s和Rényi于1959年提出,主要特點是通過增加一定的網絡連接,可以使得松散網絡快速轉變為稠密網絡。經常被用于模擬典型的規則網絡。圖2即本文仿真實驗中所生成10 000個節點的隨機圖網絡節點度的分布示意。

圖2 隨機圖網絡節點度分布

(2)Power-Law網絡

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

圖3 Power-Law網絡節點度分布

3.2 模擬環境與參數設置

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

表3 實驗參數設置

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

同時,在模擬實驗中,MQR算法使用式(2)和式(3)計算各節點的訪問數據,使用式(5)計算各節點的動態有效數據值。其中,TTL影響因子α=1,網絡距離影響因子λ=3。

3.3 實驗結果分析

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

(1)查詢成功率

在圖4(a)中,可以看出在隨機圖網絡中,APS算法與MQR算法均表現出優于Random Walk算法的查詢成功比率。在TTL值不超過9時,MQR算法具有比APS算法更高的成功比率。將TTL值設置為較大值時,這2種算法的查詢成功比率均接近了100%。由此可見,該2種算法均具有一定的學習能力,能夠對查詢消息進行啟發式路由,并且MQR算法在TTL值較小時也保持了較好的路由性能。

圖4 隨機圖和Power-Law網絡中的查詢成功比率

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

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

(2)有效查詢率

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

圖5 隨機圖和Power-Law網絡中的有效查詢率

(3)查詢召回率

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

圖6 隨機圖和Power-Law網絡中的查詢召回率

4 結束語

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

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

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

[2] 徐 玉.P2P網絡中資源搜索算法的研究[D].南京:南京郵電大學,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-),男,碩士研究生,主研方向:對等網絡,信息檢索;張 昱,副教授、博士;王云凱,碩士研究生。

2013-08-19

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

(MQR)alogorithm