基于貝葉斯概率優(yōu)化的Wi-Fi室內(nèi)定位算法

楊如民 陳 敏 余成波

(重慶理工大學遠程測試與控制研究所 重慶 400054)

0 引 言

隨著無線電通信技術、移動互聯(lián)網(wǎng)技術的發(fā)展，移動終端智能化水平的提升，基于位置的服務正逐漸成為各行各業(yè)和現(xiàn)實生活的日常需求，對室內(nèi)移動用戶的定位技術也提出更高的要求。由于室內(nèi)復雜的空間架構，各種辦公設施及人員的遮擋阻礙，使得以無線電信號為主的各種定位系統(tǒng)在室內(nèi)環(huán)境下的定位精度變差。當前主流的定位技術，如超寬帶無線電(Ultra Wide Band，UWB)、Wi-Fi、藍牙、射頻識別(Radio Frequency Identification，RFID)和紅外線等技術中，各自有其局限性。譬如：超寬帶無線電的范圍覆蓋太小，定位成本較高且智能終端暫時不支持該技術；藍牙定位技術需要預先配置大量信標節(jié)點，易受噪聲信號影響，傳輸距離短；射頻識別技術作用距離短，抗干擾性差，定位成本較高；紅外線定位技術易受環(huán)境干擾定位效果差。相比而言，Wi-Fi定位技術因其無須增加額外的發(fā)射基站，且覆蓋范圍廣[1]，無疑是最簡單快捷、方便而經(jīng)濟的室內(nèi)定位技術。

一般而言，定位技術采用的基本方法包括三邊測量、三角測量和信號強度測量[2]?？紤]到室內(nèi)環(huán)境復雜性導致的非視距[3]和多徑傳輸?shù)葐栴}，測量時間和測量角度均會產(chǎn)生較大的偏差，因而室內(nèi)Wi-Fi定位技術采用了最簡單易行、基于信號強度測量(Received Signal Strength Indication，RSSI)的定位算法，通過離線階段預先建立的Wi-Fi信號強度指紋庫，與移動終端在線測量所得到的實時信號強度進行匹配，從而對移動終端進行在線定位。目前，基于Wi-Fi信號指紋匹配的定位技術，仍然存在定位欠佳的問題，主要原因除了前面提到的人體遮擋、非視距、多徑傳輸影響等因素外，還存在著當需要進行匹配的位置空間較大時，離線指紋庫存儲的指紋信息隨之增多，導致運算量增加從而影響定位時間。

文獻[4]提出一種基于主成分分析結(jié)合加權貝葉斯的Wi-Fi室內(nèi)定位算法，對離線指紋庫進行去相關性、降維處理；匹配定位階段采用加權貝葉斯算法估算待測點位置，提高定位精度但大大增加運算時間。文獻[5]提出一種新的基于方差的指紋距離調(diào)整算法，根據(jù)當前的位置變化，不同的置信度對應不同的Wi-Fi接入點，該算法提高室內(nèi)定位精度，但在運行期間，隨機存儲器和只讀存儲器占比較大，計算成本較高。文獻[6]使用改進的KNN算法篩選出若干個采樣點，再使用樸素貝葉斯算法確定待測點最終位置，該算法將室內(nèi)定位精確度提高16.7%。

上述研究表明，提高指紋匹配定位精度有兩個有效技術措施：對離線指紋庫進行去相關及降維；利用移動終端在線測量獲得后驗概率對匹配過程進行貝葉斯加權估計，但是隨之產(chǎn)生了運算時間增加過大的問題。

為了綜合考慮定位精度與計算執(zhí)行時間問題，本文提出一種融合貝葉斯估計與加權K近鄰算法的貝葉斯概率優(yōu)化算法，在提高定位精度的同時，也能相應地降低計算時間代價。

1 貝葉斯指紋定位

貝葉斯指紋定位是在離線階段[7]建立指紋庫的基礎上，先對指紋庫中任意一個指紋信息在接收到RSSI條件下，該指紋位置發(fā)生的后驗概率進行求解。再通過對指紋庫所有指紋信息發(fā)生的后驗概率與其指紋位置一一對應相乘求和。最后得到結(jié)果即為進行貝葉斯概率算法實現(xiàn)的位置估計。具體實現(xiàn)原理如圖1所示。

圖1 貝葉斯指紋定位原理圖

1.1 加權K近鄰算法[8]

傳統(tǒng)加權K近鄰算法(Weighted K-Nearest Neighborhood，WKNN)是K近鄰法[9](K-Nearest Neighborhood，KNN)的進一步優(yōu)化。考慮到所選K個指紋與待測點距離值不盡相同，而采取KNN求取K個指紋對應位置信息平均值作為待測點位置信息有所欠缺。WKNN依據(jù)K個指紋與待測點距離值Di作為選取K個指紋的位置信息(xi,yi)的權值系數(shù)[10]，通過式(1)求出權值系數(shù)wi，通過式(2)求解出待測點位置。

