樂燕芬 盛存寶 施偉斌

（上海理工大學光電信息與計算機工程學院，上海，200093）

引 言

在室內(nèi)環(huán)境下對移動物體進行定位或追蹤，是物聯(lián)網(wǎng)基于位置服務的關(guān)鍵技術(shù)之一。由于室內(nèi)環(huán)境或建筑物密集區(qū)全球定位系統(tǒng)(Global position system，GPS)信號快速衰減，定位能力受制，因此國內(nèi)外的研究人員提出了多種不同的技術(shù)方案，如基于紅外信號[1]、超聲波技術(shù)[2]等來實現(xiàn)室內(nèi)定位，定位精度較高，但需要視距傳輸和專門的硬件設施，在大規(guī)模部署時有局限性。微軟研究院在2000年公布了基于無線局域網(wǎng)(Wireless area networks，WLAN)的RADAR定位系統(tǒng)[3]，隨著無線局域網(wǎng)的快速發(fā)展，基于WLAN的定位技術(shù)受到研究人員的青睞，成為實現(xiàn)室內(nèi)定位的重要研究方向，其中基于位置指紋庫的技術(shù)成為主流[4-10]。由于無線接入點(Access point，AP)發(fā)射的信號強度與距離的非線性及強時變性，這類方法或著眼于減小有效搜索區(qū)域、提高指紋匹配效率[5-6]，或致力于提高匹配的精準度[6-10]。隨著射頻技術(shù)和嵌入式系統(tǒng)的發(fā)展應運而生的無線傳感器網(wǎng)絡（Wireless sensor networks，WSNs）通常由大量低功耗的分布式傳感節(jié)點協(xié)同工作，來完成網(wǎng)絡控制、環(huán)境監(jiān)測、目標定位與跟蹤等諸多復雜的任務。在很多應用中，傳感數(shù)據(jù)必須攜帶位置信息才有意義，因此實現(xiàn)傳感器節(jié)點的自定位成為提供監(jiān)測目標信息的必要條件。如何設計穩(wěn)定、高精度的定位算法也成為WSNs研究中的熱點問題之一。在眾多的算法中，基于接收信號強度指示（Received signal strength indicator，RSSI）的定位技術(shù)由于無需增加額外的硬件設施而受到較多的關(guān)注[11]。Sandy等[12]利用移動目標接收的RSSI值，采用基于核函數(shù)的嶺回歸算法從指紋數(shù)據(jù)庫中找到匹配的參考位置點，然后再利用卡爾曼濾波進行位置估計完成追蹤。這種算法定位精度較高，但它利用機器學習的方法完成指紋匹配，涉及大量的計算，不適合某些利用運算能力有限的節(jié)點比如智能移動終端來實現(xiàn)追蹤的應用。石欣等[13]基于監(jiān)控區(qū)域內(nèi)，參考節(jié)點之間以及參考節(jié)點與移動節(jié)點之間通信的RSSI構(gòu)建相異性矩陣，采用多維度標度法求解節(jié)點位置。該算法魯棒性強，對RSSI擾動相對不敏感，但在實施過程中利用粒子群算法優(yōu)化參數(shù)，減小坐標轉(zhuǎn)換誤差，運算量較大；同時根據(jù)實際應用環(huán)境，需首先建立參考節(jié)點的RSSI相異性矩陣，進行算法模擬獲得相異性修正指數(shù)，在大監(jiān)控區(qū)域內(nèi)，這個參數(shù)如何選取還值得進一步研究。

考慮某些對位置隱私的應用，通常由終端設備完成自身定位或追蹤，并綜合考慮跟蹤精度、算法復雜度和存儲容量等因素，本文提出了適合錨節(jié)點稀疏分布的大監(jiān)控區(qū)域，基于位置指紋庫的局部加權(quán)K-近鄰算法(Local weighted K-nearest neighbor，L-WKNN)完成移動目標的初步定位，再利用卡爾曼濾波融合目標加速度信息完成追蹤，對算法的性能進行分析，并比較一階和二階卡爾曼濾波模型對定位精度的影響。

1 基于RSSI的高效追蹤算法

1.1 基于位置指紋的定位算法

