DV-Hop定位算法的誤差分析

朱慧勇

（西安鐵路職業技術學院，陜西 西安 710026）

美國的Rutgers University（路特葛斯大學）的 Niculescu等[1]利用GPS定位和距離向量路由的原理提出了（Distance Vector-Hop，DV-Hop）定位算法。

1 DV-Hop算法的過程

DV-Hop定位算法可以分為3個過程：第一過程是無線傳感器網絡（Wireless Sensor Networks，WSN）中使用經典距離矢量交換協議來獲得節點距錨節點的最小跳數；第二過程是每個錨節點根據與其他錨節點之間的距離和最小跳數，計算自己的平均跳距，并采用可控洪泛法向全網廣播，保證未知節點僅收到一個廣播值；第三過程是未知節點利用收到的廣播值與至少3個的錨節點的最小跳距，來獲得未知節點到錨節點距離，然后采用3邊測量定位或者最小二乘法來得到自身的位置。

2 獲得節點距錨節點的最小跳數

首先使用距離矢量交換協議，錨節點向它的鄰居節點廣播消息，消息包括錨節點的標識符、位置信息和跳數值，跳數的初始值設置為0；鄰居節點接收到消息后，先將跳數值加1，然后記錄下此消息，并將記錄下的信息廣播給它的鄰居節點，重復以上步驟，直到所有節點都具有錨節點的位置信息和彼此間的最小跳數。由于采用廣播的途徑，一個錨節點廣播的消息可能多次到達同一節點，導致信息冗余，增加了通信開銷。為了消除廣播消息的無限循環，只有新的錨節點消息才能被節點廣播，垃圾消息將被拋棄。垃圾消息是指節點在接收信息的時候，由于路徑的不同，導致節點可能收到多個相同錨節點的信息，感興趣的是跳數值最小的那條消息，其他消息都認為是垃圾消息。

3 未知節點獲得平均跳距

錨節點根據自己存儲的消息，即其他錨節點的標識符、位置信息和跳數值通過式（1）運算得到這個錨節點跟其他錨節點之間的每跳的平均距離，即平均跳距：

i代表這個錨節點，j代表其他錨節點，（xi,yi）和（xj,yj）分別表示節點i和節點j的位置的坐標，hopj表示錨節點i和錨節點j的跳數值，HopSizei是錨節點i的平均跳距。

每個錨節點經過式（1）計算后，都得到了對應的平均跳距。然后，錨節點向自己的鄰居節點廣播包含有自己平均跳距的消息，鄰居節點存儲消息后也接著廣播這條消息。重復廣播，直到所有未知節點都收到平均跳距的消息。如果未知節點收到多個包含平均跳距的消息，那么它僅存儲第一個收到的消息，拋棄后來收到的消息，這就意味著大部分未知節點收到的平均跳距是離自己最近的錨節點發出的。

3.1 未知節點計算自己的位置

這時，未知節點存儲的信息有全部錨節點的標識符、位置坐標信息和最小跳數，以及平均跳距。可以用相應的最小跳數與平均跳距的乘積來作為未知節點與相應錨節點的估計距離。如果未知節點知道與3個或者3個以上的錨節點的估計距離之后，就可以采用3邊定位法或者最小二乘法進行自身定位。

3.2 DV-Hop算法的性能分析

為了更直觀地說明DV-Hop算法的性能，本文使用Matlab軟件來做仿真實驗。仿真環境設置：100 m×100 m的二維正方形區域，節點總數為100個，錨節點為20個，節點通信半徑R為30 m。節點在仿真區域隨機分布，沒有障礙和干擾。

節點隨機分布圖如圖1所示，圖中*表示錨節點，o表示未知節點。定位誤差如圖2所示，中間用直線連起來的兩頭其中一個是估計位置，另一個是實際位置。本次仿真結果是定位誤差為29.6%。

圖1 節點隨機分布

圖2 定位誤差

在相同的條件下，又運行了很多次，定位誤差基本保持在30%左右。運行過程中，可以看到DV-Hop算法只需要少量的錨節點，計算和通信開銷適中，節點不需要有測距的能力，是一個可擴展的定位算法。對于各向同性的密集網絡，可以得到一個合理的平均跳距，使它們能夠實現更好的定位精度；但對于不規則拓撲結構的網絡，定位精度下降幅度較大。

4 DV-Hop定位算法誤差分析

影響DV-Hop算法的定位精度主要有兩方面，一方面是外部客觀因素，另一方面是算法本身的主觀因素。下面從這兩方面分析。

4.1 客觀因素

在部署無線傳感器網絡的時候，很多情況下，節點都是隨機部署的。隨機部署會造成兩方面的問題：一方面會造成網絡拓撲不規則；另一方面是節點分布不均勻。在分析DVHop算法性能的時候，DV-Hop算法適合于各同向性網絡，而對不規則網絡，定位效果比較差。節點分布不均勻主要是指錨節點和未知節點分布不均勻，比如在某片較大的區域只有一個錨節點，而在某片較小的區域有很多錨節點。節點分布不均勻會產生一些節點無法定位，這些無法定位的節點叫作不良節點。不良節點有4種情況。如圖3所示：（a）中表示完全孤立的節點，無法與整個網絡進行通信；（b）中顯示一個錨節點，它有3個鄰居未知節點，在DV-Hop算法中，是可以估計出位置的，但未知節點的位置都一樣，因此也是無法定位的；（c）中兩個錨節點是無法通過DV-Hop算法定位未知節點的；（d）中的情況和（b）類似。

4.2 主觀因素

在DV-Hop定位算法中，有4要素：未知節點到錨節點的最小跳數；未知節點收到的平均跳距；未知節點通過最小跳數乘以平均跳距來估計距離；未知節點通過3邊定位法或者最小二乘法來定位。下面按這4要素來分析誤差的產生。

圖3 不良節點

4.2.1 最小跳數

DV-Hop算法采用最小跳數為基礎是有一定的依據的，在選取節點之間的跳數的時候，通常節點之間會有好多條路徑，不同的路徑，跳數可能也不同，這時候，最小跳數可以在某種程度上表示兩個節點之間的聯系。但是如果節點之間最小跳數所在的路徑是‘U’型或者‘C’型的時候，最小跳數會失效，不能準確表示兩節點之間的聯系。

4.2.2 平均跳距

DV-Hop算法中，未知節點的平均跳距由離自己最近的錨節點計算出來，這種方法是借鑒單點代表局部，某種程度上來說也是可取的。而錨節點在計算平均跳距的時候，如果錨節點之間最小跳數比較大，而錨節點之間的歐式距離又是固定的，從而使平均跳距偏小，不利于定位。

4.2.3 估計距離

DV-Hop算法中，用最小跳數與平均跳距的乘積來作為估計距離。經過上面的分析，節點之間最小跳數所在的路徑是‘U’型或者‘C’型的時候，或者節點的平均跳距偏小的時候，估計距離就會有很大的偏差。

4.2.4 3邊定位法或者最小二乘法

采用3邊定位法，會降低計算量從而減少能量消耗，但是3邊定位法在距離信息比較準確的情況下，定位精度才準確。采用最小二乘法，如果估計距離本來就不準確，再進行處理，就會造成誤差累積，最終導致比較大的誤差。

5 結語

本文講解了DV-Hop定位算法的過程和性能分析，深入地探討了產生定位誤差的客觀原因和主觀原因。在未來的工作中，針對這些客觀原因與主觀原因，要多多思考，如何能克服這些困難。

[參考文獻]

[1]NICULESCU D，NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication systems，2003（22）：267-280.