基于無(wú)線傳感器網(wǎng)絡(luò)的同時(shí)定位與跟蹤*

趙亞鳳, 任洪娥

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

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)一個(gè)很重要的應(yīng)用就是敵方軍事目標(biāo)檢測(cè)與跟蹤。另外，無(wú)線傳感器網(wǎng)絡(luò)在民用方面也有很多的應(yīng)用，如生態(tài)環(huán)境監(jiān)測(cè)、智能交通控制、基礎(chǔ)設(shè)施安全、微創(chuàng)醫(yī)療裝置等，都用來(lái)跟蹤不同的目標(biāo)，確定其位置信息。在這些應(yīng)用中，需要在預(yù)定區(qū)域隨機(jī)散播大量無(wú)線傳感器節(jié)點(diǎn)組成無(wú)線傳感器網(wǎng)絡(luò)，實(shí)時(shí)跟蹤目標(biāo)位置信息。

移動(dòng)目標(biāo)跟蹤時(shí)，需要精準(zhǔn)的位置信息作為參考。而無(wú)線傳感器網(wǎng)絡(luò)的定位，由于其通常需要較大規(guī)模，能確定精確位置的人工部署不切實(shí)際；GPS雖能準(zhǔn)確定位，但需要在節(jié)點(diǎn)配置相應(yīng)設(shè)備，不符合傳感器網(wǎng)絡(luò)的小型化和成本要求。因此，低成本、高精度地準(zhǔn)確跟蹤移動(dòng)目標(biāo)，同時(shí)確定傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置是一種最好的解決方法。

目前，為了解決傳感器網(wǎng)絡(luò)的定位和移動(dòng)目標(biāo)的跟蹤問(wèn)題，一些文獻(xiàn)提出了相關(guān)算法，文獻(xiàn)[1～4]中使用一個(gè)移動(dòng)的目標(biāo)(或機(jī)器人)來(lái)定位無(wú)線傳感器網(wǎng)絡(luò)，因?yàn)樗鼈儾恍枰诠?jié)點(diǎn)上配置額外的硬件資源，是一個(gè)很好的解決方案，但這些方法需要在任何時(shí)候都知道運(yùn)動(dòng)物體的位置，不符合目標(biāo)跟蹤的需求。有一些文獻(xiàn)使用傳感器網(wǎng)絡(luò)跟蹤移動(dòng)目標(biāo)[5]，這些方法假定傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置信息是確定的，適用于小規(guī)模傳感器網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)定位能力提出了較高的要求。本文根據(jù)同時(shí)定位與構(gòu)圖(SLAM)的相關(guān)理論，研究一種同步定位與跟蹤算法，跟蹤一個(gè)不確定的運(yùn)動(dòng)物體位置，同時(shí)定位和校準(zhǔn)傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)位置信息。

1 同時(shí)定位與跟蹤原理

移動(dòng)目標(biāo)在一個(gè)粗定位的環(huán)境地圖中確定自己的位置，同時(shí)根據(jù)新的測(cè)量信息校正地圖,在過(guò)去的十多年中，SLAM方法證實(shí)了處理這類問(wèn)題的有效性。利用SLAM的思想，在線估計(jì)與更新移動(dòng)目標(biāo)的位置并更新傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置。

由于接收信號(hào)強(qiáng)度指示 (received signal strength indication，RSSI) 的定位技術(shù)利用能量的測(cè)量可直接計(jì)算節(jié)點(diǎn)間距離，沒(méi)有常用的視覺(jué)傳感器的視線障礙，但距離估計(jì)的可靠性不高。本文在初始估計(jì)時(shí)，允許有一定誤差存在，選用RSSI測(cè)量確定節(jié)點(diǎn)對(duì)和節(jié)點(diǎn)與目標(biāo)的相對(duì)距離。本文利用多維定標(biāo)(multidimensional sealing，MDS)的思想，根據(jù)經(jīng)典計(jì)量多維技術(shù)得到每個(gè)節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)相對(duì)坐標(biāo)圖，依次傳播得到網(wǎng)絡(luò)的相對(duì)坐標(biāo)圖，即根據(jù)節(jié)點(diǎn)和節(jié)點(diǎn)間的相關(guān)性信息來(lái)確定未知位置的節(jié)點(diǎn)坐標(biāo)。

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

