基于卡方距離改進的WLAN室內定位算法

陶 崢，王洪玉

(1.大連理工大學電子信息與電氣工程學部，遼寧大連 116024; 2.解放軍92124部隊，遼寧大連 116023)

基于卡方距離改進的WLAN室內定位算法

陶 崢1，2，王洪玉1

(1.大連理工大學電子信息與電氣工程學部，遼寧大連 116024; 2.解放軍92124部隊，遼寧大連 116023)

基于WLAN的定位服務現今已成為智慧城市中一個很有吸引力的研究領域。在各種定位算法中，經典歐氏距離法的度量方式只考慮各實際位置點RSS向量之間的絕對距離，往往忽視各實際位置點RSS向量之間的相對距離;并且只能給各AP賦予相同的權重。為克服歐氏距離法的不足，提出了基于卡方距離及靈敏度法的WLAN室內定位方法(CSKNN)。該方法利用位置指紋信息建立參考點的指紋信息和測試點的指紋信息，然后利用更能反映特征量之間相對距離的卡方距離并結合靈敏度法對各AP權重進行修正，得出在當前定位環境中各AP在定位系統中的貢獻，用加權后的卡方距離依據各參考點的指紋信息計算待定位點的位置。結果表明，該方法比傳統的歐氏距離法精度高。

室內定位;無線局域網;位置指紋;卡方距離;靈敏度法

0 引言

當今，隨著智能手機和平板電腦的興起，基于位置的服務(Location Based Service，LBS)吸引了越來越多的IT企業參與定位系統的設計。傳統的定位服務通常來自GPS或基站信號。雖然GPS的定位精度可以達到1～2 m，但當用戶進入室內環境時GPS信號就會變得很弱。基站信號雖然可以從任何環境中獲得，然而定位誤差卻往往大于1 km。因此，為了滿足室內定位系統(比如大型地下車庫車輛引導系統和商場導航系統)的需要，諸如基于RFID，WIFI和藍牙等定位技術被相繼提出。然而，由于智能移動終端設備硬件結構的限制，基于WIFI的定位技術被普遍應用于室內定位導航［1-3］。

人們經常用無線訪問接入點(Access Point，AP)發射和接收信號并可在無線接收范圍內測得信號強度。任何信號都會在傳播過程中進行衰減以致人們能用它估計用戶設備與信號源之間的距離，如果在各個方向上都有足夠的AP，那么用戶的當前位置就會被唯一確定。一般情況下，可以利用來自各個AP的信號強度值組成的向量，即RSS(Received Signal Strength)向量，作為每一個實際位置點的指紋信息(也稱實際位置點RSS向量)。通過比較這些向量之間的距離就可以得到實際位置之間的距離［4-5］。假如用戶能在一個特定的場景中采集到足夠的位置指紋信息，就可以粗略地估計用戶的實際位置。很多商業應用軟件已經開始使用該技術來對用戶進行定位和導航。然而，信號衰減受到天氣、障礙物、氣流等多種因素影響。這些影響有時會導致無法找到最優匹配的RSS向量以及定位錯誤［6］。

1 WLAN位置指紋定位方法

21世紀初，位置指紋定位技術開始應用于WLAN室內定位中。在無線局域網環境中，位置指紋定位技術利用信號強度來對用戶的移動設備進行定位。該技術先利用參考點的RSS向量建立針對環境的位置指紋地圖，然后利用該地圖對持有移動設備的用戶進行定位。

位置指紋定位技術分為兩個階段:離線訓練階段和在線定位階段。如圖1所示，在離線訓練階段，將N 個AP置于定位環境中，并在定位環境中均勻布置若干個參考點，參考點的數目和參考點之間的間隔由系統設計者決定。用戶利用筆記本電腦將各參考點接收自每一個AP的信號強度值組成的RSS向量存儲到數據庫中。在在線定位階段，待定位者可能在房間內任何一個位置，不一定在參考點上。在這個階段定位系統將待定位者設備接收各AP獲得的RSS向量和數據庫中各參考點的RSS向量進行比較，然后選取離用戶設備獲得的RSS向量最接近的幾個參考點對應的坐標經過加權計算后的值作為定位結果［7-8］。

