冯秀芳，辛 英，阴成军，常建峰

（太原理工大学 计算机科学与技术学院，山西 太原030024）

0 引 言

无线多媒体传感器网络使人类的视野更为广阔，是一个新型、前沿、多学科高度交叉的研究领域［1－2］。覆盖控制和部署策略对于整个多媒体传感器网络的监测性能、监测质量具有至关重要的作用［3］。

不同于传统传感器网络全向感知节点，无线多媒体传感器网络中，无论是红外线传感器，超声波传感器还是视频传感器都是有向的。学术界已有前辈在研究此方面。Jing Ai［4］，发表文章讨论了在随机分布的无线传感器网络中，有向传感器节点的覆盖问题。文献 ［5］介绍了无线传感器网络中，不明位置下的覆盖问题。文献 ［6］讨论有向传感器网络中，二维和三维空间在随机部署下的入侵目标检测算法。Daniel［7］等讨论了无线传感器网络中，基于有向的视频传感器节点的覆盖问题。文献 ［8］向我们介绍有向传感网络的覆盖及其能量有效利用等问题。Prasan［9］等向我们介绍了无线传感器网络中，基于拓扑结构的能量控制问题。陶丹［10］等进行了有向传感器网络的覆盖增强研究，提出了一种基于虚拟力的有向传感器网络覆盖增强算法。文献［11］提出一种基于粒子群算法的无线传感网络覆盖优化方法。文献 ［12］把基本粒子群算法和与拟物力算法相融合，设计出拟物力导向的无线传感网络覆盖优化策略。文献［13］，提出了一种微粒群优化的有向传感器网络覆盖增强算法。本文在研究前面成果的基础上，结合虚拟力和粒子群优化算法提出了一种新的覆盖增强算法。此算法在能量有效利用的前提下，能有效提高网络的覆盖率。

1 有向感知模型

感知模型的研究是进行覆盖控制研究的基础。不同于传统的全向感知模型，多媒体传感器网络中的节点具有有限的感知角，所以需要研究有向感知模型。如图1所示，有向感知模型。

图1 有向感知模型

如图1所示，有向传感器节点P覆盖区域是一个扇形，可以用四元组 （P，Rs，dij，θ）来表示。一般在二维空间中的有向感知模型如图1所示，这种模型的一个特殊情况是，当θ＝360°时，就成了全向感知模型。三角形点是感知事件，阴影扇形区域是有向传感器节点的感知范围，感知范围和有向传感器节点的感知半径和市场角度有关。节点可以选择不同的工作方向来覆盖事件和区域。其中，P是传感器节点的位置，dij是单位向量，定义了有向传感器的方向。θ是视角 （FoV），描述了有向传感器的最大感应角。Rs为传感器的感知半径。

2 基于虚拟力和粒子群算法的覆盖增强策略

2.1 覆盖增强算法

使用虚拟力算法来控制传感器节点的移动，使网络中的节点分布均匀，从而提高网络的覆盖性能。由于每个有向传感器节点可能有很多的感知方向，感知方向不同，传感器节点的覆盖区域也不一样。针对此问题，该算法首先使用虚拟力全局调整节点的位置，然后通过粒子群优化算法局部调整节点的感知方向，减少节点之间的重叠区，同时减少节点之间的感知盲区，提高整个区域的覆盖率。

2.2 算法原理及分析

2.2.1 基于虚拟力覆盖增强算法

该算法的核心思想是，传感器网络中的节点和其他的对象之间都存在着大小不等的引力和斥力，斥力和引力是用传感器节点之间的位置、方向以及设定的一些参数来刻画的。利用传感器网络中节点的可移动性，通过受力的不同，使传感器节点沿着力的方向进行移动，从而使网络中的节点分布合理，最终合理的覆盖整个区域，更好的提供感知目标区域的信息。

给出节点的受力分析如图2所示：dij表示传感器节点si的中心点vi和节点sj的中心点vj之间的欧式距离。当dij小于传感器节点的半径的时候，它们的感知区域才存在重叠的可能，故两个传感器节点之间存在的斥力的作用，该斥力作用于传感器节点的中心点vi和vj上。根据基本虚拟力公式，中心点所受引力的大小与中心点vi和vj之间的距离成正比，而中心点的位置由传感器节点si和sj的位置决定。

