周海鵬,高 芹,蔣豐千,余大為,喬 焰,李 旸

(1.安徽農(nóng)業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院, 合肥 230036; 2.農(nóng)業(yè)部農(nóng)業(yè)物聯(lián)網(wǎng)技術(shù)集成與應(yīng)用重點(diǎn)實(shí)驗(yàn)室(安徽農(nóng)業(yè)大學(xué)),合肥 230036)(*通信作者電子郵箱ly-and@qq.com)

0 引言

覆蓋控制一直是無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)的研究熱點(diǎn),它反映了WSN提供感知服務(wù)的質(zhì)量。保證對(duì)監(jiān)測(cè)區(qū)域一定的覆蓋是WSN發(fā)揮功能的關(guān)鍵。在實(shí)際應(yīng)用場(chǎng)景中,受目標(biāo)區(qū)域物理環(huán)境的限制,傳感器節(jié)點(diǎn)一般采用撒播方式隨機(jī)部署。然而,該方式部署的WSN存在節(jié)點(diǎn)分布不均、覆蓋率低、冗余度高等缺陷。部署動(dòng)態(tài)節(jié)點(diǎn),通過覆蓋優(yōu)化算法對(duì)初始部署的節(jié)點(diǎn)位置進(jìn)行調(diào)整,可以取得較好效果。

群體智能算法給解決WSN覆蓋優(yōu)化問題帶來了新思路,近年來大量國(guó)內(nèi)外學(xué)者將群體智能算法應(yīng)用于WSN覆蓋控制中[1-2]。文獻(xiàn)[3]將遺傳算法應(yīng)用到WSN的覆蓋控制中,取得了優(yōu)化,但是算法較復(fù)雜,收斂速度較慢。文獻(xiàn)[4]中提出了一種基于外推人工蜂群算法的WSN部署優(yōu)化方法,雖然收斂較快,但是與其他算法相比，在覆蓋率的提升上沒有明顯優(yōu)勢(shì)。粒子群算法由于具有控制參數(shù)少、收斂速度快、易于實(shí)現(xiàn)等特點(diǎn),被廣泛應(yīng)用于WSN覆蓋優(yōu)化中[5-6]。文獻(xiàn)[7]中提出了一種基于改進(jìn)的粒子群算法,引入了種子雜交策略,取得較好效果,比遺傳算法更容易實(shí)現(xiàn)。文獻(xiàn)[8]中提出了一種基于混沌粒子群的WSN覆蓋優(yōu)化算法,比標(biāo)準(zhǔn)粒子群有更好的全局搜索能力,不過到搜索后期粒子以大概率進(jìn)行混沌擾動(dòng)不利于精細(xì)化搜索,計(jì)算復(fù)雜度有較大幅度增加。文獻(xiàn)[9]將進(jìn)化因子和聚合因子引入粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法中的慣性權(quán)重系數(shù)中,并采取碰撞回彈策略保證粒子群的多樣性,對(duì)WSN覆蓋優(yōu)化效果較明顯。文獻(xiàn)[10]將混沌量子粒子群算法應(yīng)用于WSN覆蓋優(yōu)化中,提出了精英個(gè)體適應(yīng)值方差早熟判斷機(jī)制,提高了WSN的覆蓋率,但是該早熟判斷機(jī)制存在局限性,不能完全反映粒子的聚集情況。

為了提高WSN的覆蓋性能,針對(duì)傳統(tǒng)粒子群算法的不足,本文從種群多樣性的角度出發(fā),將種群分布熵和平均粒距兩個(gè)多樣性評(píng)價(jià)指標(biāo)引入量子粒子群算法的優(yōu)化過程中,提出了一種基于動(dòng)態(tài)自適應(yīng)混沌量子粒子群(Dynamic Self-Adaptive Chaotic Quantum-behaved PSO, DACQPSO)的WSN覆蓋優(yōu)化算法。最后通過仿真實(shí)驗(yàn)驗(yàn)證了算法的性能。

1 WSN覆蓋優(yōu)化數(shù)學(xué)模型

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

本文選取了文獻(xiàn)[7]中的概率感知模型來計(jì)算WSN的覆蓋率。WSN中傳感器節(jié)點(diǎn)si對(duì)目標(biāo)點(diǎn)g的感知概率為:

(1)

其中:d(si,g)為傳感器節(jié)點(diǎn)si與目標(biāo)點(diǎn)g之間的歐幾里得距離;re(0

1.2 覆蓋評(píng)價(jià)指標(biāo)

為了考察各種WSN部署的優(yōu)劣性,選取6種常見的指標(biāo)對(duì)覆蓋控制算法作出科學(xué)的評(píng)估,以便對(duì)覆蓋算法作對(duì)比分析。

1)覆蓋率。

為了便于計(jì)算,將面積為m×n的矩形區(qū)域A均勻劃分為m×n個(gè)單位面積的網(wǎng)格,并將其簡(jiǎn)化成像素點(diǎn)。監(jiān)測(cè)區(qū)域內(nèi)的所有傳感器節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)g的聯(lián)合檢測(cè)概率為:

