人工魚群優(yōu)化的方向傳感器覆蓋增強

董海蘭 張 可 朱 琳

(電子科技大學(xué) 成都 611731)

1 引言

無線多媒體傳感器網(wǎng)絡(luò)WMSN(Wireless Multimedia Sensor Networks)在安檢、戰(zhàn)場、環(huán)境監(jiān)測等領(lǐng)域中有著廣泛的應(yīng)用，WMSN監(jiān)測有效性主要取決于網(wǎng)絡(luò)覆蓋率，覆蓋率越高，監(jiān)測就越全面。傳統(tǒng)WSN主要通過優(yōu)化節(jié)點部署提升覆蓋率，文獻[1～3]利用粒子群算法PSO尋求最優(yōu)部署增強WSN覆蓋率。文獻[4]、[5]針對移動傳感器網(wǎng)絡(luò)，利用PSO優(yōu)化可移動節(jié)點優(yōu)化部署，增強網(wǎng)絡(luò)覆蓋率。文獻[6]利用改進的PSO對WSN中傳感器節(jié)點位置進行優(yōu)化，達到最優(yōu)覆蓋。不同于傳統(tǒng)WSN，多媒體傳感器節(jié)點帶有方向性，方向角對網(wǎng)絡(luò)覆蓋率有很大影響。文獻[7]、[8]借助虛擬力方法在節(jié)點不移動二維模型下提高覆蓋率，文獻[9]使用粒子群算法PSO提高方向傳感器網(wǎng)絡(luò)覆蓋率，且比文獻[7]、[8]更優(yōu)，文獻[10]對[9]進行了擴展，在節(jié)點位置和方向均可改變情況下利用PSO提高覆蓋率。文獻[11]提出三維感知模型，并基于此模型結(jié)合虛擬力和模擬退火(SA)算法優(yōu)化方向角，提高區(qū)域覆蓋率。文獻[12]則引用人工魚群(AF)智能優(yōu)化算法通過全局優(yōu)化方向角解決位置固定的二維覆蓋增強問題。

以上文獻對覆蓋增強問題研究大都是集中在二維網(wǎng)絡(luò)覆蓋率問題，較少涉及三維網(wǎng)絡(luò)覆蓋率，而三維網(wǎng)絡(luò)覆蓋率能夠更加真實反映網(wǎng)絡(luò)對監(jiān)測環(huán)境的覆蓋情況，因而，本文對文獻[11]三維方向傳感器感知模型進行了簡化，并利用人工魚群優(yōu)化算法優(yōu)化網(wǎng)絡(luò)傳感器方向角度值，通過減少重疊覆蓋以提升無線多媒體傳感器三維網(wǎng)絡(luò)覆蓋率。

2 感知模型及覆蓋問題

方向傳感器感知模型圖見圖1。

基于圖1(a)模型，計算視角為θ、感知半徑為R的方向傳感器監(jiān)測到的三維空間大小為(1－cosθ)(2πR3)/3。與傳統(tǒng)無線傳感器網(wǎng)絡(luò)不同，WMSN中傳感器具有方向性，圖1(b)是方向傳感器被放置于監(jiān)測環(huán)境中的傳感器方向角度示意圖，若在區(qū)域體積為Ω的空間放置N個節(jié)點，則此N個傳感器節(jié)點理論覆蓋率為:

由式(1)可以看出網(wǎng)絡(luò)覆蓋率與傳感器節(jié)點視角、感知半徑及節(jié)點個數(shù)成正比。據(jù)式(1)得到理論覆蓋率的前提是網(wǎng)絡(luò)中每個方向傳感器角度值α足夠理想，使得網(wǎng)絡(luò)中各個傳感器節(jié)點之間沒有重疊覆蓋。本文所提算法將會對傳感器方向角α進行優(yōu)化，減少網(wǎng)絡(luò)中重疊覆蓋，從而提高網(wǎng)絡(luò)覆蓋率。

由于方向傳感器三維感知模型體積計算過于繁瑣，為簡化覆蓋問題計算復(fù)雜度，將被監(jiān)測區(qū)域劃分成均勻分布的點p(xp，yp，zp)，若p在感知范圍內(nèi)，則該點能夠被覆蓋。

假設(shè)點p與傳感器節(jié)點n之間的距離為d(n，p)，交點 q(xq，yq，zq)與 n 之間的距離為 d(n，q)，點p與節(jié)點n方向向量為，q與n方向向量為，兩向量夾角為β，若點p滿足下式:

則點p在傳感器節(jié)點n的覆蓋范圍內(nèi)。每個節(jié)點所能覆蓋區(qū)域點如圖2所示。

圖2 節(jié)點覆蓋區(qū)域

假設(shè)被監(jiān)測區(qū)域點總數(shù)為M，被傳感器節(jié)點覆蓋到的點數(shù)累計為S，則WMSN覆蓋率計算公式簡化為:

3 算法描述

人工魚群算法(AF)是一種簡單高效尋優(yōu)算法[6]，人工魚作為該算法的行為個體，有三種行為方式，即覓食行為、聚群行為和追尾行為。覓食和聚群具有搜索局部極值的效用，覓食行為帶有隨機性，從而能跳出局部極值，實現(xiàn)對目標值逐步尋優(yōu)達到全局搜索的效果。在覆蓋增強問題中，人工魚群算法的變量和食物濃度分別對應(yīng)覆蓋增強問題中傳感器方向角度值和網(wǎng)絡(luò)覆蓋率，如表1所示。

表1 覆蓋問題中人工魚群變量對應(yīng)

方向傳感器撒布后，將自身地理位置和方向角度值傳回匯聚節(jié)點，在匯聚節(jié)點處執(zhí)行人工魚群算法對方向角進行迭代尋優(yōu)。試探不同方向角，減少節(jié)點之間覆蓋重疊，從而增強覆蓋率，若試探方向角度值使得覆蓋率比當前覆蓋率大，則朝嘗試后的方向角度值改變，依次逐步迭代，最后將優(yōu)化后的方向角返回給各傳感器節(jié)點，各節(jié)點轉(zhuǎn)動到優(yōu)化后的方向角度值，完成網(wǎng)絡(luò)覆蓋率增強的工作。

假設(shè)有Nfish條人工魚進行網(wǎng)絡(luò)覆蓋率尋優(yōu)，共迭代K次，每條人工魚攜帶網(wǎng)絡(luò)中所有傳感器方向角度值，若第n條魚有鄰居(即其他人工魚攜帶的方向角度值與第n條魚的方向角度值最大相對距離小于人工魚視距)，且鄰居覆蓋率大于自身，則改變方向角度值，向鄰居靠近;否則，計算鄰居中心位置，若中心點處覆蓋率大于自身，則改變方向角度值向鄰居中心靠近;否則，隨機改變方向角度值，試探找出能夠使覆蓋率更高的方向角度值，每次迭代后公告最大覆蓋率。算法流程如圖3所示。

圖3 算法流程

4 仿真及分析

4.1 仿真環(huán)境設(shè)置

基于MATLAB平臺進行仿真實驗，節(jié)點位置及方向角服從均勻隨機分布，設(shè)置人工魚及傳感器仿真參數(shù)如表2和表3。

表2 人工魚參數(shù)

表3 傳感器參數(shù)

4.2 仿真結(jié)果分析

無線多媒體傳感器網(wǎng)絡(luò)與具體應(yīng)用緊密相關(guān)，網(wǎng)絡(luò)規(guī)模大小由被監(jiān)測環(huán)境直接決定，為方便分析，對100×100×20m3三維空間(與田徑運動場大小相當)進行監(jiān)測，將100個方向傳感器節(jié)點以隨機方式撒布在被監(jiān)測區(qū)域。初始覆蓋如圖4所示，青色為需要監(jiān)測的區(qū)域，洋紅色為能夠被傳感器覆蓋到的區(qū)域，覆蓋率為72.9%，使用人工魚群算法對節(jié)點感知方向角α進行迭代優(yōu)化20次，得到覆蓋圖5，覆蓋率為82%。通過圖4與圖5對比可以看出，優(yōu)化后網(wǎng)絡(luò)對監(jiān)測區(qū)域覆蓋更全面更均勻。

圖4 初始覆蓋率72.9%

圖5 優(yōu)化后覆蓋率82%

圖6顯示隨著迭代次數(shù)增加，覆蓋率呈上升趨勢，迭代20次后覆蓋率提升9.1%。

圖6 覆蓋率提升9.1%

取參數(shù)N=100，θ=45°，對100×100×20m3三維空間進行監(jiān)測，隨著傳感器感知半徑R增大，網(wǎng)絡(luò)覆蓋率增強，如圖7所示。當R＜10m時，各傳感器感知區(qū)域重疊部分較少，所以通過人工魚群算法優(yōu)化方向角α?xí)r并未有效提高網(wǎng)絡(luò)覆蓋率;當R＞10m時，通過人工魚群算法優(yōu)化，可減少隨機部署所帶來的重疊覆蓋，相比初始覆蓋率可以提升5% ～8%。

圖7 感知半徑對覆蓋率影響