RSSI定位的基本思想是未知位置的移動物體/用戶（也稱盲節(jié)點），通過測量接收到的位置確定的參考節(jié)點（也稱錨節(jié)點）所發(fā)射信號的強度來估計自身位置。實現(xiàn)方案主要有兩類：一類是利用射頻信號傳播模型確定RSSI值與信號傳播距離之間的關(guān)系[14]，再利用幾何方法，如三邊測量、三角定位等估計移動目標的位置，其定位精度依賴于信道傳播模型的精確度，而在室內(nèi)環(huán)境下，人員活動頻繁、布局室內(nèi)差異等使RSSI值多變，定位效果不佳；另一類定位算法可稱為位置指紋匹配算法。這類算法充分考慮實際檢測環(huán)境的靜態(tài)特性，并體現(xiàn)在指紋信息中。通常定位過程分為離線指紋數(shù)據(jù)庫構(gòu)建、在線指紋數(shù)據(jù)匹配兩個階段。在第1階段需要將待定位區(qū)域劃分多個參考點，并采集每個參考點接收的錨節(jié)點的RSSI值作為指紋信息，得到充分描述該區(qū)域的RSSI特性指紋庫；在第2階段移動目標獲取錨節(jié)點的RSSI值，并與參考點的指紋信息匹配，估計自身位置。常用的匹配方法包括最近K-近鄰算法、加權(quán)K-近鄰算法等[7-8]。這些算法簡單、易實現(xiàn)，但射頻信號的衰減與傳播距離并不是線性關(guān)系且易受環(huán)境干擾，使得測量RSSI值存在不確定性和高非線性，因此基于歐式距離的指紋匹配算法定位精度不高。

為提高匹配精度，近幾年也有文獻采用基于機器學習的神經(jīng)網(wǎng)絡，支持向量機(Support vector machines，SVMs)[8]、嶺回歸[6,11]、核函數(shù)[7,9-10]等方法對監(jiān)控區(qū)域參考位置的RSSI分布進行建模，但這類方法不僅離線訓練階段的建模過程涉及大量數(shù)據(jù)運算，在追蹤過程中完成指紋動態(tài)匹配同樣如此。如文獻[10]所提出的基于核函數(shù)特征提取的定位方法，在追蹤階段采集的指紋信息需經(jīng)過KPCA變換獲得特征向量，變化過程中指紋信息需與指紋庫中所有特征位置指紋進行高斯核函數(shù)運算，并通過計算與庫中每個特征指紋的歐式距離判斷其相似程度，這在目標監(jiān)控范圍廣、錨節(jié)點布局數(shù)量多、網(wǎng)格分布密集時，計算效率不高，也限制了其在某些應用場合，如需要利用移動終端實現(xiàn)多目標實時追蹤時的應用。

不同于上述方法，本文綜合考慮定位精度和計算效率，針對大監(jiān)控室內(nèi)區(qū)域下移動目標，如四軸飛行器、無人機的追蹤，提出了一種新的算法。該算法結(jié)合指紋地圖和加速度信息，采用一種改進的加權(quán)K-近鄰算法和卡爾曼濾波實現(xiàn)對移動目標的實時追蹤。

1.2 局部加權(quán)K-鄰近定位算法L-KWNN

假定在某二維監(jiān)測定位區(qū)域內(nèi)，布置了Ns個錨節(jié)點，每個錨節(jié)點的位置已知，可表示為Si=(Si1,Si2)T，i∈{1,…,Ns}。整個監(jiān)測區(qū)域可隨機或網(wǎng)格狀構(gòu)建N個指紋，也即N個參考位置點，表示為Pl=(Pl1,Pl2)T，l∈{1,…,N}。這N個參考位置點的物理位置信息構(gòu)成位置空間P=(P1，P2，…，PN)T。錨節(jié)點以確定的發(fā)射功率持續(xù)廣播，在每個參考位置點進行若干次信號采集，將RSSI均值作為參考位置點Pl的指紋信息，可表示為一個Ns維向量ρl=(ρ1l, …,ρxl, …，ρNsl)T，l∈{1,…,N},其中，ρxl是來自第x個錨節(jié)點的RSSI均值。若采用位置模型建立指紋庫，可以獲得N個訓練集{ρl,Pl}，l∈{1,…,N}。離線訓練階段就是要找到最佳的變換函數(shù)Ψ(·)，對每一組輸入的RSSI值ρl確定相應的參考位置Pl。確定Ψ(·)后，在線定位階段移動節(jié)點利用變換函數(shù)，由RSSI值估算自身位置。

