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

董曉丹， 丁 力

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

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

董曉丹1， 丁 力2

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

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

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

0 引言

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

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

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

1 問題描述

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

S={s1,s2,…,sn}

(1)

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

(2)

另外，本文采用文獻[8]提出的概率測量模型來計算WSN的覆蓋率。節(jié)點si對網(wǎng)格點pj的檢測概率Cij可描述為

(3)

式中：Re(0

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

(4)

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

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

(5)

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

(6)

2 混沌螢火蟲算法

2.1 基本算法

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

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

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

(7)

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

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

(8)

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

(9)

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

螢火蟲i的運動方向由其鄰域內(nèi)各螢火蟲的熒光素數(shù)量來決定,而螢火蟲i向其鄰域內(nèi)螢火蟲j移動的概率為

(10)

移動后，螢火蟲i的新位置為

(11)

式中，s為移動步長。

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

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

(12)

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

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

2.2 立方映射混沌算子

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

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

(13)

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

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

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

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

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

(14)

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

2.3 算法的時間復雜度分析

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

3 仿真分析

3.1 標準函數(shù)測試

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

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

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

3.2 WSN仿真實例

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

在優(yōu)化WSN節(jié)點分布算例中，CGSO算法的最優(yōu)網(wǎng)絡覆蓋率比CPSO算法和GSO算法分別提高了0.57%和1.31%。在獲得同樣網(wǎng)絡覆蓋率的條件下，CGSO算法所需的節(jié)點數(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ǎng)絡節(jié)點分布優(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] 王翔,李志勇,許國藝,等.基于混沌局部搜索算子的人工蜂群算法[J].計算機應用,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è)工程資助項目 (PPZY2015B190)

董曉丹(1981 —),男，江蘇無錫人，碩士，講師，研究方向為通信技術(shù)、智能算法等。