無線傳感器網(wǎng)絡（Wireless Sensor Networks）是當前在國際上備受關注的、涉及多學科高度交叉、知識高度集成的前沿熱點研究領域 .對于傳感器網(wǎng)絡來說， 傳感器節(jié)點的位置信息至關重要， 事件發(fā)生的位置或獲取信息的節(jié)點位置是傳感器節(jié)點監(jiān)測消息中所包含的重要信息， 沒有位置信息的監(jiān)測數(shù)據(jù)往往毫無意義。因受成本、功耗、擴展性等問題的限制， 為每個傳感器安裝GPS模塊等這些傳統(tǒng)定位手段并不實際， 甚至在某些場合可能根本無法實現(xiàn)， 而且GPS定位在定位精度、實時性方面有時并不能滿足特定的需求， 因此針對具體的定位需求， 必須采用一定的算法機制來實現(xiàn)傳感器節(jié)點的定位。

無線傳感器網(wǎng)絡節(jié)點按定位過程中是否需要測距信息， 可分為無需測距的定位方法和基于測距技術的定位方法。近年來， 關于傳感器網(wǎng)絡節(jié)點定位技術研究成為無線傳感網(wǎng)絡技術的一重要研究熱點并取得大量的研究成果。其中， 具有代表性算法研究成果有： 凸規(guī)劃算法及其改進算法 , APS 算法、Cooperative Ranging 、AHLos 算法、nHopMultilateration Primitive 算法、MDS-MAP 算法等。

無需測距的定位方法被認為是一類具有好的成本效益的解決方案。在無需測距定位方法中， DV-Hop（ Distance Vector-Hop） 節(jié)點定位方法由于對信標節(jié)點比例要求較少， 定位精度較高， 目前已成為一種經(jīng)典的無需測距定位方法。

DV-Hop定位方法的主要思想是引入最短路徑算法到信標節(jié)點的選擇過程中， 從而在未知節(jié)點的位置估計過程中可以有效利用多跳信標節(jié)點的位置信息， 這種方法可以大大減少實現(xiàn)網(wǎng)絡定位所需信標節(jié)點的比例（密度）， 從而大大降低網(wǎng)絡的布置成本。

本文就DV-Hop算法的誤差成因進行了分析，在DV-Hop 定位算法優(yōu)點的基礎上， 針對該算法只適用于各向同性網(wǎng)絡的不足， 對DV Hop 算法進行局部優(yōu)化， 使得改進后的DV-Hop 算法減少了數(shù)據(jù)包發(fā)送量， 提高了定位精度， 并且對于不規(guī)則形狀的節(jié)點分布具有較強的適應性。

1 DV-Hop 定位算法

DV-Hop定位算法是APS算法系列中使用最為廣泛的定位方法， 其定位過程不依賴于測距方法， 利用多跳信標節(jié)點信息來參與節(jié)點定位， 定位覆蓋率較大。DV-Hop 算法非常類似于傳統(tǒng)網(wǎng)絡中的距離向量路由機制， 在該定位機制中， 未知節(jié)點首先計算與信標節(jié)點的最小跳數(shù)， 然后估算平均每跳距離， 利用最小跳數(shù)乘以平均每跳距離， 估算得到未知節(jié)點與信標節(jié)點之間的距離， 再利用三邊測量法或極大似然估計法計算未知節(jié)點的坐標。

DV-Hop定位算法可以分為以下3個階段：

（ 1） 計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)。

信標節(jié)點向鄰居節(jié)點廣播自身位置信息的分組， 其中包括跳數(shù)字段， 初始化為0.接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數(shù)， 忽略來自同一個信標節(jié)點的較大跳數(shù)的分組。然后將跳數(shù)值加1,并轉(zhuǎn)發(fā)給鄰居節(jié)點。通過這個方法網(wǎng)絡中的所有節(jié)點能夠記錄下到每個信標節(jié)點的最小跳數(shù)。

（ 2） 計算未知節(jié)點與信標節(jié)點的實際跳段距離。

每個信標節(jié)點根據(jù)第1階段中記錄的其他信標節(jié)點的位置信息和相距跳數(shù)， 利用式（1）估算平均每跳的實際距離：

其中， （ xi, yi ）、（ xj, yj ）是信標節(jié)點i、j 的坐標， hj 是信標節(jié)點i與j（ i≠j）之間的跳段數(shù)。

然后， 信標節(jié)點將計算的每跳平均距離用帶有生存期的字段的分組廣播到網(wǎng)絡中， 未知節(jié)點僅記錄接收到的第1個每跳平均距離， 并轉(zhuǎn)發(fā)給鄰居節(jié)點。這個策略可以確保絕大多數(shù)未知節(jié)點從最近的信標節(jié)點接收每跳平均距離。未知節(jié)點接收到平均每跳距離后， 根據(jù)記錄的跳數(shù)， 計算到每個信標節(jié)點之間的距離。

（ 3） 未知節(jié)點計算自身位置。

