（通信与信息系统专业论文）无线网络编码研究.pdf

大连理工大学硕士学位论文 摘要 2 0 0 0 年，香港中文大学的a h l s w e d e 等人率先提出了网络编码这一概念，该理论通 过允许中间节点在转发信息前对输入信息流进行编码来实现网络多播容量的极限，打破 了通信网络中中间节点只负责接收信息复制与转发的传统信息处理方式，即路由方式， 充分挖掘了网络潜在的能力。研究表明，网络编码除了能够提高系统的容量外，在数据 压缩、负载均衡、降低节点能量消耗、减少传播时延、提高网络健壮性及信息安全等方 面都有重要的应用前景。 网络编码的研究不仅涉及有线通信网络，如i n t e r n e t ，还涉及无线通信网络，如a d h o e 网络、无线传感器网络以及无线m e s h 网络等多个领域。作者主要对网络编码在a d h o e 网络中的应用进行了研究。 在a dh o e 网络中，信息传输之前一般要通过路由发现过程来建立源节点和目的节 点之间的路径。泛洪式的广播算法因其简单的特点被作为实现这一过程的常用方式，但 网络节点密度大时容易形成广播风暴。在信息传输时，通常是在源节点和目的节点之间 建立单一路径来实现，这种方式简单易维护。但网络负载过重时会导致路径上节点能量 消耗过快而失效，严重时造成网络的割裂。鉴于网络编码在改善网络性能方面的优势， 作者将网络编码分别应用到a dh o c 网络中上述两个过程中，提出并实现了性能更优的 算法。本文完成的工作主要有以下几个方面： 7 l 、详细阐述了网络编码的基本原理，并介绍了网络编码在a d h o e 网络中的应用。 2 、将网络编码应用于a d h o e 网络的路由发现过程中，实现基于网络编码方式的广 播算法，降低广播包的数量并提高广播投递率。 3 、将网络编码应用于a dh o e 网络的信息传输过程中，提出基于网络编码的能量高 效多路径信息传输算法，降低传输单位比特信息所消耗的能量并均衡网络负载 关键词：网络编码；广播；能量高效；多路径 大连理工大学硕士学位论文 r e s e a r c ho nw i f e l e s sn e t w o r kc o d i n g a b s t r a c t 1 1 l ec o n c e p to fn e t w o r kc o d i n gw b sp u tf o r w a r db ya h l s w e d ee ta 1 i n2 0 0 0 i n t 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 gm e t h o dc a l l e dm u t i n gt h ei n t e r m e d i a t en o d e si nt h e n e t w o r kj u s tr e s p o n df o rc o p y i n ga n df o r w a r d i n gt h ei n f o r m a t i o n t h r o u g hp e r m i t t i n gt h e i n t e r m e d i a t en o d e sc o d et h ei n p u ti n f o r m a t i o nf l o wb e f o r ef o r w a r d i n g , n e t w o r kc o d i n g 啪 r e a l i z et h eh i g h - p o i n to fn e t w o r km u l t i c a s tc a p a c i t y s t u d ys h o w sn e t w o r kc o d i n gc a l ln o t o n l yi n c r e a s et h en e t w o r kc a p a c i t y , b u ta l s oh a v e 缸i m p o r t a n ta p p l i c a t i o np r o s p e c ti nt h e f i e l do fd a t ac o m p r e s s i o i i ，l o a db a l a n c e , r e d u c t i o no fe n e r g yc o n s u m p t i o na n dp r o p a g a t i o n d e l a y ，e n h a n c e m e n to f n e t w o r kr o b u s t n e s s ，i n f o r m a t i o ns e c u r i t ya n d e ta 1 1 1 1 es t u d y i n gf i e l do fn e t w o r kc o d i n gi n c l u d e sn o to n l yw i r e dn e t w o r ks u c ha si n t c c n e t b u ta l s ow i r e l e s sn e t w o r ks u c ha sa dh o en e t w o r k , w i r e l e s ss e l g q o rn e t w o r ka n dw i r e l e s sm e s s n e t w o r k 皿ea u t h o rm a i n l ym a k e sr e s e a r c h e s0 1 3t h ea p p l i c a t i o no f n e t w o r kc o d i n gi na dh o e n e t w o r k s i na dh o en e t w o r k s ，t h ep a t hb e t w e e nt h es o l l r c en o d ea n dt h ed e s t i n a t i o nn o d ei su s u a l l y e s t a b l i s h e dt h r o u g t ht h ec o u r s eo fr o u t ed i s c o v e r yb e f o r e 廿a u s m i s f i o m1 1 1 ef l o o d i n g b r o a d c a s ta l g o r i t h mi st h eu s u a lm e t h o dt or e a l i z et h ec o l l r eb e c a u s eo fi t ss i m p l ep r o p e r t y t h et r a n s m i s s i o no fi n f o r m a t i o ni sr e a l i z e db ys i n g l ep a t hb e t w e e l lt h e $ o u r o gn o d ea n dt h e d e s t i n a t i o nn o d ea n dt h i sm a n n e ri ss i m p l ea n de a s i l ym a i n t a i n e d b u th e a v yn e t w o r kl o a d w i l lr e s n l ti nf a s te n e r g yc o n s u m p t i o na n di n v a l i d a t i o no ft h en o d ea n de v e nt h ep a r t i t i o no f t h en e t w o r kw h e ns e r i o u s t h ea l t h o rm a k e sau s eo fn e t w o r kc o d i n gd u n n gt h ea b o v et w o c o u r s e si na dh o en e t w o r k sa n db r i n g sf o r w a r da n dr e a l i z e sm o r ee f f i c i c e n ta l g o r i t h m s 1 1 ” m a i nw o r k sa r c 船f o l l o w s ： 1 n eb a s i cp r i n c i p l eo f n e t w o r kc o d i n gi sp r e s e n t e di nd e t a i la n dt h eu o f n e t w o r k c o d i n gi na dh o en e t w o r k si sa d d r e s s e d 2 ab r o a d c a s ta l g o r i t h mb a s e do i ln e t w o r kc o d i n gd u r i n gr o u t ed i s c o v e r yi nw i r e l e s s n e t w o r ki sr e a l i z e d ，w h i c hh a sas i g n i f i c a n tr e d u c t i o no ft h en u m b e ro fp a c k e t sd u r i n g b r o a d c a s t i n gi nt h en e t w o r ka n di m p r o v e st h eb r o a d c a s td e l i v e r yr a t i o 3 am u l t i p a t hi n f o r m a t i o nt r a n s m i s s i o na l g o r i t h mb a s e do i ln e t w o r kc o d i n gi s p r e s e n t e dd u r i n g i n f o r m a t i o n p r o p a g a t i o n , w h i c he f f e c t i v e l y d e c r e a s e st h e e n e r g y c o n s u m p t i o no f p e r b i ti n f o r m a t i o na n db a l 。a n c et h en e t w o r kl o a d k e yw o r d s ：n e t w o r kc o d i n g ；b r o a d c a s t ；e n e r g y - e f f i c i e n t ；m u l t i p a t h 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：至i j 垒主i ：日期：丝1 21 垒：鲨 火连理工人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 型垒塑： 曼堕墨 赳年尘月丛日 大连理工大学硕士学位论文 1绪论 1 1 论文的研究背景和意义 在目前的计算机通信网络或无线通信网络中，信息传输都是由源节点经过中间节 点，以存储转发的方式传送到目的节点的。除了数据复制以外，网络的中间节点并不需 要作做任何其它的数据处理。在许多实际应用中，人们为了信息分析、信息安全以及交 换的目的，总是要在中间节点进行某种形式的数据处理。人们普遍认为，中间节点所进 行的数据处理对数据传输过程本身并不会带来任何好处。 编码最初是在物理层，主要是为了减少信息的冗余或者使编码后的信号更适合在信 道中传输，而在高层是否能带来好处一直以来是有争议的。网络路由的传统操作是尽可 能寻找源与目的节点之间的最优路径，避免数据流的碰撞，但最近研究显示在多播环境 下与单一路由相比，如果允许中间节点处理信息可明显提高传输速率。网络编码的核心 思想就是允许并提倡网络中间节点对信息进行融合。路由本身则被视为一种特殊的编 码，即节点的输出是输入的一组数字排列。 网络编码的主要优势在于如果己知网络的拓扑结构及链路容量，就可以计算出源点 到多个目的节点的最大信息吞吐量，它可以使资源得到充分利用，并且能使网络资源利 用达到理论上限，这有赖于网络节点在转发信息前对接收数据进行编码。具备了网络编 码功能的节点从各个输入链路获得信息，并进行编码，然后把信息传送给所有输出链路。 研究表明，网络编码除了能够提高系统的容量外，在数据压缩、负载均衡、降低节点能 量消耗、减少传播时延、提高网络健壮性及信息安全等方面都有重要的应用前景。 网络编码对网络的管理和设计有着巨大影响，能够更好地挖掘出诸如网络互联和无 线带宽等共享资源，因此受到很多关注，吸引了众多研究者的兴趣，有人甚至预言，该 理论将颠覆所有现有网络的通信方式。从理论上讲，它也是一门非常具有吸引力的交叉 学科，该领域涉及信息论、算法、代数、编码理论以及图论。 网络编码最初是基于有线网络提出的，但随着研究的进展，人们发现网络编码在无 线网络中的应用有着更大的潜力。最近，不断有学者基于无线网络发表了很多学术论文， 其中，在a dh o c 网络中应用网络编码的研究居多。a dh o e 网络中一个关键的问题是路 由协议的设计问题，其中广播操作被广泛应用在a d h o c 网络路由发现过程中，如a o d v 和d s r 协议。由于盲目泛洪方式具有简单且可靠的覆盖率，因此a d h o c 网络的路由发 现过程通常通过该方式实现。但盲目泛洪在节点密集的网络中会造成大量重复的报文而 消耗大量的网络资源，因此还可能产生严重的广播信息冗余、信号竞争和信息碰撞，进 无线网络编码研究 而导致协议效率降低。因此，减少广播冗余是提高a dh o e 网络路由协议性能的重要手 段。在信息传输时，传统的路由方式一般是通过源节点和目的节点之间建立的单一路径 来实现，这种方式的好处是简单、易实现。但也存在着很多缺陷，如网络负载过重导致 路径上节点的能量消耗过快。鉴于网络编码在减少通信量以及平衡负载等改善网络性能 参数上的各种应用，如何寻找一种合适的网络编码在a dh o e 网络中的应用方式，以此 提高网络各方面的性能意义十分重大。 1 2 论文的主要工作 、 论文提出了基于网络编码的广播算法以及多路径信息传输算法。前者可应用到a d h o e 网络的路由发现过程中，主要是针对广播风暴问题，通过基于网络编码的多源间信 息交换，减少广播包的冗余量，提高广播投递率。后者主要应用到信息传输过程中，将 传统的单路径方式加以扩展，通过网络编码来实现能量高效的多路径信息传输算法，不 但减少了单位比特信息的能量消耗，而且均衡了网络负载。本文的主要工作如下： ( 1 ) 简要介绍网络编码的基本概念。 ( 2 ) 介绍几种常见网络编码构造方式。 ( 3 ) 提出了基于网络编码的减少广播冗余算法以及减少能量消耗的信息传输算法。 ( 4 ) 在不同场景下对改进的算法进行仿真，与原有算法进行比较 1 3 论文的内容与结构安排 全文的内容安排如下： 第二章：首先介绍了路由方式的局限性，然后引出了网络编码的概念。随后介绍了 网络编码的发展现状以及优势。 第三章：介绍了几种常见的网络编码构造方式，分析编码规则并给出评价。 第四章：首先介绍了网络编码在无线自组织网络中的应用。在分析传统网络路由发 现及信息传输不足的基础上，提出了基于网络编码的广播算法及能量高效多路经信息传 输算法。 第五章：对提出的算法与原有算法进行仿真比较并分析原因。 第六章：对整个论文的工作进行了总结，得出了基本结论。 大连理工大学硕士学位论文 2 网络编码概述 本章介绍在分析传统路由方式不足的基础上，引出网络编码的概念。随后介绍了网 络编码的研究现状以及网络编码相对于路由方式的优势。 2 1 组播通信方式 2 2 1 组播技术的概念 传统的通信方式主要有两种：第一种单播( u n i c a s t ) ，指一个源节点和一个目的节点 之间进行通信；第二种广播( b r o a d c a s t ) ，指一个源节点和网络中所有其他的节点之间进 行通信。如果要将信息发送给网络中的多个节点而非所有节点，可以采用上述两种方式。 采用单播方式实现时，源节点向各个用户发送相同的信息，信息的重复数量与用户数量 相等，浪费了大量的带宽，也增加了服务器的负载。采用广播方式实现时，不仅会将信 息发送给不需要的主机而浪费带宽，也可能由于路由回环引起严重的广播风暴。所以， 传统的单播和广播通信方式都不能有效的解决单点发送多点接收的问题。 组播( m u l f i c a s t ) ，也称多播，是支持多方通信的高效通信方式，发送节点只向网络发 送数据的一份实例，经由网络节点复制并发送到多个接收节点。组播在传输多方通信数 据时，不仅减轻了发送源的处理负荷，也降低了网络带宽的使用，尤其实在通信带宽及 其受限的移动自组织网络中，采用组播机制对实现多方通信是非常有必要的。 2 2 2 组播技术的路由实现 考虑一个通信网络【”，它是由一些节点和边组成的集合，我们用有向图g = ( 矿，e ，c ) 来表示，卿e 分别是节点和边的集合，非负数c ( p ) 用来表示边e 上允许传输信息的容量 上限。在这个通信网络中，要实现由一点s v 向多点t c v 组播信息，传统的路由方式 是通过在通信网络中建立一个或多个组播树g k = ( ，e k ，c 。) ，每个组播树都将信源和所 有的信宿连接起来，所要传输的信息就在这些事先选好的路径上传输。每个组播树可以 实现的传输速率取决于组成这个树的所有边中容量最小的边，也就是r a i n 。c 。( e ) 。为 了可以获得更高的组播速率，我们可以建立多个组播树g 。，k = l ，五，并且在不同的组 播树上传输不同的信息，只要每条边上传输的信息量满足艺罗q ( e ) s 以) 即可。 2 2 3 组播技术实现的局限性 上面己经提到，组播是靠在通信网络上建立组播树来实现的，下面我们就看看一个 组播树可以实现的最大传输容量。 由最小割最大流定理1 2 1 ，我们可以知道网络中两点之间的最大流量可以通过最小割 来衡量；同时，实现最大流的路径可以通过最大流算法找到。所以，当要建立两点之问 通信的时候，我们可以在两点之间，应用最大流算法，得到它们之间的最大传输速率 但是，当我们考虑一点向多点的组播路由树的建立时，问题就复杂起来一般认为，组 播树的建立是一个n p 问题【3 1 。一般采用的方法是先采用最大流算法找到信源与一个信宿 之间的最大流及其实现的路径：然后再依次寻找其他信宿与信源之间的路径。在寻找信 源与第二个信宿之间的路径时，往往就在原通信网络中去掉信源与第一个信宿之间已经 用过的链路的容量。这样处理是因为，传统路由认为网络中传输的信息是不能叠加的， 只能进行存储转发。我们可以看到，这样的组播树的建立方式会导致信源与第二个及其 后面所有信宿之间的路径都不是以它们之间的最大流进行传输的。这将最终使得组播可 以实现的传输容量远远小于最小割最大流确定的容量上限 2 2网络编码的提出和发展现状 正是针对组播技术的上述局限，网络编码应运而生，它可以用来实现由最小割最大 流定理给定的一个通信网络的容量上限。 2 2 1 网络编码的提出 2 0 0 0 年，香港中文大学的a h l s w e d e 等人【4 】发表了一篇题为“网络信息流”的文章， 提出了“网络编码”这一概念，该理论通过允许中间节点对在转发信息前对输入信息流 进行编码来实现网络多播容量的极限。 一个通信网络可以用有向图来表示，根据图论中的最大流最小割定理可知，一个网 络可以传输的最大流量等于其最小割。但传统的存储转发式路由方式，并不能实现网络 的最大流传输，所以它并不是最佳的。a h l s w e d e 等人指出，没有必要对路由节点的功能 加以限制，即允许对其接收到的信息先进行编码后再传输出去。在接收端，目的节点通 过一定的译码算法译出所需的信息，则可以大大提高网络的传输速率，充分利用网络中 的链路资源，从而实现最大流最小割定理给定的信息传输速率的上限。 我们通过一个简单的例子对网络编码的基本思想进行解释，参考图2 1 所示的通信 网络。 - - 4 大连理工大学硕士学位论文 (a)(b) 图2 1 源节点s 多搐信息到接收节点t ，t ： f i g 2 1 s o u r c en o d esm u l t i c a s t st o “x 商、，ht l , t 2 图2 1 ( a ) 给出了一个组播网络，不考虑时延和传输差错。其中s 是源节点，t i 和t 2 是目的节点，每条边的信息速率均为1 比特每单位时间。假如网络中的节点只对其收到 的信息进行复制转发，则此网络多播速率无法达到2 比特每单位时间。因为接收节点3 在一个单位时间内只能转发从节点1 和2 过来的两个比特中的一个，如果3 转发从l 节 点过来的信息，则接收节点t l 可以收到2 比特每单位时间，但是接收节点t 2 只能收到1 比特每单位时间。假设从源发向节点1 的信息比特为b i ，从源发向节点2 的信息比特为 b 2 。2 1 ( b ) 图中的3 节点将分别从节点l 和2 过来的信息b i 和b 2 进行模2 加，然后发向 节点4 ，于是接收节点t l 在一个单位时间内收到了b i 和b l + 惋，于是可以通过b l “b l + b 2 户 b 2 运算来得到b 2 ，也就是说，接收节点t l 在一个单位时间内相当于收到了b l 和b 2 。同 理我们可以知道接收节点t 2 在一个单位时间内也相当于收到了b i 和b 2 。于是2 1 ( b ) 图 的传送方法达到了多播速率2 比特每单位时问。 2 2 2 网络编码的发展现状 网络编码技术的提出只有7 年的时间。a h l s w e d e 等人首先提出网络编码这个概念。 他们的工作主要针对单个源点，多个接收点的信息传输问题，证明了在源点发送能力无 限的情况下，一个网络的最大信息传送率等于该网络的最小割的容量也就是网络的最大 流。将信息传输与图论的最大流最小割问题联系在一起。这也是第一次提出通信网络的 容量问题。 a h l s w e d e 等人仅给出了网络最大信息传送速率的存在性证明，并没有给出具体的网 络编码实现方式。l i ，y e u n g 和c 甜5 】提出单一源，多接收点网络的最大传输速率可以通 过线性编码实现。通过一个广泛适用的线性编码多播算法( l c m ) ，每个接收节点都可以 无线网络编码研究 达到其最大流。l c m 主要应用于非循环网络。l c m 规则为每条边分配边向量，每个节 点分配向量空间。边向量与点向量空间按照l c m 规则满足一定的关系通过边向量和 节点上的信息向量相乘对信息编码，在接收节点处使用逆矩阵解码。l c m 方法可以达到 任意节点的最大流。但由于l c m 规则过于严格，寻找符合规则的向量需要大量的时间， 造成了网络的延时，因此l c m 不适合用在实际网络中。 k o c t t e r 等人【6 】为网络解码设计了一个数学框架。它将一般的网络编码寻找线性解的 方法简化成为寻找多元多项式的非零解。同时寻找编码系数的方法也通过代数编码方式 而简化了。 针对多播信息传输问题，h o 等人1 7 l 设计了一种不需要知道网络节点分布情况的随机 运算法则，通过在字母表中随机选取系数实现网络编码。他同时证明了在该法则下，网 络中所有接收点收到全部信息的可能性至少为( 1 d q ) 其中d 是接收节点的个数。边上 传递的信息来自所有源节点，同时将信息传到任何一个接收节点去。满足这样要求的边 的最大数量是v 。q 是系数选择的范围就是字母表的大小。同时，由于随机编码在各条 链路上以等概传播信息，因此可以最大程度上保证传输的成功。 p s a n d e r s 8 l 等人提出了一种实现网络编码的多项式时间算法。这种方法将网络编码 的构造进一步简化，它也是在己知拓扑的情况下，首先通过最小割最大流算法找到完成 组播所需的路径的集合，在找出的这个子图上，再自上而下的确定各个节点所需要进行 的操作。这种方法不但把网络编码构造的复杂度从指数级降到了多项式级，而且大大降 低了网络编码中所采用的字母表的下限。 另外，人们对网络编码在提高网络性能方面的应用做了大量的研究。研究表明，网 络编码除了能够提高系统的容量外，在数据压缩1 9 1 、负载均甜1 0 1 、降低节点能量消耗( 1 l 】、 减少传播时延、提高网络健壮性【1 2 1 及信息安型”】等方面都有重要的应用前景，后面我们 对其中的几个方面进行了简要的介绍。 2 3 网络编码的好处 a h l s w c d e 等在提出网络编码时指出，通过网络编码可以提高网络多播的容量，达到 网络多播的最大流限，这是网络多播的理论上限。通过对网络编码的研究，人们发现网 络编码多播较传统的路由多播的好处不仅仅局限在网络多播的容量方面。下面我们将具 体讨论网络编码多播的好处。 6 一 大连理工大学硕士学位论文 2 3 1网络多播容量的改善 网络编码最主要的应用就是提高多播系统的信息传输速率，即达到网络拓扑图的最 大流，而传统的路由方式则无法实现。对于一个单源多播网络，最大的信息传输速率为 c = r a i n 。c ( s ，t ) ，其中t 是多播接收节点集合，该值是多播传输速率的理论上限值， 称之为多播容量，网络编码可以达到该多播容量。 在图2 1 中，我们通过一个典型的网络拓扑指出，只有采用网络编码才能获得网络 多播的最大流限，而无法通过传统的路由多播获得。但是这并不能完全刻画基于网络编 码的多播与传统的口多播在多播容量性能上的差异，因为网络编码的容量依赖于网络 节点的连接情况以及网络中每一条链路的容量的变化情况。因此在评价网络编码多播的 容量时，我们必须考虑多种网络拓扑结构以及链路的容量。 a v e r a l l ed 啊 图2 2 网络编码多播和多会话i p 多播的容量比较 f i g 2 2 t h ec o m p a r i s i o no f n e t w o r kc o d i n ga n dm u l t i - e e u d o ni pm u l t i c a s t 文献【1 0 】对一编码多播和口多播的多播容量性能进行了比较。其随机生成节点数为 5 0 的网络拓扑结构，并随机选取1 0 个接收节点。对于网络链路的容量，采用两种模型： 一种是链路的容量在 1 ，1 0 i 叉间内随机的选取的非均有模型( h e t e r o g e n e o u s m o d e l ) ，另一 种是链路容量为常数5 的均匀模型( h o m o g e n e o u sm o d e l ) 。因为多会话口多播更能有效 的利用网络的资源，所以将网络编码多播和多会话口多播的多播容量进行了比较图 2 2 是多播容量与节点度数关系的仿真结果。 旨召薯8| 无线网络编码研究 从图中我们可以看到，在均匀和非均匀的两种链路容量模型下，基于网络编码的多 播通常较多会话i p 多播获得更高的多播容量。此外，网络编码多播和多会话i p 多播的 容量差异随着网络节点的平均度数的增加而增加。 2 3 2 负载均衡 现有的口多播路由经常造成网络流量的不均衡分布，因此在多播通信中，链路流 量的负载平衡一直是人们关注的问题。现有的多播路由协议主要可分为基于核心的路由 协议和基于信源的多播路由协议。基于核心的路由协议经常造成流量过分集中于某一节 点。而基于信源的多播路由协议也会由于多个多播树的叠加，造成某一链路流量的过载， 影响网络的服务质量。基于网络编码的多播【1 0 1 利用多条路径进行信息数据的传输，可以 平衡网络链路的负载。 ( b )( c ) 图2 3 路由方式与网络编码方式的网络负载比较 f i g 2 3 l o a dc o m p a r i s i o no f l pa n dn e t w o r kc o d i n gb a s e dm u l t i c a s t 如图2 3 所示的链路容量为2 的网络，源节点s 将信息多播到接收节点r l ，r 2 ，聃。 假设网络编码多播使用一半的链路容量，在这种情形下，路由方式与网络编码方式多播 速率均为2 比特每单位时间。但采用路由方式( 如( b ) 所示) 时，2 比特的信息是通过5 条链路来传输的，另外5 条链路空闲。当使用网络编码方式( 如( c ) 所示) 时，1 比特的信 息是通过9 条链路来传输的。因此，通过网络编码，负载被分配到了整个网络中。另一 方面，在路由方式中，共有1 0 比特的信息量需要传输，而使用网络编码时，仅需要传 输9 比特，这就意味着网络编码可以节省1 0 的带宽。当网络编码多播使用链路的全部 容量时，不但可以获得4 比特每单位时间的多播速率，而且此时的链路资源的利用率达 到了最佳。 一8 一 大连理工大学硕士学位论文 2 3 3 减少节点能量消耗 在一些a dh o c 网络中尤其是无线传感器网络中，节点是通过有限的电池来提供能 量的，因此有效能量利用成为衡量一个无线能量受限网络性能的重要指标。 t l e q 。 ，t 2 d asb ( a )( b ) 图2 4 通过网络编码节省节点的能量消耗 f i g 2 4e n e r g ys a v i n gt h r o u g hn e t w o r kc o d i n g 图2 4 ( a ) 是一个由8 个节点组成的无线网络，信源节点s 多播信息到接收节点t i 和 t 2 ，节点传输范围有限且仅能与周围的两个节点直接通信。假设一次物理层的传输要消 耗1 个单位的能量，则传统的路由方式多播单位比特信息需要消耗的总能量为5 。图2 4 ( b ) 基于网络编码实现了信息的多播传输，信源节点将两比特信息x i 和x 2 分别传输到接收 节点t l 和t 2 ，节点t j 和t 2 再将其传输到中间节点e ，节点e 对x l 和x 2 做模2 运算后，再 将其广播到节点t l 和t 2 ，这样两个接收节点就可以同时恢复出信源的信息比特x 1 和x 2 。 在采用网络编码的多播过程中，我们总共用到了9 次物理层广播，所以每比特消耗的能 量为4 5 。因此采用基于网络编码方式的多播，可以有效地降低无线网络信息传输过程 中的能量消耗。 另外，无线多播网络中，通过跨层的设计【1 4 】可以将网络编码与物理层无线广播传输 特性相结合，实现网络的最小能量多播，最大限度的延长网络的生存期。 2 3 4 减小信息传播时延 考虑具有链路时延的网络，相对于路由方式，通过网络编码进行多播传输时可以获 得较小的传播时延。 无线网络编码研究 | | ， 4 0 - 1 ? 。 r 2 ( a ) l b a + b - l 1 ) t 。 n 。沁。q 磊 r 2 ( b ) 图2 5 路由和网络编码多播的路径时延比较 f i g 2 5d e l a yc x n p a r i s i o no f r o u t e a n dn e t w o r kc o d i n gb a s e dm u l f i c a s t 对于图2 5 所示的单信源三个接收节点的多播网络。设每条链路具有单位时间的传 播时延，节点的处理时延相对于链路的传播时延可以忽略不计。我们可以发现基于传统 路由方式( 如( a ) 所示) 多播，信息从信源发送到接收节点的最大时延为3 ，而对于基于网 络编码( 如( b ) 所示) 的多播来说，最大的传输时延是2 。因此对于特定的多播网络来说， 通过网络编码可以减小信息传输的路径时延。 另外，还可以通过网络编码对相关信源的数据进行压缩1 1 7 】，减少网络中传输的信息 量，从而减少节点能量消耗，延长网络的生存周期。通过网络编码可以抵抗网络中的链 路和节点的非各态历经失败【6 i t 坫】对网络链接的影响，提高网络链接的鲁棒性，减少网络 管理的开销。网络编码在信息安全领域的应用产生了一种基于数据包的随机网络编码检 测策略，对原数据进行的简单多项式函数哈希变换，然后把得到的结果添加到原始数据 包中。接收节点通过比较解码后的数据和哈希值就可以判断数据包是否被修改过，这样 就可以防止中间人攻击，提高数据的安全系数。 大连理工大学硕士学位论文 3 几种常见的网络编码构造方式 本章介绍了几种常见的网络编码构造方式，这也是我们后面算法的基础。 3 1 网络编码的前提假设 “等人【5 提出，通用的网络编码方法可以通过简单的线性运算实现，即节点的输出 信息流为输入信息流的线性组合，因此这种方法称为线性网络编码。后面介绍的几种形 式的网络编码都是基于这一简单思想，只是编码的构造过程不同。为了简化计算我们作 以下假设： ( 1 ) 网络是非循环网络 ( 2 ) 容量为n 的路径可以看作是n 条单位容量路径的并联。 ( 3 ) 每条边传输信号的时延相同。 “) 网络中不存在传输错误，只存在由于节点和链路的无效造成的信息丢失。 ( 5 ) 多个源节点的网络可以看成只有一个虚拟源节点的网络。 假设解释：( 1 ) 为了简化问题的表示与描述，假定网络中没有环路存在，这也是无 时延网络的前提。( 2 ) 通过选择一个非常小的单位容量，使每两个节点中间都有整数条 路径连接。这样在下面讨论两个节点之间的容量的时候就可以用两个节点之间单位路径 的多少来衡量，单位路径在单位时间内传输单位信息。( 3 ) 假设的理想情况，取消了网 络同步的要求。在后面我们会讨论更实用的网络编码。( 4 ) 我们考虑的是网络编码在网 络层的操作，差错控制可以通过底层来完成，而提供给网络层的是一个没有差错的系统。 在后面我们会讨论网络编码对于某些错误类型的鲁棒性和对随机错误的抗干扰能力。( 5 ) 虚拟源的设置参见图3 1 。 图3 1 虚拟源节点 f i g 3 11 ) u l 口ys o u r c en o d e 无线网络编码研究 网络可以通过一个虚拟源和一些虚拟链接，使虚拟源节点含有所有信息，而将所有 实际源节点都转化成网络的中间节点。整个网络就从多个源节点多个接收节点网络转化 成单源节点、多接收节点的网络。虚拟的方法是，将网络中实际的源看作是这个虚拟源 点连接的第一层接收节点。如果实际源节每次有n 个信息要传送给其他节点，那么在虚 拟源与这个实际源节点之间的链接上，信息以n 个单位信息每单位时问速率传送。相当 于所有信息都是从虚拟源通过实际源传送给接收节点。 3 2 线性向量编码 3 2 1线性向量编码的提出 l i 等人f 5 】给出了一个通用的线性编码的方法，称为线性编码多播l c m ( l i n e a f - c , o d e m u l t i c a s t ) 。 假设源节点s 发出的所有信息都是d 维( d 是整个网络所有接收点最大流的最小值) 的行向量，称为信息向量。源节点一次传送d 个不同的信息，对应信息放在信息向量的 对应位置上。每个信息都标号，无论信息中间经过怎样的变化在信息向量中的位置不变。 中间节点将所有接到的信息按照标号放在对应位置上，形成中间节点的信息向量。 3 2 2 编码规则 节点根据l c m 的规则为每一条边分配一个边向量，也称为局部编码向量。边上传 递的信息是节点的信息向量与局部编码向量作向量乘法之后得到的数值。 每一个信息都携带一条全局编码向量。这条全局编码向量记载了某个信息在网络中 经过不同的边所经历的编码的过程。中间节点发送信息的时候，首先将所有接到信息的 全局编码向量合成一个d * d 的矩阵。信息i 的全局编码是矩阵中的第i 列。该矩阵与边 上的边向量根据编码规则作向量乘法，得到的d 维列向量就是输出信息的全局编码向量。 在解码信息的时候，将所有接到的信息的全局编码组合成一个完整的矩阵f 。因为 x f = z 所以只要解出f 的逆矩阵f 1 就可以解码出原始信息。 x = zf 1( 3 1 ) 为了方便起见，源节点的第i 条边向量可以简化成v 产【o ，1 ，o 】只在第f 个位置 上向量的值不为0 。这样源节点首次传输的信息实际是不同的单信息而不是信息混合后 的结果。 下面是数学意义上的l c m 选择边上向量的规则。 大连理工大学硕士学位论文 定义3 1 一个通用的多播网络的线性编码( l c m ) 方法是，对于传输网络g ；( k 毋， v 是所有节点的集合，e 是所有边的集合。给每一个节点v 分配一个线性空间矿( ，每一 条边( ，v j ) 分配一条向量h i j ) 。源节点的向量它们之间的关系是： ( 1 ) r ( s ) f n ( 2 ) 矿o ，) 矿( f ) 只要矿o ，) e ( 3 ) 对任何非源节点的集合甲，满足 ( 杪o ) ：v 甲 ) = ( v o ，) ：f 、 ，) ，- ，叠甲) ( 3 2 ) “) 节点输出边的向量是节点输入边向量的线性组合 其中 是线性张成的意思。q 是一个d 维的向量空间，d 是网络的最大流。( 1 ) 的 意思是源节点的向量空间是d 维的，就是说源节点可以同时发出d 个线性无关的信息。 ( 2 ) 的意思是对于某一个节点发出的所有边，边上的向量都属于该点的向量空间。( 3 ) 的 意思是某个非源节点的的向量空间可以由其发出的边的向量线形张成。也就是说，如果 某些边是从某个非源节点发出的，那么这些向量的线性运算可以张成整个节点的线性空 间。想实现这个要求就需要所有边上的向量都是d 维的线性无关的向量。( 4 ) 由于有这 一条限制，所以输出的信息包含全部的输入信息。输出信息是输入信息的线性组合，也 就是所有输入信息的综合信息。虽然信息的大小没有变化，但是包含的信息量有了增加。 在不增加传送的次数的前提下增加了单个信息的接受范围，由于一个信息可以被多个接 收节点接收，相当于不同接收节点共用了信道。 3 2 3 编码评价 满足以上方法的网络编码可以在网络无错传输的情况下，在接收节点处正确地解码 出所有的信息，同时使任何一个网络中的节点达到该节点的最大流。线性向量编码可以 充分利用网络资源，使每一个传输的信息都被多个接收节点接收。但是要想达到所有边 向量线性无关的限制，在选择向量的时候必须将生成的向量与所有已知向量比较，确定 任意n ( n g ) 维的向量之间都是线性无关的。当网络的容量很大的时候，由于任意n 维向 量所组成集合的数量随网络的边数成指数增长，验证的工作量是很大的，因此将线性向 量编码应用到大型网络中是不现实的。后来h o 和m e d a r d 【7 】等人提出了一种随机网络编 码的思想。在不验证向量是否相关的情况下，给出了字母表的大小和向量相关性之间的 关系，将向量网络编码应用在实际网络，并验证了网络编码理论上的优越性。 无线网络编码研究 3 3 线性代数编码 3 3 i网络传输的代数表示 k o e t t e r 等人【6 】对网络编码和整个网络的传输情况给出了一个代数形式上的定义，如 下： 节点矿本身产生的信息是离散随机过程，用域p = 阶，1 ) ，j 和，2 ) ，j 和，3 ) 脚，开) 表示。连接的速率用r g ) = 。( 。k ，尸( x ( v ，f ) ) 表示。其中( v ，o ) 是随机过程的 熵。同一个节点的随机过程相互独立，其熵速率为常量且为整数。不同节点的随机过程 相互独立。接收点v 接到的信息用z ( 伊 z 1 ) ，z ( v ，2 ) ，z ( h 3 ) z ( v ，i n ) ) 表示。 3 3 2 编码的代数形式 对于中间某一条路径e 上传输的信息用y ( 力表示。 雌) = 芝口抽j d ，f ) + 乃，以) ( 3 3 ) i - 1 f ： 目d p p m h “) 其中系数口，成。都是域中的元素。h e a d ( e ) 意思是e 为边的起始点。t a i l ( e ) 意思是e 是边的结束点。 上面公式的意思是某条边上传送的信息是边的起始节点产生的全部信息乘以系数 口，。的加和，加上起始节点接到的所有传入信息乘以系数声的加和。换句话说节点传 输的信息是所有节点自身产生信息和节点接收到的信息的综合。将网络编码规则应用于 网络，则源节点的输出信息公式是： r ( e ) - - e ，。j g ，) 1 3 l ( 3 4 ) 接收节点的输入的信息公式是： z 蚺。毒o ，球一 ( 3 5 ) e ：k 耐k 卜柑【c lr 1 、 中间节点的输出信息公式是： y 哆毒二色，唯) ( 3 6 ) 大连理工大学硕士学位论文 因为假设源节点没有信息输入，只有自身产生的信息，所以没有后面一项：中间节 点没有本身产生的信息所以没有前一项，接收节点只有信息输入没有输出所以也只有后 一项。 通过这样的转化，就把网络编码问题转化成在域只的多项式的环中找到上面的系 数的问题。只要每一个接收节点，都能够解码出原始信息，编码就成功。系数嘶乃。， 鬈。称作网络的局部编码系数。 3 3 3 编码规则 为了方便解码，这里我们引入转移矩阵的概念。转移矩阵m 是用来描述网络输入 输出之间的关系的。假设网络源点s 的输出信息向量是j ，一瞰s ，1 ) ，郧2 ) 琊，3 ) 翟s ，”) ) ， 在接收节点r 接收到的输入信