基于LT噴泉碼的WSNs抗WLAN干擾的實(shí)驗(yàn)研究

楊 凱，施偉斌，呂 濤

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

目前，無(wú)線傳感器網(wǎng)絡(luò)（WSNs）主要基于IEEE 802.15.4協(xié)議，通常工作在2.4 GHz的ISM頻段，然而室內(nèi)環(huán)境中已有的大量基于IEEE 802.11協(xié)議的無(wú)線局域網(wǎng)（WiFi）設(shè)備也使用該頻段。有研究顯示［1］，當(dāng)WiFi網(wǎng)絡(luò)和WSNs部署在同一環(huán)境中，且WiFi信道與WSNs信道重疊時(shí)，WiFi通信會(huì)對(duì)WSNs產(chǎn)生較大干擾，嚴(yán)重影響WSNs的可靠性，在最壞的情況下，WSNs的丟包率將高于90%。

鑒于WSNs在同WiFi共存時(shí)丟包率較高，且通常MAC層使用CRC校驗(yàn)的原因，有損壞的數(shù)據(jù)包便會(huì)被簡(jiǎn)單丟棄。因此，在這種情況下，本文將無(wú)線信道看成類似BEC的二進(jìn)制刪除信道。在二進(jìn)制刪除信道上實(shí)現(xiàn)可靠傳輸?shù)耐ǔＷ龇ㄊ遣捎米詣?dòng)請(qǐng)求重傳（ARQ）的方式。該方法工作時(shí)雖然無(wú)需預(yù)先知道信道的刪除概率，但需要較多的反饋以致會(huì)產(chǎn)生反饋內(nèi)爆問(wèn)題［2］。還有一種方法是采用傳統(tǒng)的糾刪碼編碼方式，如RS糾刪碼［3］，但RS碼的碼率固定，而WiFi無(wú)線信道鏈路質(zhì)量動(dòng)態(tài)變化的特性使得發(fā)送端無(wú)法預(yù)先確定信道的刪除概率，從而無(wú)法確定使用RS碼的發(fā)送端的碼率。RS碼編解碼算法復(fù)雜，不適宜在資源有限的傳感器節(jié)點(diǎn)上實(shí)現(xiàn)。噴泉碼是一種無(wú)碼率碼，即發(fā)送端可以對(duì)原始信息源源不斷地編碼。只要接收端收到足夠的編碼信息就可以恢復(fù)出原信息。相比ARQ的反饋重傳和RS碼需根預(yù)先據(jù)信道刪除情況而確定固定碼率的方式，顯然噴泉碼的靈活性更大，能夠適應(yīng)WiFi信道多變時(shí)的數(shù)據(jù)傳輸。

1 LT碼的編譯碼算法

1998年，Luby M和Byers J等人首次提出了數(shù)字噴泉碼的概念。LT［4］碼和 Raptor［5］碼是目前典型的 2 種實(shí)用噴泉碼。鑒于Raptor碼需經(jīng)過(guò)預(yù)編碼，且算法復(fù)雜較大，考慮到WSNs中傳感器節(jié)點(diǎn)運(yùn)算能力有限，本文使用LT碼來(lái)設(shè)計(jì)并實(shí)現(xiàn)可靠傳輸協(xié)議。

1.1 噴泉碼的基本思想

源端無(wú)限制地隨機(jī)從待發(fā)送的符號(hào)（symbol）中選擇部分符號(hào)進(jìn)行異或編碼，然后發(fā)送出去，用戶只要接收到一定數(shù)量的編碼符號(hào)，即可成功恢復(fù)源端發(fā)送的符號(hào)信息，若不能全部恢復(fù)，則繼續(xù)接收至所有符號(hào)都恢復(fù)為止。

1.2 度與度分布函數(shù)的定義

假設(shè)現(xiàn)有K個(gè)符號(hào)（symbol）待發(fā)送。這里每個(gè)符號(hào)可以是1 bit，也可以是一個(gè)數(shù)據(jù)包（packet）。由于實(shí)驗(yàn)中采用的是包級(jí)別的LT編碼，所以，本文的符號(hào)特指數(shù)據(jù)包。

