（计算机应用技术专业论文）基于网络编码的传感器网络概率路由协议分析研究.pdf

硕十论文基于网络编码的传感器网络概率路由协议分析研究 摘要 传统的路由协议中，路由节点只对数据包寻径转发，网络编码允许节点对数据进行 编码操作，然后寻径转发，具有提高网络吞吐量、节省带宽资源、平衡链路负载等优 点。由于传感器网络具有对等和节点资源受限的特性，传统路由协议不适用于该网络。 概率路由因其具有可选择的信息转发、很强的容错性以及无需了解全部网络拓扑信息等 特点，非常适用于无线传感器网络。 本文用网络编码技术分析概率路由协议，对基于复制的概率路由协议和基于网络编 码的概率路由协议进行了定量分析，并在概率路由协议的基础上，结合网络编码技术， 同时参照扩散和等待路由协议中数据包直接传输和网络中数据包拥有单一拷贝的思想， 以保持网络编码优势的同时又能减少网络的冗余度为目标，提出一种基于网络编码的扩 展概率路由协议( e x p r - n c ) ，该协议中所有路由节点直接传输数据包，不拷贝数据包 进行转发，并且为每个节点建立一个已转发过信息的邻居节点列表。 本文为每一种协议建立了一种数学模型，建立传输延迟、可靠度和冗余度三个指标。 分析结果表明，网络编码可以减少传输延迟，提高网络可靠度，尤其在缓存和带宽受限 的情况下，网络编码在减少传输延迟方面有着绝对的优势，说明在概率路由中使用网络 编码来减少系统开销是可行的，但同时带来了一定的冗余度。分析结果表明，本文提出 的e x p r - n c 协议在保证网络编码技术的优势的同时，大大减少了网络的冗余度，因此 提升了概率路由协议的总体性能，并通过仿真实验证明了分析结果。 关键词：网络编码，概率路由，传输延迟，无线传感器网络 a b s t r a c t t r a d i t i o n a l l y , n o d e sj u s tr o u t ea n df o r w a r dp a c k e t s n e t w o r kc o d i n gi sp r o p o s e dt o c h a n g et h i ss i t u a t i o n w i t hn e t w o r kc o d i n g ，n o d e sc a nc o d et h ep a c k e t sb e f o r ef o r w a r d i n g ， t h i s i m p r o v e m e n tb ea b l et oe n h a n c en e t w o r kt h r o u g h p u t f u r t h e r m o r e ，t h r o u g hn e t w o r k c o d i n g ，w ec a no b t a i nt h eb e n e f i t so fs a v i n gi nb a n d w i d t h ，l o a db a l a n c i n g ，i m p r o v i n g r e l i a b i l i t ya n ds oo n b e c a u s et h en o d e si nt h ew i r e l e s ss e n s o rn e t w o r k ( w s n ) h a v el i m i t e d r e s o u r c e ，s ot h et r a d i t i o n a lr o u t i n gp r o t o c o li s n tf i tf o ri t p r o b a b i l i s t i cr o u t i n gc a nb eu s e di n t h ew s nd u et ot h ef o l l o w i n gr e a s o n s ：o p t i o n a lm e s s a g ef o r w a r d i n g ，s t r o n gf a u l t t o l e r a n c e a n di td o e s n tn e e dt ok n o wt h ew h o l en e t w o r kt o p o l o g y t h i sp a p e ra p p l i e sn e t w o r kc o d i n gt o t h e p r o b a b i l i s t i cr o u t i n g t h e n ，p r o p o s e sa l l a n a l y t i c a lf r a m e w o r kt os t u d yt h ep e r f o r m a n c eo fp r o b a b i l i s t i cr o u t i n gb a s e do nn e t w o r k c o d i n g ，i nc o m p a r i s o nw i t hp r o b a b i l i s t i cr o u t i n gb a s e do nr e p l i c a t i o n o nt h eb a s i so ft h e p r o b a b i l i s t i cr o u t i n g ，c o m b i n e sw i t hn e t w o r kc o d i n ga n dr e f e r st ot h et h i n k i n go fs i n g l ec o p y ， s p r a ya n dw a i tr o u t i n g ，w ep r o p o s e sa ni m p r o v e m e n tp r o t o c o l ：e x t e n d e dp r o b a b i l i s t i c r o u t i n gb a s en e t w o r kc o d i n g ( e x p r - n c ) i nw h i c hn o d e sd i r e c t l yf o r w a r dp a c k e t sw i t h o u t c o p y i n ga n de s t a b l i s han e i g h b o r i n gn o d e sl i s tf o re a c hn o d e t h eg o a lo ft h i sp r o t o c o li sk e e p t h ea d v a n t a g eo fn e t w o r kc o d i n ga n dr e d u c et h er e d u n d a n c ys i m u l t a n e o u s l y w ee s t a b l i s ha na n a l y t i c a lm o d e lf o re a c hp r o t o c o l ，t h e n ，g i v eo u tt h r e ec r i t e r i o n s ： d e l i v e r yd e l a y , r e l i a b i l i t ya n dr e d u n d a n c y t h ea n a l y s i sr e s u l ts h o w st h a tn e t w o r kc o d i n gc a n d e c r e a s ed e l i v e r yd e l a ya n di n c r e a s er e l i a b i l i t yb a s e do nt h ec e r t a i nr e d u n d a n c y ，e s p e c i a l l y w h e nb u f f e ra n db a n d w i d t ha r er e s t r i c t e d b u ta tt h es a m et i m e ，n e t w o r kc o d i n gb r i n g s r e d u n d a n c y i no r d e rt or e d u c et h er e d u n d a n c y , t h i sp a p e rp r o p o s e se x p r n c ，a st h er e s u l to f t h ea n a l y s i s ，w ek n o wt h a te x p r - n cc a nn o to n l yg r e a t l yd e c r e a s er e d u n d a n c yb u ta l s o d e c r e a s ed e l i v e r yd e l a ya n di n c r e a s er e l i a b i l i t y s ow eg a i nt h er e s u l t st h a te x p r n c p r o m o t e st h eg e n e r a lp e r f o r m a n c e ，a n dt h e np r o v e st h er e s u l t st h r o u g ht h es i m u l a t i o n k e yw o r d s ：n e t w o r kc o d i n g ，p r o b a b i l i s t i cr o u t i n g ，d e l i v e r yd e l a y , w i r e l e s ss e n s o rn e t w o r k ( w s n ) i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 加7 年石月洳 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 产乡月湘 硕士论文基于网络编码的传感器网络概率路由协议分析研究 1 绪论 随着人们对移动通信的需求逐渐增强，各种网络技术层出不穷，其中以无线传感器 网络晗1 ( w s n ：w i r e l e s ss e n s o rn e t w o r k ) 为代表的新兴无线通信网络因其架设方便、 通信灵活等特点被首先应用到具有挑战性、应急性的特殊通信领域。w s n 是由区域内 大量移动或静止的传感器节点以无线通信方式形成的自组织网络。传感器技术的飞速发 展使得无线传感器网络有着越来越广泛的应用，被广泛应用于环境科学、医疗卫生、军 事国防、商业应用等诸多领域。由于w s n 具有对等和节点资源受限的特性，因此传统路 由协议不适用于该网络。 概率路由协议是f l 了l i n d g r e n 等人提出来的【l2 1 ，利用节点相遇的历史信息记录节点的 传送概率，然后根据传送概率来决定是否在节点之间转发数据，其中传送概率是指一个 节点遇到已知目的节点的概率，随时间和节点的不断移动而动态更新。因其具有可选择 的信息转发、很强的容错性以及无需了解全部网络拓扑信息等特点，非常适用于w s n 。 1 1 研究现状 1 2 1 网络编码 在传统的计算机网络通信中，网络中的路由节点( 交换机或路由器) 对收到的信息 进行存储转发，不进行任何数据处理，而是将收到的信息复制转发给多个节点或直接转 发给下一个节点。但是网络中传递的信息本质上是连续的比特流，因此节点除了可以 存储和转发信息外，应该可以先对收到的信息进行一定的数学变换，然后再转发出去。 网络编码正是基于这样的思想提出的。2 0 0 0 年，香港中文大学的a h l s w e d e 首次提出了 网络编码的概念n ，其核心思想是网络中的节点可采用不加冗余的编码。 自从2 0 0 0 年a h l s w e d e 等人首次提出了对信息进行编码的思想后，网络编码就成 为了信息领域的一个热点，对其进行研究的文献更是如雨后春笋。本节主要介绍网络编 码应用于无线网络以及与无线网络中路由协议相结合的研究进展。文献 5 、 6 在 无线网络中使用网络编码，说明其与节点的物理层广播相结合，可以节省信息传输对能 量的平均消耗，文献 1 8 】、【1 9 和 4 1 】研究了其应用于无线网络中的吞吐量和多播效率， 这些研究与实践体现了网络编码强大的生命力。而近期的研究热点在于分布式的随机网 络编码研究【3 0 】以及网络编码在实际环境中的实现【3 1 1 1 3 2 】，对其安全性的研究也是一个研 究热点，一些研究者开始研究使用网络编码的安全性【2 0 】【4 3 】。 为了提升无线网络中路由协议的性能，不少学者致力于研究将网络编码应用到各种 路由协议中。文献 1 4 初步讨论了将其应用于路由协议中，介绍了如何进行重叠度较大 的路由选择及给出编码域的界；n o g u c h i 等指出通过对节点收到的数据进行编码我们可 1 1 绪论 硕士论文 以改善网络链路的负载平衡n 钔，在与传统的多播路由相同的多播速率下，使用网络编码 可以将需要传送的信息分配到多条路径上进行传输，这样可以防止一条链路的负载过 重，引起网络的堵塞。文献【2 6 、 2 7 和【2 8 】研究了在无线网络中将网络编码应用于多播 路由的优势，而文献【1 3 】研究在不连接网络中将网络编码应用于单播路由的优势。文献 【7 】将网络编码应用于具体的路由协议，通过建立数学模型进行定量分析，表明可以减少 传染性路由协议的传输延迟。 1 2 2 概率路由协议 由于w s n 中节点对等和节点资源受限等特点，传统的路由协议不适用于该网络，所 以需要研究适用于w s n 的概率。传染性路由( e p i d e m i cr o u t i n g ) 是由v a h d a t 和b e c k e r 提出的【1 6 1 ，作为第一个针对受限网络提出的路由，具有计算简单，无需解网络拓扑信息 等特点，但是它是基于路由扩散的，缓存中存在大量数据包的拷贝，消耗了大量的网络 资源，而且若缓存受限时传输延迟较大。因此，l i n d g r e n 等人对传染性路由进行了改进， 提出了概率路由协议【l2 1 ，全称为p r o b a b i l i s t i cr o u t i n gp r o t o c o lu s i n gh i s t o r yo f e n c o u n t e r s a n dt r a n s i t i v i t y 。 概率路由是基于历史信息的转发路由【2 筋，因其具有可选择的信息转发、很强的容错 性以及无需了解全部网络拓扑信息等原因，非常适用于w s n ，因此很多学者致力于对其 性能的研究。文献【1 7 】中通过仿真证明概率路由与传染性路由相比，能以较小的资源消 耗获得更多的数据包，文献 3 5 】中，作者提出了一种自适应的路由算法，详细叙述了概 率路由的原理及基本算法。 1 2 与本文相关的前期研究 在本文的研究过程中，参考了大量的国内外相关文献。特别是在对模型的建立和分 析上，借鉴了一些其它相关文献中的思想和方法。 在文献f 7 1 中，作者把网络编码技术应用到传染性路由协议中。在该文献中，作者在 带宽和节点缓存大小受限的网络环境中建立了一种分析模型，计算了在基于复制和基于 网络编码两种情况下传染性路由协议的传输延迟。但是文献只说明应用网络编码后传染 性路由协议的延迟减小了，没有对应用网络编码后的网络资源消耗情况进行分析，这样 就不能看出总体性能是否提高了。本文在文献【7 】的基础上，在第3 章中进行了更深入的 研究，建立了传输延迟，可靠度和冗余度三个指标，其中冗余度是指可靠传输一个数据 包实际在网络中传输的数据包总数，该指标从某种程度上也反映出了一种在网络中传输 数据所消耗的额外能量代价。 文献 7 】中研究的是基于路由扩散的传染性路由协议，因其基于路由扩散，所以性能 较差，文献 1 2 】中说明概率路由的性能要优于传染性路由，更适用于资源受限的网络。 2 硕1 二论文基于网络编码的传感器网络概率路由协议分析研究 第3 章中根据文献b 2 中阐述的概率路由的基本思想，将网络编码技术引入到该路由中， 并参考了文献【7 】中建立的传输延迟指标及其分析思想，建立了传输延迟，可靠度和冗余 度三个指标，通过对基于复制的路由p r - r e p 和基于网络编码的路由p r n c 两种模型 同时分析这三个指标，可看出网络编码的应用减少了传输延迟，提高了网络可靠度。 文献【4 】中，作者提出每个数据包在网络中拥有单一拷贝的思想，此种方法减少了网 络的拷贝，但是网络中只有一个拷贝包，导致传送延迟大大增加，而且降低了系统的容 错性。文献 3 】中，作者提出一种扩散和等待路由，将算法分为两阶段：第一阶段由源节 点向其周围邻居节点以不同的l 个路径转发l 个信息拷贝，若在此阶段遇到目的节点， 则传输成功；若没有则使每个载有信息拷贝的节点执行直接传输。此种算法虽然也降低 了网络中的拷贝数，但是如何确定信息拷贝个数l 是个难题，l 的大小与算法性能存在 着矛盾，而且路由节点不转发而一直等待会导致传输延迟增加。且没有任何一种方法应 用了网络编码技术，也没有建立分析模型。 本文在此基础上，在第4 章提出了基于网络编码的扩展概率路由协议( e x t e n d e d p r o b a b i l i s t i cr o u t i n gb a s e do nn e t w o r kc o d i n g ) e x p r - n c 。对p r - n c 进行了两点扩展， 设定网络中只有源节点拷贝数据包传给其它节点，而其它节点直接传输，这样可降低网 络中数据包的拷贝数目，从而降低资源的消耗。在传输的过程中，源节点可以一直将拷 贝数据包传给路由节点，这样就会避免因网络中含包的节点数目过少导致的延迟增加。 同时每个路由节点维护一张曾经传输过信息的邻居节点列表，这样可以避免一个数据包 在两个节点间重复传输，从而减少资源的消耗。并建立模型定量分析了e x p r - n c 协议， 最后通过仿真证明了e x p r n c 协议不仅保证了在概率路由中应用网络编码的优势，还 大大减少了网络的冗余度，提升了路由协议的总体性能。 在文献 8 中，主要分析了一种线形网络编码方法，本文中采用随机线形网络编码田1 ， 不需要了解全网拓扑结构，只需在有限域内选择合适的编码向量即可保证编码数据的 有效性。 1 3 本文主要工作及各章节内容 本文主要研究基于网络编码的传感器网络概率路由协议的性能。 首先，在文献 7 的基础上，参考其将网络编码技术应用到传染性路由协议中并建 立传输延迟这一指标进行分析的思想，将网络编码技术应用到概率路由协议中，并在概 率路由协议中建立了可靠度、传输延迟、冗余度三个指标，定量分析比较了基于复制的 概率路由和基于网络编码的概率路由的性能，说明应用网络编码技术可减少传输延迟， 提高网络可靠度，但是却增加了网络的冗余度。 其次，参考文献【3 中扩散和等待路由协议中节点直接传输和文献【4 】中数据包单一 拷贝的思想，本文提出了e x p r - n c 协议，对概率路由协议提出两点改进：( 1 ) 路由节 3 l 绪论 硕j ：论文 点的直接数据包传输机制；( 2 ) 已转发的邻居节点信息存储技术。 最后，针对本文提出的改进，对e x p r - n c 协议建立一个分析模型，定量分析了 e x p r - n c 中的传输延迟、可靠度和冗余度，并通过仿真验证了分析结果，证实本文提 出的改进提高了概率路由协议的总体性能。 论文章节安排如下： 第一章绪论主要介绍了本文的研究背景以及本文主要的研究工作。同时指出了与 本文研究内容相关的前期研究工作。 第二章介绍了概率路由协议的基本原理，重点介绍了网络编码的基本原理及其编 码方式。 第三章建立分析模型，建立了可靠度、传输延迟和冗余度三个指标，对基于复制 的概率路由和基于网络编码的概率路由两种模型进行了深入的性能分析与对比评价。 第四章针对网络编码和概率路由协议的特性，对已有的基于网络编码的概率路由 协议提出了两点改进，提出了e x p r n c 协议，并建立了分析模型对e x p r n c 协议性 能进行了定量分析与比较，然后对此协议进行了仿真实验，验证了理论分析的结果。 第五章总结整个论文的工作，并提出下一步的研究工作。 4 硕士论文 基于网络编码的传感器网络概率路由协议分析研究 2 相关知识 本章将重点介绍网络编码的相关知识，同时介绍概率路由协议的基本原理。 2 1 网络编码 2 1 1 网络编码的概念 网络编码的核心思想是：在网络中参与传输的节点，对其多条输入边上输入的数据 进行某种线性或非线性变换得到已编码的数据，然后输出，而且参与传输的所有节点对 数据的变换应保证最终所有接收节点可以正确恢复出源节点所发送的信息。图2 1 描述 了网络编码的基本原理。 图2 1 单信源二信宿网络 图2 1 所示是一个单信源二信宿网络，设各链路容量为1 ，s 是源节点，d 1 和d 2 是 接收节点，其余为中间节点。根据最大流最小割定理，理论文上其最大传输容量为2 ， 图2 1 ( a ) 表示的是传统的路由传输方式，显然在这种方式下不能达到网络的最大传输 量。图2 1 ( b ) 表示的是网络编码方法，节点3 对从节点l 和节点2 收到的数据进行模- - j n 运算，将运算结果发给4 ，因此目的节点d 1 在一个单位时间内收到了a 和a + 6 ，于是通 过译码操作a + 0 + 6 ) 可得到b ，也就是说，d 1 相当于同时收到了a c - g l b ，同理d 2 也是 如此。 2 1 2 随机线性网络编码 若在编码过程中，节点对收到的数据进行线性操作，则称为线性网络编码；否则称 为非线性网络编码。若编码的系数是从有限域中随机选择的，则称为随机网络编码；若 编码系数是通过一定的算法计算出来的确定值，则称为确定性网络编码。文献【8 】证明： 在有限域c 中，只要域足够大，则通过合适的线性编码，就能使多播传输达到最大的 传输容量。本文中使用的是随机线性网络编码。 2 相关知识 硕士论文 在本文的网络模型中，有1 个源节点，需要发送k 个数据包，源节点在k 个原始数 据包的包头封装上相同的标识，将其分为一组，记为巨，易，敏。然后，从中随 机的选择k 个数o 。，仅：，仅k 对k 个原包进行编码，将其编码成k 个已编码包，记为 五，而，k ，设编码成第f 个已编码包时所使用的系数记为0 u ，仅啦，g t 谜，则编码 公式如式( 2 1 ) 所示： t = 0 【u q ( f _ l ，2 ，k ) ( 2 1 ) j = l 中间节点收到数据包后，会存储一定时间内收到的包，然后从e 中随机的选择一组 系数，将具有相同组标识的包进行再编码。设节点a 收到m 个同一组的包，记为 五，再编码的系数为盼，p 啦，p 啪，编码后生成的数据记为 五，x 2 ，则a 对其缓存中第f 个包再编码的方法如式( 2 2 ) 所示： 卅 薯= 耽 ( 2 2 ) = l 由式( 2 2 ) 可以得出经过再编码以后的数据包与原始数据包的关系和中间节点进行 再编码的编码向量，分别如式( 2 3 ) 和式( 2 4 ) 所示。 k 鼍= y 爿x e f i _ i j j j = l ( 2 3 ) i 一, j = z o l f ，吼 ( 2 4 ) j = l 通过中间节点对所收到的数据包进行再编码，可以进一步降低接收节点收到的报文 的线性相关性。只要目的节点接收至少k 个包时，就能通过矩阵转换来解码出k 个原始 数据包，则解码矩阵如式( 2 5 ) 所示： 巨 最 ： 乜 f ，a ，。0 l 。、- l 1 2 i ：。： i l 伐册l仅。 而 镌 ： ( 2 5 ) 由式( 2 5 ) 可以看出，接收节点能否解码出原始数据包与编码向量所组成的矩阵是 否满秩有关。根据线性相关原理，在本节中，只要目的节点接收到k 个包时即可解码 获得所有原始数据包。在随机线性网络编码中，编码向量是从有限域中随机选取的， 可见，增大有限域的容量可以增加目的节点解码的概率。文献 3 6 1 中指出，在实际的应 用中，有限域的容量只需要使用2 8 。 2 1 3 网络编码对w s n 性能的影响 6 硕上论文基于网络编码的传感器网络概率路由协议分析研究 无线传感器网络w s n 能量、通信能力、存储能力都有限，因此需要尽量减少资源 的消耗。网络编码可最大限度的利用网络资源，因此非常适用于资源受限的w s n ，其 可以提升网络的总体性能，主要表现在以下几方面： ( 1 ) 节省节点的能量消耗 在w s n 中，节点通常采用电池供电，网络中的电池能量有限，因此限制了网络的 寿命。网络编码的应用极大地提高了数据的传输率，有效减少了重传次数，从而降低了 能量消耗。 ( 2 ) 提高网络吞吐量 网络编码最初的目的就是实现组播中的最大流传输，改善网络的吞吐量，在w s n 中，通过节点进行通信，数据通过一跳或多跳传输到目的节点，网络编码能够获得网络 组播的最大流限，从而极大的提高了网络吞吐量【4 2 】。 ( 3 ) 增强网络鲁棒性 在实际的应用中，w s n 中的节点经常会失效，从而影响网络的鲁棒性，传统方法 是恢复链接，而使用网络编码后，因为只要是同一组的数据节点接收到任意一个都是相 同的效果，因此节点失效或链路断开对网络性能的影响就会降低，从而增强了网络的鲁 棒性【3 7 】。 2 2 概率路由 概率路由协议是f l 了l i n d g r e n 等人提出来的，全称p r o b a b i l i s t i cr o u t i n gp r o t o c o lu s i n g h i s t o r yo fe n c o u n t e r sa n dt r a n s i t i v i t y ，利用节点相遇的历史信息记录节点的传送概率， 节点只向传送概率更大的节点发送数据，其中传送概率是指一个节点遇到已知目的节点 的概率，概率随时问而动态变化。 2 2 1 概率路由的基本思想 在概率路由中，当两个节点相遇后，数据通信过程如图2 2 所示： 图2 2 概率路由的数据通信过程 如图2 2 所示，当两个移动节点a 和b 相遇时，数据通信过程分为以下三个阶段完 7 2 相关知识硕：i ：论文 成： ( 1 ) 节点a 向b 发送自己的s 形； ( 2 ) b 收到s 圪后，会和自己的概括矢量s 进行比较，首先比较哪个节点的传送 概率大。若b 的传送概率比a 大，则b 判断哪些数据包a 的缓存里有而自己没有，这 些数据包的集合为m 爿，m a = s 圪+ s ，比较完成以后，b 会向a 发送信息来请求获 取m a ，接着执行步骤( 3 ) 。若b 的传送概率较小，则a 不发送数据给b ，传输结束； ( 3 ) a 根据b 的请求信息发送数据，b 接收到a 发送的数据后，更新自己的概括 矢量s k ，若数据包的目的地址就是b ，则b 将数据包传送到上一层，否则缓存数据包， 直到碰到另一个节点。 上述三阶段完成了a 向b 的数据传输，反过来b 也会按照这三个阶段完成向a 的 数据传输。网络中所有的节点都是不断移动的，随着节点的移动，原始数据包的拷贝不 断存储在各个节点的缓存中，直到传输到目的节点。 2 2 2 概率路由的算法描述 概率函数又可称为传送概率，用来表达每一个节点传送信息到已知目的地的机会。 假设网络中任意一个节点a 到已知目的节点b 的到达率为冀础) ，( 只咖) o ，l 】) ，初始传送 概率为己打，鼻舶) 根据节点口和6 间的相遇频率进行实时更新，从而动态的反映出数据 从a 传送到b 的概率。曰棚如式( 2 6 ) 所示： 最咖，= 主：一鼻以6 h 已f ，i f 。a 历m p m e e t 括s 三 c2 6 ， 其中，己打为初始传送概率，当两个节点a 和b 相遇时，传送概率进行更新，此时鼻 变大，反映出a 和b 相遇的概率增加。而当a 和b 较长时间没有相遇后，要对其之间的 概率进行老化，其中丫( 丫“0 ，1 】) 是老化常数，丫的值代表了两节点间的概率老化的“速 度”；k 是a 和b 多长时间没有相遇的单位时间数。从式( 2 6 ) 可以看出，节点间的传送 概率随时问动态变化，两节点相遇的频率越高，它们之间的传送概率越大，反之亦然。 传送概率还具有传递性。假设节点a 经常与节点b 相遇，而节点b 经常与节点c 相遇， 那么对于节点口来说，节点c 是一个比较好的信息转发节点。式( 2 7 ) 表示怎样利用传 递性来计算两节点间的传送概率，p ( 0 ，1 ) 是标题常数，决定了传递性对传送概率的影 响。 丘。d = 置。枷+ ( 1 一鼻。c ) 删) 鼻咖) 鼻6 ，。) p ( 2 7 ) 由上述分析知，概率路由根据节点间的传送概率对数据的转发策略进行限制：数据 一般只在传送概率较大的节点间进行转发，这样既能减少网络资源的耗用，又能保证协 议的性能。通过调整协议公式中的各参数值，可以使协议性能达到优化。 8 硕十论文基于网络编码的传感器网络概率路由协议分析研究 2 2 3 概率路由适用于w s n 的原因 由于w s n 具有节点对等，节点能量有限且容易出现故障，网络拓扑易变等特点， 使得传统的路由协议不适用于该网络，而概率路由因以下几个特点使之非常适用于 w s n 。 ( 1 ) 强容错性 由于w s n 中节点容易出现故障，因此适用于其中的路由协议需要有一定的容错性。 概率路由中，一个数据包在网络中有多个拷贝，节点间传输的是数据包的拷贝。当一个 节点出现故障时，不影响网络中其它的节点传输数据，因此具有很强的容错性。 ( 2 ) 选择性 由于w s n 中节点资源和端到端资源都受限，因此其网络协议必须要能高效地利用能 量。概率路由中，节点间是根据彼此的传送概率，有选择的发送信息，而不是向所有邻 居节点发送信息，因此适用于资源受限的传感器网络。 ( 3 ) 无需了解网络拓扑信息 w s n 中因环境干扰和节点故障，网络拓扑易变，所以其网络协议必须要能在局部 网络信息的基础上选择合适的路径进行传输。而概率路由是基于历史信息的，只要知道 每个节点的传送概率，当两个节点相遇时，根据彼此的传送概率有选择的发送信息，不 需要了解全部的网络拓扑信息，因此适用于拓扑易变的传感器网络。 2 3 本章小结 本章介绍了概率路由协议的基本原理，重点介绍了网络编码的基本原理与性能，并 叙述了随机线性网络编码的具体实现过程。 9 3 概率路由协议的性能分析硕上论文 3 概率路由协议的性能分析 本章通过建立两种网络模型来分析一种重要的路由协议：p r o p h e t ( p r o b a b i l i s t i c r o u t i n gu s i n gh i s t o r yo f e n c o u n t e r sa n dt r a n s i t i v i t y ) ，又称概率路由。这两种网络模型是： 1 、基于复制的概率路由( p r o b a b i l i s t i cr o u t i n gb a s e dr e p l i c a t i o n ，p r r e p ) ；2 、基于网 络编码的概率路由( p r o b a b i l i s t i cr o u t i n gb a s e dn e t w o r kc o d i n g ，p rn c ) 。 本文通过对比分析，选择了传输延迟，可靠度和冗余度作为性能指标，其中传输延 迟( d e l i v e r yd e l a y ，乃) 是指从源节点发送数据包开始直到目的节点接收到所有数据包 的时间；可靠度( r e l i a b i l i t y ，c r ) 是指由源节点发送的数据包成功到达目的节点的概 率；冗余度( r e d u n d a n c y ，) 是指可靠传输一个数据包实际在网络中传递的数据包的 总数。 3 1 建立路由模型 本文的每一种模型由1 个源节点，n 个路由节点和1 个目的节点组成，每个路由节 点均可存储和转发数据包。其中，源节点需传输k 个数据包到目的节点。当两个节点相 遇即进入彼此的传输范围内时，可通过比较彼此的传送概率来传输数据包，源节点可向 所有与它相遇的节点传输数据。 在基于复制的概率路由协议中，路由节点拷贝数据包转发给所有传送概率比它高的 节点。每个节点均可以存储和转发数据包，数据包存放在节点的缓存中，并为数据的集 合建立索引s v ( s u m m a r yv e c t o r ) ，s v 中包含数据包的索引和节点的传送概率，即节 点遇到已知目的节点的概率。当两个节点相遇( 即彼此进入到对方的无线通信范围内) 时首先交换彼此的s v ，然后，比较双方的传送概率，若自己的传送概率大，节点再遍 历自己的数据包索引，并以此来判断哪些数据包自己没有而对方有，而后节点向对方发 送一个包含这些数据包清单的请求信息，节点间传送的是彼此缓存中数据包的拷贝。节 点间通过节点的移动而不断相遇，因此，数据会从源节点开始不断复制到其它节点，直 到传送到目的节点。 这种方法通过记录每个节点的传送概率，概率随着时间的变化而动态改变，当没有 遇到传送概率更大的节点时，节点就存储数据包，因此缓存的大小对路由协议的性能有 着很大的影响。如果缓存足够大，将提高数据包传输的成功率，但同时也会增加网络资 源的消耗。本文研究当网络带宽和节点缓存受限时概率路由的性能，为了简化分析，本 文假设： ( 1 ) 当任意两个节点相遇时，它们之间的带宽仅够传输一个包，若节点间可以传 输的包大于1 个，则节点将从可以传输的数据包中随机选取一个包进行传输； l o 硕十论文基于网络编码的传感器网络概率路由协议分析研究 ( 2 ) 源节点和目的节点均有足够的缓存去存放k 个包，路由节点的最大缓存数为b ( 1 b k ) ： ( 3 ) 当目的节点接收到需要发送的所有数据包并发送一个a c k 或全局时间终止 时，路由节点的缓存可被清零，这样所有路由节点的缓存初始状态均为空； ( 4 ) 本文假设网络中的所有节点满足以下三个条件：节点依照公共迁徙模式移动； 节点传输范围小于节点移动的范围；节点移动的速度足够快。则任意两个节点的相遇时 间呈指数分布【l0 1 ，且用九来表示两个节点相遇的概率。 在本文的三种模型中，无线信道的误码率用玩表示，所以发送一段长度为三b i t 的 数据包，在传输过程中，每一跳数据包被正确接收的概率阢如式( 3 1 ) 所示。 p c = ( 1 一见) l ( 3 1 ) 3 1 1 基于复制的概率路由协议( p r _ r e p ) 3 1 1 1p r - r e p 的传输延迟 在基于复制的概率路由协议中，传输延迟是指目的节点接收到k 个包的时间，因为 在概率路由中，数据包是通过节点的不断移动来传输的，因此要计算传输延迟，首先要 计算任意时刻网络中所有路由节点缓存的分布。 本文假设b 代表路由节点最大缓存数，我们可将网络中的路由节点按缓存中数据包 的个数划分为b + i 类：用置表示缓存中含有f 个数据包的路由节点。然后用一个b 元组 i ( f ) ，2 ( f ) ，虬( ，) ) 代表t 时刻网络中所有路由节点缓存的分布，其中，m ( f ) 代表r 时 刻薯的数量，显然在此网络模型下， n o ( t ) = n - ( f ) ，对于任意时刻誓的数量，( f ) ( 1 f b ) ，可由上一时刻网络中薯的 数量加上t 在o t 时间内的改变量c ；( f ) 求得，于是任意时刻各类路由节点葺的个数 m o ) 如式( 3 2 ) 所示： rb j n o ( 归n 一j = l 啪) ( 3 2 ) 、 ) i f ( t + c t ) = ，( ，) + o t 屹( ，) ( 1 f b ) 因为在3 1 小节中，我们假设所有路由节点的缓存初始状态均为空，因此m ( f ) 的初 始值为：o ( o ) = n ，j ( 0 ) = 0 ( 1 f b ) 。 c 。( t ) 为t 时刻f ( f ) 的改变量，由两部分组成：( 1 ) t 时刻由薯一。变为薯的路由节点 的数量；( 2 ) t 时刻由薯变为薯+ 。的路由节点的数量。因为本文中假设任意两个节点相遇 时它们之间的带宽只够传输一个数据包，所以誓只可变为+ l ，薯以v ( f ) 的接收率从其 3 概率路由协议的性能分析 硕士论文 它节点接收一个新的数据包，进而变为薯+ l ，同时一。以u 一。( ，) 的接收率接收新的数据包 进而转换为墨，而只可由一。转换而来，其本身不可再接收新的数据包，于是对于 1 f b ，m ( ，) 的改变量如式( 3 3 ) 所示，其中u ( f ) 代表t 时刻路由节点五( 0 f b - 1 ) 的接收率： f c 。( f ) = 配一l ( f ) f l ( ，) 一( ，) f ( f ) ( 1 f b 一1 )r 。 i c 。( ，) = u b l ( f ) n b l ( f ) 在概率路由协议中，节点接收数据后，将数据存储在缓存在中，并为数据的集合建 立一个索引，索引中还包含节点的传送概率，节点只向传送概率大于自己的节点传送数 据。每个节点的初始传送概率均为幺f f ，随着节点的移动，各节点的传送概率随时间而 不断改变。当两个节点相遇时首先比较双方的传送概率，只向传送概率更大的节点发送 数据。 在本文的模型中，因为初始时刻网络中所有路由节点的缓存均为空，所以缓存中数 据包的个数反映了一个节点移动的频率，显然，缓存中的数据包越多，说明此节点的活 动越频繁，因此它遇到目的节点的概率也就越高。所以，本文中，含包少的节点可向含 包多的节点传输数据包。用p ( f ，) 代表节点薯从节点x j 处获得一个新包的概率，其中五 代表缓存中有f 个数据包的路由节点。显然若f ，则表明薯不如x ，活动频繁，即x e 的 传送概率小于z ，因此x ，不向薯传输数据包：若f ，说明薯的传送概率大于x j ，则葺 可以从x ，处获得一个新包，又因为缓存里的数据包比x ，多，所以仅当x ，不含x ，的所 有包时，薯能从戈，处获得一个新包。因为k 个原始数据包在各路由节点的缓存中呈均匀 分布，所以任意两个节点间的转发概率p ( i ，) 如式( 3 4 ) 如示： f of f ，、 p o ，2 1 一c ；c ：，二； 3 4 在概率路由中，源节点可向网络中的任意节点发送信息。由上文分析知，在本文的 模型中，仅当f j 时，鼍可从x ，处获得一个新的数据包，所以缓存中没有数据包的节点 只可从源节点接收信息。所以，对于0 i b ，路由节点x ，的接收率u ( f ) 见式( 3 5 ) ， j ( ，) 的值由式( 3 2 ) 可求。 r ，b 、 j 伊九【杉( f ) p ( i + 1 j ( 0 珏肛1 )(35)t=l、， - ， h ：o 。 。 在概率路由中，目的节点可以接收任意节点发送过来的数据，设目的节点以办( f ，) 的概率从其它节点获得一个包。显然，当目的节点的缓存为空时，目的节点可以从任意 含包的节点x j ( 1 j b ) 中获得一个数据包，当目的节点含有i ( 1 f k 一1 ) 个数据包 时，仅当与目的节点相遇的路由节点x i 中含有其所没有的数据包时可传输一个包，因为 1 2 硕十论文 基于网络编码的传感器嗍络概率路由协议分析研究 k 个原始数据包在各路由节点的缓存中呈均匀分布，所以p d ( i ，) 如式( 3 6 ) 所示： 聪肛j 1 ( k n ( 3 6 ) 以l d 2 1 1 u r 舀- j ) o 石 而对于0 i k - i ，目的节点的接收率d f ( f ) 如式( 3 7 ) 所示： 口( f ) _ 九i m ( f ) 办( f ，) + 1i ( o _ i f ) = 目的节点在o f 时间内遇到含包的路由节点并接收一个新包的概率) ( 1 一p ( r ) ) = 九i m ( t ) x p u ( 0 ，) + 1i ( i - a ( f ) ) = 九i m ( ，) + 1i ( 1 - p 。( f ) ) 届( f ) 在o f 时间内的改变率为您( f ) = p ( t 石t + 6 t ) ，而只( f ) 的改变率( f ) 表示 目的节点在t 时刻已收到，一1 个包，且在o ，时间内收到第i 个包的概率，则 民( f ) = p ( z l f 巧，+ o f ) ，因此( r ) 和( ，) 如式( 3 9 ) 所示： 踹三篡蕊2 删啡2i k ， 9 ， i 艮( f ) = 口一l ( ，) ( 只一l ( ，) 一只( f ) ) ( ) 由上述分析知，在基于复制的概率路由协议中，求网络的传输延迟可分为以下四个 步骤： ( 1 ) 由式( 3 5 ) 和式( 3 7 ) 求出任意时刻路由节点和目的节点的接收率； 3 概率路由协议的性能分析 硕士论文 ( 2 ) 由式( 3 3 ) 以及任意时刻各节点的接收率再进一步求出任意时刻网络中曰+ l 类路由节点各自的改变量； ( 3 ) 由式( 3 2 ) 求出各个时刻网络中各类路