無線傳感器網絡數據壓縮算法研究

劉河　陳宇

摘要：傳感器網絡中由于節點部署密度大，傳感器節點的覆蓋區域是相互重疊，因此，容易產生較多的冗余數據。而通過數據壓縮能夠有效減少冗余數據、最小化傳輸量、節省節點能量。對無線傳感器網絡中的數據冗余從時間、空間等角度進行了分析，對應用于傳感器網絡中的幾種典型數據壓縮算法進行了分類和比較。

關鍵詞：無線傳感器網絡； 數據冗余； 數據壓縮算法

中圖分類號：TP393 文獻標識碼：A[HT5”H]文章編號：2095-2163（2013）05-0028-03

0引言

傳感器節點是一個配備了無線電收發器、微控制器、能量源的信息接收處理單元。因為體積小，同時考慮到成本問題，傳感器節點受到有限的帶寬、電量和計算能力的限制。對于大規模部署無線傳感器節點的網絡來說，如何提高節點的能量效率，延長整個WSN壽命是需要解決的首要問題[1]。

對于監測區域內的傳感器節點來說，其數據采集行為往往具有：同一個信號可能被不同傳感器捕獲；對于多維度信息采集，多個傳感器的并行采集數據能夠形成互補等特點，這些都容易產生冗余數據[2]。

1數據冗余

1.1時間冗余

時間冗余來自于提高精度傳感器節點的讀數和在傳感和通信時承受瞬時故障。時間冗余的應用較為復雜，主要用于無線傳感器網絡的環境參數頻繁變動的場景，傳感器節點通過發送連續多個采集報告以提高數據置信水平，這種類型的冗余通常是在視頻監視和多代支持基于特定的數據壓縮技術的編解碼器等應用中采用。時間冗余可以分為：時間感知冗余、時間通信冗余。

1.2空間冗余

空間冗余來自于傳感器網絡中某個特定地理區域內，多個傳感器節點采集的信息出現重疊現象。這種空間冗余產生的目的，主要是為了提供容錯或提高測量數據的可靠性以達到一定的安全水平。

空間冗余幾乎在任何一個傳感器網絡部署時都會發生，因為在無線傳感器網絡的應用中通常需要密集部署節點以保證網絡的連通性。從覆蓋問題的角度來說，空間冗余可以劃分為物理冗余和分析冗余，具體分析如下。

物理冗余是一種非常普遍的技術，通過節點在某一區域的高密度部署用于保證系統的可靠性，尤其是考慮到網絡受到安全威脅時，這種冗余非常有必要。當然，由于節點之間距離過近，易造成節點采集的數據具有一定的相似性，而這些數據的產生在無線信道傳輸過程中無疑會消耗大量的節點能量，因此，需要通過一定的數據融合方法來降低數據冗余度，以節約資源。

分析冗余則是指通過一定的數學模型根據歷史監測數據推導出的預估測量值，用于與節點發送過來的實際測量值進行比較，目的是獲取出現故障或惡意攻擊的節點。通常，當節點數量過多或者數據模型過于復雜時，分析冗余的計算代價太大，[JP2]另外，分析冗余產生的冗余數據與真實的數據本身不一定能完全契合，因此，這種冗余只出現在較少的應用中。

1.3信息冗余

信息冗余則主要是用于信息表示方法上對冗余數據的描述，常常定義為使用冗余數據（例如，特殊bit）來重新構造丟失的信息。因此，信息冗余意味著額外的信息是用來檢測和從故障中恢復。奇偶校驗位附加到數據塊，使誤差檢測即可以視為一個實例信息冗余。另一個例子是信息冗余擦除碼，都是通過使用的信息冗余，無需重傳機制即可構造出原始消息。

2數據壓縮算法

大量原始數據轉發到基站的路途中將很快耗盡所經過節點的能量，導致傳感器網絡死亡，為了減少數據傳輸過程的數據量，從而節省網絡能量，延長網絡生命周期，很多專家學者提出，通過節點間的協作對傳感器網絡采集到的數據進行網內處理，也就是適當地采用數據壓縮方法，使得數據量減少[3]。

2.1數據壓縮方法分類

對觀測數據的壓縮處理，可在傳感器節點和基站兩端分別采用壓縮和解壓縮技術。在數據發送前提高編碼效率，或者是根據不同應用需求（例如圖像特征的信息，直接處理非常復雜）對信息進行數據變換，實現發送數據前的壓縮操作?；臼盏綌祿笤龠M行解壓縮，降低傳輸過程中大量冗余數據造成的能量損耗。

常見的數據壓縮方法有：

（1） 壓縮編碼。按照特定的編碼機制利用較少的數據位元（或者其他信息相關的單位）表示信息，從壓縮結果來看可以分為有損壓縮和無損壓縮，由于傳感器采集的多數為模擬信息，所以主要采用有損壓縮算法。而針對不同的傳感器數據特征又可以采用標量數據壓縮算法或者矢量數據壓縮算法，并根據不同的數據類別選擇對應的數據壓縮算法。

（2） 匯聚節點處融合。對于覆蓋范圍較大的傳感器網絡，源節點到基站之間的數據轉發采用多跳方式比點對點直接通信更能節省能耗。轉發路徑上的節點作為匯聚節點，可以在不丟失信息的前提下通過排序編碼丟棄部分于匯聚節點匯合的數據，實現數據壓縮。

（3） 依據數據空間相關性。地理位置相鄰的傳感器節點收集到的數據存在相關性，在多個節點中選取一個有代表性的節點數據，將其完整地發送至基站，而其他節點的數據提取出偏差部分并壓縮后發送，基站最后通過壓縮數據和未壓縮數據之間的相關性進行解壓縮來重構得到原始數據。

