改進(jìn)算術(shù)優(yōu)化算法的無線傳感器網(wǎng)絡(luò)覆蓋

賈鶴鳴,孟 彬,魏元昊,力尚龍,文昌盛,陳俊玲

（三明學(xué)院信息工程學(xué)院,福建三明 365004）

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)是一種分布式傳感網(wǎng)絡(luò),通過大量的傳感器節(jié)點部署形成自組織網(wǎng)絡(luò),具有精確度高、靈活性強(qiáng)和可靠性高等特點,實現(xiàn)了數(shù)據(jù)的采集、處理和傳輸三種功能.因此被廣泛應(yīng)用于環(huán)境探測、智能交通和工業(yè)領(lǐng)域.但是隨著無線傳感器網(wǎng)絡(luò)的普及,無線傳感器網(wǎng)絡(luò)自身的缺點逐漸開始暴露.而目前急需解決的是覆蓋優(yōu)化問題[1-4].WSN的覆蓋優(yōu)化問題,可以簡單描述為:在規(guī)定的可監(jiān)測范圍內(nèi)針對傳感器網(wǎng)絡(luò)可連通情況下的傳感器節(jié)點部署問題.為提高覆蓋率,人們通常在范圍內(nèi)直接撒播大量節(jié)點,龐大的數(shù)量往往會提高部署密度從而達(dá)成目的，但會產(chǎn)生大量冗余節(jié)點,降低網(wǎng)絡(luò)整體性能.而節(jié)點數(shù)目過少又會產(chǎn)生大量覆蓋盲區(qū),降低網(wǎng)絡(luò)傳輸效率.因此需要對WSN中傳感器節(jié)點的部署進(jìn)行自適應(yīng)調(diào)整,使節(jié)點在監(jiān)測范圍內(nèi)分布的更均勻,節(jié)點覆蓋率更高.

目前,國內(nèi)已經(jīng)有許多針對WSN 節(jié)點覆蓋的研究,如文獻(xiàn)[5]提出一種能量位置融合改進(jìn)灰狼算法,不僅提高了覆蓋率,并且為能量有限的情況下提供了新思路.文獻(xiàn)[6]基于水波優(yōu)化算法,將傳感器坐標(biāo)構(gòu)建為水波個體,設(shè)覆蓋率為適應(yīng)度函數(shù),執(zhí)行水波的傳播、折射和碎波操作,并對節(jié)點坐標(biāo)位置進(jìn)行優(yōu)化,以此來提高覆蓋率.文獻(xiàn)[7]針對三維WSN 節(jié)點部署問題,提出一種基于VFA 與AFSA 的融合算法獲得最優(yōu)部署模型,并有效提高了網(wǎng)絡(luò)覆蓋率.

算術(shù)優(yōu)化算法(arithmetic optimization algorithm,AOA)是由學(xué)者Laith Abualigah等于2021年提出的一種新型元啟發(fā)式優(yōu)化算法[8],其靈感來源于算術(shù)中的四則混合運(yùn)算.該算法利用乘除運(yùn)算進(jìn)行全局探索,利用加減運(yùn)算進(jìn)行局部開發(fā).目前算術(shù)優(yōu)化算法被應(yīng)用于求解多類優(yōu)化問題中,并逐步得到了發(fā)展.算術(shù)優(yōu)化算法能夠迅速的尋找到全局最優(yōu)解.針對算術(shù)優(yōu)化算法在解決無線傳感器網(wǎng)絡(luò)覆蓋問題上收斂速度慢、開發(fā)能力不足的問題,本文融合隨機(jī)反向?qū)W習(xí),引入正弦控制因子,提出了改進(jìn)的算術(shù)優(yōu)化算法(improved arithmetic optimization algorithm,IAOA),該算法通過改進(jìn)的數(shù)學(xué)函數(shù)加速器使算法前期探索階段盡可能的部署監(jiān)測范圍,后期開發(fā)階段遍歷所有點,期間通過隨機(jī)反向?qū)W習(xí)避免種群中個體錯過尋優(yōu)路徑上的有效解,最終提高算法的搜索能力.相比算術(shù)優(yōu)化算法和其他優(yōu)化算法,該算法具備較快的收斂速度及較高的收斂精度.

1 傳感器網(wǎng)絡(luò)節(jié)點覆蓋模型

