楊如民 陳 敏 余成波

(重慶理工大學(xué)遠(yuǎn)程測(cè)試與控制研究所 重慶 400054)

0 引 言

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

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

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

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

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

1 貝葉斯指紋定位

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

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

1.1 加權(quán)K近鄰算法[8]

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

(1)

(2)

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

(3)

(4)

(5)

式中：Di為第i個(gè)指紋點(diǎn)與待測(cè)點(diǎn)距離；Di+1為第i+1個(gè)指紋點(diǎn)與待測(cè)點(diǎn)距離。

1.2 貝葉斯概率算法[11]

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

(6)

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

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

(7)

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

(a) 待測(cè)點(diǎn)與接入點(diǎn)距離為1 m時(shí)

(8)

(9)

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

算法1貝葉斯概率算法

輸入：指紋庫(kù)中m個(gè)RP接收到的AP實(shí)測(cè)信號(hào)S和位置信息(xi,yi)，移動(dòng)終端接收到的AP實(shí)測(cè)信號(hào)Sk。

Fori=1：m

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

(2) 計(jì)算任意一個(gè)RP對(duì)應(yīng)位置信息的權(quán)值系數(shù)P(Li/S)。

End

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

針對(duì)貝葉斯概率算法在估算最終位置時(shí)需要計(jì)算每一個(gè)RP對(duì)應(yīng)的P(Li/S)后驗(yàn)概率，導(dǎo)致運(yùn)算量大兼定位時(shí)效性較差的問(wèn)題，本文提出一種貝葉斯概率優(yōu)化算法，融合WKNN和貝葉斯概率算法。

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

(10)

式中：q=1時(shí)表示絕對(duì)距離公式，q=2時(shí)表示歐氏距離公式[15]。本文選擇q=2來(lái)表示待測(cè)點(diǎn)與第i個(gè)RP的距離，Di值越小表示兩者之間的相似程度越大。

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

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

輸入：指紋庫(kù)中m個(gè)RP接收到的AP實(shí)測(cè)信號(hào)S和位置信息(xi,yi)，移動(dòng)終端接收到的AP實(shí)測(cè)信號(hào)Sk。

Fori=1：m

(1) 計(jì)算待測(cè)點(diǎn)與各個(gè)RP歐氏距離公式。

(2) 按照距離大小升序排序選擇前t個(gè)Dk對(duì)應(yīng)的實(shí)測(cè)信號(hào)Sk與Lk。

End

Fori=1：m

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

(2) 計(jì)算前t-1個(gè)RP對(duì)應(yīng)位置信息的權(quán)值系數(shù)P(Li/S)。

End

3 實(shí) 驗(yàn)

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

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

圖4 AP接入點(diǎn)“距離-損耗”折線圖

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

圖5 32 m×10 m實(shí)驗(yàn)區(qū)域圖

構(gòu)建指紋庫(kù)信息時(shí)，不僅需要記錄當(dāng)前位置接收來(lái)自每個(gè)AP接入點(diǎn)對(duì)應(yīng)的RSSI，而且需要記錄當(dāng)前二維位置坐標(biāo)(x,y)。在實(shí)際采集過(guò)程中由于從不同方向處采集四次，因此表1采集(13.8,9)處的指紋信息有4組。

表1 坐標(biāo)為(13.8,9)處參考點(diǎn)采集的指紋庫(kù)

3.2 靜止?fàn)顟B(tài)與運(yùn)動(dòng)狀態(tài)定位實(shí)驗(yàn)

為驗(yàn)證本文所提的貝葉斯概率優(yōu)化算法優(yōu)越性，實(shí)驗(yàn)將行人定位狀態(tài)分為靜止?fàn)顟B(tài)與運(yùn)動(dòng)狀態(tài)，同時(shí)在實(shí)驗(yàn)區(qū)域分別對(duì)每個(gè)狀態(tài)進(jìn)行了測(cè)試，兩種實(shí)驗(yàn)狀態(tài)測(cè)試具體步驟如下：

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

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

根據(jù)步驟(1)，分別測(cè)試出靜止?fàn)顟B(tài)下2個(gè)待測(cè)點(diǎn)的定位結(jié)果，如圖6和圖7所示。

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

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

在上述測(cè)試中，分別對(duì)兩個(gè)待測(cè)點(diǎn)的真實(shí)坐標(biāo)與各算法匹配的定位坐標(biāo)進(jìn)行比較，設(shè)備處于靜止?fàn)顟B(tài)下，貝葉斯概率優(yōu)化算法下的定位坐標(biāo)相比于WKNN、貝葉斯概率算法更接近真實(shí)坐標(biāo)且未存在較大偏差，穩(wěn)定性較強(qiáng)。

根據(jù)步驟(2)，測(cè)試出運(yùn)動(dòng)狀態(tài)下的定位路徑對(duì)比圖，如圖8所示。

圖8 運(yùn)動(dòng)狀態(tài)下的定位路徑圖

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

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

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

3.3 實(shí)驗(yàn)結(jié)果比較

(11)

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

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

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

表2 算法定位精度與實(shí)時(shí)性的比較

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

4 結(jié) 語(yǔ)

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