（计算机应用技术专业论文）基于节点兴趣的p2p信息搜索机制研究与实现.pdf

大连理工大学硕士学位论文 摘要 随着对等网络( p 2 p ，p e e r - t o - p e e r ) 规模和用户量的增加，p 2 p 环境下的信息量也随之 飞速增长，给用户在搜索、定位和获取信息资源上都带来了巨大的困难。对等网络信息 搜索技术是解决这一问题的重要手段较好的信息搜索技术不但能够提高搜索命中率， 减轻节点负载，降低网络开销，还能够根据用户的兴趣提高搜索性能，主动学习，为用 户的搜索节省时间，提高工作效率可见p 2 p 网络环境下的信息搜索技术，这一研究课 题具有一定的应用价值。 由于对等网络缺乏对网络中资源的整体把握，且多数搜索都是基于关键字的绝对匹 配，因此节点用户需频繁更换关键字，才能够搜索到满意的结果，并且节点用户的搜索 内容在一定程度上体现了该用户的兴趣。针对这一现象，论文提出了一种基于关键字关 联和节点兴趣的p 2 p 信息搜索机制。该机制注重关键字之间的关系的学习，注重通过用 户操作发现节点的兴趣。在以后的搜索中，利用关键字的语义关系，增加命中目标，提 高搜索成功率；根据节点的兴趣，缩小搜索范围，降低搜索开销。为了提高搜索性能， 还采取了快速建立索引表的方法和反馈机制。最后用较好的实验结果证明了算法的有效 性和高效性。 利用关键字描述文件具有不准确性，因此基于关键字的p 2 p 信息搜索限制了搜索性 能。用户发出的搜索请求不能充分地反映其喜好特征，利用节点上的共享文件，更易发 现该节点用户的兴趣所在针对这两点，本文提出一种基于类簇的音乐内容搜索算法。 利用音频特征抽取算法，进行短时傅立叶变换，得到信息熵、频谱中心、能量比等特征 的统计值，组成特征向量。通过自适应的聚类算法对本地音频文件进行聚类，发送建类 请求实现节点之间的兴趣聚类。详细阐述搜索策略，并提出改进搜索性能的动态c i t 更 新、类间节点优化和新节点启动优化等机制。最后用较好的实验结果和合理的性能比较 证明了本搜索机制的实用性和准确性。 关键词：对等网络；节点兴趣；基于内容的信息搜索；聚类 大连理：i ：大学硕士学位论文 n o d ei n t e r e s tb a s e di n f o r m a t i o nr e t r i e v a lm e c h a n i s mr e s e a r c ha n d i m p l e m e n t a t i o ni np e e r - t o - p e e rn e t w o r k a b s t r a c t p e e r - t o p e e r ( p 2 p ) a l li n n o v a t i o n a ln e t w o r kt e c h n o l o g y , i sr e g u l a r l yc o m i n gi n t o p e o p l e sl i v ea n di n d u s t r y i t su t i l i z a t i o n i sm o r ep r e v a l e n ti ns e v e r a l 丘e l d s s u c ha s f i l e - s h a r i n g , d i s t r i b u t e dc o m p u t i n ga n dc o o p e r a t i o nw o r k n i n f o r m a t i o na m o u n tr i s e s r a p i d l yw i t ht h ei n t e n s ei n c r e m e n to fb o t hu s e 幅q u a n t i t ya n dn e t w o r k ss c a l ea n dc a u s e da s e r i o u sp r o b l e m , d i f f i c u l t yi ns e a r c h i n g , l o c a t i n ga n dr e t r i e v i n gr e s o u r c , e t oc o n q u e rt h i s p r o b l e m , i n f o r m a t i o nr e t r i e v a li np 2 pn e t w o r ki sap i v o t a lt e c h n i q u e ag o o ds t r a t e g yn o to n l y i n c r e a s e sh i tr a t i o b u ta l s os e f v e sf o ru s e r si ns t u d y i n gr e l e v a n ti n f o r m a t i o nt oi m p r o v et h e p e r f o r m a n c ei nl a t o rs e a r c hp r o c e s s t h ea b i l i t vt od e c r e a s en o d el o a da n dn e t w o r kc o s ti s a n o t h e rg o a lag o o ds e a r c ha l g o r i t h ms e e k s c o n s e q u e n t l y ，t h ei n f o r m a t i o nr e t r i e v a li np 2 p n e t w o r ki sav a l u a b l er e s e a r c hd i r e c t i o n d u et ot h ei n a b i l i t yt oc o n t r o lt h ew h o l er e s o u r c ei nn e t w o r k , p 2 pi n f o r m a t i o nr e t r i e v a l h a st os t i c ki nt h em u do fu s e r s r e p e a t i n gw o r k , c h a n g i n gk e y w o r d sa n dt h ea b s o l u t e k e y w o r dm a t c h i n g l a c k i n gs u 伍e i e n ta n dd e s i r a b l er e s u l t si su n d e r s t a n d a b l ei nt h i ss i t u a t i o n o u rw o r ki sf o c u s i n gt h ep h e n o m e n o no ff r e q u e n tk e y w o r dc h a n g i n go p e r a t i o n , p r e s e n t i n ga n i n f o r m a t i o nr e t r i e v a lm e c h a n i s mb a s e do nk e y w o r dr e l a t i o n s h i p sa n dn o d ei n t e r e s t s t h r o u g h t h em e c h a n i s m , t h er e l a t i o n s h i p sb e t w e e nk e y w o r d sa l es t u d i e d ；t h en o d ep o s s i b l ei n t e r e s t s a r ed i s c o v e r e d i nl a t e rs e a r c hp r o c e s s , b a s e do nt h ek e y w o r dr e l a t i o n s ，e x p a n s i o no ft h e o r i g h 柏aq u e r yk e y w o r di n c r e a s e st h eh i tp o s s i b i l i t y , b a s e do nt h en o d ei n t e r e s t s , l i m i t a t i o no f s e a r c hs c o p er e d u c e st h en e t w o r kc o s ta n di m p r o v e st h es e a r c he f f i c i e n c y b e s i d e s ，i no r d e rt o e n h a n c et h ep e r f o r m a n c e t h er a p i dt a b l ec o n s t r u c t i o na r i df e e d b a c km e c h a n i s mi sa p p e n d e d a tl a s t , a u t h o rp r e s e n t e dad e s i r a b l ee x p e r i m e n t a lr e s u l t , ar e a s o n a b l ec o m p a r i s o na n dp r o v e d t h ev a l i d i t ya n de f f i c i e n c yo f t h ea l g o r i t h m t r a d i t i o n a li n f o r m a t i o nr e t r i e v a li sb a s e do nk e y w o r d ，a p p a r e n t l y , w h i c hi sn o tp e r f e c t l y s u i t a b l ef o rp e o p l e si n c r e a s e dn e e d s t a n d i n go nt h i sp o i n t , ac o n t e n d - b a s e di n f o r m a t i o n r e t r i e v a la l g o r i t h mi sp r e s e n t e d w h i c hi s m a i n l yu s e df o ra u d i of i l er e t r i e v a l ，n a m e d c l u s t e r - b a s e di n f o r m a t i o nr e t r i e v a ls t r a t e g y t h ea u d i of e a t u r ee x t r a c t i o ni st h ef i r s ts t e p m a i n p u r s u i to ft h i sp a r ti si n c l u d i n gt h ei m p l e m e n t a t i o no fs h o r t - t i m ef o u r i e rt r a n s f o r m ( s t f d a l g o r i t h ma n ds e v e r a lf e a t u r ee x t r a c t i o no p e r a t i o n ( a n t r o p y , c e n t r o i d ，c e n t r o i dr a t i o ， b a n d w i d t h , s i l e n c er a t i o ，e n e r g yr a t i o ，a n dl o e a t i o no fm i n i m u ma n dm a x i m m ne n e r g y ) t h e l a t e rw o r ka r e 、析t ht h ef e a t u r ev e c t o re x t r a c t e db e f o r ep e r f o r m i n gv e c t o rc a l c u l a t i o n , b u i l d i n g i i i 基于节点兴趣的p 2 p 信息搜索机制研究与实现 t h el o c a lf i l ed u s t e r , c o n s t r u c t i n gn o d ec l u s t e ra m o n gi n t e r e s tc o n t a c t s a f t e rp l 吲搬a n l l t ，a c o n c r e t es e a r c hm e c h a n i s mi si l l u s t r a t e d t oa c h i e v eab e t t e rp e r f o r m a n c e , t w oi m p r o v i n g m e t h o d sa r ep r o p o s e d , d y n a m i cc i tu p d a t ea n do p t i m i z e dd u s t e r - c l u s t e rn o d e a tt h ee n do f t h i sp a r t t h ee x p e r i m e n t a lr e s u l ta n dr e l e v a n tc h a r t sa r cl i s t e d , w i t ht h ed i s c u s s i o na n d a n a l y s i s , t h ec o n c l u s i o nt h a tt h ec l u s t e r - b a s e di n f o r m a t i o nr e t r i e v a ls t r a t e g yi sp r a c t i c a la n d a c c u r a t ei na u d i of i l er e t r i e v a li sp r o v e ds t r o n g l y k e yw o r d s ：p e e r - t o - p e e rn e t w o r k ；n o d ei n t e r e s t ；c o n t e n t - b a s e di n f o r m a t i o n r e t r i e v a l ；c l u s t e r i n g i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： ! 墓8 日期： 丑：! ：型 大连理工人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者虢! 笠壁 导师签名 丑年上月且同 大连理工大学硕士学位论文 1 绪论 1 1 对等网络的概念 对等网络( p e e r - t o - p e e rn e t w o r k ) 是近几年兴起的热门网络技术，改变了人们使用网 络的方式，也为未来网络的发展提供了一种新的思路。它是建立在i n t e r n e t 上的覆盖网 ( o v e r l a yn e t w o r k ) ，不同于传统的客户机，服务器模式，改变了集中存储和处理资源的方 法。顾名思义，对等网络中的每个节点的地位都是对等的，每个节点既充当服务器，为 其他节点提供服务，同时也享用其他节点提供的服务。同时，每个节点可以随时加入或 离开网络系统，系统的拓扑结构随时可能发生交化。对等网络最为人们所熟知的应用在 于文件共享，例如著名的n a p s t e r 就是利用对等网络提供相互共享音乐文件的一种服务， 并取得了巨大的成功。对等网络的概念并不局限于文件的共享，它在对等节点之间共享 资源和服务，可共享的计算机资源包括处理器的计算能力、存储器和磁盘空间等。 对等网络的概念其实很早就有，但直到近年来随着i n t e r n e t 的飞速发展、网络带宽 的成倍增加以及计算机计算能力的大大提高，对等网络又以一种新的形式引起了人们的 关注。以i n t c m c t 上的信息查找为例，i n t e r n e t 上的各种信息呈爆炸性增长，但利用现有 的任何搜索引擎或者门户网站都很难找到实时信息。而将来则可能通过对等网络技术， 建立一种分布式的搜索引擎，每个提供信息服务的节点都对自己保存的信息编制索引， 并回答其他节点的查询请求，实现实时的查询。虽然近年来网络带宽成倍增长，但热门 站点仍然越来越热，不堪重负，而空闲的链路带宽被白白浪费。利用对等网络提供的分 布式结构，可以有效均衡负载，充分利用带宽。计算机的计算能力按照摩尔定律在飞速 的增长，但增加的计算能力并未被充分的挖掘，对等网络为充分挖掘计算机空闲的计算 能力提供了可能。 目前有关对等网络的研究方兴未艾，国际上许多知名的大公司和一流的研究机构及 大学纷纷加入到对等网络的研究行列中，并取得了一批显著的成果。计算机网络和数据 通信领域最具权威的国际会议a c ms i g c o m mc o n f e r e n c e 白2 0 0 1 年起每年都会 发表数篇对等网络研究的最新论文，论文内容涵盖了从对等网络的体系结构到资源查找 等重要方面。这些都充分表明了工业界和学术界对于对等网络技术的重视和其发展的潜 力。 1 2 对等网络的应用 作为一种新型的网络应用体系结构，p 2 p 网络的应用发展迅速，己经在众多领域获 得成功应用，并且应用的数量和领域还在迅速发展中。 基于节点兴趣的p 2 p 信息搜索机制研究与实现 ( 1 ) 内容共享应用 p 2 p 网络赋予普通网络节点以个性化的方式共享内容的功能，是p 2 p 发展最早也是 最成功的应用。典型的内容共享系统包括n a p s t e r 、k a z a a 2 1 、m o r p h e u s 3 l 和g n u t e l l a l 4 1 等。p 2 p 内容共享应用己经成为互联网上的主流应用之一。从用户数量上来看，欧美比 较流行的p 2 p 内容共享软件k a z z a 和m o r p h e u s 的用户数以亿级别计算，超过所有网络 用户的一半以上，同时在线用户超过百万。从带宽消耗来看，许多i s p 主干带宽的5 0 以上被p 2 p 内容共享占用，而且还在持续增长中。 p 2 p 内容共享除了需要提高其服务质量之外，同时存在网络带宽消耗大，难以实现 可扩展的内容搜索等技术问题，而版权、管理等非技术性问题也制约了内容共享系统的 发展。 ( 2 ) 内容发布应用 内容发布应用是p 2 p 网络的重要应用领域。传统的基于c s 模式的内容发布应用的 服务能力的提高单纯依靠服务器集群、镜像服务器数量的增加，成本非常高昂，难于适 应用户需求的动态变化。p 2 p 网络利用普通节点的存储和带宽能力，有效减少对内容发 布服务器的压力，实现动态可扩展的内容发布服务。一些大型软件己经采用p 2 p 技术成 功完成大规模的发布【5 】。 ( 3 ) 内容存储应用 在基于p 2 p 的分布存储应用中，参与节点组成一个分布存储系统，每个节点都将自 己的部分内容存储到其它节点上，也为其它节点提供存储服务。基于p 2 p 的分布存储应 用的核心问题是数据定位算法，以及与之相关的数据复制，数据缓存、数据更新、访问 控制等关键技术。典型的分布存储应用研究包括p a s t 6 1 、o c e a n s t o r c 【刀等。 ( 4 ) 协同工作应用 协同工作是指多个用户利用网络中的协同计算平台，互相协同来共同完成计算任 务，共享信息资源等。利用p 2 p 计算技术，个人和组织可以随时采用各种方式建立在线、 非在线的协同应用环境。p 2 p 技术的出现，使得互联网上任意两台p c 都可能建立实时 的联系，构建一个安全、共享的虚拟空间，让处于不同地理位置的人们共同完成某个项 目或任务，而且p 2 p 能够较好的支持无线移动设备以及a d - h o c 网络。比较著名的p 2 p 协作系统包括g - r o o v e 、m a g i 等。 即时通信应用是一种简单的协同工作应用，参与节点之间可以实现直接的即时通 信。q q 、m s n 、a i m 等是典型的即时通信系统，这些系统都吸引了大量用户。j a b b e r 是一个开放源码的实时通信平台，提出了一个采用x m l 表示的，在不兼容的各种实时 通信平台之间进行消息交换的协议。 大连理工大学硕士学位论文 ( 5 ) 分布计算应用 p 2 p 网络可以聚合i n t e m e t 边缘大量计算机的空闲计算能力，得到可与昂贵的超级 计算机相比拟的性能。p 2 p 分布计算比较著名的项目有s e t i h o m e ，o e n o m e h o m e ， f o l d i n g h o m e ，d i s t r i b u t e d n e t 等等。p 2 p 计算适用于一些可并行化，计算量大但计算 单元之间通信量小的计算任务。需要解决的问题包括任务的分解算法、计算结果的验证、 引入商业模式激发用户参与的兴趣等。 ( 6 ) 无线移动网络应用 移动自治网络与p 2 p 网络有很多相似之处：动态网络特征，节点随时加入和退出网 络；多跳特性，节点之问的通信可以是多跳连接；分布控制特性，节点同时充当客户端 和服务器的角色p 2 p 网络的自组织技术、路由协议、容错通信都可以应用到移动自治 网络领域，提高移动节点的流量控制、负载均衡、近似路由等特性。当前p 2 p 技术与无 线网络技术的交叉应用已经成为研究热点【町。 1 3 对等网络研究的关键问题 对等网络的体系结构发展方向是基于分布式哈希表的结构化对等网络。但无结构对 等网络由于其管理简单，搜索机制灵活，所以仍将在某些领域中得到广泛的应用。对等 网络的安全问题主要是如何在一个开放的环境中防止恶意节点的攻击，可以通过建立节 点间的信誉机制等措施改善对等网络的安全。 同任何大规模的分布式系统一样，对等网络系统成功与否不仅仅在于其网络结构的 合理和有效，在很大程度上取决于其资源查找机制的灵活性和可扩展性。有效的搜索机 制一直是对等网络研究最活跃的领域之一，虽然不断有新的搜索机制被提出，但还没有 哪一种搜索机制可以脱颖而出，成为最佳选择。 本论文的努力方向是基于节点兴趣的信息搜索。节点的用户具有一定的兴趣，通过 节点用户发送搜索请求的内容和共享文件的内容能反映出其兴趣，为兴趣相似节点建立 直接连接，缩小信息搜索范围，实现较小代价下的高命中率和准确率。希望能为p 2 p 信 息搜索研究提供一些有益的借鉴。 基于节点兴趣的p 2 p 信息搜索机制研究与实现 2 对等网络研究现状及背景知识 从最初以n a p s t e r 为代表的有着中央目录服务器的对等网络结构，发展到后来以 g n u t e l l a 为代表的完全分布式的无结构对等网络和提供节点匿名发布和获取文档的 f r e e n e t ，再到以c a n 、c h o r d 等为代表的基于分布式哈希表的结构化对等网络，对等网 络的发展历经了大致三个阶段，分别采用了不同的资源定位和路由模型。本章将对这三 种最重要的对等网络模型加以介绍，并描述三种对等网络模型中的一些典型系统，重点 描述它们所采用的搜索机制以及现有机制存在的不足。本章最后对全文用到的一些背景 知识加以介绍。 2 1 集中式对等网络系统 对等网络首先引起人们的注意是从n a p s t e r 时代开始的，n a p s t e r 虽然不是严格意义 上最早的对等网络，但却是第一个通过i n t e r n e t 获得大规模应用并取得巨大成功的对等 网络系统。抛开法律上的因素不谈，n a p s t e r 的成功得益于其采用的基于中央目录服务 器的集中式对等网络结构。基于中央目录服务器的对等网络搜索模型工作方式如图2 1 所示。图中每个节点向中央目录服务器提交本地存储的文档目录，并由目录服务器编制 文档的索引。节点向中央目录服务器发起搜索请求，并由目录服务器检索本地文档索引 后返回存储匹配文档的节点地址。文档的下载直接在搜索请求的发起节点和期望文档的 存储节点之间进行，不再通过中央目录服务器。 - 图2 1 基于中央目录服务器的搜索模型 f i g 2 1s e a r c hm o d e lb a s e do nc e n t r a l $ e r v e l 大连理工大学硕士学位论文 以n a p s t e r 为例，所有节点共享的文档目录存储在一个中央目录服务器上。新加入 的节点将其要共享的文档目录上传到目录服务器，并由该服务器对这些目录信息进行索 引。节点查找和下载文档的过程如下，如图2 1 所示： ( 1 ) 当节点a 需要查找某个文档时，该节点向中央服务器提交查询请求，指明欲查 询文档的某些属性，例如作者、关键字等。 ( 2 ) 中央服务器通过检索存储的目录索引，找到共享该文档的所有节点，并返回它 们的口地址列表。 ( 3 ) 节点a 通过比较返回列表中各个节点p i n g 操作完成的时间，选择一个时延最 小的节点b 。 ( 4 ) 节点a 直接连接节点b 并完成文档下载，这一过程不再通过中央目录服务器。 从上面的过程我们可以看到，由于采用了中央目录服务器，n a p s t e r 可以提供快速 准确的搜索服务。搜索的方式也可以很灵活，其灵活程度和准确度取决于用户提供给目 录服务器的文档目录信息的详实程度。但是这种结构最大的缺陷在于可扩展性不高。集 中式的中央目录服务器容易成为系统的瓶颈。n a p s t e r 的另外一个缺陷是安全性较差， 密码以明文传输，没有认证机制，不能提供匿名。 2 2 无结构对等网络系统 无结构的对等网络系统采用完全分布式的拓扑结构。之所以称其为“无结构”，是 和下一节将要介绍的结构化对等网络相对而言的。无结构对等网络中每个节点之间是比 较松散的关系，节点的加入和离开仅需遵循一些简单的规则。无结构对等网络中每个节 点保存各自共享的文档，由于不再存在中央目录服务器，每个节点对本地保存的文档进 行索引，并转发或应答其他节点的搜索请求。 在无结构对等网络中，由于缺乏中央目录服务器，且文档并不存储在特定的节点上， 所以资源查找最基本的方式是泛洪( f l o o d i n g ) 。图2 2 是基于泛洪搜索模型的示例，图中 每个节点都将接到的搜索请求转发给所有的邻居节点，并由邻居节点进一步转发给更多 的邻居节点，直至找到期望的文档或者达到系统允许的最大搜索跳数后搜索失败。如果 成功找到所需的文档，那么搜索请求的发起节点直接从期望文档的保存节点那里下载所 需文档。 由于采用完全分布式的网络拓扑，无结构对等网络避免了集中式对等网络中中央目 录服务器带来的系统瓶颈的问题。但由于无结构对等网络中缺乏有效的搜索机制，只能 采用泛洪或类似泛洪的盲目搜索方式，导致在网络中产生过度的流量，同样影响了系统 的可扩展性。下面介绍两个无结构对等网络模型的代表。 基于节点兴趣的p 2 p 信息搜索机制研究与实现 - - + 一一 图2 2 基于泛洪的搜索模型 f i g 2 2s e a r c hm o d e lb a s e do l lf l o o d i n g ( 1 ) 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 ”( g n u t e l l a - l i k e ) 的无结构对等网络系统。g n u t e l l a 的协议规范在文献 9 】中有详细的描述。简言之，g n u t e l l a 是一个用于文档共享的对等网 络系统，它通过将搜索请求同时转发给尽可能多的邻居节点进行文档的搜索，它还通过 设置大于零的t r l 值来限制每个搜索请求传播的范围以避免过多的网络流量。对于大 量分布在系统中的热门文档，g n u t e l l a 的工作方式比较有效。但对于分布在系统中少量 节点上的稀有文档，g n u t e l l a 只能通过设置较大的t t l 值才能有效的找到，但这又会产 生大量的网络流量。r i t t e r 通过对g n u t e l l a 的搜索协议进行分析发现，对于一个包含1 8 个字节的搜索请求，如果将它同时转发给8 个邻居节点并且将t r l 也设为8 ，那么仅仅 文档的定位就将产生约1 2 g 字节的总流量【m l 。 为了提高g n u t e l l a 的可扩展性，人们纷纷提出了各种改进的g n u t e l l a 协议。m o h r 提出了对g n u t e l l a 协议进行扩展，除了原有的关键字搜索之外，增加了通过文档内容哈 希值进行搜索的方式【1 1 1 ，可以减少系统中有着不同名字的相同文档对搜索性能的影响。 t h a d a n i 提出在g n u t e l l a 的搜索请求中同时包含元数据和关键字可以提高搜索的精膨1 2 1 。 r o h r s 提出通过在相邻节点之间交换各自保存文档的关键字的方案来降低搜索的盲目 性，提高g n u t e l l a 的可扩展性【”】。 l v 等在文献b 4 1 中提出通过利用c m u t e l l a 网络中的异质性，限制发往带宽较小节点 的搜索请求数量，同时增加发往带宽较大节点的搜索请求数量来提高g n u t e l l a 的可扩展 6 大连理工大学硕士学位论文 性。s r i p a n i d k u l c h a i 通过研究g n u t e l l a 中搜索字符串的分布规律，发现它们遵循z i p f 分 布，进而提出并通过实验验证，在系统节点中缓存哪些最常被搜索的查询结果可以大大 降低网络上由泛洪引发的流量，提高系统的可扩展性【1 5 1 此外，s i n g l a 等还提出了 u l t r a p e e r s 的改进方案【1 6 1 ，该方案选择g n u t d l a 网络中有着较高带宽和计算能力的节点 担当超级节点的角色关于提高g n u t e l l a 可扩展性的最新进展来自文献【1 7 】，c h a w a t h e 等通过对g n u t e l l a 的设计增加了流量控制、动态拓扑调整、以及用随机步搜索替代泛洪 搜索等改进提出了一种新的无结构对等网络g i a ，并验证了它相对于g n u t e l l a 三至五个 数量级系统容量的提高。 l v 等在【l s 】中通过模拟实验验证了无结构对等网络中多随机步搜索方案的有效性， 得出1 6 至6 4 个随机步是比较恰当的选择。实验表明采用多个随机步的搜索机制可以将 泛洪搜索在网络中产生的流量降低两个数量级。g k a n t s i d i s 等在文献【1 9 】中进一步对无结 构对等网络中的随机步搜索进行了定量分析，并指出当对等网络的拓扑结构呈现出较强 的簇的特性以及同一个节点重复发出类似的搜索请求时，随机步搜索可以获得比泛洪搜 索更好的结果。 ( 2 ) f r c e n c t f r e e n e t 是一个完全分布式的，支持匿名的文档存储和获取的对等网络系统。严格意 义上，f r c c n e t 并不是像g n u t e l l a 那样完全无结构的对等网络系统，它可以归为介于无结 构对等网络和下一节将要介绍的结构化对等网络之间的一类有着松散结构的对等网络 系统。c l a r k 在文献【2 0 】， 2 h 中对f r e e n e t 的设计做了详细的描述。f r e e n e t 设计的一个重 要目标是支持文档的发布者、存储者、和请求者的匿名性，为了实现这一目标，f r e e n e t 中采用了和其他无结构对等网络不同的文档路由、插入及搜索方式。 f r e e n e t 中主要用到了两种标识符，一种是c h k ( c o n t e n t - h a s hk e y ) 。另外一种是s s k ( s i g n e d - s u b s p a e ek e y ) 。c h k 用来标识文档本身，而s s k 贝l j 用来标识存储c h k 的文档。 c h k j i 匝过对文档全文进行哈希变换得到，而s s k 则通过对发布文档用户的公钥以及描述 文档的文本信息进行哈希变换得到哈希变换算法采用的是s h a 1 。s h a - 1 可以保证对 于不同输入而生成相同哈希值的概率几乎为零。c h k 和s s k 在f r e e n e t 中有着不同的作 用：c h k 是面向系统的，系统通过c h k 路由、插入和搜索文档；而s s k 贝i j 是主要面向用 户的，用户可以通过对文档简要的描述找到自己感兴趣的内容，并通过s s k 找到c h k ， 最终在系统中找到所需文档。为了对文档内容提供保护，f r e e n e t 在文档发布之前通过随 机产生的加密密钥对文档内容进行加密，c h k 随同解密密钥一同存储在s s k 所标识的文 档中。 基于节点兴趣的p 2 p 信息搜索机制研究与实现 f r e e n e t 通过s s k 为每个用户创建一个私有的文档名空间，可以更好的管理不同用户 各自发布的文档。只有名空间的所有者可以写入文档，其他用户只能读取名空间中的文 档。为了生成s s k ，每个用户首先随机生成一对公钥和私钥，私钥用来对s s k 标识的文 档签名，以提供某种程度的文档完整性。对于将要发布的每个文档，用户提供一个简短 的描述，例如：t e x t p h i l o s o p h y c o n f u c i u s a n a l e c t s 。通过对公钥和描述文本分别进行哈希 变换，并将结果连接起来再次进行哈希变换，最终得到该文档的s s k 。s s k 用来标识存 储文档c h k 值和解密密钥的文档。关于文档的简要描述和用户的公钥一起以带外 ( o u t - o f - b a n d ，例如公布在某个w e b 服务器上) 的方式发布出去。用户对一个文档的请求需 要经过两个步骤：首先通过文档的描述信息和公钥得至u s s k ，并通过s s k 得到包含文档 c h k 和解密密钥的文档；然后通过该文档中的c h k 和解密密钥得到最终解密的文档。这 种对文档间接访问的好处在于文档的更新变得更加容易，由于文档更新通常只是内容的 改变，而其描述信息是不变的，即s s k 保持不变，所以只需将更新后文档生成的新c h k 的值替换相应s s k 所标识文档中的i f l c h k 值即可，这对文档的请求者是透明的。 f r e e n e t 中文档的搜索请求是基于文档标识符进行路由的，和在类g n u t e l l a 的无结构 对等网络中的盲目搜索不同，f r e e n e t 采用的是一种基于节点路由表中“提示”信息的深 度优先搜索方式。所谓“提示”信息指的是存储在节点路由表中的形如( 标识符，节点 地址) 的二元组。每个节点通过比较收到的文档标识符和路由表中的各个标识符，选择 一个数值最接近的表项，并将收到的文档标识符路由到该表项中对应的节点。如果某个 节点找不到合适的节点来转发搜索请求，则将搜索请求返回前一个节点，前一个节点继 续将搜索请求转发给路由表中指向的下一个最接近节点。这一过程一直持续到找到存储 匹配文档的节点，或者达到最大搜索跳数后搜索失败。 如果搜索成功，目的节点将所请求的文档沿着搜索请求的来路原路返回，途中经过 的每个节点都保留该文档的一个副本，并通过添加前一个节点和返回文档的标识符更新 其路由表，直至返回搜索请求的发起节点。由于搜索请求和文档返回的路径都是通过途 中多个节点串联起来的，每个节点都保留了文档的副本并谎称自己是搜索的发起者或者 文档的持有者，所以很难确定哪一个节点发起了搜索请求以及哪一个节点存储了所请求 的文档，从而实现了匿名。 搜索过程如图2 3 所示。图中节点a 发起搜索请求，并转发给节点b ；节点b 将搜索 请求转发给路由表中和节点a 发来文档标识符最接近的表项对应的节点c ；节点c 没有匹 配文档，返回节点b ；节点b 继续将搜索请求转发给下一个最接近节点d ；节点d 将搜索 请求转发给节点a ，节点a 没有匹配文档，返回节点d ；节点d 继续转发给节点e ；节点e 一8 一 大连理工大学硕士学位论文 找到了匹配文档，将文档按原路经过节点d 和节点b 返回，节点d 和节点b 在保存文档副 本并更新本地路由表后，最终将文档返回给节点a 。 _ + 查询 失败 一一卜下载 图2 3 基本f r e e n e t 搜索过程示例 f i g 2 3e x a m p l eo f f r e e n e ts e a r c hp r o c e s s f r e e n e t 在文档插入系统时，首先发布一个针对该文档标识符的搜索消息，该消息将 在系统中传播直至达到系统设定的最大搜索跳数，此时将文档插入搜索终结的节点中。 f r e e n e t 中每个节点聚集了一批标识符相近的文档，由于文档经过了加密，所以每个节点 不知道本地存储了哪些文档。f r e e n e t 通过加密和文档按查询路径返回并在每个节点保留 副本的方式保证了文档存储者、发布者和请求者的匿名性。 在f r e e n e t 中用户必须首先知道其所需文档的标识符才能发出搜索请求，这影响了 f r e e n e t 搜索机制的灵活性，给用户带来了不便。k r o n f o l 提出了对f r e e n e t 的一个扩展，为 f r e e n e t 增加了元数据搜索功甜翻。还有其他一些对等网络系统也采用了和f r e e n e t 类似的 结构，并提供了相近的功能和安全特性。f r e eh a y 饥【2 3 矛d m o j on a t i o n 通过引入信任及文 件交换等机制增加了对等网络中节点的可靠性。p u b l i 心2 4 】通过将文档分片并将冗余的文 档碎片分布在多个节点的方式增强了对等网络的鲁棒性。 2 3 结构化对等网络系统 结构化对等网络也是完全分布式的对等网络系统，通常采用的是分布式哈希表 ( d i s t r i b u t e dh a s ht a b l e ) 的结构。和无结构对等网络相比，结构化对等网络对文档在系统 中的存放位置有严格的控制并且节点之间的关系比较紧凑。结构化对等网络的最大优点 在于它可以在o ( 1 0 9 n ) ( 其中n 是系统中节点的数目) 的跳数之内完成文档的路由和定位。 一9 一 基于节点兴趣的p 2 p 信息搜索机制研究与实现 结构化对等网络的主要特点是自组织、可扩展、负载均衡以及较好的容错性。和无结构 对等网络主要用于文件共享领域不同，结构化对一等网络的这些优良特性使得它可以应 用在对可靠性和扩展性要求比较高的场合。 简单的理解，结构化对等网络中每个文档对应一个m 比特长的唯一标识符，可以将 文档的这个唯一标识符理解为一个虚拟空间中的地址。整个虚拟空间被划分为很多个区 域，每个区域包含了若干连续的虚拟地址，系统中的每个节点负责这些区域中的一个或 多个文档被存储在负责它的虚拟地址所在区域的节点中，对文档的插入和查找操作的 路由通过文档的虚拟地址进行。虚拟空间中区域的划分和负责每个区域节点的选择都是 动态的，每次节点加入或者离开系统都会导致动态的调整。文档的唯一标识符通过对文 档内容或u r l 进行哈希变换得到，一致性哈希变换( c o n s i s t e n th a s h i n g ) 2 5 】是最常用的算 法。一致性哈希变换的特性是可以将变换后得到的m 比特长的文档标识符均匀分布在一 个值空间中，不同文档产生相同哈希值的概率几乎为零。通过对节点的妒地址进行相 同的哈希变换得到唯一的节点标识符，并将节点标识符也映射在同一个值空间中，可以 将文档存储在有着和文档标识符最接近的节点标识符的节点那里。 相联路径 路由路径 节点i d ：0 0 0 5 0 0 文档i d ：0 0 0 0 8 0 节点0 0 0 8 0 0 点i d ：0 0 0 0 6 0 节点i d ：0 0 0 2 0 0 节点i d ：0 0 0 1 2 0 图2 4 结构化对等网络文档路由示例 f i g 2 4 f i l e m u t i n ge x a m p l e o f s t r u c t u r e d p 2 p i l e t w o i 妇 结构化对等网络中主要提供两种操作：文档的插入和文档的查找。这两个操作都是 通过文档的唯一标识符进行的。系统中每个节点在路由表中保存和其相邻的节点的信 息，并比较收到的文档标识符和路由表中的节点标识符，通过选择数值上和文档标识符 最接近的节点标识符对应的节点完成文档的路由。 大连理工大学硕士学位论文 结构化对等网络中基于文档标识符的路由方式如图2 4 所示。图中节点a 发出对文 档标识符为0 0 0 8 0 0 的文档的查找请求，通过和它两个相邻节点b 和c 的标识符进行比 较，节点a 发现节点c 的节点标识符和其所请求文档的文档标识符更接近，于是节点a 将查找请求转发给节点c ；通过类似步骤，这个查找请求经过了节点c 和d ，最终到达 节点d ；节点d 的标识符最接近所请