改進蟻獅算法的無線傳感器網絡覆蓋優化?

徐欽帥，何 慶?，魏康園

(1.貴州大學大數據與信息工程學院，貴陽550025；2.貴州大學貴州省公共大數據重點實驗室，貴陽550025)

無線傳感器網絡WSN(Wireless Sensor Network)是一種自組織網絡，由能夠進行傳感、處理和無線通信的傳感器節點組成[1]。網絡區域覆蓋是WSN中的一個關鍵問題，對傳感器節點的覆蓋分布進行優化，能夠改善網絡的服務質量和能耗平衡。

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

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

為了實現WSN覆蓋率的最大化，針對ALO算法的缺陷，本文提出一種基于連續性邊界收縮因子、位置更新動態權重系數和動態混合變異策略的改進蟻獅算法MS-ALO(Mixed Strategy based Ant Lion Optimizer)，應用于WSN傳感器節點覆蓋優化。仿真實驗首先通過對基準函數的優化對比，驗證改進策略的有效性；然后將MS-ALO算法應用于WSN覆蓋優化問題，選取不同文獻中4種算法在相同條件下進行對比實驗，驗證該算法的應用價值。

1 問題模型分析

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

若像素點Hj與任意一個節點距離小于或等于感知半徑Rs，則認定Hj已被網絡覆蓋。節點zi與像素點Hj的間距定義為

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

式中：Re為傳感器節點的感知誤差；λ為感知衰減系數。

在該區域內，任意一個像素點能同時被多個節點感知，其聯合感知概率p(Z，Hj)定義為

該區域的覆蓋率Rcov為節點集合Z所覆蓋的像素點總數與區域內像素點總數的比值，定義為

因此，將式(4)作為文中改進蟻獅算法求解WSN覆蓋優化問題的目標函數，即所有位置變量在監測區域范圍內，利用改進算法優化求解覆蓋率Rcov的最大值。

2 蟻獅優化算法基本原理

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

隨機初始化種群位置，計算適應度值，并采用輪盤賭方法選擇蟻獅修筑陷阱。

螞蟻在搜索空間內隨機游走，定義為

式中：cumsum為位置累計；t為當前迭代次數；T為最大迭代次數；r(t)為隨機數0或1，定義為

式中：m為在[0，1]內的隨機數。

同時，為了使螞蟻的隨機游走保持在搜索空間內，對其位置進行歸一化處理，定義為

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

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

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

當螞蟻圍繞陷阱隨機游走時，蟻獅會繼續深挖以防螞蟻逃出，使螞蟻游走邊界逐漸縮小直至滑落陷阱底部，該過程定義為

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

式中：w為由t和T決定的常數。

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

式中：Antliontj為第t次代第j只蟻獅的位置；Antti為第t代第i只螞蟻位置；f為適應度函數。

選擇當代最優蟻獅作為精英蟻獅，同輪盤賭選擇蟻獅一起引導螞蟻的位置更新，定義為

式中：RtA為第t代繞輪盤賭選擇蟻獅的螞蟻隨機游走；RtE為第t代繞精英蟻獅的螞蟻隨機游走。

3 算法分析及混合改進策略

3.1 連續性邊界收縮因子

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

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

式中：γ為收縮調節系數；λ為比例因子；經過多次基準函數優化實驗，選取γ＝400，λ＝20。

3.2 位置更新動態權重系數

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

式中：f(xi)為個體適應度值。

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

針對上述問題，將基于迭代次數的動態權重系數引入螞蟻位置更新式(14)，改進為

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

3.3 動態混合變異

由于游走邊界的收縮和精英蟻獅引導種群聚攏，導致種群多樣性減小，而易發生早熟收斂現象，陷入局部最優。

為了使算法能有效跳出局部最優，提出一種結合早熟收斂判斷方法與動態混合變異的改進策略。首先，采用文獻[16]中的早熟判斷方法，將第t代的全局適應度方差αt定義為

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

mean為第t代全局平均適應度；fta為限定αt的標定因子，定義為

然后，將個體間距Dt定義為

式中：L為搜索空間最大對角長度；n為搜索維度；xtid為第t代時第i個個體在第d維的位置；xtmean為第t代時所有個體在第d維的位置平均值。

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

針對算法陷入局部最優的困境，提出一種基于正態分布和柯西分布動態調整的混合變異方法，對蟻獅位置Antliontj進行變異擾動操作，如式(22)所示：

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

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

