基于卡方距離改進(jìn)的WLAN室內(nèi)定位算法

陶 崢，王洪玉

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

基于卡方距離改進(jìn)的WLAN室內(nèi)定位算法

陶 崢1，2，王洪玉1

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

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

室內(nèi)定位;無線局域網(wǎng);位置指紋;卡方距離;靈敏度法

0 引言

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

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

1 WLAN位置指紋定位方法

21世紀(jì)初，位置指紋定位技術(shù)開始應(yīng)用于WLAN室內(nèi)定位中。在無線局域網(wǎng)環(huán)境中，位置指紋定位技術(shù)利用信號強(qiáng)度來對用戶的移動設(shè)備進(jìn)行定位。該技術(shù)先利用參考點的RSS向量建立針對環(huán)境的位置指紋地圖，然后利用該地圖對持有移動設(shè)備的用戶進(jìn)行定位。

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

1.1 經(jīng)典位置指紋匹配算法

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

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

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

當(dāng)用歐氏距離定位用戶，式(1)就改進(jìn)成式(2):

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

在離線訓(xùn)練階段，在定位區(qū)域內(nèi)布置h個參考點并測量各參考點接收來自每一個AP的RSS值組成的RSS向量，利用這些參考點所獲得的RSS向量及其對應(yīng)的物理坐標(biāo)一同構(gòu)建位置指紋庫。

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

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

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

進(jìn)一步根據(jù)不同預(yù)定位參考點對定位結(jié)果的貢獻(xiàn)不同，計算預(yù)定位參考點坐標(biāo)加權(quán)后的和作為定位結(jié)果，即為加權(quán)K近鄰法，如式(4)所示:

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

如果wj計算結(jié)果為，即為K近鄰法。

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

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

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

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

1.2.1 離線訓(xùn)練階段

在離線訓(xùn)練階段，先利用卡方距離結(jié)合靈敏度法依據(jù)定位區(qū)域內(nèi)的位置指紋信息修正AP的權(quán)值。

(1)卡方距離。

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

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

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

從式(7)可以看出，二次卡方距離是二次式距離的標(biāo)準(zhǔn)形式，其中m為規(guī)格化參數(shù)，當(dāng)A為單位陣且m=0.5時，式(7)可變成式(8):

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

從上面的推導(dǎo)可以看出，卡方距離和馬氏距離、歐氏距離一樣能夠?qū)μ卣髁窟M(jìn)行有效度量。

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

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

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

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

(2)靈敏度法。

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

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

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

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

其中，wi滿足wi=1。

1.2.2 在線定位階段

在離線訓(xùn)練階段采用卡方距離度量和靈敏度法計算在實際定位區(qū)域中不同AP的權(quán)重，在在線定位階段應(yīng)用新的距離度量函數(shù)依據(jù)參考點的指紋信息對用戶設(shè)備進(jìn)行定位，具體步驟如下所示:

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

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

其中，wi為當(dāng)前定位系統(tǒng)中第i個AP的權(quán)重;si為待定位點用戶設(shè)備測到第i個AP的信號強(qiáng)度;dij為位置指紋庫中第j個參考點接收到第i個AP的信號強(qiáng)度。

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

其中，(xj，yj)為預(yù)定位參考點j的坐標(biāo)。

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

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

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

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

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

2實驗

定位實驗在大連理工大學(xué)創(chuàng)新園大廈C區(qū)2樓走廊處進(jìn)行。實驗區(qū)域包括一個長走廊，兩個短走廊，若干辦公室和實驗室。該區(qū)域電子設(shè)備較多，工作日課間人員流動量大。

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

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

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

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

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

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

選出9級數(shù)據(jù)對比，如表1所示。

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

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

定位標(biāo)準(zhǔn)差用式(15)來衡量:

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

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

3 結(jié)束語

文中提出一種基于卡方距離和靈敏度法結(jié)合的算法(CSKNN)來實現(xiàn)人或物的WLAN定位。CSKNN算法是一種基于距離計算方式改進(jìn)的KNN算法，其將距離的計算方法從歐氏距離變?yōu)榱丝ǚ骄嚯x。算法能夠根據(jù)不同的室內(nèi)環(huán)境特點在算法中給各AP賦予不同的權(quán)值，有效降低了復(fù)雜室內(nèi)環(huán)境對定位精度的負(fù)面影響，整個定位系統(tǒng)不用添加任何額外的硬件即可實現(xiàn)。實驗結(jié)果表明，該算法的定位精度明顯優(yōu)于原始的歐氏距離法。

［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］ 孫善武，王 楠，陳 堅.一種改進(jìn)的基于信號強(qiáng)度的WLAN定位方法［J］.計算機(jī)科學(xué)，2014，41(6):99-103.

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

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

［8］ 程金晶，魏東巖，唐陽陽.WLAN指紋定位中AP選擇策略研究［J］.計算機(jī)技術(shù)與發(fā)展，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信號指紋的樓宇內(nèi)定位算法［J］.計算機(jī)研究與發(fā)展，2013，50(3):568 -577.

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

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

［13］鄭 倩，盧振泰，陳 超，等.基于鄰域信息和高斯加權(quán)卡方距離的脊椎MR圖像分割［J］.中國生物醫(yī)學(xué)工程學(xué)報，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">網(wǎng)絡(luò)出版時間:

時間:2016-08-01

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

陶 崢(1984-)，男，工程師，碩士，研究方向為WLAN室內(nèi)定位技術(shù);王洪玉，教授，博士研究生導(dǎo)師，研究方向為無線網(wǎng)絡(luò)。

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