基于中心矩改進(jìn)的WiFi室內(nèi)定位算法

于　洋　陳　光　單志勇　陳　艷

(東華大學(xué)信息科學(xué)與技術(shù)學(xué)院　上海 201620)

0　引　言

目前，影響最大、定位覆蓋最廣的定位系統(tǒng)是美國(guó)的全球衛(wèi)星定位系統(tǒng)GPS[1]，它以全方位、全天候、高精度、高效率作為其獨(dú)特優(yōu)點(diǎn)。但是，在室內(nèi)如商場(chǎng)、醫(yī)院、博物館及地下停車場(chǎng)等公共場(chǎng)所，由于GPS衛(wèi)星發(fā)射的無(wú)線電信號(hào)無(wú)法穿透建筑物墻壁，以致于使用全球衛(wèi)星定位系統(tǒng)來(lái)進(jìn)行精確的室內(nèi)定位存在著很大的局限性。

針對(duì)GPS在室內(nèi)定位中存在的問(wèn)題，各種室內(nèi)定位技術(shù)如RFID[2]定位技術(shù)、紅外線[3]定位技術(shù)、ZigBee[4]定位技術(shù)、超聲波[5]定位技術(shù)、WiFi[6-7]定位術(shù)、 藍(lán)牙[8]定位技術(shù)、地磁[9]定位技術(shù)應(yīng)運(yùn)而生，并已經(jīng)成功地應(yīng)用于民用和商業(yè)領(lǐng)域中。其中，比較典型的有微軟研究院的RADAR[6]定位系統(tǒng)，美國(guó)馬里蘭大學(xué)的Horus[7]定位系統(tǒng)，加利福亞大學(xué)的Nibble[10]定位系統(tǒng)，麻省理工學(xué)院的Cricket[11]定位系統(tǒng)，北京航空航天大學(xué)的Weyes[12]定位系統(tǒng)，以及清華大學(xué)的WILL[13]定位系統(tǒng)等。

在這些定位技術(shù)中，基于WiFi的室內(nèi)定位技術(shù)由于WiFi網(wǎng)絡(luò)的廣泛普及和通信能力強(qiáng)優(yōu)點(diǎn)，已經(jīng)成為目前主流、也是未來(lái)最具發(fā)展?jié)摿Φ氖覂?nèi)定位技術(shù)。WiFi定位技術(shù)的獨(dú)特優(yōu)勢(shì)在于WiFi芯片已經(jīng)在各類用戶智能終端，諸如智能手機(jī)、平板電腦中得到廣泛普及，并且隨著“無(wú)線城市”的發(fā)展，國(guó)內(nèi)各大城市的運(yùn)營(yíng)商在眾多公共場(chǎng)所均已安裝了大量的WiFi熱點(diǎn)，通過(guò)利用現(xiàn)有的這些WiFi設(shè)施，能夠顯著降低建設(shè)與長(zhǎng)期維護(hù)成本[14]。

針對(duì)室內(nèi)環(huán)境下接受信號(hào)強(qiáng)度RSS值波動(dòng)較大問(wèn)題，本文根據(jù)參考點(diǎn)RP(Reference Point)信號(hào)強(qiáng)度分布的中心矩特征值，設(shè)計(jì)了一種改進(jìn)的WKNN定位算法。

1　定位系統(tǒng)

基于WiFi指紋的定位系統(tǒng)如圖1所示。它包括離線階段和在線匹階段兩部分。其中，離線階段負(fù)責(zé)采集參考點(diǎn)上信號(hào)強(qiáng)度的均值和二階矩以建立指紋數(shù)據(jù)庫(kù)；在線階段將當(dāng)前采集的數(shù)據(jù)，采用匹配算法來(lái)與數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行匹配，找出最相似的參考點(diǎn)坐標(biāo)作為定位點(diǎn)位置的估算值。

圖1　WiFi指紋定位系統(tǒng)

1.1　指紋數(shù)據(jù)庫(kù)建立

