張亞昕+劉華

收稿日期：2013-09-17

作者簡(jiǎn)介：張亞昕（1978—），女，河南新鄭人，講師，碩士，研究方向：數(shù)據(jù)挖掘，無線傳感網(wǎng)絡(luò)。

文章編號(hào)：1003-6199(2014)02-0141-04

摘 要：無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目龐大，能量消耗大，傳感器節(jié)點(diǎn)的計(jì)算和存儲(chǔ)能力有限，網(wǎng)絡(luò)丟包率較為嚴(yán)重。為了設(shè)計(jì)節(jié)能可靠的網(wǎng)絡(luò)協(xié)議，降低節(jié)點(diǎn)的能耗，在TinyOS網(wǎng)絡(luò)平臺(tái)上設(shè)計(jì)實(shí)現(xiàn)了基于LT碼的數(shù)據(jù)分發(fā)協(xié)議，在仿真環(huán)境TOSSIM上進(jìn)行了性能分析，仿真結(jié)果表明，基于LT碼的數(shù)據(jù)分發(fā)協(xié)議，更好的展示了LT碼的無比率特性，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃?，降低的網(wǎng)絡(luò)負(fù)載。



關(guān)鍵詞：LT碼；分發(fā)協(xié)議；無線傳感網(wǎng)絡(luò)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A



Based on the Analysis of LT Codes Performance Data Distribution Agreement



ZHANG Yaxin，LIU Hua

(Xi'an Railway Vocational and Technical College Department of electronic information，Xi'an,Shannxi 710014，China)

Abstract:wireless sensor network node number, energy consumption, limited computing and storage capacity of sensor nodes, network packet loss rate is more serious. In order to design of energy saving and reliable network protocol, reduce the energy consumption of nodes in TinyOS network platform design has realized the data distribution agreement based on LT codes, the performance analysis on the simulation environment TOSSIM, simulation results show that based on the data distribution agreement LT codes, better shows no ratio characteristics of LT codes, to improve the reliability of the network data transmission, reduce the network load.



Key words:LT codes;distribution agreement;wireless sensor network



1 引 言

近年來隨著無線傳感網(wǎng)絡(luò)飛速發(fā)展，其應(yīng)用范圍也逐漸從軍事應(yīng)用推廣到工業(yè)，醫(yī)療、農(nóng)業(yè)、環(huán)境監(jiān)測(cè)等領(lǐng)域［1］。由于無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目龐大,通訊能力較弱,并且傳感器節(jié)點(diǎn)的計(jì)算和存儲(chǔ)能力有限，使得網(wǎng)絡(luò)的丟包率較為嚴(yán)重,一般會(huì)達(dá)到10%甚至更高。因此為網(wǎng)絡(luò)提供可靠的傳輸和存儲(chǔ)機(jī)制成為了無線傳感網(wǎng)絡(luò)的一個(gè)基本問題。

比較簡(jiǎn)單的方法就是多次發(fā)送數(shù)據(jù)包，但這樣發(fā)包的數(shù)量會(huì)大大增加，并且也不能保證數(shù)據(jù)傳輸?shù)目煽啃?，同時(shí)還增加了網(wǎng)絡(luò)的能耗。另一種方法是采用請(qǐng)求重傳，即發(fā)送端發(fā)出的數(shù)據(jù)包丟失，接收端就會(huì)向發(fā)送端請(qǐng)求重新發(fā)送未接收到的數(shù)據(jù)包，若數(shù)據(jù)包再次丟失，發(fā)送端還要再次發(fā)送。在無線傳感網(wǎng)絡(luò)多使用廣播方式，該方法會(huì)增加網(wǎng)絡(luò)負(fù)載和傳輸延遲，如果丟包率稍大，大量的處罰數(shù)據(jù)包將可能造成整個(gè)網(wǎng)絡(luò)的癱瘓。還有一種文獻(xiàn)［2］提出了使用范德蒙德矩陣構(gòu)造RS糾刪碼［3］來提高數(shù)據(jù)的可靠傳輸,但糾刪碼運(yùn)算復(fù)雜度較高。噴泉碼(Fountain Codes)［4-6］是一種無比率碼。一般來說，噴泉碼是指原始數(shù)據(jù)分組像噴泉一樣生成任意數(shù)量的編碼分組 ，接收端只要收到足夠多任意組合的編碼分組，就可以通過譯碼以高概率成功恢復(fù)全部原始數(shù)據(jù)分組。這種性質(zhì)使得它能夠在信道多變情況下進(jìn)行數(shù)據(jù)傳輸，幾乎不受信道刪除率的影響?yīng)?-8］。

2 LT編譯碼原理

2.1 LT編碼

