基于自適應非線性因子雜草算法的WSN覆蓋優化

付波 黃曉嘯 趙熙臨 權軼 賀章擎

［收稿日期］2022-03-29

［基金項目］湖北省自然科學基金項目（2020CFB814）

［第一作者］付波（1973-），男，湖北武漢人，工學博士，湖北工業大學教授，研究方向為圖像識別與能源優化

［通信作者］黃曉嘯（1997-），男，湖北恩施人，湖北工業大學碩士研究生，研究方向為電氣工程

［文章編號］1003-4684（2023）02-0007-04

［摘要］無線傳感器網絡（WSN）的覆蓋率與區域內的傳感器節點分布密切關聯，而現有傳感器分布算法存在收斂速度慢、易陷入局部極值等問題。對此，提出了一種基于自適應非線性因子雜草算法（HA-IWO）的傳感器節點分布優化方法。首先，在初始階段，利用Halton序列產生偏差很小的初始點，使種群分布更均勻；其次，在種群擴散階段，將非線性調和因子設置為根據迭代次數自適應產生，以調整搜索步長，解決算法易陷入局部最優的問題。最后，通過4組標準函數測試與WSN覆蓋優化仿真對該算法進行驗證。仿真實驗表明：相比于標準雜草算法，改進后的算法具有收斂速度快、覆蓋率高的優點，能有效解決WSN覆蓋優化問題。

［關鍵詞］WSN覆蓋率；雜草算法；節點分布；Halton序列；非線性調和因子

［中圖分類號］TP18；TP212.9? ［文獻標識碼］A

隨著科技的不斷進步，無線傳感器網絡（WSN）的應用范圍日趨廣泛，尤其在電氣、航空、商業、工農業生產、醫療健康等領域有著廣泛的應用[1]。WSN是一種分布式傳感網絡，其末梢是可以感知和檢查外部世界的傳感器，傳感器節點的覆蓋率決定WSN的工作效率。

近年來，將智能算法應用于WSN覆蓋優化問題得到了廣泛關注。文獻[2]提出改進灰狼算法優化BP神經網絡的無線傳感器網絡數據融合算法，提高了無線傳感器的數據融合精度；文獻[3]針對無線傳感器節點能源有限導致負載不均衡，提出一種改進螢火蟲算法優化模糊C均值的無線傳感器網絡路由算法；文獻[4]將改進的麻雀搜索算法應用于無線傳感器節點定位，取得了很好的效果；文獻[5]提出改進遺傳算法解決了無線傳感器網絡節點修復不確定性問題。但這些應用于WSN覆蓋問題的群智能算法由于本身存在缺陷，導致優化結果不是很理想。

雜草優化算法（Invasive Weed Optimization，IWO）由A.R. Mehrabian和C. Lucas[7]于2006年提出，是一種啟發式搜索算法，由于IWO算法簡單、易于并行實現，具有全局和局部搜索能力，目前已經廣泛應用于許多自然科學與工程領域，如電力市場的納什均衡問題[6]、電價預估、神經網絡、魯棒控制器參數整定[8]等。同時，針對IWO的收斂速度和尋優策略，涌現許多改進雜草算法。范宏等[9]利用柯西分布對算法進行空間擴散，在計算初始產生更多可行解；頓曉晗等[10]將雜草個體以正態分布改為混合種群多種分布產生子代個體，提高了尋優精度；張華強等[11]將雜草算法與粒子群算法進行結合，改善了算法跳出局部最優的能力；王子豪等[12]改變了傳統雜草算法的適應度計算方式，提高了算法的收斂速度。

為進一步提高雜草算法的收斂速度和尋優精度，作者提出了一種基于Halton序列初始化、根據迭代次數自適應產生非線性調和因子的改進雜草算法，仿真實驗表明：本文算法不僅有更快的收斂速度，還能跳出局部極值，搜索到質量更好的最優解，能有效提高WSN覆蓋率。

1??? WSN覆蓋優化模型

