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

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

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

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

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

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

1.1 覆蓋模型

假設(shè)監(jiān)測區(qū)域?yàn)槎S平面，且為正方形，將其劃分為L×M個(gè)網(wǎng)格點(diǎn)，并在該區(qū)域部署N個(gè)傳感器，每個(gè)傳感器都具有相同的感知半徑Ks和通信半徑Kc。為了保證網(wǎng)絡(luò)能夠正常通信，Kc設(shè)置為大于或等于Ks的2倍，則節(jié)點(diǎn)集合表示為S={s1,s2,…,sN}。假設(shè)在監(jiān)測區(qū)域的某個(gè)節(jié)點(diǎn)si的位置坐標(biāo)為(xi,yi)，目標(biāo)節(jié)點(diǎn)zj的坐標(biāo)為(xj,yj)，則Si與zj之間距離表達(dá)式為

(1)

采用布爾模型[8]作為節(jié)點(diǎn)感知模型，即目標(biāo)處于節(jié)點(diǎn)的感知范圍就可以被成功感知。用p(si,zj)表示節(jié)點(diǎn)si對zj的感知質(zhì)量，當(dāng)節(jié)點(diǎn)zj的位置位于節(jié)點(diǎn)si的感知范圍內(nèi)時(shí)，則感知質(zhì)量為1；否則節(jié)點(diǎn)si對zj的感知質(zhì)量為0，數(shù)學(xué)表達(dá)式為

(2)

任一目標(biāo)都有可能會(huì)被多個(gè)傳感器協(xié)同探測，則目標(biāo)點(diǎn)的感知概率為

(3)

該監(jiān)測區(qū)的覆蓋率體現(xiàn)覆蓋質(zhì)量，為所有傳感器節(jié)點(diǎn)覆蓋的目標(biāo)點(diǎn)數(shù)除以該區(qū)域總的點(diǎn)數(shù)，定義為

(4)

節(jié)點(diǎn)的覆蓋效率體現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的冗余度，覆蓋效率越大，表示節(jié)點(diǎn)的分布越均勻，冗余程度較低。覆蓋效率為網(wǎng)絡(luò)中所有節(jié)點(diǎn)覆蓋的監(jiān)測區(qū)域面積與所有節(jié)點(diǎn)總的感知范圍面積的比值，計(jì)算表達(dá)式為

(5)

1.2 蝙蝠算法

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

(6)

(7)

(8)

步驟3進(jìn)行局部搜索，位置更新為

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

(9)

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

步驟4當(dāng)蝙蝠離獵物越來越近時(shí)，響度逐漸變小，但發(fā)射頻度會(huì)逐漸變大，則更新響度和發(fā)射頻度，其計(jì)算表達(dá)式分別為

(10)

(11)

但是，將BA應(yīng)用在無線傳感器網(wǎng)絡(luò)覆蓋中，還存在易陷入局部最優(yōu)以及收斂速度慢等問題，覆蓋效果不佳。

2 改進(jìn)的蝙蝠算法

在算法迭代中，群體智能算法包括BA等，后期會(huì)出現(xiàn)收斂速度較慢、易陷入局部最優(yōu)解等問題。BA的局部位置利用最優(yōu)蝙蝠進(jìn)行更新，受到當(dāng)前最好位置的影響，導(dǎo)致全局搜索能力不強(qiáng)，易陷入局部最優(yōu)致使算法“早熟”。

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

2.1 虛擬力導(dǎo)向策略

(12)

其中：φχ、φζ分別為虛擬引力、斥力參數(shù)；dth為設(shè)定的距離閾值；θij為兩節(jié)點(diǎn)的方向夾角。

(13)

在VFA中，Umax一般設(shè)定為固定值，導(dǎo)致網(wǎng)絡(luò)無法快速收斂。因此，將Umax設(shè)定為指數(shù)衰減函數(shù)，在算法迭代過程中算法自適應(yīng)調(diào)整步長，加快網(wǎng)絡(luò)收斂速度，其計(jì)算表達(dá)式為

(14)

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

2.2 萊維飛行擾動(dòng)策略

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

萊維飛行是一種特殊的游走策略，其能夠增強(qiáng)信息的交互，避免搜索陷入局部最優(yōu)。萊維飛行的隨機(jī)搜索路徑的表達(dá)式為

(15)

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

(16)

其中，

(17)

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

(18)

2.3 基于虛擬力導(dǎo)向BA的覆蓋優(yōu)化策略