圖1 同時(shí)定位與跟蹤的基本原理

2 算法分析

2.1 利用MDS的傳感器網(wǎng)絡(luò)粗定位

在所有節(jié)點(diǎn)間實(shí)際幾何距離正確的情況下,經(jīng)典的MDS算法可以給出沒(méi)有誤差的解。但是,由于節(jié)點(diǎn)的通信范圍限制,幾乎不可能實(shí)現(xiàn)所有網(wǎng)絡(luò)節(jié)點(diǎn)間的精確測(cè)距。在實(shí)際應(yīng)用中,只能測(cè)量相鄰節(jié)點(diǎn)間的距離信息,而對(duì)于多跳節(jié)點(diǎn)間的距離,本文利用Euclidean算法計(jì)算節(jié)點(diǎn)間幾何距離[6]。

首先,計(jì)算所有節(jié)點(diǎn)間的距離,建立MDS所需節(jié)點(diǎn)的距離矩陣D(X),再對(duì)距離的平方所構(gòu)成的矩陣D2(X)雙重中心化,然后對(duì)雙重中心化后的矩陣進(jìn)行奇異值分解,最后計(jì)算出所有點(diǎn)的相對(duì)坐標(biāo)X，生成相對(duì)坐標(biāo)圖,并利用少量的信標(biāo)節(jié)點(diǎn)和坐標(biāo)的旋轉(zhuǎn)、平移將全局相對(duì)坐標(biāo)轉(zhuǎn)換成絕對(duì)坐標(biāo)。只需知道3對(duì)轉(zhuǎn)換前后的二維坐標(biāo)，實(shí)現(xiàn)最優(yōu)線性轉(zhuǎn)換。

2.2 系統(tǒng)動(dòng)態(tài)模型和觀測(cè)模型

利用MDS算法，可以獲得網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，第i只傳感器節(jié)點(diǎn)的位置描述為pi=(xi,yi)，考慮到所有節(jié)點(diǎn)是固定不動(dòng)的，第i個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移方程為

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

假設(shè)系統(tǒng)中有效的節(jié)點(diǎn)數(shù)為N，用向量表示為

移動(dòng)目標(biāo)的狀態(tài)用xv(k) 給定，構(gòu)成系統(tǒng)狀態(tài)的有移動(dòng)目標(biāo)狀態(tài)和傳感器節(jié)點(diǎn)的位置狀態(tài)，稱為擴(kuò)張的狀態(tài)向量,表示為

擴(kuò)張的狀態(tài)轉(zhuǎn)移模型可完整描述為

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

式中A(k)為狀態(tài)矩陣，V(k)用于表示系統(tǒng)動(dòng)態(tài)噪聲?？梢?jiàn)，矩陣的維數(shù)為n×N，n為與每個(gè)節(jié)點(diǎn)關(guān)聯(lián)的狀態(tài)量，N為組合成地圖的節(jié)點(diǎn)個(gè)數(shù)。在一個(gè)大的環(huán)境中，外部傳感器不斷獲得測(cè)量數(shù)據(jù)，構(gòu)成環(huán)境地圖的路標(biāo)數(shù)不斷增加，矩陣維數(shù)呈幾何數(shù)量增長(zhǎng)，給計(jì)算機(jī)造成很大負(fù)擔(dān)。

移動(dòng)目標(biāo)和傳感器節(jié)點(diǎn)同樣配置,利用RSSI技術(shù)獲得節(jié)點(diǎn)和目標(biāo)之間的相對(duì)定位,第i個(gè)節(jié)點(diǎn)的觀測(cè)模型可寫為

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

式中W(k)用于表示系統(tǒng)測(cè)量誤差，該向量為一個(gè)零均值，方差為Ri(k)的隨機(jī)向量;Hi為觀測(cè)的第i個(gè)節(jié)點(diǎn)相對(duì)于系統(tǒng)狀態(tài)的觀測(cè)矩陣。

2.3 濾波算法分析

Kalman濾波包括2個(gè)階段：估計(jì)和更新。在估計(jì)階段，濾波器利用上一時(shí)刻的狀態(tài)估計(jì)當(dāng)前狀態(tài)，更新階段，濾波器利用在當(dāng)前狀態(tài)的觀測(cè)值優(yōu)化預(yù)測(cè)階段的預(yù)測(cè)值，以獲得一個(gè)更精確的當(dāng)前狀態(tài)的估計(jì)。