同時，為了保證變異策略產生的新解始終朝向更優區域移動，每次操作復制M個當代蟻獅位置進行變異產生新解，最后在M＋1個候選解組成的解集中選擇最優解進入下一次迭代，文中所有實驗取M＝20。

4 覆蓋優化算法設計

基于MS-ALO算法的WSN覆蓋優化的目標為監測區域覆蓋率Rcov的最大化；輸入為MS-ALO算法的種群規模N和最大迭代次數T，以及監測區域面積S、像素點數m×n、傳感器節點數V和感知半徑Rs等參數；輸出為Rcov最優適應度值，以及傳感器節點分布坐標。

MS-ALO算法的種群中每個個體代表區域內所有節點的一個覆蓋分布；尋優維度d＝2 V，則節點分布坐標可表示為(2d－1，2d)。算法流程如圖1所示。

圖1 基于MS-ALO算法的WSN覆蓋優化

具體算法步驟如下：

Step 1 輸入WSN監測區域、傳感器節點及MS-ALO算法相關參數；

Step 2 在搜索空間即監測區域內，隨機初始化種群中的個體位置；

Step 3 初始化迭代次數t＝1；

Step 4 將節點覆蓋率Rcov作為目標函數，根據式(4)計算種群適應度，保存最優個體作為精英蟻獅；

Step 5 利用輪盤賭方法選擇適應度較高的蟻獅挖掘陷阱；

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

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

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

Step 9 基于當前種群適應度值及個體位置，根據式(19)和式(21)分別計算適應度方差αt和個體間距 Dt；

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

Step 11 復制M個當前最優個體位置，分別根據式(22)進行混合變異操作，并構建當前最優個體與變異個體的新解集，從中選取適應度最優的個體并保存；

Step 12 更新迭代次數t＝t＋1，并判斷是否達到最大迭代次數，若是，結束算法并輸出覆蓋率最優適應度值和相應節點部署坐標位置；否則，跳至Step4循環迭代。

5 仿真實驗與分析

5.1 基準函數優化性能測試

為了驗證混合策略的有效性，選取12個基準函數進行數值仿真，并與基本ALO算法和文獻[11]提出的改進OB-L-ALO算法進行比較。實驗采用的12個基準函數的名稱、數學表達式及其他參數情況如表1所示，其中：f1～f5為單峰函數；f6～f10為多峰函數；f11～f12為固定低維度下的多峰函數。

表1 基準函數

為了保證算法優化性能測試的公正性，基本ALO算法、MS-ALO算法的參數設置同文獻[11]中OB-L-ALO算法參數一致：種群規模N＝30，最大迭代次數T＝1 000。同時，為減小隨機干擾的影響，不同算法對于每個基準函數均獨立運行30次，并取實驗結果平均值進行比較。

表2 基準函數優化結果對比

表2記錄了 ALO算法、OB-L-ALO算法[11]與MS-ALO算法在相同測試條件下，對于12個基準函數的優化結果。圖2為ALO算法與MS-ALO算法對基準函數優化收斂過程對比，其中：Iteration表示迭代次數；Mean best so far表示算法運行30次的平均適應度值。

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

圖2 優化測試函數收斂曲線對比

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

在固定低維度搜索空間的多峰函數優化中，MS-ALO算法對于函數f11尋優的平均最優值已達到其理論最優值，對于f12的優化結果較參比算法也有所提高，且均值方差更小，驗證了改進算法的魯棒性。

綜上所述，MS-ALO算法對于基準函數的優化求解在收斂精度、收斂速度、多峰優化能力和魯棒性等方面，均優于基本ALO算法及其改進算法OB-LALO，驗證了混合改進策略的有效性。因此，該算法可進一步應用于WSN的節點覆蓋優化問題。

5.2 WSN覆蓋優化應用

5.2.1 實驗設置

為了充分驗證MS-ALO算法對WSN節點覆蓋的優化性能，選取基本ALO算法和不同文獻中4種改進算法，分別在相應監測區域對不同數量的傳感器節點進行覆蓋優化對比。參比文獻及其算法如表3所示，仿真實驗參數與相應文獻參數設置相同。參比文獻及算法

表3

5.2.2 與DACQPSO算法對比

實驗參數設置與文獻[2]相同，如表4所示。

表4 參數設置

為了降低隨機性對實驗結果的干擾，利用ALO算法和MS-ALO算法對該區域進行20次優化，取平均覆蓋率對比。表5給出了ALO算法、MS-ALO算法與DACQPSO算法平均覆蓋率優化結果對比。圖3和圖4分別為ALO算法和MS-ALO算法優化后該區域節點分布圖和收斂曲線圖。

