基于Ｐ２Ｐ网络的资源搜索技术研究

郑　磊

[摘要]对P2P资源搜索的拓扑结构和资源搜索算法等相关知识作较详细的介绍,对基于不同P2P结构的搜索算法作简单的对比和分析。并针对现有搜索算法存在的问题,提出一些解决的设想,最后对影响搜索算法的因素和解决的方法进行归纳。

[关键词]P2P资源搜索

中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0920068-01

一、引言

P2P即端到端网络应用,又称为对等连接或对等网络,是一种新的通信模式,P2P网络中的节点是对等的,且每个peer能同时充当服务器和客户端。

在P2P网络中,不存在中心服务器,所有的节点既是客户机,享用其他节点提供的服务,同时又充当服务器,为其他节点提供服务。P2P对等的节点之间进行直接的连接与共享,因此搜索无需通过Web服务器,也可不受任何信息文档格式和宿主设备的限制,可以达到传统搜索引擎无可比拟的深度,理论上可以包括网络上所有的信息资源。现阶段互连网上大量资源被闲置,没有被充分利用,P2P搜索技术可以帮助人们方便地找到所需资源。

二、P2P资源搜索技术

为了在P2P网络中有效的发现资源,人们对P2P搜索技术做了大量的研究。目前主要从P2P网络的结构以及采用的算法两方面进行研究。P2P网络可分为两类:结构化网络和非结构化网络。在结构化网络中每个结点存储的信息与网络拓扑结构有关,通过映射完成,查找采用基于DHT分布式散列路由搜索算法。而非结构化网络则与网络拓扑无关,其结点可任意存储信息,查找采用基于广度优先的搜索算法及其改进算法。

(一)结构化P2P网络的资源搜索技术

结构化P2P网络是指像CAN、Chord、Tapestry之类的点对点的网络。这类网络中每个节点都有固定的地址,整个网络具有相对稳定和规则的拓扑结构。依赖拓扑结构,可以给网络的每一个节点指定一个逻辑地址,并把地址和节点对应起来。动态散列表是大多数结构化P2P网络所采取的资源定位方式。首先将网络中的每一个节点分配虚拟地址(VID),同时用一个关键字(KEY)来表示其可提供的共享内容。取一个散列函数,这个函数可以将KEY转换成一个散列值H(KEY)。网络中节点相邻的定义是散列值相邻。发布信息的时候就把(KEY,VID)二元组发布到具有和H(KEY)相近地址的节点上去,其中VID指出了文档的存储位置。资源定位的时候,就可以快速根据H(KEY)到相近的节点上获取二元组(KEY,VID),从而获得文档的存储位置。不同的DHT算法决定了P2P网络的逻辑拓扑,比如CAN就是一个N维向量空间,而CHORD是一个环形拓扑,TAPESTRY则是一个网状的拓扑。

基于DHT这类结构搜索算法最大的问题是DHT的维护机制较为复杂,尤其是结点频繁加入退出造成的网络波动,极大地增加了DHT的维护代价。这类搜索算法存在的另外一个问题是DHT仅支持精确关键词匹配查询,无法支持内容、语义等复杂查询。这是由于其采用相容散列函数根据精确关键词进行对象的定位与发现,散列函数总是试图保证生成的散列值均匀随机分布,结果两个内容相似度很高但不完全相同的对象被生成了完全不同的散列值,存放到了完全随机的两个结点上。目前在DHT基础上开展带有语义的资源管理技术的研究还非常少。也正是由于DHT的精确关键词映射的特性决定了无法和信息检索等领域的研究成果结合,才阻碍了基于DHT的P2P系统的大规模应用。

(二)非结构化P2P网络的资源搜索技术

非结构化P2P网络指的是以Gnutella为典型代表的一类网络。Gnutella

是更加纯粹的P2P系统,因为它没有中央索引服务器,每台机器在Gnutella

网络中是真正的对等关系。非结构化P2P网络的搜索技术按照搜索策略可以分为两大类:盲目搜索和启发式搜索。盲目搜索通过在网络中传播查询信息并且把这些信息不断扩散给每个节点,采用泛洪方式来搜索想要的资源。而启发式搜索在搜索的过程中利用一些己有的信息来辅助查找过程,因此能较快找到所需的资源。

1.Flooding搜索方法。在最初的Gnutella协议中,使用的是Flooding,又称为宽度优先搜索方法。在网络中,一个节点向所有邻居节点广播查询消息,邻居节点再向自己的邻居节点广播,这个过程不断进行下去,像洪水在网络中各个节点流动一样,所以叫做Flooding搜索。搜索的节点开始给TTL。赋一初值,它每传播一次TTL减1,如果TTL减到0还没有搜索到资源,则停止。如果搜索到资源则返回目标机器的信息以用来建立连接。在搜索过程中可能出现循环,当TTL=0的时候循环自然结束。该算法的特点:路由算法比较简单,易于实现。每次路由都是全网遍历,增加了网络的负担,搜索的效率不高,网络扩展性差,路由算法容易被攻击。

