（通信与信息系统专业论文）无线双向中继系统中的网络编码.pdf

摘要 网络编码理论突破了传统网络中路由器等中继设备只负责对信息的存储转 发的处理方式，提出中继设备可以对接收信息进行编码处理后再传输，可以很大 的提高网络的吞吐量，甚至达到系统容量的极限值。研究表明，网络编码不但可 以提高系统吞吐量，还可以均衡网络负载，提高网络的鲁棒性，甚至提高网络安 全性。 网络编码理论是基于有线网提出的，但是由于无线网络的不可靠性和广播特 性，普遍认为无线网络更适合于网络编码的应用，尤其是无线网络中物理层的网 络编码技术更是一个研究热点。本文主要对网络编码在无线双向中继系统中的应 用进行了研究。 双向中继系统就是两个节点需要在第三个节点的帮助下进行信息的交换。传 统的中继处理方式有很多，如解码转发( d f ) ，前向放大( a f ) 等。后来的研究中 将网络编码与这些中继处理方式结合起来，相应的有了联合解码转发0 d f ) ，模 拟网络编码( a n c ) ，这些在一定程度上改善了系统性能。但这些方法也存在着一 些弊端，如j d f 要受到多址接入容量域的限制，a n c 在放大信号的同时也放大 了噪声。 本文针对这些方法存在的缺点，给出了在中继不需要对来自两个源端的信息 进行解码的去噪映射方式，在这种方法中，中继首先根据已知的信道信息和两个 源端发送的所有可能的信息的情况，按照去噪映射的规则，将整个星座图划分成 若干个判决区域。当中继接收到叠加信号后，信号落入某一个区域，就把它映射 成相对应的信号。通常可以将叠加信号映射成更低进制的星座图，可以节省功率。 并且实现了在中继不解码，因此突破了多址接入容量域的限制，同时中继进行了 去噪处理，不会将噪声再传回给源端。 般情况下，仅根据映射规则，映射关系会有很多选择方法。但不是所有的 选择都可以达到同样的效果。通过分析欧氏距离对映射区域选择的影响，给出了 映射区域的选择方法。选择合理的映射区域，可以有效的降低误码率。 关键词：网络编码；无线网络；双向中继；去噪映射 a b s t r a c t n e t w o r kc o d i n gt h e o r yc h a n g e st h et r a d i t i o n a lp r o c e s s i n gm e t h o di nt h en e t w o r k t h a tt h er o u t e r sa r eo n l yr e s p o n s i b l ef o rt h es t o r i n ga n df o r w a r d i n gt h ei n f o r m a t i o n i t p r o p o s e st h a tt h er e l a yc a ne n c o d et h er e c e i v e di n f o r m a t i o nb e f o r ef o r w a r d i n gi t s u c h ap r o c e s s i n gc a ni m p r o v et h et h r o u g h o u to ft h en e t w o r k , a n de v e nm a k ei tr e a c ht h e l i m i to ft h en e t w o r kc a p a c i t y s t u d ys h o w st h a tn e t w o r kc o d i n gc o nn o to n l yi m p r o v e t h et h r o u g h o u to ft h en e t w o r k ，b u ta l s oc a nb a l a n c et h en e t w o r kl o a d ，豇1 h a l l c e n e t w o r kr o b u s t n e s s ，a n de v e ni m p r o v et h es e c u r i t yo f t h en e t w o r ke ta 1 n e t w o r kc o d i n gt h e o r yi sp r o p o s e db a s e do nt h ew i r e d n e t w o r k b e c a u s eo ft h e f a l l i b i l i t ya n dt h eb r o a d c a s tc h a r a c t e r i s t i ci nt h ew i r e l e s sn e t w o r k , i ti sc o n s i d e r e dt h a t t h ew i r e l e s sn e t w o r ki sm o r es 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 g e s p e c i a l l y , t h ep h y s i c a ll a y e rn e t w o r kc o d i n gi nt h ew i r e l e s sn e t w o r kh a sb e e nah o tt o p i c t h i s p a p e rm a i n l yf o c u s e so nt h ea p p l i c a t i o no fn e t w o r kc o d i n gi nt h eb i d i r e c t i o n a l w i r e l e s sr e l a yn e t w o r k i nb i d i r e c t i o n a lr e l a yn e t w o r kt w on o d e se x c h a n g et h ei n f o r m a t i o nw i t ht h eh e l p o ft h et h i r do n e t h e r ea r em a n yt r a d i t i o n a lp r o c e s s i n gm e t h o d ss u c ha sd e c o d ea n d f 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 ) e ta 1 t h el a t e rr e s e a r c h e sc o m b i n et h e s e p r o c e s s i n gm e t h o d sw i t hn e t w o r kc o d i n ga n dp r o p o s es o m en e wi d e a ss u c ha sj o i n t d e c o d ea n df o r w a r d ( j d f ) a n da n a l o g yn e t w o r kc o d i n g ( a n c ) t h e s em e t h o d sa l lc a n i m p r o v et h ep e r f o r m a n c eo ft h es y s t e ma tac e r t a i ne x t e n d b u tt h e ys t i l lh a v es o m e d i s a d v a n t a g e s f o re x a m p l e ，j d fi sr e s t r i c t e db yt h ec a p a c i t yr e g i o no ft h em u l t i p l e a c c e s sa n da n ca m p l i f i e st h en o i s ew h i l ea m p l i f y i n gt h es i g n a l s t 蛐p a p e ri n t r o d u c e sap r o c e s s i n gm e t h o dt h a td o e s n tn e e dt h er e l a yt od e c o d e t h es i g n a l st r a n s m i t t e db yt h et w o $ o b r c en o d e s i nt h i sm e t h o d ，t h er e l a yf i r s td i v i d e s t h ec o n s t e l l a t i o ni n t os e v e r a lj u d g i n gr e g i o n sb a s e so nt h em a p p i n gr u l ea n da c c o r d i n g t ot h ec h a n n e li n f o r m a t i o na n dt h ep o s s i b l es i g n a l st r a n s m i t t e db yt h es o u r c en o d e s b o t ho fw h i c hh a v eb e e nk n o w nb yt h er e l a y w h e nt h er e l a yr e c e i v e st h e s u p e r i m p o s e ds i g n a l s ，i td e c i d e sw h i c hr e g i o nt h es u p e r i m p o s e ds i g n a l sb e l o n gt oa n d t h e nm a p st h e mt ot h ec o r r e s p o n d i n gs i g n a l s u s u a l l yt h es u p e r i m p o s e ds i g n a l sc a nb e m a p p e di n t oal o w e rb a n do ft h ec o n s t e l l a t i o nd i a g r a m , s oa st os a v ep o w e r i tb r e a k t h r o u g ht h er e s t r i c t i o no fc a p a c i t yr e g i o nb e c a u s eo fi t sn on e e df o rd e c o d e a n di t r e m o v et h en o i s ea tt h er e l a y , s oi tw i l ln o tt r a n s m i tt h en o i s eb a c kt ot h es o u r c e n o d e s u n d e rn o r m a lc i r c u m s t a n c e s ，t h e r ew i l lb em a n y m a p p i n go p t i o n si nc a s co fo n l y a c c o r d i n gt om a p p i n gr u l e s b u tn o ta l lo ft h eo p t i o n sc a l la c h i e v et h es a m er e s u l t s o t h ep a p e rp r e s e n t st h em e t h o d st of i n dm a p p i n gr e g i o n st h r o u g ha n a l y z i n gt h ei m p a c t o fe u c l i d e a nd i s t a n c eo nt h ec h o i c eo ft h em a p p i n gr e g i o nw h i c hc o u l dd e c r e a s et h e b i te r r o rr a t e ( b e r ) k e yw o r d s ：n e t w o r k c o d i n g ，w i r e l e s sn e t w o r k ，b i d i r e c t i o n a lr e l a y ， d e n o i s i n gm a p 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞叁堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：覆j 、丽 签字日期：细。罗 年f 月3 日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权丕鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：西j ，丽 导师签名： ? 才朔 签字日期：瑚7 年6 月 弓日 签字日期：硼尹年多月弓日 天津大学硕士学位论文第一章绪论 1 1 论文的研究背景 第一章绪论 在目前的有线通信网络或无线通信网络中，信息传输都是由源节点经过中间 节点，以存储转发的方式传送到目的节点的。除了数据复制外，网络的中间节点 并不需要做任何其他的数据处理。因为人们普遍认为对中间节点的数据处理是毫 无意义的。香农证明了一个网络信息流图的容量都存在一个极限值，但是传统的 网络实际并不能达到这一极限值。依据网络信息流中的最大流最小割定理，网络 节点的功能不应该只局限于存储和转发。 2 0 0 0 年，网络编码的概念在香港中文大学由r a h l s w e d e 等教授首次提出。 它是进入2 l 世纪后通信领域的一项重大突破，它融合了编码和路由的概念，通 过允许网络的中间节点对来自不同链路的信息进行编码组合，使得网络节点既实 现路由功能又实现编码功能再转发出去，接收节点应用相应的译码运算恢复出信 源所发的信息。理论研究表明，在这种全新的体系结构下，网络性能可以达到最 大流传输的理论极限。 网络编码的概念被提出后，引起了学术界以及很多企业的关注，迅速成为了 一个研究热点。因为网络编码有着诸多优点。在网络资源越来越紧缺的时代，网 络编码的主要优势在于如果己知网络的拓扑结构及链路容量，就可以计算出源点 到多个目的节点的最大信息吞吐量，它可以使资源得到充分利用，并且能使网络 资源利用达到理论上限，这有赖于网络节点在转发信息前对接收数据进行编码。 具备网络编码功能的节点从各个输入链路获得信息，并进行编码，然后把信息传 送给所有输出链路。研究表明，网络编码除了能够提高系统的吞吐量外，在数据 压缩、负载均衡、降低节点能量消耗、减少传播时延、提高网络健壮性及信息安 全等方面都有重要的应用前景。 当然，任何增益都是有代价的，网络编码的代价就是计算的复杂度和时延， 并且为了应用网络编码相对应的路由算法，现有的路由算法，传输协议等都需要 改变，调度机制对于传统非网络编码网络也会相对复杂。因此在后续的研究中还 需要全面评估网络编码的优势以及劣势，有助于在实际应用中权衡利弊，寻找最 适合网络编码应用的场合，从而发挥其性能优势，为当前的通信网络服务。 网络编码的概念首先是基于有线网络提出的，起初的研究多集中于有线网络 天津大学硕士学位论文第一章绪论 中。但是无线链路的不可靠性和物理层广播特性更适合使用编码的方法，所以无 线网络环境应该是网络编码首先被应用的领域。因此，现在无线网络中的网络编 码技术也成为一个研究热点。应用网络编码，可以解决传统路由、跨层设计等技 术无法解决的问题，提高网络性能。 在无线网络中，经常会出现当传输距离过远或者信道很恶劣，所导致的传输 的错误概率增加，吞吐量减小。为了解决这个问题，产生了协同中继的概念。传 统的协同中继方式有放大转发( a m p l i f y - f o r w a r d , a f ) ，解码转发 ( d e c o d e f o r w a r d ，j d f ) 等。网络编码的思想被应用于无线网络中后，很多研究将 网络编码和传统的中继结合起来，更进一步改善了网络性能。 1 2 论文的研究内容 本文的研究主要侧重于两路中继信道中利用网络编码的思想进行中继处理 的情况。两路中继网络就是指两个终端通过无线半双工信道，借助于一个中继节 点进行信息传输，因为其基础性和实用性，在网络研究中受到了很多的重视。两 路中继网络中的网络编码也就成为了一个重要的研究方向。 两路中继网络中的网络编码技术也都是关于中继节点的信息处理。如何可以 降低计算的复杂度，最大可能的提高吞吐量以及如何保证终端可以可靠的解码， 都是研究的方向。前期有一些研究结果已经提出了一些处理方式，如模拟网络编 码( a n a l o gn e t w o r kc o d i n g ，a n c ) ，联合解码转发( j o i n td e c o d e f o r w a r d ，j d f ) 等。虽然这些方式也可以在一定程度上提高网络吞吐量，但也存在很多的弊端， 影响到系统其他方面的性能。 本文中针对这些方法的不足之处，介绍了一种去噪映射的处理方式，在中继 不需要解码，而是将接收到的信息进行映射。其思想是对接收到的信号做合理的 映射处理，通常是将叠加后的星座图映射成更低进制的星座图，并且可以节省功 率。并且根据欧氏距离选择合适的判决区域，减小误码率。 文章中首先简要介绍了网络编码的基本概念、网络编码几种基本的构造方 式。然后介绍了无线网络中的网络编码的应用及发展，之后详细介绍了两路中继 系统中的去噪映射。首先给出了去噪映射的规则，通过举例具体说了去噪映射。 之后以给出了映射区域的选择方法，然后对系统进行m a t l a b 仿真。最后对该算 法的优缺点进行了评价。 天津大学硕士学位论文第一章绪论 1 3 论文的内容与结构安排 全文的内容安排如下： 第二章：首先简单介绍了网络编码思想提出的理论基础一最大流最小割定 理。然后引出了网络编码的基本概念。随后介绍了网络编码的优缺点及发展现状。 第三章：简要介绍了几种网络编码的构造方式。从最初提出的线性向量编码， 到较完备的线性代数编码方式，后来提出的较实用随机网络编码方式。 第四章：介绍了网络编码的思想从有线网络到无线网络的扩展及其在无线网 络中的应用，引出了物理层网络编码的概念。 第五章：首先介绍了协同中继的概念。给出了两路中继系统模型，介绍了以 往的中继网络编码处理方式，通过对其进行性能分析，给出了去噪映射的概念。 首先详细介绍了去噪映射规则，并以源端采用q p s k 调制方式的情况为例具体说 明了去噪映射，通过对信道系数取不同值时叠加星座图的比较，说明了信道系数 不同，映射关系的选取也不同。然后通过对同一信道系数下，不同的映射区域的 选择方法的误码率的比较，说明了欧氏距离对去噪映射的影响，然后给出了判决 区域的选择方法。之后，选择参数，对系统进行了仿真，并进行性能分析。最后， 对该算法的优缺点进行了评价。 第六章：对整个论文的工作进行了总结。 天津大学硕士学位论文第二章网络编码概述 2 1 最大流最小割定理 第二章网络编码概述 香农在论文 a n o t eo i lt h em a x i m u mf l o wt h r o u g han e t w o r k ) ) 指出：“通信 网络端对端的最大信息流，是由网络有向图的最小割决定的”。从而得出了图论 中的最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。 在介绍最大流最小割定理之前，我们先简要介绍图论中一些相关的概念【1 】。 图：设有端点集v = ，y ：，v 。) 和边集e = 豫，e 2 ，e m ，当存在关系r ， 使v x v e 成立时，则说由端点集v 和边集e 组成图g ，表示为g = ( ve ) 。其 中关系r 是指对任意一边e k ，有v 中的一个点对( v ，1 ，) 与之对应。 图g 中的v 集可任意给定，而e 集只是代表v 中的二元关系。对 v v ，1 ，v ，当且仅当h 对v ，存在某种关系时( 如邻接关系) 才有某一个e k e 。 如果有一条边e k 与点对( ，v ，) 相对应，则称v ，v ，是e k 的端点，记为q = ( v i ，v j ) ， 称点，v ，与边e k 关联，而称与，为相邻点。若为两条边与同一端点关联，则 称这两条边为相邻边。 对于图g = ( ve ) ，当v l 对v ，存在的某种关系r 等价于v ，对v 存在的某种关系 r 时，则称g 为无向图，即图g 中的任意一条边e k 都对应一个无序点对( v ，v ，) ， ( h ，v ，) ，( v j ，v ) 。反之，图g 中的任意一条边e k 都对应一个有序点对( v ，) ， ( ，v j ) ( v ，) 时，则称g 为有向图。 端的度数：与某端相关联的边数称为该端的度数，记为d ( v ) 。在有向图中， 进入或者射入端v 的边数，称为端v ，的入度，记为d 一( v ) ，离开或者从端k 射出 的边数，称为b 的出度，记为d + ( v ，) 。 网络：设g = ( ve ) 为有向图，它有两个非空不相交的顶点子集) 【，y 。x 中的 顶点称为源，y 中的顶点称为宿，其他顶点称为中间顶点，在边集e ( n ) 上定义了 一个取非负整数值的函数c ，则称n 为一个网络。 函数c 称为n 的容量函数，函数c 在边= ( v ，v j ) 的值叫做岛，的容量，记为 c ( i ，) 或者c ( 白) 。一般来说，c ( f ，j ) c ( j ，i ) 。 这里主要以单源单宿网络为例来说明最大流最小割定理。所谓单源单宿网络 就是指： 1 ) 网络中有且只有一个入度为0 的端，且这个端称为源端( 发端) 。 天津大学硕七学位论文第二章网络编码概述 2 ) 网络中有且只有一个出度为0 的端，且这个端称为宿端( 收端) 。 流：通过网络n 的边( i ，j ) 的实际流量叫做这条边的流，记为z ，各边的流 的集合叫网络n 的流。从源发出的实际流量f 叫网络的总流量，且等于宿端收 到的总流量。 可行流：设厂是定义在边集e ( n ) 上的一个整数值函数，若满足： 1 ) 对所有的e ee ( n ) 有0 ( e ) c ( p ) ； 2 ) 对所有的中间顶点i 有f ( i ，y ) = f ( v ，f ) ； 则称厂是网络n 的一个可行流( f l o w ) ，f ( x ，v ) 称为可行流厂的值，记为 f ( x ，y ) 。f ( i ，y ) 叫流出顶点i 的流，f ( v ，f ) 叫流出顶点i 的流。 最大流：设厂是网络n 的一个流，如果不存在n 的流厂，使f 。圳 六 则称厂为最大流，记作厶。对于一个网络来说，最大流就是从源点到收点的 最大传输数据率，而广播的最大流量是指源点同时向所有收点发送同样数据时对 每个收点所能达到的最大数据率。 割的定义：设n = ( ve ) 是只有一个源x 和一个宿y 的网络，k 是v ( n ) 的一 个子集，x k ，y v - ，( k ，v - ) 表示起点在k ，终点在y 。的边的集合，把这些 边的集合称为n 的一个割，记作k 。割中所有边的容量之和叫做割的容量，用 c ( 巧，一v 。) 或用c ( k ) 表示割k 的容量，于是c ( k ) = c ( e ) 表示。也就是说网络的 割是分离源和宿的弧的集合。 如图2 - 1 所示，其中 c l ，c 2 ， c 2 ，c 3 ，c 4 ) ， c 4 ，c 5 ) ， c l ，c 3 ，c 5 就是该网络流 图的割边集。 ab 图2 1 最大流最小割示意图 最小割：设n 是一个网，k 是n 的一个割，若不存在n 的割k 使得 c ( k ) d 为编码符号域的大小，d 是信宿节点 的数目，7 7 是随机选取编码系数的链路的数目【l 。 在r n c 中，只要当编码符号域q 足够大，总可保证接收节点以较高概率成 功译出信源发送的信息。j a g g i 等人指出当吲= 2 1 6 和吲= 2 8 时解码成功率可达 0 9 9 6 ，而c h o u 等人指出| f | = 2 8 就足够实际使用了。 3 4 2 随机网络编码的优点 在采用r n c 的线性编码多播中，多个信源可以是独立的，也可以是线性相 关的，对于线性相关的信源，r n c 可以起到信息压缩的作用。此外，r n c 是网 络编码的分布式实现，无需事先获知整个网络的拓扑信息，尤其是适用于拓扑结 构动态变化或者大规模的网络。对于存在网络节点和链路失效的网络，r n c 可 以利用整个网络的剩余容量来获得网络的最佳容量，从而提高多播传输的鲁棒 性。 在r n c 中，虽然不能确保最终形成的系统转移矩阵m 满秩，但由于是随机 选择编码向量，其复杂度与确定性算法相比要低得多，更易于实现。而且9 9 以上的译码成功率在般情况也足以满足需求。因此，随机网络编码具有重要的 理论价值和应用价值，得到了广泛的关注和应用。 天津大学硕士学位论文第四章无线网络中的网络编码 第四章无线网络中的网络编码 早期提出的网络编码的思想是基于无噪的有线网络提出的。近期，将网络编 码的思想应用于无线协同通信也逐渐受到了人们的关注。为了充分利用有限的无 限资源，提高网络覆盖范围和系统容量，目前无线通信领域引入了多跳传输机制。 在无线多跳通信网络中，信息可以通过中间节点进行复制、放大和转发，使各接 收节点能快速收到完整信息，但中继节点简单的数据转发能力一般无法实现最大 信息传输。而网络编码的思想从理论上实现最大流传输，能有效解决中继节点传 输瓶颈问题的特点。所以将网络编码的思想应用于无线协同通信也逐渐受到人们 的关注。例如，很多研究学者研究了网络编码在无线m e s h 网，a dh o c 网，传 感器网络和蜂窝无线通信系统中的实现。 4 1 网络编码技术从有线网络到无线通信网络的扩展 将建立在有线通信网络基础上的网络编码技术应用在无线多跳通信网络中， 应用节点协作的概念和有效的编码算法，以提高无线多跳通信网络性能。但是在 网络编码的理论和应用方面，无线网络与有线网络有着显著的差别，这主要是由 无线网络的结构特征和无线传输信道的时变衰落特性决定的。与通过电缆或者光 纤等可靠媒介形成固定而独立连接的有线网络不同，无线网络的节点在分布上具 有多维空间上的随机特性，节点之间的连接因受移动或节点分布地域的限制，不 但具有时间域上的时变特性而且在空间域上具有相互制约的相关性。在信号传输 上受到时交衰落信道的影响具有时间域上的随机性和不可靠性。 因此，在无线多跳通信网络中采用网络编码技术，需要结合无线链路的特性， 采用无线传输的广播方式和节点侦听机制，同时也需要考虑各种衰落、干扰及隐 藏终端和暴露终端等因素的影响。所以把网络编码从有线网络推广到无线网络， 用来提高无线网络传输的有效性和可靠性，一定要先加强对网络模型的提取和对 网络无线传输容量的细致研究，这一研究不但在确立无线网络传输性能极限上具 有重要的理论意义，而且对如何把网络编码应用于无线网络有着根本的指导意 义。随着各种高性能低功耗器件的出现和定位精度的提高，多无线信道技术、多 径分集合并技术以及联合跨层技术的发展，节点可以具有相应的信号处理能力， 能够实施复杂的算法，网络编码的未来应用将更为明朗。同时，网络编码的应用 天津大学硕士学位论文第四章无线网络中的网络编码 也将推动相应新型技术的研究。网络编码技术与网络拓扑密切相关，将实际网络 结构进行抽象和代数实现以便更好的分析编码性能是研究需要，对相关算法进行 仿真也是实现的必要。 如图4 1 所示为网络编码技术从有线网络到无线通信网络的扩展1 6 1 。 b 2 亡令 b 2 图4 _ 1 网络编码技术从有线网络到无线通信 在无线领域中的传输，存在一个传输半径的问题，也就是说以节点为中心， 数据只能被传送到一定范围内的接收节点。如图4 1 所示，节点2 ，3 分别发射信 号b l ，b 2 到接收节点6 ，7 。但节点6 不在3 的传输半径范围内，也就是说，节点3 不能直接发射信号b 2 给6 ，同理，节点2 也不能直接发射信号b 1 给节点7 。都需要 经过中继节点来进行转发。利用网络编码的思想，在同属于节点2 ，3 的传输半径 内的中继节点4 ，对接收到的信息进行编码得n b l + b 2 ，然后发送出去，到达节点 6 ，7 后再进行解码。在节点6 ，利用收到的b 1 + b 2 和b l 就可以解出b 2 ，同样，在节 点7 也可以解出b l 。 4 2 网络编码在无线网络中的应用 4 2 1 网络编码在无线自组织网络中的应用 j y u a n 提出了一种利用网络编码优化的流路由方法，以此来提升a d h o c 网络 的多播吞吐量。这种方法是基于一种在网络层和物理层平衡链路带宽供需的跨层 优化策略。虽然运用网络编码是以增加网络的复杂性为代价来换取网络吞吐量提 高，因此，不少研究者致力于提高a dh o c 网络的组播吞吐量，同时降低复杂度。 k u n g 等把网络链路划分为两类：进入中间节点的链路和进入信宿节点的链路， 只需要在进入中间节点的链路进行网络编码即可，而对进入信宿节点的链路，只 用采用路由策略，这大大降低了网络编码的复杂性。t r a c e y 等人考虑的是时变的、 链路容量受噪声干扰影响的无线网络模型。t r a c e y 在时变无线网络模型的基础 上，使用了动态的压力反馈算法来分别优化网络编码和路由。 2 2 天津大学硕士学位论文第四章无线网络中的网络编码 y w u 和c h o u 在a dh o e 多播方面提出了应用网络编码的最小化能量解决方 法，使得传输每比特信息消耗的能量最小，从而节省a dh o e 多播传输的能耗。如 果路由方式是把无线a dh o c 网络抽象成组播树，树型结构的每条边代表着广播 链路的每比特能耗，那么最小化能耗的组播问题就划归为在组播速率一定的条件 下最小化沿着组播树路径的代价总和的问题，属于n p 难问题。而在采用网络编 码的情况下，该问题可以转化为线性规划的问题，在多项式时间内可解，并且在 能耗和计算量上都要优于传统路由。 此外，还有一些学者研究了如何利用网络编码增加无线自组织网多播传输的 鲁棒性问题。在无线网络中，空间差异性的利用已经被广泛认为是克服无线信道 衰减的最有效方法之一。c h e n 等人研究在分布式天线系统和多入多出系统 f d a s m i m 0 ) q b ，引入网络编码的概念，经过理论推导和实验仿真，证明了无论 有无辅助天线，网络编码都能提高网络的性能，尤其是减小系统丢包损耗。c h e n 研究的不足之处在于主要关注的是小型网络中线性网络编码的应用，没有考虑分 布式随机网络编码和网络规模较大的情况。在大规模的无线网络中，可以在网络 编码的基础上结合应用分布式信道编码，进一步提高网络性能【l 引。 4 2 2 网络编码在无线传感器网络中的应用 相对于a dh o c 网络，无线传感器网络密度较大，移动性不强，通常运用在 无人值守的恶劣甚至危险的远程环境中，能源无法替代，设计有效的策略延长网 络的生命周期成为无线传感器网络的核心问题。传感器网络是以数据为中心的， 非常适合采用网络编码技术。 网络编码作为路由的超集，已经被证明对于提高某些网络的吞吐量有着很大 的作用。然而，在拥有大量节点且拓扑结构动态改变的网络条件下，利用网络编 码达到网络容量的研究工作还不丰富。l e o n g 等提出了一种随机网络编码，中继 节点在有限域上各自独立地随机选择编码系数，对输入流进行线性运算，并将结 果以广播的方式发送出去，接收节点只需知道各个编码节点进行线性运算的系 数，即可解码出原始数据。 传感器网络需要把节点资源整合起来，实现一个可靠和健壮的网络，z h a n gx w i c k e rs b 等人在文章( ( e f f i c i e n c yi ns e n s o rn e t w o r k s ) ) 中，提出了一种结合分 布式源编码和网络编码的优化算法，目的是用来提高传感器网络的容错性和可靠 性，同时对分布式源编码的压缩效率和鲁棒性进行了折中考虑。该算法首先提出 了节能和鲁棒性的量化模型，然后提出了可动态调整的链式编码结构。编码链越 长，越节省能量，但是可靠性越低；编码链越短，能耗越大，但是可靠性越高。 仿真证明，分布式随机网络编码方法在组播吞吐量和鲁棒性方面要明显优于基于 天津大学硕士学位论文第四章无线网络中的网络编码 路由的算法。然而，随着网络规模的扩大，该算法的复杂性将呈指数增长，同时 该算法主要适用的是静态的传感器网络，未考虑网络动态变化的情况。 m i t 的p e t r o v i c 等人提出了种结合网络编码的对无线信号不进行调制的策 略，并证明：运用分布式随机网络编码，未经调制的无线信号能够达到经过调制 的无线信号一样的吞吐量，这样就能节省大量因为模拟器件进行调制而消耗的能 量和降低节点的成本。 传感器网络是以数据为中心的，节点感知的数据最终将汇集到汇聚节点 ( s i n k ) 。d i m a k i s 等提出了一种数据聚合算法：每个单独的节点只保存一个数据包， 当监听到邻居节点的数据包时，就在有限域上乘一个随机系数并和自身数据相 加。这样，单个普通传感器节点可能不能解码数据，但是对s i n k 节点来说，就能 以很高的概率通过查询仅仅n 个节点而重建1 1 个数据包，使得传感器网络数据聚合 的效率得到极大的提高。 4 2 3 网络编码在无线网状网中的应用 k a t t i 等提出的基于机会的网络编码方法( c o p e ) 首次研究了网络编码在无线 环境中协议层面上的具体实现问题。在c o p e 协议中，每个节点对传输媒体进行 侦听，获得它的邻居节点的状态信息，决定进行编码的机会，并在本地的f i f o 缓存结构内进行编码，然后进行基于机会的路由。c o p e 协议要求每个节点利用 本地信息各自决定哪些数据包需要进行编码以及如何进行编码。灵活的设计使得 即使在网络交通需求未知或者网络流量剧增、或者发送接收方动态变化的情况 下，c o p e 协议仍能有效的支持多路单播流。然而该协议需要节点储存数据包并 进行编码，如果网络出现拥塞，可能就会耗费较多的节点存储空间。 另外，文件共享是无线网状网的一种典型应用，为了评估网络编码对该应用 的影响，h a m r a 在理想化m a c 协议基础上开发了特定的仿真平台，分别比较了服 务时间等性能在节点个数、盲转发( b l i n df o r w a r d i n g ) 和选择性转发( s e l e c t i v e f o r w a r d i n g ) 情况下的表现。实验结果表明应用网络编码得到的改进虽然不如在有 线网络中显著，但仍然在很大程度上提高吞吐量、缩短服务时间f l 引。 4 3 物理层网络编码 4 3 1 物理层网络编码概述 为了对现有无线网络的软硬件设备和相应的协议不做大的修改，通常在高层 实现网络编码。然而，在无线协同通信中，充分利用无限介质的广播特性，在物 天津大学硕士学位论文第四章无线网络中的网络编码 理层实现网络编码更有效。2 0 0 6 年，香港中文大学的s h e n g l iz h a n g 等人发表了一 篇( ( p h y s i c a l 1 a y e rn e t w o r kc o d i n g ) ) 的文章，首次提出了物理层网络编码的概念， 这为进一步提高无线网络的吞吐量提供了一个新的思路，从2 0 0 7 年开始，物理层 网络编码的研究也受到越来越多研究学者的关注。 在无线网络的物理层，所有的数据都是通过电磁波的形式传播。无线网络具 备很多有线网络所没有的特性，其中一点就是无线链路的广播特性：一个发送端 发出的电磁波信号往往被不止一个节点所接收。同时，一个接收端也可能同时接 收来自很多个节点的信号。 这些特性往往会造成信号间的干扰。这些干扰一般对无线网络有负面影响， 对无线多跳网络的吞吐量的影响尤其明显。例如，在传统的8 0 2 1 1 网络中，因为 存在“自干扰”效应，也就是存在一跳的包和另一临近跳的包在同一个业务流中 发生碰撞，一个线性网络多跳的理论吞吐量要少于单跳网络的1 4 。很多通信系 统的设计时，都尽量减少或着避免干扰( 比如，通过接收端的设计或者传输过程 的设计) 。实际上，在物理层网络编码的设计中，我们就可以利用干扰来提高吞 吐量。为了在多跳网络中实现这一点，必须满足以下要求： 1 ) 中继节点必须可以同时将接收到的信号转换成可翻译的输出信号然后传 送给最终的目的节点。 2 ) 目的节点必须能够从中继信号中提取出所需要的信息。 网络编码结合和从简单的迦罗华域g f ( 2 “) 提取信息的能力为满足以上的要 求提供了条件。网络编码算法通常只能应用到已被检测到的位上。特别的，它不 能用来解决同时到达接收机的电磁波信号引起的干扰。所以上面的标准1 不能被 满足。 物理层网络编码是一种处理电磁波信号接收和调制的物理层的网络编码，通 过中继节点处一种恰当的调制解调技术，电磁波信号的叠加能被映射到数据比特 流叠加的迦罗华域，使得干扰变成了网络编码中算法操作的一部分【1 4 】。 4 3 2 三节点线性网络中的物理层网络编码 下面以简单的例子来说明物理层网络编码的优势。如图4 2 所示的三节点线 性网络，n h n 3 时要交换彼此信息的节点，但都不在彼此的覆盖范围内，需要在 中继节点n 2 的帮助下完成信息的交换。 卜一 图4 2 三节点线性网络 这种三节点无线网络是协作传输的一个基本单元，并且得到了广泛的研究。 天津大学硕士学位论文第四章无线网络中的网络编码 在协作传输中，中继节点r 根据不同的信噪比状况选择不同的中继策略，比如放 大转发或者解码转发。这里主要考虑“解码转发”策略以及基于帧的通信，把 一个固定大小的帧传输所需的时间定义为一个时隙。每个节点装备一个多向天 线，信道为半双工的，从而使某个节点的传输和接收必须在不同的时隙发生。 为了对比，在介绍物理层网络编码之前，我们将先介绍传统传输和传统网络 编码的过程。在下面的例子中，所有的节点都采用半双工方式。 1 传统传输 = 寻s t! 交二二= ；s l ：二= = 时隙l时隙2 一一一一时隙3 时隙4 图禾3 传统的网络传输 在传统传输中，为了避免两个节点同时向中继节点发送信息时，两路信息在 中继节点会产生碰撞，所以n l ，n 3 不能在同一时隙向n 2 发送信息，一种可能的传 输情况如图4 - 3 所示，s 1 ，s 3 分别为n l ，n 3 要传输的信息。n 1 首先在时隙l 将s l 发送 给中继节点n 2 ，在时隙2 ，n 2 再将s l 发送给n 3 。同理，n 3 要将s 3 发送给n l 也需要 占用两个时隙。 2 传统网络编码 ：二：毒：国 时隙l时隙2 一，时隙3 图4 4 传统的网络编码 同样，在传统的网络编码中，也要避免两路信息同时到达中继会产生的碰撞。 因此，n 1 ，n 3 要分别占用一个时隙的时间发送s l ，s 3 到n 2 。如图4 4 所示，n 2 接 收到s 1 ，s 3 后，对其进行编码，比如进行按位异或操作，使得s 2 = s lo s 3 。编码后， 在时隙3 ，n 2 将s 2 向n 1 ，n 3 广播。n 1 接收到s 2 后，利用本地信息s l 和接收到的s 2 就可提取出s 3 ，s 3 = s 1 国s 2 = s lo ( s 1os 3 ) 。同理n 3 也可以提取出s 1 。由此，传统的 网络编码的吞吐量被提高了3 3 。 3 物理层网络编码 天津大学硕士学位论文第四章无线网络中的网络编码 时隙1一时隙2 图4 - 5 物理层网络编码 无线网络中的传输一般采用广播的方式，基于这一个特性，一个接收端可以 同时接收来自多个节点的信息，则不用考虑多路信息同时到达时会产生碰撞。由 于无线网络中信息以电磁波的形式传输，所以，同时到达同一节点的多路信息可 以直接叠加。则如图4 5 所示，n l ，n 3 节点可以在同一个时隙同时向中继节点n 2 发送信息，n 2 收到的信息应该是s l ，s 3 的叠加的形式，n 2 对其进行一定的处理后， 得n s 2 ，再将其广播给n l 、n 3 ，n l 、n 3 再根据已知的自己发出的信息，即可以解 出另一方发送端发送给自己的信息。相对于传统的传输，物理层网络编码技术只 用了两个时隙就完成了信息的交换，吞吐量提高了1 0 0 。但是随着吞吐量的提 高，由于信息的直接叠加，计算的复杂度也随之增加。 4 4 物理层网络编码的研究现状 目前，关于无线网络编码的研究主要集中的以下几个方面【l 5 】： 1 1 无线网络中物理层网络编码的调制技术 s l z h a n g 研究了采用电磁波进行调制的物理层编码。从信息论看，研究发 送端存在干扰情况下的调制技术是物理层网络编码的关键问题。 2 ) 协同通信中网络编码的应用 众所周知，无线通信中的信号要通过自由空间来传输，无线信道得随机时变 性和多径效应决定了无线通信技术的特殊性和复杂性。协同通信是近年来在无线 通信领域出现的对抗衰落的一个重大突破，尤其是大尺度衰落。如何将网络编码 应用于协同通信，提高协同网络的容量是很有意义的研究方向。现在有很多关于 这方面的研究。 3 ) 网络编码与纠错编码的结合 传统的有线网中提出的网络编码本身具备一定的纠错能力，如果在网络中有 几条边传输的符号出错，但错误边数不超出纠错能力范围，则可通过相应的译码 变换，所有接收节点都能正确恢复源信息。但在无线网络中，对纠错能力要求更 高。在目前的系统中，大多将网络编码与纠错