基于空間特征分區和前點約束的WKNN 室內定位方法?

楊海峰 , 張勇波,2 , 黃裕梁 , 傅惠民

1(北京航空航天大學 小樣本技術研究中心,北京 100191)

2(北京航空航天大學 寧波創新研究院,浙江 寧波 315800)

在移動技術蓬勃發展的今天,基于位置信息的服務在人們的日常生活中發揮的作用愈加重要,市場對于高精度室內定位與導航服務等全新需求在不斷涌現[1,2].眾多公司已在各方面嘗試將室內定位服務拓展并進行大規模商業化運營[3,4].

截至目前,室內定位尚未形成一套統一、成熟的解決方案[5,6],但是基于不同應用場景與環境的各種室內定位方法不斷被提出,其中主要包括基于微電子機械系統(micro-electro-mechanical system,簡稱MEMS)的行人航跡遞推(pedestrian dead reckoning,簡稱PDR)算法[7,8]、利用無線射頻識別(radio frequency identification,簡稱RFID)技術的室內定位方法[9,10]、基于偽衛星網的室內GPS 定位方法[11,12]以及基于WiFi 信號的室內定位方法[13-18]等.然而,上述方法都面臨著各種各樣的問題:由于MEMS 的誤差累計,PDR 算法的定位精度會逐漸降低,以致完全失效;而RFID 定位和室內偽衛星定位則都需要鋪設大量外接設備以構建導航網絡,高昂的采購與部署成本限制了其在商業領域的大規模推廣應用.隨著移動互聯網的飛速發展,WiFi 網絡迅速普及,遍布現代社會各個角落,因此,基于WiFi 的室內定位技術以其部署成本低、易于推廣、精度較高等優勢,愈發引起研究人員的重視,逐漸成為室內定位技術的熱點[19].

在基于WiFi 信號的室內定位方法中,以指紋匹配法的位置估計精度更高、對復雜環境的適應能力更強,其包含離線采樣與在線匹配兩個階段.離線采樣階段是在目標區域內選取若干參考指紋點(reference point,簡稱RP),記錄其位置、接收到各無線接入點(access point,簡稱AP)的媒體訪問控制(media access control,簡稱MAC)地址以及相應的WiFi 信號強度值(received signal strength indication,簡稱RSSI)信息,通過對上述信息進行分析和處理,得到目標區域的指紋數據庫.在線匹配階段是用戶使用設備在當前位置接收到實時的測試數據(各AP的MAC 地址和相應的RSSI 值),將其與指紋數據庫進行匹配運算,再利用庫中已知的RP 位置對用戶當前位置進行估計[20].

由于指紋匹配法具有較大的發展優勢,研究人員對其開展了大量的研究.早期的Bahl 等人開發了信號空間最接近K鄰近法(K-nearest neighbors in signal space,簡稱KNN),該算法將篩選出的K個參考點坐標的算數平均值作為最終的位置估計[21].Lionell 等人則在KNN 算法的基礎上提出了加權K鄰近算法(weightedKnearest neighbors,簡稱WKNN),其對參考點的位置坐標計算加權平均值,以得到更優的位置估計[22].然而,無論是KNN算法還是WKNN 算法,它們的WiFi 指紋數據庫都是針對一整塊區域建立的,而工程實際要求處理面積較大的目標區域,此時由于AP 的覆蓋范圍有限,上述算法無法根據目標區域內測得的WiFi 信息建立一套全區域都適用的指紋數據庫.此外,WKNN 算法估計出的位置在空間上有時還會出現跳動距離過大的情況,這是其在整個目標區域內選擇K個參考點所造成的固有缺陷.

針對上述問題,本文提出了一種基于空間特征分區和前點約束的WKNN 室內定位方法.該方法通過將面積較大的一整塊區域按照其空間特征劃分為多個分區,解決了指紋數據庫全域覆蓋的問題;又通過考慮行人前后位置之間空間約束關系,縮小了參考點的候選范圍,很好地提升了位置估計的平順性.大量真實環境下室內定位實驗的結果表明,本文方法可以有效地解決大面積區域內的室內定位問題,且與傳統方法相比,定位精度有較大幅度的提升.

1 基于空間特征的室內分區方法

傳統的WKNN 方法在建立WiFi 指紋數據庫的過程中,需要對目標區域內所有的指紋點所獲得各AP 的RSSI 數據進行處理,具體處理方法是提取出全部RP 所共有的AP 對應的強度信息.這樣做的前提是共有的AP存在且數量足夠,從另一方面來講,即要求有足夠多的AP 其信號可以覆蓋整個目標區域.然而,當目標區域的面積足夠大時,限于AP 的信號覆蓋能力,該條件顯然無法被滿足.