1.1 經典位置指紋匹配算法

在位置指紋定位研究領域中，關于RSS向量匹配算法的研究成果比較豐富，諸如歐氏距離、概率分布、神經網絡、支持向量機、稀疏表示等等。這里主要介紹歐氏距離法［9-10］。

傳統的加權K近鄰法通常使用歐氏距離作為距離的度量。歐氏距離給出兩點之間的絕對距離，在二維空間如式(1)所示:

其中，(x1，y1)和(x2，y2)是兩點坐標。

當用歐氏距離定位用戶，式(1)就改進成式(2):

其中，si為待定位點用戶設備測到第i個AP的信號強度;dij為位置指紋庫中第j個參考點接收到第i個AP的信號強度。

在離線訓練階段，在定位區域內布置h個參考點并測量各參考點接收來自每一個AP的RSS值組成的RSS向量，利用這些參考點所獲得的RSS向量及其對應的物理坐標一同構建位置指紋庫。

在在線定位階段，歐氏距離通過搜索位置指紋庫中的每個參考點找到距離待定位點距離最近的那個參考點，即找到最小的Lj，此法稱為最近鄰法(NN)。在定位算法中，假定每一個獲得的RSS向量都可以代表定位場所中的一個實際物理位置。

如果選取Lj值較小的K(K≥2)個參考點為預定位參考點，并計算其對應坐標的平均值作為定位結果，即為K近鄰法(KNN)。計算方法如下:

與原始的最近鄰法相比，該法引入了K個估計位置坐標來計算待定位點的位置，對定位精度有一定的提升。

進一步根據不同預定位參考點對定位結果的貢獻不同，計算預定位參考點坐標加權后的和作為定位結果，即為加權K近鄰法，如式(4)所示:

其中，wj為預定位參考點j的權重因子，其值主要取決于預定位參考點和待定位點之間的歐氏距離Lj，計算方法如式(5)所示:

如果wj計算結果為，即為K近鄰法。

K近鄰法因其簡單和實用等特點已成為一種非常流行的定位算法。

然而，KNN定位算法在位置指紋定位工程應用中也存在一些問題:一是傳統KNN定位算法應用的歐氏距離度量方式只考慮各RSS向量間的絕對距離，忽視了各RSS向量間的相對距離;二是AP的權重對分類精度的影響較大，不同AP對分類準確性的影響是不同的，而以往用于KNN分類計算的歐氏距離度量方式只能將不同AP賦予相同的權重，忽視了AP因素給定位造成的影響。忽視AP因素使經典KNN定位算法對環境噪聲比較敏感，在某些待定位點上容易因為環境噪聲的影響而導致誤差偏大。

1.2 基于卡方距離及靈敏度法的位置指紋定位算法

針對這些問題，文中提出了基于卡方距離及靈敏度法的位置指紋定位算法(CSKNN)。首先利用位置指紋信息建立參考點的指紋信息和測試點的指紋信息，然后利用更能反映特征量之間相對距離的卡方距離并結合靈敏度法對AP權重進行修正，得出在當前定位環境下各AP在定位系統中的貢獻，然后用加權后的卡方距離依據各參考點的指紋信息計算待定位點的實際位置。文中提出的定位算法包括離線訓練和在線定位兩個階段。

1.2.1 離線訓練階段

在離線訓練階段，先利用卡方距離結合靈敏度法依據定位區域內的位置指紋信息修正AP的權值。

(1)卡方距離。

使用不同的距離定義方式，可以對分類算法的準確率造成直接影響。以往的距離計算方式如歐氏距離、L1范數等只考慮特征量之間的絕對距離，忽視了特征量之間的相對距離。實際上對于分類來說，相對距離往往更有實際意義?？ǚ骄嚯x可以有效反映特征量之間相對距離的變化，因此用卡方距離構建的分類算法可以獲得更優的分類性能［11-13］?？ǚ骄嚯x還可以根據各特征量對分類算法的貢獻不同，結合靈敏度法計算在卡方距離的計算方式下每個特征量的權重。

