無線傳感器網絡數據壓縮機制探究

陳廣勇，張潔昕

（公安部第三研究所，上海 200031）

0 引言

隨著無線和嵌入式技術的日益成熟和廣泛應用，低成本、低功耗、體積小、可短距離無線通信的傳感器節點構成的無線傳感器網絡（Wireless Sensor Networks，簡稱WSN）正得到越來越多的研究人員關注。無線傳感器網絡由部署在監測區域內的大量傳感器節點組成，可以在各種環境進行監測任務，傳統無線傳感網絡應用有軍事、檢測、應急、環境等領域，新興應用將涉及家用、企業管理、保健、交通等領域[1][2]，并且將會對人類未來的生活方式產生巨大影響。然而目前的WSN的技術還不夠成熟，在WSN技術應用到實際中之前還需要進一步的發展和研究。

無線傳感器網絡由大量節點隨機分布組成，由于每個傳感器節點通常都是由干電池供電，并且在大多數環境下不能較頻繁的更換電池，因此節點能耗就成為了當前制約無線傳感器網絡發展的重要瓶頸之一。文獻[3]指出由于相鄰節點處在相同的環境中，鄰居節點所采集的數據表現出很大程度上的時間與空間冗余。文獻[4]的研究證明：在無線網絡中的100米距離間傳送1比特信息所消耗的能量相當于執行3000個指令所消耗的能量。采用動態路由機制或網內數據聚合方式在一定程度上可以延長網絡的生存期，但是數據聚合只適用于僅對檢測目標的統計結果感興趣，而不關心中間數據記錄的應用。對需要同時保留中間觀測數據的應用，數據聚合方法就不能使用。所以在無線傳感器網絡中數據傳輸是必不可少的，因此若在傳輸數據前對其進行壓縮，則能減少數據間的冗余，進而可以有效降低節點的能耗，從而延長整個網絡的生存周期。

本文將首先對無線傳感器網絡中能量消耗進行分析，然后重點針對當前幾種用于無線傳感器網絡中的數據壓縮算法進行詳細描述，并分析數據壓縮在無線傳感器網絡中應用的優勢，最后給出結論。

1 傳感器網絡能量消耗分析

無限傳感器網絡中節點能耗的分配可以大致分成三個部分：數據采集、數據處理、數據傳輸。根據研究文獻[5]表明，在這三個部分中數據傳輸消耗了節點能耗的80%左右，因此如果能夠通過數據壓縮減少數據大小，則將會降低數據傳輸的能耗。在文獻[6]中作者針對數據通信與數據處理上的能耗進行了比較實驗，實驗結果表明：節點在進行一個簡單32位加法計算所消耗的能量是0.86nj，傳送一位數據所消耗的能量是0.4uj，則通過廣播媒介傳送一位數據所消耗的能量是進行一個加法計算消耗能量近480多倍，如果在源數據字節串中執行壓縮操作，壓縮一位數據大小則相當于節省了480多條加法計算的能耗，這將大大減少節點總體能耗。

2 數據壓縮技術

當前的流行的數據壓縮算法有Huffman壓縮算法、LZW（LZ77、LZ78）算法、算術編碼、預測編碼、變化編碼等。但是這些算法不能應用在無線傳感器網絡節點上，其原因主要有兩點：1)傳感器節點硬件限制，上述壓縮算法均需要強大的計算能力，一般的傳感器節點不能滿足其硬件要求。2)上述算法規模太大，算法寫入傳感器節點后，自身剩余內存容量不多，不能完成其在監測過程中對于數據的存儲任務。但是當今硬件技術突飛猛進，設計出一個有效的、針對性強的數據壓縮算法對于無線傳感器網絡地發展有著重大意義。在這部分將詳細介紹幾種適用于無線傳感器網絡中的數據壓縮機制。

2.1 基于數據順序的壓縮方式

圖1 數據傳輸路徑

在該算法中若采集很多唯一片段的數據，并且數據的發送順序對于應用不重要時，則可以利用那些數據片段的排列順序來表達其它冗余數據信息，并將其發送給接受者。例如：圖1中四個節點（N1、N2、N3、N4）發送數據給聚合節點Na時，假設每個節點采集數據值是0～5，由于N1、N2、N3三個節點的排列順序有3!=6種可能，恰好能夠表達N4節點所采集的數據值，則聚合節點Na可以利用N1、N2、N3三個節點的排列順序表達N4節點所采集的數據值并將其發送給上層節點，此時形成三個節點與數值間的一種映射關系如表1所示。

