無線傳感器網(wǎng)絡(luò)基于時空差分閾值Huffman數(shù)據(jù)壓縮

，，

(湖北大學(xué) 計算機與信息工程學(xué)院，武漢 430062)

0 引言

傳感器網(wǎng)絡(luò)[1]由大量的傳感器節(jié)點隨機部署在空間中組成的，單個節(jié)點主要組成模塊包括數(shù)據(jù)采集模塊、通信模塊、電源管理模塊。由于節(jié)點的能量、存儲、通信距離有限,為了減少節(jié)點在數(shù)據(jù)傳輸?shù)倪^程中消耗的能量[2]和節(jié)點無休眠的工作消耗的能量，采用了對節(jié)點有限時間內(nèi)自適應(yīng)采集的數(shù)據(jù)與數(shù)據(jù)壓縮的方式。該方式不僅減少了相對應(yīng)數(shù)據(jù)的傳輸量[3]，而且減少了節(jié)點能量的消耗；此時通過傳感器網(wǎng)絡(luò)中節(jié)點不同時刻和不同位置采集的數(shù)據(jù)具有一定的時空相關(guān)性[4]，以及傳感器節(jié)點對自身采集的數(shù)據(jù)可以通過硬件功能進行處。然而無線傳感器網(wǎng)絡(luò)中的節(jié)點在同一片區(qū)域采集的數(shù)據(jù)具有相對變化較小的特性，對該處理的數(shù)據(jù)將進行無損壓縮[5]，并要求傳送的數(shù)據(jù)(如：溫度，濕度)精確到一定程度。本文提出了一種基于時空差分后Huffman的數(shù)據(jù)無損壓縮算法。該方案采用單個節(jié)點自身對數(shù)據(jù)采集和處理，處理后進行編碼傳輸，節(jié)點的傳輸數(shù)據(jù)大量減少[6]，同時也能將壓縮的數(shù)據(jù)進行還原。因此減少了節(jié)點發(fā)送的數(shù)據(jù)量和網(wǎng)絡(luò)中的通信流量[7]，并延長網(wǎng)絡(luò)生命。

Steffen[8]提出了一種自適應(yīng)壓縮大型矢量的方案，該方案對節(jié)點自身的處理數(shù)據(jù)要求非常高，然而節(jié)點采用的處理方式速度較慢，加大了處理數(shù)據(jù)的時間，數(shù)據(jù)不能及時發(fā)送，也未達到節(jié)約能耗。Ikjune Yoon[9]提出了無線傳感器網(wǎng)絡(luò)能量采集的自適應(yīng)傳感和壓縮率選擇方案，通過電池的能量情況選擇不同的壓縮模式。該方案在開始就需要比較對壓縮方案進行選擇判斷，在節(jié)點能量較低的情況下采用低壓縮率方式，對節(jié)點的能量并沒有太多的節(jié)省。Sunyong Kim[10]提出使用能量回收的無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)壓縮延長網(wǎng)絡(luò)壽命,該方案通過簇頭對數(shù)據(jù)進行多級壓縮，然而多級壓縮過程容易導(dǎo)致樹列后節(jié)點的能量消耗過快。Francesco Marcelloni[11]提出了一種無線傳感器網(wǎng)絡(luò)監(jiān)測小節(jié)點的高效無損壓縮算法，該方案采用的LZW編碼這種擴展會產(chǎn)生更高的內(nèi)存占用，但不會明顯影響壓縮比，而且對應(yīng)于較長代碼的差異具有非常接近0的概率。

上述文獻都考慮到了壓縮節(jié)點采集的數(shù)據(jù)，然而并沒有真正在將數(shù)據(jù)量減少的情況下進行無損壓縮數(shù)據(jù)[12]，同時保證數(shù)據(jù)采集的時效性和數(shù)據(jù)的無損性。本文通過時空性使用差分器將數(shù)據(jù)差值，再將差值后的數(shù)據(jù)與閾值比較后進行Huffman編碼，最后節(jié)點將無損壓縮的數(shù)據(jù)傳遞給簇頭，再傳送給服務(wù)器，服務(wù)器接收到數(shù)據(jù)后通過疊加的方式將數(shù)據(jù)還原。由于服務(wù)器是一直供電，當(dāng)對收到的數(shù)據(jù)進行還原時并不用考慮服務(wù)器的能耗問題，通過實驗數(shù)據(jù)分析，采用差分Huffman編碼減小了節(jié)點的功耗[13]，同時也提高了數(shù)據(jù)壓縮的比率和網(wǎng)絡(luò)生命周期,并保證了節(jié)點在能量消耗保持相對穩(wěn)定。

