基于Lévy飛行特征的蝙蝠算法及其在WSN定位中的應(yīng)用*

石 浩,王萬良,李燕君,盧良進(jìn)

(浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

?

基于Lévy飛行特征的蝙蝠算法及其在WSN定位中的應(yīng)用*

石 浩,王萬良*,李燕君,盧良進(jìn)

(浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

針對蝙蝠算法收斂易早熟、收斂速度慢等不足,提出一種改進(jìn)的基于Lévy飛行特征自適應(yīng)的蝙蝠算法。采用Lévy飛行策略取代原算法中蝙蝠飛行速度和位置的更新方式,充分利用Lévy飛行的重尾效應(yīng),有效避免局部最優(yōu)值的吸引,加快了收斂速度,達(dá)到尋優(yōu)能力和搜索能力的平衡。在無線傳感器網(wǎng)絡(luò)自身定位應(yīng)用中,把定位問題轉(zhuǎn)換為一個全局優(yōu)化問題,使用改進(jìn)的算法進(jìn)行定位計算。通過Zigbee平臺的實(shí)驗(yàn)表明,改進(jìn)后的算法在不同空間位置的定位精度更高,收斂速度更快。算法實(shí)現(xiàn)條件簡單、精度高,具有較高的實(shí)際工程應(yīng)用價值。

無線傳感器網(wǎng)絡(luò);RSSI;定位算法;蝙蝠算法;Lévy飛行

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)是由分布在監(jiān)控區(qū)域內(nèi)的許多廉價傳感器節(jié)點(diǎn)組成,采用無線通信的方式組成的一個多跳自組織的網(wǎng)絡(luò)系統(tǒng),具備監(jiān)測、感知、采集和處理等功能[1]。近年來,WSN作為物聯(lián)網(wǎng)產(chǎn)業(yè)的核心技術(shù)日益受到研究者的重視,在室內(nèi)導(dǎo)航、火災(zāi)定位、安保系統(tǒng)和健康監(jiān)護(hù)等應(yīng)用中有著研究。在一些實(shí)際應(yīng)用中,節(jié)點(diǎn)的位置都是隨機(jī)并且未知的,節(jié)點(diǎn)所采集到的數(shù)據(jù)必須結(jié)合其位置信息才有意義。因此,實(shí)現(xiàn)節(jié)點(diǎn)的自身定位對無線傳感器網(wǎng)絡(luò)具有重要意義。

WSN的定位技術(shù)分為兩類算法:測距的定位算法(Range-based)和無需測距的定位算法(Range-free)[2]。測距的定位算法通過使用復(fù)雜的硬件設(shè)備獲取節(jié)點(diǎn)之間的距離和角度,來計算定位信息,如TOA(到達(dá)時間法)、TDOA(到達(dá)時間差)、AOA(達(dá)到的角度),RSSI(信號強(qiáng)度指示值)算法等;無需測距的定位算法是利用WSN的網(wǎng)絡(luò)連通性來計算距離,雖然不能精確得到節(jié)點(diǎn)間準(zhǔn)確的距離,但是由于使用的設(shè)備簡單、成本低,使此類算法有著廣泛的應(yīng)用[3],如質(zhì)心定位、DV-Hop[4]、APIT[5]、MDS-MAP[6]等算法。文獻(xiàn)[7]提出在煤礦井下應(yīng)用中使用改進(jìn)的RSSI指紋定位匹配算法,使用K鄰近算法和最短歷史路徑匹配法,利用機(jī)車速度對定位算法精度進(jìn)行修正。文獻(xiàn)[8]提出改進(jìn)的DV-Hop定位算法,使用自適應(yīng)蜂群算法計算未知節(jié)點(diǎn)坐標(biāo),提高了定位精度和精度穩(wěn)定性。文獻(xiàn)[9]比較了遺傳算法和人工蜂群算法在WSN中的應(yīng)用,得出人工蜂群算法在WSN定位中可以得到比遺傳算法更佳的精度。文獻(xiàn)[10]提出改進(jìn)的蝙蝠算法,通過調(diào)整聲音響度和脈沖發(fā)射頻率來提高尋優(yōu)性能。由于蝙蝠算法的局部搜索性能優(yōu)于全局搜索性能[11],這個算法只改進(jìn)了蝙蝠算法的局部搜索性能,對全局搜索性能沒有改進(jìn)。文獻(xiàn)[12]提出了具有Lévy飛行特征的蝙蝠算法,修改了蝙蝠個體位置更新的公式,使用Lévy飛行特征產(chǎn)生蝙蝠個體的新位置,改進(jìn)了蝙蝠算法的全局搜索性能。由于在最優(yōu)解附近通過Lévy飛行產(chǎn)生的新解,會與局部最優(yōu)解相距較遠(yuǎn),反復(fù)的搜索運(yùn)算降低了算法的效率。本文在基本的蝙蝠算法上使用Lévy飛行隨機(jī)游走的特性拓展了搜索的空間,加快了算法的收斂速度,提出蝙蝠個體基于Lévy飛行自適應(yīng)的位置更新方法,提高了蝙蝠算法的全局搜索性能,使全局搜索能力和局部搜索能力達(dá)到平衡。

1 WSN定位算法模型

1.1 基于RSSI的WSN測距模型

無線電波的發(fā)射功率具有隨著距離增加而衰減的特性,無線電波在自由空間中傳播,自由空間傳播模型為[13]:

(1)

式中:Pr為信號接收功率,Pt為信號發(fā)送功率,Gt為發(fā)射天線增益,Gr為接收天線增益,λ為波長,d為發(fā)射端和接收端之間的距離。式(1)表明隨著發(fā)射距離的增加,接收功率指數(shù)倍下降。無線電波的自由空間傳播模型的對數(shù)模型為:

Pl(d)=Pl(d0)-10×n×log(d/d0)+Xp

(2)

式中:Pl(d)為距離為d時信號的接收功率;d0為參考距離,一般為1m;Xp為平均值為零的高斯分布隨機(jī)變量。n為路徑損耗指數(shù),不同環(huán)境和不同天線有不同的值,通常在2到4之間。在實(shí)際應(yīng)用中,為了達(dá)到較好的測距精度,需要測量環(huán)境中的路徑損耗指數(shù)。

1.2 基于RSSI的定位算法模型

假設(shè)在自由空間區(qū)域,信標(biāo)節(jié)點(diǎn)A、B、C、D和未知節(jié)點(diǎn)N組成無線傳感器網(wǎng)絡(luò),如圖1所示。

圖1 信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)的示意圖

