（计算机应用技术专业论文）基于广义蚁群算法的p2p网络搜索技术研究.pdf

南京i l i l 5 i u 人学硕i ：研究生学位论义摘要 摘要 在过去的几年中，p 2 p 网络( p e e r - t o p e e r n e t w o r k s ) 发展迅速，应用范围也越_ 束越广泛。 p 2 p 在商业上的应用主要有文件共享、边界服务、分布式计算，其中文件共享是目前最重 要的一个应用。如何实现资源的定位是文件共享的关键问题。以g n u t e l l a 为代表的无结构 p 2 p 系统采用泛洪机制搜索资源，这种机制的最大问题是导致冗余消息的产生，节点将查 询消息向其所有邻居节点转发，从而造成查询消息被迅速复制，网络负载过重，搜索效率 降低。 蚁群算法是一种新型的启发式算法，具有自适应性、鲁棒性及并行性等许多特点，广 泛适用于各种静态和动态的组合优化问题中，具有潜在的应用前景，但是蚁群算法也存在 不少缺陷，本文采用种新的蚁群改进算法广义蚁群算法作为理论基础。广义蚁群算 法与传统蚁群算法相比，不再采用各种参数，而是用函数表示信息素更新和蚂蚁转移策略。 使得广义蚁群算法在实际应用中更为灵活。 本文的目的是提出一种基于广义蚁群算法的p 2 p 网络搜索算法，保证搜索质量的同时 减少网络中的消息量。此算法在信息素更新策略中采用全局更新函数和挥发概率函数，在 蚂蚁转移策略中同样采用函数形式，减少参数的使用，由此减少由参数不确定带来的算法 性能不稳定问题。另外根据蚂蚁觅食行为的特性，通过蚂蚁释放信息素的正反馈机制和查 询关键字之间的匹配程度共同来指导搜索前进的方向，从而利用历史搜索信息，尽可能的 提高搜索效率，减少网络中的信息量。通过仿真实验验证了采用新的信息素更新策略和转 移策略后的广义蚁群算法的收敛性能，表明基于广义蚁群算法的p 2 p 搜索算法能有效提高 搜索效率，减少网络中的消息量。 关键字：无结构p 2 p 网络，资源搜索，广义蚁群算法，信息素更新 南京邮f u 人学顾+ i j 研究生学位论义 a b s t r a c t a b s t r a c t p 2 p ( p e e r - t o p e e r ) n e t w o r k s h a v e b e e nd e v e l o p i n gr a p i d l ya n di t s a p p l i c a t i o n s a r e b e c o m i n gm o r ea n dm o r ew i d e l yi nr e c e n ty e a r s p 2 pa p p l i c a t i o nf i e l d sa r em a i n l ya sf o l l o w s ： f i l es h a r i n g ，b o r d e rs e r v i c e sa n dd i s t r i b u t e dc o m p u t i n ga n ds oo n ，b u tf i l es h a r i n gi so n eo ft h e m o s ti m p o r t a n ta p p l i c a t i o n h o wt ol o c a t ed e s i r e df i l e si sv i t a li s s u e si nt h ef i l es h a r i n g g n u t e l l a i sap r o t o c o lo fu n s t r u c t u r e dp 2 ps y s t e m ，w h i c hu s e saf l o o d i n gm e c h a n i s mt os e a r c hr e s o u r c e s t h em o s ti m p o r t a n tp r o b l e mo ft h ef l o o dp r o t o c o li st h a tc a u s er e d u n d a n tm e s s a g e s t h ep e e ri n n e t w o r ks e n d st h eq u e r ym e s s a g et oa l li t sn e i g h b o rn o d e st or e s u l ti nt h eo v e rb u r d e no ft h e n e t w o r ka n dt h el o ws e a r c he f f i c i e n c y a n tc o l o n yo p t i m i z a t i o na l g o r i t h mi san e wh e u r i s t i ca l g o r i t h m ，w h i c hh a sm a n y a t t r a c t i v ec h a r a c t e r i s t i c si n c l u d i n ga d a p t a t i o n ，r o b u s t n e s sa n dp a r a l l e l i s m ，a n dh a v eb e e na p p l i e d t os e v e r a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，s oi th a sp o t e n t i a la p p l i c a t i o np r o s p e c t s h o w e v e r ，t h e r e s af e wo fd e f e c t si na n tc o l o n ya l g o r i t h m ，g e n e r a l i z e da n tc o l o n y o p t i m i z a t i o n ( g a c o ) i sc h o s e na sab a s i ct h e o r yi nt h ea r t i c l e ，w h i c hi san e wi m p r o v e da n t c o l o n ya l g o r i t h m c o m p a r e dw i t ht h et r a d i t i o n a la n tc o l o n ya l g o r i t h m ，i tn ol o n g e ru s e sa l lk i n d s o fp a r a m e t e r s ，a n da d o p t sf u n c t i o n st or e p r e s e n ta n tp h e r o m o n eu p d a t ea n dt r a n s f e rs t r a t e g y ， w h i c hm a k e sg a c om o r ef l e x i b l ei np r a c t i c a la p p l i c a t i o n r e s e a r c ho ft h i st h e s i sa i m sa tp r o p o s i n gan e wr e s o u r c es e a r c h i n ga l g o r i t h mb a s e do n g a c oi nu n s t r u c t u r e dp 2 pn e t w o r k ，i no r d e rt oi m p r o v es e a r c he f f i c i e n c y , a n dr e d u c et h e a m o u n to fi n f o r m a t i o nn e t w o r k s t h i sa l g o r i t h mu s e sg l o b a li n c r e a s i n gf u n c t i o na n de v a p o r a t i o n r a t ef u n c t i o ni nt h ep h e r o m o n eu p d a t es t r a t e g y , a n da l s ou s e st h ef u n c t i o ni nt h et r a n s f e rs t r a t e g y , w h i c hr e d u c e st h ei n s t a b i l i t yp r o b l e mb e c a u s eo fr e d u c i n gt h ea m o u n t so fp a r a m e t e r st h a ti s u n c e r t a i n t y a d d i t i o n a l l y , a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fa n tf e e d i n gb e h a v i o r t h ed i r e c t i o no f s e a r c h i n gf o r w a r d i sd i r e c t e db ya n t sr e l e a s ep h e r o m o n e sp o s i t i v ef e e d b a c km e c h a n i s m sa n dt h e m a t c hb e t w e e nt h eq u e r yk e y w o r d st ou t i l i z et h eh i s t o r i c a ls e a r c hi n f o r m a t i o na sp o s s i b l et o i m p r o v et h es e a r c he f f i c i e n c ya n dr e d u c et h ea m o u n to fi n f o r m a t i o n i nt h en e t w o r k t h e s i m u l a t i o ne x p e r i m e n t st e s ta n dv e r i f yt h ep e r f o r m a n c eo ft h ec o n v e r g e n c ep e r f o r m a n c eo f g a c oa l g o r i t h mu s e di nt h en e wp h e r o m o n eu p d a t ea n dt h et r a n s f e rs t r a t e g y , w h i c hs h o w st h a t t h es e a r c h i n ga l g o r i t h mi nu n s t r u c t u r e dp 2 pn e t w o r kb a s e do ng a c oc a ne f f e c t i v e l yi m p r o v e l l 南京邮l u 人学顺1 ：t o l ：j e , 生学位论义 a b s t r a c t t h es e a r c he f f i c i e n c ya n dr e d u c et h ea m o u n to fn e t w o r km e s s a g e s k e y w o r d s ：u n s t r u c t u r e dp 2 pn e t w o r k ，r e s o u r c e ss e a r c h ，g a c o ，p h e r o m o n eu p d a t es t r a t e g y 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 研究生签名：皇牌日期：j 型浏 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研 究生部办理。 研究生签名：一壶蛳导师签名：避一日期：q 拿童f 签一一 南京邮 u 人学顺f ：研究生学位论义第一章绪论 1 1 研究背景 第一章绪论 近年来，随着互联网应用的飞速发展，互联网上的信息每天都在快速增长，如何有效 的管理和利用庞大的信息资源成为一个亟待解决的问题。 目前，互联网主要应用客户端服务器( c s ：c l i e n t s e r v e r ) 模式。这种网络模式以服务 器为中心，服务器向互联网上的各种终端提供服务和资源，控制着互联网的主要信息流。 这种模式在过去很长的一段时间里很好的解决了互联网的有效资源共享问题。但是，随着 互联网用户数量的激增，客户端越来越多，这种统一集中的模式使得服务器负载越来越重， 服务器成为了整个网络的瓶颈。而且，从经济层面上将，一个可靠的服务器无论从硬件还 是软件的角度考虑都是相当昂贵的，这也增加了企事业单位在互联网上部署资源的成本。 另外，c s 模式的覆盖面狭窄，即使使用强大的搜索引擎，也难以到达网络的边缘，因此 这种模式难以充分利用互联网众多的客户端资源。 为消除服务器为中心的网络瓶颈，尽可能利用网络边缘空闲的资源，对等( v 2 p ： p e e r - t o p e e r ) 网络【1 】【2 】应运而生。p 2 p 系统打破了c s 模式的局限，在网络中每个节点的地 位平等，每个节点既充当客户，共享其他节点提供的服务，又充当服务器，为其他节点提 供服务和内容。p 2 p 网络的服务能力是由网络中的节点所提供的共享资源来决定的，p 2 p 网络中的节点越多，节点提供的共享资源越大，则p 2 p 网络的服务能力也越强，而网络的 中节点所能得到的共享资源也越多。 p 2 p 网络通过将分布在i n t e r n e t 边缘的众多节点联系起来，集合它们的计算能力以及存 储空间等资源，以极低的代价形成了巨大的服务能力。也正因为如此，p 2 p 网络得到了快 速地增长。 随着p 2 p 网络规模的不断壮大，网络蕴含的资源，如计算资源、信息资源等也越来越 丰富，这导致资源在互联网中存在着大量的复制和冗余，带宽利用率不高。如何组织、定 位和传输这些资源从而合理有效地利用它们为人们提供信息资源服务成为人们所关注的 焦点问题。同时，网络规模的扩大和节点的多样性将使得p 2 p 网络的性质也变得更复杂， 这也要求有更有效的资源搜索方法。相对于集中式搜索，p 2 p 搜索技术能够更加充分的挖 掘网络边缘资源，而且p 2 p 搜索技术不需要专门的高性能服务器，也不会有单点故障等问 题。这些因素使得p 2 p 搜索技术的研究成了p 2 p 研究中的个热门领域。 1 南京邮电大学硕士研究生学位论文第章绪论 1 2 研究现状 p 2 p 网络技术是现代网络技术和分布式计算技术相结合的产物。在p 2 p 网络中系统成 员之间的地位是平等的，每个成员同时扮演服务器与客户端的角色，系统应用的用户能够 意识到彼此的存在，并构成一个虚拟或实际的群体。 在p 2 p 系统中资源分散在各个节点上，节点频繁的加入或退出，使p 2 p 系统处于不断 的变化之中。p 2 p 系统的规模一般都很大，而且会不断扩展。由于p 2 p 系统的可扩展性和 节点的不确定性，设计一个好的资源搜索机制比较困难。在p 2 p 搜索技术发展历程中，出 现了以下几种具有代表性的技术： 具有集中式的中央服务器的搜索机制( n a p s t 一习) ，采用中央索引的方法实现资源的搜 索。在集中式的中央服务器上存放对等节点的地址信息、元数据和文件的关键词信息。一 个节点想要搜索资源，将带有所要搜索资源标识的搜索请求发送到中央服务器，中央服务 器检索存储在本地的资源索引，告知资源请求者拥有该资源的节点的标识，然后资源请求 者直接去访问资源拥有者节点，下载所请求的文件或者使用其它资源。随着网络规模的增 大，中央服务器必然成为服务瓶颈，而且会造成单点失效，同时还存在扩展性问题。 采用洪泛查找机制的p 2 p 网络( g n u t e l l a 【4 1 、f r e e n e t 【5 1 ) 是一种完全分布式的网络，可以 把这种网络看成是一组对等节点之间的自组网络。这种网络又称为无结构的p 2 p 网络。当 一个节点需要搜索一个文件，它向所有邻居节点发送搜索请求，邻居节点又向它们的邻居 节点发送该请求，就这样向外扩张，拥有所请求文件的节点就可以响应这个请求这就是泛 洪机制。这种机制相对简单，各个节点将本节点满足搜索请求的结果返回给请求的源节点 即可。但这种模型因为采用广播机制，导致消息量过大，网络负担过重，使得性能较差的 节点很快就成为整个系统的瓶颈。相对于所产生的消息量，搜索效率并不高。针对泛洪机 制带来的诸多问题，目前出现了多种方法对其进行改进。主要包括：随机漫步法【6 ( r a n d o m w a l k s ) 、改进的b f s 7 i ( m o d i f i e db r e a d t hf i r s ts e a r c h ) 、迭代深入法【s i ( i t e r a t i v ed e e p e n i n g ) 、 智能b f s 9 ( i n t e l l i g e n tb r e a d t hf i r s ts e a r c h ) 、本地索引算法【9 】【1 0 l ( l o c a li n d i c e s ) 等等。 基于分布式哈希表的查找机制，如c h o r d n 】，c a n t l 2 】等。这种由分布式散列表( d h t ： d i s t r i b u t e dh a s ht a b l e ) 的方法来实现资源的定位的网络，称为结构化的p 2 p 网络。c h o r d 中每个关键字都保存在它的后继节点上，查找过程就是不断接近它的后继节点最终到达目 的节点或查找失败。c a n 基于虚拟的d 维笛卡尔坐标实现其数据组织和查找功能。以上两 种基于分布式哈希表的查找机制有很多相似之处，主要采取将共享资源的标识和节点分别 进行散列，来建立资源和节点之间的对应关系。基于d h t 的p 2 p 系统很好地解决了系统 2 宣塞! ! ! ! ! ! ! 叁堂堡：型塑皇堂垡堡兰笙二至堑堡 的可扩展性和节点的动态性问题。但在这类p 2 p 系统中，如果不知道要访问资源的标识， 将无法定位和访问该资源。针对以上搜索技术，先后出现了多种改进算法，从不同的角度 对搜索机制进行了改进，比如引进超节点的概念、采用逐步加深与有向宽度优先搜索相结 合、利用局部索引和路由索引等等相关方法，这些方法在不同程度上提高了系统效率。 本文将主要关注无结构p 2 p 网络中资源搜索算法的研究。 1 3 论文的工作和内容安排 1 3 1 本文主要工作 本文主要研究内容是把一种新型蚁群算法广义蚁群算、法【1 3 】与无结构p 2 p 网络搜索 方法相结合，依据广义蚁群算法的原理提出了一种基于广义蚁群算法的无结构p 2 p 网络搜 索算法。在算法中依据广义蚁群算法的理论，将全局更新函数、概率挥发函数用于信息素 更新策略，这两个函数都是以蚂蚁生存时间为变量，蚂蚁生存时间值可以近似的反映节点 之间的距离，采用函数后涉及的参数少，算法性能较为稳定；在转移策略中同样是采用关 于信息素浓度的递增函数，并结合查询关键字之间的匹配程度，共同引导蚂蚁选择下一步 前往的节点。在有热门资源出现的时候，网络中会出现大量的相似查询消息，这种利用历 史查询记录指导后继查询的功能，极大的提高了查询效率，减少了网络中的消息量，从而 也提高了网络资源的利用率。 1 3 2 论文内容安排 第一章：本章是绪论，主要阐述了论文的研究背景和研究现状，并对本文结构做出安 排。 第二章：本章论述了p 2 p 的概念、特点，对目前p 2 p 网络的结构分类进行了介绍，对 p 2 p 技术的应用领域进行了分析，着重对无结构p 2 p 网络的典型代表- g n u t e l l a 网络的 搜索机制进行了论述，最后对现有的各种典型的基于g n u t e l l a 网络的资源查找机制按照资 源查找方式不同，分类进行了论述和分析总结。 第三章：本章是本文的核心，在本章中首先介绍了一种新的蚁群改进算法广义蚁 群算法，并将广义蚁群算法的基本原理应用到无结构p 2 p 网络的资源搜索中，提出了种 基于广义蚁群算法的p 2 p 网络搜索算法。此算法在信息素更新策略中采用全局更新函数和 挥发概率函数，在蚂蚁转移策略中同样采用函数形式，减少了参数的使用，由此减少了参 气 堕塞! ! ! ! ! ! ! 盔堂塑! 型兰! 竺兰垡堡塞笙二童堑堡 数不确定性带来的算法性能不稳定问题。另外根据蚂蚁觅食行为的特性，通过蚂蚁释放信 息素的正反馈机制来指导搜索自订进的方向，从而尽可能的利用历史搜索信息，减少泛洪搜 索带来的冗余消息。当算法迭代几次后，在较短路径上信息素浓度明显增大，逐渐形成一 条最短路径 第四章：本章是对第三章所涉及的理论及提出的基于广义蚁群算法的p 2 p 网络搜索算 法做实验验证，主要包括两个实验，实验一是对采用全新信息素更新策略及蚂蚁选择策略 后的g a c o 算法进行收敛方面的验证。实验二是本文算法与随机漫步法在搜索方面的性能 比较。通过以上两个实验可以看出本文算法在提高搜索质量和减少网络信息量方面有较好 的性能。 第五章：工作总结和展望。本章对论文的内容进行了总结，并展望了今后需要进一步 完善和开展的工作。 4 南京邮l u 人学硕1 ：研究生学位论义第二章p 2 p 概述及j c 搜索技术 2 1p 2 p 概述 第二章p 2 p 概述及其搜索技术 p 2 p 被美国财富杂志称为改变因特网发展的四大新技术之【】，甚至被认为是 无线宽带互联网的未来技术。p 2 p 技术不仅为个人用户提供了前所未有的自由和便利， 同时也试图有效地整合互联网的潜在资源，将基于网页的互联网转变成动态存取、自由 交互的海量信息网络。本章将介绍p 2 p 的基础知识，并着重关注p 2 p 在资源搜索方面的 发展。 2 1 1p 2 p 基本概念 目前，在p 2 p 研究和应用领域并没有给p 2 p 个统一的定义。常见的几种定义如下： 定义一：p 2 p 是一种运行于个人计电脑上的应用程序，它通过互联网连接和其他用 户共享文件。p 2 p 通过连接彼此的计算机实现资源共享，而没有一个统一的服务器。 定义二：p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源， 包括处理能力、存储能力、网络连接和打印机等，这些共享资源需要由网络提供服务， 能被其它对等节点直接访问而无需经过中间实体。在此网络中的参与者既是资源( 服务和 内容) 提供者，又是资源获取者。 定义三：p 2 p 系统是由若干互联协作的计算机构成，且至少具有如下特征之一：网 络依存于边缘化( 非中央式服务器) 设备的主动协作，每个成员直接从其它成员而不是从服 务器的参与中受益；网络中成员同时扮演服务器与客户端的角色；网络中的用户能够意 识到彼此的存在，构成一个虚拟或实际的群体。 由以上的定义不难看出，在p 2 p 系统中，网络不存在中心节点( 或中央服务器) ，每一 个节点都同时担当着信息消费者、信息提供者和信息中介者这三重职责；每一个节点都 具有完全相同的地位，每台计算机的权利和义务都是对等的，没有e s 系统中的服务器 和客户机之分。p 2 p 系统与c s 系统的区别体现在图2 1 和图2 2 中。 p 2 p 的结构使互联网重新回到了早期互联网无中心的状态，一切权力连同切责任 都交还给用户，网络实现了真f 的平等。由于没有服务器，网络上每一台计算机( 特别是 用户端设备) 的计算能力都可以得到充分发挥，使人们避免了在中央服务器端的昂贵支出 ( 包括软件、硬件、通信以及人力投入等) ，从而使得系统具有更低的运营成本和近乎无限 5 南京邮f 乜大学硕二j ：研究生学位论文第二章p 2 p 概述及其搜索技术 的扩展能力。 2 1 2p 2 p 的特点 图2 1p 2 p 模式的网络结构 图2 2c s 模型的网络结构 ( 1 ) 非中心化 网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在结点之 间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。p 2 p 的非中心化基本 特点，带来了其在可扩展性、健壮性等方面的优势。 ( 2 ) 可扩展性 在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务 能力也在同步的扩充，始终能较容易地满足用户的需要。整个体系是全分布的，不存在 瓶颈。理论上其可扩展性几乎是无限的。 ( 3 ) 健壮性 6 塑塞些! ! 叁堂丝：! ：丛! ! 竺兰篁丝兰兰三至呈! 呈垫堕丝! ! 堡窒丝查 p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之间进行的， 部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分结点失效时能够 自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通常都是以自组织的方式建立起 来的，并允许结点自由地加入和离丌。p 2 p 网络还能够根据网络带宽、结点数、负载等 变化不断地做自适应式的调整。 ( 4 ) 高性价比 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的 计算和存储能力以及网络带宽等性能都在高速增长。采用p 2 p 架构可以有效的利用互联 网中散布的大量普通结点，将计算任务或存储资料分布到所有结点上。利用其中闲置的 计算能力或存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲 资源，可以用更低的成本提供更高的计算和存储能力。 ( 5 ) 隐私保护 在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个集中环节， 用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决i n t e m e t 隐私问题主要 采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实体之中。在传统的 一些匿名通信系统中，实现这一机制依赖于某些中继服务器节点。而在p 2 p 中，所有参 与者都可以提供中继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为 用户提供更好的隐私保护。 ( 6 ) 负载均衡 p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结构服务 器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整个网络 的负载均衡。 2 1 3p 2 p 的体系结构分类 按照服务器的集成度即网络中是否存在中央服务器的标准，p 2 p 技术存在三种结构 模式的体系结构，即集中目录式结构，典型代表是n a p s t e r ；完全分布式结构，其中又包 括以g n u t e l l a 为代表的完全分布式无结构化p 2 p 网络和以c a n 等为代表的完全分布式结 构化p 2 p 网络；混合式p 2 p 网络结构，典型代表有s k y p e 。 ( 1 ) 第一代p 2 p 集中目录式结构 集中目录式结构形式上有一个中心服务器来负责记录共享信息以及回答对这些信息 7 堕室! ! ! ! ! 皇奎兰堡主里! 塑竺兰垡笙茎蔓三兰丝呈丝堕丝基望室垫查 的查询。每一个对等实体对它将要共享的信息以及进行的通信负责，根据需要下载它所 需要的其他对等实体上的信息。这种形式具有中心化的特点，但是它不同于传统意义上 的c s 模式。传统意义上的c s 模式采用的是一种垄断的手段，所有的资料都存放在服 务器上，客户机只能被动地从服务器上读取信息，并且客户机之间不具有交互能力。其 典型结构如图2 3 所示。而集中目录式结构则是所有网上提供的资料都分别存放在提供该 资料的客户机上，服务器上只保留索引信息，此外服务器与对等实体以及对等实体之间 都具有交互能力。 集中目录式结构的优点是提高了网络的可管理性，使得对共享资源的查找和更新非 常方便；缺点是网络的稳定性差，。服务器失效则该服务器下的对等节点全部失效。 图2 3 集中目录式结构图 ( 2 ) 第二代p 2 p 完全分布式结构 完全分布式无结构p 2 p 网络结构没有集中的中央目录服务器，每个用户随机接入网 络，并与自己相邻的一组邻居节点通过端到端连接构成一个逻辑覆盖的网络。对等节点 之间的内容查询和内容共享都是直接通过相邻节点广播接力传递，同时每个节点还会记 录搜索轨迹，以防止搜索环路的产生。无结构p 2 p 网络结构解决了网络结构中心化问题， 扩展性和容错性较好。由于没有一个对等节点知道整个网络的结构，网络中的搜索以泛 洪方式进行，信息的泛滥消耗了大量带宽并很快造成网络拥塞甚至网络的不稳定，从而 导致整个网络的可用性较差，另外这类系统更容易受到垃圾信息，甚至是病毒的恶意攻 击。 结构化p 2 p 网络在查找信息时，采用基于d h t 的分布式发现和路由算法。这种算法 避免了类似n a p s t e r 的中心服务器，也不像g n u t e l l a 那样基于泛洪进行查找，而是通过分 布式散列函数将输入的关键字唯一的映射到某个节点上，然后通过一些特定路由算法和 该节点建立连接。d h t 类结构能够自适应节点的动态加入或退出，有着良好的可扩展性， 节点i d 分配的均匀性和自组织能力。但是d h t 的维护机制较为复杂，尤其是节点频繁 加入退出造成的网络波动会极大的增加d h t 的维护代价。 南京邮r 乜大学硕士研究生学位论文第二章p 2 p 概述及其搜索技术 图2 4 无结构p 2 p 网络结构图 ( 3 ) 第三代p 2 p 混合式结构 混合式网络结构综合了完全分布式p 2 p 网络去中心化和集中式p 2 p 快速查找的优势。 按节点能力不同( 计算能力、内存大小、连接带宽以及网络滞留时间等) 区分为普通节点 和搜索节点两类。搜索节点与其临近的若干普通节点之间构成一个自治的簇，簇内采用 基于集中目录式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间通过分布式p 2 p 的模 式将搜索节点连接起来。可以在各个搜索节点之间再次选取性能最优的节点，或者另外 引入一个新的性能最优的节点作为索引节点来保存整个网络中可以利用的搜索节点信 息，并且负责维护整个网络的结构。普通节点的文件搜索先在本地所属簇内进行，只有 查询结果不充分的时候，再通过搜索节点之间进行有限的泛洪。这样就极为有效地消除 了分布式p 2 p 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时，由于 每个簇中的搜索节点监控所有普通节点的行为，能确保一些恶意的攻击行为能在网络局 部得到控制，在一定程度上提高整个网络的安全性能。 2 1 4p 2 p 的应用 图2 5 混合式网络结构图 p 2 p 的应用【1 5 】【1 6 】【1 7 】主要包括以下几个方面： ( 1 ) 文件共享 包括共享文件下载、搜索、内容分发、网络存储和对等广播等。文件共享可以说是 目前p 2 p 最为广泛的应用，如n a p s t e r 就是共享音乐的一个平台，对等网络的用户可以通 9 南京邮电大学硕士矽f 冗生学位论文第二苹p 2 p 概述及其搜索技术 过n a p s t e r 共享自己主机上的音乐文件。传统的w e b 方式中，要实现文件交换需要w e b 服务器的大力参与，通过将文件上传到某个特定的网站，用户再到该网站搜索需要的文 件，然后下载。由于w e b 服务器处理能力是有限的，同一时间下载的人数过多，使得用 户要等待很长时间。自从n a p s t e r 产生之后，一切变得简单。即使用户对w e b 应用一无 所知，只要花几分钟下载n a p s t e r 就可以非常简单地完成同样的功能。因为n a p s t e r 会自 动的把自己设置成一个服务器和客户端软件，通过下载别人机器上的文件以及把本机上 的软件提供给别人下载来实现目的。此类软件除了n a p s t e r 以外，还有g n u t e l l a 、f r e e n e t 等，都是用来实现文件特别是m p 3 文件共享的。 ( 2 ) 即时通讯 即时通讯指的就是诸如o l c q 、i c q 、m s n 等可以方便用户在线聊天的软件，即时通 讯从某种意义上说将超过文件共享应用，成为p 2 p 的第一大应用。即时通讯领域，在国 内，o i c q 处于不可动摇的地位，在国外，美国在线、微软、y a h o o 之间直有比较激烈 的竞争。作为一种便捷的网络通讯技术，p 2 p 的即时通讯软件不仅可以随时知晓对方在 线与否，而且通讯双方的交流完全是点对点进行，不依赖服务器的性能和带宽。尽管目 前的即时通讯技术一般都带有中心服务器，但中心服务器仅是用来控制用户的认证信息 等基本信息，并且帮助完成节点之间的初始连接工作。即时通讯软件的种种优点使它已 经越来越深入人心，应用范围从单纯的网络聊天工具变成工作生活所不可缺的信息交流 平台。在互联网日益普及的今天，即时通信的用户规模也呈现出快速增长的态势。 ( 3 ) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台来共同完成某项任务，共享 信息资源等。协同工作是w e b 更具个性化的特征，使用户可以按自己的方式来和其他人 共享信息。企业机构的日益分散，员工和客户游离不定，人们的工作环境起了很大的变 化。当前的以服务器为中心的c s 集中式互联网结构不再适合这种环境的变化。p 2 p 技 术的出现，使协同工作成为可能。通过让绝大部分的节点和其它节点直接交互，p 2 p 大 大减弱了中间商的作用，使个人电脑再一次成为商务中心的内容的主要存储地。p 2 p 技 术使得人们在互联网上进行实时信息交互交流变得更方便和容易。互联网上任意两台p c 机都可建立实时的联系，建立了一个安全共享的虚拟空间，用户在此基础上进行各种各 样的活动。采用p 2 p 技术，可以去掉目前协同工作系统中的中央服务器，参与协同工作 的计算机直接建立连接。 ( 4 ) 对等计算 随着科学技术的飞速发展，以及人类对未来宇宙空间技术的探索，我们必须对大量 1 0 南京邮i 【1 人学坝i ：t o l 究生学位论义 第二章p 2 p 概述及j e 搜索技术 的数掘进行处理。应用网络上众多计算机来完成超级计算机功能，直是科学家梦寐以 求的事情。对等计算 婚1 是分布式计算的思想在广域网上的延伸，目的是将网络上的c p u 资源共享。采用p 2 p 技术的对等计算，f 是把网络中的众多计算机暂时不用的计算能力 连结起来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理的行业都可 从对等计算中获利，如天气预报、动画制作、基因组的研究等，有了对等计算之后，就 会大大减少对超级计算机的需求。 ( 5 ) 搜索引擎 传统的搜索引擎由于其特点，会产生很多冗余的资料。p 2 p 技术的另一个优势是开 发出强大的搜索工具，使用户深度搜索文档成为可能，为互联网的信息搜索提供了全新 的解决办法。运用p 2 p 技术进行深度文档搜索，无需通过w e b 服务器，可以不受信息文 档格式和计算机设备的种种限制，达到传统目录式搜索引擎( 只能搜索到2 0 一3 0 的 网络资源) 无可比拟的深度，理论上将包括网络上所有开放的信息资源。采用p 2 p 技术， 搜索范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台p c 上的资源。应用 实例有：i n f r a s e a r c h ，p o i n t e r a 等。 ( 6 ) 用于i n t e r n e t 的文件存储系统 存储技术一直是人们关注的一项技术。由于网络规模的扩大，人们开始将传统的局 域存储技术向基于i n t e r n e t 的文件存储系统发展。一些研究项目开始采用p 2 p 技术来组织 和存储文件，像o c e a n s t o r e 、f a r s i t e 等。这些项目的目标都是提供面向全球的文件存储服 务。 2 2g n u t e l l a 搜索技术 由于本文的主要工作是研究无结构p 2 p 网络中的资源搜索方法，在无结构p 2 p 网络 中搜索的基本思想是泛洪( f l o o d i n g ) 机制，这里我们先对泛洪机制的代表吨u t e l l a 搜 索技术做简要介绍。 2 2 1g n u t e l l a 网络的协议体系结构 g n u t e l l a 协议【1 9 】定义了对等点之间工作于t c p 协议之上的应用层通讯协议，包括在 对等点之间通讯描述符集( 服务原语集) 和相应的通信规则集。这里所介绍的是g n u t e l l a 协 议的0 4 版本，在这个版本中定义了对等机通过网络通讯的方式，它定义了包括通过对等 机进行数据通讯的描述符集合内部的对等机相互交互的规则集。g n u t e l l a 通信协议主要包 l l 堕室! ! ! ! ! ! ! 叁兰堡! 型! 壅竺兰篁笙苎 笙三主氅! 丝堕丝! ! 堡窒垫查 括四种类型的消息，分别是p i n g 、p o n g 、q u e r y 、q u e r y h i t 和p u s h ，相关内容如2 1 表所 示。 在表2 1 中p i n g 和p o n g 用于主机的动态发现；q u e r y 和q u e r y h i t 用于数据查询；p u s h 用于穿越防火墙的主机和文件探测。 一旦一个新的对等点成功地连接到g n u t e l l a 网络时，它就可以使用g n u t e l l a 协议描 述符与其它对等点进行通信。每一个g n u t e l l a 协议描述符在使用时，都必须加上一个消 息的基本格式。 表2 1g n u t e l l a 消息描述表 消息种类描述 用来动态的发现g n u t e l l a 网络中的主机。当一个主机收到一个p i n g 消 p i n g 息后，应该返回一条p o n g 消息作为回应消息。 p i n g 消息的回应消息。包括已经连接主机的地址以及该主机可以向网 p o n g 络提供的共享数据的数量信息。 分布式g n u t e l l a 网络的主要的查询机制。当一个主机收到一个q u e r y q u e r y 消息，它将根据消息中的信息搜索本地的数据列表，如果发现要查询 的数据，它需要返回一条回应消息。 q u e r y h i t是q u e r y 消息的回应消息。包括获取查询到的数据的足够信息。 p u s h 一种允许防火墙内的主机也能够共享自己文件的数据机制。 g n u t e l l a 协议中的消息主要由两部分组成，即消息头和数据。消息头的格式如表2 2 所示。 表2 2g n u t e l l a 消息头格式 消息i d i 消息描述符 l t t l h o p s负载长度 其描述如表2 3 所示。 在g n u t e l l a 中定义了五种消息，分别是p i n g 、p o n g 、q u e r y 、q u e r y h i t 以及p u s h ， g n u t e l l a 依赖这五种消息完成伙伴关系的建立，内容的查找以及文件传输连接的建立。下 面给出这五种消息的负载格式以及功能描述。 p i n g ：用于获取和维护邻居节点，p i n g 消息没有负载。 p o n g - 回应p i n g 消息，格式如表2 4 所示。 表2 4p o n g 消息格式 端口i p 地址 共享文件数 i共享千字节数 南京邮f 【5 人学颂j ：研究生学位论文第二市p 2 p 概述及1 c 搜索技术 表2 3g n u t e l | a 消息头描述 消息头字段描述 一个1 6 位的字符串，用来表明消息的唯一性，当节点收到具有 消息i d相同消息i d 的q u e r y 消息或p i n g 消息时，节点可以只做一次处 理。 用来表示消息的类型。 0 x 0 0 = p i n g 0 x 0 1 = p o n g 消息描述符 0 x 4 0 = p u s h 0 x 8 0 = q u e r y 0 x 8 1 = q u e r y h i t 描述消息在g n u t e l l a 网络中向前传递的次数。每个客户端在将包 t t l 向前传递前t t l 将减1 。当m 等于0 ，消息将不再被向前传递 描述消息在g n u t e l l a 网络中向前传递的次数。每个客户端在将包 h o p s 向前传递前h o p s 将加1 。满足关系式t t l ( o ) = t t l ( i ) + h o p s ( i ) 负载长度表示紧接着头部后面的部分的长度。 q u e r y ：引起节点检索动作，格式如表2 5 所示。 表2 5q u e r y 消息格式 q u e r y h i t ：当查询到匹配的内容时，回应q u e r y 消息，带有查询结果。 表2 6q u e r y h i t 消息格式 p u s h ：指明内容下载信息，格式如表2 7 所示。 表2 7p u s h 消息格式 2 2 2g n u t e l l a 网络工作原理 在g n u t e l l a 网络中搜索采用的是泛洪方法，简单的描述就是一个节点向所有的邻居 节点广播查询消息，邻居节点再向自己的邻居节点广播，这个过程不断的进行下去。 g n u t e l l a 的工作原理f 2 0 】 2 1 】如图2 5 所示，当某一主机在需要查询资源时，先根据查询 1 3 童室! ! ! ! ! 里盔兰堡三! 三里! 窒圭兰篁堡茎笙三至呈翌堡垄墨基望窒垫查