未知節(jié)點利用第2階段中記錄的到各個信標節(jié)點的跳段距離， 利用三邊測量法或極大似然估計法計算出自身坐標。

如圖1所示， 經(jīng)過第1和第2階段， 能夠計算出信標節(jié)點L1 與L2、L3 之間的距離和跳數(shù)。信標節(jié)點L2 計算得到校正值（即每跳平均距離）為（ 40 +75） / （ 2+ 5） = 16. 42.假設未知節(jié)點A 從L2 獲得校正值， 則它與3 個信標節(jié)點之間的距離分別為L1: 3×16. 42, L2: 2×16. 42, L3: 3×16. 42, 最后可利用三邊測量法確定節(jié)點A 的位置。

圖1 DV H op算法示意圖

DV-Hop算法采用平均每跳距離來估算實際距離， 對節(jié)點的硬件要求低， 實現(xiàn)簡單。其缺點是利用跳段距離代替直線距離， 存在一定的誤差。

2 DV-Hop算法誤差分析

在DV-Hop定位算法中， 算法的第1階段， 由于傳感器節(jié)點隨機分布和廣播分組過程中可能存在沖突等因素， 節(jié)點得到的到信標節(jié)點的最小跳數(shù)存在有一定偏差， 且跳數(shù)越多， 偏差越大。

在信標節(jié)點采用式（1）估算平均每跳距離時，所利用的是除本節(jié)點外所有其他信標節(jié)點， 所以得到的是全網(wǎng)絡范圍內(nèi)的平均每跳距離， 不能反映本信標節(jié)點局部范圍內(nèi)的網(wǎng)絡密度分布情況。因此，采用該方法得出的平均每跳距離在密度均勻的各向同性網(wǎng)絡中影響不大， 但在密度不均勻的各向異性網(wǎng)絡中， 就會造成較大的誤差。

在DV-Hop算法的第3階段， 未知節(jié)點利用了到所有信標節(jié)點的距離信息， 而據(jù)前面的分析， 未知節(jié)點到信標節(jié)點的最小跳數(shù)可能有偏差， 跳數(shù)越多，偏差越大， 且第2階段得出的平均每跳距離也只是對實際距離的一種估算， 不可避免會存在著誤差， 這樣信標節(jié)點距未知節(jié)點跳數(shù)越多， 二者之間的跳段距離估算誤差就越大， 利用較遠信標節(jié)點的距離信息參與位置計算， 反而可能降低了定位結(jié)果的精確度。

3 DV-Hop算法改進

根據(jù)上面的分析， 本文對DV-Hop算法加以改進， 改進后的方法計算過程仍與原DV-Hop算法大致相同， 下面僅對改進之處加以說明。

在DV-Hop算法的第1階段， 信標節(jié)點向鄰居節(jié)點廣播自身位置信息的分組時， 該分組加上生存期字段n, 其它節(jié)點在轉(zhuǎn)發(fā)該廣播包時， 首先檢測生存期字段， 如果n 大于1, 則n = n - 1, 轉(zhuǎn)發(fā)廣播包；如果n 不大于1, 則不再轉(zhuǎn)發(fā)該廣播包， 以保證該分組僅在n跳范圍內(nèi)廣播。這樣每個節(jié)點僅收到n跳范圍內(nèi)信標節(jié)點信息， 降低了原DV-Hop算法全網(wǎng)洪泛造成的高通信開銷、高分組沖突概率。

在DV-Hop算法的第2階段， 利用式（1）估算平均每跳實際距離時， 信標節(jié)點j 取自該節(jié)點n 跳范圍內(nèi)跳數(shù)最少的m 個信標節(jié)點。這樣處理保證估算的平均每跳實際距離更符合該節(jié)點附近的節(jié)點分布， 提高了距離估計精確度， 并使該方法適用于各向異性網(wǎng)絡。

最后， 在未知節(jié)點利用極大似然估計法計算自身坐標時， 由于信標距離該未知節(jié)點跳段越近， 二者之間的距離估計越精確（概率意義上）， 所以這里只取跳段距離最近的l個節(jié)點進行極大似然估計法運算。這樣， 既提高了定位精確度， 又降低了節(jié)點的計算開銷。

參數(shù)n、m、l的取值要綜合考慮信標節(jié)點比例、網(wǎng)絡的連通度、傳感器節(jié)點分布等因素。一般情況下， n 要保證絕大部分未知一個節(jié)點能收到3 個以上的信標節(jié)點分組， 而m、l取4~ 6即可取得相對高的精確度。

4 仿真分析

為了評估所提出的改進算法的可用性和有效性， 作者利用Matlab7. 0對DV-Hop算法及本文提出的改進算法（ Improved DV- Hop, IDV H op）進行了實驗仿真， 并對相關實驗結(jié)果進行分析。