2.Modified-BFS方法。该算法的路由机制大部分跟Flooding搜索方法相同,即采用全网遍历的搜索形式。不同处在于,源只是随机的选取一定比例的相邻节点作为查询信息的发送目标,而不是发送给所有相邻节点。相比于Flooding方法来说,是以时间换取空间的有效尝试。该算法的特点:减少了路由消息,降低了网络负载,降低了网络的覆盖,因此可能需要发费更长的时间才能到达定位的目标节点。

3.Random Walk搜索方法。该算法进一步加强对节点路由消息的扩散程度的控制,主要体现在扩散程度和扩散范围两个方面都有所改进。请求者发出K个查询请求给随机挑选的K个相邻节点。然后每个查询信息在以后的漫步过程中直接与请求者保持联系,询问是否还要继续下一步。如果请求者同意继续漫步,则又开始随机选择下一步漫步的节点,否则中止搜索。

4.Gnutella2的搜索方法。为了减少系统中的路由消息,这种算法采用了超级节点和叶子节点的两级节点的分类方法,将系统分成了两级网络。超级节点存储着离它最近的叶子节点的文件信息并定期互相更新,超级节点互相连接形成一个核心网络。当叶子节点需要查询文件时,它首先从它连接的超级节点的索引中寻找,如果找到了文件,则直接根据文件所存储的机器的IP地址建立连接,否则,超级节点把这个查询请求发给它连接的其他超级节点,直到得到想要的资源。该算法的特点:超级节点负责了大部分的路由功能,降低了叶子节点的负载,从而缩短了查询的延时。但由于超级节点的存在,安全性较差,当超级节点受到攻击或失效时易造成网络的瘫痪。

5.基于移动Agent的搜索方法。该算法将移动Agent和P2P路由人工智能技术进行了结合,简单的说,移动Agent是一个能在异构网络中自主地从一台主机迁移到另一台主机,并可与其他Agent或资源进行交互的程序。Agent非常适合在网络环境中来帮助用户完成信息检索的任务。当有节点需要搜索的时候,它发送一个移动Agent给它相邻的节点,移动Agent记录着它的一些搜索的信息。当这个Agent到达一台新的机器上,然后在这个机器上进行资源搜索任务,如果这台机器上没有它想要的资源,则它把这些搜索的信息传给它的邻节点,如果找到资源,则返回给请求的机器。该算法的特点:在用户的个性化管理方面有着相当的优势,可根据用户的需求进行分类、整理、分析用户的爱好,帮助用户查找其感兴趣的信息。但其实现较为复杂,由于Agent的运行增加了节点的负载,搜索时延差别较大。

对于非结构的P2P网络路由技术,其本质就是通过一种方法尽可能少地覆盖网络中的节点,以达到遍历搜索的目的。这就要求:消息路由过程中必要的动态终止,消息的重复必须尽可能减少,消息搜索遍历过程中下一步覆盖的节点数要尽量少。

三、P2P资源搜索技术研究的挑战

目前P2P搜索技术中,两个重要的研究成果分别是基于Small World理论的非结构化搜索算法和基于DHT的结构化搜索算法。尤其是DHT及其搜索技术为资源的组织与查找提供了一种新的方法,在近年来的P2P研究领域成为热点。随着P2P系统实际应用的发展,物理网络中影响路由的一些因素开始影响P2P搜索算法的效率。

P2P资源搜索方法要实现的搜目标包括:减少搜索过程中产生的消息数量,减少节点维护的路由索引或数据索引大小,保证系统的容错性、可扩展性,维持节点之间的负载平衡等。虽然目前新的P2P搜索方法不断的涌现,但其在资源搜索效率、准确定位和复杂查询等方面还有很大的改善空间,在具体的应用实现上仍有较长的路要走。基于P2P技术的搜索引擎要达到现在集中式的搜索引擎(如Google、百度)这样广泛的使用还需要一段长时间的努力。如何将资源搜索方法结合实际需求进行改进及推广应用将是需要进一步研究和解决的问题性地做好这项工作,才能更好地为用户服务,为企业获取最大的效益。

参考文献:

[1]DietterichAT G,Lathrop R H,Lozano-Pérez P T.Solving the multiple-instance problem with axis-parallel rectangles[J].Artificial Intelligence,1997,89(1-2):31-71.

[2]O Maron,T Lozano-Perez.A framework for multiple-instance learning[C].Advances in Neural Information Processing Systems.MIT Press,1998.

[3]Wang J.,Zucker J.-D.Solving the multiple-instance problem:A lazy learning approach.In:Langley P.eds.Proc.of the 17th In-ternational Conference on Machine Learning,San Francisco,2000,341-349.

[4]赵战斌,对等网络(P2P)讨研究,福建电脑,2007,(1).

[5]李莉、韩慧健,无结构P2P网络资源搜索方法研究,网络与通信,2007,(1).

[6]杨天路等,P2P网络技术原理与系统开发案例,北京:人民邮电出版社,2007.