基于改進(jìn)蝴蝶優(yōu)化的DV-Hop定位算法*

葉 帥，余修武，劉 永

（南華大學(xué)，湖南 衡陽 421001）

0 引言

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

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

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

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

1 相關(guān)理論

1.1 DV-Hop算法

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

（1）獲得最小跳數(shù)。所有的信標(biāo)節(jié)點(diǎn)廣播的信息中包括坐標(biāo)信息和跳數(shù)的數(shù)據(jù)分組，初始化跳數(shù)為0。如果信標(biāo)節(jié)點(diǎn)跳數(shù)小于前一個(gè)值，則更新并保存該最小值。根據(jù)此機(jī)制，在廣播結(jié)束后，所有信標(biāo)節(jié)點(diǎn)獲得最小跳數(shù)。

（2）估計(jì)平均跳距。由第一階段獲得的任意兩個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)信息以及最小跳數(shù)計(jì)算得到平均跳距為：

式中：(xi,xj)，(yi,yj)為信標(biāo)節(jié)點(diǎn)i，j的坐標(biāo)；hij為信標(biāo)節(jié)點(diǎn)i和j(j≠i)之間的跳數(shù)。

每個(gè)未知節(jié)點(diǎn)通過第二階段獲得的平均跳距乘以最小跳數(shù)得出到各信標(biāo)節(jié)點(diǎn)之間的距離，其計(jì)算公式為：

式中：di為未知節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)的估計(jì)距離；hni為未知節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

（3）計(jì)算未知節(jié)點(diǎn)坐標(biāo)。當(dāng)信標(biāo)節(jié)點(diǎn)數(shù)大于或者等于3時(shí)，使用最小二乘法估計(jì)目標(biāo)節(jié)點(diǎn)位置。

設(shè)目標(biāo)節(jié)點(diǎn)的坐標(biāo)為(x,y)，信標(biāo)節(jié)點(diǎn)的坐標(biāo)為(xi,xj)(i=1,2,…,n)，根據(jù)距離公式可得目標(biāo)節(jié)點(diǎn)與各個(gè)信標(biāo)節(jié)點(diǎn)間的距離關(guān)系為：

用向量表示為：

根據(jù)最小二乘法可得目標(biāo)節(jié)點(diǎn)的坐標(biāo)：

1.2 蝴蝶優(yōu)化算法

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

在BOA中，蝴蝶的香味強(qiáng)度f與所受刺激強(qiáng)度I有關(guān)。香味強(qiáng)度的計(jì)算公式為：

式中：c表示感官模態(tài)；a表示香味強(qiáng)度衰減指數(shù)。

蝴蝶優(yōu)化算法在初始化階段定義目標(biāo)函數(shù)和解空間，并對(duì)算法中的相關(guān)參數(shù)賦值，然后在解空間中隨機(jī)生成蝴蝶的位置，并根據(jù)目標(biāo)函數(shù)和式（9）計(jì)算每只蝴蝶的香味強(qiáng)度。迭代過程中，蝴蝶種群會(huì)隨機(jī)移動(dòng)或者向著全局最優(yōu)的蝴蝶移動(dòng)。若處于全局搜索階段，其位置更新公式為：

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

2 改進(jìn)蝴蝶優(yōu)化的DV-Hop算法

2.1 DV-Hop算法優(yōu)化

2.1.1 跳數(shù)的改進(jìn)

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

圖1 多通信半徑圖示

隨著廣播次數(shù)增加，信標(biāo)節(jié)點(diǎn)所消耗的能量也隨之加大?？紤]到無線傳感器節(jié)點(diǎn)能量的有限性，設(shè)定信標(biāo)節(jié)點(diǎn)的廣播半徑為0.25R，0.5R，0.75R和R。

2.1.2 跳距的改進(jìn)

（1）信標(biāo)節(jié)點(diǎn)跳距的改進(jìn)

