無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮技術(shù)的研究進(jìn)展

收稿日期：2014－05－04

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61033015)。

作者簡(jiǎn)介：李國(guó)華(1984-)，男，湖南婁底人，博士研究生，主要研究方向: 無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮、擁塞控制。

摘要：隨著傳感器技術(shù)、嵌入式計(jì)算以及無(wú)線通訊技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)應(yīng)運(yùn)而生。因?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)只有有限的電池能量，而數(shù)據(jù)的無(wú)線傳輸是能量消耗的主要部分，過(guò)多的無(wú)線傳輸將會(huì)快速耗盡節(jié)點(diǎn)的電池能量，從而引起節(jié)點(diǎn)失效。因此，如何在不危及網(wǎng)絡(luò)的任務(wù)條件下盡可能地壓縮數(shù)據(jù)是一個(gè)重要的研究問(wèn)題。本文從時(shí)間相關(guān)性、空間相關(guān)性以及時(shí)空相關(guān)性三個(gè)方面綜述了近年來(lái)無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮技術(shù)的研究進(jìn)展，討論了目前存在的一些問(wèn)題以及未來(lái)的一些研究方向。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 數(shù)據(jù)壓縮； 時(shí)間序列

中圖分類號(hào)：TP3111文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2014）03-0060-05

Research on Data Compression Techniques in Wireless Sensor Networks

LI Guohua

(School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China)

Abstract：Technological advances in the development of sensing， embedded computing and low-power wireless communication technologies have enabled the development of wireless sensor networks. Because sensor nodes have limited battery lifetime， and radio transmission is the primary consumer of energy， excessive transmission quickly depletes batteries， rendering the nodes useless. Therefore， how to compress data while not compromising the mission of applications is a fundamental research problem. This paper surveys the research work on data compression， including time correlation based data compression， space correlation based data compression and time-space correlation based data compression. The existing problems in the current research and some future research directions are also discussed.

Key words：Wireless Sensor Networks; Data Compression; Time Series

0引言

近年來(lái)，隨著無(wú)線通信、微機(jī)電系統(tǒng)、超大規(guī)模集成技術(shù) (Very Large Scale Integrated circuits， VLSI )的飛速發(fā)展和日益成熟，使得現(xiàn)代傳感器具備了強(qiáng)大的感知能力和通信能力，且開啟了微型化、智能化、網(wǎng)絡(luò)化的發(fā)展進(jìn)程，其中最具典型的代表就是無(wú)線傳感器節(jié)點(diǎn)（也稱傳感器節(jié)點(diǎn)）。 這些具有一定感知、計(jì)算和通信能力的傳感器節(jié)點(diǎn)分布在一個(gè)特定的區(qū)域，通過(guò)自組織的方式實(shí)時(shí)協(xié)作地監(jiān)測(cè)、感知并處理網(wǎng)絡(luò)里的數(shù)據(jù)，再通過(guò)短距離無(wú)線通信的方式經(jīng)多跳將數(shù)據(jù)傳送到匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))，從而形成了一個(gè)集信息感知、信息處理、信息傳送于一體的整合網(wǎng)絡(luò)，并稱之為無(wú)線傳感器網(wǎng)絡(luò)［1-2］(Wireless Sensor Networks， WSNs)。

WSNs最先在美國(guó)軍隊(duì)中得到了廣泛的應(yīng)用并取得了巨大成效。美軍遠(yuǎn)程戰(zhàn)場(chǎng)感知系統(tǒng)［3］ (Remotely Monitoring Battlefield Sensor System， REMBASS) 由美國(guó)L-3通信公司設(shè)計(jì)推出，能夠全天候地對(duì)地面戰(zhàn)場(chǎng)實(shí)現(xiàn)遠(yuǎn)程監(jiān)控，其技術(shù)功能主要是實(shí)時(shí)地探測(cè)、分類、定位、報(bào)告車輛和人等活動(dòng)目標(biāo)的動(dòng)向。REMBASS最初即應(yīng)用于上世紀(jì)70年代初的越戰(zhàn)，當(dāng)時(shí)，美軍在北約部隊(duì)的重要交通運(yùn)輸線—胡志明小道上部署了大量的傳感器節(jié)點(diǎn)，獲得了準(zhǔn)確度極高的情報(bào)，取得了出眾優(yōu)異的偵查效果。 2001年， DARPA提出了靈巧傳感器網(wǎng)絡(luò) (Smart Sensor Web， SSW) 計(jì)劃［4］，于2001-2005財(cái)政期間發(fā)布實(shí)施。SSW的核心思想是在戰(zhàn)場(chǎng)上部署大量的傳感器節(jié)點(diǎn)以收集數(shù)據(jù)，并對(duì)原始數(shù)據(jù)加以過(guò)濾，而后將重要的信息傳送到各個(gè)數(shù)據(jù)融合中心，從而得到了一幅由大量信息集結(jié)而成的戰(zhàn)場(chǎng)全景圖。當(dāng)士兵需要時(shí)，即可給其發(fā)送相關(guān)信息，由此則極大地提高了士兵對(duì)戰(zhàn)場(chǎng)態(tài)勢(shì)的感知能力。

