（通信与信息系统专业论文）基于语义的对等网资源搜索技术研究.pdf

基于语义的对等网资源搜索技术研究 摘要 基于分布式散列表( d h t ) 的技术是目前p 2 p 网络的主要实现方式之一。 d h t 可以提供信息的精确匹配查询，但是无法支持内容、语义等复杂查询，从 而给用户的信息检索带来了极大的不便。如何在现有的0 p e n d h t 网络上，解决 精确匹配查询和内容语义检索之间的矛盾，成为了现阶段网络结构以及内容语义 搜索研究的一项新兴课题。本文设计并实现了构建于d h t 网络之上的语义资源搜 索系统。 本系统能够完成将相似文档发布到语义相近的节点，同时完成对相似文档的 搜索。我们希望借此对基于对等网络的搜索进行研究分析以及改进，改善用户的 搜索体验。 本文研究重点包括： 一、研究了当前主流的全分布式结构化对等网络技术，着重分析了d h t 网络 在精确匹配查询和内容语义检索之间的矛盾，进而提出在d h t 对等网上建立基于 语义的信息搜索系统。 二、提出基于文档关联度的语义搜索算法。它是应用在d h t 网络内容搜索的 一个创新算法。首先它不是对关键字的搜索，而是针对相似文档的搜索；其次， 它假设文档的意思是由某个或某些词的出现与否及它们出现的频率决定的，使用 统计学的方法，根据文档中单词之间的关系，达到概念匹配的目的。 三、为了配合我们的语义搜索算法，将d h t 改造成语义对等网。研究了如何 对节点标识符空间进行了语义划分，改变文档信息与d h t 节点标识符的映射关 系，实现了语义节点的聚合。 关键字：搜索技术，语义，p 2 p ，对等网，文档关联度，d h t 中图分类号： r p 3 v 基于语义的对等网资源搜索技术研究 a b s t r a c t d h tt e c h n o l o g yi so n eo ft h em a i nr e a l i z a t i o nm e t h o d so fp 2 pa tp r e s e n t d h tp r o v i d e sp r e c i s em a t c h i n go fi n f o r m a t i o n ，b u ti tc a n ts u p p o r tc o n t e n t o rs e m a n t i c m e a n i n go ro t h e rc o m p l e xs e a r c h ，w h i c hb r i n g sg r e a t i n c o n v e n i e n c et ou s e r s i n f o r m a t i o ns e a r c h h o wt os o l v et h ec o n f l i c t s b e t w e e np r e c i s em a t c h i n ga n ds e m a n t i cs e a r c hh a sb e c o m ean e ws u b j e c ti n t h er e s e a r c ho ft h en e t w o r ks t r u c t u r ea n ds e m a n t i cs e a r c h t h et h e s i s d e s i g n sa n dr e a l i z e ss e m a n t i cs e a r c hs y s t e mb a s e do nd h t 。 t h es y s t e mc a np u b l i s hr e s e m b l ed o c u m e n t st or e s e m b l en o d e so n s e m a n t i c sa n dc o n d u c ts e a r c ho nr e s e m b l ed o c u m e n t sa tt h es a m et i m e w e h o p et os t u d y ，a n a l y z ea n di m p r o v ep 2 ps e a r c hb ym e a n so ft h es y s t e m , a n d m a k eu s e r sf e e lb e t t e ri nt h es e a r c hc o u r s e a r e a so fr e s e a r c hi n t e r e s t s ： 1 t h i sc h a p t e r a n a l y z e st h em a i nd i s t r i b u t e dn e t w o r k si nu s e ， e s p e c i a l l yt h ec o n f l i c t sb e t w e e np r e c i s em a t c h i n ga n ds e m a n t i cs e a r c ho f d h tn e t w o r k s a f t e rt h ea n a l y s i s ，an e wi n f o r m a t i o ns e a r c hs y s t e mb a s e d o ns e m a n t i cm e a n i n gi sp u tf o r w o r d 2 as e m a n t i cs e a r c ha l g o r i t h mb a s e do nd o c u m e n tr e l a v a n c yi sp r o p o s e d i t i sac r e a t i v ea l g o r i t h mu s e di nc o n t e n ts e a r c ho fd h t f i r s t l y i t f o c u s e so nt h es e a r c ho fr e s e m b l ed o c u m e n t si n s t e a do fd i s t i n c tk e y w o r d s o n l y s e c o n d l y ，i ts u p p o s e st h ed o c u m e n tm e a n i n gi sd e c i d e db yt h e a p p e a r a n c eo fs o m ew o r d sa n dt h e i rf r e q u e n c y ，a n dt h e ng e t st ot h eg o a l o fc o n c e p tm a t c h i n gu s i n gs t a t i s t i cm e t h o d sa c c o r d i n gt ot h er e l a t i o no f w o r d si nad o c u m e n t 3 w et r a n s f o r md h ti n t os e m a n t i cp 2 pi no r d e rt oc o o p e r a t ew i t ho u r s e m a n t i cs e a r c h i n ga l g o r i t h m t h et h e s i sa l s oa n a l y z e sh o wt op a r t i t i o n n o d e s i d e n t i f i e rs p a c es e m a n t i c a l l y ，h o wt oc h a n g em a p p i n gr e l a t i o n b e t w e e nd o c u m e n ti n f o r m a t i o na n dn o d e s i d e n t i f i e ra n dh o wt or e a l i z e s e m a n t i cn o d e s a g g r e g a t i o n k e y w o r d s ：s e a r c ht e c h n o l o g y , s e m a n t i c s p 2 pn e t w o r k , d o c u m e n tr e l e v a n c y , d h t c l c ：t p 3 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：童纽日期：j 銎丑：! ：2 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 延交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：量盔缝导师签名 日期：型：! ：! 基于语义的对等网资源搜索技术研究 1 1 研究背景及意义 第一章绪论 互联网的迅速发展和广泛普及导致网上信息爆炸性增长。据权威机构统计， 网上约有数十亿的网页，甚至有些专家宣称网页总数已达5 5 0 0 亿，这一数字仍 然在不断的快速增长。如何在庞大的互联网上获得有价值的信息已成为人们日益 关注的问题。搜索技术的出现为人们快速找到所需信息带来了福音。搜索引擎是 种用于帮助因特网用户查询信息的搜索工具，它以一定的策略在互联网中搜 集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务， 从而起到信息导航的目的。传统的网络中，c s ( c l i e n t s e r v e r ) 结构是构成网络 的主体。在这种结构下，随着用户数量的增加，服务器的负载也随之迅速增加， 甚至达到了不堪重负的地步。 针对这种状况，如何分散服务器的计算工作以及充分利用网络的计算能力成 为了网络发展的一个方向。近些年来，对等网络( p e e r t o p e e r ，简称p 2 p ) 迅 速发展并得到了大规模的应用。在对等网中，网络的计算工作被分布到网间的每 台计算机中。因此整个网络的计算能力得到了充分的利用。并且，随着网络用 户数量的增长，网络的整体计算能力也会随之得到加强，于是客户端数量增长和 服务器计算能力有限的矛盾得到了完善的解决。 从目前的应用来看，p 2 p 的威力主要体现在大范围的共享、搜索的优势上。 开发出强大的搜索工具是p 2 p 技术的一个优势。p 2 p 技术使用户能够深度搜索 文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿主设 各的限制，可达到传统c s 结构的搜索引擎( 只能搜索到2 0 - 3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有开放的信息资源) 以p 2 p 技术发 展先锋g - n u t e l l a 进行的搜索为例：一台p c 机上的g n u t e l l a 软件可将用户的搜索 请求同时发给网络上另外1 0 台p c ，如果搜索请求未得到满足，这1 0 台p c 中 的每一台都会把该搜索请求转发给另外l o 台p c ，这样搜索范围将在几秒钟内以 几何系数增长，几分钟内就可以搜遍几百万台p c 上的资源。 传统的全文检索系统在网络信息检索中最大的问题就是检索模式单一、表面 化，仅用单一的词或词的组合来对网络式结构的知识进行检索，缺乏对知识的理 解和处理，其结果是返回的匹配网页数目过多，起不到真正的信息检索的作用。 语义检索是把信息检索与人工智能技术、自然语言处理技术相结合的检索，能够 较好地解决传统全文检索中关键词词问关系模糊、查准率低的问题。语义检索立 基于语义的对等网资源搜索技术研究 足于对原文信息进行语义层次上的分析和理解，根据对用户提问的理解来检索知 识库中相关的信息以提供结果。 基于分布式散列表( d h t ) 的技术是目前p 2 p 网络的主要实现方式之一。在d h t 网络中，每一个数据资源都有一个全局i d 。通3 生h a s h 算法，网络可以迅速定位到 资源所在的节点，而并不借助中心服务器的计算能力。d h t 可以提供信息的精确 匹配查询，但是无法支持内容、语义等复杂查询，从而对用户的信息检索带来了 极大的不便。本文所讨论的基于对等网的语义搜索算法就是应用在d h t 网络模型 中解决内容语义检索的一个创新算法。它假设文档的意思是由某个或某些词的出 现与否及它们出现的频率决定的，不以分离的单词作为处理对象，使用统计学的 方法，根据文档中单词之间的关系，达到概念匹配的目的。 1 2p 2 p 资源搜索方面的研究进展 前人对p 2 p 资源搜索进行了很多有意义的研究【4 l 】【4 2 】【4 3 】【4 5 】【4 8 】【5 l 】。 g n u t d l a 1 网络模型被认为是完全分布式p 2 p 系统的代表，目前研究和改进基 于g n u t c l l a 网络的资源查找机制的方式有以下4 种：( 1 ) 智能化的选择进行查 询的节点，只向被选择的节点发送查询消息的方式，如定向广度优先搜索方法； ( 2 ) 提高网络的冗余的方式，如预先复制文件法：( 3 ) 网络节点建立索引的方 式，如本地索引法；( 4 ) 利用特有的网络结构的方式。如最大聚集度优先法。这 些方式可以单独使用，也可以相互结合使用来提高查询效率。 由于g - n u t e u a 的网络拓扑没有严格的控制，对等体可以随意加入或离开，再 加上不存在中央服务器存储资源索引项，数据存储的位置不容易精确的定位。资 源的搜索是通过将查询请求广播到所有对等体来完成的。这种松散式的结构容易 支持关键字的查询，但缺点也很明显，搜索效率以及查询范围有限。为此，人们 又提出了很多改进方案，大大提高了搜索效率。b e v e r l yy a n g 和h e c t o r g a r c i a - m o l i n a 提出了迭代深入方法( i t e r a t i v ed e e p e n i n g ) 、定向广度优先搜索 ( d c t e db f s ) f 2 】，黄道颖等研究了可选择的查询分配方法，使用多路平行 查询机制进行查询【3 】，v a n ak a l o g e r a k i 等提出了一个智能化的搜索机制 4 】。迭 代加深技术的思路是逐步增加发生的对等体数，直到请求得到响应。所谓广度优 先遍历是从源点邻居中选择一部分发送查询请求，这种改变广播策略的方法，大 大减少了涉及的对等体数。e c o h e n 等提出预先复制其他节点的共享文件，在 网络中形成高度的冗余，提高查询效果的方法【5 】。b ，y a n g 等研究了将智能化 选择网络节点和提高节点冗余这两种机制结合起来的方法 6 】。i a d a m i c 和 a 。c r e s p o 等研究了网络节点提出路由索引( r o u t i n gi n d i c e s ) 的方法 7 】【8 】，它 利用分布式索引返回一个邻居列表，这些邻居对等体根据它们对请求的贡献程度 基于语义的对等网资源搜索技术研究 排序，这样请求就可以转发给最可能响应该请求的对等体。l a d a m i c 等和黄道 颖等研究了利用网络的幂规律和小群体的特点提高查询性能的方法【6 】【9 】【lo 】。 c h o r d 1 2 ，c a n l 3 等是结构化的p 2 p 网络资源搜索系统的代表。在这些 系统中网络拓扑以及对等体的位置都有严格的控制，搜索机制是利用分布式哈希 表( d i s t r i b u t e d h a s h t a b l e ，d h t ) 将请求发送到目标对等体。在研究初始阶段， 这些系统都是通过文件的唯一标识符作为搜索键值( k e y ) 来查找文件的，因此 不支持关键字的查询。后来人们对此进行了改进，对关键字以及模糊查询都予以 了支持。 语义覆盖网络( s e m a n t i co v e r l a yn e t w o r k s ，s o n s ) 的概念在文献【1 4 】中第一 次提出，所谓语义覆盖网，指的是将内容语义上较为相似的对等体聚集在一起， 形成一个小范围网络。当进行查询时，将与查询内容相似的对等体选择出来作为 邻居对等体，其代表有n e u r o g r i d 1 5 等。s 0 n 主要提高c m u t e l l a 这类系统的性 能，在召回率相同的情况下，发送的消息数明显减少，未涉及比较精确的语义搜 索，以及排序算法。 文献 1 6 1 基于c a n 提出了p c , r o u p 语义对等网的构造方法，提出的节点 加入算法能使节点快速地加入到相应的s p n 中，并且构造的s p n 能够适应节 点内容不断变化以及节点不断加入、离开和故障等事件的发生；针对用户的查询 行为，提出了直接组扩散算法d o f 、随机组扩散算法r g f 和预测组扩散算法 p o f 。并基于b l o o m 过滤器通过简单的分布式算法构造了p e e r 组过滤器，利 用增大的背景来改进r g f 算法。这些算法假定文档分类器和查询分类器可以由 信息检索和数据挖掘领域中成熟的分类算法来实现，也可以让用户在安装p 2 p 软件时自己对文档分类，查询时提交文档类别。 文献1 7 针对g n u t e l l a 类型的p 2 p 网络不能进行大规模扩展问题，提出 了一个p 2 p 网络模型，该模型通过p 2 p 网络的动态和实时搜索功能来提高语 义w e b 服务能力。该文构建了一个超立方体h y p e r c u p 的p 2 p 拓扑网络结构， 并通过通用的本体概念将网络拓扑分割为概念聚类。该聚类能够进行特定的查 询，使得网络能够应答由本体概念组成的查询请求。该算法通过语义w e b 服务 使用本体来描述其功能，适合于配置大型的动态网络。但是，超立方体的构造较 复杂，因而对节点的开销比传统的非语义方法大。 文献【1 8 】基于p 2 p 结构构建了一个开放式超媒体系统d d l s ( d i s t r i b u t e d d y n a m i cl i n ks e r v i c e ) ，它是一个补充的超媒体服务，根据该服务，客户可以查 询一组链接库。通过将链接库和链接服务组件分布到节点当中，d d l s 使得多 个想共享连接资源的用户能够进行连接解析和链接库通信服务。链按库在本地进 行维护，带有最小限制来提供数据灵活性；该库通过r d f ( r e s o u r c ed e f i n i t i o n 6 基于语义的对等网资源搜索技术研究 f r a m e w o r k ) 将信息编码，成为与元数据相关联的三元组集合，并在语义基础上 进行语义搜索。 此外，p s e a r c h 【1 9 】是一个高效的信息检索系统，支持基于语义的全文搜索。 它主要是扩展了传统的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 r s p a c em o d a l ，v s m ) 和潜在语义索引( l a t e n ts e m a n t i ci n d e x ，l s i ) ，使其适用 基于d h t 的p 2 p 网络结构。因此该系统既具有d h t 系统的高度可扩展性， 又有双算法的准确性。p s e a r c h 不仅利用v s m 实现了语义查询，而且通过改 造的l s i 算法有效的消除了v s m 算法所带来的同义、多义的问题。e d u t e l l a 1 2 是一个基于元数据的p 2 p 通用搜索框架，共享元数据都是r d f 格式。该框架 的r d f 查询语言和基于r d f 的元数据模型可以支持多种已开发的r d f 查询。 1 3 本文主要工作及论文结构 在整个语义对等网系统的设计实现过程中，作者全程参与了系统的实现，主 要负责语义方面的实现。其间，作者进行了大量的理论研究以及实验测试，确定 了系统的理论基础并取得了大量的实验数据，并开发了包括基于文档关联度语义 搜索系统算法部分，语义特征算法部分等核心模块。目前，系统已基本开发完成， 正在试运行之中。 在系统的设计与开发中，作者完成的具体工作有： 1 根据文档的统计特征，设计并实现了基于文档关联度的语义搜索算法， 根据该算法，系统能够实现对相似文档的查询，并根据语义距离返回 结果列表。 2 为了解决d h t 系统与语义查询的矛盾，对节点标识符进行了语义划分， 实现了语义节点的聚合。 通过大量的理论研究和实际工作，作者在基于对等网的内容语义搜索技术领 域取得了一定的经验以及研究成果。本文便是对于这些经验以及研究成果的总 结。 本论文分六章叙述： 第一章、绪论 阐述了当前对等网领域的研究现状，分析了在对等网中实现语义搜索的意义 及当前存在的问题。该章内容对文章的总体目标以及研究方向进行了阐述，列举 了作者在该研究方向中所涉及的领域。 第二章、p 2 p 概述 7 基于语义的对等网资源搜索技术研究 本章对全文所涉及到技术领域的背景知识进行了系统的介绍。其中包括p 2 p 文件共享结构，结构化d h t 系统的路由算法，p 2 p 网络信息检索模型的现状研究 及这些方法存在的问题，提出了目前存在的语义查询和d h t 系统的矛盾。 第三章、p 2 p 资源搜索系统分析 提出了我们建立基于语义的p 2 p 资源搜索系统的设计目标，划分了系统的层 次，确定了核心功能模块的设计要求。 第四章、基于文档关联度的语义搜索算法 叙述了作者设计的应用于系统中的语义搜索算法一基于文档关联度的语 义搜索算法并对其性能进行了理论分析与实验验证。 第五章、基于语义的p 2 p 资源搜索系统实现 介绍了我们建立的基于语义的p 2 p 资源搜索系统详细的实现过程，首先描述 了系统总体架构、工作过程，然后阐述了各核心功能模块的实现，最后对整个系 统的性能给出了定性的评价。 第六章、总结与展望 本章是全文的最后一章。对已完成的工作进行了总结并提出了今后需进一步 研究的方向。 8 基于语义的对等网资源搜索技术研究 第二章p 2 p 概述 2 1p 2 p 概念及应用 o r a m 2 0 给p e e r t o p e e r ( p 2 p ) 下了一个简单的定义：p 2 p 是利用i n t e r n e t 边缘的存储、c p u 计算周期、内容及人力等资源的一组应用程序。因为访问这些 分布式的资源意味着需要运行在一个连接不稳定、i p 地址不可预测的环境下， 所以p 2 p 节点必须运行于d n s 之外并且具有自治的中央服务器。简言之，p 2 p 是 一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处理能力、 存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络提供服务和内 容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。现在，人们对p 2 p 的概念进行了扩展，如i b m 公司认为：p 2 p 系统由若干互联协作的计算机构成， 且至少具有如下特征之一：系统依存于边缘化( 非中央式服务器) 设备的主动协 作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中成员同时扮 演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在，构成一个虚 拟或实际的群体。 2 1 2 2 3 为了更清楚地理解p 2 p ，我们将p 2 p 模型与传统的c l i e n t s e r v e r 模型进 行了比较。在c l i e n t s e r v e r 模型中，节点要么是客户端要么是服务器，资源 ( 如存储或计算能力) 可以在客户端和服务器之间共享。c s 模型中的服务器实 际上是个中央控制点。在p 2 p 模型中，节点既是客户端又是服务器。作为客户 端，节点可以从其他节点( 对等体) 查询或下载它想要的对象，同时它又作为服 务器向其他节点提供对象。 根据生命周期，p 2 p 节点一般有四个阶段：加入、查询、下载和离开。首先， 一个刚刚到来的节点必须加入p 2 p 系统中。在这个阶段，它可以获得一些基本的 信息( 如其邻居节点的连接情况) 来启动，同时发布它所持有的信息。其次，节 点可以查询它想要的对象。p 2 p 定位协议将帮助该节点确定目的节点，而p 2 p 路由协议则将查询消息路由到目的节点。再次，如果查询成功( 通常返回目的节 点的i p 地址) ，节点可以直接从目的节点下载对象。最后，在理想的情况下，节 点会宣布它离开系统。因此，p 2 p 系统有三个重要的组成部分：邻居发现，定位 协议和路由协议。 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心从 中央服务器向网络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以建立p 2 p 9 基于语义的对等网资源搜索技术研究 对话。这使人们在i n t e r n e t 上的共享行为被提到了一个更高的层次，使人们以 更主动深刻的方式参与到网络中去。p 2 p 给互联网的分布、共享精神带来了无限 的遐想，有观点认为至少有1 0 0 种应用能被开发出来，但从目前的应用来看， p 2 p 的威力还主要体现在大范围的共享、搜索的优势上。从目前的应用来看，p 2 p 的应用主要有即时通信软件，如i c 0 等；实现共享文件资源的软件，如n a p s t e r 和g n u t e l l a 等；用于在网络上将存储对象分散存储的存储系统，如o c e a n s t o r e ： 协同计算软件，如n e t b a t c h 可连接几千或上万台p c ，利用其空闲时间进行协同 计算等等。 2 2p 2 p 文件共享结构分类 l 、按照集成度来区分，p 2 p 系统可以根据它们的集成度来进行分类，即系 统如何使用服务器在节点之间进行相互交互。通常可分为三类： ( 1 ) 纯分布式p 2 p 结构( 比如最初的c r n u t e l l a 结构) 在这种p 2 p 网络中所有的节点都既是服务器，又是客户端。它们在网络中 有着同等的作用，没有中心式的节点对它们之间的交互起协调作用。这些节点被 称为：“船r v e n t s ”( $ e w c i s + c l i e n t s ) 。 ( 2 ) 部分中心式的系统( 比如k a z a a ，m o u p h c u s 等) 这种系统的结构与纯分布式的系统一样，只是有些节点被认为比其它节点更 重要。这些节点上有其它节点上共享文件的索引。它们被叫做“s u p e m o d e s ( 超 级节点) ”。单个的超级节点不能组成一个p 2 p 网络，因为它们是被动态任命的， 万一它们被恶意的攻击，网络能够任命其它的节点作为新的超级节点来取代原有 的超级节点 ( 3 ) 混合式的分布式结构( 比如n a p s t e r ) 在这种网络中有一个中心服务器。进入网络的节点首先要以元数据的方式在 中- f i , 服务器上进行注册，中心服务器通过维护其他节点的元数据来方便节点之间 的交互。端到端的交互就是节点问的交互，这个中心服务器通过进行查找和确定 网络中拥有相关文件的节点来对节点间的交互提供便利。 显然在这种结构中，中心服务器是一个单一的故障点。技术故障和恶意攻击 容易使得服务器出现故障，从而失去使用这种p 2 p 结构的优势。这种系统并不 被认为是真正的p 2 p 系统，而是被认为是标准的c s 结构的范例，只不过在节 点间进行文件传输而已。 2 、按照系统是否建立覆盖网络结构来区分，结构化的p 2 p 系统由带有复杂 拓扑结构的高度动态的网络节点组成。这个拓扑结构建立了一个覆盖网络，它与 连接不同节点的物理网络无关。网络中的共享文件可以根据网络的拓扑结构进行 1 0 基于语义的对等网资源搜索技术研究 定位。p 2 p 系统根据是否建立了结构化或特殊的覆盖网来区分，可分为两类：非 结构化网络和结构化网络。 ( 1 ) 非结构化网络( 比如c m u t e l l a ) 在这种系统中文件的位置和覆盖网完全没有关系。因为节点没有相关文件的 信息进行文件定位，所以需要查询每个节点是否有与查询条件匹配的文件。非结 构化的p 2 p 系统中不需要建立覆盖网，这种结构的优点是网络具有很强的动态 性，节点可以随时离开和加入网络，缺点是查找到理想的文件需要进行大范围的 搜索。因为这个原因，非结构的p 2 p 系统被认为是可扩展性不强，可是现在正 在进行许多研究以增加非结构化系统的可扩展性。 ( 2 ) 结构化的网络( 比如c h o r d ，c a n ，p a s t r y 等等) 结构化网络的出现主要是解决非结构网络可扩展性差的问题。这些系统建立 覆盖网后，将文件放置在规定好的位置上，在文件标识符和文件位置之间建立了 一个映射，形成了一个分布式的哈希表，使得查询能够有效的定位到要查找的文 件。 结构化的系统对于精确查询提供了一个可扩展的方案，因为要查找的资料的 标识符是明确的。结构化系统的缺点是很难在具有高动态性的网络中( 如 g n u t e l l a 网络中节点加入、离开网络很频繁) 维持网络的结构。 ( 3 ) 松散结构的网络( 比如f r e e n e t ) 这种网络结构介于非结构的网络结构 和结构化网络结构之间。文件的定位有一些索引信息能够进行提示，但是这些索 引信息并没有规范，因此搜索的效果并不理想。 3 按照出现的先后时间和目的，现有p 2 p 网络可以分为三代： ( 1 ) 1 g 一第一代( f a s tg e n e r a t i o n ) 早期的p 2 p 网络如n a p s t e r 和g n u t e l l a ，它们比较简单，但是可扩展性差、 查询效率低。 ( 2 ) 2 g 一第二代( s e c o n dg e n e r a t i o n ) 第二代p 2 p 网络通常利用d h t 技术来实现较好的可扩展性和查询效率以及 负载平衡和确定性查找。如p l a x t o n 、p a s t r y 、c a n 、c h o r d 等。但是它们的适 应性和容错性不好，尤其在遭到恶意攻击的时候。 ( 3 ) 3 g 一第三代( t h i r dg e n e r a t i o n ) 最近提出的p 2 p 网络如l o w - d i a m e t e r ，b u t t e r f l y ，m u l t i - b u t t e r f l y ，可以提 供较高的适应性和容错性，常用的技术有对象复制，扩展节点问连接数以及一些 特殊的拓扑结构。 第二代和第三代p 2 p 网络通常是分布式、结构式的覆盖网。 基于语义的对等网资源搜索技术研究 2 3 结构化p 2 p 网络研究 由于结构化网络的可扩展性比较强，目前p 2 p 系统一般都采用结构化的组网 方式，所以研究在结构化p 2 p 的环境下进行资源搜索是p 2 p 相关研究中的热点也是 核心的问题。首先有必要对结构化网络的路由机制作一个介绍： 结构化网络指的是c a n 、t a p e s t r y 、c h o r d 、p a s t r y 之类的点对点网络。在 这类网络中。每个节点都有固定的编址，整个网络具有相对稳定而规则的拓扑结 构。 依赖拓扑结构，可以给网络的每个节点指定一个逻辑的地址，并把地址和节 点的位置对应起来。给定某个地址，拓扑结构保证只需要通过o ( 1 0 9 。n ) 跳就能路 由到具有相应地址的节点上去( 其中n 是网络中的节点数) 。结构化网络可以用来 有效地存储分布的信息，网络中存储的信息可以用 这个二元组来唯一 定位，其中k e y 是信息的索引，州是存储该信息的节点。 分布地存 储在结构化网络中，每个节点存储那些后e 瘌自己的地址相近的二元组。这样， 要查找某个索引为k e y 的信息，只需要路由到地址和k e y 相近的节点就可以获 得 的二元组，从而定位目标信息，就像我们平常在哈希表中查找数据 一样，所以称为分布式的哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 。 2 3 1d h t 中的路由协议 p a s t r y 2 1 1 【2 2 】是微软研究院提出的，基于d h t 的可扩展的分布式对象定位 和路由协议，可用于构建大规模p 2 p 系统。信息将根据其k e y 所计算的h a s h 值 被放在拥有最接近n o d e l d 的d h t 节点的上，快速定位资源的所在，方便路由阎 【2 3 】。 p a s t r y 有如下基本特性： 1 每个网络节点都有一个固定的1 2 8 位n o d e l d ，当收到一条含1 2 8 位k e y 的消 息时，节点能高效地将消息发送到在当前节点中，数值上n o d e i d 最接近k e y 的节点。在p a s t r y 网络中里，发送步骤的复杂度应该是0 ( i o g n ) 。在每个 p a s t r y 节点中，路由表要维护节点数量的复杂度是0 ( i o g n ) 。在消息传递经 过的每个p a s t r y 节点时，会通知回调函数，应用程序可以对这条消息做一 些处理。 基于语义的对等网资源搜索技术研究 2 每个p a s t r y 节点监视和它n o d e l d 值最接近的l 个节点( 这个集合叫作 l e a f s e t ，其中比当前节点n o d e i d 大及小的节点各占l 2 ) ，应用程序可以通 过回调知道l e a f s e t 中新节点的加入，节点的失效，节点的恢复。 3 p a s t r y 探寻消息传递的最小距离，比如以p i n g 的延时作为判断的依据。 p a s t r y 网络是分散的，灵活的，自组织的；当出现新节点，死节点，节点失 败时它会自动配置。 几个重要的参数： b ：一般取1 、2 、3 、4 。内部处理1 2 8 位i d 时用的进制为( 2 的b 次方) 。 l ：l e a fs e t 的容量，一般取( 2 的b 次方) 或( 2 的b + 1 次方) 。 m ：n e i g h b o r h o o ds e t 的容量，般取( 2 的b 次方) 或( 2 的b + 1 次方) 。 为表达方便，n 代表网络中存活的节点数。 节点需要维护的三种数据： 1 l e a fs e t 表： 容量为l ，用于保存在数值上最接近n o d e l d 的节点，其中s m a l l e r 和l a r g e r 各占一半。 2 路由表：( r o u t i n gt a b l e ) l o g 以( 2 的b 次方) 为底n 的对数行，每行( 2 的b 次方) 一l 条数据。第n 行 表示n o d e i d 与当前节点的前n 位相同，且第n + l 位与当前节点的不相同。 3 邻居表：( n e i g h b o r h o o ds e t ) 保存节点的直接邻居( 如p i n g 值最小的m 个节点) ，它不是用来路由消息的， 而是为配置网络服务的。 图1 ：路由索引表示意图 基于语义的对等网资源搜索技术研究 参照图1 中的左图：每个节点维持一个路由表。路由表里n o d e i d 换算成 2 b ( 缺省值1 6 ，b - = 4 ) 进制的数。举例说明，按1 6 进制，n o d e i d 为6 5 a l f c 8 3 ( 一共3 2 个数字，1 2 8 b i t ) 的节点，它的路由表中第一行填入的是这样的节点， 它们n o d e i d 的第一个数字为除6 以外的值，共1 5 个。第二行填入的节点，它们 n o d e i d 的第一个数字均为6 ，而第二个数字则为除5 以外的值，也是1 5 个。依 此类推，第三行的节点，n o d e i d 的第一个数字为6 ，第二个数字为5 ，第三个数 字为除a 以外的值。 另外每个节点还需要维持一个邻居表，表里是和本节点之间网络延迟最小的 一些节点。节点周期性的和邻居表里的节点交换信息，依此来更新路由表里的条 目。 路由原理：路由是靠l e a fs e t 和路由表，而邻居表是为维护路由表而存在 的。路由表负责路由消息到目的节点附近的某个范围，而l e a fs e t 则负责精确 地找到目的节点。 参照图1 中的右图：递归路由算法：如果6 5 a l f c 这个节点需要路由一个k e y 为d 4 6 a l c 消息到目的地，首先看第一个数字，去路由表里第一行找到数字为d 的节点，根据记录的i p 地址信息，把消息发送出去。收到消息的节点，比如说 是d 1 3 d a 3 ，由于n o d e l d 和消息的k e y 第一个数字相同，而第二个数字不同，那 么就去节点d 1 3 d a 3 的路由表中第二行找数字为l 的节点，也是发送出去。这样 每经过一跳，n o d e i d 都可以同目的节点最少接近4 b i t 。在节点数为n 的网络中， 平均来说，路由一个消息到任何一个目的节点所经过的跳数小于1 0 9 n ( b 是 一个影响路由表大小的配置参数，缺省为4 ) 。 p a s t r y 网络是以n o d e i d 在数值上相近作基础的，脱离了实际的网络，而以 数理上的i d 作为路由的算法的依据。 p a s t r y 能在无协调的网络中完成消息的路由，而且非常高效 2 4 l 2 5 1 ，理论 路由步数为l o g 以( 2 的b 次方) 为底n 的对数，可以看出b 决定着全网的性能， b 越大当然越高效，但也会使路由表变大，路由表变大不仅占用更多内存，更意 味着传递消息时需要探测更多节点，处理更复杂的问题。因此需要根据网络的特 性选择一个b 值。 p a s t r y 的路由利用了成熟的最大掩码匹配算法，因此实现时可以利用很多 现成的软件算法和硬件框架，从而获得很好的效率。 1 4 基于语义的对等网资源搜索技术研究 2 3 2 改进的路由协议b a m b o o b a m b o o 2 6 可以认为是基于p a s t r y ，对p a s t r y 协议进行了重新设计，增强 了其性能，更具有可扩展性：它采用与p a s t r y 相同的网络几何，但是却采用不 同的节点加入和邻居节点管理算法 2 7 2 8 。 从性能上说，b a m b o o 能更好的承受d h t 网络节点数的剧烈变化和持续扰动， 即网络波动( c h u r n ) 。波动( c h u r n ) 会极大增加d h t 的维护代价。使用b a m b o o 路由算法，即使在扰动很剧烈的网络环境中进行查找时仍能返回可靠性很高的结 果，并且响应时间较短”1 。 在一个带宽受限的环境中，这种优势表现得更明显。 b a m b o o 在路由策略中有个特点就是即便没有节点加入或退出也会周期性地 更新路由表以尝试优化路由表，这就是所谓的p r o x i m i t yn e i g h b o rs e l e c t i o n ( p n s ) 。 2 3 3o p e n d h t 系统 o p e n d h t 是b a m b o o 路由算法的一个具体实现【3 0 3 1 1 。 o p e n d h t 区分了网络结点和客户端的概念，使得o p e n d h t 网络成为一个开放 的d h t 网络。通过r p c 连接到网络的客户端可使用网络提供的统一接口对网络进 行访问。完成资源的发布、查找、获取以及路由等功能。客户端不必参与维护网 络的结点信息。不必参与资源的路由查找等工作，从丽减轻了负担，提高了网络 的易用性。当然，其实现的代价是降低了网络的通用性。其结构如下图所示： 幂一 ， l l 多 圆 田2 ：o p e n d h t 网络示意图 基于语义的对等网资源搜索技术研究 客户端是位于d h t 网络外部的节点，它们运行应用程序代码，利用r p c ( 远 程过程调用) 来获得o p e n d h t 节点的服务。o p e n d h t 节点除了进行d h t 路由以及 数据存储，还作为接受客户端r p c 的网关。 应用程序不需要考虑d h t 网络的部署与维护，但同时也不能在o r e n d h t 服务 器节点上运行a p p l i c a t i o n - s p e c i f i c 代码。这一点同大多数基于d h t 的程序不 大一样，那些程序把d h t 的功能封装成库函数以供调用。这样做的好处就是，具 有充分的灵活性和性能上的优化。但是必须自己部署d h t 网络。 o p e n d h t 的特点是： 功能分开：系统的运行完全由i n f r a s t r u c t u r e 节点支持，无需c l i e n t 节点 的参与。同时，应用程序也只能在c l i e n t 节点运行。 折中方案：系统运行和应用程序两个功能的截然分开，使得系统的灵活性降 低，但是系统更加易于部署。 综上所述，给定存储信息的索弓 k e y ，d h t 能高效率定位到对应该索引的信 息。但要作全文信息检索，必须要像搜索引擎一样能按内容中包含的字段来进行 检索。因此，这些内容字段必须能够转化成为相应的索引缸这就要求k e y 必 须体现内容信息，而这是个很有挑战性的任务。同时d h t 类的方法面临本身固有 的问题一负载均衡不易、网络拓扑维护代价大、k e y 的同步维护困难等。这些问 题在设计d h t 文件共享系统的时候都是无法避免的。 2 4 非结构化p 2 p 搜索算法 非结构化p 2 p 搜索技术 4 4 4 s 5 0 - 直采用洪泛转发( f l o o d i n g ) 的方式，与 d h t 的启发式搜索算法相比，可靠性差，对网络资源的消耗较大。最新的研究 从提高搜索算法的可靠性和寻找随机图中的最短路径两个方面展开。也就是对重 叠网络( o v e r l a y n e t