基于RSS空間線性相關的WLAN位置指紋定位算法

徐小良，高健，黃河，馬哲

（1.杭州電子科技大學計算機學院，浙江 杭州 310018；2.中浙信科技咨詢有限公司，浙江 杭州 310007）

基于RSS空間線性相關的WLAN位置指紋定位算法

徐小良1，高健1，黃河2，馬哲2

（1.杭州電子科技大學計算機學院，浙江 杭州 310018；2.中浙信科技咨詢有限公司，浙江 杭州 310007）

針對RSS（接收信號強度）時變性以及不同終端信號接收能力的差異性，導致WLAN位置指紋定位不穩定的問題，基于RSS空間線性相關性提出一種新穎的位置指紋定位算法。在每個參考點分別采集多組RSS樣本形成特征矩陣，并構建離線位置指紋數據庫。定位時，通過計算實時RSS矩陣與指紋庫參考點相關性，得到最相關的k個參考點，利用二次加權質心算法計算用戶的最終位置。為了有效降低信號時變性的影響，采樣時進行了濾波、排序等處理，構建離線指紋數據庫時盡量增加采樣次數，但需要對樣本進行聚合處理以適應定位相關性計算。實驗結果表明，該算法在保證較高定位準確度的同時，針對不同終端有更好的定位穩定性。

室內定位；位置指紋；線性相關；加權質心算法

1 引言

隨著無線網絡的廣泛普及和移動智能終端的迅猛發展，室內定位受到越來越多的關注。由于室內空間比較狹小，無線電波的傳播方式非常復雜，大多數的定位方法難以實現穩定的定位效果。

目前用于室內定位的主要方法有基于信號到達時間（time ofarrival，TOA）[1]、基于信號到達時間差（time difference of arrival，TDOA）[2]、基于信號到達角度（angle ofarrival，AOA）[3]、基于接收信號強度（received signal strength，RSS）和基于信道狀態信息（channel state information，CSI）[4]等。基于RSS的定位方法是根據信號強度隨傳播距離變化的規律實現定位，相比于其他定位方法，開發成本低、定位精度較高，是現今主流的室內定位方法[5]。

研究人員已經針對RSS定位方法開展了大量的研究工作，并取得了一定的研究成果。參考文獻[6]提出一種考慮室內環境布局等因素的無線傳播模型，有利于提高定位精度；參考文獻[7]根據目標AP（access point，接入點）距離采用簡單質心算法與加權質心算法進行定位計算，解決測試點距離AP位置較遠時準確性不高的問題；參考文獻[8]提出基于矩陣相關（matrix correlation，MC）的位置指紋定位算法，算法能充分利用RSS樣本信息，具有較精確的定位效果；參考文獻[9]提出了一種抗多徑和陰影的視距指紋定位算法，降低了環境對室內定位精準度的影響；參考文獻[10]提出一種基于主成分分析 （principal component analysis，PCA）白化RSS的聚類算法，以增強指紋庫穩定性，使定位誤差在2 m內的概率提高44.8%。上述方法雖然在特定環境下提高了室內定位的精確度，但針對不同終端，由于硬件及采用的無線技術不同，使得定位穩定性較差。參考文獻[11]提出使用同一位置不同 AP的信號強度差值（signal strength difference，SSD）來消除環境的干擾，可以在一定程度上降低終端異質的影響，但定位精準度受到影響。

上述研究工作并未針對不同終端下定位穩定性差的問題做出深入的研究和探索，導致現有的室內定位方法在不同終端情況下穩定性較差。本文針對此問題，充分利用信號強度信息，結合室內定位基本流程提出一種新穎的位置指紋定位算法。將RSS空間線性相關性作為定位度量標準，通過計算實時采集的 RSS數據與指紋樣本數據的線性相關系數，選取候選參考點利用二次加權質心算法進行定位，該算法不僅能保證定位精度，在不同終端定位時有更好的穩定性。

2 RSS特性分析

將某一位置采集到的多個AP信號強度信息稱為RSS樣本，當室內環境能夠收到足夠數目（如4個以上）的 AP信號時，在任意兩個位置上獲取的RSS樣本和位置的物理距離存在很強的相關性，這種相關性會隨著位置間距的增大而減小，同時也受終端設備差異性的影響。本節分析了不同位置、不同終端下RSS的空間線性相關性，為本文提出的定位算法提供理論基礎。

2.1 不同位置RSS空間線性相關性

RSS能在一定程度上描述兩個位置點環境的近似程度[9]，對一個具體的AP、MT（mobile terminal，移動終端）組合，假定P（d）和P（d0）分別表示與AP相距任意距離d和參考距離d0處的接收信號強度，則有：