以數(shù)據(jù)為中心的WSNs的設(shè)計(jì)目的就是將數(shù)據(jù)從網(wǎng)絡(luò)中傳輸?shù)絽R聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))，再進(jìn)行其后相應(yīng)的各級(jí)處理。因此，如何高效節(jié)能地將網(wǎng)絡(luò)中的數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn)即成為WSNs研究的關(guān)鍵技術(shù)之一。但由于無(wú)線傳感器網(wǎng)絡(luò)的存儲(chǔ)、計(jì)算和通信能力都較為有限，這就給數(shù)據(jù)的傳輸帶來(lái)一定的挑戰(zhàn)。在傳統(tǒng)無(wú)線網(wǎng)絡(luò)里，數(shù)據(jù)傳輸一般都要經(jīng)過(guò)先壓縮、后傳輸?shù)倪^(guò)程。香農(nóng)(Claude Shannon)于1948年發(fā)表的論文“A Mathematical Theory of Communication”當(dāng)屬信息論的開山之作［5］，其在論文中指出任何信息都存在一定程度的冗余，并第一次給出了信息熵的計(jì)算公式。而數(shù)據(jù)壓縮的實(shí)質(zhì)就是要消除信息中的冗余部分。通常所理解的數(shù)據(jù)壓縮是指按照一定的編碼方法，利用比未經(jīng)編碼少的數(shù)據(jù)位來(lái)表示原數(shù)據(jù)的技術(shù)。數(shù)據(jù)壓縮一般包含兩個(gè)過(guò)程：壓縮和解壓縮。壓縮過(guò)程就是對(duì)原始數(shù)據(jù)采用某種算法或者編碼機(jī)制，實(shí)現(xiàn)以更少的數(shù)據(jù)位元來(lái)描述原數(shù)據(jù)的過(guò)程。而解壓縮過(guò)程則與壓縮相反，而是利用壓縮后得到的數(shù)據(jù)位元通過(guò)某種算法來(lái)進(jìn)行壓縮數(shù)據(jù)還原的過(guò)程。解壓縮后，可根據(jù)還原得到的數(shù)據(jù)是否與原數(shù)據(jù)一樣，而將數(shù)據(jù)壓縮算法分為兩類，即有損壓縮和無(wú)損壓縮［6］。有損壓縮是指通過(guò)壓縮后的數(shù)據(jù)無(wú)法還原原始數(shù)據(jù)，因其具有較高的壓縮率(衡量壓縮性能的一個(gè)重要指標(biāo))，更常見(jiàn)于多媒體壓縮，如圖像、視頻等的壓縮；無(wú)損壓縮則是指通過(guò)壓縮后的數(shù)據(jù)可以完整地還原得到原始數(shù)據(jù)，只是其壓縮率要比有損壓縮方法的壓縮率低一些，因而多是用于文本文件的壓縮，比較常用的無(wú)損壓縮算法有哈夫曼編碼、算術(shù)編碼等。經(jīng)過(guò)近幾十年的發(fā)展，已經(jīng)研發(fā)了大量的數(shù)據(jù)壓縮算法，并且廣泛應(yīng)用于各個(gè)領(lǐng)域。但是由于WSNs中節(jié)點(diǎn)計(jì)算、存儲(chǔ)和通信能力較為有限，使得大部分傳統(tǒng)數(shù)據(jù)壓縮算法很難在WSNs中獲得理想的應(yīng)用，其主要原因如下：

(1)許多傳統(tǒng)數(shù)據(jù)壓縮算法所需內(nèi)存較大，而節(jié)點(diǎn)的內(nèi)存一般非常有限，如bzip壓縮算法所需內(nèi)存為219KB，而TelosB節(jié)點(diǎn)的內(nèi)存僅有10KB［7］；

(2)許多傳統(tǒng)數(shù)據(jù)壓縮算法所需計(jì)算處理能力較高，而目前許多已開發(fā)的節(jié)點(diǎn)(Mica系列、Telos系列節(jié)點(diǎn))的CPU時(shí)鐘頻率一般卻在1~8MHz范圍內(nèi)；

(3)許多傳統(tǒng)數(shù)據(jù)壓縮算法往往最關(guān)注算法的壓縮性能，即壓縮率，而較少論及節(jié)能，而在WSNs中，能量有效性卻是算法和協(xié)議設(shè)計(jì)的重要參數(shù)之一。

