基于优化Raptor码的水下传感器网络可靠传输机制

2017-11-01柳秀秀杜秀娟

重庆邮电大学学报(自然科学版) 2017年5期

关键词：编解码孤子解码

柳秀秀，杜秀娟

(1.青海师范大学计算机学院，西宁 810008； 2.青海省物联网重点实验室，西宁 810008)

基于优化Raptor码的水下传感器网络可靠传输机制

柳秀秀1，2，杜秀娟1，2

(1.青海师范大学计算机学院，西宁 810008； 2.青海省物联网重点实验室，西宁 810008)

针对水声通信带宽低、时延长、误码率高、多普勒效应显著等特征，分析了传统可靠传输机制在水下传感器网络应用的局限性，提出了基于数字喷泉码-优化Raptor码的水下传感器网络可靠传输机制。采用反馈控制对Raptor码内码的鲁棒孤子分布和多项式描述的Shokrollahi度分布进行优化设计，降低了编码包平均度。进一步对Raptor码的内码—弱化的LT码(Luby transform codes)的编解码进行优化，实现了快速的编解码。基于优化Raptor码的可靠传输机制采用反馈控制，动态评估信道删除概率，从而提高编解码和通信效率。通过Aqua-Sim仿真工具对提出的可靠传输机制与基于编码的多跳协同可靠数据传输(coding based multi-hop coordinated reliable data transfer，CCRDT)机制进行仿真对比。结果表明，所提出的可靠传输机制明显降低了传输开销，提高了数据吞吐量。

水下传感器网络；可靠传输机制；Raptor码；反馈控制

0 引言

当前，在海洋环境监测、海洋资源勘探、军事反潜入侵检测等方面有着广泛应用前景的水下传感器网络(underwater sensor network，UWSN)已逐渐成为各国学者研究的热点。UWSN节点部署在复杂多变的水下环境中，由于水的吸收作用，电光信号在水下衰减严重，其中典型衰减值为40 dB/km。实验表明，遵循IEEE 802.15.4( 868 MHz，915 MHz，2.4 GHz)或IEEE 802.11b/g(2.4 GHz)协议的水下节点发送的电光信号传输距离一般为[1-5]50～100 cm。由此可见，电光信号在水中的传播距离极为有限，无法有效地工作于水下。因此，UWSN采用损耗较小和传播距离较远的声波通信。

声信号在UWSN中传播速度为1 500 m/s，比电光信号传播速率低5个量级，导致声信号在UWSN中传播延迟很大。相对于电光信号微秒级传播时延，声波的传播时延达到0.67 s/km。声波在UWSN的通信误码率较高，通常在[1-3]10-7～10-3，这给UWSN协议的设计带来很大的挑战。针对水声通信的带宽低、时延长、误码率高、多普勒效应显著、多径干扰严重和节点随水流移动等特点[1-5]，本文提出了基于优化Raptor码的水下传感器网络可靠传输机制。

1 相关工作

迄今为止，多数访问控制协议采用请求发送/清除发送协议(request to send/clear to send，RTS/CTS)握手机制来避免收发产生的冲突，但UWSN生成数据的速率为1～5 bit/s，数据包长度一般为[6]100 Byte，而RTS/CTS包长为几十个字节。因此，与数据包相比，RTS/CTS帧长并不是很短，采用RTS/CTS握手机制带来的收益并不显著。相反，考虑到水声信道窄带宽、长延时等特点，RTS/CTS握手机制降低了信道利用率、网络吞吐量，延长了端到端延迟。

由于水声Modem采用半双工通信，故UWSN网络传输控制机制应避免发送-接收干扰。文献[7]采用增加限定条件ΔT时间间隔的方式来避免收发冲突，但由于UWSN网络传输时延长，增加限定条件ΔT时间间隔导致了传输时延过长。文献[8]提出了采用自动重传请求(automatic repeat request，ARQ)和前向纠错(forward error correction，FEC)相结合的分段数据可靠传输协议(segmented data reliable transport，SDRT)，SDRT协议是逐块的、逐跳的可靠传输协议。SDRT协议通过预期所需数据包数量设置适当长度的数据块，来减少发送数据包的数量，但发送节点以非常缓慢的速率发送窗口外的数据包，降低了信道利用率。