參考文獻(xiàn)[2]建立一個監(jiān)測范圍為S=L×L的二維正方形平面,并在該監(jiān)測范圍內(nèi)隨機(jī)播撒N個傳感器節(jié)點,分別定義為C={C1,C2,…,CN},每個節(jié)點的位置Ci的坐標(biāo)為(xi,yi),i=1,2,…,N,所有節(jié)點具有相同的通信半徑R和感知半徑r.傳感器節(jié)點的感知范圍均為以點(xi,yi)為中心,以r為半徑的圓形區(qū)域.將該監(jiān)測范圍離散為m×n個像素點,定義為zj(xj,yj),j=1,2,…,m×n.計算像素點zj與任一節(jié)點Ci之間的歐式距離,記為d,如式（1）所示.

若d≤r,說明該像素點zj已被傳感器節(jié)點Ci覆蓋,反之則未被覆蓋.像素點zj被傳感器節(jié)點Ci感應(yīng)到的概率如式（2）所示.

其中:Pcov(Ci,zj)為感知概率;r為傳感器節(jié)點的感知半徑.

在監(jiān)測范圍內(nèi),任一像素點zj可同時被多個節(jié)點Ci所感應(yīng),定義zj的聯(lián)合感知概率為:

其中:P(C,zj)為聯(lián)合感知概率;N為范圍內(nèi)節(jié)點總數(shù)目;C為監(jiān)測目標(biāo)點的節(jié)點集合.

區(qū)域覆蓋率為傳感器節(jié)點集合C所覆蓋的像素點數(shù)占范圍總像素點數(shù)的比例,定義為COV,其計算公式如下:

2 算術(shù)優(yōu)化算法

算術(shù)優(yōu)化算法是一種根據(jù)運(yùn)算符的不同特性實現(xiàn)全局尋優(yōu)的元啟發(fā)式優(yōu)化算法,通過數(shù)學(xué)函數(shù)加速器選擇優(yōu)化策略,即利用乘法策略和除法策略進(jìn)行全局搜索,提高解的分散性;利用加法策略和減法策略進(jìn)行局部開發(fā),增強(qiáng)算法的尋優(yōu)能力.具體實現(xiàn)原理如下.

2.1 初始化

算術(shù)優(yōu)化算法通過式（5）與式（6）生成隨機(jī)數(shù)進(jìn)行種群的初始化。

其中:N為粒子數(shù)目;dim為維度；Ub為上界,Lb為下界;Rand為0～1之間的隨機(jī)數(shù);Position(i,j)是第i個解在第j維空間的位置.

2.2 數(shù)學(xué)函數(shù)加速器MOA

根據(jù)MOA的值判斷進(jìn)行全局探索還是局部開發(fā):

其中:r1為0～1之間的隨機(jī)數(shù);MOA(t)為當(dāng)前的加速函數(shù)值;Min為加速函數(shù)的最小值;Max為加速函數(shù)最大值,T為最大迭代次數(shù);t為當(dāng)前迭代次數(shù).當(dāng)r1＜MOA(t)時,函數(shù)將進(jìn)入全局探索階段;反之,則進(jìn)入局部開發(fā)階段.

2.3 全局探索階段

根據(jù)隨機(jī)數(shù)r2決定采用乘法或除法策略,兩種策略離散度高,有利于粒子在算法空間內(nèi)探索,計算公式如下:

其中，r2為0～1的隨機(jī)數(shù),X(t+1)為下一代粒子的位置,Xb(t)為當(dāng)前適應(yīng)度最佳粒子的位置,μ為搜索過程控制系數(shù)(此處設(shè)為0.499),ε為極小值,MOP為數(shù)學(xué)優(yōu)化器概率,其計算公式如下:

式中:MOP(t)為當(dāng)前數(shù)學(xué)優(yōu)化器概率;α為迭代敏感系數(shù),α值越高迭代次數(shù)對MOP(t)影響越大.

2.4 局部開發(fā)階段

算術(shù)優(yōu)化算法通過加法策略和減法策略進(jìn)行局部開發(fā),兩種策略均具有顯著的低分散性,可以容易地接近目標(biāo),有利于算法更快尋找最優(yōu)解.其計算公式如下:

其中:r3為0～1之間的隨機(jī)數(shù).

3 改進(jìn)算術(shù)優(yōu)化算法

算術(shù)優(yōu)化算法由線性關(guān)系的MOA 控制探索與開發(fā)階段,而算法為非線性變化,導(dǎo)致算法探索與開發(fā)不平衡.為解決該問題,本文引入正弦控制因子對MOA 進(jìn)行改進(jìn),以此平衡算法探索與開發(fā)的能力.針對迭代后期種群多樣性下降、搜索能力減弱的問題,引入了隨機(jī)反向?qū)W習(xí)策略以幫助算法增加種群多樣性,提高搜索能力.

3.1 引入正弦控制因子對MOA(數(shù)學(xué)函數(shù)加速器)的改進(jìn)

