基于改進哈夫曼編碼的Haar 小波WSN 數據壓縮算法

夏長權，徐思韻，張劍云，時壯壯，朱金榮

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

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

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

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

1 小波數據壓縮

1.1 曲線擬合

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

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

圖1 節點采集的原始數據分布

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

圖2 不同次數多項式擬合結果

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

表1 不同次數多項式擬合誤差

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

1.2 小波壓縮

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

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

圖3 小波變換的分解和重構過程

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

圖4 信號被分解后的頻率結構

2 Haar小波系數的編碼

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

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

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

圖5 哈夫曼算法實現流程圖

3 實驗與分析

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

3.1 比較不同算法的壓縮比

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

表2 不同壓縮算法壓縮比

定義壓縮比概念為：

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

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

均方誤差反映了重構數據與原始數據的相似程度，均方誤差越小表明重構的數據越精確。

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

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

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

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

4 結論

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