（通信与信息系统专业论文）无线网络广播方式中的网络编码技术的研究.pdf

重庆邮电大学硕士论文摘要 摘要 随着无线网络应用的增加和规模的日益扩大，如何更好地提高网络带宽利用 率变得愈加重要，从而促进了网络编码的诞生和发展。网络编码是一种新型的传 输方法，与传统的存储转发方式不同，它是在中间节点上对需要转发的信息包进 行编码，在接收端进行相应解码，最后得到所需要信息的方法。因此它出现在各 个方面的研究领域中，如用于提高网络的吞吐量、如何确保信息的安全以及能量 的利用率等方面。由于无线网络链路的不可靠性，非常适合使用网络编码技术， 因此网络编码被视为无线网络研究的重要方向，对未来的信息传输具有重要意义。 本文首先对网络编码的基本原理进行了详细介绍。然后对前人提出的无线网 络中基于网络编码的重传方法，即遍历接收节点的网络编码重传策略进行了研究， 该策略的基本思想是通过中间节点对在传输中丢失而需要重传的信息包进行编码 组合后再重传，该方法可以有效地减少信息包的重传次数，从而提高网络带宽利 用率。然而，进一步的研究发现该方法存在如下缺点：( 1 ) 生成的编码分组在接收 端会出现不可解码的情况，因此需要二次或多次重传操作，降低了编码效率、增 大了网络开销；( 2 ) 中间节点要等到收到所有接收节点反馈的回复包后，才能判断 进行编码组合，增大了传输时延；( 3 ) 接收节点要通过发送反馈( a c k n a c k s ) 信息， 将数据分组是否成功传输到接收节点的情况告知发送节点，增大了网络开销。 针对编码分组可解性和传输时延的问题，本文提出一种基于滑动窗口的连续 网络编码方案，即在待重传数据分组矩阵中设计一个按时间顺序滑动的编码窗口 并在其中选择参与网络编码的分组，以期达到既能减少数据分组的重传次数和传 送时延，又能同时保证编码分组的可解性的目的；针对接收节点同时发送反馈 a c k n a c k s 信息导致的网络开销过大问题，本文提出接收节点仅反馈a c k 信息、 中心节点等待一段时间后对未接收到反馈a c k 信息的节点进行编码重传的方案， 减少了网络开销。为了验证改进的编码方案，本文使用o p n e t 仿真工具对普通重 传策略、遍历接收节点的网络编码重传策略及改进后的基于滑动窗口的网络编码 算法进行了仿真建模和仿真实现，对改进前后算法的结果进行了比较和分析。仿 真结果表明改进后的算法能够减少网络的重传次数、缩短端到端的平均时延、减 少网络总开销，从而使网络总能耗也随之降低。 本文最后展望了基于滑动窗口的网络编码策略的进一步研究方向，并对全文 进行了总结。 关键词：无线网络，网络编码，广播，重传，滑动窗口 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t a l o n g 蜥t l lt h ei n c r e a s eo fa p p l i c a t i o na n dl a r g es c a l eo fw i r e l e s sn e t w o r k s ，h o wt o i m p r o v et h en e t w o r kb a n d w i d t hu t i l i z a t i o n h a sb e c o m em o r ea n dm o r ei m p o r t a n t ， w h i c hp r o m o t e st h eb i r t ha n dd e v e l o p m e n to fn e t w o r kc o d i n g c o m p a r e dt ot r a d i t i o n a l s t o r e a n d f o r w a r dm o d e ，n e t w o r kc o d i n gi san e wk i n do fm o d eo ft r a n s m i s s i o n , w h i c h e n c o d e st h ep a c k e t sn e e d e dt of o r w a r di nt h em i d d l en o d e sa n dg e t sd e c o d ei nt h e r e c e i v i n gn o d e ss oa st og e tt h ec o r r e s p o n d i n gi n f o r m a t i o n t h e r e f o r e ，n e t w o r kc o d i n g c a nb ea p p l i e do nm a n yr e s e a r c hf i e l d s ，s u c ha sh o wt oi n c r e a s en e t w o r kt h r o u g h p u t ， h o wt om a k es e c u r i t yo fi n f o r m a t i o na n dh o wt oi m p r o v et h ee n e r g yu t i l i z a t i o na n ds o o n d u et ot h ec h a r a c t e r i s t i c so fb r o a d c a s t i n gi nw 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 gi s v e r ys u i t a b l ef o rw i r e l e s sn e t w o r k s i nt h i sp a p e r , w ef i r s ti n t r o d u c et h eb a s i cp r i n c i p l eo fn e t w o r kc o d i n gi nd e t a i l ，t h e n w ed oas t u d yo nt h ee x i s t i n gr e t r a n s m i s s i o na p p r o a c h - - - - n e t w o r kc o d i n gr e t r a n s m i s s i o n s c h e m eb a s e do nt r a v e r s i n gt h er e c e i v i n gn o d e si nw i r e l e s sn e t w o r k s ，t h ek e y p o i n to f w h i c hi st oc o m b i n em u l t i p l el o s tp a c k e t s 、析mn e t w o r kc o d i n gt oa c h i e v eh i 【g he f f i c i e n t r e t r a n s m i s s i o n h o w e v e r , t h e r ee x i s ts o m ep r o b l e m sa b o u tt h i se x i s t i n gr e t r a n s m i s s i o n a p p r o a c h e s ：( 1 ) t h ec o d i n gc o m b i n a t i o nc a nn o tg e ts o l v a b i l i t yc o m p l e t e l yi nt h e r e c e i v i n gn o d e sa n dn e e ds e c o n d a r yo rm u l t i p l er e t r a n s m i s s i o n s ，w h i c hr e d u c et h e c o d i n ge f f i c i e n c ya n di n c r e a s e st h en e t w o r ko v e r h e a d ( 2 ) o n l yi ft h ec e n t r a ln o d eh a s r e c e i v e da l lt h ef e e d b a c ki n f o r m a t i o na b o u tp a c k e tl o s sf r o mm u l t i p l er e c e i v i n gn o d e s ， t h ec o d i n gc o m b i n a t i o nc a ni m p l e m e n t ，w h i c hi n c r e a s e st h et r a n s m i s s i o nd e l a y ( 3 ) w h i l er e c e i v i n gd a t ap a c k e t s ，r e c e i v i n gn o d e sr e t u r nf e e d b a c kt ot h es e n dn o d ew i t h a c ko rn a c km e s s a g e s ，w h i c hi n c r e a s e st h en e t w o r ko v e r h e a d t oa d d r e s st h ep r o b l e m so fc o d i n gi n s o l v a b i l i t ya n dt r a n s m i s s i o nd e l a y , w ep r o p o s e ac o n t i n u o u sn e t w o r kc o d i n gs c h e m eb a s e do ns l i d i n gw i n d o w sw h i c hd e s i g n sac o d i n g w i n d o ww h i c hs l i d e si nc h r o n o l o g i c a lo r d e ri nt h em a t r i xo fd a t ap a c k e t sw a i t i n gf o r r e t r a n s m i s s i o n , a n dt h ed a t ap a c k e t su s e dt oe n c o d ea r ec h o s e nf r o mt h ec o d i n gw i n d o w t h ep r o p o s e ds c h e m en o to n l yc a nr e d u c et h en u m b e r so fr e t r a n s m i s s i o na n dd e l a y , b u t a l s oc a ne n s u r et h es o l v a b i l i t yo fc o d e dp a c k e t s m e a n w h i l e ，i td e c r e a s e st h en e t w o r k o v e r h e a db yo n l yf e e d b a c ka c k m e s s a g e i fc e n t r a ln o d ed o e s n tr e c e i v et h ef e e d b a c k i n f o r m a t i o na b o u tac e r t a i np a c k e tf r o ms o m er e c e i v i n gn o d ea l t e rs o m et i m e ，i t 1 n d i c a t e s 廿1 a tt h ep a c k e th a sl o s t i no r d e rt o v a l i d a t ei m p r o v e dc o d i n gs c h e l l l e 。w e e v a j u a t em ep 柏锄觚c eo fo u r s c h e m et h r o u g ho p n e ts 舢l a t o r 孤d c o m p a r ei tw i n l 0 r d l 唧舭s m i s s i o ns t r a t e g ya n dn e t w o r kc o d i n gr e 慨s m i s s i o ns 觚c g y b 嬲e do n 昀v e r s i n gt h er e c e i v i n gn o d e s s i m u l a t i o nr e s u l t ss h o w t h a tt h ep r o p o s e ds c h 锄ec 觚 ? m 比e m em u n b e f so f r e t r a n s m i s s i o n , m i n i m i z et h ea v e r a g ee n d - t o e n dd e l a y , d e c r c 弱e u l en e t 、7 l r o r k0 v e r h e a da n d r e d u c et h en e t w o r k 锄e 曙y c o l l s u m p t i o na c c o r d i n g l v 一 上 m a l 堍w ep r o v i d ec o n c l u s i o na b o u t t h i s p a p e ra n dp r o s p e c tf m h e rr e s e a r c h d l r e c t i o n so f n e t w o r kc o d i n g s c h e m eb a s e do ns i i 妇g w i n d o w s k e yw o r d s ：w i r e l e s sn e t w o r k ，i 咖o f k w i n d o w s c o d i n g , b r o a d c a s t i n g , r e t r a n s m i s s i o n ，s l i d i n g 重庆邮电大学硕士论文缩略语 英文缩写 a c k c o p e f e c f s m i d m a c m o r e o d b p 2 p s t d 缩略语 英文全称 a c k n o w l e d g ec h a r a c t e r c o m p l e t e l yo p p o r t u n i t ye n c o d i n g f o r w a r de r r o rc o r r e c t i o n f i n i t es t a t em a c h i n e i d e n t i t y m e d i u ma c c e s sc o n t r o l m a c i n d e p e n d e n to p p o r t u n i s t i cr o u t i n g e n c o d i n g o p n e t d e b u g g e r p e e r - t o - p e c r s t a t et r a n s i t i o nd i a g r a m v i 中文译文 确认字符 基于机会的网络编码方法 前向纠错 有限状态机 身份 介质访问控制 & 独立m a c 的机会路由编码 o f n e t 调试 点对点 状态迁移图 重庆邮电大学硕士论文插图目录 插图清单 第一章 图1 1 源节点组发送播信息包到节点t l 、t 2 2 第二章 图2 1 传统的转发方式和基于网络编码方法的信息交换比较6 图2 2 网络编码减少能耗。7 图2 3 多个接收节点的无线网络广播模型1 0 图2 4 网络编码应用于广播重传策略的编码组合情况1 1 图2 55 个接收节点接收l o 个信息包情况表1 2 图2 6 两种重传策略的比较1 3 图2 7 重传丢失信息包的动态组合策略1 4 图2 8 网络编码应用于广播重传方法组合信息包算法描述1 5 第三章 图3 1 包含6 个节点的无线单跳广播网络1 8 图3 2 待重传分组矩阵例子2 2 第四章 图4 1o p n e t 的仿真流程2 7 图4 2c 唧咂t 仿真中的网络场景。2 8 图4 3 无线网络的节点模型2 9 图4 4 无线网络的进程模型3 0 图4 5 无线网络进行数据重传的进程模型3 1 图4 6 遍历接收节点的网络编码重传的进程模型3 2 图4 7 基于滑动窗口的网络编码进程模型3 3 图4 8 重传次数3 4 图4 9 网络总开销3 6 图4 1 0 网络总能耗3 6 图4 1 1 重传次数3 7 图4 1 2 网络总开销3 8 图4 13 网络总能耗3 9 图4 1 4 重传次数4 0 图4 1 5 网络总开销4 2 v 重庆邮电大学硕士论文插图目录 图4 1 6 网络总能耗4 2 图4 1 7 重传次数4 3 图4 1 8 网络总开销4 4 图4 1 9 网络总能耗4 5 v 重庆邮电大学硕士论文 表目录 表目录 第四章 表4 1 分组的端到端平均时延3 5 表4 2 分组的端到端平均时延3 8 表4 3 分组的端到端平均时延4 1 表4 4 分组的端到端平均时延4 4 i x 重庆邮电大学硕士论文 第一章绪论 1 1 课题研究背景及意义 第一章绪论 在当前的通信网络中，信息是由源节点发出，在中间节点上通过存储转发的 方式传输到目的节点。中间节点只对数据包进行复制转发，而不做其它任何数据 处理。人们为了达到分析信息、保证信息安全等目的，在中间节点上对数据进行 处理。但中间节点对数据的处理相对于信息的传输过程来说并没有带来任何的好 处。而网络编码的提出，即中间节点对输入的信息包进行编码，将编码的信息包 再发送出去，对提高网络带宽的利用率和网络吞吐量等方面有很大的优势。因此 网络编码的提出，对通信网络的研究产生了巨大的影响。 网络编码可以提高网络的性能，如增大网络容量，减少传输次数，节省网络 资源，均衡网络负载，以及增强网络的健壮性等。由于网络编码将多个信息包进 行组合，因此，网络编码本身对信息具有一定的隐藏功能，从而保证信息的安全。 网络编码也可以在多种网络中运用，如多播网络，广播网络，无线自组织网，无 线传感器网络等。 现在，对网络编码有很多的研究，都是基于无线网络路由协议设计方面的， 很少将网络编码应用于差错重传方面。因此，在无线网络广播重传中应用网络编 码，可以减少重传次数，从而提高网络的性能等方面具有很大的研究价值。 1 2 网络编码的提出和研究现状 1 2 1 网络编码的提出 香港中文大学的r a h l s w e d e 等【l 】于2 0 0 0 年在i e e e 上发表一篇文章，题目为 “网络信息流 。该文章对如何提高网络的传输容量提出了一个新方向，即从信息 论的角度证明了：利用网络编码可以达到通信网络的最大容量，对现有的网络资 源可以最大限度的利用。 网络编码的核心思想就是通过中间节点对信息包进行处理，即中间节点将输 入的多个信息包编码成一个或多个信息包，然后再转发，目的节点通过解码得到 原始的数据。可以增大每次转发的信息量，减少转发次数，从而提高了链路带宽 的利用率和网络的吞吐量以及鲁棒性。同时，网络编码具有多种编码方案，其中 异或编解码方案由于编解码方案简单，具有很强的适用性，因此，是常用的一种 重庆邮电大学硕士论文 第一章绪论 网络编码方案。 通信网络可以用图论中的有向图来表示，并且由最大流最小割定理可知，一 个网络传输的最大流量与其最小割是可以相等的。传统的通信网络是存储转发的 方式，并不能使网络进行最大流量的传输，因此从线路的利用率角度来说它不是 最好的；而基于网络编码的通信网络，在中间节点对信息包进行编码处理再转发 出去，目的节点再根据已有的信息包解码得到所需的信息包。在传输相同信息的 情况下，利用网络编码方案可以使得网络的传输速率得到大大的提高，网络资源 也得到充分的利用，实现了利用最大流最小割定理可以达到传输信息流量上限的 理论。 下面通过一个简单的例子来说明网络编码的基本思想及其带来的好处【l 】。通信 网络如图1 1 所示，该网络是一个不考虑传输时延和传输差错的组播网络。在图 1 1 ( a ) 中s 是源节点，t l 、t 2 为网络的两个接收节点。每个单位时间内每条边的信息 速率为l 。若网络的中间节点只对信息进行存储转发，则该网络的速率在每个单位 时间内达不到2 比特。因此中间节点3 在单位时间内只能接收并转发1 节点和2 节点中的一个，若中间节点转发节点l 的信息，则在t 2 节点可以收到2 比特的信 息，但t l 节点在每个单位时间内只能收到1 比特的信息。若从源节点s 发信息比特 a 到节点1 ，发信息比特b 到节点2 ，如图1 1 ( b ) 所示。在节点3 处将1 节点和2 节点发的信息比特a 和b 进行模2 加，然后发送到4 节点，节点4 发送信息到t l 和 t 2 。在t 1 节点经过a + ( a + b ) 运算得到b 信息包。即在t l 节点不仅收到了a 信息包， 也收到了b 信息包，因此在一个单位时间内收到了2 个比特，同理在t 2 节点也收 到了2 个比特，因此达到了每单位时间内2 比特的多播速率。 图1 1 源节点组发送播信息包到节点t l 、t 2 1 2 2 网络编码的研究现状 目前，网络编码作为可以有效地达到网络容量极限传输理论的方法已被证明， 2 重庆邮电大学硕士论文 第一章绪论 并且已被学术界和美国军方认定为可以有效解决网络问题的重要手段【2 】。目前，在 具有确定拓扑结构的有线网络中使用网络编码已受到广泛的关注，但是在无线网 络中却很少得到应用，由于无线链路具有不可靠和广播传输的特性，因此在无线 链路中使用网络编码方法将非常适合。由此可见，网络编码应首先应用在无线网 络环境中【3 】。现在有许多著名大学和i t 巨头都在致力于这一方面的研究，例如麻 省理工学院【4 1 、多伦多大学【5 1 、普林斯顿大掣6 1 、瑞士e p f l 学院【7 1 以及美国的贝 尔实验型引、微软研究酣9 1 、a t & t 的香农信息实验室等。而当前的研究主要都 集中在通过网络编码技术的应用来提高无线网络的吞吐量和能量的有效利用等方 面【1 1 1 。下面，我们就从无线传感器网络、无线a d - h o c 网络及无线m e s h 网络等三 个无线网络方面对相关研究进行归纳总结。 ( 1 ) 网络编码技术应用在无线传感器网络中的优势 在改善吞吐量方面，l e o n g 等【1 2 】提出了一种分布式随机网络编码的算法，该算 法规定除了接收节点以外的所有节点，各自地对在有限域上的随机线性映射关系 进行选择，将映射应用在输入数据流上，就可以得到输出数据。与d i j k s t r a 最短路 径算法、基于在线s t e i n e r 树生成算法及最近节点优先算法【1 3 】等路由算法进行比较 后，可以得出分布式随机网络编码算法与基于路由的算法相比，在网络吞吐量和 鲁棒性等方面都有明显地优势。 在提高能量利用效率方面，p e t r o v i c 等人【1 4 】提出了一种结合网络编码的、对无 线信号不进行调制的策略，同时证明运用随机分布式网络编码，未经调制的无线 信号能够达到经过调制的无线信号一样的吞吐量。在节省大量因为模拟器件进行 调制而消耗的能量同时，也能降低节点的成本。 ( 2 ) 网络编码技术应用在无线a d h o e 网络中的优势 在改善吞吐量方面，继r a h l s w e d e 等人【l 】结合图论等内容提出了网络编码的 概念，并且证明了通过中间节点进行编码后的网络具有更大的流量之后，m e d a r d 等人【1 5 】和l i 等人【1 6 】通过证明随机网络编码、线性网络编码同样可以达到网络传输 理论的最大流问题，并对网络编码的数学架构进行了阐述，为在无线网络中应用 网络编码进行传输从而提高网络吞吐量等方面的研究提供了理论依据。为了解决 优化无线a dh o c 网络吞吐量的问题，y u a nj u n 等人【l7 】将该问题分为优化物理层能 量分配和优化网络层的多跳路由两个子问题，分别在物理层和网络层平衡链路带 宽的供需关系，在这种平衡状态上，提供了利用网络编码来提高网络吞吐量的方 法。随之，w u y u n n a m 等人【l l 】提出了利用网络编码减少分组传输次数的方法。k u n g 等人【l8 】从网络编码的角度把网络链路分为两类，即进入目的节点的链路和进入中 继节点的链路，同时证明了，在容量相同的情况下，对进入中继节点的链路进行 网络编码可以有效地降低网络的复杂度。t r a c e y 等人【1 9 】在时变的、受噪声干扰的 3 重庆邮电大学硕士论文 第一章绪论 无线网络模型【2 0 】上，通过动态的压力反馈算法对网络编码和路由分别进行了优化， 并分析了在恶劣的网络环境下网络编码传输的性能。 在提高能量利用效率上，w uy u n n a n 等人【2 l 】证明了在到无线a dh o e 网络组 播时应用网络编码，可以将最小化每位数据能量消耗问题归结为线性问题，同时 提出了动态拓扑组播的最小化解决能量方法。l u n 等人【2 2 】通过独立的研究也得到 了相似的结论。l u n 和m e d a r d l 2 3 】【2 4 】等提出了随机化和非中心化的网络解决方法， 该方法在动态变化和不可靠的网络环境下实现最小化能量的信息组播。在传统方 式中通过重传、前向纠错码( f o r w a r de r r o rc o r r e c t i o n , f e c ) 、路径编码、链路编 码等方法来提高无线网络中的单播通信效率。l u n 和m e d a r d 等人【2 5 】提出了分布 式流优化和网络编码相结合的方法，该方法提高了传输效率，有效地减少了重传 次数，提高传送成功率，从而降低了能量的消耗。 ( 3 ) 网络编码技术应用在无线m e s h 网络中的优势 在改善吞吐量方面，k a t t i 等人【2 6 l 对基于机会网络编码方法( c o m p l e t e l y o p p o r t u n i t ye n c o d i n g 。c o p e ) 的提出是在无线环境中的协议层面上将网络编码进 行具体实现方面问题的首次研究。在c o p e 协议中，每个接收节点都会对传输 媒体进行侦听，通过获得邻居节点的信息状态，对编码的机会进行确定，并且在 本地的信息缓存区内进行编码，最后进行基于机会的路由，该方法可以有效的提 高无线网络的传输容量和吞吐量。c h a c h u l s k i 等人口7 1 对c o p e 协议进行改进，提 出m o r e 协议，并证明m o r e 协议可以使网络的吞吐量得到有效地提高。 在提高能量利用率方面，针对全网广播的能量广播最小化问题，w i d e m e r 等人【2 8 】提出了一种在广播节点上应用网络编码减少能量消耗的方法，并证明该 方法是有效性的。针对这个问题，f r a g u o l i 等人【2 8 】【2 9 1 又进行了深入的研究，分析 了网络拓扑结构、节点能量传输半径及节点丢包率等因素对能量广播最小化问题 的影响。 综上所述，在无线网络中使用网络编码技术，其核心思想是通过牺牲网络节 点进行编码、解码的计算代价从而换取网络传输的增益。由于网络编码进行的计 算复杂度较低并且由摩尔定律可知，传输代价与计算能力相比，要高很多，因此， 节点的计算代价和网络时延与网络传输增益相比是可以接受的【3 0 】。因此，网络 编码的应用不仅可以改善网络性能，而且对网络结构及网络协议的设计方法也可 以改变，网络编码与传统的网络相比有革命性的改变。 由于无线网络环境恶劣，信息包在传输过程中发生错误传输或丢失的概率明 显增多，将网络编码应用于无线网络的广播重传中，可以有效提高无线网络的传 输性能。 4 重庆邮电大学硕士论文 第一章绪论 1 3 论文研究的主要内容 本论文的工作目标是提出一种以较快的速度选取编码信息，并在接收端可以 完全解码作为度量的编码机制，使得编码后的信息包具有接收端可解，传输时延 相对较短的特点，在重传的时候，充分考虑了链路的不稳定性，即重传时仍会有 重传的信息包丢失。因此，将网络编码应用与重传策略中，可以减少重传的次数、 减少网络开销及能耗降低，从而提高网络性能。针对以上目标，本论文研究的主 要内容可以分为以下几个方面： ( 1 ) 对现阶段将网络编码应用于无线网络中进行研究，详细了解了网络编码 在无线网络中的应用过程、主要功能、当前算法的实现以及该算法要达到的目标。 ( 2 ) 根据无线网络的架构，利用o p n e t l 4 5 的网络仿真软件建立不同功能 的节点，搭建以一个中心节点和五个接收节点为场景的无线网络的仿真平台，并 通过该平台检验网络编码对无线网络广播重传的重传次数、端到端的时延、网络 开销、网络能耗等方面的影响，探寻更好的网络编码方案。 ( 3 ) 深入分析了无线网络中广播重传算法的实现过程，针对该算法存在的问 题，提出了一种基于滑动窗口的网络编码重传算法并在o p n e t 仿真软件上进行实 现，继而对网络性能进行分析。 1 4 论文的结构安排 本论文各章节的安排如下： 第一章“绪论 。首先阐述了论文的研究背景及意义，然后介绍了网络编码的 提出及研究现状。 第二章“网络编码原理和应用概述。首先介绍了网络编码的基本原理；然后 介绍了网络编码的优缺点及应用，并对网络编码在无线网络中的应用进行了详细 介绍，最后提出了网络编码应用于无线网络中，即遍历接收节点的网络编码实现 算法中存在的问题。 第三章“基于滑动窗口的连续无线网络编码改进算法 。本章通过遍历接收节 点的网络编码的算法中存在的一些问题，提出了一种基于滑动窗口的网络编码策 略，该算法是对原算法的改进，使网络编码算法得到进一步的优化。 第四章“基于滑动窗口的网络编码的仿真建模与实现 。通过o p n e t 仿真工 具对普通重传、遍历接收节点的网络编码算法及本文所提出基于滑动窗口的网络 编码算法进行仿真实现，验证了该算法的可行性。 第五章“结论及未来的工作。对全文进行总结，并展望下一步的研究工作。 5 重庆邮电大学硕士论文 第二章网络编码原理和应用概述 第二章网络编码原理和应用概述 2 1 网络编码的基本原理 利用无线网络信道的广播特性，网络编码可以增加信道的传输容量。图2 1 所示为传统的存储转发方式和基于网络编码的信息转发方式的例子，即节点a 和 节点b 通过中间节点s 进行信息互换。对于传统的存储转发方式，首先，节点a 和节点b 分别传输信息包k 和托到中间节点s 。节点s 将信息包z 和五分别进 行广播，因此，完成信息交互需要经过4 次传输。而基于网络编码的方式，信息 包丘和托在中间节点s 处进行异或编码，得到编码后的信息包置。以，然后， 将信息包五0 五进行广播发送。由于节点a 和b 分别有信息包咒和咒，因此通 过异或操作，节点a 和节点b 可以通过解码得到信息包咒和咒，由此可知，完成 信息交互只需要经过3 次传输。网络编码方法与传统方式相比，减少了传输次数， 提高了无线网络的性能【3 1 】。 x o x o 固一竺8 ( b ) ) 传统方法信息互挟( b ) 基于网络编码方法的信息互换 图2 1 传统的转发方式和基于网络编码方法的信息交换比较 2 2 网络编码的优势和不足 r a h l s w e d c 等人【l 】结合图论等内容提出了网络编码的概念，指出网络编码可 以提高网络容量，达到网络的最大流。人们通过不断的研究发现网络编码多播与 传统的路由多播相比，不仅在网络容量方面有很大的优势，而且在其它方面也有 很大的好处，以下是网络编码的优点t ( 1 ) 提高网络的吞吐量 图论的最大流最小割定理可以确定网络容量的最大值，通过研究发现网络编 6 重庆邮电大学硕士论文 第二章网络编码原理和应用概述 码可以使网络的传输速率达到最大值，因此这也成为网络编码的最大优点。当接 收节点的个数大于等于2 时，通常使用网络编码的方法来达到组播的最佳方式。 若一个网络各条链路上的容量已给定，则组播的最佳方式就是源节点到一系列接 收节点间组播的最大吞吐量。如果中间节点将编码后的数据进行传输，则就可以 将资源利用率达到最大，从而达到理论上的传输速率的最大值。 ( 2 ) 均衡网络负载 组播路由协议主要可以分为基于信源节点的路由协议和基于核心节点的路由 协议。基于信源节点的路由协议，由于该协议是由多个信源数的叠加，因此，会 使某链路上的流量过载，网络的服务质量下降；基于核心节点的路由协议由于信 息都从核心节点经过，因此就会使流量过分集中于该节点上。而基于网络编码的 组播将多条路径上的信息进行叠加后，对叠加后的数据进行传输，因此可以使网 络的负载均衡。 ( 3 ) 减少能耗 在无线网络中尤其是传感器网络中，节点的能量都是通过电池来提供的，因 此能量的消耗便成为衡量无线网络性能的重要指标。 t t et 4 c 。 。 。 图2 2 网络编码减少能耗 图2 2 ( a ) 是由8 个节点组成的一个无线网络。信源节点s 将信息通过多播的方 式发送到接收节点t l 和t 2 。而节点只能与周围的两个节点进行直接通信。假设传输 一次需要消耗1 个单位的能量。则使用传统的多播方式进行传输，共需要消耗5 个单位的能量。图2 2 0 ) 是通过基于网络编码的方式来实现信息的组播传输，信源 节点分别将信息x l 和x 2 传输到t l 和t 2 接收节点。t 1 和t 2 节点再将其传输到公共的 中间节点e ，在中间节点e 处，对信息x l 和x 2 做异或运算后，再将异或后的信息 包广播发送，这样在节点t l 和t 2 处通过解码可以提到所需要的信息x l 和x 2 。采用 网络编码方式的多播传输过程中，共经历了9 次广播，因此每比特消耗的能量为 4 5 。由此可以看出，基于网络编码方式的多播传输与传统的重传方式相比，可以 有效地减少网络能量的消耗。 7 重庆邮电大学硕士论文 第二章网络编码原理和应用概述 另外，在无线网络中，通过跨层设计【3 2 】将物理层的广播特性与网络编码相结 合，可以实现最大限度的延长网络生命周期。 ( 4 ) 提高网络的鲁棒性【3 3 】 在实际的网络中，链路和节点的失效会影响网络的鲁棒性。然而当通信链路 失效时，传统恢复链路的方法是基于整个网络去寻找新的路由。k o e t t e r 等【3 4 】证明 了：在组播方式中，可以设计网络最大鲁棒性的编码策略及适用于所有链路失效 的通用方案。在基于网络编码的组播网络中，若链路失效，源节点的信息发送速 率仍小于源节点和接收节点的最小割时，则存在一种网络编码方式，即静态的编 码方式。该编码方式恢复网络链路的方法是基于接收节点的编码方式。该方法不 需要重新寻找路由，只需要接收节点对不同的失效链路情况进行译码变换，而不 改变其它编码变换就可恢复出源节点发送的数据信息。与传统的失效路径恢复方 法相比，该方法更有效地节省了网络的带宽，并且当链路失效时，数据也不存在 丢失问题。 ( 5 ) 提高网络的安全性 由于网络编码是在中间节点对数据进行处理。假设数据信息在链路上被他人 所截取到，由于没有收到可解码的信息，因此，即使截取到数据信息，也得不到 真正的数据，可以确保数据的安全性。 虽然当前的网络编码拥有众多优点，但是还有一些无法克服的弊端。网络编 码的缺点主要表现在以下几个方面： ( 1 ) 由于经过网络编码的信息包是经过处理的，因此有一个包丢失就会使多 个信息包不能解码； ( 2 ) 在某个接收节点，只有当接收到足够的信息包后才能进行解码； ( 3 ) 由于中间节点对信息包进行编码的选取、对算法进行计算等处理，因此 时延会增大。 2 3 网络编码的应用领域 数据链路层和网络层中的两个核心问题是编码和路由，通过网络编码能够有 机地将二者结合在一起，改变了中间节点只对信息进行存储转发的传统模式，从 而建立起一种全新的信息编码和传输方式。网络编码的应用并非只局限于提高网 络吞吐量，当与其它技术相结合时，还可以应用于多个领域： ( 1 ) 内容分布式存储与分发 传统的分布式存储与分发是基于p e e r 之间传送的原始数据块，因此具有p e e r 节点的搜索定位、设计数据分发路由、均衡网络负载及资源分发与优化调度算法 8 重庆邮电大学硕士论文第二章网络编码原理和应用概述 等问题是分布式分发目前所无法解决的难题。而在p e e r 之间进行传输时，通过网 络编码运算则可以很好的解决这些问题，甚至可以避免。 ( 2 ) 应用层组播 由于组播功能不仅在网络层进行运用，现在也扩展到了应用层。在p 2 p 应用 层组播系统中，节点p e e r 不仅对数据进行存储转发，而且可以进行网络编码处理， 因此很大程度上改善了应用层的组播性能，提高了覆盖网络的数据吞吐能力。 ( 3 ) 获取无线传感器网络中的数据 在无线传感器网络中，由于传感器节点的存储数据能力十分有限，因此如何 将这些节点信息的采集在最大容量、最小耗能、最小代价等条件下发送给接收节 点是网络编码在无线网络研究中的一个新课题。 ( 4 ) 网络管理 如果链路断开，则传统的方法是启用备用链路，重新进行路由选择，而对使 用网络编码的节点，则不需要重新查找路由，只需改变编码规则就可以传送其它 节点的信息，该方法不仅起到了重新选路的作用，而且该网络管理方式可以减少 网络的开销。 2 4 网络编码应用于无线网络广播重传的基本原理 与传统的有线网络相比，无线网络由于环境的影响，信息包在传输过程中发 生错误传输或丢失的概率明显增多，因此，就必须使用重传策略对错误的信息包 进行处理。在传统的重传策略中，源节点收到目的节点反馈的出错或丢失信息后， 对出错或丢失的信息包进行重传，以此来恢复错误或丢失的信息包。信息包出错 或丢失数目越大，需要重传的次数就会越多，因此，无线网络信道的利用率就会 下降。 为了提高无线网络的信道利用率，将网络编码应用于无线网络的广播重传中， 以达到使无线网络的广播重传次数减少的目的。但是，基于网络编码的无线广播 重传策略需解决以下几个方面的问题：如何将网络编码的信息包进行组合； 如果重传的编码信息包传输错误或丢失，该如何处理。 2 4 1 广播重传策略在无线网络中的基本模型 为了分析广播重传策略的基本原理，我们设定一个具有1 个广播节点和个 接收节点的多节点无线广播网络，并假设该网络的传输损耗较严重，损耗率大于 5 0 。网络模型如图2 3 所示【3 5 】。 在该模型中，对无线网络中的广播重传策略做出以下假设： 9 重庆邮电大学硕士论文第二章网络编码原理和应用概述 假设1 所有数据传输都是通过信息包来完成的。广播源节点以固定的间隔时 间( t ) 广播信息包，每次广播操作都将一个信息包传输到所有的接收节点。n 个接 收节点传输丢包率互不相关，且服从伯努利分布，对应某个接收节点i 的丢包率为 p i o 小 u r e c e 量v i n gn 州ef r o m1t on 图2 3 多个接收节点的无线网络广播模型 假设2 广播节点能获得接收节点信息包丢失情况：a 信息包是否丢失；b 丢 失信息包序列号和丢失节点序列号。节点丢失情况的获得通过a c k n a c k s 来完 成，假定a c 跳c k s 不存在损耗。 假设3 广播节点知道接收节点的情况后，将对应的接收情况保存在缓存列表 中，缓存列表内容包括接收节点的序列号和信息包的接收情况。缓存中的行表示 接收节点情况，列表示信息包接收情况。如果某个信息包在某个接收节点成功接 收，矩阵相应位置赋值为o ；若丢失，相应位置赋值为1 。 以上的广播重传策略模型简化地描述了无线广播网络重传策略操作。该模型 假定了广播源的缓存列表，该列表可以直观反应广播操作的发送情况和接收情况。 2 4 2 基于网络编码广播重传策略的基本思想 基于网络编码的重传策略用于无线网络广播模型中，针对多个接收节点，通 过编码组合不同的丢失包来进行重传，减少重传发送次数。如图2 4 所示为5 个 接收节点，广播源节点( 即中心节点) 发送1 0 个信息包的示例【3 2 】。 由图2 4 ( a ) 可知，在给5 个接收节点传输1 0 个信息包的过程中，共有2 5 个信 息包丢失，因此丢包率为5 0 ，在假定重传包不损耗的情况下，传统的重传策略， 需要重传所有的信息包，即1 0 个信息包均需重传。 在该例中，应用基于网络编码的重传策略，可以计算得到1 0 2 0 3 ，4 0 5