基于改進螢火蟲算法的覆蓋優化方法?

茍平章孫現超

(西北師范大學計算機科學與工程學院，甘肅 蘭州 730070)

無線傳感器網絡(Wireless Sensor Networks，WSNs)是由大量的傳感器節點通過多跳和自組織成的無線網絡。 隨著嵌入式技術和無線通信技術的發展，WSNs 已被廣泛應用于軍事，工業和農業控制，生物醫學，環境測試，救災等領域[1]。 同時，合理的節點部署不僅可以提高網絡數據傳輸效率和網絡資源利用率，還可以根據實際應用需求動態的調整網絡狀況，因此，節點部署與覆蓋問題是WSNs 的主要研究方向[2]。 由于傳感器節點通常部署在戰場或沙漠等偏遠或敵對環境中，只能通過飛機投擲等隨機方式進行部署，風和障礙物會影響節點的實際著陸位置，導致目標區域出現覆蓋空洞[3]。 如果僅部署靜態傳感器節點，即使在目標區域部署大量冗余節點，覆蓋質量也無法保證，而且還會造成節點浪費。 如果僅部署移動傳感器節點，成本會很高。

針對上述存在的問題，可以在目標區域內同時部署靜態傳感器節點和移動傳感器節點。 移動傳感器節點能夠在部署后可以移動到指定的位置，從而提高網絡覆蓋率，滿足網絡的覆蓋要求。 近年來，越來越多的學者研究節點部署問題。 文獻[4]提出利用Voronoi 圖對網絡中隨機布置的傳感器節點進行部署，該算法減少了冗余并去除了孤立節點，保持網絡連通性。 該算法將區域劃分為不同的Voronoi 單元，并部署所需的節點，從而根據Voronoi 劃分將節點移動到它們的最佳位置，提高網絡覆蓋率。 文獻[5]提出一種具有無參數配置的異構無線傳感器節點部署算法，利用Delaunay 三角剖分方法查找出最大的覆蓋空洞，采用eVForce 方法避開障礙物進行節點的部署，該算法的性能優于隨機部署和傳統的Delaunay 三角網部署，并提高了異構無線傳感器網絡的覆蓋范圍和網絡生命周期。 文獻[6]利用改進正弦余弦算法進行節點部署優化，利用該算法部署的節點覆蓋率優于改進粒子群優化算法和改進灰狼優化算法，有效提高了網絡節點覆蓋率。 文獻[7]提出一種基于外推人工蜂群算法的節點部署優化方法，利用該算法代入模型進行求解，獲得覆蓋最優的節點部署位置，覆蓋率得到了一定的提高。 文獻[8] 提出一種基于改進的自適應粒子群優化(Particle Swarm Optimization，PSO)算法的覆蓋優化方法，克服了粒子群優化算法在優化后期容易陷入局部最優的弱點，提高了網絡覆蓋率。 文獻[9]提出自適應混沌量子粒子群算法的移動傳感器網絡覆蓋優化算法，彌補標準粒子群、量子粒子群的不足，覆蓋性能得到提高。 文獻[10]提出一種改進蟻獅算法(Mixed Strategy based Ant Lion Optimizer，MSALO)的網絡覆蓋優化方法，結合早熟收斂判斷機制與動態混合變異方法，使算法能夠有效跳出局部最優。 文獻[11]提出基于改進鯨魚優化算法的WSNs覆蓋優化策略，該策略解決了隨機部署移動節點時分布不均勻導致覆蓋率低的問題，減少了傳感器節點冗余。 文獻[12] 提出一種基于布谷鳥搜索(Cuckoo Search，CS)的覆蓋優化策略，與粒子群優化算法相比，減少了移動節點的數量，提高了目標區域覆蓋率。 文獻[13]提出一種多因素協同空洞修補優化算法，該算法考慮了虛擬修復節點與移動節點之間的距離、移動修復過程中的能耗以及待修復節點的可信度，建立虛擬修復節點和移動節點之間的皮爾遜模糊匹配關系來修復空洞，從而提高網絡覆蓋率。 文獻[14]提出一種改進差分進化算法(Improved Differential Evolution Algorithm，IDEA)的網絡節點部署優化策略，使用節點的有效覆蓋率作為優化因子構造目標函數優化模型，采用混沌反向學習初始化策略，加快收斂速度、提升節點的網絡覆蓋率。

