袁　曦， 張曦煌

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

?

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

袁曦， 張曦煌

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

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

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

0引言

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

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

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

1蝙蝠算法簡(jiǎn)介

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

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

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

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

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

(1)

節(jié)點(diǎn)PCk對(duì)目標(biāo)P的覆蓋度為

(2)

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

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

(3)

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

(4)

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

E(w)=Dmin/Dmax.

(5)

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

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

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

(6)

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

2.2改進(jìn)的蝙蝠算法

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

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

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

(7)

(8)

故

(9)

式中V為速度常量。

2.3部署策略

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

1)初始化節(jié)點(diǎn)個(gè)數(shù)和蝙蝠的個(gè)數(shù)。

2)隨機(jī)初始化節(jié)點(diǎn)的位置，從而獲取每個(gè)蝙蝠的信息。

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

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

fi=fmin+(fmax-fmin)β,

(10)

(11)

(12)

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

具體更新策略如下：

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

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

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

(13)

(14)

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

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

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

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

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

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

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

通過(guò)Matlab模擬，算法在運(yùn)行50輪時(shí)，所有傳感器節(jié)點(diǎn)分布如圖2所示。

圖2　算法運(yùn)行50輪時(shí)節(jié)點(diǎn)部署Fig 2　Node deployment while algotithm is operating 50 round

算法在運(yùn)行100輪時(shí)，所有傳感器節(jié)點(diǎn)分布如圖3所示。

圖3　算法運(yùn)行100輪時(shí)節(jié)點(diǎn)部署Fig 3　Node deployment while algorithm is operating 100 round

算法在運(yùn)行150輪時(shí)，所有傳感器節(jié)點(diǎn)分布如圖4所示。

圖4　算法運(yùn)行150輪時(shí)節(jié)點(diǎn)部署Fig 4　Node deployment while algorithm is operating 150 round

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

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

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

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

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

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

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

參考文獻(xiàn):

[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]龍騰，孫輝，趙嘉.基于改進(jìn)蛙跳算法的WSNs移動(dòng)節(jié)點(diǎn)部署研究[J].計(jì)算機(jī)工程，2012,38(5):96-98.

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

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

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

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

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

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

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

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

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

[12] 劉長(zhǎng)平,葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及其性能仿真[J].系統(tǒng)仿真學(xué)報(bào),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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61170120)

中圖分類(lèi)號(hào):TN 393

文獻(xiàn)標(biāo)識(shí)碼:A

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

作者簡(jiǎn)介:

袁曦(1991-)，男，江蘇泰興人，碩士研究生，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、人工智能計(jì)算。