人工鱼群优化的方向传感器覆盖增强

董海兰 张 可 朱 琳

(电子科技大学 成都 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).