基于P2P的分布式搜索算法研究

基于P2P的分布式搜索算法研究 软 件 导 刊第8卷 第3期 Vol.8 No.3 2009年 3 月 Software Guide Mar. 2009 基于P2P的分布式搜索算法研究 ,陈雪兆杰杨 ,1,湖南科技学院,湖南 永州 425100,2.永州职业技术学院,湖南 永州 425100, 摘要,针对目前P2P系统中广泛采用的泛洪搜索方法中产生大量冗余搜索包的缺点,提出了一种基于小范围P2P搜 索环境的全新搜索模型—— 将广度优先搜索算法和本地索引搜索算法相结合,以增强节点间的交互能力。 最后用数学方法证明了它的有效性。 关键词,P2P,算法,分布式,搜索 中图分类号,TP301,6文献标识码,A 文章编号,1672-7800,2009,03-0043-02 收到一个搜索包,就不会产生冗余。 0 引言可以看出,减少冗余搜索数据包的有效方法是减少P2P网 ,直到完全消除网络中的环路。 由此想到建立一棵 络中的环路 ,可以完全消除网络中的环路。 目前,关于P2P技术研究的一个主要问题是搜索问题。 现生成树的方法 在P2P系统采用泛洪,Floodin,g进行搜索,一个节点向所有邻居 节点广播查询消息, 邻居节点再向自己的所有邻居节点广播。 2 广度优先搜索分析泛洪虽然具有节点覆盖率高、 健壮性好以及实现简单的优点, 但是,泛洪会产生大量冗余搜索包,带来很大的网络负载。 本文 广度优先搜索算法,又称宽度优先搜索,即BFS,是最简便 P2P网络的特性,提出了分布式广 结合广度优先搜索的优点和的图的搜索算法之一。 为了减少冗余的搜索包,最简单的方法 。 度优先搜索的方法,建立网络图的广度优先生成树,源节点根 就是以源节点为根 。这样可以保证 据广度优先生成树将查询消息发送到每个节点 , 而且每个节点只收到一次查询消 每个节点都收到查询消息 1 冗余搜索包产生的原因及分析,不会产生冗余。 息 已知图G=,V,E,和一个源顶点s,广度优先搜索以一种系 我们把P2P 网络看作一个无向图 , 顶点 代 网 络 中 的 节G的边,从而“发现”s所能到达的所有顶点,并计 统的方式探寻 点,边表示节点之间的连接的路径。 直接相连的两个节点互为s到所有这些顶点的距离,最少边数,。 该算法同时能生成一 算邻居,Neighbo,r节点。 消息从一个节点发送到另一个节点肯定 s且包括所有可达顶点的广度优先树。 对从s可达的任意 棵根为。路径的长度用路径上节点的个数即跳 要经过图中的一条路径v,广度优先树中从s到v的路径对应于图G中从s到v的最短 顶点,Hop,来表示。 如果两个节点之间的最短路径长度为N,我们 数,即包含最小边数的路径。 该算法对有向图和无向图同样 路径N跳远。 就说这两个节点相距。 适用 在P2P搜索中之所以会产生冗余搜索包,是因为网络中存之所以称之为广度优先算法,是因为算法自始至终一直通 在圈,也就是网络中存在着环路。 如图1、图2所示,箭头的实线 ,也就是说,算法 过已找到和未找到顶点之间的边界向外扩展,当发出搜索后,通过图中实线的路径,图 表示发出搜索的次数s距离为k的所有顶点,然后再去搜索和s距离为k+1 首先搜索和。箭头虚线表示冗余的搜索 中的所有节点全部都收到搜索信息的其他顶点。 ,虚线所示的搜索信息为多余的、重复的。 相反,如果网络图 包 ,由于树形图中不存在环路,因此每个节点只会 是一个树形图 3 分布式广度优先算法 3.1 分布式广度优先搜索模型 如图3所示,它是一个分布式广度优先的原理图,同时也是 、理想化了的P2P网络图。 一个被简化了的 图1 三个节点的圈 图2 四个节点的圈 作者简介,杨杰,1976-,,男,湖南永州人,硕士,湖南科技学院计算机系讲师,研究方向为计算机网络、算法、数据库,陈雪兆,1975,,女,湖南永州 - 人,永州职业技术学院计算机系讲师,研究方向为计算机网络、数据库。 图中,在搜索信息没有收到之前,首先通过启发式搜索的v,中至少有一个节点不是叶子节点,因此,v,v,… ,v,中至少 m12m统计方法发现节点A、B、C、D四个节点具有在线时间比较长、在 有一个节点会被选做转发节点。 所以v必定会收到消息。 以往的搜索中返回的搜索结果比较多、响应的时间比较快等特 3,2,2 算法能够终 止 点,具有索引节点所应该具备的特点,同时它们相距4跳远,满 证明, 在分布式广度优先搜索中, 节点在转发时都会将 足建立2跳远节点信息的条件, 所以确定节点A、B、C、D四个节 TTL值减为1,因此,TTL必然会在某个时刻为0。 节点在检查到 点为索引节点,其他节点为转发节点。 TTL=0时便不再继续转发,过程结束。 所以算法是能够终止的。 4 仿真结果对比分析 实验选择了节点个数N=10,20,30以及节点度数?=2,3,5 的 9 种 组 合 情 况 , 对分布式广度优 先 搜索方法和泛 洪 搜索 ,Floodin,g分别进行了模拟,实验结果如表1所示。 表1 实验结果 分布广度优先差值flooding N=10 18 12 6 分布式广度优先搜索原理 图3 D=2 N=20 46 31 15 这四个节点分别索引2跳节点内的节点信息,图中4个节点 N=30 65 39 26 索引的信息分别是4个椭圆中的所有节点中的信息。 这一索引 N=10 45 26 19 过程是通过广度优先搜索和启发式搜索相结合,分别在各自的 N=20 88 51 37 D=3 区域内确立一棵广度优先生成树来完成的,这样就保证了在区 N=30 134 76 58 域内部每个节点能够收到且只收到一次索引信息。同时也保证 N=10 72 36 36 了所有节点的信息都存储到索引节点上, 即图中的节点A、B、 N=20 139 76 63 D=5 C、D。 N=30 203 114 89 在搜索信息到来时, 其他所有节点都只转发这一搜索信 从实验结果可以看出,分布式广度优先搜索方法总是能够息,只有节点A、B、C、D才响应搜索信息,同时返回与搜索信息 减少冗余的搜索包,而且节点个数越多,减少的冗余数据包越 相匹配的信息。 由于所有节点的信息都存储到了索引节点上, 多,节点的度数越多,减少的冗余数据包也越多。 随着节点度数 所以,只查询节点A、B、C、D四个节点,就能达到查询图3中所有 和节点个数的增加, 这两者之间的发送的搜索数据包也在增 节点信息的目的,大大减少了搜索次数,同时大量减少了冗余 加,它们之间的差值也在增加,效果就越显著。 的搜索数据包,减少了返回信息时多余的数据包。 通过分布式广度优先搜索,能够保证每个节点的信息都能 够被搜索到,这就提高了搜索的效率和成功率,由于在2跳节点 5 结束语的内部采用了启发式搜索、广度优先搜索相结合的方法来建立 索引节点的信息, 所以在区域内部大大地减少了搜索的次数, 本文以节点之间的网络通信质量为依据, 将网络按2跳距 减少了冗余的搜索数据包,也就提高了搜索的速度。 离节点进行分组, 组的核心维护着一定数量的高速连接的节 总之,通过分布式广度优先搜索,能大量减少搜索的次数, 点,同时为了覆盖整个网络,将网络中通信质量最佳的节点置 减少区域内部冗余的数据包, 减轻搜索过程中网络的负载,提 于组核心级的核心,并采用建立最优生成数的方法对区域内部 高搜索的速度和准确率。 加以管理。 搜索时,只搜索索引节点的信息,就可以搜索出整个 区域节点的信息。 最后, 将分布式广度优先搜索方法和现在 P2P网络中采用的泛洪方法进行了比较,并对分布式广度优先 搜索进行了相关证明和分析。 正确性证明3.2 3,2,1 算法能搜索到网 络中的每个节点 证明,我们用归纳法来证明。 参考文献, 因为源节点s会向它的所有邻居发送消息,所以距离s节点 许斌.JXTA-Java P2P 网络编程技术,M,.北京,清华大学出 版 社, ,1, 一跳远的节点都能收到消息。 假设距离s节点N,N?1,跳远的 2003. 节点都能收到消息。s节点N+1跳远的节点也能 下面证明距离管昌,邓磊,崔华.基于P2P技术的流媒 体服 务 模型 研 究,J,. 武 汉 ,2, 收到消息。 ,2006,2,. 理工大学学报 李 祖 鹏 , 黄 道 颖 , 庄 雷. 基 于Pee-rto-Peer 网 络 的JXTA 技 术 研 究 从距离s节点N+1跳远的节点中任意选出一个节点, 假设 ,3, ,J,.计算机工程与应用,2003,11,. 为v,由于图是连通图,源节点s与v之间至少有一条路径,所以 黄道 颖, 李 祖 鹏, 庄 雷 , 等. 分 布 式Pee-rto-Peer 网 络Gmitella 模 型 距离s节点N跳远的节点中至少有一个节点是v的邻居节点,假 ,4, ,J,.计算机工程与应用,2003,5,. 研究设在距离s 节点N 跳远的节点中v 的邻居节点为 ,v,v, … ,v,。 12m,责任编辑,袁 月, 在距离s节点N-1跳远的节点进行广度优先遍历时,,v,v, … , 12