基于線性內插法改進的室內定位算法

張夢丹，盧光躍，王宏剛，劉繼明

（西安郵電大學，陜西 西安710121）

基于線性內插法改進的室內定位算法

張夢丹，盧光躍，王宏剛，劉繼明

（西安郵電大學，陜西 西安710121）

針對室內位置指紋定位技術存在的離線階段工作量大、定位精度有限、頑健性較差的缺點，提出了一種基于線性內插法改進的指紋定位匹配算法。與傳統位置指紋定位技術相比，該算法不僅降低了整體工作量，而且降低了多徑效應造成的不利影響。最后搭建實驗場景對該算法定位性能進行測試。實驗數據顯示，該算法與WKNN法相比，平均定位精度大約提高了34.25%，絕大部分待測點的定位誤差在0.4 m以內，驗證了所提算法在定位精度、頑健性和適應環境變化方面的優勢。

室內定位；位置指紋；WKNN；PCA；線性內插法

1 引言

隨著無線技術、移動計算機和互聯網應用的不斷增長，人們對位置敏感系統及其服務的需求越來越高。在室外，GPS系統被廣泛用于提供定位信息與服務，其室外定位精度能夠達到美國E911標準。但在室內復雜環境中，由于室內物品的干擾、非視距等因素，一般不采用GPS系統進行定位。現在常用的室內定位技術有Wi-Fi技術、藍牙技術[1]、紅外線室內定位技術、超聲波定位技術等。這些技術有的成本較高、有的室內定位精度低，均不利于室內定位的廣泛推廣。而融入了藍牙4．0的新技術，不僅增強了信號的穩定性及覆蓋范圍，而且降低了功耗，因此迅速成為室內定位領域的優選技術。

根據定位過程中是否需要實際測量節點間距離，室內定位方式可分為兩類：即基于距離[2]和距離無關。目前，基于測距的定位技術主要有到達角度（angle of arrival，AOA）法、到達時間（time of arrival，TOA）法、到達時間差（time difference of arrival，TDOA）法等，而基于非測距定位主要是基于信號強度測量法定位[4]。基于信號強度測量法定位可分為位置指紋定位法和信號傳輸損耗法[5]，而現有利用位置指紋進行匹配的算法主要包括 WKNN（weighted K-nearest neighbor，加權K鄰近）算法、神經網絡算法、概率算法和支持向量機（SVM）算法等。WKNN算法遍歷指紋點的接收信號強度指示（received signal strength indication，RSSI），找出最接近測試點RSSI的一個或多個指紋點，然后將這些指紋點位置的加權值作為測試點的估計位置。WKNN算法容易實現，但定位精度不高，且在實際的室內環境中，無線信號在傳播過程中會受到多徑效應的影響，因而在同一個位置上的接入點（access point，AP）的RSSI往往表現出復雜的時變特性，進而進一步降低了室內定位的精度。為此，本文應用主成分分析（principal component analysis，PCA）變換提取原始RSSI信號中的主要定位特征，以減少多徑效應對定位的影響。另外，針對定位離線階段工作量大的問題，本文應用線性插值法來重構離線指紋庫，并對測試點進行定位。實驗證明，所提算法具有較高的定位精度和較好的實時性，滿足了室內定位的基本需求。

2 基于RSSI的位置指紋定位算法

2.1 指紋算法描述

位置指紋定位算法包括兩個階段：離線階段和在線階段。離線階段的工作是在待定位區域內按照一定的間隔距離確定若干參考點，形成一個采樣網格圖，并將每個節點測得的信號強度值及其位置信息按照＜指紋，地點＞的格式存儲在數據庫中；在線階段，通過移動終端對各個AP發出的信號強度進行實時采集，通過特定的匹配算法實現對移動設備位置的估計[7,8]。

2.2WKNN算法