其中，PAP是 AP的發送功率；GAP是AP的天線增益；GMT是 MT的天線增益；f是系統損耗因子；λ是無線信號的波長；β是路徑損耗因子；X是一個正態隨機變量，X～N（0，σ2）。

由式（1）可知，假設外界環境相同，即硬件參數、系統損耗等因素不變，RSS主要依賴于終端與AP的距離d。當它們位置比較接近時，終端所能采集的RSS樣本也比較相似，本文利用皮爾遜相關系數來描述這種空間相關性。計算相鄰位置RSS樣本相關系數，由于RSS樣本比較相似，所以計算出的相關系數趨于1，把這種相鄰位置RSS樣本強相關稱為空間線性相關。

可是實際情況下，RSS受到AP和MT的硬件參數以及外界環境的影響而產生波動。為了更有效地表示RSS空間線性相關性，需要對測量的RSS進行濾波處理，并用多組RSS樣本信息構建矩陣來描述位置點的指紋信息。

2.2 不同終端下RSS空間線性相關性

目前大多數的移動終端都具有測量AP RSS的能力，由于不同終端所采用的無線技術及硬件存在差異，同一位置每次所獲取的AP RSS往往有波動，這就對室內定位造成了一定的難度。

根據式（1），兩個不同終端在同一位置對某AP的RSS觀測值如下：

由P（d）1-P（d）2可得：

從式（3）可以看出，對不同終端RSS值做差后，結果和AP配置幾乎無關，盡管結果受到終端天線增益G、系統損耗因子f、路徑損耗因子β、隨機變量X等因素的影響，但當外界條件相同時，這些配置一般是保持不變的，因此，不同終端的差值趨于一個常量。由此可知，各終端所采集的RSS樣本值是線性相關的，將這種特性作為定位度量標準可以有效屏蔽終端的差異性。

為了驗證這個結論，在杭州電子科技大學第一教學樓403實驗室，利用3種不同移動終端分別采集接收到的20個AP的強度，進行了實驗對比，結果如圖1所示，圖1中每一個點是對相應AP進行多次RSS測量的均值，實驗也表明了RSS的線性相關性。從圖1中還可以分析出，當RSS較強時，這種相關性比較明顯；當RSS較弱時，相關性不太明顯，因此在定位階段，應該做好AP的選擇，摒棄較弱的AP。

3 基于RSS空間線性相關定位方法

3.1 概述

由第2節分析可知，RSS具有顯著的空間線性相關性，對于不同終端，雖然信號接收能力存在差異，但是采集的RSS樣本也存在這種空間線性相關性，充分說明了RSS空間線性相關性對室內定位具有積極的意義。

在室內定位系統中，如何克服終端設備的差異性對定位精度以及穩定性的影響，進而實現精確、穩定的定位系統是室內定位領域的重點和難點。基于RSS位置指紋定位技術包括離線指紋庫構建和在線定位兩個階段[12]。本文將RSS空間線性相關性應用于上述兩個階段，在每個參考點采集多組RSS樣本形成特征矩陣，充當指紋，通過皮爾遜相關系數計算實時RSS數據與指紋庫 RSS信息相關系數，最后利用二次加權質心算法計算最終位置。總體框架如圖2所示。

基于RSS空間線性相關性的室內定位算法的過程可概括如下。

（1）離線指紋數據庫構建階段

該階段主要工作是進行數據采集，構建能夠描述位置信息的指紋數據庫。其中包括數據采集、數據過濾和數據處理。針對數據采集，首先在目標定位環境中設計若干個參考點，通過移動設備在每個參考點采集多組RSS樣本信息，得到原始訓練數據集；針對數據過濾，由于室內環境比較復雜以及信道擁塞，導致移動設備接收的RSS信息存在時變性，因此需要采用數據過濾規則對原始RSS數據集進行過濾處理，提高訓練樣本質量，本文采用限幅平均濾波法對RSS信息進行過濾處理；針對數據處理，首先對 RSS樣本進行排序處理，以增強與在線采集的RSS數據的相關性，其次，為了保證與在線RSS數據有相同的維度，需要對RSS樣本進行聚合處理，最終得到參考點指紋信息。

（2）在線定位階段

圖1 同一位置不同終端分別采集多個AP的RSS樣本對比

圖2 定位系統總體框架