圖1中:信標(biāo)節(jié)點(diǎn)A、B、C、D的坐標(biāo)分別為(xA,yA)、(xB,yB)、(xC,yC)和(xD,yD);信標(biāo)節(jié)點(diǎn)A、B、C、D和未知節(jié)點(diǎn)N(x,y)的距離分別為:dA、dB、dC、dD。文獻(xiàn)[8]和文獻(xiàn)[9]通過遺傳算法和蜂群算法的將定位問題轉(zhuǎn)換為全局優(yōu)化問題,求的未知節(jié)點(diǎn)N的坐標(biāo),文獻(xiàn)中使用的適應(yīng)度函數(shù)為:

(3)

式中:(x,y)為未知節(jié)點(diǎn)坐標(biāo);(xi,yi)為信標(biāo)節(jié)點(diǎn)坐標(biāo);n表示信標(biāo)節(jié)點(diǎn)數(shù)量;di是根據(jù)無線電波與距離衰減模型映射的距離;求得的最小值minf(x,y)即為最優(yōu)解。

在實(shí)際環(huán)境中,信號接收端接收的信號強(qiáng)度(RSS)和距離的并不是線性關(guān)系,某實(shí)際環(huán)境中RSS和距離的曲線如圖2所示。

圖2 實(shí)際環(huán)境中RSS與傳輸距離的曲線

圖2中,信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)距離小時,曲線線性好;距離大時,曲線線性差,并且標(biāo)準(zhǔn)差也較大。說明:節(jié)點(diǎn)距離越大,對定位精度的影響越大。在式(3)中,沒有考慮不同節(jié)點(diǎn)距離對定位精度的影響。為了提高適應(yīng)度函數(shù)的準(zhǔn)確性,在適應(yīng)度函數(shù)中增加距離的倒數(shù)作為權(quán)重系數(shù),如式(4)所示。

