（计算机应用技术专业论文）基于语义的动态超节点网络模型及搜索算法.pdf

摘要 对等网络( p 2 p ，p e e r t o p e e r ) 作为一种新兴的网络计算模式，打 破了传统的c s 模式，其应用越来越广泛。但是随着对等网络规模和 用户量的增加，p 2 p 环境下的信息量也随之飞速增长，给用户在搜索、 定位和获取信息资源上都带来了巨大的困难。对等网络信息搜索技术 是解决这一问题的重要手段。较好的信息搜索技术不但能够提高搜索 命中率，减轻节点负载，降低网络开销，还能够根据用户的兴趣提高 搜索性能，为用户的搜索节省时间。 针对目前非结构化p 2 p 网络泛洪搜索机制的盲目性所引发较大 网络流量的问题，提出一种基于语义的改进搜索算法。为每个节点引 入朋友节点，根据节点间的兴趣相关度，逐步聚集具有相似兴趣的朋 友节点信息，利用信息资源聚集程度将网络中的节点进行逻辑上划分 为逻辑超节点和普通节点。根据历史成功搜索记录更新朋友信息，以 减少缓存对象替换的频率，同时也不断的更新逻辑超节点，从而减小 搜索范围，提高搜索效率。实验表明改进算法有效地减少了网络信息 流量。 最后本文对改进的基于兴趣的搜索方案进行了分析和模拟实验， 相比于传统的非结构化系统中的搜索机制，本文所提方案提高了搜索 效率，缩短了搜索路径，并且减少了系统中的消息流量。 关键词p 2 p ，语义，搜索，聚集，超节点 a bs t r a c t a san e wn e t w o r kc o m p u t em o d e ，p 2 p ( p e e r - t o p e e r ) n e t w o r k m o d i f i e st h et r a d i t i o n a lc sm o d ea n dh a sb e e nu s e dm o r ea n dm o r e p o p u l a r i t y t h e i n f o r m a t i o na m o u n tr o s e r a p i d l y w i t ht h ei n t e n s e i n c r e m e n to fb o t hu s e r s q u a n t i t ya n dn e t w o r k ss c a l ea n dc a u s e da s e r i o u sp r o b l e m ，d i f f i c u l t yi ns e a r c h i n g ，l o c a t i n ga n dr e t r i e v i n gr e s o u r c e t oc o n q u e rt h i sp r o b l e m ，i n f o r m a t i o nr e t r i e v a li np 2 pn e t w o r ki sa p i v o t a lt e c h n i q u e ag o o ds t r a t e g yn o to n l y i n c r e a s e sh i tr a t i oa n d d e c r e a s e sn o d el o a da n dn e t w o r kc o s t ，b u ta l s os e r v e sf o ru s e r si n s t u d y i n gr e l e v a n ti n f o r m a t i o nt oi m p r o v et h ep e r f o r m a n c ei nl a t e rs e a r c h p r o c e s sa n d s a v et i m e f o ru s i n gb r o a d c a s t i n ga si t sb a s i cs e a r c hs t r a t e g yi nu n s t r u c t u r e d p 2 pn e t w o r k sn o w , al a r g e rn e t w o r kf l o w sa r ec a u s e d s o ，a ni m p r o v e d s e a r c ha p p r o a c hb a s e do ns e m a n t i ci s p r o p o s e d b a s e do nr e l a t i o n a l i n t e r e s t sb e t w e e np e e r s ，i n t r o d u c ef r i e n d - n o d e st oe a c h p e e r , a n d g r a d u a l l yg a t h e rn o d e sw i t ht h es a m ei n t e r e s t t h e nd i v i d en o d e si n t ot w o t y p e s ：s u p e r - n o d e si nl o g i ca n do r d i n a r y - n o d e sw h i l eg a t h e r i n g u p d a t e t h ef r i e n d - n o d e s i n f o r m a t i o nm a k i n gu s eo ft h es u c c e s s f u ls e a r c h e s s o r e d u c et h ef r e q u e n c yo ft h ec a c h e dn o d e s r e p l a c e m e n ta n du p d a t e s u p e r - n o d e s i n f o r m a t i o ni nl o g i c a sar e s u l t ，t h es e a r c he x t e n s i o ni s r e d u c e da n dt h es e a r c he f f i c i e n c yi si m p r o v e d s i m u l a t i o nr e s u l t ss h o w t h a ti m p r o v e dm e t h o d se n h a n c et h es e a r c he f f i c i e n c ya n dr e d u c et h e n e t w o r kc o s t s m o d e la n a l y s i sa n ds i m u l a t i o nr e s u l t sp r o v et h a t ，t h ei n t e r e s t b a s e d s e a r c hm e c h a n i s mi sm o r ee f f i c i e n tt h a nt h et r a d i t i o n a ls e a r c hm e t h o di n g n u t e l l a - l i k es y s t e m k e y w o r d s ：p 2 p , s e m a n t i c s ，s e a r c h ，g a t h e r , s u p e r - n o d e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：j 挞扯 日期：斟年月坐日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：趣鱼 导师签名燃日期：卫1 年妇三日 硕士学位论文第一章绪论 1 1 研究背景及意义 第一章绪论弟一早珀1 ：匕 随着计算机技术的飞速发展，以共享资源为目的的计算机网络及其相关应用 得到了迅猛的发展和普及，i n t e m e t 早已深入到人们的日常生活中。基于开放互 联的t c p i p 网络通信技术提供了简单易行的互联标准，网络规模越来越大，连 入网络中的设备、计算单元的数量和种类也越来越多，分布在i n t e m e t 各个角落 的各种资源也越来越丰富。如何对这些资源进行采集、获取、组合、处理和利 用也一直是计算机网络研究的一个热点问题。 目前在资源共享方面主要采用的是客户机服务器：( c l i e n t s e r v e r ) 模式，客户 机通过i n t e m e t i n t r a n e t 与服务器互连，整个网络依赖于中心节点来提供服务。 这样用户所能得到的资源数量、服务质量、共享性能往往有一定的局限性，无 法满足规模化发展的需要。客户机服务器模式实质上是一种集中式体系结构， 它在海量信息的组织、访问等方面存在着服务瓶颈、易于崩溃等缺点。 p 2 p t l l ( p e e r - t o p e e r ) 网络正凭借着自身的优势获得了越来越广泛的应用： 在p 2 p 网络中，为数众多的普通节点成为数据的主要载体，打破了少数服务器 垄断资源的局面；节点之间直接交换信息，避免或减轻了单点故障和服务器性 能瓶颈的问题；节点拥有充分的自主性，可以自由地加入或离开网络。目前的 p 2 p 网络按照搜索机制大体可分为结构化p 2 p 网络和非结构化p 2 p 网络两大类： 结构化p 2 p 网络对节点进行了有效地组织，获得了较高的搜索效率，但是因为 结构化p 2 p 网络对结构要求过于严格，更新代价过大，仅适用于小规模的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 网络结构特点并研究改进搜索性能的算法具有积 极的意义。 硕士学位论文第一章绪论 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 系统的可扩展性，节点的不确定性，设计一个好的搜索机制比较困难。最早的 n a p s t e r 2 】系统采用集中式的结构来进行搜索，中央服务器保留了所有资源的索 引，节点( p e e r ) 通过向中央服务器搜索索引然向别的节点请求获取资源，n a p s t e r 的组织结构决定了它的可靠性和可伸缩性不太好。现阶段，国内外p 2 p 搜索算 法的研究热点主要集中在以下三个方面：( 1 ) 在非结构化p 2 p 网络结构基础上， 引入统计信息对节点的路由进行指导，改善搜索的效率，避免泛洪搜索引起的 巨大通信量；( 2 ) 在结构化p 2 p 网络中，通过研究语义路由以及将节点在覆盖 网( o v e r l a y ) 上的逻辑地址与节点在物理网络中的i p 地址对应起来的方法，提 高语义路由效率和可扩展性；( 3 ) 在结构化以及非结构化p 2 p 网络的基础上， 研究融合两者的方法，提出新的网络模型，并提出基于新模型的资源分布、路 由查找和成员关系。 非结构化p 2 p 网络采用泛洪( f l o o d i n g ) 的方法进行搜索，例如g n u t e l l a 3 。，一 个节点向所有邻居节点广播查询消息，邻居节点再向自己的所有邻居节点广播， 就这样向外洪泛扩张。这种模型本身因为采用应用层广播的协议，导致消息量 过大，网络负担过重，使得性能较差的节点很快就成为整个系统的瓶颈；但是 这种方法具有节点覆盖率高，健壮性好以及实现简单的优点，更重要的是搜索 时理论上可以使用任何的匹配方法，例如基于关键字的全文搜索，只要各个节 点将本节点满足搜索请求的结果返回给请求的源节点即可。算法方面新近提出 的方法有迭代加深技术( i t e r a t i v ed e e p e n i n g ) 1 4 范围扩张( e x p a n d i n gr i n g ) 5 1 本 地索引方法( l o c a li n d e x ) 6 1 、最大聚集度优先法1 7 l 、随机游走搜索方法( r a n d o m w a l k ) 1 5 j 等。 c h o r d 【引，c a n 【9 1 ，t a p e s t r y i 嘲，p a s t r y i 1 l 等采用分布式散列表( d h t ， d i s t r i b u t e dh a s ht a b l e ) 的方法来实现资源的搜索，这类系统又称为结构化的p 2 p 系统。这类系统对各共享资源的标识进行散列，将所有共享资源映射到一个散 列空间，并且对各个节点也进行相同的散列，将所有节点也映射到同样的散列 空间。从而在资源和节点之间建立一种对应关系。在用户给定一个资源的标识 2 硕士学位论文第一章绪论 后，对该标识进行散列就可以快速而准确地定位到负责该资源的节点。但在这 类p 2 p 系统中，如果不知道要访问资源的标识，将无法定位和访问该资源。因 此从本质上说，这样的p 2 p 系统只是在资源标识与资源位置之间的一种映射， 并不真正具有搜索功能：另方面，由于网络中资源的多样性和资源本身的复 杂性，仅仅用一个标识很难去标识一个资源。由于不支持复杂查询，严重制约 了这种搜索方法的发展。 混合式p 2 p 网络主要是提出了超级节点的概念，利用超级节点作为高速转 发层来进行搜索，典型的有k a z a a 【1 2 】。 语义覆盖网络( s e m a n t i co v e d a yn e t w o r k s ，s o n s ) 的概念在文献【1 3 中第一次 提出，所谓语义覆盖网，指的是将内容语义上较为相似的对等体聚集在一起， 形成一个小范围网络。当进行查询时，将与查询内容相似的对等体选择出来作 为邻居对等体，其代表有n u e r o g r i d l l 4 】等。p s e a r c h i ”l 是一个高效的信息检索系 统，支持基于语义的全文搜索。它主要是扩展了传统i r ( i n f o r m a t i o nr e t r i e v a l ) 算 法：向量空间模型( v e c t o rs p a c em o d a l ，v s m ) 和潜在语义索引( l a t e n ts e m a n t i c i n d e x ，l s i ) ，使其适用基于d h t 的p 2 p 网络结构。因此该系统既具有d h t 系 统的高度可扩展性，又有r j 算法的准确性。p s e a r c h 不仅利用v s m 实现了语义 查询，而且通过改造的l s 工算法有效的消除了v s m 算法所带来的同义、多义 的问题。e d u t e l l a t l 6 j 是一个基于元数据的p 2 p 通用搜索框架，共享元数据都是 r d f l l 7 】格式。该框架的r d f 查询语言和基于r d f 的元数据模型可以支持多种已 开发的r d f 查询。 在p 2 p 网络中，每个节点都表现出某些可以捕捉到的兴趣，相近兴趣的节点 保存的内容和提交的查询也相近。通过挖掘每个节点的兴趣，把节点按照兴趣 关系组成网络，使得兴趣相近的节点在网络中比较近。目前主要是按照用户提 交的检索行为来划分用户兴趣的，文献【1 8 】中揭露了这种按兴趣组成的网络表现 出和社会网络相近的所谓“小世界( s m a l l w o r l d ) ”特性，其用于提高检索效率是有 效的。但这类研究没有充分挖掘节点共享内容所体现的节点兴趣，用户提交的 查询只反映用户共享兴趣的一个部分，尤其对于提供大量信息的节点，所产生 的查询只是反映其存储内容一个很小的子集，因此需要去挖掘其共享内容所反 映的兴趣，从而使得网络中其他节点在需要时能够高效地检索这些内容。在p 2 p 全文信息检索中这个问题更加突出，因为用户提出的查询词的尺度远远小于共 享的信息的尺度，查询所反映的共享兴趣就更有限了。研究提出【l9 】通过节点共 享的内容来挖掘节点的兴趣。它使用类似于分布式检索的方法，由代理节点定 期采集各个共享节点共享的内容索引，然后通过聚类的方法把这些索引分成若 干话题区域，每个节点属于一、两个区域，每次查询通过计算查询和各个话题 3 硕士学位论文第一章绪论 区域中心的距离来判断该查询所属的区域，路由查询时先路由到该查询所属的 目标区域，然后再在目标区域中进行广播。这种方法的不足之处在于代理节点 负担沉重，而且共享的内容很难确定地划分为独立的区域，因为每个节点往往 属于多个t o p i c s 。 1 3 研究内容和本文结构安排 本文研究了非结构化分散型p 2 p 网络的特点以及搜索机制，构建了一种基 于兴趣相关度的逻辑超节点网络模型，并在此基础上提出了优化算法和改进技 术。 本文共分6 章，第一章绪论，介绍了课题研究背景和国内外研究现状；第 二章简要介绍了本文的技术基础p 2 p 网络的相关概念、分类以及特点；第三 章介绍了本文所涉及到的关键技术，以及根据p 2 p 网络节点共享内容的兴趣相 关度，构建一种包含逻辑结构超节点和普通节点的网络模型；第四章详细描述 了基于本文所构建的网络模型的搜索策略，并从实验角度对搜索策略的性能进 行了比较分析；第五章主要是根据本文研究成果，设计了一个原形系统，简单 模拟了一个具体有搜索、下载功能的p 2 p 系统；第六章对本文的工作进行总结， 并提出了下一步工作的方向。 4 硕士学位论文第二章p 2 p 网络概述及搜索技术 第二章p 2 p 网络概述及搜索技术 p 2 p 网络模型与客户服务器( c s ) 模型有较大差别，且不同结构的p 2 p 网 络之间有较大的区别。各种模型各有优缺点，针对不同类别的p 2 p 网络，研究 方向与手法也不尽相同。本章简单介绍了p 2 p 网络的相关概念，着重描述了非 结构化的p 2 p 网络模型，为下一章作理论基础上的铺垫。 2 1 p 2 p 网络简介 点对点( p 2 p ) 网络并不是新概念，上世纪7 0 年代i n t e r n e t 出现以来它就存 在了。互联网最基本的t c p i p 并没有服务器和客户机的概念，所有的网络设备 都是平等的，互联网上的任何系统都具有服务器和客户机的功能。然而，受到 早期计算机性能、资源等因素的限制，大多数普通互联网用户没有能力提供网 络服务，因此逐渐形成了客户服务器架构。在这种架构下，用户可以以低廉的 成本方便的访问互联网，推动了互联网的普及。然而，随着互联网同益深入到 大众的生活中，人们需要更直接广泛的信息交流，近年来，技术上的变化和个 人计算机计算能力的提高使这一需求具备了实现的可能性，并为p 2 p 带来了大 范围的复兴。一个著名的p 2 p 应用就是n a p s t e r 。n a p s t e r 为用户提供了m p 3 音 乐文件的共享平台，它使得用户可以在网络上共享自己硬盘中的m p 3 文件，也 可以搜索其他用户共享的m p 3 文件并下载。n a p s t e r 的p 2 p 特性使得它在短时间 里就吸引了5 0 0 0 万用户。随着n a p s t e r 的成功，各种p 2 p 应用纷至沓来，这些 应用使用户可以通过p 2 p 网络共享数据和计算资源以及进行实时通信。 总的来说，p 2 p 网络具有这些基本特点：分散性。p 2 p 系统将信息的载体 和传送信息的带宽分布到了网络中节点上，信息传输和服务直接在节点之间进 行，无须中间环节的介入；健壮性。由于分散性的特点，服务器的角色在网 络中被淡化或消除了，因此单点故障不会给系统稳定性和服务质量带来影响。 可扩展性。p 2 p 网络中的节点拥有双重角色：它们既是服务器也是客户端，节 点向其他节点请求服务也响应其他节点的请求。因此p 2 p 网络可以通过集合更 多的节点来扩充网络规模，资源和服务能力而不需要c s 架构中的高性能服务 器【1 3 l 。 5 硕十学位论文第二章p 2 p 网络概述及搜索技术 2 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 网络。 2 2 1 集中目录式p 2 p 网络结构及其搜索技术 集中式网络结构中使用了中央服务器来实现一些管理。所有的节点需要登 陆中央服务器注册节点和共享资源的信息。资源搜索请求也被发送到服务器， 服务器若找到资源，则告知请求节点直接从拥有资源的对等节点上直接下载， 此时服务器不再参与。当节点的资源发生变化时，比如资源的增加，修改，删 除等，索引服务器将到更新消息，并据此修改服务器缓存的资源索引信息。这 种结构查询信息和更消息只在服务器和节点之问传播。如图2 1 【6 l j 所示： 服务器 图2 - 1 集中式结构 n a p s t e r 就是最早的据此建立起来的第一代p 2 p 系统。中央索引服务器保存 所有n a p s t e r 用户上传的音乐文件索引和存放位置的信息，当某个用户需要某个 音乐文件时，首先连接到n a p s t e r 中央索引服务器，在服务器上进行检索，服务 器返回存有该文件的用户信息，再由请求者直接连到文件的所有者传输文件。 n a p s t e r 首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带 宽消耗，减少了系统的文件传输延时。 集中式p 2 p 搜索技术的优点： 查询效率高，查询算法灵活多变并能够实现复杂查询。 对等体负载低，处理消息量少。 6 硕十学位论文 第二章p 2 p 网络概述及搜索技术 系统可维护性好。 缺点： 对索引服务器的处理能力和带宽的要求很高。 对索引服务器的安全性要求比较高，易受d o s ( 拒绝服务攻击) 等攻击瘫 痪。 随着网络规模的不断扩大，维护成本将会变高。 索引服务器容易引起版权问题的纠纷。 综合上述的优缺点，这种网络的搜索形式只势，但是由于上述的缺点，这 种形式不适合大型网络使用。 2 2 2 全分布式非结构化p 2 p 网络及其搜索技术 全分布式非结构化p 2 p 网络结构完全不设置中央服务器，查询以泛洪方式在 网络中传播，收到查询消息的节点首先查找本地文件，然后把结果发送至查询 节点。这种网络结构在查询过程中会产生很多查询消息，但是此结构具有容错 性，可用性好。该搜索技术主要采取的是泛洪( f l o o d i n g ) 。非结构化p 2 p 网络的 典型代表就是g n u t e l l a ，g n u t e l l a 采取的是基于随机图的泛洪算法。f l o o d i n g 的 工作流程：当一台计算机要下载一个文件，它首先以文件名或者关键字生成一 个查询，并把这个查询发送给与它相连的所有计算机，这些计算机如果存在这 个文件，则与查询的机器建立连接，如果不存在这个文件，则继续在自己相邻 的计算机之间转发这个查询，直到找到文件为止。为了控制搜索消息不至于永 远这样传递下去，一般通过t t l ( t i m et ol i v e ) 机制来控制查询的深度。随着联 网节点的不断增多，网络规模不断扩大，通过这种f l o o d i n g 方式定位对等点的 方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过 载而失效。所以，后来许多研究人员在f l o o d i n g 的基础上作了许多改进。算法 方面新近提出的方法有迭代泛洪方法( i t e r a t i v ef l o o d i n g ) 、本地索引方法( l o c a l i n d e x ) 、随机游走搜索方法( r a n d o mw a l k ) 以及基于移动a g e n t 的搜索方法等。 另外一类改进方法是在搜索中采用某些启发式策略和统计的信息，如选择 最近返回结果最多的邻居，或者是根据路由索引选择可以到达目标文件节点的 邻居等等。算法利用各种信息指导节点选择更有可能共享请求资源或找到资源 的节点转发定位请求信息，可以达到减少网络中查询消息流量的目的。启发式 搜索包括：有指导的b f s t l 8 1 ( d i r e c t e db f s ) 、智能b f s 【6 ( i n t e l l i g e n tb f s ) 、路由 索引1 2 0 1 ( r o u t i n gi n d i c e s ) 、自适应概率搜索【2 1 1 ( a d a p t i v ep r o b a b i l i s t i cs e a r c h ，a p s ) 等。如图2 2 1 6 l j 所示： 7 硕士学位论文 第二章p 2 p 网络概述及搜索技术 图2 - 2 分散式结构 2 2 3 全分布式结构化p 2 p 网络及其搜索技术 全分布式结构化p 2 p 网络采用分布式哈希表【2 2 l ( d i s t r i b u t e dh a s h ，t a b l e 简称 d h t ) 结构，起源于s d d s l 2 3 1 ( s c a l a b l ed i s t r i b u t ed a t as t r u c t u r e ) 研究，使用分布式 哈希表索引对资源和节点进行搜索。首先将正搜索空间对应到一个散y 1 ( h a s h ) 空间，并且对各个节点( 基于节点的l p 地址) 也进行相应散列，每个节点各负责 一部分散列空间。当一个节点发布一个资源( 例如文件) ，需要对该资源的唯一标 识( 如文件名) 进行散列，而根据该散列值可以确定负责管理该资源的节点。当一 个节点要搜索该资源时，同样对该资源的唯一标识使用相同的散列函数进行散 列得到散列值，通过有效地局部路由，找到负责该资源的节点从而可以找到要 搜索的资源。在这类系统中，赋给每个节点的区域是动态的，依赖于每个时候 加入和离开网络的节点数量。 d h t 类结构能够自适应节点的动态加入或退出，有着良好的可扩展性、鲁 棒性、节点i d 分配的均匀性和自组织能力。由于覆盖网络采用了确定性拓扑结 构，d h t 可以提供精确的资源节点发现。经典的d h t 类结构的案例是t a p e s t r y ， p a s t r y ，c a n 和c h o r d 。 采用分布式p 2 p 网络模式的软件通常也被称为第二代p 2 p 。分布式p 2 p 网 络模式摆脱了集中式p 2 p 网络模式由于中央索引服务器而带来的系统鲁棒性问 题，但是其仍然存在一些弊端。主要表现在以下几个方面：由于对等节点的不 稳定性和分散性，分布式p 2 p 网络模式下的资源查询往往难以对查询的全局性 ( 搜索应能覆盖整个p 2 p 网络而不存在查询盲区) 、准确性、灵活性、可扩展性 做到兼顾。 2 2 4 混合式p 2 p 网络结构及其搜索技术 8 、x 一 昌、，、，盛 硕士学位论文 第二章p 2 p 网络概述及搜索技术 混合式结构是以上两种结构的结合体，目的是继承两者的优点。通过引入 超级节点( s u p e r - p e e r ) ，混合式结构既有集中式的特点又有分散式的特点。超级 节点成为与其相邻节点的服务器，就学集中式结构一样，超级节点完成这些节 点的注册与查询工作。超级节点又通过完全分布式结构连接起来。混合式结构 在控制层面引入了两层：一层是普通节点通过c s 模式连接到超级节点；另一 层是超级节点通过完全分布式无结构网络连接到一起。这种结构的代表应用是 其代表就是k a z a a 。如图2 3 所示： 走召级节点 图2 - 3 混合式结构 混合式p 2 p 网络搜索的优点是性能、可扩展性较好，较容易管理，但对超 级节点依赖性大，易于受到攻击，容错性也受到影响，实现上比较困难，为了 能够利用这种模式的优点，需要提供能够有效组织对等体间关系的搜索网络， 这里所说的组织关系，包括超级节点间的组织模式、客户对等体与超级节点间 的组织模式、超级节点间的负载平衡等。 2 3 本章小结 本章介绍了p 2 p 及其特点，分别描述了两大类四种结构p 2 p 网络的基本工 作原理和优缺点。非结构化p 2 p 网络是本章介绍的重点，因为非结构化p 2 p 网 络是本文的研究对象( 后续章节中如出现“p 2 p 网络”字样，无特别说明均指非 结构化p 2 p 网络) 。 9 硕士学位论文第三章基于兴趣相关度的p 2 p 网络模型 第三章基于兴趣相关度的p 2 p 网络模型 全分布式非结构化p 2 p 网络中的搜索是一种广播式的搜索，如g n u t e l l a 。网 络中的节点收到查询以后不仅进行本地搜索，而且将查询发送到除查询消息来 源节点以外的所有邻居节点。搜索范围由t i m et ol i v e ( t t l ) 决定。广播式的 查询比较简单，当t t l 取值适当时，查询具有很高的查全率，能满足用户的查 询需求。但是由于采用广播的方式转发查询，容易造成查询洪流，引起网络拥 塞，降低p 2 p 网络的性能。 在本系统中，每个节点都可以看作是一个独立的信息检索系统，采用传统 的信息检索方法完成本地节点的搜索任务。为了支持语义丰富的信息检索，同 时也为了方便对检索结果排序，本文使用空间向量模型对本系统中的共享文档 进行描述，用向量的形式表示文档。由于该模型把文档以向量的形式定义到实 数域中，因而具有较强的可计算性和可操作性。同时，考虑到p 2 p 网络结构的 动态性，构造了基于语义的动态超节点的d s sp 2 p 网络模型，根据节点间的兴 趣相关度逐步聚集语义相似的节点集，拥有一定数量的节点荣升为逻辑超节点， 并具有一定的语义域。搜索请求首先在语义域中传播，可大大提高搜索效率， 减小网络流量。同时，根据历史成功搜索记录更新朋友信息，以减少缓存对象 替换的频率，提高搜索效率。而本文的优化算法适应于动态的p 2 p 网络，在查 询中能够获得相同的优化效果。 另外，系统根据节点群的大小动态设置逻辑超节点。从整体上来看，该网 络模型可以抽象为两个层次，上层为超节点组成的超节点域，在超节点域中， 超节点采用完全分布式的结构；下层为普通节点组成的语义域，普通节点也采 用完全分布式的结构，但是普通节点也都在查询过程中逐步聚集兴趣相关的节 点，超过一定阈值就荣升为超节点。逻辑超节点一般来说是数据资源丰富的节 点，它是在搜索过程中动态建立的，是逻辑上的概念。 针对如何在提高纯p 2 p 网络查询性能的同时保证查询效率这一问题，本文提 出的d s sp 2 p 网络除了继承了传统超级节点网络的优点之外，又对之进行了改 进，在一定程度上弥补了传统超级节点网络的不足，使得查询请求在小范围节 点上传播就可以获得足够的信息资源。大幅度降低了网络带宽消耗，同时也保 证了一定的查全率，从而提高了系统的搜索效率。 1 0 硕十学位论文第三章基于兴趣相关度的p 2 p 网络模犁 3 1 文档