（计算机软件与理论专业论文）基于mas的p2p信息共享系统：fgrid.pdf

中罔科学技术人学坝f j 学位论史堆j 二m a s 的p 2 p 信息j 享系统：f - g r i d 摘要 随着i n t e r n e t 的发展，c l i e n t s e r v e r ( c s ) 当i 构在信息兆享方面的缺陷越来越 明显。单点失败以及硬件资源不能得到充分利用足日l mc l i e n t s e r v e r 结构给 i n t e r n e t 带来的两个微，“重的m 题。这两个问题促使了对等计算( p e e r - t o p e e r ，简 称p 2 p ) 的出现。对等计算这利，新型的计算方式可以充分利用各个自治节点的计 算资源( 包括文件、c p u 执行周期以及网络带宽等) ，以较低的性能价格比进行资 源共享及协同计算。它在解决目前i n t e r n e t 面临的各种问题上潜力很大。尤其是 随着个人p c 的处理能力不断增强、存储容量不断加大，导致大量计算和存储资 源闲置，使得p 2 p 在信息共享方面的应用日# 景非常广阔。本文分析了当前几种 典型p 2 p 系统的优点和不足，在此基础上实现了一个p 2 p 信息共享的原型系统： f g r i d 。本文的特色和创新点如下： 1 ) 语义索引空间p 2 p 网络中具有大量的可用资源，但是，如果没有完善 的检索机制，其应用价值将大打折扣。为了提供高效的检索机制，f g r i d 中利用关键词、类型以及信息标识构造了一个语义索引空间，并采用 d h t ( d i s t r i b u t e dh a s ht a b l e ) 技术管理该空间。系统根据共享信息的语义 特征，生成其在索引空问中的坐标。然后将信息的索引发确淫4 管辖空问 包含这些坐标的节点。检索时，根掘用户输入的检索条件，生成定位坐 标，找到相应的节点，然后在这些节点生成检索结果返回用户。语义索 引空间让f g r i d 既具有第二代p 2 p 系统可扩展性好、负载均衡以及健壮 的优点。又弥补了它们不支持语义检索的不足。 2 ) 采用多a g e n t 结构 f - g r i d 以j a d e 作为刀：发框架，整个系统由共享 维护a g e n t 、索引管理a g e n t 、消息转发a g e n t 、信息检索a g e n t 等十多 个a g e n t 组成。a g e n t 之间通过f i p a a c l 语言通信，共同协作使f g r i d 能够整合广域异构资源，为用户提供透明的信息资源共享、检索以及访 问功能。采用a g e n t 技术在很大程度上简化了p 2 p 网络固有的动态、异 构、分砸i 等特点带来的复杂性。 3 ) 依存语法分析 将自然语言处理技术应用到信息检索中正在受到越来越 多的关注，而句法分析是其中的关键步骤之一。本文提出基于最大熵的 中文依存句法分析模型。用自底而上的方式构建语句的依存关系树，构 建过程中每一步可归纳为在向左连接、向右连接以及不连接三种动作之 中选取其一，用最大熵原理判断每个动作的概率，进而得到依存树中各 边的概率，然后找出具有最大概率的依存关系树。实验结果表明该模型 具有较好的分析精度。 关键词：p 2 p ，d h t ，信息检索，语义索引孙j j ，多a g e n t 系统，自然语言。处 理，最大熵原理，依存语法，统计句法分析 j 1m a sn 1p 2 pf 二u ，j 10 系统：i ：- ( ；r i d a b s t t a c t w i t ht i l ed e v e l o p m e n te l i n t e r n c t ，t h ed c l i c i c n c yo ft h ec l j c n t s c t v c l c h i t e c ll i i e i ni 1 1 f o i m a t i o ns h a r i n gg r a d u a l l y0 1 1 l c l g e s c e n u a l i h i l u r ea n dn n d e t t i t j i i z a t i o ne lt h e l l a r d w a r er e s o u r c e sa r et h et w os e r i o u sp r o b l c n l st h a tt h ec i l c n t s e l v o l ( c s ) a r c h i t e c t u r eb r i n g st oi n t e r n e t ，w h i c hl c a dt ot i l ea d v e n to fp e c r - t o i e c l 。( 1 2 i ) c o m p u t i n g p 2 p sg o a l i st om a k ef u l lu s eo ft h el _ c s o n r c e s l o c a t i n g i ne a c h a u t o n o n l o u sn o d e ，i n c l u d i n gf i l e s ，c p oc y c l e sa n db a n d w i d t h ，e t c ，s oi ti sp o s s i b l et o c o n d u c tr e s o u r c es h a r i n ga n dc o o p e r a t i v ec o m p u t a t i o nw i t hb e t t e rp r i c e p e r f o r n l a n c e r a t i o p 2 p1 1 a sg r e a tp o t e n t i a lt os o l v et h ep r o b l e m so f c u r r e n ti n t e r n c t e s p e c i a l l yw i t h t i l ep r o c e s s o rb e c o m i n gm o r ep o w e r f u la n dt i l ec a p a c i t yo fs t o r a g ed e v i c eb e c o m i n g l a r g e r , n l o r ec o n l p u t i n ga n ds t o r a g er e s o u r c e sa r ev a c a n tt h u s ，p 2 pi se x t r e m e l y p r o n a i s i n gi nt i l ef i e l do fi l l f o r m a t i o ns h a r i n g 1 1 1t h i sp a p e r s o r t i et y p i c a lp 2 pm o d e l s a r ea n a l y z e d b a s e do nt h i s ap 2 pi n f o r m a t i o n s h a r i n gs y s t e m ：i ? 一g r i di sr e a l i z e d t h e c h a r a c t e r i s t i ca n di n n o v a t i o no f t h i sp a p e ri sa sf o l l o w s ： 1 ) s e m a n t i ci n d e xs p a c e t h e r ei sal o to fr e s o u r c ei nt i l ep 2 pn e t w o lk b u t i ft i l er e t r i e v a l1 1 1 e c h a l a i s n li sn o te f f e c l i v e p 2 pw o u l dn o tb es ou s e f u l 1 1 1f g 1 i d t o m a k ei e t r i e v a le f f e c t i v e as e m a n t i ci n d e xs p a c ej sp r o p o s e dw h i c hi sc o m p o s e do f s o m es e m a n t i cf e a t u r e s ：k e y w o r d i a f o r m a t i o ni da n di 1 1 f o l n l a l i o nt y p e t h ej n d e x s p a c ei ss p l i ta n dl n a n a g e d b yp e e r su s i n gd h t ( d i s u l i b u t e dh a s h r a b l e ) t h e i n f o n n a t i o ns h a r e di nt h en e t w o r ki sm a p p e dt op o i n t si i lt h ei n d e xs p a c ed u et oi t s s e m a n t i cf e a t u r e s a l a dt h ei n d e x e sa r ep u b l i s h e dt op e e r s s p a c eo fw h i c hc o n t a i n st h e p o i n t s w h i l er e t r i e v i n g ，t h ep o i n t sa l eg e n e l a t e dd n ct ot h eq u e r ye x p l e s s i o nt h e n t h ee x p r e s s i o ni sp u b l i s h e dt ot h ep e e l ss t o r i n gs e m a n t i c a l l yc o l 1 e l a t i o ni n d e x e sjl i s t l i k ep u b l i s h i n gi n d e x e s t h u st i l er e s u l tc a l lb er e t r i e v e di nt l l e s ep e e r s o w i n gt ot h e s e m a n t i ci n d e xs p a c e ，o u rp 2 pm o d e l i se f l e c t i v e ，s c a l a b l ea n dr o b u s t ，a n do v e r c o m e s t h es h o r t c o m i n gt h a tt h e2 “g e n e r a t i o np 2 pm o d e l su s i n gd h tc a l l ts u p p o r ts e m a n t i c r e t r i e v a lw e l l ， 2 、m u l t i a g e n ts y s t e m f gr i di sb u i l t0 1 1j a d ef i a n l e w o l l k 1 t1 1 1 c 1 u d e s s h a r i n g m a i n t e n a n c ea g e n t 、i n d e x m a n a g c n l e n ta g e n t ，m e s s a g e - l r a n s m i s s i o na g e n t ， a n dh i f o r m a t i o n - r e t r i e v a l a g e n t e t c t h ea g e n t su s ef i i ) aa c ll a n g n a g et o c o o p e r a t e 、s ot h a ti i g r i dc a l lc o m b i n en l u l t i p l i c a t er e s o u r c e si nt h en e t w o l kt o p r o v i d es e r v i c e ss n c ha sj n f o r m a l i o ns h a r i n g i c t l i e v a ia n dd o w n l o a d i n g f l a ca g e n t t e c h n o l o g yo v e r c o m e st h ec o m p l e x i t yc a u s e db yt h ei m p l i c i tl ；e a t u r e so fp 2 pl l e t w o l k s ， w h i c ha l ed y n a n l i c m u l l i p l i g a t ea n dd 【s t r i b u t e d 3 ) d e p e n d e n c yp a r s i n gw i t hm a x i l n u n le n t r o p yp r i n c i p l e t i l e a p p l i c a t i o n o f n l p ( n a t n r a ll a n g u a g ep r o c e s s i n g ) t oi n f o r m a t i o nr e t r i e v a li sa t t r a c t i n gr n o r ea n d m o r ea t t e n t i o n p a l s i n gi st h em o s ti m p o r t a n ts t e po fn l pt h i sp a p e rl 1 s c sm a x i i l l l _ 1 1 1 1 e n t r o p yf me ) m o d e lt op a l 。s ec h i n c s es e n t e n c ew i t hd c p e n d e n c yg 1 a n i m a lt h e d e p e n d e n c y t r e ei sc o n s t r u c t e dw i t hab o t t o m u dp r o c e s s ，a n doneo ft h et h r e ea c t i o n s ( 1 c f t c o n c a t e n a t i o n ，1 i g h t c o n c a t e n a t i o n ，n e l l c o n c a t e n a t i o n ) i ss e l e c t e e ii i ie v c l ys t e p 中珊科学技术人学坝l 学位论史j m a s 的p 2 p 信息共享系统；f - g r i d o ft h ec o n s t r u c t i n gp r o c e s s t l wm a x i m u me n t r o p yp r i n c i p l ei su s e dt oc o m p u t et h e p r o b a b i l i t yo ft h ea c t i o n s ，t h u st h ed e p e n d e n c y t r e ew i t hm a x i m u mp r o b a b i l i t yc a n b eo b t a i n e d t h em o d e li se x p e r i m e n t a l l yp r o v e ds a t i s f y i n gi np r e c i s i o n k e y w o r d s ：p 2 p ( p e e r - t o p e e r ) ，d h t ( d i s t r i b u t e dh a s ht a b l e ) ，i n f o r m a t i o nr e t r i e v a l ， s e m a n t i ci n d e xs p a c e ，m a s ( m u l t i a g e r t ts y s t e m ) ，n a t u r el a n g u a g ep r o c e s s i n g ， m a x i m u me n t r o p yp r i n c i p l e ，d e p e n d e n c yg r a m m a r , s t a t i s t i c a lp a r s i n g i i l t ，i 叫利学投4 ：人学删i 学位沦史j t m a s 的p 2 pf 青膛、兆_ ! ；乐统：f - g r i d 1 1 课题背景 第一章绪论 随菥俯息技术的飞速发腱，i n t c r n e t 的发展也一l ：lt _ | ! e q 信息量飞速 膨胀。根据一项可靠估计1 1 1 ，在1 9 9 7 年1 2 月w e b 上能被索引到的公丌网页数 大约是3 2 亿，到了1 9 9 9 年5 月增加到8 亿，2 0 0 0 年1 月，己经达到了1 0 亿。 专家们认为，如果把非公丌的网页考虑进去的话，比如位于公司以及政府防火墒 后丽的网页，数目几乎要翻5 倍。而根据g o o g l e l 2 1 的主页显示，2 0 0 4 年g o o g l e 大概索引了4 2 8 亿嘲页。 如何有效地管理和利，月如此庞大的信息成为了一个亟待解决的问题。目6 “ w e b 采用c s 模式，也就足客户i n 务器体系结构。这k q , 鲜4 1 ：, j x q 。i n t e r n e 的发展起 到了重大的推动作用，并且仍然是日d 0 主要的刚络应用模式。然而随着信息量的 刁i 断急删膨胀，这_ 手l | i 结构在i n t e r n e t 规模的分砷】式环境下的缺陷已经越来越明显。 在像w e b 这样的应用系统c p ，资源集中在一台或少数服务器中，热点访问和 单点失效将导致严重的负载平衡问题甚至服务的终止。另：9 1 、，网络带宽也是瓶颈 之一。虽然研究者们开发了许多方法( 如分粕式机群等) 束解决这些瓶颈问题，但 付出的代价却非常昂贵。 白2 0 0 0 年以来，一些新型网络应用如n a p s t e r 队g n u e l l a 【4 】、t a p e s t r y 引、 c h o r d 队p a s t r y 7 1 以及c a n i6 】等的玑为我们引入了一种新的汁算方式，即对等 计算( p e e r t o p e e rc o m p u t i n g ) 。它试图提供仝网范围的信息存取、资源共享和协 作。 目目口对等汁算已经发展成一利，新型的计算方式，其日的在 ：充分利用各个 自治一1 ，点f 门计算资源( 包括存储能力、c i u 执行周j 孵以及网络带宽等) ，以较低的 性能价格比进 j ：资洲 共享及呐汁算。 对等网络( p 2 p ) 与传统的客户n 务器( c s ) n 络相比较有如下优点： l 、剥等刚络的资源能够在网络的中心和边缘被共享。而在客户服务器网络 资源通常只能在网络的中心被共享 2 、对等网络易】：扩展，m 佃比单个服务器业可靠。啦个似务器会遭受单肖 的故障i ：且有可能会成为系统瓶颈。 3 、划等网络能分享他的处理器，对于分币i 式的计算任务能合并计算资源 而不是只靠一个计算机，如超级计算机。 4 、对等计算机的分享资源能被直接访问。剥等计算机能在他的当地存储器 l 分，乒他的文件，l 而小必在一个中- t 2 , j l l i 务器上分享文件。 l i l l ： 钉1 适应性、 组织性、高可靠性、高可用性以及大舰模的资源，e 享 刷训州汁算能力等，p 2 p 系统拥有广阔的产业前景和科学研y z f i l j 景。 但是系统的丌放性特征以及缺乏集中的控制中心使得对等计算- 1 的效率问 题、资源管理和搜索问题一直是研究的重点和难点，可扩展性和易用性也是p 2 p 中l t ，学 盘术人i f ：i , 9 1i 学化论史 肚j m a sf i jp 2 1 ，f i i 息l ! 一系统：f - gr i d 系统所而临的重要问题1 1 。 虽然p 2 p 可以应用在包括信息共享的许多领域，如计算能力共享 ( s e t h o m e ，d a t as y n a p s e ) 、 存储空| 、日j 共享等t 但本文将主要致力于研究p 2 p 信息其宁技术，拟解决刘等计算q 一的可扩展性、易用性和关键的倩息获取问题， 并最终研制出一个l 向效、易川的p 2 p 信息j l 享系统：f - g r i d 。 1 2p 2 p 发展概述 p 2 1 1 是p e e r - t o p e e r 的缩写，p e e r 在英语垠有“( 地位、能力等) 同等者”、 伙伴”等意思。因此，p 2 p - j 以耻解为“伙伴对伙伴”，称之；z j x , j - 等网络。 简单的说p 2 p 将网络j 1 j 户直接联系起来，让人们通过互联网直接连接到其 他用户的计算机进行交互，交换文件，而不是像过去那样连接到服务器去浏览与 下载。这使得网络上的沟通变得容易、更直接共享和交互，真正地消除中间商。 i i 前，它在加强网络上人的交流、文件交换、分斫j 计算等方i l ：i 大有前途。 p 2 p 另一个重要特点是改变互l i j c 俐现在的以人刚站为r l ，心的状态、重返“非 中心化”，并把权力交还给用户。p 2 p 看起来似乎很新，但是币如b 2 c ，b 2 b 是 将现实t u ：界中很平常的东西移植到互联刚上一样，p 2 p 并不是什么新东西。从网 络角度看，p 2 p 是互联网整休架构的基础。互联网最基本的协议t c p i p 并没有 客户机和服务器的概念，所有的设备都是通讯的平等的一端。在十多年之前，所 有的互联网上的系统都i 司时具有服务器和客户机的功能。 当然，后来发展的那些架构在t c p i p 之上的软件采用了客户机服务器的结 构：浏览器和w e b 服务器、邮件客户1 端和i i i v ! i i i 务器。但是，划于服务器来说， g i f t 之m 仍然是刘等联劂的。以e m a i l 为例，互联删上并没有一个巨大的，唯一 的邮件服务器来处理所有的e m a i l ，而是对等联网的邮件服务器相互协作把e m a i l 传送到相应的服务器上去。另外 j 户之f u je m a i l 则一直通过对等的联络渠道。但 在过去的几年里，互联网的发展至少表面上远离了p 2 p ，互联网上绝大部分的节 点并不能和其他节点直接地交流。 1 2 1p 2 p 的起源 n a p s t e r 3 l 唤醒了深臧在互联俐背后的对等联网。应用侄局域网l = 岫0 共享目录 足下常_ i 过的事情。但是n a p s t e r 文件共享功能的成功促使人们认识到把这种“对 等联网”拓展到整个互联网范围的可能性。当然，从菜利们度u f ，n a p s t e r 并不 是纯粹的p 2 p ，它仍然需要一个处于中心协调$ l t ；t 0 。事实上，网络上现有的许多 服务可以归入这种非纯粹的p 2 p 的行列。即时通汛系统譬如i c q 、a o li n s t a n t m e s s e n g e r ，y a h o op a g e r ，微软的m s nm e s s e n g e r 以及剧内的o l c q 是最流行的 p 2 p 应用。它们允许用户互相沟通雨i 交换信息、交换文件，但仍需要位于中心的 服务器术协调。 1 2 2p 2 p 带来的改变 p 2 p 带来的一个变化就是改变了“内容”所在的位簧，内容难在从“中心” 巾同科学技术人学坝l 学位沦殳 堆十m a s 的p 2 1 j _ 息北享系统：v - g r i d 走向“边缘”，也就是说内容将主要才i 是存存几个主要的服务器上，而是存在所 有用户的系统上。 p 2 p 使得每个人办公桌上的电脑都可以成为“服务器”。用户原来是用台式 i 电脑准备好数据之后再把数掘上载到服务器上去，而使用p 2 p 将不再需要这个 过程。p 2 p 使得个人电脑 ；i j ：一次成为“ii 一心。p 2 p 使得个人q ! j j 卤重新焕发活力、 不再是被动的客广端，而成为具有服务器和客户端的特征的设备，个人电脑将更 新成为! f ：联网的，h c 、。 互联刚的存储模式将山现在的“内容位于中心”模式转，变为“内容位于边缘” 模式。从这个角度看p 2 p 带来了几个改变： 首先，客户不再需要将文件上找到服务器，而只需要使用p 2 p 将共享信息提 供出去： 其次，运行p 2 p 的个人电脑不需要强大的计算能力，海量的存储空间。这使 得更多的联网用户可以参与其中，用户也就能够分享到更多的资源。而这部分用 户在所有j ；1 】户中占有极大的比重： 最后，p 2 p 完全改变过去控制互联网的客户机j j e 务器模式，消除客户机和服 务器二者之的差别。 n a p s t e r 是难得的对p 2 p 的概念上可行性的证明，揭示了p 2 p 改变互联网的 潜力。直通桌面的宽带网络逐渐成为现实、个人电脑越来越强大足以胜任“服务 器”功能，硬件功能的进步保障p 2 p 系统的成功。 1 3 主要研究内容 海量的信息以及对信息的大量需求，使得c l i e n t s e r v e r 结构越来越不嫩重负。 p 2 p 因为自身的特性，将成为信息获取| 勺一种新的网络范例。p 2 p 披术充分利用 各个i i 点的资源，避免了资源的高度集中、提供了一个高效的资源管理框架。本 文结合国内外p 2 p 信息共享系统的研究现状，设计并实现了个蜒于多a g e n t 的 p 2 p 信息共享系统。我们把这个系统命名为f g r i d 。 本文的主要工作分为以下几个方面： ( 1 ) 研究p 2 p 技术。对现有p 2 p 系统中所采用的主要算法进行铆f 究，探讨其 备自的优点和不足。 ( 2 ) 改进p 2 p 系统。i 殳汁j j ：实现了f - g r i d 。f - g r i d 采j j 多a g e n t 的体系结构， 以分斫j 台希技术( d ii t ，d i s t r i b u t e dh a s ht a b l e ) 为丛础，维护一个逻辑的语 义空州，使衍系统高效、 i i ! 壮、扩展性好，弥补了现有采用d h t 技术的p 2 p 系 统刈拈于语义信息检索支持的不足。 ( 3 ) 结果的评价与比较。实现了f - g r i d 的原型系统，验证了其效率、扩展性 等性能指标，并在此基础上进行了讨论。 ( 4 ) 捉出基于最大熵的汉语依存分析模型。自然语占理m 犁技术与信息检索技术 的结合将大大提高人们获取信息的效率，而句法分析是向然语高理解的关键步骤 之一。本文提出了一+ 种依存句法分析模型十h 刘其它模型墩f ! ，了较好的效果。 j 一i m a s 的p 2 p 竹息享系统；f - gr i d 1 4 本文结构 本文首先介绍了p 2 p 系统的发展概况第二章介绍了本文所涉及到的背景知 识。首先，介绍了p 2 p 系统的结构及其分类，重点描述了几种驰型的p 2 p 系统 所采用关键技术、特点，分析了各自的优缺点；然后简要介绍了a g e n t 的概念、 技术，以及将a g e n t 技术的优越性。第四章给出f g r i d 的整体设计和规划。笫 五章介绍了f - g r i d 的核心结构一语义索引空问分析了其性能特点，结合模拟 实验结果，展丌讨论。第六章给出了f g r i d 的，i ：发平台，组成f g r i d 的各a g e n t 的具体功能特点和实现。筇七章探讨自然语言理解技术在信息检索中的应用，拙 述了基于最大熵的依存晤法分析模型。最后给j 1 了本文结论以及对今后： 作的展 望。 j l m a s 的p 2 pf ? i 息j “l 系统：1 7 g r k l 第二章背景知识 2 1p 2 p 信息共享系统现状 2 1 1p 2 p 信息共享系统中的资源发现机制 p 2 p 系统的主要好处之一就是让我们能够访问更多的资源。然而在p 2 p 系统 中，资源的数目与主机数的增加是分不丌的。如果信息发现方法不完善，那么随 着网络规模o f l j 。大将会出现一一个临界点，若超过这个j 界l i ，州使j = j j l 数u 继续 增加，刈网络中的每个主机而高，都不会增j j u 任何的可利j j 资源，甚至会使现有 资源的可用性下降。因此信息发现在p 2 p 系统中是十分重要。 目前的p 2 p 信息共享系统中的信息发现机制按其技术特点大致司分为集中 索引、查询广播、索引广播、社交启发及分斫j 路出等等。 1 ) 集中索引式发现l ：j l f l ；4 这是n a p s t e r i ”、e d o n k e y l l2 1 等系统的发现机制。在系统一i j 存在着。h 洲务器， 服务器上存放的刁i 是实际的数撕，而赴刚络巾指示信息位臀的索引。其它主j ! f 【l 通 过服务器上的索引信息来寻找资源。这种机制有着很高的性能，但是由于中心服 务器的存在，为了保障整个网络系统的丁f 常运行，服务器必须要用很高的代价来 构建。另外如果意外情况中心服务器被关闭那么整个p 2 p 网络就会瘫痪。 2 ) 查询广播发现机制 这是g n u t e l l a 4 所采用的发现机制。这种机制在查询处理过程中存在着很大 的灵活性。因为每个节点都自己决定如何处理查询消息。但是这种机制决定了系 统的不可扩展性，只能应刚于小型刚络，因为广播查询的木质决定了特宽需求会 随菥i 岫络舰模的扩火而急川j _ f l ：f j | 1 从而严匝影响发脱f 内效率，网络川采m 题也会 鼎得特别严重。 为了克服上述缺点，又产生了选择式推进路山发现机制。采用这利机制的网 络其伸缩性胜过采用扩散式广播机制的网络。在这种机制中，查询信息不是被发 给所有的其它主机，而是有选择地发送给最有可能自h 有相关资源的某些特定主 机。 3 ) 索引广播发现机制 这是p l a n e t p ”“1 采用的机制。这种方式f 门特点是网络中的任何一个节点均保 存全局的索引信息，减少了索引集中存储带来的问题。p l a n e t p 中节点生成以二 进制串表示的自身共享信息的索引概要用g o s s i p i n g 机制将摘要复制到网络中 所有其它节点。检索时，节点首先根掘自己收集到的摘要，确定哪些节点上i j 丁能 保存有目标信息：然后直接访问这些节点，进行更详细的查询。为了防止过多的 占用带宽，摘要的更新周期受到一定限制。然而这利机制也存在着缺陷。当节点 共享的信息更新频繁时，节点的摘要不能反应实际情况。随着网络规模的增大， 每个节点存储的摘要随之增加全局复制索引摘要所耗费的带宽和计算资源也将 急刷扩大。另外是否能够有效的利用摘要判断目标节点包含有用户感兴趣的信 中闻 ：i 学 生术人学坝卜学位论文拈- 一m a s 的i ) 2 1 ) 信息，i 享系统：f - g r i d 思，仍需研究。 4 ) 社交启发式发现机制 这是a l p i n l 4 卜4 2 】中所采用的发现机制。它是一种自适应的信息发现方法。在 这种方法中，每个h 点保存一定数量的朋友节点信息，查询时直接i 方问这些节点， 当这些节点不能满足查询要求时，则可向这些节点保存的朋友节点查询，以此类 推，最终可得到满足要求的内容。在运行过程中节点不断地将能满足自己要求的 节点加入自己的朋友节点信息表中，这样经过一定时闻的运行，每个节点都知道 与自己有共同志趣的其他竹点，查咖速度会越米越快。但是这种方法的关键问题 是如何有效合理地归类历史信息，这要涉及到知识发现、知识表达的问题，而这 些j 司题到目i j h 为止还没冉得到微妤的解决。而且钍交启发式发现4 j t $ l j 直接向系统 中小部分节点查询虽然增加了查询效率，但也导致了系统查询的不完全性，其 它节点上的大量有价值数据被忽略了。 5 ) 分布路由发现机制 以上四种发现机制中存在的一个共同缺点就是系统的扩展性，随着网络舰模 增大，他们的性能将不可避免的出现下降。为了解决这个问题，国外几个p 2 p 工作组分别提出了各自的撞于d h t ( d i s t r i b u t e dh a s h t a b l e ) 的分确j 路由算法。 它们利川哈希敝列函数为搜索空m 地立索引。将杂乱的信息柯序化，然后将信息 按照一定的舰利! 组纵，进而抽级山商效的查i f l j 算法完成准确查询定位。山于每个 节点都保存一张洲有其他少数节点的索引信息的路由表，所以这利r 算法被称为分 布路由算法。 分佃路山算法足新一代规模可扩展性路由算法，现在己经有t a p e s t r y pj ， p a s t r y i7 1 c h o r d i ”，c a n l 6 1 等较成功的范例。 分佃路由发现机制是基于内容的分布共享系统，它给基于内容的分布共享系 统【3 2 0 7 l 带来了良好的系统扩展性和信息可用性。所溜信息i u 用性足指如果文件 确实存在就一定能够找到。但是现有的分相路由算法只支持精确查询，它要求用 户必须提供语义无关的精确的查询关键字，文件以什么关键字发布，就必须以什 么为关键字查询，显然这一点在数百万用户自出发柿文件的p 2 p 环境里是很不 现实的，正是这个原因目6 u 众多的采用分布式路由机制的p 2 p 系统，多用于可 根据唯一标识访问的信息定位，如网络存储、服务定位等，比如o c e a n | 4 4 、 s j l v e r b a c k l 45 l 、c a n l 6 1 。 采月j 分嘶j 式路出发现机制的p 2 p 系统以它查询高效性、规模可扩展性、负载 平衡性吸引着人们仍在不断探索新的信息组织和发现方式，从而弥补现在采用分 斫i 路由算法的p 2 p 系统只能精确查询的缺点。 2 1 2 几种典型p 2 p 系统 2 1 2 1n a p s t e r v 2 pj x l , 暴可以说是由n a p s t e r l 3 1 的诞生而引起的。n a p s t e r 是一个基于服务器的 集中式文件共享系统，从结构上属于混合式的p 2 p 文件共享系统，所共享的文件 中| _ i 寸科学投术人学坝i j 学位论史 j l l 十m a s 的p 2 p 竹息 j # 系统：f - g r i d 类型只局限于m p 3 文件。川户在中心服务器上检索感兴趣内容的存储地址，然后 直接从存储这些内容的节点下载。山于是混合的p 2 p 模型因此当服务器出现问 题时，就会受到很_ 人的影响。后来由于各大影音出版公刮联合控告它侵犯版权， 改系统n 勺中心服务器被迫关闭，于是整个系统就垮了。 2 1 2 2g n u t e l l a g n u t e l l a 4 1 是一种采用分布式搜索协议的、能共享任何类型文件的网络应用， 它是纯p 2 p 系统。g n u t e l l a 中每个主机既是客户也是服务器，我们称之为s e r v e | 1 t s e r v e n t 为月】户提供了一个提交搜索要求和浏览艘索结粜灼界面，同时接收其它的 s e r v e n t f t ：j 查砌并进 1 ：搜索服务，在满足金咖要求的情况给请求f l ，j s e l v e n t 返回查 询结果山于采月1 分嘶j 式控制方式，1 i 存在中心服务器，倒此这种l 叫络具有高容 错性，而且其协议是公丌的，因此g n u t e l l a 是目时应用较为广泛的p 2 p 系统，它适 用于各种平台，用户软件也比较多。g n u t e l l a 中采用的扩敞式广播查找算法，这 种方法能灵活处理用户的查询要求，但是也使网络带宽被严重占用。随着网络中 主机数目的增加，g n u t e l l a 中单个查询所占用的带宽会按指数级增加，因此 g n u t e l l a 只适用于小型网络，可扩展性差，而且g n u t e l l a 并不保证数据的可用性 ( a v a i l a b i l i t y ) 2 1 2 3e d o n k e y e d o n k e y i l 2 j 是另一个比较优秀的混合式的p 2 p 文件共享系统。该系统与 n a p s t e r l ：e 较类似，但是能共享任意类型的文件。d o n k e y 将服务器端软件和客户 端软件分丌实现，但是这两个软件都可以免费获得，可以在任意一台拥有真实i p 地址的机器上构建服务器。这从一定程度上目日化了混合式p 2 p 文件共享系统的中 心失效问题。该软件基于m u l t i s o u r c ef i l et r a n s f e rp r o t o c o l ( m f t p ) 挑议，这个协 议使得一个文件在d o n k e y 中可以分成多个部分进行传输，实现断点续传功能。 当多台主机要求下载同一文件时可以形成传送链，从先下载的机器上获取所需 的文件部分，从而使文件分发速度加快，避免产生访问热点，：符约带宽。另外该 系统也具有聊天功能，并配有一个年对简单的搜索引擎。该系统是一个比较优秀 的孤立式的混合式系统。但是它有一个缺陷，就是各服务器之间缺乏信息交换。 用户如果想要进行全系统范围内的检索，必须逐个与服务器相连并查询。 2 1 2 4t a p e s t r y t a p e s t r y i5 j 是一个在广域删范围内能够容错发机信息和路由的越础框架，其路 由思想来源于p l a x t o n h 3 算法，但摒弃了p l a x t o n 要求掌握全局信息，难以扩展， 单点失效等缺点因而更灵活，而且具有自适应性和容错性等优点。t a p e s t r y 维 护的是一个网状空f n j 结构，每个节点及文件被分配了一个固定长度f 内标以符( 该 标u 符可以门j 哈希敞列算法得到) ，标识符被看作是以b 为基的连续数字，文件 位置信息 存储在与其标识符有最长共同后缀的某一特定节点 上，谚：节点被称为文件的根( m o t ) 在t a p e s t r y 中，每个节点维护一张两缴的邻表和一个相关节点表。节点的邻 表分l o b b n 层，每层包含b 个条目，每个条目引出两个指针，指向最满足条件的 中用科学技术人学坝i 学位论史筚于m a s 的p 2 1 ，侪息共享系统：f - g r i d 两个柑j i i ，分别称作主节点和次= 悼点。这个条什就是：邻表筇i 层叫_ i 指向的行节 点均0 当时节点有1 个共同后缀，而笫1 + 1 位有b 种可能，并| 距离当前：1 ，点最 近，其巾主m s 比次节点离当时：m _ 更近。 踏t l _ l 时，标点是目标文件的位筲信息所在点，每个节点郝选择邻表中与目 标点柯最人共j 司后缀的最近邻点作为下一跳点，如此一l 、古，直到到达某一节点， 孩节点的邻袭中唯一满足条件的节点是它本身，那么浚1 ，点即为目标点。 所l 以，t a p e s t r y 中到达目标点的最大跳数为l o g b n ，其中b 为标识符的基数， n 为逻辑空问内节点数。 t a p e s t r y 继承了p l a x t o n 算法的丝小心恕，从而扶得了j | ! 由长度0 0 0 9 n ) 的高效性，它又具有优于p l a x t o n 算法的许多特点： 1 路由时考虑了网络底层信息，因而路由时延期望更短。 2 灵活的复制机制：每个对象( o b j e c t ) 在不同节点内保存多个副本；每个副本 有多个根节点，解决了单点失效问题。 3 通过备份a ”、，姒1 - a 。, i j 表t + l 每个条目指向两个节点) 和定期向邻表中各邻点打招 呼的方法淘汰失效邻点，从而提高查询效率。 4 通过软件维护系统的稳定性( 发稚节点定期更新发嘶j 消息；节点定期与邻点 交换信息) 。 5 节点可以动念加入和离丌一易扩展。 2 1 2 5p a s t r y p a s t r y l 7 1 在i n t e r n e t 上构建了一个环形逻辑空恻，每个节点及文件被随机分配 了一个1 2 8 位的标识符，标识符被看作是以b 为基的连续数字。文件存储在与其 标识符数值最近的节点上。 p a s t r y 中每个节点维护一个叶子集，一个邻点集及一张路山表。叶子集中保 存的是l 个在标识符空间上与当前点相邻的节点的信息，其中u 2 个标识符比当 前点小，另l 2 个比当前点大。利用叶子集可以保证正确查询。邻点集中保存的 是在地理位露上与当时点邻近的m 个节点的信息，该表主要在形成或更新路由 表时作参考，使得路山表中节点在满足前缀条件的同时，应该是离当前点较近的。 路出表分l o g h n 层，每层包含b 一1 个条目。第1 层中的各条目均是与当前点 有1 个共同d 鸸& ，而第1 + 1 位有b 1 种可能的节点。如果没有满足条件的节点存 在，相应条目可空。而且路由表中各条目都是与当前点的物理距离相对较近的节 点。利用路山表可加快查询速度。 路出时，当目标点被叶予集覆盖时i “步完成查咖；否则，从路山表中选择 与目标标识符有更长共同