人工魚群優化的方向傳感器覆蓋增強

董海蘭 張 可 朱 琳

(電子科技大學 成都 611731)

1 引言

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

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

2 感知模型及覆蓋問題

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

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

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

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

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

則點p在傳感器節點n的覆蓋范圍內。每個節點所能覆蓋區域點如圖2所示。

圖2 節點覆蓋區域

假設被監測區域點總數為M，被傳感器節點覆蓋到的點數累計為S，則WMSN覆蓋率計算公式簡化為:

3 算法描述

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

表1 覆蓋問題中人工魚群變量對應

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

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

圖3 算法流程

4 仿真及分析

4.1 仿真環境設置

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

表2 人工魚參數

表3 傳感器參數

4.2 仿真結果分析

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

圖4 初始覆蓋率72.9%

圖5 優化后覆蓋率82%

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

圖6 覆蓋率提升9.1%

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

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

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

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

圖9 節點個數對覆蓋率影響

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

5 結論

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

[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－hwan 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覆蓋優化方法[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).