一種改進(jìn)的基于貝葉斯的位置指紋算法

徐瀟瀟， 謝林柏 ， 彭 力

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122)

隨著移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展以及智能移動(dòng)終端的普及，基于LBS 的服務(wù)在越來越多的領(lǐng)域得到了應(yīng)用。目前，GPS 在室外空曠區(qū)域進(jìn)行定位時(shí)可以獲得很好的效果;然而，在室內(nèi)環(huán)境下，由于建筑結(jié)構(gòu)的復(fù)雜性以及人員走動(dòng)等因素的存在，GPS 往往不能取得較好的定位效果，甚至存在著無法定位的情況［1］。這時(shí)，就需要一種能在室內(nèi)進(jìn)行定位的方法，以滿足人們?cè)谑覂?nèi)環(huán)境下對(duì)位置信息的需求。

基于WiFi 信號(hào)強(qiáng)度的定位算法由于其成本低、可擴(kuò)展性強(qiáng)等因素而成為了近些年的研究熱點(diǎn)。與TOA，TDOA 以及AOA 等方法相比，該方法不需要添加額外的設(shè)備［2］，利用現(xiàn)有的WiFi 以及智能移動(dòng)終端，再配合一個(gè)APP，即可實(shí)現(xiàn)定位，成本較低。基于信號(hào)強(qiáng)度的定位方法分為信號(hào)傳播模型定位以及位置指紋定位。其中，位置指紋算法又分為確定性方法與概率性方法。確定性方法通過計(jì)算信號(hào)特征之間的歐氏距離選取最接近的參考點(diǎn)，該方法較為簡單，但是精確度不夠高;而概率性方法則是通過計(jì)算出參考點(diǎn)的后驗(yàn)概率來進(jìn)行定位，該方法具有較高的精度，但是計(jì)算比較復(fù)雜［3］。

文中提出了一種改進(jìn)的基于貝葉斯的位置指紋算法。通過選取固定的若干個(gè)參考AP，防止突然加入的AP 對(duì)定位結(jié)果產(chǎn)生的影響。在對(duì)采樣數(shù)據(jù)進(jìn)行處理時(shí)，采用高斯概率分布描述取代離散概率描述。在線階段，通過實(shí)測信號(hào)特征中強(qiáng)度最大的AP 判斷并去除一部分不可能的參考節(jié)點(diǎn)，在不影響定位精度的情況下減小計(jì)算量，并通過加權(quán)處理進(jìn)一步較小誤差。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法能減小定位算法的計(jì)算量，同時(shí)有效地提高了定位精度。

1 位置指紋算法的基本原理

位置指紋定位算法通常由兩個(gè)階段構(gòu)成:離線階段和在線階段［4］。離線階段，又稱訓(xùn)練階段，其主要工作是在定位區(qū)域中設(shè)定若干個(gè)參考點(diǎn)，并在每個(gè)參考點(diǎn)采集相應(yīng)的指紋信息。通常每個(gè)參考點(diǎn)的指紋信息由該點(diǎn)采集到的各個(gè)AP 的信號(hào)強(qiáng)度信息和該點(diǎn)的物理坐標(biāo)構(gòu)成，參考點(diǎn)一般設(shè)置為網(wǎng)格狀分布。最終，將每個(gè)參考點(diǎn)的指紋信息錄入數(shù)據(jù)庫，該數(shù)據(jù)庫稱為Radio Map。通常選取的參考點(diǎn)越多，即網(wǎng)格密度越大，采樣次數(shù)越多，對(duì)定位精度的提高越是有利［5］，然而，考慮到工作量的問題，需在可接受的工作量范圍內(nèi)盡可能地提高定位的精度。在線階段，又稱定位階段，其主要工作是利用智能移動(dòng)終端在待定位點(diǎn)采集AP 的信號(hào)特征信息，再通過匹配算法將其與Radio Map 中的指紋信息進(jìn)行對(duì)比，從而計(jì)算出待定位點(diǎn)的物理位置。

