袁 博，趙旦峰，錢晉希

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱 150001)

WSN中降低噴泉碼存儲(chǔ)冗余量的方法研究

袁 博，趙旦峰，錢晉希

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱 150001)

針對由于數(shù)字噴泉碼的冗余編碼數(shù)據(jù)包和所需內(nèi)存空間較大，導(dǎo)致無線傳感器網(wǎng)絡(luò)(WSN)實(shí)時(shí)性較差的問題，設(shè)計(jì)一種平均分幀長LT碼的編譯碼系統(tǒng)。建立典型拓?fù)浣Y(jié)構(gòu)模型，應(yīng)用網(wǎng)絡(luò)編碼和數(shù)字噴泉碼的級聯(lián)形式進(jìn)行數(shù)據(jù)傳輸，并對平均分幀長LT碼的生成矩陣進(jìn)行壓縮編碼。通過加權(quán)平均法和多比特打包法，在不破壞噴泉碼特性的前提下降低無線整個(gè)傳感器網(wǎng)絡(luò)的存儲(chǔ)冗余量。實(shí)驗(yàn)結(jié)果表明，該系統(tǒng)能使數(shù)字噴泉碼降低103量級的存儲(chǔ)冗余量，并提高WSN編譯碼效率及數(shù)據(jù)中心的數(shù)據(jù)恢復(fù)率。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；噴泉碼；平均分幀長LT碼；壓縮算法；網(wǎng)絡(luò)編碼；多比特打包

1 概述

數(shù)字噴泉碼在近幾年飛速發(fā)展，能夠在各種網(wǎng)絡(luò)通信或者節(jié)點(diǎn)通信中充分利用節(jié)點(diǎn)之間的互信息，提高信息傳輸?shù)聂敯粜?，接收端在接收到網(wǎng)絡(luò)編碼后的數(shù)據(jù)時(shí)便于進(jìn)行信息提取，當(dāng)接收到的數(shù)據(jù)包數(shù)量足夠多時(shí)，可進(jìn)行錯(cuò)誤恢復(fù)，并且其編譯碼復(fù)雜度較低，滿足一定條件時(shí)可進(jìn)行線性編譯碼。無線傳感器網(wǎng)絡(luò)(Wireless Sen sor Net work, WSN)能高效提取及處理信息，并實(shí)時(shí)監(jiān)控傳輸信息數(shù)據(jù)，在通信領(lǐng)域中具有重要的地位。但是數(shù)字噴泉碼具有較大的冗余編碼數(shù)據(jù)包，存在一定的譯碼失敗概率，而且其譯碼算法還有待進(jìn)一步提高，在WSN中應(yīng)用時(shí)存在延時(shí)及占用帶寬較大的問題，因此需要改善網(wǎng)絡(luò)編碼及其在WSN中應(yīng)用時(shí)的性能。

本文對LT碼的編譯碼算法進(jìn)行討論，研究LT碼參數(shù)的影響，在WSN中建立平均分幀長LT碼的編譯碼系統(tǒng)模型。將矩陣壓縮算法引入平均分幀長LT碼的生成矩陣中，對不同的信息幀長做出仿真分析。通過建立系統(tǒng)模型，研究其拓?fù)浣Y(jié)構(gòu)，并在不同的系統(tǒng)參數(shù)及WSN條件下，應(yīng)用多比特打包法實(shí)現(xiàn)信息的小冗余傳輸。

2 LT碼的編譯碼算法研究

2.1 L T碼參數(shù)討論

討論的參數(shù)[1-2]包括：符號節(jié)點(diǎn)度為1的平均值S，編碼個(gè)數(shù)K'，度數(shù)值d，解碼失敗概率δ和常數(shù)c。分析符號節(jié)點(diǎn)度為1的平均值S和編碼個(gè)數(shù)K'的表達(dá)式：

其編譯碼算法是K的線性函數(shù)，并希望以少的冗余得到高的譯碼成功率，在理想條件下，考慮冗余量趨近于0，得出δ的極限值為：

