混沌優(yōu)化細(xì)菌覓食算法的傳感器節(jié)點(diǎn)部署策略*

王振東,陳峨霖,胡中棟

(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

廣泛應(yīng)用于地質(zhì)監(jiān)測、環(huán)境保護(hù)等領(lǐng)域的自組織多跳無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)具有部署靈活、成本低廉、覆蓋范圍廣等優(yōu)點(diǎn)[1],但監(jiān)測區(qū)域的大范圍隨機(jī)部署會帶來節(jié)點(diǎn)分布不均勻問題[2],針對該問題,眾多學(xué)者運(yùn)用群智能仿生算法進(jìn)行優(yōu)化處理[3]。文獻(xiàn)[4]基于人工魚群算法構(gòu)建網(wǎng)絡(luò)覆蓋模型,通過模型求解來優(yōu)化網(wǎng)絡(luò)覆蓋。文獻(xiàn)[5]利用概率感知模型將遺傳算法與粒子群算法相結(jié)合來優(yōu)化網(wǎng)絡(luò)覆蓋。文獻(xiàn)[6]提出使用有效質(zhì)心和重疊質(zhì)心改進(jìn)虛擬力計(jì)算公式和節(jié)點(diǎn)往復(fù)運(yùn)動優(yōu)化網(wǎng)絡(luò)節(jié)點(diǎn)部署。為了克服粒子群算法容易陷入局部最優(yōu)等,后期收斂速度慢等缺點(diǎn),文獻(xiàn)[7]采用混沌運(yùn)動對原始算法進(jìn)行了優(yōu)化。文獻(xiàn)[8]提出一種在不同網(wǎng)絡(luò)規(guī)模及連通度都可以明顯提高傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位準(zhǔn)確度及網(wǎng)絡(luò)覆蓋率的算法。文獻(xiàn)[9]采用改進(jìn)蟻群算法的方式優(yōu)化離散監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋率。上述群智能算法在WSN覆蓋優(yōu)化問題上取得了較大成效,但也存在諸如求解復(fù)雜度高、收斂速度慢、收斂精度低、運(yùn)算成本大等問題。

對此,本文提出一種混沌優(yōu)化的細(xì)菌覓食算法COBFA(Chaos Optimization of Bacterial Foraging Algorithm),并基于該算法對監(jiān)測區(qū)域節(jié)點(diǎn)部署情況進(jìn)行仿真。研究表明,現(xiàn)有細(xì)菌覓食算法對全局空間尋優(yōu)能力差,搜索速度和搜索精確度均有待提高,且容易陷入局部最優(yōu)及產(chǎn)生早熟。針對上述問題,首先構(gòu)造菌群密度函數(shù)因子、細(xì)菌反彈因子及自適應(yīng)細(xì)菌趨化步長來改進(jìn)細(xì)菌覓食過程中的翻轉(zhuǎn)概率和細(xì)菌的趨化步長。然后,依據(jù)混沌系統(tǒng)的遍歷性,隨機(jī)生成混沌擾動序列來幫助細(xì)菌翻轉(zhuǎn)后對方向的選擇,當(dāng)菌群繁殖時(shí)利用交叉和變異操作以避免細(xì)菌搜索到局部最優(yōu)。最后,利用自適應(yīng)菌群遷徙概率來提高算法的收斂速度,使最終部署的WSN網(wǎng)絡(luò)具有較高的綜合覆蓋率及較低的能量消耗。

1 相關(guān)模型

本節(jié)主要介紹需要用到的基本模型和基本算法。主要包括:節(jié)點(diǎn)之間的距離模型,節(jié)點(diǎn)能量消耗計(jì)算公式,如何計(jì)算節(jié)點(diǎn)覆蓋面積并構(gòu)造聯(lián)合覆蓋率目標(biāo)函數(shù),接著介紹基本BFO算法。算法主要工作是求解構(gòu)造的目標(biāo)函數(shù)。

1.1 節(jié)點(diǎn)距離模型

隨機(jī)拋撒在監(jiān)測區(qū)域的大量傳感器節(jié)點(diǎn)可以視為隨機(jī)且相互獨(dú)立[10]。設(shè)定單個(gè)節(jié)點(diǎn)的感知半徑為r,通訊半徑為R,在應(yīng)用中R≥2r。o(i)是位于目標(biāo)監(jiān)測區(qū)域內(nèi)的一個(gè)傳感器節(jié)點(diǎn)[11],其坐標(biāo)的位置為(xi,yi),(xj,yj)是另一個(gè)位于目標(biāo)監(jiān)測區(qū)域內(nèi)的某個(gè)傳感器節(jié)點(diǎn)g(j)的坐標(biāo)。則節(jié)點(diǎn)o(i)到節(jié)點(diǎn)g(j)的距離為:

