（通信与信息系统专业论文）实用网络编码系统的可靠传输策略研究.pdf

大连理上大学硕十学位论文 摘要 在今天的实际网络通信中，分组交换信息的传递都是通过路由的方式来执行的。 但是中间节点传统的存储转发方式存在着功能上的缺欠，无法使得网络的吞吐量达到 理论上的最大值。于是，2 0 0 0 年香港中文大学的a h l s w e x i c 等人基于图论中的最大流 最小割原理提出了网络编码的理论。该理论提出改变网络中间节点的功能，允许中间 节点在转发信息前对输入信息流进行编码来实现网络吞吐量的极限。随后的研究表明， 网络编码不仅能够提高系统的吞吐量，还可以在均衡负载，减少传播延迟，降低节点 能最损耗等方面起着重要的作用。 针对网络编码的思想，专家学者们提出了许多种网络编码的构造方式，其中就包 括实用网络编码这种网络编码构造方式。实用网络编码技术是基于实际的通信环境提 出的一种可以用于现实环境中的网络编码方式。但是，该编码方式需要编码向量在传 输的过程中有着很高的可靠性，不然容易造成通信质量的严重恶化。尤其是在无线的 网络中，由于空间噪声的干扰较为严重，并且网络中的节点能量有限，不能提供较高 的信号发射功率，因此这种实用网络编码技术在无线网络中的应用时，通信质量更是 一个亟需解决的问题。鉴于这些问题，作者在本文中提出了几种实用网络编码系统的 可靠传输策略，将几种信道编码的方案应用到实用网络编码系统当中，针对实用网络 编码系统的特点以及实际应用的需要，提出了较为合适的编码保护方案，用于解决这 种通信质量不稳定的问题。仿真结果表明，本文提出的几种保护方案对于提高实用网 络编码系统的通信可靠性有着重要的意义。本文主要完成的工作有以下几个方面： 1 详细阐述了网络编码的基本原理，以及网络编码会给分组交换的通信方式带来 的好处。 2 详细介绍了几种常见的网络编码的构造方式。 3 提出了实用网络编码系统存在的通信质量恶化的问题，并详细的说明了存在 问题的原因。 4 提出了几种提高实用网络编码系统传输可靠性的策略，其中包括c r c 循环冗余 策略，联合编码策略，保护模式切换策略以及改进的c r c 循环冗余策略。 5 对于提出的几种保护箢略进行仿真以及分析说明。 关键词：网络编码；信道编码；空时编码；编码向量 实用网络编码系统的可靠传输策略研究 s t r a t e g i e so fr e l i a b l et r a n s m i s s i o ni np r a c t i c a ln e t w o r kc o d i n gs y s t e m a b s t r a c t i nt o d a y sp r a c t i c a lc o m m u n i c a t i o nn e t w o r k , i n f o r m a t i o nd e l i v e r yi sp e r f o r m e db y r o u t i n g h o w e v e r , t h et r a d i t i o n a ls t o r a g e f o r w a r dr o u t i n gm e t h o dh a si t so w nd r a w b a c k s w h i c hm a k e st h er e a ln e t w o r kc a n n o tr e a c ht h em a x i m u mt h r o u g h p u t t ot a c k l ew i mt h e i s s u e ，t h ec o n c e p to fn e t w o r kc o d i n gt h a ti sb a s e do nt h em a x f l o w - m i n c u tt h e o r e mw a sp u t f o r w a r db ya h l s w e d ee ta 1 i n2 0 0 0 t 1 1 i sc o n c e p tc h a n g e st h et r a d i t i o n a lf u n c t i o no fi n t e r n o d e ss u c ha sr o u t e r sa n dm a k e st h e me n c o d et h ei n c o m i n gi n f o r m a t i o nb e f o r et r a n s m i s s i o n t oa c h i e v et h em a x i m u mt h r o u g h p u t 1 1 1 ef o l l o w i n gs t u d ym a n i f e s t st h a tn e t w o r kc o d i n g c a nn o to n l yp r o m o t et h et h r o u g h p u to ft h es y s t e m ，b u ta l s op r o v i d ew i t ht h el o a db a l a n c e ， r e d u c t i o no ft h ep r o p a g a t i o nd e l a ya n de n e r g yc o n s u m p t i o n b a s e do l lt h ei d e ao fn e t w o r kc o d i n g ，t h ee x p e r t sh a v ep r o p o s e dm a n ys t r u c t u r e so f n e t w o r kc o d i n g t l 圮p r a c t i c a ln e t w o r kc o d i n gi sak i n do fn e t w o r kc o d i n gt h a tw a s d e s i g n e df o rt h er e a lc o m m u n i c a i t o ne n v i r o n m e n t h o w e v e r , t h i sc o d i n gs t r a t e g yn e e d s l l i g hr e l i a b i l i t yo fe n c o d i n gv e c t o r sw i t h o u tw h i c ht h ec o m m u n i c a i t o nq u a l i t yc o u l db e h o r r i b l e 。1 1 1 ec a s ei se v e nm o r eu r g e n t i nt h ew i r e l e s sn e t w o r kw h i c ha b i d e ss e v e r en o i s e i n t e r f e r e n c ea n dc a n n o ta f f o r dh i g ht r a n s m i r i n gp o w e r t ot a c k l ew i t ht h ei s s u e ，t h ea u t h o r p r o p o s e ss o m es t r a t e g i e so ft r a n s m i s s i o ni nt h ep r a c t i c a ln e t w o r kc o d i n gs y s t e ma n da p p l i e s s o m ec h a n n e lc o d i n ga l g o r i t h mt ot h en e t w o r kc o d i n gs y s t e m 1 1 1 ep a p e ra l s op r o p o s e st h e s u i t a b l ec h a n n e lc o d i n gm e t h o d sa c c o r d i n gt od i f f e r e n ts i t u a t i o n 鹪w e l la sa p p l i c a t i o n 1 1 1 e s i m u l a t i o nr e s u l t ss h o wt h a tt h e s ep r o t e c t i o ns t r a t e g i e sc a nm a k eg r e a tc o n t r i b u t i o n st ot h e e o m m u n i c a t i o nq u a l i t y n l em a i nw o r k sa r ea sf o l l o w s ： 1 1 1 1 eb a s i ct h e o r e mo fn e t w o r kc o d i n ga n dt h eb e n e f i t st h a tn e t w o r kc o d i n go f f e r s 2 s p e c i f i e ss o m ec o m m o n s t r u c t u r e so fn e t w o r kc o d i n ga l g o r i t h m 3 1 1 1 ep r o b l e mo fp r a c a t i c a ln e t w o r ks y s t e mi ss p e c i f i e da n dt h er e a s o no ft h e p r o b l e mi sp r e s e n t e di nd e t a i l s i i 大连理t 大学硕十学位论文 4 s o m es t r a t e g i e so fr e l i a b l et r a n s m i s s i o ni np r a c t i c a ln e t w o r kc o d i n gs y s t e ma r e b r o u g h tf o r w a r d ，i n c l u d i n gt h ec r cm o d e ，t h ec o o p e r a t i v ec o d i n gm o d e ，t h es h i f tm o d ea s w e l la st h ea m c = n d a t o r yc r cm o d e 5 a n a l y s i so f t h es i m u l a t i o nr e s u l t so ft h es t r a t e g i e s k e yw o r d s ：n e t w o r kc o d i n g ；c h a n n e lc o d i n g ；s p a c e - t i m ec o d i n g ；e n c o d i n g v e c t o r s i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含二! - 乙申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：堡璺旦丝盗塑塾整塑互龇塑猛盗 作者签名：至兰整 一日期：- 二醒丛年坠月生日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 瑟国固丝勉丕盗盟互施验缍建蹴 作者签名： 导师签名： 日期：圣芝之五年垒月上生- 日 日期：2 董! 兰年上! 月已日 大连理工大学硕士学位论文 1 绪论 1 1论文的研究背景以及意义 在目前已存在的计算机分组交换网络中，信息分组是通过在中间节点存储转发的 形式由信源节点传送到信宿节点的。对于中间节点来说，它只完成存储转发，寻找传 输路由的功能，并不对输入的信息进行任何编码操作。而目前传统的编码方式大多是 发生在数据链路层，以信道编码居多，其目的主要是为了提高信息传递的可靠性。但 是在网络的高层，例如应用层来进行编码是否会给信息的传输带来好处一直未有定论。 网络编码的核心思想就是改变网络中间节点的传统的存储转发功能，在这些节点的高 层将输入到该节点的信息分组进行融合再传输出去。 网络编码系统的这种特性为网络带了许多的好处。根据图论中最大流最小割原理 说证明的，如果已知源节点和目地节点之间的拓扑结构以及链路容量，那么就可以计 算出该网络的最大吞吐量来。通过网络编码的方法可以实现多播传输方式，源节点到 目地节点之间的最大吞吐量，使资源得以充分利用。具备了网络编码功能的节点从各 个输入链路获得信息，并对所有的输入信息进行编码，然后把编码好的信息传送给所 有输出链路。研究表明，网络编码除了能够提高系统的吞吐量之外，在信息的安全性， 降低传播的时延、数据压缩、均衡负载、减小网络中节点的能量消耗、提高网络的鲁 棒性等方面都有重要的应用【l 】。 网络编码的提出对于目前网络体系结构和设计有着十分深远的影响，能够更好的 开发网络互联的带宽资源。基于上述的原因，许多专家学者的开展了大量的对于网络 编码算法的理论研究。网络编码实际上是一门交叉的学科，它所涉及的领域包括了信 息论、代数、编码理论以及图论的相关知识【l 】。 但是对于网络编码的研究，目前还只是停留在理论阶段。由于实际网络环境十分 复杂，网络中间节点很难获取整个网络拓扑结构以及链路容量的信息。基于这种实际 情况，p h i l i pa c h o u ，y u n n a nw u 等人在随机网络编码的理论基础上提出了更加适用 于现实网络环境的实用网络编码的体系。该体系的提出为网络编码这项新兴的技术应 用于现实开辟了新的道路。虽然实用网络编码算法已经可以很好的适应实际网络的要 求，但是实用网络编码的体系目前还不是很成熟，尤其是在接收节点未知编码向量的 情况下，如果对于编码向量的保护不利，导致编码向量在传输过程中出现错误，那么 传输质量就会迅速的恶化。因此，低信噪比环境的网络中，如何避免实用网络编码系 统的通信质量恶化的问题，对于推动实用网络编码系统应用于实际的网络有着非常重 要的意义【l ，3 】。 实用网络编码系统的可靠传输策略研究 1 2 论文的主要工作 论文提出了基于实用网络编码系统的几种可靠的传输策略以及针对c r c 循环冗 余校验的重传策略提出了改进的减少能量损耗的重传策略。前者主要针对的问题是实 用网络编码系统中，编码向量可能会在传输过程中因受到噪声的干扰而产生错误，而 这种错误由于网络编码的特殊解码方式而被放大，使得数据的通信质量产生严重的下 降。而后者主要是针对循环冗余校验策而略提出的一种改进的，降低能量消耗的重传 保护模式。这种模式在低信噪比下既可以保证编码向量的正确性，又可以有效的减少 传输能量的损耗，对于一些诸如无线传感器网络这种对能量有效性要求高的网络，有 着重要的应用价值。本文的主要工作如下： ( 1 ) 简单介绍了网络编码的基本概念。 ( 2 ) 介绍了几种常见的网络编码的构造方式。 ( 3 ) 简单介绍了几种常见的差错控制编码的算法。 ( 4 ) 从理论和仿真结果证明实用网络编码系统存在的问题，并且提出了几种适 用于该系统的可靠传输策略以及减少传输能量消耗的改进的重传策略。 ( 5 ) 对于提出的策略进行仿真并对于仿真结果进行分析说明。 1 3 论文的内容与结构安排 全文的内容安排如下： 第二章：首先介绍了组播传输方式的概念，网络编码基本思想的提出以及发展现 状，然后说明了网络编码给网络通信所带来的好处以及应用价值。 第三章：介绍了几种常见的网络编码构造方式及规则，并给予评价。 第四章：在介绍了实用网络编码系统的编解码规则的基础上，提出了该系统存在 的通信质量恶化的问题以及问题产生的原因。 第五章：首先介绍了几种信道编解码算法以及联合编码思想，然后给出了几种解 决实用网络编码系统传输质量恶化的问题的方案，并且对于循环冗余校验方案提出了 基于减少传输过程中能量消耗的改进策略。对于所提出的算法进行仿真验证，并对仿 真的结果进行分析说明。 第六章：对整个文章进行总结，得出了基本结论。 大连理工大学硕士学位论文 2 网络编码概述 本章首先阐述了本文研究的问题中所涉及的一个关键背景知识，即计算机通信网 络中的组播技术。然后详细介绍了网络编码是如何提出的以及它的发展现状，网络编 码在网络通信中的应用价值以及几种常见的网络编码的构造方式。 2 1 组播技术简介 2 1 1 组播技术的提出背景 传统意义上分组交换的通信方式主要包括两种：一种是单播通信，即通信的双方 是一台信源主机和一台信宿的目的机；另一种称为广播通信，是在一台信源主机向网 络中其他所有主机主机发送消息的通信方式。当要将一台主机上的信息发送给网络中 的某些节点而不是所有节点时，若采用单播的方式，那么会由于信息的重复发送而浪 费了许多带宽资源并且增加了服务器的负担；如果采用广播的方式，因为信息会发送 给一些不需要该信息的节点，则也会浪费带宽资源，并且容易引起信息的广播风暴。 所以上述两种传输方式都不能很好的解决单发送节点多接收节点的问题。因此，组播 的思想就应运而生了。组播的基本思想是，源节点只向网络中发送一份数据数据拷贝， 这份数据拷贝中的目的地址是网络中某些确定节点的地址，只有该目的地址所指定的 节点可以接收主机发送的数据，网络中的其他主机则无法接收到该数据。 2 1 2 组播技术的应用价值 组播的发送方式可以很好的解决单信源多信宿的问题，实现了网络中单点到多点 的有效传输。在大量节省网络带宽的同时，更能减小网络的负载。目前，组播技术已 经成为与单播，广播并列的通信方式了。更为重要的是，我们可以利用网络组播的特 点，开发一些新的互联网功能，包括在线直播，远程教育，远程医疗以及实时视频会 议等互联网的信息服务。 2 1 3 组播的路由实现 将网络设想为由一些边和节点组成的集合，于是便可以用有向图g - ( 形e “p ) ) 来表 示该网络了。其中矿和e 分别代表有向图的节点和边，非负数c ( p ) 用来表示边e 上信 实用网络编码系统的可靠传输策略研究 息传输的容量上限。在这个信息网络中，组播方式即实现由一个信源节点s v 向多个 信宿节点t v 发送信息。传统的路由方式是在该网络中建立若干个组播树 锯( 既o ，每个组播树都将信源和所有的信宿连接起来。而传播的信息就是在这些 组播树的路径上传输。每个组播树可以达到的传输速率是由每个树最小割，m i n 。酏g ( e ) 的容量来决定的。当我们建立多个组播树，并且每个组播树中每条边上的信息满足 g ( 0 f ( 由，那么通过在不同的组播树上传输不同的信息，我们就可以获得更高的组 播速率。 2 1 4 组播技术的局限性 根据上述内容，我们可以知道组播的通信方式是依靠通信网络上建立组播树来实 现的。最大流最小割定理证明了，网络中两个节点之间的最大流量可以由最小割来计 算。同时，实现最大流的路径也可以由最大流算法找到。因此，在两个节点之间建立 通信时，我们可以在两个节点之间应用最大流算法，得到他们的最大传输速率。但是 在组播通信时问题就较为复杂了。组播树的建立通常被认为是一个n p 问题，因此一 般采用的方案是首先利用最大流算法找到信源节点与一个信宿节点之间的最大流以及 实现的路径，然后再依次寻找其他信宿与信源之间的路径。而在寻找信源与其他信宿 之间的路径时，通常就在原始通信网络中去掉信源与第一个信宿之间已经用过的路径。 之所以这样处理是因为传统的路由方式中，信息不能叠加，只能在中间节点进行存储 转发。组播树的建立就会导致信源与其他信宿节点之间的路径都不是以其最大流进行 传输的。这样会最终导致实际的传播容量小于最大流最小割定理确定的容量上限【2 】。 2 2 网络编码的提出以及发展现状 2 2 1网络编码的提出 1 9 2 7 年，m o n g e r 提出了最大流最小割理论：对于拥有单位容量边的无向图，总 存在着一个集合h ，这个集合是由一个源节点s 到一个目的节点t 的所有不相接的边 所组成的。这样，通过将信息在这个集合所组成的边上进行路由，我们可以获得s 到 t 可靠通信时的最大传输速率r ( s ，t ) = m i n c u t ( s ，t ) 。随后，在1 9 5 6 年，f o r d 和f u l k e r s o n 提出了寻找最大流的算法。这个算法随后被扩展到有向图中了【2 1 。 网络编码是由a h l s w e d e 等人在2 0 0 0 年提出的一个新的理论，其精髓来源于最大 流最小割定理。在其发表的文章“网络信息流”中，他提出了可以允许中间节点在转 发信息前对输入信息流进行编码，在信宿节点通过一定的译码算法解码出所需的信息 大连理t 大学硕士学位论文 从而实现网络多播容量的极限。之所以允许中间节点对输入信息流进行编码，是因为 传统的存储转发的路由方式不能实现最大流最小割定理已经证明了的网络最大流，所 以它并不是最佳的。研究表明，这种在中间节点对输入信息进行编码的方法可以大大 提高网络的吞吐量，充分利用网络中的链路资源，从而实现信息传输速率的上刚4 1 。 参考图2 1 所示的网络，我们可以对于网络编码提高网络吞吐量，充分利用链路 资源做以详细的解释。 图2 1源节点s 向两个接收节点多播信息 f i g 2 1 s o u r c esm u l t i c a s t st ot w or e c e i v e r st l ，t 2 图2 1 ( a ) 给出了一个组播网络。其中s 是信源节点，t l 和t 2 是两个目的节点，每 条边的信息容量均为1 比特每单位时间。如果网络中的节点只对收到的信息执行存储 转发的操作，那么此网络多播速率无法达到2 比特每单位时间。这是因为接收节点3 在每个单位时间里只能转发从节点1 和2 发送过来的两个比特中的一个，如果3 转发 从1 节点过来的信息，则接收节点t 1 可以达到的接收速率为2 比特每单位时间，但是 对于接收节点t 2 只能收到l 比特每单位时间。假设从源节点1 发送的信息位为b 1 ，从 源节点2 发送的信息比特为b 2 。图2 1 ( b ) 中的3 节点把分别从节点1 和2 过来的信息 b l 和6 2 进行异或操作，然后将编码的结果发送至节点4 ，于是接收节点t l 在一个单位 时间内收到了b l 和6 l + 6 2 ，它可以通过6 l + ( 6 l + 如) = 6 2 运算来还原b 2 ，也就是说，接收 节点t 1 在一个单位时间内相当于收到了b l 和6 2 两个信息。同理我们可以知道接收节 点t a 在一个单位时间内也相当于收到了b l 和幻。于是图2 1 ( b ) 的传送方法可以使得网 络的多播传输速率达到2 比特每单位时间【5 1 。根据上述说明，我们可知通过在网络的 中间节点进行功能扩展，使其具备简单的编码功能，就可以使得网络的多播速率达到 最大流最小割定理所证明的网络吞吐量最大值。 实用网络编码系统的可靠传输策略研究 2 2 2 网络编码的发展现状 自从网络编码的基本思想被提出以后，关于网络编码的研究如雨后春笋般蓬勃发 展起来了。目前，许多电信业公司以及世界知名的大学都有许多的研究人员在致力于 网络编码的研究。他们的研究方向也是多种多样的。目前对于网络编码的构造方式是 研究的热点问题。许多专家学者提出了针对不同的网络传输类型，来构造网络编码的 结构。 按照网络编码的构造方式，主要可以将网络编码分为以下几种。第一种是k o e t t e r 和m m e d a r d 等人在文献 4 】中为网络编码设计的代数构造方式。这种构造方式是在己 知整个网络拓扑信息的情况下，用一个系统转移矩阵来描述信源输入信息和信宿上接 收到的信息之间的关系，然后通过构造符合要求的系统转移矩阵来实现网络编码的编 码过程。另一种也是在已知网络拓扑的情况下，p s a n d e r s 提出的一种实现网络编码的 多项式时间算法，该方法将网络编码的构造进一步简化，将其复杂度从指数级降到了 多项式级，而且大大降低了网络编码中所采用的字母表的下限。上述的两种方法都是 在已知网络拓扑信息的情况下所提出的构造形式。与此同时，又有人提出了不需要知 道网络拓扑结构的网络编码构造方案。针对于多播传输的网络，h o 等人设计了一个不 需要知道网络节点分布情况的随机网络编码的运算法则，通过在有限域中随机选取系 数来实现网络编码。由于随机编码在各条链连路上以相等的概传播信息的，因此该方 案了保证传输的成功率。 而除了在构造编码方式之外，对于网络编码安全性分析上也取得了重大的进展。 北京邮电大学的李大霖，林雪红等人通过香农保密系统的理论，证明了网络编码系统 密钥信息率的下界。另外，对于网络编码思想应用于网络分布式存储，p 2 p 传输技术 等热门领域也取得长足的进步。 2 3 网络编码的特点 在a l s h e w e d e 提出网络编码的理论之初，其主要的出发点就是要通过在中间节点 增加编码功能来提高网络的吞吐量，使之达到最大流最小割定理所证明的吞吐量最大 值。随后经过专家学者的深入研究，发现网络编码的作用不仅仅局限于能够提高网络 的吞吐量，在降低发送单位比特所需的能量，减小传输延迟以及负载均衡等众多方面 都体现出了巨大的优势。 大连理工大学硕士学位论文 2 3 1提高网络的吞吐量 考虑如图2 2 所示的网络，链路的容量为b b s 。s l 与s 2 分别要以比特率，1 ，r 2 发 送各自的消息至节点e ，f 。他们需要共享链路c d 。因此链路c d 就成为一个瓶 图2 2 两个单播消息竞争一条瓶颈链路 f i g 2 2 t w ou n i c a s ts e s s i o n sc o n t e n d i n gf o rab o t t l e n e c kl i n k 颈链路。如果网络节点的功能还仅仅只是传统的存储转发，那么这条瓶颈链路就需要 被两个信息流复用该链路，即需要满足 ( r l , r 2 ) ：0 r l ，0 2 ，1 + 您姐) ，如图2 3 ( a ) 所 示。然而如果在节点c 进行网络编码，例如将两路信息用按位“异或”的方式合成一 组新的信息，使得新信息中含有原来两路信息的内容，则在一个时间间隔内发送新信 息就相当于同时发送这两路信息。在接收端e ，f 用同样的方式来对信息进行还原， 则可以有效提高信息的传输速率，使之满足 ( r b r 2 ) ：0 r l 召，0 t 2 ，信息b 由s 一 t 3 一 t 1 t 2 ) 。但是如果节点s 进行网络编码，在链路s t 2 上传送口+ 6 ，在t 2 上再利用 已经接收到的a 和时6 解码出b 的信息。则对于所有的三个接收节点，收到所有信息 的延迟只是两个单位时间。这样通过减少信息在传递过程中的跳数，就降低了信息到 达目的节点的时间延迟【2 j 。 2 3 4 负载均衡 现在的网络中，由于多播路由算法的问题，往往会造成网络流量的不均衡分布， 这种不均衡分布会严重影响网络的正常通信。现有的多播路由协议主要包括两种，即 基于核心的路由协议和基于信源的多播路由协议。基于核心的路由协议经常造成流量 过分集中于某一节点。而基于信源的多播路由协议也会由于多个多播树的叠加，造成 某一链路流量的过载，影响网络的服务质量。基于网络编码的多播方式，利用多条路 径进行信息数据的传输，可以平衡网络链路的负载【7 1 。如图2 6 所示，在一个每条边 的容量都是2 的网络中，要从源节点s 传送信息口，b 到三个目标节点r l ，r 2 与r 3 。 如果在传统的网络中传输，需要如图2 6 ( b ) 所示的5 条链路来传送这两个信息，但是 这种传输方式就没有能够利用节点2 的链路资源。而如果像图2 6 ( c ) 所示，使用网络 编码的技术之后，在链路上同时传送口，b 以及升6 的信息的话，这样就实现了用9 条链路来传递两个信息，每条链路只传递一个单位信息，并且每条链路资源都得以利 用，这样便达到了均衡负载的目的。另外，在传统的路由方式的网络中，需要1 0 比特 数据在网络中传输。而在使用了网络编码技术的网络中，只用9 比特就达到了目的， 这样也在无形中提高的带宽利用率。 b a , ba , b a , ba , ba , b ( a ) 链路容量( b ) 路由方式 ( c ) 网络编码方式 图2 6 路由方式与网络编码方式的网络负载比较 f i g 2 6 l o a dc o m p a r i s o no fi pa n dn e t w o r kc o d i n gb a s e dm u l t i c a s t 9 b 实用网络编码系统的可靠传输策略研究 2 4 网络编码的应用 在应用方面，网络通信的一个最重要也是最普通的应用就是将文件从服务器下载 到用户端。传统的文件下载是以组播方式将文件从服务器传送到用户端。但是如果忽 略延迟，这个过程就可以被视为将文件从服务器多播到一组用户端。从多播的角度来 看，网络编码在文件下载方面的应用可以增加吞吐量并且降低平均的下载时间。而在 分布式存储的应用中，网络编码同样可以起到重要的作用。当一个文件被分布式的存 储在一组不可靠的节点中并且节点有足够的冗余。比如一个m 大小的文件被分k 块x l ， 砣，酞长度均为m k 的数据，将其编码为刀( 胗七) 块长度依然为m k 的新数据y l ， 耽，。这些新数据都被分布式的存储在行个节点中。这样，只要接收到至少k 个节点的编码信息y 并且进行解码，就可以还原出原始的信息了。这种分布式的存储 方式可以有效的对抗节点间因为链路的失效而导致的无法下载的问题，并且能够在一 定程度上提高信息的安全性。而这种对于原始信息x l ，x 2 ，溉进行编码生成新的 数据y l ，y 2 ，”的算法，正是可以通过网络编码来实现的。 另一个可以应用到网络编码的领域是无线网格网络。这是一个在链路层上对于网 络编码的应用。k a t t i 等人提出了适用于无线网格网络的机会主义编码方案，该方案在 通信密集时可以有效的提高网络的整体吞吐量，并且相对于口网络层是透明的。 另外，网络编码还可以对相关信源的数据进行压缩【4 】，从而减少网络中传输的信 息量。而在信息安全领域中，网络编码可以产生一种基于数据包的随机网络编码检测 策略。对于信源数据进行简单的多项式函数哈希变换，然后把得到的结果添加到原始 信息中。根据信息加密的原理，在接收端只要对编码后的数据和哈希值进行判断就可 以知道数据包是否被修改过了，从而提高了信息安全的性能。 总之，网络编码的思想目前已经被证明可以有效的应用到网络通信的各个领域中 去。该技术已经日益成为现代网络通信世界里最不可或缺的一项技术了。 大连理t 大学硕士学位论文 3 几种主要的网络编码构造算法 本章首先介绍了网络编码的几个前提假设，然后详细说明了几种常见的网络编码 的构造算法以及这些构造算法的性能评价b 3 1 网络编码的前提假设 网络编码其实主要是指线性网络编码，因为研究表明，通过对输入信息进行线性 的组合编码就可以完全实现网络的最大流了。因此，我们后面所要介绍的几种编码的 方案都是基于线性编码这一基本思想，只是构造的方式不同而已。但是在介绍这些编 码构造方式的之前，我们首先要对网络做如下的假设： ( 1 ) 网络是非循环网络 ( 2 ) 容量为n 的路径可以被认为是刀条单位容量路径的并联。 ( 3 ) 每条边传输信号的时延是相同的。 ( 4 ) 网络中不存在因为噪声干扰而导致的传输错误，只存在由于节点和链路的无 效造成的信息丢失。 ( 5 ) 多个源节点的网络可以看成是只有一个虚拟源节点的网络。 对于假设的解释：( 1 ) 假定网络中没有环路存在是无时延网络的前提。( 2 ) 该假设 是为了实现两个节点之间有整数条路径连接。这样讨论两个节点之间的容量问题时， 就可以转化为讨论两个节点之间有多少条单位容量路径连接的问题了。( 3 ) 该假设避免 了讨论网络中传输不同步的问题，简化了理论研究。( 4 ) 因为网络编码操作是在网络体 系结构的上层来实现的。这也是我们考虑的主要方面，而一些差错控制编码是在网络 底层( 诸如数据链路层) 来实现的，不在理论的研究范围之内。本文所研究的是实用 网络编码系统中存在问题，因此在文章的后面我们主要讨论的是在实际的网络环境中， 实用网络编码系统出现传输差错时的一些解决方案。但在做理论的编码构造研究时， 先不考虑传输错误。( 5 ) 虚拟源的设定参见图3 1 。 图3 1 虚拟源节点 f i g 3 1d u m m y s o u r c en o d e 1 1 实用网络编码系统的可靠传输策略研究 将网络中实际的源看作是一个虚拟源点连接的第一层接收节点。如果实际源节点 每个时隙里有h 个信息要传送给其他节点，那么在虚拟源节点与这个实际源节点之间 的链接上，信息以h 个单位信息每单位时间速率传送。这就相当于是所有信息都是从 虚拟源通过实际源传送给接收节点的【5 1 。 3 2 线性编码多播 3 2 1线性编码多播算法的提出 s h u oy e n ，r o b e r tl i 等人在文献 6 中提出了一种线性网络编码的算法，称为线性 编码多播l c m ( l i n e a r - e o d em u l t i c a s o 。在该算法中，首先假设源节点s 所发送的所有 信息帧都是d 维的行向量，称为信息向量。源节点发送这d 维的信息，中间节点接收 到这些信息之后，形成中间节点的信息向量。 3 2 2 线性编码多播的编码规则以及评价 根据l c m 的编码规则，在信息向量生成的同时，源节点也为每一个信息向量分 配一个全局编码向量( g l o b a le n c o d i n gv e c t o r s ) ，该全局编码向量因为在每次编码过程 中都会根据每条链路所分配局部编码向量( l o c a le n c o d i n gv e c t o r s ) 而改变，因此全局编 码向量记载了某个信息在网络中经过不同的边所经历的编码的过程。整个的编解码过 程如下： ( 1 ) 中间节点发送信息的时候，首先将所有接收到的信息的全局编码向量组成一个 d * d 维的矩阵。 ( 2 ) 根据输出链路所分配的局部编码向量，让该d * d 维矩阵与局部编码向量做向量 乘法，得到一个新的全局编码向量。 ( 3 ) 用新的全局编码向量对d 维信息行向量做向量乘法，得到编码后的新数据。 ( 4 ) 在接收端解码时，将所有接收到的信息的全局编码向量组合成一个完成的矩阵 ，设原始信息位为x ，接收端得到的信息位组成的矩阵为z ，那么编码的过程相当于 x 辟z ，而解码的过程则为： 萨z f l ( 3 1 ) 文献【6 】中给出了数学意义上的l c m 选择边上的局部编码向量的规则： 定义3 1 一个通用的多播网络的线性编码方法是在一个传输网络g = ( n 目中， 其中y 是所有节点的集合，e 是所有边的集合，给每一个节点v 分配一个线性空间v ( v ) ， 每一条边( v ，砧分配一个向量坎f ，) 。源节点的向量之间的关系是： 大连理j f 人学硕+ 学位论文 ( 1 ) 坎s ) = q ( 2 ) v ( i ，) v ( g ) ，只要y ( f ，) e ( 3 ) 对任何非源节点的集合甲满足： ( 杪o ) ：v 、壬， ) = ( y ( f ，) ：f 甲) ，仨、壬，) ( 4 ) 节点输出边的向量是节点输入边向量的线性组合 其中， 是线性张成的意思。q 是d 维的向量空间，其中d 是信息向量的个数， 也是网络的最大流的最小值。( 1 ) 是指源节点的向量空间是d 维，即源节点同时发出d 个线性无关的信息。( 2 ) 的意思是对于某一个节点的输出链路所分配的局部编码向量都 属于该点的向量空间。( 3 ) 是表示某个非源节点的向量空间可以由其发出的边的向量线 形张成。( 4 ) 说明了输出的信息包含全部的输入信息。虽然信息的大小没有变化，但是 包含的信息量有了增加。 对于l c m 的网络编码构造方法，我们可知在网络无错误传输时，可以使网络中 的节点达到该节点理论上的最大流，实现了充分利用网络资源这一目标。但是该构造 方法也存在其局限性。比如说想要达到所有边的局部编码向量线性无关，在选择向量 的时候必须将生成的向量与已知向量进行比较，确定所有的已知向量是线性无关的。 当网络容量很大的时候，由于任意，2 维向量所组成集合的数量随网络的边数成指数增 长，验证相关性的算法比较复杂，因此该算法并不适用于大型的网络中【1 0 】。 3 3 线性代数编码 3 3 1线性代数编码的表示 在说明线性代数编码的原理之前，首先需要对网络做如下的代数定义：节点v 产 生的信息是离散的随机过程，用撤功= 徽u1 ) ，坝m 2 ) ，坝m 3 ) ，坦v 功) 表示。用 z ( 垆 z ( ，1 ) ，z ( v ，2 ) ，z ( 1 ，3 ) z ( 1 ，聊) ) 表示接收节点v 所接收到的信息。 对于网络中一条链路来说，其传输的信息用h p ) 表示： y 0 ) = e 口加x ( v ，卅既r ( e ) ( 3 2 ) 1 = 1 e h e a d l _ e 刎( e ) 其中系数嘶。与忽。都是取自有限域( 2 肌) 。而h e a d ( e ) 是指链路的起始点为p ， t a i l ( e ) 是指链路的结束点为e 。由此，就可以看出式3 2 的是指某条链路上传输的信息 是该链路上的起始点所产生的信息撮v ，d 乘以系数口，。逐位相加的和与起始点接收到的 实用网络编码系统的可靠传输策略研究 所有信息妖p ) 乘以系数愿。的逐位相加之和所组成的。因此，依据式3 2 ，在应用了 网络编码算法的网络中，对应的源节点的输出信息公式为： 】，q ) = 口f e x g ，) ( 3 3 ) 因为源节点没有信息输入，只有自身产生的信息，所以没有接收到的信息项。对 于中间节点而言，其输出的信息公式为： z = 。二 t m l ( e ，乞。) ( 3 4 ) 口：颤阳d k) 对于中间节点来说因为没有自身产生的信息，只是负责编码接收到的信息，因此 没有产生的信息项。而对于接收节点来说，其输入的表达式为： 雌) = 膨。谁) ( 3 5 ) e 。觑四七j = 训p ) 接收节点只有信息输入没有输出和信息产生，所以和中间节点一样也只有后一项。 根据上面的代数表示，我们便可以把网络编码问题转化称为在有限域( 2 脚) 的多项式 中寻找系数，。， t e 和t ，的问题。系数嘶愿，。和巳也称为局部编码向量系数。 3 3 2 编码规则以及评价 在线性代数编码中，我们引入一个转移矩阵的概念。转移矩阵m 表示网络输入输 出之间的关系。假设源节点s 输出的信息向量是z 接收节点t 收到的输入信息向量 为z ，那么根据转移矩阵的定义有： z = x m( 3 6 ) 这样，对于接收节点t 来说，只要已知转移矩阵m 以及其接收到的信息矩阵z ， 就可以根据： z 圹1 = x( 3 7 ) 求出原始的信息。当然，因为存在m 的逆运算，这便需要矩阵m 有非零解。因此， 如何求这样一个转移矩阵m 就成为线性代数编码的关键问题。下面介绍一下如何获得 网络的转移矩阵从 考虑如图3 2 所示的网络： 大连理t 大学硕士学位论文 x ( v ，1 般v ，2 ) 坦v 3 ) 图3 2 网络信息传输图 f i g 3 2 t r a n s m i s s i o no fn e t w o r ki n f o r m a t i o n 预v ，i ) 预v ，1 ) z ( v ，1 ) 源节点为v 。，接收节点为v 4 ，其余都是中间的转发节点。他们之间的链路用图3 3 来表 不： 图3 3网络节点之间的关系 f i g 3 3n er e l a t i o n s h i po f t h en o d e s 将图3 3 中的7 条边按照从源节点到接收节点的顺序作出边之间的关系，加入局部编 码向量，得到图3 4 。 实用网络编码系统的可靠传输策略研究 图3 4 网络节点之间局部编码图 f i g 3 4 l o c a lc o d ea m o n gt h en o d e s 定义转移矩阵f l a * 陋l 来表示整个网络中间节点对于信息的作用，e 指所有容量为单 位容量的边的数量。边上的信息向量乘以局部编码系数就是该边传输到另一条边的信 息。，的元素为： = 倍抛谢秽，) 限8 ， 定义网络源节点处的信源输出矩阵彳一旧为： 铲 翟铲袈川 9 ， 则信源的输出为： y = x a( 3 1 0 ) 而对于接收节点来说，其接收到的矩阵b l t t * m 的元素为： b u ：1 - 0 ，一( 其h e 他a d ) c 3 ， 则接收节点接收到的信息可表示为： z = y b ( 3 1 2 ) 那么对于一个给定的网络彳，f 和b ，则该网络的转移矩阵m 表示为 m = a ( i - f ) 1 8 r ( 3 1 3 ) 根据之前得到的结论：只要d e t ( m ) 不为零，那么接收节点就可以通过解码还原出原始 信息。因此，只要我们合理的选取局部编码向量系数，就可以实现解码。对于上面的 例子，系统转移矩阵膨为： 大连理工大学硕十学位论文