徐欽帥，何 慶?，魏康園

(1.貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽(yáng)550025；2.貴州大學(xué)貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴陽(yáng)550025)

無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是一種自組織網(wǎng)絡(luò)，由能夠進(jìn)行傳感、處理和無(wú)線通信的傳感器節(jié)點(diǎn)組成[1]。網(wǎng)絡(luò)區(qū)域覆蓋是WSN中的一個(gè)關(guān)鍵問(wèn)題，對(duì)傳感器節(jié)點(diǎn)的覆蓋分布進(jìn)行優(yōu)化，能夠改善網(wǎng)絡(luò)的服務(wù)質(zhì)量和能耗平衡。

近年來(lái)，群體智能算法被廣泛應(yīng)用于WSN傳感器節(jié)點(diǎn)覆蓋優(yōu)化問(wèn)題中，如周海鵬等[2]提出了一種動(dòng)態(tài)自適應(yīng)混沌量子粒子群算法，對(duì)比其他改進(jìn)粒子群算法的覆蓋率有所提高，但其精度及節(jié)點(diǎn)均勻度不夠理想；胡小平等[3]基于多種策略改進(jìn)灰狼優(yōu)化算法用于節(jié)點(diǎn)覆蓋優(yōu)化，覆蓋率和收斂速度均優(yōu)于基本灰狼優(yōu)化算法，但其優(yōu)化結(jié)果與其他算法相比并不具備優(yōu)勢(shì)；李光輝等[4]提出了一種結(jié)合Voronoi圖、虛擬力擾動(dòng)和布谷鳥(niǎo)搜索算法的網(wǎng)絡(luò)覆蓋優(yōu)化算法，有效提高了覆蓋率；付光杰等[5]借鑒貝葉斯預(yù)測(cè)算法思想改進(jìn)人工蜂群算法，取得了較好的覆蓋效果，但要實(shí)現(xiàn)近似完全覆蓋仍需改善。上述研究成果表明，多種不同群體智能算法應(yīng)用于WSN網(wǎng)絡(luò)覆蓋優(yōu)化行之有效，但優(yōu)化效果仍有待提高。

蟻獅優(yōu)化算法ALO(Ant Lion Optimizer)是一種新的群體智能優(yōu)化算法，由澳大利亞學(xué)者Seyedali于2015年提出[6]。由于其初始參數(shù)少和收斂精度高的優(yōu)點(diǎn)，已被廣泛應(yīng)用于WSN數(shù)據(jù)收集[7]、天線陣列合成[8]、光伏參數(shù)尋優(yōu)[9]和無(wú)人機(jī)航徑規(guī)劃[10]等多種工程領(lǐng)域。研究證明[6]ALO算法的尋優(yōu)性能優(yōu)于粒子群算法、遺傳算法和布谷鳥(niǎo)搜索算法等7種智能算法。因此，將ALO算法應(yīng)用于WSN覆蓋優(yōu)化值得深入探索。然而，與其他智能算法相似，ALO算法具有早熟收斂、易陷入局部最優(yōu)等缺點(diǎn)。對(duì)此，國(guó)內(nèi)外許多學(xué)者對(duì)其進(jìn)行了改進(jìn)，如Dinkar等[11]引入反向?qū)W習(xí)機(jī)制，并利用拉普拉斯分布代替正態(tài)分布，擴(kuò)大了算法搜索范圍；Yao等[12]采用萊維飛行的不均勻步長(zhǎng)作為螞蟻游走步長(zhǎng)，基于1/5原理動(dòng)態(tài)調(diào)整蟻獅陷阱，改善了算法的收斂性能；張振興等[13]使用Tent映射初始化種群位置并引導(dǎo)螞蟻游走，采用錦標(biāo)賽選擇策略，形成全局與局部并行搜索模式，提高了算法的尋優(yōu)效率。盡管改進(jìn)算法各有優(yōu)勢(shì)，但如何使算法能夠跳出局部最優(yōu)、提升收斂速度，以及如何實(shí)現(xiàn)全局探索與局部開(kāi)發(fā)能力的平衡仍是難點(diǎn)。