(1)

1.2 能耗模型

WSN節(jié)點(diǎn)消耗的能量包括收發(fā)數(shù)據(jù)、處理數(shù)據(jù)和其他能量消耗,能耗模型使用文獻(xiàn)[12]中的模型,本文主要考慮收發(fā)數(shù)據(jù)消耗的能量。則節(jié)點(diǎn)在相距為d*m時(shí)發(fā)送l*bit的數(shù)據(jù)消耗的能量為:

(2)

ER(l*)表示節(jié)點(diǎn)接收l*bit數(shù)據(jù)消耗的能量:

ER(l)=lEelec

(3)

則節(jié)點(diǎn)剩余能量為:

Es=E0-q*Emem-p*ET(l*)

(4)

1.3 節(jié)點(diǎn)探測概率

本文采用奈曼—皮爾遜準(zhǔn)則[13]的感知模型計(jì)算傳感器的探測概率,設(shè)傳感器節(jié)點(diǎn)存在高斯噪聲并對其進(jìn)行相互獨(dú)立的處理,那么第a個(gè)目標(biāo)點(diǎn)的測量值為:

(5)

則接收信號ra在H0和H1情況下的概率密度函數(shù)分別為:

(6)

(7)

式中:σ是噪聲的標(biāo)準(zhǔn)差,由奈曼—皮爾遜準(zhǔn)則:

準(zhǔn)則:

(8)

式中:ω為閾值,由式(5)得:

(9)

由式(6)可得:

(10)

那么得到的WSN節(jié)點(diǎn)誤警率是:

(11)

則節(jié)點(diǎn)b對目標(biāo)點(diǎn)a的探測概率為:

(12)

式中:W為可以探測到目標(biāo)a的周圍固定節(jié)點(diǎn)的個(gè)數(shù)。

(13)

那么WSN的有效覆蓋率為:

(14)

定義1聯(lián)合覆蓋目標(biāo)函數(shù) WSNs聯(lián)合覆蓋是指在保證能量均衡的情況下利用較少節(jié)點(diǎn)達(dá)到較大的網(wǎng)絡(luò)覆蓋率,綜合考慮WSN工作節(jié)點(diǎn)數(shù)、有效覆蓋率和剩余能量均衡性的聯(lián)合覆蓋目標(biāo)函數(shù)f為:

f=w1f1+w2f2+w3f3

(15)

式中:w1、w2、w3為權(quán)值,且;

w1+w2+w3=1

(16)

式中:f1為WSN有效覆蓋率,f2為WSN節(jié)點(diǎn)閑置率:

f2=(N-N′)/N

(17)

N為WSN節(jié)點(diǎn)的部署總數(shù),N′為WSN工作的節(jié)點(diǎn)數(shù),節(jié)點(diǎn)閑置率越大越好。

WSN剩余能量均衡函數(shù)為f3,表示W(wǎng)SN局部區(qū)域的剩余能量均衡程度,其值越大,局部區(qū)域內(nèi)的節(jié)點(diǎn)生存時(shí)間越長。

(18)

將目標(biāo)函數(shù)轉(zhuǎn)化為多目標(biāo)優(yōu)化過程來求f得極大值,即求子函數(shù):f1、f2、f3的極大值及其對應(yīng)權(quán)重系數(shù)。

圖1 AHP層次結(jié)構(gòu)模型

1.4 AHP確定權(quán)值系數(shù)

在多因素或多目標(biāo)決策過程中,層次分析法[14]AHP(Analytic Hierarchy Process)應(yīng)用相對廣泛,主要包括6個(gè)步驟:構(gòu)造階梯層次結(jié)構(gòu)、建立判斷矩陣、判斷矩陣一致性檢驗(yàn)、層次單排序和總排序和對分析結(jié)果進(jìn)行決策。本文采AHP對f中的權(quán)值系數(shù)w1、w2、w3優(yōu)化求解。

根據(jù)式(15)中f1、f2、f3與節(jié)點(diǎn)部署之間的關(guān)系建立層次結(jié)構(gòu)模型如圖1所示。

從圖1目標(biāo)層開始,自上而下依據(jù)上一層元素分別同下一層元素中與之關(guān)聯(lián)的元素兩兩比較,建立判斷矩陣A。

由實(shí)驗(yàn)得出的準(zhǔn)則層因素相對比重如判斷矩陣A:

經(jīng)過一致性檢驗(yàn)可知矩陣A具有近似一致性。權(quán)值向量由計(jì)算A的最大特征根及其對應(yīng)特征向量可得:

w=[0.633 3 0.106 2 0.260 5]T

在雙層層次結(jié)構(gòu)模型中,單排序權(quán)重w與總排序權(quán)重相同,所以由w得到的三因素權(quán)值系數(shù)為:

