王振東，汪嘉寶，李大海

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

隨著互聯(lián)網(wǎng)技術(shù)，人工智能和5G技術(shù)的不斷發(fā)展，物聯(lián)網(wǎng)已經(jīng)成為當(dāng)下科技領(lǐng)域熱門的研究對(duì)象。而無(wú)線傳感器網(wǎng)絡(luò)作為物聯(lián)網(wǎng)的核心支撐技術(shù)之一，對(duì)物聯(lián)網(wǎng)起到支撐作用。無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量的靜止或移動(dòng)的傳感器以自組織和多跳的方式構(gòu)成無(wú)線網(wǎng)絡(luò)，以協(xié)作的方式感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對(duì)象的信息，并最終把這些信息發(fā)送給網(wǎng)絡(luò)的所有者。因?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)技術(shù)能夠滿足快速移動(dòng)、自組織和方便快捷等需求，且無(wú)線傳感器網(wǎng)絡(luò)技術(shù)發(fā)展也日漸成熟。因此，無(wú)線傳感器網(wǎng)絡(luò)被廣泛的應(yīng)用到軍事[1]、航空[2]、救災(zāi)[3]、環(huán)境[4]、醫(yī)療[5]、保健[6]、工業(yè)[7]、商業(yè)[8]等領(lǐng)域。 近年來(lái)提出的智慧交通[9]，智能家居[10]，智慧城市[11]等領(lǐng)域，同樣取得了很大規(guī)模的應(yīng)用。但是隨著無(wú)線傳感器網(wǎng)絡(luò)的普及，無(wú)線傳感器網(wǎng)絡(luò)自身的不足開(kāi)始被逐漸重視。尤其是網(wǎng)絡(luò)服務(wù)質(zhì)量和網(wǎng)絡(luò)應(yīng)用的穩(wěn)定性方面。而對(duì)于解決這兩個(gè)問(wèn)題來(lái)說(shuō)，覆蓋優(yōu)化問(wèn)題又是一個(gè)必須先解決的基本問(wèn)題。WSN的覆蓋優(yōu)化問(wèn)題可描述為在規(guī)定監(jiān)測(cè)區(qū)域內(nèi)，保證傳感器網(wǎng)絡(luò)連通情況下的節(jié)點(diǎn)部署問(wèn)題。為了滿足覆蓋要求，人們通常直接隨機(jī)拋灑大量傳感器節(jié)點(diǎn)，由于受到傳感器節(jié)點(diǎn)電量和穩(wěn)定性等性能約束，往往會(huì)造成比較大的覆蓋盲區(qū)或者節(jié)點(diǎn)冗余現(xiàn)象，進(jìn)而縮短網(wǎng)絡(luò)使用壽命，降低網(wǎng)絡(luò)可靠性，在能耗與成本上造成大量的資源浪費(fèi)，因此需要對(duì)無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)進(jìn)行自適應(yīng)的調(diào)整部署，使其在監(jiān)測(cè)區(qū)域分布更加均勻，覆蓋率更高。從而增長(zhǎng)網(wǎng)絡(luò)使用壽命，提高網(wǎng)絡(luò)可靠性。這對(duì)整個(gè)無(wú)線傳感器網(wǎng)絡(luò)具有重要的意義。

近年來(lái)，將智能優(yōu)化算法應(yīng)用到無(wú)線傳感器覆蓋問(wèn)題上受到了越來(lái)越多學(xué)者的關(guān)注。胡小平等[12]提出一種基于多種策略改進(jìn)灰狼優(yōu)化算法，雖然較于基本灰狼優(yōu)化算法來(lái)說(shuō)，在覆蓋優(yōu)化、覆蓋率和收斂速度等方面均有提升，但與其他改進(jìn)智能算法相比并無(wú)法凸顯出該算法的優(yōu)越性；楊永健等[13]提出了一種基于改進(jìn)PSO算法的傳感器網(wǎng)絡(luò)覆蓋優(yōu)化模型，對(duì)比其他改進(jìn)粒子群算法覆蓋率有所提高，但仍需完善才能實(shí)現(xiàn)近似覆蓋；徐欽帥等[14]提出了一種改進(jìn)蟻獅算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化模型，雖然相較于不同改進(jìn)的蟻獅算法有效地提高了覆蓋率，但其精度及穩(wěn)定性不夠理想且節(jié)點(diǎn)有效覆蓋率較低。上述研究成果表明，多種不同群體智能算法應(yīng)用于WSN網(wǎng)絡(luò)覆蓋優(yōu)化結(jié)果雖然較之前有所改善，但整體優(yōu)化效果仍有待提高。