定義1 度（d）:生成一個(gè)LT編碼包所需的原始數(shù)據(jù)包的個(gè)數(shù)。

定義2 度分布函數(shù)（ρ（d））:對(duì)于所有的d，ρ（d）表示該LT編碼包中出現(xiàn)度為d的概率。

1.3 LT碼的編碼算法

1）從度分布函數(shù)ρ（d）中隨機(jī)選取LT編碼數(shù)據(jù)包的度d。

2）等概率地從K個(gè)原始數(shù)據(jù)包中隨機(jī)選取d個(gè)不同的原始數(shù)據(jù)包。

3）將這d個(gè)原始數(shù)據(jù)包互相異或產(chǎn)生一個(gè)LT編碼包。以圖1為例，從LT度分布函數(shù)中按照概率分布，某次恰取得d=3，然后從K個(gè)原始數(shù)據(jù)包中等概率地選取3個(gè)，這里是t1，t3，tK，接著將這3個(gè)數(shù)據(jù)包互相異或就得到了一個(gè)LT數(shù)據(jù)包。

4）重復(fù)步驟（1），（2），（3），N次得到N個(gè)編碼包。

上述編碼過(guò)程非常簡(jiǎn)單，關(guān)鍵是度分布函數(shù)的設(shè)計(jì)，具體設(shè)計(jì)方法參見(jiàn)文獻(xiàn)［4］。

圖1 某個(gè)LT編碼包的生成Fig 1 Generation of a LT encoding packet

1.4 LT碼的譯碼2種算法

1）高斯消元（Gaussian elimination）算法［6］

高斯消元法適用于所有噴泉嗎的解碼，它在數(shù)學(xué)上實(shí)際就是解線性方程組。LT碼解碼端的任務(wù)就是從T=GS中通過(guò)矩陣求逆恢復(fù)出S矩陣，這里S是原始數(shù)據(jù)包矩陣，T表示收到的LT編碼包的矩陣。原始數(shù)據(jù)包和LT編碼包的關(guān)系可用B×K的生成矩陣G來(lái)表示，這里K是原始數(shù)據(jù)包的個(gè)數(shù)，N是發(fā)送端生成的LT編碼包的個(gè)數(shù)。若矩陣滿秩，則譯碼成功;否則，不能夠恢復(fù)原始數(shù)據(jù)包，那么就需要接收更多的LT編碼包。

2）置信傳遞（belief propagation）算法

a.根據(jù)LT編碼包和原始數(shù)據(jù)包的對(duì)應(yīng)關(guān)系建立二分圖。

b.在譯碼的每一階段，都在LT編碼包集合中尋找度為1的包，顯然，這些LT編碼包對(duì)應(yīng)相連的原始數(shù)據(jù)包可以直接譯出。

c.譯碼器將每一個(gè)譯出的原始數(shù)據(jù)包與所有跟它相連的LT編碼包相異或，異或后的值覆蓋對(duì)應(yīng)LT編碼包的以前的值，同時(shí)刪去這個(gè)譯出的原始數(shù)據(jù)和對(duì)應(yīng)的LT編碼包的聯(lián)系（二分圖的邊），從而使得這些編碼包的度數(shù)減1，這樣就會(huì)產(chǎn)生新的度數(shù)為1的編碼包。

d.重復(fù)上述過(guò)程（b），（c），直到譯碼結(jié)束或者沒(méi)有度數(shù)為1的編碼包，迭代過(guò)程停止。如果所有LT編碼包被成功恢復(fù)，則譯碼成功;否則，譯碼失敗。

以上2種譯碼算法各有優(yōu)缺點(diǎn):GE算法譯碼復(fù)雜度為O（K3）pj，復(fù)雜度較高，但只要G矩陣滿秩，必然可以譯碼成功。由于度分布函數(shù)的精細(xì)設(shè)計(jì)，使得G矩陣是稀疏矩陣，所以，BP算法顯然比GE算法復(fù)雜度低，但BP譯碼過(guò)程的延續(xù)需要每一步都存在度為1的LT編碼包，故即使生成矩陣G是滿秩的，采用BP譯碼也可能造成譯碼失敗?？紤]到TinyOS系統(tǒng)定義的數(shù)據(jù)包的data部分最大為28個(gè)字節(jié)，故采用GE算法的復(fù)雜度可以接受，同時(shí)，采用GE算法的譯碼成功率又比BP算法要高。所以，設(shè)計(jì)的LT噴泉碼的譯碼采用高斯消元算法。

