張孟健，汪 敏，王 霄,2，覃 濤,2,楊 靖,2

(1.貴州大學(xué)電氣工程學(xué)院,貴州 貴陽 550025;2.貴州省“互聯(lián)網(wǎng)+”協(xié)同智能制造重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025)

1 引言

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)由大量能量有限的傳感器節(jié)點(diǎn)組成[1]，通過節(jié)點(diǎn)之間的相互協(xié)作，處理感知對象的檢測數(shù)據(jù)，并向用戶提供精確、全面的實(shí)時(shí)數(shù)據(jù)。目前，WSN已廣泛應(yīng)用在軍事、交通和環(huán)境監(jiān)測等領(lǐng)域[2]。覆蓋率反映了傳感器網(wǎng)絡(luò)提供的感知服務(wù)質(zhì)量，亦是評價(jià)傳感器網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)。如何提高覆蓋率是WSN研究領(lǐng)域的關(guān)鍵問題之一。

在WSN中合理部署傳感器節(jié)點(diǎn)，可以有效提高網(wǎng)絡(luò)的覆蓋率。針對WSN中的部署問題，Zou等[3]首次提出了一種虛擬力算法用于傳感器節(jié)點(diǎn)的目標(biāo)部署；李翠然等[4]對虛擬力算法進(jìn)行改進(jìn)，提出了一種優(yōu)化的虛擬力節(jié)點(diǎn)部署算法。隨著群體智能優(yōu)化算法的涌現(xiàn)，如粒子群優(yōu)化算法PSO(Particle Swarm Optimization)[5]、灰狼優(yōu)化算法GWO(Grey Wolf Optimizer)[6]、蝴蝶優(yōu)化算法BOA(Butterfly Optimization Algorithm)[7]等，目前已有很多智能優(yōu)化算法用于優(yōu)化WSN的節(jié)點(diǎn)部署。Wang等[8]提出一種改進(jìn)的協(xié)同進(jìn)化粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略；楊永建等[9]提出基于改進(jìn)PSO算法的傳感器網(wǎng)絡(luò)覆蓋優(yōu)化；胡小平等[10]提出了一種改進(jìn)灰狼優(yōu)化算法用于WSN節(jié)點(diǎn)部署，以解決傳感器節(jié)點(diǎn)的確定性覆蓋問題；宋婷婷等[11]提出了基于改進(jìn)鯨魚優(yōu)化算法的WSN覆蓋優(yōu)化，以提高被監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋率?，F(xiàn)有的研究表明，將新型的優(yōu)化算法、改進(jìn)的智能優(yōu)化算法用于節(jié)點(diǎn)部署具有一定的價(jià)值及意義。

蝴蝶優(yōu)化算法是Arora和Singh提出的一種新型群體智能算法，已應(yīng)用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題[12]、小波神經(jīng)網(wǎng)絡(luò)的優(yōu)化訓(xùn)練[13]等，但BOA存在易陷入局部最優(yōu)、收斂精度低等不足。鑒于PSO算法具有收斂速度快的優(yōu)勢，同時(shí)BOA具有結(jié)構(gòu)簡單、調(diào)節(jié)參數(shù)少等優(yōu)勢，Zhang等[14]提出了一種混合混沌映射的混合粒子群蝴蝶優(yōu)化算法HPSOBOA(chaotic Hybrid Butterfly Optimization Algorithm with Particle Swarm Optimization)以求解高維優(yōu)化問題，但該算法對工程優(yōu)化問題的求解結(jié)果不佳。

本文對HPSOBOA進(jìn)行改進(jìn)，并將其用于WSN的部署優(yōu)化，以提高網(wǎng)絡(luò)覆蓋率。本文主要工作包括：(1) 結(jié)合PSO算法和BOA的優(yōu)點(diǎn)，提出了一種混合粒子群-蝴蝶算法HPSBA(Hybrid Particle Swarm-Butterfly Algorithm)；(2) 設(shè)計(jì)了基于Logistic映射和自適應(yīng)調(diào)節(jié)的策略，用于分別調(diào)節(jié)控制參數(shù)c和ω，以提高混合算法的尋優(yōu)速度、收斂精度和全局搜索能力；(3) 通過4個(gè)基準(zhǔn)測試函數(shù)驗(yàn)證算法的性能，并將尋優(yōu)的結(jié)果與6種智能優(yōu)化算法進(jìn)行對比；(4) 將提出的混合算法用于WSN節(jié)點(diǎn)部署問題。