1 數(shù)據(jù)壓縮理論

1.1 數(shù)據(jù)的時空性

無線傳感器網(wǎng)絡(luò)節(jié)點通過傳感器采集數(shù)據(jù)，并通過A/D模型將采集的模擬信號轉(zhuǎn)換成數(shù)字信號，節(jié)點發(fā)送的數(shù)據(jù)包含節(jié)點ID和節(jié)點所采集數(shù)據(jù)(圖1)。通過節(jié)點采集的數(shù)據(jù)具有一定的時間相關(guān)性，同一節(jié)點相鄰的兩個時刻采集的數(shù)據(jù)具有一定的關(guān)聯(lián)，當(dāng)相鄰時刻采集的數(shù)據(jù)不變時，可以減少大量的數(shù)據(jù)傳輸；同時，不同的節(jié)點間的數(shù)據(jù)具有一定的空間相關(guān)性，當(dāng)在一定的區(qū)域中，不同節(jié)點采集的數(shù)據(jù)具有一定的差異時，根據(jù)區(qū)域內(nèi)多個傳感器采集的數(shù)據(jù)進行比較分析，可以將大量一致的數(shù)據(jù)在矩陣中轉(zhuǎn)換成0后，再進行傳輸?shù)骄W(wǎng)關(guān)，并可以減少簇頭在傳輸時的數(shù)據(jù)。此時可以將數(shù)據(jù)放置在三維空間表示(圖2)，節(jié)點通過當(dāng)前時刻的數(shù)據(jù)與前一時刻的數(shù)據(jù)進行差值，并將同一簇類節(jié)點的數(shù)據(jù)進行比較，之后采用無損壓縮將數(shù)據(jù)傳輸給服務(wù)器。由于無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸消耗的能量與距離和放大系數(shù)有關(guān)，傳輸數(shù)據(jù)的能量遠大于處理數(shù)據(jù)所用的能量，此時傳輸數(shù)據(jù)消耗的能量[14]公式為：

ETX=mEelec+Eamp(m,d)=mEelec+mεdx

(1)

Eelec為采集1bit數(shù)據(jù)消耗的能量；Eamp為傳輸時消耗的能量，d表示節(jié)點與簇頭的距離，ε表示傳輸時與距離相關(guān)的放大倍數(shù)；

圖2 節(jié)點的時空性

1.2 一階差分方程

節(jié)點中的每一個傳感器采集到的數(shù)據(jù)不相互影響，通過差分器將現(xiàn)在時刻采集的數(shù)據(jù)與前一個時刻的數(shù)據(jù)進行差分(圖3)。多個數(shù)據(jù)同時進行并行處理并獲得一個差分值。該差分器的公式為：

yi(n)=xi(n)-xi(n-1)

(2)

而此時xi(n)為單個節(jié)點傳感器某時刻所采集的數(shù)據(jù)xi={xi1,xi2,xi3,,,xin},并通過單個節(jié)點現(xiàn)在采集的數(shù)據(jù)與前一時刻xi(n-1)的數(shù)據(jù)進行差分，并獲得yi(n)={yi1,yi2,yi3,,,yin},yi(n)為單個節(jié)點所有傳感器采集的數(shù)據(jù)差分后保存的數(shù)據(jù)；為了保證數(shù)據(jù)的有效性，同一簇內(nèi)將對不同的節(jié)點進行比較分析，同時消除數(shù)據(jù)的冗余；這時再將所獲得的數(shù)據(jù)yn進行編碼，同時根據(jù)yn所產(chǎn)生的數(shù)據(jù)進行Huffman編碼，并確定該值以確定編碼長度。

圖3 差分器數(shù)據(jù)模型

