用small-world设计无组织p2p系统路由算法（

《用small-world设计无组织p2p系统路由算法（》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、周晋等:用Small-world设计无组织P2P系统的路由算法用Small-world设计无组织P2P系统的路由算法*SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60003004(国家自然科学基金)周晋(1977－),男,河北唐山人,博士生,主要研究领域为P2P搜索算法,信息检索.李衍达(1936－),男,广东南海人,教授,博士导师,主要研究领域为生物信息学,智能信息处理,信号处理.周晋+,李衍达(清华大学自动化系网络信息实验室,北京100084)UsingSmall-worldtoDeviseRo

2、utingAlgorithmofUnstructuredPeer-to-peerSystem*ZHOUJin+,LIYan-Da(WebInformationLaboratory,DepartmentofAutomation,TsinghuaUniversity,Beijing100084,China)+Correspondingauthor:Phn86-10-6277-8137,Fax86-10-6278-1816,E-mail:zhoujin00@mails.tsinghua.edu.cnhttp://webinfo.au.tsinghua.edu.cn/~zhoujinReceiv

3、ed2003-3-25;Accepted2003-10-8ZhouJ,LiYD.UsingSmall-worldtoDeviseRoutingAlgorithmofUnstructuredPeer-to-peerSystem.JournalofSoftware,2003,Abstract:Peer-to-peersystemshaveshownagreatpotentialonfilesharinginrecentyearsandefficientsearchtechniqueshasbecomeacrucialresearchproblem.Mostunstructuredpeer-t

4、o-peersystemslackingcachescheme,withexistingdistributedroutingalgorithms,canonlyrunblindsearch,butnotglobalsearch.Toaddresstheproblem,wepurposeanovelkeyclusteringalgorithm,whichdividesroutingspaceintotwolayers,AUTlayerandHUBlayer.Suchanalgorithmcandoesawell-orderedsearchfromaglobalview.Inordertoi

5、mprovescalability,weutilizetheoreticalresultsfromsmall-world.Inimprovedalgorithm,afewshortcutswithdistantpeerswillbeinsertedintoroutingtableswithsomeprobabilities,andaveragepathlengthwillbereduced.Throughpreliminarysimulation,wedemonstratethatkeyclusteringalgorithmwithshortcutsisefficientandscala

6、ble.Keywords:P2Prouting;clustering;small-world;unstructuredpeer-to-peersystem摘要:由于Peer-to-peer系统在文件共享方面有着巨大的应用前景,Peer-to-peer搜索问题已成为目前学术界的重点研究问题之一.对于缺乏缓存机制的无组织P2P系统,已有的分布式路由算法缺乏全局导航能力,属于无序搜索.为此,本文提出一种Keyclustering算法,将路由空间分HUB和AUT两层,从全局角度进行有序搜索.为提高Keyclustering算法的可扩展性,我们借鉴Small-world领域的研究成果,在路由表中以

7、一定概率插入连接远距离节点的快捷连接,以缩短平均路径长度.初步仿真试验表明,引入快捷连接的Keyclustering算法具有良好的搜索能力和扩展性.关键词:P2P路由;聚类;小世界;无组织Peer-to-peer系统中图法分类号:TP393　　　文献标识码:A周晋等:用Small-world设计无组织P2P系统的路由算法1简介近来,Peer-to-peer系统(简称P2P系统)在文件共享和信息搜索等方面得到了越来越多的应用.P2P系