基于質(zhì)心的改良Wi—Fi三邊定位算法設(shè)計(jì)與分析

藍(lán)茂俊+陳正銘+戴經(jīng)國(guó)+張楠

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

關(guān)鍵詞：WI-FI；定位；三邊定位算法；質(zhì)心定位算法

中圖分類(lèi)號(hào)：TP393.1 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

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

2 三邊定位算法簡(jiǎn)述（The sketch of trilateral localization algorithm）

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

2.1 測(cè)量距離

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

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

2.2 定位

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

如果存在三個(gè)圓相交能得出唯一交點(diǎn)時(shí)，可以利用式（3）—式（5）[7]，解出點(diǎn)S的坐標(biāo)。

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

這受限于測(cè)量距離的精度不夠，雖然也是可以通過(guò)特定的公式計(jì)算出待測(cè)點(diǎn)的坐標(biāo)，但是計(jì)算方式比較復(fù)雜，且算出的是一個(gè)近似范圍解，不能精確定位。

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析（The experiment and analysis）

待測(cè)點(diǎn)定位算法優(yōu)劣性主要從待測(cè)點(diǎn)的定位準(zhǔn)確度、網(wǎng)絡(luò)中RSS的密度、待測(cè)點(diǎn)的密度、網(wǎng)絡(luò)規(guī)模等方面進(jìn)行評(píng)估[8]。本文只針對(duì)算法本身所估算出來(lái)的待測(cè)點(diǎn)的定位精度進(jìn)行分析。

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

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

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

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

（4）為d1、d2、d3分別加上人為誤差后假設(shè)為D1、D2、D3，以確保實(shí)驗(yàn)的真實(shí)性。

（5）根據(jù)式（6）—式（10）讓三角形ABC滿(mǎn)足五個(gè)結(jié)論。

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

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

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

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

5 結(jié)論（Conclusion）

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

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

參考文獻(xiàn)（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].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，28（8）：1094.

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

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

[7] 鄭學(xué)偉.基于權(quán)值參數(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.

作者簡(jiǎn)介：

藍(lán)茂?。?996-），男，本科生.研究領(lǐng)域：Java開(kāi)發(fā).

陳正銘（1978-），男，碩士，講師.研究領(lǐng)域：數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)應(yīng)用軟件開(kāi)發(fā).

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

張 楠（1994-），女，本科生.研究領(lǐng)域：項(xiàng)目運(yùn)維，團(tuán)隊(duì)管理.