2 節(jié)點(diǎn)覆蓋模型

對于WSN中的二維點(diǎn)覆蓋問題[1]，假設(shè)二維平面的部署區(qū)域中存在n個(gè)待覆蓋的監(jiān)測目標(biāo)點(diǎn)，部署的傳感器節(jié)點(diǎn)采用同構(gòu)的傳感器，即傳感器的感知半徑相同。設(shè)感知半徑為rs，通信半徑為rc，其單位為m,且2rs≤rc。

假設(shè)待覆蓋的區(qū)域內(nèi)有n個(gè)監(jiān)測目標(biāo)點(diǎn)，設(shè)第i個(gè)待監(jiān)測目標(biāo)點(diǎn)的位置坐標(biāo)為(xi,yi)，第s個(gè)傳感器節(jié)點(diǎn)的位置坐標(biāo)為(xs,ys)，則傳感器節(jié)點(diǎn)能夠覆蓋的待監(jiān)測目標(biāo)點(diǎn)的歐氏距離如式(11)所示：

(1)

待監(jiān)測目標(biāo)點(diǎn)i被傳感器節(jié)點(diǎn)s所覆蓋的概率p(i,s)[2]如式(2)所示:

(2)

將待部署的二維平面區(qū)域沿x,y軸以步長q等分化，則每段長度l=q，部署區(qū)域網(wǎng)格化的交點(diǎn)為q2。則在部署區(qū)域的監(jiān)測點(diǎn)集T被傳感器節(jié)點(diǎn)集Q感知的概率，即節(jié)點(diǎn)覆蓋率如式(3)所示：

(3)

其中節(jié)點(diǎn)集Q中的傳感器數(shù)量為S。

假設(shè)部署區(qū)域?yàn)檎叫?，邊長為L。理論上在設(shè)定的部署區(qū)域，部署節(jié)點(diǎn)的數(shù)量可以通過計(jì)算得到，節(jié)點(diǎn)全覆蓋部署的示意圖如圖1所示。

Figure 1 Node coverage diagram圖1 節(jié)點(diǎn)覆蓋示意圖

在圖1中，O1、O2、O3分別表示3個(gè)傳感器節(jié)點(diǎn)的位置，此時(shí)三角形O1O2O3為正三角形，O3A=rs即傳感器的感知半徑，∠AO3B=π/3，AB=BO3=O3A=rs，根據(jù)圓的性質(zhì)，則AB⊥O2O3，∠AO3C=1/2∠AO3B=π/6。由余弦定理可得，線段O3C的長度如式(4)所示：

LO3C=LO3A×cos(∠AO3C)=

(4)

則理論上部署區(qū)域的節(jié)點(diǎn)數(shù)量如式(5)所示：

(5)

根據(jù)上述分析，節(jié)點(diǎn)部署問題可簡化為約束的工程優(yōu)化問題，如式(6)所示：

maxf(x)=Cov,

(6)

3 混合粒子群-蝴蝶算法

3.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法[5]是模仿多維搜索空間中移動(dòng)的鳥群搜索食物的群體智能優(yōu)化算法。PSO算法尋優(yōu)的2個(gè)重要特征分別為：粒子的位置和速度。其中，粒子指每個(gè)個(gè)體，每個(gè)粒子在搜索空間的初始位置和速度采用隨機(jī)初始化。粒子的位置和速度更新如式(7)和式(8)所示：

(7)

(8)

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

蝴蝶優(yōu)化算法[7]中，每只蝴蝶均有各自獨(dú)特的氣味和感知能力，個(gè)體之間會(huì)產(chǎn)生不同的氣味感知強(qiáng)度。其中，個(gè)體的氣味被其他蝴蝶感知的強(qiáng)度如式(9)所示：

f(x)=cIa

(9)

其中，f(x)表示氣味強(qiáng)度函數(shù)；c表示感官形態(tài)系數(shù)；I表示刺激強(qiáng)度，即函數(shù)適應(yīng)度值；a表示強(qiáng)度系數(shù)，取值在[0,1]。

感官形態(tài)系數(shù)c在理論上可取[0,∞)內(nèi)任意值，其計(jì)算如式(10)所示：

ct+1=ct+[0.025/(ct·Tmax)]

(10)

