P2P网络中主流搜索算法的分析比较

《P2P网络中主流搜索算法的分析比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、P2P中主流搜索算法研究报告（中南大学信息科学与工程学院林建华）摘要:对等(P2P)网络是实现下一代互联网的重要组成部分。对等网络的可用性依赖于对网络上数据的高效的查找和提取方法,如何高效的定位和搜索P2P网络上的资源是P2P网络实现的最为关键的问题。本文首先从P2P的定义出发,深入介绍了几种主流的算法与协议并对每种协议进行了讨论。关键词:P2P网络;;搜索算法AnalysisandCompareofMainstreamDHTSearchArithmeticinP2PnetworkAbstract:Coordinated(P2P)thenetworkistherea

2、lizationnextgenerationInternetimportantconstituent.Thepeer-to-peernetworkuabilityreliesontothedatahighlyeffectivesearchandwithdrawsthemethodtothenetworkin,howdoesthehighlyeffectivelocalizationansearchintheP2PnetworktheresourcesistheP2Pnetworkrealizationmostessentialquestion.Thisarticle

3、firstembarksfromtheP2PdefinitionthoroughlyintroducedseveralkindofmainstreamsDHTalgorithmsandtheagreementandhavecarriedonthediscussiontoeachkindoagreement.Keywords:P2PNetwork;DHT;SearchingArithmetic1引言对等网络(Peer-to-Peer，简称P2P)是目前非常热门的应用，自1999年以来，P2P的研究一直是国外知名学府(如美国麻省理工学院，加州大学伯克利分校和莱斯大学等)

4、以及知名企业的研发机构(如微软，诺基亚的研究院)关注的重点。它甚至被美国《财富》杂志称为改变因特网发展的四大新技术之一，被认为是代表无线宽带互联网未来的关键技术。2、P2P对现有搜索的意义   　对于现有搜索服务而言，P2P技术不仅仅是简单的节约了服务器成本和提升了搜索速度，更重要的价值在于促进了搜索的多元化和权力、责任、义务的分解。通过合理可行的模式，将P2P技术与搜索服务结合一体，意味着在现有的建立统一的搜索索引数据库的思路之外，还可以引进另外两条思路，一是在互联网进行全面分散备份和无机备份、分散索引和无机索引的思路，二是在互联网只索引而无备份的思路，此两条新路

5、线的本质精神，在于将搜索的格局有目前的统而死、一而全转变为分而活、多而散，是一条发动全网力量参与开展搜索自读物的全息思路。3．非结构化P2P搜索算法　　按照搜索策略，可以分为两大类：盲目搜索和启发式搜索。盲目搜索通过在网络中传播查询信息并且把这些信息不断扩散给每个节点。通过这种洪泛方式来搜索想要的资源。而启发式搜索在搜索的过程中利用一些已有的信息来辅助查找过程。由于信息搜索对资源的存储有一些知识，所以信息搜索能够比较快的找到资源。3.1Flooding搜索方法在最初的Gnutella协议中，使用的是Flooding方法，在网络中，每个节点都不知道其他节点的资源。当它

6、要寻找某个文件，把这个查询信息传递给它的相邻节点，如果相邻节点含有这个资源，就返回一个QueryHit的信息给Requester。如果它相邻的节点都没有命中这个被查询文件，就把这条消息转发给自己的相邻节点。这种方式像洪水在网络中各个节点流动一样，所以叫做Flooding搜索。由于这种搜索策略是首先遍历自己的邻接点，然后再向下传播，所以又称为宽度优先搜索方法（BFS）。如图所示：搜索的节点一开始TTL=3，它每传播一次TTL减1，如果TTL减到0还没有搜索到资源，则停止。如果搜索到资源则返回目标机器的信息以用来建立连接。在搜索过程中可能出现循环，但是由于有TTL控制，

7、所以这个循环不会永远进行下去，当TTL=0的时候自然结束。图1Flooding方法示意图3.2IterativeDeepening搜索方法迭代递增是Flooding方法的改进，策略循环递增TTL（TimetoLive）值，这个值用来控制Flooding的搜索深度。跟Flooding搜索方法给TTL赋一个较大的值不同，这种方法在初始阶段，给TTL一个很小的值，如果在TTL减为0，还没有搜索到资源，则给TTL重新赋更高的值。这种策略可以减少搜索的半径，但是在最坏的情况下，延迟很大，如果P2P网络内重复资源丰富，这种方法在不影响搜索质量的基础上将减少网络内的查询流量，