摘 要：DV-Hop是大規(guī)模無線傳感器網(wǎng)絡（WSN）典型定位算法，通過測量節(jié)點之間的信號傳輸距離和經(jīng)過的中繼節(jié)點數(shù)，實現(xiàn)節(jié)點的位置估計。針對傳統(tǒng)DV-Hop算法中存在的平均跳距誤差較大和最小跳數(shù)難以確定等問題，通過引入加權(quán)平均跳距和基于節(jié)點分布的最小跳數(shù)，改進了傳統(tǒng)DV-Hop算法。仿真結(jié)果表明，改進的DV-Hop算法在提高定位精度方面優(yōu)于傳統(tǒng)DV-Hop算法。

關(guān)鍵詞：無線傳感器網(wǎng)絡；節(jié)點定位；DV-Hop；平均跳距；最小跳數(shù)；定位誤差

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2024）03-00-04

0 引 言

隨著傳感器技術(shù)的快速發(fā)展，無線傳感器網(wǎng)絡已經(jīng)廣泛應用于農(nóng)業(yè)數(shù)據(jù)采集、工業(yè)控制、森林火災控制和醫(yī)療等領(lǐng)域[1]。在無線傳感器網(wǎng)絡中，節(jié)點的位置信息對于網(wǎng)絡性能和應用效果具有至關(guān)重要的作用。因此，無線傳感器網(wǎng)絡的定位問題一直是研究熱點之一。

目前，無線傳感器網(wǎng)絡定位算法主要分為基于距離測量和無需距離測量兩類。基于距離測量的算法主要包括接收信號強度（RSSI）、到達時間（TOA）、到達時差（TDOA）和到達角測量（AOA）。無需距離測量的算法主要包括質(zhì)心定位算法（CL）、凸規(guī)劃方法、近似三角形內(nèi)點算法（APIT）、網(wǎng)絡多跳路由算法（DV-Hop）等[2]。其中DV-Hop算法是一種典型的基于節(jié)點距離的定位算法，其利用節(jié)點間的跳數(shù)和跳距信息進行節(jié)點的定位。因其簡單易實現(xiàn)、適用于大規(guī)模網(wǎng)絡和低成本等優(yōu)點，被廣泛應用于無線傳感器網(wǎng)絡中。因此有許多國內(nèi)外學者對DV-Hop算法進行研究與改進。文獻[3]提出了一種細化半徑的節(jié)點通信思路，進而細化最小跳數(shù)值，大幅降低了傳感器的定位誤差。文獻[4]利用改進鯨魚優(yōu)化算法替代最小二乘法求未知節(jié)點坐標，以提高定位精度。文獻[5]提出了一種質(zhì)心和DV-Hop混合定位算法MCDA，通過設(shè)置TTL值來限制信標節(jié)點廣播數(shù)據(jù)的范圍以及提高鄰居信標節(jié)點的比例來改進質(zhì)心定位算法。

然而，傳統(tǒng)的DV-Hop算法存在平均跳距誤差較大和最小跳數(shù)難以確定等問題，這些問題嚴重影響了算法的定位精度和魯棒性。因此本文針對傳統(tǒng)DV-Hop算法存在的問題，提出了改進的DV-Hop算法。該算法通過引入加權(quán)平均跳距和基于節(jié)點分布的最小跳數(shù)，能夠有效地提高定位精度和魯棒性[6]。

1 DV-Hop算法概述

1.1 算法原理

DV-Hop算法是由Niculescu提出的一種定位方法，是一種基于跳數(shù)的無線傳感器網(wǎng)絡定位算法，其基本思想是通過節(jié)點之間的跳數(shù)關(guān)系來計算節(jié)點之間的距離，從而實現(xiàn)節(jié)點的定位。具體來說，DV-Hop算法分為三個階段，分別是跳數(shù)計算階段、距離計算階段和未知節(jié)點計算階段[7]。

（1）跳數(shù)計算階段：信標節(jié)點An通過網(wǎng)絡廣播包含An位置和跳數(shù)字段hn初始值0的消息。節(jié)點記錄跳數(shù)計數(shù)值表示未知節(jié)點u和An之間的最小跳數(shù)hun。重復接收到消息時，節(jié)點更新跳數(shù)計數(shù)值，停止信息獲取。該機制使得所有節(jié)點都能獲得每個信標節(jié)點中的最小跳數(shù)。

（2）距離計算階段：根據(jù)在跳數(shù)計算階段得到的每個信標節(jié)點的最小跳數(shù)計算每個跳躍的平均實際距離，如式（1）所示：

（1）