本文提出的基于空間特征的室內分區算法可以很好地解決上述問題,其基本做法為:首先將面積較大的目標區域依據其空間特征(如是否貫通、有無遮擋等)劃分為多個面積較小的分區,然后對每個分區分別獲取各自內部RP 所共有的AP 信息作為該分區的標識信息,同時建立分區指紋數據庫;在在線匹配階段,通過比對測試點獲取的AP 信息與各分區的標識信息,判斷該測試點所處的分區;最后,使用相應分區內的指紋數據對測試點位置進行估計.具體處理方法如下.

?步驟1:劃分分區.

根據目標區域的面積大小,恰當地選取RP 的分布密度,記錄各RP 的位置信息.在每個RP 處獲取各AP 信息,并記錄相應的RSSI 值.設目標區域內共有參考點m個,第i個RP 的位置坐標為(xi,yi),在該點可獲取ni個AP信息,其中,第j個AP 的MAC 地址為MAC_i_j,對應的強度值為RSSI_i_j,則WiFi 信號的原始數據可以表示為

通過分析目標區域的空間特征,將m個RP 分配到k個不同的分區.設第i個分區內有參考點im個,則該分區內的WiFi 信號數據可以表示為

由于每個RP 處能夠接受到的AP 信號數目各不相同,所以每條RP 數據的長度不可能全部相同.為了后續計算的方便,需要對分區內的WiFi 信號數據進行預處理,使其長度保持一致.具體做法是,截取分區內所有RP 所共有的AP 信息,組裝成長度統一的分區指紋數據庫.設i分區內im個RP 所共有的AP 數目為ni,則分區指紋數據庫可以表示為

?步驟2:提取分區標識序列.

各分區的最主要區別在于其內部信號較強的AP 各不相同,因此,將每個分區內信號最強的q個AP 的MAC地址按照RSSI 由強到弱的順序排列組裝成一串特征序列,它就可以作為分區的標識序列,簡捷地反映出各分區的特征.具體做法如下.

(1)對i分區指紋數據庫內對應相同MAC 地址的RSSI 值進行求和運算,并按照由強到弱的順序進行排列,得到強度和序列:

其中,

(2)若某AP 在分區內部影響較大,則分區內絕大部分RP 可以接收其RSSI,且數值較大.通過公式(4)和公式(5)的求和運算后,該AP 對應的強度和數值也較大,排序靠前.因此,可以截取公式(4)所示序列的前q個作為分區的標識信息,組成新的強度和序列.

(3)將公式(6)中RSSI 值的和依照公式(3)所示的分區指紋數據庫替換為其各自對應的MAC 地址,則可得到i分區的標識序列:

?步驟3:分區判別.

由于對目標區域進行了分區處理,當測試點數據獲得以后,首先需要執行對其所處分區的判別,之后才能夠調取相應分區內的WiFi 指紋數據執行WKNN 算法.設在測試點獲取的測試數據包含p個AP 信息,將其按信號強度從強到弱排序后,可以表示為

截取測試數據的前q個MAC 地址組成測試序列:

將公式(9)中的測試序列與公式(7)中每個分區的識別序列進行比對,記錄各組數據在2q個MAC 地址中重合的個數,記作nums_amei,其中,1≤i≤k.

一般來說,選取{nums_ame}中數值最大的一個,其所對應的i即為當前測試點所處的分區編號.但是當測試點處于兩分區交界線附近時,其受到兩個分區的影響程度相當,便很容易出現nums_amei=nums_amej的情況.此時,算法將無從判斷測試點所處的分區.更嚴重時,甚至會造成分區的誤匹配.為了盡可能減少匹配失效和誤匹配情況的發生,本文在采用識別序列進行分區判別的基礎上,引入信號空間距離判定作為二級判定依據,其具體做法如下.

(1)設定啟動二級判據的閾值Δnums_ame,設{nums_ame}中數值最大的兩個分別為nums_amei和nums_amej,且nums_amei≥nums_amej,如果兩者的差值大于Δnums_ame,則說明i分區對測試點的影響力遠大于j分區,此時不需要啟動二級判據;如果兩者的差值小于或等于Δnums_ame,則說明兩分區對測試點的影響力相當,此時就需要啟動信號空間距離判據.

