噴泉碼的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)編解碼算法的探究

杜 濤

(晉中學(xué)院 遠(yuǎn)程教育學(xué)院，山西 晉中030600)

1 無線傳感器網(wǎng)絡(luò)的體系結(jié)構(gòu)

1．1 無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)

傳感器網(wǎng)絡(luò)由接收發(fā)送器、傳感器節(jié)點(diǎn)、Internet 或任務(wù)管理節(jié)點(diǎn)、通信衛(wèi)星等組成．傳感器的節(jié)點(diǎn)分布在指定的區(qū)域內(nèi)，而且這些節(jié)點(diǎn)都能夠?qū)?shù)據(jù)進(jìn)行收集，利用“多跳”路由方式把數(shù)據(jù)傳送到Sinko．Sink 能用同樣的方式將信息發(fā)送給出去，Sink 直接與通信衛(wèi)星或者Internet 相連，利用通信衛(wèi)星或者Internet 能夠很好地實(shí)現(xiàn)傳感器與任務(wù)管理節(jié)點(diǎn)的通信功能［1－5］．

傳感器節(jié)點(diǎn)是一個微型的嵌入式系統(tǒng)，通過攜帶能量有限的電池來實(shí)現(xiàn)供電的．對其它節(jié)點(diǎn)轉(zhuǎn)發(fā)來的數(shù)據(jù)進(jìn)行存儲、存儲能力、它的處理能力以及通信．傳感器除了進(jìn)行數(shù)據(jù)處管理、本地信息收集等這些處理，還與其它節(jié)點(diǎn)一同完成特定的任務(wù)．匯聚節(jié)點(diǎn)連接傳感器網(wǎng)絡(luò)與Internet 等外部網(wǎng)絡(luò)，實(shí)現(xiàn)兩種協(xié)議棧之間的協(xié)議順利轉(zhuǎn)換，而且可以把收集數(shù)據(jù)轉(zhuǎn)發(fā)到外部的網(wǎng)絡(luò)上面．匯聚節(jié)點(diǎn)是具有增強(qiáng)功能的傳感器節(jié)點(diǎn)，當(dāng)然也可以是沒有功能的特殊網(wǎng)關(guān)設(shè)備［6－9］．

1．2 無線傳感器網(wǎng)絡(luò)協(xié)議棧

早期提出的協(xié)議棧包括數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、物理層、應(yīng)用層和傳輸層，這個是與互聯(lián)網(wǎng)協(xié)議棧的五層協(xié)議相對應(yīng)．協(xié)議棧還可以有移動管理平臺、能量管理平臺和任務(wù)管理平臺．這幾個平臺使得傳感器節(jié)點(diǎn)實(shí)現(xiàn)了高效協(xié)同，實(shí)現(xiàn)了在傳感器網(wǎng)絡(luò)中轉(zhuǎn)發(fā)數(shù)據(jù)，并且能夠支持資源共享以及多任務(wù)．

1)物理層是實(shí)現(xiàn)簡單卻有力的信號調(diào)制以及無線收發(fā)技術(shù)．

2)傳輸層是實(shí)現(xiàn)數(shù)據(jù)流的傳輸控制，這是通信服務(wù)質(zhì)量的有效保障．

3)數(shù)據(jù)鏈路層是幀檢測、媒體訪問、數(shù)據(jù)成幀．

4)應(yīng)用層是監(jiān)測任務(wù)的應(yīng)用層軟件．

5)網(wǎng)絡(luò)層是實(shí)現(xiàn)一個路由生成與路由選擇．

2 編碼在WSNs 的可行性分析

WSNs 的部署特點(diǎn)，是高效的利用能量是否順利的重要一點(diǎn)．編碼技術(shù)增加了節(jié)點(diǎn)的計(jì)算能耗，因此我們應(yīng)該從節(jié)點(diǎn)能耗入手，探究編碼是否可以在節(jié)點(diǎn)能耗上能夠占一些優(yōu)勢． 硬件自身會有一線必須能耗之外，傳感器能量消耗模塊有傳感器模塊，無線通信模塊以及處理器模塊．處理器和傳感器消耗的能量逐漸變低，但是與通信模塊中的能耗卻越大．在2002 年的Mobicom 上，Deborah Estin 有說到了傳感器節(jié)能耗情況，如圖1 所示．

圖1 傳感器節(jié)點(diǎn)各部分能量消耗Fig．1 All parts of sensor node energy consumption

圖1 可以看出通信模塊耗能情況處理器模塊耗能情況的差別非常大．通信模塊有4 種工作狀態(tài)，包括空閑、睡眠、發(fā)送和接收，接收和空閑狀態(tài)耗能情況差不多大，在發(fā)送狀態(tài)的過程當(dāng)中耗能是最大的，但也還是比較接近發(fā)送狀態(tài)時候的能耗．也就是說節(jié)點(diǎn)在睡眠狀態(tài)外，其他時候都是保持很高的能量消耗．使用編碼時，若能夠在保證可靠性又減少數(shù)據(jù)量的傳輸就能夠節(jié)約很多能量． 傳感器能耗包括通信距離能耗，也包括了硬件本身的必須的能耗．