為了實(shí)現(xiàn)WSN覆蓋率的最大化，針對(duì)ALO算法的缺陷，本文提出一種基于連續(xù)性邊界收縮因子、位置更新動(dòng)態(tài)權(quán)重系數(shù)和動(dòng)態(tài)混合變異策略的改進(jìn)蟻獅算法MS-ALO(Mixed Strategy based Ant Lion Optimizer)，應(yīng)用于WSN傳感器節(jié)點(diǎn)覆蓋優(yōu)化。仿真實(shí)驗(yàn)首先通過(guò)對(duì)基準(zhǔn)函數(shù)的優(yōu)化對(duì)比，驗(yàn)證改進(jìn)策略的有效性；然后將MS-ALO算法應(yīng)用于WSN覆蓋優(yōu)化問(wèn)題，選取不同文獻(xiàn)中4種算法在相同條件下進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證該算法的應(yīng)用價(jià)值。

1 問(wèn)題模型分析

假設(shè)在面積為S＝L1×L2的二維正方形WSN監(jiān)測(cè)區(qū)域內(nèi)，隨機(jī)部署N個(gè)同構(gòu)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)集合定義為 Z ＝ {z1，z2，…，zi，…，zN}，zi位置坐標(biāo)為(xi，yi)，i＝ 1，2，…，N，每個(gè)節(jié)點(diǎn)的感知半徑均為Rs，通信半徑均為Rc。由于傳感器節(jié)點(diǎn)的感知范圍是一個(gè)以自身為圓心、Rs為固定半徑的封閉圓形區(qū)域，為方便計(jì)算，將該監(jiān)測(cè)區(qū)域離散化為m×n個(gè)待覆蓋像素點(diǎn)，其集合為 Hj＝(xj，yj)，j∈{1，2，…，m×n}，每個(gè)像素點(diǎn)的幾何中心點(diǎn)即覆蓋優(yōu)化目標(biāo)位置。

若像素點(diǎn)Hj與任意一個(gè)節(jié)點(diǎn)距離小于或等于感知半徑Rs，則認(rèn)定Hj已被網(wǎng)絡(luò)覆蓋。節(jié)點(diǎn)zi與像素點(diǎn)Hj的間距定義為

像素點(diǎn)Hj被傳感器節(jié)點(diǎn)zi感知的概率p(zi，Hj)定義為

式中：Re為傳感器節(jié)點(diǎn)的感知誤差；λ為感知衰減系數(shù)。

在該區(qū)域內(nèi)，任意一個(gè)像素點(diǎn)能同時(shí)被多個(gè)節(jié)點(diǎn)感知，其聯(lián)合感知概率p(Z，Hj)定義為

該區(qū)域的覆蓋率Rcov為節(jié)點(diǎn)集合Z所覆蓋的像素點(diǎn)總數(shù)與區(qū)域內(nèi)像素點(diǎn)總數(shù)的比值，定義為

因此，將式(4)作為文中改進(jìn)蟻獅算法求解WSN覆蓋優(yōu)化問(wèn)題的目標(biāo)函數(shù)，即所有位置變量在監(jiān)測(cè)區(qū)域范圍內(nèi)，利用改進(jìn)算法優(yōu)化求解覆蓋率Rcov的最大值。

2 蟻獅優(yōu)化算法基本原理

ALO算法原理源于自然界中蟻獅獵食螞蟻行為的啟發(fā)，描述如下：

隨機(jī)初始化種群位置，計(jì)算適應(yīng)度值，并采用輪盤(pán)賭方法選擇蟻獅修筑陷阱。

螞蟻在搜索空間內(nèi)隨機(jī)游走，定義為

式中：cumsum為位置累計(jì)；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)；r(t)為隨機(jī)數(shù)0或1，定義為

式中：m為在[0，1]內(nèi)的隨機(jī)數(shù)。

同時(shí)，為了使螞蟻的隨機(jī)游走保持在搜索空間內(nèi)，對(duì)其位置進(jìn)行歸一化處理，定義為

式中：bi和ai分別為第i個(gè)變量的上界和下界；di和ct分別為第t代時(shí)第i個(gè)變量的上界和下界。i

輪盤(pán)賭選擇的蟻獅位置影響著螞蟻的游走邊界，定義為

式中：dt和ct分別為所有變量在第t代的上界和下界；Antliontj為第t代第j只蟻獅的位置。

當(dāng)螞蟻圍繞陷阱隨機(jī)游走時(shí)，蟻獅會(huì)繼續(xù)深挖以防螞蟻逃出，使螞蟻游走邊界逐漸縮小直至滑落陷阱底部，該過(guò)程定義為

