（计算机应用技术专业论文）结构化p2p关键词搜索模型的研究.pdf

i i i i 1 111l l l l l l i i l l1 11i l l u i iy 17 9 7 9 7 7 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文套秀枸仳p 2 | p 矢 建；习般蒙李萸型酋勺研完 系本人在 南开大学工作和学习期间创作完成的作品，并已通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库”。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解直珏太堂图盘鱼差王堡在! 僮旦堂鱼迨塞的筐堡壶洼滏! 同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文在保密期限过后同样适用。 院系所名称：力杀怎坡季、升学学腭 作者签名：物一孝 学号： l o0 5q4o 黾 日期：砒年乡月多日 、 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：枷一碎 歹口扩莎年芗月 之日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 枷一李禾 ) 矿秽5 年5 月 乡e 1 摘要 摘要 对等网络( p 2 p ) 是一种采用分布式体系结构的网络，也是当今一个迅速发 展的研究领域。现有的p 2 p 系统网络规模大、动态性高、异构性强，有效的搜 索技术一直是p 2 p 系统研究中的核心问题，而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 ) 建立的p 2 p 系统在广域网支 持巨量级的数据一致性分布，并提供可度量的低跳步路由算法来进行精确定位， 同时具有高容错性。但分布式散列函数只适于精确的查找，而在p 2 p 应用系统 中，通常需要提供对关键词查询等非精确查找机制的支持。 本文深入分析结构化p 2 p 网络本身的特点，结合搜索引擎核心技术中的分 词索引技术，提出了支持多关键词搜索的资源发现模型k r d m ( k e y w o r d s r e s o u r c ed i s c o v e r ym o d a l ) ，它通过将 分发到p 2 p 系统节点， 然后建立资源簇的方法来提供多关键词查询。在此基础上，本文还利用l s h 技 术对关键词的映射机制进行改进，体现出相似关键词相邻存储的特性，从而能 够搜索出与关键词相近的内容。这种方案使得相似关键词由相同节点维护的可 能性大大增加，而且对于关键词输入错误具有一定的容错能力。 k r d m 模型建立于全分布式结构化网络，具有良好的可扩展性，同时独立 于o v e r l a y 层所使用的协议，可重用性强。最后，本文还针对互联网资源的“热 点现象对o v e r l a y 协议提出了改进方案，旨在减轻关键词映射带来的负载不均 衡问题，合理分配p 2 p 系统中资源的分布。 通过仿真实验，k r d m 能够在不增加路由复杂度的基础上，。实现多关键词 查询，同时支持相似关键词的搜索，并能达到较高的准确度。此外，利用捎带 查找优化的节点分配方案也能够将“热点 节点的负载有效降低，使新加入节 点向着“热点 汇聚。 关键词：结构化p 2 p ，覆盖网络，关键词搜索，倒排文件，相似散列函数 a b s t r a c t a b s t r a c t p e e rt op e e rn e t w o r k , b u i l to nd i s t r i b u t e ds y s t e m s ，h a sb e c o m ear e s e a r c ha r e ao f r a p i dg r o w t h c u r r e n tp 2 ps y s t e m sa r eg e n e r a l l yl a r g e s c a l e ，h i g h l yd y n a m i ca n d i s o m e r o u s ，s oh o wt oc r e a t ea l le f f e c t i v es e a r c hm e c h a n i s mi sac o r ei s s u eo fp 2 p r e s e a r c h t h ee f f e c t i v e n e s so fs e a r c hm e c h a n i s mi np 2 pn e t w o r ki se m b o d i e di n s t a b l el o c a t i n ga n dl o wc o s t c e n t e r e dp 2 pr e q u i r e sap o w e r f u li n d e xs e r v e r , w h i c h c a l le a s i l yr e s u l ti ns i n e j e - p o i n tf a i l u r ea n db o t t l e - n e c k ；f l o o d i n g - b a s e ds e a r c hi s s o m e w h a tb l i n da n ds u f f e r sf r o mal a r g ew a s t eo f b a n d w i d t h p 2 ps y s t e m sb u i rt h r o u g hd h t ( d i s t r i b u t e dh a s ht a b l e ) c a i ls u p p o r tc o n s i s t e n t d i s t r i b u t i o no fm a s s e so fd a t a0 1 1w a n ，a n dp r o v i d em e a s u r a b l er o u t i n ga l g o r i t h m s w i t has m a l ln u m b e ro fh o p sa n dg r e a tr o b u s t n e s s t h o u g h , d h ti so n l ys u i t a b l ef o r a c c u r a t es e a r c h i n gw h i l es e a r c ht e c h n i q u e sl i k ek e y w o r d - b a s e ds e a r c ha r ea l w a y s r e q u i r e di np 2 pa p p l i c a t i o n s a f t e rm a k i n gad e e pa n a l y s i so fp 2 pn e t w o r k sf e a t u r e s ，t h i st h e s i sp r o p o s e sa 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 y m o d e lk r d m ，w i t hw o r dp a r t i t i o n i n ga n d i n d e x i n gt e c h n i q u e si ns e a r c he n 出ei n t e g r a t e d t h i sm o d e ld i s t r i b u t e s p a i r st on o d e si np 2 ps y s t e m sa n dt h e ni m p l e m e n t sm u l t i - k e y w o r ds e a r c h b yc r e a t i n gi n v e r t e di n d i c e s b e s i d e s ，t h i st h e s i sa l s oi m p r o v e sk r d m sk e y w o r d m a p p i n gi nv i r t u r eo fl s h ( l o c a l i t ys e n s i t i v eh a s h i n g ) ，w h i c hc a np r o b a b l ym a k e s i m i l a rk e y w o r d sm a i n t a i n e db ys a m en o d e s i nt h i sw a ys i m i l a rw o r d sc a nb ef o u n d b yd h tm a p p i n ga tt h es a m en o d e ，a n de r r o rt o l e r a n c ec a na l s ob ep r o v i d e dw i t h g e n e r a li n p u tm i s t a k e si nk e y w o r d s c r e a t e d0 1 1 f u l l y d i s t r i b u t e ds t m c t u r e d o v e r l a y , k r d m e x h i b i t sw e l l s c a l a b l e n e s s ，a n di ti sh i g h l yr e u s a b l eb e c a u s eo fi t si n d e p e n d e n c eo ft h eu n d e r l y i n g o v e r l a yp r o t o c 0 1 a i m i n ga t h o ts p o t b r o u g h tb yk e y w o r dm a p p l i n g , t h i st h e s i sa l s o d i s c u s s e sh o wt oi m p r o v eo v e r l a yp r o t o c o lt or e d u c eo v e r h e a di m b a l a n c ea n d o r g a n i z er e s o u r c ed i s t r i b u t i o nr e a s o n a b l y t h r o u g hs i m u l a t i o nt e s t s ，i ti sp r o v e dt h a t k r d mc a ni m p l e m e n tm u l t i - k e y w o r d n 垒! ! 堕 s e a r c hw i t h o u ti n c r e a s i n gr o u t i n gc o m p l e x i t ya n di t ss i m i l a r i t ys e a r c ha l s oa c h i e v e sa c o n s i d e r a b l e a c c u r a c y m o r e o v e r , i d e n t i f i e rd i s t r i b u t i o ns c h e m eo p t i m i z e db v a c c o m p a n y i n gl o o k u pc a l le f f e c t i v e l yr e d u c e ”h o ts p o t ”n o d e s o v e r h e a da n dn e w j o i n i n gn o d e sw i l lg a t h e ra r o u n dt h e mg r a d u a l l y k e yw o r d s ：s t r u c t u r e dp 2 p , o v e r l a yn e t w o r k , k e y w o r ds e a r c h , i n v e r t e df i l e ，l s h 目录 目录 第一章绪论l 第一节研究背景。1 第二节w e b 搜索与p 2 p 搜索2 1 2 1w e b 搜索引擎。2 1 2 2p 2 p 搜索技术3 1 2 3 评价p 2 p 搜索技术的标准3 第三节p 2 p 搜索的研究现状4 第四节问题的提出5 第五节论文的主要内容7 第二章p 2 p 技术综述9 第一节从n a p s t e r 说起9 第二节p 2 p 网络拓扑结构1 0 2 2 1 中心化拓扑1 0 2 2 2 全分布式非结构化拓扑1 1 2 2 3 全分布式结构化拓扑1 1 2 2 4 半分布式拓扑1 3 第三节p 2 p 网络的搜索算法1 3 2 3 1p 2 p 搜索算法的意义1 3 2 3 2 集中索引模式1 4 2 3 3 非结构化搜索模式1 4 2 3 4 结构化搜索模式1 5 第四节影响p 2 p 发现算法的重要因素1 6 2 4 1 度数和直径的折衷关系1 6 2 4 2s m a l lw o r l d 理论l7 2 4 3 语义查询18 2 4 4 面临的困难1 8 目录 第三章关键词搜索模型( m m ) 19 第一节k r d m 概述。1 9 3 1 1 设计思想1 9 3 1 2 模型结构2 3 3 1 3 应用环境。2 5 第二节k r d m 中的关键词搜索。2 6 3 2 1 提取关键词2 6 3 2 2 关键词映射2 7 3 2 3 分布式索引的建立2 8 3 2 4 再映射机制：3 2 3 2 5k r d m 搜索过程3 4 3 2 6 性能优化3 6 第三节k r d m 中的相似搜索3 9 3 3 1 拼写错误与相似搜索3 9 3 3 2 结构化网络中的解决方案4 0 3 3 3l o c a l i t ys e n s i t i v eh a s h i n g 4 1 3 3 4 利用n - g r a m 进行相似映射。4 3 3 3 5 相似搜索过程4 5 第四节关于“热点问题4 6 3 4 1 出现的原因4 6 3 4 2 节点空间分配的重要性4 7 3 4 3 解决方案4 7 第五节模型评估：。51 3 5 1 功能评估51 3 5 2 性能评估5 2 第六节k r d m 改进方向。5 4 第四章仿真实验5 6 第一节实验目的和环境5 6 第二节k r d m 的仿真5 7 4 2 1p l a n e t s i m 结构5 7 目录 4 2 2 实验内容5 9 4 2 3 代码实现6 0 第三节实验结果与分析6 2 第五章总结和展望一6 5 第一节论文的总结6 5 第二节后续工作的展望6 5 参考文献6 7 致谢。7 0 附录。7 1 附录a ：图索引7 1 附录b ：表索引7 1 个人简历、在学期间发表的学术论文与研究成果7 3 第一章绪论 第一章绪论 第一节研究背景 9 0 年代，c s 模式开始流行。这种模式将网络应用一分为二，服务器负责 数据管理，客户机完成与用户的交互。c s 模式具有强壮的数据操纵和事务处理 能力，以及数据的安全性和完整性约束。 但是随着互联网应用的飞速发展，网络用户群的迅速壮大，网络中交互的 信息量呈爆炸式增长的趋势，单服务器系统成了性能瓶颈。并行处理技术一定 程度上缓解了问题，它通过协调多个处理器和多个服务器来扩大服务系统的应 用规模，但未从根本上改变系统的服务模式。c s 模式的缺陷在日益增长的计算 需求的环境下开始突显，这种模式很难满足这些新的需求： ( 1 ) 抗d o s 攻击的需求。服务器是网络中最易受到攻击的节点，而一旦服 务器受到破坏，系统中的客户机都无法正常工作。 ( 2 ) 对网络信息源的准确定位。计算机网络上的信息增长速度惊人，搜索 引擎对于信息的变动更新具有一定的滞后性，搜索结果可靠性有待改进。 ( 3 ) 网络负载均衡的需求。单个服务器的性能不但取决于其软硬件配置， 还受到带宽的限制。c s 模式的应用使得客户系统的运算能力和网络带宽未能得 到有效利用，造成了整个互联网资源的浪费。 ( 4 ) 永久存储的需求。显然，单服务器系统难以满足任何时候，任何地点 都能访问有效数据这样的需求。 p 2 p 的出现改变了互联网现在的以大网站为中心的状态，使网络应用系统重 返“非中心化，并把权力交还给用户。 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源 ( 处理能力、存储能力、网络连接能力) ，这些共享资源需要由网络提供服务和 内容，能被其他对等节点( p e e r ) 直接访问而无需经过中间实体。在此网络中的 参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源获取者( c l i e n t ) 。 p 2 p 作为分布式网络系统，具有许多优于传统网络系统的特征： ( 1 ) 非中心化( d e c e n t r a l i z a t i o n ) ：网络中资源和服务分散在所有节点上，信 第一章绪论 息的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的 介入，避免了可能的瓶颈，带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 3 ) 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。 ( 4 ) 高性价比：采用p 2 p 架构可以有效地利用互联网中散布的大量普通节 点，将计算任务或存储资料分布到所有节点上，充分利用这些闲置的计算能力 或存储空间。 ( 5 ) 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而 无需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。 ( 6 ) 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减 少了对传统c s 结构服务器计算能力、存储能力的要求，更好的实现了整个网 络的负载均衡。 1 2 1w e b 搜索引擎 第二节w e b 搜索与p 2 p 搜索 搜索引擎的原理是起源于传统的信息全文检索理论，即计算机程序通过扫 描每一篇文章中的每一个词，建立以词为单位的排序文件，检索程序根据检索 词在每一篇文章中出现的频率和每一个检索词在一篇文章中出现的概率，对包 含这些检索词的文章进行排序，最后输出排序的结果。 互联网搜索引擎除了需要有全文检索系统之外，还要有所谓的“蜘蛛” ( s p i d e r ) 系统，即能够从互联网上自动收集网页的数据搜集系统。当然，一个 完整的搜索引擎系统还需要有一个检索结果的页面生成系统，也就是要把检索 结果高效地组装成万维网页面。 搜索技术的未来发展体现在高效和智能两个方面。自然语言理解通过建立 一种计算机模型，能够像人那样理解、分析并回答自然语言。以这种技术为基 础的新一代搜索引擎，称之为智能搜索引擎。它将信息检索从目前基于关键词 层面提高到基于知识( 或概念) 层面，对知识有一定的理解与处理能力，能够实现 2 第一章绪论 分词技术、同义词技术、概念搜索、短语识别以及机器翻译技术等。 1 2 2p 2 p 搜索技术 随着宽带技术的发展，未来的互联网是多媒体数据的时代，图像、视频将 很快取代文本成为互联网上主要的信息。但搜索引擎远远无法涵盖互联网中所 有的共享内容，如互联网上的动态网页、存储在边缘网络主机上的共享信息资 源，都是大型搜索引擎无法触及到的。 随着p c 存储技术和处理器的迅速发展，作为互联网上的叶节点的个人电脑 并不缺少信息资源，也不缺乏足够的处理能力，只是由于在其上的资料无法被 搜索、无法被他人知晓，而不能够被共享。此外，个人计算机也拥有大量的空 闲的计算资源被浪费。 ， p 2 p 搜索技术通过让所有信息提供者共同构建一个庞大的分布式搜索引擎 的方式，可以将信息检索服务延伸到这些大型集中搜索引擎无力触及的地方。 所以，p 2 p 搜索可以成为传统搜索的一个良好的互补。 1 2 3 评价p 2 p 搜索技术的标准 评价p 2 p 搜索的标准基本上分为两个方面：从用户的角度以及从网络的角 度。好的搜索技术可以使用户能够有效的定位需要的内容，用户评价p 2 p 搜索 技术的好坏，主要从以下几方面： ( 1 ) 返回的结果数量，指一次查询能够找到多少结果。 ( 2 ) 满意程度，由于查询结果众多，结果的内容如果能够较好地反映用户 提交查询的需求，就说查询是令人满意的。 ( 3 ) 响应时间，指用户从发起查询开始到接收到结果等待的时间。 从网络的角度来评价p 2 p 搜索技术，主要包括效率、可扩展性及健壮性。 ( 1 ) 搜索效率，查询请求信息在网络中扩散，许多节点都要花费资源( 如 c p u 、时间、存储空间) 进行处理，看是否有满足要求的内容或要转发查询请求， 这同时也消耗了带宽资源。高效率的p 2 p 搜索技术应该能以尽量少的资源消耗 获得满意的搜索效果。 ( 2 ) 可扩展性，p 2 p 网络的规模一般很大，而且增长快速。p 2 p 搜索方法 必须能够适应网络对可扩展性的要求，及时有效的搜索到用户需要的资源。 第一章绪论 ( 3 ) 健壮性，p 2 p 网络从来都不是静止不动的，在网络中节点频繁加入或 退出。根据对g n u t e l l a 的统计，4 0 的节点在线的时间少于4 小时，只有2 5 的 节点在线超过2 4 小时。因此，p 2 p 搜索方法应具有良好的健壮性，将网络动态 变化的影响降到最低。 第三节p 2 p 搜索的研究现状 虽然目前有许多基于p 2 p 的应用系统，但如何在大规模、分散化和分布式的 p 2 p 系统中构建灵活、可扩展的信息搜索与发现机制仍然是当前亟待解决的关键 问题。 n a p s t e r 是历史上第一个获得大规模应用的p 2 p 系统，它采用的是中心化p 2 p 的拓扑结构。在中心化p 2 p 系统中，资源搜索模型由一个中央服务器和许多客 户机组成，服务器上存放着所有共享资源的索引。为了定位一个文件，用户向 中央服务器发出包含有资源标识符的查询请求。这种资源发现机制是集中式的， 它具有不易扩展并且存在单点失效的缺点。 在非结构化p 2 p 系统中，没有索引服务器，它采用了基于完全随机图的洪 泛发现，每个节点都维护着与其邻居的常量数量连接，形成o v e r l a y 网络。因此， 发现的准确性和可扩展性是非结构化网络面临的两个重要问题，目前对此类结 构的研究主要集中在改进发现算法和复制策略以提高发现的准确率和性能。 在1 2 9 1 提出了一种基于路由转发的网格资源发现模型。每个资源路由器都 是对等的实体。资源路由表信息定期更新，解析资源查询请求时，根据路由表 进行转发。在 3 0 1 1 7 a r i a 等提出了一种符合o g s a 规范网格的资源发现的p 2 p 体系结构。此结构由两层组成，底层由索引服务组成，负责发布每个虚拟组织 中的信息。高层是p 2 p 层，负责收集和分布信息，p e e r 服务之间通过采用扩展 的g n u t e u a 协议来交换消息。在 3 1 中m a s t r o i a n n i 等采用了超级节点模型设计基 于p 2 p 的网格信息服务。超级p e e r 作为普通p e e r 的中央服务器，超级p e e r 之间 构成p 2 p 的覆盖网络。超级节点模型适用于大规模的网格环境。资源发现过程 是：某个网格节点发出的查询消息被转发到超级p e e r 。如果超级p e e r 在本地找 到所请求的资源，则向请求节点发送响应；如果没找到则将请求转发到被选择 的超级p e e r 邻居，并重复以上过程。 在结构化的p 2 p 系统中，资源和p e e r 都是通过分布式散列表来进行定位和 4 第一章绪论 查找的。d h t 是p 2 p 系统的一种数据放置策略，对于一份标识为d a t a l d 的数 据，将其d a t a l d 通过散列函数映射到地址空间( 这个地址空间即为支持这个d h t 的结构化p 2 p 系统的地址空间) 中的某个位置h a s h l d ，规定该数据必须放置在 当前所有节点中n o d e l d 离h a s h l d 最近的节点上。d h t 的实现必然需要有消息 通信机制保证任意节点都可以与离某个h a s h l d 最近的节点进行通信，而这正是 结构化p 2 p 系统的通信语义。因此结构化p 2 p 系统很好地支持了d h t 的实现。 s c h m i d t 在 3 2 1 提出了用单个d h t 支持多属性查询。多维属性值用空间填 充曲线映射到一维空间。每个资源映射到的节点i d 通过计算属性值获得。查询 向和目的i d 的共同前缀位比当前节点多一位的节点进行转发。r a t n a s a m y 等在 3 3 中提出了利用一致散列函数在节点间均匀分布存储负载的系统。由于属性值的 局部性并未保持，在底层的d h t 上构建了一层覆盖以有效地进行区段查询。每 个属性对应不同的t i e r 树，t i e r 树的根节点分配了该属性的全部值空间。资源向 每个属性对应的t i e r 树的叶子节点进行注册。初始化时，仅有根节点存在，所有 的资源注册到根节点上。 上述不同结构的p 2 p 系统所运用的资源发现模型具有各自的优势和缺陷。 集中式的p 2 p 系统可以在中央服务器建立完备可靠的索引，可支持各种复杂的 查询，还可以通过数据挖掘分类技术及语义相关技术提供智能搜索服务，但中 央服务器随着系统节点容量和资源数量的增大，性能会受到很大的影响，易产 生单点故障。无结构化的p 2 p 系统可以方便地支持多关键词查询、部分查询等 复杂查询，但其以“洪泛 方式向邻居节点发送查询消息，可扩展性很差，且不 能确保搜索到系统中存在的全部资源。虽然提出了随机漫步算法类似的改进方 法，但都是以牺牲时间和网络覆盖率为代价。结构化的p 2 p 系统( 如c h o r d , c a n ) 具有高度的扩展性，其基于分布式散列表( d h t ) 将节点组织成一定结构的覆盖网 络，可以保证在一定的跳跃次数内查找到p 2 p 网络中存在的数据对象，但只能根 据资源的键进行准确匹配的查询，本身对于模糊查询和关键词查询的支持不够， 需要引入新的方法。 第四节问题的提出 p 2 p 系统的两种全分布式拓扑结构在各自的资源发现模型中，都有着相互不 可比拟的优势，但自身也有着无法避免的缺陷。 第一章绪论 首先，p 2 p 系统中的扩展性是一个很重要的问题。非结构化的p 2 p 系统在传 递查询的过程产生过多的流量，扩展性相对较差，路由性能没有理论保证。与 此相比，基于d h t 的p 2 p 系统将整个网络的资源按照全局方式组织起来进行查 找，能够自适应节点的动态加入或退出，有着良好的可扩展性、鲁棒性、负载 均衡等能力，符合大规模网络体系的应用要求。 结构化p 2 p 系统采用相容散列函数根据精确关键词进行对象的定位与发现， 这种精确的映射在提供稳定的查询性能的同时，也限制了查询的形式必须是完 整的资源描述符，这就无法通过多关键词和模糊查询来搜索需要的资源。另外， 相容散列函数总是试图保证生成的散列值均匀随机分布，结果两个内容相似度 很高但不完全相同的对象被生成了完全不同的散列值，存放到了完全随机的两 个节点上。 能不能将两种拓扑结构的优点有机的结合起来呢? 结构化p 2 p 的o v e r l a y 为上层网络应用主要提供的接口有两个：i n s e r t ( k e y , v a l u e ) 和l o o k u p ( k e y ) ，这两 个接口代表着结构化p 2 p 资源发现模型中最为关键的两个部分。常见的c h o r d ， c a n 等协议都是将整个资源描述符作为d h t 的输入参数，来得到最终发布到网 络中的k e y 。因此，必须在这两个关键部分进行改进，才能使结构化p 2 p 系统具 备支持复杂查询的能力。 资源描述符( d e s c r i p t o r ) 通常是指能够简要标识资源的字符串。对于p 2 p 文件共享应用来说，可以是文件名；对于网页搜索来说，可以是网页摘要；对 于d n s 应用来说，可以是域名。资源描述符通常是具有很强概括性的短文本 ( s h o r tt e x t s ) ，虽然是短文本，但仍是由合法的语义成分组成，这些语义成分共 同组成了完整的语义体。当前的语义分析技术可以提取文本中具有独立性的语 义成分，并且排除那些不具备实际意义或关键性意义的单词。 利用短文本的这样一个特点，可以将描述符分解成独立的若干个关键词或 词组，然后以这些词或词组为短描述符( s h o r td e s c r i p t o r ) 进行映射，在负责维护的 节点处建立倒排索引，存储所有与该关键词有关的资源。这样以来，多关键词 查询可以转化为分别满足每一个关键词的查询结果的交集。 关键词查询需要输入，而关键词的正确性在d h t 这种精确映射的机制中是 至关重要的。错误的关键词往往会导致没有任何查询结果返回。另一方面，结 构化p 2 p 是自组织的，资源的发布缺少集中式的管理，因此资源发布具有一定 的随意性，这种随意性也会带来资源描述符中关键词的错误。同时，对于资源 第一章绪论 描述符本身来说，并不是所有的关键词都是在语言辞典里存在的，因此不可能 通过内置语言辞典来消除这种错误。综上所述，有必要对d h t 映射机制过程中 的某个环节进行改进，使这类错误所造成的查询退化的程度达到最小。 结构化的p 2 p 网络如果支持关键词搜索，不可避免的要涉及到资源的内容， 由此就会引发出另一个问题，即互联网的“热点( h o ts p o t ) 现象。相容散列函 数对于完整描述符的映射能够消除描述符内容的相近性，形成负载均衡的特性， 但是，基于关键词的映射使这种特性发生了改变。因为关键词不是资源的唯一 描述符，而只是资源的属性，同一关键词可以对应多个资源，这就使得维护关 键词的节点负载和关键词的热度成正比。因此，要在结构化p 2 p 系统中建立支 持多关键词的搜索模型，负载均衡是要被重新审视的问题。 第五节论文的主要内容 作者通过查阅大量的国内外文献资料，比较系统全面的学习了有关p 2 p 网 络的知识，包括p 2 p 网络的发展，p 2 p 的特点、拓扑结构及协议，主要类型的结 构化网络以及p 2 p 网络搜索的各种技术等。本文在归纳总结当前主要p 2 p 搜索 技术和文本处理技术的基础上，深入研究了许多p 2 p 应用系统的体系结构和搜 索算法，提出了在结构化网络上支持多关键字搜索的资源发现模型，并利用l s h 对关键词映射机制进行补充，使之能够避免关键词错误带来的查询失败，并在 一定程度上支持相近关键词的搜索。此外，本文还针对多关键词映射带来的负 载不均衡的问题进行了讨论，并提出了一些优化方案。 本文的结构安排如下： 第一章介绍了课题的背景及研究意义、国内外的研究现状、论点的提出以 及结构安排。 第二章作为技术背景，全面的论述了p 2 p 各方面的内容，包括概念和特征、 网络拓扑分类、资源搜索机制及相关协议，此外还介绍了一些应用系统在资源 搜索方面的特点。 第三章是论文的核心部分，系统地阐述了本文提出的基于结构化p 2 p 的支 持多关键词搜所的资源发现模型k r d m 。它分为以下几个部分：第一部分是关 于k r d m 的概述，包括设计思想、体系结构和应用环境等；第二部分主要是讲 述k r d m 的关键词搜索功能的设计细节，包括预处理、关键词映射、索引结构、 第一章绪论 再映射机制以及优化方案等；第三部分介绍了相似搜索功能的设计实现，包括 背景分析、l s h 技术和n - g r a m s 的转化等；第四部分是针对搜索模型中的“热点 现象提出的方案；第五部分从不同角度对k r d m 模型进行了评估；最后部分总 结了k r d m 的特点和应用，并对改进方向进行了展望。 第四章是利用开源的p e e r s i m 系统进行的搜索模型的仿真模拟，通过模拟实 验的结果可以证明多关键词查询模型的正确性，以及对相似关键词的搜索的支 持。此外，通过实验还可以检验对“热点 现象的优化在负载均衡方面所体现 的作用。 第五章对论文的工作进行了总结，指出了文中的资源搜索模型的需要改进 的地方，为其指明了今后研究的方向。 8 第二章p 2 p 技术综述 第二章p 2 p 技术综述 第一节从n a p s t e r 说起 n a p s t c r 主要用于m p 3 文件共享，n a p s t e r 采用了集中式的目录服务器机制， 目录服务器集中存放对等节点节点的地址信息和所保存数据的信息。这种集中 式的目录服务器可以对请求的数据进行快速查找并能够返回最合适的目的节 点。实际的文件传输将在请求节点和目的节点之间通过t c p 连接直接进行。 和n a p s t e r 不同，g n u t e l l a 2 采用了完全分布式的策略，g n u t e l l a 可以被看成 是一组对等节点之间的自组网络。图2 1 描述了传统的客户服务器系统，n a p s t e r 系统和g n u t e l l a 系统的比较。 每个g n u t e l l a 节点都定义了本地的共享文件夹，它们可以根据文件名的部分 或者完全匹配进行查找。查找按照简单洪泛( f l o o d i n g ) 的方式进行，首先传播 到所有相邻节点，然后再传播到相邻节点的相邻节点，直到达到预先确定的层 次为止。每条查找消息都带有全局唯一的标识符，防止对同样的查找消息进行 多次响应。 r 譬衫瓢 篇囊r ( 1 ) s e a r c h ( 2 ) l o c a t i o n 2 舞恐 ( c ) g n i 叫i a f 穗锄吐类型的系统 图2 1 不同类型的p 2 p 系统 从上述系统的特点中可以看出对等网络具有的几个特点： ( 1 ) 没有服务器。这是和客户机服务器网络的最大的区别。在对等网络中， 没有服务器的概念，所以的对等节点都是客户机，也都是服务器。 ( 2 ) 可扩展性好。对等网络的规模随着加入节点的数量的增长而增长，新 第二苹p 2 p 技术综述 节点的加入会给系统增加新的资源，这种可扩展性几乎是无限的，理论上限是 现有的i n t e m e t 的规模。 ( 3 ) 完全对称。在对等网络中，所以的节点都是对称的，运行完全相同的 软件，完成完全相同的功能，这也是对等网络名称的由来。 上述这些文件共享对等网络系统都存在一个基本问题，就是缺乏有效的或 可扩展的查找机制。n a p s t 盯采用的是集中式的目录服务器，随着规模的增长， 服务器必然称为系统的瓶颈，而且容易造成单点故障。g n u t e l l a 和f r e e n e t 虽然 支持分布式的查找策略，但是都采用的是类似于o s p f 路由协议的洪泛机制，网 络通信负担较大，可扩展性也较差。 由于非结构化网络的出现，近年来许多研究小组在可扩展的查找机制方面 做了大量研究工作，主要集中在如何构造一个高度结构化的系统，最新的研究 成果体现在采用分布式散列表的完全分布式结构化网络。这些算法通过分布式 散列函数，将输入的关键字惟一映射到某个节点上，然后通过某些路由算法同 该节点建立连接。因此，要对p 2 p 有更全面的理解，还需要深入了解p 2 p 网络 的拓扑结构。 第二节p 2 p 网络拓扑结构 ， 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系， 节点之间的拓扑结构一直是确定系统类型的重要依据。p 2 p 系统一般要构造一个 非集中式的拓扑结构，在构造过程中需要解决系统中所包含的大量节点如何命 名、组织以及确定节点的加入离开方式、出错恢复等问题。 根据拓扑结构的关系可以将p 2 p 网络分为4 种形式：中心化拓手 ( c e n t r a l i z e d t o p o l o g y ) j 全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) ；全分 布式结构化拓扑( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ，也称作d h t 网络) 和半分 布式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 。 2 2 1 中心化拓扑 中心化拓扑最大的优点是维护简单， 接建立连接，但网络的构建需要服务器， 1 0 资源发现效率高。各节点之间可以直 通过集中认证，建立索引机制。然而 第二章p 2 p 技术综述 这里的服务器仅用于辅助对等节点之间建立连接，一旦连接成功，服务器不再 起动用，对等节点之间直接进行通信。这不同于c s 模式中的服务器，也可以 认为是马马化了服务器的作用。 中心化网络模式和全分布式网络相比，容易发现网络节点，管理方便且安 全性好。由于资源的发现依赖于中心化的目录系统，发现算法灵活高效并能够 实现复杂查询。 这种模型的缺陷在于中央索引服务器的瘫痪容易导致整个网络的崩溃，容 易造成单点故障，因此可靠性和安全性较低；随