（计算机应用技术专业论文）结构化p2p覆盖网设计与搜索机制研究.pdf

结构化p 2 p 覆盖网设计与搜索机制研究 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“ ) 本人郑重声明：此处所提交的博士口硕士回论文结构化p 2 p 覆盖网 设计与搜索机制研究，是本人在导师指导下，在曲阜师范大学攻读博士口 硕士陛乎位期间独立进行研究工作所取得的成果。论文中除注明部分外不包 含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中已明确的方式注明。本声明的算法律结果将完全由本人 承担。 作者签名： 夸狄日期：知仞占1 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“) 结构化p 2 p 覆盖网设计与搜索机制研究系本人在曲阜师范大学攻读博 士口硕士日学位期间，在导师指导下完成的博士口硕士日学位论文。本 论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的 名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同 意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和 借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可 以公开发表论文的全部或部分内容。 作者签名：杏次 剔磴名堋 日期：驯及多工 日期：沙c 口，二、； 结构化p 2 p 覆盖网设计与搜索机制研究 摘要 p 2 p 覆盖网( p e e r - t o p e e ro v e r l a yn e t w o r k s ) 是包含能够自组织的节点的分布式系统， 目的在于共享资源，比如c p u 的能力、带宽和存储能力。在不要求一个全局的集中服务器 的支持或者调解的同时，能够适应节点失效和不断变换的节点数目，系统保持可以接受的 连接能力和性能。基于d h t 的结构化p 2 p 覆盖网是p 2 p 覆盖网的重要组成部分，并且因 为具有路由高效性、鲁棒性、可扩展性、负载均衡及数据位置的确定性等优点而成为研究 热点。 本文主要研究了结构化p 2 p 覆盖网的设计与搜索机制，共分为五章。第一章简要介绍 p 2 p 的相关概念及搜索方法，指出了论文的结构和主要创新点。 第二章提出一个基于c y c l o i d 与折叠立方体的常数度结构化覆盖网f c y c l o i d ，它用折 叠立方体中补边的概念优化了c y c l o i d 中的部分查询。在f c y c l o i d 覆盖网中，节点的“度 ( 即连接数或邻居数) 为固定数值，不随着网络规模的变化而变化。这个特征保证了在网 络规模不断增大时，覆盖网仍能保持较少的维护开销。在节点数为n = ( d + 1 ) 2 d 的f c y c l o i d 系统中，每个节点只需要维护o ( 1 ) 个邻居，每次查询只要o ( d ) 步。同时，通过仿真验证了 f c y c l o i d 搜索效率的提高，并分析了相关性能。 第三章设计层次化的b g k r 覆盖网，它将查询请求限定在特定的区域内，从而提高查 询效率。b g k r 以广义k a u t z 有向图和环作为拓扑结构，使得每一次新节点的加入会导致 网络中部分节点间的连接关系改变。因此，层次化的b g k r 覆盖网以k a u t z 图和环为基本 结构，并基于一个特定的本体将其分层。通过仿真验证了网络的查询效率及负载分布等性 能。 第四章对m c h o r d 中的相近搜索机制进行研究。相近搜索在很多领域都有广泛应用， 从数据库的角度上讲，相近搜索基于逐渐的而非精确的相关性。对象间的距离用于确定查 询对象和数据库中将被搜索的存储对象间的近似性、相近性或者非相近性。一个相近查询 通过一个查询对象和一个关于界定与该对象相似性的限制条件来定义。区间查询和k 最近 邻居查询是相近搜索的两种基本类型。m c h o r d 使用度量空间及一个保持顺序的变换函数， 在c h o r d 上实现了上述两种查询。在这一部分，针对m c h o r d 中上述两种查询算法中的缺 点，分别提出了改进方案。 第五章给出总结，并指出了下一步的研究工作。 关键词：p e e r - t o p e e r ；结构化p 2 p ；常数度；层次化：相近搜索；m c h o r d 结构化p 2 p 覆盖网设计与搜索机制研究 a b s t r a c t p e e r - t o p e e r ( p 2 p ) o v e r l a yn e t w o r k sa r ed i s t r i b u t e ds y s t e m sw h i c hc o n t a i ns e l f - o r g a n i z e d n o d e st os h a r er e s o u r c e s ，s u c ha sc p u ，b a n d w i d t ha n ds t o r a g e t h e yc a na d a p tt on o d e s f a i l u r e ， a c c o m m o d a t ec h a n g i n gn u m b e ro fn o d e s ，a n dm a i n t a i na c c e p t a b l ec o n n e c t i v i t ya n dp e r f o r m a n c e w i t h o u tt h es u p p o r to ri n t e r m e d i a t i o no fg l o b a lc e n t r a ls e r v e r s s t r u c t u r e dp 2 po v e r l a yn e t w o r k s b a s e do nd i s t r i b u t e dh a s ht a b l ea r es i g n i f i c a n tp a r to fp 2 po v e r l a yn e t w o r k s a n dt h e yb e c o m e t h er e s e a r c hf o c u sf o rt h e i ra d v a n t a g e so fe f f e c t i v er o u t i n g ，r o b u s t , s c a l a b i l i t y , l o a db a l a n c ea n d d e t e r m i n a c yo f d a t al o c a t i o n t h et h e s i sm a i n l ys t u d i e st h ed e s i g na n ds e a r c hm e c h a n i s m so fs t r u c t u r e dp 2 po v e r l a y n e t w o r k s ，a n di s d i v i d e di n t of i v e c h a p t e r s i nt h e f i r s tc h a p t e r , w eb r i e f l yi n t r o d u c et h e c o r r e s p o n d i n gc o n c e p t sa n ds e a r c hm e t h o d so fp 2 p , a n di n d i c a t et h e s t r u c t u r ea n dm a i n i n n o v a t i v ep o i n t so ft h et h e s i s i nt h es e c o n dc h a p t e r , w ep r o p o s eas t r u c t u r e dp 2 po v e r l a yn e t w o r k 、析t l lc o n s t a n td e g r e e b a s e do nc y c l o i da n df o l d e dh y p e r c u b e ，n a m e l yf c y c l o i d i te m p l o y st h ec o n c e p to f c o m p l e m e n t a r ye d g e si nf o l d e dh y p e r c u b et oo p t i m i z es o m es e a r c h e s 试c y c l o i d i nf c y c l o i d , n o d e s d e g r e e s ( a l s ok n o w na st h en u m b e r so fl i n k so rn e i g h b o r s ) a r ec o n s t a n t sa n dd o n tc h a n g e w i t ht h ec h a n g eo ft h es i z eo ft h en e t w o r k a n dt h i sf e a t u r eg u a r a n t e e st h a tt h eo v e r l a yn e t w o r k c a nk e 印l e s sm a i n t e n a n c ec o s t sw h i l et h es i z eo ft h en e t w o r ki sc o n t i n u o u s l yg r o w i n g i n f c y c l o i d 、 r i t l ln = ( d + 1 ) 2 dn o d e s ，e a c hn o d eo n l yh a st ok e e po ( 1 ) n e i g h b o r sa n de a c hl o o k u p j u s tn e e d so ( d ) s t e p s a tt h es a m et i m e ，t h ei m p r o v e m e n to fs e a r c he f f i c i e n c yo ff c y c l o i dh a s b e e np r o v e na n dc o r r e s p o n d i n gp e r f o r m a n c e sa r ea n a l y z e db yt h es i m u l a t i o n i nt h et i l i r dc h a p t e r , w ed e s i g nah i e r a r c h i c a lb g k ro v e r l a yn e t w o r k i tl i m i t st h eq u e r y r e q u e s t si nas p e c i f i ca r e a , a n de n h a n c e ss e a r c he f f i c i e n c y b g k ru s e dg e n e r a l i z e d k a u t g d i g r a p ha n dr i n ga si t st o p o l o g yw h i c hm a d ee a c hj o i n i n go fa n e wn o d el e a dt os o m ec h a n g e si n t h ec o n n e c t i o nr e l a t i o n s h i pb e t w e e np a r t so fn o d e s h e n c e ，t h eh i e r a r c h i c a lb g k ro v e r l a y n e t w o r kt a k e sk a u t zd i g r a p ha n dr i n ga si t sb a s i cs t r u c t u r ea n ds t r a t i f i e sb g k rb a s e do na s p e c i f i co n t o l o g y p e r f o r m a n c e so fl o o k u pe f f i c i e n c ya n dl o a dd i s t r i b u t i o na r ev e r i f i e db yt h e s i m u l a t i o n i nc h a p t e r4 ，w es t u d yt h em e c h a n i s mo fs i m i l a r i t ys e a r c hi nm c h o r d s i m i l a r i t ys e a r c h h a sb e e nw i d e l yu s e di nm a n yf i e l d s f o rd a t a b a s e ，s i m i l a r i t ys e a r c hi sb a s e d0 1 1g r a d u a lr a t h e r t h a ne x a c tr e l e v a n c e ad i s t a n c eb e t w e e no b j e c t si su s e dt oq u a n t i f yt h ep r o x i m i t y , s i m i l a r i t yo r d i s s i m i l a r i t yo f aq u e r yo b j e c tv e r s u st h eo b j e c t ss t o r e di i lad a t a b a s et ob es e a r c h e d as i m i l a r i t y n 结构化p 2 p 覆盖网设计与搜索机制研究 q u e r yi sd e f i n e db yaq u e r yo b j e c ta n dac o n s t r a i n to nt h ep r o x i m i t yr e q u i r e df o ra no b j e c tt ob e i i lm er e s u l ts e t r a n g eq u e r ya n dk - n e a r e s tn e i g h b o rq u e r ya r et w ob a s i ct y p e so ft h es i m i l a r i t y q u e r i e s m - c h o r da d o p t e dm e t r i cs p a c e sa n da no r d e r - p r e s e r v i n gf u n c t i o nt or e a l i z et h e s et w o k i n d so fq u e r i e si nc h o r d i nt h i sp a r t ，c o n s i d e r i n gd i s a d v a n t a g e so fa b o v et w oq u e r ya l g o r i t h m s ， i m p r o v e m e n tp r o p o s a l sa r ep u tf o r w a r d i nc h a p t e r5 ，t h ec o n c l u s i o ni sg i v e na n dt h ef u t u r ew o r ki sp o i n t e do u t k e yw o r d s ：p e e r - t o - p e e r ；s t r u c t u r e dp 2 p ；c o n s t a n td e g r e e ；h i e r a r c h y ；s i m i l a r i t y s e a r c h ；m - c h o r d i i i 结构化p 2 p 覆盖网设计与搜索机制研究 目录 第一章绪论l 1 1p 2 p 概j 2 登1 1 1 1p 2 p 定义、优点及其应用1 1 1 2p 2 p 的分类与特点1 1 2p 2 p 中的搜索3 1 2 1 搜索方法的分类3 1 2 2 几种典型的搜索方法4 1 3 论文结构与主要创新点6 第二章基于c y c l o i d 和折叠立方体的常数度结构化p 2 p 覆盖网7 2 1 引言7 2 2 基本结构7 2 2 1f q d 和键值分配8 2 2 2 路由算法1 l 2 2 3 动态维护l l 2 3 仿真与分析：1 3 2 3 1 数据查询效率1 3 2 3 2 查询负载1 5 2 3 3 节点离开1 6 第三章层次化b g k r 覆盖网1 7 3 1 引言l7 3 2 层次化b g k r 覆盖网。1 8 3 2 1k a u t z 有向图18 3 2 2b g k r 及层次化b g k r 网络的基本结构18 3 3 资源管理与资源定位2 0 3 3 1 资源管理2 0 3 3 2 资源定位2 l 3 4 路由方法2 2 3 4 1 路由策略与分析2 2 3 4 2 节点间的路由操作2 2 3 5 动态维护。2 5 3 5 1 节点加入2 5 3 5 2 节点离开2 5 3 6 仿真与分析2 7 3 6 1 数据查询效率。2 7 3 6 2 负载分布2 8 3 6 3 路由表的规模2 9 3 6 4 节点的加入过程3 0 w 结构化p 2 p 覆盖网设计与搜索机制研究 第四章m c h o r d 中的相近搜索机制31 4 1 弓i 言3l 4 2 背景知识31 4 2 1 度量空间3 l 4 2 2i d i s t a n e e 方法3 2 4 2 3 支点选择3 3 4 2 4 变换函数3 3 4 3 区间查询算法的改进与分析3 4 4 3 1 存在的问题及解决方案3 4 4 3 2 改进后的区间查询算法3 5 4 3 3 算法分析j 3 5 4 4k 最近邻居查询算法的改进与分析3 5 4 4 1 存在的问题及解决方案。3 5 4 4 2 改进后的k 最近邻居查询算法。3 6 4 4 3 算法分析3 7 第五章总结与展望3 8 【参考文献】3 9 在校期间发表的学术论文4 3 致谢j 4 4 v 结构化p 2 p 覆盖网设计与搜索机制研究 第一章绪论 1 1p 2 p 概述 1 1 1p 2 p 定义、优点及其应用 自计算机网络产生以来，其管理和控制就有两种不同的方式：集中式和分布式。集中 式系统中的节点是分层次的，处于较高层次的节点在系统中占主导地位，管理其它下层节 点之间的信息交换，数目比下层节点数要少，因此它们的工作繁重，容易成为网络的瓶颈。 但由于这种模式开发了网络节点的异质性，这种模式的典型代表客户服务器模式在 i n t e m e t 上广泛应用。分布式系统中的节点在功能上是平等的，节点间信息的交换是平等、 自由的，因而扩展性好，缺点在于缺乏对整个系统的有效控制。 p 2 p 覆盖网是分布式系统与计算机网络结合的产物，体现了信息交换的边缘化。p 2 p 网络的核心机制是在应用层建立逻辑上的覆盖网络，封装传输层，互联网络层和网络接口 层的细节，将应用功能部署到边缘节点上而不需要更改现存的网络基础设施。它有很多优 点，主要体现于以下五点：( 1 ) p 2 p 覆盖网提高了网络效率，任何两个节点之间交换信息 不需要经过一个固定的服务器；( 2 ) p 2 p 覆盖网有非常高的可扩展性，即当网络规模扩大 时，每一个节点承担的负载不会增加很多且不需要增加额外设备；( 3 ) p 2 p 覆盖网开发了 网络节点的潜力，数据分散存储在所有节点上，计算任务由各个节点分布、协同完成；( 4 ) p 2 p 覆盖网有良好的容错性，这点通常由冗余方法和周期性检测的机制来保证；( 5 ) p 2 p 覆盖网充分利用了网络带宽，节点间交换信息的过程不受其它节点的控制与影响，传输速 率通常只取决于网络带宽【l 】。 覆盖网提供了很多流行应用的平台，包括文件共享系统，多媒体传输软件，实时通信 软件，它还提供了协同工作、分布式计算、p 2 p 搜索引擎等功能。文件共享是p 2 p 应用的 重点和主流，最具代表性的p 2 p 文件共享系统如下：n a p s t e r 2 ，b i t t o r r e n t 3 ，c j n u t e l l a 4 ， k a z a a 5 ，e d o n k e y 6 e m u l e 7 ，f r e e n e t 8 和m a z e 9 。代表性的p 2 p 多媒体传输软件有： s k y p e 1 0 ，v e e r c a s t 1 1 ，a n y s e e 1 2 和m e r e o r a 1 3 。常见的p 2 p 实时通信软件有：m s n m e s s e n g e r ，i c q ，g 0 0 9 l et a l k 等。c f s 1 4 ，p a s t 1 5 及o c e a n s t o r e 1 6 是典型的p 2 p 分 布式数据存取系统。m i n e r v a 1 7 贝t j 是基于p 2 p 的w e b 搜索原型系统，具体的基于p 2 p 的w e b 搜索技术见文献【1 8 】。 1 1 2p 2 p 的分类与特点 【1 9 】： 当前主要有三种不同的p 2 p 体系结构：集中式的、分布式无结构的和分布式结构化的 一 结构化p 2 p 覆盖网设计与搜索机制研究 ( 1 ) 集中式p 2 p 系统保留了c s 模式中的服务器，节点查询信息时必须先与服务器 建立连接，不过此时服务器不再负责文件的传送。当服务器给查询发起者返回查询成功的 消息时，该节点不经过服务器与数据拥有者直接进行数据传送。此种结构的典型代表是于 1 9 9 9 年推出的第一个p 2 p 系统n a p s t e r 。 ( 2 ) 无结构的p 2 p 系统在i n t e r n e t 中广泛应用。它们采用基于洪泛的搜索机制使得网 络难以扩展，扩展环、随机走、偏向的随机走、有向的洪泛及r 跳复制等路由方法被提出 以缓解这一问题。另外，一些无结构的p 2 p 系统利用节点的异质性进行分层以改善系统性 能。此种结构的代表有g n u t e l l a ，c m u t e l l a 0 6 ，f r e e n e t 和k a z a a 。 ( 3 ) 结构化的p 2 p 系统是为了克服无结构的p 2 p 系统中数据定位效率低的问题而被 提出的。它们的最大特点在于有一个严格的覆盖网拓扑结构。以c a n 2 0 为例，c a n 的多 维空间被动态分配给网络节点，每个节点占有一个属于自己的空间并负责该空间中的所有 的“点 。而每个数据对象通常被唯一映射到多维空间中的一个“点 ，由负责该点的节点 来存储数据对象( 或其索引) 。当某个节点查找数据时，路由路径上的节点明确地知道怎 样转发，才能使得查询信息尽快到达目的节点。c a n 和其它结构化p 2 p 系统利用贪心、局 部的定位算法。这种结构的代表有c h o r d 2 1 ，p a s t r y 2 2 和c y c l o i d 2 3 ，2 4 等。 表1 1 中给出典型p 2 p 系统的各项参数。 表1 1 典型p 2 p 系统的参数 竺! ! ：! 竺兰竺竺竺竺皇兰兰竺皇兰! 摧至茎盎鉴 篆岩趸n a 阿酉 星形服务器 0 1 1 )= l i ) ( i x i ) c h o r d 带弦环 墼值邻近) l i o g n ) l o g n i o g n 路i h 9 。 c a n 多维空间 篷瑟邻近删n i d ) 2 d 2 d t a p c s t n 超立方体i k l 重警匹配o l o g b n ) b * l o g b n iogbn(pl 结构化 a x t o nh i e 地) 路山 挖p 州鬈惹叭絮繁黜o ( t 。鳓7 蝌 k o o r d ed eb n f i j nd er n , i j n 路山、( x i o g n ) 4 l o 州 幽、环形环形路山 。 c y c l o i dc c c 、环形c c c 路山、o ( i o g n ) 7 i o g n 坯形鳗出 p 2 p 覆盖网的特点体现在以下几方面 2 5 1 ： 2 结构化p 2 p 覆盖网设计与搜索机制研究 ( 1 ) 非集中化及自组织：资源和服务分散于所有的节点，信息的传输和服务的实现， 无需中间环节和服务器的介入，直接在节点间进行。这种基本特点，带来了系统的可扩展 性及容错性等方面的优势。 ( 2 ) 隐私保护：p 2 p 覆盖网中信息传输的分散性使得用户的隐私信息被监听、泄露的 可能性大大降低。由于采用分布式哈希表的网络特有的匿名性，保护了发布者的信息，用 户能够更自由地参与到网络中来。 ( 3 ) 可扩展性：随着网络中节点的增多，服务需求增加的同时，资源和服务能力也 提高了。另外，若网络中有n 个节点，结构化p 2 p 覆盖网路由跳数的典型值是l o g n ，所 以随着n 的增加，路由跳数会增多，但是数量非常少，通信效率仍保持在较高水平。因此， 在理论上可以认为它能够无限扩展。 ( 4 ) 负载均衡：在p 2 p 覆盖网中，节点同时扮演服务器与客户端的角色，计算与存 储要求分担给所有的节点，因此说它实现了整个网络的负载均衡。这种负载均衡更好地体 现在结构化网络中，因为它通常使用一致性哈希函数将节点与数据对象分布到覆盖网上： 所有节点大致均匀地分布在整个覆盖网中，所有数据对象的索引大致均匀地分布在所有节 点中，即使有新节点加入、旧节点离开、新对象插入、旧对象删除，一致性哈希函数都能 保证高效的动态调整，调整后的网络仍能保持很好的负载均衡特性。注意，这里的“负载 均衡 没有考虑节点间能力的差异。 1 2p 2 p 中的搜索 p 2 p 覆盖网最重要的功能之一就在于搜索资源，搜索是任何文件共享系统中都必不可 少的重要部分。大多数现存的p 2 p 系统支持通过键值和标识符的简单对象查找。一些现有 的p 2 p 系统能够解决比较复杂的关键字查询和相近搜索。大多数的搜索技术是基于转发的。 从请求节点开始，查询消息在节点间被转发( 或路由) 直到转发到拥有所需数据( 或所需 数据的索引) 的节点 2 5 】。 1 2 1 搜索方法的分类 p 2 p 覆盖网中的搜索方法可以根据搜索查询消息的转发决定来分类，按照此种分类依 据，搜索方法可分为两大类 2 6 ，2 7 】： ( 1 ) 盲目搜索( b l i n ds e a r c h ) 在盲目搜索中，节点不知道关于文件存放位置的信息。因此，其它节点被随机刺探以 确定是否拥有所请求的文件。c m u t e l l a 0 4 采用的洪泛方法，就是一种典型的盲目搜索。为 了查询文件，节点给它所有的邻居节点发送q u e r y 消息，收到q u e r y 消息的节点首先检查 是否有与q u e r y 消息中的查询请求相匹配的共享文件。如果有共享文件，节点就沿着q u e r y 消息传过来的路径回播q u e r yr e s p o n s e 消息。在q u e r y 消息的t t l 没有减到0 的情况下， 结构化p 2 p 覆盖网设计与搜索机制研究 该消息会继续被广播给邻居节点。盲目搜索很简单，只要求节点存储关于网络组织的少量 信息。 ( 2 ) 提示性搜索( i n f o r m e ds e a r c h ) 在使用这种搜索方法的系统中，节点保存可能对于搜索有用的、关于文件存放位置的 额外信息。比如说，一个节点可能拥有其它节点提供的文件( 或文件的索引) 信息。基于 这些额外的信息，节点决定向哪些节点转发查询请求。 如果根据网络结构如何组织及保持对搜索方法进行分类，可以分为： ( 1 ) 基于n o n - d h t ( n o n - d i s t r i b u t e dh a s ht a b l e ) 的搜索 这种方法又可以进一步划分为在结构化p 2 p 网络中的基于n o n d h t 的搜索和无结构 p 2 p 网络中的基于n o n - d h t 的搜索。无结构的p 2 p 网络都使用基于n o n d h t 的搜索。 s k i p n e t 2 8 中使用的搜索方法也属于这种，但它有结构，只是没有使用分布式哈希函数来 映射节点和数据对象，此外s k i p n e t 还支持空间局部性和区间查询。 ( 2 ) 基于d h t 的搜索 在这种方法中，将节点的m 地址、端口号等相关信息用( 一致性) 哈希函数进行哈希， 给系统中的每一个节点分配一个i d ( 标识符) ，同时对于系统中的资源( 数据对象) 也使 用( 一致性) 哈希函数，在与节点标识符相同的空间中分配一个i d 。一般把资源存放在其 标识符与资源标识符最接近、但是大于资源标识符的节点上。在不同的网络拓扑( 环、树、 立方体等) 中，节点按照相应路由表中的信息转发查询请求，完成对资源的搜索。绝大多 数的结构化p 2 p 覆盖网使用这种搜索方法。 1 2 2 几种典型的搜索方法 洪泛法是无结构p 2 p 覆盖网中最简单最直接的方法，它的路由覆盖范围是一个以t t l 值为半径的圆。洪泛法的网络开销是随着跳数限制t t l 的增加而呈指数级增加的，因此可 扩展性不好。 迭代加深【2 9 】也称为扩展环，实际上是一种试探性的洪泛法。查询者首先以一个小的 ”几值做洪泛查询，如果查到则成功结束，否则查询者增加t t l 。这个方法一直继续下去 直到查询成功。其覆盖范围是一个逐渐变大的圆。迭代加深的搜索效率比洪泛法高，但是 没有改变洪泛的本质。 随机走是指节点收到查询消息时，只随机选择一个邻居节点发送该消息，直到数据被 找到或者跳数限制1 v 几用完。在标准的随机走方法中，查询发起节点只发送一条消息，这 条消息被称为一个“行者 ，它随机往前走，直到结束条件满足。这种方法减少了搜索花 费但是有较长的延迟。k - 行者随机走【3 0 】_ 一次派出k 个行者，这k 个行者分别走自己的路。 已证明在通常的无结构网络中，k 行者随机走方法在t 步内所覆盖的范围与单行者方法在 k t 步内所覆盖的范围是等价的。因此，k 行者随机走可以在不带来多少网络开销的情况下， 有效降低查询时延。 4 结构化p 2 p 覆盖网设计与搜索机制研究 上述几种搜索方法属于盲目搜索方法，因为节点没有关于文件存储位置的信息，也不 知道其它节点的存储内容，查询请求的转发存在盲目性。这些搜索方法有很多改进和扩展 算法，且改进的方法大多利用了节点在查询过程中获得的信息，将查询请求转发到有可能 获得更好查询结果的邻居节点上，因而属于提示性搜索。比如文献【3 l 】将行者的概念扩充 为搜索小组，并在此基础上提出了概率搜索小组算法。文献 3 2 】提出了m u l t i l a y e r l i g h t g o s s i p 分级搜索算法。 基于d h t 的搜索都属于提示性搜索，查询请求的路由方法蕴含在其结构之中，下面 通过介绍结构化p 2 p 覆盖网来理解其搜索过程。 c h o r d 2 1 基于一维的环形值域空间，使用一致性哈希函数将节点和数据对象映射到相 同的值域空间中，每个节点负责一部分数据。具体地说，一个节点负责哈希后其键值落在 节点前驱的i d 和其本身的i d 间的数据对象。假如当前节点i d 为7 8 ，其前驱的d 为5 9 ， 则节点负责的数据对象将是哈希后，键值属于区间( 5 9 ，7 8 的数据对象。系统中的每一个节 点保存其前驱节点的信息，k 个后继节点的信息和一个指针表。对于一个值域空间为【o ，2 m ) 的c h o r d 系统，节点指针表的第i 个表项指向距离当前节点至少2 卜1 远的、第一个存活的 节点( osi m ) 。对于一个查询，除了最后一步，每次将查询请求发送到其i d 离键值最 近，但不超过键值的那个节点。由于每次查询消息的转发都将源点到目的点的距离缩小一 半，所以在网络规模为n 的情况下，很容易证明路径长度是o ( 1 0 9 n ) 。 c a n 2 0 使用了虚拟的d 维笛卡尔坐标空间。这个坐标空间是完全逻辑的，在任何时 刻，整个坐标空间被系统中所有的节点动态分割，使得每个节点都有一个它自己的空间， 而且它的邻居就是那些相邻区域中的关联节点。整个虚拟的坐标空间被用于存储( k e y , v a l u e ) 对，此处，k e y 为数据对象，v a l u e 是数据对象的相关信息，比如对象的索引信息。当发布 一个( k l ，v 1 ) 对时，通过使用哈希函数，k l 被映射到空间中的一个点p ，然后这个( k i ，v 1 ) 对被存储到拥有点p 所在区域的节点。当搜索( k l ，v i ) 对时，任何一个节点可以用相同的哈 希函数把k i 映射到p ，然后从点p 检索这个( k i ，v 1 ) 。如果点p 不存储在查询发起节点或 者发起节点的邻居上，节点路由查询请求，路由的每一步只需要将查询消息发送到离k l 更近的邻居。c a n 的性能与其它的覆盖网络有些不同，每个节点有d 个邻居，若网络中有 n 个节点，那么路由长度为o ( d * n d ) 步。 p a s t r y 2 2 采用超立方体结构，使用前缀逐位匹配的路由算法，通常每一步至少比前一 步多匹配一位前缀，直到前缀无法再匹配更多位，此时的下一跳节点为i d 与目的地最邻 近的节点。t a p e s t r y 3 3 也是超级立方体结构，只不过采用后缀匹配，两种路由方法并无本 质的差别，路由效率均为o ( 1 0 9 b 0 ，n 为网络规模。 常数度的结构化p 2 p 覆盖网是一种邻居数目确定的覆盖网，即网络中节点所存储的其 它节点信息的数目是有限的。它们有各自的结构，分别对应不同的路由算法。v i c e r o y 3 4 】 维护了一个具有常数度和对数直径的连接结构图，类似于蝴蝶网络。k o o r d e 3 5 将c h 0 订 和d ea r u i j n 图结合起来，在两个网络中，每次查询需要o ( 1 0 9 n ) 步。c y c l o i d 结合了p a s t r y 结构化p 2 p 覆盖网设计与搜索机制研究 和c c c 图( c u b e c o n n e c t e dc y c l e s ) 3 6 的特征。在节点数为n = d * 2 d 的c y c l o i d 系统中， 每次查询都需要o ( d ) 步。 与上述基于d h t 的结构化网络不同的是，文献 3 7 】中提出的模型虽然采用了结构化的 网络拓扑，但是使用了基于非d h t 的搜索方式，即在c h o r d 基础上，通过n d f s 模型， 采用顺时针漫步( 随即走) 、选择性广播等查找方式进行搜索。 另外有一些网络是分层次的。层次化的p 2 p 覆盖网将节点分为不同的层，每一个层形 成它自己的覆盖，所有的层形成整个的层次覆盖网。覆盖网的层次典型地分为两层或三层。 层次化p 2 p 覆盖网之间的不同主要在于每个层形成的覆盖网的结构 2 5 1 。有些网络分为两 层，上层是能力较强的节点，下层是普通节点。如果上层和下层都是无结构的覆盖网，则 整个覆盖网仍然是无结构网络。如果仅下层是无结构的，而上层覆盖网的节点是按照一定 的结构连接成的结构化覆盖网( 或者相反) ，则整个覆盖网称为混合覆盖网，因为它是无 结构覆盖网和结构化覆盖网混合而成的逻辑覆盖网。查询请求的路由过程包括层间路由和 层内路由。i s p 2 p 3 8 就属于混合覆盖网。文献 3 9 】提出了这种混合p 2 p 环境下的两种有效 的查询扩展算法。 1 3 论文结构与主要创新点 本文后续章节做如下安排：第二章设计一个基于c y c l o i d 与折叠立方体的常数度结构 化p 2 p 覆盖网f c y e l o i d ：第三章改进b g k r 覆盖网的结构及资源发布方法等，将同类查询 限制在一定的覆盖层内，提出层次化的b g k r 网络：第四章研究m c h o r d 中的相近搜索， 给出改进后的区间查询和k 最近邻居查询算法：第五章给出总结与展望。 论文的主要创新点如下： 1 提出了一个基于c y c l o i d 与折叠立方体的常数度结构化p 2 p 覆盖网f c y e l o i d ，利用 折叠立方体中补边的概念优化了c y c l o i d 中的部分查询。由于覆盖网上的一跳可能对应物 理网络上的多跳且c y c l o i d 不是地理近似覆盖网络，因此通过引入补边，减少搜索路由跳 数以优化系统性能。另外，f c y c l o i d 比同维数的c y c l o i d 有更多的节点。 2 提出一种新型的多层次覆盖网络，覆盖网的所有资源基于特定的本体被分成不同的 类别。每一个类别对应着一个覆盖层，一个节点根据它所共享资源的主要类别被分配到一 个覆盖层上。每一个覆盖层以同心多环的k a u t z 图为基本结构。所有的覆盖层形成逻辑上 统一的覆盖网。该网络中的绝大多数节点都维护常数个节点信息，有利于网络维护，一个 资源有若干个代理，有利于提高网络抖动时资源的命中率。 3 将递归分割广播方法引入到m c h o r d 中，使得其区间查询具有针对性，查询消息只 被发送至可能含有查询对象的节点中，在保证准确性的前提下，大大减少了查询消息的数 目，提高了网络的可扩展性；在进行k 最近邻居查询时，查询消息转发的每一步都力图减 少查询半径，从而提高了查询效率。 6 结构化p 2 p 覆盖网设计与搜索机制研究 第二章基于c y c l o i d 和折叠立方体的常数度结构化p 2 p 覆盖网 -2 1 引言 与经典的结构化p 2 p 网络c h o r d 、c a n 等相比，常数度结构化p 2 p 网络中的每个节点 的“度”( 即连接数、邻居数) 是固定的，不随网络规模而变；而其路由、定位、自组织 方式