呂元海 王海波

摘 要：基于非測距的DV-Hop定位算法，根據(jù)距離未知節(jié)點(diǎn)最近的三個信標(biāo)節(jié)點(diǎn)之間的覆蓋關(guān)系，利用三邊測量法估算未知節(jié)點(diǎn)的坐標(biāo)，將傳統(tǒng)三邊測量法改進(jìn)后估計未知節(jié)點(diǎn)的坐標(biāo)值，并利用MyEclipse平臺進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的三邊測量算法能對無線未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行有效地定位。

關(guān)鍵詞：定位；DV-Hop；三邊測量；MyEclipse

中圖分類號：TP212.9 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2016）07-00-04

0 引 言

無線傳感網(wǎng)絡(luò)中，在對節(jié)點(diǎn)自身定位的研究中[1]，很多改進(jìn)定位精度的算法被提出來，但由于多種原因例如節(jié)點(diǎn)定位帶來的開銷、大規(guī)模無線傳感器網(wǎng)絡(luò)中存在的誤差累計等并沒有一種完善的DV-Hop算法，因此，包括DV-Hop定位算法在內(nèi)的很多定位算法仍然需要進(jìn)一步的研究和探索[2]。

1 網(wǎng)絡(luò)模型

為了驗(yàn)證改進(jìn)后的估算未知節(jié)點(diǎn)坐標(biāo)的三邊測量法[3]，將其實(shí)驗(yàn)平臺設(shè)置為一個矩形區(qū)域，并在此區(qū)域內(nèi)隨機(jī)部署若干實(shí)驗(yàn)節(jié)點(diǎn)，作以下要求：

（1）實(shí)驗(yàn)中，隨機(jī)在實(shí)驗(yàn)區(qū)域內(nèi)布置出同構(gòu)的信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)，節(jié)點(diǎn)半徑均為5 m，每個節(jié)點(diǎn)的通信半徑為10 m。

（2）為保證網(wǎng)絡(luò)的連通性，避免不可達(dá)節(jié)點(diǎn)的出現(xiàn)，盡量保證信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的分散密集[4]。

（3）每個節(jié)點(diǎn)位置均已知。

2 算法設(shè)計

2.1 基于求交點(diǎn)的三邊測量法

2.1.1 設(shè)計思想

基于求交點(diǎn)的三邊測量法將三個圓在平面中所形成的交點(diǎn)情況分為四類進(jìn)行討論，其中（xi， yi）代表未知節(jié)點(diǎn)的坐標(biāo)值。

（1）三個圓兩兩相交時，會形成六個交點(diǎn)，如圖1所示，將這六個交點(diǎn)的平均值作為未知節(jié)點(diǎn)的估計位置，此時（xi，yi）的值使用式（1）計算。

（2）當(dāng)一個圓同時與其它兩個圓有交點(diǎn)時，會形成四個交點(diǎn)，選取如圖2所示的四個交點(diǎn)兩兩連線，連線的長度分別為d1，d2，d3，d4，選出長度最小的直線，用它兩個端點(diǎn)的均值作為未知節(jié)點(diǎn)的估計位置，采用式（2）計算。

（3）三個圓中只有兩個圓相交時，如圖3所示，計算出兩圓交點(diǎn)后再分別計算出這兩個交點(diǎn)與第三個圓圓心的距離d1，d2，將距圓心距離小的點(diǎn)的坐標(biāo)值作為未知節(jié)點(diǎn)的估計位置，按式（3）計算。

（4）當(dāng)三個圓沒有任何交點(diǎn)時，這種情況依然利用基于求交線的三邊測量法來計算未知節(jié)點(diǎn)的估計距離。

2.1.2 算法流程圖

基于求交點(diǎn)的三邊測量法流程如圖4所示。

2.2 基于求交線的三邊測量

將三個圓在平面中的位置關(guān)系分為兩類：內(nèi)含和其它，以此為基礎(chǔ)將三個圓之間形成的交線分為三種情況討論。其中（xi， yi）代表未知節(jié)點(diǎn)的坐標(biāo)值，三個圓的圓心坐標(biāo)為（x1， y1），（x2，y2），（x3，y3），半徑為r1，r2，r3，所對應(yīng)的三個圓的方程如式（4）所示：