排列順序 數值N1，N2，N3 0 N1，N3，N2 1 N2，N1，N3 2 N2，N3，N1 3 N3，N1，N2 4 N3，N2，N1 5

對于通常情況下，假設N個節點發送數據給匯聚節點，K為節點采集數據值的范圍（例：若每個節點產生4位值，則K=24），D為整個網絡中節點的個數，每個節點均有一個唯一ID 號，L為節點在匯聚節點處丟棄的數據包個數。則要用（N-L）個數據包來表示所有N個數據包，可以表達[(N-L)!]個數據值。在N個節點中，可丟棄的節點ID個數為，每個節點可以表示KL個數據值，因此所丟棄的數據值必須包含在[(N-L)!]中，則下列不等式必須成立：

理論上來說當D=27，K=24，N≤100時，仿真圖如圖2所示：

圖2 壓縮率仿真圖

若取N=100，壓縮率可以保證在44%，理論上的壓縮上限為53%，此壓縮方法具有高壓縮率和算法簡潔的特點，適合應用于無線傳感器網絡中。但是這種方式的缺點是數據值不能有效的與排列映射，并且算法所要求映射表會隨著傳感器匯聚節點數目的增加成指數級增長，從另一個方面給傳感器節點帶來了很大的負擔。

2.2 基于管道的壓縮方式

基于管道的壓縮方式PINCO（PipelinedIn-Network Compression Scheme）在文獻[8]中詳細進行了介紹分析。核心思想是：在聚合節點收到不同節點發送來的數據后，把各個節點的數據包整合成一個單一的數據包，在整合過程中刪除包頭等冗余數據。例如：數據包的格式為＜測量數據、節點ID、時間戳＞，那么整合后的數據包格式可以為＜共享前綴、后綴列表、節點ID列表、時間戳列表＞。圖3為基于管道壓縮算法的例子，在這個例子中數據總比特由33壓縮到27。

圖3 管道壓縮算法

在存儲每個數據包之前，數據會被轉化成為一個數據組GD（Groupof Data），在每個GD的生存周期里，若兩個GD要相互融合壓縮的話，它們必須擁有相同的共享前綴。至此會不斷有新的GD與已有GD進行融合壓縮，進而達到數據壓縮的目的。給GD數據組提供大的緩沖可以提高壓縮率，但是這樣做將會增加網絡延遲，若此網絡應用于在線檢測，將會造成巨大的影響。

共享前綴是非常關鍵的數據位，在將不同的數據包壓縮成一個數據包時，其長度(spl)是一個系統級參數用以指定在傳感器采集的數據中有多少相似度。如果得到的共享前綴與測量數據中有較長的相似性，壓縮率會增加。相反，若傳感器測量的數據值沒有相似性的話，即使我們取較長的共享前綴，這個算法的有效性也會下降，并且其算法有效性主要依靠共享前綴的長度。假設傳感器讀取數據服從參數為(μ,σ2)高斯分布，若要得到高壓縮率應該選擇適中的spl值。既不能太大，因為太大會造成緩存中的數據組減少，也不能太小，因為太小會造成很大的后綴值，依據分析壓縮率(CR)應滿足以下公式：

其中x為任意傳感器，n為其讀取數據值，E[SP]是共享前綴的期待值，假設最優的sql就可以被找到。

(4)西研究區見25條礦(化)體，各礦體呈脈狀斷續分布，與含礦地質體的產狀相一致，在本次工作中大多數礦體僅為地表單工程控制，多數礦體缺乏深部的了解。借鑒CuⅫ礦體經鉆探施工發現：CuⅫ礦體不僅地表相連，而且沿斜深方向也比較穩定。照此辦法，今后應用硐探和鉆探手段對其它礦(化)體進行中深部的探索，以便擴大礦體規模增加資源量。

