基于改進蝙蝠算法的WSNs覆蓋優化策略

姚引娣，楊 軒，劉武英，廖煥敏，胡珊珊，付子坤

(1.西安郵電大學 通信與信息工程學院,陜西 西安 710121；2.西安郵電大學 學報編輯部,陜西 西安 710121；3.西安郵電大學 電子工程學院，陜西 西安 710121)

無線傳感器網絡(Wireless Sensors Networks,WSNs)是由大量微小的具有計算處理、感知和無線通信能力的傳感器節點組成的自組織網絡[1]。目前，WSNs被廣泛應用在軍事[2]和民用[3]等領域。無線傳感器網絡節點對目標區域的覆蓋是WSNs中的關鍵問題，為了滿足覆蓋要求，往往采用隨機部署的方式，導致部分區域出現覆蓋盲區或者覆蓋冗余，降低覆蓋質量。因此，需要對傳感器網絡節點重新部署調整，通過控制調整移動節點在網絡中的分布，修復覆蓋空洞，提升WSNs覆蓋率。

近年來，群體智能被廣泛應用在WSNs覆蓋問題中。文獻[4]提出一種虛擬力導向粒子群的無線傳感器覆蓋優化算法，在粒子群位置更新公式中引入了虛擬力權重，提升了算法的收斂速度與搜索能力，但存在易陷入局部最優等缺點。文獻[5]通過判斷Voronoi圖頂點與傳感器節點之間的關系構造虛擬力，再將虛擬力擾動和布谷鳥搜索結合進行覆蓋優化，有效提高了網絡覆蓋率并降低了節點移動距離。混合策略改進蟻獅算法的網絡覆蓋優化算法[6]，取得了較好的覆蓋效果，但節點覆蓋效率及穩定性不足。文獻[7]提出的基于外推人工蜂群算法的節點部署優化方法，與原人工蜂群算法相比，表現出更快的尋優速度，但覆蓋率仍需改善。上述方法應用在WSNs覆蓋優化中，都存在網絡收斂速度慢、網絡覆蓋率低等問題。

為了有效降低節點的冗余度，提升網絡覆蓋率，擬提出一種自適應虛擬力導向蝙蝠算法(Adaptive Virtual Force-guided Bat Algorithm,AVFBA)的WSNs覆蓋優化策略。將虛擬力中的最大移動距離設計為指數衰減函數，算法自適應調整步長，加快網絡收斂速度。隨后，在原蝙蝠算法的基礎上加入萊維飛行策略擾動更新最優蝙蝠的位置。利用自適應虛擬力導向改進的蝙蝠算法，增強全局搜索和跳出局部極值的能力。最后，將AVFBA應用到WSNs覆蓋優化中，以期使網絡收斂速度更快，傳感器節點分布更均勻。

1 覆蓋問題模型及蝙蝠算法

1.1 覆蓋模型

假設監測區域為二維平面，且為正方形，將其劃分為L×M個網格點，并在該區域部署N個傳感器，每個傳感器都具有相同的感知半徑Ks和通信半徑Kc。為了保證網絡能夠正常通信，Kc設置為大于或等于Ks的2倍，則節點集合表示為S={s1,s2,…,sN}。假設在監測區域的某個節點si的位置坐標為(xi,yi)，目標節點zj的坐標為(xj,yj)，則Si與zj之間距離表達式為

(1)

采用布爾模型[8]作為節點感知模型，即目標處于節點的感知范圍就可以被成功感知。用p(si,zj)表示節點si對zj的感知質量，當節點zj的位置位于節點si的感知范圍內時，則感知質量為1；否則節點si對zj的感知質量為0，數學表達式為

(2)

任一目標都有可能會被多個傳感器協同探測，則目標點的感知概率為

(3)

該監測區的覆蓋率體現覆蓋質量，為所有傳感器節點覆蓋的目標點數除以該區域總的點數，定義為

(4)

節點的覆蓋效率體現網絡節點的冗余度，覆蓋效率越大，表示節點的分布越均勻，冗余程度較低。覆蓋效率為網絡中所有節點覆蓋的監測區域面積與所有節點總的感知范圍面積的比值，計算表達式為

(5)

1.2 蝙蝠算法