麻雀搜索算法[15](SSA)是由薛建凱于2020年最新提出，它通過(guò)麻雀?jìng)€(gè)體搜尋食物和反捕食進(jìn)行迭代尋優(yōu)，具有搜索精度高，收斂速度快，穩(wěn)定性好，魯棒性強(qiáng)等特點(diǎn)。但是和其他群體智能優(yōu)化算法一樣，在求解復(fù)雜工程優(yōu)化問(wèn)題時(shí)，容易“早熟”導(dǎo)致收斂精度不高，且易于陷入局部最優(yōu)解。

針對(duì)以上討論問(wèn)題，同時(shí)結(jié)合SSA算法，本文研究了一種增強(qiáng)型SSA算法的WSN覆蓋優(yōu)化問(wèn)題。首先，考慮到非線性收斂因子能更好的平衡局部和全局搜索，以及柯西變異算子跳出局部最優(yōu)的特點(diǎn)，本文提出一種增強(qiáng)型麻雀搜索算法(ESSA)。通過(guò)測(cè)試不同模態(tài)的基準(zhǔn)測(cè)試函數(shù)，表明與其他改進(jìn)智能算法相比，該算法在搜索精度、收斂速度、穩(wěn)定性和避免局部最優(yōu)值等方面均有明顯提升。其次，針對(duì)區(qū)域覆蓋難以應(yīng)用幾何學(xué)方法解決的問(wèn)題，本文在所提出ESSA算法的基礎(chǔ)上，應(yīng)用到WSN覆蓋優(yōu)化中，并與其他相同場(chǎng)景的改進(jìn)算法相比，結(jié)果表明ESSA算法有著更好的優(yōu)化效果。

1 覆蓋模型描述

1.1 覆蓋率描述

在WSN中，本文假設(shè)有N個(gè)同構(gòu)傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)都具有相同的感知半徑R及通信半徑R c，為保證無(wú)線傳感器網(wǎng)絡(luò)的連通性，節(jié)點(diǎn)的通信半徑設(shè)置為大于或者等于節(jié)點(diǎn)感知半徑的2倍。節(jié)點(diǎn)集合可表示為S＝{s1，s2，s3，…，s n}。監(jiān)測(cè)區(qū)域節(jié)點(diǎn)的集合M＝{m1，m2，m3，…，mn}，(x i，y i)與(x j，y j)分別對(duì)應(yīng)集合中si、m j的二維空間坐標(biāo)。本文采用布爾感知模型[16](即傳感器節(jié)點(diǎn)對(duì)位于R范圍內(nèi)檢測(cè)區(qū)域節(jié)點(diǎn)的感知能力相同，因而傳感器節(jié)點(diǎn)的感知范圍是以傳感器節(jié)點(diǎn)為圓心、以R為半徑的圓盤)作為節(jié)點(diǎn)感知模型，只要監(jiān)測(cè)區(qū)域處于節(jié)點(diǎn)感知半徑范圍則視為覆蓋該節(jié)點(diǎn)。傳感器節(jié)點(diǎn)與監(jiān)測(cè)區(qū)域節(jié)點(diǎn)之間的歐氏距離為

監(jiān)測(cè)點(diǎn)m j被節(jié)點(diǎn)s i感知的概率為

所有傳感器節(jié)點(diǎn)對(duì)監(jiān)測(cè)點(diǎn)mj的聯(lián)合感知概率為:

式中:Sall為監(jiān)測(cè)區(qū)域內(nèi)的所有無(wú)線傳感器節(jié)點(diǎn)。假設(shè)監(jiān)測(cè)區(qū)域?yàn)榫匦?，面積為L(zhǎng)Wm2。為便于計(jì)算，將該矩形劃分為L(zhǎng)W個(gè)面積相等的網(wǎng)格，監(jiān)測(cè)節(jié)點(diǎn)m位于網(wǎng)格的中心點(diǎn)位置。通過(guò)上式(3)計(jì)算出所有監(jiān)測(cè)點(diǎn)的聯(lián)合感知概率，累加之和即為覆蓋面積。覆蓋率C r可表示如下:

所求問(wèn)題描述如下:

1.2 網(wǎng)絡(luò)連通描述

網(wǎng)絡(luò)連通為WSN的最基本要求，因此我們?cè)诒ＷC最大覆蓋率的同時(shí)要使整個(gè)網(wǎng)絡(luò)保持連通狀態(tài)。為便于計(jì)算，假設(shè)2R＝R c。建立有向圖鄰接矩陣Mv，其用于存儲(chǔ)任意兩節(jié)點(diǎn)的連通情況，根據(jù)式(6)判斷是否連通，M v[i][j]＝1表示第i個(gè)節(jié)點(diǎn)可向第j個(gè)節(jié)點(diǎn)傳送信息(即單向連通)，當(dāng)其值為0表示不連通，再根據(jù)文獻(xiàn)[17]的矩陣冪算法判斷整個(gè)網(wǎng)絡(luò)是否連通，矩陣S v由式(7)計(jì)算得出。

