基于螺旋更新策略蜜獾優化的DV-Hop 定位算法*

魯 興，張來洪，任芳雨

（武漢中原電子集團有限公司，湖北 武漢 430205）

0 引言

隨著物聯網的發展，無線傳感器網絡（Wireless Sensor Networks，WSNs）得到了蓬勃發展。WSNs綜合了微電子學、集成電路、無線通信等多個學科的技術，因其具有自組織性、功效低、價格低廉、靈活性強等優勢，被廣泛地應用于搶險救災、環境監測、康復醫療、智慧城市建設和國防軍工等領域[1-4]。WSNs 定位技術主要有基于測距的算法和非測距的算法2 種?；跍y距的定位算法精度較高，但對硬件要求也高，在大規模的網絡環境中實現較為困難。非測距的定位算法不需要額外的硬件，實現簡單、成本較低，廣泛應用于大規模無線傳感器網絡中。

距離向量跳段（Distance Vector Hop，DV-Hop）算法因其實現簡單、通信開銷小等特點成為受到關注最多的非測距算法。傳統的DV-Hop 算法由于跳距處理誤差和最小二乘的累積誤差等原因導致定位精度較低。為了解決傳統DV-Hop 算法定位精度低的問題，國內外學者提出了大量的改進策略[5-7]。邴曉瑛等人[8]提出采用多通信修正跳數，并采用加權的思想修正未知節點的平均跳距，但未知節點的位置估計過程仍采用最小二乘法，沒有消除最小二乘法求解本身帶來的誤差。文獻[9]和文獻[10]將粒子群優化算法或人工蜂群優化算法引入到傳統DV-Hop 算法中，發現新算法可以減小最小二乘導致的誤差，一定程度上提高了定位精度，但該過程未改進粒子群算法以適應WSNs 場景，定位精度有待進一步提升。文獻[11]采用基于自適應策略的灰狼優化算法來替代傳統DV-Hop 的最小二乘法，新算法的收斂速度快、定位精度高，但忽略了未知節點平均跳距的誤差，定位精度有待進一步提升。文獻[12]提出了基于差分進化的節點定位方法，但差分進化受參數影響較大，控制參數選取不合適，種群進化中容易失去多樣性，無法找到最優解。

為此，本文分析傳統DV-Hop 定位算法的不足，提出了一種結合未知節點平均跳距修正和改進型蜜獾算法（Honey Badger Algorithm，HBA）的DVHop 定位方法，以期彌補傳統DV-Hop 定位算法的不足，提高定位精度和穩健性。

1 DV-Hop 算法及誤差分析

DV-Hop 算法主要分為3 個階段，具體如下文所述。

（1）未知節點與錨節點間最小跳數的估計。節點之間相互交換Hello 包，Hello 包中包含了跳數及錨節點坐標，網內未知節點獲得錨節點坐標及離各錨節點的最小跳數。

（2）計算未知節點與各錨節點間的距離。錨節點之間相互傳遞Hello 包后，獲知各自的位置信息以及互相之間的最小跳數。錨節點可利用式（1）計算平均跳距。

式中：(xi,yi)，(xj,yj)分別為錨節點i和錨節點j的位置坐標，num_hop為錨節點i和錨節點j的最小跳數。錨節點將自己計算得到的平均跳距向外廣播。未知節點將第1 個收到的錨節點的平均跳距作為自己的跳距，則根據式（2）可以估算出未知節點u與錨節點i之間的距離dui。

式中：num_hopui為未知節點u與錨節點i間的最小跳數，Hopsizeu為未知節點u選取的平均跳距。

（3）計算未知節點位置坐標。獲取錨節點的位置坐標以及未知節點到錨節點的距離，利用最小二乘法可求得未知節點坐標。

式中：X為未知節點位置，A和b為與錨節點位置以及未知節點與錨節點間距離相關的已知向量。通過上述過程，傳統DV-Hop 算法完成了未知節點的定位。由以上定位過程分析可知：在傳統DV-Hop算法中，未知節點以收到的最近的錨節點的平均跳距值作為自己的平均跳距值，沒有全面考慮網絡中的錨節點信息，在多跳網絡中，該取值方法不能真實反映網絡中的跳距情況，未知節點平均跳距產生的誤差會導致節點間距離與實際距離相差過大，因此需要綜合考慮多個錨節點的平均跳距離來準確地估計未知節點在網絡中的平均跳距[13,14]。此外，跳距誤差會在最小二乘法求解未知節點位置階段被進一步擴大，最小二乘法本身也會有較小的解算誤差，會造成誤差累積[15]。