其中，c的初值為0.01，Tmax為算法的最大迭代次數(shù)。BOA根據(jù)切換概率p決定算法的全局搜索和局部搜索，位置更新公式如式(11)所示：

(11)

3.3 混合算法

3.3.1 算法的種群初始化

設(shè)D維搜索空間中，隨機(jī)生成初始解的表達(dá)式如式(12)所示：

Xi=Lb+(Ub-Lb)·o

(12)

其中，Xi表示蝴蝶群體中第i只蝴蝶(i=1,2,3,…,N)的空間位置，N表示初始解的個(gè)數(shù)；Lb和Ub分別表示搜索空間的上界和下界；o表示元素為(0,1)的隨機(jī)數(shù)的矩陣。

3.3.2 算法的全局搜索

混合算法HPSBA的全局搜索階段可用式(13)和式(14)表示：

(13)

(14)

3.3.3 算法的局部搜索

混合算法HPSBA的局部搜索階段可用式(15)和式(16)表示：

(15)

(16)

3.3.4 控制策略

混沌理論在群智能優(yōu)化算法中有著較多的應(yīng)用研究，如混沌種群初始化、控制參數(shù)混沌調(diào)節(jié)策略等。Logistic映射[15]是混沌理論中的一個(gè)經(jīng)典的混沌映射方式，其表達(dá)式如式(17)所示：

zl+1=μzl(1-zl)

(17)

其中，l表示混沌映射的迭代次數(shù)；μ為混沌參數(shù)，其取值在[0,4]。Logistic映射的混沌序列為(0,1)，當(dāng)μ=4時(shí)，該映射會(huì)產(chǎn)生混沌現(xiàn)象。

李雅普諾夫(Lyapunov)指數(shù)[16]是判別混沌特性的一個(gè)重要指標(biāo)。若混沌映射的最大Lyapunov指數(shù)越大，其混沌特性越明顯、混沌程度越高。該指數(shù)表達(dá)式如式(18)所示：

(18)

其中，λ表示Lyapunov指數(shù)；f′(·)表示混沌映射函數(shù)的一階導(dǎo)數(shù)；nh表示混沌映射的迭代次數(shù)。

取參數(shù)μ∈(3,4]繪制分岔圖和Lyapunov指數(shù)曲線，如圖2所示。

Figure 2 Logistic mapping圖2 Logistic映射

從圖2a可知，Logistic映射在μ=3.55左右的位置進(jìn)行分岔，隨著參數(shù)取值的增加，映射的范圍逐漸增至(0,1)。當(dāng)μ=4時(shí)，Logistic映射的混沌序列為(0,1)，其對應(yīng)的最大Lyapunov指數(shù)為0.683 9。

HPSBA中感官形態(tài)系數(shù)c的表達(dá)式如式(19)所示：

c(t)=4·c(t-1)·(1-c(t-1))

(19)

慣性權(quán)重系數(shù)ω對PSO算法的粒子飛行速度有直接影響，能夠調(diào)整算法的全局搜索和局部搜索能力。本文采用自適應(yīng)的調(diào)整策略，如式(20)所示：

ω(t)=ωmax-((ωmax-ωmin)·Ti)/Tmax

(20)

其中，ωmax=0.9,ωmin=0.2,Tmax為算法的最大迭代次數(shù)。

針對控制參數(shù)c和ω，取Tmax=500，c(0)=0.35，迭代曲線如圖3所示，其中c0表示式(9)描述的控制策略，c表示Logistic映射的控制策略。由圖3可知，隨著迭代次數(shù)的增加，控制策略c0的參數(shù)變化在(0,0.3)；改進(jìn)的控制策略c的參數(shù)則在迭代次數(shù)內(nèi)的取值在(0,1)；自適應(yīng)的調(diào)整策略ω的參數(shù)由0.9線性遞減至0.2。改進(jìn)的控制策略能有效調(diào)節(jié)混合算法的局部搜索和全局搜索，進(jìn)而尋優(yōu)到最佳值。

Figure 3 Variation curve of control parameters圖3 控制參數(shù)的變化曲線

3.3.5 算法偽代碼

基于混合算法HPSBA節(jié)點(diǎn)部署的偽代碼如下所示：

Input：部署區(qū)域的范圍L×L，傳感器節(jié)點(diǎn)的感知半徑rs，通信半徑rc，部署傳感器節(jié)點(diǎn)數(shù)量S，種群數(shù)量N，參數(shù)c,a和ω的初始值，迭代次數(shù)Tmax。