假設(shè)編碼器要編碼的數(shù)據(jù)文件被分為k個(gè)數(shù)據(jù)分組s1,s2,…,sk，編碼后生成的編碼分組為t1,t2,….tn。當(dāng)接收端收到一定數(shù)量的輸出數(shù)據(jù)后，就可以通過譯碼以高概率成功恢復(fù)全部原始數(shù)據(jù)分組。LT編碼過程如下（如圖1）：

圖1 LT編碼示意圖



1)按照度分布函數(shù)為每一個(gè)編碼分組隨機(jī)選取一個(gè)度d(d

SymbolcB@

k)，d的選擇由度概率分布函數(shù)ρ(d)決定;

2) 從k個(gè)原始數(shù)據(jù)分組中，等概地隨機(jī)選擇不同的d個(gè);

3) 將這d個(gè)原始數(shù)據(jù)分組進(jìn)行異或運(yùn)算，即得到一個(gè)編分組;

重復(fù)步驟1)、2)、3)即可源源不斷地產(chǎn)生編碼分組。

顯然LT碼編碼的前提是隨機(jī)度d的選擇，而度概率 ρ(d)是度分布函數(shù)設(shè)計(jì)的關(guān)鍵。既要保證編碼器輸出的任何一個(gè)編碼分組sk參與了編碼；又要盡量使編碼和譯碼過程異或的次數(shù)較少，保證譯碼能夠開始并持續(xù)下去。Luby在文獻(xiàn)［4］中提出理想孤波分布(Ideal Solition Distribution)，定義為：

ρ(d)=1kd=11d(d－1),d=2,3,…k(1)

對(duì)于這種度分布k個(gè)編碼分組的度的平均度值近似為ln k。但是，由于理想孤波分布度值選取是隨機(jī)的，造成在實(shí)際應(yīng)用中很不穩(wěn)定，稍有波動(dòng)就可能導(dǎo)致在譯碼時(shí)在某些點(diǎn)沒有度為1編碼分組出現(xiàn)，造成譯碼失敗。為了提高譯碼成功率，Luby在理想孤波分布之上進(jìn)行了改進(jìn)，提出了魯棒孤波分布(Robust Soliton distribution，RSD)：

τ(d)=sk1d d=1,2,3,…(k/s)－1sklog (s/δ)d=k/s0d＞k/s(2) 

將理想孤波分布ρ(?)與τ(?)相加，得到改進(jìn)后的度概率密度分布函數(shù)μ(d)：

μ(d)=ρ(d)+τ(d)Z (3)

計(jì)算技術(shù)與自動(dòng)化2014年6月

第33卷第2期張亞昕等：基于LT碼數(shù)據(jù)分發(fā)協(xié)議性能分析

其中c為大于0的常數(shù)，取值范圍為0,1，δ為譯碼失敗的概率。s=c?ln (k/δ)k表示編碼分組度為1的數(shù)目。

2.2 LT譯碼

開始時(shí)原始數(shù)據(jù)分組均未恢復(fù)，當(dāng)接收端收到一定數(shù)量的編碼分組后開始譯碼。譯碼器在每一步都利用部分已經(jīng)譯碼的數(shù)據(jù)在剩余的數(shù)據(jù)中解出一部分新的源數(shù)據(jù),如此不斷的反復(fù)迭代直到所有的數(shù)據(jù)都被恢復(fù)出來。譯碼過程如下：

1）根據(jù)已有的原始數(shù)據(jù)和編碼分組的對(duì)應(yīng)關(guān)系建立雙向圖；

2）任意選取一個(gè)度為1的編碼分組，如果存在,即可恢復(fù)與其相連的原始數(shù)據(jù)，并將該編碼分組從雙向圖中移除;如果不存在,則譯碼停止；

3）對(duì)已恢復(fù)的數(shù)據(jù),將其從其他參與異或的編碼分組中移除，從而使輸出數(shù)據(jù)的的度減1；

4）重復(fù)步驟2）和3）,直至所有數(shù)據(jù)都被恢復(fù),則譯碼成功；否則,譯碼失敗,需接收更多的編碼分組才能繼續(xù)譯碼。

3 LT碼數(shù)據(jù)分發(fā)協(xié)議的設(shè)計(jì)

在分析了LT碼編譯原理后，可知LT碼數(shù)據(jù)包的數(shù)量一般不受限制，但為了進(jìn)行LT編碼數(shù)據(jù)包數(shù)量、數(shù)據(jù)包號(hào)、每個(gè)包對(duì)應(yīng)的度需要知道。數(shù)據(jù)包結(jié)構(gòu)一般包括四部分：Head、Data、Footer、Dataelement。其中Data是主要部分，最大長(zhǎng)度為29個(gè)字節(jié)，如果接收方不知道發(fā)包數(shù)量和碼率,Data還要設(shè)置原始數(shù)據(jù)包數(shù)(Sour-num)和編碼后的數(shù)據(jù)包數(shù)(Codenum)。其余三部分與硬件相關(guān)。LT傳輸數(shù)據(jù)包結(jié)構(gòu)如圖2所示：

