《p2p网络系统搜索算法的研究》由会员分享，可在线阅读，更多相关《p2p网络系统搜索算法的研究（57页珍藏版）》请在金锄头文库上搜索。
1、国内图书分类号：TP393.4国际图书分类号：681.324工学硕士学位论文P2P 网络系统搜索算法研究硕士研究生：朱超导师：廖明宏教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：计算机科学与技术学院答辩日期： 2007 年 7 月授予学位单位：哈尔滨工业大学Classified Index：TP393.4U.D.C.: 681.324A Dissertation for the Degree of M. Eng.RESEARCH OF SEARCHALGORITHMS FOR P2P NETWORKSYSTEMSCandidate：Supervisor：Academic Degr
2、ee Applied for：Specialty：Affiliation：Date of Defence：University：Zhu ChaoProf. Liao MinghongMaster of EngineeringComputer Science and TechnologySchool of Computer Science andTechnologyJuly, 2007Harbin Institute of Technology哈尔滨工业大学工学硕士学位论文摘要对等网络(Peer-to-Peer，简称 P2P)是一种新兴的复杂网络。随着 P2P网络的广泛应用，人们发现即使每个用户
3、提供少量文件，整个用户群所共享的文件数也是非常庞大的。要想充分利用这些资源，首先要能够快速准确地找到它们。因此，P2P网络搜索算法研究成为了一个重要的研究课题。P2P网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何利用复杂网络的最新研究成果对 P2P网络模型进行优化与改进，以达到提高搜索效率和精度的目的以及如何基于现有 P2P网络模型设计出更加有效的局部搜索策略等已成为 P2P网络搜索技术研究中的重要内容。P2P搜索算法主要分为结构化搜索算法和无结构搜索算法两大类。前者虽然平均查询跳数较低，但存在系统难于维护、不支持复杂查询等缺点；而后者简单灵活且鲁棒性好，但其
4、平均查询跳数大，系统可扩展性差。本文研究如何克服以上这些不足，使搜索算法的各个性能指标都能达到一个良好的水平。首先总结了现存的主要几种算法和其优缺点，接着介绍了小世界和无标度这两种复杂网络的重要性质，然后提出了两种新的无结构搜索算法扩散式搜索算法和推荐式搜索算法，前者基于复杂网络的无标度和小世界性质，遵循聚集度大优先的原则，后者基于复杂网络的自相似小世界性质，先查找到目的簇的祖先，再进行簇内搜索，最后经实验表明，该算法在许多方面相比原有的算法具有更好的性能。关键词P2P网络；无标度；小世界；扩散式搜索；推荐式搜索-I-哈尔滨工业大学工学硕士学位论文AbstractPeer-to-Peer(P2
5、P) network is a new kind of complex network. It is foundthat even if each individual provides only a few files, enormous files can beshared by the whole group of users. In order to use these abundant resources, thekey problem is to find them effectively. Therefore, the issue of search in P2Pnetworks
6、 has become an important topic.The search in P2P networks is related to many fields, such as graph theory,statistical physics, network measuring, mathematics modeling, and algorithmdesign. Two main aspects of search in P2P networks have been studied in recentyears: one is how to optimize and improve
7、 the P2P network models, according tothe known results of the complex networks, to obtain high search efficiency andaccuracy, the other is how to design more effective local search strategies basedon current P2P network models.There are two kinds of P2P search algorithms: structured search algorithm
8、sand unstructured search algorithms. Although structured search algorithms canguarantee small average query hops, there are shortcomings such as difficultmaintainability and nonsupport for complex search in these systems. On the otherhand, unstructured search algorithms are simple, flexible and very
9、 robust, buttheir average query hops is much larger, and their scalability is much unfavorable.This paper studies how to overcome these disadvantages, in order to get ahigh level of each performance target. First, we concluded the up-to-date P2Psearch algorithms and their excellence and shortcoming.
10、 Second, we introducedsmall-world and scale-free, which are two important characters of complexnetworks. Then we provided two new unstructured search algorithms: diffusesearch algorithm and recommend search algorithm. The former based on scale-free and small-world characters of complex networks, and
11、 follows the principleof high degree first. The latter based on self-similar small-world character ofcomplex networks, and after the ancestor of the destination cluster is found, thealgorithm will search the nodes in the cluster. Experimental results indicated thatour algorithms excel other up-to-date P2P searching algorithms in many aspects.- II -哈尔滨工业大学工学硕士学位论文KeywordsP2P network; scale-free; small-world; diffuse search; recommendsearch- III -哈尔滨工业大学工学硕士学位论文目录摘要 .IAbstract . II第 1章绪论 . 11.1课题背景 . 11.2研究目的和意义 . 41.3国内外P2P网络系统综述 . 51.3.1主要研究机构 . 51.3.2 P2P网络系统研究现状 .