蝙蝠算法(Bat Algorithm,BA)是一種群體智能算法，由Yang等[9]于2010年提出，具有模型簡單、收斂速度快等優勢，其在解決優化問題上明顯優于粒子群等經典算法。BA算法已應用到如機器人路徑規劃[10]、故障診斷[11]、微電網優化[12]及神經網絡模型[13]等領域。BA的主要原理是模擬BA捕食獵物回聲定位，蝙蝠覓食時發出聲波，當聲波碰到獵物或者障礙物返回，蝙蝠接收到聲波即可定位。當蝙蝠與獵物距離越來越小，蝙蝠會增大脈沖發射頻度，響度則逐漸變小。BA的基本步驟如下。

(6)

(7)

(8)

步驟3進行局部搜索，位置更新為

x*(t+1)=x*(t)+εAt

(9)

其中：ε∈[-1,1]，At表示所有蝙蝠在t時刻的平均響度。

步驟4當蝙蝠離獵物越來越近時，響度逐漸變小，但發射頻度會逐漸變大，則更新響度和發射頻度，其計算表達式分別為

(10)

(11)

但是，將BA應用在無線傳感器網絡覆蓋中，還存在易陷入局部最優以及收斂速度慢等問題，覆蓋效果不佳。

2 改進的蝙蝠算法

在算法迭代中，群體智能算法包括BA等，后期會出現收斂速度較慢、易陷入局部最優解等問題。BA的局部位置利用最優蝙蝠進行更新，受到當前最好位置的影響，導致全局搜索能力不強，易陷入局部最優致使算法“早熟”。

針對上述問題，將利用虛擬力導向策略、萊維飛行擾動策略對BA進行改進，提升算法的收斂速度、全局搜索能力和跳出局部極值的能力，避免出現“早熟”現象。

2.1 虛擬力導向策略

(12)

其中：φχ、φζ分別為虛擬引力、斥力參數；dth為設定的距離閾值；θij為兩節點的方向夾角。

(13)

在VFA中，Umax一般設定為固定值，導致網絡無法快速收斂。因此，將Umax設定為指數衰減函數，在算法迭代過程中算法自適應調整步長，加快網絡收斂速度，其計算表達式為

(14)

其中，ω為指數衰減常數，取值范圍為(0,1]。選取ω=0.1，Umax隨著算法迭代逐漸減小，能緩解傳感器震蕩現象產生的影響，并減少了節點的無效移動[16]。

2.2 萊維飛行擾動策略

利用萊維飛行算法的隨機游走性能，提升BA跳出局部最優的能力，改善其易陷入局部最優的問題。將萊維飛行算法融入到BA局部位置更新中，增加算法的尋優性能，避免過早陷入“早熟”[17-18]。

萊維飛行是一種特殊的游走策略，其能夠增強信息的交互，避免搜索陷入局部最優。萊維飛行的隨機搜索路徑的表達式為

(15)

其中：β為參數，其取值范圍為0<β<2，一般取1.5；參數μ、ρ服從正態分布，表示為

(16)

其中，

(17)

在BA局部位置更新中只依靠最優蝙蝠的位置和平均響度，下一代最有蝙蝠的位置更新容易受到上一代最優蝙蝠的影響，失去種群多樣性。因此，在蝙蝠局部位置更新中加入萊維飛行，其計算表達式為

(18)

2.3 基于虛擬力導向BA的覆蓋優化策略

在大小為L×M的覆蓋區域中，隨機部署N個傳感器節點，每一種蝙蝠代表一種覆蓋方案，蝙蝠的種群數量為n。初始化所有蝙蝠的位置，以覆蓋率為優化目標，使得目標監測區域的覆蓋率最大化，即求得最佳蝙蝠的位置，使得Rv最大。將所提的虛擬力導向策略、萊維飛行擾動策略組合為WSNs覆蓋優化策略，稱為基于AVFBA的WSNs覆蓋優化策略,AVFBA流程如圖1所示。

圖1 AVFBA流程

基于AVFBA的WSNs覆蓋優化策略的具體步驟如下。

步驟1初始化網絡參數，包括種群規模n，維度D,蝙蝠的速度vi和位置xi。設置發射脈沖頻率最小值fmin、最大值fmax，初始響度Ai和脈沖頻度ri，以及最大迭代次數Tmax，節點移動的最大距離Umax，并設置目標函數f(x)。

步驟3通過式(6)更新脈沖頻率，并利用式(7)、式(8)和式(13)分別更新蝙蝠速度、位置。

步驟6判斷是否滿足終止條件，即達到最大終止條件，最大迭代次數或滿足適應度值為最優覆蓋率的要求。如果滿足，則停止迭代，輸出最優解；若不滿足，則轉至步驟3，直到滿足條件。

3 實驗分析

3.1 仿真環境設置

