采用喷泉码的无线传感器网络数据编解码算法

彭小峰，杨 川，王凯立，王正旭

(重庆理工大学电子信息与自动化学院，重庆 400054)

无线传感器网络(WSNs)被认为是21世纪最有影响的二十一项技术之一［1－2］。在一般情况下，WSNs传输数据是比较准确的，但对煤气瓦斯泄漏、军事战场敌情检测等场景，要求必须在异常事件发生时能及时、可靠、准确地传递数据，否则WSNs就有可能达不到要求［3］。另外，WSNs本身并不稳定，环境、传输距离、计算能力、通信带宽等多方面的影响极易造成数据在传输过程中损坏或者丢失。如何在保证数据传输速度的前提下保证传输信息的准确度成为一个关键的问题。传统的网络可靠性机制(如链路层的ARQ和FEC)应用于WSNs时效率非常低下，甚至常常无法保证WSNs正常工作。

为在保证数据传输可靠性的同时不增加系统控制的复杂性，保证网络模型的分层结构，本文采用一种新的称为“喷泉码”的编解码算法，直接在应用层对数据进行分组编码。该方法不仅在低能耗的WSNs中确保数据可靠传输，还能有效工作于各种异构网络中，是一种有很大应用价值的新型数据传输方法。

1 可行性分析

WSNs因其自身的节点结构和部署特点，必须考虑如何高效地利用能量。如果在WSNs中使用喷泉码进行编解码，节点的计算能耗也会随之增加。

WSNs的能耗有来自硬件自身的固有能耗，也有传感器的节点能耗。传感器的节点能耗主要产生于3个模块:无线通信模块、传感器模块和处理器模块［4－5］。传感器模块耗能低，几乎可以忽略不计。在通信模块中，发送状态下耗能最大，远大于处理器模块;接收和空闲状态时，与处理器模块耗能情况相当。据推算，100 m距离实现单跳传输一比特的数据所耗的能量足够使处理器执行3000条以上的计算命令。在WSNs中利用喷泉码技术进行编解码，可以在保证可靠性的同时精简数据量，减少冗杂数据的传输，有效减少发送的能耗量，从而达到节能的目的。

除了能量消耗需要考虑外，在WSNs中运用喷泉码技术还必须基于一个事实——网络链路质量不理想［6－8］。WSNs的节点一般使用的是长步跳，这必定会使链路的质量不太理想。在这种情况下，如果网络采用的是重发请求的方式，即接收端向发送方发送未接收到数据包的重发请求信号，发送端接收到该请求后将丢失的数据重新发送，如此循环下去，发送端因为丢包反复重发，导致由于网络的丢包率过大而使得节点的通信信道被过多的节点重发请求占用。尤其是当WSNs在进行数据分发时一般采用多播的方式，如果接受过多的重发请求可能会导致发送节点崩溃，给发送端整个系统带来不可估量的严重后果。这种情况下使用喷泉码则能很好地避免发送方和接收方对数据包丢失采取的过多数据重传，表明喷泉码在WSNs中可保证数据传输的质量。

2 系统方案及模型

在不改变原有网络模型的条件下，分别在发送者和接收者的结构中加入编码层和解码层，使发送者在编码层利用“喷泉码”进行编码，接收者在解码层进行译码，对于其他层则不做任何改变。网络结构模型如图1所示。整个系统在保证数据可靠性的同时，有效地避免了增加网络模型和系统结构的复杂性［9］。

图1 可靠性传输网络模型

3 喷泉码编解码算法设计

先将每个数据包进行分组，保证每个组中都包含k个长度相等的数据包B，并且每个数据包中都分配有一个k位的单位系数向量e。对于数据包Bi(1≤i≤k)，定义相应的ei值:除第i个分量的值为1外，其余分量的值均为0。这样则构成了一个由组内所有向量组成的k×k单位矩阵。数据包的报文格式可设计为:组标识—系数向量—数据［10］。

对于源节点，首先计算所需编码包数m，并产生m组随机数，再用每组的随机数对组内原始数据和随机数据进行编码，如图2所示。将产生的m份数据传输给中继节点。

图2 源节点将k个源数据包编码成m个编码数据包

对于中继节点，首先对给定时间内所收到的编码数据进行检查。假设数量为c，则可得到c组随机数。按照上述编码方法对编码数据进行再次编码，从而进一步减少数据之间的相关性。

汇聚节点Sink根据收到的编码数据包数量进行判断:如果收到的数据包大于k，判断

对应的系数向量矩阵是否线性相关，或者

系数如果满足线性相关，同时又满足秩大于或者等于k，Sink则按照式(3)的数据编码解码矩阵方法恢复原始数据包［11］。

如果收到的编码数据包数量小于k或者大于k，而对应的系数向量的秩小于k，Sink则请求原始节点继续发送新的编码数据包，并要求新发送的编码数据包系数向量和已有的数据系数向量线性无关，直到Sink接收到的编码数据包满足解码条件为止。