圖2 LT碼的數(shù)據(jù)包結(jié)構(gòu)圖

由于LT碼的碼率無關(guān)性，發(fā)送端產(chǎn)生的編碼序列可以是無限的，接收端只要收到足夠的編碼分組就可以恢復(fù)全部原始數(shù)據(jù)，不需要關(guān)心中間節(jié)點(diǎn)之間的鏈路關(guān)系。一般為了減少能量消耗，縮短傳輸延遲，接收端只要成功譯碼，發(fā)送端將停止編碼。圖3是LT碼數(shù)據(jù)分發(fā)協(xié)議編解碼的具體過程:

Notations:

rec_pkt:receive queueε:decoding inefficiency factor

Information Dissemination Protocol Based LT Erasure Codes

Upon entering Encode Phase

if (TOS_NODE_ID == Sender) then 

call Encode() and Send()

end if

Upon entering Forward Phase

if(TOS_NODE_ID != Sender 

&& TOS_NODE_ID != Receiver) then

call Forward()

end if

Upon entering Decode Phase

if(TOS_NODE_ID ==Receiver) then

if( len(receive_packet) >=(1 +ε)*k) then 

call Decode()and flush rec_pkt

else

Store the message in rec_pkt

end if

end if

/*The following is for Encode*/

Encode()

See encoding process of LT codes in section 2

Decode()

See decoding process of LT codes in section 2

圖3 LT碼數(shù)據(jù)分發(fā)協(xié)議

其中Forward()的設(shè)計(jì)是關(guān)鍵，最容易實(shí)現(xiàn)的方法就是泛洪法，發(fā)送方不斷重復(fù)發(fā)送數(shù)據(jù)包，滿足不同的網(wǎng)絡(luò)丟包率，接收方也以同樣的方式轉(zhuǎn)發(fā)數(shù)據(jù)包。但該方法會(huì)增加網(wǎng)絡(luò)負(fù)載，因此設(shè)計(jì)盡量減少數(shù)據(jù)包的發(fā)送次數(shù)。但是對(duì)路由協(xié)議的效果不是很明顯。

4 性能仿真與分析

仿真實(shí)驗(yàn)環(huán)境采用TOSSIM［9］，數(shù)據(jù)分發(fā)協(xié)議是在TinyOS［10］平臺(tái)上實(shí)現(xiàn)的。在TOSSIM中可以設(shè)置無線傳感器網(wǎng)絡(luò)中每條鏈路的信噪比，用來模擬真實(shí)的無線傳感器網(wǎng)絡(luò)鏈路通信，TOSSIM提供的噪聲源來自真實(shí)噪聲，使仿真更接近現(xiàn)實(shí)。本文用來模擬的無線傳感網(wǎng)絡(luò)圖（如圖4）是隨機(jī)生成的，其中0節(jié)點(diǎn)用于分發(fā)數(shù)據(jù)，其余63個(gè)是轉(zhuǎn)發(fā)數(shù)據(jù)節(jié)點(diǎn)，接收端在收到編碼數(shù)據(jù)包后，首先檢查是否收到該包，若沒有收到則以相同的方式轉(zhuǎn)發(fā)，否則直接丟棄。接收端在收到數(shù)據(jù)包后，由于沒有相應(yīng)的應(yīng)答方式，故是否停止發(fā)送數(shù)據(jù)包完全由接收方控制。

圖4 模擬無線傳感器網(wǎng)絡(luò)圖

圖5所示，LT編碼數(shù)據(jù)包數(shù)對(duì)譯碼性能的影響。從圖中可以看到數(shù)據(jù)包數(shù)k為10000譯碼成功率比k為100時(shí)要高，所以只有數(shù)據(jù)包數(shù)量達(dá)到一定程度時(shí)，LT譯碼才能達(dá)到良好的性能，滿足一定的統(tǒng)計(jì)規(guī)律。

圖5 數(shù)據(jù)包數(shù)對(duì)LT譯碼性能的影響?yīng)オ?/p>

圖6所示發(fā)送數(shù)據(jù)包數(shù)為100的單跳網(wǎng)絡(luò)中，LT碼與RS糾刪碼的時(shí)間比較曲線。從圖中可見LT編解碼所需時(shí)間略長(zhǎng)于RS碼，但RS碼是有比率碼，編解碼基于矩陣的有限域運(yùn)算，數(shù)據(jù)量大時(shí)需將數(shù)據(jù)分塊編碼發(fā)送，運(yùn)算復(fù)雜度較高，突發(fā)事件時(shí)不能實(shí)時(shí)的改變碼率，LT碼則能適應(yīng)信道多變的情況，不受信道刪除率的影響。

