基于网络编码技术的水声网络路由协议研究

祝　琳，江志浩，李　迅

(中国人民解放军91635部队,北京 102249)



基于网络编码技术的水声网络路由协议研究

祝琳，江志浩，李迅

(中国人民解放军91635部队,北京 102249)

摘要：针对水声通信传输速率低、时延大的缺点，提出在水声环境下将随机网络编码方法应用于节点之间广播通信，利用NS-2仿真软件对网络编码路由协议NCR(Network Coding Routing)进行仿真，并分别从投递率、投递时延、协议开销和冲突率4个网络性能评价指标进行了分析。发现在节点数量为50的随机网络拓扑结构中，与传统的泛洪(Flooding)方式相比，NCR协议的数据包投递率大约提高了20%～50%，网络时延降低了大约50%～60%，NCR协议改善了水声通信网络传输效率，提高投递率，提高能量利用效率和传输可靠性，时延和数据冲突率有效降低，网络性能获得明显改善。

关键词：水声通信；网络编码；协议；投递率

0引言

随着人类对海洋的探索、开发和利用程度越来越深入，无论是军用还是民用领域，都对海洋环境下的信息传递有着巨大的需求。建立可靠、安全的水下通信网络，是实现海洋国土安全、海下科学研究、海洋勘探开采各种工作的关键问题。声信号在水下的传播有扩散损耗、吸收损耗和边界损耗，且传播距离越大、信号频率越高，传播损失也越大[1]。由于水下设备多采用电池供电，能够利用的能量十分有限，因此需要设计一个具有高可靠性、大吞吐量、低功率消耗和短传输时延的水声通信网络[2]。传统的路由算法只对数据存储和转发[3]，不对传输的信息进行处理，最终导致多播通信可以实现的传输容量远远小于最大流最小割定理(Max-Flow Min-Cut Theorem)所确定的容量上限，不能实现吞吐量的最大化[4]。网络编码技术不同于传统路由算法，该技术能够使网络中间节点对信息进行融合处理，即中间节点不仅仅是简单的存储转发，还可以对信息进行一定处理，增加单次传输的信息量，提高网络的性能[5]。大量研究显示网络编码技术可以提升多播、单播和广播等方式的网络吞吐量，可明显提高传输效率[6]，该技术已经在P2P网络中、分布式存储、无线网状网、无线自组织网络、无线传感网络以及网络安全中得到有效应用[7-9]。

传统水声通信广播信息一般采用泛洪法，泛洪方式是一种节点广播数据方式[10，11]，这种方法主要特点是算法简单，尤其在网络拓扑结构时常发生变化时适合使用该方法，但是由于众多非目的节点都接收到数据包并参与了数据包的转发，导致网络开销太大，数据传输率低，甚至造成广播风暴[12]。

1NCR协议算法原理

NCR协议将随机网络编码算法应用于网络中除源节点以外的所有中间节点。编码系数均在有限域GF(q)[13]上随机选取，且对节点数据包进行线性组合[14]，因此该算法也称随机线性网络编码算法。解码时采用高斯消元法，通过求解编码系数组成的线性方程组来恢复原始消息，文献[14]已经证明只要有限域GF(q)足够大，就可以使目的节点的全局编码矩阵满秩，从而能够以较高概率完成解码操作。

在随机线性网络编码算法中，各中间节点先将要发送的数据包进行编码，形成新的组合再发送出去，所有其他节点收到足够的已编码数据包进行再编码并转发出去，当目的节点收到足够多的编码包后，就可以解码得出原始数据包。因此各节点输入端收到的一定数量的已编码数据包，是原始数据包的线性组合。

用理论模型描述如下：在有向无环网络G=(V,E)中，源节点S∈V，接收节点T∈V，具有单位容量的链路e∈E，广播容量h是发送节点和接收节点间所有割的容量中的最小值，x1,...,xh为源符号，g(e1),...,g(eh)为有限域GF(q)上全局编码向量，数据包中的每个元素编码后得到的线性组合y和带有随机系数的向量g(e)(编码向量)，线性组合y可以表示为：