图2 有向传感器节点受力

当dij大于传感器节点的半径的时候，它们的感知区域不存在重叠，这时两个传感器节点之间存在着引力的作用，该引力作用于传感器节点的中心点vi和vj上。根据基本虚拟力公式，中心点所受斥力的大小与中心点vi和vj之间的距离成反比，同样，中心点的位置由传感器节点si和sj的位置决定。

各传感器节点根据虚拟力将原位置 （x，y）更新为新位置 （x，，y，），如式 （1）所示，其中，MaxStep是传感节点最大移动距离，Fxy是作用于传感节点的虚拟力，Fx，Fy是虚拟力的x轴和y轴的分量，Fth是虚拟力阈值，当传感节点所受虚拟力小于该值时，则认为它不需移动

距离阈值Fth在传感器网络部署的疏密程度起到一个重要的作用。当Fth很小时，传感节点会分布过密，从而传感器网络不能很好的覆盖整个区域，无法保证网络的覆盖率；当Fth设定很大的时候，传感节点的分布很稀疏，这就容易形成感知盲区。因此，虚拟力算法在实际的应用中，一些参数只能通过经验来确定，无法自动的满足不同检测环境的需求。

虚拟力移动节点算法流程：

（1）随机分布n个节点，获取有向传感器节点位置信息，生成有向传感器节点模型

（2）for loop＝1：MAXLOOP%循环迭代次数

（3）计算传有向传感器节点中心点之间的距离Dij，计算网络的覆盖率C，计算网络的覆盖效率CE，覆盖均匀性U：

for i＝1：n%计算节点之间的虚拟力Fi

for j＝1：n

计算传感器节点Si，Sj的中心点Mi和Mj的虚拟力Fij

End

End

End

（4）计算传感器节点的新位置

（5）计算节点的平均移动距离

（6）将新位置赋值给旧位置End

2.2.2 粒子群优化覆盖增强算法

根据2.2.1的分析，经过虚拟力作用的调整后，多媒体传感器网络中节点分布相对均匀。本节用粒子群算法局部调整有向传感器网络的感知方向，针对有向传感器网络感知方向调整的需要，设计微粒适应值计算函数和种群进化策略，在此基础上，以网络的覆盖率为优化目标，调整传感器节点的感知方向最后实现有向传感器网络覆盖的增强［14］。

设监测区域中的有向传感器节点数为n，每个节点的初始感知方向向量为 （O1，O2，…，ON）。引入的微粒群种群规模为m，微粒群的搜索空间d为监测区域中传感器节点数n。微粒i的角度向量αi为 （αi1，αi2，…，αin），其中αi1，αi2，…，αin依次表示传感器节点1至n的感知方向。微粒i的角度调整向量ωi，为 （ωi1，ωi2，…，ωin）。

定义微粒i的适应值函数fi为

适应值fi应传感器节点在感知方向 （O1，O2，…，ON）＝ （αi1，αi2，…，αin）下的有向传感器网络的有效覆盖率，群体中所有微粒经历的最佳位置pg为

为了找到全局最优解，需要对微粒进行迭代的进化，微粒进化对应的角度调整计算公式如下所示

式中：C1、C2——加速因子，它们的作用是用于调节每个微粒向局部最优解和全局最优解的进化步长；pbestaij——微粒i的第j维经历的局部最佳角度；gbestaij——用为全局最佳角度；aij（t）——第i代种群中的第j个微粒的第j维，即传感器j的感知方向；在进化过程中对于每次调整的角度大小ωij应限制于一定范围内，这样就能进使迭代进化比较稳定。当ωij超出该范围时，则调整为ωmax或ωmin；β﹙t﹚∈ （0，1）为随机数，称为惯性因子，随迭代次数增加应逐步减少，从而使得算法在初期能快速到达全局最优解附近，后期则能稳定收敛至全局最优解。β﹙t﹚的取值如

式 （6）所示［15］

式中：βmax——惯性因子的最大值，βmin——惯性因子的最小值，t——当前迭代次数，MaxDT——最大迭代次数。

基于微粒群优化算法的多媒体传感器网络覆盖增强算法流程：

