基于衰落Bloom Filter的P2P网络弱状态路由算法

• 作者: 朱桂明 郭得科 金士尧
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 对等计算 有向随机网络 弱状态路由 衰落Bloom Filter 噪音
• 年，卷（期）: 2011,（11）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 2810-2819
• 分类号: TP393
• 字数: 8288字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03863

摘要

在P2P网络中,基于衰落Bloom Filter的弱状态路由算法试图将每条查询消息沿着成员资格信息量最强的方向传递,并最终以较低的传输代价和传输时延确保较高的查准率.衰落Bloom Filter在传递过程中存在严重的多径叠加和噪音问题,这直接导致查询消息会以很高的概率沿着错误的方向传播,甚至会退化为泛洪路由算法.为了解决这一挑战性难题,提出了DWalker这种基于衰落Bloom Filter的高效弱状态路由算法.DWalker基于有向随机网络,采用指数衰落Bloom Filter来发布和传播每个节点共享资源的信息,且其最大传播距离小于网络中任意两点之间距离的期望值,从而有效抑制了衰落Bloom Filter在传播过程中的多径叠加问题.DWalker采用多个Bloom Filter而不是单个Bloom Filter来表达一项路由条目,在单个Bloom Filter的错误发生概率达到设计上限时,可按需动态增加新的Bloom Filter,以将更多资源对象信息纳入到当前路由条目中.DWalker仅根据当前节点的各项路由条目中值为1的比特位所占的最大比例,以及查询消息在正确转发方向对应的路由条目中对应比特位中值为1的个数的临界值,就能使进入目标对象传播范围内的查询消息以较高的概率辨认出正确的路由方向.理论分析和实验结果表明,DWalker能够以较低的查询消息代价、较小的路由条目存储开销以及较短的查询时延,使绝大多数查询消息沿正确方向转发,从而获得较高的查准率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	金士尧	国防科学技术大学计算机学院并行与分布处理国防科技重点实验室	71	714	15.0	23.0
2	郭得科	国防科学技术大学信息系统与管理学院信息系统工程国防科技重点实验室	14	139	5.0	11.0
3	朱桂明	国防科学技术大学计算机学院并行与分布处理国防科技重点实验室	6	25	3.0	4.0