基于上述原因，近年來(lái)已有大量研究人員開展了WSNs數(shù)據(jù)壓縮算法的研究工作，主要可分為三大類：

(1)基于時(shí)間相關(guān)性的數(shù)據(jù)壓縮算法研究；

(2)基于空間相關(guān)性的數(shù)據(jù)壓縮算法研究；

(3)基于時(shí)空相關(guān)性的數(shù)據(jù)壓縮算法研究。

下面將分別介紹這三個(gè)方面的研究工作。第3期李國(guó)華：無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮技術(shù)的研究進(jìn)展智能計(jì)算機(jī)與應(yīng)用第4卷

1基于時(shí)間相關(guān)性的數(shù)據(jù)壓縮算法

在許多WSNs應(yīng)用中，單個(gè)傳感器節(jié)點(diǎn)連續(xù)不斷地采集感知對(duì)象的數(shù)據(jù)(簡(jiǎn)稱感知數(shù)據(jù))，在短時(shí)間內(nèi)，感知數(shù)據(jù)的數(shù)據(jù)值變化并不大，可將這一性質(zhì)稱為WSNs數(shù)據(jù)的時(shí)間相關(guān)性；另一方面，由于WSNs中的節(jié)點(diǎn)多會(huì)部署在一個(gè)地理區(qū)域，這就使得相鄰節(jié)點(diǎn)在同一時(shí)間內(nèi)采集到的感知數(shù)據(jù)值將會(huì)較為相近，這一性質(zhì)則可稱為WSNs數(shù)據(jù)空間相關(guān)性。

