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

VIP免费

3.0 林婧 2024-09-20 4 4 495KB 6 页 150积分

侵权投诉

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

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

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

发式搜索算法中 2 跳节点的信息、DBFS 算法的思路，并着重阐述了 DBFS 搜索算法的主要策略及具体的设计实现。测试结果

证明，采用分布式广度优先搜索算法的 DBFS 模型具有冗余的数据包少、能减轻网络的负载，提高 P2P 搜索的速度，以及提

高 P2P 的搜索效率等优点。

关键字：分布式广度优先；P2P 网络；搜索

Study of Distributed Breadth First Search based on P2P Network

XU Tu LI De-min

Shanghai Donghua University Information Department

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， the DBFS model having adopt distributed extent to give priority to an algorithm has.

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

0 引言

由于 P2P 蕴含着巨大的技术潜力和商业价值，许多学术机构、大公司先后投入到对 P2P 技术的研究之

中。要想充分的利用 P2P 网络上的资源，首先要有效的发现需要的资源，即在 P2P 网络中进行搜索【1】。目

前，P2P 研究中的一个主要问题就是搜索问题。为了在 P2P 网络中进行有效的搜索，本文结合广度优先搜

索的优点和 P2P 网络的特性，提出了分布式广度优先搜索的方法。编程模拟分布式广度优先搜索和泛洪搜

索，对这两种方法进行实验分析。

1 分布式广度优先搜索算法的提出

文献【1】指出广度优先搜索能够确保搜索到网络中的每个节点的信息，同时每个节点只被搜索一次。

但是，进行广度优先搜索需要事先知道 P2P 网络中关于所有节点的网络拓扑结构，这在 P2P 网络中几乎是

不可能的。

文献【2】指出在 P2P 网络中，虽然可以通过节点之间相互交换信息来获得所有节点的网络拓扑结构，

但是这需要大量的信息交换，会给网络带来很大的负载，特别是当网络的规模比较大时，要获得网络拓

扑结构图所带来的负载是不可想象的。广度优先搜索在消除了网络中存在的环路，也即消除冗余数据包的

同时，又带来了新的弊端.

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

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

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

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

2 分布式广度优先思路

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

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

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

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

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

本文中，用 N(v)表示节点 v的邻居节点的集合，N(N(v))表示节点 v的邻居节点的邻居节点的集合，

也就是 v的 2 跳距离的节点。

在图中，N (Vi)，N(Vj)，N(N(Vj)分别用一个圈表示。假设节点 Vj收到节点 Vi发送的查询请求消息，

并且 Vj是Vi的转发表里的节点，那么 Vj需要转发请求消息，因此需要决定自己的转发表。

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

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

150 积分 4人已下载

立即下载 VIP免费下载

摘要：

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

展开>> 收起<<

基于P2P网络的分布式广度优先搜索.doc

共6页,预览1页

还剩页未读，继续阅读

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: