基于混沌量子粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化*

王　偉，朱娟娟，萬(wàn)家山，喬　焰，李　旸*

（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)室，合肥230036；3.安徽工程大學(xué)機(jī)電學(xué)院，安徽蕪湖241000）

?

基于混沌量子粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化*

王偉1，2，朱娟娟1，2，萬(wàn)家山3，喬焰1，2，李旸1，2*

（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)室，合肥230036；3.安徽工程大學(xué)機(jī)電學(xué)院，安徽蕪湖241000）

摘要：針對(duì)傳統(tǒng)粒子群算法在求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題上存在的收斂速度慢、易陷入局部極值等缺陷，以提高傳感器網(wǎng)絡(luò)覆蓋率為主要優(yōu)化目標(biāo)，提出了基于量子粒子群和Logistic混沌映射相結(jié)合的優(yōu)化算法CQPSO。該算法基于量子δ勢(shì)阱模型，同時(shí)引入精英個(gè)體適應(yīng)值方差的早熟判斷機(jī)制，提高了搜索效率。仿真結(jié)果表明，對(duì)比基本粒子群、混沌粒子群以及量子粒子群三種算法，該算法在覆蓋率、均勻度以及平均移動(dòng)距離指標(biāo)方面具有更好的覆蓋優(yōu)化效果。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；混沌搜索；量子粒子群；覆蓋優(yōu)化

自溫總理提出“感知中國(guó)”以來(lái)，我國(guó)物聯(lián)網(wǎng)產(chǎn)業(yè)進(jìn)入健康快速的發(fā)展期。作為當(dāng)前物聯(lián)網(wǎng)領(lǐng)域的熱門(mén)研究方向，無(wú)線傳感器網(wǎng)絡(luò)［1］WSN（Wireless Sensor Networks）的研究與開(kāi)發(fā)也越來(lái)越得到重視。作為一種目標(biāo)區(qū)域監(jiān)測(cè)和信息獲取的重要技術(shù)，無(wú)線傳感器網(wǎng)絡(luò)在環(huán)境保護(hù)［2-3］、智慧醫(yī)療［4］、智能建筑、農(nóng)業(yè)物聯(lián)網(wǎng)［5］等諸多領(lǐng)域發(fā)揮著重大作用。

覆蓋率是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要的衡量指標(biāo)［6-7］，如何使用有限數(shù)量的傳感節(jié)點(diǎn)最大范圍的覆蓋目標(biāo)區(qū)域，同時(shí)盡可能的延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，一直是無(wú)線傳感器網(wǎng)絡(luò)研究的熱點(diǎn)。因此，傳感節(jié)點(diǎn)在待測(cè)區(qū)域的部署數(shù)量以及分布位置的合理性對(duì)于網(wǎng)絡(luò)服務(wù)質(zhì)量的影響顯得尤為重要。針對(duì)WSN覆蓋優(yōu)化問(wèn)題，群體智能算法［8］在這方面的研究越來(lái)越廣泛，國(guó)內(nèi)外學(xué)者們相繼提出了基于遺傳算法［9］、蟻群算法［10-11］、粒子群優(yōu)化算法［12］、人工蜂群算法［13］、人工魚(yú)群算法［14］、蛙跳算法［15］以及相關(guān)算法的改進(jìn)組合［16-17］等的WSN覆蓋優(yōu)化算法。這些算法均能夠有效提高覆蓋率，并使整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的分布更加均勻。但算法本身也存在著不足之處，均存在“早熟”收斂、局部最優(yōu)解［18］等問(wèn)題。

為了獲得更優(yōu)的傳感器節(jié)點(diǎn)覆蓋率，提高算法搜索效率，并克服標(biāo)準(zhǔn)粒子群算法群體智能程度低，協(xié)同搜索能力差［19］等缺陷，本文提出一種基于混沌量子粒子群CQPSO（Chaos Quantum-Behaved Particle Swarm Optimization）的WSN覆蓋優(yōu)化算法，通過(guò)覆蓋率、均勻度、平均移動(dòng)距離、耗時(shí)4個(gè)典型的傳感器網(wǎng)絡(luò)性能評(píng)價(jià)指標(biāo)，并同基本粒子群、混沌粒子群以及量子粒子群三種算法做對(duì)比仿真實(shí)驗(yàn)，對(duì)CQPSO算法的性能進(jìn)行驗(yàn)證。

1　相關(guān)工作

1.1無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問(wèn)題概述

本文中，傳感節(jié)點(diǎn)的感知模型采用混合感知模型［20］，相比于圓盤(pán)模型，該模型能較為客觀的反映現(xiàn)實(shí)網(wǎng)絡(luò)部署環(huán)境。假設(shè)監(jiān)測(cè)區(qū)域?yàn)橐粋€(gè)二維平面區(qū)域，各個(gè)傳感器節(jié)點(diǎn)可以部署在該區(qū)域內(nèi)的任意位置。設(shè)傳感器網(wǎng)絡(luò)中傳感節(jié)點(diǎn)si的坐標(biāo)為（xi，yi），監(jiān)測(cè)區(qū)域中任意點(diǎn)p（像素節(jié)點(diǎn)）的坐標(biāo)為（xp，yp），則節(jié)點(diǎn)si對(duì)目標(biāo)點(diǎn)p的監(jiān)測(cè)概率為：

式中：d(si,p)為傳感器節(jié)點(diǎn)si與目標(biāo)點(diǎn)p的歐氏距離；re(0＜re＜Rs)是傳感節(jié)點(diǎn)測(cè)量可靠性參數(shù)；α1=re-Rs+d(si,p)，α2=re+Rs-d(si,p)；λ1,λ2,β1,β2是與節(jié)點(diǎn)特性有關(guān)的測(cè)量參數(shù)。

整個(gè)監(jiān)測(cè)區(qū)域的傳感節(jié)點(diǎn)對(duì)目標(biāo)點(diǎn)p同時(shí)進(jìn)行檢測(cè)的聯(lián)合檢測(cè)概率為：

設(shè)無(wú)線傳感器目標(biāo)節(jié)點(diǎn)可以被檢測(cè)到的概率閾值為Cth，那么，傳感器目標(biāo)節(jié)點(diǎn)能被檢測(cè)到的限制條件為：

假設(shè)無(wú)線傳感器監(jiān)測(cè)區(qū)域?yàn)閙×n（m2）的矩形，將該待測(cè)區(qū)域劃分成大小相等、面積為1的m×n個(gè)相同網(wǎng)格，然后再將網(wǎng)格簡(jiǎn)化成為像素點(diǎn)，其離散精度為1。本研究中，WSN傳感器節(jié)點(diǎn)覆蓋率定義為滿足式（3）要求的網(wǎng)格數(shù)量與待測(cè)區(qū)域網(wǎng)格總數(shù)之比，即：

那么，覆蓋優(yōu)化問(wèn)題簡(jiǎn)述如下：

Step 1利用式（1）計(jì)算一個(gè)像素點(diǎn)對(duì)各個(gè)傳感節(jié)點(diǎn)的覆蓋率；

Step 2利用式（2）計(jì)算該像素點(diǎn)對(duì)各個(gè)傳感節(jié)點(diǎn)的聯(lián)合覆蓋率；

Step 3重復(fù)Step 1～Step 2，計(jì)算各個(gè)像素點(diǎn)對(duì)各個(gè)傳感節(jié)點(diǎn)的聯(lián)合覆蓋率；

Step 4利用式（3）～式（4）計(jì)算該監(jiān)測(cè)區(qū)域的區(qū)域覆蓋率，把式（4）作為覆蓋優(yōu)化算法的目標(biāo)函數(shù)f。

1.2量子粒子群算法描述

2004年，孫俊博士等從量子力學(xué)的角度出發(fā)提出了一種新的PSO（Particle Swarm Optimization，PSO）算法模型，該模型是以δ勢(shì)阱為基礎(chǔ)，認(rèn)為粒子具有量子的行為，并據(jù)此提出了量子粒子群算法［21］。在量子空間中粒子滿足聚集態(tài)的性質(zhì)完全不同，它可以在整個(gè)可行解空間中進(jìn)行搜索，因而QPSO（Quantum- behaved Particle Swarm Optimization）算法的全局搜索性能優(yōu)于標(biāo)準(zhǔn)PSO算法，且群體智能化程度高，協(xié)同搜索能力強(qiáng)［19］。