圖7中給出了發(fā)送數(shù)據(jù)包數(shù)為100，網(wǎng)絡(luò)丟包率為25%，LT碼與RS糾刪碼的收包率比較曲線。從圖可見RS碼實(shí)際發(fā)送數(shù)據(jù)包數(shù)大于接收到的編碼包數(shù)時(shí)，由于編碼數(shù)據(jù)矩陣的不可逆性，因此解碼出的包數(shù)為0，收包率為0。只有發(fā)送數(shù)據(jù)包數(shù)小于接收到的包數(shù)時(shí)，RS碼才能解碼成功。LT碼中隨著發(fā)送數(shù)據(jù)報(bào)數(shù)的增收包率也會(huì)隨之增加，只要接收端收到足夠多的編碼分分組就能成功譯碼，且不受網(wǎng)絡(luò)好壞的影響。

圖6 LT碼的編解碼時(shí)間比較曲線

圖7 LT碼和RS碼的收包率比較曲線

5 結(jié) 論

本文研究了LT碼編譯碼原理，在TinyOS網(wǎng)絡(luò)操作平臺(tái)上設(shè)計(jì)并實(shí)現(xiàn)了在無線傳感網(wǎng)絡(luò)基于LT碼的數(shù)據(jù)分發(fā)協(xié)議。在單跳網(wǎng)絡(luò)中通過TOSSIM仿真實(shí)驗(yàn)，比較了LT碼與RS碼的編解碼時(shí)間和包接受率。仿真結(jié)果表明，RS碼運(yùn)算復(fù)雜度高，需要將數(shù)據(jù)分塊編碼發(fā)送，突發(fā)事件不能實(shí)時(shí)改變碼率。而基于LT碼的數(shù)據(jù)分發(fā)協(xié)議，更好的展示了LT碼的無比率特性，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

參考文獻(xiàn)

［1］ SONG W,WANG B,ZHOU Y B. Technology and application of wireless sensor network ［M］. Bei jing:Electronics Industrial Publisher, 2007:2-6.

［2］ HO T,KOETTER R，EDARD M M,D.Karger,and .Effros.The benefits of coding over routing in a randomized setting［C］// PaeifieoYokoharna.In Proc.IEEE ISIT.JaPan:2003: 227-234.

［3］ 王新梅,肖國(guó)鎮(zhèn).糾錯(cuò)碼-原理與方法［M］.西安:西安電子科技大學(xué)出版社,2001.

［4］ LUBY M.LTcodes［C］// in Proceedings of the ACM Symposium on Foundations of Computer Science . 2002:271-282.

［5］ JANSHID ABOUEI ，DAVID BROWN J,KONSTANTIONS N. Plataniotis. On the Energy Efficiency of LT Codes in Proactive Wireless Sensor Networks ［J］．IEEE Transactions On Signal Processing, 2011, 59(3):：1116-1127 ．

［6］ 朱宏杰.噴泉碼編譯碼技術(shù)與應(yīng)用研究［D］．北京：清華大學(xué),2008．

［7］ 慕建君,焦曉鵬,曹訓(xùn)志.數(shù)字噴泉碼及其應(yīng)用的研究進(jìn)展和發(fā)展［J］.電子學(xué)報(bào)2009,37(7):1571-1577.

［8］ BYERS J W,LUBY M,MITZENMACHERM.Adigital folultain approach to asynchronous reliable multicast［J］.IEEE Journal on Seleeted Areas in Conlnlunieations,2002,20(8):1528-1540.

［9］ LEVIS P,MADDENS，GAYD,POLASTRE J,SZEWCZYK R,WOOA,BREWER E,CULLERD. The emergence of networking abstractions and techniques in tinyos ［C］//Proceedings of the First USENIX/ACM Networked System Design and Implementation 2004:1-14.

［10］LEVIS P,LEEN,WELSHM,CULLERD.TOSSIM: Accurate and scalable simulation of entire tinyos applications ［C］// Proceedings of the 1st international conference on Embedded networked sensor system2003: 126-137.

3 LT碼數(shù)據(jù)分發(fā)協(xié)議的設(shè)計(jì)