式中：I為邊界收縮因子，定義為

式中：w為由t和T決定的常數(shù)。

螞蟻滑落到陷阱底部被蟻獅捕捉，若種群中包含適應(yīng)度高于蟻獅的個(gè)體，則該個(gè)體將作為新蟻獅重筑陷阱，定義為

式中：Antliontj為第t次代第j只蟻獅的位置；Antti為第t代第i只螞蟻位置；f為適應(yīng)度函數(shù)。

選擇當(dāng)代最優(yōu)蟻獅作為精英蟻獅，同輪盤(pán)賭選擇蟻獅一起引導(dǎo)螞蟻的位置更新，定義為

式中：RtA為第t代繞輪盤(pán)賭選擇蟻獅的螞蟻隨機(jī)游走；RtE為第t代繞精英蟻獅的螞蟻隨機(jī)游走。

3 算法分析及混合改進(jìn)策略

3.1 連續(xù)性邊界收縮因子

在基本ALO算法中螞蟻圍繞陷阱游走階段，其邊界即搜索范圍逐漸縮小，以開(kāi)發(fā)陷阱鄰域最優(yōu)值。但由式(12)可知，邊界收縮因子I的變化呈現(xiàn)間斷增大趨勢(shì)，其間斷式增大易導(dǎo)致螞蟻遺漏部分區(qū)域，使算法易錯(cuò)過(guò)最優(yōu)值[14]；而從文獻(xiàn)[6]中ALO算法優(yōu)化單峰函數(shù)Sphere和Schwefel 2.21的收斂曲線可知，雖然其收斂精度在迭代后期時(shí)優(yōu)于PSO、BA和CS等算法，但由于I的間斷式增大，搜索邊界不均勻緩慢衰減，導(dǎo)致收斂速度劣于其他參比算法。

針對(duì)上述問(wèn)題，為了增強(qiáng)算法的遍歷性，使其更全面地搜索求解空間以及提高算法收斂速度，提出一種隨著算法迭代進(jìn)化而快速連續(xù)增大的邊界收縮因子，將螞蟻游走邊界更新方式定義為

式中：γ為收縮調(diào)節(jié)系數(shù)；λ為比例因子；經(jīng)過(guò)多次基準(zhǔn)函數(shù)優(yōu)化實(shí)驗(yàn)，選取γ＝400，λ＝20。

3.2 位置更新動(dòng)態(tài)權(quán)重系數(shù)

在精英化階段，螞蟻根據(jù)式(14)學(xué)習(xí)輪盤(pán)賭選擇蟻獅和精英蟻獅行為以更新位置。已知蟻獅被輪盤(pán)賭選擇概率為

式中：f(xi)為個(gè)體適應(yīng)度值。

由于精英蟻獅具有最優(yōu)適應(yīng)度值，由式(16)便有較大概率被選作輪盤(pán)賭選擇蟻獅[15]，導(dǎo)致螞蟻只繞精英蟻獅游走，而降低算法全局探索能力，如式(17)所示：

針對(duì)上述問(wèn)題，將基于迭代次數(shù)的動(dòng)態(tài)權(quán)重系數(shù)引入螞蟻位置更新式(14)，改進(jìn)為

在式(18)中，輪盤(pán)賭選擇蟻獅RtA的權(quán)重系數(shù)k1在迭代前期較大，使螞蟻在搜索空間內(nèi)探索更優(yōu)區(qū)域；而在后期，精英蟻獅鄰近最優(yōu)區(qū)域，其權(quán)重系數(shù)k2逐漸增大，使螞蟻在最優(yōu)區(qū)域鄰域開(kāi)發(fā)，以此提高算法全局探索與局部開(kāi)發(fā)的平衡能力。

3.3 動(dòng)態(tài)混合變異

由于游走邊界的收縮和精英蟻獅引導(dǎo)種群聚攏，導(dǎo)致種群多樣性減小，而易發(fā)生早熟收斂現(xiàn)象，陷入局部最優(yōu)。

為了使算法能有效跳出局部最優(yōu)，提出一種結(jié)合早熟收斂判斷方法與動(dòng)態(tài)混合變異的改進(jìn)策略。首先，采用文獻(xiàn)[16]中的早熟判斷方法，將第t代的全局適應(yīng)度方差αt定義為

