基于改進蝙蝠算法的無線傳感器網絡的移動節點部署*

袁　曦， 張曦煌

(江南大學 物聯網工程學院，江蘇 無錫 214122)

?

基于改進蝙蝠算法的無線傳感器網絡的移動節點部署*

袁曦， 張曦煌

(江南大學 物聯網工程學院，江蘇 無錫 214122)

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

關鍵詞:蝙蝠算法； 無線傳感器網絡； 移動節點部署

0引言

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

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

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

1蝙蝠算法簡介

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

2基于蝙蝠算法的無線傳感器網絡節點部署策略

2.1無線傳感器網絡節點部署模型

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

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

(1)

節點PCk對目標P的覆蓋度為

(2)

對于目標P，被所有節點聯合檢測到的概率為

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

(3)

則無線傳感器網絡節點覆蓋率為

(4)

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

E(w)=Dmin/Dmax.

(5)

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

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

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

(6)

其中,α和β為權值影響因子。

2.2改進的蝙蝠算法

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

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

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

(7)

(8)

故

(9)

式中V為速度常量。

2.3部署策略

故通過蝙蝠算法和無線傳感器網絡節點網絡模型，節點部署優化策略如下：

1)初始化節點個數和蝙蝠的個數。

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

3)根據設定的目標方程計算得到最優蝙蝠，并通過最優蝙蝠更新所有節點的位置和速度，更新公式如下

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

fi=fmin+(fmax-fmin)β,

(10)

(11)

(12)

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

具體更新策略如下：

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

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

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

(13)

(14)

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

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

5)輸出最優節點部署。

3仿真結果與分析

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

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

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

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

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

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

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

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

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

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

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

表1　不同算法對比結果

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

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

4結束語

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

參考文獻:

[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移動節點部署研究[J].計算機工程，2012,38(5):96-98.

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

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

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

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

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

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

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

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

[11] 王戰備.基于蝙蝠算法的無線傳感器網絡節點定位[J].計算機工程與應用,2014，50(11):90-94.

[12] 劉長平,葉春明.具有混沌搜索策略的蝙蝠優化算法及其性能仿真[J].系統仿真學報,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

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

中圖分類號:TN 393

文獻標識碼:A

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

作者簡介:

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