袁　曦， 張曦煌

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

?

基于改進蝙蝠算法的無線傳感器網(wǎng)絡(luò)的移動節(jié)點部署*

袁曦， 張曦煌

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

摘要:針對傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(WSNs)中存在的移動節(jié)點部署的分布不均勻、網(wǎng)絡(luò)覆蓋度太低等各種問題，提出了一種基于改進蝙蝠算法(BA)的移動節(jié)點部署策略，通過蝙蝠算法的收斂特性，不斷迭代尋求問題的最優(yōu)解，從而不斷優(yōu)化傳感器節(jié)點的部署。Matlab仿真表明:提出的算法可以顯著改善傳感器節(jié)點的覆蓋密度，并且節(jié)點分布也相對比較均勻。

關(guān)鍵詞:蝙蝠算法； 無線傳感器網(wǎng)絡(luò)； 移動節(jié)點部署

0引言

無線傳感器網(wǎng)絡(luò)(WSNs)是由大量成本低、處理能力有限、能量資源受限的無線傳感器節(jié)點組成[1,2]。節(jié)點通過一定的部署方法自組織形成網(wǎng)絡(luò)，實現(xiàn)對目標(biāo)區(qū)域的有效監(jiān)控。而合適的網(wǎng)絡(luò)部署對于無線傳感器網(wǎng)絡(luò)來說是至關(guān)重要的，良好的網(wǎng)絡(luò)布局可以顯著提高網(wǎng)絡(luò)節(jié)點覆蓋率、減少全局網(wǎng)絡(luò)能量損耗、增加網(wǎng)絡(luò)健壯性等。

目前已有很多對無線傳感器網(wǎng)絡(luò)移動節(jié)點部署相關(guān)的報導(dǎo)：文獻[2]基于改進蛙跳算法提出新的策略，在一定程度上增加網(wǎng)絡(luò)覆蓋度，文獻[3]針對蛙跳算法容易陷入局部最優(yōu)解而提出基于虛擬力的改進蛙跳算法，文獻[4，5]則通過改進魚群算法優(yōu)化移動節(jié)點部署。

本文基于改進蝙蝠算法(BA)，通過尋求最優(yōu)解的過程，使網(wǎng)絡(luò)節(jié)點部署均勻，改善網(wǎng)絡(luò)節(jié)點覆蓋度，優(yōu)化網(wǎng)絡(luò)能耗。

1蝙蝠算法簡介

蝙蝠算法是劍橋大學(xué)的學(xué)者Yang提出的一種基于模擬自然界蝙蝠通過超聲波進行搜索的群智能優(yōu)化算法[6～12]。在蝙蝠算法中，將待優(yōu)化問題的解作為搜索空間中的一個蝙蝠，每個蝙蝠都有其對應(yīng)的適應(yīng)度值，蝙蝠群體通過調(diào)整頻率、響度、脈沖發(fā)射率，追隨當(dāng)前最優(yōu)蝙蝠在解空間中進行搜索。大量研究結(jié)果表明：相對于粒子群算法、 遺傳算法等群智能算法，蝙蝠算法可以動態(tài)控制局部搜索和全局搜索間的相互轉(zhuǎn)換過程，較好地避免算法陷入局部最優(yōu)解。

2基于蝙蝠算法的無線傳感器網(wǎng)絡(luò)節(jié)點部署策略

2.1無線傳感器網(wǎng)絡(luò)節(jié)點部署模型

現(xiàn)在假定在一個二維平面區(qū)域M2={(x,y),0≤x≤m,0≤y≤m}中，開始隨機布置n個傳感器節(jié)點，n個節(jié)點集合可以表示為w=(C1,C2,…,Cn)；對于特定節(jié)點Ck，其位置可以通過一定手段定位獲得，現(xiàn)假設(shè)其位置表示為PCk=(xk,yk)，節(jié)點的感知半徑為r，即每個節(jié)點的覆蓋模型是以節(jié)點坐標(biāo)為圓心，r為半徑的圓。

若目標(biāo)位置為P=(x,y)，則對于節(jié)點PCk，其與目標(biāo)的距離為

(1)

節(jié)點PCk對目標(biāo)P的覆蓋度為

(2)

對于目標(biāo)P，被所有節(jié)點聯(lián)合檢測到的概率為

p(C)=1-∏(1-Fxy(P,PCk)),

(3)

則無線傳感器網(wǎng)絡(luò)節(jié)點覆蓋率為

(4)

對于所有傳感器節(jié)點，假設(shè)相鄰節(jié)點最大距離和最小距離為Dmax和Dmin，則節(jié)點相對部署均勻度為

E(w)=Dmin/Dmax.

(5)

顯然，若E(w)越大，則所有傳感器節(jié)點之間部署相對比較均勻。

