夏長權(quán)，徐思韻，張劍云，時(shí)壯壯，朱金榮

（1.揚(yáng)州大學(xué)物理科學(xué)與技術(shù)學(xué)院，江蘇揚(yáng)州 225000；2.揚(yáng)州大學(xué)信息工程學(xué)院，江蘇 揚(yáng)州 225000）

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的主要部署區(qū)域?yàn)榈乩憝h(huán)境比較復(fù)雜的地方，而且節(jié)點(diǎn)的供電方式為電池供電，一旦節(jié)點(diǎn)能量耗盡，更換起來十分麻煩。因此，如何有效節(jié)能成為近幾年無線傳感器網(wǎng)絡(luò)領(lǐng)域研究的熱點(diǎn)。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在硬件上的能量消耗主要在傳感器、處理器和無線通信三大模塊上。但是，隨著集成電路工藝的進(jìn)步，處理器和傳感器模塊的功耗變得很低，絕大部分的能量消耗在無線通信模塊上，傳輸1 bit 數(shù)據(jù)所消耗的能量大約相當(dāng)于執(zhí)行1 000 條CPU 指令消耗的能量[1]。因此，通過減少傳感器節(jié)點(diǎn)之間的數(shù)據(jù)傳輸量來降低無線通信模塊負(fù)載量可以大大節(jié)省傳感器節(jié)點(diǎn)能量，達(dá)到降低網(wǎng)絡(luò)能耗的目的。

目前無線傳感器網(wǎng)絡(luò)中常用的數(shù)據(jù)壓縮算法主要可以分為兩大類：有損壓縮算法和無損壓縮算法。有損壓縮算法主要有離散余弦變換和小波變換[2]，無損壓縮算法主要有游程編碼和哈夫曼編碼[3]。有損壓縮算法在數(shù)據(jù)壓縮率方面具有一定的優(yōu)越性，但是在數(shù)據(jù)恢復(fù)方面顯得略為遜色，而無損壓縮算法則正好相反。關(guān)于有損壓縮算法，前人已經(jīng)做了一些相關(guān)的改進(jìn)，比如文獻(xiàn)[4]提出了一種可以動(dòng)態(tài)改變壓縮位率的小波壓縮算法，文獻(xiàn)[5]提出了一種減少數(shù)據(jù)空間相關(guān)性的分布式小波壓縮算法。但是，這些文獻(xiàn)中提到的壓縮算法均不能獲得較高的數(shù)據(jù)壓縮率。

為了完全覆蓋監(jiān)控區(qū)域，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)一般部署比較密集，同一節(jié)點(diǎn)在不同時(shí)刻采集到的數(shù)據(jù)和不同節(jié)點(diǎn)在同一時(shí)刻采集到的數(shù)據(jù)具有極大的相似性[6]。這種相似性被稱為時(shí)間相關(guān)性和空間相關(guān)性，正是這些相關(guān)性為數(shù)據(jù)的有效壓縮提供了依據(jù)。這里依據(jù)傳感器節(jié)點(diǎn)采集到的數(shù)據(jù)具有時(shí)間相關(guān)性和空間相關(guān)性，提出一種基于曲線擬合的小波壓縮算法，并采用網(wǎng)絡(luò)仿真軟件，對提出的數(shù)據(jù)壓縮算法進(jìn)行仿真實(shí)驗(yàn)，選取的評價(jià)指標(biāo)為壓縮比和均方誤差。仿真結(jié)果表明，該算法在對無線傳感器網(wǎng)絡(luò)采集到的數(shù)據(jù)進(jìn)行數(shù)據(jù)壓縮時(shí)具有較高的壓縮比，能夠有效地減少數(shù)據(jù)傳輸量，并且在數(shù)據(jù)恢復(fù)方面精度較高。

1 小波數(shù)據(jù)壓縮

1.1 曲線擬合

