资源密度对P2P搜索算法的影响  

Impact of Resource Density on Search Algorithms in Peer-to-Peer Networks

作　　者：田舟贤[1,2] 顾乃杰[1,2] 何颂颂[1,2] 李恺[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术系,安徽合肥230027 [2]安徽省计算与通信软件重点实验室,安徽合肥230027

出　　处：《计算机仿真》2009年第5期150-153,157,共5页Computer Simulation

基　　金：国家自然科学基金重点项目(60533020);教育部博士点基金部分支持(20060358011)

摘　　要：在无结构P2P网络中,资源密度影响搜索算法的搜索时间、通信开销以及搜索策略的设计与选取。在资源随机分布的假设下分析了资源密度同搜索性能的关系,给出了随机漫步和洪泛搜索的平均搜索时间和通信开销下界,并分析得出结论:增加资源备份或者降低节点被重复搜索的概率能显著提升稀有资源的搜索性能,但较难提升稠密资源的搜索性能。基于上述理论分析,提出了一个随机漫步改进算法以验证结论。仿真实验表明,实验数据同理论分析结果符合。Resource density has impact on the search time, communication cost and design of search algorithms in unstructured P2P networks. This paper gives the lower bound of search time and communication cost of random walk and flooding method, given that the resource is uniformly distributed in the network. The conclusion shows that increasing resource copies or reducing nodes＇ repeated visiting times can improve search performance for rare resource, but they are not efficient for popular resource. The paper proposes a search algorithm based on analysis. Simulation results are all in consistence with the conclusion.

关 键 词：资源密度 随机漫步 洪泛搜索 无结构对等网络 

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