2 DV-Hop 算法的優化

2.1 未知節點的平均跳距修正

傳統的DV-Hop 定位算法中，未知節點將離它最近的錨節點所估計的平均跳距值作為其平均跳距值，但單個錨節點的平均跳距值無法反映整個網絡的實際情況。

由文獻[16]可知：傳統DV-Hop 算法計算出的錨節點平均跳距比實際值偏小，并且錨節點數量越多，偏小誤差累加越大。為了使未知節點估計的平均跳距值更加準確，基于上述偏小誤差分析，將未知節點收到的多個錨節點所估計的平均跳距值、錨節點比例進行綜合考慮，修正后的未知節點在網絡中的平均跳距如下：

若0 ≤Bratio＜0.5，則

若0.5 ≤Bratio＜1，則

式中：UhopSize為未知節點在網絡內的平均跳距；BhopSizeave為錨節點平均跳距均值，即對未知節點所收到的所有錨節點的平均跳距取平均值；BhopSizemax為未知節點所收到的所有錨節點的平均跳距的最大值；Bratio為錨節點占總節點的比例。BhopSizemax和BhopSizeave的計算過程如下：

式中：Nb為未知節點所收到的錨節點個數。當錨節點較多時，用錨節點平均跳距最大值BhopSizemax來減小偏小的誤差。當錨節點較小時，結合錨節點平均跳距均值BhopSizeave和錨節點平均跳距最大值BhopSizemax進行綜合處理，修正后的未知節點平均跳距能夠更好地反映網絡的實際情況。

2.2 改進的蜜獾優化算法

HBA 作為一種新興的元啟發式優化算法，主要模擬蜜獾挖掘和尋找蜂蜜的智能覓食行為，因其與多種著名的元啟發式算法如模擬退火（Simulated Annealing，SA）、鯨魚優化（Whale Optimization Algorithm，WOA）等相比，在搜索復雜空間的優化問題上更為有效、結構簡單，故可廣泛地應用于許多場景。為了減小最小二乘算法估計未知節點坐標帶來的累積誤差，引入改進的HBA 算法來提高節點的定位精度。相較于傳統的HBA 算法，改進的HBA 算法首先引入了Sobol 序列來提高初始種群的遍歷性，其次使用螺旋更新機制來加強HBA 算法的局部搜索能力，最后采取鏡像策略規避估算位置越界的情況。

改進的HBA 算法的步驟大致分為確定適應度函數、種群初始化、定義氣味強度、更新密度因子、更新個體位置和越界處理。

2.2.1 確定適應度函數

改進的HBA 算法中，首先確定適應度函數以評估搜索位置的優劣，依據適應度函數向正確的方向進行搜索。適應度值的計算式為：

式中：n為該未知節點能接收到n個錨節點的信號，(x,y)和(xi,yi)分別為未知節點和錨節點i的坐標，disi為對未知節點平均跳距修正后計算得到的錨節點i與未知節點之間的距離。

2.2.2 基于Sobol 序列的種群初始化

在運用群智能算法時，首要需對種群中的個體分布進行初始化。若初始種群分布不佳，無法充分涵蓋取值空間，算法最終可能會收斂到質量不佳的解上，此時則需要增加迭代次數或種群個體數量來使解達到最優值，這會提高算法的計算量。傳統的蜜獾優化算法采用隨機分布的種群初始化方法，無法保證初始個體在搜索空間中合理分布。為了避免初始化種群隨機分布產生的問題，文中利用Sobol序列來初始化種群。

Sobol 序列是一種低差異序列，在種群的各個維度上均以2 為底數的radical inversion 組成，將盡可能均勻的初始點放置至多維立方體中，具有遍歷性、規律性的特點，可以用來初始化蜜獾種群，確保種群分布更為均勻和廣泛。

設全局解的取值范圍為[lb,ub]，由Sobol 序列產生的第i個隨機數為Ki，則種群的初始位置P0i可以表示為：

假設種群規模為100，分別采用隨機法和Sobol序列初始化種群，種群分布如圖1 和圖2。由圖1和圖2 可看出，Sobol 序列產生的初始種群分布更加均勻，擴大了蜜獾群的搜索范圍，增加了群體的多樣性，有利于算法跳出局部極值，一定程度上提高了算法的計算效率。

圖1 隨機初始化種群

圖2 Sobol 序列初始化種群

2.2.3 定義氣味強度

