甄志軍，魯士文

(中國科學院研究生院，北京100049)

0 引言

無線傳感器網(wǎng)絡是當前信息科學的熱點研究領域，在環(huán)境監(jiān)測、安全監(jiān)控、科研實驗等方面應用廣泛［1］。數(shù)量眾多的傳感器節(jié)點產生大量的數(shù)據(jù)，而無線傳感器網(wǎng)絡的能量供給、存儲能力和通信帶寬等資源相對有限，不適合傳送大數(shù)據(jù)量。為了減少傳輸?shù)臄?shù)據(jù)量，一般需要在網(wǎng)絡內部對原始采集的數(shù)據(jù)進行適當?shù)娜诤虾蛪嚎s處理。目前已有較多利用時間和空間相關性來進行數(shù)據(jù)融合和壓縮的算法和研究。DIDAS方案［2］是在各一跳節(jié)點來對二跳節(jié)點采集的數(shù)據(jù)進行一維離散余弦變換(discrete cosine transform，DCT)來去除數(shù)據(jù)間的空間冗余度，一跳節(jié)點再將壓縮后的數(shù)據(jù)傳輸至簇頭節(jié)點。然而，該方案沒有考慮時間冗余度，并且僅僅利用屬于相同一跳節(jié)點分支的各二跳節(jié)點之間的一維空間冗余度，而沒有將其應用于簇內所有節(jié)點之間?；诃h(huán)模型的分布式時空小波數(shù)據(jù)壓縮算法［3］基于虛擬網(wǎng)格構建環(huán)模型，將傳感器網(wǎng)絡中的數(shù)據(jù)抽象為一個矩陣，將時間相關性與空間相關性分別映射為該矩陣的小波列變換與行變換，從而利用二維小波變換來去除時間和空間冗余度。然而，雖然小波變換壓縮性能較好，但該算法將二維網(wǎng)格區(qū)域內的節(jié)點構建為一維的環(huán)模型，數(shù)據(jù)之間的二維空間相關性難以充分得到利用。

針對該問題，本文提出一種基于虛擬網(wǎng)格和DCT變換的數(shù)據(jù)融合算法(virtual-grid and DCT based data aggregation，VDDA)，該算法基于虛擬網(wǎng)格來構建采集數(shù)據(jù)矩陣，并分別利用時域差分與二維DCT變換來去除時間和空間冗余，從而降低節(jié)點能耗和提高網(wǎng)絡使用壽命。

1 基于虛擬網(wǎng)格的數(shù)據(jù)融合算法

本文提出的基于二維DCT變換的數(shù)據(jù)融合算法VDDA通過將節(jié)點分布不均勻的傳感器簇劃分為多個虛擬網(wǎng)格來去除部分密集節(jié)點間的冗余，并便于將其采集的數(shù)據(jù)組織為二維數(shù)據(jù)矩陣，連續(xù)2個時間點的數(shù)據(jù)矩陣進行差分以去除時間上的冗余，對該矩陣進行DCT變換和非均勻量化以去除空間上的冗余，最后進行編碼以去除碼間的冗余，其主要步驟如圖1所示。

圖1 VDDA算法的處理步驟Fig 1 Processing steps of VDDA algorithm

1.1 傳感器簇C劃分為虛擬網(wǎng)格G mn

為了有效地進行數(shù)據(jù)處理，研究中常將傳感器網(wǎng)絡分為多個簇(cluster)，并假定簇內節(jié)點間可以直接通信。每個簇選舉一個節(jié)點作為簇頭節(jié)點(cluster head)，簇頭節(jié)點收集簇內各成員節(jié)點采集到的數(shù)據(jù)。然而，由于傳感器網(wǎng)絡部署的隨機性(如飛機隨機投放)等原因，簇內的各成員節(jié)點分布并不均勻，某些區(qū)域的節(jié)點分布密度可能較大，因而存在著一定的冗余節(jié)點。如果不作去冗余處理，這些節(jié)點將因偵聽、發(fā)射和接收等處理而給網(wǎng)絡帶來額外的能量消耗。為此，將包含傳感器簇C的矩形區(qū)域G劃分為M×N個小區(qū)域Gmn，每個小區(qū)域稱為一個虛擬網(wǎng)格(virtual grid)。Gmn表示區(qū)域G中第m行第n列個虛擬網(wǎng)格，其中，m∈［9，M］，n∈［0，N］。行列數(shù)M，N 的取值由簇的大小、節(jié)點相關程度等因素決定，以保證每個網(wǎng)格中平均包含2～4個傳感器節(jié)點比較合適。在保證可覆蓋探測區(qū)域的前提下，設定每個虛擬網(wǎng)格內同時工作的節(jié)點數(shù)量為1，該節(jié)點稱為工作節(jié)點，其他節(jié)點處于休眠狀態(tài)。虛擬網(wǎng)格中某個休眠節(jié)點將在合適的時刻被喚醒，以代替因能量耗盡或其他原因而失效的工作節(jié)點，以保證整個網(wǎng)絡正常工作，達到延長網(wǎng)絡生存時間的目的［4］。

