劉 政，狄 佳

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

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

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

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

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

1 算法介紹

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

2 適合WSN的Huffman編碼算法

2.1 簡(jiǎn)單的Huffman算法

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

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

1)當(dāng)di＞0時(shí)，ai是由2個(gè)2的補(bǔ)碼表示的ni的低階位描述;

2)當(dāng)di＜0時(shí)，ai通過(guò) ni描繪 di－1的補(bǔ)碼表示低序位;

3)當(dāng)di=0時(shí)，ai沒(méi)有代表的意義，并且si的編碼為00。

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

2.2 動(dòng)態(tài)Huffman算法

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

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

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

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

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

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

表1 用于壓縮的字典D

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

在傳輸中，di=ri－ ri－1之間的差異是由當(dāng)前的數(shù)據(jù)和以前的由傳感器獲得的數(shù)據(jù)計(jì)算得到的。這種差異是在向量q［j］中被搜索到的，而且j的值會(huì)被保存。j被應(yīng)用在式(1)或(2)中，而且q［j］的值在初始化時(shí)就存在?；跀?shù)據(jù)字典，這個(gè)值會(huì)被編碼并傳輸?shù)浇邮掌鞑糠?。發(fā)射器和接收器有相同的數(shù)據(jù)字典，以同樣的方式對(duì)向量q［j］和 p［j］進(jìn)行更新。當(dāng) q［j］=di時(shí)，j所對(duì)應(yīng)的p［j］值增 1。完成這種改變后，向量 p［j］的值重新向下排列。同時(shí)，向量 p［j］重新整理后，q［j］也根據(jù)j的值重新排列。

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

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

傳送開(kāi)始時(shí)，第1個(gè)值開(kāi)始傳送。當(dāng)?shù)?個(gè)值開(kāi)始傳送時(shí)，算法開(kāi)始執(zhí)行，算法開(kāi)始計(jì)算實(shí)際值和前一個(gè)值之間的差異。

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

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

假設(shè)，r24－ r23=3(10)，值 3 可以在 qi［j］序列中找到，并且得到 j=2。然后，可以從最初的qinit［j］序列中得到對(duì)應(yīng)j=2的值，并應(yīng)用到式(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］在得到值后向下重新配置。同時(shí)，向量 q［j］在 p［j］之后根據(jù) j的值重新配置。

表2 q［j］和 p［j］的例子 3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

圖4 壓縮比例

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

3 結(jié)束語(yǔ)

本文提出了一個(gè)基于時(shí)空相關(guān)性和Huffman編碼的數(shù)據(jù)壓縮算法。在傳輸?shù)谋忍財(cái)?shù)和壓縮比方面對(duì)該算法的性能進(jìn)行分析，并與靜態(tài)Huffman算法進(jìn)行了比較。結(jié)果表明，在所有的測(cè)試中，本文所提出的算法執(zhí)行效果更好。雖然動(dòng)態(tài)Huffman算法在進(jìn)行處理時(shí)需要更多的資源，但其后得到的壓縮增益效果使得它適合用于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］張鳳林，劉思峰 一個(gè)改進(jìn)的Huffman數(shù)據(jù)壓縮算法［J］.計(jì)算機(jī)工程與應(yīng)用，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］方敏，秦曉新，劉本喜.動(dòng)態(tài)Huffman編碼的數(shù)據(jù)壓縮方法［J］.計(jì)算機(jī)世界，1999(7):16－19.

［8］嚴(yán)劍.Huffman算法及其在數(shù)據(jù)壓縮中的應(yīng)用［J］.計(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.