（管理科学与工程专业论文）MP2P资源搜索算法研究.pdf

一 r e s e a r c ho fr e s o u r c ed i s c o v e r y a l g o r i h m i nm o b i l e p e e r - t o p e e rn e t w o r k at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y x i a oc h o n g x i a ( m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g ) t h e s i ss u p e r v i s o r ：p r o f e s s o rc h e nr u l i a n g m a y 2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文 ：丛至塑近理塞篡鎏硒塞：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全 文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发 行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保甜 ( 请在以上方框内打“”) 一唪维名：彦牙彩 日期：肋i 年莎月砧日 中文摘要 摘要 随着移动网络的不断优化以及移动设备的迅速普及，人们逐渐的开始使用移 动网络来实现固定网络中的各种功能。据统计数据显示，移动网民数量己占了网 民数量的6 6 2 。然而，在移动网民数量急剧上升的同时，运营商也面临着移动互 联网数据流量增速远远超过无线带宽增速的问题。为了有效解决这个问题，各大 移动运营商都开始探索如何将成熟的p 2 p 技术应用到移动网络环境中，随之形成 了一个新的研究方向m p 2 p ( m o b i l ep e e r - t o p e e r , 移动p 2 p ) 。因为移动网络环境 具有高动态性、节点处理能力不足以及网络资源受限等特征，所以m p 2 p 技术不 能将原有的p 2 p 技术直接用到移动网络中，必须对其进行改进以适应移动网络这 种特殊环境。在m p 2 p 技术中以网络资源的搜索最为重要，因此本课题的研究方 向就是如何改进原有的p 2 p 资源搜索算法使其能够适应移动网络并提高m p 2 p 资 源搜索的性能。 本文在分析了m p 2 p 特点后设计了一种基于异类多群蚁群算法和移动a g e n t 的m p 2 p 资源搜索算法，另外，还提出了一种超级节点失效处理机制。m p 2 p 中的 节点都具有高动态性特征，超级节点失效会使下层普通节点被迫离开网络，从而 造成资源丢失和目标资源的召回率下降。为了及时处理节点失效以提高资源搜索 的召回率，文中提出了候补节点机制。新设计的算法中引入移动a g e n t 来实现节 点间以一种非直接的方式进行交互，该方式能够减少搜索所耗带宽。另外，算法 中还使用了异类多群蚁群算法，它把整个蚁群划分为多个子蚁群，这些子蚁群可 以属于不同的蚁群系统，这样的设计能够在算法收敛速度和解的多样性间达到平 衡。蚁群算法中的信息素机制使资源搜索能够充分利用原有的历史信息达到减小 一 。 搜索延时和降低网络负载的目标。在论文的最后使用了m a t l a b 工具来对算法进 行性能测试，结果表明，改进后的算法能够提高资源搜索的目标资源召回率并能 够减少资源搜索的流量负载，而其优势在网络规模增加的情况下更加明显。 关键字：m p 2 p ；资源搜索；蚁群算法；移动a g e n t ；候补节点 英文摘要 a b s t r a c t w i t ht h ec o n t i n u o u so p t i m i z a t i o no fm o b i l en e t w o r k sa n dt h er a p i dp o p u l a r i z a t i o n o fm o b i l ed e v i c e s ，p e o p l eg r a d u a l l yb e g i nt ou s em o b i l en e t w o r k st oa c h i e v et h ev a r i o u s f u n c t i o n si nt h ef i x e dn e t w o r k s s t a t s t i e ss h o wt h a t6 6 2 o fi n t e r n e tu s e r sa r em o b i l e i n t e m e tu s e r s s h a r pr i s e i nt h en u m - b e ro fm o b i l eu s e r sa tt h es a m et i m e ，m o b i l e o p e r a t o r sa r ea l s of a c i n gt h ep r o b l e mt h a tt h es p e e do fm o b i l en e t w o r kt r a f f i ci n c r e a s ei s m u c hf a s t e rt h a nt h eg r o w t hr a t eo fw i r e l e s sb a n d w i d t h i no r d e rt oe f f e c t i v e l yr e s o l v e t h i s c o n f l i c t ，i no r d e rt oe f f e c t i v e l yr e s o l - v et h i sc o n t r a d i c t i o nt h em a j o rm o b i l e o p e r a t o r sh a v eb e g u nt oe x p l o r et h ea p p l i c a t i o no fp 2 pt e c h n o l o g yi nt h em o b i l e n e t w o r ke n v i r o n m e n tw h i c hc a l l e dm p 2 pt e c h n o l o g y b u tt h em o b i l en e t w o r k e n v i r o n m e n th a sm a n yf e a t u r e s ，s u c h a s ：h i g hd y n a m i c ，l a c ko fn o d ep r o c e s s i n g c a p a c i t y , l i m i t e dn e t w o r kr e s o u r c e sa n ds oo n s ot h eo r i g i n a lp 2 pt e c h n o l o g yc a l l tb e d i r e c t l ya p p l i e dt om o b i l en e t w o r k s i np 2 pt e c h n o l o g yt h em o s ti m p o r t a n tr e s e a r c h d i r e c t i o ni sr e s o u r c e sd i s c o v e r y , s ot h eo b j e c to ft h i sp a p e ri sh o wt oi m p r o v et h e e x i s t i n gs e a r c ha l g o r i t h mi np 2 pt om a k et h e ma d a p tt ot h em o b i l en e t w o r ka n di m p r o v e ， t h ep e r f o r m a n c eo fr e s o u r c e sd i s c o v e r y a f t e ra n a l y s i n gt h ef e a t u r e so fm p 2 p , t h i sp a p e rd e s i g na ni m p r o v e dr e s o u r c e d i s c o v e r ya l g o r i h mw h i c hb a s e do nd i f f e r e n tk i n d so fa n tc o l o n ya n dm o b i l ea g e n t i n a d d i t i o n , i ta l s om a k eas u p e rn o d ef a i l u r e - h a n d l i n gm e c h a n i s m t h en o d e si nm o b i l e n e t w o r kh a v eah i g hd y n a m i cc h a r a c t e r i s t i c w h e ns u p e r - n o d eb e c o m ef a i l u r e ，t h e c o m m o nn o d e st h a tm a n a g e db yi n v a l i ds u p e r - n o d ea r ef o r c e dt ol e a v et h en e t w o r ka n d t h er e s o u r c e st h a ts t o r e di nt h e s en o d e sh a v e b e e nl o s t t oi m p r o v er e c a l lo f r e s o u r c e s ，t h ep a p e rp r o p o s e sa na l t e r n a t en o d em e c h a n i s m t h em o b i l ea g e n ti nt h i s a l g o r i t h mg a l lm a k en o d e s i n t e r a c t 砸t l le a c ho t h e rb yan o n - d i r e c tw a y w h i c hc a n r e d u c e st h eb a n d w i d t hc o n s u m p t i o no ft h es e a r c h h e t e r o g e n e o u sm u l t i - g r o u pa n t c o l o n ya l g o r i t h mi sa n o t h e ri n n o v a t i o no ft h ea l g o r i t h m ，i td i v i d et h ew h o l ec o l o n yi n t o m u l t i p l es u b - a n tc o l o n i e sw h i c hc a l lb e l o n gt od i f f e r e n ta n tc o l o n ys y s t e m s t h ed e s i g n c a nk e e pb a l a n c eb e t w e e nt h ec o n v e r g e n c es p e e da n dt h ed i v e r s i t yo fr e s u l t t h ee x i s t i n g h i s t o r i c a li n f o r m a t i o nc a nb em a d e9 0 0 du s eo fw i t l lp h e r o m o n ei nt h ea n tc o l o n y a l g o r i t h m t h i sw a yc a nr e d u c es e a r c hl a t e n c ya n dn e t w o r kl o a d a tt h ee n do fp a p e r 英文摘要 m a t i a bi su s e dt o t e s tt h ev a l i d i t yo ft h i si m p r o v e da l g o r i t h m t h er e s u l t ss h o wt h a t t h ei m p r o v e da l g o r i t h mc a ni m p r o v er e s o u r c ed i s c o v e r yr e c a l lr a t ea n dr e d u c et r a f f i c l o a d ，a n dm o r e o v e rt h i sa d v a n t a g ei sm o r ea p p a r e n tw i t ht h ei n c r e a s i n gs c a l eo ft h e n e t w o r k k e yw o r d s ：m p 2 p ；r e s o u r c ed i s c o v e r y ；a n t c o l o n ya l g o r i t h m ；m o b i l ea g e n t ； a l t e r n a t en o d e 录 目录 第1 章绪论1 1 1 课题研究背景及意义1 1 2 研究现状2 1 3 课题研究目标和创新点。3 1 4 论文内容及组织结构5 第2 章m p 2 p 网络研究6 2 1m p 2 p 网络综述6 2 1 1传统p 2 p 网络6 2 1 2 m p 2 p 与p 2 p 的比较1 5 2 1 3m p 2 p 关键技术方向1 6 2 2 典型p 2 p 资源搜索算法1 8 2 2 1泛洪算法：1 9 2 3 蚁群算法。j ；：j 2 4 2 3 1 蚁群算法原理：_ ：2 4 2 3 2 蚁群算法分类：2 5 2 3 3 蚁群算法应用j j ：_ 。：2 7 。 2 4 本章小结：。：j 2 9 第3 章m p 2 p 资源搜索算法设计。j j 。3 0 3 1 网络架构设计；：o ：31 3 1 1 网络体系框架3 1 3 1 2 超级节点结构设计j 。3 2 3 1 3 移动a g e n t 分类及行为设计。3 5 3 2 算法模型的建立：3 9 3 2 1 问题描述一3 9 3 2 2 模型说明3 9 3 2 3目标函数4 0 3 2 4 假设约束条件4 l 3 3 异类多群蚁群算法设计4 1 3 3 1 蚁群种类的选择4 2 3 3 2 交流子群体的确定4 4 3 3 3 交流周期的设计。4 6 目录 3 3 4 子群体间信息交流的方法 3 4m p 2 p 资源搜索机制。4 7 3 4 1 单蚁群内部的路由机制4 8 3 4 2 单蚁群内部的信息素更新策略。51 3 4 3 m p 2 p 资源搜索的流程5 2 3 5 节点变动处理。5 7 3 5 1 普通节点的变动：i 5 7 3 5 2 超级节点的变动：5 9 3 6 本章小结6 l 第4 章算法测试与结果分析6 2 4 1 测试目标6 2 4 2 测试环境。6 3 4 2 1 使用工具介绍6 3 4 2 2 具体环境配置6 4 4 3 算法有效性验证j ：6 6 4 3 1 候补节点的有效性6 6 4 3 2 异类多群蚁群算法的有效性6 7 4 4 本章小结：。：6 9 第5 章总结与展望。7 0 5 1 本文总结。：_ 7 0 5 2 工作展望。7l 参考文献7 2 攻读学位期间公开发表论文7 6 致谢7 7 研究生履历：7 8 m p 2 p 资源搜索算法研究 第1 章绪论 1 1 课题研究背景及意义 未来的信息社会在很大程度上要依赖于无线技术。近年来，随着信息通信的 迅速发展，产生了众多不同的无线接入技术，如：g s m 、p h s 、c d m a 、w c d m a 、 b l u e t o o t h 等等。日前从中国移动获悉，“新一代宽带无线移动通信网”国家重大科 技专项t d l t e 规模技术试验取得新进展，将于2 0 1 1 年下半年推出t d l t e 上网 卡供用户体验，上网峰值速度将达到每秒上百兆，是目前3 g 上网速度的1 0 倍以 上【1 1 。在移动网络传输速度不断增加的同时，移动设备的硬件配置和外观表现也是 一再创出新记录，目前，加拿大已出现一种重量不足苹果i p h o n c4 六分之一的手 机，而其机身薄度更是只有几页纸厚度。正是因为移动设备技术的不断创新，人 们越来越希望能够使用这些设备来进行各种日常工作、生活和娱乐，如：视屏会 议、网络视屏、在线电影等。 统计数据显示，移动互联网数据流量增速远远超过无线带宽的增速，给移动 网络带来了巨大的压力。作为中国三大移动运营商，中国移动、中国电信以及中 国联通均公布了其移动用户数量。截至1 月3 1 日，中国移动用户总数达到了5 8 9 2 8 亿户，其中当月新增用户5 2 6 3 万户；中国电信方面，截至1 月3 1 日，移动用户 总数达到9 4 0 5 万户，其中当月新增用户数为3 5 3 万户；而中国联通用户总数也已 超过1 5 4 亿户【2 1 。为了缩小移动网络使用流量增速和无线带宽发展之间的差距， 各大运营商都在不断尝试将p 2 p ( p e e r - t o p e e r ) 技术应用到自己的网络中并对其应用 模式不断的进行改进。 运营商使用p 2 p 技术来优化自己的网络，这样既能保证用户的下载速度又可 以减轻运营商自己的网间出i z i 带宽压力，从而达到用户和运营商双赢的目的【3 1 。然 而，无论移动设备制造商或是移动运营商怎样提高自己的技术都不能解决移动网 络和固定网络之间的差距，如：节点移动性，能源受限，拓扑变化频繁，处理能 力受限，无限传播环境的复杂性等。移动网络的这些不同点导致在互联网中已经 第1 章绪论 发展比较成熟的p 2 p 技术并不适合直接用到无线环境中。所以，如何将应用成熟 的p 2 p 技术应用到移动网络中成为了新的研究趋势。而资源搜索算法是传统p 2 p 网络和m p 2 p ( m o b i l ep e e r - t o p e e r , 移动p 2 p ) 中研究的一个重要内容，如何以有效的 算法快速准确地进行资源搜索关系到整个网络的效率和性能。因此，有必要针对 移动p 2 p 网络的特点设计合适的资源搜索算法。 1 2 研究现状 目前对m p 2 p 资源搜索的研究主要是从两个方向进行：一是不再考虑传统p 2 p 的算法而直接设计出m p 2 p 资源搜索算法；二是改进原有p 2 p 资源搜索算法使其 适用于移动网络环境。在这两个方向中，后者是现在的主要研究方向，其原因在 于：第一，基于i n t e r n e t 的p 2 p 资源搜索策略因为进行了比较长时间及大范围应用， 其性能得到了很好的验证；第二，很多移动设备可以通过一定的基础设施实现在 无线网络和固定网络之间自由切换，因此我们在研究m p 2 p 资源搜索时需要考虑 异构网络间协议兼容的问题。 ( 1 ) 设计新的m p 2 p 搜索算法 根据搜索原理的不同可以将设计全新的m p 2 p 资源搜索策略的思路分为两种： 反应式( p r o a c t i v e ) 和先应式( r e a c t i v e ) 。先应式需要在网络中事先存放好共享资源的 位置信息和路由信息，反应式则不需要维护这样一个信息表，它只是在需要进行 信息交互时才发起相关信息请求，以洪泛的形式向整个网络扩散。先应式资源搜 索策略需要事先建立资源索引，该方式使其不适合节点频繁移动的m p 2 p 网络环 境；反应式则具有更好的变动适用性，但是反应式资源搜索策略主要是采用洪泛 式的信息传播方式，该方法增加了网络的冗余通信量，加重了网络的负载。综上 所述，最好的处理方式就是将先应式和反应式两种资源搜索策略进行有机结合， 以充分利用两者的优点。这是今后设计全新m p 2 p 资源搜索策略的一个发展方向。 ( 2 ) 改进p 2 p 搜索算法 在将p 2 p 应用于互联网的过程中，出现了很多应用于在不同网络拓扑结构的 经典资源搜索算法，基于这些经典算法和m p 2 p 的本身特点来设计适用m p 2 p 的 资源搜索策略。这样的改进方式既能保证算法的有效性又能节约资源。王萍【4 】改进 m p 2 p 资源搜索算法研究 了p 2 p 中多维搜索系统，提出了一种移动p 2 p 多维搜索系统一m u l t i d i m e n s i o n a l i n d e xi nm o b i l ee n v i r o n m e n t ( m i m e ) 。传统p 2 p 中的多维搜索系统是将多维数据空 间划分为不同大小的子空间，根据覆盖网组织结构模块中的规则将各个子空间分 配给网络中的各对等节点。而m i m e 则将空间划分为数据空间和物理空间两种， 并通过这样的二维空间对系统物理网络拓扑结构建模以实现覆盖网络和物理网络 的一致性，解决了传统多维搜索系统的不一致问题。程超【5 】提出了一种改进t a p e s t r y 的新算法m t a p e s t r y ，该算法将超级节点的概念应用到了t a p e s t r y 算法中，在原来 的t a p e s t r y 算法中每个对等节点均保存有搜索索引且都需负责消息的转发，这样会 造成节点瓶颈以及资源浪费问题。而在引入m t a p e s t r y 的m p 2 p 系统中只有高性 能的超级节点才存有这些索引并负责转发资源搜索信息，这样既不存在节点瓶颈 问题也减少了索引占用的存储空间。刘孝男【6 】在其论文中设计了一个m d b s ( m o d i f i e dd i r e c t i o n b a s e ds e a r c h ) 算法，其设计理念是将洪泛式搜索算法与结构化 分布式散列表结合起来并进行一定的改进。具体表现在两个方面：其一，将节点 划分为超级节点和普通节点，并将基于d h t 的搜索机制与洪泛机制相结合。其二， 通过使用较少的副本、缓存和控制信息来减少洪泛的次数，从而降低搜索过程所 占用的网络带宽，并提高整体的搜索效率。p e n gg 、l is p 、j i nh r 等人1 7 1 提出了 一种基于传统c a n 的帆a n 算法，c a n 算法能有效减少路由条数，降低路由 延时，但是当网络中节点数量很大时，该算法资源定位所需要的时间会呈指数级 增加，而现在移动设备数量庞大，因此该算法不能直接用在m p 2 p 中。为了解决 c a n 算法的流量负载过高的问题，眦a n 算法引入了超级节点以及普通节点的 注册和分组机制，算法资源定位首先在超级节点间进行，这种方式能有效减少路 由节点的数量，提高发现资源的效率。 1 3 课题研究目标和创新点 随着技术的发展以及移动终端处理能力的增强，网民间相互共享文件不仅仅 是通过固定网络进行，还可以由移动网络实现随时随地的文件分享。但是移动网 络和固定网络又有很大的不同，设备的移动性、网络连接的不稳定性等使得原来 成熟运用的p 2 p 技术不能按部就班的运用到移动网络环境中，自从m p 2 p 提出以 第1 章绪论 来就有很多人专注于研究如何提高p 2 p 应用于移动网络中的性能。在m p 2 p 技 研究中，资源搜索又是p 2 p 应用的关键技术。因此本文主要是研究m p 2 p 中的 源搜索算法并在这个基础上提出一种更有效的算法，算法改进主要是为了达到 面几个目标： ( 1 ) 算法能够进一步适应m p 2 p 的高动态特征，即在节点发生变动时能够降 由此造成的损失，提高资源搜索过程的目标资源召回率。 ( 2 ) 算法能够降低资源查找过程中的流量负载，并进一步减少搜索延时。 为了达到预期的目标，本文对原来的算法进行了改进，而改进后的创新点主 要有4 个方面： ( 1 ) 候补节点的设置 算法在普通节点中设置一个性能仅次于超级节点的候补节点，该节点在超级 节点失效时能代替它而成为新一任超级节点，从而避免了超级节点失效造成下层 普通节点脱离网络的问题。 ( 2 ) 异类多群蚁群算法的引入 采用了异类多群蚁群算法，目前在将蚁群算法用到资源搜索方面的算法中， 都是采用每次只派出一个种群或是一类多群蚂蚁的方式来进行资源搜索。这样的 搜索算法要么就是陷入局部最优解困境中要么就是存在搜索速度慢的问题，为了 避免这些缺陷本文将异类多群蚁群算法应用到资源搜索当中，这种方式能够使搜 索过程既能达到全局最优又能提高算法的收敛速度。 ( 3 ) 移动a g e n t 遍历节点 使用移动a g e n t 来遍历网络节点，此时网络中节点以一种间接方式进行交互， 避免了由于节点间直接传送和反馈消息而浪费网络带宽的问题。除此之外，移动 a g e n t 的加入实现了资源搜索过程的异步性。 ( 4 ) “心跳感应 机制 为了进一步防止节点频繁失效造成的资源搜索延时过长的问题，本文设定了 “心跳感应 机制。该机制的主要思想是：每隔一个周期超级节点会向其所管理 的所有普通节点发送一条“心跳感应”消息，如在一定时间内收到节点反馈的消 m p 2 p 资源搜索算法研究 息则表明该节点目前属于稳定状态。否则，节点可能已经离网或者脱离该超级节 点管辖范围。 1 4 论文内容及组织结构 本论文的内容主要分文五章： 第l 章，绪论：该部分首先介绍论文所研究课题的背景以及研究意义，然后 描述了目前该研究方向的发展状况，针对研究的现状阐述了本论文研究的突破点 以及要实现的目标，最后是简洁的说明了论文的组织结构。 第2 章，m p 2 p 网络研究：本章主要对改进算法中涉及到的理论知识进行阐述。 m p 2 p 是在p 2 p 基础上发展起来的，因此在说明m p 2 p 概念前需要先对p 2 p 的相 关知识进行介绍( 包括p 2 p 定义、特点、网络架构类型以及几种典型的资源搜索算 法) 。在了解p 2 p 后再说明m p 2 p 的知识( 如m p 2 p 特点以及研究的技术方向等) ， 由于本文主要使用多种蚁群算法来改进资源搜索过程，所以在该部分的最后对蚁 群算法进行了详细的阐述。 第3 章，m p 2 p 资源搜索算法设计：本章是论文的核心部分，主要内容为改进 算法的基本思想、具体算法设计以及搜索机制。在本章最后还对论文的另一个改 进点节点失效处理过程，进行了描述。 第4 章，算法测试与结果分析：本章主要使用仿真工具m a t l a b 来验证算法 的有效性。可分为测试目标、测试环境、结果分析以及最后的总结四小节。 第5 章，总结与展望：本章对论文的所有研究工作和内容进行了总结，并对 以后需要进一步研究的问题进行了展望。 第2 章m p 2 p 网络研究 2 1 m p 2 p 网络综述 第2 章m p 2 p 网络研究 2 1 1传统p 2 p 网络 p 2 p ( p e e r - t o p e e r ) 是一种对等计算或对等网络，网络中每个终端都是一个对 等节点，节点间资源和服务的共享不需要依赖于传统的服务器而是直接连接进行 交互。所谓的“对等 就是指节点间地位的平等性，每个节点都扮演着服务器和 客户端两种角色，当其提供资源给其他节点时为服务器角色，而向网络请求资源 时则以客户端的身份存在。节点间共享的资源和服务包括：信息的共享与交换、 计算资源( 如c p u 的共享) 、存储资源( 如缓存和磁盘空间的使用) 等。 ( 1 ) p 2 p 特点 p 2 p 网络模型在互联网中得到了大范围的推广，很多我们现在使用的工具和软 件都是使用这个技术来实现的，而p 2 p 之所以能受到推崇很大程度上取决于它的 网络模型与传统c l i e n t s e r v e r ( c s ) 相比具有绝对的优势。图2 1 显示了两种模型结 构： c s 雕络模硬 图2 1c s 和p 2 p 网络模型对比 f i g 2 1t h ec o m p a r i s o no fc sa n dp 2 pn e t w o r k m p 2 p 资源搜索算法研究 在c s 模型中，所有的资源都存放在中央服务器中，客户的交互必须要通过 这个中央服务器，只有收到了中央服务器的答复后客户端才能得到资源从而对资 源进行相关操作，这样就会使中央服务器成为整个网络的瓶颈。该缺陷表现在三 个方面：第一，所有的资源都存放在中央服务器中，服务器负载过重，很容易崩 溃从而造成整个网络瘫痪；第二，由于中央服务器的处理能力是有限的，对每个 客户端所发送过来的请求很多时候不能给予及时的响应，网络资源的利用率低下。 第三，服务器集中存放着所有资源，这样很容易成为黑客攻击的目标。从图2 1 的 p 2 p 网络模型中我们可以看到整个网络结构不存在c s 中的中央处理器，所有的资 源都分散存储在各个对等节点中，各个节点问不用再通过中央服务器而是直接进 行交互。在p 2 p 中每个对等节点充当了两种角色：客户端和服务器，这样既避免 了中央服务器引起的网络瓶颈问题又能提高网络的资源利用率。 综合来看，p 2 p 网络的特点可以归纳为六个方面1 8 m 】： 非中心化( ( d e c e n t r a l i z a t i o n ) ：p 2 p 将资源分散在网络中的不同节点上，取代了 传统的中央服务器存储资源的方式，这种结构能够提高系统的安全性和健壮性。 可扩展性：在p 2 p 网络中，用户资源( 包括软件资源、硬件资源和信息资源) 都是可以直接共享的。当用户连接网络时，不仅仅是增加网络服务请求消息的流 量，更多的是扩充了整个网络的处理、存储以及服务的能力。网络中对等节点越 多系统的整体能力也越强，这说明了p 2 p 系统具有很好的扩展性。 健壮性：p 2 p 网络是一个自组织的网络，服务的分散性、节点的松耦合性以及 p 2 p 网络结构的自我调节能力都在很大程度上提高了p 2 p 网络的健壮性。比如， 某个节点的失效只是造成该节点上的资源搜索失败，而不会阻碍其他节点间的交 互或其他资源的搜索过程。 性能价格比高：性能优势是p 2 p 得到广泛应用的一个主要原因。个人电脑的 存储能力、处理能力以及所拥有的信息量都是有限的，很多大型计算无法在个人 电脑上运行，此时我们可以利用p 2 p 技术将网络上闲置的计算机资源结合起来处 理这些庞大的运算，只需要在计算完成后将结果反馈给最初的计算请求终端。这 样只要很低成本就能实现大规模项目。 第2 章m p 2 p 网络研究 ( 2 ) p 2 p 应用 由于p 2 p 技术既解决了传统集中式网络结构中服务器的瓶颈问题又有效的利 用了网络中各个终端的丰富资源，所以它被广泛用于各个领域中，包括对等计算 与协同处理、流媒体、共享存储、即时通信以及文件的共享等等。 主要的几个应用包括：n a p s t e r 、s k y p e 、p p l i v e 、s e t i h o m e 。 文件共享 通过p 2 p 技术，网络中的任意两台对等机之间都可以直接建立连接，下载自 己需要的文件资源。将p 2 p 用于文件共享的软件主要有：n a p s t e r 和g n u t e l l a 。 n a p s t e r 是一款音乐共享软件，这款软件就像是一个音乐搜索引擎。图2 2 为 n a p s t e r 模型结构图： 图2 2n a p s t e r 模型结构图 f i g 2 2n a p s t e rm o d e ls t r u c t u r e 从图2 2 中可以看出，整个模型分为两个部分：处于核心位置的中央目录索 引服务器和分布于各个地方的客户端。在中央目录索引服务器中保存了资源的目 录信息以及拥有这些资源的客户端地址，当某一个客户端想要共享资源时，它首 先向中央目录索引服务器发送一条请求消息，该信息中包含了目标资源的信息和 m p 2 p 资源搜索算法研究 保护模式下或以后台模式运行【1 6 1 。另外一个例子是北京大学网络实验室研发的 m a z e 系统，它是一个采用了混合结构化模型的对等计算机文件共享系统，这个系 统的节点可分为可控和分散两种。可控节点主要保存有系统核心的控制功能，而 分散节点则负责运行系统的计算等一般性功能。其中的控制节点能够获得系统运 行过程中所有环节的信息，这样就能够为进一步开展对等计算系统研究积累了宝 贵数据【1 刀。 ( 3 ) p 2 p 网络模型 传统p 2 p 网络模型分为集中目录式p 2 p 网络、分布式p 2 p 网络以及混合式p 2 p 网络三种【1 8 1 9 1 。 集中目录式网络模型 集中目录式网络模型是最早的p 2 p 应用模式。表现为星形结构，中央服务器 是网络的核心，网络中所有对等节点都与它相连，由于仍然具有c s 的中心化特 征因而也被看成是一种非纯粹的p 2 p 结构。中央服务器保存所有对等节点以及这 些节点中包含的资源信息，另外还提供一些安全检测服务。 节点l萤点2 节点3 1 ) 浚源汴册f 2 资源精求 3 ) 晌应4 ) 凌源 簟输 餐点4 图2 3 集中目录式网络模型 f i g 2 3c e n t r a l i z e dd i r e c t o r y - b a s e dn e t w o r km o d e l 第2 章m p 2 p 网络研究 在图2 3 显示的集中目录式网络模型图中节点4 在加入网 送含有本机地址、所拥有资源信息的注册消息，中央服务器接收注册消息后在目 录索引中生成一行新的目录便于其他终端对该资源的搜索。节点3 想要在网络中 查找自己想要的资源，首先给中央服务器发送请求，中央服务器根据请求中的资 源信息在目录中检索并将结果返回给请求终端，然后请求端直接与服务器响应消 息中的目的终端进行连接，进而实现数据传输。 集中目录式网络模型和传统c s 都是中心化结构，但是二者本质区别在于前 者中央服务器中保存的是资源目录，各个对等节点只是通过服务器找到资源所在 的对等节点信息，真正的资源是直接从目的对等节点获取。后者网络中的真正资 源就直接保存在服务器中，客户端不和其他客户端连接而直接从服务器取得。集 中目录式网络模型的优点是：可管理、维护简单和发现效率高。但其存在的缺陷 也很明显，存在着中心化结构共有的中央服务器瓶颈问题。 分布式网络模型 分布式网络模型也叫作纯p 2 p 网络模型，在该模型中所有的对等节点都是平 等地位没有中央服务器，节点本身就是客户端和服务器。在分布式网络中每个节 点都有自己的邻居列表，所有的操作都是在和邻居节点间交互完成。这样能够克 服集中目录式网络模型的中心化缺陷，具有很好的扩展性和容错能力。分布式网 络模型如图2 4 所示： 图2 4 分布式网络模型 f i g 2 4d i s t r i b u t e dn e t w o r km o d e l 1 2 m p 2 p 资源搜索算法研究 本机地址。服务器接收到该条请求消息后在自己所保存的目录索引中检索被请求 资源的信息，并将搜索结果返回给请求客户端。最后客户端根据反馈消息中显示 的目的地址来直接与目的客户端进行连接并传输文件。 从表面上看，n a p s t e r 模型和传统的c s 很相似，但两者的实质却完全不一样。 在c s 模型中服务器保存的是真正的资源，客户端资源的查找和传输都必须经过 服务器，这样当网络规模扩大时会使得整个文件的访问变慢。而在n a p s t e r 中目录 索引服务器只保存资源目录不是真正的资源，客户端只是通过服务器对资源进行 定位，文件的传输是直接与目的客户端连接而不通过服务器，这样能有效降低服 务器的负载，减少文件传输的延时。 但是中心化拓扑结构也不可避免地存在以下两个问题：中央目录索引服务 器的瘫痪容易导致整个网络的崩溃，因此可靠性和安全性较低；随着网络规模 的扩大，对中央索引服务器进行维护和更新的费用将急剧增加，所需成本较高【1 2 】。 即时通信 通信的实时性和清晰性是现在通信的一个衡量标准，不再依赖于中央服务器 的p 2 p 技术解决了中间服务器带来的网络带宽、传输延时的问题，使终端能够更 快的传输和更新数据。从信息安全方面考虑，p 2 p 即时通信系统中终端之间的交互 是直接点对点的，不需要通过服务器，这样就避免了服务器被攻击而泄漏通信信 息的危险。正因为融合了p 2 p 技术的即时通信系统具有这些优势才能发展的如此 迅速甚至对传统通讯模式造成了威胁。 融合了p 2 p 技术的即时通信软件有：s k y p e 、g t a l k 、q q 等，其中最具有代表 性的是s k y p e 软件，它通过网络上的带宽资源进行高质量的语音服务通信。s k y p e 是由著名的k a z a a 软件的创始人n i k l a s 推出的一款网络即时语音通信软件，它采 用半分布式网络拓扑结构【1 3 】。整个网络中存在三种类型的节点：负责用户登陆的 服务器、普通节点以及具有一定搜索和转发功能的超级节点( 本身也具有普通节点 的功能) 。s k y p e 软件工作原理如下：服务器给每个注册用户分配一对唯一的公钥 私钥；用户登陆时需通过服务器进行身份验证，服务器验证无误后给用户节点分 配一张能加入的超级节点列表，用户选择一个超级节点连接来加入网络；用户如 果想要和某个节 方连接进行对话 性、免费多方通 流媒体 娱乐性和交 高效利用、限制 d i s t r i b u t i o ns e r v 组播技术虽然能 控制等问题【1 5 1 。c d n 分发网络技术的成本很高，它主要是采用增加分散的服务器 节点，把终端服务请求发送到离终端最近的服务器上进行处理以降低流媒体对服 务器的负载压力和主要网络的带宽消耗。这种方式只是将服务器造成的瓶颈现象 转移到各个分散的服务器并不能从根本上解决问题