【作者】 陈欣；

【导师】 傅游；

【作者基本信息】 山东科技大学 ， 计算机应用技术， 2006， 硕士

【摘要】 Peer-to-Peer(P2P)作为以文件共享为初始目的的应用，允许任意终端用户对等体(Peer)间通过Internet完成文件交换。在P2P应用仅有的短短几年发展时间里，它已成为了占用Internet流量的主要应用类型。P2P系统支持大量用户的能力，已经开始显示出技术优势：它能够以较低的成本快速地部署强大的、大规模分布式应用。由于P2P网络的动态性以及可扩展性，在P2P网络中的首要问题是能够有效地搜索到这些资源。 本文简要介绍了P2P的基本概念、P2P的应用、P2P的特性、P2P目前研究方向等。介绍了结构P2P和无结构P2P的搜索技术。在无结构P2P搜索技术中，详细描述了一种无结构P2P的搜索技术——基于连通支配集的搜索技术。 本文分析了基于连通支配集搜索技术的优势和不足，针对其不足，提出了改进的方法。首先，结合图论的知识，提出了改进的连通支配集生成规则。定义了节点的加入规则、节点marker标识修改规则。为了将上述规则应用到P2P网络中，给出了若干定义，包括：节点的加入、支配节点的“共享”从节点、支配节点的“独占”从节点、节点加权连通支配图、节点的退出等。证明了在上述两个规则的作用下，图中的支配节点仍然保持连通性。同时，给出了节点的加入算法和节点修改marker标识算法。其次，提出了改进的基于连通支配集的P2P网络文件查找算法。改进的算法将关键字的词频与节点拥有热门文件和冷门文件的数量相结合，使得查询请求在转发中更有目的性。改进的查找算法采纳了k_随机漫步的思想，并修改了Wu的查找算法中的终止条件，以访问更多的节点。最终的试验数据表明改进的基于连通支配集的P2P模型查找算法，与Wu的查找算法相比，在相同的跳数下，可以访问到较多的节点，并且访问到较多的文件，达到提高查找效率的目的。更多还原

【Abstract】 File sharing among the end client peers through Internet is the initial purpose of peer-to-peer. In the short history of P2P applications, it has become one of the main application types that consume a large fraction of Internet traffic. P2P architecture has begun to show its capability to support massive users, and this capability makes it suitable for rapidly deploying powerful and large-scale distributed applications with low cost. How to search these end client peers in dynamic and scalable P2P architecture efficiently is the first to be solved.The basic concepts about P2P have been introduced, including the applications, the specialties, directions of research and the topology of P2P. The searching technology in P2P networks, structured topology and unstructured topology, has been presented comprehensively. Among these unstructured P2P searching technologies, the dominating set based search scheme is recited, which is proposed by Wu.The predominance and disadvantage of the dominating set based search scheme have been analyzed. To enhance its performance, a modified rule of forming dominating connected set (CDS) based search scheme has been proposed. Firstly, based on graph theory, the rules of forming the connected dominating set have been proposed, including the nodes adding rule and node marker updating rule. Some definitions adapted to P2P networks, such as node adding, sharing slave node, exclusive slave node, CDS graph with node power, and node exiting is presented. The CDS graph is proved to maintain the connection of CDS with the rules. Moreover, the algorithms of node adding and node marker updating are designed properly. Secondly, The searching scheme based on the modified dominating set formation has been designed. The term frequency of key and the number of popular files and that of the rare files provided by nodes are related in the modified searching algorithm The alternative algorithm derives the concept of k-walkers random walk, and modifies the stop condition in order to access more nodes.The computer simulation test indicates that compared with Wu’s dominating set based search scheme, using the improved dominating set based search scheme provided in this thesis, under the sitution with the same hops, more nodes can be accessed and more files can be更多还原