一種基于感知概率的室內定位匹配算法

楊 萌，修春娣，鄒 坤，楊東凱，劉 源

(1.北京航空航天大學 電子信息工程學院，北京 100191；2.中國電信集團 上海市電信公司，上海 200120)

1 引言

基于位置的服務被應用于很多領域，大部分的設備是基于室外定位系統(tǒng)，如全球定位系統(tǒng)(global positioning system，GPS)。但是基于GPS的定位需要視距來保證可靠的定位精度，并不適用信號多變且環(huán)境復雜的室內定位系統(tǒng)，因此基于無線局域網絡中無線保真(wireless fidelity，WiFi)的室內定位技術得到了廣泛的應用?，F(xiàn)今很多建筑中裝有WiFi接入點，現(xiàn)有的基礎設施可以基本上滿足定位需求，因此可以減少經濟開支和額外的硬件裝配。

基于WiFi的室內定位方法主要有基于傳播模型的定位方法和基于指紋匹配的定位方法。基于傳播模型的定位方法不需要預先采集接入點(access point，AP)的信號強度，只需找出射頻信號在室內環(huán)境中的傳播模型，依據信號傳播模型和設備與AP之間的信號強度差來估計位置信息，可以實現(xiàn)距離的粗略估計，不能提供準確的定位，因為接收信號強度(received signal strength，RSS)[1]很容易受周圍環(huán)境影響。指紋匹配的定位算法構建信號強度與定位位置之間的映射關系，使用存儲所有參考點(reference point，RP)的RSS信息的數(shù)據庫來進行匹配計算，可以獲得較好的定位效果，因此，本文的工作主要是基于指紋定位技術。

基于指紋匹配的室內定位技術通常工作在兩個階段：離線訓練階段和在線階段。在離線訓練階段，目標區(qū)域中所有RP接收到的來自可用AP的信號強度信息形成指紋數(shù)據庫。在線定位階段，將實時采集的RSS與指紋數(shù)據庫中的指紋進行匹配，從而得到定位設備的位置信息。

基于指紋匹配的定位算法分為確定型和概率型兩種算法。確定型定位算法主要是比較指紋庫中的指紋與定位階段采集的RSS之間的相似度，選擇最大相似度的指紋對應的位置作為測量設備的估計位置。常采用的匹配算法為k近鄰(k-nearest neighbor，k-NN)[2-6]，該算法首先采用歐式距離度量指紋庫中指紋與實測RSS之間相似度，找出相似度最大k個位置，然后計算這k個位置的質心得到估計位置。概率型算法把實測RSS與指紋庫中指紋的匹配過程看成概率估計問題，基于RSS信號的統(tǒng)計特性，建立室內環(huán)境中射頻信號的概率分布模型，解決了復雜環(huán)境下RSS值的不確定性。常用的基于概率型算法為最大似然算法(maximum likelihood，ML)[2]，基于貝葉斯框架理論，將后驗概率轉化為似然概率問題，匹配最大的似然概率，得到估計位置信息。常用來計算似然概率的方法有理想高斯模型[7]，直方圖統(tǒng)計模型[8]和核密度估計方法[9]。其中核密度估計方法不利用有關數(shù)據分布的先驗知識，對數(shù)據分布不附加任何假定，是一種從數(shù)據樣本本身出發(fā)研究數(shù)據分布特征的方法，可以更準確的表征復雜信號的分布，從而提高定位精度。

在離線訓練階段，并非每個RP都能接收到測試區(qū)域內的所有AP信號，RP點可以感知到相應的AP信號樣本越多，可用于匹配計算的信息越多，該RP點指紋的可靠性越高，因此本文中引入感知概率的定義，來表征定位區(qū)域內不同位置的信號分布特征，并將感知概率結合k-NN算法，提出修正k-NN，與常用理想化高斯分布模型不同，本文采用核直方圖統(tǒng)計模型和密度估計方法計算似然函數(shù)，并將感知概率和核密度估計結合ML算法，提出修正ML算法。

2 修正算法

2.1 感知概率

由于信號衰減和障礙物的影響，同一個采樣設備很難在不同的位置甚至在同一位置獲得相同的信號強度。但是由于環(huán)境和AP功率的穩(wěn)定性，同一個采樣設備在相同的位置獲得特定AP信號的概率是相對穩(wěn)定的。如果在測試位置處的AP信號強度小于采樣設備可以感知到的最小信號強度，表示設備不能夠感知到AP信號，用一個固定的信號強度代替不能感知到的信號強度信息。因此，感知概率定義為感知到的AP次數(shù)與總的訓練樣本數(shù)之比[2]。

