基于WBOA的3D-DV-Hop節點定位算法*

彭 鐸，張騰飛，黎鎖平，楊雅文

（1.蘭州理工大學計算機與通信學院，甘肅 蘭州 730050；2.蘭州理工大學理學院，甘肅 蘭州 730050）

0 引 言

無線傳感器網絡（wireless sensor networks，WSNs）［1］的節點用來感知、采集、處理網絡分布比較危險復雜區域內的檢測對象的位置及其信息，所以，節點定位成為WSNs的關鍵問題之一，也是該領域的研究熱點［2］。而這些危險復雜區域的地貌通常都是三維（3D）的，因此，3D節點定位至今仍是研究熱點［3］。

3D-DV-Hop（distance vector hop）是典型的非測距定位算法，存在定位精度不高的缺陷。文獻［4］提出了一種自適應免疫粒子群與DV-Hop 融合算法，優化了位置估計階段，有效的提高了算法的定位精度。文獻［5］提出的算法通過對跳數、跳距優化，用改進粒子群算法優化位置坐標來提高算法定位精度。文獻［6］提出了基于彈簧系數和接收信號強度指示的DV-Hop 的改進算法，通過引入彈簧模型改進最小跳數與平均跳距，提高了算法的定位精度。文獻［7］針對3D-DV-Hop全局跳數劃分不夠精確，利用錨節點的平均跳距估算距離時導致定位誤差大的問題，提出一種基于多通信半徑和跳距加權的WSNs 3D迭代定位算法。文獻［8］通過創建權值與跳數的數學模型，利用遺傳算法對該定位模型進行全局最優求解，使得模型定位誤差收斂到1／4。文獻［9］提出了一種改進的基于鄰近節點信息的3D-DV-Hop算法，該算法通過計算未知節點的跳數，消除了節點間的一次通信，降低了網絡的功耗。文獻［10］提出了一種基于改進的獅子群優化算法的3D-DV-Hop定位方法，該算法利用群智能優化算法用于未知節點坐標的優化，沒有考慮平均跳距誤差過大造成節點定位精度低的情況。

為了更加擬合現實環境狀況，網絡節點分布變得比較隨機，可能會出現某一節點在其他節點的通信范圍之外，導致此節點無法與其他節點通信或者無法定位，（后文將這些節點統稱為孤立點，在3.1 節說明），將這些節點去除。對于由平均跳距估算距離時出現誤差較大的問題，本文首先利用修正因子修正平均跳距，然后利用修正的平均跳距估算的距離與實際距離的差值函數作為目標函數，用自適應權重改進后的蝴蝶優化算法（butterfly optimization algorithm，BOA）求得全局最優平均跳距。

1 3D-DV-Hop定位算法

1.1 3D-DV-Hop算法步驟

3D-DV-Hop 定位算法是二維DV-Hop 定位算法［11］的擴展，是一種距離無關的定位算法，其算法主要有3 個階段：

步驟1 計算錨節點與每個未知節點的最小跳數

所有錨節點以多跳的方式向網絡中廣播自身數據包，信息發出的錨節點的跳數為0，數據包每經過一個節點，跳數加1，當一個節點收到多個跳數信息時，保存跳數值最小的一條信息。

步驟2 計算錨節點的平均每跳距離

利用式（1）估算平均每跳距離

式中 （xi，yi，zi）和（xj，yj，zj）為錨節點i和j的坐標，hopi，j為錨節點i到錨節點j的跳數，hopsizei為錨節點i的平均跳距。

步驟3 利用極大似然估計法計算自身坐標

未知節點通過式（2）計算它和錨節點之間的距離Di，j，然后根據最小二乘法就能得到未知節點的坐標

式中Di，j為錨節點i和未知節點j之間的距離，hopi，j為錨節點i和未知節點j之間的最小跳數。

1.2 DV-Hop算法的誤差分析

