基于特征點(diǎn)集GABC算法的WSN覆蓋優(yōu)化

侯義飛，楊 勇

(河南工業(yè)大學(xué)電氣工程學(xué)院，河南 鄭州 450001)

0 引 言

網(wǎng)絡(luò)覆蓋是無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)技術(shù)研究中的一個(gè)基本研究問(wèn)題，其反應(yīng)了WSN對(duì)物理世界的監(jiān)測(cè)能力[1]，而覆蓋率是衡量網(wǎng)絡(luò)覆蓋質(zhì)量的重要標(biāo)準(zhǔn)之一。在實(shí)際應(yīng)用中，應(yīng)當(dāng)使目標(biāo)區(qū)域的覆蓋最大化，盡量使其做到覆蓋無(wú)死角[2]。通常，傳感器節(jié)點(diǎn)都是隨機(jī)拋灑在監(jiān)測(cè)區(qū)域內(nèi)的，容易造成傳感器節(jié)點(diǎn)分布不均勻，導(dǎo)致覆蓋效果不理想。通過(guò)覆蓋優(yōu)化算法對(duì)初始部署的節(jié)點(diǎn)位置進(jìn)行調(diào)整，可以取得很好的覆蓋效果[3]。目前，移動(dòng)節(jié)點(diǎn)覆蓋算法有虛擬力算法[4]與群體智能算法等。

近年來(lái)，有許多學(xué)者將群體智能算法成功應(yīng)用到WSN覆蓋控制中[5-6]。文獻(xiàn)[7]將人工魚(yú)群算法應(yīng)用到WSN覆蓋領(lǐng)域中，雖然網(wǎng)絡(luò)覆蓋有所提高，但是算法收斂速度較慢。文獻(xiàn)[8]將粒子群算法應(yīng)用到WSN覆蓋優(yōu)化中，有效提高了網(wǎng)絡(luò)的覆蓋率，但容易陷入局部最優(yōu)。人工蜂群算法是一種新興的群智能算法，結(jié)構(gòu)簡(jiǎn)單，參數(shù)少，有著分層協(xié)作機(jī)制等優(yōu)點(diǎn)，被廣泛應(yīng)用于WSN覆蓋優(yōu)化問(wèn)題中[9-10]。文獻(xiàn)[11]提出了一種改進(jìn)人工蜂群算法，改進(jìn)偵查蜂搜索公式，加快算法收斂速度。文獻(xiàn)[12]利用分層機(jī)制改善人工蜂群算法的性能，但算法進(jìn)行局部搜索時(shí)需要大量迭代，使搜索速度變慢。文獻(xiàn)[13]利用基于反向?qū)W習(xí)策略的人工蜂群算法優(yōu)化部署移動(dòng)傳感器節(jié)點(diǎn)，可以減少算法的迭代次數(shù)，但是容易陷入局部最優(yōu)解。

為了提高WSN的覆蓋性能和網(wǎng)絡(luò)的覆蓋率，并且在求解覆蓋率時(shí)可以減少計(jì)算量，本文將特征點(diǎn)集和全局最優(yōu)解引入人工蜂群算法中，提出一種基于特征點(diǎn)集全局最優(yōu)解人工蜂群算法(Gbest-guided Artificial Bee Colony, GABC)，并將其應(yīng)用到WSN網(wǎng)絡(luò)覆蓋領(lǐng)域。通過(guò)仿真實(shí)驗(yàn)，重點(diǎn)對(duì)比了標(biāo)準(zhǔn)ABC (Artificial Bee Colony)算法和GABC算法在網(wǎng)絡(luò)覆蓋上的性能。

1 網(wǎng)絡(luò)模型建立

1.1 節(jié)點(diǎn)感知模型

為了使節(jié)點(diǎn)監(jiān)測(cè)更接近實(shí)際的情況，本文選取的節(jié)點(diǎn)感知模型為概率感知模型[14]：

(1)

其中：m是區(qū)域內(nèi)任意一點(diǎn)；si是第i個(gè)傳感器節(jié)點(diǎn)；d(si,m)表示si與點(diǎn)m的歐氏距離；Rs是感知半徑，Re(0≤Re≤Rs)是傳感器監(jiān)測(cè)的一種不確定程度；α1、α2、β1、β2是傳感器節(jié)點(diǎn)本身相關(guān)的參數(shù)；λ1=Re-Rs+d(si,m),λ2=Re+Rs-d(si,m)。

