無線傳感器網(wǎng)絡的虛擬力蛙跳優(yōu)化布局策略*

徐躍州，張 欣

（貴州大學電子與信息學院，貴州貴陽 550025）

0 引言

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

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

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

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

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

2 虛擬力蛙跳策略

2.1 蛙跳算法

蛙跳算法［6］是一種全新的后啟發(fā)式群體進化算法，具有高效的計算性能和優(yōu)良的全局搜索能力。模擬青蛙覓食時按組群進行思想傳遞的過程。整個青蛙群體采用模因分組分為不同的組群，每個組群中的青蛙都定義為問題的一個解。每個組群中的青蛙按照各自的群文化進行進化，在模因組每一次進化過程中，對組內(nèi)最差的青蛙采用類似于PSO算法中的速度位移模型操作算子進行位置調(diào)整，經(jīng)過一定次數(shù)的組內(nèi)進化后，模因組間的青蛙重新混合形成新的模因組，實現(xià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進行更新，若濃度值仍低于原濃度值，則隨機生成一個青蛙代替Fw。

2.2 虛擬力算法

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

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

2.3 虛擬力蛙跳算法

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

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

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

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

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

3 仿真分析

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

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

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

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

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

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

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

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

4 結論

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

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

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

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

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

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

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

［7］孫 偉.基于群體智能優(yōu)化算法的WSNs部署策略研究［D］.南京:南京林業(yè)大學，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)絡部署［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.