(1)

通常取q=2n，局部编码向量的元素在有限域GF(2n)上随机选择，所以只要全局编码向量g(e1),...,g(eh)的矩阵Gt秩为h，接收节点T就可以恢复出源符号x1,...,xh。

假设数据包能够携带N个符号，每条链路上的符号y(e)流可以被分组成向量y(e)=[y1(e),y2(e),....,yN(e)]，源符号xi流被分组成向量xi=[xi,1,xi,2,...,xi,N]，则任何接收端可以从接收的数据包中恢复出h个源向量x1,...,xh，如式(2)：

(2)

解码方案采用渐进式译码方法[15]，每收到一个编码数据包，对由系数和线性组合组成的增广矩阵使用行初等变换化简一次，使增广矩阵变为行最简型阶梯矩阵，收到第h个线性分组经过化简后，原来的增广矩阵的左侧为h阶单位矩阵右侧为化简后得到的原始数据分块，如式(3)所示，以h=4为例，如图1说明解码过程。

(3)

图1　解码化简结果

NCR协议流程如图2所示。

图2　协议流程图

2协议仿真结果分析

采用NS-2仿真软件对NCR协议进行仿真，应用层为CBR数据流。建立50个节点的随机网络拓扑结构，如图3所示，各节点服从[0,1]均匀分布，随机分布在1 km×1 km的矩形区域内。

由于NS-2仿真软件提供的无线电环境的传输模型不适用于水声传输模型，需对其修改。式(4)是无方向性发射声源，W为平均辐射声功率。参考基准声压pref一般取1 μPa，对应的水中基准声强式(5)代入式(4)可以得到距离为r处的辐射声功率式(6)：

(4)

(5)

(6)

式中，发送因子ρ为每个节点发送数据包数量与接收的新数据包数量的比[16]。ρ决定了节点的转发概率每个节点能发送数据包的数量，对于NCR协议而言，若ρ值较大节点的解码率越高，若ρ值较小可能使节点不能收到足够数量的编码包用于解码。因此，仿真部分给出各协议发送因子ρ在[0,1]范围内不同取值下的仿真结果。

图3　随机拓扑结构

以下是在节点数为50的随机网络拓扑结构对数据包投递率、数据包投递平均时延、协议开销和冲突率的仿真结果。曲线“NC”表示NCR协议的仿真结果，曲线“Flooding”表示泛洪协议的仿真结果。

图4是数据包投递率的仿真结果，可以看出NCR协议投递率一直高于泛洪协议，大约提高了20%~50%，投递率随发送因子的增长快速增长，且在发送因子较小时就可以得到很高的数据包投递率，图5是数据包投递平均时延的仿真结果。

图4　数据包投递率　　　图5　数据包投递平均时延　仿真结果　仿真结果

从图5可以看出NCR协议传输时延远低于泛洪协议，随着发送因子的增长时延相对平稳，没有明显增加。因此在节点数量较多的网络中，NCR协议能够显著提高数据包传输率，从而降低传输时延。

图6是协议开销的仿真结果，可以看出，在相同发送因子的条件下NCR协议开销始终比泛洪协议的协议开销大。主要原因是节点对数据包编码后，将每个数据包的编码向量作为头部信息添加到数据头部，从而有大量携带编码向量的数据包进行转发，使协议开销相对增大；而泛洪协议的网络开销主要是大量重复数据包发送造成的。

图7是数据包冲突率的仿真结果，可以看出，在节点数为50的随机网络拓扑结构中，接收到的数据包数量较小时NCR协议和泛洪协议的冲突率相当；但当网络节点传输数据增大时，NCR协议的冲突率明显低于泛洪协议。因此，NCR协议通过数据包编码，提高了数据包转发机会，减少了数据包碰撞，降低了冲突率，有效降低了数据丢包，具有较高的可靠性。

图6　协议开销仿真结果　　图7　冲突率仿真结果

3结束语