由式(2)、式(3)可以得出：若要使δ＜1，則K＜e，可見，若要增大譯碼成功率，則要使K盡量小。

根據(jù)上述對LT碼參數(shù)的討論，建立平均分幀長LT碼系統(tǒng)。減少每組的幀長度，盡量減少冗余量，同時(shí)提升譯碼準(zhǔn)確性。原始數(shù)據(jù)平均分幀長編碼設(shè)計(jì)流程如圖1所示。通過上述分析可以得出，為實(shí)現(xiàn)不同的效果可以采用不同的設(shè)計(jì)方案，但均能滿足系統(tǒng)某一方面的性能要求。

圖1 原始數(shù)據(jù)平均分幀長編碼設(shè)計(jì)流程

2.2 平均分幀長LT碼的系統(tǒng)性能參數(shù)分析

平均分幀長LT碼的系統(tǒng)性能參數(shù)包括：平均度數(shù)D和編譯碼復(fù)雜度Q。

編譯碼復(fù)雜度的計(jì)算公式為Kln(K/ q)，平均度數(shù)的計(jì)算公式為lnK，K是原始數(shù)據(jù)長度。在平均分幀長LT碼系統(tǒng)中，假設(shè)原始數(shù)據(jù)K平均分成8組，滿足式(4)：

由假設(shè)條件可知，平均分幀長LT碼的復(fù)雜度Q計(jì)算公式如下：

當(dāng)原始數(shù)據(jù)進(jìn)行原始LT編碼時(shí)，原始LT碼的復(fù)雜度計(jì)算公式如下：

平均分幀長LT碼的平均度數(shù)D計(jì)算公式如下：

原始LT碼的平均度數(shù)計(jì)算公式如下：

由于k＜8k，因此得到Q'＜Q，D'＜D。

可見，應(yīng)用平均分幀長LT碼系統(tǒng)時(shí)，可以降低編譯碼復(fù)雜度，當(dāng)原始數(shù)據(jù)固定時(shí)，可以在不增加額外運(yùn)算量的情況下，一方面縮短編碼時(shí)間，提高譯碼速率；另一方面提高譯碼成功率。

2.3 基于平均分幀長LT碼的編譯碼系統(tǒng)模型建立

在分析系統(tǒng)的編譯碼復(fù)雜度與平均度數(shù)后，確定WSN中平均分幀長LT碼的編譯碼系統(tǒng)模型如圖2所示。

圖2 W SN中平均分幀長LT碼的編譯碼系統(tǒng)模型

3 矩陣壓縮算法研究

根據(jù)上文建立的WSN中平均分幀長LT碼的編譯碼系統(tǒng)模型，本節(jié)將對矩陣壓縮編譯碼器進(jìn)行探討，基于已有的集中壓縮算法研究多比特打包法[3]，以減少數(shù)據(jù)流量，同時(shí)實(shí)現(xiàn)節(jié)能。

3.1 矩陣G的生成

設(shè)t(t1, t2,…,tM)為編碼后序列，s(s1, s2,…,sN)為原始信息序列，LT編碼過程[4]可以表示為：

矩陣G的生成過程如圖3所示。

圖3 矩陣G的生成過程

3.2 基于單比特打包法的矩陣壓縮算法原理

本文經(jīng)過分析可知，矩陣G有如下特點(diǎn)：(1)元素只可能為0或1；(2)G中大部分元素是0的稀疏矩陣。

根據(jù)以上特點(diǎn)，可以確定改進(jìn)矩陣壓縮算法的編碼方法，具體步驟為：(1)由編碼原理生成矩陣G；(2)提取生成矩陣中所有元素為1的行位置和列位置；(3)將行位置和列位置用與其對應(yīng)的二進(jìn)制數(shù)表示；(4)將列位置相同的所有行位置打包成一個(gè)數(shù)據(jù)包；(5)重復(fù)以上步驟，直至完成。綜上所述，得到的矩陣冗余量降低比可表示為：

