非结构化P2P网络环境下资源发现和搜索方法研究

摘要

网络技术的进步和个人计算机能力的增强，使得传统的客户机／服务器模式正在向对等(Peer-to-Peer，P2P)模式发展。对某些应用来说，分散的非结构化的P2P网络(如Gnutella)是非常吸引人的,因为它们不需要中央目录，也不需要对网络拓扑和数据放置进行准确的控制。一方面，Gnutella中采用的基于洪泛(Flooding)的搜索算法可以快速地覆盖网络，得到搜索结果的最大化；另一方面，也意味着每次查询会产生大量的网络流量，使系统负载过重。因此，在类似Gnutella的分散的非结构化P2P网络中，如何降低时间开销，提高搜索效率，是解决其扩展性问题的关键。 为了避免由洪泛搜索引起的大量网络流量问题，人们提出了多种基于统计的搜索方法，其思想是节点根据某些统计信息和启发式算法，选择部分邻居节点进行查询的转发，而不是像洪泛那样将查询发送到所有的邻居节点。因为查询只发送到部分的节点，缩小了查询范围，所以出现了局部覆盖问题。基于连通支配集的广播算法(BCDS)是在节点的两跳范围拓扑中找到一个最小连通支配集，集合中的节点作为转发查询的节点，不属于集合的节点则只接收消息，从而减少了查询消息的数量，又保证了消息的覆盖范围。本文对BCDS算法进行改进，选择长链路邻居作为转发节点，可以使搜索覆盖到别的网段，而短链路邻居作为接收节点，减少了计算转发节点集合和接收节点集合的时间，而且不用维持局部两跳拓扑的信息。算法分析和实验结果表明改进的BCDS算法比洪泛性能更优越。蚁群算法是一种新颖的进化类系统优化方法。在P2P网络中，搜索就是查询消息包在网络中传播，寻找拥有请求资源的节点，就像是蚂蚁在寻找食物源一样。因此，本文将蚁群算法的思想引入P2P网络的搜索中，查询消息包看作是蚂蚁，搜索的目标视为食物，存在搜索目标的节点就是食物源。当源节点发出搜索请求时，就相当于派出蚂蚁到网络中寻找食物。根据蚂蚁觅食行为的特性，通过蚂蚁释放信息素的正反馈机制来指导搜索前进的方向，从而尽快地得到更好的搜索输出。

目录

文摘

英文文摘

第一章绪论

第二章P2P网络的拓扑分类及搜索方法

第三章一种改进的基于连通支配集的广播算法

第四章一种基于蚁群算法的非结构化P2P网络搜索算法

第五章总结与展望

参考文献

致谢

在读期间参加的科研项目

在读期间发表录用的学术论文