分布式生成树中限制搜索半径的定位算法研究

《分布式生成树中限制搜索半径的定位算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第24卷第4期电子测量与仪器学报24No．4·334·JoURNALoFELECTRoNIC伍AsURE伍NTANDlNsTRU匝NT2010年4月D0I：10．3724／SP．J．1l87．2010．00334分布式生成树中限制搜索半径的定位算法研究木王铁军刘恒周明天(电子科技大学计算机科学与技术学院，成都610054)摘要：在分布式生成树(DST)eP，针对限制TTL的DST定位算法不能有效地降低搜索时间和网络带宽使用的问题，提出了一种基于搜索半径限制的定位算法，并给出了确定搜索半径的依据．在资源均匀分布的

2、DST中，满足条件的搜索半径可以确保搜索请求以高概率成功定位到符合条件的资源，减少了网络带宽的使用，缩短了资源定位时间。通过数学分析和实验仿真，说明基于搜索半径限制定位算法的网络带宽使用和搜索时间与网络规模无关，算法的时间复杂度为常数阶，其性能优于限制TTL的DST定位算法。关键词：分布式生成树；对等网络；资源定位；搜索半径中图分类号：TP393．02文献标识码：A国家标准学科分类代码：520．3040Researchonsearchradiuslimitedlocationalgorithmindistrib

3、utedspanningtreeWangTiejunLiuHengZhouMingtian(SchoolofComputerScienceandEngineering，UESTC，Chengdu610054，China)Abstract：Inthedistributedspanningtree(DST)，toresolvetheproblemthattheDSTlocationalgorithmwithTTLlimitedcannotefectivelyreducethesearchingtimeandthen

4、etworkbandwidthusage，weproposealocMional—gorithmbasedonsearchradiusandalsodescribeabasisfordeterminingthesearchradius．IntheDSTwithresourcesuniformlydistributed，thequalifiedresourcescanbesuccessfullylocatedbyusingthealgorithmwithsatisfiedsearchradius，SOthenet

5、workbandwidthusageandsearchingtimeCanbereduced．Throughthemathematicalanalysisandsimulations，theresultsshowthatthenetworkbandwidthusageandsearchingtimeofthelocationalgorithmwithsearchradiuslimitedarenotrelatedwiththenetworksize，thetimecomplexityofwhichisconst

6、antorder,andwhoseper-formanceisbetterthantheDSTalgorithmwithTTLlimited．Keywords：distributedspanningtree；peer-to-peer；resourceslocation；searchradius1引言哈希操作破坏了原有资源Key的特性，使得基于DHT的定位算法不支持范围查询和复杂查询。而在利用传统的Internet，构建基于IP地址的覆盖网非结构化的P2P网络中，如Gnutella、FastTrackJ、络进行分

7、布式的存储、共享和发现资源是对等网络(P2P)的主要应用模式【l】。在P2P网络中，资源的管理Freenet[引，由于系统中保留了资源的原始信息，所以和查找一直是人们关注的热点问题。目前研究较为定位算法可以很好地支持上述查询。根据查询过程广泛的是结构化P2P中基于分布式哈希表(DHT)的中是否依赖系统信息，非结构化P2P网络中定位算定位算法。在Chord[，、CAN[、Pastry[、Tapestry[]法可分为随机搜索和体系搜索两类pJ。其中，随机走网络中，首先对资源和结点的Key值进行哈希操作，／步【加】、

8、概率泛洪¨和Gossip[搜索算法是经典的随然后根据哈希结果将资源放到相应的结点上。由于机定位算法。这些定位算法通过构建概率模型可提本文于2009年l0月收到。基金项目：“十一五”国家科技支撑计划(编号：2006BAH02A0407)资助项目。第4期分布式生成树中限制搜索半径的定位算法研究高搜索l生能，但却无法确保全概率搜索。体系搜索则功率的前提下，其平均搜索时间和网络带宽使用性是根据