其中，L為矩陣中1的個(gè)數(shù)；N為原始數(shù)據(jù)長度；M為編碼后數(shù)據(jù)長度；x為行位置用二進(jìn)制數(shù)表示時(shí)的位數(shù)；y為列位置用二進(jìn)制數(shù)表示時(shí)的位數(shù)。

假設(shè)用數(shù)組a，b保存行位置二進(jìn)制表示和列位置二進(jìn)制表示，數(shù)組a，b中的位置值由更多二進(jìn)制數(shù)表示，同時(shí)可以降低其誤碼率。應(yīng)用該方法，只需將生成矩陣中的1的行位置和列位置進(jìn)行傳送，而不需傳輸整個(gè)生成矩陣，在接收端，也只需根據(jù)接收到的行位置和列位置進(jìn)行譯碼，無需恢復(fù)生成矩陣即可譯出原始數(shù)據(jù)。

3.3 多比特打包法

現(xiàn)階段研究的LT碼的編譯碼過程及應(yīng)用都是對單比特原始數(shù)據(jù)進(jìn)行打包傳輸，而單比特?cái)?shù)據(jù)打包傳輸，在數(shù)據(jù)量較大的情況下會(huì)出現(xiàn)占用較大內(nèi)存和帶寬的問題，延時(shí)較大，且出現(xiàn)有效性和可靠性下降的現(xiàn)象。而影響內(nèi)存空間的主要因素是生成矩陣，若將數(shù)據(jù)進(jìn)行多比特?cái)?shù)打包傳輸，生成矩陣G會(huì)大大減小，G將不再是影響存儲(chǔ)空間大小的主要因素，能更好地發(fā)揮數(shù)字噴泉碼的優(yōu)勢。

經(jīng)過以上分析與驗(yàn)證得到多比特打包法，即將多個(gè)比特?cái)?shù)進(jìn)行打包后編碼傳送，取代原有的單比特?cái)?shù)傳輸，這樣在數(shù)據(jù)量較大時(shí)就可大大減少存儲(chǔ)空間，減少存儲(chǔ)冗余量，提高譯碼成功率。

4 LT碼在WSN中的應(yīng)用研究

由于實(shí)際用于森林中的WSN主要是自組織網(wǎng)絡(luò)[5]，因此將WSN應(yīng)用到森林中，再用數(shù)字噴泉碼傳輸信息。根據(jù)林區(qū)的實(shí)際分布情況，提出2種WSN拓?fù)浣Y(jié)構(gòu)，即平面結(jié)構(gòu)和分層結(jié)構(gòu)，具有較好的擴(kuò)展性和可靠性。

4.1 W SN中數(shù)字噴泉碼和網(wǎng)絡(luò)編碼的級聯(lián)碼應(yīng)用

WSN對傳感器采集的數(shù)據(jù)進(jìn)行接收、發(fā)送、處理等操作以完成信號傳遞，從而實(shí)現(xiàn)對特定區(qū)域的監(jiān)測。基于此數(shù)字噴泉碼和網(wǎng)絡(luò)編碼級聯(lián)的方式已被應(yīng)用到WSN中[6]。因?yàn)榫W(wǎng)絡(luò)編碼能在理想信道條件下，在相關(guān)節(jié)點(diǎn)通過最大流最小割定理對輸入流編碼獲得最大可能速率，而噴泉碼是一種無碼率碼，通過在相應(yīng)節(jié)點(diǎn)結(jié)合網(wǎng)絡(luò)編碼和數(shù)字噴泉碼，能減少能量損耗。

4.2 W SN平面結(jié)構(gòu)中典型拓?fù)浣Y(jié)構(gòu)模型的建立

4.2.1 星形拓?fù)浣Y(jié)構(gòu)

