（应用数学专业论文）多播网络编码算法研究.pdf

摘要网络编码概念，最早于2 0 0 0 年，由香港中文大学的r a h l s w e d e 等人提出该理论打破了通信网络中中间节点对接收到的信息只进行存储。转发的传统信息处理方式，允许中间节点对输入信息流先进行编码处理，再转发出去，最后在信宿节点上，通过一定的处理方式，译出信源所发出的信息从而实现最大流最小割定理所决定的多播传输的最大理论传输容量网络编码的构造算法解决的主要问题是如何有效求得每条链路对应的编码向量，并运用该编码向量进行线性操作计算出链路上传输的信息向量编码算法的复杂性是衡量网络编码能否有效实现的重要依据本文主要对多播网络编码算法进行了研究，完成的工作有以下几个方面：1 深入研究了现有的网络编码的几种经典算法：指数时自j 算法、多项式时间算法及随机网络编码算法2 在深入研究g e n e t i c 线性网络编码算法的基础上，结合离散路由的使用，对其进行了改进，提出了一种改进的多播网络编码算法，并给出了算法的合理性证明和复杂度分析3 提出了一种基于最短路的网络编码多播路由算法，该算法与现有编码模式一起，能够构成完整的网络编码多播传输方案并通过仿真试验，将多播路由算法与i p 路由算法之间的性能进行了比较关键词：网络编码多播网络编码算法路由算法a b s t r a c tt h ec o n c e p to fn e t w o r kc o d i n gw a sf i r s tp u tf o r w a r db yr a h l s w e d ee ta 1 f r o mc h i n e s eu n i v e r s i t yo fh o n gk o n gi n2 0 0 0 i nt 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 d ，t h ei n t e r m e d i a t en o d e si nt h en 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 h o w e v e r , n e t w o r kc o d i n ga 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 nn e t w o r k st oc 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 t h e na tt h es 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 yr e c e i v e d n e t w o r kc o d i n gc a na 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 u n 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 t h ec o n s t r u c t i o no fn e t w o r kc o d i n ga l g o r i t h mi su s e dt oo b t a i nt h ec o r r e s p o n d i n gc o d i n gv e c t o rf o re a c hl i n k 嬲e f f e c t i v e l ya sp o s s i b l e ，a n dt h e ng a i nt h ei n f o r m a t i o nt r a n s m i t t e do v e rt h el i n kb yc a l c u l a t i n gt h ee n c o d i n gv e c t o r s t h ec o m p l e x i t yo fn e t w o r kc o d i n ga l g o r i t h mm i g h tr e f l e c tw h e t h e rt h ea l g o r i t h mc a nb ee f f e c t i v e l yi m p l e m e n t e d i nt h i sp a p e r t h em u l t i c a s tn e t w o r kc o d i n ga l g o r i t h mh a sb e e ns t u d i e da n ds e v e r a lr e s u l t sa r eo b t a i n e d t h em a i nw o r ko ft h ep a p e rc o n s i s t so ft h ef o l l o w i n gt h r e ep a r t s ：1 s e v e r a lc l a s s i c a ln e t w o r kc o d i n ga l g o r i t h m sh a v eb e e nr e s e a r c h e d ，s u c h 弱e x p o n e n t i a l t i m ea l g o r i t h m ，p o l y n o m i a l - t i m ea l g o r i t h ma n dr a n d o mn e t w o r kc o d i n ga l g o r i t h m 2 b a s e do nt h eg e n e r i cl i n e a rn e t w o r kc o d i n ga l g o r i t h m ，a n dc o m b i n e dw i t ht h eu s a g eo fd i s c r e t er o u t i n g ，an o v e li m p r o v e dm u l t i c a s tn e t w o r kc o d i n ga l g o r i t h mi sp r o p o s e di nt h i sp a p e r t h er a t i o n a l i t yo ft h ea l g o r i t h mh a sb e e np r o v e d c o m p l e x i t ya n a l y s i si n d i c a t e st h a tt h ea l g o r i t h mi nt h i sp a p e rr e d u c e st h ec o m p u t a t i o n a lc o m p l e x i t yo b v i o u s l yc o m p a r e dw i t hg e n e r i ca l g o r i t h m 3 ar o u t i n ga l g o r i t h mf o rn e t w o r kc o d i n gm u l t i c a s tb a s e do nt h es h o r t e s tp a t hi sp r o p o s e d t h ea l g o r i t h m ，t o g e t h e rw i t ht h ee x i s t i n ge n c o d i n gs c h e m e ，c a nc o n s t r u c tap r a c t i c a lm u l t i c a s ts y s t e m s i m u l a t i o n ss h o wt h a t ，f o rn e t w o r kc o d i n gm u l t i c a s t ，p e r f o r m a n c eh a sb e e ni m p r o v e ds i g n i f i c a n t l yi nc o m p a r i s o nw i t ht h et r a d i t i o n a li pm u l t i c a s ti nt e r m so ft h r o u g h p u t k e y w o r d s - n e t w o r kc o d i n gm u l t i c a s tn e t w o r kc o d i n ga l g o r i t h mr o u t i n ga l g o r i t h m创新性声明本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的研究成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志所做的任何贡献均已在论文中做了明确的说明并表示了谢意申请学位论文与资料若有不实之处，本人承担一切相关责任本人签名：蠲垒筐关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文( 保密的论文在解密后遵守此规定)本人签名：蝴鱼建导师签名：e ta 1 ：丝 ! ：至望第一章绪论第一章绪论本章首先介绍计算机通信网络的基本知识；接着介绍计算机通信网络中所采用的多播通信技术以及其实现方式和局限性；然后着重论述网络编码的提出、发展以及现状；最后给出了本文的内容安排1 1 计算机通信网络1 1 1 计算机通信网络的产生和发展自从1 9 4 6 年，世界上第一台数字计算机问世以来，计算机技术开始和通信技术相结合，相互促进，共同发展，最终产生了计算机网络计算机网络的发展大体上可划分为四个阶段【l l ：( 1 ) 面向终端的计算机网络从2 0 世纪5 0 年代中期至6 0 年代中期，面向终端的计算机网络实际上是以单个计算机为中心的远程联机系统该系统中，终端围绕着具备自处理功能的中心计算机分布在各处系统中主要存在的是终端和中心计算机间的通信而计算机的主要任务是进行批处理( 2 ) 计算机计算机网络( 分组交换网)从2 0 世纪6 0 年代末至7 0 年代末，多台计算机通过通信线路互联起来为用户提供服务，称为计算机计算机网络该系统中，终端和中心计算机间的通信已改变为计算机和计算机之间的通信，用单台中心计算机为所有用户需求服务的模式，被大量分散而又互联在一起的多台计算机共同完成服务的模式所替代换言之，分组交换网以通信子网为中心，以由主机和终端构成的用户资源子网为边缘用户不仅共享通信子网的资源，而且还可共享用户资源子网的丰富的硬件和软件资源( 3 ) 开放式标准化的计算机网络从2 0 世纪8 0 年代初至9 0 年代初，国际标准化组织( i s o ) 提出了一个使各种计算机能够互连的标准框架开放式系统互连参考模型( o p e ns y s t e mi n t e r c o n n e c t i o n r e f e r e n c em o d e l ，o s i i 洲) ，简称o s i 自此，计算机网络进入开放式标准化发展阶段该系统有统一的网络体系结构、遵循国际标准化的协议网络标准化的最大体现就是i n t e m e t 的飞速发展( 4 ) 网络互联与高速网络技术进入2 0 世纪9 0 年代以来，微电子技术、光通信技术、大规模集成电路技术和2多播网络编码算法研究计算机技术不断发展，为网络技术的发展提供了有力的支持；而网络应用正迅速朝着实时化、高速化、智能化、集成化和多媒体化的方向不断深入信息高速公路的建设旨在建设一个覆盖全国的高速宽带通信和计算机网络；全球信息基础设施的建设旨在实现全球范围内的网络通信这一切在全球范围内极大地推动了计算机网络及其应用的发展新一代网络的出现己成必然1 1 2 计算机通信网络的体系结构( 1 ) o s i 参考模型为了使网络系统结构标准化，1 9 7 8 年国际标准化组织( i s o ) 提出了开放系统互联( o s i ) 参考模型该模型将整个网络通信的功能分为7 个层次【2 l ，下层为上层提供服务，每个层次完成特定功能图1 1 为o s i 参考模型示意图表1 1概括了o s i 参考模型中各层的功能主机系统和用户7 应 1 j 层= 。! i 一6 表示层。冒。土5 会话层。r 。：i 。一4 运轿层。 r 。土3 网络层。r 。土一2 数据钎路层。1 。土一1 物珊层传输媒体图1 1o s l 网络分层模型第一章绪论表1 1o s i 网络各层功能层次功能7 应用层6 表示层5 会话层4 运输层3 网络层2 数据链路层1 物理层提供电子邮件、文件传输等用户服务转换数据格式，数据加密和解密通信同步，错误恢复和事务操作网络决策，实现分组和重新组装路由选择，计费信息管理错误检测和校正，组帧数据的物理传输( 2 ) t c p f i p 协议模型在计算机网络通信中，o s i 模型只是作为理论研究的模型，并没有实际应用实际中使用最为广泛的通信协议是t c p i p 协议1 2 , 4 6 1 它包括传输控制协议( t c p ) 和网际协议( i p ) ，是网络互联的标准协议连入i m e m e t 的计算机进行的信息交换和传输都需要采用该协议t c p i p 实际上是一组协议的代名词该体系中，通信任务组织成五个相对独立的层次：应用层、运输层、互联网层、网络接入层、物理层每个层次都包含许多其他的协议如应用层的主要协议有：文件传送协议( f t p ) 、超文本传送协议( h t t p ) 、简单邮件传送协议( s m t p ) 、远程登录协议( t e l n e t ) ，以及近几年发展起来的域名服务( d n s ) 等运输层的协议有t c p 和u d p 其中，t c p 是面向连接的传输控制协议，为应用程序之间的数据传输提供可靠连接；u d p 为应用层提供无连接的服务，它并不保证一定传到，也不保证按顺序传输网络接入层关心的是如何在一个网络中两个端系统之间传送数据的问题总之，t c p i p 协议重点强调应用层、运输层和互联网层，而对网络接入层和物理层只要求能够使用某种协议来传送互联网层的分组1 2 多播通信技术1 2 1 几种网络通信方式的概念及特点计算机网络的主要功能包括数据通信和资源共享等，用户数据要从一个终端发送到另一个终端，首先要确定传输路由，不同的通信方式，具有不同的路由传输方式也不同【3 1 网络的通信方式主要有以下几种f 4 5 】：( 1 ) 单播( u n i c a s t ) ：点到点的通信方式( 2 ) 多播( m u l t i c a s t ) ：点到多点的通信方式( 3 ) 汇播( c o n c a s t ) ：多点到一点的通信方式4多播网络编码算法研究( 4 ) 群播( m u l t i p o i n tt om u l t i p o i n t ) 多点到多点的通信方式( 5 ) 广播( b r o a d c a s t ) ：点到所有点的通信方式其中，单播和广播是传统的通信方式，采用单播方式实现网络通信时，源节点向各个用户发送相同的信息，信息的重复数量与用户数量相等，浪费了大量带宽，也增加了服务器的负载采用广播方式实现时，不仅会将信息发送给不需要的主机而浪费带宽，也可能由于路由回环引起严重的广播风暴所以，传统的单播和广播通信方式都不能有效的解决单点发送多点接受的问题多播，是支持多方通信的高效通信方式，发送节点只向网络发送数据的一份实例，经由网络节点复制并发送到多个接受节点多播在传输多方通信数据时，不仅减轻了发送源的处理负荷，也降低了网络带宽的使用，尤其是在通信带宽及其受限的移动自组织网络中，采用多播机制对实现多方通信是非常有必要的综上，在多播、汇播和群播这些通信方式中，多播是目前研究最多，也是应用最广的网络连接方式1 2 2 多播通信技术的路由实现多播是信源节点向多个目的节点传输同一信息的通信方式，参与多播的所有节点组成了一个多播组，每个节点称为多播组成员m 】实现多播传输的传统的路由方式是建立一棵覆盖所有多播组成员的生成树，即多播树【2 6 1 由源节点向树中的相邻节点发送消息，然后这些相邻节点继续向树中下一级节点转发这些消息具体过程如下：为了实现信源节点向多个信宿节点多播信息，在通信网络中建立一个或多个多播树，每个多播树都将信源和所有的信宿连接起来，所要传输的信息就在这些事先选好的路径上传输每个多播树能够实现的传输速率取决于组成这个树的所有边中容量最小的边为了获得更高的多播速率，可以建立多个多播树，在不同的多播树上传输不同的信息，只要每条边在各个树上传输的信息量之和不超过该边的容量即可多播树分为两种类型1 4 1 ：有源树和共享树有源树的根是信源节点，叶子节点是信宿节点有源树又分为两种：一种是最短路径树，从源节点到各多播组成员都以最短路径相连；另一种是最小s t e i n e r 树，即：在一个连通图中，给定一个节点子集，要求在图中找出一棵覆盖给定子集的费用最小的生成树共享树，也称为中心树，每个多播组只需建立一棵多播树，各组节点之间的通信通过中心树中被称为”核心”的节点进行，即各节点通过最短路与核心相连，将消息发往核心，再由核心发往接收节点可以看出，比起有源树，共享树减少了很大的计算和存储开销第一章绪论1 2 3 多播通信技术实现的局限性多播通信主要靠在通信网络上建立多播树来实现虽然多播树具有很多优点，如：信息以并行的方式沿着树枝发送到不同的组成员，降低了信息传递的时延；网络中需要传送的复制信息减少，而且信息的复制只在树权处进行，节省了网络带宽资源，并减少了拥塞，降低了网络负载然而，多播树最主要的局限在于：不能实现多播传输的最大容量说明如下：由最大流最小割定理( m i n 。c u tm a x f l o wt h e o r e m ) 5 】可知，网络中两点之间的最大流量可以通过最小割来衡量；同时，可以通过最大流算法 6 1 得到两点之间的最大传输速率并找到它们之间的最大流路径然而，建立一点到多点的多播树时，问题变得复杂起来一般认为，多播树的建立是一个n p 问题i t ! 一般先采用最大流算法寻找信源与一个信宿之间的最大流及其实现的路径；然后再依次寻找信源和其它信宿之问的路径注意，在寻找信源与第二个信宿之间的路径时，要在原通信网络中去掉信源与第一个信宿之间已经用过的链路的容量以此类推，在寻找信源与第三个信宿之问的路径时，要在原通信网络中去掉信源与前两个信宿之问已经用过的链路的容量进行这样操作的原因是，传统的路由算法认为网络中传输的信息是不能叠加的，只能进行存储转发如此继续下去，总可以找到信源与所有信宿之间的路径，建立起一点到多点的多播树可以看出，通过上述方式建立起的多播树，会导致信源与第二个及其后面所有信宿之间的路径都不是以它们之间的最大流进行传输的，最终导致多播通信可以实现的传输容量，远远小于最大流最小割定理所确定的容量上限1 3 1 网络编码的提出1 3 网络编码的发展历史与现状正是针对多播通信技术的上述局限，网络编码应用而生，它可以用来实现由最小割最大流定理给定的一个通信网络的容量上限2 0 0 0 年，香港中文大学的a h l s w e d e 等人【8 l 在i t 上发表了一篇题为“网络信息流”的文章，提出了“网络编码”这一概念，该理论允许中问节点在转发信息前对输入信息流进行编码，从而实现网络多播容量的极限一个通信网络可以用有向图来表示，根据图论中最大流最小割定量可知，一个网络可以传输的最大流量等于其最小割但传统的存储转发式路由方式，并不能实现网络的最大流传输，所以它并不是最佳的a h l s w e d e 等人指出，没有必要对路由节点的功能加以限制，即允许对其接受到的信息先进行编码后再传输出去在6多播网络编码算法研究接受端，目的节点通过一定的译码算法译出所需的信息，则可以大大提高网络的传输速率，充分利用网络中的链路资源，从而实现最大流最小割定理给定的信息传输速率上限我们通过一个简单的例子对网络编码的基本思想进行解释，参考图1 2 所示的通信网络：图1 2 网络编码基本原理我们以图1 2 所示的单信源双信宿的蝴蝶网络 9 1 来说明网络编码的基本原理信源为s ，信宿为，r ，；根据c t 最大流最小割定理【5 】该组播的最大流为2 ，即理论上信宿 和，：能够同时收到信源s 发出的2 个单位的信息假设各条链路为无差错无延时链路，且各条链路上信息的传输速率为l b i t 单位时间图1 2 ( a ) 表示的是传统的基于路由的传输方法，节点形执行存储或转发操作显然，无论节点转发b 。或6 ：，均不能使信宿和f ：同时收到6 。和b 2 图1 2 ( b ) 表示的是网络编码方法，节点形对输入的信息进行网络编码( 模二加) 操作，然后将编码的结果b 。ob ：发送至输出链路w x ，最后到达信宿，。和，2 当信宿，l 收到6 。和b io6 2 后，通过译码操作就能获取b l 和b 2 ( b 2 = b io ( 6 l ( gb 2 ) ) 同样，信宿t 2 也可同时收到b l 和b ，因此网络编码实现了该组播传输的最大理论传输容量第一章绪论71 3 2 网络编码理论的建立与发展2 0 0 0 年，a h l s w e d e 在“网络信息流”中首次提出“网络编码”这一概念时指出，当符号域足够大时，通过网络编码，信源可以以接近信源与任何信宿之间最小割的速率多播信息到所有信宿1 8 j a h l s w e d e 仅给出网络最大信息传输速率的存在性证明，并没有给出具体的网络编码实现方式2 0 0 3 年，l i ，y e u n g 和c a i 提出，在单信源多信宿的多播网络中，线性网络编码可以实现多播传输的最大传输速率【l 们他们给出了一个线性编码多播( l c m )算法l c m 算法的编码规则是这样的：为每一个节点分配向量空间，为每一个边分配向量，它们满足一定的关系通过边向量和节点上的信息向量相乘对信息编码，在信宿节点处使用逆矩阵解码l c m 算法虽能实现多播传输的最大传输速率，但算法复杂度高，不适合用于实际网络中2 0 0 2 年，k o e r e r 等1 1 1 , 1 2 j 提出基于代数结构的网络编码算法，他将有限域上的多项式法用到网络编码的研究中，将寻找编码系数的方法简化成寻找多元多项式的非零解问题，为网络编码理论研究提供了有效的代数研究工具但是，该算法是一种指数时间算法，算法复杂度较大2 0 0 3 年，s a n d e r s 等和j a g g i 等人同时提出实现网络编码的多项式时间算法1 1 3 , 1 4 1 该算法在网络编码中考虑多播路由问题，在从源点到各终端节点传输信息之前，先通过一种简单的路由算法选取源节点到各个信宿节点的传输路径该算法较前面的指数时问算法，复杂度大大降低2 0 0 3 年，t h o 等给出了随机网络编码算法1 1 5 , 16 1 该算法在不知网络拓扑的情况下，在有限域中随机选择符号做编码系数，并证明当有限域足够大时，编码失败的概率就很低该算法虽然简单，但所需的编码符号域较大，编译码运算复杂度较高本文将在第三章给出上面所述的三种经典的网络编码算法即指数时间算法、多项式时间算法及随机编码算法正如上文所示，网络编码最初的研究主要针对多播网络传输及其编码算法、编码算法所带来的传输速率的提高程度等此外，关于网络编码和别的方面结合的研究也很多如无线网络中网络编码的研究2 4 1 、基于网络编码的路由算法的研究、网络编码与纠错码的结合1 1 s , 1 9 】、网络编码与加密体制的结合以及网络编码的实际应用研究【2 0 】等等另外，人们对网络编码的性能做了大量研究【2 0 , 2 1 , 2 2 , 2 3 , 2 5 1 研究表明，网络编码除了能够提高系统的容量外，在负载均衡、在数据压缩、减少传播时延、降低节点能耗、提高网络建壮性及信息安全等方面都有重要的应用前景本文在2 3 节中通过例子给出网络编码的性能分析网络编码的提出仅十年，关于网络编码的研究还有很多东西去做，网络编码8多播网络编码算法研究理论有待于进一步发展和完善关于多信源网络编码问题、非线性网络编码算法、有时延网络中网络编码即网络卷积编码研究以及网络编码的应用研究等等都是比较困难的研究方向，网络编码是当今通信领域的研究热点之一1 4 本文主要内容及安排本文主要做了三方面的工作：对现有网络编码算法进行了深入研究；对g e n e r i c线性网络编码算法进行了改进，提出一种改进的多播网络编码算法；对i p 多播进行了改进，提出了一种基于最短路的网络编码多播路由算法全文共分五章，具体内容安排如下：第一章简要介绍了网络编码的研究背景，即计算机通信网络的发展过程、多播通信技术，接着重点回顾了网络编码的提出、发展和现状第二章简要介绍了网络编码中用到的数学思想，系统介绍了网络编码的基本原理，最后通过两个例子详细给出了网络编码的性能分析第三章深入研究了现有的几种经典的网络编码构造算法，它们是指数时间算法、多项式时间算法和随机网络编码算法第四章在深入研究g e n e r i c 线性网络编码算法的基础上，结合离散路由的使用，对其进行了改进，提出了一种改进的多播网络编码算法，并给出了算法的合理性证明和复杂度分析第五章提出了一种基于最短路的网络编码多播路由算法，该算法与现有编码模式一起，能够构成完整的网络编码多播传输方案然后通过仿真试验，将多播路由算法与i p 路由算法之间的性能进行了比较最后是本文的结束语、致谢、参考文献以及作者在攻读硕士学位期间的主要研究成果第二章网络编码概述9第二章网络编码概述本章简要介绍了网络编码中用到的数学思想，系统介绍了网络编码的基本原理，最后通过两个例子详细给出了网络编码的性能分析2 1 网络编码中的数学思想对于一个实际的通信网络，可以采用一个有向图加以描述和研究有向图中的节点表示一台主机或者路由器，图中的一条边表示实际中的一条端到端的通信链路这里首先给出有向图等的基本概念【5 6 】2 1 1 有向图、网络流图、割、流定义2 1 ( 有向图) ：一个有向图g 是由一个非空有限集合y ( g ) 和v ( c ) 中某些元素的有序对集合e ( g ) 构成的二元组，记为有向图g = 缈( g le ( g ) ) 其中y ( g )称为图g 的节点集，y ( g ) 中每一个元素称为该图的一个节点；e ( g ) 称为图g 的链路集，e ( g ) 中每个元素称为该图的一条链路在不引起混淆的情况下，省略记号y ( g ) 和e ( g ) 中的g ，分别记节点集、链路集为v 和e ，而记有向图为g = 缈，e ) 若对于图g = 缈7 ，e ) 和g = 缈，e ) ，有v v ，e e ，则称图g 是图g 的子图有向链路用e = u ，1 ，) e 表示，这里甜，是网络中的两个节点链路p = 0 ，)的头用，= 办p 耐g ) 来表示，尾用u = 胁甜g ) 来表示如果w = t a i l ( 1 ) ，称链路，是节点w 的输出链路，记f l z l o u t ( w ) ；如果w - h e a d ( 1 ) ，则称链路，是节点w 的输入链路，记作，咖( w ) 称源节点的输出链路为源链路，接收节点的输入链路为终端链路定义2 2 ( 网络流图) ：若一个有向图g = 缈，e ) 仅有一个源点和一个( 或多个)1 0多播网络编码算法研究汇点，且有向图中的每一条链路( f ，) 对应着一个非负数如，则称凡为该链路的容量，称该有向图为网络流图5 1 图2 1 给出了一个具有一个源点j 和一个汇点，的网络流图，图中各条边上的数字为该网络流图各边的容量图2 1 一个网络流图下面介绍网络流图中割和流1 5 , 6 1 的概念：定义2 3 ( 割) ：网络流图g 的顶点集为v ，k 和为y 的两个子集，且ku = v ，kn = ，则图g 中节点集k 到节点集的一个割表示为c u t ( v i ，) = p e ：h e a d ( e ) = 吒，t a i l ( e ) = k 在这个集合c 斫( k ，) 中，把从k 到的链路的容量之和叫做这个割的容量，用v c u t ( v i ，) 表示如图2 1 ，虚线表示信源j 和信宿t 的一个割，割的容量为v c u t ( s ，f ) = 2 + l “= 7 显然，对于一对节点，不同的割对应的容量可能不同定义2 4 ( 流) ：对于网络流图g ，每一条链路o ，) 都给定一个非负数乃，这一组数满足下列条件时称为该网络的可行流，用f = ：( f ，) e j 表示：( 1 ) 每一条链路( f ，j ) ，有r 矿( 2 ) 除源点j 和汇点t 以外的所有节点f ，恒有：兄，= 吒上式表示中间节点i 的流量守恒，即输入量与输出量相等( 3 ) 对于源点s 和汇点t 有：c 。= 巳= wfjw 称作该网络流的流量，且从源点s 流出的总量等于流入收点t 的总量一，j参、a9 ，小r 6b，、，、一。、j、，2 。卜。一。，j，、rj 、。工o第二章网络编码概述当乃= 心时，称链路o ，) 饱和，表示流f 对该链路已饱和该网络流图的最大流指从源点s 向收点，发送的流量w 的最大值，用m a x f l o w ( s ，) 表示定理2 1 ( 最大流最小割定理) 0 5 l ：在网络流图g = 缈，e ) 中，源点s 向收点，发送信息，其流量w 的最大值等于所有s 与，之间割容量中的最小值，即m a x ：a o w ( j ，) = m i nv c u t ( s ，r )f o r d f u l k e r s o n 标号法【5 】给出上述定理的一个构造性证明，证明的过程也是寻找最大流的过程2 1 2 有限域、偏序、全序在抽象代数中，域是一种可进行加、减、乘和除( 除了除以零之外) 运算的代数结构域的概念是数域以及四则运算的推广定义2 5 ( j 或) 1 2 7 1 ：非空集合f 上定义了两种运算，记为扩，+ ，) ，当这两种运算满足如下八条运算性质时，即：1 ) 在加法和乘法上封闭：即对所有属于f 的a ，b ，口+ 6 和a 木6 属于f ；2 ) 加法和乘法符合结合律：对所有属于f 的口，b ，c ，o + 6 ) + c = 口+ ( 6 + c ) ，0 毒6 ) 幸c = 口幸( 6 宰c ) ：3 ) 加法和乘法符合交换律：对所有属于f 的a ，b ，口+ 6 = b + 口，a b = b 枣口；4 ) 符合乘法对加法的分配律：对所有属于f 的口，b ，c ，口+ ( 6 + c ) = g 事6 ) + g 奉c ) ；5 ) 存在加法单位元：在f 中有元素o ，使得所有属于f 的a ，a + 0 = 口；6 ) 存在乘法单位元：在f 中有不同于o 的元素l ，使得所有属于f 的口，a 掌l = a ：7 ) 存在加法逆元：对所有属于f 的口，存在一口使得口+ ( _ 口) = 0 ；8 ) 存在乘法逆元：对所有口0 ，存在元素a 。1 使得a 口= l ；则称定义了两种运算的该集合f 为域，记作域( f ，+ ，枣) 注：其中o l 的要求排除了没有什么意义的只由一个元素组成的域定义2 6 ( 有限域) ：包含有限个元素的域被称为有限域，也称为g a l o i s 域( 伽罗瓦域) 1 2多播网络编码算法研究定理2 2 1 2 7 i ：任意一个有限域的元素个数是一个素数g 的乘方，一般记作c 定理2 3 ：任意一个元素个数是素数p 的域都同构于扩，+ ，) ，其中f = 0 1 ，p 一1 ) ，a + b = 口+ b ( m o d p ) ；a * b = 1 b ( m o d p ) ，记作卯0 ) 下面介绍序例的概念：定义2 7 ( 偏序) ：设彳是一个非空集，r 是彳上的一个关系，若关系r 是自反的、反对称的、和传递的，即：( 1 ) 对任意的口彳，0 ，口) r ；( 2 ) 若q ，6 ) r 且( 6 ，口) r ，贝a = 6 ；( 3 ) 若q ，6 ) r ，( 6 ，c ) r ，则g ，c ) r ；则称r 是集合么上的偏序关系带偏序关系的集合彳称为偏序集或半序集若r 是集合彳上的一个偏序关系，我们用口b 来表示g ，b ) er 定义2 8 ( 全序) ：在集合a 中，如果对于任意口a ，b a ，有g ，6 ) r或o ，口) r ，即a 中的每对元素都满足关系只，则集合彳上的偏序r 是全序的或线性序的全序的集合称为全序集合、线序集合或链在有向无环图中对节点集引入偏序“1 ，当且仅当该网络图中存在一条从z ，到1 ，的链路在有向无环图中我们称这样的扩展后的全序为一个编码序即在编码序s 中，对ve e ，可以得到：t a i l ( e ) h e a d ( e ) 同样，在有向无环图中对链路集也可以引入偏序当存在节点r 且满足d i n 仃) ，e o u t ( t ) 时，称链路d 和e 存在偏序关系d e 第二章在介绍网络编码的数学描述时将用到链路之间的拓扑序定理2 4 ：一个偏序总能扩展成一个全序第二章网络编码概述2 2 1 网络编码模型2 2 网络编码基本原理定义2 9 ：一个点到点的通信网络由如f 五部分组成：1 ) 有向图g = ( y ，e ) ，其中矿表示节点集或用户，e 表示表示边集或链路集；2 ) 在边集上定义容量c ：e r + ；3 ) 消息源q = 正，x ：，x 。 ；4 ) 函数口： ，一2 口，v v v ，其中2 e = 臼：asq ) ，即为q 的幂集；当且仅当x ，口d ) 时，我们称消息置接入节点v ，或者称节点，产生消息置如果a o ) m ，则称节点，为信源节点，信源节点集合记为 ；图2 2 是一个q = i x 。，x ：，x ，) ，a o ) = i x ：，x ，) 的信源节点的示意图x lo图2 2 信源节点示意图5 ) 函数卢：1 ，专2 q ，当且仅当x ，p ) 时，我们称节点，需要消息置如果卢o ) ，则称节点y 为信宿节点，信宿节点集合记为t 本文主要研究单信源无环网络，无环指网络图中不含有圈，单信源指lq i = 1 ，即q = x ) 对于单信源无环网络，当通信网络中含有多个信源节点时，可以通过设立一个虚拟信源节点的方法，将这多个信源节点合并为单一的信源节点，并用s 标记，如图2 3 所示1 4多播网络编码算法研究图2 3 虚拟信源：肖点引入示意图信源节点以外的其他节点称为非信源节点，同前述一样，用觑( s ) 表示信源节点s 的入边，因信源节点没有入边，故称其为假想信道只有信源节点有假想信道假想信道终止于信源节点，但没有始发点假想信道的个数标记为c o 如图2 4 给出了依附于信源s 的具有两条假想信道( 即t o = 2 ) 的无环网络，又称其为蝴蝶网络【9 1 图2 4 附带假想信道的蝴蝶网络为简单起见，对通信网络进行如下假设：( 1 ) 选择时间单位，使网络g 中每条链路的容量是1 比特单位时间对于任意一条链路，若其容量为，( ，为整数) ，则将它分成，条容量为l 比特单位时间的并行链路( 2 ) 每条链路具有相同的时延如果时延为零，则称该网络为无时延网络，无时延网络只适用于无环网络第二章网络编码概述2 2 2 网络编码的数学描述通信网络中信息传输及编码过程简述如下：可以用有限域f 中的元素表示一个数据单位，例如，当数据单位是l 比特时，f = 卯( 2 ) 一条信息x 包含个数据单位，可以用维行向量x f 表示信源节点s 产生信息向量x ，通过符号的形式将该信息通过输出信道发送出去网络上的信息传输通过在网络中每条信道p 上传输一个符号z g ) f 得以实现非信源节点不一定能接收足够多的信息来确定信源信息x 的值网络节点具有编码功能，将所有输入信道上的接收符号进行编码，然后将编码后的符号发往输出信道以下给出网络编码严格的数学定义，本文的研究范围只限于有向无环网络，故下文的定义都是指有向无环网络中网络编码的定义后文中遇到不再说明定义2 1 0 1 9 ( 网络编码的局部描述) ：令f 是一个有限域，是一个正整数有向无环通信网络中c o 维，f 取值的网络编码，由一个局部编码映射，即疋：f i 加( 7 l f构成，其中，该映射作用在每一个节点丁和节点丁的每条输出信道e o u t ( t ) 上网络编码的局部编码映射确定了每一条信道p 上的传输符号z g ) ，网络的非循环拓扑为局部编码映射提供了上流到下流的结构定义2 1 0 并没有明确给出信道p 上的传输符号z g ) 的具体值下面给出网络编码的全局描述，它和定义2 1 0是等价的定义2 1 1 1 9 1 ( 网络编码的全局描述) ：令f 是一个有限域，缈是一个正整数有向无环通信网络中国维，f 取值的网络编码，对网络中的每条信道e ，包含一个局部编码映射：乞：f i 伽( 7 l 专f 和一个全局编码映射：z ：f 。jf ，满足以下条件：( 1 ) 对每个节点丁和其输出信道p o u t ( t ) ，z g ) 唯一由( z g ) ，d 伽仃确定，疋是( 五g ) d 如仃) ) hz g ) 的映射；( 2 ) 对于0 3 个假想信道e ，映射以是有限域f 到个不同坐标的投影1 6多播网络编码算泫研究f 向举例来理解上述定义例2 1 【9 l ：对图2 4 所示的蝴蝶网络进行网络编码假定信源s 发送信息向量x = 0 ，b ：) ，设x 陋( 2 ) 】2 ，下面给出采用网络编码时，图2 4 各个信道上的全局编码映射：z g ) = b i ，f o re = o s ，s t ，邢，吖z g ) = b 2 ，f o rp = o s ，s u ，u w ，泥z g ) = b io6 2 ，f o rp = w x ，脬，勉其中o s 和o s 表示图2 4 中的两条假想信道相应的局部编码映射为：r ( 6 。，b ：) = b 。，疋u ( 6 。，b ：) = b ：，o ) = 砖( 6 。) = 6 。，o ：) = 砬( 6 ：) = b ：，k w x ( 6 b ) = b o6 ：，l 也0 6 ：) = 砭( 6 l0 6 ：) = b 。0 6 ：通信网络中信息传输的延迟包括节点处理延迟和信道延迟，其中节点处理延迟占主导地位，线性编码函数因其简单快速，得到了最初研究和广泛应用，下面介绍线性网络编码函数当全局编码映射z 线性时，则存在维列向量以，使得信道p 上的传输符号z g ) = x 以，其中x 为c o 维行信源信息向量类似地，当局部编码映射疋( e o u t ( t ) ) 线性时，则存在l 砌仃) i 维列向量k 。，使得链路p 上的传输符号艺) = y k e ，其中y 为节点r 接收到的i 砌仃】维符号行向量，y f i 胁刑当存在节点殂满足d l n ( t ) ，e o u t ( t ) 时，信道d 和e 称为邻接信道当通信网络采用网络编码，所有局部和全局编码映射都是线性时，该网络编码就称为线性网络编码线性网络编码最初被研究者称为线性编码多播【1 0 l ( 1 i n e a rc o d em u l t i c a s t ，l c m ) 定义2 1 2 1 9 1 ( 线性网络编码的局部描述) ：令f 是一个有限域，是一个正整数有向无环通信网络中c o 维，f 取值的线性网络编码，对每对邻接信道0 ，e ) ，存在一个标量l 蠢，称为局部编码核节点丁上的局部编码核构成一个第二章网络编码概述1 7l i ( t ) i l d 川仃】维矩阵k r = k 。l 。胁( r 胁咖( r ) 矩阵瞄的结构暗含了通信网络中所有链路之间的一个拓扑序定义2 1 3 1 9 i ( 线性网络编码的全局描述) ：令，是一个有限域，是一个正整数有向无环通信网络中维，f 取值的线性网络编码，对每对邻接信道p ，e ) ，存在一个标量吒以及对每条信道e ，对应一个国维列向量z ，满足以下条件：( 1 ) 以。d 。加( ，) k ，。厶，其中e o u t ( t ) ；( 2 ) 个虚信道e 砌 ) 的向量以，构成了向量空间f 的自然基底其中，以称为信道e 的全局编码核( 向量) 引理2 1 ：定义2 1 3 可以作为定义2 1 1 的推广证明：可以按如下方式由定义2 1 1 得到定义2 1 3 中的条件( 1 ) 设节点丁的输出信道e 上传输的符号为：z g ) = 幻，z g ) = ，。g 厶) = x i 匕，厶i式( 2 1 )d e l n ( ? ) d e l n ( r )，加仃)其中，式( 2 1 ) 中的元g ) = x 厶由全局编码核向量的定义得知，类似的有：z g ) = x z式( 2 2 )由式( 2 - 1 ) 和式( 2 1 ) 相等，得定义2 1 3 中的条件( 1 ) ，即丘= 拈胁( r ) 吒。厶，其中p o u t ( t ) 引理2 2 ：对于有向无坏通信网络中的维，f 取值的网络编码，如果所有的局部编码映射是线性的，则所有的全局编码映射也是线性的相应地，如果所有全局编码映射是线性的，则局部编码映射也是线性的该结论的证明可以参考文献【9 】假定信源产g g 提升网络吞吐量 提高带宽利用率 均衡网络负载我们分别以如下两个图例来加以说明例2 5 【8 ，2 9 】：( a )( c )包包蚊6 , 6 2- ，岛6 2l 葛如2 j i ( d )( e )图2 6 单信源三信宿网络嬲妣+三第二章网络编码概述2 1分析图2 6 所示的单信源三信宿网络，将分别得到网络编码对带宽的节省、对吞吐量的提升以及对网络负载的均衡首先，在图2 6 ( b ) 中，若允许网络编码，共9 条链路，每条链路传输l b i t 信息，单位时间内信宿节点，l ，3 均收到符号6 l 和6 2 若网络中不允许使用网络编码时，见图2 6 ( 0 ，为了使三个信宿节点都收到6 l 和6 2 ，至少还得多发送l b i t 信息由此我们看到，即使简单的网络编码，也能够节省1 0 的带宽其