基于Raptor碼的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)分布存儲(chǔ)

郭峰

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

基于Raptor碼的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)分布存儲(chǔ)

郭峰

哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱 150001

在無(wú)線傳感器網(wǎng)絡(luò)中，經(jīng)常出現(xiàn)節(jié)點(diǎn)失效等意外情況。如何實(shí)現(xiàn)數(shù)據(jù)的分布式存儲(chǔ)是無(wú)線傳感器研究的重點(diǎn)。根據(jù)以包為中心編碼的相關(guān)研究，提出了一種基于Raptor碼的無(wú)線傳感器分布式數(shù)據(jù)存儲(chǔ)方案。Raptor碼是噴泉碼的一種，是一種在刪除信道上有效的低復(fù)雜度的編碼。通過(guò)預(yù)編碼形成虛擬節(jié)點(diǎn)，使校驗(yàn)包更多的參與LT編碼（Luby transform code），提高了編碼的隨機(jī)性。實(shí)驗(yàn)證明在有噪聲條件下，具有優(yōu)于分布式LT碼的性能。

Raptor碼；無(wú)線信道；傳感器網(wǎng)絡(luò)；數(shù)據(jù)存儲(chǔ)；虛擬節(jié)點(diǎn)

無(wú)線傳感器網(wǎng)絡(luò)（WSN）［1］是一種建立在特定區(qū)域的自組織Ad-hoc網(wǎng)絡(luò)，廣泛應(yīng)用于軍事、工業(yè)、交通、環(huán)保等領(lǐng)域［2］。但無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算能力和能量十分有限。因此，如何在節(jié)點(diǎn)（特別是大量節(jié)點(diǎn)）突然死亡的情況下，保證傳感器數(shù)據(jù)的有效收集是當(dāng)前研究的熱點(diǎn)。傳統(tǒng)的解決方案是采用簡(jiǎn)單泛洪或傳統(tǒng)糾錯(cuò)編碼實(shí)現(xiàn)數(shù)據(jù)的分布式存儲(chǔ)。但這2種方式會(huì)大量消耗系統(tǒng)資源并存在糾錯(cuò)門限數(shù)據(jù)噴泉碼是一種無(wú)碼率的編碼。2002年，Luby M［3］提出了第一種實(shí)用的噴泉碼—LT碼。2006年，shokrollahi［4］改進(jìn)了LT碼，提出了Raptor碼。數(shù)字噴泉碼非常適合在無(wú)線傳感器網(wǎng)絡(luò)中數(shù)據(jù)的分布式存儲(chǔ)，人們針對(duì)這一問(wèn)題做了大量的研究［5-6］。2006年，Kamara［7-8］提出了一種基于噴泉碼的分布式編碼方案GrowthCodes，用以提高網(wǎng)絡(luò)數(shù)據(jù)的持久性。2007年，Dimakis等［9］設(shè)計(jì)了一種新的分布式編碼方案，該編碼方案采用查詢機(jī)制來(lái)完成分布式編碼。以上這2種算法都是以節(jié)點(diǎn)為中心完成編碼。2009年Dejan Vukobratovic［10］提出了以包為中心LT碼的編碼方式。

1 基于Raptor碼的分布式存儲(chǔ)方案

傳統(tǒng)的存儲(chǔ)方案是由節(jié)點(diǎn)來(lái)主導(dǎo)，控制整個(gè)編碼過(guò)程，故收集滿足度分布的源數(shù)據(jù)塊并進(jìn)行噴泉碼編碼是節(jié)點(diǎn)的任務(wù)；以包為中心的編碼方案恰好相反。整個(gè)編碼過(guò)程由每個(gè)碼包包頭中的信息來(lái)控制，這樣碼包在網(wǎng)絡(luò)中傳輸?shù)倪^(guò)程中同時(shí)就可以完成編碼。這種以包為中心的編碼方法比傳統(tǒng)的以節(jié)點(diǎn)為中心的方式更適用于分布式的傳感器網(wǎng)絡(luò)環(huán)境。

1.1 分布式LT碼編碼方案

LT碼是第一類碼率不受限的實(shí)用噴泉碼編碼方案。圖1為L(zhǎng)T碼的編碼示意圖。

圖1 LT碼的編碼示意

