一種基于預測策略的目標跟蹤算法研究*

任 靜，熊慶宇，石為人

(重慶大學自動化學院，重慶 400030)

無線傳感器網絡由于節點體積小、能耗低、隱蔽性好等優點［1］，非常適合用于移動目標的跟蹤［2］。但是由于其節點能量有限，要求在保證跟蹤精度的同時還要考慮其它因素，例如網絡生存時間［3］、能量消耗等。傳感器節點的計算能力和存儲能力有限要求我們在設計算法時要平衡網絡生存時間和能量有限，高精度和低計算能力［4］之間的關系。基于測距的定位算法［5］可以得到較精確的目標位置，它是根據一些屬性模型得到節點和目標之間的距離，這些往往不是它們之間的真實距離，容易造成積累誤差。

目前用于目標跟蹤的預測方法主要有粒子群濾波、卡爾曼濾波［6］等，這些方法的共同特點就是需要大量的數據迭代計算，適合于集中式系統，不適合在資源有限的傳感器節點上進行。在某一時刻移動節點不可能全部被節點感知到，而且距離移動目標近的節點感知信號強度［7］要比距離移動目標遠的節點的感知強度大，本文提出了一種基于預測策略的目標跟蹤算法。該算法采用靜態網格網絡結構，當目標進入監控區域后，節點攜帶的震動傳感器感知到目標，簇頭節點根據節點檢測目標信號強度值來計算目標位置，目標位置計算采用一種基于檢測信號強度的加權質心定位算法;簇頭節點根據目標移動的已知信息來預測移動目標未來的位置，利用分段線性擬合的思想，將整個網絡的軌跡預測分為簇內預測以及相鄰簇間的預測，降低了目標預測的計算時間復雜度;當跟蹤簇頭節點發現目標丟失，根據傳感網絡結構提出了目標恢復機制。

1 目標跟蹤算法

1.1 算法思想

本文論述的無線傳感器網絡系統是采用靜態分簇網絡結構。整個監控區域被劃分成不同的虛擬單元格，每個節點根據自身地理位置信息被劃分到不同的單元格。監控區域的節點被分成邊界簇頭節點、簇頭節點和簇內節點，每個節點都有三種狀態即跟蹤狀態、偵測狀態和睡眠狀態。每個傳感器節點攜帶振動傳感器，當移動目標進入到監控區域時，節點便可監測到信號能量強度。

目標跟蹤流程圖如圖1所示。

圖1 目標跟蹤流程圖

算法的具體實現步驟:

步驟1網絡初始化 整個監控區域被劃分成不同的虛擬單元格，每個單元格稱為一簇。在沒有跟蹤任務時，監控區域只有邊界簇頭節點處于偵測狀態，其余節點則處于睡眠狀態，每個邊界簇每隔一段時間更新一次簇頭節點。

步驟2目標跟蹤 當邊界簇頭節點偵測到未知目標出現時，激活其簇內節點對目標進行定位計算，邊界簇頭節點根據其簇內節點發回的信息計算未知目標的位置信息和路徑，從而預測目標下一時刻的位置并喚醒附近節點繼續跟蹤。

步驟3下一時刻節點的喚醒 當未知目標運動區域超出一簇監控范圍時，簇頭節點計算目標下一時刻的位置信息并通知相應簇頭節點啟動跟蹤，休眠當前簇頭節點及監測信號強度值低的節點。

步驟4 目標恢復 如果目標意外丟失，則啟動相應的恢復喚醒機制。

1.2 目標定位

目標信號的強度是隨著傳輸距離的增加而呈指數衰減的［8］，當目標進入監控區域后，節點i在t時刻的采樣信號強度值ei(t)可用式(1)所示:

式中:s是目標信號源的強度;α是信號強度的衰減指數(α約等于2);di(t)是t時刻節點i與跟蹤目標之間的距離;ni～N(0，σ2)是測量噪聲，可近似為高斯白噪聲。由式(1)可知，當目標經過節點i時，一般是一個由遠到近再到遠的過程，同一節點在不同時刻監測到的信號強度值也是不相同的。同理，在同一時刻不同節點所監測到的信號強度值也是不相同的。當檢測強度值大于某一閾值時，便可參與到定位計算中。

信號峰值意味著此時目標位于距離節點i最近，i所對應的信號強度值ei(t)也為最大。據此，本文提出了基于檢測信號強度值的目標位置定位算法，基本思想是:跟蹤節點檢測到目標強度值相互之間的比值之和作為加權質心定位算法的加權值。具體表述為:設目標在t時刻的位置為L(xt，yt)，此時監控區域有n個參考節點(n≥3)，這些節點的坐標分別為{(x1，y1)，(x2，y2)…(xn，yn)}，t時刻這些節點檢測到的目標信號強度分別為e1(t)，e2(t)…en(t)。根據檢測到的目標信號強度對跟蹤節點進行從大到小排序，并選取前k個(3≤k≤6)跟蹤節點建立參考節點集合，G={(x1，y1)，(x2，y2)…(xk，yk)}。它們彼此互相獨立，各個跟蹤節點的加權因子分別為w1，w2…wk，則加權質心定位計算得到的跟蹤目標在t時刻的位置L(xt，yt)為:

