張乾初，劉正熙

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

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

張乾初，劉正熙

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

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

0　引言

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

1　差分梯度匹配算法原理

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

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

其流程如圖1 所示。

1.1訓(xùn)練階段

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

1.2差分梯度匹配算法

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

圖1　Wi-Fi定位流程

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

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

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

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

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

算法流程圖如下：

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

1.3定位階段

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

2　實驗結(jié)果及分析

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

圖3　停車場微地圖

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

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

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

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

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

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

3　結(jié)語

本文將講解了Wi-Fi指紋定位的一般方法，并提出了一種基于差分梯度匹配的算法。在實驗中通過對比傳統(tǒng)的指紋匹配算法，可以發(fā)現(xiàn)本文算法在Wi-Fi信號強度較大的地方其匹配效果明顯高于傳統(tǒng)方法，但當(dāng)待定位點處于Wi-Fi信號強度比較弱的地方時，其定位效果明顯變差。本文算法可以結(jié)合KNN匹配算法進(jìn)行定位，其信號間距離可采用歐氏距離。在匹配前先判斷待定位點的信號強度，若信號強度有明顯的一個或多個較大的值時采用本文算法，若所采集的所有的信號值都比較小則采用KNN匹配算法。從而彌補了由于信號強度較小而對定位產(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)基于信號強度的室內(nèi)定位[J].計算機科學(xué)，2007（6）:68-71.

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

[5]王暉.基于RSSI的無線傳感器網(wǎng)絡(luò)室內(nèi)定位算法設(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-），男，安徽六安人，碩士研究生，研究方向為數(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)的實現(xiàn)越來越成為可能。提出一種基于差分梯度匹配算法的Wi-Fi定位方法，差分梯度匹配即對Wi-Fi的信號強度進(jìn)行梯度劃分，不同梯度對應(yīng)不同的匹配率，通過計算當(dāng)前待定位點和指紋庫里所有指紋的匹配率，找到匹配率最高的K個點，以這K個點的幾何中心作為帶定位點的位置坐標(biāo)。

劉正熙（1962-），男，四川成都人，教授，研究方向為數(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.