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

摘要 2 0 0 0 年，香港中文大学的r ，a h l s w e d e 等人从信息论的角度出发，提出了网络 编码的概念，它可以大大提高网络中的传输容量，从而可以实现利用有限的网络 资源传输更多的信息。像很多基本的概念一样，网络编码也是基于一个很简单的 思想。网络编码是指在通信网络中，可以在网络的中间节点上对接收到的信息进 行一定形式的编码处理，然后再传输出去，然后在信宿节点上，通过一定的处理 方式，译出信源所发的信息，而不是像传统通信网络中那样在中间节点上只是进 行存储转发。 网络编码的提出彻底地改变了计算机通信网络中的信息处理方式，其研究结 合了信息论、计算机通信网络、组播技术、多用户信息论和图论等很多方面的知 识。 本论文首先对网络编码的基本理论进行了全面系统的介绍；然后在充分掌握 了网络编码的各种基本理论知识后，作者重点对无线网络编码进行了深入的研究， 提出了一种无线网络编码模型，并证明了其可行性。这种新的无线网络编码模型 不但可以实现以网络的最大传输容量进行信息的传输，而且可以大大降低无线网 络中的能源消耗，这对用电池进行能量供给的无线网络来说，至关重要；最后对 网络编码构造中的一个重要参数一字母表进行了充分的研究，掌握了构造网络编 码必需足够大的字母表空间的根本原因；然后分析并证明了在新的无线网络编码 模型下，字母表大小并不会增加。 关键词：网络编码网络信急流组播 a b s t r a c t n e t w o r kc o d i n gw a sp u tf o r w a r db yr a h l s w e d ee ta 1 f r o mi n f o r m a t i o nt h e o r y p r o s p e c t i v ei n2 0 0 0 i tc a l la c h i e v et h em a x i m u mc a p a c i t yo fc o m m m f i c a t i o nn e t w o r k s ， w h i c hi sd e t e r m i n e db yt h em i n - c u tm a x - f l o wt h e o r e m a c t u a l l yn e t w o r kc o d i n gi s b a s e do i las i m p l ei d e a ，w h i c ha l l o w st h ei n t e r m e d i a t en o d e so ft h ec o m m u n i c a t i o n n e t w o r k st oc o d et h ei n f o r m a t i o nt h e yr e c e i v e df r o mt h e i ri n c o m i n gl i n k s t h e na tt h e s i n k s ，i n f o r m a t i o ni sr e t r i e v e df r o mw h a tt h e y r e c e i v e d n e t w o r kc o d i n gh a sa b s o l u t e l yi n c i t e dt h ec h a n g e so ft h ei n f o r m a t i o no p e r a t i o n m e t h o di nac o m m u n i c a t i o nn e t w o r k i t sr e s e a r c hi n v o l v e st h e k n o w l e d g ea b o u t i n f o r m a t i o nt h e o r y , c o m p u t e rc o m m u n i c a t i o nn e t w o r k s ，m u l t i c a s tt e c h n i q u e ，m u l t i p l e u s e ri n f o r m a t i o nt h e o r ya n dg r a p ht h e o r y t h ep a p e rf i s ts y s t e m a t i c a l l yi n t r o d u c e st h eb a s i ct h e o r yo fn e t w o r kc o d i n g t h e n b a s e do nt h ec o m m a n do fn e t w o r kc o d i n g ，t h ea u t h o rm a d ead e e pr e s e a r c ho nw i r e l e s s n e t w o r kc o d i n g ，a n dp r e s e n t saw i r e l e s sn e t w o r kc o d i n gm o d e lw h o s ef e a s i b i l i t yi s p r o v e d a tt h es a m et i m e t h i sn e ww i r e l e s sn e t w o r kc o d i n gm o d e lc a l ln o to n l y a c c o m p l i s ht h eu p p e rb o u n d o fn e t w o r kc a p a c i t y , b u ta l s og r e a t l yr e d u c et h er e s o u r c e c o n s u m eo fw s r e l e s sn e t w o r k sw h e r ee n e r g yi ss u p p l i e db yb a t t e r i e s ，f i n a l l ya l p h a b e t s i z e ，l t l 1i m p o r t a n tf a c t o ro f n e t w o r kc o d i n g ，i si n v e s t i g a t e d b yt h e o r e t i c a la n a l y s i s ，t h e r e a s o nw h ya l a r g e ra l p h a b e ts i z ei sn e e d e di nn e t w o r kc o d i n gi sl a yo u t a n d r e s e a r c h s h o w st h a tt h er e q u i r e da l p h a b e ts i z eo ft h en e ww i r e l e s sn e t w o r kc o d i n gm o d e ld o e s n o tj n c r e a s e k e y w o r d s ：n e t w o r kc o d i n g n e t w o r ki n f o r m a t i o nf l o wm u l t i e a s t 创新性声明 y 6 9 5 3 6 7 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 杰茹硷 日期 碰：墨：笪 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文和使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复印手段保存论文。( 保密的论文 在解密后遵循此规定) 本人签名：毒扣砼 导师签名 日期硼r 上g - 日期 矽学| 轨旷 第一章绪论 第一章绪论 本章首先介绍计算机网络的基本知识； 简单介绍；然后着重论述网络编码的提出、 安排。 接着给出无线通信网络和组播技术的 发展及其现状；最后给出本文的内容 1 1 计算机网络 计算机网络系统的产生，使现代社会发生了巨大的变化，尤其是i n t e r n e t 的 建立，推动了网络向更高层次发展，而建设信息高速公路，更是使得网络技术进 入新的发展阶段。 1 1 。1 计算机网络的产生和发展 计算机网络的发展大体上可以分为以下四个发展阶段l l j 。 ( 1 ) 面向终端的计算机网络 随着军事、工业等部门应用计算机的需求增加，人们非常需要将分散在不同 地方的数据进行集中处理。在2 0 世纪5 0 年代，人们开始将彼此独立发展的计算 机技术与通信技术结合起来进行研究，以计算机为中心，各终端通过通信线路共 享主机的硬件和软件资源，实际上就是以单机为中心的联机系统。 ( 2 ) 分组交换网 2 0 世纪6 0 年代中期，英国的d a v i e s 提出了分组( p a c k e t ) 的概念，使计算机 的通信方式由终端与计算机的通信发展到了计算机与计算机之间的通信。到了6 0 年代末期，美国国防部高级计划研究署的分组交换网a r p a n e t 的建立，对网络技 术的发展起了重要的作用，使网络的概念发生了根本性的变化，即表明了计算机 网络要完成数据处理与数据通信两大功能，从而为i n t e r n e t 的形成奠定了基础。 分组交换网由通信子网和资源予网组成，其核心技术是分组交换。 ：h ( x ( v ，f ) ) = 挣彬( v ) ( 2 - 1 0 ) 第二章网络编码概述 目的节点v 所收到的信息空间甲( v ) = z ( v ，1 ) ，z ( v ，2 ) ，z ( v ，叩( v ) ) ) ，它是由印( v ) 个离 散随机过程组成。在一个通信网络中，可以用( v ，v ，q ( v ，v ) 来表示节点v 和节点v 1 之 间的通信，它们之间所需传输的信息是q ( v ，v ) 。节点v 可以通过从其出发的边 e = ( v ，v 。) 来传输信息，我们用随机过程i ( e ) 来表示。边上所传输的随机过程的取值 范围是有限域只。 本文所讨论的通信网络都满足以下基本假设： ( 1 1 有向图g 中的任意一条边的容量均为常数，比如说比特每单位时间。这种假 设可以达到任意的精度。如果某条边上的容量超过了一比特每单位时问，则我们 用并行边来表示，每条边的容量还是一比特每单位时间。我们可以通过选择足够 大的时间单位来精确的表示边上的容量为分数的情况。 ( 2 ) 通信网络中的任意链路上都有相同的时延。在这里，我们假定所有链路的时延 均为0 ，也就是不考虑网络的时延。 ( 3 ) 为了简化问题的表示与描述，我们假定网络中没有环路存在。 ( 4 ) 不考虑通信网络中链路上的传输差错，这是因为网络编码是网络中网络层的操 作。在网络的七层模型中，差错控制可以由底层完成，而提供给网络层的是一个 没有差错的系统。 ( 5 ) 信源产生的随机过程x ( v ，f ) ， 1 , 2 ( v ) ) 是相互独立的，并且有相同的整数 熵，不如说一比特每单位时间。而且不同节点产生的随机过程也是彼此独立的。 2 2 2 网络编码的数学描述 在第一章中，我们已经用一个简单的例子图1 2 说明了网络编码的基本原理， 在这罩，我们给出网络编码的抽象数学描述。网络编码不同于传统路由之处就在 于在各个中间节点上的信息处理方式，下面定义各边上的函数映射。对边集e 中 的每条边e = ( v ，v 。) ，存在一种映射： z ：兀，一t 。 。8 r j ( ” ( 2 - 11 ) 这是对应于每条边的编码函数，它把某个节点所有输入边上的信息映射成其某个 输出边上将传输的信息。目的节点v 为了得到所需信息，对 v z ( v ，f ) 甲( v ) ，g 。：丌，寸， ( 2 1 2 ) 映射g 。是对应与目的节点v 的第i 个所需信息的译码函数，它从此目的节点输入 边上所传输的信息中恢复出所需信息。如果存在编码函数工和译码函数g 。，使 q ( v ，v ) c 甲( v ) ，则称通信网络( v ，v + ，q ( v ，v 。) 是可解的，同时称编码函数疋和译码函 1 4 西安电子科技大学硕士论文：无线网络编码研究 数g 。是此网络的一组解。 2 2 ，3 网络编码可以实现网络最大流的可行性证明 在这一部分，给出一个重要的结论：使用网络编码后，可以实现网络的最大容 量。设有向图g = ( 矿，e ) 中，信源为s ，信宿为f 。，屯，边( f ，j ) e 上的容量为r ，。 因为我们所关心的是信源到信宿的最大流，所以，不失一般性，我们假定图中没 有从其他节点流入信源s 的边，也不存在( f ，i ) e 。 我们考虑一个码长为n 的分组码。j 的取值x 取自于均匀分布的集合q 中，集 合q 中的元素称为信息。对于边( f ，j ) e ，节点f 发送给节点u ，的信息仅仅依赖于 节点i 以前接收到的信息。下面我们定义类分组码，d 码。 图g 上的一个( h ，( 巩，( f ，j ) e ) ，h ) 口- 码定义如下： ( 1 ) 一个正整数k ： ( 2 ) “： 1 ，k - 9 v ，v ：缸，k + 矿，使( “( ) ，v ( i ) ) e ( 3 ) a t = 4 ，| 爿t i ( i a t i 1 ) ，1 k k ，使1 7 i 彳。i = ，7 口 ，其中 l e n 瓦= 1 k k ：( “( t ) ，v ( t ) ) = ( f ，川a ( 4 ) 如果“( 女) = s ，那么以：q a 。，否则：以：n a 。斗4 ，其中 q = 4 ，1 2 “，q k = 1 七s t ：v ( 女t ) = “( 七) ”。岛 ( 5 ) g f ：兀a 女哼q ，1 珏l ，其中彬= 1 k k ：v ( | ) = f ) 使得对于所有的 1 广乳，云( x ) = x 成立，且x 为q 中的任意值。 ( n ，( 巩，( f ，) e ) ，h ) 口一码根据上述描述如下构造：在编码的起始阶段，变量x 的值 只有信源s 知道。在编码阶段，按照时间顺序，一共需要k 次处理，每次处理是指 一个节点向另个节点传输信息。在第k 次处理中，节点u ( k ) 根据函数 进行编 码得到4 中的个符号，然后将其发送给节点v ( k ) 。函数正所处理的符号域是节 点“( ) 目前接收到的信息，这里可以分为两种情况：如果“( 七) = s ，则函数 所处 理的符号域是q ：如果“( ) s ，则q 给出了目前节点 ( ) 所接收到的信息，因 此函数九所处理的符号域是兀。a 。集合毛给出了从节点f 向节点j 所传输信 息的处理次数，因此叩。表示出了在编码阶段，从节点i 向节点所传输的所有可能 的符号集。最后，嘭给出了t ，上接收到的信息的处理次数，g ，是信宿f ，上的译码 函数。 定义2 - 9 设孵= r 。( f ，j ) e 】。三维向量( 孵，h ，g ) 如果满足下列条件，则称其 第二章网络编码概述 为口一可达的。 如果对于任意s 0 ，则存在一个足够大的 ，使得图g 上的 ( n ，( ，( f ，j ) e ) ，h s ) 口一码，对于所有的边( f ，j ) e 均满足： l 0 9 2r 。r 。+ s 。( 2 1 3 ) 定义2 - 1 0 孵m = 觏：( m ，h ，g ) 是口一可达的j 。 定义2 1 l 有向图g = ( v ，e ) 中，信源为s ，信宿为t ，屯，边( f ，j ) 上的容量 等于r 。，则孵：。= 觏：从s 到f ，( ，= 1 ，l ) 的最大流h 定理2 - 2 豫 g = 暖：6 佗一1 4 ) 证明：首先，证明孵mc 倪：也就是如果对任意的f 0 ，则存在一个足够 大的”，使得图g 上的( 珂，( 仉，( f ，) e ) ，h f ) 口一码，对于所有的边( f ，- ，) e 均满足： n l 0 9 2r r ”+ s 的话，则从5 n t ，1 = l ，l 的最大流大于等于厅。 取1 l s l 和b c v 使得s b 且f ，蛋b 。令 e b = ( f ，) e ：f b 且，萑b w l ，( x ) = ( - ( x ) ，k u 。瓦，) ( 2 1 5 ) ( 2 1 6 ) 其中，x q ，以 ) 代表函数 的以工为自变量时的取值。w f ，( x ) 指信宿f ，在编码 阶段所收到的关于消息x 的所有信息。根据前面对口一码的定义， ( x ) 是节点u ( k ) 上前面所收到的信息的函数，所以， ) 是 ) ，k e u 巧的函数。因为节点 上可以接收到信息x ，所以有： “。” h 伍) = h ( w 。( z ) ) ( 2 - 1 7 ) = h ( ( z ) ，k u 毛) ( 2 - 1 8 ) ( 1 ，j ) e e , e 日( _ ( x ) ) ( 2 - 1 9 ) ( ，j ) e e s 女e 7 ； l o g ：( 2 - 2 0 ) ( ，) e 乩1 5 珞 = l o g ：( 兀阻i ) ( 2 2 1 ) = l o g ： ( r ，j ) e e 8 因此，h f 1 , 1 - i h ( x ) l 0 9 2r ( ，j ) e o f 2 2 2 1 ( 2 2 3 ) r 2 2 4 ) 西安电子科技大学硕士论文：无线网络编码研究 ( 凡+ 占) 忆瞎e “ r 。+ 蚓s ( j ，) ( 2 2 5 ) r 2 2 6 ) 在集合b 的所有可能取值范围内最小化上式的右边，得到 h - e m i n 。y r 。+ 陋p ( 2 2 7 ) 根据最小割最大流定理，上式右边的第等于从s 到t ，的最大流。当g 啼o ，就 得到了想要的结论。 接着证明暇。3 吼：。，由于这个证明相当复杂，这里就不再赘述，详见【1 2 。 一 上述定理利用有关熵的理论证明了通过网络编码，可以使网络的传输容量达 到最小割最大流给定的理论限。 2 3 线性网络编码及其实现 2 3 1 线性网络编码 文献【1 4 】 1 6 】【2 0 2 2 】【2 3 】【2 4 等都讨论了网络编码的线性描述和实现问题。 所谓线性网络编码也就是在实现网络编码过程中所用到的编码函数f 和译码 函数g 均采用线性函数来实现。具体定义如下： 定义1 f 3 】、设g ( v ，e ) 是无延迟的通信网络。我们称这样的g 为线性网络，如 果对于网络中的每一条边e = ( v ，v 。) e 上的随机过程i ( e ) 均满足： “n 一) i ( p ) = 吼，x ( v ，f ) + e , f l ( e ) ( 2 - 2 8 ) 在目的节点v 处有： z ( v ，i ) = g 。m ) ( 2 - 2 9 ) 耻 ( f ) i 其中，系数口叫，以k ，占。的取值是有限域，中的元素a 下面给出两个基本的概念： 定义2 1 2 上两式中的系数口叫，岛。，。被称为局部编码向量。 定义2 - 1 3 组播通信网络g ( y ，e ) 中，信源s v 的输入可以看作是有限域。， 上的向量( 吼，口：，o - 。) 。由于采用线性网络编码，则边p = ( v ，v ) e 上携带的信息 i ( p ) 是信源输入符号向量的线性组合，我们用一个向量耽0 ) 来表示，称其为全局 第二章网络编码概述 编码向量。则有 盯i i m ) ：z e ( 。) j 鼍z i ： l r 2 3 0 ) 我们可以看出，全局编码向量和局部编码向量之间的关系是： v e ( e ) = 。“旧m 见- v e ( e ) ( 2 _ 3 1 ) 全局编码向量和局部编码向量描述出了为了在一个组播通信网络中实现网络 编码，网络中的各个节点上需要进行的操作，所以如果一个通信网络是可解的， 那么网络编码的求解可以通过两个途径实现，确定全局编码向量或者确定局部编 码向量，它们具有同等的作用。下面我们将会看到，从向量角度出发实现网络编 码是求解全局编码向量，而代数构造角度出发的实现，是求解局部编码向量。 s - y r l i 等人【2 l 】指出可解组播网络均有线性解。从目前的研究来看，线性网 络编码的实现主要从两个角度去考虑，个是从向量空间的角度2 0 f 旧，另一个是 从代数构造的角度出发用转换矩阵来描述【1 4 】【1 5 1 1 3 3 1 ，下面分别介绍。 2 3 2 从向量空间角度出发实现线性网络编码 继r a h l s w e d e 等人【1 2 】指出网络的摄大流可由网络编码实现以后， 2 0 】首先给 出了网络编码的具体实现方法，之后， 1 6 】又从信息流的角度对以上方法进行了简 化，把算法的时间复杂度从指数级降到了多项式时间级。 定义2 - 1 4 通信网络g ( v ，e ) 上的线性码组播( l c m ) 是指给通信网络中的每 个节点v v 分配向量空间q 。( v ) ，同时给每条边e e 分配全局编码向量n ( e ) 。使 它们满足： ( 1 ) q ( s ) = q ( s ) ： ( 2 ) v e ( e ) q ( v ) 对每一个e = ( v ，v 。) ； ( 3 ) 对于网络中的任何非源节点集合k ： 2 。 代表其中的向量张成的空间。 如果对于通信要求( v ，v ，q ( v ，v 。) ，在目的节点v 7 处有： = q ( v ，v 。) ，则此线性码组播是此通信要求的一个解。把信源将 要传输的信息看成有限域只。中的元素所组成的向量，则某条边上所传输的信息 i ( p ) 就等于信源向量和全局编码向量沈( e ) 的乘积。 西安电子科技大学硕士论文：无线网络编码研究 下面我们以在第一章中给出的图卜2 中的通信网络为例，看一下线性码组播 在具体网络中的实现。对于图卜2 中的通信网络，我们可以如下给各条边分配全 局编码向量： 心c 文r ，= 娩。，w ，= 您。，y ，= i l o 。：一，：， 沈c 墨“，= c “，奶= 阮似，z ，= o 。一。s ， v e ( w ，z ) = 娩( x ，y ) = v e ( x ，z )r 2 3 4 ) 可以验证，上述线性码组播可以实现图卜2 中网络的通信。但是对于任意复 杂的通信网络，如何找到其所有的全局编码向量呢? e s a n d e r s 等人【l6 】针对组播网 络给出了一种多项式时间算法。现在把其主要思想介绍如下： 这种多项式时间算法是基于信息流的角度对 2 0 l 中的方法进行的简化。首先， 对于任意给定的通信网络，我们利用最小割最大流算法确定网络中所能传输的最 大信息量h 。如果这个通信网络是可解的，那么对每一个目的节点，我们都可以找 到h 条边不相互重合的路径，这h 条路径组成了此目的节点的一个流。此网络的 最大信息传输量是h 个符号，所以，我们沿着每个目的节点的流上的 条路径， 在每条路径上分别传输一个符号，则可实现所要的通信。也就是说，对每个节点 的h 条路径，它们传输了目的节点所要的全部信息，所以这h 条路径上的全局编 码向量必须张成整个信息空间。这种确定全局编码向量的方法可以在多项式时间 内完成。 下面看一个例子。 图2 - 2 多项式时间算法举例 如图所示组播网络。信n s 同时向信宿 a , b ，c ，d ，e ，f ) 组播信息，每条边的容量 均为单位比特。根据最小割最大流定理，我们可以得知此网络可以实现的最大组 播流量为2 。下面我们就按照上述多项式时间算法的思想给各边分配全局编码向 量。对于每个信宿来说，为了实现传输速率为2 的组播容量，我们由最小割最大 田 第二章网络编码概述 流算法分别找到各个信宿的两条互不相交的路径。然后在维持每个节点的路径上 都能张成整个信息空间的情况下，给各条边按自上而下，即信息流动的方向分配 向量，最终得到的向量分配为：取有限域g f ( 3 ) 的元素，v e ( s ，“) = do r ， v e ( s ，v ) = 【11 1 7 ，v e ( s ，w ) = 12 】7 ，v e ( s ，x ) = ol 】7 ，各信宿的入边上的全局编码 向量，和其始发节点的入边上的向量相同。 2 3 3 从代数构造角度出发实现线性网络编码 r k o e t t e r 和m m e d a r d 1 4 1 5 1 从另外一个角度出发，给出了实现线性网络编 码的全局编码向量所必须满足的条件。在这种表示方法中，引入了转移矩阵来描 述输入变量与输出变量之间的关系。设节点v 是网络中的唯一信源，用 五= ( x ( v ，1 ) ，x ( v ，2 ) ，x ( v ，4 v ) ) ) 来表示信源v 的输出。同时，我们用 z = ( z ( v ，1 ) ，z ( v ，2 ) ，z ( v ，卵( v ) ) ) 来表示目的节点v 的输入，则输入变量和输出变 量之间的关系我们就可咀表示为! = x m ，其中m 就称为系统转移矩阵。所以，要 想在目的节点由接收到的消息向量! 得到信源输入x ，则必须要求系统转移矩阵m 的行列式不为0 。那么，剩下的问题就是如何求得系统转移矩阵脚 在这里，我们用局部编码向量来表示出系统转移矩阵m 。在中间节点上，局 部编码向量与全局编码向量的关系为：v e ( e ) =p i ) 。首先定义任意 一* 再，( c ) j o v e ( e 通信网络的邻接矩阵f ，其中的元素为： k i = 豫e l , h ( e ，) = t ( e ，) 其它 则邻接矩阵f 是一个吲闷的矩阵，它直接反映了通信网络的拓扑结构。 我们定义通信网络的信源输出矩阵a 为： f 2 3 5 ) t o 裟对某们 ( 2 - 3 6 ) 它是一个x 旧阶矩阵，反映了信源输出的情况。 通信网络的目的节点输入矩阵b 定义为： 驴悟z j = z 仁妥善两神 p 。， 它是一个玎阶矩阵，反映了某个目的节点的收到信息的情况。 li 综上，矩阵a 、f 和b 均用局部编码向量表示，它们反映了整个通信网络的 信息输入输出和整个拓扑结构的情况。 0 o 口 ，l，、l = 4 西安电子科技大学硕士论文：无线网络编码研究 定理2 - 3 【1 哪5 在给定了一个表示网络的矩阵a 、f 和b 后，我们可以得到这个 网络的系统转移矩阵m 为： m = 4 ( ，一f ) “b 7 ( 2 3 8 ) 其中i 是一个l e l x 蚓的单位阵。 证明：矩阵a 与矩阵b 对整个转移矩阵不起根本性的作用，它们只是输入与 输出随机过程的一个线性组合。为了找到在一个输入随机过程( v ，i ) 与输出随机 过程z ( v ，) 之间的连接关系，我们必须沿着所有经过的路径记录随机过程x ( v ，i ) 所经历的变化，并最终转化为z ( v ) 。在网络中节点间的路径的变化可以用序列 ，+ ，+ f 2 + f 3 + 来表示。其中矩阵f 是一个上三角矩阵，最终将会有一个n 使 得f “为一个全零矩阵。 又因为，= ( ，一f ) - 1 ( ，一f ) ，同时有，= ( ，+ f + f 2 + f 3 + ) ( ，一f ) 所以，我们得到( ，一f ) = ( ，+ f + f 2 + ，3 + ) ，也就是( ，一，) 。反映出了信 源的信息在网络的传播过程中，由于经过网络编码而引起的影响。定理得证。 一 给出了网络的上述代数描述后，我们可以得到下面的重要定理： 定理2 - 4 ( 1 4 l 【1 5 1 给定一个线性网络，以下的三个命题是等价的： 1 一个组播传输是可解的。 2 可以达到图g 上由最小割最大流定理得到的容量限。 3 转移矩阵时的行列式在环e 1 ，口“，屈_ ，吐，上非零。 我们只要根据约束条件：系统转移矩阵的行列式不为0 ，确定出上式中的满足 条件的变量，也就是得到了局部编码向量，就完成了这个通信网络的线性网络编 码。 看下面的通信网络【1 4 l ，它满足上述的各种假设。 v 1 v 2 图2 - 3 例子 v 4 第二章网络编码概述2 由最小割最大流定理可得，其可以组播的最大流量为3 。下面我就用上述线性代数 的方法描述它，并得到实现上述最大容量的局部编码向量。根据上图的拓扑结果， 我们可以得到以下表达式： r ( e i ) = 口。l x 0 , i ，1 ) + t 2 z j , 2 x 0 1 ，2 ) + 口。3 x ( v l ，3 ) ( 2 3 9 ) y ( e 2 ) = t 2 e ：, 1 x 0 1 ，1 ) + 口2 x 0 i ，2 ) + 口3 x ( v l ，3 ) ( 2 - 4 0 ) y ( e 3 ) = 口。，】x ( v 】，1 ) + 口，2 ( v l ，2 ) + 口。3 x ( v 】，3 ) ( 2 4 1 ) r ( e 4 ) = q y ( e ，) + ，。y ( e 2 ) ( 2 - 4 2 ) y ( e 5 ) = p o m r ( e 1 ) + 气a y ( e 2 ) ( 2 4 3 ) r ( ) = 氏，y ( e 3 ) + 氏，y ( e 4 ) ( 2 4 4 ) r ( e ，) = 成，y ( e 3 ) + 氏h y ( e 4 ) ( 2 4 5 ) z ( v 4 ，1 ) = s ，l y ( e 5 ) + s ，l y ( e 6 ) + s 。，l r ( e 7 ) ( 2 4 6 ) z ( v 4 ，2 ) - - ，2 r ( e 5 ) + 占，2 y ( e 6 ) + 氏，2 y ( e 7 ) ( 2 4 7 ) z ( v 4 ，3 ) = r e ，, 3 y ( e 5 ) + s ，y ( e 6 ) + q 3 y ( e 7 ) ( 2 4 8 ) 把上述表达式根据前面的描述，写成矩阵的形式有： f 口轧。 口， 口唧， 4 = l 口钆2 口屯，2口2 l ( 2 4 9 ) l t 2 卵吼：，3 ，j j ( e e 3 , 1 8 e ，, 2 3 1 肚峨芝：j q j l 吼一乞，2s q ，3j 则系统矩阵m 就等于： f 以。鼠，。, c o 。k o ，。氏。1 m = a 1 反： , e o ：，q 氏，。鬼q 氏，q1 8 7 ( 2 一s 1 ) ( o以，。, c o 。 矩阵m 的行列式为： d e t ( m ) = d e t ( a ) ( 声。以， 一屈。屈h ；) ( 氏，。一。，。) d e t ( b ) ( 2 5 2 ) 我们可以在只，延伸的领域内选择参数，使得系统矩阵肘的行列式在只。中为非零 矩阵。因此，我们可令矩阵a 与矩阵b 为单位阵。由f o r d f u l k e r s o n 算法找到的 解决问题的方法等同于屈。= 。= 既，。= 氏。= 1 ，而这时所有的倪。类型的 西安电子科技大学硕士论文：无线网络编码研究 其它系数均令它们等于零。可以清楚地看到，一个在v ，与v 。之间的点对点通信在3 比特每单位时问下是可行的。我们指出，对于令人困惑的网络问题存在很多种解 决办法，那就是对于系数卢。的所有值，可令已知的转移矩阵的行列式的值不为零。 观察这个例子，可看到网络极其重要的地方是方程式( 成。厦。一成：。以。) ， ( 卢。以，。一屈。) 被认为是可变的选择。因此该多项式的值并不为零。 2 3 4 线性网络编码的局限性 现已证明，可解的组播网络均有线性解。但是，对于非组播网络，线性失去 了其优越性。s r i i s 等人【2 3 中给出了线性不可解的非组播网络。但口1 1 中用向量线性 网络编码解决了那个问题。向量线性网络编码是一种更为广泛的线性运算，它不 同于前面讲到的线性网络编码，它一次处理的每个信源的信息不为1 ，这相当于在 一次处理中重复使用通信网络。紧接着，r a n d a l ld o u g h e r t y 等人拉4 j 又构造出了一 个向量线性网络编码出不能解的非组播网络，但它却存在非线性解。 2 4 网络编码的性能分析 网络编码的提出彻底改变了传统网络中的信息处理方式，从信息论的角度证 明了其可行性，那么网络编码到底能给我们带来怎么样的好处呢? 在带来各种 好处的同时，又会带来什么弊端呢? 已经有很多人致力于这方面的研究 e l l l 8 艄胁】【3 6 】，在这里我们将引用他们的研究成果来说明网络编码的作用。 2 4 1 吞吐量的改善 网络编码最主要的目的就是改善网络的吞吐量，实现组播中的最大流传输。 我们下面讲从理论与实际应用两方面来讨论其对吞吐量的改善情况。 首先从理论分析上讲，网络编码相对于传统路由在吞吐量上有如下改善： 定理2 - 5 f 1 9 1 在一个每条链路上都是单位容量，无环的通信网络g ( y ，e ) 中，使 用网络编码后得到的传输容量是不编码前的q d o g l z ) 倍。其中，q 是信源符号空 i 、自j ，州是通信网络中节点的个数。 证明：我们考虑这样的一个通信网络g ( v ，e ) ，节点集合v = u u t , a t ，其 中中间节点u = l ，2 ，2 ，接收节点丁= c 刎“= h ， 边集为 e ：f ( s ，“) ks u u ( “，) i r ，“e ，) ，h = 。( 1 。g l v i ) 。 第二章网络编码概述 因为信源与所有信宿之间的最小割为h ，所以网络编码可以提供的组播容量就 为h 。在没有网络编码的情况下，组播容量小于2 ，为了证明这一点，假定信源要 在h 次连续的不编码传输中发送2 ”个符号乜，b ，。给丁中的每个信宿。设 ，是中间 节点中接收到b ，的那些节点的集合。因为每条边上都是单位容量，那么信源一共 至多可以发送2 砌个符号给这些中间节点，因此：l u “墨2 h n 。这就表示存在一 个f 使得l u ，l h 。设u 表示u u 。中的任意h 个元素组成的子集。那么信宿u 就不 能接收到符号b ，。定理得证。 下面看一下网络编码与传统的各个组播路由算法的吞吐量的比较1 1 8 1 。图2 4 中的结果是基于六大商用因特网服务提供商( i s p s ) n 网络拓扑研究得到的结果。对 于每一个i s p ，我们任意选择一个发射节点和2 0 个接收节点。图2 - 4 由六部分组 成，每一部分对应一个i s p 图。同时，对于每一部分，从左到右，分别依次给出 了以下算法的吞吐量：最大速率分布树、重复最大速率分布树、基于e d m o n d s 定 理l o v a s z s 证明的组播树构造、实际网络编码、组播容量。最大速率分布树是用 p r i m 算法，找到从源节点到每个接收节点的可以提供最大速率的路径。而重复最 大速率分布树就是多次用p r i m 算法。寻找多个最大速率分布树。从图中我们可以 看出，利用多个组播树比传统i p 组播中的仅仅使用一个组播树，吞吐量会得到很 大的改善。用多个组播树和网络编码得到的吞吐量都已经十分接近网络的组播容 量。 两安电子科技大学硕士论文；无线网络编码研究 2 4 2 均衡网络负载 图2 - 4 几种组播路由算法的仿真结果比较1 目 网络编码除了可以改善网络的吞吐量以外，还可以均衡网络负载0 3 4 】，这一点 我们通过下面的一个例子来说明。 图2 - 5网络编码用于均衡网络负载举例 第二章网络编码概述 a a ，ba ，ba b a , b ，c ，da , b ，c ，da , b ，c ，d 图2 6 两种组播树 如图2 5 所示的通信网络，各边上的容量均为2 。图2 - 6 给出了此网络的两种 组播树的建立方式，一种是传统的单会话组播树，如图2 - 6 的左图所示，另一种 是基于网络编码的组播树，如图2 - 6 的右图所示。我们可以看到左图实现的组播 容量为2 ，也就是可以同时传输2 个比特给每个信宿；而使用网络编码的右图的组 播容量为4 。这是网络编码在吞吐量上的改善，前面已经说过，不是这里讨论的重 点。 这里要看的是，为了实现信源信息向所有信宿组播的目的，左图中的实现方 式是所有传输集中在5 条链路上，而网络中的其他链路没有得到充分利用，为空 闲状态。这样必然会引起所用链路上的拥塞，从而导致“瓶颈效应”：而同时又有 部分链路没有得到充分利用。而使用网络编码的右图与此相反，其使用了网络中 的所有链路实现信息的传输，使信息在传播过程中，均匀的分布于整个网络，从 而有效地避免了“瓶颈效应”。 从这个简单的例子中，我们可以看出网络编码在均衡网络负载方面的优越性 能，这方面正待于进一步的研究。 2 4 。3 其他的好处 除了上述两点外，网络编码还会给我们带来很多其他的好处，比如说更少的 网络资源消耗。这里的网络资源不但指带宽等有限的资源，而且当网络编码应用 在无线网络中时，它还可以同时减少能量钓消耗，这是本文的一个研究重点，后 面的章节中还会讲到。 应用网络编码可以提高网络的鲁棒性也是网络编码的一个重要作用。文献【j 2 已经对这方面的应用进行了理论分析和试验仿真。 最后，有一点值得我们特别注意的是，网络编码在给我们带来这么多方面的 同时，也有其自身的缺点。比如说，应用网络编码后，会给网络带来更多的时延3 4 0 ； 、叶 、0 h一3饥|；土6掣意娥蕊苜 吵voj哆黪 b f，3丫ii，又6、)寸蛩户”国 抄、|，f、 ， ， n 、引m誊 西安电子科技大学硕士论文：无线网络编码研究 而且网络编码的运算是不但有有限域上的加法运算，而且有有限域上的乘法运算 和矩阵的求逆，所以这会提高实现的复杂度。在这方面还有很多问题，有待于我 们进一步的研究。 2 5 本章小节 网络编码是一个全新的概念，本章对网络编码进行了基本的介绍。首先给出 了研究网络编码所需的图论中的各种相关基本概念，网络编码的实现与网络拓扑 直接相关，所以了解图论中的一些概念和相关知识非常重要。接着重点描述了网 络编码的基本概念，并用个简单的例子直观的描述出了网络编码的巨大优势， 接着从信息论的角度出发证明了其可咀实现网络中的最大流，而这是传统路由方 式所不能达到的；然后介绍了网络编码目前最主要的实现方式一线性网络编码， 并给出了线性网络编码的从不同角度出发的两种构造方式。线性网络编码便于实 现，但是它有些很多局限性，因此非线性网络编码的研究越来越受到人们的关注。 最后，从理论和试验仿真两个方面总结了网络编码的性能分析，这些已有的研究 成果充分显示了网络编码的巨大优越性。但是，这些分析的模型还是基于很多理 想的假设，所以关于更接近实际网络的性能分析有待于我们进一步的努力。 第三章无线组播中的网络编码研究 第三章无线组播中的网络编码研究 本章首先介绍了无线网络中特有的无线组播特性；接着讨论了结合无线组播 特性和网络编码实现的最小能量组播方法；然后给出了这种方法的一个应用特例 一通信网络中的信息互换：最后我们提出了一种无线网络编码模型，并对其进行 了详细讨论，证明了其可行性。 3 1 无线组播特性 3 1 1 无线组播特性w m a ( w i r e l e s s m u l f i e a s t a d v a n t a g e l 我们考虑一个无线组播网络，网络的连通性取决于各个节点的发射能量。我 们假定每个节点可以自由选择它的发射能量值，但其值不可超过p 。，接收能量 值随r ”变化，其中r 是接收节点距离发射节点的距离，口为取值在2 和4 之间参 数，具体取值取决于网络的通信介质的特性。所以，相距为r 的两个节点之间建立 链路所需的发射能量正比与，不失一般性，我们归一化能量值为1 。由此可得， p ，= 节点f 和节点，之间建立链路所需的能量= ，”( 3 - 1 ) 如果一个无线通信网络的最大允许发射能量p 。足够大，那么节点就可以以充分 大的能量值发射，以使整个通信网络是全连通的。 我们假设用的是全向天线，因此在一个发射节点通信范围内的所有节点均可以 收到其发射的信息。下面就举例说明无线通信中的广播特性在组播中应用的重要 性。如图3 - i 所示，无线通信网络中节点i 要同时向其邻居节点，和传输相同的 信息，设到达节点，和k 分别所需的能量为p 。和p ，。，而节点i 只要以 p = m a x ( p 。，p 衅) 的能量发射，则节点和k 都可以接收到所要的信息。于是 可以节省的能量为：p 。+ p ， 一p f ，“，i ) 。这就是无线网络中的无线组播特性【3 9 】4 0 1 。 k 幽3 - l 无线组播特性p 砌，t ) 2 m a x p u ，p 啦) 3 1 2 代价衡量 寻找最优的组播路由算法，就是要在最小可能的能源消耗情况下，完成最大 西安电子科技大学硕士论文：无线网络编码研究 信息量的传输。在考虑无线组播特性的无线网络中，代价函数是基于节点的，而 不是基于链路的，下面我们就分别介绍基于链路的代价衡量和基于节点的代价撕 量f 3 9 】。 ( 1 ) 基于链路的代价衡量(