該階段的主要工作是通過比較終端實時獲取的RSS數據與指紋庫中的RSS數據，將信號強度最相似的參考點的位置估計為目標定位結果。其中包括RSS信息采集、數據過濾、空間線性相關性計算和最終位置估算。針對 RSS信息采集，在現階段連續采集多組RSS樣本信息，作為待預測位置的原始 RSS特征信息；針對數據預處理，對原始RSS樣本信息進行濾波和排序處理，得到描述待預測位置的RSS特征矩陣；針對空間線性相關性計算，通過計算待預測位置 RSS特征矩陣與離線指紋庫各參考點指紋皮爾遜相關系數，確定最相似的k個參考位置點；針對位置估算，由于最終確定的k個相似位置點中常存在偏離用戶當前位置較遠的參考點，這些點會嚴重影響定位精度，所以利用二次加權質心算法進行位置估算，得到用戶的最終位置。

3.2 離線指紋數據庫構建階段

由第3.1節可知，離線階段首先需要RSS數據采集以及數據處理。假設目標定位環境有 P個 AP用于定位，移動設備在物理位置l處第n次采集的RSS樣本信息為其 中 p= 1,2，…,P，rssl,n,p表示參考點l處第n組RSS樣本中第p個AP的信號強度。

對參考點 l多次采集的 RSS樣本進行過濾后，得到N組RSS樣本序列，用矩陣Fl表示：

其中，rssl,n,p表示參考點 l第 n組 RSS信息中第 p個AP的RSS值。

Fl的第p行表示參考點l對第p個AP的多次RSS信息采集，為了增強離線指紋庫與在線RSS數據的相關性，對同一AP多次采集的RSS進行排序，即對矩陣Fl每一行排序，使矩陣滿足：

離線指紋庫構建時，采集的RSS組數越多，越能形象描述參考位置空間特性，定位精確度越高。在實時定位時，終端也需要采集相應組數RSS樣本，這就使得定位速度緩慢。要做到快速定位，需要對矩陣Fl聚合處理，使得定位階段需要采集的RSS樣本較少。

3.3 在線定位階段

離線階段通過數據過濾與處理，去除了訓練樣本中不穩定、非正常的RSS數據，得到能較準確描述參考位置的離線指紋數據庫。在線定位過程中，采集到待定位的實時RSS數據，也要對RSS數據進行濾波、排序等處理，然后對比實時RSS數據與參考點指紋相關性，通過皮爾遜相關系數描述這種相關性，對最相關的k個參考點，利用二次加權質心算法計算用戶的最終位置。

3.3.1 基于RSS線性相關系數計算

在待定位區域，終端采集m組通過濾波處理的RSS樣本，構建成一個P×M維的RSS測量矩陣，對RSS測量矩陣的每一行進行排列，需要和指紋庫構建時排序規則相同，即可得到需要的在線RSS矩陣F*：

根據皮爾遜相關系數計算在線終端接收樣本與指紋數據庫樣本的線性相關系數rl，為：

將所述Q個相關系數計算好后，對其進行降序排序，從大到小取k個相關系數所對應的參考點{P1P2…Pk}，Pk=（xkykrk）。Pk表示所述Q個相關系數降序排序后的第k個相關系數所對應的參考點信息，（xk，yk）分別是第k個相關系數所對應的坐標值，rk表示第k個相關系數。然后，運用加權質心算法，求出用戶的最終位置點。

3.3.2 二次加權質心算法進行位置估算

質心算法是將最終確定的 k個相似參考點組成多邊形，用該多邊形質心代表估算位置。由于該k個相似位置點中常存在偏離用戶當前位置較遠的參考點，采用傳統的質心算法會受到這些點的干擾，影響定位精度。如圖3所示，參考點 A、B、C、D、E在待定位位置S周圍呈不均勻分布，質心算法結果將最終位置定位在I點。在圖 3所示的3種情況中，均是參考點A和E離待定位位置S的實際距離較遠，由于其產生的負面作用，使得估算出的位置I不同程度地偏向A和E點，待定位位置的實際位置距A和E越遠，偏離程度越大。

本文用二次加權質心算法來計算用戶的最終位置，第一次質心算法預算出初始位置，第二次質心算法中，首先將距離初始位置較遠的坐標歸并為有用的參考點，然后再進行一次加權質心算法估算用戶最終位置，如圖4所示，將A、E歸并為F點，再利用B、C、D、F組成的多邊形的質心I充當定位的位置。

二次加權質心算法具體計算過程如下。

（1）一次加權質心算法計算

將k個相似參考點信息拆分為兩個數組VX和VY：

其中，VX和VY表示所述k個相關系數所對應的參考點信息中x坐標數組和y坐標數組，vxk和vyk表示第k個相關系數對應參考點的x坐標和y坐標信息。