(2)

其中:sall表示W(wǎng)SN中所有檢測(cè)目標(biāo)點(diǎn)g的傳感器節(jié)點(diǎn)的集合。點(diǎn)g能被有效檢測(cè)到的條件為:

Pr(sall,g)≥Prth

(3)

其中：Prth為檢測(cè)概率閾值。節(jié)點(diǎn)集S對(duì)監(jiān)測(cè)區(qū)域的覆蓋率Rarea(S)為節(jié)點(diǎn)集的覆蓋面積與監(jiān)測(cè)區(qū)域的總面積的比值[11],即滿足式(3)的單元網(wǎng)格數(shù)量和與監(jiān)測(cè)區(qū)域總的單元網(wǎng)格數(shù)量之比。

(4)

2)均勻度。

均勻度反映節(jié)點(diǎn)分布的均勻程度,計(jì)算公式如下:

(5)

其中：n為節(jié)點(diǎn)總數(shù);ki為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù);Di, j為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的歐幾里得距離;Mi為節(jié)點(diǎn)i與其所有鄰居節(jié)點(diǎn)之間距離的平均值。覆蓋均勻度越小網(wǎng)絡(luò)覆蓋質(zhì)量越好。

另外還選取覆蓋效率[12-13]、平均移動(dòng)距離、最優(yōu)迭代次數(shù)和算法耗時(shí)4個(gè)指標(biāo),限于篇幅不作具體介紹。

2 量子粒子群優(yōu)化算法

粒子群優(yōu)化(PSO)算法[14]擁有進(jìn)化計(jì)算和群體智能等特點(diǎn),但它不能保證收斂到全局最優(yōu)甚至局部最優(yōu)[15],盡管對(duì)PSO算法作了眾多改進(jìn)[16-20],實(shí)際上改進(jìn)的效果有限。

國(guó)內(nèi)江南大學(xué)的孫俊等[21-22]根據(jù)量子力學(xué)理論,建立δ勢(shì)阱勢(shì)能場(chǎng)模型,于2004年提出了量子行為粒子群優(yōu)化(Quantum-Behaved PSO, QPSO)算法,之后量子粒子群優(yōu)化算法得到了廣泛的研究與應(yīng)用。

PSO算法在進(jìn)化過程中始終維持兩個(gè)最優(yōu)位置:1)粒子i(i=1,2,…,M,M為種群規(guī)模)的個(gè)體最好位置pbesti(t),表示為Pi(t)=[Pi,1(t),Pi,2(t),…,Pi,N(t)]T(N為問題維度)。2)種群全局最好位置gbest(t),表示為Pg(t)=[Pg,1(t),Pg,2(t),…,Pg,N(t)]T。若優(yōu)化模型為maxf(x),f(x)為適應(yīng)度函數(shù)。其更新公式為:

(6)

(7)

Clerc[16]分析PSO算法的收斂性時(shí)發(fā)現(xiàn),粒子i以pbest和gbest之間的隨機(jī)點(diǎn)Qi(t)=[Qi,1(t),Qi,2(t),…,Qi,N(t)]T為吸引子,其坐標(biāo)為:

Qi, j(t)=φi, j(t)·Pi, j(t)+[1-φi, j(t)]·Pg, j(t)

(8)

其中:φi, j(t)～U(0,1),1≤j≤N。

量子粒子群算法以點(diǎn)Qi(t)為吸引勢(shì),建立δ勢(shì)阱場(chǎng)來構(gòu)筑粒子的量子束縛態(tài),使得群體具有聚集態(tài)。通過解粒子在δ勢(shì)阱中運(yùn)動(dòng)的定態(tài)Schr?dinger方程得到波函數(shù)，再通過逆變換法得到粒子位置的更新方程[23]為:

Xi, j(t+1)=

(9)

其中：引入了平均最好位置mbest(t)記為C(t),是所有粒子各個(gè)最好位置gbest(t)的平均值,即

(10)

其中：α稱為收縮擴(kuò)張系數(shù)(Contraction-Expansion coefficient, CE coefficient)。QPSO算法可以收斂到全局最優(yōu)解[24],是全局收斂的隨機(jī)搜索算法。

3 混沌搜索

混沌系統(tǒng)具有隨機(jī)性、遍歷性和初值敏感性的特性,可以將其應(yīng)用到隨機(jī)搜索中。

混沌映射方程很多,文獻(xiàn)[9,25-26]用的是經(jīng)典的Logistic混沌方程,其迭代公式為:

Zn+1=μZn(1-Zn);n=1,2,…;μ∈(0,4]

(11)

Tent混沌映射的混沌方程為：

(12)