根據(jù)Radio Map 中指紋信息記錄形式的不同，通常將定位方法分為確定性方法和概率性方法［6］。其中，確定性方法將AP 在一段時(shí)間內(nèi)的信號(hào)強(qiáng)度平均值記錄到指紋信息中，然后由最近鄰法(NN)、k 最近鄰法(KNN)或者加權(quán)的k 最近鄰法(WKNN)通過計(jì)算曼哈頓距離或者歐氏距離推算出待定位點(diǎn)的物理坐標(biāo)。距離越小，表示兩個(gè)指紋的相似度越高。概率性方法則是將AP 的離散采樣樣本或者信號(hào)強(qiáng)度均值以及方差等信息保存在指紋信息中。利用貝葉斯定理，計(jì)算在每個(gè)參考點(diǎn)的后驗(yàn)概率，選取后驗(yàn)概率最小的一個(gè)或者若干個(gè)參考節(jié)點(diǎn)，從而計(jì)算出待定位點(diǎn)的物理坐標(biāo)。概率性方法相比確定性方法的優(yōu)勢在于該方法可以有效地去除采樣信號(hào)中較大誤差的影響，去噪性優(yōu)勢明顯。

Horus 系統(tǒng)首次實(shí)現(xiàn)了基于概率的定位解決方案［7］。利用貝葉斯法，通過計(jì)算待定位點(diǎn)的后驗(yàn)概率估計(jì)該點(diǎn)的物理坐標(biāo)［8］。假設(shè)定位區(qū)域所有參考點(diǎn)的位置集合為

式中:n 為定位區(qū)域內(nèi)參考點(diǎn)的個(gè)數(shù);li= {xi，yi}，為第i 個(gè)參考點(diǎn)對(duì)應(yīng)的物理坐標(biāo)。與L 一一對(duì)應(yīng)的位置指紋集合為

其中

式中:rssiij為第i 個(gè)參考點(diǎn)接收到的來自第j 個(gè)AP的信號(hào)強(qiáng)度值;m 為參考AP 的個(gè)數(shù)。

在線階段，令待定位點(diǎn)測得的指紋信息為A，A中包含m 個(gè)AP 的信號(hào)強(qiáng)度信息，則指紋A = {a1，a2，…，am}在各個(gè)參考點(diǎn)的后驗(yàn)概率為P(li| A)。根據(jù)貝葉斯定理，可將后驗(yàn)概率的公式轉(zhuǎn)化為

其中:P(A| li)為在已知位置li處的RSSI 指紋為A的條件概率;P(li)為在定位區(qū)域內(nèi)li位置上的先驗(yàn)概率。由于待定位點(diǎn)在定位區(qū)域內(nèi)任意一點(diǎn)出現(xiàn)的可能性都一樣，即P(li)在任意位置出現(xiàn)的概率均相同，所以將其看成一個(gè)常量。P(A)對(duì)于所有位置而言為常數(shù)。所以式(1)可以轉(zhuǎn)化為

由于各個(gè)AP 之間相互獨(dú)立［9］，因此，P(A | li)可采用聯(lián)合概率分布函數(shù)描述為如下形式

即

所以，將問題轉(zhuǎn)化為求P(A| li)值最大時(shí)對(duì)應(yīng)的參考點(diǎn)li。

2 改進(jìn)的位置指紋算法

2.1 特征AP 的選取

由式(4)可知，若在定位區(qū)域內(nèi)加入了某一AP，則在定位階段，A 中會(huì)增加一個(gè)該AP 的信號(hào)強(qiáng)度信息。使用式(4)進(jìn)行后驗(yàn)概率計(jì)算時(shí)，則會(huì)出現(xiàn)P(A| li)= 0 的情況，從而導(dǎo)致無法定位。若某一參考AP 在定位階段發(fā)生斷電等情況，從而導(dǎo)致無法獲取該AP 的信號(hào)強(qiáng)度值，則可以繼續(xù)完成定位，而不會(huì)導(dǎo)致無法定位的情況發(fā)生。為了避免不相關(guān)AP對(duì)定位結(jié)果的影響，參考AP 應(yīng)選取若干個(gè)固定的AP。

改進(jìn)的具體實(shí)現(xiàn)如下:共選取m 個(gè)固定參考AP，即式(1)中的m 為固定值。在參考點(diǎn)進(jìn)行采樣時(shí)，分別獲取這m 個(gè)參考AP 的信號(hào)強(qiáng)度特征信息。若在某次采樣中并未搜索到某個(gè)參考AP，則給其賦值搜索到的AP 中信號(hào)強(qiáng)度值最小的值減去3 dBm，即rssimin－3 dBm，確保每個(gè)參考位置的指紋信息均包含了所有參考AP 的信息。在線階段，考慮到信號(hào)較強(qiáng)的AP 往往較為穩(wěn)定，能較好地反映該位置的信號(hào)分布情況，故選取指紋信息中信號(hào)強(qiáng)度較大的t(t ＜m)個(gè)AP 計(jì)算后驗(yàn)概率，則公式(4)可以寫為