設(shè)搜索空間為j維，則基于δ勢(shì)阱模型的粒子位置更新公式如式（5）～式（8）所示：

QPSO算法詳細(xì)描述如下：

Initialize X；%初始化種群中每個(gè)粒子的位置向量

for t=1：t_max

belta=（1.0-0.5）*（t_max-t）/t_max+0.5 %收縮-擴(kuò)張系數(shù)β%從1.0到0.5線性遞減

mbest=mean（X）%計(jì)算平均最好位置

for i=1 to種群規(guī)模N

if f（Xi）＞f（Pi）then Pi=Xi%P保存?zhèn)€體最優(yōu)值

Pg=max（Pi）% Pg保存群體最優(yōu)值

for j=1 to粒子維度D

u=rand（0，1）v=rand（0，1）

p=u*Pid+（1-u）*Pg%局部吸引子坐標(biāo)公式

if v＞=0.5 %位置更新公式

Xid=p+β*abs（mbest-Xid）*ln（1/v）

else Xid=p-β*abs（mbest-Xid）*ln（1/v）

將更新后的粒子位置限制在搜索范圍中

直到達(dá)到終止條件

1.3Logistic混沌映射

混沌運(yùn)動(dòng)具有隨機(jī)性、規(guī)律性、遍歷性的特點(diǎn)，這些特性應(yīng)用到優(yōu)化搜索中將帶來(lái)很大的優(yōu)越性［22］?；煦绲碾S機(jī)性可以讓搜索形成負(fù)反饋，避免陷入局部最優(yōu)；規(guī)律性使得搜索有章可循，新解由確定的迭代方程式產(chǎn)生；遍歷性可以無(wú)重復(fù)的搜索整個(gè)可行解區(qū)域，提高算法的全局尋優(yōu)能力。本文使用典型的Logistic混沌映射，方程式如（9）所示：

式中：u為控制參量，N為混沌搜索次數(shù)，當(dāng)u=4，0≤Z0≤1，Logistic完全處于混沌狀態(tài)。

2　基于混沌量子粒子群的WSN網(wǎng)絡(luò)覆蓋優(yōu)化算法

2.1算法基本思想

為了解決粒子群算法在求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋問(wèn)題上存在的收斂速度慢、易陷入局部極值等問(wèn)題，本文基于量子粒子群的強(qiáng)全局收斂性和混沌運(yùn)動(dòng)的特性，提出了混沌量子粒子群的WSN網(wǎng)絡(luò)覆蓋優(yōu)化算法。該算法迭代尋優(yōu)過(guò)程中依據(jù)精英適應(yīng)值方差的早熟判斷機(jī)制，在當(dāng)前最優(yōu)解局部進(jìn)行精細(xì)化搜索，避免算法陷入局部極值而停滯，保證了粒子的種群多樣性。

2.2基于精英個(gè)體適應(yīng)值方差的早熟判斷機(jī)制

量子粒子群算法在迭代尋優(yōu)過(guò)程中，如果一些粒子暫時(shí)找到局部最優(yōu)解，則其他粒子通過(guò)局部吸引子式（6）迅速向其靠攏，導(dǎo)致整個(gè)算法易陷入局部最優(yōu)，即所謂的“早熟”收斂現(xiàn)象。當(dāng)種群發(fā)生早熟收斂，所有粒子聚集在一起時(shí)，算法要么陷入了局部最優(yōu)解，要么就是找到了全局最優(yōu)解。此時(shí)算法尋優(yōu)過(guò)程十分緩慢，降低搜索效率。為保持種群粒子的多樣性，文獻(xiàn)［23-25］提出了基于群體適應(yīng)值方差的早熟收斂判斷機(jī)制，較好的幫助粒子逃離局部最優(yōu)。然而，這種機(jī)制運(yùn)算量大、耗時(shí)多。為此，本文提出基于精英個(gè)體適應(yīng)度方差的早熟判斷機(jī)制，其理論依據(jù)在于：一個(gè)種群發(fā)生早熟收斂時(shí)，主要應(yīng)看這個(gè)種群中當(dāng)前適應(yīng)度暫時(shí)最大的那些個(gè)體是否有重復(fù)或相互趨同的現(xiàn)象。定義如下：

精英個(gè)體的適應(yīng)值方差設(shè)粒子種群數(shù)量為N，其第t代種群粒子的適應(yīng)度分別為f1(t),f2(t),…,fN(t)，種群個(gè)體的平均適應(yīng)度記為f_avg(t)，如式（10）所示。將粒子適應(yīng)度值大于平均適應(yīng)度的個(gè)體成為精英個(gè)體，假設(shè)有m個(gè)（m＜N），記全體精英個(gè)體的適應(yīng)度平均值為f_elite(t)，定義精英個(gè)體適應(yīng)值方差σ2(t)，計(jì)算方式如式（11）所示。

其中：F為歸一化因子，作用是限制σ2的大小。在本文中，F(xiàn)的取值如式（12）所示。

此處計(jì)算f_elite(t)與fi(t)之間的差值，而不是計(jì)算fi(t),i∈(1,N)與f_avg(t)之間的差值，主要是為避免適應(yīng)值差的個(gè)體對(duì)整個(gè)計(jì)算結(jié)果帶來(lái)的不利影響，最大程度的反映種群在搜索過(guò)程中的收斂情況。

2.3算法流程

①設(shè)置WSN傳感器節(jié)點(diǎn)的覆蓋模型參數(shù)，利用混沌算法產(chǎn)生初始化的傳感節(jié)點(diǎn)位置，并根據(jù)目標(biāo)函數(shù)計(jì)算對(duì)應(yīng)粒子的網(wǎng)絡(luò)覆蓋率；②初始化每個(gè)粒子的個(gè)體最優(yōu)Pbest和群體最優(yōu)Pg；③收縮擴(kuò)張系數(shù)β隨迭代次數(shù)從1.0到0.5線性減?。虎芨鶕?jù)式（8）計(jì)算種群的平均最好位置mbest，并利用式（5）更新每個(gè)粒子的位置，并根據(jù)目標(biāo)函數(shù)f計(jì)算每個(gè)粒子更新后的網(wǎng)絡(luò)覆蓋率；⑤將每個(gè)粒子更新位置后的覆蓋率與Pbest對(duì)應(yīng)的覆蓋率相比較，如果前者較大，則更新Pbest；⑥將種群中的每個(gè)粒子的個(gè)體最優(yōu)Pbest對(duì)應(yīng)的覆蓋率與Pg對(duì)應(yīng)的覆蓋率相比較，如果前者較大，則更新Pg；⑦根據(jù)式（11）計(jì)算種群適應(yīng)度的方差σ2，如果σ2＜C（C為判斷早熟收斂的停滯閾值，其值根據(jù)算法前期測(cè)試情況而定），則根據(jù)式（9）進(jìn)行N次（具體算法中取30）混沌搜索，得到最優(yōu)解向量Y和對(duì)應(yīng)的適應(yīng)值Ybest，若Ybest＞Pg則Pg=Ybest；⑧如果循環(huán)未達(dá)到預(yù)設(shè)最大迭代次數(shù)，則返回2）；否則算法結(jié)束，并返回群體最優(yōu)分布。

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

3.1仿真設(shè)置與平臺(tái)

根據(jù)1.1節(jié)覆蓋網(wǎng)絡(luò)模型，在20 m×20 m的平面監(jiān)測(cè)區(qū)域部署30個(gè)無(wú)線傳感器節(jié)點(diǎn)。所有節(jié)點(diǎn)感知半徑Rs=2.5 m，通信半徑Rc=2Rs=5 m。概率模型中，λ1=1，λ2=0，β1=1，β2=1.5，Cth=0.6，t_max=500，測(cè)量可靠性參數(shù)re=1.25 m，使用MATLAB 2010進(jìn)行實(shí)驗(yàn)仿真（算法使用元胞數(shù)組保存?zhèn)鞲泄?jié)點(diǎn)位置坐標(biāo)，每個(gè)粒子包含30個(gè)傳感節(jié)點(diǎn)位置坐標(biāo)）。

3.2停滯閾值C的影響

CQPSO算法的主要參數(shù)包括種群規(guī)模，收-擴(kuò)因子β以及停滯閾值C等。對(duì)收-擴(kuò)因子β進(jìn)行討論的文獻(xiàn)已有很多。因此，本節(jié)將重點(diǎn)研究停滯閾值C對(duì)算法搜索性能的影響。

種群數(shù)量取30，收-擴(kuò)因子β從1.0到0.5線性減少，停滯閾值C分別取0.002 5，0.003 0，0.003 5，0.004 0，0.004 5。對(duì)目標(biāo)函數(shù)f分別進(jìn)行10次優(yōu)化，函數(shù)的維度取30，迭代次數(shù)500，優(yōu)化結(jié)果見(jiàn)下表1。同時(shí)，為了更好的評(píng)估影響，除主要指標(biāo)覆蓋率外，引入最優(yōu)值迭代次數(shù)（算法尋得最優(yōu)值之前的迭代次數(shù)）、均勻度、平均移動(dòng)距離、耗時(shí)4個(gè)性能指標(biāo)。

表1　停滯閾值C對(duì)算法的影響

表1中：elite/all：elite表示基于精英個(gè)體適應(yīng)值方差的早熟判斷機(jī)制的優(yōu)化結(jié)果，all表示基于群體適應(yīng)值方差的早熟收斂判斷機(jī)制的優(yōu)化結(jié)果。網(wǎng)絡(luò)均勻度指標(biāo)計(jì)算公式如式（13）式所示：

式中：n為節(jié)點(diǎn)總數(shù)；ki為節(jié)點(diǎn)i的鄰居數(shù)；Di,j為節(jié)點(diǎn)i、j之間的歐氏距離；Mi為節(jié)點(diǎn)i與其所有鄰居節(jié)點(diǎn)之間歐氏距離的平均值；U為網(wǎng)絡(luò)均勻度，U越小，則覆蓋均勻性越好。

從表1數(shù)據(jù)可以發(fā)現(xiàn)，C值太小或太大都會(huì)影響算法的優(yōu)化性能。總體來(lái)看，基于精英個(gè)體適應(yīng)值方差的早熟判斷機(jī)制的表現(xiàn)比基于群體適應(yīng)值方差的早熟收斂判斷機(jī)制性能的函數(shù)優(yōu)化結(jié)果要優(yōu)越些。在小于及大于0.003 5的范圍結(jié)果較差。這是由于C取太小會(huì)使得粒子非常聚集時(shí)才進(jìn)行擾動(dòng)，容易陷入局部極值。而C太大，則使得粒子還沒(méi)有對(duì)局部區(qū)域仔細(xì)搜索就被擾動(dòng)，影響其局部搜索能力?？紤]圖1所示兩種機(jī)制對(duì)主要指標(biāo)覆蓋率影響，本次實(shí)驗(yàn)中的停滯閾值C取0.003 5。

圖1　C的取值對(duì)兩種機(jī)制下覆蓋率的影響

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

3.3.1初始傳感節(jié)點(diǎn)覆蓋情況分析

為了分析兩種不同算法所產(chǎn)生的初始傳感節(jié)點(diǎn)位置分布情況，在待測(cè)區(qū)域生成如圖2、圖3所示的節(jié)點(diǎn)位置分布圖（圖中的“+”表示傳感節(jié)點(diǎn)的位置，圓周表示傳感節(jié)點(diǎn)的感知范圍），可以看出：隨機(jī)生成的傳感節(jié)點(diǎn)分布雜亂無(wú)章，重復(fù)覆蓋區(qū)域較多；而結(jié)合混沌算法優(yōu)化后節(jié)點(diǎn)布局較為均勻，重復(fù)覆蓋區(qū)域相對(duì)較少。

圖2　隨機(jī)生成的傳感節(jié)點(diǎn)位置分布

圖3　混沌生成的傳感節(jié)點(diǎn)位置分布

對(duì)種群的20個(gè)粒子位置分布情況求取平均值，計(jì)算出初始覆蓋率、均勻度，如表2所示。從表中可以看出，混沌算法產(chǎn)生的初始節(jié)點(diǎn)位置分布的覆蓋率、均勻度分別為0.712 0、0.824 7，相比于隨機(jī)生成的0.676 0、1.042 0分別提高3.60%、0.217 3，可見(jiàn)經(jīng)混沌優(yōu)化后的傳感節(jié)點(diǎn)分布具有相對(duì)更好的覆蓋效果。

表2　傳感節(jié)點(diǎn)初始位置生成情況對(duì)比

3.3.24種算法的實(shí)驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證算法性能，選擇基本粒子群（PSO）、混沌粒子群CPSO（Chaos Particle Swarm Optimization）以及量子粒子群（QPSO）3種粒子群算法做對(duì)比實(shí)驗(yàn)。圖4～圖7分別代表PSO、CPSO、QPSO以及CQPSO算法優(yōu)化后的傳感節(jié)點(diǎn)位置分布。從圖4～圖7可以看出，CPSO和CQPSO算法優(yōu)化后的節(jié)點(diǎn)在待測(cè)區(qū)域內(nèi)分布更加均勻。如圖8所示，4種算法經(jīng)500次迭代進(jìn)化后，CQPSO、CPSO、QPSO和PSO算法的網(wǎng)絡(luò)覆蓋率分別為88.13%、86.17%、80.17%和75.92%，CQPSO相比于其他3種算法分別提高1.96%、7.96%和12.21%。

圖5　混沌粒子群算法優(yōu)化后的節(jié)點(diǎn)分布

圖6　量子粒子群算法優(yōu)化后的節(jié)點(diǎn)分布

圖8　4種優(yōu)化算法的網(wǎng)絡(luò)覆蓋率收斂曲線

3.3.3性能指標(biāo)對(duì)比結(jié)果

為了更好的評(píng)價(jià)算法，對(duì)4種算法分別進(jìn)行20次獨(dú)立的優(yōu)化實(shí)驗(yàn)求各指標(biāo)均值，比較每種算法在各個(gè)性能指標(biāo)上的優(yōu)劣，每種算法的性能指標(biāo)數(shù)據(jù)如表3所示。

表3　算法運(yùn)行20次結(jié)果對(duì)比

從表3數(shù)據(jù)可以得出：在均勻度方面，CQPSO算法的均勻度最高，20次測(cè)試平均值為0.6846，比CPSO、QPSO和PSO算法分別提高了2.51%、9.06%以及16.05%；在平均移動(dòng)距離方面，CQPSO算法平均移動(dòng)距離為9.24m，比CPSO、QPSO和PSO算法平均少移動(dòng)了0.35 m、0.72 m和1.28 m；然而在整個(gè)算法耗時(shí)方面，CQPSO算法平均耗時(shí)21 986 s，比QPSO和PSO算法延時(shí)2 182 s和1 587 s，但比CP?SO算法耗時(shí)快了約710 s，這是由于CQPSO算法有比CPSO算法更好的全局收斂性（位置更新公式的不同），混沌優(yōu)化次數(shù)較少。

綜合上述可知，CQPSO算法相比于其他3種算法在網(wǎng)絡(luò)覆蓋率、均勻度以及平均移動(dòng)距離3個(gè)指標(biāo)方面具有更優(yōu)的表現(xiàn)，混沌優(yōu)化后的傳感節(jié)點(diǎn)分布更加均勻，交叉重復(fù)覆蓋相對(duì)較小，節(jié)點(diǎn)能量消耗相對(duì)均衡；同時(shí)，每個(gè)節(jié)點(diǎn)平均移動(dòng)距離減少，降低了節(jié)點(diǎn)移動(dòng)的能量耗損。由于CQPSO算法中增加了混沌優(yōu)化環(huán)節(jié)，導(dǎo)致計(jì)算復(fù)雜度有一定增加，計(jì)算耗時(shí)相應(yīng)增多。

4　結(jié)語(yǔ)

