基于非结构化p2p网络的资源搜索算法研究

《基于非结构化p2p网络的资源搜索算法研究》由会员分享，可在线阅读，更多相关《基于非结构化p2p网络的资源搜索算法研究（62页珍藏版）》请在金锄头文库上搜索。

1、南京邮电大学 硕士学位论文 基于非结构化P2P网络的资源搜索算法研究 姓名：张莉 申请学位级别：硕士 专业：计算机应用技术 指导教师：宗平 20090308 南京邮r 乜大学硕+ L 研究生学位论殳摘要 摘要 近年来，随着对等网络( P e e r - t o P e e r ，P 2 P ) 规模、信息量和用户量的飞速增长， P 2 P 技术成为人们研究与关注的焦点。在P 2 P 网络中，节点既是客户机，享用其他节点 提供的服务，同时又充当服务器，为其他节点提供服务。P 2 P 网络中的节点都是对等的， 节点之间进行直接的连接与共享。 然而，所有P 2 P 系统都面临一个难题，即如何在缺少集

2、中控制的、大规模的、分布 式的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 网络的搜索算法的改进，提出了一种改进的资源搜索算法I S A F 。该算法通过兴趣相 似的分析引入节点相似度，将节点关系分组

3、为邻居节点、朋友节点和捷径节点，使节点 搜索有不同优先级：同时引入蚂蚁算法，将节点相似度映射为信息素，采用正反馈的方 式来用搜索结果修正节点相似度。仿真实验的结果表明，该算法有效地约束了搜索范围， 提高了P 2 P 资源搜索的搜索成功率、减少了搜索时间和网络流量。 关键字：P 2 P ，非结构化，兴趣相似，蚂蚁算法，资源搜索 南京邮r 乜大学硕L 研宄牛学位论义 A b s t r a c t A b s t r a c t P e e r - t o P e e r ( P 2 P ) t e c h n o l o g yh a sr e c e n t l yr e c e i v e

4、dal o to fa t t e n t i o n sw i t ht h ei n c r e a s e o ft h en e t w o r ks c a l ea n dt h ea m o u n to fu s e r s I nP 2 Pn e t w o r k ，t h ep e e ri sn o to n l yac l i e n t ，b u t a l s oas e r v i c ep r o v i d e r T h e yc a ng e tr e s o u r c e sf r o mr e m o t ep e e r s ，m e a n w

5、 h i l e ，t h e ya r ea l s o a b l et op r o v i d el o c a lr e s o u r c e sf o ro t h e rp e e r s T h ep e e r sa r ee q u a l ，d i r e c t l yc o r m e c t e da n d s h a r i n gr e s o u r c e H o w e v e r ，i ti sa ni m p o r t a n tp r o b l e mi na l lP 2 Ps y s t e mt h a th o wt of i n d

6、a n dl o c a t et h e r e q u i r e dr e s o u r c e N o w a d a y ，e x i s t i n gP 2 Ps y s t e m sh a v ev a r i o u sd e f i c i e n c i e si nt h i sa r e a F o r e x a m p l e ，s t r u c t u r e dP 2 Pn e t w o r kh a se f f i c i e n ts e a r c h ，b u ta r i s ef r o mt h i ss t r i c ts t r

7、u c t u r e ，i ti s h a r dt Ob e c o m ep o p u l a ri nI n t e r a c ta n dh a s p o o rs u p p o r ti nc o m p l e xq u e r i e s ；u n s t r u c t u r e dP 2 P s y s t e mi ss i m p l eb o t hi ns t r u c t u r ea n di m p l e m e n t a t i o n ，b u ti n e f f i c i e n ts e a r c h i n gp e r f

8、o r m a n c e b e c a u s eo fs e a r c h i n gb l i n d n e s s B yr e s e a r c h i n gP 2 Pn e t w o r k St o p o l o g ya n ds e a r c h i n ga l g o r i t h e m ，t h i st h e s i sf o c u s e so n h o wt oi m p r o v es e a r c he f f i c i e n c yo fu n s t r u c t u r e dP 2 Ps y s t e m ，a n