本文算法并不采用上述復雜的模式匹配方法完成指紋匹配，而是采用一種改進的K-近鄰算法L-KWNN完成目標節(jié)點的粗定位，具體如下：設某移動節(jié)點在大監(jiān)測區(qū)域內(nèi)自由活動，在k時刻的位置表示為x(k)=(x1(k)，x2(k))。追蹤時，移動節(jié)點以固定時間間隔接收來自錨節(jié)點的信號，在k時刻的RSSI向量用ρk=(ρ1,…，ρNs)T表示?？紤]到錨節(jié)點布局稀疏，至少間隔10 m以上，環(huán)境變化引起的RSSI波動會增大實測的RSSI向量與指紋的歐式距離，但基本不會改變對應的錨節(jié)點信號強度的分布趨勢，也就是即使擾動存在，改變某1,2個錨節(jié)點的強度變化趨勢，但傳輸距離越遠信號衰減越多這個總體的趨勢并不改變。基于這一點，本文算法的步驟如下：

（1）完成局部錨節(jié)點匹配。以RSSI值的大小對錨節(jié)點進行刪選，從ρk的Ns個RSSI值中選出信號強度最大的Nk個，并確定其所對應的錨節(jié)點物理位置作為局部匹配錨節(jié)點。

（2）確定待匹配指紋。指紋庫中位于局部匹配錨節(jié)點周圍一定區(qū)域內(nèi)的N′個參考位置點作為待匹配的指紋。

（3）找到n個匹配指紋。計算ρk與N′個參考位置點指紋信息ρi的歐式距離

式中(ρk,ρi)可以表征ρk與ρi間的相似程度，其值越小，二者越相似，也可認為k時刻移動節(jié)點與對應參考位置點越接近，位置估算可靠性強。對這N′個進行排序，選出前n個最小的及其對應的參考位置點Pi作為匹配集I(k)。

（4）估算位置。移動節(jié)點在k時刻的位置可以用式（2）估算

式中：Pi為所選參考位置點的坐標；wn為歸一化的權(quán)重系數(shù)，表征該參考位置點對估算位置的影響度，可表示為

根據(jù)以上算法描述，可以得出L-WKNN算法的優(yōu)勢如下：

（1）算法在離線階段只需采集每個參考位置點的RSSI值，構(gòu)成指紋數(shù)據(jù)庫，并不需要在更高維度進行特征提取，離線階段涉及的訓練工作量小。

（2）算法在追蹤過程中，對獲得的指紋數(shù)據(jù)并不進行全局匹配，而是首先獲取移動節(jié)點最鄰近的若干錨節(jié)點，再對錨節(jié)點一定物理范圍內(nèi)的參考位置點進行匹配，尋找最接近的n個位置，通過加權(quán)平均后作為移動節(jié)點的估算位置。由于本算法的應用場景為大監(jiān)控區(qū)域的移動追蹤，錨節(jié)點布局是物理間距在十幾米到幾十米的范圍內(nèi)。雖然RSSI值在采集過程中由于室內(nèi)環(huán)境的復雜性會存在干擾，一般測量值會存在10 dBm的誤差，對應的距離為2～4 m，這并不影響錨節(jié)點的選取。另外，由于錨節(jié)點分散分布，即使室內(nèi)環(huán)境局部突變引起干擾增強，其對RSSI的影響一般也只局限于某一個錨節(jié)點，不影響其他錨節(jié)點的選取，因此這種局部匹配法在提高計算效率的同時并不會引入大的定位誤差。

1.3 追蹤算法

基于位置指紋獲得的節(jié)點位置，通常定位精度不夠高。通過對移動節(jié)點運動狀態(tài)的分析，建立合適的模型，采用卡爾曼濾波可以提高定位精度，很多文獻對移動節(jié)點的定位或追蹤采用了這一方法。本文根據(jù)移動節(jié)點的運動狀態(tài)，采用一階和二階模型[12]對其追蹤性能進行仿真分析。