Output：部署傳感器節(jié)點(diǎn)的位置和覆蓋率。

1：根據(jù)式(12)對節(jié)點(diǎn)的位置進(jìn)行初始化，計(jì)算初始覆蓋率;

2：根據(jù)覆蓋率確定初始粒子的最佳適應(yīng)度值和位置;

3：Fort=1:Tmaxdo

4：Fori=1:Ndo

5：Forj=1:Ndo

6：Ifp≥rand

7： 根據(jù)式(13)和式(14)更新節(jié)點(diǎn)的位置;

8：Else

9： 根據(jù)式(15)和式(16)更新節(jié)點(diǎn)的位置;

10：Endfor

11： 判斷節(jié)點(diǎn)的坐標(biāo)是否超出部署區(qū)域；

12：Endfor

13： 根據(jù)式(3)計(jì)算部署區(qū)域的節(jié)點(diǎn)覆蓋率;

14： 更新覆蓋率和選擇最佳的節(jié)點(diǎn)位置;

15： 根據(jù)式(19)和式(20)分別更新參數(shù)c和ω的值;

16：Endfor

17：輸出部署傳感器節(jié)點(diǎn)的位置和覆蓋率

3.3.6 復(fù)雜度分析

假設(shè)算法的種群個(gè)數(shù)為N，搜索空間維度為D，最大搜索次數(shù)為Tmax,則HPSBA的復(fù)雜度包括：種群的初始化復(fù)雜度O(ND)，適應(yīng)度值計(jì)算復(fù)雜度O(ND)，全局和局部搜索的位置更新復(fù)雜度O(N2logN)，算法的適應(yīng)度值排序復(fù)雜度O(N2)和算法的控制參數(shù)更新復(fù)雜度O(ND)。則HPSBA算法的復(fù)雜度如式(21)所示：

O(HPSBA)=O(ND)+

O(Tmax)O(ND+N2logN+N2+ND)

(21)

BOA的算法時(shí)間復(fù)雜度如式(22)所示：

O(BOA)=O(ND)+

O(Tmax)O(N2logN+N+ND)

(22)

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證HPSBA的尋優(yōu)性能及其有效性，本文設(shè)計(jì)了3組對比實(shí)驗(yàn)：(1)HPSBA與PSO算法[5]、GWO算法[6]、BOA[7]、LBOA[12]、IBOA[13]和HPSOBOA[14]共6種優(yōu)化算法進(jìn)行尋優(yōu)仿真對比；(2)基于PSO算法、BOA和HPSBA的3種節(jié)點(diǎn)部署算法對比；(3)與現(xiàn)有的其他節(jié)點(diǎn)部署算法(如GWO算法、IGWO算法、WOA和IWOA)的結(jié)果進(jìn)行比較。各算法的參數(shù)設(shè)置詳見表1。

Table 1 Parameter settings of comparison algorithms

尋優(yōu)實(shí)驗(yàn)的基準(zhǔn)測試函數(shù)[6]為：Sphere(F1)、Schwefel 2.22(F2)、Rastrigin(F3)、Griewank(F4)。4種基準(zhǔn)測試函數(shù)的理論最優(yōu)值均為0，其中，F(xiàn)1和F2為單峰函數(shù)，F(xiàn)3和F4為多峰函數(shù)，設(shè)尋優(yōu)精度為1.00E-30。為了更好地評價(jià)提出的改進(jìn)算法，本文用尋優(yōu)成功率(Success rate)作為評價(jià)指標(biāo)。實(shí)驗(yàn)的環(huán)境為：Windows 7操作系統(tǒng)，Intel(R) Core(TM) i5-10210U CPU @2.11 GHz，16 GB內(nèi)存，Matlab 2018a仿真平臺(tái)。

尋優(yōu)成功率：即尋優(yōu)成功次數(shù)占總測試次數(shù)的百分比。當(dāng)尋優(yōu)成功率小于設(shè)定的尋優(yōu)精度(ε< 1.00E-30)時(shí)，認(rèn)為尋優(yōu)成功;反之則認(rèn)為失敗。

根據(jù)式(5)計(jì)算理論上的部署區(qū)域所需的傳感器節(jié)點(diǎn)數(shù)量，設(shè)定的節(jié)點(diǎn)部署區(qū)域的實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。

Table 2 Parameter settings of node deployment

4.2 仿真結(jié)果分析

