基于节点簇的P2P随机漫步搜索  

Node Cluster-Based Random Walk Search in Peer-to-Peer Network

作　　者：赵堃[1] 牛振东[1] 

机构地区：[1]北京理工大学计算机学院,北京100081

出　　处：《华南理工大学学报（自然科学版）》2010年第7期14-19,共6页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60803050)

摘　　要：以Gnutella为代表的P2P系统通常会呈现复杂的网络结构,为此,文中提出了一种基于节点簇的随机漫步搜索算法.该算法利用节点簇来存储系统中文件的索引,通过将搜索过程限制于节点簇内部来提高搜索性能.基于数学模型的理论分析,文中给出了搜索性能上下界的数学描述.实验结果表明:搜索性能与簇的阈值c密切相关;c的建议值为系统中节点最大度值的一半,与普通随机漫步相比,此时稀有文件的搜索效率至少可以提高250%,文件索引的传输和存储代价可以减少一个数量级;该算法具有索引存储代价非常低、搜索效率高、易于实现和部署的优点.In order to simplify the complex structure of unstructured peer-to-peer （ P2P） networks such as Gnutella,a node cluster-based random walk search algorithm is proposed. In this algorithm,node clusters are used to store file indices,and the search process is constrained in node clusters to improve the search performance. Afterwards,the upper and lower bounds of search performance are formulated based on the theoretical analysis of the mathematical model. Experimental results indicate that the search performance of the proposed algorithm is closely related to the cluster threshold c,and that,at the suggested value of c,namely half of the maximum degree in the system,the success rate of searching rare files increases by at least 250% and the transfer and storage cost decreases by one order of magnitude,as compared with the common random walk algorithm. The proposed algorithm is of the advantages of low storage cost high search efficiency as well as ease realization and deployment.

关 键 词：非结构化P2P网络 复杂网络 随机漫步 簇 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]