基于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.