由于同一傳感器節(jié)點(diǎn)在不同時(shí)刻采集到的數(shù)據(jù)為離散時(shí)間序列，為了便于研究，這里采用曲線擬合的方法將離散信號轉(zhuǎn)換為連續(xù)信號。常用的曲線擬合方法有最小二乘法、基于RBF 的曲線擬合法和三次樣條曲線擬合法[7]。其中，最小二乘法邏輯推導(dǎo)比較簡單，并且具有計(jì)算量小的特點(diǎn)，被廣泛應(yīng)用在多項(xiàng)式曲線或直線的擬合問題上。使用最小二乘法進(jìn)行曲線擬合時(shí)，需要注意選取合適的匹配函數(shù)模式。

傳感器節(jié)點(diǎn)采集的溫度數(shù)據(jù)如圖1 所示，縱坐標(biāo)是用十進(jìn)制表示的溫度數(shù)據(jù)值，橫坐標(biāo)是選取的溫度數(shù)據(jù)樣本數(shù)。由圖1 可以看出，傳感器節(jié)點(diǎn)采集的數(shù)據(jù)呈現(xiàn)多項(xiàng)式的變化規(guī)律，因此，可以用式（1）多項(xiàng)式進(jìn)行擬合：

圖1 節(jié)點(diǎn)采集的原始數(shù)據(jù)分布

為了使擬合后的數(shù)據(jù)與原始數(shù)據(jù)之間誤差盡可能小，這里選取了三種不同次數(shù)的多項(xiàng)式進(jìn)行擬合，并分析各自的誤差情況。其中，誤差大小用誤差平方和來衡量，其定義如式（2）所示：

圖2 不同次數(shù)多項(xiàng)式擬合結(jié)果

誤差平方和是評價(jià)一條曲線擬合效果好壞的重要指標(biāo)，誤差平方和越小，則該曲線的擬合效果越好；誤差平方和越大，則該曲線的擬合效果越差。使用上述三種不同次數(shù)的多項(xiàng)式擬合結(jié)果如表1所示。

表1 不同次數(shù)多項(xiàng)式擬合誤差

從圖2 以及表1 可以看出，用最小二乘法進(jìn)行數(shù)據(jù)擬合時(shí)，擬合結(jié)果與實(shí)際數(shù)據(jù)之間存在一定誤差，并且選取的多項(xiàng)式次數(shù)較小時(shí)，誤差較大；選取的多項(xiàng)式次數(shù)較大時(shí)，誤差較小。這是因?yàn)檫x取的多項(xiàng)式次數(shù)較小時(shí)，各數(shù)據(jù)點(diǎn)之間距離較遠(yuǎn)，誤差也就較大。在該實(shí)驗(yàn)中，多項(xiàng)式擬合的誤差平方和隨著擬合多項(xiàng)式次數(shù)的增加而逐漸減小，在多項(xiàng)式次數(shù)選取為十五時(shí)，誤差最小，擬合曲線更接近實(shí)際數(shù)據(jù)，擬合更準(zhǔn)確。

1.2 小波壓縮

傳感器節(jié)點(diǎn)在不同時(shí)刻采集到的數(shù)據(jù)具有極大的相似性，處理這些數(shù)據(jù)常用的方法有傅里葉變換、K-L 變換等。隨著研究的深入，越來越多的變換域算法開始應(yīng)用于無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮，如離散余弦變換和小波變換等。小波變換數(shù)據(jù)壓縮算法相較于其他的變換域數(shù)據(jù)壓縮算法有著分解效果更好和運(yùn)算結(jié)構(gòu)單一的特點(diǎn)[8-9]。

Haar 小波基函數(shù)是小波變換中最簡單的基函數(shù)，它的函數(shù)集由多個(gè)分段函數(shù)組成，并且這個(gè)分段函數(shù)是常值函數(shù)，在區(qū)間[0,1)上一段為1，一段為0。Haar 小波變換的過程是求均值和差值的過程[10]，對于長度為2n的信號sn={sn,l|0 ≤l＜2n}，將求均值和差值應(yīng)用到a=sn,2l,b=sn,2l+1(l=0,1,…,2n-1-1)中。記，則多級Haar 小波變換的分解過程和重構(gòu)過程可用圖3 表示。

圖3 小波變換的分解和重構(gòu)過程