在離線階段，首先將室內(nèi)場(chǎng)景劃分為等間距的方形網(wǎng)格，一般網(wǎng)格間距為1～2 m，此時(shí)將各個(gè)網(wǎng)格相交的點(diǎn)作為參考點(diǎn)，然后在每個(gè)參考點(diǎn)上依次采集來(lái)自不同AP(Access Point)的信號(hào)強(qiáng)度，同時(shí)記錄該參考點(diǎn)的坐標(biāo)，以建立指紋數(shù)據(jù)庫(kù)。

第i個(gè)參考點(diǎn)RP測(cè)得來(lái)自第j個(gè)AP的信號(hào)強(qiáng)度可以表示成一個(gè)數(shù)集：

rssij={sijt,t=1,2,…,T}

(1)

式中：t代表單位采樣時(shí)間，由于環(huán)境的時(shí)變性，有可能會(huì)出現(xiàn)采集來(lái)自AP信號(hào)強(qiáng)度值不穩(wěn)定的情況，根據(jù)大數(shù)定律，當(dāng)樣本數(shù)據(jù)量很大的時(shí)候，平均結(jié)果將趨于某一穩(wěn)定值。則第i個(gè)參考點(diǎn)RP來(lái)自第j個(gè)AP的信號(hào)強(qiáng)度為：

(2)

式(2)表示在第i個(gè)參考點(diǎn)RP測(cè)得來(lái)自第j個(gè)接入點(diǎn)AP的信號(hào)強(qiáng)度的均值。則所有參考點(diǎn)RP來(lái)自每個(gè)AP的信號(hào)強(qiáng)度可以表示為一個(gè)矩陣：

(3)

1.2　經(jīng)典指紋匹配算法

在線定位時(shí)，用戶終端在定位場(chǎng)景中移動(dòng)并實(shí)時(shí)獲取當(dāng)前來(lái)自每個(gè)AP的信號(hào)強(qiáng)度值，同時(shí)將該數(shù)據(jù)上傳至定位服務(wù)器與指紋數(shù)據(jù)庫(kù)的數(shù)據(jù)進(jìn)行在線匹配，從而獲得該點(diǎn)的估算位置，并返回至終端。其中常見(jiàn)的匹配算法有最鄰近NN[15]算法、K最鄰近KNN[16-17]算法、加權(quán)K鄰近WKNN[18]算法。

NN算法通過(guò)計(jì)算當(dāng)前采集的信號(hào)強(qiáng)度向量與指紋數(shù)據(jù)庫(kù)的每個(gè)參考點(diǎn)的信號(hào)強(qiáng)度向量的歐式距離度量，然后將計(jì)算結(jié)果中的最小值所對(duì)應(yīng)的參考點(diǎn)坐標(biāo)最為定位位置。

KNN算法與NN算法類似，NN算法在于找出計(jì)算結(jié)果中一個(gè)最小值，而KNN算法則是找出計(jì)算結(jié)果中K個(gè)(K一般取4[19])最小值所對(duì)應(yīng)的K個(gè)參考點(diǎn)坐標(biāo)值，然后將坐標(biāo)取平均作為定位位置。

WKNN算法是對(duì)KNN算法的改進(jìn)，該算法不是簡(jiǎn)單地對(duì)K個(gè)位置坐標(biāo)取均值，而是對(duì)于每個(gè)位置設(shè)定一個(gè)權(quán)值，權(quán)值的大小決定其在定位所占的比重[20]。

2　改進(jìn)的WKNN 算法

由于室內(nèi)環(huán)境的時(shí)變性，因此，參考點(diǎn)采集的信號(hào)強(qiáng)度會(huì)產(chǎn)生一定的波動(dòng)。而對(duì)發(fā)射信號(hào)功率穩(wěn)定性差的AP，這種波動(dòng)尤為明顯[21]。針對(duì)采集來(lái)自AP的信號(hào)強(qiáng)度不穩(wěn)定問(wèn)題，在已有的WKNN算法基礎(chǔ)上本文提出了一種改進(jìn)的 WKNN 算法以提高定位精度。