（4） 依據數據時間相關性。單個傳感器節點收集到的數據在時間上可能是相關的，使用例如小波變換等信號處理辦法來去除其中的冗余信息，并在保持信號的統計特性的基礎上實現數據壓縮的目的。

2.2典型的數據壓縮算法

文獻[4]提出了一種能量高效的分布式線性回歸數據采集優化策略，根據同一監測區域附近的傳感器節點采集的數據測量值具有極大相關性這一特點，通過構建線性回歸模型表示傳感器的感知數據。

假設傳感器在時間t1，t2，…tm上感知的數據為y1，y2，…ym，則構建滿足逼近誤差最小δi=Y（ti）-yi的函數Y（函數用多項式表示，Y（t）=

λ1+λ2t+λ3t2+λ4t3）；構建函數模型之后，多個實際測量值僅僅需要在網內傳輸4個參數值，即λ1、λ2、λ3和λ4即可得到原始數據。為了使估計值的逼近誤差δi最小，選定使得逼近誤差向量的范數最小為優化目標，即min（‖δ‖=（∑[DD（]m[]i=1[DD）]δ2i）1/2）。另外，文中還提出了回歸模型的參數更新方法以采用增量方式更新線性回歸系統模型的矩陣和向量參數。該模型大大減少了傳感器節點間頻繁數據傳輸帶來的通信開銷，降低了節點的能量消耗，不足之處在于模型中矩陣的運算量偏大。

文獻[5]利用一維Haar小波分解算法，對數據向量通過逐級分解以得到近似分量和細節分量，針對誤差‖e‖∞形成小波系數的誤差樹，再根據小波系數的值和誤差限ε來判定哪些節點可以被零化，并通過量化系數的熵編碼提高數據的壓縮效率，從而減少傳輸的數據。此外，文中還提出了多屬性的誤差有界小波數據壓縮算法，對每個節點在某時刻采集的多種不同屬性的數據進行數據壓縮。方案中，首先對數據進行規范化，用二維Haar 小波變換進行全分解；再根據不同屬性的感知數據以及同一屬性不同時段的數據具有相關性的特點，選出基信號，回歸表示其他信號。方案的不足之處在于，基信號挑選算法將不同的屬性按相關性分到某個基代表的組中，而為了使得誤差越小，需要的基就越多，壓縮效果也將變差。另外，將基信號等分分段實現多次回歸，但當基分段太多時，卻易造成該段回歸結果可能會超過規范化誤差的結果。

考慮到網絡中部署的傳感器節點在監測數據行為上存在數據相關性，比如在某些應用中，一個特定區域可能被多個傳感器覆蓋，這些傳感器很可能監測到同一時間，產生相同的數據而造成不必要的能耗上的浪費，文獻[6]介紹了一種通過各傳感器節點遵循關聯機制，來實現網內數據壓縮以減少數據量的行為策略。主要步驟為：

（1）網絡中包含n個傳感器節點，構成集合S={s1，s2，……，sn}，時間片λ根據用戶可任意設置大小。每個傳感器均有一個大小為B的緩沖池，每經過一個時間片，各傳感器節點根據是否監測到事件發生來設置緩沖區入口。

（2）傳感器的行為數據在一定的時間間隔后發送至基站，基站通過行為數據獲知在這段時間內該節點監測到事件發生的次數。

（3）該網絡中的數據約簡是借助創建數據收集樹實現的，稱之為最小的節點的數據收集樹（minimum nodes data gathering tree， MNDGT），另外結合分布式的約減機制。MNDGT樹中只包含了參與制定傳感器關聯規則的節點以及與基站距離近的部分節點。

（4）數據收集沿著樹形結構從最低層至最高層。在MNDGT最后一級每個葉節點將參與集合發送至雙親節點。雙親節點則根據這些集合來計算所有子節點的交集，并依據一定的規則設置活動節點。

文獻[7]提出了一個分布式數據融合算法，其主要思想是在中間節點將傳入的多個數據包通過PCA（principal component Analysis）方法將其壓縮成一個數據包，再將融合結果發至父親節點。具體的數據壓縮過程是基于多跳網絡，即假設網絡中的節點需通過多跳方式將采集的數據發至基站，但是最多只能經過兩跳，路徑可以任意選擇且不一定為最短的路徑。再將路徑上的節點構造成一棵樹型結構，基站為該數據結構中的根節點。

文獻[8]首先提出了一種具有普遍性的體系結構來減少數據流造成的能量開銷和延遲方面的影響，在該體系結構中，把監測節點采集過程中數據的產生（感知流）或是當一個節點轉發數據至另一個節點（路由流）視為輸入流，當傳感器獲取過多的樣本，并且不能動態校準處理比目前更多的數據處理時，通過應用層對感知流進行數據壓縮；根據不同應用的需求，當網絡中不需要對過多的數據進行數據轉發時，則交給路由層進行數據壓縮以避免無法控制的丟包行為。應用層的數據壓縮算法主要分為隨機采樣、居中采樣、多元抽樣、概要數據等環節，壓縮后的數據流如果需要轉發給其他節點，則通過網絡層進行重新封裝后再發給sink節點。

3結束語

在傳統的數據傳輸模式下，無線傳感器網絡中的各節點如果傳輸全部的感測信息，將因為大量冗余信息的傳輸使得能量消耗過大，因此，先對數據進行融合處理再發給基站是非常必要的。本文對時間冗余、空間冗余和信息冗余等方面進行了分析，對數據壓縮算法進行了簡單的分類，并對幾種典型的數據壓縮算法進行了分析比較，[JP2]下一步的工作將在這些研究的基礎上，提出考慮數據的空間相關的數據壓縮算法。