通過式(4)和式(5),可以得到算法目標(biāo)方程

FM(w)=αR(w)+βE(w).

(6)

其中,α和β為權(quán)值影響因子。

2.2改進的蝙蝠算法

在傳統(tǒng)的蝙蝠算法中，蝙蝠的位置和蝙蝠的飛行速度都是隨機生成，未考慮位置和速度的相關(guān)性，故存在一定缺陷，本文通過引進權(quán)值因子來改進蝙蝠算法。

假設(shè)某個蝙蝠初始位置是P，其初始速度為v0(i)，初始速度計算為：

假設(shè)二維平面區(qū)域中心為P0=(x0,y0),則蝙蝠與中心的距離為D

(7)

(8)

故

(9)

式中V為速度常量。

2.3部署策略

故通過蝙蝠算法和無線傳感器網(wǎng)絡(luò)節(jié)點網(wǎng)絡(luò)模型，節(jié)點部署優(yōu)化策略如下：

1)初始化節(jié)點個數(shù)和蝙蝠的個數(shù)。

2)隨機初始化節(jié)點的位置，從而獲取每個蝙蝠的信息。

3)根據(jù)設(shè)定的目標(biāo)方程計算得到最優(yōu)蝙蝠，并通過最優(yōu)蝙蝠更新所有節(jié)點的位置和速度，更新公式如下

38%吡唑醚菌酯·啶酰菌胺水分散粒劑將2種不同作用機制的藥劑混配，畝用藥80 g，2年對黃瓜灰霉病的防治效果分別為80.16%和80.14%，說明該藥劑對黃瓜灰霉病的防治效果優(yōu)良，是防治黃瓜灰霉病的良好藥劑。在黃瓜灰霉病發(fā)病初期施用第一次藥，以后每隔7天用藥一次，連續(xù)施藥3次。以噴霧方式施用，使用制劑量40-80 g/畝為宜，可有效地控制黃瓜灰霉病發(fā)生蔓延，也可考慮和其它類型殺菌劑交替使用。

fi=fmin+(fmax-fmin)β,

(10)

(11)

(12)

4)對于最優(yōu)蝙蝠，采取隨機更新方式更新蝙蝠位置和速度，并更新蝙蝠響度和頻度。

具體更新策略如下：

1)產(chǎn)生一個隨機數(shù)rand1,如果rand1>ri(ri為第i只蝙蝠的脈沖頻度),則對當(dāng)前最優(yōu)蝙蝠位置進行隨機擾動得到新的位置，然后替換原位置。

2)產(chǎn)生一個隨機數(shù)rand2，如果rand2>Ai(Ai為第i只蝙蝠的脈沖音強),并且f(bfi)>f(BF)(BF為當(dāng)前最優(yōu)蝙蝠)，則移動至更新后的位置。

3) 當(dāng)滿足步驟(2)條件，則根據(jù)式(13)和式(14)更新脈沖頻度r和脈沖音強A

(13)

(14)

其中,t為迭代輪數(shù)，γ為脈沖頻度增加系數(shù)，α為脈沖音強衰減系數(shù)。

4)若達到迭代次數(shù)或達到精度要求，則退出蝙蝠算法；否則，回到步驟(3)。

5)輸出最優(yōu)節(jié)點部署。

3仿真結(jié)果與分析

實驗仿真環(huán)境如下：實驗選擇在50m×50m的正方形區(qū)域內(nèi)隨機分布25個節(jié)點，傳感器節(jié)點感知半徑r為5m，通信半徑為2 r，蝙蝠數(shù)目為20，區(qū)域被均勻分成2 500個粒子，蝙蝠發(fā)出的脈沖頻率范圍[-1，1],最大脈沖頻度r0=0.75，最大脈沖音強A=0.25，脈沖頻度增加系數(shù)γ=0.05，脈沖音強衰減系數(shù)α=0.95。

實驗中，隨機生成25個傳感器節(jié)點，由圖可以看出初始的節(jié)點部署相對比較擁擠，分布不均勻，區(qū)域覆蓋面積比較低，如圖1。

圖1　隨機分布的傳感器節(jié)點Fig 1　Randomly distributed sensor node

通過Matlab模擬，算法在運行50輪時，所有傳感器節(jié)點分布如圖2所示。

圖2　算法運行50輪時節(jié)點部署Fig 2　Node deployment while algotithm is operating 50 round

算法在運行100輪時，所有傳感器節(jié)點分布如圖3所示。

圖3　算法運行100輪時節(jié)點部署Fig 3　Node deployment while algorithm is operating 100 round

算法在運行150輪時，所有傳感器節(jié)點分布如圖4所示。

圖4　算法運行150輪時節(jié)點部署Fig 4　Node deployment while algorithm is operating 150 round