對(duì)單個(gè)Z0(Z0不取混沌方程的平衡點(diǎn)),μ取4,用Tent映射和Logistic映射分別迭代5 000次,得到兩種混沌映射的遍歷性分析如圖1所示。從圖1可看出:Logistic混沌映射產(chǎn)生的變量軌道點(diǎn)分布不均,落在區(qū)間[0,0.1]和[0.9,1]上的變量數(shù)量遠(yuǎn)遠(yuǎn)多于平均值，而Tent映射的混沌變量分布較為均勻,在平均值附近波動(dòng),沒有較大落差；另外,多條混沌軌道的混沌遍歷性要優(yōu)于單條混沌軌道[27]。因此,本文采用遍歷性更好的Tent混沌映射作為混沌變量發(fā)生器,并使用多條混沌軌道進(jìn)行混沌搜索。

圖1 混沌映射遍歷性分析

4 多樣性測(cè)度

4.1 種群熵

信息論中,Shannon引入了信息熵的概念來度量離散事件的不確定度。本文受文獻(xiàn)[28]啟發(fā),度量多樣性的種群熵描述如下:

1)設(shè)種群粒子集合為X={X1,X2,…,XM},粒子i表示成向量形式Xi=(Xi,1,Xi,2,…,Xi,N)T,其中：M為種群規(guī)模;N為問題維數(shù)。假定問題解空間的最大對(duì)角線的方向向量為V,長(zhǎng)度為L(zhǎng)。

2)計(jì)算每個(gè)粒子在V上的投影,即向量作內(nèi)積Bi=VTXi(i=1,2,…,M),得到M個(gè)投影的值。

4)按照香農(nóng)信源熵的定義計(jì)算在第t次迭代的種群分布熵:

(13)

需要注意的是:這種定義下的種群分布熵在粒子分布絕對(duì)均勻時(shí)達(dá)不到理論上的最大值lnM。原因是即使粒子在解空間內(nèi)均勻分布,但是此時(shí)解空間是一個(gè)N維的方體,向方體對(duì)角線方向向量作投影后落在等長(zhǎng)度區(qū)間內(nèi)的粒子數(shù)并不是均勻的,一般與空間的大小成正比。所以在種群隨機(jī)初始化時(shí),種群分布熵一般達(dá)不到lnM。

4.2 平均粒距

平均粒距表達(dá)了種群各粒子之間分布的離散程度[26]。設(shè)解空間的最大對(duì)角線長(zhǎng)度為L(zhǎng),M和N分別是種群規(guī)模和問題維數(shù),則第t次迭代種群的平均粒距的計(jì)算公式如式(14)所示:

(14)

其中：

Xi, j(t)為粒子i的第j維坐標(biāo)。平均粒距獨(dú)立于種群規(guī)模和問題維數(shù),D(t)的值越大,各粒子較分散,種群多樣性較好;D(t)的值越小,粒子分布較集中,種群多樣性較差。

5 動(dòng)態(tài)自適應(yīng)混沌量子粒子群優(yōu)化算法

通常,種群多樣性越好,算法全局探索能力越強(qiáng),但算法的局部搜索能力較弱。反之亦然。近年來已經(jīng)有學(xué)者從種群多樣性的角度來動(dòng)態(tài)調(diào)整粒子群算法的搜索過程,文獻(xiàn)[27]通過平均粒距來調(diào)整PSO算法的慣性權(quán)重w,在搜索過程中動(dòng)態(tài)調(diào)整搜索方向提高了算法性能;但是只通過平均粒距來控制算法是有缺陷的,例如當(dāng)遇到類似多峰問題時(shí)雖然平均粒距的值很小,但是粒子的多樣性卻很差。文獻(xiàn)[20]根據(jù)多樣性評(píng)價(jià)值,對(duì)慣性權(quán)重w動(dòng)態(tài)控制,提出了基于反饋的自適應(yīng)粒子群優(yōu)化算法(Adoptive PSO algorithm based on feedback mechanism, APSO),具有較好的尋優(yōu)能力和搜索速度。針對(duì)QPSO算法,從種群多樣性的角度提出了一種基于種群分布熵的CE系數(shù)α的自適應(yīng)調(diào)整策略,并結(jié)合粒子分散程度,利用對(duì)平均粒距的評(píng)價(jià)在算法后期進(jìn)行混沌搜索,即一種動(dòng)態(tài)自適應(yīng)混沌量子粒子群算法DACQPSO,并將DACQPSO算法應(yīng)用到WSN覆蓋優(yōu)化中。

5.1 收縮擴(kuò)張系數(shù)α的自適應(yīng)控制

在量子粒子群優(yōu)化算法QPSO中,一般認(rèn)為收斂性受CE系數(shù)α的取值影響。α取較大值時(shí),算法具有較強(qiáng)的全局探索(exploration)能力,有利于跳出局部極值;α取較小值時(shí),算法具有較強(qiáng)的局部開發(fā)(exploitation)能力,有利于精細(xì)化搜索。對(duì)于QPSO算法而言,算法收斂到全局最優(yōu)的充分必要條件是α<1.781[29]。對(duì)CE系數(shù)α的設(shè)置通常采用線性遞減(Linear-Descending, LD)策略,其表達(dá)式為:

(15)

其中:MAXTER為最大迭代次數(shù);αmax和αmin為CE系數(shù)的迭代初始值和終止值。α從1.0線性減小到0.5一般都能取得比較好的效果。