為了減小信標(biāo)節(jié)點(diǎn)平均跳距誤差對(duì)定位結(jié)果的影響，本文引入修正因子ei優(yōu)化信標(biāo)節(jié)點(diǎn)的平均跳距。修正因子的計(jì)算公式為：

式中：dij為信標(biāo)節(jié)點(diǎn)間的實(shí)際距離；為信標(biāo)節(jié)點(diǎn)間的估計(jì)距離。

優(yōu)化后的平均跳距表達(dá)式為：

（2）未知節(jié)點(diǎn)跳距的改進(jìn)

由于現(xiàn)實(shí)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)都是隨機(jī)分布的，未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離不盡相同，從而導(dǎo)致較大誤差。因此，本文根據(jù)每個(gè)信標(biāo)節(jié)點(diǎn)的跳數(shù)信息引入權(quán)重因子wi，從而改進(jìn)未知節(jié)點(diǎn)的平均跳距。假設(shè)未知節(jié)點(diǎn)m接收到n個(gè)信標(biāo)節(jié)點(diǎn)的平均跳距，權(quán)重因子wi的表達(dá)式為：

式中：hmi為未知節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)m的最小跳數(shù)。

未知節(jié)點(diǎn)的平均跳距為：

2.2 基于改進(jìn)蝴蝶算法的定位優(yōu)化

2.2.1 佳點(diǎn)集初始化種群

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

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

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

假設(shè)種群規(guī)模為100、空間維度為2。圖2和圖3分別表示隨機(jī)分布和佳點(diǎn)集初始化的種群，可以看出由佳點(diǎn)集初始化的種群分布更加均勻，覆蓋更加充分。x,y分別表示節(jié)點(diǎn)對(duì)應(yīng)的橫、縱坐標(biāo)。

圖2 隨機(jī)初始化種群分布

圖3 佳點(diǎn)集初始化種群分布

2.2.2 動(dòng)態(tài)切換概率策略

p用于全局搜索和局部探索的切換。標(biāo)準(zhǔn)的BOA中的p是一個(gè)固定的值[14]，在算法的后期搜索最優(yōu)個(gè)體的能力弱，易陷入局部最優(yōu)，因此本文采用動(dòng)態(tài)轉(zhuǎn)換概率來實(shí)現(xiàn)全局搜索和局部搜索的轉(zhuǎn)換，從而提高算法后期的尋優(yōu)能力，更好平衡全局搜索和局部搜索。轉(zhuǎn)換概率公式為：

式中：i，N_iter分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

2.2.3 全局?jǐn)_動(dòng)因子

為了進(jìn)一步加強(qiáng)算法的探索能力和提高收斂精度，受到正態(tài)分布的啟發(fā)，在傳統(tǒng)全局位置更新處引入全局?jǐn)_動(dòng)因子Ψ，其表達(dá)式為：

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

2.2.4 黃金正弦搜索策略

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

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

式中：r1為區(qū)間[0,2π]中的隨機(jī)數(shù)；r2為區(qū)間[0,π]中的隨機(jī)數(shù)。θ1和θ2的表達(dá)式為：

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

2.3 改進(jìn)DV-Hop算法流程

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

（1）在無線傳感器網(wǎng)絡(luò)中隨機(jī)分布若干個(gè)節(jié)點(diǎn)，根據(jù)改進(jìn)的DV-Hop算法得到最小跳數(shù)以及節(jié)點(diǎn)間的最優(yōu)跳距。

（2）運(yùn)用佳點(diǎn)集初始化種群，并設(shè)置迭代次數(shù)、蝴蝶種群數(shù)量、官能模態(tài)以及刺激強(qiáng)度等相關(guān)參數(shù)。

（3）根據(jù)目標(biāo)函數(shù)計(jì)算種群的適應(yīng)度值，并記錄最佳的適應(yīng)度值以及所對(duì)應(yīng)個(gè)體的位置。

（4）根據(jù)式（21）和式（22）對(duì)個(gè)體位置進(jìn)行更新，并且記錄每次更新之后最佳個(gè)體的適應(yīng)度值以及所對(duì)應(yīng)的位置。