此算法是用高數據傳輸延遲來換取傳輸數據的低能耗。收集到的傳感器數據被存儲在一個匯聚節點的緩沖區內用以延長時間。在這段時間內數據包融合成為一個包，在一個數據包中的冗余數據將以最小化的數據傳輸方式轉移。其優點是共享前綴系統可以選擇為節點號或是時間戳等。

2.3 自適應矢量量化壓縮方式

在文獻[9]中作者提出了一種新的算法ALVQ(Adoptive Learning VectorQuantization)用于壓縮歷史數據信息。其核心思想是：ALVQ算法創建一個碼本(CodeBook)，這個碼本用于收集數據明顯的特征。依據這些特征其他數據可以應用分段編碼方式（Piece-wise Encode）進行數據壓縮。此外在此基礎上應用2層分段線性回歸方式（2-Level Piece-wise LinearRegression）進行碼本的更新，從而節省數據傳輸過程中的帶寬以及提高數據壓縮精度。在此算法中網絡拓撲結構應用典型的LEACH模型，如圖4所示在同一個簇中的節點共用簇頭節點的通信帶寬，也就是說當節點與簇頭結點傳輸數據時，它們擁有相同的數據傳輸帶寬。

圖4 LEACH模型拓撲圖

ALVQ算法設定n為節點最新得到的數據值；TotalBand為帶寬上限；MCode是碼本的最大值以及Cbase是當前碼本的大小，因此 |Cbase|＜MCode。

原始碼本由采集到的數據集構成，而數據集由采集的數據x按照如下操作得來：首先將采集的數據x簡單分割成為大小為W(W=)的數據段DPs（Data Piece），由于傳感器節點和基站的緩存限制，碼本大小限制為MCode。可以對第一個DPs(MCode/W)應用分段回歸方法來估計其它的DPs，這樣就形成了一個初始的字典。之后在數據X中的每個DPs，可以在碼本中找到一個最優的CDP（Code DataPiece）與其映射，定義這個X中的DP在碼本中的值為CDPi，其更新的CDPi應滿足：

當初始碼本建立完成后，傳感器節點不斷的將從外界中采集的數據存入緩存區中，當緩存區存滿數據，則將其將其分割成大小為W(W=)的數據間隔，對每個數據間隔做分段回歸變換使之與碼本中的CDP相對應，直到最優的CDP出現，之后將估計參數作為壓縮標識發送給基站。

ALVQ應用LFU（Least Frequently Use）算法對其中過時的碼本數據段進行更新并壓縮新的碼本數據段，將其與壓縮標識一起發送給基站。運用2層分段線性回歸法，可以有效的提高壓縮精度并且可以有效的節省帶寬。在傳輸數據階段ALVQ提出了一種稱為動態帶寬分配的策略，如圖5所示，簇頭節點根據每個傳感器節點的壓縮效率分配不同的傳輸帶寬，使低效率的壓縮節點可以得到更多的帶寬，而高效率的壓縮節點得到較少的帶寬，從而平衡了整個網絡的帶寬分配，減少了網絡能耗，延長網絡生存周期。

圖5 動態分配帶寬圖

2.4 分布式信源編碼壓縮方式

基本思想是對相關的信源進行分布式獨立編碼，而在解碼端進行聯合解碼。分布式信源編碼由于其固有的編碼簡單、不需節點間通信等特點，非常適合于無線傳感器網絡中數據壓縮的應用，由于其充分利用了傳感器數據間的相關性，所以壓縮性能非常高。文獻[10]介紹了分布式信源編碼方式的核心思想，如圖6所示，在編碼時圖中傳感器節點A不進行數據壓縮，直接發送數據Y，傳感器節點B用信道碼對數據X進行編碼產生校驗信息P，B節點只發送校驗信息P；在解碼時把節點A的數據Y看作為節點B數據X經過一個有噪信道后的誤碼數據，那么就可以用節點B傳過來的校驗信息P對Y進行信道解碼，從而得到重建的節點B數據X。因為校驗信息P一般都遠小于原始信息X，所以節點B就實現了數據壓縮的目的。

圖6 分布式信源編碼理論壓縮方案

