（通信与信息系统专业论文）网络编码在无线网络中的应用.pdf

摘要 2 0 0 0 年，r a h l s w d e e 等人从信息论的角度出发，提出了网络编码的概念， 它可以大大提高网络中的传输容量，从而实现利用有限的网络资源传输更多的信 息。网络编码的基本原理是在中间节点上对接收到的信息进行一定形式的编码处 理，然后再传输出去。在信宿节点上，通过一定的处理方式，译出信源所发的信 息。网络编码的提出彻底地改变了计算机通信网络中的信息处理方式，其研究结 合了信息论、计算机通信网络、多路路由技术、多用户信息论等很多方面的知识。 本文首先对网络编码的基本理论进行了全面系统的介绍；然后结合无线网络 知识、多路径路由知识和传感器网络知识，架设了实际的基于网络编码的无线网 络演示平台；该平台通过多个搭载射频芯片的无线节点模拟了一个多用户的无线 传输网络，在该网络中通过实际的数据传输证明了在无线网络中应用网络编码可 以较大地提高网络吞吐量、降低网络时延和维持网络性能。 最后本文提出了一种新的多路路由网络编码传输方案，该方案包括了新的 m a c 协议，硬件协议，路由协议，传输协议和存储控制协议；新的方案通过新的 m a c 协议和传输协议大大降低了网络时隙和数据传输次数；通过新的硬件协议和 存储控制协议减轻了节点的存储压力，降低了网络编码对中继节点的要求；并且 在降低网络时延和传输次数的同时，增大了最优编码的机会，提高了网络编码增 益；因而，新的方案提高了网络吞吐量和中继节点的转发效率，改善了网络的性 能。 关键词：网络编码多路路由无线网络网络编码跨层设计 a b s t r a c t o nt h eb a s i so fi n f o r m a t i o nt h e o r y , r a h l s w d ea n ds o m er e s e a r c h e r sp u t f o r w a r dt h ec o n c e p t i o no fn e t w o r kc o d i n gi n2 0 0 0 ，w h i c hc o u l dh i g h l yi m p r o v et h e t r a n s m i s s i o nc a p a c i t yo ft h en e t w o r ki no r d e rt ot r a n s m i tm o r ei n f o r m a t i o nw i t ht h e l i m i t e dn e t w o r kr e s o u r c e t h er a t i o n a l eo fn e t w o r kc o d i n gi st of i r s tp r o c e s st h e i n f o r m a t i o nr e c e i v e do nt h er e l a y s ，t h e nt ot r a n s m i ti t , a n df i n a l l yt od e c o d et h e i n f o r m a t i o nr e c e i v e df r o mt h es o u r c eo nt h es i n k 、) l ，i t l l as p e c i a lp r o c e s s t h e c o n c e p t i o no f n e t w o r kc o d i n gh a st o t a l l yc h a n g e dt h ew a yo fi n f o r m a t i o np r o c e s s i n g i nn e t w o r k i n g ，w h i c hc o m b i n e st h ek n o w l e d g eo fi n f o r m a t i o nt h e o r y , c o m m u n i c a t i o n n e t w o r k , m u l t i - p a t hr o u t i n g ，a n dm u l t i u s e ri n f o r m a t i o nt h e o r y , e t e t h i sp a p e rf i r s tg i v e sag e n e r a la n ds c i e n t i f i cd e s c r i p t i o na b o u tt h eb a s i ct h e o r y o fn e t w o r kc o d i n g s e c o n d l y , c o m b i n i n gt h ek n o w l e d g eo fw i r e l e s sn e t w o r k , m u l t i p a t hr o u t i n ga n ds e n s o rn e t w o r k , t h ep a p e rb u i l d sa r e a ld i s p l a yp l a t f o r mo f w i r e l e s sn e t w o r kb a s e do nn e t w o r kc o d i n g ；t h ep l a t f o r m ，w h i c hi sc o m p o s e do fs o m e w i r e l e s sn o d e st h a tc o n t a i nr fc h i p ，s i m u l a t e sam u l t i - u s e rw i r e l e s st r a n s m i s s i o n n e t w o r k , i nw h i c h i tc a l lb ep r o v e dt h a tt h ea 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 s n e t w o r kt h r o u g ha c t u a ld a t at r a n s m i s s i o nc o u l dl a r g e l yi m p r o v et h et h r o u g h p u to f n e t w o r k ，g r e a t l yr e d u c et h en e t w o r kd e l a ya n dm a i n t a i nt h ee f f i c i e n c yo ft h e n e t w o r k f i n a l l y ，t h ep a p e rr a i s e s an e wn e t w o r ke n c o d i n gt r a n s m i s s i o ns c h e m eo f m u l t i p a t hr o u t i n g ，w h i c hi n c l u d e sn e wm a c p r o t o c o l ，h a r d w a r ep r o t o c o l ，r o u t i n g p r o t o c o l ，t r a n s m i s s i o np r o t o c o la n ds t o r a g ec o n t r o l l i n gp r o t o c 0 1 t h en e wm a c p r o t o c o l a n dt r a n s m i s s i o np r o t o c o lc a l lh i g h l yr e d u c et h en e t w o r ks l o t a n d t r a n s m i s s i o nf r e q u e n c y t h en e wh a r d w a r ep r o t o c o la n ds t o r a g ec o n t r o l l i n gp r o t o c o l c a nl e s s e nt h es t o r a g ep r e s s u r eo f t h en o d ea n dl o w e rt h er e q u i r e m e n t so ft h en e t w o r k c o d i n go nt h er e l a y m e a n w h i l e ，t h e yc a ni n c r e a s et h eo p p o r t u n i t yo ft h eo p t i m u m c o d i n ga n de n h a n c et h en e t w o r kc o d i n gg a i n t h e r e f o r e ，t h en e wp r o g r a m c a n i m p r o v et h et h r o u g h p u to f n e t w o r ka n dt h er e t r a n s m i s s i o ne f f i c i e n c ya tt h er e l a y ，a n d e n h a n c et h ef u n c t i o no fn e t w o r k k e y w o r d s ：n e t w o r kc o d i n g m u l t i p a t hr o u t i n g w i r e l e s sn e t w o r k c r o s s 1 a y e r - d e s i g n i n g ； 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指 导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所 罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果：也不包含为获得 西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 风 日期： a 口j0 、弓1a 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论 文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采 用影印、缩印或其它复印手段保存论文。同时本人保证，毕业后结合学位论文研究课题 再撰写的文章一律署名单位为西安电子科技大学。( 保密的论文在解密后遵循此规定) 本人签名： 导师签名： 日期如，d 、弓、p 日期 劢勿。；i 汹 虹一 第一章绪论 第一章绪论 随着当今科技发展的日新月异，各种无线通信终端已经深入到人们日常生活 的各个领域，从普通百姓的日常通信、生活必须，到军事、环境监测和预报、健 康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、大 型车间和仓储管理，以及机场、大型工业园区的安全监测等领域都可以看见无线 通信的影子。无线网络在配置、安装、修改和扩展等方面的成本都低于有线网络。 特别是通过无线网络可以很方便地接入移动设备，这将大大提高工作人员的工作 效率和精确性。 于此同时，无线网络编码技术作为一种新的技术在宽带无线网络中得到了飞 速的发展。网络编码改变了传统的“存储转发模式，中间节点将输入信息进行 编码后才发送出去。研究表明，现有的无线网络都可以通过使用网络编码技术显 著提高网络的吞吐率、可靠性、鲁棒性等等。为此，无线网络与网络编码技术相 结合的研究已经成为了一个新的研究热点。 1 1 研究目标与意义 2 0 0 0 年，香港中文大学的y e u n g 等人【l j 首次提出网络编码这一全新概念， 随着研究的深入，研究者发现网络编码在无线网络中有着巨大的应用潜力1 2 圳。 本文主要研究的是网络编码技术在无线网络应用中的相关问题，并通过实际的演 示平台验证网络编码给无线网络带来的益处。通过深入研究网络编码和多路径路 由以及无线传感器网络，综合、改进现有的编码方式为无线网络带来更高的吞吐 率、可靠性和时延消耗，结合无线传感器网络，架设出网络编码在无线网络中的 实际运用的平台，并提出了一种新的时延较小的多路路由网络编码传输方案。 当前的研究表明应用网络编码就可以提高无线网络的吞吐率【4 副。在传统的 网络中，中继节点只能对接收到的信号进行复制和转发，这种方式一般很难使通 信达到较高的效率。网络编码技术则打破了这种限制，节点可以在不提高带宽消 耗的情况下从编码数据包中解码出自己需要的信息。在网络编码下，不同的信息 可以同时通过有限的链路，从而提高网络流量。y e u n g 等人【l j 已经证明网络编码 的应用可以使通信达到信道最大容量。 相对于有线网络，无线网络的可靠性一般较低。而网络编码与无线信道的广 播特性和多路径路由充分结合起来是可以提高分布式无线网络传输可靠性的。在 不使用网络编码时，各种节点源节点需要确切的直到它发送的数据包是否能被目 的节点正确地接收到，如若不能，网络就需要重新传送失败的数据包，在这种策 网络编码在无线网络中的应用 略下，用于控制传输的确认信息( a c k 消息) 将耗费大量的带宽。在多跳的无线网 络中，使用传统的重传方式会造成很大的时延，严重影响数据的传输效率。而使 用网络编码后，路由器可以将缓存中所有的数据包放在一起进行编码，这些编码 数据包含有整个数据的等量信息，即所有的编码数据包是无差异的，目的节点在 可以解码时对所有的数据只进行一次确认即可。因此，网络编码的应用在提高网 络可靠性的同时还能有提高协议的执行效率。然而，当前的用于提高可靠性的网 路编码策略存在计算量大、时延高和传输次数过多等缺点，为此，本文将研究和 改进现有的编码策略以缓解这些问题。 网络编码的应用给无线网络带来各种好处的同时，却给实时应用带来新的问 题：因为数据包需要解码之后才能被上层协议使用，参与编码的数据越多，则传 输这些数据需要的时间也会越长，然而，若是编码的数据太少则不能充分利用网 络编码带来的优势。这些问题，都在本文所进行的将网络编码应用到实际的无线 网络平台中得以验证，为此，我们设计了一套新的在无线网络中运用网路编码的 传输体制。 1 2 研究现状 在分布式无线网络中，每个节点都可以与一个或者多个节点进行直接通信。 这种结构中，终端节点可以是普通的v o i p 手机、笔记本电脑和无线p d a 等。这 些无线终端可以自己组成独立的无线网络也可以接入到更上层的网络中。目前， 网络编码是国际信息论和网络理论领域所关注的热点，y e u n g 等人【8 , 9 1 从信息论 的角度提出并分析了网络编码的理论模型，而k o e t t e r 等人【lo j 则从代数的角度对 网络编码特别是线性网络编码进行了解释并进一步证明了存在满足多播容量的 线性时不变编码。h o 等人【l i j 综合了以上的工作并提出了随机网络编码，而随机 网络编码的出现将网络编码带入了更为实用的分布式网络中1 1 2 , 1 3 】。2 0 0 6 年h a m r a 等人【1 4 j 的研究将网络编码引入无线网络中，随后这方面的研究也迅速成为关注的 热点 1 5 , 1 6 。 最近，网络编码理论及其应用的研究引起了国内外学者的广泛关注，不断有 新的学术成果出现。在国外，如普林斯顿大学【1 7 , 1 8 】和m i t 1 9 ，2 0 】研究并分析了网络 编码在多播网络中对路由和吞吐率的影响、微软实验室【2 1 ，2 2 2 3 】贝f j 在网络编码的实 用技术方面积极开展研究工作。香港中文大学的y e u n g 和西安电子科技大学的 c a i 作为网络编码理论的创始人，主要从事网络编码的基础理论 2 4 , 2 5 】，和网络编 码的安全性2 6 2 7 2 8 1 等方面的研究，他们在网络编码的研究邻域内具有非常大的影 响力。下面将从网络编码策略、无线可靠性和无线业务的时延这三个方面对无线 网络编码的研究现状进行讨论。 第一章绪论 1 2 1 网络编码的基本策略 现有的网络编码基本策略一般分为两个大类，一类以数据包异或运算作为网 络编码的基本操作1 2 9 即娜l ，每个节点对传输媒体进行机会主义侦听( o p p o r t u n i s t i c l i s t e n i n g ) ，以获得其邻居节点的状态信息，决定进行编码的机会，并在本地的缓 存内进行机会编码( o p p o r t u n i s t i cc o d i n g ) 。节点利用本地信息各自决定哪些数据 包需要进行异或编码运算，这一机制可以称为机会路由机铝1 ( o p p o r t u n i s t i c r o u t i n g ) 。典型的协议是s a c h i nk a t t i 等人1 3 , 3 2 1 提出了的c o p e 协议，在无线网络 中，c o p e 使得即使在网络流量需求未知或者网络状态动态变化的情况下，协议 仍能有效地支持多路单播流的传输。随后的研究者对c o p e 协议的细节进行了更 进一步的研究，d o n g 等人1 1 3 j 将c o p e 应用在t c p 层用于提高网络的吞吐率，2 0 0 8 年j i l i nl e 等人1 3 3 j 讨论了c o p e 中同时参与异或运算的数据包数量的问题。 r i c h a r da l i m i 等人1 3 0 贝j j 提出了i p a c k 算法以提高无线网络的吞吐率。t a oc u i 等 人【2 9 】则从能耗的角度设计出了c o p r 协议，通过仿真实验他们宣称该协议比一 般的纯路由协议节省能量达到2 5 。然而，在这种以异或运算为基础的编码方式 下，节点并不是所有的节点都进行网络编码操作，在具有多跳特点的无线网络中 会有其局限性。 另一种方式则采用了基于数据块的随机网络编码，在2 0 0 3 年，p c h o u 等人 3 4 , 3 5 】提出一种面向实用的分布式编码策略，他对于包的随机丢失和时延都具有鲁 棒性，仿真结果显示这种方法能够使吞吐率接近网络容量。2 0 0 7 年，在这一框 架下c h a c h u l s k i 等人【3 6 1 在s i g c o m m 会议上发表论文提出了专门为无线多跳网 络设计的m o r e 协议，他们通过搭建了包含2 0 个节点的8 0 2 1 1 无线网络实验 平台，通过实验发现，根据目的节点数量的不同，m o r e 协议的较e x o r 协议口7 j 吞吐率可以提高3 5 2 0 0 之多。 1 2 2 网络编码与网络可靠性 随着随机网络编码在无线网络中应用研究的深入，研究人员对随机网络编码 对无线传输可靠性的提高进行了大量的研究。针对无线网络，o y m a n 等人p & 3 9 1 从理论到实践的角度分析了网络编码对提高可靠性的作用。l t m 等人1 4 0 , 4 1 , 4 2 j 多次 发表论文阐述在无线多跳网中使用网络编码提高m a c 层可靠性的单播、多播传 输策略，通过理论证明了随着参与编码数据包的增多利用随机网络编码策略可以 使通信速率无限逼近无线网络的最大容量( 最小割) 。g h a d e f i 等人 4 3 , 4 4 从理论上将 网络编码策略与传统方法进行了比较，他们的研究结果显示用网络编码较其它方 法能为无线网络提供更高的可靠性，若为节点的个数，端到端重传机制重传 网络编码在无线网络中的应用 次数的是利用网络编码后的o ( 1 0 9 n ) 倍。 1 2 3 网络编码与块时延 2 0 0 7 年m i t 的m e d a r d 等人1 4 5 】在分析无线网络编码遇到的机遇和挑战时候 提出，参与随机网络编码的数据块过大就可能会影响实时应用的性能，但是如果 数据包太少则会降低网络编码给无线网络带来的好处。近两年，这方面的研究也 逐渐引起研究者的关注4 7 1 ，2 0 0 8 年，m a h m i n o 等人【4 8 1 研究了保证单个数据包 在节点最大时延的方法，但并没有研究多个数据包的时延保证问题。我国清华大 学的m a 等人【4 9 】则从排队论的角度分析了网络编码条件下数据包在节点的等待 时延和业务流的统计特征。 1 3 本文的研究内容和章节组织 本文通过深入理解网络编码和无线网络领域近年来重要的研究成果，对网络 编码在无线网络的实际应用进行了深入地研究。 首先，本文主要对无线网络，网络编码，多路径路由和传感器网络进行了相 关研究；对m a c 协议，路由协议进行了深入地研究；介绍了网络编码的原理， 路由协议和多路径路由理论。 其次，本文介绍了对a t m l 2 8 微处理器的操作和相关程序的编写方法：介 绍了c c 2 4 2 0 无线射频芯片的使用方法；对无线传感器硬件进行了深入地探讨和 操作。在深刻理解了各种网络编码、多路径路由协议和8 0 2 1 5 4 等传输协议的基 础上，通过无线射频节点架设了实际的无线网络演示平台。 最后，通过对串口通信编程、m f c 串口类、a v rs t u d i o 环境的研究和应用， 编写了网络编码传输方案相关的硬件程序和软件应用程序，将网络编码应用到实 际的数据传输中。并在演示平台上，验证了网络编码给实际网络带来的增益，得 到了模拟结果。 此外，本文在现有的网络编码传输方案的基础上，提出了新的硬件协议， m a c 协议，路由协议，网络传输协议和存书控制协议等基础协议，并在此基础 之上提出了一种新的多路路由网络编码传输方案，与现有的网络编码方案相比， 该方案可以大大降低网络时延和数据包传输次数，提高网络吞吐量，稳定网络性 能。 本文安排了以下章节对上述内容进行了详细说明，具体的章节安排如下： 第一章绪论主要介绍了本文的研究背景，知识背景以及主要的研究任务和 成果。 第一章绪论 第二章背景知识主要介绍了网络编码和多路径路由的相关知识和原理，介 绍了c o p e 网络编码方案。 第三章仿真演示平台主要介绍了仿真演示平台的硬件基础和软件基础，以 及相关的协议和硬件设计，介绍了相关的标准和网络协议；并将网络编码应用到 此平台中，验证了应用网路编码给网络性能带来的增益，并与传统中继网络进行 了对比。 第四章介绍了一种新的无线网络多路路由网络传输方法，这个方法包括了 新的硬件协议，新的m a c 协议，新的路由协议，新的网络传输协议和节点存储 控制协议。 第五章总结全文的工作和研究成果进行了总结，并展望了下一步的研究方 向。 第二章背景知识 第二章背景知识 7 一 本章主要介绍了网络编码、多路径路由和c o p e 的相关知识。着重介绍了网 络编码的基本概念和原理，包括线性网络编码基本原理及构造方式；阐述了网络 编码的优点以及应用的方向。简要介绍了多路径路由的发展与现状，机会主义路 由协议产生和原理，并结合机会路由和最优编码阐述了c o p e 方案。 2 1 1 网络编码的提出和发展 2 1 网络编码概述 多播通信采用路由的方法无法确保信息传输速率达到最大流最小割定理所 确定的信源和信宿间的最大流量。针对多播通信存在的上述局限，2 0 0 0 年， a h l s w e d e 等人u j 在i e e et r a n s o ni n f o r m a t i o nt h e o r y 上发表了一篇题为“网络信 息流”的文章，为提高多播网络的传输容量指明了一个新的发展方向。他们从信 息论的角度出发，严格证明了在单点对多点的通信网络中，通过节点编码的方式 可使信息传输速率达到网络的最大流量，从而编码的方式优于路由的方式。这一 发现推翻了在中间节点上对传输的数据进行加工不会带来任何收益这一传统观 点，由此给网络通信带来了根本性的变革。 由于线性编码的简单性和实用性，l i ，y e u n g 和c a i 在后续工作中提出了线 性网络编码1 8 】，并构造了码率达到最大流量的线性码，证明了线性码的最优性。 这一工作奠定了网络编码的理论和应用基础，引起了更多人对网络编码的注意。 网络编码最初的研究主要针对多播网络传输，研究的角度主要是编码算法、 编码所带来的传输速率的提高程度、无线网络应用中编码带来的能耗减少程度 等。目前，对一个任意给定的多播网络进行网络编码算法主要有三种： 由k o e t t e r 等【l o 5 0 】于2 0 0 2 年提出的基于代数结构的网络编码算法，他将有限 域上的多项式法用到网络编码的研究中，为网络编码理论研究提供了有效的代数 研究工具。但是，这种算法是一种指数时间算法，其算法复杂度较大。 由s a n d e r s 等和j a g g i 等于2 0 0 3 年同时提出的一种基于网络信息流传播的多 项式时间算法【5 1 , 5 2 】。在从源点到各终端节点传输信息之前，该算法先通过一种简 单的路由算法选取源节点到各个终端节点的传输路径。这是第一次在网络编码中 考虑多播路由问题。与第一种算法相比而言，其算法复杂度大大降低。 t h o 等给出了随机网络编码算法【5 3 , 5 4 。该算法虽然简单，但是所需的编码 符号域较大，增加了编译码运算的复杂度。 8 网络编码在无线网络中的应用 基于网络编码的路由算法是另一前沿研究方向，目前仅有少数文献研究该内 容。k a p i lb h a t t a d 给出了基于网络编码多播传输的信息流的解释1 5 5 1 ，并提出最小 化参与网络编码包数目的分布式算法，及基于网络编码的有线路由算法( 包括 m u l t i c a s t 和u n i c a s t ) 。 c a i 和y e u n g 等【2 6 , 2 7 , 5 6 , 5 7 , 5 8 1 提出了基于网络编码的网络纠错编码概念。以网 络编码为基础，当信息在网络中传播时，若某一时刻有几条链路上传输的符号发 生错误，只要错误数没有超出纠错范围，终端接收节点通过恰当的译码可恢复出 正确的信息，而不需要信息重传。 s k a t t i 等人在2 0 0 8 年提出了c o p e t 3 j 网络编码方案，并将网络编码应用到 实际的无线网络中，证明了网络编码可以使网络性能得到较大的提高。 2 1 2 网络编码的基本原理 2 1 2 1 网络编码的简单示例 下面通过一个例子来说明网络编码的基本原理。有一个网络拓扑如图2 1 ， 甩户k 几 中继 ，以八 用户b 几厂 图2 1 网络编码原理不例 有两个用户，分别是用户a 和用户b ，他们之间有一个中继。其中用户a 要将消息m 1 发送给用户b ，同时用户b 要将消息m 2 发送给用户a ，那么传统 的复制转发网络完成这项任务的过程是： 1 、a 发送m 到中继； 2 、中继把m 发送到a 和b ，其中b 是接收者； 3 、b 发送m 2 到中继； 4 、中继把m 2 发送到a 和b ，其中a 是接收者。 至此，用户a 和b 完成了数据交换，整个局域网链路需要被占用4 个时隙。 如果应用网络编码的技术，那么完成同样任务的过程是： 1 、a 发送m 到中继； 2 、b 发送胞到中继； 3 、中继把m 1 与m 2 作一系列运算( 在例中用异或运算) ，然后把得到的结果 m 1om 2 发送到用户a 与用户b 。这样，用户a 可以根据运算，例如 m 1o ( m 1o 施) 得到m 2 ；同样用户b 也可以得到m 。而整个任务完成仅占用 了整个局域网链路3 个时隙。 第二章背景知识 9 2 1 2 2 网络编码的定义 设g = ( y ，e ) 为边的容量限为尺的一个多播网络，h 为信息从信源s 到信宿 t l , t 2 ，一 i l ，的多播传输速率。令信源s 到信宿节点t l 的最大流值为m a x f l o w ( s ，) ， 则对于所有，= l ，2 ，三，有厅一= m a x f l o w ( s ，t t ) ，即办嘣m i n m a x f l o w ( s ，) ， 将这个称作网络多播传输的最大流限。对于只有一个信宿节点的网络，依靠路由 就可以获得最大流。下面看一个具有两个信宿的多播网络，如何获得网络多播的 最大流。 c 图2 2 采用编码的具有两个信宿的多播网络 图2 2 是一个具有两个信宿节点的单位容量多播网络。假设各条链路无差错 和无时延。图2 2 ( a ) 显示了各个边的容量，由无向图的最大流最小割定理有 m a xt l o w ( s ，尼) = 2 ，= 1 , 2 。由最大流限，可以知信源到信宿尺l 和足2 的最大传播 速率不可能超过2 。图2 2 ( b ) 是采用普通路由转发方式传输2 b i t 到信宿r t 和r 2 。 由对称性可以得到，信源s 的输出边各传输1 比特，在节点f ，i = i ，2 ，比特口和 b 分别被复制，它们的复本分别输送到两个输出边。在节点3 ，由于a 和b 被同 时接收到，但只有一条输出边，只能随机选择一比特送到输出边( 3 ，4 ) 。假设如图 选择口，则在接收节点r 2 ，a 和b 可同时被接收到。然而接收节点r 只能接收到 两个复本口，无法恢复出比特b 。因此这种路由方式不是有效的。对于这一网络， 给斟 网络编码在无线网络中的应用 采用传统的路由转发的方法是不能够达到网络多播的最大流限。 然而，如果允许节点采用编码，就实际上可以获得最大流限。如图2 2 ( c ) ， 显示了一种将口和b 同时发送到信宿节点尺- 和r z 的方案，这里“+ 为模2 加。 这样接收节点r - 接收到a 和口+ b ，将口和口+ b 模2 加可恢复出b 。同理，接收节 点r z 。可恢复出a 和6 。如果不采用编码，就必须多发送一个比特。如图2 2 ( d ) 所示，链路( 3 ，4 ) 的容量将超过了1 。 2 1 3 网络编码的优点 网络编码思想突破了传统数据传输的固定模式，带来了许多潜在优点： 首先，与传统的路由传输方式相比，网络编码可提高网络的信息传输速率， 增加网络的信息吞吐量( t h r o u g h p u t ) 。文献【1 7 3 5 1 通过网络拓扑图仿真也表明编码 可有效地提高多播容量。在无向图网络中，文献【5 9 】证明了网络编码网络比普通 路由转发网络最多能提高两倍的吞吐量。 其次，网络编码可充分利用网络上的信道，使数据传输普适化( u n i v e r s a l ) 。 在构造网络编码及其编码器时不需知道信息接收者在网络中的具体位置；即使在 从信源到某一节点的最大流量小于信源的信息率的情况下，在该节点的用户也可 以收到信源所产生的消息的部分信息，这样此用户就可以利用这部分信息对信源 消息作满足一定失真准则的编码或列表译码；局域网可以轻易地接入主干网上 【9 ，6 0 1 o 第三，网络编码可增加网络通信的鲁棒性和可调节性。经适当网络编码的数 据具有同等的重要性，因此只要用户收到了足够多( 无论来自什么地方) 的编码 数据，他都可以从这些数据正确地译出所需的消息来。 最后，当网络编码应用于无线通讯网络时 3 , 4 2 , 6 1 , 6 2 , 6 3 , 6 4 , 6 5 】，不仅可以提高信息 传输率，节约传输所需能量，而且可以使节点之间在所需能量方面进行折中 ( t r a d e o i f ) 6 4 1 。 综上，网络编码可广泛地应用在各种实际网络上，并可带来传统路由方式无 法实现的效益。 2 1 4 线性网络编码 网络编码方案可分为线性和非线性两种，所谓线性网络编码【1 1 也就是在实现 网络编码过程中所用到的编码函数和译码函数均采用线性函数来实现。线性网络 编码是中间节点将接收数据在某有限域内进行线性组合，节点接收足够数量的独 立数据包就可以通过正确译码解得全部信息内容，能充分利用网络带宽。假设每 第二章背景知识 个信息数据包为三比特，当它与要组合的数据包长度不同时，较短的信息附加额 外一串“0 ”，将包中的j 个连续比特组成域上的一个符号，则一个包中包含l s 个符号。在线性编码下，运用乘法和加法运算，使从节点发送出去的数据为该节 点接收到信息的线性组合。 2 1 4 1 编码过程 假设一个源或多个源产生的原始数据包信息为m ，m 。，则在线性网络编码 中传输的数据可表示为为 x = ：。m ， ( 2 1 ) 其中蜀岛表示相应的编码系数，对每个符号有： 丘= ：。m ： ( 2 2 ) 其中m ：和五分别为肘。和x 的第k 个符号。 传输的数据包总计包括编码向量，又包括信息向量，编码向量用于接收端的 解码。编码过程采用迭代的方法，若一个节点已经接收和存储的包信息集合为 ( 9 7 ，x 7 ) 9 * oo ( g “，x ”) ，则该店可以通过选定的编码系数啊k 和运算式( 2 3 ) 得到新的信息包( ，x ) ，编码向量可以通过直接的代数计算得到式( 2 4 ) ， 该过程在若干个节点中重复操作。 r = 2 l h j x t ( 2 3 ) g ：= 2 l h , g n , g ( 2 一4 ) & 2 己一 l j 2 1 4 2 解码过程 假设节点接收集合为( 9 1 ，x 1 ) ，( g ”，x ”) ，为了恢复原始信息，需要求解 式( 2 5 ) 的m 个等式中的甩个未知数m ，恢复所有数据要求m r l ，也就是说 接收包的个数至少为原信息的个数。而有些线性组合可能是线性相关的，m 1 1 并 不是充分条件，但却是网络编码的重要条件。 x k ：。g l m ( 2 5 ) 解码需要求解一组线性方程。实际中，可以应用高斯消去的方法：节点存储 编码向量以及编码之后的结果，以行向量的形式，存储在所谓解码矩阵中。最初， 解码矩阵中只包含未经该节点编码的包以及与之相对应的编码向量( 如果有的 话1 ，否则为空。当接收到一个已编码包后，会从中抽取它的编码向量以及编码 结果，放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型，最终变成行 网络编码在无线网络中的应用 最简型。所收到的某一个包如果可以增加矩阵的秩，则称之为更新包，如果所收 到的包是非更新的，它可以通过等价变换变为全零，从而可以忽略。当解码矩阵 变换成最简型后，方程组得解。这种情况发生在当接收到玎个线性独立的编码向 量之后。 2 1 5 随机网络编码 确定性线性网络编码要求对所选择的系数进行验证，只有当选择的系数满足 一定的条件的时候才能成功地编码。这些算法是一种集中式的编码算法，需要知 道网络的整个拓扑结构，同时也要知道整个网络每个节点的编码过程。只有这样 才能保证边上选择的向量能够相互线性无关，同时选择的编码系数能使整个网络 有解。但这只是理想的状况。实际上，由于网络拓扑的变化和网络规模的扩大， 每一个节点了解整个网络结构和每个节点的编码系数不容易实现。所以，提出了 随机网络编码概念，以下作出介绍。 源节点把m 个数据包分为一组，把这m 个数据包记五，五，以，并赋予相 同的组标识。当源节点准备发送这m 个数据数据包五，k ，以时，会随机地从 有限域c 中随机选取m 个数，用这m 个数作为编码系数，对原始的m 个数据数 据包五，五，以进行编码，把原来的m 个数据编码成新的刀个数据包，记编码 第f 个数据包时所使用的m 个编码系数为g t l ，岛2 ，。删，记编码后的数据包为 z ，k ，e ，则编码的公式由式( 2 6 ) 所示，其中i - - 1 ，2 ，刀。 三 r = 芝：g i ，x ， ( 2 6 ) 再” 。 源节点在对数据进行编码后，生成z ，k ，k 个数据包。然后再把这一组数 据包的组标识，与每一个数据包的编码向量 l ， 2 ，& ，埘。作为头部信息添加 到数据首部，将数据包发出。 源节点发送出刀个数据包以后，对于从源节点到目的节点中间的节点来说， 它们会把一定时间间隔内收到的数据包在本地缓存，然后在这缓存的数据包中， 挑出具有相同组标识的数据包，再从有限域e 中挑选一组系数，其系数个数等 于这一组数据包个数，然后对这一组数据包进行重新编码，重新编码后生成了新 的编码系数，编码生成的数据包个数等于该组数据包的个数。记中间节点为， 记它收到的具有相同组标识的数据包个数为k ，记该组数据包为i = 1 ，2 ，k ， 其中的编码数据为墨，五，砭，第f 个数据包携带的编码向量记为蜀 l ，蜀 2 ，。； 记这一组数据包经过中间节点，编码后生成的k 个数据为y l r9 k 7 ，k 7 ，记中间 节点，在编码第f 个数据包1 7 时选取的系数为或。，：，9 0 ，则中间节点，对收 第二章背景知识 到的数据包进行再编码的方法可以由式( 2 7 ) 表示出来。 七 r 7 = 吒 ( 2 7 ) j = l 同时，由式( 2 7 ) 也可以得到中间节点，再编码后的数据与源数据包的关系， 如式( 2 8 ) 所示，其中的红，就是编码第i 个数据包r 7 所使用的与源数据包相关的 编码系数，这组编码系数作为编码后数据包的首部，与再编码后的数据组合成新 的数据包。 z 7 = 红， ( 2 8 ) j = l 从而可以求出中间节点再编码后的数据的编码向量，可以由式( 2 9 ) 表示出 来。 七 = & ， ( 2 9 ) f 王l 中间节点对它所收到的数据包进行再编码的意义在于：通过这样的多次编 码，可以进一步降低目的节点收到的报文间的线性相关性。因为，当目的节点接 收到一定数量编码后的数据包以后，会判断数据包总数是否大于或等于肌，只有 当数据包总数大于等于m 时，才有可能通过矩阵转换来解码出原始的m 个数据 包。假设节点收到了所个数据包，会再进一步判断这m 个数据包中携带的编码 系数的线性相关性。记目的节点收到的朋个数据包中的编码数据为k ，艺，匕， 其中的第f 个数据包携带的编码向量为j ，g ，g j ，。如果由所有的编码向量组 成的编码系数矩阵满秩，则可以通过式( 2 1 0 ) ，恢复出原始的历个数据包。 五 置 x 。 岛。1 - 1 i l a m 。 x k ： 匕 ( 2 1 0 ) 由式( 2 1 0 ) 也可以看出，由编码向量所组成的矩阵是否满秩，关系着目的节 点是否能解码出原始数据包。而在随机线性网络编码中，对编码向量的选取是随 机地从有限域中挑选出来。可见，增大有限域可以减少目的节点收到的向量 线性相关的概率。 2 1 6 实用网络编码的基本技术 当前，无线网络编码策略并没有统一的标准，要在无线网络中实现随机网络 编码策略应用需要有三个关键技术：随机编码技术( r a n d o mc o d i n g ) 、包标记技 网络编码在无线网络中的应用 ：术( p a c k e tt a g g i n g ) 和缓存技术( b u f f e r i n g ) 3 4 3 5 1 。通过随机编码能使网络编码实现 分布式处理；包标记使网络编码技术应用到分组交换网络成为可能；缓存技术使 网络编码策略在现实中的异步网络实现数据包同步。 2 1 6 1 随机编码技术 源节点向目的节点发送数据前，首先将要传递的信息拆分为，个数据块 ( b l o c k s ) 蜀，b 2 ，b 1 ) ，数据块b 。又由k 。数据包组成，不同的数据块分成的 数据包数量可能会不相同，则称：数据块曰。的大小为k 。然后使用前面将介绍 的随机线性编码方式对各个数据块分别进行编码。在源节点从未进行过编码的数 据本文称之为：本地数据包( n a t i v ep a c k e t ) ，而网络中传输的数据包都是经过线 性随机网络编码处理的，为了区别，称这些数据包为编码数据包( c o d e dp a c k e t ) 。 若编码数据包只可由数据块b 。的本地数据包线性表示则称：只属于数据块b 。 网络编码的节点都会缓存接收到的线性无关编码数据包，当节点接收到k 。 个属于当前数据块b 。的线性无关数据包时，本文中称该节点：数据块占。可解码。 2 1 6 2 包标记技术 根据前面的介绍，传输数据块口。时，每个数据包就需要使用一个k 。维向量 来记录全局编码向量g ( e ) ，数据包中加入包标记后，编码原理可由式( 2 1 1 ) 表示。 那么当个节点接收到数据包以后可以从中获取所需的解码信息。而且这个方法 可以很方便的实现，数据包其它部分和原来的处理没有任何区别。需要解码的节 点可以用高斯消元法来恢复原来的消息。 l ；。i；i g 任曩1x k n 乏吲 ，i ； ；ii i l o ，lx 砌，2x 勋， ，j 使用包标记技术后，在未知拓扑结构的分布式无线网络中，接收者可以根据 包标记的全局编码向量为依据进行解码操作，甚至是有新的节点加入或者退出都 对解码成功率没有影响，即使有包丢失或者节点失效都可以保证解码概率。 然而，使用包标记后需要付出的代价是：每个数据包中必须多携带的足。个 符号。例如当编码有限域e 的大小口= 2 ”时，每个编码向量符号可由，z 比特表示 ( 1 0 9 ，( 2 “) = 刀) ，且数据包的总长度为三字节时，增加的负载占数据包总长度的比 、，l_ 2， = l、，一 、，、， i l p p l，l y y 第二章背景知识 僦为k ，f l o 2 1 6 3 缓存技术 仅使用前面介绍的数据包结构还不能让随机网络编码能够在实际网络中正 常使用。为了让网络编码能够在实际网络中使用，首先要保证属于同一数据块的 数据包才能放在一起操作。因此每个数据包都需要加上一个序号用于区别他们所 属的不同数据块。一般来说，数据块的序号一般是顺序递增的，在传输中用一至 两个字节就足够对网络中所有的数据块进行编号以示区别了。区分了数据块之 后，节点就可以根据数据包的这一序号来决定哪些数据包能够放在