無線傳感器網(wǎng)絡DV—Hop定位算法研究

呂元海 王海波

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

關鍵詞：定位；DV-Hop；三邊測量；MyEclipse

中圖分類號：TP212.9 文獻標識碼：A 文章編號：2095-1302（2016）07-00-04

0 引 言

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

1 網(wǎng)絡模型

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

（1）實驗中，隨機在實驗區(qū)域內布置出同構的信標節(jié)點和未知節(jié)點，節(jié)點半徑均為5 m，每個節(jié)點的通信半徑為10 m。

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

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

2 算法設計

2.1 基于求交點的三邊測量法

2.1.1 設計思想

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

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

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

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

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

2.1.2 算法流程圖

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

2.2 基于求交線的三邊測量

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

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

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

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

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

2.3 算法流程圖

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

3 仿真實驗與性能分析

3.1 仿真實驗

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

3.2 性能分析

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

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

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

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

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

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

4 結 語

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

參考文獻

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

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

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

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

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