w1=0.633 3,w2=0.106 2,w3=0.260 5

1.5 基本BFO

BFO(Bacterial Foraging Optimization Algorithm)是一種受細(xì)菌覓食行為啟發(fā)提出的仿生群智能算法[15],設(shè)置3種算子代表細(xì)菌在覓食過程中的趨化、繁殖和遷徙行為來尋找種群最優(yōu)。

定義2趨化算子

菌群趨化算子表示單個(gè)細(xì)菌在尋找食物時(shí)以一定概率向任意方向翻轉(zhuǎn),并在該方向以單元步長游動:

θi(g+1,s,l)=θi(g,s,l)+c(i)×φ(i)

(19)

(20)

式中:θi(g+1,s,l)表示單個(gè)細(xì)菌粒子進(jìn)行g(shù)次趨化、s次移動和l次繁殖操作時(shí)細(xì)菌i的位置函數(shù),c(i)是細(xì)菌游動的趨化步長,Δ(i)為細(xì)菌變向過程中生成的某個(gè)方向向量,φ(i)為細(xì)菌調(diào)整方向后的單元步長向量。

定義3繁殖算子

對于搜索菌群,細(xì)菌趨化循環(huán)后選擇性繁殖,通過對細(xì)菌適應(yīng)度排序,淘汰一半較差適應(yīng)度的細(xì)菌后分裂復(fù)制另一半細(xì)菌保持細(xì)菌總數(shù)不變。假設(shè)第i個(gè)細(xì)菌適應(yīng)度累加和為:

(21)

J(i,g,s,l)代表細(xì)菌i在l次遷徙、s次復(fù)制、g次趨化時(shí)的適應(yīng)度。

定義4遷徙算子

對于搜索菌群,趨化繁殖若干次后,細(xì)菌個(gè)體隨機(jī)分布在監(jiān)測區(qū)域,假設(shè)以概率Ped對菌群進(jìn)行驅(qū)散操作來避免覓食過程過早收斂,提高全局搜索最優(yōu)解的概率。

1.6 基本BFO步驟

Step 1 隨機(jī)初始化N個(gè)細(xì)菌,細(xì)菌的趨化、復(fù)制、遷徙次數(shù)分別為Nc,Nre,Ned。操作計(jì)數(shù)參數(shù)設(shè)為g,s,l,θi(g,s,l)表示細(xì)菌第g次趨化,第s次復(fù)制,第l次遷徙的位置。單個(gè)細(xì)菌的趨化步長為c(i),在相同方向最大趨化步數(shù)為Nc,遷徙概率為Ped,細(xì)菌搜索維度為d。

Step 2 計(jì)算細(xì)菌的初始適應(yīng)值J(i,g,s,l)。

Step 3 趨化行為g=g+1。

Step 4 復(fù)制行為s=s+1。

Step 5 遷徙行為l=l+1,

對細(xì)菌i=1,2,…,N,按如下方法進(jìn)行趨化循環(huán)操作。

(1)用Jlast=J(i,g,s,l)存儲當(dāng)前最佳適應(yīng)度值。

①翻轉(zhuǎn),產(chǎn)生隨機(jī)向量Δ(i)∈Rn,且Δm(i),(m=1,2,…,N)隨機(jī)分布在[-1,1]。

②移動,

θi(g+1,s,l)=θi(g,s,l)+c(i)×φ(i),

其中c(i)表示細(xì)菌i翻轉(zhuǎn)后游動的步長。

(2)用θi(g+1,s,l)計(jì)算適應(yīng)度值J(i,g+1,s,l),用g計(jì)數(shù)細(xì)菌游動次數(shù),讓g=g+1.若J(i,g+1,s,l)

若g

Step 7 若s

Step 8 按給定概率Ped對每個(gè)細(xì)菌i=1,2,…,N進(jìn)行遷徙行為,讓Ped小于隨機(jī)值的細(xì)菌存活并分布于尋優(yōu)空間,若l

2 模型求解

本節(jié)主要介紹構(gòu)造的聯(lián)合覆蓋率目標(biāo)函數(shù)模型如何求解;為了避免細(xì)菌的位置難以與WSN節(jié)點(diǎn)位置重合,首先定義了細(xì)菌粒子與節(jié)點(diǎn)的編碼映射,然后通過對Logistic映射方程初值及參數(shù)的對比實(shí)驗(yàn),尋找能迭代出的具有較好遍歷性和全局搜索能力的混沌隨機(jī)序列的初值及參數(shù),幫助細(xì)菌在趨化行為階段細(xì)菌翻轉(zhuǎn)后選擇方向。

