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

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

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

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

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

1 DV-Hop 定位算法

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

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

（ 1） 計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

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

（ 2） 計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離。

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

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

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

（ 3） 未知節(jié)點(diǎn)計(jì)算自身位置。

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

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

圖1 DV H op算法示意圖

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

2 DV-Hop算法誤差分析

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

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

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

3 DV-Hop算法改進(jìn)

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

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

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

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

（ 3） 定位精度。

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

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

圖4 節(jié)點(diǎn)均勻分布時(shí)的定位精度

圖4給出了傳感器節(jié)點(diǎn)均勻分布時(shí)， DV-Hop算法和IDV-Hop算法定位精度比較結(jié)果?？梢钥闯觯诟飨蛲跃W(wǎng)絡(luò)中， 在相同的網(wǎng)絡(luò)連通度和信標(biāo)節(jié)點(diǎn)比例下， 改進(jìn)后的算法比原算法定位精度均有所提高， 特別是在大于6% 時(shí)， IDV-Hop算法的定位精度隨著信標(biāo)節(jié)點(diǎn)比例升高而迅速提高， 而原DVHop算法提高并不明顯， 這是由于信標(biāo)節(jié)點(diǎn)比例越高， IDV-Hop算法越有機(jī)會(huì)采用距離估計(jì)精確度較高的鄰近信標(biāo)節(jié)點(diǎn)進(jìn)行定位運(yùn)算， 從而提高了定位精度， 驗(yàn)證前面對(duì)DV-Hop算法的分析。

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

圖5 節(jié)點(diǎn)不均勻分布時(shí)的定位精度

5 結(jié)語(yǔ)

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