（电路与系统专业论文）网络编码构造方式的研究.pdf

南 硕士 学 研 作 题 英 主 群算法 i ( e y w o r d s ：n e t w o r kc o d i n g ，m i n i m u n c o s t ，i n f o r m a t i o nf o l wd e c o m p o s i t i o n , m i n i m a ls u b t r e eg r a p h s ，g r a p hc o l o r i n gt h e o r y , a n ta l g o r i t h m s 南京邮电大学硕士研究生学位论文中文摘要 摘要 2 0 0 0 年，a h l s w e d e 从信息论的角度出发，首次提出了网络编码的概念。网络编码将原 来分立于物理层和网络层的两个核心概念编码和路由有机的融为一体，彻底改变了路 由器只能对信息进行存储转发的传统模式，建立起一种全新的网络体系结构和信息编码传 输模式。 通过允许网络节点进行编码，可以获得网络多播速率的最大流限，即网络资源利用的 理论上限。此外通过网络编码可以取得节省网络带宽资源、平衡链路负载、优化能量受限 网络的能量消耗等好处。因此，对于网络编码的研究具有相当重要的意义。 本论文在分析网络编码理论的基础上，利用最小代价函数网络编码、信息流分解、图 染色、蚁群算法等理论对网络编码构造算法进行研究。论文首先回顾了网络编码的提出、 发展和概况：简要描述了网络编码的基本概念，并从信息论的角度证明了其可以实现网络 中的最大流，而这是传统路由方式所不能达到的；然后介绍了线性网络编码的实现方式； 通过引入最小代价函数网络编码和信息流分解的思想简化网络编码的构造；基于最小代价 函数网络编码提出了一种多速率网络编码的构造，将其应用于无线m e s h 网络，并进行了仿 真实验；提出了m s g - n c 网络编码构造算法，该算法通过最小子树图的划分，提高网络编 码的有效性，并结合图染色理论，提出了基于蚁群算法的图染色算法来实现网络编码构造 的思想，进一步简化了网络编码构造。 关键词：网络编码，最小代价，信息流分解，最小子树图，图染色理论，蚁群算法 英文摘要 a b s t r a c t n e t w o r k c o d i n gw a sp u tf o r w a r db ya h l s w e d ef r o mi n f o r m a t i o nt h e o r yp e r s p e c t i v ei n2 0 0 0 n e t w o r kc o d i n gm a k e sc o d i n ga n dr o u t i n go r g a n i ci n t e g r a t i o n , w h i c ha r et w oc o r ec o n c e p t s c p e r c t e sf r o mt h ep h y s i c a ll a y e ra n dt h en e t w o r kl a y e r i tt h o r o u g h l yc h a n g e st h et r a d i t i o n a l p a t t e r no ft h er o u t i n ga n de s t a b l i s h e san e wn e t w o r ka r c h i t e c t u r ea n di n f o r m a t i o nc o d e d t r a n s m i s s i o nm o d ei n s t e a do fs t o r e - a n d f o r w a r dm o d e i fc o d i n gi sp e r m i t t e db yt h en e t w o r kv e r t i c e s ，t h em a x f l o wb o u n do fn e t w o r km u l t i c a s t c a nb ea c h i e v e dt h et h e o r e t i c a lu p p e rb o u n do fn e t w o r kr e s o u r c eu t i l i z a t i o n f u r t h e r m o r e , t h r o u g hn e t w o r kc o d i n g , w ec a no b t a i nt h eb e l e f i t so fs a v i n gi nb a n d w i d t h ，l o a db a l a n c i n g , o p t i m i z i n gt h ee n e r g yu s a g eo fe n e r g y - l i m i t e dn e t w o r k sa n ds oo n a sar e s u l t , t h es t u d yo n n e t w o r kc o d i n gi so f g r e a ts i g n i f i c a n c e r e s e a r c ho nn e t w o r kc o d i n gc o n s t r u c t i o na l g o r i t h mb a s e do nt h eu s eo fm i n i m u m - c o s t f u n c t i o nn e t w o r kc o d i n g , i n f o r m a t i o nf l o wd e c o m p o s i t i o n , g r a p hc o l o r i n g , a n tc o l o n ya l g o r i t h m w i t ht h ea n a l y s i so fn e t w o r kc o d i n gt h e o r y f i r s t l y , t h ed i s s e r t a t i o nr e v i e w st h ec u r r e n ts t a t ea n d d e v e l o p m e n to ft h en e t w o r kc o d i n g i td e s c r i b e st h ec o n c e p to f t h en e t w o r kc o d i n g i n f o r m a t i o n t h e o r yh a sp r o v e ni t sn e t w o r ka c h i e v e dt h em a x i m u mf l o w ，w h i c ht h et r a d i t i o n a lr o u t i n gc a l ln o t a c h i e v e s e c o n d l y , t h et h e s i sd e s c r i b e st h er e a l i z a t i o no fl i n e a rn e t w o r kc o d i n ga n di n t r o d u c e s t h a tm i n i m u m c o s tf u n c t i o nn e t w o r kc o d i n ga n di n f o r m a t i o nf l o wd e c o m p o s i t i o ns i m p l i f y n e t w o r kc o d i n gc o n s t r u c t i o n t h et h e s i sp u t sf o r w a r dam u l t i - r a t en e t w o r kc o d i n gc o n s t r u c t i o n b a s e do nm i n i m u m - c o s tf u n c t i o nw h i c ha p p l i e dt ow m na n dc 凋f f l i e so u tas i m u l a t i o ne x p e r i m e n t t h ed is s e r t a t i o np r o p o s e sm s g - n ca l g o r i t h md e t e r m i n e sd i v i s i o no fm i n i m a ls u b t r e eg r a p h s ，s o t h a tn e t w o r kc o d i n gi sm o r ee f f i c i e n ta n dp r o p o s e sag r a p hc o l o r i n ga l g o r i t h mb a s e da n t a l g o r i t h m st od e s i g nn e t w o r kc o d i n gb yl i n k i n gm i n i m a ls u b t r e cg r a p h so fn e t w o r kt og r a p h c o l o r i n gt h e o r y , f u r t h e rs i m p l i f y i n gn e t w o r kc o d i n gc o n s t r u c t i o n k e y w o r d s ：n e t w o r kc o d i n g , m i n i m u m - c o s t , i n f o r m a t i o nf l o wd e c o m p o s i t i o n ，m i n i m a ls u b t r e e 笋a p l l s ，g r a p hc o l o r i n gt h e o r y ，a n ta l g o r i t h m h 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c t i i 目录i i i 第一章绪论1 1 1 计算机网络概述1 1 2 单播、广播和多播1 1 3 网络编码的提出和发展现状2 1 3 1 网络编码的提出2 1 3 2 网络编码的发展概况2 1 4 本文的主要研究工作和章节安排。4 第二章网络编码概述6 2 1 网络编码预备知识6 2 2 网络编码的基本概念9 2 2 1 网络编码的定义9 2 2 2 网络编码可实现网络最大流的可行性证明1 0 2 3 线性网络编码1 3 2 3 1 线性网络编码的定义1 3 2 3 2 线性网络编码的实现1 4 2 3 3 单源多播网络和多源多播网络1 8 2 4 线性网络编码构造方式的符号界2 0 2 5 网络编码的分布式实现方式随机网络编码2 l 2 5 1 随机网络编码方法2 2 2 5 2 随机网络编码的评价2 3 2 6 网络编码的好处2 3 2 6 1 网络多播容量的改善：2 3 2 6 2 均衡负载2 3 2 6 3 提高带宽利用率：2 4 2 6 4 减少节点能量消耗2 5 2 6 5 减少信息传播时延2 5 2 6 6 差错控制2 6 第三章两种优化网络编码构造的解决方案2 7 3 1 基于最小代价函数的网络编码构造2 7 3 2 信息流分解2 8 3 2 1 子树图分解2 8 3 2 2 信息流分解后的可行和有效网络编码3 2 第四章一种多速率网络编码的构造3 3 4 1 无线m e s h 网络的多传输速率3 3 4 1 1 无线m e s h 网络结构3 3 m 妻室坚皇三! 三堂堡主堕壅生堂篁笙奎 旦墨 -_-_-一 4 1 2 多传输速率3 3 4 2 网络模型与定义3 4 4 3 多速率网络编码3 5 4 3 1 寻找最小代价子图。3 5 4 3 2 最小代价子图中搜索多速率编码节点3 6 4 3 3 执行最小代价网络编码3 7 4 4 仿真实验一3 8 第五章m s g - n c 网络编码构造算法3 9 5 1 最小子树图的搜索算法3 9 5 1 1 最小子树图的定义。3 9 5 1 2 种最小子树图的改进搜索算法4 1 5 2 一种基于蚁群算法的网络编码优化算法4 4 5 2 1 算法思想4 4 5 2 2 经典算法的局限性4 5 5 2 3 算法描述4 6 5 2 4 算法验证4 8 5 3 仿真实验5 1 第六章结束语5 5 致谢5 6 参考文献5 7 本人在攻读硕士研究生期间发表的论文6 l i v 第一章绪论 1 1 计算机网络概述 第一章绪论 知识经济的两个重要特点是信息化和全球化。要实现信息化和全球化，就必须依靠完 善的网络。因此，网络现在已经成为信息社会的命脉和发展知识经济的重要基础。网络对 社会生活的很多方面以及对社会经济的发展已经产生了不可逆转的影响。网络是指“三 网 ，即电信网络、有线电视网络和计算机网络。虽然三种网络在信息化的过程中都起到 了十分重要的作用，但其中发展最快并起到核心作用的是计算机网络【l 】。 计算机网络从产生到发展大体上可以分为以下四个阶段【2 】： 第一阶段：2 0 世纪6 0 年代末到2 0 世纪7 0 年代初为计算机网络发展的萌芽阶段。其 主要特征是：为了增加系统的计算能力和资源共享，把小型计算机连成实验性的网络。 第二阶段：2 0 世纪7 0 年代中后期是局域网络( u 蝌) 发展的重要阶段。其主要特征是： 局域网技术是从远程分组交换通信网络和i o 总线结构计算机系统派生出来的。 第三阶段：整个2 0 世纪8 0 年代是计算机局域网络的发展时期。其主要特征是：综合 数字数据通信网络( 1 s d d ) 和智能化网络( 玳) 的发展。 第四阶段：2 0 世纪9 0 年代初至现在是计算机网络飞速发展的阶段。其主要特征是： 计算机网络化，协同计算能力发展以及全球互连网络( i n t e m e t ) 的盛行。计算机的发展已 经完全与网络融为一体，体现了“网络就是计算机”的口号。 1 2 单播、广播和多播 网络的传输方式有单播、广播和多播三种。 ( 1 ) 单播 单播是指在一个信源节点和一个目的节点之间进行的通信。 ( 2 ) 广播 广播是指在一个信源节点和网络中所有其它节点之间进行的通信。 ( 3 ) 多播 多播又称组播，是指在网络中将数据包以尽力传送( b e s t 。e f f o r t ) 的形式发送到网络中 的某个确定节点子集，这个子集称为多播组( m u l t i c a s tg r o u p ) 。多播的信源节点只向网络 南京邮m ：大学硕士研究生学位论文 第一章绪论 发送一份实例，通过网络节点复制发送到多个目的节点( 不会像广播那样发送给不需要的 目的节点) 。多播是一种高效的通信方式，不仅减轻了发送源的处理负荷，也降低了网络 带宽的使用。 1 3 网络编码的提出和发展现状 1 3 1 网络编码的提出 一直以来，通信网络都是采用存储转发的方式来传输信息，其基本思想类似于邮递系 统。1 9 9 7 年，杨伟豪教授首先将编码概念使用于卫星网络的数据传输。同年，李硕彦教授 参与研究一般抽象网络上数据传输与编码的混合使用。2 0 0 0 年，a h l s w c d e 等人发表了一篇 题为“网络信息流的文章【3 】，这篇文章为提高网络的传输容量指明了一个新的方向。作 者在文中首次提出了“网络编码这一概念，该概念打破了常规，通信网络的中间节点不 仅仅转发或存储转发输入的信息流，而是允许中间节点在转发信息前对输入的信息流进行 编码，这样可以达到通信网络的最大容量，从而最大限度的利用现有网络资源。 一个通信网络可以用有向图来表示，根据图论中的最大流最小割定理可知，网络多播 的最大容量等于发送节点和多播组中各接收节点之间的最小割的最小值，该最小值称作网 络多播的最大流限。对于一般的网络，并不能实现网络最大流的传输，因此它不是最佳的； 而如果使用网络编码，即在网络的中间节点上，对接收到的信息先进行编码然后再传输出 去，在接收端，目的节点再根据自己的要求译出所需要的信息，可以大大提高网络的传输 速率，充分利用网络中的链路资源。 网络编码思想是在y e u n g 的对称分层编码【4 5 6 】研究的基础上提出的，将分层编码在信 源节点的编码推广到允许整个网络节点进行编码来获得网络多播的最大流限。传统的存储 转发方式是网络编码的一种特殊形式。 1 3 2 网络编码的发展概况 自从2 0 0 0 年碰s w e d e 等人提出网络编码的基本概念之后，关于网络编码的研究如雨后 春笋般多起来。目前，有很多电信业巨头和著名的大学都在致力于这方面的研究，如普林 斯顿大学川、麻省理工学院【8 1 、瑞士e p f l 学院9 1 等以及多家盯公司的研究中心，包括微软 研究院【1 0 1 、贝尔实验室【l l 】、香农信息实验室1 2 1 都在积极开展对网络编码理论和应用的研究； 网络编码也逐渐引起了国内学术界的关注和重视，我国的清华大学【1 3 】、南京大学【1 4 1 、西安 2 南京邮电大学硕士研究生学位论文第一章绪论 电子科技大掣1 5 】等也对网络编码进行了探索。 a h l s w e d e 等人仅给出了网络最大信息传输速率的存在性证明，并没有给出具体的网络 编码方式。l i 、y e u n g 和c a i 提出单一源，多接收节点网络的最大传输速率可以线性网络编 码实现【1 6 1 。通过一个广泛适用的线性编码多播( l c m ) 算法，每个接收节点都可以达到其 最大流。l c m 主要应用于无环网络。l c m 规则为每条边分配边向量，也称局部编码向量。 边上传递的信息是节点的信息向量与局部编码向量作向量乘法之后得到的数值。每一个信 息都携带一个全局编码向量。这个全局编码向量记载了某个信息在网络中经过不同的边所 经历的编码的过程。中间节点发送信息的时侯，首先将所有接收信息的全局编码向量合成 一个d x d 的矩阵。信息f ( 1 s i d ) 的全局编码是矩阵中第i 列。该矩阵与边上的边向量根 据编码规则作向量乘法，得到的d 维列向量就是输出信息的全局编码向量。在解码的时候， 将所有接收到的信息的全局编码向量组合成一个完整的矩阵，只要求出它的逆矩阵就可以 解码出原始信息。 k o e t t e r 等人【1 7 , 1 8 , 1 9 】提出的网络编码的代数构造方式，它将一般的网络编码寻找线性解 的方法简化为寻找多元多项式的非零解。同时寻找编码系数的方法也通过代数编码方式而 简化了。这种构造方式是在已知整个网络的拓扑信息的情况下，用一个系统转移矩阵来描 述信源输入信息和信宿接收到的信息之间的关系，并通过构造符合要求的系统转移矩阵来 实现网络编码。 与此同时，c a i 等人【2 0 l 基于网络编码提出了网络纠错码的概念。网络纠错码不同于传 统的基于逐个链路错误纠正的经典纠错码，它是采用分布式的方法来对整个网络中的差错 进行纠正。文中同时给出了网络纠错码的汉明( h a m m i n g ) 限和沃尔沙莫夫一吉尔伯特 ( g i bc r t - v a r s h a m o v ) 限。 s a n d e r s 等人【2 1 2 2 提出了一种构造网络编码的多项式时间算法。该算法的核心思想是编 码时对每一接收节点维持一个大小为信源多播速率j i l 的割集，使得其对应的全局编码向量 线性无关。这种方法不但把网络编码构造的复杂度从指数级降到了多项式级，而且大大 降低了网络编码中所采用的字母表的下限。 针对多播信息传输问题，h o 和m e d a r d 【2 3 盈】等人设计了一种不需要知道网络节点分布情 况的随机网络编码法则，通过在字母表中随机选取系数实现网络编码。 对于有环网络，可以采用卷积码的思想进行研究【2 5 郐】。当信息流在有环网络中传播， 时延成了构造网络编码必须要考虑的问题，可以将时延与卷积编码器( 由一系列移位寄存 器和加法器组成) 联系起来。 3 南京邮l 怠大学硕士研究生学位论文第一章绪论 上述研究都是针对有线网络的，关于无线网络中的网络编码的研究也是网络编码研究 中的一个热点【2 7 ，2 引。网络编码在无线a d h o e ( 无线自组织网络) 、w s n ( 无线传感器网络) 、 无线m e s h 网络中的应用也取得了新的进展。 另外，人们对网络编码在提高网络性能方面的应用也作了大量的研究，研究表明，网 络编码除了能够提高系统的容量外，在数据压缩【2 9 1 、负载均衡【3 0 1 、降低节点能量消耗【3 1 1 、 减少传播时延、差错控制【3 2 1 以及信息安全【3 3 】等方面都有重要的应用前景。 1 4 本文的主要研究工作和章节安排 网络编码理论是网络通信研究领域中的一项重要突破，自从提出以来，已迅速发展成 为一个重要的研究领域，并对信息论、编码、通信网络、网络交换理论、无线通信、计算 机科学、密码学、运筹学、图论、矩阵理论等领域带来了深远影响。自从网络编码概念提 出以来，很多专家和学者都致力于网络编码算法的研究与构造。他们从不同的角度出发， 提出了很多的方案，大多基于理论的分析和实现。特别是近几年，网络编码成为了众多国 际研讨会的热门议题。从信息流分解出发并将网络编码构造算法研究进一步深化是本文将 要研究的主要工作。 作者在对网络编码的基本理论进行深入学习的基础上，从最小代价函数网络编码的思 想出发，提出了一种基于无线m e s h 网络的多速率网络编码的构造算法，并进行了仿真；从 信息流分解的思想出发，提出了m s g - n c ( m i n i m a ls u b t r e eg r a p h s - n e t w o r kc o d i n g ) 构造 算法，并证明了其可行性。本文共分五章，主要结构如下： 第一章绪论部分简要介绍了计算机网络的产生和发展，回顾了网络编码的提出、发 展和概况。 第二章介绍了研究网络编码所需的相关预备知识，并从信息论的角度证明了其可以 实现网络中的最大流，而这是传统路由方式所不能达到的；其次，介绍了网络编码目前最 主要的实现方式一线性网络编码，并对其编码符号界进行分析；最后，给出了采用网络 编码所带来的好处。 第三章第一部分引入最小代价函数网络编码的思想优化网络编码构造。第二部分引 入信息流分解的思想优化网络编码构造，信息流分解可以简化网络拓扑结构从而简化网络 编码的构造，然后介绍了子树分解的概念和过程，并讨论了在信息流分解的基础上构造有 效网络编码的方法。 第四章基于最小代价函数网络编码，提出了一种多速率网络编码的构造算法，将其 4 5 ( 2 ) 设m 为有向图g = ( y ，层) 中的节点，以v f 为始点的边的条数称为节点坼的出度，记 为d e g + ( m ) ；以m 为终点的边的条数称为节点屹的入度，记为d e g 一( v 3 。显然， d e g ( v ，) = d e g + ( m ) + d e g 一( h ) 。 ( 3 ) 对于图g = ( y ，e ) ，度数为1 的节点称为悬挂节点，它所关联的边称为悬挂边。 在研究和描述图的性质时，子图的概念占重要地位。 6 所谓最大流问题是求使得从信源节点s 送往信宿节点t 的流量w 达到最大流。为了解决 网络的最大流问题，给出切割的概念。 定义2 8 ：设u 为节点集合的一个子集，使得s u ，t 萑u ，将一个端点在【，而另一个 端点不在u 的边的集合目= ( f ，j ) e i u ，萑u 称为节点s 和f 的一个割。割的容量定 义为集合昂中包含的所有边容量的和，用c ( s ，f ) 表示，即c ( s ，f ) = 岛。 7 南京邮咆大学硕士研究生学位论文 第二章网络编码概述 图2 1 中虚线表示节点s 和t 的一个割，其中： 【，= s ，b ，c ，d ， c ( s ，f ) = 如+ + 民+ 如= 4 + 3 + 2 + 4 = 1 3 。 很显然，对于一对节点，其不同的割对应的容量可能不同。 f 、 、 图2 1 网络流图 定理2 1 【3 5 1 ：( 最小割最大流定理) 对于已知的网络流图，从信源节点5 到信宿节点t 的 流量w 的最大值等于其最小割的容量，即 m a xf l o w ( s , t ) = m i nc (s，0(2-4) 对于一个有向网络，我们可以采用f o r d - f u l k e r s o n 标号算法和d i n i c 算法求解网络的最 大流。 以单信源信宿为例，定义一些将会用到的符号：设图g = ( y ，司中的信源为j ，信宿 t n ，气。边o ，j ) e 上的容量为吗，且有足= 【岛，( f ，j ) e e 。从信源j 到信宿，l = 1 9 o o o ，上 的子图用g ，= ( y ，目) 表示，其中：局= ( f ，j ) ee ：j 莲l ( f ，户在信源s 到信宿的有向路径上) 。 对于所有的边( f ，j ) e 有 o 石色 ( 2 5 ) 对于除信源s 和信宿厶之外的所有其他节点f 矿有 厶= 乃 ( 2 6 ) ，：( f 。) e e 爿j ，j ) e e 也就是流入节点f 的总的流量等于流出节点f 的总的流量。 设f = 厶，( f ，- ，) 司代表图g 中对于所有的边( f ，) e ，从信源s 到信宿的流。，在 8 的路由传输方式，中间节点采用存储和转发的操作。假定w 转发信息2 j i ，则链路似，x y 和届 上传输信息均为6 i ，虽然信宿z 收到了岛和如，但信宿y 却只能收到6 i ( 同时收到一个多余 的包) ，区 l l ty 和z 无法同时收到6 i 和6 2 ，该多播不能实现最大传输容量。图2 2 ( 3 ) 给出 一种编码方案从图中可以看出，为了从信源节点s 同时传输两比特信息6 i ，6 2 到信宿节点， 9 定一个映射规则，中间节点按这个规则把输入映射为输出。 2 2 2 网络编码可实现网络最大流的可行性证明 在这一部分，给出一个重要的结论，使用网络编码后，可以实现网络的最大容量，这 是整个网络编码理论的基础。设有向图g 中，信源为j ，信宿为，乞，边o ，力e 上的 容量为足，。假定图中没有从其他节点流入信源s 的边，也不存在( f ，f ) e 。 考虑一个长度为刀的分组码。令z 表示信息源，工为x 的输出。q 称信息空间，x 以 均匀分布按一定索引从q 中获得相应的符号。 图g 上的一个( 玎，( 仍( j ) ee ) ， 皿一码定义如下： ( 1 ) 有一个正整数k 。 ( 2 ) 存在映射 ”： l ，k ) 专矿 ( 2 1 0 ) 1 0 南京邮电大学硕士研究生学位论文 1 ，：l i po ，k ) 专v 使得( 后) ，1 ，( 七) ) e 。 ( 3 ) 存在集合4 = 1 ”，1 4 i ) ，l k k ，使得 兀= 嘞 t e 巧 其中乃= ( 1 七k ： ( j ) ，y ( 后”= o ，力) ( 4 ) 如果u ( k ) = s ，那么 其中q = 1 2 ，f 2 柚1 ) 。 石：q 专4 如果”( 后) s ，且幺= l 七- k ：y ( 后= “( 后) ) 非空，那么 五：丌4 专4 t e 么 ( 5 ) 设为：兀4 ，专z ，1 ，其中 j t e 昕 形= l 七足：叫【后) = ，( 2 - 1 5 ) 使得对于所有的l - i o ，存在一个足够大 e 日( _ ( x ) ) l o g ： = l o g ：( 兀i a 。i ) = l o g ：嘞 ( f ，) e 岛 1 2 ( 2 - 2 1 ) ( 2 - 2 2 ) ( 2 - 2 3 ) ( 2 2 4 ) 南京邮电大学硕士研究生学位论文 第二章网络编码概述 因此j l l 一占n - l h ( x ) = 刀一l 0 9 2 嘞 ( 玛+ s ) 嘞+ i e i s 一 口 在集合b 的所有可能取值范围内最小化上式的右边，得到 h - 6 m 。i n 岛+ i e i g 口( f 。j ) e e a ” ( 2 2 5 ) ( 2 2 6 ) ( 2 2 7 ) ( 2 - 2 8 ) ( 2 2 9 ) 根据最小割最大流定理，式( 2 - 2 9 ) 的右边等于从snt , 的最大流。当s 专o ，就得到 了想要的结论。 同理可证明孵腼3 吼：g ，详见文科3 1 。 上述定理利用有关熵的理论证明了通过网络编码，可以使网络的传输容量达到最小割 最大流给定的理论限。 2 3 线性网络编码 前面介绍了通过网络编码可以获得网络多播容量的最大流限，这里介绍线性网络编码。 将信息分组看作特定基域上的向量，在信息通过某一节点时，只对其作线性变换。通过线 性网络编码可以获得网络多播的最大流限。 2 3 1 线性网络编码的定义 设q 表示足够大基域f 上的h 维向量空间。这里采用的信息单位为基域上的一个符 号，即每单位时间信道上可以传输一个基域上的符号。 定义2 1 4 ：通信网络g = ( y ，e ) 上的线性编码多播( l c m ) 是指给通信网络中的每个节点 1 ，v 分配向量空间q ( 1 ，) ，同时给每条边e ee 分配全局编码向量v e ( e ) ，其中 ( 1 ) q ) = q ； ( 2 ) v e ( e ) q i ( 1 ，) 对于每一个p = ( 1 ， ，； ( 3 ) 对于网络中的任何非信源节点集合矽 = ( 2 3 0 ) 1 3 堕壅坚皇奎堂堡主塑壅竺堂竺堡壅兰三兰塑鳌叁里塑垄 代表其中的向量张成的空间； ( 4 ) 给节点t 的输出边分配的编码向量是其输入边所分配的编码向量的线性组合0 l c m 亥i j 画了一种信息数据在网络中传播的结构。将信源节点s 要传输的信息分成h 维 的向量组，称作信息向量。在传输过程中，一条边上承载的数据符号是信息向量和该边所 分配的向量的向量乘积。 下面以图2 2 中的通信网络为例，说明线性码多播在具体网络中的实现。对于图2 2 ( i ) 中的通信网络，网络编码的基域为只，可以如下给各条边分配全局编码向量 阮c 品r ，= 圪。，计= 纥c 以y ，= 巴 c 2 - 3 ) 圪c s ，”，= 圪c “，们= 圪c ，z ，= ：) c 2 3 2 ， v e ( w , x ，= 圪c x ，y ，= 虼c 毛z ，= 1 c 2 3 3 ， 信源3 的信息向量为 恕) ，每条边上传输的信息符号为信息向量( 6 i6 2 ) 和该边的编码 列向量的向量乘积。 对于任意复杂的通信网络，如何找到其所有的全局编码向量呢? 文献 1 6 ，1 7 ，1 8 , 3 6 1 等都 讨论了线性网络编码的如何实现线性编码多播最大流的问题，主要从两个角度去考虑，一 个是从向量空间的角度【1 1 ，另一个是从代数构造的角度出发用转换矩阵来描述【1 7 1 耵。本 文着重对第二种方式做深入研究。 2 3 2 线性网络编码的实现 本节主要介绍从代数角度如何实现线性网络编码。 k o e t t e r ：看f l m e d a r d 1 7 , 1 8 , 1 9 从代数构造角度出发，给出了实现线性网络编码的全局编码向 量所必须满足的条件。在代数构造方式中，引入了系统转移矩阵来描述输入变量与输出变 量之间的关系。设节点j 是网络中的信源，用x = ( x ( s ，1 ) ，x ( s ，2 ) ，x ( s ，p ) ) ) 来表示信源j 的输出，其中x ( s ，u ( s ) ) 是一个离散随机过程，( s ) 表示信源s 的出度。同时，用 z = ( z ( t ，1 ) ，z ( t ，2 ) ，z ( t ，7 7 ( f ) ) ) 来表示信宿节点t 的输入，同理z ( t ，r l ( t ) ) 是一个离散随机过 程，r l ( t ) 表示信宿t 的出度。则输入变量和输出变量之间的关系我们就可以表示为z = x m ， 1 4 南京邮1 乜大学硕士研究生学位论文 第二章网络编码概述 其中朋就称为系统转移矩阵。所以，要想在信宿节点由接收到的信息向量z 得到信源输入 工，则必须要求系统转移矩阵膨的行列式不为0 。那么，剩下的问题就是如何求得系统转 移矩阵m ? 下面首先给出线性网络编码的代数描述： 定义2 1 5 【1 8 】：设g = ( 矿，e ) 表示通信网络。如果对于网络中的每一条边e = ( v , v 3 e _ l z 的随机过程用i ( e ) 表示。 u f v ) i ( e ) - x ( v ，f ) + 尼，讹) ( 2 3 4 ) 1 = i 一： ( ，) 爿f ) 其中h ( e ) 代表为边的始点，( p ) 代表p 为边的终点。上面公式代表每一条边上传送 的信息是始点产生的全部信息乘以系数哆，的加权和，加上始点接收的所有传入信息乘以 系数屏，的加权和。换句话说节点传输的信息是所有节点自身产生信息和节点接收到信息 的综合。于是，有： 信源节点j 处输出的信息公式： 声h ， m = x ( s ，0 ( 2 - 3 5 ) j i i 信宿节点t 处输入的信恳公式： z ( t ，f ) = 毛，。讹) ( 2 - 3 6 ) r h ( e ) - - t 中间节点的输出的信息公式： i c e ) = 厦c l ( e 3 ( 2 - 3 7 ) f 铀( f 爿( f ) 其中，系数哎，纵，岛，的取值是有限域墨中的元素。称这样的无延迟的通信网络为线性 网络。式( 2 3 4 ) 和式( 2 - 3 6 ) 中的系数吒j ，厦f ，毛，。被称为局部编码向量。 定义2 1 6 ：多播通信网络g = ( y ，e ) 中，信源s 矿的输入可以看作是有限域上的向 量 q ，】t 。由于采用线性网络编码，则边p 上携带的信息，( 0 是信源输入符号向量的线 性组合，用一个向量阮( p ) 来表示，称其为全局编码向量。则有 ，( 力= 圪( p ) q ，0 2 ，吒】t 可以看出，全局编码向量和局部编码向量之间的关系是 1 5 ( 2 3 8 ) 丽尕郴t i f 、掌硕士研冗生学位论文第二章网络编码概述 。4 “o - _ - o - _ _ _ o o _ _ _ _ _ _ _ _ _ o o _ o l i _ - - _ _ _ _ _ - - - - - _ _ _ - _ _ _ - - - _ o _ _ - i _ _ - i _ _ - _ - - - _ _ _ - _ - i _ _ _ i - _ - - i - _ _ - o _ - i - _ - _ - l _ o _ - - - - _ _ _ _ _ _ 一 v e c e ) = y 州州( 力易，。v e ( e ) ( 2 - 3 9 ) 式( 2 3 9 ) 表示全局编码向量和局部编码向量之间的关系，描述出了为了在一个多播 通信网络中实现网络编码，网络中的各个节点上需要进行的操作。 定义2 1 7 ：任意通信网络的邻接矩阵f ，其中的元素为： ，一f 见勺j i l ( q ) = f ( 巳) 擘一0 其它(2-40) 则邻接矩阵f 是一个蚓吲的矩阵，它直接反映了通信网络的拓扑结构。 定义2 1 8 ：任意通信网络的信源输出矩阵彳，其中的元素为： 吻= 伊铲瓷x d 对某仰 ( 2 它是一个吲阶矩阵，反映了信源输出的情况。 定义2 1 9 ：任意通信网络的信宿节点输入矩阵b 定义为： = 伊铲引凳啊某个， ( 2 啦) 它是一个叩吲阶矩阵，反映了某个信宿节点的收到信息的情况。 式( 2 - 4 0 ) 、式( 2 - 4 1 ) 、式( 2 - 4 2 ) 中矩阵f ，a 和b 均用局部编码向量表示，它 们反映了整个通信网络的信息输入输出和整个拓扑结构的情况。 其次给出系统转移矩阵m 的表达式。 定理2 3 【1 7 捌：在给定了一个表示网络的矩阵，彳和b 后，可以得到这个网络的系统 转移矩阵m 为： m = a c i - f ) 一1 丑t ( 2 4 3 ) 其中，是一个l e i 蚓的单位阵。 证明：矩阵彳与矩阵曰对整个转移矩阵不起根本性的作用，它们只是输入与输出随机 过程的一个线性组合。为了找到在一个输入随机过程x ( ，i ) 与输出随机过程z c v , j ) 之间的 连接关系，必须沿着所有经过的路径记录随机过程x c v ，f ) 所经历的变化，并最终转化为 z p ：) 。在网络中节点问的路径的变化可以用序列i + f 1 + ，2 + f 3 + 表示，其中矩阵，是 上三角矩阵，最终将会有一个n 使得，为一个全零矩阵。又因为，= ( ，一，) 1 u f ) ，同 雨囊l t t f ! f i 太掌硕士研究生学位论文第二章网络编码概述 一_ 。- _ i _ - i - - _ _ _ - _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ - - _ _ - - - - _ _ _ l _ - _ - - - 。一 时有，= ( ，+ f 1 + f 2 + p + ) ( ，一f ) 。所以得到u 一，) 一1 = ( ，+ f + ，2 + ，3 + ) ，u 一，) 一1 反映出了信源的信息在网络的传播过程中，由于经过网络编码而引起的影响。至此定理得 证。 给出了网络的上述代数描述后，可以得到下面的重要定理。 定理2 4 t 1 7 , 1 8 】：给定一个线性网络，以下的三个命题是等价的： ( 1 ) 一个多播传输是可解的。 ( 2 ) 可以达到图g 上由最小割最大流定理得到的容量限。 ( 3 ) 转移矩阵肘的行列式在环e 【- ，吒，乃，0 ，”j 非零。 只要根据约束条件，系统