仿真實驗均采用MATLAB仿真軟件，設置WSNs各參數相同，并且每個算法運行50次以上，取其平均值保證公平性。采用BA、VFA和VFPSO作為對比算法，分析AVFBA算法的覆蓋率性能指標，各算法的參數設置如表1所示。

表1 各算法參數設置

3.2 仿真結果及分析

3.2.1 覆蓋率

仿真區域為100 m×100 m，對應節點數量N分別為25、30和35時的覆蓋率，如圖2(a)～2(c)所示。從圖2可以看出，隨著迭代次數的增加，AVFBA覆蓋率先急速上升，隨后趨于平穩，最終達到穩定。以N=30為例，AVFBA在迭代40次之后就已經收斂，而BA、VFPSO在57次、86次才逐漸收斂，分別提前了17次和46次。在覆蓋率方面，相較于BA、VFA和節點隨機拋灑等部署策略，覆蓋率分別提升了1.75%、5.86%和35.39%。對比結果表明，與BA、VFA、VFPSO算法相比，AVFBA算法收斂速度更快，網絡覆蓋率優勢明顯。

圖2 各算法覆蓋率對比

為了體現算法在不同環境下的適應性，采用不同的區域大小和節點數量，并設置WSNs各參數均相同，以及每個算法運行50次以上，取其平均值保證公平性。當節點數量變多時，3種群體智能算法都不同程度上陷入局部最優，導致網絡覆蓋率下降。尤其是當區域大小為100 m×100 m、N=25和區域大小400 m×400 m、N=400對比時，AVFBA覆蓋率僅下降1.88%，而VFPSO、BA分別下降6.25%、17.73%。這是因為AVFBA加入了自適應虛擬力和萊維飛行，增強了跳出局部最優的能力。僅當區域大小為400 m×400 m、節點數量N=400時，AVFBA覆蓋率低于VFA。在其余不同區域大小和節點數量情況下，AVFBA網絡覆蓋率均大于其他3種算法，表明AVFBA適應性強。各算法覆蓋率對比情況如表2所示。

表2 各算法覆蓋率對比

當仿真區域大小為100 m×100 m，N=30時，4種算法覆蓋部署如圖3所示。圖3(a)～圖3(d)分別為執行BA、VFA、AVFBA和VFPSO后的節點分布與覆蓋部署效果。其中：X表示覆蓋區域的長；Y表示覆蓋區域的寬。

圖3 4種算法覆蓋部署

從圖3中可以明顯看出，BA和VFPSO覆蓋圖有較多的覆蓋冗余，這是由于BA和粒子群算法易陷入局部最優，導致覆蓋率無法持續增長。而VFA覆蓋圖的覆蓋盲區較大，則是因為原虛擬力算法將迭代步長設置為固定步長，無法自適應調整步長，導致算法產生較差的覆蓋效果。AVFBA由于加入了萊維飛行策略和虛擬力導向策略，增強了全局搜索和跳出局部極值的能力，覆蓋部署圖中節點分布更加均勻，覆蓋漏洞較小，取得了很好的覆蓋效果。

3.2.2 覆蓋效率

為了進一步檢驗算法在不同數量的網絡節點情況下的性能，以及驗證是否能有效降低節點冗余度，對各算法的覆蓋效率進行了測試。

算法的覆蓋效率越高，說明覆蓋冗余較小，節點分布更加均勻，部署的成本更低。仿真實驗采用的區域大小面積為100 m×100 m，節點數量N分別為25、30和35，實驗結果如圖4所示。

圖4 節點覆蓋效率對比

由圖4可以看出，在相同的區域內，隨著節點數量增多，節點覆蓋效率都在逐漸降低，表示覆蓋冗余在不斷增加。但在3種不同的節點數量情況下，AVFBA的覆蓋效率均優于其他3種算法，表明AVFBA的覆蓋性能更優。

4 結語

為了提升網絡覆蓋率，優化WSNs節點布局，提出了一種基于自適應虛擬力導向蝙蝠算法的WSNs覆蓋優化策略。通過將虛擬力的節點最大移動距離設計為指數衰減函數，并將自適應虛擬力應用在蝙蝠全局位置更新時引導蝙蝠位置，加快收斂速度，提升網絡覆蓋率。再加入萊維飛行擾動策略產生局部新解，增強算法跳出局部最優的能力。仿真結果表明，AVFBA相比BA、VFA、VFPSO，網絡收斂速度更快，其覆蓋率更高，優化了WSNs的網絡布局，降低了節點冗余度。