基于自適應(yīng)非線性因子雜草算法的WSN覆蓋優(yōu)化

付波 黃曉嘯 趙熙臨 權(quán)軼 賀章擎

［收稿日期］2022-03-29

［基金項(xiàng)目］湖北省自然科學(xué)基金項(xiàng)目（2020CFB814）

［第一作者］付波（1973-），男，湖北武漢人，工學(xué)博士，湖北工業(yè)大學(xué)教授，研究方向?yàn)閳D像識(shí)別與能源優(yōu)化

［通信作者］黃曉嘯（1997-），男，湖北恩施人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)殡姎夤こ?/p>

［文章編號(hào)］1003-4684（2023）02-0007-04

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

［關(guān)鍵詞］WSN覆蓋率；雜草算法；節(jié)點(diǎn)分布；Halton序列；非線性調(diào)和因子

［中圖分類號(hào)］TP18；TP212.9? ［文獻(xiàn)標(biāo)識(shí)碼］A

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

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

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

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

1??? WSN覆蓋優(yōu)化模型

假設(shè)覆蓋區(qū)域?yàn)槎S平面A，將A離散成n×n的網(wǎng)格，每個(gè)網(wǎng)格的面積設(shè)置為1，A中分布著屬性相同且位置不變的M個(gè)傳感器節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)同時(shí)具有通信半徑R1和感知半徑R2，且2R2=R1。所有傳感器節(jié)點(diǎn)可以看成是L{l1，l2，l3，…，ln}的集合，li=（xi， yi）， （i=1，2，…，n），zi=（xi， yi）為目標(biāo)點(diǎn)的位置，則節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離如式（1）所示：

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

WSN中傳感器節(jié)點(diǎn)覆蓋概率分布為：

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）

多個(gè)傳感器共同作用的WSN感知概率：

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

式中：Lall為傳感器節(jié)點(diǎn)集合。

WSN的覆蓋率為所有節(jié)點(diǎn)覆蓋面積與總面積的比值，用公式（6）表示：

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

2??? 雜草算法（IWO）

雜草算法主要步驟如下：

1）種群初始化。由下式隨機(jī)產(chǎn)生雜草i：

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

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

2）生長(zhǎng)繁殖：雜草按照式（8）產(chǎn)生種子：

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

式中，f為雜草適應(yīng)度值，s為雜草個(gè)體生成的種子數(shù)。子代種子數(shù)目與適應(yīng)度值呈線性關(guān)系，計(jì)算過程如圖1所示。

3）擴(kuò)散階段：在IWO算法中，種子按照平均值為0，標(biāo)準(zhǔn)差為б的正態(tài)分布，б的變化公式如下：

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

其中，iter為迭代次數(shù)，б為標(biāo)準(zhǔn)差，n為非線性調(diào)和因子，n=2或3。

4）競(jìng)爭(zhēng)生存階段：在種群擴(kuò)散過程中，如果種群數(shù)量達(dá)到預(yù)設(shè)最大種群規(guī)模，則按照適應(yīng)度值高低對(duì)雜草和種子進(jìn)行排序，選取適應(yīng)度好的前pmax數(shù)目個(gè)體，淘汰其余個(gè)體（圖2）。

5）停止準(zhǔn)測(cè)：重復(fù)步驟1）到4），記錄每一代種群中適應(yīng)度最好的個(gè)體，到最大迭代次數(shù)為止，得到種群的最優(yōu)解。

3??? 改進(jìn)的雜草算法（HA-IWO）

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

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

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

3.2??? 利用非線性因子調(diào)整搜索步長(zhǎng)

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

n=2－1+iteritermax0

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

4??? 仿真實(shí)驗(yàn)與分析