改進(jìn)BFO包括:細(xì)菌在趨化階段進(jìn)行行為翻轉(zhuǎn)時(shí),改進(jìn)趨化翻轉(zhuǎn)概率,引入時(shí)間參數(shù)因子對翻轉(zhuǎn)概率進(jìn)行動態(tài)調(diào)整來保證算法的精確性;細(xì)菌翻轉(zhuǎn)后,用混沌模型生成的混沌隨機(jī)序列幫助細(xì)菌選擇方向;在移動行為時(shí),設(shè)置菌群密度函數(shù)因子,以適應(yīng)細(xì)菌周圍環(huán)境的影響。此外,對細(xì)菌的趨化步長進(jìn)行動態(tài)調(diào)整,當(dāng)細(xì)菌之間的距離小于閾值時(shí),利用反彈步長使細(xì)菌向食物感知系數(shù)大的方向移動;在細(xì)菌繁殖階段,使用交叉算子和變異算子改善細(xì)菌的適應(yīng)度,并計(jì)算各個(gè)菌群的聯(lián)合覆蓋率以求解聯(lián)合覆蓋率目標(biāo)函數(shù)模型;最后在遷徙階段動態(tài)調(diào)整遷徙概率以確保細(xì)菌具有較好的尋優(yōu)能力。

2.1 多目標(biāo)優(yōu)化模型求解

針對構(gòu)造的聯(lián)合覆蓋目標(biāo)函數(shù)多目標(biāo)優(yōu)化模型(15)采取如圖2所示的方法求解。

圖2 多目標(biāo)優(yōu)化模型求解流程圖

定義5編碼映射關(guān)系:

假設(shè)菌群對監(jiān)測區(qū)域離散搜索時(shí)細(xì)菌粒子與WSN節(jié)點(diǎn)位置間的相互映射[16]函數(shù)為:

Z(Xid)={Xnd|min(‖Xnd-Xid‖)}1≤n≤N

(22)

式中:Xnd表示W(wǎng)SN的節(jié)點(diǎn)位置,Xid表示細(xì)菌粒子的位置,‖Xnd-Xid‖是歐氏距離,d是離散搜索的空間維度(本文中d=2)。

菌群為監(jiān)測目標(biāo)區(qū)域的節(jié)點(diǎn)集合,一個(gè)菌落由e個(gè)細(xì)菌粒子構(gòu)成,代表一種節(jié)點(diǎn)部署方案。每個(gè)粒子代表一個(gè)WSN節(jié)點(diǎn),細(xì)菌的搜索維度為2,表示二維搜索平面x軸和y軸的取值,區(qū)域內(nèi)節(jié)點(diǎn)的聯(lián)合覆蓋率代表細(xì)菌的適應(yīng)度值。

2.2 混沌模型

混沌優(yōu)化CO(Chaos Optimization)依據(jù)混沌運(yùn)動對初始值敏感性且能按照自身搜索規(guī)律在搜索范圍內(nèi)不重復(fù)遍歷搜索所有狀態(tài)來提高搜索效率[17]。

著名的Logistic混沌映射方程表達(dá)式為:

zn+1=cρ(ρ,zn)=ρxn(1-zn),zn∈(0,1)

(23)

式中:ρ表示混沌映射系統(tǒng)的參數(shù)。若zi=[mi,ni],那么可由式(24)、式(25)對混沌序列[14]zi進(jìn)行往返映射。

(24)

(25)

2.3 初值及參數(shù)影響產(chǎn)生的混沌序列

Logistic映射系統(tǒng)十分敏感初值和參數(shù),不同的初值和參數(shù)可能得到不同的混沌隨機(jī)序列,通過研究混沌運(yùn)動的軌跡所生成的軌跡序列分布圖直觀表示,在細(xì)菌覓食時(shí)加入混沌隨機(jī)序列,提高了菌群的多樣性和全局尋優(yōu)能力。

圖3表示不同初值z0,參數(shù)ρ通過Logistic方程迭代500次后得到分布在(0,1)區(qū)間上的軌跡序列分布圖,利用它來尋找具有較好遍歷性和全局搜索能力的混沌隨機(jī)序列。

圖3 5種初值和參數(shù)的時(shí)軌跡序列分布圖

