一種改進的基于貝葉斯的位置指紋算法

徐瀟瀟， 謝林柏 ， 彭 力

(江南大學 物聯網工程學院，江蘇 無錫214122)

隨著移動互聯網的高速發展以及智能移動終端的普及，基于LBS 的服務在越來越多的領域得到了應用。目前，GPS 在室外空曠區域進行定位時可以獲得很好的效果;然而，在室內環境下，由于建筑結構的復雜性以及人員走動等因素的存在，GPS 往往不能取得較好的定位效果，甚至存在著無法定位的情況［1］。這時，就需要一種能在室內進行定位的方法，以滿足人們在室內環境下對位置信息的需求。

基于WiFi 信號強度的定位算法由于其成本低、可擴展性強等因素而成為了近些年的研究熱點。與TOA，TDOA 以及AOA 等方法相比，該方法不需要添加額外的設備［2］，利用現有的WiFi 以及智能移動終端，再配合一個APP，即可實現定位，成本較低?；谛盘枏姸鹊亩ㄎ环椒ǚ譃樾盘杺鞑ツＰ投ㄎ灰约拔恢弥讣y定位。其中，位置指紋算法又分為確定性方法與概率性方法。確定性方法通過計算信號特征之間的歐氏距離選取最接近的參考點，該方法較為簡單，但是精確度不夠高;而概率性方法則是通過計算出參考點的后驗概率來進行定位，該方法具有較高的精度，但是計算比較復雜［3］。

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

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

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

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

Horus 系統首次實現了基于概率的定位解決方案［7］。利用貝葉斯法，通過計算待定位點的后驗概率估計該點的物理坐標［8］。假設定位區域所有參考點的位置集合為

式中:n 為定位區域內參考點的個數;li= {xi，yi}，為第i 個參考點對應的物理坐標。與L 一一對應的位置指紋集合為

其中

式中:rssiij為第i 個參考點接收到的來自第j 個AP的信號強度值;m 為參考AP 的個數。

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

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

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

即

所以，將問題轉化為求P(A| li)值最大時對應的參考點li。

2 改進的位置指紋算法

2.1 特征AP 的選取

由式(4)可知，若在定位區域內加入了某一AP，則在定位階段，A 中會增加一個該AP 的信號強度信息。使用式(4)進行后驗概率計算時，則會出現P(A| li)= 0 的情況，從而導致無法定位。若某一參考AP 在定位階段發生斷電等情況，從而導致無法獲取該AP 的信號強度值，則可以繼續完成定位，而不會導致無法定位的情況發生。為了避免不相關AP對定位結果的影響，參考AP 應選取若干個固定的AP。

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

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

2.2 離線階段信號特征的描述

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

針對上述情況，文中在離線階段記錄一定量的采樣樣本，采用基于分布的概率法代替離散概率法，這樣不僅可以節省存儲空間，還能避免后驗概率為0 的情況的出現。同一位置的WiFi 信號強度值雖然存在著不穩定的現象，但是總體在某一個值的附近波動，故同一位置的信號強度分布可用高斯概率分布描述，其概率密度函數為

其中，x 為實際測得的信號強度值;μ 和σ 分別為函數的均值與標準差。由式(6)可得，出現強度值為r的概率為

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

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

2.3 在線階段匹配算法的改進

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

進行后驗概率的計算后，選取計算結果最大的k 個參考點，然后進行加權處理。待定位位置的坐標可表示為

其中，wi為權重，該值取決于參考點后驗概率的大小。后驗概率越大，則該參考點對定位結果的影響最大。wi的計算公式為

其中，Pi為后驗概率。

3 算法測試

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

實驗中智能移動終端采用三星Galaxy S4，該終端采用的是Android 系統，具備WiFi 功能。為了采集AP 的信號強度，需要在終端上設計一個APP。該APP 的開發涉及到以下的接口和類: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);

}

}

}

}

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

表1 測試結果Fig.1 Results of the test

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

4 結 語

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

［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］趙聘，陳建新.利用現有無線局域網進行室內定位算法研究［J］.信號處理，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 的室內定位技術研究［D］.上海:上海交通大學，2009.

［6］王賽偉.基于位置指紋的WLAN 室內定位方法研究［D］.哈爾濱:哈爾濱工業大學，2009.［7］徐偉.基于Android 手機的室內定位技術研究與實現［D］.武漢:華中師范大學，2014.

［8］羅利.基于Android 的WIFI 室內定位技術研究［D］.成都:西南交通大學，2014.

［9］楊萌，修春娣，鄒坤，等.一種基于感知概率的室內定位匹配算法［J］.導航定位學報，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］.西安郵電大學學報，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］孫善武，王楠，陳堅.一種改進的基于信號強度的WLAN 定位方法［J］.計算機科學，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 室內定位技術研究［D］.哈爾濱:哈爾濱工業大學，2014.