由于網絡拓撲的隨機性，當網絡區域大，節點數少或通信半徑短時，網絡中會出現一些孤立點，導致實驗不能有效進行，且離錨節點距離越遠的未知節點累積的誤差越大。

利用極大似然估計法計算未知節點坐標時，需要知道錨節點與未知節點的估計距離，由于兩節點之間的跳距往往并不相等，利用錨節點的平均跳距估算距離時也會產生較大的誤差。

2 BOA

根據蝴蝶的覓食行為，提出了一種新的全局優化元啟發式算法--BOA［12］。BOA模仿蝴蝶覓食這種行為來尋找超搜索空間中的最優解。

蝴蝶的自然現象受變量I和對香味感知度f的影響，算法的變量I與目標函數相關聯。在BOA中，香味是物理刺激強度的函數，公式如下

式中f為對香味的感知程度，即其他蝴蝶對香味的感知程度，c為感覺模態，I為刺激強度，a為與模態有關的冪指數，反映了不同的吸收程度，a和c的取值范圍為［0，1］。

該算法有2個關鍵的階段：全局搜索階段與局部搜索階段。在全局搜索階段，蝴蝶朝著香味最濃的方向移動，即向最優的蝴蝶g*靠近?？梢杂檬剑?）來表示

式中為迭代次數為t的蝴蝶的解向量。g*為當前迭代中所有解中找到的當前最佳解，r為（0，1）中的隨機數。

局部搜索階段可以表示為

式中和為解空間中的第j個和第k個蝴蝶的解向量。如果和屬于同一個種群，并且r為（0，1）中的隨機數，則式（5）為局部隨機游走。在BOA 中使用切換概率在全局搜索和局部搜索之間切換，由文獻［13］測試可知，p＝0.8對算法最有益。

3 3D-DV-Hop定位算法

3.1 去除孤立點

在該算法中，如果某一節點到與其他超過總節點數50%節點的跳數的返回值為無窮大，那么稱這個節點為孤立點。去除孤立點的過程如下：

1）節點i與a個節點不能通信，判斷a是否大于總節點數的50%；

2）若是，則將節點i確定為孤立點，并分別記錄錨節點與未知節點中存在的孤立點個數；

3）從錨節點和未知節點中去除這些孤立點，然后重新初始化節點個數及節點間的距離與跳數。

3.2 修正平均每跳距離

由DV-Hop算法的誤差分析得知，錨節點的平均跳距是影響定位精度的主要原因。因此本文添加了修正因子優化錨節點的平均跳距。

改進步驟如下：

步驟1 根據式（1）求得每個錨節點的每跳平均距離hopsizei，則2個錨節點i，j之間的估計距離Dij為

步驟2 錨節點i，j之間的實際距離可以由其坐標計算得到

步驟3 根據式（6）和式（7），錨節點i，j之間的距離誤差dij可表示為

步驟4 根據距離誤差dij計算錨節點i的修正因子

ci為

此時，錨節點i的平均每跳距離hopsizei可表示為

步驟5 利用修正后的平均跳距計算錨節點i，j之間的估計距離D公式為

3.3 求取最優平均跳距

求取最優平均跳距分為3個步驟：

步驟1 初始化階段，算法定義目標函數及其解空間，為BOA中使用的參數賦值，創建一個用于優化的蝴蝶初始種群。

設錨節點i對應的平均跳距為hopsizei，ε為平均跳距引起的誤差，合理的hopsizei應使ε最小，由式（7）和式（11）可得

由此，可知適應度函數如下

使用式（3）計算蝴蝶的香味。在求解最優平均跳距hopsizei時，在搜索空間中隨機生成蝴蝶的位置，計算并存儲它們的香味值和適應度值。

步驟2 迭代階段，由算法進行多次迭代。

基本的BOA 存在收斂精度較低，全局搜索能力不足，容易陷入局部最優的缺陷。受文獻［13］的啟發，為了平衡全局搜索與局部搜索的能力，算法采用自適應權重處理的方法。