式中：N為種群規(guī)模；ft(xi)為第i個(gè)個(gè)體在第t代的適應(yīng)度；ft

mean為第t代全局平均適應(yīng)度；fta為限定αt的標(biāo)定因子，定義為

然后，將個(gè)體間距Dt定義為

式中：L為搜索空間最大對(duì)角長(zhǎng)度；n為搜索維度；xtid為第t代時(shí)第i個(gè)個(gè)體在第d維的位置；xtmean為第t代時(shí)所有個(gè)體在第d維的位置平均值。

已知αt和Dt在種群完全聚集時(shí)將等于0，此時(shí)可能達(dá)到全局收斂或陷入局部最優(yōu)。為了進(jìn)一步區(qū)分，設(shè)當(dāng) αt＜β 且 Dt＜σ(β＝10－6，σ＝10－3)時(shí)，則判定算法已早熟收斂。

針對(duì)算法陷入局部最優(yōu)的困境，提出一種基于正態(tài)分布和柯西分布動(dòng)態(tài)調(diào)整的混合變異方法，對(duì)蟻獅位置Antliontj進(jìn)行變異擾動(dòng)操作，如式(22)所示：

式中：Antliontj＋1為第t＋1代的蟻獅位置；η 為調(diào)節(jié)系數(shù)；C(0，1)為服從柯西分布的變異因子；N(0，1)為服從正態(tài)分布的變異因子。

已知柯西分布比正態(tài)分布變異尺度更大[17]。在式(20)中，柯西變異因子系數(shù)w1與k1相似的是其取值均隨迭代次數(shù)遞減，不同的是w1取值范圍為[0 .1，2)，比 k1變化幅度更大，結(jié)合 C(0，1)相對(duì)較大的變異步長(zhǎng)，使算法能跳出局部最優(yōu)，探索更廣泛的區(qū)域；正態(tài)變異因子權(quán)重w2＝k2，隨迭代次數(shù)逐漸增大，較小的變異步長(zhǎng)以便算法快速收斂，并在最優(yōu)值鄰域進(jìn)行搜索。

同時(shí)，為了保證變異策略產(chǎn)生的新解始終朝向更優(yōu)區(qū)域移動(dòng)，每次操作復(fù)制M個(gè)當(dāng)代蟻獅位置進(jìn)行變異產(chǎn)生新解，最后在M＋1個(gè)候選解組成的解集中選擇最優(yōu)解進(jìn)入下一次迭代，文中所有實(shí)驗(yàn)取M＝20。

4 覆蓋優(yōu)化算法設(shè)計(jì)

基于MS-ALO算法的WSN覆蓋優(yōu)化的目標(biāo)為監(jiān)測(cè)區(qū)域覆蓋率Rcov的最大化；輸入為MS-ALO算法的種群規(guī)模N和最大迭代次數(shù)T，以及監(jiān)測(cè)區(qū)域面積S、像素點(diǎn)數(shù)m×n、傳感器節(jié)點(diǎn)數(shù)V和感知半徑Rs等參數(shù)；輸出為Rcov最優(yōu)適應(yīng)度值，以及傳感器節(jié)點(diǎn)分布坐標(biāo)。

MS-ALO算法的種群中每個(gè)個(gè)體代表區(qū)域內(nèi)所有節(jié)點(diǎn)的一個(gè)覆蓋分布；尋優(yōu)維度d＝2 V，則節(jié)點(diǎn)分布坐標(biāo)可表示為(2d－1，2d)。算法流程如圖1所示。

圖1 基于MS-ALO算法的WSN覆蓋優(yōu)化

具體算法步驟如下：

Step 1 輸入WSN監(jiān)測(cè)區(qū)域、傳感器節(jié)點(diǎn)及MS-ALO算法相關(guān)參數(shù)；

Step 2 在搜索空間即監(jiān)測(cè)區(qū)域內(nèi)，隨機(jī)初始化種群中的個(gè)體位置；

Step 3 初始化迭代次數(shù)t＝1；

Step 4 將節(jié)點(diǎn)覆蓋率Rcov作為目標(biāo)函數(shù)，根據(jù)式(4)計(jì)算種群適應(yīng)度，保存最優(yōu)個(gè)體作為精英蟻獅；

Step 5 利用輪盤(pán)賭方法選擇適應(yīng)度較高的蟻獅挖掘陷阱；

