（计算机软件与理论专业论文）基于语义检索的结构化p2p网络模型研究.pdf

璃灞瓣瀛谶蕊蕊藤裔舔赢瓣稿灞瓣缀磊荔灞瀚镶溺瓣蠢丽露灞滋瓣域茹矗器鼋氟蚕蠢磊纛赫蠢瓣茹荔藕添蕊酝珏溺蒜瓣纛磊季翥i 溺瀛黼；嚣舔磊；藏磊 西华大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：豸弘殇钎够 日期：力彳知 荫矧叫 日期洲口、【 l 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的金部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文( 保密的论文在解 密后遵守此规定) 学位论文作者签名：霉猾粥易 日期：y 夕彳加 一v、 九1专 专 名 h 参 山 教舄 铋期 削日 西华大学硕士学位论文 摘要 p 2 p ( p e e r - t o p e e r ) 技术作为i n t c r n c t 的重要技术之一，近些年来受到了计算机业界 较为广泛的关注。而目前大部分p 2 p 网络应用虽然都由p 2 p 主流网络模型支撑，但是由 于其主流网络模型算法自身的局限性，并不适合一些有特殊需求的p 2 p 网络应用，如语 义检索等，因此我们需要寻求更为适合的网络模型。 本文首先研究和分析了向量空间模型的原理，并在此基础上，提出了一种改进的基 于向量空间模型的文本聚类算法一z h s c m 算法。此算法一般情况不需要比较所有簇 之间的相似度，执行速度相对较快，可适用于大规模文件系统，实用性较高。另外，在 聚类过程中不需要事先确定簇的数目k 的取值，降低了与领域知识的依赖性，提高了灵 活性和扩展性。 随后本文总结和分析了目前主流p 2 p 网络模型和语义模型的发展现状和趋势，在 z h s c m 算法的基础上，对结构化p 2 p 网络模型做了迸一步的扩展，。提出了一种基于 c h o r d 的层次式p 2 p 网络模型基于语义检索的结构化p 2 p 网络模型( p n s s s t r u c t u r e d p 2 pn e t w o r km o d e lb a s e do ns e m a n t i cs e a r c h ) ，并分析了该模型的信息检索流程和工作 过程。p n s s 模型旨在为用户提供更高效准确的信息资源发布、查找等用户服务功能， 使用户能够快速、准确地找到所需要的资源，提升p 2 p 网络信息检索的查准率和查全率。 关键词：p 2 p ，d h t ，c h o r d ，文本聚类，向量空间模型，语义检索 鳓藩簿黼赫瀚黼辜瑶赫灞酾黼螽蠡蒸舔氟彝蓊添焉劾弱舔黼藤露磊女焉藏蓊瓣荔藏蔼蕊嚣藤豸蕊夏；赢麓蕊灞瀛霉籀荔瓣瀛瀛黼瓣磊糕蕊躺磊纛器蓊 t h ep a p e rt h e ns u m m a r i z e sa n da n a l y z e st h ec u r r e n tm a j o rp 2 pn e t w o r km o d e la n d s e m a n t i cm o d e lo fd e v e l o p m e n ts t a t u sa n dt r e n d s ，a n do nt h eb a s i so ft h ez h s e ma l g o r i t h m ， s t r u c t u r e sp e e r - t o - p e e rm o d e lf o rf u r t h e re x p a n s i o n m e n t i o n sac h o r d 1 e v e lp 2 pn e t w o r k r o o d e l - s t r u c m r e dp 2 pn e t w o r km o d e lb a s e do ns e m a n t i cs e a r c h 口n s s ) ，a n da n a l y z e st h e i n f o r m a t i o nr e t r i e v a lp r o c e s sa n dw o r kp r o c e s so ft h em o d e l p n s sm o d e ld e s i g n e dt op r o v j 【d e u s e r sw i t hm o r ee 伍c i e n ta n da c c u r a t es e r v i c ef u n c t i o n s s u c ha st h er e l e a s ea n dd e l e t i o no f i n f o r m a t i o nr e s o u r c e s 。降乃i c he n a b l et h eu s e r st oq u i c k l ya n da c c u r a t e l yf i n dt h en e c e s s a r y r e s o u r c e st oi m p r o v et h ep 2 pn e t w o r ki n f o r m a t i o nr e t r i e v a lp r e c i s i o na n dr e c a l lr a t i o k e yw o r d s ：p 2 p ；d h t ；c h o r d ；c l u s t e r i n g ；v e c t o rs p a c em o d e l ；s e m a n t i cs e a r c h i i 西华大学硕士学位论文 目录 摘 要i a b s t r a c t i i 1 绪论1 1 1课题的研究背景1 1 2 国内外研究现状1 1 3 目标3 1 4 本文的内容组织结构3 2p 2 p 及p 2 p 搜索技术简介4 2 1p 2 p 的技术背景4 2 2 p 2 p 网络的分类4 2 2 1非结构化p 2 p 网络5 2 2 2 结构化p 2 p 网络8 2 3p 2 p 网络信息检索概述1 0 2 3 1p 2 p 网络信息检索的动机1 0 2 3 2 传统的p 2 p 网络信息检索1 1 2 4 语义检索1 2 2 4 1 相关概念1 3 2 4 2 原理介绍1 3 2 5 本章小结15 3 z h s e m 聚类算法j l6 3 1向量空间模型介绍1 6 3 1 1 文本聚类的研究1 6 3 1 2 文本聚类过程1 7 3 1 3 向量空间模型1 7 3 2 基于距离的文本聚类算法1 9 3 3 传统聚类算法分析1 9 3 4 z h s e m 文本聚类算法：o k 。2 0 3 5 本章小结- 2 l 4 基于语义检索的网络模型_ p n s s 2 2 4 1 问题的提出：2 2 4 2 设计思想一2 4 n i 塑骥爱塑黧缫塑塑氅簸璧篓塑釜赫鳓泓酝翰黉磁藕蕊蟊霭赫瀚藏瀚麟蕊券赢萄露囊藏戳蒸瓣蕊蕊聂灞瓣霉蕊黼面赢翥蓊瓣爵葛j 礴黼甏舞瓣 基于语义检索的结构化p 2 p 网络模型研究 4 3 模型的构建2 5 4 3 1模型中节点的等级划分2 6 4 3 2 模型的逻辑拓扑2 6 4 3 3 上层和中层网络2 7 4 3 4 下层网络。2 8 4 4 心跳协议2 9 4 5 数据结构2 9 4 6 网络的动态维护3 3 4 6 1 节点的加入3 4 4 6 2 节点的离开3 4 4 6 3节点的失效。3 5 4 7 资源发布及定位过程描述3 6 4 7 1 资源的发布3 6 4 7 2 资源的定位3 6 4 8 模型性能分析3 8 4 9 模型仿真3 8 4 9 1n s 2 仿真系统简介3 9 4 9 2 数据分析4 0 4 1 0 本章小结4 2 结论。4 3 参考文献：4 5 攻读硕士学位期间发表学术论文情况4 9 致谢? 5 0 西华大学硕十学位论文 1绪论 1 1 课题的研究背景 本文课题来源于四川省教育厅重点项目：p 2 p 系统中复杂搜索技术的研究。项目编 号0 8 z a 0 2 3 。 随着计算机的普及，相关技术的成熟以及网络的飞速发展，i n t e m e t 应用在世界范 围内的日益广泛，网络规模越来越大，在现代社会生活中的作用也越来越突出。为了充 分利用分散在网络上的每台计算机中的资源，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 直接将人们联系起来，让人们通过互联网可以直接交互。p 2 p 使得网络上的沟 通变得更容易、更直接，真正地消除了中间商。p 2 p 就是人可以直接连接到其他用户的 计算机、交换和共享文件，而不是像过去那样连接到服务器去浏览与下载。p 2 p 的另外 一个重要特点则是改变互联网现在的以大网站为中心的状态、重返“非中心化”，并把 权力交还到用户手中。 p 2 p 目前而言，最大的优势就是，它可以提高网络用户的网络利用率，因为多个节 点互相连接，用户所在的网络带宽必将会被最大程度的利用。 语义检索本身还是信息检索，但它强调的是“语义”，这与目前的文本匹配相对的。 目前的信息检索，不管是采用元数据的还是采用全文文本的，都是基于文本字符串匹配 的，这种检索带来的问题很显然，如不同的两个词可以表示完全相同的意义，而一个词 在不同的语境中又可以有不同的意义，这样就在一定程度上限制了检索的准确性和全面 性。语义检索则是关注信息资源的意义，而不仅仅是停留在其表层文本上，因而可以克 服基于文本匹配的检索的弊端，这也是两者间本质上的区别。 原始的基于d h t 的p 2 p 网络只提供针对单一关键字的查询技术，无法很好的反映 文档语义，如果文档存在多个关键字，需要采用哈希算法得到某个关键字的存储位置， 并分别针对各个关键字进行多次查询：发布文件时也同样需要对每个关键字进行哈希以 获得多个存储位置，如此占用了大量的网络带宽，故原始的基于d h t 的p 2 p 网络不能 很好支持语义搜索。因此，需要针对其中的弊端，研究满足其要求的网络模型。 1 2 国内外研究现状 目前，在p 2 p 语义检索方面的研究主要集中在以下几种方测1 2 】： ( 1 ) 利用用户兴趣或行为提高检索性能。 基于语义检索的结构化p 2 p 网络模型研究 文献f 3 1 基于这一原理，提出使用兴趣捷径( i n t e r e s t b a s e ds h o r t c u t s ) 来改进g n u t e l l a 的查询性能的方案，该方案通过节点的查询历史或与其他节点交流的方式来获得感兴趣 的节点地址作为捷径，在以后的查询中优先向这些节点发送查询请求，从而大量减少 f l o o d i n g 的数量。文献4 1 认为用户的兴趣是比较稳定的，即节点未来查询的数据和节点 当前存储的数据应该同属于一个类别，它通过计算节点上所有文件名的词频向量的 j e n s e n s h a n n o n 分歧值来得到节点的相似度，进而将用户进行分组，在以后的查询中， 用户向比较有可能返回结果的用户组发出查询。文献【5 ，6 】也提出了用户分组的思路，但 文献【5 】利用资源的类别得到用户的兴趣，而文献【6 】则通过分析节点的历史查询记录发 现用户的兴趣。文献f 1 】提出了一种新颖的语义搜索方案，它利用p 2 p 共享系统中海量用 户的搜索行为与下载行为自动计算关键字与资源内容的相关度，利用相关度来实现基于 资源内容的搜索机制，具有实现代价小、时间复杂度低、可进化和支持语义搜索的优点， 实验证明它具有较高的查询命中率和准确率。 ( 2 ) 在p 2 p 覆盖网上构建语义覆盖网( s e m a n t i co v e r l a yn e t w o r k s ，s o n s ) ，形 成双层或多层网络逻辑结构。 检索时，优先查找语义相似节点集，可提高查准率和检索效率。语义覆盖网由具有 相似知识内容的节点聚类形成，需要解决的问题有【5 】：提问和节点首先要能够分类；分 类的粒度大小选择；节点如何加入一个s o n s ；在回答用户提问时选择哪个s o n s 搜索。 文献f 7 1 提出了三层系统结构：单元层( 一个信息单元，如一个文档或一幅图片) 、节点 层( 信息单元所属的节点) 和超级节点层( 一群节点组) ，主要采用向量空间模型( v s m ) 和隐含语义索引( l a t e n ts e m a n t i ci n d e x i n g ) 生成三层结构支持检索。文献【8 】针对s e m r e x 系统，提出根据节点之间的语义相似度生成语义拓扑网络。文献【9 】基于c a n 构造的 p g r o u p 介于结构化和非结构化之间，节点根据内容的类别自组织在一起，包含相同类 别的节点相互关联构成语义对等网。文献【1 0 】基于语义网和小世界理论提出了一种对等 网搜索模型s e m 锄t i c p 2 p 。模型中节点依据小世界理论在物理上形成自然的区域自 治系统( a a s ) ，各a a s 依据幂规律选取各域内的超节点，超节点再根据语义关系形成多 个超节点语义网，从而形成一个层次化的超节点叠加网络模型。文献【1 1 】通过对节点上 的文档集合进行聚类得到不同的主题，然后按照主题将含有相同主题文档的节点组织成 主题覆盖网络，在p 2 p 搜索过程中，只将查询消息路由到与查询主题相关的节点上。 ( 3 ) 通过对节点知识或节点提问进行语义标引支持语义检索。 由欧盟资助的s w a p 1 2 项目从分析、架构、开发方式、实现工具到集成等多方面 提出了一种将p 2 p 和本体应用于开发分布式知识检索与管理的方法论。文献 1 3 】以旅游 业为例，研究了如何对节点的信息抽取和知识表示、提问处理，并构建了支持语义检索 西华大学硕士学位论文 将含注释的关键字发送到传统的网页搜索引擎，得到一个统一资源定位向量结果。 浏览搜索结果时，如果发现某个资源与查询相关，就可以将该网页资源关联到语义 ，也即间接对网页资源进行语义注释。在对等网上其他节点可以共享每个节点的语 源注释。文献 1 5 】通过分离对等基础层和语义支持层，提出了一个实现语义覆盖对 息共享系统的两层框架，并从知识建立和知识检索角度分析了框架实现技术，探讨 查询所表达的语义层次处理用户的查询请求，实现语义的同义扩展、蕴涵扩展、外 展、并列扩展和相关扩展的过程。文献 1 6 1 在p 2 p 网络中构建一个基于r d f 的元数 间，并解决分布式查询和概念间的合并、映射、进化及资源的注解等问题。文献 1 7 】 了一种基于语义相似、本体匹配的对等网信息检索方法，通过定义语义节点，在节 通过计算语义相似度，在网络中进行语义匹配来部分替换传统的字符串相似度计 有效地提高信息检索效率。 i 目标 本文是从结构化p 2 p 网络出发，对现有的基本网络模型的工作原理、结构和行为特 方面展开深入研究，并从中得到的启发，对现有的网络模型特性展开探讨，最终提 出一种拥有较高查询效率与准确率的基于语义检索的多层结构的结构化p 2 p 网络模型。 1 4 本文的内容组织结构 第一章绪论。本章主要对课题背景做了一个简要的介绍，概括了国内外当前的研 究现状以及存在的问题，并说明了本文的动机和目标。 第二章p 2 p 及p 2 p 搜索技术简介。本章对p 2 p 系统进行了概述，包括这种系统的 历史起源、应用现状、结构、工作原理、系统的行为特性等，同时也对p 2 p 搜索技术等 相关知识进行了介绍。 第三章语义检索与文本聚类算法。本章内容首先对语义检索的相关概念以及原理 进行了介绍，之后介绍了向量空间模型和文本聚类的相关知识、原理等，并对文本聚类 算法进行了介绍，在此基础上，提出了改进的文本聚类算法z h s e m 算法。 第四章基于语义检索的网络模型。本章对c h o r d 模型进行了分析，在现在c h o r d 模型的基础上，并在基本不影响c h o r d 模型性能的前提下，对其结构进行修改与优化， 使得新的模型能够较好的支持基于语义的检索。并对改进过后的系统进行测试工作。 基于语义检索的维_ ；穹j f 艺p 2 p 网络模型研究 2 p 2 p 及p 2 p 搜索技术简介 2 1p 2 p 的技术背景 p 2 p 起源于最初的互联通信方式，如在建筑物内p c 通过局域网进行互联，不同的 建筑物间通过m o d e m 远程拨号连接。其中建立在t c p i p 协议之上的通信模式构成了今 天互联网的基础，所以从基础技术角度来看，p 2 p 也不是新技术，而只是新的应用技术 模式。 另外，即使从网络看，p 2 p 也不是什么新概念，早在许多年之前i n t e r n e t 刚刚诞生 时就已经有了，而且当时的i n t e m e t 就是一个p 2 p 结构的大网络。人们之间完全是以“点 对点 方式通讯的，根本不存在现在所谓的服务器与客户端，所有的互联网上的系统都 既具有服务器也具有客户机的功能，这可以看作为p 2 p 最原始的应用。当然，后来发展 的那些架构在t c p i p 之上的软件是采用了客户端j j 及务器的结构，也就是所谓的c s 结 构，浏览器与w c b 服务器，即b s 结构，以及邮件客户端与邮件服务器。但是，对于 服务器来说，它们之间仍然是对等互联的。 事实上，网络上现有的许多服务亦可以归入p 2 p 的行列。例如：即时消息通讯软件， 微软的m s n 0 s 】以及国内的q q 1 9 1 都是最流行的p 2 p 应用。它们允许用户互相沟通和交 换信息、交换文件。用户之间的信息交流不是直接的，需要有位于中心的服务器来协调。 但这些系统并没有诸如搜索这样的，对于大量信息共享特别重要的功能，这个特征的缺 乏可能也正好解释了为什么即时消息通讯软件出现了这么久，但却并没有能够产生如 n a p s t e r t 2 0 】这样的影响力。 2 2 p 2 p 网络的分类 图2 1p 2 p 系统的分类 f i g 2 1 c l a s s i f i c a t i o no fp 2 ps y s t e m s 4 西华大学硕士学位论文 p 2 p 网络的分类有多幂中形式，其中包括：集中式p 2 p 网络，非集中式p 2 p 网络，还 结构化p 2 p 网络、结构化p 2 p 网络( 也称作d h t 网络) 等，其中非结构化p 2 p 网 结构化p 2 p 网络更加引人关注，也是目前研究的重点，如图2 1 所示。结构化与非 化p 2 p 网络的主要区别，就在于结构化p 2 p 网络是按照某种规则进行组织和构建的， 中的节点的加入和离开需要严格遵守这种规则，而非结构化p 2 p 则不存在这样的限 1 非结构化p 2 p 网络 这类系统没有中心服务器，各个节点之间几乎扮演完全平等的角色。每个节点都会 一个节点列表，记录着同属于此网络的相邻节点的地址，需要说明的是，这类系统 有若干个初始连接节点，保存着一张最大的节点列表，每个节点上线的时候都会被 下来，这个最大列表的用处就在于，随时为网络其他普通节点提供可以访问的节点 ，g n u t e l l a l 2 1 1 和f r e e n c t 2 2 是这方面两个的应用。g n u t e l l a 由于良好的协议开放性得 十分广泛的使用，而严格的加密和传输加密则是f r e e n e t 追求的一个重要功能，其 复杂的加密机制使得很难用明文进行搜索，同时也降低了传输效率，因此用户比g n u t e l l a 相对较少。 非结构化对等网络系统采用完全分布式的拓扑结构，之所以称其为“非结构化”， 是和结构化对等网络相对的。非结构化对等网络中每个节点之间是比较松散的关系，节 点的加入和离开仅需遵循一些简单的规则。非结构化对等网络中每个节点保存各自共享 的文档，由于不再存在中央目录服务器，每个节点对本地保存的文档进行索引，并转发 或应答其他节点的搜索请求。目前，非常流行的p 2 p 软件g n u t e l l a 、f r e e n e t 等，均是非 结构化p 2 p 系统，它吸取了n a p s t e r 的失败教训，将p 2 p 的理念推进一步：它不存在中 央目录服务器，用户只要安装了该软件，立即变成一台能够提供完整目录和文件服务的 服务器，并会自动搜寻其它同类服务器，从而联成一台由无数p c 组成的网络超级服务 器。 在非结构化对等网络中，由于缺乏中央目录服务器且文档并不存储在特定的节点 上，所以资源查找最基本的方式是泛洪( f l o o d i n g ) 或类似泛洪的盲目搜索。如在g n u t e l l a 中( 如图2 2 ) ，一个节点要进行检索的话，它就向它的邻居节点广播消息( 泛洪) ， 如果其邻居节点满足要求则返回结果，如果不满足则将其消息向该节点的邻居转发，查 寻范围由t t l ( 生存时间，t i m et ol i v e ) 参数来控制。尽管这种方法是非完全集中式 的，有效地避免了单点失效问题，但由于它采用了广播消息加t t l 参数的控制方法， 其检索范围仅在发起节点为中心的某个特定半径范围有效，可扩展性受到很大限制。 基于语义检索的结构化p 2 p 踺终檀型研究 图2 2 基于洪泛的p 2 p 检索模型 f i g 2 2 p 2 ps e a r c hm o d e lb a s e df l o o d i n g 由于采用完全分布式的网络拓扑，非结构化对等网络避免了集中式对等网络中中央 目录服务器带来的系统瓶颈的问题。但由于非结构化对等网络中缺乏有效的搜索机制， 只能采用泛洪或类似泛洪的盲目搜索方式，导致在网络中产生过度的流量，同样影响了 系统的可扩展性。 ( 1 ) g n u t e l l a 、 g n u t e l l a 于2 0 0 0 年3 月在s l a s h d o t 网站正式发布。它的作者是j u s t i nf r a n k e l 和t o m p e p p e r ，这两位是n u l l s o f t 公司的创始人，著名的m p 3 播放软件w i n a m p 的创作者。 g n u t e l l a 在发布时就被称为“一种文件共享的工具，将比n a p s t e r 更强大”。不久之后 发布c m u t e l l a 的网站就不再提供服务了，n u l l s o f t 后来也没有在继续推出新版本的 g n u t e u a 软件。不过，当时已经有很多人下载了g n u t e u a 软件，并且有一批程序员致力 于继续开发这一工具软件。他们在技术和协议分析的基础上根据g n u t e l l a 协议开发了一 系列衍生系统。g n u t e l l a 作为一种纯粹p 2 p 架构的分布式文件共享系统，其中的节点只 知道与自己已经建立了连接的节点的存在，而不知道其它节点的存在，也就是说其它节 点是不可见的，除非这些节点对本节点的探测或者请求消息做出了应答。 节点发起文件搜索请求时提供了一个用于标志文件的搜索字符串和t i m e - t o 1 i v e 参 数，并把这个搜索请求发给与自己有链接的所有节点。收到搜索请求的节点在本地进行 查找，若找到请求文件则沿着搜索路径方向返回搜索成功的信息，把本节点的相关信息 6 西华大学硕士学位论文 如i p 地址、端口等发回。请求者收到这些信息后就可以与目的节点建立连接下载文件。 若在当前节点未找到所需文件则把请求进一步转发到与当前节点有链接的所有节点。消 息转发的次数受到t i m e t o 1 i v e 参数的限制。 新节点加入系统时至少要知道一个老节点的存在，通过发出t i m e t o 1 i v e 参数的探索 消息向老节点生命自己的存在。收到消息的老节点除了做出回应，把自身的i p 、端口、 共享文件数目等信息传回之外，还把消息转发给与自己有连接的其它节点，转发次数受 最初指定的t i m e t o 1 i v e 参数的限制。 ( 2 ) f r e e n e t f r e e n e t 起源于1 9 9 7 年，是由爱丁堡大学的i a nc l a r k e 发起的一个研究项目。该系 统是一个完全分布式的，支持匿名的文档存储和检索的p 2 p 应用系统。它允许在发布、 复制和检索文件的同时保护发布者和检索者的匿名性，其主要设计目标是： 保护文件的作者与读者的匿名性； 文件存储者的否认本领； 高效的信息路由和分布式的文档存储； 消除所有的单点控制和单点失效。 f r e e n e t 是已经实现的点对点技术并以不受场所限制的密钥著称。每个节点维护他们 自己在本地的数据存贮，提供网络对其进行读、写的能力，就像包含其他节点及密钥的 动态路由表。他有意让系统的许多用户都能建立节点，同时提供措施防止恶意外部节点 的攻击及提高整个网络存储的能力。f 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 最基本的模型为：对密钥的请求沿着节点通过一串代理请求向外发送，在这串代 理中的每个节点都按照口路由的模式，做出一个向何处节点发送下个请求的决定。依 靠请求密钥，路由不断变化。这是必须要做的，因为为了保护信息的隐蔽性，每个节点 仅拥有在代理链上的与他们相连的上一个或者下一个节点信息。 每个请求都受到h o p s t o i v e 的限制，与g n u t e l l a 中的t i m e t o 1 i v e ( t t l ) 类似，这 是一个在每个节点上都减i 的变量，专门用来防止形成无穷的代理链。每个请求还被设 计了一个“伪唯一随机标识符”，便于节点能拒绝他们曾经发出过的请求阻止死循环的 发生。如果它们发现有一个请求是他们曾经处理过的请求，他们立即将前一个节点发出 的信息转发到另外一个节点上。这个过程一直持续到满足这个请求或者超出它的 h o p s t o 1 i v e 地限制。成功或者失败的结果都返回到发出这个请求的接点上。f r e e n e t 很 重要的一个特点是：所有资料都是加密传输、分散存放，而且多次存放，具体一份资料 基于语义检索的结构化p 2 p 网络模型研究 的位置是无人知晓的，而且它们的口地址和端口号是不断变化着的。自由网中的文件 是通过二进制的索引密钥进行标识的，而索引密钥又是通过哈希运算得到的。f r e e n e t 使用1 6 0 位s h a - 1 作为进行运算的哈希函数。一共采用了四种不同类型的文件索引密 钥，它们的用途和构成方式都有所不同，这四种索引密钥分别是标识关键字索引密钥 ( k e y w o r d - s i g n e dk e y ，简称k s k ) 、标识子空间索引密钥( s u b s p a c e s i g n e dk e y ，简 称s s k ) 、内容哈希密钥( c o n t e n t h a s hk e y ，简称c h k ) 、地图空间索引密钥( m a p s p a c e k e y s ，简称m s k ) 。 2 2 2 结构化p 2 p 网络 这类系统没有中心服务器，各个节点之间扮演几乎完全平等相同的角色。结构化 p 2 p 模式是一种采用纯分布式的消息传递机制和根据关键字进行查找的定位服务，目前 的主流方法是采用分布式哈希表( d h t ) 技术，这也是目前扩展性最好的p 2 p 路由方式 之一，由于d h t 各节点并不需要维护整个网络的信息，只在节点中存储其邻近的后继 节点信息，因此较少的路由信息就可以有效地实现到达目标节点，同时又取消了洪泛算 法。该模型有效地减少了节点信息的发送数量，从而增强了p 2 p 网络的扩展性，同时， 出于冗余度以及延时的考虑，大部分d h t 总是在节点的虚拟标识与关键字最接近的节 点上复制备份冗余信息，这样也避免了单一节点失效的问题，这类网络的代表有 c h o r d 2 3 1 ，p a s t r y 2 4 1 ，t a p e s t r y 2 5 1 ，k a d e m l i a 2 6 j 等。 ( 1 )c h o r d j ， 7 丽。 ， - _ - - _ _ 一 ，_ _ f n 6 0 图2 4c h o r d 路由示例 f i g 2 4 c h o r d r o u t i n ge x a m p l e 为了提高路由的效率，c h o r d 实际采用了基于f i n g e r t a b l e 的路由方式。每个节点在 f i n g e rt a b l e 中保存多个后继节点的地址。标识符为k 的节点f i n g e rt a b l e 中第i 个表项指 向的是标识符大于或等于k + 2 1 - 1 ，的第一个节点，其中1 i m 。节点f i n g e rt a b l e 中的 第一个表项总是指向当前节点的直接后继节点。当c h o r d 达到稳定状态时，每个节点只 需在路由表中维护o ( 1 0 9 n ) 个其他节点的信息，其中n 为系统中节点的数目。对文档进 行路由时，经过的每个节点将文档标识符和f i n g e rt a b l e 中的各表项进行比较，并选择 f i n g e rt a b l e 中和文档标识符相对应的第一个前驱节点为下一跳节点。c h o r d 进行文档路 由的路径长度为o ( 1 0 9 n ) ，其中n 为系统中节点的数目。图2 5 是基于f i n g e rt a b l e 的c h o r d 路由示例。图中环形空间的标识符范围为0 ，1 2 7 ，标识符为3 2 的节点n 3 2 希望查找 9 基于语义检索的结构化p 2 p 网络模型研究 标识符为1 9 的文档，文档标识符绕过了环形空间的最后一个节点，存储在节点n 2 0 。 从图中可以看出，利用f i n g e rt a b l e 的c h o r d 查找过程类似于二分查找的过程，因此可以 取得较高的路由效率。 ( 2 ) p a s t r y p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，它是由p a s t r y 节 点组成的自组织的高结构化覆盖网络( o v e r l a yn e t w o r k ) 。每个节点都可以路由客户请 求并和应用程序( 可以是多个) 的本地实例进行交互。任何一台连接到i n t e m e t 的计算 机只要运行p a s t r y 节点软件就可以称为p a s t r y 节点，当然，它需要满足应用定义的安全 策略。p a s r t y 系统中的每个节点都被分配一个1 2 8 位的节点号，节点号用于在节点间中 标识节点的位置，节点号是在节点加入系统时随机分配的，分配策略是在点空间中均匀 分布，节点号可以通过计算节点公钥或者i p 地址的哈希函数值获得，由于采用了均匀 分布，因此节点标识相邻的节点处于不同的地理位置的几率很大。 ( 3 )k a d e m l i a k a d e m l i a 是美国纽约大学的p e t a r p m a y m o u n k o v 和d a v i dm a z i e r e s 在2 0 0 2 年发布 的一项研究结果( ( k a d e m l i a ：ap e e r t o p e e ri n f o r m a t i o ns y s t e mb a s e do nt h ex o rm e t r i c ) ) 。 简单的说，k a d e m l i a 是一种分布式哈希表( d h t ) 技术，不过和其他d h t 实现技术比 较，如c h o r d 、c a n 、p a s t r y 等，k a d e m l i a 通过独特的以异或算法( x o r ) 为距离度量 基础，建立了一种全新的d h t 拓扑结构，相比于其他算法，大大提高了路由查询速度。 在2 0 0 5 年5 月著名的b i t t o r r e n t l 2 7 1 在4 1 0 版实现基于k a d e m l i a 协议的d h t 技术后， 很快国内的b i t c o m e t i 冽和b i t s p i r i t 2 9 1 也实现了和b i t t o r r e n t 兼容的d h t 技术，实现 t r a c k e r l e s s 下载方式。另外，e m u l e ! 驯中也很早就实现了基于k a d e m l i a 类似的技术。 2 3 p 2 p 网络信息检索概述 2 3 1 p 2 p 网络信息检索的动机 随着i n t e r a c t 的发展，人们日渐依赖搜索的理念，去定位所需要的资源，但是这种 集中式的搜索引擎，远远无法涵盖互联网中所有的共享内容，而p 2 p 信息检索( p 2 p i n f o r m a t i o nr e t r i e v a l ) 却j 下好是这种集中式检索的一种良性互补。p 2 p 信息检索的动机 主要可以表现在以下四个方面【3 l j ： ( 1 ) 可以充分利用以大规模分布形式存在的信息。 在i n t e r a c t 中除了那些可以被搜索引擎检索到的静念页面外，还有分布在边缘网络 内的海量信息值得去采集和挖掘。这些分布存储在各个主机里面的信息具有潜在的巨大 价值，因为这些信息是经过用户过滤选择后保存下来的，是和用户密切相关的“精华 。 1 0 西华大学硕士学位论文 传统的集中式引擎无法胜任这种实时性强的海量信息检索。而在p 2 p 网络中，每个参与 网络的主机既是内容的消费者，又是内容的提供者。 ( 2 ) 可以弥补传统搜索引擎无力深度挖掘网站信息的弱点。 据报道，i n t e m e t 上共享的文档总量超过5 5 0 0 亿，而即使那些具有强大检索能力的 搜索引擎( 如g o o g l e 所能检索到最大文档总量为8 0 亿) 也只能检索其中很小的一部分。 其中大部分的信息是存储在网站的数据库中以动态网页的形式来提供的，这些信息无法 用传统搜索引擎通过对静态网页上的链接进行采集和获取。而p 2 p 检索提供了一条可行 的途径：各个信息提供者作为一个节点加入p 2 p 共享网络，各个节点各自对自己本机上 存储的信息制作索引，所有的信息提供者一起构成一个庞大的分布式数据库以供检索。 ( 3 ) 挖掘移动终端的信息。 随着3 g 的到来，智能手机、智能终端的功能不断加强。这些移动终端存储的数据 具有分布面广、地域性强、存储信息和用户终端密切相关的特点，而它们可以看成是 p 2 p 共享网络的一个自然延伸。充分挖掘这些分布的信息，具有相当大的实用价值和研 究意义。p 2 p i r 十分适合于解决这些实际问题。 ( 4 ) 构建人性化的信息终端。 在p 2 p 网络中，分布于各个终端的数据非常直接而深刻地反映了用户的兴趣。在对 这些兴趣进行挖掘的基础上，可以很方便地对产品和业务进行个性化推送，组织协作， 研究和开发更加富有人性化的信息终端。这无论对提升企业内部信息流通的质量还是对 改善公众网络信息服务都有十分重大的意义。 2 3 2 传统的p 2 p 网络信息检索 如前所述，p 2 p 网络按拓扑结构可以分为结构化p 2 p 网络和非结构化p 2 p 网络，针 对这些不同的结构，按搜索机制不同主要分为三类： ( 1 ) 集中索引式信息检索 传统信息检索与w e b 信息检索都是基于集中式的，p 2 p 中集中式信息检索的最基本 解决方法是就像n a p s t e r 一样构建一个中央服务器，在中央服务器中存储所有注册过的 文件，所有检索工作都由中央服务器完成，然后各节点间的通讯采用点对点方式直接进 行。显然，中央服务器具有单点失效、可扩展性不佳等缺陷。集中目录式信息检索主要 用于集中式的p 2 p 系统，代表系统有早期的n a p s t e r 。其算法思想是：系统中每一个节 点都将自身能够提供共享的内容注册到一个或几个集中式的目录服务器中，并由服务器 对这些目录信息进行索引。查找资源时，首先向目录服务器发出搜索请求，通过服务器 定位，然后两个节点之间再直接通信。显然，即便在一个很大的网络中，通过中心服务 器来寻找有用的信息也是非常方便快捷的。但是设置一个中心服务器的成本相当高，并 基于语义检索的结构化p 2 p 网络模型研究 且还可能涉及版权、隐私等相差问题，同时也比较脆弱。因此，在p 2 p 网络中设置中心 服务器并非是一个理想的选择。 ( 2 ) 泛洪式信息检索 为了解决集中式信息检索中存在的问题，人们提出了基于泛洪的信息检索方式，实 际系统如g n u t e l l a 、f r e e n e t 等。在这些系统中，节点索引只在本节点中存在，其它节点 不存储本节点的内容索引。因此为了找到与用户需求相关的节点，基本方法就是泛洪。 如在g n u t e l l a 中，一个节点要进行检索的话，它就向它的邻居节点广播消息( 泛洪) ， 如果其邻居节点满足要求则返回结果，如果不满足则将其消息向该节点的邻居转发，查 寻范围由1 陀参数来控制。尽管这种方法是非完全集中式的，有效地避免了单点失效 问题，但由于它采用了广播消息加订l 参数的控制方法，其检索范围仅在发起节点为 中心的某个特定半径范围有效，可扩展性受到很大限制。另外由于采用泛洪方式，易造 成广播风暴引起节点过载，人们提出一些改进办法，如y a n g l 2 0 】等提出的迭代深入、直 接广度优先搜索及邻居节点内容的本地索引等机制，利用超级节点机制和随机泛洪来减 少广播流量及采用分布数据复制策略来提高网络性能等，但都不能从根本上解决可扩展 性问题。 ( 3 ) d h t 式信息检索 为了有效解决泛洪信息检索中存在的可扩展性问题，人们提出了分布式哈希表思 想。分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 搜索的算法思想是【3 2 l ：网络中的所 有文档和节点都被分配了唯一的标识符，文档的唯一标识符是通过对文档内容的关键字 进行哈希变换得到的，节点的唯一标识符是通过对节点的地址进行相同的哈希变换得到 的，文档存储在具有和文档标识符最接近的节点标识符的节点里，检索时节点将查询请 求转发给与预搜索的文档标识符最为接近的邻居节点，根据文件的索引在d h t 中搜索