綜合以上研究，利用啟發式算法的逐步尋優特性，本文提出一種基于改進螢火蟲算法的覆蓋優化方法。 該方法通過在監測區域內隨機部署靜態節點和移動節點，對位置公式進行改進，加入權重函數，提高全局搜索能力，防止陷入局部最優；對步長因子進行改進，加快算法收斂速度。 通過改進螢火蟲算法(Improved Firefly Algorithm，IFA)初步確定移動傳感器節點的候選目標位置，利用目標位置優化方法確定傳感器節點最佳位置，從而完成覆蓋優化，同時減少節點移動距離，達到節省節點能量，延長網絡生命周期的目的。

1 系統模型與術語定義

1.1 網絡模型

本文的網絡模型假設如下:

假設1 在無線傳感器網絡目標區域內部署N個傳感器節點，其中包括Nm個移動傳感器節點，Nn個靜態傳感器節點。 傳感器節點集合定義為:

假設2 網絡中每個傳感器節點都可以通過GPS或某些位置服務知道其位置信息。

假設3 所有傳感器節點具有相同的感知范圍Rs和通信范圍Rc，并且Rc＝2Rs。

假設4 目標區域內的移動傳感器節點具有充足能量，確保其能夠移動到指定位置。

1.2 能量模型

為使數據能被有效發送，采用文獻[15]提出的能耗模型進行能量消耗計算，根據節點傳輸距離，節點部分能量在數據傳輸過程中進行信號放大。 節點在鏈路上傳輸kbit 數據的能耗可表示為:

式中:dmax表示該移動節點可移動最大距離，Eres為移動節點剩余能量。

1.3 感知模型

假設監測區域A是L×L的正方形區域，為方便計算和比較各算法的覆蓋性能，將監測區域A網格化，分為l×l個像素點，以像素點是否在節點Si的感知半徑范圍內表示覆蓋程度。 若像素點Hj(j＝1，2，3，…，l×l)的坐標為(xi，yi)，則Si和Hj的之間的距離可表示為:

1.4 術語定義

定義1(區域覆蓋率) 區域覆蓋率表示所有傳感器節點感知區域的并集與目標區域總面積的比值，定義為Rarea(S):

式中:ad(S)表示傳感器節點的平均移動距離，Rarea(S)為區域覆蓋率。

2 覆蓋優化方法

針對在目標區域內僅僅部署靜態傳感器節點和移動傳感器節點存在的問題，本文提出一種基于改進螢火蟲算法的覆蓋優化方法。 該方法分為兩個步驟:①對位置公式和步長因子進行改進，提高了全局搜索能力，加快算法收斂。 利用IFA 算法初步確定移動傳感器節點的候選目標位置。 ②通過目標位置優化方法對第一步驟獲取到的候選目標位置進行優化，從而確定移動傳感器節點的最佳目標位置。 算法流程如圖1 所示。

圖1 IFA 算法覆蓋優化流程圖

2.1 IFA 覆蓋優化方法

FA 算法最早由文獻[16]提出，是一種模仿自然界螢火蟲捕食、求偶行為的新型群體智能優化算法。 FA 算法需要的參數較少，思想比較簡單且優化性能好，FA 算法在WSNs 中[17]得到廣泛應用。 但也存在易陷入局部最優、算法過早收斂等問題[18]，因此本文對FA 算法進行改進，將IFA 算法應用到WSNs 覆蓋優化中，利用IFA 算法初步確定移動傳感器節點的候選目標位置。

FA 算法中，每個螢火蟲的位置代表了一個待求問題的可行解，而螢火蟲的亮度表示該螢火蟲位置的適應度，亮度越高的螢火蟲個體在解空間內的位置越好。 螢火蟲個體之間，高亮度的螢火蟲會吸引低亮度的螢火蟲。 FA 算法有以下三個基本假設:①所有螢火蟲無性別之分，每一只螢火蟲只會被比其更亮的螢火蟲所吸引。 ②螢火蟲之間的吸引力與他們的亮度成正比，對于任意兩個螢火蟲，亮度低的螢火蟲向亮度高的螢火蟲移動，越靠近亮度越強，吸引力越大，即吸引力與亮度成正比。 而亮度隨距離的增加而變弱，則吸引力與距離成反比。 ③螢火蟲的亮度在算法里是根據待優化的目標函數值所決定的，目標函數值越好，證明其熒光亮度越高。