假設在一個室內測試區(qū)域中有n個RP和m個AP，在離線訓練階段，AP信號采集可以看成一個伯努利過程。對特定RP，每次采樣可以獲得一個二進制序列B=(b1,b2,…bj,…,bn)，其中bj∈(0,1)。對于第i個RP，可以感知到的第j個AP的次數(shù)為nbj|ω(1|ωi)，總的訓練樣本數(shù)為N(1|ωi)，因此第i個RP對第j個AP的感知概率可以定義為：

(1)

由感知概率的定義可知，感知概率可以一定程度上表征測試區(qū)域內不同位置的信號分布情況，因此基于感知概率的修正算法可以提高定位算法精度。

2.2 修正k-NN算法

在離線訓練階段，采集的樣本存儲為指紋數(shù)據庫，在線定位階段，將采集到的信號強度信息與指紋數(shù)據庫中的指紋信息進行匹配，對每一個RP點，相應的歐氏距離定義為：

(2)

式(2)中，S=(s1,s2,…,sn)為實測信號向量，Ri=(r1,r2,…,rn)為指紋庫中存儲的第i個RP的指紋信息。

修正算法將感知概率和歐氏距離結合起來，定義了感知歐氏距離。假設離線訓練階段感知概率相對穩(wěn)定，記為Pbj|ω(1|ωi)，那么在線階段可以感知到信號的概率是Pbj|ω(1|ωi)，計算歐氏距離時利用離線階段的RP位置指紋進行計算；同樣地，不能感知到信號的概率是1-Pbj|ω(1|ωi)，此時采樣特定數(shù)值C進行匹配計算。兩者之和即為感知歐氏距離。如公式(3)所示：

(3)

式(3)中，Pbj|ω(1|ωi)為第i個RP對第j個AP的感知概率，C=-100 dbm為代替未感知到的信號強度情況的數(shù)值。

k-NN算法通過選擇與實時測量位置距離最近的k個RP點，并計算出這k個RP點對應坐標的均值，即為實時測量位置的估計坐標：

(4)

式(4)，中(xi,yi)'=(xt,yt)為與實時測量位置距離最近的K個RP點的坐標，t為RP點由歐氏距離從小到大排列時對應的前K個RP點的序號為

(5)

2.3 修正最大似然概率算法

為了在復雜環(huán)境下獲得盡可能好的定位性能，將感知概率引入到貝葉斯估計框架中，并使用直方圖統(tǒng)計模型和核密度估計方法進行似然概率計算，提出了基于感知概率的修正最大似然概率算法，具體方案如下：

對于概率型算法，把實測RSS與指紋庫中指紋的匹配過程看成概率估計問題，則最大后驗概率分布可以描述為：

P(ωi|RSS)>P(ωj|RSS)
i,j=1,2,…,m,j≠i

(6)

式(6)中,ω1,ω2,ω3,…,ωm為離線訓練階段中m個RP的位置信息，RSS為在線測量階段的接收信號強度。

基于貝葉斯定理，未知參數(shù)的后驗概率分布可以表示為：

(7)

式(7)中，P(ωi)為對應參考點位置的概率，稱之為先驗分布密度，P(RSS)為常量。P(RSS|ωi)為給定參考點ωi的數(shù)據后的似然概率，各個參考點是相互獨立的，并且似然概率相對于參考點而言是唯一的。貝葉斯定理可等價描述為：后驗概率分布∝似然函數(shù)×先驗分布函數(shù)。

一般情況下，先驗分布密度P(ωi)為根據實踐經驗在量測實驗數(shù)據之前確定的，在不考慮定位歷史信息的情況下，P(ωi)為常量，因此最大后驗概率問題可以轉化為最大似然概率問題，即：

P(RSS|ωi)>P(RSS|ωj)
i,j=1,2,…,m,j≠i

(8)

假定各個接入點發(fā)出的射頻信號之間的影響可以忽略，即各個AP之間是相互獨立的，因此可得到似然概率的表達式：

(9)

式(9)中，P(RSSj|ωi)為第i個RP對第j個AP的匹配似然概率。

(1)直方圖統(tǒng)計模型

