（计算机应用技术专业论文）基于网络编码的无线传感器网络dd协议研究.pdf

摘要 无线传感器网络的资源很有限，却集成了监测、控制以及无线通信等多种 功能。因此，无线传感器网络资源的节省显得尤为重要。网络编码理论的提出， 为提高网络性能、节省网络资源提供了新思路，路由协议中，中继结点先对报 文进行编码处理，再将编码的报文发送给后续结点，目的结点能够解码并恢复 原始的报文。这种路由建立过程是基于网络编码的。 本文首先介绍无线传感器网络、定向扩散路由协议以及网络编码。定向扩 散路由协议( d i r e c t e dd i f f u s i o n ，简称d d ) 是一个以数据为中心的传感器网络路由 协议。根据该协议的原理和运行机制，找出该协议浪费网络资源的缺点。 然后采用网络编码技术，提出了一种新的基于网络编码的定向扩散路由协议 ( d i r e c t e dd i f f u s i o nb a s e do nn e t w o r kc o d i n g ，简称n c d d ) ，通过对该协议的安全 性能进行分析，找出n c d d 存在的威胁，提出了增强安全性的基于网络编码的定 向扩散路由协议( s e c u r en c d d ，简称s n c d d ) ，该协议采用的是同态的签名方案。 最后，采用著名的网络仿真平台n s 2 对新协议n c d d 、s n c d d 的网络性 能进行仿真。在n s 2 已有的定向扩散协议实现的基础上，修改定向扩散路由协 议的源文件，重新编译n s 2 ，生成新的仿真平台。数据跟踪文件用来保存仿真 过程中产生的数据，编写a w k 程序对报文平均的端到端延迟、网络中所有结点 的平均剩余能量、网络平均吞吐量进行计算，并用一个命令导向的交互式绘图 程式g n u p l o t 画出对应的曲线图，从而得到n c d d 的性能分析。用同样的方 法和步骤对s n c d d 协议进行网络性能仿真。 本文的主要特色与创新之处体现在如下三个方面：( 1 ) 利用随机的线性网络 编码，提出一种新的基于网络编码的定向扩散路由协议n c d d 。( 2 ) 利用同态的 签名方案，提出了安全的基于网络编码的定向扩散路由协议s n c d d ，该协议 增强了n c d d 对污染攻击的抵抗力。( 3 ) 对n s 2 仿真平台进行2 次扩展，使用 扩展后的仿真平台分别对n c d d 、s n c d d 路由协议的网络性能进行了不同网 络规模的仿真。结果表明：n c d d 比d d 的网络性能好，报文平均端到端延迟、 结点的平均剩余能量和网络吞吐量都有改善。s n c d d 在安全性增加的同时， 网络吞吐量有所提高，但是报文端到端平均延迟增加。 关键字：无线传感器网络，网络编码，定向扩散，安全，仿真，同态 a b s t r a c t t h er e s o u r c e so fw i r e l e s ss e n s o rn e t w o r ka r el i m i t e d ，b u tm a n yf u n c t i o n ss u c h a sm o n i t o r i n g ，c o n t r o l l i n ga n dc o m m u n i c a t i n ga r ei n t e g r a t e di nt h en e t w o r k s oi ti s s i g n i f i c a n t l yi m p o r t a n tt os a v et h er e s o u r c e so f w i r e l e s ss e n s o rn e t w o r k w i t ht h e d e v e l o p m e n to fn e t w o r kc o d i n g ，t h e r ea r en e ww a y s t oi m p r o v et h ep e r f o r m a n c eo f n e t 、v o r l ( a n dt os a v et h er e s o u r c e s i nr o u t i n gp r o t o c o l s ，t h ei n t e r m e d i a t en o d e s p e r f o r mt h ec o d i n gm a n i p u l a t i o n so nr e c e i v e dp a c k e t s a n ds e n dt h ec o d e dp a c k e t st o n e x th o p s ，t h ed e s t i n a t i o nn o d e sc a l ld e c o d ea n dr e c o v e rt h eo r i g i n a lp a c k e t s t h i s p r o c e s so fr o u t i n g i sb a s e do nn e t w o r kc o d i n g f i r s t l y , t h i sp a p e ri n t r o d u c e st h ew i r e l e s ss e n s o rn e t w o r k ，d i r e c t e dd i f f u s i o n r o u t i n gp r o t o c o la n dn e t w o r kc o d i n g d i r e c t e d d i f f u s i o nr o u t i n gp r o t o c o li s a d a t a c e n t r i cp r o t o c 0 1 a c c o r d i n gt ot h ep r i n c i p a la n dm e c h a n i s m ，t h i sp a p e rf o u n d o u tt h ed i s a d v a n t a g e so fw a s t i n gn e t w o r kr e s o u r c e si nt h ep r o t o c o l s e c o n d l y , t h ep a p e ru s e st h en e t w o r kc o d i n gt e c h n i q u e ，p r o p o s e s an o v e l r o u t i n gp r o t o c o l - n c 。d d ( n e t w o r k c o d i n g b a s e d d i r e c t e d d i f f u s i o n ) f u r t h e r m o r e ， b ya n a l y z i n gt h ew e a k n e s si ns e c u r i t y , t h i sp a p e rp r o p o s e san o v e l s e c u r en e t w o r kc o d i n gb a s e dd dp r o t o c o l ( s n c d df o rs h o r t ) ，w h i c hm a k e s u s eo f ah o m o m o r p h i cs i g n a t u r es c h e m e f i n a l l y t h i s p a p e r u s e st h ew e l l k n o w ns i m u l a t i o np l a t f o r m n s 2 t o s i m u l a t et h en e t w o r kp e r f o r m a n c eo fn c d da n ds n c d d i tn e e d st om o d i f yt h e s o u r c ec o d eo fd di nn s 2 ，c o m p i l en s 2a n dg a i na n e ws i m u l a t i o np l a t f o r m ，t h e na t r a c i n gf i l ei su s e df o rs a v i n gt h ed a t ag e n e r a t e di nt h ep r o c e s so fs i m u l a t i o n ，t h e a w kp r o g r a m sa r ew r i t t e nt oa d du pt h ea v e r a g ee n dt oe n dd e l a yo fp a c k e t s ，t h e a v e r a g er e m a i n d e re n e r g yo fn o d e sa n dt h ea v e r a g et h r o u g h p u to fn e t w o r k a tl a s t u s i n gac o m m a n d d r i v e n i n t e r a c t i v ef u n c t i o np l o w i n gp r o g r a mg n u p l o tt o g e n e r a t et h ec u r v e ，i tw i l lg e tt h ep e r f o r m a n c ea n a l y s i s o fn e wp r o t o c o l s t h e s i i n u l a t i n gp r o c e s so fs n c d d i st h es a m ea st h a to fn c - d d n t h em a i nr e s e a r c ha n di n n o v a t i o no ft h i sp a p e ra r ea sf o l l o w s ： ( 1 ) t h ep a p e rp r o p o s e san o v e lp r o t o c o l - - n c d d ( d i r e c t e dd i f f u s i o nb a s e do n n e t w o r kc o d i n g ) b a s e do nar a n d o m i z e dl i n e a rn e t w o r k c o d i n gs c h e m e ( 2 ) t h ep a p e rp r o p o s e s an e ws e c u r e r o u i n gp r o t o c o l - - s n c d d ( s e c u r e n c - d d ) ，w h i c hi sb a s e do nt h eh o m o m o r p h i cs i g n a t u r es c h e m e s n c d da d d st h e r e s i s t i b i l i t yt op o l l u t i o na t t a c kf o rn c d d ( 3 ) i te x p a n d st h es i m u l a t i o np l a t f o r m - - n s 2f o rt w ot i m e s ，s i m u l a t e sn c - d d a n ds n c - d dp r c t o c o li nd i f f e r e n ts c i n a r i o so fn e t w o r k t h er e s u l to fs i m u l a t i o n s h o w st h a tn c - d dh a sb e t t e rp e r f o r m a n c et h e nd d ，t h ea v e r a g ee n dt oe n dd e l a yo f p a c k e t s ，t h ea v e r a g er e m a i n d e re n e r g yo fn o d e sa n dt h ea v e r a g en e t w o r kt h r o u g h p u t a r ca l li m p r o v e d s n c d ds t r e n g t h st h es e c u r i t y , t h en e t w o r kt h r o u g h p u ti sh i g h e r t h a nt h a to fd d ，b u tt h ea v e r a g ee n dt oe n dd e l a yo fp a c k e t si sl o n g e r k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ，n e t w o r kc o d i n g ，d i r e c t e dd i f f u s i o n ，s e c u r i t y , s i m u l a t i o n ，h o m o m o r p h i c m 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生( 签名) ： 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 导师c 签名，：j 坠她期瑚 武汉理工大学硕士学位论文 1 1 引言 第l 章绪论 微电子技术、计算机技术和无线通信等技术的进步，推动了低功耗多功 能传感器的快速发展，使其在微小的体积内能够集成信息采集、数据处理和 无线通信等多种功能，在此基础上产生了无线传感器网络。传感器网络的研 究起步于2 0 世纪9 0 年代末期。从2 1 世纪开始，传感器网络引起了学术界、 军界和工业界的极大关注，美国和欧洲相继启动了许多关于无线传感器网络 的研究计划。传感器的应用前景非常广阔，能够广泛应用于军事、环境监测 和预报、健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、 空间探索、大型车间和仓库管理，以及机场、大型工业园区的安全监测等领 域。随着传感器网络深入研究和广泛应用，传感器网络将逐步深入到人类生 活的各个领域，被认为将对2 l 世纪产生巨大影响力的技术之一【l 】 1 2 研究背景及意义 1 2 1 研究背景 无线传感器网络【2 】是由大量的传感器结点组成，结点间协作地感知、采 集和处理网络覆盖区域中感知对象的信息。无线传感器网络是资源受限的网 络，结点的电源能量，通信能力，存储和计算能力都很有限，在设计无线传 感器网络协议的时候，能量是必须考虑的首要问题【3 j 。 在无线传感器网络中，传感器结点消耗能量的模块包括传感器模块、处 理器模块和无线通信模块。随着集成电路工艺的进步，处理器和传感器模块 的功耗变得很低，绝大部分能量消耗在无线通信模块上。因此，有必要设计 新的网络协议，来提高能量利用的有效性。路由协议不仅影响数据传输的可 靠性、实时性等一系列网络性能，而且还会影响通信所消耗的能量，从而影响 整个网络的生存时间1 4 1 。提高能量利用的有效性，延长网络生存时间的路由 武汉理工大学硕士学位论文 协议对于无线传感器网络的研究具有非常重要的意义。在存储转发的传统路 由方式下，已经设计出许多能量使用更为有效的无线网络路由协议【5 j 。 网络编码技术的产生，改变了传统的存储转发的路由方式，为设计新的 无线网络路由协议提供了新的方法。由于传感器结点传输信息时要比执行计 算时更消耗电能，传输l 比特信息l o o m 距离需要的能量大约相当于执行3 0 0 0 条计算指令消耗的能量，因此，在实时性要求不高的应用中，采用网络编码， 先对信息进行计算后再发送，减少链路上传输的数据量，就能有效节省能量。 随着微电子技术的发展，传感器结点的处理能力加强，计算消耗的能量降低。 网络编码技术在无线传感器网络中能得到应用。随机的网络编码方案，将网 络编码方案拓展到无线网络环境。 定向扩散路由协议是基于查询的、以数据为中心的路由协议。在路由建 立的过程中，能量没有得到有效利用。在已有的改进的定向扩散路由协议中， 都是采用传统的存储转发的路由方式。设计基于网络编码的定向扩散路由协 议是一个全新的课题。网络编码的安全性也逐渐引起了重视，同态的签名方 案也被用于网络编码的应用之中1 6 j 。 1 2 2 研究意义 网络编码理论是网络通信研究领域中一项重要突破，自从首次提出以来， 网络编码已迅速发展成一个重要的研究范畴，并对信息论、编码、通信网络、 网络交换理论，无线通信、计算器科学、密码学、运筹学、矩阵理论等领域带 来影响深远。网络编码是现今世界各地一流大学及工业实验室最热门研究领域 之一，亦是许多国际研讨会的热门议题。 网络编码理论对无线传感器网络领域的研究也有重大意义。传感器网络的 特征决定了传感器网络设计的首要目标是能源的高效利用。传感器结点的体积 微小，通常携带能量十分有限的电池，但数量多、分布广，而且部署的地区环 境复杂，有些区域甚至人员不能到达，所以通过更换电池的方法来补充能源是 不现实的，因此高效使用能量来最大化网络生命周期的意义十分重大。使用网 络编码能实现能量的有效利用。随着集成电路工艺的进步，处理器和传感器模 块的功耗变得很低，绝大部分能量消耗在无线通信模块上。网络编码是利用结 点的计算资源和存储资源，其能量消耗与传送数据相比要少很多。如果使用 2 武汉理工大学硕士学位论文 m i c a d o t 结点，发送一个比特数据的能耗可以用来执行大约8 0 0 条指令。因此用 结点的处理代价来换取能量的节省是很好的选择。网络编码能提高结点能量利 用的有效性，最大化网络的生命周期。此外，网络编码还能提高网络多播的容 量，节省带宽资源，改善网络链路的负载平衡。在已有的无线传感器网络路由 协议中，信息的传输很多是通过多播或者广播方式，因此网络编码在该领域有 很多应用的空间。 1 3 研究目的及所做的主要工作 1 3 1 研究目的 对无线传感器网络路由协议、网络编码理论以及签名算法进行研究，改变 传统路由中的存储转发方式，采用网络编码思想，提出新的基于网络编码的无 线传感器网络路由协议，以此来节省网络资源，提高网络的性能。在此基础上， 采用同态签名方案，增强所设计的新协议的安全性，提出安全的基于网络编码 的定向扩散路由协议。 1 3 2 本文所做的主要工作 本文的具体工作如下： 1 、找出原始的定向扩散路由协议d d 在网络资源消耗、网络性能上的缺陷。 2 、针对d d 协议在网络资源消耗、网络性能上的不足，本文提出了基于网 络编码的定向扩散路由协议n c d d 。路由建立过程中采用了网络编码技术。 3 、找出n c d d 协议在安全性上的某些缺陷，并针对n c d d 协议在安全 性能上的不足，提出了增强安全性能的s n c d d 协议。该协议中采用了同态的 签名方案。 4 、由于在原始的定向扩散路由协议中引入了网络编码技术，在n c d d 协 议中加入了同态签名机制，这样必然会对网络的性能产生较大的影响。网络性 能的好坏、负面影响是否在可接受范围之内，都需要验证。为此，采用国际上 公认的权威仿真工具。首先对n s 2 仿真软件进行扩展，在其协议族中加入 n c d d 协议。然后在扩展的n s 仿真平台上对n c d d 协议进行不同网络场景 武汉理工大学硕士学位论文 的仿真：使用s e t d e s t 工具生成动态场景；采用d i f f - s i n k 数据流；编写t c l 源程 序并进行仿真，得到t r a c e 文件；编写a w k 程序对t r a c e 文件进行分析，提取需 要考察的信息；结果使用绘图工具g n u p l o t 绘制成图。仿真结果表明，n c d d 协议比d d 协议在网络结点的平均剩余能量、报文端到端的平均延迟、网络吞 吐量这3 个指标都有较大改善。s n c d d 协议和d d 协议相比，网络结点的平 均剩余能量仍有较大提高。 1 4 论文结构 本文共分为六章，其中第三章至第五章是本人所做的主要研究工作。 第二章第一部分介绍了无线传感器网络的特点、体系结构、协议栈结构和 无线传感器网络路由协议的种类，并对各种路由协议进行了简要说明。第二部 分介绍了定向扩散路由协议，详细描述了该协议的路由建立过程并进行分析， 找出了定向扩散路由协议在网络资源的消耗及网络性能上的缺陷。第三部分主 要介绍网络编码，依次介绍网络编码的概念、理论基础、编码类型、编码算法 以及研究的现状。第四部分对网络编码进行了安全性分析，介绍了同态的签名 算法。第五部分介绍目前广泛使用的网络仿真平台n s 2 以及相关的几个工具。 第三章分析定向扩散路由协议在网络资源消耗及网络性能上的缺陷，在路 由的建立过程中采用网络编码技术，中间转发结点进行网络编码，从而提出一 种新的基于网络编码的定向扩散路由协议。 第四章分析设计的基于网络编码的定向扩散路由协议安全性能的缺陷，利 用同态的签名方案来解决定向扩散路由协议的污染攻击问题，增强了协议的安 全性，提出了一种新的能防污染攻击的定向扩散路由协议。 第五章对新设计的协议n c d d 、s n c d d 进行网络性能仿真。首先修改定 向扩散协议的源文件，重新编译n s 2 ，用扩展的n s 2 仿真平台，先后对新协议 n c d d 和s n c d d 进行性能仿真。编写相应的t c l 文件，对端到端延迟、结点 剩余能量、网络吞吐量进行测试，仿真过程中产生的数据保存在t r a c e 文件中， 使用数据处理工具g a w k 提取t r a c e f i h 的相关数据，最后利用图形绘制工具g n u p l o t 画出相关曲线，从而得到新协议的性能分析。 第六章对整个论文的工作作出了总结，并且对后续的工作作了简要的描述。 4 武汉理工大学硕士学位论文 第2 章背景知识介绍 2 1 无线传感器网络 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 是由部署在检测区域 内的大量廉价微型传感结点组成，通过无线通信方式形成的一个多跳的自组 织的网络系统。其目的是协作地感知、采集和处理网络覆盖区域中感知对象 的信息，发送给观察者。传感器、感知对象和观察着构成了传感器网络的三 i 要素。传感器网络结构如图2 1 所示： 图2 - 1 传感器网络体系结构图 2 1 1 传感器网络的特点 ( 1 ) 传感器网络是大规模网络l ，j 。一方面传感器结点分布在很大的地理区 域内，需要部署大量的传感器结点，为了获取精确信息，传感器结点数量可 能达到成千上万，甚至更多；另一方面，传感器结点部署很密集，在一个面 积不是很大的空间内，密集部署了大量的传感器结点。 ( 2 ) 传感器网络是自组织网络。在传感器网络应用中，传感器结点通常被 放置在没有基础结构的地方，结点的位置没有预先精确设定，结点之间的相互 邻居关系预先也不知道，这样就要求传感器结点具有自组织的能力，能够自 武汉理工大学硕士学位论文 动进行配置和管理，通过拓扑控制机制和网络协议自动形成转发监测数据的 多跳无线网络系统。在传感器网络使用过程中，网络中的结点个数可能动态 地增加或减少，从而使网络的拓扑结构随之动态地变化。传感器网络的自组 织性要能够适应这种网络拓扑结构的动态变化。 ( 3 ) 传感器网络具有动态的系统可重构性。传感器网络的拓扑结构可能因 为下列因素而改变：环境因素或电能耗尽造成的传感器结点出现故障或失 效；环境条件变化可能造成无线通信链路带宽变化，甚至时断时通；传 感器网络的传感器、感知对象和观察者这三要素都可能具有移动性；新结 点的加入。这就要求传感器网络系统要能够适应这种变化。 ( 4 ) 传感器网络必须是可靠的网络。传感器网络特别适合部署在恶劣环境 或人类不宜到达的区域，网络的维护十分困难甚至不可维护。传感器网络的 通信保密性和安全性也十分重要，要防止监测数据被盗取和获取伪造的监测 信息。因此，传感器网络的软硬件必须具有鲁棒性和容错性。 ( 5 ) 传感器网络是与应用相关的网络。传感器网络用来感知客观物理世 界，获取物理世界的信息量。客观物理世界的物理量多种多样，不可穷尽。 不同的传感器网络应用关心不同的物理量，因此对传感器的应用系统也有多 种多样的要求。不同的应用背景对传感器网络的要求不同，其硬件平台、软 件系统和网络协议必然会有很大的差别。针对每一个具体应用来研究传感器 网络技术，这是传感器网络设计不同于传统网络的显著特征。 ( 6 ) 传感器网络是任务型的网络，以数据为中心的网络。脱离传感器谈论 传感器结点没有任何意义。传感器网络中的结点采用结点编号标识，结点标 识是否需要全网唯一取决于网络通信协议的设计。由于传感器结点随机部署， 结点编号与结点位置没有必然关系。用户使用传感器网络查询事件时，直接 将所关心的事件通告给网络，而不是通告给某个确定编号的结点。网络在获 得指定事件信息后汇报给用户。这种以数据本身作为查询或传输线索的思想 更接近于自然语言交流的习惯，所以通常说传感器网络是一个以数据为中心 的网络。 2 1 2 传感器网络的结点的限制 传感器结点在实现各种网络协议和应用时，存在以下一些现实约束【7 】： 6 武汉理工大学硕士学位论文 ( 1 ) 传感器结点的电源能量有限。传感器结点体积微小，通常携带能量十 分有限的电池。传感器结点消耗能量的模块包括传感器模块、处理器模块和 无线通信模块。随着集成电路工艺的进步，处理器和传感器模块的功耗变得 很低，绝大部分能量消耗在无线通信模块上。 ( 2 ) 通信能力有限。无线通信的能量消耗随着通信距离的增加，能耗将急 剧增加，因此，在满足通信连通度的前提下，应尽量减少单跳通信距离。考 虑到传感器结点的能量限制和网络覆盖区域大，传感器网络采用多跳路由的 传输机制。 ( 3 ) 计算和存储能力有限。传感器结点是一种微型嵌入式设备，它价格低、 功耗小，这些限制必然导致其携带的处理器能力比较弱，存储器容量比较小。 2 1 3 无线传感器网络协议栈结构 随着对传感器网络的深入研究，研究人员提出了多个传感器结点上的协议 栈【8 】，这个协议栈包括物理层、数据链路层、网络层、传输层和应用层，和互 联网协议栈的五层协议相对应。此外，协议栈还包括能量管理平台、移动管理 平台和任务管理平台。这些管理平台使得传感器结点能够按照能源高效的方式 协同工作，在结点移动的传感器网络中转发数据，并支持多任务和资源共享。 各层协议和平台的功能如下g 物理层提供简单但健壮的新号调制和无线收发技术；数据链路层负责数据 成帧、帧检测、媒体访问和差错控制；网络层主要负责路由生成和路由选择： 传输层负责数据流的传输控制，是保证通信服务质量的重要部分；应用层包括 一系列基于监测任务的应用层软件；能量管理平台管理传感器结点如何使用能 源，在各个协议层都需要考虑节省能量；移动管理平台检测并注册传感器结点 的移动，维护到汇聚结点的路由，使得传感器结点能够动态跟踪其邻居的位置； 任务管理平台在一个给定的区域内平衡和调度监测任务。 2 1 4 无线传感器网络路由协议类型 k a k k a y a 等 9 1 对当时已有的二十多种无线传感器网络路由协议进行调查 研究，并进行分类，提出了以数据为中心的，分层的和基于地理位置为主的分 类法，并对每个路由协议进行描述和讨论，也对使用网络流和服务质量等方法 7 武汉理工人学硕士学位论文 的协议进行了讨论。从具体的应用角度出发，根据不同的应用对传感器网络各 种特性的敏感度不同，把路由协议分为四种类型：( 1 一量感知路由协议。由于 无线传感器网络中能量的重要性，早期提出的一些传感器网络路由协议往往只 考虑了能量因素，从数据传输中的能量消耗出发，讨论最优能量消耗路径以及 最长网络生存期等问题。( 2 ) 基于查询的路由协议。在环境监测等类似的应用中， 需要不断查询传感器结点采集的数据，查询结点发出查询任务的命令，传感器 结点向查询结点报告采集的数据，通信流量主要是查询结点和传感器结点之间 的命令和数据的传输，同时数据在传输路径上通常要进行融合，通过减少通信 流量来节省能量。( 3 ) 地理位置路由协议。在目标跟踪等类似应用中，往往需要 唤醒距离跟踪目标最近的传感器结点，以得到目标的更精确的位置等相关信息。 把结点的位置信息作为路由选择的依据，不仅能够完成结点路由功能，还可以 降低系统专门维护路由协议的能耗。( 4 ) 可靠的路由协议。无线传感器的某些应 用对通信的服务质量有较高的要求，如可靠性和实时性等，需要设计相应的可 靠的路由协议。 2 2 定向扩散路由协议 2 2 1 定向扩散路由协议介绍 定向扩散【1o j ( d i r e c t e dd i f f u s i o n , d d ) 是一种基于查询的、以数据为中心的 路由机制，其路由的建立过程由周期性的兴趣扩散、梯度建立和路径加强3 个 阶段组成。 图2 - 2 兴趣散布 8 s i n k 心 e 、一 舭 一 弧，一、i=一 一矮 晕 ， - ， 一 t 一 一 一= 武汉理工大学硕士学位论文 e v e n t ，一一 ， s o u r c e t 、一一 图2 - 3 初始梯度建立 s i n k e v e m oo - 一，一一一一一、 i 7s o i r c e 手叫s i n k 、一一一一一， oo 图2 4 数据传送 在兴趣扩散阶段，图2 1 ，汇聚结点周期性地向邻居结点广播兴趣消息。兴 趣是汇聚结点查询的任务，即信息需求，其中含有任务类型、目标区域、发送 数据率、时间戳等参数。兴趣消息由汇聚结点产生并注入网络的，以洪泛传播 的方式发送给所有的结点，这个过程是查找数据源的过程。网络中的每个结点 在本地都有一个兴趣高速缓存，用于存放兴趣列表，列表中都有一个表项用于 记录发来该兴趣消息的邻居结点、数据发送速率和时间戳等任务相关信息，以 建立该结点向汇聚结点传递数据的梯度关系。每个兴趣实体可能对应多个邻居 结点，每个邻居结点对应一个梯度信息。通过定义不同的梯度参数，可以满足 不同的应用需求。每个兴趣都有生存期，超过这个时间，结点将删掉对应的表 项。当结点收到邻居结点的兴趣消息时，首先检查自己的兴趣高速缓存，看兴 趣列表中是否存在参数类型与收到的兴趣相同的表项，而且对应的发送结点是 该邻居结点。如果有对应的表项，就更新表项的有效时间值；如果只是参数类 型相同，但不包含发送该兴趣的邻居结点，则在相应的表项中添加这个邻居结 点：对于其他情况都需要建立一个新的表项来记录这个新的兴趣。如果收到的 兴趣消息和结点刚刚转发的兴趣消息一样，为避免消息循环则丢弃该信息。否 则，转发收到的兴趣消息。梯度终止则应先从兴趣中删除对应的梯度，直到该 9 武汉理工大学硕士学位论文 兴趣中所有的梯度都被删除了，该兴趣在兴趣列表中对应的表项才会被结点清 除。 梯度建立过程是数据源给汇聚结点的回应过程，图2 3 。当传感器结点采集 到与兴趣匹配的数据时，把数据发送到梯度上的邻居结点，并按照梯度上的数 据传输速率设定传感器模块采集数据的速率。由于可能从多个邻居结点收到兴 趣消息，结点向多个邻居结点发送数据，汇聚结点可能收到经过多个路径的相 同数据。中间结点收到其他结点转发的数据后，首先查询兴趣列表的表项，如 果没有匹配的兴趣表项，就丢弃数据。如果存在相应的兴趣表项，则检查与这 个兴趣对应的数据缓冲池，数据缓冲池用来保存最近转发的数据。如果在数据 缓冲池中有与接收到的数据匹配的副本，说明已经转发过这个数据，为避免痴 线传输环路而丢弃这个数据；否则，检查该兴趣表项的邻居结点信息。如果设 置的邻居结点数据发送率大于等于接收的数据速率，则全部转发接收的数据； 如果记录的邻居结点数据发送速率小于接收的数据速率，则按照比例转发。对 于转发的数据，数据缓冲池保留一个副本，并记录转发时间。因为兴趣扩散阶 段是为了建立源结点到汇聚结点的数据传输梯度，数据源结点以较低的速率采 集和发送数据，称这个阶段建立的梯度为探测梯度。 定向扩散路由机制通过正向加强机制来建立优化路径，并根据网络拓扑结 构的变化来修改数据转发的梯度关系。汇聚结点在收到从源结点发来的数据之 后，启动建立到源结点的加强路径，后续数据将沿着加强路径以较高的数据速 率进行传输，图2 4 。加强后的梯度称为数据梯度。路径加强的标准不是唯一的， 可以数据传输延迟作为路由加强的标准，汇聚结点选择首先发来最新数据的邻 居结点作为加强路径的下一跳结点，向该邻居结点发送路径加强消息。路径加 强消息中包含新设定的数据传输速率值。邻居结点收到消息后，经过分析确定 该消息描述的是一个已有的兴趣，只是提高了数据发送速率，则断定这是一条 路径加强消息，从而更新对应兴趣的表项的到邻居结点的发送数据率。同时， 按照同样的规则选择加强路径的下一跳邻居结点。汇聚结点根据数据源的回应 报文逐级选择时间性能最优的链路，最终形成一条从数据源到汇聚结点的加强 路径。在加强路径上的结点，如果发现下一跳结点的发送数据率明显减小，或 者收到来自其他结点的新位置估计，推断加强路径的下一跳结点失效，就需要 使用上述的路径加强机制重新确定下一跳结点。 在基于定向扩散的网络中，每个结点的应用都是已知的。c i n t a n a g o n w i w a t 1 0 武汉理工大学硕士学位论文 等首次提出定向扩散路由协议的时候，是以鲁棒性、可扩展性和能量高效性为 目标，提出了这种新的数据传播方式。定向扩散的最重要的特征是兴趣和数据 的传播、融合都是局部交互作用决定的。c h a l e r r n e ki n t a n a g o n w i w a t 等【1 1 1 对定 向扩散协议的实施，具体问题的解决做了研究，并对定向扩散的性能作了评价， 还和洪泛法、全知的广播作了比较。研究了网络动态因素、数据融合、路径负 加强等方面对协议性能的影响。 2 2 2 定向扩散路由协议的缺陷 定向扩散路由的兴趣扩散阶段，兴趣是以洪泛传播方式发送给所有结点， 能量和时间开销都比较大，而且在梯度建立阶段，报文是作为汇聚结点的回应 信息，传播方向是根据兴趣洪泛传播而建立的反向梯度，能量和时间的开销同 样比较大。路径加强后形成一条从源到汇聚结点的加强路径，若某条链路失效， 必须重建路由，周期性地进行兴趣扩散、梯度建立和路径加强，其中前2 个阶 段的能量和时间开销比较大，不利于无线传感器网络的应用。 y a n r o n gc u i 等【1 2 j ，1 1 1 s h y a nc h e n 等1 1 3 】对定向扩散路由协议进行了改进， 提高了网络性能，能量的有效性有一定提高。但传统的存储转发的路由方式没有 改变。m i nc h e n 等【1 4 j 设计了新的实时过滤器和尽最大努力过滤器，以及相应的 梯度建立、数据传播机制，形成了新的能量有效的定向扩散路由协议。本文采 用新的网络编码技术，提出新的基于网络编码的定向扩散路由协议。 2 3 网络编码 2 - 3 1 网络编码基本思想和理论基础 r u d o l fa h l s w e d e 等【l5 j 第一次提出网络编码的概念。网络编码的基本思想 是网络的中继结点不再只进行数据的存储转发，而是对收到的数据进行处理之 后再发送出去，以达到节省网络资源，提高网络性能的目的。 r u d o l f a h l s w e d e 等从计算机网络应用中提出网络信息流问题，得到网络信 息流的最大流最小割理论：任何带发送结点和接收结点的网络中都存在最大流 和最小割，并且最大流的流值等于最小割的容量。该理论为节省网络资源、提 高网络性能提供了理论依据，理论上网络的传输速率可以达到网络的最大流， 武汉理工大学硕士学位论文 而网络的最大流可以用割的最小容量来计算。 网络的最大流量是从源结点到接收结点的最大传输数据率，广播的最大流 量是指源结点同时向所有接收结点发送同样数据时对每个接收结点所能达到的 最大数据率。多播时，从源结点到每一个接收结点都有一个最大流，这些最大 流中的最小值即是多播的最大流。最大流取决于网络的拓扑结构，即各结点的 连接关系和带宽。因此给定一个网络，拓扑一定的情况下，其理论上的最大流 也就确定了。最大流是网络传输速率的上限。网络编码的目的就是使每个结点 的传输速率接近或达到最大流。 ( 1 ) 网络中的流 在一个网络中传输的信息可以形象地称之为“流。对于给定的网络， 从源结点出来的信息，经过网络上的有向边，最后流入目的结点的信息称为流 量，而每一条边上流过的流量称为流，记为。价，彬。显然，边 ，吁，) 的流 不能超过该边的容量c ( v t ，桫，因此有：0 f ( v 。，v f ) c ( v 。，v ，) ，满足此式的网 络称为相容网络。 对给定的网络n ，若每条边上的流都已知，即相当于在的边集点上定义 了一个函数：f = f ( u ，) i 甜，v ) ，则称f 为网络的流。若某条边( 甜，1 ，) 上 的流等于该边的容量，即f ( u ， ，) = c ( u ，v ) ，则称( 材，v ) 是饱和边，否则称为非饱 和边。 设巧和圪是的顶点集v 的两个子集，用( 巧，巧) 表示起点在巧，终 点在巧的有向边的集合，用f ( ，n ，圪夕表示集合( ，所，乃) 中各边流的总和， 即： f ( v i ，) = f ( u ，v ) 特别，纸缴茉从顶点工流出来的流的和，f ( - g , x ) 表示流进顶点x 的流的总 和，也记为：讹功- 厂，f ( 1 f , x ) 可俐 网络的最大流量即是从源结点到目的结点的最大传输数据率。最大流是针 对某一个具体结点而言，是流的一个上限。广播的最大流量是指源结点同时向 所有接收结点发送同样的数据的时候，每个接收结点能接收的最大数据传输速 率。多播的时候，从源结点到每一个接收结点都有一个最大流，在这些最大流 中值最小的一个就是多播容量。每一条边都有固定的容量，也是该边上流量的 理论上限。因此最大流取决于网络的拓扑结构，即各个结点的连接关系和带宽。 对于一个给定的网络，其最大流也是确定的，也是可以计算的。 1 2 武汉理工大学硕士学位论文 ( 2 ) 网络的割 设网络- 习具有单一发送结点x 和单一接收结点，的割是边集e 的子 集，记为k = ( s ，歹) = ( “，v ) lu s ，v 曩，x s ，y 季) ，其中su 蚕= v ，sn 歹= ， 显然网络的割不是唯一的。 割k 中所有边的容量之和称为该割的容量，记为c a p k ，即c a p k = c ( p ) 由割的定义可知，一个网络的割不是唯一的。同一个网络的多个不筒割的 容量也可能不同，但总有一个割的容量最小，这个最小值是唯一的，对应的割 即网络的最小割。 2 3 2 线性网络编码 网络编码方案可以分为线性编码和非线性编码，相比之下，线性编码要简 单得多。s 一yr l i 等【1 6 】提出了线性网络编码的基本理论，构造了无线网络多 播方案，并用图论的方法证明应用线性网络编码就可以实现网络最大流传输， 即满足最大流最小割定理，同时给出了线性网络的贪婪构造算法。其编码方法 是将传输的信息分成等长的信息向量，网络中的每一条边都事先分配好了一个 编码向量，该边上传输的是信息向量和编码向量的矩阵积。 ( 口b ) 图2 5 确定的线性网络编码图 如图2 5 ，源结点s 多播a ，b 给结点畏和乃原始信息向量为( a ，b ) ，中继结 点c 对接收的信息口，b 进行线性编码( 模2 加法) ，边s a 、s b 、c r 、c t 上的 编码向量分别为( 1 ，o ) 。，( o ，1 ) o ，( 1 ，1 ) 。，( 1 ，1 ) ，目的结点r ，2 1 对收到的信息进行 解码得到原始信息，每条边上传输的信息是信息向量和编码向量的矩阵积。这种 方法是典型的确定性编码，在网络拓扑结构已知且变动不大的情况下，会有很 好的性能，可以很好的应用于有线网络。如果网络的拓扑结构变动频繁，就需 武汉理工大学硕士学位论文 要不断地了解整个网络的拓扑结构，重新给各条边分配编码向量，代价是很大 的。因此这种编码不适用于拓扑结构变动频繁的有线网络，同样，在无线网络 中也不适用，这是因为在无线网络中，结点的加入和退出，链路的失败，环境 的变化等多种原因都可能导致拓扑结构改变。 2 3 3 随机线性网络编码 确定性网络编码的复杂度高，需要了解整个网络的拓扑信息，编码向量依 据网络拓扑结构预先确定，一旦网络拓扑发生变化，如有结点加入或离开、链路 失效等，就要重新确定编码向量，代价很大，因此不适用于无线网络环境。针 对这种情况，h o 和m e d a r d 等【i7 j 提出了随机的线性网络编码的概念，是在一般 的多源多播的网络中，信息传输、压缩的分布式随机线性网络编码方法，它的提 出拓宽了网络编码的适用场景，能够适应网络拓扑的动态变化，使得网络编码 不再局限于确定的网络拓扑和集中式的算法。 随机编码和