對所述 k個位置節點利用加權質心算法進行第一次計算，算出初始位置坐標質心算法如下：

圖3 參考點分布不均勻時定位誤差示意

圖4 二次加權質心處理原理

其中，k表示所述Q個相關系數降序排序后取得的參考點數量，ri表示第 i個參考點所對應的相關系數，（xi，yi）分別表示第i個參考點對應的位置坐標信息。

（2）二次加權質心算法計算

4 實驗與結果分析

對于本文所提出的算法，搭建了實際環境并進行了相應的實驗，實驗環境部署在杭州電子科技大學第一教學樓403實驗室，為長22.5 m、寬14 m的矩形場地，室內布置4個AP，分別在4個角落。對加權K近鄰（W K NN）定位算法[13]、矩陣相關定位算法[8]和基于信號強度差定位算法[9]與本文定位新算法進行比較實驗。

（1）實驗1

定位與指紋庫構建階段，采用相同終端情況下，采用不同的參考點間距，分別測試4種定位算法平均誤差，如圖5所述。定位誤差定義為：

其中，（xi，yi）表示第 i個測試點的實際物理坐標，（xi,1oc，yi,1oc）表示第 i個測試點的估算位置坐標。

圖5 W K NN、MC、SSD與本文算法定位誤差比較

圖5中可以看出當距離為 0.5～1.5 m時，4種定位算法精度都較高，其中本文算法定位誤差最小，當大于1.5 m時，定位誤差明顯增大。考慮到采樣間距太小會使得采集指紋的工作量增大，因此后續的實驗采取1 m作為構建離線指紋庫時采樣點間距。當取1 m作為采樣間距時，本算法的平均定位誤差為1.96 m，相比W K NN算法2.37 m與SSD算法2.45 m有較大的提升，比MC算法的2.13 m提升了0.17 m。

（2）實驗2

定位與指紋庫構建階段，采用相同終端情況下，對不同位置定位誤差波動性進行對比實驗。

圖6給出了W K NN、MC、SSD與本算法在25個采樣點的誤差對比結果。從整體上看，相比于W K NN算法和SSD算法，本算法定位誤差波動性較小，相比于MC算法，定位誤差波動相似。

（3）實驗3

定位與指紋庫構建階段，采用不同終端進行對比實驗。指紋庫構建采用華為榮耀7手機，定位時分別采用華為榮耀7、紅米Note 2、中興u956手機。圖7分別給出了W K NN、MC、SSD與本算法定位誤差累計概率的比較結果。

從圖7可以看出，本文算法在誤差距離為 5 m時，定位誤差累計概率趨于1，而SSD算法、W K NN算法和MC算法分別需要誤差距離達到7 m、6.5 m和5.5 m，這也就驗證了實驗1的結論。在不同終端條件下，圖7顯示了使用W K NN算法時，不同終端差異化比較明顯，說明該算法受終端異質的影響較大，而MC算法和SSD算法相對于W K NN算法，受終端異質的影響較小，而本文提出的算法受終端異質影響最小。因此可以得出，本文算法相對于其他3種算法，在不同終端定位下有更好的穩定性，并且相比于W K NN算法和SSD算法，在定位精度方面有明顯的優勢。

圖6 W K NN、MC、SSD與本文算法在各個定位點誤差

圖7 不同算法下不同終端定位誤差累計概率比較

5 結束語

針對RSS時變性以及不同終端信號接收能力差異性的問題，本文提出了基于RSS空間線性相關的WLAN室內定位算法，該算法利用特征矩陣充當參考點的指紋信息，利用相關系數作為相似性度量標準，采用二次加權質心算法估算用戶的最終位置。通過實驗結果可以看出，本文算法有較高的定位精度，平均定位誤差可以達到1.96 m，并且本算法可以有效降低不同終端信號接收能力差異性對定位性能的影響。考慮到目前的智能終端都內置很多先進的傳感器原件，因此在后續的研究中，計劃將多傳感器與位置匹配算法融合來進一步提升定位的精度。

[1]AL-JAZZAR S,CAFFERY J J,YOU H R.A scattering model based approach to NLOS mitigation in TOA location systems[C]// IEEEVehicularTechnology Conference,May6-9,2002,Birmingham, England.New Jersey:IEEE Press,2002:861-865.

[2]YAMASAKIR,OGINO A,TAMAKIT,etal.TDOA location system for IEEE 802.11b WLAN[C]//IEEE Wireless Communications and Networking Conference,March 13-17,2005,New Orleans, USA.New Jersey:IEEE Press,2005:2338-2343.