當權重比較大時，算法的全局搜索能力較強，可以搜索較大的區域；當權重比較小時，算法的局部搜索能力較強。采用如式（14）所示的權重因子對全局搜索階段進行加權，使得算法易跳出局部最優，提高了算法的全局搜索能力

改進后的全局搜索階段如式（15）所示

采用式（16）的所示的權重因子對局部搜索階段進行加權，提高了算法的局部搜索能力，加快了算法的收斂精度

改進后的局部搜索階段如式（17）所示

由開關概率p判斷算法是進行全局搜索還是局部搜索，若r＜p，則算法進行全局搜索，由式（15）來尋優，若r≥p，則算法進行局部搜索，由式（17）來尋優。然后判斷尋找的最優值是否在所設特定條件之內發生，若是，更新最優解，算法更新感覺模態c，進行下次迭代，直到達到最大迭代次數，算法停止。

步驟3 當迭代階段結束時，算法輸出找到具有最佳適應度的hopsizei的最佳解。

在該算法中，將利用自適應權重因子改進的BOA命名為WBOA（weighted BOA）。

3.4 利用極大似然估計法計算自身坐標

未知節點接收到改進后的最優平均每跳距離，通過式（2）計算它和錨節點之間的距離Di，j，然后根據極大似然估計法能得到未知節點的坐標。該算法的流程如圖1 所示。

圖1 算法流程

4 算法仿真與結果分析

4.1 WBOA的優化性能分析

為了進一步驗證WBOA在求解此定位問題的有效性，將WBOA 與BOA、鯨魚優化算法（whale optimization algorithm，WOA）［14］以及花授粉算法（flower pollination algorithm，FPA）［15］進行對比。為了實驗的公平、客觀性，選取與式（13）維數一致的基本測試函數式（18）來驗證WBOA的尋優性能，范圍為［-100，100］，WBOA 和BOA 中的c感官形態設置為0.01，冪指數a為0. 1，切換概率p為0.8，所有算法的初始種群規模統一設為30，迭代次數設置為500，4個算法的共有參數保持一致

算法的尋優質量由最優值和最差值反映，從表1 數據中可知，對求解函數f時，WBOA 能尋到理論最優值0，說明，在求解此類函數，WBOA 的尋優性能最強，明顯優于BOA、WOA、FPA。

表1 測試函數實驗結果比較

為了直觀展現WBOA的尋優性能，本文給出測試函數的收斂曲線，如圖2 所示。由函數的收斂曲線可以直觀地看出改進后的算法WBOA的收斂精度更高，解決了基本算法BOA尋優精度不高的問題。

圖2 收斂曲線

4.2 基于WBOA的3D-DV-Hop算法參數設置

為了驗證本文算法的定位性能，利用MATLAB 2018a對基于WBOA的3D-DV-Hop、3D-DV-Hop算法和文獻［10］中提出的算法，從錨節點個數、通信半徑大小和總節點個數等3個方面進行仿真實驗分析。在100 m ×100 m ×100 m的仿真區域內，隨機產生一定數量的網絡節點。算法的參數設置如表2所示。

表2 基于WBOA的3D-DV-Hop算法相關參數設置

網絡的平均定位誤差計算公式如下

式中 （xi，yi，zi）與（x′i，y′i，z′i）為未知節點i的實際坐標和估計坐標，R為錨節點的通信半徑，N為未知節點的總數。

4.3 仿真實驗分析

圖3是節點總數為100，網絡通信半徑為30 m時，錨節點個數的變化對網絡節點平均定位誤差的影響，從圖中可以看出，3種算法在隨著錨節點個數增加時平均定位誤差都有不同程度的降低。其原因是錨節點的個數增加，則其密度增大，未知節點從距離最近的錨節點獲取的平均跳距時更加接近其自身的平均跳距，從而使得平均定位誤差降低。在相同的條件下，基于WBOA的3D-DV-Hop算法的平均定位誤差最小，當錨節點的比例在20%～30%之間時，基于WBOA的3D-DV-Hop 算法的平均定位誤差相比于文獻［10］算法降低了10%～15%；當錨節點的比例在35%～50%之間時，基于WBOA 的3D-DV-Hop 算法的平均定位誤差相比于文獻［10］算法降低了3%～6%。

