無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法綜述

屈志偉

摘 要：無線傳感器網(wǎng)絡(luò)不同于常規(guī)網(wǎng)絡(luò)，網(wǎng)內(nèi)節(jié)點受能量和信道等硬件條件的限制，且網(wǎng)絡(luò)采集和傳輸?shù)臄?shù)據(jù)存在大量冗余，將額外消耗大量節(jié)點能量，此時需要適用于節(jié)點的數(shù)據(jù)壓縮算法除去冗余數(shù)據(jù)，節(jié)約能量，提高網(wǎng)絡(luò)的生存周期。文章依據(jù)冗余數(shù)據(jù)的類型，分別介紹了對應(yīng)的數(shù)據(jù)壓縮算法，并詳細(xì)描述了各自的壓縮工作原理。

關(guān)鍵詞：無線傳感器；數(shù)據(jù)壓縮；冗余

無線傳感器網(wǎng)絡(luò)[1]（wireless sensor networks，WSNs）是由大量廉價的具有通信、計算和存儲的微小傳感器節(jié)點隨機(jī)鋪灑在監(jiān)控區(qū)域內(nèi)，網(wǎng)內(nèi)節(jié)點可以相互協(xié)作，實時地感知和采集監(jiān)測數(shù)據(jù)，并將處理后的數(shù)據(jù)傳送到需要的用戶。但節(jié)點受制于能量、儲存和帶寬等硬件條件的限制，如何設(shè)計適用于節(jié)點的數(shù)據(jù)壓縮技術(shù)以提高節(jié)點的能量使用效率，延長整個網(wǎng)絡(luò)的生存周期就成為了當(dāng)下無線傳感器網(wǎng)絡(luò)研究的重點。

一般在監(jiān)測區(qū)域內(nèi)網(wǎng)絡(luò)節(jié)點采集的數(shù)據(jù)具有時間相關(guān)性、空間相關(guān)性和時空相關(guān)性三個方面的特點[2]。針對上述采集數(shù)據(jù)特點，研究人員已研究出多種經(jīng)典的數(shù)據(jù)壓縮算法來解決這些數(shù)據(jù)冗余。具體的壓縮算法如下。

1 基于時間相關(guān)性的數(shù)據(jù)壓縮算法

此類壓縮算法主要是去除時間方面的冗余數(shù)據(jù)。主要算法有：基于線性回歸原理的分段常數(shù)逼近算法（PMC-MR）和其改進(jìn)算法（PMC-MENAN）算法，其基本原理是根據(jù)實際應(yīng)用場景給定數(shù)據(jù)最大誤差限值，原始數(shù)據(jù)使用一分段常數(shù)的表達(dá)式來擬合，并記錄獲得的這次原始數(shù)據(jù)的最小、最大值，兩者進(jìn)行差值計算，其值超過給定的最大誤差容限后輸出該段序列的持續(xù)時間和其最值平均；基于預(yù)測編碼思想的算法主要是利用已獲得的原始數(shù)據(jù)根據(jù)數(shù)學(xué)模型來預(yù)測未來數(shù)據(jù)，將預(yù)測值與真實值進(jìn)行比較所得值即誤差如在允許的范圍內(nèi)，就用預(yù)測值代替所采集的真實數(shù)據(jù)。此時就實現(xiàn)了對原始數(shù)據(jù)的壓縮目的。常用的算法有自回歸預(yù)測算法、移動平均預(yù)測算法、指數(shù)平滑預(yù)測算法等；LZW編碼算法原理是將采集的數(shù)據(jù)按照各自特征建立初始詞典，編碼器在所建的詞典中依據(jù)其數(shù)據(jù)在詞典中的位置輸出索引值進(jìn)行查找，并將查找結(jié)果對應(yīng)用作編碼值。隨著壓縮過程詞典的不斷擴(kuò)充，最終得到所有數(shù)據(jù)用位置索引來代表數(shù)據(jù)串。而在壓縮過程中不會保存相應(yīng)的字典，在解壓縮過程會根據(jù)數(shù)據(jù)的特征重新建立初始詞典，然后根據(jù)編碼查找到字典中相對應(yīng)的數(shù)據(jù)值；Huffman編碼算法是一種依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字的基于統(tǒng)計規(guī)律的數(shù)據(jù)壓縮算法，常使用算法思想有靜態(tài)Huffman和動態(tài)Huffman[3]。