CE系數(shù)α采用LD策略可以使得QPSO算法實(shí)現(xiàn)從廣泛探索到精細(xì)搜索的動(dòng)態(tài)演化,完成對(duì)算法的控制,實(shí)驗(yàn)結(jié)果表明α的這種設(shè)定策略具有普遍的指導(dǎo)性。雖然將α與迭代次數(shù)t建立強(qiáng)線性關(guān)系可以取得較好的效果,但是,群體內(nèi)粒子的進(jìn)化狀態(tài)與迭代次數(shù)t之間并不是這種直接的函數(shù)關(guān)系。由于粒子位置的更新具有隨機(jī)性,相鄰的兩代種群可能差異很大,此時(shí)需要跳躍性地控制進(jìn)化趨勢(shì)才能避免種群極速跌入局部極值以致失去進(jìn)化的動(dòng)力。而相鄰兩次迭代的α的變化量Δα=(αmax-αmin)/MAXTER很小,不足以應(yīng)付種群進(jìn)化狀態(tài)的劇烈變化。LD策略沒有感知群體內(nèi)各粒子進(jìn)化態(tài)勢(shì)信息的能力,不能充分發(fā)揮QPSO算法的潛在性能。經(jīng)過之前的分析容易知道,種群的多樣性可以在一定程度上描述群體內(nèi)粒子的進(jìn)化狀態(tài),因此,本文從種群多樣性的角度出發(fā),以種群分布熵作為多樣性評(píng)價(jià)指標(biāo),考察研究通過種群多樣性的變化來動(dòng)態(tài)調(diào)整CE系數(shù)α的策略。

由于Sigmoid函數(shù)在線性與非線性之間具有極好的平衡性[30],將種群分布熵引入Sigmoid函數(shù)用于控制CE系數(shù)α,如式(16)所示:

(16)

當(dāng)kx<-9.903 438時(shí),s(x)趨向于0;kx≥9.903 438時(shí),s(x)趨向于1。DACQPSO算法的CE系數(shù)α定義如下:

(17)

(18)

5.2 DACQPSO算法的混沌搜索機(jī)制

一般在粒子群算法在搜索后期,各粒子要么已經(jīng)聚集在局部極值點(diǎn)要么聚集在全局極值點(diǎn)。DACQPSO算法由于在前期已經(jīng)采用了自適應(yīng)搜索,在搜索后期,粒子以很大的概率聚集到了全局極值點(diǎn)的鄰域內(nèi)。DACQPSO算法的混沌搜索思想為:算法按照式(17)定義的α(t)控制種群進(jìn)化,完成粒子更新的基本操作,當(dāng)種群平均粒距D(t)達(dá)到混沌搜索閾值c(c為一給定閾值,由具體問題測(cè)試確定)時(shí),進(jìn)行混沌搜索,實(shí)現(xiàn)混沌擾動(dòng)。具體描述如下:隨機(jī)產(chǎn)生一個(gè)N維的向量Z0(t)=(Z0,1(t),Z0,2(t),…,Z0,N(t))T,其中,Z0, j(t)～U(0,1),j=1,2,…,N。以Z0(t)為初始值,每一維用Tent混沌方程式(12)分別迭代h次,產(chǎn)生N條混沌軌道,得到h個(gè)N維的混沌向量并構(gòu)成一個(gè)混沌群,記作Ch。Ch群中第i個(gè)粒子表示為Zi(t)=[Zi,1(t),Zi,2(t),…,Zi,N(t)]T,i=1,2,…,h。根據(jù)式(19)、 (20)得到h個(gè)向量,這h個(gè)向量就是問題的h個(gè)解向量。

Yi(t)=gbest(t)±Ri(t)·Zi(t);i=1,2,…,h

(19)

Ri(t)=γRi-1(t);i=1,2,…,h;R1=R;0<γ≤1

(20)

由式(19)～(20)可以看出,混沌搜索的范圍可以覆蓋以gbest為中心、R為半徑的鄰域空間,并且可以由收縮因子γ控制搜索精度。在這h個(gè)解向量中確定最優(yōu)的解向量,記為cbest(t)。按照式(21)和(22)更新pbestl(t+1)和gbest(t+1)。

pbestl(t+1)=

gbest(t+1)=

5.3 算法流程

DACQPSO算法具體流程描述如下:

1)設(shè)置種群規(guī)模M、問題維數(shù)N、混沌搜索閾值c、混沌迭代次數(shù)h和收縮因子γ等參數(shù)的初始值;隨機(jī)初始化種群各粒子,并計(jì)算每個(gè)粒子的個(gè)體最優(yōu)pbest(t)和全局最優(yōu)gbest(t)。

2)按式(13)計(jì)算本次迭代的種群分布熵E(t),并根據(jù)式(17)計(jì)算CE系數(shù)α(t)。

3)根據(jù)式(10)計(jì)算平均最好位置mbest(t)。并根據(jù)式(8)～(9)更新粒子i的吸引子Qi(t)和粒子位置Xi(t+1)。

