（电路与系统专业论文）线性网络编码研究[电路与系统专业优秀论文].pdf

南京邮电人学硕j ：研究生学位论文中文摘要 摘要 2 0 0 0 年，香港中文大学的a h l s w e d e 博士等人从信息论的角度出发，提出了网络编码的 概念。网络编码是指在计算机网络的中间节点上对接收到的信息进行一定形式的编码处 理，然后再传输出去，在信宿节点上，通过一定的处理方式，译出信源节点所发的信息， 而不是像传统网络那样在中间节点上只是进行存储转发。 网络编码的研究涉及计算机通信技术、组播技术、信息论和图论等方面的知识。它的 提出彻底地改变了计算机网络中的信息处理方式，提高了网络的传输容量，可实现利用有 限的网络资源传输更多的信息。因此，对于网络编码的研究具有相当重要的意义。 本论文以图论为工具，从流增广路径出发，对线性网络编码算法进行了研究。论文首 先简要介绍了计算机网络的产生和发展、组播技术的产生、路由实现及组播技术的局限性， 回顾了网络编码的提出、发展和现状；其次描述了网络编码的基本概念，并从信息论的角 度证明了其可以实现网络中的最大流，而这是传统路由方式所不能达到的：然后介绍了目 前网络编码最主要的实现方式线性网络编码，介绍了针对线性网络编码的线性信息流 编码组播算法和完全随机的网络编码方式；最后本文基于图论提出了一种新的线性网络编 码实现算法，并给出可行性证明。本算法直接求解全局编码向量，不需求解局部编码向量， 简化了计算。 关键词：网络信息流，组播，网络编码，线性网络编码，最大流最小割，线性码组播 南京螂r 乜大学颂j ：研究生学位论义 英文擒要 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 yd r a 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 n 2 0 0 0 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 p u t e rn e t w o r k st oc o d et h e i 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 es i n k s ，i n f o r m a t i o ni sd e c o d e d f r o mw h a t t h e yr e c e i v e d 。 t h er e s e a r c ho fn e t w o r kc o d i n gi n v o l v e st h ek n o w l e d g ea b o u tc o m p u t e rn e t w o r k s ， m u l t i c a s tt e c h n i q u e ，i 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 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 d t 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 nm e t h o di nn e t w o r k sa n di tc a l le n h a n c et h ec a p a c i t yo f t h ec o m m u n i c a t i o nn e t w o r k s a sar e s u l t , t h es t u d yo nn e t w o r kc o d i n gi so fg r e a ts i g n i f i c a n c e r e s e a r c ho na l g o r i t h mo fn e t w o r kc o d i n gb a s e do ng r a p ht h e o r yi si n c l u d e di nt h e d i s s e r t a t i o n 。f i r s t l y ，t h ed i s s e r t a t i o ni n t r o d u c e s t h eo c c u r r e m e n ta n dd e v e l o p m e n to ft h e c o m p u t e rn e t w o r k s ，m u t t i c a s tt e c h n i q u ea n dt h en e t w o r kc o d i n g 。s e c o n d l y , i td e s c r i b e st h e c o n c e p to ft h e n e t w o r kc o d i n g ，c o n f i r m i n gt h a tt h r o u g hn e t w o r kc o d i n gc a l la c h i e v et h e m a x f l o wo ft h en e t w o r k s ，a n dt h e ni n t r o d u c e st h em e t h o do fn e t w o r kc o d i n g ，l i n e a rn e t w o r k c o d i n g 。t h i r d l y ，i ti n t r o d u c e st h el i n e a ri n f o r m a t i o n f l o wa l g o r i t h mw h i c hb a s e do nl i n e a r n e t w o r kc o d i n g 。f i n a l l y ，t h ea u t h o rp r o p o s e dan e wa l g o r i t h mo fl i n e a rn e t w o r kc o d i n ga n d c o n f i r m si t ，w h i c hi st h ee m p h a s i so ft h ep a p e r a n dt h ea l g o r i t h mm a k e se a s y ， k e yw o r d s ：n e t w o r ki n f o r m a t i o nf l o w , m u l t i c a s t ，n e t w o r kc o d i n g ，l i n e a rn e t w o r kc o d i n g ， m a x - f l o wm i n - c u t , l i n e a r - c o d em u l t i c a s t i i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 圈鱼也日期：型! 墨：竺丝 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：! 虱堡垒导师签名：妻i 嗑日期：丝鳘：生竺 南京邮电人学硕士研究生学位论文第一章绪论 1 1 计算机网络 第一章绪论 当前世界经济正从工业经济向知识经济转变。知识经济的两个重要特点是信息化和全 球化。要实现信息化和全球化，就必须依靠完善的网络。因此，网络现在已经成为信息社 会的命脉和发展知识经济的重要基础。网络对社会生活的很多方面以及对社会经济的发展 已经产生了不可逆转的影响，尤其是i n t e r n e t 的建立，推动了网络向更高层次发展，而建设 信息高速公路，更是使得网络技术进入新的历史阶段【l 】o 1 1 1 计算机网络的产生和发展 计算机网络的发展大体上可以分为以下四个发展阶段【2 1 。 ( 1 ) 面向终端的计算机网络 随着军事、工业等部门应用计算机的需求增加，人们非常需要将分散在不同地方的数 据进行集中处理。在2 0 世纪5 0 年代，人们开始将彼此独立发展的计算机技术与通信技术结 合起来进行研究，以计算机为中心，各终端通过通信线路共享主机的硬件和软件资源，实 际上就是以单机为中心的联机系统。 ( 2 ) 分组交换网 2 0 世纪6 0 年代中期，英国的d a v i e s 提出了分组的概念，使计算机的通信方式由终端与 计算机的通信发展到了计算机与计算机之间的通信。到t 6 0 年代末期，美国国防部高级计 划研究署的分组交换网a r p a n e t 的建立，对网络技术的发展起了重要的作用，使网络的 概念发生了根本性的变化，即表明了计算机网络要完成数据处理与数据通信两大功能，从 而为i n t e m e t 的形成奠定了基础。分组交换网由通信子网和资源子网组成，其核心技术是分 组交换。 ( 3 ) 计算机网络体系结构和网络协议的标准化 2 0 世纪7 0 年代中期国际上各种网络系统发展十分迅速，相互通信的计算机系统必须高 度协调才能工作，因此网络体系结构和网络协议的国际标准化问题显得越发重要。为了使 不同体系结构的网络能够实现互联，i s o 推出了开放系统互联网的参考模型，对网络理论 体系的形成与网络技术的发展起了重要作用。 ( 4 ) 网络互联与高速网络技术 l 堕墨塑皇奎堂堡圭堕窒竺兰垡笙壅苎二童丝堡 从2 0 世纪8 0 年代末期以来，计算机网络迅速发展，其主要标志为：采用高速网络技术； 建设信息高速公路；多媒体网络及宽带综合业务数据网的开发和利用；智能网络的发展； 高速以太网、光纤分布式数据接口f d d i 、快速分组交换技术；i n t e m e t 的发展，更是促使网 络技术飞速发展，实现全球范围内的网络通信。 1 1 2 计算机网络的主要功能 计算机网络由计算机系统通信链路( 指线路及其设备) 和网络节点组成。一般的网 络体系具有下述主要功能： ( 1 ) 通信功能 网络技术是通信技术和计算机技术结合得产物，信息的传递是计算机的基本功能。 ( 2 ) 资源共享 指共享计算机系统的硬件、软件和数据：共享硬件资源，指在网络内提供处理资源、 存储资源、输入输出资源等的共享，特别是对一些高级和昂贵的设备；共享软件资源，包 括很多语言处理程序、网络软件等：共享数据资源，包括各种数据库、数据文件等。网络 提高了整个系统的数据处理能力，降低了平均处理费用。 ( 3 ) 提高了系统的可靠性和可用性 网络依靠可替代的资源提高可靠性，使网络计算机彼此互为备用，一台计算机出故障， 可将任务交由其他计算机完成。通过计算机网络均衡各台计算机的负担，由网络上的计算 机协同完成各种处理任务，均衡使用网络资源，提高了每台计算机的可用性。 ( 4 ) 容易进行分布式综合处理 利用网络技术，按一定的算法将复杂任务交给不同计算机协作完成，便于采用分布式 处理综合解决大型复杂的问题。 1 1 3o s i 参考模型 为了使网络系统结构标准化，1 9 7 8 年国际标准化组织提出了开放系统互联参考模型 ( o p e ns y s t e mi n t e r n a t i o n a lr e f e r e n c em o d e l ，o s i - r m ) 。 所谓“开放系统 是指一个系统与其他系统进行通信时能够遵循o s i 标准的系统。开 放系统互联网络模型的7 层结构如图1 1 。 2 南京邮电大学硕士研究生学位论文第一章绪论 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 图1 1 开放系统互联网络参考模型 o s i 参考模型采用了层次化结构，将整个网络通信的功能分为了7 个层次，每层完成特 定的功能，并且下层为上层提供服务。这7 层分别为：物理层、数据链路层、网络层、传 输层、会话层、表示层和应用层。通常将其中的低三层称为通信子网，是由计算机和网络 共同执行的功能；而将其余的四层称为资源子网，执行开放系统之间的通信控制功能。 1 1 4 网络通信方式 如今网络的通信方式主要有以下几种： ( 1 ) 单播( u n i c a s t ：p o i n tt op o i n t ) ，点到点的通信方式； ( 2 ) 组播( m u l t i c a s t ：p o i n tt om u l t i p o i n t ) ，点到多点的通信方式； ( 3 ) 汇播( c o n c a s t ：m u l t i p o i n tt op o i n 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 c a s t ：p o i n tt oa l lp o i n t ) ，点到所有节点的通信方式。 1 2 组播技术 1 2 1 组播技术的产生 传统通信有两种方式【3 】：第一种是在一台源i p 主机和一台目的i p 主机之间进行， 即单播( t m i c a s t ) ；第二种是在一台源i p 主机和网络中所有其它的i p 主机之间进行，即广 播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而非所有主机，则要么由源主机分 南京邮电人学硕士研究生学位论文第一章绪论 别向网络中的多台目标主机以单播方式发送i p 包，要么采用广播方式。采用单播方式实现 时，由于i p 包的重复发送会白白浪费掉大量带宽，也增加了服务器的负载：采用广播方式 实现时，不仅会将信息发送给不需要的主机而浪费带宽，也可能由于路由回环引起严重的 广播风暴。因此，传统的单播和广播通信方式不能有效地解决单点发送多点接收的问题。 i p 组播是指在i p 网络中将数据包以尽力传送( b e s t e f f o r t ) 的形式发送到网络中的某个 确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。i p 组播的基本思想是，源主机只 发送一份数据，这份数据中的目的地址为组播组地址，组播组中的所有接收者都可接收到 同样的数据拷贝，并且只有组播组内的主机( 目标主机) 可以接收该数据，网络中其它主 机不能收到。 1 2 2 组播技术的路由实现 考虑一个通信网络【4 】，它是由一些节点和边组成的集合，用有向图g = ( y ，e ) 来表示， y 和e 分别是节点和边的集合，非负数r ( e ) 用来表示边e 上允许传输信息的容量上限。在 这个通信网络中，要实现由一点s v 向多点t c v 组播信息，传统的路由方式是通过在通 信网络中建立一个或多个组播树q = ( 圪，毛) ，每个组播树都将信源和所有的信宿连接起 来，所要传输的信息就在这些事先选好的路径上传输。每个组播树可以实现的传输速率取 决于组成这个树的所有的边中容量最小的边，也就是m i n 。反r k ( e ) 。为了可以获得更高的 组播速率，可以建立多个组播树q ，k = 1 ，k ，并且在不同的组播树上传输不同的信息， 只要每条边上传输的信息量满足er k ( e ) r ( p ) 即可。 1 2 3 组播技术的局限性 上面已经提到，组播是靠在通信网络上建立组播树来实现的。由最小割最大流定理【5 1 ， 网络中两节点之间的最大流量可以通过最小割来衡量，同时，实现最大流的路径可以通过 最大流算法【5 】找到。当要建立两节点之间通信的时候，在两节点之间，应用最大流算法， 得到它们之间的最大传输速率。但是，一点向多点的组播路由树的建立是一个n p i 口- j 题【6 l 。 一般采用的方法是首先采用最大流算法找到信源与一个信宿之间的最大流及其实现的路 径，其次再依次寻找信源与其他信宿之间的路径。在寻找信源与第二个信宿之间的路径时， 就在原通信网络中去掉信源与第一个信宿之间已经用过的链路的容量。这样处理是因为， 4 塑室! ! ! ! ! 皇查兰堡= ! 三竺窒生兰垡笙苎兰二里丝堡 传统路由认为网络中传输的信息是不能叠加的，只能进行存储转发。这样的组播树的建立 方式会导致信源与第二个及其后面所有信宿之间的路径都不是以它们之间的最大流进行 传输的。这将最终使得组播可以实现的传输容量远远小于最小割最大流确定的容量上限。 1 3 网络编码的提出和发展现状 针对组播技术的上述局限性，网络编码应运而生，它可以用来实现由最小割最大流定 理给定的一个通信网络的容量上限。 1 3 1 网络编码的提出 随着信息时代的不断发展，各种通信网络与人们工作生活的各个方面结合的越来越紧 密。与此同时，由于用户数量的激增，网络服务的多样化以及针对网络传输质量要求的不 断提高，如何提高现有网络资源的利用率，优化网络，已成为当今通信网络研究的重要课 题之一。 传统的网络组播方式是在网络中寻找一棵有效的组播树，这种方式中网络节点只对数 据分组进行路由或复制。这样很难达到网络组播的最大传播容量，没有必要仅仅将网络节 点的功能限制为复制和转发。 2 0 0 0 年，a h l s w e d e 等【7 1 根据网络信息流的概念指出，网络组播的最大容量等于发送节 点和组播组中各接收节点之间的最小割的最小值，该最小值称作网络组播的最大流限。对 于一般的网络，这一容量很难通过传统的组播路由获得，但却可以通过网络编码组播获得。 网络编码指网络节点的输入链路与输出链路上传播的数据的相互关系。网络编码思想是在 y e u n g 的对称分层编码【8 , 9 , 1 0 , 1 1 , 4 5 】研究的基础上提出的，将分层编码在信源节点的编码推广到 允许整个网络节点进行编码来获得网络组播的最大流限。传统的组播路由可以看作是网络 编码的一种特例。 1 3 2 网络编码的发展现状 自从2 0 0 0 年a h l s w e d e 等人提出网络编码的基本概念之后，关于网络编码的研究如雨后 春笋般多起来。目前，有很多电信业巨头和著名的大学都在致力于这方面的研究，如香港 中文大学、微软、麻省理工学院、伊利诺伊大学、加利福尼亚大学洛杉矶分校、以色列的 t e l a v i v 大学等等。 雨泵邮电大掌坝士研冗生掌位论义第一荦绪论 按构造方式，网络编码可大致分为两种。一种是由k o e r 和m e d a r d 【1 2 , 1 3 , 1 4 1 提出的网络 编码的代数构造方式。这种构造方式是在知道整个网络的拓扑信息的情况下，用一个系统 转移矩阵来描述信源输入信息和信宿上接收到的信息之间的关系，并通过构造符合要求的 系统转移矩阵来实现网络编码。另一种是s a n d e r s 等人提出了一种实现网络编码的多项式时 间算法【1 5 , 1 6 】，这种方法不但把网络编码构造的复杂度从指数级降到了多项式级，而且大大 降低了网络编码中所采用的字母表的下限。 上述方法都是基于己知整个网络的拓扑信息，同时c h o u 等提出了不需网络拓扑信息的 分布式网络编码【1 7 1 和随机网络编码f 1 8 , 1 9 1 。分布式网络编码的实现是在网络中传输的每个数 据包上留出一些比特用来记载此数据包在前面各个节点上所经历的各种操作，接收节点就 可以从接收到的数据包中直接译出信源所发送的信息。这种方法是可以在不知网络拓扑信 息的情况下实现网络编码，但是增加了网络负载，但是仿真结果表吲 】，在整个信息的组 播过程中，这种处理方式所带来的负载代价不大。随机网络编码，即在网络的中间节点上 对接收到的信息在一个有限域内随机选择一个元素作为组合的系数。研究己经表明只要有 限域取的足够大，这种方法的失败率就可以很低。这种方法带来的缺点一个是以一定的概 率实现正确无误的传输，另一个是需增大通信网络中所需的字母表的大小。 还有一些人致力于线性网络编码【7 2 0 1 的研究，给出线性网络编码的实现方法，并分析 了线性网络编码的有效性【2 1 ，2 2 】。线性网络编码不但可以用在己知网络拓扑的构造方式中， 也可以用在不需网络拓扑信息的分布式网络编码和随机网络编码中。他们推测线性网络编 码可以实现所有的可解网络的网络编码【2 3 1 。而文献 2 4 】中己经构造了一个特殊的网络说明 了线性网络编码的局限性，在这些特殊的网络中使用非线性网络编码可以实现最小割最大 流确定的网络容量的上限，线性网络编码却无能为力。 上述研究都是针对有线网络的，关于无线网络中的网络编码的研究也是网络编码研究 中的一个热点f 2 5 2 6 2 7 2 引。由于无线网络自身的一些不同于有线网络的特性，这使得网络编 码在无线网络中的应用带来了新的好处。 另外，现在关于网络编码和其它方面结合的研究也很多，例如网络编码和纠错码的结 合 2 9 , 3 0 , 3 1 1 ，网络编码和加密体制的结合1 3 2 3 3 3 4 】等。 目前，网络编码的研究热点主要集中在以下几个方面： ( 1 ) 网络编码节点选取方案 在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编 译码的节点，给予编译码功能。对于不需要编译码的节点，只具有传统的存储转发功能即 可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码的 6 南京邮电大学硕t ：“j f 究生学位论义第一章绪论 应用更为广泛。文献 3 1 】根据网络拓扑结构，利用种子树分解算法来寻找编码节点。将 该算法应用于有线网络中并使用确定的网络编码机制，效果较好。对于无线网络，节点之 间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导致拓 扑结构更为紧密，应用上述方法选择编码节点就不适合。无线网络中主要考虑节点能量及 稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较高、具有较强的运 算速度和较大的缓存空间的节点，以提高网络的鲁棒性。 ( 2 ) 网络编码算法的设计 目前，网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构 架上，这些方案主要是基于理论上的分析和实现，在实际网络中需要针对不同的应用设计 相应的编码方式。对于结构较小的网络，可以选择比较简单的确定性算法，编码过程中甚 至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度。对于无线网 络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对节点所 有的可用信息应用线性编码，并随时更新编码系数。文献 1 3 】已经证明，当符号集为无穷 大时，采用随机编码，系数传输矩阵满秩的概率是1 ，即编码成功的概率很大，但同时会 增加数据报头的负担，因此符号集的大小需要权衡各种因素。 ( 3 ) 网络编码复杂度分析 网络节点编码过程中涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接收 节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块的 大小共同决定了编码符号集的最l k 乇f - 限。对于确定性编码而言，所需的符号集可以较小， 编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多 应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码 算法从而降低网络的复杂度。对于随机网络编码而言，所需的符号集较大，而且节点在传 送信息的同时传送系数向量，虽然系数向量相对于信息而言较小，但同样会占用较大的带 宽，因此需要设计合适的算法，保证在提高编码增益的同时降低复杂度。网络编码复杂度 要受到符号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面分析得 出。 ( 4 ) 网络编码的性能分析和应用 网络编码可以提高网络容量，已经证明，应用网络编码可以逼近香农极限。网络编码 通过编码节点对输入信息线性或非线性的编码处理，可以在不提高消耗带宽的情况下，使 不同的信息同时通过有限的链路，从而提高网络流量。 7 塑室堕皇盔兰堕：! 型! ! ! 圭兰垡笙苎茎二里堑堡 网络编码导致编解码的过程中可能会产生编译码错误，这将增大网络数据传输的误码 率。而就网络编码本身而言，对误码率有着相当苛刻的要求，只有较小的误码率才能保证 网络编码的有效性和可靠性，否则使用网络编码可能还会带来系统整体性能的降低。因此， 如何设计可靠的网络编码方案以保证数据传输较低的误码率，并尽可能地采用相应技术减 少误码率对网络编码方案的影响是网络编码研究所必需的。 ( 5 ) 网络编码与系统安全性分析 网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络的安全性能产生影 响。一方面，由网络编码导致的信息的分散性和编译码特性增加了信息破译难度，对安全 性而言是一种改善：另一方面，对确定性编码算法而言，由于传输过程中将涉及较多的节 点数目，以及编码算法方案的确定性，会导致系统的安全性能的降低。因此编码算法的设 计中也需要考虑系统的安全性能，通过对不同的编码算法进行恰当的安全性能分析，来确 定不同网络算法对系统安全性的影响，从而针对不同的系统应选用合适的编码算法，以提 高网络安全性能，这对于通信网络的研究具有重要意义。 ( 6 ) 网络编码在无线分布式网络中的应用 对网络编码技术的研究需要在加深理论研究的同时，考虑实际的应用场景，侧重解决 实际应用中遇到的问题，比如需要降低编码复杂度，需要考虑系统本身的延时以及网络编 码带来的延时影响等。网络编码在无线通信网络当中的应用是一片亟待开发的热土，一方 面无线网络的广播特性非常利于网络编码的应用；另一方面，相对于有线网络而言，无线 网络中的节点不可能同时监听来自多个信源的信息，对网络编码的应用造成了一定的阻 碍。如何结合无线分布式网络的特点扬长避短，找到能够最大程度发挥网络编码优势的结 合点，是需要考虑的主要问题。 总之，现在关于网络编码的研究是百家争鸣，各种方法和应用层出不穷。到目前为止， 网络编码还没有应用在实际网络中，所以关于网络编码的研究还有很多问题亟待解决，这 是一个相当诱人的新领域。 1 4 本文的主要研究工作和章节安排 网络编码的提出彻底改变了计算机网络中的信息处理方式，网络节点不再仅仅限制于 存储转发，而是在网络节点上可以进行编码处理，实现利用有限的带宽资源传输更多的信 息。其研究涉及计算机通信技术、组播技术、信息论和图论等方面的知识。自从网络编码 概念提出以来，很多专家和学者都致力于网络编码算法的研究与设计，从不同的角度出发， 南京邮电大学硕上研究生学位论义第一章绪论 提出了很多的方案，大多基于理论的分析和实现。网络编码算法设计是本文将要研究的主 要工作。 作者在对网络编码的基本理论进行深入学习的基础上，提出了一种线性网络编码算 法，并证明了其可行性。本文共分六章，主要结构如下： 第一章绪论部分简要介绍了计算机网络的产生和发展，组播技术的产生、路由实现及 组播技术的局限性，回顾了网络编码的提出、发展和现状； 第二章首先介绍了研究网络编码所需的图论中的各种相关基本概念，为后续章节作铺 垫；其次描述了网络编码的基本概念，并从信息论的角度证明了其可以实现网络中的最大 流，而这是传统路由方式所不能达到的；然后后介绍了网络编码目前最主要的实现方式一 一线性网络编码，并给出了线性网络编码的从不同角度出发的两种构造方式：从向量空间 角度和从代数构造角度出发的构造方式；最后给出了线性网络编码两种构造方式的编码符 号界。 第三章首先介绍了针对线性网络编码的线性信息流编码组播算法，其次介绍了完全随 机的网络编码方式，最后讨论了在实际环境中采用网络编码时应考虑的具体问题以及采取 的相应措施。 第四章在充分掌握了网络编码的基本理论知识后，本论文以图论为工具，从流增广路 径出发，对线性网络编码算法进行了研究，提出了一种新的线性网络编码算法，并且证明 了其可行性。本算法直接求解全局编码向量，不需求解局部编码向量，简化了计算。 第五章对全文工作进行总结并提出进一步研究方向。 9 南京邮电大学硕士研究生学位论文第二章网络编码概述 第二章网络编码概述 在这一章中，首先，介绍了研究网络编码所需的图论中的各种相关基本概念，描述了 网络编码的基本概念，并从信息论的角度证明了其可以实现网络中的最大流，而这是传统 路由方式所不能达到的；其次，介绍了网络编码目前最主要的实现方式一线性网络编码， 并给出了线性网络编码的从不同角度出发的两种构造方式及其各自的编码符号界；最后， 从理论上总结了网络编码性能分析的已有成果，这些成果显示了网络编码的巨大优越性。 2 1 网络编码的预备知识 2 1 1 图的基本概念 一个图是由一些节点和连接两个节点之间的边所组成，至于边的长度及节点的位置是 无关紧要的【5 1 。 定义2 1 ：一个图g 是一个序偶( v ，e ) ，记为g = ( v ，e ) ，其中： ( 1 ) v = v l , v 2 ，) 是有限的非空节点集合，v ( f = 1 ，2 ，m ) 称为节点，v 称为节 点集。 ( 2 ) e 是有限的边的集合，e 称为边集。e 中的每个元素都是以( v ，v j ) 或( ，v ) 形式出 现的无序对，其中f ，= l ，2 ，m 。 若边p 与节点的无序对( v ，v j ) 相对应，则称p 为无向边，记为p = ，这时称v f 、 是边p 的两个端点。若边p 与节点的有序对( v ，v j ) 相对应，则称p 为有向边，记为 p = ( v ，) ，这时v 称为p 的始点，为p 的终点，统称为p 的端点。 为了描述简便起见，在一般情况下，对于一个图g = ( v ，e ) ，往往不写出v 和e 的集合 表示，而只画出它的图形，用小圆圈表示v 中的节点，用( e ，) 表示由指向的有向线 段。 定义2 2 ：每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有 些边是无向边，而另一些边是有向边的图称为混合图。 在有向图中，两节点间( 包括节点自身间) 若有同始点和同终点的几条边，则这几条 边称为平行边。在无向图中，两节点间( 包括节点自身间) 若有几条边，则这几条边称为 i n 南京邮电大学f 顶士研冗生学位论文第二章网络编码概述 平行边。两节点v j 和 ，间相互平行的边的条数称为边( b ，v j ) 的重数。 定义2 3 ：( 1 ) 图g = ( 矿，e ) 中节点v y 所关联的边数( 有环时计算两次) 称为节点v 的 度数，简称度，记为d e g ( v ，) 。 ( 2 ) 设v 为有向图g = ( 矿，e ) 中的节点，以v ，为始点的边的条数称为节点v 的出度，记 为d e g + ( _ ) ；以v 为终点的边的条数称为节点一的入度，记为d e g 一( v ) 。显然， d e g ( v , ) = d e g + ( ) + d e g 一( v ，) 。 ( 3 ) 对于图g = ( y ，e ) ，度数为1 的节点称为悬挂节点，它所关联的边称为悬挂边。 在研究和描述图的性质时，子图与补图的概念占重要地位。 定义2 4 ：设有图g = ( y ，e ) 和图g = ( v ，e ) 。 ( 1 ) 若矿sy ，e e ，则称g 是g 的子图，记为g g 。 ( 2 ) 若g g ，且g g ( 即矿cy 或e ce ) ，则称g 是g 的真子图，记为g cg 。 ( 3 ) 若y = 矿，e e ，则称g 是g 的生成子图。 ( 4 ) 设矿”矿且矿”，以y ”为节点集，以两个端点均在y ”中的边的全体为边集的g 的子图称为y ”导出的子图，简称g 的导出子图。 定义2 5 ：若有向图满足下列条件者，则称其为网络流图： ( 1 ) 有且仅有一个顶点s ，它的入度为零，这个顶点s 便称为信源节点，或称为发点。 ( 2 ) 有且仅有一个顶点，它的出度为零，这个顶点f 便称为信宿节点，或称为收点。 ( 3 ) 每一条边都有一个与之相关的非负数，表示该边的容量。边( _ ，v j ) 的容量用如表 口 例如图2 1 便是一个网络流图。 图2 1 网络流图 雨京邮电大学硕上研究生学位论文 第二章网络编码概述 上面定义的网络常常称为运输网络。可用运输网络来表示的物理模型是多种多样的。 网络中的有向边可以用来表示城市之间的公路、电讯局之间的通信线路，边的容量则可以 是允许通过的物资、速度，公路上的汽车数量或信号流量等等。 定义2 6 ：对于网络流图g ，每一条边( 一，v j ) 都给定一个非负数乃，这一组数满足下列 两条件时称为这网络的容许流，用厂表示它。 ( 1 ) 每一条边( v ，v ，) ，有 石色 ( 2 - 1 ) ( 2 ) 除了发点s 和收点，以外的所有的点”，恒有 乃= 兀 ( 2 2 ) j 式( 2 2 ) 说明中间节点m 的流量守恒，输入与输出的流量相等。 ( 3 ) 对于信源s 和信宿节点t 有 兀= 乃，= w ， j ( 2 3 ) 式( 2 3 ) 中w 叫做这个网络流的流量，而且从点j 发出的量等于流入信宿节点，的量。 定义2 7 ：当厶= 彤时便称边( _ ，v j ) 为饱和，表示流厂对该边已饱和。 所谓最大流问题是求使得从发点s 送往信宿节点f 的流量w 达到最大的流厂。 为了解决求网络的最大流问题，给出切割的概念。 定义2 8 ：对有向图g = ( y ，e ) 中两个不同的节点j 和，j 一，割是g 中弧( ，又) 的集合， 其中s x ，f x ，x 是y 的子集，彳= 矿一彳。 定义2 9 ：在这集合( x ，x ) 中，把从x 到x 的边的容量的和叫做这个割切的容量，用 c ( x ，x ) 表示，有 c ( x ，孑) = 一 m x ，j e x 1 2 ( 2 4 ) 南京邮电大学硕士研究生学位论文 第二章网络编码概述 图2 2 割切举例 如图2 2 中虚线分别表示割切( 置，五) 和( 置，五) ，其中： 对于割切( 五，五) ，有 五= s ，五= 口，6 ，c ，d ， c ( x l ，j i ) = + = 2 + 3 = 5 对于割切( 五，置) ，有 五= s ，口，b ) ，五= c ，d ，) c ( 五，五) = + + = l + 1 + 4 = 6 定理2 i f 3 5 】：( 最小割最大流定理) 对于已知的网络流，从源点j 到宿点，的流量w 的最大 值等于最小s r 割的容量，即 m a xw = m i n c ( x , ，置) ) ( 2 - 5 ) 其中，( z ，z ) 是s - t 割。 2 1 2 通信网络中的网络流图 假定考虑一个通信网络，用有向图g = ( y ，e ) 来表示。设口： 1 ，脚 哼矿和 b ： l ，聊) 专2 矿是两个任意的映射。信源z 在节点口( f ) 上产生，它将被组播到节点，对 所有的b ( i ) 。对于这里的单源问题，假定口( 1 ) = s ，和6 ( 1 ) = ，i ，t ) ，也就是说，信源 南京邮电大学硕上研究生学位论文第二章网络编码概述 墨由节点s 产生，网络将其产生的信息组播到节点f 1 ，f 。我1 f l n g as 为信源，节点 ，1 ，。为信宿。对于某个特定的值工，称这种i h - j n n 单信源l 信宿问题。 定义一些下面将会用到的符号：设图g = ( y ，e ) 中的信源为s ，信宿为f 1 ，t t 。边 ( f ，) e 上的容量为饬，且有足= 毛，( f ，) e 】。从信源s 到信宿，= 1 ，三的子图用 g f = ( y ，e ，) 表示，其中 局= ( f ，) e ：边( f ，) 在信n s n 信宿，的有向路径上) f = ，( f ，) e 】是图g 中从信源s 到信宿，的流 如果式( 2 - 6 ) 对于所有的( f ，j ) e 都成立 0 乃心 ( 2 - 6 ) 且对于除信源s 和信宿，之外的所有其他节点i v 有 巧，= 弓 ( 2 7 ) ，：( f i ) e ej ：o ，j ) e e 也就是流入节点f 的总的流量等于流出节点f 的总的流量。e 是指向量f 在边( f ，- ，) 上的取 值。向量f 的定义如下： 一瓦= 气一， ( 2 8 ) “，j ) e e ，：( ，j k e ：( ，j ，) e ej ：( t t ，j ) e e 如果从信n s 到信宿f 的流量的值大于等于任何其他从信源s 到信宿，的流量值，就称 f 为图g 中从信源j 到信宿f ，的最大流。 2 2 网络编码的基本概念 网络编码从广义上来讲，是网络中的节点将接收到的信息进行编码后再转发出去的多 点传送技术。多点传送( 也称组播) 是网络中的一种重要的通信方式。当一个或几个节点同 时向若干个其他节点发送数据时，往往要借助其他节点的传递。在传统的网络中，作为中 继的节点只能对接收到的信号进行复制、放大和转发，这对于网络资源有时候是一种浪费。 网络编码技术打破了这种限制，它允许中间节点对接收到的信息进行编码，并将接收到的 多个数据包按照某种特定算法重新组合再发送出去。 南京邮电大学硕士研究生学位论文第- 二章网络编码概述 2 2 1 网络编码的定义 对于一个网络g ( v ，e ) ，由最大流最小割定理，很容易求得信源s 到信宿，的最大单播 速率。对于组播网，值得关心的是信源的最大组播信息速率问题。 定义2 1 0 ：设g ( y ，e ) 为一个组播网络，h 为信息从信源j 到信宿“，2 ，t l 的组播传输 速率。令信源s 到信宿节点的最大流值为m a xa o w ( s ，) ，则对于所有的，= 1 ，2 ，l ，有 雒m a x f l o w ( s ，t 1 ) ( 2 - 9 ) 即 k 。m i n m a x f l o w ( s ，) ( 2 1 0 ) 将h 称作组播网络传输的最大流限。 对于只有一个信宿节点的网络，依靠路由就可以获得最大流。下面看一个具有两个信 宿的组播网络，如何获得网络组播的最大流。 通信网络如图2 3 所示，这是一个单信源两信宿的网络，假设每条链路无时延和无差错。 其中，s 是信源节点，y 和z 是信宿节点。图2 3 ( 1 ) 给出了每条边的信息速率均为1 比特 单位时间。由最大流最小割定理容易得出从信源s 到信宿节点y 和z 的最大流均为2 。由此 得到信源s 可以同时发送2 比特信息给y 和z 。图2 3 ( 3 ) 给出一种编码方案从图中可以看 出，为了从信源节点j 同时传输两比特信息6 l ，6 2 到信宿节点，则在中间节点w 处，必须通 过网络编码，使输出边( w ，x ) 传输两个输入边上携带信息的线性组合6 l + 6 2 ，那么在信宿节 点j ，和z 处，才可分别由b j + 6 2 和6 1 ，6 1 + 6 2 和2 j 2 ，恢复出所有信息6 l ，岛。如果按传统路由 方式如图2 3 ( 2 ) ，在一个单位时间内将无法完成以上传输。 南京邮电丈学硕i ：研究生学位论文 第二鼋炳络编码檄述 ( 1 遗豹器量( 2 ) 传统赣蠡l( 3 ) 麓络缡码 图2 3 经典鼹络编码原理醚 定义2 。l l ：阏络孛的节点对倍患比特流进行一定的操作，如模二加、与、鼓等等，恧 不是仅仅对其进行复制转发，称之为网络编码。 网络编码就是网络节点魄输入与输出的耀互关系。 网络编码不但可以用在组播通信网络中而且还可以用在非组播网络中以提高网络容 量。另一方蘸，霹络编码在提离嬲络的通信容量的瞄时，在受载均衡、降低麓量消耗等方 面也有不容忽视的作用。 道过网络编码，中阍节点可以将接收到的信息进行编码并发送凄去，提高了鼹终眷睦 量和鲁棒性。为了不对觋有网络的软硬件设备和相应的协议做很大的修改，可以选择在离 层实现网络编璐。 2 2 。2 网络编码的网络模型 个通信潮络可潋用有南篷g - ( v ，e ) 来表示，其中矿代表节点集，e 代表边集。考 虑组播情况，用scv 来表示通信网络中的信源节点的集合，集合tcg 表示信宿节点的 集合。网络中豹节点可以分失信源节点、中闻节点、信宿节点( 有时一个节点会充当多种 角色，比如说既是中间节点又是信源节点) 。耀( i ，歹) 来表示节点# 到节点歹豹边，即g ，歹) e ； 边g 嚣( i , j ) 的始点为j = h ( e ) ，其终点为i 聋f ) 。f 一( f ) 表示节点f v 的输入边鼢集合；f + ( ) 表示蕊点f t 的输出边的集合。其产生魄信息空闻为x - - - x ( i ，l 太x 辑2 ) ，。，x ( i ，4 0 ) ，它 1 6 南京邮电大学硕士研究生学位论文第二章网络编码概述 是由t ( i ) 个离散独立的随机过程x ( i ，g i ) ) 组成的，( f ) 是节点f 的入度。其中每个离散随 机过程均取自有限域互，。信宿节点f 所收到的信息空间z = z ( f ，1 ) ，z ( i ，2 ) ，z ( i ，7 7 ( f ) ) ) ，它 是由r l ( i ) 个离散随机过程z ( i ，7 7 ( 功组成，7 7 ( f ) 是节点i 的出度。在一个通信网络中，可以用 ( f ，j ，q ( f ，) ) 来表示信源节点f