徐躍州，張 欣

（貴州大學(xué)電子與信息學(xué)院，貴州貴陽 550025）

0 引言

無線傳感器網(wǎng)絡(luò)（WSNs）是由部署在監(jiān)測區(qū)域內(nèi)大量的廉價微型傳感器節(jié)點(diǎn)，通過無線通信方式形成的一個多跳自組織網(wǎng)絡(luò)，廣泛的應(yīng)用于環(huán)境監(jiān)測、目標(biāo)追蹤等領(lǐng)域［1］。優(yōu)化無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)布局提升網(wǎng)絡(luò)覆蓋率、降低網(wǎng)絡(luò)能耗、增強(qiáng)系統(tǒng)可靠性是當(dāng)前傳感器網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵問題之一。近年來，混合蛙跳算法（SFLA）得到廣泛關(guān)注，該算法結(jié)合了模因演算法（MA）和粒子群優(yōu)化（PSO）算法的優(yōu)點(diǎn)，具有高效的計(jì)算能力和優(yōu)良的全局搜索能力。文獻(xiàn)［2］提出了一種改進(jìn)蛙跳算法運(yùn)用在無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)布局方法;文獻(xiàn)［3］提出一種遺傳蛙跳混合算法。但是，由于蛙跳算法本身所具有的“早熟性”，在求解多維空間解集時容易陷入局部搜索，難以算出全局最優(yōu)解。

針對上述問題，本文結(jié)合虛擬力（virtual force）算法，該算法是通過建立節(jié)點(diǎn)和監(jiān)測區(qū)域的物理模型，構(gòu)造其之間的引力和斥力來優(yōu)化網(wǎng)絡(luò)布局，提出一種虛擬力蛙跳算法布局策略。該策略采用虛擬力指引蛙跳算法中各個子群中最優(yōu)解的結(jié)構(gòu)布局，及時跳出局部解，加快算法收斂性，并避免了虛擬力算法導(dǎo)致的移動節(jié)點(diǎn)優(yōu)化約束［4］。分析和仿真同時表明:虛擬力蛙跳算法具有更強(qiáng)的全局搜索能力和更快的全局收斂性。

1 傳感器網(wǎng)絡(luò)覆蓋模型

被節(jié)點(diǎn)集聯(lián)合檢測到的概率為

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

2 虛擬力蛙跳策略

2.1 蛙跳算法

蛙跳算法［6］是一種全新的后啟發(fā)式群體進(jìn)化算法，具有高效的計(jì)算性能和優(yōu)良的全局搜索能力。模擬青蛙覓食時按組群進(jìn)行思想傳遞的過程。整個青蛙群體采用模因分組分為不同的組群，每個組群中的青蛙都定義為問題的一個解。每個組群中的青蛙按照各自的群文化進(jìn)行進(jìn)化，在模因組每一次進(jìn)化過程中，對組內(nèi)最差的青蛙采用類似于PSO算法中的速度位移模型操作算子進(jìn)行位置調(diào)整，經(jīng)過一定次數(shù)的組內(nèi)進(jìn)化后，模因組間的青蛙重新混合形成新的模因組，實(shí)現(xiàn)全局的信息交流，依此進(jìn)行，直到算法到達(dá)預(yù)設(shè)的進(jìn)化次數(shù)或濃度值。其局部更新算子為

其中，為更新后的位置值，F(xiàn)w為模因組最差青蛙，F(xiàn)b為組內(nèi)最優(yōu)青蛙，F(xiàn)g為群體最優(yōu)青蛙，Dmax，Dmin分別為最大和最小移動距離。若Fb對Fw更新后濃度值低于原濃度值，則用Fg對Fw進(jìn)行更新，若濃度值仍低于原濃度值，則隨機(jī)生成一個青蛙代替Fw。

2.2 虛擬力算法

虛擬力算法是模仿物理模型中電荷之間的作用力，算法設(shè)定每個節(jié)點(diǎn)都與其他節(jié)點(diǎn)或監(jiān)測區(qū)域存在一定的引力或斥力，通過相互間的作用力使傳感器節(jié)點(diǎn)保持一定組合，避免節(jié)點(diǎn)的重復(fù)覆蓋和過分疏離［7］，節(jié)點(diǎn)間的作用力由預(yù)設(shè)的閾值dth決定。節(jié)點(diǎn)的虛擬力模型如圖1。