表5 覆蓋率優化結果對比

圖3 優化后節點分布

圖4 覆蓋優化收斂曲線

由表5可知，在相同測試條件下，MS-ALO算法運行20次優化的平均覆蓋率相比DACQPSO算法和基本ALO算法分別提高了6.31%和7.07%，較大程度地提高了網絡覆蓋率。同時，從圖3可以看出，基本ALO算法覆蓋優化效果較差，MS-ALO算法優化后節點分布更加均勻，無線網絡覆蓋范圍更加廣泛，且改善了文獻[2]中DACQPSO算法優化節點分布區域邊界覆蓋盲區較大的問題。

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

5.2.3 與IGWO算法對比

參數設置與文獻[3]相同，如表6所示。

利用MS-ALO算法對該區域進行20次覆蓋優化，取平均覆蓋率對比。表7給出了ALO算法、MSALO算法與IGWO算法平均覆蓋率優化結果對比。圖5和圖6分別為ALO算法和MS-ALO算法優化后該區域節點分布圖和收斂曲線圖。

表7 覆蓋率優化結果對比

圖5 優化后節點分布

圖6 覆蓋優化收斂曲線

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

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

5.2.4 與VF-CS算法對比

參數設置與文獻[4]相同，如表8所示。

表8 參數設置

利用MS-ALO算法對該區域進行30次優化，取平均覆蓋率對比。表9為ALO算法、MS-ALO算法與VF-CS算法對不同傳感器節點數量的平均覆蓋優化結果對比。圖7和圖8分別給出了ALO算法和MS-ALO算法優化后該區域內傳感器節點數為90和80的節點分布圖，圖9為相應收斂曲線。

表9 覆蓋優化結果對比

圖7 V＝90時優化后節點分布

圖8 V＝80時優化后節點分布

由表9可知，在相同的監測區域，隨著部署節點數的增加，覆蓋率也在逐漸提高。在節點數為80、70、50和40時，MS-ALO算法優化的平均覆蓋率相比于VF-CS算法分別提高了0.11%、1.37%、0.27%和1.43%；而在節點數為90和60時，則比VF-CS算法分別降低了0.09%和1.88%。相比于基本ALO算法，MS-ALO算法對不同數量節點優化的平均覆蓋率則分別提高了8.68%、7.82%、14.2%、7.72%、8.88%和8.15%，表明動態權重系數的引入能夠有效平衡算法的全局與局部搜索能力，從而有效提高算法的收斂精度。

圖9 覆蓋優化收斂曲線

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

5.2.5 與BPABC算法對比

參數設置與文獻[5]相同，如表10所示。

表10 參數設置

利用MS-ALO算法對該區域進行200次覆蓋優化，取平均覆蓋率對比。表11為ALO算法、MSALO算法與BPABC算法的平均覆蓋率和最差覆蓋率數值對比。圖10和圖11分別為ALO算法和MSALO算法優化后節點分布圖和相應收斂曲線圖。

表11 覆蓋率優化結果對比

圖10 優化后節點分布

圖11 覆蓋優化收斂曲線

由表11可知，MS-ALO算法運行200次優化的平均覆蓋率相比BPABC算法和ALO算法分別提高了2.02%和8.49%，最差覆蓋率相比兩種算法分別提高了3.13%和10.23%，收斂精度和穩定性均有較大程度地提高。在如圖10所示的節點分布中，基本ALO算法優化后傳感器節點在部分區域過于聚集，覆蓋盲區較大；而MS-ALO算法優化后節點分布較均勻，有效縮減了無線網絡盲區，近似實現了區域完全覆蓋。

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

綜上所述，通過與不同算法在相應同等測試條件下的實驗結果對比，MS-ALO算法實現了更高的平均覆蓋率、較均勻的傳感器節點分布和較少的網絡覆蓋盲點，驗證了該算法具有較好的WSN覆蓋優化性能。

6 結束語

針對無線傳感器網絡覆蓋率最大化的目標，本文提出了一種基于混合策略的改進蟻獅優化算法(MS-ALO)實現傳感器節點的覆蓋優化。該算法通過連續性邊界收縮因子，提高了算法對搜索空間的遍歷性和收斂速度；利用位置更新動態權重系數，增強了算法的全局探索與局部開發的平衡能力；基于早熟收斂判斷和動態混合變異機制，改善了算法易陷入局部最優的問題。通過對不同形態基準函數的優化求解，以及與基本蟻獅優化算法和其改進算法的對比，驗證了改進策略的有效性。

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