早期的基于時(shí)間相關(guān)性的數(shù)據(jù)壓縮算法中，Jagadish［8］提出了一個(gè)動(dòng)態(tài)規(guī)劃算法，通過(guò)該算法使得在給定線段條數(shù)的情況下，L2誤差達(dá)到最小化來(lái)對(duì)數(shù)據(jù)進(jìn)行壓縮近似。該算法是一個(gè)最優(yōu)算法，但卻是一個(gè)離線算法，并且算法時(shí)間復(fù)雜度僅為O(n2)。文獻(xiàn)［9］則提出Top-Down算法和Bottom-Up算法。Top-Down算法是在給定精度的前提下，自頂向下地考慮時(shí)間序列的每種可能劃分，從中選取一個(gè)最優(yōu)的劃分點(diǎn)，再不斷地迭代下去，直到整個(gè)時(shí)間序列結(jié)束。Bottom-Up算法的主要思想?yún)s與Top-Down算法恰好相反，起始是將整個(gè)時(shí)間序列劃分成n/2個(gè)小段(n為時(shí)間序列的長(zhǎng)度)，而后算法不斷迭代，即合并代價(jià)最低的相鄰小段，直到滿足某個(gè)停止準(zhǔn)則才結(jié)束。文獻(xiàn)［10］又提出了Cache算法，其初始是選擇第一個(gè)數(shù)據(jù)點(diǎn)作為近似值，如果后續(xù)的數(shù)據(jù)點(diǎn)在第一個(gè)數(shù)據(jù)點(diǎn)的ε范圍內(nèi)，則將其過(guò)濾，否則即結(jié)束當(dāng)前的線段，并且選擇不能過(guò)濾掉的數(shù)據(jù)點(diǎn)以作為新的近似值，等待后續(xù)數(shù)據(jù)點(diǎn)的到來(lái)。重復(fù)前面過(guò)程，直到整個(gè)時(shí)間序列結(jié)束。文獻(xiàn)［11］還提出了Linear filter算法，算法選擇由開始的兩個(gè)數(shù)據(jù)點(diǎn)連接而成的直線作為第一部分?jǐn)?shù)據(jù)的近似，當(dāng)新的數(shù)據(jù)點(diǎn)到直線的距離小于給定閾值ε時(shí)，則等待下一個(gè)新數(shù)據(jù)點(diǎn)的到來(lái)，否則立即結(jié)束第一部分?jǐn)?shù)據(jù)的近似，而由當(dāng)前未被近似壓縮的數(shù)據(jù)點(diǎn)出發(fā)，開始第二部分的數(shù)據(jù)近似。Franky Kin-Pong Chan等人也提出了基于哈爾小波(Haar wavelets)的時(shí)間序列匹配算法［12］。首先，為了描述兩個(gè)時(shí)間序列的相似性，算法給出了一個(gè)相似性度量，即傳統(tǒng)的歐氏距離。然后，該算法對(duì)節(jié)點(diǎn)的時(shí)間序列進(jìn)行哈爾小波變換，再利用一個(gè)滑動(dòng)窗口來(lái)處理小波系數(shù)，繼而建立多維索引樹，并且還要利用相似性度量來(lái)查詢多維索引樹來(lái)確定n個(gè)最相鄰的時(shí)間序列中，序列相似度量值小于給定閾值的所有序列。對(duì)于沒(méi)有超過(guò)閾值的序列可用一個(gè)編碼表示，其余的則分別用不同編碼予以表示。需要發(fā)送的編碼后的數(shù)據(jù)多會(huì)比原數(shù)據(jù)要少，這就實(shí)現(xiàn)了在一定程度上消除序列中的冗余信息。文獻(xiàn)［13］又接著提出了一種用直線來(lái)近似時(shí)間序列的PMC-MR算法。其主要思想是，當(dāng)?shù)谝粋€(gè)數(shù)據(jù)點(diǎn)到達(dá)時(shí)，將第一個(gè)數(shù)據(jù)放到第一個(gè)桶內(nèi)(抽象的說(shuō)法)，令最大值和最小值和第一個(gè)數(shù)據(jù)點(diǎn)的值相等。當(dāng)?shù)诙€(gè)數(shù)據(jù)點(diǎn)到達(dá)時(shí)，將其與之前的最大、最小值進(jìn)行比較，并且更新最大、最小值，同時(shí)計(jì)算最大、最小值之差，Max-Min，是否在給定的閾值2ε內(nèi)。如果Max-Min小于2ε，即將第二個(gè)數(shù)據(jù)點(diǎn)放入桶內(nèi)，稍后等待第三個(gè)數(shù)據(jù)點(diǎn)的到來(lái)，否則就要用(Max+Min)/2來(lái)近似表示當(dāng)前桶內(nèi)每個(gè)數(shù)據(jù)點(diǎn)的值，再?gòu)牡谌齻€(gè)數(shù)據(jù)點(diǎn)開始啟用一個(gè)新桶來(lái)裝后續(xù)數(shù)據(jù)。上述過(guò)程一直繼續(xù)，直至整個(gè)時(shí)間序列結(jié)束。該算法能保證近似值與真實(shí)值的誤差不超過(guò)ε。進(jìn)一步地，文獻(xiàn)［14］提出了SBR算法，每個(gè)節(jié)點(diǎn)可同時(shí)監(jiān)測(cè)多個(gè)物理量，利用該算法探索各個(gè)物理量之間的相關(guān)性，通過(guò)選定一個(gè)物理量信號(hào)作為基礎(chǔ)，探索該物理量與其他物理量之間的相似性，再用此基信號(hào)加上一些參數(shù)來(lái)表示其他物理量信號(hào)。文獻(xiàn)［15］提出了BBQ算法，算法是在用戶給定的一個(gè)誤差以及置信區(qū)間條件下，利用一個(gè)統(tǒng)計(jì)模型來(lái)減少數(shù)據(jù)的感知和通信開銷。相應(yīng)地，文獻(xiàn)［16］提出了Ken算法，通過(guò)使用兩個(gè)動(dòng)態(tài)概率模型，其中一個(gè)運(yùn)行在匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))，另一個(gè)則運(yùn)行在網(wǎng)絡(luò)里的每個(gè)節(jié)點(diǎn)上，在損失微小精度的前提下可通過(guò)這兩個(gè)模型來(lái)盡量減少數(shù)據(jù)的傳輸量。其他的研究還有，文獻(xiàn)［17］提出了ALVQ算法，就是通過(guò)歷史數(shù)據(jù)來(lái)構(gòu)造一個(gè)密碼本用以探索數(shù)據(jù)的內(nèi)在特性，再利用這個(gè)密碼本對(duì)其他數(shù)據(jù)進(jìn)行分段線性壓縮，如此即減少了數(shù)據(jù)的傳輸量。另外，文獻(xiàn)［18］提出一個(gè)分段線性近似的算法，就是在給定一個(gè)誤差界限的條件下，運(yùn)用一條直線來(lái)近似當(dāng)前已出現(xiàn)但未被壓縮的數(shù)據(jù)點(diǎn)，直到新來(lái)一個(gè)數(shù)據(jù)點(diǎn)使得這個(gè)界限得以突破。其后類似地，從這個(gè)新的數(shù)據(jù)點(diǎn)開始再運(yùn)用新的直線來(lái)近似后續(xù)的到達(dá)點(diǎn)。而且，文獻(xiàn)［19］還提出了EAQ算法，首先將原始時(shí)間序列轉(zhuǎn)換成一個(gè)特殊的時(shí)間序列描述MVA(multi-version array)，利用這個(gè)MVA的前綴，就可以恢復(fù)出誤差一定的原始時(shí)間序列的近似版本，而隨著前綴的增大，誤差將逐漸減少，由此而實(shí)現(xiàn)了變誤差的時(shí)間序列近似。除上述研究外，研究人員還提出了用離散傅立葉變換［20］、離散余弦變換［21］和離散小波變換［22］來(lái)進(jìn)行數(shù)據(jù)壓縮的算法，這些算法均是基于時(shí)間序列的時(shí)間相關(guān)性算法。只是其計(jì)算復(fù)雜性較高，并不適用于WSNs。