假設兩個直方圖X，Y是非負且有界的，構造相似度加權矩陣A，則X，Y之間的二次式距離如式(6):

如果矩陣A是X，Y協方差矩陣的逆，則該二次式距離就是馬氏距離(Mahalanobis distance)。如果矩陣A是單位陣，則該二次式距離就是歐氏距離。將該二次式距離和卡方距離結合，就形成了二次卡方距離［14］(Quadratic Chi-squared distance，QC)，如式(7)所示:

從式(7)可以看出，二次卡方距離是二次式距離的標準形式，其中m為規格化參數，當A為單位陣且m=0.5時，式(7)可變成式(8):

式(8)就是卡方距離，當m=0時，式(7)就變成二次式距離。

從上面的推導可以看出，卡方距離和馬氏距離、歐氏距離一樣能夠對特征量進行有效度量。

文獻［14］還證明了卡方距離具有相似矩陣量化不變性(similarity matrix quantization invariance property)和稀疏不變性(sparseness invariance property)。

卡方距離已被應用到很多用距離描述的分類問題中，并且都取得了相當優異的效果?？ǚ骄嚯x如式(9)所示:

將該式變換到WLAN位置指紋定位工程應用領域，如式(10)所示:

其中，si為待定位點用戶設備測到第i個AP的信號強度;dij為位置指紋庫中第j個參考點接收到第i個AP的信號強度。

(2)靈敏度法。

在位置指紋定位的工程應用中，卡方距離體現了各實際位置點接收來自各AP的RSS值組成的RSS向量之間的相對關系，但是仍然對每個AP賦予相同的權重，在WLAN位置指紋定位的實際環境中不同AP對定位的貢獻不同。因此，應在卡方距離的基礎上采用靈敏度法，對不同的AP賦予不同的權重以降低環境噪聲的影響，AP權重的計算方法如下所示:

利用采集的位置指紋信息建立位置指紋數據庫，把位置指紋信息分為參考點的指紋信息和測試點的指紋信息。具體方法為，先在定位區域內布置參考點，采集參考點的指紋信息，然后在每一個參考點周圍布置若干個測試點，采集測試點的指紋信息。

首先，利用卡方距離依據各參考點的指紋信息對離該參考點最近的若干個測試點進行定位，當某測試點獲得的來自各AP的RSS向量和該參考點獲得的來自各AP的RSS向量之間的卡方距離為最大，而它們的實際物理距離為非最小時，即視為該測試點定位錯誤。統計定位錯誤的測試點個數n。

每次在定位系統中去除第 i(i=1，2，…，R)個AP，再用上述方法對測試點進行定位，統計定位錯誤的測試點個數ni。

其中，wi滿足wi=1。

1.2.2 在線定位階段

在離線訓練階段采用卡方距離度量和靈敏度法計算在實際定位區域中不同AP的權重，在在線定位階段應用新的距離度量函數依據參考點的指紋信息對用戶設備進行定位，具體步驟如下所示:

第一步:采集待定位點用戶移動設備接收來自各AP的RSS值，組成待定位點RSS向量。

第二步:根據權重修正后的卡方距離，計算待定位點RSS向量和各參考點RSS向量之間的距離，具體計算方式如式(12):

其中，wi為當前定位系統中第i個AP的權重;si為待定位點用戶設備測到第i個AP的信號強度;dij為位置指紋庫中第j個參考點接收到第i個AP的信號強度。

第三步:將第二步得到的距離按降序排列，選取Lj值較大的K(K≥2)個參考點作為預定位點，利用式(13)計算最終的定位結果。

其中，(xj，yj)為預定位參考點j的坐標。

總體來說，提出的CSKNN算法包括如下幾點:

(1)在WLAN位置指紋定位中利用卡方距離替代歐氏距離進行定位運算。

(2)將定位系統分為離線訓練和在線定位兩個階段。在離線訓練階段，把采集的位置指紋信息分為兩類:參考點的指紋信息和測試點的指紋信息;利用參考點和測試點的指紋信息依據卡方距離和靈敏度法對AP的權重進行修正。

