基于WBOA的3D-DV-Hop節(jié)點(diǎn)定位算法*

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

（1.蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050；2.蘭州理工大學(xué)理學(xué)院，甘肅 蘭州 730050）

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）［1］的節(jié)點(diǎn)用來(lái)感知、采集、處理網(wǎng)絡(luò)分布比較危險(xiǎn)復(fù)雜區(qū)域內(nèi)的檢測(cè)對(duì)象的位置及其信息，所以，節(jié)點(diǎn)定位成為WSNs的關(guān)鍵問(wèn)題之一，也是該領(lǐng)域的研究熱點(diǎn)［2］。而這些危險(xiǎn)復(fù)雜區(qū)域的地貌通常都是三維（3D）的，因此，3D節(jié)點(diǎn)定位至今仍是研究熱點(diǎn)［3］。

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

為了更加擬合現(xiàn)實(shí)環(huán)境狀況，網(wǎng)絡(luò)節(jié)點(diǎn)分布變得比較隨機(jī)，可能會(huì)出現(xiàn)某一節(jié)點(diǎn)在其他節(jié)點(diǎn)的通信范圍之外，導(dǎo)致此節(jié)點(diǎn)無(wú)法與其他節(jié)點(diǎn)通信或者無(wú)法定位，（后文將這些節(jié)點(diǎn)統(tǒng)稱為孤立點(diǎn)，在3.1 節(jié)說(shuō)明），將這些節(jié)點(diǎn)去除。對(duì)于由平均跳距估算距離時(shí)出現(xiàn)誤差較大的問(wèn)題，本文首先利用修正因子修正平均跳距，然后利用修正的平均跳距估算的距離與實(shí)際距離的差值函數(shù)作為目標(biāo)函數(shù)，用自適應(yīng)權(quán)重改進(jìn)后的蝴蝶優(yōu)化算法（butterfly optimization algorithm，BOA）求得全局最優(yōu)平均跳距。

1 3D-DV-Hop定位算法

1.1 3D-DV-Hop算法步驟

3D-DV-Hop 定位算法是二維DV-Hop 定位算法［11］的擴(kuò)展，是一種距離無(wú)關(guān)的定位算法，其算法主要有3 個(gè)階段：

步驟1 計(jì)算錨節(jié)點(diǎn)與每個(gè)未知節(jié)點(diǎn)的最小跳數(shù)

所有錨節(jié)點(diǎn)以多跳的方式向網(wǎng)絡(luò)中廣播自身數(shù)據(jù)包，信息發(fā)出的錨節(jié)點(diǎn)的跳數(shù)為0，數(shù)據(jù)包每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，跳數(shù)加1，當(dāng)一個(gè)節(jié)點(diǎn)收到多個(gè)跳數(shù)信息時(shí)，保存跳數(shù)值最小的一條信息。

步驟2 計(jì)算錨節(jié)點(diǎn)的平均每跳距離

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

式中 （xi，yi，zi）和（xj，yj，zj）為錨節(jié)點(diǎn)i和j的坐標(biāo)，hopi，j為錨節(jié)點(diǎn)i到錨節(jié)點(diǎn)j的跳數(shù)，hopsizei為錨節(jié)點(diǎn)i的平均跳距。

步驟3 利用極大似然估計(jì)法計(jì)算自身坐標(biāo)

未知節(jié)點(diǎn)通過(guò)式（2）計(jì)算它和錨節(jié)點(diǎn)之間的距離Di，j，然后根據(jù)最小二乘法就能得到未知節(jié)點(diǎn)的坐標(biāo)

式中Di，j為錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)j之間的距離，hopi，j為錨節(jié)點(diǎn)i和未知節(jié)點(diǎn)j之間的最小跳數(shù)。

1.2 DV-Hop算法的誤差分析

由于網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性，當(dāng)網(wǎng)絡(luò)區(qū)域大，節(jié)點(diǎn)數(shù)少或通信半徑短時(shí)，網(wǎng)絡(luò)中會(huì)出現(xiàn)一些孤立點(diǎn)，導(dǎo)致實(shí)驗(yàn)不能有效進(jìn)行，且離錨節(jié)點(diǎn)距離越遠(yuǎn)的未知節(jié)點(diǎn)累積的誤差越大。

利用極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)坐標(biāo)時(shí)，需要知道錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的估計(jì)距離，由于兩節(jié)點(diǎn)之間的跳距往往并不相等，利用錨節(jié)點(diǎn)的平均跳距估算距離時(shí)也會(huì)產(chǎn)生較大的誤差。