1.2 構建采集數(shù)據(jù)矩陣D

設虛擬網(wǎng)格Gmn中包含fmn個傳感器節(jié)點，其中的工作節(jié)點在某一特定的時間點采集的數(shù)據(jù)為Dmn，則Dmn即作為虛擬網(wǎng)格Gmn的采集數(shù)據(jù)，其由工作節(jié)點傳送至傳感器簇的簇頭節(jié)點H。如果某個虛擬網(wǎng)格Gmn中不包含有任何傳感器節(jié)點，即fmn=0，則可以根據(jù)其鄰域多個虛擬網(wǎng)格的采集數(shù)據(jù)來估計該虛擬網(wǎng)格的采集數(shù)據(jù)值Dmn，比如選取左右2個相鄰的虛擬網(wǎng)格的采集數(shù)據(jù)的算術平均值。

由此，在某一特定的時間點M×N個虛擬網(wǎng)格所采集的數(shù)據(jù)在簇頭節(jié)點H中構成一個M×N的二維采集數(shù)據(jù)矩陣D

1.3 構建待變換數(shù)據(jù)矩陣X(i)

簇頭節(jié)點H構建某一時間點的采集數(shù)據(jù)矩陣D，并進行后續(xù)的數(shù)據(jù)壓縮處理。設D(i)表示第i個時間點的采集數(shù)據(jù)矩陣，則虛擬網(wǎng)格在第i個時間點與第i－1個時間點的采集數(shù)據(jù)矩陣差值構成時域差分矩陣

由于時間間隔較短的前后2個時間點采集的數(shù)據(jù)具有較高的相關性，構建差分矩陣可以有效地去除時間方面的冗余。因此，為了提高壓縮效率，對于首個時間點，可對其原始采集數(shù)據(jù)進行壓縮處理，而對其他各時間點，則對差分矩陣來進行相應的壓縮處理。然而，如果長時間持續(xù)對差分數(shù)據(jù)進行編碼，則容易導致解碼端的誤碼擴散現(xiàn)象。為了均衡解碼失真和壓縮效率之間的矛盾，可以周期性地在某些時間點對原始采集數(shù)據(jù)來進行壓縮編碼，其余時間點則對其差分數(shù)據(jù)進行壓縮編碼。設待變換數(shù)據(jù)矩陣表示為X(i)，則

其中，T表示時間點周期，n為自然數(shù)。

1.4 DCT 變換

DCT擁有良好的解相關性能，常用于數(shù)據(jù)壓縮［5］。簇頭節(jié)點H對待變換數(shù)據(jù)矩陣X(i)進行二維DCT變換，得到正交變換后的數(shù)據(jù)矩陣Y(i)

其中，算子F［X］表示對輸入矩陣X進行二維DCT變換。由于DCT變換屬于正交變換，其能量集中特性使得包含較多能量的低頻分量集中至矩陣的左上角區(qū)域，而能量較低的高頻分量則集中至右下角，該性能有利于后續(xù)的非均勻量化。

1.5 量化和編碼

對DCT變換后的矩陣進行非均勻量化的各個量化門限即構成量化表，可以通過選擇不同的判決門限來調整數(shù)據(jù)的壓縮率。低頻分量可選擇較低的量化門限以減少數(shù)據(jù)失真，高頻分量則選擇較高的量化門限以提高壓縮效率。由于待變換矩陣X(i)中差分矩陣數(shù)值遠小于原始數(shù)據(jù)矩陣，可以選擇不同的量化表來對該2種矩陣分別量化。設Z(i)表示選取量化表QB對變換后矩陣Y(i)量化后得到的數(shù)據(jù)矩陣，即

然后，簇頭節(jié)點H對數(shù)據(jù)向量V(i)進行無損變長編碼VLC，得到AC部分的壓縮碼流

DC部分壓縮碼流S(i)DC和AC部分壓縮碼流S(i)AC組成總的壓縮碼流S(i)，即

簇頭節(jié)點H將該碼流傳輸至遠端的服務器。

1.6 服務器的數(shù)據(jù)處理

服務器接收到簇頭節(jié)點H傳輸來的壓縮碼流S(i)后，對其進行相應的解碼處理。該處理為本地簇頭節(jié)點H進行數(shù)據(jù)融合的逆過程，對壓縮碼流進行相應的解碼、反量化、DCT逆變換等處理，即可得到恢復后的采集數(shù)據(jù)矩陣

2 算法仿真

