《P2P网络的搜索算法分析》由会员分享，可在线阅读，更多相关《P2P网络的搜索算法分析（6页珍藏版）》请在金锄头文库上搜索。
1、P2P网络的搜索算法分析摘要：P2P网络的搜索算法是P2P技术的一个重要研究领域。通过对P2P网络搜索算法定义和研究意义的介绍，让读者概略地了解此种搜索算法；并且通过对其分类，展示了其发展的过程；最后，通过典型P2P搜索算法的分析，进一步说明了其优越性和发展前景。关键词：P2P;搜索算法；泛洪；DHT1什么是P2P网络的搜索算法P2P是英文PeertoPeer（对等）的简称，又被称为“点对点”。“对等”技术是一种网络新技术。P2P技术可以不通过服务器的中转而实现计算机系统之间资源和信息的直接共享。P2P技术研究的一个重要分支便是搜索算法的研究。P2P搜索算法即指基于P2P网络结构的搜索方式。它
2、的存在形式导致其与现有搜索技术有了很大的不同。由于P2P网络资源分散性极强，分布于各个节点；节点允许自由进退，资源不断变化处于动态。而这两方面都使得P2P网络搜索的难度大大地增加。2P2P网络搜索算法的分类对比2.1集中式集中式的搜索是以目录服务器为中心的搜索方式。目录服务器会记录下网络中共享资源的所有信息并且会对对这些共享资源逐一进行索引和查找。集中式搜索里，所有的对等点和已经知道地址的目录服务器都相互连接，因此，目录服务器会记下每个对等点的加入或离开，并随之更新系统索引表。集中式搜索具有诸多优势，例如：搜索的速度快、内容全面，搜索过程中需要的信息量小，节省网络带宽等等。但是，不容忽视的是，
3、集中式搜索也有其自身无法克服的缺陷：由于中央服务器的瘫痪容易造成其整个网络的崩毁，因此大大降低了其搜索的可靠性和安全性；另外，中央目录服务器的更新维护费用都会由于网络规模的扩大而急剧增加，致使所需成本也大大提高；再有就是中央服务器的存在引起了共享资源在版权上的划分不清纷争不断，也因此这种搜索成为了非纯粹意义的P2P网络模型。2.2分布式搜索能够解决集中式搜索所具有以上的问题。与集中式搜索相比较，分布式搜索没有目录服务器，或者说每个对等点都可称为一个服务器；每个对等点都具有相似的功能；对等点通过彼此相连串联起整个网络体系，依靠其所在的网络来搜索确定其余对等点和搜索资源。分布式搜索能够消除中央索引
4、模型难题的法宝是采用了泛洪请求模型，且增加了系统的伸缩性，且不会因个别节点的错误而导致整个系统的失败。但分布式搜索自身的局限性是：对等点的定位和查找较为复杂；网络规模越来越大，广播方式定位必将使网络流量快速增大，导致网络堵塞；易遭到恶意攻击，安全性低。2.3混合式混合式搜索P2P网络是由普通对等点和提供搜索的超级对等点构成。所有对等点在资源共享方面具有相同地位。所有普通对等点在资源搜索方面在某一时刻只与一个超级的连接，超级对等点从普通对等点获取资源索引和搜索资源请求；在收到请求后，超级对等点一边做本地缓存处理，一边在网上的其它所有的超级对等点中间下达搜索请求；当收到回应后，超级对等点就会把收到
5、的回应与本地搜索结果全部反馈给发出搜索指令的普通对等点。集了分布式和集中式优点与一身的混合式搜索，在设计思想和处理能力上都有了很大的改进和提高，主要表现在以下3方面：可大大减少查询资源传播的数量，查询消息只在超级对等点之间传播，所以参与传播的对等点数量较少；减少了单个点的失败对网络的影响。如果某个超级对等点没有成功，与其直接相连的普通对等点也可以二次发现并与别的超级对等点重新搭建连接；能够根据对等点的能力合理有效地分配分担负载，超级对等点都是由网络速度快、计算能力强的对等点转化的，并承担查询的任务。但是，混合式搜索也有自身的不足，即实现较困难，为了利用该模式的优点，必须提供能合理有效组织各对等
6、点之间关系的搜索网络。3两类典型的P2P搜索算法分析3.1泛洪(Flooding)算法网络上的节点预先都能相互知晓其它节点所拥有的资源。当一个节点发出资源搜索指令时，会首先生成出一个搜索消息，并且把此消息广播传给它相邻接的节点。邻接节点收到消息后，首先搜索自身资源，如果搜索到与之匹配的资源，就会生成出一个查询回应回发给源节点；如果没有，便会继续转给除源节点之外的其他邻接节点。这便是传统泛洪算法的基本思路。这样的方式会使查询消息像洪水般在网络中的各节点间涌动，所以称之为Flooding搜索。过程如图1所示：搜索节点开始TTL=3，每传播一次TTL减去1，如果TTL减到0却还没有搜索到资源，那么就
7、停止；如果搜索到了需要的资源则返馈回目标机器的信息来建立连接。另外由于有TTL的控制，所以即使在搜索过程中出现了循环，这个循环也不会永远进行下去，当TTL=0的时候自然结束。图1非结构化P2P搜索算法（1）Flooding搜索算法泛洪算法在搜索深广度上有着难以超越的优越性。每个节点都将转发查询消息给它相邻的节点，以致查询的信息可迅速蔓延到整个网络，因此将大大提高信息挖掘的程度，使得整个网络可以搜索与查询匹配的数据的所有消息但传统的洪水算法有很大的缺陷。它迅速产生大量的冗余信息，尤其是当网络规模增大，相对高度之间的连接节点时，冗余消息随着大量的网络带宽，造成网络拥塞，影响系统的性能。3.2DHT
8、算法DHT是DistributedHashTable的缩写，DHT算法是一种在P2P网络中被大规模应用搜索算法。P2P网络拥有相对规则和固定的拓扑结构，网络中所有的节点都有唯一固定的逻辑地址。逻辑地址在路由时起到标识节点位置的作用，节点标识符（PeerID）是经散列函数得到的。此外，网络上的数据全部具有唯一的（DataID）。点路由表是表示P2P网络的全部节点一起承担一张哈希表，各个节点承担整张表的各个片段。动态的P2P节点通过动态形式变成哈希表的某一部分，网络的节点数目不断加入，DHT也就不断的变大。所有节点的哈希表都有着两种对应关系：vDataID,Value和vDataID,PeerID
9、。其中，vDataID,Value由数据标识符搜索相关的数据信息Value,包含了数据文件名和数据节点地址等；DataID，PeerID由数据标识符存放无误DataID，Value的标识符。因此，用DHT算法做数据查找时就应该采用与此算法相应的存储策略。其搜索过程：一个节点运用散列函数由搜索的数据信息生成搜索请求和DataID;若本节点没有存储需要搜索的信息，则由vDataID，PeerID找下个节点标识符，将搜索请求下达到该节点；接到搜索请求的节点，先由DataID搜索相应的数据信息；若搜索成功，就将搜索的数据信息返回给查询节点；若不存在数据信息，就由vDataID，PeerID查询下个Pe
10、erID且发出查询请求。DHT算法其实是一个由关键字来搜索路由转换哈希表的过程。由于有哈希函数的存在,使得查询的安全性和速度都得以提高且不会占用太多网络流量,且便于管理。P2P网络搜索算法主要采用的是DHT和泛洪。泛洪算法的优点是节点覆盖率高、响应时间快,且健壮性好,但缺点是同时会产生许多冗余消息。DHT算法优点是快速定位查找的节点,不会产生大量冗余消息。但DHT算法的缺陷是其依赖于网络规则稳定的拓扑结构，且没有模糊查询的功能。为了解决P2P网络查询的这些问题，工程师进行了大量的研究,也提出了很多新的P2P查询策略。4P2P搜索算法的新思路及挑战基于对泛洪算法和DHT算法的优缺点比较，我们对P
11、2P算法的进一步研究应该是如何把这两种算法结合起来，同时拥有两种算法的优势。最新的研究从提高搜索算法的可靠性和寻找随机图中的最短路径两个方面展开。也就是对重叠网络(OverlayNetwork)的重新认识。其中，小世界模型(SmallWorld)对P2P搜索技术的新发展有着重大的影响。Smallworld模型的网络拓扑具有高聚集度和短链的特性。在符合SmallWorld特性的网络模型中，可以根据结点的聚集度将结点划分为若干簇(Cluster)，在每个簇中至少存在一个度最高的结点为中心结点。大量研究证明了以Gnutella为代表的P2P网络符合SmallWorld特征，也就是网络中存在大量高连通
12、结点，部分结点之间存在“短链”现象。因此，P2P搜索算法中如何缩短路径长度的问题变成了如何找到这些“短链”的问题。尤其是在DHT搜索算法中，如何产生和找到“短链”是搜索算法设计的一个新思路。SmallWorld特征的发现和引入会对P2P搜索算法产生重大影响。这也将是我们进一步的研究方向。参考文献：1 余敏.基于superpeer的连续查询策略J.计算机工程与应用，2006(8).2 杨天路.P2P网络技术原理与系统开发案例M.北京：人民邮电出版社，2007.3 江莉莉.基于JXTA的P2P资源管理技术的实现J.计算机应用，2006(8).4 刘宇芳.P2P网络的搜索算法分析J.信息科学，2005(6).5 林建华.P2P中主流算法研究报告R.中南大学信息科学与工程研究学院，2010.