2基于空間相關(guān)性的數(shù)據(jù)壓縮算法

由于節(jié)點(diǎn)部署多在一個(gè)地理區(qū)域，地理位置相鄰的節(jié)點(diǎn)在同一時(shí)間采集的數(shù)據(jù)將具有極大的相似性，為了充分利用節(jié)點(diǎn)的帶寬資源，減少冗余數(shù)據(jù)的傳輸，研究人員開始研究如何消除數(shù)據(jù)空間冗余。文獻(xiàn)［23］提出的算法主要研究了WSNs數(shù)據(jù)的空間相關(guān)性。該算法在開始一段時(shí)間內(nèi)由Sink節(jié)點(diǎn)收集節(jié)點(diǎn)傳來(lái)的原始數(shù)據(jù)，然后Sink節(jié)點(diǎn)挖掘節(jié)點(diǎn)間數(shù)據(jù)的相關(guān)性，通過(guò)契比雪夫不等式確定具有數(shù)據(jù)相關(guān)性的節(jié)點(diǎn)。確立了相關(guān)性后，則建立了相關(guān)性模型，此后再進(jìn)行數(shù)據(jù)傳輸時(shí)，只需要傳輸一個(gè)節(jié)點(diǎn)的原始數(shù)據(jù)，以及相關(guān)性模型的對(duì)應(yīng)參數(shù)即可。文獻(xiàn)［24］也提出了基于貪心選擇最優(yōu)路徑的算法，其主要思想類似Directed Diffusion算法［25］，不同之處僅在于不同的最優(yōu)路徑的選擇準(zhǔn)則。在該算法中，每個(gè)節(jié)點(diǎn)還都會(huì)向網(wǎng)絡(luò)發(fā)送一個(gè)路徑探尋數(shù)據(jù)包，其中記錄了從源節(jié)點(diǎn)至當(dāng)前節(jié)點(diǎn)傳輸該數(shù)據(jù)包的所需能量。已存在于路徑樹中的每個(gè)節(jié)點(diǎn)還能夠產(chǎn)生一個(gè)遞增能耗數(shù)據(jù)包，該數(shù)據(jù)包即對(duì)應(yīng)著每個(gè)被節(jié)點(diǎn)接收到的新的路徑探尋數(shù)據(jù)包，而此遞增能耗數(shù)據(jù)包卻只能沿著節(jié)點(diǎn)至Sink節(jié)點(diǎn)的方向進(jìn)行發(fā)送以及更新，遞增能耗數(shù)據(jù)包經(jīng)過(guò)的區(qū)域也只能被最近的節(jié)點(diǎn) (即以最低能耗接收到相應(yīng)路徑探索數(shù)據(jù)包的節(jié)點(diǎn)) 更新，能耗最少的路徑將得到記錄，由此則構(gòu)造了由最近節(jié)點(diǎn)構(gòu)成的路徑樹GIT(greedy incremental tree)。其后在最優(yōu)路徑樹上探索具有空間相關(guān)性的節(jié)點(diǎn)，并在傳輸數(shù)據(jù)時(shí)進(jìn)行數(shù)據(jù)聚集，從而就減少了數(shù)據(jù)的傳輸量。文獻(xiàn)［26］提出了GIST算法，其中假設(shè)節(jié)點(diǎn)部署在一個(gè)方形區(qū)域，每個(gè)節(jié)點(diǎn)均知道自己的位置信息，其后即遞歸迭代地劃分區(qū)域，并構(gòu)造一棵overlay樹，樹中的每個(gè)點(diǎn)都代表區(qū)域內(nèi)的一個(gè)點(diǎn)。構(gòu)造結(jié)束后，Sink節(jié)點(diǎn)逐層向下發(fā)送數(shù)據(jù)請(qǐng)求，而在數(shù)據(jù)傳輸過(guò)程中，當(dāng)下層非葉子節(jié)點(diǎn)向上層節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，就要先消除數(shù)據(jù)的空間冗余后再向上傳輸。這樣一來(lái)就遞歸迭代地依次消除了空間冗余，從而減少了數(shù)據(jù)的傳輸量。文獻(xiàn)［27］提出了三個(gè)算法，分別是：DSC(DistributedSource coding)、 RDC (Routing Driven Compression )和 CDR(Compression Driven Routing)。這三個(gè)算法均是在數(shù)據(jù)傳輸時(shí)，將數(shù)據(jù)壓縮和路由選擇綜合起來(lái)考慮以最大限度地消除數(shù)據(jù)空間的冗余。文獻(xiàn)［28］提出了利用路由選擇來(lái)實(shí)現(xiàn)數(shù)據(jù)聯(lián)合最優(yōu)編碼，從而達(dá)到消除空間冗余的目的。文獻(xiàn)［29］提出了數(shù)據(jù)傳輸經(jīng)過(guò)中間結(jié)點(diǎn)時(shí)進(jìn)行編碼的算法，文中提到了兩種編碼方法：外編碼(foreign coding)和自編碼(self coding)。前者中，原始數(shù)據(jù)只有在數(shù)據(jù)傳輸時(shí)經(jīng)過(guò)的中間節(jié)點(diǎn)處進(jìn)行編碼，而后者中的原始數(shù)據(jù)則可以在本節(jié)點(diǎn)進(jìn)行編碼，只是其前提卻是必須有其他節(jié)點(diǎn)傳輸來(lái)的數(shù)據(jù)。文獻(xiàn)［30］提出了兩個(gè)算法E-Span(Energy-aware Spanning Tree)和LPT(Lifetime Preserving Tree)。其中，E-Span算法可用剩余能量最多的節(jié)點(diǎn)作為根節(jié)點(diǎn)，而其他節(jié)點(diǎn)則要根據(jù)自己和相鄰節(jié)點(diǎn)的剩余能量來(lái)確定父子關(guān)系，結(jié)構(gòu)樹建立之后，數(shù)據(jù)傳輸時(shí)非葉子節(jié)點(diǎn)將會(huì)融合其孩子節(jié)點(diǎn)的數(shù)據(jù)來(lái)消除數(shù)據(jù)空間冗余，如此即實(shí)現(xiàn)了遞歸地往匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))傳輸。LPT算法則選擇Directed Diffusion協(xié)議作為路由協(xié)議，具有剩余能量最多的節(jié)點(diǎn)即當(dāng)選為聚集父親 (aggregating parents) 節(jié)點(diǎn)，并且LPT具有自我恢復(fù)的特性，通過(guò)這一特性，當(dāng)出現(xiàn)某個(gè)節(jié)點(diǎn)失效或者網(wǎng)絡(luò)鏈路中斷的情況時(shí)，網(wǎng)絡(luò)的樹結(jié)構(gòu)即可得到修復(fù)與重建。文獻(xiàn)［30］又分別給出了集中式與分布式的LPT算法，進(jìn)一步通過(guò)仿真驗(yàn)證了在處理同一組數(shù)據(jù)時(shí)，兩種形式的LPT算法節(jié)點(diǎn)的能耗較為相似，同時(shí)還驗(yàn)證了LPT算法中節(jié)點(diǎn)的平均生命周期是高于E-Span算法中相應(yīng)指標(biāo)的。

