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

杜 涛

(晋中学院 远程教育学院，山西 晋中030600)

1 无线传感器网络的体系结构

1．1 无线传感器网络体系结构

传感器网络由接收发送器、传感器节点、Internet 或任务管理节点、通信卫星等组成．传感器的节点分布在指定的区域内，而且这些节点都能够对数据进行收集，利用“多跳”路由方式把数据传送到Sinko．Sink 能用同样的方式将信息发送给出去，Sink 直接与通信卫星或者Internet 相连，利用通信卫星或者Internet 能够很好地实现传感器与任务管理节点的通信功能［1－5］．

传感器节点是一个微型的嵌入式系统，通过携带能量有限的电池来实现供电的．对其它节点转发来的数据进行存储、存储能力、它的处理能力以及通信．传感器除了进行数据处管理、本地信息收集等这些处理，还与其它节点一同完成特定的任务．汇聚节点连接传感器网络与Internet 等外部网络，实现两种协议栈之间的协议顺利转换，而且可以把收集数据转发到外部的网络上面．汇聚节点是具有增强功能的传感器节点，当然也可以是没有功能的特殊网关设备［6－9］．

1．2 无线传感器网络协议栈

早期提出的协议栈包括数据链路层、网络层、物理层、应用层和传输层，这个是与互联网协议栈的五层协议相对应．协议栈还可以有移动管理平台、能量管理平台和任务管理平台．这几个平台使得传感器节点实现了高效协同，实现了在传感器网络中转发数据，并且能够支持资源共享以及多任务．

1)物理层是实现简单却有力的信号调制以及无线收发技术．

2)传输层是实现数据流的传输控制，这是通信服务质量的有效保障．

3)数据链路层是帧检测、媒体访问、数据成帧．

4)应用层是监测任务的应用层软件．

5)网络层是实现一个路由生成与路由选择．

2 编码在WSNs 的可行性分析

WSNs 的部署特点，是高效的利用能量是否顺利的重要一点．编码技术增加了节点的计算能耗，因此我们应该从节点能耗入手，探究编码是否可以在节点能耗上能够占一些优势． 硬件自身会有一线必须能耗之外，传感器能量消耗模块有传感器模块，无线通信模块以及处理器模块．处理器和传感器消耗的能量逐渐变低，但是与通信模块中的能耗却越大．在2002 年的Mobicom 上，Deborah Estin 有说到了传感器节能耗情况，如图1 所示．

图1 传感器节点各部分能量消耗Fig．1 All parts of sensor node energy consumption

图1 可以看出通信模块耗能情况处理器模块耗能情况的差别非常大．通信模块有4 种工作状态，包括空闲、睡眠、发送和接收，接收和空闲状态耗能情况差不多大，在发送状态的过程当中耗能是最大的，但也还是比较接近发送状态时候的能耗．也就是说节点在睡眠状态外，其他时候都是保持很高的能量消耗．使用编码时，若能够在保证可靠性又减少数据量的传输就能够节约很多能量． 传感器能耗包括通信距离能耗，也包括了硬件本身的必须的能耗．

上式中α 代表晶体磁震荡的能耗，E代表传感器节点的总能耗，β 表示放大器因子，n是衰减因子，d是通信距离．βdn就是距离能耗，E确实与d成指数关系，α 消耗的能量远大于βdn，WSNs 中的节点发射功率不大．Athero s 提供下面这个能量模型参数

很好的说明了这点．

如表1 可以看出发射功率占所消耗总功率的百分较小，8% 都没有超过． Martin Haenggi 和 Daniele Puccinelli 还使用MicaZ 和Mica2 节点对此进行了周密细致的实验进行验证，如图2 所示．

表1 Atheros2004 Tri－mode chipset 能耗参数Tab．1 Energy consumption parameters of Atheros2004 Tri－mode chipset

如 图3 所示，发射功率为10 dBm，总功率约为18． Sd-Bm，所耗的能耗在1．4%～14%范围之间．证明了WSNs 在距离增加后能耗并没有增加多少，却是节点数目和能耗是一个正比关系，在保证可靠性前提下，极短步跳对节能并无其他好的地方，反而会增加了传感器网络的能耗，还会干扰影响通信过程中的质量．

图2 节点总功耗与发射功率的关系Fig．2 The relationship between node total power consumption and transmission power

3 典型喷泉码(Raptor 码)实现原理

3．1 典型喷泉码(Raptor 码)预编码原理