式中:n為傳感器節(jié)點(diǎn)數(shù)目，若S v中存在元素為0，網(wǎng)絡(luò)不連通；反之則連通。

1.3 有效覆蓋率描述

文獻(xiàn)[18]提到了節(jié)點(diǎn)溢出面積計(jì)算，討論了節(jié)點(diǎn)輻射(感知)溢出監(jiān)測(cè)區(qū)域的情況。本文據(jù)此提出一種有效覆蓋率，因?yàn)橐绯雒娣e較大時(shí)，不僅浪費(fèi)了節(jié)點(diǎn)的輻射能量，而且當(dāng)節(jié)點(diǎn)能量耗盡后，網(wǎng)絡(luò)將出現(xiàn)較大的覆蓋空洞，二次部署也較麻煩。故網(wǎng)絡(luò)的有效覆蓋率越高，越能說(shuō)明網(wǎng)絡(luò)的穩(wěn)定性和適應(yīng)性越好。有效覆蓋率用C t表示。

定義1(最大化覆蓋面積) 若傳感器節(jié)點(diǎn)的感知范圍沒(méi)有超出監(jiān)測(cè)區(qū)域，且任意傳感器節(jié)點(diǎn)之間無(wú)重疊部分，即傳感器群感知最大面積C m。如圖1所示，一個(gè)傳感器節(jié)點(diǎn)覆蓋了12個(gè)監(jiān)測(cè)點(diǎn)，故C m＝4×12＝48。

圖1 最大化覆蓋面積

定義2(有效覆蓋面積) 傳感器節(jié)點(diǎn)感知范圍內(nèi)的監(jiān)測(cè)區(qū)域面積為有效面積，用C v表示，如圖2。通過(guò)計(jì)算可知有效覆蓋面積為C v＝63，C m＝9×12＝108，故

圖2 有效覆蓋面積圖

2 基本的麻雀搜索算法

在麻雀覓食的過(guò)程中，分為探索者和追隨者兩部分，探索者在種群中負(fù)責(zé)尋找食物并為整個(gè)麻雀種群提供覓食區(qū)域和方向，而追隨者則是追隨探索者的位置來(lái)獲取食物。為了獲得食物，麻雀通?？梢圆捎锰剿髡吆妥冯S者這兩種行為策略進(jìn)行覓食，種群中的個(gè)體會(huì)監(jiān)視群體中其他個(gè)體的行為，并且該種群中的捕食者會(huì)與高食物資源的同伴爭(zhēng)奪食物，以提高自己的捕食率。此外，當(dāng)麻雀種群意識(shí)到危險(xiǎn)時(shí)會(huì)做出反捕食行為。

在模擬實(shí)驗(yàn)中，我們需要使用虛擬麻雀來(lái)尋找食物。麻雀的位置可以用以下矩陣表示:

式中:n是麻雀的數(shù)量，d表示要優(yōu)化的變量的維數(shù)。然后，所有麻雀的適應(yīng)度值可以用以下向量表示:

式中:n表示麻雀的數(shù)量，F(xiàn) x中每行的值表示個(gè)體的適應(yīng)值。在SSA中，具有較好適應(yīng)度值的探索者在搜索過(guò)程中優(yōu)先獲得食物。此外，因?yàn)樘剿髡哓?fù)責(zé)尋找食物和引導(dǎo)整個(gè)種群的流動(dòng)。所以，探索者可以在更廣泛的地方尋找食物。根據(jù)規(guī)則(9)和(10)，在每次迭代過(guò)程中，探索者的位置更新如下:

式中:t代表當(dāng)前迭代數(shù)，itermax是一個(gè)常數(shù)，表示最大的迭代次數(shù)，X i，j表示第i個(gè)麻雀在第j維中的位置信息。α∈(0，1)是一個(gè)隨機(jī)數(shù)，R2(R2∈[0，1])和ST(ST∈[0.5，1])分別表示預(yù)警值和安全值，Q是服從正態(tài)分布的隨機(jī)數(shù)，L表示一個(gè)1×d的矩陣，其中該矩陣內(nèi)每個(gè)元素全部為1，當(dāng)R2

追隨者的位置更新描述如下:

式中:X P是目前探索者所占據(jù)的最優(yōu)位置，Xworse則表示當(dāng)前全局最差的位置，A表示一個(gè)1×d的矩陣，其中每個(gè)元素隨機(jī)賦值為1或－1，并且A＋＝AT(AAT)－1。當(dāng)i>n/2時(shí)，這表明，適應(yīng)度值較低的第i個(gè)追隨者獲得很少食物，處于十分饑餓的狀態(tài)，此時(shí)需要飛往其他地方覓食，以獲得更多的能量。

當(dāng)意識(shí)到危險(xiǎn)時(shí)，麻雀種群會(huì)做出反捕食行為，其數(shù)學(xué)表達(dá)式如下:

