基于質心的改良Wi—Fi三邊定位算法設計與分析

藍茂俊+陳正銘+戴經(jīng)國+張楠

摘 要：針對節(jié)點不均勻導致的Wi-Fi三邊定位算法精度較低的問題，提出了基于質心的改良Wi-Fi三邊定位算法。該算法通過計算相交圓的公共區(qū)域所組成的質心來提高對待測點位置估算的精確度，然后通過數(shù)據(jù)圖表分析，證明基于質心改良后的Wi-Fi三邊定位算法的確比原三邊定位算法定位精確度更高。

關鍵詞：WI-FI；定位；三邊定位算法；質心定位算法

中圖分類號：TP393.1 文獻標識碼：A

1 引言（Introduction）

Wi-Fi全稱Wireless Fidelity，又可稱為無線保真網(wǎng)絡，是一種可以將個人電腦、手機等終端設備以無線連接的方式進行數(shù)據(jù)傳輸?shù)募夹g，相比藍牙和紅外線技術，具備傳送范圍更廣、速率更快、和多設備連接等特點。現(xiàn)如今隨著無線網(wǎng)絡的迅速發(fā)展，許多新興應用的通信設備大量涌現(xiàn)[1]并運用于許多公共場所和商業(yè)服務，包括搜索救援、災難搶險和基于位置的服務，這導致對無線連接用戶的位置信息需求逐步增多[2]。因此需要比較成熟的定位技術去監(jiān)測信息，而監(jiān)測信息必須和位置相結合才有意義[3]，如三邊定位算法，雖然它能快速和較為精確地定位，但是存在節(jié)點不均勻導致的精度較低的問題。為了提高三邊定位算法的精確度，本文將通過質心算法的思想提出基于質心的改良Wi-Fi三邊定位算法的實現(xiàn)過程與實驗分析。

2 三邊定位算法簡述（The sketch of trilateral localization algorithm）

三邊定位算法是依靠三個坐標點的位置，通過三邊定位的公式求需定位點的坐標值[4]。根據(jù)此算法分成兩個步驟：測量距離以及進行定位。

2.1 測量距離

待測點首先需要接收來自三個RSS點，前提是這三個RSS點的位置AP已知并且不重復。假設這三個RSS點分別為P1（X1，Y1）、P2（X2，Y2）和P3（X3，Y3）。由于無線信號在傳輸過程當中一般會受路徑損耗、陰影衰落等因素影響，其接收信號的功率隨距離的變化關系可由信號傳輸損耗模型體現(xiàn)[5]。信號傳輸損耗模型如式（1）所示。

式（1）中，d是某一個已知位置的RSS點與待測點的距離，而ε代表非自由空間的損耗系數(shù)，K是一個常數(shù)[6]，可由式（2）體現(xiàn)。

2.2 定位

假設待測點為S（X，Y），在上一步測量距離過程當中，可用三個已知位置的RSS點作為圓心，以RSS點與待測點的距離d作為半徑做圓，得到三個圓的共同交點，如圖1所示。

如果存在三個圓相交能得出唯一交點時，可以利用式（3）—式（5）[7]，解出點S的坐標。

但是，這只是其中一種情況，還有以下兩種情況，如圖2所示。

這受限于測量距離的精度不夠，雖然也是可以通過特定的公式計算出待測點的坐標，但是計算方式比較復雜，且算出的是一個近似范圍解，不能精確定位。

三邊定位算法由于存在許多的能夠影響信號傳輸?shù)囊蛩兀绛h(huán)境的變化，其他的信號波的干擾等，這些都會造成傳輸損耗模型有所不同，導致測量距離d受到影響，致使待測點的位置誤差較大。

3 基于質心的改良Wi-Fi三邊定位算法的思路（The thought of the Wi-Fi trilateral positioning algorithm based on centroid）

針對三邊定位算法的缺陷，提出將質心算法[8]的思想融入到三邊定位算法里面，通過多次計算相交圓的公共區(qū)域所組成的質心來估算出待測點的位置，以提高計算出待測點的坐標位置的精確度的思路，而該算法需要滿足網(wǎng)絡環(huán)境中已知的RSS點位于待測點的外側且這些RSS不少于三個。

第一步，假設三個RSS點分別為A（X0，Y0）、B（X1，Y1）、C（X2，Y2），以及假設待測點為S（X，Y）。三個RSS點作為相交圓的圓心，以圓心到待測點的距離作為半徑形成三個圓，假設三個RSS點到待測點的距離分別為d1、d2、d3。

第二步，計算出點與點之間的距離，假設點A到點B的距離為D1，點A到點C的距離為D2，點B到點C的距離為D3。將三個RSS點連接形成三角形ABC，其中包含進去了三個RSS點到待測點的距離邊。因此可以通過三角形定理得出結論，如式（6）—式（10）所示。

通過這五個結論，可分兩種情況來判斷，第一種情況是當不滿足后三個結論的任意一個時，將對d1、d2、d3對應的三條邊都增加其對應外邊減去當前大三角形內(nèi)部對應外邊所形成的三角形的最小邊的差的一定倍數(shù)。另外一種情況是當不滿足前兩個結論時，將對d1、d2、d3對應的三條邊都減少當前大三角形內(nèi)部對應外邊所形成的三角形的最大邊減去對應外邊的差的一定倍數(shù)。直至滿足這五個結論才進入到下一步。