3基于時(shí)空相關(guān)性的數(shù)據(jù)壓縮算法

文獻(xiàn)［31］提出了針對(duì)WSNs數(shù)據(jù)時(shí)空冗余的DIMENTIONS算法，DIMENTIONS先利用小波變換在節(jié)點(diǎn)內(nèi)消除數(shù)據(jù)的時(shí)間冗余，而后在分層的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中消除數(shù)據(jù)的空間冗余。該算法的優(yōu)點(diǎn)在于可以多分辨率提取數(shù)據(jù)特征，因此可根據(jù)實(shí)際情況獲取不同精度的數(shù)據(jù)；另外，該算法采用分布式結(jié)構(gòu)及隨機(jī)簇頭產(chǎn)生方案，有利于平衡節(jié)點(diǎn)間的能耗。DIMENTIONS算法的缺點(diǎn)卻在于需進(jìn)行多次小波變換，算法復(fù)雜度較高，同時(shí)對(duì)節(jié)點(diǎn)計(jì)算，存儲(chǔ)能力等要求也較高。文獻(xiàn)［32］考慮將Slepian-Wolf Coding［33］算法應(yīng)用到WSNs中來(lái)消除數(shù)據(jù)的時(shí)空冗余性。文獻(xiàn)［34］提出了GAMPS算法。首先，該算法動(dòng)態(tài)地將節(jié)點(diǎn)分簇，使得每個(gè)簇里的節(jié)點(diǎn)數(shù)據(jù)都是具有時(shí)空相關(guān)的，全部時(shí)空相關(guān)的節(jié)點(diǎn)就能進(jìn)行聯(lián)合壓縮。而后則在給定誤差界限的條件下，于時(shí)空相關(guān)的節(jié)點(diǎn)里選擇一個(gè)基礎(chǔ)信號(hào)，當(dāng)進(jìn)行數(shù)據(jù)傳輸時(shí)，只需要傳輸基礎(chǔ)信號(hào)和相關(guān)性參數(shù)即可。又有文獻(xiàn)提出了一個(gè)基于小波變換的算法。算法假設(shè)節(jié)點(diǎn)部署在一維的直線上，等距排列，并且給所有節(jié)點(diǎn)進(jìn)行編號(hào)，奇節(jié)點(diǎn)將數(shù)據(jù)發(fā)給偶節(jié)點(diǎn)，偶節(jié)點(diǎn)接收到數(shù)據(jù)后，聯(lián)合本節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行哈爾小波(Harr wavelets)變換，將得到的高頻系數(shù)按照一定的閾值壓縮后再轉(zhuǎn)發(fā)至匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))。同時(shí)，對(duì)偶節(jié)點(diǎn)重新進(jìn)行奇偶排序，再進(jìn)行哈爾小波變換后，又將新奇節(jié)點(diǎn)的低頻系數(shù)發(fā)給相鄰的新偶節(jié)點(diǎn)。此后即遞歸迭代地對(duì)新偶節(jié)點(diǎn)進(jìn)行哈爾小波變換，直到最后一組哈爾小波變換后，且將最后的高頻與低頻系數(shù)傳輸給匯聚節(jié)點(diǎn)。文獻(xiàn)［35］提出了一個(gè)應(yīng)用壓縮感知技術(shù)的算法，其主要思想是從源節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳輸數(shù)據(jù)的過(guò)程中，每經(jīng)過(guò)一個(gè)中間節(jié)點(diǎn)，則加上一項(xiàng)中間節(jié)點(diǎn)的數(shù)據(jù)值與某個(gè)系數(shù)的乘積，這樣節(jié)點(diǎn)傳輸耗能較均衡，數(shù)據(jù)的恢復(fù)在匯聚節(jié)點(diǎn)進(jìn)行，并通過(guò)應(yīng)用壓縮感知方面的理論知識(shí)來(lái)對(duì)數(shù)據(jù)進(jìn)行恢復(fù)。

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