2 WSNs中實(shí)現(xiàn)LT噴泉碼的具體問(wèn)題

2.1 LT噴泉碼度分布函數(shù)的選取

傳統(tǒng)的LT噴泉碼主要用于大數(shù)據(jù)包或大文件的編碼，以保持很好的統(tǒng)計(jì)特性，所以，現(xiàn)有的較成熟得度分布函數(shù)［4］:全“1”分布、理想孤波分布、均勻分布和魯棒孤波分布均不適用于以短數(shù)據(jù)包通信的WSNs中。

通過(guò)研究比較和實(shí)驗(yàn)仿真，本文采用意大利普渡大學(xué)Rossi Michele設(shè)計(jì)的度分布函數(shù)［7］，如表1所示。

2.2 LT噴泉碼生成矩陣的重構(gòu)

當(dāng)接收端使用收到的LT編碼包來(lái)恢復(fù)原始數(shù)據(jù)包時(shí)，需要知道每個(gè)LT編碼包的度和該LT編碼包究竟是由哪幾個(gè)原始數(shù)據(jù)包異或而成的，其實(shí)就是重構(gòu)發(fā)送端的生成矩陣G。顯然，將發(fā)送端的生成矩陣G整體發(fā)送給接收端一方面增加了網(wǎng)絡(luò)負(fù)載，另一方面由于受無(wú)線信道干擾，有些LT編碼包會(huì)被破壞，這樣接收端要從整個(gè)G中選擇收到的LT編碼包中獲得上述信息，增加了譯碼的復(fù)雜度。

表1 采用的度分布函數(shù)Tab 1 Adopted degree distribution function

本文采用的方法是:在收發(fā)兩端采用相同的隨機(jī)數(shù)生成器，且將隨機(jī)數(shù)種子跟隨LT編碼包一起由發(fā)送端發(fā)送出去，接收端接收到編碼包后取出其中的種子放入自己的隨機(jī)數(shù)生成器中，這樣就又重新知道了收到的該LT編碼包究竟是由哪幾個(gè)原始數(shù)據(jù)包異或而成的，循環(huán)往復(fù)即可重構(gòu)出生成矩陣G。

2.3 LT編碼包結(jié)構(gòu)

本文所進(jìn)行的實(shí)驗(yàn)基于TinyOS—2.x操作系統(tǒng)，其幀結(jié)構(gòu)message_t由包頭、數(shù)據(jù)區(qū)、包尾、元數(shù)據(jù)四部分構(gòu)成，其中主要設(shè)置的是數(shù)據(jù)區(qū)部分。LT編碼包結(jié)構(gòu)如圖2所示。

圖2 LT編碼包結(jié)構(gòu)Fig 2 Structure of LT encoding packet

數(shù)據(jù)區(qū)的前2個(gè)字節(jié)用于存放隨機(jī)數(shù)種子，之后的負(fù)載區(qū)域的25個(gè)字節(jié)是根據(jù)隨機(jī)選取的度數(shù)而將某幾個(gè)源消息包異或而成的。

3 WSNs中基于LT噴泉碼的單跳信息分發(fā)協(xié)議

3.1 基本思想

發(fā)送節(jié)點(diǎn)源源不斷地發(fā)送LT編碼包，各個(gè)接收節(jié)點(diǎn)譯碼成功后均發(fā)送停止消息，發(fā)送節(jié)點(diǎn)收到所有鄰居節(jié)點(diǎn)的停止消息后，則停止發(fā)送LT編碼包。

3.2 4 種消息

1）ADV消息:由發(fā)送節(jié)點(diǎn)發(fā)出該消息，用于通知鄰居的接收節(jié)點(diǎn)準(zhǔn)備接收文件;

2）REQ消息:由接收節(jié)點(diǎn)廣播該消息，以告知發(fā)送節(jié)點(diǎn)本節(jié)點(diǎn)已準(zhǔn)備好接收;