定義Bij為t時刻，跟蹤節點i，j分別檢測到的目標信號強度值的比值，即:

定義權值為:

根據權值信息，代入到式(2)中即可得到跟蹤目標在t時刻的位置。

1.3 目標位置預測

目前用于目標跟蹤的預測方法主要有粒子群濾波、卡爾曼濾波等［9－10］，這些方法的共同特點就是需要大量的數據迭代計算，對節點的處理模塊要求比較高，不適合應用在資源有限的傳感器節點上。本文利用分段線性擬合［11］思想，把目標在監控區域的運動分為在若干個簇內的運動，假設目標在一簇內做直線運動，設目標進入當前簇的起始位置為L(xk，yk)，下一時刻的感知位置坐標為(xk+1，yk+1)，采樣間隔時間為Δt，則在初始感知目標的速度vk和加速度ak如式(5)、式(6)所示:

目標的運動速度和方向決定了目標在當前簇內的停留時間和移動距離，設目標在當簇內感知到m個位 置 信 息 為 (xk，yk)，(xk+1，yk+1) … (xk+m－1，yk+m－1)，利用目標的這些位置信息可以構建目標做直線運動的直線方程y=ax+b，由最小二乘法求直線方程的參數a和b的值。設當前目標跟蹤簇的簇頭節點為坐標原點，當前監控區域邊界曲線方程如式(7)所示:

tstqv是移動目標在當前簇的停留時間，如式(9):

根據以上預測數據，當前跟蹤簇的簇頭節點在一定的時間內喚醒邊界節點進行目標跟蹤。如果移動目標的運動范圍超出了當前簇的監控范圍，則目標在當前簇的最終位置作為相鄰簇的初始位置，喚醒預測鄰居簇頭節點啟動跟蹤任務。

1.4 目標恢復機制

由于目標的運動速度、方向存在一定程度的誤差并且在預測時間內，目標的一些運動特性會突然發生較大的改變，致使目標離開當前的監控區域，這種現象稱作是目標丟失，為了能夠快速的重新跟蹤目標，我們提出了一種有效的目標恢復喚醒算法。

目標丟失檢測 被喚醒的節點檢測到目標時會向前一監控節點發送確認消息，否則在一周期內沒有發現目標則自動進入睡眠狀態，如果前一監控節點在規定時間內沒有收到喚醒節點發送的確認消息，則表明目標丟失，啟動目標恢復機制。

目標恢復 目標恢復分為兩個過程，首先當前跟蹤簇頭節點洪泛命令，喚醒其簇內所有節點搜索其監測范圍內的所有目標信息，所有當前簇內節點在一個周期內上傳其檢測信息，若當前簇頭節點監測到移動目標，則休眠不相關節點繼續進行跟蹤;若沒有發現目標說明移動目標已經離開當前簇，當前簇頭節點休眠其簇內節點并且洪泛消息到一跳范圍的相鄰的簇頭節點，相鄰簇頭節點再啟動搜索任務。

2 算法仿真分析

為了驗證本文算法的有效性以及在定位精度和目標丟失率方面的優勢，利用MATLAB軟件對本文算法進行仿真實驗。仿真場景的基本設置為:400個節點隨機分布在100 m×100 m的二維監控平臺，節點的傳輸半徑R=30 m，從文獻［12］可以知道簇的半徑與傳感器節點傳輸半徑之間的關系，如式(10)所示，可以計算出當前監控區域半徑r的范圍。

各個節點根據其地理位置信息被劃入分成半徑為8 m的監控區域。目標信號源強度s=100，衰減指數 α=2，噪聲分布ni～N(0，σ2)，檢測閾值e0=1，目標做直線運動，其中v=10 m/s，a=±cos(t)m/s2。仿真分別對本文算法、基于預測策略的能量高效目標跟蹤算法(PES)［13］和基于無線傳感器網絡動態簇的目標跟蹤算法［14］進行了10次仿真，跟蹤性能對比圖如圖2～4所示，圖中的數據為對應參數10次仿真所得結果的平均值。

首先對本文提出的目標定位算法與質心算法，DV-Hop算法進行了對比，分別對其進行五次仿真，每次的仿真定位誤差方差如下表1所示。

表1 本文、質心、DV-Hop定位誤差

分析表1可知，由于受到許多不確定性的干擾，質心算法和DV-Hop算法的定位誤差較大，而本文定位算法精度比較高，這是由于本文算法中的加權值充分利用了各個位置檢測目標信號強度值，使離目標近的節點在目標位置中的權值大，與目標距離遠的節點在目標位置結算中所占的權值小，其結果更接近目標的真實位置。

