（通信与信息系统专业论文）网络编码理论及其应用的研究.pdf

摘要 不同于传统路由方法，在多播通信网络中，通过网络编码可使信息传输速率达 到网络的最大流量，从而编码的方式优于路由的方式，网络编码的诞生和发展为 网络信息传输指明了一个新的研究方向。结合现有的理论成果和实践经验，将网 络编码技术应用到现有的通信技术以获得更好的性能，正日益成为近年来的研究 热点之一。 本文对网络编码理论及其应用进行了深入研究，获得了几个关键性的研究成 果，主要概括为： ( 1 ) 系统地总结了网络编码的基本原理；详细分析了指数时间算法、多项式时 间算法，以及网络编码可行时所需有限域的大小。 ( 2 ) 给出了一种网络编码的多播路由算法，系统地分析了该算法能减少资源消 耗以及提高负载均衡的原因。为有效地恢复链路传输错误，给出了一种基 于x o r 选择重传a r q 的网络编码多播路由算法。 ( 3 ) 研究了最小子树图的性质，提出了一种最小子树图搜索算法，可在最小子 树图上进行有效地网络编码，所有的网络编码问题简化为搜索多播网络的 最小子树图问题。 ( 4 ) 利用最大距离可分码的已有成果，分别给出k 冗余多播网络、存在链路故 障多播网路的链路码字分配算法以及所需要的最小有限域：基于网络编码 信息线性组合方法，给出了一种无线传感器网络数据快速采集算法。 ( 5 ) 针对两信源通过中继节点进行信息交换的网络模型，提出了一种星座映射 的物理层网络编码算法，可在不损失性能的前提下降低中继节点的能量消 耗。 ( 6 ) 分析了网络编码在协作分集中的应用，给出了复数域网络编码中一种并行 中继优化设计方案，可显著降低目的节点的检测复杂度以及信源符号的传 输时延。 关键词：网络编码多播网络路由算法最小子树图星座映射协作分集 a b s t r a c t o t h e rt h a nt r a d i t i o n a lm u l t i c a s tr o u t i n ga l g o r i t h m s ，t h en e t w o r k i n f o r m a t i o nf l o wc a n a p p r o a c ht h em a x f l o wo f m u l t i c a s tn e t w o r kb ya d o p t i n gn e t w o r kc o d i n g s o ，c o d i n gi s b e t t e rt h a nr o u t i n g t h ei n v e n t i o na n dd e v e l o p m e n to fn e t w o r kc o d i n gp o i n to u ta n e w r e s e a r c _ hf i e l df o ri n f o r m a t i o nt r a n s m i s s i o n c o m b i n i n gt h et h e o r e t i ca n dp r a c t i c a lf i u i t s a v a i l a b l e ，n e t w o r kc o d i n gc a l lb ea p p l i e dt ot h ee x i s t i n gc o m m u n i c a t i o nt e c h n i q u et o 0 b t a i nb e t t e rp e r f o r m a n c e ，w h i c hh a si n s p i r e dm a n ya t t e n t i o n s i nt h i sd i s s e r t a t i o n ，t h et h e o r yo fn e t w o r kc o d i n ga n di t sa p p l i c a t i o na l es t u d i e d s e v e r a lr e s u l t sa r eo b t a i n e d t h e ya r e ( 1 ) t h ep r i n c i p l e so fn e t w o r kc o d i n ga l es y s t e m a t i c a l l ys u m m a r i z e d t h ee x p o n e n t t i m ea l g o r i t h m sa n dp o l y n o m i a lt i m ea l g o r i t h m sa l ea n a l y z e d ，a n dt h e nt h ef i n i t e f i e l dr e q u i r e di sg i v e n ( 2 ) am u l t i c a s tr o u t i n ga l g o r i t h mw i t hn e t w o r kc o d i n gi sp r e s e n t e d t h er e a s o nt h a t t h i sa l g o r i t h mc a nd e c r e a s er e s o u r c ec o n s u m p t i o na n di m p r o v el o a db a l a n c ei s s y s t e m a t i c a l l ya n a l y z e d t oh a n d l i n gt r a n s m i s s i o ne r r o r so fd a t al i n k ，am u l t i c a s t r o u t i n ga l g o r i t h mb a s e d o nx o rs e l e c t i v er e p e a ta r qi sp r o p o s e d ( 3 ) b a s e do nt h ec h a r a c t e r i z a t i o n so fm i n i m a ls u b t r e eg r a p h s ，a na l g o r i t h mt os e a r c h m i n i m a ls u b t r e eg r a p h si sp r e s e n t e d t h e nn e t w o r kc o d i n gc a nb ee f f e c t i v e l y c o n s t r u c t e di nm i n i m a ls u b t r e eg r a p h s ，a n da l lt h en e t w o r kc o d i n gp r o b l e m sc a n b ee q u i v a l e n tt os e a r c ht h em i n i m a ls u b t r e eg r a p h s ( 4 ) u s i n gs o m er e s u l t so fm a x i m u md i s t a n c es e p a r a b l ec o d e sa v a i l a b l e ，m e t h o d sf o r c o n s t r u c t i n gc o d e si nk r e d u n d a n tm u l t i c a s tn e t w o r ka n d m u l t i c a s tn e t w o r k sw i t h l i n kf a i l u r ea r er e s p e c t i v e l yp r o p o s e d t h em i n i m a lf i n i t ef i e l dw h i c hi se n o u g ht o i m p l e m e n tn e t w o r kc o d i n gf o rd i f f e r e n tm u l t i c a s tr a t e i so b t a i n e d i nw i r e l e s s s e n s o rn e t w o r k b a s e do nt h el i n e a rc o m b i n a t i o nm e t h o do fn e t w o r kc o d i n g ，a n a l g o r i t h mf o rf a s t e rd a t ac o l l e c t i o ni sp r e s e n t e d ( 5 ) f o rt h en e t w o r kw i t ht w os o u r c e se x c h a n g i n gi n f o r m a t i o nt h r o u g hr e l a yn o d e ，a p h y s i c a l 1 a y e rn e t w o r kc o d i n gm e t h o dw i t hc o n s t e l l a t i o nm a p p i n g i sg i v e n t h i s m e t h o dc a nr e d u c ee n e r g yc o n s u m p t i o ni nr e l a yn o d ew i t h o u tp e r f o r m a n c e d e g r a d a t i o n ( 6 ) t h ea p p l i c a t i o no fn e t w o r kc o d i n gi nc o o p e r a t i v ec o m m u n i c a t i o ni sa n a l y z e d t h e n ，a no p t i m i z a t i o nd e s i g nm e t h o df o rp a r a l l e lr e l a y si nc o m p l e x f i e l dn e t w o r k c o d i n gi sp r o p o s e d t h i sm e t h o dc a nd e c r e a s e t h ed e t e c t i o nc o m p l e x i t yo f d e s t i n a t i o nn o d ea n dt h et r a n s m i s s i o nd e l a yo fs o u r c es y m b 0 1 k e y w o r d s ：n e t w o r kc o d i n g m u l t i c a s tn e t w o r k r o u t i n ga l g o r i t h m m i n i m a ls u b t r e eg r a p hc o n s t e l l a t i o nm a p p i n g c o o p e r a t i v ed i v e r s i t y 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人签名：量蔓童 日期澌弓i j 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制于段保存论文。 本人签名：叁盏 导师签名： 日期嘶弓i ) 日期嘶；1 1 第一章绪论 第一章绪论 本章茂先简单介绍计算机通信网络及其体系结构；接着介绍计算机通信网络 中所采用的多播通信技术，综述了多播通信技术的实现方式及局限性；然后着重 论述网络编码的提出发展以及当前研究的热点问题。最后给出了本文的研究范 围以及全文的章节安排。 1 1 计算机通信网络 1 1 1计算机通信网络的产生和发展 2 0 世纪5 0 年代中期，计算机技术开始和通信技术相结合，从此计算机网络经 历了一个从简单到复杂的演变过程，大体上可分为以下四个阶段【l 】：面向终端的计 算机网络、计算机计算机网络、开放式标准化的计算机网络以及目前的网络互联 与高速网络技术。 第一阶段的计算机网络大体上从2 0 世纪5 0 年代中期至6 0 年代中期，实际上 是以单个计算机为中心的远程联机系统。这样的系统中除了一台中心计算机，其 余的终端都不具备自主处理的功能。系统中主要存在的是终端和中心计算机间的 通信，为了更明确地与后来出现的多台计算机互联的计算机网络相区分，称为面 向终端的计算机网络。 第二阶段的计算机网络大体上从2 0 世纪6 0 年代末至7 0 年代末，它是多台计 算机通过通信线路互联起来为用户提供服务，即计算机计算机网络。它和以单台 计算机为中心的远程联机系统的显著区别在于这里的多台计算机都是具有自主处 理能力的，它们之间不存在主从关系。这样的多台计算机互联的网络才是我们目 前常称的计算机网络。这种系统中，终端和中心计算机问的通信已改变为计算机 和计算机之间的通信，用单台中心计算机为所有用户需求服务的模式被大量分散 而又互联在一起的多台计算机共同完成的模式所替代。 第三阶段的计算机网络大体上从2 0 世纪8 0 年代初至9 0 年代初，是开放式标 准化的计算机网络。换句话说，它具有统一的网络体系结构、遵循国际标准化的 协议。标准化将使得小同的计算机能方便地互联在一起。标准化还将带来大规模 生产、产品v l s i 化和成本降低等一系列的好处。 1 9 9 3 年9 月，美国政府发布了名为“国家信息基础设施( n a t i o n a li n f o r m a t i o n i n f r a s t r u c t u r e n i i ) 行动计划 的文件。n i l 俗称为信息高速公路。该文件的核心 2 西安电子科技大学博士学位论文：网络编码理论及其应用的研究 内容就是建设一个覆盖全国的高速宽带通信和计算机网络，其功能就类似于传输 物流的高速公路，不同在于现在传输的是信息流。随后又有人提出建立全球信息 基础设施( g l o b a li n f o r m a t i o ni n f r a s t r u c t u r e ，g i i ) 。这一切在全球范围内极大地推动 了计算机网络及其应用的发展，使得计算机网络也随着计算机的发展进入了一个 网络计算( n e t w o r kc o m p u t i n g ) 的新阶段。所谓“网络计算”，可以理解为以网络 为中心的计算( n e t w o r kc e n t r i cc o m p u t i n g ) 或者以网络为基础的计算 ( n e t w o r k b a s e dc o m p u t i n g ) 。在这个新阶段中任何信息处理，即计算，几乎都离 不开网络。事实上，现在几乎所有的计算机都必须以某种形式联网，以共享信息 或协同工作，否则就无法充分发挥其效能。这也就是s u n 公司早就提出的“网络 就是计算机( n e t w o r ki sc o m p u t e r ) 的e l 号的含义。在这个新阶段中，计算机网 络的发展有若干引人注目的方向，如迅速向高速宽带发展、网络的应用多媒体化 并深入到人们社会生活的各个方面。 1 1 2计算机通信网络的体系结构 ( 1 ) 开放系统互联协议的体系结构 国际标准化组织( i s o ) 将协议体系结构模型分为七个层次：应用层、表示层、 会话层、运输层、网络层、数据链路层和物理层，并将它作为开发协议标准的框 架。该模型称为开放系统互联( o s i ) 参考模型1 2 1 。 各层的主要功能如下： 第一层：物理层。在由物理通信信道连接的任一对节点之间，提供一个传送比 特流( 比特序列) 的虚拟比特管道。在发端它将从高层接收的比特流变成适合于 物理信道传输的信号，在收端再将该信号恢复成所传输的比特流。 第二层：数据链路层。数据链路层负责数据块( 帧) 的传送，并进行必要的同 步控制、差错控制和流量控制。有了第二层的服务，它的上层可以认为链路上的 传输是无差错的。 第三层：网络层。网络层提供系统之间的连接，它负责将两个终端系统经过网 络中的节点用数据链路连接起来，组成通信通路，实现两个终端系统之间的数据 透明传送。 第四层；运输层。运输层利用低三层所提供的网络服务向高层提供可靠的端到 端的透明数据传送，可以看成是用户和网络之间的“联络员”。 第五层：会话层。会话层负责控制两个系统的表示层实体之间的对话。它的基 本功能是向两个表示层实体提供建立和使用连接的方法，这种表示层之间的连接 就叫做“会话。 第六层：表示层。表示层负责定义信息的表示方法，并向应用程序和终端处理 第一章绪论 3 一 程序提供一系列的数据转换服务，以使两个系统用共同的语言来进行通信。 第七层：应用层。应用层是最高的一层，直接向用户提供服务，它为用户进入 o s i 环境提供了一个窗口。应用层包含了管理功能，同时也提供一些公共的应用程 序。 ( 2 ) t c p f l p 协议的体系结构 t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e r a c tp r o t o c 0 1 ) 协议族【2 】是在美国国防 远景研究规划局( d a r p a ) 所资助的实验性分组交换网络a r p a r n e t 上研究开发 成功的。t c p 以p 的通信任务组织成五个相对独立的层次：应用层、运输层、互联 网层、网络接入层、物理层。 t c p i p 协议重点强调应用层、运输层和互联网层，而对网络接入层和物理层 只要求能够使用某种协议来传送互联网层的分组。 网络接入层关心的是如何在一个网络中两个端系统之间传送数据的问题。它主 要解决一个端系统( 计算机) 和它连接的网络之间的数据交换。发端计算机必须 给网络提供目的计算机的地址，以便网络将数据传到相应的目的地。发端可以充 分利用网络提供的服务。如果两台设备连在两个不同的网络上，要使数据穿过多 个互联的网络正确地传输，这是互联网络层要完成的功能。该层采用的协议称为 互联网协议( i p ) ，它提供跨越多个网络的选路功能。 t c p i p 协议族中的运输层采用两种不同的协议：t c p 和u d p 。t c p 为应用程 序之间的数据传输提供可靠连接，它是面向连接的传输控制协议。u d p ( u s e r d a t a g r a mp r o t o c 0 1 ) 为应用层提供无连接的服务，它并不保证一定传到，也不保证 按顺序传输以及不重复传送。 t c p d p 协议族中应用层的主要协议有：文件传送协议( f t p , f i l et r a n s f e r p r o t o c 0 1 ) 、简单邮件传送协议( s m t p , s i m p l em a i lt r a n s f e rp r o t o c 0 1 ) 、远程登录协 议( t e l n e t ) ，以及近几年发展起来的域名服务( d n s ，d o m m nn a m es e r v i c e ) 、 网络新闻传送协议( n n t p , n e t w o r kn e w st r a n s f e rp r o t o c 0 1 ) 和超文本传送协议 ( h t t p , h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) 等。 1 2 多播通信技术 1 2 1多播通信技术产生的背景 如今计算机网络飞速发展，网络功能u 益强大。网络的作用从简单的信息传 输发展到远程教学、视频会议、数据分发和网络游戏等。用户数据要从一个终端 发送到另一个终端，首先要确定传输路由，不同的通信方式，其路由传输方式也 4 西安电子科技大学博士学位论文：网络编码理论及其应用的研究 不同【l0 2 1 。如今网络的通信方式主要有以下几种： ( 1 ) 单播( u n i c a s t ) ：点到点的通信方式 ( 2 ) 多播( m u l t i c a s 0 - 点到多点的通信方式 ( 3 )汇播( c o n c a s t ) ：多点到一点的通信方式 ( 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 e a s 0 ：点到所有点的通信方式 一般采用d i j k s t r a 最短路算法( s h o r t e s tp a t ha l g o r i t h m ) 3 , 4 l 或者 b e l l m a n f o r d 算法 【4 ，5 】建立点到点路由，实现单播通信。广播是网络中常用的通信方式，多用于局域 网中，涉及一节点向网络中所有节点发送信息。多播是源节点同时向多个目的节 点( 不包含所有节点) 发送信息的通信方式，被广泛应用于多媒体会议、远程教育、 数据分发等领域。多播应用的普及也导致了多播主干网( m b o n e ) 【6 j 的快速发展。汇 播和多播有相似之处，多播是一点到多点通信，而汇播则是多点到一点的通信方 式。而群播的通信方式被广泛应用于网络即时游戏，在多方游戏中，需要将各自 的状态相互同步发送。在多播、汇播和群播这些通信方式中，多播是目前研究最 多，也是应用最广的网络连接方式。 1 2 2多播通信技术的实现方式 多播是信源节点向多个目的节点传输同一信息的通信方式，参与多播的所有 节点组成了一个多播组，每个节点称为多播组成员。可以通过如下三种方式实现 多播通信： ( 1 ) 以单播为基础，信源节点单独地向所有目的节点发送同样的消息，这种 方式不仅浪费带宽，而且还要求信源已知全部目的节点的完整信息； ( 2 ) 每个分组具有一张目的节点清单，当分组到达路由器时，路由器检查所 有目的节点，以确定将要用到的传输路径。路由器为所使用的每条输出路径复制 一个新的分组，每个分组中仅包含用此路径的那些目的节点。这种路由方式象各 自分组寻址一样，当若干分组必须经过同一路由时，其中一个分组负担全部费用， 其它分组则不必承担费用【7 1 。多媒体实时应用业务的出现，使得多播组的规模、业 务的特征和要求发生了很大变化，为了满足这种需求，有必要寻求网络层对多播 通信的支持，使多播技术满足多媒体实时应用的要求。 ( 3 ) 建立一棵覆盖所有多播组成员的生成树，即多播树，实现多播传输。多 播树具有以下优点：信息以并行的方式沿着树枝发送到不同的组成员，降低了信 息传递的时延；网络中需要传送的复制信息减少，而- 日信息的复制只在树权处进 行，这样能够节省网络带宽资源，提高每次多播通信时的资源利用率，并减少拥 塞，降低网络负载。 第一章绪论 5 一 多播树一般具有两种类型引，一种是有源树，另一种是共享树。有源树是多播 树中最简单的一种形式，它的根是多播信息流的来源，有源树的分支形成了通过 网络到达接收节点的分布树。有源树也具有两种形式，一种是最短路径树( s p t ： s h o r t e s tp a t ht r e e ) ，从信源节点到所有多播组成员都是通过最短路径相连。很明显， s p t 的全树费用并不一定就是最优的，这里树的费用是指树中所有链路上的费用 ( c o s t ：这里的费用是一个广义上的费用，可以根据距离、信道带宽、平均通信量、 通信开销、测量到的时延和其它因素来计算) 之和。第二种有源树是最d x s t e i n e r 树1 9 ， 在一个连通图中，给定一个节点子集，要求在图中找到一棵覆盖给定节点子集的 费用最小的生成树。s t e i n e r 树的总费用最小，但从信源到每个目的节点不一定是最 短路。在网络中的每个节点( 实际是路由器) 都具有多播功能时，求解费用最小的多 播树问题与s t e i n e r 树问题是等价的。 另一种形式的多播树是共享树或中心树( c b t ：c o r e b a s e dt r e e ) t 7 , 1 0 】，其中每个多 播组只需建立一棵多播树，其树根靠近多播组的中间部位，当发送多播消息时， 主机先将它发往树根，在由树根沿着生成树发送消息。尽管共享树并不是对于任 何源节点都是最优的，但它将每组m 棵树的存储开销降低到了一棵树，节省了大 量的存储空间。 一般要求多播服务的业务对带宽和实时性要求较高，涉及用户较多，占用的资 源也多，因此有必要优化多播路由。多播路由算法就是要寻求最优多播树，理想 有效的路由算法将设计一棵仅覆盖多播组成员的树，并体现如下特征：多播树随 着多播组成员变化动态更新；最小化节点需要保存状态信息量：避免链路和节点 的流量集中；根据费用函数优化路由。 1 2 3多播通信技术实现的局限性 多播通信主要靠在通信网络上建立多播树来实现，下面就看看一个多播树可以 实现的最大传输容且【咧。 由最大流最小割定理( m i n c u tm a x f l o wt h e o r e m ) 1 1 】可知，网络中两点之间的最 大流量可以通过最d , - 害u 来衡量；同时，实现最大流的路径可以通过最大流算法2 j 找 到。当要建立两点之间通信的时候，可以在两点之间，应用最大流算法，得到它 们之间的最大传输速率。 考虑建立一点到多点的多播树时，问题变得复杂起来。一般认为，多播树的建 立是一个n p i 洒j 题【1 3 】。一般先采用最大流算法寻找信源与一个信宿之间的最大流及 其实现的路径：然后再依次寻找信源和其它信宿之间的路径。在寻找信源与第i 个 信宿之间的路径时，在原通信网络中去掉信源与前i 一1 个信宿之间已经用过的链路 的容量( 这里i 小于信宿节点的数目) 。进行这样操作的原因是，传统的路由算法 6 西安电予科技大学博士学位论文：网络编码理论及其应用的研究 认为网络中传输的信息是不能叠加的，只能进行存储转发。可以看出，这样的多 播树的建立方式会导致信源与第二个及其后面所有信宿之间的路径都不是以它们 之间的最大流进行传输的，最终导致多播通信可以实现的传输容量远远小于最大 流最小割定理所确定的容量上限。 1 3 网络编码的发展历史与现状 1 3 1网络编码的提出 多播通信采用路由的方法无法确保信息传输速率达到最大流最小割定理所确 定的信源和信宿问的最大流量。针对多播通信存在的上述局限，2 0 0 0 年，a h l s w e d e 等人1 1 4 j 在l t 上发表了一篇题为“网络信息流”的文章，为提高多播网络的传输容 量指明了一个新的发展方向。他们从信息论的角度出发，严格证明了在单点对多 点的通信网络中，通过节点编码的方式可使信息传输速率达到网络的最大流量， 从而编码的方式优于路由的方式。( 其实从广义上来看，路由可以看成一种特殊的 编码) 编码的网络通信方式的关键是中间节点在接收和存储前面节点送来的消息 后，先对这些消息进行编码再送往下面的节点。这一发现推翻了在中间节点上对 传输的数据进行加工不会带来任何收益这一传统观点，由此给网络通信带来了根 本性的变革。 1 3 2 网络编码的蓬勃发展 考虑到线性编码的简单性和实用性，l i ，y e u n g 和c a i 在后续工作中提出了线性 网络编码i i ”，并构造了码率达到最大流量的线性码，证明了线性码的最优性。这 一工作奠定了网络编码的理论和应用基础，引起了更多人对网络编码的注意。由 于文【1 5 】的杰出贡献，l i ，y e u n g 和c a i 被授予i e e ei n f o r m a t i o nt h e o r ys o c i e t y2 0 0 5 年度最佳论文奖。 网络编码思想突破了传统数据传输的固定模式，带来了许多潜在优点： 首先，与传统的路由传输方式相比，网络编码可提高网络的信息传输速率， 增加网络的信息流量( t h r o u g h p u t ) ，这也是y e u n g 提出网络编码的主要原因。在有 向图网络中，不乏编码比路由可观地提高流通量的例子1 2 2 1 ，文献 4 7 ，4 8 通过网络 拓扑图仿真也表明编码可有效地提高多播容量。在无向图网络中，文献【2 1 】证明了 网络编码比路由最多能提高两倍的流通量。 其次，网络编码可充分利用网络上的信道，使数据传输普适化( u n i v e r s a l ) 。直 观地说，对单信源网络进行适当的编码，可使每一个节点从信源节点所收到的信 息量达到信源节点到该点的最大流。这给我们带来的好处包括： 第一章绪论 在构造网络编码及其编码器时不需知道信息接收者在网络中的具体位 置： 即使在从信源到某一节点的最大流量小于信源的信息率的情况下，在该 节点的用户也可以收到信源所产生的消息的部分信息，这样此用户就可 以利用这部分信息对信源消息作满足一定失真准则( d i s t o r t i o nc r i t e r i o n ) 的编码或列表译码( 1 i s td e c o d i n g ) ： 一局域网( 1 0 c a la r e an e t w o r k s ) 可以轻易地接入主干网上( b a c k b o n e n e t w o r k ) 【2 3 2 4 1 。 第三，网络编码可增加网络通信的鲁棒性( r o b u s t n e s s ) 和可调节性 ( a d a p t a b i l i t y ) 。经适当网络编码的数据具有同等的重要性，因此只要用户收到了 足够多( 无论来自什么地方) 的编码数据，他都可以从这些数据正确地译出所需 的消息来。这样，当部分节点处于休眠状态暂时停止发送消息时，只要有足够的 节点在工作，网络通信仍可正常进行。 最后，当网络编码应用于无线通讯网络时 2 7 , 2 8 , 2 9 , 3 0 , 3 1 , 3 2 , 3 3 , 3 4 , 1 0 4 , 1 0 7 】，不仅可以提 高信息传输率，节约传输所需能量，而且可以使节点之间在所需能量方面进行折 中( t r a d e o f f ) 3 1 , 3 2 】。值得指出的是，在文献 3 4 1 中提出了一个在无线a dh o c 网络上 求得最小能量多播( m u l t i c a s t ) 编码的多项式时间算法，而构造这种网络的路由算 法所用的最小能量多播树法( m i n i m u m e n e r g ym u l t i c a s tt r e e ) 是n p - h a r d l f i j 题。 此外，t a k un o g u c h i 等指出网络编码还可对整个网络起到负载均衡作用【4 5 1 ，可 作为流量工程的一种技术加以应用。 综上，网络编码可广泛地应用在各种实际网络上，并可带来传统路由方式无 法实现的效益。 网络编码最初的研究主要针对多播网络传输，研究的角度主要是编码算法、 编码所带来的传输速率的提高程度、无线网络应用中编码带来的能耗减少程度等。 目前，对一个任意给定的多播网络进行网络编码算法主要有三种： - i 主t k o e a e r 等【1 6 , 3 9 1 于2 0 0 2 年提出的基于代数结构的网络编码算法，他将有限 域上的多项式法用到网络编码的研究中，为网络编码理论研究提供了有效 的代数研究工具。但是，这种算法是一种指数时间算法，其算法复杂度较 大。 一 由s a n d e r s 等和j a g g i 等于2 0 0 3 年同时提出的一种基于网络信息流传播的多 项式时间算法【1 7 , 1 8 】。在从源点到各终端节点传输信息之前，该算法先通过 一种简单的路由算法选取源节点到各个终端节点的传输路径。这是第一次 8 西安电子科技大学博士学位论文：网络编码理论及其应用的研究 在网络编码中考虑多播路由问题。与第一种算法相比而言，其算法复杂度 大大降低。 - t h o 等给出了随机网络编码算法【1 9 , 2 0 。该算法虽然简单，但是所需的编 码符号域较大，增加了编译码运算的复杂度。 基于网络编码的路由算法是另一前沿研究方向，目前仅有少数文献研究该内 容。k a p i lb h a t t a d 给出了基于网络编码多播传输的信息流的解释【i l5 1 ，并提出最小 化参与网络编码包数目的分布式算法，及基于网络编码的有线路由算法( 包括 m u l t i c a s t 和u n i c a s t ) 。d s l u n 提出了在多播网络中建立最小费用多播连接的问题 【4 9 1 ，并将其作为一个线性规划问题来研究。结果表明在有线网络中，最小费用多 播相对于有向s t e i n e r 树可以节约1 0 3 3 的计算量。a n n al e e 等人【1 1 6 】考虑具有相 关源网络的多播路由选择问题，采用随机网络编码，在网络中进行子图构造，对 链路速率的分配提供一个线性最佳化描述。此方法需要联合分布式源和网络编码， 比独立源具有更低的费用。 网络通信中，建立可靠的网络连接一直是人们重点关心的问题，而基于网络 编码的网络连接也是目前的研究热点之一。k o e t t e r 和m e d a r d 在文献【3 9 】提出了用静 态的( s t a t i c ) 线性编码保障在有链路中断可能的网络上进行可靠传输方式。文献 【l1 7 】利用信息理论的观点分析了非各态历经链路失败恢复的网络管理问题，指出 采用网络编码可以简化网络链路失败恢复管理开销，并给出了针对一条链路失败 所需的码字数目的上下界。c a i 和y e u n g 等【3 6 ，3 7 ，3 8 , 1 0 0 , 1 0 1 , 1 0 9 1 提出了基于网络编码的网 络纠错编码概念。以网络编码为基础，当信息在网络中传播时，若某一时刻有几 条链路上传输的符号发生错误，只要错误数没有超出纠错范围，终端接收节点通 过恰当的译码可恢复出正确的信息，而不需要信息重传。s r i i s 指出基于差错控制 的网络编码和传统差错控制码的设计有很强的联系【1 1 8 l ，为基于差错摔制的网络编 码设计提供了方向。 在研究网络编码理论的同时，学者们也开始关注有关网络编码的安全问题。现 在有关嘲络编码安全的研究，主要是基于n c a i 等提出的基于门限切割方案的安全 模型【3 5 , 1 0 3 。j o nf e l d m a n 等【1 1 9 1 证明了构造安全的网络编码问题等效于寻找具有某种 普遍距离特性的线性码问题，并且通过容量和编码域两者间的折衷可实现网络编 码的安全性。c h r i s t o sg k a n t s i d i s 等给出了基于网络编码的文件分发问题的协作安全 模型1 2 0 1 ，此模型不仅能够有效的检测出投放攻击和熵攻击，而且还能检测出恶意 节点。 当对网络编码的一些基本理论问题进行研究的同时，有关的实际应用研究也 在逐步深入。2 0 0 3 年，p a c h o u 等【4 7 l 考虑了网络编码在实际应用中的相关问题及 解决方案，并对其性能进行了仿真和分析。j w i d m e r 等【1 2 1 1 研究了在一些特殊网络 第一章绪论 9 一 中采用网络编码，如节点之间距离远、连接概率小的无线传输网络，并且给出了 有效、可靠的传输算法。d p e t r o v i 6 等人【1 2 2 】将网络编码应用到未调谐无线通信网 络中，给出了一个包含数字器件和模拟器件的整合架构，该架构不仅可大大降低 通信器件的成本、尺寸和功率消耗，还使可达通过率接近完美调谐网络的1 e 倍。 文献 2 5 2 6 研究了网络编码在大数据分发中的应用问题。微软公司新近以此技术开 发了一款p 2 p 雪崩型( a v a l a n c h e ) 软件，该软件预计能够提高网上信息传输率百分之 二十至三十。网络编码不仅节约了下载时间，还增强了p 2 p 通信系统的鲁棒性，即 当有些p e e r 节点提前离开系统时可保障整个系统照常工作。 1 3 3有待研究的问题 网络编码理论已经取得了很多研究成果，微软公司开发的以网络编码为核心 技术的p 2 p 雪崩型( a v a l a n c h e ) 软件，使网络编码也步入了实用化的进程。但还有许 多问题有待研究，下面描述了其中一些重要的问题。 ( 1 ) 要进行网络编码，就要求网络中的路由器或者至少一部分路由器具有数据 流处理的功能。而目前的路由器尚不具备这种功能，因此必须更换目前的路由器。 更换所有路由器会增加非常大的成本，这在近期是不现实的。那么更换目前网络 中的多少路由器及哪些路由器是一个关键问题。 ( 2 ) 基于网络编码的路由算法和目前的路由算法有较大区别，但还是可分为集 中式和分布式两种，寻找基于特定编码算法的简单有效的路由算法是网络编码迈 向实用化的关键一步。 ( 3 ) 目前只有三种网络编码算法，其中p s a n d e r s 等人1 1 7 , 1 8 1 提出的多项式时间算 法较简单，但还是有许多因素需要进一步深入研究，如网络编码算法应用在网络 中时，为了让参与的节点能知道编解码信息，耗费的开销有多大，如果开销过大 则该算法不可能应用于实践。对特定的网络环境构造简单有效的网络编码算法将 成为今后网络编码研究的重点内容。 ( 4 ) 网络编码能确保信息传输速率达到最大流最小割定理所确定的网络最大 流，将网络编码引入到网络通信系统中并与现有的通信技术相结合，是否能带来 网络通信性能的进一步提高，还有待于进行深入的探讨。 1 4 论文的主要工作概述及章节安排 作者结合国家8 6 3 自然基金项目和华为公司的联合项目对网络编码的基本原 理以及各种网络编码算法进行了深入的研究。在多播网络进行网络编码之前，涉 及到多播路由的选择问题，不同的路由选择策略将消耗不同的网络资源。针对路 1 0 西安电子科技大学博士学位论文：网络编码理论及其应用的研究 由问题，提出了基于网络编码的多播路由算法；针对子树图搜索问题，根据最小 子树图性质提出了基于网络编码多播路由图的最小子树图搜索算法；考虑到不同 网络需要不同的链路码字分配策略，利用最大距离可分码的基本原理，给出了不 同网络的码字构造算法；针对两信源节点通过中继节点相互交换信息的网络模型， 给出一种基于星座映射的物理层网络编码算法；最后针对复数域网络编码，给出 了一种并行中继优化设计方案，并讨论了节点的检测复杂度以及信源符号的传输 时延。以上研究取得的成果将在论文的各个章节中体现： 第二章系统介绍了网络编码的基本原理；详细分析了指数时间算法、多项式 时间算法，以及这些网络编码算法可行时所需有限域的大小。 第三章从减少网络资源消耗以及改善链路负载均衡的角度，给出了一种基于 网络编码的多播路由算法，并分析了该算法能减少资源消耗以及提高负载均衡的 原因。针对x o r 选择重传a r q 协议，提出一种网络编码的多播路由算法，有效 地恢复链路传输错误。 第四章利用最小子树图的性质，给出了一种最小子树图搜索算法。在最小子 树图上进行有效地网络编码，所有的网络编码问题可以简化为搜索多播网络的最 小子树图问题。 第五章利用最大距离可分码的已有成果，分别给出了k 冗余多播网络、存在链 路故障多播网络的链路码字分配算法以及所需的最小有限域；基于网络编码信息 线性组合的方法，给出了一种无线传感器网络中的数据快速采集算法。 第六章针对两信源通过中继节点进行信息交换的网络模型，给出一种基于星 座映射的物理层网络编码算法，可在不损失性能的前提下降低中继节点的能量消 耗。 第七章分析了网络编码在协作分集中的应用，给出了复数域网络编码的一种 并行中继优化设计方案，显著地降低了目的节点的检测复杂度以及信源符号的传 输时延。 第八章对全文的工作进行总结，并给出进一步的研究方向。 第二章网络编码概述 第二章网络编码概述 本章首先给出网络编码的基本模型，综述网络编码基本原理，并指出网络编 码的可译条件从各种网络编码算法角度出发，详细分析了指数时间算法、多项 式时间算法，并给出了网络编码可行时所需有限域的大小 2 1 1网络模型 2 1 网络编码模型 对于一个实际的通信网络，可以采用一个有向图加以描述和研究。有向图中 的节点表示一台主机或者路由器，图中的一条边表示实际中的一条端到端的通信 链路。这里首先对有向图的基本概念【1 1 , 1 2 】作以介绍。 定义2 1 ：一个有向图g 是由一个非空有限集合y ( g ) 和y ( g ) 中某些元素的有序 对集合e ( g ) 构成的二元组，记为有向图g = ( y ( g ) ，e ( g ) ) 。其中y ( g ) 称为图g 的节点 集，矿( g ) 中每一个元素称为该图的一个节点；e ( g ) 称为图g 的链路集，e ( g ) 中每 个元素称为该图的一条链路。不引起混淆的情况下，记号矿( g ) 和e ( g ) 可以省略g ， 分别记节点集、链路集为v 和e ，而记有向图为g = ( 矿，e ) 。 如果对于图g ，：( y ，e ，) 和g = ( y ，e ) ，有v gv ，f e ，则称图g 是图g 的子 图( s u b g r a p h ) 。 有向链路用e ：( v ，v ) e 表示，这里v ，v 是网络中的两个节点。链路p = ( v ，v ) 的 头用v ：h e a d ( p ) 来表示，尾用v 7 = t a i l ( e ) 来表示。如果v = t a i l ( 1 ) ，称链路i 是节点v 的 输出链路；如果y = h o d ( 1 ) ，则称链路，是节点v 的输入链路。 称源节点的输出链路为源链路，接收节点的输入链路为终端链路。定义r ，( v ) 为 节点v v 的输入链路集合，即