（信号与信息处理专业论文）基于网络编码的中继传输模型与协议研究.pdf

重庆邮电大学硕士论文 摘要 摘要 目前，无线网络资源的需求在不断增长，而有限的网络带宽资源影响着无线通 信网络的发展。网络编码技术可以通过对传输数据进行编码压缩，使网络尽可能 多的容纳用户并且保证每个用户的服务质量，从而有效提高网络带宽资源利用率。 网络编码正大量的应用于无线m e s h 网、a dh o c 网、传感器网络和蜂窝无线通信系 统，同时其已经成为了当前通信领域的研究热点之一。 现有的提升网络资源利用率的技术主要是中继协作分集技术。该技术要求引入 大量的中继节点进行协作通信，使源节点到目的节点通过中继进行通信即单跳传 输链路转化为多跳传输链路，缩短了每一跳的通信距离，提高数据传输速率，扩 大通信网络的覆盖范围，增加系统容量。采用中继协作分集技术的蜂窝小区内， 源端用户的信号可经过多条不同的路径进行传输，接收端用户则通过合并经过不 同衰落路径的信号从而获得分集增益。但当小区内的用户数量大幅上升时，如何 能保持中继数量不变，而提升系统性能，这是该技术面临的关键问题之一。 为了解决上述问题，本文首先将网络编码技术应用到蜂窝小区的中继节点处， 在中继处分别采用解码转发网络编码( n e t w o r kc o d i n g - d e c o d ea n df o r w a r d ， n c d f ) 和放大转发网络编码( n e t w o r kc o d i n g - a m p l i f ya n df o r w a r d ，n c a f ) 传输机制，进一步改进中继传输协议。该方案下，单个中继能够同时为多个用户 服务，即能够减少所需的中继节点数量。仿真结果证明，n c - d f 和n c - a f 两种传 输机制与传统传输机制相比，提升了网络吞吐量、降低了中断概率并获得了编码 增益。 其次，本文提出了一种新的中继物理层网络编码( r e l a y - p h y s i c a ln e t w o r k c o d i n g ，r - p n c ) 传输机制。其在中继处引入物理层网络编码技术( p h y s i c a ln e t w o r k c o d i n g ，p n c ) ，并兼容了n c d f 能够消除干扰噪声与n c a f 可以节省传输时隙 的两个优点。仿真结果证明，与传统传输机制及n c d f 和n c a f 两种传输机制 相比，r - p n c 传输机制的在网络吞吐量、中断概率、编码增益等方面性能更加优 越。 最后，为了将r - p n c 传输机制有效应用于蜂窝小区中继处，本文设计了一种 新的帧结构，并剖析了r - p n c 传输机制的混合自动重传请求( h y b r i da u t o m a t i c r e p e a tr e q u e s t ，h a r q ) 流程，同时从所设计的r - p n c 帧结构上分析说明了其可 行性。 关键词：网络编码解码转发，网络编码放大转发，中继物理层网络编码，中继 协议，帧结构 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t r e c e n t l y , w i t ht h ei n c r e a s eo fw i r e l e s sr e s o u r c e sr e q u i r e m e n t ，t h ed e v e l o p m e n to f c o m m u n i c a t i o nn e t w o r ki sr e s t r i c t e dt or e s o u r c e sl i m i t e d n e s s n e t w o r kc o d i n g t e c h n o l o g yi sa b l et oe n h a n c en e t w o r kb a n d w i d t h u t i l i z a t i o ne f f e c t i v e l yb yc o m p r e s s i n g t r a n s m i s s i o np a c k e t s t h i st e c h n o l o g yh a sb e c o m et h ec u r r e n th o ts p o t ，a n di th a sb e e n w i d e l yu s e df o rw i r e l e s sm e s hn e t w o r k ，a dh o en e t w o r k , w i r e l e s ss e n s o rn e t w o r ka n d c e l l u l a rr a d i oc o m m u n i c a t i o n ss y s t e m f o r i m p r o v i n gt h en e t w o r kr e s o u r c e su t i l i z a t i o n ，e x i s t i n gt e c h n o l o g yi n c l u d e sr e l a y c o o p e r a t i v ed i v e r s i t ym a i n l y t h et e c h n o l o g y t a k em a n yr e l a yi n t o c o o p e r a t i o n c o m m u n i c a t i o na n dc o n v e r to n eh o pc o u n tl i n ki n t om u l t i - h o pc o u n t sl i n k ，i no r d e rt o s h o r t e nt r a n s m i s s i o nd i s t a n c ei ne a c hh o pc o u n t ，e n h a n c et r a n s m i s s i o ns p e e d ， e n l a r g e c o v e r a g ea n di n c r e a s es y s t e mc a p a c i t y i nt h ec e l l sw i t hu s i n gt h er e l a yc o o p e r a t i v e d i v e r s i t yt e c h n o l o g y , s o u r c es i g n a l i s t r a n s p o r t e db ym a n yd i f f e r e n tp a t h s ，w h i l e d e s t i n a t i o nm e r g e sa l lt h es i g n a l sf r o md i f f e r e n tp a t h st o g e t h e rf o rg e t t i n gd i v e r s i t yg a i n b u tt h e r ei sap r o b l e mi nt h i st e c h n o l o g y w h e nu s e rn u m b e ri n c r e a s e sd r a m a t i c a l l yi n c e l l s ，h o wt ok e e pr e l a yn u m b e rn o tc h a n g i n gw h i l ei m p r o v et h es y s t e mp e r f o r m a n c ei s a ni m p o r t a n tp r o b l e mi nt h i st e c h n o l o g y i no r d e rt os o l v ea b o v eo np r o b l e m ，f l r s t l yt h i sp a p e ra p p l yn e t w o r kc o d i n gi n t ot h e r e l a yo fc e l l u l a r r a d i oc o m m u n i c a t i o n ss y s t e m ，w h i c ha d o p tn c d f ( n e t w o r k c o d i n g - d e c o d e a n df o r w a r d ) a n dn c - a f ( n e t w o r k c o d i n g - - a m p l i f y a n df o r w a r d ) r e s p e c t i v e l y , a n dt h e ni m p r o v er e l a yt r a n s m i s s i o np r o t o c 0 1 i nt h i sm e t h o d ，ar e l a yc o u l d s e r v i c ef o rm u l t i - r e l a yi nas a m et i m e ，s ot h a t 血em e t h o dd e c r e a s et h er e l a yn u m b e r a s s i m u l a t i o nr e s u l t ss h o w , c o m p a r i n gw i t ht r a d i t i o n a lt r a n s m i s s i o nm e c h a n i s m ，t h e n c d fa n dn c a fm e c h a n i s m sc o u l di m p r o v en e t w o r kt h r o u g h p u t ，d e c l i n eo u t a g e p r o b a b i l i t ya n do b t a i nc o d i n gg a i n s e c o n d l y , t h i sp a p e rp r o p o s e san e wc o d i n gt r a n s m i s s i o nm e c h a n i s mn a m e d r - p n c ( r e l a y - p h y s i c a ln e t w o r kc o d i n g ) i tt a k e sp n c ( p h y s i c a ln e t w o r kc o d i n g ) t e c h n o l o g yi n t or e l a y , a n dc o m b i n e si n t e r f e r e n c en o i s ee l i m i n a t i o no fn c - d fw i t h t r a n s m i s s i o ns l o ts a v i n go fn c - a ft w oa d v a n t a g e s a ss i m u l a t i o nr e s u l t ss h o w , f r o m t h ea s p e c t so f n e t w o r kt h r o u g h p u t ，d e c l i n eo u t a g ep r o b a b i l i t ya n do b t a i nc o d i n gg a i n , r - p n cm e c h a n i s mi sm u c hb e r e rt h a nt r a d i t i o n a lt r a n s m i s s i o nm e c h a n i s m ，n c - d f m e c h a n i s ma n dn c 皤m e c h a n i s m 一 重庆邮电大学硕士论文 a tl a s t ，i no r d e rt ou s et h er - p n ct r a n s m i s s i o nm e c h a n i s ma v a i l a b l yo nr e l a y , t h i s p a p e rd e s i g n san e wf r a m es t r u c t u r e ，i nt h es a m et i m e i ta n a l y s e sn a r qf l o wa n d r - p n cf e a s i b i l i t y k e yw o r d s ：n e t w o r kc o d i n g - d e c o d ea n df o r w a r d ，n e t w o r kc o d i n g - a m p l i f ya n d f o r w a r d ，r e l a y - p h y s i c a ln e t w o r kc o d i n g ，r e l a yp r o t o c o l ，f r a m es 觚c t u r e i i i 重庆邮电大学硕士论文第一章绪论 1 1 研究背景及意义 第一章绪论 由于各种各样的无线电磁波充斥着有限的空间，造成了无线资源紧张，于是 如何提升无线资源的利用率引起了很多研究机构的重视。目前无线网络中采用中 继协作传输技术来扩大通信网络的覆盖范围并提高整个系统的容量。此技术使通 信网络由单跳传输变为多跳传输的形式，比如i e e e8 0 2 工作组提出的无线传感器 网络、a dh o c 网络以及无线m e s h 网络等。 在多跳无线网络中，中继节点对接收到的信息进行复制、放大和转发，从而 能改善了接收的质量，但是中继节点对接收信号的简单处理并转发无法实现网络 的最大流传输。于是文献 n e t w o r ki n f o r m a t i o nf l o w ) ) 【l 】从信息论和图论等角度出 发，严格证明了中间节点采用网络编码对接收到的多个信源的信息进行特定的压 缩编码处理后再转发，而多个接收节点则通过相应的方式解码获得源信息，能够 使通信网络从理论上逼近其最大容量，从而最大限度的提升网络吞吐量，同时也 解决了网络资源利用率过低的问题。 网络编码的理论一经提出，就引起了通信领域的高度关注，其理论和应用的 研究已成为了通信方面的热点之一。国外许多著名大学，包括瑞士e p f l 学院、美 国m r r 大学、美国p r i n c e t o n 大学等在内的国际许多著名大学和包括b e l l 实验室、 m i c r o s o r 研究院a t & t 香农信息实验室等在内的各种研究机构以及多家r r 公司的 研究中心，都已经开始了对网络编码的研究和应用；二而国内的许多著名学府亦 对其非常重视，如成都电子科技大学、清华大学、上海交通大学、西安电子科技 大学等也认为网络编码的研究对通信网络的具有积极的影响，因此开始了相应的 研究。 网络编码非常适合应用在无线网络中，这是因为无线链路的不可靠性和物理 层的广播特性。网络编码提出的本质是为了使通信网络达到理论上的最大传输流 量，从而能取得更高的网络吞吐量，随着研究的进一步的深入，在均衡网络负载、 鲁棒性、安全性等方面网络编码亦彰显了其卓越的性能。 虽然已经对网络编码理论和应用进行了广泛的研究，并证实运用网络编码能 提升网络的性能，但验证的步骤或模拟的环境，大多基于假设或理想化的理论模 型，与实际的应用环境还有一定的差距，由此得出的一些结论存在着局限性。此 外，研究过程大多基于理论上定性的分析，缺乏实际的定量的研究。因此，如何 参考实际环境的各种影响因素来应用网络编码，并基于网络编码建立应用的环境 重庆邮电大学硕士论文 第一章绪论 的模型，还有待更严格、更深入、更广泛地研究与实践。 1 2 研究现状 作为下一代网络的关键技术之一，网络编码是通信网络中的信息处理和传输 理论研究的重大突破，其应用前景相当广泛且极具理论的研究价值。毋庸置疑， 无线通信系统中采用网络编码技术，能进一步提高网络吞吐量、节省传输能量、 增强鲁棒性和安全性等。但是目前对该技术的研究还处于理论上的研究以及局限 性的应用分析中，目前主要围绕下面几个方面进行研究： 1 ) 网络编码节点的选取 文献【3 】提出了一种简化卷积编码器的设计的方案。其基于网络子树分解的线 图，描述了相关的矩阵结构，设计了一种减少解码复杂度的方法并且讨论了二元 执行的可能性。如何选取编码节点正是这篇论文的基础，即创建更为优化的树分 解的方法，从而达到简化相关矩阵的结构，进一步降低解码复杂度。但是在无线 网络的场景下，此方案却不能适用，这是由于无线网络的节点将信息转化为电磁 波来发送信号，即无线网络中的节点与其它节点间电磁波信号交织在一起，相互 产生一定的干扰，关系较为复杂。此外，无线网络中还有节点的能量和稳定性等 因素必须加以考虑。 2 ) 网络编码算法的设计 目前的网络编码主要的两种编码方案分别是线性编码和非线性编码。比如有 线网络由于结构可见，所以选择线性的算法较为适合；对于结构复杂的无线网络， 则更适合非线性网络编码，但文献【4 】中证明了，当符号集无穷大时，采用非线性编 码，系数传输矩阵满秩的概率为l ，此时数据报头的负担将会增大，因此符号集的 大小需要权衡各种因素。 3 ) 网络编码复杂度的分析 网络节点编码过程中对信号的处理涉及到的计算复杂度很高，即使接收节点 用高斯消元法译码，则译码过程依然比较复杂。编码符号集的最低门限的决定因 素是接收节点的数量和节点信息块大小，进而如何在网络开销的增加不显著的情 况下，综合考虑效率和性能以实现最小化网络编码复杂度【5 1 ，则需要进行更加深入 的研究。 4 ) 适合网络编码的路由机制与调度方案研究 网络编码的基本原理是将多个输入的数据信息通过网络编码压缩成一个数据 信息发送出去，降低了节点处的排队时延，其带来的效果就是组播网络中每个接 收节点近似独享本该多个节点共享的网络资源【6 1 。而传统的路由机制会为了减少排 2 重庆邮电大学硕士论文第一章绪论 队时延而回避交叉路径，若加入了网络编码，就可以不回避交叉路径，采取更加 自由的路由机制。如果在某节点处存在交叉路径，即可进行相应的网络编码来解 决排队时延的问题。为了更加充分的利用网络编码机制，提高节点的利用率，可 以从路由算法的建立之初就制造交叉路径，从而达到减少的中继节点亦能达到同 样的组播性能效果。同时，采用网络编码的路由机制还需考虑的一个重要问题就 是接收节点处的解码处理。在采用线性网络编码的网络中，每个接收节点必须能 够接收到k 维不相关的信息才能正确解码( 其中k 为源节点同时发送的符号个数) 。 因此设计适合网络编码的新型路由算法需要结合这几方面的因素来考虑。另外， 基于网络编码的调度机制也是网络编码的研究方向之一【7 】。传统的通信网络中，一 个发送节点可以在缓存中有一个或多个数据包时进行信息的传输，任何一种状态 都不会影响最后的吞吐量。但是在采用网络编码的通信网络中，由于节点采用网 络编码后的特性，缓存中拥有的包的个数会在很大程度上影响网络的传输效果， 所以应该选取合适的时机来进行信息的传输，以期达到最好的效果。 5 ) 协作网络编码机制的研究 协作机制可以带来分集增益，即单个或者多个中继节点为一个用户提供中继 协作服务，其代价就是大量的增加中继节点。当中继节点采用网络编码后，使得 单个中继节点可以为两个或者多个用户提供服务，从而减少了总共所需的中继节 点数目，尤其在大规模组网时更能体现出其优势。文献【8 】中采用多点协作传输 ( c o o r d i n a t e dm u l t i p o i n tt r a n s m i s s i o n r e c e p t i o n ，c o m p ) 机制，即多个单天线用 户共享彼此的天线，构成分布式的虚拟m i m o ( v i r t u a lm i m o ) 系统进行通信， 接收端通过合并经过不同衰落路径的信号从而获得分集增益。用户本身具有两个 作用，一个是用户本身，一个是中继节点的作用。每个用户可以与其附近任意一 个自由用户( 没有参与协作通信的空闲用户) 进行协作通信，即第一个时隙自由 用户从其协作用户处接收到信息，第二个时隙则将其需要发送的信息与接收到的 信息进行网络编码后发送到目的节点。两种编码方式的结合也是协作网络编码机 制的一个极具潜力的研究方向，文献【3 l 】中提出了空时编码与网络编码结合的中继 协作机制。其采取了两种方案来分析和比较了空时编码结合网络编码的优势。第 一种方案，中继节点与目的节点距离一定，且不断增加等距的协作中继节点；第 二种方案，中继节点与目的节点的距离一定，但是不断增加非等距的协作中继节 点。文中仿真结果表明空时编码与网络编码结合的中继协作方案性能更加优越， 亦证明了这种方案下，协作中继点的数量并不是越多越好。 6 ) 网络编码的性能分析与应用 文献【9 】中介绍和分析基于网络编码的中继技术，采用双向中继通信实现多跳无 线网络吞吐量的提升。这种技术被称为双向中继提升吞吐量( t w o - w a y ) ，即中继 重庆邮电大学硕士论文 第一章绪论 节点将多个信源的数据包进行编码且转发给多个不同的节点。其对两种基于网络 编码的t w o w a y 传输机制进行了仿真证明和性能分析：中继技术解码转发( d e c o d e a n df o r w a r d ，d f ) 和放大转发( a m p l i f ya n df o r w a r d ，a f ) 分别与网络编码( n e t w o r k c o d i n g ，n c ) 结合形成的新传输机制，即网络编码解码转发( n e t w o r k c o d i n g d e c o d e a n df o r w a r d ，n c d f ) 和网络编码放大转发( n e t w o r k c o d i n g - a m p l i f ya n df o r w a r d ，n c a f ) 。 7 ) 基于网络编码的系统安全性的分析 对通信网络带来的安全性的影响亦是网络编码不可忽略的一大特征。网络编 码对信息的处理可以使信息较为分散，同时较高的计算复杂度亦增加了破译信息 的难度，也就是说改善了通信的安全性【1 0 】【l l 】【1 羽。但是，我们也必须注意到网络编 码并不是完全就能够改善安全性的。以线性编码算法为例，传输网络中的节点数 目过多，以及不确定的编码算法方案，都是降低系统的安全性能的影响因素。因 此应该通过对不同的编码算法进行合理的安全性能分析，来确定不同网络算法对 系统安全的影响，从而针对不同的系统来设计合适的网络编码算法，从而提高网 络安全性能，这对于无线通信具有深远的意义。 8 ) 网络编码的实际应用 在加深网络编码技术的理论研究的同时，考虑实际场景的应用【8 】f 1 3 】【1 4 】【1 5 】，侧 重解决在实际环境中所遇到的应用问题，比如需要降低网络编码的复杂度，需要 对系统本身的延时以及网络编码带来的延时影响加以考虑等。网络编码在蜂窝网 中的应用是一个亟待开发的热点，首先蜂窝网的广播特性非常适合网络编码的应 用，但是无线网络的节点不可能同时监听来自多个信源的信息，如何在无线网络 中的节点处应用网络编码，这需要结合实际的环境进行深入的分析与研究。 1 3 主要研究工作和创新点 论文的工作内容主要包括基于中继的网络编码研究、蜂窝小区内基于n c - d f 和n c a f 的两种中继传输机制、蜂窝小区内基于r - p n c 的中继传输机制以及基 于r - p n c 传输机制的帧结构设计和仿真分析。具体包括以下几部分： 1 ) 基于中继的网络编码技术的研究 由于中继技术的引入，源节点的信号可经过多条不同的路径进行传输，即参 与协作通信的中继节点有很多。但是，其代价是增加中继节点的数量巨大，也就 是一个用户通信就有几个中继在为其服务：其导致了无线资源利用率极低。因此， 网络编码技术的引入，使中继可以同时为多个用户的通信服务，即能够大量减少 所需的中继节点数量，进而提高了无线资源利用率。 4 重庆邮电大学硕士论文第一章绪论 2 ) 蜂窝小区内基于n c d f 和n c a f 的中继协作传输机制的研究 蜂窝小区内的中继技术的主要作用是提高小区覆盖范围，因为小区内阴影衰 落比较严重，小区边缘及其小区覆盖死角等区域内的用户提供信号覆盖。由于中 继站的建立复杂度远低于基站，使用这项技术提升小区覆盖范围的成本很低，因 此，3 g p p 的大量提案都提出了基于中继技术的网络编码技术的应用方案。文中针 对蜂窝小区的应用场景，在中继处采用n c d f 和n c a f 两种中继传输机制，进 一步改进中继传输协议，并评估分析其网络吞吐量，中断概率，平均发送次数， 编码增益等主要性能指标。 3 ) 蜂窝小区内基于p n c 技术的中继协作传输机制的研究 基于文献1 6 】【1 7 1 1 1 8 】【1 9 】中提出了一种能够直接在物理层调制解调的p n c 技术，即 采用恰当的调n 解调技术，将中继节点处接收到的自然叠加的电磁信号，映射至 数据比特流叠加的高斯域中，并将此高斯域信号进行调制转发。简而言之，p n c 利用用户信号的干扰噪声，直接通过电磁信号高斯域映像实现网络编码机制。文 中针对蜂窝小区场景，在中继处采用p n c 技术，提出r - p n c 传输机制，进而改进 中继处的传输协议，然后对其几项主要性能指标进行分析和仿真。仿真结果显示 r p n c 传输机制同时具备了n c - d f 和n c - a f 两种传输机制的优势，其性能获得 更好的提升。 4 ) 基于r - p n c 的中继传输机制帧结构设计 l t e a d v a n c e d 中t d d 机制下，文中参考r - p n c 传输机制的传输协议，结合 透明与非透明两种中继场景，设计了与其相应的帧结构，进而从理论上分析了帧 结构的可行性，最后对其h a r q 流程进行了分析。 1 4 论文结构安排 本文其它章节安排如下：第二章总结了基于中继的网络编码技术，并概述了 各种技术的原理；第三章讲述了蜂窝小区场景下的中继处的采用n c d f 和n c a f 两种传输机制的应用方案，并改进相应的中继传输协议，且分析仿真了几项重要 性能指标；第四章在物理层网络编码技术的基础上，提出r - p n c 传输机制，改进 中继传输协议，并分析其性能；第五章基于r - p n c 传输协议，设计适用的帧结构， 且研究了h a r q 流程，且从理论上分析其可行性。 重庆邮电大学硕士论文 第二章基于中继的网络编码研究 2 1 引言 第二章基于中继的网络编码研究 随着各种通信业务和互联网技术的发展，尤其是无线通信业务的多元化和多 媒体化，人类对移动通信系统传输带宽的需求与日俱增。但是由于无线信道自身 具有的衰落特性与其有限性，限制了无线信道的容量和通信质量。再加之现有的 调制技术和编码技术对信道容量的改善已接近了香农极限，所以在无线带宽资源 和人类需求之间产生了矛盾。 于是多输入多输出( m u l t i p l ei n p u tm u l t i p l eo u t p u t ，m i m o ) 技术应运而生， 该技术要求传输节点采用多天线，可以有效提高无线通信系统的容量和抗干扰能 力【2 0 1 。但是由于移动台受到尺寸和电池寿命等原因的限制，采用多天线并不现实。 于是，为了使单天线终端也能获得m i m o 技术的分集增益，s e n d o n 撕【2 l 】【2 2 】等提出 了协作中继分集技术。协作中继的基本原理是增加中继节点的数量，然而也增加 了协作传输系统实现的复杂度，但同时会获得更高的多天线的分集增益。 由于无线信道所具有的衰落特性，限制了其容量和通信质量，而且现有的调 制技术和编码技术对信道容量的改善已接近了香农极限，使得有限的无线资源显 得非常紧蹙。因此促成了中继协作分集技术的产生和发展，该技术要求引入大量 的中继节点进行协作通信，使单跳传输链路转化为多跳传输链路，缩短了节点间 的通信距离，且提高数据速率，并扩大通信网络的覆盖范围，增加系统容量。采 用了中继技术的蜂窝小区内，源端用户的信号可经过多条不同的路径进行传输， 接收端用户则通过合并经过不同衰落路径的信号从而获得分集增益。但该技术同 样面临着新的问题，当小区内的用户数量大幅上升，为了提升系统性能，这就需 要增加数量更多的中继。本章主要致力于解决提升系统性能，使得单中继能够同 时为多个用户服务，进而减少所需中继数量。 2 2 网络编码的基本理论 网络编码是基于有线的组播网络所提出的一项技术【2 】。所谓组播技术是指在多 个节点组成的有线网络中，将数据包尽可能的发送至一个确定的节点子集( 即组 播组) 。其基本原理就是：源节点多向发送数据信息，而此数据信息到达目的节点 子集后，子集中的所有节点都能够接收到此数据信息的拷贝，但是目的节点子集 以外的所有节点都无法接收到此数据信息。 组播网络是由很多个节点相互连接组成树状的传播网络，简称组播树来实现 6 重庆邮电大学硕士论文第二章基于中继的网络编码研究 的。由最大流最小割【2 】的定理我们可以知道，组播网络中两个节点之间的最大传 输流量可以通过最小割来衡量，实现最大传输流的路径可以通过最大传输流的算 法找到。所以，建立两个节点之间通信的时候，可以采用最大传输流的算法，找 到适合的传输路径，从而得到此两节点之间的最大传输速率。但是，建立一节点 向多节点的传输网络时，其传播网络就会复杂起来。 网络编码的本质是在组播通信网络中，令网络上的中继节点对接收到的信息 进行一定的信号处理之后，再转发出去，而不是简单的存储转发。同时，接收节 点通过一定的方式译出信源发送的信息，网络则通过这种信号处理的方式获得了 节点接收速率的提升。 2 2 1 网络编码模型 通信网络中传输的数据信息被认为是传输信道中的流体( f l u i df l o w ) ，正如渠 道中流动的水一样。渠道的横截面积等因素可以影响通过的水量，所以，只有一 个单位容量的信道不能容纳多于一个单位信息速率的信源信息。如何在信道容量 无法扩大的情况下，提高信道的信息量的吐纳，进一步提高信息传输速率，这就 是网络编码产生的原因，即先对网络节点处的信息进行网络编码处理再进行传输。 网络编码本质上并没有扩大信道容量，而是在网络节点处进行信息处理，使得多 个用户的数据包由特定的算法重新组合后发送。下面我们将从图论和信息论的角 度对网络编码的模型进行表述。 下面的通信网络都必须满足以下的假设： a ) 有向图g 中的任意一条边的容量均为常数，比如l b i t 每单位时间，对于每 条边得容量的假设可以以任意的精度的定义。但是，如果某条边上的数据 信息传输量超过了l b i t 每单位时间，则加入一条并行边来表示，每条边的 容量仍然是l b i t 每单位时间。另外，也可以通过选择足够大的时间单位来 精确表示边上的容量为分数的情况； b ) 通信网络中的所有链路上都应该有时延的存在，下面为了便于分析，假设 所有链路的时延都等于0 ，即这里我们暂时不考虑时延所带来的影响； c ) 为了简化问题的表示与描述，假定通信网络中没有环路存在； d ) 因为网络编码是网络层的操作，但底层能够完成差错控制，从而提供一个 没有差错的系统给网络层。因此我们亦暂时不考虑通信网络中各条链路上 的传输差错； c ) 信源产生的随机过程石似，) ，z 1 ，2 ，( d ) 是相互独立的，并且有相同的整 数熵，比如说l b i t 每单位时间，而且不同节点产生的随机过程也是彼此独 7 重庆邮电大学硕士论文第二章基于中继的网络编码研究 立的。 一个通信网络可以用有向图g ( 矿，e ) 来表示2 1 ，其中y 代表节点集，e 代表边集。 考虑组播情况，用scy 来表示通信网络中的信源，集合tcy 表示目的节点的集 合。网络中的节点可以分为源节点、中间节点、目的节点( 一个节点亦可能分饰 多个角色，即同时为源节点、中间节点、目的节点) 。用( v ，v i ) 来表示节点v 到节点 ，的边，即p ，e ；边e = n ，i ) 的头为，= i i l ( p ) ，其尾为，= f 。l ( v ) 表示节点y y 的输入边的集合，r n 表示节点y v 的输出边的集合。 某个信源节点y 产生的信息空间为赋d = 似1 ) ，x 似2 ) ，x ( v ，( y ” ，它是由 ( y ) 个离散独立的随机过程所组成，其中每个离散随机过程均取自有限域l ，所 以节点v 的熵为： 日：篁c x ( v h ( x ( v ，功；m z ( v )式( 2 1 ) 日= ，功=式( 2 1 ) i = 1 目的节点所收到的信息空间为v ( v ) = z 似1 ) ，z ( v ，2 ) ，z ( v ，7 ( 力) ) ，它是由r l ( v ) 个 离散随机过程组成。在一个通信网络中，可以用( v ，v ，q “v 来表示节点v 和y 之间 的通信，它们之间所需传输的信息表示为q ( y ，v ) 。节点1 ，可以通过从其出发的边 p = ( y ，v i ) 来传输信息，可以用随机过程，( p ) 来表示。该随机过程的取值范围为有限 域。 网络编码不同于传统路由之处就在于各个中间节点上的信息处理方式，下面 定义各边上的函数映射。对边集e 中的每条边p = 似y ，存在一种映射： z ：兀一式( 2 2 ) 。e l ( y j 。 这时对应于每条边的编码函数，它把某个节点所有输入边上的信息映射成其 某个输出边上将传输的信息。目的节点y 为了得到所需信息，则： v z ( v ，i ) 甲( v ) ，毋j ：兀 ( 。 式( 2 3 ) e l ， 式中，映射毋。是对应于目的节点y 的第i 个所需信息的译码函数，它从此目 的节点输入边上所传输的信息中恢复出所需信息。如果存在编码函数正和译码函 数& ，使q 似v ) c 甲( v ) ，则称通信网络似v ，q ，v 是可解的，同时称编码函数z 和 译码函数毋。是这个网络的一组解。 2 2 2 网络编码处理过程 当一个或几个节点同时向若干个其它节点发送数据时，需要中继节点进行转 发，网络编码允许中继节点对接收到的信息进行编码，将接收到的多个数据包按 照特定的算法重新组合之后再转发。 图2 1 ( a ) 中箭头代表有向链路，这里假设每条链路的容量为1 ，节点1 将岛 8 重庆邮电大学硕士论文 第二章基于中继的网络编码研究 和6 2 两个b i t 分别传送给了节点6 和7 ，若采用传统的通信方式，将在中间节点4 和5 之间产生排队延时；而次用了如图2 1 ( a ) 中的简单的网络编码策略则可使 带宽效率更高，节点4 将接收的两个b i t 异或后转发，接收节点6 接收到6 l 和6 lo 如， 解码后即可恢复出如，同理节点7 也可收到完整信息。 ，一一、 b l ， j 一、之 j 。 j “一、。i 、 。 ；。+ b 2 ，：j | 、j j x h 一，。王j ： 、包 ! 、- 、j j 一一， ， 图2 1 网络编码示意图：( a ) 有线网络( b ) 无线网络 将其从有线网络推广到无线领域中，如图2 1 ( b ) 中所示。这里引入传输半 径的概念( 用以节点为中心的圈表示) ，通过在节点4 进行的编码和两个接收节点 的解码，在接收完整信息的同时，同样提高了传输速率。 一个有效地网络编码方案必须使收点能从接收到的数据中恢复出原始信息， 数据在经过中间节点群时可能经过多次编码。作为中继节点，发送的信息只能来 源于收到的信息，其信息量必然不能超过收到的信息量，即信息熵是非增的。因 此，必须保证接收节点接收到足够多的不相关信息，即对于每个接收节点的系统 传输矩阵满秩，才能正确解码。因此，根据网络拓扑的特点，建立节点间的合作 机制，设计合适的低复杂度编码算法是网络编码技术的重要内容之一。 2 3 基于中继的异或压缩算法 异或压缩编码算法是网络编码技术应用于无线通信网络的最直接也是复杂度 最低的一种算法。即中继节点通过对接收到的两个节点的数据进行异或运算 ( x o r ) 完成信息合并，进而实现对接收到的数据信息的压缩，从而满足网络编 码的基本条件，即中继节点处的信息量是非增的。文献【9 】【3 0 】研究了t w o - w a y 中继 网络环境下的基于x o r 运算的信息交换。 本节将简单的介绍t w o - w a y 中的两种中继传输机制的传输模型和其吞吐量公 9 - ， b 一 一 、， 、， 重庆邮电大学硕士论文 第二章基于中继的网络编码研究 式推导。为了便于说明，我们设定无误码率的传输速率为r o = n r , ( 其中n 和瓦分 别为传输包的数量和传输所需时隙) ，且节点s l 和节点8 2 到中继节点的误包率分 别为见，和以：。 2 3 1t w o w a y 中继下的n c - i ) f 中继的解码转发机制，中继端r 将接收来自节点s 的信号。r 将对信号进行 解码处理，以获得原始信息。然后它再将其获得的信息重新编码，以一定功率发 送给接收端s 。 d f 机制的设计目的是在中继r 处将用户信息的高斯白噪声除去。但是，中继 节点r 处如果错误判决了接收到的数据信息，则此错误的数据信息就会继续向前 传送。为避免由于中继节点r 处对接收的数据信息的错误判决而造成的错误前向 传送，所以在中继节点r 处可以采用循环冗余校验( c y c l i cr e d u n d a n c yc h e c k ，c r c ) 技术对接收数据进行校验。若判决正确就前向发送，否则丢弃该帧并不进行中继 向前传输，并发送n a c k 信息。为了实现单中继节点能够同时为多用户提供服务， 则在中继节点r 处采用网络编码，即网络编码。解码转发机制。 如图2 2 所示，以简单的三节点线性网络为例，r 为中继节点。n c d f 传输机 制即中继节点在接收两信源信息后，先进行解码然后再进行网络编码后转发。 - slo t1 - 。slo t2 。“。sl o t3 图2 2t w o - w a y 中继下的n c d f 传输流程图 由图l ，t w o - w a y 中继下的n c d f 传输机制的传输协议如下： 1 ) 中继节点r 清空b u f f e r 后，通知节点s 1 发送信息，则节点s l 发送信息至中 继节点r ，直至中继节点r 成功接收； 2 ) 若中继节点r 的b u f f e r 中存在节点s 1 的信息，则通知节点s 2 发送信息，则 节点s 2 发送信息至中继节点r ，直至中继节点r 成功接收； 3 ) 若中继节点r 的b u f f e r 中存在节点s 2 的信息，则通知节点s l 发送信息，则 s 1 发送信息至中继节点r ，直至中继节点r 成功接收； 4 ) 若中继节点r 的b u f f e r 中存在节点s l 和节点s 2 的信息，则解码后再编码并 双向发送至节点s l 和节点s 2 ； 根据上述的传输协议，用m a r k o v 链以中继的不同状态，以及不同状态之间的 l o 重庆邮电大学硕士论文 第二章基于中继的网络编码研究 转移概率建立转移模型如图2 2 所示。 设p ( s o ，p ( s 2 ) ，p ( s 3 ) ，p ( s 4 ) 分别表示中继节点r 所处的s i ，s 2 ，s 3 ，s 4 四种不同状态，可得到各个状态方程如下： 图2 3t w o - w a y 中继f 的n c d f 传输机制的中继状态转移图 p ( s o ) = p ( s o ) 见。+ p ( s 3 ) ( 1 一见。) ( 1 一p e 2 ) 三簿：2 翟x 、1 一他：? 墨狰+ 尸( 墨) 见：( 1 一见- 式( 2 4 ) p ( 最) = p ( 是) 几+ 尸( 岛) 见。( 1 一见：) 、 p ( s o ) + p ( s ) + p 幌) + p ( 岛) = 1 由上式可以推出n c d f 的传输速率如下： 一胛= 心两( 1 - i p , ) 瓦( 1 - 忑p , 2 ) ( 石2 - p 丽, , - p , 2 ) 式( 2 5 ) 3 一j p n 一3 p n + p n p t 2 + p i + p z 假设以。= 见：= 见肥一d ，则上式可简化为： 一d ，：2 r o ( 1 - p - , , 一c - d p ) 式( 2 6 ) 则可得出传统三节点网络下t w o - w a y 中继下的n c d f 传输机制的归一化吞吐 量如下： 鱼竽：_2(1-p,c-or) 式( 2 7 ) 2 2 2t w o - w a y 中继下的n c - a f 放大转发方式是一种最为简单的协作发送信号方式。顾名思义，在这种机制 下，中继节点r 将接收到来自发射端s 的信号，然后中继节点r 将此未除掉噪声 干扰的信号放大并向前发送。n c a f 传输机制即在中继处采用网络编码的a f 转 发模式。 如图2 3 所示，同样以简单的三节点线性网络为例，n c a f 传输机制即中继 重庆邮电大学硕士论文 第二章基于中继的网络编码研究 节点在接收两信源节点信息后，无需解码直接编码后放大转发。 t 1 t 2 s l o t1 。”。s l o t2 图2 4t w o - w a y 中继下的n c - a f 传输流程图 t w o w a y 中继下的n c a f 传输机制的传输协议如下： a