利用上述Harr 小波變換算法對傳感器采集的數(shù)據(jù)進(jìn)行三次小波分解后的空間-頻率結(jié)構(gòu)如圖4 所示。小波變換具有大部分有用信息集中在低頻系數(shù)，而小部分細(xì)節(jié)信息集中在高頻系數(shù)的特點(diǎn)[11]。在圖4 中，經(jīng)過擬合后的信號被分為四個(gè)部分，其中，H0、H1、H2 是高頻部分，L2 是低頻部分。對高頻部分的系數(shù)進(jìn)行閾值處理，將絕對值小于閾值的高頻系數(shù)設(shè)置為零，絕對值大于閾值的高頻系數(shù)保持不變。為了將閾值處理后的小波系數(shù)進(jìn)行編碼壓縮，首先將小波系數(shù)整數(shù)化，采用的取整方法是向下取整法。假設(shè)某小波系數(shù)為3.671 2，則向下取整后為3。要獲取傳感器采集的數(shù)據(jù)的主要信息只需存儲(chǔ)取整后的小波系數(shù)即可，而通過算術(shù)編碼的方法存儲(chǔ)小波系數(shù)在提高數(shù)據(jù)恢復(fù)準(zhǔn)確率的同時(shí)還可以進(jìn)一步壓縮存儲(chǔ)空間。

圖4 信號被分解后的頻率結(jié)構(gòu)

2 Haar小波系數(shù)的編碼

對進(jìn)行Haar 變換后的小波系數(shù)進(jìn)行編碼，需要在保證數(shù)據(jù)質(zhì)量的前提下提高壓縮率，而哈夫曼編碼正好滿足這一條件。哈夫曼編碼是根據(jù)信源中各符號出現(xiàn)的概率進(jìn)行編碼，出現(xiàn)概率大的符號使用較短的碼字，出現(xiàn)概率小的符號使用較長的碼字[12]。舉例來說，假設(shè)某信源產(chǎn)生五種符號u1、u2、u3、u4 和u5，它們各自的概率分別為P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。編碼過程：進(jìn)行編碼前首先將各符號按照概率由大到小的次序排隊(duì)，編碼時(shí)，從最小概率的兩個(gè)符號開始，將上支路設(shè)為0，下支路設(shè)為1。然后將兩個(gè)已編碼支路的概率相加，并重新排隊(duì)。以此類推，不斷使用上述方法，直到相加概率為1 時(shí)結(jié)束。此時(shí)，按照每個(gè)符號的支路路徑可以得出各自的編碼結(jié)果。u1、u2、u3、u4 和u5 的編碼結(jié)果即為000101011011。

為了存儲(chǔ)方便同時(shí)進(jìn)一步壓縮存儲(chǔ)空間，對經(jīng)過傳統(tǒng)哈夫曼編碼后的結(jié)果按一定位數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)后再存儲(chǔ)，這里選取的數(shù)據(jù)位數(shù)為8 位，不足8位的在前面用0 補(bǔ)齊，則上述假設(shè)中的最終編碼結(jié)果為2111，進(jìn)一步壓縮了數(shù)據(jù)位數(shù)。

改進(jìn)哈夫曼編碼算法的實(shí)現(xiàn)過程：首先，統(tǒng)計(jì)原始數(shù)據(jù)中各字符出現(xiàn)的概率，然后，將這些字符按照出現(xiàn)概率的降序排列，并依此建立哈夫曼樹，將哈夫曼樹的索引結(jié)果存入各字符的編碼結(jié)果中，最后，使用進(jìn)制轉(zhuǎn)換將一定位數(shù)的二進(jìn)制編碼轉(zhuǎn)換為十進(jìn)制編碼即為最終編碼結(jié)果。其算法實(shí)現(xiàn)流程圖如圖5 所示。

圖5 哈夫曼算法實(shí)現(xiàn)流程圖

3 實(shí)驗(yàn)與分析