從圖2～圖4可以看出:隨著算法的不斷迭代，傳感器節(jié)點開始慢慢分散，重合度開始降低，范圍覆蓋度上升，說明算法對于無線傳感器網(wǎng)絡(luò)的移動節(jié)點部署可以在一定程度上進行優(yōu)化，從而改善網(wǎng)絡(luò)環(huán)境。

在相同面積區(qū)域和同等初始部署情況下,實驗對于本文算法和基于蛙跳算法進行了5組實驗,實驗結(jié)果取5次平均結(jié)果,比較數(shù)據(jù)和圖表如表1和圖5。

表1　不同算法對比結(jié)果

圖5　不同算法覆蓋率隨迭代次數(shù)比較Fig 5　Comparison of coverage rate of different algorithms with iterations

從表1和圖5中可以看出:改進蝙蝠算法得到的覆蓋率較基于蛙跳算法有所提高， 這有效地提高了節(jié)點的覆蓋范圍，并且從表1中可以看出，本文算法的執(zhí)行效率也較基于蛙跳算法的有所提高。

4結(jié)束語

本文通過分析傳統(tǒng)無線傳感器網(wǎng)絡(luò)節(jié)點部署的一些缺點，提出了基于蝙蝠算法的網(wǎng)絡(luò)節(jié)點部署優(yōu)化算法。新算法通過給定的目標(biāo)方程不斷迭代，最終尋求最優(yōu)解，獲得最優(yōu)節(jié)點部署。實驗仿真結(jié)果表明：算法顯著改善了網(wǎng)絡(luò)節(jié)點部署，使節(jié)點部署更加均勻，網(wǎng)絡(luò)覆蓋度也明顯增加。

參考文獻:

[1]Heinzelman W,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2]龍騰，孫輝，趙嘉.基于改進蛙跳算法的WSNs移動節(jié)點部署研究[J].計算機工程，2012,38(5):96-98.

[3]徐躍州,張欣.無線傳感器網(wǎng)絡(luò)的虛擬力蛙跳優(yōu)化布局策略[J].傳感器與微系統(tǒng)，2014,33(6):49-51.

[4]廖燦星,張平,李行善,等.基于混合人工魚群算法的傳感器網(wǎng)絡(luò)優(yōu)化[J].北京航空航天大學(xué)學(xué)報，2010,36(3):373-377.

[5]周利民,楊科華,周攀.基于魚群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略[J]． 計算機應(yīng)用研究,2010,27(6):2276-2279.

[6]盛曉華,葉春明.蝙蝠算法在PFSP調(diào)度問題中的應(yīng)用研究[J].工業(yè)工程,2013,16(1):119-124.

[7]孫文捷,張惠珍,張健,等.基于Fuch映射的混沌蝙蝠算法[J].上海理工大學(xué)學(xué)報,2014(1):26-30.

[8]凌遠雄,葉春明,郭迎迎.改進蝙蝠算法在Job-shop調(diào)度問題上的應(yīng)用[J].科技與管理,2014(1):37-40，61.

[9]盛孟龍,賀興時,王慧敏.一種改進的自適應(yīng)變異蝙蝠算法[J].計算機技術(shù)與發(fā)展,2014(10):131-134.

[10] 李枝勇,馬良,張惠珍.蝙蝠算法在多目標(biāo)多選擇背包問題中的應(yīng)用[J].計算機仿真,2013(10):350-353.

[11] 王戰(zhàn)備.基于蝙蝠算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J].計算機工程與應(yīng)用,2014，50(11):90-94.

[12] 劉長平,葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及其性能仿真[J].系統(tǒng)仿真學(xué)報,2013,25 (6):1183-1188.

Mobile node deployment of WSNs on improved bat algorithm*

YUAN Xi, ZHANG Xi-huang

(School of IOT Engineering,Jiangnan University,Wuxi 214122，China)

Abstract:Aiming at problems that in traditional wireless sensor networks(WSNs) distribution of mobile node deployment is uneven and low coverage of networks,propose a mobile node deployment strategy based on improved bat algorithm (BA),through convergence properties of BA constantly iterat,seek the optimal solution,so as to optimize deployment of sensor node constanrly.Matlab simulation shows that,this algorithm can improve coverage density of node and node distribution is homogeneous.

Key words:bat algorithm(BA); WSNs; mobile node deployment

DOI:10.13873/J.1000—9787(2016)03—0144—03

收稿日期：2015—06—11

*基金項目：國家自然科學(xué)基金資助項目(61170120)

中圖分類號:TN 393

文獻標(biāo)識碼:A

文章編號:1000—9787(2016)03—0144—03

作者簡介:

袁曦(1991-)，男，江蘇泰興人，碩士研究生，主要研究領(lǐng)域為無線傳感器網(wǎng)絡(luò)、人工智能計算。