9、 dp r o p o s e sa ni m p r o v e d r e s o u r c es e a r c ha p p r o a c h I S A Fa l g o r i t h m F i r s t l y ，t h et h e s i si n t r o d u c e st h en o d es i m i l a r i t y b a s e do na n a l y z i n gt h en o d ei n t e r e s t ，a n dt h es e a r c h i n ga l g o t i t h e mg r o u pt

10、h ep e e r st od i f f e r e n t s e a r c hp r i o r i t y ，s u c ha sn e i g h b o rn o d e s ，f r i e n dn o d e sa n ds h o r t c u tn o d e s S e c o n d l y ，t h i st h e s i s i n t r o d u c e st h ea n ta l g o r i t h mt om a pt h en o d es i m i l a r i t yt ot h ep h e r o m o n e ，a n d

11、a m e n d m e n t st h e n o d es i m i l a r i t yb yt h es e a r c h i n gr e s u l t st h r o u g hp o s i t i v ef e e d b a c k S i m u l a t i o nr e s u l t ss h o w t h a tt h ea l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h er e s o u r c es e a r c hs u c c e s sr a t e ，r e d

12、u c et h es e a r c h t i m ea n dn e t w o r kt r a f f i c ，a n dm a k et h es c o p eo fs e a r c hs m a l l e r K e y w o r d s ：P 2 P , u n s t r u c t u r e d ，i n t e r e s ts i m i l a r i t y ，a n ta l g o r i t h m ，r e s o u r c e ss e a r c h 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作

13、及取得 的研究成果。尽我所知，除了文中特! l I J ) j I 以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：塑当日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊

14、登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名： 拯蜀 导师签名：日期： 翊兰：! 南京邮电大学硕上研宄生学位论T 迁 第章引言 1 1 研究背景 第一章引言 计算机对等互连网( P e e r - t o p e e r ，P 2 P ) 技术是目前流行于计算机网络技术研究领域 的一个热点。互连网在早期阶段，由于当时计算机的处理能力、存储空间以及网络带宽 等的限制，互连网并没有采用P 2 P 模式，而是采用的客户N 务器( c S ) 模式。现在，由 于计算机和网络的性能发生了飞跃性的提高，同时由于C S 模式自身的不足，学术界和 企业界开

15、始关注P 2 P 技术。 P 2 P 网络具有集中式服务网络所缺乏的优势：可扩展性强、容错性好、成本低、充 分利用分布资源。在P 2 P 网络中，不存在中心服务器，所有的节点既是客户机，享用其 他节点提供的服务，同时又充当服务器，为其他节点提供服务【I 】。P 2 P 中的节点都是对 等的，节点之间进行直接的连接与共享。P 2 P 模式能让互连网上的闲散资源得到充分的 利用，网络的容错性能也大大提高。P 2 P 成功的典范是N a p s t e r 和G n u t e l l a 。在P 2 P 网络 中，信息的传播更加迅速，同时也优化了网络的带宽利用情况。目前，P 2 P 技术己被应 用

16、于文件共享、分布式计算、协同工作、即时通讯等许多领域，对计算机技术的应用产 生了重要影响l 引。 由于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 网络的搜索技术具有重要 的理论意义和实用价值。从理论意义上讲，P 2 P 网络L 资源的存在形式对搜索技术提出 了新的要求。P 2 P 网络上的资源内容丰富多样，其分布具有极大的分散性。同时由于节 点的自由加入或退出，P 2 P 网络的资源还处于不断的动态变化之中。因此P 2 P 的搜索技 术和现有的搜索技术有很大的不同。从实用价值上讲，在P 2 P 应用短短几年的发展时间 里，它成为了占用I n t e r n e t 流量的