網(wǎng)絡(luò)中多個(gè)傳感器同時(shí)監(jiān)測(cè)到同一點(diǎn)m的聯(lián)合覆蓋概率可以用下式表示：

(2)

其中，S表示傳感器節(jié)點(diǎn)集合。

1.2 相關(guān)定義與定理

如圖1所示，m1、m2是相距為L(zhǎng)的2個(gè)被監(jiān)測(cè)點(diǎn)，區(qū)域內(nèi)N個(gè)傳感器節(jié)點(diǎn)對(duì)m1和m2的聯(lián)合覆蓋率分別是ρ1和ρ2。當(dāng)N=1時(shí)，在以m1為圓心、m1A為半徑的圓周上任意部署傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)監(jiān)測(cè)到點(diǎn)m1的覆蓋率均為ρ1。

圖1 定理1示意圖

定理1[15]如圖1所示，當(dāng)N=1且節(jié)點(diǎn)在A處，A為m1、m2連線上與圓m1相交距m2更遠(yuǎn)的那一點(diǎn)，ρ2取最小值ρ2min。

定理2[16]假設(shè)點(diǎn)m是區(qū)域內(nèi)任意一點(diǎn)，如果其覆蓋率滿足ρ=f1(ε,L)時(shí)，在以點(diǎn)m為圓心，L為半徑的區(qū)域內(nèi)的點(diǎn)的覆蓋率都大于等于ε。其中，ε為概率閾值。

(3)

通過(guò)定理1和定理2可以得到區(qū)域的特征，可以分析特征點(diǎn)集來(lái)等價(jià)分析整個(gè)區(qū)域的性能。通過(guò)分析傳感器節(jié)點(diǎn)對(duì)特征點(diǎn)的覆蓋就可以知道傳感器節(jié)點(diǎn)對(duì)整個(gè)區(qū)域的覆蓋情況。

2 基于特征點(diǎn)集全局最優(yōu)解人工蜂群算法

2.1 人工蜂群算法

人工蜂群算法是Karaboga等人[17]根據(jù)蜜蜂的采蜜行為提出的一種群體智能算法。它與粒子群算法和遺傳算法相比較具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少等優(yōu)點(diǎn)，有著廣泛的應(yīng)用。人工蜂群算法將蜂群分為雇傭蜂、跟隨蜂和偵查蜂[18]。雇傭蜂和跟隨蜂的任務(wù)是在蜂巢附近尋找優(yōu)質(zhì)蜜源，而偵查蜂的任務(wù)是觀察是否陷入局部最優(yōu)解。雇傭蜂的個(gè)數(shù)和跟隨蜂的個(gè)數(shù)與蜜源的數(shù)量SN相等，算法在D維空間中搜索。每個(gè)蜜源的位置表示問(wèn)題的一個(gè)可能解，用適應(yīng)度函數(shù)對(duì)每個(gè)蜜源進(jìn)行評(píng)價(jià)[19-21]。

雇傭蜂和跟隨蜂按照公式(4)尋找新蜜源：

(4)

其中：i∈{1,2,…,SN};j∈{1,2,…,D};rij是區(qū)間[-1,1]上的隨機(jī)數(shù)；k∈{1,2,…,SN}，且k≠i。

在蜜源初始化或每個(gè)蜜源被分配給每個(gè)雇傭蜂后，蜜源的優(yōu)劣由適應(yīng)度來(lái)評(píng)價(jià)，用公式(5)來(lái)計(jì)算每個(gè)解的適應(yīng)度。若求解最大值問(wèn)題，則可取目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。

(5)

其中，F(xiàn)i為第i個(gè)蜜源的適應(yīng)值，fi為第i個(gè)個(gè)體對(duì)于優(yōu)化問(wèn)題的目標(biāo)函數(shù)。

標(biāo)準(zhǔn)ABC算法采用貪婪選擇策略保留優(yōu)秀個(gè)體的解，每個(gè)蜜源被選擇的概率為：

(6)

