p2p搜索器

龙源期刊网

P2P网络的搜索算法分析

作者：王雅静马娟

来源：《软件导刊》2011年第12期

摘要：P2P网络的搜索算法是P2P技术的一个重要研究领域。通过对P2P网络搜索算法定

义和研究意义的介绍，让读者概略地了解此种搜索算法；并且通过对其分类，展示了其发展的

过程；最后，通过典型P2P搜索算法的分析，进一步说明了其优越性和发展前景。

关键词：P2P；搜索算法；泛洪；ＤＨＴ

中图分类号：TP312文献标识码：A文章编号：（2011）

作者简介：王雅静（1977-），男，山西曲沃人，山西财贸职业技术学院讲师，研究方向

为计算机网络；马娟（1978-），女，山西永济人，山西财贸职业技术学院讲师，研究方向为

计算机软件。1什么是P2P网络的搜索算法

P2P是英文（对等）的简称，又被称为“点对点”。“对等”技术是一种网络

新技术。P2P技术可以不通过服务器的中转而实现计算机系统之间资源和信息的直接共享。

P2P技术研究的一个重要分支便是搜索算法的研究。P2P搜索算法即指基于P2P网络结构的搜

索方式。它的存在形式导致其与现有搜索技术有了很大的不同。由于P2P网络资源分散性极

强，分布于各个节点；节点允许自由进退，资源不断变化处于动态。而这两方面都使得P2P网

络搜索的难度大大地增加。

2P2P网络搜索算法的分类对比

2.1集中式

集中式的搜索是以目录服务器为中心的搜索方式。目录服务器会记录下网络中共享资源的

所有信息并且会对对这些共享资源逐一进行索引和查找。集中式搜索里，所有的对等点和已经

知道地址的目录服务器都相互连接，因此，目录服务器会记下每个对等点的加入或离开，并随

之更新系统索引表。集中式搜索具有诸多优势，例如：搜索的速度快、内容全面，搜索过程中

需要的信息量小，节省网络带宽等等。但是，不容忽视的是，集中式搜索也有其自身无法克服

的缺陷：由于中央服务器的瘫痪容易造成其整个网络的崩毁，因此大大降低了其搜索的可靠性

和安全性；另外，中央目录服务器的更新维护费用都会由于网络规模的扩大而急剧增加，致使

所需成本也大大提高；再有就是中央服务器的存在引起了共享资源在版权上的划分不清纷争不

断，也因此这种搜索成为了非纯粹意义的P2P网络模型。

龙源期刊网

2.2分布式

搜索能够解决集中式搜索所具有以上的问题。与集中式搜索相比较，分布式搜索没有目录

服务器，或者说每个对等点都可称为一个服务器；每个对等点都具有相似的功能；对等点通过

彼此相连串联起整个网络体系，依靠其所在的网络来搜索确定其余对等点和搜索资源。分布式

搜索能够消除中央索引模型难题的法宝是采用了泛洪请求模型，且增加了系统的伸缩性，且不

会因个别节点的错误而导致整个系统的失败。但分布式搜索自身的局限性是：对等点的定位和

查找较为复杂；网络规模越来越大，广播方式定位必将使网络流量快速增大，导致网络堵塞；

易遭到恶意攻击，安全性低。

2.3混合式

混合式搜索P2P网络是由普通对等点和提供搜索的超级对等点构成。所有对等点在资源共

享方面具有相同地位。所有普通对等点在资源搜索方面在某一时刻只与一个超级的连接，超级

对等点从普通对等点获取资源索引和搜索资源请求；在收到请求后，超级对等点一边做本地缓

存处理，一边在网上的其它所有的超级对等点中间下达搜索请求；当收到回应后，超级对等点

就会把收到的回应与本地搜索结果全部反馈给发出搜索指令的普通对等点。集了分布式和集中

式优点与一身的混合式搜索，在设计思想和处理能力上都有了很大的改进和提高，主要表现在

以下3方面：①可大大减少查询资源传播的数量，查询消息只在超级对等点之间传播，所以参

与传播的对等点数量较少；②减少了单个点的失败对网络的影响。如果某个超级对等点没有成

功，与其直接相连的普通对等点也可以二次发现并与别的超级对等点重新搭建连接；③能够根

据对等点的能力合理有效地分配分担负载，超级对等点都是由网络速度快、计算能力强的对等

点转化的，并承担查询的任务。但是，混合式搜索也有自身的不足，即实现较困难，为了利用

该模式的优点，必须提供能合理有效组织各对等点之间关系的搜索网络。

3两类典型的P2P搜索算法分析

3.1泛洪(Flooding)算法

网络上的节点预先都能相互知晓其它节点所拥有的资源。当一个节点发出资源搜索指令

时，会首先生成出一个搜索消息，并且把此消息广播传给它相邻接的节点。邻接节点收到消息

后，首先搜索自身资源，如果搜索到与之匹配的资源，就会生成出一个查询回应回发给源节

