基于Wi-Fi 的三邊定位算法的改進

郭陽，曹子騰，趙正旭，王威，劉曼云

（1.石家莊鐵道大學復雜網絡與可視化研究所，石家莊050043；2.青島理工大學機械與汽車工程學院，青島266520；3.西交利物浦大學計算機科學與軟件學院，蘇州215123）

0 引言

隨著信息時代的到來，人們對各種信息的需求越來越多，位置信息也變得越來越重要，不論是在老人贍養時的位置監視，還是在大型商場中對所需商品位置的快速定位，還有在地下停車場中快速尋找車位等，都顯示出位置信息的重要性。不止在生活中對位置信息有著強烈的需求，在工業、商業等都需要位置的信息，甚至在安全救援方面，快速確定受困人員位置也十分重要[1]。所以，對定位技術的研究是非常有意義的。

現如今，室外定位技術發展已經足夠成熟，例如美國全球衛星導航系統GPS、俄羅斯的“格洛納斯”、歐盟的“伽利略”以及中國的北斗衛星導航系統[2]。但是因為在室內環境中，墻壁、家具等建筑物可能會對衛星信號產生遮擋，所以室外定位技術并不能很好地應用到室內，所以專門用于室內條件下的定位技術逐漸成為研究熱點。常見的室內定位技術主要有紅外線定位技術、超聲波定位技術、藍牙定位技術、Wi-Fi 定位技術等。這些室內定位技術因為其自身特性各有優缺點[3]。例如紅外線定位技術雖然定位精度高但是成本高，不能普遍適用。藍牙定位技術雖然硬件環境簡單，但是藍牙信號容易受到室內其他信號的干擾產生誤差。

上述定位技術中，Wi-Fi 定位技術因為其成本低、覆蓋面廣等優點被廣泛使用。現在智能移動設備越來越普及，Wi-Fi 廣泛分布在各種大小區域，不論是商場、停車場還是個人住所，Wi-Fi 都隨處可見。所以對Wi-Fi 室內定位技術的研究成為一個熱點。在Wi-Fi 定位技術中，三邊定位算法是最基礎、最簡單的一種定位算法，也是基于測距的定位技術中使用較多的一種算法。但是因為其在使用過程中會產生累積誤差，本文針對三邊定位法精度不高的問題[4]，在使用三邊定位法進行定位的過程中對其進行改進從而減小定位誤差。

1 Wi-Fi定位技術的定位原理

Wi-Fi 已被開發用于無線電信號的數據通信，其定位應用變得十分流行[5]。

Wi-Fi 定位技術是一種基于輔助設備的定位技術，其定位原理是通過在室內區域中部署一定數量的AP（無線接入點，Access Point），每一個AP 都有自己獨立的MAC 地址和名稱。在室內建立好坐標系，設立好原點位置和橫縱軸方向。其中放置的這些AP 的坐標已知。當待定位設備進入此室內區域后，可以接收到來自各個AP 發射出的信號，并測出Wi-Fi 的RSSI 值（Received Signal Strength Indication，可接收信號強度值）[6]。根據信號傳播的衰減模型，推算出信號強度和距離的轉化公式，后臺可以計算出待定位設備與每個AP 的距離，再通過三邊定位算法或其他定位算法對待定位設備的位置坐標進行計算。

2 信號強度與距離

Wi-Fi 定位技術中可以采用基于測距的定位方法[7]，計算方法是根據接收到的信號強度值轉化為距離，因為信號在傳播環境中會產生衰減，所以信號強度和距離不能直接轉化，需要考慮信號的衰減，并且要考慮不同環境中信號的衰減速度是不同的，也就是信號穿過不同的障礙物時產生的信號衰減都不相同。例如信號在空氣中傳播和穿透墻壁后如果按相同的公式計算就會產生較大誤差。計算時一般采用無線信號的傳輸損耗模型，傳輸損耗模型的公式為[8]：

