無線傳感網(wǎng)絡中基于誤差橢圓的自適應節(jié)點選擇目標跟蹤算法*

2017-11-03 12:32:42安康寧范馨月高建軍

傳感技術學報 2017年10期

周非,安康寧,范馨月,高建軍

(重慶郵電大學光通信與網(wǎng)絡重點實驗室,重慶 400065)

項目來源:國家自然科學基金項目(61471077)

2017-04-26修改日期2017-06-12

無線傳感網(wǎng)絡中基于誤差橢圓的自適應節(jié)點選擇目標跟蹤算法*

周非*,安康寧,范馨月,高建軍

(重慶郵電大學光通信與網(wǎng)絡重點實驗室,重慶 400065)

追蹤精度與傳感器節(jié)點能耗是無線傳感網(wǎng)絡WSN(Wireless Sensor Network)中主要考慮的兩個性能指標,現(xiàn)有的許多目標追蹤算法在提高追蹤精度、降低傳感器節(jié)點能耗的同時缺乏對傳感器節(jié)點位置與數(shù)目的考慮。因此,提出一種基于誤差橢圓的自適應節(jié)點選擇目標追蹤算法,以誤差橢圓為基準計算目標最可能出現(xiàn)的區(qū)域,然后根據(jù)誤差判決調整區(qū)域內所需激活的傳感器節(jié)點數(shù)量,完成對目標的跟蹤。仿真結果表明,該算法可以在保證追蹤精度的同時有效降低激活傳感器節(jié)點數(shù)量。

無線傳感網(wǎng)絡;目標追蹤;誤差橢圓;誤差指示器;擴展卡爾曼濾波

無線傳感網(wǎng)絡是一種新型的信息獲取及處理平臺,由部署在監(jiān)測區(qū)域內的大量傳感器節(jié)點組成,傳感器節(jié)點之間可以通過無線通信組成一個多跳的自組織網(wǎng)絡系統(tǒng)[1-2]。基于無線傳感網(wǎng)絡的目標跟蹤[3]系統(tǒng)具有部署方便、成本低且跟蹤精度高等優(yōu)點,但傳感器節(jié)點能量有限且電池更換困難,因此選取最優(yōu)傳感器節(jié)點參與觀測能有效延長無線傳感網(wǎng)絡系統(tǒng)的使用壽命。

文獻[4]提出了一種基于預測機制的低功耗目標追蹤算法,以角度為觀測量對目標狀態(tài)進行預測,最后利用最小二乘估計(Least Square Estimation)完成對目標的追蹤,但其算法十分簡單,并未考慮其他約束,在現(xiàn)實生活中難以應用。Wang等人[5]考慮乘性噪聲(Multiplicative Noise)對觀測量的影響,以極大似然估計(Maximum Likelihood Estimation)與牛頓-拉夫遜迭代方法(Newton-Raphson Iterative Method)完成對觀測量的預處理,最后進行卡爾曼濾波(Kalman Filter)完成目標追蹤。但其算法復雜度較高,計算量較大。Li 等人在文獻[6]中提出一種基于自適應強跟蹤粒子濾波(Particle Filter)的目標追蹤算法,通過每一時刻真實觀測值與預測觀測值之間的冗余使遺忘因子與軟化因子達到自適應的狀態(tài)。該算法的缺點是樣本數(shù)量較多,計算量較大。Cheng等人在文獻[7]中對移動節(jié)點的感知質量與網(wǎng)絡覆蓋率進行了分析,在擴展卡爾曼(Extended Kalman Filter)的基礎上提出基于梯度的節(jié)點運動控制策略。文獻[8]提出一種自適應節(jié)點選擇擴展卡爾曼濾波算法,以DMR(Delta Measurement Residual)、目標節(jié)點移動速度以及追蹤時間為參考調整每一次所需觀測量的數(shù)目。文獻[9]中,未避免對系統(tǒng)噪聲等先驗信息的依賴,作者提出一種基于粒子群有計劃地最小剩余定位算法,進而采用數(shù)據(jù)擬合將非迭代算法轉換為迭代算法,完成對目標的追蹤定位。Feng等人在文獻[10]中提出一種分布式無線傳感網(wǎng)絡的自適應節(jié)點選擇方法,根據(jù)不同傳感器節(jié)點的空間相關性,利用聯(lián)合距離加權觀測量來估計觀測節(jié)點的信息效用,最后根據(jù)粒子濾波完成對目標節(jié)點的追蹤。其算法復雜度較高,計算量較大。文獻[11]針對傳統(tǒng)容積卡爾曼濾波算法計算量大,求解空間維度高的缺點,將無線傳感網(wǎng)絡對移動機器人的觀測量/機器人自身對環(huán)境特征的觀測量以及機器人自身運動控制量進行數(shù)據(jù)融合,并利用相關門限閾閥值對數(shù)據(jù)進行處理,完成對機器人的定位。