上式中α 代表晶體磁震蕩的能耗，E代表傳感器節(jié)點(diǎn)的總能耗，β 表示放大器因子，n是衰減因子，d是通信距離．βdn就是距離能耗，E確實(shí)與d成指數(shù)關(guān)系，α 消耗的能量遠(yuǎn)大于βdn，WSNs 中的節(jié)點(diǎn)發(fā)射功率不大．Athero s 提供下面這個能量模型參數(shù)

很好的說明了這點(diǎn)．

如表1 可以看出發(fā)射功率占所消耗總功率的百分較小，8% 都沒有超過． Martin Haenggi 和 Daniele Puccinelli 還使用MicaZ 和Mica2 節(jié)點(diǎn)對此進(jìn)行了周密細(xì)致的實(shí)驗(yàn)進(jìn)行驗(yàn)證，如圖2 所示．

表1 Atheros2004 Tri－mode chipset 能耗參數(shù)Tab．1 Energy consumption parameters of Atheros2004 Tri－mode chipset

如 圖3 所示，發(fā)射功率為10 dBm，總功率約為18． Sd-Bm，所耗的能耗在1．4%～14%范圍之間．證明了WSNs 在距離增加后能耗并沒有增加多少，卻是節(jié)點(diǎn)數(shù)目和能耗是一個正比關(guān)系，在保證可靠性前提下，極短步跳對節(jié)能并無其他好的地方，反而會增加了傳感器網(wǎng)絡(luò)的能耗，還會干擾影響通信過程中的質(zhì)量．

圖2 節(jié)點(diǎn)總功耗與發(fā)射功率的關(guān)系Fig．2 The relationship between node total power consumption and transmission power

3 典型噴泉碼(Raptor 碼)實(shí)現(xiàn)原理

3．1 典型噴泉碼(Raptor 碼)預(yù)編碼原理

如果經(jīng)LT 譯碼出的數(shù)據(jù)包是由另一種編碼方式實(shí)現(xiàn)，加上使用該方式譯碼可能會有較高的概率將原數(shù)據(jù)包譯碼出來．Raptor 碼中預(yù)編碼思想就是這么被提出來了，用有比率的糾錯碼先對數(shù)據(jù)編碼，這里得到的冗余校驗(yàn)數(shù)據(jù)當(dāng)成LT 碼的輸入．預(yù)編碼所使用的碼種是異或運(yùn)算，與以往的區(qū)別就在于這個編碼有無比率．以往的LT 碼是無比率碼，源數(shù)據(jù)端得到編碼序列有些是無限的;另外預(yù)編碼正常是用Tornado 碼等這些有比率碼，根據(jù)給定的度分布生成的校驗(yàn)節(jié)點(diǎn)數(shù)目是一個確定數(shù)． Tornado 是非正則的LDPC 碼，分布序列為Heavy－Tail/Possion 分布，出度和入度各自服從一個度分布是其一大特點(diǎn)，出度即數(shù)據(jù)源節(jié)點(diǎn)的度，入度即編碼后校驗(yàn)節(jié)點(diǎn)的度．如下圖3 所示．

設(shè)E 為編碼二分圖的總邊數(shù)，編碼冗余度為β，k為左節(jié)點(diǎn)數(shù)．αr為校驗(yàn)節(jié)點(diǎn)的平均入度數(shù)，ai為變量節(jié)點(diǎn)的平均出度數(shù)，λi為與度為i的變量節(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)之和與總邊數(shù)E的比，dl和dr分別為變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的最大度數(shù)，ρi為與度為i的校驗(yàn)節(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)之和與總邊數(shù)E的比，D為一正整數(shù)．根據(jù)定義的這些變量，可以得出如下式子:

則Tornado 碼的度分布如下:

Tornado 碼的編碼與譯碼復(fù)雜度是一樣的，同樣是與邊的個數(shù)成比，可得節(jié)點(diǎn)數(shù)的為O(ln(D)+ 3)，編譯復(fù)雜度就為O(k(ln(D)+3))．

圖3 LDPC 碼中入度與出度Fig．3 The degree and the degree of LDPC code

3．2 弱LT 碼的度分布

Raptor 碼還包括弱LT 碼編碼過程，弱LT 碼編碼的原理與一般的LT 編碼完全一樣，不一樣的地方就是弱LT 碼的度分布設(shè)計(jì)目的不是成功解碼所有源數(shù)據(jù)，而是以比較高的效率解碼約95%左右的源數(shù)據(jù)，這里對弱LT 碼的度分布進(jìn)行探究．