[3]XIE Y Q,WANG Y,ZHU C,et al.Grid search based hybrid TOA/AOA location techniques for NLOS environments[J].IEEE Communications Letters,2009,13(4):254-256.

[4]HALPERIN D,HU W,SHETH A,et al.Predictable 802.11 packet delivery from wireless channel measurements[J].ACM Sigcomm Computer Communication Review,2010,40(4): 159-170.

[5]HOSSAIN A K M M,SOH W S.A survey of calibration-free indoor positioning systems[J].Computer Communications,2015(66):1-13.

[6]NARZULLAEV A,PARK Y,YOO K,et al.A fast and accurate calibration algorithm for real-time locating systems based on the received signal strength indication[J].AEU-International Journal of Electronics and Communications,2011,65(4):305-311.

[7]劉暢,張迅.WLAN接入點的室內定位技術 [J].電信科學, 2015,31(2):135-139．LIUC,ZHANGX.WLANaccesspointindoorpositioningtechnology[J]. Telecommunications Science,2015,31(2):135-139.

[8]SUNYL,XUYB.Errorestimation method formatrixcorrelation-based W i-Fi indoor localization[J].KSII Transactions on Internet& Information Systems,2013,7(11):2657-2675.

[9] 陳永樂,朱紅松,孫利民.一種抗多徑和陰影的視距指紋定位算法[J].計算機研究與發展,2013,50(3):524-531. CHEN Y L,ZHU H S,SUN L M.A line of sight fingerprint localization algorithm resisting multipath and shadow[J].Journal of Computer Research and Development,2013,50(3):524-531.

[10]楊明極,劉愷懌,邵丹.用于WLAN室內定位的PCA聚類算法[J].電信科學,2016,32(7):21-26. YANG M J,LIU K Y,SHAO D.PCA clustering algorithm for indoor positioning in WLAN[J].Te lecommunications Science, 2016,32(7):21-26.

[11]CHANG N,RASHIDZADEH R,AHMADI M.Robust indoor positioning using differential wi-fi access points [J].IEEE Transactions on Consumer Electronics,2010,56(3):1860-1867.

[12]GENTILE C,ALSINDI N,RAULEFS R,et al.Geolocation techniques:principles and applications[M].Berlin:Springer Publishing Company,2014:64-70.

[13]XUYB,ZHOUM,MENGWX,etal.Optimal K NNpositioning algorithm via theoreticalaccuracy criterion in WLAN indoor environment[C]// 2010 IEEE Global Telecommunications Conf,Dec 6-10,2010, Miami,USA.New Jersey:IEEE Press,2010:1-5.

Fingerprint localization algorithm based on linear spatial dependence of WLAN RSS

XU Xiaoliang1,GAO Jian1,HUANG He2,MA Zhe2
1.School of Computer Science and Technology,Hangzhou Dianzi University,Hangzhou 310018,China 2.Zhongzhexin Consulting Co.,Ltd.,Hangzhou 310007,China

Due to RSS time-varying and difference of signal receiving ability of different terminals,the performance of RSS-based technologies is usually instability.In order to solve such problem,a novel fingerprint localization algorithm based on linear spatial dependence of RSS was proposed.Multiple sets of RSS samples were collected at each reference point to form a feature matrix and an offline location fingerprintdatabase was conducted.When the real-time RSS matrix was used to calculate the correlation between the real-time RSS matrix and the reference point of the fingerprint library, the k-reference points were obtained,and the final position of the user was calculated by the quadratic weighted centroid algorithm.In order to effectively reduce the influence of signal time-varying,the sampling and sorting process were carried out,and the number of sampling times increased as much as possible when constructing the offline fingerprint database,but the samples needed to be aggregated to fit the positioning correlation calculation.Experiment results show that the proposed algorithm can guarantee the high positioning accuracy and also achieve the better stability for different term inal.

indoor localization,location fingerprint,linear dependence,weighted centroid algorithm

TN911

：A

10.11959/j.issn.1000-0801.2017064

徐小良（1976-），男，杭州電子科技大學計算機學院教授、碩士生導師，主要研究方向為無線網絡、大數據處理、人工智能等。

高健（1991-），男，杭州電子科技大學計算機學院碩士生，主要研究方向為無線與移動通信。

黃河（1991-），男，中浙信科技咨詢有限公司工程師、技術經理，主要研究方向為數據通信。

馬哲（1982-），男，博士，中浙信科技咨詢有限公司工程師，主要研究方向為大數據分析。

2017-01-10；

2017-03-03

國家青年科學基金資助項目（No.61602410）

Foundation Item:The National Science Foundation for Young Scientists of China(No.61602410)