P2P网络系统搜索算法与研究.pdf

国内图书分类号:
国际图书分类号:



工学硕士学位论文

P2P 网络系统搜索算法研究





硕士研究生: 朱超
导师:廖明宏教授
申请学位:工学硕士
学科、专业: 计算机科学与技术
所在单位:计算机科学与技术学院
答辩日期:2007 年 7 月
授予学位单位: 哈尔滨工业大学
Classified Index:
.:



A Dissertation for the Degree of M. Eng.


RESEARCH OF SEARCH
ALGORITHMS FOR WORK
SYSTEMS


Candidate: Zhu Chao
Supervisor: Prof. Liao Minghong
Academic Degree Applied for: Master of Engineering
Specialty: Computer Science and Technology
Affiliation: School puter Science and
Technology
Date of Defence: July, 2007
University: Harbin Institute of Technology
哈尔滨工业大学工学硕士学位论文
摘要
对等网络(Peer-to-Peer,简称 P2P)是一种新兴的复杂网络。随着 P2P 网
络的广泛应用,人们发现即使每个用户提供少量文件,整个用户群所共享的
文件数也是非常庞大的。要想充分利用这些资源,首先要能够快速准确地找
到它们。因此,P2P 网络搜索算法研究成为了一个重要的研究课题。
P2P 网络搜索技术涉及到图论、统计物理学、网络测量、数学建模及算
法设计等多个领域。如何利用复杂网络的最新研究成果对 P2P 网络模型进
行优化与改进,以达到提高搜索效率和精度的目的以及如何基于现有 P2P
网络模型设计出更加有效的局部搜索策略等已成为 P2P 网络搜索技术研究
中的重要内容。
P2P 搜索算法主要分为结构化搜索算法和无结构搜索算法两大类。前者
虽然平均查询跳数较低,但存在系统难于维护、不支持复杂查询等缺点;而
后者简单灵活且鲁棒性好,但其平均查询跳数大,系统可扩展性差。
本文研究如何克服以上这些不足,使搜索算法的各个性能指标都能达到
一个良好的水平。首先总结了现存的主要几种算法和其优缺点,接着介绍了
小世界和无标度这两种复杂网络的重要性质,然后提出了两种新的无结构搜
索算法——扩散式搜索算法和推荐式搜索算法,前者基于复杂网络的无标度
和小世界性质,遵循聚集度大优先的原则,后者基于复杂网络的自相似小世
界性质,先查找到目的簇的祖先,再进行簇内搜索,最后经实验表明,该算
法在许多方面相比原有的算法具有更好的性能。

关键词 P2P 网络;无标度;小世界;扩散式搜索;推荐式搜索
- I -
哈尔滨工业大学工学硕士学位论文
Abstract
Peer-to-Peer(P2P) network is a new kind work. It is found
that even if each individual provides only a few files, enormous files can be
shared by the whole group of users. In order to use these abundant resources, the
key problem is to find them effectively. Therefore, the issue of search in P2P
networks has e an important topic.
The search in works is related to many fields, such as graph theory,
statistical physics, network measuring, mathematics modeling, and algorithm
design. Two main aspects of search in works have been studied in recent
years: one is how to optimize and improve the work m