鑒于覆蓋優(yōu)化問(wèn)題在當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)研究中的重要性，以網(wǎng)絡(luò)覆蓋率為優(yōu)化目標(biāo)，本文將量子粒子群算法和混沌優(yōu)化相結(jié)合，提出了基于混沌量子粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法。該算法基于量子粒子群算法提高算法的全局收斂性，以及精英個(gè)體適應(yīng)值方差的機(jī)制判斷算法是否陷入過(guò)早收斂；若陷入局部極值，算法對(duì)局部極值位置進(jìn)行混沌搜索，引導(dǎo)其跳出局部最優(yōu)。仿真結(jié)果表明，相對(duì)于其他3種粒子群WSN覆蓋優(yōu)化算法，CQPSO算法提高了WSN節(jié)點(diǎn)覆蓋率，網(wǎng)絡(luò)均勻度較低，平均移動(dòng)距離較少，提高了WSN網(wǎng)絡(luò)的整體性能。

參考文獻(xiàn)：

［1］孫利民，李建中，陳渝.無(wú)線傳感器網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版，2005.

［2］高德民，林海峰，劉云飛，等.基于無(wú)線傳感網(wǎng)的森林火災(zāi)FWI系統(tǒng)分析［J］.林業(yè)科技開(kāi)發(fā)，2015，29（1）：105-109.

［3］李光輝，趙軍，王智.基于無(wú)線傳感器網(wǎng)絡(luò)的森林火災(zāi)監(jiān)測(cè)預(yù)警系統(tǒng)［J］.傳感技術(shù)學(xué)報(bào)，2007，19（6）：2760-2764.

［4］趙澤，崔莉.一種基于無(wú)線傳感器網(wǎng)絡(luò)的遠(yuǎn)程醫(yī)療監(jiān)護(hù)系統(tǒng)［J］.信息與控制，2006，35（2）：265-269.

［5］常超，鮮曉東，胡穎.基于WSN的精準(zhǔn)農(nóng)業(yè)遠(yuǎn)程環(huán)境監(jiān)測(cè)系統(tǒng)設(shè)計(jì)［J］.傳感技術(shù)學(xué)報(bào)，2011，24（6）：879-883.

［6］Huang C F，Tseng Y C.The Coverage Problem in A Wireless Sen?sor Network［J］.Mobile Networks and Applications，2005，10（4）：519-528.

［7］Cardei M，Wu J.Energy-efficient Coverage Problems in Wireless Ad Hoc Sensor Networks［J］.Computer Communications，2006，29 （4）：413-420.

［8］胡中功，李靜.群智能算法的研究進(jìn)展［J］.自動(dòng)化技術(shù)與應(yīng)用，2008，27（2）：13-15.

［9］賈杰，陳劍，常桂然，等.無(wú)線傳感器網(wǎng)絡(luò)中基于遺傳算法的優(yōu)化覆蓋機(jī)制［J］.控制與決策，2007，22（11）：1259-1292.

［10］黃亮.基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署［J］.計(jì)算機(jī)測(cè)量與控制，2010，18（9）：2210-2212.

［11］毛科技，方凱，戴國(guó)勇，等.基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：1058-1065

［12］林祝亮，馮遠(yuǎn)進(jìn).基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略［J］.計(jì)算機(jī)仿真，2009，26（4）：190-193.

［13］文政穎，翟紅生.基于混沌人工蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化［J］.計(jì)算機(jī)測(cè)量與控制，2014，22（5）：1609-1612.

［14］李顯，劉明生，李燕，等.基于混沌魚(yú)群改進(jìn)算法的無(wú)線傳感網(wǎng)覆蓋優(yōu)化［J］.激光雜志，2015，36（1）：98-101.

［15］龍騰，孫輝，趙嘉.基于改進(jìn)蛙跳算法WSN移動(dòng)節(jié)點(diǎn)部署研究［J］.計(jì)算機(jī)工程，2012，38（5）：96-98，116.

［16］李忠.采用遺傳模擬退火策略的WSN節(jié)點(diǎn)部署優(yōu)化［J］.系統(tǒng)仿真學(xué)報(bào)，2014，26（2）：353-356.

［17］劉洲洲，王福豹，張克旺.改進(jìn)螢火蟲(chóng)算法性能分析及其在WSNs網(wǎng)絡(luò)覆蓋中的應(yīng)用［J］.傳感技術(shù)學(xué)報(bào)，2013，26（5）：675-682.

