分布式P2P网络中基于方向搜索算法研究

刘 卫，刘金岭

（1.昆明理工大学 计算机中心，云南 昆明 650024；2.淮阴工学院 计算机工程学院，江苏 淮安 223003）

分布式P2P网络中基于方向搜索算法研究

刘 卫1，刘金岭2

（1.昆明理工大学 计算机中心，云南 昆明 650024；2.淮阴工学院 计算机工程学院，江苏 淮安 223003）

针对Flooding算法及其改进算法的理念提出了P2P网络中基于方向的搜索算法，该算法动态生成一棵以搜索源点为根的搜索树，在每一次的搜索过程中，每个节点都能沿着搜索方向进行，这样可以避免节点被重复地搜索。有效地避免了搜索过程中冗余搜索报文的产生，节省了网络带宽，提高了效率和网络性能。通过二维空间的数字数据和图像数据这两种实验结果的分析并进行了仿真实验，该算法充分体现了在搜索过程中的有效性及可操作性。

分布式；P2P网络；拓扑结构；方向搜索

目前人们已经意识到P2P技术[1]在网络信息交流、文件交换、分布计算等方面大有前途。在P2P网络上，闲散资源有机会得到利用，所有节点的资源总和构成了整个网络的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。P2P技术的另一个优势是开发出强大的搜索工具，使用户深度搜索成为可能，为互联网的信息搜索提供了全新的解决方法。运用P2P技术进行深度搜索，无需通过WEB服务器，可以不受信息格式和计算机设备的种种限制，达到传统目录式搜索引擎无可比拟的深度，理论上将包括网络上所有开放的信息资源。采用P2P技术，搜索范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台PC上的资源。文献[2]中给出了分布式结构化网络中的Chord搜索算法，其优点是算法简单，性能较好，缺点是随着节点规模的不断增大，节点的性能差异会影响系统效率。Flooding算法[3]是分布式P2P网络中的一个基本搜索算法。Flooding搜索算法的优点是路由算法简单且易于实现；缺点是每一次路由都要进行全网遍历，从而加重网络负担，降低搜索效率，限制网络扩展，使得路由算法容易受到攻击。正是由于目前P2P网络搜索中存在的一系列缺陷，很多研究人员在该领域中做了大量工作，在Flooding算法基础上出现了一些改进算法，如文献[4]中提到的Modified-BFS、PartialMinFlood等。这些改进后的算法在某些特定条件下确实提高了搜索效率，进而提高了网络的整体性能。然而，这些改进算法中为了实现某些方面的改进而在其他方面付出了昂贵的代价，主要体现在如下几个方面：1）算法过于复杂，难以实现；2）算法限制条件太多，实际网络中难以满足要求；3）对算法的改进非常有限。这些算法在目前P2P网络中均没有得到应用。文中在现有的研究基础上，给出了一种基于方向的搜索算法 （记为：Direct_Search），该算法充分利用了网络中邻居节点的信息，从源节点到网络拓扑空间的每一个方向做平行搜索。在Direct_Search算法中，搜索树[5]的生成要求网络中各节点知道P2P网络的拓扑信息，因此该算法的实现需要相应的P2P网络拓扑结构的支持。

1 Direct_Search算法的P2P网络拓扑结构构建

分布式结构化 P2P网络研究的重点在如何有效地查找信息上。大部分结构化P2P网络都采用分布式散列表DHT[6]的资源定位方式。

为了将分布式 P2P网络中的资源分布结构化，以利于有效地查找信息，分布式散列表 DHT采取了以下的方法[6]：

1）按照一定的规则为每个网络节点分配一个唯一的节点标示符（Node ID），按照散列算法为每个节点的资源对象产生一个唯一的资源对象标识符（Object ID）；

2）Node ID与Object ID通过散列函数将被映射到同一个分布式散列表中；

3）将分布式散列表分割成不连续的散列块，每个节点配置一个散列块，并且每个节点要负责维护属于自己的散列块；

4）通过分布式散列表来查找节点所需要的资源，定位到资源所在的节点位置；通过特定的路由算法在节点之间建立连接路径。