式中:Xbest是當(dāng)前的全局最優(yōu)位置。β作為步長(zhǎng)控制參數(shù)，是服從均值為0，方差為1的正態(tài)分布的隨機(jī)數(shù)。K∈[－1，1]是一個(gè)隨機(jī)數(shù)，f i則是當(dāng)前麻雀?jìng)€(gè)體的適應(yīng)度值，f g和f w分別是當(dāng)前全局最佳和最差的適應(yīng)度值，ε是最小的常數(shù)，以避免分母出現(xiàn)零。

為簡(jiǎn)單起見(jiàn)，當(dāng)f i>f g表示此時(shí)的麻雀正處于種群的邊緣，極其容易受到捕食者的攻擊。f i＝f g時(shí)，這表明處于種群中間的麻雀意識(shí)到了危險(xiǎn)，需要靠近其他的麻雀以此盡量減少它們被捕食的風(fēng)險(xiǎn)。K表示麻雀移動(dòng)的方向同時(shí)也是步長(zhǎng)控制參數(shù)。

3 一種增強(qiáng)型麻雀搜索算法

3.1 非線性收斂因子

在SSA中，探索者的比例因子pd是一個(gè)固定值，其值為0.2，這與算法的早期和后期策略相同，因此不靈活，容易導(dǎo)致算法收斂速度慢。為了提高算法的搜索效率，本文提出了一個(gè)收斂因子∝來(lái)約束原比例因子。圖3描繪了收斂因子，其數(shù)學(xué)描述如下:

圖3 非線性收斂因子

T是最大迭代次數(shù)，t是當(dāng)前迭代次數(shù)。如圖3所示，∝的值從1非線性減小到0，在迭代的早期，∝值較大，即探索者個(gè)數(shù)較多，有利于全局優(yōu)化搜索，加快算法的收斂速度。在迭代的后期，∝值較小，即探索者個(gè)數(shù)較少，集中于理論最優(yōu)值附近，有利于局部尋優(yōu)，從而提高解的精度。

3.2 柯西變異算子

柯西高斯變異算子[19]，可以很大程度上提高算法全局勘探能力，收斂精度以及穩(wěn)定度。比如近年來(lái)柯西逆累積分布改進(jìn)的鯨魚優(yōu)化算法[20]，基于柯西變異的蟻獅優(yōu)化算法[21]均得到了良好的優(yōu)化效果。

柯西分布如下:

柯西分布從峰值向兩側(cè)下降相對(duì)平緩，麻雀?jìng)€(gè)體受局部的極值點(diǎn)約束力在柯西變異后下降，并且柯西分布的峰值相對(duì)較小，麻雀?jìng)€(gè)體在變異后會(huì)花費(fèi)相對(duì)較少的時(shí)間來(lái)搜索相鄰區(qū)間，把更多的時(shí)間放在搜尋全局最優(yōu)值上，使得增強(qiáng)的麻雀搜索算法在尋找全局的最優(yōu)值方面具有很好的調(diào)節(jié)能力。利用上述柯西分布特點(diǎn)對(duì)麻雀搜索算法進(jìn)行優(yōu)化改進(jìn)，在探索者的狀態(tài)上引入服從柯西分布的隨機(jī)向量，公式如下:

式中:x′為初始位置x的更新位置，Cauchy(0，1)是τ＝1時(shí)的標(biāo)準(zhǔn)柯西隨機(jī)分布；參數(shù)γ是用來(lái)表示柯西分布變異強(qiáng)度，公式如下:

式中:f(x)為當(dāng)前探索者個(gè)體適應(yīng)度值，worst為當(dāng)前種群最差適應(yīng)值，T為最大迭代次數(shù)，參數(shù)θ為控制柯西變異強(qiáng)度的系數(shù)。

3.3 一種新穎的越界處理方法

大多數(shù)情況下，研究者們對(duì)于種群個(gè)體的越界行為處理的很簡(jiǎn)單，直接把位于搜索區(qū)域之外的個(gè)體重定位到距離目標(biāo)區(qū)域最近的邊界域，即區(qū)域邊界。這樣處理雖然簡(jiǎn)單，但是無(wú)意中降低了個(gè)體的差異性，使得種群無(wú)法更好的進(jìn)行的全局尋優(yōu)。因此，本文提出一種新穎的越界處理方法，公式如下:

公式如其中x′為越界個(gè)體x的更新位置，lb為搜索區(qū)域下界，ub為搜索區(qū)域上界，μ為0～1之間的隨機(jī)數(shù)，σ為介于0～1之間的越界處理因子。

增強(qiáng)型麻雀搜索算法流程如下。

①設(shè)置參數(shù):最大迭代次數(shù)Tmax、麻雀種群數(shù)量pop、意識(shí)到危險(xiǎn)的麻雀數(shù)量SD。