定義1 螢火蟲的相對熒光亮度。式中:x′i表示一個比第i個亮度更高的螢火蟲位置，rij的定義如同定義(1)，xi，xj分別代表螢火蟲i，j在空間中所處的位置。 rand 是服從均勻高斯分布的隨機數，α為步長因子。

2.1.1 IFA 算法

標準FA 算法在迭代后期，由于螢火蟲已經逐漸移動至局部或者全局極值點附近，此時螢火蟲之間的距離逐漸縮小，根據位置更新公式(11)可以得到:螢火蟲之間的吸引度逐漸增大，將會使螢火蟲個體的移動距離過大而無法到達或者錯過最優位置，造成在極值點附近震蕩的問題。 本文在標準FA 算法的基礎上，引入了權重函數，此時位置更新公式變為:

式中:ωmax，ωmin分別為最大、 最小權重；t，MaxGeneration 分別為當前和最大迭代次數。

通過權重函數可以控制螢火蟲以前位置信息對當前位置的影響，權重的大小決定螢火蟲移動距離的大小，并提高了螢火蟲算法的全局尋優和局部搜索能力。 當權值取值較大時，螢火蟲當前的位置會對下一步要移動的位置有較大的影響，螢火蟲間的吸引度影響相對較小，全局尋優能力增強，局部搜索能力相對減弱。 反之，螢火蟲當前的位置會對下一步要移動的位置影響較小，螢火蟲間的吸引度影響相對較大，全局尋優能力減弱，局部搜索能力相對增強。 因此通過調整權重函數w(t)的取值，可以使螢火蟲算法在搜索前期具有較強的全局搜索能力，有助于加快全局的收斂速度，隨著迭代次數的增加，權重逐漸減小，到搜索后期，局部搜索能力增強。

從螢火蟲之間的吸引度公式(11)中不難發現，當兩個螢火蟲之間的距離很大時(rij→∞)此時吸引度β≈0，則螢火蟲i進行的位置公式(11)就會近似式(14)的形式:

式中:t代表算法的當前迭代次數，a為步長因子，rand 是服從高斯分布的隨機數。

從式(14)中可以看出，此時螢火蟲i的位置更新與其他亮度更高的螢火蟲無關。 因此在算法運行前期螢火蟲種群過于分散導致有些螢火蟲之間的距離過大時即(rij→∞)，這時如果步長因子α的取值過小，則處于劣勢位置的螢火蟲i就會按照近似公式(14)進行位置更新，而不能被處于更好位置的螢火蟲j吸引，只能在自己位置周邊完成局部搜索，降低了全局尋優能力。

當兩個螢火蟲之間的距離趨于0 時(rij→0)，吸引度β≈β0(β0一般為常數1)，此時位置移動公式(11)也會近似于式(14)的形式。 因此在算法運行后期，螢火蟲間的距離即將收斂到最小時(rij→0)，且α取值過大，處于劣勢位置的螢火蟲i就會遠離處于更好位置的螢火蟲j，這樣就會容易使算法產生震蕩現象降低了收斂速度。

綜上所述，發現步長因子α的取值在平衡全局尋優和提高收斂速度上有著至關重要的作用。 因此本文不再取固定不變的α值，而是在迭代過程中對α的值進行了動態調整。 在算法運行初期，α的值較大，有利于全局尋優；而隨著迭代次數的增加，α的值逐漸減少，可以提高算法收斂速度。 步長因子α的動態調整過程如式(15)所示:

式中:upper，low 分別為搜索范圍上下限。

從式(15)中可以看出，α的取值是隨著迭代次數遞減的，因此在算法運行初期時，α的取值較大，可以避免由于螢火蟲之間距離過大只能在自己周圍局部搜索的情況，提高了全局尋優能力；在算法運行后期時，α的取值會變得較小，避免了算法產生震蕩的現象，有利于提高算法收斂速度。

2.1.2 基于IFA 算法的覆蓋優化

