基于随机网络编码的无线网络可靠性研究

宋小全，胡 鹏，宋福晓

北京跟踪与通信技术研究所，北京100094

在传统通信网络中，节点只对收到的信息进行存储和转发.而网络编码则允许中间节点对接受到的数据进行编码处理，将多个数据包进行融合后转发，从而获得网络性能增益.Ahlswede等［1］指出，网络编码能使有线网络中组播传输吞吐量达到传输的理论上限.Ho等［2］提出分布式的码构造算法—随机网络编码，能较好地适应拓扑动态变化的网络;Chou等［3］提出面向现实的网络编码及其相应的设计原则，大大推动了网络编码的实际应用，尤其是在无线网络领域的应用.

无线信道的传输错误率通常较高，因而其数据传输可靠性较弱.在无线网络中采用网络编码，不仅能提高网络传输的吞吐量，还能提高传输可靠性［4-7］.传统无线网络中解决传输可靠性的机制主要有［6-7］:自动重传请求机制(automatic repeat request，ARQ)、前向纠错机制(forward error correction，FEC)和多路径路由.ARQ通过目的节点请求源节点重发出错数据包来恢复出错的数据包，但当链路传输差错率较高时，会产生传输延时较长的问题.FEC在源节点的编码数据包通过增加冗余数据包来实现可靠传输，需源节点根据链路质量控制冗余量，因此难以准确估计链路差错率.多路径路由利用无线信道的广播特性建立源节点到目的节点多条传输路径，将相同的数据包沿多个路径转发，通过冗余路径提高传输可靠性，但存在重复发送的问题.采用随机网络编码能解决多路径传输中的重复发送问题，进而提高网络传输效率.Oh等［8］研究了网络编码结合基于链路状态的多径路由在移动自组织网络中的应用，并通过仿真评估传输成功率和延时等网络性能.Yang等［9］设计了网络编码与缠绕多径路由结合的应用方案.赵炜等［10］分析了网络编码在非相交多路径和缠绕多路径两种传感器网络模型下的传输成功率及冗余度.Cai等［11］提出混合多路径模型，并用网络编码分析其传输成功率.Wang 等［12］和Wei等［13］分别采用确定性编码和随机网络编码，通过不同路径传输编码数据包，分析网络中的能量消耗问题.文献［8，12-13］缺少理论分析与仿真结果对比，文献［9-11］使用的网路模型中，所有链路的丢包率一样，模型过于理想化.本研究阐述随机网络编码与多路径路由结合的可靠性传输机制，针对存在不同链路丢包率的多路径网路模型，通过数值与仿真实验，分析其在无线多跳网络单播中的可靠性及抗干扰特性.

1 随机网络编码与多路径传输

1.1 随机网络编码原理

随机线性网络编码［14］是一种分布式网络编码方式，它能适应拓扑动态变化、无中心节点的网络.随机线性网络编码的提出推动了网络编码走向实用，特别是将网络编码应用于无线网络，使网络编码不再受限于确定的网络拓扑及集中式的算法.以下将从发送端、转发节点和接收端分别描述随机线性网络编码基本原理.

源节点.如图1，信源以m为单位，将数据包分组，每组都用X1，X2，…，Xm表示m个数据包.从有限域Fq中随机地选择m个数gi1，gi2，…，gim组成第i个数据包的编码，对X1，X2，…，Xm进行编码组合，编码后变成了M(＞m)个数据包，用Y1，Y2，…，YM表示，即信源把编码数据包Y1，Y2，…，YM的组标志和相应的编码 gi1，gi2，…，gim添加到数据包前发送出去，编码后的数据包格式如图2.

图1 随机网络编码示意图Fig.1 Random network coding scheme

图2 随机网络编码下的数据包结构Fig.2 Structure of random network coding packet

中间节点.中间节点接收到一个数据包，首先判断与缓存中已有的编码数据包是否线性相关.若无关，则放入缓存;否则，丢弃.假设中间节点R缓存中存在k个相同组标识的线性无关的数据包Y1，Y2，…，Yk，从有限域Fq中随机选择k个数生成局部编码对应的编码过程为Yri=由此，得到原始信息对应的全局编码，利用新编码更新数据包中的编码系数后继续向下发送.

目的节点.目的节点接收到至少m个线性无关编码数据包后，可根据式(1)解码得到原始数据包.

其中，gij(i=1，2，…，m;j=1，2，…，m)为目的节点得到的编码系数;为对应的编码数据包.Ho等［15］指出，当所有节点的编码系数都在有限域Fq内随机产生，无差错传输时，目的节点成功解码的概率超过(1-d/q)β.其中，d为目的节点数;q为有限域大小;β为产生的随机编码系数数目.若选择Fq=28，即q=8，β=3，则有98.8%的成功解编码率，相应数据包中只需增加3×8=24 bit的数据记录编码系数，不会带来过高的编码管理开销.

1.2 多路径路由与网络编码

在传统路由机制下，无线多跳网络中源节点会依据不同的路由指标确定一条到达目的节点的传输路径，将数据包通过中继转发至目的节点.这种路由方式忽略了无线信道的广播特性，即数据包会被其发送节点通信范围内的多个邻居节点监听.多路径传输机制充分利用此特性，发送节点会选择多个邻居节点组成潜在的转发节点集合并参与数据包转发，从而提高传输可靠性.

本研究通过一个实例理解多路径传输思想及其与网络编码结合的优势.如图3，3个节点S、R和D组成的通信网络，S-R、R-D和S-D之间链路上数据包传输成功概率分别为1.0、0.9和0.5，网络采用时分复用的信道控制方式.假设S需发送数据包P1和P2到D，传统路由方式下会选择传送成功率最高的链路转发，即选择S-R-D路径发送，传输成功概率为1.0×0.9=0.9.实际上，由于无线信道具有广播特性，S向R发送数据时，D能侦听到S发送的数据.D将缓存侦听到S发送给R的数据包，假设D侦听到了数据包P1，由于D是目的节点，D将不再向下转发，否则D可参与转发.此时，S-D之间成功传输概率为1-(0.5×0.1)=0.95.可见，针对一个数据包的传输，选择2条传输路径的传输成功率较1条传输路径的成功率提高了5%，R只需转发P2就能保证D收到P1和P2.但D需告知R自己已侦听到了P1，才能保证R不重复转发P1，这需在网络中建立协作机制，必将消耗额外的通信资源.

图3 网络编码在无线网络中应用Fig.3 Application of network coding in wireless network

采用随机网络编码，不需建立节点之间的协作机制就可避免重发数据包.如图3(b)，S将P1与P2线性组合成两个编码数据包后发送给R，假设D侦听到了其中的一个编码数据包α1P1+β1P2，［αi，βi］为各编码数据包中的编码系数.R将接收到编码数据包再编码，如式(2)，此时R只需将α3P1+β3P2和α4P1+β4P2中的一个转发给D，假设为α3P1+ β3P2，在保证［α1，β1］和［α3，β3］线性无关的条件下，D能根据式(3)解编码得到P1和P2，解决了重复发送问题.

表1为图3实例中全网络发送的时隙分配情况，详细列出了每个时隙中各节点缓存的数据包.从表1可见，采用随机网络编码与机会路由结合的方式，少占用一个发送时隙，从而提高了网络吞吐量.可见，随机网络编码与多路径传输结合的方式，可有效提高网络传输可靠性.

表1 采用网络编码前后的时隙分配情况Table1 Time slot assignment with/without network coding

2 传输可靠性分析

本研究定义传输可靠性为在1次传输中，目的节点成功接收源节点发送的一组原始数据包的概率［16］.图4为一种无线两跳网络模型.S和D分别为源节点和目的节点，两节点间无直接链路，其共同邻居节点的集合R={R1，R2，…，RN}.S，D与 {R1，R2，…，RN}之间的链路上的数据包成功传输概率分别为{pS1，pS2，…，pSN}和{pD1，pD2，…，pDN}，不妨设按降序排列成功传输概率，即pS1≥pS2≥…≥pSN和pD1≥pD2≥…≥pDN.

图4 无线两跳网络模型Fig.4 Wireless two-hop multipath network model

2.1 单路径传输

对传统单径路由机制，选择链路质量最好的一跳路径进行传输，即单个数据包传输成功概率为

若采用端到端前向纠错机制，源节点在原始数据包中加入数据冗余增加传输可靠性.假设将m个原始数据包编码成Msingle(＞m)个数据包进行传输，目的节点D只要能成功接收到其中m个数据包就能恢复原始数据包，则成功完成一次传输的概率为

2.2 多路径传输

在多路径路由机制下，源节点寻找多条到目的节点的路径进行数据传输，只要有一条路径有效就能完成数据包发送，所以多路径传输下，单个数据包发送成功的概率为

同样采用端到端前向纠错机制，发送存在数据冗余的M个数据包，目的节点能成功完成m个原始数据包接收的传输概率为

2.3 网络编码

在此分析基于网络编码的多路径传输机制的可靠性.采用随机网络编码和多径的传输方式，S先将m个原始数据包进行线性编码组合，编码成M(＞m)个线性无关编码数据包，它们属于同一批(分批编号识别)，发送给中继节点集合R，再由R转发给D.R中节点i成功接收k个编码数据包的概率为

其中，i=1，2，…，N.

定义qi，r为目的节点D接收来自R中i节点的r个编码数据包的概率.因为每个中继节点最多发送m个编码数据包，故得

则目的节点共接收到R转发的k个编码数据包的概率为

其中，ri=0，1，…，k，且∑ri=k.

D成功接收m个线性无关的编码数据包就能解编码得到原始数据包，再向上游节点发送Ack确认数据包，让上游节点停止编码数据包转发，可见S到D完成一批编码数据包传输的概率为

3 数值仿真实验

3.1 数值实验

本研究针对图4模型，设置3个中间节点组成转发节点集进行数值实验.假设链路上包传输成功概率初始值为 {pS1，pS2，pS3}={0.8，0.6，0.4}，{pD1，pD2，pD3}={0.8，0.6，0.4}.为对比 3 种传输方式的可靠性，初始化设置3种传输方式下原始数据包数m=3，编码冗余数据包数Msingle=M=5.为评估3种传输方式的抗干扰特性，以S-R1链路为例，改变该链路包丢失率e=1-pS1，并观察链路质量对3种传输方式下可靠性影响，如图5(a).由于随机产生的编码之间线性相关的可能性很小，所以对应用了网络编码的传输方式，我们只需对比不同编码冗余数目M下的传输可靠性，如图5(b).由图5(a)可见，网络编码与多路径传输相结合的传输方式可靠性最优，其次是多路径传输方式，这两种方式下的传输可靠性都远优于单路径传输方式.随着S-R1链路包丢失率增加，3种传输方式下的传输可靠性都会下降，但用了网络编码的传输方式其可靠性下降最缓，抗干扰性更强.单路径传输方式下的传输可靠性下降较快，当S-R1链路恶化到一定程度，源节点会选择其他路径发送数据，可靠性将不再受e变化影响.图5(b)显示，网络传输可靠性随M的增加而提高，M超过一定值后性能改善效果趋于稳定.增加M意味需发送更多数据包，这会消耗更多的网络资源，所以在确定网络编码方案时，需折衷考虑网络可靠性提升和网络资源的消耗.

图5 可靠性数值分析结果Fig.5 Reliability numerical result

3.2 仿真实验

图6 可靠性仿真实验结果Fig.6 Reliability simulation result

按照3.1节设置参数，用matlab进行蒙特卡罗仿真实验，源节点1 000次发送原始数据包，统计目的节点成功解编码的次数得到传输可靠性，仿真结果如图6(a)和图6(b).仿真实验结果进一步验证了理论分析结果.应用网络编码方式下，仿真实验与理论分析结果比较如图6(c)，相同参数设置下，仿真实验中传输可靠性略逊于理论分析结果.我们认为这是因为理论分析时并未考虑目的节点收到的编码数据包的编码之间的线性相关性.仿真实验中，由于有真实的有限域编码参与运算，即使目的节点接收到足够数量的编码数据包，只要对应的编码矩阵不满秩，不可逆，就无法通过式(1)完成解编码得到源节点发送的原始数据包.

结 语

