基于智能終端的室內定位系統研究與實現

黃 璐，甘興利，李雅寧

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150000； 2.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊050081)

基于智能終端的室內定位系統研究與實現

黃 璐1，甘興利2，李雅寧2

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150000； 2.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊050081)

針對全球定位系統GPS不能提供令人滿意的室內定位結果，提出一種基于接收信號強度的WLAN指紋匹配定位技術，采用一種創新式的指紋庫構建方式，改進加權K近鄰算法，同時利用指紋匹配的優點來校準行人航位推算的累積誤差，提高定位精度，設計完成一套基于智能終端的絕對定位系統。實驗結果表明，與傳統無線定位算法相比較，改進的無線指紋匹配定位平均誤差為1.66 m，無線修正航位推算平均定位誤差為0.56 m，達到了室內定位精度的標準，驗證了改進算法的有效性及導航系統的實效性。

室內定位；航位推算；無線指紋；智能終端

0 引言

根據近幾年的統計，人們80%～90%的生活時間處于室內環境中，包括在商場、機場、圖書館和大學校園等場所，同時70%的移動電話和80%的蜂窩數據傳輸來自于室內[1]，這些引起了人們對基于位置服務(LBS)與位置感知的室內定位的濃厚興趣，例如在正在建設中的建筑物中導航與規劃、資產跟蹤，還有一些老年人輔助生活(AAL)等。為了使這些應用能夠被廣泛地接收，室內定位需要一個準確可靠的位置估計方案。在室外使用GPS系統，然而在室內GPS信號較弱甚至接收不到，不能得到準確的定位結果，這導致在進入陌生的環境需要耗費很多時間和精力去熟悉環境，大大降低了效率，甚至在特殊環境中帶來各種潛在的危險[2]。

由于室內環境多變復雜，存在多種干擾，造成傳統的基于到達時間和到達角度的方式很難得到準確的定位結果，而且雖然無線網絡廣泛存在于室內環境中，但是魯棒性強的室內定位系統需要離線采集到的指紋信息長期穩定不變，這對傳統的指紋匹配算法來說是一個很大的挑戰。針對上述問題，本文提出了一種改進的無線指紋定位算法，并設計了一種融合多種方式的定位系統。

1 行人航位推算

慣性導航系統[2](Inertial Navigation System，INS)一般分為2類：

① 基于雙積分的方式[3]，根據牛頓力學的原理，通過對三軸加速度數據積分處理，得出相應的行進速度和行進距離，理論較為成熟，但在實際應用中，由于傳感器精度受限，加上長時間定位累積誤差較大沒有得到推廣；

② 航位推算法，已知初始位置，利用傳感器數據獲得行進方向與移動速度，推算下一步的位置，該方法是目前用于室內定位最常用的連續自主導航定位方式[4]。

近年來，慣性導航系統逐漸從穩定平臺技術轉向捷聯技術，應用范圍也由早先的車船拓展到航天器導航。隨著微機電系統(Micro-Electro-Mechanical Systems，MEMS)[5]技術水平的提升，基于MEMS的捷聯慣性導航系統逐漸成為室內定位技術的研究熱點。行人航位推算原理圖如圖1所示。

圖1 PDR算法原理

加速度計的測量值用來檢測步數，陀螺儀、磁力計用來檢測方向的，當PDR的步伐檢測算法檢測到行人行走一步時，步長和行進方向估算算法開始運行并估計出第K步的步Lk及行進方向θk行人的位置可以通過下式進行更新：

2 改進無線指紋定位算法修正航跡推算結果

2.1 傳統加權K近鄰算法

在室內定位技術探索與發展的過程中，基于無線指紋匹配技術是應用最廣泛的，最成熟也是最易于推廣使用的絕對定位方式。目前各大商場、機場和博物館等大型場所均已覆蓋無線網絡，可以利用這些無線信號確定行人在環境中的位置，實現室內定位[6]。

指紋匹配技術又稱場景分析法[7]，是基于匹配思想的一種定位方法，通過某一場景下實時接收到的場景信息與指紋數據庫中的信息進行匹配，得到最優估計。在室內環境下，特別是大型建筑物，無線電波在傳輸的過程中，經過傳播損耗、反射、折射、繞射以及多徑傳播[8]，每次接觸到阻礙物就會有一部分能量被吸收，室內環境雖然復雜，但格局基本保持不變，設施幾乎也不會有太大的移動，因此只要信源不作變化，在特定位置上形成的無線信號特征(信號數目、強度和相位)就會呈現出較高的特殊性。如果把這一特征和位置的坐標進行關聯，則該信號特征可以表征該點位置，這是位置指紋定位技術成立的必要條件。