式中：HSizen表示信標節(jié)點An的平均跳距；（xn， yn）、（xm， ym）是信標節(jié)點An、Am的坐標；hnm是兩個信標節(jié)點n與m（n≠m）之間的最小跳數(shù)。該算法保證了大部分的未知節(jié)點都能得到最近的信標節(jié)點之間的平均距離。

（3）未知節(jié)點計算階段：通過三方測量或最大似然估計方法，對每個信標節(jié)點采用距離計算階段的固定間隔計算其坐標。

1.2 算法的不足

雖然傳統(tǒng)DV-Hop算法具有一定的定位精度和可靠性，但其也存在一些局限性。主要包括以下幾點：

（1）定位精度受到節(jié)點部署密度和網(wǎng)絡拓撲結(jié)構(gòu)的影響。當節(jié)點部署密度不足或網(wǎng)絡拓撲結(jié)構(gòu)較為復雜時，DV-Hop算法的定位精度會受到較大的影響。

（2）DV-Hop算法的準確度受到節(jié)點測距誤差的影響。在實際應用中，由于環(huán)境干擾等因素的存在，節(jié)點之間的跳距測量誤差較大，從而影響了DV-Hop算法的準確度。

（3）算法的計算復雜度較高。由于DV-Hop算法需要計算每個節(jié)點到已知節(jié)點的跳數(shù)和跳距信息，因此其計算復雜度較高，對于大規(guī)模的無線傳感器網(wǎng)絡，計算時間較長，從而影響了算法的實用性。

2 DV-Hop定位算法的改進

針對DV-Hop算法的不足，為了進一步提高DV-Hop算法的定位精度，本文主要從兩個方面進行改進：基于加權(quán)平均跳距和基于節(jié)點分布的最小跳數(shù)。

2.1 改進平均跳距

加權(quán)平均跳距的改進是針對DV-Hop算法中平均跳距的問題而提出的。在DV-Hop算法中，平均跳距的計算沒有考慮到節(jié)點之間跳數(shù)關(guān)系的不同，導致了節(jié)點的平均跳距具有一定的偏差，從而影響了定位精度。因此，本文研究了一種加權(quán)平均跳距的改進方法，通過對節(jié)點之間跳數(shù)關(guān)系進行加權(quán)，以降低平均跳距求值中造成的誤差，優(yōu)化節(jié)點之間的距離估計。

如圖1所示，實心圓u表示未知節(jié)點，空心圓表示信標節(jié)點。在傳感器網(wǎng)絡中，假設(shè)信標節(jié)點An與信標節(jié)點Am之間的最小跳數(shù)為hnm，信標節(jié)點An的平均跳距為HSizen，這樣可以求得信標節(jié)點An與信標節(jié)點Am之間的理論距離如

式（2）所示：

（2）

在計算信標節(jié)點An的平均跳距時，考慮信標節(jié)點的真實距離和估計距離之間的誤差，實際平均跳距也可能與估計值略有偏差，其誤差εn如式（3）所示：

（3）

式中，εn表示信標節(jié)點An的平均跳距誤差。求得誤差值后就可以利用對誤差εn的優(yōu)化來達到對信標節(jié)點An的平均跳距進行優(yōu)化的目的，如式（4）所示：

（4）

式中，DHSizen為修正之后的信標節(jié)點An的平均跳距[8]。

2.2 改進最小跳數(shù)

基于節(jié)點分布的最小跳數(shù)的改進是針對DV-Hop算法中基于平均跳距的最小跳數(shù)問題而提出的。在DV-Hop算法中，由于節(jié)點的分布不均勻，可能會存在距離相近但跳數(shù)較大的節(jié)點，從而影響距離估計的精度。因此，本文提出了一種基于節(jié)點分布的最小跳數(shù)的改進方法。通過考慮節(jié)點分布的情況，尋找距離最近且分布相近的鄰居節(jié)點，進一步優(yōu)化節(jié)點之間的距離估計，進而根據(jù)信標節(jié)點之間的實際距離，對最小跳躍次數(shù)進行修正，也就是理論上的信標節(jié)點Ai的跳躍次數(shù)hμnm，如式（5）所示：

（5）

信標節(jié)點之間估算跳數(shù)和實際跳數(shù)之間存在較大差異，為了解決這一問題，可以定義一個差異系數(shù)θn，用于計算未知節(jié)點到信標節(jié)點的最小跳數(shù)，如式（6）所示：

（6）

通過差異系數(shù)可以直觀體現(xiàn)出實際跳數(shù)hnm和理論跳數(shù)hμnm之間的偏差。差異系數(shù)越大，則說明兩者之間存在的偏差越大，于是，可以定義一個優(yōu)化系數(shù)wn，用于減少誤差以優(yōu)化節(jié)點之間的最小跳數(shù)，如式（7）所示：