由于傳感器節(jié)點(diǎn)具有有限的電池能量，因此如何提高節(jié)點(diǎn)的能量有效性就成為無(wú)線傳感器網(wǎng)絡(luò)各種協(xié)議設(shè)計(jì)時(shí)必須考慮的一個(gè)重要問(wèn)題。而且無(wú)線傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心且數(shù)據(jù)傳輸是能量消耗的主要部分，因此，減少數(shù)據(jù)的傳輸量將極大地減少節(jié)點(diǎn)的能量消耗。本文從數(shù)據(jù)的時(shí)間相關(guān)性、空間相關(guān)性以及時(shí)空相關(guān)性綜述了無(wú)線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)壓縮技術(shù)的研究進(jìn)展?，F(xiàn)有的數(shù)據(jù)壓縮算法存在的問(wèn)題是：其中一部分算法對(duì)資源有限的傳感器網(wǎng)絡(luò)來(lái)說(shuō)復(fù)雜性較高，而另一部分算法則是離線算法，因而具有較大的時(shí)延。針對(duì)這些問(wèn)題，可以研究復(fù)雜度較低，具有在線特性的數(shù)據(jù)壓縮算法，此類算法對(duì)于資源有限的傳感器網(wǎng)絡(luò)將更為適用。

參考文獻(xiàn)：

［1］孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京: 清華大學(xué)出版社，2005.

［2］AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: A survey［J］. Computer networks， 2002， 38(4): 393-422.

［3］MARANDOLA H， MOLLO J， WALTER P. REMBASS-II: the status and evolution of the Army‘s unattended ground sensor system［C］//Proceedings of Unattended Ground Sensor Technologies and Applications IV (SPIE)， 2002: 99-107.

［4］PAUL J L. Smart sensor Web: tactical battlefield visualization using sensor fusion［J］. IEEE Aerospace and Electronic Systems Magazine， 2006， 21(1): 13-20.

［5］SHANNON C. A mathematical theory of communication［J］. ACM SIGMOBILE Mobile Computing and Communications Review， 2001， 5(1):3-55.

［6］SRISOOKSAI T， KEAMARUNGSI K， LAMSRICHAN P， et al. Practical data compression in wireless sensor networks: A survey［J］. Journal of Network and Computer Applications， 2012， 35(1):37-59.

［7］TelosB datasheet ［OL］.http://www.willow.co.uk/TelosB_Datasheet.pdf

［8］JAGADISH H V， KOUDAS N， MUTHUKRISHNAN S， et al. Optimal histograms with quality guarantees［C］//VLDB， 1998， 98:24-27.

［9］KEOGH E， CHU S， HART D， et al. An online algorithm for segmenting time series［C］//ICDM， 2001:289-296.

［10］OLSTON C， JIANG J，WIDOM J. Adaptive filters for continuous queries over distributed data streams［C］//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM， 2003:563-574.

［11］JAIN A， CHANG E Y， WANG Y F. Adaptive stream resource management using kalman filters［C］//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM， 2004:11-22.