Shokrollahi 之前有關(guān)Raptor 碼的文章里，有說了經(jīng)典的弱LT 碼度分布，本課題只涉及該度分布使用，這里也就不具體證明和分析，只給這個度分布．

設(shè)Raptor 碼的無效比率1 +ε ，弱LT 碼的度分布μ(i)，可以有如下式子:

4 噴泉碼編解碼算法實(shí)現(xiàn)的數(shù)據(jù)收集協(xié)議

4．1 現(xiàn)有的Raptor 碼分布式實(shí)現(xiàn)方案

Raptor 碼編碼由弱LT 碼編碼過程和預(yù)編碼過程來實(shí)現(xiàn)，Raptor 碼將這兩個過程作為相互獨(dú)立階段，也就是說實(shí)現(xiàn)分布式的預(yù)編碼之后再來實(shí)現(xiàn)LT 碼．本課題考慮的場景為n個節(jié)點(diǎn)中有k個節(jié)點(diǎn)，課題中Raptor 碼方案是將預(yù)編碼當(dāng)成獨(dú)立階段來進(jìn)行，如圖4 所示．

4．2 基于分布式Raptor 碼的數(shù)據(jù)收集協(xié)議

以包為中心的Raptor 碼分布式實(shí)現(xiàn)，進(jìn)一步探究以包為中心的編碼方法之后，較簡易的在分布式中實(shí)現(xiàn)Raptor 編碼．Raptor 編碼中源數(shù)據(jù)節(jié)點(diǎn)是弱LT 編碼的輸入時的一個LT 編碼過程，這里把編碼包分類為不需要進(jìn)行預(yù)編碼直接進(jìn)行弱LT 編碼，和先進(jìn)行預(yù)編碼后再弱LT 編碼兩大類別．

圖4 Raptor 碼預(yù)編碼現(xiàn)有的分布式實(shí)現(xiàn)Fig．4 Distributed implementation of raptor code precoding

圖5 以包為中心的Raptor 碼分布式實(shí)現(xiàn)Fig．5 Distributed implementation of packages centered raptor code

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

本課題利用加州大學(xué)伯克利分校開發(fā)的基于構(gòu)件的開放源代碼TinyOS 操作系統(tǒng)．TinyOS 是專為WSNs 設(shè)計(jì)的這樣一個系統(tǒng)，在實(shí)現(xiàn)快速更新的同時能夠讓存儲器限制的代碼長度減?。?dāng)?shù)據(jù)包的設(shè)計(jì)如下所示:

6 結(jié)語

本課題主要是對噴泉碼技術(shù)在無線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)目尚行蕴骄浚到y(tǒng)設(shè)計(jì)方案和模型設(shè)計(jì)了噴泉碼編解碼算法． 以噴泉碼中的Raptor 碼為例，進(jìn)行深入的探究．在實(shí)驗(yàn)室科研支持下，本課題探究了線傳感器網(wǎng)絡(luò)中噴泉碼技術(shù)的實(shí)現(xiàn)原理，總結(jié)了基于分布式噴泉碼的數(shù)據(jù)收集技術(shù)研究動態(tài)．實(shí)驗(yàn)結(jié)果表明:合理的參數(shù)，該算法是可以有效改善譯碼的成功率．另外新方案在噴泉碼無線傳感器網(wǎng)絡(luò)中的編解碼速度能否比其他算法編解碼速度更有優(yōu)勢等還需后續(xù)進(jìn)一步探究．

圖6 Raptor 碼編碼流程Fig．6 Process of raptor code coding

［1］ 段桂華，王偉平，王建新，等．一種基于多路徑網(wǎng)絡(luò)編碼的匿名通信機(jī)制［J］．軟件學(xué)報，2010(9):112－136．

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

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

［4］ 胡世文，華蓓．基于Bloom 過濾器改進(jìn)的GrowthCodes［J］．計(jì)算機(jī)工程，2009，35(11):65－67．

［5］ 孫利民，李建中，陳渝，等．無線傳感器網(wǎng)絡(luò)［M］．北京:清華大學(xué)出版社，2005:16－23．

［6］ 洪鋒，褚紅偉，金宗科，等．無線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進(jìn)展綜述［J］．計(jì)算機(jī)研究與發(fā)展，2010，47(增刊):81－87．

［7］ 何李石．無線傳感器網(wǎng)絡(luò)基于數(shù)字噴泉碼的數(shù)據(jù)交換策略研究［M］．杭州:杭州電子科技大學(xué)出版社，2012:20－30．

［8］ 陳月云，劉偉．基于新型隨機(jī)度分布的壓縮噴泉碼［J］．電了信息學(xué)報，2012，84(5):1185－1190．

［9］ 肖文顯，劉震，馬孝琴，等．無線傳感器網(wǎng)絡(luò)LEACH 路由協(xié)議研究［J］．河南科技學(xué)院學(xué)報:自然科學(xué)版，2012，40(1):93－98．