（计算机科学与技术专业论文）p2p网络中基于蚁群算法的资源搜索研究与设计.pdf

，j rrj|liiili 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密口。 学位论文作者签名： 山年6 月荔日 厂蝴l 指导教师签名： 加研年厂月拍 ，司颤 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均己 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 阉极 日期：功叼年6 月 效解决网络结构中心化的 但同时由于资源的完全分 布性和网络的动态自组性，也使其资源搜索技术成为新的应用瓶颈。目前应用在 p 2 p 网络中的搜索算法多基于洪泛广播，而占用过多网络带宽、搜索效率低是洪 泛广播带来的普遍问题，也是各种改进的智能搜索算法主要关注点。 蚁群算法己在路由优化方面得到了很好的应用，本文在此基础上，将其应用 到p 2 p 网络资源搜索中，提出了一种基于蚁群算法的非结构化p 2 p 网络资源搜 索算法。该算法通过合理的搜索路径和搜索节点的信息素定义，保证搜索算法的 搜索效率；针对节点的动态性可能造成的己获取的路径失效而导致的搜索失败的 问题，算法给出了一种路径优化选择方法，可有效避免对失效路径的使用。同时， 算法充分利用了p 2 p 网络所具有的幂律特性和搜索局部性原理，即一方面，虽然 理论而言p 2 p 网络节点之间的关系是对等的，但事实上p 2 p 网络仍具有明显的 幂律特性，即网络中只有少数节点掌握着较多的受欢迎资源，而大部分节点只含 有极少能被访问的资源或者根本不包含资源，成为所谓的低效节点；另一方面， p 2 p 网络资源搜索行为具有某种相似性，或者说遵循局部性原理，即在某一搜索 时段，会有大量用户对某种特定资源的搜索兴趣较高，相应的资源成为所谓的搜 索热点。 算法的具体设计，首先是将网络中的节点进行分类，将经常提供资源的节点 称为有效节点，而那些很少提供或者提供恶意资源的节点称为低效节点。相对应 地，将节点的信息素定义为节点上资源访问的成功率，并以此作为资源搜索过程 中节点的选择依据，避免对低效节点的访问；同时以节点间的通信次数为基数定 义路径信息素，以此衡量路径的稳定性，避免对不稳定路径和节点的访问。此外， 根据p 2 p 网络所具有的幂律特性和搜索局部性原理，提出了资源主动声明机制， 对近期经常被访问的资源进行主动声明，以实现对资源信息的直接定位，进一步 提高搜索效率。 为验证论文所提出的搜索算法的有效性，论文进行了基于g r i d s i m 的算法仿 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 真实验。仿真结果表明，与常用的洪泛算法和c h o r d 算法相比，论文所提出的搜 索算法在查询次数、查询命中率等方面都有明显优势。 关键词：p 2 p ；蚁群算法；幂律特性：信息素；资源搜索 江苏大学硕士学位论文 a b s r a c t c e n t r a ld i r e c t o r ys e r v e rh a sb e e nc a n c e l e di nu n s t r u c t u r e dp 2 pn e t w o r ka n dt h e r e s u l tc a na v a i l a b l ye l i m i n a t eb o t t l e n e c kc a u s e db ys t r u c t u r en e t w o r k ，s ou n s t r u c t u r e d p 2 pn e t w o r kh a sp r e f e r a b l ep e r f o r m a n c e si nm a i n t a i n a b i l i t ya n df a u l tt o l e r a n c e b u t ， r e s o u r c es e a r c hh a sb e c o m en e wb o t t l e n e c ki n a p p l i c a t i o nb e c a u s eo fr e s o u r c e c o m p l e t ed i s t r i b u t i o na n dd y n a m i cs e l f - o r g a n i z a t i o n m o s to fs e a r c ha l g o r i t h m s a p p l i e di nu n s t r u c t u r e dp 2 pn e t w o r ka r eb a s e do ff l o o d i n gm e c h a n i s m ，w h i c hr e s u l t s i nc o m m o np r o b l e m sa r ee x c e s s i v eu s eo fb a n d w i d t ha n di n e f f i c i e n te f f i c i e n c yo f r e s o u r c es e a r c h s ot h i sh a sb e e nam a j o ra r e ai nf u t u r er e s e a r c ho fi n t e l l i g e n t i z e d s e a r c ha l g o r i t h m a n t c o l o n yo p t i m i z a t i o n h a s d i s p l a y e d e x c e l l e n t p e r f o r m a n c ei np a t h o p t i m i z a t i o no p t i o ns i n c ei tw a sc r e a t e d ，a f t e rd e t a i l e dr e s e a r c ho na n tc o l o n y o p t i m i z a t i o n ，w eu s ei ti n t oa r e ao fr e s o u r c e ss e a r c ho fu n s t r u c t u r e dp 2 pn e t w o r ka n d p r e s e n tas e a r c ha l g o r i t h mb a s e do na n tc o l o n yo p t i m i z a t i o ni nu n s t r u c t u r e dp 2 p n e t w o r k i nt h ea l g o r i t h m ，p e e r - p h e r o m o n ea n dp a t h p h e r o m o n ea r er e a s o n a b l y d e f i n e dt oe n s u r ei t se x c e l l e n ts e a r c he f f i c i e n c y , a n dam e t h o do fp a t h so p t i m i z e c h o i c ei sp r e s e n t e di nt h ea l g o r i t h mt oa v o i dt h ep r o b l e mo f p a t h d i s a b l e db e c a u s eo f p e e r sd y n a m i c b e s i d e s ，p o w e r - l a wp r o p e r t i e sa n dp r i n c i p l eo fl o c a l i t yw h i c hh a v e b e e nd i s p l a y e di np 2 pn e t w o r ka r ea d e q u a t e l yu s e di na l g o r i t h m t h a ti st os a y , o n e h a n d ，t h o u g ht h e r e l a t i o n sb e t w e e n p e e r sa r ee q u i p o t e n t i np 2 pn e t w o r ki n t h e o r e t i c a l l y , r e a ln e t w o r kh a sb e e nd i s p l a y i n gp o w e r - l a wp r o p e r t i e so b v i o u s l y ，w h i c h m e a n sm i n o rp e e r sc o n t a i nm a j o ru s e f u lr e s o u r c e s ，t h er e s t p e e r sc o n t a i nf e w r e s o u r c e so rn o t h i n ga n db e c o m es o - c a l l e di n e f f i c i e n c yp e e r s o nt h eo t h e rh a n d ， a c t i o n so fr e s o u r c e ss e a r c hh a v es i m i l a r i t yi np 2 pn e t w o r k ，w h i c hm e a n sa c t i o n so f s e a r c hf o l l o wp r i n c i p l eo fl o c a l i t y , a n dt h i sm e a n sam a s so fu s e r sh a v em o r ei n t e r e s t s o rd e m a n d si ns o m es p e c i f i cr e s o u r c e s ，a n dc o r r e s p o n d i n gr e s o u r c e sb e c o m ek e yo f s e a r c h 1 1 1 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 d e t a i l e dd e s i g ni s p r e s e n t e d i nt h ea l g o r i t h m f i r s t ，p e e r si nn e t w o r ka r e c l a s s i f i e d ，p e e r st h a to f t e np r o v i d eu s a b l er e s o u r c e sa r ec a l l e de f f e c t i v ep e e r s ，a n d t h e s ep e e r st h a ts e l d o mo rn e v e rp r o v i d er e s o u r c e se v e np r o v i d em a l i c i o u sr e s o u r c e s a r ec a l l e dp a s s i v ep e e r s c o r r e s p o n d i n g l y , p e e r - p h e r o m o n ei sd e f i n e db a s e do np e e r s s u c c e s sr a t e so fr e s o u r c e sc o n t r i b u t i o n ，w h i c ha saf o u n d a t i o no fp e e r s c h o i c ei n o r d e rt oa v o i dv i s i t i n go fp a s s i v ep e e r s ，p a t h p h e r o m o n ei sd e f i n e db a s e do nn u m b e r o fc o m m u n i c a t i o n sd u r i n gp e e r s ，w h i c hc a nw e i g hs t a b i l i t yo fp e e r st oa v o i dv i s i t i n g o fu n s t a b l ep a t h sa n dp e e r s b e s i d e s ，r e s o u r c e si n i t i a t i v em e c h a n i s mi sp r e s e n t e d a c c o r d i n gt ol o c a lp r i n c i p l e so fr e s o u r c e sq u e r i e sa n dp o w e r - l o wb e h a v i o rd i s p l a y e d i np 2 pn e t w o r ka sa na u x i l i a r ym e t h o do fr e s o u r c e ss e a r c h ，w h i c hc a nt a k ei n i t i a t i v e d e c l a r a t i o no nr e s o u r c e st h a to f t e nb ev i s i t e dt oh e l pr e a l i z et h ed i r e c t e dp o s i t i o n i n go f r e s o u r c e st of u r t h e ri m p r o v ee f f i c i e n c yo fr e s o u r c e ss e a r c h i no r d e rt ov e r i f ya l g o r i t h m sp e r f o r m a n c e ，as i m u l a t i o ne x p e r i m e n tb a s e do n g r i d s i mi sp r o p o s e da tt h ee n do fp a p e r , a n dac o m p a r i s o nw a sm a d ew i t ho t h e rt w o a l g o r i t h m s ，f l o o d i n ga n dc h o r d ，t h er e s u l t ss h o wt h a t t h i sa l g o r i t h mh a sb e t t e r p e r f o r m a n c ei nr o u t i n gq u e r ya n dh i tr a t i oo fr e s o u r c e sc o m p a r e dw i t hf l o o d i n ga n d c h o r d k e yw o r d s ：p 2 p ；a n tc o l o n ya l g o r i t h m ；p o w e r - l o wb e h a v i o r ；p h e r o m o n e ； r e s o u r c e ss e a r c h l v 1 1 研究背景一1 1 2 国内外研究现状一2 1 3 论文主要研究内容4 1 4论文组织结构5 第2 章相关知识简介7 2 1 p 2 p 网络概述7 2 1 1p 2 p 基本概念7 2 1 2p 2 p 的技术特点8 2 1 3p 2 p 的应用9 2 2 p 2 p 网络模型1 0 2 2 1 集中目录式网络模型11 2 2 2 分布式网络模型1 2 2 2 3 混合式网络模型1 3 2 3p 2 p 网络资源搜索技术1 5 2 3 1 搜索机制1 5 2 3 2 常见搜索算法15 2 4蚁群算法基础知识2 1 2 4 1核心概念21 2 4 2 蚁群算法工作原理2 3 2 4 3蚁群算法工作流程2 4 2 4 4 蚁群算法应用2 5 2 5 本章小结2 6 第3 章基于蚁群算法的非结构化p 2 p 网络资源搜索算法2 7 3 1问题分析2 7 3 1 1 p 2 p 网络的特点一2 8 3 1 2 非结构化p 2 p 网络资源搜索面临的问题2 8 v p 2 p 网络中基于蚁群算法的资源搜索研究与设计 3 1 3p 2 p 网络的局部性原理和幂律特性2 9 3 1 4 算法优化思路3 0 3 2算法设计3l 3 2 1节点的划分31 3 2 2 节点结构3 2 3 2 3 信息素的定义与更新3 3 3 2 3 1 节点信息素的定义与更新3 4 3 2 3 2 路径信息素的定义与更新3 4 3 2 4 最优路径的选取3 5 3 2 5资源的主动声明3 5 3 3算法实现3 6 3 3 1 算法描述3 6 3 3 1 1 算法步骤3 6 3 3 1 2 资源主动声明机制的使用3 8 3 3 2 算法流程3 9 3 4 本章小结4 l 第4 章仿真实验4 2 4 1仿真平台g r i d s i m 分析4 2 4 1 1 g r i d s i m 体系架构一4 2 4 1 2g r i d s i m 模拟过程4 3 4 2实验设计4 5 4 2 1 实验参数设置4 5 4 2 2实验流程4 5 4 2 3 算法在g r i d s i m 中的实现4 6 4 3结果分析4 8 4 3 1搜索路径长度比较。4 8 4 3 2 搜索成功率的比较。一4 9 4 4本章小结5 0 第5 章总结与展望5 1 江苏大学硕士学位论文 5 1 总结一5 l 5 2 展望一5 2 参考文献5 3 致谢 一5 6 攻读硕士学位期间发表的论文5 7 v l l 位论文 论 近年来，随着网络技术的发展，尤其是国内互联网的迅速普及，人们对网络 资源需求越来越多。网络资源的发展速度出现了以下特点：网络的流量以每6 个 月翻倍的速度增长，网络带宽以每7 个月翻倍的速度增长，计算资源近似依照摩 尔定理速度增长( 1 8 个月翻倍) ，而存储能力每年仅提升7 。网络资源的迅速 膨胀，而相应的网络承载能力却没有跟上它的步伐。而造成这一困境的一个主要 原因就是传统的c s 网络模式的局限性。众所周知，传统的c s 模式需要一个单 独的中央节点或者服务器来提供服务，它使互联网上的资源向服务器集中，在这 种模式下网络的每个用户向服务器发出请求，然后从服务器得到相应的回应信 息，用户之间的交流均高度依赖于网络服务器，无法进行直接的信息交流。 p 2 p 技术瞳1 的出现有效地解决了这一问题。客观上讲，p 2 p 并不是新技术， 在2 0 世纪7 0 年代就已出现，其典型的代表是u s e n e t 和f i d o n e t 这两个分散、 分布的信息交换系统，而真正的p 2 p 技术的大规模应用起源于文件交换软件 n a p s t e r 。p 2 p 的基本特征是直接将人们联系起来，让人们通过因特网直接交流。 它使网络上的沟通变得更容易、直接，真正地消除中间环节。p 2 p 技术是目前国 际计算机网络技术领域研究的一个热点，被财富杂志誉为将改变因特网未来 的四大新技术之一，甚至被认为是无线宽带因特网的未来技术。包括微软、s u n 、 i b m 等很多著名的企业和公司都投入到对p 2 p 技术的研究之中。作为一种分布式 网络，p 2 p 网络的参与者共享他们所拥有的一部分硬件资源( 处理能力、存储能 力、网络连接能力和打印机等) ，这些共享资源需要由网络提供服务和内容，能 被其他对等节点( p e e r ) 直接访问而无需经过中间实体。随着高速互联网的普及、 个人计算机计算和存储能力的提升，p 2 p 网络技术重新登上历史舞台并且带来了 一场技术上的革命。 p 2 p 的应用有三大类，即资源共享、协同工作、分布计算。其中应用最广泛 的就是资源共享，这也使得资源搜索成为p 2 p 的核心技术。基于p 2 p 网络的搜 索方法与目前其他各类传统的搜索方法相比，其优势在于使用了更加先进的对等 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 搜索理论，不需要通过中央服务器，也可不受信息样式和设备的的制约，对互联 网络进行全方位的搜索。如何以最小的代价找到所需资源是p 2 p 资源搜索需要 解决的关键问题，而其应用的可行性取决于能否实现对数据高效的查找和提取， 这也成为限制p 2 p 网络发展的的“瓶颈”问题之一。 1 2 国内外研究现状 p 2 p 技术进入我国市场的时间并不是很长，但是，近几年来，随着我国宽带 技术的发展和我国网民对p 2 p 的逐步认可，国内的p 2 p 市场正在日益发展壮大。 从目前的状况来分析，我国的p 2 p 发展正处在自由竞争阶段，进入市场的 企业，无论是规模还是实力都不相上下。因此，在较长一段时间内，我国的p 2 p 是长将延续势均力敌的竞争局面。然而，由于我国的p 2 p 市场十分年轻，所以 蕴藏着很多商机，企业在p 2 p 的许多商业应用领域都可以有所作为。目前，国 内的p 2 p 产品主要有： ( 1 ) 北京大学的m a z e 。它是北京大学网络实验室开发的一个中心控制与对 等连接相融合的对等计算机文件共享系统，在结构上类似n a p s t e r ，对等计算搜 索方法类似于g n u t e l l a 。网络上的一台计算机，不论是在内网还是外网，都可以 通过安装运行m a z e 的客户端软件自由加入和退出m a z e 系统。每个节点可以将 自己的一个或多个目录下的文件共享给系统的其他成员，也可以分享其他成员的 资源。 ( 2 ) 清华大学的g r a n a r y 。它是清华大学自主开发的对等计算存储服务系统。 它以对象格式存储数据。另外，g r a n a r y 设计了专门的节点信息收集算法 p e e r w i n d o w 的结构化覆盖网络路由协议t o u r i s t 。 ( 3 ) 华中科技大学的a n y s e e 。它是华中科大设计研发的视频直播系统。它 采用了一对多的服务模式，支持部分n a t 和防火墙的穿越，提高了视频直播系统 的可扩展性；同时，它利用近播原则、分域调度的思想，使用l a n d m a r k 路标算 法直接建树的方式构建应用层上的组播树，克服了e s m 等一对多模式系统由于连 接图的构造和维护带来的负面影响。 ( 4 ) 广州数联软件技术有限公司的p o c o 。它是我国最大的p 2 p 用户分享平 台，是有安全、流量控制能力的，无中心服务器的第三代p 2 p 资源交换平台， 2 江苏大学硕士学位论文 也足世界范围内少有的盈利的p 2 p 平台。目前已经形成了2 6 0 0 万海龟用户，平 均在线5 8 5 万，在线峰值突破7 1 万，成为国内第一的p 2 p 分享平台。 ( 5 ) 基于p 2 p 的在线电视直播p p l i v e 3 1 。它是一款用于因特网上大规模视 频直播的共享软件。它使用网络模型，有效地解决的了当前网络视频点播服务的 带宽和负载有限问题，实现用户越多，播放月流畅的特性，整体服务质量大大提 高。 ( 6 ) 2 0 0 5 年1 2 月中旬，中国网络通信集团贵州分公司宣布正式推出以p 2 p 为基础的免费视频点播业务。这是国内首家开始商用p 2 p 技术的主流运营商。 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p 2 p w g ) 、全球网格论 坛( g l o b a lg r i df o r u m ，g g f ) 。p 2 p 工作组成立的主要目的是希望加速p 2 p 计 算基础设施的建立和相应的标准化工作。p 2 p w g 车公里后，对p 2 p 计算中的术 语进行了统一，也形成了相关的草案，但是在标准化工作方面进展缓慢。目前 p 2 p w g 已经和g g f 合并，由该论坛管理p 2 p 计算相关的工作。g g f 负责网格 计算和p 2 p 计算等相关的标准化工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 、s u n 和i n t e l 公司投入 较大。m i c r o s o f t 成立了p a s t r y 项目组，主要负责p 2 p 计算技术的研究、开发工 作。目前m i c r o s o f t 公司已经发布了基于p a s t r y 的软件包s i m p a s t r y v i s p a s t r y 。r i c e 大学也在p a s t r y 的基础上发布了f r e e p a s t r y 软件包。 2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组，正式开展p 2 p 的研究，工作 组成立以后，积极与应用开发商合作，开发p 2 p 应用平台。2 0 0 2 年i n t e l 发布 了n e t 基础架构之上的a c c e l e r a t o rk i t ( p 2 p 加速工具包) 和p 2 p 安全a p i 软件 包，从而使微软n e t 开发人员能够迅速建立p 2 p 安全w 曲应用程序。 s u n 公司以j a v a 技术为背景，开展了j x t a l 4 1 项目。j x t a 是基于j a v a 的开 源p 2 p 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大 批p 2 p 研究人员和开发人员，而且已经发布了基于j x t a 的即时聊天软件包。 j x t a 定义了一组核心业务：认证、资源发现和管理。在安全方面，j x t a 加入 了加密软件包，允许使用该加密包进行数据加密，从而保证消息的隐私、可认证 性和完整性。在j x t a 核心之上，还定义了包括内存管理、信息搜索以及服务管 理在内的各种其他可选j x t a 服务。在核心服务和可选服务基础上，用户可以开 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 发各种j x t a 平台上的p 2 p 应用。 在p 2 p 技术高速发展的同时，国外的运营商也开始尝试用p 2 p 技术部署网 络。总部位于挪威首都奥斯陆的v o l p 服务供应商i p d r u m 公司，退出了i p d r u m m o b i l es k y p ec a b l e 解决方案，通过该解决方案可以令s k y p e t m 与移动电话完美结 合，为用户提供真正意义上的移动通信和全球范围内的免费电话。 诺基亚公司于2 0 0 6 年2 月1 5 日在西班牙巴塞罗那举行的3 g s m 2 0 0 6 上发 布了他们旗下的第二款支持u m a 技术的手机：6 1 3 6 所谓“u m a ”是一种3 g p p 标准的接入技术，支持移动语音与数据从蜂窝到无线局域网的无缝转换 ( w l a n w i f i ) 。 1 3 论文主要研究内容 p 2 p 网络分为结构化p 2 p 网络和非结构化p 2 p 网络。结构化p 2 p 网络由于 采用分布式哈希( d h 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 网络还存在免费乘车现象 ( f r e e r i d i n g ) ，即大量节点只索取资源而不会共享资源，成为所谓的低效节点或 者无效节点，造了资源的搜索请求将在更多的节点之间转发才能到达资源所在的 4 江苏大学硕士学位论文 节点，既增加了系统开销，又进一步加深了搜索的延时。 针对以上问题，本文提出了一种基于蚁群算法的资源搜索算法，该算法以 节点上资源访问成功率来定义节点信息素，以避免对低效节点的访问；以节点间 的通信次数为基数定义相邻节点的路径信息素，使搜索尽量在稳定的节点问进 行，降低搜索范围，提高搜索效率。针对节点的动态性带来的搜索路径失效的问 题，本文提出一种路径优化选择方法：对被选路径进行优化选择，选出最优路径， 尽量避免路径失效带来的搜索失败问题。另外，为充分利用资源自身的信息，本 文提出一种资源主动声明机制，直接对资源进行定位，作为资源搜索的辅助方法， 提高搜索效率。 论文给出了该机制的详细搜索算法，并进行了仿真试验。试验结果表明，相 比于f l o o d i n g 和c h o r d 算法，本文算法在提高搜索成功率的同时也降低了查询 次数。 1 4 论文组织结构 本文共分5 章，文章结构及各章主要内容组织如下： 第1 章绪论。介绍课题的研究背景、国内外关于p 2 p 的研究现状，以及p 2 p 现在和未来的主要应用领域。 第2 章相关知识综述。主要介绍了p 2 p 的背景技术知识，即p 2 p 的基本概 念的以及p 2 p 的系统结构，在此基础上介绍了p 2 p 网络中的搜索机制和搜索算 法，其中重点介绍了非结构化p 2 p 网络中的搜索算法。另外，介绍了蚁群算法 的相关基础知识，为本文算法的提出打下良好的基础。 第3 章改进的的p 2 p 资源搜索方法。本章是整篇论文的重点。在充分分析 p 2 p 网络的特点的基础上，结合现存p 2 p 网络中资源搜索机制存在的问题，以及 p 2 p 网络中所表现出的局部性原理和幂律特性，提出了本文的优化算法，最后给 出了算法的详细描述和实现流程。 第4 章仿真实验。本章是对本文课题所提算法的测试章节。首先介绍了实 验所用到的仿真平台g r i d s i m 。分别介绍了它的体系架构和模拟过程，并在此基 础上给出了实验的设计过程，最后对实验数据进行了对比分析。 第5 章总结与展望。首先对本文所做过工作进行了简单的总结，分析了在 5 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 工作过程中所取得的一些阶段性成果以及其中存在的不足之处。 6 江苏大学硕士学位论文 第2 章相关知识简介 本章作为本文课题研究的背景，首先介绍了p 2 p 网络的一些基础理论知识 和常见的网络模型。在此基础上介绍了p 2 p 网络搜索技术，先是介绍了p 2 p 网 络的搜索机制，然后详细介绍了几种常见搜索算法，分析了这些算法的搜索性能； 然后介绍了蚁群算法的相关理论知识，分别介绍了蚁群算法的核心概念、工作原 理和工作流程，最后列出了蚁群算法的一些应用。 2 1p 2 p 网络概述 2 1 1p 2 p 基本概念 p 2 p 即p e e r - t o p e e r 的缩写1 6 j 。而p e e r 在英语里是“同等着”的意思。因此， p 2 p 也就可以理解为“伙伴对伙伴”的意思，或称为对等网络。p 2 p 也可以被看 作是一种思想，它具有改变整个因特网的潜能的思想。虽然从纯技术角度而言， p 2 p 并未激发出任何重大的创新，而更多的是改变了人们对因特网的理解与认 识。正是由于这个原因，i b m 早就宣称p 2 p 不是一个技术概念，而是一个社会 和经济现象。不管是技术还是思想，p 2 p 直接将人们联系了起来，让人们通过因 特网直接进行交流。现在，对p 2 p 概念进行了扩展，作为一种分布式网络，网 络的参与者共享他们所拥有的一部分硬件资源( 处理能力、存储能力、网络连接 能力、打印机等) ，这些共享资源需要由网络提供服务和内容，能被其他对等节 点直接访问而无需经过中间实体，在此网络中的参与者既是资源( 服务和内容) 提 供者( s e r v e r ) ，又是资源的获取者( c l i e n t ) 。i b m 公司认为：p 2 p 系统由若干互联 协作的计算机构成，且至少具有如下特征之一：系统依存于边缘化( 非中央式服 务器) 设备的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益； 系统中成员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的 存在，构成一个虚拟或实际的群体。目前，学术界、工业界对于p 2 p 没有一个 统一的定义，但是共同点就是p 2 p 打破了传统的c s 模式，在网络中的每个节 7 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 点的地位都是对等的。每个节点既充当服务器，为其它节点提供服务，同时也享 用其它节点提供的服务。 2 1 2p 2 p 的技术特点 相对于传统的c s 模式的网络，p 2 p 网络具有其自身的一些技术特点。 ( 1 ) 去中心化：与传统的c s 模式最显著的一点区别就是，p 2 p 网络中所 有的资源及服务分布在各个节点上，资源信息的交流直接在节点之间进行，无需 通过中间环节和服务器的介入，很好地解决了c s 模式遇到的性能瓶颈问题。 ( 2 ) 可扩展性：p 2 p 网络的另一个特点是，用户节点可以自由地加入或者 退出网络。用户节点的加入，使得服务的需求增加，整个网络系统的资源和服务 能力也在同步提高，能很容易地满足用户的需求。整个体系是完全分布式的，不 存在瓶颈问题。 ( 3 ) 稳健性：p 2 p 的网络结构特点决定了它的高安全、高容错的特点。由 于资源和服务分散在各个节点，部分节点或网络的损坏对其他部分的影响很小。 p 2 p 网络在节点退出或者失效时能够自发调整整体拓扑结构f _ 7 1 ，保持剩余节点的 连通性。p 2 p 网络通常都是以自组织的形式建立起来的，没有特定的约束规则， 它允许节点自由地加入或离开。此外，还能够根据网络带宽、负载等变化做自适 应的调整。 ( 4 ) 负载均衡：p 2 p 的中文解释就是对等网络的意思，这就决定了网络中 节点的地位是平等的。也就是说，网络中的每个节点既充当服务器的角色，又充 当客户机的角色，这就降低了对传统c s 中心结构服务器的计算能力、存储能力 的要求，同时由于资源分布在各个节点，很好的实现了整个网络的负载均衡。 ( 5 ) 迅速定位：p 2 p 的资源定位技术是基于内容寻址的，这里的内容不仅 包括信息资源的数据内容，还包括带宽状态、存储空间等。p 2 p 网络中，用户节 点直接输入要索取的资源信息的内容，而不是信息的所在地址，p 2 p 软件会迅速 地把用户节点的请求翻译成包含此信息的节点的实际地址，进而快速定位请求资 源并得- n s h 应。 ( 6 ) 资源的高利用率：p 2 p 网络的另外一个显著特点就是对资源的高利用 率。传统的c s 模式下，中央服务器负责存储和管理所有的资源。尽管这些高性 8 江苏大学硕士学位论文 能的大型机拥有较大规模的资源处理能力，但仍然无法和p 2 p 网络中众多节点 的集合能力相提并论。在p 2 p 模式下，许多分散的资源、信息和服务自组织的 利用起来，众多节点的资源总和构成了整个网络的资源，使得整个网络的存储能 力得到最大限度的提升，使其具有超级计算机的巨大计算处理能力。 2 1 3p 2 p 的应用 目前，网络上实际广泛使用的p 2 p 应用大致可分为以下几种，下面逐一进 行分析。 ( 1 ) 文件共享：p 2 p 文件下载是p 2 p 应用中最为广泛的方式之一，它通过 在不同用户间直接进行文件交换达到文件共享的目的。该种方式较之传统c s 模 式下从公共服务器系统下载文件的方式具有速度快、资源丰富等优势。其中最为 典型的应用就是b t 下载，其原理如图2 1 所示。 ，臼 懋畔 返回l a e e r 一 l 上传、下载 ，上传、下载 图2 1b t 下载工作原理 ( 2 ) 协作：p 2 p 群件允许在封闭的工作组级别上使用文档管理，其结果是 工作组成员能够同步地通信、进行集体在线会议和编辑共享文档。在基于客户 服务器的群建中，在服务器上必须为每个工作组建立并管理一个用于中心数据管 理的对应工作区。为了避免这个额外的管理任务，可使用p 2 p 网络进行合作研 究工作。目前，在协同工作方面，基于p 2 p 网络原理最有名的应用是g r o o v e 虚 拟办公室( g r o o v ev i r t u a lo f f i c e ) ，这个系统提供的功能类似于那些广泛使用c s 的应用，如l o t u s 系列产品、n o t e s 、s a m e t i m e ，但这个系统不需要中心的数据 9 p 2 p 网络中基于蚁群算法的资源搜索研究与设计 管理，创建的所有数据存储在每个对等端即节点上，并自动地同步。如果对等端 不能相互直接到达，有一种通过目录和中继服务器的异步的同步方法可以选择。 ( 3 ) 在席信息：就p 2 p 应用而言，在席信息扮演了一个非常重要的角色。 在p 2 p 网络的自组织中，这是决定性的，因为它提供了网络中哪个对等端和哪 个资源是可用的，这使对等节点们能够建立到其他对等节点的直接联系并请求资 源。一个广泛的p 2 p 示例是即时消息系统，它实际上使用在席信息。这些系统 向对等节点提供通过网络传送信息的机会信息，例如就通信过程而言，它们是否 可用。 共享使用处理器周期，和无处不在的计算机和信息可用性( 泛在计算) 相关 的场合中，在席信息的使用是关键的。这些应用能够独立地识别一个计算机网格 内哪些对等端节点对它们是可用的。因此，在泛在计算环境中，如果一个移动设 备能够独立地识别那些在其环境中的可用对等端节点将是有帮助的1 8 l 。 ( 4 ) 视频播放：在基于p 2 p 结构的视频组播系统中，节点一方面从其它节 点处获得数据，一方面也向其它节点提供数据。整个系统的体系结构为树状结构 或者网状结构。这种以对等方式构建的视频组播系统充分利用了结点之问的可用 带宽而使系统的可扩展性大为提高。在视频组播领域的应用包括p p l i v e ， a n y s e e ，g r i d c a s t 等等。 ( 5 ) p 2 p 在v o i p 中的应用：无论传统电信运营商情愿与否，以s k y p e 为代 表的v o l p 软件已经在全球拥有越来越多的用户。s k y p e 是p 2 p 技术演进到混合 模式后的典型应用。它结合了集中式和分布式的特点，在网络的边缘节点