王 敏，吳中博，徐德剛，屈俊峰，吳 釗

(湖北文理學院數(shù)學與計算機科學學院，湖北 襄陽 441053)

基于預(yù)測模型的傳感器網(wǎng)絡(luò)近似數(shù)據(jù)采集算法*

王 敏，吳中博，徐德剛，屈俊峰，吳 釗

(湖北文理學院數(shù)學與計算機科學學院，湖北 襄陽 441053)

基于模型的數(shù)據(jù)采集技術(shù)可以有效抑制不必要的數(shù)據(jù)傳輸，節(jié)省能量開銷，已經(jīng)在傳感器網(wǎng)絡(luò)中得到廣泛應(yīng)用。對傳統(tǒng)基于模型的數(shù)據(jù)采集進行了改進，提出基于卡爾曼濾波器的近似數(shù)據(jù)采樣算法ADCA。ADCA可以在一定誤差范圍內(nèi)有效獲取數(shù)據(jù)?？臻g相近的節(jié)點被組織成簇，簇頭和成員分別建立卡爾曼濾波模型，并保存對方的鏡像模型。簇頭節(jié)點可以為成員節(jié)點產(chǎn)生近似的數(shù)據(jù)，所以用戶查詢可以通過簇頭來回答。實驗表明ADCA具有較好的性能。

預(yù)測模型；傳感器網(wǎng)絡(luò)；近似算法；數(shù)據(jù)采集

1 引言

在傳感器網(wǎng)絡(luò)中，大量傳感器節(jié)點自組織形成網(wǎng)絡(luò)，節(jié)點采樣后通過多跳的方式將數(shù)據(jù)傳回基站。節(jié)點都是電池供電的，而且由于部署環(huán)境復(fù)雜，一般難以更換電池，節(jié)約能量、延長傳感器網(wǎng)絡(luò)生命周期成為傳感器網(wǎng)絡(luò)研究的熱點問題。節(jié)點的能量開銷包含計算代價、通信代價、采樣代價等，其中通信消耗能量遠遠高于其他的能量消耗，所以我們在設(shè)計算法時以最小化通信開銷作為目標。研究人員在路由協(xié)議、事件監(jiān)測算法、網(wǎng)內(nèi)聚集等算法、近似數(shù)據(jù)采集等很多層面都提出了算法，以減少節(jié)點的通信開銷。

對于類似的技術(shù)，每個節(jié)點單獨估計其采樣。我們注意到，臨近的節(jié)點之間具有空間相關(guān)性，它們往往具有相似的變化趨勢。我們提出近似數(shù)據(jù)采集算法ADCA(Approximate Data Collection Algorithm)，ADCA算法的目標是在閾值范圍內(nèi)有效預(yù)測節(jié)點的采樣。ADCA算法利用卡爾曼濾波器，利用先前的預(yù)測值和當前的采樣值來預(yù)測下一個采樣值。預(yù)測采樣時利用了節(jié)點的空間相關(guān)性，節(jié)點的采樣值是在變化的，但是對于具有空間相關(guān)性的不同節(jié)點而言，他們之間的差是相對穩(wěn)定的。為了利用空間相關(guān)性，我們把節(jié)點組織成簇，每個簇有一個簇頭，簇頭負責估計其采樣值和節(jié)點采樣之間的差。

論文組織如下，第2節(jié)介紹相關(guān)工作，第3節(jié)介紹卡爾曼濾波器，第4節(jié)介紹我們的算法，第5節(jié)是實驗，最后是總結(jié)。

2 相關(guān)工作

傳感器網(wǎng)絡(luò)包含了大量的節(jié)點，將所有數(shù)據(jù)收集上來是不現(xiàn)實的，會導(dǎo)致節(jié)點浪費過多能量，對原始數(shù)據(jù)進行數(shù)據(jù)聚集然后再進行傳送，可以避免傳送大量的原始信息所帶來的通信開銷。在數(shù)據(jù)聚集方面，文獻[1]提出了TAG(Tiny Aggregation)算法。TAG算法在網(wǎng)內(nèi)構(gòu)造樹結(jié)構(gòu)，數(shù)據(jù)從葉子節(jié)點沿路由樹向基站節(jié)點傳送，中間節(jié)點不斷進行聚集計算得到部分聚集值，最后根節(jié)點得到最終的聚集值。文獻[2]采用多路徑傳輸算法對TAG算法進行了改進，對于距離基站較遠的節(jié)點采用路由樹結(jié)構(gòu)，降低網(wǎng)絡(luò)能量開銷；對于距離基站較近的節(jié)點采用多路徑路由，可以有效降低數(shù)據(jù)丟失率。