文献[9]提出了基于编码实用的多跳可靠数据传输协议(practical coding based multi-hop reliable data transfer，PCMRDT)。该协议提出了一个可避免发送和接收冲突的方案，从整体上降低了端到端延时。文献[10]提出了基于GF(256)随机线性编码的多跳协调协议，保证了UWSN的传输可靠性。该协议通过编码率估计方法和合适调度算法有效消除了数据包之间的冲突，进一步提高了端到端吞吐量。由于水下节点随水流移动，若传输时延过长，可能导致连续传输数据包间断。

文献[11]研究了无线传感器网络中基于Raptor码的数据传输技术，该技术可以提高数据传输的可靠性和传输效率。文献[12]提出了基于递归LT码(recursive LT，RLT)的水下传感器网络逐跳可靠传输机制。该机制减小了包冲突和端到端的延时，提高了网络吞吐量和信道利用率。

数字喷泉码是基于二部图的高性能稀疏无码率编码，传输的冗余量不是固定常数，且能够随着错误恢复算法的执行而动态确定，是一种轻量级的编解码实现，适用于时空变的水下传感器网络。典型的数字喷泉码有LT码和Raptor码2种[13-15]。由于节点的移动性，水下网络相邻节点之间的传输时间极其有限，导致节点间传输的数据块只能包含少量数据包。因此，需要进一步对数字喷泉码的度分布和编解码进行优化，研究水声环境下较小数据分块的可靠传输机制。本文提出了基于优化Raptor码的水下传感器网络可靠传输机制，对Raptor码中内码的度分布和编解码进行了优化，信息中增加ID字段和成功接收的数据包数量，用于指明目前已恢复的原始包和评估信道包错误率，发送节点进一步根据反馈信息确定哪些原始包再次编码和调节发送窗口大小，从而提高编解码和通信效率。

2 Raptor码

1998年，M.Luby等[13-15]提出了数字喷泉码。数字喷泉码是一种基于二部图的高性能稀疏码，其由固定数量的原始包生成和发送无限多个编码包的方式可以形象地描述为喷泉。发送方将这些编码包像喷泉一样源源不断地发送出去，接收方只要能够接收足够多的编码包，就能成功解码，恢复全部的原始数据包。通常假设，发送方有k个原始包，经数字喷泉码编码产生n(n是无限的)个编码包，接收方只要收到任意k′(k′≥k)个编码包，就可以进行解码。边接收边解码，直到解码成功，数字喷泉码的开销为o=k′-k。其中，ε是解码开销，定义为ε=k′/k-1，也即k′=k(1+ε)[13-16]。2002年，Luby提出了第一类实用型数字喷泉码—LT码。之后，在LT码的基础上，Shokrollahi提出了另外一类性能更佳的数字喷泉码—Raptor码。LT码和Raptor码性能比较如表1所示。

表1 LT码和Raptor码性能比较

2.1Raptor码度分布

Raptor码包括预编码和弱化的LT编码2个部分，k个原始包经预编码后，产生K个中间数据包，K个中间数据包再经弱化的LT编码。Raptor码的度分布主要是内码度分布，内码是弱化的LT码，其解码成功的关键是合理的度分布。原有内码度分布有函数表示的鲁棒孤子分布和多项式描述的Shokrollahi度分布两类。

1)鲁棒孤子分布。鲁棒孤子分布u(d)由理想孤子分布ρ(d)和正数函数τ(d)运算得来[16]，其中，ρ(d)的表达式为

(1)

τ(d)的表达式为

(2)

(3)

2)Shokrollahi度分布。Shokrollahi度分布[14]表达式中幂代表度，系数代表概率，表达式为

f(x)=0.007 969x+0.493 570x2+0.166 220x3+