在文獻[11]中考慮了如圖7中的對兩個相關信源進行無損編碼的情況。文章給出了兩個相關信源編碼問題的碼率可達域，如圖8所示。在A點對X1編碼的碼率為RX1=H(X1)，而對X2進行壓縮時所需要的碼率僅為RX2=H(X2 | X1)。同樣在B點對X2編碼的碼率為RX2=H(X2)，而對X1進行壓縮時所需要的碼率僅為RX1=H(X1 | X2)。這就是在解碼端具有邊信息的無損信源編碼問題的理論極限。

圖7 多信源編碼系統

圖8 確定信息可達域

用一個簡單的例子來說明分布式數據壓縮，設定有兩個3位的數據序列（X和Y），并且X與Y之間的海明距離不會超過1個數據位，如果解碼器知道的信息Y以及X與Y之間的海明距離只有1位，則X=111與X=000就不能有效的分辨，同理X=001和110，X=010和101以及X=01和110這三組也不用區分，所以X的序列可以組合成4種集合：

Set1=（000，111）：00

Set2=（001，110）：01

Set3=（010，101）：10

Set4=（011，100）：11

若X=010，Y=110，則解碼器根據圖7所示將Y作為邊信息（SideInformation），X的序列集（set）為10作為部分信息（Partial Information），根據X的序列集10以及與Y之間的海明距離2則可以挑選出X=010。所以無論X是否知道Y的序列值，X都可以將3位數據壓縮到2位數據。分布式壓縮算法思想可以應用于離散數據也可應用于連續數據中，并且也可以應用于無數據丟失和有數據丟失的壓縮方法中，因此此方法具有較好的適用性。

3 結論

無線傳感器網絡的飛速發展在帶來新便捷的同時也提出了眾多亟待解決的問題，如何節省能耗從而達到整體網絡生存期的延長成為當今制約無線傳感器網絡發展的重大瓶頸之一。本文通過介紹幾種當今比較重要的數據壓縮機制來解釋如何通過數據壓縮降低節點能耗，從而達到無線傳感器網絡生存期的延長。在本篇論文中，重點介紹了四種不同的數據壓縮方式：基于管道的壓縮方式、基于管道的壓縮方式、自適應適量量化壓縮方式以及分布式信源編碼壓縮方式，盡管這些方法一直在優化發展，但是實驗結果表明其壓縮率和能耗降低還是顯有成效的，他們之中很有可能會解決無線傳感器網絡能耗限制的途徑之一。

[1]EstrinD,Govindan R,Heidemann J,et al.Scalable coordination in sensor network[J].IEEEComputer Society,1999 :263-270.

[2]L.Akyildiz,W.Su,Y.Sankarasubramaniam,andE.Cayirci,A Survey on Sensor Networks.IEEECommunications Magazine,Vol.40,No.8,2002.102-114.

[3]Compression and Storage Schemes in a SensorNetwork with Spatial and Temporal CodingTechniques.

[4]J.Pottie and W.J.Kaiser.Wireless Integratednetwork sensors[J].Communications of the ACM,vol.43,May 2000:51-58.

[5]Kimura,N.Latifi,S.A survey on data compressionin wireless sensor networks information technologyCoding and Computing[J].ITCC 2005.InternationalConference,on 4-6 April 2005:8-13.

[6]Kenneth Barr，KrsteAsanovic.Energy AwareLossless Data Compression.In First InternationalConference on Mobile Systems，Applications，andServices，May 2003.

[7]D.Petrovic，R.C.Shah，K.Ramchandran，J.Rabaey.Data Funneling: Routing withAggregation and Compression for Wireless SensorNetworks.In Proceedings of First IEEE InternationalWorkshop on Sensor Network Protocols andApplications，May 2003.

[8]T.Arici，B.Gedik，Y.Altunbasak，and L.Liu.PINCO: a Pipelined In-Network Compression Schemefor Data Collection in Wireless Sensor Networks.InProceedings of 12th International Conference onComputer Communications and Networks,October2003.

[9]Online Information Compression in SensorNetworks.

[10]S.Pradhan and K.Ramchandran.Distributedsource coding: Symmetric rates and applications tosensor networks.In Proc.DCC’00,Snowbird,UT,2000:363-372.

[11]D.Slepian and J.K.Wolf.Noiseless Coding ofCorrelated Information Sources.IEEE Transactionson Information Theory,19(4),1973:471-480.