螢火蟲算法在WSN節(jié)點(diǎn)部署中的應(yīng)用

曹娜娜　謝智峰　穆莉　王汐存

摘要：為解決WSN隨機(jī)部署方法導(dǎo)致覆蓋率低的問題，提出了一種基于螢火蟲算法的WSN自適應(yīng)部署方法。該方法融合概率感知模型和螢火蟲算法兩種技術(shù)，建立網(wǎng)格覆蓋模型，實(shí)現(xiàn)WSN節(jié)點(diǎn)優(yōu)化部署。設(shè)計(jì)了3組仿真測試，實(shí)驗(yàn)結(jié)果表明，新方法相較于隨機(jī)部署方法，其測覆蓋率有所提升。

關(guān)鍵詞：WSN;隨機(jī)部署;螢火蟲算法;概率感知模型;網(wǎng)格覆蓋模型

中圖分類號：TP301、TP391? ? ? 文獻(xiàn)標(biāo)識碼： A

文章編號：1009-3044（2021）03-0005-03

Abstract： In order to solve the problem of low coverage caused by the random deployment method of WSN， a WSN adaptive deployment method based on the Firefly algorithm is proposed. This method fuses two technologies， the probability perception model and the firefly algorithm， to establish a grid coverage model to achieve optimal deployment of WSN nodes. Three sets of simulation tests are designed， and the experimental results show that compared with the random deployment method， the new method has improved test coverage.

Key words： WSN; random deployment; firefly algorithm; probabilistic perception model; grid coverage model

1 前言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）[1]是基于微處理、嵌入式及無線通信等技術(shù)的一種具有低功耗、低成本、自組織等特點(diǎn)的分布式信息感知、傳輸和處理系統(tǒng)。它通過網(wǎng)絡(luò)技術(shù)，實(shí)時(shí)感知、采集、處理和發(fā)布網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)檢測對象的信息。目前，WSN被廣泛應(yīng)用于軍事[2]、災(zāi)害預(yù)警[3]、空間探測[4]和環(huán)境監(jiān)測[5]等領(lǐng)域。在應(yīng)用過程中，WSN面臨的首要問題是節(jié)點(diǎn)部署，其直接影響整個(gè)網(wǎng)絡(luò)的覆蓋能力。隨機(jī)部署是最簡單的節(jié)點(diǎn)部署方式，但該方式易使眾多節(jié)點(diǎn)聚集，節(jié)點(diǎn)無法均勻部署，導(dǎo)致監(jiān)測區(qū)域盲區(qū)較多，從而影響整個(gè)WSN監(jiān)測性能。為了克服隨機(jī)部署方式存在的缺點(diǎn)，因此，需要設(shè)計(jì)一種自適應(yīng)調(diào)整的WSN部署方法。該方法可以根據(jù)監(jiān)測區(qū)域的變化，動(dòng)態(tài)地調(diào)整傳感器的位置，減少區(qū)域覆蓋盲點(diǎn)，提高WSN 覆蓋率。

群體智能算法（Swarm Intelligence Algorithm， SIA）是一種仿生優(yōu)化技術(shù)，可用于解決各種具有高維、多模和不可微等特性的復(fù)雜問題。典型的算法有粒子群算法（Particle Swarm Optimization， PSO）[6-7] 、蜂群算法（Artificial Bee Colony， ABC） [8-9] 和螢火蟲算法（Firefly Algorithm， FA）[10-12]等。受自然界螢火蟲的生物社交行為影響，楊新社教授[13]于 2008 年提出螢火蟲算法。該算法采用全吸引方式更新螢火蟲的位置，即每只螢火蟲依次地向其它所有更亮的螢火蟲移動(dòng)，隨著種群的進(jìn)化，螢火蟲逐漸地聚集于最亮的螢火蟲附近，完成尋優(yōu)任務(wù)。

由于 FA 概念簡單、參數(shù)少，具有較強(qiáng)尋優(yōu)能力，本文將其應(yīng)用于基于概率感知模型的WSN節(jié)點(diǎn)部署，實(shí)現(xiàn)WSN高覆蓋率。仿真實(shí)驗(yàn)結(jié)果表明，基于螢火蟲算法的WSN節(jié)點(diǎn)部署方式具備更佳的監(jiān)測效果。

2 WSN節(jié)點(diǎn)覆蓋模型

