（信号与信息处理专业论文）新一代无线通信网中网络编码的应用研究.pdf

重庆邮电大学硕士论文 摘要 摘要 新一代无线通信网中，对传输速率和频谱的利用率的要求提高。网络编码作为 新一代无线通信系统的关键技术之一，它对改善移动通信的频谱利用率，优化网络 结构，降低误码率有着至关重要的作用。网络编码技术的主要优点是在中间节点将 来自不同信道的信息进行再编码，这样不仅可以节省信号传输所需要的时隙，还可 以在一定程度上降低由干扰、噪声、衰落等因素所引起的误码率，从而在无线频谱 资源紧缺的条件下，达到提高系统吞吐量，改善系统误码率，提高系统频谱利用率 的目的。 为此，论文在充分理解网络编码理论的基础上，主要研究分析了无线场景下的 传统网络编码、联合网络编码、物理层网络性能，特别是针对物理层网络编码的特 性，研究分析了它在典型无线衰落环境下的性能，以及其与典型数字调制方式结合 下的性能。具体主要工作如下几个方面。 首先，在分析网络编码基本原理的基础上，对传统网络编码方案与传统调度方 案进行了分析比较；由于信道的广播特性以及衰落、延迟和干扰等因素，传统编码 方案在抗衰落方面并不能取得理想效果，为此论文从抑制衰落、降低系统计算复杂 度等方面，在b s c 和a w g n 无线场景下，分别对联合网络编码和物理层网络编码 的误码率和吞吐量等性能进行了分析研究。 其次，考虑到无线信道特性对物理层网络编码性能的影响尤为重要，论文利用 典型的无线衰落信道特性，对物理层网络编码相关性能做了进一步的性能分析与研 究，一方面注重比较分析物理层网络与典型性的其他网络编码在这一无线场景下的 性能，另一方面着重从无线场景适应性出发比较研究适合不同无线场景的物理层网 络方案，从而优化编码方案。 最后，从典型通信系统角度出发，将网络编码与调制联合分析研究，研究了在 典型衰落环境下不同数字调制与网络编码结合的相关问题，从误码率和吞吐量等性 能进行了比较研究，从而优化不同应用场景下的网络编码与调制方案。 关键词：移动通信，无线信道，网络编码，物理层网络编码，数字调制 重庆邮电大学硕士论文 a b s t r a c t a bs t r a c t i nt h e n e x t - g e n e r a t i o nw i r e l e s s c o m m u n i c a t i o n s y s t e m ，t h er e q u i r e m e n t s o f t r a n s m i s s i o nr a t ea n dt h es p e c t r u me f f i c i e n c yh a v eb e e ni n c r e a s e d a so n eo ft h ek e y t e c h n i q u e sf o rt h ef u t u r ew i r e l e s sc o m m u n i c a t i o ns y s t e m s ，n e t w o r kc o d i n gh a sp l a y e da n i m p o r t a n t r o l e i ni m p r o v i n gt h e s p e c t r u me f f i c i e n c yo fm o b i l ec o m m u n i c a t i o n s ， o p t i m i z i n gn e t w o r ks t r u c t u r ea n dd e c r e a s i n gt h eb i te r r o rr a t e t h em a i na d v a n t a g eo f n e t w o r kc o d i n gi st h a te n c o d i n ga n dd e c o d i n go p e r a t i o n sa r ea p p l i e do nt h ed i f f e r e n t i n c o m i n gm e s s a g e so fa ni n t e r m e d i a t en o d e ，i no r d e rt os a v et h et i m es l o t so fs i g n a l t r a n s m i s s i o na n dr e d u c et h ee r r o rr a t ee a s e db yi n t e r f e r e n c e ，n o i s ea n df a d i n g t h e r e f o r e ， i tc a na c h i e v et h et a r g e to fi m p r o v i n gt h r o u g h p u t ，d e c r e a s i n gt h eb i te r r o rr a t ea n d i n c r e a s i n gt h es p e c t r a le f f i c i e n c ya g a i n s tt h el i m i t e dw i r e l e s ss p e c t r a lr e s o u r c e s h e n c e ，b a s e do nf u l lu n d e r s t a n d i n go fn e t w o r kc o d i n gt h e o r y , t h et h e s i sm a i n l y a n a l y z e dt h ep e r f o r m a n c eo ft r a d i t i o n a ln e t w o r kc o d i n g ，j o i n tn e t w o r kc o d i n g ，p h y s i c a l l a y e rn e t w o r kc o d i n g ，e s p e c i a l l yc o n s i d e r i n gt h ew o r k i n gc h a r a c t e r i s t i c so ft h ep h y s i c a l l a y e rn e t w o r kc o d i n g ，t h ep e r f o r m a n c eo fp h y s i c a ll a y e rn e t w o r ka l o n gw i t hs o m e p o p u l a rw i r e l e s sf a d i n ga n dd i g i t a lm o d u l a t i o n sa r ed i s c u s s e di nd a t a i l t h em a i nw o r k s a r el i s t e da sf o l l o w s f i r s t , t h et h e s i sa n a l y z e da n dc o m p a r e dt r a d i t i o n a ln e t w o r kc o d i n ga n dt r a d i t i o n a l d i s p a t c hs c h e m eb a s e do nt h ec o n c e p to fn e t w o r kc o d i n g b e c a u s eo ft h eb r o a d c a s t c h a r a c t e ra n df a d i n g ，d e l a ya n di n t e r f e r e n c ea n ds oo ni nw i r e l e s sc h a n n e l ，t h et r a d i t i o n a l n e t w o r kc o d i n gc a n tg e tp e r f e c te f f e c ti nr e s i s t i n gf a d i n g t h e r e f o r e ，f r o mt h ea s p e c t so f r e s t r a i n i n gf a d i n ga n dr e d u c i n gc o m p u t a t i o n a lc o m p l e x i t y , t h ep e r f o r m a n c e so ft h ej o i n t n e t w o r kc o d i n ga n dp h y s i c a ll a y e rn e t w o r k ，s u c ha se l r o rr a t ea n dt h r o u g h p u t ，w i l lb e a n a l y z e da n dr e s e a r c h e ds p e c i f i c a l l yi nt h eb s ca n da w g nw i r e l e s ss c e n a r i o s s e c o n d ，i nv i e wo ft h ei m p o r t a n ti n f l u e n c eo fw i r e l e s sc h a n n e lc h a r a c t e r i s t i c so n p e r f o r m a n c eo fn e t w o r kc o d i n g ，w ea n a l y z et h ep h y s i c a ln e t w o r kc o d i n gp e r f o r m a n c e b a s e do nt h ec h a r a c t e ro fw i r e l e s sc h a n n e l o nt h eo n eh a n d , w cm a i n l ya n a l y z ea n d c o m p a r et h ep e r f o r m a n c eo fp h y s i c a ll a y e rn e t w o r k 丽1t h eo t h e r s o nt h eo t h e rh a n d , f r o mt h ea d a p t a b i l i t yo fd i f f e r e n tw i r e l e s ss c e n a r i o s ，w ef o c u so n d i s c u s s i n gt h ep h y s i c a l l a y e rn e t w o r ks c h e m et h a ta c c o m m o d a t e st h ev a r i o u sw i r e l e s ss c e n a r i o sa n dt h e n o p t i m i z i n gt h es c h e m e h i nt h el a s t ，i nt h ep e r s p e c t i v eo fa t y p i c a lc o m m u n i c a t i o ns y s t e m ，w ea n a l y z ea n d r e s e a r c h e dt h ej o i n tn e t w o r kc o d i n ga n d d i g i t a lm o d u l a t i o ns c h e m ea n dt h er e l a t e di s s u e s o f j o i n td i f f e r e n td i g i t a lm o d u l a t i o na n dn e t w o r kc o d i n gi nt h et y p i c a lf a d i n gs c e n a r i o s ， a n dt h e n , t h ee l t o rr a t ea n dt h r o u g h p u tp e r f o r m a n c e sa l ea n a l y z e da n dc o m p a r e d ，i n o r d e rt oo p t i m i z et h es c h e m ei nd i f f e r e n ts c e n a r i o s k e y w o r d s ：m o b i l ec o m m u n i c a t i o n , w i r e l e s sc h a n n e l ，n e t w o r k c o d i n g ，p h y s i c a l n e t w o r kc o d i n g , d i g i t a lm o d u l a t i o n n i 重庆邮电大学硕士论文 主要符号对照表 主要符号对照表 数学符号符号说明 ，复数的共轭 量表示x 的估计值 g表示信道转移矩阵 ( 宰) 一矩阵的逆 e ( 木)( 幸) 的数学期望 。异或 v ( 1 表示向量空间 v i 重鏖堂皇奎兰堡主笙奎 茎奎堕量室 -_-_-_-_-_-_-_-_-_-_i-i_-_-_i_-_-_-_-_一一一一 英文缩写表 v i i 重庆邮电大学硕士论文第一章绪论 1 1 研究背景 第一章绪论 在通信技术飞速发展的今天，随着通信业务需求的不断扩展，传统的网络规划、 管理以及相应的网络信息容量的评估、利用效率和通信网络的工程使用都面临着巨 大的挑战。在特定的通信网络环境下，如何能够最大限度的利用信道容量传输信息， 并保证在较低误码率和时延的情况下接收到相应的信息引起了广大学者的关注与 研究。自2 0 0 0 年，杨伟豪、李硕彦教授【l 】等提出了网络信息流和网络编码( n c ) 的概念后，经过研究证明了在某些特定的环境下网络编码可以缓解甚至解决一些网 络中遗留的问题，比如信道容量的利用率，网络负载均衡等，因此网络编码受到了 很多关注，吸引了国内外众多研究者的兴趣。网络编码彻底改变了通信网络中信息 处理和传输的方式，是信息理论研究领域的重大突破，已经引起学术界广泛关注和 高度重视。国外许多著名大学，如普林斯顿大学、麻省理工大学、瑞士e p f l 学院 等以及多家r r 公司的研究中心，包括微软研究院、贝尔实验室、a t & t 的香龙信 息实验室等都在积极开展对网络编码理论和应用的研究，我国清华大学、南京大学、 西安电子科技大学等也对网络编码进行了探索。研究显示，在多播环境下与单一路 由相比，如果允许中间节点处理信息，可明显提高传输速率。进一步研究显示，网 络编码在提高网络吞吐量、改善负载平衡、减小传输延迟、节省节点能耗和增强网 路鲁棒性、安全性等主要方面都有很好的效果。 随着数字通信的概念和s h a n n o n 信息论的出现，信息传输网络化成为了学术界 的焦点。随之诞生的一个新的通信研究领域一网络信息论【2 1 ，它打破了传统的通 信网络模式，并将物理层纳入了网络容量的分析范畴。在网络信息论中，如何准确 客观地评估一个现有网络的信息容量，并使网络容量利用率和网络负载最大化，成 为了它所研究的问题；而不同网络之间的互联互通，以及网络资源互补等研究也是 网络信息化处理的重要研究课题。网络编码作为研究这些课题的关键技术之一，可 以改善网络的空闲度和网络资源的利用率，因为传统的通信网络理论将物理层看成 一个信息通信的管道，通过屏蔽物理层对网络层的影响，以排队理论为基础，通过 路由和交换处理信息，导致整个网络的空闲程度较高而网络资源利用率较低。 在无线通信网中，网络编码的出现推翻了之前的单一复制转发的传输方式，并 从理论上验证了它给整个通信系统带来的性能改善。无线信道的广播特性非常适合 重庆邮电大学硕士论文 第一章绪论 网络编码的特点，当一个节点传输一个数据包给它的一个邻居节点时，它的其它邻 居节点也可以接收到这个数据包。因此，当一个节点的邻居节点对不同的数据包感 兴趣时，可以将这些数据包编码后再一起传输，这样可以使其所有的邻居节点都收 到感兴趣的数据包并可以节约无线资源。应用网络编码可以解决传统路由、跨层设 计等技术无法解决的问题，提高网络吞吐量，尤其是组播容量：并可以减少数据包 的传播次数，降低无线发送能耗 3 1 ；当网络部分节点或链路失效时采用随机网络编 码，最终在目的节点仍能恢复原始数据，增强网络的容错性和鲁棒性等。 在新一代无线通信网中，由于i m t - a d v a n c e d 系统对传输速率要求的提高，对 频谱的利用率的增强，传统的路由传输方案已经不能够完全满足需求，因为传统的 路由传输方案在中间节点只对数据进行存储转发，不能充分有效的利用带宽，不能 达到最大网络传输速率。而网络编码作为下一代移动通信的关键技术之一，能够在 有限的频谱资源中尽可能多的传输数据，可以增加信道的传输容量。并将网络编码 与m i m o ( 多输入多输出) 相结合，充分利用m i m o 的分集特性，不仅能够抵抗 数据在传输过程中的丢包率和信道的衰落，还可以在误码率，传输速率等方面有所 提高【4 】。 除此之外，网络编码在网络安全方面有着非同一般的作用。因为网络编码使在 网络的任意中间节点对接收到的信息流进行组合编码然后再转发出去，所以窃听者 无法得到网络所传输的完整信息和源信息，并且网络编码的编码冗余度可以克服信 息传输过程中被篡改或者插入错误信息的问题。因此网络编码的研究在未来通信网 络的安全性和保密性的研究中也有着重大的意义【5 1 。 1 2 网络编码的发展现状与前景 2 0 0 0 年以来网络编码技术在众多学者的潜心研究下得到了充足的发展，从它 的基本理论、构造方案到编码方案和网络优化都有了很大的进展，为未来网络信息 论的发展奠定了坚实的基础。网络编码的核心是在网络的任意中间节点，对所接收 到的信息流进行分析，编码和转发，从而保证信息安全快速的到达目的节点。 1 2 1 网络编码构造方式的研究现状 网络编码的基本特征就是在网络层对传输的信息进行智能化处理，包括采用各 种编码策略。给定一个组播网络，如何设计网络编码并实现最大流传输是一个很重 要的问题。目前，人们提出了( 非) 线性网络编码，集中式网络编码以及分布式网 络编码，如图1 1 所示。 2 重庆邮电大学硕士论文 第一章绪论 其中线性网络编码和随机网络编码是目前应用最多的两个构造方案。线性网络 编码【6 】的中心思想是在中间节点对来自不同链路的信息流进行线性组合，然后再转 发出去，将节点传送信息线性映射到一个有限域内，通过这种处理从而实现最大流 的信息传输。而随机网络编码【2 1 是h o 等人给出了一种随机系数的分布式网络编码 算法，其编码系数从有限域中均匀随机选取。该方法对线性相关的信源具有信息压 缩作用，使用于链路动态变化的场景，当给定的字母表足够大时，能渐进达到最大 组播速率，具有很强的实用性，因而被广泛应用于各种网络中，如多播、中继等网 络，用来提高网络的传输容量、系统吞吐量等性能。而为了降低编码和等待延迟， 网络编码的机会调度策略在随机线性编码的基础上充分利用延迟时间传输数据，实 现流的“匹配”从而提高网络吞吐量。通过理论分析和证明【7 】，随机线性网络编码方 案在编码方案、运算复杂度和误码率方面有着很大的优势。但是在某些信道环境中， 非线性网络编码【8 1 的使用将会弥补线性网络编码方案的不足，比如在有噪信道中可 以有效降低失真，提供更好的网络性能。相对而言，其它的编码方式的研究和应用 较少。 广( 非) 线性 r 躺厂代溯络 网络编码构卜一集中式网络一 造方法i编码l 信息流型网 l 络编码 i广随机网络编 1分布式网络l 码 编码l l 确定型网络 1 2 2 网络编码方案的发展现状与前景 随着网络编码的不断发展，在理论方面的不断完善，它的应用问题被逐渐提上 了日程，无论是在中继网络还是在m i m o 网络环境下的网络编码方案不断地被提 出和创新，最终目的就是为了提高吞吐量和降低误码率和中断概率。目前有以下几 种方案被广泛关注，并得出了有效的研究成果，如图1 2 所示。 网络编码起源于有线网络，目的是改善网络传输信息的速率、控制丢包率、降 低时延等。但是随着性能的改善网络编码也会带来很多的问题，比如编码节点的选 择、网络路由的选取、节点间信息的交换与调度以及编码延迟等。为了消除这些负 重庆邮电大学硕士论文 第一章绪论 面影响，尽可能的达到网络传输的吞吐量极限，传统网络编码( t r a d i t i o n a ln e t w o r k c o d i n g ) 方案中使用了“流的匹配”和机会调度策略从而降低数据传输过程中的时延， 逼近网络传输吞吐量极限。但是在无线通信网中，由于信道中的噪声以及信号间的 干扰等因素，传统网络编码并不能够使数据的传输达到最优，并不能很好的体现网 络编码的作用。基于信道的广播特性以及衰落、延迟和干扰等因素，提出了将网络 编码同信道编译码结合，不仅可以提高信道容量还可以有效抑制衰落，降低系统的 误比特率和编码的复杂度。网络编码与信道编码相结合的思想是利用网络编码的冗 余支持信道编码从而获得好的抗噪声性能和误码率( b e r ) ，达到最大信道容量， 并充分利用中继传输的额外冗余度获得分集增益【9 】。由于无线通信的信息传输载体 是电磁波( e m ) ，传输界面是全开放的空间界面。而电磁波间的干扰会导致信号 间的混乱，因此提出了物理层网络编码( p n c ) 从物理层的角度去分析网络编码并 将之与信道中的各种特性和传输技术结合从而消除干扰降低b e r 。而物理层网络 编码与信道译码联合设计是利用电磁波的相加特性和t u r b o 码与网络编码的线性特 性直接对网络编码的码字进行估计。基于一种软判决检测和t u r b o 编译码，在双向 中继和多址中继信道中联合编译码可以在目的节点获得额外的分集增益并在中间 节点减少5 0 的计算复杂度。 广一 传统网络 i l _ 一物理层网 网络编硎 编码 方案 l l 一 联合网络 l 码一 i l 协作网络 码 编码 络 传统网络编码与信道编 译码联合设计方案 物理层网络编码与信道 编译码联合设计方案 m i m o 技术与网络编码 的联合设计方案 图1 2 网络编码方案图 在新一代无线移动通信系统中，面对复杂的无线场景和信道的衰落特性，网络 编码与无线协作分集技术、m i m o 技术相结合，在提高系统吞吐量、信道容量和分 集增益等方面具有极大的前景。协作分集技术【i o 】是通过节点间的协作，来获得较大 的分集增益，克服无线信道衰落。在协作分集的基础上进行网络编码能进一步的提 高分集增益和系统的性能，在获得分集增益的同时也能获得网络编码增益。在考虑 只有源节点a 和b 以及目的节点c 的模型中，节点a 和b 互相协作互为中继，将 数据包传输到目的节点c 。在发送节点a 和b 将接收到来自协作节点的信息( 中 继信息) 并将此信息译码与本地信息相结合( 网络编码和) ，通过判决检测和各自 的不同先验信息对得到的码字进行译码，并用循环冗余校来验检测节点是否成功译 码出了中继信息，并通过调制发送到目的节点。而目的节点根据来自发送节点a 4 重庆邮电大学硕士论文 第一章绪论 和b 中构成的码字以及信息的先验概率进行检测译码，恢复出所需信息【l l 】。而基 于m i m o 的联合网络编码技术是利用m i m o 技术的空间分集和类似的系统进行结 合，从而降低因路径损耗和衰落引起的丢包率，而网络编码通过在不同的包内编码 相同的信息，并利用获得的冗余度将接收到的能量传递给译码器，更好的完成检测 译码过程，获得大的信噪比增益，增强系统的鲁棒性、降低丢包率和误比特率【4 】。 1 2 3 基于网络编码的业务保密发展现状 从网络传输角度来看，信息的保密性主要涉及两类问题：一是传输的信息被窃 听，此时造成信息泄露；二是所传输的信息被篡改，此时导致信息的接收者无法正 确接收原始信息。由此可见网络的保密安全性十分重要。目前，搭线窃听和拜占庭 攻击是最常见的破坏数据安全传播的手段。由于密码学在使用领域以及计算复杂度 和数据传输速率等方面不是很好，而蔡宁等人研究了单信源有向无圈网络中数据安 全多播问题，给出了搭线窃听的网络通信模型，并且构造了在信息论意义下的安全 网络编码，即窃听者无论偷听所给定偷听范围内的哪个窃听集都无法恢复出原始信 息。而拜占庭攻击不仅能够组织双方的正常通信还能够从中获取一些有用信息，根 据攻击者的不同攻击能力它又可分为秘密共享模型，万能攻击者模型和有限的窃听 模型。而网络编码可以利用它的编码冗余度将这种信息分为被修改或者插入错误信 息问题。而这些问题常常发生在一些信息所经过的网络节点上【2 1 。 在实际通信网络环境中，通常信息传输会受到很多错误的影响，比如由信道引 起的随机错误，网络拥塞引起的数据包丢失以及由恶意节点故意改变或者创造的数 据包和包头错误。而网络编码可以用来检测和纠正网络中的错误。杨伟豪等人在经 典纠错码的基础上引入了网络纠错码【l2 】的概念，通过引入空间域的冗余代替时间域 的冗余来纠正网路通信中的错误。他们将经典纠错码的h a m m i n g 界、s i n g l e t o u 界 和g i l b e r - v a s h a m o v 界推广到网络编码，并提出了网络纠错码的解码原则一包括接 受节点处的解码矩阵和错误空间、接收节点处的消息空间、错误模式的秩以及网络 纠错码的最小距离等。而张珍在此基础上将线性网络编码与纠错码进行了融合，提 出了线性网络纠错码。 1 3 网络编码的关键技术 网络编码的具体操作是在中间节点对所接收到的信息流处进行随机线性编码， 然后再进行转发。其中最关键的两个技术点就是编码算法和转发方式。目前网络编 码的编码算法有异或算法和置信传播算法，而转发方式有译码转发 重庆邮电大学硕士论文 第一章绪论 ( d e c o d e a n d - f o r w a r d , d f ) ，放大转发( a m p l i f y - a n d - f o r w a r d , a f ) ，映射转发 ( m a p a n d f o r w a r d , m f ) ，除噪转发( d e n o i s e a n d - f o r w a r d ，d n f ) 和联合译码转发 ( j d f ) 。除此之外，在物理信道中不同的调制方式对网络编码以及整个通信系统 的性能有很大的影响，通过不同的调制方式或转发方式可以使网络编码的性能达到 最优。 1 4 论文结构 本文首先介绍了网络编码技术的研究背景、发展现状及其关键技术：进而介绍 了网络编码的相关理论，从编码原理、构造方式到编码方案进行了逐一分析介绍， 并对网络编码方案进行了性能分析与改善，最后我们将网络编码方案应用在新一代 无线场景中，并对其性能进行了分析比较和改善，具体内容和工作如下： 本文共分为五章。第一章绪论，介绍了网络编码的研究背景、目的和意义，然 后描述了自网络编码产生以后至今的发展现状以及编码的关键技术，最后为本文的 论文结构介绍。论文第二章，主要介绍网络编码技术的相关理论知识，首先详细的 阐述了网络编码的具体定义和基本原理，在此基础上讲述了目前编码的几种构造方 式，最后重点描述了网络编码的几种编码方案，从传统网络版面到物理层网络编码 进行了逐一的分析介绍，为后续章节奠定了理论基础。论文第三章，针对不同编码 方案进行了性能分析与比较，首先分析了传统网络编码优势和不足，而联合网络编 码与物理层网络编码方案是相对于传统方案在某些性能上的一种完善和改进，最后 分析了物理层网络编码在不同调制方式下的性能，并分析出了适合此方案的调制方 式。论文第四章，首先分析了无线衰落环境下的传统网络编码的性能，从它对系统 误码率以及系统容量的角度深入阐述了它的优缺点，并针对传统传输方式进行了性 能比较。随之我们重点分析了物理层网络编码的性能，并通过不同场景下和不同方 案的性能比较，从而看出其对系统性能的影响，并针对其不足之处进行了改进，即 采用p n c 与调制方案进行结合，从而优化典型衰落环境的物理层网络编码方案。 论文第五章是全文的总结，并根据现有的研究工作提出了未来可以研究工作的 方向。 6 重庆邮电大学硕士论文第二章网络编码的相关理论 2 1 引言 第二章网络编码的相关理论 继a h l s w e d e 等人于2 0 0 0 年以著名的“蝴蝶网络”模型为例，阐述了网络编码的 基本原理后，l i 等人证明了使用线性网络编码已经足够达到网络多播容量。m e d a r d 等人提出了网络编码的代数框架，并证明了存在满足多播容量的线性时不变编码， 后两者的工作为网络编码的发展准备了必要的理论条件。随机网络编码是由h o 、 m e d a r d 等人在2 0 0 3 年提出的，它的提出拓展了网络编码的使用场景，使得网络编 码不再局限于确定的网络拓扑和集中式的算法。c a i 利用分布式网络编码来纠正整 个网络中的差错，并论述了网络编码在安全方面的应用，为网络编码增加了新的应 用领域。经过这几年的迅猛发展，网络编码从最初用来达到有线网络中的组播容量， 发展到有线和无线网络中提高吞吐量、节省能量、增强鲁棒性和安全性，甚至改变 网络结构、改变网络协议设计方法，可以说网络编码正在给现有的网络带来革命性 的变化。 网络编码使网络节点不仅可以对数据进行存储转发，还可以进行编码处理，从 而提高信息的传输速率，但是它的优点不只这些，它可以说是信息论领域的一个里 程碑，推翻了独立的比特流不能再被压缩的结论，并论证了网络信息流( n e t w o r k i n f o r m a t i o nf l o w ) 可以被压缩，从而改善网络的部分性能。下面介绍一下网络编码 的一些基本理论，并重点介绍联合网络编码、物理层网络编码和本文所用到的信道 模型。 2 2 网络编码基本概念 网络编码是一种基于网络层的编码技术，其核心思想是网络中参与传输的节点 上输出的传输数据，可以通过该节点多条输入上传输数据的某种线性或非线性变换 而得到，且参与传输的所有节点对数据变换可以保证最终所有接收节点正确恢复出 信源所发送的信息。在一定程度上也可以认为它是一种融合了编码和路由的交换传 输技术。 下面我们通过“蝶型网络”来具体说明网络编码的特点【1 3 】。如图2 1 所示，有向 图g 中s 为源节点，r 1 和比为接收节点即汇，其它节点为中间节点。设g 中每一 个有向链路为一个无噪信道，每个信道的容量为l b i t 。源s 有两个b i t s 的数据要组 7 重庆邮电大学硕士论文 第二章网络编码的相关理论 播给接收点r l 和r 2 。根据“最大流最小切割定理【l 】 传输的最大流为2 ，即汇点可 以同时接收到s 所发的数据。图2 1 ( a ) 是传统的网络传输方案，中间节点只有存储 和转发功能。由于c d 链路的最大容量为l b i t ，节点c 只能依次在2 秒内把信息b 1 和b 2 转发给汇，而r l 和r 2 会分别收到多余的b 1 和b 2 。如果在节点c 用网络编码， 如图2 1 ( b ) 所示，c 收到b l 和b 2 时就可以进行异或操作【l4 1 ，使b = 包o6 2 并将它通 过链路c d 传送到接受节点。在接受节点通过异或的加减法定理便可以译出b 1 和 b 2 。所以通过网络编码可以实现最大容量传输，而传统的传输方案不能有效利用带 宽进行最大容量的传输。 ( i ) ( b ) 图2 1 蝶形网络模型 与此同时，网络的其它性能也相应的得到了改善。在图2 1 ( a ) 中由于b 1 和b 2 不能同时在链路c d 中传输，所以从s 到接收节点的最大信息传输速率为1 5 b i t s 。 若节点0 使用网络编码如图2 1 ( b ) 示，在链路c - d 上传输b = 扛e b , ，接收节点可 以同时恢复出信息b 1 和b 2 ，其信息流速率为2 b i t s ，带宽利用率提高了3 3 。网 络吞吐量也得到了提高，可以证明在无环网络g | n e ) 中，经网络编码后的传输容量 是不使用网络编码的q l o g l v i 倍，其中q 是信源符号的全空间，m 表示通信网络中 的节点个数【l5 1 。网络编码使信息在传输过程中均匀分布于整个网络，有效的解决了 网络拥塞和传输瓶颈问题，从而使网络负载得到均衡。由于实际网络中的节点和链 路常会失效，从而影响组播网络的鲁棒性，通过网络编码可以实现基于接收者的组 播链路失效恢复，从而预防网络链接失效对网络链接的影响，提高网络的鲁棒性【1 6 】。 2 3 网络编码构造方法 2 3 1 线性网络编码 线性网络编码【6 1 的中心思想是在中间节点对来自不同链路的信息流进行线性 组合，然后再转发出去，将节点传送信息线性映射到一个有限域内。通过这种处理 重庆邮电大学硕士论文 第二章网络编码的相关理论 实现最大流的信息传输。给定一个通信网络的拓扑图g = “e ) ，它的一个线性编码 组播即l c m v ( ) 对网络中每个节点定义一个向量空间并给每条边分配一个向量。在 源节点处应尽可能的利用线性空间中线性独立的向量分配给不同的边，传输原始数 据包的线性组合向量，遵循编码规则以便在目的节点可以通过解线性方程得到原始 信息，但其接收包的数量至少要是原信息包的个数，才能有效的译出原始信息。而 每个非源节点定义的线性空间的维数等于该节点的最大流值即 d i m ( v ( f ) ) - - m a x f l o w ( f ) 。在信道x y 中传输的数据就是信息向量( 行) 与边向量v c x v ) 的乘积。对于无环网络，通过对网络中的节点按照某种顺序进行标号，并使得每条 边( 每个信道) 都是从标号小的节点指向标号大的节点，其l c m v o 就是向量空间 v ( x ) 和v ( x y ) 对每个节点x 和链路x y 的一个分配。而对于有环网络【l7 1 ，要引入时 间延迟指标，将循环网络转化成等价的无环网络，然后按照上述的非循环网络设计 相应的l c m 。相对于线性网络编码，非线性网络编码可以在某些信道或网络中弥 补线性网络编码的不足【l 引，从而实现更好的编码性能。 2 3 2 分布式网络编码 根据编码系数生成的随机性，分布式网络编码【l9 】可分为随机网络编码和确定性 网络编码。 1 ) 确定性网络编码 其基本思想将网络拓扑分解成多个子树，并保证每个子树的编码矢量属于其父 树编码矢量的扩张空间，且任意两个子树的共有信宿的编码矢量均线性无关。该方 法具有良好的可扩展性。但所需的字母表空间随节点规模呈线性增长，在多个节点 的网络中它的运算复杂度比较高，实用性不强。 2 ) 随机网络编码 h o 等人给出了一种随机系数的分布式网络编码算法，其核心就是每个网络节 点独立地随机选取一种映射方式将自己接受到的输入信息映射到相应的输出链路 上。通常情况下，该映射方式选取线性映射，即在一个有限域内每个输入信息流选 取相应的加权系数。利用这种方法在进行组播数据时，每个接收点可以以很高的概 率恢复出原始数据。在一个有单位延迟链路的存在可行解的组播通信网络中，网络 编码的系数都取自于有限域e ，则目的节点可以成功译码的概率至少为 ( 1 一d g ) 邛，其中d 为接收节点的数目，r 表示转接输入信号的随机组合的链路数。 2 3 3 集中式网络编码方法 9 重庆邮电大学硕士论文第二章网络编码的相关理论 1 ) 代数法 代数法【2 0 】的本质是通过对矩阵行列式的研究，来判定网络编码的存在性，并构 造网络编码代数法将构建网络编码问题归结为求解系统转移矩阵的问题，通过寻 找一组使行列式不为0 的参数来求解网络编码k o e t t e r 等人给出了网络编码构造 的代数框架，将系统转移矩阵m 分解为| t 1 个子矩阵m 1 ，m 2 ，mi t | ，通过 构造一组参数使得每个子矩阵的行列式非0 ，从而得到网络编码解基于代数法的 构造算法的优点在于可借助成熟的矩阵理论分析各类拓扑结构的网络编码问题，其 缺点是可扩展性差、计算量大。 2 ) 信息流法 信息流法【2 1 】利用解耦技术，将网络编码问题分解为确定编码子图和给子图分配 码字两个子问题分别求解。j a g g i 等人给出了一个多项式时间复杂度的网络编码构 造算法，分为两个步骤：首先采用流算法为每个信宿找到从信源到信宿的n 条边不 重叠的路径集合，然后采用贪心策略对已知路径的边按拓扑顺序分配线性码，并保 证任意信宿的n 条入边上的全局编码向量线性独立，且能扩张成有限域，从而获得 网络编码解。其优点在于解耦合的两个子问题可结合成熟的优化理论采用分布式算 法分别求解，难点在于保证所有信宿的入边上的编码向量均线性独立。 其中随机线性网络编码在编译码方面比较简单实用，目前它已被广泛用于多 播，中继【2 2 】等网络中。在有向组播网络中【2 3 】可达到最大组播速率，提高系统的吞 吐量，实现网络编码增益并可有效降低编码算法的复杂度。其编码算法有很多种， 主要解决的问题是如何有效求得每条链路对应的编码向量，并运用该编码向量进行 线性运算从而得出链路上所传输的信息向量。典型的编码算法有：贪婪算法【6 】，指数 时间算法【2 0 1 ，多项式时间算法【2 4 】等，其中多项式时间算法相对复杂度较低，具有 重要的实用价值。 2 4 物理层网络编码 物理层网络编码是将编码从m a c 层转向物理层，从物理层的角度对网络编码 进行改进并与信道的各种特性和技术相结合，更好的提高系统的吞吐量、信道容量、 数据传输速率并有效地降低误码率。 物理层网络编码【2 5 】( p n c ) 主要是针对无线通信系统提出的，其特征是合理地 利用无线传播的信息广播特性来提高无线网路中的信道容量。无线通信的信息传输 载体是电磁波( e m ) ，传输界面是全开放的空间界面。由于电磁波间的干扰会导 致信号间的混乱，因此在传输过程中简单的编码方案通过协调节点间的传输，对节 点正确接受到的数据比特流进行编码操作，包容数据干扰并要求中继节点可以同时 1 0 重庆邮电大学硕士论文 第二章网络编码的相关理论 将接受信号转化成输出信号，在目的节点正确译码，如此可以提高网络吞吐量性能。 但是如果节点不能正确地接收比特流，即电磁波是来自于多个信源重叠和相互干扰 的话，就可通过物理层网络编码在物理层设计一个装置来处理e m 信号的接收和调 制，再通过中间节点的调制解调技术，所增加的e m 信号将被映射成数据比特流， 则干扰就变成了网络编码中的算术操作。网络编码通过包容干扰来提高吞吐量必须 满足： 1 ) 中间节点能够同时将它所接受到的正确信号组合转发给目的节点。 2 ) 目的节点必须能够从所接受的信号中提取出中继节点转发给它的信息。 如果来自多个信源的电磁波彼此有重合且干扰严重的话，上述条件不能被满 足，中继节点不能正确接收信号的话就通过物理层网络编码( p n c ) 来解决这个问 题。主要思想是通过中继节点适当的调制解调技术，将电磁信号的自然叠加映射 为数字比特流的伽罗华域加法，即进行了网络编码。通过以下分析和比较来证明物 理层网络编码调制解调可以达到网络吞吐量的上限，相对传统传输方式和传统网络 编码，系统容量分别提高了1 0 0 和5 0 。 图2 2 双向中继信道 图2 2 所示是简单的三节点信息交换图，物理层网络编码只需要两个时隙就可 以完成信息的交换，而传统的网络编码需要三个时隙完成相同信息的传输，因为在 n 2 接收信号时，传统网络编码不能在同一个时隙同时接收来自n 1 和n 3 的信息， 这样会产生信号间的干扰或叠加，造成中间节点不能正确接收信息，从而产生编码 错误。而传统传输调度方案，需要四个时隙才能完成。 物理层网络编码是在调制解调的基础上进行网络编码，通过映射完成编码过 程。通过寻找一种合适的调制解调方案，使得在中间节点的e m 信号的相加映射到 g f ( 2 ”) ，从而简化操作，消除信号间的干扰。物理层网络编码过程如图2 3 所示。 图2 3 物理层网络编码流程图 在双向中继信道中【2 6 1 ，为了获得更好的信道容量和双向传输速率，提出了在中 继节点采用物理层网络编码方案并把双向信道分为多址接入信道( 第1 时隙) 和广 播信道( 第2 时隙) 。发送端对信号进行调制，在多址接入信道( 图3 ) 中通过与 重庆邮电大学硕士论文 第二章网络编码的相关理论 信道编码相结合，使两个发送信号相叠加并正确地传输到中继节点，在中继节点对 所接收到的数据进行判决并得到它的估计，然后通过信道译码完成节点的编码操 作。在第二个时隙将编码后的数据通过广播信道传输给接收节点，从而完成数据的 整个传输过程。编译码方案主要有三种：放大转发，去噪转发和联合译码转发。 图2 4 中墨和墨分别是节点1 和3 信息比特流，g 。和以是编码调制后的符号且 相互独立，并被同时送到中继节点。，是多址信道的输出，= q + 强+ 刀，其中刀是 高斯噪声。物理层网络编码通过多址信道中的映射和线性信道编码可以分别达到信 道容量的上限和下限，在信噪比高于5 d b 时上下限会重合，与传统的网络编码和简 单网络编码方案相比物理层网络编码的信道容量增益分别为3 2 和2 。而在多跳网 络中，与传统的传输方式和简单的网络编码相比，物理层网络编码可能会分别实现 1 0 0 和5 0 的吞吐量增加。 2 5 联合网络编码 图2 4 物理层网络编码的多址信道框图 2 5 1 传统联合网络编码 基于信道的广播特性以及衰落、延迟和干扰等因素，文献【2 7 】提出了将网络编码 同信道编译码结合，不仅可以提高信道容量还可以有效抑制衰落，降低系统计算复 杂度。网络编码与信道编码相结合的思想是利用网络编码的冗余支持信道编码从而 获得好的抗噪声性能，达到最大信道容量，并充分利用中继传输的额外冗余度获得 分集增益。基于t u r b o 码【2 8 】和低密度奇偶校验码( l d p c ) 1 2 9 的联合编码被广泛研 究，并在多址中继信道、时分复用双向中继信遄3 0 】以及b s c 和a w g n 信道中与传统 的编码方案进行了比较，显示了