無線傳感器網絡DV—Hop定位算法研究

呂元海 王海波

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

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

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

0 引 言

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

1 網絡模型

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

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

（2）為保證網絡的連通性，避免不可達節點的出現，盡量保證信標節點和未知節點的分散密集[4]。

（3）每個節點位置均已知。

2 算法設計

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

2.1.1 設計思想

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

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

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

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

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

2.1.2 算法流程圖

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

2.2 基于求交線的三邊測量

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

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

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

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

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

2.3 算法流程圖

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

3 仿真實驗與性能分析

3.1 仿真實驗

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

3.2 性能分析

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

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

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

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

定位誤差的方差隨信標節點變化的趨勢如圖13所示，保持未知節點的個數不變，隨著信標節點個數的增加，兩種算法所求得的平均誤差的方差均逐步減小。基于求交點的三邊測量法對每個未知節點的定位誤差的波動較小，而基于求交線的三邊測量法在定位誤差上波動比較大?？傮w上，基于求交線的三邊測量法平均誤差的方差始終大于基于求交點的三邊測量法的平均誤差的方差。

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

4 結 語

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

參考文獻

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

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

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

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

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