3）DATA消息:由發(fā)送節(jié)點(diǎn)廣播該消息，該消息包含將源數(shù)據(jù)包經(jīng)過(guò)LT編碼后的編碼包;

4）STOP消息:由接收節(jié)點(diǎn)廣播該消息，告知發(fā)送端本節(jié)點(diǎn)已成功解碼。

3.3 系統(tǒng)工作過(guò)程

系統(tǒng)開(kāi)始，發(fā)送節(jié)點(diǎn)廣播ADV消息，通知鄰居的接收節(jié)點(diǎn)準(zhǔn)備接收文件。ADV消息中包含此次傳輸?shù)奈募拇笮?。?dāng)接收節(jié)點(diǎn)收到發(fā)送節(jié)點(diǎn)的ADV消息后，廣播REQ消息，以告知發(fā)送節(jié)點(diǎn)本節(jié)點(diǎn)已準(zhǔn)備好接收 DATA消息。當(dāng)發(fā)送節(jié)點(diǎn)收到所有鄰居節(jié)點(diǎn)的REQ消息后，將源數(shù)據(jù)包經(jīng)過(guò)LT編碼后廣播出去，每一個(gè)LT編碼包對(duì)應(yīng)一個(gè)DATA消息。當(dāng)接收節(jié)點(diǎn)收到足夠多的DATA消息而解碼成功后，須廣播STOP消息，告知發(fā)送端本節(jié)點(diǎn)已成功解碼，不再需要LT編碼包。當(dāng)發(fā)送節(jié)點(diǎn)收到所有鄰居節(jié)點(diǎn)的STOP消息后，表明所有接收節(jié)點(diǎn)已成功恢復(fù)源數(shù)據(jù)，則發(fā)送端停止發(fā)送DATA消息，系統(tǒng)停止。

整個(gè)節(jié)點(diǎn)程序流程圖如圖3所示。

圖3 LT噴泉碼的單跳信息分發(fā)協(xié)議流程圖Fig 3 Flow chart of single-hop information distribution protocol of LT fountain codes

其中，時(shí)間段T表示數(shù)據(jù)包往返收發(fā)兩端的最長(zhǎng)時(shí)間，從發(fā)送端成功發(fā)送出ADV消息開(kāi)始計(jì)時(shí)。N為接收節(jié)點(diǎn)個(gè)數(shù)，K為源數(shù)據(jù)包的個(gè)數(shù)，ε為譯碼開(kāi)銷。

4 實(shí)驗(yàn)方法

實(shí)驗(yàn)的主要目的是測(cè)試WSNs中基于LT噴泉碼的單跳信息分發(fā)協(xié)議能否正常工作和工作性能。以往很多研究都是采用仿真的方法測(cè)試LT噴泉碼的性能和效果［8］，但仿真測(cè)試不能模擬環(huán)境中存在的各種干擾，尤其是WLAN鏈路質(zhì)量的動(dòng)態(tài)變化會(huì)造成不同的干擾影響。

4.1 實(shí)驗(yàn)平臺(tái)與環(huán)境

實(shí)驗(yàn)系統(tǒng)的硬件由8個(gè)以CC2430為核心的WSNs節(jié)點(diǎn)，一個(gè)網(wǎng)關(guān)板和一臺(tái)PC機(jī)構(gòu)成。節(jié)點(diǎn)軟件采用TinyOS系統(tǒng)的NesC語(yǔ)言開(kāi)發(fā)，上位機(jī)軟件采用串口通信程序。

實(shí)驗(yàn)在6.3 m×5.7 m的實(shí)驗(yàn)室內(nèi)進(jìn)行。節(jié)點(diǎn)分布如圖4所示。其中1#節(jié)點(diǎn)是發(fā)送節(jié)點(diǎn)，通過(guò)串口與主機(jī)相連，其余節(jié)點(diǎn)均是接收節(jié)點(diǎn)。2#和7#點(diǎn)旁邊各有一臺(tái)主機(jī)，4#節(jié)點(diǎn)附近是無(wú)線路由器。

圖4 實(shí)驗(yàn)室節(jié)點(diǎn)分布圖Fig 4 Node distribution in lab