本文內容安排如下:第1部分針對目標追蹤系統(tǒng)模型進行描述,并闡述了目前目標追蹤算法存在的問題;第2部分針對現(xiàn)有目標追蹤算法的不足,提出改進方法;第3部分對本文提出的改進算法進行仿真分析;最后,對本文進行總結。

1 系統(tǒng)模型及問題描述

本文只考慮單個目標節(jié)點在二維無線傳感網(wǎng)絡中的追蹤問題,假設在無線傳感網(wǎng)中分布N個靜態(tài)傳感器節(jié)點和一個匯聚節(jié)點。匯聚節(jié)點控制靜態(tài)傳感器節(jié)點的狀態(tài),并且進行相關數(shù)據(jù)的分析與處理。

1.1 目標運動模型

目標節(jié)點在二維平面內以恒定速度(constant velocity)運動,選取目標節(jié)點的狀態(tài)變量[12]如式(1)所示:

(1)

xk+1=Fxk+Bwwk

(2)

T為采樣間隔,F及Bw為動態(tài)轉移矩陣:

(3)

wk為動態(tài)加速度噪聲,服從零均值正態(tài)分布,其協(xié)方差為:

(4)

1.2 觀測模型

(5)

(xi,yi)為傳感器節(jié)點i在無線傳感網(wǎng)中的位置,(xt(k),yt(k))為目標節(jié)點k時刻的位置。則目標節(jié)點的觀測模型[13]為:

(6)

1.3 問題描述

無線傳感網(wǎng)絡中目標追蹤所面臨的主要問題有:①傳統(tǒng)方法中,傳感器節(jié)點持續(xù)保持觀測狀態(tài),造成節(jié)點能耗較大,縮短了無線傳感網(wǎng)絡生命周期;②未對傳感器節(jié)點的激活數(shù)量做具體分析,造成大量節(jié)點冗余;③選擇傳感器節(jié)點激活之前,缺乏對其位置的考慮;④大量的觀測量涌入?yún)R聚節(jié)點,造成數(shù)據(jù)擁堵。

2 問題解決方法

本節(jié)首先利用擴展卡爾曼濾波對目標節(jié)點的狀態(tài)進行預測,根據(jù)其預測狀態(tài)的不穩(wěn)定性構建誤差橢圓,即為預測目標節(jié)點最可能出現(xiàn)的區(qū)域,規(guī)劃候選節(jié)點;然后依據(jù)誤差指示器,調整所需激活傳感器節(jié)點數(shù)目,完成目標追蹤。

2.1 誤差橢圓

借助上述的目標運動模型和觀測模型,應用擴展卡爾曼濾波[14-15]對目標的狀態(tài)進行預測。如式(7)所示:

(7)

因為目標節(jié)點受到加速度噪聲的影響,所以擴展卡爾曼濾波對目標節(jié)點狀態(tài)的預測存在一定誤差,因此確定目標節(jié)點預測狀態(tài)的不確定性可以保證節(jié)點對目標節(jié)點持續(xù)進行觀測。文獻[16]中,Zhou以預測協(xié)方差構建3σ橢圓,對目標預測狀態(tài)的不確定性進行描述。