4)計(jì)算各粒子的適應(yīng)度,根據(jù)式(6)和(7)更新各粒子的個(gè)體最優(yōu)pbest(t+1)和全局最優(yōu)gbest(t+1)。

5)根據(jù)式(14)計(jì)算本次迭代的種群平均粒距D(t),若D(t)≤c,則轉(zhuǎn)入6)進(jìn)行混沌搜索;否則轉(zhuǎn)入7)。

7)若未達(dá)到終止條件則返回2);否則,算法結(jié)束。

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

6.1 仿真環(huán)境與參數(shù)設(shè)置

假設(shè)監(jiān)測(cè)區(qū)域?yàn)?0 m×20 m的平面,將該區(qū)域離散化成20×20個(gè)像素點(diǎn)。在該區(qū)域內(nèi)部署24個(gè)同構(gòu)的傳感器節(jié)點(diǎn)。所有節(jié)點(diǎn)的感知半徑Rs=2.5 m,通信半徑Rc=2Rs=5 m[31]。節(jié)點(diǎn)概率感知模型式(1)中的參數(shù)λ1=1,λ2=0,β1=1,β2=1.5,re=1.25 m,Prth=0.6。算法最大迭代次數(shù)MAXTER=150。設(shè)置式(17)中的αmax=0.95,αmin=0.4?；煦绲螖?shù)h=50,混沌搜索最大半徑R=5;收縮因子k=0.85。種群規(guī)模M=15,粒子表示為Xi=(xi,1,yi,1,xi,2,yi,2,…,xi,24,yi,24)T,i=1,2,…,15,其分量xi, j、yi, j表示傳感器節(jié)點(diǎn)i的位置坐標(biāo)。由于解空間是個(gè)48維的方體,經(jīng)前期大量數(shù)據(jù)測(cè)試,種群隨機(jī)初始化的種群分布熵取其均值,lnM=0.935。同時(shí)受MAXTER的影響將式(18)更新為:

(23)

使用主頻3.2 GHz的主機(jī),Windows 7旗艦版操作系統(tǒng),在Matlab 2015b環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。

6.2 參數(shù)設(shè)置對(duì)算法性能的影響分析

DACQPSO算法中最重要的參數(shù)就是CE系數(shù)α和混沌搜索閾值。而混沌搜索閾值受問題規(guī)模、適應(yīng)度函數(shù)和問題類型等眾多因素的影響,混沌搜索閾值的選取是一個(gè)不確定優(yōu)化問題,由具體問題給定,不是本文的研究重點(diǎn)。本節(jié)將研究DACQPSO算法在不同參數(shù)設(shè)置下的性能，并作對(duì)比分析。

為了驗(yàn)證CE系數(shù)α對(duì)算法的影響,將α分別取固定值從1～0.1，以式(4)定義的網(wǎng)絡(luò)覆蓋率為適應(yīng)度函數(shù)f,分別在每個(gè)固定的α下對(duì)目標(biāo)問題進(jìn)行10次優(yōu)化,每次優(yōu)化迭代100次,結(jié)果如表1所示。為了考察不同的α值對(duì)算法性能的影響是否有顯著的差異,對(duì)目標(biāo)函數(shù)在不同α水平下的結(jié)果作單因素方差分析,結(jié)果如表2所示。

表1 不同CE系數(shù) α 值下網(wǎng)絡(luò)覆蓋率的優(yōu)化結(jié)果

表2 單因素方程分析

圖2 兩種算法在各混沌閾值c下的網(wǎng)絡(luò)覆蓋率對(duì)比

表2中：SS為離差平方和，df為自由度，MS為均方，F(xiàn)為F值，P-value為F分布的概率，F(xiàn)-crit為F的臨界值。由于F=33.812>F-crit=1.985 6,故在顯著性水平0.05條件下認(rèn)為不同的α值對(duì)算法性能的影響存在顯著的差異。方差分析的結(jié)果表明:CE系數(shù)α的取值對(duì)QPSO算法的性能有很大的影響,在算法執(zhí)行過程中合理地調(diào)整α對(duì)提高算法性能意義重大。

為了研究混沌量子粒子群CQPSO算法和DACQPSO算法在不同的混沌搜索閾值下對(duì)目標(biāo)問題的優(yōu)化性能,設(shè)置不同的c值,分別在每個(gè)c下對(duì)目標(biāo)問題進(jìn)行10次優(yōu)化,每次優(yōu)化的最大迭代次數(shù)為150,結(jié)果如表3所示。為了全面考察閾值的影響,除覆蓋率外還增加了均勻度、覆蓋效率、平均移動(dòng)距離、最優(yōu)迭代次數(shù)、計(jì)算耗時(shí)5個(gè)指標(biāo)。表3中的數(shù)據(jù)為優(yōu)化結(jié)果的平均。