蜜獾依據氣味尋找獵物，因此獵物氣味越強越大，則表明離獵物越近，被搜索到的速度越快。氣味強度的定義如下：

式中：Ii為第i只蜜獾感受到獵物的氣味強度；S為獵物的集中強度，S=(Pi-Pi+1)2；ηi為獵物Pprey與第i只蜜獾Pi的距離，ηi=Pprey-Pi；r2為（0,1）的隨機數。

2.2.4 更新密度因子

密度因子α隨著迭代次數的增加而減少，確保算法在勘探和開發之間的平穩過渡。

式中：C0為大于1 的常數，取值不同會影響試驗結果，取2；lmax為最大迭代次數，l為當前迭代次數。

2.2.5 更新個體位置

傳統HBA 算法的位置更新分為挖掘階段和采蜜階段，該算法使用改變搜索方向的標志F，避免陷入個體位置的局部最優解。然而傳統蜜獾算法的挖掘階段沿著類心形軌跡運動，這會導致算法局部尋優能力較弱。挖掘階段的運動軌跡對算法最終的尋優位置具有重要的影響。若尋優軌跡不適合，算法很容易陷入局部優化，收斂速度減慢。

由前人研究可知：WOA、飛蛾火焰算法采用螺旋飛行路徑均具有較好的局部尋優能力。受此啟發，本文提出一種基于螺旋更新策略的局部尋優方法。在傳統蜜獾尋優算法的基礎上，增加螺旋更新階段，增強蜜獾算法的局部搜索能力。

（1）挖掘階段。蜜獾尋找獵物過程類似于心形，心形運動的軌跡可表示為：

式中：Pprey為當前發現的獵物的全局最佳位置；β為獵物獲取食物的能力；ηi為獵物和第i只蜜獾的距離；r3，r4，r5均為（0,1）的隨機數；F為改變搜索方向的標志，由下式確定：

式中：r6為0 至1 之間的隨機數。

（2）采蜜階段。蜜獾隨著導蜜鳥找到蜂巢，計算過程如下：

式中：r7為0 至1 之間的隨機數。

（3）螺旋更新階段。設置1 個隨機參數r8，由r8來決定蜜獾尋優的更新公式，當r8＜0.3 時，則依據個體當前位置更新，否則依據種群最優位置進行更新，計算過程如下：

式中：ηj為第j只蜜獾個體與目標獵物的距離；b為對數螺旋形狀參數；t取值為[-1,1]；Pnew為蜜獾尋優更新后的位置；Pi為蜜獾個體當前所處位置；l為迭代的次數；Pb為當前所估計的獵物位置，即全局最優位置。

螺旋更新的軌跡如圖3 所示。其中，Mi為第i只蜜獾個體，Ni為目標位置，個體位置圍繞目標位置Ni進行螺旋更新。通過修改參數t，個體位置可以收斂到目標位置的任意領域范圍內。螺旋方程表明個體可以環繞在目標位置的周圍而不僅是在它們之間的空間搜索，保證了算法的全局開發和局部搜索能力。

圖3 對數螺旋軌跡

2.2.6 越界處理

通過改進的HBA 算法估計出未知節點的最優位置，但有時估計出的未知節點會超出規定的網絡區域，發生越界情況。在現實應用中，所有節點部署在規定區域內，越界的節點將無意義。

本文提出了鏡像策略來處理節點越界情況。在節點越界的維度，對其進行鏡像處理，將其映射回合法區域內。具體映射變換過程如下：

若未知節點求解出的坐標為(xi,yi)，其在x上的取值范圍為[xlow,xup]，在y上的取值范圍為[ylow,yup]。由式（16）、式（17）求出的解即可不出現越界情況，保證了解的現實意義。

綜上，文中所提基于螺旋更新策略蜜獾優化的DV-Hop 定位算法的流程如圖4 所示。

圖4 改進型DV-Hop 算法流程

（1）設置相關參數，如蜜獾個體的數目、蜜獾種群維度、蜜獾捕食能力β、密度因子中的常數C0、最大迭代次數lmax、搜索空間的上下界ub和lb、對數螺旋形狀參數等。

（2）修正未知節點的平均跳距，并求解出未知節點與錨節點間的距離。依據錨節點個數比例、所有錨節點平均跳距的最大值和所有錨節點平均跳距的平均值3 個因子來修正未知節點平均跳距。將此修正的平均跳距乘以未知節點到各錨節點的最小跳數，從而得出未知節點與各錨節點間的距離。

（3）采用Sobol 序列初始化蜜獾種群。

