朱慧勇

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

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

1 DV-Hop算法的過程

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

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

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

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

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

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

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

3.1 未知節(jié)點計算自己的位置

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

3.2 DV-Hop算法的性能分析

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

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

圖1 節(jié)點隨機分布

圖2 定位誤差

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

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

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

4.1 客觀因素

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

4.2 主觀因素

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

圖3 不良節(jié)點

4.2.1 最小跳數(shù)

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

4.2.2 平均跳距

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

4.2.3 估計距離

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

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

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

5 結(jié)語

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

[參考文獻]

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