上述改進(jìn)可有效去除新加入的AP 對(duì)定位結(jié)果的影響，用于計(jì)算后驗(yàn)概率的AP 信息則能較好地反映該位置的無線信號(hào)分布特征。

2.2 離線階段信號(hào)特征的描述

若采用離散概率法，則需要較大的存儲(chǔ)空間［10］。由于室內(nèi)環(huán)境較為復(fù)雜，而且人員走動(dòng)頻繁，所以接收信號(hào)強(qiáng)度存在一定的波動(dòng);同一位置同一設(shè)備在不同時(shí)刻測得的數(shù)據(jù)也往往不一樣，所以導(dǎo)致在線階段測得的信號(hào)值并未在離線采樣樣本中出現(xiàn)，最終出現(xiàn)概率為0 的情況。這是由式(5)右邊存在單個(gè)概率為0 導(dǎo)致的，因而無法獲得定位結(jié)果。

針對(duì)上述情況，文中在離線階段記錄一定量的采樣樣本，采用基于分布的概率法代替離散概率法，這樣不僅可以節(jié)省存儲(chǔ)空間，還能避免后驗(yàn)概率為0 的情況的出現(xiàn)。同一位置的WiFi 信號(hào)強(qiáng)度值雖然存在著不穩(wěn)定的現(xiàn)象，但是總體在某一個(gè)值的附近波動(dòng)，故同一位置的信號(hào)強(qiáng)度分布可用高斯概率分布描述，其概率密度函數(shù)為

其中，x 為實(shí)際測得的信號(hào)強(qiáng)度值;μ 和σ 分別為函數(shù)的均值與標(biāo)準(zhǔn)差。由式(6)可得，出現(xiàn)強(qiáng)度值為r的概率為

考慮到采樣時(shí)初始的10 s 內(nèi)信號(hào)波動(dòng)較大［11］，之后便相對(duì)趨于穩(wěn)定，所以文中在離線階段忽略前10 s 的采樣值。此外，WiFi 的信號(hào)直方圖存在一定的偏左性［12］，這是由于WiFi 在某一時(shí)刻由于較為嚴(yán)重的傳播損耗造成的。若能將這些較大誤差去除，則可以更加精確地使用高斯分布描述信號(hào)強(qiáng)度分布情況。文中利用3σ 準(zhǔn)則去除誤差較大的數(shù)據(jù)。令終端設(shè)備在某一位置對(duì)某一AP 按照固定頻率進(jìn)行q 次采樣，采樣獲得的信號(hào)強(qiáng)度值集合為{r1，r2，r3，…，rq}。由貝塞爾公式可得采樣樣本的均方根誤差為

若| vi|≥3σ，則其對(duì)應(yīng)的采樣值ri應(yīng)被視為較大誤差而剔除。對(duì)剩余的數(shù)據(jù)使用高斯分布進(jìn)行描述，并將指紋信息錄入Radio Map。

2.3 在線階段匹配算法的改進(jìn)

貝葉斯算法雖然精度較高，但是相比KNN 等確定性方法而言計(jì)算較為復(fù)雜。針對(duì)這一問題，文中通過去除一部分不可能作為定位結(jié)果的參考點(diǎn)以減小搜索范圍，在不影響定位精度的前提下盡可能地減小計(jì)算量。具體實(shí)現(xiàn)為:選取在線階段在待定位點(diǎn)實(shí)測所得的信號(hào)強(qiáng)度最強(qiáng)的AP，將Radio Map中信號(hào)強(qiáng)度最強(qiáng)的兩個(gè)AP 為該AP 的指紋信息作為備選參考點(diǎn)，縮小計(jì)算的范圍。

進(jìn)行后驗(yàn)概率的計(jì)算后，選取計(jì)算結(jié)果最大的k 個(gè)參考點(diǎn)，然后進(jìn)行加權(quán)處理。待定位位置的坐標(biāo)可表示為