圖3 錨節點數對平均定位誤差的影響

圖4 是節點總數為100，網絡通信半徑為40 m時，錨節點個數的變化對網絡節點平均定位誤差的影響，與圖3 相比，通信半徑增大，3種定位算法的平均定位誤差都有了不同程度的下降，是因為隨著跳數的增加，未知節點的累積誤差也會增大，而通信半徑增大時，節點間的跳數隨之減少，則未知節點的定位誤差也隨之降低。由圖4 可知，在相同的條件下，基于WBOA的3D-DV-Hop算法的平均定位誤差一直都最小，對比于文獻［10］來說，平均定位誤差降低了1%左右。3種算法的平均定位誤差隨著錨節點的增多穩定下降，這是因為網絡區域小，錨節點數增多，通信半徑大，誤差波動相對穩定。

圖4 不同通信半徑下錨節點數對平均定位誤差的影響

圖5 是錨節點數比例為30%，網絡通信半徑為30 m時，總節點個數的變化對網絡節點平均定位誤差的影響。從圖中可以看出，隨著節點總數的不斷增加，3 種定位算法的平均定位誤差都較為穩定的降低，這是因為節點總數增加，節點的密度提高，網絡的連通性變好，孤立點減少，網絡可以收集更多的定位信息用于未知節點的定位。在相同的條件下，本文算法的平均定位誤差一直都最小，與文獻［10］算法比較而言，本文算法的平均定位誤差大致降低了5%左右。而當節點總數在100 ～120 之間時，本文算法明顯更加優于其他兩種算法，當節點數大于120 時，3 種算法的平均定位誤差隨著節點總數的增加逐漸降低，從整體分析來看，本文算法的優勢更加突出。

圖5 節點總數對平均定位誤差的影響

4.4 算法的時間復雜度分析

時間復雜度反應了算法執行的時間長短。算法中所涉及的網絡節點規模大小與節點總數n相關，錨節點的數為m。則3D-DV-Hop算法的時間復雜度為O（n3）；文獻［10］算法在3D-DV-Hop 算法的基礎上增加的時間復雜度為O（n（n-m）2）；本文算法在3D-DV-Hop算法的基礎上增加的時間復雜度為O（n×m），由此可知：本文算法相比較文獻［10］算法時間復雜度略小一些。

4.5 計算開銷分析

將算法的平均運行時間作為算法開銷指標進行分析。表3為相同實驗條件下所統計的3 種算法的平均運行時間。由實驗結果可知：本文算法的平均運行時間比文獻［10］算法小，但大于3D-DV-Hop 算法，因為本文算法添加了修正因子和智能優化算法導致運算量加大，計算開銷略有增加，但是定位精度明顯提升。

表3 3 種算法的平均運行時間

5 結束語

本文考慮了3D-DV-Hop定位算法孤立點的存在，以及利用錨節點的平均跳距估算到未知節點之間的距離時誤差較大的問題。提出了一種基于WBOA 的3D-DV-Hop 節點定位算法。該算法首先去除了網絡中可能存在的孤立點，然后重新計算節點個數以及節點間的距離與跳數，之后對錨節點的平均跳距進行了修正，接下來利用自適應權重平衡全局搜索與局部搜索能力，使算法不易陷入局部最優，加快了算法的收斂精度，得到全局最優平均跳距。從定位精度來看，本文改進的算法明顯優于傳統定位算法，具有較好的實用價值。未來3D-DV-Hop定位可能的研究熱點是移動網絡、不規則拓撲網絡和基于多目標優化模型的定位算法。