假設移動節(jié)點攜帶有加速度傳感器，在二維監(jiān)控區(qū)域內(nèi)運動，每個節(jié)點獨立追蹤。為表述簡單又不失一般性，本文估計某個節(jié)點在當前k時刻的坐標位x(k)，采用線性模型描述節(jié)點的運動

式中：x(k-1)為節(jié)點前一時刻的位置；A為2×2維的狀態(tài)轉(zhuǎn)移矩陣；B(k)為取決于加速度的輸入控制量；V(k)為隨機噪聲，一般可認為是均值為0，協(xié)方差矩陣為Q(k)的正態(tài)分布，即V(k)～Ν(0,Q(k))。節(jié)點在運動過程中，與錨節(jié)點通信，并獲得一些測量值z(k)。這樣，觀測方程就可描述為

式中：H為觀測矩陣，該矩陣描述了狀態(tài)量x(k)與觀測量z(k)之間的關(guān)系。n(k)～Ν(0,U)為觀測噪聲，符合均值為0，協(xié)方差矩陣為U的正態(tài)分布。若定義了狀態(tài)空間模型和觀測方程，基于測得的加速度信息，可以由前一時刻位置x(k-1)預測當前位置x(k)。一階模式下，在連續(xù)的兩個采樣間隔內(nèi)，假設節(jié)點速度保持恒定；二階模式下則認為在采樣間隔內(nèi)，加速度為常數(shù)，而速度則線性變化。不管哪種模式，移動節(jié)點的運動均用式(4)描述，兩種狀態(tài)模型具體描述如下。

(1)一階狀態(tài)模型

該模型認為開始追蹤前移動節(jié)點靜止，也即v(0)=0。追蹤開始后，節(jié)點速度按式(6)進行更新計算

式中a(k)為在k時刻采集的加速度。由于設定k-1時刻到k時刻速度近似恒定，因此式(4)中

而A是2×2的單位矩陣，這也意味著此模型適合加速度較小的移動物體，在一個采樣間隔內(nèi)，可認為速度變化不大。

模型的位置噪聲V(k)由加速度測量誤差所引入，可認為符合均值為0，方差矩陣為Q(k)的正態(tài)分布，其中

由于初始位置確定，Q(0)=0。Qv(k)為k時刻速度的方差矩陣，符合

式中：diag(ε2)為2×2的對角矩陣，對角線上的元素εd2，d=1,2，是測得的運動節(jié)點加速度的方差，且假設各運動軸方向上的加速度彼此獨立。也由于這一點，速度的方差矩陣Qv(0)為對角線矩陣，且有Qv(0)=0。

(2)二階狀態(tài)模型

假設節(jié)點在時刻k-1與k之間的Δt時間內(nèi)加速度恒定，表示為a(k)，那么仍采用式(6)估計節(jié)點的運動速度，而狀態(tài)方程的控制量B(k)則符合

式中：k=0時，Q(k)=0；速度的方差矩陣Qv按式(9)更新。

兩個模型的區(qū)別在于采樣間隔內(nèi)節(jié)點運動是假設為勻速運動還是勻加速運動。對于運動軌跡變化劇烈的節(jié)點，顯然二階模型更適合。不管一階還是二階模型，涉及的只有簡單的迭代運算，所需的計算量都不大。

其次考慮模型的觀測方程。在對運動節(jié)點追蹤過程中，并不是把測量所得RSSI值作為觀測方程的觀測量，而是利用前述L-WKNN獲得的運動節(jié)點的估算位置x^(k)作為觀測量z(k)，也即

這樣，觀測方程中的H矩陣可設為單位矩陣，而觀測噪聲n(k)的協(xié)方差矩陣U在跟蹤之前需計算確定?？梢园压?jié)點布置在監(jiān)控區(qū)域的S個確定位置，獲得S組{ρl,Pl}，再利用L-WKNN算法估算位置，通過計算實際位置與估算位置的誤差獲得方差作為觀測噪聲的方差U。一般可認為該方差矩陣在整個跟蹤期間不變，并適用所有的運動節(jié)點。