将随机网络编码方法应用于节点广播数据包中，采用NS-2仿真工具模拟仿真了水声网络环境中随机拓扑结构中的对NCR协议网络数据传输。在节点数量为50的随机网络拓扑结构中，与传统的泛洪协议相比，NCR协议的数据包投递率大约提高了20%~50%，时延降低了大约50%~60%，同时数据包的冲突率也减小。网络编码方法使网络性能获得改善。

仿真结果表明，NCR协议比传统泛洪方法，明显提升了数据包投递率，减小了投递平均时延，降低数据包的冲突率，从而提高了传输可靠性以及传输效率，虽然在协议开销方面有所增加，但提高了数据传输效率，减小了数据包发生冲突的可能性，总体网络性能获得明显改善。

参考文献

[1]Yang Xiao.水下声传感器网络[M].北京：国防工业出版社，2012:1-3.

[2]郭忠文，罗汉江，洪 锋，等.水下无线传感器网络的研究进展[J].计算机研究与进展，2010：377-389.

[3]郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].北京：人民邮电出版社，2002：20-30.

[4]卢开澄，卢华明.图论及其应用(第2版)[M].北京：清华大学出版社，1995.

[5]Ahlswede R， Cai N，Li S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000：1204-1216.

[6]Lucani D E，Milica Stojanovic.Underwater Acoustic Networks :Channel Models and Network Coding based Lower Bound to Transmission Power for Multicast[J].IEEE Journal of Selected Areas in Communications，2008,26(9):1708 - 1719，December.

[7]徐明.水声传感器网中基于网络编码的多径路由协议[J].传感器与微系统,2013,32(1)：58-61.

[8]徐明，刘广钟.三维水声传感器网络中基于网络编码的地理位置路由协议[J].传感技术学报,2012,25(11):45-48.

[9]Guo Zheng，Wang Bing，Xie Peng，et al.Efficient Error Recovery with Network Coding in Underwater Sensor Networks [J].Ad Hoc Networks，2009，7(4):791-802.

[10]樊昌信.通信原理[M].北京：国防工业出版社，2006.

[11]柯志亨，程荣祥，邓德隽. NS2仿真实验-多媒体和无线网络通信[M].北京：电子工业出版社，2009.

[12]刘磊，李 宇，张春华，等.水声通信网竞争式介质访问控制协议的研究[J].应用声学,2014,33(3):19-22.

[13]黄佳庆，Li Zong-peng.网络编码原理[M].北京：国防工业出版社,2012.

[14]Neubauer A，Freudenberger J，Kuhn V.编码理论——算法、结构和应用[M].北京：人民邮电出版社，2009.

[15]Katti S，Rahul H S，Hu Wen-jun，et al.XORs in the Air: Practical Wireless Network Coding[J].IEEE/ACM Transactions on Networking，2008: 497-510.

[16]Fasolo E，Rossi M，Widmer J，et al.On MAC Scheduling and Packet Combination Strategies for Practical Random Network Coding，In Communications[C]∥ ICC’07.IEEE international conference on，IEEE，2007：3582-3589.

Research on Routing Protocol of Underwater Acoustic Network
Based on Network Coding Technique

ZHU Lin，JIANG Zhi-hao，LI Xun

(Unit 91635，PLA，Beijing 102249,China)

Abstract：Duo to some disadvantages of underwater acoustical communication，such as low transmission speed，long delay and etc.，this paper proposes a random network coding technique in underwater acoustical environment，and simulate NCR(Network Coding Routing) protocol with NS-2.The results show that not only the packet delivery ratio is increased by 20% through 50%，but also the packet delivery average delay is reduced by 50% through 60%.The network performance has been improved.

Key words：underwater acoustic communication；network coding；protocol；delivery ratio

作者简介：祝琳(1987—)，女，助理工程师，主要研究方向：通信工程。江志浩(1981—)，男，工程师，主要研究方向：无线电通信。

收稿日期：2015-07-16

中图分类号：TN929.3

文献标识码：A

文章编号：1003-3114(2016)01-24-4

doi:10.3969/j.issn.1003-3114.2016.01.06

引用格式：祝琳,江志浩，李迅.基于网络编码技术的水声网络路由协议研究[J].无线电通信技术,2016,42(1):24-27.