一種自適應Huffman算法在無線傳感器網絡數據壓縮中的應用

劉 政，狄 佳

(重慶理工大學計算機科學與工程學院，重慶 400054)

由于系統的靈活性和應用的多樣性，無線傳感器網絡(WSN)的應用越來越廣泛。無線傳感器網絡中的傳感器節點用來處理和收集信息，節點之間要進行相互通信，并將數據傳輸到基站。無線傳感器節點一般包括傳感器、微控制器、通信模塊和電源。

無線傳感器網絡(WSN)通過傳感器節點之間的相互通信來共同完成一項任務。資源的利用效率在WSN中被認為是一個很重要的問題，因為較高的資源利用效率可以延長了網絡的使用壽命［1］。傳感器節點的資源消耗主要集中在處理和傳輸過程中。資源消耗最多的是通信模塊，所占比例為60%～80%。通過數據壓縮可以減少發送的比特數，從而降低能耗。然而有研究表明，無線電通信中所使用的硬件類型對數據壓縮的執行效果有很大的影響［3］。

在許多無線傳感器網絡應用(如一個特定的參數或事件跟蹤監測)中，傳感器的工作與實時性高度相關［4］。為了減少傳輸的比特數，需要采用更有效的壓縮技術來處理由傳感器獲得的連續數據之間的差異。因此，新的數據是通過以前的數據和新的數據之間的差異獲得的，這種差異遠小于實際數據，可以用較低的比特數編碼。

WSN的應用程序需要多個傳感器的密集部署協同工作，因此多個傳感器對某一單個事件的發生都會有記錄信息。由于高的空間相關性的存在，將每個傳感器節點的冗余信息都發送到匯聚節點是不必要的。相反，數量較少的傳感器則可能有足夠的信息溝通渠道，并具有一定的可靠性［5］。反復利用現有的相關性，以自適應信號處理和分布式信源編碼原則為基礎，對傳感器數據的分配方式進行研究，提出了基于自適應Huffman算法和數據存儲的空間相關性的數據壓縮算法。壓縮算法主要用于數據存儲，因此，對于資源有限的傳感器節點，要求有簡單和具體的應用程序。簡單的以靜態Huffman編碼為基礎的壓縮算法特別適合內存和計算資源都有限的無線傳感器節點。該算法利用了傳感器數據之間存在的局部相關性，通過一個簡單的數據字典計算出一個壓縮版本。為了設計數據字典，需要統計不同的實時數據，數據統計的改變將依賴于所發生的事件［6］。

1 算法介紹

在WSN中可以實現多種壓縮算法。例如:LZW算法是基于數據字典的壓縮算法;S-LZW算法將未壓縮的輸入比特流分成固定大小的塊，然后分別對每塊進行壓縮，對于每個塊，數據字典通過使用標準字符集對塊進行重新初始化。另一個重要的算法是自適應Huffman算法。它通過有節點和葉子的樹型結構的象征符號來表示傳播模式。在傳輸開始時，源序列的統計數據是未知的。隨著數據傳輸的進行，將新的節點添加到樹中，對樹進行重新配置。在遍歷樹的路徑后，如果目前的值在當前的樹中存在，其編碼可以通過遍歷樹的路徑獲得［7］。改進的自適應 Huffman 算法［8］與自適應Huffman算法的結構相同，但樹的葉子代表的是相同的頻率，而不是個別的符號或符號集。靜態Huffman算法［8］是一個簡單的壓縮算法，減少了WSN節點上的內存和計算所消耗的資源。該算法利用了Huffman壓縮以及預先設定的概率表。

2 適合WSN的Huffman編碼算法

2.1 簡單的Huffman算法

簡單的Huffman算法可以減少無線傳感器網絡節點的內存和計算所消耗的資源。算法使用了一個較小的數據字典，其大小由模擬到數字轉換器(ADC)的決議所決定［9］。每一個值通過傳感器測試后獲得，其中mi由ADC輸入并與R決議有關。通過轉換器后，對mi的測試轉化為二進制所代表的類型，ri在R位。對于每一個獲得的新值mi，壓縮算法編碼2個連續值的差異，di=riri－1。假設為了計算 d0，r－1等于 2R的可能離散值的中間值。無損壓縮是根據其統計特性執行的，di的差異將被編碼得更加緊湊。

用bit序列來表示bsi，由2部分組成:第1位的序列si通過編纂ni的數量bit來表示;第2位的序列ai用di的二進制來表示。在di=0的情況下ni的值是0。對于任何其他的不同情況，ni的值為ni=［log2(|di|)］。因此，ni的最大值會等于 R。對ni執行Huffman編碼，si代碼產生一個可變長度的特征符號。所有的Huffman編碼算法的思路是分配更短的數據值表示更頻繁出現的數據，解決的辦法是為出現的字母繪制一個字母表，這是一個可變大小的位序列。在這種特定的情況下，其符號為R+1，隨著其值的增加，其出現的可能性下降。第2位的序列是bsi，ai是可變長度的代碼，根據di值可以通過3種方法產生:

1)當di＞0時，ai是由2個2的補碼表示的ni的低階位描述;

2)當di＜0時，ai通過 ni描繪 di－1的補碼表示低序位;

3)當di=0時，ai沒有代表的意義，并且si的編碼為00。

此過程用來確定ai，確保所有可能出現的不同的值有不同的碼字。當bsi序列產生時，ai序列附著在該bit流的尾端，共同構成了壓縮版本的mi測試序列。

2.2 動態Huffman算法

靜態Huffman算法有著明顯的缺點，即傳入數據源的出現概率是未知的，概率的分配是根據數據之間值的差異進行的，因此，一旦差異增長，概率值就會變小。此外，差異較小的值將以較小的比特流編碼，較大的值將以較大的比特流編碼。

動態Huffman算法不遵循自適應的Huffman算法所表述的不同類型的樹模型結構。與靜態Huffman算法一樣，它開始以默認的概率差進行通信，但是，隨著數據的傳送到達，會將傳入元素的出現概率更新，并將高概率出現的值分配給小規模的數據流位。

bsi的序列組成中第1部分仍然相同，只是si字典發生了一些變化:用2位代碼位對ni=1進行編碼，而不是3位。在ni＞4時向bit序列中增加1位，ni=1時在傳入的值概率很高時增加1位序列。最后字典D如表1所示。給出的例子是10位編碼，它增加或減少的可能性取決于數據精度。

根據其概率值進行差異更新，本文考慮2個向量:q［j］包括所有的差異di值，可以在字典D中找到;p［j］包含從q［j］發生到輸入時的數量差異，并需要考慮j的值。

在初始化時，q［j］有以下表示:

q［j］的值可以根據 j獲得:

表1 用于壓縮的字典D

例如，q［j］的第6 個元素 q［5］=(5+1)/2=3，q［j］的第7 個元素 q［6］= －6/2= － 3。對于p［j］，默認值是 0，而且隨著值傳入 q［j］，p［j］的值會加1。

在傳輸中，di=ri－ ri－1之間的差異是由當前的數據和以前的由傳感器獲得的數據計算得到的。這種差異是在向量q［j］中被搜索到的，而且j的值會被保存。j被應用在式(1)或(2)中，而且q［j］的值在初始化時就存在。基于數據字典，這個值會被編碼并傳輸到接收器部分。發射器和接收器有相同的數據字典，以同樣的方式對向量q［j］和 p［j］進行更新。當 q［j］=di時，j所對應的p［j］值增 1。完成這種改變后，向量 p［j］的值重新向下排列。同時，向量 p［j］重新整理后，q［j］也根據j的值重新排列。

一旦數據到達，則接收器接收解碼，并找到q［j］在初始化時的值。然后得到的 qinit［j］的值，并被應用在式(1)或(2)中，于是j的值也找到了。根據j的值，q［j］的值被提取出來，并且該值代表數據傳輸之間的差異。最后，向量 p［j］和q［j］被更新。因此，di的編碼字長度的改變是永久的，并且是要基于所傳入的值。這種方式中高概率的差異是由較小規模的比特流來編碼的。動態哈夫曼算法流程如圖1所示。

圖1 動態哈夫曼算法流程

傳送開始時，第1個值開始傳送。當第2個值開始傳送時，算法開始執行，算法開始計算實際值和前一個值之間的差異。

圖1 中的〈si，ai〉表示 si和 ai的聯系，〈y2|ni〉為用2的補碼表示y的ni低階位。

例如，考慮 qi［j］的值和 pi［j］的值可從表 2 中得到。可以注意到，qi［2］的值是3，而且這種差異到現在為止已經出現過5次。

假設，r24－ r23=3(10)，值 3 可以在 qi［j］序列中找到，并且得到 j=2。然后，可以從最初的qinit［j］序列中得到對應j=2的值，并應用到式(1)或式(2)中，得到qinit［2］=－1。此值被編碼并傳送到接收器端。接收端將輸入值－1代入式(1)或(2)，并根據得到的值索引j=2，然后，搜索序列qi［j］得到 qi［2］的值，并得到傳送差異為 3。因此，值的差異為3，被編碼為－1，并且被1位保存。在步驟 i，p［2］=p［1］=5。在步驟 i+1，值 3 出現之后，p［2］的值增1。在該情況下，更新之前，p［2］=6 ＞ p［1］。向量 p［j］在得到值后向下重新配置。同時，向量 q［j］在 p［j］之后根據 j的值重新配置。

表2 q［j］和 p［j］的例子 3 實驗結果