2 BOA

根據(jù)蝴蝶的覓食行為，提出了一種新的全局優(yōu)化元啟發(fā)式算法--BOA［12］。BOA模仿蝴蝶覓食這種行為來(lái)尋找超搜索空間中的最優(yōu)解。

蝴蝶的自然現(xiàn)象受變量I和對(duì)香味感知度f(wàn)的影響，算法的變量I與目標(biāo)函數(shù)相關(guān)聯(lián)。在BOA中，香味是物理刺激強(qiáng)度的函數(shù)，公式如下

式中f為對(duì)香味的感知程度，即其他蝴蝶對(duì)香味的感知程度，c為感覺(jué)模態(tài)，I為刺激強(qiáng)度，a為與模態(tài)有關(guān)的冪指數(shù)，反映了不同的吸收程度，a和c的取值范圍為［0，1］。

該算法有2個(gè)關(guān)鍵的階段：全局搜索階段與局部搜索階段。在全局搜索階段，蝴蝶朝著香味最濃的方向移動(dòng)，即向最優(yōu)的蝴蝶g*靠近?？梢杂檬剑?）來(lái)表示

式中為迭代次數(shù)為t的蝴蝶的解向量。g*為當(dāng)前迭代中所有解中找到的當(dāng)前最佳解，r為（0，1）中的隨機(jī)數(shù)。

局部搜索階段可以表示為

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

3 3D-DV-Hop定位算法

3.1 去除孤立點(diǎn)

在該算法中，如果某一節(jié)點(diǎn)到與其他超過(guò)總節(jié)點(diǎn)數(shù)50%節(jié)點(diǎn)的跳數(shù)的返回值為無(wú)窮大，那么稱這個(gè)節(jié)點(diǎn)為孤立點(diǎn)。去除孤立點(diǎn)的過(guò)程如下：

1）節(jié)點(diǎn)i與a個(gè)節(jié)點(diǎn)不能通信，判斷a是否大于總節(jié)點(diǎn)數(shù)的50%；

2）若是，則將節(jié)點(diǎn)i確定為孤立點(diǎn)，并分別記錄錨節(jié)點(diǎn)與未知節(jié)點(diǎn)中存在的孤立點(diǎn)個(gè)數(shù)；

3）從錨節(jié)點(diǎn)和未知節(jié)點(diǎn)中去除這些孤立點(diǎn)，然后重新初始化節(jié)點(diǎn)個(gè)數(shù)及節(jié)點(diǎn)間的距離與跳數(shù)。

3.2 修正平均每跳距離

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

改進(jìn)步驟如下：

步驟1 根據(jù)式（1）求得每個(gè)錨節(jié)點(diǎn)的每跳平均距離hopsizei，則2個(gè)錨節(jié)點(diǎn)i，j之間的估計(jì)距離Dij為

步驟2 錨節(jié)點(diǎn)i，j之間的實(shí)際距離可以由其坐標(biāo)計(jì)算得到

步驟3 根據(jù)式（6）和式（7），錨節(jié)點(diǎn)i，j之間的距離誤差dij可表示為

步驟4 根據(jù)距離誤差dij計(jì)算錨節(jié)點(diǎn)i的修正因子

ci為

此時(shí)，錨節(jié)點(diǎn)i的平均每跳距離hopsizei可表示為

步驟5 利用修正后的平均跳距計(jì)算錨節(jié)點(diǎn)i，j之間的估計(jì)距離D公式為

3.3 求取最優(yōu)平均跳距

求取最優(yōu)平均跳距分為3個(gè)步驟：

步驟1 初始化階段，算法定義目標(biāo)函數(shù)及其解空間，為BOA中使用的參數(shù)賦值，創(chuàng)建一個(gè)用于優(yōu)化的蝴蝶初始種群。

設(shè)錨節(jié)點(diǎn)i對(duì)應(yīng)的平均跳距為hopsizei，ε為平均跳距引起的誤差，合理的hopsizei應(yīng)使ε最小，由式（7）和式（11）可得

由此，可知適應(yīng)度函數(shù)如下

使用式（3）計(jì)算蝴蝶的香味。在求解最優(yōu)平均跳距hopsizei時(shí)，在搜索空間中隨機(jī)生成蝴蝶的位置，計(jì)算并存儲(chǔ)它們的香味值和適應(yīng)度值。