其中，d 表示距離輔助設備的距離，n 為環境衰減因子，PR（d）是距離輔助設備距離為d 時的信號強度RSSI 值，PR（d0）是距離待測設備為d0 時的信號強度，一般取d0 為1m。所以根據此式可得出距離與信號強度的轉化公式如下：

其中，d 是測量設備距發射信號強度設備的距離，單位是m。RSSI 為信號強度值，測出的信號強度值一般情況下是負數。A 是測量設備距離發射信號強度設備1m 時的RSSI 值的絕對值，需要在實驗中進行測量得到。n 為環境衰減因子，需要進行校正測試，不同的障礙物中信號的衰減是不同的，所以需要后期實驗得到。

3 三邊定位算法

三邊定位算法的主要流程是先通過測量信號強度計算出待定位設備與每個AP 的距離，選出待定位設備距離附近的三個AP，分別為AP1、AP2、AP3，且距離這三個AP 的距離分別為的d1、d2、d3。分別以AP1、AP2、AP3 為圓心，以d1、d2、d3 為半徑作圓，三個圓的交點就是待定位設備的位置。如圖1 所示。

圖1 三邊定位（a）

但是這種情況只出現在理想條件下，也就是沒有定位誤差的條件下。由于在測量信號強度的時候信號會在空氣中產生衰減，所以會存在誤差，在信號強度轉化為距離的時候也會存在誤差，所以一般情況下三圓很難相交于一點，出現較多的可能是三個圓相交于一個區域，甚至還可能出現其中兩個圓不相交。

4 三邊定位算法的改進

由于使用三邊定位算法時分為測距階段和定位階段，在測距階段，由于信號傳播的不穩定性，一次測量得到的RSSI 值可能會與實際的值有偏差，所以在轉換成距離的時候也會產生一定的誤差。在定位階段，由于上述誤差使三個圓不會相交于一點，而是相交于一個區域，所以在這個區域中找出待定位點也會產生誤差。這兩個階段的誤差會累積導致測出的位置與實際位置偏差較大，所以分別在這兩個階段采取措施減小誤差的累積，最后達到縮小定位誤差的目的。在測距階段，分別對每一個AP 的RSSI 值進行多次測量，將得到的數據采用Mahalanobis 距離檢測方法去除噪聲數據，得到一組相對準確的RSSI 值再進行距離的轉換。在定位階段，通過計算三圓相交區域的質心點，得到待定位坐標。

4.1 Mahalanobis距離

Mahalanobis 距離又稱為馬氏距離，表示數據的協方差距離，是一種有效計算兩個未知樣本的相似度的方法。定義為：設總體G 為m 維樣本，均值向量為μ（μ1，μ2，…，μm）′，協方差陣為∑（σ ），則樣品X=（x1，x2，…，xm）′與總體G 的馬氏距離定義為：

當m=1 時，只有一個考量單位，公式可轉化為：

因為只需涉及信號強度一個考量單位，所以采用m=1 時的馬氏距離公式。計算RSSI 值樣本的均值μ，以及方差σ2，再根據公式計算出每個樣本與均值之間的Mahalanobis 距離。即：

設定好參數，樣本RSSI 值與均值之間的Mahalanobis 距離超過此參數，將該RSSI 值判定為噪聲數據，并進行剔除。余下的RSSI 值求平均數得到最終要轉換為距離的RSSI 值。

采用Mahalanobis 距離的優點是Mahalanobis 距離的計算是建立在總體樣本的基礎上的，兩個相同的樣本在不同的總體中計算的結果一般也是不同的。所以對每一個AP 多次測量RSSI 值，即使每一組的均值都相同，可能要剔除的奇異點也是不相同的，這會在一定程度上減小誤差。

4.2 三邊質心定位算法

