基于Raptor码的无线传感器网络数据分布存储

郭峰

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

基于Raptor码的无线传感器网络数据分布存储

郭峰

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

在无线传感器网络中，经常出现节点失效等意外情况。如何实现数据的分布式存储是无线传感器研究的重点。根据以包为中心编码的相关研究，提出了一种基于Raptor码的无线传感器分布式数据存储方案。Raptor码是喷泉码的一种，是一种在删除信道上有效的低复杂度的编码。通过预编码形成虚拟节点，使校验包更多的参与LT编码（Luby transform code），提高了编码的随机性。实验证明在有噪声条件下，具有优于分布式LT码的性能。

Raptor码；无线信道；传感器网络；数据存储；虚拟节点

无线传感器网络（WSN）［1］是一种建立在特定区域的自组织Ad-hoc网络，广泛应用于军事、工业、交通、环保等领域［2］。但无线传感器网络节点计算能力和能量十分有限。因此，如何在节点（特别是大量节点）突然死亡的情况下，保证传感器数据的有效收集是当前研究的热点。传统的解决方案是采用简单泛洪或传统纠错编码实现数据的分布式存储。但这2种方式会大量消耗系统资源并存在纠错门限数据喷泉码是一种无码率的编码。2002年，Luby M［3］提出了第一种实用的喷泉码—LT码。2006年，shokrollahi［4］改进了LT码，提出了Raptor码。数字喷泉码非常适合在无线传感器网络中数据的分布式存储，人们针对这一问题做了大量的研究［5-6］。2006年，Kamara［7-8］提出了一种基于喷泉码的分布式编码方案GrowthCodes，用以提高网络数据的持久性。2007年，Dimakis等［9］设计了一种新的分布式编码方案，该编码方案采用查询机制来完成分布式编码。以上这2种算法都是以节点为中心完成编码。2009年Dejan Vukobratovic［10］提出了以包为中心LT码的编码方式。

1 基于Raptor码的分布式存储方案

传统的存储方案是由节点来主导，控制整个编码过程，故收集满足度分布的源数据块并进行喷泉码编码是节点的任务；以包为中心的编码方案恰好相反。整个编码过程由每个码包包头中的信息来控制，这样码包在网络中传输的过程中同时就可以完成编码。这种以包为中心的编码方法比传统的以节点为中心的方式更适用于分布式的传感器网络环境。

1.1 分布式LT码编码方案

LT码是第一类码率不受限的实用喷泉码编码方案。图1为LT码的编码示意图。

图1 LT码的编码示意

2009年Dejan Vukobratovic提出了以包为中心LT码的编码方式。分布式LT包生成过程如图2所示，具体步骤如下：

1）初始化阶段：每个节点产生b个拷贝，每个拷贝依据度分布产生一个度值d。

2）编码阶段：每个编码包在网络中随机漫步［11］，选择节点进行异操作，收集其他d－1个数据。

3）存储阶段：编码完成之后随机将数据包存入节点进行保存。

观察组:硝苯地平控释片（进口药品注册证号：H20171341；批准文号：国药准字 J20180025，规格:30 mg×7 片）；起始剂量:口服 30 mg/次，1 次/d，常用剂量:口服 30 mg/次，1～2次/d。缬沙坦胶囊（国药准字H20040217，规格:80 mg×7 s），起始剂量:口服 80 mg/次，1 次/d，常用剂量:口服 80 mg/次，1～2 次/d。

图2 分布式LT包生成过程

但该编码方案存在2个问题：1）该结果得出的条件是理想的，即不出现丢包。而在实际的网络环境中这是不现实的，尤其是LT码中的高度包更易在网络中丢失，使性能急剧下降。2）LT码的编译码代价随klnk增长，随着网络规模的增大，译码工作会变得困难，不适合在大型网络中应用。

1.2 分布式Raptor码编码方案

为了修正分布式LT码的缺陷，文中提出了一种分布式Raptor码的编码方案。Raptor码编码首先用一个分组码进行预编码，然后采用一个平均度约为3的弱化LT码对数据符号进行编码。实验表明该方法取得了良好的效果。Raptor码的度分布为

式中ε为编码参数，用以调节解码率。

分布Raptor码编码过程可分为以下2个步骤。