0.072 646x4+0.082 558x5+0.056 058x8+

0.037 229x9+0.055 590x19+

0.025 023x65+0.003 137x66

(4)

2.2Raptor码编解码过程

Raptor码编解码过程包括预编码和弱化的LT编码2个部分，其中，预编码为外码，弱化的LT编码为内码。预编码对k个原始包使用传统纠删编码方式产生K个中间数据包，K=k/R，R为预编码的码率；弱化的LT编码:将K个中间数据包进行异或运算得到Raptor编码包；编码过程如图1所示，解码是编码的逆过程。Raptor码编码过程中的中间数据包已具有了一定的纠错能力，因此，接收方不需要恢复出所有中间数据包，只需重构出一定量的中间数据包，便可利用外码的纠错特性得到全部的原始数据包[13-18]。

图1 Raptor码的编码过程 Fig.1 Encoding process of raptor code

3 基于优化Raptor码的UWSN网络可靠传输机制

3.1 度分布优化设计

合理的度分布直接决定了编解码性能的好坏，是内码解码成功的关键。较小度的编码包能够减少解码复杂度，度为1的编码包决定了解码能否开始并持续进行。大度的编码包能覆盖较多的原始数据包，增加了重构所有原始包的概率，但是增大了编解码复杂度，且容易出现解码中断。因此，需要对度分布进行优化。

3.1.1 鲁棒孤子分布优化

采用Matlab对鲁棒孤子分布进行仿真，参数c=0.2，δ=0.5，K=500，仿真结果如图2所示。编码包度的概率随着度值增大而逐渐减小，当度值较大时，概率均很小，但度值较大的包增加了编解码复杂度，因此，编码包度值适中才能在保证解码成功的条件下，解码复杂度和开销较为合理。

图2 鲁棒孤子分布Fig.2 Robust soliton distribution

鉴于此因素本文对鲁棒孤子分布进行优化，其最大度由原始数据包数量K改为较小值D[18]，D≤K,则优化的鲁棒孤子分布表示为u′(d)，其中，s，c和δ意义不变，表达式为

(5)

则优化的理想孤子分布ρ′(d)的表达式为

(6)

τ′(d)的表达式分为3种情况，分别如下。

(7)

(8)

(9)

图3显示了优化的鲁棒孤子分布情况。优化的鲁棒孤子度分布u′(d)的度值更改为不固定D值，增加了小于D的度值编码包概率。当K=500时，u(d)的平均度为lnK=6.21，而u′(d)的度D取值不同时，平均度不一样，通过计算D=25时，平均度为3.93。

图3 优化的鲁棒孤子分布Fig.3 Robust soliton distribution by optimized

3.1.2 优化Shokrollahi度分布

虽然Shokrollahi度分布的最大度远小于K，且平均度是与K无关的常量，小于鲁棒孤子分布的平均度lnK[14]。Shokrollahi度分布是理想孤子分布与鲁棒分布的一个折中，是编码包复杂度和解码效率的平衡。采用Matlab对Shokrollahi度分布进行仿真，仿真结果如图4所示，度值分布不均匀，最大度值较大，容易导致解码中断。

图4 Shokrollahi度分布Fig.4 Shokrollahi degree distribution

鉴于以上原因，对Shokrollahi度分布进行优化，度值的概率进行调整，且最大值由固定值66改为可变值v+1，表达式为

f′(x)=0.007 969x+0.493 570x2+0.166 220x3+

0.072 646x4+0.082 558x5+0.056 058x8+

0.037 229x9+0.055 590x19+0.025 023xv+

0.003 137xv+1

(8)

f′(x)的度分布的平均度为

0.072 646×4+0.082 558×5+0.056 058×8+

0.037 229×9+0.055 590×19+

0.025 023×v+0.003 137×(v+1)=

0.028 16v+4.040 015

(9)

图5 优化的Shokrollahi度分布结构图Fig.5 Shokrollahi degree distribution by optimized