由圖3知當(dāng)初值z0=0.6576,參數(shù)ρ=2.5、z0=0.997 8,參數(shù)ρ=3.56和z0=0.5,參數(shù)ρ=4時(shí),Logistic混沌映射方程迭代生成的的生成的隨機(jī)序列分布不均勻,在(0,1)區(qū)間上形成的是近似于直線的間斷運(yùn)動軌跡沒有較好的均勻性和遍歷性。當(dāng)初值z0=0.997 8,參數(shù)ρ=3.8時(shí),Logistic混沌映射方程迭代產(chǎn)生的混沌序列隨機(jī)分布于(0,1)區(qū)間,但該初值和參數(shù)生成的混沌序列分布在一個(gè)帶狀區(qū)域,序列并不能對搜索區(qū)域完全遍歷相關(guān)區(qū)域。當(dāng)初值z0=0.997 8,參數(shù)ρ=4時(shí),Logistic混沌映射方程通過迭代可以在(0,1)區(qū)間上形成分布較為平均的且有著很好遍歷性的混沌隨機(jī)序列,該序列能夠?qū)λ阉鲄^(qū)域進(jìn)行全局搜索。所以在后文利用Logistic混沌映射方程迭代產(chǎn)生混沌隨機(jī)序列時(shí)選取的是初值z0=0.997 8,參數(shù)ρ=4。

2.4 細(xì)菌覓食算法改進(jìn)

2.4.1 菌群密度函數(shù)

單個(gè)細(xì)菌不斷感知菌群擁擠程度以減小菌群周圍環(huán)境影響搜索結(jié)果,根據(jù)細(xì)菌間的平均距離動態(tài)調(diào)整搜索細(xì)菌的趨化步長。設(shè)菌群密度函數(shù)因子為:

(26)

感知細(xì)菌密度改進(jìn)趨化函數(shù):

C(i)=A×D(k)+B

(27)

式中:Cmin與Cmax,Dmin與Dmax分別是細(xì)菌最小、最大趨化步長,最小、最大間隔距離。

Cmin≤C(k)≤Cmax,Dmin≤D(k)≤Dmax,

A=(Cmax-Cmin)/(Dmax-Dmin),

B=(DminCmax-DmaxCmin)/(Dmax-Dmin)。

2.4.2 趨化反彈步長

細(xì)菌趨化階段加入反彈系數(shù),當(dāng)菌落內(nèi)細(xì)菌i和j距離小于設(shè)定閾值,細(xì)菌i對細(xì)菌j產(chǎn)生反彈作用,使其各自向食物感知系數(shù)大的方向遷徙,sij表示細(xì)菌i和j反彈后的游動距離,α表示節(jié)點(diǎn)的冗余覆蓋度:

(28)

2.4.3 冗余覆蓋度

節(jié)點(diǎn)i的冗余覆蓋度[18]表示i感知區(qū)域內(nèi)鄰居節(jié)點(diǎn)nei(i)感知面積與節(jié)點(diǎn)感知面積的重疊區(qū)域與節(jié)點(diǎn)感知面積的比值,用式(29)計(jì)算:

(29)

式中:axi代表節(jié)點(diǎn)i的感知面積區(qū)域。

axi=

(30)

式中:n為i的鄰居節(jié)點(diǎn)數(shù)目,r為節(jié)點(diǎn)感知的半徑,dit為鄰居節(jié)點(diǎn)t與節(jié)點(diǎn)i的距離。

2.4.4 趨化翻轉(zhuǎn)概率

在細(xì)菌覓食時(shí)引入時(shí)變衰減函數(shù)作為衰減因子β,改進(jìn)覓食時(shí)細(xì)菌的翻轉(zhuǎn)概率[19],通過時(shí)間參數(shù)因子對翻轉(zhuǎn)概率進(jìn)行動態(tài)調(diào)整來保證算法的精確性。其函數(shù)為:

visk+1=β×visk+vismin

(31)

β=e-Ti-T0

(32)

式中:T0表示算法初始運(yùn)行時(shí)間,Ti表示算法當(dāng)前運(yùn)行時(shí)間,vismin為給定的最小翻轉(zhuǎn)概率,開始時(shí)β值較大,函數(shù)快速收斂且翻轉(zhuǎn)概率大。隨著時(shí)間的推移,β逐漸變小,翻轉(zhuǎn)概率也會慢慢變小最終達(dá)到最小值。

2.4.5 繁殖算子改進(jìn)

細(xì)菌繁殖階段利用交叉算子使健康細(xì)菌在搜索過程中起正向作用以改善適應(yīng)度差的細(xì)菌個(gè)體,適應(yīng)度差的半數(shù)細(xì)菌個(gè)體與適應(yīng)度好的健康細(xì)菌先相互雜交;同時(shí)為了防止菌群早熟陷入局部最優(yōu)解,設(shè)置菌群變異算子對雜交后的高適應(yīng)度的半數(shù)細(xì)菌進(jìn)行隨機(jī)微小擾動后復(fù)制分裂。

菌群細(xì)菌的交叉算子設(shè)為:

F″(i)=χX(i)+(1-χ)X(best),i=1,2,…,N

(33)

式中:χ為[0,1]均勻的隨機(jī)數(shù),X(best)為菌群搜索的高適應(yīng)度細(xì)菌的編號,F″(i)為高適應(yīng)度細(xì)菌的坐標(biāo)信息。