②初始化麻雀種群位置，計(jì)算各個(gè)體適應(yīng)度值并進(jìn)行排序，找出最佳個(gè)體和最差個(gè)體，然后按照比例確定探索者數(shù)量。

③每次迭代時(shí)計(jì)算非線性收斂因子∝，以∝為探索者比例確定探索者數(shù)量，然后使用式(11)更新探索者位置，實(shí)現(xiàn)探索者進(jìn)行食物的全局搜索，并且進(jìn)行越界處理。

④使用式(12)更新追隨者位置，使得跟隨者不斷地靠近探索者位置。

⑤如果預(yù)警者發(fā)現(xiàn)潛在危險(xiǎn)，則使用式(13)快速離開(kāi)危險(xiǎn)位置，尋找更為安全的食物源。

⑥在麻雀搜索食物之后，對(duì)麻雀?jìng)€(gè)體適應(yīng)度值進(jìn)行大小排序。

⑦判斷該算法是否到達(dá)最優(yōu)迭代次數(shù)，若到達(dá)，則獲得最佳食物位置，否則轉(zhuǎn)至步驟③。

⑧在進(jìn)入循環(huán)迭代后，當(dāng)麻雀種群中相鄰兩次迭代的最優(yōu)值相同時(shí)，我們認(rèn)為算法陷入局部最優(yōu)，此時(shí)使用式(16)變異種群，跳出局部最優(yōu)。

3.4 增強(qiáng)型麻雀搜索算法時(shí)間復(fù)雜度分析

假設(shè)算法最大迭代次數(shù)為T，種群規(guī)模為N，優(yōu)化問(wèn)題的維數(shù)為D。在SSA算法中，初始化種群，其時(shí)間復(fù)雜度為O(ND)。每一次迭代需要完成以下步驟，先計(jì)算種群的適應(yīng)度值并找出種群中最優(yōu)個(gè)體，其時(shí)間復(fù)雜度為O(N)，之后麻雀?jìng)€(gè)體更新位置，其時(shí)間復(fù)雜度為O(N)，故一次迭代的時(shí)間復(fù)雜度為O(N＋N)?？偟臅r(shí)間復(fù)雜度為O[T(N＋N)＋ND]，即O(TN)。相比于SSA，ESSA增加了非線性收斂因子和柯西變異算子，仍屬于麻雀?jìng)€(gè)體更新位置的操作，并沒(méi)有增加額外的時(shí)間復(fù)雜度，故ESSA總的時(shí)間復(fù)雜度和SSA一致。

3.5 基于ESSA算法的覆蓋優(yōu)化步驟

①設(shè)置傳感器的組數(shù)(種群大小)N，每組傳感器節(jié)點(diǎn)數(shù)目(維數(shù))D以及監(jiān)測(cè)區(qū)域的范圍。

②初始化N組傳感器節(jié)點(diǎn)的位置和半徑，即I s，隨機(jī)選擇一組I1為第一代解。

③根據(jù)式(4)求出每組傳感器部署方案的覆蓋率，最優(yōu)解為當(dāng)前最大覆蓋率對(duì)應(yīng)的傳感器節(jié)點(diǎn)按部署方案。

④將ESSA算法用于優(yōu)化每組部署方案的覆蓋率，若節(jié)點(diǎn)位置處在監(jiān)測(cè)區(qū)域外，則利用式(18)將節(jié)點(diǎn)重定位到合理的區(qū)域內(nèi)，算法結(jié)束后將會(huì)得到覆蓋率最大的一組傳感器節(jié)點(diǎn)部署方案I2。

⑤按照傳感器覆蓋率大小排序并根據(jù)式(7)判斷網(wǎng)絡(luò)是否連通，若不連通則選擇次優(yōu)方案，直至找到第一組連通的部署方案。

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

為了驗(yàn)證混合策略的有效性，選取了四個(gè)基準(zhǔn)函數(shù)進(jìn)行數(shù)值仿真，并與基本的SSA算法和其他改進(jìn)算法進(jìn)行對(duì)比，其中實(shí)驗(yàn)參數(shù)與其他文獻(xiàn)對(duì)應(yīng)的參數(shù)一致。參與對(duì)比的算法如表1所示，實(shí)驗(yàn)采用的4個(gè)基準(zhǔn)測(cè)試函數(shù)詳細(xì)信息如表2所示，其中F1為單模態(tài)基準(zhǔn)測(cè)試函數(shù)，F(xiàn)2為多模態(tài)基準(zhǔn)函數(shù)，F(xiàn)3，F(xiàn)4為固定維多模態(tài)基準(zhǔn)函數(shù)。

表1 對(duì)比算法

表2 基準(zhǔn)測(cè)試函數(shù)

4.1 基準(zhǔn)函數(shù)優(yōu)化性能測(cè)試

