基于灰狼算法和極大似然估計的改進DV-HOP算法

朱曉娟 陳智麗

摘 要：DV-HOP算法是無線傳感器網(wǎng)絡(luò)中一種常見的基于非測距的定位技術(shù)，該算法使用平均跳距表示實際距離，在實際應(yīng)用中造成很大的誤差和節(jié)點能耗。為此，在原有DV-HOP算法的基礎(chǔ)上，引入了灰狼算法細化節(jié)點之間的跳數(shù)，用極大似然估計法修正實際坐標(biāo)與估計坐標(biāo)之間的誤差。仿真結(jié)果表明，改進算法在不顯著提高算法復(fù)雜度的基礎(chǔ)上提高了一定的定位精度。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);DV-HOP算法;灰狼算法;極大似然估計;誤差分析;平均跳躍距離

中圖分類號：TP39 文獻標(biāo)識碼：A 文章編號：2095-1302（2020）05-00-05

0 引 言

隨著無線網(wǎng)絡(luò)的高速發(fā)展，無線定位技術(shù)受到了業(yè)界的廣泛關(guān)注，已經(jīng)在智能農(nóng)業(yè)[1]、目標(biāo)跟蹤[2]、水質(zhì)監(jiān)測[3]、遠程醫(yī)療[4]等領(lǐng)域得到不斷發(fā)展。在無線傳感器網(wǎng)絡(luò)的大多數(shù)應(yīng)用中，沒有位置信息的任何事件信息都是毫無意義的。例如，在火災(zāi)探測應(yīng)用程序中，需要事件（火災(zāi)）和探測火災(zāi)的地點（位置）。因此，精準(zhǔn)定位是無線傳感器網(wǎng)絡(luò)的要求。

定位的基本方法分為距離式定位和非距離式定位。距離式定位[5]是通過測量距離或角度進行位置估計，測量數(shù)據(jù)的精度對定位精度有很大影響，常見的基于距離的定位算法有RSSI，AOA，TOA，TDOA[6]等。非距離式定位[5]是通過節(jié)點間的HOP數(shù)或估計距離計算節(jié)點的坐標(biāo)，這種方法無需測量距離或角度，利用估計距離代替真實距離，常見的非距離式定位算法有CL，DV-HOP，APIT等。其中，DV-HOP算法不僅開銷低，還可以處理普通節(jié)點少于3個相鄰錨點的情況。國內(nèi)外許多學(xué)者對DV-HOP算法提出了改進，使得定位精度大大提高。例如，AMANPREET KAUR提出了一種加權(quán)質(zhì)心DV-HOP算法[7]，該算法考慮不同因素（如錨數(shù)、通信半徑和最近錨）影響的權(quán)重來確定未知節(jié)點的位置。Guangshun Li對傳統(tǒng)的DV-HOP算法[8]提出了兩方面的改進：對平均每條跳距進行修正;分別采用加權(quán)質(zhì)心定位算法和加權(quán)最小二乘法分別得到一個估計位置，并由2個估計位置的算術(shù)均值確定最終位置。XUE Dalong提出了一種基于跳變細化和距離校正的改進型DV-HOP算法[9]。通過引入接收信號強度指示（RSSI）測距技術(shù)來校正最小跳，通過跳躍距離誤差和估計距離誤差的加權(quán)平均值對平均跳躍距離進行校正。LIU Guiqi等人[10]提出了一種基于跳的校正平均大小改進的DV-HOP定位算法，改進的算法根據(jù)跳數(shù)信息和錨節(jié)點信息的相對準(zhǔn)確的坐標(biāo)來校正未知節(jié)點與不同錨節(jié)點之間的估計距離，并使用改進的差分進化算法獲得未知節(jié)點的估計位置。本文提出了一種基于多通道半徑和極大似然估計的改進DV-HOP算法，在原有DV-HOP算法的基礎(chǔ)上，引入了多通道半徑廣播細化節(jié)點之間的跳數(shù)，用極大似然估計法修正實際坐標(biāo)與估計坐標(biāo)之間的誤差。仿真結(jié)果表明，相比較傳統(tǒng)的DV-HOP算法，本文算法在定位精度上有一定提高。

1 DV-HOP算法與誤差分析

1.1 傳統(tǒng)的DV-HOP算法

DV-HOP（Distance Vector-Hop）算法是由美國Rutgers University的Dragons等人提出的。該算法使用路由交換協(xié)議使未知節(jié)點獲得錨節(jié)點信息，并用于計算其自身坐標(biāo)。DV-HOP算法主要由三個階段組成[7]。

