基于DV-Hop的大規(guī)模WSN定位方法研究

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2024）03-00-04

0 引 言

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

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

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

1 DV-Hop算法概述

1.1 算法原理

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

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

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

（1）

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

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

1.2 算法的不足

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

（1）定位精度受到節(jié)點(diǎn)部署密度和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響。當(dāng)節(jié)點(diǎn)部署密度不足或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較為復(fù)雜時(shí)，DV-Hop算法的定位精度會(huì)受到較大的影響。

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

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

2 DV-Hop定位算法的改進(jìn)

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

2.1 改進(jìn)平均跳距

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

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

式（2）所示：

（2）

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

（3）

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

（4）

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

2.2 改進(jìn)最小跳數(shù)

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

（5）

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

（6）

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

（7）

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

（8）

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

（9）

2.3 算法流程

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

3 仿真實(shí)驗(yàn)與性能分析

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

3.1 仿真環(huán)境

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

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

（10）

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

3.2 仿真結(jié)果

3.2.1 只改進(jìn)平均跳距

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

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

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

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

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

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

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

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

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

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

3.2.5 不同信標(biāo)節(jié)點(diǎn)比例對定位誤差的影響

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

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

4 結(jié) 語

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

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

參考文獻(xiàn)

[1]王慧.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的研究與改進(jìn)[D].南京：南京郵電大學(xué)，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ìn)[J].火控雷達(dá)技術(shù)，2021，50（1）：20-25.

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

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

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

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

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

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

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