假設覆蓋區域為二維平面A，將A離散成n×n的網格，每個網格的面積設置為1，A中分布著屬性相同且位置不變的M個傳感器節點。每個節點同時具有通信半徑R1和感知半徑R2，且2R2=R1。所有傳感器節點可以看成是L{l1，l2，l3，…，ln}的集合，li=（xi， yi）， （i=1，2，…，n），zi=（xi， yi）為目標點的位置，則節點到目標點的距離如式（1）所示：

dij=（xi－xj）2+（yi－yj）2（1）

WSN中傳感器節點覆蓋概率分布為：

P（x，y，l）=1dij≤R2－re，-α1β1λ1α2+β2λ2R2－re

式中：re（0

α1=Re－R2+dij（3）

α2=re+R2－dij（4）

多個傳感器共同作用的WSN感知概率：

pcov（Lall）=1－∏li∈Lall（1－P（x，y，l））（5）

式中：Lall為傳感器節點集合。

WSN的覆蓋率為所有節點覆蓋面積與總面積的比值，用公式（6）表示：

Rall=∑n×nj=1Pcov（Lall）n×n（6）

2??? 雜草算法（IWO）

雜草算法主要步驟如下：

1）種群初始化。由下式隨機產生雜草i：

xi=xmin+（xmax－xmin）·rand（0，1）（7）

其中，xi=（xi1，xi2，…，xiD），且i=1， 2， …，P，D為問題的維度，P為種群數量，xmax和xmin分別為xi的極大值和極小值。

2）生長繁殖：雜草按照式（8）產生種子：

weedn=f－fminfmax－fmin·（smax－smin）+smin（8）

式中，f為雜草適應度值，s為雜草個體生成的種子數。子代種子數目與適應度值呈線性關系，計算過程如圖1所示。

3）擴散階段：在IWO算法中，種子按照平均值為0，標準差為б的正態分布，б的變化公式如下：

σ=（itermax－iter）n（itermax）n·（σinit－σfinal）+σfinal（9）

其中，iter為迭代次數，б為標準差，n為非線性調和因子，n=2或3。

4）競爭生存階段：在種群擴散過程中，如果種群數量達到預設最大種群規模，則按照適應度值高低對雜草和種子進行排序，選取適應度好的前pmax數目個體，淘汰其余個體（圖2）。

5）停止準測：重復步驟1）到4），記錄每一代種群中適應度最好的個體，到最大迭代次數為止，得到種群的最優解。

3??? 改進的雜草算法（HA-IWO）

3.1??? 基于Halton序列的種群初始化

IWO算法在初始階段會隨機生成初始點，初始點分布不均勻易導致算法陷入局部極值，因此初始點的分布選擇是提升IWO算法效率的重要環節。低偏差序列能較好地解決分布不均勻的缺陷，提高初始解質量。圖3、圖4分別是偽隨機序列和低偏差序列的空間分布效果。

從圖4可以看出，偽隨機序列分布的點有聚集和扎堆現象，這種初始點極易讓算法陷入局部極值。而低偏差序列的點在空間內呈現均勻分布，因此具有更好的尋優能力。Halton序列屬于低偏差序列的一種，由于其定義簡單且能生成無窮個樣本點，因此被廣泛應用。它是一種為數值方法（如蒙特卡洛模擬算法）產生頂點的系列生成算法。雖然這些序列是以確定的方法算出來的，但它們的偏差很小，所以，這些點可以看成是空間內隨機分布的點。

3.2??? 利用非線性因子調整搜索步長

雜草種子按照式（9）分布在父代周圍，基本IWO算法中的非線性因子n是一個定值，極大限制了雜草個體的全局尋優能力。將非線性因子設置成根據迭代次數自適應變化，使得迭代前期算法的標準差較大，種子分布在離父代較遠的位置，迭代后期算法標準差變小，種子分布在離父代較近的位置，從而實現算法從全局到局部的搜索，避免早熟。非線性因子n的變化如式（10）：

n=2－1+iteritermax0

式中：iter表示當前迭代次數，itermax為最大迭代次數。HA-IWO算法步驟見圖5。

4??? 仿真實驗與分析