Step 6 由式(8)和式(9)計(jì)算螞蟻個(gè)體游走上下邊界；

Step 7 螞蟻在邊界內(nèi)根據(jù)式(5)和式(18)圍繞輪盤(pán)賭蟻獅和精英蟻獅游走，并在爬入陷阱時(shí)，根據(jù)式(15)更新游走邊界；

Step 8 計(jì)算螞蟻適應(yīng)度值，根據(jù)式(13)比較判斷，更新蟻獅位置并重新挖掘陷阱；

Step 9 基于當(dāng)前種群適應(yīng)度值及個(gè)體位置，根據(jù)式(19)和式(21)分別計(jì)算適應(yīng)度方差αt和個(gè)體間距 Dt；

Step 10 若 αt＜β 且 Dt＜σ，執(zhí)行 Step 11；否則，跳至Step 12；

Step 11 復(fù)制M個(gè)當(dāng)前最優(yōu)個(gè)體位置，分別根據(jù)式(22)進(jìn)行混合變異操作，并構(gòu)建當(dāng)前最優(yōu)個(gè)體與變異個(gè)體的新解集，從中選取適應(yīng)度最優(yōu)的個(gè)體并保存；

Step 12 更新迭代次數(shù)t＝t＋1，并判斷是否達(dá)到最大迭代次數(shù)，若是，結(jié)束算法并輸出覆蓋率最優(yōu)適應(yīng)度值和相應(yīng)節(jié)點(diǎn)部署坐標(biāo)位置；否則，跳至Step4循環(huán)迭代。

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

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

為了驗(yàn)證混合策略的有效性，選取12個(gè)基準(zhǔn)函數(shù)進(jìn)行數(shù)值仿真，并與基本ALO算法和文獻(xiàn)[11]提出的改進(jìn)OB-L-ALO算法進(jìn)行比較。實(shí)驗(yàn)采用的12個(gè)基準(zhǔn)函數(shù)的名稱(chēng)、數(shù)學(xué)表達(dá)式及其他參數(shù)情況如表1所示，其中：f1～f5為單峰函數(shù)；f6～f10為多峰函數(shù)；f11～f12為固定低維度下的多峰函數(shù)。

表1 基準(zhǔn)函數(shù)

為了保證算法優(yōu)化性能測(cè)試的公正性，基本ALO算法、MS-ALO算法的參數(shù)設(shè)置同文獻(xiàn)[11]中OB-L-ALO算法參數(shù)一致：種群規(guī)模N＝30，最大迭代次數(shù)T＝1 000。同時(shí)，為減小隨機(jī)干擾的影響，不同算法對(duì)于每個(gè)基準(zhǔn)函數(shù)均獨(dú)立運(yùn)行30次，并取實(shí)驗(yàn)結(jié)果平均值進(jìn)行比較。

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

表2記錄了 ALO算法、OB-L-ALO算法[11]與MS-ALO算法在相同測(cè)試條件下，對(duì)于12個(gè)基準(zhǔn)函數(shù)的優(yōu)化結(jié)果。圖2為ALO算法與MS-ALO算法對(duì)基準(zhǔn)函數(shù)優(yōu)化收斂過(guò)程對(duì)比，其中：Iteration表示迭代次數(shù)；Mean best so far表示算法運(yùn)行30次的平均適應(yīng)度值。

從表2和圖2可以看出，MS-ALO算法較其他算法均取得了更好的收斂結(jié)果。在單峰函數(shù)優(yōu)化方面，該算法對(duì)f1～f3的收斂精度較ALO算法提高了至少7個(gè)數(shù)量級(jí)，表明連續(xù)性邊界收縮因子策略能改善算法的遍歷性，提高算法收斂速度。

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

對(duì)于多峰函數(shù)優(yōu)化問(wèn)題，在30維搜索空間中，以具有大量局部極值點(diǎn)的非線性函數(shù)Rastrigin(f7)和Griewank(f8)為例，MS-ALO算法對(duì)其優(yōu)化的平均結(jié)果較ALO算法分別提高了14和9個(gè)數(shù)量級(jí)，較OB-L-ALO算法分別提高了10和3個(gè)數(shù)量級(jí)，表明改進(jìn)策略能使算法有效跳出局部最優(yōu)，該算法具有良好的多峰尋優(yōu)能力。