如果经LT 译码出的数据包是由另一种编码方式实现，加上使用该方式译码可能会有较高的概率将原数据包译码出来．Raptor 码中预编码思想就是这么被提出来了，用有比率的纠错码先对数据编码，这里得到的冗余校验数据当成LT 码的输入．预编码所使用的码种是异或运算，与以往的区别就在于这个编码有无比率．以往的LT 码是无比率码，源数据端得到编码序列有些是无限的;另外预编码正常是用Tornado 码等这些有比率码，根据给定的度分布生成的校验节点数目是一个确定数． Tornado 是非正则的LDPC 码，分布序列为Heavy－Tail/Possion 分布，出度和入度各自服从一个度分布是其一大特点，出度即数据源节点的度，入度即编码后校验节点的度．如下图3 所示．

设E 为编码二分图的总边数，编码冗余度为β，k为左节点数．αr为校验节点的平均入度数，ai为变量节点的平均出度数，λi为与度为i的变量节点关联的边数之和与总边数E的比，dl和dr分别为变量节点和校验节点的最大度数，ρi为与度为i的校验节点关联的边数之和与总边数E的比，D为一正整数．根据定义的这些变量，可以得出如下式子:

则Tornado 码的度分布如下:

Tornado 码的编码与译码复杂度是一样的，同样是与边的个数成比，可得节点数的为O(ln(D)+ 3)，编译复杂度就为O(k(ln(D)+3))．

图3 LDPC 码中入度与出度Fig．3 The degree and the degree of LDPC code

3．2 弱LT 码的度分布

Raptor 码还包括弱LT 码编码过程，弱LT 码编码的原理与一般的LT 编码完全一样，不一样的地方就是弱LT 码的度分布设计目的不是成功解码所有源数据，而是以比较高的效率解码约95%左右的源数据，这里对弱LT 码的度分布进行探究．

Shokrollahi 之前有关Raptor 码的文章里，有说了经典的弱LT 码度分布，本课题只涉及该度分布使用，这里也就不具体证明和分析，只给这个度分布．

设Raptor 码的无效比率1 +ε ，弱LT 码的度分布μ(i)，可以有如下式子:

4 喷泉码编解码算法实现的数据收集协议

4．1 现有的Raptor 码分布式实现方案

Raptor 码编码由弱LT 码编码过程和预编码过程来实现，Raptor 码将这两个过程作为相互独立阶段，也就是说实现分布式的预编码之后再来实现LT 码．本课题考虑的场景为n个节点中有k个节点，课题中Raptor 码方案是将预编码当成独立阶段来进行，如图4 所示．

4．2 基于分布式Raptor 码的数据收集协议

以包为中心的Raptor 码分布式实现，进一步探究以包为中心的编码方法之后，较简易的在分布式中实现Raptor 编码．Raptor 编码中源数据节点是弱LT 编码的输入时的一个LT 编码过程，这里把编码包分类为不需要进行预编码直接进行弱LT 编码，和先进行预编码后再弱LT 编码两大类别．

图4 Raptor 码预编码现有的分布式实现Fig．4 Distributed implementation of raptor code precoding

图5 以包为中心的Raptor 码分布式实现Fig．5 Distributed implementation of packages centered raptor code

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

本课题利用加州大学伯克利分校开发的基于构件的开放源代码TinyOS 操作系统．TinyOS 是专为WSNs 设计的这样一个系统，在实现快速更新的同时能够让存储器限制的代码长度减小．数据包的设计如下所示:

6 结语

本课题主要是对喷泉码技术在无线传感器网络中实现数据传输的可行性探究，系统设计方案和模型设计了喷泉码编解码算法． 以喷泉码中的Raptor 码为例，进行深入的探究．在实验室科研支持下，本课题探究了线传感器网络中喷泉码技术的实现原理，总结了基于分布式喷泉码的数据收集技术研究动态．实验结果表明:合理的参数，该算法是可以有效改善译码的成功率．另外新方案在喷泉码无线传感器网络中的编解码速度能否比其他算法编解码速度更有优势等还需后续进一步探究．

图6 Raptor 码编码流程Fig．6 Process of raptor code coding

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

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

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

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

［5］ 孙利民，李建中，陈渝，等．无线传感器网络［M］．北京:清华大学出版社，2005:16－23．

［6］ 洪锋，褚红伟，金宗科，等．无线传感器网络应用系统最新进展综述［J］．计算机研究与发展，2010，47(增刊):81－87．

［7］ 何李石．无线传感器网络基于数字喷泉码的数据交换策略研究［M］．杭州:杭州电子科技大学出版社，2012:20－30．

［8］ 陈月云，刘伟．基于新型随机度分布的压缩喷泉码［J］．电了信息学报，2012，84(5):1185－1190．

［9］ 肖文显，刘震，马孝琴，等．无线传感器网络LEACH 路由协议研究［J］．河南科技学院学报:自然科学版，2012，40(1):93－98．