菌群細(xì)菌的變異算子設(shè)為:

F′(i)=F(i)+Y,i=1,2,…,N

(34)

式中:Y服從標(biāo)準(zhǔn)正態(tài)分布N(0,1)。

2.4.6 動態(tài)遷徙概率調(diào)整

細(xì)菌遷徙階段以概率Pself對遷徙概率動態(tài)調(diào)整:

(35)

式中:Jnum是適應(yīng)度函數(shù),Ped是原始遷徙概率。

3 算法及分析

3.1 步驟

Step 1 隨機(jī)初始化N個(gè)細(xì)菌,細(xì)菌的趨化、復(fù)制、遷徙次數(shù)分別為Nc,Nre,Ned.設(shè)3種操作循環(huán)計(jì)數(shù)參數(shù)為g,s,l,θi(g,s,l)表示細(xì)菌第g次趨化,第s次復(fù)制,第l次遷徙的位置.單個(gè)細(xì)菌的趨化步長為c(i),在相同方向最大趨化步數(shù)為Nc,遷徙概率為Ped,細(xì)菌搜索維度為d。

Step 2 計(jì)算初始化細(xì)菌的f作為適應(yīng)度值J(i,g,s,l)。

Step 3 趨化行為g=g+1。

Step 4 復(fù)制行為s=s+1。

Step 5 遷徙行為l=l+1,

對細(xì)菌i=1,2,…,N,按如下方法進(jìn)行趨化循環(huán)操作。

(1)用Jlast=J(i,g,s,l)存儲當(dāng)前適應(yīng)度值。

①翻轉(zhuǎn);根據(jù)式(31)計(jì)算在細(xì)菌在趨化行為時(shí)的趨化翻轉(zhuǎn)概率。

②移動;

Ⅰ.產(chǎn)生混沌隨機(jī)序列.依據(jù)混沌系統(tǒng)的遍歷性,隨機(jī)生成混沌隨機(jī)序列幫助細(xì)菌翻轉(zhuǎn)后對方向的選擇,

由式(23)選擇初值z0=0.997 8,參數(shù)ρ=4后由混沌系統(tǒng)迭代出確定的混沌隨機(jī)序列z1,z2,z3,…。

zxi+1=ρzxi(1-zxi),i∈(0,1)

(36)

式中:ρ為混沌控制參數(shù)。

(a)搜索細(xì)菌xi的Pbestxi通過式(37)映射到式(36)Logistic方程定義域(0,1)上。

zxi=(Pbestxi-axi)/(bxi-axi)

(37)

式中:axi,bxi為節(jié)點(diǎn)坐標(biāo)范圍。

(b)通過Logistic方程zxi+1=ρzxi(1-zxi)多次迭代得到混沌序列:

zm(m=1,2,3,…)

(38)

(c)把產(chǎn)生的混沌序列通過式(25)逆映射

(39)

從而返回原解空間并產(chǎn)生一個(gè)含有混沌變量的可解混沌序列:

(40)

菌群中的細(xì)菌按此序列對搜索空間尋優(yōu)。

Ⅱ.混沌游動方向序列:

及游動步長

θi(g+1,s,l)=θi(g,s,l)+C(i)×φ(i)

來使細(xì)菌游動以尋找最優(yōu)適應(yīng)度值。其中c(i)表示細(xì)菌i翻轉(zhuǎn)后游動的步長,且當(dāng)菌落內(nèi)細(xì)菌i和j距離小于設(shè)定閾值,細(xì)菌i對細(xì)菌j產(chǎn)生反彈作用,使其各自向食物感知系數(shù)大的方向遷徙,sij表示細(xì)菌i和j反彈后的游動距離。

(2)用θi(g+1,s,l)計(jì)算適應(yīng)度值J(i,g+1,s,l),用g計(jì)數(shù)細(xì)菌游動次數(shù),讓g=g+1.若J(i,g+1,s,l)

若g

圖4

Step 6 對細(xì)菌i=1,2,…,N,進(jìn)行Nc次趨化行為后;

②對適應(yīng)度值較差的半數(shù)細(xì)菌用交叉算子與挑選出的精英細(xì)菌進(jìn)行雜交,生成N/2個(gè)新細(xì)菌,然后用變異算子F′(i)=F(i)+Y,i=1,2,…,N對交叉操作后的一半細(xì)菌進(jìn)行變異操作后復(fù)制分裂構(gòu)成新細(xì)菌群Nnew。

Step 7 若s

Step 8 按式(35)計(jì)算概率并對每個(gè)細(xì)菌i=1,2,…,N進(jìn)行遷徙行為,讓Pself小于隨機(jī)值的細(xì)菌存活并重新分布于尋優(yōu)空間,若l

3.2 實(shí)驗(yàn)分析