WLAN無線定位系統包括組網階段、離線階段和在線階段[9]。組網階段包括建立室內傳播模型、AP的布置；離線階段包括指紋采集及數據庫預處理；在線階段包括測試點信號的實時采集及預處理、定位算法匹配指紋數據庫等。傳統無線指紋匹配總體框圖如圖2所示。

圖2 指紋庫匹配示意

雖然無線指紋匹配技術已經在室內定位領域中得到廣泛應用，但是定位精度還遠遠不足，因此本文提出一種改進的加權K近鄰算法用于指紋庫定位，同時提出一種新的指紋構建模式，使用指紋定位結果來修正PDR的累計誤差。現實生活中幾乎任何建筑中都存在Wi-Fi網絡，這使得可以根據接收到的來自各種路由器的Wi-Fi信號強度值區分不同的位置，本文可以將接收到的信號構建指紋庫用于室內定位，基于位置指紋庫的定位系統通常包括離線采樣和在線測試[6]這2個階段。

離線采樣階段，利用了AP熱點的獨一無二的特性，每一個AP熱點都有自己的標示符BSSID，同樣在已知位置處接收到的信號強度值rssi雖然隨著距離的增加會越來越弱，但是在10m之內，仍然可以獲得到每一個AP熱點廣播的信號強度值，在采樣點處記錄來自m個不同AP的信號強度值RSSI，構建Wi-Fi指紋地圖Radio Map，n個參考點的存儲結構為：

(qi,ri)i=1,2,…,n，

式中，qi=(xi,yi)，qi為第i個位置的地理坐標；ri=(ri1,ri2,…,rim)，為位置i處接收到來自m個AP的信號強度值。

在線測量階段，在待定位點處搜集并記錄接收到的指紋信息，使用定位估計算法結合離線階段構建的Radio Map解算出位置坐標作為Wi-Fi單點定位的結果。

本文利用改進的加權KNN算法進行Wi-Fi位置解算得到Wi-Fi定位結果。傳統加權KNN算法在線測量階段，首先通過計算n個參考點與定位點信號強度值的歐氏距離，然后遞增排列距離d，取前k個值及其坐標計算定位點坐標，具體實現步驟如下：

① 在RadioMap中找到k個最近的參考點。

輸入：n個參考點的信息(q1,r1),(q2,r2),…,(qn,rn)，未知點的接收RSSI為r。

輸出：k個最近的參考點。

步驟：通過公式計算未知點rssi與n個參考點的rssi的歐氏距離，按照遞增的順序排列，返回前k個位置點(q1,r1),(q2,r2),…,(qk,rk)。

② 計算當前待定位點的坐標。

輸入：最近鄰的k個參考點的信息，包括位置坐標和該位置接收到的各個AP的信號強度值r。

輸出：待定位點的坐標。

步驟：計算位置坐標

這里所有的權重均是非負的，

式中，d為信號強度值之間的歐氏距離；qj為第j個位置的坐標。

加權K近鄰算法有一個調整參數k，這個k用來控制計算的位置坐標，當k=1時，算法就相當于在一個列表中查找一個位置坐標，當k值很大時，計算的位置坐標就會估算到在這些參考點附近。考慮到現實的一些影響因素[7]：

① 抖動的接收信號強度，導致在相同位置處信號強度值差異較大；

②AP可靠性，考慮到定位應該是長期性整體性的系統，所有AP應該是長期可利用的或者新加入AP會影響系統的穩定性。

③ 用戶的身體朝向，人體中的水分會嚴重影響用戶接收到的信號強度值[10]。

2.2 改進的加權K近鄰算法

無線信號在空間中傳輸會受到建筑物、人和電磁場等造成各種干擾，這些干擾會造成獲得的RSSI不準確，進而影響到定位結果[11]。所以，針對存在的種種問題提出了一系列解決方案。首先，在離線訓練階段采集數據時同時采集每個AP一段時間內的最大值、最小值及平均值。通過編寫的數據采集軟件，在采樣點的1m2范圍內走動，身體朝向不同的方向采集信息持續30～40s，將數據保存到手機SD存儲卡上，同時將文件名設置成該采樣點的位置坐標。在線階段通過程序編寫算法可以增量式的添加新的AP，以離線采樣的格式存儲，實時更新指紋信息庫，增強定位系統的穩定性。其中對定位算法影響較大的是權值計算，傳統的加權K近鄰算法單一地使用信號強度值的歐氏距離作為權值，由于信號強度值的不穩定性導致錯誤的權重分配，比如某段時間內原本離的很近的參考位置點權重變的很低，原本很遠的點權重很高，最終導致定位誤差增大，所以為了解決這個問題，提出了一種優化權值的新方法，在某種程度上解決了路徑損耗帶來的誤差，具體實現步驟如下：

