無線傳感器網(wǎng)絡(luò)中一種改進的DV-Hop 定位算法研究*

何少尉

（浙江郵電職業(yè)技術(shù)學(xué)院，浙江 紹興 312366）

0 引言

隨著無線通信技術(shù)的快速發(fā)展，擁有感知、計算和網(wǎng)絡(luò)通信能力的傳感器以及傳感器構(gòu)成的無線傳感器網(wǎng)絡(luò)成為研究人員關(guān)注的焦點。傳感器擁有低成本、低功耗、體積小的特點，無線傳感器網(wǎng)絡(luò)有著極為廣泛的應(yīng)用前景[1-2]。節(jié)點的定位算法是傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)。DV-Hop 算法是一種廣泛研究的免測距定位算法，具有開銷小、成本低和抗噪性能強等優(yōu)點。DV-Hop 算法僅需要考慮最鄰近的信標節(jié)點的平均距離來計算平均每跳距離，使得算法的定位精度不高。目前，對DV-Hop 算法的改進已經(jīng)進行了較多研究，如文獻[3]基于進化算法提出改進的DV-Hop 定位算法，文獻[4]通過設(shè)置跳數(shù)閥值來約束節(jié)點間的最小跳數(shù)，并通過加權(quán)處理平均跳距來改善DV-Hop 定位算法的精度。相關(guān)研究均能在一定程度上提高定位精度。本文針對DV-Hop 定位算法中存在的不足，提出一種利用提高全網(wǎng)平均每跳距離來改進DV-Hop 定位算法精度的方法，以期為無線傳感器網(wǎng)絡(luò)的定位提供新的方法。

1 DV-Hop 定位算法

DV-Hop 定位算法起源于美國路特葛斯大學(xué)。根據(jù)已知節(jié)點跳數(shù)的平均值，與已知節(jié)點的最小跳數(shù)的乘積來預(yù)測未知節(jié)點的距離，采用三邊測量方法來獲得節(jié)點位置信息的方法[5]。DV-Hop 算法不僅可以規(guī)避信標節(jié)點數(shù)量有限的缺點，還可以獲得目標范圍外的眾多信標節(jié)點的大概距離。DV-Hop算法獲取距離是間接的，把有方向、有大小的距離信息和網(wǎng)絡(luò)的互通特性相結(jié)合，再轉(zhuǎn)變?yōu)榻凭嚯x[6]。在定位的各個環(huán)節(jié)中，每個節(jié)點都起著至關(guān)重要的作用，缺一不可。

DV-Hop 算法的定位過程分為3 個階段。

第一階段：計算未知節(jié)點與每個信標節(jié)點的最小累計量化值。

未知節(jié)點根據(jù)信標節(jié)點向其傳達的位置坐標和有關(guān)推算的程序，加上自身具有的關(guān)于坐標的片段或者演練的路徑，獲取更加精確的位置數(shù)據(jù)。

網(wǎng)絡(luò)中的每個節(jié)點要想達到完全捕捉到全部節(jié)點的最小累計的量化值，先要準確收集全部節(jié)點的最小累計量化值。對信標節(jié)點相同的一組中累計量化值相對比較大的值，可以在容錯范圍內(nèi)劃去不計，直接將有效累計量化值加上1，隨后傳送給周圍節(jié)點[7]。

第二階段：計算未知節(jié)點和信標節(jié)點的實際跳段距離。

所有的節(jié)點完成第一階段后保留了全部節(jié)點的最小累計的量化值和相關(guān)的位置數(shù)據(jù)，然后進入DV-Hop 定位算法的第二階段，使用式（1）計算未知節(jié)點和信標節(jié)點的實際跳段距離：

式中，i、j代表信標節(jié)點，坐標分別用(xi，yi)、(xj，yj)表示；hj表示的在i與j不相等的前提下，i、j之間的量化單位總數(shù)。信標節(jié)點通過用生存期字段來代表所有量化距離的平均單位距離值，然后將其傳送到系統(tǒng)中，而且未知節(jié)點只對首次接受的距離做保留，然后按照保留的距離總數(shù)和信標節(jié)點總數(shù)計算出每一個信標節(jié)點的單位距離，最后發(fā)給相鄰的節(jié)點[8]。

第三階段：計算未知節(jié)點坐標位置。

