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

張乾初，劉正熙

（四川大學計算機學院，成都　610065）

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

張乾初，劉正熙

（四川大學計算機學院，成都610065）

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

0　引言

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

1　差分梯度匹配算法原理

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

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

其流程如圖1 所示。

1.1訓練階段

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

1.2差分梯度匹配算法

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

圖1　Wi-Fi定位流程

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

當前待定位點所采集到的信息設為：

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

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

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

算法流程圖如下：

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

1.3定位階段

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

2　實驗結果及分析

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

圖3　停車場微地圖

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

表1　匹配結果誤差統計

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

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

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

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

3　結語

本文將講解了Wi-Fi指紋定位的一般方法，并提出了一種基于差分梯度匹配的算法。在實驗中通過對比傳統的指紋匹配算法，可以發現本文算法在Wi-Fi信號強度較大的地方其匹配效果明顯高于傳統方法，但當待定位點處于Wi-Fi信號強度比較弱的地方時，其定位效果明顯變差。本文算法可以結合KNN匹配算法進行定位，其信號間距離可采用歐氏距離。在匹配前先判斷待定位點的信號強度，若信號強度有明顯的一個或多個較大的值時采用本文算法，若所采集的所有的信號值都比較小則采用KNN匹配算法。從而彌補了由于信號強度較小而對定位產生的偏差。

[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的無線傳感器網絡三角形質心定位算法[J]．現代電子技術，2009（2）：180-182．

[3]張明華，張申生，曹健.無線局域網基于信號強度的室內定位[J].計算機科學，2007（6）:68-71.

[4]陳文周著.Wi-Fi技術的研究與應用.數據通信，2008（2）.

[5]王暉.基于RSSI的無線傳感器網絡室內定位算法設計與實現[D].北京：北京郵電大學，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-），男，安徽六安人，碩士研究生，研究方向為數字圖像處理及地理信息系統

2015-12-08

2016-01-08

GPS定位系統被普遍使用在軍用和民用系統中，但是由于房屋等障礙物的遮擋，GPS無法用于室內定位。隨著經濟的發展，Wi-Fi覆蓋范圍越來廣，基于Wi-Fi的定位系統的實現越來越成為可能。提出一種基于差分梯度匹配算法的Wi-Fi定位方法，差分梯度匹配即對Wi-Fi的信號強度進行梯度劃分，不同梯度對應不同的匹配率，通過計算當前待定位點和指紋庫里所有指紋的匹配率，找到匹配率最高的K個點，以這K個點的幾何中心作為帶定位點的位置坐標。

劉正熙（1962-），男，四川成都人，教授，研究方向為數字圖像處理、智能系統與信息處理

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.