（计算机应用技术专业论文）基于语义的p2p搜索算法的研究.pdf

摘要 摘要 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 ；语义；搜索算法；节点；超级节点 a b s t r a c t a b s t r a c t p 2 pi si n c r e a s i n g l yr e c e i v i n ga t t e n t i o ni nr e s e a r c hb e c a u s eo fi t sd i s t r i b u t e dc a p a b i l i t y , e x p a n s i b i l i t ya n dl o a de q u i l i b r i u m i th o l d st h em a i ni d e at h a tt a k e st h ea p p l i c a t i o nt od i f f u s e f r o mc e n t r a l i t yt oe d g eo fn e t w o r k 1 1 1 em a i np u r p o s e sa r em a k i n gu s eo ft h el a t e n tr e s o u r o e i nn e t w o r k ；l i g h t e nt h el o a di nb a c k b o n en e t w o r k n o wt h ep 2 pt e c h n i q u ei sm a i n l y a p p l i e di n f i l es h a r i n g 、d i s t r i b u t e dc a l c u l a t i o n 、c o o p e r a t i n gs y s t e m s 、e l e c t r o n i cc o m m e r c ea n ds oo n a n d f i l es h a r i n gi st h ed o m i n a n tp 2 p a p p l i c a t i o n h o wt os e a r c ha n dl o c a t ed e s i r e dr e s o u r c ei so n e o ft h ek e yi s s u e s t h e r e f o r et h es t u d yo fp 2 ps e a r c h i n gm o d e li s a l w a y sa ni m p o r t a n t c o m p o n e n ti nt h er e s e a r c ho f p 2 pn e t w o r k 劢ei d e a ls e a r c h i n ga l g o r i t h mi np 2 ps y s t e ms h o u l dn o to n l yp r o v i d eg o o dq u a l i t yo f q u e r y , b u ta l s og u a r a n t e ew e l lp e r f o r m a n c eo fs e a r c h h o w e v e rm o s to fe x i s t e n ta l g o r i t h m s c a nn o tm e e tb o t h o b j e c t i v e s u p t o n o w , m o s tp 2 pn e t w o r k s h a v ei m p l e m e n t e d k e y w o r d - b a s e dr e s o u r c ed i s c o v e r ys c h e m e sw i t h o u te n o u g hs u p p o r to ns e m a n t i cb a s e d r e s o u r c ed i s c o v e r y i ti sd i f f i c u l tt or e a l i z ee f f e c t i v eq u e r ya n d f i n d i n g i ti sr e a lc h a l l e n g et h a t h o wt om a k ea p p r o p r i a t es e m a n t i cd e s c r i p t i o nf o rm a n a g i n gi n f o r m a t i o nf a c e db y i n t e l l i g e n t r e s o u r c es e a r c h i n g t i l i sp a p e rt a k e sa d v a n t a g eo fp 2 pa n ds e m a n t i cw e bt e c h n o l o g y , w h i c ho v e r c o m e st h e s h o r t c o m i n g so ft r a d i t i o n a ls e a r c h i n gm o d ea n dm a k e sl e s su s eo fn o d ei ne d g en e t w o r k r l a b e l sr e s o u r c e sw i mp r o p e rs e m a n t i c s t h es y s t e mc a np e r f o r mc o m p l i c a t e dq u e r ya n d p r o v i d em o r ed e s i r a b l es e a r c hr e s u l t t l l i sp a p e rp r o p o s e s as e m a n t i c - b a s e dr e s o u r c e s e a r c h i n gf r a m eb a s e do np 2 ei tp r e s e n t ss e m a n t i cs i m i l a r i t ya l g o r i t h m sa n ds e m a n t i c c o m p a r i n gw a y , b yw h i c hs e m a n t i cs i m i l a r i t yb e t w e e nr e s o u r c e sc a nb ea t t a i n e di no r d e rt o r e a l i z es e m a n t i cq u e r y t l l i sq u e r yi m p r o v e st h es y s t e ms c a l a b i l i t ya n dq u a l i t yo fq u e r yr e s u l t s i m u l t a n e o u s l y , s u p e rp e e ri d e ai su s e dt or e a l i z el o a de q u i l i b r i u m w em a k en o d e sw h i c h h a v es i m i l a rs e m a n t i ci n f o r m a t i o nl i n ki nt h es a m es u p e rp e e rw h e ns e m a n t i c - b a s e dp 2 pi s c o n s t r u c t e dt oi m p r o v es e a r c h i n ge f f i c i e n c y k e y w o r d s ：p 2 p ；s e m a n t i c ；s e a r c h i n ga l g o r i t h m ；p e e r , s u p e rp e e r i i 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：三篮 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密面。 ( 请在以上相应方格内打“4 ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为前浩义扮阳娜鼢听琵 的学位论文，是我个人在导师枷导并与导师合作下取得的研究成果，研 究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资 助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的 各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人矽 作者签名：j 丝 导师签名： 日期：! 墨年鱼月l 日 日期：丛年上月l 日 日期：丝! 绛 月上日 第1 章绪论 1 1 研究背景和意义 第1 章绪论 互联网的迅速发展使网上的信息量呈爆炸式增长，人们对网络资源的利用也日益增 多，为了方便地实现对信息的检索，1 9 9 3 年，出现了最早的网络浏览器，随后各公司也 推出了自己的搜索引擎。不可否认，这为我们实现快速的信息检索，为学习和工作提供 了很多便利，但随着人们对资源返回质量和返回时间的要求越来越高，目前的搜索引擎 技术显然已经不能达到人们的满意了。2 0 0 1 年，r o p e rs t a r c h 经过调查发现，3 6 的互联 网用户平均每星期花费2 小时以上在网上进行搜索；7 1 的用户在利用搜索引擎时出现 过错误，平均搜索1 2 分钟发现搜索出错，其中有4 6 是因为链接错误而导致的。从这些 数据不难看出，目前的搜索引擎及搜索技术仍存在很多局限性，这主要是指信息丢失、 返回信息无关性等方面。通过分析可以发现，造成这种问题的原因主要有两个方面： ( 1 ) 传统的基于客户栅服务器结构的搜索引擎，将全部索引信息存在服务器中， 无形中，使服务器的质量成为搜索的关键，现在网络资源如此丰富，相应地，资源索引 也越来越多，这就更增加了服务器的负担，即使增多服务器的数量，也很难将所有的资 源索引都存储上。 ( 2 ) 目前，网络上的信息资源形式多样，缺乏统一的描述形式，以致资源的内容 和意义不能被机器很好地理解与处理，这对搜索结果的质量有很大影响。因此，能够找 到一种方法对资源进行统一的详细的描述，是成熟的搜索引擎所必需的。 近年来，对等网络( p e e rt op e e r ，p 2 p ) 技术作为一种革命性的技术，致力于充分 利用互联网中巨大的边缘资源，合理高效地组织利用这些大量分布的信息、存储、计算 等资源进行操作。仅几年的时间，p 2 p 网络已经成为发展速度最快、最流行的互联网应 用。p 2 p 在商业上的应用主要有文件共享、边界服务、分布式计算等【l 】，但从目前的实 际应用来看，p 2 p 的优越性还主要体现在大范围的共享、搜索的优势上。如何在用户广 泛分布、数量巨大、节点行为不可控、计算能力和网络连接不均匀的复杂环境下实现高 效的搜索服务是p 2 p 应用面临的最大难题。如何在大规模、分散化和分布式的p 2 p 系统中 河北大学工学硕十学位论文 构建灵活、可扩展的信息查询机制仍然是当前亟待解决的关键问题，目前存在的搜索算 法都存在一定缺陷。例如无组织的p 2 p 系统可以支持多关键字查询、部分查询等复杂查 询，但其发送查询请求时使用“洪泛的方式，可扩展性很差，且不能确保搜索到系统 中存在的资源；有组织的p 2 p 系统( 如c h o r d 2 | ，c a n t 3 】) 具有高度的扩展性，基于分布 式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 将节点组织成一定结构的覆盖网络，可以保 证在一定的跳跃次数内查找多j p 2 p 网络中存在的数据对象，但只能根据资源的键进行准 确匹配的查询。 作为万维网的扩展，语义网于2 0 0 1 年被正式提出。它能够实现面向机器的理解，帮 助人类和机器更好的协同工作，因此得到了研究者的广泛关注，出现了不少关于这方面 的研究。 在本文中，我们将p 2 p 的搜索算法和语义网技术相结合，提出一种基于语义的p 2 p 搜索模型。该模型将有组织p 2 p 搜索拓扑中的典型算法c h o r d 与语义网1 4 融合，查询结果 更符合人们的预期要求，同时在查询效率上比不与c h o r d 算法结合单独进行语义匹配的 搜索模型有很大提高。 1 2 研究现状 对等计算研究热潮的兴起首先是从应用开始的，随后迅速受到工业界和研究界的关 注。目前越来越多的政府和国际组织也开始进行对等计算的研究。p 2 p 引导网络计算模 式由集中式向分布式转移，也就是说网络应用的核心从中央服务器向网络边缘的终端设 备扩散，这也是我们最初构建网络的意图。 n a p s t e r 5 】出现于1 9 9 9 年，它是第一个p 2 p 形式的系统。它允许用户共享在各自磁 盘中存储的m p 3 音乐。按照集成度来分，n a p s t e r 属于集中目录式对等网络模型。在 n a p s t e r 模型中，网络中所有活动节点的地址信息及其共享资源的目录信息都保存在一 群高性能的中央服务器中。当需要查询某个文件或者资源时，节点会向一台中央服务器 发出查询请求。中央服务器按照存储在其中的索引和目录信息进行相应的检索和查询 后，会将符合查询要求的节点地址信息列表返回给发出查询请求的节点。当此节点接收 到返回结果后，将根据网络流量和延迟等信息进行选择，与合适的节点直接建立连接， 并开始文件传输。显然，在这种结构中，如果中央服务器因为受到攻击或者技术原因出 第1 章绪论 现故障，就会失去p 2 p 系统的优势，也就是说，中央服务器的作用太过重要，这对于保 持系统的稳定性是很不利的，中央服务器容易成为系统的瓶颈。 为了避免这样的情况，g l l u t e l l a 【6 】网络模型应运而生。c m u t e l l a 被认为是非结构化p 2 p 系统的代表。按照集成度来分，g n u t e l l a 属于分布式对等网络模型。在c m u t e l l a 的网络 中，拓扑结构并没有严格的控制，节点可以随意加入或离开，但是也因为这样，再加上 不存在中央服务器存储资源索引项，数据存储的位置不容易精确的定位。资源的搜索是 通过查询请求，以“洪泛的方式广播到所有节点来完成的。这种松散式的结构支持关 键字的查询，但缺点也很明显，搜索效率以及查询范围有限。 c h o r d ，c o n t e n t - a d d r e s s a b l en e t w o r k s ( c a n ) ，t a p e s t r y 7 1 ，p a s t r y l 8 1 等是结构化的p 2 p 网络资源搜索系统的代表 9 1 。在这些系统中都构建了覆盖网络，通过各自的方式，对网 络拓扑以及节点的位置进行严格的控制，搜索机制是利用分布式哈希表将请求发送到目 的节点，这样使搜索效率有很大提高。在研究初级阶段这些系统只能通过将文件或者资 源的唯一标识作为搜索键值来查找文件，因此，不支持多关键字的查询。后来，有一些 文章【l o 】对此进行了改进，支持了多关键字的查找，但在查全率上仍有待提高。 在文献【l l 】中第一次提出了语义覆盖网络的概念，这使搜索技术前进了一大步。所 谓语义覆盖网，就是指将内容语义上相同或较为相似的节点聚集在一起，形成一个小的 覆盖网络。当进行查询时，将与查询内容相似的节点选择出来作为邻居节点，这样，邻 居节点中往往存在着大量的符合查询要求的文件或资源，进而，查询效率会得到明显提 高。 由于c m u t e l l a 类型的p 2 p 网络可扩展性差，不能进行大规模地扩张，文献 1 2 】在其 基础上提出了一个p 2 p 网络模型，为提高其搜索性能，该模型采用了语义网技术与p 2 p 网络的动态调整和实时搜索功能结合。该文所构建的p 2 p 拓扑结构是一个超立方体，并 根据通用的本体概念对其进行划分形成概念聚类。节点的查询要求是由本体概念组成 的，由于有概念聚类，网络能够对其做出反应并返回结果。此模型适合于配置大型的动 态网络，利用语义网服务使用本体来描述其功能。但是，此模型结构的构造较复杂，因 而相对于传统的非语义方法，其对节点的开销较大。 此外，还有许多算法利用向量空间模型和潜在语义索引来实现语义查询，如文献 1 3 。e d u t e l l a 1 4 】是一个基于元数据的p 2 p 通用搜索框架，共享元数据都是r d f 格式的， 该框架的r d f 查询语言和基于l m f 的元数据模型可以支持多种已开发的r d f 查询。 冀 河北大学工学硕+ 学位论文 1 3 搜索网络的特征 在p 2 p 中，优秀的搜索网络应该具有以下方面的特征： ( 1 ) 扩展性 扩展性是指在p 2 p 环境中，搜索算法必须能够支持多达数百万的同时在线用户数。 ( 2 ) 高效性 高效性是指资源既能被快速定位，同时仅使用较少的网络通信量。 ( 3 ) 稳定性 稳定性是指对于p 2 p 这种各个节点经常频繁地加入或者离开的系统，搜索网络应该 有足够的适应能力。 ( 4 ) 负载平衡 负载平衡是指总体搜索负载和索引负载应针对各个节点的不同性能，保持基本的平 衡。 1 4 本文主要内容及工作 目前存在的大部分搜索算法都是机械地按照关键字进行查询，缺乏对查询信息的理 解能力和处理能力。有组织p 2 p 网络查询效率高，可将搜索步数控制在o ( 1 0 9 2 n ) 的范围 内( n 为节点总数) ，但其缺陷是不支持具有多关键字、模糊匹配等复杂查询条件的资 源搜索。一些研究试图在有组织p 2 p 网络上支持复杂查询，但适用范围有限，建立有效 的p 2 p 信息搜索算法依然是当前亟待解决的问题。语义网中包含了文档或者部分文档， 其对事物进行了具体描述，并且包含了语义信息，有利于机器进行处理和理解。本文致 力于将p 2 p 技术与语义网技术二者的特长结合起来，解决资源搜索问题。 基础工作包括： ( 1 ) 深入研究p 2 p 网络本身的特点，如p 2 p 网络具有s m a l l w o r l d 1 5 , 1 6 特性，以及 节点之间的异构性，利用这些特点构造新的资源搜索模型； ( 2 ) 了解对于文本描述的一些知识，现在比较常用的是利用向量空间模型将文本 内容向量化，同时，研究语义网的关键技术【1 7 1 ，如本体的描述语言1 8 】，分析资源描述框 架( r d f ) 1 9 】等，利用它们可以将资源描述的更加清晰； 第1 章绪论 ( 3 ) 详细了解现有的搜索模型的算法，分析其优点和不足，以更好的进行改进【2 0 】； ( 4 ) 在此基础上，我们给出了基于语义的对传统查询算法c h o r d 进行改进的算法， 并且给出了相似度的计算公式。 1 5 文章结构 本文共分五章，具体章节结构安排如下： 第1 章绪论。介绍了课题的研究背景，意义及p 2 p 搜索的研究现状以及本文的主 要内容及工作。 第2 章p 2 p 系统概述。介绍了p 2 p 系统的概念，p 2 p 系统的应用领域和分类情况。 第3 章语义网的相关技术。介绍了语义网的体系结构，x m l ，r d f 以及本体。 第4 章基于语义的搜索模型。讨论了c h o r d 算法，给出基于语义的c h o r d 改进算 法，详细地介绍了改进算法的基本概念、基本操作以及查询策略，并给出了相似度的计 算方法。在实验中对改进算法进行了验证，最后对实验结果进行了分析。 第5 章结论与展望。对本文的工作进行了总结，并对以后的工作进行了展望。 第2 章p 2 p 概述 2 ip 2 p 概念 第2 章p 2 p 概述 p 2 p 是p e e r - t o p e e r 的缩写，p e e r 在英文中有“( 地位、能力等) 同等者 、“同事 、 “伙伴 等意义，因此，我们可以把其理解为“伙伴对伙伴 ，即对等网络。o r a m 曾给 p 2 p 下过一个简单的定义：p 2 p 是利用i n t e r n e t 边缘的存储、c p u 计算周期、内容及人 力等资源的一组应用程序【2 。 p 2 p 有两个层面的基本含义【翻： ( 1 ) p 2 p 通信模式：这种模式区别于传统的客户机服务器模式，每个通信方都具 有同等的能力，并且每个通信方都可以发起一个通信过程。 ( 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 也不是新概念，它是互联网整体构架的基础。互联网发展初期， 所有的通信方在通讯中的地位都是平等的，并不存在服务器和客户机的概念。当然，后 来出现的一些软件的确采用了客户机服务器的模式，如邮件客户端和邮件服务器，浏览 器和w 曲服务器。但是，从服务器的层面上来说，它们之间仍然是对等的关系。例如电 子邮件，互联网上并不是由一个巨大的、唯的邮件服务器来处理所有的电子邮件，而 是通过将邮件服务器进行对等联网和相互协作，最终将电子邮件传送到相应的服务器上 去。另外用户之间的电子邮件也一直是对等的联络渠道。当然在过去的几年里，互联网 7 河北大学t 学硕十学何论文 上很大一部分节点不能与其它节点进行直接交流，使得互联网的发展从表面上远离了 p 2 p 。但是，n a p s t e r 的发展唤醒了深藏在互联网背后的对等联网理念。虽然在局域网中， n a p s t e r 的文件共享目录功能是很平常的事情，但是n a p s t e r 的成功促使人们认识到把这种 “对等联网 理念拓展到整个互联网范围的可能性。 2 2p 2 p 的应用 在某种意义上讲，p 2 p 体现了i n t e m e t 的本质。在网络发展的初级阶段，用户间就是 通过所谓的“布告板等渠道直接交互信息和资源。目前i n t e m e t 的存储模式是“内容位 于中心舫，而使用p 2 p 技术后，i n t e r n e t 上的内容向“边缘( 用户) 移动。从目前来看， p 2 p 主要有以下几种应用。 2 2 1 即时通信 所谓即时通信，就是指q q 、i c q 、m s n 等即时通信软件。主要是两个或者多个用 户可以通过文字、声音或文件等进行交流，甚至还可以与手机进行通讯。p 2 p 的即时通 信软件可以随时知晓对方是否在线，不依赖服务器的性能和网络带宽。尽管目前的即时 通信技术一般都具有中心服务器，但只是用来控制用户的认证等基本信息，并帮助节点 之间完成初始连接，双方交流完全基于点对点通信。 2 2 2 文件共享 p 2 p 技术使在i n t e r n e t 上的任意两台计算机之间直接共享文件、文档等资源成为了 可能，如n a p s t e r 和g n u t e l l a 软件等。传统的w e b 方式中，要实现文件交换需要服务器 的全程参与，文件的持有者将其上传至某个特定的网站，接收者再到该网站进行搜索和 下载，这种方式无疑会浪费大量的时间，且不方便操作。电子邮件的出现使个人间文件 传递问题得以解决，却难以解决大范围的交换，这就是w e b 的重要缺陷。利用p 2 p 技 术，用户可以直接从任意一台安装相同软件的网上计算机中下载文件，而不需要使用任 何一台中央服务器。可以说，对文件交换的需求直接引发了p 2 p 技术热潮。 第2 章p 2 p 概述 2 2 3 对等计算 采用p 2 p 技术的对等计算，可以把网络中的众多计算机暂时不用的计算能力( 如处 理器、存储器等) 等分散的资源积聚起来，完成超级计算机的任务。如应用于天气预报、 动画制作、基因组的研究等。p 2 p 技术使得这些需要大量数据处理的行业十分受益。 2 2 4 协同工作 基于p 2 p 技术，在网络上任意两台计算机建立的共享虚拟空间中，人们可以进行协 同工作。这其中最有名的计划是由伯克利大学开展的寻找外星生命的s e t i h o m e 研究 计划。s e t i h o m e 使用p 2 p 技术来分析行星的无线电信号，寻找宇宙中可能存在的其 他外星文明的证据。p 2 p 技术串联所有参与研究计划者闲置的电脑来执行庞大复杂的运 算，然后再把结果传到s e t i h o m e 总部。 2 2 5 搜索引擎 p 2 p 技术的另一个优势是开发出强大的搜索工具。传统目录式搜索引擎只能搜索到 2 0 - - - 3 0 的网络资源，p 2 p 技术使用户能够深度搜索文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿主设备的限制，理论上将包括网络上的所有开放 的信息资源。可以说，p 2 p 为互联网的信息搜索提供了全新的解决之道。著名的搜索引 擎公司g o o g l e 也宣称要采用p 2 p 技术来改进其搜索引擎。 2 2 6 其它应用 除上述几种之外，p 2 p 也应用于电子商务和游戏软件领域。p 2 p 技术在电子商务上 的应用可以包括金融服务，购物行为分析，电子商务集市等几个方面。目前许多游戏软 件都是通过对等网络来实现的。 河北大学t 学硕十学位论文 2 3p 2 p 系统的分类 2 3 1 按照是否建立覆盖网络分类 p 2 p 系统根据是否建立了一个结构化或者特殊的覆盖网络，可分为三类：非结构化 网络、结构化网络和松散结构的网络。 ( 1 ) 非结构化网络( 如g n 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 等) 结构化网络的出现是为了解决非结构化网络可扩展性差的问题。这些系统建立覆盖 网后，将文件放置在根据一定算法计算后确定的位置上，在文件标识符和文件之间建立 一定的映射关系，形成一个分布式哈希表，使查询能够迅速定位，找到有效信息。 本文中采用了结构化网络的典型算法c h o r d 作为搜索模型的基础，并对其进行了一 些语义的标识，增强搜索结果的质量。 ( 3 ) 松散结构的网络( 如f r e e n e t ) 这种网络结构介于非结构化的网络结构和结构化的网络结构之间。文件的定位有一 些索引信息能够进行提示，但是这些索引信息并没有规范，因此查询的效果并不是很理 想。 2 3 2 按照资源搜索的集中程度分类 在p 2 p 搜索系统中，以资源搜索的集中程度为标准，可以分为三种模式：集中式 p 2 p 模式【2 3 1 、纯p 2 p ( 分布式p 2 p ) 模式 2 4 1 、混合p 2 p 模式。在这三种模式中各个节点 在搜索中承担的任务是不同的。 ( 1 ) 集中式p 2 p 模式 代表性软件为n a p s t e r 。n a p s t e r 模型中，节点将查询请求发送到一个单一的索引服 1 0 第2 章p 2 p 概述 务器。索引服务器根据本地的客户资源索引，对查询做出回应。当各个节点的资源出现 变化时，比如资源的增加、删除等，索引服务器将收到更新消息，并据此修改本地缓存， 但查询不在客户节点间传递。当需要查询某个文件时，节点会向索引服务器发出文件查 询请求。索引服务器进行相应的搜索后，将符合查询要求的节点地址信息列表返回。发 出查询要求的节点接收到应答后，根据网络流量和延迟等信息进行选择，与合适的节点 直接建立连接，并开始文件传输。集中式p 2 p 工作原理如图2 1 所示。 ( 乡 服务器 对等端 图2 1 集中式p 2 p 工作原理图 ( 2 ) 纯p 2 p 模式 代表性软件有g n u t e l l a 、b e a r s h a r e 、l i m e w a r e 等。每一个节点在内容的共享和搜索 两个方面，都具有完全相同的作用和责任。所有的节点既是搜索查询的发出者，同时也 是搜索处理的执行者。这种模型的特点是在每个节点上都保存有部分索引信息，这些分 布式索引表一般要求很小，这些索引信息给出了文件所在的方向，而一般不是文件所在 的真实位置，因而与传统的目的索引不同【2 5 】。而且，用户除了提交查询条件之外，还提 交停止条件( 例如所期望的结果数目，或1 儿等) 。 纯p 2 p 模式也存在很多弊端，主要表现在以下方面：随着网络规模的扩大，查询信 息时，通过扩散方式定位节点的方法将造成网络流量急剧增加，导致网络拥塞，最终 使得网络被分片，查询操作只能局限于网络中的一小部分进行。因此，网络的可扩展 性不好，不适用于大型网络。同时，安全性不高，容易遭受恶意攻击，如攻击者大量 1 1 河北大学t 学硕十学位论文 发送垃圾查询信息，就会造成网络拥塞。 纯p 2 p 模式的工作原理如图2 - 2 所示。 t t l 已到 不再转发消息 对等体发出查询， 果 图2 - 2 纯p 2 p 工作原理图 ( 3 ) 混合p 2 p 模式 这种形式的关键之一是引入了索引节点，索引节点不会直接连接到有版权的资料， 它就像y a h o o 一样，只是搜索和所需资料相关的地址，至于用户到底连接下载了什么内 容和它无关。这种形式的关键之二是引入了超级节点，超级节点管理着所属用户的文件 列表。一些混合的方式和k a z a a 都是用与这种方式相似的方法，这些方法使用性能比较 高的节点作为超级节点管理其他节点。 对于资源的查询，每一个一般节点每一时刻仅与一个超级节点连接，一般节点将自 己的资源索引发送给它，并且需要查询时，向其发送自己的查询请求。超级节点在收到 请求后既要根据本地缓存处理，又要将查询转发。转发查询的超级节点在收到其他超级 节点的回应后，会将所有结果返回给一般节点。 混合式p 2 p 工作原理如图2 3 所示。 第2 章p 2 p 概述 2 4 搜索模式选择 超级节点 对等体 图2 3 混合式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 网络具有高度的扩展性，由于每个终端设备在线时间不是固定的，良好的扩 展性使得新终端设备加入或者旧终端设备退出时，网络仍能保持较好的稳定性和结构 性。 随着搜索引擎的高速发展，人们在方便工作与生活的同时对搜索效率有很多不满， 河北大学f t 学硕七学何论文 如果可以对结构化p 2 p 网络进行改进，既保留了其效率高的优点，又克服其查询受限的 缺点，将会对搜索研究产生重要影响。正因如此，很多研究者试图用多种方式对结构化 p 2 p 进行改进。 本文同样利用结构化p 2 p 作为搜索模型的基础。 综上所述，我们的搜索模型可以这样描述。首先，根据结构化网络的构建方法，建 立一个覆盖网络，然后将覆盖网络中的部分节点充当第二种分类方法中的混合式p 2 p 的 超级节点，这样构造的搜索模型，由于采用了覆盖网络而提高查询效率，同时因为设置 了超级节点而达到负载平衡。 第3 章语义网的介绍 孽_ i i- - - , 1 1 l i _i=i。li_ii i , 皇皇曼皇皇曼曼曼置舅量皇量皇量曼皇 3 1 语义网的体系结构 第3 章语义网的介绍 1 9 9 8 年t i m 等人首先提出了语义网( s e m a n t i cw e b ) 的概念【2 6 】，t i mb e m e r s - l e e 在x m l 2 0 0 0 大会上描述了这个体系结构，他对语义网作了如下的描述：语义网并不是 孤立的，而是当前网络的延伸，它上面信息的含义已经被预先良好的定义，使人与机器、 机器之间能够更好的实现信息的共享与协作。语义网的目标就是让机器能理解网络上的 信息，使机器可以对网络上的信息资源进行智能化的处理。旨在赋予万维网上信息资源 以一种标识，在资源之间建立起机器可处理的各类语义联系，帮助人类和计算机更好的 协同工作。语义网的体系结构如图3 1 所示鲫。 信任 证明 逻辑 数 字 签 本体 名 资源描述框架 可扩展标记语言i 命名空间 统一字符编码统一资源定位符 图3 - 1 语义网体系结构 语义网的体系结构包括七层，从底层到高层依次为：统一字符编码与统一资源定位 符、可扩展标记语言+ 命名空间、资源描述框架、本体、逻辑、证明、信任。各层间相 互联系，通过自下而上逐层拓展形成了一个功能逐渐增强的体系。它不仅描述了语义网 的基本框架，而且可以利用这种思路，在现有网络的基础上，逐层扩展其功能，实现语 义网。 第一层是统一字符编码与统一资源定位符层，是整个语义网的基础。要实现语义网， 必须能够找到资源。本层主要是解决网络上资源的定位和跨地区字符编码的标准格式问 1 5 河北大学t 学硕十学位论文 题。其中统一资源编码负责处理资源的编码，确保计算机能识别资源的编码。而负责标 识资源的统一资源定位符( u r i ，u n i v e r s a lr e s o u r c ei n d i c a t o r ) 是u r l ( u n i v e r s a lr e s o u r c e l o c a t o r ) 的超集，确保资源具有唯一标识。 第二层是可扩展标记语言+ 命名空间层，是x m l 及其相关技术层。x m l 不仅功能 强大，而且易于使用，是网络上数据表示的标准。用户可以在x m l 上通过创建自己的 标签对网页进行注释，这些标签将成为脚本获得信息的途径。因此，x m l 非常适用于 不同应用问的数据交换，而且这种交换不需要预先规定一组数据结构定义，具备很强的 开放性。x m l 为用户提供了一个可以根据实际需要定义自己的置标语言的标准，并为 这个置标语言规定它特有的一套标签。因此准确地说，x m l 是一种元标记语言，即定 义标记语言的语言。命名空间由统一资源定位符索引确定，目的是为了简化其书写。通 过在命名前加上统一资源定位符索引前缀，即使具有相同命名的两个事物，只要它们的 索引前缀不同，二者就不会混淆。本层中还包含x m ls c h e m a ，它实际上也是x m l 的 一种应用，采用x m l 语法，所以x m l 文档是一种自描述文档。x m ls c h e m a 是d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 的替代品，但比d t d 更加灵活。它的优点在于提供了一 套完整的机制对x m l 文档中标签的使用进行约束，同时，它支持更多的数据类型，能 更好地为有效的x m l 文档服务并提供数据校验机制。 第三层是资源描述框架层，其提供的语义模型用于描述网络上的资源及其类型，为 网上资源描述提供了一种通用表示框架和实现数据集成的元数据解决方案。r d f 即资源 描述框架，是w 3 c ( 互联网联合组织) 推荐的用来描述万维网上的信息资源及其之间 关系的语言规范。从语法上来说，由于r d f 符合x m l 规范，因此可以把r d f 看成是 利用x m l 规范而定义的一种置标语言。但在语义描述上，r d f 与x m l 却有天壤之别。 r d fs c h e m a 规范用r d f 进一步定义了建模原语，提供了r d f 模型中使用的一个基本 类型系统。 第四层为本体层，对领域知识进行统一描述和规范，具有很强的表达能力，支持可 保证计算完整性和可判定性的逻辑推理。 第五层为逻辑层，提供公理和推理规则，为智能服务提供基础。 第六层为证明层，用来在逻辑层之上进行更为复杂的证明和推理。比如为了满足逻 辑层的各种断言和公理的使用条件而进行的证明过程。 第七层信任层和跨越多层的数字签名注重于提供认证和信任机制，使用户代理 1 6 第3 章语义网的介绍 a g e n t 在网络上实现个性化服务和彼此间交互合作具有可靠性和安全性。虽然公钥密码 技术已存在较长的时间了，但还没有真正广泛应用，如果加上语义网各层支持，使一个 团体在一定范围内可信任，就实现了信任层，这样一些诸如电子商务等重要应用就可以 进入到语义网的实用领域。 在语义网七层结构中的可扩展标记语言( 煳l ) 、资源描述框架( r d f ) 和本体层 三层，主要用于表示网络中信息的语义，是系统的核心和关键所在。数字签名用来检测 文档是否被篡改过，以证实其真实可靠性。 3 2 元数据 元数据最本质、最抽象的定义为：d a t aa b o u td a t a ( 关于数据的数据) 。它在许多领 域广泛存在并被具体的定义和应用。有人把元数据定义为：描述数据或者数据对象的数 据。元数据是整个语义网的基础。 对于元数据的种类有许多不同的分类方法。一般分为描述性元数据、管理性元数据、 结构性元数据、保存性元数据等【2 8 1 。 ( 1 ) 描述性元数据，用来描述、发现和鉴别数字化信息对象，如m a r c 、d c ， 它主要描述资源的主题和内部特征； ( 2 ) 结构性元数据，描述数字化信息的内部结构； ( 3 ) 存取控制性元数据，用来描述数字化信息资源能够被利用的基本条件和期限， 以及这些资源的知识产权特征和使用权限； ( 4 ) 评价性元数据，描述和管理数据在信息评价系统中的位置。 3 3x m l 语义网通过采用多层次的表示框架对文档语义信息进行描述。首先为文档引入结 构，将文档分解成一些可以识别的“块 ，这样计算机就能够方便地解读文档，这就是 x m l 2 9 1 。了解x m l 后，就可以编程序对内容进行信息提取等操作。 x m l ( e x t e n s i b l em a k e u pl a n g u a g e ) 是组允许文本和数据编码的w 3 c 规范。它 的数据与应用软件、平台、硬件都不相关，这种数据格式便于在互联网上交换，也便于 软件开发人员和内容创作者在网页上组织信息。 1 7 河北大学t 学硕士学位论文 x m l 的开发始于1 9 9 6 年，1 9 9 8 年成为w 3 c 规范之一。w 3 c 网站是这样描述它的： 可扩展标记语言( x m l ) 是在网上构造文档和数据的所有格式。它是“标准通用标记语 言 ( s t a n d a r dg e n e r a l i z e dm a k e u pl a n g u a g e ，s g m l ) 的精简臃子集合。s g m l 于8 0 年代早期开始发展，主要用于一