為了驗證算法的性能，利用Matlab來進行仿真。首先構建仿真數(shù)據(jù)模型以產生具有時間和空間相關性的模擬采集數(shù)據(jù)，然后利用VDDA算法對其進行壓縮，得到壓縮碼流，最后仿真服務器來對壓縮碼流進行解壓等逆處理，得到還原后的數(shù)據(jù)，并根據(jù)該些數(shù)據(jù)來計算數(shù)據(jù)壓縮率和失真等指標以評估算法的壓縮性能。

2.1 構建仿真數(shù)據(jù)模型

在仿真中，在一塊8m×8 m大小的區(qū)域內按高斯分布隨機地撒入150個溫度傳感器節(jié)點，該些節(jié)點構成傳感器簇C。將該傳感器簇C劃分為8×8的區(qū)域G，即M=N=8，每個虛擬網(wǎng)格Gmn中平均包含大約2～4個傳感器節(jié)點。

為了模擬溫度傳感器節(jié)點在某一特定時間點(如i=1時)檢測到的溫度數(shù)據(jù)，需考慮臨近節(jié)點采集數(shù)據(jù)之間的空間相關性。據(jù)研究，空間距離為d的2個節(jié)點所采集到的數(shù)據(jù)之間的相關系數(shù)f(d)正比于d－a，其中，α為大于0的參數(shù)［6］。假設每個節(jié)點的采集數(shù)據(jù)(信源)是獨立同分布的高斯隨機變量，其數(shù)值服從高斯分布N(μ，σ2)，其方差σ2與相關系數(shù)f(d)成正比。仿真中設α為2，σ2=d－2。

如圖2所示，為了簡便地模擬各個節(jié)點采集的具有空間相關性的溫度數(shù)據(jù)，在區(qū)域G中以中心點為基點均勻選取4個一級參考點，再以各一級參考點為基點分別均勻地選取4個二級參考點。假設區(qū)域G的中心點采集到的溫度為T0=25℃，各個傳感器節(jié)點在某一時間點(如i=1時)的模擬數(shù)據(jù)產生步驟為:

1)根據(jù)T0產生各一級參考點的溫度數(shù)據(jù)T1i:T1i～N(T0，1/8)，i∈［1，4］;

2)根據(jù)T1i得到各二級參考點的溫度數(shù)據(jù)T2ij:T2ij～N(T1i，1/24)，i，j∈［1，4］;

3)根據(jù)T2ij產生各個臨近工作節(jié)點的溫度數(shù)據(jù)Dmn:Dmn～ N(T2m'n'，1/d2)，其中，T2m'n'表示與虛擬網(wǎng)格 Gmn的工作節(jié)點最近的二級參考點的溫度，d表示該工作節(jié)點與該二級參考點之間的距離。

為了模擬其他時間點(如，i=2～5時)，需產生具有時間相關性的隨機數(shù)據(jù)。假設各節(jié)點的溫度值D(i)服從高斯分布N(μ，σ2)，其期望μ隨時間而線性變化，方差與時間間隔的負二次方成正比，即 μ =D(i－1)+kΔt，σ2=(Δt)－2。仿真中可設 k=1，Δt=2，周期 T=5。

圖2 仿真數(shù)據(jù)的產生過程示意圖Fig 2 Schematic diagram of the simulation data’s generating process

2.2 仿真參數(shù)的選擇

1)DCT變換選擇目前較常用的快速算法FDCT，以優(yōu)化計算速度和資源消耗;

2)量化表QB0，QB1需要根據(jù)Y(i)的數(shù)值范圍和期望數(shù)據(jù)壓縮率來進行選擇，即選擇各個頻率分量的閾值門限。該仿真中，選擇JPEG壓縮標準中的亮度量化表Q進行適當縮放來構成，即 QB0=Q/Qgain，QB1=Q/(Qgain×100)，其中，Qgain為可變量化縮放系數(shù);

3)對量化后矩陣Z(i)的AC分量進行Zigzag掃描后進行常用的霍夫曼編碼。

3 性能分析

3.1 數(shù)據(jù)壓縮率和量化縮放系數(shù)之間的關系

通過數(shù)據(jù)融合過程的數(shù)據(jù)壓縮率Ratio來評估數(shù)據(jù)融合算法的壓縮效率

其中，L表示所有節(jié)點采集數(shù)據(jù)的比特長度之和，Length(S(i))為壓縮碼流的數(shù)據(jù)長度。量化縮放系數(shù)Qgain可以控制變換后矩陣各個頻率分量的量化門限的大小，進而調整數(shù)據(jù)的壓縮率Ratio，如圖3所示。當Qgain越大，則量化門限矩陣(量化表)QB0，QB1越小，丟棄的數(shù)據(jù)量越少，數(shù)據(jù)壓縮率Ratio相應地越小。

圖3 Ratio和Qgain之間的關系Fig 3 Relation between Ratio and Qgain