2.1　中心矩特征值的提取

指紋數(shù)據(jù)庫(kù)中在第i個(gè)參考點(diǎn)RP上的信號(hào)強(qiáng)度可以表示為一均值向量，如式(4)所示。

rssi=rssiji=1,2,…,Mj=1,2,…,N

(4)

式中：M表示RP的數(shù)量，N表示AP的數(shù)量，rssij表示在第i個(gè)參考點(diǎn)RP測(cè)得來(lái)自第j個(gè)AP的信號(hào)強(qiáng)度均值向量，根據(jù)式(1)和式(2)，可進(jìn)一步表示為：

(5)

根據(jù)采集到的信號(hào)強(qiáng)度集合式(1)和n階中心矩式(6)計(jì)算參考點(diǎn)上的信號(hào)強(qiáng)度中心矩。式(6)中，E(rssijt)表示在第i個(gè)參考點(diǎn)測(cè)得來(lái)自第j個(gè)AP的信號(hào)強(qiáng)度均值，rssijt表示每隔單位時(shí)間t采集來(lái)自AP的信號(hào)強(qiáng)度值，cij表示信號(hào)強(qiáng)度的n階中心距。

cij=E{[rssijt-E(rssijt)]n}t=1,2,…,T

(6)

由于二階中心矩是用來(lái)衡量隨機(jī)變量與均值之間的偏離程度，故n取值為2，則計(jì)算第i個(gè)參考點(diǎn)來(lái)自第j個(gè)AP的信號(hào)強(qiáng)度二階中心矩向量cij如式(7)。

cij=(ci1,ci2,…,ciN)i=1,2,…,Mj=1,2,…,N

(7)

通過(guò)式(5)和式(7)，指紋數(shù)據(jù)庫(kù)式(3)可以進(jìn)一步表示為信號(hào)強(qiáng)度向量和二階中心矩向量，如式(8)所示。

R=(rssij,cij)i=1,2,…,Mj=1,2,…,N

(8)

2.2　加權(quán)距離的計(jì)算

改進(jìn)WKNN算法采用加權(quán)歐式距離來(lái)尋找與定位點(diǎn)最近的K個(gè)參考點(diǎn)，而權(quán)值的大小取決于數(shù)據(jù)庫(kù)中每個(gè)參考點(diǎn)上采集的信號(hào)強(qiáng)度的二階中心矩。

假設(shè)移動(dòng)終端在定位場(chǎng)景中某點(diǎn)x所獲取的信號(hào)強(qiáng)度矢量為：

rssxj=(rssx1,rssx2,…,rssxj)j=1,2,…,N

(9)

加權(quán)歐氏距離是在已有歐氏距離的基礎(chǔ)上對(duì)它作出的一種改進(jìn)，改進(jìn)的歐氏距離在n維信號(hào)強(qiáng)度向量的每一維度賦予了不同權(quán)重，權(quán)重與參考點(diǎn)上的信號(hào)強(qiáng)度二階中心矩相關(guān)， 則使用改進(jìn)加權(quán)距離計(jì)算用戶終端定位點(diǎn)x與參考點(diǎn)i的距離dxi為：

(10)

式中：ωik是參考點(diǎn)i在第k個(gè)AP處的權(quán)值系數(shù)，與該參考點(diǎn)采集到的AP信號(hào)強(qiáng)度的中心矩有關(guān)，并以中心矩的倒數(shù)作為系數(shù)，然后將該系數(shù)歸一化處理，如公式所示：

(11)

二階中心矩大的參考點(diǎn)，說(shuō)明RSS的波動(dòng)越大，

采集的信號(hào)強(qiáng)度與其均值相離越遠(yuǎn)；二階中心矩小的參考點(diǎn)，說(shuō)明RSS的分布越緊湊，采集的信號(hào)強(qiáng)度都會(huì)在其均值附近波動(dòng)。