(1)

(2)

針對Wi-Fi指紋匹配使用傳統(tǒng)WKNN算法定位精度低的情況，本文對傳統(tǒng)WKNN算法中位置信息權值系數(shù)進行改進，通過式(3)和式(4)求出權值系數(shù)wi1和wi2，通過式(5)求解出待測點位置信息。

(3)

(4)

(5)

式中：Di為第i個指紋點與待測點距離；Di+1為第i+1個指紋點與待測點距離。

1.2 貝葉斯概率算法[11]

指紋庫中第i個參考點(Reference Point，RP)接收到接入點(Access Point，AP)RSSI信號為Si=[Si1,Si2,…,Sij,…,Sin],j=1,2，…,n，其中：RP個數(shù)為m，AP個數(shù)為n。構建指紋庫Si=[Si1,Si2,…,Sij,…,Sin],i=1,2，…,m，其中第i個參考點的位置信息Li=(xi,yi)，通過式(6)計算出實測信號在第i個參考點出現(xiàn)的后驗概率[12]P(Li/S)。

(6)

式中：P(S/Li)為第i個參考點在該位置處接收到實測信號S的條件概率；P(Li)為第i個參考點位置信息發(fā)生的概率事件，一般認為出現(xiàn)在任意一個參考點的位置信息概率相等，即服從均勻分布P(Li)=1/m。假設n個接入點在第i個參考點發(fā)出的實測信號S均相互獨立[13]且互不干擾，即：

P(S/Li)=P(s1/Li)P(s2/Li)P(sn/Li)

(7)

從概率統(tǒng)計的相關理論可以得出，任意第i個待測點接收到第j個接入點的實測信號sj均滿足高斯正態(tài)分布[14]，通過在實驗環(huán)境中選擇任意一個待測點與接入點進行100次測試驗證，如圖2所示。

(a) 待測點與接入點距離為1 m時

(8)

(9)

貝葉斯概率算法流程如算法1所示。

算法1貝葉斯概率算法

輸入：指紋庫中m個RP接收到的AP實測信號S和位置信息(xi,yi)，移動終端接收到的AP實測信號Sk。

Fori=1：m

(1) 計算任意一個RP的P(S/Li)。

(2) 計算任意一個RP對應位置信息的權值系數(shù)P(Li/S)。

End

2 貝葉斯概率優(yōu)化算法

針對貝葉斯概率算法在估算最終位置時需要計算每一個RP對應的P(Li/S)后驗概率，導致運算量大兼定位時效性較差的問題，本文提出一種貝葉斯概率優(yōu)化算法，融合WKNN和貝葉斯概率算法。

在離線建庫階段，指紋庫中m個RP的AP實測信號S集合為[S1,S2,…,Sm]T，其中第i個RP的數(shù)據(jù)集合為{(Si1,Si2,…,Sim),(xi,yi)},(Si1,Si2,…,Sim)表示第i個RP接收到的AP實測信號S，(xi,yi)表示第i個RP的當前位置Li。匹配定位階段，第k個待測點RSSI信號記為Sk=[Sk1,Sk2,…,Skj,…,Skn],k∈N*，可通過式(10)計算待測點與指紋庫中各個RP的距離。

(10)

式中：q=1時表示絕對距離公式，q=2時表示歐氏距離公式[15]。本文選擇q=2來表示待測點與第i個RP的距離，Di值越小表示兩者之間的相似程度越大。

圖3 貝葉斯概率優(yōu)化算法流程圖

算法2貝葉斯概率優(yōu)化算法

輸入：指紋庫中m個RP接收到的AP實測信號S和位置信息(xi,yi)，移動終端接收到的AP實測信號Sk。

Fori=1：m

(1) 計算待測點與各個RP歐氏距離公式。

(2) 按照距離大小升序排序選擇前t個Dk對應的實測信號Sk與Lk。

End

Fori=1：m

(1) 計算前t-1個RP的P(S/Li)。

(2) 計算前t-1個RP對應位置信息的權值系數(shù)P(Li/S)。

End

3 實 驗

3.1 實驗環(huán)境布置

本文選取建筑面積為32 m×10 m的一層典型辦公環(huán)境，其中包括辦公室和走廊。本實驗使用TP-LINK無線路由器作為AP接入點，華為P10手機終端作為RP參考點采集器與后續(xù)進行測試的待測點。為了確保實驗區(qū)域內(nèi)RP參考點采集的來自各個AP接入點的RSSI序列有差異，實驗測試各個AP節(jié)點的信號“距離-損耗”情況。如圖4所示，AP節(jié)點的距離在8～10 m范圍內(nèi)實測信號強度值趨于平緩，但結(jié)合實際成本問題，布置10 m以內(nèi)即可。

圖4 AP接入點“距離-損耗”折線圖

