張乾初，劉正熙

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

一種基于差分梯度匹配算法的Wi-Fi定位方法

張乾初，劉正熙

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

Wi-Fi指紋定位；差分梯度匹配；卡爾曼濾波

0　引言

隨著Wi-Fi技術(shù)的不斷發(fā)展，無線城市的推動(dòng)，越來越多的地方覆蓋了Wi-Fi信號(hào)。同時(shí)位置信息對(duì)各種現(xiàn)實(shí)需求有著重要的作用，如車輛定位、寵物定位、井下人員定位、室內(nèi)商場(chǎng)定位、建筑工地管理等。GPS廣泛用于各種位置定位，同時(shí)在許多領(lǐng)域得到了推廣應(yīng)用。然而，其信號(hào)卻極易受障礙物的干擾和阻斷，在密集的城市地帶、隧道、室內(nèi)等環(huán)境定位不可靠甚至于失效。因此，基于Wi-Fi的定位技術(shù)越來越受到人們的關(guān)注。Wi-Fi定位技術(shù)隨著Wi-Fi信號(hào)的普遍覆蓋，越來越多的商城會(huì)采用這個(gè)方式進(jìn)行定位。

1　差分梯度匹配算法原理

路由器在傳播Wi-Fi時(shí)，手機(jī)或其他Wi-Fi接收器所接收到的信號(hào)極易受障礙物的干擾和阻斷，如果單純通過RSSI即Wi-Fi信號(hào)強(qiáng)度的大小來得到帶定位點(diǎn)與路由器直接距離，則所得距離偏差將會(huì)很大。Wi-Fi路由器所發(fā)出的信號(hào)強(qiáng)度范圍在-1dBm到-120dBm之間。Wi-Fi接收器在接收到的信號(hào)基本沒有什么衰減的情況下，一般能達(dá)到-35dBm。在信號(hào)強(qiáng)度小于-90dbm時(shí)，Wi-Fi接收器就基本上無法連接到該路由器。因此當(dāng)Wi-Fi接收器接收某個(gè)路由器的Wi-Fi信號(hào)強(qiáng)度特別大，則表明該接收器距離此路由器距離相對(duì)較近。差分梯度匹配算法即基于以上所述的Wi-Fi信號(hào)傳播特點(diǎn)而提出的。

Wi-Fi定位依靠和表征特征的指紋數(shù)據(jù)庫進(jìn)行匹配來進(jìn)行識(shí)別。其定位過程包含兩個(gè)階段，即訓(xùn)練階段和定位階段。

其流程如圖1 所示。

1.1訓(xùn)練階段

訓(xùn)練階段為定位階段建立匹配的位置指紋識(shí)別數(shù)據(jù)庫。首先，對(duì)待定位區(qū)域以一定的幾何規(guī)律選擇合理的指紋點(diǎn)分布，通常采用網(wǎng)格式指紋點(diǎn)分布。指紋點(diǎn)分布要確保能為定位階段提供足夠的信息。接著在每個(gè)指紋點(diǎn)上采集來自不同路由器的RSSI值，將對(duì)應(yīng)的MAC地址和指紋點(diǎn)位置信息記錄到數(shù)據(jù)庫中。接著依次遍歷所有選定的指紋點(diǎn)，并采集相應(yīng)的信息。由于信號(hào)強(qiáng)度極易受干擾，為了得到相對(duì)穩(wěn)定的信號(hào)強(qiáng)度值，需對(duì)采集的RSS值進(jìn)行濾波處理，通常采用卡爾曼濾波算法來得到穩(wěn)定的RSSI值。

1.2差分梯度匹配算法

指紋識(shí)別庫中記錄了每個(gè)參考指紋點(diǎn)所能接收到的Wi-Fi路由器的MAC地址和相應(yīng)的RSSI值。

圖1　Wi-Fi定位流程

設(shè)指紋庫中的指紋點(diǎn)所保存的信息為：（lon，lat，mac1，lev1，mac2，lev2，…，maci，levi，…）其中i∈[1，n]，lon表示經(jīng)度，lat表示緯度，mac表示路由器MAC地址，lev表示信號(hào)強(qiáng)度。

當(dāng)前待定位點(diǎn)所采集到的信息設(shè)為：

（dmac1，dlev1，dmac2，dlev2，…，dmaci，dlevi，…）其中i∈[1，m]，lon表示經(jīng)度，lat表示緯度，mac表示路由器MAC地址，lev表示信號(hào)強(qiáng)度。