從表3可以看出,混沌搜索閾值對(duì)CQPSO算法和DACQPSO算法的優(yōu)化性能都有影響。從整體上看,在每個(gè)實(shí)驗(yàn)選取的c值下,DACQPSO算法在除算法耗時(shí)以外的所有指標(biāo)上都要優(yōu)于CQPSO算法。圖2顯示了在不同混沌搜索閾值下CQPSO算法和DACQPSO算法的優(yōu)化結(jié)果在覆蓋率指標(biāo)上的情況。從圖2可以看出兩種算法當(dāng)c值在取0.005 5附近時(shí)算法能發(fā)揮最佳性能。c值過小,種群粒子過分聚集混沌搜索只能完成精細(xì)搜索,很難跳出目前的極值;c值過大,混沌擾動(dòng)對(duì)量子粒子群內(nèi)在尋優(yōu)機(jī)制產(chǎn)生較大干擾,不利于全局搜索且大幅增加了計(jì)算消耗。因此,本文實(shí)驗(yàn)中的混沌搜索閾值c取0.005 5。

6.3 實(shí)驗(yàn)結(jié)果與分析

圖3 不同算法優(yōu)化后的節(jié)點(diǎn)分布

算法閾值c覆蓋率/%均勻度覆蓋效率/%平均移動(dòng)距離/m最優(yōu)迭代次數(shù)耗時(shí)/sCQPSODACQPSO0.001584.90000.550672.06549.7973144.7000564.88900.002584.42500.556971.66229.6788143.4000562.30580.003583.65000.545971.00439.8999145.3000629.68220.004585.22500.571272.34129.7401143.3000584.76300.005585.47500.501172.553410.1080144.4000639.76310.006582.32500.582369.87969.9210145.6000596.14610.007585.50000.541272.57479.9552141.7000619.36470.008584.45000.568771.68349.7212147.1000572.68600.001585.57500.523172.63839.5805127.9000836.27440.002585.97500.530372.97789.7303127.7000842.22090.003585.15000.521072.27769.5648120.1000957.34080.004585.47500.537172.55349.4789125.7000890.53120.005586.30000.567873.25379.6779125.2000915.40010.006584.80000.550471.98059.6891121.2000860.22180.007586.00000.512972.99919.6918122.7000784.95240.008585.77500.531672.80819.7739122.5000938.5698

為了驗(yàn)證DACQPSO算法的性能,選取了標(biāo)準(zhǔn)粒子群算法SPSO、量子粒子群算法QPSO、混沌量子粒子群算法CQPSO與DACQPSO算法作對(duì)比實(shí)驗(yàn)。圖3為經(jīng)過不同算法迭代150次優(yōu)化后傳感器節(jié)點(diǎn)的分布情況?？梢钥闯?SPSO算法優(yōu)化效果較差,經(jīng)過DACQPSO優(yōu)化后的節(jié)點(diǎn)分布更為均勻,WSN的覆蓋范圍更大。圖3中:“+”表示傳感器節(jié)點(diǎn)位置;圓圈表示節(jié)點(diǎn)感知半徑Rs;“—”連接的節(jié)點(diǎn)構(gòu)成的集合構(gòu)成一個(gè)最小生成樹,以保持WSN的連通性。這四種算法的尋優(yōu)收斂曲線如圖4所示。其中,SPSO、QPSO、CQPSO和DACQPSO算法優(yōu)化后的網(wǎng)絡(luò)覆蓋率分別為81%、83%、86.25%和88%。在WSN網(wǎng)絡(luò)覆蓋率優(yōu)化上,DACQPSO算法相對(duì)于其他算法分別提高了7、5和1.75個(gè)百分點(diǎn)。

為了全面地評(píng)價(jià)算法的性能,對(duì)四種算法分別進(jìn)行20次WSN覆蓋優(yōu)化,每次優(yōu)化算法迭代150次。各覆蓋評(píng)價(jià)指標(biāo)數(shù)據(jù)取平均值,如表4所示。

分析表4數(shù)據(jù)可以得出:在WSN覆蓋優(yōu)化最重要的性能評(píng)價(jià)指標(biāo)網(wǎng)絡(luò)覆蓋率上,DACQPSO算法優(yōu)勢(shì)明顯,相對(duì)于其他三種算法,將網(wǎng)絡(luò)覆蓋率分別提高了2.825、2.25和1.625個(gè)百分點(diǎn)。傳感器節(jié)點(diǎn)的覆蓋效率也最高,比其他算法分別提高了2.397 9、1.909 8和1.379 3個(gè)百分點(diǎn),提高了節(jié)點(diǎn)的利用率。在最優(yōu)迭代次數(shù)指標(biāo)上,比其他算法分別提前了30.6、39.6和38.0次,說明算法收斂更快。在均勻度和最優(yōu)平均距離兩個(gè)指標(biāo)上四種算法大致相當(dāng),無明顯優(yōu)勢(shì)。在算法耗時(shí)指標(biāo)上,DACQPSO算法的耗時(shí)幾乎是其他三種算法的2倍。這是因?yàn)镈ACQPSO算法需要計(jì)算種群分布熵和平均粒距這兩個(gè)種群多樣性指標(biāo),增加了計(jì)算消耗。隨著軟硬件水平的發(fā)展,算法耗時(shí)問題可以得到解決。

