董曉丹， 丁 力

(1.江蘇信息職業(yè)技術(shù)學(xué)院，江蘇 無(wú)錫 214153； 2. 南京航空航天大學(xué)，南京 210016)

一種混沌螢火蟲算法的WSN節(jié)點(diǎn)分布優(yōu)化研究

董曉丹1， 丁 力2

(1.江蘇信息職業(yè)技術(shù)學(xué)院，江蘇 無(wú)錫 214153； 2. 南京航空航天大學(xué)，南京 210016)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布優(yōu)化問題，提出了一種有效的混沌螢火蟲優(yōu)化算法。在保證節(jié)點(diǎn)相互連通的前提下，建立了無(wú)線傳感器網(wǎng)絡(luò)對(duì)目標(biāo)區(qū)域覆蓋的數(shù)學(xué)模型，并將節(jié)點(diǎn)分布優(yōu)化問題轉(zhuǎn)換為求解函數(shù)最大值問題；利用螢火蟲算法優(yōu)越的尋優(yōu)能力來(lái)實(shí)現(xiàn)最優(yōu)的網(wǎng)絡(luò)節(jié)點(diǎn)分布，并引入立方映射混沌算子來(lái)提高算法的局部搜索能力和保持種群的多樣性。通過(guò)標(biāo)準(zhǔn)函數(shù)測(cè)試與無(wú)線網(wǎng)絡(luò)覆蓋優(yōu)化仿真對(duì)所提算法進(jìn)行了驗(yàn)證，結(jié)果表明：與其他算法相比，所提算法能夠較好地跳出局部最優(yōu)的束縛，具有優(yōu)化效果佳、穩(wěn)定性好、魯棒性強(qiáng)的優(yōu)點(diǎn)，能夠滿足無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布優(yōu)化的要求。

無(wú)線傳感器網(wǎng)絡(luò)； 節(jié)點(diǎn)分布； 螢火蟲算法； 混沌算子

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由多個(gè)移動(dòng)或靜止的傳感器節(jié)點(diǎn)以自組織形式構(gòu)成的多跳無(wú)線網(wǎng)絡(luò)。它能夠在惡劣或特殊環(huán)境下感知、采集、處理與傳輸網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被監(jiān)測(cè)對(duì)象的信息，在軍用與民用上有著廣泛的應(yīng)用前景，近年來(lái)一直是國(guó)內(nèi)外研究的熱點(diǎn)[1-2]。合理布置網(wǎng)絡(luò)節(jié)點(diǎn)有助于提高WSN的工作效率，減少能量耗散。因此，研究如何對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分布優(yōu)化已成為WSN關(guān)鍵性技術(shù)之一。

針對(duì)WSN節(jié)點(diǎn)分布優(yōu)化問題，國(guó)內(nèi)外很多學(xué)者采用人工智能算法來(lái)進(jìn)行處理。例如，文獻(xiàn)[3]利用粒子群算法(Particle Swarm Optimization Algorithm，PSO)有效處理了WSN節(jié)點(diǎn)分布優(yōu)化問題，但PSO算法迭代效率低、定向性差且易陷入局部最優(yōu)值；在保證網(wǎng)絡(luò)連通性的前提下;文獻(xiàn)[4]通過(guò)遺傳算法(Genetic Algorithm，GA)的優(yōu)化機(jī)制，得到WSN區(qū)域覆蓋所需的最優(yōu)節(jié)點(diǎn)集，但仍未解決算法前期收斂過(guò)早、后期收斂速度變慢的問題。近期研究成果表明，利用改進(jìn)算法進(jìn)行優(yōu)化計(jì)算更具優(yōu)勢(shì)，也是學(xué)者們研究的重點(diǎn)。文獻(xiàn)[5]將差分進(jìn)化算法(Different Evolution Algorihtm，DE)與人工蜂群算法(Artificial Bee Colony Algorithm，ABC)結(jié)合，提出了一種DABC算法來(lái)解決WSN節(jié)點(diǎn)分布優(yōu)化問題；文獻(xiàn)[6]采用數(shù)據(jù)聚合算子來(lái)改進(jìn)蟻群算法(Ant Colony Algorithm，ACO)，并極大化WSN有效覆蓋面積的問題，提出了一種基于DAACO算法的WSN節(jié)點(diǎn)分布優(yōu)化機(jī)制。