(3)在在線定位階段，運用步驟2加權后的卡方距離依據參考點的指紋信息計算待定位點的坐標。

CSKNN定位算法在離線訓練階段和在線定位階段的基本流程如圖2和圖3所示。

2實驗

定位實驗在大連理工大學創新園大廈C區2樓走廊處進行。實驗區域包括一個長走廊，兩個短走廊，若干辦公室和實驗室。該區域電子設備較多，工作日課間人員流動量大。

在實驗區域共布置6個AP，AP的具體信息為TP -Link TL-WR340G+54 M單天線無線寬帶路由器1臺，思科WRVS4400N千兆三天線路由器2臺，思科RV180W Wireless-N多功能路由器3臺。實驗所用AP為布置的6個AP。實驗分析所采用的數據完全是真實測得，實驗過程沒有用到任何仿真數據。實驗環境如圖4所示。

實測設備為裝配了D-Link DWA-125無線網卡和Netstumbler采集軟件的阿圖木X20A-W125上網本，實測的位置指紋信息為各參考點和測試點接收來自實驗布置的6個AP(標記為MMCL1-MMCL6)的RSS值組成的RSS向量，單位為dBm。

采集位置指紋信息并建立位置指紋庫，把位置指紋信息分為參考點的指紋信息和測試點的指紋信息，其中1/5為參考點的指紋信息，4/5為測試點的指紋信息。具體方法為先采集參考點的指紋信息，再在每個參考點周圍選取4個點作為該參考點的測試點并采集指紋信息，在實驗環境(圖4網格區域)中共放置24個參考點和96個測試點，并標定好這些參考點和測試點的坐標。利用上述卡方距離結合靈敏度法的方法，修正在待測實驗環境中每個AP在定位系統中的權重，在在線定位階段利用加權后的卡方距離依據各參考點的指紋信息，計算待定位點的坐標。

為了驗證文中方法，分別利用歐氏距離法和卡方距離結合靈敏度法依據實驗環境中的位置指紋信息，對待定位點進行定位。

實驗中分別計算上述二種定位方法在每一個待定位點上的定位誤差，定位誤差由計算位置和實際位置的歐氏距離度量，如式(14)所示:

其中，(xreal，yreal)為第m個待定位點的實際物理坐標;(xcalc，ycalc)為定位算法計算得出的第m個待定位點的坐標。

選出9級數據對比，如表1所示。

在位置指紋定位的工程應用中，常常采用累積分布函數(Cumulative Distribution Function，CDF)來評判位置指紋定位算法的優劣。累積分布函數主要用來表征定位誤差門限以下的定位次數與總的定位次數之間的比值。累積分布函數也稱作累積誤差分布(Cumulative Error Distribution，CED)。

兩種方法得到的累計誤差分布曲線圖見圖5。

定位標準差用式(15)來衡量:

最終獲得的定位結果:采用歐氏距離法獲得的定位誤差平均值為1.792 7 m，標準差為0.873 1 m;使用文中方法獲得的定位誤差平均值為1.414 6 m，標準差為0.814 8 m。

通過圖5可以看出，歐氏距離法對環境噪聲比較敏感，在受環境噪聲影響較大的待定位點定位誤差較大，利用文中提出的定位算法可以比歐氏距離更好地對抗環境噪聲，以整體提高定位精度。

3 結束語

文中提出一種基于卡方距離和靈敏度法結合的算法(CSKNN)來實現人或物的WLAN定位。CSKNN算法是一種基于距離計算方式改進的KNN算法，其將距離的計算方法從歐氏距離變為了卡方距離。算法能夠根據不同的室內環境特點在算法中給各AP賦予不同的權值，有效降低了復雜室內環境對定位精度的負面影響，整個定位系統不用添加任何額外的硬件即可實現。實驗結果表明，該算法的定位精度明顯優于原始的歐氏距離法。

［1］ Khan A U，Al-Akaidi M.A distributive algorithm for WLAN localization［C］//Proc of 6th international conference on emerging technologies.［s.l.］:IEEE，2010:388-393.