4.2.1 基準(zhǔn)測試函數(shù)尋優(yōu)對比

為了保證比較結(jié)果的合理性和公平性，設(shè)置對比算法的種群規(guī)模N=30，基準(zhǔn)測試函數(shù)的維度Dim=30，最大迭代次數(shù)Tmax=500。對于同一個(gè)用于驗(yàn)證的基準(zhǔn)測試函數(shù)，每種算法分別獨(dú)立運(yùn)行30次，根據(jù)統(tǒng)計(jì)值得出均值、標(biāo)準(zhǔn)差、尋優(yōu)成功率和尋優(yōu)時(shí)間。尋優(yōu)的對比結(jié)果如表3所示。

由表3可知，針對單峰基準(zhǔn)測試函數(shù)F1和F2的尋優(yōu)，HPSBA的尋優(yōu)均值和標(biāo)準(zhǔn)差均優(yōu)于其他算法的，且尋優(yōu)成功率均為100%；針對多峰基準(zhǔn)測試函數(shù)F3的尋優(yōu)，LBOA、IBOA、HPSOBOA與HPSBA都能夠達(dá)到同樣的尋優(yōu)精度，其中LBOA的尋優(yōu)時(shí)間最長；針對多峰基準(zhǔn)測試函數(shù)F4的尋優(yōu)，除IBOA和HPSOBOA外，HPSBA明顯優(yōu)于其他4種優(yōu)化算法，雖然GWO算法的尋優(yōu)成功率為80%，但其均值和方差分別為4.18E-03和9.48E-03，說明該算法的穩(wěn)定性較差。

Table 3 Comparison results of optimization algorithms

為了進(jìn)一步說明7種對比算法的收斂速度和收斂精度，4種基準(zhǔn)測試函數(shù)的尋優(yōu)過程曲線如圖4所示。圖4a和圖4b分別表示7種對比算法對單峰基準(zhǔn)測試函數(shù)的尋優(yōu)曲線，HPSBA明顯優(yōu)于其他6種優(yōu)化算法，且收斂速度較快、收斂精度較高。圖4c和圖4d分別表示7種對比算法對多峰基準(zhǔn)測試函數(shù)的尋優(yōu)曲線，HPSBA的收斂速度較快，且收斂精度較高。從函數(shù)F3的尋優(yōu)曲線可知，LBOA、IBOA、HPSOBOA和HPSBA的尋優(yōu)均能達(dá)到最優(yōu)值，但HPSBA的迭代次數(shù)較少，即尋優(yōu)的速度較快。

Figure 4 Convergence curves of comparative algorithms圖4 對比算法的尋優(yōu)曲線

4.2.2 節(jié)點(diǎn)數(shù)量對覆蓋率的影響

為驗(yàn)證HPSBA對WSN優(yōu)化節(jié)點(diǎn)覆蓋的效果，對監(jiān)測區(qū)域內(nèi)3種算法(BOA、PSO算法和HPSBA)在不同數(shù)量傳感器節(jié)點(diǎn)的覆蓋率進(jìn)行比較。在100 m × 100 m的正方形監(jiān)控區(qū)域內(nèi)部署傳感器節(jié)點(diǎn)，感知半徑為10 m，通信半徑為20 m，最大迭代次數(shù)為150；分別在傳感器節(jié)點(diǎn)數(shù)量為45，50和55的情況下用不同算法進(jìn)行10次獨(dú)立實(shí)驗(yàn)，記錄其平均值。圖5所示為當(dāng)傳感器節(jié)點(diǎn)數(shù)量為55，迭代次數(shù)為150時(shí)的部署仿真結(jié)果。其他參數(shù)不變，不同的部署策略下的覆蓋率隨節(jié)點(diǎn)數(shù)量變化的趨勢如圖6所示。

由圖 5 可知，傳感器節(jié)點(diǎn)數(shù)量為55時(shí)，初始的隨機(jī)部署如圖 5a所示，隨著HPSBA的迭代次數(shù)達(dá)到150次，節(jié)點(diǎn)的部署位置如圖5b所示。根據(jù)HPSBA優(yōu)化部署前后的傳感器節(jié)點(diǎn)坐標(biāo)位置，運(yùn)用最小生成樹Prim算法[17]繪制模擬部署區(qū)域的傳感器節(jié)點(diǎn)通信網(wǎng)絡(luò)，分別如圖5c和圖5d所示。