在使用三邊定位算法的時候，如圖3、圖4 所示，三個圓相交于一個區域，待定位坐標在此區域內，在此區域內要求得待定位點的位置，采用求多邊形質心點的方法[9]。求一個多邊形質心點的過程是：已知多邊形的頂點坐標（X1，Y1），（X2，Y2），…，（Xn，Yn），則質心點（X，Y）的解法如下式：

三邊質心定位算法的主要流程是：如圖3 和圖4所示，三個圓圍成了一個類似于三角形的區域，分別對三個圓兩兩求交點，得到這個區域的三個頂點坐標，再求質心點，所得到的質心點的坐標就是待定位設備的坐標位置。

具體流程是在室內環境中部署4 個AP，分別為AP1、AP2、AP3 和AP4，并且位置已知。從這四個中選出三個進行組合，根據排列組合原理可得到四組，分別為（AP1，AP2，AP3），（AP1，AP2，AP4），（AP1，AP3，AP4），（AP2，AP3，AP4）。對每一個組合分別用三邊質心定位算法求出一個坐標，這樣可以求出四個坐標，再對所求得的四個坐標求平均值，得到最終的待定位點的位置坐標。如果在計算過程中出現有一組數據三個圓有不相交的情況，表明誤差過大該組數據不可用，舍棄該組數據，余下的可用數據再求平均值。算法流程如圖2 所示。

圖2 三邊定位（b）

圖3 三邊定位（c）

圖4 算法流程

5 算法的實驗驗證

在實驗驗證階段，需要的硬件設備有：路由器和至少四個AP。本次實驗場景選擇石家莊鐵道大學第九實驗樓230 室，實驗場景和硬件設備如圖5 所示。

圖5 硬件設備

通過在室內環境中放置四個AP，建立坐標系，選取好坐標原點和橫縱軸方向，并記錄好AP 的坐標位置，待定位設備采用日常使用的可以接收到Wi-Fi 信號的智能移動設備，當開始定位時，待定位設備分別接收到四個位置的AP 信號并對每個AP 的信號強度進行五十次測量。記錄下測量數據，通過Mahalanobis 距離去除奇異值，再求平均值得到一組RSSI 值。再將RSSI 值轉化為距離。在五個未知點分別對四個AP 測量信號強度并進行去噪處理后可得到五組數據如表1所示。

表1 信號強度表

距離與RSSI 值的轉化利用轉化公式，在轉化之前的第一步需要先測量出A 的值，測量方法是室內部署好AP 后，距離其中一個AP 一米時測量信號強度，同樣采用多次測量去除奇異點得到一個較為準確的值。第二步，矯正測試環境衰減因子n 的值，因為在不同室內環境中，環境衰減因子n 的值是不同的，經過矯正測試，得到一個最佳值。第三步，將RSSI 值轉化為距離。因為實驗場景障礙物較少，無墻壁、石膏等障礙，所以環境中信號衰減相對較少。經實驗，最后確定A的值為30，環境衰減因子n 的值為1.5，再根據信號強度與距離的轉化公式求得與每個AP 的距離。

最后分別采用原始的三邊定位算法和本文提出的三邊算法的改進流程進行定位，定位結果如表2 所示。按照本文提出的先采用Mahalanobis 距離去除奇異RSSI 值，再采用三邊定位算法后求質心點得到的未知點坐標要比原始的三邊定位算法所求出的未知點坐標在一定程度上更加精確，減少了誤差的累積。

表2 定位結果

6 結語

三邊定位算法在許多基于測距的定位技術中使用頻率相對較高，但是由于其每個過程都會產生一定的誤差最終會造成誤差的累積，所以直接使用會使最終數據與實際值偏差較大。本文提出的定位流程先對測量出的信號強度進行處理去噪，再通過三邊定位算法，最后求出三圓交點圍成三角形區域的質心點的方法求出定位坐標，該方法可以在每一個過程中減小一定的誤差，最終避免誤差的累積導致最終數據失實。經實驗驗證，基于Wi-Fi 定位技術使用該定位方法比傳統的三邊定位方法的定位精度在一定范圍內有所提高。