（1）獲取錨節(jié)點和未知節(jié)點的跳數(shù)信息

通過可控的泛洪算法，網(wǎng)絡(luò)中的錨節(jié)點將其位置數(shù)據(jù)包廣播到整個網(wǎng)絡(luò)。接收到來自錨節(jié)點的信息后，鄰居節(jié)點會將數(shù)據(jù)包中的躍點值增加一跳，然后將其轉(zhuǎn)發(fā)到下一個鄰居節(jié)點。接收節(jié)點只保留來自同一錨節(jié)點的最小跳數(shù)信息，忽略較大跳數(shù)的信息包。泛洪后，所有節(jié)點將獲得每個錨節(jié)點的最小路徑和跳值。

（2）計算錨節(jié)點之間的平均跳躍距離

令錨節(jié)點i與其他錨節(jié)點j之間的平均跳距為AvgHopdistance。通過公式（1）估算自身平均跳距：

式中：m是給定網(wǎng)絡(luò)中的錨的總數(shù);i是每個錨的id;（xi， yi）和（xj， yj）分別為錨節(jié)點i和錨節(jié)點j的坐標(biāo);hji是錨節(jié)點i和錨節(jié)點j之間的最小跳數(shù)。

每個未知節(jié)點u使用式（2）計算距錨節(jié)點i的近似距離。其中，hui是錨節(jié)點i和未知節(jié)點u之間的最小跳數(shù)。

（3）確定未知節(jié)點的坐標(biāo)

當(dāng)獲得未知節(jié)點與三個或者更多錨節(jié)點之間的距離時，可以用最小二乘法來求解自身坐標(biāo)。

利用未知節(jié)點u和錨節(jié)點i的坐標(biāo)（xu， yu）和（xi， xj）可以得到方程（3）：

化簡后可得方程（4）：

方程（4）可寫成Ax=B的形式：

由此可得未知節(jié)點u的坐標(biāo)為Xu=（ATA）-1ATB

1.2 DV-HOP算法的誤差分析

在實際應(yīng)用中，由于信標(biāo)節(jié)點的成本較高，所以并不會大面積部署。此外，實際布置節(jié)點是隨機的，無法保證分布的合理性。所以，DV-HOP算法在實際應(yīng)用中精度必定存在一定誤差。

由于在實際應(yīng)用中，節(jié)點隨機且不均勻地部署在給定監(jiān)視區(qū)域中。因此，對于錨節(jié)點而言，其通信半徑中存在許多未知節(jié)點，并且未知節(jié)點與錨節(jié)點之間的距離并不完全相等。但是DV-HOP算法在計算它們之間的距離時，獲得的結(jié)果一致。

在DV-HOP算法中，用信標(biāo)節(jié)點的跳數(shù)乘以平均每跳的距離來表示節(jié)點之間的距離，這種估算方法可能會存在較大誤差。例如圖1所示的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

圖1中，A1，A2，A3為信標(biāo)節(jié)點，其余的為未知節(jié)點。A1，A2之間的距離為20 m，A2，A3之間的距離為40 m，由式（1）可得AvgHopDistance =7.5。然而由于各節(jié)點之間的距離不同，所以計算出來的平均每跳距離與實際相比存在誤差，跳數(shù)越多，累計誤差越大。

2 算法的改進

2.1 標(biāo)準(zhǔn)灰狼優(yōu)化算法

GWO算法由Mirjalili等人提出，它是受到灰狼狩獵機制啟發(fā)而出現(xiàn)的一種元啟發(fā)式優(yōu)化技術(shù)，該算法簡單、靈活。文獻[12]與其他知名的優(yōu)化算法進行了28種基準(zhǔn)測試功能的比較，證明了GWO優(yōu)于其他元啟發(fā)式優(yōu)化算法。

灰狼主要為群居方式生活，并且等級制度嚴明。灰狼一般分成四類：頭狼稱為α，它是領(lǐng)導(dǎo)者，主要負責(zé)群體中的各項事務(wù)，包括選擇追逐、休息的地點，喚醒時間等;略次于α的稱為β，它作為α的下屬，負責(zé)輔助α對群體進行管理決策;次于β的稱為σ，它聽從α和β的指令，但能指揮更底層的個體，負責(zé)執(zhí)行偵查、看護、放哨等任務(wù)，年邁的α和β也會降為σ;最底層的稱為ω，它們主要負責(zé)捕獵[13]。

在GWO算法中，α，β和σ分別表示為最優(yōu)解、次優(yōu)解和第三最優(yōu)解，其他個體為ω，獵物的最終位置即為所求未知節(jié)點的位置。