［18］赫然，王永吉，王青，等.一種改進(jìn)的自適應(yīng)逃逸微粒群算法及實(shí)驗(yàn)分析［J］.軟件學(xué)報(bào)，2005，16（12）：2036-2044.

［19］孫俊.量子行為粒子群優(yōu)化算法研究［D］.無(wú)錫：江南大學(xué)，2009.

［20］Li S J，Xu C F，Pan W K.Sensor Deployment Optimization for De?tecting Maneuvering Targets［C］//Proceedings of 7th International Conference on Information Fusion.Washington，DC：IEEE Com?puter Society，2005：1629-1635.

［21］Sun J，F(xiàn)eng B，Xu W B.Particle Swarm Optimization with Parti?cles Having Quantum Behavior［C］.Proceedings of 2004 Congresson Evolution Computation.Piscataway，NJ：IEEE Press，2004：325-331.

［22］申清明，閻立軍.基于混沌搜索的特征選擇方法［J］.兵工學(xué)，2013，34（12）：1616-1619.

［23］逄珊，楊欣毅，張小峰.混沌映射的多種群量子粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（33）：56-62.

［24］谷海紅，齊名軍，李士勇.基于混沌機(jī)制的混合量子粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程，2009，35（12）：164-165，168.

［25］林星，馮斌，孫俊.混沌量子粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（10）：2610-2612.

王　偉（1989-），男，安徽六安人，碩士研究生，主要從事計(jì)算機(jī)應(yīng)用技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)安全方面的研究，17009636880，wwang0211@163.com；

李　旸（1963-），男，安徽懷遠(yuǎn)人，現(xiàn)任安徽農(nóng)業(yè)大學(xué)教授、碩士生導(dǎo)師、院學(xué)術(shù)委員會(huì)副主任、院教學(xué)專家組組長(zhǎng)，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)分析管理、智能交通、智能建筑與安全防范技術(shù)、農(nóng)業(yè)網(wǎng)絡(luò)信息工程應(yīng)用等；擔(dān)任安徽省及合肥市政府采購(gòu)資深專家評(píng)委；安徽省智能交通協(xié)會(huì)理事；安徽省建筑智能化資深專家；安徽省教育信息化專家委員會(huì)委員，lyand@ahau.edu.cn。

朱娟娟（1991-），女，安徽肥東人，碩士研究生，主要從事從事計(jì)算機(jī)應(yīng)用技術(shù)、智能農(nóng)業(yè)信息技術(shù)方面的研究，15056977902，15056977902@163.com；

Coverage Optimization of Wireless Sensor Networks Based on Chaotic Quantum-Behaved Particle Swarm Algorithm*

WANG Wei1，2，ZHU Juanjuan1，2，WAN Jiashan3，QIAO Yan1，2，LI Yang1，2*
（1.School of Information &Computer Science，Anhui Agriculture University，Hefei 230036，China；2.Key Laboratory of Technology Integration and Application in Agricultural Internet of Things，Ministry of Agriculture，Hefei 230036，China；3.College of Mechanical &Electrical Engineering，Anhui Polytechnic University，Wuhu Anhui 241000，China）

Abstract：The conventional PSO algorithm has its own shortages of low convergence speed，sensitivity to local con?vergence in solving problems of the WSN coverage rate.To address these problems，based on the combined utiliza?tion of quantum-behaved particle swarm algorithm and logistic chaotic map，taking the network coverage rate as the optimized goal，a hybrid optimal algorithm（chaos quantum-behaved particle swarm optimization，CQPSO）is pro?posed.By using the new model based delta potential and judging the local convergence by the variance of the elite individuals’fitness，the algorithm improves the search's efficiency and precision.Simulating results show that the proposed algorithm is superior to other algorithms（namely PSO，QPSO and CPSO algorithm）on the coverage rate，network evenness and average traveling distance.

Key words：wireless sensor networks（WSN）；chaos searching；QPSO；coverage optimization

doi：EEACC：621010.3969/j.issn.1004-1699.2016.02.023

收稿日期：2015-08-10修改日期：2015-12-04

中圖分類號(hào)：TP391.9

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）02-0290-07

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金項(xiàng)目（61402013）；省科技攻關(guān)計(jì)劃項(xiàng)目（1301b042008）