為驗證本文HA-IWO算法在WSN覆蓋優化研究中的優勢，選用4個國際通用Benchmark函數[13]進行了測試，并選擇基本粒子群算法（PSO）、基本雜草算法（IWO）、本文算法（HA-IWO）進行對比分析。本次仿真實驗所使用環境為：DELL inspiron 15-5557系列，內存為8 GB，操作系統為Windows 10，編程環境Matlab 2019a。

設置檢測區域為100 m×100 m的二維平面，傳感器覆蓋節點數為20個，節點通信半徑為15 m，感知半徑為7.5 m。用HA-IWO算法、IWO算法、PSO算法分別對這些節點在區域內進行覆蓋優化，三種算法同時迭代300次，重復操作10次，記錄下每次迭代得到的最優解。各算法參數：PSO（c1=c2=2， ω=0.6， vmax=5）， IWO（smax=20， smin=0，бini=300，бfinal=0.05）， HA-IWO（smax=20， smin=0， бini=300，бfinal=0.05）。

4.1??? 算法覆蓋率對比

用以上三種算法對WSN覆蓋優化仿真。首先，僅用Halton序列對雜草算法進行改進，結果見表1第二列，可以看出，相比于另外兩種優化算法，H-IWO算法對WSN的平均覆蓋率大大提高了，比IWO算法高出大約2.66%，比PSO算法高出大約9.52%。其次，僅用非線性因子對雜草算法進行改進，見表1第三列，可以看出，A-IWO算法的覆蓋率比IWO算法高出3.55%，比PSO算法高出8.18%。最后，用Halton序列和非線性因子同時改進雜草算法，見表1第四列，可以看出，HA-IWO算法的覆蓋率比IWO算法高出5.76%，比PSO算法高出11.31%。綜上所述，相比于PSO算法和IWO算法，經過Halton序列和非線性因子改進后的HA-IWO算法能有效地提高WSN的覆蓋率，體現了該算法的有效性。

另外，三種算法的傳感器最終分布如圖6所示，不難看出，PSO算法和IWO算法的傳感器分布較雜亂，導致覆蓋率低下；HA-IWO算法引入了Halton序列，使得傳感器分布更加均勻，從而使覆蓋率大大提高。

4.2??? 不同節點數對比試驗

傳感器節點個數不同，對WSN覆蓋率也會有影響。本文記錄了傳感器節點數為10、15、20個時各算法的覆蓋率（表2）。

隨著傳感器節點數的增加，各算法的覆蓋率均有提高，且HA-IWO算法的覆蓋率均高于PSO算法和IWO算法。另外分析各算法達到最大覆蓋率時的迭代次數可知，HA-IWO達到最大覆蓋率時的迭代次數為100次左右，而PSO和IWO在迭代150次以后才達到覆蓋率最大，這表明HA-IWO算法的收斂速度更快。3種算法的WSN覆蓋率隨迭代次數的變化曲線見圖7-9。可見，IWO和PSO分別在182次和227次時才開始收斂，而HA-IWO的曲線在50次時就開始收斂，收斂速度明顯更快，加強了尋優精度。

4.3??? 算法的優越性對比

選用4個標準函數分別測試PSO、IWO和HA-IWO（表3），最終結果以最大值0為最優。從表中可以看出，HA-IWO算法得出的函數值均優于前兩種算法，說明HA-IWO算法得到的解質量更高，尋優精度更好。

5??? 結束語

本文針對無線傳感器網絡節點分布不均勻導致的覆蓋率低下的問題，提出了一種基于非線性因子的改進雜草算法（HA-IWO），該算法在種群初始化階段引入了一種Halton序列，使得初始種群分布更加均勻，提高算法全局尋優的能力；在種群擴散階段，引入自適應非線性調和因子，使得前期種群的標準差更大，防止算法陷入局部最優。并將改進的雜草算法應用于WSN覆蓋優化中。從仿真結果可以看出，相比于粒子群算法和雜草算法，HA-IWO算法能增強雜草在空間的搜索速度，提高求解精度，從而有利于提升WSN的覆蓋率。

［參考文獻］

