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

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

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

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

1 可行性分析

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

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

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

2 系統(tǒng)方案及模型

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

圖1 可靠性傳輸網(wǎng)絡(luò)模型

3 噴泉碼編解碼算法設(shè)計

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

對于源節(jié)點，首先計算所需編碼包數(shù)m，并產(chǎn)生m組隨機數(shù)，再用每組的隨機數(shù)對組內(nèi)原始數(shù)據(jù)和隨機數(shù)據(jù)進行編碼，如圖2所示。將產(chǎn)生的m份數(shù)據(jù)傳輸給中繼節(jié)點。

圖2 源節(jié)點將k個源數(shù)據(jù)包編碼成m個編碼數(shù)據(jù)包

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

匯聚節(jié)點Sink根據(jù)收到的編碼數(shù)據(jù)包數(shù)量進行判斷:如果收到的數(shù)據(jù)包大于k，判斷

對應(yīng)的系數(shù)向量矩陣是否線性相關(guān)，或者

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

如果收到的編碼數(shù)據(jù)包數(shù)量小于k或者大于k，而對應(yīng)的系數(shù)向量的秩小于k，Sink則請求原始節(jié)點繼續(xù)發(fā)送新的編碼數(shù)據(jù)包，并要求新發(fā)送的編碼數(shù)據(jù)包系數(shù)向量和已有的數(shù)據(jù)系數(shù)向量線性無關(guān)，直到Sink接收到的編碼數(shù)據(jù)包滿足解碼條件為止。

由于噴泉碼的各種編解碼性能分析方法和算法的設(shè)計方法類似，本文不再逐一介紹?？紤]Rapto碼是最典型的噴泉碼，本文僅以Raptor碼為例分析算法性能和設(shè)計實現(xiàn)方法。

4 噴泉碼編解碼性能分析

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

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

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

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

圖3 參數(shù)γ對譯碼性能的影響

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

圖4 數(shù)據(jù)包數(shù)對Raptor碼譯碼性能的影響

波紋尺的大小同樣會直接影響Raptor的譯碼性能。波紋尺不能過大也不能太小。圖5是波紋尺在原始數(shù)據(jù)包數(shù)為10000的時候?qū)aptor碼譯碼性能的影響。

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

5 噴泉碼編解碼算法的實現(xiàn)

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

對于Raptor碼，數(shù)據(jù)包的結(jié)構(gòu)設(shè)計如下:

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

圖6 Raptor碼編碼流程

為了方便譯碼，設(shè)置如下3個宏:

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

圖7 Raptor碼譯碼流程

6 結(jié)束語

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

新方案在編解碼是否存在其他額外的開銷，以及噴泉碼在無線傳感器網(wǎng)絡(luò)中的編解碼速度是否優(yōu)于現(xiàn)有的其他算法編解碼速度等方面還有待進一步研究。

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

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

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

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

［5］洪鋒，褚紅偉，金宗科，等.無線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進展綜述［J］.計算機研究與發(fā)展，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］段桂華，王偉平，王建新，等.一種基于多路徑網(wǎng)絡(luò)編碼的匿名通信機制［J］.軟件學(xué)報，2010(9):2338－2351.

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

［9］賀超.機械振動無線傳感器網(wǎng)絡(luò)監(jiān)測模式和網(wǎng)絡(luò)傳輸協(xié)議研究［D］.重慶:重慶大學(xué)，2009.

［10］丁飛，張西良，胡永光，等.無線傳感器網(wǎng)絡(luò)在環(huán)境監(jiān)測系統(tǒng)中的應(yīng)用［J］.微計算機信息，2006(25):175－177.

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

［12］張熒俊.擦除碼在無線傳感器網(wǎng)絡(luò)可靠數(shù)據(jù)傳輸中的應(yīng)用［D］.西安:西安電子科技大學(xué)，2010.

［13］周迪.基于TinyOS的無線傳感器網(wǎng)絡(luò)簇內(nèi)MAC協(xié)議設(shè)計［D］.上海:上海交通大學(xué)，2010.

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