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

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

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

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

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

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

1.1 曲線擬合

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

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

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

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

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

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

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

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

1.2 小波壓縮

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

Haar 小波基函數(shù)是小波變換中最簡單的基函數(shù)，它的函數(shù)集由多個分段函數(shù)組成，并且這個分段函數(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ù)進行三次小波分解后的空間-頻率結(jié)構(gòu)如圖4 所示。小波變換具有大部分有用信息集中在低頻系數(shù)，而小部分細節(jié)信息集中在高頻系數(shù)的特點[11]。在圖4 中，經(jīng)過擬合后的信號被分為四個部分，其中，H0、H1、H2 是高頻部分，L2 是低頻部分。對高頻部分的系數(shù)進行閾值處理，將絕對值小于閾值的高頻系數(shù)設(shè)置為零，絕對值大于閾值的高頻系數(shù)保持不變。為了將閾值處理后的小波系數(shù)進行編碼壓縮，首先將小波系數(shù)整數(shù)化，采用的取整方法是向下取整法。假設(shè)某小波系數(shù)為3.671 2，則向下取整后為3。要獲取傳感器采集的數(shù)據(jù)的主要信息只需存儲取整后的小波系數(shù)即可，而通過算術(shù)編碼的方法存儲小波系數(shù)在提高數(shù)據(jù)恢復準確率的同時還可以進一步壓縮存儲空間。

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

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

對進行Haar 變換后的小波系數(shù)進行編碼，需要在保證數(shù)據(jù)質(zhì)量的前提下提高壓縮率，而哈夫曼編碼正好滿足這一條件。哈夫曼編碼是根據(jù)信源中各符號出現(xià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。編碼過程：進行編碼前首先將各符號按照概率由大到小的次序排隊，編碼時，從最小概率的兩個符號開始，將上支路設(shè)為0，下支路設(shè)為1。然后將兩個已編碼支路的概率相加，并重新排隊。以此類推，不斷使用上述方法，直到相加概率為1 時結(jié)束。此時，按照每個符號的支路路徑可以得出各自的編碼結(jié)果。u1、u2、u3、u4 和u5 的編碼結(jié)果即為000101011011。

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

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

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

3 實驗與分析

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

3.1 比較不同算法的壓縮比

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

表2 不同壓縮算法壓縮比

定義壓縮比概念為：

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

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}為一個估計信號，則該估計信號的均方誤差如式（4）所示。

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

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

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

4 結(jié)論

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