步驟2 迭代階段，由算法進(jìn)行多次迭代。

基本的BOA 存在收斂精度較低，全局搜索能力不足，容易陷入局部最優(yōu)的缺陷。受文獻(xiàn)［13］的啟發(fā)，為了平衡全局搜索與局部搜索的能力，算法采用自適應(yīng)權(quán)重處理的方法。

當(dāng)權(quán)重比較大時(shí)，算法的全局搜索能力較強(qiáng)，可以搜索較大的區(qū)域；當(dāng)權(quán)重比較小時(shí)，算法的局部搜索能力較強(qiáng)。采用如式（14）所示的權(quán)重因子對(duì)全局搜索階段進(jìn)行加權(quán)，使得算法易跳出局部最優(yōu)，提高了算法的全局搜索能力

改進(jìn)后的全局搜索階段如式（15）所示

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

改進(jìn)后的局部搜索階段如式（17）所示

由開(kāi)關(guān)概率p判斷算法是進(jìn)行全局搜索還是局部搜索，若r＜p，則算法進(jìn)行全局搜索，由式（15）來(lái)尋優(yōu)，若r≥p，則算法進(jìn)行局部搜索，由式（17）來(lái)尋優(yōu)。然后判斷尋找的最優(yōu)值是否在所設(shè)特定條件之內(nèi)發(fā)生，若是，更新最優(yōu)解，算法更新感覺(jué)模態(tài)c，進(jìn)行下次迭代，直到達(dá)到最大迭代次數(shù)，算法停止。

步驟3 當(dāng)?shù)A段結(jié)束時(shí)，算法輸出找到具有最佳適應(yīng)度的hopsizei的最佳解。

在該算法中，將利用自適應(yīng)權(quán)重因子改進(jìn)的BOA命名為WBOA（weighted BOA）。

3.4 利用極大似然估計(jì)法計(jì)算自身坐標(biāo)

未知節(jié)點(diǎn)接收到改進(jìn)后的最優(yōu)平均每跳距離，通過(guò)式（2）計(jì)算它和錨節(jié)點(diǎn)之間的距離Di，j，然后根據(jù)極大似然估計(jì)法能得到未知節(jié)點(diǎn)的坐標(biāo)。該算法的流程如圖1 所示。

圖1 算法流程

4 算法仿真與結(jié)果分析

4.1 WBOA的優(yōu)化性能分析

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

算法的尋優(yōu)質(zhì)量由最優(yōu)值和最差值反映，從表1 數(shù)據(jù)中可知，對(duì)求解函數(shù)f時(shí)，WBOA 能尋到理論最優(yōu)值0，說(shuō)明，在求解此類函數(shù)，WBOA 的尋優(yōu)性能最強(qiáng)，明顯優(yōu)于BOA、WOA、FPA。

表1 測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果比較

為了直觀展現(xiàn)WBOA的尋優(yōu)性能，本文給出測(cè)試函數(shù)的收斂曲線，如圖2 所示。由函數(shù)的收斂曲線可以直觀地看出改進(jìn)后的算法WBOA的收斂精度更高，解決了基本算法BOA尋優(yōu)精度不高的問(wèn)題。

圖2 收斂曲線

4.2 基于WBOA的3D-DV-Hop算法參數(shù)設(shè)置

為了驗(yàn)證本文算法的定位性能，利用MATLAB 2018a對(duì)基于WBOA的3D-DV-Hop、3D-DV-Hop算法和文獻(xiàn)［10］中提出的算法，從錨節(jié)點(diǎn)個(gè)數(shù)、通信半徑大小和總節(jié)點(diǎn)個(gè)數(shù)等3個(gè)方面進(jìn)行仿真實(shí)驗(yàn)分析。在100 m ×100 m ×100 m的仿真區(qū)域內(nèi)，隨機(jī)產(chǎn)生一定數(shù)量的網(wǎng)絡(luò)節(jié)點(diǎn)。算法的參數(shù)設(shè)置如表2所示。

表2 基于WBOA的3D-DV-Hop算法相關(guān)參數(shù)設(shè)置

網(wǎng)絡(luò)的平均定位誤差計(jì)算公式如下

式中 （xi，yi，zi）與（x′i，y′i，z′i）為未知節(jié)點(diǎn)i的實(shí)際坐標(biāo)和估計(jì)坐標(biāo)，R為錨節(jié)點(diǎn)的通信半徑，N為未知節(jié)點(diǎn)的總數(shù)。