圖1 節(jié)點(diǎn)的虛擬力模型Fig 1 Virtual force model of node

2.3 虛擬力蛙跳算法

蛙跳算法是通過模因組內(nèi)最差解Fw逐次迭代向組內(nèi)和群體最優(yōu)解進(jìn)化的過程，但是，每次迭代過程中群體最優(yōu)解Fg和模因組內(nèi)最優(yōu)解Fb自身不進(jìn)行進(jìn)化，這就導(dǎo)致了整個蛙群很容易陷入局部最優(yōu)解。本文通過在每次蛙群進(jìn)化的過程中，對Fg本身進(jìn)行虛擬力進(jìn)化，若進(jìn)化后所得解優(yōu)于當(dāng)前解，則用進(jìn)化值代替當(dāng)前Fg，若劣于則不替換;而對Fb每次虛擬力進(jìn)化后不管所得解是否優(yōu)于當(dāng)前解，均對當(dāng)前Fb進(jìn)行替換。通過這種方式保證了全局最優(yōu)解收斂性，打破組內(nèi)循環(huán)，使各個模因組能夠快速的跳出局部極值，進(jìn)行全局搜索。Fg與Fb的位置優(yōu)化為

其中，F(xiàn)xy為傳感器受到的虛擬力;Fx，F(xiàn)y為虛擬力x，y軸的分量;s0為傳感器的最大移動距離，分為格點(diǎn)作用力和節(jié)點(diǎn)作用力下的移動距離;Fth為虛擬力的閾值。

虛擬力蛙跳優(yōu)化布局策略過程如圖2所示。

圖2 虛擬力蛙跳優(yōu)化布局策略過程Fig 2 Virtual force leapfrog strategy process to optimize layout

蛙跳算法具有高效的計(jì)算性能和優(yōu)良的全局搜索能力，而虛擬力的作用使重疊覆蓋的節(jié)點(diǎn)迅速分散［10］，因此，基于虛擬力的蛙跳算法將具有更好的優(yōu)化性能。

3 仿真分析

假設(shè)在邊長為50 m的正方形監(jiān)測區(qū)域中布置25個參數(shù)相同的無線傳感器節(jié)點(diǎn)，節(jié)點(diǎn)監(jiān)測半徑r為5 m，通信半徑為2r，虛擬力算法參數(shù)為:距離閾值dth為10m，節(jié)點(diǎn)在格點(diǎn)作用下最大步長s1為2.5 m，在傳感器節(jié)點(diǎn)作用下最大步長s2為3.5 m。蛙跳算法參數(shù)為:種群分組數(shù)m為8，模因組青蛙數(shù)n為8，組內(nèi)最大迭代數(shù)Ne為8，最大步長s3為5 m，在每次Fg，F(xiàn)b進(jìn)化時虛擬力迭代次數(shù)為2。文獻(xiàn)［11］表明，當(dāng)粒子數(shù)為待測區(qū)域大小的0.25%～4%時，偏差約為0.5%～0.1%，本文取粒子數(shù)為2500，具有較小的偏差性。所有算法均在Matlab上進(jìn)行仿真模擬。

圖3～圖6是節(jié)點(diǎn)覆蓋圖，節(jié)點(diǎn)數(shù)為25個。圖3為理論上最優(yōu)解，節(jié)點(diǎn)占監(jiān)測區(qū)域覆蓋面積的78.5%;圖4為蛙跳算法200輪后節(jié)點(diǎn)覆蓋圖，占62.5%，達(dá)到最優(yōu)覆蓋率的79.6%;圖5為虛擬力算法200輪后節(jié)點(diǎn)覆蓋圖，占67.3%，達(dá)到最優(yōu)覆蓋率的85.7%;圖6為虛擬力蛙跳算法200輪后覆蓋圖，占75.1%，達(dá)到最優(yōu)覆蓋率的95.7%。仿真表明:虛擬力蛙跳算法優(yōu)于蛙跳和虛擬力算法。

