郭峰

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

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

郭峰

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

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

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

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

1 基于Raptor碼的分布式存儲方案

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

1.1 分布式LT碼編碼方案

LT碼是第一類碼率不受限的實用噴泉碼編碼方案。圖1為LT碼的編碼示意圖。

圖1 LT碼的編碼示意

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

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

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

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

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

圖2 分布式LT包生成過程

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

1.2 分布式Raptor碼編碼方案

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

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

分布Raptor碼編碼過程可分為以下2個步驟。

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

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

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

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

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

圖4 LT碼編碼包包頭格式

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

2 仿真分析

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

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

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

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

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

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

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

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

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

2.2 與分布式LT的比較分析

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

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

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

圖7為分布式LT碼和Raptor碼在有噪信道下剩余包數(shù)隨步長變化圖，網(wǎng)絡(luò)節(jié)點數(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é)點數(shù)N＝500，漫步步長等于3。Raptor碼ε＝0.15，b＝6，m＝4，LT碼b＝10。雖然文中提出的方案在無丟包的情況下稍差，但在實際有噪聲的情況下，分布式Raptor的解碼所需的包數(shù)要少于分布式LT碼，在丟包率大于13%的情況下LT開始出現(xiàn)不能解碼的現(xiàn)象。

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

3 結(jié)束語

以包為中心的分布式噴泉碼相比以節(jié)點為中心的噴泉碼更適合無線傳感器網(wǎng)絡(luò)的環(huán)境。文中提出的編碼方案將Raptor碼引入了無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)分布存儲，修正了分布式LT碼編碼方式的不足。實驗結(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ǎ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.