(4)

2 基于Lévy飛行特征的蝙蝠算法

2.1 蝙蝠算法描述

近年來,具有自然進(jìn)化思想的元啟發(fā)式算法(Meta-heuristicAlgorithms)掀起了國內(nèi)外科學(xué)家研究的熱潮。元啟發(fā)式算法的思想是人們在長期的生產(chǎn)實(shí)踐中,對物理、生物、社會等現(xiàn)象經(jīng)過長期觀察和深入研究,模擬自然現(xiàn)象的運(yùn)行機(jī)制得到的知識結(jié)晶。新型元啟發(fā)式算法例如蟻群優(yōu)化算法、螢火蟲算法、布谷鳥搜索算法、和聲搜索算法已經(jīng)成為現(xiàn)今復(fù)雜的優(yōu)化問題的有效解決方法。

蝙蝠算法[14]BA(BatAlgorithm)是由劍橋大學(xué)的Xin-SheYang在2010年提出的一種新的元啟發(fā)式優(yōu)化算法。蝙蝠算法是模擬蝙蝠回聲定位行為,采用不同的脈沖發(fā)射頻率和響度,通過全局搜索的辦法找到最優(yōu)解。蝙蝠算法已經(jīng)逐漸在各個應(yīng)用領(lǐng)域中受到學(xué)者的重視,針對蝙蝠算法全局搜索能力不佳的缺點(diǎn),有許多文獻(xiàn)展開研究。文獻(xiàn)[15]提出了使用蝙蝠算法優(yōu)化電力系統(tǒng)穩(wěn)定性的問題(PSS)。文獻(xiàn)[16]提出在蝙蝠算法中使用模擬退火和的高斯擾動算法,對蝙蝠個體進(jìn)行高斯擾動,增加了全局搜索性能。

2.2 改進(jìn)的Lévy飛行特征的蝙蝠算法

Lévy飛行的數(shù)學(xué)模型是由法國數(shù)學(xué)家PaulLévy提出,它是一種馬爾可夫過程,行走的步長滿足重尾(Heavy-tailed)分布[17],步長μ和出現(xiàn)的頻率P(μ)的公式為:

P(μ)=μ-λ, 1<λ<3

(5)

Viswanathan經(jīng)過研究發(fā)現(xiàn),Lévy飛行現(xiàn)象在自然界很普遍,如螞蟻或果蠅等動物搜索食物的行走路徑[18],甚至是人在戶外的某些活動路徑也服從Lévy分布[19]。在大范圍的搜索的過程中,Lévy飛行比布朗隨機(jī)運(yùn)動更佳有效[20],Lévy飛行在搜索過程中會產(chǎn)生較大跳躍,并且方向會急劇變化,這樣可以使智能算法跳出局部最優(yōu)。特別在高維復(fù)雜空間中,通過Lévy飛行擴(kuò)大搜索空間,能夠有效提高算法的收斂速度。Lévy飛行1000步的二維軌跡如圖3所示,圖中“○”表示起點(diǎn),“☆”表示終點(diǎn)。

圖3 Lévy飛行軌跡

基于Lévy飛行特征的蝙蝠算法的主要計算過程如下:

步驟1:定義適應(yīng)度函數(shù)f(x),x=(x1,x2,…,xd)T,其中d為維數(shù),x為蝙蝠個體的位置,f(x)的最優(yōu)解就是蝙蝠個體找到獵物的位置;

步驟2:初始化蝙蝠種群位置xi(i=1,2,3,…,n)(n為種群數(shù)量)和飛行速度vi;

步驟3:定義蝙蝠個體在位置xi的頻率fi;

步驟4:定義蝙蝠發(fā)出的音量Ai、脈沖發(fā)生率ri、迭代次數(shù)。通常為了簡易計算,音量和脈沖發(fā)生率都設(shè)為常數(shù)0.5;

步驟5:通過調(diào)整頻率產(chǎn)生新的新的位置(新解),并且更新位置xi和速度vi。

