基于高度包保护的优化融合编码算法

赵旦峰，文杰，伦贵阳

(哈尔滨工程大学 信息与通信工程学院, 黑龙江 哈尔滨 150001)

基于高度包保护的优化融合编码算法

赵旦峰，文杰，伦贵阳

(哈尔滨工程大学 信息与通信工程学院, 黑龙江 哈尔滨 150001)

为了提升水声网络中现有的基于喷泉码与网络编码融合传输方案的性能，减少LT编码包经过中继节点网络编码后度分布的变化，本文提出一种基于高度包保护的优化融合编码算法(LTNC- HP)。LTNC- HP算法通过在各个中继节点增加高度保护传输算法，解决融合编码时存在的不理想覆盖问题，有效减少了传输的信息量。同时LTNC- HP算法在中继节点编码时加入同度包优先选择机制，提高各个中继节点编码信息的有效性，增加了网络中数据包的多样性。仿真结果表明，与改进前的融合编码方案相比，LTNC- HP算法传输信息的有效性显著提高，且传输冗余大幅度降低。

水声网络； 喷泉码； 网络编码； 高度包保护传输； 同度包优先选择； 编码融合

Abstract：LTNC- HP, a novel optimized recoding algorithm for the protection of high- degree packets in underwater acoustic sensor networks, is proposed. The proposed algorithm improves the performance of a data transmission scheme and is based on the combination of LT codes with network coding. Moreover, the algorithm decreases the variation in the degree distribution of LT coding packets after passing the network coding at the relay point. By introducing a high- degree protection transmission algorithm at each intermediate node, the proposed algorithm can resolve the imperfect coverage of the input symbols and decrease the amount of data transmission. Moreover, the priority selection mechanism for the same degree packet is added in LTNC- HP when coding at each relay node, significantly improving the efficiency of coding information at each relay node and increasing the diversity of the data packets in the network. Simulation results showed that compared with existing encoding algorithms, LTNC- HP improves the effectiveness of the information transmission and decreases transmission redundancy.

Keywords：underwater acoustic network; LT code; network coding; protective transmission for high degree packets; priority selection mechanism of unison packets; coding fusion

随着科技的快速发展，水声通信正在迅速成长为一个具有广泛的商业应用前景和军事应用前景的领域。然而水声传感器网络(underwater acoustic sensor networks, UASNs)[1]因其存在窄带、时变、长延时、能源供给受限等恶劣的通信条件，使得水声传感器网络在应用时面临巨大的挑战[2-4]。喷泉码[5]和网络编码[6]都被认为是有助于提高水声通信网络鲁棒性的信道编码技术。喷泉码凭借其独特的编码无速率特点，对于水声通信环境表现出良好的适应性，但其应用于多跳通信网络中时，采用数据包逐跳解码转发的方式不可避免的增加了整个网络的传输延时[7]，并且带来其他潜在的因素。同时网络编码因其较高的编译码运算复杂度[8]，使得其在应用时也受到了一定的限制。研究表明，结合喷泉码和网络编码技术可以弥补两种编码技术各自的缺陷，大幅度提升网络传输性能。

为了减少传输延迟，最初喷泉码在多跳中继传输网络中采用中继转发的模式，该方案在各个节点不存在编码开销，但是在恶劣的信道条件下将造成大量的信息重传和能量消耗。Khaldoun Al Agha等首次提出了一种基于指数分布的喷泉码与网络编码融合编码传输的方案，算法的核心在于中继节点先通过简单的网络编码运算降低高度LT编码包的度数，然后按照指数分布生成度值完成中继节点的异或网络编码[9]。然而该方案因受到度分布概率函数的限制，无法充分利用网络编码的优势来增大网络传输的效率，使其在应用中具有一定的局限性。Anya Apavatjrut等提出了LT自适应融合编码(LT- adapted xor with network coding, XLT)算法，XLT算法利用节点的空闲时隙引入了低度包保护传输方法和异或网络编码算法，提高了低度编码包在各个中继节点编码包中所占的比例，增加了网络中数据包的多样性[10]。但是XLT算法采用了时分复用的通信方式，在进行网络编码时只能使用当前时刻缓存序列中的编码包，使其编码包多样性受到了一定的限制。在恶劣的信道条件下，缓存序列中编码包的局限性将可能导致大量冗余信息的传输，引起大量的能量消耗。随后，文献[11]提出了基于LT码和随机线性网络编码(random linear network coding, RLNC)的融合编码算法，算法的核心思想是利用LT码和RLNC分别实现在时域编码和空间域编码，以此提高数据传输的可靠性。这种乘积型融合编码算法，虽然通过RLNC来增加各个中继节点编码包的信息多样性，可以保证信息的有效传输，但是其在译码时需要先进行网络编码包的高斯消元译码[12]恢复出LT编码包，然后再进行BP译码[13]。在恶劣的通信环境下，这种方案将需要大量的传输冗余才能完成数据恢复，同时也将带来较大的译码延时和运算复杂度，不适用于能量和带宽受限的水声通信环境。

