一種無線傳感器網(wǎng)絡(luò)缺失數(shù)值估計(jì)算法*

闞 杰， 張瑞瑞， 陳立平

(1.首都師范大學(xué) 信息工程學(xué)院，北京 100048； 2.國家農(nóng)業(yè)智能裝備工程技術(shù)研究中心，北京 100097；3.農(nóng)業(yè)部 農(nóng)業(yè)信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100097； 4.中國農(nóng)業(yè)大學(xué) 信息與電氣工程學(xué)院，北京 100083)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是集成無線傳輸能力、感知能力和計(jì)算能力的節(jié)點(diǎn), 通過相互協(xié)作而形成的自組織網(wǎng)絡(luò)[1～3]。由于傳感器節(jié)點(diǎn)受隨機(jī)環(huán)境因素和自身穩(wěn)定性干擾，節(jié)點(diǎn)感知數(shù)據(jù)往往出現(xiàn)缺失異常問題，大大影響了傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量[4,5]。如何有效地估計(jì)和恢復(fù)數(shù)據(jù)，是WSNs系統(tǒng)非常重要的一環(huán)。

文獻(xiàn)[6] 結(jié)合時(shí)空相關(guān)性提出DESM算法,算法利用鄰居節(jié)點(diǎn)相關(guān)數(shù)據(jù)對(duì)缺失感知數(shù)據(jù)進(jìn)行估計(jì)恢復(fù)。文獻(xiàn)[7]采用多元線性回歸模型，同時(shí)結(jié)合時(shí)空相關(guān)性和加權(quán)平均方法，提出STM算法。文獻(xiàn)[8]提出MR算法，將數(shù)據(jù)序列分為平穩(wěn)段和非平穩(wěn)段，平穩(wěn)段采用時(shí)間序列上的線性插值方法，非平穩(wěn)段采用基于空間相關(guān)性的多元線性回歸方法，最后對(duì)2種估計(jì)值進(jìn)行加權(quán)平均得到穩(wěn)定恢復(fù)值。文獻(xiàn)[9]中提出WARM算法，以數(shù)據(jù)挖掘?yàn)榛A(chǔ)，尋找異常數(shù)據(jù)節(jié)點(diǎn)相關(guān)聯(lián)的其他節(jié)點(diǎn)，并作為其估計(jì)值。文獻(xiàn)[10]中對(duì)WARM算法進(jìn)行改進(jìn)，提出CARM算法。算法通過計(jì)算感知數(shù)值關(guān)聯(lián)規(guī)則，得到多節(jié)點(diǎn)頻繁模式，并以此對(duì)異常數(shù)據(jù)進(jìn)行估計(jì)。以上算法都能夠獲得較好的效果，但算法對(duì)當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)依賴性較強(qiáng)，存在一定局限性。

本文提出一種基于BP神經(jīng)網(wǎng)絡(luò)的缺失數(shù)值估計(jì)(va-lue estimation with BP neural network,VEBP)算法，利用節(jié)點(diǎn)自身多參數(shù)相關(guān)性進(jìn)行數(shù)值估計(jì)。為提高估計(jì)精度和穩(wěn)定性，將線性回歸模型引入VEBP算法,提出VEBP-LR算法，利用加權(quán)平均，最終得出穩(wěn)定的估計(jì)值。

1 問題定義與模型選擇

1.1 問題定義

WSNs中節(jié)點(diǎn)以固定周期進(jìn)行數(shù)據(jù)采集，得到時(shí)間維度上離散數(shù)據(jù)集。假設(shè)節(jié)點(diǎn)nk在一時(shí)間序列內(nèi)采集到某監(jiān)測參數(shù)數(shù)據(jù)集合為Dk={dk1,dk2,…,dkt}，其中，dkt為節(jié)點(diǎn)k在t時(shí)刻實(shí)際采集數(shù)據(jù)。若數(shù)據(jù)集合內(nèi)某時(shí)刻的采集數(shù)據(jù)dki丟失，則問題可描述為：尋求一種方法求取其估計(jì)值kt，該估計(jì)值能夠盡可能精確且滿足實(shí)際應(yīng)用需求。

1.2 BP神經(jīng)網(wǎng)絡(luò)模型

BP網(wǎng)絡(luò)是一種單向傳播的多層前向網(wǎng)絡(luò)，由輸出層向輸入層逐步反饋的學(xué)習(xí)算法。已證明，僅有一個(gè)非線性隱含層的BP前饋網(wǎng)絡(luò)就能以任意精度逼近任意復(fù)雜度的函數(shù)[11,12]。

圖1 三層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

構(gòu)造BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型之前，為了避免不同參數(shù)間因數(shù)量級(jí)差別造成誤差，需要對(duì)輸入?yún)?shù)進(jìn)行歸一化處理，本文使用的歸一化方法為