Direct_Search算法在执行搜索过程中，会动态的差生一棵搜索树，搜索树的产生要求网络中的每个节点知道自身在P2P网络中的拓扑信息。文中算法的实现设计了一个基于笛卡尔坐标的P2P网络拓扑结构。该结构的拓扑空间S与n维向量空间V十分相似。

笔者对于加入P2P网络的节点按一定的算法映射成n拓扑空间S中的一个点。S中的每个点都有自己的坐标（x1，x2，…，xn），任意两点 N1（x1，x2，…，xn）和 N2（y1，y2，…，yn）的欧式距离d定义为：

对于加入P2P网络中的每个节点分配一个坐标，该坐标唯一对应P2P网络拓扑空间S中的一个点，节点与节点之间的距离定义为与节点对应的点与点之间的欧式距离d。在区域分布中充分考虑节点分布的均匀性，所以被添加到P2P网络中的节点将会在n维空间S中通过Hash算法被映射成相应的点。

1.1 基本概念

由于在网络节点的加入和退出过程中，需要维护网络的拓扑结构，为此引出如下超级节点的定义。

定义1在网络拓扑结构中确定唯一个节点Super-Node来存储了该网络拓扑结构中所有节点的坐标、id、ip地址、端口信息等，则称该节点Super-Node为该网络拓扑结构的超级节点。

由于在搜索过程中，节点的搜索信息量会不断地增加，这样会加重Super-Node的负载量，本文中Super-Node只负责存储节点加入和离开的信息。

定义2设N是拓扑空间S中的一个节点，称与N相距最远邻居节点间的距离r为N的视觉搜索半径；与节点N之间的距离小于视觉搜索半径的节点集合所在区域称为N的视觉搜索区域。如果在某个搜索区域内，没有邻居节点的存在，则定义这个搜索区域的视觉半径为0。

n维坐标的拓扑空间 S中节点N的搜索区域是一个圆锥体，该圆锥体的顶点即为搜索源节点，每个进入该搜索区域的节点在进行搜索的过程中都要对这个圆锥体搜索区域负责。二维空间的搜索区域是个扇形区，该扇形的顶点为搜索源节点。

1.2 网络拓扑结构的节点加入和移出

当节点Nj申请加入网络时，首先要访问超级节点Super-Node，并将自己的信息告知Super-Node。Super-Node随即为节点Nj在网络空间S中分配位置坐标，同时将节点Nj的位置信息和邻居列表信息发给节点Nj。Nj加入网络后，要判断是否在其邻居节点Ni的搜索区域内，如果节点Nj在其邻居节点Ni的视觉搜索区域内，节点Nj的信息将会被加入到进该视觉搜索区域的邻居列表中。如果邻居列表中的节点个数大于m个（其中m为邻居列表存储搜索信息的最大节点数），那么该视觉搜索区域内远离节点Nj的节点信息将会被超级节点删除，随即超级节点将通知相应的节点修改其自身的邻居节点信息。

当节点要申请移出网络时，该节点首先要告知Super-Node。Super-Node随即移去节点的信息，这时移去节点在视觉搜索区域内的邻居节点所保存的信息将会有所变动。因为一个节点的移去，网络需要进行调整，意味着在视觉搜索区域内的其他节点会被加入，来保证二叉树的网络结构。Super-Node会为被加入的节点分配新的位置坐标，同时Super-Node存储的邻居列表信息也要实时地做出更新来保持网络拓扑的准确性。

1.3 搜索方向机搜索区域

基于方向搜索设计的目的是避免节点被重复搜索。在每一次的搜索过程中，每个节点都要沿着搜索方向进行。一个节点沿着其搜索方向进行搜索的区域我们称为该节点负责的搜索区域。n维拓扑空间S中的节点N的搜索区域是一个以搜索源点为顶点的锥体，在搜索过程中，每个参与节点分别负责一个锥体搜索区域。下面以二维空间为例，说明搜索方向和搜索区域的确定。在二维拓扑空间S中，搜索区域是一个以搜索源点为中心的扇形，搜索沿着远离搜索源点的方向进行。如图1所示。

图1 搜索方向和搜索区域示意图Fig.1 Schematic diagram of direction search and searching area

1.4 下一跳基于方向搜索节点的选择