螢火蟲算法是由KRISHNANAND[7]提出的一種新興元啟發(fā)式優(yōu)化算法，已被成功應(yīng)用于WSN節(jié)點(diǎn)分布優(yōu)化。但是，和其他全局算法一樣，基本的螢火蟲算法也易于陷入局部最優(yōu)值導(dǎo)致出現(xiàn)早熟和種群多樣性降低的問題。本文利用立方映射混沌算子來(lái)改進(jìn)傳統(tǒng)的螢火蟲算法，提出了一種混沌螢火蟲算法(Chaotic Glowworm Swarm Optimization，CGSO)來(lái)解決WSN節(jié)點(diǎn)分布優(yōu)化問題,該算法在螢火蟲位置初始化過(guò)程中使用混沌序列，有效保證了種群的多樣性而且避免了算法的早熟現(xiàn)象,同時(shí)，也給出了以網(wǎng)絡(luò)覆蓋率為目標(biāo)函數(shù)的描述。最后，通過(guò)標(biāo)準(zhǔn)函數(shù)測(cè)試與WSN仿真算例對(duì)本文所提算法的性能進(jìn)行了驗(yàn)證與分析。

1 問題描述

假定將一個(gè)二維平面區(qū)域A離散化為s×s的網(wǎng)格，每個(gè)網(wǎng)格的面積為1。整個(gè)區(qū)域內(nèi)分布著n個(gè)無(wú)線傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都可通過(guò)某些特殊的方式或GPS來(lái)獲取自身位置，并具有相同的感知半徑R。因此，區(qū)域A上的所有WSN節(jié)點(diǎn)集可表示為

S={s1,s2,…,sn}

(1)

式中，si=(xi,yi)，i=1,2,…,n，(xi,yi)為節(jié)點(diǎn)si在區(qū)域A內(nèi)的坐標(biāo)。對(duì)于任意網(wǎng)格點(diǎn)pj，j=1,2,…,m×n，其與節(jié)點(diǎn)si的距離為

(2)

另外，本文采用文獻(xiàn)[8]提出的概率測(cè)量模型來(lái)計(jì)算WSN的覆蓋率。節(jié)點(diǎn)si對(duì)網(wǎng)格點(diǎn)pj的檢測(cè)概率Cij可描述為

(3)