表4 四種算法優(yōu)化效果對(duì)比

圖4 四種對(duì)比算法的收斂曲線

7 結(jié)語

通過研究種群多樣性與粒子群算法進(jìn)化的關(guān)系,將種群分布熵和平均粒距兩個(gè)指標(biāo)引入混沌量子粒子群優(yōu)化算法中,提出了一種動(dòng)態(tài)自適應(yīng)的混沌量子粒子群優(yōu)化算法——DACQPSO,該算法通過種群多樣性的變化感知種群的進(jìn)化態(tài)勢(shì),動(dòng)態(tài)自適應(yīng)地控制算法的優(yōu)化進(jìn)程,實(shí)現(xiàn)了全局搜索與局部搜索的平衡,具有較強(qiáng)的自適應(yīng)能力。將算法應(yīng)用于WSN的覆蓋優(yōu)化中,仿真實(shí)驗(yàn)結(jié)果表明,DACQPSO算法提高了WSN的覆蓋率和覆蓋效率,提高了收斂速度,是一種有效的WSN覆蓋優(yōu)化算法。

如果找到一種理想的種群分布熵的計(jì)算模型,可以度量任意維度空間內(nèi)粒子分布的均勻性,那么DACQPSO的適應(yīng)性將會(huì)更加出色。

參考文獻(xiàn)(References)

[1] YOON Y, KIM Y-H. An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks [J]. IEEE Transactions on Cybernetics, 2013, 43(5): 1473-1483.

[2] AKBARZADEH V, GAGNE C, PARIZEAU M, et al. Probabilistic sensing model for sensor placement optimization based on line-of-sight coverage [J]. IEEE Transactions on Instrumentation and Measurement, 2013, 62(2): 293-303.

[3] 賈杰,陳劍, 常桂然, 等. 無線傳感器網(wǎng)絡(luò)中基于遺傳算法的優(yōu)化覆蓋機(jī)制[J]. 控制與決策, 2007, 22(11): 1289-1292.(JIA J, CHEN J, CHANG G R, et al. Optimal coverage scheme based on genetic algorithm in wireless sensor networks [J]. Control and Decision, 2007, 22(11): 1289-1292.)

[4] 于文杰, 李迅波, 羊行, 等. 外推人工蜂群算法在WSN部署優(yōu)化中的應(yīng)用研究[J]. 儀表技術(shù)與傳感器, 2017(6): 158-160.(YU W J, LI X B, YANG H, et al. Extrapolation artificial bee colony algorithm research on deployment optimization in wireless sensor network [J]. Instrument Technique and Sensor, 2017(6): 158-160.)

[5] KUNDU R, DAS S, MUKHERJEE R, et al. An improved particle swarm optimizer with difference mean based perturbation [J]. Neurocomputing, 2014, 129(129): 315-333.

[6] WANG X, WANG S, MA J J. An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment [J]. Sensors, 2007, 7(3): 354-370.

[7] 馮琳, 冉曉旻, 梅關(guān)林. 基于改進(jìn)粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 太赫茲科學(xué)與電子信息學(xué)報(bào), 2015, 13(3): 486-490.(FENG L, RAN X M, MEI G L. WSN coverage optimization by improved artificial PSO algorithm [J]. Journal of Terahertz Science and Electronic Information Technology, 2015, 13(3): 486-490.)

[8] 劉維亭, 范洲遠(yuǎn). 基于混沌粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(2): 338-340.(LIU W T, FAN Z Y. Coverage optimization of wireless sensor networks based on chaos particle swarm algorithm [J]. Journal of Computer Applications, 2011, 31(2): 338-340.)

[9] 吳意樂, 何慶, 徐同偉. 改進(jìn)自適應(yīng)粒子群算法在WSN覆蓋優(yōu)化中的應(yīng)用[J]. 傳感技術(shù)學(xué)報(bào), 2016, 29(4): 559-565.(WU Y L, HE Q, XU T W. Application of improved adaptive particle swarm optimization algorithm in WSN coverage optimization [J]. Chinese Journal of Sensors and Actuators, 2016, 29(4): 559-565.)

[10] 王偉, 朱娟娟, 萬家山, 等. 基于混沌量子粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 傳感技術(shù)學(xué)報(bào), 2016, 29(2): 290-296.(WANG W. ZHU J J, WAN J S, et al. Coverage optimization of wireless sensor networks based on chaotic quantum-behaved particle swarm algorithm [J]. Chinese Journal of Sensors and Actuators, 2016, 29(2): 290-296.)

[11] 張娟. 基于粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)節(jié)能覆蓋研究[D]. 上海: 華東理工大學(xué), 2014: 9-10.(ZHANG J. Energy saving coverage control study of wireless sensor networks based on particle swarm optimization algorithm [D]. Shanghai: East China University of Science and Technology, 2014: 9-10.)