灰狼群接近獵物行為的數(shù)學(xué)模型分為種群初始化、種群搜索和種群位置更新三個過程。

2.1.1 種群初始化

該算法在運行之初需要將搜索個體分布到搜索區(qū)域中，采取隨機布設(shè)方式，即：

式中：x為灰狼個體，i∈[1， 2， ...， N]，j∈[1， 2， ...， D];N是灰狼個體數(shù)量;D是種群的維數(shù);lb和ub構(gòu)成搜索區(qū)間的邊界;R是隨機分布函數(shù)。

2.1.2 種群搜索

灰狼個體與獵物之間的距離通過式（7）確定，灰狼個體按照公式（8）接近獵物：

式中：D為獵物與灰狼之間的距離;C和A為系數(shù);Xp和X為獵物位置和個體位置。

系數(shù)C和A的計算公式如下：

式中：r1和r2是[0，1]之間任意一個數(shù)字;t為當(dāng)前迭代次數(shù);tmax為最大迭代次數(shù)。

2.1.3 種群位置信息計算

當(dāng)狼群發(fā)現(xiàn)獵物后，假設(shè)α，β和σ為更好地了解獵物，提出下列公式以獲取獵物的信息。通過式（12）、式（13）計算出個體與α，β和σ的距離，再由式（14）計算出獵物移動的方向：

2.2 灰狼算法修正平均跳數(shù)

在經(jīng)典的DV-HOP第二階段，信標(biāo)節(jié)點通過應(yīng)用式（1）計算平均跳距，然后應(yīng)用式（3）計算它們與每個信標(biāo)的距離。此后，信標(biāo)使用灰狼算法細化平均跳距。式（15）為用于實現(xiàn)最佳平均跳躍距離的適應(yīng)度函數(shù)：

此階段可幫助所有信標(biāo)獲得精確的平均跳數(shù)。所有平均跳數(shù)都會廣播給網(wǎng)絡(luò)中的其他節(jié)點，然后再通過取最接近信標(biāo)到給定節(jié)點的平均跳數(shù)與最小跳數(shù)的乘積來得出每個信標(biāo)的距離。使用灰狼算法通過每個信標(biāo)獲得最佳平均跳數(shù)的步驟：

初始化隨機數(shù)a，A，C，根據(jù)式（16）尋找目標(biāo)fobj，fobβ，fobσ，設(shè)置Xα，Xβ，Xσ的初始最佳估計，在該算法中，Xα被設(shè)定為由給定信標(biāo)計算的平均跳數(shù)，Xβ和Xσ被設(shè)定為所有信標(biāo)計算的平均跳數(shù)。算法如下：

初始化i=1

do

for 每一個節(jié)點用式（15）更新其平均跳數(shù)

end for

更新a，A，C的值，再次決定目標(biāo)函數(shù)fobj1

If fobj1

用新值更新Xα且fobjβ=fobj1

else

if fobj1>fobj and fobj1

用新值更新Xβ且fobjβ=fobj1

end if

else

if fobj1>fobj and fobj>fobjβ and fobj1

用新值更新Xσ且fobjσ=fobj1

End if

else

清空fobj1的值，保持先前的fobj

end if

用式（13）更新Xα，Xβ和Xσ

I=i+1

end for

得到Xα，Xβ，Xσ的質(zhì)心，返回最優(yōu)平均跳數(shù)

2.3 極大似然估計法修正坐標(biāo)

在式（4）的求解過程中，用每個方程與最后一個方程作差得到修正值。雖然使方程更加簡潔明了，但是相減還是會丟失一部分信息，從而導(dǎo)致計算誤差。為了減少計算誤差，可以對方程進行泰勒公式展開。對于式（3），令

偏差量（Δx， Δy）表示實際位置（x， y）與估計位置? 的差值，即，所以式（17）可改寫成：

f （x， y） 在? 處的泰勒展開為：

將式（19）中一階偏導(dǎo)之后的展開項省略，以避免式中非線性項的干擾。對f （x， y）在? 求一階偏導(dǎo)為：

式（19）可以表示為：

令

則式（22）可以表示為，即：

令

所以方程組可表示為AX=B，根據(jù)最小二乘式可得到X=（ATA）-1ATB。然后可得未知節(jié)點的坐標(biāo)，偏差量（Δx， Δy） 的值決定了定位的精度。

3 實驗仿真驗證

3.1 仿真環(huán)境

為了驗證改進后算法的精確性，采用Matlab 2018a進行仿真。仿真環(huán)境為100 m×100 m的正方形區(qū)域，區(qū)域中隨機分布有100個節(jié)點。在錨節(jié)點數(shù)相同的情況下，進行多次實驗取平均值。本文選取未知節(jié)點平均相對定位誤差作為評價指標(biāo)，表示為：