（1）初始化多媒体传感器节点的位置，设定种群的规模为n，随机生成每个粒子的初始位置Xi、初始感知角度αi和速度Vi。

（2）根据多媒体传感器网络覆盖率的计算方法，计算传感器节点初始部署下的覆盖率。

（3）对每个微粒，根据公式更新最优位置pbest＿aij和全局最优位置gbest＿aij。

（4）判断粒子是否达到当前的近似最优解，重新生成各粒子速度，计算适应值。

（5）是否达到停止的条件 （粒度减少到特定的值、达到最好的适应值或到了最大的跌代数），返回步骤 （2）。

3 覆盖增强算法的仿真试验

3.1 覆盖效果

实验采用Matlab7.0仿真环境，用到粒子群工具箱对覆盖增强算法的调整。假设在边长为1000cm的正方形监测区域中随机部署70个有向传感器节点，所有传感器节点感知半径R＝70cm，通信半径为2R＝140cm。虚拟力算法的参数为：ωA＝2与ωR＝4，采用微粒群算法的加速因子C1＝C2＝1。传感器网络的初始角度为60°，每次调整的角度为5°。图3（a）为初始随机部署70个传感器节点的分布图，从图中可以看出，有些区域中节点的分布集中，有些空白区域没有被节点覆盖，因此，节点的分布不均匀，不能最大化覆盖检测区域，同时也浪费了传感器节点资源。图3（b）、（c）、 （d）为用虚拟力算法先全局调整节点的位置，然后用粒子群优化算法调整每个传感器网络的感知方向，通过仿真实验进行200次的迭代的结果。

3.2 参数变化分析

（1）节点数分析：多媒体传感器网络的感知半径对网络的覆盖率有很大的影响，在感知角度一定的情况下，随着感知半径的增加，覆盖区域的面积相应的增加。表1为不同节点数覆盖率数据，从表中看以看出，节点数越多覆盖率越高。

图4表示随着节点的变化，随机部署、基于虚拟了算法的优化和粒子群算法优化的覆盖率的比较图。通过图可以看出，初始的随机部署节点的覆盖率不是很高，进过虚拟力的作用调整节点的位置后，覆盖率有了明显的提高。在调整位置的基础上，采用粒子群优化算法对节点的感知方向进行局部的调整，可以看出，网络的覆盖率又提升了很多。

图3 70个节点覆盖优化迭代

表1 节点数变化的覆盖性能测试数据

图4 初始部署与覆盖增强后比较

（2）感知半径分析：有向传感器网络的感知半径对网络的覆盖性能有很大的影响，表2为不同的感知半径下，网络的覆盖率数据。

如图5所示，在随机部署下，节点数的不同初始覆盖率有很大的区别。在固定的区域中，传感器节点的感知半径不变的时候，节点数越多，传感器网络的覆盖率就越高，节点数为90个时候比节点数45个的时候的覆盖率对了42%。同样在虚拟力算法的优化中，节点数为90的覆盖率比节点数为45个时候的覆盖率多了49%。在粒子群优化算法优化后，节点数为90的覆盖率比节点数为45的时候覆盖率多了38%。

表2 传感器节点半径覆盖性能测试数据

图5 节点半径对覆盖优化的影响

小结：通过实验表明，该算法很好的消除了初始部署中传感器节点的感知盲区和重叠区，并分析传感器节点的半径和个数对网络覆盖率的影响，随着传感器节点的感知半径和个数的增加，网络的覆盖也有所增加。虚拟力参数对网络的覆盖具有很大的影响。在实验的过程中粒子群优化算法具有陷入局部最优解的确定，有时候在迭代次数增加的时候，网络的覆盖率有所减少。后续的工作是进一步对粒子群算法改进和参数调整，是网络达到更优的覆盖。

4 结束语

本文围绕无线多媒体传感器网络的有向感知模型，研究基于虚拟力和粒子群算法的覆盖增强算法。采用随机部署方法在检测区域中投放地大量有向传感器节点，由于初始部署后节点分布往往不合理和不均匀，不能最大化的覆盖整个区域，因此，在完成初始部署后，需要采用相应的覆盖增强策略来调整传感器节点的分布和感知方向，进而改善多媒体传感器网络的覆盖性能。本算法通过节点之间及节点和障碍物之间的虚拟力，调整传感器节点的分布位置，使网络中的节点最后分布合理、均匀，同时，有效地调整有向传感器节点的工作方向，使得能够用最少的节点达到最大的覆盖。