(1)

式中μi為BP網(wǎng)絡(luò)第i維輸入?yún)?shù)集均值；?i為BP網(wǎng)絡(luò)第i維輸入?yún)?shù)集標(biāo)準(zhǔn)差。

1.3 線性回歸模型

對(duì)于監(jiān)測參數(shù)變化穩(wěn)定部分?jǐn)?shù)據(jù)中的缺失值，通過鄰近時(shí)間數(shù)據(jù)進(jìn)行線性回歸處理，可得到缺失值的插值估計(jì)量，即LR算法。假設(shè)節(jié)點(diǎn)某時(shí)間段內(nèi)感知數(shù)據(jù)集為D={d1,d2,…,dn}，其中,di為i(i=1,2,…,n)時(shí)刻采集數(shù)據(jù)，若di丟失，則可以通過選取i時(shí)刻鄰近時(shí)間點(diǎn)數(shù)據(jù)進(jìn)行線性擬合，建立線性回歸方程求解i時(shí)刻缺失值估計(jì)量i。例如:可以選取di-1和di+1構(gòu)造線性回歸函數(shù)為

(2)

對(duì)于i時(shí)刻缺失值，將i代入式(1)即可得到其估計(jì)量i。線性回歸模型雖然簡單，但只能用于數(shù)據(jù)平穩(wěn)變化的時(shí)間段，難以應(yīng)對(duì)波動(dòng)較大的數(shù)據(jù)段，因此,下面將提出一種基于BP神經(jīng)網(wǎng)絡(luò)的非線性映射估計(jì)算法，算法能有效地解決非平穩(wěn)波動(dòng)數(shù)據(jù)段缺失值估計(jì)問題。

2 VEBP算法

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)具有多參數(shù)感知能力，如溫度、濕度、光照等。圖2描述了三種(環(huán)境溫度、濕度和土壤溫度)實(shí)際采集數(shù)據(jù)變化情況；表1顯示了它們之間相關(guān)系數(shù)，數(shù)據(jù)來自北京市小湯山國家精準(zhǔn)農(nóng)業(yè)示范基地2013年5月?？梢钥闯觯和寥罍囟群铜h(huán)境溫度、空氣相對(duì)濕度具有顯著的相關(guān)性。因此，當(dāng)對(duì)某一參數(shù)缺失值進(jìn)行估計(jì)時(shí)，通過其它相關(guān)參數(shù)進(jìn)行估計(jì)是可行的。

圖2 相同時(shí)間段環(huán)境溫度、環(huán)境濕度和土壤溫度典型變化

表1 參數(shù)相關(guān)性表(樣本數(shù)n=300)

假設(shè)對(duì)土壤溫度缺失值進(jìn)行估計(jì)，即它為BP神經(jīng)網(wǎng)絡(luò)的預(yù)測輸出。首先選取同節(jié)點(diǎn)其它強(qiáng)相關(guān)參數(shù)集作為算法輸入。輸入?yún)?shù)集的選取非常重要，必須尋求最優(yōu)輸入?yún)?shù)集使得缺失估計(jì)值精度最高，選取過程見1.1小節(jié)，然后對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練。假設(shè)輸入?yún)?shù)集確定為環(huán)境溫度和環(huán)境濕度，它們便是BP網(wǎng)絡(luò)的輸入量。其中，輸入輸出參數(shù)集中樣本容量大小也是影響預(yù)測模型估計(jì)精度的重要因素，樣本容量較小則不能精確反映參數(shù)映射關(guān)系，樣本容量較大則可能因?yàn)闀r(shí)間維度上的規(guī)律遷移導(dǎo)致模型精度下降。由時(shí)間相關(guān)性可知，離缺失值時(shí)間點(diǎn)越近的樣本越能精確的表示其估計(jì)量，為保證數(shù)據(jù)完整性，樣本選取應(yīng)以缺失值時(shí)刻為中心的鄰近點(diǎn)集合，樣本容量不小于一周期數(shù)據(jù)。

為了消除冗余參數(shù)對(duì)VEBP算法干擾，需要對(duì)輸入?yún)?shù)集進(jìn)行優(yōu)化選擇，首先對(duì)節(jié)點(diǎn)不同感知數(shù)據(jù)樣本進(jìn)行相關(guān)性計(jì)算，從中選取相關(guān)性最高子集，構(gòu)成輸入樣本。具體描述步驟如下：

假設(shè)單一節(jié)點(diǎn)具有n個(gè)感知參數(shù)，t時(shí)刻第i個(gè)參數(shù)采集數(shù)據(jù)表示為xit，則傳感器數(shù)據(jù)集可描述為矩陣X，如下

(3)