(2)二級判據啟動后,測試點需要依照WKNN 算法,分別與i,j兩個分區內的指紋數據逐一計算信號空間距離,各空間距離可以表示為

在上式的計算過程中,由于測試數據和兩個分區指紋數據所包含的AP 信息不盡相同,因此需要截取各組數據所共有的AP 信息進行計算.

(3)由于計算信號空間距離時對兩個分區指紋數據截取的維度不同,為了使空間距離具有可比性,將公式(10)中的空間距離分別除以各自對應的維度,得到歸一化的信號空間距離,按距離從小到大排序后,可以表示為

其中,

(4)截取公式(11)中歸一化空間距離最小的K個,記作:

對其進行平均值的求取,得到K個歸一化歐式距離的均值:

如果mean_li≤mean_lj,則判定測試點處于i分區;反之,則為j分區.

綜上所述,本節給出了基于空間特征的室內分區方法.方法流程圖如圖1 所示.它由兩部分組成.

?第1 部分是將目標區域劃分為不同分區,同時得到各分區的標識序列和指紋數據庫

?第2 部分則給出了判斷測試點處于哪一分區的兩級判據:標識序列判別和歐氏距離判別.

通過分區,在大面積目標區域內執行室內定位算法的困難得以解決,為后續基于前點約束的WKNN 定位算法的實現奠定了基礎.

Fig.1 Spatial characteristics partition framework圖1 空間特征分區框架圖

2 基于前點約束的WKNN 定位算法

通過對目標區域分區和分區判別算法,可以確定用戶所在測試點的分區編號,進而可以調用對應分區內的WiFi 指紋數據庫,采用WKNN 算法得到最終的用戶位置估計.傳統的WKNN 算法雖然較KNN 算法在定位精度上有了一定的提升,但是并沒有解決其定位結果在短時間內往復跳動、平順性不佳的問題.造成該問題的原因在于,這兩種算法對K個參考點的選取并不恰當.理論上講,兩條WiFi 數據的信號空間距離越小,其在真實空間中對應位置的距離也就越近,這是WKNN 算法的理論基礎.但是無論是在指紋數據庫的錄入過程中,還是在測試數據的獲取過程中,WiFi 信號都不可避免地受到來自外界各種因素的干擾;同時,由于AP 發射的WiFi 信號本身就存在很大的波動性,因此實測得到的指紋數據與測試數據都不可能完全準確.所以在WKNN 算法的計算過程中,通過比對信號空間距離篩選出的K個參考點很有可能并不是在實際空間上距離測試點最近的K個.又由于WKNN 算法對于K個參考點的篩選范圍并沒有限制,所以篩選出的某一個或幾個參考點與測試點實際距離較遠的極端情況也有可能發生,而這無疑會對位置估計的平順性和精度造成負面影響.

用戶在室內行進過程中,在比較短的時間段內行進的距離并不會很遠,因此可以認為行人的位置在空間和時間上具有連續型,即,其受到空間與時間的約束限制.本文所采用的前點約束法正是基于室內定位的這一特征,利用行人前一時刻獲得的位置估計來對當前時刻的位置估計進行約束.其基本做法為:首先,通過WKNN 算法在整個分區內選出K個候選參考點;然后,以前一時刻的位置為圓心,選取恰當的R為半徑做圓,以圓內作為約束條件對K個候選指紋點進行篩選,得到用以進行位置估計的最終參考點;再通過WKNN 算法計算出最終的位置估計.與傳統的WKNN 算法相比,基于前點約束法的WKNN 算法縮小了參考點的候選范圍,強制它們聚集到測試點實際位置的周圍,在根本上杜絕了由于WiFi 信號數據不準確造成參考點距離實際位置較遠情況的出現,從而增強了定位結果的平順性,提高了位置估計的精度.基于前點約束的WKNN 算法的具體步驟如下所示.

?步驟1:計算信號空間距離.

用戶使用設備在測試點獲取如公式(8)所示的測試數據,簡記作序列A.

設測試點通過分區判別以被確認屬于i分區,則將序列A與公式(3)所示i分區指紋逐一進行信號空間距離的計算,得到一組歐式距離的集合B.

其中,

其中,nj為序列A與分區指紋RP_ij所重合的AP 個數.

?步驟2:加權得到位置估計.

截取集合B的前K個元素,組成候選參考點歐氏距離集合C.

將集合C中的每個元素替換為其所對應的RP 位置坐標,則可得到候選參考點位置集合D.

設行人在t-1 時刻的位置估計為(xt-1,yt-1),以其為圓心、以Rt-1為半徑做圓,記作圓o.以處于圓o內部作為約束條件,獲取集合D的子集E,即為最終參考點位置集合.