Figure 5 Comparison of node deployments圖5 節(jié)點(diǎn)部署對比

從圖5c和圖5d可知，初始部署的傳感器節(jié)點(diǎn)之間的通信距離均勻性較差，匯聚節(jié)點(diǎn)位于部署區(qū)域的中心位置，傳感器節(jié)點(diǎn)之間的數(shù)據(jù)傳輸距離較長，因此傳感器節(jié)點(diǎn)的耗能較大；而優(yōu)化后的傳感器節(jié)點(diǎn)之間的通信距離較為均勻,有多個(gè)匯聚節(jié)點(diǎn)，且位置位于邊界處，從而增強(qiáng)了網(wǎng)絡(luò)的可靠性，進(jìn)而降低了傳感器節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)暮哪?，延長了網(wǎng)絡(luò)的壽命。

由圖6可知，BOA的部署效果較差，HPSBA在迭代10次之后均處于領(lǐng)先位置。3種算法分別經(jīng)過150次迭代的最終覆蓋率分別為89.38%,97.86%和99.36%。

Figure 6 Comparison of coverage curves圖6 覆蓋率曲線對比

對于不同節(jié)點(diǎn)數(shù)量的無線傳感器網(wǎng)絡(luò)的覆蓋率變化如圖7所示。

Figure 7 Coverage of different numbers of nodes圖7 不同節(jié)點(diǎn)數(shù)量的覆蓋率對比

從圖7中可以看出，HPSBA部署策略在不同傳感器節(jié)點(diǎn)數(shù)量的無線傳感器網(wǎng)絡(luò)覆蓋率均優(yōu)于BOA和PSO算法的。

4.2.3 與其他算法對比

(1) 與改進(jìn)的GWO部署算法進(jìn)行對比。

為了保證與文獻(xiàn)[10]中方法對比的公平性，本節(jié)實(shí)驗(yàn)參數(shù)設(shè)置與文獻(xiàn)[10]中的相同，即設(shè)節(jié)點(diǎn)部署區(qū)域?yàn)?0 m×50 m的二維平面，傳感器節(jié)點(diǎn)個(gè)數(shù)N=40，其感知半徑rs=5 m，通信半徑rc=10 m，迭代次分別設(shè)為100次，150次和200次。表4為隨機(jī)部署、BOA、PSO算法、GWO算法、IGWO算法和HPSBA的覆蓋優(yōu)化結(jié)果。其中，“/”表示部署算法未給出。

由表4可知，迭代次數(shù)為100時(shí)，隨機(jī)部署的覆蓋率僅為74.85%，且傳感器節(jié)點(diǎn)的分布不均勻,存在冗余節(jié)點(diǎn)和覆蓋漏洞;采用BOA優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為80.79%，消耗的時(shí)間為10.30 s，節(jié)點(diǎn)分布較為均勻，覆蓋率仍有待提高；采用PSO算法優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為89.94%，消耗的時(shí)間為10.65 s，節(jié)點(diǎn)分布較為均勻，覆蓋率仍有待提高；采用HPSBA優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為93.51%，消耗的時(shí)間為10.44 s。相較于節(jié)點(diǎn)隨機(jī)部署策略、BOA和PSO算法，HPSBA節(jié)點(diǎn)覆蓋率分別提升了18.66個(gè)百分點(diǎn)，12.72個(gè)百分點(diǎn)和 3.57個(gè)百分點(diǎn)，且分布更均勻，覆蓋的漏洞也有所減少，近似實(shí)現(xiàn)區(qū)域完全覆蓋。

Table 4 Optimization results of different algorithms

與GWO算法和IGWO算法的部署結(jié)果相比，當(dāng)?shù)螖?shù)為100次時(shí)，HPSBA優(yōu)化后的覆蓋率優(yōu)于GWO算法的；雖然HPSBA比IGWO算法的優(yōu)化后覆蓋率稍低，但HPSBA的優(yōu)化部署耗時(shí)遠(yuǎn)遠(yuǎn)低于IGWO算法的。當(dāng)HPSBA優(yōu)化部署的迭代次數(shù)為150次時(shí)，其覆蓋率優(yōu)于IGWO算法的，且耗時(shí)亦遠(yuǎn)低于IGWO算法迭代100次的耗時(shí)。當(dāng)?shù)螖?shù)為200次時(shí)，HPSBA的覆蓋率為94.93%，優(yōu)化部署的耗時(shí)為20.68 s。