为此，本文提出一种基于高度包保护传输策略的优化融合编码算法(the combination of LT code and network coding for the protection of high- degree packets,LTNC- HP)，通过引入高度包保护(the protection of high degree packets,HP)算法和同度包优先选择机制实现水声传感器网络中低冗余数据可靠传输。

1 喷泉码与网络编码的融合分析

从本质上来看，喷泉码与网络编码的融合过程中存在的主要问题是经过网络编码后生成的新的编码包度分布相比原始LT编码包的度分布情况发生了显著的变化。为了进一步分析度分布的变化情况，图1展示了理想条件下在喷泉码与网络编码的直接融合方案中，LT编码包经过5跳中继节点的再编码处理后度分布的变化情况，这里的直接融合即中继节点直接对于LT码字进行伽罗华域的异或网络编码运算，不进行任何的特殊处理，其中信源的输入符号数K=100，0跳代表原始RSD分布图。从图中可以看出，融合编码后度分布的变化主要表现为两个方面：1)经过5跳中继节点的网络编码处理后，度数为1的数据包已经全部消失，这必将造成接收端因缺少度数为1的数据包而无法开始译码；2)相比原始的度分布，第5跳中继节点生成的编码包对于原始输入符号的覆盖度(这里编码包度分布中最高度数值代表了对于输入符号的覆盖程度，在图1中用竖直线标出)大幅度下降，覆盖度的降低将直接导致大量数据包的重传和冗余信息的发送。上述分析可知单纯的直接融合编码方案是可不行的。

图1 度分布变化情况Fig.1 The situation of degree distribution

众所周知，保证到达接收端的编码包集合中存在度数为1是译码开始的充分条件，而确保可译码集合对于输入符号的覆盖度是保证译码持续进行的必要条件。在XLT算法中已经给出了保证低度编码包存在的解决方法，因此如何提高接收端的可译码集合对于输入符号的覆盖度是本文研究的重点。

研究发现，中继节点执行异或网络编码时关于编码符号的选择是影响覆盖度的主要步骤。中继节点进行编码符号的选择时主要存在两个问题：1)选取编码符号的方式。现有的融合算法中，中继节点都是采用随机的方式选择编码包进行异或网络编码，然而无规律地随机选择编码包进行再编码将高概率地造成信息的冗余编码，使得译码端获取的有效信息量减少，增加了译码过程的复杂度。因此，找到一个最佳的选择方式是提高编码信息有效性的一个直接思路。2)异或网络编码时存在度碰撞(degree collision, DC)。DC就是指利用LT编码包进行异或网络编码时可能出现生成的编码包的度数不等于所有参与编码的数据包度数之和的现象，例如：(x1⊕x2)⊕(x3⊕x2)的度数是2而不是4。由于再编码时DC现象的存在，导致高度编码包(d>K/2)将很难通过中继节点的网络编码运算生成，进而造成各个中继节点对于输入符号覆盖度的降低。 由于DC问题是无法避免的，因此在中继节点执行编码处理时考虑保护原有高度数编码包(d>K/2)的传输是解决可译码集合不理想覆盖问题的一个解决办法。

2 LTNC- HP算法的设计

LTNC- HP算法主要包含两个阶段的设计，一是在编码前的阶段引入高度包保护传输算法，保证各个中继节点对于输入编码符号的覆盖度；二是在编码阶段引入同度包优先选择机制，提高各个中继节点编码信息的有效性。

2.1 高度保护传输算法

高度包保护传输(HP)是在中继节点编码前完成的。中继节点在完成接收工作后，首先统计缓存序列中高度值编码包(d>K/2)的个数，如果个数不为0，则将数据包放入高度编码包集合SH中；否则，将直接进入异或网络编码阶段。算法的具体步骤如下：

1)初始化。节点编码次数N、高度数编码包个数NH、高度编码包集合{SH}，本节点新编码包集合S′;