在大小為L×M的覆蓋區(qū)域中，隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，每一種蝙蝠代表一種覆蓋方案，蝙蝠的種群數(shù)量為n。初始化所有蝙蝠的位置，以覆蓋率為優(yōu)化目標(biāo)，使得目標(biāo)監(jiān)測區(qū)域的覆蓋率最大化，即求得最佳蝙蝠的位置，使得Rv最大。將所提的虛擬力導(dǎo)向策略、萊維飛行擾動(dòng)策略組合為WSNs覆蓋優(yōu)化策略，稱為基于AVFBA的WSNs覆蓋優(yōu)化策略,AVFBA流程如圖1所示。

圖1 AVFBA流程

基于AVFBA的WSNs覆蓋優(yōu)化策略的具體步驟如下。

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

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

步驟6判斷是否滿足終止條件，即達(dá)到最大終止條件，最大迭代次數(shù)或滿足適應(yīng)度值為最優(yōu)覆蓋率的要求。如果滿足，則停止迭代，輸出最優(yōu)解；若不滿足，則轉(zhuǎn)至步驟3，直到滿足條件。

3 實(shí)驗(yàn)分析

3.1 仿真環(huán)境設(shè)置

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

表1 各算法參數(shù)設(shè)置

3.2 仿真結(jié)果及分析

3.2.1 覆蓋率

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

圖2 各算法覆蓋率對比

為了體現(xiàn)算法在不同環(huán)境下的適應(yīng)性，采用不同的區(qū)域大小和節(jié)點(diǎn)數(shù)量，并設(shè)置WSNs各參數(shù)均相同，以及每個(gè)算法運(yùn)行50次以上，取其平均值保證公平性。當(dāng)節(jié)點(diǎn)數(shù)量變多時(shí)，3種群體智能算法都不同程度上陷入局部最優(yōu)，導(dǎo)致網(wǎng)絡(luò)覆蓋率下降。尤其是當(dāng)區(qū)域大小為100 m×100 m、N=25和區(qū)域大小400 m×400 m、N=400對比時(shí)，AVFBA覆蓋率僅下降1.88%，而VFPSO、BA分別下降6.25%、17.73%。這是因?yàn)锳VFBA加入了自適應(yīng)虛擬力和萊維飛行，增強(qiáng)了跳出局部最優(yōu)的能力。僅當(dāng)區(qū)域大小為400 m×400 m、節(jié)點(diǎn)數(shù)量N=400時(shí)，AVFBA覆蓋率低于VFA。在其余不同區(qū)域大小和節(jié)點(diǎn)數(shù)量情況下，AVFBA網(wǎng)絡(luò)覆蓋率均大于其他3種算法，表明AVFBA適應(yīng)性強(qiáng)。各算法覆蓋率對比情況如表2所示。

表2 各算法覆蓋率對比

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

圖3 4種算法覆蓋部署

從圖3中可以明顯看出，BA和VFPSO覆蓋圖有較多的覆蓋冗余，這是由于BA和粒子群算法易陷入局部最優(yōu)，導(dǎo)致覆蓋率無法持續(xù)增長。而VFA覆蓋圖的覆蓋盲區(qū)較大，則是因?yàn)樵摂M力算法將迭代步長設(shè)置為固定步長，無法自適應(yīng)調(diào)整步長，導(dǎo)致算法產(chǎn)生較差的覆蓋效果。AVFBA由于加入了萊維飛行策略和虛擬力導(dǎo)向策略，增強(qiáng)了全局搜索和跳出局部極值的能力，覆蓋部署圖中節(jié)點(diǎn)分布更加均勻，覆蓋漏洞較小，取得了很好的覆蓋效果。

3.2.2 覆蓋效率

為了進(jìn)一步檢驗(yàn)算法在不同數(shù)量的網(wǎng)絡(luò)節(jié)點(diǎn)情況下的性能，以及驗(yàn)證是否能有效降低節(jié)點(diǎn)冗余度，對各算法的覆蓋效率進(jìn)行了測試。

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

圖4 節(jié)點(diǎn)覆蓋效率對比

由圖4可以看出，在相同的區(qū)域內(nèi)，隨著節(jié)點(diǎn)數(shù)量增多，節(jié)點(diǎn)覆蓋效率都在逐漸降低，表示覆蓋冗余在不斷增加。但在3種不同的節(jié)點(diǎn)數(shù)量情況下，AVFBA的覆蓋效率均優(yōu)于其他3種算法，表明AVFBA的覆蓋性能更優(yōu)。

4 結(jié)語

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