[12] 曹峰, 劉麗萍, 王智. 能量有效的無線傳感器網(wǎng)絡(luò)部署[J]. 信息與控制, 2006, 35(2): 147-153.(CAO F, LIU L P, WANG Z. A new energy-efficient WSN deployment algorithm [J]. Information and Control, 2006, 35(2): 147-153.)

[13] 林祝亮. 基于粒子群算法的無線傳感網(wǎng)絡(luò)覆蓋問題優(yōu)化策略研究[D]. 杭州: 浙江工業(yè)大學(xué), 2009: 14-16.(LIN Z L. Coverage optimization strategy of wireless sensor networks based on particle swarm optimization [D]. Hangzhou: Zhejiang University of Technology, 2009: 14-16.)

[14] KENNEDY J, EBERHARR R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942-1948.

[15] BERGH F V D. An analysis of particle swarm optimizers [D]. Pretoria: University of Pretoria, 2001: 78-126.

[16] CLERC M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization [C]// Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 1999: 1951-1957.

[17] KENNEDY J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance [C]// Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ: IEEE, 1999: 1931-1938.

[18] LOVBJERG M, RASUSSEN T K, KRINK T. Hybrid particle swarm optimizer with breeding subpopulations [EB/OL]. [2017- 09- 20]. http: //pdfs.semanticscholar.org/1e4c/ddd9d4b89a9dbdf854aaf84b584ba47386ab.pdf.

[19] 劉宇, 覃征, 史哲文. 簡(jiǎn)約粒子群優(yōu)化算法[J]. 西安交通大學(xué)學(xué)報(bào), 2006, 40(8): 883-887.(LIU Y, QIN Z, SHI Z W. Compact particle swarm optimization algorithm [J]. Journal of Xi’An Jiaotong University, 2006, 40(8): 883-887.)

[20] 俞歡軍, 張麗平, 陳德釗, 等. 基于反饋策略的自適應(yīng)粒子群優(yōu)化算法[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2005, 39(9): 1286-1291.(YU H J, ZHANG L P, CHEN D Z, et al. Adaptive particle swarm optimization algorithm based on feedback mechanism [J]. Journal of Zhejiang University (Engineering Science), 2005, 39(9): 1286-1291.)

[21] SUN J, FENG B, XU W. Particle swarm optimization with particles having quantum behavior[C]// CEC 2004: Proceedings of the 2004 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2004: 325-331.

[22] 孫俊. 量子行為粒子群優(yōu)化算法研究[D]. 無錫: 江南大學(xué), 2009: 9-83.(SUN J. Particle swarm optimization with particle having quantum behavior [D]. Wuxi: Jiangnan University, 2009: 9-83.)

[23] SUN J, XU W, FENG B. A global search strategy of quantum-behaved particle swarm optimization [C]// Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems. Piscataway, NJ: IEEE, 2004: 111-116.

[24] 孫俊, 方偉, 吳小俊. 量子行為粒子群優(yōu)化: 原理及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2011: 9-68.(SUN J, FANG W, WU X J. Quantum behaved particle swarm optimization: principle and application [M]. Beijing: Tsinghua University Press, 2011: 9-68.)

[25] 高尚, 楊靜宇. 混沌粒子群優(yōu)化算法研究[J]. 模式識(shí)別與人工智能, 2006, 19(2): 266-270.(GAO S, YANG J Y. Research on chaos particle swarm optimization algorithm [J]. Pattern Recognition and Artificial Intelligence, 2006, 19(2): 266-270.)

[26] 劉軍民, 高岳林. 混沌粒子群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(2): 322-325.(LIU J M, GAO Y L. Chaos particle swarm optimization algorithm [J]. Journal of Computer Applications, 2008, 28(2): 322-325.)

[27] 陳如清, 俞金壽. 混沌粒子群混合優(yōu)化算法的研究與應(yīng)用[J]. 系統(tǒng)仿真學(xué)報(bào), 2008, 20(3): 685-688.(CHEN R Q, YU J S. Study and application of chaos-particle swarm optimization-based hybrid optimization algorithm [J]. Journal of System Simulation, 2008, 20(3): 685-688.)

[28] 湯可宗, 吳雋, 趙嘉. 基于多樣性反饋的自適應(yīng)粒子群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(12): 3372-3374.(TANG K Z, WU J, ZHAO J. Adaptive particle swarm optimization algorithm based on diversity feedback [J]. Journal of Computer Applications, 2013, 33(12): 3372-3374.)

[29] SUN J, WEI F, WU X, et al. Quantum-behaved particle swarm optimization: analysis of individual particle behavior and parameter selection [J]. Evolutionary Computation, 2012, 20(3): 349-393.

[30] 王玉冰, 王錦江, 王穎龍. 一種基于種群熵的自適應(yīng)遺傳算法[J]. 微計(jì)算機(jī)信息, 2010, 26(1): 32-34.(WANG Y B, WANG J J, WANG Y L. An colony entropy-based adaptive genetic algorithm [J]. Microcomputer Information, 2010, 26(1): 32-34.)

[31] ZHANG H, HOU J. Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(2): 89-124.

This work is partially supported by the National Natural Science Foundation of China (61402013).