2)统计缓存序列中高度编码高的个数，记为NH，并将满足条件的编码包存入集合SH；

3)如果SH≠∅，将SH集合中数据包全部转存至集合S′中；否则执行步骤5；

4)更新节点的编码次数N=N-NH；

5)结束。

在添加了HP算法的融合编码方案中，所有参与传输的中继节点都将对于接收的高度数编码进行保护传输，间接避免了中继节点再编码时因DC问题无法生成高度包的情形，同时也将提高各个节点对于原始输入符号的覆盖度，减少信息重传的次数，进而减少冗余信息传输带来的延时问题。

2.2 同度包优先选择机制

传统的编码符号随机选择方式所造成的编码包重复选择是无规律且不可控制的。图2为某节点缓存序列中27个度数为2的编码包通过随机选择方式各自在本节点网络编码操作中出现的次数。从图2可以看出，编码符号的随机选择造成了同度编码包不均匀地参加本节点网络编码操作。这种选取的不均匀性将导致编码信息重复的可能性增大，使得对于原始输入符号的覆盖度降低。针对存在的不均匀选择问题，提出了同度包优先选择机制。

同度包优先选择机制(priority selection mechanism for the same degree packets, PSM)是指每个中继节点进行异或网络编码时，标记每个编码包参与本节点异或网络编码的次数，在面对多个同度数编码包是否参与编码的选择时，选取在当前时刻参与本节点编码操作最少的编码包进行编码，避免了不均匀选择的问题。这样在整体的编码操作中，所有同度数的编码包参与编码的次数大致上将是相同的。PSM机制通过避免重复无意义的编码操作来提高编码信息的有效性，避免了冗余信息的传输。

图2 度为2的编码包出现次数Fig.2 Occurrences of coded packets with the degree of 2

2.3 LTNC- HP优化融合编码方案

在前面的内容中介绍了HP算法和PSM机制，本节将对基于高度包保护的优化融合编码方案LTNC- HP的整体流程进行详细阐述：

假设信源数据块由K个输入符号构成，各个节点将按照预设的RSD分布进行编码，且编码在伽罗华域GF(2)进行。

中继节点首先进行数据初始化，初始化完成后进入分阶段处理：第一阶段，执行HP算法，前面的内容已经叙述过算法的原理，这里将不再赘述；完成高度保护传输后，进入第二阶段，执行异或网络编码运算，具体的编码过程如下：

1)结合RSD分布和约束条件生成度值d。中继节点进行异或网络编码时，参与编码的数据包不仅仅包括度值为1的原输入符号而且包含上一跳节点生成的编码包，这样在度d的选择上必须要通过约束条件判断d是否可达，约束条件如下

(1)

d

(2)

式中：n(i)是指节点缓存中包含的度数为i的数据包个数，upper_bound是代表节点缓存序列中包含源输入符号的个数。如果d不满足其中的任何一个约束条件，则按照RSD分布重新生成d，直至找到满足条件的d，方可执行下一步。

2)编码符号的选择。根据生成的度值d，节点首先利用PSM机制选出满足条件的数据包，如果当前已经参与编码的数据包个数大于1，则需要通过异或运算来判断是否存在DC问题。如果存在DC，则重新使用PSM机制进行筛选，直至找到满足条件的编码包；如果判断不存在DC问题，则执行异或网络编码运算。

3)重复步骤2，生成预设数目的数据包后，将全部的编码数据包传输至下一跳中继节点。

那么，LTNC- HP算法的流程图如下。

图3 LTNC- HP算法流程图Fig.3 The flow chart of LTNC- HP

LTNC- HP算法通过引入高度包保护传输(HP)算法，提高了各个中继节点编码后对于原始输入符号的覆盖度，减少了信息重传的次数；同时，在编码时加入同度优先选择机制(PCM)弥补了传统随机选择编码的不可控性和随机性，再次减少了冗余信息的传输，使得整个系统的传输延迟性能得到改善。

3 算法仿真与分析

本文基于OPNET仿真平台搭建一个简单的线性网络模型对于LTNC- HP算法进行验证。仿真实验分别从度分布情况、传输跳数的影响及信道条件的影响3方面进行，以平均传输冗余Overhead为衡量指标将LTNC- HP与传统多种融合算法进行仿真比较。平均传输冗余用来描述传输方案的编码效率，冗余越低，说明传输方案的传输效率越高。那么平均传输冗余Overhead的计算表达式如下

(3)

