基于無線傳感器網絡的同時定位與跟蹤*

趙亞鳳, 任洪娥

(東北林業大學，黑龍江 哈爾濱 150040)

0 引 言

無線傳感器網絡一個很重要的應用就是敵方軍事目標檢測與跟蹤。另外，無線傳感器網絡在民用方面也有很多的應用，如生態環境監測、智能交通控制、基礎設施安全、微創醫療裝置等，都用來跟蹤不同的目標，確定其位置信息。在這些應用中，需要在預定區域隨機散播大量無線傳感器節點組成無線傳感器網絡，實時跟蹤目標位置信息。

移動目標跟蹤時，需要精準的位置信息作為參考。而無線傳感器網絡的定位，由于其通常需要較大規模，能確定精確位置的人工部署不切實際；GPS雖能準確定位，但需要在節點配置相應設備，不符合傳感器網絡的小型化和成本要求。因此，低成本、高精度地準確跟蹤移動目標，同時確定傳感器網絡節點位置是一種最好的解決方法。

目前，為了解決傳感器網絡的定位和移動目標的跟蹤問題，一些文獻提出了相關算法，文獻[1～4]中使用一個移動的目標(或機器人)來定位無線傳感器網絡，因為它們不需要在節點上配置額外的硬件資源，是一個很好的解決方案，但這些方法需要在任何時候都知道運動物體的位置，不符合目標跟蹤的需求。有一些文獻使用傳感器網絡跟蹤移動目標[5]，這些方法假定傳感器網絡節點位置信息是確定的，適用于小規模傳感器網絡，對網絡定位能力提出了較高的要求。本文根據同時定位與構圖(SLAM)的相關理論，研究一種同步定位與跟蹤算法，跟蹤一個不確定的運動物體位置，同時定位和校準傳感器網絡的節點位置信息。

1 同時定位與跟蹤原理

移動目標在一個粗定位的環境地圖中確定自己的位置，同時根據新的測量信息校正地圖,在過去的十多年中，SLAM方法證實了處理這類問題的有效性。利用SLAM的思想，在線估計與更新移動目標的位置并更新傳感器網絡節點位置。

由于接收信號強度指示 (received signal strength indication，RSSI) 的定位技術利用能量的測量可直接計算節點間距離，沒有常用的視覺傳感器的視線障礙，但距離估計的可靠性不高。本文在初始估計時，允許有一定誤差存在，選用RSSI測量確定節點對和節點與目標的相對距離。本文利用多維定標(multidimensional sealing，MDS)的思想，根據經典計量多維技術得到每個節點的一跳鄰居節點相對坐標圖，依次傳播得到網絡的相對坐標圖，即根據節點和節點間的相關性信息來確定未知位置的節點坐標。

本文假設目標可以隨意移動，傳感器節點位置固定，移動目標與節點間能相互通信。首先，利用傳感器網絡節點對之間的距離信息，對傳感器網絡初始定位。但這些定位信息通常包含很大的誤差，不能作為目標跟蹤的絕對參考，需要根據目標在行進過程中與節點的相對距離，實時更新節點位置，同時跟蹤目標。為了實現這一過程，基于Kalman濾波的理論得到廣泛研究，但隨著目標前進，測量信息增加，濾波器狀態方程維數隨之增大，產生很大的計算量，不適合無線傳感器網絡節點的分布式計算。本文利用Kalman濾波的可取特點，使用壓縮Kalman濾波估計與更新減小算法復雜度，實現分布式算法的實時性要求,算法原理如圖1所示。

圖1 同時定位與跟蹤的基本原理

2 算法分析

2.1 利用MDS的傳感器網絡粗定位

在所有節點間實際幾何距離正確的情況下,經典的MDS算法可以給出沒有誤差的解。但是,由于節點的通信范圍限制,幾乎不可能實現所有網絡節點間的精確測距。在實際應用中,只能測量相鄰節點間的距離信息,而對于多跳節點間的距離,本文利用Euclidean算法計算節點間幾何距離[6]。