WKNN法屬于典型的確定性定位算法[9]。其定位思路為：首先構建離線指紋庫，Fi=(fi1,fi2,fi3,…,fin)，fin表示在第i個參考點處接收到第n個AP的指紋信息，其次，移動終端用戶獲取在待測點位置處各個AP的信號強度值，記為向量 Rt=(r1,r2,r3,…,rn)，rn為移動設備接收到的第 n個 AP的信號強度，最后計算此向量與指紋庫中向量的歐氏距離，為：

選擇距離最小的前K個采樣點，并按照每個參考點對待測點的貢獻程度計算每個參考點的權值 wj[10]，如式（3）所示，定位點的估計位置是這K個點的加權質心。其中，K值可根據定位環境選取[11]。

其中，Dj表示第j個參考點與待測點的歐氏距離。由式（3）知，歐氏距離Dj越大，wj越小；相反歐氏距離Dj越小，wj越大。

3 改進的定位估計匹配算法

WKNN算法雖然能基本滿足人們對位置的需求，但是仍存在一些問題：增加參考標簽數目可以提高室內定位精度，但會增加額外的成本；在密集環境下，多徑效應會給定位結果帶來一定的影響。因此提出了一種基于子區域插值改進的指紋定位匹配算法。

3.1 主成分分析法

主成分分析法的基本原理是：根據K-L變換在測試空間中找到一組能最大限度表示出原始數據信息的正交向量，把原始數據從原來的空間投影到這組正交向量組成的空間上，其投影系數便構成新的特征矢量，從而完成對維數的壓縮。

設T={(S1,L1),(S2,L2),…,(Sp,Lp),}，Sp∈Rm為參考點處的信號集。Sp為在位置p處接收到的AP的信號強度，Lp為位置p的二維位置坐標。假設 X=[S1,S2,…,Sp]T，則PCA變換為：Z=AT(X-E[X])，A=[u1,u2,…,uk]，A中的uk是由X的協方差矩陣CX=E{(X-X)(X-X)T}的特征值λk對應的特征向量按從大到小的順序排列組成。經過PCA變換，Z中各個矢量間的相似性基本消除，其中，Z中前m個主成分占據了X的絕大部分信息，Z′=[S1′,S2′,…,Sp′]T，因m＜d，因此完成了對指紋數據維數的壓縮。

3.2 線性內插法

線性內插法的基本思想是：在待定位區域內按照一定的間隔距離確定若干采樣點，形成一個采樣網格圖，在網格圖內進一步劃分，將每個由4個參考標簽覆蓋的網格分為N×N個大小相同的虛擬網格單元，由于參考標簽坐標已知，虛擬參考標簽易得到，同時采用線性插值方法來獲得虛擬參考標簽的信號強度值。下面將詳細地對該算法進行介紹。線性內插法原理如圖1所示。

圖1 線性內插法原理

如圖1所示，其中，白色圓圈代表采樣點，4個組成采樣網格圖，然后把網格劃分成N×N個小網格，灰色圓圈代表劃分好的虛擬參考點。根據實際參考點位置坐標可求得虛擬參考點的坐標。最后采用線性插值可以得到虛擬參考點處的接收信號強度值。

水平方向上的虛擬參考點接收信號強度值可以由式（4）求出：

垂直方向上的虛擬參考點接收信號強度值可以由式（5）求出：

其中，Sk(Ti,j)表示在第k個參考點坐標位置為(i,j)處讀到的接收信號強度值，a=「i/n」，b=「j/n」，「」表示向下取整，0≤p=i%n≤n-1，0≤q=j%n≤n-1，n=N-1。

3.3 N值的選擇

實際上，參考點處的RSSI值與距離的關系非線性，室內環境信道的大尺度衰落服從對數正態分布的特性，選用對數距離路徑損耗模型獲取虛擬參考點的RSSI值。“距離—損耗”計算式為：

其中，d0是參考距離；dij是第i個參考點到第 j個AP的實際距離；P0是終端和 AP的距離為 d0時接收到的RSSI；P是距離為 dij時接收到的 RSSI；n是路徑損耗指數；ζ為遮蔽因子，是均值為0、標準差為σ的正態隨機變量。