2009年Dejan Vukobratovic提出了以包為中心LT碼的編碼方式。分布式LT包生成過(guò)程如圖2所示，具體步驟如下：

1）初始化階段：每個(gè)節(jié)點(diǎn)產(chǎn)生b個(gè)拷貝，每個(gè)拷貝依據(jù)度分布產(chǎn)生一個(gè)度值d。

2）編碼階段：每個(gè)編碼包在網(wǎng)絡(luò)中隨機(jī)漫步［11］，選擇節(jié)點(diǎn)進(jìn)行異操作，收集其他d－1個(gè)數(shù)據(jù)。

3）存儲(chǔ)階段：編碼完成之后隨機(jī)將數(shù)據(jù)包存入節(jié)點(diǎn)進(jìn)行保存。

觀察組:硝苯地平控釋片（進(jìn)口藥品注冊(cè)證號(hào)：H20171341；批準(zhǔn)文號(hào)：國(guó)藥準(zhǔn)字 J20180025，規(guī)格:30 mg×7 片）；起始劑量:口服 30 mg/次，1 次/d，常用劑量:口服 30 mg/次，1～2次/d。纈沙坦膠囊（國(guó)藥準(zhǔn)字H20040217，規(guī)格:80 mg×7 s），起始劑量:口服 80 mg/次，1 次/d，常用劑量:口服 80 mg/次，1～2 次/d。

圖2 分布式LT包生成過(guò)程

但該編碼方案存在2個(gè)問(wèn)題：1）該結(jié)果得出的條件是理想的，即不出現(xiàn)丟包。而在實(shí)際的網(wǎng)絡(luò)環(huán)境中這是不現(xiàn)實(shí)的，尤其是LT碼中的高度包更易在網(wǎng)絡(luò)中丟失，使性能急劇下降。2）LT碼的編譯碼代價(jià)隨klnk增長(zhǎng)，隨著網(wǎng)絡(luò)規(guī)模的增大，譯碼工作會(huì)變得困難，不適合在大型網(wǎng)絡(luò)中應(yīng)用。

1.2 分布式Raptor碼編碼方案

為了修正分布式LT碼的缺陷，文中提出了一種分布式Raptor碼的編碼方案。Raptor碼編碼首先用一個(gè)分組碼進(jìn)行預(yù)編碼，然后采用一個(gè)平均度約為3的弱化LT碼對(duì)數(shù)據(jù)符號(hào)進(jìn)行編碼。實(shí)驗(yàn)表明該方法取得了良好的效果。Raptor碼的度分布為

式中ε為編碼參數(shù)，用以調(diào)節(jié)解碼率。

分布Raptor碼編碼過(guò)程可分為以下2個(gè)步驟。

1）預(yù)編碼階段。

首先按照碼率R＝b／a，每個(gè)節(jié)點(diǎn)生成m＝（ab）個(gè)校驗(yàn)包，每個(gè)節(jié)點(diǎn)將自己的m個(gè)數(shù)據(jù)包發(fā)送到網(wǎng)絡(luò)中，根據(jù)校驗(yàn)包生成算法在網(wǎng)絡(luò)中隨機(jī)漫步生成最終的校驗(yàn)包，而后將校驗(yàn)包根據(jù)一定的存儲(chǔ)原則在適當(dāng)?shù)墓?jié)點(diǎn)存儲(chǔ)下來(lái)，這樣在一個(gè)節(jié)點(diǎn)內(nèi)就不僅有本節(jié)點(diǎn)的數(shù)據(jù)包，還有可能存儲(chǔ)了校驗(yàn)包。這樣既可以將此節(jié)點(diǎn)看成信息節(jié)點(diǎn)，也可以看成校驗(yàn)節(jié)點(diǎn)，稱這樣的校驗(yàn)節(jié)點(diǎn)為虛擬節(jié)點(diǎn)。校驗(yàn)包的格式如圖3所示。

圖3 預(yù)編碼包包頭格式