1）预编码阶段。

首先按照码率R＝b／a，每个节点生成m＝（ab）个校验包，每个节点将自己的m个数据包发送到网络中，根据校验包生成算法在网络中随机漫步生成最终的校验包，而后将校验包根据一定的存储原则在适当的节点存储下来，这样在一个节点内就不仅有本节点的数据包，还有可能存储了校验包。这样既可以将此节点看成信息节点，也可以看成校验节点，称这样的校验节点为虚拟节点。校验包的格式如图3所示。

图3 预编码包包头格式

每个节点上的数据包根据步长随机选取一个节点加入编码，此时预编码计数器减1，节点编号加入数据源节点号部分。重复此步骤，直到预编码计数器减到0为止，这样就形成了一个校验节点包。

完成预编码阶段以后，网络中的总包数为na个，平均每个节点有a个数据包。在LT编码阶段，每个节点为自己节点上的每个数据包（包括节点上的b个原始数据拷贝和当前存储的校验包），其包格式如图4所示。

图4 LT码编码包包头格式

随机从ΩD（x）中选取一个度值d，将d－1写入带编码符号计数器，而后数据包进入网络进行随机漫步。根据步长和漫步算法，数据包在网络中前进，当步长减为0时，当前节点会选择数据包与当前码包进行模二和，待编码计数器减1。数据包选择策略是：根据R＝b／a的编码比率，节点以R的概率选择节点的原始数据拷贝，以1－R的概率选择校验包。反复重复此步骤，直到待编码计数器减到0为止，这样就形成了一个最终的数据包。

2 仿真分析

2.1 与传统分布式方案的比较分析

传统分布式方案可大致分为3类：简单泛洪方式、传统纠错编码和以节点为中心的喷泉码方案。

简单泛洪是每个节点将自身的数据拷贝若干份后发送到其他节点。这种解决方案对网络资源造成极大浪费。

将传统纠错编码应用到数据分布式存储中可以改善系统性能，在确知网络的删余概率时性能较好，但无线传感器网络所处环境十分恶劣，当网络的删余概率超过纠错门限，会造成大量数据无法恢复。

以节点为中心的喷泉码方案可以解决传统纠错编码的问题。但以节点为中心的编码方式要求网络中需要专门的编码节点且分布均匀。在随机抛撒的网络环境中编码节点很难均与地分布在整个网络中，并且网络中编码节点的能量消耗较快，编码节点可能突然死亡。

为分析分布式Raptor码与上述3种算法的性能，在N＝500，通信半径R＝0.15的情况下对这4种算法在步长取1～20时的性能进行仿真，结果如图5所示。

图5 分布式Raptor码与传统方案的比较

从图5可以看出简单泛洪算法的性能最差，该算法没有使用任何编码手段，使得算法性能不高。传统纠错码方案在性能上有了一定的提高，但传统纠错编码方案在分布式信源条件下难以实现严格的校验关系，且存在码率门限，所以其性能相对较差。这2种算法中编码步长对性能的影响较小。以节点为中心的喷泉码方案较前两种方案性能有了较大的提高，随着编码步长的增大性能提高，但当编码步长较大时，性能会随着编码步长的增加而下降。从图中可以看出，文中提出的分布式Raptor码方案比前3种方案性能有了明显的改善，并随着编码步长的增加而提高。

相对于以上3种分布式方案，文中提出的编码方案编译码算法简单、性能优良，编码过程由数据包包头控制，网络中不需要有特殊的编码节点，非常适合无线传感器网络环境。

2.2 与分布式LT的比较分析

分布式LT码编码方案在理想情况下可取得非常好的效果。在c＝0.1，δ＝0.5，网络节点数N＝500对其进行仿真。图6为分布式LT码的解码数据包数与随机漫步步长的关系图，b为原始数据拷贝数。

但该结果的前提是网络中不存在丢包，但实际无线传感器网络不可避免都存在丢包现象。在实际网络环境中一方面步长的增加会增大丢包的可能性，另一方面LT编码中的高度包会因为在网络中漫步时间过长而丢失。而LT码的覆盖度恰恰是由这些高度包来保证的。因此分布式LT码的性能会随着网络丢包率的上升而大幅下降。