4.3 仿真實(shí)驗(yàn)分析

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

圖3 錨節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

圖4 是節(jié)點(diǎn)總數(shù)為100，網(wǎng)絡(luò)通信半徑為40 m時(shí)，錨節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)平均定位誤差的影響，與圖3 相比，通信半徑增大，3種定位算法的平均定位誤差都有了不同程度的下降，是因?yàn)殡S著跳數(shù)的增加，未知節(jié)點(diǎn)的累積誤差也會(huì)增大，而通信半徑增大時(shí)，節(jié)點(diǎn)間的跳數(shù)隨之減少，則未知節(jié)點(diǎn)的定位誤差也隨之降低。由圖4 可知，在相同的條件下，基于WBOA的3D-DV-Hop算法的平均定位誤差一直都最小，對(duì)比于文獻(xiàn)［10］來(lái)說(shuō)，平均定位誤差降低了1%左右。3種算法的平均定位誤差隨著錨節(jié)點(diǎn)的增多穩(wěn)定下降，這是因?yàn)榫W(wǎng)絡(luò)區(qū)域小，錨節(jié)點(diǎn)數(shù)增多，通信半徑大，誤差波動(dòng)相對(duì)穩(wěn)定。

圖4 不同通信半徑下錨節(jié)點(diǎn)數(shù)對(duì)平均定位誤差的影響

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

圖5 節(jié)點(diǎn)總數(shù)對(duì)平均定位誤差的影響

4.4 算法的時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度反應(yīng)了算法執(zhí)行的時(shí)間長(zhǎng)短。算法中所涉及的網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模大小與節(jié)點(diǎn)總數(shù)n相關(guān)，錨節(jié)點(diǎn)的數(shù)為m。則3D-DV-Hop算法的時(shí)間復(fù)雜度為O（n3）；文獻(xiàn)［10］算法在3D-DV-Hop 算法的基礎(chǔ)上增加的時(shí)間復(fù)雜度為O（n（n-m）2）；本文算法在3D-DV-Hop算法的基礎(chǔ)上增加的時(shí)間復(fù)雜度為O（n×m），由此可知：本文算法相比較文獻(xiàn)［10］算法時(shí)間復(fù)雜度略小一些。

4.5 計(jì)算開(kāi)銷分析

將算法的平均運(yùn)行時(shí)間作為算法開(kāi)銷指標(biāo)進(jìn)行分析。表3為相同實(shí)驗(yàn)條件下所統(tǒng)計(jì)的3 種算法的平均運(yùn)行時(shí)間。由實(shí)驗(yàn)結(jié)果可知：本文算法的平均運(yùn)行時(shí)間比文獻(xiàn)［10］算法小，但大于3D-DV-Hop 算法，因?yàn)楸疚乃惴ㄌ砑恿诵拚蜃雍椭悄軆?yōu)化算法導(dǎo)致運(yùn)算量加大，計(jì)算開(kāi)銷略有增加，但是定位精度明顯提升。

表3 3 種算法的平均運(yùn)行時(shí)間

5 結(jié)束語(yǔ)

本文考慮了3D-DV-Hop定位算法孤立點(diǎn)的存在，以及利用錨節(jié)點(diǎn)的平均跳距估算到未知節(jié)點(diǎn)之間的距離時(shí)誤差較大的問(wèn)題。提出了一種基于WBOA 的3D-DV-Hop 節(jié)點(diǎn)定位算法。該算法首先去除了網(wǎng)絡(luò)中可能存在的孤立點(diǎn)，然后重新計(jì)算節(jié)點(diǎn)個(gè)數(shù)以及節(jié)點(diǎn)間的距離與跳數(shù)，之后對(duì)錨節(jié)點(diǎn)的平均跳距進(jìn)行了修正，接下來(lái)利用自適應(yīng)權(quán)重平衡全局搜索與局部搜索能力，使算法不易陷入局部最優(yōu)，加快了算法的收斂精度，得到全局最優(yōu)平均跳距。從定位精度來(lái)看，本文改進(jìn)的算法明顯優(yōu)于傳統(tǒng)定位算法，具有較好的實(shí)用價(jià)值。未來(lái)3D-DV-Hop定位可能的研究熱點(diǎn)是移動(dòng)網(wǎng)絡(luò)、不規(guī)則拓?fù)渚W(wǎng)絡(luò)和基于多目標(biāo)優(yōu)化模型的定位算法。