式中：Re(0

假定所有節(jié)點(diǎn)檢測(cè)都是相互獨(dú)立事件，那么由點(diǎn)pj被單個(gè)節(jié)點(diǎn)檢測(cè)的概率可得其被所有節(jié)點(diǎn)同時(shí)檢測(cè)到的綜合概率為

(4)

式中:若Cj小于某個(gè)特定閾值Ct，則認(rèn)為點(diǎn)pj不被檢測(cè)；反之，若Cj大于或等于某個(gè)特定閾值Ct，則認(rèn)為點(diǎn)pj被節(jié)點(diǎn)檢測(cè)。本文取Ct=0.75。

然后，通過(guò)點(diǎn)pj被檢測(cè)的綜合概率來(lái)衡量每個(gè)網(wǎng)格的覆蓋率，即根據(jù)式(4)計(jì)算每個(gè)網(wǎng)格點(diǎn)的檢測(cè)概率，將被檢測(cè)網(wǎng)格點(diǎn)的個(gè)數(shù)占網(wǎng)格總數(shù)的比例作為WSN的覆蓋率。具體的數(shù)學(xué)描述為

(5)

因此，WSN節(jié)點(diǎn)分布優(yōu)化問題可描述為目標(biāo)區(qū)域A上的n個(gè)無(wú)線傳感器節(jié)點(diǎn)通過(guò)優(yōu)化算法達(dá)到對(duì)整個(gè)目標(biāo)區(qū)域的覆蓋。也就是，該問題可轉(zhuǎn)換為式(5)的最大化問題，即

(6)

2 混沌螢火蟲算法

2.1 基本算法

GSO算法是對(duì)螢火蟲之間互相吸引和位置更新的模擬。算法主要由4個(gè)部分構(gòu)成，即初始化螢火蟲、熒光素更新、位置更新和決策域更新[9]。在算法中，定義t時(shí)刻第i只螢火蟲的位置和該處的熒光素值分別為xi(t)，li(t)，并且每個(gè)位置對(duì)應(yīng)的一個(gè)目標(biāo)函數(shù)值f(xi(t))，也就是WSN區(qū)域覆蓋率。

算法初始時(shí)，螢火蟲i的位置隨機(jī)產(chǎn)生,即

xi(t)=L+rand(0,1)·(U-L)i=1,…,M

(7)

式中：M為螢火蟲種群總數(shù);L和U分別是xij取值的下限和上限。

當(dāng)每只螢火蟲在其區(qū)域決策范圍內(nèi)向其鄰域個(gè)體傳遞信息時(shí)，決策范圍更新為

(8)

螢火蟲i決策范圍內(nèi)的個(gè)體數(shù)量為

(9)

式中,xj(t)和lj(t)分別為螢火蟲j的位置與熒光素值。

螢火蟲i的運(yùn)動(dòng)方向由其鄰域內(nèi)各螢火蟲的熒光素?cái)?shù)量來(lái)決定,而螢火蟲i向其鄰域內(nèi)螢火蟲j移動(dòng)的概率為

(10)

移動(dòng)后，螢火蟲i的新位置為

(11)

式中，s為移動(dòng)步長(zhǎng)。

熒光素值的大小由目標(biāo)函數(shù)值f(xi(t))決定，當(dāng)螢火蟲i更新位置后，新的熒光素值重新計(jì)算為

li(t)=(1-ρ)li(t-1)+γf(xi(t))

(12)

式中：ρ∈(0,1)為常數(shù)，與熒光素?fù)]發(fā)有關(guān)；γ為熒光素更新率。

在鄰域集合中，當(dāng)螢火蟲i找到具有更高熒光素值的螢火蟲j時(shí)，如果這兩個(gè)體間的距離小于感知半徑，則螢火蟲i以概率Pij(t)選擇螢火蟲j，并向該方向移動(dòng)；然后按式(11)更新位置，并計(jì)算新位置的目標(biāo)函數(shù)值；最后，按式(12)對(duì)熒光素值進(jìn)行更新；直至算法迭代次數(shù)達(dá)到Tmax，輸出最優(yōu)解。

2.2 立方映射混沌算子

為了克服GSO算法易陷入局部最優(yōu)值和全局開采能力不足的缺點(diǎn)，本文利用混沌算子遍歷性、規(guī)律性與隨機(jī)性的特點(diǎn)進(jìn)行優(yōu)化搜索，并保持種群的多樣性?；煦缢阕拥男问接泻芏喾N，不同的混沌算子對(duì)混沌優(yōu)化過(guò)程的影響不同。目前引用較多的是Logistic混沌算子，但算法的尋優(yōu)速度易受Logistic遍歷不均勻的影響而導(dǎo)致迭代效率降低。文獻(xiàn)[10]通過(guò)嚴(yán)格的數(shù)學(xué)推理證明了立方混沌映射要比Logistic映射具有更快的收斂速度與更好的遍歷均勻性,故本文采用立方混沌算子來(lái)改進(jìn)GSO算法的位置初始化。產(chǎn)生混沌序列為

y(n+1)=4y(n)3-3y(n)n=0,1,…,M

(13)

式中,y(n)∈[-1,1]。

將混沌序列映射到待優(yōu)化變量的取值空間內(nèi)，并實(shí)現(xiàn)對(duì)螢火蟲初始位置的混沌搜索。詳細(xì)步驟如下。

