摘　要：P2P（Peer-to-Peer）网络是分布式网络的最新热点应用，目前流行的大多数P2P网络大都基于非结构化拓扑，这种拓扑利用洪泛方法传播查询信息,但是由于搜索的盲目性，其检索效率又普遍低下。本文分析了各种搜索算法的优势以及存在的缺陷，为高性能的资源搜索算法提出奠定理论基础。

关键词：

 引言近几年来,基于点对点P2P①的网络逐渐成为互联网中最流行的网络之一。对等网络打破了传统的C/S模式,每个节点既是服务器，为别的节点提供服务，同时又可以向其他节点请求服务。P2P的概念并不局限于文件的共享,它在对等节点之间共享资源和服务,可以共享的计算机资源包括处理器的计算能力、存储器和磁盘等。目前，根据拓扑结构的关系可以将P2P分为4 种形式：中心化拓扑；非结构化拓扑；结构化拓扑②和混合拓扑。中心化拓扑最大的优点是维护简单发现效率高，最大的问题是与传统C/S结构类似，容易造成单点故障，经典案例就是Napster。目前主流的结构化拓扑采用哈希表DHT技术，最大问题是维护机制比较复杂，节点的增加与减少都会产生维护代价。和结构化P2P网络相比，非结构化P2P网络在网络拓扑上没有严格的控制，节点可以随意地加入或离开网络，并不会给网络结构的调整带来太大负担，因此大部分P2P应用系统都是基于非结构化的。   P2P搜索技术评价标准在对目前主流的非结构化P2P搜索算法进行探究之前，我们先从用户角度和网络的角度给出P2P搜索技术的评价标准。从用户角度出发，我们最关心的是每次查询能否立即定位成功，每次能查询到多少内容，其中有多少是用户想得到的信息。因此用户一般从返回的结果数、满意度以及响应时间来进行评价。从网络角度出发，一个好的搜索算法搜索效率要高，系统资源利用率要高，要能保证搜索质量，用最少的代价获取最高的质量。   非结构化P2P网络搜索算法的分类 1 洪泛算法③ Gnutella的 Flooding方法，是一种典型的盲目搜索算法。该算法又叫宽度优先搜索方法（BFS）。该算法每次要搜索资源的时候就向它的所有邻居节点发布查询信息。而邻居节点收到该节点的查询信息时，先检查自己是否有该资源信息，如果有，就将满足要求的结果返回给该节点；如果没有，则邻居节点继续以同样的方式向它自己的所有邻居节点发布查询信息，如此反复。这种搜索过程在一开始设定了消息生命周期TTL，来防止无休止的洪泛。这种算法里每个节点都在TTL周期里不停地洪泛，即使已经查询到正确资源。因此容易造成大量的查询冗余信息，给网络造成负载，在节点规模增大的时候容易造成网络堵塞。因此在实际网络中，需要更合理的搜索方法。 2 Iterative Deeping④搜索方法迭代加深算法是洪泛算法的一种改进，它在查询开始的时候先给TTL设定一个较小的值，当查询进行到TTL为0的时候，检测查询结果，如果满足则停止搜索；如果仍未得到查询结果，就重新开始搜索，并且给TTL一个较大的值。等到TTL再次为0的时候再检测查询结果，如此反复，一直到最后得到满足的查询结果。这个过程中很有可能在比最大深度小很多的时候就搜索到资源，因此和直接以最大深度进行洪泛搜索比起来，可以节省大量的资源。在好的情况下，这种策略可以很快得到搜索结果，但是因为P2P网络的状况的未知的，最差的时候可能要进行最大规模的查询，这时迭代算法由于多次反复迭代，其查询冗余开销就比直接洪泛更多，占用了更多的网络资源。 3 Random Walk搜索方法随机漫步算法中，每次查询都是同时发出K个查询消息，而这K个查询消息节点都随机地将查询消息转发给自己的一个邻居节点。每个节点收到查询消息时，先检测该消息标志是否为0，如果不是，则随机选择一个邻居节点转发；如果为0，则直接联系请求者，看查询结果是否满足请求：如果满足，则查询结束；如果不满足，则重新设置消息标志，继续随机漫步。这种方法只记录成功的搜索，一旦所以来的资源发生变化，中途经过的节点频繁退出，将无法得到反馈调整，节点的偏好准确度就会大为降低，可能导致大的查询延时。 4 Gnutella2⑤ Gnutella2不是Gnutella的继承，它没有在整个P2P网络中使用洪泛算法，它把网络中的节点划分成两种：超级节点和叶子节点。超级节点只存储离它最近的叶子节点的信息，而这些超级节点又共同连接起来形成一个覆盖网络。当某个叶子节点需要搜索资源时，它先从它所连接的超级节点的索引中搜。如果搜索成功，则根据资源所存储的机器IP地址建立连接；如果搜索失败，该超级节点就把这个查询请求转发给它所连接的其它超级节点，如此反复，直至搜索结束。 Gnutella2只是在超级节点向其相连接的超级节点转发信息时才使用洪泛，有效地减少了冗余消息，提高了搜索效率。但超级节点向其邻居超级节点转发查询消息时仍使用洪泛机制，在目前P2P网络规模大、节点数多的情况下，仍存在较多的带宽浪费。