茍平章孫現(xiàn)超

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

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

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

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

1 系統(tǒng)模型與術語定義

1.1 網絡模型

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

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

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

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

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

1.2 能量模型

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

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

1.3 感知模型

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

1.4 術語定義

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

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

2 覆蓋優(yōu)化方法

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

圖1 IFA 算法覆蓋優(yōu)化流程圖

2.1 IFA 覆蓋優(yōu)化方法

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

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

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

2.1.1 IFA 算法

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

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

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

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

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

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

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

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

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

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

2.1.2 基于IFA 算法的覆蓋優(yōu)化

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

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

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

Step 3 根據(jù)待優(yōu)化的目標函數(shù)計算每一個傳感器節(jié)點位置的適應度值并作為其絕對熒光亮度；

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

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

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

2.2 目標位置優(yōu)化方法

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

具體方案描述如下:

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

圖2 移動距離優(yōu)化

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

圖3 能量優(yōu)先

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

圖4 位置交換原則

3 仿真實驗與分析

3.1 實驗環(huán)境

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

表1 網絡環(huán)境和參數(shù)設置

3.2 實驗結果及分析

3.2.1 移動距離分析

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

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

3.2.2 網絡覆蓋優(yōu)化分析

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

圖6 網絡覆蓋優(yōu)化迭代柱狀圖

3.2.3 能耗及結果優(yōu)化分析

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

圖7 網絡總能耗與迭代次數(shù)的關系

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

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

圖8 初始節(jié)點位置分布圖

圖9 迭代100 次節(jié)點分布圖

圖10 迭代200 次節(jié)點分布圖

圖11 IFA 算法優(yōu)化后節(jié)點分布圖

圖12 目標位置優(yōu)化

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

4 總結

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