第三步假設求出圓A與圓B的交點分別為（Xab1，Yab1）、（Xab2，Yab2），圓A與圓C的交點分別為（Xac1，Yac1）、（Xac2，Yac2），以及圓B與圓C的交點分別為（Xbc1，Ybc1）、（Xbc2，Ybc2）。之后通過公式（X-X1）2+（Y-Y1）2求出圓A和圓B的兩個交點中離圓C最近的點，假設為（Xab1，Yab1）。同理可以求出圓A和圓C的兩個交點中離圓B最近的點假設為（Xac1，Yac1），以及圓B和圓C的兩個交點中離圓A近的點，假設為（Xbc1，Ybc1）。如果這三個點完全一致的話，那么這個交點即為待測點，否則將以這三個交點為圓心，再進行上述流程。一般此過程重復三次左右即可較大程度地提高對待測點的精確度。若重復十次之后三個點仍然不一致的話，可用質心定位算法的思想去估算待測點的坐標，求法如式（11）所示。

4 實驗與分析（The experiment and analysis）

待測點定位算法優(yōu)劣性主要從待測點的定位準確度、網(wǎng)絡中RSS的密度、待測點的密度、網(wǎng)絡規(guī)模等方面進行評估[8]。本文只針對算法本身所估算出來的待測點的定位精度進行分析。

通過Java代碼分別對三邊定位算法以及本文所提出的改良算法的優(yōu)劣性進行分析比較，仿真過程如下：

（1）在10*10的平面直角坐標中隨機生成至少三個RSS點，這里為了方便就設定隨機生成三個RSS點，分別為A點（X1，Y1）、B點（X2，Y2）和C點（X3，Y3）。（實際中如果出現(xiàn)超過三個RSS點的話則可以通過Wi-Fi覆蓋等級尋找出一個RSS分布較為均勻的網(wǎng)絡環(huán)境，在此環(huán)境尋找出滿足本算法條件的三個RSS點。

（2）尋找出三個RSS點之后將其形成三角形ABC，在其內(nèi)部的隨機位置生成D點，假設為（X，Y）。

（3）計算AD、BD、CD的距離假設分別為d1、d2、d3，以及計算AB、AC、BC的距離假設分別為D1、D2、D3。

（4）為d1、d2、d3分別加上人為誤差后假設為D1、D2、D3，以確保實驗的真實性。

（5）根據(jù)式（6）—式（10）讓三角形ABC滿足五個結論。

（6）根據(jù)A、B、C三點的坐標值，以及D1、D2、D3，通過三邊定位算法和本文所提出的改良算法估算出待測點的坐標點，假設求出的待測點分別為（Xthr，Ythr）、（Xcen，Ycen）。

（7）分別根據(jù)上述兩種算法估算出坐標值（Xthr，Ythr）、（Xcen，Ycen）與點D的真實值（X，Y）根據(jù)公式（X-X1）2+（Y-Y1）2=d12求出兩點直接的距離并作為其誤差。

（8）在同一設定誤差值下重復以上過程50次，求出平均誤差并記錄數(shù)據(jù)。通過數(shù)據(jù)表格來進行比較分析，如表1和圖3所示。

從表格列出的誤差可以看出，本文所提出的算法與三邊定位算法相比較好地解決了定位精度較低的問題。

5 結論（Conclusion）

本文中介紹并分析比較了三邊定位算法，以及質心定位算法，針對三邊定位算法的不足，將質心定位算法的思想引入到本算法中，使本算法與三邊定位算法相比更有效地解決定位精度較低的問題。

本文中所提出的改良的定位算法還是有一定的局限性例如至少需要三個RSS點，在日后的工作中將針對RSS隨機分布的情況加以研究，以找出更加好地定位算法。

參考文獻（References）

[1] Zhong Ming，et al.Channel-Hopping Algorithm for Rendezvous Based on Asymmetric Model in Cognitive Networks[J].Journal of South China University of Technology（Natural Science Edition），2015，43（5）：35-39.

[2] Deng Zhongliang，et al.Situation and Development Tendency of Indoor Positioning[J].China Communications，2013（3）：42-55.

[3] Xu B，et al.High-Accuracy TDOA-Based Localization Without Time Synchronization[J].IEEE Transactions on Parallel and Distributed Systems，2013，24（8）：1567-1576.

[4] 朱劍，等.基于RSSI均值的等邊三角形定位算法[J].東北大學學報（自然科學版），2007，28（8）：1094.

[5] 盧恒惠，劉興川，張超.基于三角形與位置指紋識別算法的Wi-Fi定位比較[J].移動通信，2010（10）：72-76.

[6] 陸霞.Wi-Fi定位技術——基于質心定位的三邊定位算法的研究[J].電腦知識與技術，2013（9）：5765-5767.

[7] 鄭學偉.基于權值參數(shù)的Wi-Fi定位算法研究[J].理論與方法，2014（3）：35-37.

[8] Bulusu N，Heidemann J，Estrin D.GPS-Less Low Cost Outdoor Localization for Very Small Devices[J].IEEE Personal Communication，2000（5）：28-34.

作者簡介：

藍茂俊（1996-），男，本科生.研究領域：Java開發(fā).

陳正銘（1978-），男，碩士，講師.研究領域：數(shù)據(jù)結構，計算機應用軟件開發(fā).

戴經(jīng)國（1962-），男，碩士，教授.研究領域：網(wǎng)絡信息安全，高可靠性軟件.

張 楠（1994-），女，本科生.研究領域：項目運維，團隊管理.