p2p网络系统搜索算法的研究.docx

国内图书分类号:::朱超导师:廖明宏教授申请学位:工学硕士学科、专业:计算机科学与技术所在单位:计算机科学与技术学院答辩日期:2007年7月授予学位单位:哈尔滨工业大学ClassifiedIndex:.::Supervisor:AcademicDegreeAppliedfor:Specialty:Affiliation:DateofDefence:University:,2007HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要对等网络(Peer-to-Peer,简称P2P)是一种新兴的复杂网络。随着P2P网络的广泛应用,人们发现即使每个用户提供少量文件,整个用户群所共享的文件数也是非常庞大的。要想充分利用这些资源,首先要能够快速准确地找到它们。因此,P2P网络搜索算法研究成为了一个重要的研究课题。P2P网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何利用复杂网络的最新研究成果对P2P网络模型进行优化与改进,以达到提高搜索效率和精度的目的以及如何基于现有P2P网络模型设计出更加有效的局部搜索策略等已成为P2P网络搜索技术研究中的重要内容。P2P搜索算法主要分为结构化搜索算法和无结构搜索算法两大类。前者虽然平均查询跳数较低,但存在系统难于维护、不支持复杂查询等缺点;而后者简单灵活且鲁棒性好,但其平均查询跳数大,系统可扩展性差。本文研究如何克服以上这些不足,使搜索算法的各个性能指标都能达到一个良好的水平。首先总结了现存的主要几种算法和其优缺点,接着介绍了小世界和无标度这两种复杂网络的重要性质,然后提出了两种新的无结构搜索算法——扩散式搜索算法和推荐式搜索算法,前者基于复杂网络的无标度和小世界性质,遵循聚集度大优先的原则,后者基于复杂网络的自相似小世界性质,先查找到目的簇的祖先,再进行簇内搜索,最后经实验表明,该算法在许多方面相比原有的算法具有更好的性能。关键词P2P网络;无标度;小世界;扩散式搜索;推荐式搜索-I-哈尔滨工业大学工学硕士学位论文AbstractPeer-to-Peer(,,,,suchasgraphtheory,workmeasuring,mathematicsmodeling,:workmodels,works,uracy,:,,unstructuredsearchalgorithmsaresimple,flexibleandveryrobust,buttheiraveragequeryhopsismuchlarger,,,weconcludedtheup-to-,weintroducedsmall-worldandscale-free,:-fr