（通信与信息系统专业论文）网络编码原理及其纠错性分析.pdf

摘要 网络编码是2 0 0 0 年由r u d o l fa h l s w e d e 等人首次提出来。其主要优点之一就是 使多播传输速率能达到上限值，即多播容量。而使用目前的多播传输方法，多播 传输速率往往是达不到这个上限值。另外，网络编码也在资源消耗、负载均衡、 网络管理等方面带来了好处。目前大多数的研究对象是多播网络，本文也是针对 多播网络进行分析研究，而网络编码在非多播网络中的应用有待于更多的研究。 要对一个任意给定的多播网络进行网络编码，目前已有的方法有两种：第一 种是由蹦fk o e r e r 等人提出的基于代数结构的网络编码方法，这种方法是一种指 数时间算法。另一种重要的网络编码方法是由p e t e rs a n d s 等人提出了一种多项式 时间算法的网络编码方法，这种方法相对第一种方法而言不仅算法复杂度简化了， 而且有一个很大的优点，就是在进行从源节点到各个终端节点进行传输信息之前， 先选好从源节点到各个终端节点的传输路径，因此在同样的信息传输速率下减小 了对网络资源的占用，同时使网络编码变得更简单。 针对特殊的多播网络可能具有更为快速有效的网络编码方法。本文对两类特 殊的多播网络进行分析，给出了它们的有效网络编码方法。 另外基于网络编码的多播网络可以具备纠错性能。即如果在网络中有几条边 传输的符号出错，且错误边数不超出纠错能力范围，则所有接收节点都能正确的 译出源信息。 本文所作的工作主要有以下几个方面： 1 介绍网络编码的原理；详细介绍目前已有的两种针对所有多播网络的 网络编码方法：简单介绍针对非多播网络的网络编码方法。 2 分析了两类特殊多播网络，分别给出了它们的快速网络编码方法。 3 以传统纠错码为基础，介绍什么是基于网络编码的纠错码；对基于网 络编码的纠错码进行分析研究，给出了信息符号空间大小的上下界： 分析了构造该纠错码校验矩阵的复杂度，并给出了些降低复杂度的 简单方法。 关键词：网络编码最大流多播传输唯一化图m d s 码差错控制 a b s t r a c t n e t w o r kc o d i n gi sf i r s ti n t r o d u c e db yr u d o l fa h l s w e d e e ta 1 o n e i m p o r t a n t a d v a n t a g eo f n e t w o r kc o d i n gb a s e dm u l t i c a s ti st h a tt h eu p p e rb o u n do f am u l t i c a s t ，i e - m u l t i c a s tc a p a c i t yc a r lb ea c h i e v e d b u tu s i n gp r e s e n tm u l t i c a s tm e t h o d s ，m u h i c a s tc a n n o t ，o f t e n ，a c h i e v et h i su p p e rb o u n d i na d d i t i o n ，n e t w o r kc o d i n gb r i n go t h e rb e n e f i t s ， i n c l u d i n gr e s o u r c e sc o n s u m p t i o n ，l o a db a l a n c i n g ，n e t w o r km a n a g ea n ds oo n s of a r , m a i nr e s e a r c h e sa r et a k e no nm u l t i c a s tn e t w o r k sa n dm a i nw o r ko ft h i s p a p e r i s c o n c e n t r a t e do nm u l t i c a s t g i v e na l la r b i t r a r ym u i t i c a s t ，t h e r ea r et w om e t h o d sf o rn e t w o r kc o d i n gp r e s e n t l y t h e f i r s to d eb a s e do na l g e b r a i cs t r u c t u r ei sb r o u g h tf o r w a r db yr a l fk o e t t e re ta la n di ti s a ne x p o n e n t i a lt i m e a l g o r i t h m t h es e c o n d o n ei si n t r o d u c e db yp e t e rs a n d e r se ta 1 a n d i ti sa p o l y n o m i a lt i m ea l g o r i t h m t h i sm e t h o dc o m p a r e d t ot h ef i r s to n en o to n l yh a s l o wc o m p l e x i t y , b u th a sa n o t h e rb i ga d v a n t a g e b e f o r et r a n s m i t t i n gi n f o r m a t i o nf r o m s o u r c en o d et oa l lr e c e i v e rn o d e s ，t h ep a t h sf r o ms o u r c et oe a c hr e c e i v e rh a v eb e e n d e t e r m i n e d s or e s o u r c e sc o n s u m p t i o ni sl o w e ra n dn e t w o r k c o d i n g i se a s i e rt op e r f o r m f o rs p e c i a lk i n do fm u l t i c a s tn e t w o r kt h e r em a yb em o r ee f f e c t i v em e t h o d i nt h i s p a p e r , f o rt w ok i n d so fm u l t i c a s tn e t w o r k s ，e f f e c t i v em e t h o d so f n e t w o r kc o d i n ga r e g i v e nr e s p e c t i v e l y i na d d i t i o nn e t w o r k c o d i n gb a s e dm u l t i c a s t c a l lp o s s e s st h ea b i l i t yo fe r r o rc o r r e c t i o n i ft h e r ea r es e v e r a ll i n k s ，s y m b o l so u to fw h i c ha r ed i f f e r e n tf r o mi n p u ts y m b o l s ，a n d t h en u m b e ri sn o te x c e e dt h ea b i l i t yo fe r r o rc o r r e c t i o n ，t h e na l lr e c e i v e r sc a nr e c o v e r s o u r c ei n f o r m a t i o n c o r r e c t l y t h em a i nr e s u l t so f t h i sp a p e ra r es h o w e da sf o l l o w s ： 1 t h ep r i n c i p l eo fn e t w o r kc o d i n gi si n t r o d u c e d ；t w ok i n d so fn e t w o r kc o d i n g m e t h o d sw h i c ha r ea p p l i c a b l et oa n ym u l t i c a s t sa r ei n t r o d u c e di nd e t a i l ；n e t w o r k c o d i n g m e t h o d sf o rn o n m u l t i c a s tn e t w o r k sa r e d e p i c t e db r i e f l y 2 t w ok i n d so f s p e c i a lm u l t i c a s tn e t w o r k sa r ea n a l y z e da n dg i v e nq u i c kn e t w o r k c o d i n gm e t h o d s 3 b a s e do nc l a s s i c a le r r o r - c o r r e c t i n gc o d e s ，w h a ti se r r o r - c o r r e c t i n gc o d e sb a s e do n n e t w o r kc o d i n gi si n t r o d u c e d ；u p p e rb o u n da n dl o w e rb o u n do nt h es i z eo fs o u r c e a l p h a b e ta r eg i v e na f t e re r r o r - c o r r e c t i n gc o d e sb a s e do nn e t w o r kc o d i n gi sf u n l l e r a n a l y z e d ；t h ec o m p l e x i t y o fc o n s t r u c t i n gp a r i t y - c h e c km a t r i xi s a n a l y z e d a n d s o m e t e c h n o l o g i e su s e d t od e c r e a s e c o m p u t a t i o n a lc o m p l e x i t ya r eg i v e n k e y w o r d s ：n e t w o r kc o d i n g m a x - f l o wm n l t i e a s tt r a n s m i s s i o n u n i q u e g r a p h m d sc o d ee r r o rc o r r e c t i o n 创新性声明 y 6 9 5 2 7 s 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：】丝盥魈日期兰! 堕! ! ! 兰! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍是西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公开论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 日期兰! 堕：皇9 日期q 、f 聊 第一章绪论 第一章绪论 本章首先简单介绍图论中的一些基本概念和网络编码的概念及网络编码目前 的发展状况，接着简单介绍网络编码带来的好处。最后总结了作者在攻读硕士学 位期间的研究工作，及给出了全文的内容安排。 1 1 图的基本概念 定义1 1 ：一个有向图g 是由一个非空有限集合矿( g ) 和矿( g ) 中某些元素的有序对 集合e ( g ) 构成的二元组，记为有向图g = ( 矿( g ) ，e ( g ) ) 其中v ( g ) 称为图g 的节 点集，y ( g ) 中的每一个元素称为该图的一个节点；e ( g ) 称为图g 的链路集，e ( g ) 中的每一个元素( 即矿( g ) 中某两个元素的有序对) 称为该图的一条链路。在不引起 混淆的情况下，记号v ( g ) 和e ( g ) 中也可以省略g ，即分别记节点集、链路集为v 和e ，而记有向图g = ( 矿，日 如果对于图g = ( 矿，e ，和g = ( v ，d ，有矿y ，e 量e ，则称图g 是图g 的 子图( s u b g r a p h ) 。 有向链路用圆括号表示，即( v ，v ) e 。( v ，v ) 的头用v = h e a d ( e ) 来表示，尾用 - , 2 = t a i l 如) 来表示。如果v = t a i l ( 1 ) ，称链路，是节点v 的出链路：如果v = h e a d ( ) ， 称链路，是节点v 的入链路。 称源节点的输出链路为源链路，接收节点的输入链路为终端链路。定义r ，( v ) 为节点v v 的输入链路集合：f o ( v ) 为节点v v 的输出链路集合。用数学形式表 达即为r ，( v ) = 口e ：h e a d ( e ) = v 及r 。( v ) = 忙e ：t a i l ( e ) = v ) 。 有向图中的途径( w a l k ) 是该图的一些顶点，f 2 ，和链路q ，a 2 ，a r 。所组成 的子图，这些顶点和链路可以交错排列成点链路序列i i , q ，i 2 , a 。，q - ，其中 a k = ( t ，+ i ) 或 a k = ) ( v 七= l 2 ，r - i ) 。例 如图 1 1中的 e 呻d - - - ) c b 寸e 斗d 斗d 。如果该序列中的所有链路都指向同方向，即 a k = ( ，+ 1 ) ( v = l 2 ，p - 1 ) ，则称该途径为有向途径( d i r e c t e dw a l k ) ，例如图1 1 中的o _ b 斗d 专口呻b 斗e 。 有向图中的路( p a t h ) 是该图的不包含重复顶点的途径。例如图1 1 中的 口一b c - - - d 。有向图中的有向路( d i r e c t e dp a t h ) 是该图中不包含重复顶点的 有向途径，即不包含反向链路的路。例如图1 1 中的a - - b 斗d - - c 。 b 图1 1 网络图 强安电子科技大学硕士论文：网络编码原理及其纠错性分析 割( c u t ) 的定义如下：连通图g 的顶点集为v ，k 和k 为y 的两个子集，且 k u k ：v ，h n k = 妒，那么，一个端点在k 内而另外个端点在k 内的图g 中 的全部边的集合s 就叫图g 的一个割，用( k ，以) 表示。在这集合弼，匕) 中，把从巧到 k 的边的容量之和叫做这割韵容量，用c ( k ，k ) 表示。 流( f l o w ) 就是广义的运输的概念，它将我们需要输送的东西从一个地方运送 到另一个地方。在通信网络中流指的是信息的传输。如果在一个图g 中，一个从 信源s 到接收节点 的流，它的值大于等于任何其它从s 到的流的值，则称这个 流是从s 到f ，的最大流，记为m a x f l o w ( s ，) ，简记为f 。 下面给出著名的最大流最小割定t 里( m i n c u tm a x f l o wt h e o r e m ) ： 定理1 1 1 1 】：在一个网络中，节点v 往接收节点v 发送信息，可达传输速率小 于或等于所有v 与v 之间切割容量中的最小值。 f o r d f u l k e r s o n 标号法 1 】给出了一个证明，证明了流的最大值等于割容量的最 小值。该证明是构造性的，证明的过程就是寻找最大流的过程。 1 2 网络编码的概念 一个通信网络( n e t w o r k ) 包含许多有向通信链路。这些链路连接着发端、交 换器和收端。如果把发端、交换器和收端看成节点，则我们可以将通信网络用有 向图g = ( v ，e ) 表示，其中y 是发端、交换器和收端的集合，e 是有向通信链路的 集合。另外，每条链路( f ，) e 有一个对应的权值足，即链路容量。 如果一个网络包含有向环，即在g 中存在一个链路序列 ( v 0 ，v 。) ，( v 1 ，v 2 ) ，( ，) ，则称此网络是循环的( c y c l i c ) 。 如果不包含有向环，则 称此网络是非循环的。 传统的网络节点只是将收到的数据路由、转发，并不进行数据的数学运算。 在2 0 0 0 年r a h l s w e d e 2 等人提出了网络编码，其核心思想是在网络中的节点可采 用不加冗余的编码。此思想突破了一直以来数据传输的固定模式，从而为进一步 提高目前的网络传输速率奠定了基础。在论文【2 中，作者给出了一个多播网络的 例子，采用网络编码时传输速率比仅使用路由、转发对的来得大，并且达到了多 播网络的速率上限c = m t n c j ) ( c 从信源s 到接收节点的最小割最大流值) 。s - y r l i 3 等人随后表明采用线性的网络编码在有限大的域中能够达到速率上限 c 。 下面举个例子说明什么是网络编码。 图1 2 ( 来自 2 】) 中的( a ) 图给出了一个单源二接收多播传输网络图，网络中边 的上标的是链路的容量，即1 比特单位时间。实际网络中容量为k 比特单位时间 的链路可拆开成爱条容量为1 比特，单位时问的并行链路，因此为简单起见，本文 第一章绪论 图中的所有链路的容量都为1 比特单位时间。假如网络中的节点只对其收到的信 息进行复制转发，则此网络多播速率无法达到2 比特单位时间。因为接收节点3 在一个单位时间内只能转发从节点l 和2 过来的两个比特中的一个。如果3 转发 从1 节点过来的信息，则接收节点t 1 可以收到2 比特单位时间，但是接收节点t j 只能收到1 比特单位时间。 假设从源发向节点1 的信息比特为b j ，从源发向节点2 的信息比特为b 2 。( b ) 图中的3 节点将分别从节点1 和2 过来的信息b l 和b 2 进行模二加，然后发向节点 4 ，于是接收节点t l 在一个单位时间内收到了b l 和b l + b 2 ，于是可以通过b l + ( b l + b 2 户b 2 运算来得到b 2 ，也就是说，接收节点t 1 在一个单位时间内相当于收到了b l 和b 2 。同理我们可以知道接收节点t 2 在一个单位时间内也相当于收到了b 1 和b 2 。 于是( b ) 图的传送方法达到了多播速率2 比特单位时间。 图1 2 单源二接收网络图 定义1 2 ：象这种网络中的节点对信息比特流进行一定的操作，如模二加、与、 或等等，而不是仅仅对其进行复制转发，称之为网络编码。 从上面的这个简单例子可以看出图1 2 中的网络，如果采用网络编码，则可以 增加信息传输速率。对于接收节点个数大于等于2 的网络，最优多播传输方案一 般要用网络编码。当然并不是每个网络采用网络编码都可以增加传输速率的，假 如不采用网络编码就已经达到网络本身所能提供的最大速率，那么采用网络编码 也就不再增加速率了。本文不具体论述什么样的网络采用网络编码能增加速率。 如果网络中所有节点对其输入边上的信息符号进行的是线性操作，则称为线 性网络编码；否则称为非线性网络编码。 数是随机选取的，则称为随机网络编码： 为确定性网络编码。 如果网络节点对信息符号进行组合的系 如果是通过某个算法确定出来的，则称 本论文讨论的是多播传输的线性确定性网络编码。 要在一个给定的网络中进行多播传输，信源j 传输信息的速率h 必定有个上限 值，这个上限值就是从s 到t ，z = 1 ，三n l 个最大流中最小的那个值。在图】2 中 4西安电子科技火学硕士论文：网络编码原理及其纠错性分析 的网络，从信源j 到f ，的最大流值为2 ，从信源s 到f ，的最大流值为2 ，因此信源信 息速率最大值为2 ，因此图k 2 ( b ) 中的传输速率已经达到了网络本身所能提供的最 大传输速率2 0 1 3 网络编码发展概况 如何判断一个网络中的某传输要求是否可以用线性网络编码实现昵? 目前已 经有一些文献对该问题进行了探讨，文献 4 给出了线性向量运算的概念，指出任 何传输要求( 满足节点与节点间的传输速率小于等于两节点间的最小截) 都可以用 线性网络编码完成的猜想，后来别的文献中证明了该猜想错误。同时指出任何一 个网络可以转换为s t s d 系统( s t s ds y s t e m ) 。并给出一个编码定理，该编码定理 是从熵的角度去判定网络编码函数是否能实现给定的传输要求。文献 5 中重新提 出了非线性操作是否对信息传输有作用，认为有些网络不能用线性网络编码完成， 并举了一个例子进行说明，但r u l f k o t t e r 给出了该例子中网络图的线性编码方案。 文献 6 根据信源和接收节点间是多播、非多播来划分网络，分成无需网络编码、 多项式时间线性网络编码、n p 线性网络编码这三类，指出了存在一些仅用非线性 网络编码才能解决的网络。文献 7 中提出了在某个符号空间上有解时在更大的符 号空间上未必有解。文献 8 成功找出了一个不能用线性网络编码完成的例子。 文献 9 中给出：若多项式最大度为d v ，每变量最大度为d ，从纯数学角度求 出其等于0 的概率，并根据此结论推出任何一个随机编码成功概率的下界表达式。 然后将其应用于方格网络，得出了随机网络编码的成功概率的下界高于路由的成 功概率的上界。文献 1 0 介绍了把随机编码的结论一般化到有循环、有延迟、有 不可靠链路的网络中，从e d m o n d s 矩阵里得到有延迟的网络随机编码成功概率的下 界( 定理2 ) ，并证明随机编码成功的概率大于以概率d q 删除边时网络可行的概 率( 定理3 ) ，并给出了以概率p 删除边、有y 条边冗余时编码成功的概率( 定理4 ) 。 文献 1 1 初步讨论了网络编码的路由情况，介绍了如何进行重叠度较大的路 由选择及给出编码域大小的界。 在文献 3 中证明了有限大的域中采用线性网络编码能够达到速率c 的多播 传输。r k o e t t e r 和m m e d a r d 1 2 给出一种针对多播传输的指数时间算法，p s a n d e r s 等人【1 3 】和s j a g g i 等人【1 4 】针对多播网络同时提出了一种针对多播传输的 第一章绪论 多项式时间算法。 1 4 网络编码的好处 本文仅论述网络编码应用于多播传输时带来的好处。 对于一个单源多播网络，最大的信息传输速率为c = m i n 。巧，其中r 是多播 接收节点集合，该值是多播传输速率的理论上限值，称之为多播容量，以c 表示。 文献 2 】表明利用线性网络编码可以达到多播容量。 网络编码除了提高可达传输速率外，还在资源消耗、负载均衡、管理、网络健 壮性等方面带来了好处。t a k un o g u c h i 等人 1 5 1 提出了网络编码对整个网络负载起 了均衡的作用，可以作为流量工程的一种技术 1 6 1 ，并针对某个特定的简单拓扑分 析了网络编码在负载均衡性方面所起的作用。p a c h o u 等人 1 7 针对六个实际 i s p 网络拓扑图分别仿真了基于随机网络编码的多播吞吐量、帧延时等性能参数。 y w u 等人【1 8 】针对六个实际i s p 网络拓扑图分别仿真了基于单棵多播数、多棵最 大速率多播树和基于网络编码多播树的多播容量，得出结论是后二者多播容量基 本相同。 下面简单说明网络编码带来的一些好处。对于一个给定的网络，如果我们想在 一个源节点和多个终端节点之间进行最大速率的信息传输，那么这个最大速率值 和多播路由算法有关，并称该最大值为此算法的多播容量。基于网络编码的可达 信息速率能达到多播网络的理论上限值，因此是其容量值已经达到最大。目前多 播方法未必能达到这个上限值，图1 已经很好地说明了这一点。 为了有效地支持实时的大量数据传送的应用，好的多播路由算法应该考虑到资 源消耗( 即带宽消耗) 和负载均衡性。我们以图1 2 ( a ) 拓扑图为例加以说明。假设 多播信息传输速率为2 ，则目前最短路径多播树路由算法生成的路由如图1 3 ( a ) 所 示，而基于网络编码的路由如图1 3 ( b ) 所示。 ( a ) 最短路径路由 c o ) 基于网络编码的路由 图1 3 路由图 为了实现速率2 的多播传输，图1 3 ( a ) 中共有5 条边参与传输信息，每条比被占 西安电子科技大学硕士论文：网络编码原理及其纠错性分析 用的带宽为2 ，总共耗费的带宽为1 0 ；图1 3 ( b ) 中共有9 条边参与传输信息每条比 被占用的带宽为1 ，总共耗费的带宽为9 ，因此由于网络编码而节省了1 0 的带宽。 另外，图1 3 ( b ) 中的网络流量是均匀分布于整个网络的，而图1 3 ( a ) 中的网络流量 是集中在5 条边上，因此在网络编码在负载均衡性方面也起了作用。 此处仅以多播传输为例，极其简单地分析了网络编码在多播网络中所带来的 一些好处，但这不说明网络编码没有应用于非多播网络的前景，只是有待于进一 步的深入研究。 1 5 本文的主要研究工作和内容安排 作者对目前处于初期阶段的非循环网络( 本文后面分析的网络都是非循环网络) 的网络编码进行了一定深度的理论研究，并结合计算机程序仿真，取得了一些初 步成果。全文共分五章，其余章节安排如下： 第二章详细介绍两种适用于任何单源多播网络的网络编码方法；第三章针对 两类单源多播网络，给出了相应的有效网络编码方法；第四章介绍什么是基于网 络编码的差错控制，给出了在给定纠错能力的前提下、信源空间的上下界，并分 析如何有效地降低构造校验矩阵的复杂度。第五章对目前网络编码的发展状况及 作者所做工作进行总结。 第二章无延迟网络通用的网络编码方法 第二章无延迟网络通用的编码方法 本章首先给出了网络编码的代数模型，然后详细介绍目前已有的针对多播网 络的通用网络编码算法，一种是指数时阚算法，一种是多项式时潜算法给出了 这两种算法实现的时间复杂度 2 1 网络编码模型 为简单起见，对通信网络进行如下简单化的假设： 1 ) g 中每条边的容量是l 比特单位时间。就是对于任意一条边，若其容量为 ，( r 为整数) ，则将它分成，条容量为l 比特单位时间的并行边。 2 ) 每条链路有相同的时延。如果时延为零，则称该网络无时延。无时延网络 只适用于非循环网络。 下面给出比绪论中更明确的网络编码定义。 对于一个通信网络g = ( v ，e ) ，网络编码就是一族函数： 破。：( a , b ) e ，它们 满足：如果口是一个源节点，旃。：z 叶z ；如果口不是一个源节点，则 嚷叫) ：兀。k 。) 刀哼疋。于是对于任何链路( 口，6 ) e ，有一个对应的函数 旃甜) ：z 一七，它可以由函数( 氟础1 ：( d ，b ) e e 推导出来。 对于单源多播网络9 = ( y ，d ，源节点用s 表示，接收节点集合用r 表示。令 c = m i n 。n l a x f l o w ( s ，) ，则信源信息速率必须小于或等于c ，本文中假设信息速 率为”仍c ) 比特单位时间。设链路上传的符号集刀是有限域圮，园为每条边的 容量为l 比特单位时间，所以是将m 个连续时间单位的信息组成一个符号考虑的。 因此信源符号集z 是开维行向量空间聪，信源输入用信息向量z = k 如z 。】z 表 示，接收节点f 输出为y 。= f 弘只t 2 ，只，。】。如果译码没有错误，则y ，= z 。 对于多源多播网络有以下定理。 定理2 1 任何多源多播网络的网络编码可以等效为单源多播网络。 图2 1 多源多播网络 证明：假设如图2 1 所示，网络g = ( 矿，e ) 中有t 个源节点，分n g s , ，是。，s 西安电子科技大学硕士论文：网络编码原理及其纠错性分析 且设它们的信息传输速率分别为冠， z l = 毛，1z s l , 2 z & , r i 】哗，z 2 = 暖，lk 2 现在对给网络进行如下操作： 是，冠。它们的信息向量表示如下： 呜】哆，z = 。气，2 。，q 】。 r 1 1 引进一个节点s 作为虚拟源节点。 ( 2 ) 在节点s 和任意一个源节点s 之间引入尺条边。在这只，条边上依次传输 = 1 i ，：，2 ，z ，日e 于是得到一个新的网络9 = ( 矿，e ) ，该网络只有一个源节点s ，其功能等同于源 网络9 = ( 矿，e ) ，传输速率为r = r 1 + r 2 + + r k 。 用y ( e ) 表示链路8 上传的符号，下面给出线性网络编码的定义： 定义：对于一个网络夕= ( 矿，d ，如果对源链路e 满足 r ( e ) = z a ，其中a = 【口l ，。口2 一q 吐。吒，。】且q 。g f ( 2 ”) ； 对于非源链路e 满足 y ( p ) = 。“；t 。j l ( e ) 忽，0 且孱，g f ( 2 ”) ， 则称此网络编码为线性网络编码。 对于接收节点f ，其输出y f 的第f 个分量以= 。_ ，屯j 。】，和。 如果在g f ( 2 8 ) 中能找出参数q 。，屈- 和吃_ 的一组值，使每个接收节点都能 恢复出信息z ，则称这组参数为该多播的一个解决方案。对于r r l 值的选取后面将会 提到，只有其值足够大时某个多播才会有解决方案。 有了此定义，两个问题随之而来， 1 ) 一个给定的网络编码在各个接收节点唯一可译，参数q 。，屈- 和必须 满足什么条件； 2 )怎样有效地对给定的网络进行网络编码。 这两个问题中的第一个指出了网络编码唯一可译的条件，给解决第二个问题 提供了方向。本章后面的编码方法是在假设链路无延时的前提下进行的，链路有 延迟的情况在第三章讨论。 2 2 网络编码可译的条件 假设网络中只有一个源节点j 和一个接收节点f ，可用m 表示接收节点f 的转 移矩阵，z 是源节点输入、y 是接收节点输出，则有y = z x m 。矩阵m 元素可以 用系数q 肛。和也。表示出来。 下面举个简单的例子说明 t 的具体含义。 例：有一个网络图如图2 2 所示，信息从v l 发往h 。 第二章无延迟网络通用的网络编码方法 9 圈2 2 单源单接收节点网络幽 根据此图，有下列等式： y ( e 1 ) 2 a l ，qw l + a 2 q 心+ a 3 q 码 r ( e 2 ) = a l ，电+ a 2 ，吐w 2 + 口3 吐w 3 y ( e 3 ) = a 1 w 1 + 口2 + 吒， y ( 匕) = 反， 】，( q ) + 丘q y ( e 2 ) y ( e s ) = 名 y ( e 1 ) + & r ( e 2 ) y ( e 6 ) = 气，y ( 吒) + 以，y ( e ) y ( e 7 ) = 履y ( 吩) + 氏。y ( ) z l = 1 y ( e 5 ) + k ，i y ( e 6 ) + ，t y ( e 7 ) 屯= ，2 y ( e 5 ) + 气，2 】，( ) + ，2 y ( e 7 ) 乞= 气3 r ( e 5 ) + 气3 r ( e 6 ) + ，3 y ( e 7 ) 如果矩阵a 和口表示如下， a = a i ，qd i ，咆q 口2 ，q口2 ，p 2呸b q q呜qd 3 c 。 b r ： 则很容易就得到m = a i 氏，。 0 气- 气z ， ，- ，：。 气，b e , j 尼。氏，。 8 、d j ，。 p 。口。1 0 m 9 k 。 b7 。 转移矩阵的行列式 d e t ( m ) 2 d e t ( a ) ( f l , , ，。屁。一氏，。以，。) ( 氏，。戌。一戌。) d e t ( b ) 。选择a 为单位 阵，则只要( 以。& 。一& ，。屈，) ( & ，。& ，。一& 。& 。) 0 ，就可通过合适地选择 矩阵b 7 而使m 是个单位阵，从而在接收端有y = z x m = z 。 上面这个例子非常简单，很容易就可得到系数口。，展。和饥，的合理取值。但 要在一个多源节点、多接收节点的复杂网络中得到系统转移矩阵，需要一种一般 化的方法。 为了后面的描述方便，可以给网络的所有边定一个序，用关系 j 的 最小值； ( 2 ) 在f ：，找出一个a t 使尸( 茧，毒m ，) i 自；。0 且让 p 一p ( 点，毒“，皇) b 。； ( 3 ) 如果r = h 则结束，否则t 卜t + l ，回到( 3 ) 。 输出：( q ，啦，) 。 有了此算法就可以找出一个点( ，a i ，& 。，b e _ ，) 使 ，( ，q ，履 ，) 0 。此时所选系数值( ，a i ，瓯 ，) 已经满足定理2 3 中的条件了，因为如果不满足此条件，则无论( ，允i ，) 选什么值都是p = 0 。因此 可以重新选择系数( ，也一) ，使所有子矩阵m ，m b ， 都是单位阵。 算法中给出了网络编码可行时有限域的大小，这是一个上界，即当域大小大 于等于2 。时该网络的网络编码是一定有解的。下面定理给出了这个界的证明。 定理2 4 ( u p p e rb o u n d1 ) ：对于一个单源多播网络9 ，有个接收节点。 用p 表示n 个子矩阵m ，m ：，m ，行列式之积且假设万是p 中关于任意变量毒 的最高次幂。则在域f ，中存在该网络的网络编码有解，这儿的f 取满足2 占的最 小值。而算法2 1 中已经给出了如何求解。 证明：要证明当2 。 占时在域f ，中有解，只需证明算法2 1 的第( 2 ) 步中能 找出q f ：，使尸( 舌，喜。，品) i ：。0 就行了。 p ( 毒，点+ ，) 可表示如下： p ( 喜，毒+ l ，点) = ( 口1 o + q 1 茧+ + l , k i 点 ) # ( 毒+ l ，六) + ( 吒o + 口2 ，1 毒+ + d 2 毒屯) 置( 善+ 1 ，品) + + ( 吼，。+ 口l 1 毒+ + a l 毒k ) 置( 毒+ ，品) ( 2 2 ) 因为原先p ( 卣，磊，己) 包含的子项数是有限的，因此式子( 2 - 2 ) 中的是个有限 值；另外，因为p ( 卣，彘，品) 中每个参数的最高次至多为占，因此有k l 占， k 2 占，t 一，吒 占。因此多项式q ，。+ a i ，高+ + a i 1 。缶“，口2 ，。+ 嘭，l 戋+ + a 2 ，缶“， 吼，。+ 吼，t 专+ + 口岫毒k 都不含有因子等1 ，因此一定存在一个q f 当毒= a t 1 4西安电子科技大学硕士论文：网络编码原理及其纠错性分析 时多项式 q ，o + a 1 1 眚+ + c t i 毒“ ， 口2 ，o + 呜j 毒+ + a 2 ，毒屯 ， ， 吼，o + 吼1 毒+ + 吼，扎当k 中至少有一个不为0 ，即p ( 专，点，磊) k 。0 。 _ 根据定理2 4 可以给出一个粗略的上界。 推论2 1 ：假设一个零延迟传输网络9 有一个源节点和个接收节点，且设其传输 速率是r 。则在域只。( m l o g ：( n r + 1 ) 1 ) 中网络编码有解。 证明：因为矩阵( j f ) “的元素中含的系数砖。至多为1 次，同理r x r 矩阵 m = a ( i f ) 。1 8 7 含的系数q 。，厦。和玩，至多为1 次，因此t 接收节点的转移矩 阵行列式多项式l m i | 的每一分项中含系数q 一屈_ 和以_ 至多为r 次。又因为总共 有个接收节点，因此p = i m i 。i m , i “l m 。l 的每一分项中含系数口f 一包- 和b e ， 至多为n r 次。 2 4 多项式时间算法 一 2 4 1 算法描述 上面的网络编码算法是指数时间算法，不是非常有效，p s a n d e r s 等人【1 3 和 s j a g g i 等人【1 4 针对多播网络同时提出了一种多项式时间算法，下面详细介绍该 算法。 在给出的多播网络中引入一个虚拟源s ，并引入从s 到j 的仃条并行边，分别 用e 。，8 ：，e n 表示。假设这而条并行边传输的符号分别为而，乞，乙表示，即信源输 出信息向量的竹个分量。 对于任意一条边e e 上传输的符号y ( e ) ，可以用一个玎维行向量b ( e ) p 与 之对应，即有y ( 8 ) = z x b 7 ( p ) = 【2 z 2 毛】b r ( e ) ，称列向量b ( p ) 为边p 的全局编码 向量 。边 e ie ：，e n 的全局编码 向量依次 为 【1 0 0 ，1 ， o 1 0 ，【o 0 l o l ，【0 0 0 1 】。根据边e ie ，e n 的全局编码 向量及该网络的网络编码，可以得到其它任意一条边e e 的全局编码向量b ( e ) ， 即 9 ，一| 、 f 纂 图2 5 虚拟源引入示意图 第二章无延迟网络通用的网络编码方法 f q ，。b ( e 1 ) + d 2 ，山( e 2 ) + + a n ，加( 巳) ，e f o o ) 叭印2 1 。州嘶n 艮b ( e ) ，e 虬 。 易知有下面式子 爿( ，一f ) = b 7 ( e 1 ) b r ( e 2 ) b ：r ( e n ) 】。 ( 2 4 ) 由定理2 3 知道如果各个接收节点能译出输入信源向量，则当且仅当对于任意 f t ，向量集合f b ( p ) ：e f 忍) 张成空间酽。 现在关键是如何有效求出系数q 一屈。在具体描述算法前简单介绍路由算 法。 在真实网络中，如i n t e m e t 网络中，必须对某多播传输建立路由。对于单源、 单接收传输，建立路由非常简单，传输速率为n ( h 蔓m a xf l o w ( s ， ) ) 比特单位对 间时，只需建立以条无重合边的从s 到t 的路径。对于基于网络编码的单源、多接 收多播路由，可以通过分别建立每信源、信宿对( 5 ，) 之间的路由来得到。称( s ，t ) 之 间的疗条无重合边的路径集合为( f ) 的路径族，用厂表示。各个路径族之间可能 有些共同的边。如果某条边e 在路径w f 上，用足( p ) 表示边e 在路径矿上的 前一条边。 为了方便，暂时把系数q ，和尼。都用他。表示，即一条边到另条边的转移 系数。 对于一个给定的多播网络，