擴展卡爾曼濾波對目標節(jié)點進行預測后,即可得到目標節(jié)點的預測位置以及預測協(xié)方差,此時可以根據(jù)預測位置以及預測協(xié)方差確定目標節(jié)點的可能區(qū)域[17]PR(probable region),目標出現(xiàn)在可能區(qū)域的概率如式(8)所示:

(8)

(9)

當PR所描述的區(qū)域為橢圓時,描述方程如式(10)所示[18]:

(10)

進一步展開為:

(11)

c是一個常量,與目標節(jié)點出現(xiàn)在橢圓內的概率Pe有關,ρ為相關系數(shù)。式即為誤差橢圓(Error ellipse)[19],則目標節(jié)點出現(xiàn)在誤差橢圓的概率如式(12)所示:

(12)

式中:Γ(·)為伽瑪函數(shù)。因為p=2,所以式(12)結果如式(13)所示:

Pe=1-exp(-c2/2)

(13)

同時可得,c的表達式為:

(14)

此時的誤差橢圓是一個傾斜橢圓,其長軸與短軸不能直接獲取,因此需要對誤差橢圓進行旋轉,使其成為標準橢圓。順時針旋轉角度如式(15)所示:

(15)

因為旋轉后的橢圓與未經(jīng)旋轉的橢圓形狀相同,因此可通過旋轉后的誤差橢圓,求得其長軸與短軸。其長軸為:

(16)

短軸為:

(17)

由式(16)和(17)可得,誤差橢圓的主半軸與c呈正相關,其大小可以根據(jù)c進行調節(jié)。c隨著Pe的變化而改變誤差橢圓的大小。

誤差橢圓體現(xiàn)了擴展卡爾曼對目標節(jié)點位置預測的不確定性,目標節(jié)點會以較高的概率出現(xiàn)在誤差橢圓內。因此誤差橢圓內的傳感器節(jié)點會以更高的概率觀測到目標節(jié)點。綜上以誤差橢圓為界限,設誤差橢圓內的傳感器節(jié)點為候選節(jié)點,完成對節(jié)點位置的規(guī)劃。每次對目標節(jié)點進行觀測時,僅對候選節(jié)點進行選擇性激活,而誤差橢圓外的傳感器節(jié)點保持休眠狀態(tài)。同時在確定Pe后,誤差橢圓的大小與所在位置會隨著目標節(jié)點狀態(tài)而改變,所圈定的候選節(jié)點也隨之改變,這一過程由匯聚節(jié)點進行處理。

2.2 誤差指示器

由于誤差橢圓內的候選節(jié)點數(shù)目較多,激活所有候選節(jié)點進行觀測會造成不必要的能量浪費,同時,受噪聲干擾目標節(jié)點在不同時刻所表現(xiàn)出的非線性程度不同,如果目標節(jié)點本時刻運動近似線性運動時,僅需很少的觀測量即可完成對目標節(jié)點狀態(tài)的修正;如果目標節(jié)點本時刻運動非線性程度較高,則需要更多的傳感器節(jié)點對目標節(jié)點進行觀測,修正目標節(jié)點狀態(tài)。因此,需要根據(jù)目標節(jié)點不同時刻所需觀測量的不同,靈活的調整激活候選節(jié)點的數(shù)目能有效節(jié)省傳感器節(jié)點的能量,延長無線傳感網(wǎng)絡的生命周期。

誤差指示器(Error indicator)根據(jù)目標真實位置與預測位置之間誤差的大小增加或減少激活節(jié)點的數(shù)目。但是位置誤差往往不能直接獲取,需要通過與位置誤差相關的變量進行指示。常用的誤差指示器[8]有協(xié)方差矩陣指示器PI(covariancematrix P Indicator),幾何精度因子GDOP(Geometric Dilution Of Precision),平均測量殘差MR(average Measurement Residual),預測與校正之間距離DPC(Distance between Prediction and Correction)。

本文所用誤差指示器為平均測量殘差MR(average Measurement Residual)。MR與位置誤差的斯皮爾曼等級相關系數(shù)更大,接近強相關性,且MR容易獲取。MR具體表達式如式(18)所示:

(18)

SNk為當前時刻所需激活候選節(jié)點的數(shù)目,Hi為觀測矩陣。