使用改進(jìn)的加權(quán)歐氏距離進(jìn)行在線匹配計(jì)算時(shí)，此算法將中心矩的倒數(shù)作為權(quán)系數(shù)加入到歐式距離的計(jì)算中，能大大地降低中心矩較大的AP的RSS值在歐式距離計(jì)算時(shí)所占的比重，能夠在一定程度上消除大部分由于環(huán)境的實(shí)時(shí)變化而造成RSS值產(chǎn)生一定波動(dòng)帶來(lái)的影響，進(jìn)而提高用戶終端的定位精度。

3　實(shí)驗(yàn)測(cè)試

3.1　測(cè)試環(huán)境

實(shí)驗(yàn)環(huán)境選擇了室內(nèi)8 m×8 m區(qū)域，首先在該區(qū)域劃分若干個(gè)網(wǎng)格，然后選擇其中有16個(gè)點(diǎn)作為參考點(diǎn)RP，3個(gè)點(diǎn)作為接入點(diǎn)AP，其中，圖2為實(shí)際場(chǎng)景，圖3為仿真場(chǎng)景。

圖2　定位場(chǎng)景

圖3　仿真場(chǎng)景

離線階段，用戶終端依次在每個(gè)參考點(diǎn)RP每隔1秒鐘采集一次信號(hào)強(qiáng)度，共采集50次來(lái)自每個(gè)接入點(diǎn)AP的信號(hào)強(qiáng)度，然后將原始數(shù)據(jù)進(jìn)行預(yù)處理，得到信號(hào)強(qiáng)度的均值和二階中心矩以建立指紋數(shù)據(jù)庫(kù)。

在線定位階段時(shí)，在上述8 m×8 m區(qū)域內(nèi)隨機(jī)選定10個(gè)點(diǎn)作為定位測(cè)試點(diǎn)，如圖4所示。

圖4　AP=3的場(chǎng)景分布

然后依次將該場(chǎng)景中分布的AP分別增加至5個(gè)和7個(gè)。其中，AP分布如圖5和圖6所示，最后在上述10個(gè)同樣的測(cè)試點(diǎn)再次進(jìn)行在線定位。

圖5　AP=5的場(chǎng)景分布

圖6　AP=7的場(chǎng)景分布

3.2　性能分析

在上述三種不同AP數(shù)量分布的場(chǎng)景下，通過(guò)定位結(jié)果分析，當(dāng)AP的數(shù)量為5時(shí)，定位誤差達(dá)到最小。其中，各測(cè)試點(diǎn)的定位結(jié)果見(jiàn)表1和表2，場(chǎng)景定位結(jié)果如圖7所示。

表1　定位結(jié)果

表2　定位結(jié)果

圖7　AP=5的定位結(jié)果

在上述10個(gè)同樣的測(cè)試點(diǎn)分別進(jìn)行在線定位，三中不同場(chǎng)景下的AP分布的定位誤差如圖8所示。從定位誤差分析，當(dāng)場(chǎng)景中AP的數(shù)量為5時(shí)，定位誤差最小。

圖8　定位誤差比較

圖9是NN算法，KNN算法，WKNN算法與改進(jìn)WKNN算法的實(shí)驗(yàn)仿真的累計(jì)誤差分布直方圖，其中，K=4。從圖中可明顯看出采用改進(jìn)WKNN算法的累計(jì)誤差距離是最小的。因此，實(shí)驗(yàn)證明采用改進(jìn)WKNN算法進(jìn)行在線匹配能夠有效提高室內(nèi)定位精度。

圖9　不同算法的CDF比較

4　結(jié)　語(yǔ)