1) 對(duì)于D維空間內(nèi)的M個(gè)個(gè)體，隨機(jī)產(chǎn)生一個(gè)D維向量Y=(y1,…,yd)作為新個(gè)體，其中,yi∈[-1,1]，1≤i≤d。

2) 利用式(13)對(duì)Y逐維進(jìn)行M-1次迭代，這就產(chǎn)生了其余M-1個(gè)個(gè)體。

3) 將產(chǎn)生的混沌變量映射到解的搜索空間內(nèi)，即

(14)

式中：xid為螢火蟲i在第d維的位置；yid為利用式(13)產(chǎn)生的螢火蟲i的第d維值。

2.3 算法的時(shí)間復(fù)雜度分析

根據(jù)分析可知，GSO算法的時(shí)間復(fù)雜度為O(M×Tmax)。由于增加了混沌搜索算子，CGSO算法的時(shí)間復(fù)雜度取決于混沌序列的長(zhǎng)度K，故混沌搜索階段的時(shí)間復(fù)雜度為O(K×Tmax)。但根據(jù)參數(shù)敏感性分析[11]，種群大小M與混沌序列K呈線性關(guān)系，經(jīng)過(guò)約減后CGSO算法的時(shí)間復(fù)雜度也為O(M×Tmax)。因此，兩種算法的時(shí)間復(fù)雜度是相同的。

3 仿真分析

3.1 標(biāo)準(zhǔn)函數(shù)測(cè)試

為了測(cè)試CGSO算法的性能，本文采用文獻(xiàn)[12]提出的4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試，并與CPSO算法、GSO算法比較。4個(gè)函數(shù)的理論全局最小值均為0，為了公平比較各算法的優(yōu)化性能，設(shè)置各算法的種群規(guī)模為20，各測(cè)試函數(shù)的維數(shù)為30，迭代次數(shù)為1000次。然后，通過(guò)各算法分別對(duì)各測(cè)試函數(shù)進(jìn)行50次獨(dú)立測(cè)試，表1給出了測(cè)試的統(tǒng)計(jì)結(jié)果，包括平均值(Mean)和標(biāo)準(zhǔn)差(SD)。

表1 函數(shù)優(yōu)化的結(jié)果

由表1可知，CGSO算法在Sphere，Rastrigin和Griewank函數(shù)上，無(wú)論是平均值還是標(biāo)準(zhǔn)差均優(yōu)于GSO算法與CPSO算法，而且都有明顯的數(shù)量級(jí)提升。雖然，CGSO算法在Ackley函數(shù)上性能要略低于CPSO算法，但它們的平均值和標(biāo)準(zhǔn)差仍處于同一數(shù)量級(jí)。這說(shuō)明與其他兩種算法相比，CGSO算法具有更強(qiáng)的尋優(yōu)能力和更高的求解質(zhì)量。

3.2 WSN仿真實(shí)例

為了驗(yàn)證本文所提算法在處理WSN節(jié)點(diǎn)分布優(yōu)化問題的有效性，假設(shè)WSN的監(jiān)控范圍為100 m×100 m的正方形區(qū)域，傳感器節(jié)點(diǎn)的感知半徑R為7 m。在監(jiān)控范圍內(nèi)隨機(jī)分布著100個(gè)WSN節(jié)點(diǎn)，通過(guò)GSO算法、CPSO算法和CGSO算法分別對(duì)其進(jìn)行優(yōu)化處理，各迭代1000代，重復(fù)操作50次，記錄下其中的最優(yōu)解。

3種算法的參數(shù)設(shè)置如下：在GSO算法和CGSO算法中，M=20，ρ=0.4，γ=0.6，β=0.1，nt=8，s=0.03；在CPSO算法中，種群大小為20，學(xué)習(xí)因子c1=c2=2，權(quán)重因子W=0.8[13]。