其中,iO為使用前點約束篩選出的參考點的個數.

相應地,可以得到集合C的子集F,即為最終參考點歐氏距離集合.

基于WKNN 算法,根據公式(22)中的歐氏距離,可以計算最終參考點各自的權重:

則當前時刻,t的位置估計(xt,yt)為

對于前點約束法,有兩點需要特殊說明.

(1)對初始位置進行估計時,由于其沒有前一時刻的位置估計,因此需要采用標準的WKNN 方法計算;

(2)在公式(21)與公式(22)所示的最終參考點篩選過程中,仍有小概率出現篩選結果為空集的情況,此時也采用標準的WKNN 方法進行位置估計.

前點約束法的流程圖如圖2 所示.

Fig.2 Former location restriction framework圖2 前點約束框架圖

3 實驗與結果分析

3.1 實驗設備與環境

選擇北京航空航天大學新主樓C 座9 層環形走廊作為實驗場地進行定位實驗,使用MI 5 手機(MEID:990********129)對參考點RP 處的WiFi 信號強度進行采集,通過空間特征分區算法獲取指紋數據庫后,實驗員手持該設備沿走廊中線繞實驗場一周,實時獲取測試數據并與指紋數據庫進行匹配,通過基于前點約束的WKNN 算法得到室內位置的估計結果.

3.2 實驗過程

(1)設置參考點并獲取原始數據

首先需要針對實驗區域設置一定數量的參考點,考慮到本實驗中的目標區域形狀為矩形,因此采用四邊形法,以1.2m 間隔進行參考點的獲取,并在同一坐標系下記錄各參考點的位置坐標,最終在目標區域內獲得158 個指紋點,如圖3 所示.

Fig.3 Map of experimental environment圖3 實驗環境示意圖

隨后,實驗員手持MI 5 手機在所有參考點處對WiFi 信號進行測量,所需記錄的數據包括所有接收到的AP的MAC 地址及其對應的信號強度RSSI,經編號后存儲為公式(1)所示的格式.在數據獲取過程中,為保證指紋數據的準確性,盡量減少WiFi 信號波動性造成的不利影響,在每個RP 處按照東西南北這4 個方向各進行10 次測量,再對40 條數據取平均值作為最終的信號強度存入原始數據庫中.

(2)劃分分區并提取指紋數據庫

在參考點設置完畢的情況下對目標區域進行分區,由于實驗環境為一條環形走廊,按照分區內部應當貫通的原則,在實驗中將4 條直線型的走廊作為目標區域的4 個分區,如圖4 所示.

Fig.4 Target space partition圖4 目標區域分區

在分區過程中需要注意:為了避免分區后形成定位盲區(即不被任何分區所覆蓋的室內空間,如圖5 所示),相鄰的分區應當共享邊界處的指紋點,使分區之間達到無縫連接.

Fig.5 Blind zone caused by wrong partition圖5 錯誤分區造成的定位盲區

在分區劃分完成后,對各自分區內部的WiFi 信號原始數據進行共有AP 信息的截取,以建立分區指紋數據庫(如公式(3)所示),進而提取出各分區的標識序列(如公式(7)所示).分區指紋數據庫的建立過程與分區標識序列的提取過程分別詳見第1 節的步驟1 與步驟2,此處不再贅述.

(3)在線測試并得到位置估計

建立分區指紋數據庫后可進行在線測試階段,在該階段,實驗員手持MI 5 手機沿走廊中線的規劃路徑勻速行走一圈,當行走至測試點時,通過操作實時獲取測試數據,測試數據的存儲格式如公式(8)所示.實驗過程中,共獲得155 個測試點,測試點間隔0.6m,如圖6 所示.

Fig.6 True trajectory of positioning experiment圖6 定位實驗真實軌跡

對于每一條測試數據,首先通過分區判別算法確定實驗員當前位置所處的分區(詳見第1 節步驟3),進而調用相應分區的指紋數據庫與該條數據進行匹配,最終通過基于前點約束的WKNN 算法計算得到位置估計結果(詳見第2 節).

3.3 實驗結果與分析

基于上述已獲取的指紋數據庫和測試數據,分別采用傳統的WKNN 算法、融合軌跡外推信息的WKNN 算法與本文基于空間特征分區與前點約束的WKNN 算法進行對比運算.實驗中,對前兩種算法取K=5,對本文方法取K=10,R=2.7m.而對于前文所述兩種特殊情況,K取值與傳統WKNN 算法保持一致,記作KW.為保證分區判別算法的準確性,對其所需參數取q=20,Δnums_ame=0.用戶在目標區域行進一圈,3 種方法位置估計的對比圖如圖7 所示,其各自的位置估計誤差見表1.