對(duì)于所有算法，都使用了種群大小和最大迭代次數(shù)分別為30個(gè)和100次，并且單獨(dú)運(yùn)行30次，實(shí)驗(yàn)結(jié)果取平均值進(jìn)行比較，比較結(jié)果如表3所示。

表3 基準(zhǔn)函數(shù)優(yōu)化結(jié)果對(duì)比

從表3和圖4可以看出，ESSA算法較其他算法均取得了更好的收斂結(jié)果，對(duì)于單模態(tài)基準(zhǔn)測(cè)試函數(shù)F1，該算法雖然在前20代最優(yōu)值差于ML-ALO算法，但在最終結(jié)果上較其他五種算法至少提高了2個(gè)數(shù)量級(jí)，且在算法穩(wěn)定性上也更穩(wěn)定。對(duì)于多模態(tài)基準(zhǔn)測(cè)試函數(shù)F2，因?yàn)槎喾搴瘮?shù)包含許多局部最優(yōu)值，其數(shù)量隨問(wèn)題規(guī)模呈指數(shù)增長(zhǎng)，因此，如果以評(píng)估優(yōu)化算法的探索能力為目的，這類測(cè)試問(wèn)題就變得非常有用。根據(jù)表中實(shí)驗(yàn)結(jié)果來(lái)看，ESSA算法最優(yōu)值優(yōu)于DACQPSO算法，近乎是其他四種對(duì)比算法最優(yōu)值的兩倍。這表明ESSA具有很好的勘探能力。這是由于ESSA算法中的綜合探索機(jī)制導(dǎo)致該算法走向全局最優(yōu)。對(duì)于固定維多模態(tài)基準(zhǔn)函數(shù)F3，F(xiàn)4，ESSA在收斂速度和尋優(yōu)精度上都明顯由于其他五種算法，且在迭代前期的探索性和迭代后期的開(kāi)發(fā)性都優(yōu)于其他五種算法，這表明ESSA在保證探索能力的同時(shí)也能充分保證開(kāi)發(fā)能力，還能保持較高的種群差異性。

圖4 優(yōu)化測(cè)試函數(shù)收斂曲線對(duì)比

綜上所述，ESSA對(duì)4個(gè)基準(zhǔn)測(cè)試函數(shù)的尋優(yōu)性能有明顯的提升，且穩(wěn)定性好，魯棒性強(qiáng)。同時(shí)ESSA的收斂速度也明顯優(yōu)于其他五種算法，且實(shí)時(shí)性表現(xiàn)良好。由此證明了ESSA算法改進(jìn)的可行性和優(yōu)越性。

4.2 WSN覆蓋優(yōu)化

4.2.1 實(shí)驗(yàn)設(shè)置

為了充分驗(yàn)證ESSA算法對(duì)WSN節(jié)點(diǎn)覆蓋的優(yōu)化性能，選取基本SSA算法和不同文獻(xiàn)中的4種改進(jìn)算法做對(duì)比，參考文獻(xiàn)及對(duì)比算法如表1所示。此外，幾種對(duì)比算法仿真實(shí)驗(yàn)的參數(shù)均一致。且為使實(shí)驗(yàn)更具說(shuō)服力，每種對(duì)比算法的仿真實(shí)驗(yàn)獨(dú)立運(yùn)行30次，取平均覆蓋率進(jìn)行對(duì)比。需要注意的是對(duì)于改進(jìn)蟻獅算法(ML-ALO)的覆蓋優(yōu)化實(shí)驗(yàn)數(shù)據(jù)來(lái)自文獻(xiàn)[14]。

4.2.2 監(jiān)測(cè)區(qū)域?yàn)?0×20覆蓋優(yōu)化對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置如表4所示，表5給出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法和MS-ALO算法的平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖5和圖6分別為ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法優(yōu)化后該區(qū)域節(jié)點(diǎn)分布圖和收斂曲線圖。

圖5 優(yōu)化后節(jié)點(diǎn)分布圖

表4 參數(shù)設(shè)置

表5 覆蓋率優(yōu)化結(jié)果對(duì)比

從圖6可以清晰的看出基本SSA算法在第50代左右覆蓋率達(dá)到90%左右，雖然在前50代中取得了最好的網(wǎng)絡(luò)覆蓋率，但此后一直陷入了局部最優(yōu)。而DACQPSO算法相比與ESSA算法來(lái)說(shuō)雖然網(wǎng)絡(luò)覆蓋率都在穩(wěn)步提高，但是ESSA算法提升的速率更快，且在130代左右就達(dá)到了DACQPSO算法的最大網(wǎng)絡(luò)覆蓋率，相比于DACQPSO算法快了370代。IGWO算法雖然有最高的初始覆蓋率81.5%，但此后一直未跳出局部最優(yōu)。IWOA算法覆蓋率有所提高但收斂速度過(guò)慢，在后350代覆蓋率只提升了不到3%。這說(shuō)明ESSA可以很好地平衡勘探開(kāi)發(fā)階段，這種能力來(lái)自于非線性收斂因子對(duì)生產(chǎn)者的數(shù)量隨著迭代次數(shù)而減小使全局搜索和局部搜索更為平衡合理。