在分析了LT碼編譯原理后，可知LT碼數(shù)據(jù)包的數(shù)量一般不受限制，但為了進(jìn)行LT編碼數(shù)據(jù)包數(shù)量、數(shù)據(jù)包號(hào)、每個(gè)包對(duì)應(yīng)的度需要知道。數(shù)據(jù)包結(jié)構(gòu)一般包括四部分：Head、Data、Footer、Dataelement。其中Data是主要部分，最大長(zhǎng)度為29個(gè)字節(jié)，如果接收方不知道發(fā)包數(shù)量和碼率,Data還要設(shè)置原始數(shù)據(jù)包數(shù)(Sour-num)和編碼后的數(shù)據(jù)包數(shù)(Codenum)。其余三部分與硬件相關(guān)。LT傳輸數(shù)據(jù)包結(jié)構(gòu)如圖2所示：

圖2 LT碼的數(shù)據(jù)包結(jié)構(gòu)圖

由于LT碼的碼率無關(guān)性，發(fā)送端產(chǎn)生的編碼序列可以是無限的，接收端只要收到足夠的編碼分組就可以恢復(fù)全部原始數(shù)據(jù)，不需要關(guān)心中間節(jié)點(diǎn)之間的鏈路關(guān)系。一般為了減少能量消耗，縮短傳輸延遲，接收端只要成功譯碼，發(fā)送端將停止編碼。圖3是LT碼數(shù)據(jù)分發(fā)協(xié)議編解碼的具體過程:

Notations:

rec_pkt:receive queueε:decoding inefficiency factor

Information Dissemination Protocol Based LT Erasure Codes

Upon entering Encode Phase

if (TOS_NODE_ID == Sender) then 

call Encode() and Send()

end if

Upon entering Forward Phase

if(TOS_NODE_ID != Sender 

&& TOS_NODE_ID != Receiver) then

call Forward()

end if

Upon entering Decode Phase

if(TOS_NODE_ID ==Receiver) then

if( len(receive_packet) >=(1 +ε)*k) then 

call Decode()and flush rec_pkt

else

Store the message in rec_pkt

end if

end if

/*The following is for Encode*/

Encode()

See encoding process of LT codes in section 2

Decode()

See decoding process of LT codes in section 2

圖3 LT碼數(shù)據(jù)分發(fā)協(xié)議

其中Forward()的設(shè)計(jì)是關(guān)鍵，最容易實(shí)現(xiàn)的方法就是泛洪法，發(fā)送方不斷重復(fù)發(fā)送數(shù)據(jù)包，滿足不同的網(wǎng)絡(luò)丟包率，接收方也以同樣的方式轉(zhuǎn)發(fā)數(shù)據(jù)包。但該方法會(huì)增加網(wǎng)絡(luò)負(fù)載，因此設(shè)計(jì)盡量減少數(shù)據(jù)包的發(fā)送次數(shù)。但是對(duì)路由協(xié)議的效果不是很明顯。

4 性能仿真與分析

仿真實(shí)驗(yàn)環(huán)境采用TOSSIM［9］，數(shù)據(jù)分發(fā)協(xié)議是在TinyOS［10］平臺(tái)上實(shí)現(xiàn)的。在TOSSIM中可以設(shè)置無線傳感器網(wǎng)絡(luò)中每條鏈路的信噪比，用來模擬真實(shí)的無線傳感器網(wǎng)絡(luò)鏈路通信，TOSSIM提供的噪聲源來自真實(shí)噪聲，使仿真更接近現(xiàn)實(shí)。本文用來模擬的無線傳感網(wǎng)絡(luò)圖（如圖4）是隨機(jī)生成的，其中0節(jié)點(diǎn)用于分發(fā)數(shù)據(jù)，其余63個(gè)是轉(zhuǎn)發(fā)數(shù)據(jù)節(jié)點(diǎn)，接收端在收到編碼數(shù)據(jù)包后，首先檢查是否收到該包，若沒有收到則以相同的方式轉(zhuǎn)發(fā)，否則直接丟棄。接收端在收到數(shù)據(jù)包后，由于沒有相應(yīng)的應(yīng)答方式，故是否停止發(fā)送數(shù)據(jù)包完全由接收方控制。

圖4 模擬無線傳感器網(wǎng)絡(luò)圖

圖5所示，LT編碼數(shù)據(jù)包數(shù)對(duì)譯碼性能的影響。從圖中可以看到數(shù)據(jù)包數(shù)k為10000譯碼成功率比k為100時(shí)要高，所以只有數(shù)據(jù)包數(shù)量達(dá)到一定程度時(shí)，LT譯碼才能達(dá)到良好的性能，滿足一定的統(tǒng)計(jì)規(guī)律。

圖5 數(shù)據(jù)包數(shù)對(duì)LT譯碼性能的影響?yīng)オ?/p>