每個(gè)節(jié)點(diǎn)上的數(shù)據(jù)包根據(jù)步長(zhǎng)隨機(jī)選取一個(gè)節(jié)點(diǎn)加入編碼，此時(shí)預(yù)編碼計(jì)數(shù)器減1，節(jié)點(diǎn)編號(hào)加入數(shù)據(jù)源節(jié)點(diǎn)號(hào)部分。重復(fù)此步驟，直到預(yù)編碼計(jì)數(shù)器減到0為止，這樣就形成了一個(gè)校驗(yàn)節(jié)點(diǎn)包。

完成預(yù)編碼階段以后，網(wǎng)絡(luò)中的總包數(shù)為na個(gè)，平均每個(gè)節(jié)點(diǎn)有a個(gè)數(shù)據(jù)包。在LT編碼階段，每個(gè)節(jié)點(diǎn)為自己節(jié)點(diǎn)上的每個(gè)數(shù)據(jù)包（包括節(jié)點(diǎn)上的b個(gè)原始數(shù)據(jù)拷貝和當(dāng)前存儲(chǔ)的校驗(yàn)包），其包格式如圖4所示。

圖4 LT碼編碼包包頭格式

隨機(jī)從ΩD（x）中選取一個(gè)度值d，將d－1寫入帶編碼符號(hào)計(jì)數(shù)器，而后數(shù)據(jù)包進(jìn)入網(wǎng)絡(luò)進(jìn)行隨機(jī)漫步。根據(jù)步長(zhǎng)和漫步算法，數(shù)據(jù)包在網(wǎng)絡(luò)中前進(jìn)，當(dāng)步長(zhǎng)減為0時(shí)，當(dāng)前節(jié)點(diǎn)會(huì)選擇數(shù)據(jù)包與當(dāng)前碼包進(jìn)行模二和，待編碼計(jì)數(shù)器減1。數(shù)據(jù)包選擇策略是：根據(jù)R＝b／a的編碼比率，節(jié)點(diǎn)以R的概率選擇節(jié)點(diǎn)的原始數(shù)據(jù)拷貝，以1－R的概率選擇校驗(yàn)包。反復(fù)重復(fù)此步驟，直到待編碼計(jì)數(shù)器減到0為止，這樣就形成了一個(gè)最終的數(shù)據(jù)包。

2 仿真分析

2.1 與傳統(tǒng)分布式方案的比較分析

傳統(tǒng)分布式方案可大致分為3類：簡(jiǎn)單泛洪方式、傳統(tǒng)糾錯(cuò)編碼和以節(jié)點(diǎn)為中心的噴泉碼方案。

簡(jiǎn)單泛洪是每個(gè)節(jié)點(diǎn)將自身的數(shù)據(jù)拷貝若干份后發(fā)送到其他節(jié)點(diǎn)。這種解決方案對(duì)網(wǎng)絡(luò)資源造成極大浪費(fèi)。

將傳統(tǒng)糾錯(cuò)編碼應(yīng)用到數(shù)據(jù)分布式存儲(chǔ)中可以改善系統(tǒng)性能，在確知網(wǎng)絡(luò)的刪余概率時(shí)性能較好，但無(wú)線傳感器網(wǎng)絡(luò)所處環(huán)境十分惡劣，當(dāng)網(wǎng)絡(luò)的刪余概率超過(guò)糾錯(cuò)門限，會(huì)造成大量數(shù)據(jù)無(wú)法恢復(fù)。

以節(jié)點(diǎn)為中心的噴泉碼方案可以解決傳統(tǒng)糾錯(cuò)編碼的問(wèn)題。但以節(jié)點(diǎn)為中心的編碼方式要求網(wǎng)絡(luò)中需要專門的編碼節(jié)點(diǎn)且分布均勻。在隨機(jī)拋撒的網(wǎng)絡(luò)環(huán)境中編碼節(jié)點(diǎn)很難均與地分布在整個(gè)網(wǎng)絡(luò)中，并且網(wǎng)絡(luò)中編碼節(jié)點(diǎn)的能量消耗較快，編碼節(jié)點(diǎn)可能突然死亡。

為分析分布式Raptor碼與上述3種算法的性能，在N＝500，通信半徑R＝0.15的情況下對(duì)這4種算法在步長(zhǎng)取1～20時(shí)的性能進(jìn)行仿真，結(jié)果如圖5所示。

圖5 分布式Raptor碼與傳統(tǒng)方案的比較