2.1問題分析

WSN中的每個(gè)節(jié)點(diǎn)覆蓋范圍是以自身為中心，以感知距離為半徑的圓內(nèi)，在覆蓋范圍內(nèi)的所有信息均可被節(jié)點(diǎn)采集并存儲。WSN中的節(jié)點(diǎn)均是以圓面的形式對監(jiān)測局域進(jìn)行覆蓋，每個(gè)節(jié)點(diǎn)之間會出現(xiàn)覆蓋重疊情況，為計(jì)算WSN總覆蓋率帶來極大困難。為此，本文借助網(wǎng)格覆蓋模型來統(tǒng)計(jì)WSN覆蓋率。網(wǎng)格覆蓋模型將監(jiān)測區(qū)域進(jìn)行網(wǎng)格化，即將面積為[S]區(qū)域劃分成[M?N]的網(wǎng)格，若所有網(wǎng)格點(diǎn)均被監(jiān)測，則WSN總覆蓋率為[100%];若只有部分網(wǎng)格點(diǎn)[C]被監(jiān)測，則WSN覆蓋率為[（C/M?N）*100%]。

2.2模型建立

4 實(shí)例應(yīng)用

4.1 WSN與FA融合

WSN與FA融合關(guān)鍵在于待求解和目標(biāo)函數(shù)的確定。在WSN中，其解為傳感器的部署方案，即每個(gè)節(jié)點(diǎn)坐標(biāo);其部署方案的優(yōu)劣由WSN覆蓋率來確定。因此，可將螢火蟲的維度定位所有節(jié)點(diǎn)坐標(biāo)集合，即一只螢火蟲代表一個(gè)部署方案;可將WSN未覆蓋率作為算法的目標(biāo)函數(shù)，如公式（9）：

確定待求解和目標(biāo)函數(shù)后，F(xiàn)A尋優(yōu)的步驟如下：

1）初始化種群數(shù)量[N]、步長因子[α]、初始吸引度[β0]、光吸收系數(shù)[γ];

2）設(shè)定搜索范圍，初始化位置，將傳感器節(jié)點(diǎn)坐標(biāo)與螢火蟲的位置關(guān)聯(lián);

3）螢火蟲根據(jù)式（8）更新位置，結(jié)合式（9）計(jì)算螢火蟲的適應(yīng)值。若FA達(dá)到終止條件，則跳轉(zhuǎn)至步驟5），否則，重復(fù)執(zhí)行步驟4）;

4）輸出最優(yōu)螢火蟲位置信息和適應(yīng)值。

4.2實(shí)驗(yàn)分組及參數(shù)設(shè)置

為了比較隨機(jī)部署和基于螢火蟲算法部署的性能差異，設(shè)計(jì)了3組實(shí)驗(yàn)，具體信息見表1。傳感器其他參數(shù)[Re=0.5Rs]、[λ1]為1，[λ2]為0;FA種群大小[N]為40，步長因子[α]為0.2，初始吸引度[β0]為1.0，光吸收系數(shù)[γ=1/Γ2]（[Γ]為搜索域的區(qū)間值），評估次數(shù)[MAX_FEs]為1000;WSN傳感器聯(lián)合感知概率閾值[Cthreshold]為0.8。

4.3 仿真結(jié)果

為了消除隨機(jī)性影響，對兩種部署方案分別進(jìn)行了20次仿真測試，表2統(tǒng)計(jì)了兩種部署方案在不同實(shí)驗(yàn)分組的平均覆蓋率情況。基于螢火蟲算法部署的平均覆蓋率均高于隨機(jī)部署，分別高出5.65%，15.73%，8.81%;由組1和2數(shù)據(jù)可知，在只增加節(jié)點(diǎn)個(gè)數(shù)的情況下，平均覆蓋率提高了8.73%，說明增加節(jié)點(diǎn)可覆蓋率，但與此同時(shí)，增加了部署成本;組3在增大監(jiān)測面積和節(jié)點(diǎn)感知半徑的同時(shí)，減少了節(jié)點(diǎn)個(gè)數(shù)，平均覆蓋率最高，說明節(jié)點(diǎn)感知半徑是影響覆蓋率的重要因素之一。