图6 分布式LT码与集中式LT码性能比较

图7为分布式LT码和Raptor码在有噪信道下剩余包数随步长变化图，网络节点数N＝500，丢包率为5%。Raptor码ε＝0.35，b＝6，m＝4，LT码b＝10。由图7可以看出分布式TL码在有噪声的情况下码包的存活数低于文中提出的分布式Raptor码。

图7 分布式Raptor码与LT码数据包存活数

图8为分布式Raptor码与LT码解码包数随丢包率变化的仿真图，网络节点数N＝500，漫步步长等于3。Raptor码ε＝0.15，b＝6，m＝4，LT码b＝10。虽然文中提出的方案在无丢包的情况下稍差，但在实际有噪声的情况下，分布式Raptor的解码所需的包数要少于分布式LT码，在丢包率大于13%的情况下LT开始出现不能解码的现象。

图8 分布式Raptor码与LT码解码包数

3 结束语

以包为中心的分布式喷泉码相比以节点为中心的喷泉码更适合无线传感器网络的环境。文中提出的编码方案将Raptor码引入了无线传感器网络的数据分布存储，修正了分布式LT码编码方式的不足。实验结果表明，在有噪信道的条件下，分布式Raptor码具有优于LT码的性能。

［1］AKYILDIZ I F，SUETAL W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：a survey［J］.Computer Networks，2002，38（4）：393-412.

［2］孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版社，2005：4-5.

［3］LUBY M.LT codes［C］／／Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.Van-couver，Canada，2002：271-282.

［4］SHOKROLLAHI A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）：2551-2567.

［5］APAVATJRUT A.GOURSAUD C，COMANICIU C，et al.Toward increasing packet diversity for relaying LT fountain codes in wireless sensor networks［J］.IEEE Communica-tions Letters，2011，15（1）：52-54.

［6］SURACHAI C，HOSSAIN E.Wireless fountain coding with IEEE 802.11e block ACK for media streaming in wireline-cum-WiFi networks：a performance study［J］.IEEE Trans-actions on Mobile Computing，2011，10（10）：1416-1433.

［7］GUOGANG H，CHANG W C.Distributed source coding in wireless sensor networks［C］／／2nd International Conference on Quality of Service in Heterogeneous Wired／Wireless Net-works.Orlando，USA，2005：1－7.

［8］KAMRA A，MISRA V，FELDMAN J，et al.Growth codes：maximizing sensor network data persistence［C］／／Proceed-ings of the 2006 conference on Applications，technologies，architectures，and protocols for computer communications.New York，USA，2006：255-266.

［9］SCHIFF J，ANTONELLI D，DIMAKIS A G，et al.Robust message-passing for statistical inference in sensor networks［C］／／Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks.Cambridge，USA，2007：109-118.

［10］VUKOBRATOVIE D，STEFANOVIE C，CRNOJEVIC V，et al.A Packet-centric approach to distributed rateless cod-ing in wireless sensor network［C］／／6th Annual IEEE Communications Society Conference on Sensor.Rome，Ita-ly，2009：1-8.

［11］KINDLER G，ROMIK D.On distributions computable by random walks on graphs［J］.SIAM Journal on Discrete Mathematics，2004，17（4）：624-633.

Wireless sensor network data distributed storage based on Raptor code

GUO Feng
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

In wireless sensor networks，node failure accidents often occur.How to realize the distributed data storage is the key in the research of wireless sensors.According to related research with the package as the center code，this paper proposes a novel wireless sensor network distributed data storage scheme based on Raptor codes.Raptor code is a kind of fountain code，as well as an effective，low complex coding scheme over erasure channels.By form-ing virtual nodes in the pre-coding phase，this algorithm makes the parity packets more involved in Luby Transform（LT）coding，which improves the coding randomness.The experiment proved that in noisy conditions this scheme has better performance than LT codes.

Raptor code；wireless channel；sensor network；data storage；virtual nodes

TP393

A

TP3931009-671X（2014）05-040-04

10.3969／j.issn.1009-671X.201309004

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1009-671X.201309004.html

2013-09-08.

日期：2014-09-24.

郭峰（1987-），男，硕士研究生.

郭峰，E-mail：sy-guofeng1987＠163.com.