圖6所示發(fā)送數(shù)據(jù)包數(shù)為100的單跳網(wǎng)絡(luò)中，LT碼與RS糾刪碼的時(shí)間比較曲線。從圖中可見LT編解碼所需時(shí)間略長(zhǎng)于RS碼，但RS碼是有比率碼，編解碼基于矩陣的有限域運(yùn)算，數(shù)據(jù)量大時(shí)需將數(shù)據(jù)分塊編碼發(fā)送，運(yùn)算復(fù)雜度較高，突發(fā)事件時(shí)不能實(shí)時(shí)的改變碼率，LT碼則能適應(yīng)信道多變的情況，不受信道刪除率的影響。

圖7中給出了發(fā)送數(shù)據(jù)包數(shù)為100，網(wǎng)絡(luò)丟包率為25%，LT碼與RS糾刪碼的收包率比較曲線。從圖可見RS碼實(shí)際發(fā)送數(shù)據(jù)包數(shù)大于接收到的編碼包數(shù)時(shí)，由于編碼數(shù)據(jù)矩陣的不可逆性，因此解碼出的包數(shù)為0，收包率為0。只有發(fā)送數(shù)據(jù)包數(shù)小于接收到的包數(shù)時(shí)，RS碼才能解碼成功。LT碼中隨著發(fā)送數(shù)據(jù)報(bào)數(shù)的增收包率也會(huì)隨之增加，只要接收端收到足夠多的編碼分分組就能成功譯碼，且不受網(wǎng)絡(luò)好壞的影響。

圖6 LT碼的編解碼時(shí)間比較曲線

圖7 LT碼和RS碼的收包率比較曲線

5 結(jié) 論

本文研究了LT碼編譯碼原理，在TinyOS網(wǎng)絡(luò)操作平臺(tái)上設(shè)計(jì)并實(shí)現(xiàn)了在無線傳感網(wǎng)絡(luò)基于LT碼的數(shù)據(jù)分發(fā)協(xié)議。在單跳網(wǎng)絡(luò)中通過TOSSIM仿真實(shí)驗(yàn)，比較了LT碼與RS碼的編解碼時(shí)間和包接受率。仿真結(jié)果表明，RS碼運(yùn)算復(fù)雜度高，需要將數(shù)據(jù)分塊編碼發(fā)送，突發(fā)事件不能實(shí)時(shí)改變碼率。而基于LT碼的數(shù)據(jù)分發(fā)協(xié)議，更好的展示了LT碼的無比率特性，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

參考文獻(xiàn)

［1］ SONG W,WANG B,ZHOU Y B. Technology and application of wireless sensor network ［M］. Bei jing:Electronics Industrial Publisher, 2007:2-6.

［2］ HO T,KOETTER R，EDARD M M,D.Karger,and .Effros.The benefits of coding over routing in a randomized setting［C］// PaeifieoYokoharna.In Proc.IEEE ISIT.JaPan:2003: 227-234.

［3］ 王新梅,肖國(guó)鎮(zhèn).糾錯(cuò)碼-原理與方法［M］.西安:西安電子科技大學(xué)出版社,2001.

［4］ LUBY M.LTcodes［C］// in Proceedings of the ACM Symposium on Foundations of Computer Science . 2002:271-282.

［5］ JANSHID ABOUEI ，DAVID BROWN J,KONSTANTIONS N. Plataniotis. On the Energy Efficiency of LT Codes in Proactive Wireless Sensor Networks ［J］．IEEE Transactions On Signal Processing, 2011, 59(3):：1116-1127 ．

［6］ 朱宏杰.噴泉碼編譯碼技術(shù)與應(yīng)用研究［D］．北京：清華大學(xué),2008．

［7］ 慕建君,焦曉鵬,曹訓(xùn)志.數(shù)字噴泉碼及其應(yīng)用的研究進(jìn)展和發(fā)展［J］.電子學(xué)報(bào)2009,37(7):1571-1577.

［8］ BYERS J W,LUBY M,MITZENMACHERM.Adigital folultain approach to asynchronous reliable multicast［J］.IEEE Journal on Seleeted Areas in Conlnlunieations,2002,20(8):1528-1540.

［9］ LEVIS P,MADDENS，GAYD,POLASTRE J,SZEWCZYK R,WOOA,BREWER E,CULLERD. The emergence of networking abstractions and techniques in tinyos ［C］//Proceedings of the First USENIX/ACM Networked System Design and Implementation 2004:1-14.

［10］LEVIS P,LEEN,WELSHM,CULLERD.TOSSIM: Accurate and scalable simulation of entire tinyos applications ［C］// Proceedings of the 1st international conference on Embedded networked sensor system2003: 126-137.

3 LT碼數(shù)據(jù)分發(fā)協(xié)議的設(shè)計(jì)