其中，wi為權(quán)重，該值取決于參考點(diǎn)后驗(yàn)概率的大小。后驗(yàn)概率越大，則該參考點(diǎn)對(duì)定位結(jié)果的影響最大。wi的計(jì)算公式為

其中，Pi為后驗(yàn)概率。

3 算法測試

為了驗(yàn)證改進(jìn)算法的有效性，分別對(duì)改進(jìn)前后的算法進(jìn)行定位測試。針對(duì)離線階段的采樣樣本，改進(jìn)前的算法直接對(duì)若干次采樣樣本進(jìn)行計(jì)算，求得樣本的均值與方差;而改進(jìn)后的算法首先利用3σ準(zhǔn)則去除采樣樣本中的較大誤差，然后再對(duì)剩余的數(shù)據(jù)求均值與方差。在線階段，改進(jìn)前的算法直接采用后驗(yàn)概率最大的參考點(diǎn)作為定位結(jié)果;而改進(jìn)后的算法則選取3 個(gè)后驗(yàn)概率最大的參考點(diǎn)，并分別考慮了各個(gè)參考點(diǎn)對(duì)定位結(jié)果的不同貢獻(xiàn)，最終得出定位結(jié)果。

實(shí)驗(yàn)中智能移動(dòng)終端采用三星Galaxy S4，該終端采用的是Android 系統(tǒng)，具備WiFi 功能。為了采集AP 的信號(hào)強(qiáng)度，需要在終端上設(shè)計(jì)一個(gè)APP。該APP 的開發(fā)涉及到以下的接口和類:ScanResult，WifiInfo 和WifiManager。主要代碼如下:

public void onClick(View v){

wifiAdmin.startScan();

mWifiList = wifiAdmin.getWifiList();

LevelComparator comp = new Level-Comparator();

Collections.sort(mWifiList，comp);

if (mWifiList != null){

for (int i = 0;i ＜mWifiList.size();i++){

mScanResult = mWifiList.get(i);

if (

mScanResult.BSSID.equals( "00:87:36:1e:e9:19")||

mScanResult.BSSID.equals( "00:24:b2:1e:a4:88")||

mScanResult.BSSID.equals( "00:1f:33:b4:b1:4c")||

mScanResult.BSSID.equals( "14:e6:e4:69:f2:42")||

mScanResult.BSSID.equals( "00:24:b2:a0:33:16")||

mScanResult.BSSID.equals( "94:0c:6d:35:80:ea")){

sb = sb.append(mScanResult.BSSID + " ")

.append(mScanResult.SSID + " ")

.append(mScanResult.capabilities + " ")

.append(mScanResult.frequency + " ")

.append(mScanResult.level + " ");

arrayList.add(mScanResult.BSSID);

arrayList.add(mScanResult.level);

}

}

}

}

離線階段，每個(gè)參考點(diǎn)進(jìn)行50 次采樣，即式(8)中的q 取50，采樣間隔為2 s。在線階段，考慮到采樣時(shí)間不宜過長，所以進(jìn)行5 次采樣，時(shí)間間隔為2 s，取中間值作為采樣結(jié)果。定位區(qū)域選擇江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院C 區(qū)516 室附近。定位區(qū)域大小為12 ×18 m，采用網(wǎng)格布局，每隔2 m 設(shè)置一個(gè)參考點(diǎn)，共選取70 個(gè)參考點(diǎn)。離線階段，選取6 個(gè)固定參考AP，即式(1)中的m =6。匹配階段，使用實(shí)測的6個(gè)AP 中信號(hào)最強(qiáng)的3 個(gè)進(jìn)行后驗(yàn)概率的計(jì)算，即式(5)中的t = 3。式(9)中的k = 3，即選取后驗(yàn)概率最大的3 個(gè)參考點(diǎn)進(jìn)行加權(quán)處理。在完成離線階段與在線階段的數(shù)據(jù)采集后，使用Matlab 對(duì)改進(jìn)前后的算法進(jìn)行仿真。測試中，選取20 個(gè)測試點(diǎn)進(jìn)行定位測試。測試結(jié)果見表1 所示。

表1 測試結(jié)果Fig.1 Results of the test

通過實(shí)際測試可得，采用改進(jìn)前的算法進(jìn)行定位，平均誤差為2.568 0 m;采用改進(jìn)后的算法，平均誤差為1.407 0 m。定位精度提高了45.21%，計(jì)算量平均減少了64.93%。