從圖3中可以看出:Ratio隨著Qgain增加而增加，當Qgain達到20左右時逐漸趨于某個穩(wěn)定值;由于量化表QB0，QB1的選擇較合適，原始數(shù)據(jù)矩陣和差分矩陣的壓縮率相近。

3.2 均方誤差和量化縮放系數(shù)之間的關系

根據(jù)所有節(jié)點采集的溫度數(shù)據(jù)Dmn和還原后的數(shù)據(jù)來計算數(shù)據(jù)融合過程的均方誤差(MSE)，以此來評估該算法的數(shù)據(jù)失真情況

量化縮放系數(shù)Qgain同樣可以通過控制變化后矩陣各個頻率分量的量化門限的大小來調整數(shù)據(jù)融合過程的MSE。當Qgain越大，則量化門限矩陣(量化表)QB0，QB1越小，丟棄的數(shù)據(jù)量越少，還原后的數(shù)據(jù)則更接近原始采集數(shù)據(jù)，即其MSE越小，MSE與Qgain的關系如圖4。

圖4 MSE和Qgain之間的關系Fig 4 Relation between MSE and Qgain

從圖4中可以看出:隨著Qgain的增大而減小，當Qgain足夠大時，MSE趨近于零;由于量化表QB1數(shù)值較小，差分矩陣壓縮后的MSE接近于零。

3.3 數(shù)據(jù)壓縮率和綜合評價指數(shù)之間的關系

量化縮放系數(shù)Qgain與數(shù)據(jù)壓縮率Ratio正相關，而與MSE負相關。為衡量壓縮率和失真度的綜合效果，定義一個折衷的綜合評價指數(shù)S

該指數(shù)越小，則表明相應方案的效果越好。由于差分矩陣壓縮時(i≠nT+1)的MSE明顯較小，其綜合評價指數(shù)S較小，此節(jié)僅針對原始數(shù)據(jù)矩陣壓縮時(i=nT+1)。綜合評價系數(shù)S和Ratio的關系如圖5。

從圖5可以看出:提出的VDDA算法的綜合評價指數(shù)顯著小于DIDAS算法，因而其綜合壓縮性能更好。其原因主要在于:1)實現(xiàn)去冗余處理的相關節(jié)點范圍更廣，包括整個傳感器簇內的節(jié)點，而不限于屬于相同一跳節(jié)點的二跳節(jié)點;2)采用二維DCT變換以充分利用二維空間的相關性，而不是一維DCT變換;3)量化采用非均勻量化方式，即根據(jù)各個頻率分量的重要程度不同而選擇不同的量化門限，而不是采用同一門限的均勻量化。

圖5 綜合評價系數(shù)S和Ratio之間的關系Fig 5 Relation between S and Ratio

4 結論

節(jié)點數(shù)量眾多且分布稠密的傳感器網(wǎng)絡內部產生巨大的數(shù)據(jù)量，如何有效地對其進行融合和壓縮以適應傳感器網(wǎng)絡資源受限的現(xiàn)狀，是傳感器網(wǎng)絡研究中一項具有挑戰(zhàn)性的課題。本文提出的數(shù)據(jù)融合算法VDDA基于虛擬網(wǎng)格來構建采集數(shù)據(jù)矩陣，并對該數(shù)據(jù)矩陣或前后2個時間采集數(shù)據(jù)的差分矩陣進行二維DCT變換來去除時間和空間冗余度。仿真實驗和理論分析表明:該算法具有良好的壓縮性能，從而降低網(wǎng)絡能耗和提高網(wǎng)絡使用壽命。由于小波變換的壓縮性能更加優(yōu)越，利用3D小波變換來去除傳感器網(wǎng)絡采集數(shù)據(jù)的時空相關性是今后的研究方向。

［1］Akyildiz I F，Weilian S，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.IEEE Communications Magazine，2002，40:102－114.

［2］曹 萌，陳莘萌.一種基于DCT變換的傳感網(wǎng)簇內數(shù)據(jù)融合方案［J］.計算機工程與應用，2008，44(2):152－154，176.

［3］周四望，林亞平，張建明，等.傳感器網(wǎng)中基于環(huán)模型的小波數(shù)據(jù)壓縮算法［J］.軟件學報，2007，18(3):669－680.

［4］Xu Y，Heidemann J，Estrin D.Geography-informed energy conservation for Ad Hoc routing［C］∥Proc of the Annual Int'l Conf on Mobile Computing and Networking.New York:ACM Press，2001:70－84.

［5］Subhasis Saha.Image compression-from DCT to wavelets:A review［C］∥Spring 2000，2000:12－21.

［6］Apoorva Jindal，Konstantinos Psounis.Modeling spatially-correlated sensor network data［C］∥2004 First Annual IEEE communications Society Conference on Sensor and Ad Hoc Communications and Networks2004，IEEE SECON 2004，2004:162－171.