（计算机应用技术专业论文）p2p信息检索的研究.pdf

摘要 摘要 p 2 p 已经成为近年来的研究热点，它具有可扩展性，容错性等特点，在p 2 p 环境下 进行资源定位是p 2 p 研究的核心问题，目前p 2 p 已经应用于很多领域，但如何在大规模 的p 2 p 网络中进行可扩展、有效的信息检索仍然是个开放型问题。非结构化p 2 p 网络采 用的是“洪泛 的方法搜索资源，具有较高的稳定性，并支持模糊查询，但多数情况下 效率较低，扩展性差，定位稀疏资源困难；结构化的p 2 p 网络具有可扩展性，是建立在 分布式哈希表( d h t ) 之上，定位资源效率高，比较适合大规模范围的p 2 p 信息检索，但 是基于d h t 的p 2 p 网络一般不能支持模糊查询。 本文首先分析了p 2 p 信息检索的一些关键技术，对基于d h t 的结构化p 2 p 信息检 索的核心机制进行深入的研究，介绍了目前基于d h t 的结构化p 2 p 网络支持模糊查询 的两类方法：关键词查询和语义查询。 然后，针对目前结构化p 2 p 网络信息检索中基于多关键词查询出现的带宽消耗等问 题提出了一种基于关键词设置的p 2 p 信息检索策略，采取了如下措施( 1 ) 删节与特征词 相关的存储文件信息的索引列表至恒定长度。( 2 ) 选择通过关键词联合的新特征词设置 来扩充索引特征。性能分析和实验结果显示，该策略具有很好的带宽消耗扩展性。 最后，针对语义查询思想，阐述了基于d h t 的p 2 p 网络利用向量空间模型( v s m ) 技术进行资源描述的基础上融合位置敏感散y w j ( l s h ) 技术的策略，将内容相似的文件信 息分布到p 2 p 标识空间中相同的节点上，实验结果分析显示了该系统的可行性和有效 性。 关键词：p 2 p ，信息检索，分布式哈希表 a b s t r a c t p 2 pt e c h n o l o g yh a sb e c o m et h eh o ts p o to fr e s e a r c hr e c e n t l y i th a sg o o df a u l t - t o l e r a n c ea b i l i t ya n ds c a l a b i l i t ya n do t h e r w i s e r e s o u r c e sl o c a t i n gi sak e yi s s u eo fp 2 p r e s e a r c h a l t h o u g hp 2 pn e t w o r kh a sb e e n u s e di nav a r i e t yo fa p p l i c a t i o n ss u c c e s s f u l l yt h o s e y e a r s ，h o wt os e a r c he f f i c i e n t l ya n ds c a l a b i l i t yi nl a r g e - s c a l ep 2 po v e r l a y , w h i c hi ss t i l la l l o p e np r o b l e m f l o o d i n gs e a r c hm e c h a n i s m si sa d a p tb yu n s t r u c t u r e dp 2 pn e t w o r ka d o p t s ，i t h a sh i 曲s t a b i l i t ya n ds u p p o r tf u z zs e a r c h ，b u ti th a sl o we f f i c i e n c ya n db a de x t e n s i b i l i t ya n d l o c a t i n gt h er a r er e s o u r c ed i m c u l t y s t r u c t u r e dp 2 pn e t w o r kw h i c hb a s e sd i s t r i b u t e dh a s h t a b l e ( d h t ) c a np r o v i d eg o o ds e a r c he f f i c i e n c ya n ds c a l a b i l i t y , m o r e o v e r ，i ti sm o r es u i t a b l e f o rp 2 pi n f o r m a t i o nr e t r i e v a li n l a r g e s c a l en e t w o r k w h i l ed h t - b a s e ds t r u c t u r e dp 2 p n e t w o r k sf a i lt os u p p o r tf l e x i b l em u l t i k e y w o r ds e a r c h 1 1 1 ek e yt e c h n o l o g i e so ft h ep 2 pi n f o r m a t i o nr e t r i e v a li si n t r o d u c e di nt h i sp a p e ra n di t e m p h a t i c a l l ya n a l y z e st h ec o r em e c h a n i s mo fd h t - b a s e ds t r u c t u r e dp 2 pn e t w o r k m o r e o v e ri t i n t r o d u c e ss o m em e t h o d sf o rs u p p o r tf u z zs e a r c hi nd h t - b a s e ds t r u c t u r e dp 2 pn e t w o r kw h i c h i sd i v i d e di n t ot w om a i nc a t e g o r i e s ：k e y w o r ds e a r c ha n ds e m a n t i cs e a r c h a n d t h e n ，a n a l y z i n gt h em u t i k e y w o r d ss e a r c hi ns t r u c t u r e dp 2 pi n f o r m a t i o nr e t r i e v a l i n o r d e rt oc o p ew i t hs u c hp r o b l e mo fb a n d w i d t hc o n s u m p t i o n ai n d e x i n gf r a m e w o r ko ft h es e t o fk e y w o r d ss t r a t e g yi sp r o p o s e d i ta d o p t i n gt r u n c a t ep o s t i n gl i s t sa s s o c i a t e dw i t hi n d e x i n g f e a t u r e st oac o n s t a n ts i z ea n de x t e n dt h es e to fi n d e x i n gf e a t u r e sw i t hc a r e f u l l yc h o s e n f e a t u r ei t e ms e t so fk e y w o r d sc o m b i n a t i o n t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t s s h o w si tg u a r a n t e ea na c c e p t a b l eb a n d w i d t hc o n s u m p t i o n ，t h es y s t e mh a sg o o ds c a l a b i l i t y f i n a l l y , a c c o r d i n gt o s e m a n t i cs e a r c hi ns t r u c t u r e dp 2 pr e t r i e v a l ，a ne f f e c t i v e i n f o r m a t i o nr e t r i e v a lo fs t r u c t u r e dp 2 pi sd e s i g n e d t e c h n o l o g i e so fv e c t o rs p a c em o d e la n d l o c a ls e n s i t i v eh a s h i n ga r ea d a p t t h eb a s i ci d e ai st op l a c ed a t ao fs e m a n t i c a l l yc l o s ef i l e s i n t os a m ep e e rn o d e s 埘t hm g hp r o b a b i l i t y i ts p e e d su ps e a r c hp r o c e s s e x p e r i m e n t a lr e s u l t s s h o w st h ev a l i d i t yo ft h i ss y s t e m k e y w o r d s ：p 2 p ；i n f o r m a t i o nr e t r i e v a l ；d i s t r i b u t e dh a s ht a b l e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：华瞵一导师签名：差l 日 飙掣甲融细 第一章绪论 1 1 研究背景及意义 第一章绪论 传统的基于客户栅服务器( c l i e n t s e r v e r ) 的模式中，处于核心地位的中央服务器拥 有大量的带宽和计算资源，管理着其他从属用户，并为许多从属用户服务，而个人计算 机只能作为网络的终端，不可能为他人提供服务。随着网络技术的发展，越来越多的机 器接入网络，p c 机、网络传输设备及各种数字设备性能快速增强，一台个人计算机的 存储和计算能力甚至超过了二十年前的大型机，于是很多人开始用自己的个人计算机对 外提供特定的服务。随着边缘p c 机能力的增强，边缘网络信息不断丰富，互联网中亟 待新的计算模式来充分利用这些资源来满足各种应用，使得网络计算成为工业生产、社 会生活的强力支持，为经济发展乃至社会进步提供动力。对等网络( p e e rt op e e r ，p 2 p ) 就是在这种背景下逐渐成为研究热点。 对等网络( p e e r t op e e r ，p 2 p ) ，不同于传统模式，它抛开了应用服务器的束缚，每个 节点既可以享用其他节点提供的数据或服务，又可以向其他节点提供数据和服务。所有 成员都可以以一种对等的方式共享这些节点的存储空间、处理器计算能力、网络带宽等 资源。p 2 p 具有自组织性，可伸缩性，可靠性等优点，极大的技术优势和简单的实现技 术使得p 2 p 技术具有广阔的应用前景，广泛应用于数据共享，c p u 周期共享，即时通 信，协同工作组件等各个领域，自1 9 9 9 年的风行一时的网络音乐文件共享n a p s t e r 盛行 之后，人们熟知的各种p 2 p 软件相应出台，如：g n u t e l l a , k a z a a ，e d o n k e y e m u l e ，s k y p e 等等，短短几年的历史，p 2 p 在应用领域和学术界获得了广泛的重视和成功i lj 。 w e b 信息每年都呈爆炸性的增长，当前如何有效的进行信息采集，实现信息共享已 经成为一个的热点，以g o o g l e 、y a h o o 、新浪为典型代表的集中式搜索引擎技术为人们 提供了一种方便快捷的获取信息的方式，人们越来越依赖通过搜索的理念去定位所需要 的资源1 2 j 。但传统的集中式的搜索引擎远远无法涵盖所有互联网内的共享内容，缺乏可 扩展性，处理和存储能力有限。而p 2 p 技术呈现的各种性能正好是这种集中式搜索的补 充，p 2 p 信息检索的出现【3 4 】，为互联网信息检索提供一种全新的模式。其优势在于应用 先进的对等搜索理念，可不通过给定的中央服务器，也可不受信息文档格式和宿主设备 的限制，对互联网络进行全方位的搜索。搜索范围可在短时间内以几何级数迅速增长， 其理论上最终将包括网络上的所有开放的信息资源，搜索深度较传统模式也有很大提 高，检索到的信息将有更强的实时性和有效性。总体来说，p 2 p 信息检索可以有以下几 个方面的现实意义： 1 即时的搜索大规模分布形式存在的信息。除了传统的搜索引擎检索到的静态页 面之外，在边缘网络还存在海量的信息。这些存在于不同主机里的信息中有很多是用户 通过筛选后保存下来的，具有一定的价值。随着现代p c 机能力的不断增强，这种信息 爆炸性增长。而这类信息具有动态变化的短周期特性。传统的搜索引擎检索是预先通过 “网络爬虫 或者其他工具形成的索引。由于网络规模的庞大，导致基于“网络爬虫” 江南大学硕士学位论文 的传统搜索引擎的索引刷新周期过长，必然会影响到实时性强的海量信息检索的问题。 通过p 2 p 的搜索模型构建的p 2 p 信息检索是一个自然的选择。在p 2 p 网络中，所有的 主机自组织地构成一个p 2 p 网络。p 2 p 搜索引擎系统将搜索的功能放置在每个独立的对 等点上，基本上实现了搜索引擎系统的本地化，当请求消息到来时，将搜索功能在本地 机器上实施，可以很便捷地检索到所有主机中所存储的相关信息，返回的信息都是即时 的。 2 弥补传统搜索引擎无力深度搜索信息的弱点。传统的搜索引擎，主要搜索的是 网络中的静态信息、h t m l 页面以及静态的主页等，由文献 5 】可知，目前g o o g l e 所能 检索到的8 0 亿只是互联网上超过5 5 0 0 亿共享文档总量中很小的一部分。大部分在网站 数据库中以动态网页形式的信息则无法用传统搜索引擎通过对静态网页上的链接爬行 采集来获取，通常情况下网站只有主动提供信息索引以备检索。而p 2 p 的信息检索使得 各个节点可以作为一个提供者加入网络，并把本机上存储的信息制成索引，所有的节点 形成一个庞大的全局分布式索引以方便检索。 3 挖掘移动智能终端信息。3 g 时代到来之即，各种移动智能设备( 智能手机或其 它智能终端) 的功能不断加强，这种互联网中的移动终端存储的信息具有分布广、地域 特性强、密切关联用户等特点，这些将在互联网中的p 2 p 覆盖网中仍然存在，p 2 p 网络 信息检索所具有的独特特性可以充分挖掘这些分布的信息，进一步辅助了信息在各用户 群体内部的顺畅流通。可见，p 2 p 信息检索适合于解决移动终端信息的一些实际问题， 具有很大的实用价值和研究意义。 4 构建兴趣信息终端，提供人性化的信息服务。目前，国内在线用户排名靠前的 p 2 p 软件p o c o 和o p e n e x t 在文件共享的基础上，采用挖掘娱乐兴趣团体，从而吸引 用户保持在线。p 2 p 网络中终端用户所存储的信息直接反应了用户的兴趣。随着p 2 p 信 息检索技术的不断发展，在对这些兴趣进行挖掘的基础上，可以很方便地对产品和业务 进行个性化推送，并且研究和开发出更加富有人性化的信息终端1 6 l 。这无论是对提升企 业内部信息流通的质量还是对改善公众网络信息服务都有十分重大的意义。 由上所述，p 2 p 信息检索具有很高的研究价值，它蕴含着巨大的技术潜力和商业前 景，许多学术机构、大公司已经先后投入到对p 2 p 检索技术的研究之中，它是未来若干 年互联网发展的重要趋势。 1 2 国内外研究现状 目前，p 2 p 技术已经进入高速发展期，而从p 2 p 技术诞生那天起，p 2 p 搜索技术便 是一个热门的话题，国内外研究者们一直致力于寻求有效的p 2 p 搜索技术来满足应用需 求。 在国外，自n a p s t e r 开始盛行以来，很多大型公司、著名高校及研究机构都积极参 与到p 2 p 网络的研究及开发中，其中包括i n t e l 、s u n 、m i c r o s o f t 和h p 等一些极具影响 力的大公司，其中，i n t e l 发起成立了p 2 p 网络工作组，推动了p 2 p 的发展。而s u n 公 2 第一章绪论 司在p 2 p 研究领域主要的贡献就是t a 【7 l 工程。国外著名科研机构和学术团体也成立 并完善了专门的p 2 p 研究小组进行相关研究，其中包括m i t 的c h o r d 和c f s 研究组， u cb e r k e l e y 的t a p e s t r y 和o c e a n s t o r e 研究组等，目前国内对p 2 p 信息检索的研究还处 于初级，主要是清华大学开发的以对象格式存储数据的g r a n a r y 及北京大学网络实验室 开发的一个中心控制与对等连接相融合的对等计算文件共享系统m a z e 。 以下是对于p 2 p 信息检索的研究主要的两个方面。 2 0 0 0 年出现的g n u t e l l a s l 采用分布式非结构化p 2 p 结构，称为非结构化p 2 p 网络， 这类网络的采用的是“洪泛”方法发布请求、搜寻资源，具有较高的稳定性。但系统的扩 展性差，且不能保证搜索到存在的资源。因此，研究界也提出了一些方法来提高性能， 如：s r i p a n i d k u l c h a i 等提出了由节点的内容分析用户的兴趣，在相似兴趣的节点之间添 加快捷链接【9 1 。c o h e n 等人利用节点内容之间产生向导规则，把相同规则的节点组织到 关联网络中b o 。 2 0 0 1 年出现了以c h o r d1 1 1 】，c a n 1 2 】，t a p e s t r y 1 3 1 ，p a s t r y t l 4 1 为代表的结构化p 2 p 网络， 它们的共同特点是需要建立在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) z _ l t ”j ，d h t 方法的核心是在资源的索引编码与p 2 p 网络节点的标识码( i d ) 之间建立相对一致的映 射，能够在o ( 1 0 9 n ) 跳之内定位到对应的节点，结构化p 2 p 网络克服非结构化洪泛查找 引起的网络拥塞的弊端，解决了p 2 p 网络可扩展性的问题，实现了实时高效的检索，因 此结构化p 2 p 成为对等研究和应用的主流和热点。但是结构过于严格使得结构化的p 2 p 网络只支持精确查询。近年来，一些在结构化p 2 p 网络的基础上支持多关键词查询的研 究相继被提出，如：p e e r s e a r h | 1 6 】和s e t s | 。7 1 ，结合了在具有相似内容的结点间添加连接 构建覆盖网络，然后将查询消息路由到相关的覆盖网络中进行局部搜索。还有一类方法 是基于关键词建立索引【1 8 , 1 9 ，查询时将请求分割出关键词来进行检索。 1 3 本文主要研究内容 本文结合p 2 p 信息检索的发展趋势，对p 2 p 信息检索的相关技术进行以下方面的研 究： 详细的分析了p 2 p 技术特点并阐述了p 2 p 信息检索的技术优势和趋势。提出了研究 和开发p 2 p 信息检索的必要性。 分析了p 2 p 信息检索的一些关键技术，详细介绍了基于d h t 的p 2 p 信息检索的d h t 机制和相关路由算法，并介绍了目前基于d h t 的p 2 p 模糊查询的不同方法。 针对结构化p 2 p 网络关键词查询的检索质量及带宽消耗的特性，深入分析该问题的 根源，并提出了一种基于关键词设置的结构化p 2 p 索引框架。最后实验结果证明该p 2 p 信息检索策略具有较高的扩展性。 从理论上描述了p 2 p 信息检索中向量空间描述数据对象的方法，为了方便信息检 索，在向量空间模型( v s m ) 描述数据对象的基础上融合位置敏感散列( l s h ) 技术，来进 行数据的相似性分布。实验表明该策略具有较高性能。 江南大学硕士学位论文 本文的组织结构安排 根据以上分析，本文重点将讨论面向p 2 p 信息检索的相关技术。论文各章节内容安 排如下： 第一章主要介绍课题的研究背景和意义、相关研究内容以及研究现状。 第二章介绍p 2 p 定义及技术特点，并由此阐述了p 2 p 信息检索的技术优势和趋势， 并分类介绍了p 2 p 信息检索的原理、特点。 第三章主要目前p 2 p 信息检索的一些关键技术，并重点介绍了基于d h t 的p 2 p 检 索的核心机制，包括d h t 机制和一些路由算法。并分析了目前两方面基于d h t 的p 2 p 模糊查询的方法。 第四章针对当前结构化p 2 p 网络信息检索的关键词查询，提出了基于关键词设置的 p 2 p 信息检索策略，并进行了带宽消耗性能分析和检索质量的模拟分析。 第五章针对语义查询思想，基于d h t 的p 2 p 查询，提出了一种p 2 p 信息检索系统 模型，该模型将内容相似的文件信息分布到p 2 p 标识空间中相同的节点上，系统具有较 高的性能。 第六章对论文的主要工作做了总结，同时也提出了今后需要迸一步研究和完善的工 作。 4 第二章p 2 p 及信息检索 2 1p 2 p 技术概述 第二章p 2 p 及信息检索 对等网络( p e e rt op e e r ，p 2 p ) 技术并不是一种新兴的技术，2 0 世纪7 0 年代中期，源 于局域网的文件共享，p 2 p 技术就开始流行起来了。目前大家所关注的p 2 p 技术，是原 有技术的新应用模式。下面对p 2 p 技术进行简单的介绍。 2 1 1p 2 p 定义和特点 p 2 p 是p e e r - t o p e e r ( 对等网络，对等计算) 的简称，中文译名为对等互联或者点对 点技术。在p 2 p 网络中各个节点被称为p e e r ( 对等体) 。p 2 p 是一种网络模型，在这种 网络中所有的节点是对等的( 称为对等点) ，各节点无主从之分，各节点具有相同的责任 与能力并协同完成任务。对等点之间通过直接互连共享信息资源、处理器资源、存储资 源甚至高速缓存资源等，无需依赖集中式服务器或资源就可完成。业界对于p 2 p 的定义 有多种，典型的是i n t e l 公司和i b m 公司对p 2 p 的定义【2 0 j 。 i n t e l 将p 2 p 定义为“通过系统间的直接交换达成计算机资源与信息共享系统”，这 些资源与服务包括信息交换、处理器时钟、缓存和磁盘空间等。 i b m 将p 2 p 定义为：“p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特 性：系统储存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员 而不是从服务器的参与中受益；系统中的成员同时扮演服务器与客户端的角色；系统应 用的用户能够意识到彼此的存在，构成一个虚拟的或实际的群体”。 总之，p 2 p 技术就是在不同用户之间，不通过中继设备直接交换数据和服务的技术。 p 2 p 网络中任意节点既可以作为服务器为其它节点提供数据和服务，又可以作为客户机 享用其它节点提供的数据和服务。随着p 2 p 的飞速发展，因特网的存储模式将由目前的 “内容位于中心 模式转变为“内容位于边缘模式。 2 1 2p 2 p 技术特点 p 2 p 以其独特的技术特点，成为当今文件共享的理想平台。p 2 p 的技术特点主要体 现在以下几个方面： ( 1 ) 分散化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有节点上，通过各个节 点间的合作，直接在节点之间完成内容的传输和服务的实现，避免了中心存储和内容交 换可能存在的瓶颈。 ( 2 ) 可扩展性( s c a l a b i l i t y ) ：在p 2 p 网络中，节点在获取资源的同时也为其它节点提 供服务。随着网络节点数目不断增加，虽然服务的需求增加了，但是系统整体的资源和 服务能力因更多节点的分担也在同步地扩充，即p 2 p 系统的服务能力能够随需求的增长 江南大学硕士学位论文 而增长。此外，针对结构化p 2 p 网络中路由跳数典型值l o g n ，随着增加跳数增量非 常少，通信效率可保持在较高水平。 ( 3 ) 健壮性( r o b u s m e s s ) ：p 2 p 有很强的自适应性，天生具有耐攻击、高容错的优点。 p 2 p 的服务是分散在各个节点之间进行，因此，部分网络或节点遭到破坏对其它部分的 影响很小【2 l 】。p 2 p 网络通常在部分节点失效时能够自动调整整体拓扑，从而保持其它节 点的连通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和 离开，还能够根据网络带宽、节点数、负载等变化不断地做自适应式的调整。 ( 4 ) 高性能价格比( h i g hp e r f o r m a n c ep r i c er a t i o ) ：随着硬件技术的发展，个人计算 机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长【2 1 1 。采用p 2 p 架构可以 有效地利用互联网中散布的大量普通结点，将内容交换、计算任务或存储资料分布到所 有结点上。通过利用网络中的大量空闲资源如：计算能力或存储空间，可以用更低的成 本提供更高的计算和存储能力，从而达到高性能计算和海量存储的目的。 ( 5 ) 隐私保护( p r i v a c yp r o t e c t i o n ) ：p 2 p 网络信息的传输在各节点之间进行，无需经 过某个集中环节，因此，用户的隐私信息被窃听和泄漏的可能性大大缩小。目前互联网 主要采用的中继转发的技术方法，将通信的参与者隐藏在众多的网络实体之中，很大程 度上解决互联网隐私问题，而在传统的一些实现匿名通信的系统中也是依赖于某些中继 服务器节点。而在p 2 p 网络中，每个节点都可以提供中继转发的功能，因此匿名通讯的 灵活性和可靠性大大增强了，从而提供更好的隐私保护【2 。 ( 6 ) 负载均衡( p a y l o a db a l a n c e ) ：p 2 p 网络将资源和服务分散的分布在网络中，减少 了对集中服务器性能的依赖，更好的实现了网络的负载均衡。此外，通常使用的一致性 散列函数使得所有节点大致均匀的分布在覆盖网中，所有资源也大致均匀的分布在节点 中，即使有新节点加入，旧节点离开也能够进行动态的调整保持很好的负载均衡。 2 1 3p 2 p 的应用 p 2 p 具有广泛的应用前景，核心应用的研发主要聚焦在以下几个方面： 1 ) 文件共享 文件共享指网络上各个节点直接进行文件的传输与共享，p 2 p 技术使得任意两台相 连的计算机间共享文档、多媒体和其他文件成为可能。典型例子有n a p s t e r 2 2 1 、g n u t e l l a i s 和文件下载工具b t 2 3 】等。 2 ) 分布式计算 分布式计算是将巨大的计算任务分解，分发给网络中若干计算机分别执行，再将计 算结果进行归纳整合，从而开发每个节点潜力，利用了它们的空闲资源。美国柏克利大 学的s e t i h o m e l 2 4 1 研究计划就使用p 2 p 计算方法来分析星际间无线电信号。 3 ) 协同工作 协同工作是指一起工作的多个用户相互之间共享着不同的因特网资源，但他们通过 利用网络中的协同计算平台协同完成一项共同任务。协作工作中的一个用户可以同时将 6 第二章p 2 p 及信息检索 一个信息多点传送到若干个用户【2 0 1 。美国l o t u s 公司创办g r o o v en e t w o r k 2 5 】就是最为著 名的p 2 p 协作工作应用之一。 4 ) 即时通信 即时通信软件是i n t e m e t 上非常流行的软件，目前的即时通信技术通常也会采用一 个集中服务器控制着认证等基本信息，节点之间直接进行通信。即时通信应用在国内最 著名的有q q ，p o p o ，国外著名的有m s nm e s s e n g e r 、s k y p e 、i c q 、g o o g l et a l k 等。 5 ) 信息检索技术 目前的p 2 p 共享软件大多支持p 2 p 方式的专用搜索。随着网络信息量增加，p 2 p 技 术能够使用户尝试更深度的文档搜索，而且这种搜索无需通过w e b 服务器中转，也可以 不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度【2 0 1 。 6 ) 其他应用领域 除了上述几种应用之外，还有其他的一些应用模式，包括分布式存储、多媒体传输 和应用层组播等，并且随着研究的深入，p 2 p 技术会在更广泛的领域内得到应用。 2 2p 2 p 信息搜索技术 p 2 p 以其独特的技术特点成为近几年来的研究热点，研究界提出的p 2 p 信息检索的 理念，把p 2 p 与信息检索相集成，充分发掘各自的优点并相互克服对方的不足，依据 p 2 p 技术开发出的强大搜索工具可以弥补传统搜索引擎无力深度搜索的不足。 2 2 1p 2 p 信息检索的特点 p 2 p 信息检索通过分布式存储和处理能力为大范围的w e b 文件搜索提供可能，目前 基于传统的搜索技术最出色的全文搜索g o o g l e 只能搜索到2 0 3 0 的网络资源，而一 个设计良好的p 2 p 搜索将远超过这一数字。另外，传统式的搜索引擎对于数据的更新缓 慢不能满足用户实时性要求。受网络爬虫采集信息能力的限制，传统的搜索引擎很难进 行深度采集深层次的网页信息。相对于传统搜索引擎，p 2 p 信息检索具有以下特点： 分布式：网络中的数据以分布式大规模存在，p 2 p 结构的分布式特性适应了这种搜 索需求。 可扩展性：目前大规模网络搜索系统的可扩展性都面临着挑战，p 2 p 系统可以将大 量的节点连接起来进行资源的管理和服务，在大规模网络中引入p 2 p 系统的各种先进技 术和方法，可以提高系统的处理能力。 鲁棒性：p 2 p 信息搜索不会出现传统集中式搜索引擎的单点失效、瓶颈效应的问题。 低成本：在p 2 p 网络中存在大量的边缘网络节点，可以充分利用这些节点的闲置资 源来提供服务，可以有效的降低成本，而一些自组织的节点，也可以降低系统的管理和 维护的成本。 7 江南大学硕士学位论文 可以挖掘深层网页：大部分在网站数据库中以动态网页形式的信息则无法用传统搜 索引擎通过对静态网页上的链接爬行采集来获取，通常情况下网站只有主动提供信息索 引以备检索。而p 2 p 的检索使信息的提供者可以作为一个节点加入p 2 p 网络，主动贡献 信息提供服务，使得可以搜索更加丰富的信息。 个性化搜索：p 2 p 信息检索可以更加容易的利用用户协作、分析节点兴趣偏好和地 理位置等特点，来更好的推进个性化搜索，从而更好的满足用户需求。 总之，p 2 p 信息检索弥补了传统搜索引擎的不足，引起了研究界的关注，目前，p 2 p 信息检索的研发还处于初始阶段，p 2 p 信息搜索应用有美国d i g i t a l 公司推出的依据p 2 p 理念的商业性搜索引擎p a n d a n g o 等。 2 2 2p 2 p 信息检索研究的问题 p 2 p 信息搜索技术一直是现代p 2 p 技术研究的重点。目前，虽然已有许多基于p 2 p 的应用系统，但如何在大规模、分散化和分布式的p 2 p 系统中构建准确、可扩展的信息 搜索与发现机制仍然是当前亟待解决的关键问趔2 6 1 。 p 2 p 信息搜索是指如何在p 2 p 网络中找到所需的资源，这个资源包括各种类型文件、 节点提供的服务、数据库中的数据等。p 2 p 的搜索也有很多种，包括元数据搜索、键值 搜索、全文搜索、数据库搜索等，而大规模网络的p 2 p 信息检索的搜索对象往往是各种 类型的w e b 文档，是以关键词查询的全文搜索。p 2 p 信息搜索的任务是：在大规模动态 性的p 2 p 网络中找到满足用户需求的一定质量与数量信息，同时花费系统可接受的网络 带宽消耗、单点可接受的计算消耗以及用户可接受的查询时间。对于p 2 p 信息搜索的研 究主要可分为搜索效率研究与表达方式研究两个方向。 搜索效率：是考虑在给定表达方式的条件下，缩短搜索时间，降低搜索消耗( 包括 节点内存和网络带宽) 。该类研究的关键环节是解决空间开销与时间开销的折衷问题。 表达方式：研究的目的是丰富搜索功能，达到w e b 信息检索( w e bi n f o r m a t i o nr e t r i e v a l ) 甚至数据库检索( d a t a b a s ei n f o r m a t i o nr e t r i e v a l ) 的水平，这方面的研究题目包括关键词搜 索( k e y w o r d ss e a r c h ) 和复杂形式的键码查询( k e yl o o k u p ) 等。 上述两个研究思路直接关系着搜索的性能，并决定了p 2 p 系统的搜索问题其他方面 的研究。搜索的性能包括查询响应时间、查询结果质量。而搜索效率和查询结果质量也 存在折衷问题。如何在大规模动态环境下保证p 2 p 搜索的性能也是p 2 p 信息检索的关键。 p 2 p 系统搜索问题其他方面的研究还包括负载平衡、可扩展性、可用性、安全性等技术。 2 3p 2 p 信息搜索的分类 p 2 p 网络的体系结构决定p 2 p 的信息搜索机制，从而决定p 2 p 信息搜索的性能。不 同的p 2 p 网络表现出不同的搜索机制。对于已经应用或正在处于理论研究阶段的各种 p 2 p 网络，国内外的学者从多个不同角度对它们进行分类，包括从体系结构、出现时间 8 第二章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 网络呈现出不同的搜索机制。 2 3 1 集中式p 2 p 网络的搜索 集中式p 2 p 网络是c s 和p 2 p 两种模式的混合，它反映了p 2 p 工作模式从c s 到 p 2 p 的过渡，代表性的p 2 p 网络有n a p s t e r 2 2 j 。 以n a p s t e r 为例，n a p s t e r 有两个部分组成，n a p s t e r 网站和n a p s t e r 节点，如图2 1 所示，n a p s t e r 网站可以看成是服务器机群，每个服务器保存一部分用户共享文件索引 信息，所有服务器互联整合起来对外面的用户提供服务。每个用户连接到机群中的一台 服务器。服务器记录相连用户的共享文件信息和用户位置，并做成索引添加到索引表中。 图2 - 1n a p s t e r 的搜索 f i g 2 - 1t h es e a r c hi nn a p s t e r 当用户想要查询一个文件时，将查询( q u e r y ) 消息发送给与其相连的服务器，该服务 器收到查询消息后，与其它服务器协作处理查询消息，处理完成后，将回复( r e s p o n s e ) 消息返回给用户，回复消息包含所有查到的匹配文件的索引，用户可以根据相应机制选 择需要的文件，并根据索引中文件所对应的位置跟相应用户直接建立连接进行文件下 载。 这种查找方式的优点是查找效率较高且易于管理，但集中式目录服务器容易成为单 点失效和性能瓶颈，系统的稳定性和可用性不高。 2 3 2 非结构化p 2 p 网络的搜索 非结构化p 2 p 网络是以分布、松散的结构来组织的网络。网络中不再有集中服务器 的存在。非结构化p 2 p 网络中g n u t e l l a 8 1 是最简单最具代表性的，以g n u t e l l a 为例，网 络中所有参与的节点都是对等的，各对等节点之间直接通信，一个新对等节点首先访问 9 江南大学硕士学位论文 某特殊站点提供“主机缓存服务 得到该节点的活动地址，将自己接入到g n u t e l l a 网络， 之后，该节点通过探测网络中其它对等机找到与之相邻的节点。 如图2 2 所示，当用户进行文件查找时，该节点首先向所有与之相邻的节点发送查 询消息，其它节点接收到该消息之后，检查本地是否有符合查询请求的文件内容，如果 有则按查询消息发送的路径返回一个查询响应，无论本地是否有符合查询的内容，其它 节点都会将查询包以扩散的方式在网络中继续传递，直到查询包中的t t l ( t i m eo f l i f e ) 的值为0 时才停止转发。 这类网络的采用的是“洪泛”方法发布请求、搜寻资源，具有较高的稳定性。但大部 分情况下效率较低，定位稀疏资源困难，系统的扩展性差。 2 3 3 结构化p 2 p 网络的搜索 “卜q u e r y 一。l c s p o n 图2 - 2g n u t e l l a 的搜索 f i g 2 - 2 t h es e a r c hi ng n u t e l l a 结构化p 2 p 网络对文档在系统中的存放位置有严格的控制并且节点之间的关系比 较紧凑。结构化p 2 p 网络是建立在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 之上【l 引，它 通过对文件的内容特征进行哈希变换的得到一个m 比特长的文件标识，通过对节点i p 地址等进行哈希变换得到节点标识，整个标识空间被划分为很多个区域，每个区域包含 了若干连续的标识符，p 2 p 覆盖网中每个节点负责这些区域中的一个或多个。文件信息 被存储在负责这个标识符区域的相应节点中，文档的加入和查找都是通过标识符来进 行，标识空间区域的划分和每个节点负责的区域都可以随着节点的加入和退出进行动态 调整的。一般情况下，文件信息被存储在与该文件标识最接近的节点标识对应的节点之 中。 目前的结构化p 2 p 网络包括c h o r d ，p a s t r y ，t a p e s t r y ，k a d e m l i a 等。结构化p 2 p 网 络的最大优点在于它可以在o ( 1 0 9 a z ) ( 其中是系统中节点的数目) 的跳数之内完成文档 的路由和定位。结构化p 2 p 网络的技术特点是自组织、可扩展、负载均衡以及较好的容 错性。和非结构化p 2 p 网络主要用于文件共享领域不同，结构化p 2 p 网络的这些优良特 性使得它可以应用在对可靠性和扩展性要求比较高的场合。结构化p 2 p 网络的路由算法 将在本文第三章具体介绍。 1 0 第二章p 2 p 及信息检索 2 3 4 混合式p 2 p 网络的搜索 混合式p 2 p 网络是由集中式拓扑和非结构化拓扑结合而成的，混合式p 2 p 网络最简 单最具代表性的是k a z a a t z 7 。 对于k a z a a 网络，选择性能( 包括处理，存储，带宽等方面的性能) 较高的节点 作为超级节点，各超级节点之间形成非结构化拓扑，每个超级节点与一些普通节点形成 集中式拓扑，即每个超级节点采用“文件索引”将文件标识符映射其相应的位置，这些 文件索引分布在k a z a a 超级节点中，每个节点为其所有的子普通节点共享的文件保存 一个本地索引。k a z a a 超级节点很像一台n a p s t e r 服务器，但与n a p s t e r 不同的是k a z a a 超级节点不是恒定的，永久的。搜索发现算法在超级节点间转发，超级节点再将查询信 息转发给适当终端节点。 卜q u e r y卜r e s p o n s e 图2 - 3k a z a a 的搜索 f i g 2 3 t h es e a r c hi nk a z a a 如图2 3 所示，当用户想要查询一个文件时，将带有文件关键词的查询消息发送给 其父超级节点，超级节点在自己的数据库里寻找匹配的文件索引，并把收到的消息发给 与它相连的一些超级节点，但查询只能发生在很小的一个超级节点集里，最后返回给用 户文件所在的一些节点的位置。 混合式p 2 p 网络的搜索易于管理，而且搜索性能及可扩展性都有提高，但是网络高 度依赖超级节点，易受攻击，容错性不高。 2 3 5 几种p 2 p 信息搜索的比较 从上面的几种p 2 p 信息搜索的介绍可以看出，不同拓扑结构的p 2 p 网络具有不同的 搜索机制并表现出各自的优缺点。目前，对于大规模w e b 范围的p 2 p 信息检索主要采 用的是非结构化和结构化两种结构。非结构化p 2 p 稳定性强，易维护，且支持复杂查询， 但是搜索效率低，可扩展性差。结构化p 2 p 定位资源效率高，扩展性好，比较适合大规 模w e b 范围的p 2 p 信息检索，需要解决的就是维护开销等问题。 江南大学硕士学位论文 2 4 本章小结 本章介绍了p 2 p 技术的基本概念，包括技术特点和应用领域。通过对比当前通用信 息搜索分析了p 2 p 和