点；如果没有，便会继续转给除源节点之外的其他邻接节点。这便是传统泛洪算法的基本思

路。这样的方式会使查询消息像洪水般在网络中的各节点间涌动，所以称之为Flooding搜索。

过程如图1所示：搜索节点开始TTL=3，每传播一次TTL减去1，如果TTL减到0却还

没有搜索到资源，那么就停止；如果搜索到了需要的资源则返馈回目标机器的信息来建立连

接。另外由于有TTL的控制，所以即使在搜索过程中出现了循环，这个循环也不会永远进行

下去，当TTL=0的时候自然结束。

龙源期刊网

图1非结构化P2P搜索算法（1）——Flooding搜索算法

泛洪算法在搜索深广度上有着难以超越的优越性。每个节点都将转发查询消息给它相邻的

节点，以致查询的信息可迅速蔓延到整个网络，因此将大大提高信息挖掘的程度，使得整个网

络可以搜索与查询匹配的数据的所有消息但传统的洪水算法有很大的缺陷。它迅速产生大量的

冗余信息，尤其是当网络规模增大，相对高度之间的连接节点时，冗余消息随着大量的网络带

宽，造成网络拥塞，影响系统的性能。

3.2DHT算法

DHT是DistributedHashTable的缩写，DHT算法是一种在P2P网络中被大规模应用搜索

算法。P2P网络拥有相对规则和固定的拓扑结构，网络中所有的节点都有唯一固定的逻辑地

址。逻辑地址在路由时起到标识节点位置的作用，节点标识符(PeerID)是经散列函数得到的。

此外，网络上的数据全部具有唯一的(DataID)。点路由表是表示P2P网络的全部节点一起承担

一张哈希表，各个节点承担整张表的各个片段。动态的P2P节点通过动态形式变成哈希表的某

一部分，网络的节点数目不断加入，DHT也就不断的变大。所有节点的哈希表都有着两种对

应关系：和。其中，由数据标识符搜索相关的数据信息Value，包含了数据文件名和数据节点

地址等；由数据标识符存放无误的标识符。因此，用

DHT算法做数据查找时就应该采用与此算法相应的存储策略。其搜索过程：①一个节点运用

散列函数由搜索的数据信息生成搜索请求和DataID；②若本节点没有存储需要搜索的信息，

则由找下个节点标识符，将搜索请求下达到该节点；③接到搜索请求的节点，先由DataID搜

索相应的数据信息；④若搜索成功，就将搜索的数据信息返回给查询节点；⑤若不存在数据信

息，就由查询下个PeerID且发出查询请求。DHT算法其实是一个由关键字来搜索路由转换哈

希表的过程。由于有哈希函数的存在，使得查询的安全性和速度都得以提高且不会占用太多网

络流量，且便于管理。

P2P网络搜索算法主要采用的是DHT和泛洪。泛洪算法的优点是节点覆盖率高、响应时

间快，且健壮性好，但缺点是同时会产生许多冗余消息。DHT算法优点是快速定位查找的节

点，不会产生大量冗余消息。但DHT算法的缺陷是其依赖于网络规则稳定的拓扑结构，且没

有模糊查询的功能。为了解决P2P网络查询的这些问题，工程师进行了大量的研究，也提出了

很多新的P2P查询策略。

4P2P搜索算法的新思路及挑战

基于对泛洪算法和DHT算法的优缺点比较，我们对P2P算法的进一步研究应该是如何把

这两种算法结合起来，同时拥有两种算法的优势。最新的研究从提高搜索算法的可靠性和寻找

随机图中的最短路径两个方面展开。也就是对重叠网络(OverlayNetwork)的重新认识。其中，

小世界模型(SmallWorld)对P2P搜索技术的新发展有着重大的影响。

龙源期刊网

Smallworld模型的网络拓扑具有高聚集度和短链的特性。在符合SmallWorld特性的网络

模型中，可以根据结点的聚集度将结点划分为若干簇(Cluster)，在每个簇中至少存在一个度最

高的结点为中心结点。大量研究证明了以Gnutella为代表的P2P网络符合SmallWorld特征，

也就是网络中存在大量高连通结点，部分结点之间存在“短链”现象。

因此，P2P搜索算法中如何缩短路径长度的问题变成了如何找到这些“短链”的问题。尤其

是在DHT搜索算法中，如何产生和找到“短链”是搜索算法设计的一个新思路。SmallWorld特

征的发现和引入会对P2P搜索算法产生重大影响。这也将是我们进一步的研究方向。参考文

献：

[1]余敏.基于的连续查询策略[J].计算机工程与应用，2006(8).

[2]杨天路.P2P网络技术原理与系统开发案例[M].北京：人民邮电出版社，2007.

[3]江莉莉.基于JXTA的P2P资源管理技术的实现[J].计算机应用，2006(8).

[4]刘宇芳.P2P网络的搜索算法分析[J].信息科学，2005(6).

[5]林建华.P2P中主流算法研究报告[R].中南大学信息科学与工程研究学院，2010.

（责任编辑：杜能钢）