WSN中降低喷泉码存储冗余量的方法研究

袁 博，赵旦峰，钱晋希

(哈尔滨工程大学信息与通信工程学院，哈尔滨 150001)

WSN中降低喷泉码存储冗余量的方法研究

袁 博，赵旦峰，钱晋希

(哈尔滨工程大学信息与通信工程学院，哈尔滨 150001)

针对由于数字喷泉码的冗余编码数据包和所需内存空间较大，导致无线传感器网络(WSN)实时性较差的问题，设计一种平均分帧长LT码的编译码系统。建立典型拓扑结构模型，应用网络编码和数字喷泉码的级联形式进行数据传输，并对平均分帧长LT码的生成矩阵进行压缩编码。通过加权平均法和多比特打包法，在不破坏喷泉码特性的前提下降低无线整个传感器网络的存储冗余量。实验结果表明，该系统能使数字喷泉码降低103量级的存储冗余量，并提高WSN编译码效率及数据中心的数据恢复率。关键词：无线传感器网络；喷泉码；平均分帧长LT码；压缩算法；网络编码；多比特打包

1 概述

数字喷泉码在近几年飞速发展，能够在各种网络通信或者节点通信中充分利用节点之间的互信息，提高信息传输的鲁棒性，接收端在接收到网络编码后的数据时便于进行信息提取，当接收到的数据包数量足够多时，可进行错误恢复，并且其编译码复杂度较低，满足一定条件时可进行线性编译码。无线传感器网络(Wireless Sen sor Net work, WSN)能高效提取及处理信息，并实时监控传输信息数据，在通信领域中具有重要的地位。但是数字喷泉码具有较大的冗余编码数据包，存在一定的译码失败概率，而且其译码算法还有待进一步提高，在WSN中应用时存在延时及占用带宽较大的问题，因此需要改善网络编码及其在WSN中应用时的性能。

本文对LT码的编译码算法进行讨论，研究LT码参数的影响，在WSN中建立平均分帧长LT码的编译码系统模型。将矩阵压缩算法引入平均分帧长LT码的生成矩阵中，对不同的信息帧长做出仿真分析。通过建立系统模型，研究其拓扑结构，并在不同的系统参数及WSN条件下，应用多比特打包法实现信息的小冗余传输。

2 LT码的编译码算法研究

2.1 L T码参数讨论

讨论的参数[1-2]包括：符号节点度为1的平均值S，编码个数K'，度数值d，解码失败概率δ和常数c。分析符号节点度为1的平均值S和编码个数K'的表达式：

其编译码算法是K的线性函数，并希望以少的冗余得到高的译码成功率，在理想条件下，考虑冗余量趋近于0，得出δ的极限值为：

由式(2)、式(3)可以得出：若要使δ＜1，则K＜e，可见，若要增大译码成功率，则要使K尽量小。

根据上述对LT码参数的讨论，建立平均分帧长LT码系统。减少每组的帧长度，尽量减少冗余量，同时提升译码准确性。原始数据平均分帧长编码设计流程如图1所示。通过上述分析可以得出，为实现不同的效果可以采用不同的设计方案，但均能满足系统某一方面的性能要求。

图1 原始数据平均分帧长编码设计流程

2.2 平均分帧长LT码的系统性能参数分析

平均分帧长LT码的系统性能参数包括：平均度数D和编译码复杂度Q。

编译码复杂度的计算公式为Kln(K/ q)，平均度数的计算公式为lnK，K是原始数据长度。在平均分帧长LT码系统中，假设原始数据K平均分成8组，满足式(4)：

由假设条件可知，平均分帧长LT码的复杂度Q计算公式如下：

当原始数据进行原始LT编码时，原始LT码的复杂度计算公式如下：

平均分帧长LT码的平均度数D计算公式如下：

原始LT码的平均度数计算公式如下：

由于k＜8k，因此得到Q'＜Q，D'＜D。

可见，应用平均分帧长LT码系统时，可以降低编译码复杂度，当原始数据固定时，可以在不增加额外运算量的情况下，一方面缩短编码时间，提高译码速率；另一方面提高译码成功率。

2.3 基于平均分帧长LT码的编译码系统模型建立

在分析系统的编译码复杂度与平均度数后，确定WSN中平均分帧长LT码的编译码系统模型如图2所示。

图2 W SN中平均分帧长LT码的编译码系统模型

3 矩阵压缩算法研究

根据上文建立的WSN中平均分帧长LT码的编译码系统模型，本节将对矩阵压缩编译码器进行探讨，基于已有的集中压缩算法研究多比特打包法[3]，以减少数据流量，同时实现节能。