該實(shí)驗(yàn)采用的是英特爾伯克利實(shí)驗(yàn)室54 個(gè)傳感器中的3 個(gè)在不同時(shí)刻采集到的數(shù)據(jù)，這些傳感器分布在實(shí)驗(yàn)室的不同位置，每個(gè)傳感器每隔31 s采集一次數(shù)據(jù)，采集的數(shù)據(jù)包括溫度、濕度、光照和電壓[13]。提取其中的溫度數(shù)據(jù)作為數(shù)據(jù)源進(jìn)行實(shí)驗(yàn)，圖1 是原始溫度數(shù)據(jù)與樣本數(shù)的關(guān)系圖，由圖1 可以看出節(jié)點(diǎn)采集的溫度數(shù)據(jù)呈逐漸下降的趨勢。

3.1 比較不同算法的壓縮比

將以上3 個(gè)不同傳感器采集到的數(shù)據(jù)保存為不同的txt文件，分別命名為1.txt、2.txt、3.txt。對這些txt 文件采用不同的壓縮算法進(jìn)行壓縮測試，測試環(huán)境為Matlab2016a,測試結(jié)果如表2 所示。

表2 不同壓縮算法壓縮比

定義壓縮比概念為：

由表2 可以看出，改進(jìn)算法的壓縮比最大，可以獲得平均7.09 的壓縮比。相比小波壓縮算法以及哈夫曼編碼方法，改進(jìn)算法提取了兩種算法的優(yōu)勢之處，并對編碼后的結(jié)果進(jìn)行了二次壓縮，因此具有相對較高的壓縮比。

3.2 比較不同算法的均方誤差

均方誤差反映了重構(gòu)數(shù)據(jù)與原始數(shù)據(jù)的相似程度，均方誤差越小表明重構(gòu)的數(shù)據(jù)越精確。

均方誤差的概念如下：設(shè)原始信號S={X(t)|t=1,2,3,…,k},S*={X*(t)|t=1,2,3,…,k}為一個(gè)估計(jì)信號，則該估計(jì)信號的均方誤差如式（4）所示。

表3 是三種不同壓縮算法的均方誤差。

表3 不同壓縮算法均方誤差

由表3 可以看出，三種算法的均方誤差里哈夫曼編碼算法的誤差最小，這是因?yàn)楣蚵幋a是無損數(shù)據(jù)壓縮技術(shù)，而哈夫曼編碼算法的誤差主要來源于曲線擬合時(shí)的誤差。小波壓縮算法是有損數(shù)據(jù)壓縮技術(shù)，其誤差來源有曲線擬合時(shí)的誤差、小波系數(shù)閾值處理以及取整時(shí)的誤差。因此，小波壓縮算法和改進(jìn)算法的誤差基本持平，稍大于哈夫曼編碼算法。在對數(shù)據(jù)恢復(fù)精度要求不高的情況下，使用改進(jìn)算法更為合適，因其具有更大的數(shù)據(jù)壓縮比。

4 結(jié)論

針對無線傳感器網(wǎng)絡(luò)在數(shù)據(jù)采集時(shí)存在的大量冗余數(shù)據(jù)問題[14-16]，提出了一種基于改進(jìn)哈夫曼編碼的Haar 小波WSN 數(shù)據(jù)壓縮算法。首先對這些數(shù)據(jù)進(jìn)行線性擬合，然后經(jīng)過小波變換提取出相應(yīng)的小波系數(shù)后，采用哈夫曼編碼的方式將原始數(shù)據(jù)轉(zhuǎn)換為一串二進(jìn)制編碼。進(jìn)一步地，為了達(dá)到更好的壓縮效果，將這些二進(jìn)制編碼串按一定位數(shù)轉(zhuǎn)換為十進(jìn)制編碼串。仿真實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)小波壓縮算法數(shù)據(jù)壓縮率提高了大約34%，而均方誤差基本持平。該算法可以應(yīng)用于對數(shù)據(jù)壓縮比要求比較高的場景，但是由于所提算法在進(jìn)行線性擬合時(shí)采用的是傳統(tǒng)的擬合方法，擬合精度還有待提高。未來可考慮與神經(jīng)網(wǎng)絡(luò)結(jié)合，進(jìn)一步提高擬合精度，進(jìn)而減小均方誤差。