跟隨蜂選擇雇傭蜂所搜索的解，然后跟隨蜂通過(guò)公式(6)來(lái)計(jì)算蜜源被保留下來(lái)的選擇概率，保留雇傭蜂階段較好的解，用來(lái)提高解的質(zhì)量。

如果搜索次數(shù)到達(dá)limit值后，蜜源的質(zhì)量沒(méi)有得到提升，雇傭蜂就會(huì)放棄對(duì)該蜜源的搜索，角色轉(zhuǎn)變?yōu)閭刹旆洹＜尤雮刹榉洳襟E的目的是為了避免人工蜂群算法陷入局部最優(yōu)解。偵查蜂將隨機(jī)生成新的蜜源用來(lái)代替原來(lái)的蜜源，計(jì)算如下[22]：

(7)

2.2 全局最優(yōu)解人工蜂群算法

在人工蜂群算法中，雇傭蜂和跟隨蜂都會(huì)隨機(jī)產(chǎn)生新的解，算法容易出現(xiàn)收斂速度慢和早熟的問(wèn)題。因此，人工蜂群算法有很大的改進(jìn)和提高空間。

受粒子群算法的啟發(fā)[23]，為了提高人工蜂群算法的開(kāi)發(fā)能力，利用全局最優(yōu)解[24]來(lái)引導(dǎo)候選解的產(chǎn)生，將公式(4)的搜索方程修改為：

(8)

其中：i∈{1,2,…,SN};j∈{1,2,…,D};rij是區(qū)間[-1,1]上的隨機(jī)數(shù)，控制領(lǐng)域范圍；k∈{1,2,…,SN}，且k≠i;xgj是蜂群當(dāng)前最優(yōu)解的第j維值；ψij是[0,C]間的隨機(jī)數(shù)，C為正數(shù)，C取1.5。

通過(guò)加入全局最優(yōu)項(xiàng)，GABC算法在搜索最優(yōu)解的時(shí)候，可以朝著最優(yōu)解的方向迅速靠攏，使算法很快找到最優(yōu)解，加快算法的收斂速度和避免算法出現(xiàn)早熟現(xiàn)象。

2.3 特征點(diǎn)集的GABC算法優(yōu)化無(wú)線傳感網(wǎng)

2.3.1 特征點(diǎn)選取

圖2 特征點(diǎn)的示意圖

2.3.2 網(wǎng)絡(luò)覆蓋的優(yōu)化目標(biāo)函數(shù)

GABC算法求解網(wǎng)絡(luò)覆蓋率用的是基于網(wǎng)格點(diǎn)來(lái)求解的，要想得到接近實(shí)際的覆蓋率，需要將網(wǎng)絡(luò)劃分成稠密的網(wǎng)格點(diǎn)。其中，網(wǎng)格點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)大于特征點(diǎn)的個(gè)數(shù)，這樣會(huì)導(dǎo)致計(jì)算量很大。因此，利用特征點(diǎn)集來(lái)求解網(wǎng)絡(luò)中的覆蓋率，可以有效地減少計(jì)算量。本文用特征點(diǎn)集優(yōu)化覆蓋公式(9)求解最大覆蓋率。

Maximizeρ

(9)

其中：ROI是被監(jiān)測(cè)區(qū)域；M是特征點(diǎn)數(shù)量；N是傳感器節(jié)點(diǎn)數(shù)量；m是區(qū)域內(nèi)任意一點(diǎn)；pj是第j個(gè)特征點(diǎn)；d(m,pj)是區(qū)域內(nèi)任一點(diǎn)m到特征點(diǎn)pj的距離；FPS是特征點(diǎn)集(Feature Point Set)；ρi,pj是第i個(gè)傳感器節(jié)點(diǎn)對(duì)特征點(diǎn)pj的覆蓋率；ρpj是所有節(jié)點(diǎn)對(duì)pj的聯(lián)合覆蓋率；ρ是所有pj的覆蓋率ρpj中的最小值；第1個(gè)條件表示區(qū)域內(nèi)任一點(diǎn)都至少被一個(gè)特征點(diǎn)包絡(luò)。

將無(wú)線傳感器網(wǎng)絡(luò)性能指標(biāo)中的所有特征點(diǎn)的覆蓋率最小值作為適應(yīng)度值，因此，無(wú)線傳感器網(wǎng)絡(luò)的適應(yīng)度函數(shù)的計(jì)算方法為：

