（计算机软件与理论专业论文）网络编码感知的无线网络路由机制的研究.pdf

网络编码感知的无线网络路由机制的研究 网络编码感知的无线网络路由机制的研究 专业：计算机软件与理论 博士生：樊凯 指导老师：龙冬阳教授 摘要 网络编码打破了通信网络中传统的信息处理方式，目前已经取得了巨大的进 展。作为网络编码思想在无线网络中的扩展，针对无线单播传输的网络编码机制 已经成为当前的一个研究热点。论文涉及无线单播网络编码机制在无线网络中的 实际应用，主要研究了以下几个问题： 首先，基于“机会 的无线单播网络编码机制c o p e 将对无线网络已有的其 它应用产生怎样的影响? 目前对c o p e 机制的改进以及新的无线单播网络编码机 制其性能到底如何? 针对这两个问题，论文在第二章提出网络仿真器n s 2 上的网 络编码扩展的无线模型( e w m c ) 。基于c o p e 机制的特性和网络体系结构的分层 思想，在分析n s 2 的无线模型架构的基础上，通过在n s 2 无线模型的核心：无 线节点模型中引入通用的网络编码层并对数据包传输流程进行调整来实现编码 机制。此外针对c o p e 机制的编) 樨码算法难以实际应用的局限性，论文基于对 c o p e 机制研究的最新理论结果在该扩展模型中提出适用于实际情况的多项式时 间编解码算法。仿真结果显示在一个节点低速移动的无线a d h o c 网络中c o p e 机制对网络吞吐量的提高约为9 。8 ，有效地验证了该扩展模型的可行性。 其次，c o p e 机制中编码机会的数量依赖于传统无线路由协议所建立的数据 传输路径，这在实际应用中大大地制约了c o p e 机制的性能。论文的第三章关注 这个问题，在链路丢包率为零的理想网络条件下提出一个无线m e s h 网络中支持 c o p e 机制有效应用的按需路由协议( o c r ) 。该协议使用一个将编码带来的收益 和路径跳数综合考虑的路由量度来发现拥有编码机会的高吞吐量路径，此外其采 用的优化策略能够快速地发现潜在的编码机会并能降低协议的消息复杂度。论文 同时证明了该协议具有的几点性质：( 1 ) 该协议所发现的路径是无环的；( 2 ) 该协议 网络编码感知的无线网络路由机制的研究 所采用的优化策略不会对最佳路径的发现造成影响；( 3 ) 该协议的消息复杂度介于 a o d v 协议的消息复杂度和该协议相关工作的消息复杂度之间。论文的仿真实验 结果指出：( 1 ) 基于第三章对网络的假设条件，在一个特定无线m e s h 网络拓扑中 c o p e 机制可能无法显示出其提高网络吞吐量的特性( 对网络吞吐量的提高仅为 3 6 ，非常微弱) ，而该协议能够有效地打破这种局限性( 使用该协议建立数据传 输路径后编码对网络吞吐量的提高可达2 1 6 ) ；( 2 ) 该协议所发现的编码机会与传 统无线路由协议相比增加约6 6 。 再次，在链路具有丢包率的单信道无线网络环境中当前已有的网络编码感知 的路由协议均存在着两个问题：( 1 ) 编码对多条数据流需要在某些路由节点处交汇 的需求可能使得某些非交汇的路由节点过载从而抵消网络编码带来的整体性能 收益；( 2 ) 在进行编码可行性的判断时存在着不同程度的误判情况。论文的第四章 主要解决这两个问题。对于第一个问题，提出一个将路由节点的负载程度、数据 包的期望传输次数以及网络编码带来的收益综合考虑的路由量度( h p m c l ) 。同时 为了使得该量度能够有效地被使用，提出了与其相配套的无线路由协议( h l c r ) 。 对于第二个问题，论文通过多个实例来分析已有工作的局限所在，并提出一个编 码可能性判断规贝j j ( c p j c ) 来发现所有潜在的能够进行编码的状态以及实质上不 宜进行编码的情况。同时论文证明了一个辅助的判定定理来提高该判断规则在实 际应用中的有效性。论文选择链路具有丢包可能性的随机无线m e s h 网络拓扑来 进行多个仿真实验，结果表明：( 1 ) 已有编码感知的无线路由协议o c r 的性能在 该实验条件下受到限制( 利用其建立路径后编码对网络吞吐量的提高量约为 1 0 6 ) ；( 2 ) 采用h p m c l 量度能够发现拥有潜在编码机会的高吞吐量路径( 网络吞 吐量的提高量约为2 8 6 ) ；( 3 ) 6 有工作的编码可行性判断方法出现误判的情况确 实存在，编码可能性判断规则真实有效( 在仿真实验中使用其前后，编码对吞吐量 的提高量相差约3 3 ) 。 第五章对全文进行了总结，并对本文的后续工作进行了展望。 关键词：网络编码，无线网络，单播传输，c o p e ，网络仿真，路由协议，路由 量度 网络编码感知的无线网络路由机制的研究 r e s e a r c ho nc o d i n g a w a r er o u t i n g m e c h a n i s m si nw i r e l e s sn e t w o r k s m a jo r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：f a nk a i s u p e r v i s o r ：p r o f l o n gd o n g y a n g a b s t r a c t n e t w o r kc o d i n g ，w h i c hr e f o r m st h et r a d i t i o n a li n f o r m a t i o np r o c e s s i n g i n c o m m u n i c a t i o nn e t w o r k s ，h a sa c h i e v e dg r e a ti m p r o v e m e n ti nt h er e c e n ty e a r s a sa l l e x p a n db r a n c ho fn e t w o r kc o d i n gi nt h ew i r e l e s sn e t w o r k s ，n e t w o r kc o d i n gf o r w i r e l e s su n i c a s tt r a f f i ch a sb e c o m eah o t - b u t t o ni s s u ef o rr e s e a r c h e r s t h i sp a p e r c o n t r i b u t e dt ot h ep r a c t i c a la p p l i c a t i o no ft h i sm e c h a n i s ma n df o c u s e do nt h e f o l l o w i n ga s p e c t s f i r s to fa l l ，t h i sp a p e re x p l o r e dt w oi s s u e sr e l a t e dt ot h ep r a c t i c a la p p l i c a t i o no f w i r e l e s sn e t w o r kc o d i n g f o ro n e t h i n g ，a sa l li n n o v a t i v eo p p o r t u n i t y b a s e dn e t w o r k c o d i n gs c h e m ef o rw i r e l e s su n i c a s tt r a f f i c ，h o wd o e sc o p ei n f l u e n c et h eo t h e r a l r e a d ye x i s t e dw i r e l e s sa p p l i c a t i o n s ? f o ra n o t h e rt 1 1 j n g ，h o we x c e l l e n td ot h e u p d a t e dv e r s i o n so fc o p ea n ds o m en e wc o d i n gs c h e m e sp e r f o r m ? t of i g u r et h e m o u t ，t h i sp a p e rf i r s t l ya n a l y z e dt h ec h a r a c t e r i s t i co fc o p e ，t h eh i e r a r c h i c a ln e t w o r k s t r u c t u r ea n dt h ew i r e l e s sm o d e lo ft h en e t w o r ks i m u l a t o r2 ( n s 2 ) ；a n dt h e n p r o p o s e dt h ee x t e n d e dw i r e l e s sm o d e lf o rc o d i n g ( e w m c ) t or e a l i z en e t w o r k c o d i n gi nc h a p t e r2 ，w h i c ha d d e dag e n e r a ln e t w o r kc o d i n gl a y e ri n t on s 2 ，a n d m o d i f i e dt h ep a c k e tt r a n s m i s s i o ns c h e m e a p a r tf o r mt h a t ，w h e ni tc o m e st ot h ep r a c t i c a ll i m i t a t i o no fc o p e ，t h i sp a p e r p r e s e n t e dac o d i n ga l g o r i t h m 、析t l lp o l y n o m i a lt i m ec o m p l e x i t yi na ne x p a n d e d m o d e l ，w h i c hi sb a s e do nt h el a t e s tt h e o r e t i c a lr e s u l t so fc o p er e s e a r c h e s t h e s i m u l a t i o nr e s u l t ss h o w st h a tc o p ec a ni m p r o v et h en e t w o r kt h r o u g h p u tb y9 8 i n i h 网络编码感知的无线网络路由机制的研究 as p e c i a lw i r e l e s sa d - h o cn e t w o r k ，i nw h i c ht h en o d e sm o v ew i t hl o ws p e e d t h e s e r e s u l t se f f e c t i v e l yv e r i f yt h ef e a s i b i l i t yo ft h em o d e l s e c o n d l y , i tg r e a t l y a f f e c t st h ep e r f o r m a n c eo fc o p ei nt h e p r a c t i c a l a p p l i c a t i o n s t h a tt h en u m b e ro fc o d i n go p p o r t u n i t i e sl a r g e l yd e p e n do nt h e t r a n s m i s s i o nr o u t e sc o n s t r u c t e db yt r a d i t i o n a lw i r e l e s sr o u t i n gp r o t o c o l s t h e r e f o r e ， t or e s o l v et h ep r o b l e m ，i nc h a p t e r3ac o p e - s u p p o r t e dp r a c t i c a ls c h e m ew a s p r o p o s e d , w h i c hi sc a l l e do n d e m a n dc o p e - a w a r er o u t i n g ( o c r ) ，i na l li d e a l w i r e l e s sm e s hn e t w o r kw h e r et h ep a c k e tl o s so ft h el i n kd o e sn o te x i s t c o n s i d e r i n g t h eb e n e f i to fc o d i n ga n dt h eh o p so fr o u t e s ，o c ru s e sap r o p e rr o u t i n gm e t r i ct o f i n dh i g ht h r o u g h p u tr o u t e sw i t hc o d i n go p p o r t u n i t i e s a sap a r to fo c r , t h e o p t i m i z a t i o ns c h e m eo fm u t i n gd e t e c t i n gc a nf i n dp o t e n t i a lc o d i n go p p o r t u n i t i e s m o r ee f f i c i e n t l ya n dd r o pt h em u t i n gm e s s a g ec o m p l e x i t ys i g n i f i c a n t l y f u r t h e r m o r e ，t h i sp a p e rp r o v e dt h a tt h es c h e m eh a st h ef o l l o w i n gp r o p e r t i e s ：( 1 ) e a c hr o u t ef o u n db yo c ri sa c y c l i c ；( 2 ) t h er o u t ef o u n db yo c ri sa l s oa l lo p t i m a l r o u t ee v e nu n d e ro t h e re v a l u a t i o nm e t r i c ；( 3 ) t h em e s s a g ec o m p l e x i t yo fo c ri s b e t w e e nt h a to fa o d va n dt h a to ft h eo t h e rr e l a t e dw o r k s t h es i m u l a t i o nr e s u l t s i n d i c a t e dt h a t ：( 1 ) b a s e do nt h ea s s u m p t i o ni l l u s t r a t e di nc h a p t e r3 ，c o p ei m p r o v e s t h en e t w o r kt h r o u g h p u ts l i g h t l y ( o n l y3 6 ) c o m p a r et ot h a t , o c rc a ne f f e c t i v e l y b r e a k t h r o u g ht h el i m i t a t i o n ( i e t h ei m p r o v e m e n to fn e t w o r kt h r o u g h p u ta c h i e v e s 2 1 6 u s i n gc o d i n ga f t e ra d o p t i n gt h et r a n s m i s s i o nr o u t ef o u n db yo c r ) ；( 2 ) w i t h o c rt h en u m b e ro fc o d i n go p p o r t u n i t i e sc a nb ei n c r e a s e db y6 6 c o m p a r e dt o 、析t l l t h et r a d i t i o n a lw i r e l e s sr o u t i n gp r o t o c 0 1 t h i r d l y , t h e r ea r et w op r o b l e m so fe x i s t e dc o d i n ga w a r er o u t i n gp r o t o c o l si n w i r e l e s su n i c a s tn e t w o r k sw i t hp a c k e tl o s s t h a ti s ，( 1 ) t oa c q u i r es u f f i c i e n tc o d i n g o p p o r t u n i t i e s ，s o m ef l o w ss h o u l di n t e r s e c ta ts o m er o u t i n gn o d e s h o w e v e r , s o m e o t h e rr o u t i n gn o d e s ，w h i c hd on o ti m p l e m e n tc o d i n g ，m a yb eo v e r l o a d e dd u et ot h e i n t e r s e c t i o n ；( 2 ) i ti sp o s s i b l et h a tt h ec o d i n gf e a s i b i l i t yi sm i s j u d g e dt os o m ee x t e n d t h i sp a p e rc o n t r i b u t e dt or e s o l v et h et w op r o b l e m sf i t sf o l l o w s t om a k et h ef l r s t p r o b l e mo u t , h e u r i s t i cp a t h m e t r i cf o rc o d i n ga n d l o a d - b a l a n c i n g ( h p m c l ) w a sp r o p o s e di nc h a p t e r4 t on l a k eac o m p r o m i s ea m o n g 网络编码感知的无线网络路由机制的研究 t h el o a do fr o u t i n gn o d e s ，t h ee x p e c t e dt r a n s m i s s i o nt i m e ，a n dt h eb e n e f i to fn e t w o r k c o d i n g m o r e o v e r , t oi m p r o v et h ee f f e c t i v e n e s so ft h em e t r i c ，ac o r r e s p o n d i n g h e u r i s t i cl o a d - b a l a n c e dc o d i n g a w a r er o u t i n g ( h l c r ) w a sp r e s e n t e d f o rt h e s e c o n dp r o b l e m ，t h i sp a p e ra n a l y z e dt h el i m i t a t i o no fe x i s t e dr e s e a r c h e sb a s e do n a h o s to fp r a c t i c a li n s t a n c e s ，a n dp r o p o s e dac o d i n g - p o s s i b l ej u d g i n gc o n d i t i o n ( c p j c ) t of i n do u ta l lt h ep o t e n t i a lc o d i n g f e a s i b l ec o n d i t i o n sa n dc o d i n g - u n f e a s i b l e c o n d i t i o n s t h i sp a p e ra l s og a v eap r o o fo faj u d g et h e o r e m ，w h i c hi m p r o v e st h e e f f e c t i v e n e s so fc p j ci nt h ep r a c t i c a la p p l i c a t i o n t h e nq u a n t i t i e so fs i m u l a t i o ne x p e r i m e n t sw e r ec o n d u c m di nar a n d o mw i r e l e s s n e t w o r k 晰t l lp a c k e tl o s s ，a n dt h er e s u l t ss h o wt h a t ：( 1 ) t h ep e r f o r m a n c eo fe x i s t e d c o d i n ga w a r ew i r e l e s sr o u t i n gp r o t o c o lo c r i sa l s ol i m i t e d ，w h i c hc a n o n l yi m p r o v e t h en e t w o r kt h r o u g h p u tb y10 6 ) ；( 2 ) h i g ht h r o u g h p u tr o u t e sw i t hp o t e n t i a lc o d i n g o p p o r t u n i t i e sc a l lb ef o u n db ya d o p t i n gh p m c l ，w h i c hc a l li m p r o v et h en e t w o r k t h r o u g h p u tb y2 8 6 ；( 3 ) t h em i s j u d g m e n t so ft h er e l a t e dw o r ke x i s t se x a c t l y , a n d c p j ci sv a l i da n de f f e c t i v e ( t h ed i f f e r e n c eo ft h et h r o u g h p u ti m p r o v e m e n ti s3 3 i n t h ee x p e r i m e n t s ) f i n a l l y , t h ec o n c l u s i o na n dt h ep r o s p e c to ft h ew o r kw e r eg i v e ni nc h a p t e r5 k e y w o r d s ：n e t w o r kc o d i n g ，w i r e l e s sn e t w o r k ，u n i c a s tt r a f f i c ，c o p e ，n e t w o r k s i m u l a t o r , r o u t i n gp r o t o c o l ，r o u t i n gm e t r i c v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在 导师的指导下，独立进行研究工作所取得的成果。 除文中已经注明引用的内容外，本论文不包含其他 个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以 明确的方式标明。本人完全意识到本声明的法律结 果由本人承担。 学位论文作者签名：超当u e tg q ：仉1 年6 月fe l 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论 文的规定，即：学校有权保留学位论文并向国家主 管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆、院系资料室被查阅，有权 将学位论文的内容编入有关数据库进行检索，可以 采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：穆礼导师签名：带龇 日期舢下g 月e 1 日期： 。j ? 年占 b 日 网络编码感知的无线网络路由机制的研究 1 1 网络编码概述 1 1 1 网络编码简介 第一章绪论 目前通信网络在各行各业已经显示出其越来越重要的作用。与此同时由于 网络使用者数量的骤增以及网络服务需求和网络传输质量的多样化使得如何对 网络进行优化从而最大限度地利用网络的现有资源成为当前研究者们所关注的 重要问题。 在传统的网络传输过程中，信息的传输从本质上来讲基于存储转发机制 ( s t o r e a n d f o r w a r d ) ，即网络节点只对数据包进行路由转发或复制。这种机制沿 用了5 0 年代以福特、富克逊为代表建立的网络流理论。但是与交通运输等传统 领域中使用网络流理论所研究的实物对象不同，通信网络中所传输的信息是表 征事物特性的一种抽象符号，能够方便地进行运算并被改变内容。因此从信息 论的观点来看没有必要将网络节点的功能局限在仅仅转发或复制数据包上，应 当通过允许网络节点对数据包的内容进行处理( 即编码) 来对网络节点的功能进 行扩展【l 】。 网络编码( n e t w o r kc o d i n g ) 起源于网络的多播( 组播，m u l t i c a s 0 i h 题。2 0 0 0 年 a h l s w e d e 等人根据网络信息流的概念在文献 1 】中指出通过节点对数据包对来 自不同链路的数据包进行组合发送( 编码) f i g 够使得网络多播确定性地达到最大 流理论的极限( 该极限被称作网络多播的最大流限) ，由于这一极限在很多情况 下无法通过传统的多播路由机制来达到，因此网络编码的优点非常明显。 可以通过文献【l 】中给出的蝶形网络为例来阐述网络编码如何达到网络多播 的最大流限，如图1 1 所示。图1 1 中所示的网络是一个无差错的传输系统， 不考虑时延和传输差错。其中源节点s 准备将信息a 和b 发送到目的节点，l 和 t 2 ，其余中间节点1 ，l 到均为路由节点。此外网络中的每一条边的容量为l ， 即每次只能传输一个信息。图1 1 ( a ) q h 显示了传统的网络多播传输过程。由最 网络编码感知的无线网络路由机制的研究 大流最小割定理【2 】j 艮容易得出源节点s 到两个目的节点f l 和t 2 的最大流分别为 2 。但是由于在链路v 3 一心每次只能传输一个信息，因此待转发的信息a 和6 中的一个必须在v 3 处等待，从而目的节点f i 和如同时获得信息口和6 的需求无 法被满足。显然在该网络中传统的多播方式无法达到多播的最大流限。而由于 使用网络编码的多播方案允许节点进行编码，均对口和b 进行异或操作( 编码) 并将编码结果口o6 进行转发。这样目的节点，l 和t 2 能够通过将各自接收到的信 息进行异或操作( 解码) 从而同时获得a 和6 。显而易见这种处理方式达到了网络 多播的最大流限。 ( a ) 传统的网络多播方式( b ) 使用网络编码的多播方式 图1 - 1 蝶型网络中的网络编码示意图 网络编码是从信息论的角度出发提出来的概念，它本质上打破了通信网络 中传统的信息处理方式，目前已经成为通信网络研究领域中的一个研究热点。 网络编码从形式上来划分可以分为下面的两大类【3 】。 1 “数据流内 编码 进一步地来讨论图1 1 ( b ) 所示的实例。该例通过在中间节点v 3 对信息a 和6 进行“混合”( 编码) 从而达到了网络多播吞吐量的上限。由于参与编码的信息口 和6 同属于一条多播数据流，因此将这种编码类型称为“数据流内 ( i n t r a - s e s s i o n ) 的编码，即参与编码的信息属于同一的数据流的编码机制。“数据流内 编码起 源于文献【l 】所研究的多播网络编码，目前已经得到了迅速发展。 2 “数据流间编码 与“数据流内 编码相对应，“数据流间 ( i n t e r - s e s s i o n ) 的编码指参与编码 的信息分别属于不同的数据流的编码机制。早期的“数据流间 编码主要是针 对非多播网络的编码方案，如本章1 1 2 节的第三部分阐述的非线性编码。文献 2 网络编码感知的无线网络路由机制的研究 【3 】的会议版本引发了在无线网络上对“数据流间 编码的研究，即针对单播 ( u n i c a s t ) 传输的无线网络编码机制，目前其研究已经成为无线网络编码研究的主 流。本文的研究将主要关注于这类型的网络编码机制。 需要说明的是上述对网络编码的划分仅仅基于编码所针对的网络需求( 多播 非多播) 而言，并不针对某种特定的编码方案。比如所有多播网络中的线性编码 方案均为“数据流内”编码，而某些非多播网络中的线性编码方案却属于“数 据流间 编码。 网络编码研究目前已经引起国内外研究者们的广泛关注。从国外来看，普 林斯顿大学、麻省理工学院、微软研究院等著名大学和科研机构已经致力于网 络编码的理论和应用研究。从国内来看，许多知名高校的学者已经在网络编码 方向取得了相当重要的成果，并且针对网络编码的学术研讨会也吸引着越来越 多的研究者的目光。 1 1 2 网络编码基础 1 确定型线性编码 在网络编码理论被提出之后，在一个网络中对信息进行怎样的操作才能够 使得网络多播达到上限成为首先被考虑的问题。l i 、y e u n g 和c a i 三人首次在文 献【4 - 5 】中提出网络编码的线性编码方案( 1 i n e a rn e t w o r kc o d i n g ) ，证明了在运算所 选取的有限域足够大的前提下，只需要对传输的信息进行线性操作即可确定 性地使得多播传输达到最大流限。 r k o e t t e r 和m m e d a r d 首先给出了一种可应用于任意网络拓扑的线性编码 代数构造方法 6 7 】。这种构造方法是在已知整个网络的拓扑结构信息的情况下， 使用一个关系矩阵m 来描述源节点的输入信息和接收节点所接收的信息之间的 关系：m = 彳( ，一f ) 1 b 。其中矩阵a 为源节点输入与边之间的关系矩阵，矩 阵f 为网络中边与边之间的关系矩阵，矩阵君为边与目的节点输出之间的关系 矩阵。这种方法将编码是否可行的问题归结到关系矩阵m 是否满秩的问题上， 使得编码的构造简单有效。 与r k o e t t e r 和m m e d a r d 提出的线性编码的代数构造框架相对应，e s a n d e r s 等人基于图论提出了一种实现网络编码的多项式时间算法 8 9 】。该方法同样需 网络编码感知的无线网络路由机制的研究 要己知网络拓扑的情况下对网络进行编码，通过最大流最小割算法寻找完成网 络多播所需的路径来依次确定路径上各个路由节点的编码操作。这种方法有效 地避免了冗余边上的编码过程，不但将编码的构造进一步简化而且大大降低了 编码运算中基于的有限域的大小。 2 随机线性编码 上面所提到的编码构造方法都是基于已知网络拓扑信息的集中式方法，在 应用中具有一定的局限性。针对这个问题研究者们又提出了不需网络拓扑信息 的随机网络编码方法 1 0 1 1 。在该方法中节点只需对来自不同链路的数据包进 行随机的线性组合处理( e t p 节点输出是输入的随机线性组合，组合的系数从一个 有限域内随机选取) ，就可以使得接收节点以一定的概率成功解码。研究结果表 明随着接收节点数量与编码运算基于的有限域大小的比值趋近于0 时，该算法 中接收节点能够成功解码的概率将趋近于l 。 总的来看，集中式的网络编码方法 6 9 】需要根据全局拓扑状况来给每个节 点分配编码系数。虽然这些方法使得编码运算所需的有限域不会太大，但是网 络拓扑的变化将导致全部编码系数重新分配，因此可扩展性较差。虽然随机网 络编码方法具有良好的拓扑适应性，但是这种方法实现正确无误的数据传输具 有一定的概率性。 3 非线性编码 线性编码已被证明可以确定性地达到任何一个多播网络的最大流限。但是 线性编码在非多播网络中的性能将会是怎样，或者说是否线性编码同样能够使 得非多播网络达到其容量的上限? 文献 1 2 1 首先关注这一问题，证明了当编码运算基于的有限域为二元域时， 存在着没有线性编码方案的多播网络。文献【1 3 】通过一个实例证明了同样限定 编码域为二元域时存在没有线性编码方案但有非线性编码方案的非多播网络， 并首次探讨了使用非线性函数进行编码的可能性。文献 1 4 】进一步地指出编码 域的增加不足以使得所有非多播网络都存在线性编码方案。文献 1 5 】将非线性 编码分成两类，证明了存在着一类与线性编码等价的非线性编码。由于在非多 播网络中构造达到其容量上限的编码方案非常复杂，因此对非线性编码的研究 目前还处于起步阶段。 4 网络编码感知的无线网络路由机制的研究 1 2 无线网络编码的发展现状1 近年来，对无线网络环境中网络编码机制的研究成为了网络编码研究方向 中的一个热点。由于无线网络具有数据传输速率低、物理层广播和信道不可靠 的特点，因此尝试使用网络编码来提高其网络性能显得十分必要。一般地从网 络节点之间通讯模式的角度来看，无线网络中网络编码的研究可以简单地分为 无线多播网络编码和无线单播网络编码两部分。本节将分别对其当前的研究状 况进行阐述。 1 2 1 无线多播网络编码机制 无线多播网络编码本质上来讲是传统网络编码方法在无线网络中的扩展， 同样属于“数据流内”编码的范畴。早期无线多播网络编码的研究主要关注提 高a d h o e 网络的多播吞吐量以及节省移动节点能量消耗即这两个问题。w u 等 人首先在文献 1 6 】中使用网络编码来解决无线a d h o e 网络的最小能量多播问 题，将应用网络编码后的最小能量多播树的构建转化为在多项式时间内可解的 线性规划问题。l 吼等人对节省节点能量消耗问题进行了进一步地抽象并提出 了最小费用多播的概念，在文献 1 7 】中同样给出了基于线性规划的解决方法。 文献 1 8 1 提出一种平衡链路带宽的跨层优化策略从另外一个角度来尝试使 用网络编码提高无线a d h o e 网络的多播吞吐量，但是这种方法增加了网络的复 杂性从而在实际应用中具有一定的局限性。文献 1 9 1 讨论如何在提高无线a d - h o e 网络多播吞吐量的同时尽可能地降低网络编码带来的计算复杂性，证明了只需 要在进入转发节点的链路上进行编码就能够达到无线a d h o e 网络多播吞吐量的 上限。文献 2 0 1 提出了一种多重分离路径算法来计算从源节点到目的节点的分 离路径的数量来支持在使用将线性编码提高a d h o e 网络多播吞吐量的过程中编 码方案的实现。文献 2 1 】针对多播网络编码在无线网络中实际应用时存在的问 题，提出一种将网络编码思想与多路径机会路由机制相结合的编码方案来提高 网络的多播吞吐量。此外，对无线多播网络编码的研究还包括网络编码在无线 传感器网络中的应用【2 2 】等。 1 这里所指的无线网络包括无线a d h o e 网络，无线m e s h 网络和无线传感器网络。 网络编码感知的无线网络路由机制的研究 1 2 2 无线单播网络编码机制 与1 2 1 节所阐述的属于“数据流内编码的无线多播网络编码相比，属于 “数据流间编码范畴的无线单播网络编码是一种全新的机制。在文献【2 3 2 5 】 对某些特殊单播传输网络拓扑中的网络编码研究的基础上，k a t t i 等人首先在文 献 2 6 1 q b 提出基于机会的无线单播网络编码机制c o p e 来支持无线网络中的单 播传输，并同时研究了其在各种无线环境中具体实现的问题。c o p e 机制充分 利用了无线网络的“广播 特性，通过对数据包进行编码发送来尽可能地减少 局部拓扑中数据包的传送量，从而提高无线网络的整体性能( 包括节省无线节点 能量和提高网络单播传输的吞吐量) 。目前关于无线单播网络编码机制的许多问 题已经引起越来越多研究者的关注，下面将分别阐述当前对其的研究热点。 1 应用无线单播网络编码机制后网络的容量 文献 2 6 】已经指出在无线网络的单播传输中应用网络编码能够有效地提高 网络吞吐量1 ，那么该吞吐量的上界即网络容量是多少? 文献 2 7 2 8 1 首先注意到 这个问题在文献【2 9 】提出的通信模型的基础上加入网络编码的元素，以此讨论 了随机拓扑上的同时有多条单播数据流存在的网络吞吐量上界。这两篇文献指 出不论是在协议模型还是物理通讯模型上来对问题进行研究，在有多条单播数 据流存在的无线网络中网络编码对吞吐量提高的上界均为一个常数因子。因此 引入网络编码后无线网络的吞吐量上界与未引入编码时的吞吐量上界处于同一 个数量级，并且该结论可以扩展到1 d ( d i m e n s i o n ) 、2 d 、3 d 甚至加随机网络 拓扑的情形。此外文献 2 7 2 8 还刻画了1 d 和2 d 网络拓扑中该上界的范围。 通过文献 2 7 2 8 1 可得在无线网络中网络编码应用的不会提高网络吞吐量的 上界，但是它可以使得实际吞吐量尽可能地接近理论上界。文献 3 0 】在讨论无 线单播网络编码机制使得无线节点能量节省量的上界的同时，从另一个角度给 出了一个与文献 2 7 2 8 相比更具有普遍性意义的吞吐量上界。而文献【3 l 】给出 了应用实际的网络编码方案后网络吞吐量的紧致( t i g h t ) 上界。此外文献 3 1 1 还通 过几何学的方法证明了在节点的一次编码中参与编码数据包的数量存在可达上 界，进而推翻了文献【2 6 】中的一个论断。 是否文献 2 7 2 8 1 所给出的网络编码对吞吐量提高的上界已经达到了所有可 1 在本文中如无特别说明，网络吞吐量即指网络单播传输的吞吐量 6 网络编码感知的无线网络路由机制的研究 能的无线网络编码机制的能力极限? 文献【3 2 】关注了这一问题，认为将无线单 播网络编码机制c o p e 的编码思想扩展到物理层的两种新无线网络编码机制： 物理层网络编码机铝l j ( p h y s i c a l l a y e rn e t w o r kc o d i n g ，p n c ) 3 3 和类网络编码机 制( a n a l o gn e t w o r kc o d i n g ，a n c ) 3 4 的网络吞吐量上界的数量级能够超越传统 无线单播网络编码机制对吞吐量提高的上界。文献 3 2 给出了应用p n c 机制和 a n c 机制后网络吞吐量上界和下界的数量级，并证明了虽然下界的数量级将与 应用传统无线单播网络编码机制后网络吞吐量下界的数量级等同，但上界的数 量级将大于文献 2 7 2 8 所给出的上界。此外文献 3 2 】给出的上下界均可达，应 用p n c 机制和a n c 机制的网络实际吞吐量在这两个界之间变化。由于是一种 全新的理念，文献 3 2 3 4 所进行的研究目前只局限在最简单三跳网络拓扑上， 因此与真正的实际应用还有一定的距离。类似文献 3 2 】，文献 3 5 】同样关注应用 p n c 机制后网络的吞吐量上界这个问题，并给出了i d 随机网络拓扑中网络吞 吐量上界的值和2 d 随机网络拓扑中网络吞吐量的上确界。 2 应用无线单播网络编码机制后网络的可达吞吐量 在无线单播网络编码机制被提出之后，一个很自然的问题浮现出来：在实 际情况中编码究竟能够将无线网络的吞吐量提高多少，即网络的可达吞吐量有 多大。目前对这个问题的研究已经成为对无线单播网络编码机制研究的主流。 文献【3 6 】首先注意到这个问题，给出了一种理想情况下已知网络全局拓扑和单 播传输需求时网络单播传输最大的吞吐量。在文献 3 6 】的研究基础上，文献 3 7 】 通过两个实例给出了一个重要的结论：在某些特定的情况下在无线网络中引入 网络编码后将使得网络的吞吐量下降。虽然出现这种情况的无线网络具有网络 非常不稳定、网络带宽随时间波动以及特定的m a c 层调度策略等特征属于极 少数的情况，但是这个现象确定性地反映了一个事实：网络编码对网络吞吐量 的提高需要有相应的包调度策略对其支持。此外文献【3 7 】给出了一个普适性的 编码框架来将最优编码方案和包调度策略相结合。 基于文献 3 6 3 7 1 的研究，许多研究者开始关注如何设计有效的编码方案使 得无线网络单播传输的实际吞吐量尽可能地被提高。文献【3 8 】研究如何能够确 定性地创造编码机会，给出一个结合数据包调度和拥塞控制来支持无线网络单 播传输编码的跨层编码方案。该方案通过一些简单的数据包转发规则使得在保 7 网络编码感知的无线网络路由机制的研究 证编码机会存在的同时能够有效地进行拥塞控制。 文献 3 9 】通过改进数据包的编码策略来对c o p e 机制进行改进使得节点向 其每个邻居发送的字节数进一步地被压缩，从而有效地提高网络吞吐量。此外 该文献提出一个适用于多种编码策略的普适框架，在此框架下将最优编码问题 描