（通信与信息系统专业论文）基于网络编码的无线网状网路由技术的研究.pdf

摘要 摘要 2 0 0 0 年，r u d o l fa h l s w e d e 等人首次提出了网络编码的概念，允许和鼓励网 络中的中间节点对数据进行处理。网络编码的最大优点是使组播传输速率达到最 大流最小割定理决定的网络容量的上限。目前，具有稳定拓扑结构的有线网络的 网络编码已经得到了广泛的关注，但是网络编码在无线网络中的研究和应用还处 在探索阶段。本文结合无线网络环境的特点，研究基于网络编码的无线网状网路 由及其实现中的关键技术，主要研究内容归纳如下： 第一章主要介绍了网络编码的基本概念、优缺点以及研究意义，然后介绍了 无线网状网的体系结构及其路由的背景和特点，分析了无线网状网中适于引入网 络编码的特点。 第二章分析了无线网络适合采用网络编码的特点，介绍了无线网络编码在提 高网络吞吐量、节能、增强网络鲁棒性和安全性等方面的应用，分析了无线网络 编码的研究意义，并总结归纳了当前和将来的热门研究方向。 第三章结合无线网状网的特点，从组播和单播两个方面研究基于网络编码的 无线网络路由。基于网络编码的组播路由问题主要是指把哪些数据包采用何种方 法编码到一起。在单播路由方面，分析了无线网状网中可能存在编码机会的三种 拓扑结构，研究了基于“机会主义”的路由和编码感知的路由两种无线网络编码 思想，并介绍了几种现有的基于网络编码的无线网络路由协议。 第四章研究了基于网络编码的无线网络路由在具体实现中所涉及到的关键 技术，重点研究了广播和单播系统中基于网络编码的队列调度算法，提出基于 c r p 思想的编码重传策略和积极进行网络编码的队列调度策略，并对各算法的性 能进行了分析和比较。 第五章结合无线网状网的结构及其路由的背景和特点，提出一种基于流的无 线网络编码算法f n c 。f n c 以逐跳路由协议获得先验参考路径，充分利用每 个节点的路由表信息，在网络状态相对稳定的时间段内对满足条件的数据流持续 进行类似的网络编码操作。仿真结果表明，f n c 比未采用网络编码的传统方案具 有更高的吞吐量和数据包投递率，且性能优于c o p e 。 第六章总结全文，并对未来的后续工作进行了展望。 关键字：网络编码无线网状网路由技术 a b s t r a c t a b s t r a c t n e t w o r kc o d i n gw a sp r o p o s e db yr u d o l fa h l s w e d ee ta 1 i n2 0 0 0 ，w h i c ha l l o w s a n de n c o u r a g e si n t e r m e d i a t en o d e st op r o c e s sp a c k e t s t h eg r e a ta d v a n t a g eo f n e t w o r kc o d i n gi sf o rt r a n s m i s s i o nr a t et or e a c ht h eu p p e rb o u n do fn e t w o r kc a p a c i t y d e t e r m i n e db ym a x - f l o wm i n c u tt h e o r yi nm u l t i c a s t r e c e n t l y , n e t w o r kc o d i n gi n w i r e dn e t w o r k sw h i c hh a v es t a b l et o p o l o g i e sh a sb e e nc o n c e r n e de x t e n s i v e l y , b u tt h e r e s e a r c ha n da p p l i c a t i o no fn e t w o r kc o d i n gi nw i r e l e s sn e t w o r k sa r es t i l li nt h e p r i m a r ys t a g e b a s e do nt h ec h a r a c t e r i s t i c so fw i r e l e s sn e t w o r k ，t h i st h e s i sr e s e a r c h e s n e t w o r kc o d i n gb a s e dr o u t i n gi nw i r e l e s sm e s hn e t w o r k sa n dc r i t i c a lt e c h n o l o g i e si n p r a c t i c e t h em a j o rc o n t e n t so f t h i st h e s i sa m l i s t e da sf o l l o w s ： c h a p t e r1m a i n l yi n t r o d u c e st h eb a s i ci d e a ，a d v a n t a g e sa n dd i s a d v a n t a g e s ，a n d r e s e a r c hs i g n i f i c a n c eo fn e t w o r kc o d i n g ，p r e s e n t st h es y s t e ms t r u c t u r e sa n dr o u t i n gi n w i r e l e s sm e s hn e t w o r k s ，a n da n a l y z e st h ec h a r a c t e r i s t i c sf o ri n t r o d u c i n gn e t w o r k c o d i n gi n t ow i r e l e s sm e s hn e t w o r k s c h a p t e r2a n a l y z e st h ec h a r a c t e r i s t i c so fw i r e l e s sn e t w o r k ss u i t a b l ef o rn e t w o r k c o d i n g ，p r e s e n t sa p p l i c a t i o n so fw i r e l e s sn e t w o r kc o d i n g i n i n c r e a s i n gn e t w o r k t h r o u g h p u t ，s a v i n ge n e r g y , e n h a n c i n gr o b u s t n e s sa n ds e c u r i t ye r e ，a n a l y z e st h e r e s e a r c hs i g n i f i c a n c eo fw i r e l e s sn e t w o r kc o d i n g ，a n dc o n c l u d e st h eh o tr e s e a r c h d i r e c t i o n si nt h ep r e s e n ta n df u t u r e c h a p t e r3s t u d i e so nn e t w o r kc o d i n gb a s e dr o u t i n gi nw i r e l e s sn e t w o r k sf o r m u l t i c a s ta n du n i c a s t b a s e do nt h ec h a r a c t e r i s t i c so fw i r e l e s sm e s hn e t w o r k s t h e m a i np r o b l e mi nm u l t i c a s tr o u t i n gw i t hn e t w o r kc o d i n gi sc h o o s i n gw h i c hp a c k e t st o c o d et o g e t h e ra n du s i n gw h i c hc o d i n gs t r a t e g y o nu n i c a s tr o u t i n g ，t h i sc h a p t e r a n a l y z e st h r e ek i n d so ft o p o l o g i e si nw i r e l e s sm e s hn e t w o r k si nw h i c ht h e r em a y b e n e t w o r kc o d i n g o p p o r t u n i t i e s ，s t u d i e s t w oi d e a so fw i r e l e s sn e t w o r kc o d i n g ： o p p o r t u n i s t i cr o u t i n ga n dc o d i n g a w a r er o u t i n g ，a n dd e s c r i b e ss e v e r a le x i s t i n g w i r e l e s sr o u t i n gp r o t o c o l sw i t hn e t w o r kc o d i n g c h a p t e r4s t u d i e sc r i t i c a lt e c h n o l o g i e si nt h ei m p l e m e n t a t i o no f n e t w o r kc o d i n g b a s e dr o u t i n gi nw i r e l e s sn e t w o r k s q u e u es c h e d u l i n gw i t hn e t w o r kc o d i n gi n m u l t i c a s ta n du n i c a s ts y s t e m si st h ef o c a lp o i n to ft h i sc h a p t e r t h i sc h a p t e rp r o p o s e s ac r p b a s e dc o d i n gr e t r a n s m i s s i o np o l i c ya n da na c t i v en e t w o r kc o d i n gp o l i c yf o r q u e u es c h e d u l i n g ，a n a l y z e sa n dc o m p a r e st h ep e r f o r m a n c e o fe a c hs t r a t e g y a b s t r a c t -一一一 c h a p t e r5p r o p o s e saf l o wb a s e dw i r e l e s sn e t w o r kc o d i n gs t r a t e g y ( f n c ) ， i n t e g r a t i n gw i t ht h es t r u c t u r ea n dr o u t i n gi nw i r e l e s sm e s hn e t w o r k s f n cu s e s h o p b y 。h o pr o u t i n gp r o t o c o lt og e tp r i o rp a t h s ，d e t e c t sc o d i n go p p o r t u n i t i e sb yu s i n g t h ei n f o r m a t i o ni ne a c hn o d e sr o u t i n gt a b l e ，a n dc o n t i n u o u s l ye n c o d e s t h o s ep a c k e t s f r o md i f f e r e n tf l o w sw h i c hs a t i s f yt h ec o d i n gc o n d i t i o n sd u r i n gt h ep e r i o dw h e nt h e n e t w o r ki s r e l a t i v e l ys t a b l e s i m u l a t i o nr e s u l t ss h o wt h a tf n cc a ng e tb e t t e r t h r o u g h p u ta n dp a c k e td e l i v e r yr a t i ot h a nt h es t r a t e g yw i t h o u tn e t w o r kc o d i n ga n d c o p f c h a p t e r6c o n c l u d e st h ew h o l et h e s i sa n dd i s c u s s e st h ef u r t h e rw o r k k e yw o r d s ：n e t w o r kc o d i n g ，w i r e l e s sm e s hn e t w o r k s ，r o u t i n g t e c h n o l o g i e s 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：奎验脸 ) 叼年皇月y - 日 第一章绪论 1 1网络编码概述 第一章绪论 在现有通信网络中，网络节点只是对收到的信息进行存储和转发，扮演着转 发器的角色。但是从信息理论的观点来看，没有理由让节点只能进行存储转发， 可以让节点对多条输入边上收到的信息进行一定的线性或非线性操作( 编码) ， 然后再发送出去，起到编码器的作用，从而提高网络的吞吐量。网络编码正是根 据这一思想而产生的。在接收节点上，通过一定的运算，可以译码得到信源所发 信息。 1 1 1 网络编码的提出 2 0 0 0 年，r u d o l fa h l s w e d e 等人首次提出了网络编码的概念。简单地说， 网络编码就是允许和鼓励网络中的中间节点对数据进行处理，例如：进行线性组 合。 传统意义上，编码一般只应用在源节点上，即信源编码，用来对冗余数据进 行压缩，或防止网络中信息的损失；也有应用在信道上的，即信道编码，用来降 低错误率，提高可靠性。网络的任务就是正确传输源节点发出的未经修改的信息。 相反地，网络编码则把信息当作数学意义上的可操作实体，而不是单纯地传输未 经修改的源信息。网络编码允许网络中的中间节点对输入的不同信息进行一些操 作。 图1 1 单源两信宿网络编码示例 第一章绪论 图1 1 是一个经典的网络编码示例：一个单源两信宿的网络。图1 1 ( a ) 显 示了网络中每条连接的容量，根据最大流最小割定理“副，容易计算出从s 到t t ( 1 = 1 ，2 ) 的最大流为2 ，s 可以同时向t l 和乞发送两个比特。图1 1 ( b ) 设计 了一个可以达到最大速率的方案，明显地，每个接收节点可以从收到的数据中正 确推导出源节点发送的两个比特。需要指出的是：在这种特定的结构中，如果不 采用网络编码是不可能以两比特的速率传输数据的。 1 1 2 线性网络编码 线性网络编码，是指将一个数据分组看作是一个基本域上的一个矢量，允许 节点在传输之前对其进行线性变换。文献 3 8 证明了：线性编码足以实现最优， 即达到从源到接收节点的最大流。目前，组播集中式线性网络编码算法主要有两 种：代数构造方法乜1 和多项式时间算法0 9 i 。 1 1 2 1 线性网络编码的数学描述 考虑一个通信网络( g ，s ) ，g 是一个有限有向多重图，s 为源。假设g 中的 信道是无损通信链路，每个信道的容量为l 。通信网络( g ，s ) 上的线性编码组 播v 是指为每个节点x 分配矢量空间v ( x ) ，为每个信道x y 分配矢量v ( x y ) ，使得： 1 ) v ( s ) = q ，q 表示一个足够大的基本域上的矢量空间； 2 ) 对每个信道x y ，有：v ( x y ) v ( x ) ； 3 ) 对网络中的任何一个非源节点集合f ，有： = 4 ) 分配给节点t 的输出信道的矢量必是分配给t 的输入信道的矢量的线性组合。 由上述定义可知：一个通信网络上的线性编码组播完全由分配给信道的矢量 决定。4 ) 可看作是在一个节点的信息流定理。当网络中包含有向环时，该定理 不适用于节点集，因此4 ) 只适用于单个节点。对于无环网络的线性编码组播， 该定理既适用于单个节点，也适用于节点集。 一个信道x y 上的数据流是信息( 行) 向量与( 列) 向量v ( ) ( 1 ) 的矩阵乘积。 由于分配给x 的输出信道的向量是分配给x 的输入信道的向量的线性组合，因此， 从x 流出的信道上的数据是流入x 的信道上的数据的线性组合。到达节点t 的信 息总量由矢量空间v ( t ) 给出。 1 1 2 2 线性网络编码的编解码过程 假设一个节点v 收到了对源信息( x ，x z ，勘) 的n 个编码信息( y ，少z ，弘) ， 其中每个编码帧弦中都包含了相应的编码矢量( 守，黟：，一，勋) ，即： 第一章绪论 聍噌j = 乃 m - ， 艮刊撇 m 2 ， 矩阵( 毋) 就称为节点v 的系统转移矩阵或编码矩阵。为了从编码信息矢量 ( y l ，y z ，弦) 中解出源信息( j c l ，x 2 ，渤) ，矩阵( 毋) 必须是可逆的，从而有： 口讨1 夕( p ) = m e ( p ) 如) ( 1 - 4 ) 6 ( p ) = m e ( p ) 6 ( p ) ( 1 6 ) 1 1 3 网络编码的优缺点 与传统的网络运行方法相比，网络编码具有以下优点： ( 1 ) 提高网络吞吐量 网络编码可以使组播传输速率达到最大流最小割定理决定的网络容量的 上限，这也是网络编码的最大优点。当信宿个数大于等于2 时，通常需要采用 第一章绪论 网络编码来达到最佳组播。给定一个网络中各个连接的容量，最佳组播的问题 就是计算出源节点与一系列接收节点之间可能的最大组播吞吐量。如果允许中 间节点( 如路由器) 在继续向前传送收到的数据前对其进行编码，就可以获得 资源的最大利用，达到理论上的最大流的传输速率。每个具有网络编码功能的 节点从所有输入的连接中接收信息，编码，然后发送编码信息至所有输出连接。 ( 2 ) 节省网络带宽资源消耗 对于相同的组播速率，基于网络编码的组播与传统的i p 组播相比，可以节 省对网络带宽资源的消耗。如图1 2 所示，信源s 要向信宿t - ，f z ，t ，发送两比特 信息，图1 2 ( a ) 显示了网络中每条连接的容量。采用网络编码时( 如图1 2 ( b ) 所示) ，整个网络只需传送9 比特，即占有的网络带宽为9 。如果不采用网 络编码，至少还需多传送一个比特，才能使t l ，t 2 ，t 3 都恢复出a 和b ( 如图l 。2 ( c ) 所示) 。由此可以看出，一个简单的网络编码就节省了1 0 的带宽。 ( c ) 图1 2 单信源三信宿网络示例 ( 3 ) 提高网络的鲁棒性 实际网络中，网络节点和链路经常会失效，从而影响网络的鲁棒性。当组播 通信中的链路失效时，传统的网络链接恢复方法是基于整个网络的重新路由。文 献 2 证明了：在组播设置下，存在可以提供最大鲁棒性网络的编码策略和适用 于不同链路失效类型的通用方案。对基于网络编码的组播网络，当网络中的链路 失效时，若接收节点和信源的最小割仍大于信源的信息发送速率，则存在一种静 态的网络编码方式，可以采用基于接收节点的网络链路恢复方法。该方法不需要 网络重新路由，只需接收节点根据不同的链路失效情况进行不同的译码变换，而 不需改变其它内部节点的编码变换就可以恢复出信源发送的数据信息。相对于传 统的基于路径的失效恢复方法，该方法可有效地节省网络带宽资源，且当有效链 路失效时，不存在数据丢失问题。 ( 4 ) 均衡网络负载 现有的组播路由协议主要分为基于核心节点的路由和基于信源的路由。基于 4 第一章绪论 核心节点的路由经常会造成流量过分集中于某一节点。而基于信源的组播路由也 会由于多个组播树的叠加，造成某一链路流量的过载，影响网络的服务质量。基 于网络编码的组播利用多条路径进行信息数据的传输，可以均衡网络链路的负 载。如图1 2 所示的简单例子中，采用网络编码时，每条链路传输i 比特信息，而 不采用网络编码时，至少有一条链路要比别的链路多传输1 比特的信息。 此外，网络编码还具有节省无线网络节点的能量消耗、减少信息传播的路径 时延、提高网络的纠错效率等优点。 任何事物都有两面性，网络编码也有一些缺点：信息的丢失会引起连锁反应， 一个包的丢失会引起多个包不能解码；在某个特定的接收节点上，只有当所有解 码所需的包到达( 即接收到足够数目的数据包) 后才能开始解码，等等。 1 1 4 网络编码的研究意义与发展前景 编码一开始只应用于物理层，而在更高的层里能否带来好处曾经争议了好多 年。网络编码的主要思想是：允许和鼓励中间节点对数据编码组合，这样就可以 达到s h a n n o n 提出的网络容量的上限。网络编码给出了一种新的强有力的角度和 方法来帮助解决网络发展中存在的一些理论上和实际中的问题，它将原先分立于 物理层和网络层的两个核心概念“编码”和“路由”有机地融为一体，彻底改变 了交换路由器只能对信息进行存储转发的传统多播模式，建立起一种全新的网 络体系结构及信息编码和传输模式。 网络编码代表了一种协同工作的理念，这使得它的应用不局限于改进多播和 增加网络容量。网络编码与其它技术相结合，已经应用于网络管理、纠错、信息 安全、p 2 p 对等网络通信、路由和交换等数十个领域。网络编码已迅速发展成为 一个重要的研究热点，并对信息论、编码、通讯网络、网络交换理论、无线通讯、 计算机科学、密码学、运筹学、矩阵理论等方面的研究影响深远。网络编码更是 现今世界各地一流大学及工业实验室最热门的研究领域之一。 以网络编码为核心技术，微软公司开发出了“雪崩”( a v a l a n c h e ) 原型软件。 “雪崩 用于p 2 p 通信的大规模数据分发，传送速度可高出b t ( b i tt o r r e n t ) 2 0 3 0 。由于p 2 p 通信占互联网频宽的六成以上，网络编码的影响极为深远。 不难预测，未来几年，计算机、无线电以及其他各类通信，都会广泛应用网 络编码。网络编码带给网络应用的是一场范式革命，它将对网络的规划设计产生 重大影响。 5 第一章绪论 1 2 无线网状网的体系结构和路由技术 1 2 1无线网状网介绍 随着人们对网络通信需求的不断提高，人们希望在任何时间、任何地点、与 任何人都能够进行快速准确的通信。为了达到通信的“无处不在”。一种新型的 无线网络技术无线网状网( w i r e l e s sm e s hn e t w o r k s ，w m n s ) 应运而生。 简单地说，无线网状网就像是由一些固定的路由器组成的一种网络，只不过 它们之间只能通过无线链路建立连接。无线网状网采用的是一种网状结构，各用 户节点可以通过相邻的其他用户节点，以多跳方式实现到骨干网的连接。新用户 可以通过它周围的其他用户节点很方便地接入到网络中。由于在网络扩展时不再 需要中心节点，无线网状网可以极大地减少整个网络的建设成本。 无线网状网中有两种类型的节点：路由节点( m e s hr o u t e r s ，m r ) 和客户节 点( m e s hc 1 i e n t s ，m e ) 。终端用户设备( c l i e n t ) 兼备主机和路由器两种角色： 一方面，节点作为主机运行相关的应用程序；另一方面，节点作为路由器需要运 行相关的路由协议，参与路由发现、路由维护等常见的路由操作。 根据节点功能的不同，无线网状网可以分为三种典型结构：骨干网 ( i n f r a s t r u c t u r e b a c k b o n e 聊f i n s ) 、客户网( c l i e n tw s ) 、混合网( h y b r i d 矾悄s ) 。 ( 1 ) 骨干网 如图1 - 3 所示，骨干网是由路由节点通过无线链路建立的网状网络。具有网关 功能的路由节点可直接连接到i n t e r n e t 上。如果普通客户节点采用与路由节点相 同的无线电技术，就可直接连接到路由节点上；如果客户节点采用与路由节点不 同的无线电技术，则需先连接到一个具有以太接口的基站上，再通过基站连接到 路由节点上。图中实线和虚线分别代表有线和无线链路。 w m n 骨干网是最常用的网络类型，本文对基于网络编码的w m n 路由技术的研究 主要就是基于骨干网的。 第一章绪论 图1 3w 州骨干网示意图 ，豸f 蕻二凌、 憋啬，过、i i ：渺 囝14 州客户网示意图 第一章绪论 ( 3 ) 混合网络 顾名思义，混合网络即是将上述两种网络相结合，如图l - 5 所不，它提供与其 它多种网络的连通性，比如：i n t e r n e t 、叭f i 、w b t a x 、蜂窝网和传感器网络。在 这种网络中，客户节点既可以与路由节点连接，也可蚍与其它客户节点直接相连。 而且，客户节点的路由功能也进一步提高了w 删的连通性和覆盖能力。 7 、弋 一一- 等躲挈 蠡一、妪_ 尊 w i t h ”r 、i 圈】5m “混台阿示意图 22 无线网状网路由的背景和特点 删n 宽带接入网中一个很重要的问题是路由选择，例如从节点a 到节点b ，可 阻经过不同的用户站中转，存在多条路径于是选择哪条路径就成为一个关键问 题，这将直接影响系统的性能。而且，当节点增加或是减少时，无线网状阿的拓 扑结构会发生变化，路由选择问题变得更加复杂。采用无线网状网技术还会带 来“隐藏终端”问题，需要进一步研究解决。 w 删是移动a dh o c 网络的一种特殊形态，它继承了a dh o c 网络的特点，具有自 配置、自组织与自管理等特性，所以部分传统的a dh o c 网络路由协议在w m n 中仍然 可用，但需要在删路由协议设计中考虑其特殊性。 w n 的路由协议可以参考a dh o c 网络现有的一些路由协议。a dh o c 网络的路 由协议大致可以分为先应式( p r o a c t i v e ) 路由协议、反应式( r e a c t i v e ) 路由协议 她奄一 。甄 髫 琴熊蠢| ) 第一章绪论 以及混合式路由协议。目前几种典型的路由协议有：d s d v 口习( d e s t i n a t i o n s e q u e n c e dd i s t a n c ev e c t o r ) 、d s r 2 6 1 ( d y n a m i cs o u r c er o u t i n g ) 、t o r a 2 7 ( t e m p o r a l l y - o r d e r e dr o u t i n ga l g o r i t h m ) 和a o d v 幅( a dh o co n d e m a n d d i s t a n c ev e c t o rr o u t i n g ) 。微软公司提出的一种多无线收发器、多跳无线网络 的路由协议m r l q s r 瞄9 1 ，主要思想是在d s r 协议的基础上采用最大吞吐量准则，已 经开始考虑w m n 的特征。 由于w m n 的特殊性，在设计w m n 路由协议时，必须考虑以下因素： ( 1 ) 路由判据：许多已有的a dh o c 网络路由协议均以最小跳数作为路由判据，研 究表明，大多数情况下，该路由判据的性能并不是最优的。例如两节点之间选择跳 数最小的路径，由于干扰冲突、通信距离等因素的影响，使该路径的链路质量恶化， 从源节点到目的节点的端到端吞吐量、误码率等性能将变得很差。为解决因路径 质量差而影响网络吞吐量等性能的问题，要求w m n 采用一种新的路由判据，并且该 判据能正确反映出链路质量对各指标的影响。 ( 2 ) 负载均衡：在w m n 中，所有节点通过路由共享网络资源，因此，w m n 路由协议必 须满足负载均衡这一要求。当网络中某些节点发生拥塞，并成为整个网络的瓶颈 节点时，新的业务流应能“绕过”这些节点。可以从两方面来解决该问题：通过路 由发现机制在业务流建立阶段“绕过”网络中的拥塞区；利用路由维护机制在链 路发现拥塞时，自动选择其他路径进行数据传输。 ( 3 ) 路由容错：在w m n 中，路由发生错误时，需要尽快完成路由重建，以避免服务中 断。一般有两种重建方法：一种是利用缓存路由进行数据发送；另一种是通过重 新执行路由查找过程实现路由重建。在w m n 中，由于m r 移动性小，路由错误往往是 由数据冲突造成的，并非实际链路断裂造成。有两种方法可以解决该矛盾：利用 跨层设计机制，在m a c 层对因冲突而发送失败的数据包进行二次处理；对节点增加 路由缓存功能，缓存暂时不能发送的数据包，待无线信道质量变好时再次尝试发 送。 ( 4 ) 网络资源消耗：随着网络规模的扩大，利用广播机制进行路由查找的方法会 消耗很多网络资源。同时，由于大规模网络建立路径时将花费很长时间，使端到端 的延时变大，一旦路径建立起来，由于路径发生变化又需要消耗很大的网络资源 进行路由重建。 ( 5 ) 如何在w m n 中为用户提供q o s 保证也是一个重要的研究课题。 1 2 3 几种典型的无线网状网路由协议 无线网状网路由协议的研究主要包括两个方面：一是使用传统a dh o c 网络 中开发出来的路由协议，并结合无线网状网的特性进行一些修改；另一方面是研 第一章绪论 究专用于无线网状网的路由协议。本节将介绍无线多跳网络中几个典型的路由协 议，其中包括本文第五章多次提到的a o d v 路由协议。 1 2 3 1a dh o c 按需距离矢量路由协议a o d v a o d v 晗耵是在d s d v 和d s r 协议基础上建立起来的一种按需距离矢量路由协议。 它借用了d s r 中的路由发现和维护过程，以及d s d v 中的逐跳路由、顺序编号和 路由维护的周期更新机制。 a o d v 使用简单的请求一应答机制进行路由发现( 如图1 6 ) 。当源节点s 要给 目的节点d 发送数据包，但路由表中没有到达d 的路由时，s 会发起一个路由发现 过程。源节点首先广播路由请求分组( r r e q ：r o u t er e q u e s t ，如图1 6 ( a ) ) ，邻 居节点收到广播后再向其它邻居节点广播，直到到达目的节点或者已有最新路由 的中间节点。r r e q 分组中的序列号可以避免环路，并保证中间节点只回应最新的 r r e q 。在路由发现过程中，如果节点收到来自不同节点转发的相同序列号的r r e q ， 则直接丢弃，减少不必要的广播。扩散r r e q 的时候，收至u r r e q 的节点根据请求分 组内容和发送广播的上一跳节点，建立指向源节点的反向路由( 需要双向链路的 支持，a o d v 缺省假设网络链路是双向的) 。如果r r e q 分组传递到目的节点或者中 间某个具有有效路由的节点，那么该节点单播返回路由应答分组( r r e p ：r o u t e r e p l y ，如图1 6 ( b ) ) 。收n r r e p 的节点，查找之前通过r r e q 所建立的指向源节点 的反向路由，将r r e p 逐跳转发至源节点。最终，如果存在一条到达目的节点的路 径，源节点s 将接收到一个r r e p 消息。这时，源节点缓存中的数据包就可以通过 新发现的路径发送到目的节点了。 一一r r e q ( a ) 路由请求 o o 9 m oo ( b ) 路由应答 图1 6a o d v 路由发现过程 a o d v 协议中，节点通过周期性地广播h e l l o 消息来判断链路状态，如果当前 节点连续几个周期未收到来自邻居节点的h e l l o 消息，就认为本节点到该邻居节 点的链路已断开，当前节点就删除包含该链路的路由信息，发送路由错误消息 第一章绪论 ( r r e r ：r o u t ee r r o r ) ，通知相邻节点和相应的上游节点删除因链路断开而导致目 的节点不可达的路由信息。 1 2 3 2一种单接口多信道路由协议叫c r p 无线多跳网络的性能经常随着用户的增多而降低，其中一个重要原因就是多 用户共享一个信道。虽然i e e e8 0 2 1 l 标准允许配置多个信道，但是1 】l m n 中的设 备大都只有一个收发装置，一个节点一次只能侦听一个信道，因而单接口多信道 协议的设计十分必要。 j u n g m i ns o 等人提出的m c r p ( m u l t i - c h a n n e lr o u t i n gp r o t o c 0 1 ) 协议阳伽就 是一种考虑了信道分配的单接口多信道路由协议，它在网络层考虑多个信道，而 在m a c 层采用单信道协议( 如：i e e e8 0 2 1 1d c f ) 。m c r p 为同一数据流中的所 有节点分配一个公共信道，允许节点转换信道，但是不允许同一个数据流中的两 个连续节点转换信道，以免产生耳聋问题。 m c r p 的优点是：使用多信道，而不需要改变m a c 层的协议；通过给不同的数 据流分配不同的信道改善网络性能，因此在一个区域内允许多个传输同时进行； m c r p 能够明显提高吞吐量，并且不需要额外的硬件设备。 1 2 3 3 多射频链路质量源路由协议堋r l 0 s r m r - l q s r ( m u l t i r a d i ol i n k - q u a l i t ys o u r c er o u t i n g ) 是微软公司研发 的多信道w m n 路由协议，采用了一种新的路由性能判据加权累计传输时间 w c e t t ( w e i g h t e dc u m u l a t i v ee x p e c t e dt r a n s m is s i o nt i m e ) 。w c e t t 综合考 虑了带宽等链路性能参数以及最小跳数等因素( 见式( 卜7 ) ) 。因此m r - l q s r 能在吞吐量与延时之间获得一种平衡。 l w c e t t = ( 1 一) 宰 e t tl + ：i cm a x x ( 卜7 ) 百 1 5 ，纵 其中，x =： e t t ，e t t ( e x p e c t e dt r a n s m i s s i o nt i m e ) 为期望传输 h o p i i 石k n n d j 时间，1 3 是一个可调参数，且0 b 1 。 m r - l q s r 是将l q s r 协议和w c e t t 判据相结合得到的一种路由协议，是在传统的 d s r 路由协议的基础上进行的改进，不但需要获得路径中节点和其邻居链路相关 的状态信息，而且还要综合链路状态信息来评价链路质量的优劣，从而形成自身 的路由判据。 与其他的多射频路由判据( 如：e t x ( e x p e c t e dt r a n s m i s s i o nc o u n t ，期望 传输次数) ) 相比，m r - l q s r 能够提高吞吐量，这主要是由于m r - l q s r 考虑了备 选路径的端到端延时和路径吞吐量之间的平衡。m r - l q s r 的一个明显缺点是没有 第一章绪论 考虑相邻链路的信道干扰这个重要因素，这在另外一个路由判据m i c b ”( m e t r i c o fi n t e r f e r e n c ea n dc h a n n e l s w i t c h i n g ) 中得到了解决。 1 2 3 4 混合无线网状网协议h w m p h w m p 眵副( h y b r i dw i r e l e s sm e s hp r o t o c 0 1 ) 是i e e e8 0 2 1 l s 草案标准规定 的路由协议，是a o d v 与基于生成树的路由协议的综合，结合了先应式和反应式 两种构件，把按需路由发现的灵活性与通往m p p ( m e s hp o r t a l ，网状网入口) 的有 效的先验式路由相结合。 如果w m n 没有配置根节点，则对w m n 的所有路由使用按需路由发现。h w m p 的按需路由使用a o d v 的路由请求( r r e q ) 和路由应答( r r e p ) 机制在两个 4 p ( m e s h p o i n t ，网状网节点) 之间建立路由。原始的a o d v 是为基于i p 的网络和第三层路 由开发的。h w m p 对原始a o d v 进行了改进，使其适用于第2 层的工作，并把所有 的i p 和i p 地址改成了m a c 和m a c 地址。此外，相比跳数判据而言，h w m p 能充 分利用更精确的路由判据( 如：射频感知判据) 。 如果w 脒中的一个m p ( 一般以m p p 为典型) 被选择配置为根节点，其他的 m p 使用原始的拓扑发现来先验地维护通往根节点的路由。w m n 的根节点首先广播 根通知消息发布自己的存在。其他节点收到根通知消息后，通过路由请求和应答 机制在自己的路由表中维护自己到根节点的路由。当源节点s 要向目的节点d 发送数据时，s 先在自己的路由表中查找到d 的路由。如果路由表中有到d 的有 效路由，s 就沿该路由发送数据。如果路由表中没有到d 的路由或者路由失效， s 将直接通过到根节点的路由把数据包发给根节点，然后再由根节点对该数据包 进行转发。 1 。2 4 无线网状网适于引入网络编码的特点 无线网状网作为一种独特的网络组织方式，不仅具备无线网络编码的一般特 点，还具有与其网络环境和组网方式密切相关的特性。 ( 1 ) 覆盖广 在无线网状网中，由于节点间距很短，每个节点只需保持较低的发射功率就 可以建立连接，这就意味着用户的加入不像无线局域网那样受发射功率的影响。 另一方面，较短的节点间距也意味着传输受到障碍物阻挡的可能性降低，因而无 线网状网的覆盖率较高，每个节点覆盖范围内的邻居节点较多，这就在一定程度 上增加了潜在的编码机会。 ( 2 ) 连接度高 在传统的点对点网络中，节点的接入采用星型结构，即多个节点首先接入到 第一章绪论 一个中心节点，再由中心节点接入到网络中。这样，中心节点就成了瓶颈，一旦 出故障，就会影响到整个网络的正常工作。而在无线网状网中，链路为网状结构， 每个节点可使用的链路数大大增加，且每个网络节点都具有链路功能，如果其中 的某一条链路出了故障，节点便可以自动转移到其他可选链路进行接入。在采用 了网络编码的系统中，无线网状网的这种冗余链路在一定程度上增加了节点解码 成功的概率。 ( 3 ) 拓扑结构相对稳定 在无线网状网最常用的网络类型删n 骨干网中，节点大都静止不动，拓 扑结构相对稳定，就像是有线i n t e r n e t 网络的无线化，这不仅增强了网络的健 壮性，降低了对网络编码策略的要求，又使有线网络中网络编码的研究成果可以 方便地扩展到无线网状网中去。 1 3 研究目标和思路 网络编码已经引起越来越多的研究人员的重视，然而，对网络编码及其应用 的研究仍然处于初级阶段，大多数都是基于理论的研究，而且通常采用简化的模 型，对实际应用环境和系统模型的考虑不多。无线网络物理层的广播特性、无线 链路的不可靠性、无线节点的发射功率特性等，使得网络编码更适合于无线网络。 本文将致力于研究无线网络环境下的网络编码。 目前，对无线网络环境中网络编码的研究主要集中在对网络吞吐量、能量消 耗、算法复杂度等的理论研究方面，也有不少文献研究了网络编码对无线网络中 组播性能的改善。无线网络的特性使得网络编码不仅能够应用于组播，而且也能 为无线网络中的单播带来益处。本文正是要充分利用无线网络的特性和网络编码 的优点，研究基于网络编码的无线网状网路由技术。 本文对无线网络编码的研究大多都是以无线网状网的骨干网络为背景的，其 中基于网络编码的无线网络路由及其具体实现中的关键技术是本文研究的重点。 1 4 论文主要内容和结构 本文首先介绍了无线网络编码的特点、应用和研究现状，分析总结了组播和 单播场景下基于网络编码的无线网络路由协议。然后研究了基于网络编码的无线 网络路由协议在具体实现过程中涉及到的关键技术，并从几个方面提出了可能的 解决方案。在本文的最后，我们以无线网状网为背景，将路由技术与网络编码相 结合，提出一种基于流的无线网络编码。 第一章绪论 本文共分六章，内容组织如下： 第一章绪论，首先介绍了本文研究内容所涉及的两个关键的背景知识：网络 编码和无线网状网路由技术。然后简述了本文的研究目标和思路，最后简单介绍 了本文的主要内容，并说明了论文的结构安排。 第二章结合无线网络环