ρ=min{[ρpj]M×1}

(10)

無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化，最終的目的是使網(wǎng)絡(luò)的覆蓋率最大，也就是說(shuō)，求解適應(yīng)度函數(shù)ρ的最大值。

2.3.3 算法整體流程

將GABC算法應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)領(lǐng)域，用來(lái)提高網(wǎng)絡(luò)的覆蓋率。其中種群中每個(gè)個(gè)體就是傳感器節(jié)點(diǎn)的位置，適應(yīng)度值代表網(wǎng)絡(luò)覆蓋率。適應(yīng)度函數(shù)為公式(10)，其目的就是讓公式(10)取得最大值的最佳位置。算法的具體實(shí)現(xiàn)步驟為：

Step1初始化參數(shù)：目標(biāo)區(qū)域大小、將區(qū)域劃分成的若干特征點(diǎn)、傳感器節(jié)點(diǎn)個(gè)數(shù)、感知半徑Rs的大小、蜜源數(shù)量SN、總的蜜蜂數(shù)量BN，其中雇傭蜂的數(shù)量和觀察蜂的數(shù)量相等且均為BN/2。設(shè)置最大迭代次數(shù)MaxCycle，迭代次數(shù)iter=0，最大領(lǐng)域開(kāi)采度limit，隨機(jī)生成BN/2個(gè)蜜源位置，設(shè)置一只偵查蜂。

Step2對(duì)每個(gè)隨機(jī)生成的SN個(gè)初始解，根據(jù)公式(9)與公式(10)計(jì)算每個(gè)蜜源的覆蓋率。

Step3選出傳感器節(jié)點(diǎn)最優(yōu)位置。

Step4在雇傭蜂階段，雇傭蜂按照公式(8)在鄰域內(nèi)搜索新的解，并對(duì)新解計(jì)算覆蓋率。然后對(duì)邊界進(jìn)行處理，使其不超過(guò)監(jiān)測(cè)區(qū)域的邊界。

Step5比較新產(chǎn)生的解的覆蓋率與原來(lái)解的覆蓋率的大小，取較高的覆蓋率，并記錄此時(shí)解的位置。

Step6在跟隨蜂階段，跟隨蜂按照公式(6)計(jì)算選擇概率Pi。跟隨蜂根據(jù)選擇概率選擇較好的蜜源，并按照公式(8)在蜜源鄰域內(nèi)尋找新的解，同樣計(jì)算比較新舊解的覆蓋率大小，取較高的一個(gè)，并記錄此時(shí)解的位置。

Step7如果一個(gè)蜜源的位置經(jīng)過(guò)limit次均未更新，則該位置的雇傭蜂變?yōu)閭刹榉?，按照公?7)隨機(jī)產(chǎn)生新解。

Step8記錄到目前為止的最優(yōu)解的位置。

Step9判斷iter與MaxCycle的大小，如果iter≤MaxCycle，則跳轉(zhuǎn)至Step4，否則算法終止運(yùn)行，輸出最優(yōu)解。

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

3.1 無(wú)線傳感網(wǎng)覆蓋優(yōu)化仿真實(shí)驗(yàn)設(shè)置

假設(shè)監(jiān)測(cè)區(qū)域?yàn)?00 m×100 m的平面區(qū)域，每個(gè)傳感器的監(jiān)測(cè)半徑Rs=10 m,Re=3 m，傳感器節(jié)點(diǎn)選用公式(1)的概率感知模型。其中，α1=β1=β2=1,α2=0。算法在Windows 10操作系統(tǒng)、MATLAB2014b仿真平臺(tái)上實(shí)現(xiàn)。算法最大迭代次數(shù)為300次，limit值為100，蜜源數(shù)SN為30，維數(shù)D為傳感器節(jié)點(diǎn)的個(gè)數(shù)。覆蓋閾值ε=0.9500，最大特征點(diǎn)距MFPD≤8.0704，取整數(shù)8。

3.2 無(wú)線傳感網(wǎng)覆蓋優(yōu)化性能比較