未知節(jié)點計算自身坐標是根據(jù)第二階段中接收到的所有信標節(jié)點的跳段距離，一般采用三邊測量法或極大似然估計法[9]。DV-Hop 定位算法舉例如圖1 所示。

圖1 DV-Hop 定位算法舉例

圖1 中，第一階段和第二階段后，信標節(jié)點L1、L2、L3兩兩之間的真實距離和跳數(shù)很容易得出，所以信標節(jié)點L2計算的每跳平均距離為（50+70）/（2+5）=17.14。假設(shè)A 從L2獲得平均每跳距離，則節(jié)點A 與L1、L2、L3這3 個信標節(jié)點之間的距離為3×17.14、2×17.14、3×17.14，最后A 的坐標位置就能按照三邊測量法得出結(jié)果。

2 一種改進的DV-Hop 節(jié)點自定位算法

2.1 DV-Hop 節(jié)點自定位算法的不足

DV-Hop 算法的精確度僅僅限于跳數(shù)小于2 的節(jié)點間的距離，所以當DV-Hop 算法采用乘法計算未知節(jié)點和信標節(jié)點的距離時誤差較大，精確度明顯降低。產(chǎn)生誤差的原因如圖2 所示。

圖2 未知節(jié)點與信標節(jié)點距離

圖2 中，L1代表信標節(jié)點，未知節(jié)點用A 表示，它們之間的跳數(shù)已經(jīng)處于大于等于2 的情況。圖2粗虛線表示的就是L1和A 節(jié)點之間的距離，等于跳數(shù)與每跳的平均距離（細虛線）的乘積，此處即是誤差產(chǎn)生的根本原因。

2.2 DV-Hop 節(jié)點自定位算法的改進思路

DV-Hop 算法在第一個階段時只收集到全部節(jié)點中的最小累計量化值，而改進后的算法保留自己的計算結(jié)果后發(fā)送到網(wǎng)絡(luò)中，起到一個校對的作用。發(fā)送的數(shù)據(jù)是以分組的方式進行傳播，一般格式為{di，ci}，其中ci表示信標節(jié)點i到剩下全部信標節(jié)點每跳距離的平均值。當所有節(jié)點收到數(shù)據(jù)后，會把這些分組數(shù)據(jù)保存在自己的數(shù)據(jù)表中，并且再次向相鄰的節(jié)點傳輸，而重合的分組信息將自動被刪除。重新設(shè)定的第一階段，每個節(jié)點都能參與進來，共同計算出整個網(wǎng)絡(luò)的每跳距離的平均值。計算原理：將ci即全部信標節(jié)點的平均值加權(quán)平均，得到整個網(wǎng)絡(luò)的平均每跳距離為：

然后，未知節(jié)點可以得出自身到每個信標節(jié)點的大概距離為：

第三階段未知節(jié)點如能利用最大似然估計法預(yù)估自身的大致坐標，當未知節(jié)點收到至少3 個信標節(jié)點的位置信息后，就能計算得到自己的位置信息。

根據(jù)以上分析，提出進一步的改進思路：利用全網(wǎng)平均每跳距離c代替最近信標節(jié)點的平均每跳距離ci；無論是未知節(jié)點間還是信標節(jié)點間得出的距離，都更能代表它們之間的實際距離，使之后的計算結(jié)果更加準確。要想提高全網(wǎng)平均每跳距離c，需從根源上找解決的辦法。首先，要想辦法減小各個信標節(jié)點之間的距離誤差，盡可能接近真實的距離，這樣計算出的全網(wǎng)平均每跳距離c才更有代表性，進而提高最終位置信息的精確度。

將信標節(jié)點i的平均每跳距離誤差定義為：

其中：節(jié)點j為信標節(jié)點i數(shù)據(jù)表中的其他信標節(jié)點；hopsij代表信標節(jié)點i、j之間的跳數(shù)；ni為信標節(jié)點i數(shù)據(jù)表中其他信標節(jié)點總數(shù)；|dtrue-dset|ij表示信標節(jié)點i、j之間實際距離與計算距離之差的絕對值，其中：

因此，提出一種改進的DV-Hop 定位算法，具體描述如下。

