基于P2P网络的分布式广度优先搜-徐图-修改后

VIP免费

3.0 李佳 2024-09-23 4 4 100.5KB 4 页 150积分

侵权投诉

基于 P2P 网络的分布式广度优先搜索的研究

摘要：针对小范围 P2P 搜索环境，提出了全新的 P2P 搜索模型，并研究了该搜索模型的各重要组成部分：

BFS 算法、启发式搜索算法中 2 跳节点的信息、DBFS 算法的思路，并着重阐述了 DBFS 搜索算法的主要策略

及具体的设计实现。测试结果证明，采用分布式广度优先搜索算法的 DBFS 模型具有冗余的数据包少、能减

轻网络的负载，提高 P2P 搜索的速度等优点。

关键词:分布式广度优先；P2P 网络；搜索

中图分类号：TP393.06 文献标识码：

Study of distributed breadth first search based on P2P network

XU Tu LI De-min

(Donghua University Information Department Shanghai 200051)

Abstract: This paper puts forward an new P2P search model specifically for small range P2P searches for an environment, and studies

every important component being a model's turn respectively: DBFS algorithm, 2 springs in the BFS algorithm, the algorithmic train

of thought of DBFS, emphasize the main tactics, mathematics certificate and concrete design having set forth the DBFS algorithm

coming true. The experiment bear results indicates redundancy data bag characteristics such as few, being able to lighten network

loads on certain degree, enhances P2P search speed.

Keywords: Distributed Breadth First Search； Peer-to-Peer Network；Search

1 引言

广度优先搜索能够确保搜索到网络中的每个节点的信息，同时每个节点只被搜索一次。但是，进行广

度优先搜索需要事先知道 P2P 网络中关于所有节点的网络拓扑结构，这在 P2P 网络中几乎是不可能的[1]。

在 P2P 网络中，虽然可以通过节点之间相互交换信息来获得所有节点的网络拓扑结构，但是这需要

大量的信息交换，会给网络带来很大的负载，特别是当网络的规模比较大时，要获得网络拓扑结构图所

带来的负载是不可想象的[2]。广度优先搜索在消除了网络中存在的环路，也即消除冗余数据包的同时，又

带来了新的弊端.

结合广度优先搜索不会产生冗余的优点和 P2P 网络的动态特性，以及本地索引搜索、启发式搜索的优

点，本文提出在小范围内进行广度优先搜索的方法，称为分布式广度优先搜索(DBFS)。分布式广度优先搜

索可以在区域内部的范围内大量减少冗余的搜索包，同时，由于范围比较小，因此具有很好的可扩展性

和健壮性，能够适应 P2P 网络的动态变化。

2 分布式广度优先思路

在分布式广度优先搜索中，节点对 2 跳内的邻居节点进行广度优先遍历，建立最优生成树，并决定

通过哪些邻居节点来转发消息，其余的邻居节点不转发消息，而只是查询并返回查询结果的信息。

通过这种方式，减少了需要查询的邻居节点个数，减少了查询的次数；同时，由于最优生成树的建

立，在区域内部消除了环路，从而减少了冗余。被选中进行转发的邻居节点再广度优先遍历 2 跳内的邻居

节点，决定哪些邻居节点需要转发消息。这个过程不断进行，直到 TTL=0 为止。

3 分布式广度优先搜索模型

图 1 是一个分布式广度优先的原理图。在图中，在搜索信息没有收到之前，首先通过启发式搜索的统

计方法发现节点 A，B，C，D 四个节点具有在线时间比较长，在以往的搜索中返回的搜索结果比较多，响

应的时间比较快等特点，具有索引节点所应该具备的特点，同时它们相距 4 跳远，满足建立 2 跳远节点信

息的条件，所以确定节点 A，B，C，D 四个节点为索引节点，其他节点为转发节点[3]。

在搜索信息到来时，其它所有节点都只转发这一搜索信息，只有节点 A,B,C,D才响应搜索信息，同

时返回与搜索信息相匹配的信息。由于所有节点的信息都存储到了索引节点上，所以，只查询节点

A，B，C,D 四个节点，就能达到查询图中所有节点信息的目的，大大减少了搜索次数，同时大量减少了冗

余的搜索数据包，减少了返回信息时多余的数据包。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

150 积分 4人已下载

立即下载 VIP免费下载

摘要：

基于P2P网络的分布式广度优先搜索的研究摘要：针对小范围P2P搜索环境，提出了全新的P2P搜索模型，并研究了该搜索模型的各重要组成部分：BFS算法、启发式搜索算法中2跳节点的信息、DBFS算法的思路，并着重阐述了DBFS搜索算法的主要策略及具体的设计实现。测试结果证明，采用分布式广度优先搜索算法的DBFS模型具有冗余的数据包少、能减轻网络的负载，提高P2P搜索的速度等优点。关键词:分布式广度优先；P2P网络；搜索中图分类号：TP393.06文献标识码：StudyofdistributedbreadthfirstsearchbasedonP2PnetworkXUTuLIDe-min(Donghu...

展开>> 收起<<

基于P2P网络的分布式广度优先搜-徐图-修改后.doc

共4页,预览1页

还剩页未读，继续阅读

基于P2P网络的分布式广度优先搜-徐图-修改后

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: