为推动基于网络编码的多路径路由(NCMR)可靠性传输机制的实用化，提出了一种面向无线Ad hoc网络应用的基于局部重传和网络编码的多路径路由(LR-NCMR)可靠性传输机制，在多路径路由基础上应用网络编码对数据包进行编码融合，引入重传机制在局部范围进行数据包重传.仿真结果表明，相比于已有的NCMR可靠性传输机制，新的方式能提高网络的传输可靠性，同时降低网络中的数据包冗余度.
To make network coding based multipath routing(NCMR)reliability transmission mechanism more practiced, local retransmission and network coding based multipath routing(LR-NCMR) reliability transmission mechanism was proposed for wireless Ad hoc network, transmitting coded packets over multipath and using retransmission within local area. Comparing with NCMR, the simulation shows that LR-NCMR is more reliable than NCMR and it can reduce the redundancy in the network.
传统无线网络中解决传输可靠性的机制主要有[1]自动重传请求(ARQ，automatic repeat request)机制、前向纠错(FEC，forward error correction)机制、多路径路由机制. ARQ机制下，当链路传输差错率较高时，会存在传输延时较长的问题. FEC与多路径传输机制都属于冗余传输，冗余传输机制不需要等待重传，将减少数据包的传输延时和网络中的冗余度. FEC机制需要源节点根据链路质量控制冗余量，在源节点处准确地估计链路差错率难以实现.多路径路由机制下将相同的数据包沿多个路径转发，通过冗余路径提高传输可靠性，但存在重复发送的问题.网络编码的应用能解决多路径传输中的重复发送问题，在提高传输可靠性的同时降低网络中的数据包冗余度.近年来，大量研究围绕NCMR可靠性传输机制展开[1-4]. Guo Zheng等[1]设计了随机网络编码与多径路由结合的可靠性传输机制.赵炜等[2]分析了基于网络编码的可靠性传输机制在非相交多径和缠绕多径2种传感器网络模型下的传输成功率及冗余度. Cai Shaobin等[3]通过不同路径传输不同的编码数据包，从而提高数据传输可靠性. Oh等[4]根据链路质量在单路径传输、多路径传输以及基于网络编码下的多路径传输3种机制之间自适应切换传输方式，在保证传输可靠性的同时，降低网络中的冗余度.本研究在分析已有冗余传输机制的可靠性基础上，对NCMR传输机制进行改进，提出了一种融合数据重传和网络编码的多路径传输机制，分析其在无线多跳网络中的传输可靠性以及冗余度.仿真结果表明，新的方式能进一步提高数据传输可靠性，并且降低网络中的数据包冗余度.
1 随机网络编码原理随机线性网络编码[5]是一种分布式网络编码方式，它能适应拓扑动态变化、无中心节点的网络.随机线性网络编码提出推动了网络编码走向实用，特别是将网络编码应用于无线网络，使得网络编码不再受限于确定的网络拓扑以及集中式的算法，其基本原理描述如下[6].
信源以m为单位，将原始数据包分割，由同一原始数据包分割而来的m个小数据包X1, X2，…，Xm属于同一分组，用分组号识别.从有限域Fq中随机地选择m个数gi1, gi2, …, gim作为编码系数，对X1, X2，…，Xm进行编码组合，编码后变成了M( > m)个数据包，用Y1, Y2, …, YM表示，即
从拓扑形状划分，多路径路由可分为2类，一类是不相交多路径；另一类是相交多路径，对应的网络模型也分为不相交路径网络模型和相交路径网络模型[7]，如图 1所示.多路径路由对应2种传输方式：一种是冗余多路径方式，从多条路径中选择一条最优路径传输数据，当最优路径失败时能迅速选择备份路径进行传输; 另一种是同时使用多条路径并行传输.不相交多路径路由建立的条件较为苛刻并且鲁棒性较差.相交多路径路由可由单路径路由扩展而来[8]，且数据包在逐跳转发时，能被下一跳节点集中多个节点同时接收，符合无线信道的广播特征.因此，本研究选取不相交路径网络模型，同时采用传输效率更高的并行传输方式进行分析.如图 1(b)所示，S、D分别需通过中继节点转发数据包.相交多路径网络模型下，网络中节点根据源节点到目的节点的跳数H分为N个集合，它们之间不存在直接链路，每一集合中的节点数为ni，网络中链路丢包率都为p.
|
图 1 多路径网络模型 |
定义传输可靠性为一次传输中，目的节点成功接收或者解编码获得源节点发送的原始数据包的概率PSD.定义标准化冗余度r为成功传输一个数据包在网络中产生的发送总次数，标准化冗余度反映了在相同的传输可靠性下网络中产生的数据包冗余量以及网络中的能量消耗.
3.1 局部重传设计应用随机网络编码和多路径的传输方式，S首先将原始数据包分割成m个小数据包进行线性编码组合，编码成M( > m)个线性无关编码数据包.这M个数据包属于同一批(分批编号识别)，S将其发向下一跳中继节点集合R1，再由中继节点集逐跳转发，直到D接收到足够多(>m)的线性无关的编码数据包，中间节点最多转发m个线性无关的编码数据包.
对NCMR可靠性传输机制进行了改进，引入局部重传，能进一步提高传输可靠性，降低冗余度.
目的节点接收到第1个编码数据包后启动该批数据包的定时器，当超过一定时间Ttimeout后，将已经收到的编码向量及其秩封装到ACK(Acknowledgement)确认包中，如图 2(a)所示，向上一跳节点传输.任意中继节点收到ACK数据包，首先判断该分组的编码系数矩阵是否满秩，若满秩，则说明目的节点完成该分组数据包的接收，清除掉缓存里该分组编码数据包；若不满秩，则节点将缓存中编码向量与ACK中编码向量线性无关的数据包发送给目的节点，并且将发送的编码数据包的编码向量添加到ACK数据包后，同时修改编码系数的秩，并将新的ACK数据包向上转发. ACK数据包的处理流程如图 2(b)所示.通常情况下，因为NCMR传输方式可靠性已经很高，使得网络中中继节点集有很高的概率存在满秩的编码数据包，所以通常在离目的节点较近的局部区域内的节点集就能完成重传，不会引入过长的延时.本研究设置离目的节点1跳内的中间节点集才参与重传.
|
图 2 新方式下ACK数据包结构和处理流程 |
由于应用局部重传后，理论分析变得复杂，为对提出的LR-NCMR(local retransmission and network coding based multipath routing)可靠性传输机制进行评估，本研究利用Matlab进行了蒙特卡罗仿真实验.初始设置原始数据包数m=3，编码冗余数据包数M=5，源节点到目的节点之间的跳数H=6，即中继节点集N=5个，每个节点集包含ni=3(i=1, 2，…，5) 个节点.
3.2 LR-NCMR与NCMR可靠性比较图 3(a)所示为LR-NCMR与NCMR可靠性传输机制的比较，当链路质量较好时(p < 0.3)，LR-NCMR与NCMR都有接近1的传输可靠性；当链路质量恶化后(p > 0.45), LR-NCMR比NCMR的传输可靠性大约高出8%，且随链路质量下降，这种改善就越明显.虽然引入重传会增加数据包的传输次数，但提高了传输可靠性，使得LR-NCMR比NCMR标准冗余度要低，且随链路质量下降，这种改善就越明显，如图 3(b)所示.
|
图 3 LR-NCMR与NCMR仿真结果对比 |
为考查各参数对在NCMR以及LR-NCMR下传输可靠性及标准冗余度的影响.本研究将改变源节点到目的节点之间的跳数H、源节点编码冗余包数M，以及有限域大小q，对比2种链路丢包率(p=0.5，0.6) 下的传输可靠性及冗余度，其他参数参照初始设置.
跳数H.随着源节点到目的节点之间的跳数H的增大，在NCMR以及LR-NCMR下传输可靠性小幅度下降，如图 4(a)所示.网络中的传输冗余度会随跳数线性增长，如图 4(b)所示，这主要是因为网络规模增大，参与转发的节点增多，源节点发送一个数据包，引发的网络中整体数据包转发次数线性增长.
|
图 4 可靠性仿真结果 |
编码冗余量M.在设置原始数据包个数m=3下，改变源节点编码冗余量M. M的增加能提高2种方式下的传输可靠性，但当冗余量超过6后，这种提升效果会趋缓，传输可靠性提升出现平台效应，如图 4(c)所示.虽然M越大，源节点注入的编码数据包越多，但由于传输可靠性的提升，标准冗余度会出现明显下降趋势，但随着传输可靠性平台效应的出现，标准冗余度也会出现上升的趋势，如图 4(d)所示.
有限域大小q.对于一般网络规模不大的情况，有限域大小选取为一个字节的长度，即q=8，就能保证随机生成编码向量之间的线性无关性.仿真结果也验证了，当网络规模不大时，随着有限域的增大，网络传输可靠性会出现上升趋势，但这种影响效果不明显, 如图 4(e)所示；同时生成的编码向量之间线性相关性减小，线性相关的编码数据包随之减少，网络中标准冗余度也呈下降趋势，如图 4(f)所示.
由于LR-NCMR是基于NCMR的改进方式，所以这2种传输机制下参数对传输可靠性、标准冗余度的影响效果基本一致.但无论在何种参数设置下，LR-NCMR的传输可靠性、标准冗余度都要优于NCMR.
4 结束语笔者提出了一种LR-NCMR可靠性传输机制.利用多路径网络模型进行分析，仿真结果表明，LR-NCMR提高了NCMR的传输可靠性同时降低了标准冗余度，且随着网络中链路质量下降，改善效果更加明显.下一阶段将分析LR-NCMR运行在真实网络协议上的应用效果，对可靠性、延时、吞吐量等性能进行更加全面的评估，为设计面向无线网络的更实用可靠性传输机制提供依据.
| [1] | Guo Zheng, Xie Peng, Cui Junhong, et al. On applying network coding to underwater sensor networks[C]//Proceedings of the 1st ACM International Workshop on Underwater Network. New York: ACM, 2006: 109-112. |
| [2] |
赵炜, 唐振民, 纪淑标, 等. 基于网络编码的传感网多径模型分析[J]. 计算机工程与设计, 2012, 33(3): 875–879.
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. |
| [3] | Cai Shaobin, Gao Zheng, Yang Deshen, et al. A network coding based protocol for reliable data transfer in underwater acoustic senor[J].Ad hoc Networks, 2013, 11(5): 1603–1609. doi: 10.1016/j.adhoc.2013.02.001 |
| [4] | Oh S Y, Gerla M, Tiwari A. Robust MANET routing using adaptive path redundancy and coding[C]//Communication System and Networks and Workshops, CSNW. Bangalore, India: IEEE, 2009: 1-10. |
| [5] | Li S Y R, Yeung R W, Cai Ning. Linear network coding[J].IEEE Transaction On Information Theory, 2003, 49(2): 371–381. doi: 10.1109/TIT.2002.807285 |
| [6] |
宋小全, 胡鹏, 宋福晓. 基于随机网络编码的无线网络可靠性研究[J]. 深圳大学学报:自然科学版, 2014, 31(1): 51–56.
Song Xiaoquan, Hu Peng, Song Fuxiao. Research on reliability based on random network coding in wireless network[J].Journal of Shenzhen University Science and Engineering, 2014, 31(1): 51–56. |
| [7] |
郝静, 冯海林. 基于网络编码的传感器网多径模型分析[J]. 计算机应用研究, 2010, 27(11): 4260–4263.
Hao Jing, Feng Hailin. Wireless sensor network data reliability analysis based on network coding[J].Application Research of Computers, 2010, 27(11): 4260–4263. |
| [8] | Yi Jiazi, Cizeron E, Hamma S, et al. Simulation and performance analysis of MP-OLSR for mobile Ad hoc networks[C]//Wireless Communications and Networking Conference, WCNC. Las Vegas: IEEE, 2008: 2235-2240. |