在分析了LT碼編譯原理后，可知LT碼數(shù)據(jù)包的數(shù)量一般不受限制，但為了進(jìn)行LT編碼數(shù)據(jù)包數(shù)量、數(shù)據(jù)包號(hào)、每個(gè)包對(duì)應(yīng)的度需要知道。數(shù)據(jù)包結(jié)構(gòu)一般包括四部分：Head、Data、Footer、Dataelement。其中Data是主要部分，最大長(zhǎng)度為29個(gè)字節(jié)，如果接收方不知道發(fā)包數(shù)量和碼率,Data還要設(shè)置原始數(shù)據(jù)包數(shù)(Sour-num)和編碼后的數(shù)據(jù)包數(shù)(Codenum)。其余三部分與硬件相關(guān)。LT傳輸數(shù)據(jù)包結(jié)構(gòu)如圖2所示：

圖2 LT碼的數(shù)據(jù)包結(jié)構(gòu)圖

由于LT碼的碼率無關(guān)性，發(fā)送端產(chǎn)生的編碼序列可以是無限的，接收端只要收到足夠的編碼分組就可以恢復(fù)全部原始數(shù)據(jù)，不需要關(guān)心中間節(jié)點(diǎn)之間的鏈路關(guān)系。一般為了減少能量消耗，縮短傳輸延遲，接收端只要成功譯碼，發(fā)送端將停止編碼。圖3是LT碼數(shù)據(jù)分發(fā)協(xié)議編解碼的具體過程:

Notations:

rec_pkt:receive queueε:decoding inefficiency factor

Information Dissemination Protocol Based LT Erasure Codes

Upon entering Encode Phase

if (TOS_NODE_ID == Sender) then 

call Encode() and Send()

end if

Upon entering Forward Phase

if(TOS_NODE_ID != Sender 

&& TOS_NODE_ID != Receiver) then

call Forward()

end if

Upon entering Decode Phase

if(TOS_NODE_ID ==Receiver) then

if( len(receive_packet) >=(1 +ε)*k) then 

call Decode()and flush rec_pkt

else

Store the message in rec_pkt

end if

end if

/*The following is for Encode*/

Encode()

See encoding process of LT codes in section 2

Decode()

See decoding process of LT codes in section 2

圖3 LT碼數(shù)據(jù)分發(fā)協(xié)議

其中Forward()的設(shè)計(jì)是關(guān)鍵，最容易實(shí)現(xiàn)的方法就是泛洪法，發(fā)送方不斷重復(fù)發(fā)送數(shù)據(jù)包，滿足不同的網(wǎng)絡(luò)丟包率，接收方也以同樣的方式轉(zhuǎn)發(fā)數(shù)據(jù)包。但該方法會(huì)增加網(wǎng)絡(luò)負(fù)載，因此設(shè)計(jì)盡量減少數(shù)據(jù)包的發(fā)送次數(shù)。但是對(duì)路由協(xié)議的效果不是很明顯。

4 性能仿真與分析

仿真實(shí)驗(yàn)環(huán)境采用TOSSIM［9］，數(shù)據(jù)分發(fā)協(xié)議是在TinyOS［10］平臺(tái)上實(shí)現(xiàn)的。在TOSSIM中可以設(shè)置無線傳感器網(wǎng)絡(luò)中每條鏈路的信噪比，用來模擬真實(shí)的無線傳感器網(wǎng)絡(luò)鏈路通信，TOSSIM提供的噪聲源來自真實(shí)噪聲，使仿真更接近現(xiàn)實(shí)。本文用來模擬的無線傳感網(wǎng)絡(luò)圖（如圖4）是隨機(jī)生成的，其中0節(jié)點(diǎn)用于分發(fā)數(shù)據(jù)，其余63個(gè)是轉(zhuǎn)發(fā)數(shù)據(jù)節(jié)點(diǎn)，接收端在收到編碼數(shù)據(jù)包后，首先檢查是否收到該包，若沒有收到則以相同的方式轉(zhuǎn)發(fā)，否則直接丟棄。接收端在收到數(shù)據(jù)包后，由于沒有相應(yīng)的應(yīng)答方式，故是否停止發(fā)送數(shù)據(jù)包完全由接收方控制。

圖4 模擬無線傳感器網(wǎng)絡(luò)圖

圖5所示，LT編碼數(shù)據(jù)包數(shù)對(duì)譯碼性能的影響。從圖中可以看到數(shù)據(jù)包數(shù)k為10000譯碼成功率比k為100時(shí)要高，所以只有數(shù)據(jù)包數(shù)量達(dá)到一定程度時(shí)，LT譯碼才能達(dá)到良好的性能，滿足一定的統(tǒng)計(jì)規(guī)律。

圖5 數(shù)據(jù)包數(shù)對(duì)LT譯碼性能的影響?yīng)オ?/p>