為了更加直觀的比較兩種部署方法對監(jiān)測區(qū)域的部署情況，圖1展示了傳感器節(jié)點(diǎn)位置分布情況。由組別1節(jié)點(diǎn)分布圖可知，基于螢火蟲算法部署節(jié)點(diǎn)分布圖更均勻，未被覆蓋區(qū)域較少;由組別2節(jié)點(diǎn)分布圖可知，隨機(jī)部署節(jié)點(diǎn)分布圖未被覆蓋區(qū)域較多;由組別3節(jié)點(diǎn)分布圖可知，基于螢火蟲算法部署節(jié)點(diǎn)分布圖重疊區(qū)域相對較少;總體而言，基于螢火蟲算法部署節(jié)點(diǎn)分布圖覆蓋面更廣，節(jié)點(diǎn)感知重疊現(xiàn)象較少。

5 結(jié)論

螢火蟲算法相較于隨機(jī)部署方法，更有助于WSN覆蓋率的提高，說明該算法具備一定的優(yōu)化性能。觀察表2可知，WSN覆蓋率有很大的提升空間。因此，下一步的研究重點(diǎn)工作是對螢火蟲算法優(yōu)化性能進(jìn)行深入研究，通過對算法性能的優(yōu)化，提高WSN覆蓋率。

參考文獻(xiàn)：

[1] 劉建英，張仲良.水環(huán)境監(jiān)測方法標(biāo)準(zhǔn)技術(shù)體系探討[J].科技與創(chuàng)新，2017（7）：54-54.

[2] 李志剛，屈玉貴，藺智挺，等.基于無線傳感器網(wǎng)絡(luò)的戰(zhàn)場目標(biāo)跟蹤[J].傳感器與微系統(tǒng)，2007，26（7）：118-120.

[3] 夏梁斌.基于無線傳感網(wǎng)絡(luò)的公路邊坡監(jiān)測及臨滑預(yù)警研究[J].公路與汽運(yùn)，2017（1）：125-128.

[4] 龍吟，陳淞，齊鑫，等.應(yīng)用無線傳感器網(wǎng)絡(luò)的月表環(huán)境長期無人監(jiān)測系統(tǒng)構(gòu)想[J].航天器工程，2017，26（3）：9-16.

[5] 胡堅(jiān)，胡峰俊，張紅，等.基于改進(jìn)布谷鳥搜索算法對水質(zhì)監(jiān)測無線傳感器部署的優(yōu)化[J].浙江農(nóng)業(yè)學(xué)報(bào)，2020，32（5）：897-903.

[6] ZHAO J， LV L， WANG H， SUN H， et al. Particle Swarm Optimization based on Vector Gaussian Learning[J]. KSII Transactionson Internet and Information Systems， 2017，11（4）：2038-2057.

[7] SUN H， SHI X L， ZHAO J， et al. Hybrid algorithm of particle swarm optimization and artificial bee colony with its application in wireless sensor networks[J]. Sensor Letters，2014，12（2）： 392-397.

[8] 孫輝，謝海華，趙嘉，等.加權(quán)中心人工蜂群算法[J].控制與決策，2019，34（10）：2115-2124.

[9] GAO W F， HUANG L L， WANG J， et al. Enhanced artificial bee colony algorithm through differ-renttial evolution[J]. Applied Soft Computing， 2016， 48： 137-150.

[10] YU S H， SU S B， LU Q P， et al. A novel wise step strategy for firefly algorithm[J]. International Journal of Computer Mathematics， 2014， 91（12）：2507-2513.

[11] FISTER J I，YANG X S， FISTER I， et al， Fister Iztok， Brest Janez. Memetic firefly algorithm for combinatorial optimization： Proceedings of International Conference on Bioinspired Optimization Methods and their Application[C]. Piscataway： IEEEPress， 2012， 76-86.

[12] WANG H， WANG W J， SUN H， et al. Firefly algorithm with random attraction[J].International Journal of Bio-Inspired Computation，2016， 8（1）：33–41.

[13] YANG X S. Nature-Inspired Metaheuristic Algorithms[M]. Luniver Press， 2008.

[14] 何欣， 桂小林， 安健. 面向目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)確定性部署方法[J]. 西安交通大學(xué)學(xué)報(bào)， 2010， 44（6）：6-9.

[15] 張?jiān)浦蓿?吳成東， 程龍，等. 確定性空間的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略研究[J]. 控制與決策， 2010， 25（11）：1625-1629.

【通聯(lián)編輯：梁書】