当前节点的下一跳基于方向搜索节点的计算是比较关键的步骤。计算的方法是：从当前节点的邻居列表里取出一个邻居节点N，根据该邻居节点的坐标和当前节点的搜索区域的边界平面方程，计算出该邻居节点是否在当前节点的搜索区域中。如果该邻居节点N在当前节点的搜索区域中，则进一步根据该邻居节点的坐标和当前节点的搜索方向直线方程判断该邻居节点K是否在当前节点的搜索方向上。如果在搜索方向上，则该邻居节点符合条件，是当前节点的下一跳搜索节点。否则，该邻居节点不是当前节点的下一跳搜索节点。

2 分布式P2P网络中基于方向的搜索算法Direct_Search

Direct_Search的设计思想是把 P2P网络中的节点映射到二维空间坐标的平面上，在这个二维空间坐标上的每个节点都会被分配一个二维空间坐标，以此来标注其在空间中的位置。在整个算法中只设置一个超级节点，想要进入 P2P网络的每一个节点首先要和超级节点进行通信，在通信的过程中超级节点会为该节点在 P2P网络的应用层分配一个二维坐标。同时，Direct_Search在P2P网络中的资源定位也是以节点被分配的坐标为基础的。把这个二维空间坐标平面分成4个象限，该算法是以搜索源节点作为根节点，以4个象限内的节点作为叶节点，并在每个象限内生成一棵二叉树，搜索过程根据二叉树模型进行搜索，这一想法在 Direct_Search能够有效地避免发送重复的搜索消息而造成冗余所带来的网络高负载。同时网络中的每个节点都被设置了若干个邻居节点，其只能从它的邻居节点获取搜索消息，并不需要整个网络中节点的所有消息，这一想法使得 Direct_Search具有很好的可扩展性和稳定性，同时能够很好地适应 P2P网络的动态变化。在整个搜索过程中，搜索的起点是搜索的源节点。该算法充分地利用网络中邻居节点的信息，从源节点到网络拓扑空间的每一个方向做平行搜索。Direct_Search算法流程如图2所示。

图2 Direct_Search算法执行的流程图Fig.2 Direct_search algorithm on execution flowchart

Direct_Search算法在二维空间内的搜索算法描述如下：

1）从搜索源节点出发，搜索开始。搜索源节点根据其邻居节点的存储信息和一些搜索参数计算下一个被搜索的节点，下一个被搜索的区域以及下一个被搜索节点所负责的搜索方向，然后跳转至步骤2）。

2）如果经过步骤1）计算出的下一跳节点的数量为0，则跳转至步骤4）；如果经过步骤 1）计算的下一跳节点的数量不为 0，则搜索消息将被发送给这些“下一跳节点”，然后跳转至步骤3）。

3）接收到搜索消息的节点进行本地文件搜索，搜索到符合条件的文件，搜索结果将被返回至搜索源节点，然后跳转至步骤4）；搜索不到符合条件的文件，那么就会执行步骤1）中的搜索操作，计算出的结果生成搜索文件，发送给下一跳节点。

4）搜索在现有节点负责的搜索区域内结束。

5）搜索在各个搜索区域内都被完成时，整个搜索结束。

3 Direct_Search 算法在二维空间内的模拟实验及结果分析

本次模拟实验的主要目的是对Direct_Search算法在搜索执行过程中的覆盖率进行定量分析，从而验证该算法的正确性和可行性，同时因为在算法执行的整个过程中没有涉及到P2P网络通信协议的模拟情况，为了达到简洁高效更加直观的验证该算法，文中是Intel Core i3主频为2.93 GHz的双核处理器、内存为4 GB、操作系统为Windows XP Server Pack3、开发语言C++的机器上进行的，通过编写程序来模拟算法搜索执行过程，获取实验数据的。

3.1 模拟实验结果分析

在对Direct_Search算法的五次模拟实验过程中，不考虑网络的边缘节点，在网络中设置了10 000个搜索节点，每个节点设定存储了48个邻居节点的信息，即取m=48。实验数据如表1所示。搜索覆盖率S_C用式（2）表示。

表1 Direct_Search算法的五次模拟实验数据Tab.1 Direct_search algorithm of five times simulation experiment data

表1中的实验数据说明了Direct_Search算法的搜索覆盖率在95%左右。

3.2 Direct_Search算法的搜索过程仿真实验