fi=fmin+(fmax-fmin)β

(6)

式中:fmax和fmin是聲音頻率的最大和最小值;β∈[0,1]是一個服從均勻分布的隨機(jī)向量。

vt=vt-1+(xt-1-x*)f

(7)

式中:x*表示當(dāng)前全局最優(yōu)解,它是在所有n只蝙蝠搜索到的解中進(jìn)行比較而得到的位置。

xt=xt-1+vt

(8)

式(8)表示蝙蝠個體更新之后的位置。

一個優(yōu)秀的智能算法,需要達(dá)到全局搜索性能和局部搜索性能的平衡,這樣既能避免收斂早熟,又有較佳的尋優(yōu)性能[21]。傳統(tǒng)的蝙蝠算法,式(6)中β是服從均勻分布,蝙蝠個體根據(jù)布朗運(yùn)動更新位置。Lévy飛行的優(yōu)點(diǎn)在于:使用Lévy分布比使用高斯分布或者泊松分布更不易訪問到前一次的位置[22]。使用Lévy飛行策略更新蝙蝠飛行的位置,會擴(kuò)大蝙蝠個體的搜索空間,提升蝙蝠算法在高維空間的尋優(yōu)能力,避免蝙蝠個體陷入局部最優(yōu)。文獻(xiàn)[12]提出的基于Lévy飛行的蝙蝠算法,把速度和位置更新式(7)和式(8)改為:

xt=xt-1+Lévy(λ)?(xt-1-x*)

(9)

考慮到隨著迭代次數(shù)的增加,蝙蝠個體會越來越接近全局最優(yōu)解,相應(yīng)地逐步減小Lévy飛行的搜索步長,會加快算法收斂速度,改進(jìn)的算法為:

(10)

步驟6:根據(jù)音量Ai和脈沖發(fā)生率ri,判斷局部最優(yōu)解;

在每次迭代的過程中,音量Ai和脈沖發(fā)生率ri的更新公式為:

(11)

(12)

(13)

根據(jù)Ai和ri選擇局部最優(yōu)解的偽代碼如表1所示。

表1 最優(yōu)解判斷偽代碼

從最優(yōu)解集中選擇一個解,在選擇的最優(yōu)解周圍產(chǎn)生一個新解,公式為:

xnew=xold+εAt

(14)

式中:ε∈[-1,1]是一個服從均勻分布的隨機(jī)數(shù);At是所有蝙蝠在同一個時間段的平均音量;xold是當(dāng)前全局最優(yōu)解;xnew是根據(jù)當(dāng)前全局最優(yōu)解產(chǎn)生的新解。

步驟7:排列適應(yīng)度函數(shù)的數(shù)值,更新最優(yōu)解集;

步驟8:循環(huán)次數(shù)遞增,重復(fù)步驟5～步驟7;

步驟9:滿足終止條件,達(dá)到最大迭代次數(shù)。

3 實(shí)驗(yàn)和性能分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

在實(shí)際環(huán)境中進(jìn)行實(shí)驗(yàn),驗(yàn)證算法的準(zhǔn)確性。實(shí)驗(yàn)場地為一個10 m×10 m的室內(nèi)平面樓層,信標(biāo)節(jié)點(diǎn)分別放置在:A(0,0)、B(10,0)、C(0,10)和D(10,10),如圖4所示。

圖4 實(shí)驗(yàn)場地示意圖

未知節(jié)點(diǎn)N在定位區(qū)域中,向4個信標(biāo)節(jié)點(diǎn)A、B、C和D廣播信號,4個信標(biāo)節(jié)點(diǎn)收到未知節(jié)點(diǎn)的定位信號之后,讀出信號強(qiáng)度RSS并發(fā)送給信號集中器H。信號集中器通過USB傳輸線與PC機(jī)相連,將所有的定位信息以串行傳輸?shù)姆绞絺魉徒oPC。在PC機(jī)上使用定位算法進(jìn)行計算,得到未知節(jié)點(diǎn)N的坐標(biāo)。

3.2 實(shí)驗(yàn)系統(tǒng)硬件

