非结构化P2P中搜索算法及信任机制研究

论文摘要

对等网络应用自出现以来,发展非常迅速,引起了学术界和工业界的广泛关注,因此,对对等网络的研究一直非常活跃。非结构化对等网络是实际应用中大量部署的对等网络应用,所以对非结构化对等网络的研究具有重要的现实意义。特别是非结构化对等网络中的搜索算法和信任机制,对系统性能起着关键的作用,也是近年来广泛研究的热点领域。本文是作者在该领域研究工作的总结,主要创新性工作有以下几点:1.研究了非结构化P2P中高度节点的作用,提出利用高度节点可以改善非结构化P2P系统的性能,如搜索算法的性能。提出一个用于评估传播机制性能的评估框架,并基于该评估框架分析比较了四种传播机制的性能,指出随机步行传播机制和高度步行传播机制具有更高的复本率、更低的开销。2.为了有效改善类Gnutella网络的性能,在随机步行传播机制和高度步行传播机制的基础上,提出四个用于非结构化P2P的搜索算法,分析了这四个搜索算法的性能。大量实验表明这几个搜索算法具有较高的成功率、较低的搜索开销,并且搜索速度较快。由于这几个搜索算法采用的搜索机制和传播机制的不同,具有不同的性能特点,适用于不同的应用环境。3.为了消除对等网络中恶意节点对系统造成的危害,研究了声望模型,提出一个基于社会规则的声望模型,给出了模型参数的计算方法以及两个基于该声望模型的信任构造方案。通过对各类攻击的仿真表明,该声望模型能够有效减小各类攻击对网络系统造成的危害。4.在基于社会规则的声望模型的基础上,结合RWSS搜索方法提出一个用于非结构化P2P的SRRT信任管理方案。在该信任方案中,给出了评价信息的分布式存储方案以及信任管理中信誉和满意率的计算方法,并提出一个信誉搜索算法用于搜索节点的评价信息。提出一个基于信任的拓扑进化算法,该算法改善了网络拓扑结构,增加了网络性能的稳定性。5.研究了P2P网的应用,提出将非结构化P2P技术应用于Web服务通告领域用于构建通告代理集群,实验仿真表明该通告代理集群具有很好的动态特性,对随机节点故障是强壮的。同时,提出采用基于主题的分层技术管理通告代理集群,并给出一个主题层通告消息广播算法TopicLayerBroadcast,仿真表明该广播算法具有高可靠性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 对等网络
• 1.2 对等网络的应用及意义
• 1.3 对等网络的关键问题
• 1.4 本文主要工作
• 1.5 章节安排
• 第二章 非结构化对等网络研究现状及背景知识
• 2.1 复杂网络
• 2.1.1 随机图模型
• 2.1.2 小世界模型
• 2.1.3 无尺度模型
• 2.2 非结构化对等网络是Power-Law网络
• 2.3 非结构化对等网络中的搜索方法
• 2.3.1 盲目搜索方法
• 2.3.2 基于信息的搜索方法
• 2.4 非结构化对等网络中的信任机制
• 2.4.1 基于策略的信任机制
• 2.4.2 基于信誉的信任机制
• 2.4.3 基于社会网络的信任机制
• 2.5 小结
• 第三章 非结构化对等网络中传播机制研究
• 3.1 引言
• 3.2 相关工作
• 3.3 传播机制
• 3.3.1 洪泛传播机制
• 3.3.1.1 性能分析
• 3.3.1.2 实验仿真
• 3.3.2 Percolation传播机制
• 3.3.2.1 性能分析
• 3.3.2.2 实验仿真
• 3.3.3 随机步行传播机制
• 3.3.3.1 性能分析
• 3.3.3.2 实验仿真
• 3.3.4 高度步行传播机制
• 3.3.4.1 性能分析
• 3.3.4.2 实验仿真
• 3.4 评估框架
• 3.5 基于评估框架四种传播机制性能比较
• 3.5.1 基于复本率和开销的性能比较
• 3.5.2 基于搜索算法的性能比较
• 3.6 小结
• 第四章 非结构化对等网络中搜索方法研究
• 4.1 搜索方法
• 4.1.1 RWSS搜索方法
• 4.1.2 RHWS搜索方法
• 4.1.3 HRWS搜索方法
• 4.1.4 HHWS搜索方法
• 4.2 搜索方法性能分析
• 4.3 实验仿真
• 4.3.1 RWSS和RHWS算法仿真
• 4.3.1.1 随机步行传播生成动态服务器组
• 4.3.1.2 RWSS和RHWS的性能
• 4.3.1.3 负载平衡
• 4.3.1.4 抵抗高度节点故障的强壮性
• 4.3.2 HRWS和HHWS算法仿真
• 4.3.2.1 高度步行传播生成动态服务器组
• 4.3.2.2 HRWS和HHWS的性能
• 4.3.2.3 负载平衡
• 4.3.2.4 抵抗高度节点故障的强壮性
• 4.3.3 与其它搜索方法的性能比较
• 4.4 小结
• 第五章 基于社会规则的声望模型
• 5.1 相关工作
• 5.2 基于社会规则的声望模型
• 5.2.1 满意值和不满意值的计算
• 5.2.2 满意率的计算
• 5.2.3 声望模型中的时间因素
• 5.3 声望模型的存储
• 5.4 声望模型的讨论
• 5.5 构造节点的信任值
• 5.6 实验及相关分析
• 5.6.1 简单攻击
• 5.6.2 概率攻击
• 5.6.3 叛变者攻击
• 5.6.4 共谋攻击
• 5.6.5 诋毁攻击
• 5.6.6 陌生者攻击
• 5.6.7 复合攻击
• 5.7 小结
• 第六章 基于社会声望模型的非结构化P2P信任机制
• 6.1 信任模型及相关数据结构
• 6.2 评价记录的存储
• 6.3 信誉搜索算法
• 6.4 服务节点的信任计算及选择
• 6.5 基于信任的服务请求响应
• 6.6 基于信任的拓扑进化
• 6.7 信任机制性能分析
• 6.8 实验仿真
• 6.8.1 攻击方式仿真
• 6.8.1.1 简单攻击
• 6.8.1.2 概率攻击
• 6.8.1.3 共谋攻击
• 6.8.2 抗节点故障能力
• 6.8.3 动态网络仿真
• 6.8.4 基于信任的拓扑进化
• 6.8.5 对Free-Riding现象的抑制
• 6.9 小结
• 第七章 基于非结构化P2P的通告代理网络
• 7.1 相关工作
• 7.2 基于P2P的通告代理集群
• 7.2.1 通告代理集群构造算法
• 7.2.2 通告代理集群生成算法讨论
• 7.3 基于主题的分层技术管理通告代理集群
• 7.3.1 主题层的管理
• 7.3.1.1 创建新主题层
• 7.3.1.2 加入到一个主题层
• 7.3.1.3 进化的主题层
• 7.3.2 主题层内的通告消息传播算法
• 7.3.3 通告消息的发布订阅
• 7.3.3.1 发布通告消息
• 7.3.3.2 注册订阅兴趣
• 7.4 实验
• 7.4.1 通告代理集群生成算法实验
• 7.4.2 通告消息传播算法实验
• 7.4.2.1 通告代理的负载
• 7.4.2.2 TopicLayerBroadcast算法的可靠性
• 7.5 小结
• 结束语
• 参考文献
• 致谢
• 附录A 第五章仿真程序详述
• A.0.1 仿真程序总体结构
• A.0.2 仿真程序中的两个主要类
• A.0.3 部分攻击方式仿真伪代码
• 攻读学位期间发表的学术论文及参加的科研项目