此時為單個節(jié)點的數(shù)據(jù)差分，由于多個節(jié)點具有多個傳感器可以采集多個數(shù)據(jù)，此文將根據(jù)LEACH分層協(xié)議[15]，普通的節(jié)點將數(shù)據(jù)傳輸給簇頭，簇頭將數(shù)據(jù)收集后傳送給網(wǎng)關(guān)，最后在傳給服務(wù)器。節(jié)點將采集的數(shù)據(jù)轉(zhuǎn)換在矩陣中進行存儲，初始數(shù)據(jù)都為H0(為了方便處理數(shù)據(jù)已經(jīng)在服務(wù)器接收到數(shù)據(jù)應(yīng)為同等大小矩陣，簇內(nèi)低于規(guī)定的矩陣的列數(shù)采用零補充，大于列數(shù)的簇將舍棄簇內(nèi)數(shù)據(jù)差異性很大的節(jié)點)。當(dāng)所有節(jié)點部署完畢后并正常工作，第i個節(jié)點初次開始采集的數(shù)據(jù)xi={xi1,xi2,xi3,,,xin}并存儲在內(nèi)部的存儲器中并傳遞給簇頭，同時將一個簇內(nèi)所有節(jié)點采集的數(shù)據(jù)直接傳遞給簇頭，并在簇頭中以矩陣H1方式存儲，并進行編碼傳遞給網(wǎng)關(guān)；此時，每個節(jié)點都有了初始的采集數(shù)據(jù)，而后每一次采集的數(shù)據(jù)通過與前一時刻采集的數(shù)據(jù)進行差分(式2)，單個節(jié)點差分后的數(shù)據(jù)為yi(n)，同時簇內(nèi)有多個節(jié)點，并將保存數(shù)據(jù)存儲為Hn。為了保證數(shù)據(jù)有準(zhǔn)確性和數(shù)據(jù)壓縮效率高，并在此設(shè)定一個標(biāo)準(zhǔn)的高斯分布(α=0.05)作為數(shù)據(jù)置信區(qū)間的閾值矩陣為HT(圖4)，并以此判斷差分后的數(shù)據(jù)是否在閾值范圍內(nèi)；當(dāng)yi(n)的差值大于閾值，則此時刻節(jié)點判斷差值大于閾值，節(jié)點將重新裝載數(shù)據(jù)xi，同時節(jié)點將數(shù)據(jù)傳遞給簇頭，并重新載入新的節(jié)點數(shù)據(jù)給H1。

圖4 數(shù)據(jù)的存儲

而此時的Hn是在某個時刻在一個簇內(nèi)不同的節(jié)點產(chǎn)生的數(shù)據(jù)并具有一定的空間性，通過于上一時刻的數(shù)據(jù)差分后，簇頭存儲的數(shù)據(jù)可以根據(jù)空間性，將矩陣中的數(shù)據(jù)大部分轉(zhuǎn)換成0，但并不是所有的差分后數(shù)據(jù)都是0，再次之后對簇頭的數(shù)據(jù)進行數(shù)據(jù)壓縮，這樣將大量減少了簇頭的數(shù)據(jù)量，所以將采用時間和空間相結(jié)合對數(shù)據(jù)進行處理。

2 差分后的Huffman數(shù)據(jù)壓縮

2.1 動態(tài)Huffman編碼

如果基于靜態(tài)Huffman編碼則需要對字符需要兩次掃描，而動態(tài)Huffman編碼是不需要事先構(gòu)造哈夫曼樹和輸入掃描符號流；而是一邊進行編碼，同時開始構(gòu)造哈夫曼樹；這樣可以減少處理器消耗的能量和時間。

當(dāng)初始化編碼數(shù)時，由于只能對數(shù)據(jù)流進行一次掃描，所以不能預(yù)先知道每一個符號的出現(xiàn)次數(shù)和頻率。為了對所有符號一致對待，編碼樹的初始狀態(tài)只包含一個葉節(jié)點，包含符號 NYT(Not Yet Transmitted，尚未傳送)，權(quán)重值為 0。NYT 是一個逸出碼(escape code)，不同于任何一個將要傳送的符號。當(dāng)有一個尚未包含在編碼樹中的符號需要被編碼時，系統(tǒng)就輸出 NYT 編碼，然后跟著符號的原始表達并重新給予新的編碼樹。

當(dāng)輸入一個字符時，將會構(gòu)造一個空的新子樹，子樹包含NYT符號和新符號的兩個節(jié)點，并用新的節(jié)點取代舊的NYT節(jié)點在子樹的位置(最初的NYT權(quán)重為0)，將舊的NYT取代后，新符號節(jié)點的葉節(jié)點的權(quán)重為1，同時將試圖對該父結(jié)點執(zhí)行權(quán)重加一的操作。同時，每讀取一個字符，首先檢查字符是否已經(jīng)在編碼樹中；如果不在，則先對空葉結(jié)點進行編碼，再生成一顆子樹，其右分支結(jié)點為剛的讀入的字符，其左分支結(jié)點為新的空葉結(jié)點，并用這個子樹代替原來的空葉結(jié)點；如果在已經(jīng)編碼的樹中，則以靜態(tài)哈夫曼編碼的方式進行編碼，如圖5所示。

圖5 動態(tài)Huffman編碼過程