仿真分析的網(wǎng)絡模型的標準參數(shù)如下： 設定節(jié)點射頻通信距離是10個長度單位， 網(wǎng)絡規(guī)模為400個節(jié)點， 均勻隨機分布在邊長為100 個長度單位的正方形中（這時的平均連通度為11左右）， 其中信標節(jié)點比例為5% .在相同的網(wǎng)絡場景下， 通過改變總節(jié)點數(shù)來改變網(wǎng)絡的連通度， 從而實現(xiàn)相同網(wǎng)絡場景下不同網(wǎng)絡連通度的仿真實驗條件。為消除隨機性產(chǎn)生的誤差， 所得仿真結(jié)果均為同樣參數(shù)下仿真100次所得結(jié)果的平均值。

（ 1） 可定位節(jié)點比例。

可定位節(jié)點比例（也稱算法覆蓋率） 是指通過定位算法成功實現(xiàn)位置估計的未知節(jié)點數(shù)量占網(wǎng)絡中所有未知節(jié)點數(shù)量的百分比。通過仿真結(jié)果（圖2, IDV- Hop算法中n 取值為3）。

圖2 可定位節(jié)點比例

可以看出， 兩種算法的可定位節(jié)點比例均和網(wǎng)絡的平均連通度、信標節(jié)點比例、算法中分組廣播的生存期字段的取值都有關系； 在同樣的參數(shù)條件下，IDV-Hop算法的可定位節(jié)點比例和DV-Hop算法相比要低若干個百分點， 這是因為在算法第1階段， 可控洪泛使得部分未知節(jié)點收到的信標節(jié)點小于3而不能實施第3階段的定位運算。

圖3 數(shù)據(jù)包發(fā)送量

（2） 數(shù)據(jù)包發(fā)送量。

圖3為網(wǎng)絡連通度為9和12時時， DV-Hop算法與IDV-Hop算法在數(shù)據(jù)包發(fā)送量上的比較， 其中橫坐標表示信標節(jié)點所占的比例， 分組廣播的生存期字段均取3, IDV-Hop算法中的n 取值為3.從圖中可以看出， 網(wǎng)絡的數(shù)據(jù)通信量隨信標節(jié)點比例和網(wǎng)絡連通度的增加而增加。而在同樣的網(wǎng)絡參數(shù)下， IDV-Hop 算法的數(shù)據(jù)通信量遠小于DV-Hop算法（不到原通信量的20% ） , 這主要是由于在算法的第1階段， IDV-Hop采用的部分洪泛代替了DV-Hop算法全網(wǎng)范圍洪泛的緣故。

另外， IDV-Hop算法的數(shù)據(jù)通信量與還與n的選擇有關， 當n較小時， 該算法限制洪泛跳數(shù)范圍內(nèi)小，所需的數(shù)據(jù)通信量就小， 但n 值也不是越小越好， 如前面分析， 較小的n 值會降低算法的可定位節(jié)點比例。

（ 3） 定位精度。

定位誤差（ Localization E rror, LE）指的是通過定位算法得到的未知節(jié)點的估算位置與實際位置的偏差， 這種偏差可以用兩者之間的歐氏距離除以節(jié)點的通信半徑來衡量， 如式（ 2）所示。顯然， 定位誤差的大小能最直接說明算法的有效性。

其中（x ea, yea ）為未知節(jié)點的估算位置， （ xa, ya ）為未知節(jié)點的實際位置， R為節(jié)點的通信半徑。

圖4 節(jié)點均勻分布時的定位精度

圖4給出了傳感器節(jié)點均勻分布時， DV-Hop算法和IDV-Hop算法定位精度比較結(jié)果。可以看出，在各向同性網(wǎng)絡中， 在相同的網(wǎng)絡連通度和信標節(jié)點比例下， 改進后的算法比原算法定位精度均有所提高， 特別是在大于6% 時， IDV-Hop算法的定位精度隨著信標節(jié)點比例升高而迅速提高， 而原DVHop算法提高并不明顯， 這是由于信標節(jié)點比例越高， IDV-Hop算法越有機會采用距離估計精確度較高的鄰近信標節(jié)點進行定位運算， 從而提高了定位精度， 驗證前面對DV-Hop算法的分析。

圖5為傳感器節(jié)點非均勻分布時（節(jié)點分布從左到右逐漸由疏變密），DV-Hop算法和IDV-Hop算法定位精度結(jié)果。與圖4相比， DV-Hop算法定位精度大幅下降， 而IDV-Hop算法僅稍有下降。在同樣的網(wǎng)絡參數(shù)下， IDV-Hop算法的定位精度比DV H op算法提高了大約20%, 可見， 改進后的算法更適用于各向異性網(wǎng)絡。

圖5 節(jié)點不均勻分布時的定位精度

5 結(jié)語

本文分析了DV-Hop算法只適用于各向同性網(wǎng)絡的原因， 對DV-Hop算法進行局部性優(yōu)化， 給出了無線傳感器網(wǎng)絡無需測距DV-Hop 定位的改進算法。仿真結(jié)果表明， 改進后的算法可定位節(jié)點比例略有下降， 但提高了定位精度， 特別是節(jié)點非均勻分布時的定位精度， 減少了數(shù)據(jù)包發(fā)送量， 因此更適用于在實際項目中應用。