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