（计算机应用技术专业论文）基于小世界模型的p2p网络文本检索.pdf

中文摘要 与集中式搜索引擎相比，构建在p 2 p 网络上的文本检索系统在可扩展性、数 据更新、维护成本和安全性等方面具有与生俱来的优势。由于p 2 p 网络中的节点 缺乏全局网络的拓扑知识，如何定位节点资源、减少网络节点之间的通信开销成 为p 2 p 网络中文本检索的核心问题。本文基于小世界模型研究了p 2 p 网络中的文 本检索问题，主要贡献如下： 针对向量空间模型中文档矩阵高维稀疏的问题，提出了一个p 2 p 网络节点文 档向量降维的方法。该方法将文档中词频出现两次以上的词条作为文档的摘要信 息，来表示节点文档内容，然后根据改进的s t c 算法为选出的词条建立了一个树 状的层次结构。在计算文档向量相似度时，采用s i g m o i d 函数为不同层次的词条 赋予不同的权重。 针对g n u t e l l a 网络中转发消息的泛洪问题，基于小世界模型提出了一种无 结构p 2 p 网络文本检索的方法。该方法中，p 2 p 网络的每个节点都维护一定数量 的短程连接邻居节点和长程连接邻居节点，由此来构建具有小世界特性的网络。 邻居节点的更新策略是在节点的查询和应答交互过程中进行的，每次查询结束 后，都会更新邻居节点文档向量中关键词的权重，使得节点能够动态地快速了解 网络的拓扑情况和其他节点的文档内容。实验结果显示，与g n u t e u a 网络相比， 小世界p 2 p 网络具有更大的聚类系数、较小的特征路径长度和更高的文本检索查 全率。 针对基于d h t 技术的结构化p 2 p 网络在不支持复杂查询、负载不平衡和路由 效率低等方面的问题，根据k l e i n b e r g 小世界模型设计了一个结构化p 2 p 网络协 议( s p p s w 协议) 。在s p p s w 协议中，内容相近的节点被划分到相同的节点类中， 在节点类的内部，节点可以根据相似程度选择邻居，网络由一些相互连接节点类 构成。节点类可以动态地调整节点类的大小，能够自组织地分裂、合并，节点类 之间存在一些长程连接，缩短了查询路由步数。实验结果显示，随着网络规模的 扩大，在s p p s w 协议网络中，搜索开销呈对数平方曲线增长，维护开销呈线性 增长；选择一个合适的节点类内部节点的数量，可以使得整体的网络维护开销和 搜索开销最小。 关键词：对等网络小世界现象文本检索覆盖网 a b s t r a c t c o m p a r i n gt ot h ec e n t r a l i z e ds e a r c he n g i n e ，t e x tr e t r i e v a ls y s t e m sb u i l to nt o po f p 2 pn e t w o r k sh a v ei n n a t es u p e r i o r i t yi ns c a l a b i l i t y , d a t au p d a t e ，m a i n t e n a n c ec o s t ， s a f e t y , a n ds of o r t h d u et ol a c ko fg l o b ek n o w l e d g eo fn e t w o r k st o p o l o g y , h o wt o l o c a t ed a t ai np 2 pn e t w o r k sa n dr e d u c ec o m m u n i c a t i o no v e r h e a db e c o m et h em a j o r i s s u e si nt e x tr e t r i e v a lu n d e rt h ep 2 pe n v i r o n m e n t i nt h i sp a p e r , p r o b l e m so ft e x t r e t r i e v a i np 2 pn e t w o r k sa r es t u d i e db a s e do nt h es m a l lw o r l dm o d e la n dt h em a i n c o n t r i b u t i o n sa r ea sf o l l o w s f o rt h ep r o b l e mo fh i g h d i m e n s i o n a l ，s p a r s ed o c u m e n t a t i o nm a t r i x ，t h i sp a p e r p r e s e n t sad i m e n s i o nr e d u c t i o nm e t h o dt od o c u m e n t si nn o d e so fp 2 pn e t w o r k s i n t h i sm e t h o d ，w o r d sw h i c ha p p e a rm o r et h a nt w i c ea r ep i c k e du pt or e p r e s e n tt h e c o n t e n to ft h en o d e s ，a n dt h e ni m p r o v e ds t ca l g o r i t h mi se m p l o y e dt ob u i l da h i e r a r c h i c a ls t r u c t u r ew i t ht h es e l e c t e dw o r d s i nt i l ec a l c u l a t i o no fd o c u m e n tv e c t o r s i m i l a r i t y , w o r d sa td i f f e r e n tl e v e l si nt h eh i e r a r c h i c a ls t r u c t u r ea r eg i v e nd i f f e r e n t w e i g h t sw i t ht h es i g m o i df u n c t i o n f o rt h ef l o o d i n gp r o b l e mi ng n u t e l l a ，at e x tr e t r i e v a lm e t h o di sp r o p o s e di n u n s t r u c t u r e dp 2 pn e t w o r k sb a s e do ns m a l lw o r l dm o d e l s e a c hn o d ei nt h ep 2 p n e t w o r k sm a i n t a i n ss e v e r a ll o n g - - l i n kn e i g h b o u r sa n ds h o r t - - l i n kn e i g h b o u r st ob u i l da s m a l lw o r l dp 2 pn e t w o r k s n e i g h b o u ru p d a t ei sp r o c e s s e dd u r i n gt h eq u e r ya n d r e s p o n s e a n da f t e re a c hq u e r y , w e i g h t so ft h ew o r d si nd o c u m e n t so fn e i g h b o u r n o d e sw i l lb er e v i s e d t h i sm a k e si tr a p i d l yt of r e do u tt h en e t w o r k st o p o l o g ya n d c o n t e n t so fo t h e rn o d e s e x p e r i m e n tr e s u l t ss h o wt h a ts m a l lw o r l dp 2 pn e t w o r k s y i e l d sh i g h e rr e c a l l i nc o m p a r i s o nw i t hg n u t e u aa n dt a k e so nt h ec h a r a c t e r i s t i c so f s m a l lw o r l dw i t hg r e a t e rc l u s t e r i n gc o e f f i c i e n ta n dl o w e ra v e r a g ep a t hl e n g t h f o rt h ep r o b l e m so fc o m p l e xq u e r i e s ，l o a db a l a n c ea n dr o u t i n ge f f i c i e n c yi n s t r u c t u r e dp 2 pn e t w o r k sb a s e do nd h t , ap r o t o c o li ns t r u c t u r e dp 2 pn e t w o r k s c a l l e ds p p s wi sd e s i g n e dw i t hk l e i n b e r gs m a l lw o r l dm o d e l i ns p p s w , n o d e sa r e c l u s t e r e dw i t ht h es i m i l a r i t yo fn o d e sc o n t e n t s n o d e si nt h es a m ec l u s t e rc a ns e l e c t n e i g h b o u r sa c c o r d i n gt ot h es i m i l a r i t y , a n df m a l l yt h en e t w o r ki sm a d eu po fl i n k e d c l u s t e r n o d ec l u s t e r sc o u l da d j u s ti t ss i z eb yd i v i d i n gi n t os m a l l e ro n eo rm e r g i n g i n t ol a r g e ro r l e w i t hs p p s w , r o u t i n gp a t hl e n g t hi ss h o r t e n e db yt h el o n g l i n k b e t w e e nn o d ec l u s t e r s e x p e r i m e n tr e s u l t ss h o wt h a ts e a r c hc o s ti si n c r e a s e dw i t ht h e c u r v eo ft h es q u a r eo fl o g a r i t h ma n dm a i n t e n a n c ec o s ti sl i n e a r l yi n c r e a s e da st h e s c a l eo fn e t w o r k sg o e su p a n da l s ot h em a i n t e n a n c ec o s ta n ds e a r c hc o s tw i l lb e m i n i m i z e dw i t hp r o p e rc l u s t e rs i z e k e yw o r d s ：p e e r - t o - p e e rn e t w o r k s ( p 2 p ) ，t h es m a l lw o r l dp h e n o m e n o n ，t e x t r e t r i e v a l ，o v e r l a yn e t w o r k s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞苤堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 蜘 7 签字日期：p p ，7年f 月岁日 学位论文版权使用授权书 本学位论文作者完全了解墨凄盘堂有关保留、使用学位论文的规定。 特授权墨鲞叁堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 吏讧j 蒂导师签名：心明 七 签字日期：砂。，7 年f 月f 日 签字日期： 枷7 年1 月 广日 第一章绪论 第一章绪论 随着万维网( w o r l dw i d ew e b ，w w w ) 的迅速普及，i n t e m e t 已逐渐成为人 们获取信息最重要的来源，人们的生活已经离不开网络。目前，9 3 的信息是以 电子文本，图像或视频的形式存储的，而且每年电子数据的增长量都超过1 0 0 0 千兆字节以上 1 】。随着万维网爆炸性的增长，人们面对庞大、繁杂的网页，往 往无法理出头绪，很容易迷失在信息海洋中，如何从海量网页中快速有效地找到 有用的信息己成为人们普遍关注的、具有很大挑战性的问题。 传统的集中式搜索引擎技术在整合网页信息、检索网页文本时，遇到了网页 深度挖掘、数据更新和安全性等方面的问题；另一方面，本世纪初兴起的对等网 络( p e e r - t o p e e r n e t w o r k s ，p 2 p ) 技术在充分利用网络带宽、实时更新数据和隐 私保护等方面有着与生俱来的优势。因此，在p 2 p 网络环境下实现网页文本的检 索，已经成为p 2 p 技术应用研究的一个重要领域。 本章以下的部分说明了本文的选题背景及研究意义，介绍了p 2 p 网络的一些 基本概念和目前p 2 p 网络环境下文本检索的研究现状，阐述了本文的主要目标以 及取得的主要研究成果，并说明了论文的组织结构。 1 1 选题背景和研究意义 目前，人们定位和查询万维网数据的方法是利用搜索引擎。搜索引擎的工作 流程一般分为网页搜集、预处理和查询服务三个步骤，即利用爬虫程序抓取网页， 然后对搜集到的网页进行关键词的提取、链接分析和建立索引等处理，将最后的 结果保存在服务器的数据库中，供用户查询使用。以g o o g l e 、y a h o o ! 和百度为 代表的集中式( c l i e n t s e r v e r ) 搜索引擎技术为人们提供了一种方便快捷的网上 冲浪形式，人们越来越依赖搜索的理念去定位所需要的资源。 虽然采用中心服务器方式的搜索引擎能够在一定程度上满足用户的需要，但 由于c l i e n t s e r v e r 结构在处理大规模数据上先天性的缺陷，这种集中式的搜索引 擎无法涵盖大规模互联网的共享数据。利用集中式的搜索引擎处理网页的缺点主 要表现在以下几个方面： 1 可扩展性 集中式的搜索引擎需要中心服务器提供爬虫程序搜索网页，对网页进行处理 第一章绪论 并建立索引，还要对用户的请求做出快速的应答，这些都对服务器硬件的计算能 力提出了较高的要求，中心服务器往往不堪重负，搜索的准确程度已经不能满足 用户的需要。文献 2 5 中指出，目前互联网上存在1 4 亿个以上的网站，包含8 9 亿以上的表面网页( s u r f a c ew e b ) 和4 9 ，0 0 0 亿以上的深度网页( d e e pw e b ) ，g o o g l e 所能检索到的8 0 亿网页只是其中很小的一部分，随着网页数量的增加这个比例 还会降低。即使g o o g l e 使用分布式的爬虫程序搜集网页，要想搜集到大部分的 网页也是不可能的，g o o g l e 已宣布将减少搜索网页的数量，而转向为用户提供 更好的服务方向发展。 2 数据更新 集中式的搜索引擎是基于对静态网页上的链接进行爬虫来采集数据的，实际 上，网站上的网页更新是非常频繁的( 4 0 的网页平均每星期更新一次 6 】) ，而 且还有相当大部分的信息是存储在网站的数据库中，以动态网页的形式来提供 的。这些信息无法用传统搜索引擎通过对静态网页上的链接进行爬虫采集来获 取，传统的集中式的搜索引擎无力对网站信息进行深度挖掘。同时，由于中心服 务器所维护的数据索引过于庞大，数据更新的代价是昂贵的，对于大规模搜索引 擎来说，每次搜集数据的时间通常会花几周，而由于这样做开销较大，通常两次 搜集的间隔时间也不会很短( g o o g l e 大约是每隔2 8 天搜索一次) 。因此，现今 的搜索引擎普遍存在断链的现象，无法提供高质量的即时信息。 3 安全性 集中式的搜索引擎无法避免单节点失效的问题( as i n g l en o d ef a i l u r e ) ，即中 心服务器的损坏意味着整个系统的瘫痪。中心服务器的维护、数据的备份都会消 耗大量的资源，同时，中心服务器的存在给了网络上恶意破坏者一个攻击的目标， m y d o w n 蠕虫及其变种就多次侵袭了g o o g l e 等搜索引擎网站，百度网站也曾经 受到过每秒钟攻击次数高达1 0 0 0 次的攻击，致使搜索引擎在短时间内不能为用 户提供服务。另外，一些恶意网站利用搜索引擎的漏洞使其成为病毒传播的载体， 在网络中传播病毒。 4 民主性 给定一个查询，集中式搜索引擎一般是根据与查询内容相关程度将搜索结果 进行排序，然后返回给用户。但是受利益驱动，多数搜索引擎会将提供赞助的企 业、机构或团体的相关内容排在前列，而不考虑其内容与查询的相关程度，这无 疑会损害用户和竞争者的利益。一些垃圾邮件、广告软件及其他恶意软件的承办 商经常通过赞助的形式，将其网站排在搜索结果的前列来欺骗用户。m c a f e e 公 司的调查结果显示，由按照搜索引擎的赞助( 付费) 方式将结果排序导致用户访 问危险网站的可能性是按照随机搜索结果排序( 非付费) 方式的3 倍，全美的英 第一章绪论 特网用户每个月通过搜索引擎查询对恶意站点的点击达到2 亿8 干5 百万。另外， 由于中心服务器的存在，权威机构可以根据自己的喜好，屏蔽一些信息。 由于集中式搜索引擎在可扩展性、安全性以及网页深度挖掘等方面的弱点， 人们开始考虑如何充分利用网络参与者所拥有的软硬件资源来分担中心服务器 的压力，即采用对等( p e e rt op e e r ) 的通信模式来提高网络的性能和搜索的服务 质量。在p 2 p 网络中，网络中的节点( p e e r ) 既是资源的提供者( s e r v e r ) ，又是 资源的获取者( c l i e n t ) ，各个节点各自对自己本机上存储的信息制作索引，所有 的信息提供者一起构成一个庞大的分布式数据库以供检索。p 2 p 网络可以充分利 用网络中的节点资源，提高网络带宽的利用率，g o o g l e 等公司推出的桌面搜索 引擎目的也是希望能够由内容提供商对自身的存储数据进行深度挖掘，并以统一 的形式提供给服务器以供检索。 与传统的集中式搜索引擎相比，p 2 p 技术具有无可比拟的优越性： 1 健壮性 p 2 p 网络结构的特点决定了p 2 p 网络具有耐攻击、高容错的优点。p 2 p 网络 是由动态的节点构成的，一定比例的节点失效不会影响整个网络的性能，不会发 生一个节点损坏导致系统瘫痪的现象【7 】。p 2 p 网络一般在部分结点失效时能够自 动调整整体网络的拓扑结构，保持其他结点的连通性，p 2 p 网络还能够根据网络 带宽、结点数和负载的变化不断地做出自适应的调整 8 】。 2 低成本、高覆盖性 随着硬件技术的发展，网络节点计算机的计算能力和存储能力以及网络带宽 等性能得到了迅速的提高，采用p 2 p 网络结构可以使每个节点的软硬件资源都得 到充分的利用。p 2 p 技术将计算任务或存储资料分布到所有结点上，通过利用网 络中的大量空闲资源，降低某一个或几个节点的工作负荷，从而达到有效地利用 网络资源，降低维护成本的目的。同时，在p 2 p 网络中，每个节点都可以随时发 布自己的资源，也可以及时地得到其他节点发布的最新资源，资源可以覆盖到网 络中的每个角落。 3 自组织性 p 2 p 网络中节点的地位是平等的，每个参与的节点既是服务器又是客户端， 既是信息的提供者又是信息的消费者。网络中的节点可以任意提交检索的请求， 通过某种路由机制与其他节点连接，将相关的内容以对等的形式直接传送到请求 节点上。节点的加入、离开、连接以及维护都是由节点自发完成的，没有外界的 干预，网络的拓扑结构，网络负载也由节点自我维护，自我修复，因此p 2 p 网络 具有更好的安全性和容错性。 4 隐私保护 第一章绪论 在p 2 p 网络中，节点有权力决定自己的身份和节点存储的内容是否为外界所 见，信息的交换在各节点之间进行而不需要经过某个集中环节，用户的隐私信息 被窃听和泄漏的可能性大大缩小。此外，p 2 p 中的每个匿名用户同时也是服务器， 为其他用户提供匿名服务，经过一个节点的消息可能是源于该节点，也可能是源 于其他节点。在一个大规模的环境中，任何一次通信都可能包含许多潜在的用户， 因此，攻击者不易找到明确的攻击目标来获取节点的信息。 自从1 9 9 9 年1 月第一个文件共享p 2 p 软件n a p s t e r 9 取得成功以来，g n u t e l l a 、 k a z a a 、l i m e w i r e 、m o r p h e u s 、b i t t o r r e n t 、e m u l e 、l u m a q q 和o c e a n s t o r e 10 - 17 等分布式p 2 p 系统不断发展壮大，互联网上潜在的p 2 p 软件用户数以亿计，p 2 p 系统必将对i n t e r n e t 的发展产生深刻的影响。目前，p 2 p 技术的应用处于文件、 数据共享和即时通信的阶段，对于节点内容的深度挖掘和信息整合还处于研究探 索阶段，真正能为用户提供方便、快捷的信息服务的系统还没有出现。尽管如此， p 2 p 网络文本检索作为一种集中式搜索引擎的替代方案，将不断渗透到互联网的 各个应用领域，蕴涵着巨大的商用前景和研究价值，必将成为下一代网络发展的 重要趋势。 1 2p 2 p 网络介绍 1 2 1 什么是p 2 p p 2 p 并不是一个新的概念，在p 2 p 网络诞生之前，电信领域和一些游戏软件 中已经有了p 2 p 的工作模式，即做为c l i e n t s e r v e r 的一种替代方式，没有一个或 几个中心服务器作为节点之间通信、交换信息的枢纽，各个节点( p e e r ) 的地位 是平等的，节点之间可以任意交换资源，没有中心服务器的概念。一种高度概括 的p 2 p 与c s 的结构比较如图1 - 1 所示 1 8 】。 e r s 图1 1p 2 p 与c s 结构比较 4 第一章绪论 图1 - 1 中的p 2 p 结构是一种简单的模型，目前的一些p 2 p 系统的通信模式和 体系结构中经常混杂着一些“中心”的概念，如超级节点、中心路由等等。因此， 在学术界和工业界还没有一个统一的p 2 p 的定义，一些常见的p 2 p 定义有： 国际p 2 p 工作组的定义【1 9 ： p 2 p 系统是由一些共享资源和服务、直接交换信息的节点组成。 g r a h a m 的定义 2 0 ： p 2 p 系统的必备条件有：1 ) 具有服务器能力的可互操作的计算机；2 ) 具有 独立于域名服务器( d n s ) 的寻址能力；3 ) 具有处理网络连通的能力。 s h i r k y 的定义 2 1 ： p 2 p 是一种共享i n t e m e t 上资源( 存储、计算、内容) 的一种应用，访问这 些分散的资源，就意味着要在连接不稳定和i p 地址不可预见的环境里工作。由 于网络上大量的节点工作在d n s 系统之外，这些分散的资源具有不稳定的连通 性和未知的i p 地址。 归纳起来，p 2 p 网络中的节点应该能够以自组织的形式构建网络拓扑，共享 数据、文档、c p u 和网络带宽等资源，并且能够自适应地处理节点加入、离开 和失效等网络拓扑改变的问题，p 2 p 系统的主要特征应该包含以下两点 2 2 1 ： 1 共享数据的直接交互能力 由于没有中心服务器管理节点之间的信息交换和定位节点，p 2 p 系统中的节 点应该能够独立地处理好搜索其他节点、定位资源、维护其他节点的路由信息、 维护节点之间的连接和发布自身信息等任务。 2 网络拓扑结构的动态更新能力 当节点位置发生变化时，p 2 p 系统应该能够迅速地自动做出反应，保证网络 的连通性，网络的性能也不能因为小部分节点的离开或失效受到影响。 1 2 2p 2 p 网络结构 p 2 p 系统应该是由独立的节点以自组织的方式构建在i n t e m e t 上的一个覆盖 层( o v e r l a y ) ，在这个逻辑层内，节点之间能够完成远程节点的路由、资源查找、 冗余存储、匿名通信、维护网络拓扑结构和性能等任务。图1 2 是一个简要的 p 2 p 网络覆盖层示意图，说明了p 2 p 网络覆盖层的一些主要组件。网络通信层是 指由i n t e m e t 网络中的计算机构成的物理网络，p 2 p 系统应该能够确保节点在物 理网络中的通信；节点管理层是构建在物理网络之上的一个逻辑层，负责完成节 点发现、节点路由优化等任务；特征管理层处理的是维护p 2 p 系统的安全性、容 错性和健壮性等方面的问题；服务请求、协调服务安排等事务由服务管理层来处 第一章绪论 理；应用层包含了一些应用程序和一些实用工具。 应用程序、工具 服务通信、服务安排 安全、资源、容错管理 路由，资源发现、查找 物理网络( i n t e m e t ) 应用层 服务管理层 特征管理层 节点管理层 网络通信层 图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 网络和结构化p 2 p 网络两 个类别，如图1 3 所示。 图1 3p 2 p 系统结构分类 在非结构化的p 2 p 系统中，没有中心服务器，但是节点在进行相关信息搜 索时可能存在一个目录服务器来记录节点的一些信息，它有三种情况，分别是完 全非中心化、部分中心化和混合中心化。完全非中心化的p 2 p 系统可以认为是纯 正的p 2 p 结构，所有节点都是平等的，扮演服务器和客户端的双重角色；部分中 心化的p 2 p 系统中，一些具有高带宽、计算能力强的节点被选举出来作为超级节 第一章绪论 点。超级节点作为其他节点的代理发送请求和做出应答，并且维护节点间的路由 信息；混合中心化的p 2 p 系统中，存在一些不可替代的节点提供集中式的目录服 务，而系统内其他的节点，具有彼此等同的功能。结构化p 2 p 系统采用分布式哈 希表( d h t , d i s t r i b u t e dh a s ht a b l e ) 技术构造，存在某种预定的结构( 如环或者 网格等) 映射数据文件与存储位置之间的关系，从而保证具有有效路由，并能够 保证最终找到目标节点。 目前存在的p 2 p 系统中，g n u t e l l a 、f r e e n e t 2 3 是完全非中心化的非结构化 p 2 p 系统，k a z a a 和m o r p h e u s 是部分中心化的非结构化p 2 p 系统，n a p s t e r 是 混合中心的非结构化p 2 p 系统。c h o r d 2 4 、c a n 2 5 、p a s t r y 2 6 和t a p e s t r y 2 7 是结构化p 2 p 系统。 1 2 3 目前的p 2 p 系统介绍 自从第一个共享m p 3 文件的p 2 p 软件n a p s t e r 诞生以来，p 2 p 软件的研究迅 速发展起来，按时间顺序出现了所谓非结构化的第一代p 2 p 系统和结构化的第二 代p 2 p 系统，这两种系统由于协议的设计理念不同，有着各自的优势和不足之处， 都在不断地完善和发展之中，以下是一些著名的p 2 p 系统的简要介绍。 - n a p s t e r n a p s t e r 是最早出现的p 2 p 系统，它采用一个中心服务器维护系列的索引 对为文件和文件的位置建立映射，如图1 4 所示。 图1 - 4n a p s t e r 系统结构图 在图1 4 中，当用户想要得到某个音乐文件时，首先要查询服务器的索引， 第一章绪论 得到存放这个音乐文件的节点i p 地址，然后在与该节点连接并下载此音乐文件。 文件的传输与中心服务器无关，中心服务器的作用是为资源定位。 n a p s t e r 实现了资源定位与资源交换的分离，有效地节省了中心服务器的一 部分带宽，但是这种简单的方法存在着可扩展性的问题。当网络规模扩大时，中 心服务器索引的维护成本急剧增加，同时n a p s t e r 也存在着单节点失效的问题， 即中心服务器的瘫痪意味着整个网络的崩溃。如果能够采用大规模服务器集群， 比如g o o g l e 和y a h o o ! ，则也可以达到相当大的可扩展性。尽管如此，由于集群 服务器在高性能机器和高带宽等方面需要相当大的投资，因而并不适用于p 2 p 网络。此外，这种通过中心服务器维护索引的方法也不是容错的。 g n u t e l l a g n u t e l l a 是一种最基本的完全非结构化的p 2 p 系统，网络中的节点的地位都 是相等的，没有中心服务器，因此资源的定位和交换都是分布式的，节点之间通 信的方法是泛洪( f l o o d i n g ) 。在g n u t e l l a 网络中，节点有查询请求时，首先要向整 个网络广播其查询消息，收到查询消息的节点检查本地资源，如果有相关的答案， 将答案返回给请求节点并转发消息，否则，直接将消息转发，如图1 5 所示。 图1 - 5g n u t e l l a 系统结构图 g n u t e l l a 网络的设计方式不需要n a p s t e r 式的中心服务索引器，使得资源查 找是分布式的。然而这种设计并不是一种可扩展的方案，因为它对于每个请求而 言都会生成太多的通信开销，随着请求数量的增大，网络性能会急剧下降。一般 情况下，g n u t e l l a 都要采用消息生命周期( ”m ，t i m et ol i v e ) 来控制消息数量， 第一章绪论 但是这样可能会丢失一部分正确的答案。 f r e e n e t f r e e n e t 是一个基于j a v a 的跨平台的分布式文件存储系统，文件的发布者、 查询者包括文件的持有者在f r e e n e t 系统中都是匿名的。在f r e e n e t 系统中定义了 二进制文件键用来存储节点数据，每个节点都维护着一个局部路由表保存邻近节 点的地址和节点的文件键。f r e e n e t 系统查询请求顺序如图1 6 所示，节点a 检 查路由表将查询请求发送给节点b ，节点b 将查询请求转发给节点c ，节点c 检查本地资源发现没有答案并且没有其他邻居节点，然后将查询失败的信息回溯 给节点b 。节点b 再尝试发送查询请求给节点d ，节点d 再将消息转发给节点f ， 节点f 又将消息转发给节点b ，这样形成了一个回路，节点b 发现回路后将查 询失败的消息按回路的逆序发送给节点f 和节点d 。节点d 收到失败信息后， 将查询请求转发给节点e ，节点e 中存在与查询相关的答案，答案将经由节点d 和节点b 返回给请求节点a 。 一一一一一答案 卜失败 请求 图1 - 6f r e e n e t 系统下查询顺序 f r e e n e t 系统具有很好的可靠性和容错性，部分节点失效不会影响整个网络 的性能，但由于没有全局节点的路由信息，与g n u t e l l a 系统一样，可能会丢失一 部分数据，同时f r e e n e t 系统存在安全性的问题，即恶意节点或病毒可以通过发 送虚假消息的方式来降低路由效率。 c a n c a n 是一种基于d h t 技术的p 2 p 系统，具有可扩展性、容错性和自组织性。 第一章绪论 c a n 将网络中的节点映射到一个d 维的虚拟笛卡尔空间中，每个节点都得到一 块区域( z o n e ) ，随着节点的加入和离开，c a n 系统自动调整整个空间的区域分 配。c a n 采用一个统一的哈希函数将节点的( k e y ，v a l u e ) 对中的k e y 进行哈 希运算，得到笛卡尔空间中的一个点，并将( k e y , v a l u e ) 对存储在拥有该点所在 区域的节点内。每个节点都维护一个路由表，用来存储邻近节点的i p 地址和虚 拟空间中的区域。 节点x 的邻节点集合为 a ，b ，c ，d 点e 的路由 加入 图1 7c a n 系统的查询路由和节点加入 c a n 的路由算法和节点更新如图1 7 所示，请求节点x 的请求消息中包含 目的节点e 的虚拟空间坐标，采用贪婪算法，将请求转发给节点x 的邻近节点 a 、b 、c 和d 中与目的节点最近的节点，直到发现目的节点。 一个新节点加入网络时，首先随机选取一个节点p 发送加入请求，c a n 中 的节点将加入请求消息转发给节点p 。节点p 收到消息后将自己的区域划分为相 等的两个部分，其中的一部分分配给新节点，新节点还会从节点p 那里得到邻近 节点的i p 地址等信息。当节点离开网络时，它的一个邻居节点就会接管离开节 点的空间，这个节点会更新它的邻近节点列表，删除已经离开的邻居，并通知其 他节点网络的拓扑结构已经改变。 在c a n 中，处理节点失效的方法是相邻节点周期性的交换更新信息，如果 第一章绪论 某个节点多次没有发送更新消息，则相邻节点认为该节点已经退出系统，执行取 代操作。取代操作的步骤是：首先启动一个时钟，如果时钟超时，取代节点向退 出节点的所有相邻节点发送取代消息，消息中包括取代节点的区域面积信息，节 点收到取代信息后，对比自身和取代节点的区域面积大小，面积最小的节点成为 最终的取代节点。 c h o r d c h o r d 采用一致性哈希函数s h a 1 为节点和数据k e y 分配了一个m 位的标 识，节点标识对2 研取余，构成一个表示环。每个节点x 存储指向它的直接后续 ( s u c c e s s o r ) 标识，同样需要存储m 个其他节点的信息，这些信息的集合被称 为查询表( f i n g e rt a b l e ) ，表中的第i 项存储x + 2 卜1 的后续标识，图1 8 是一个 有三个节点的c h o r d 标识环的示意图。 k e y s 团 图1 - 8 三个节点0 、1 和3 的c h o r d 标识环 在查询的过程中，查询节点将请求发送到与键值最接近的节点上，收到查询 请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点( 这与一 致性哈希完全相同) 。如果被查询的信息不在本地，就根据查询表将请求转发到 与键值最接近的节点上，这样的过程一直持续到找到相应的节点为止。在图1 8 中，节点3 想要查询k e y l ，首先检查自己是否存储了k e y l ，然后通过查询表确 苗一习墼群 第一章绪论 定与k e y l 最接近的节点0 ，发送查询消息；节点0 收到查询消息后，检查自己 是否存储了k e y l ，然后通过查询表确定与k e y l 最接近的节点1 ；节点1 收到查 询消息后，确定k e y l 存储在本地，向节点0 确认。 新的节点的加入c h o r d 系统时，需要首先初始化本地节点查询表，然后通知 网络中的其他节点更新自身的查询表，最后，其他节点将属于加入节点的关键字 转移到加入节点上。节点退出时，查询表中所有节点都要把退出节点替换为退出 节点的后继节点，同时退出节点负责把自己的关键字信息转移到它的后继节点 上。如果后继节点失效，则在后继节点列表中选择其他节点替换。 p a s t r y 在p a s t r y 系统中，每个节点都拥有一个1 2 8 比特的标识( n o d ei d ) ，这样节 点的标识空间的范围是2 1 2 81 ，p a s t r y 中的每个节点都拥有一个路由表r ( r o u t i n g t a b l e ) 、一个邻居节点集m ( n e i g h b o r h o o ds e t ) 和一个叶子节点集合l ( l e a f s e t ) ， 它们一起构成了节点的状态表。 如图i - 9 所示，路由表r 共有l o g 日n ( b = 2 d 为系统参数，b 的典型值为4 ， n 表示系统的节点总数) 行，每行包括b 1 个表项，每个表项记录了一个邻居节 点的信息( 节点标识、i p 地址和当前状态等) 。路由表第n 行的表项所记录的邻 居节点的n o d ei d 前n 个数位和当前节点的前n 个数位相同，而第n + 1 个数位 则分别取从0 到b 1 的值( 除了与当前节点第n + 1 数位的值) 。 叶子节点集合l 中存放的是在键值空间中与当前节点距离最近的叫个节点 的信息，其中一半节点标识大于当前节点，另一半节点标识小于当前节点。叫 的典型值为2 b 或者2 2 b 。 邻居节点集合m 中存放的是在真实网络中与当前节点“距离”最近的f m l 个节 点的信息。“距离”的定义在p a s t r y 中非常类似i p 路由协议中对距离的定义，也 就是考虑到转发跳数、传输路径带宽和q o s 等综合因素后所得的转发开销，i m i 的典型值为2 b 或者2 2 b 。 p a s t r y 的路由过程如下： 当收到路由消息时，节点首先检查消息键值是否落在叶子节点集合的范围 内，如果是，则直接把消息转发给叶子节点集合中节点标识和消息键值最接近的 节点，否则就从路由表中根据最长前缀优先的原则选择一个节点作为路由目标， 转发路由消息。如果不存在这样的节点，当前节点将会从其维护的所有邻居节点 集合( 包括路由表叶子集合及邻居集合中的节点) 中选择一个距离消息键值最近 的节点作为转发目标。 b 节点3 7 a 0 x 的r o u t i n gt a b l e ，b = 4 第一章绪论 o xl x2 x3 x4 xd xe xf x 3 0 x3 h3 2 x3 a 13 8 x3 e x3 f “ 3 7 0 x3 7 lx3 7 2 x3 7 觚3 7 b x3 7 e 13 7 f x 3 7 a 0 x3 7 a 1x3 7 a 2 x3 7 a b x 3 7 a c x3 7 a d x 3 7 a e x3 7 a f x 节点3 7 a o f l 搜索镁t b 5 7 8 2 d 的路由 节点3 7 a f i 的路由状态 b = 4 ，l = 1 6 ，m = 3 2 n o d e l d3 7 a o f l l e a f s e t s m a l l e r 3 7 a l3 7 a o 3 7 a 0 2 23 7 a 0 3 3 3 7 a 0 4 43 7 a 0 5 53 7 a 0 6 6 3 7 a 0 7 7 l e a f s e t l a r g e r 3 7 a o f 23 7 a 0 1 = 43 7 a o f 63 7 a o f 8 3 7 a o f a3 7 a o f b3 7 a o f ( 3 7 a o f e n e i g h b o r - h o o ds e t 】a 2 2 3 b1 8 3 4 6 72 4 5 a d o2 6 7 0 a b 3 6 l2 a b3 7 8 9 0 a3 9 0 a f 03 9 l ! c d 4 6 7 l a 04 7 7 8 l o4 8 8 i f 4 9 0 ( d e 2 7 9 1 ) 1 - + 02 9 0 a o b 5 1 0 a o c 5 2 l3 ：a l l3 4 5 81 2 2 16 7 6 2 2 8 a1 9 9 0 2 d 2 2 】j 4 52 6 7 2 2 l2 8 9 8 9 c1 9 9 a b c 图1 - 9p a s t r y 的节点路由表、叶子节点集、邻居集和搜索路由 与c h o r d 和c a n 相比，p a s t r y 引入了叶子节点和邻居节点集合的 应用层能够及时准确地获得这两个集合的节点信息时，可以大大加快路 概念。在 由查找的 速度，同时降低因路由引起的网络传输开销，不过在动态变化的p 2 p 网络中如何 理想地做到这一点有很大的难度。 1 3p 2 p 网络文本检索及研究现状 p 2 p 环境下的文本检索与传统的文本检索的任务一样，就是网络中的某一节 点发送检索请求，然后检索请求通过某种路由机制传播到网络上的其他节点，存 储有相关信息的节点将会回应请求，把本地相关的内容以对等的形式直接传送到 请求节点上，一个简单的p 2 p 网络文本检索示意图如图1 1 0 所示。 第一章绪论 r 曼 应答 p 一 图1 1 0p 2 p 文本检索示意图 由于p 2 p 网络中没有中心服务器管理节点，如何找到包含与查询内容相关的 节点成为p 2 p 文本检索系统机制设计的首要问题。容易想到的节点资源定位的方 式有两种，一种是p 2 p 网络中的节点以自组织的方式加入网络，请求查询