圓的方程兩兩相減求出直線如式（5）所示：

（1）三個圓中兩組圓的位置關(guān)系均為其它。圖5所示以兩條直線的交點(diǎn)作為未知節(jié)點(diǎn)的估計位置。

（2）三個圓中一組圓的位置關(guān)系為其它，如圖6所示，求出交線后，在任選兩個圓的圓心，求過兩個圓圓心的直線，求出交點(diǎn)。

（3）三個圓均沒有其它位置關(guān)系。三個圓沒有其它位置關(guān)系的情況非常少見，即三個圓均存在內(nèi)含關(guān)系，如圖7所示。在這種情況下估算未知節(jié)點(diǎn)坐標(biāo)時，選取兩組圓心間的連線形成交點(diǎn)，在實(shí)驗(yàn)中發(fā)現(xiàn)，由于此位置關(guān)系的特殊性，三個信標(biāo)節(jié)點(diǎn)的距離非常相近，在這種計算方式中，三個信標(biāo)節(jié)點(diǎn)的任一信標(biāo)節(jié)點(diǎn)坐標(biāo)會被視為未知節(jié)點(diǎn)的估計位置。形成交點(diǎn)時，此交點(diǎn)作為未知節(jié)點(diǎn)的估計位置，如果出現(xiàn)沒有交點(diǎn)的情況，那么未知節(jié)點(diǎn)將無法定位，所以這種位置關(guān)系的定位精度相對較差[5]，特殊情況下甚至無法定位。

2.3 算法流程圖

基于求交線的三邊測量法流程如圖8所示。

3 仿真實(shí)驗(yàn)與性能分析

3.1 仿真實(shí)驗(yàn)

本實(shí)驗(yàn)通過在MyEclipse中編寫Java代碼來模擬上述算法的仿真實(shí)驗(yàn)，模擬區(qū)域參數(shù)設(shè)置為70 m×70 m，在實(shí)驗(yàn)區(qū)域內(nèi)部署30個同構(gòu)的信標(biāo)節(jié)點(diǎn)和100個同構(gòu)的未知節(jié)點(diǎn)，節(jié)點(diǎn)半徑為5 m。在實(shí)驗(yàn)過程中，為了測試所寫算法對定位精度的影響，首先保持信標(biāo)節(jié)點(diǎn)個數(shù)不變，將未知節(jié)點(diǎn)的個數(shù)分別設(shè)置為100、200、300、400、500。再保持未知節(jié)點(diǎn)個數(shù)不變，將信標(biāo)節(jié)點(diǎn)的個數(shù)分別設(shè)置為10、20、30、40、50。實(shí)驗(yàn)平臺如圖9所示。

3.2 性能分析

在實(shí)驗(yàn)過程中，計算出未知節(jié)點(diǎn)的估計坐標(biāo)后，由于生成坐標(biāo)時未知節(jié)點(diǎn)的坐標(biāo)是已知的，計算出估計的坐標(biāo)值與實(shí)際的坐標(biāo)值之差越小，證明估算誤差越小。

定位誤差隨未知節(jié)點(diǎn)變化的趨勢如圖10表示，增加未知節(jié)點(diǎn)的個數(shù)，通過兩種算法計算出的各個未知節(jié)點(diǎn)的估計坐標(biāo)與實(shí)際坐標(biāo)之差的平均數(shù)，從圖中折線圖的走向來看，此時基于求交線的三邊測量法的定位平均誤差在不斷增大，而基于求交點(diǎn)的三邊測量法的平均誤差保持穩(wěn)定，增大幅度較小，且基于求交點(diǎn)的三邊測量法的平均誤差始終比基于求交線的三邊測量法的平均誤差小。

定位誤差隨信標(biāo)節(jié)點(diǎn)變化的趨勢如圖11所示，保持未知節(jié)點(diǎn)數(shù)目不變，逐漸增多信標(biāo)節(jié)點(diǎn)的個數(shù)為10，20，30，40，50，計算出平均誤差后整理出折線圖，可以從折線圖的走勢看出，兩種定位算法的平均誤差都在逐漸減小，但基于求交點(diǎn)的三邊測量法的平均誤差始終小于基于求交線的三邊測量法的平均誤差，并且下滑趨勢快，所以，隨著信標(biāo)節(jié)點(diǎn)數(shù)目的增多，基于求交點(diǎn)的三邊測量法的定位精度優(yōu)于基于求交線的三邊測量法。