無線傳感器節(jié)點(diǎn)采用作者自己制作的設(shè)備,分為傳感器節(jié)點(diǎn)和信號集中器,如圖5所示。傳感器節(jié)點(diǎn)既作為信標(biāo)節(jié)點(diǎn)又作為未知節(jié)點(diǎn)。信號集中器負(fù)責(zé)采集數(shù)據(jù)并上傳PC機(jī)。設(shè)備單片機(jī)采用的是德州儀器的(TI)MSP430G2452十六位微處理器,RF采用的是TI CC2500低功耗2.5 G全雙工射頻芯片。CC2500發(fā)射功率最大為0 dBm(1 mW),在2.4 K的接收速率下,接收端靈敏度為-108 dBm。節(jié)點(diǎn)設(shè)備通訊范圍為可達(dá)到50 m,非常適合構(gòu)建無線傳感器網(wǎng)絡(luò)。實(shí)驗(yàn)中使用計算機(jī)CPU配置為Intel Core i5,主頻為2.67 GHz,內(nèi)存為4 GB。

圖5 傳感器節(jié)點(diǎn)設(shè)備

3.3 平均定位誤差

平均定位誤差是評估系統(tǒng)定位性能的指標(biāo)之一,節(jié)點(diǎn)的實(shí)際位置和估算位置之間的誤差由下面的關(guān)系式計算:

(15)

式中:(xest,yest)為估算節(jié)點(diǎn)坐標(biāo),(xr,yr)為實(shí)際節(jié)點(diǎn)。

根據(jù)WSN中所有的定位結(jié)果,定義平均定位誤差:

(16)

式中:(xr,yr)為實(shí)際節(jié)點(diǎn)坐標(biāo),(xi,yi)為不同計算次數(shù)的估算坐標(biāo),n為計算次數(shù)。

3.4 實(shí)驗(yàn)結(jié)果和分析

在實(shí)驗(yàn)中,把未知節(jié)點(diǎn)放置在平面測量區(qū)域中不同的位置(中心、左下角、右上角),使用蝙蝠算法(BA)、文獻(xiàn)[12]提出的基于Lévy飛行的蝙蝠算法(LBA)和本文提出的改進(jìn)的Lévy飛行特性的蝙蝠算法(MLBA)3種算法比較節(jié)點(diǎn)在不同位置的定位性能。在不同的位置,分別使用3種算法運(yùn)行100次,記錄定位誤差。蝙蝠算法初始化參數(shù),如表2所示。

表2 蝙蝠算法參數(shù)

未知節(jié)點(diǎn)在中心,坐標(biāo)為(5,5),使用BA、LBA和MLBA算法得到的實(shí)驗(yàn)結(jié)果如圖6～圖8所示,縱坐標(biāo)表示定位誤差,橫坐標(biāo)表示未知節(jié)點(diǎn)的計算的次數(shù)。未知節(jié)點(diǎn)在左下角,坐標(biāo)為(2,2),分別使用3種算法得到的實(shí)驗(yàn)結(jié)果如圖9～圖11所示。未知節(jié)點(diǎn)在右上角,坐標(biāo)為(8,8),分別使用3種算法得到的實(shí)驗(yàn)結(jié)果如圖12～圖14所示。

圖6 BA算法定位中心節(jié)點(diǎn)的結(jié)果

圖7 LBA算法定位中心的節(jié)點(diǎn)的結(jié)果

圖8 MLBA算法定位中心節(jié)點(diǎn)的結(jié)果

圖9 BA算法定位左下角節(jié)點(diǎn)的結(jié)果

圖10 LBA算法定位左下角節(jié)點(diǎn)的結(jié)果

圖11 MLBA算法定位左下角節(jié)點(diǎn)的結(jié)果

圖12 BA算法定位右上角節(jié)點(diǎn)的結(jié)果

圖13 LBA算法定位右上角節(jié)點(diǎn)的結(jié)果

圖14 MLBA算法定位右上角節(jié)點(diǎn)的結(jié)果

圖15 尋優(yōu)迭代曲線

對于BA、LBA和MLBA算法,統(tǒng)計運(yùn)算100次的平均定位誤差、誤差均方差和平均運(yùn)行時間,實(shí)驗(yàn)結(jié)果如表3所示。