（7）

式中，wn代表信標節(jié)點An的優(yōu)化系數(shù)。利用所定義的系數(shù)wn來優(yōu)化未知節(jié)點u到信標節(jié)點An的最小跳數(shù)hunmin，如式（8）所示：

（8）

式中，hun為未知節(jié)點u到信標節(jié)點An的實際最小跳數(shù)。通過建立權(quán)重系數(shù)來優(yōu)化未知節(jié)點到信標節(jié)點的距離位置，并可以根據(jù)最小跳數(shù)和平均跳距求出在未知節(jié)點u到信標節(jié)點An的距離dun，如式（9）所示[9]：

（9）

2.3 算法流程

通過基于加權(quán)平均跳距和節(jié)點分布的最小跳數(shù)的改進，可以有效減小節(jié)點之間距離估計的誤差，提高定位精度。其算法流程如圖2所示。

3 仿真實驗與性能分析

為驗證改進的DV-Hop算法的性能，本文在MATLAB平臺上進行了一系列仿真實驗，并與傳統(tǒng)DV-Hop算法進行比較。

3.1 仿真環(huán)境

仿真中使用的無線傳感器網(wǎng)絡由100個隨機部署的節(jié)點組成，節(jié)點部署范圍為100×100的矩形區(qū)域，其中有8個信標節(jié)點，節(jié)點通信半徑值選取50 m，節(jié)點部署如圖3所示。

為了驗證該算法的性能，引入平均定位誤差Error如式（10）所示，主要是通過定位誤差進行分析，運行10次取平均值[10]。

（10）

式中：（xt， yt）是信標節(jié)點An的計算坐標值；（xn， yn）是信標節(jié)點An的真實坐標值；N為信標節(jié)點數(shù)量；K為節(jié)點總數(shù)；R為通信半徑。

3.2 仿真結(jié)果

3.2.1 只改進平均跳距

理論距離為數(shù)學估計距離，不可能百分之百等同于實際距離，所以有必要對算法進行軟件仿真，繪出測距誤差圖，以展示算法的精確性。測距誤差是指未知節(jié)點間的理論距離和實際距離的相差值。

如圖4所示，我們繪制了改進傳統(tǒng)算法平均跳距的測距誤差仿真圖。實驗結(jié)果表明，算法能夠準確地估算未知節(jié)點的位置，其中最大誤差為57.75 m，最小誤差為2.27 m，平均誤差為21.75 m。

3.2.2 只改進最小跳數(shù)

如圖5所示，我們在其他條件相同的情況下進行了只改進傳統(tǒng)算法最小跳數(shù)的誤差仿真。實驗結(jié)果表明，該算法能夠準確地估算未知節(jié)點的位置，其中最大誤差為57.75 m，最小誤差為2.96 m，平均誤差為21.83 m。

3.2.3 同時改進平均跳距和最小跳數(shù)

如圖6所示為在其他條件都相同的情況下，對傳統(tǒng)算法的平均跳距和最小跳數(shù)都進行優(yōu)化后的誤差仿真圖。從實驗結(jié)果中可知，算法能夠準確地估算未知節(jié)點的位置，其中最大誤差為48.73 m，最小定位誤差為0.97 m，平均誤差為19.27 m。

實驗結(jié)果表明，在通信半徑為50 m、信標節(jié)點比例為8%的仿真環(huán)境中，無論是僅優(yōu)化平均跳距、僅優(yōu)化最小跳數(shù)，還是同時優(yōu)化平均跳距和最小跳數(shù)，實際位置與理想位置之間的差異都不大。這說明三種優(yōu)化算法在該仿真環(huán)境下的實際定位效果差別不大。因此，在實際應用中我們可以根據(jù)具體情況選取運行消耗低且計算相對簡單的算法。

3.2.4 不同通信半徑對定位誤差的影響

為了更全面地評估四種算法的性能，本文進行了另一組誤差仿真實驗，分別改變通信半徑和信標節(jié)點比例，選取不同參數(shù)值進行仿真并記錄實驗數(shù)據(jù)。在信標節(jié)點比例為8%的情況下，選取通信半徑的值分別為20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m進行仿真，得出平均誤差數(shù)據(jù)，并繪制誤差對比折線圖，如圖7所示。實驗結(jié)果表明，隨著通信半徑的增加，四種算法的誤差逐漸減小，但是減小的幅度逐漸趨于平穩(wěn)。在通信半徑為65 m時，部分算法的誤差略有增加，可能是由于節(jié)點隨機分布所導致的?？傮w而言，改進算法的定位性能明顯優(yōu)于傳統(tǒng)算法。