為避免激活傳感器節(jié)點數(shù)目劇增或者驟減,定義誤差指示器在k時刻的決策公式如式(19)所示:

(19)

式中:DVk=|MRk-MRk-1|,Φu為上閾值,Φl為下閾值。

如果DVk僅簡單設定為MRk,則有可能因測量噪聲的影響使MRk一直保持較高的值,致使需要激活的傳感器節(jié)點數(shù)目持續(xù)增加,造成傳感器節(jié)點能量的浪費。如果DVk設定為|MRk-MRk-1|,則可以減少測量噪聲對DVk的影響,需要激活的傳感器節(jié)點數(shù)目增減也更加平穩(wěn)。

當DVk達到預設上限值Φu時,即目標估計位置與目標真實位置之間差距過大,需要激活更多的傳感器節(jié)點對目標進行觀測,此時在上一時刻選擇激活候選節(jié)點數(shù)目的基礎上加1。當DVk達到下限值Φl時,即目標估計位置與真實位置之間誤差很小,為節(jié)省傳感器節(jié)點能量,在上一時刻選擇激活候選節(jié)點數(shù)目的基礎上減1。

當激活候選節(jié)點數(shù)目確定后,激活相應數(shù)目的候選節(jié)點,根據(jù)所激活候選節(jié)點提供的觀測量即可進行擴展卡爾曼濾波的修正階段,完成對目標節(jié)點預測狀態(tài)的更新。如公式所示:

(20)

本文所提出的改進算法流程如下:

輸入:x0|0P0|0SN0

輸出:xk|k

1.Fork=1 tondo;

3.構建誤差橢圓,規(guī)劃候選節(jié)點

4.If DVk>Φuthen

5.SNk=SNk-1+1

6.Else if DVk<Φlthen

7.SNk=SNk-1-1

8.Else

9.SNk=SNk-1

10.End if

12.End for

首先根據(jù)擴展卡爾曼濾波對目標節(jié)點進行狀態(tài)預測,通過式(11)與式(13)確定誤差橢圓的大小;以誤差橢圓為界限,挑選出候選節(jié)點;然后根據(jù)式(19)確定本時刻所需激活節(jié)點的數(shù)目,最后激活候選節(jié)點,完成卡爾曼濾波的修正過程。

3 仿真分析

3.1 追蹤精度分析

本節(jié)主要分析誤差指示器對追蹤精度的影響。在有無誤差指示器判決的情況下,分別進行仿真分析,初始激活節(jié)點數(shù)目分別設置為1,2,3,4,5,Φu=1.5,Φl=0.5,即DV上限為步長的30%,下限為步長的10%。跟蹤精度設為累計均方誤差:

(21)

圖1為本文所提出的算法,無誤差指示器判決的算法以及基于最小二乘[20]的目標追蹤3種算法的累計誤差對比。前兩者都是基于誤差橢圓的目標追蹤算法。其中k=15,M=100。從圖中可看出隨著激活節(jié)點的增加,誤差逐漸降低。但存在誤差指示器判決的時候目標追蹤累計均方誤差基本保持不變,因為誤差指示器能夠及時的調節(jié)激活節(jié)點的數(shù)目,無論初始激活節(jié)點數(shù)目為多少,都可以在追蹤過程中對激活節(jié)點數(shù)目進行修正,既可以滿足精度的需要,又能減少激活節(jié)點數(shù)目,節(jié)省傳感器能量。基于最小二乘的目標追蹤算法在激活節(jié)點數(shù)目較少時,因觀測量較少累計誤差較大,當激活節(jié)點數(shù)目為4時,達到其算法理論最優(yōu)值,與本文所提出的基于誤差橢圓但無誤差指示器的追蹤算法精度基本一致。

圖1 累計誤差分析