（1）平均每跳的距離改進。在改進算法中，全網(wǎng)平均每跳的距離經(jīng)過兩個階段就能得到，后續(xù)各個信標節(jié)點利用式（4）就能得出各自的平均每跳距離誤差，然后各個坐標節(jié)點會把自身的平均每跳距離誤差進行分組后發(fā)送到網(wǎng)絡(luò)中，即改進的算法中添加的第三個數(shù)據(jù)分組廣播階段。以{idi，diseri}的數(shù)據(jù)分組方式進行，diseri代表信標節(jié)點i與剩下信標節(jié)點之間的平均每跳距離誤差。各個接收到分組的數(shù)據(jù)信息后會自動添加到數(shù)據(jù)表中，并且發(fā)送給相鄰的節(jié)點。對于分組信息中重合的idi號，節(jié)點會自動刪除。這樣的處理無論是信標節(jié)點還是未知節(jié)點，都能知道全部信標節(jié)點計算的平均每跳距離誤差，最后再進行整個網(wǎng)絡(luò)的平均每跳距離誤差的計算，即把信標節(jié)點得到的所有平均每跳距離誤差相加取平均，即：

其中：n為網(wǎng)絡(luò)中的信標節(jié)點總數(shù)。通過該新增加的階段，每個未知節(jié)點得到整個網(wǎng)絡(luò)的平均每跳距離誤差。由于已經(jīng)在第二個數(shù)據(jù)分組廣播階段后得到了整個網(wǎng)絡(luò)的平均每跳距離c，修正得到新的網(wǎng)絡(luò)平均每跳距離為：

其中：k為變量參數(shù)，-1 ≤k≤l，k的取值隨具體的網(wǎng)絡(luò)環(huán)境而定，k值的大小影響著定位精度。這樣未知節(jié)點就可以得出自身到每個信標節(jié)點的大概距離為：

第三階段未知節(jié)點利用最大似然估計法或者三邊定位法得到自己的大致坐標，所以當未知節(jié)點收到至少3 個信標節(jié)點的位置信息后，就能計算得到自己的位置信息。

（2）網(wǎng)絡(luò)區(qū)域的上下界限判斷。對網(wǎng)絡(luò)來說，雖然網(wǎng)絡(luò)區(qū)域的大小無法衡量，但能大致判斷網(wǎng)絡(luò)區(qū)域的上下界限：

其中xarea為網(wǎng)絡(luò)區(qū)域在x軸上的分量，yarea為網(wǎng)絡(luò)區(qū)域在y軸上的分量

改進之后的算法減小了整個網(wǎng)絡(luò)中的平均定位誤差，只要針對出現(xiàn)偏差的未知節(jié)點的位置信息進行改正，就能從根本上解決整個網(wǎng)絡(luò)中誤差問題的出現(xiàn)。

3 仿真實驗結(jié)果與分析

如圖3 所示，假設(shè)在通信半徑為30 m、100 m×100 m 的范圍里隨意分布200 個傳感器節(jié)點，其中有20 個信標節(jié)點，其中*表示信標節(jié)點，·表示未知節(jié)點。用傳統(tǒng)的DV-Hop 定位算法得到每一個未知節(jié)點的坐標，再根據(jù)實際的位置坐標計算出未知節(jié)點的定位誤差。

圖3 傳感器節(jié)點分布

如圖4 所示，將所有的定位誤差相加求和，再除以未知節(jié)點總數(shù)得到平均定位誤差為10.072 9，平均定位誤差除以通信半徑30 m 得到定位精確度為33.58%。從定位誤差和定位精度看出，用傳統(tǒng)的DV-Hop 算法計算得到的定位誤差和定位精確度都不是很好，因此這種算法只能應(yīng)用在對精度要求不高的地區(qū)。

圖4 各個未知節(jié)點的定位誤差

3.1 DV-Hop 定位算法的影響因素

傳統(tǒng)的DV-Hop 算法得到的定位誤差和定位精度都很高，下面進行原因探究。

首先探究定位誤差和定位精度是不是受到通信半徑的影響。同樣模擬在100 m×100 m 的范圍里雜亂分布200 個傳感器節(jié)點，當中信標節(jié)點的個數(shù)還是20 個時，現(xiàn)在只改變節(jié)點的通信半徑，分別取值為25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m 和65 m，通過仿真計算得出結(jié)果如圖5 和圖6所示。

圖5 節(jié)點通信半徑與定位誤差的關(guān)系

圖6 節(jié)點通信半徑與定位精確度的關(guān)系