首先,計算所有節點間的距離,建立MDS所需節點的距離矩陣D(X),再對距離的平方所構成的矩陣D2(X)雙重中心化,然后對雙重中心化后的矩陣進行奇異值分解,最后計算出所有點的相對坐標X，生成相對坐標圖,并利用少量的信標節點和坐標的旋轉、平移將全局相對坐標轉換成絕對坐標。只需知道3對轉換前后的二維坐標，實現最優線性轉換。

2.2 系統動態模型和觀測模型

利用MDS算法，可以獲得網絡中節點的位置信息，第i只傳感器節點的位置描述為pi=(xi,yi)，考慮到所有節點是固定不動的，第i個節點的狀態轉移方程為

pi(k)=pi(k-1)=pi.

假設系統中有效的節點數為N，用向量表示為

移動目標的狀態用xv(k) 給定，構成系統狀態的有移動目標狀態和傳感器節點的位置狀態，稱為擴張的狀態向量,表示為

擴張的狀態轉移模型可完整描述為

X(k)=A(k)X(k-1)+V(k-1),

式中A(k)為狀態矩陣，V(k)用于表示系統動態噪聲。可見，矩陣的維數為n×N，n為與每個節點關聯的狀態量，N為組合成地圖的節點個數。在一個大的環境中，外部傳感器不斷獲得測量數據，構成環境地圖的路標數不斷增加，矩陣維數呈幾何數量增長，給計算機造成很大負擔。

移動目標和傳感器節點同樣配置,利用RSSI技術獲得節點和目標之間的相對定位,第i個節點的觀測模型可寫為

Z(k)=H(k)X(k)+W(k),

式中W(k)用于表示系統測量誤差，該向量為一個零均值，方差為Ri(k)的隨機向量;Hi為觀測的第i個節點相對于系統狀態的觀測矩陣。

2.3 濾波算法分析

Kalman濾波包括2個階段：估計和更新。在估計階段，濾波器利用上一時刻的狀態估計當前狀態，更新階段，濾波器利用在當前狀態的觀測值優化預測階段的預測值，以獲得一個更精確的當前狀態的估計。

在經典SLAM算法中，狀態向量維數為移動目標狀態加節點數的2倍，即M=2N+3，而在實際的目標跟蹤中，只有移動目標周圍一跳內的節點是有意義的，大量節點位置信息并無參考價值[7]。經典算法中隨著節點數目的增加，標準濾波計算量劇增，不適用于實時目標跟蹤。本文提出壓縮濾波來減小實時計算,將復雜度減小到O(2Na2)，Na是局部區域的路標數。

在壓縮EKF濾波中，將狀態分為2個部分

XA∈R2NA+3,XB∈R2NB,N=NA+NB.

狀態XA被定為移動目標周圍一跳內的節點狀態，移動目標的狀態也包括在XA中。假設在一段時間內得到的觀測點只與狀態XA相關，與XB不相關，即

h(x)=h(XA),H=[HA0].

根據2種不同的狀態，誤差協方差矩陣P寫為

考慮時刻k,更新之后的協方差矩陣為

P(k|k)=P(k|k-1)-ΔP,

在目標跟蹤任務中，XA狀態維數將會通常比全局地圖的總維數小很多，即NA?NB?M，矩陣μ(k),ξ(k)為稀疏的,壓縮的濾波算法會使得算法復雜度得到很大程度降低。

3 仿真結果

由于RSSI定位距離超過20 m時有較大誤差，將傳感器最大測量距離定為20 m。在長、寬均為180 m的范圍內，隨機布置的節點個數為80個，設置3個配備GPS的錨節點。利用MDS算法對網絡節點初始定位如圖2所示，節點平均誤差為5 m。本文利用一種簡便的方法劃分全局地圖，將全局地圖分為9個正方形，每個正方形邊長為60 m，選擇邊長為60 m的正方形作為局部區域。

如果移動目標和探測到的節點屬于同一個封閉區域，不會產生較大誤差，但在探測到相鄰區域的節點時，由于前面節點的相關信息丟棄，會使得節點的估計位置誤差變大， 同時改變節點所在的區域的定位誤差。本文在局部區域轉換時設置一個滯后區域來避免多重地圖切換產生的誤差，即地圖之間有一定的重合，將該重合區域設定為20 m，如圖2中虛線所示。圖中圓圈為估計位置,黑圓點為實際位置，黑色方框為錨節點，中間連線表示誤差。