另外一個比較簡單的減少通信開銷的方法是采用時間抑制方法，節(jié)點僅當其采樣發(fā)生變化后才傳輸數(shù)據(jù)。這種策略適合于環(huán)境比較穩(wěn)定的情況。然而，節(jié)點的采樣會隨著時間的變化而變化。當節(jié)點采樣變化比較劇烈時，節(jié)點將頻繁發(fā)送采樣數(shù)據(jù)到基站，其能量將很快消耗殆盡。

大多數(shù)的應(yīng)用不需要高度精確的數(shù)據(jù)，所以開發(fā)了一些近似的數(shù)據(jù)采集技術(shù)。為了估計節(jié)點采樣，Madden S R[3]提出了PAQ(Probabilistic Adaptable Query)算法。PAQ算法基于靜態(tài)的自回歸的時間序列模型，提出了一種動態(tài)的自回歸模型來進行采樣值的預(yù)測：

(1)

其中,b(w)N(0，1)表示零均值和標準差的高斯白噪聲。為了比較精確地進行采樣預(yù)測，需要合適的α、β、γ，PAQ需要很長的學習過程以建立靜態(tài)數(shù)據(jù)模型。

文獻[4]介紹了Snapshot查詢方法。節(jié)點可以和鄰居合作，選擇一個代表性節(jié)點的集合。代表性節(jié)點使用線性回歸來預(yù)測他們鄰居節(jié)點的采樣。為了保持代表性節(jié)點的集合，作者假設(shè)每個節(jié)點知道他的鄰居的采樣值。所以，節(jié)點必須周期性地廣播其采樣給鄰居，這將會消耗過多的能量。由于代表性節(jié)點在非廣播周期不知道其他節(jié)點的采樣，所以不能保證誤差范圍。

3 卡爾曼濾波器

有許多方法被用來預(yù)測傳感器節(jié)點的采樣值，例如線性回歸、貝葉斯網(wǎng)絡(luò)方法等?？柭鼮V波器也是常用的一種算法，用來解決離散數(shù)據(jù)的線性濾波問題。卡爾曼濾波器可以用在很多場合，例如信號處理、模式匹配等。文獻[5]提出了一種自適應(yīng)容積卡爾曼濾波算法，構(gòu)造了一組噪聲統(tǒng)計估計器對噪聲的統(tǒng)計特征進行實時估計，在測量異常時利用修正函數(shù)對濾波過程進行修正，可以有效提高濾波估計的精度，并對濾波發(fā)散有較好的抑制能力。文獻[6]針對無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合時的丟包問題，對傳統(tǒng)擴散卡爾曼濾波進行了改進，并給出了丟包問題的改善方案。文獻[7]在基于接收信號強度RSSI(Received Signal Strength Indication)測距、三邊測量法初始定位的基礎(chǔ)上，提出以接收信號強度為觀測量，將無跡卡爾曼濾波UKF(Unscented Kalman Filter)應(yīng)用到節(jié)點精確定位中。

卡爾曼濾波器是由數(shù)學方程估計的內(nèi)部狀態(tài)系統(tǒng)使用一個預(yù)估-校正型的估計，如圖1所示。

Figure 1 Model of Kalman filter圖1 卡爾曼濾波模型

在卡爾曼濾波器中，系統(tǒng)模型用公式(2)和公式(3)表示：

(2)

zk=Hxk+vk

(3)

其中，公式(2)表示處理模型。

(4)

(5)

在離散的卡爾曼濾波器中，公式(4)預(yù)測未來采樣。公式(5)是對估計的修正。n×m矩陣Kk被稱為卡爾曼增益。

(6)

(7)

然后,后驗誤差估計協(xié)方差用公式(8)導(dǎo)出：

(8)

卡爾曼濾波器不存儲之前的數(shù)據(jù)集，為了在k時刻預(yù)測下一個采樣，卡爾曼濾波器僅僅需要k時刻的測量值和k-1時刻的預(yù)測值。

4 ADCA算法

傳感器節(jié)點能量有限且無法進行遠距離的傳輸，因此傳感器節(jié)點在部署時密度會比較高。位置相近的傳感器節(jié)點感知的數(shù)據(jù)也會比較相似，它們之間存在著空間相關(guān)性[8～10]。這一節(jié)，介紹我們提出的ADCA算法。ADCA算法將節(jié)點組織成簇，通過空間關(guān)系監(jiān)視節(jié)點采樣。對于傳感器節(jié)點而言，通信開銷遠遠大于計算開銷，所以我們不考慮計算開銷。假設(shè)所有節(jié)點具有相同的通信距離c，簇頭通過多跳和基站通信。

