非结构化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