圖2 壓縮濾波算法的地圖處理

在圖2所示的傳感器節點布局中，移動目標從原點開始隨機移動，移動速度為1 m/s，線速度標準差為0.1 m/s，角速度標準差為3.00。設置實驗中的觀測參數，最大觀測距離為20 m；觀測時間間隔為0.2 s；觀測的距離標準差為0.1 m。短距離和長距離的目標跟蹤和傳感器節點定位如圖3和圖4所示。

圖中“*”號描述實際節點位置，“+”號表示估計節點位置，橢圓表示估計誤差，“-”表示估計移動路徑，“·-”表示實際移動路徑，可見在較短距離的目跟蹤任務中，誤差會越來越大。在長距離的跟蹤任務，由于關聯到確定位置的節點，誤差會隨著路徑的增加而減小。

圖3 短距離目標跟蹤

圖4 長距離目標跟蹤

經典EKF濾波算法中，80個參考節點的目標跟蹤，算法復雜度為O(812)。本文中所用壓縮濾波算法計算量為O(Na2)，在離開本地區域時更新的復雜度是O(Na2Nb2)。每個區域內節點個數小于10，區域內算法復雜度最大為O(102)。移動到一個新的區域時，需要做一個全局的更新，但該算法復雜度也遠小于經典EKF。

在經典的目標跟蹤任務中,傳感器節點位置誤差在初始定位后保持不變,本文的算法節點位置誤差隨時間變化比較如圖5所示。

圖5 WSNs節點定位誤差比較

實線為經典MDS定位后的WSNs節點誤差協方差矩陣行列式,虛線為同時定位與跟蹤的節點誤差協方差。可見，在短距離的跟蹤中，節點誤差沒有得到很好的改善，隨著關聯節點的增多，節點誤差隨著跟蹤的進行而減小。

圖6為重復實驗中目標跟蹤誤差取均值的結果。實驗結果表明:多次實驗的平均誤差在0.9～2.6 m間，可見算法有較高的精度和穩定性。

圖6 多次跟蹤平均誤差

4 結 論

本文提出了無線傳感器網絡節點位置不確定時移動目標的跟蹤和節點位置的更新。仿真結果表明:該算法能減小無線傳感器網絡節點的位置誤差，在初始位置節點位置為5 m的情況下，通過估計—更新步驟，將節點平均位置誤差降低到3 m以下。同時，目標跟蹤的誤差最大為2.6 m，并很大幅度減小算法復雜度。尤其是長距離的跟蹤任務中，經典EKF濾波算法復雜度太高而不能滿足實時性的要求，本文用一個局部SLAM算法的代價完成載體位置和局部地圖中的地標位置估計，體現了該算法在長時間執行的優越性。

參考文獻:

[1] Pathirana P,Bulusu N,Ha S J,et al.Node localization using mobile robots in delay-tolerant sensor networks[J].IEEE Transactions on Mobile Computing,2005,4(4):285-296.

[2] Galstyan A,Krishnamaehari B,Lerman K,et al.Distributed online localization in sensor networks using a moving target[C]∥Proc of the Third International Symposium on Information,Wa-shington:IEEE,2004:61-70.

[3] Menegatti,Zanella A,Zilli S,et al.Range-only SLAM with a mobile robot and a wireless sensor networks[C]∥Proceedings of the 2009 IEEE International Conference on Robotics and Automation，Kobe,Japan,2009:1699-1705.

[4] Djugash Joseph,Singh Sanjiv,Kantor George A,et al.Range-only SLAM for robots operating cooperatively with sensor networks[C]∥IEEE International Conference on Robotics and Automation,2006:2078-2084.

[5] 姚先連,胡 貞,呂曉玲.無線傳感器網絡中卡爾曼濾波在移動目標跟蹤中的研究[J].長春理工大學學報:自然科學版，2011，34(3):88-92.

[6] 王 健,趙亞鳳,劉勁風.一種適用于大規模無線傳感器網絡的定位算法[J].東北林業大學學報,2009,37(8):84-89.

[7] Nebot E.Simultaneous localization and mapping 2002 summerschool[EB/OL].[2002—08—05].http：∥acfr.usyd.edu.au /home pages/academic/enebot/.