假設(shè)簇頭CH有兩個成員n1和n2。在之前的工作中，每個節(jié)點保持它們自己的模型，獨立預(yù)測未來采樣。如圖2所示，虛線表示估計值，實線表示實際采樣值。如果估計值和實際值的差別高于實現(xiàn)規(guī)定的閾值，n1和n2將他們的采樣傳給簇頭。在簇頭收集了成員的采樣值后，其將所有數(shù)據(jù)傳給基站，上述描述中需要至少三條消息。n1和n2各發(fā)一條消息給簇頭，簇頭發(fā)一條消息給基站。

Figure 2 Example of model based data collection圖2 基于模型的數(shù)據(jù)采集示例

我們對此進行了改進。簇頭將其采樣廣播給成員，成員如果不反饋，簇頭就知道他們依然保持空間相關(guān)性，這樣就只需要發(fā)送兩條消息。

(9)

如圖3所示，簇頭節(jié)點CH具有卡爾曼濾波器KFch，用于估計vch。每個成員節(jié)點也保持KFch。每個成員ni節(jié)點同時還具有卡爾曼濾波器KFdni，以估計其采樣和簇頭采樣之間的差dni。

Figure 3 Kalman filter in cluster圖3 分簇下的卡爾曼濾波器

□

5 實驗

在這一節(jié)，驗證所提出算法的效率，比較ADCA、PAQ、Snapshot方法的性能。用OMNET++仿真平臺來模擬算法過程，實驗設(shè)置如下，傳感器網(wǎng)絡(luò)包含100個節(jié)點，部署在100m×100m的區(qū)域。基站部署在區(qū)域的中央，節(jié)點的通信距離是20m。實驗數(shù)據(jù)采用合成的數(shù)據(jù)集。我們使用正弦函數(shù)構(gòu)造，為每個地點的節(jié)點分配[0.0,50.0]的數(shù)值，具有相同x坐標的節(jié)點具有同樣的值，然后我們模擬波浪從左往右垂直移位。為了測量不同環(huán)境下的能量消耗，我們使用三種誤差范圍0.2、0.1和0.05。

節(jié)點傳輸m-bit的消息給距離c外的節(jié)點將消耗：

(10)

接收消息將消耗：

(11)

其中,Eelec表示發(fā)送或接收單元消耗的能量，ξamp表示發(fā)送放大器消耗的能量。實驗中將Eelec設(shè)置為50nJ/bit，將ξamp設(shè)置為100pJ/bit/m2。

圖4展示了不同算法的能量消耗情況?？偟膩碚f，隨著誤差范圍的增加，需要傳輸?shù)臄?shù)據(jù)減少了，能量的消耗也變少了。圖5展示了誤差范圍為0.1的情況下，傳感器網(wǎng)絡(luò)運行至第一個節(jié)點失效時的情況。圖5中左圖表示100個節(jié)點的情況，右圖表示500個節(jié)點的情況。Snapshot算法中節(jié)點必須周期性地廣播其采樣給鄰居，這將會消耗過多的能量，所以它表現(xiàn)出的性能最差。PAQ算法基于自回歸模型，需要一個很長的學習階段。當數(shù)據(jù)相對穩(wěn)定時，PAQ算法可以精確地估計未來采樣值。然而，我們的數(shù)據(jù)集中，節(jié)點采樣隨著時間的變化在不斷變化，所以PAQ算法的表現(xiàn)也不如ADCA算法。相比較而言ADCA算法表現(xiàn)出了更優(yōu)異的性能。

Figure 4 Average energy consumption圖4 平均能量消耗

Figure 5 Rounds of first sensor failure圖5 第一個節(jié)點失效時數(shù)據(jù)采集的輪數(shù)

6 結(jié)束語

本文對傳統(tǒng)基于模型的數(shù)據(jù)采集進行了改進，提出基于卡爾曼濾波器的近似數(shù)據(jù)采樣算法ADCA。ADCA算法將空間相近的節(jié)點組織成簇，簇頭和成員分別建立卡爾曼濾波模型，并保存對方的鏡像模型。簇頭節(jié)點可以在成員節(jié)點不傳輸數(shù)據(jù)的情況下預(yù)測其采樣，從而大大降低通信開銷，實驗表明ADCA具有較好的性能。

[1]MaddenSR,FranklinMJ,HellersteinJM,etal.TAG:Atinyaggregationserviceforad-hocsensornetworks[J].ACMSIGOPSOperatingSystemsReview, 2002, 36(SI):131-146.