從圖5 能夠得到，隨著通信半徑的增大，定位誤差隨之增大。從圖6 能夠知道，通信半徑減小，定位精確度也在減小。可見，通信半徑對這兩者的影響是相反的。有時候?qū)σ粋€通信半徑雖然定位誤差較小，但是定位精確度卻很大；有時候定位精確度較小，但是定位誤差很大。因此，一味提高或者減小通信半徑是不可行的，需找到一個效益最好的平衡點。

3.2 改進的DV-Hop 定位算法仿真結(jié)果與分析

改進的DV-Hop 定位算法，模擬在相同條件下觀察參數(shù)k值對定位精確度的影響。對100 m×100 m、無規(guī)律分布200 個傳感器節(jié)點，20 個信標節(jié)點個數(shù)，35 m 的通信半徑，增加參數(shù)k（取值為-1 到1，間隔為0.1），通過仿真觀察k值對定位精確度的影響，結(jié)果如圖7 所示。

圖7 參數(shù)k 對定位精確度的影響

從圖7 能夠得到，除了k值變化、其他條件都不變情況下，定位精確度在-1～0.6 范圍內(nèi)隨著k值的增加不斷下降；在0.6～1 范圍內(nèi)，定位精確度隨著k值的增加而增加。因此，當k值為0.6 時，定位精確度最低，也就是最精確的時候。

隨后模擬在不同條件下觀察參數(shù)k的值對定位精確度的影響。保持基本仿真環(huán)境不變，只改變節(jié)點總數(shù)和信標節(jié)點的個數(shù)。第1 種：在節(jié)點總數(shù)為100，信標節(jié)點數(shù)為10；第2 種：節(jié)點總數(shù)為200，信標節(jié)點數(shù)為50；第3 種：節(jié)點總數(shù)為300，信標節(jié)點數(shù)為80。參數(shù)k從-1 到1，間隔為0.1，仿真結(jié)果如圖8 所示。

圖8 在不同的網(wǎng)絡(luò)環(huán)境下參數(shù)k 對定位精確度的影響

從圖8 可以得到：當k從0.1～0.7 時，3 種狀況下的定位精度都在0.3 以下都有最佳值。第1 種情況下，當k值為0.4 時，定位精確度最低；第2種情況下，當k值為0.6 時，定位精確度最低；第3 種情況下，當k值為0.7 時，定位精確度最低。

3.3 DV-Hop 定位算法與改進算法的對比分析

分別對傳統(tǒng)算法和改進算法進行仿真和分析，在100 m×100 m 的范圍里無規(guī)律放置200 個傳感器，20 個節(jié)點是信標節(jié)點，通信半徑是20 m。同時，將信標節(jié)點個數(shù)除以節(jié)點總數(shù)減去信標節(jié)點個數(shù)的差值作為k的值。用傳統(tǒng)DV-Hop 定位算法和改進的DV-Hop 定位算法對未知節(jié)點進行定位，然后比較兩者定位誤差和定位精確度，仿真結(jié)果如圖9、圖10 所示。

圖9 平均定位誤差對比

圖10 平均定位誤差的對比

從圖9 可知，傳統(tǒng)DV-Hop 算法的定位誤差比改進算法大很多，因此就定位誤差來說，改進算法占很大優(yōu)勢。

從圖10 可知，傳統(tǒng)DV-Hop 算法的定位精確度比改進算法高出很多，即改進算法定位比較精確。因此，就定位精確度來說，改進算法占很大優(yōu)勢。

綜上所述，改進的DV-Hop 算法大大減小了定位誤差，提高了定位精度，改善了傳統(tǒng)DV-Hop 算法的不足。

4 結(jié)語

節(jié)點定位算法是無線傳感器網(wǎng)絡(luò)中研究的一個熱點。在介紹DV-Hop 算法的基礎(chǔ)上，分析該算法存在的不足提出改進的對策，通過減小全網(wǎng)平均每跳距離與真實的平均每跳距離間的差距，對不在網(wǎng)絡(luò)區(qū)域的未知節(jié)點的坐標進行重新修訂。實驗分析表明，改進算法的精確度明顯高于DV-Hop 算法，且減小了定位誤差，具有很高的可用性，為無線傳感器網(wǎng)絡(luò)的定位提供了可行的方法。