表2给出K=500时，分别采用上述4种度分布编码时的平均度。不难看出，优化的鲁棒孤子分布和Shokrollahi度分布的平均度均比优化前的平均度小。当优化后的最大度均为25时，优化鲁棒孤子分布u′(d)的平均度较小，但其度为1的编码包数量仅只有1个，由于UWSN网络误码率较高，度为1的编码包出错时，容易导致解码中断。因此，本文采用f′(x)度分布函数进行编解码。

表2 不同编码的平均度

3.2 优化Raptor码的编解码过程

相较于现有的《RSSP-II安全协议》方案，新方案采用基于简单UDP/IP的《RSSP-I安全协议》处理安全通信，可以有效解决目前互联互通项目中由于车地通信数据包丢失而带来的安全通信问题，也简化了车地安全通信实现互联的复杂度。同时，该方案将伪装防护所需的加密技术部署在成熟的LTE标准设备，这种分布式架构有利于今后不同信号设备厂商之间实现互联，从而形成标准的互联互通车地安全通信系统，也有利于今后加密技术的维护和扩展。

基于以下假设：包的丢失在每一跳是独立的。本文用二部无向图G=(V,E)表示内码-LT码。其中，E为边的集合，V表示节点集合，V=(D∪C)。D为原始包集合，C表示编码包集合。边E连接节点D和C。

3.2.1 优化的LT编码

(10)

(10)式中，BER为误比特率，UWSN网络中BER的取值为10-7～10-3。优化的LT的编码过程如下。

3.2.2 优化的Raptor码内码-LT解码

由于UWSN的误码率较高，导致出错丢包现象较为严重，有可能导致度为1的编码包恰巧不存在。在这种情况下，优化的内码编码方式，当度为1的编码包出错时，也能继续解码。根据编码方式，具体的解码过程如下。

1)找到度为1的编码包C1(C1编码包仅连接一个原始包Di)，令Di=C1，表示编码包C1直接付给第i原始包，即：第i个原始包解码成功。

2)接下来寻找度相差1的2个编码包Cx和Cx+1，度小的编码包Cx里的所有原始数据包同样参与了度较大的编码包Cx+1的异或运算，则通过将这2个编码包进行异或，能解出只参与了大度编码包中的原始数据包Di=Ci⊕Cx+1。比如符合条件的度为2和度为3的编码包，将这2个编码包进行异或运算，解出只存在于度3编码中的原始数据包。

3.3 基于优化Raptor码的UWSN网络可靠传输机制

可靠传输机制离不开反馈控制，本文通过反馈控制对Raptor码度分布进行优化。通过反馈控制可对未成功重构的原始包进行再次编码传输，这样不需要太多大度的编码包，因此，可降低对大度编码包的需求，增加较小度的分布概率；从而减小编译码复杂度[17]。

传统的Raptor码传输过程中，只有当接收节点解码成功时，才会向发送节点反馈信息[3-4]。发送节点在接收反馈信息前，一直处于编码和发送状态，而水声Modem通常工作在半双工模式，接收和发送不能同时执行，因此，处在发送状态的发送节点无法接收反馈信息。为了避免这种收发冲突，发送节点在收到反馈信息之前需要停止发送，并切换到接收状态。因此，本文通过发送窗口和反馈来避免这一问题。

1)首先，发送节点由k个原始包经预编码后，产生K个中间数据包，根据优化的Shokrollahi度分布f′(x)按着优化的LT编码方式对K个中间数据包进行编码，发送KS′个编码包，即KS′=CS1+CS2+CS3+CS4+CS5+CS8+CS9+CS19+CS24+CS25,此时，发送窗口大小为KS′，之后转换到接收状态，等待接收反馈信息。接收节点接收到编码包后，首先按着优化的LT码解码方式进行解码，再进行预编码解码，解码完成后发送反馈信息。

图6 传输过程Fig.6 Transmission process

3.4 仿真结果