取傳感器節(jié)點(diǎn)個(gè)數(shù)為30個(gè)時(shí)，用2種算法分別對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行優(yōu)化。GABC算法和ABC算法分別運(yùn)行10次，取每次運(yùn)行的覆蓋率的平均值繪制成曲線圖，如圖3所示，最終得到算法部署后的傳感器節(jié)點(diǎn)分布圖。30個(gè)傳感器節(jié)點(diǎn)在ABC算法和GABC算法優(yōu)化的每個(gè)特征點(diǎn)的覆蓋率對(duì)比圖，如圖4所示。

圖3 節(jié)點(diǎn)平均覆蓋率變化曲線

從圖3可以看出，與ABC算法相比，GABC算法明顯地能夠提高網(wǎng)絡(luò)的覆蓋率。

圖4 2種算法優(yōu)化特征點(diǎn)覆蓋率對(duì)比圖

從圖4可以看出，GABC算法傳感器節(jié)點(diǎn)對(duì)每個(gè)特征點(diǎn)的覆蓋率絕大多數(shù)都比較高，ABC算法得到的每個(gè)特征點(diǎn)覆蓋率整體上要劣于GABC算法。研究對(duì)特征點(diǎn)的覆蓋可以等效研究對(duì)整個(gè)區(qū)域的覆蓋，2種算法對(duì)特征點(diǎn)的覆蓋可以反映出，GABC算法比ABC算法可以提高網(wǎng)絡(luò)的覆蓋率。

30個(gè)傳感器節(jié)點(diǎn)隨機(jī)初始分布圖如5所示。用ABC算法部署傳感器節(jié)點(diǎn)后，網(wǎng)絡(luò)中節(jié)點(diǎn)分布圖如圖6所示。用GABC算法部署傳感器節(jié)點(diǎn)后節(jié)點(diǎn)分布圖如圖7所示。從最終分布圖可以看出，GABC算法可以使傳感器節(jié)點(diǎn)分布得更均勻進(jìn)而提高網(wǎng)絡(luò)的覆蓋率。

圖5 隨機(jī)部署節(jié)點(diǎn)分布

圖6 ABC算法部署后節(jié)點(diǎn)分布

圖7 GABC算法部署后節(jié)點(diǎn)分布

由于研究網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)對(duì)特征點(diǎn)的覆蓋相當(dāng)于研究網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)對(duì)整個(gè)區(qū)域的覆蓋情況，這樣可以減少對(duì)覆蓋率的計(jì)算量，因此，可以通過(guò)研究傳感器節(jié)點(diǎn)對(duì)特征點(diǎn)的覆蓋率，反應(yīng)出傳感器節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的覆蓋率。在30、50、70個(gè)傳感器節(jié)點(diǎn)，GABC算法和ABC算法重復(fù)運(yùn)行10次，對(duì)所有特征點(diǎn)覆蓋率的統(tǒng)計(jì)結(jié)果如表1所示。

表1 隨機(jī)試驗(yàn)下覆蓋率的統(tǒng)計(jì)結(jié)果分析

從表1中不同節(jié)點(diǎn)數(shù)量下對(duì)網(wǎng)絡(luò)中所有特征點(diǎn)的覆蓋率統(tǒng)計(jì)的結(jié)果，可以看出，GABC算法對(duì)特征點(diǎn)的覆蓋率都好于ABC算法。從均值和標(biāo)準(zhǔn)差可以看出，GABC算法在覆蓋性能和穩(wěn)定性都比標(biāo)準(zhǔn)ABC算法更好，說(shuō)明GABC算法可以有效提高網(wǎng)絡(luò)的覆蓋率。

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)特征點(diǎn)集概念的研究，將傳統(tǒng)的區(qū)域覆蓋問(wèn)題轉(zhuǎn)化成對(duì)特征點(diǎn)的覆蓋問(wèn)題，提出了一種基于特征點(diǎn)集的GABC算法來(lái)優(yōu)化WSN問(wèn)題。該算法減少了求解覆蓋率的計(jì)算量，改善了ABC算法容易陷入局部最優(yōu)解的不足，最后通過(guò)仿真實(shí)驗(yàn)表明基于特征點(diǎn)集的GABC算法可以有效提高網(wǎng)絡(luò)的覆蓋率。今后將對(duì)特征點(diǎn)集的選取方式是否對(duì)覆蓋率有所影響進(jìn)行進(jìn)一步的研究。