在MATLAB2010b環(huán)境下使用經(jīng)典的LEACH協(xié)議仿真算法,(協(xié)議運(yùn)行步驟為:選取簇頭并形成簇、 建立時(shí)隙表和穩(wěn)定運(yùn)行。)800 m×800 m矩形區(qū)域平面隨機(jī)分布200個(gè)傳感器節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)代表菌群中的一個(gè)細(xì)菌,節(jié)點(diǎn)的監(jiān)測半徑r=50,通信距離R=100,初始化算法的各項(xiàng)參數(shù),Nre∶Nc∶Ned=5∶60∶3初始節(jié)點(diǎn)能量E0=0.5 J,趨化步長c是0.05,反彈碰壁系數(shù)α為0.05,遷徙概率為0.25,單方向翻轉(zhuǎn)最大次數(shù)為15次,實(shí)驗(yàn)結(jié)果如圖所示。圖4(a)、圖4(b)為隨機(jī)分布節(jié)點(diǎn)對監(jiān)測區(qū)域進(jìn)行覆蓋時(shí)節(jié)點(diǎn)的部署情況及覆蓋率曲線圖,圖4(c)為用BFO優(yōu)化后得到的WSN部署節(jié)點(diǎn)情況,圖4(e)為用COBFA算法優(yōu)化后得到的WSN部署節(jié)點(diǎn)情況,其中黑點(diǎn)和圓分別表示傳感器節(jié)點(diǎn)坐標(biāo)位置信息和節(jié)點(diǎn)覆蓋面積區(qū)域。

分析圖4～圖6可知,隨機(jī)節(jié)點(diǎn)部署策略中節(jié)點(diǎn)在區(qū)域分布極不均勻,出現(xiàn)覆蓋空洞的同時(shí)也存在有大量的節(jié)點(diǎn)冗余和大面積重復(fù)覆蓋,節(jié)點(diǎn)覆蓋率為91.15%,經(jīng)過細(xì)菌覓食算法優(yōu)化節(jié)點(diǎn)部署休眠冗余覆蓋度大的節(jié)點(diǎn)后節(jié)點(diǎn)覆蓋比較均勻,減少了重復(fù)覆蓋區(qū)域,但仍然存在較多的冗余節(jié)點(diǎn)和覆蓋空洞,其覆蓋率為96.71%。在用混沌優(yōu)化的細(xì)菌覓食算法得到的節(jié)點(diǎn)覆蓋方案中WSN節(jié)點(diǎn)在監(jiān)測區(qū)域中均勻分布,休眠冗余覆蓋度大的節(jié)點(diǎn)后,幾乎不產(chǎn)生節(jié)點(diǎn)冗余,并且覆蓋率能夠到98.97%,幾乎沒有覆蓋空洞。與隨機(jī)部署節(jié)點(diǎn)的策略比較,通過混沌序列優(yōu)化細(xì)菌覓食算法得到節(jié)點(diǎn)部署策略網(wǎng)絡(luò)覆蓋率提高了7.82%,節(jié)點(diǎn)在監(jiān)測區(qū)域分布更加均勻,重復(fù)覆蓋的區(qū)域更少,節(jié)點(diǎn)的冗余度極低,達(dá)到了WSN優(yōu)化覆蓋的目的,而且優(yōu)化的算法使用更少的節(jié)點(diǎn)就能有效覆蓋監(jiān)測區(qū)域,節(jié)約了部署成本,同時(shí)也極大地延長了WSN的監(jiān)測時(shí)間。

由表1可知,混沌優(yōu)化過的細(xì)菌覓食節(jié)點(diǎn)部署策略其網(wǎng)絡(luò)平均覆蓋率高于其他對比算法,且使用的節(jié)點(diǎn)個(gè)數(shù)少于其他節(jié)點(diǎn)部署算法,節(jié)點(diǎn)的利用率、能量平衡性優(yōu)于其他節(jié)點(diǎn)部署算法且搜索最優(yōu)覆蓋策略的速度最快,通過互相對比發(fā)現(xiàn),COBFO優(yōu)化算法能夠有效提高節(jié)點(diǎn)的利用率、網(wǎng)絡(luò)覆蓋率、降低節(jié)點(diǎn)能量消耗及延長網(wǎng)絡(luò)生存壽命。

圖5 生存周期對比曲線

圖6 節(jié)點(diǎn)剩余能量對比曲線

表1 部署策略比較

4 結(jié)束語

