基于Wi-Fi 的三邊定位算法的改進(jìn)

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

（1.石家莊鐵道大學(xué)復(fù)雜網(wǎng)絡(luò)與可視化研究所，石家莊050043；2.青島理工大學(xué)機(jī)械與汽車工程學(xué)院，青島266520；3.西交利物浦大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，蘇州215123）

0 引言

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

現(xiàn)如今，室外定位技術(shù)發(fā)展已經(jīng)足夠成熟，例如美國全球衛(wèi)星導(dǎo)航系統(tǒng)GPS、俄羅斯的“格洛納斯”、歐盟的“伽利略”以及中國的北斗衛(wèi)星導(dǎo)航系統(tǒng)[2]。但是因?yàn)樵谑覂?nèi)環(huán)境中，墻壁、家具等建筑物可能會對衛(wèi)星信號產(chǎn)生遮擋，所以室外定位技術(shù)并不能很好地應(yīng)用到室內(nèi)，所以專門用于室內(nèi)條件下的定位技術(shù)逐漸成為研究熱點(diǎn)。常見的室內(nèi)定位技術(shù)主要有紅外線定位技術(shù)、超聲波定位技術(shù)、藍(lán)牙定位技術(shù)、Wi-Fi 定位技術(shù)等。這些室內(nèi)定位技術(shù)因?yàn)槠渥陨硖匦愿饔袃?yōu)缺點(diǎn)[3]。例如紅外線定位技術(shù)雖然定位精度高但是成本高，不能普遍適用。藍(lán)牙定位技術(shù)雖然硬件環(huán)境簡單，但是藍(lán)牙信號容易受到室內(nèi)其他信號的干擾產(chǎn)生誤差。

上述定位技術(shù)中，Wi-Fi 定位技術(shù)因?yàn)槠涑杀镜?、覆蓋面廣等優(yōu)點(diǎn)被廣泛使用?，F(xiàn)在智能移動設(shè)備越來越普及，Wi-Fi 廣泛分布在各種大小區(qū)域，不論是商場、停車場還是個人住所，Wi-Fi 都隨處可見。所以對Wi-Fi 室內(nèi)定位技術(shù)的研究成為一個熱點(diǎn)。在Wi-Fi 定位技術(shù)中，三邊定位算法是最基礎(chǔ)、最簡單的一種定位算法，也是基于測距的定位技術(shù)中使用較多的一種算法。但是因?yàn)槠湓谑褂眠^程中會產(chǎn)生累積誤差，本文針對三邊定位法精度不高的問題[4]，在使用三邊定位法進(jìn)行定位的過程中對其進(jìn)行改進(jìn)從而減小定位誤差。

1 Wi-Fi定位技術(shù)的定位原理

Wi-Fi 已被開發(fā)用于無線電信號的數(shù)據(jù)通信，其定位應(yīng)用變得十分流行[5]。

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

2 信號強(qiáng)度與距離

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

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

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

3 三邊定位算法

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

圖1 三邊定位（a）

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

4 三邊定位算法的改進(jìn)

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

4.1 Mahalanobis距離

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

當(dāng)m=1 時，只有一個考量單位，公式可轉(zhuǎn)化為：

因?yàn)橹恍枭婕靶盘枏?qiáng)度一個考量單位，所以采用m=1 時的馬氏距離公式。計(jì)算RSSI 值樣本的均值μ，以及方差σ2，再根據(jù)公式計(jì)算出每個樣本與均值之間的Mahalanobis 距離。即：

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

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

4.2 三邊質(zhì)心定位算法

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

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

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

圖2 三邊定位（b）

圖3 三邊定位（c）

圖4 算法流程

5 算法的實(shí)驗(yàn)驗(yàn)證

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

圖5 硬件設(shè)備

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

表1 信號強(qiáng)度表

距離與RSSI 值的轉(zhuǎn)化利用轉(zhuǎn)化公式，在轉(zhuǎn)化之前的第一步需要先測量出A 的值，測量方法是室內(nèi)部署好AP 后，距離其中一個AP 一米時測量信號強(qiáng)度，同樣采用多次測量去除奇異點(diǎn)得到一個較為準(zhǔn)確的值。第二步，矯正測試環(huán)境衰減因子n 的值，因?yàn)樵诓煌覂?nèi)環(huán)境中，環(huán)境衰減因子n 的值是不同的，經(jīng)過矯正測試，得到一個最佳值。第三步，將RSSI 值轉(zhuǎn)化為距離。因?yàn)閷?shí)驗(yàn)場景障礙物較少，無墻壁、石膏等障礙，所以環(huán)境中信號衰減相對較少。經(jīng)實(shí)驗(yàn)，最后確定A的值為30，環(huán)境衰減因子n 的值為1.5，再根據(jù)信號強(qiáng)度與距離的轉(zhuǎn)化公式求得與每個AP 的距離。

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

表2 定位結(jié)果

6 結(jié)語

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