面向服务发现应用的非结构化覆盖网络建模与分析

论文摘要

互联网的快速发展促进了软件的网络化趋势,使得服务逐渐成为软件的核心和形式。Web Service是网络化软件的重要组成部分,服务发现的目标是准确、高效地在互联网环境中搜索Web Service。由于集中式服务发现系统存在单点故障和可扩展性差等问题,基于非结构化覆盖网络的分布式服务发现系统得到了广泛关注。此前的研究主要关注系统架构和Web Service描述,作为系统运行基础的非结构化覆盖网络却未得到充分的研究。本文从实测拓扑分析、网络建模和搜索性能优化等角度对面向服务发现应用的非结构化覆盖网络进行研究。首先,本文研究非结构化覆盖网络具有怎样的拓扑特征,并基于特征分析建立网络模型。Gnutella是一个典型的非结构化覆盖网络,本论文通过它的实测拓扑数据进行分析,验证了非结构化覆盖网络的节点度分布重尾特征、节点度分布波峰现象和小世界特征,发现了非结构化覆盖网络的弱Rich-club特征。通过对拓扑特征内在机制的分析,建立了面向非结构化覆盖网络的GFCC模型。其次,本文证实了GFCC网络模型的有效性,并揭示了面向服务发现应用的非结构化覆盖网络中节点行为与拓扑结构之间的关系。首先根据服务发现应用的特点确定GFCC模型的适应度函数,然后通过理论推导和仿真实验,对GFCC模型的节点度分布、Rich-club系数、聚类系数和平均路径长度进行分析。分析结果表明GFCC模型可重现实际网络的拓扑特征,分析还揭示了节点缓存行为、邻居数约束机制和节点聚类行为对网络拓扑结构的影响。最后,本文基于GFCC模型对Web Service搜索性能进行了分析和优化,并将研究结论应用于工程实践,设计了分布式服务发现系统SOONET。通过比较分析泛洪和随机游走两种搜索算法在GFCC网络模型中的搜索成功率、搜索延时和搜索开销等性能指标,给出了分布式服务发现系统的建议搜索算法:k-Walkers;并通过约束优化方法,给出了Web Service描述信息的副本数最优分布。以上述研究结论为理论指导而设计的SOONET是一个基于Web Service的分布式服务发现系统,采用基于令牌的搜索消息路由策略实现k-Walkers,并采用沿搜索路径缓存Web Service描述信息的策略使系统的副本数分布达到最优。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景和研究意义
• 1.1.1 应用背景
• 1.1.2 理论背景
• 1.1.3 项目背景
• 1.1.4 研究意义
• 1.2 相关研究综述
• 1.2.1 服务发现系统的研究现状
• 1.2.2 非结构化覆盖网络模型的研究现状
• 1.3 论文的研究内容
• 1.4 论文的主要贡献
• 1.5 论文的结构安排
• 第2章 非结构化覆盖网络拓扑的实测数据分析
• 2.1 数据来源与分析方法
• 2.1.1 Gnutella 网络拓扑实测数据的来源
• 2.1.2 分析方法
• 2.2 拓扑特征分析的研究背景
• 2.2.1 非结构化覆盖网络的数学描述方法
• 2.2.2 经典复杂网络模型
• 2.3 Gnutella 网络的节点度分布特征
• 2.3.1 节点度分布
• 2.3.2 累积节点度分布
• 2.4 Gnutella 网络的 Rich-club 特征
• 2.5 Gnutella 网络的小世界特征
• 2.5.1 聚类系数
• 2.5.2 平均路径长度
• 2.6 本章小结
• 第3章 非结构化覆盖网络建模
• 3.1 节点优先依附机制建模
• 3.1.1 基于节点度的优先依附模型之局限性（一）
• 3.1.2 基于节点度的优先依附模型之局限性（二）
• 3.1.3 基于适应度的优先依附模型
• 3.2 邻居数约束的节点度增长机制建模
• 3.3 小世界网络建模
• 3.3.1 聚类系数可调网络模型的相关研究
• 3.3.2 节点聚类行为模型
• 3.4 非结构化覆盖网络模型－GFCC 模型
• 3.4.1 GFCC 网络模型算法
• 3.4.2 GFCC 网络模型的参数分析与退化模型
• 3.5 本章小结
• 第4章 GFCC 网络模型的结构特征分析与仿真实验
• 4.1 服务发现应用的特点与GFCC 模型参数的选择
• 4.1.1 适应度函数
• 4.1.2 初始适应度分布
• 4.2 基本结构特征分析
• 4.3 GF 网络的累积节点度分布分析
• 4.3.1 累积节点度分布的解析式
• 4.3.2 初始适应度满足均匀分布时的情况
• 4.3.3 初始适应度满足幂率分布时的情况
• 4.3.4 节点行为对网络累积节点度分布的影响
• 4.4 GFC 网络的累积节点度分布分析
• 4.5 Rich-club 系数分析
• 4.6 聚类系数分析
• 4.7 平均路径长度分析
• 4.8 网络连通性分析
• 4.9 本章小结
• 第5章 Web Service 搜索性能分析与优化
• 5.1 Web Service 搜索性能研究框架
• 5.1.1 拓扑模型
• 5.1.2 搜索算法
• 5.1.3 Web Service 搜索率分布
• 5.1.4 Web Service 描述信息的副本数分布
• 5.1.5 搜索性能评价指标
• 5.2 泛洪的性能分析
• 5.2.1 搜索成功率
• 5.2.2 搜索开销
• 5.3 随机游走的性能分析
• 5.4 分布式服务发现系统的建议搜索算法
• 5.5 Web Service 描述信息的最优副本数分布
• 5.6 本章小结
• 第6章 分布式服务发现系统 SOONET 设计与实现
• 6.1 体系结构设计
• 6.2 并发随机游走搜索算法
• 6.3 沿搜索路径缓存Web Service 描述信息的复制策略
• 6.4 节点架构设计
• 6.5 性能实验
• 6.6 本章小结
• 第7章 结论和展望
• 7.1 结论
• 7.2 下一步研究展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果