通過對比曲線圖可以直觀看出，在同一信標節(jié)點比例條件下，三種改進算法與傳統(tǒng)算法的定位誤差隨通信半徑增大而減小。三種優(yōu)化算法定位精度明顯更高，例如當通信半徑為55 m時，傳統(tǒng)算法定位精度誤差為24.73%，改進算法定位精度誤差都在20%以下。當通信半徑大于50 m時，四種算法定位誤差下降趨勢減緩，但總體來說，三種優(yōu)化算法定位性能明顯優(yōu)于傳統(tǒng)算法。

3.2.5 不同信標節(jié)點比例對定位誤差的影響

在總節(jié)點數(shù)相同的情況下，通過改變信標節(jié)點數(shù)量來控制不同的信標節(jié)點密度，以評估其對算法性能的影響。選取通信半徑為20 m不變，信標節(jié)點比例從5%到50%進行實驗，并得到平均誤差數(shù)據(jù)圖如圖8所示。實驗結(jié)果顯示，隨著信標節(jié)點比例的增加，所有算法的誤差逐漸減小，但下降速率逐漸趨于平穩(wěn)。當信標節(jié)點比例達到一定程度時，傳統(tǒng)算法和改進算法的誤差減小幅度明顯變小，趨于穩(wěn)定。只有最小跳數(shù)改進和平均跳距與最小跳數(shù)同時改進的算法在信標節(jié)點比例為50%時誤差略有增加，這可能是由于隨機分布引起的個別數(shù)據(jù)誤差較大。

通過對比曲線圖可以更加清晰地觀察到第二種關(guān)系，即在相同的通信半徑下，隨著信標節(jié)點比例的增加，三種改進算法和傳統(tǒng)算法的定位誤差都在逐漸減少。顯然，相對于傳統(tǒng)的DV-Hop方法，本文提出的三種優(yōu)化算法能夠顯著降低定位誤差，提高定位精度。在信標節(jié)點比例超過40%時，四種算法的定位誤差下降趨勢逐漸變緩，但是相較于傳統(tǒng)算法，本文提出的三種優(yōu)化算法依然表現(xiàn)出了更好的定位性能。

4 結(jié) 語

本文針對DV-Hop算法存在的問題，提出了基于加權(quán)平均跳距和節(jié)點分布的最小跳數(shù)的方法。仿真實驗研究表明，改進算法相比傳統(tǒng)的DV-Hop算法，在定位精度和計算復雜度方面均有明顯的提高，而且改進算法適用于大規(guī)模無線傳感器網(wǎng)絡的定位應用。

注：本文通訊作者為蔡立濤。

參考文獻

[1]王慧.無線傳感器網(wǎng)絡DV-Hop定位算法的研究與改進[D].南京：南京郵電大學，2020.

[2] GAYANA S，DIAS D. Improved DV-Hop algorithm through anchor position re-estimation [C]// 2014 IEEE Asia Pacific Conference on Wireless and Mobile. Bali， Indonesia：IEEE，2020：126-131.

[3]劉超，李海鵬. DV-Hop定位算法的研究與改進[J].火控雷達技術(shù)，2021，50（1）：20-25.

[4]王磊，劉晶晶，齊俊艷，等.基于測距修正及改進鯨魚優(yōu)化的DV-HOP定位算法[J].儀表技術(shù)與傳感器，2022，59（2）：116-121.

[5]張悅，梁建國，張浩，等.無線傳感器網(wǎng)絡質(zhì)心和DV-Hop混合定位算法研究[J].儀表技術(shù)與傳感器，2021，58（4）：122-126.

[6]劉芷珺，張玲華.基于鄰域搜索粒子群算法的節(jié)點定位算法研究[J].電子技術(shù)應用，2022，48（9）：97-102.

[7]周凱，周培釗，付文涵，等.無線傳感器網(wǎng)絡的改進DV-hop定位算法研究[J].東北師大學報（自然科學版），2021，53（4）：137-143.

[8]劉川洲，張玲華.基于DV-Hop算法的無線傳感器網(wǎng)絡定位精度優(yōu)化[J].激光與光電子學進展，2021，58（22）：498-504.

[9]祁祺.無線傳感器網(wǎng)絡中DV-Hop定位算法的研究與改進[D].南京：南京郵電大學，2021.

[10]何少尉.無線傳感器網(wǎng)絡中一種改進的DV-Hop定位算法研究[J].通信技術(shù)，2020，53（3）：648-653.