星形拓?fù)浣Y(jié)構(gòu)如圖4所示。其中，基站為中間節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)作為一個(gè)邊緣節(jié)點(diǎn)，在中間節(jié)點(diǎn)和邊緣節(jié)點(diǎn)之間建立的鏈路看作是星形拓?fù)涞囊粭l邊。為了能適應(yīng)網(wǎng)絡(luò)的特征，使得網(wǎng)絡(luò)傳播的總信息速率達(dá)到最大，建立適合每條鏈路的信息傳輸模式，即采用多速率、多分辨率的信源信息編碼，使得不同的鏈路傳輸不同的編碼信息[7-8]。

圖4 星形拓?fù)浣Y(jié)構(gòu)

4.2.2 網(wǎng)狀拓?fù)浣Y(jié)構(gòu)

該結(jié)構(gòu)中的傳感器節(jié)點(diǎn)是相同的，可直接進(jìn)行通信，與基站傳輸數(shù)據(jù)和命令，該系統(tǒng)是多跳系統(tǒng)(圖5)。在WSN中，有時(shí)會(huì)存在多對無線傳感器節(jié)點(diǎn)之間在同一時(shí)間進(jìn)行通信的情況?？紤]如圖5所示的一種特殊情況，圖中有兩對無線傳感器節(jié)點(diǎn)要進(jìn)行通信，其中，傳感器A要將信息發(fā)送給傳感器E，而傳感器B要將信息發(fā)送給傳感器D。由于地理位置的原因，它們都需要借助傳感器C進(jìn)行轉(zhuǎn)發(fā)。由此可知，利用網(wǎng)絡(luò)編碼可在3個(gè)時(shí)隙內(nèi)(在圖5中，實(shí)線表示第1個(gè)時(shí)隙，虛線表示第2個(gè)時(shí)隙，點(diǎn)線表示第3個(gè)時(shí)隙；a，b為信息流)完成使用常用方法時(shí)4個(gè)時(shí)隙的信息傳遞量，即可以節(jié)省25%的發(fā)送時(shí)間，以完成信息傳遞。

圖5 網(wǎng)狀拓?fù)浣Y(jié)構(gòu)

4.2.3 混合拓?fù)浣Y(jié)構(gòu)

混合網(wǎng)絡(luò)中存在整體傳輸數(shù)據(jù)時(shí)的線性接力拓?fù)浣Y(jié)構(gòu)(圖6)。利用網(wǎng)絡(luò)編碼時(shí)，在第1個(gè)時(shí)隙，無線傳感器節(jié)點(diǎn)1需要將信息a發(fā)送給無線傳感器節(jié)點(diǎn)2；在第2個(gè)時(shí)隙內(nèi)傳感器節(jié)點(diǎn)2將信息a轉(zhuǎn)發(fā)給傳感器節(jié)點(diǎn)3；在第3個(gè)時(shí)隙內(nèi)，傳感器節(jié)點(diǎn)3將信息a廣播出去，此時(shí)，傳感器節(jié)點(diǎn)4和傳感器節(jié)點(diǎn)2都會(huì)收到傳感器節(jié)點(diǎn)3廣播的信息a。同時(shí)傳感器節(jié)點(diǎn)1也向傳感器節(jié)點(diǎn)2發(fā)送信息b，傳感器節(jié)點(diǎn)2可利用網(wǎng)絡(luò)編碼求出b，其他傳感器節(jié)點(diǎn)的傳輸可依次仿照傳感器節(jié)點(diǎn)2的處理進(jìn)行，直到傳到目的地傳感器節(jié)點(diǎn)N。

圖6 混合拓?fù)浣Y(jié)構(gòu)

應(yīng)用本文提出的矩陣壓縮法分別[9]計(jì)算3種拓?fù)浣Y(jié)構(gòu)中數(shù)字噴泉碼存儲(chǔ)冗余量的降低比，達(dá)到降低WSN多節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)中數(shù)字噴泉碼存儲(chǔ)冗余量的目的。

4.3 W SN分層結(jié)構(gòu)中典型拓?fù)浣Y(jié)構(gòu)模型的建立