表3 BA、LBA和MLBA算法的性能比較

圖6、圖9和圖12說明:BA算法在定位不同位置節(jié)點(diǎn)的時候,都會發(fā)生最優(yōu)解被局部解吸引的情況,基于Lévy飛行特征的算法,尋優(yōu)性能優(yōu)于基本的BA算法,是由于Lévy飛行不均勻隨機(jī)游走的特性,保證了足夠的空間搜索,避免局部極值的吸引。如果定位節(jié)點(diǎn)在區(qū)域的邊緣,MLBA算法的定位精度明顯優(yōu)于BA和LBA算法,使用MLBA算法,圖11表明全部定位誤差小于1m;圖14全部定位誤差小于1.4m。表3表明,使用3種算法,運(yùn)行一樣的迭代次數(shù),時間上相差不大;MLBA算法的平均定位誤差優(yōu)于BA和LBA算法,MLBA的定位誤差的方差也優(yōu)于BA和LBA算法。

測試3種算法的尋優(yōu)效率。把定位節(jié)點(diǎn)放置在區(qū)域中心,測試迭代次數(shù)和平均定位誤差的關(guān)系,實(shí)驗(yàn)結(jié)果如圖15所示。圖15中使用BA算法迭代50次,平均定位誤差小于1.15m;使用LBA算法平均定位誤差小于0.95m;使用MLBA算法平均定位誤差小于0.51m;說明:MLAB算法的收斂速度優(yōu)于BA和LBA算法。

4 結(jié)論

為了改進(jìn)蝙蝠算法在無線傳感器的定位性能,本文提出了一種改進(jìn)的基于Lévy飛行特征的蝙蝠算法,通過修改傳統(tǒng)蝙蝠算法中蝙蝠飛行速度和位置的更新方式,使用Lévy飛行拓展搜索空間,避免最優(yōu)解陷入局部最優(yōu),加快了收斂速度。通過比較和分析,表明了MLBA算法具有更快的收斂速度和良好的尋優(yōu)性能。本文設(shè)計的系統(tǒng)實(shí)現(xiàn)簡單、成本低、運(yùn)行快,在進(jìn)行定位計算具有明顯的優(yōu)勢,在實(shí)際環(huán)境的應(yīng)用中能明顯提高節(jié)點(diǎn)定位的精度。

[1] Liu Q,Huang X H,Leng S P. Deployment Strategy of Wireless Sensor Networks for Internet of Things[J]. China Communications,2011,8(8):111-120.

[2] Chen C C,Lin T C. A Low-Cost Anchor Placement Strategy for Range-Free Localization Problems in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013,2(3):23-30.

[3] Wang S S,Shi K P,Chang C Y. Distributed Direction-Based Localization in Wireless Sensor Networks[J]. Computer Communications,2007,30(6):1424-1439.

[4] Gui L Q,Wei A. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2014,8:1-19.

[5] Xu F C,Liu Z. A New Node Self-Localization Algorithm Based RSSI for Wireless Sensor Networks[C]//Proceedings of the 5th Computational and Information Sciences(ICCIS),Shiyang,China,2013:1616-1619.

[6] Shon M,Minho J,Choo H. An Interactive Cluster-Based MDS Localization Scheme for Multimedia Information in Wireless Sensor Networks[J]. Computer Communications,2012,35(15):1921-1929.

[7] 李論,丁恩杰,郝麗娜,等. 一種改進(jìn)的煤礦井下指紋定位匹配算法[J]. 傳感技術(shù)學(xué)報,2014,27(3):388-393.

[8] 李牧東,熊偉,梁青. 基于人工蜂群改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報,2013,26(2):241-245.

[9] Wang H C,Wang Y C,Tsai M S. Performance Comparisons of Genetic Algorithm and Artificial Bee Colony Algorithm Applications for Localization in Wireless Sensor Networks[C]//Proceeding of International Conference on System Science and Engineering(ICSSE),Taipei:IEEE Press,2010:469-474.

[10] Yilmaz S,Ugur E,Cengiz Y. Modified Bat Algorithm[J]. Elektronika IR Elektrotechnika,2014,20:1392-1215.