由此，可以得出：必然存在一個使定位誤差達到最小的N值，下面將進一步進行理論論證。

以圖1參考點為例進行線性插值，假設該網格的4個參考點為T1、T2、T3和T4，假設Rik為第i個參考點（包括實際參考點和虛擬參考點）處接收到的第k（k=1,2,3,4,5,6）個AP的RSSI值，Epk為相鄰參考點RSSI的差值，p=0,1,2,…,N-1，則：為在參考點T1處接收到的節點APk的RSSI，R2k為在參考點T2處接收到的節點APk的RSSI，R0k為在位置d0處接收到的節點AP1的RSSI，參考點T1的坐標為(x1,y1)，T2的坐標為(x2,y1)，APk的坐標為(ak,bk)。

對Epk求N-1的導數，并令導數為零，可得：

其中

假設k=1，此時(ak,bk)=(a1,b1)=(0,0)，若p取1，分別遍歷(x1,y1)和(x2,y1)，并將各個參數的值代入式（9）中，最終得到N值變化如圖2所示。實驗面積為14 m×10 m，參考點數為7×5，可見，理論上當N為5～6時，用線性內插法的誤差達到最小值。

圖2 N值變化折線

3.4 定位步驟

對于室內位置指紋定位算法來說，離線階段數據庫的構建以及室內環境存在多徑效應的特點都對定位產生嚴重的影響。下面將詳細介紹改進的定位估計匹配算法的步驟。對應的匹配算法流程如圖3所示。

圖3 基于線性內插和PCA改進的指紋定位匹配算法流程

步驟1 選取試驗場景，搭建測試環境，并多次采集每個參考點處的RSSI值求平均，構建離線指紋數據庫。

步驟2 選取N值，確定虛擬參考點的劃分結構，利用第3.2節介紹的線性內插法求解虛擬參考點的位置坐標和各個虛擬參考節點的RSSI值，重新構建離線指紋數據庫。

步驟3 對構建的離線指紋數據庫進行主成分分析，去掉多徑效應對信號造成的干擾，構建特征數據庫。

步驟4 選取待測點，并用移動終端讀取待測點的RSSI值，對待測點測量的數據進行PCA變換，提取特征，假設變換后的向量為Z′=[S1′,S2′,…,Sp′]T。

步驟5 選取指紋定位算法WKNN的K值，這里令K=4，然后計算Z′與特征數據庫中每個參考點的歐氏距離，選取歐氏距離最小的前4個參考點，并分別計算對應的加權值wj。

步驟6 按照式（3）估算移動端的位置，實現對移動端的實時定位。

4 實驗性能比較與結果分析

4.1 測試平臺

本實驗軟件平臺是基于Andriod開發的手機應用軟件BLE Scanner，用于實現離線及在線階段的RSSI數據采集。硬件平臺采用的是iPhone 5和蘋果公司的iBeacon產品。實驗環境位于西安郵電大學長安區3號實驗樓523房間。實驗軟件、硬件平臺和實驗場地實景如圖4所示。實驗環境參數選取見表1。

圖4 軟件、硬件平臺和實驗場地實景

表1 實驗環境參數選取

4.2 性能比較與仿真分析

由第2.2節的介紹可知，當測試環境和K值一定的情況下，影響WKNN算法定位結果的主要因素是：離線階段的參考點的數量太少，則造成定位精度下降；數量太大，耗時耗力，造成定位成本的增加。因此要根據具體的實驗場景，合理地選擇參考點的數量。對這種算法的參考點的數量選取不同的值進行MATLAB仿真，參考點的數量的選取及定位誤差見表2，仿真結果如圖5所示。由仿真結果可知，定位誤差隨著參考點數量的增加而減少。

表2 WKNN參考點數量的選取及定位誤差