取參數(shù)N=100，R=20m，隨著θ增大，網(wǎng)絡(luò)覆蓋率相應(yīng)增大。當θ＜20°時，利用人工魚群算法優(yōu)化各節(jié)點方向角α對覆蓋率提升效果并不明顯;當20°＜θ＜60°時，人工魚群優(yōu)化可降低覆蓋重復(fù)率，覆蓋率提升大約在4% ～7%之間;當θ＞60°方向傳感器節(jié)點接近全向傳感器，所以優(yōu)化方向角與否已經(jīng)對覆蓋率影響不大。特殊的，當θ=90°，傳感器感知模型為半球狀，改變α對覆蓋率提升已經(jīng)沒有意義，初始和優(yōu)化后的覆蓋率相等，如圖8所示。

取參數(shù)R=20m，θ=45°傳感器個數(shù)在1～100之間逐漸遞增，由圖9仿真結(jié)果可知，隨節(jié)點個數(shù)增多，網(wǎng)絡(luò)覆蓋率整體都呈上升趨勢，采用人工魚群算法后覆蓋率相比初始有5%左右的提升。

圖9 節(jié)點個數(shù)對覆蓋率影響

圖7、8、9理論覆蓋率值根據(jù)公式(1)計算得到，分別分析了隨著感知半徑R、視角θ、傳感器個數(shù)N改變對算法的影響。結(jié)合人工魚群算法優(yōu)化能夠提高覆蓋率，雖與理論覆蓋值仍有一定差距，但比初始覆蓋率更接近理論值。由于節(jié)點隨機撒布，方向傳感器間重疊覆蓋不可避免，因而很難達到理論覆蓋值。

5 結(jié)論

本文基于節(jié)點三維感知模型對三維監(jiān)測區(qū)域的覆蓋增強問題進行研究，利用人工魚群算法迭代優(yōu)化傳感器方向角度值，降低冗余覆蓋，增強網(wǎng)絡(luò)覆蓋率。經(jīng)過仿真證明此法可以有效提高三維區(qū)域覆蓋率，并就傳感器參數(shù)對三維區(qū)域覆蓋的影響進行了分析，得出在迭代次數(shù)相同情況下，隨參數(shù)改變?nèi)斯~群算法對網(wǎng)絡(luò)覆蓋增強效果不盡相同，但相比初始覆蓋能更加接近理論覆蓋值。

[1]Aziz N.A.B.A，Mohemmed A.W，Alias M.Y.A wireless sensor network coverage optimization algorithm based on particle swarm optimization and Voronoi diagram[C].International Conference on Networking，Sensing and Control，2009，602 －607.

[2]Lin Zhuliang，Ma Shiping，Tao Zuo － ying.Research on Particle Swarm Optimization strategy for forest fire detection system based on Wireless Sensor Networks[C].Chinese Control and Decision Conference，2009，3608－3612.

[3]W.Z.Wan Ismail and S.Abd.Manaf.Study on coverage in Wireless Sensor Network using grid based strategy and Particle Swarm Optimization[C].Asia Pacific Conference on Circuits and Systems，2010，1175－1178.

[4]Nor Azlina Ab.Aziz，Ammar W.Mohemmed，Mohamad Yusoff Alias，etc.Coverage Maximization and Energy Conservation for Mobile Wireless Sensor Networks:A Two Phase Particle Swarm Optimization Algorithm [C].the 6th International Conference on Bio－Inspired Computing:Theories and Applications，2011，64－69.

[5]Chan－Myung Kim，Yong－h(huán)wan Kim，Youn－Hee Han etc，An Energy－Efficient Self－Deployment Scheme in Intelligent Mobile Sensor Networks[C].the 4th International Conference on Multimedia and Ubiquitous Engineering，2010，1－6.

[6]朱海榮，李平，程劍.基于改進PSO算法的WSN覆蓋優(yōu)化方法[J].計算機工程，2011.37(8):82－84.

[7]Dan.Tao，Huadong Ma，Liang Liu.A Virtual Potential Field Based Coverage－Enhancing Algorithm forDirectionalSensorNetworks[J]，Journal of Software，2007，18(5):1152－1163.

[8]Dan Tao.Research on coverage control and cooperative processing method for video sensor networks[D].doctoral dissertation，Beijing University of Posts and Telecommunications，2007.

[9]Y.Xu，B.Lei.Particle swarm optimization to improve the coverage of a camera network[C].In Proc.2009 SPIE －MIPPR，2009，7497(18).

[10]Yichun Xu，angjun Lei，huifa Sun，etc.Three particle swarm algorithms to improve coverage of camera networks with mobile nodes[C].Conference on Bio－Inspired Computing:Theories and Applications，2010，816－820.

[11]Huadong Ma.Xi Zhang，and Anlong Ming.A Coverage－Enhancing Method for 3D Directional Sensor Networks[C].INFOCOM 2009，2791－2795.

[12]Ke Zhang，Wei Zhang，Chunyang Dai，etc.Artificial fish－swarm based enhancing algorithm for visible light sensor networks[J].Optoelectronics Letter，2010，6(3).