采用噴泉碼的無線傳感器網絡數據編解碼算法

彭小峰，楊 川，王凱立，王正旭

(重慶理工大學電子信息與自動化學院，重慶 400054)

無線傳感器網絡(WSNs)被認為是21世紀最有影響的二十一項技術之一［1－2］。在一般情況下，WSNs傳輸數據是比較準確的，但對煤氣瓦斯泄漏、軍事戰場敵情檢測等場景，要求必須在異常事件發生時能及時、可靠、準確地傳遞數據，否則WSNs就有可能達不到要求［3］。另外，WSNs本身并不穩定，環境、傳輸距離、計算能力、通信帶寬等多方面的影響極易造成數據在傳輸過程中損壞或者丟失。如何在保證數據傳輸速度的前提下保證傳輸信息的準確度成為一個關鍵的問題。傳統的網絡可靠性機制(如鏈路層的ARQ和FEC)應用于WSNs時效率非常低下，甚至常常無法保證WSNs正常工作。

為在保證數據傳輸可靠性的同時不增加系統控制的復雜性，保證網絡模型的分層結構，本文采用一種新的稱為“噴泉碼”的編解碼算法，直接在應用層對數據進行分組編碼。該方法不僅在低能耗的WSNs中確保數據可靠傳輸，還能有效工作于各種異構網絡中，是一種有很大應用價值的新型數據傳輸方法。

1 可行性分析

WSNs因其自身的節點結構和部署特點，必須考慮如何高效地利用能量。如果在WSNs中使用噴泉碼進行編解碼，節點的計算能耗也會隨之增加。

WSNs的能耗有來自硬件自身的固有能耗，也有傳感器的節點能耗。傳感器的節點能耗主要產生于3個模塊:無線通信模塊、傳感器模塊和處理器模塊［4－5］。傳感器模塊耗能低，幾乎可以忽略不計。在通信模塊中，發送狀態下耗能最大，遠大于處理器模塊;接收和空閑狀態時，與處理器模塊耗能情況相當。據推算，100 m距離實現單跳傳輸一比特的數據所耗的能量足夠使處理器執行3000條以上的計算命令。在WSNs中利用噴泉碼技術進行編解碼，可以在保證可靠性的同時精簡數據量，減少冗雜數據的傳輸，有效減少發送的能耗量，從而達到節能的目的。

除了能量消耗需要考慮外，在WSNs中運用噴泉碼技術還必須基于一個事實——網絡鏈路質量不理想［6－8］。WSNs的節點一般使用的是長步跳，這必定會使鏈路的質量不太理想。在這種情況下，如果網絡采用的是重發請求的方式，即接收端向發送方發送未接收到數據包的重發請求信號，發送端接收到該請求后將丟失的數據重新發送，如此循環下去，發送端因為丟包反復重發，導致由于網絡的丟包率過大而使得節點的通信信道被過多的節點重發請求占用。尤其是當WSNs在進行數據分發時一般采用多播的方式，如果接受過多的重發請求可能會導致發送節點崩潰，給發送端整個系統帶來不可估量的嚴重后果。這種情況下使用噴泉碼則能很好地避免發送方和接收方對數據包丟失采取的過多數據重傳，表明噴泉碼在WSNs中可保證數據傳輸的質量。

2 系統方案及模型

在不改變原有網絡模型的條件下，分別在發送者和接收者的結構中加入編碼層和解碼層，使發送者在編碼層利用“噴泉碼”進行編碼，接收者在解碼層進行譯碼，對于其他層則不做任何改變。網絡結構模型如圖1所示。整個系統在保證數據可靠性的同時，有效地避免了增加網絡模型和系統結構的復雜性［9］。

圖1 可靠性傳輸網絡模型

3 噴泉碼編解碼算法設計

先將每個數據包進行分組，保證每個組中都包含k個長度相等的數據包B，并且每個數據包中都分配有一個k位的單位系數向量e。對于數據包Bi(1≤i≤k)，定義相應的ei值:除第i個分量的值為1外，其余分量的值均為0。這樣則構成了一個由組內所有向量組成的k×k單位矩陣。數據包的報文格式可設計為:組標識—系數向量—數據［10］。

對于源節點，首先計算所需編碼包數m，并產生m組隨機數，再用每組的隨機數對組內原始數據和隨機數據進行編碼，如圖2所示。將產生的m份數據傳輸給中繼節點。

圖2 源節點將k個源數據包編碼成m個編碼數據包

對于中繼節點，首先對給定時間內所收到的編碼數據進行檢查。假設數量為c，則可得到c組隨機數。按照上述編碼方法對編碼數據進行再次編碼，從而進一步減少數據之間的相關性。

匯聚節點Sink根據收到的編碼數據包數量進行判斷:如果收到的數據包大于k，判斷

對應的系數向量矩陣是否線性相關，或者

系數如果滿足線性相關，同時又滿足秩大于或者等于k，Sink則按照式(3)的數據編碼解碼矩陣方法恢復原始數據包［11］。

如果收到的編碼數據包數量小于k或者大于k，而對應的系數向量的秩小于k，Sink則請求原始節點繼續發送新的編碼數據包，并要求新發送的編碼數據包系數向量和已有的數據系數向量線性無關，直到Sink接收到的編碼數據包滿足解碼條件為止。