本文針對(duì)WiFi室內(nèi)定位系統(tǒng)在線階段匹配精度低問(wèn)題，在已有的WKNN算法基礎(chǔ)上，提出了一種改進(jìn)的WKNN算法。并通過(guò)理論分析和實(shí)驗(yàn)測(cè)試，在不同AP數(shù)量的分布以及不同定位算法的選擇下對(duì)定位結(jié)果進(jìn)行了分析。實(shí)驗(yàn)結(jié)果證明：采用改進(jìn)的WKNN算法將信號(hào)強(qiáng)度的二階矩作為權(quán)值加入到計(jì)算歐式距離中，有效地降低了室內(nèi)環(huán)境實(shí)變性而造成RSS值產(chǎn)生一定波動(dòng)帶來(lái)的影響，提高了定位的精度。此外，該系統(tǒng)無(wú)需增加額外的硬件設(shè)備，易于實(shí)現(xiàn)，具有潛在的實(shí)用價(jià)值。

[1] Enge P,Misra P.Special Issue on Global Positioning System[J].Proceedings of the IEEE,1999,87(1):3-15.

[2] Ni L M,Liu Y,Lau Y C,et al.LANDMARC:Indoor Location Sensing Using Active RFID[C]//IEEE International Conference on Pervasive Computing and Communications.IEEE,2003:407-415.

[3] Want R,Hopper A,Gibbons J.The active badge location system[J].Acm Transactions on Information Systems,1992,10(1):91-102.

[4] Sugano M,Kawazoe T,Ohta Y,et al.Indoor Localization System using RSSI Measurement of Wireless Sensor Network based on ZigBee Standard[C]//The 6th IASTED International Multi-Conference on Wireless and Optical Communications,Wireless Sensor Networks.DBLP,2006:1-6.

[5] Ward A,Jones A,Hopper A.A new location technique for the active office[J].Personal Communications IEEE,1997,4(5):42-47.

[6] Bahl P,Padmanabhan V N.RADAR:an in-building RF-based user location and tracking system[C]//INFOCOM 2000.Nineteenth Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.IEEE Xplore,2000:775-784.

[7] Youssef M,Agrawala A.The Horus WLAN location determination system[C]//International Conference on Mobile Systems,Applications,and Services.ACM,2005:205-218.

[8] Hallberg J,Nilsson M,Synnes K.Positioning with Bluetooth[C]//International Conference on Telecommunications.IEEE,2003,2:954-958.

[9] Boles L C,Lohmann K J.True navigation and magnetic maps in spiny lobsters[J].Nature,2003,421(6918):60.

[10] Castro P,Chiu P,Kremenek T,et al.A Probabilistic Room Location Service for Wireless Networked Environments[C]//International Conference on Ubiquitous Computing.Springer-Verlag,2001:18-34.

[11] Priyantha N B.The Cricket indoor location system[J].Architecture,2005,16(2001):199.

[12] 郎昕培,許可,趙明.基于無(wú)線局域網(wǎng)的位置定位技術(shù)研究和發(fā)展[J].計(jì)算機(jī)科學(xué),2006,33(6):21-24.

[13] Wu C,Yang Z,Liu Y,et al.WILL:Wireless Indoor Localization without Site Survey[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(4):839-848.

[14] 杜曉黎.基于WIFI的室內(nèi)定位系統(tǒng)[D].東南大學(xué),2015.

[15] Cover T M.Rates of convergence for nearest neighbor procedures[C]//Hawaii International Conference on System Sciences,1968.

[16] Short R D,Fukunaga K.A new nearest neighbor distance measure[C]//1980.

[17] Hastie T,Tibshirani R.Discriminant Adaptive Nearest Neighbor Classification[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1996,18(6):607-616.

[18] Brown T,Koplowitz J.The weighted nearest neighbor rule for class dependent sample sizes (Corresp.)[J].IEEE Transactions on Information Theory,1979,25(5):617-619.

[19] Mitchell H B,Schaefer P A.A “soft” K-Nearest Neighbor voting scheme[J].International Journal of Intelligent Systems,2001,16(4):459-468.

[20] 任睿.基于數(shù)據(jù)庫(kù)相關(guān)算法的位置指紋定位技術(shù)[J].鐵道通信信號(hào),2012,48(3):49-51.

[21] 陳空,宋春雷,陳家斌,等.基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法[J].導(dǎo)航定位與授時(shí),2016,3(4):58-64.