利用直方圖統(tǒng)計模型來獲得近似的似然概率，離線訓練階段，根據采樣數(shù)據以及設定的組距得到相應的分組區(qū)間，在線階段，通過判斷接收信號所屬的分組區(qū)間，統(tǒng)計分組區(qū)間內可感知樣本數(shù)目，得到相應的匹配似然概率為：

(10)

則感知似然概率為：

(11)

式(11)中，C=-100 dbm為用來代替未能感知到的信號強度。

(2)核密度估計

采用適合于復雜信號分布的無參數(shù)核密度估計方法來計算似然概率，核密度估計方程為：

(12)

式(12)為一個加權平均，而核函數(shù)K(·)是一個權函數(shù)，核函數(shù)的形狀和值域控制著用來估計f(x)在點x的值時所用數(shù)據點的個數(shù)和利用的程度，直觀來看，核密度估計的好壞依賴于核函數(shù)和核寬參數(shù)h的選取。

本文核函數(shù)K(·)選定為高斯核函數(shù)，如公式(13)所示為：

(13)

由于核寬參數(shù)h的取值對基于訓練樣本的核密度估計曲線的平滑性有較大的影響，所以需要對核寬參數(shù)h進行優(yōu)化選擇[11]。本文中通過最小化均方誤差來實現(xiàn)核寬參數(shù)的優(yōu)化。

(14)

從積分均方誤差的定義式可以看出，被積函數(shù)非負，所以上式可改寫為：

(15)

假定核方程K(u)連續(xù)，真實核密度方程f有界，且二次導數(shù)連續(xù)。定義兩個常數(shù)α和β，其中

根據泰勒展開式，MISE可以展開為如下方程：

(16)

因此，最小化均方誤差MISE，可以得到核寬參數(shù)的優(yōu)化解為：

(17)

當核函數(shù)為高斯方程時，核寬參數(shù)的優(yōu)化解為：

(18)

將感知概率與核密度估計方程結合起來，可以得到第i個RP對第j個AP的感知似然概率為：

(19)

式(19)中，Sk為設備接收到的第k個AP的實時信號強度，C=-100 dbm為用來代替未能感知到的信號強度。

通過直方圖統(tǒng)計模型或者核密度估計方法得到感知似然概率之后，通過ML算法，可求得測量位置的估計坐標為：

(20)

(21)

3 實驗及算法性能分析

3.1 實驗環(huán)境

為了驗證修正算法的定位性能，在基于WLAN框架的室內環(huán)境下進行驗證實驗。測試環(huán)境位于北航新主樓六層，面積為22 m×14 m的室內區(qū)域，主要由房間內區(qū)域和走廊區(qū)域兩部分組成。其中在房間內布置3個符合IEEE 802.11b標準的AP，并將房間區(qū)域劃分為91個1.1 m×1.1 m的格子；在走廊內布置兩個AP，并將走廊區(qū)域劃分為104個1.2 m×1.2 m的格子。將195個參考點的位置選定為195個格子的中心。實驗區(qū)域及AP分布如圖1所示。

圖1 試驗區(qū)域

在離線訓練階段，對195個參考點分別進行采樣，每個參考點采樣60次，將60次采樣RSS的平均值作為指紋，構成指紋數(shù)據庫，指紋數(shù)據庫格式如表1所示。在線階段，對各個參考點采樣20次，并將平均采樣值作為實測RSS，用于驗證算法性能。

表1 指紋數(shù)據庫

3.2 實驗結果與性能分析

3.2.1 感知概率

室內AP2和室外走廊AP4感知概率分布情況如圖2所示。從分布情況可知：對于AP2，室外的參考點(92-195RPs)的感知概率小于1，相反的，對于AP4，室內參考點(1-91RPs)的感知概率小于1。感知概率的分布情況符合信號傳播模型，也一定程度上反映了信號強度的分布特性。

圖2 感知概率分布圖

根據感知概率的定義，對于感知概率較小的AP，信號有很大的不確定性，可用匹配計算可靠性較低，因此把感知概率引入到現(xiàn)有算法中，可以一定程度上提高定位精度。

3.2.2 修正k-NN算法

對195個參考點進行測試并改變k-NN算法中的k值，以驗證修正算法性能。圖3為測試位置與真實位置之間誤差距離的累積分布函數(shù)(cumulative distribution function，CDF)圖。

