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

袁 博，趙旦峰，錢晉希

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

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

袁 博，趙旦峰，錢晉希

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

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

1 概述

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

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

2 LT碼的編譯碼算法研究

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

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

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

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

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

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

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

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

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

由假設條件可知，平均分幀長LT碼的復雜度Q計算公式如下：

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

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

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

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

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

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

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

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

3 矩陣壓縮算法研究

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

3.1 矩陣G的生成

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

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

圖3 矩陣G的生成過程

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

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

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

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

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

3.3 多比特打包法

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

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

4 LT碼在WSN中的應用研究

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

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

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

4.2 W SN平面結(jié)構(gòu)中典型拓撲結(jié)構(gòu)模型的建立

4.2.1 星形拓撲結(jié)構(gòu)

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

圖4 星形拓撲結(jié)構(gòu)

4.2.2 網(wǎng)狀拓撲結(jié)構(gòu)

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

圖5 網(wǎng)狀拓撲結(jié)構(gòu)

4.2.3 混合拓撲結(jié)構(gòu)

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

圖6 混合拓撲結(jié)構(gòu)

應用本文提出的矩陣壓縮法分別[9]計算3種拓撲結(jié)構(gòu)中數(shù)字噴泉碼存儲冗余量的降低比，達到降低WSN多節(jié)點拓撲結(jié)構(gòu)中數(shù)字噴泉碼存儲冗余量的目的。

4.3 W SN分層結(jié)構(gòu)中典型拓撲結(jié)構(gòu)模型的建立

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

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

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

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

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

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

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

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

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

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

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

5.3 不同比特數(shù)打包的LT碼性能仿真分析

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

圖10 不同比特數(shù)打包時LT碼矩陣冗余量降低比值

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

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

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

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

6 結(jié)束語

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

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

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

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

[3] 薩洛蒙. 數(shù)據(jù)壓縮原理與應用[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].現(xiàn)代電子技術(shù), 2011, 34(2): 109-115.

[10] 湯文亮, 曾祥元, 曹義親. 基于ZigBee無線傳感器網(wǎng)絡的森林火災監(jiān)測系統(tǒng)[J]. 實驗室研究與探索, 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)絡特點以及應用探究[J]. 計算機光盤軟件與應用, 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

黑龍江省自然科學基金資助項目(F200810)。

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

2013-03-04

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

1000-3428(2014)05-0068-05

A

TP393