在經(jīng)典SLAM算法中，狀態(tài)向量維數(shù)為移動(dòng)目標(biāo)狀態(tài)加節(jié)點(diǎn)數(shù)的2倍，即M=2N+3，而在實(shí)際的目標(biāo)跟蹤中，只有移動(dòng)目標(biāo)周圍一跳內(nèi)的節(jié)點(diǎn)是有意義的，大量節(jié)點(diǎn)位置信息并無(wú)參考價(jià)值[7]。經(jīng)典算法中隨著節(jié)點(diǎn)數(shù)目的增加，標(biāo)準(zhǔn)濾波計(jì)算量劇增，不適用于實(shí)時(shí)目標(biāo)跟蹤。本文提出壓縮濾波來(lái)減小實(shí)時(shí)計(jì)算,將復(fù)雜度減小到O(2Na2)，Na是局部區(qū)域的路標(biāo)數(shù)。

在壓縮EKF濾波中，將狀態(tài)分為2個(gè)部分

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

狀態(tài)XA被定為移動(dòng)目標(biāo)周圍一跳內(nèi)的節(jié)點(diǎn)狀態(tài)，移動(dòng)目標(biāo)的狀態(tài)也包括在XA中。假設(shè)在一段時(shí)間內(nèi)得到的觀測(cè)點(diǎn)只與狀態(tài)XA相關(guān)，與XB不相關(guān)，即

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

根據(jù)2種不同的狀態(tài)，誤差協(xié)方差矩陣P寫為

考慮時(shí)刻k,更新之后的協(xié)方差矩陣為

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

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

3 仿真結(jié)果

由于RSSI定位距離超過(guò)20 m時(shí)有較大誤差，將傳感器最大測(cè)量距離定為20 m。在長(zhǎng)、寬均為180 m的范圍內(nèi)，隨機(jī)布置的節(jié)點(diǎn)個(gè)數(shù)為80個(gè)，設(shè)置3個(gè)配備GPS的錨節(jié)點(diǎn)。利用MDS算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)初始定位如圖2所示，節(jié)點(diǎn)平均誤差為5 m。本文利用一種簡(jiǎn)便的方法劃分全局地圖，將全局地圖分為9個(gè)正方形，每個(gè)正方形邊長(zhǎng)為60 m，選擇邊長(zhǎng)為60 m的正方形作為局部區(qū)域。

如果移動(dòng)目標(biāo)和探測(cè)到的節(jié)點(diǎn)屬于同一個(gè)封閉區(qū)域，不會(huì)產(chǎn)生較大誤差，但在探測(cè)到相鄰區(qū)域的節(jié)點(diǎn)時(shí)，由于前面節(jié)點(diǎn)的相關(guān)信息丟棄，會(huì)使得節(jié)點(diǎn)的估計(jì)位置誤差變大， 同時(shí)改變節(jié)點(diǎn)所在的區(qū)域的定位誤差。本文在局部區(qū)域轉(zhuǎn)換時(shí)設(shè)置一個(gè)滯后區(qū)域來(lái)避免多重地圖切換產(chǎn)生的誤差，即地圖之間有一定的重合，將該重合區(qū)域設(shè)定為20 m，如圖2中虛線所示。圖中圓圈為估計(jì)位置,黑圓點(diǎn)為實(shí)際位置，黑色方框?yàn)殄^節(jié)點(diǎn)，中間連線表示誤差。

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

在圖2所示的傳感器節(jié)點(diǎn)布局中，移動(dòng)目標(biāo)從原點(diǎn)開(kāi)始隨機(jī)移動(dòng)，移動(dòng)速度為1 m/s，線速度標(biāo)準(zhǔn)差為0.1 m/s，角速度標(biāo)準(zhǔn)差為3.00。設(shè)置實(shí)驗(yàn)中的觀測(cè)參數(shù)，最大觀測(cè)距離為20 m；觀測(cè)時(shí)間間隔為0.2 s；觀測(cè)的距離標(biāo)準(zhǔn)差為0.1 m。短距離和長(zhǎng)距離的目標(biāo)跟蹤和傳感器節(jié)點(diǎn)定位如圖3和圖4所示。