通過以上分析確定了運動節(jié)點的狀態(tài)空間模型和觀測方程，接著便可采用卡爾曼濾波的方法解決跟蹤問題：首先用k-1時刻運動節(jié)點的狀態(tài)(位置)估計值和狀態(tài)空間方程來預測k時刻的狀態(tài)(位置)；然后用觀測方程對預測值進行修正獲得k時刻的狀態(tài)估計值?？柭鼮V波以最小均方誤差為估計準則，采用迭代運算對存儲空間要求不高，適合傳感器節(jié)點運算。

狀態(tài)轉(zhuǎn)移矩陣A為單位矩陣，狀態(tài)方程中的位置隨機噪聲V(k)的方差可由式（11）獲得

2 仿真分析

為驗證本文所提算法的可行性，以及在室內(nèi)環(huán)境下RSSI存在較大波動時算法的魯棒性，本文采用MATLAB進行仿真實驗，分析算法的性能。仿真過程中，主要分析以下參數(shù)對算法定位性能的影響：

（1）局部匹配錨節(jié)點個數(shù)Nk、參考位置點個數(shù)N′、最近鄰參考位置數(shù)n對L-WKNN算法性能的影響；

（2）節(jié)點不同運動狀況下，一階、二階運動模型的定位性能；

（3）RSSI值噪聲對本定位算法的影響。

實驗采用平均誤差來衡量算法的性能，定義如下

式中：Nm為在線估計位置點的個數(shù)；Xi為運動節(jié)點的實際位置；Xi′為估計位置。

實驗仿真場景為100 m×100 m的二維監(jiān)控區(qū)域，均勻布置了25個錨節(jié)點和121個參考位置點。每個參考位置點的RSSI值由式(14)給出的Okumura-Hata模型[15]獲得

式中：ρi,l為在參考位置點Pl接收到的來自錨節(jié)點Si的信號強度，也是參考位置點Pl指紋信息向量中的第i個元素；ρT為初始功率；η為路徑損耗因子，根據(jù)室內(nèi)環(huán)境的差異，一般設為2～4；‖ ‖Si-Pl為參考位置點Pl與錨節(jié)點Si的歐氏距離；由于O-H模型通常適用室外環(huán)境，針對室內(nèi)存在人員走動，多徑傳播，障礙物等因素，用均值為0、方差為σ2的高斯隨機變量Xσ來模擬引起的RSSI值的擾動。仿真參數(shù)設定見表1。

表1 仿真參數(shù)設定Tab.1 Setting of simulation parameters

圖1給出了一個移動節(jié)點在監(jiān)控區(qū)域內(nèi)的運動軌跡，以及基于本文所提出的L-WKNN算法和二階卡爾曼濾波后的追蹤軌跡，采樣間隔為1 s，共采集100個點。其各運動軸的加速度如圖2所示。在建立指紋庫時，每個參考位置點接收到的來自錨節(jié)點信號的RSSI值加入了方差σ2為1的噪聲，而在在線定位過程中，節(jié)點采集的RSSI值加入了方差σ2ρ為16的測量噪聲。L-WKNN算法中，選取了接收信號最強的4個局部錨節(jié)點，并以這4個錨節(jié)點周圍20 m內(nèi)的參考位置點作為加權(quán)K-近域算法匹配的位置點范圍。本次仿真中選取了4個最近鄰的參考位置點加權(quán)平均后作為節(jié)點運動估計位置，整個軌跡追蹤的平均誤差小于3.1 m。以此估計位置作為節(jié)點運動模型中的觀測值，并設兩個運動軸的加速度測量噪聲誤差的均方差ε設為0.01 m/s2，觀測噪聲的方差U分別設為1.5和2，用二階卡爾曼濾波進行估計，整個追蹤軌跡濾波后的平均誤差為1.4 m。

圖1 運動節(jié)點的軌跡及追蹤路徑Fig.1 Tracking trajectory of the target

圖2 移動節(jié)點的加速度Fig.2 Acceleration signals of the target

同時也發(fā)現(xiàn)，在RSSI測量方差為16時，本算法與指紋庫全局匹配下找到的最近鄰指紋一致。圖3給出幾種算法定位誤差的累計密度函數(shù)(Cumulative density function,CDF)，其中WKNN與L-WKNN曲線完全重合。網(wǎng)格間距10 m的情況下，采用本算法，90%的定位誤差小于3 m。