（5）如果滿足迭代終止條件，則終止算法執(zhí)行并且輸出全局最優(yōu)解以及相對(duì)應(yīng)的位置，否則返回步驟4繼續(xù)進(jìn)行迭代優(yōu)化。

3 仿真分析

為了驗(yàn)證本文所提出IBOA算法的有效性，利用MATLAB 2018a進(jìn)行了仿真實(shí)驗(yàn)，并與傳統(tǒng)的DVHop算法和文獻(xiàn)[16]算法進(jìn)行比較。如圖4所示，設(shè)在100 m×100 m的方形區(qū)域內(nèi)隨機(jī)部署100個(gè)傳感器節(jié)點(diǎn)，其中信標(biāo)節(jié)點(diǎn)20個(gè)。為了增加實(shí)驗(yàn)結(jié)果的準(zhǔn)確度，實(shí)驗(yàn)選取模擬50次的平均值作為最終的結(jié)果。

圖4 網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署

本文通過依次改變信標(biāo)節(jié)點(diǎn)比例、節(jié)點(diǎn)通信半徑以及節(jié)點(diǎn)總數(shù)來驗(yàn)證提出算法的性能，并且采用歸一化相對(duì)誤差作為定位算法的評(píng)價(jià)標(biāo)準(zhǔn)。其計(jì)算公式為：

3.1 信標(biāo)節(jié)點(diǎn)比例對(duì)定位精度的影響

在網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)布設(shè)100個(gè)節(jié)點(diǎn)，保持通信半徑R=20 m不變，信標(biāo)節(jié)點(diǎn)的比例從5%變換至25%，對(duì)比3種算法，結(jié)果如圖5所示。

圖5 信標(biāo)節(jié)點(diǎn)比例對(duì)定位精度的影響對(duì)比

3種算法的平均定位誤差總體上均隨著信標(biāo)節(jié)點(diǎn)比例增大而減小，其中改進(jìn)算法定位誤差明顯要低于另外兩種對(duì)比算法。在信標(biāo)節(jié)點(diǎn)比例較小時(shí)，定位誤差曲線下降的幅度較大。信標(biāo)節(jié)點(diǎn)比例增加到15%之后，曲線趨于平穩(wěn)。在不同信標(biāo)節(jié)點(diǎn)比例下，本文改進(jìn)算法的平均定位精度相比傳統(tǒng)DV-Hop算法和文獻(xiàn)[16]算法分別提高了23.51%和4.7%。

3.2 通信半徑對(duì)定位精度的影響

在網(wǎng)絡(luò)區(qū)域隨機(jī)分布100個(gè)節(jié)點(diǎn)，其中信標(biāo)節(jié)點(diǎn)個(gè)數(shù)為10，通信半徑R從20 m依次增加到40 m。對(duì)比3種算法，結(jié)果如圖6所示。

圖6 通信半徑對(duì)定位精度的影響對(duì)比

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

3.3 節(jié)點(diǎn)總數(shù)對(duì)定位精度的影響

在網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)分布10個(gè)信標(biāo)節(jié)點(diǎn)，保持通信半徑R=20 m不變，節(jié)點(diǎn)總數(shù)從60增加到100，對(duì)比3種算法，結(jié)果如圖7所示。

圖7 節(jié)點(diǎn)總數(shù)對(duì)定位精度的影響對(duì)比

3種定位算法的定位誤差總體隨著節(jié)點(diǎn)總數(shù)的增加而逐漸減小。當(dāng)節(jié)點(diǎn)總數(shù)較小時(shí)，定位誤差下降幅度較大，當(dāng)總數(shù)達(dá)到90以后，曲線開始趨于平穩(wěn)。在不同的節(jié)點(diǎn)總數(shù)下，本文改進(jìn)算法平均定位精度相比傳統(tǒng)DV-Hop算法和文獻(xiàn)[16]算法分別提高了30.35%和12.10%。

4 結(jié)語

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