由于噴泉碼的各種編解碼性能分析方法和算法的設計方法類似，本文不再逐一介紹。考慮Rapto碼是最典型的噴泉碼，本文僅以Raptor碼為例分析算法性能和設計實現方法。

4 噴泉碼編解碼性能分析

假定對于任意一個編碼塊，該編碼塊擁有的信息包個數為k，冗余包個數為m，并且假定丟包率為p。因Raptor碼的譯碼與編碼復雜度相同，都與邊的個數成比，那么，如果有足夠的碼長，節點度的期望值即可得到，為ο(ln(D)+3)，所以其編譯碼的復雜度都是ο(k(ln(D)+3))。

理論上D的取值越大，Raptor碼的譯碼率越能逼近刪除信道容量，從而使得譯碼無效比率逼近1。

D的增大相對也讓譯碼變得更加復雜。一般情況下，數據包的數量級數多為104，故最佳D值取為100。

另一個決定譯碼性能的重要參數為γ。設定k=20000，β=0.5，D=100，通過仿真可以得到參數γ對譯碼性能的影響，如圖3所示。當數據包的數量級為104時，參數γ以0.01左右為佳。隨著數據包的減少，γ可適當增加，但是若γ選取不當，反而會增大譯碼無效的比例，減小譯碼的效率。原始數據包的個數越多，譯碼的性能越能體現出來。

圖3 參數γ對譯碼性能的影響

圖4是β=0.5時原始數據包數對譯碼性能的影響。觀察圖4可知:數據包越多，譯碼的無效率越趨近1;當數據包的數量級為104時，譯碼需要的冗余包大約為原始數據包數的5%，而當數據包數比較少的時候，所需的冗余包數會大于 10%［12］。

圖4 數據包數對Raptor碼譯碼性能的影響

波紋尺的大小同樣會直接影響Raptor的譯碼性能。波紋尺不能過大也不能太小。圖5是波紋尺在原始數據包數為10000的時候對Raptor碼譯碼性能的影響。

圖5 波紋對Raptor譯碼性能的影響

5 噴泉碼編解碼算法的實現

本設計采用加州大學伯克利分校開發的基于構件(component-based)的開放源代碼TinyOS操作系統。TinyOS是專為WSNs設計的操作系統，能在實現快速更新的同時使受傳感網絡存儲器限制的代碼長度得到減小［13－14］。

對于Raptor碼，數據包的結構設計如下:

Raptor碼的編碼流程如圖6所示。

圖6 Raptor碼編碼流程

為了方便譯碼，設置如下3個宏:

Raptor碼譯碼流程如圖7所示。

圖7 Raptor碼譯碼流程

6 結束語

本文著重分析了噴泉碼技術在無線傳感器網絡中實現數據傳輸的可行性，基于系統設計方案和模型設計了噴泉碼編解碼算法。以噴泉碼中的Raptor碼為例，主要針對參數D、數據包數以及波紋尺對Raptor譯碼性能的影響進行了實驗。實驗結果表明:通過合理設置相關參數，該算法能有效提高譯碼成功率，對研究其他噴泉碼的編解碼算法具有一定的參考價值。

新方案在編解碼是否存在其他額外的開銷，以及噴泉碼在無線傳感器網絡中的編解碼速度是否優于現有的其他算法編解碼速度等方面還有待進一步研究。

［1］魏康林，溫志渝，趙新強，等.基于MEMS的結構監測無線傳感器網絡研究進展［J］.壓電與聲光，2010(4):692－696.

［2］陶紅艷.無線傳感器網絡動態分簇路由BWAS的算法研究［J］.壓電與聲光，2011(1):155－160.

［3］唐海燕，余成波，張一萌.基于WSN的礦井環境檢測系統［J］.重慶理工大學學報:自然科學版，2011(5):105－109.

［4］牛星，李捷，周新運，等.無線傳感器網絡節點能耗測量及分析［J］.計算機科學，2012，39(2):84－87.

［5］洪鋒，褚紅偉，金宗科，等.無線傳感器網絡應用系統最新進展綜述［J］.計算機研究與發展，2010(S2).

［6］Zhang X，Wicker S B.Robustness vs efficiency in sensor networks［J］.Fourth International Symposium on Information Processing in Sensor Networks(IPSN).2005.

［7］段桂華，王偉平，王建新，等.一種基于多路徑網絡編碼的匿名通信機制［J］.軟件學報，2010(9):2338－2351.

［8］胡世文，華蓓.基于Bloom過濾器改進的Growth Codes［J］.計算機工程.2009，35(11):65 －67.

［9］賀超.機械振動無線傳感器網絡監測模式和網絡傳輸協議研究［D］.重慶:重慶大學，2009.

［10］丁飛，張西良，胡永光，等.無線傳感器網絡在環境監測系統中的應用［J］.微計算機信息，2006(25):175－177.

［11］劉政，狄佳.一種自適應Huffman算法在無線傳感器網絡數據壓縮中的應用［J］.重慶理工大學學報:自然科學版，2013(2):84 －88，92.

［12］張熒俊.擦除碼在無線傳感器網絡可靠數據傳輸中的應用［D］.西安:西安電子科技大學，2010.

［13］周迪.基于TinyOS的無線傳感器網絡簇內MAC協議設計［D］.上海:上海交通大學，2010.

［14］陳果.基于TinyOS的基本網絡協議研究［J］.電腦與信息技術，2010，18(1):11 －12，16.