面向非结构化P2P网络的双向随机漫步搜索机制

• 作者: 孟祥武 张玉洁 马文明
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: Peer-to-Peer 搜索 随机漫步 抗扰动 拓扑
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 894-911
• 分类号: TP393
• 字数: 12603字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04086

摘要

为解决目前Random Walk改进算法中过于依赖历史搜索记录而导致动态网络环境下搜索命中率低、网络开销过高和稀有资源的搜索成功率提高不明显等问题,通过分析随机漫步的基本性质和易转向高度数节点的搜索特性,提出了一种双向随机漫步搜索机制——BRWS(bidirectional random walk search),并证明了其能够提高包括稀有资源在内的搜索成功率,抗扰动性强.分别在静态和动态网络环境中,将Random Walk,APS(adaptive probabilistic search),PQR(path-traceable query routing),P2PBSN(peer-to-peer based on social network)和BRWS基于Random Graph、Scale Free网络、Small World网络3种拓扑进行了对比实验.结果表明,BRWS可以以较少的网络搜索代价,极大地提高搜索成功率；并在动态网络环境中,对稀有资源的搜索成功率也有显著提高.所提出的方法可适用于P2P文件分发网络应用中.