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

屈志偉

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

文章主要研究了無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間冗余、空間冗余和時(shí)空冗余這三種冗余數(shù)據(jù)類型，然后根據(jù)數(shù)據(jù)冗余類型不同，分別介紹了對(duì)應(yīng)的且適用于無(wú)線傳感器節(jié)點(diǎn)的數(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ú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法研究[J].智能計(jì)算機(jī)與應(yīng)用，2013，3（5）：28-30.

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

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

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

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