由于喷泉码的各种编解码性能分析方法和算法的设计方法类似，本文不再逐一介绍。考虑Rapto码是最典型的喷泉码，本文仅以Raptor码为例分析算法性能和设计实现方法。

4 喷泉码编解码性能分析

假定对于任意一个编码块，该编码块拥有的信息包个数为k，冗余包个数为m，并且假定丢包率为p。因Raptor码的译码与编码复杂度相同，都与边的个数成比，那么，如果有足够的码长，节点度的期望值即可得到，为ο(ln(D)+3)，所以其编译码的复杂度都是ο(k(ln(D)+3))。

理论上D的取值越大，Raptor码的译码率越能逼近删除信道容量，从而使得译码无效比率逼近1。

D的增大相对也让译码变得更加复杂。一般情况下，数据包的数量级数多为104，故最佳D值取为100。

另一个决定译码性能的重要参数为γ。设定k=20000，β=0.5，D=100，通过仿真可以得到参数γ对译码性能的影响，如图3所示。当数据包的数量级为104时，参数γ以0.01左右为佳。随着数据包的减少，γ可适当增加，但是若γ选取不当，反而会增大译码无效的比例，减小译码的效率。原始数据包的个数越多，译码的性能越能体现出来。

图3 参数γ对译码性能的影响

图4是β=0.5时原始数据包数对译码性能的影响。观察图4可知:数据包越多，译码的无效率越趋近1;当数据包的数量级为104时，译码需要的冗余包大约为原始数据包数的5%，而当数据包数比较少的时候，所需的冗余包数会大于 10%［12］。

图4 数据包数对Raptor码译码性能的影响

波纹尺的大小同样会直接影响Raptor的译码性能。波纹尺不能过大也不能太小。图5是波纹尺在原始数据包数为10000的时候对Raptor码译码性能的影响。

图5 波纹对Raptor译码性能的影响

5 喷泉码编解码算法的实现

本设计采用加州大学伯克利分校开发的基于构件(component-based)的开放源代码TinyOS操作系统。TinyOS是专为WSNs设计的操作系统，能在实现快速更新的同时使受传感网络存储器限制的代码长度得到减小［13－14］。

对于Raptor码，数据包的结构设计如下:

Raptor码的编码流程如图6所示。

图6 Raptor码编码流程

为了方便译码，设置如下3个宏:

Raptor码译码流程如图7所示。

图7 Raptor码译码流程

6 结束语

本文着重分析了喷泉码技术在无线传感器网络中实现数据传输的可行性，基于系统设计方案和模型设计了喷泉码编解码算法。以喷泉码中的Raptor码为例，主要针对参数D、数据包数以及波纹尺对Raptor译码性能的影响进行了实验。实验结果表明:通过合理设置相关参数，该算法能有效提高译码成功率，对研究其他喷泉码的编解码算法具有一定的参考价值。

新方案在编解码是否存在其他额外的开销，以及喷泉码在无线传感器网络中的编解码速度是否优于现有的其他算法编解码速度等方面还有待进一步研究。

［1］魏康林，温志渝，赵新强，等.基于MEMS的结构监测无线传感器网络研究进展［J］.压电与声光，2010(4):692－696.

［2］陶红艳.无线传感器网络动态分簇路由BWAS的算法研究［J］.压电与声光，2011(1):155－160.

［3］唐海燕，余成波，张一萌.基于WSN的矿井环境检测系统［J］.重庆理工大学学报:自然科学版，2011(5):105－109.

［4］牛星，李捷，周新运，等.无线传感器网络节点能耗测量及分析［J］.计算机科学，2012，39(2):84－87.

［5］洪锋，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述［J］.计算机研究与发展，2010(S2).

［6］Zhang X，Wicker S B.Robustness vs efficiency in sensor networks［J］.Fourth International Symposium on Information Processing in Sensor Networks(IPSN).2005.

［7］段桂华，王伟平，王建新，等.一种基于多路径网络编码的匿名通信机制［J］.软件学报，2010(9):2338－2351.

［8］胡世文，华蓓.基于Bloom过滤器改进的Growth Codes［J］.计算机工程.2009，35(11):65 －67.

［9］贺超.机械振动无线传感器网络监测模式和网络传输协议研究［D］.重庆:重庆大学，2009.

［10］丁飞，张西良，胡永光，等.无线传感器网络在环境监测系统中的应用［J］.微计算机信息，2006(25):175－177.

［11］刘政，狄佳.一种自适应Huffman算法在无线传感器网络数据压缩中的应用［J］.重庆理工大学学报:自然科学版，2013(2):84 －88，92.

［12］张荧俊.擦除码在无线传感器网络可靠数据传输中的应用［D］.西安:西安电子科技大学，2010.

［13］周迪.基于TinyOS的无线传感器网络簇内MAC协议设计［D］.上海:上海交通大学，2010.

［14］陈果.基于TinyOS的基本网络协议研究［J］.电脑与信息技术，2010，18(1):11 －12，16.