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

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

1 引言

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

基于WiFi的室內(nèi)定位方法主要有基于傳播模型的定位方法和基于指紋匹配的定位方法?；趥鞑ツＰ偷亩ㄎ环椒ú恍枰A(yù)先采集接入點(diǎn)(access point，AP)的信號(hào)強(qiáng)度，只需找出射頻信號(hào)在室內(nèi)環(huán)境中的傳播模型，依據(jù)信號(hào)傳播模型和設(shè)備與AP之間的信號(hào)強(qiáng)度差來估計(jì)位置信息，可以實(shí)現(xiàn)距離的粗略估計(jì)，不能提供準(zhǔn)確的定位，因?yàn)榻邮招盘?hào)強(qiáng)度(received signal strength，RSS)[1]很容易受周圍環(huán)境影響。指紋匹配的定位算法構(gòu)建信號(hào)強(qiáng)度與定位位置之間的映射關(guān)系，使用存儲(chǔ)所有參考點(diǎn)(reference point，RP)的RSS信息的數(shù)據(jù)庫來進(jìn)行匹配計(jì)算，可以獲得較好的定位效果，因此，本文的工作主要是基于指紋定位技術(shù)。

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

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

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

2 修正算法

2.1 感知概率

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

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

(1)

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

2.2 修正k-NN算法

在離線訓(xùn)練階段，采集的樣本存儲(chǔ)為指紋數(shù)據(jù)庫，在線定位階段，將采集到的信號(hào)強(qiáng)度信息與指紋數(shù)據(jù)庫中的指紋信息進(jìn)行匹配，對(duì)每一個(gè)RP點(diǎn)，相應(yīng)的歐氏距離定義為：

(2)

式(2)中，S=(s1,s2,…,sn)為實(shí)測(cè)信號(hào)向量，Ri=(r1,r2,…,rn)為指紋庫中存儲(chǔ)的第i個(gè)RP的指紋信息。

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

(3)

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

k-NN算法通過選擇與實(shí)時(shí)測(cè)量位置距離最近的k個(gè)RP點(diǎn)，并計(jì)算出這k個(gè)RP點(diǎn)對(duì)應(yīng)坐標(biāo)的均值，即為實(shí)時(shí)測(cè)量位置的估計(jì)坐標(biāo)：

(4)

式(4)，中(xi,yi)'=(xt,yt)為與實(shí)時(shí)測(cè)量位置距離最近的K個(gè)RP點(diǎn)的坐標(biāo)，t為RP點(diǎn)由歐氏距離從小到大排列時(shí)對(duì)應(yīng)的前K個(gè)RP點(diǎn)的序號(hào)為

(5)

2.3 修正最大似然概率算法

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

對(duì)于概率型算法，把實(shí)測(cè)RSS與指紋庫中指紋的匹配過程看成概率估計(jì)問題，則最大后驗(yàn)概率分布可以描述為：

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

(6)

式(6)中,ω1,ω2,ω3,…,ωm為離線訓(xùn)練階段中m個(gè)RP的位置信息，RSS為在線測(cè)量階段的接收信號(hào)強(qiáng)度。

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

(7)

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

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

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

(8)

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

(9)

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

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

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

(10)

則感知似然概率為：

(11)

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

(2)核密度估計(jì)

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

(12)

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

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

(13)

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

(14)

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

(15)

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

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

(16)

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

(17)

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

(18)

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

(19)

式(19)中，Sk為設(shè)備接收到的第k個(gè)AP的實(shí)時(shí)信號(hào)強(qiáng)度，C=-100 dbm為用來代替未能感知到的信號(hào)強(qiáng)度。

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

(20)

(21)

3 實(shí)驗(yàn)及算法性能分析

3.1 實(shí)驗(yàn)環(huán)境

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

圖1 試驗(yàn)區(qū)域

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

表1 指紋數(shù)據(jù)庫

3.2 實(shí)驗(yàn)結(jié)果與性能分析

3.2.1 感知概率

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

圖2 感知概率分布圖

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

3.2.2 修正k-NN算法

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

圖3 確定型算法誤差CDF圖

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

表2 定位誤差

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

3.2.3 修正ML算法

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

圖4 概率型算法誤差CDF圖

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

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

4 結(jié)論

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

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

[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] 鄒坤，修春娣，楊東凱.基于感知概率的室內(nèi)定位系統(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算法在室內(nèi)定位中的應(yīng)用研究[J].電子設(shè)計(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.