從圖5可以看出簡(jiǎn)單泛洪算法的性能最差，該算法沒(méi)有使用任何編碼手段，使得算法性能不高。傳統(tǒng)糾錯(cuò)碼方案在性能上有了一定的提高，但傳統(tǒng)糾錯(cuò)編碼方案在分布式信源條件下難以實(shí)現(xiàn)嚴(yán)格的校驗(yàn)關(guān)系，且存在碼率門限，所以其性能相對(duì)較差。這2種算法中編碼步長(zhǎng)對(duì)性能的影響較小。以節(jié)點(diǎn)為中心的噴泉碼方案較前兩種方案性能有了較大的提高，隨著編碼步長(zhǎng)的增大性能提高，但當(dāng)編碼步長(zhǎng)較大時(shí)，性能會(huì)隨著編碼步長(zhǎng)的增加而下降。從圖中可以看出，文中提出的分布式Raptor碼方案比前3種方案性能有了明顯的改善，并隨著編碼步長(zhǎng)的增加而提高。

相對(duì)于以上3種分布式方案，文中提出的編碼方案編譯碼算法簡(jiǎn)單、性能優(yōu)良，編碼過(guò)程由數(shù)據(jù)包包頭控制，網(wǎng)絡(luò)中不需要有特殊的編碼節(jié)點(diǎn)，非常適合無(wú)線傳感器網(wǎng)絡(luò)環(huán)境。

2.2 與分布式LT的比較分析

分布式LT碼編碼方案在理想情況下可取得非常好的效果。在c＝0.1，δ＝0.5，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N＝500對(duì)其進(jìn)行仿真。圖6為分布式LT碼的解碼數(shù)據(jù)包數(shù)與隨機(jī)漫步步長(zhǎng)的關(guān)系圖，b為原始數(shù)據(jù)拷貝數(shù)。

但該結(jié)果的前提是網(wǎng)絡(luò)中不存在丟包，但實(shí)際無(wú)線傳感器網(wǎng)絡(luò)不可避免都存在丟包現(xiàn)象。在實(shí)際網(wǎng)絡(luò)環(huán)境中一方面步長(zhǎng)的增加會(huì)增大丟包的可能性，另一方面LT編碼中的高度包會(huì)因?yàn)樵诰W(wǎng)絡(luò)中漫步時(shí)間過(guò)長(zhǎng)而丟失。而LT碼的覆蓋度恰恰是由這些高度包來(lái)保證的。因此分布式LT碼的性能會(huì)隨著網(wǎng)絡(luò)丟包率的上升而大幅下降。

圖6 分布式LT碼與集中式LT碼性能比較

圖7為分布式LT碼和Raptor碼在有噪信道下剩余包數(shù)隨步長(zhǎng)變化圖，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N＝500，丟包率為5%。Raptor碼ε＝0.35，b＝6，m＝4，LT碼b＝10。由圖7可以看出分布式TL碼在有噪聲的情況下碼包的存活數(shù)低于文中提出的分布式Raptor碼。

圖7 分布式Raptor碼與LT碼數(shù)據(jù)包存活數(shù)

圖8為分布式Raptor碼與LT碼解碼包數(shù)隨丟包率變化的仿真圖，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N＝500，漫步步長(zhǎng)等于3。Raptor碼ε＝0.15，b＝6，m＝4，LT碼b＝10。雖然文中提出的方案在無(wú)丟包的情況下稍差，但在實(shí)際有噪聲的情況下，分布式Raptor的解碼所需的包數(shù)要少于分布式LT碼，在丟包率大于13%的情況下LT開(kāi)始出現(xiàn)不能解碼的現(xiàn)象。

圖8 分布式Raptor碼與LT碼解碼包數(shù)

3 結(jié)束語(yǔ)

以包為中心的分布式噴泉碼相比以節(jié)點(diǎn)為中心的噴泉碼更適合無(wú)線傳感器網(wǎng)絡(luò)的環(huán)境。文中提出的編碼方案將Raptor碼引入了無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)分布存儲(chǔ)，修正了分布式LT碼編碼方式的不足。實(shí)驗(yàn)結(jié)果表明，在有噪信道的條件下，分布式Raptor碼具有優(yōu)于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］孫利民，李建中，陳渝.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，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，F(xiàn)ELDMAN 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.