4 結(jié) 語

文中針對(duì)傳統(tǒng)的基于貝葉斯的位置指紋算法存在著后驗(yàn)概率可能為0 以及計(jì)算量較大等問題，對(duì)算法進(jìn)行了改進(jìn)。離線階段，首先選取固定的AP作為指紋信息來源，排除了突然加入的AP 可能對(duì)定位造成的影響，進(jìn)而考慮到信號(hào)強(qiáng)度分布的偏左性，先利用3σ 準(zhǔn)則去除最小的一部分?jǐn)?shù)據(jù)，再對(duì)剩余數(shù)據(jù)采用高斯概率分布進(jìn)行描述，排除了后驗(yàn)概率可能為0 的情況。在線階段，通過判斷指紋信息中信號(hào)最強(qiáng)的AP，排除一部分不可能的參考節(jié)點(diǎn)，以此減小了計(jì)算量，同時(shí)對(duì)后驗(yàn)概率最大的3 個(gè)參考點(diǎn)進(jìn)行了加權(quán)處理。測試階段，首先利用Android 終端進(jìn)行WiFi 指紋信息的采集，最后將測得的數(shù)據(jù)在Matlab 平臺(tái)上進(jìn)行仿真測試，驗(yàn)證了改進(jìn)算法的有效性。

［1］LUO Jiayou，ZHAN Xingqun. Characterization of smart phone received signal strength indication for WLAN indoor positioning accuracy improvement［J］.Journal of Networks，2014，9(3):739-746.

［2］CHENG Jiantong，YANG Ling，LI Yong，et al. Seamless outdoor/indoor navigation with WIFI/GPS aided low cost inertial navigation system［J］.Physical Communication，2014，13:31-43.

［3］Eunchan K，Kim K. Distance estimation with weighted least squares for mobile beacon-based localization in wireless sensor networks［J］.IEEE Signal Processing Letters，2010，17(6):559-562.

［4］趙聘，陳建新.利用現(xiàn)有無線局域網(wǎng)進(jìn)行室內(nèi)定位算法研究［J］.信號(hào)處理，2014，30(11):1413-1418.

ZHAO Pin，CHEN Jianxin. A study on indoor localization algorithm using existing wireless local area network［J］. Journal of Signal Processing，2014，30(11):1413-1418.(in Chinese)

［5］張明華.基于WLAN 的室內(nèi)定位技術(shù)研究［D］.上海:上海交通大學(xué)，2009.

［6］王賽偉.基于位置指紋的WLAN 室內(nèi)定位方法研究［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2009.［7］徐偉.基于Android 手機(jī)的室內(nèi)定位技術(shù)研究與實(shí)現(xiàn)［D］.武漢:華中師范大學(xué)，2014.

［8］羅利.基于Android 的WIFI 室內(nèi)定位技術(shù)研究［D］.成都:西南交通大學(xué)，2014.

［9］楊萌，修春娣，鄒坤，等.一種基于感知概率的室內(nèi)定位匹配算法［J］.導(dǎo)航定位學(xué)報(bào)，2014，2(4):49-53，57.

YANG Meng，XIU Chundi，ZOU Kun，et al.A sensing probability-based matching algorithm for WiFi indoor positioning systems［J］.Journal of Navigation and Positioning，2014，2(4):49-53，57.(in Chinese)

［10］王忠民，陳振，潘春華.一種改進(jìn)的位置指紋智能手機(jī)室內(nèi)定位算法［J］.西安郵電大學(xué)學(xué)報(bào)，2014，19(1):17-20.

WANG Zhongmin，CHEN Zhen，PAN Chunhua.Improved fingerprinting algorithm for smart phone indoor positioning［J］.Jonrnal of Xi’an University of Posts and Telecommunications，2014，19(1):17-20.(in Chinese)

［11］孫善武，王楠，陳堅(jiān).一種改進(jìn)的基于信號(hào)強(qiáng)度的WLAN 定位方法［J］.計(jì)算機(jī)科學(xué)，2014，41(6):99-103.

SUN Shanwu，WANG Nan，CHEN Jian.Improved RSSI-based localization method using bounding-box algorithm in WLAN［J］.Computer Science，2014，41(6):99-103.(in Chinese)

［12］孫永亮.基于位置指紋的WLAN 室內(nèi)定位技術(shù)研究［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2014.