圖2是初始激活節(jié)點為1,k=15的目標追蹤誤差對比圖。根據(jù)圖2分析可得:當無誤差指示器判決時,目標追蹤算法累計均方誤差為23.8,整個過程中的激活節(jié)點數(shù)目始終為1;當存在誤差指示器判決時,目標追蹤算法累計均方誤差為12.9,整個過程中平均激活節(jié)點數(shù)目為1.8個。雖然存在誤差判決機制的情況下平均激活節(jié)點數(shù)目較無誤差判決多0.8個,但是精度提升了45%。而且可以從圖1中看出,存在誤差判決的情況下,累計均方誤差基本維持在12.5左右;而無誤差判決的情況下,累計均方誤差最小為13.9。表明本文所提出改進算法的有效性。

圖2 X軸、Y軸誤差分析

3.2 激活節(jié)點數(shù)目分析

本節(jié)主要分析誤差指示器的閾值與激活節(jié)點數(shù)目的關系。圖3為在Φu為1.5,Φl,為0.5,初始節(jié)點分別為1,2,3,4,5的條件下對目標追蹤進行帶有誤差值時判決的仿真。

從圖3中可以得出,雖然初始激活候選節(jié)點數(shù)目不同,但是隨著仿真的進行,激活候選節(jié)點數(shù)目變化趨于一致。平均激活節(jié)點數(shù)目分別為1.8,1.9,1.7,2.4,3.2.,后兩項平均激活候選節(jié)點數(shù)目較大是因為初始激活節(jié)點數(shù)較大,且k較小,如果k足夠大,平均節(jié)點激活數(shù)應接近一致。

圖3 激活節(jié)點數(shù)目變化

圖4與圖5針對Φu與Φl進行分析,取k等于15,初始激活節(jié)點數(shù)目為1。圖4中Φi固定為0.5。隨著Φu的增大,誤差指示器靈敏度越來越低,對DV值的變化越來越不敏感,造成激活節(jié)點數(shù)量改變的遲緩,累計誤差增大。圖5中Φu固定為1.5。隨著Φl的減少,同樣會造成誤差指示器靈敏度降低。當Φl為步長的1%時,激活節(jié)點數(shù)目幾乎不會減少,因為此時要求DV值小于0.05,這在觀測噪聲的干擾下很難實現(xiàn)。

圖4 DV上限分析

圖5 DV下限分析

因此,靈活的選取的Φu與Φl才能使誤差指示器起到更好的指示作用,及時增加或減少激活節(jié)點的數(shù)目,節(jié)省節(jié)點的能量,進而延長無線傳感網(wǎng)絡的生命周期。

4 結論

本文提出一種基于誤差橢圓與誤差指示器判決的改進目標追蹤算法。通過EKF構建誤差橢圓,以誤差橢圓圈定候選節(jié)點,然后根據(jù)誤差指示器對激活節(jié)點數(shù)目進行調節(jié)。本文提出的改進算法仍有不足之處:沒有針對候選節(jié)點對追蹤貢獻度進行考慮,只是隨機選取節(jié)點數(shù)目;同時并沒有考慮到在稀疏無線傳感網(wǎng)絡中,誤差橢圓內不存在候選節(jié)點的情況。今后將針對上述幾個缺陷進行改進。

[1] Yick J,Mukherjee B,Ghosal D. Wireless Sensor Network Survey[J]. Computer Networks the International Journal of Computer and Telecommunications Networking,2008,52(12):2292-2330.

[2] Han G,Xu H,Duong T Q,et al. Localization Algorithms of Wireless Sensor Networks:A Survey[J]. Telecommunication Systems,2013,52(4):1-18.

[3] Patwari N,Ash J N,Kyperountas S,et al. Locating the Nodes[J]. IEEE Signal Processing Magazine,2005,22(4):54-69.

[4] Mirsadeghi M. Mahani a Low Power Prediction Mechanism for WSN-Based Object Tracking[J]. Procedia Technology,2014,17:692-698.

[5] Wang X,Fu M,Zhang H. Target Tracking in Wireless Sensor Networks Based on the Combination of KF and MLE Using Distance Measurements[J]. IEEE Transactions on Mobile Computing,2012,11(4):567-576.

[6] Li J,Zhao R,Chen J,et al. Target Tracking Algorithm Based on Adaptive Strong Tracking Particle Filter[J]. IET Science Measurement and Technology,2016,10(7):704-710.