① 離線采樣階段，為了解決在一個固定區域內搜索到很多個AP熱點的強度值的無法區分的問題，使用BSSID和RSSI的最大最小值，及固定時間內的平均值采樣，建立一個RadioMap選擇建筑物內的一些位置點作為采樣參考點，數據庫的存儲格式為：

(BSSIDrssi_maxrssi_minrssi_mean)。

② 在線測量階段，在使用KNN算法計算出k個最近鄰的參考點后，這里的權重增加匹配率m，分別判斷這k個位置點的指紋庫與待定位點指紋信息的匹配程度，通過程序編寫計算k個位置點的匹配率，程序偽碼如下：

1for(ArrayListtable:Table){

2 for(Datad:dtable){

3 for(Info i:table){

4 if(i.getBSSID().equals(d.getBSSID())){

5 if(d.getLevel()i.getLowestlevel()){

6 result[Table.indexOf(table)]++;

7 }

8 }

9 }

10 }

11r[Table.indexOf(table)]=((float)result[Table.indexOf(table)]/(float)table.size())*100;

12 }

匹配率高的分得更大的權重再結合rssi的歐式距離，最終提高定位精度，改進后的計算公式為：

圖3 改進算法流程

3 航位推算結果的修正與路徑約束

傳統的Wi-Fi指紋庫匹配算法修正PDR推算結果均是在計算機上仿真實現的，本文將利用改進的加權K近鄰算法在智能終端上實時修正PDR推算結果，實現完整的定位跟蹤系統，同時會在智能手機屏幕上實時顯示用戶軌跡及校準點位置，真正意義上實現了移動終端獨立定位跟蹤的技術[12]。具體實現步驟如下：

步驟1 通過JavaOpenStreetMap(JOSM)編輯器繪制出導航路徑與實驗路徑圖[13]，由于該軟件繪制的路徑是由經緯度表示的，所以需要將經緯度通過墨卡托投影轉換成大地坐標，最后將大地坐標與室內地圖XY坐標對應，存儲為map3.osm，通過編寫程序解析出路徑信息并顯示在手機屏幕上[14]；

步驟2 根據實際應用環境規劃行走路徑，通過實驗分析標定參考點位置；

步驟3 在標定參考點處采集指紋信息同時對接收信號強度值進行預處理，預處理的主要目的是消除奇異值[15]、噪聲等因素的影響，主要包括均值濾波和高斯濾波2種方法。

① 均值濾波

均值濾波是取同一參考點處多次采集數據的平均值作為該參考點信號強度的估計值，計算公式為：

② 高斯濾波

由于均值濾波是用采集數據的均值作為信號的估計值，所以引入了小概率信號誤差，高斯濾波就是為了消除小概率信號的影響而引入的一種RSS預處理方法[16]。高斯濾波通過概率門限降低小概率信號誤差，提高信號估計的準度。根據工程中經驗值得出高概率發生區為概率大于0.6的區域，經高斯濾波后，移動終端RSS的取值范圍應為[0.15σ+μ,3.09σ+μ]，其中σ和μ分別為測得數據的標準差和均值。最后取出高概率范圍內的RSS值再計算其平均值，即可得到最終的RSS值。

步驟4 通過使用改進的算法得到無線定位結果作為PDR推算的初始位置；

步驟5 使用者手持智能終端沿著規劃路徑以正常速度行走，終端屏幕顯示路徑軌跡。

步驟6 定位結果分析，計算定位誤差。

4 實驗結果與分析

實驗環境選擇衛星導航系統與裝備技術國家重點實驗室，環境大小為20m×82m。在實驗環境中布置5個AP熱點，在試驗路徑周圍每1m設置一個參考點，并在參考點處采集指紋信息構建指紋數據庫，在以參考點為中心，1×1鄰域內行走，每個參考點采集2～3min。每隔2m設置一個測試點，實驗數據采集完成后，將指紋信息與位置坐標一一對應，文件名為位置坐標，內容包括物理地址和信號強度值的最大、最小以及平均值。存儲格式如圖4所示。

圖4 指紋庫存儲格式

實驗對比分析傳統的無線定位算法，包括傳統K近鄰算法、傳統加權K近鄰算法和本文提出的改進WKNN定位算法，使用繪圖工具將采集到的真實數據處理分析得到如圖5和圖6所示的定位誤差結果。