3.1 矩阵G的生成

设t(t1, t2,…,tM)为编码后序列，s(s1, s2,…,sN)为原始信息序列，LT编码过程[4]可以表示为：

矩阵G的生成过程如图3所示。

图3 矩阵G的生成过程

3.2 基于单比特打包法的矩阵压缩算法原理

本文经过分析可知，矩阵G有如下特点：(1)元素只可能为0或1；(2)G中大部分元素是0的稀疏矩阵。

根据以上特点，可以确定改进矩阵压缩算法的编码方法，具体步骤为：(1)由编码原理生成矩阵G；(2)提取生成矩阵中所有元素为1的行位置和列位置；(3)将行位置和列位置用与其对应的二进制数表示；(4)将列位置相同的所有行位置打包成一个数据包；(5)重复以上步骤，直至完成。综上所述，得到的矩阵冗余量降低比可表示为：

其中，L为矩阵中1的个数；N为原始数据长度；M为编码后数据长度；x为行位置用二进制数表示时的位数；y为列位置用二进制数表示时的位数。

假设用数组a，b保存行位置二进制表示和列位置二进制表示，数组a，b中的位置值由更多二进制数表示，同时可以降低其误码率。应用该方法，只需将生成矩阵中的1的行位置和列位置进行传送，而不需传输整个生成矩阵，在接收端，也只需根据接收到的行位置和列位置进行译码，无需恢复生成矩阵即可译出原始数据。

3.3 多比特打包法

现阶段研究的LT码的编译码过程及应用都是对单比特原始数据进行打包传输，而单比特数据打包传输，在数据量较大的情况下会出现占用较大内存和带宽的问题，延时较大，且出现有效性和可靠性下降的现象。而影响内存空间的主要因素是生成矩阵，若将数据进行多比特数打包传输，生成矩阵G会大大减小，G将不再是影响存储空间大小的主要因素，能更好地发挥数字喷泉码的优势。

经过以上分析与验证得到多比特打包法，即将多个比特数进行打包后编码传送，取代原有的单比特数传输，这样在数据量较大时就可大大减少存储空间，减少存储冗余量，提高译码成功率。

4 LT码在WSN中的应用研究

由于实际用于森林中的WSN主要是自组织网络[5]，因此将WSN应用到森林中，再用数字喷泉码传输信息。根据林区的实际分布情况，提出2种WSN拓扑结构，即平面结构和分层结构，具有较好的扩展性和可靠性。

4.1 W SN中数字喷泉码和网络编码的级联码应用

WSN对传感器采集的数据进行接收、发送、处理等操作以完成信号传递，从而实现对特定区域的监测。基于此数字喷泉码和网络编码级联的方式已被应用到WSN中[6]。因为网络编码能在理想信道条件下，在相关节点通过最大流最小割定理对输入流编码获得最大可能速率，而喷泉码是一种无码率码，通过在相应节点结合网络编码和数字喷泉码，能减少能量损耗。

4.2 W SN平面结构中典型拓扑结构模型的建立

4.2.1 星形拓扑结构

星形拓扑结构如图4所示。其中，基站为中间节点，每个传感器节点作为一个边缘节点，在中间节点和边缘节点之间建立的链路看作是星形拓扑的一条边。为了能适应网络的特征，使得网络传播的总信息速率达到最大，建立适合每条链路的信息传输模式，即采用多速率、多分辨率的信源信息编码，使得不同的链路传输不同的编码信息[7-8]。

图4 星形拓扑结构

4.2.2 网状拓扑结构

该结构中的传感器节点是相同的，可直接进行通信，与基站传输数据和命令，该系统是多跳系统(图5)。在WSN中，有时会存在多对无线传感器节点之间在同一时间进行通信的情况。考虑如图5所示的一种特殊情况，图中有两对无线传感器节点要进行通信，其中，传感器A要将信息发送给传感器E，而传感器B要将信息发送给传感器D。由于地理位置的原因，它们都需要借助传感器C进行转发。由此可知，利用网络编码可在3个时隙内(在图5中，实线表示第1个时隙，虚线表示第2个时隙，点线表示第3个时隙；a，b为信息流)完成使用常用方法时4个时隙的信息传递量，即可以节省25%的发送时间，以完成信息传递。

图5 网状拓扑结构

4.2.3 混合拓扑结构

混合网络中存在整体传输数据时的线性接力拓扑结构(图6)。利用网络编码时，在第1个时隙，无线传感器节点1需要将信息a发送给无线传感器节点2；在第2个时隙内传感器节点2将信息a转发给传感器节点3；在第3个时隙内，传感器节点3将信息a广播出去，此时，传感器节点4和传感器节点2都会收到传感器节点3广播的信息a。同时传感器节点1也向传感器节点2发送信息b，传感器节点2可利用网络编码求出b，其他传感器节点的传输可依次仿照传感器节点2的处理进行，直到传到目的地传感器节点N。