本文針對監(jiān)測區(qū)域節(jié)點(diǎn)隨機(jī)部署時(shí)網(wǎng)絡(luò)存在冗余覆蓋面積大、能量不均勻消耗及細(xì)菌覓食未優(yōu)化算法存在的易陷入?yún)^(qū)域局部最優(yōu)、后期搜索速率慢等缺陷,用混沌理論對原始細(xì)菌覓食算法改進(jìn)后優(yōu)化WSN覆蓋。仿真表明,改進(jìn)的節(jié)點(diǎn)部署策略與節(jié)點(diǎn)隨機(jī)部署覆蓋策略及未優(yōu)化的細(xì)菌覓食算法部署策略比較,通過改進(jìn)算法得到的WSN節(jié)點(diǎn)部署策略有著較高網(wǎng)絡(luò)覆蓋率及節(jié)點(diǎn)綜合利用率,增加算法的搜索能力和探索速度,有效地增強(qiáng)搜索的精確性,能夠?qū)崿F(xiàn)優(yōu)化節(jié)點(diǎn)覆蓋、節(jié)約節(jié)點(diǎn)能量、提高WSN覆蓋率,大幅降低節(jié)點(diǎn)重復(fù)覆蓋面積及節(jié)點(diǎn)冗余度,提高WSN的監(jiān)測時(shí)間。

[1] Singh M,Khilar P M. A Range Free Geometric Technique for Localization of Wireless Sensor Network(WSN)Based on Controlled Communication Range[J]. Wireless Personal Communications,2016:1-27.

[2] 牛玉剛,杜國杰,賈廷綱. 一種基于能耗均衡的分區(qū)節(jié)點(diǎn)部署算法[J]. 控制與決策,2016,31(6):1021-1026.

[3] 張夢蓓,喬帥. WSN中節(jié)點(diǎn)分布的協(xié)方差矩陣自適應(yīng)優(yōu)化策略[J]. 儀表技術(shù)與傳感器,2016(2):83-86.

[4] 范政武,王鐵,陳峙. 基于人工魚群算法的車輛平順性優(yōu)化分析[J]. 農(nóng)業(yè)工程學(xué)報(bào),2016,32(6):107-114.

[5] 丁旭,吳曉蓓,黃成. 基于改進(jìn)粒子群算法和特征點(diǎn)集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J]. 電子學(xué)報(bào),2016,44(4):967-973.

[6] 黃帥,程良倫. 一種基于虛擬力的有向傳感器網(wǎng)絡(luò)低冗余覆蓋增強(qiáng)算法[J]. 傳感技術(shù)學(xué)報(bào),2011,24(3):418-422.

[7] Kwon O M,Park M J,Ju H P,et al. Script H∞Synchronization of Chaotic Neural Networks with Time-Varying Delays[J]. Chinese Physics B,2013,46(11):244-252.

[8] 陳躚. 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位算法研究[D]. 重慶:重慶大學(xué),2014.

[9] 馬學(xué)森,曹政,韓江洪,等. 改進(jìn)蟻群算法的無線傳感器網(wǎng)絡(luò)路由優(yōu)化與路徑恢復(fù)算法[J]. 電子測量與儀器學(xué)報(bào),2015,29(9):1320-1327.

[10] 王成成. 基于蒙特卡洛方法的移動無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D]. 山東大學(xué),2014.

[11] 趙玫,楊洪勇,李路偉. 基于權(quán)重的目標(biāo)覆蓋控制算法[J]. 控制與決策,2014(10):1845-1850.

[12] 張品,王佳佳,占夢. 能量高效的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(12):1919-1923.

[13] 胡楠,吳成東,于曉升,等. 基于C-V模型的網(wǎng)絡(luò)覆蓋空洞探測與修復(fù)算法[J]. 控制與決策,2016,31(8):1424-1428.

[14] 于春娣,丁勇,李偉,等. 一種能量有效的WSN目標(biāo)跟蹤動態(tài)協(xié)同自組織算法[J]. 傳感技術(shù)學(xué)報(bào),2012,25(11):1577-1583.

[15] 姜建國,周佳薇,周潤生,等. 一種采用改進(jìn)細(xì)菌覓食優(yōu)化算法的圖像增強(qiáng)方法[J]. 控制與決策,2015(3):461-466.

[16] Zhang Z,Li J X,Liu L. Distributed State Estimation and Data Fusion in Wireless Sensor Networks Using Multi-Level Quantized Innovation[J]. Science China Information Sciences,2016,59(2):1-15.

[17] 王偉,朱娟娟,萬家山,等. 基于混沌量子粒子群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J]. 傳感技術(shù)學(xué)報(bào),2016,29(2):290-296.

[18] 周文宏,雷欣,姜建國,等. 變概率混合細(xì)菌覓食優(yōu)化算法[J]. 系統(tǒng)工程與電子技術(shù),2016,38(4):960-964.

[19] 蔣鵬,王興民. 網(wǎng)絡(luò)分層的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法[J]. 電子學(xué)報(bào),2016,44(5):1240-1246.