同理，由第3.2節對線性內插法的介紹可知，為了在不增加定位成本的情況下提高定位精度，在WKNN算法的基礎上提出了線性內插法。當測試環境、K值以及參考點數量一定的情況下，影響基于線性內插法改進的WKNN算法定位結果的因素主要是N值的選取：N值太小，造成定位精度提高得不明顯；N值太大，由于位置和接收信號強度的非線性關系造成定位精度降低。因此要根據具體的實驗場景，合理地選擇N值的大小。對這種改進算法的參考點數量取35個，對N選取不同的值進行MATLAB仿真，N的選取及定位誤差分別見表3，仿真如圖6所示。由仿真結果可知，定位誤差并不是隨著N的增大而增大，而是有一個最佳值，因此要根據試驗場景，合理地選擇N的大小，從而達到最佳定位效果。

圖5 WKNN法不同參考點數量仿真結果對比

表3 基于線性內插法的WKNN不同N值及定位誤差

圖6 基于線性內插法的WKNN不同N值仿真結果對比

最后，根據第3.1節對PCA的介紹可知，為了減少多徑效應對定位造成的影響，在基于線性內插法改進的WKNN算法的基礎上增加了PCA，先對離線指紋庫數據進行降維，去除干擾，再進行定位，此時，選擇K=5，K=4，參考點的數目為35個，待測點數量為20個，并用MATLAB對比WKNN法和基于線性內插法改進的WKNN法，仿真結果如圖7所示，各個算法的定位誤差見表4。由仿真結果可知，PCA能進一步提高定位的精確度，精度提高了4%左右。

表4 不同算法相同條件情況下的定位誤差

圖7 不同算法相同條件下定位誤差累計分布仿真對比

另外，對于WKNN法、基于線性內插法改進的WKNN法以及基于線性內插和PCA改進的WKNN法分別進行20次測試，定位誤差對比如圖8所示。由圖8可知，基于線性內插和PCA的WKNN匹配算法的定位誤差明顯比WKNN法的定位誤差低。

由上述對算法的仿真結果可知，基于線性內插和PCA改進的WKNN法能在減少定位成本的同時提高定位精度，該算法與WKNN法相比，平均定位精度大約提高了34.25%，但是，由于離線指紋庫是根據線性內插法構建，計算勢必帶來定位時間的消耗，進而影響定位效率，用MATLAB中的tic和toc語句分別對WKNN法、基于線性內插法改進的WKNN法以及基于線性內插和PCA改進的WKNN法的效率進行仿真，仿真時間見表5，結果顯示，該算法雖然以犧牲時間為代價提高定位精度，但消耗的時間處于可接受的范圍內，說明在滿足人們對定位的要求的同時提高了定位精度。

圖8 不同算法相同條件下各個待測點處定位誤差對比

表5 不同算法相同條件情況下的仿真時間

5 結束語

本文針對增加參考點耗時耗力以及多徑干擾問題，在位置指紋定位算法的基礎上提出一種基于線性內插和PCA改進的WKNN定位方法。該算法將劃分好的網格點進行進一步的劃分，利用線性內插法重新構建離線指紋數據庫，并引入主成分分析法，減少多徑效應對定位造成的影響。所提算法使用匹配定位估計，在減少定位成本的同時提高了定位精度。由仿真分析可知，所提算法的最大定位誤差為0.391 9 m，最小定位誤差為0.026 6 m，對于長14 m、寬10 m的定位環境而言，最大誤差處于可接受范圍內。

[1]陳錫劍,程良倫.基于RSSI的功率匹配定位算法的研究與實現[J].傳感技術學報,2013,26(5):710-714. CHEN X J,CHENG L L.Research and implementation of power matching algorithm based on RSSI[J].Chinese Journal of Sensors and Actuators,2013,26(5):710-714.

[2]LU Y H,LAI C F.Path loss exponent estimation for indoor wireless sensor positioning[J].KSII Transactions on Internet and Information Systems,2010,4(3):243-256.

[3]PATWARI N,HERO A O,PERKINS M.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,2003,51(8):2137-2147.