2 基于空間相關(guān)性的數(shù)據(jù)壓縮算法

這類壓縮算法主要是去除空間方面的冗余數(shù)據(jù)，代表算法有分布式信源編碼[4]。其原理為兩個獨(dú)立關(guān)系的離散的無記憶信源C和D，D為C的參考信息。根據(jù)香農(nóng)信息理論可知，D已知（即K閉合），C的無損壓縮極限為H（C|D），其中H（C|D）為C的條件熵，與之相對應(yīng)在解壓縮端C，此時壓縮極限仍然為C的條件熵H（C|D）。此時解壓縮端只需知道C和D的聯(lián)合概率分布就可以在參考消息D不清楚的情況下就可以進(jìn)行壓縮，并且可以取得和已知參考消息D一樣的編碼效果。

3 基于時空相關(guān)性的數(shù)據(jù)壓縮算法

此類壓縮算法主要是去除數(shù)據(jù)在時間和空間方面的冗余。其代表算法有兩級DPCM差分脈碼調(diào)制，原理為在處理時間冗余階段采用基于歷史數(shù)據(jù)的預(yù)測，而在處理空間冗余是則采用基于相鄰節(jié)點的預(yù)測；小波算法[5]是近幾年來壓縮算法研究的熱點，其理論基礎(chǔ)是繼承和發(fā)展短時傅立葉變換局部化的思想并獨(dú)特的提出“時間-頻率”窗口概念，通過對信號的時間、空間頻率進(jìn)行局部化分析，使用伸縮平移運(yùn)算過程來對信號（函數(shù)）逐步的進(jìn)行多尺度的細(xì)化以取得高頻處時間細(xì)分、低頻處頻率細(xì)分。小波算法可以自動適應(yīng)時頻信號并聚集到所采集信號的任意細(xì)節(jié)，進(jìn)而達(dá)到壓縮數(shù)據(jù)的目的；壓縮感知算法[6]原理是對一類具有稀疏或可壓縮特性的信號進(jìn)行信號壓縮重構(gòu)的技術(shù)。主要是利用觀測矩陣把可以壓縮或稀疏的高維信號用一定的技術(shù)投影到一個低維空間得到壓縮數(shù)據(jù)，然后根據(jù)信號的稀疏性先驗條件，借助重構(gòu)算法高概率恢復(fù)原始信號的過程。壓縮感知過程主要包括信號的稀疏表示、編碼測量以及壓縮信號的精確重構(gòu)三個方面。

4 結(jié)束語

文章主要研究了無線傳感器網(wǎng)絡(luò)的時間冗余、空間冗余和時空冗余這三種冗余數(shù)據(jù)類型，然后根據(jù)數(shù)據(jù)冗余類型不同，分別介紹了對應(yīng)的且適用于無線傳感器節(jié)點的數(shù)據(jù)壓縮算法，并詳細(xì)描述了各自的壓縮工作原理。

參考文獻(xiàn)

[1]Liang Yuzhu， Zhang Aili， Li Yongzhen. An energy effective routing protocolconstructs cluster topology for WSNs[C] //Proceedings of the 2013 Third International Conferenceon Instrumentation，Measurement，Computer，Communication and Control（IMCCC），Shenyang：IEEE，2013：1097-1100.

[2]劉河，陳宇.無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法研究[J].智能計算機(jī)與應(yīng)用，2013，3（5）：28-30.

[3]呂利娟，李靜.霍夫曼算法在降低WSN系統(tǒng)功耗中的應(yīng)用研究[J].電腦知識與技術(shù)，2007，2（9）：735-735.

[4]胡易俗.無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)壓縮技術(shù)研究[D].西安電子科技大學(xué)，2012.

[5]黨小超，高琪，郝占軍.基于小波變換的分布式WSN數(shù)據(jù)融合模型研究[J].計算機(jī)工程與應(yīng)用，2014，50（22）：97-101.

[6]柯家龍，李繼樓.壓縮感知中的投影矩陣優(yōu)化算法[J].計算機(jī)技術(shù)與發(fā)展，2015，25（3）：95-98.