圖6 覆蓋優(yōu)化收斂曲線

由表5可以看出，在相同的實(shí)驗(yàn)參數(shù)下，ESSA算法運(yùn)行三十次所得的平均覆蓋率相比DACQPSO算法和基本的SSA算法分別提高了9.1%和4.6%，較于IGWO算法和IWOA算法提高均超過(guò)10%。雖然MS-ALO算法覆蓋率達(dá)到第二高的93.46%，高于DACQPSO算法但仍少于ESSA算法的96.25%覆蓋率。

同時(shí)從圖5可以看出相比于基本SSA算法和四種改進(jìn)的對(duì)比算法優(yōu)化效果較差，且易出現(xiàn)覆蓋空洞的問(wèn)題，ESSA算法優(yōu)化后的節(jié)點(diǎn)分布更加均勻，節(jié)點(diǎn)冗余更少，無(wú)線網(wǎng)絡(luò)覆蓋范圍更加廣泛。

4.2.3 監(jiān)測(cè)區(qū)域?yàn)?0×50覆蓋優(yōu)化對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置如表6所示，表7給出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法、MS-ALO算法的平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖7和圖8分別為ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法優(yōu)化后該區(qū)域節(jié)點(diǎn)分布圖和收斂曲線圖。

表6 參數(shù)設(shè)置

由表7可知，ESSA算法進(jìn)行30次覆蓋優(yōu)化的平均覆蓋率相比基本SSA算法、DACQPSO算法、IGWO算法、IWOA算法分別提高了4.92%、10.16%、12.92%和10.35%。由圖7所示分布節(jié)點(diǎn)中可以看出DACQPSO算法、IGWO算法和IWOA算法優(yōu)化后的區(qū)域節(jié)點(diǎn)覆蓋盲區(qū)較大，而ESSA算法優(yōu)化后節(jié)點(diǎn)分布更加均勻，極大改善了這三種改進(jìn)算法節(jié)點(diǎn)冗余的現(xiàn)象。表7中MS-ALO算法的覆蓋率高達(dá)96.45%，超出ESSA算法2.77%。但是在文獻(xiàn)[14]中有40個(gè)傳感器節(jié)點(diǎn)，多出本實(shí)驗(yàn)5個(gè)。因此通過(guò)式(8)計(jì)算有效覆蓋率可知，ESSA算法的有效覆蓋率為85.24%，MS-ALO算法的有效覆蓋率為76.79%，ESSA算法有效覆蓋率更高。這表明柯西變異算子能有效提高算法的全局勘探能力，但本文提出的控制柯西分布變異強(qiáng)度的因子更加合理，且綜合機(jī)制優(yōu)于MS-ALO算法。

表7 覆蓋率優(yōu)化結(jié)果對(duì)比

圖7 優(yōu)化后節(jié)點(diǎn)分布圖

從圖8可以看出在收斂速度上ESSA算法在不斷的向最優(yōu)值靠近，最終覆蓋率達(dá)到93.68%，SSA算法在運(yùn)行至50代時(shí)節(jié)點(diǎn)覆蓋率達(dá)到82%，之后的300代一直陷入局部最優(yōu)，直到350代后才跳出局部最優(yōu)，最后達(dá)到88.76%的節(jié)點(diǎn)覆蓋率，不如ESSA算法。相較于ESSA算法，DACQPSO算法、IGWO算法、IWOA算法收斂速度太慢，經(jīng)過(guò)500次迭代后覆蓋率增長(zhǎng)均低于10%，ESSA算法隨機(jī)部署時(shí)節(jié)點(diǎn)覆蓋率只有最低的36.92%，在500次迭代后增長(zhǎng)了56.76%。遠(yuǎn)遠(yuǎn)優(yōu)于對(duì)比算法。這表明ESSA算法在保證探索能力的同時(shí)也能充分保證開(kāi)發(fā)能力，還能保持較大的種群差異性。

圖8 覆蓋優(yōu)化收斂曲線

4.2.4 監(jiān)測(cè)區(qū)域?yàn)?00×100覆蓋優(yōu)化對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置如表8所示，表9給出了ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法、MS-ALO算法的平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖9和圖10分別為ESSA算法、SSA算法、DACQPSO算法、IGWO算法、IWOA算法優(yōu)化后該區(qū)域節(jié)點(diǎn)分布圖和收斂曲線圖。由表9可知，ESSA算法進(jìn)行30次覆蓋優(yōu)化的平均覆蓋率相比于基本SSA算法、DACQPSO算法、IGWO算法、IWOA算法分別提高了3.29%、10.68%、6.67%、7.32%，具有更好的覆蓋效果。由圖9所示分布節(jié)點(diǎn)中可以看出基本SSA算法優(yōu)化后的區(qū)域節(jié)點(diǎn)冗余較多，DACQPSO算法、IGWO算法、IWOA算法優(yōu)化后的區(qū)域節(jié)點(diǎn)覆蓋盲區(qū)較大，而ESSA算法優(yōu)化后節(jié)點(diǎn)分布均勻，冗余較少。