式中：pk_numi代表第i跳节点发送的编码包数，h为传输跳数。

仿真参数设置如下：信源输入符号数K=100；各个节点的编码冗余均设为1.2；RSD度分布表达式如下

(4)

(5)

其中

(6)

式中：c=0.03，δ=0.5；选用BP算法进行译码；反馈确认ACK信号在接收端完成全部数据恢复后由译码节点发出，且假设反馈信道中无信息丢失。

3.1 度分布情况

假设信道丢包率为0.5，传输跳数为6跳，分别对于采用XLT算法和LTNC- HP算法的方案中第5跳中继节点编码前后的度分布情况进行仿真分析。

图4和图5分别为XLT算法和LTNC- HP算法编码前后度分布对比图，图4和图5中已经将最高度数值即代表对于输入符号的覆盖度用竖直虚线标注。从图4中可以看出，中继节点采用XLT算法进行异或网络编码时，虽然编码后中低度包所占的比例显著提升，但是大部分其他度值的编码包已经消失，并且编码后新的编码包的度分布和 RSD分布的结构有很大区别。同时值得注意的是，高度数编码包在连续5跳节点的编码处理后也已经全部消失，这将不可避免的导致到达第6跳译码节点的编码包对于输入符号的覆盖度大幅度降低，进而造成译码过程的中断。相比较之下，图5给出的采用LTNC- HP算法编码纠正后的度分布基本保留了RSD原始度分布的形状，同时也实现了对于高度编码包的保护传输，对于输入符号的覆盖度基本保持不变，这将有利于译码过程的顺利进行，减少不必要的冗余重传。

图4 XLT算法度分布Fig.4 The degree distribution of XLT

图5 LTNC- HP算法度分布Fig.5 The degree distribution of LTNC- HP

3.2 传输跳数

为了验证高度包保护传输算法对于融合编码传输方案的影响，图6展示了丢包率为0.5时，增加HP算法和无保护方案在不同网络传输跳数的条件下，平均传输冗余性能的比较情况。从图中可以看出，引入了HP算法的传输方案，平均传输冗余明显少于传统无高度保护的传输方案，并且随着网络中传输跳数的增加，性能提升的幅度逐渐增大。当传输跳数达到6时，引入HP算法的传输方案性能提升最大，与无保护的传输方案相比平均传输冗余下降了2.0，这对于能源有限的水声通信系统是十分有利的。上述仿真证明，在中继节点编码时引入HP算法可以用来抵抗在恶劣水声信道进行通信时，编码信息传输有效性降低的情况。

图6 高度保护传输(HP)对传输冗余的影响Fig.6 The influence of HP on the transmission redundancy

进一步验证LTNC- HP算法的性能，假设信道丢包率为0.5。图7展示了中继节点分别采用Passive Relay算法、XLT算法及LTNC- HP算法进行处理时，平均传输冗余随传输跳数变化的曲线对比图。如图所示，随着传输跳数的增加，三种方案的平均传输冗余均呈现逐渐上升的趋势，但其上升的速率有明显的差异。三种方案的平均传输冗余性能符合LTNC- HP算法最优、XLT算法次之、Passive Relay算法最差的规律。仿真结果也同时验证了随着网络传输跳数的增加，LTNC- HP算法的性能优势更加明显。

图7 三种方案平均传输冗余随跳数变化Fig.7 Average transmission redundancy under different transmission schemes varied with Hop

3.3 信道条件

固定传输跳数为6跳，本文以信道丢包率来描述水声传感器网络中信道条件的变化。图8以丢包率为变量，比较了三种算法的平均传输冗余性能。通过仿真结果可以发现，随着丢包率的逐渐增大，三种方案的平均传输冗余均表现出上升的趋势。在信道条件较好丢包率较小的条件下，即丢包率小于0.11时，三种算法的性能基本相同；在丢包率大于0.11时，XLT算法和LTNC- HP算法相比Passive Relay算法逐渐表现出优势；随着信道条件继续变差，XLT算法的平均传输冗余上升速度明显高于LTNC- HP算法，可以证明XLT算法的优势在恶劣的信道条件下逐渐降低，然而LTNC- HP算法的优越性更加凸显的表现出来。这是因为LTNC- HP算法在各个中继节点编码效率更加有效，同时提高了对于输入符号的覆盖度，在恶劣的信道条件下，接收端可以实现以更少的编码包即可完成译码，即实现以低冗余完成数据传输。