MOA 的取值影響著算法探索與開發(fā)之間的平衡,針對原算法全局探索與局部開發(fā)能力不平衡的現(xiàn)象,本文引入正弦控制因子對MOA 進(jìn)行改進(jìn).原算法中MOA 呈線性關(guān)系,而算法在進(jìn)化探索過程中呈非線性變化,線性增長的MOA不能準(zhǔn)確貼切實際迭代過程,而正弦控制因子可以將MOA的變化轉(zhuǎn)變?yōu)榉蔷€性,使其更貼切算法實際迭代過程,故引入正弦控制因子來改進(jìn)數(shù)學(xué)函數(shù)加速器.改進(jìn)后的數(shù)學(xué)函數(shù)加速器(sin math optimizer accelerated,SMOA)能夠防止算法因早熟而陷入局部最優(yōu)或因收縮過慢導(dǎo)致收斂精度不足等問題.前期SMOA較大便于節(jié)點部署,而后期SMOA迅速減小以便算法迅速收縮,提高搜索精度.其表達(dá)式如（11）所示:

其中:MOP_Min 為SMOA 的最小值,MOP_Max 為SMOA 的最大值.選取MOP_Min=0.05、MOP_Max=0.95.

3.2 隨機(jī)反向?qū)W習(xí)策略

隨機(jī)反向?qū)W習(xí)策略(random opposition-based learning,ROBL)是一種能夠提高種群避免局部最優(yōu)能力[9],增強(qiáng)種群多樣性的改進(jìn)策略,由反向?qū)W習(xí)策略(opposition-based learning,OBL)改進(jìn)而來[10].其思想為:在種群尋優(yōu)過程中,當(dāng)前解根據(jù)原點位置產(chǎn)生一個距離原點長度為隨機(jī)值的反向解,比較當(dāng)前解與反向解的適應(yīng)度值,擇優(yōu)進(jìn)入下一次迭代.

隨機(jī)反向?qū)W習(xí)公式如下:

其中:Value(i,:)是由當(dāng)前解根據(jù)原點位置產(chǎn)生的反向解,而fitness(Position(i,:))代表當(dāng)前解的適應(yīng)度值,fitness(Value(i,:))代表反向解的適應(yīng)度值,對比兩解的適應(yīng)度值,選擇適應(yīng)度值更優(yōu)的解進(jìn)入下一次迭代.

4 改進(jìn)算術(shù)優(yōu)化算法應(yīng)用于WSN覆蓋的實現(xiàn)步驟

綜合上述改進(jìn)策略,本文提出一種改進(jìn)的算術(shù)優(yōu)化算法,即引入正弦控制因子對數(shù)學(xué)函數(shù)加速器進(jìn)行改進(jìn)以避免算法陷入局部最優(yōu),并融合隨機(jī)反向?qū)W習(xí)策略來增強(qiáng)種群多樣性,以此提高算法的尋優(yōu)性能.對于WSN 覆蓋問題，最優(yōu)個體的適應(yīng)度值與其他個體的適應(yīng)度值相差較小，容易陷入局部最優(yōu)而無法尋找到更優(yōu)解,而改進(jìn)的算術(shù)優(yōu)化算法可以完美解決該問題.具體算法實現(xiàn)步驟如下.

步聚1輸入節(jié)點數(shù)N、感知半徑r、監(jiān)測范圍邊長L等,種群大小U為30、迭代次數(shù)為500.

步聚2根據(jù)式（5）和（6）初始化種群.

步聚3根據(jù)式（11）計算SMOA,同時根據(jù)式（9）計算MOP.比較SMOA 與r1的大小,若SMOA＜r1則進(jìn)入局部開發(fā)階段并根據(jù)式（8）更新位置,否則進(jìn)入全局探索階段根據(jù)公式（10）更新位置.

步聚4以覆蓋率COV為目標(biāo)函數(shù)，根據(jù)式（4）計算種群適應(yīng)度.

步聚5通過隨機(jī)反向?qū)W習(xí)式（12）生成反向解Value.

步聚6根據(jù)式（4）計算Value的適應(yīng)度.

步聚7根據(jù)式（13）比較適應(yīng)度值,保留較優(yōu)解..

步聚8判斷是否達(dá)到當(dāng)前迭代次數(shù)是否等于目標(biāo)迭代次數(shù),如果達(dá)到目標(biāo)迭代次數(shù)則輸出最優(yōu)分布并結(jié)束循環(huán),否則回到步聚3.

IAOA求解WSN部署優(yōu)化流程圖，如圖1所示.

圖1 IAOA的WSN部署優(yōu)化流程圖Fig.1 WSN deployment optimization flow chart of IAOA

5 仿真實驗結(jié)果與分析