[2]MaddenSR,FranklinMJ,HellersteinJM,etal.TinyDB:Anacquisitionalqueryprocessingsystemforsensornetworks[J].ACMTransactionsonDatabaseSystems(TODS), 2005, 30(1):122-173.

[3]TuloneD,MaddenSR.PAQ:Timeseriesforecastingforapproximatequeryansweringinsensornetworks[C]∥EuropeanWorkshoponWirelessSensorNetworks, 2006:21-37.

[4]KotidisY.Snapshotqueries:Towardsdata-centricsensornetworks[C]∥Procofthe29thInternationalConferenceonDataEngineering(ICDE), 2005:131-142.

[5]AoZhi-gang,TangChang-chun,FuCheng-qun,etal.Multi-sensoradaptivecubatureKalmanfilterdatafusionalgorithm[J].ApplicationResearchofComputers, 2014, 31(5):1312-1315.(inChinese)

[6]NieWen-mei,LuGuang-yue.ImproveddiffusionKalmanalgorithmwithpacket-droppinginwirelesssensornetworks[J].JournalofXi’anUniversityofPostsandTelecommunications, 2013, 18(4):9-12.(inChinese)

[7]DuJuan-juan.ApplicationofunscentedKalmanfilteralgorithmtonodelocalizationinwirelesssensornetworks[J].JournalofNanjingUniversityofPostsandTelecommunications(NaturalScience), 2013, 33(1):84-90.(inChinese)

[8]JindalA,PsounisK.Modelingspatiallycorrelateddatainsensornetworks[J].ACMTransactionsonSensorNetworks, 2006, 2(4):466-499.

[9]WangC,MaH,HeY,etal.Adaptiveapproximatedatacollectionforwirelesssensornetworks[J].IEEETransactionsonParallelandDistributedSystems, 2012, 23(6):1004-1016.

[10]FatchB,GovindarasuM.Energyminimizationbyexploitingdataredundancyinreal-timewirelesssensornetworks[J].AdHodNetworks, 2013, 11(6):1715-1731.

附中文參考文獻：

[5] 敖志剛, 唐長春, 付成群,等. 多傳感器自適應(yīng)容積卡爾曼濾波融合算法[J]. 計算機應(yīng)用研究, 2014, 31(5):1312-1315.

[6] 聶文梅, 盧光躍. 無線傳感器網(wǎng)絡(luò)中丟包擴散卡爾曼算法的改進[J]. 西安郵電大學學報, 2013, 18(4):9-12.

[7] 杜娟娟. 無跡卡爾曼濾波在無線傳感器網(wǎng)絡(luò)節(jié)點定位中的應(yīng)用[J]. 南京郵電大學學報(自然科學版), 2013, 33(1):84-90.

WANGMin,born in 1982,MS,lecturer,CCF member(E200037518M)，her research interests include database, and sensor network.

吳中博(1980),男,湖北襄陽人，博士，副教授，CCF會員(E200027710M)，研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘和傳感器網(wǎng)絡(luò)。E-mail:rucwzb@163.com

WUZhong-bo,born in 1980,PhD,associate professor,CCF member(E200027710M)，his research interests include database, data mining, and sensor network.

Anapproximatedatacollectionalgorithmbasedonpredictionmodelinsensornetworks

WANG Min，WU Zhong-bo，XU De-gang,QU Jun-feng,WU Zhao

(School of Mathematics and Computer Science,Hubei University of Arts and Science,Xiangyang 441053,China)

The model-based data collection technology which can inhibit unnecessary data transportation and save energy effectively has been widely applied in sensor networks. We improve the traditional model-based data collection technology and put forth an approximate data collection algorithm based on the Kalman filter,called ADCA, which can collect data effectively within a given range of error.In ADCA,sensor nodes are organized as clusters.Cluster header and cluster members build the Kalman filter respectively and save their mirror models.Cluster header can produce approximate data for cluster members,so some user queries can be answered by cluster header.Experiments show that ADCA has good performance.

prediction model;sensor network;approximate algorithm;data collection

1007-130X(2014)11-2148-05

2014-06-25;

：2014-08-29

國家自然科學基金資助項目(61202046)

：吳中博(rucwzb@163.com)

TP274

：A

10.3969/j.issn.1007-130X.2014.11.016

王敏(1982),女,山西晉城人，碩士，講師，CCF會員(E200037518M)，研究方向為數(shù)據(jù)庫和傳感器網(wǎng)絡(luò)。E-mail:meiwen1982@qq.com

通信地址：441053湖北省襄陽市隆中路296號湖北文理學院數(shù)學與計算機科學學院

Address:School of Mathematics and Computer Science,Hubei University of Arts and Science,296 Longzhong Rd,Xiangyang 441053,Hubei,P.R.China