［1］DeBardelaben J A.Multimedia sensor networks for ISR applications ［C］.Conference Record of the Thirty－Seventh Asilomar Conference on Signals，Systems and Computers.Pacific Grove，Califomia：IEEE Press，2005：2009－2012.

［2］Akyildiz I F，Melodia T，Chowdhury K R.A survey on wireless multimedia sensor networks ［J］.Computer Networks，2007，51 （4）：921－960.

［3］Misra S，Reisslein M，Xue G.A survey of multimedia streaming in wireless sensor networks ［J］.IEEE Communications Surveys Tutorials，2008，10 （4）：18－39.

［4］Jing Ai·Alhussein A.Abouzeid coverage by directional sensors in randomly deployed wireless sensor networks ［J］.Comb Optim，2006，11 （1）：21－41.

［5］Ossama Younis，Marwan Krunz，Srinivasan Ramasubramanian location－unaware coverage in wireless sensor networks ［J］.Ad Hoc Networks，2008，6 （7）：1078－1097.

［6］Yang Xiao，Zhang Yanping，Miao Peng，et al.Intrusion object detection under Two and three－dimensional randomized scheduling algorithms in sensor networks ［J］.Computer Networks，2009，53 （14）：2458－2475.

［7］Daniel G Costa，Luiz Affonso Guedes.The coverage problem in video－based wireless sensor networks：A survey ［J］.Sensors，2010，10：8215－8247.

［8］Ma H，Liu Y.Some problems of directional sensor networks［J］.International Journal of Sensor Networks（InderScience），2007，2 （1－2）：44－52.

［9］Prasan Kumar Sahoo，Sheu Jang－Ping，Hsieh Kun－Ying.Power control based topology construction for the distributed wireless sensor networks ［J］.Computer Communications，2007，30（14－15）：2774－2785.

［10］TAO Dan.Research on coverage control and collaborative approach of video sensor network ［D］.Beijing：Beijing University of Posts and Telecommunications，2007 （in Chinese）.［陶丹.视频传感器网络覆盖控制及协作处理方法研究 ［D］.北京：北京邮电大学，2007.］

［11］TAO Dan，MA Donghua，LIU Liang.The coverage enhancement algorithm of sensor network based on virtual potential field ［J］.Journal of Software，2007，18 （5）：1152－1163（in Chinese）.［陶丹，马华东，刘亮.基于虚拟势场的有向传感器网络覆盖增强算法 ［J］.Journal of Software，2007，18 （5）：1152－1163.］

［12］WANG Xue，WANG Chen，MA Junjie.The virtual poweroriented particle swarm optimization strategy for the layout of wireless sensor network ［J］.Chinese Journal of Electronics，2007，35 （11）：2038－2042 （in Chinese）. ［王雪，王晨，马俊杰.无线传感网络布局的虚拟力导向微粒群优化策略 ［J］.电子学报，2007，35 （11）：2038－2042.］

［13］LIN Zhuliang.The study on coverage problem optimization Strategy of wireless sensor network based on particle swarm optimization ［D］.Hangzhou：Zhejiang University of Industrial，2009（in Chinese）.［林祝亮.基于粒子群算法的无线传感网络覆盖问题优化策略研究 ［D］.杭州：浙江工业大学，2009.］

［14］SUN Lijuan，DU Pengling，XIAO Pu，et al.The enhanced coverage problem of sensor network coverage based on particle swarm optimization ［J］.Journal of Computer Research and Development，2010，47 （Supply.）：22－25. ［孙力娟，杜鹏玲，肖甫，等.基于微粒群优化的有向传感器网络覆盖增强算法 ［J］. 计 算 机 研 究 与 发 展，2010，47 （Supply.）：22－25.］

［15］LU Xiaoling.Model based on particle swarm optimization deployment of wireless sensor network nodes ［D］.Taiyuan：Taiyuan University of Science and Technology，2009 （in Chinese）.［户晓玲.基于微粒群模型的无线传感器网络节点部署研究 ［D］.太原：太原科技大学，2009.］