在固定低維度搜索空間的多峰函數(shù)優(yōu)化中，MS-ALO算法對(duì)于函數(shù)f11尋優(yōu)的平均最優(yōu)值已達(dá)到其理論最優(yōu)值，對(duì)于f12的優(yōu)化結(jié)果較參比算法也有所提高，且均值方差更小，驗(yàn)證了改進(jìn)算法的魯棒性。

綜上所述，MS-ALO算法對(duì)于基準(zhǔn)函數(shù)的優(yōu)化求解在收斂精度、收斂速度、多峰優(yōu)化能力和魯棒性等方面，均優(yōu)于基本ALO算法及其改進(jìn)算法OB-LALO，驗(yàn)證了混合改進(jìn)策略的有效性。因此，該算法可進(jìn)一步應(yīng)用于WSN的節(jié)點(diǎn)覆蓋優(yōu)化問(wèn)題。

5.2 WSN覆蓋優(yōu)化應(yīng)用

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

為了充分驗(yàn)證MS-ALO算法對(duì)WSN節(jié)點(diǎn)覆蓋的優(yōu)化性能，選取基本ALO算法和不同文獻(xiàn)中4種改進(jìn)算法，分別在相應(yīng)監(jiān)測(cè)區(qū)域?qū)Σ煌瑪?shù)量的傳感器節(jié)點(diǎn)進(jìn)行覆蓋優(yōu)化對(duì)比。參比文獻(xiàn)及其算法如表3所示，仿真實(shí)驗(yàn)參數(shù)與相應(yīng)文獻(xiàn)參數(shù)設(shè)置相同。參比文獻(xiàn)及算法

表3

5.2.2 與DACQPSO算法對(duì)比

實(shí)驗(yàn)參數(shù)設(shè)置與文獻(xiàn)[2]相同，如表4所示。

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

為了降低隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果的干擾，利用ALO算法和MS-ALO算法對(duì)該區(qū)域進(jìn)行20次優(yōu)化，取平均覆蓋率對(duì)比。表5給出了ALO算法、MS-ALO算法與DACQPSO算法平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖3和圖4分別為ALO算法和MS-ALO算法優(yōu)化后該區(qū)域節(jié)點(diǎn)分布圖和收斂曲線圖。

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

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

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

由表5可知，在相同測(cè)試條件下，MS-ALO算法運(yùn)行20次優(yōu)化的平均覆蓋率相比DACQPSO算法和基本ALO算法分別提高了6.31%和7.07%，較大程度地提高了網(wǎng)絡(luò)覆蓋率。同時(shí)，從圖3可以看出，基本ALO算法覆蓋優(yōu)化效果較差，MS-ALO算法優(yōu)化后節(jié)點(diǎn)分布更加均勻，無(wú)線網(wǎng)絡(luò)覆蓋范圍更加廣泛，且改善了文獻(xiàn)[2]中DACQPSO算法優(yōu)化節(jié)點(diǎn)分布區(qū)域邊界覆蓋盲區(qū)較大的問(wèn)題。

另一方面，已知文獻(xiàn)[2]中DACQPSO算法的迭代次數(shù)為150，取得了87.15%的網(wǎng)絡(luò)覆蓋率。而由圖4可知，MS-ALO算法和基本ALO算法在150代取得的平均覆蓋率分別為88.11%和82.97%，可知MS-ALO算法相比DACQPSO算法和ALO算法的覆蓋率分別提高了0.96%和5.14%，說(shuō)明位置更新動(dòng)態(tài)權(quán)重系數(shù)等改進(jìn)策略的引入提升了算法在迭代前期的全局搜索能力，有效地提高了相同迭代次數(shù)下的網(wǎng)絡(luò)覆蓋率。同時(shí)，從圖4可以看出，由于連續(xù)性邊界收縮因子的改進(jìn)，MS-ALO算法在380代開(kāi)始收斂，相比ALO算法提前了430代，提高收斂精度的同時(shí)，明顯加快了收斂速度。

5.2.3 與IGWO算法對(duì)比

參數(shù)設(shè)置與文獻(xiàn)[3]相同，如表6所示。

利用MS-ALO算法對(duì)該區(qū)域進(jìn)行20次覆蓋優(yōu)化，取平均覆蓋率對(duì)比。表7給出了ALO算法、MSALO算法與IGWO算法平均覆蓋率優(yōu)化結(jié)果對(duì)比。圖5和圖6分別為ALO算法和MS-ALO算法優(yōu)化后該區(qū)域節(jié)點(diǎn)分布圖和收斂曲線圖。

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

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

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