（4）進入迭代循環后計算個體位置更新公式所需要的一些參數，如密度因子α、氣味強度I、搜索方向F等，用蜜獾挖掘階段和采蜜階段的式（12）和式（14）更新個體位置。

（5）為了進一步提高解的精度，采用式（15）進行螺旋更新，并計算種群個體適應度值，更新個體最優值和全局最優值。

（6）判斷是否達到迭代次數上限，沒有則返回步驟（4），達到迭代上限，則輸出最優個體位置。

（7）判斷所有估計的未知節點位置是否越界，若越界按式（16）和式（17）進行越界處理，否則不處理。

3 仿真實驗及結果分析

為了驗證文中所提算法的定位性能，對比分析所提算法與傳統DV-Hop算法、基于跳距修正的DVHop 算法和基于POS 的DV-Hop 算法。在100 m×100 m 的網絡范圍內隨機部署未知節點和錨節點。文中算法的蜜獾優化種群規模設為100，最大迭代次數設為50，并采用歸一化的平均定位誤差來定量地評估各算法的定位精度，其定義如下：

式中：Nu為未知節點個數，R為節點的通信半徑，為估計的未知節點位置，(xi,yi)為未知節點的真實位置，σ取連續仿真30 次的平均值結果。

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

首先，分析總節點數對定位性能的影響，其中總節點數從60～260 變化，錨節點占總節點數的比例為25%，通信半徑為30 m，平均定位誤差隨總節點數的變化趨勢如圖5 所示。由圖5 可知：當總節點數為60 時，DV-Hop 算法的平均定位誤差為0.351，跳距修正的DV-Hop 算法的平均定位誤差為0.310，基于POS 的DV-Hop 算法的平均定位誤差為0.255，而本文提出的算法平均定位誤差為0.205。隨著節點總數的增加，平均定位誤差隨之降低。究其原因可能在于，在一定區域內，隨著節點總數的增加，節點之間連通性變強，節點收集到更多的信息，從而使定位誤差下降。當然，當總節點數達到一定的值時，平均定位誤差下降的速度明顯減緩。相比于 DV-Hop 算法、跳距修正的DV-Hop 算法和基于PSO 的DV-Hop 算法，本文所提算法平均定位誤差最低，這歸功于本文所提算法修正了未知節點平均跳距以及采用改進的HBA 算法來估算未知節點位置。

圖5 總節點數對定位精度的影響

3.2 錨節點所占比例對定位性能的影響

將節點總數設置為100，通信半徑設置為30 m，錨節點所占比例為20%～70%，仿真結果如圖6所示。在錨節點較少時，所有算法的平均定位誤差均較大。隨著錨節點比例的增加，各算法的平均定位誤差均減小。這是由于較多的信標節點可以使跳距估計更為準確。當信標比例大于45%時，各算法平均定位誤差下降的趨勢明顯減緩。從4 種算法的對比可以看出，最終本文所提算法的誤差小于DVHop 算法、跳距修正的DV-Hop 算法、基于POS 的DV-Hop 算法的誤差，且分別平均降低56.17%、44.70%和28.12%。

圖6 錨節點比例對定位精度的影響

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

在節點總數為100，信標所占比例為25%時，通信半徑在20～45 m 之間變化，觀察通信半徑對定位性能的影響。各算法的平均定位誤差隨通信半徑R的變化曲線如圖7 所示。隨著通信半徑的增加，平均定位誤差不斷下降。在通信半徑為20～40 m 之間時，通信半徑的增加會極大提升網絡連通性，快速提高定位精度。當通信半徑大于40 m 時，平均定位誤差下降的速度減緩，不再有效提高定位精度。對比分析可知：最終本文所提算法的定位誤差與DV-Hop 算法、跳距修正的DV-Hop 算法、基于POS 的DV-Hop 算法相比分別降低了54.95%、45.51%和25.19%。

圖7 通信半徑對定位精度的影響

4 結語

針對傳統DV-Hop 算法定位精度不足的問題，本文首先分析了其產生誤差的原因，提出了一種改進的HBA 算法與基于未知節點平均跳距修正的DV-Hop 算法相結合的融合算法。該融合算法首先采用依據信標節點比例對未知節點平均跳距進行分段修正以縮小跳距估計誤差，再針對傳統蜜獾算法的不足進行了改進。結果表明：在不增加任何通信開銷時，文中所提算法能有效提高定位精度和穩定性。但文中所提算法的計算量較傳統的DV-Hop 算法有所提高，后續研究在提高計算精度的同時能兼顧計算復雜性。