圖6所示發(fā)送數(shù)據(jù)包數(shù)為100的單跳網(wǎng)絡(luò)中，LT碼與RS糾刪碼的時(shí)間比較曲線。從圖中可見LT編解碼所需時(shí)間略長(zhǎng)于RS碼，但RS碼是有比率碼，編解碼基于矩陣的有限域運(yùn)算，數(shù)據(jù)量大時(shí)需將數(shù)據(jù)分塊編碼發(fā)送，運(yùn)算復(fù)雜度較高，突發(fā)事件時(shí)不能實(shí)時(shí)的改變碼率，LT碼則能適應(yīng)信道多變的情況，不受信道刪除率的影響。

圖7中給出了發(fā)送數(shù)據(jù)包數(shù)為100，網(wǎng)絡(luò)丟包率為25%，LT碼與RS糾刪碼的收包率比較曲線。從圖可見RS碼實(shí)際發(fā)送數(shù)據(jù)包數(shù)大于接收到的編碼包數(shù)時(shí)，由于編碼數(shù)據(jù)矩陣的不可逆性，因此解碼出的包數(shù)為0，收包率為0。只有發(fā)送數(shù)據(jù)包數(shù)小于接收到的包數(shù)時(shí)，RS碼才能解碼成功。LT碼中隨著發(fā)送數(shù)據(jù)報(bào)數(shù)的增收包率也會(huì)隨之增加，只要接收端收到足夠多的編碼分分組就能成功譯碼，且不受網(wǎng)絡(luò)好壞的影響。

圖6 LT碼的編解碼時(shí)間比較曲線

圖7 LT碼和RS碼的收包率比較曲線

5 結(jié) 論

本文研究了LT碼編譯碼原理，在TinyOS網(wǎng)絡(luò)操作平臺(tái)上設(shè)計(jì)并實(shí)現(xiàn)了在無線傳感網(wǎng)絡(luò)基于LT碼的數(shù)據(jù)分發(fā)協(xié)議。在單跳網(wǎng)絡(luò)中通過TOSSIM仿真實(shí)驗(yàn)，比較了LT碼與RS碼的編解碼時(shí)間和包接受率。仿真結(jié)果表明，RS碼運(yùn)算復(fù)雜度高，需要將數(shù)據(jù)分塊編碼發(fā)送，突發(fā)事件不能實(shí)時(shí)改變碼率。而基于LT碼的數(shù)據(jù)分發(fā)協(xié)議，更好的展示了LT碼的無比率特性，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

參考文獻(xiàn)

［1］ SONG W,WANG B,ZHOU Y B. Technology and application of wireless sensor network ［M］. Bei jing:Electronics Industrial Publisher, 2007:2-6.

［2］ HO T,KOETTER R，EDARD M M,D.Karger,and .Effros.The benefits of coding over routing in a randomized setting［C］// PaeifieoYokoharna.In Proc.IEEE ISIT.JaPan:2003: 227-234.

［3］ 王新梅,肖國(guó)鎮(zhèn).糾錯(cuò)碼-原理與方法［M］.西安:西安電子科技大學(xué)出版社,2001.

［4］ LUBY M.LTcodes［C］// in Proceedings of the ACM Symposium on Foundations of Computer Science . 2002:271-282.

［5］ JANSHID ABOUEI ，DAVID BROWN J,KONSTANTIONS N. Plataniotis. On the Energy Efficiency of LT Codes in Proactive Wireless Sensor Networks ［J］．IEEE Transactions On Signal Processing, 2011, 59(3):：1116-1127 ．

［6］ 朱宏杰.噴泉碼編譯碼技術(shù)與應(yīng)用研究［D］．北京：清華大學(xué),2008．

［7］ 慕建君,焦曉鵬,曹訓(xùn)志.數(shù)字噴泉碼及其應(yīng)用的研究進(jìn)展和發(fā)展［J］.電子學(xué)報(bào)2009,37(7):1571-1577.

［8］ BYERS J W,LUBY M,MITZENMACHERM.Adigital folultain approach to asynchronous reliable multicast［J］.IEEE Journal on Seleeted Areas in Conlnlunieations,2002,20(8):1528-1540.

［9］ LEVIS P,MADDENS，GAYD,POLASTRE J,SZEWCZYK R,WOOA,BREWER E,CULLERD. The emergence of networking abstractions and techniques in tinyos ［C］//Proceedings of the First USENIX/ACM Networked System Design and Implementation 2004:1-14.

［10］LEVIS P,LEEN,WELSHM,CULLERD.TOSSIM: Accurate and scalable simulation of entire tinyos applications ［C］// Proceedings of the 1st international conference on Embedded networked sensor system2003: 126-137.