2.2 時空差分閾值Huffman編碼

當(dāng)節(jié)點采集好的數(shù)據(jù)在自身的內(nèi)存中具有一定的時效性，通過該內(nèi)存存儲初始的數(shù)據(jù)作為一個基準(zhǔn)，初始時刻的數(shù)據(jù)直接基于動態(tài)Huffman編碼進行傳輸，此后的數(shù)據(jù)基于前一時刻的數(shù)據(jù)先進行差分，并存儲在矩陣中Hn。對差分后的數(shù)據(jù)設(shè)定一個閾值HT，當(dāng)進行差分后的數(shù)據(jù)小于閾值，則節(jié)點直接將差分器差分的差值進行編碼，如果節(jié)點的某一個傳感器差分的值大于閾值，則節(jié)點將此時的數(shù)據(jù)直接編碼進行傳輸，并以此數(shù)據(jù)為基準(zhǔn)進行差分，如圖6所示。

圖6 數(shù)據(jù)處理過程

為了保證數(shù)據(jù)傳輸?shù)臎]有太多的冗余的數(shù)據(jù)，每一次數(shù)據(jù)都要進行差分閾值的比較，而此時采用的閾值使用高斯分布置信區(qū)間驗證是否能正常通過Hn進行動態(tài)Huffman編碼。對該差分后的數(shù)據(jù)進行高斯分布X～N(0，1)的檢驗思想方式，假設(shè)差分后的Hn能通過置信區(qū)間，則將數(shù)據(jù)傳輸給編碼器進行動態(tài)Huffman編碼；反之，差分后Hn通過不了置信區(qū)間，此時，節(jié)點將采集到的原始數(shù)據(jù)進行動態(tài)Huffman編碼，并將此時刻采集到的源數(shù)據(jù)壓縮后發(fā)送給簇頭，同時簇頭收到數(shù)據(jù)后，也將采用動態(tài)Huffman編碼進行傳輸。然而置信區(qū)間往往可以由某參數(shù)的顯著性水平為α(α=0.05)的檢驗，得到該參數(shù)的置信度為1-α的置信區(qū)間[-2,2]，當(dāng)在置信區(qū)間內(nèi)是，反之。顯著性水平α的均值μ的雙側(cè)檢驗出現(xiàn)問題，則高斯分布標(biāo)準(zhǔn)化公式：

(3)

對數(shù)據(jù)進行差分后減少了大量的數(shù)據(jù)，在同一區(qū)域內(nèi)分析數(shù)據(jù)的可靠性之后，并通過動態(tài)的Huffman編碼對矩陣Hn進行數(shù)據(jù)壓縮，由于每一次的數(shù)據(jù)都是未知的，通過Huffman編碼的動態(tài)原則，先編碼在調(diào)整編碼數(shù)進行壓縮。動態(tài)的Huffman編碼以默認(rèn)的概率進行編碼，并不斷更新元素的概率，從而可以達到高概率出現(xiàn)的分配給小規(guī)模的數(shù)據(jù)流位。

動態(tài)Huffman編碼是基于動態(tài)變化的哈夫曼樹,也就是說,對第t+1個字符編碼是根據(jù)原始數(shù)據(jù)中前t個字符得到的哈夫曼樹來進行的。壓縮和解壓子程序具有相同的初始化樹,每處理完一個字符,壓縮和解壓方使用相同的算法修改哈夫曼樹,因而該方法不需要為解壓而保存樹的有關(guān)信息。壓縮和解壓一個字符所需的時間與該字符的編碼長度成正比,因而該過程可以實時進行。

3 實驗仿真

通過Matlab對數(shù)據(jù)壓縮進行處理，為了讓實驗效果更明顯，將采用LEACH協(xié)議對節(jié)點采集的數(shù)據(jù)進行壓縮，同時引入SINK中繼站盡量節(jié)省節(jié)點的能量。與原有不采用壓縮對比，能量消耗相對減少、數(shù)據(jù)傳輸效率和網(wǎng)絡(luò)壽命都相對提高，同時也保證了數(shù)據(jù)的準(zhǔn)確性；并主要分析了WSNs網(wǎng)絡(luò)的數(shù)據(jù)傳輸量，對比網(wǎng)絡(luò)生命周期等數(shù)據(jù)；將300個節(jié)點隨機部署在400 m*400 m的正方形內(nèi)，BS的坐標(biāo)為(0,0)。在仿真中，本節(jié)通過大量的實驗比較同一領(lǐng)域的壓縮算法；主要分析WSNs網(wǎng)絡(luò)壽命和數(shù)據(jù)傳輸。WSNs主要參數(shù)如表1所示。

