（计算机应用技术专业论文）混合p2p系统的设计和搜索机制研究.pdf

混合p 2 p 系统的设计和搜索机制研究 摘要 当今，网络广泛应用于社会的各个领域，成为日常生活中不可缺少的必需品。随着网 络的不断应用，网络技术也越来越先进。其中对等网络( p e e r t o p e e r ，p 2 p ) 技术已经成 为世界计算机网络技术研究领域的一个关注点。而且实现了最初网络设计的理念，真正做 到了节点与节点的直接通信，而不再需要借助服务器。 对等网络是被称为将改变互联网未来的四大技术之一的技术，其主要专注于如何高效 地利用国际互联网( i n t e m e t ) 上分布的大量的资源，充分共享巨大的资源。 本文的创新之处在于结合结构化和无结构化p 2 p 网络的特点以及在搜索方面的优缺 点，设计出一个混合p 2 p 系统，系统由两部分组成，一部分是结构化p 2 p 网络，另一部分是 无结构化p 2 p 网络。把网络中的节点按照一定的规则划分成许多组，组内选出性能最优的 节点作为超级节点，除超级节点外的其他节点分布符合无结构化p 2 p 网络的拓扑结构的特 性，各组中的超级节点相连，形成结构化p 2 p 网络的拓扑结构，拓扑图采用d eb r u j i n 图 访问网络的用户兴趣爱好各不相同，但都有一两个感兴趣并尝试搜索的主题，本文提 出了基于用户兴趣的搜索，网络中的节点根据不同的用户感兴趣的主题分组后，更加方便 了用户的搜索。所以混合系统中的节点分组方式可以是基于用户兴趣的分组。 查询是指定位用户指定的内容。指定的内容可以是文件名也可以是某些关键字，就像 百度那样，只要知道一部分关键字就可以进行查询，这种只知道一部分关键字就可以进行 的查询称“模糊查询”。结构化p 2 p 网络的优点是精确查询，缺点是不支持模糊查询，其原 因在于结构化p 2 p 网络的结构严格，网络中的数据对象又被分布式哈希表映射得没有章法。 而无结构化p 2 p 网络虽然很好的支持了模糊查询，但由于t t l 的限制，系统中存在的资源却 未必能找到。结合结构化p 2 p 网络和无结构化p 2 p 网络搜索的优缺点，本文设计了结构化p 2 p 网络中的模糊查询的方法递归并行搜索r p s 。 本文主要研究混合p 2 p 系统的设计和搜索机制，共分为六章。 第一章绪论描述了研究的背景和意义、论文的组织结构：第二章设计了混合p 2 p 系统； 第三章是基于兴趣组的p 2 p 搜索机制；第四章是模糊查询；第五章是仿真实验；第六章给 出总结并展望下一步要做的工作。 关键词：p e e r t o p e e r 混合p 2 p ；覆盖网络；兴趣组；搜索；模糊搜索 混合p 2 p 系统的设计和搜索机制研究 a b s t r a c t l a t e l y , t h en e t w o r ki su s e da l lo v e ro u rd a i l yl i f e ，a n db e c o m ea b s o l u t e l yn e c e s s a r i l y w i m t h ea p p l i c a t i o no ft h en e t w o r k ，t h en e t w o r kt e c h n o l o g yb e c o m e sm o r ea n dm o r ea d v a n c e d a n d p e e r - t o p e e r ( p 2 p 1t e c h n o l o g yi sap o p u l a rr e a c h i n gp o i n ti n t h ei n t e r n a t i o n a li ta r e a t h e o r i g i n a lt h e o r yo fd e s i g nt h en e t w o r ki si m p l e m e n t e d ，t h ep e e r sc a nc o m m u n i c a t e dw i t he a c h o t h e rd i r e c t l y , w i t h o u tt h eh e l po ft h es e r v e r p e e r - t o p e e r ( p 2 p ) i sc a l l e dt h eo n eo ft h ef o n ht e c h n o l o g yi nt h ec h a n g eo ft h en e t w o r k s f u r t h e r p e e r - t o p e e r ( p 2 p ) i sf o c u so nh o w t ou s et h ep l e n t yo fr e s o u r c e s 晰t i l1 1 i g he f f i c i e n c yi n t h ei n t e r n e t ，a n ds h a r et h ee n o r m o u sr e s o u r c e sa d e q u a t e l y t i l ei n n o v a t i o no ft h i st h e s i si sc o m b i n et h ec h a r a c t e r i s t i c so fs t r u c t u r e da n du n s t r u c t u r e d p 2 pn e t w o r k , a sw e l la st h ea d v a n t a g ea n dd i s a d v a n t a g e si nt h es e a r c ha r e a d e s i g nt h eh y b r i d p 2 ps y s t e m t h es y s t e mi sc o m p o s e do ft w op a r t s ，t h eo n ei st h es t r u c t u r e dp 2 pn e t w o r k ，a n dt h e o t h e ri su n s t r u c t u r e dp 2 pn e t w o r k t h en o d e si nt h en e t w o r ka r ed i v i d e di n t om a n yg r o u p si n a c c o r d a n c e 、析t l lc e r t a i nr u l e s s e l e c tt h en o d ew i t ht h eb e s tp e r f o r m a n c ea sas u p e r p e e ri ne v e r y g r o u p ，t h en o d e si nt h eg r o u pf o l l o w e dt h eu n s t r u c t u r e dp 2 pn e t w o r kt o p o l o g y ；t h es u p e r p e e ro f e a c hg r o u pc o n n e c te a c ho t h e r , a n df o r mt h es t r u c t u r e dp 2 pn e t w o r kt o p o l o g y , t h eg r a p ho ft h e s t r u c t u r e dt o p o l o g yu s ed eb r u j i ng r a p h b e c a u s eo ft h eu s e ri n t e r e s t e di no n eo rt w os u b j e c t sa n dt r i e dt os e a r c hf o ri tw h e nt h e y a c c e s st h ei n t e m e t t h e nw ei n t r o d u c e dt h es e a r c hb a s e do nt h eu s e r si n t e r e s t s a f t e rt h en o d ei n n e t w o r kd i v i d e di n t om a n yg r o u p sa c c o r d i n gt h ei n t e r e s t s ，t h es e a r c hi sm o r ec o n v e n i e n t s ow e a d o p tt h ei n t e r e s tg r o u pi nt h eh y b r i ds y s t e m t h es i g n i f i c a n c eo ft h es e a r c hi sl o c a t e di na c c o r d a n c ew i t ht h ed e v e l o p m e n to fc o n t e n t y o uc a ns p e c i f yt h en o d e ，t h ee x a c tn a m eo fd a t ao b j e c t s ，a n dc a na l s ob el i k eb a i d u , o n l y d e s i g n a t e daf e ww o r d s - m i si ss o c a l l e d “b l i n ds e a r c h ”1 1 l ea d v a n t a g eo fs t r u c t u r e d p 2 p n e t w o r ki sa c c u r a t es e a r c h b u tb l i n ds e a r c hi s m o r ec o m p l i c a t et h a nl o c a t e ，t h i si st h e d i s a d v a n t a g eo fs t r u c t u r e dp 2 pn e t w o r k ，b e c a u s eo fi t s s t r u c t u r ei st o os t r i c t ，d i s t r i b u t e dh a s h t a b l em a p p i n gd a t ao b j e c t sw i l lb en o n eo fd i s c i p l i n a r i a n h o w e v e r , u n s t r u c t u r e dp 2 pn e t w o r ki s s u p p o r tt h eb l i n ds e a r c hw e l l ，b e c a u s eo ft h er e s t r i c t i o n so ft h et t l ，t h e r ee x i s t sap r o b l e mi n u n s t r u c t u r e dp 2 pn e t w o r k ，t h er e s o u r c e sa l ei nt h es y s t e m ，b u tc a nn o tf i n d a c c o r d i n gt ot h e a d v a n t a g ea n dd i s a d v a n t a g e si nt h es t r u c t u r e da n du n s t r u c t u r e dp 2 pn e t w o r k ，t h i sp a p e rd e s i g n t h eb l i n ds e a r c hi nt h es t r u c t u r e dp 2 pn e t w o r k r e c u r s i v ep a r a l l e l i s ms e a r c h ，l 冲s t h i st h e s i sm a i n l ys t u d i e sa r et h ed e s i g no fh y b r i dp 2 ps y s t e ma n dt h es e a r c h ，a n di s d i v i d e di n t os i xc h a p t e r s i nt h ef i r s tc h a p t e rw ei l l u m i n a t eb a c k g r o u n do fo u rs t u d ya n dp u tf o r w a r do ft h ep r o b l e m s ， 混合p 2 p 系统的设计和搜索机制研究 t h ew o r kw ed oi nt h ep a p e ra n dt h es t r u c t u r eo ft h ep a p e r t h es e c o n dc h a p t e rd e s i g n st h eh y b r i d p 2 ps y s t e m t h et h i r dc h a p t e ri st h es e a r c hb a s e do l lt h eu s e r si n t e r e s t s i nt h ef o n hc h a p t e r , t h e b l i n ds e a r c hi nt h es t r u c t u r e dp 2 pn e t w o r k i nt h ef i f t hc h a p t e r , t h es i m u l a t i o n a n dt h el a s t c h a p t e rm a i n l yp r e s e n t st h ef o l l o w i n gp r o b l e m sf o rf u t u r er e s e a r c h k e yw o r d s ：p e e r - t o p e e r ；h y b r i dp 2 p ；o v e r l a yn e t w o r k ；t h eg r o u po fi n t e r e s t ； s e a r c h ；b l i n ds e a r c h 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) ， 本人郑重声明：此处所提交的博士口硕士酣论文混合p 2 p 系统的 设计和搜索机制研究，是本人在导师指导下，在曲阜师范大学攻读博士口 硕士目学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包 含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中已明确的方式注明。本声明的法律结果将完全由本人承 担。 作者签名：振春睫日期：御7 年6 日j j i 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 混合p 2 p 系统的设计和搜索机制研究系本人在曲阜师范大学攻读博 士口硕士日每位期间，在导师指导下完成的博士口硕士由每位论文。本 论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的 名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同 意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和 借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可 以公开发表论文的全部或部分内容。 作者签名：苏春霞 剔噬轹岛阑 v v 日期：加7 7 平石目弓日 日期：叫6 、) 混合p 2 p 系统的设计和搜索机制研究 1 1 研究背景和问题的提出 第一章绪论 网络技术的迅速发展，使得网络在社会中成为一种必需品。网络技术提供了一种便捷 的方式来获取资源共享。传统的“客户服务器”下载方式，由于受服务器带宽的限制，进行 下载操作的用户越多，网络速度越慢。对等网络( p e e r - t o p e e r ) 的产生，有效地利用了网 络带宽，实现了网络设计的最初理念，真正做到了节点与节点问的直接通信，提高了下载 速度，快速共享资源。 根据结构可以将对等网络分以下四种： 1 集中式系统( c e n t r a l i z e ds y s t e m ) 。以n a p s t e r 1 为代表。集中式系统是最早出现的纯 资源共享对等网络，集中式系统中必须从服务器查询所需的资源所在节点的位置，连线到 该节点获取资源。集中式系统的优点是搜索效率高、维护简单。集中式系统的缺点是单点 失败( s i n g l ep o i n tf a i l u r e ) 。所谓单点失败是指如果服务器出现故障或者离线，整个系统就 会无法正常运行，而且如果用户数量很多，服务器还会因为负担过重而瘫痪。 2 分散式无结构化系统( d e c e n t r a l i z e du n s t r u c t u r e ds y s t e m ) 。以k a z a a 2 为代表。分散式 无结构化系统在覆盖网络( o v e r l a yn e t w o r k ) 上的信息查询是通过洪泛( f l o o d i n g ) 方法。 分散式无结构化系统的优点是没有集中服务器，不存在单点失败，即使用户数量很多也能 正常运行；最重要的是在高动态网络环境下分散式无结构化系统仍能正常运行。分散式无 结构化系统的缺点是在网络规模不断变大的情况下，因为采用洪泛方法来进行查询，网络 流量剧增，而只能搜索到某一部分资源导致搜索效率低。而且由于t t l ( t i m e t o l i v e ) 的限制，即便系统中存在资源但未必能查找到而导致搜索失败。 3 分散式结构化系统( d e c e n t r a l i z e ds t r u c t u r e ds y s t e m ) 。以c h o r d 3 、p a s t r y 4 等为代表。 分散式结构化系统是研究人员为了改善分散式无结构化系统的搜索效率低的问题而研发 出来的。分散式结构化系统的优点是搜索效率高。使用分布式哈希表( d i s t r i b u t e dh a s h t a b l e _ d h t ) 将关键字映射到某个节点上，然后再根据各系统拓扑结构的路由方法和策略 来查询资源。分散式结构化系统的缺点是维护分布式哈希表代价太大，并且不能支持语义 相关的多结构查询。 4 混合式系统( h y b r i ds y s t e m ) 。上述系统各有优缺点，混合式系统的设计整合了各系 统的优点加以运用，避免各系统的缺点，扬长避短。系统中选择性能( 处理、存储、带宽 等方面性能) 较高的结点作为超级结点( s u p e r p e e r ) ，超级节点会保存普通节点的信息，超 级节点下的普通节点利用超级节点来转发信息，构成了一种层次结构( h i e r a r c h i c a l s t r u c t u r e ) 。所有的超级节点是一层，所有的普通节点是一层。 本文在覆盖网络的基础上，将网络中的节点进行分组，组中节点具有无结构化系统的 拓扑特点。选择组内综合性能相对好的节点作为超级节点，超级节点间相互连接后，形成 混合p 2 p 系统的设计和搜索机制研究 了结构化系统的拓扑特点，使网络具有层次化结构。结合分散式结构化系统和分散式无结 构化系统的特性，使整个网络的节点构成一个混合系统。 文献 5 1 1 6 7 1 1 8 9 是近年来关于基于兴趣( i n t e r e s t b a s e d ) 的对等网络的研究，这些 研究的重点是如何提高分散式无结构化系统低下的搜索效率。采用兴趣分组的原因是用户 ( p e e r ) 在日常生活中上网浏览信息或者查询资源时，一般只对少数几个感兴趣的主题进 行查询与搜索。如果对系统中的资源按照用户的兴趣进行分类，用户在进行查询和搜索时 会更高效和便捷。 对等计算是未来网络中的关键技术，对等网络是互联网技术中的重要组成部分。如何 高效地搜索p 2 p 网络上的资源是p 2 p 网络实现的最为关键的问题。 节点( p e e r ) 通过路由能定位到想要的结果和数据，但是大多数情况下，用户并不清 楚自己确切想要什么，好比g o o g l e 上人们只是输入几个关键词，希望从中得到一些东西。 因而p 2 p 网络需要建立像g o o g l e 那样的查询和搜索机制。但是g o o g l e 采用的集中式搜索 引擎的方法对p 2 p 网络并不适用，这主要是因为建立集中式搜索引擎的巨大开销和p 2 p 网 络中节点和数据的高动态性。 无结构化p 2 p 网络能够很好的支持模糊查询，但是受到t t l ( t i m e t o l i v e ) 的限制， 系统中即便存在需要的资源也未必能够查询成功。而结构化p 2 p 网络只支持精确查询不支 持模糊查询。本文设计的递归并行搜索机制( r e e u r s i v ep a r a l l e l i s ms e a r c h r p s ) 使得结 构化p 2 p 网络也能够进行模糊查询。 本文的创新点：设计了混合p 2 p 系统，由结构化p 2 p 网络和无结构化p 2 p 网络混合而 成，结构化部分拓扑结构采用d eb m j i n 图；按照一定的规则对系统中的节点进行分组，组 内节点形成无结构化系统拓扑结构。随后提出了一个分组方法一基于用户兴趣的分组。 通过采用兴趣分组能够有效地提高用户的搜索效率。最后，针对结构化p 2 p 网络中不能进 行模糊查询的情况，设计了并行递归搜索机制，使得结构化p 2 p 网络也能够进行模糊查询。 2 混合p 2 p 系统的设计利搜索机制研究 1 2 论文的组织结构 第一章简要介绍了本文的研究背景、问题的提出、本文所做的主要工作以及组织结 构。 第二章混合p 2 p 的设计，超级节点部分形成结构化p 2 p 网络的拓扑特性，普通节点 形成无结构化p 2 p 网络的拓扑特性。 第三章基于用户兴趣的p 2 p 搜索机制，提出了一种分组方式兴趣分组。系统中 的节点按照用户的兴趣，分成不同主题的小组。方便了用户的搜索，有效地提高搜索效率。 第四章模糊查询，结构化特性的超级节点间的模糊查询。 第五章仿真实验 第六章总结与展望 混合p 2 p 系统的设计和搜索机制研究 第二章混合p 2 p 系统的设计 混合p 2 p 系统的设计结合了结构化p 2 p 网络和无结构化p 2 p 网络的优点。一般来说， 混合系统要优于单一系统，因为它能够结合两个或两个以上的单一系统的技术，避免单一 系统的缺陷。所谓单一系统是指系统中只有一个结构，要么是固定拓扑的结构化p 2 p 网络； 要么是无结构化p 2 p 网络。混合的成功与否在于对结合在起的各个部分的特性和优缺点 的了解和掌握。混合系统优于单一系统也是因为设计者了解单一系统的局限和缺陷，进行 改进，使得系统性能大大提高。但是并非每一个任意的系统的结合都能够提供优异的解决 方案。 具体来说，设计混合系统是为了避免单一系统的缺陷，减少固定数量的节点间点对点 的连接，降低大多数节点间路由表维护费用。此外，分组机制的使用为系统提供了稳定的 网络拓扑结构。把节点划分为超级节点和普通节点是为了处理异构的节点和使用者的行 为。这个设计能够充分利用每个节点的能力，尤其是能力强的节点，其目的是最大化分组 效率，从而能有效地支持异构性和平衡均匀分布的负载。显然，混合系统是处理大规模、 动态性和异构性的唯一可行的办法。 文献【1 0 】【l l 】【1 2 】【1 3 】【1 4 】中设计的混合系统要么是把无结构化p 2 p 网络结构化了的系统 要么是把结构化p 2 p 网络无结构化了的系统，总的来说就是把无结构化的p 2 p 网络和结构 化的p 2 p 网络很好的结合在一起，形成混合系统。 2 1 覆盖网络 p 2 p 网络的核心机制是在应用层建立逻辑上的覆盖网络( o v e d a yn e t w o r k ) ，封装应用 层下的传输层、网络层、网络接入层，p 2 p 网络的研究者和开发者不必关心下面三层是如 何工作的，而是仅考虑在应用层上的覆盖网络的工作情况，将精力集中于覆盖网络的设计、 优化上，如图2 1 所示。在p 2 p 覆盖网络上依靠d h t 能准确、快速地路由消息和定位数据 对象，这正是p 2 p 查询的优势所在。 覆盖网络被认为是用来改善互连网路由的最优途径。简单说来覆盖网络就是应用层网 络，它是面向应用层的，不考虑或很少考虑网络层，物理层上的操作。详细说来，覆盖网 络是指建立在另一个网络上的网络。该网络中的结点可以看作是通过虚拟或逻辑链路而连 接起来的。虽然在底层有很多条物理链路，但是这些虚拟或逻辑链路都与路径一一对应。 许多p 2 p 网络都是覆盖网络，它运行在互连网的应用层上。覆盖网络允许对没有i p 地址 标识的目的主机路由信息，例如：f r e e n e t 1 5 1 1 1 6 1 和分布式哈希表( d i s t r i b u t e dh a s ht a b l e d h t ) 可以路由信息到一个存储特定文件的结点，而这个结点的i p 地址可能事先并不知道。 4 混合p 2 p 系统的设计和搜索机制研究 2 2 拓扑结构 。系统1 卜点口 路器1 ，点 + o v e r i a y 链路-i p 链路 图2 1 覆盖网络 o v e r l a y q 络 p 2 p 系统模型是一个无向图g = - ( v ，e ) ，v 是节点集，e 是节点间的边集。彼此知道 i p 地址的两个节点认为是邻居，邻居的个数称为节点的度。每个节点v 的容量值为c a p ( v ) ， 假设每个节点都知道自己的容量。如果信息需要在不相邻的两个节点间传递，那么信息将 在多条边上传递，信息在路径上传播的长度称为跳数。f 。( v ) ，v v ，是节点v 除自己之 外的r 跳邻居集，节点v 的直接邻居，用1 1 ( v ) 来代替f 1 ( v ) 。 本文设计的混合系统，具有双重( t w o t i e r ) 体系结构。系统中节点按照一定的规则进 行分组，组中节点选取性能好的节点作为超级节点，超级节点连接后具有结构化p 2 p 系统 的拓扑特性，有严格的拓扑结构，本文采用d eb 州i n 图作为结构化的拓扑图，来嫁接两种 不同系统的拓扑结构；组内的普通节点形成无结构化p 2 p 系统的拓扑结构。此系统是结合 无结构p 2 p 系统和结构化p 2 p 系统的混合系统。 混合p 2 p 系统的拓扑结构如图2 2 所示：覆盖网络是d eb 州i 1 1 ( 2 ，3 ) 有向图。图中 两个节点放大显示组内网络连接来表明节点分组。 混合p 2 p 系统的设计和搜索机制研究 图2 2 混合p 2 p 系统的体系结构 组内节点采用无结构化系统拓扑特性的原因：p 2 p 网络是高动态的，p 2 p 用户的在线 时间是短暂的，节点变动很频繁。文献【1 7 】通过测量g n u t e l l a 1 8 】和n a p s t e r 1 】网络表明， 一个节点的平均在线时间是6 0 分钟，对于一个有1 0 0 ，0 0 0 个节点的较大对等网络，每分钟 有1 6 0 0 个节点离开和加入的变动，节点频繁变动对无结构的对等网络影响很小。但是在 结构化网络中，为了维持系统的正确性和有效性，每次节点变动就需要o ( 1 0 9 n ) 个修复操作。 而且如果系统中某个节点是非正常离开，那么会导致更多的开销。 2 3d eb r u j i n 图 互连网络的设计有两个固有的基本限制：网络中的每个元件的接口数是有限的；为确 保通信，数据传输过程通过的中间点数必须尽可能地小。在这两个限制条件下，网络最多 能连接多少个节点? 用图论的语言，这个问题可以描述为：求最大度为d ，直径最多为k 的图的最大阶数，即最多的节点数。这就是图论中著名的“度一直径问题。 与其他结构化的拓扑结构相比，d eb r u j i n 图在节点数固定的条件下能提供最优的直 径，最好的连接。 d eb m j i n 图是由d eb r u j i n 1 9 和g o o d 2 0 于1 9 6 4 年独立地提出来的。作为互联网络 拓扑结构，d eb 州i n 图网络是由s c h l u m b e r g e r 2 1 于1 9 7 4 年首次提出来的。 对于两个给定整数d ( 2 ) 和n ( 1 ) ，d eb m j m 有向图，记为b ( d ，n ) ，通常有下面 三个等价定义。 定义2 1 ：利用长为n 的d 元序列来定义 b ( d ，n ) 的顶点集 v = x l x 2 k ：x i 0 i l ，d - l ，i = l ，z ，n ) ， b ( d ，n ) 的边集e 是由顶点x t x 2 x 。到x 2 x 。口的所有边组成的；其中 6 混合p 2 p 系统的设计和搜索机制研究 口 0 ，l ，dl 。 定义2 2 ：利用线有向图来定义 d eb 州i n 有向图b ( d ，n ) ，能被定义为花完全图k d + 的( n 一1 ) 重线图( 即k d + 是在完全 有向图k 。的每个顶点上添加一条环而得到的有向图) 。因此，d eb m j i i l 有向图b ( d ，n ) 能递 归地定义为 b ( d ，1 ) = k d + ；b ( d ，n ) = l n - 1 ( k d + ) ，n 2 。 定义2 3 ：利用代数方法的定义 b ( d ，n ) 的顶点集v = 0 ，1 ，d 。- 1 ) ，边集 e = ( x ，y ) ：y 量x d + a ( m o d d 。) ，口= 0 ，l ，d - l 。 由前两个定义得到的三个小阶d eb 删i n 有向图b ( 2 ，3 ) ， 0 0 1 、 l i 、 o o 、一 i l 7 、 10 0 【0 1 0 j 、o 袋 1 ( 1 0 ) 0 图2 3d eb r u j i n ( 2 ，3 ) d eb r u j i n 2 2 用于许多的p 2 p 系统中。如图2 3 所示是一个有向的d eb m j i n ( 2 ，3 ) 图， 图中最大出度为2 ，直径为3 ，阶为8 。若图有固定的出度为2 ，节点的最大数限制在2 d ( 在 此例中d = 3 ) ，图有2 叫条有向边，每个节点有长度为d 的字符串做标识符，字符串的每 个字节有k 个( 在此例中k - 2 ) 不同的值。一般情况下，每个节点的字符串表示为u 。u ：u d ， 节点间连接服从简单的左移操作u 。( u ：u d ) u 。，u 。可以从( o ，k - 1 ) 中任意取值。 定义2 4 ：摩尔界：最大度为k ，直径为d ，节点数n 最大为 d + i 1 n l + k + k2 + k d = ! 二：n 、 k l d eb r u j i n 图节点数n = k d 或n = k d + k 蹦近似于摩尔界。或者换另一种方式描述： 给定节点数n ，度k ，求得最小直径d ，d il o g k 州仙1 mi 一1 = d m ，d eb r u j i n 图直径 为d = ll o g 。nl = d m + 1 是接近最优直径的图。举例说明： 假设有一百万个节点，度为k ( k = ll o g ：ni = 2 0 ) ，在这种情况下，c h o r d 提供的图的 直径为d = 1 0 9 ：n l = 2 0 ，而d eb r u j i n 图的直径为d = | o g k n l = i 0 9 2 0 n l = r 4 6 1 1 = 5 ， 最优的摩尔图的直径d m = il o g k 州k 1 卜”i - 1 = | - 4 5 9 = 5 。 所以选用直径最接近最优直径的d eb 州i n 图作为混合网络中结构化部分的拓扑结构。 7 混合p 2 p 系统的设计和搜索机制研究 2 4 超级节点的选择 超级节点通常具有高带宽、高处理能力、大存储容量的特点，不受网络地址转换 ( n e t w o r k a d d r e s s t r a n s l a t i o n - n a t ) 的限制，相比之下，普通节点通常具有低带宽，低处 理能力，小存储容量的特点，常常受网络地址转换的限制。 当普通节点加入网络时，它会选择一个超级节点作为其父超级节点，并且与父超级节 点维持一条半永久的t c p 连接，将它所共享的文件元数据信息( 类似文件索引) 上传给这 个超级节点。 系统初始，只有一个节点，则认为该节点是超级节点。新节点加入系统，新节点到超 级节点的延迟小于t o l ，即l a t ( n 。，s p ) t o l ；如果l a t ( n , 。，s p ) t o l ，寻找另外的超级节点， 满足l a t ( n 。鲫，s p ) t o l ；如果没有满足条件的超级节点，则新节点自己作为超级节点。这 里我们只讨论第一种情况。 如果新加入的节点无论带宽、处理能力、存储容量等都比它所选择的超级节点高，则 会改变节点的角色： p ( r o l e ( v ) = o p r o l e ( v ) = s p ) = l 二百 s 是发送给s p 的信号量大小，见是节点v 返回的门限值，o p 是普通节点( o r d i n a r yp e e r ) 。 判断发送出去的和返回的信号的多少方法为：如果s 或，则p = i ，也就是说发送的信号 远多于接收到的信号，s p 的处理能力小于新加入节点的能力，交换两个节点的角色；如果 s t o l ，则 新加入节点n 一会寻找其他合适的超级节点。如果没有合适的超级节点满足条件，则新加 入节点n 自己成为超级节点。图2 4 是新节点加入时的几种情况： 图2 4 ( 1 ) 是新节点加入之前的情况。 8 混合p 2 p 系统的设计和搜索机制研究 s p l v ( 1 ) s p n n e w vv ( 2 ) ( 3 ) ( 4 ) n n e w 图2 4 节点的加入 假设超级节点的最大容量是，则 ( 1 ) 如果超级节点的容量小于，即e a p ( s p ) ，超级节点将接受连接请求，则新加 入节点n 一连接到超级节点。并加入超级节点s p 的邻居集f ( s p ) ，如图2 4 ( 2 ) 所示。 ( 2 ) 如果超级节点的容量等于，即e a p ( s p ) = ，超级节点将接受连接请求，并检查 自己是否存在这样的邻居节点v 满足以下条件：v f ( s p ) 且e a p ( v ) ，新加入节点n 一连 接到超级节点的邻居节点v ，并加入已存在节点v 的邻居集r ( v ) ，也是超级节点的邻居集 的邻居集r 2 ( s p ) ，如图2 4 ( 3 ) 所示。 ( 3 ) 如果超级节点的容量等于，即c a p ( s p ) = ，超级节点将接受连接请求，检查到 自己没有满足条件的邻居节点v ，超级节点的所有邻居节点的容量都达到最大值，则超 级节点丢掉任意一条与其邻居节点v 的连接，而与新加入节点n 一，建立连接，节点v 也与 新加入节点n 。建立一条连接。新加入节点n 。加入超级节点的邻居集f ( s p ) ，v 加入新加 入节点的邻居集f ( n 一) 。如图2 4 ( 4 ) 所示。 每个节点都有自己的角色，要么是超级节点，要么是普通节点。节点或者作为超级节 点或者作为普通节点加入网络。一个超级节点连接多个普通节点，一个普通节点可能直接 连接一个超级节点或在t o l 范围内与一个超级节点多跳连接。 2 5 2 节点的离开 节点离开有两种情况：一、普通节点的离开。二、超级节点的离开。 一、普通节点的离开 p 2 p 网络中节点的离开是很正常的事，维护网络节点的正常离开也是p 2 p 网络管理的 一部分。节点的离开分为正常离开和非正常离开。 若节点n 正常离开它所属的某个组，则n 须向组内所有节点发送一个广播消息，当组 内的超级节点收到n 发来的广播消息以后，首先删除其自身路由表中与节点n 相关的路由 信息，以及超级节点中保存的关于n 的查询信息；然后再发送一个删除消息给其它组的超 9 混合p 2 p 系统的设计和搜索机制研究 级节点，通知它们检查各自的超级节点，查找与n 相关的查询信息，将其删除。 若节点n 非正常离开系统，如断电，网络拥塞等，则节点n 所属组的超级节点采用查 询的方式得知其离开，然后删除其路由信息，并通知其它超级节点。这种情况下，超级节 点会定期检查组内节点，一旦发现有节点非正常离开系统，就会做出相应的操作。 二、超级节点的离开和备用超级节点 为了防止单点失败，在系统中引入了备用超级节点( s t a n d b ys u p e r p e e r ) 。在每个组中 设置了多个备用超级节点，按照节点性能的高低进行排序，每个组的超级节点要定期将自 身保存的路由表发送到每个备用超级节点上进行备份。 超级节点正常离开系统之前，应先向备用超级节点中排名最高的可用备用超级节点发 送离开消息，得到回复以后，超级节点应将其保存和维护的本组内的路由表，以及其它组 中超级节点的路由信息发送到备用超级节点，备用超级节点收到超级节点发来的路由信息 后，发送一个确认消息给超级节点。超级节点收到确认消息后，正式离开系统。备用超级 节点发送完确认消息后，就开始着手重新组建本组，备用超级节点根据路由信息表给本组 内的所有节点发送重新建立连接请求，一旦新的连接建立，备用超级节点就正式成为本组 的超级节点。新的超级节点确立以后，自动运行超级节点选择规则，重新选出几个备用超 级节点，重新备份新的路由表。 超级节点如果是非正常离开系统，则由备用超级节点中排名最高的可用的备用中心节 点成为超级节点，由它利用备份的路由表重新组建网络。 节点的不稳定性是p 2 p 网络的一个重要的特点，因此如何管理好节点的频繁加入与离 开是p 2 p 网络管理的一个难点。本文提出的备用超级节点可以有效地防止单点失败对网络 造成的危害。另外采用节点的准入制度，也有效的避免了用户节点加入的随意性，对于分 组的实现和提高网络的搜索效率都有很大的帮助。 2 5 3 路由 一、组内的路由 组内的路由采用洪泛方法。当一个节点收到请求消息时，首先检查自己是否拥有该文 件，如果有就回送消息，如果没有则回到自己的路由表里找与文件标识最接近的文件标识， 并把请求消息发送给与之相应的节点；如果最终查询成功，文件被回送，这个节点除了将 文件回传给请求者外，还会在它自己的数据库里缓存这个文件，并且在自己的路由表里创 建一个新项指向该文件的数据源。因此，如果以后该节点再收到对此文件的请求，那么可 以立刻返回自己缓存的文件；如果收到与此文件标识相近的文件标识，则会把请求消息传 给路由表罩所有记录的文件源。 如果某个节点不能将请求消息发送给它所选择的最好节点，( 这可能因为该节点此时 不在线，或者是如果传送给它会导致循环路径) ，它将尝试它认为第二好的节点，如果这 l o 混合p 2 p 系统的设计和搜索机制研究 个节点再不行，再尝试第三好、第四好。如果所有的尝试都失败了，就回送失败消息 给自己的前一跳，由前一跳节点来尝试新的下一跳，在路由过程中，如跳数限制减为o ， 节点不会再做尝试，而只是发送失败消息给自己的前一跳。对于跳数限制，在路由过程中 每个节点都可以单方面减少跳数限制以减轻网络负担，甚至可以直接丢弃某个消息以释放 存储容量。 二、超级节点间的路由 网络的主体普通节点，将所连接的超级节点当作自己的“服务器 ，查询直接发 送给超级节点，由超级节点代为完成查询。而网络的核心超级节点，自组织成一个超 级节点网络。由于超级节点的数目相对很少，所以超级节点网络即使采用结构化网络的路 由方式- d h t ( 分布式哈希表) 也是可行的，并且可以提高查询的成功率。 三、跨组路由 组内节点未在本组内找到所需资源，则需到其他组中查找，先发送查询信息给本组的 超级节点，由超级节点将查询信息发送给目标资源所在组的超级节点，再由该超级节点发 送至目标资源所在的节点。 2 6 小结 本章结合结构化和无结构化p 2 p 网络的特点，以及在搜索方面的优缺点，设计了一个 混合p 2 p 系统，该系统可以把网络中的节点按照一定的规则划分成许多组，选出性能最优 的节点作为超级节点，除超级节点外，其他节点均符合无结构化p 2 p 网络的拓扑特性，超 级节点以结构化p 2 p 网络结构连接，拓扑图采用d eb r u j i n 图。给出了系统拓扑结构，分 析了超级节点的选择和节点加入和离开的情况。混合p 2 p 系统降低了大多数节点问路由表 维护费用。 混合p 2 p 系统的设计和搜索机制研究 第三章基于兴趣组的p 2 p 搜索机制 对等网络的搜索应用十分广泛，其中最著名的软件有g n u t e l l a 1 8 】，n a p s t e r 1 】和 b t 2 3 2 4 】。这些系统的搜索仅仅是资源文件名的匹配，却无法对资源的内容进行搜索。 p 2 p 系统中对资源内容的搜索【2 5 】是一个热点。 传统的资源搜索方法是像g o o g l e 或y a h o o 这样的w e b 搜索引擎。w e b 搜索引擎是采 用网络爬虫( c r a w l e r ) 2 6 把从网络上下载的页面保存到页面数据库中的集中式的搜索方 法，再根据页面解析的内容建立索引。但是这种w r e b 搜索引擎也有很多缺点【2 7 】，页面数 据库更新不及时；对所有用户的搜索请求都会返回同样的结果等。对等网络的检索技术就 能够根据用户的兴趣进行对资源内容的搜索 2 8 】。 3 1p 2 p 搜索技术的研究现状 3 1 1 无结构化p 2 p 网络的搜索技术 一、洪泛法( f l o o d