圖6 無線定位算法誤差累計分布函數

從圖5和圖6可以看出，傳統的KNN算法由于權值分配過程中存在信號強度值不穩定導致定位誤差波動較大，傳統WKNN算法在K=3時的參考點的指紋信息分配權重定位誤差相對穩定，當信號強度值波動較大時權重分配就會不準確，造成定位誤差仍舊很大，本文提出的新算法整體誤差穩定，平均誤差也有了一定的提高，結果如表1所示，對3種不同無線定位手段進行對比實驗，表1中的對比數據為了保證數據的可靠性和普遍性，均是經過多次真實實驗收集到的數據。實驗驗證了算法的有效性。

表1 不同定位方式結果比較

從表1中可以看出，傳統的無線定位算法與本文提出的定位算法在定位精度上有顯著差別，傳統KNN與WKNN算法，誤差波動較大，定位結果不穩定，平均定位誤差分別為5.90和2.35，5 m內的定位精度分別達到52.9%和90.7%。改進后的加權KNN算法平均定位誤差為1.66 m，5 m內的定位精度達到98.7%，在一些特定場合完全符合室內定位的標準，但是最大誤差與最小誤差差距仍在7 m以上，定位不穩定，所以本文通過改進的定位算法與PDR算法相融合，使用絕對位置來修正PDR的累計誤差，建立了一個穩定的定位系統，同時提出一種路徑約束方式約束PDR的定位系統。實驗通過使用者手持智能終端在設定好的路徑起點走到終點，實驗分為2種對比模式：單獨PDR和無線指紋算法單點修正PDR，實驗結果如圖7、圖8、圖9和圖10所示。

圖7 傳統PDR定位跟蹤真實軌跡

圖8 改進的加權KNN修正PDR真實軌跡

圖9 2種定位方式誤差對比

圖10 2種方式誤差累計誤差分布函數

由圖7中可以看出，實驗人員手持智能終端在實驗環境中按照規劃好的路徑行走，傳統PDR推算的真實路徑圖。圖7中彎曲軌跡是PDR推算軌跡，直線軌跡是規劃好的真實路徑，可以清晰地看到在開始階段PDR推算較為準確，在第一個轉彎處由于方向的檢測存在誤差導致路徑開始偏移，繼續行走累計誤差越來越大。由圖8中可以看出，在PDR行走的偏差較大處通過改進的無線定位手段進行修正，將位置校準到真實路徑上，整體軌跡較為準確，基本達到室內定位標準。由圖9和圖10可以看出，傳統PDR定位算法在定位初期較穩定且誤差較小，隨著時間的增長誤差開始發散，最大誤差為4.12 m，平均誤差為1.44 m，在某些空間較小的室內環境下，PDR跟蹤定位可以單獨使用。經過改進的無線單點定位算法修正PDR的結果最大定位誤差在1.52 m，平均定位誤差在0.56 m，消除了累計誤差。

仿真實驗是在處理器型號為Intel-i5-4200H，主頻為2.80 GHz，內存為4 G，操作系統為Windows 8.1中文版的PC機上使用Matlab2010以及Eclipse兩種軟件實現，真實實驗是在搭載Android 4.0操作系統的三星Note2、紅米2A加強版和華為榮耀4智能手機上實現。

5 結束語

通過對傳統PDR存在的不足之處進行改進，包括步數估計方面采用自適應閾值校正的方式，采用方向補償方式優化了設備方向的檢測。針對傳統無線定位手段采用各種濾波方式融合PDR數據難以在智能手機上單獨實現的問題，提出了一種基于智能終端的改進的加權K近鄰無線定位算法單點修正傳統PDR累計誤差的定位方式，通過實驗得到平均定位精度達到0.56 m，基本滿足室內定位的精度要求。

結合本文提出的室內定位方式，未來將會設計一種室內外無縫切換的高精度定位系統，比如在一些大型場所可以用過智能手機開啟定位系統，室外使用GPS/BD，室內使用無線定位結合PDR及路徑約束方式進行定位與導航。

[1] TANCHAROEND,AIZAWA K.Wearable Video Retrieval and Navigation System Using GPS Data[J].IEEE Int.Can Computer and Information Technology,2010,23(10):62-67.

[3] RAOMGD,ROENG T.Using the ADXL202 in Pedometer and Personal Navigation Applications[J].Application Note AN602,Analog Devices,2013,6(2):23-24,56.

[4] BAHLP,PADMANABHAN V N.RADAR:An In-building RF-based User Location and Tracking System[J].Microsoft Research,2000,4(1):10-16.

