基于改進蝴蝶優化的DV-Hop定位算法*

葉 帥，余修武，劉 永

（南華大學，湖南 衡陽 421001）

0 引言

無線傳感器網絡（Wireless Sensor Networks，WSNs）是一種由大量的傳感器節點組成，通過無線方式進行通信、連接進而達到某種任務目的的網絡[1]，其在軍事偵察、地理環境監測以及交通路況監測[2]等領域都有廣泛的前景。WSNs進行數據采集和檢測時需要結合位置信息以確保信息的有效性[3]，因此定位技術成為WSNs技術中研究的熱點。

目前無線傳感網絡定位算法大致分為基于測距和無須測距兩類[4]。基于測距的定位算法主要有信號傳輸時間算法（Time Of Arrival，TOA）、到達時間差算法（Time Difference Of Arrival，TDOA）、接收信號強度指示算法（Received Signal Strength Indication，RSSI）和信號到達角算法（Arrival Of Angle，AOA）等。無須測距定位算法主要有質心算法、近似最佳三角形內點測試算法（Approximate Perfect Point-In-Triangulation Test，APIT）、Amorphous算法以及距離向量跳段算法[5]（Distance Vector-Hop，DV-Hop）等。相比基于測距的定位算法，無須測距定位算法雖然定位精度不高，但具有成本低、功耗小以及硬件設備簡單等優勢，從而備受關注。無須測距定位算法中的DV-Hop算法由于對物理測量單元的要求不高并且在各向同性網絡中具有良好的性能[6]，引起了廣大學者的關注。

為了解決DV-Hop算法定位精度不高的問題，學者們對該算法做了不同程度的改進。文獻[7]通過引入多通信半徑廣播數據，減小平均跳數誤差，改善了算法的定位精度，但由于只對前兩個階段進行改進，定位精度并不穩定。文獻[8]使用局部加權線性回歸（Locally Weighted Linear Regression，LWLR）選擇最佳候選信標節點子集，提高了定位精度，但在信標節點密度較低的環境中，定位效果并不理想，具有一定的局限性。文獻[9]提出了改進鯨魚算法（Improved Whale Optimization Algorithm，IWOA），該算法采用深度神經網絡（Deep Neural Networks，DNN）來初始化種群，并使用非線性策略以及二次插值對鯨魚算法進行改進，提高了定位精度。文獻[10]利用接收信號強度值和無偏估計對跳數和平均跳距進行了校正，使用差分進化算法估計未知節點算法，在一定程度上降低了平均定位誤差。文獻[11]提出了MA*-3DDV-Hop算法，該算法首先通過A*路由算法減小了跳數以及平均跳距不準確所帶來的誤差，在定位階段采用非支配遺傳算法（Non-dominated Sorting Genetic Algorithm-II，NSGA-II）替代原有的最小二乘法，提高了定位精度，但是算法復雜度較大。

上述方案在一定程度上提高了定位精度，但仍然存在很大的局限性。為了進一步提高DV-Hop算法的定位精確度，本文提出了基于改進蝴蝶優化的DV-Hop定位算法（Improved Butterfly Optimization Algorithm，IBOA）。首先通過細化信標節點廣播半徑以及引入跳距修正因子來減小傳統DV-Hop算法前兩個階段產生的誤差；其次在定位階段，將黃金正弦算法和蝴蝶算法相結合優化定位結果，從而減少節點定位誤差，提高算法尋優能力。

1 相關理論

1.1 DV-Hop算法

DV-Hop算法的定位過程分為以下3個階段。

（1）獲得最小跳數。所有的信標節點廣播的信息中包括坐標信息和跳數的數據分組，初始化跳數為0。如果信標節點跳數小于前一個值，則更新并保存該最小值。根據此機制，在廣播結束后，所有信標節點獲得最小跳數。

（2）估計平均跳距。由第一階段獲得的任意兩個信標節點的坐標信息以及最小跳數計算得到平均跳距為：

式中：(xi,xj)，(yi,yj)為信標節點i，j的坐標；hij為信標節點i和j(j≠i)之間的跳數。

每個未知節點通過第二階段獲得的平均跳距乘以最小跳數得出到各信標節點之間的距離，其計算公式為：

式中：di為未知節點i到信標節點的估計距離；hni為未知節點i到信標節點的最小跳數。

（3）計算未知節點坐標。當信標節點數大于或者等于3時，使用最小二乘法估計目標節點位置。

設目標節點的坐標為(x,y)，信標節點的坐標為(xi,xj)(i=1,2,…,n)，根據距離公式可得目標節點與各個信標節點間的距離關系為：

用向量表示為：