1)計(jì)算樣本相關(guān)系數(shù)rij:rij表示第i個(gè)參數(shù)樣本與第j個(gè)參數(shù)樣本之間的相關(guān)系數(shù)，采用簡單樣本相關(guān)系數(shù)計(jì)算方法

(4)

2)將樣本相關(guān)系數(shù)排序，選擇排序較高相關(guān)系數(shù)子集作為預(yù)測模型輸入量。

3 VEBP-LR算法

由于環(huán)境復(fù)雜，參數(shù)時(shí)空相關(guān)性處于動(dòng)態(tài)變化中。LR算法基于時(shí)間相關(guān)性構(gòu)造缺失估計(jì)值，對(duì)數(shù)據(jù)穩(wěn)定變化部分估計(jì)精度較高，但隨著采樣周期增加其估計(jì)精度降低，且難以適用于非穩(wěn)定變化部分。對(duì)于VEBP算法，其缺失值估計(jì)過程并不受數(shù)據(jù)變化的明顯影響，但由于其受到其他參數(shù)集限制，數(shù)據(jù)穩(wěn)定變化時(shí)，其估計(jì)精度一般低于LR算法。為了有效提高算法的穩(wěn)定性，引入加權(quán)系數(shù)，同時(shí)結(jié)合LR算法和VEBP算法進(jìn)行缺失值估計(jì)，即VEBP-LR算法。

假設(shè)LR算法和VEBP算法分別計(jì)算得到某時(shí)刻缺失值估計(jì)量為LR和VEBP。首先，VEBP-LR算法計(jì)算對(duì)應(yīng) 2個(gè)加權(quán)系數(shù)w1和w2，則VEBP-LR算法計(jì)算得到該時(shí)刻的估計(jì)值可以表示為

VL=w1·LR+w2·VEBP,

(5)

式中 0≤w1，w2≤1。

當(dāng)缺失值處于穩(wěn)定變化段時(shí)LR更為可信;反之,VEBP更為可信。因此，將權(quán)系數(shù)定義如下

(6)

式中T為缺失值所處時(shí)間點(diǎn)，maxT表示距離T時(shí)刻最近的極大值數(shù)據(jù)時(shí)間點(diǎn)，minT表示距離T時(shí)刻最近的極小值數(shù)據(jù)時(shí)間點(diǎn)。因此 ，w1=1-α,w2=α。由于VEBP-LR算法綜合考慮了2種不同情況，因此,能夠獲得更加穩(wěn)定的估計(jì)效果。

4 實(shí)驗(yàn)分析

以北京市小湯山國家精準(zhǔn)農(nóng)業(yè)示范基地2013年5月實(shí)際采樣數(shù)據(jù)為實(shí)驗(yàn)仿真樣本，采樣周期為10 min，以Matlab為算法仿真平臺(tái)。根據(jù)樣本相關(guān)性計(jì)算，VEBP算法輸入?yún)?shù)集選取空氣溫度、空氣濕度，輸出參數(shù)為土壤溫度。BP神經(jīng)網(wǎng)絡(luò)不同隱藏層對(duì)應(yīng)訓(xùn)練誤差如表2所示，可知其結(jié)構(gòu)設(shè)置為2×9×1的結(jié)構(gòu)。為了進(jìn)行算法估計(jì)誤差計(jì)算，仿真實(shí)驗(yàn)選取原始不含缺失值的數(shù)據(jù)集合，隨機(jī)標(biāo)記其中部分?jǐn)?shù)據(jù)為缺失值，通過比較算法估計(jì)值和真實(shí)值即可得出估計(jì)誤差。本文選取均方根誤差(RMSE)為評(píng)價(jià)標(biāo)準(zhǔn)。

表2 神經(jīng)網(wǎng)絡(luò)隱含層節(jié)點(diǎn)數(shù)與相應(yīng)訓(xùn)練誤差

首先，從仿真樣本參數(shù)相關(guān)性出發(fā)，使用VEBP算法對(duì)土壤溫度參數(shù)整體進(jìn)行估計(jì)效果仿真分析，結(jié)果如圖3所示。結(jié)果顯示:土壤溫度實(shí)測值與估計(jì)值決定系數(shù)達(dá)0.930，預(yù)測結(jié)果的RMSE和AE分別達(dá)到0.83，0.54 ℃，預(yù)測值和實(shí)測值趨勢基本一致，精度比較理想。

圖3 土壤溫度估計(jì)值與實(shí)測值對(duì)比