[4]葉蔚.室內無線定位的研究[D].廣州:華南理工大學,2010. YE W.Study on indoor wireless location[D].Guangzhou:South China University of Technology,2010.

[5]楊東勇,顧東袁,傅曉婕.一種基于RSSI相似度的室內定位算法[J].傳感技術學報,2009,22(2):264-268. YANG D Y,GU D Y,FU X J.An indoor location algorithm based on RSSI-similarity degree[J].Chinese Journal of Sensors and Actuators,2009,22(2):264-268.

[6]劉鵬,盧潭城,高翔.基于射頻識別的室內定位技術綜述[J].太赫茲科學與電子信息學報,2014(2):195-201. LIU P,LU T C,GAO X.A survey of indoor location technology based on radio frequency identification[J].Terahertz Science and Electronic Information,2014(2):195-201.

[7]梁瑩.INS/地磁匹配組合導航系統技術研究 [D].哈爾濱:哈爾濱工程大學,2010. LIANG Y.Study ofINS/geomagnetic matching integrated navigation system technology [D].Harbin:Harbin Engineering University,2010.

[8]王欣.基于地磁場和RSSI的室內定位算法設計與實現[D].杭州:杭州電子科技大學,2014. WANG X.Design and implementation of indoor location algorithm based on geomagnetic field and RSSI[J].Hangzhou:Hangzhou University of Electronic Science and Technology,2014.

[9]JIANG S Y,PANG G S,WU M L.An improved K-nearest-neighbor algorithm for text categorization[J].Expert Systems with Applications,2012,29(1):1503-1509.

[10]詹杰,劉宏立,劉述鋼,等.基于RSSI的動態權重定位算法研究[J].電子學報,2011,39(1):82-88. ZHAN J,LIU H L,LIU S G,et al.Study algorithm based RSSI’s dynamic weights location[J].Journal of Electronics, 2011,39(1):82-88.

[11]HUANG C N,CHAN C T.ZigBee-based indoor location system by k-nearest neighbor algorithm with weighted RSSI[J].Procedia Computer Science,2011(5):58-65.

An improved indoor location algorithm based on linear interpolation

ZHANG Mengdan,LU Guangyue,WANG Honggang,LIU Jiming
Xi’an University of Posts and Telecommunications,Xi’an 710121,China

Aiming at the shortcomings of heavy workload in the off-line phase,limited positioning accuracy and poor robustness of indoor location fingerprint positioning technology,an improved fingerprint matching algorithm based on linear interpolation was proposed.Compared with the traditional location fingerprint positioning technology,it reduced the overall workload as well as the bad effects caused by muti-path effect.At last,a lab scene was set up to test the positioning performance of this algorithm.It is shown by the test that the average positioning accuracy of this algorithm has been improved by 34.25%compared with that of WKNN method,and the positioning accuracy error ratio of most points to be test is within 0.4 m,the positioning accuracy,robustness and adaptability in environment change were demonstrated.

indoor location,location fingerprint,weighted K-nearest neighbor,principal component analysis,linear interpolation

TN961

A

10.11959/j.issn.1000-0801.2017020

張夢丹（1990-），女，西安郵電大學碩士生，主要研究方向為通信網技術。

盧光躍（1971-），男，博士，西安郵電大學通信工程學院教授，主要研究方向為現代移動通信中信號處理。

王宏剛（1977-），男，博士，西安郵電大學講師，主要研究方向為物理層能源效率和通信協議的設計、RFID和無線定位。

劉繼明（1964-），男，博士，西安郵電大學教授，主要研究方向為下一代軟交換核心技術。

2016-07-29；

2017-01-10

陜西省工業科技攻關項目（No.2014K05-09）；陜西省教育廳科學研究計劃項目（No.14JK1660）

Foundation Items：Shaanxi Industrial Science and Technology Project(No.2014K05-09),Shaanxi Science Research Program of Education Department(No.14JK1660)