通過實驗對比分析，當(dāng)節(jié)點采集數(shù)據(jù)后進行Huffman、動態(tài)Huffman、差分動態(tài)Huffman三種壓縮算法，三種無損壓縮算法都對節(jié)點的數(shù)據(jù)進行了壓縮，然而前兩種算法的壓縮效果并未達到理想效果，通過圖7可以看出，差分動態(tài)Huffman算法在壓縮前對數(shù)據(jù)進行了相對應(yīng)的融合，在減少了數(shù)據(jù)的傳輸同時反而增大了數(shù)據(jù)量傳輸，明顯可以看出Huffman編碼的壓縮效果低于差分動態(tài)Huffman無損壓縮。

圖7 三種算法的數(shù)據(jù)傳輸

圖8呈現(xiàn)了三種算法的能量的消耗，當(dāng)節(jié)點與簇頭之間的距離較遠時，節(jié)點在數(shù)據(jù)采集后進行數(shù)據(jù)壓縮消耗的能量低于數(shù)據(jù)傳輸?shù)哪芰?，?dāng)節(jié)點采集數(shù)據(jù)開始時，節(jié)點第一次的數(shù)據(jù)將直接進行動態(tài)Huffman編碼傳輸，此后節(jié)點通過前一次時刻的數(shù)據(jù)與現(xiàn)采集的數(shù)據(jù)進行差分，并將大量的冗余數(shù)據(jù)抵消，只用將差值后的數(shù)據(jù)進行動態(tài)Huffman編碼，再將編碼后的數(shù)據(jù)進行傳輸。數(shù)據(jù)傳輸?shù)臄?shù)據(jù)量越少，則網(wǎng)絡(luò)消耗的能量就越少。此時整個系統(tǒng)中的能量消耗減少，則總體的剩余能量將相應(yīng)的減少，圖9表示為三種壓縮算法的剩余能量對比。圖10顯示，當(dāng)采用差分Huffman算法時可以大大減少節(jié)點的死亡率并保證了節(jié)點的相對穩(wěn)定性，同時也提高了數(shù)據(jù)的壓縮率，這樣將會讓整個網(wǎng)絡(luò)更好地監(jiān)控該區(qū)域的環(huán)境。

圖8 三種算法的網(wǎng)絡(luò)能量消耗對比

圖9 三種算法的網(wǎng)絡(luò)的剩余能量

圖10 三種算法節(jié)點的存活數(shù)

在仿真中，為了保證該方案可行性，采用了節(jié)點數(shù)為100/200/300/400/500個節(jié)點部署進行了數(shù)據(jù)壓縮比的分析。通過壓縮算法的訓(xùn)練，當(dāng)節(jié)點數(shù)越多時，三種算法的壓縮率都會提高，而差分Huffman算法的壓縮也隨之提高。壓縮率公式為：

(4)

表2 三種算法的壓縮率對比 %

通過表2的數(shù)據(jù)壓縮比率統(tǒng)計當(dāng)節(jié)點數(shù)增多時，差分動態(tài)Huffman算法的壓縮比率是不斷增大，傳輸?shù)臄?shù)據(jù)量相對是不斷減小。當(dāng)直接采用Huffman編碼時當(dāng)節(jié)點數(shù)增加到某一個值時節(jié)點的壓縮率將會保持并不在減小，而差分動態(tài)Huffman算法確保了節(jié)點的數(shù)據(jù)壓縮率、數(shù)據(jù)的無損性、數(shù)據(jù)的準(zhǔn)確性、節(jié)點的節(jié)能性，同時保證了網(wǎng)絡(luò)系統(tǒng)的穩(wěn)定性。

4 總結(jié)

本文主要針對無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮算法進行研究，采用差分器再對數(shù)據(jù)進行動態(tài)Huffman編碼。當(dāng)數(shù)據(jù)進行減法時將大量的相同數(shù)據(jù)抵消，只用將差值編碼進行傳輸，極大的節(jié)省了數(shù)據(jù)傳輸?shù)哪芰?，并將?shù)據(jù)傳輸?shù)臏?zhǔn)確性也得到了提高，也減少了簇內(nèi)成員的通信開銷，提升了網(wǎng)絡(luò)的生命周期。然而本文的不足在于沒考慮到SINK的運行速度和路徑規(guī)劃。后期將會結(jié)合SINK與數(shù)據(jù)壓縮，并提高網(wǎng)絡(luò)生命周期。