本节通过仿真实验对基于优化Raptor码的UWSN网络可靠传输机制进行性能评估。实验通过NS2仿真平台的Aqua-Sim水下传感器网络仿真工具执行。仿真环境依据实际水下情况设置，50多个节点随机部署在3 000 m×3 000 m×3 000 m 的三维区域，仿真参数如表3所示。

表3 仿真参数

本文可靠传输机制与 CCRDT协议[10]在网络吞吐量和开销方面分别进行仿真对比，仿真参数按照CCRDT协议进行设置。节点部署结构采用四跳线型拓扑，设置流量产生器产生数据包的间隔时间服从泊松分布。定义在多跳网络中冗余数据包数与原始数据包数量之比为传输开销。

图7 吞吐量vs.数据包长度Fig.7 Throughput vs. packet length

图8为比特率对端到端吞吐量的影响。在图8中，包的长度设置为100 Byte。图8表明，本文可靠传输机制的吞吐量比CCRDT协议更高。采用优化Raptor编码的可靠传输机制，比完全随机编码的CCRDT协议更为高效，因为减少了重构原始包所需传输的编码包的数量。

图8 吞吐量vs.比特率Fig.8 Throughput vs. bit rate

图9 开销vs.跳数Fig.9 Overhead vs. hop count

4 结束语

本文针对水声通信带宽低、时延长、误码率高、多普勒效应显著、多径干扰严重、节点随水流移动等特点，分析了传统可靠传输机制在水下应用的局限性，提出了基于优化Raptor码的水下传感器网络可靠传输机制，采用Matlab工具对Raptor码中内码的度分布进行仿真并进行优化，根据优化的度分布，对编解码进行了优化设计。该机制采用反馈控制避免收发冲突，减少传输延时。数据包中增加ID字段，标识目前已恢复原始包，发送节点根据已恢复原始包确定编码包，从而提高编解码和通信效率。采用网络仿真软件(network simulator version 2，NS-2)中的Aqua-Sim UWSN网络仿真工具对基于优化Raptor码的UWSN网络可靠传输机制和CCRDT协议进行仿真和对比。结果表明，基于优化Raptor码的UWSN网络可靠传输机制降低了传输开销，提高了数据吞吐量。

[1] RICE J, DALE G. Underwater acoustic communications and networks for the US Navy’s Seaweb program[C]//The 2nd International Conference on Sensor Technologies and Applications. Piscataway, NJ: IEEE, 2008:715-722.

[2] STOJANOVIC M.Optimization of a data link protocol for an underwater acoustic channel[J].Oceans,2005,1(14):68-73.

[3] DU Xiujuan, HUANG Kejun, LIU Fan, et al. Micro-ANP: A Novel Network Protocol Architecture for Underwater Sensor Network[J]. Applied Mechanics and Materials, 2013, 24(5): 223-230.

