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

朱曉娟 陳智麗

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

關鍵詞：無線傳感器網絡;DV-HOP算法;灰狼算法;極大似然估計;誤差分析;平均跳躍距離

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

0 引 言

隨著無線網絡的高速發展，無線定位技術受到了業界的廣泛關注，已經在智能農業[1]、目標跟蹤[2]、水質監測[3]、遠程醫療[4]等領域得到不斷發展。在無線傳感器網絡的大多數應用中，沒有位置信息的任何事件信息都是毫無意義的。例如，在火災探測應用程序中，需要事件（火災）和探測火災的地點（位置）。因此，精準定位是無線傳感器網絡的要求。

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

1 DV-HOP算法與誤差分析

1.1 傳統的DV-HOP算法

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

（1）獲取錨節點和未知節點的跳數信息

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

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

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

式中：m是給定網絡中的錨的總數;i是每個錨的id;（xi， yi）和（xj， yj）分別為錨節點i和錨節點j的坐標;hji是錨節點i和錨節點j之間的最小跳數。

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

（3）確定未知節點的坐標

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

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

化簡后可得方程（4）：

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

由此可得未知節點u的坐標為Xu=（ATA）-1ATB

1.2 DV-HOP算法的誤差分析

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

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

在DV-HOP算法中，用信標節點的跳數乘以平均每跳的距離來表示節點之間的距離，這種估算方法可能會存在較大誤差。例如圖1所示的網絡拓撲結構。

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

2 算法的改進

2.1 標準灰狼優化算法

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

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

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

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

2.1.1 種群初始化

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

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

2.1.2 種群搜索

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

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

系數C和A的計算公式如下：

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

2.1.3 種群位置信息計算

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

2.2 灰狼算法修正平均跳數

在經典的DV-HOP第二階段，信標節點通過應用式（1）計算平均跳距，然后應用式（3）計算它們與每個信標的距離。此后，信標使用灰狼算法細化平均跳距。式（15）為用于實現最佳平均跳躍距離的適應度函數：

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

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

初始化i=1

do

for 每一個節點用式（15）更新其平均跳數

end for

更新a，A，C的值，再次決定目標函數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σ的質心，返回最優平均跳數

2.3 極大似然估計法修正坐標

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

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

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

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

式（19）可以表示為：

令

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

令

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

3 實驗仿真驗證

3.1 仿真環境

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

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

仿真參數見表1所列。

節點隨機分布如圖2所示。

3.2 仿真結果分析

3.2.1 節點總數對定位性能的影響

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

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

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

4 結 語

本文提出了基于極大似然估計法的DV-HOP改進算法，在經典算法的基礎上細化節點之間的跳數值，同時采用極大似然估計法修正求解節點坐標時產生的誤差。通過Matlab仿真實驗，與經典的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]郝志凱，王碩.無線傳感器網絡定位方法綜述[J].華中科技大學學報（自然科學版），2008（S1）：224-227.

[6]景路路，張玲華.基于跳距優化的改進型DV-HOP定位算法[J].傳感技術學報，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]張曉鳳，王秀英.灰狼優化算法研究綜述[J].計算機科學，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.