5.1 實驗環(huán)境設(shè)置

為了驗證改進(jìn)的算術(shù)優(yōu)化算法應(yīng)用于WSN 覆蓋優(yōu)化的性能,均在主頻為2.50 GHz 的11th Gen Intel(R)Core(TM)i7-11700 處理器,16 GB 內(nèi)存,操作系統(tǒng)為64 位Windows11 的電腦上使用MATLAB2021a 進(jìn)行仿真實驗.

5.2 實驗結(jié)果

5.2.1 與原始AOA對比

為了比較原始算術(shù)優(yōu)化算法與改進(jìn)后算術(shù)優(yōu)化算法的性能差異,本實驗設(shè)置了3 組實驗參數(shù),具體信息見表1.其他參數(shù)設(shè)置:種群大小U為30,迭代次數(shù)T為500.圖2 為根據(jù)表1 數(shù)據(jù)執(zhí)行后得到的迭代曲線及節(jié)點分布情況,表2為算法覆蓋率結(jié)果對比.

表1 實驗分組及部分參數(shù)設(shè)置Tab.1 Experimental grouping and some parameter settings

由圖2可知,相較于原始算法,改進(jìn)后的算術(shù)優(yōu)化算法明顯能夠跳出局部最優(yōu).由表2所示,在全局尋優(yōu)能力上,相比原始算法,改進(jìn)后算法的覆蓋率在各種環(huán)境下均得到了提高.為了更直觀的比較兩種算法對監(jiān)測范圍的部署情況,圖2展示了傳感器節(jié)點分布情況.由圖2所示,IAOA在WSN覆蓋問題上明顯優(yōu)于AOA.

圖2 不同組別的IAOA算法和AOA算法結(jié)果對比Fig.2 Comparison of the results of IAOA algorithm and AOA algorithm in different groups

表2 AOA算法與IAOA算法覆蓋率對比Tab.2 AOA vs IAOA coverage

5.2.2 IAOA與其他優(yōu)化算法對比

設(shè)監(jiān)測范圍為100 m×100 m 的二維正方形平面,傳感器節(jié)點數(shù)N=50,感知半徑r=10 m,通信半徑R=15 m,種群大小U為30,迭代次數(shù)T為500.本次實驗選取了原始的AOA、改進(jìn)的粒子群優(yōu)化算法(binary particle swarm optimization,BPSO)[11]、改進(jìn)的鯨魚優(yōu)化算法(improved whale optimization algorithm,IWOA)[12]以及改進(jìn)的灰狼優(yōu)化算法(improved grey wolf optimizer,IGWO)[13]作為對比算法.圖3為覆蓋優(yōu)化時的迭代曲線及節(jié)點分布,表3為算法覆蓋結(jié)果對比.

由圖3所示,改進(jìn)后的算術(shù)優(yōu)化算法性能明顯優(yōu)于原始算法及文獻(xiàn)[8-10]中所提出的優(yōu)化算法.由表3看出,改進(jìn)后的算術(shù)優(yōu)化算法與對比算法相比,覆蓋率分別提升了14.96%,6.82%,4.12%和15.82%.各算法的節(jié)點位置分布情況如圖3 示,可以看出IAOA 的覆蓋效果最好.通過以上實驗有效證明了IAOA 對于WSN覆蓋問題的有效性和實用性.

圖3 各算法節(jié)點分布及迭代曲線Fig.3 Node distribution and iteration curves of each algorithm

表3 不同算法的覆蓋率結(jié)果對比Tab.3 Comparison of coverage results of different algorithms

6 結(jié)語

針對實現(xiàn)無線傳感器網(wǎng)絡(luò)覆蓋率最大化的目標(biāo),從無線傳感器網(wǎng)絡(luò)的視角,構(gòu)建0-1 節(jié)點覆蓋模型并通過對監(jiān)測范圍內(nèi)的節(jié)點部署,利用改進(jìn)后的算術(shù)優(yōu)化算法尋找最優(yōu)位置,使WSN 盡可能達(dá)到全覆蓋.本文提出的改進(jìn)算術(shù)優(yōu)化算法,是在原始算法的基礎(chǔ)上加入隨機(jī)反向?qū)W習(xí)策略并針對數(shù)學(xué)函數(shù)加速器引入正弦控制因子,使算法更容易跳出局部最優(yōu),并且增強(qiáng)了算法的開發(fā)能力.仿真實驗表明,在與其他4 個算法測試條件相同的情況下,IAOA的適應(yīng)性更強(qiáng),不僅可以有效提高網(wǎng)絡(luò)覆蓋率,而且可以降低冗余,以此減少節(jié)點數(shù)目和降低部署成本.