通過對FA 算法進行改進，防止陷入局部最優，加快搜索速度。 將改進的螢火蟲算法應用到WSNs覆蓋優化中，利用IFA 算法求解出移動傳感器節點的候選目標位置。 該算法利用螢火蟲之間的吸引力，以節點間的剩余能量和節點間的距離作為吸引力，確定移動節點的候選位置，提高網絡覆蓋率。 具體算法步驟如下:

Step 1 對最大迭代次數、種群數目、最大吸引度、光吸收系數等相關必要參數進行初始化；

Step 2 在目標區域內隨機拋灑傳感器節點，并將每個傳感器節點看成一個螢火蟲，從而形成螢火蟲群；

Step 3 根據待優化的目標函數計算每一個傳感器節點位置的適應度值并作為其絕對熒光亮度；

Step 4 每兩個傳感器節點進行相互比較，適應度值小的傳感器節點則按照位置公式(12)進行位置更新；

Step 5 檢查算法是否達到最大迭代次數，如果未達到則返回步驟3，達到則輸出該迭代次數條件下最優解。

通過對FA 算法進行改進，提高其全局搜索能力，加快收斂速度。 當問題維度為D，外層迭代次數為G，標準FA 算法的時間復雜度為O(n2×G)。 本文在標準的FA 算法的基礎上，對位置公式和步長因子進行改進，本文算法的時間復雜度為O[G(n×D＋n)]＝O[G(n×D)]。 因此，本文算法比標準的FA算法大大減少了時間復雜度。 利用IFA 算法初步確定移動傳感器節點的位置，將基于IFA 算法的覆蓋優化得到的最優解作為目標位置優化方法的輸入，進一步完成覆蓋優化。

2.2 目標位置優化方法

目標位置優化方法以能量優先為原則，在不減少網絡覆蓋率的前提下，通過減少移動傳感器節點的移動距離，從而降低節點移動能量消耗，延長網絡生命周期。 該方法從移動距離優化、能量優先、移動節點目標位置交換3 個方面對候選目標位置進行優化。

具體方案描述如下:

①移動距離優化。 利用IFA 算法獲取到移動傳感器節點的候選目標位置后，移動傳感器節點將移到此位置進行覆蓋優化。 如圖2 所示，當傳感器節點Si從P0移動到P2時，區域覆蓋率Rarea(S)沒有提高。 在這種情況下，覆蓋質量并沒有得到有效改善，此時將取消移動傳感器節點Si的移動。 通過移動距離優化方法，可以減少傳感器節點總的移動距離，并且節省節點能量，延長網絡生命周期。

圖2 移動距離優化

②能量優先原則。 假設Si的能量大于Sj的能量，d1和d2相等。 在滿足約束條件1，移動節點移動距離不超過其最遠移動距離dmax的前提下，假設移動傳感器節點Si、Sj分別從P0和P1移動P2的位置皆可完成覆蓋優化，且2 個傳感器節點移動到候選目標位置后網絡覆蓋范圍不變，則優先選擇能量高的Si節點進行移動，如圖3 所示。 按照能量優先方式進行移動，會延長網絡生命周期，提高網絡監測效率。

圖3 能量優先

③移動節點目標位置交換原則。 如果2 個移動節點移動到候選目標位置后增加相同的覆蓋率，那么可以交換這2 個節點的候選目標位置。 如圖4(a)所示，當節點S1和S2分別移動到P1和P2后，區域覆蓋率Rarea(S)增加程度相同，此時移動傳感器節點S1和S2的總移動距離為d1＋d2，若按圖4(b)方式交換候選目標位置之后，移動的距離為d3＋d4，顯然d3＋d4

圖4 位置交換原則

3 仿真實驗與分析

3.1 實驗環境

為了驗證IFA 算法應用于WSNs 覆蓋優化的可行性，在MATLAB2018 上進行仿真實驗。 假設監測區域為200 m×200 m 的矩形區域，在監測區域內隨機部署100 個傳感器節點，其中有30 個移動傳感器節點，移動傳感器節點由空心圓表示。 實驗中具體仿真參數如表1 所示。

表1 網絡環境和參數設置

3.2 實驗結果及分析

3.2.1 移動距離分析

