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

袁 博，趙旦峰，錢晉希

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

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

袁 博，趙旦峰，錢晉希

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

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

1 概述

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

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

2 LT碼的編譯碼算法研究

2.1 L T碼參數討論

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

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

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

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

圖1 原始數據平均分幀長編碼設計流程

2.2 平均分幀長LT碼的系統性能參數分析

平均分幀長LT碼的系統性能參數包括：平均度數D和編譯碼復雜度Q。

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

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

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

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

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

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

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

2.3 基于平均分幀長LT碼的編譯碼系統模型建立

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

圖2 W SN中平均分幀長LT碼的編譯碼系統模型

3 矩陣壓縮算法研究

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

3.1 矩陣G的生成

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

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

圖3 矩陣G的生成過程

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

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

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

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

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

3.3 多比特打包法

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

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

4 LT碼在WSN中的應用研究

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

4.1 W SN中數字噴泉碼和網絡編碼的級聯碼應用

WSN對傳感器采集的數據進行接收、發送、處理等操作以完成信號傳遞，從而實現對特定區域的監測。基于此數字噴泉碼和網絡編碼級聯的方式已被應用到WSN中[6]。因為網絡編碼能在理想信道條件下，在相關節點通過最大流最小割定理對輸入流編碼獲得最大可能速率，而噴泉碼是一種無碼率碼，通過在相應節點結合網絡編碼和數字噴泉碼，能減少能量損耗。

4.2 W SN平面結構中典型拓撲結構模型的建立

4.2.1 星形拓撲結構

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

圖4 星形拓撲結構

4.2.2 網狀拓撲結構

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

圖5 網狀拓撲結構

4.2.3 混合拓撲結構

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

圖6 混合拓撲結構

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

4.3 W SN分層結構中典型拓撲結構模型的建立

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

圖7 三頻分層結構

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

5 系統仿真與結果分析

本文系統仿真平臺是Vista系統，CPU為2.27 GHz，內存為2 GB，采用Matlab軟件仿真。

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

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

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

5.2 不同LT碼分幀數的性能仿真分析

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

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

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

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

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

5.4 分層Ad hoc網絡中的LT碼性能仿真分析

由于實際WSN中傳輸的數據量很大，因此考慮對LT碼進行多比特數打包傳輸。

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

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

6 結束語

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

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

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

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

[3] 薩洛蒙. 數據壓縮原理與應用[M]. 北京: 電子工業出版社, 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].現代電子技術, 2011, 34(2): 109-115.

[10] 湯文亮, 曾祥元, 曹義親. 基于ZigBee無線傳感器網絡的森林火災監測系統[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網絡特點以及應用探究[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