實(shí)驗(yàn)室無(wú)線路由器固定占用遵從IEEE 802.11 b/g標(biāo)準(zhǔn)的11信道。根據(jù)WSNs使用的信道和WLAN使用的信道是否重疊，將實(shí)驗(yàn)測(cè)試條件分為2種:

條件 1:WSNs使用 11信道，從圖 5可知［9］，此時(shí)，WSNs和WLAN使用的信道無(wú)重疊。

條件2:WSNs使用信道22，從圖5可知，此時(shí)，接近無(wú)線路由器11信道的中心頻率，即WSNs和WLAN使用的信道重疊。

圖5 IEEE 802.15.4 和 IEEE 802.11b/g 在2.4 GHz頻段的頻率范圍Fig 5 Frequency range of IEEE 802.15.4 and IEEE 802.11 b/g in 2.4 GHz band

4.2 實(shí)驗(yàn)步驟

首先，將相同的TinyOS源程序燒寫(xiě)到所有節(jié)點(diǎn)上，節(jié)點(diǎn)通過(guò)判斷自身的節(jié)點(diǎn)號(hào)是否為1來(lái)選擇到底是發(fā)送還是接收文件。

然后，將連接節(jié)點(diǎn)1的主機(jī)通過(guò)串口通信程序向1#節(jié)點(diǎn)發(fā)送一個(gè)800字節(jié)的文件。1#節(jié)點(diǎn)收到該文件后立即開(kāi)始廣播ADV消息。

接著，如果是在環(huán)境1中進(jìn)行實(shí)驗(yàn)，省略這一步。如果是在環(huán)境2中進(jìn)行實(shí)驗(yàn)，則在圖4中3臺(tái)主機(jī)上通過(guò)WLAN互傳大小為2 G左右的大文件。文件傳輸速度為2～3 Mbps。

最后，觀察節(jié)點(diǎn)板的黃燈是否閃爍，若閃爍，則代表本節(jié)點(diǎn)已成功解碼，恢復(fù)出源數(shù)據(jù);反之，則沒(méi)有。還可以將每一個(gè)節(jié)點(diǎn)通過(guò)串口連接到主機(jī)上，通過(guò)串口通信程序顯示本節(jié)點(diǎn)的一系列評(píng)價(jià)指標(biāo)。

4.3 實(shí)驗(yàn)結(jié)果分析

根據(jù)文獻(xiàn)［10］所得結(jié)論，將接收節(jié)點(diǎn)開(kāi)始解碼所需的包個(gè)數(shù)設(shè)置為36，幾乎可100%地保證解碼成功。因此，為提高解碼的成功率，減少多次解碼的時(shí)間浪費(fèi)，實(shí)驗(yàn)中，將該值設(shè)置為36。

在條件1中，實(shí)驗(yàn)結(jié)果如表2所示。

表2 條件1中實(shí)驗(yàn)結(jié)果圖Tab 2 Experimental results in condition 1

在條件2中，實(shí)驗(yàn)結(jié)果如表3所示。

表3 條件2中實(shí)驗(yàn)結(jié)果圖Tab 3 Experimental results in condition 2

對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以得到如下結(jié)論:

1）當(dāng)WSNs和WLAN使用的信道不重疊時(shí)，WSNs中的丟包率很小，約為0.34%。如表2所示，除5#節(jié)點(diǎn)收到的第36個(gè)包的序列號(hào)是37外，其余節(jié)點(diǎn)收到的第36個(gè)包的的序列號(hào)均為36。當(dāng)WSNs和WLAN使用的信道重疊，且WLAN使用的信道被大文件傳輸而占用時(shí)，WSNs中的丟包率很高，約為79%。

2）當(dāng)WSNs和WLAN使用的信道不重疊時(shí)，接收節(jié)點(diǎn)成功接收一個(gè)800字節(jié)的文件平均需要2.68 s。當(dāng)WSNs和WLAN使用的信道重疊，且WLAN使用的信道被大文件傳輸而占用時(shí)，接收節(jié)點(diǎn)成功接收一個(gè)800字節(jié)的文件平均需要14.37s，相較于條件1中的3.17s大大增加;究其原因:一是由于條件2中WSNs的信道常被WLAN中傳輸?shù)奈募加?，?dǎo)致WSNs中的編碼包很難獲得信道;二是由于WSNs和WLAN同時(shí)使用信道時(shí)數(shù)據(jù)包的碰撞而致WSNs發(fā)送的DATA包被破壞，故發(fā)送端需要傳輸更多的編碼包，這樣自然增加了通信時(shí)間。

