一種自適應Huffman算法在無線傳感器網(wǎng)絡數(shù)據(jù)壓縮中的應用

劉 政，狄 佳

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

由于系統(tǒng)的靈活性和應用的多樣性，無線傳感器網(wǎng)絡(WSN)的應用越來越廣泛。無線傳感器網(wǎng)絡中的傳感器節(jié)點用來處理和收集信息，節(jié)點之間要進行相互通信，并將數(shù)據(jù)傳輸?shù)交尽o線傳感器節(jié)點一般包括傳感器、微控制器、通信模塊和電源。

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

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

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

1 算法介紹

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

2 適合WSN的Huffman編碼算法

2.1 簡單的Huffman算法

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

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

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

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

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

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

2.2 動態(tài)Huffman算法

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

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

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

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

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

q［j］的值可以根據(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之間的差異是由當前的數(shù)據(jù)和以前的由傳感器獲得的數(shù)據(jù)計算得到的。這種差異是在向量q［j］中被搜索到的，而且j的值會被保存。j被應用在式(1)或(2)中，而且q［j］的值在初始化時就存在。基于數(shù)據(jù)字典，這個值會被編碼并傳輸?shù)浇邮掌鞑糠帧０l(fā)射器和接收器有相同的數(shù)據(jù)字典，以同樣的方式對向量q［j］和 p［j］進行更新。當 q［j］=di時，j所對應的p［j］值增 1。完成這種改變后，向量 p［j］的值重新向下排列。同時，向量 p［j］重新整理后，q［j］也根據(jù)j的值重新排列。

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

圖1 動態(tài)哈夫曼算法流程

傳送開始時，第1個值開始傳送。當?shù)?個值開始傳送時，算法開始執(zhí)行，算法開始計算實際值和前一個值之間的差異。

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

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

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

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

在Visual Basic平臺上進行了模擬。靜態(tài)Huffman算法和動態(tài)Huffman算法都得以實現(xiàn)。對算法的性能進行了分析，其中傳輸?shù)谋忍財?shù)只是指那些對應的值，不包括數(shù)據(jù)包封裝相應的位。

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

圖2 數(shù)據(jù)集1和數(shù)據(jù)集2傳送數(shù)據(jù)的bit數(shù)

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

圖3 數(shù)據(jù)集3傳送數(shù)據(jù)的bit數(shù)

動態(tài)霍夫曼算法和靜態(tài)霍夫曼算法對3組數(shù)據(jù)的壓縮比如圖4所示。壓縮比的計算公式為［3］

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

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

圖4 壓縮比例

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

3 結束語

本文提出了一個基于時空相關性和Huffman編碼的數(shù)據(jù)壓縮算法。在傳輸?shù)谋忍財?shù)和壓縮比方面對該算法的性能進行分析，并與靜態(tài)Huffman算法進行了比較。結果表明，在所有的測試中，本文所提出的算法執(zhí)行效果更好。雖然動態(tài)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數(shù)據(jù)壓縮算法［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］方敏，秦曉新，劉本喜.動態(tài)Huffman編碼的數(shù)據(jù)壓縮方法［J］.計算機世界，1999(7):16－19.

［8］嚴劍.Huffman算法及其在數(shù)據(jù)壓縮中的應用［J］.計算機與現(xiàn)代化，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.