根據最小二乘法可得目標節點的坐標：

1.2 蝴蝶優化算法

蝴蝶優化算法[12]是一種自然啟發式算法。該算法的主要思想就是通過模擬蝴蝶覓食和求偶行為來尋找最優解，具有操作簡單、調整參數少、魯棒性好等優點。

在BOA中，蝴蝶的香味強度f與所受刺激強度I有關。香味強度的計算公式為：

式中：c表示感官模態；a表示香味強度衰減指數。

蝴蝶優化算法在初始化階段定義目標函數和解空間，并對算法中的相關參數賦值，然后在解空間中隨機生成蝴蝶的位置，并根據目標函數和式（9）計算每只蝴蝶的香味強度。迭代過程中，蝴蝶種群會隨機移動或者向著全局最優的蝴蝶移動。若處于全局搜索階段，其位置更新公式為：

若處于局部游走階段，其位置更新公式為：

2 改進蝴蝶優化的DV-Hop算法

2.1 DV-Hop算法優化

2.1.1 跳數的改進

在傳統的DV-Hop算法中，其跳數是通過節點的通信半徑來確定的，只要在信標節點廣播半徑范圍內的節點跳數均記為一跳。如圖1所示，圖中信標節點A和未知節點B、C、D、E間跳數均記為一跳，但實際上AB、AC、AD、AE的距離相差很大。這種方式記錄得出的跳數存在巨大誤差，因此本文采用多通信半徑方式對跳數進行細化，提高跳數的準確性，從而提高算法的定位精度。其中，R為節點的通信半徑。

圖1 多通信半徑圖示

隨著廣播次數增加，信標節點所消耗的能量也隨之加大。考慮到無線傳感器節點能量的有限性，設定信標節點的廣播半徑為0.25R，0.5R，0.75R和R。

2.1.2 跳距的改進

（1）信標節點跳距的改進

為了減小信標節點平均跳距誤差對定位結果的影響，本文引入修正因子ei優化信標節點的平均跳距。修正因子的計算公式為：

式中：dij為信標節點間的實際距離；為信標節點間的估計距離。

優化后的平均跳距表達式為：

（2）未知節點跳距的改進

由于現實無線傳感器網絡中節點都是隨機分布的，未知節點到信標節點的距離不盡相同，從而導致較大誤差。因此，本文根據每個信標節點的跳數信息引入權重因子wi，從而改進未知節點的平均跳距。假設未知節點m接收到n個信標節點的平均跳距，權重因子wi的表達式為：

式中：hmi為未知節點i到信標節點m的最小跳數。

未知節點的平均跳距為：

2.2 基于改進蝴蝶算法的定位優化

2.2.1 佳點集初始化種群

原始的蝴蝶優化算法在搜索空間中隨機產生初始種群，從而造成初始解分布不均勻。為了使初始解分布更加均勻，本文引入佳點集初始化種群。佳點集[13]是由我國數學家華羅庚等人提出，其原理為，設Gs是s維歐式空間單位立方體，如果r∈Gs，有：

式中：{r1(n)×k}表示取小數部分。則稱pn(k)為佳點集，r稱為佳點。其偏差φ(n)=C(r,ε)n(-1+ε)，其中C(r,ε)為只與r,ε(ε＞0)有關的常數。取r={2cos(2π/p)}，1≤k≤s，p是滿足(p-3)/2≥s的最小素數。將其映射到搜索空間，則有：

式中：ubj和lbj為種群第j維的上下界。

假設種群規模為100、空間維度為2。圖2和圖3分別表示隨機分布和佳點集初始化的種群，可以看出由佳點集初始化的種群分布更加均勻，覆蓋更加充分。x,y分別表示節點對應的橫、縱坐標。

圖2 隨機初始化種群分布

圖3 佳點集初始化種群分布

2.2.2 動態切換概率策略

p用于全局搜索和局部探索的切換。標準的BOA中的p是一個固定的值[14]，在算法的后期搜索最優個體的能力弱，易陷入局部最優，因此本文采用動態轉換概率來實現全局搜索和局部搜索的轉換，從而提高算法后期的尋優能力，更好平衡全局搜索和局部搜索。轉換概率公式為：

式中：i，N_iter分別為當前迭代次數和最大迭代次數。

2.2.3 全局擾動因子

為了進一步加強算法的探索能力和提高收斂精度，受到正態分布的啟發，在傳統全局位置更新處引入全局擾動因子Ψ，其表達式為：

式中：normrnd(0,1)表示服從正態分布的隨機數；randn()表示(0,1)之間的隨機數。改進后的全局位置更新公式為：

2.2.4 黃金正弦搜索策略