圖3 確定型算法誤差CDF圖

表2列出了不同k值時的算法定位誤差結果。當k=3時，修正算法可以達到最好的定位效果，修正wkNN算法的平均誤差距離相對于k-NN算法提高了4.3%，修正k-NN算法的平均誤差距離相對于k-NN算法提高了6.9%。

表2 定位誤差

誤差結果分析：由于測試區(qū)域簡單并且AP信號基本上可以覆蓋所有區(qū)域，只有少數(shù)參考點的感知概率小于1，因此修正算法沒有達到最好的定位性能，修正算法對感知概率較小的AP可獲得較好的定位精度。

3.2.3 修正ML算法

圖4為修正ML算法采用核密度估計技術與直方圖統(tǒng)計模型的誤差距離的CDF對比圖。其中直方圖統(tǒng)計模型帶寬設為3dBm。修正ML算法采用KDE方法，90%定位誤差小于4 m，而采用直方圖統(tǒng)計模型相同的定位精度為76%。

圖4 概率型算法誤差CDF圖

核寬參數(shù)h對核密度估計的影響大于核函數(shù)的選擇，對核密度估計曲線有較大影響，圖5中實線為核寬參數(shù)h取最小均方誤差下的最優(yōu)解時的誤差CDF圖，表明當核寬參數(shù)取最優(yōu)解時，定位精度有較大提升。

圖5 核寬參數(shù)對定位精度的影響

4 結論

本文中，首先為了在一定程度上反映信號的分布特征，給出了感知概率的具體定義，然后將

感知概率對歐式距離和似然概率進行加權，提出感知歐式距離和感知似然概率，并將直方圖統(tǒng)計模型和核密度估計技術引入到貝葉斯理論框架中，提出確定型k-NN和概率型ML修正算法。通過實驗表明，兩種修正算法均可以提高定位精度。

[1] KAEMARUNGSI K，KRISHNAMURTHY P.Properties of Indoor Received Signal Strength for WLAN Location Fingerprinting[C]//Proceedings of the First Annual International Conference on Mobile and Ubiquitous Systems：Networking and Services(MobiQuitous'04).Massachusetts：IEEE，2004：14-23.

[2] 鄒坤，修春娣，楊東凱.基于感知概率的室內定位系統(tǒng)[J].全球定位系統(tǒng)，2013(6)：7-11.

[3] LI Bing-hao，SALTER J，DEMPSTER A G，et al.Indoor Positioning Techniques Based on Wireless LAN[EB/OL].[2014-08-10].http：//www.gmat.unsw.edu.au/snap/publications/lib_etal2006a.pdf.

[4] ZHOU Mu，XU Yu-bin，MA Lin.Radio-map Establishment Based on Fuzzy Clustering for WLAN Hybrid knn/ann Indoor Positioning[J].中國通信，2010，7(3)：64-80.

[5] SHIN B J，LEE J H，LEE T J，et al.Enhanced Weighted k-nearest Neighbor Algorithm for Indoor Wi-Fi Positioning Systems[J].International Journal of Networked Computing and Advanced Information Management，2012，2(2)：15-21.

[6] 張曉亮，趙平，徐冠青，等.基于一種優(yōu)化的KNN算法在室內定位中的應用研究[J].電子設計工程，2013，21(7)：44-46.

[7] LEE D J，CAMPBELL M E.Iterative Smoothing Approach Using Gaussian Mixture Models for Nonlinear Estimation[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).Vilamoura：IEEE，2012：2498-2503.

[8] ROOS T，MYLLYMAKI P，TIRRI H，et al.A Probabilistic Approach to WLAN User Location Estimation[J].International Journal of Wireless Information Networks，2002，9(3)：155-164.

[9] HAGMANN M，SCAILLET O.Local Multiplicative Bias Correction for Asymmetric Kernel Density Estimators[EB/OL].[2014-08-10].http：//papers.ssrn.com/sol3/papers.cfm?abstract_id=473541.

[10] SHI Xun.Selection of Bandwidth Type and Adjustment Side in Kernel Density Estimation over Inhomogeneous Backgrounds[J].Geographical Information Science，2010，24(5)：643-660.

[11] ALIREZA T，MIRCEA N，GEORGE B，et al.Non-parametric Statistical Background Modeling for Efficient Foreground Region Detection[J].Machine Vision and Applications，2009，20(6)：395-409.