《网络编码在无线网络中的信息交换》由会员分享，可在线阅读，更多相关《网络编码在无线网络中的信息交换（9页珍藏版）》请在金锄头文库上搜索。
1、网络编码在无线网络中的信息交换沈丽丽侯春萍杨家琛天津大学电子信息工程学院，天津3 0 0 0 7 2摘要：网络编码是一种全新的概念，组播网络中应用网络编码可以得到由最小割最大流理论 确定的网络客量本文研究了在无线网络中进行信息交换时，结合无线网络中物理层的广播特性采用C O P E 网络编码得到相邻节点的信息，进行网络编码。研究表明与传统意艾上简单 的路由算法相比，采用这种C O P E 网络编码进行信息侍输可以有效支持多个单播流，而且有很好的鲁棒性，能够提高网络的吞吐率。关键宇：信息互换；网络编码；C O P EI n f o r m a t i o ne x c h a n g eu s
2、i n gn e t w o r kc o d i n gi nw i r e l e s sn e t w o r k S H E NL i l i ，H O UC h u n p i n g ，Y A N Gj i a c h e n( S d l 0 0 do f E l e c m 商cI n f o r m a t i o n I n f o r m a t i o nE n g i n e e r i n g ，甄岫i i l lU n i v e m t y , T l ；a n j i n3 0 0 0 7 2 ，C h i n a )A b s t r a e t ：N e
3、t w o r kc o d i n gi sa1 3 e wm e t h o db vw h i c ham u l t i c a s tn e t w o r kc a na c h i e v et h en e t w o r kc a p a c i t yd e t e r m i n e db yt h em a x f l o wa n dl n i n - c u tt h e o r e m T h i sp a p e rs h o wm u t u a le x c h a n g eo fi n d e p e n d e n ti a f o r m a ：c
4、i o nb e t w i nt w on o d e si naw i r e l e s sn e t w o r kc a nb ee f f i c i e n t l yc o m b i n e dw i t hn e t w o r kc o d i n ga n db r o a d c a s tp r o p e r t yo f f e r e db yw i r e l e s sm e c l i m m l ti n u o d u c e sC O P E , a no p p o r m n i s t i ea p p r o a c ht On e t w
5、 o r kc o d i n g C o m p a r e dw i t ht r a d i t i o n a lr o u t i n gC O P Ec a l li n o r e a s et h en e t w o r kt h r o u g h p u t ，a p p l yf o rm u l t i p l et m i c a s tf l o we f f i c i e n t l ya n dr o b u s t l y K e y w o r d s ：i n f o r m a t i o ne x c h a n g e ；n e t w o r
6、kc o d i n g ；C O P E1引言在现有的计算机通信网络中，信息传输都是由源节点经过中间节点，以存储转发的方式传送到目标节点的。除了数据复制以外，一般来说在网络的中间节点并不需要做任何数据处 理。但在许多实际应用中，为了信息分析、信息安全以及交换的目的，总是要在中间节点进行某种形式的数据处理。之前人们普遍认为，中间节点所进行的数据处理对数据传输过程本身并不会带来任何好处；然而，香港中文大学的R A hl s w e d e 等人从信息论的角度出发提出了网络编码的概念，它可以大大提高网络中的传输容量，从而可以实现利用有限的网络资源 传输更多的信息。像很多基本的概念一样，网络编码也是
7、基于一个很简单的思想。网络编码是指在通信网络中，可以在网络的中间节点上对接收到的信息进行一定形式的编码处理，然后再传输出去，最后在信宿节点上，通过一定的处理方式，译出信源所发的信息，而不是像5 8 传统通信网络中那样在中间节点上只是进行存储转发。 嗣路编码指出允许路由器对不同的信息流进行编码组合以达到香农最大流最小割定理规定的上界。L ie t a l 吲在此基础上，进一步证明了在单信源多信宿情况下应用线性网络编码理论，一定能够达到该上界。线性网络编码将原先分立于物理层和网络层的两个核心概念：编码和 路由有机的融为一体，彻底改变了交换、路由器只能对信息进行存储转发的传统多播模式，建立起一种全新
8、的网络体系结构及信息编码和传输模式。网络编码代表了一种协同工作的理 念，这使得它的应用不仅局限于改进多播增加网络容量；与其它技术相结合已经应用于网络 管理，纠错，信息安全P 2 P 对等网络通信，路由和交换等数十个领域 3 - 6 1 从A h l s w e d e 等提出在中间节点对不同的信息进行网络编码开始，已经有大量关于编解码的文章了，它们都从理论方面证明了网络编码确实可以提高吞吐率，但是很少有针对无线环 境的。本文重点就集中在如何在无线A d - h o c 网络中充分寻找机会来进行网络编码。首先我们 介绍如何进行机会主义路由，在无线网络中应用网络编码来进行信息交换，证明其能够使网络
9、的吞吐率提高2 倍。然后对网络编码的基本理论有了定理解之后，作者重点对无线网络 编码进行了深入的研究，根据无线网络的物理层广播的特性，给出了一种C O P E 网络编码，证 明了对于单播传输的无线网络，采用网络编码能够提高网络带宽有效性、提高吞吐率，增强网络的鲁棒性。2 机会主义路由网络编码是基于网络层的网络设计，这就需要在网络层知道整个网络的拓扑连接情况。 对于有线网络来说，节点之间的链路一旦建立，就可以提供可靠有效的传输，所以网络层就 可以直接用有向图来表示整个网络的拓扑结构。但是，在无线网络中，链路是根据节点之间 的位置关系和现有可以利用的资源动态建立的而且随着节点的移动，旧的节点的离开
10、及新 的节点的加人，发生比较大的变化，这就给网络层的路由带来了麻烦。我们用G ( v ，E ) 来表示整个网络的拓扑结构，其中V 表示所有节点的集合，E 是所有边的集合。相互独立的信源之间的信息互换u - s 1 是无线通信网络中的一种特殊情况，在这种情况下， 结合无线网络中的无线组播特性，应用网络编码的信息处理方式，可以在节省网络的能量消耗方面给我们带来很大的好处。2 1 信息互换我们首先说一下什么是信息互换，其定义很简单，如下所示：假定在个基于包的无线通信网络中有两个相互独立的信源节点A 和B ，其中，节点A 想把它自己产生的数据包串【X - ( n ) 1 发送给节点B ，而节点B 想把
11、它自己产生的数据包串f x 2 ( n ) 发送给节点A 。信息互换的广泛用途；它可以用在语音通信，两方参加的可视会议以及及时消息的传 输等场合。事实上，信息互换不但可以应用在上面所举的那些一般地端到端通信上，而且可 以应用在更广泛的情况下，比如说，节点A 和B 并非两个需要进行通信的终端，而是网络中间的两个路由器，但是它们之间需要交换互有的信息。节点A 和B 之间的信息互换一般是由 两个单播过程完成，一个是从节点A 到B 传输，另一个是从节点B 到A 传输。因为这两个单 播过程中传输的是不同的信息，所以它们好像只能分别对待，各自独立建立链路，完成传输。5 9 但是，实际上，并非如此，在这里，
12、我们可以应用网络编码，改变传统的信息处理方式。 下面我们用一个简单的例子来说明网络编码在此处的基本应用思想。接八点( A P j接入点( A P( a J 没有编码嘞编码图1 信息互换的例子Bf x I n图1 是无线局域网( W L A N ) 的一个简单例子。假定w L A N 工作在有基础设施模式下， 也就是网络中存在一个接人点A P 将网络连接到有线网络。与接人点A P 有关的通信都分为上 行链路和下行链路。在这种结构下，我们假定节点A 和B 需要互换信息。那么，传统上，如图l ( a l 所示，数据包( x I ( n ) 】( 或f x 2 ( n ) 1 1 ) 需要先沿上行链路
13、发射到接人点A P ，然后再由接 入点在下行链路上发射到B ( 或A ) 。现在，我们可以结合网络编码给出一种更好的方案，如图l ( b ) 所示：首先，在上行链路阶段，A ( 或B ) 发射f x l ( n ) 】( 或 X 2 ( n ) 1 ) 给A P ，这与传统方式的 处理方式是一样的。不同在于第二阶段，由于无线媒质是一种广播媒质，所以在A P 点。我们可以发射【x 1 0 1 ) 】和 X 2 ( n ) l 的异或 x ，( n ) ) 0 f x ：( ) ，此包可以沿下行链路同时到达A 和B ，然后节点A ( 或B ) 可以根据接收到的信息 X 。( n ) 0 【X ，(
14、 n ) ) 和自己原有信息的 X 1 ( n ) ( 或 x “) 】) 异或，解出想要接收的信息 x 2 ( ) ) ( 或t x l ( n ) ) ) ，这样就完成了信息的传递。 上述传输体制的实现用到了两点：一个是无线通信网络的传输媒质是一种广播媒质；另一个是采用了网络编码。我们可以看到，这种新体制的好处就是在传输的第二个阶段，只用 一个发射就完成了整个传输，而不是传统方法的两次发射，这样就节省了能源( 不但包括能 量，如果是频分多址的话，还有频率资源，发射机等) 。2 _ 2 信息互换的一般性描述上面结合一个简单的例子，可以看到在无线网络的信息互换中，结合网络编码和无线组 播特性的
15、这种新的处理方案给我们带来的好处，下面来讨论一下信息互换的一般形式。假设某个需要信息互换的两个节点中间需要很多个节点作为中继，设共用到“L 3 ) 个节 点。如图2 所示： 瓣小仪图2 多个节点之问的信息互换如图2 所示，为了方便表示，我们给每个节点f 引入了一个相应的虚拟节点f ，它充当着每个节点的发射机的角色，可以将两条路径要传输的包缓存，并且限制着这个节点的最大可6 0 传输的信息速率。每当机会出现，路由器会联合两个包分别向两个方向传输异或后的结果。而相邻的两个接收节点已经知道了其中一个包，将其与收到的包再进行异或，就会得到个新的包。一次广播可以使两个路由器都能收到新的包，这样就可以将容
16、量加倍。实现信息互换的一般性描述如下；XJ ( n ) = X 2 ( n ) = X l ( n )( 1 )( n ) = 圪。( 哟= X ：( n )( 2 )K ( n ) = X 性l ( n ) = I f + l ( n )= X ，( n 一“一1 ) ) 0 X 2 ( n 一( L - D ) ( 3 )I = 2 L - 1其中，n 代表时刻，当n 1 时，认为x ，( n ) 为携带数据全为0 的包。现在我们用演绎法来证明上面的编码方案是可行的，即经过f 1 个时延节点f 能够恢复出 X 1 ( n ) ，经过L f 个时延a 醣# 恢复I X 2 ( n ) 。当n = l 时，节点1 能够恢复出( x l ( n ) ，节点L 能够恢复出f X 2 ( n ) l ，因此n = 1 时，证明成立。我们假设时刻凡节点f 诣够恢复出X 。( 1 ) ，X 。一“一1 ) ) 及 X ：( 1 ) ，X ：