在進(jìn)行匹配時(shí)，必須保證計(jì)算的RSS值來自同一個(gè)路由器。因而首先對(duì)當(dāng)前點(diǎn)所接收到的信號(hào)依據(jù)路由器的MAC地址進(jìn)行排序。算法用兩個(gè)vector，設(shè)為pa1，pa2，來保存兩個(gè)位置點(diǎn)所接收到的不同路由器的信號(hào)值，當(dāng)指紋點(diǎn)沒有接收到待定位點(diǎn)所接收的路由器的Wi-Fi信號(hào)時(shí)，將對(duì)應(yīng)的值保存為minLevel，即Wi-Fi接收器所能接收的最小的信號(hào)強(qiáng)度值。同樣當(dāng)待定位點(diǎn)沒有收到指紋點(diǎn)所對(duì)應(yīng)的路由器的Wi-Fi信號(hào)時(shí)，也將對(duì)應(yīng)位置的值保存為minLevel。這樣pa1和pa2即保存了指紋點(diǎn)和待定位點(diǎn)的所能接收到的所有的路由器的信號(hào)值的大小。

接下來需計(jì)算指紋點(diǎn)和待定位點(diǎn)之間的匹配率。計(jì)算方法采用差分梯度算法，即對(duì)Wi-Fi信號(hào)值進(jìn)行梯度劃分，將-1dBm到-10dBm作為第一梯度，當(dāng)指紋點(diǎn)所接收到的信號(hào)值和待定位點(diǎn)所接收到的信號(hào)值都大于-10dBm，將其匹配率乘以該梯度的匹配率0.1，并同時(shí)檢測(cè)指紋點(diǎn)和帶定位點(diǎn)的信號(hào)值的差分平方是否小于100，若是小于100則將匹配率再乘以0.5。用差分平方的目的在于比較兩者之間的信號(hào)強(qiáng)度大小的距離值。若是指紋點(diǎn)和待定位點(diǎn)的RSSI差值比較小，則表明兩點(diǎn)在地理位置上比較接近。同樣將-11dBm到-20dBm作為第二梯度，兩者的信號(hào)值都大于-20dBm時(shí)，匹配率乘以該梯度的匹配率0.2，并同時(shí)檢測(cè)指紋點(diǎn)和帶定位點(diǎn)的信號(hào)值的差分平方是否小于100，若是小于100則將匹配率再乘以0.5。依次將-21dBm到-100dBm進(jìn)行梯度劃分，并將匹配率乘以相應(yīng)梯度的匹配率。默認(rèn)的總的匹配率為100。由于各點(diǎn)所能接收到的Wi-Fi路由器信號(hào)數(shù)量不一樣，因而必須對(duì)所得值進(jìn)行歸一化處理。

算法流程圖如下：

圖2　差分梯度匹配算法流程

1.3定位階段

Wi-Fi接收器接收到環(huán)境中的Wi-Fi信號(hào)后，依據(jù)上述的差分梯度匹配算法依次對(duì)指紋庫里面的所有指紋點(diǎn)進(jìn)行差分梯度匹配算法，計(jì)算指紋庫中所有點(diǎn)的匹配率大小。找出匹配率最大的K個(gè)點(diǎn)，取出這K個(gè)點(diǎn)的經(jīng)緯度，計(jì)算這K個(gè)點(diǎn)的幾何中心，即為待定位點(diǎn)的位置坐標(biāo)。

2　實(shí)驗(yàn)結(jié)果及分析

本文選擇一個(gè)地下停車場(chǎng)作為測(cè)試環(huán)境，其地圖如圖3 所示。采用華為WS832型號(hào)的路由器作為Wi-Fi信號(hào)發(fā)射器，并采用華為榮耀3C手機(jī)作為信號(hào)接收器。在停車場(chǎng)中選擇367個(gè)點(diǎn)作為指紋參考點(diǎn)，選擇125個(gè)點(diǎn)作為待測(cè)點(diǎn)，其中A區(qū)有60個(gè)點(diǎn)，B區(qū)有65個(gè)點(diǎn)。所有數(shù)據(jù)用MySQL5.6進(jìn)行保存，并利用C++進(jìn)行定位處理。實(shí)驗(yàn)結(jié)果數(shù)據(jù)通過MATLAB進(jìn)行統(tǒng)計(jì)分析。

圖3　停車場(chǎng)微地圖

表1統(tǒng)計(jì)了在不同誤差范圍內(nèi)的點(diǎn)的數(shù)量，通過統(tǒng)計(jì)表明，70.4%的點(diǎn)誤差都在4m以內(nèi)。其中圖4 的橫軸表示所接收的路由器中Wi-Fi信號(hào)強(qiáng)度最大的點(diǎn)的信號(hào)值，縱軸表示計(jì)算結(jié)果和實(shí)際距離誤差大小，通過圖4 可以看出，當(dāng)待測(cè)點(diǎn)的所接收到的最強(qiáng)的信號(hào)值較小時(shí)，所算的的誤差將會(huì)偏大。

表1　匹配結(jié)果誤差統(tǒng)計(jì)

圖4　位置距離偏差大小和Wi-Fi信號(hào)強(qiáng)度的關(guān)系