圖3 理論極限節(jié)點(diǎn)覆蓋圖Fig 3 Node coverage in theoretical limit

圖4 蛙跳算法節(jié)點(diǎn)覆蓋圖Fig 4 Leapfrog algorithm node coverage

圖5 虛擬力算法節(jié)點(diǎn)覆蓋圖Fig 5 Virtual force algorithm node coverage

圖7是3種算法的收斂速度比較圖，由圖中可以看出虛擬力蛙跳算法的收斂速度最快，當(dāng)?shù)降?8代的時候已收斂為全局最優(yōu)解，虛擬力算法直至200代仍未收斂，而蛙跳算法一直陷入局部最優(yōu)解，未能進(jìn)行全局搜索。與虛擬力算法和蛙跳算法相比，虛擬力算法能迅速跳出局部搜索找出全局最優(yōu)解，具有更好的全局布局優(yōu)化效果和更快的收斂速度。

圖6 虛擬力蛙跳算法節(jié)點(diǎn)覆蓋圖Fig 6 Virtual force leapfrog algorithm node coverage

圖7 3種算法的收斂速度比較Fig 7 Comparison of convergence rate of three algorithms

4 結(jié)論

無線傳感器網(wǎng)絡(luò)的優(yōu)化布局可以極大地提高節(jié)點(diǎn)的覆蓋率，增強(qiáng)系統(tǒng)的可靠性，降低網(wǎng)絡(luò)能耗。在融合虛擬力和蛙跳算法的基礎(chǔ)上，本文提出一種新型的虛擬力蛙跳策略，該策略以優(yōu)化網(wǎng)絡(luò)布局為目標(biāo)，利用虛擬力算法優(yōu)化蛙跳算法的局部最優(yōu)解，使蛙跳算法能夠迅速的跳出局部極值，進(jìn)行全局搜索。仿真證明:相對于虛擬力和蛙跳算法，虛擬力蛙跳策略具有更快的收斂速度和更大網(wǎng)絡(luò)覆蓋范圍。

［1］Wang X，Wang S.An improved particle filter for target tracking in sensor system［J］.Sensors，2007，7（1）:144-156.

［2］龍 騰，孫 輝，趙 嘉.基于改進(jìn)蛙跳算法的WSNs移動節(jié)點(diǎn)部署研究［J］.計(jì)算機(jī)工程，2012，38（5）:96-99.

［3］王曉笛.基于改進(jìn)蛙跳算法的多目標(biāo)優(yōu)化問題研究［D］.長沙:湖南師范大學(xué)，2011:5.

［4］王 雪，王 晟，馬俊杰.無線傳感器網(wǎng)絡(luò)布局的虛擬力導(dǎo)向微粒群優(yōu)化策略［J］.電子學(xué)報(bào)，2007，35（11）:2038-2042.

［5］李 麗.基于改進(jìn)魚群算法的WSNs覆蓋優(yōu)化策略［J］.微電子學(xué)與計(jì)算機(jī)，2013，2（30）:83-86.

［6］楊淑瑩，張 樺.群體智能與仿生計(jì)算—Matlab技術(shù)實(shí)現(xiàn)［M］.北京:電子工業(yè)出版社，2012:6.

［7］孫 偉.基于群體智能優(yōu)化算法的WSNs部署策略研究［D］.南京:南京林業(yè)大學(xué)，2013:6.

［8］Zou Y.Coverage-driven sensor deployment and energy-efficient information processing in wireless sensor networks［D］.Durham USA:Duke University，2004.

［9］Zou Y，Chakrabarty K.Sensor deployment and target location based on virtual forces［C］//IEEE INFOCOM，Piscataway，NJ，USA:IEEE，2003:1293-1303.

［10］王 蕊，劉國枝.基于魚群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)部署［J］.振動與沖擊，2009，2（28）:8-11.

［11］Wang X，Wang S，Ma J.Dynamic deployment optimization in wireless sensor networks［J］.Lecture Notes in Control and Information Science，2006，344:182-187.