[5] MAJ,LI X,TAO X,et al.Cluster Filtered KNN:a WLAN-based Indoor Positioning Scheme[J].International Symposium on a World of Wireless,Mobile and Multimedia Networks,2008(8):1-8.

[6] YOUSSEFM A,AGRAWALA A,SHANKAR A U.WLAN Location Determination via Clustering and Probability Distributions[J].IEEE International Conference on Pervasive Computing and Communications,2003(4):143-150.

[7] SAHAS,CHAUDHURI K,SANGHI D,et al.Location Determination of a Mobile Device Using IEEE 802.11b Access Point Signals[C]∥In Proc.IEEE WCNC,2003(3):66-67.

[8] PRASITHSANGAREEP,KRISHNAMURTHY P,CHRYSANTHIS P K.On Indoor Position Location with Wireless LANs[C]∥ In Proc.IEEE PIMRC,2002(9):78.

[9] JIM′ENEZA,SECO F,PRIETO C,et al.A Comparison of Pedestrian Dead-reckoning Algorithms Using a Low-Cost MEMS IMU[C]∥In Intelligent Signal Processing,IEEE International Symposium on,2009:37-42.

[10] AZIZYANM,CONSTANDACHE L,CHOUDHURY R R.SurroundSense:Mobile Phone Localization via Ambience Finger Printing[J].In Proceedings of 15th ACM Mobile Com.,2009(6):261-272.

[11] RALLAPALLIS,QIU L,ZHANG Y,et al.Exploiting Temporal Stability and Low-rank Structure for Localization in Mobile Networks[J].In Proceedings of 16th ACM MOBICOM,2010(10):161-172.

[12] STEINHOFFU,SCHIELE B.Dead Reckoning from the Pocket[C]∥ In Proceedings of 8th IEEE PerCom,2010(5):162-170.

[13] GRAUD,CALDAS C H,HAAS C T,et al.Assessing the Impact of Materials Tracking Technologies on Construction Craft Productivity[J].Autom.Constr.2009,18(7):903-911.

[14] RAZAVI S N,HAAS C T.Multisensor Data Fusion for On-site Materials Tracking in Construction[J].Autom.Constr.2010,19(8):1 037-1 046.

[15] RAZAVI S N,HAAS C T.Reliability-based Hybrid Data Fusion Method for Adaptive Location Estimation in Construction[J].Comput.Civ.Eng.2012,26(1):1-10.

[16] DING L Y,ZHOU C,DENG Q X,et al.Real-time Safety Early Warning System for Cross Passage Construction in Yangtze Riverbed Metro Tunnel Based on the Internet of Things[J].Autom.Constr.2013,3(6):25-37.

Research and Implementation of Indoor Positioning System Based on Intelligent Terminal

HUANG Lu1,GAN Xing-li2,LI Ya-ning2

(1.HarbinEngineeringUniversity,InformationandCommunicationEngineeringInstitute,HarbinHeilongjiang150000,China; 2.TheStateKeyLaboratoryofSatelliteNavigationSystemandEquipmentTechnology,ShijiazhuangHebei050081,China)

Considering that it is unable to provide satisfactory indoor positioning results by using Global Positioning System(GPS),a WLAN fingerprinting positioning technology based on

signal strength is proposed.The weighted K nearest neighbor algorithm is improved;an innovative fingerprint structuring method is proposed,and the positioning accuracy is increased.A set of absolute positioning system based on smart phones is designed.The experimental results show that as compared with the traditional wireless positioning algorithm,the average error of the improved wireless single point positioning method is 1.66 m,the average error of wireless positioning single point correction navigation calculation is 0.56 m,which reaches the standard of indoor positioning accuracy,and verifies the effectiveness of the improved algorithm and the navigation system.

indoor positioning;dead-reckoning;wireless fingerprint;intelligent terminal

10.3969/j.issn.1003-3106.2017.09.09

黃璐,甘興利,李雅寧.基于智能終端的室內定位系統研究與實現[J].無線電工程,2017,47(9):44-50.[HUANG Lu,GAN Xingli,LI Yaning.Research and Implementation of Indoor Positioning System Based on Intelligent Terminal[J].Radio Engineering,2017,47(9):44-50.]

TP311.52

A

1003-3106(2017)09-0044-07

2016-12-03

“十三五”國家重點研發計劃基金資助項目(SQ2016YFGX040104)。

黃 璐 男，(1991—)，碩士研究生。主要研究方向：室內定位與導航。

甘興利 男，(1981—)，高級工程師。主要研究方向：衛星導航。