研究随机网络编码在无线网络可靠性传输中的应用，分析基于单路径路由的前向纠错机制、多路径路由机制、随机网络编码与多路径路由相结合的机制，在无线多跳网络单播中的传输可靠性.数值分析与仿真结果表明，相比传统单路径和多路径传输方式，网络编码与多路径路由相结合的机制能提高无线网络的可靠性，抗干扰能力更强.由于节点需缓冲多个数据包进行编解码，采用网络编码会增加传输延时.下一步，我们将研究网络编码引入的传输延时，分析网络编码与多路径路由结合的可靠性传输机制中不同参数对传输延时和可靠性的影响，为设计更实用的可靠性传输机制提供理论依据.

/References:

［1］Ahlswede R，Cai N，Li S R，et al.Network information flow ［J］.IEEE Transactions on Information Theory，2000，46(4):1204-1216.

［2］Ho T，Médard M，Effros M，et al.Network coding for correlated sources［C］//Proceedings of Conference on Information Sciences and Systems.Princeton(USA):［s.n.］，2004.

［3］Chou P A，Wu Y，Jain K.Practical network coding［C］//Allerton Conference on Communication，Control and Computing.Monticello(USA):［s.n.］，2003.

［4］Ghaderi M，Towsley D，Kurose J.Reliability gain of network coding in lossy wireless networks［C］//The 27th Conference on Computer Communications.IEEE INFOCOM.Phoenix(USA):［s.n.］，2008:2171-2179.

［5］Ghaderi M，Towsley D，Kurose J.Reliability benefit of network coding［R］.TR-07-08.Massachusetts(USA):University of Massachusetts Amherst，2007:1-13.

［6］Guo Z，Wang B，Xie P，et al.Efficient error recovery with network coding in underwater sensor networks［J］.Ad Hoc Networks，2009，7(4):791-802.

［7］Ma L，Lin Z，Zhang Z，et al.Improving reliability in lossy wireless networks using network coding［C］//IEEE International Conference on Communications Workshops.Budapest:［s.n.］，2013:312-316.

［8］Oh S Y，Shen B，Gerla M.Network coding over a MANET proactive link state routing protocol and TDMA scheduling［C］//Military Communications Conference，IEEE MILCOM.Orlando:［s.n.］，2012:1-6.

［9］Yang Yuwang，Zhong Chunshan，Sun Yamin，et al.Network coding based reliable disjoint and braided multipath routing for sensor networks［J］.Journal of Network and Computer Applications，2010，33(4):422-432.

［10］Zhao Wei，Tang Zhenmin，Ji Shubiao，et al.Analysis of sensor network multipath routing model based on network coding ［J］.Computer Engineering and Design，2012，33(3):875-879.(in Chinese)赵 炜，唐振民，纪淑标，等.基于网络编码的传感网多径模型分析［J］.计算机工程与设计，2012，33(3):875-879.

［11］Cai S，Gao Z，Yang D S，et al.A network coding based protocol for reliable data transfer in underwater acoustic sensor［J］.Ad Hoc Networks，2013，11(5):1603-1609.

［12］Wang L，Yang Y，Zhao W.Network coding-based multipath routing for energy efficiency in wireless sensor networks［J］.EURASIP Journal on Wireless Communications and Networking，2012，2012(1):1-15.

［13］Zhao Wei，Tang Zhenmin T，Yang Yuwang，et al.Network coding based reliable multi-path routing in wireless sensor network ［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2013，11(12):7754-7761.

［14］LI S Y R，Yeung R W，Cai N.Linear network coding［J］.IEEE Transactions on Information Theory，2003，49(2):371-381.

［15］Ho T，Medard M，Shi J，et al.On randomized network coding［C］//Proceedings of the 41st Annual Allerton Conference on Communication，Control，and Computing.Monticello(USA):［s.n.］，2003，41(1):11-20.

［16］Hao Jing，Feng Hailin.Wireless sensor network data reliability analysis based on network coding［J］.Application Research of Computers，2010，27(11):4260-4263.(in Chinese)郝 静，冯海林.基于网络编码的传感网多径模型分析［J］.计算机应用研究，2010，27(11):4260-4263.