圖7為三頻分層結(jié)構(gòu)，S將信息流b1和b2傳送到2個(gè)目的地網(wǎng)關(guān)A和B，頻率1用于簇頭與簇成員以及相距較近的簇成員之間的通信，而簇頭之間的通信用頻率2，來彌補(bǔ)平面結(jié)構(gòu)可擴(kuò)充性差的缺陷。網(wǎng)關(guān)之間的通信用頻率3?？梢哉J(rèn)為此拓?fù)浣Y(jié)構(gòu)就是分層結(jié)構(gòu)中的典型拓?fù)浣Y(jié)構(gòu)。

圖7 三頻分層結(jié)構(gòu)

由于在分層結(jié)構(gòu)中[10-12]，通常檢測的區(qū)域很大，要傳輸?shù)臄?shù)據(jù)量也很大，此時(shí)考慮單比特打包傳輸已經(jīng)不能滿足信息量的要求，因此考慮多比特?cái)?shù)打包傳輸?shù)姆椒?，將多比特?cái)?shù)打包傳輸時(shí)，將減少矩陣的生成，達(dá)到降低存儲(chǔ)冗余量的目的。在WSN的分層結(jié)構(gòu)中，應(yīng)用多比特?cái)?shù)打包法進(jìn)行LT碼編碼數(shù)據(jù)傳輸，然后對WSN整體求出一個(gè)平均的矩陣冗余量降低比。

5 系統(tǒng)仿真與結(jié)果分析

本文系統(tǒng)仿真平臺(tái)是Vista系統(tǒng)，CPU為2.27 GHz，內(nèi)存為2 GB，采用Matlab軟件仿真。

5.1 原始LT碼和平均分幀長LT碼的編譯碼時(shí)間比較

圖8為原始LT碼和平均分幀長LT碼的編譯碼時(shí)間比較。平均分幀長LT碼編譯碼系統(tǒng)能夠減少延時(shí)，提高編譯碼效率，增加速率。

圖8 原始LT碼和平均分幀長LT碼的編譯碼時(shí)間比較

5.2 不同LT碼分幀數(shù)的性能仿真分析

為了更好地說明不同分幀數(shù)對LT碼壓縮性能的影響，將原始幀長進(jìn)行不同等分傳輸，如圖9所示，應(yīng)用碼本壓縮法對其生成矩陣進(jìn)行壓縮，得到矩陣冗余量降低比曲線。可見，隨著平均分幀數(shù)的增加，矩陣冗余量降低比迅速增大，壓縮效果顯著。

圖9 不同分幀數(shù)碼本壓縮時(shí)矩陣冗余量降低比值

5.3 不同比特?cái)?shù)打包的LT碼性能仿真分析

圖10為LT碼在不同比特?cái)?shù)打包情況下的矩陣冗余量降低比性能曲線，原始數(shù)據(jù)為5 000 bit，平均分幀數(shù)分別為取1，2，4，5，8，10的6種情況。為便于對比，選擇5 bit，8 bit，10 bit 3種情況分別進(jìn)行打包，并進(jìn)行仿真比較?？梢钥闯?，在平均分幀數(shù)相同條件下，隨著每包比特?cái)?shù)的增大，其矩陣冗余量降低比隨之迅速上升。這是因?yàn)槊堪忍財(cái)?shù)的增長，使得生成矩陣減小，性能也隨之變優(yōu)。同時(shí)可以看出平均分幀數(shù)為10，10 bit打包時(shí)可使矩陣冗余量降低比達(dá)到103量級，而誤比特率基本為0。

圖10 不同比特?cái)?shù)打包時(shí)LT碼矩陣冗余量降低比值

5.4 分層Ad hoc網(wǎng)絡(luò)中的LT碼性能仿真分析

由于實(shí)際WSN中傳輸?shù)臄?shù)據(jù)量很大，因此考慮對LT碼進(jìn)行多比特?cái)?shù)打包傳輸。

