（计算机应用技术专业论文）p2p覆盖网与传感器网络路由协议研究.pdf

p 2 p 覆盖网与传感器网络路由协议研究 摘要 当前的p 2 p 网络呈现了一些不同于传统的分布式系统的特征，网络通常由数以千万 的结点构成且结点频繁地加入和离开使得系统极具动态性相应地，超级对等体( s p ) 的 概念被引入用来提高系统的性能一个超级对等体是p 2 p 网络中的一个结点，它作为系 统中客户结点的服务器且这些超节点之间的功能是逻辑对等的通过利用异质性，超结 点模式允许p 2 p 网络在不失分散特征的同时使系统的运行更加高效，而当前的相关构建 协议还存在诸如拓扑容易分片等问题 无线传感器网络( w s n s ) 是由部署在观测环境内的大量微型传感器节点通过无线通 信方式组成的一种无线网络高效地定位数据是未来无线传感器网络的一个基本应用 已知基于i n t e r n e tp 2 p 协议的分布式哈希表( d h t ) 对分布式的结点提供了近似最优的查 寻使用一个基于d h t 的网络协议来作为无线传感器网络的查询是一个有趣的研究课 题然而，这两种网络有各自不同的特点，如基于d h t 的协议通常可以独立与物理上的 网络拓扑，这对于能量受限的传感器网络是不适合的此外，在一个能量约束的无线传 感器网络，特别是大规模的无线传感器网络中。维护所有节点对之间的路由信息的代价 足非常昂贵的因此，一个一般的基于d h t 的i n t e r n e t 协议到w s n s 的直接映射非常困 难，需要相应的机制予以克服 在无线传感器网络路由设计问题上，充分考虑有限的网络能量，最大化延长网络寿 命非常关键分簇提供了一个很好的延长网络寿命的机制基于分簇的层次式路由方法 在提高网络的可扩展性方面也特别有效在以分簇方式组织的传感器网络中，传感器节 点的角色分为簇首和簇成员两种簇首作为簇的中心负责簇结构的建立，收集簇成员的 数据，经融合处理后发送给基站( b s ) 其路由分为簇内通信和簇问通信两部分当簇成 员与簇首之间传输数据时，可以采用单跳通信方式，这样易于调度各成员的数据传输当 簇首向汇点进行长距离数据传输时，已有研究表明采取多跳的方式更有利于节约能量 对于分簇技术，可以选择具有更多剩余能量的簇首及周期地旋转簇首来平衡节点能量的 消耗，从而达到延长整个网络寿命的目的此外还存在考虑利用基站能量的策略，即尽 可能让能量近似无限的基站进行广播、路由路径选择和提供维护工作等等让传感节点 仅履行诸如传感、转发数据等基本任务，从而节省网络节点的能量 本文主要研究了p 2 p 覆盖网和传感器网络路由协议的相关问题，并得到了一些结 果第一章的绪论简要介绍了研究背景，问题的提出和相关工作，给出本文所做的主要 工作和论文的组织结构第二章介绍了一种非结构化的超级对等体覆盖网e r a s p 在第 三章中探索了大规模无线传感器网络中使用双层c h o r d 完成高效查询的相关机制第四 章针对无线传感器网络提出的一个能量高效的多跳路由协议e e m r 第五章总结全文， 并对下一步的研究提出了设想 关键词：p 2 p ，覆盖网，无线传感器网络，分簇，多跳路由，网络寿命 p 2 p 覆盖网与传感器网络路由协议研究 _ _ _ _ _ - - _ _ _ - - _ _ _ - - - _ - _ _ _ - - - - - _ _ _ - _ _ _ 一l 11 _ _ _ _ _ _ _ _ - _ - _ _ - _ _ _ - _ - _ - - - _ _ - _ - _ _ _ _ _ _ - _ - - _ - _ _ _ _ _ _ - - - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - a b s tr a c t m o d e r np e e r t o - p e e r ( p 2 p ) n e t w o r k sp r e s e n ts e v e r a lu n i q u ea s p e c t st h a td i s t i n g u i s h t h e mf r o mt r a d i t i o n a ld i s t r i b u t e d s y s t e m s n e t w o r k sc o m p r i s i n gh u n d r e do ft h o u s a n do re v e n m i l l i o n so fp e e r sa r en o tu n c o m m o n a sac o n s e q u e n c eo fs u c hs c a l e ，t h e ya r ec h a r a c t e r i z e d b ye x t , r e l n ed y n a m i s m ，w i t hac o n t i n u o u sf l o wo fn o d e sj o i n i n go rl e a v i n gt h en e t w o r k t h e c o n c e p to fs u p e r p e e r ( s p ) h a sb e e ni n t r o d u c e dt oi m p r o v et h ep e r f o r m a n c eo fp o p u l a rf i l e s h a r i n ga p p l i c a t i o n s as u p e r p e e ri san o d ei nap 2 pn e t w o r kt h a to p e r a t e sa sas e r v e rf o ra s e to fc l i e n t s ，a n da sa ne q u a lw i t hr e g a r dt oo t h e rs u p e r p e e r s b ye x p l o i t i n gh e t e r o g e n e i t y th ( s u p c r p c c rp a r a d i g ma l l o w sp 2 pn e t w o r k s t or u nm o r ee f f i c i e n t l y w i t h o u tc o m p r o m i s i n g t h e i rd e c e n t r a l i z e dn a t u r e h o w e v e r ，t h ec u r r e n tc o n s t r u c t i n gp r o t o c o l sa r ei n e f f i c i e n t aw i r e l e s ss e n s o rn e t w o r k ( w s n ) i sac o l l e c t i o no fw i r e l e s ss e n s o rn o d e sf o r m i n ga t e m p o r a r yn e t w o r kw i t h o u tt h ea i do fa n ye s t a b l i s h e di n f r a s t r u c t u r eo rc e n t r a l i z e da d m i n i s t r a t i o n e f f i c i e n t l yl o c a t ed a t ai saf u n d a n m n t a lp r o b l e mf o rf u t u r ea p p l i c a t i o n so fw i r e l e s s s e n s o rn e t w o r k i ti sk n o w nt h a td i s t r i b u t e dh a s ht a b l e ( d h t ) b a s e di n t e r n e tp 2 pp r o t o c o l sp r o v i d en e a r - o p t i m u md a t al o o k u pt i m e sf o rq u e r i e sm a d eo nn e t w o r k so fd i s t r i b u t e d n o d e s u s i n gad h t b a s e dn e t w o r kp r o t o c o lt os e r v eq u e r i e si nw s n sb e c o m e sa ni m p o r t a n t p r o b l e mt os t u d y h o w e v e r ，ag e n e r i cm a p p i n go fd h tb a s e di n t e r n e tp r o t o c o l st ow s n s i sc o n s i d e r e dd i f f i c u l ta st h e s ep r o t o c o l st y p i c a l l yi n t e r c o n n e c tn o d e si n d e p e n d e n t l yo ft h e i r p r o x i m i t yi nt h ep h y s i c a ln e t w o r kt o p o l o g yw h i c hi sn o ts u i t a b l ef o re n e r g y c o n s t r a i n e ds e n s o r n e t w o r k sa sn e i g h b o r si nt h ed h t l o g i c a li d e n t i f i e rs p a c em a ya c t u a l l yb ef a ra p a r ta n de a c h l o g i c a lh o pw i t h i nad h tm a yc o s te n e r g yo fm a n yp a c k e tt r a n s m i s s i o n s f u r t h e r m o r e ，i n th ee n e r g y c o n s t r a i n e dw s n se n v i r o n m e n t s ，p a r t i c u l a r l yi nl a r g es c a l ew s n s ，m a i n t a i n i n g r o u t i n gi n f o r m a t i o na m o n ga l lp a i r so fn o d e sb e c o m e se x p e n s i v e o n ei m p o r t a n ti s s u ew h e nd e s i g n i n gw s ni st h er o u t i n gp r o t o c o lt h a tm a k e st h eb e s t u s eo ft h es e v e r e l yl i m i t e dr e s o u r c ep r e s e n t e db yw s n ，e s p e c i a l l yt h ee n e r g yl i n f i t a t i o n c l u s t e r i n gp r o v i d e sa ne 仃e c t i v ew a yf o rp r o l o n gi n gt i l el i f e t i m eo faw i r e l e s ss e n s o rn e t 一 彤o r k 。c u r r e n tc l u s t e r i n ga l g o r i t h m su s u a l l yu t i l i z et w ot e c h n i q u e s ? s e l e c t i n gc l u s t e rh e a d s l f7 i t hm o r er e s i d u a le n e r g ya n dr o t a t i n gc l u s t e rh e a d sp e r i o d i c a l l y , t od i s t r i b u t et h ee n e r g y c o n s u m p t i o na m o n gn o d e si ne a c hc l u s t e ra n de x t e n dt h en e t w o r kl i f e t i m e i na d d i t o n ， t h e r ei st h es t r a t e g yt om a k eu s eo ft h ee n e r g yo fb a s es t a t i o n ( b s ) a ss o o na sp o s s i b l e t h a ti s ，b sd o e se v e r y t h i n g ，f r o mb r o a d c a s t i n gc o n t r o lp a c k e t s ，r o u t i n gp a t h ss e l e c t i o na n d m a i n t e n a n c e s e n s o rn o d e sa r eo n l yr e s p o n s i b l ef o rb a s i cf u n c t i o n s ，s u c ha ss e n s i n gd a t a ， f o l w a r d i n gp a c k e t so nb e h a l fo fo t h e rn o d e sa n ds e n d i n gs e n s i n gd a t at ob s t h i st h e s i sm a i n l yi sd i v i d e di n t of i v ec h a p t e r s i nt i l ef i r s tc h a p t e rw ei l l u m i n a t eb a c k p 2 p 覆盖网与传感器网络路由协议研究 g r o u n do fo u rs t u d ya n dp u tf o r w a r do ft h ep r o b l e m s ，t h ew o r kw ed oa n dt h es t r u c t u r eo f th ct h c i s t i l es e c o n dc h a p t e rw ep r o p o s ea l le f f i c i e n ta n dr o b u s ta d a p t i v es u p e r p e e rp 2 p o v e r l a yn e t w o r ke r a s p an o v e lt w o - t i e rc h o r db a s e dn e t w o r kp r o t o c o lf o rs e r v i n ge f f i c i e n t q u e r i e si nw i r e l e s ss e n s o rn e t w o r k s ( c 2 w s n ) i sp r o p o s e di nt h et h i r dc h a p t e r i nt h ef o u r t h c h a p t e rw ep r o p o s ea l le n e r g y - e f f i c i e n tm u l t i - h o pr o u t i n gp r o t o c o lf o rw i r e l e s ss e n s o rn e t w o r k s ( e e m r ) t i l ef i f t hd l a p t e rm a i n l yp r e s e n t st h ef u t u r ew o r k k e yw o r d s ：p e e r t o - p e e r ，o v e r l a yn e t w o r k ，w i r e l e s ss e n s o rn e t w o r k s ，c l u s t e r i n g ，m u l t i h o pr o u t i n g ，n e t w o r kl i f e t i m e u l 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士酣论文( ( p 2 p 覆盖 网与传感器网络路由协议研究，是本人在导师指导下，在曲阜师范 大学攻读博士口硕士d 学位期间独立进行研究工作所取得的成果。 论文中除注明部分外不包含他人已经发表或撰写的研究成果。对本文 的研究工作做出重要贡献的个人和集体，均己在文中已明确的方式注 明。本声明的法律结果将完全由本人承担。 作者签名：川；孳 日期：加衅，斗可 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) ( ( p 2 p 覆盖网与传感器网络路由协议研究系本人在曲阜师范大学攻 读博士口硕士口学位期间，在导师指导下完成的博士口硕士口学 位论文。本论文的研究成果归曲阜师范大学所有，本论文的研究内容 不得以其他单位的名义发表。本人完全了解曲阜师范大学关于保存、 使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件 和电子版本，允许论文被查阅和借阅。本人授权曲阜师范大学，可以 采用影印或其他复制手段保存论文，可以公开发表论文的全部或部分 内容。 作者签名： ；i 孓孳 日期：力够母矿 导师签名：滔名蔷溺日期：h 鹋- u 1 p 2 p 覆盖网与传感器网络路由协议研究 1 1 研究背景和问题的提出 1 1 1p 2 p 覆盖网 第一章绪论 随着对等网络规模的逐渐增大和应用的不断推广，当网络规模达到某个数量级或对 等结点的请求速率达到某个值时，整个网络处理请求的能力将急剧下降甚至瘫痪【1 】 由于对等网络结点的异构性，低带宽结点带宽瓶颈已经成为影响无结构对等网络处理请 求能力的一个主要因素为了解决这个问题，很多无结构对等系统的覆盖网拓扑开始采 用超结点结构，如k a z a a 【2 1 ，m o r p h e u s 【3 1 等 传统超结点结构利用高带宽的超结点代替低带宽结点处理定位请求消息，解决了低 带宽结点带宽瓶颈问题。但其目前的构建协议十分低效，降低了超结点对等网络定位文 件的效率每个加入结点没有根据实际网络需求决定自己的身份和邻居集合，产生了大 量不必要的超结点和无遮蔽叶结点，其中无遮蔽叶结点是找不到超结点的叶结点，它们 必须自己亲自处理文件请求同时失去超结点的叶结点无法共享和定位文件，即传统的 超结点结构还存在鲁棒性相对较弱的问题 为了提高超结点对等网络的构建效率，p y u n 等人利用e r 模型来建立度数平衡的 低直径的随机超结点拓扑【4 1 但是，这种方法需要利用广播来估计网络规模的大小，因 而开销较大m o n t r e s o r 通过不断用较大容量结点替换较小容量结点来达到一个最小的 超结点集合【5 】，但是，这种方法会导致叶结点所属超结点频繁变动，产生大量文件索引 信息流为了提高超结点对等网络的鲁棒性，g n u t e l l a0 6 【6 】协议规定每个叶结点可以 同时属于d 个不同的超结点，但每个叶结点必须把自己的文件索引传送给超结点，这样 会增加网络流量，且占用超结点的有效带宽，使得超结点数目增加，因此d 值必须很小 ( 最大不超过4 ) m o n t r e s o r 利用g o s s i p 协议动态维持一个底层拓扑来构建和维护超 结点对等网络，产生较大开销更重要的是，这些方法都不能保证失去超结点的叶结点 进行文件请求在这些工作的基础上产生了第二章的研究内容，即构建一个高效和鲁棒 的超级对等体覆盖网 1 1 2 无线传感器网络中基于d h t 的查询 无线传感器网络( w s n s ) 是当今国内外备受关注的，由多学科高度交叉的新兴前沿 研究领域传感器网络是由部署在观测环境内的大量微型传感器节点通过无线通信方式 组成的一种无线网络组成传感器网络的节点一般包括数据基站、汇聚节点和传感器节 点在过去的很长一段时间里。对无线传感器网络的研究主要关注数据的收集【7 ，8 1 该 p 2 p 覆盖网与传感器网络路由协议研究 研究领域中通常假定以固定的频率报告兴趣数据，这些传感器本身并不存储数据这样 假定的一个缺点是用户不能根据需要随时改变系统的行为，而且如果来自于用户的查询 不足足够的频繁则相当大的能量被浪费用于传感不必要的数据传感器仅在用户查询时 而非以固定的频度向用户报告数据就使得系统的使用更加能量高效 当前的无线传感器网络的组网研究进入了一个以终端用户既消耗数据同时也提供数 据为标志的新时代【9 ，1 0 】。在这样的应用中用户通常需要在传感器网络内部搜索需求数 据同时i n t e r n e t 规模的p 2 p 设计是一个活跃的研究领域当前的主流p 2 p 技术使用 基于分布式哈希表d h t 的结构化的覆盖网，如p a s t r y 【1 1 】，c h o r d 【1 2 】和内容可寻址网 ( c a n ) 【1 3 】尽管w s n s 和p 2 p 研究的范畴有了一定的交叉，但是它们基本上还是相对 孤立的研究领域因此使用一个基于d h t 的网络协议作为高效查询的基础设施变为一 个值得注意的问题，这是本文第三章关注的问题 1 1 3 无线传感器网络路由协议 与传统的网络不同的是w s n s 中传感器节点通常足由能量十分有限的电池供电，而 且在部署后难以二次补充能量，因此传感器网络存在严重的能量约束问题所以，传感器 网络的能量资源必须被很好地管理通常能量的消耗来自于三个部分：传感、通信和数 据处理在这三者之中数据通信对一个节点的能量耗费最为显著关于w s n s 应用的一 个主要关注点就是设计开发能够平衡能量消耗的高效路由协议，使得网络的寿命得以延 长文献中提出的许多协议最小化路由路径上的能量消耗，这些方法增加了能量效率， 但当路径中的某个节点作为热点时效果不够理想 分簇提供了使用无线传感器网络的一个高效的方式f 1 4 ，1 5 ，1 6 ，1 7 】借助于分簇， 一个热点在固定的时间间隔后便会失去热度( 因为不再担负簇首任务) 当网络划分为 簇后，数据传输被分为两个阶段；簇内和簇间的数据传输非簇首节点首先发送数据给 簇首，然后簇首又将数据发送给基站h e i n z e l m a n 等1 1 4 】首次提出了一个用于周期性 数据收集应用的称为l e a c h 的分簇算法来延长传感器网络的寿命l e a c h 使用随机 簇首旋转来平衡网络内结点能量的消耗，在数据传输阶段每个簇首直接将数据转发给基 站在文献【1 5 】中作者使用了一个与l e a c h 类似的随机分簇，并且使用多跳路由的方 式将数据传给基站因为基站通常位于距离传感区域较远的距离，以前的研究( 如( 1 8 1 ) 指出簇间的多跳路由更加高效h e e df 1 9 】引入了一个用来定义传输功率的簇半径的变 量每个节点变为候选簇首的概率依赖结点剩余能量，而最终簇首依赖簇内的通信代价 选举h e e d 在确定数目的迭代后结束且完成网络内相对均匀的簇首分布e e c s ( 2 0 i 引入了一个无需消息交换迭代的簇首竞选算法通过选择具有更多剩余能量的簇首和大 小非均匀的簇使得距离基站较远的簇首具有更小的簇规模。因而可以预留能量用于到基 站的数据转发 当前许多协议存在的另一个可能的问题是寻找到的最低能量路由担负了从源到目的 2 p 2 p 覆盖网与传感器网络路由协议研究 点的所有通信传输这不可避免地导致该路径上节点能量的消耗更为迅速，从而导致网 络的分割为了解决这个问题，【2 1 】探索尽可能使用基站的能量履行寻找最优路径，更 新可用路径等任务，收到了较好的效果对于无线传感器网络的路由问题将在本文第四 章中给出我们的一些结论，包括分布式的分簇、进一步探索基站在最优通信路径中的作 用等在问题的解决过程中，我们通常借助图论中的一些模型，因为路由选择问题本质 上是图论中的问题 1 2 论文研究内容和组织结构 论文第一章的绪论中简要介绍了本文的研究背景、问题的提出和相关工作，给出本 文所做的主要工作和论文的组织结构 第二章提出了一种高效和鲁棒的非结构化的超级对等体覆盖网e r a s p ，e r a s p 在构建和维护网络时充分考虑网络中结点的容量和在线时间等参数，并加强了普通结点 到超结点之间的连接使用p e e r s i m 的仿真结论验证了该新型的覆盖网协议具有高效性 和鲁棒性 第三章提出了将基于双层c h o r d 的p 2 p 覆盖网用于传感器网络高效查询的基础设 施( c 2 w s n ) 对于数据查询c 2 w s n 拥有o ( 1 0 9m + l o ga i ) 的边界时时，此处的m 和 a i 分别为网络内簇的数目和单个簇内的最大节点数目另外，c 2 w s n 中提出的动态簇 头旋转机制有利于平衡网络能量的消耗，因而可以显著增加传感器网络的寿命 第四章提出了一种针对传感器网络的多跳路由协议e e m r ，该协议的特点是分布式 的节点分簇和由基站发起的最优路径查找分簇机制中那些距离基站近的簇头通常具有 更小的簇规模，因而可以预留能量用于簇间的数据转发对于簇间的数据通信我们的策 略足尽量使用基站的能量，从而使得传感节点的能量得到最大化的保存网络仿真表明 e e m r 比当前存在的一些类似协议如h e e d 性能有了显著提高 第五章对全文进行了简要的总结，并对下一步的研究提出了设想 3 p 2 p 覆盖网与传感器网络路由协议研究 第二章e r a s p ：一种高效和鲁棒的超级对等体覆盖网 超级对等体( s p ) 的概念被广泛引入用来提高文件共享系统应用的性能，但目前超 结点对等网络的构建协议效率较低且网络拓扑的鲁棒性较弱，本章提出一种自适应的超 结点对等体网络的构建算法( 记为e r a s p ) 它基于n e w s c a s t n 协议。考虑结点的容 量和在线时间等参数，并加强了叶结点到超结点之间的连接，本协议可以快速地从初始 拓扑自动演化为最优的目标拓扑网络仿真表明采用e r a s p 构建p 2 p 叠加网络的方案 具有高效性和鲁棒性 2 1 背景知识 随着p 2 p 技术的成熟及其应用的推广，当前的对等网络规模不断增大，由数以万计 的对等体结点构成的网络变得十分普通另一方面，由于p 2 p 网络中对等体结点的频繁 加入和离开系统所引起的波动，使p 2 p 网络极具动态性这些都无疑给系统开发者带来 了挑战：需要维护一个动态变化的叠加网拓扑且实现完全分散化的控制换句话说，选 择、构建和维护一个恰当的拓扑对于一个高效鲁榜的p 2 p 系统的实现具有重要的意义 文献 2 2 ，2 3 ，2 4 】描述了许多典型的p 2 p 覆盖网结构在稍早的工作中我们提出了一 些新奇的p 2 p 覆盖网系统【2 5 ，2 6 ，2 7 1 另外一个较为普遍的应用是当前的许多p 2 p 应 用引入了超结点( s u p e rp e e r s ，记为s p ) 的概念一个超结点是p 2 p 系统中作为客户结 点服务器，同时超结点之间功能对等的结点这样拓扑被组织为分层的结构f 2 8 ，2 9 】 相对一般的结点( c o m m o np e e r s ，记为c p ) ，那些具有更强的处理能力，更长的在线时 问，更高的可信赖性的结点担负类似于服务器的角色，为普通结点提供服务这种由s p 和c p 组成的两层模式充分利用了网络结点的异质性，使系统效率得到显著提升：一个 面，它摒弃了c s 模式的单点失败；另一方面，它利用纯p 2 p 模式的某些优点将网络中 的业务流量分散开来 传统的双层结构利用高带宽的超结点代替低带宽结点处理定位请求消息，解决了低 带宽结点带宽瓶颈问题，但是总的说来目前的构建协议还处在十分低效的水平，如在文 件共享系统中其结果表现为降低了超结点对等网络定位文件的效率每个加入结点没有 根据实际网络需求决定自己的身份和邻居集合，产生大量不必要的超结点和无遮蔽叶结 点，其中无遮蔽叶结点是找不到超结点的叶结点，必须自己亲自处理文件请求；同时失 去超结点的叶结点无法共享和定位文件，即传统的超结点结构还存在鲁棒性弱的问题 然而，构建和维护这样的一个双层拓扑并不简单p 2 p 系统所固有的众多特性要求有一 个高效且鲁棒的协议提供支持，在面对网络中结点的加入、离开，尤其足不可预知的结 点崩溃时，该协议能够对构建的双层拓扑有良好的自组织和自修复能力 4 p 2 p 覆盖网与传感器网络路由协议研究 2 2e r a s p 详述 为了表示上的方便首先给出本章用到的一些符号令磁为结点网络中的一个对 等体每个对等体啦依据协议动态地决定自身角色，超结点表示为s p ，普通的客户结 点表示为c p 在该系统中令每个超级对等体维护两个邻居集：客户对等体集合g 印( 啦) 和超级对等体集g 。p ( 啦) 为了将能够作为超级对等体的的结点从普通结点区分开来， 我们对死i 关联一个表示结点容量的参数c n ；，它表示结点孤所能处理的普通客户对等 体的数目为了使结果拓扑更具鲁棒性，我们要求每个客户对等体维护一个规模为d 的 超级对等体集合出于降低系统波动考虑，引入了参数t n ，来表示结点啦的在线时间因 子此外，令s 表示候选的超级对等体集合，令l o a d , ，表示结点m 的实际负载此处假 定每个对等体知道自身的容量和在线时间参数在一个实际的实现中，这些值可以通过 在线的测量计算出来 构建的分层覆盖网络拓扑可以刻画如下：网络中的每个结点分配两个互斥的角色 ( s p 或c p ) 这里值得注意的是角色的分配不是永久不变的，在协议演化之初每个结点 的角色都是超结点s p ，而随着演化的进行大多结点迅速变为在超结点覆盖下的普通客 户结点c p 协议演化的一个目标是超结点的数目应当尽量小且能够覆盖所有的普通结 点最后形成的目标拓扑的链接关系为超结点被链接到随机采样的其他超结点和它所负 责的普通结点，而普通结点仅链接到负责它的d 个超结点图2 2 1 是对获得的结果拓 扑的抽象，细的连续线代表“客户超级对等体，关系，粗线代表s p 之间的连接点线 代表“候选客户一超级对等体，关系。它用来增加系统的鲁棒性 图2 2 一l 超级对等体拓扑 我们的目标是基于结点容量和在线时间的度量产生由最少数目超结点刻画的一个尽 可能高效和鲁棒的拓扑显然，为了达到这一效果，具有更高容量和具有更长的在线时 间的结点是超结点的更好的候选者每一次，目标拓扑由总容量能够覆盖所有作为普通 结点的最小结点集构成，且这些超结点通常具有更长的在线时间换句话说，容量保证 了超结点的数目尽可能少，在线时间量度保证超结点尽可能降低系统的波动，使得花费 较小的代价就可以维护目标拓扑 5 p 2 p 覆盖网与传感器网络路由协议研究 2 2 1 潜在拓扑 我们选择n e w s c a s t 协议来维护一个我们潜在的近似随机拓扑【3 0 i 在n e w s c a s t 中，一个对等体的状态被称为局部视图( p a r t i a lv i e w ) ，它由固定大小的对等体描 述符的集合构成一个对等体描述符包含该对等体的地址，标识描述符被创建的逻辑时 间戳一个局部视图的规模为8 算法2 2 一l 显示了一个基于g o s s i p 模式的算法框架其中方法r a n d o m p e e r 返回 一个在局部视图中随机选择的地址方法u p d a t e 合并一次交换中涉及的两个对等体 的局部视图且保持s 个最新的描述符。因而可以创建一个新的局部视图 ( a ) a c t i v et h r e a d w a i t ( jt i m eu n i t s ) ； q 一r a n d o m p e e r 0 ； s e n d s t a t e ( q ) ； s q 卜r e c e i v e ( q ) ； ( b ) p a s s i v et h r e a d 8 q 卜r e c e i v e ( q ) ； ，r e t u r n s t a t e ( q ) ； u p d a t e ( s q ，s e n d e r ( s q ) ) ； 当一个对等体通过s e n d s t a t e 和r e t u r n s t a t e 发送它的局部视图给另一个对 等体时，新的信息进入系统在该步中，对等体总是将它自己的新创建的描述符插入到 局部视图中旧的信息逐渐自动地从系统中移除并被新的信息所取代该特性允许协议 通过忘记失效的对等体来修复覆盖拓扑所得的结果拓扑具有几个不错的特性 3 0 i ：它 具有一个很低的直径且接近一个具有出度为8 的随机图按照试验结论，选取8 = 2 0 来 获取一个稳定和鲁棒的连通性是足够的 2 2 2 选择客户和超级对等体 为了构建一个具有所有特性的拓扑，我们提出了一个基于著名的g o s s i p 模式的的机 制f 3 0 诸如标识符、容量、在线时间、当前角色和参与对等体的邻居关系等的拓扑信 息通过周期的g o s s i p 消息在随机选择的两个对等体之间扩散基于收到的消息，对等体 6 p 2 p 覆盖网与传感器网络路由协议研究 更新它们的邻居以获取一个目标拓扑的更好的接近 算法2 2 - 2 自适应的分布式演化算法框架符号：p 是本地对等体， q 和r 为远程对等体标识符 1 ： g n u l l ； 2 ： s 卜 ri su n d e r l o a d e dac r 勺at ，知) ； 3 ： w h i l e ( s ! = n u l laq = = n u l l ) 4 ： r 卜r a n d o m ( s ) ； 5 ： s 卜g ，i ； 6 ： i f ( 1 0 a d ， c ra ( c p l o a d p ) ) 7 ： q 卜r ： 8 ： i f ( pi ss p ) 9 ： i f ( q ! = n u l l ) 1 0 ： 1 1 ： 1 2 ：e l s e 1 3 ： 1 4 ：e l s e 1 5 ： i f ( q ! = n u l l ) 1 6 ： 1 7 ：e l s e 1 8 ： 构建协议的算法框架如2 2 2 所示，算法的原理如下；所有的超结点都试图将普通 结点推向具有更大容量和更长在线时问且愿意接收更多负载的结点为达此目的，在2 7 行算法在未饱和的且其容量和在线时间更优的那些超节点中进行随机选择从算法的第 8 行每个对等体判断自身的角色( s p 或c p ) 如果当前的对等体p 为s p 角色且选择的 超级对等体q 不空。则p 试图将其所有的客户传递给选择的超级对等体q 而其自身变为 e f 的一个客户如果q 是空的则不做任何工作在第1 5 行，如果p 的角色是客户c p 且 选择的超级对等体q 不空，则p 变为g 的一个客户在第1 7 行，一个不能加入任何超级 对等体的客户自己变为s p 注意该算法仅由更具威力的超结点执行因为它们可以更容易地负担协议花费的代 价显然，一个加入结点要么寻找一个愿意接受它的s p ，要么声明自己作为超结点并 参加到选择协议中看其是否与该角色相称在协议的演化过程中，所有的超结点持续尝 7 p 2 p 覆盖网与传感器网络路由协议研究 试发现具有更大容量且没有被完全利用的结点，直到未饱和的结点集变为空集或达到最 小可见如果没有失败发生，该机制最终产生了想要的目标拓扑 选择的结果是每个客户对等体被连接到它的超级对等体上注意容量和在线时间参 数可能并不一致我们可以在所设定的在线时间阈值内选择更具威力的对等体当具有 相同的容量和相同的在线时间的情况，协议选择具有更多客户的那格结点作为超级对等 体，如果这三个参数均相等可以随机选择 2 2 3 连通性增强 为了增加协议的鲁棒性，从客户对等体到超级对等体的连通性被增强，即每个客户 维护d 个超级对等体令m 为一个客户对等体，则m 在不同的情况下维护不同的对等 体集合 - 如果g 印( n ) 非空且i g 印( 毗) i d ，从超结点集合g 印( 啦) 中选择d 个具有最大容量 和最长在线时间的的超级对等体 如果g 印( 啦) 非空且i g 印( 啦) i o芒。乏oz p 2 p 覆盖网与传感器网络路由协议研究 0 6 和文献【8 】做一个简单的比较为了计算总的网络开销，我们收集不同的网络规模下 所有的对等体与其邻居之间的消息量图2 3 _ 5 给出了总的开销比较我们发现随着网络 规模的增加e r a s p 构建s p 拓扑的开销远小于g n u t e l l a0 6 和文献【8 】的类似的开销 原因在于e r a s p 选择具有更长的在线时间和具有更好的容量的对等体，这导致了更小 的不必要的网络流量 1 2 p 2 p 覆盖网与传感器网络路由协议研究 第三章c 2 w s n ：大规模无线传感器网络中的双层c h o r d 查询机制 高效地定位数据是未来传感器网络应用的一个基本问题已知基于d h t 的p 2 p 协 议对分布式的节点提供了近似最优的查询时间本章探索了将一种基于双层c h o r d 的 p 2 p 网络协议用作传感器网络高效的查询的基础设施( 记为c 2 w s n ) 对于数据查询 c 2 、7 s n 拥有o ( 1 0 9 m + l o g 凡) 的边界时间。此处的m 和入i 分别为网络内簇的数目和 单个簇内的最大节点数目此外，在c 2 w s n 中呈现了一个动态的簇首选择机制，该机 制甲衡了网络能量的消耗因而可以增加传感器网络的寿命 3 1 无线传感器网络中的p 2 p 观念 3 1 1 无线传感器网络特征 无线传感器网络最早来源于美国军方，是一种由大量具有特定功能的传感器节点通 过自组织的无线方式通信，相互传递信息，协同地完成特定功能的智能专用网络它综 合了传感器技术、嵌入式计算技术、通信技术、分布式信息处理技术、微电子制造技术和 软件编程技术等，可以实时监测，感知和采集网络所监控区域内的各种环境或监测对象 的信息，并对收到的信息进行处理后传送给终端用户无线传感器网络在工业、农业、交 通，军事、安全、医疗、空间探索，以及家庭和办公环境等众多领域都有着广泛的应用。 无线传感器网络是一种智能网络，它具有传统网络所不具备的独特之处，正是由于 这些特点，使得无线传感器网络在具有其自身优势的同时也存在很多需要解决的问题， 这不论足对于研究者来说，还是对无线传感器网络的应用来说，都具有很大的挑战性 无线传感器网络的主要特点可以总结如下f 3 2 】 ( 1 ) 传感器节点数目大，密度高，采用空间位置寻址在一个无线传感器网络中，为 了保证网络的可用性和生存能力，可能有成千上万的的节点，从而节点的密度很高正足 由于传感器节点的数目巨大，而且网络中一般不支持任意两个节点之间的点对点通信， 以及每个节点不存在唯一的标识，因而在进行数据的传输过程中采用空间位置寻址 ( 2 ) 传感器节点的能量、计算能力和存储容量有限随着传感器结点的微型化，在设 计中大部分结点的能量靠电池提供。其能量有限，而且由于条件限制，难以在使用过程 中给节点更换电池，所以传感器节点的能量限制足整个无线传感器设计的瓶颈，它直接 决定了网络的工作寿命；另一方面。传感器节点的计算能力和存储能力都较低，使得其 不能进行复杂的计算和数据存储 ( 3 ) 无线传感器网络的拓扑结构易变化，具有自组织能力由于无线传感器网络中节 点的节能的需要，传感器节点可以在工作和睡眠状态之间切换，传感器节点随时都可能 1 3 p 2 p 覆盖网与传感器网络路由协议研究 由于发生故障而失效，或者添加新的传感器节点到网络中，这些情况的发生使得无线传 感器网络的拓扑在使用中很容易发生变化 ( 4 ) 传感器节点具有数据融合能力在无线传感器网络中，由于传感器节点数目大， 很多节点会采集到具有相同类型的数据，因而通常要求其中的一些节点具有数据融合能 力，能对来自多个节点采集的数据进行融合，然后将融合后的数据送给信息中心数据 融合可以减少冗余数据，从而可以减少在传送数据的过程中的能量消耗，进而延长网络 的寿命 此外，无线传感器网络是a d h o c 网络的一种典型应用，虽然它具有无线网络自组织 特征，但与传统的无线自组织网络相比，又有一些不同之处，它们之间的主要区别有以 下几点【3 2 1 在网络规模方面，无线传感器网络包含的节点一般比a d h o c 网络高几个数量级 在分布密度方面，无线传感器网络节点的分布密度更大 由于能量限制和环境因素，无线传感器网络节点容易损坏易出故障 由于节点的移动和损坏，无线传感器网络的拓扑结构频繁变化 在通信方式方面，无线传感器网络节点主要使用广播通信。而a d h o c 节点采用点对 点通信 无线传感器网络节点的能量、计算能力和存储能力受限 由于无线传感器网络节点数量的原因，节点没有统一标识 无线传感器网络通常以数据为中心 图3 1 1 分簇的无线传感器网络系统结构 图3 卜1 显示了一个分簇的无线传感器网络的系统结构具有射频功能的传感器节 点分布于无线传感器网络的各个部分，负责对