按照1 m×1 m規(guī)格將實驗區(qū)域劃分成若干個正方形網(wǎng)格，將每一個正方形網(wǎng)格頂點作為RP參考點并從左往右、從下向上依次標注好序號，一共標注363個RP參考點，并且在每個RP參考點不同方向處采集了四次，指紋庫指紋數(shù)量共1 452個，AP接入點布置如圖5所示。

圖5 32 m×10 m實驗區(qū)域圖

構建指紋庫信息時，不僅需要記錄當前位置接收來自每個AP接入點對應的RSSI，而且需要記錄當前二維位置坐標(x,y)。在實際采集過程中由于從不同方向處采集四次，因此表1采集(13.8,9)處的指紋信息有4組。

表1 坐標為(13.8,9)處參考點采集的指紋庫

3.2 靜止狀態(tài)與運動狀態(tài)定位實驗

為驗證本文所提的貝葉斯概率優(yōu)化算法優(yōu)越性，實驗將行人定位狀態(tài)分為靜止狀態(tài)與運動狀態(tài)，同時在實驗區(qū)域分別對每個狀態(tài)進行了測試，兩種實驗狀態(tài)測試具體步驟如下：

(1) 實驗室選擇2個待測點(tx1,ty1)和(tx2,ty2)，在設備處于靜止狀態(tài)下每個點測量15組定位結(jié)果，并記錄下真實坐標與采用傳統(tǒng)WKNN算法、貝葉斯概率算法、貝葉斯概率優(yōu)化算法下的定位坐標。

(2) 行人處于運動狀態(tài)下，按照設定的真實路徑行走，并記錄下真實路徑與采用傳統(tǒng)WKNN算法、貝葉斯概率算法、貝葉斯概率優(yōu)化算法下的定位路徑。

根據(jù)步驟(1)，分別測試出靜止狀態(tài)下2個待測點的定位結(jié)果，如圖6和圖7所示。

(a) WKNN與貝葉斯概率算法

(a) WKNN與貝葉斯概率算法

在上述測試中，分別對兩個待測點的真實坐標與各算法匹配的定位坐標進行比較，設備處于靜止狀態(tài)下，貝葉斯概率優(yōu)化算法下的定位坐標相比于WKNN、貝葉斯概率算法更接近真實坐標且未存在較大偏差，穩(wěn)定性較強。

根據(jù)步驟(2)，測試出運動狀態(tài)下的定位路徑對比圖，如圖8所示。

圖8 運動狀態(tài)下的定位路徑圖

當行人手持設備處于運動狀態(tài)下，貝葉斯概率優(yōu)化算法下的定位路徑相比于WKNN波動較小，雖相比貝葉斯概率算法定位穩(wěn)定性稍差，但整體定位路徑相比于WKNN、貝葉斯概率算法更貼近真實路徑。

智能手機端安裝App后，將指紋信息依次錄入指紋庫，同時將室內(nèi)地圖導入App中，如圖9所示。

圖9 數(shù)據(jù)庫采集與室內(nèi)定位測試

3.3 實驗結(jié)果比較

(11)

本文選取實驗區(qū)域內(nèi)的100個獨立且互不相關待測點進行實驗。根據(jù)實驗計算出平均定位誤差。圖10為WNNN、貝葉斯概率算法和貝葉斯概率優(yōu)化算法的累積分布函數(shù)情況。

圖10 定位結(jié)果誤差曲線

在1 m內(nèi)WKNN算法定位精度可達57%，貝葉斯概率優(yōu)化算法定位精度可達73%；在2 m內(nèi)WKNN定位精度可達88%，貝葉斯概率優(yōu)化算法定位精度可達92%。表2為算法定位精度與實時性的比較。

表2 算法定位精度與實時性的比較

對表2進行分析：平均定位精度方面，貝葉斯概率優(yōu)化算法相對于WKNN算法、貝葉斯概率算法分別提高21.49%、18.41%；平均運行時間方面，貝葉斯概率優(yōu)化算法相對于貝葉斯概率算法減少約61%；定位穩(wěn)定性方面，貝葉斯概率優(yōu)化算法雖相對于WKNN算法有所增強，但相對于貝葉斯概率算法穩(wěn)定性仍需加強。綜上所述，本文所提貝葉斯概率優(yōu)化算法相比當前已有算法在定位精度、穩(wěn)定性和實時性方面都有一定的改善效果。

4 結(jié) 語

本文提出一種貝葉斯概率優(yōu)化算法，融合貝葉斯概率算法與WKNN算法，相對于傳統(tǒng)WKNN、貝葉斯概率算法具有顯著優(yōu)勢。實驗結(jié)果顯示，本文算法相比于傳統(tǒng)WKNN平均定位精度提高約21.49%，運行穩(wěn)定性也有所加強。但本文算法仍有值得改進的地方,譬如平均運行時間相對于WKNN算法僅增加約0.54%。未來將進一步改進該算法的實時性與穩(wěn)定性。