［1］M SALEHI. HOSSAIN. Federated learning in unreliable and resource-constrained wireless Networks[J]. IEEE Transactions on Communications，2021：5136-5151.

[2]曹軻，譚沖，劉洪，等.基于改進灰狼算法優化BP神經網絡的無線傳感器網絡數據融合算法[J].中國科學院大學學報，2022，39（02）：232-239.

[3]余修武， 秦曉坤， 劉永. 基于螢火蟲算法優化FCM的WSN路由算法[J]. 北京郵電大學學報（自科版）， 2022， 45（02）：50-56.

[4]彭鐸， 楊雅文， 高玉蔚，等. 基于多通信半徑和麻雀搜索的節點定位算法[J].傳感技術學報，2021，34（11）：7.

[5]茍平章，孫現超，毛剛.基于改進遺傳算法的覆蓋空洞修復優化[J].傳感技術學報，2020，33（12）：1800-1807.

[6]MALLAHZADEH A R， ORAIZI H， DAVOODI-RAD Z.Application of the invasive weed optimization technique for antenna configuration[C].∥Proc of Loughborough Antennas and Propagation Conference. Piscataway： IEEE Press， 2008：425-428.

[7]Mehrabian A R， Lucas C. A noveloptimization algorithm inspired from weed colonization[J]. Ecological Informatics， 2006， 1（4）：355-366.

[8]HAJIMRSADEGHI H， GHAZANFARI A， RAHIMI-KIAN A， et al. Cooperative coevolutionary invasive weed optimization andapplication to Nash equilibrium search in electricity markets[C].∥Proc of World Congress on Nature&Biologically Inspired Computing. [S.l.]：IEEE Press， 2009：1532-1535.

[9]FAN H，LIU Z C.Reconfiguration of distribution Network containing distributed power generation based on differential evolution invasive weed algorithm[J]. Renewable Energy，2019，37（04）：545-551.

[10] 頓曉晗，周建中，曾小凡.基于改進雜草算法優化的神經網絡模型在徑流預報中的應用[J].水電能源科學，2018，36（05）：17-20.

[11] 張華強，陳傳訓，呂云飛，等.IWO-PSO-SVR算法在甲烷檢測中的應用[J].中國環境科學，2020，40（04）：7.

[12] 王子豪，馬俊濤，魯軍，等.基于改進雜草入侵算法的陣元失效校正方法[J].計算機仿真，2021，38（10）：222-226.

[13] 艾哈邁迪 M，莫賈拉利 H. 混沌入侵雜草優化算法及其在混沌系統參數估計中的應用[J]．Chaos Solitons & Fractals the Interdisciplinary Journal of Nonlinear Science & Nonequilibrium & Complex Phenomena， 2012， 45（s9-10）：1108-1120.

WSN Coverage Optimization by AdaptiveNonlinear Factor based Weed Algorithm

FU Bo， HUANG Xiaoxiao， ZHAO Xilin， QUANG Yi， HE Zhangqing

（School of Electrical and Electronic Engineering， Hubei Univ. of Tech.， Wuhan 430068，China）

Abstract： The coverage rate of wireless sensor network （WSN） is closely related to the distribution of sensor nodes in the area， and existing sensor distribution algorithms have problems such as slow convergence speed and easy to fall into local extreme values. In this regard， this paper proposes an optimization method for sensor node distribution based on adaptive nonlinear factor weed algorithm （HA IWO）. First， in the initial stage， the Halton sequence is used to generate initial points with small deviations to make the population distribution more uniform; second， in the population diffusion stage， the nonlinear harmonic factor is set to be adaptively generated according to the number of iterations to adjust the search step size. Solve the problem that the algorithm is easy to fall into the local optimum. Finally， the algorithm is verified by 4 sets of standard function tests and WSN coverage optimization simulation. Simulation experiments show that the algorithm has the advantages of fast convergence speed and high coverage rate， and can effectively solve the WSN coverage optimization problem.

Keywords：WSN coverage rate; Weed algorithm; Node distribution; Halton sequence; Nonlinear harmonic factor

［責任編校： 張巖芳］