混合粒子群-蝴蝶算法的WSN節點部署研究*

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

(1.貴州大學電氣工程學院,貴州 貴陽 550025;2.貴州省“互聯網+”協同智能制造重點實驗室，貴州 貴陽 550025)

1 引言

無線傳感器網絡WSN(Wireless Sensor Network)由大量能量有限的傳感器節點組成[1]，通過節點之間的相互協作，處理感知對象的檢測數據，并向用戶提供精確、全面的實時數據。目前，WSN已廣泛應用在軍事、交通和環境監測等領域[2]。覆蓋率反映了傳感器網絡提供的感知服務質量，亦是評價傳感器網絡性能的一個重要指標。如何提高覆蓋率是WSN研究領域的關鍵問題之一。

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

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

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

2 節點覆蓋模型

對于WSN中的二維點覆蓋問題[1]，假設二維平面的部署區域中存在n個待覆蓋的監測目標點，部署的傳感器節點采用同構的傳感器，即傳感器的感知半徑相同。設感知半徑為rs，通信半徑為rc，其單位為m,且2rs≤rc。

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

(1)

待監測目標點i被傳感器節點s所覆蓋的概率p(i,s)[2]如式(2)所示:

(2)

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

(3)

其中節點集Q中的傳感器數量為S。

假設部署區域為正方形，邊長為L。理論上在設定的部署區域，部署節點的數量可以通過計算得到，節點全覆蓋部署的示意圖如圖1所示。

Figure 1 Node coverage diagram圖1 節點覆蓋示意圖

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

LO3C=LO3A×cos(∠AO3C)=

(4)

則理論上部署區域的節點數量如式(5)所示：

(5)

根據上述分析，節點部署問題可簡化為約束的工程優化問題，如式(6)所示：

maxf(x)=Cov,

(6)

3 混合粒子群-蝴蝶算法

3.1 粒子群優化算法

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

(7)

(8)

3.2 蝴蝶優化算法

蝴蝶優化算法[7]中，每只蝴蝶均有各自獨特的氣味和感知能力，個體之間會產生不同的氣味感知強度。其中，個體的氣味被其他蝴蝶感知的強度如式(9)所示：

f(x)=cIa

(9)

其中，f(x)表示氣味強度函數；c表示感官形態系數；I表示刺激強度，即函數適應度值；a表示強度系數，取值在[0,1]。

感官形態系數c在理論上可取[0,∞)內任意值，其計算如式(10)所示：

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

(10)

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

(11)

3.3 混合算法

3.3.1 算法的種群初始化

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

Xi=Lb+(Ub-Lb)·o

(12)

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

3.3.2 算法的全局搜索

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

(13)

(14)

3.3.3 算法的局部搜索

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

(15)

(16)

3.3.4 控制策略

混沌理論在群智能優化算法中有著較多的應用研究，如混沌種群初始化、控制參數混沌調節策略等。Logistic映射[15]是混沌理論中的一個經典的混沌映射方式，其表達式如式(17)所示：

zl+1=μzl(1-zl)

(17)

其中，l表示混沌映射的迭代次數；μ為混沌參數，其取值在[0,4]。Logistic映射的混沌序列為(0,1)，當μ=4時，該映射會產生混沌現象。

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

(18)

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

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

Figure 2 Logistic mapping圖2 Logistic映射

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

HPSBA中感官形態系數c的表達式如式(19)所示：

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

(19)

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

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

(20)

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

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

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

3.3.5 算法偽代碼

基于混合算法HPSBA節點部署的偽代碼如下所示：

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

Output：部署傳感器節點的位置和覆蓋率。

1：根據式(12)對節點的位置進行初始化，計算初始覆蓋率;

2：根據覆蓋率確定初始粒子的最佳適應度值和位置;

3：Fort=1:Tmaxdo

4：Fori=1:Ndo

5：Forj=1:Ndo

6：Ifp≥rand

7： 根據式(13)和式(14)更新節點的位置;

8：Else

9： 根據式(15)和式(16)更新節點的位置;

10：Endfor

11： 判斷節點的坐標是否超出部署區域；

12：Endfor

13： 根據式(3)計算部署區域的節點覆蓋率;

14： 更新覆蓋率和選擇最佳的節點位置;

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

16：Endfor

17：輸出部署傳感器節點的位置和覆蓋率

3.3.6 復雜度分析

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

O(HPSBA)=O(ND)+

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