如圖11所示，原始數(shù)據(jù)包為1 000時(shí)，圖11(a)中每包5 bit，圖11(b)中每包1 bit，由圖11(a)可以看出，在碼包個(gè)數(shù)相同條件下，多比特位數(shù)打包傳輸時(shí)的矩陣冗余量降低比遠(yuǎn)大于單包時(shí)的矩陣冗余量降低比，從圖11(a)和圖11(b)可以看出，分幀數(shù)為10時(shí)，采用多比特打包時(shí)，矩陣冗余量降低比已超過1 000，即103量級，而采用單包的平均分幀長矩陣壓縮算法時(shí)，矩陣冗余量降低比只有140，即102量級，遠(yuǎn)小于多比特?cái)?shù)打包時(shí)的矩陣冗余量降低比?？梢?，多比特?cái)?shù)打包LT碼壓縮性能良好。

圖11 數(shù)據(jù)包為1 000時(shí)不同比特?cái)?shù)打包下矩陣冗余量降低比值

6 結(jié)束語

在WSN中引入傳統(tǒng)LT碼可以將傳感器節(jié)點(diǎn)的數(shù)據(jù)分布存儲(chǔ)到不同節(jié)點(diǎn)中，增強(qiáng)WSN的可靠性。但是由于傳統(tǒng)LT算法的復(fù)雜度高、編譯碼時(shí)間長等問題，使得無線傳感器網(wǎng)絡(luò)的實(shí)時(shí)性較差。數(shù)字噴泉碼不需要反饋，但譯碼時(shí)需要接收很多的編碼分組，因此需要很大的內(nèi)存空間，造成噴泉碼難以在實(shí)際系統(tǒng)中應(yīng)用。

本文研究表明，由于壓縮編碼方法會(huì)增加編譯碼時(shí)間，因此采用平均分幀長方法減少編譯碼時(shí)間，降低其復(fù)雜度。本文先將原數(shù)據(jù)進(jìn)行平均分幀長處理，通過小幀長的方法對原始數(shù)據(jù)拆分編譯碼，然后對生成矩陣進(jìn)行壓縮編碼，使得在不破壞噴泉碼特性的前提下減少傳送的數(shù)據(jù)量，增強(qiáng)LT碼在實(shí)際應(yīng)用中的可行性。在需要傳輸大量數(shù)據(jù)時(shí)，應(yīng)用多比特打包法，可減少生成矩陣的大小，當(dāng)使用越多的比特?cái)?shù)進(jìn)行打包時(shí)，存儲(chǔ)空間占用將越少。因?yàn)樯删仃嚧笮Q定了存儲(chǔ)冗余量的大小，所以采用多比特打包法會(huì)使誤碼率上升，但數(shù)值非常小，可以忽略不計(jì)。LT碼會(huì)增加網(wǎng)絡(luò)冗余，而網(wǎng)絡(luò)編碼在WSN中則能提高編譯碼效率。在WSN中傳輸數(shù)據(jù)時(shí)，應(yīng)用壓縮編碼方法會(huì)增加節(jié)點(diǎn)處理和傳輸數(shù)據(jù)的能量消耗，從而減少WSN的生命時(shí)間。但通過平均分幀長法和多比特打包法，可減少每次存儲(chǔ)的生成矩陣大小、傳輸和接收數(shù)據(jù)時(shí)需要的帶寬，以及每個(gè)節(jié)點(diǎn)處理和傳輸數(shù)據(jù)的能量消耗。所以，將網(wǎng)絡(luò)編碼和數(shù)據(jù)壓縮相結(jié)合來利用WSN資源是一種有效的方法。今后將進(jìn)一步研究數(shù)字噴泉碼在并行下載、視頻流、數(shù)據(jù)廣播、數(shù)據(jù)文件存儲(chǔ)、無線網(wǎng)絡(luò)等領(lǐng)域中的應(yīng)用。

[1] 樊平毅. 網(wǎng)絡(luò)信息論[M]. 北京: 清華大學(xué)出版社, 2009.