图6 混合拓扑结构

应用本文提出的矩阵压缩法分别[9]计算3种拓扑结构中数字喷泉码存储冗余量的降低比，达到降低WSN多节点拓扑结构中数字喷泉码存储冗余量的目的。

4.3 W SN分层结构中典型拓扑结构模型的建立

图7为三频分层结构，S将信息流b1和b2传送到2个目的地网关A和B，频率1用于簇头与簇成员以及相距较近的簇成员之间的通信，而簇头之间的通信用频率2，来弥补平面结构可扩充性差的缺陷。网关之间的通信用频率3。可以认为此拓扑结构就是分层结构中的典型拓扑结构。

图7 三频分层结构

由于在分层结构中[10-12]，通常检测的区域很大，要传输的数据量也很大，此时考虑单比特打包传输已经不能满足信息量的要求，因此考虑多比特数打包传输的方法，将多比特数打包传输时，将减少矩阵的生成，达到降低存储冗余量的目的。在WSN的分层结构中，应用多比特数打包法进行LT码编码数据传输，然后对WSN整体求出一个平均的矩阵冗余量降低比。

5 系统仿真与结果分析

本文系统仿真平台是Vista系统，CPU为2.27 GHz，内存为2 GB，采用Matlab软件仿真。

5.1 原始LT码和平均分帧长LT码的编译码时间比较

图8为原始LT码和平均分帧长LT码的编译码时间比较。平均分帧长LT码编译码系统能够减少延时，提高编译码效率，增加速率。

图8 原始LT码和平均分帧长LT码的编译码时间比较

5.2 不同LT码分帧数的性能仿真分析

为了更好地说明不同分帧数对LT码压缩性能的影响，将原始帧长进行不同等分传输，如图9所示，应用码本压缩法对其生成矩阵进行压缩，得到矩阵冗余量降低比曲线。可见，随着平均分帧数的增加，矩阵冗余量降低比迅速增大，压缩效果显著。

图9 不同分帧数码本压缩时矩阵冗余量降低比值

5.3 不同比特数打包的LT码性能仿真分析

图10为LT码在不同比特数打包情况下的矩阵冗余量降低比性能曲线，原始数据为5 000 bit，平均分帧数分别为取1，2，4，5，8，10的6种情况。为便于对比，选择5 bit，8 bit，10 bit 3种情况分别进行打包，并进行仿真比较。可以看出，在平均分帧数相同条件下，随着每包比特数的增大，其矩阵冗余量降低比随之迅速上升。这是因为每包比特数的增长，使得生成矩阵减小，性能也随之变优。同时可以看出平均分帧数为10，10 bit打包时可使矩阵冗余量降低比达到103量级，而误比特率基本为0。

图10 不同比特数打包时LT码矩阵冗余量降低比值

5.4 分层Ad hoc网络中的LT码性能仿真分析

由于实际WSN中传输的数据量很大，因此考虑对LT码进行多比特数打包传输。

如图11所示，原始数据包为1 000时，图11(a)中每包5 bit，图11(b)中每包1 bit，由图11(a)可以看出，在码包个数相同条件下，多比特位数打包传输时的矩阵冗余量降低比远大于单包时的矩阵冗余量降低比，从图11(a)和图11(b)可以看出，分帧数为10时，采用多比特打包时，矩阵冗余量降低比已超过1 000，即103量级，而采用单包的平均分帧长矩阵压缩算法时，矩阵冗余量降低比只有140，即102量级，远小于多比特数打包时的矩阵冗余量降低比。可见，多比特数打包LT码压缩性能良好。

图11 数据包为1 000时不同比特数打包下矩阵冗余量降低比值

6 结束语

在WSN中引入传统LT码可以将传感器节点的数据分布存储到不同节点中，增强WSN的可靠性。但是由于传统LT算法的复杂度高、编译码时间长等问题，使得无线传感器网络的实时性较差。数字喷泉码不需要反馈，但译码时需要接收很多的编码分组，因此需要很大的内存空间，造成喷泉码难以在实际系统中应用。