從圖7 中的對比可以看出,使用本文方法的位置估計軌跡更加平順.與使用傳統WKNN 方法的位置估計軌跡相比,往復跳動的現象得到了很好地抑制,也更加貼合圖6 所示用戶真實的行進軌跡.結合表1 所示兩種方法位置估計誤差的數值,其最小估計誤差都保持在0.02m,但是WKNN 方法的最大估計誤差達到了7.92m,而本文方法的最大估計誤差只有2.63m.

從全程的平均誤差來看,本文方法的平均估計誤差保持在1m 以內,達到了0.88m,與WKNN 方法1.66m 的平均誤差相比,估計精度提升了47%.融合軌跡外推信息的WKNN 方法則是在傳統WKNN 方法結果的基礎上,通過對前兩個時刻的位置估計外推得到當前時刻位置估計的預測值,再將該預測值與WKNN 方法所得當前時刻的位置估計進行融合,從而得到最終的估計結果.該方法由于在估計過程中利用了用戶的歷史位置信息,因此精度與傳統的WKNN 方法相比有小幅度的提升,但是與本文方法的位置估計精度相比仍有非常巨大的差距(如表1 所示),這說明本文方法對于歷史位置信息的挖掘和應用更加深入和充分.此外,通過對155 個測試點分區判定結果的統計,由識別序列與信號空間距離所組成的兩級分區判別算法,其準確率達到了96.4%,顯示出判別算法在實際應用中的可靠性.

Fig.7 Comparation of estimated trajectories圖7 位置估計對比

Talbe 1 Comparison of estimation errors表1 估計誤差對比

圖8 進一步給出了本文方法和傳統WKNN 方法位置估計誤差的累計概率對比圖.從圖中可以看出,在采用本文方法對全程155 個測試點進行位置估計時,有80%以上的估計結果精度都保持在1.5m 以內;而在同樣的精度范圍內,傳統WKNN 方法估計結果達到標準的還不足60%.這也可以從另一個方面說明,本文方法相對于WKNN 方法的提升是全方位的.

Fig.8 Cumulative probability of location estimation errors圖8 位置估計誤差的累計概率

3.4 參數優化

在第3.2 節中已知,對本文方法所需要的參數取K=10,R=2.7m,KW=5.對于一個確定的目標區域,選取不同的參數值得到最終的估計結果也有所不同.為了最大限度地發揮本文方法的優勢,實驗中對參數進行了最優化計算.具體考慮了KW∈{4,5,6},R∈{2.5,2.6,…,3},K∈{5,6,…,15}下所有的組合方案,得到的計算結果如圖9～圖11所示.

在這3 種情況下,最優參數組合均為K=10,R=2.7m,而其中以KW=5 時的位置估計精度最高,因此在本實驗環境下,選取其作為實驗參數.需要說明的是,該參數組合僅在當前目標區域下為最優參數,當實驗環境、測量工具發生變化時,需要重新運行參數優化過程以獲得相應條件下的最優參數.

Fig.9 Average estimation error distribution when KW=4圖9 KW=4 時平均估計誤差分布

Fig.10 Average estimation error distribution when KW=5圖10 KW=5 時平均估計誤差分布

Fig.11 Average estimation error distribution when KW=6圖11 KW=6 時平均估計誤差分布

4 結 論

傳統的WKNN 方法無法解決一套指紋數據庫覆蓋整個目標區域的難題,同時還存在估計結果跳動跨度較大的問題,嚴重影響室內定位精度.針對上述問題,本文提出了一種基于空間特征分區和前點約束法的WKNN室內定位方法.通過將面積較大的目標區域按照其空間特征劃分為多個分區,同時引入識別序列和歐氏距離的組合分區判據,解決了指紋數據庫無法實現全域覆蓋的問題;又通過考慮行人在相鄰時刻所處位置之間的空間約束關系,縮小了最終參考點的篩選范圍,很好地提升了位置估計的精度.在北京航空航天大學新主樓C 座9 層環形走廊進行的室內定位實驗結果表明,與傳統的WKNN 方法相比,本文方法極大地提升了位置估計軌跡的平順性,分區判別正確率達到96.4%,室內定位精度則提升了47%,達到了0.88m,進而證明了本文方法的有效性.