由表7可知，MS-ALO算法進(jìn)行20次覆蓋優(yōu)化的平均覆蓋率相比IGWO算法和ALO算法分別提高了2.17%和5.38%。在圖3所示節(jié)點(diǎn)分布中，ALO算法優(yōu)化后區(qū)域節(jié)點(diǎn)覆蓋盲區(qū)較大，MS-ALO算法優(yōu)化后節(jié)點(diǎn)分布更加均勻，改善了文獻(xiàn)[3]中IGWO算法節(jié)點(diǎn)區(qū)域聚集現(xiàn)象。

在收斂速度方面，已知文獻(xiàn)[3]中IGWO算法在100代時(shí)已經(jīng)收斂，而由圖4可知，MS-ALO算法在100代時(shí)平均覆蓋率為91.52%，相比IGWO算法降低了2.76%，且在550代時(shí)收斂。雖然本文算法的收斂速度差于IGWO算法，但由于改進(jìn)的邊界收縮因子隨著算法迭代進(jìn)化而快速連續(xù)增大，從圖4可以看出，本文算法相比基本ALO算法提前了300代收斂，收斂速度有了較大提升。

5.2.4 與VF-CS算法對(duì)比

參數(shù)設(shè)置與文獻(xiàn)[4]相同，如表8所示。

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

利用MS-ALO算法對(duì)該區(qū)域進(jìn)行30次優(yōu)化，取平均覆蓋率對(duì)比。表9為ALO算法、MS-ALO算法與VF-CS算法對(duì)不同傳感器節(jié)點(diǎn)數(shù)量的平均覆蓋優(yōu)化結(jié)果對(duì)比。圖7和圖8分別給出了ALO算法和MS-ALO算法優(yōu)化后該區(qū)域內(nèi)傳感器節(jié)點(diǎn)數(shù)為90和80的節(jié)點(diǎn)分布圖，圖9為相應(yīng)收斂曲線。

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

圖7 V＝90時(shí)優(yōu)化后節(jié)點(diǎn)分布

圖8 V＝80時(shí)優(yōu)化后節(jié)點(diǎn)分布

由表9可知，在相同的監(jiān)測(cè)區(qū)域，隨著部署節(jié)點(diǎn)數(shù)的增加，覆蓋率也在逐漸提高。在節(jié)點(diǎn)數(shù)為80、70、50和40時(shí)，MS-ALO算法優(yōu)化的平均覆蓋率相比于VF-CS算法分別提高了0.11%、1.37%、0.27%和1.43%；而在節(jié)點(diǎn)數(shù)為90和60時(shí)，則比VF-CS算法分別降低了0.09%和1.88%。相比于基本ALO算法，MS-ALO算法對(duì)不同數(shù)量節(jié)點(diǎn)優(yōu)化的平均覆蓋率則分別提高了8.68%、7.82%、14.2%、7.72%、8.88%和8.15%，表明動(dòng)態(tài)權(quán)重系數(shù)的引入能夠有效平衡算法的全局與局部搜索能力，從而有效提高算法的收斂精度。

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

同時(shí)，以節(jié)點(diǎn)數(shù)為90和80為例，從圖7和圖8可以看出，MS-ALO算法相比ALO算法更好地實(shí)現(xiàn)了區(qū)域節(jié)點(diǎn)部署優(yōu)化。在收斂速度方面，已知文獻(xiàn)[4]中VF-CS算法僅用50次迭代便實(shí)現(xiàn)了收斂。從圖9可以看出，MS-ALO算法對(duì)于節(jié)點(diǎn)數(shù)為90和80的覆蓋優(yōu)化實(shí)驗(yàn)中，分別在695代和700代收斂，而ALO算法則分別迭代至935代和950代開(kāi)始收斂。因此，MS-ALO算法的收斂速度雖差于VFCS算法，但相比基本ALO算法仍有很大地提高。

5.2.5 與BPABC算法對(duì)比

參數(shù)設(shè)置與文獻(xiàn)[5]相同，如表10所示。

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