图3显示了采用Direct_Search算法进行搜索的仿真过程。图中的星号代表网络节点，星号下边的数字是该节点的id。该图显示的是从图的右上方节点向左下方节点进行的搜索过程。两个节点之间有连线，表示在搜索过程中，其中一个节点是另一个节点的下一跳节点。图中有些节点是孤立节点，既没有直线把它和别的节点连起来。这些孤立节点就是在搜索中被忽略的节点。在图3中，许多节点只有上一跳节点，没有下一跳的节点。这表示在搜索过程中，这些节点没有在自己的搜索区域中找到符合条件的下一跳节点，搜索在这些节点处中断。在搜索过程中，参与搜索的节点所负责的搜索区域为扇形。在搜索中断处，那些比当前节点距离搜索源点更远的、在搜索区域中的节点，是无法被搜索到的。

图3 Direct_Search搜索过程仿真实验图Fig.3 Experimental graph of direct_search process in simulation

4 结束语

最近几年，P2P技术得到了极大的发展，P2P技术作为一种应用日益广泛的技术，其功能﹑性能逐渐得到人们的重视。由于P2P运行环境比较复杂，所以到目前为止，在国际上还没有一个通用P2P搜索方法。笔者根据Flooding算法及其改进算法的理念提出了P2P网络中基于方向的搜索算法—Direct_Search算法，讲述了Direct_Search算法的基本思想，设计的详细过程，并对其进行了模拟实验以及实验结果分析。由于P2P网络的搜索是现今研究的一个热点，P2P网络的搜索方面的研究还在探索中，尤其在资源搜索效率和准确定位方面还有很大的改善空间。

[1]刘金岭.基于P2P网络的AVL索引树范围查询研究[J].微电子学与计算机，2011，28（2）:11-14.

LIU Jin-ling.Study of the AVL-index tree range query based on P2P networks[J].Microelectronics and Computer，2011，28（2）:11-14.

[2]刘金岭.基于Chord覆盖网络索引结构的多属性查询[J].微电子学与计算机，2011，28（3）:104-107.

LIU Jin-ling.An index structure based on chord overlay network of multi-attribute query[J].Microelectronics and Computer，2011，28（3）:104-107.

[3]Kim H，Kim Y.Restricted path flooding scheme in distributed P2P overlay networks[C]//ICISS 2008:International Conference on Information Science and Security Proceedings，2008:58-61.

[4]Gkantsid I S C，Miha I LM，Saber I A.Hybrid search schemes for unstructured peer-to-peer networks[C]//Proc of IEEE INFOCOM.Miami:IEEE Press，2005:1526-1537.

[5]吴艾，刘心松，郝尧，等.P2ST:基于带权搜索树的P2P搜索模型[J].计算机科学，2007，34（8）:64-68.

WU Ai， LIU Xin-song， HAO Yao， et al.P2ST:A weighted search tree based P2P searching model[J].Computer Science，2007，34（8）:64-68.

[6]李士宁，夏贻勇，杜艳丽.对等网络中DHT搜索算法综述[J].计算机应用研究，2008，25（6）:1611-1615.

LI Shi-ning， XIA Yi-yong， DU Yan-li.Survey of DHT search algorithm in peer-to-peer network [J].Application Research of Computers，2008，25（6）:1611-1615.

Based on research of direction algorithm research in distributed P2P network

Flooding algorithm and its improved algorithm based on the concept of P2P networks is proposed based on the direction of the search algorithm,which dynamically generate a source point to search for the root of the search tree,the search along the search tree,the search process effectively avoided redundant search packets in the production,save network bandwidth and improve the efficiency and network performance.By two-dimensional digital data and image data analysis of the two experimental results fully reflected the algorithm in the search process for effectiveness and feasibility

distributed； P2P networks； topology； direction search

TP393

A

1674－6236（2011）24-0078-04

2011-10-12 稿件编号：201110048

武汉工程大学青年基金（Q200802）

刘 卫（1965—），女，云南昆明人，副教授。研究方向：网络结构/数据挖掘。LIU Wei1，LIU Jin-ling2

（1.Computer Center,Kunming University of Science and Technology,Kunming650024,China；

2.Computer Engineering Faculty,Huaiyin Institute of Technology,Huaian223003,China）