3）根據(jù)表3中每個(gè)節(jié)點(diǎn)收到的第36個(gè)DATA包的序列號(hào)不同可知，雖然這些節(jié)點(diǎn)都處在同一實(shí)驗(yàn)室內(nèi)，但各節(jié)點(diǎn)所受干擾卻各有差異:2#節(jié)點(diǎn)受干擾最嚴(yán)重，發(fā)送節(jié)點(diǎn)發(fā)送給2#節(jié)點(diǎn)時(shí)丟包率達(dá)83%。3#節(jié)點(diǎn)受干擾影響最小，發(fā)送節(jié)點(diǎn)發(fā)送給3#節(jié)點(diǎn)時(shí)丟包率為72%。表3中2#，7#節(jié)點(diǎn)受干擾較重是因?yàn)樗鼈兣赃叺闹鳈C(jī)和1#節(jié)點(diǎn)的主機(jī)正在無(wú)線傳輸大文件，而3#和5#節(jié)點(diǎn)因?yàn)檫h(yuǎn)離無(wú)線路由器和主機(jī)，所以，受干擾也較小。

5 結(jié)束語(yǔ)

本文提出了一種采用糾刪碼——LT噴泉碼編碼來(lái)保證可靠傳輸?shù)姆椒ǎ⒃谝訡C2430為核心的平臺(tái)上設(shè)計(jì)并實(shí)現(xiàn)了基于LT噴泉碼的單跳信息分發(fā)協(xié)議。該方法在有較強(qiáng)WiFi干擾的情況下可以正常工作，實(shí)現(xiàn)大數(shù)據(jù)量的可靠傳輸。

［1］Sikora A，Groza V F.Coexistence of IEEE 802.15.4 with other systems in the 2.4 GHz-ISM-band［C］//Proceedings of the IEEE Instrumentation ＆ Measurement Technology Conference，Ottawa，Canada，2005:1786-1791.

［2］Nonnenmacher J，Biersack E W，Towsley D.Parity-based loss recovery for reliable multicast transmission［J］.IEEE/ACM Trans on Networking，1998，6（4）:349-361.

［3］Reed I S，Solomon G.Polynomial codes over certain finite fields［J］.Journal of the Society for Industrial and Applied Mathematics，1960，8（2）:300-304.

［4］Luby M.LT codes［C］//Proc of the 43rd Annual IEEE Symposium on Foundation of Computer Science，Washington DC，USA，2002:271-280.

［5］Shokrollahi A.Raptor codes［J］.IEEE Transactions on Information Theory，2006，52（6）:2551-2567.

［6］Pishro-Nik H，F(xiàn)ekrii F.On decoding of low density parity-check codes over binary erasure channel［J］.IEEE Transactions on Information Theory，2004，50（3）:439-454.

［7］Rossi M，Zanca G，Stabellini L，et al.SYNAPSE:A network reprogramming protocol for wireless sensor networks using fountain codes［C］//Proc of IEEE Comm Soc Conf on Sensor，Mesh and Ad Hoc Comm and Networks（SECON），San Francisco，USA，2008:188-196.

［8］劉 惠，李曉軍，杜軍朝，等.基于LT噴泉碼的無(wú)線傳感器網(wǎng)絡(luò)信息分發(fā)協(xié)議性能評(píng)價(jià)［J］.微電子學(xué)與計(jì)算機(jī)，2010，27（8）:100-102.

［9］Musaloiu E R，Terzis A.Minimising the effect of WiFi，interference in 802.15.4 wireless sensor networks［J］.International Journal of Sensor Networks，2007，3（1）:43-54.

［10］Rossi M，Bui N，Zanca G，et al.SYNAPSE++:Code dissemination in wireless sensor networks using fountain codes［J］.IEEE Transactions on Mobile Computing，2010，9（12）:1749-1765.