黃金正弦算法（Gold-SA）[15]是于2017年提出的一種新型元啟發式優化算法。與傳統的元啟發式優化算法相比，Gold-SA算法具有魯棒性好、設置參數少、尋優能力強等特點。另外，Gold-SA算法在位置更新的過程中融入黃金分割系數，在每次迭代過程中都充分搜索能產生優解的區域，加快了算法的收斂速度，增強了局部開發能力。

針對傳統BOA算法局部搜索能力弱，無法快速準確尋找到最優解，本文引入黃金正弦算法來替代原算法的局部搜索進行尋優，提高了算法的搜索效率和定位準確性。改進后的局部搜索公式為：

式中：r1為區間[0,2π]中的隨機數；r2為區間[0,π]中的隨機數。θ1和θ2的表達式為：

式中：α和β的初始值分別取-π和π；τ為黃金分割系數

2.3 改進DV-Hop算法流程

為了提高DV-Hop算法的定位精度，本文提出了基于改進蝴蝶的DV-Hop算法。改進后的算法流程如下：

（1）在無線傳感器網絡中隨機分布若干個節點，根據改進的DV-Hop算法得到最小跳數以及節點間的最優跳距。

（2）運用佳點集初始化種群，并設置迭代次數、蝴蝶種群數量、官能模態以及刺激強度等相關參數。

（3）根據目標函數計算種群的適應度值，并記錄最佳的適應度值以及所對應個體的位置。

（4）根據式（21）和式（22）對個體位置進行更新，并且記錄每次更新之后最佳個體的適應度值以及所對應的位置。

（5）如果滿足迭代終止條件，則終止算法執行并且輸出全局最優解以及相對應的位置，否則返回步驟4繼續進行迭代優化。

3 仿真分析

為了驗證本文所提出IBOA算法的有效性，利用MATLAB 2018a進行了仿真實驗，并與傳統的DVHop算法和文獻[16]算法進行比較。如圖4所示，設在100 m×100 m的方形區域內隨機部署100個傳感器節點，其中信標節點20個。為了增加實驗結果的準確度，實驗選取模擬50次的平均值作為最終的結果。

圖4 網絡節點隨機部署

本文通過依次改變信標節點比例、節點通信半徑以及節點總數來驗證提出算法的性能，并且采用歸一化相對誤差作為定位算法的評價標準。其計算公式為：

3.1 信標節點比例對定位精度的影響

在網絡區域內隨機布設100個節點，保持通信半徑R=20 m不變，信標節點的比例從5%變換至25%，對比3種算法，結果如圖5所示。

圖5 信標節點比例對定位精度的影響對比

3種算法的平均定位誤差總體上均隨著信標節點比例增大而減小，其中改進算法定位誤差明顯要低于另外兩種對比算法。在信標節點比例較小時，定位誤差曲線下降的幅度較大。信標節點比例增加到15%之后，曲線趨于平穩。在不同信標節點比例下，本文改進算法的平均定位精度相比傳統DV-Hop算法和文獻[16]算法分別提高了23.51%和4.7%。

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

在網絡區域隨機分布100個節點，其中信標節點個數為10，通信半徑R從20 m依次增加到40 m。對比3種算法，結果如圖6所示。

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

3種算法的定位誤差總體上隨著通信半徑的增加逐漸減小。當通信半徑較小時，定位誤差曲線下降幅度較大，當通信半徑增加到20 m時，曲線開始趨于平穩。在相同條件下，本文提出的算法定位精度始終都是最高的。在不同通信半徑條件下，本文改進算法平均定位精度相比傳統DV-Hop算法和文獻[16]算法分別提高了22.33%和2.81%。

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

在網絡區域內隨機分布10個信標節點，保持通信半徑R=20 m不變，節點總數從60增加到100，對比3種算法，結果如圖7所示。

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

3種定位算法的定位誤差總體隨著節點總數的增加而逐漸減小。當節點總數較小時，定位誤差下降幅度較大，當總數達到90以后，曲線開始趨于平穩。在不同的節點總數下，本文改進算法平均定位精度相比傳統DV-Hop算法和文獻[16]算法分別提高了30.35%和12.10%。

4 結語

針對傳統DV-Hop算法定位精度低的問題，本文提出了IBOA的無線傳感器定位算法。IBOA首先采用多通信半徑的方式降低信標節點間的跳數，其次通過引入修正因子降低未知節點到信標節點的平均跳距，最后使用黃金蝴蝶算法計算未知節點的坐標。實驗結果表明，本文提出的IBOA算法相比傳統的DV-Hop算法以及其他現有算法在定位精度上有了明顯的提高。