（1）Nk，N′，n對算法定位性能的影響

Nk為局部匹配錨節(jié)點個數(shù)，范圍在1～Ns之間，隨著該值的增加，算法的計算量增大，當Nk=Ns時，本算法退化為普通的加權(quán)K-近鄰算法；N′為算法所選擇進行匹配的參考位置點個數(shù)，一般選擇局部匹配錨節(jié)點某半徑范圍內(nèi)的參考位置點，該半徑可根據(jù)網(wǎng)格的大小進行調(diào)整；n為所選擇的最近鄰參考位置數(shù)，在文獻中根據(jù)網(wǎng)格的大小取值多在4～8范圍內(nèi)。針對圖1中的運動軌跡，改變這幾個參數(shù)值，用L-WKNN算法進行了100次追蹤，平均定位誤差e及定位誤差的標準差σMSE如表2所示。從表2中可看出：適當增大Nk，N′，n有助于提高定位精度，但效果并不明顯。在本仿真條件下，也即網(wǎng)格間距10 m，RSSI值測量噪聲方差σ2ρ為16時，4個局部匹配錨節(jié)點半徑20 m內(nèi)的參考位置點可以有效完成定位，且平均定位誤差e說明算法整體定位精度較高，而標準差σMSE表明算法的一致性較好，定位誤差波動小。

圖3 定位誤差累計密度函數(shù)Fig.3 CDF of the error distance

表2 不同條件下的L-WKNN算法的定位精度Tab.2 Positioning accuracy of L-WKNN with various parameters

（2）測量噪聲對算法的影響

在運動節(jié)點動態(tài)追蹤過程中，室內(nèi)復雜的環(huán)境必然會使測量的RSSI值產(chǎn)生干擾。本文用高斯隨機變量的不同方差值來模擬RSSI擾動的大小。圖4依次取σρ2=1，9，25來分析追蹤算法的精度，其他仿真條件設置同圖1。從圖4中可以清楚看出，當存在較大測量噪聲時，L-WKNN的定位誤差增大，而經(jīng)過二階卡爾曼濾波后，算法依舊呈現(xiàn)良好的追蹤性能，定位平均誤差在1.5 m左右。

圖4 取不同時各算法的定位誤差累計密度函數(shù)Fig.4 CDF of the proposed methods under differentvalues

（3）一階、二階運動模型的性能分析

為研究本文提出的一階和二階運動模型對移動節(jié)點追蹤性能的影響，設置了具有如圖5所示運動特點的軌跡，采樣間隔為1 s，前55 s內(nèi)移動節(jié)點與圖1的軌跡一致，具有變化的加速度，從第56 s開始，節(jié)點保持勻速運動。為保證節(jié)點一直處于監(jiān)控區(qū)域，共采集了80個采樣點。加速度測量噪聲誤差的標準差為測量值的10%，其他仿真條件設置同圖1。圖6給出了每個采樣點50次仿真的平均定位誤差?？梢钥闯?，不管運動節(jié)點的加速度如何變化，二階運動模型的定位精度稍高于一階運動模型，前者的平均定位誤差為1.1 m，后者的平均定位誤差為1.6 m。

圖5 移動節(jié)點的速度Fig.5 Velocity signals of the target

圖6 不同算法的定位誤差Fig.6 Estimation error of different methods

3 結(jié)束語

本文針對錨節(jié)點稀疏布局的室內(nèi)大監(jiān)控區(qū)域，提出了一種基于位置指紋的室內(nèi)追蹤算法。該算法在離線階段不需要訓練建模，在線階段采用L-WKNN算法，通過尋找局部匹配錨節(jié)點大幅縮小待匹配的指紋數(shù)量，從而提高計算效率。在追蹤階段，采用融合移動節(jié)點加速度信息的卡爾曼濾波提高追蹤精度，對一階和二階卡爾曼濾波的追蹤性能進行了分析。仿真實驗表明本算法具有良好的一致性，整體定位精度較高，可有效抑制室內(nèi)環(huán)境變化引起的RSSI測量值擾動對目標追蹤性能的影響，適合室內(nèi)移動目標的實時追蹤。在四軸飛行器上對本算法進行性能驗證將是下一步研究方向。