［2］ Gu Y，Lo A，Niemegeers I.A survey of indoor positioning systems for wireless personal networks［J］.IEEE Communications Surveys＆Tutorials，2009，11(1):13-32.

［3］ Zhou M，Zhang Q，Tian Z，et al.IMLours:indoor mapping and localization using time-stamped WLAN received signal strength［C］//Proc of wireless communications and networking conference.［s.l.］:IEEE，2015:1817-1822.

［4］ Ding G，Zhang J，Zhang L，et al.Overview of received signal strength based fingerprinting localization in indoor wireless LAN environments［C］//Proc of 5th international symposium on microwave，antenna，propagation and EMC technologies for wireless communications.［s.l.］:IEEE，2013:160-164.

［5］ 孫善武，王 楠，陳 堅.一種改進的基于信號強度的WLAN定位方法［J］.計算機科學，2014，41(6):99-103.

［6］ 徐玉濱，鄧志安，馬 琳.基于核直接判別分析和支持向量回歸的WLAN室內定位算法［J］.電子與信息學報，2011，33(4):896-901.

［7］ 劉洺辛，孫建利.基于能效的WLAN室內定位系統模型設計與實現［J］.儀器儀表學報，2014，35(5):1169-1178.

［8］ 程金晶，魏東巖，唐陽陽.WLAN指紋定位中AP選擇策略研究［J］.計算機技術與發展，2015，25(3):1-5.

［9］ Sohn I.Localization performance analysis of KNN in IEEE 802.11 TGn channel［C］//Proc of ICT convergence.［s.l.］: IEEE，2011:219-220.

［10］牛建偉，劉 洋，盧邦輝，等.一種基于Wi-Fi信號指紋的樓宇內定位算法［J］.計算機研究與發展，2013，50(3):568 -577.

［11］Bosch A.Image classification for a large number of object categories［D］.Girona:University of Girona，2007.

［12］賈世杰，孔祥維.一種新的直方圖核函數及在圖像分類中的應用［J］.電子與信息學報，2011，33(7):1738-1742.

［13］鄭 倩，盧振泰，陳 超，等.基于鄰域信息和高斯加權卡方距離的脊椎MR圖像分割［J］.中國生物醫學工程學報，2011，30(3):357-362.

［14］Pele O，Werman M.The quadratic-chi histogram distance family［C］//Proc of ECCV 2010.Berlin:Springer，2010:749-762.

Improved WLAN Localization Algorithm Based on Chi-square Distance

TAO Zheng1，2，WANG Hong-yu1
(1.Faculty of Electronic Information and Electrical Engineering，Dalian University of Technology，Dalian 116024，China; 2.PLA 92124 Unit，Dalian 116023，China)

WLAN-based localization service has become a hotspot for smarter city nowadays.Among the localization algorithms，the classical Euclidean distance solely keeps count of the absolute distance between the RSSI vector and overlooks the relative distance between the RSSI vector.And it can only give the same weight to every AP.In order to overcome the defects of Euclidean distance，a new algorithm based on Chi-square distance and sensitivity method for WLAN indoor localization is proposed.The algorithm uses fingerprinting technique to make training dataset and testing dataset，then uses Chi-square distance and sensitivity method to correct the training dataset which will be used in the online localization phase and get the weight of every AP in the algorithm in order to improve positioning accuracy.The results show that the proposed algorithm has better accuracy compared with the classical Euclidean distance.

indoor localization;WLAN;fingerprint;Chi-square distance;sensitivity method

TP391

A

1673-629X(2016)09-0050-06

10.3969/j.issn.1673-629X.2016.09.012

2015-11-30< class="emphasis_bold">修回日期:2

2016-03-08< class="emphasis_bold">網絡出版時間:

時間:2016-08-01

國家自然科學基金資助項目(61172058);高等學校博士學科點專項科研基金(20120041110011)

陶 崢(1984-)，男，工程師，碩士，研究方向為WLAN室內定位技術;王洪玉，教授，博士研究生導師，研究方向為無線網絡。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.036.html