為驗(yàn)證本文HA-IWO算法在WSN覆蓋優(yōu)化研究中的優(yōu)勢(shì)，選用4個(gè)國際通用Benchmark函數(shù)[13]進(jìn)行了測(cè)試，并選擇基本粒子群算法（PSO）、基本雜草算法（IWO）、本文算法（HA-IWO）進(jìn)行對(duì)比分析。本次仿真實(shí)驗(yàn)所使用環(huán)境為：DELL inspiron 15-5557系列，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10，編程環(huán)境Matlab 2019a。

設(shè)置檢測(cè)區(qū)域?yàn)?00 m×100 m的二維平面，傳感器覆蓋節(jié)點(diǎn)數(shù)為20個(gè)，節(jié)點(diǎn)通信半徑為15 m，感知半徑為7.5 m。用HA-IWO算法、IWO算法、PSO算法分別對(duì)這些節(jié)點(diǎn)在區(qū)域內(nèi)進(jìn)行覆蓋優(yōu)化，三種算法同時(shí)迭代300次，重復(fù)操作10次，記錄下每次迭代得到的最優(yōu)解。各算法參數(shù)：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??? 算法覆蓋率對(duì)比

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

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

4.2??? 不同節(jié)點(diǎn)數(shù)對(duì)比試驗(yàn)

傳感器節(jié)點(diǎn)個(gè)數(shù)不同，對(duì)WSN覆蓋率也會(huì)有影響。本文記錄了傳感器節(jié)點(diǎn)數(shù)為10、15、20個(gè)時(shí)各算法的覆蓋率（表2）。

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

4.3??? 算法的優(yōu)越性對(duì)比

選用4個(gè)標(biāo)準(zhǔn)函數(shù)分別測(cè)試PSO、IWO和HA-IWO（表3），最終結(jié)果以最大值0為最優(yōu)。從表中可以看出，HA-IWO算法得出的函數(shù)值均優(yōu)于前兩種算法，說明HA-IWO算法得到的解質(zhì)量更高，尋優(yōu)精度更好。

5??? 結(jié)束語

本文針對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布不均勻?qū)е碌母采w率低下的問題，提出了一種基于非線性因子的改進(jìn)雜草算法（HA-IWO），該算法在種群初始化階段引入了一種Halton序列，使得初始種群分布更加均勻，提高算法全局尋優(yōu)的能力；在種群擴(kuò)散階段，引入自適應(yīng)非線性調(diào)和因子，使得前期種群的標(biāo)準(zhǔn)差更大，防止算法陷入局部最優(yōu)。并將改進(jìn)的雜草算法應(yīng)用于WSN覆蓋優(yōu)化中。從仿真結(jié)果可以看出，相比于粒子群算法和雜草算法，HA-IWO算法能增強(qiáng)雜草在空間的搜索速度，提高求解精度，從而有利于提升WSN的覆蓋率。

［參考文獻(xiàn)］

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

[2]曹軻，譚沖，劉洪，等.基于改進(jìn)灰狼算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法[J].中國科學(xué)院大學(xué)學(xué)報(bào)，2022，39（02）：232-239.

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

[4]彭鐸， 楊雅文， 高玉蔚，等. 基于多通信半徑和麻雀搜索的節(jié)點(diǎn)定位算法[J].傳感技術(shù)學(xué)報(bào)，2021，34（11）：7.

[5]茍平章，孫現(xiàn)超，毛剛.基于改進(jìn)遺傳算法的覆蓋空洞修復(fù)優(yōu)化[J].傳感技術(shù)學(xué)報(bào)，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ìn)雜草算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)模型在徑流預(yù)報(bào)中的應(yīng)用[J].水電能源科學(xué)，2018，36（05）：17-20.

[11] 張華強(qiáng)，陳傳訓(xùn)，呂云飛，等.IWO-PSO-SVR算法在甲烷檢測(cè)中的應(yīng)用[J].中國環(huán)境科學(xué)，2020，40（04）：7.

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

[13] 艾哈邁迪 M，莫賈拉利 H. 混沌入侵雜草優(yōu)化算法及其在混沌系統(tǒng)參數(shù)估計(jì)中的應(yīng)用[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

［責(zé)任編校： 張巖芳］