(2) 與改進(jìn)的WOA部署算法進(jìn)行對比。

為了保證與文獻(xiàn)[11]中方法對比的公平性，本節(jié)實(shí)驗(yàn)參數(shù)設(shè)置與文獻(xiàn)[11]中的相同，即設(shè)節(jié)點(diǎn)部署區(qū)域?yàn)?00 m×100 m的二維平面，傳感器節(jié)點(diǎn)個(gè)數(shù)N=50，其感知半徑rs=10 m，通信半徑rc=20 m，迭代次數(shù)分別設(shè)為150次，200次和1 000次。表5為隨機(jī)部署、BOA、PSO算法、WOA、IWOA和HPSBA的覆蓋優(yōu)化結(jié)果。其中，“/”表示部署算法中未給出。

Table 5 Optimization results of different algorithm

由表5可知，迭代次數(shù)為150時(shí)，隨機(jī)部署的覆蓋率僅為83.84%，且節(jié)點(diǎn)的分布不均勻，存在冗余節(jié)點(diǎn)和覆蓋漏洞；采用BOA優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為87.82%，消耗的時(shí)間為19.85 s，節(jié)點(diǎn)分布較為均勻，覆蓋率仍有待提高；采用PSO算法優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為96.45%，消耗的時(shí)間為20.38 s，節(jié)點(diǎn)分布較為均勻，覆蓋率仍有待提高；采用HPSBA優(yōu)化節(jié)點(diǎn)部署后，節(jié)點(diǎn)的覆蓋率為97.97%，消耗的時(shí)間為19.47 s。相較于節(jié)點(diǎn)隨機(jī)部署策略、BOA和PSO算法，HPSBA節(jié)點(diǎn)覆蓋率分別提升了14.13個(gè)百分點(diǎn)，10.15個(gè)百分點(diǎn)和 1.52個(gè)百分點(diǎn)，且分布更均勻，覆蓋的漏洞也有所減少，近似實(shí)現(xiàn)區(qū)域完全覆蓋。

與WOA和IWOA的部署結(jié)果相比，當(dāng)?shù)螖?shù)為150次時(shí)，HPSBA優(yōu)化后的覆蓋率優(yōu)于WOA的；雖然HPSBA比IWOA優(yōu)化后的覆蓋率低，但HPSBA優(yōu)化部署的迭代次數(shù)遠(yuǎn)低于IWOA的。當(dāng)?shù)? 000次時(shí)，HPSBA優(yōu)化部署的覆蓋率優(yōu)于IWOA的，提升了0.34個(gè)百分點(diǎn)，優(yōu)化部署的耗時(shí)為119.44 s；與BOA和PSO算法的優(yōu)化策略相比，覆蓋率分別提升了10.4個(gè)百分點(diǎn)和2.11個(gè)百分點(diǎn)，耗時(shí)亦比BOA和PSO算法少。當(dāng)?shù)螖?shù)為200次時(shí)，HPSBA的覆蓋率為98.27%，優(yōu)化部署的耗時(shí)為25.61 s。

5 結(jié)束語

針對傳感器網(wǎng)絡(luò)隨機(jī)部署方式下的節(jié)點(diǎn)分布不均、覆蓋率不高的問題，提出了一種混合粒子群-蝴蝶算法HPSBA。HPSBA通過Logistic映射和自適應(yīng)調(diào)節(jié)策略來提高算法的收斂速度，并可改進(jìn)算法的收斂精度。通過與6種群體智能算法對4種基準(zhǔn)測試函數(shù)的尋優(yōu)實(shí)驗(yàn)來驗(yàn)證HPSBA的性能，尋優(yōu)結(jié)果表明HPSBA尋優(yōu)能力和收斂精度均得到提高，且穩(wěn)定性更強(qiáng)。對于WSN的節(jié)點(diǎn)部署問題，HPSBA能夠有效協(xié)調(diào)算法的全局探索和局部開發(fā)能力，與其它對比算法相比，HPSBA在使用更少節(jié)點(diǎn)數(shù)的情況下，有效提升了WSN節(jié)點(diǎn)的覆蓋率，因而也降低了網(wǎng)絡(luò)配置成本。未來將對HPSBA的收斂性理論證明[18]開展進(jìn)一步的研究，并將其應(yīng)用到WSN的異構(gòu)節(jié)點(diǎn)部署和三維部署問題中。