在Visual Basic平臺上進行了模擬。靜態Huffman算法和動態Huffman算法都得以實現。對算法的性能進行了分析，其中傳輸的比特數只是指那些對應的值，不包括數據包封裝相應的位。

試驗采用了3組數據。前2組數據代表在1天內收集到的電站發電機周圍環境的高度相關的溫度值。第1組是當溫度升高時由當天第1部分記錄的140個值所組成，第2組為1天記錄的第2部分由溫度降低時收集的140個值組成。靜態、動態霍夫曼編碼及未壓縮的數據之間的比較如圖2所示。考慮到在6～11℃的分辨率在0.1℃，未壓縮的數據可以是最小的6位編碼，因此，傳輸未壓縮140位值的總消耗是840位。從圖2可以看出，動態Huffman壓縮后傳輸的比特數是小于靜態Huffman壓縮后傳輸的比特數。與未壓縮的數據相比較，2種方法所需傳輸的比特5數量小得多。動態霍夫曼的執行類似，并且其對這2組數據的處理有更好的效果。

圖2 數據集1和數據集2傳送數據的bit數

為了對該算法有一個更好地了解，對一些相關較低的數據也進行了比較。第3組數據表示2010年全年所搜集到的介質的溫度值(365個值)。圖3所示未壓縮的數據大小是經過霍夫曼算法的結果。在溫度值為－20℃ ～35℃時通過采用一個合適的解決策略，在6位的基礎上進行數據采集。可以看出，相比靜態Huffman，動態霍夫曼獲得更好的結果，在解壓縮數據時也有同樣的效果。數據均由重慶匯能達電子有限公司提供［7］。

圖3 數據集3傳送數據的bit數

動態霍夫曼算法和靜態霍夫曼算法對3組數據的壓縮比如圖4所示。壓縮比的計算公式為［3］

其中:Cr是壓縮比;Cs是壓縮的大小;Os代表原始大小。

由圖4可以看出，動態霍夫曼獲得的壓縮比是約55%，靜態霍夫曼獲得壓縮比在45%左右。對于數據集3相關度較低的數據，其壓縮比小于前2個的分析結果。然而，即使在這種情況下，動態Huffman算法仍存在優勢:相對于應用靜態Huffman方法的30%的壓縮比，動態霍夫曼有近40%的壓縮比。傳送的bit數量與所消耗的資源緊密相關。10%的數據壓縮的增益可以顯著延長任何系統的使用時間，尤其是無線傳感器網絡。

圖4 壓縮比例

添加到靜態Huffman算法的指令的數量約為幾十條，依賴數組中的數據索引地址。該數量可以容納100條指令，但這種情形只有在很少的情況下出現，如連續2個數據之間的差異非常高時。對于140個高度相關的bit量，其增益大約是70位。對比文獻［3］的結果，處理過程中節省的70位所消耗的能量相當于傳輸2個比特的消耗。最后仍有超過60位可以保存，節省了很多資源。

3 結束語

本文提出了一個基于時空相關性和Huffman編碼的數據壓縮算法。在傳輸的比特數和壓縮比方面對該算法的性能進行分析，并與靜態Huffman算法進行了比較。結果表明，在所有的測試中，本文所提出的算法執行效果更好。雖然動態Huffman算法在進行處理時需要更多的資源，但其后得到的壓縮增益效果使得它適合用于WSN。

［1］Sadler C M，Martonosi M.Data compression clgorithms for energy-constrained devices in delay tolerant networks［C］//Proc.SenSys:4th Int.Conference on Embedded networked sensor systems.USA: ［s.n.］，2006:265－278.

［2］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks:a survey［J］.Computer Networks，2002，38:393 －422.

［3］Barr K C，Asanovic K.Energy-aware lossless data compression［J］.ACM Transactions on Computer Systems，2006，24(3):250 －291.

［4］張鳳林，劉思峰 一個改進的Huffman數據壓縮算法［J］.計算機工程與應用，2007，43(2):73.

［5］Akyildiz I F，Vuran M C，Akan A B.On exploiting spatial and temporal correlation in Wireless Sensor Networks［C］//Proceedings of WiOpt 2004:Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks.USA:［s.n.］，2004.

［6］Lin M B，Lee J F，Jan G E.A lossless data compression and decompression algorithm and its hardware architecture［J］.IEEE Trans.Very Large Scale Integrat Syst，2004，14:925 －936.

［7］方敏，秦曉新，劉本喜.動態Huffman編碼的數據壓縮方法［J］.計算機世界，1999(7):16－19.

［8］嚴劍.Huffman算法及其在數據壓縮中的應用［J］.計算機與現代化，1996(4):15－19.

［10］Marcelloni F，Vecchio M.A simple algorithm for data Compression in wireless sensor networks［J］.IEEE Commun Lett，2008，12:411 －413.