圖2顯示了本文算法跟蹤目標的結果，并與基于預測策略的能量高效目標跟蹤算法(PES)進行了對比，結果顯示，兩種算法都能夠很好的近似模擬目標實際運動軌跡，特別是當目標做直線運動時，算法基本和目標運動軌跡吻合;但當目標突然改變方向時，PES算法由于只有一個節點跟蹤目標，所以在目標突然改變方向時不能夠很好的做出反應，實時性比較差，而本文算法有多個節點協作跟蹤目標，能比PES以更快的速度做出改變，從而實時跟蹤目標。本文的定位算法能夠很好的計算出移動目標位置，采用基于分段線性擬合預測策略很好的擬合了目標的運動軌跡，擬合度較高。

圖2 曲線軌跡跟蹤結果

圖3所示為目標丟失率隨著速度的增加而變化的曲線，目標丟失率是指在跟蹤過程中，無效的定位次數在本次目標跟蹤中總的定位次數的比值。

圖3 目標丟失率對比圖

從圖3可以看出，當目標運動速度較低時，三種算法都比較穩定，目標丟失率比較低;隨著目標運動速度的增加，尤其是當目標運動速度達到15 m/s時，PES算法由于無法快速喚醒節點導致其目標丟失率顯著增加，動態簇算法和本文算法都能較好的適應速度的變化，目標丟失率變化不大，本文算法由于采用了靜態分簇以及合理的目標恢復機制，當目標丟失時能夠迅速找到目標，從而降低目標丟失率。

圖4所示為分別對PES算法，動態簇算法和本文算法隨速度變化的能耗進行了仿真，由于動態簇算法組簇的能耗比較大，所以雖然目標運動速度較慢，但是能耗依然較大;但隨著速度的增大，PES算法的目標丟失率相應增大，找回目標所需的能耗更大。從圖中可以看出本文算法能耗隨速度的變化比較穩定，這可以說明本算法采用的節點調度機制能夠在不影響跟蹤精度的同時減少能耗。

圖4 能量消耗對比圖

3 結論

目標跟蹤是無線傳感器網絡主要應用之一，同時也是目前傳感器網絡研究的重要課題。本文在提出的網絡結構基礎上，提出了基于加權質心算法的目標位置計算方法，可以在不增加計算量的情況下提高目標跟蹤的精度。針對其他預測方法需要大量的數據迭代計算，改進了分段線性擬合預測方法，算法仿真結果表明該算法可以很好的預測目標的位置，降低目標丟失的概率，另外目標丟失時，還給出了目標意外丟失時的目標恢復機制，從而進一步減低目標丟失率。

［1］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005:8－10.

［2］Guojun Wang，Huan Wang，Jiangnong Cao，et al.Energy-Efficient DualPrediction Based Data Gathering for Environmental MonitoringApplications［C］//IEEE Communication Society subject matter experts for publication in the WCNC 2007 proceedings:3516－3521.

［3］Bhattacharya A，Das S K.Lezi-Update:An Information Theoretic Framework for Personal Mobility Tracking in PCS Networks［J］.ACM/KluWer Journal on Wireless Networks)，March－May 2002，8(2－3):121－135.

［4］Jeongkeun Lee，Kideok Cho，Seungjae Lee.Distributed and Energy-Efficient Target Localization and Tracking in Wireless Sensor Networks［J］.Computer Communications，2006，(29):2494－2505.

［5］任倩倩，李建中，李金寶，等.無線傳感器網絡中一種能源有效的移動對象跟蹤方法［J］.通信學報，2009，30(4):50－59.

［6］Lee W C，Xu Y.On Localized Prediction for Power Efficient Object Tracking in Sensor Networks［C］//Proceedings of the 23rd Inter-national Conference on Distributed Computers Systems Workshops，434－439，2003.

［7］Kawuu W Lin，Ming Hua Hsieh，Vincent S Tseng.A Novel Prediction-Based Strategy for Object Tracking in Sensor Networks by Mining Seamless Temporal Movement Patterns［J］.Expert Systems with Applications，2010，(37):2799－2807.

［8］Wang G，Wang T，Jia W，et al.Local Update-Based Routing Protocol in Wireless Sensor Networks with Mobile Sinks［C］//Proceedings of the 2007 IEEE International Conference on Communications(ICC 2007)，Glasgow，Scotland，UK，June 2007.

［9］曾明，危阜勝，陳冠升，等.面向目標跟蹤的WSN協同調度策略及拓撲控制［J］.華南理工大學學報(自然科學版)，2010，38(6):60－65.

［10］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡DV-Hop定位算法［J］.傳感技術學報，2011，24(1):83－87.

［11］危阜勝，胥布工，高煥麗，等.基于無線傳感器網絡的分布式處理目標跟蹤系統［J］.傳感技術學報，2009，(10).132－137.

［12］潘旭武，楊東勇.一種面向目標跟蹤的無線傳感器網絡拓撲結構［J］.計算機系統應用，2007，(12):37－40.

［13］Winter J，Lee W C，Xu Y，Prediction Based Strategies for Energy-Saving in Object Tracking Sensor Networks，Proc.2004 IEEE International conference on Mobile Data Management，346－57，2004.

［14］鄧克波，劉中.基于無線傳感器網絡動態簇的目標跟蹤［J］.兵工學報，2008，29(10):1197－1202.