（通信与信息系统专业论文）无线协同中继网络的多址网络编码技术.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究：【作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证二 弓而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处， 本人签名： 本人承担一切相关责任。 同期：凇l 曼! ll 鱼 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文t 作的知识产权单位属北京邮电人学。学校有权保留并向国家有关部门或 机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅：学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 1 7 1 期： 迦! 全：l ：! 垒 同期： 强l 窆! ! ! ! 里 无线协同中继网络的多址网络编码技术 摘要 网络编码是一种新型的信息处理机制，允许中继节点将多个接收 信息处理成一个综合的数据包后再发送，再在接收端联合多个相互独 立的数据包即可恢复原始信息。无线网络中中继节点的引入，可以有 效改善蜂窝小区的边缘覆盖。无线网络天然的广播特性非常适合网络 编码的应用，而网络编码混合信息的能力也可以有效地提高无线中继 网络的频谱效率。 本文主要研究无线协同中继网络中的多址网络编码技术。针对基 于单天线的单用户多中继单基站的上行多址网络，我们设计了一种多 时隙的复数域网络编码传输方案，允许多个中继节点依次将自身成功 解码的多个数据包随机网络编码后发送，基站联合多个直射路径和中 继网络编码路径恢复原始信息，并从遍历容量，中断概率，误码率的 角度进行了性能分析，得到了遍历容量的闭式解以及中断概率和误码 率在高信噪比情况下的近似闭式解，同时与传统的机会中继方案进行 了性能比较，证明了网络编码能够带来的性能优势。 针对配置多天线的多用户单中继单基站的上行多址网络，我们提 出了一种基于数字域网络编码的传输机制，在中继节点处进行数字域 网络编码，在不了解信道状态信息的情况下随机选择天线满功率发 送，在基站通过多天线进行接收分集，并与传统的中继方案以及正交 空时编码的传输方式进行了性能比较，从遍历容量和中断概率的角度 分析了三种传输方案的性能以及天线个数对系统性能的影响。 关键词：网络编码中继协同多址 m u i r i p l ea c c e s s i n gn e t w o r kc o d i n gi n w i r e l e s sc o o p e r a t i v er e l a yn e t w o r k s a b s t r a c t n e t w o r kc o d i n gi san e wk i n do fs i g n a lp r o c e s s i n gm e c h a n i s m i t a l l o w st h er e l a yn o d et oc o m b i n em u l t i p l em e s s a g e st ob eas i n g l e i n t e g r a t e do n ef o rf o r w a r d i n g a n dt h e nt h ed e s t i n a t i o nc a nr e c o v e rt h e o r i g i n a lm e s s a g e sw i t hs e v e r a li n d e p e n d e n tc o m b i n e dv e r s i o n s t h er e l a y n o d ei m p o r t e dt ot h ew i r e l e s sn e t w o r ki st oi m p r o v et h ec o v e r a g ea tt h e e d g eo ft h ec e l l t h eb r o a d c a s t i n gn a t u r eo fw i r e l e s sn e t w o r ki sq u i t e s u i t a b l ef o rt h ea p p l i c a t i o no fn e t w o r kc o d i n ga n dt h em i x i n ga b i l i t yo f n e t w o r kc o d i n gc a ne f f e c t i v e l yi m p r o v et h es p e c t r a le f f i c i e n c yo ft h e w i r e l e s sr e l a yn e t w o r k i nt h i sp a p e r , w es t u d ym u l t i p l ea c c e s s i n gn e t w o r kc o d i n go ft h e w i r e l e s sc o o p e r a t i v er e l a yn e t w o r k f o rt h es i n g l ea n t e n n ab a s e dw i r e l e s s u p l i n km u l t i p l ea c c e s s i n gn e t w o r kc o n s i s t i n go fas i n g l es o u r c e ，m u l t i p l e r e l a y sa n das i n g l eb a s es t a t i o n ，w ed e s i g nam u l t i t i m e s l o t sc o m p l e xf i e l d n e t w o r kc o d i n g ( m t n c ) s c h e m e i nm t n c ，t h er e l a yn o d e sp e r f o r m r a n d o mn e t w o r kc o d i n go nt h em e s s a g e ss u c c e s s f u l l yd e c o d e d ，a n dt h e b a s es t a t i o nr e c o v e r st h eo r i g i n a lm e s s a g e sb yj o i n tp r o c e s s i n go ft h e d i r e c ta n dr e l a yp a t h w ea n a l y z et h ep e r f o r m a n c ef r o mt h ev i e w p o i n to f e r g o d i cc a p a c i t y , o u t a g ep r o b a b i l i t ya n ds y m b o le r r o rr a t e ，a n do b t a i nt h e c l o s e df o r mo fe r g o d i cc a p a c i t y , t h ea p p r o x i m a t e dc l o s e df o r mo fo u t a g e p r o b a b i l i t ya n ds y m b o le r r o rr a t ew i t hh i g hs n ra s s u m p t i o n a l s ow e c o m p a r et h ep e r f o r m a n c eo fm t n cs c h e m ea n dt h et r a d i t i o n a lb e s tr e l a y s c h e m e f o rt h em u l t i p l ea n t e n n a sb a s e du p l i n km u l t i p l ea c c e s s i n gw i r e l e s s n e t w o r kc o m p o s e do fm u l t i p l eu s e r s ，s i n g l er e l a ya n ds i n g l eb a s es t a t i o n ， w ep r e s e n tag a l o i sf i e l dn e t w o r kc o d i n gt r a n s m i s s i o ns t r a t e g y i nt h e s t r a t e g y , t h er e l a yp e r f o r m sn e t w o r kc o d i n go nt h em e s s a g e sr e c e i v e d p r e v i o u s l y , s e l e c t sa na n t e n n ar a n d o m l yi n t h ec o n d i t i o no fn oc h a n n e l s t a t ei n f o r m a t i o n ，a n dt h e nt h e b a s es t a t i o nc a no b t a i n t h es o u r c e m e s s a g e sw i t hr e c e i v i n gd i v e r s i t y w ec o m p a r et h ep e r f o r m a n c eo ft h r e e k i n d so fs t r a t e g i e s ，t h ep r o p o s e dn e t w o r kc o d i n go n e ，t h et r a d i t i o n a l r e l a y i n go n ea n dt h eo r t h o g o n a ls p a c e - t i m ec o d i n gb a s e do n ef r o mt h e p e r s p e c t i v eo fe r g o d i cc a p a c i t ya n do u t a g ep r o b a b i l i t y a n dw eg e t t h e p e r f o r m a n c eg a i no fn e t w o r kc o d i n ga n da l s ot h er e l a t i o n s h i pb e t w e e n t h e a n t e n n an u m b e ra n dt h es y s t e ms p e c t r a le f f i c i e n c y k e yw o r d s ：n e t w o r kc o d i n g ，r e l a y , c o o p e r a t i o n ，m u l t i p l ea c c e s s i n g 北京邮电大学2 0 1 0 届硕：e 毕业设计( 论文) 目录 第一章概述1 1 1 无线中继网络和网络编码简介。1 1 2 本文的j r 作3 第二章无线中继网络和网络编码5 2 1 无线中继网络5 2 2 网络编码6 2 2 1 网络编码概述：6 2 2 2 网络编码的优势7 2 2 2 1增加网络流量7 2 2 2 2提高网络健壮性8 2 2 2 3均衡网络负载8 2 2 3线性网络编码的编解码过程9 2 2 3 1 编码过程9 2 2 。3 2 解码过程1 1 2 2 4 物理层网络编码1 2 2 2 4 1 物理层网络编码的简单举例说明1 2 2 2 4 2 物理层网络编码的调制解调映射原则1 5 2 2 4 3 物理层网络编码在多跳线性网络中的应用1 8 2 2 5 网络编码在无线多址网络中的分集增益分析2 2 2 2 5 1 系统描述2 2 2 2 5 2 性能分析2 4 2 2 6 网络编码在双向中继网络中的应用2 6 2 2 6 1 方案描述2 7 2 2 6 2 性能理论分析3 0 第三章上行多址网络中的网络编码性能分析3 5 3 1 概j 2 睦3 1 ； 3 2 系统模型及传输方案描述3 6 3 2 1 系统模型3 6 3 2 2 传输方案描述3 6 3 3 理论分析3 7 3 3 1 网络编码方案( m t h c ) 。3 8 3 3 1 1m t n c 方案的互信息3 8 3 3 1 2m 1 n c 方案的遍历容量4 0 3 3 1 3m t n c 方案的中断概率。4 0 3 3 1 4m t n c 方案的误码率。4 1 3 3 2 机会中继方案( r r ) 4 2 3 3 2 1r r 方案的互信息4 2 北京邮i 乜人学2 0 1 0 届硕1 ：毕业设汁( 论文) 3 3 2 2r r 方案的遍历容餐4 3 3 3 2 3r r 方案的中断概率4 3 3 3 2 4r r 方案的误码率4 4 3 4 仿真结果4 5 3 4 1 遍历容量的比较。4 5 3 4 2 中断概率的比较4 5 3 4 3 误码率的比较4 6 第四章多天线场景上行多址网络中的网络编码性能4 8 4 1多天线简介4 8 4 1 1 m 1 m o 系统描述。4 8 4 1 2m i m o 系统的容量4 8 4 1 3 m i m o 系统空时编码方案设计5 0 4 2 4 3 基于多大线的网络编码机制概述5 1 系统模型及传输方案5 2 4 3 1 系统模型5 2 4 3 2 传输方案描述5 2 4 4 理论分析5 3 4 4 1 普通中继分集方案( t d m a d f 5 3 4 4 1 1t d m a - d f 方案的互信息5 3 4 4 1 2 t d m a d f 方案的遍历容量5 4 4 4 1 3 t d m a - d f 方案的中断概率5 5 4 4 1 4 t d m a - d f 方案的分集度5 6 4 4 2 正交空时编码方案( o s t c d f ) 5 7 4 4 2 1o s t c d f 方案的互信息5 7 4 4 2 2o s t c d f 方案的遍历容量5 7 4 4 2 3o s t c d f 方案的中断概率5 8 4 4 2 4o s t c d f 方案的分集度5 9 4 4 3 基于网络编码的分集方案( n c d f ) 6 0 4 4 3 1n c d f 方案的互信息6 0 4 4 3 2n c d f 方案的遍历容量6 0 4 4 3 3n c d f 方案的中断概率6 l 4 4 3 4 n c d f 方案的分集度6 2 4 5 数值结果6 2 4 5 1 遍历容量的比较6 2 4 5 2 中断概率的比较6 3 第五章总结与展望6 5 i i 北京邮电大学2 0 1 0 届硕：i = 毕业设计( 论文) 第一章概述 网络编码是一种新型的信息处理机制，允许中继节点将接收到的多个信息进 行综合处理之后再发送，接收端则按照相应的规则解码来恢复原始信息，可以有 效地提高网络的吞吐量和鲁棒性。中继技术在无线网络中的应用，主要目的是 改善小区边缘用户的性能，通过中继节点来协助用户与基站之间的信息传输，可 以获得一定的分集增益。网络编码和中继技术本是两种相互独立的技术体制，但 是考虑到无线蜂窝网络中中继，时隙等资源的有限性，因此在采用中继节点改善 传输性能的同时，需要通过网络编码来提高中继节点以及时间等各种资源的利用 率，从而达到有效性与可靠性的统一。 1 1 无线中继网络和网络编码简介 未来的无线通信系统中，要求能达到很高的频谱效率，不论是对于小区中心 的用户还是对于小区边缘的用户，而小区边缘的用户通常由于距离问题和相邻小 区的干扰等导致性能较差，因此，中继技术被应用在蜂窝小区中以改善小区边缘 用户的性能。中继节点乜1 的处理方式主要可以分为a f ，d f 两种，所谓a f 是指 放大转发，即针对模拟信号的处理，按照接收机灵敏度的要求。，对接收的模拟 信号进行一定的放大之后再发送，当然，同时得到放大的也包含噪声；而d f 则 是解码转发“1 ，也就是说首先会执行与发送相反的过程，解调解码判决等，得到 原始发送的数据信息，而后再将该数据信息进行一系列的调制解调后再发送，这 种解码转发的机制可以避免噪声的放大问题，但是有可能解码的结果本身就是错 误的，因此可能会导致错误传播。鉴于此，形形色色的改进版本如c f ( 压缩转 发) ，e f ( 估计转发) 等也被提出来以改善网络性能。 网络编码饰1 于2 0 0 0 年由香港中文大学的a h l s w e d e 等提出，打破了传统的中 继限制一中继节点只负责存储转发，而允许中继节点对接收到的多个数据信息进 行一定的线性或者非线性的处理嘲，处理成一个综合的数据包再发送，从而解决 了中继节点处多个数据包的排队时延问题，而接收端联合多个来自不同路径的相 互独立的网络编码数据包，即可恢复出原始的发送信息口1 。对于某接收节点而言， 只需要接收到足够数量的相互独立的数据包即可恢复原始信息，而不必局限于某 个特定的数据包，因此，网络的鲁棒性可以得到提高。对于某个网络编码的综合 数据包而言，该数据包对于多个接收节点处原始信息的恢复都是有效的，因此， 可以达到一定程度的资源共享，从而有助于提高网络的吞吐量。对于具体的网络 北京邮电大学2 0 1 0 届硕i ：毕业设计( 论文) 编码方式，相对于节点而言，由局部编码向量决定，相对于链路而言，由全局编 码向量决定。从确定与否的角度来看，网络编码方式可以分为确定网络编码和随 机网络编码两种睛1 。所谓确定网络编码是指，局部编码向量事先通过信令确定； 而随机网络编码则是指网络编码所需的系数是从固定大小的域中随机选择的，而 后编码向量和编码结果都要传送给接收节点。 无线网络具有天然的广播特性，而网络编码可以充分利用这一广播特性来提 高数据传输的频谱效率，同时，无线网络存在链路状况恶劣的问题，也需要网络 编码来改善传输性能，因此，将网络编码和无线网络结合起来是合适的，研究无 线中继网络中的网络编码是有意义的。 网络编码的当前研究热点主要有三个：网络编码机制的纯理论研究，网络层 的网络编码机制研究，物理层的网络编码机制研究。其中关于网络编码机制的纯 理论研究侧重具体的线性和非线性的网络编码方案，以及随机网络编码的域的大 小对网络编码性能的影响。网络层的网络编码机制首先集中在有线网络，而后拓 展到无线网络，主要是从网络层来分析相关的路由调度机制，分析网络编码所能 够带来的传输时延的降低，吞吐量的提高，鲁棒性的提高，主要的应用网络包括 有线网络，a d h o c ，m e s h 等。物理层的网络编码机制研究又可以分为三个方向： 双向中继网络的网络编码机制，下行组播网络的网络编码机制以及上行多址网络 的网络编码机制。 双向中继网络田1 的网络编码机制的典型应用场景是两个节点通过单个中继 交互信息，由于只有一个中继节点，所以存在两个节点之间的资源冲突，因此需 要通过网络编码来实现两个节点的资源共享，提高数据交互的频谱效率n 0 。 对于下行组播网络，存在的同样是中继节点的资源冲突，需要单个中继节点 为两个用户服务，所以需要在中继节点处对要发送给两个用户的信息进行网络编 码，从而使得一个编码的数据包对两个用户而言都是有效的，达到了一种资源共 享，提高网络的吞吐量。 上行多址网络中的网络编码机制1 中，同样存在两个用户之间的资源冲突问 题，因此藉由网络编码可以占用较少的资源实现上行数据传输，同时保证一定的 分集增益。 t a i r a nw a n g 在( ( c o m p l e xf i e l dn e t w o r kc o d i n gf o rm u l t i u s e rc o o p e r a t i v e c o m m u n i c a t i o n s ) ) 中提出了复数域网络编码的概念n2 l 。一般情况下，网络编码是 在g a l o i s 域中进行的，比如简单的异或运算。g a l o i s 域中的运算满足交换律，如 对于异或运算而言，在x l 与x 2 不等的前提下，置o x ：和x ：o x 。的结果是一样 的：而复数域网络编码则不同，同样是对于不同的x 1 与x 2 ，q 宰x l - i - 吼幸x ：和 晚事五- i - 0 1 拳x ：的结果是不同的。文章中还分析了复数域网络编码在多源多中继 2 北京邮f 乜人学2 0 1 0 届硕上毕业设计( 论文) 单接收节点场景下的分集增益，从理论分析和数字仿真两个角度证明了接收节点 所能够达到的分集度是虬+ l ( 其中心为中继节点的个数) ，因为总共有一条直 射路径和r 条中继路径。 x i n g k a ib a o 等人分析了多用户场景下的网络编码性能n 驯。整个传输过程分 成两个阶段：第一阶段，多个源节点依次广播自身信息，接收节点d 接收信息， 同时，当前时隙不发送信息的源节点监听信息；第二阶段，多个源节点作为中继 节点中继自己在第一阶段接收到的信息给接收节点d 。其中，第二阶段的方案有 三种：第一种是传统的中继方式，即对于每个源节点的数据，寻找最好的中继进 行中继传输，总共需要虬个时隙完成传输( 帆是源节点的个数) ；第二种是空 时编码的方式，即在第i 个时隙，所有成功接收到第i 个源节点数据的节点同时 传输信息给接收节点d ；第三种是网络编码方案，即所有的中继节点依次传输数 据，每个中继传输的是自己正确接收到的所有信息的网络编码结果。理论分析和 仿真结果表明，从遍历容量和中断概率的角度来看，空时编码方案的性能最优， 传统中继方案的性能最差，而网络编码方案的性能相对空时编码方案而言略差， 但其复杂度以及对于系统同步的要求大幅降低，因此是一种折中考虑后较优的方 案。 1 2 本文的工作 鉴于当前的研究现状，结合未来无线通信系统对高频谱效率的要求，本文主 要研究无线协同中继网络的多址网络编码技术。 针对单用户多中继单基站的上行多址网络，本文提出了一种多时隙网络编码 ( m t n c ) 的概念，将用户多个时隙发送的信息进行复数域随机网络编码后发送， 而后在基站处联合直射路径的信息和中继路径的网络编码信息，按照多输入多输 出( m i m o ) 系统中常用的处理方式，如z f , m m s e 等恢复用户的原始发送信息， 并且自互信息开始，从遍历容量，中断概率，误码率的角度对m t n c 方案以及 传统的机会中继方案进行了性能比较，得到了关于遍历容量的闭式解，中断概率 和误码率的数值解以及高信噪比情况下的近似闭式解，证明了网络编码在这种单 用户多中继单基站的上行多址网络的性能优势以及多中继选择对整个传输机制 分集度的影响。 不仅如此，考虑到多天线技术在未来无线通信系统中的广泛应用，本文设计 了基于多天线的多用户单中继单基站的上行多址网络中的网络编码机制，在发送 端不了解信道状态信息的情况下随机选择发送天线，在接收端通过多天线获得接 收分集增益，并且在网络编码阶段于中继节点处将多个用户的数据解码之后进行 数字域的网络编码处理，来获得多用户分集增益，同时与传统的中继转发方案以 3 北京邮i u 人学2 0 1 0 届硕： ：毕业敬计( 论文) 及基于正交空时编码传输的转发方案进行了性能比较，从遍历容量，中断概率的 角度来说，不论是理论分析结果还是数字仿真结果都证明了基于网络编码的传输 方案的性能增益，同时也说明了天线个数对系统分集度的影响。 本文的结构划分如下：第一章总体概述，第二章阐述无线中继网络和网络编 码的背景知识，第三章描述单用户多中继单基站系统模型下基于网络编码的传输 方案及其性能分析，第四章将系统模型扩展到了基于多天线的多用户单中继单基 站的上行无线中继网络，并进行了相关的分析，第五章则进行了总结与展望。 4 北京邮 乜大学2 0 1 0 届硕i ：毕业设计( 论文) 第二章无线中继网络和网络编码 2 1无线中继网络 近年，无线蜂窝通信系统中中继节点的辅助通信受到越来越多的关注，中继 节点的引入扩大了小区的覆盖范围，是满足小区边缘高数据率通信的一种低成 本、低复杂性的解决方案。协同通信是指无线网络中节点相互协作转发信息，构 成一个虚拟的m i m o 系统，从而能够在不增加天线数量的前提下，获得空间分 集增益，提高系统性能，抵抗信道衰落。因此，协同通信受到了广泛关注。目前 协同通信领域的研究热点之一是中继节点的选择问题，即在所有可能的中继节点 中，如何选择以及如何进行性能评估等。 从中继节点个数来看，中继方式主要分为两种：多中继( m r ，m u l t i p l er e l a y ) 方案和单中继( s r ，s i n g l er e l a y ) 方案。m r 顾名思义，是指多个中继节点共 同协助源节点与目的节点之间的信息传输，s r 则是只有一个中继节点进行中继 服务。m r 在获得较高的分集增益的同时要占用较多的信道资源，而且为了避免 干扰，需要为不同节点分配相互正交的信道，从而使得信道的调度分配比较困难。 而s r 的优点则是易于实现，但是分集度较低。 关于中继节点的选择，主要方案有中心式和分布式。中心式是指中继节点的 选择是由一个居于支配地位的中心节点来决定的，类似于蜂窝系统中的基站。在 中心式方案中，中心节点需要知道整个网络的全局信道状态信息，这需要大量的 信息反馈；而且在复杂多变的无线信道中，这样的反馈还要频繁进行，显然大大 增加了系统开销。分布式是指是否参与协作由各节点自行决定，适合于分布式的 网络，且避免了大量的反馈，但算法的复杂度较高。在近年来提出的协同通信方 案中，b l e t s a s 等人提出的机会中继( o r ，o p p o r t u n i s t i cr e l a y i n g ) 是比较合理 可行的。它是一种分布式的单中继方案，其关键之处在于各中继节点根据其与源 节点和目的节点的信道状况自行设置倒计时，通过竞争找出最佳的节点作为转发 中继节点。它保持了单中继方案的简单、易于实现的优点，同时达到了多中继方 案的分集阶数，且在中继节点的选择上付出的代价最小。b l e t s a s 分析了采用d f 的o r 方案o p p o r t u n i s t i cd f ( o d f ) 的中断概率，证明o d f 具有比采用m r 方 案的空时编码协作分集( s t c c d ，s p a c e t i m e c o d e dc o o p e r a t i v ed i v e r s i t y ) 更低 的中断概率。不过o r 沿用了固定中继的方式，即为中继节点固定分配信道，无 论目的节点能否正确接收，都要由中继节点向其转发信息，在一定程度上会造成 频谱效率的降低。 5 北京邮i 乜人学2 0 1 0 届硕+ i ：毕业使计( 论文) 2 2 网络编码 2 2 1 网络编码概述 网络编码技术n 钔是允许中继节点对已接收的多个数据包进行编码后再发送， 而接收节点通过相应的译码过程得到完整原始信息的信息处理技术。网络编码机 制可以提高网络的吞吐量。如图2 - 1 所示为无线双向中继网络的应用场景：节 点a 、b 相互传递信息a ，b ，网络编码机制下，节点a 本身的信息和接收的信 息可以用矩阵表示为丘呈1 ，即：接收信息为a x o r b ，本身信息为a ，从而可以 通过译码得到信息b 。可见，网络编码技术将整个传输时间从四个时隙缩减到了 三个时隙，降低了传输时延，提高了吞吐量。 传统方式 网络编码 a a 一b _ 一s b _ 叶b a t _ sb a s 一b - 一b a _ a x o rb - 一s a x o r 扣+ b 图2 - 1 无线双向中继网络中传统传输方式与网络编码技术比较 线性网络编码是指中继节点将接收数据在某有限域内进行线性组合在发送， 接收节点通过对接收信息的线性处理来译码。在算法设计上，主要有两种方案： 一种是完全确定的编码方案，它能保证网络实现最大流传输，并且所需的符号集 较小，但需要了解全网的拓扑情况，复杂度较高，难于分布式实现，而且一旦网 络拓扑结构发生了变化，就必须对整个编码方案进行修改，所以鲁棒性比较差； 另一种是随机网络编码方案，所谓随机编码是指每个编码节点随机地选取编码向 量，对输入信息进行处理，并把这组随机编码向量作为报头的一部分发送给接收 节点，以便于解码。随机网络编码可以解决分布式实现的问题，但是可能造成系 统传输矩阵奇异，导致接收节点无法恢复出原始数据。已有研究成果表明，当符 号集为无穷大时，采用随机网络编码，系统传输矩阵满秩的概率为1 ；而当符号 集为2 8 时，系统传输矩阵满秩的概率接近l 。 6 北京邮电人学2 0 1 0 届硕二 ：毕业设计( 论义) 2 2 2 网络编码的优势 2 2 2 1增加网络流量 网络编码可以实现网络的最大流传输，而且只通过线性网络编码即可，而中 继节点不能增加网络信息内容，所发送的信息只是接收信息内容的积累。 图2 - 2 所示是一个简单的网络拓扑。图中的箭头代表有向链路，假设每条 链路的容量为1 。其中s 为源节点，分别向y 和z 同时发送两个独立数据比特a 和b ，从而构成一组组播会话。 左图采用传统的组播技术，方法是让s t 、t y 、t w 和w z 信道传送比特a ， 而s u 、u z 、u w 和w y 传送比特b ，这样y 可以直接获得a ，而z 可以直接获 得b 。但是当a 和b 准备通过w 进行转发时，由于链路容量为1 ，a 或b 必须在 此排队等候一个单位时间。这样每个接收节点在单位时间内收到的比特数为 1 5 。 右图应用了网络编码技术，节点w 将a 和b 作模2 和运算后直接转发出去。 在收点y 处，根据接收到的a 和a0 6 ，即可恢复出b ；同理，在z 处也可以恢 复出a 。由于不需要排队，每个收点在单位时间可收到2 个比特。也就是说，此 时的编码增益为3 3 ，并达到了组播的最大流量。 图2 - 2 蝶形图中的网络编码方案 不难看出，不用网络编码，就不可能在单位时间从s 向y 和z 同时传递组 播信息，这充分证明了网络编码提高网络吞吐量的能力。对于一个多源多接收节 点的网络，只考虑其中一个接收节点时，对应该接收节点会有一个传输速率，网 络编码的功能在于，当所有的接收节点同时接收信息时，每个接收节点的速率仍 然可以保持，而不用网络编码时，由于多个接收节点之间的资源冲突，传输速率 一般会小于网络中只有一个接收节点时的情况。换言之，当有n 个接收节点共 享网络资源时，每个接收节点都可以达到最大的接收速率，整个网络仿佛只为这 7 北京邮i u 人学2 0 1 0 届硕 ：毕业设计( 论义) 一个接收节点所用。因此，网络编码有助于更好地共享网络资源。 网络编码不仅可以在组播网络中带来吞吐量方面的改善，在其他的传输场景 中也可以改善网络性能，如图2 - 1 所示的双向中继网络。 2 2 2 2提高网络健壮性 网络编码模式下，将原始信息包进行编码后发送出去，各编码数据包具有同 等的重要性，接收节点只要收到足够数量的数据包就可以进行解码，而不必拘泥 于某个特定的数据包，从而可以提高网络的健壮性和适应性。网络编码分布式地 存在于整个网络，而不仅仅存在于信源，这种特性与典型的分布式网络特性相适 应( 各节点只有关于整个网络的拓扑结构的一部分信息) ，使得网络编码不仅可 以用于集中式网络架构，还可以在分布式网络中应用。 如图2 一l 网络中，假设a 或b 在事先没有通知基站s 的情况下进入了睡眠 模式或者移出了网络覆盖范围，如果基站广播a 或者b ，由于期望的接收节点可 能无法接收，整个传输过程可能完全是一种浪费，而若基站广播口0 ) b ( 或其它 原始信息的线性组合) ，传输过程就可以为活动节点带来新的信息。 2 2 2 3 均衡网络负载 网络编码除了可以改善网络吞吐量和提高网络健壮性外，还可以均衡网络负 载，这一点可以通过下面的例子来说明。 图2 - 3 网络编码用于均衡网络负载举例 8 北京1 1 5 d a 人学2 0 1 0 届硕十毕业设计( 论文) b 图2 - 4 两种组播方式 如图2 - 3 所示的通信网络，各链路容量均为2 。图2 4 给出了此网络的两 种组播方式，一种是传统的组播树，如图2 - 4 的左图所示，另一种是基于网络 编码的组播图，如图2 - 4 的右图所示。可见左图实现的组播容量为2 ，也就是可 以同时传输2 个比特给每个信宿；而使用网络编码的右图的组播容量为4 。这是 网络编码在吞吐量上的改善，由于之前已有论述，因此吞吐量不是此处讨论的重 点。 这里要看的是，为了实现信源信息向所有信宿的组播，左图中的传输集中在 5 条链路上，而网络中的其他链路没有得到充分利用，处于空闲状态，这样必然 会引起所用链路上的拥塞，从而导致“瓶颈效应。而采用网络编码的右图与此 相反，其使用了网络中所有的链路来实现信息的传输，使信息在传播过程中，均 匀地分布于整个网络，从而有效地避免了“瓶颈效应 。可见，网络编码可以有 效地均衡网络负载。 2 2 3 线性网络编码的编解码过程 2 2 3 1编码过程 线性网络编码是将节点传送信息线性映射到一个有限域内，利用线性关系实 现编译码的过程。假设每个信息数据包长lb i t ，当它与要编码的数据包长度不 同时，较短的信息附加额外一串零。将包中的每s 个连续的比特组成只，域上的 一个符号，则一个包中包含l s 个符号。在线性编码模式下，运用乘法和加法运 算，使节点发送的数据包为该节点接收到信息的线性组合。 假设单个源或多个源产生的原始信息为m 190 0 7 m “，g ，g 。为相应的编码系 数，则线性网络编码后传输的信息为x = ，i ，& m ；假设对于每个符号位置编 码系数都相同，则有五= 罗王，g ，m 。，其中m 。和鼍分别为m 和x 的第k 个符 号。一般情况下为便于接收端解码，传输的信息包中既包括编码向量，即系数 9 北京l l i l l 人学2 0 1 0 届硕 ：毕业设计( 论义) g 。( g ，岛) ，又包括编码结果，即信息向量x 2 三。g ；膨。 编码过程可以迭代进行，若一个节点已经接收并存储的编码包的信息集合为 ( 9 1 ，x 1 ) ，皓“，x “) ，其中9 7 为第j 个包x ，的编码向量，则该节点可以通过选 定编码系数l l l ，吮和运用算式x = 2 。h ，x 得到新的信息包( g ，x ) ，而编码 r 句j r g 可以通过直接的代数计算得到：= 2 。h ，g ；。 可见，线性网络编码是对输入数据不断迭代进行线性处理的过程。 图2 - 5 具体说明了全局编码向量以及局部编码向量的作用。图中标于信道 附近的向量即为该信道对应的全局编码向量，意味着该条链路上传送的信息即为 源发送的信息向量与该信道的全局编码向量内积之后的结果；标于节点附近的向 量即为该节点对应的局部编码向量，代表了对输入信息的处理，比如对于节点w 而言，其局部编码向量是2 1 的矩阵，首先代表的是该节点的入度为2 ，出度为 ，、 1 ，其次具体的数值rl 代表的是对第一条链路的数据乘以w ，对第二条链路的 x 数据乘以x 而后将两个结果相加之后再发送出去。同时，节点的局部编码向量不 仅代表了输入链路与输出链路上数据之间的关系，同时也是输入信道与输出信道 的全局编码向量之间的桥梁，因为全局编码向量也是向量空间所传送的数据的一 种。 图2 - 5 蝶形图中具体的全局编码向量局部编码向量之间的关系 如果要从更一般的角度阐明局部编码向量，全局编码向量以及信道上传输的 数据之间的关系，则首先需要定义下列基本概念： 1 0 北京邮电大学2 0 1 0 届硕：l ：毕业设计( 论文) 觑似o u t ( t ) ：代表有向图中节点t 的输入信道，输出信道的集合。 砌：代表输入源节点的虚信道的集合。 z ：代表源节点欲传送的数据向量，也即网络编码向量空间的基。 f g f ( 2 5 ) ：代表信道上所传送的数据的域_ g a l o i s 域，该域上面的加减乘 除乘方等运算都可以转化为二进制数的移位以及异或运算，而且满足封闭性。 正0 ) ：代表信道e 上传送的数据信息，表示为x 的函数代表的是对原始信 息的处理。 k 一阮一】d 翮。汨咖o ) ：代表节点t 的局部编码向量，本身是一个m ( 1 l n ( t ) 1 ) 行 n ( 1 0 u t ( t ) 1 ) 列的矩阵，其中m 为节点t 的入度，1 1 为节点t 的出度；矩阵中的元素 为域f 上的数据。 五：代表信道e 上的全局编码向量，本身是一个行向量或者列向量， 则从图论的角度表征的网络编码的含义如下： l2 三，d ：输出信道的全局编码向量即为输入信道的全局编码向量并 置成的矩阵与节点本身局部编码向量的乘积。 输入信道d 与输出信道e 上传送的数据之间的关系： 石奉无圳三，屯，r 小d 酗，c 木肋 式( 2 1 ) 其根本含义在于局部编码向量不仅表征了输入输出信道全局编码向量之间 的关系，也表征了输入输出信道传送数据之间的关系。 2 2 3 2解码过程 假设节点接收集合为( 9 1 ，x 1 ) ，( g ”，x ”) ，为了恢复原始信息，需要求解 x = ：2 ，g f 7 m 的m 个等式中的n 个未知数mz ，要恢复所有数据要求肌苫疗， 也就是说，接收包的个数至少为原信息的个数。而有些线性组合可能是线性相关 的，因此m 刀并不是充分条件，而是网络编码能够成功解码的必要条件。 具体的解码可以采用高斯消去的方法：节点存贮编码向量以及编码之后的结 果，以行向量的形式，存储在解码矩阵中。最初，解码矩阵中只包含未经该节点 编码的包以及与之相对应的编码向量( 如果有的话，否则为空) 。当接收到一个已 编码包后，会从中抽取出它的编码向量以及编码结果，放入到解码矩阵中。解码 矩阵经过等价变换变成行阶梯型最终变成行最简型。所收到的某一个数据包如果 可以增加矩阵的秩，则称之为更新包，如果所收到的包是非更新的