式中：N為節(jié)點總數(shù);n為信標(biāo)節(jié)點數(shù);R為節(jié)點的通信半徑;（xi， yi）和（Xi， Yi）分別為未知節(jié)點i的估計坐標(biāo)和真實坐標(biāo)。

仿真參數(shù)見表1所列。

節(jié)點隨機分布如圖2所示。

3.2 仿真結(jié)果分析

3.2.1 節(jié)點總數(shù)對定位性能的影響

當(dāng)通信半徑為30 m，信標(biāo)節(jié)點比例保持在30%時，調(diào)整節(jié)點總數(shù)進行仿真。如圖3所示，隨著節(jié)點總數(shù)的增加，進行測試的3個算法的平均誤差都在逐漸降低。這是因為隨著總節(jié)點的增加，節(jié)點之間的密度增大，從而降低了節(jié)點之間的距離，使得跳數(shù)和平均跳距估計更加準(zhǔn)確。由圖可知，本文算法的平均誤差較小。

3.2.2 通信半徑對定位性能的影響

通信半徑的大小決定了未知節(jié)點可以獲得的信標(biāo)節(jié)點的數(shù)量。圖4表示節(jié)點總數(shù)為100，信標(biāo)節(jié)點為10個，通信半徑由20 m變化為40 m時經(jīng)典DV-HOP算法、文獻[7]的算法、文獻[8]的算法以及本文改進算法的平均定位誤差仿真圖。由圖3的仿真結(jié)果可以看出，通信半徑的增大有效降低了節(jié)點的相對平均誤差，本文提出的改進算法相較于比對算法，平均相對誤差有一定的降低。但是通信半徑并非越大越好，通信半徑越大能耗就越多。

4 結(jié) 語

本文提出了基于極大似然估計法的DV-HOP改進算法，在經(jīng)典算法的基礎(chǔ)上細化節(jié)點之間的跳數(shù)值，同時采用極大似然估計法修正求解節(jié)點坐標(biāo)時產(chǎn)生的誤差。通過Matlab仿真實驗，與經(jīng)典的DV-HOP算法和其他兩種算法進行對比，充分驗證了本文算法能夠在一定程度上減少定位誤差，提高定位精度。

參考文獻

[1] Ban?ur，?oko Jak?i?，Branimir Ban?ur，et al. An analysis of energy efficiency in wireless sensor networks（WSNs）applied in smart agriculture [J]. Computers and electronics in agriculture，2019，156：500-507.

[2] JERWIN PRABU.Optimization approach for a climbing robot with target tracking in WSNs [J]. Journal of ocean engineering and science，2018，3（4）：282-287.

[3] Design a WSN system for monitoring the safety of drinking water quality [J]. IFAC-papers on line，2018，51（17）：752-757.

[4] An improved three-factor authentication scheme for patient monitoring using WSN in remote health-care system [J]. Computer methods and programs in biomedicine，2019，182.

[5]郝志凱，王碩.無線傳感器網(wǎng)絡(luò)定位方法綜述[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2008（S1）：224-227.

[6]景路路，張玲華.基于跳距優(yōu)化的改進型DV-HOP定位算法[J].傳感技術(shù)學(xué)報，2017，30（4）：582-586.

[7] AMANPREET KAUR，PADAM KUMAR，GOVIND P GUPTA. A weighted centroid localization algorithm for randomly deployed wireless sensor networks [J]. Journal of king saud university - computer and information sciences，2019，39（1）：82-91.

[8] DV-Hop localization algorithm based on minimum mean square error in internet of things [J]. Procedia computer science，2019，147：458-462.

[9] XUE D L. Research of localization algorithm for wireless sensor network based on DV-Hop [J]. Eurasip journal on wireless communications an networking，2019（1）.

[10] LIU G Q，QIAN Z H，WANG X. An Improved DV-HOP localization algorithm based on HOP distances correction [J].中國通信，2019，16（6）：200-214.

[11]張曉鳳，王秀英.灰狼優(yōu)化算法研究綜述[J].計算機科學(xué)，2019，46（3）：30-38.

[12] MIRJALILI S，MIRJALILI S M，LEWIS A. Advances in engineering software [J]. Grey wolf optimizer，2014，69：46-61.

[13] LONG W，ZHAO D Q，XU S J. Improved grey wolf optimization algorithm for constrained optimization problem [J]. Journal of computer applications，2015，35（9）：2590-2592.