表8 參數(shù)設(shè)置

表9 覆蓋率優(yōu)化結(jié)果對(duì)比

圖9 優(yōu)化后節(jié)點(diǎn)分布圖

另外從圖10可以看出在收斂速度上，ESSA算法在不斷的向最優(yōu)值靠近，最終覆蓋率達(dá)到96.2%，SSA算法在運(yùn)行至50代時(shí)節(jié)點(diǎn)覆蓋率達(dá)到89%，之后運(yùn)行的100代一直陷入局部最優(yōu)，直到150代后跳出局部最優(yōu)，最后只達(dá)到92.91%的節(jié)點(diǎn)覆蓋率，不如ESSA算法。IWOA算法雖然在后面200代覆蓋率增長(zhǎng)最多，但在迭代結(jié)束只達(dá)到了88.88%的覆蓋率。IGWO算法收斂速度太慢，在隨機(jī)部署時(shí)就達(dá)到五種對(duì)比算法里最高覆蓋率80.01%，但經(jīng)過(guò)500次迭代后只增長(zhǎng)了9.3%。ESSA算法在500次迭代后增長(zhǎng)了21%左右，收斂速度遠(yuǎn)遠(yuǎn)優(yōu)于其他四種對(duì)比算法。對(duì)于MS-ALO算法來(lái)說(shuō)，雖然覆蓋率只有71.63%，但是在監(jiān)測(cè)面積，傳感器節(jié)點(diǎn)數(shù)量相同的情況下，它的感知半徑為7，本實(shí)驗(yàn)感知半徑為10。所以通過(guò)式(8)計(jì)算有效覆蓋率可知，ESSA算法的有效覆蓋率率為76.59%，MS-ALO算法的有效覆蓋率為71.63%，低于ESSA算法。

上述三個(gè)仿真實(shí)驗(yàn)結(jié)果表明，增強(qiáng)型的麻雀搜索算法具有適應(yīng)性強(qiáng)，收斂速度快，跳出局部最優(yōu)能力強(qiáng)等特點(diǎn)。將ESSA算法應(yīng)用到無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化問(wèn)題，能夠快速有效的提升網(wǎng)絡(luò)覆蓋率，減少覆蓋盲區(qū)，降低覆蓋成本。

5 結(jié)束語(yǔ)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋率最大化的問(wèn)題，本文提出了一種增強(qiáng)型的麻雀搜索算法實(shí)現(xiàn)傳感器節(jié)點(diǎn)的覆蓋優(yōu)化。該算法模擬了麻雀的覓食和反捕食行為之后加入了非線性收斂因子，增強(qiáng)了算法的全局探索和局部開(kāi)發(fā)的平衡能力，柯西變異算子改善了算法易陷入局部最優(yōu)的問(wèn)題。然后通過(guò)不同形態(tài)基準(zhǔn)函數(shù)的優(yōu)化求解，并與基本麻雀搜索算法和其他改進(jìn)智能算法相比較，驗(yàn)證了該算法在搜索精度、收斂速度和穩(wěn)定性等方面與其他算法相比具有很強(qiáng)的競(jìng)爭(zhēng)力。

將ESSA算法進(jìn)一步應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題中，并選取了基本麻雀搜索算法和4種改進(jìn)的智能算法，在相同條件下進(jìn)行對(duì)比試驗(yàn)。實(shí)驗(yàn)結(jié)果表明基于ESSA的WSN覆蓋優(yōu)化算法取得的平均覆蓋率均優(yōu)于同條件下其他對(duì)比算法，通過(guò)節(jié)點(diǎn)分布圖來(lái)看ESSA算法優(yōu)化后的節(jié)點(diǎn)分布更加均勻，覆蓋盲區(qū)更小，且節(jié)點(diǎn)冗余更少。通過(guò)對(duì)比覆蓋優(yōu)化收斂曲線，更驗(yàn)證了ESSA算法對(duì)收斂速度的有效提升。因此可以說(shuō)本文提出的算法能夠很好地提高無(wú)線傳感器網(wǎng)絡(luò)的覆蓋率，直接節(jié)省了網(wǎng)絡(luò)覆蓋所花費(fèi)的成本。然而，如何保證在較高覆蓋率的情況下進(jìn)一步延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生存壽命，更大限度的節(jié)省網(wǎng)絡(luò)覆蓋所花費(fèi)的成本，將是ESSA算法下一步需要解決的問(wèn)題。