從上圖中可以看出，在Wi-Fi信號(hào)比較強(qiáng)的區(qū)域，本文所用算法偏差很小。然而當(dāng)待定位點(diǎn)所在區(qū)域的信號(hào)均十分微弱時(shí)，定位偏差變的很大。其可能原因如下：

由于在距離路由器較近的地方信號(hào)衰減不是很大，但當(dāng)距離路由器較遠(yuǎn)時(shí)，信號(hào)衰減隨距離增加變化將非常大，因而采用線性方式對(duì)Wi-Fi信號(hào)強(qiáng)度值進(jìn)行劃分存在一定的不合理性。

由于待定位點(diǎn)是通過匹配指紋庫中的參考點(diǎn)的信息，所有待定位點(diǎn)附近的參考點(diǎn)數(shù)量，也在一定程度上影響該點(diǎn)的定位精度。

3　結(jié)語

本文將講解了Wi-Fi指紋定位的一般方法，并提出了一種基于差分梯度匹配的算法。在實(shí)驗(yàn)中通過對(duì)比傳統(tǒng)的指紋匹配算法，可以發(fā)現(xiàn)本文算法在Wi-Fi信號(hào)強(qiáng)度較大的地方其匹配效果明顯高于傳統(tǒng)方法，但當(dāng)待定位點(diǎn)處于Wi-Fi信號(hào)強(qiáng)度比較弱的地方時(shí)，其定位效果明顯變差。本文算法可以結(jié)合KNN匹配算法進(jìn)行定位，其信號(hào)間距離可采用歐氏距離。在匹配前先判斷待定位點(diǎn)的信號(hào)強(qiáng)度，若信號(hào)強(qiáng)度有明顯的一個(gè)或多個(gè)較大的值時(shí)采用本文算法，若所采集的所有的信號(hào)值都比較小則采用KNN匹配算法。從而彌補(bǔ)了由于信號(hào)強(qiáng)度較小而對(duì)定位產(chǎn)生的偏差。

[1]R.E.Kalman.A New Approach to Linear Filtering and Prediction Problems[J].Transactions of the ASME Journal of Basic Engineering，1960:35-45

[2]林瑋，陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J]．現(xiàn)代電子技術(shù)，2009（2）：180-182．

[3]張明華，張申生，曹健.無線局域網(wǎng)基于信號(hào)強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué)，2007（6）:68-71.

[4]陳文周著.Wi-Fi技術(shù)的研究與應(yīng)用.數(shù)據(jù)通信，2008（2）.

[5]王暉.基于RSSI的無線傳感器網(wǎng)絡(luò)室內(nèi)定位算法設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)，2010.

Wi-Fi Fingerprint Positioning;Differential Gradient Match;Kalman Filter

A New Wi-Fi Location Method Based on Differential Gradient Matching Algorithm

ZHANG Qian-chu，LIU Zheng-xi
（College of Computer Science，Sichuan University，Chengdu 610065）

張乾初（1989-），男，安徽六安人，碩士研究生，研究方向?yàn)閿?shù)字圖像處理及地理信息系統(tǒng)

2015-12-08

2016-01-08

GPS定位系統(tǒng)被普遍使用在軍用和民用系統(tǒng)中，但是由于房屋等障礙物的遮擋，GPS無法用于室內(nèi)定位。隨著經(jīng)濟(jì)的發(fā)展，Wi-Fi覆蓋范圍越來廣，基于Wi-Fi的定位系統(tǒng)的實(shí)現(xiàn)越來越成為可能。提出一種基于差分梯度匹配算法的Wi-Fi定位方法，差分梯度匹配即對(duì)Wi-Fi的信號(hào)強(qiáng)度進(jìn)行梯度劃分，不同梯度對(duì)應(yīng)不同的匹配率，通過計(jì)算當(dāng)前待定位點(diǎn)和指紋庫里所有指紋的匹配率，找到匹配率最高的K個(gè)點(diǎn)，以這K個(gè)點(diǎn)的幾何中心作為帶定位點(diǎn)的位置坐標(biāo)。

劉正熙（1962-），男，四川成都人，教授，研究方向?yàn)閿?shù)字圖像處理、智能系統(tǒng)與信息處理

GPS positioning system is widely used in the military and civil systems,but because of housing and other obstacles,GPS cannot be used for indoor positioning.With the development of economy,the wide range of Wi-Fi coverage,the realization of the positioning system based on Wi-Fi is becoming more and more possible.Proposes a kind of based on differential graded matching algorithm of Wi-Fi location method,differential gradient matching is that dividing Wi-Fi signal strength to different gradient,different gradient corresponding to different matching rate,by calculating the current positioning and fingerprint library’s data matching rate and find the matching rate of the highest k points,the geometric center of the K points regard as the position coordinates of the current point positioning.