[11] Wang G,Guo L. A Novel Hybrid Bat Algorithm with Harmony Search for Global Numerical Optimization[J]. Journal of Applied Mathematics,2013,9:21-29.

[12] 劉長平,葉春明. 具有Lévy飛行特征的蝙蝠算法[J]. 智能系統(tǒng)學(xué)報,2013,8(3):240-246.

[13] Proakis J,Salehi M. Digital Communications[M]. New York:McGraw-Hill Press,2010:165-170.

[14] Yang X S. A New Metaheuristic Bat-Inspired Algorithm[C]//Proceeding of Nature Inspired Cooperative Strategies for Optimization(NISCO 2010)[C]//Springer Berlin,2010:65-74.

[15] Ali E S. Optimization of Power System Stabilizers Using BAT Search Algorithm[J]. International Journal of Electrical Power and Energy Systems,2014,61:683-690.

[16] Shi H X,Ding W J,Yang X S. Bat Algorithm Based on Simulated Annealing and Gaussian Perturbations[J]. Neural Computing and Applications,2014,25(2):459-468.

[17] Mehrdad G,Zahra Z,Yazdan A. Computer Simulation Study of the Lévy Flight Process[J]. Physica A,2009,388:1509-1514.

[18] Viswanathan G M,Afanasyev V,Buldyrev S V,et al. Lévy Flight Search Patterns of Wandering Albatrosses[J]. Nature,1996,381:413-415.

[19] Rhee I,Shin M,Hong S,et al. On the Lévy-Walk Nature of Human Mobility[C]//Proceeding of International Conference on Computer Communications(INFOCOM 2008),Phoenix:IEEE Press,2008:924-932.

[20] Viswanathana G M,Bartumeus F,Sergey V B,et al. Lévy Fight Random Searches in Biological Phenomena[J]. Phusical A,2002,314:208-213.

[21] Selim Y,Ecir U K. Improved Bat Algorithm(IBA)on Continuous Optimization Problems[J]. Lecture Notes on Software Engineering,2013,1(3):279-283.

[22] Viswanathan G M,Afanasyev V,Buldyrev S V. Lévy Fights in Random Searches[J]. Physica A,2000,282:1-12.

[23] Kirkpatrick S,Gelatt C D,Vecchi M P. Optimization by Simulated Annealing[J]. Science,1983,220:671-680.

石 浩(1976-),男,博士研究生,浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,主要研究方向?yàn)闊o線傳感器目標(biāo)定位與跟蹤等,constr@163.com;

王萬良(1957-),男,教授,博士生導(dǎo)師,浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,研究方向?yàn)镃IMS、生產(chǎn)計劃與調(diào)度、智能自動化等,wwl@zjut.edu.cn;

李燕君(1982-),女,副教授,浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,博士,碩士生導(dǎo)師,研究方向?yàn)闊o線傳感器路由優(yōu)化,yjli@zjut.edu.cn。

Bat Algorithm Based on Lévy Flight Feature and ItsLocalization Application in WSN*

SHIHao,WANGWanliang*,LIYanjun,LULiangjin

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

Given the shortcomings of premature convergence and slow convergence speed in bat algorithm,an improved adaptive bat algorithm(BA)based on Lévy flight strategy characterized by heavy-tailed distribution is proposed,which differs traditional BA in update approach of bat’s flying velocity and positions. It could effectively keep from the algorithm into a local optimum and accelerate convergence to achieve a balance between exploration and exploitation mechanisms. In WSN applications,we converted the WSN location problems into the global optimization ones and by applying ZigBee hardware platform to compare with other algorithms in different position,a conclusion could be drawn that the improved algorithm is of quicker convergence speed and higher precision,moreover,which realizes simple condition,high accuracy with huge value of practical engineering applications.

wireless sensor network;RSSI;localization algorithm;bat algorithm;Lévy flight

項目來源:“十二五”國家科技支撐計劃項目(2012BAD10B01)

2014-11-27 修改日期:2015-03-12

C:6150P;7230

10.3969/j.issn.1004-1699.2015.06.019

TP393;TN98

A

1004-1699(2015)06-0888-07