P2P网络的搜索算法分析

admin管理员组

文章数量:1532440

2024年7月4日发(作者：)

P2P网络的搜索算法分析

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

P2P网络搜索算法定义和研究意义的介绍，让读者概略地了解此种搜

索算法；并且通过对其分类，展示了其发展的过程；最后，通过典型

P2P搜索算法的分析，进一步说明了其优越性和发展前景。

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

1什么是P2P网络的搜索算法

P2P是英文PeertoPeer（对等）的简称，又被称为“点对

点”。“对等”技术是一种网络新技术。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是 Distributed Hash Table的缩写，DHT算法是一种在

P2P网络中被大规模应用搜索算法。P2P网络拥有相对规则和固定的

拓扑结构，网络中所有的节点都有唯一固定的逻辑地址。逻辑地址在

路由时起到标识节点位置的作用，节点标识符(Peer ID)是经散列函数

得到的。此外，网络上的数据全部具有唯一的(Data ID)。点路由表是

表示P2P 网络的全部节点一起承担一张哈希表，各个节点承担整张

表的各个片段。动态的 P2P 节点通过动态形式变成哈希表的某一部

分，网络的节点数目不断加入，DHT也就不断的变大。所有节点的

哈希表都有着两种对应关系：和。

其中，由数据标识符搜索相关的数据信息 Value，

包含了数据文件名和数据节点地址等； < Data ID，Peer ID>由数据标

识符存放无误< Data ID，Value>的标识符。因此，用DHT 算法做数

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

节点运用散列函数由搜索的数据信息生成搜索请求和Data ID；②若

本节点没有存储需要搜索的信息，则由找下个节

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

Data ID 搜索相应的数据信息；④若搜索成功，就将搜索的数据信息

返回给查询节点；⑤若不存在数据信息，就由查

询下个 Peer ID 且发出查询请求。DHT 算法其实是一个由关键字来

搜索路由转换哈希表的过程。由于有哈希函数的存在，使得查询的安

全性和速度都得以提高且不会占用太多网络流量，且便于管理。

P2P网络搜索算法主要采用的是DHT和泛洪 。泛洪算法的优点

是节点覆盖率高、响应时间快，且健壮性好，但缺点是同时会产生许

多冗余消息。DHT 算法优点是快速定位查找的节点，不会产生大量

冗余消息。但 DHT 算法的缺陷是其依赖于网络规则稳定的拓扑结

构，且没有模糊查询的功能。为了解决P2P网络查询的这些问题，工

程师进行了大量的研究，也提出了很多新的 P2P 查询策略。

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

基于对泛洪算法和DHT算法的优缺点比较，我们对P2P算法的

进一步研究应该是如何把这两种算法结合起来，同时拥有两种算法的

优势。最新的研究从提高搜索算法的可靠性和寻找随机图中的最短路

径两个方面展开。也就是对重叠网络(Overlay Network)的重新认识。

其中，小世界模型(Small World)对P2P搜索技术的新发展有着重大的

影响。

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

合Small World特性的网络模型中，可以根据结点的聚集度将结点划

分为若干簇(Cluster)，在每个簇中至少存在一个度最高的结点为中心

结点。大量研究证明了以Gnutella为代表的P2P网络符合Small World

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

现象。

因此，P2P搜索算法中如何缩短路径长度的问题变成了如何找

到这些“短链”的问题。尤其是在DHT搜索算法中，如何产生和找

到“短链”是搜索算法设计的一个新思路。Small World特征的发现

和引入会对P2P搜索算法产生重大影响。这也将是我们进一步的研究

方向。参考文献：

[1]余敏.基于super

2006(8).

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

出版社，2007.

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

用，2006(8).

peer的连续查询策略[J].计算机工程与应用，

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

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

程研究学院，2010.

本文标签： 搜索网络节点搜索算法算法