[2] 張 翼, 高宏峰, 師春靈. LT碼編譯的改進(jìn)方法[J]. 計(jì)算機(jī)工程, 2010, 36(11): 271-273, 276.

[3] 薩洛蒙. 數(shù)據(jù)壓縮原理與應(yīng)用[M]. 北京: 電子工業(yè)出版社, 2003.

[4] Byers J W, Lub y M, Mitze nmacher M. A Digital Fountain Approach to Asynchronous Re liable Multicast[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1528-1540.

[5] Mitzenmacher M. Digital Fountains: A S urvey and Lo ok Forward[C]//Proceedings of Infor mation Theory Workshop. San Antonio, USA: IEEE Press, 2004: 271-276.

[6] Xu Qian, S tankovic V, Xi ong Zixiang. Wyner-ziv Video Compression an d Fou ntain Co des for Receiver Driven Layered Multicast[J]. IEE E Transactions on Ci rcuits and Systems for Video Technology, 2007, 17(7): 901-906.

[7] Ma Yuanyuan, Yuan Dongfeng, Zhang Haixia. Fountain Codes and Applications to Reliable Wireless Broadcast System[C]// Proceedings of ITW’06. Chengdu, China: [s. n.], 2006: 66-70.

[8] Byers J, Luby M, Mitzenmacher M. Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed up Downloads[C]//Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies. [S. l.]: IEEE Press, 1999: 275-283.

[9] 胡鳳國. 語言計(jì)量研究中的上小三角矩陣壓縮存儲(chǔ)算法[J].現(xiàn)代電子技術(shù), 2011, 34(2): 109-115.

[10] 湯文亮, 曾祥元, 曹義親. 基于ZigBee無線傳感器網(wǎng)絡(luò)的森林火災(zāi)監(jiān)測系統(tǒng)[J]. 實(shí)驗(yàn)室研究與探索, 2010, 29(6): 49-53.

[11] Yang Jing, An Jianping, Yang Miao. Combined Fountain Code with Network Co ding for Error-tolerant T ransmission Network[C]//Proceedings of the 5th International Conference on W ireless Communications, Networking a nd Mo bile Computing. [S. l.]: IEEE Press, 2009: 1-4.

[12] 王 立. Ad hoc網(wǎng)絡(luò)特點(diǎn)以及應(yīng)用探究[J]. 計(jì)算機(jī)光盤軟件與應(yīng)用, 2011, (17): 69-70.

編輯 陸燕菲

Research on Storage Redundancy Reduction Method of Fountain Code in WSN

YUAN Bo, ZHAO Dan-feng, QIAN Jin-xi

(College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)

For the problems that the redundant encoded data packets of fountain code are big and require large memory space, resulting in poor real-time Wireless Sensor Network(WSN) problems. A system of average framing length of Luby Transform(LT) codes split encoding and dec oding is designed. The ty pical topology m odel is built, th e cascade form o f the net work c oding and fountai n codes in d ata transmission is applied, and the i mprovement coding compression algorithm in the average framing length LT code generator matrix is introduced. The weighted average method and the multi-bit packag ing method are i ntroduced in the hierarchy of WSN, which greatly reduces the amount of storage redundancy without damaging the characteristic of fountain codes. Experimental results show that the system makes the red uction amount of the compression ra tio of the storag e redundancy in the WSN to 103, promotes the encoding rate a nd decoding rate in the WSN and improves the recovery rate of the data center.

Wireless Sensor Network(WSN); fountain code; average framing length LT code; compression algorithm; network coding; multi-bit packaging

10.3969/j.issn.1000-3428.2014.05.015

黑龍江省自然科學(xué)基金資助項(xiàng)目(F200810)。

袁 博(1989－)，女，碩士研究生，主研方向：信號處理；趙旦峰，教授、博士生導(dǎo)師；錢晉希，博士研究生。

2013-03-04

2013-05-08E-mail：icetinghai@126.com

1000-3428(2014)05-0068-05

A

TP393