利用MS-ALO算法對(duì)該區(qū)域進(jìn)行200次覆蓋優(yōu)化，取平均覆蓋率對(duì)比。表11為ALO算法、MSALO算法與BPABC算法的平均覆蓋率和最差覆蓋率數(shù)值對(duì)比。圖10和圖11分別為ALO算法和MSALO算法優(yōu)化后節(jié)點(diǎn)分布圖和相應(yīng)收斂曲線圖。

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

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

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

由表11可知，MS-ALO算法運(yùn)行200次優(yōu)化的平均覆蓋率相比BPABC算法和ALO算法分別提高了2.02%和8.49%，最差覆蓋率相比兩種算法分別提高了3.13%和10.23%，收斂精度和穩(wěn)定性均有較大程度地提高。在如圖10所示的節(jié)點(diǎn)分布中，基本ALO算法優(yōu)化后傳感器節(jié)點(diǎn)在部分區(qū)域過(guò)于聚集，覆蓋盲區(qū)較大；而MS-ALO算法優(yōu)化后節(jié)點(diǎn)分布較均勻，有效縮減了無(wú)線網(wǎng)絡(luò)盲區(qū)，近似實(shí)現(xiàn)了區(qū)域完全覆蓋。

另外，從圖11可以看出，MS-ALO算法迭代至500代時(shí)已接近收斂，但由于早熟收斂判斷機(jī)制的引入，使得算法利用動(dòng)態(tài)混合變異策略跳出局部極值，以搜索更優(yōu)解，進(jìn)一步提高了收斂精度。如圖11所示，MS-ALO算法和ALO算法分別在615代和790代時(shí)收斂，說(shuō)明改進(jìn)策略有效提升了MS-ALO算法的收斂速度，能夠更快速地尋優(yōu)最大覆蓋率。

綜上所述，通過(guò)與不同算法在相應(yīng)同等測(cè)試條件下的實(shí)驗(yàn)結(jié)果對(duì)比，MS-ALO算法實(shí)現(xiàn)了更高的平均覆蓋率、較均勻的傳感器節(jié)點(diǎn)分布和較少的網(wǎng)絡(luò)覆蓋盲點(diǎn)，驗(yàn)證了該算法具有較好的WSN覆蓋優(yōu)化性能。

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

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)覆蓋率最大化的目標(biāo)，本文提出了一種基于混合策略的改進(jìn)蟻獅優(yōu)化算法(MS-ALO)實(shí)現(xiàn)傳感器節(jié)點(diǎn)的覆蓋優(yōu)化。該算法通過(guò)連續(xù)性邊界收縮因子，提高了算法對(duì)搜索空間的遍歷性和收斂速度；利用位置更新動(dòng)態(tài)權(quán)重系數(shù)，增強(qiáng)了算法的全局探索與局部開(kāi)發(fā)的平衡能力；基于早熟收斂判斷和動(dòng)態(tài)混合變異機(jī)制，改善了算法易陷入局部最優(yōu)的問(wèn)題。通過(guò)對(duì)不同形態(tài)基準(zhǔn)函數(shù)的優(yōu)化求解，以及與基本蟻獅優(yōu)化算法和其改進(jìn)算法的對(duì)比，驗(yàn)證了改進(jìn)策略的有效性。

將MS-ALO算法進(jìn)一步應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化，選取基本ALO算法和不同參考文獻(xiàn)中4種覆蓋優(yōu)化算法，在相同測(cè)試條件下進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，基于MS-ALO的WSN覆蓋優(yōu)化算法多次運(yùn)行取得的平均覆蓋率，除了與文獻(xiàn)[4]在傳感器節(jié)點(diǎn)數(shù)為90和60對(duì)比時(shí)略低于VF-CS算法0.09%和1.88%，對(duì)于其他參比算法均有較大程度的提升；同時(shí)，通過(guò)與ALO算法和參比文獻(xiàn)中的傳感器節(jié)點(diǎn)優(yōu)化分布圖對(duì)比，MS-ALO算法優(yōu)化后的節(jié)點(diǎn)分布更加均勻，覆蓋盲區(qū)更??；然后，通過(guò)對(duì)比覆蓋優(yōu)化收斂曲線，驗(yàn)證了改進(jìn)策略對(duì)于ALO算法收斂速度的有效提升。因此，本文算法能夠較好地提高無(wú)線傳感器網(wǎng)絡(luò)的性能。然而，如何在保證較高覆蓋率收斂精度的情況下進(jìn)一步提升算法收斂速度，是MS-ALO算法下一步需要完善的工作。