定位誤差的方差也可作為定位精度的參考，方差在通常情況下表示的是數(shù)據(jù)波動性的大小，在本實(shí)驗(yàn)中，平均誤差的方差所代表的是某一定位方法中定位精度波動的大小。定位誤差的方差隨未知節(jié)點(diǎn)變化的趨勢如圖12所示，使用平均誤差的方差時，隨著未知節(jié)點(diǎn)個數(shù)的增加，基于求交線的三邊測量法平均誤差的方差始終大于基于求交點(diǎn)的三邊測量法平均誤差的方差，并且基于求交線的三邊測量法的方差整體呈增大趨勢，而基于求交點(diǎn)的三邊測量法的方差保持穩(wěn)定。由此可知，未知節(jié)點(diǎn)個數(shù)增多時，基于求交線的三邊測量法對于單個節(jié)點(diǎn)定位的誤差波動逐漸增大，而基于求交點(diǎn)的三邊測量法的定位精度保持穩(wěn)定，比較具有可靠性。

定位誤差的方差隨信標(biāo)節(jié)點(diǎn)變化的趨勢如圖13所示，保持未知節(jié)點(diǎn)的個數(shù)不變，隨著信標(biāo)節(jié)點(diǎn)個數(shù)的增加，兩種算法所求得的平均誤差的方差均逐步減小?；谇蠼稽c(diǎn)的三邊測量法對每個未知節(jié)點(diǎn)的定位誤差的波動較小，而基于求交線的三邊測量法在定位誤差上波動比較大。總體上，基于求交線的三邊測量法平均誤差的方差始終大于基于求交點(diǎn)的三邊測量法的平均誤差的方差。

由實(shí)驗(yàn)可以看出，平均誤差在保持未知節(jié)點(diǎn)的數(shù)目不變時，改變信標(biāo)節(jié)點(diǎn)數(shù)目，信標(biāo)節(jié)點(diǎn)數(shù)目越多，定位的精度越高，根據(jù)研究數(shù)據(jù)可知，綜合平均誤差來看，兩種算法均優(yōu)于傳統(tǒng)三邊測量法，但基于求交點(diǎn)的三邊測量法的定位精度高于基于求交點(diǎn)的三邊測量法，故可得出結(jié)論，基于求交點(diǎn)的三邊測量法的定位精度較高。

4 結(jié) 語

本文設(shè)計了基于RSSI實(shí)現(xiàn)網(wǎng)絡(luò)目標(biāo)定位的條件概率定位算法和均值定位算法，通過仿真實(shí)驗(yàn)證明，這兩種算法都能夠?qū)崿F(xiàn)無線傳感網(wǎng)絡(luò)中未知節(jié)點(diǎn)的定位，但在同等環(huán)境下，條件概率定位算法在穩(wěn)定性、平均誤差和定位精度等方面均優(yōu)于均值定位算法。本文的研究僅基于二維空間，具有一定的局限性，下一步將在三維空間中實(shí)現(xiàn)未知節(jié)點(diǎn)的定位問題。

參考文獻(xiàn)

[1]王珊珊，殷建平，蔡志平，等.基于RSSI的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位算法[J].計算機(jī)研究與發(fā)展，2008，45（S1）：385-388.

[2]李成岳.基于DV-Hop的無線傳感器節(jié)點(diǎn)定位算法研究[D].長春：吉林大學(xué)，2011.

[3]秦小虎，辛云宏，夏海峰，等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)[J].計算機(jī)系統(tǒng)應(yīng)用，2011，20（9）：117-121.

[4]催遜學(xué)，左從菊.無線傳感器網(wǎng)絡(luò)簡明教程[M].北京：清華大學(xué)出版社，2009：17-19.

[5]趙文輝，姜宇，劉大昕.高精度無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].哈爾濱工程大學(xué)學(xué)報，2009，30（4）：466-471.