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

朱慧勇

（西安鐵路職業(yè)技術(shù)學(xué)院，陜西 西安 710026）

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

1 DV-Hop算法的過程

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

2 獲得節(jié)點(diǎn)距錨節(jié)點(diǎn)的最小跳數(shù)

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

3 未知節(jié)點(diǎn)獲得平均跳距

錨節(jié)點(diǎn)根據(jù)自己存儲的消息，即其他錨節(jié)點(diǎn)的標(biāo)識符、位置信息和跳數(shù)值通過式（1）運(yùn)算得到這個(gè)錨節(jié)點(diǎn)跟其他錨節(jié)點(diǎn)之間的每跳的平均距離，即平均跳距：

i代表這個(gè)錨節(jié)點(diǎn)，j代表其他錨節(jié)點(diǎn)，（xi,yi）和（xj,yj）分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的位置的坐標(biāo)，hopj表示錨節(jié)點(diǎn)i和錨節(jié)點(diǎn)j的跳數(shù)值，HopSizei是錨節(jié)點(diǎn)i的平均跳距。

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

3.1 未知節(jié)點(diǎn)計(jì)算自己的位置

這時(shí)，未知節(jié)點(diǎn)存儲的信息有全部錨節(jié)點(diǎn)的標(biāo)識符、位置坐標(biāo)信息和最小跳數(shù)，以及平均跳距。可以用相應(yīng)的最小跳數(shù)與平均跳距的乘積來作為未知節(jié)點(diǎn)與相應(yīng)錨節(jié)點(diǎn)的估計(jì)距離。如果未知節(jié)點(diǎn)知道與3個(gè)或者3個(gè)以上的錨節(jié)點(diǎn)的估計(jì)距離之后，就可以采用3邊定位法或者最小二乘法進(jìn)行自身定位。

3.2 DV-Hop算法的性能分析

為了更直觀地說明DV-Hop算法的性能，本文使用Matlab軟件來做仿真實(shí)驗(yàn)。仿真環(huán)境設(shè)置：100 m×100 m的二維正方形區(qū)域，節(jié)點(diǎn)總數(shù)為100個(gè)，錨節(jié)點(diǎn)為20個(gè)，節(jié)點(diǎn)通信半徑R為30 m。節(jié)點(diǎn)在仿真區(qū)域隨機(jī)分布，沒有障礙和干擾。

節(jié)點(diǎn)隨機(jī)分布圖如圖1所示，圖中*表示錨節(jié)點(diǎn)，o表示未知節(jié)點(diǎn)。定位誤差如圖2所示，中間用直線連起來的兩頭其中一個(gè)是估計(jì)位置，另一個(gè)是實(shí)際位置。本次仿真結(jié)果是定位誤差為29.6%。

圖1 節(jié)點(diǎn)隨機(jī)分布

圖2 定位誤差

在相同的條件下，又運(yùn)行了很多次，定位誤差基本保持在30%左右。運(yùn)行過程中，可以看到DV-Hop算法只需要少量的錨節(jié)點(diǎn)，計(jì)算和通信開銷適中，節(jié)點(diǎn)不需要有測距的能力，是一個(gè)可擴(kuò)展的定位算法。對于各向同性的密集網(wǎng)絡(luò)，可以得到一個(gè)合理的平均跳距，使它們能夠?qū)崿F(xiàn)更好的定位精度；但對于不規(guī)則拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，定位精度下降幅度較大。

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

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

4.1 客觀因素

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

4.2 主觀因素

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

圖3 不良節(jié)點(diǎn)

4.2.1 最小跳數(shù)

DV-Hop算法采用最小跳數(shù)為基礎(chǔ)是有一定的依據(jù)的，在選取節(jié)點(diǎn)之間的跳數(shù)的時(shí)候，通常節(jié)點(diǎn)之間會(huì)有好多條路徑，不同的路徑，跳數(shù)可能也不同，這時(shí)候，最小跳數(shù)可以在某種程度上表示兩個(gè)節(jié)點(diǎn)之間的聯(lián)系。但是如果節(jié)點(diǎn)之間最小跳數(shù)所在的路徑是‘U’型或者‘C’型的時(shí)候，最小跳數(shù)會(huì)失效，不能準(zhǔn)確表示兩節(jié)點(diǎn)之間的聯(lián)系。

4.2.2 平均跳距

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

4.2.3 估計(jì)距離

DV-Hop算法中，用最小跳數(shù)與平均跳距的乘積來作為估計(jì)距離。經(jīng)過上面的分析，節(jié)點(diǎn)之間最小跳數(shù)所在的路徑是‘U’型或者‘C’型的時(shí)候，或者節(jié)點(diǎn)的平均跳距偏小的時(shí)候，估計(jì)距離就會(huì)有很大的偏差。

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

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

5 結(jié)語

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

[參考文獻(xiàn)]

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