對監測區域為200 m×200 m 矩形區域進行仿真實驗，迭代次數設置為300 次。 研究IFA 算法與文獻[10]中的MS-ALO 算法，以及文獻[9]PSO 算法的平均移動距離與移動節點數量的關系。 將三種算法分別進行300 次獨立實驗后取平均值，得到如圖5 所示的實驗結果。 分析圖5 可知，三種算法都隨著移動節點比例的增加而增加，但IFA 算法的平均移動距離比其他兩種算法有明顯的優勢，同時節省節點能量，延長網絡生命周期。

圖5 平均移動距離與節點比例的關系

3.2.2 網絡覆蓋優化分析

將IFA 算法與文獻[12]中的CS 算法，以及FA算法作比較，圖6 分別為三種算法在相同條件下經過多次實驗得到的網絡覆蓋率與迭代次數的柱狀圖。 分析圖6 可知，三種算法的網絡覆蓋率都隨著迭代次數的增加不斷提升。 IFA 算法可以將區域覆蓋率從最初的37%優化到94.95%，提高了57.95%，而CS 算法和FA 算法分別提高了54.6%和52.51%。IFA 算法與CS 算法和FA 算法相比，分別提升了3.35%和5.44%，將IFA 算法用于WSNs 覆蓋優化中具有更好的覆蓋效果；另外，由圖6 可知，IFA 算法在迭代次數達到150 次時，可以達到94.95%的覆蓋率，而其他兩種算法分別在200 次和250 次才達到最優的覆蓋效果，因此IFA 算法具有更好的收斂性。

圖6 網絡覆蓋優化迭代柱狀圖

3.2.3 能耗及結果優化分析

將IFA 算法與文獻[9]PSO 算法、文獻[12]CS算法、文獻[14]IDEA 算法作比較。 圖7 分別為四種算法在相同條件下經過多次實驗得到的能耗與迭代次數的關系圖。 分析圖7 可知，四種算法的總能耗都隨著迭代次數的增加不斷提升，但IFA 算法相比其他三種算法所消耗的能量少。 從仿真結果可知，IFA 算法在迭代250 次以后，網絡總能耗還是趨于增加的趨勢。 而IDEA 算法和CS 算法在迭代250次后、PSO 算法在迭代200 次后，網絡總能耗就不再增加，此時網絡已經不能正常工作。 由此可知，將IFA 算法應用于WSNs 覆蓋優化中，具有更長的生命周期。

圖7 網絡總能耗與迭代次數的關系

為驗證該方法的可行性，分別對該方法的2 個步驟的優化結果進行仿真實驗，結果如圖8～圖12所示。

圖8 為隨機部署在目標區域的節點位置分布圖，圖9～圖11 分別為迭代100 次、200 次和IFA 算法優化后的節點位置分布圖，圖12 為經過目標位置優化后移動傳感器節點的最佳位置。 分析圖8～圖11的變化可知，目標區域的空洞逐漸減少，網絡的覆蓋率在增加。 從圖11 到圖12 的變化可知，對候選目標位置進行優化，得到移動傳感器節點的最佳位置，覆蓋率也進一步得到提高。 減少非必要節點的移動，節省能量。

圖8 初始節點位置分布圖

圖9 迭代100 次節點分布圖

圖10 迭代200 次節點分布圖

圖11 IFA 算法優化后節點分布圖

圖12 目標位置優化

分析實驗結果表明，本文利用IFA 算法可以初步確定移動傳感器節點的位置，然后再經過目標位置優化方法確定最佳位置是可行的。 通過對圖12進行覆蓋面積計算，網絡覆蓋率可以達到94.95%，實現比較好的覆蓋優化。 同時使用目標優化方法可以減少節點移動距離，節省節點能量，延長網絡生命周期。

4 總結

針對在無線傳感器網絡監測區域內僅僅部署靜態傳感器節點和移動傳感器節點存在的問題，本文提出一種基于改進螢火蟲算法的覆蓋空洞優化方法，將靜態傳感器節點和動態傳感器節點隨機部署在目標區域內，對位置公式和步長因子進行改進，提高全局尋優能力，加快搜索速度。 通過IFA 算法初步確定移動傳感器節點的位置，然后通過目標位置優化方法對初步位置進行優化，最終確定最佳的位置。 仿真實驗表明，該方案是可行的，可以很好的確定移動傳感器節點的最佳位置，從而完成覆蓋優化。