[4] DU Xiujuan, HUANG Kejun, LAN Shenglin. LB-AGR: Level-Based Adaptive Geo-routing for Underwater Sensor Networks[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(1) :54-59.

[5] IAN F A, DARIO P, TOMMASO M. Underwater acoustic sensor networks: research challenges[J]. Ad Hoc Networks, 2005,3(1):257-279.

[6] 杜秀娟,苏毅珊.水下传感器网络研究[M].北京:科学出版社, 2016:18-24.

DU Xiujuan, SU Yishan. Research about underwater sensor network[M]. Beijing: Science Press, 2016: 18-24.

[7] 柳秀秀,杜秀娟,彭春燕，等.基于数字喷泉码的水下传感器网络可靠传输与分析[J].重庆邮电大学学报：自然科学版, 2014, 26(6): 750-755.

LIU Xiuxiu, DU Xiujuan. PENG Chunyan, et al. Reliable transfer mechanism based on digital fountain codes and performance analysic for underwater sensor networks[J]. Journal of Chongqing University of Post and Telecommunicaations: Natural Science Edition, 2014, 26(6): 750-755.

[8] XIE Peng, CUI Junhong. An fec-based reliable data transport protocol for underwater sensor networks[C]// International Conference on Computer Communications and Networds. Piscataway, NJ: IEEE, 2007: 747-753.

[9] MO H, ZHOU Zhong, Michael Zuba, et al. Practical Coding-based Multi-hop Reliable Data Transfer for Underwater Acoustic Networks[C]// Global Communications Conference. Atlanta: IEEE，2013, 11(18): 5751-5756.

[10] MO H, PENG Zheng, ZHOU Zhong, et al. Coding based Multi-hop Coordinated Reliable Data Transfer for Underwater Acoustic Networks: Design, Implementation and Tests[C]// Globecom Workshops. Atlanta: IEEE, 2013, 12(16): 4566-4571.

[11] PENG X F, YANG Y, YANG C, et al. Research on Data Transmission Technology Based on Raptor Code in Wireless Sensor Networks[J]. Applied Mechanics & Materials, 2013, 442:538-543.

[12] DU Xiujuan, LI Keqin, LIU Xiuxiu, et al. RLT code based handshake-free reliable MAC protocol for underwater sensor networks[J]. Journal of Sensors, 2016, 2016(9): 45-50.

[13] MACKAY DJC. Fountain codes[J]. IEE Communications Proceedings, 2005, 152 (6): 1062-1068.

[14] BA S. Raptor codes[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2551-2567.

[15] LUBY M. LT codes[C]//The 43rd annual IEEE symposium on Foundations of Computer Science. Vancouver: IEEE Press,2002:271-280.

[16] BARRON J, SHAPIRO J. Design of Raptor codes for parallel AWGN channels and slow-fading MIMO channels[C]// Military Communications Conference. San Jose: IEEE,2010, 12(14): 820-825.

[17] HUSSAIN I, XIAO M, RASMUSSEN L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]// Global Telecommunications Conference. Houston: IEEE,2011, 58(11):1-5.

[18] 雷维嘉，张伟，谢显中.单次反馈的Raptor码的内码度分布设计[J]. 重庆邮电大学学报：自然科学版,2014,26(2):228-232.

LEI Weijia, ZHANG Wei, XIE Xianzhong. Design of degree distribution of internal code of Raptor codes with a feedback[J]. Journal of Chongqing University of Post and Telecommunicaations: Natural Science Edition, 2014, 26(2): 228-232.

(编辑：刘勇)

ReliabletransmissionmechanismbasedonoptimizedRaptorcodeforunderwatersensornetwork

LIU Xiuxiu1，2， DU Xiujuan1，2

(1.School of Computer Science, Qinghai Normal University, Xining 810008, P.R. China；2.Key Laboratory of IoT of Qinghai Province, Xining 810008, P.R. Chia)

Underwater acoustic communication is characterized by low bandwidth, long propagation delay, high error probability and Doppler effect. In this paper, we analyze the limitations of traditional reliable transmission applied in underwater sensor network. Based on digital fountain codes-optimized Raptor code, we propose a reliable transmission mechanism for underwater sensor network. We adopts feedback control to optimize the robust soliton distribution and the Shokrollahi degree distribution of polynomial description of Raptor code which reduce the average degree of encoding packet. Further, in this paper, we optimize codec of Raptor code, so a fast encoding and decoding is realized. The reliable transmission mechanism based on optimized Raptor code uses feedback control to dynamically evaluate the erasure probability of channel. So feedback control improves the efficiency of codec and communication. Using the Aqua-Sim simulation tool, we conduct a serial of experiments, and take a comparison between our reliable transmission mechanism and CCRDT. Simulations results show that our reliable transmission mechanism reduces overhead and improves throughput significantly.

underwater sensor network; reliable transmission mechanism; Raptor Code; feedback control

s：The National Natural Science Foundation of China(61162003); The Natural Science Foundation of Qinghai(2015-ZJ-904); The Construction Project of Key lab of IoT of Qinghai (2017-ZJ-Y21); The CERNET Innovation Project(NGII20151101, NGII20160307); The Hebei IoT Data Acquisition and Processing Engineering Center

TP393

1673-825X(2017)05-0696-08