[7] Cheng P,Cao X,Bai J,et al. On Optimizing Sensing Quality with Guaranteed Coverage in Autonomous Mobile Sensor Networks[J]. Computer Communications,2012,35(9):1107-1114.

[8] Robles J J,Cardenas-Mansilla G,Lehnert R. Adaptive Selection of Anchors in the Extended Kalman Filter Tracking Algorithm[C]//2014 Positioning,Navigation and Communication(WPNC). IEEE Press,2014:1-7.

[9] Xu N,Zhang Y,Zhang D,et al. Moving Target Tracking in Three Dimensional Space with Wireless Sensor Network[J]. Wireless Personal Communications,2016(2016):1-11.

[10] Feng J,Zhao H,Lian B. Efficient and Adaptive Node Selection for Target Tracking in Wireless Sensor Network[J]. Journal of Sensors,2016(2016):1-9.

[11] 陳曉飛,凌有鑄,陳孟元. WSNs環(huán)境下基于高斯混合容積卡爾曼濾波的移動機器人定位算法[J]. 傳感技術學報,2017,30(1):133-138.

[12] Li X R,Jilkov V P. Survey of Maneuvering Target Tracking. Part I. Dynamic Models[J]. IEEE Transactions on Aerospace and Electronic Systems,2003,39(4):1333-1364.

[13] Li X R,Jilkov V P. A Survey of Maneuvering Target Tracking-Part Ⅲ:Measurement Models[J]. Proceedings of SPIE—The International Society for Optical Engineering,2001,4473(4):423-446.

[14] Faragher R. Understanding the Basis of the Kalman Filter Via a Simple and Intuitive Derivation[Lecture Notes][J]. IEEE Signal Processing Magazine,2012,29(5):128-132.

[15] Welch G,Bishop G. An Introduction to the Kalmanfilter[J]. University of North Carolina at Chapel Hill,2006,8(7):127-132.

[16] Zhou K,Roumeliotis S I. Optimal Motion Strategies for Range-Only Constrained Multisensor Target Tracking[J]. IEEE Transactions on Robotics,2008,24(5):1168-1185.

[17] Chan Y T,Chan F,Read W,et al. Probable Regions for Emitter Localization[C]//IEEE Military Communications Conference,Milcom. IEEE,2015:222-227.

[18] Qi Y,Cheng P,Bai J,et al. Energy-Efficient Target Tracking by Mobile Sensors with Limited Sensing Range[J]. IEEE Transactions on Industrial Electronics,2016,63(11):6949-6961.

[19] Paradowski L R. Uncertainty Ellipses and their Application to Interval Estimation of Emitter Position[J]. IEEE Transactions on Aerospace and Electronic Systems,1997,33(1):126-133.

[20] Mauro C,Pierfrancesco L,Matteo S. A Weighted Least Squares Approach for Multi-Target Doppler-Only Localization[C]//2013 IEEE Radar Conference(RADAR). IEEE Press,2013:1-6.

TargetTrackinginWirelessSensorNetworkBasedonErrorEllipseandAdaptiveSelectionofNodes*

ZHOUFei*,ANKangning,FANXinyue,GAOJianjun

(Chongqing Key Laboratory of Optical Communication and Networks,Chongqing University of Posts and Telecommunications,Chongqing 40065,China)

In the Wireless Sensor Network,tracking accuracy and energy consumption of nodes are two main performance indicators.Although many target tracking algorithms improved the tracking accuracy and reduced the energy consumption of the sensor nodes,few of them considered the distribution number and position of sensor nodes.Therefore,a target tracking algorithm based on error ellipse and adaptive selection of nodes is proposed. Firstly,proposed algorithm calculates the most possible region for target based on error ellipse. Then determines the number of sensor nodes by using the error indicator.Finally,activating the sensor nodes to complete the target tracking. The simulations demonstrate that proposed algorithm can effectively reduce the number of activated sensor nodes in the premise high tracking accuracy.

wireless sensor network;target tracking;error ellipse;error indicator;extended Kalman filter

TP393

1004-1699(2017)10-1548-06

10.3969/j.issn.1004-1699.2017.10.016