图8 不同信道条件下平均传输冗余性能Fig.8 Average transmission redundancy under different transmission schemes varied with Packet Loss Rate

4 结论

1)LTNC- HP算法使得中继节点融合编码后的度分布接近于RSD度分布。

2)高度包保护方案相对于非保护方案可明显减少数据包的传输冗余。

3)与Passive Relay算法、XLT算法相比，LTNC- HP算法可显著降低数据包的传输冗余，有效地提高节点的能量效率。

LTNC- HP算法为网络编码与喷泉码的编码融合传输提供了参考，后续的研究中将探讨如何把融合算法扩展用于典型网络中。

[1] GAO Xiujing, ZHANG Feifei, ITO M. Underwater acoustic positioning system based on propagation loss and sensor network[C]//Processing of OCEANS 2012, Yeosu, 2012: 1-4.

[2] 赵旦峰,梁明珅,段晋珏. 水声网络中喷泉码的应用研究现状与发展前景[J]. 系统工程与电子技术, 2014,36(9): 1838-1843.

ZHAO Danfeng, LIANG Mingshen, DUAN Jinjue. Survey of fountain codes in underwater acoustic sensor networks[J]. Systems engineering and electronics, 2014, 36(9): 1838-1843.

[3] CAI Shaobin, GAO Zhenguo, YANG Desen, et al. A network coding based protocol for reliable data transfer in underwater acoustic sensor[J]. Ad Hoc networks, 2013, 11(5): 1603-1609.

[4] OTNES R, ASTERJADHI A, CASARI P, et al. Underwater acoustic networking techniques[M]. Berlin: Springer, 2012: 19-81.

[5] CASTURA J, MAO Y. Rateless coding over fading channels[J]. IEEE communications letters, 2012, 10(1): 46-48.

[6] WU Huayang, CHEN Min, GUAN Xin. A network coding based routing protocol for underwater sensor networks[J]. Sensors, 2012, 12(4): 4559-4577.

[7] CASTURA J, MAO Yongyi. Rateless coding for wireless relay channels[J]. IEEE trans wireless commun,2007，6(5):1638-1642.

[8] CUI Tao, CHEN Lijun, HO T. Energy efficient opportunistic network coding for wireless networks[C]. INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008: 361-365.

[9] AI A K, KADI N, STOJMENOVIC I. Fountain code with XOR of encoded packets for broadcasting and source independent backbone in multi- hop networks using network coding[C]//Vehicular Technology Conference, VTC-2009, Barcelona, Spain, 2009.

[10] APAVATJRUT A, GOURSAUD C, JAFFRES R K, et al. Toward increasing packet diversity for relaying LT fountain codes in wireless sensor networks[J]. Communications letters, IEEE, 2011, 15(1):52-54.

[11] BASSOLI R, TALOOKI V N, MARQUES H, et al. Product network codes for reliable communications in diamond networks[M]∥Wireless Internet. 2014,146: 85-90

[12] NOURA H, MARTIN S, AGHA K A, et al. ERSS- RLNC: Efficient and robust secure scheme for random linear network coding[J]. Computer networks, 2014, 75: 99-112.

[13] 李璐颖，吴湛击. 喷泉码编译码原理研究和分析 [J].中国新通信， 2010， 4(7)： 41-46. LI Luying, WU Zhanji. Code research and analysis on fountain codes[J].China new telecommunications, 2010， 4(7)： 41-45.

ThealgorithmbasedonthecombinationofLTcodeandnetworkcodingfortheprotectionofhigh-degreepackets

ZHAO Danfeng, WEN Jie, LUN Guiyang

(College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)

10.11990/jheu.201607030

http://www.cnki.net/kcms/detail/23.1390.u.20170427.1328.022.html

TN929.3

A

1006- 7043(2017)09- 1491- 06

2016-07-11. < class="emphasis_bold">网络出版日期

日期：2017-04-27.

国家自然科学基金项目(61371099).

赵旦峰(1961-), 男, 教授,博士生导师； 文杰(1991-)，女，硕士研究生.

文杰,E- mail：wenjie_wsq@126.com.

本文引用格式：赵旦峰，文杰，伦贵阳. 基于高度包保护的优化融合编码算法的设计[J]. 哈尔滨工程大学学报， 2017， 38(9): 1491-1496.

ZHAO Danfeng, WEN Jie, LUN Guiyang. Optimized algorithm based on the combination of LT code and network coding for the protection of high- degree packets[J]. Journal of Harbin Engineering University， 2017， 38(9): 1491-1496.