本文研究表明，由于压缩编码方法会增加编译码时间，因此采用平均分帧长方法减少编译码时间，降低其复杂度。本文先将原数据进行平均分帧长处理，通过小帧长的方法对原始数据拆分编译码，然后对生成矩阵进行压缩编码，使得在不破坏喷泉码特性的前提下减少传送的数据量，增强LT码在实际应用中的可行性。在需要传输大量数据时，应用多比特打包法，可减少生成矩阵的大小，当使用越多的比特数进行打包时，存储空间占用将越少。因为生成矩阵大小决定了存储冗余量的大小，所以采用多比特打包法会使误码率上升，但数值非常小，可以忽略不计。LT码会增加网络冗余，而网络编码在WSN中则能提高编译码效率。在WSN中传输数据时，应用压缩编码方法会增加节点处理和传输数据的能量消耗，从而减少WSN的生命时间。但通过平均分帧长法和多比特打包法，可减少每次存储的生成矩阵大小、传输和接收数据时需要的带宽，以及每个节点处理和传输数据的能量消耗。所以，将网络编码和数据压缩相结合来利用WSN资源是一种有效的方法。今后将进一步研究数字喷泉码在并行下载、视频流、数据广播、数据文件存储、无线网络等领域中的应用。

[1] 樊平毅. 网络信息论[M]. 北京: 清华大学出版社, 2009.

[2] 张 翼, 高宏峰, 师春灵. LT码编译的改进方法[J]. 计算机工程, 2010, 36(11): 271-273, 276.

[3] 萨洛蒙. 数据压缩原理与应用[M]. 北京: 电子工业出版社, 2003.

[4] Byers J W, Lub y M, Mitze nmacher M. A Digital Fountain Approach to Asynchronous Re liable Multicast[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1528-1540.

[5] Mitzenmacher M. Digital Fountains: A S urvey and Lo ok Forward[C]//Proceedings of Infor mation Theory Workshop. San Antonio, USA: IEEE Press, 2004: 271-276.

[6] Xu Qian, S tankovic V, Xi ong Zixiang. Wyner-ziv Video Compression an d Fou ntain Co des for Receiver Driven Layered Multicast[J]. IEE E Transactions on Ci rcuits and Systems for Video Technology, 2007, 17(7): 901-906.

[7] Ma Yuanyuan, Yuan Dongfeng, Zhang Haixia. Fountain Codes and Applications to Reliable Wireless Broadcast System[C]// Proceedings of ITW’06. Chengdu, China: [s. n.], 2006: 66-70.

[8] Byers J, Luby M, Mitzenmacher M. Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed up Downloads[C]//Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies. [S. l.]: IEEE Press, 1999: 275-283.

[9] 胡凤国. 语言计量研究中的上小三角矩阵压缩存储算法[J].现代电子技术, 2011, 34(2): 109-115.

[10] 汤文亮, 曾祥元, 曹义亲. 基于ZigBee无线传感器网络的森林火灾监测系统[J]. 实验室研究与探索, 2010, 29(6): 49-53.

[11] Yang Jing, An Jianping, Yang Miao. Combined Fountain Code with Network Co ding for Error-tolerant T ransmission Network[C]//Proceedings of the 5th International Conference on W ireless Communications, Networking a nd Mo bile Computing. [S. l.]: IEEE Press, 2009: 1-4.

[12] 王 立. Ad hoc网络特点以及应用探究[J]. 计算机光盘软件与应用, 2011, (17): 69-70.

编辑 陆燕菲

Research on Storage Redundancy Reduction Method of Fountain Code in WSN

YUAN Bo, ZHAO Dan-feng, QIAN Jin-xi

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

For the problems that the redundant encoded data packets of fountain code are big and require large memory space, resulting in poor real-time Wireless Sensor Network(WSN) problems. A system of average framing length of Luby Transform(LT) codes split encoding and dec oding is designed. The ty pical topology m odel is built, th e cascade form o f the net work c oding and fountai n codes in d ata transmission is applied, and the i mprovement coding compression algorithm in the average framing length LT code generator matrix is introduced. The weighted average method and the multi-bit packag ing method are i ntroduced in the hierarchy of WSN, which greatly reduces the amount of storage redundancy without damaging the characteristic of fountain codes. Experimental results show that the system makes the red uction amount of the compression ra tio of the storag e redundancy in the WSN to 103, promotes the encoding rate a nd decoding rate in the WSN and improves the recovery rate of the data center.

Wireless Sensor Network(WSN); fountain code; average framing length LT code; compression algorithm; network coding; multi-bit packaging

10.3969/j.issn.1000-3428.2014.05.015

黑龙江省自然科学基金资助项目(F200810)。

袁 博(1989－)，女，硕士研究生，主研方向：信号处理；赵旦峰，教授、博士生导师；钱晋希，博士研究生。

2013-03-04

2013-05-08E-mail：icetinghai@126.com

1000-3428(2014)05-0068-05

A

TP393