基于改進(jìn)螢火蟲算法的覆蓋優(yōu)化方法?

茍平章孫現(xiàn)超

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

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

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

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

1 系統(tǒng)模型與術(shù)語(yǔ)定義

1.1 網(wǎng)絡(luò)模型

本文的網(wǎng)絡(luò)模型假設(shè)如下:

假設(shè)1 在無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)區(qū)域內(nèi)部署N個(gè)傳感器節(jié)點(diǎn)，其中包括Nm個(gè)移動(dòng)傳感器節(jié)點(diǎn)，Nn個(gè)靜態(tài)傳感器節(jié)點(diǎn)。 傳感器節(jié)點(diǎn)集合定義為:

假設(shè)2 網(wǎng)絡(luò)中每個(gè)傳感器節(jié)點(diǎn)都可以通過(guò)GPS或某些位置服務(wù)知道其位置信息。

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

假設(shè)4 目標(biāo)區(qū)域內(nèi)的移動(dòng)傳感器節(jié)點(diǎn)具有充足能量，確保其能夠移動(dòng)到指定位置。

1.2 能量模型

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

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

1.3 感知模型

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

1.4 術(shù)語(yǔ)定義

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

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

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

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

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

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

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

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

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

2.1.1 IFA 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 2 在目標(biāo)區(qū)域內(nèi)隨機(jī)拋灑傳感器節(jié)點(diǎn)，并將每個(gè)傳感器節(jié)點(diǎn)看成一個(gè)螢火蟲，從而形成螢火蟲群；

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

Step 4 每?jī)蓚€(gè)傳感器節(jié)點(diǎn)進(jìn)行相互比較，適應(yīng)度值小的傳感器節(jié)點(diǎn)則按照位置公式(12)進(jìn)行位置更新；

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

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

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

目標(biāo)位置優(yōu)化方法以能量?jī)?yōu)先為原則，在不減少網(wǎng)絡(luò)覆蓋率的前提下，通過(guò)減少移動(dòng)傳感器節(jié)點(diǎn)的移動(dòng)距離，從而降低節(jié)點(diǎn)移動(dòng)能量消耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。 該方法從移動(dòng)距離優(yōu)化、能量?jī)?yōu)先、移動(dòng)節(jié)點(diǎn)目標(biāo)位置交換3 個(gè)方面對(duì)候選目標(biāo)位置進(jìn)行優(yōu)化。

具體方案描述如下:

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

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

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

圖3 能量?jī)?yōu)先

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

圖4 位置交換原則

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

3.1 實(shí)驗(yàn)環(huán)境

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

表1 網(wǎng)絡(luò)環(huán)境和參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 移動(dòng)距離分析

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

圖5 平均移動(dòng)距離與節(jié)點(diǎn)比例的關(guān)系

3.2.2 網(wǎng)絡(luò)覆蓋優(yōu)化分析

將IFA 算法與文獻(xiàn)[12]中的CS 算法，以及FA算法作比較，圖6 分別為三種算法在相同條件下經(jīng)過(guò)多次實(shí)驗(yàn)得到的網(wǎng)絡(luò)覆蓋率與迭代次數(shù)的柱狀圖。 分析圖6 可知，三種算法的網(wǎng)絡(luò)覆蓋率都隨著迭代次數(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ù)達(dá)到150 次時(shí)，可以達(dá)到94.95%的覆蓋率，而其他兩種算法分別在200 次和250 次才達(dá)到最優(yōu)的覆蓋效果，因此IFA 算法具有更好的收斂性。

圖6 網(wǎng)絡(luò)覆蓋優(yōu)化迭代柱狀圖

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

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

圖7 網(wǎng)絡(luò)總能耗與迭代次數(shù)的關(guān)系

為驗(yàn)證該方法的可行性，分別對(duì)該方法的2 個(gè)步驟的優(yōu)化結(jié)果進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖8～圖12所示。

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

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

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

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

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

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

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

4 總結(jié)

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