當(dāng)算法運(yùn)行結(jié)束后，統(tǒng)計(jì)各算法的最優(yōu)覆蓋率與平均覆蓋率，相應(yīng)結(jié)果如表2所示。從表中可以看出，經(jīng)混沌算子改進(jìn)后的GSO算法優(yōu)化成功率得到了大大的提升。

表2 3種算法結(jié)果對(duì)比

圖1給出了3種算法網(wǎng)絡(luò)覆蓋率最優(yōu)解的迭代曲線。從圖中可見，GSO算法與CPSO算法分別到了411次和197次迭代才開始收斂，而CGSO算法到了156次迭代便開始收斂。另外，本文算法獲得的最優(yōu)網(wǎng)絡(luò)覆蓋率為99.44%，而CPSO算法與GSO算法獲得的分別為98.87%和98.13%。這表明CGSO算法收斂速度快，全局搜索能力強(qiáng)，能夠擺脫局部最優(yōu)的束縛。

圖1 3種算法網(wǎng)絡(luò)覆蓋率最優(yōu)解的迭代曲線Fig.1 Optimal iteration curves of three algorithms

另外，為了驗(yàn)證種群規(guī)模對(duì)算法性能的影響，設(shè)置種群大小分別為10, 20和30，運(yùn)行500代。通過(guò)3種算法獲得的網(wǎng)絡(luò)覆蓋率如表3所示。從表中可以看出，隨著種群規(guī)模的擴(kuò)大，CGSO算法的尋優(yōu)精度要高于其他算法,這表明本文所提算法能夠獲取更多的搜索信息和保持種群的多樣性。

表3 不同種群規(guī)模下各算法的優(yōu)化結(jié)果比較

為了進(jìn)一步驗(yàn)證CGSO算法的性能，設(shè)計(jì)了基于不同節(jié)點(diǎn)數(shù)目的網(wǎng)絡(luò)覆蓋率仿真。3種算法的網(wǎng)絡(luò)覆蓋率隨節(jié)點(diǎn)密度的變化曲線如圖2所示。從圖中可以看出，要實(shí)現(xiàn)90%以上的覆蓋率，GSO算法與CPSO算法各需要布置125和175個(gè)節(jié)點(diǎn)，而CGSO算法只需要布置75個(gè)節(jié)點(diǎn),這說(shuō)明CGSO算法對(duì)全局信息的開采速度快。

圖2 網(wǎng)絡(luò)覆蓋率比較圖Fig.2 Network coverage when node density changes

從圖3與圖4可以看出，初始狀態(tài)雜亂無(wú)章的節(jié)點(diǎn)經(jīng)CGSO算法優(yōu)化布置后，分布比較均勻，重疊覆蓋率相對(duì)較小。因此，本文提出的基于CGSO算法的WSN節(jié)點(diǎn)分布優(yōu)化策略可以合理解決網(wǎng)絡(luò)覆蓋優(yōu)化問題，并能有效提高網(wǎng)絡(luò)覆蓋率。

圖3 初始節(jié)點(diǎn)分布圖Fig.3 Initial node distribution

圖4 經(jīng)CGSO算法優(yōu)化后的節(jié)點(diǎn)分布圖Fig.4 Node distribution based on CGSO

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

本文針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布優(yōu)化問題，提出了一種基于混沌螢火蟲算法(CGSO)的節(jié)點(diǎn)分布優(yōu)化方案。該算法利用立方映射混沌算子改進(jìn)了GSO算法中螢火蟲初始位置的更新策略，保持了種群的多樣性，提高了算法的收斂速度與全局搜索能力。

與GSO算法和CPSO算法相比，CGSO算法在求解標(biāo)準(zhǔn)測(cè)試函數(shù)上有更高的求解質(zhì)量與更快的收斂速度。

在優(yōu)化WSN節(jié)點(diǎn)分布算例中，CGSO算法的最優(yōu)網(wǎng)絡(luò)覆蓋率比CPSO算法和GSO算法分別提高了0.57%和1.31%。在獲得同樣網(wǎng)絡(luò)覆蓋率的條件下，CGSO算法所需的節(jié)點(diǎn)數(shù)量更少。

