论文研究-基于网络全局与搜索局部特性的P2P搜索算法.pdf
需积分: 0 194 浏览量
2019-07-22
20:15:55
上传
评论
收藏 852KB PDF 举报
收稿日期： ２０１０唱０１唱０８； 修回日期： ２０１０唱０２唱２５
作者简介：周慧（１９８３唱） ，女，湖北鄂州人，博士研究生，主要研究方向为对等网络、分布式计算等（ ｚｈｏｕｈｕｉｗｈｕｔ＠１６３．ｃｏｍ） ；杨杰（１９６０唱） ，湖北
武汉人，教授，博导，主要研究方向为信息技术、对等网络等．
基 于 网 络 全 局 与 搜 索 局 部 特 性 的 Ｐ２ Ｐ 搜 索 算 法
周 慧， 杨 杰
（武汉理工大学 信息工程学院， 武汉 ４３００６３）
摘 要： 现有启发式搜索只考虑了搜索过程中的局部性原理，少数的考虑了网络的全局特征，却没有一个算法
能同时利用局部性原理和全局性原理来指导搜索过程。 为此提出了一种基于动态拓扑调整的搜索算法 ＧＬＭＷ，
在考虑网络的幂律特征与异构性的基础上利用搜索过程中存在的局部特征来构建搜索协议。 通过在仿真软件
上的实验，不同的网络规模下比较分析结果表明，算法可以得到更好的查询效果。 在同等网络环境下，ＧＬＭＷ 查
询到的目标副本文件数较多，延时较短，对网络中高能力节点的利用率高。
关键词： 对等网络； 全局特征； 局部特征； 缓存定位； 遍历器
中图分类号： ＴＰ３０１．６ 文献标志码： Ａ 文章编号： １００１唱３６９５（２０１０）０８唱３１１５唱０５
ｄｏｉ：１０．３９６９ ／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１０．０８．０８２
Ｓｅａｒｃｈ ｍｅｔｈｏｄ ｔａｋｉｎｇ ｆｕｌｌ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｏｆ ｂｏｔｈ ｇｌｏｂａｌ ａｎｄ
ｐａｒｔｉａｌ ｆｅａｔｕｒｅｓ ｉｎ ｕｎｓｔｒｕｃｔｕｒｅｄ Ｐ２Ｐ ｎｅｔｗｏｒｋｓ
ＺＨＯＵ Ｈｕｉ， ＹＡＮＧ Ｊｉｅ
（ Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ ４３００６３， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ｍｏｓｔ ｅｘｉｓｔｉｎｇ ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ｍｅｔｈｏｄｓ ｏｎｌｙ ｃｏｎｓｉｄｅｒｅｄ ｐａｒｔｉａｌ ｆｅａｔｕｒｅｓ ｅｘｉｓｔｅｄ ｉｎ ｓｅａｒｃｈ ｐｒｏｃｅｓｓ， ｏｒ ｏｎｌｙ ｐａｉｄ ａｔｔｅｎ唱
ｔｉｏｎｓ ｔｏ ｔｈｅ ｇｌｏｂａｌ ｆｅａｔｕｒｅｓ ｉｎ ｎｅｔｗｏｒｋｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｕｔ ｆｏｒｗａｒｄ ａ ｓｅａｒｃｈ ｍｅｔｈｏｄ ｃａｌｌｅｄ ＧＬＭＷ．Ｔｈｅ ＧＬＭＷ ｒｅｔａｉｎｅｄ ｔｈｅ ａｄ唱
ｖａｎｔａｇｅ ｏｆ ｄｙｎａｍｉｃ ｔｏｐｏｌｏｇｙ ａｄａｐｔａｔｉｏｎ ｉｎ ｃｏｎｆｏｒｍｉｎｇ ｔｏ ｔｈｅ ｇｌｏｂａｌ ｆｅａｔｕｒｅｓ ｉｎ ｎｅｔｗｏｒｋｓ， ａｎｄ ａｄｄｅｄ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｏｆ ｔｈｅ ｐａｒｔｉａｌ
ｆｅａｔｕｒｅｓ ｉｎ ｏｂｊｅｃｔ ｓｅａｒｃｈｉｎｇ ｐｒｏｃｅｓｓ， ｏｐｔｉｍｉｚｉｎｇ ｃｕｒｒｅｎｔ ａｎｄ ｓｕｂｓｅｑｕｅｎｔ ｒｅｑｕｅｓｔｓ ａｃｃｏｒｄｉｎｇ ｔｏ ｈｉｓｔｏｒｉｃａｌ ｓｅａｒｃｈ ｒｅｃｏｒｄｓ ａｎｄ
ｍａｋｉｎｇ ｂｅｔｔｅｒ ｕｓｅ ｏｆ ｈｉｇｈ ｃａｐａｃｉｔｙ ｎｏｄｅｓ ｔｏ ｓｅｒｖｅ ｓｅａｒｃｈ ｐｒｏｃｅｓｓ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ａｎｄ ａｎａｌｙｓｉｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＧＬＭＷ ｃａｎ
ｆｉｎｄ ｍｏｒｅ ｏｂｊｅｃｔ ｒｅｐｌｉｃａｓ ｗｉｔｈ ｌｏｗｅｒ ｄｅｌａｙｓ， ａｃｈｉｅｖｅ ｂｅｔｔｅｒ ｕｔｉｌｉｚａｔｉｏｎ ｏｆ ｈｉｇｈ ｃａｐａｃｉｔｙ ｎｏｄｅｓ．
Ｋｅｙ ｗｏｒｄｓ： Ｐ２Ｐ； ｇｌｏｂａｌ ｆｅａｔｕｒｅ； ｐａｒｔｉａｌ ｆｅａｔｕｒｅ； ｃａｃｈｉｎｇ ａｎｄ ｌｏｃａｔｉｎｇ； ｗａｌｋｅｒ
０ 引言
近年来，对等（ ｐｅｅｒ唱ｔｏ唱ｐｅｅｒ，Ｐ２Ｐ） 计算系统基于一种完全
分布式、协同网络的设计，使得每个节点完全自治，责任相同，
成为计算机领域的研究热点。 作为对等计算的应用之一，文件
资源共享一直是网络技术发展的重要推动力，而其应用的一个
核心问题是有效的文件搜索机制，这也是提高网络可扩展性、
解决网络带宽被吞噬的关键所在。
根据 Ｐ２Ｐ 网络控制层实现的不同方式，可将其分为结构
化和非结构化两种体系结构。 结构化对等资源共享系统的网
络拓扑和资源部署严格遵守协议规定，要求网络规模的可扩展
性与搜索的高效性。 然而由于 Ｐ２Ｐ 网络中节点的自治与高动
态，节点的存在具有瞬时性。 对 Ｇｎｕｔｅｌｌａ 和 Ｎａｐｓｔｅｒ 的研究表
明，一个节点的平均生存时间大约是 １０ ｍｉｎ
［１］
，这就是说，对于
一个节点数量达到 １０
５
的大型对等系统，大约每分钟有超过
１ ６００ 个节点进出网络。 频繁的网络波动会给结构化网络带来
影响。 另外，基于关键字的查找比基于哈希表的精确查找更普
遍，因此无结构 Ｐ２Ｐ 网络更加流行。
本文主要对无结构化 Ｐ２Ｐ 网络的搜索技术进行研究，在
分析研究了现有搜索方法后，提出了一种基于动态拓扑调整的
搜索算法。 算法在分析了 Ｐ２Ｐ 网络的全局特征与搜索进程的
局部特征之后，将全局特征与局部特性加入到搜索协议，指导
搜索过程，并在逐步搜索中进行指导调整，提高搜索效率。 通
过 ＯＭＮｅＴＰＰ 与 ＯｖｅｒＳｉｍ 进行仿真实现，对仿真结果进行分析，
并与原搜索算法进行比较。 实验表明，改进的搜索方法能够增
加目标查找数，减少查找延时，提高查询效率。
１ 相关工作
根据查询请求广播条件的不同，可以将无结构 Ｐ２Ｐ 网络
的搜索分为盲目搜索和启发式搜索两个部分。 所谓盲目搜索，
就是指将查询消息随机无序地传播给一定数目的节点，以此来
满足搜索。 启发式搜索是指利用文件资源的位置信息来进行
查询。 现有的几种代表性搜索算法如表 １ 所示
［２１４］
。
在非结构 Ｐ２Ｐ 网路中，洪泛方式是最基本的，也是最盲目
的搜索方式。 文献［３，４，８］ 中介绍的几种算法实际上都是洪
泛方式的改进算法，如改进的 ＢＦＳ、迭代加深、随机游走等。 从
相关文献的仿真结果来看，这些算法在提高搜索性能上都有一
定的效果，然而若从原理上来分析，改进的算法往往缺乏足够
的理论依据，显得过于机械。 盲搜索的主要贡献在于网络消息
量的减少，搜索成功率并没有多大的提高
。
第 ２７ 卷第 ８ 期
２０１０ 年 ８ 月
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ．２７ Ｎｏ．８
Ａｕｇ．２０１０
资源评论