［12］CHAN F K P， FU A W C， YU C. Haar wavelets for efficient similarity search of time-series: with and without time warping［J］. IEEE Transactions on Knowledge and Data Engineering， 2003， 15(3):686-705.

［13］LAZARIDIS I， MEHROTRA S. Capturing sensor-generated time series with quality guarantees［C］//IEEE ICDE'03， 2003:429-440.

［14］DELIGIANNAKIS A， KOTIDIS Y， ROUSSOPOULOS N. Compressing historical information in sensor networks［C］//Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM， 2004:527-538.

［15］DESHPANDE A， GUESTRIN C， MADDEN S， et al. Model-driven data acquisition in sensor networks［C］//Internation Conference on Very Large Data Bases (VLDB)， 2004:588-599.

［16］CHU D， DESHPANDE A， HELLERSTEIN J M， et al. Approximate data collection in sensor networks using probabilistic models［C］//IEEE ICDE'06， 2006:48-59.

［17］LIN S， KALOGERAKI V， GUNOPULOS D， et al. Online information compression in sensor networks［C］//IEEE ICC'06， 2006:3371-3376.

［18］ELMELEEGY H， ELMAGARMID A K， CECCHET E， et al. Online piece-wise linear approximation of numerical streams with precision guarantees［J］. the VLDB Endowment， 2009， 2(1):145-156.

［19］LIU Y， LI J， GAO H， et al. Enabling ε-Approximate Querying in Sensor Networks［C］//VLDB′ 09， 2009: 563-574.

［20］RAFIEI D， MENDELZON A. Similarity-based queries for time series data［C］//ACM SIGMOD Record. ACM， 1997， 26(2):13-25.

［21］KORN F， JAGADISH H V， FALOUTSOS C. Efficiently supporting ad hoc queries in large datasets of time sequences［C］//ACM SIGMOD Record， 1997， 26(2): 289-300.

［22］CHAN K P， FU A W C. Efficient time series matching by wavelets［C］//IEEE ICDE’99， 1999:126-133.

［23］CHOU J， PETROVIC D， RAMCHANDRAN K. Tracking and exploiting correlations in dense sensor networks［C］//ProceedingsoftheAsilomarConferenceonSignals，SystemsandComputers. Berkeley， CA， USA， 2002， 1(3):39-43.

［24］INTANAGONWIWAT C， ESTRIN D， GOVINDAN R， et al. Impact of network density on data aggregation in wireless sensor networks［C］//Proceeding of the 22nd International Conference onDistributed Computing Systems， ICDCS 2002. IEEE， 2002:457-458.

［25］INTANAGONWIWAT C， GOVINDAN R， ESTRIN D. Directed diffusion: a scalable and robust communication paradigm for sensor networks［C］//Proceedings of MobiCom’00， Boston， MA， USA， 2000:56-67.

［26］JIA L， NOUBIR G G， RAJARAMAN R， et al. Gist: Group-independent spanning tree for data aggregation in dense sensor networks［M］//Distributed Computing in Sensor Systems. Springer Berlin Heidelberg， 2006:282-304.

［27］PATTEM S， KRISHNAMACHARI B， GOVINDAN R. The impact of spatial correlation on routing with compression in wireless sensor networks［J］. ACM Transactions on Sensor Networks (TOSN)， 2008， 4(4):24.

［28］CRISTESCU R， BEFERULL-LOZANO B， VETTERLI M. On network correlated data gathering［C］//IEEE INFOCOM'04， 2004， 4:2571-2582.

［29］RICKENBACH P V， WATTENHOFER R. Gathering correlated data in sensor networks［C］//Proceedings of the 2004 joint workshop on Foundations of mobile computing. ACM， 2004:60-66.

［30］LEE W M， WONG V W S. E-Span and LPT for data aggregation in wireless sensor networks［J］. Computer Communications， 2006， 29(13):2506-2520.

［31］GANESAN D， ESTRIN D， HEIDEMANN J. DIMENSIONS: Why do we need a new data handling architecture for sensor networks?［J］. ACM SIGCOMM Computer Communication Review， 2003， 33(1):143-148.

［32］XIONG Z， LIVERIS A D， CHENG S. Distributed source coding for sensor networks［J］. Signal Processing Magazine， IEEE， 2004， 21(5):80-94.

［33］SLEPIAN D D， WOLF J K. Noiseless coding of correlated information sources［J］. IEEE Transactions on Information Theory， 1973， 19(4):471-480.

［34］GANDHI S， NATH S， SURI S， et al. GAMPS: Compressing multi sensor data by grouping and amplitude scaling［C］//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ACM， 2009:771-784.

［35］LUO C， WU F， SUN J， et al. Compressive data gathering for large-scale wireless sensor networks［C］//Proceedings of the 15th Annual international conference on Mobile computing and networking. ACM， 2009:145-156.