(21)

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

O(BOA)=O(ND)+

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

(22)

4 實驗設計與結果分析

4.1 實驗設計

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

Table 1 Parameter settings of comparison algorithms

尋優實驗的基準測試函數[6]為：Sphere(F1)、Schwefel 2.22(F2)、Rastrigin(F3)、Griewank(F4)。4種基準測試函數的理論最優值均為0，其中，F1和F2為單峰函數，F3和F4為多峰函數，設尋優精度為1.00E-30。為了更好地評價提出的改進算法，本文用尋優成功率(Success rate)作為評價指標。實驗的環境為：Windows 7操作系統，Intel(R) Core(TM) i5-10210U CPU @2.11 GHz，16 GB內存，Matlab 2018a仿真平臺。

尋優成功率：即尋優成功次數占總測試次數的百分比。當尋優成功率小于設定的尋優精度(ε< 1.00E-30)時，認為尋優成功;反之則認為失敗。

根據式(5)計算理論上的部署區域所需的傳感器節點數量，設定的節點部署區域的實驗參數設置如表2所示。

Table 2 Parameter settings of node deployment

4.2 仿真結果分析

4.2.1 基準測試函數尋優對比

為了保證比較結果的合理性和公平性，設置對比算法的種群規模N=30，基準測試函數的維度Dim=30，最大迭代次數Tmax=500。對于同一個用于驗證的基準測試函數，每種算法分別獨立運行30次，根據統計值得出均值、標準差、尋優成功率和尋優時間。尋優的對比結果如表3所示。

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

Table 3 Comparison results of optimization algorithms

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

Figure 4 Convergence curves of comparative algorithms圖4 對比算法的尋優曲線

4.2.2 節點數量對覆蓋率的影響

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

由圖 5 可知，傳感器節點數量為55時，初始的隨機部署如圖 5a所示，隨著HPSBA的迭代次數達到150次，節點的部署位置如圖5b所示。根據HPSBA優化部署前后的傳感器節點坐標位置，運用最小生成樹Prim算法[17]繪制模擬部署區域的傳感器節點通信網絡，分別如圖5c和圖5d所示。

Figure 5 Comparison of node deployments圖5 節點部署對比

從圖5c和圖5d可知，初始部署的傳感器節點之間的通信距離均勻性較差，匯聚節點位于部署區域的中心位置，傳感器節點之間的數據傳輸距離較長，因此傳感器節點的耗能較大；而優化后的傳感器節點之間的通信距離較為均勻,有多個匯聚節點，且位置位于邊界處，從而增強了網絡的可靠性，進而降低了傳感器節點數據傳輸的耗能，延長了網絡的壽命。

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

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

對于不同節點數量的無線傳感器網絡的覆蓋率變化如圖7所示。

Figure 7 Coverage of different numbers of nodes圖7 不同節點數量的覆蓋率對比

從圖7中可以看出，HPSBA部署策略在不同傳感器節點數量的無線傳感器網絡覆蓋率均優于BOA和PSO算法的。

4.2.3 與其他算法對比

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

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

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

Table 4 Optimization results of different algorithms

與GWO算法和IGWO算法的部署結果相比，當迭代次數為100次時，HPSBA優化后的覆蓋率優于GWO算法的；雖然HPSBA比IGWO算法的優化后覆蓋率稍低，但HPSBA的優化部署耗時遠遠低于IGWO算法的。當HPSBA優化部署的迭代次數為150次時，其覆蓋率優于IGWO算法的，且耗時亦遠低于IGWO算法迭代100次的耗時。當迭代次數為200次時，HPSBA的覆蓋率為94.93%，優化部署的耗時為20.68 s。

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

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

Table 5 Optimization results of different algorithm

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

與WOA和IWOA的部署結果相比，當迭代次數為150次時，HPSBA優化后的覆蓋率優于WOA的；雖然HPSBA比IWOA優化后的覆蓋率低，但HPSBA優化部署的迭代次數遠低于IWOA的。當迭代1 000次時，HPSBA優化部署的覆蓋率優于IWOA的，提升了0.34個百分點，優化部署的耗時為119.44 s；與BOA和PSO算法的優化策略相比，覆蓋率分別提升了10.4個百分點和2.11個百分點，耗時亦比BOA和PSO算法少。當迭代次數為200次時，HPSBA的覆蓋率為98.27%，優化部署的耗時為25.61 s。

5 結束語

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