[1] ANTONIO P,GRIMACCIA F,MUSSETTA M.Architecture and methods for innovative heterogeneous wireless sensor network applications[J].Remote Sensing,2012,4(5):1146-1161.

[2] ZHANG J,ZHANG M.Energy efficient dynamic mixed key management scheme based on virtual grid in wireless sensor netwoks[J].Journal of Convergence Information Technology,2011,6(7):111-118.

[3] KUILA P,JANA P K.Energy efficient clustering and routing algorithms for wireless sensor networks:particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014(33):127-140.

[4] HUSSAIN S,MATIN A W,ISLAM O.Genetic algorithm for hierarchical wireless sensor networks[J].Journal of Networks,2007,2(5):87-97.

[5] 熊偉麗,劉欣,陳敏芳,等.基于差分蜂群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布優(yōu)化[J].控制工程,2014,6(21):1036-1040.

[6] LIN C,WU G,XIA F,et al.Energy efficient ant colony algorithms for data aggregation in wireless sensor networks[J].Journal of Computer and System Sciences,2012,78(6):1686-1702.

[7] KRISHNANAND K N,GHOSE D.Glowworm swarm optimisation: a new method for optimising multi-modal functions[J].International Journal of Computational Intelligence Studies,2009,1(1):93-119.

[8] ?ZTüRK C,KARABOA D,G?RKEMLB.Artificial bee colony algorithm for dynamic deployment of wireless sensor networks[J].Turkish Journal of Electrical Engineering & Computer Sciences,2012,20(2):255-262.

[9] KRISHNANAND K N,GHOSE D.A glowworm swarm optimization based multi-robot system for signal source localization[M].Berlin:Springer Heidelberg,2009:49-68.

[10] CHEN G,WU X D,ZHU X Q,et al.Efficient string mat-ching with wildcards and length constraints[J].Knowledge and Information Systems,2006,10(4):399-419.

[11] 王翔,李志勇,許國(guó)藝,等.基于混沌局部搜索算子的人工蜂群算法[J].計(jì)算機(jī)應(yīng)用,2012,32(4):1033-1036.

[12] LEI L,SHIRU Q.Path planning for unmanned air vehicles using an improved artificial bee colony algorithm[C]//31st Chinese Control Conference (CCC),IEEE, 2012: 2486-2491.

[13] 陳志敏,薄煜明,吳盤龍,等.混沌粒子群優(yōu)化粒子濾波算法[J].電光與控制,2013,20(1):36-40.

ChaoticGlowwormSwarmOptimizationAlgorithminSensorDeploymentforWirelessSensorNetworks

DONG Xiao-dan1, DING Li2

(1.Jiangsu Vocational College of Information Technology,Wuxi 214153,China;2.Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Aiming at node deployment optimization in wireless sensor networks,an effective chaotic glowworm swarm optimization was proposed.On the premise that connectivity among nodes was guaranteed,we established a mathematical model to achieve the coverage of objective area with wireless sensor networks,and transformed the node-deployment optimization problem into finding the largest value of a function.The glowworm swarm optimization with the strong search performance was used to search the optimal node deployment.And the cubic mapping chaotic operator was introduced to enhance the ability of local search and robustness and to keep the diversity of population.Then,the proposed algorithm was verified through the numerical benchmark functions and coverage simulation.All the results showed that the proposed algorithm has the ability to jump out of local optimum and has good optimization results,nice stability and strong robustness.Hence,it can satisfy the requirement of optimal node deployment in wireless sensor networks.

wireless sensor network; node deployment; glowworm swarm optimization; chaotic operator

TP18

A

1671-637X(2017)03-0073-04

2016-05-05

2016-06-03

江蘇省高校品牌專業(yè)建設(shè)工程資助項(xiàng)目 (PPZY2015B190)

董曉丹(1981 —),男，江蘇無(wú)錫人，碩士，講師，研究方向?yàn)橥ㄐ偶夹g(shù)、智能算法等。