圖中“*”號(hào)描述實(shí)際節(jié)點(diǎn)位置，“+”號(hào)表示估計(jì)節(jié)點(diǎn)位置，橢圓表示估計(jì)誤差，“-”表示估計(jì)移動(dòng)路徑，“·-”表示實(shí)際移動(dòng)路徑，可見(jiàn)在較短距離的目跟蹤任務(wù)中，誤差會(huì)越來(lái)越大。在長(zhǎng)距離的跟蹤任務(wù)，由于關(guān)聯(lián)到確定位置的節(jié)點(diǎn)，誤差會(huì)隨著路徑的增加而減小。

圖3 短距離目標(biāo)跟蹤

圖4 長(zhǎng)距離目標(biāo)跟蹤

經(jīng)典EKF濾波算法中，80個(gè)參考節(jié)點(diǎn)的目標(biāo)跟蹤，算法復(fù)雜度為O(812)。本文中所用壓縮濾波算法計(jì)算量為O(Na2)，在離開(kāi)本地區(qū)域時(shí)更新的復(fù)雜度是O(Na2Nb2)。每個(gè)區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)小于10，區(qū)域內(nèi)算法復(fù)雜度最大為O(102)。移動(dòng)到一個(gè)新的區(qū)域時(shí)，需要做一個(gè)全局的更新，但該算法復(fù)雜度也遠(yuǎn)小于經(jīng)典EKF。

在經(jīng)典的目標(biāo)跟蹤任務(wù)中,傳感器節(jié)點(diǎn)位置誤差在初始定位后保持不變,本文的算法節(jié)點(diǎn)位置誤差隨時(shí)間變化比較如圖5所示。

圖5 WSNs節(jié)點(diǎn)定位誤差比較

實(shí)線為經(jīng)典MDS定位后的WSNs節(jié)點(diǎn)誤差協(xié)方差矩陣行列式,虛線為同時(shí)定位與跟蹤的節(jié)點(diǎn)誤差協(xié)方差?？梢?jiàn)，在短距離的跟蹤中，節(jié)點(diǎn)誤差沒(méi)有得到很好的改善，隨著關(guān)聯(lián)節(jié)點(diǎn)的增多，節(jié)點(diǎn)誤差隨著跟蹤的進(jìn)行而減小。

圖6為重復(fù)實(shí)驗(yàn)中目標(biāo)跟蹤誤差取均值的結(jié)果。實(shí)驗(yàn)結(jié)果表明:多次實(shí)驗(yàn)的平均誤差在0.9～2.6 m間，可見(jiàn)算法有較高的精度和穩(wěn)定性。

圖6 多次跟蹤平均誤差

4 結(jié) 論

本文提出了無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置不確定時(shí)移動(dòng)目標(biāo)的跟蹤和節(jié)點(diǎn)位置的更新。仿真結(jié)果表明:該算法能減小無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的位置誤差，在初始位置節(jié)點(diǎn)位置為5 m的情況下，通過(guò)估計(jì)—更新步驟，將節(jié)點(diǎn)平均位置誤差降低到3 m以下。同時(shí)，目標(biāo)跟蹤的誤差最大為2.6 m，并很大幅度減小算法復(fù)雜度。尤其是長(zhǎng)距離的跟蹤任務(wù)中，經(jīng)典EKF濾波算法復(fù)雜度太高而不能滿足實(shí)時(shí)性的要求，本文用一個(gè)局部SLAM算法的代價(jià)完成載體位置和局部地圖中的地標(biāo)位置估計(jì)，體現(xiàn)了該算法在長(zhǎng)時(shí)間執(zhí)行的優(yōu)越性。

參考文獻(xiàn):

[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] 姚先連,胡 貞,呂曉玲.無(wú)線傳感器網(wǎng)絡(luò)中卡爾曼濾波在移動(dòng)目標(biāo)跟蹤中的研究[J].長(zhǎng)春理工大學(xué)學(xué)報(bào):自然科學(xué)版，2011，34(3):88-92.

[6] 王 健,趙亞鳳,劉勁風(fēng).一種適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的定位算法[J].東北林業(yè)大學(xué)學(xué)報(bào),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/.