由于本文所述估計(jì)算法性能主要受節(jié)點(diǎn)采樣間隔影響，因此，仿真實(shí)驗(yàn)將設(shè)置不同的采樣間隔對(duì)算法結(jié)果進(jìn)行比較。以20 min為例，分別設(shè)置20～120 min為節(jié)點(diǎn)采樣間隔進(jìn)行對(duì)比實(shí)驗(yàn)仿真。仿真結(jié)果如圖4所示。 可以看出:當(dāng)采樣周期較短時(shí)，由于時(shí)間相關(guān)性較強(qiáng)，線性回歸LR算法估計(jì)誤差最小，效果好于VEBP算法。隨著采樣間隔的增加，可以看到線性回歸算法誤差逐漸增大，并且在100 min時(shí)超過VEBP算法，由于其完全依賴于時(shí)間維度上的鄰近采樣點(diǎn)進(jìn)行計(jì)算，當(dāng)采樣間隔增加，時(shí)間相關(guān)性逐漸降低，估計(jì)精度也逐漸減低。當(dāng)時(shí)間相關(guān)性降低時(shí)，基于參數(shù)間相關(guān)性的VEBP算法便顯示出其優(yōu)勢，其估計(jì)誤差處于較為穩(wěn)定狀態(tài)，此時(shí)估計(jì)精度高于LR算法。而結(jié)合LR和VEBP二種算法的VEBP-LR算法則最為穩(wěn)定，其估計(jì)誤差隨著采樣周期的增加均處于最佳估計(jì)精度附近，有時(shí)甚至優(yōu)于其它二種算法。

圖4 RMSE與不同采樣間隔關(guān)系

5 結(jié) 論

由于WSNs數(shù)據(jù)缺失的不可避免性，如何進(jìn)行數(shù)據(jù)恢復(fù)是WSNs研究重要方向。針對(duì)不同變化規(guī)律的感知數(shù)值，本文首先介紹了基于時(shí)間相關(guān)性的線性回歸缺失數(shù)值估計(jì)方法，對(duì)于短時(shí)采樣間隔且穩(wěn)定變化數(shù)據(jù)段具有良好的估計(jì)性能。其次，提出一種基于BP神經(jīng)網(wǎng)絡(luò)的缺失數(shù)值估計(jì)算法，基于不同參數(shù)間相關(guān)性特征進(jìn)行缺失數(shù)值估計(jì)。最后，為了提高算法穩(wěn)定性和自適應(yīng)性，對(duì)二種算法進(jìn)行加權(quán)平均，得到穩(wěn)定估計(jì)值。由于本文提出的算法僅僅依賴于節(jié)點(diǎn)自身參數(shù)集，因此,對(duì)WSNs拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)覆蓋率適應(yīng)性較強(qiáng)。實(shí)驗(yàn)仿真表明:對(duì)于不同的采樣間隔，算法均具有較高的估計(jì)性能。

參考文獻(xiàn):

[1] Akyildiz L F,Su W,Sankarasubramaniam Y,et al.A survey on sensor networks[J].IEEE Communication Magazine,2002,40(8):102-114.

[2] Yick J,Mukherjee B,Ghosal D.Wireless sensor networks sur-vey[J].Computer Networks,2008,52(12):2292-2330.

[3] 李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報(bào),2003,14(10):1717-1727.

[4] KulkarniI R V,Forster A,Venayagamoorthy G K.Computational intelligence in wireless sensor networks:A survey[J].IEEE Communications Survey & Tutorials,2011,13(1):68-96.

[5] Zhang Xin,Wicker S B.How to distribute sensors in a random field[C]∥Proc of the 3rd International Symposium on Information Processing in Sensor Networks,New York:ACM,2004.

[6] Li Y,Ai C,Deshmukh W P,et al.Data estimation in sensor networks using physical and statistical methodologies[C]∥Proc of the 28th IEEE Int’l Conf on Distributed Computing Systems,Washington:IEEE Computer Society,2008:538-545.

[7] 潘立強(qiáng),李建中.傳感器網(wǎng)絡(luò)中一種基于多元回歸模型的缺失值估計(jì)算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(12):2101-2109.

[8] 潘立強(qiáng),李建中,駱吉洲.傳感器網(wǎng)絡(luò)中一種基于時(shí)—空相關(guān)性的缺失值估計(jì)算法[J].計(jì)算機(jī)學(xué)報(bào),2010,31(1):1-10.

[9] Halat Chev M,Gruen Wald L.Estimating missing values in related sensor data streams[C]∥Proc of the 11th Int’l Conf on Management of Data,Vadodara,Mumbai:Allied Publishers,2005:83-94.

[10] Jiang N,Gruen Wald L.Estimating missing data in data stream-s[C]∥Proc of the 12th Int’l Conf on Database Systems for Advanced Applications,Berlin:Springer,2007:981-987.

[11] Hornik K M,Stinchcombe M,White H.Multilayer feed-forward networks are universal approximators[J].Neural Networks,1989,2(2):359-366.

[12] 王德明,王 莉,張廣明.基于遺傳BP神經(jīng)網(wǎng)絡(luò)的短期風(fēng)速預(yù)測模型[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,2012,46(5):837-841.