基于虚拟力的异构无线传感器网络覆盖优化策略*

2016-09-19王婷婷孙彦景张晓光

传感技术学报 2016年8期

关键词：网络覆盖多边形步长

王婷婷，孙彦景，2*，徐　钊，张晓光

（1.中国矿业大学信息与电气工程学院，江苏徐州221116；2.江苏省煤矿电气与自动化工程实验室，江苏徐州221008）

基于虚拟力的异构无线传感器网络覆盖优化策略*

王婷婷1，孙彦景1，2*，徐钊1，张晓光1

（1.中国矿业大学信息与电气工程学院，江苏徐州221116；2.江苏省煤矿电气与自动化工程实验室，江苏徐州221008）

针对异构无线传感器网络覆盖优化过程中，固定Sink节点的虚拟作用力限制移动节点的位置移动，导致覆盖盲区得不到全局修复的问题，本文结合计算几何理论，提出基于Voronoi多边形形心引力的虚拟力覆盖优化算法（CAVFA）。虚拟力算法能有效指导移动节点的散布过程，形心引力能更好地实现全局的覆盖优化。通过合理设置虚拟力的距离阈值参数和优先级，调整固定节点对移动节点的约束。仿真表明，相比传统VFA算法和CBA算法，本文提出的CAVFA算法能够更有效地提高异构网络的覆盖率，且算法收敛速度更快。

无线传感器网络；异构网络；网络覆盖；虚拟力；优化算法

现代传感器与执行器相结合实现了传感器节点的移动，可移动的无线传感器网络WSNs（Wireless Sensor Networks）以其高度的灵活性和集成功能多样化，其应用已经渗透到军事侦察、防爆救灾、环境监测等各个领域［1-4］。覆盖是无线传感网络应用的基础，覆盖性能的好坏直接体现网络的感知、监视和通信等服务质量，覆盖算法的性能优劣同样影响着网络的生存周期。传感器节点受到能量、存储容量、计算能力、移动性等自身条件的约束限制，通常具有异构性，主要包括移动性、感知和通信能力以及能量等方面差异［5-7］。

近年来，对无线传感器网络覆盖性能优化的算法研究已有大量的成果，包括基于计算几何理论的理想节点模型约束下的无线传感网络覆盖建模方法，如基于Delaunay、Voronoi等网格划分分析方法［2-3，8-9］；仿生物学的智能群体优化算法［10-11］，以及基于物理力学原理的虚拟力算法［3，9］等。Lee 2009等［12］提出了基于泰森多边形形心的部署策略CBS （Centroid-Based Scheme），采用移动节点的分布式模式，提出基于Voronoi多边形形心的概念，设计了基于CBS（Centroid-Based Scheme）的自组织节点部署优化策略，将节点移动至本地Voronoi多边形的形心位置，覆盖性能得到一定程度的改善，但是在节点移动后容易产生新的覆盖盲区。虚拟力导向算法［3，9-10，13-14］在扩大网络覆盖范围，优化网络连接等方面表现突出。但是仅能够满足纯移动节点构成的无线传感网络的部署优化需求。

而在移动特性异构的WSN中，往往是由位置固定的Sink节点和移动传感器节点组成。在用传统虚拟力算法（VFA）进行覆盖优化时，移动节点会因为受到固定节点的虚拟力约束，难以实现覆盖区域的全局优化。为解决这一问题，王雪等［10］提出基于概率感知模型的传感器网络进行的虚拟力导向粒子群覆盖优化策略，关志艳等［14］提出虚拟力导向群居智能优化算法，虚拟力距离阈值参数来改善固定节点作用在移动节点上的虚拟力，用虚拟力影响群聚智能算法中粒子速度和距离的进化，以节点有效覆盖率为适应值，指导微粒进化。虽然虚拟力算法能有效指导移动节点的散布过程，微粒群算法具有很强的全局优化能力，能消除固定节点对全局优化的影响。但是计算耗时仍是严重制约微粒群算法在无线传感网络布局优化中应用的瓶颈之一。

为实现对异构无线传感器网络的覆盖优化，受计算几何理论启发，结合Voronoi图的特点，对虚拟力算法进行了改进，提出基于Voronoi多边形形心引力的虚拟力覆盖优化算法 CAVFA（Centroidbased Attractive Virtual Force Algorithm）。通过合理设置虚拟力距离阈值参数和优先级来改善固定节点对移动节点的约束，通过实验证明了所提算法对实现异构WSN全局覆盖的有效性。

1　问题与假设

假设无线传感器网络由N1个固定Sink节点集G和N2个移动传感器节点集S组成，移动传感器节点通过直接或间接多跳的方式连接到Sink节点，进行数据传输。节点的感知半径均为Rs，随机抛撒在监测区域A中，A为二维平面应用场景下的面积为L×H的矩形区域。节点模型均采用布尔感知模型，Rc为节点的通信半径，并满足Rc≥2Rs。对无线传感器网络参数进行如下假设：①Sink节点位置固定，并较均匀地分布在待覆盖区域中；②无线传感器网络中的所有节点初始位置可自知，第i个传感器节点Si的位置坐标为（xi，yi）；③节点的通信半径是感知半径的2倍，即Rc=2Rs，在节点通信范围内的节点为邻居节点；④网络包含一个信息处理中心节点，具有较强的计算能力，用于实现网络布局优化；⑤每个传感器节点配备移动执行器，可以在监测区域内自由移动，且有足够的能量到达指定位置，忽略边界的斥力。

2　Voronoi多边形的形心计算

将网络覆盖问题简化为二维平面中随机布散的点，为简化覆盖求解过程，借助计算几何中的Voronoi图，对这N个在平面上有区别的点，按照最邻近原则划分平面，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成，构成Voronoi图的凸多边形称为泰森多边形或者Voronoi单元，如图1（a）所示。不难发现，在每个多边形内的点到该节点的距离比到其他任何节点的距离都小。

图1　Voronoi网格图与多边形形心

泰森多边形的形心是所有将多边形平分成两个等面积区域的直线的交点［12］。如图1（b）所示，节点S所在VOR多边形包含有m个边和m个顶点，多边形顶点坐标集合为V=｛（vx1，vy1），（vx2，vy2）…（vxm，vym）｝。通过修正Lee在文献［12］中所用的形心计算方法，计算该多边形的形心（Cx，Cy），公式如下：

其中Sv为Voronoi多边形的面积，计算如下：

Voronoi多边形与目标点的覆盖情况的对应几何关系可以有效确定盲区位置［3，12］，Voronoi（简写为VOR）图是解决覆盖控制问题的一种有效的几何方法，VOR单元结构可实现局部的或者分布式算法设计，而无需已知全局信息；通过网格划分将网络覆盖优化问题转换为每个传感器节点各自覆盖对应VOR多边形区域内的优化问题，降低了问题的复杂性与计算复杂度。本文利用VOR形心的几何特性，将其引入虚拟力算法中，解决异构网络中固定节点对移动节点的束缚问题，通过引力约束，优化全局的节点覆盖率和均匀性。

3　相关算法

3.1VFA算法

虚拟力算法VFA（Virtual Force Algorithm）起源于虚拟势场［17］，起初被用于机器人移动过程中的障碍物避让，后来被引用到WSN节点部署策略中［1］，优化网络覆盖。通过将移动传感器节点虚拟成带电粒子，并假设存在一个距离阈值，当两个粒子间的距离大于该阈值，粒子间的作用力为引力；当粒子间的距离小于该阈值，粒子间的作用力为斥力。通过虚拟作用力的引导，网络可以通过节点间的距离调整，实现区域的有效覆盖，通过合理的阈值设定，达到满足部署要求的覆盖效果。假设节点Si所受的虚拟作用力包括其他节点的作用力FιJ，障碍物和边界的斥力，以及待覆盖区域中未被覆盖的点对节点的引力等，将总的斥力记为（repulsive）FιR，引力记为（attractive）FιA，节点Si所受的合力记为Fι，则有

节点间的作用力属性是由距离决定的，通常根据网络的具体应用环境以及对覆盖性能的要求进行设置。

3.2CBA算法

针对移动传感器节点分布式自组织优化算法研究中，最早由Lee 2009等［12］提出的基于VOR多边形形心的部署策略CBS（Centroid-Based Scheme），包括 Centroid和 Dual-Centroid两种模式。Dual-Centroid是将节点移动至Voronoi多边形和邻居节点构成的多边形的两个质心的线段中点处，如图2所示：A点为节点S所在VOR多边形的质心，点B为邻居节点构成的多边形的质心点，C为线段AB的中点。Centroi-Based Algorithm（CBA）是将节点移动至本地Voronoi多边形质心位置处。双质心的算法求解过程比较复杂，且覆盖优化效果并不优于CBA算法，因此本文采用CBA算法作为对比算法。

由于CBA算法是基于VOR图网格划分实现的，节点被看作分布在区域内的点，并不考虑节点的感知范围因素，在半径异构的WSN覆盖优化应用中，CBA算法并不直接适用，需要与虚拟力算法相结合，以实现更优的覆盖。

图2　基于质心的部署策略

4CAVFA算法描述

4.1受力分析

本文的网络环境包括位置固定的骨干节点和移动的传感器节点，网络初始化设定骨干节点位置，并保持静止，传感器节点在待测区域随机部署，并在虚拟力的约束下进行散布行为决策，调整网络覆盖度和冗余度。本文采用布尔圆盘感知模型，假设节点的通信半径为Rc，节点位置为中心的圆盘，质心即为该节点的坐标，记为受力点S。假设监测区域为矩形，但现实中的区域边界并不规则，因此本文忽略边界的作用力。可移动传感器节点的受力包括固定骨干节点的作用力、移动节点间的作用力、未被覆盖区域格点引力以及Vornoi多边形质心引力的作用。具体受力分析如下。

其中未被覆盖的区域中的格点Gi（gxi，gyi）对传感器节点Si（xi，yi）的作用力设为引力（attractive），Dij为Gi与Si之间的距离，记为FιA，计算如下：

节点Si所在的VOR多边形的形心Ci对节点的作用力设为引力，方向为Si到Ci连线的方向，记为FιC，计算如下：

节点Si和其他节点（可以是固定节点或者移动节点）Sj之间的作用力记为FιJ（且i≠j），作用力的性质由节点间的欧式距离决定。虚拟势场算法采用距离阈值来调整WSN节点间的相互作用力FιJ的属性，设dij是节点Si与Sj之间的欧式距离，如式（1）所示，dth是节点间通信的临界距离。当dij大于dth且小于Rc时，两者之间的作用力为引力；当dij小于dth时，作用力为斥力，FιJ关系式如式（9）所示。

其中，αij是节点Si到节点Sj线段的方向角，ka/kb分别为虚拟力引力/斥力系数。且FιJ仅在两邻居节点之间产生，即dij≤RC，减少算法计算量。已知区域一次覆盖的最佳部署方式为正三角形部署方式，如图3所示，因此本文以正三角形为覆盖目标，设置节点间的距离为。

以节点间虚拟力为例，那么节点Si所受邻居节点作用力的总和记为Fι，表达式如式（10）所示。

节点所受虚拟力Fι可分解为x与y两个方向，力的大小为Fxy，且存在如下向量关系和矢量关系：

无线传感器节点在虚拟力Fxy作用的约束下，将按照如下配置方式对节点位置进行调整：

其中，（x_old，y_old）为节点原来的位置坐标，算法每执行一轮，节点位置坐标更新为（x_new，y_new）。max_step是虚拟力步长，可分为max_grid、max_sensor、max_center，分别为在热点区域网格点、传感器节点和质心引力的作用下的半径调整步长。虚拟力算法的设计过程就是寻找使网络内部节点所受虚拟力达到平衡状态的一个过程。

图3　正三角形部署模式

4.2算法伪代码

基于上述分析，合计算几何理论，提出一种基于泰森多边形形心引力的虚拟力覆盖优化算法（CAVFA）。虚拟力算法能有效指导移动节点的散布过程，形心引力能更好地实现全局的覆盖优化。通过合理设置虚拟力距离阈值参数和优先级来改善固定节点对移动节点的约束，以实现全局的覆盖优化，提高网络覆盖效率和虚拟力算法性能。算法实现的伪代码如下。

输入：

监测区域L×H，N1个固定骨干节点坐标SN1=｛（x1，y1），（x2，y2…（xN1，yN1）｝，N2个移动传感器节点的坐标的集合SN2=｛（x1，y1），（x2，y2…（xN2，yN2）｝，节点感知半径Rs，迭代次数max-iteration，节点间的距离阈值 dth，最大移动步长 max_sensor、max_grid、max_center，虚拟力阈值fth.

输出：移动传感器节点坐标SN2，覆盖率fth.

算法描述：

（1）SN1；rand（SN2）；//初始化部署

（2）while（t＜max-iteration）

（3）Fι←0，FιJ←0，FιC←0，FιA←0；

（4） VOR网格划分，根据式（4）、式（5）计算每个V单元的质心Ci（cxi，cyi）；

（5）for（i=0；i＜N2；i++）

（6）if（cxi，cyi）∈A

（7）根据式（7）进行FιC计算；

（8）根据式（11），带入max_center进行节点虚拟移动；

（9）end

（10）end

（11） for（i=0；i＜N2；i++）

（12）计算节点间的距离dij

（14）按式（8）进行FιJ计算

（15）根据式（11），带入max_sensor进行节点虚拟移动；

（16）end

（17） end

（18） for（i=0；i＜N2；i++）

（19）计算未被覆盖格点与节点间距离Dij

（20）if Dij＜Rc

（21）按式（6）计算引力FιA

（22）根据式（11），带入max_grid进行节点虚拟移动；

（23） end

（24） end

（25）更新节点位置，进行位移移动，计算覆盖率

（26）循环迭代

（27）end%算法结束

5　仿真结果及性能分析

本节通过仿真来验证算法对提高网络覆盖质量的有效性，并对算法性能进行分析，包括收敛性能、复杂性，及其影响参数的讨论。本章的算法是针对节点异构的移动无线传感器网络进行的覆盖优化，通过引入VOR形心约束力对节点的移动进行干预，提高感知覆盖率的同时，加速了算法收敛。与VFA和CBA算法进行了对比分析，结果验证了VOR形心引力导向对虚拟力算法性能改进的有效性。本节中的仿真实验均是在Matlab R2012b环境下进行的，仿真实验参数设置如表1所示。

文献［18］在对距离阈值调节虚拟力属性的模型的研究中指出，用到的虚拟力的引力系数和斥力系数几乎是与覆盖率不相关，故设为相同的常数值。考虑到覆盖算法的能效性，节点的最大移动步长一般取感知半径的1/2［10］。本文通过几组步长值对覆盖率的优化效果对比分析实验，从经验值中选取了对算法有利的步长值，作为下一步的实验仿真参数。

表1　仿真实验参数

首先对几个参数对算法性能的影响进行分析，包括最大移动步长，固定和移动节点数量分配。图4所示为4组不同的最大移动步长设置条件下的覆盖有效效果图，参数设置如表2所示，且其他参数设置为Rs=7 m，N1=16，N2=60，初始化覆盖率为67%，算法运行100次以后的覆盖率分别为80%，85%，90%，89%。

图4　CAVFA算法运行时待监测区域覆盖情况，绿色为固定节点，蓝色的为移动传感器节点

表2　参数对优化性能的影响

仿真结果表明适当减小最大移动步长，覆盖率有一定程度的提高，且当max_grid＞max_center时的覆盖效果最佳。第4组数据表明移动步长并不是越小越好。在后面的算法对比分析中都选用第3组步长设置。

部署在待覆盖区域的节点总数为100个，分析固定节点和移动节点的不同分配方式对算法性能的影响，选取两组数据，并与VFA和CBA算法进行了性能对比，如图5和表3所示。仿真结果显示，在N1= 80，N2=20的条件下，经过100次循环后，CAVFA算法所能提高的覆盖率百分比为16%，VFA和CBA算法分别能提高的覆盖率百分比为15%和12%，CAVFA性能略优于其他算法；在N1=40，N2=60的条件下，经过100次循环后，CAVFA算法提高了覆盖率的31%，明显优于其他两种算法的覆盖效果28%和27%。从图5（d）可以看出，即使在固定节点数远多于传感器节点数时，CAVFA也能实现全局的均匀覆盖，这是因为通过Voronoi网格划分提高了节点覆盖的公平性，进而解决了固定节点对移动节点的约束问题。

图5　VFACBACAVFA算法覆盖优化效果图

表3　固定节点与移动节点数的分配

算法运行时间和收敛性的比较与分析，如图6所示，描绘了待监测区域内的覆盖率在覆盖优化算法随执行时间的变化情况，节点数：N1=40，N2=60，算法运行时间：T_CAVFA=40 s，T_CBA=28 s，T_VFA= 30 s。虽然CAVFA算法运行100次所需的时间大约为40 s，耗时比CBA和VFA各自的运行时间长，但是本文所提的算法完成了对形心和虚拟力的遍历搜索，并且耗时小于CBA与VFA算法之和，这说明本文的算法迅速有效。从图6可以看出前5个步长内，待监测区域的覆盖率均得到了较大幅度的提升，其中本文提出的CAVFA算法与初始覆盖率相比提高了22个百分点，并高于VFA和CBA算法。在5个步长以后，CAVFA算法对覆盖率的优化效果减慢，但仍有提升的空间，并趋于平稳；而VFA优化效果不稳定，随着步长的增加反而出现了下降的趋势；CBA算法的优化性能趋于平缓。三种算法在10个步长以后均趋于收敛。由此可见本文提出的算法CAVFA结合了VFA和CBA算法的优点，充分利用虚拟力算法的全局搜索特性，又将局部单元优化方法引入，克服了传统虚拟力算法优化过程中出现的局部节点聚焦的现象，从而实现了对待监测区域高效、均匀的覆盖。

图6　算法运行100次所需的时间与覆盖率的关系图

6　总结

基于Voronoi多边形形心引力的虚拟力优化的异无线传感器网络覆盖策略在传统虚拟力算法的基础上，引入了基于计算几何理论中的Voronoi多边形形心的虚拟引力，通过调整虚拟力距离阈值参数、节点移动步长和虚拟力优先级等参数设置，来改善来克服固定节点对移动节点的虚拟力作用限制。通过实验验证了本算法的有效性，结果表明：相比传统虚拟力算法和基于Voronoi形心的覆盖优化策略，基于Voronoi多边形形心引力的虚拟力优化算法实现了对异构无线传感器网络的全局部署优化，且覆盖效率最高，收敛更快。但是由于本实验环境所有节点初始化部署的随机性，算法执行过程中并没有实现百分之百的覆盖率，算法中的参数设置对实验结果的影响，有待下一步继续研究。

［1］Zhu C，Zheng C，Shu L，et al.A Survey on Coverage and Connectivity Issues in Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（2）：619-632.DOI：10.1016/ j.jnca.2011.11.016

［2］Sung T，Yang C.Distributed Voronoi-Based Self-Redeployment for Coverage Enhancement in a Mobile Directional Sensor Network ［J］.International Journal of Distributed Sensor Networks，2013，2013：1-15.DOI：10.1155/2013/165498

［3］Ye G，Zhang B，Wen L，et al.Extended Virtual Force-Based Coverage Scheme for Heterogeneous Wireless Sensor Networks［C］//2014 14th International Conference on Control，Automation and Systems （ICCAS 2014）.KINTEX，Gyeonggi-do，Korea，2014：1560-1564

［4］Jiang H，Sun Y，Sun R，et al.Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2013，2013：1-8.DOI：10.1155/2013/216561

［5］杜晓玉，孙力娟，郭剑，等.异构无线传感器网络覆盖优化算法［J］.电子与信息学报，2014（3）：696-702.

［6］Donmez M Y，Kosar R，Ersoy C.An Analytical Approach to the Deployment Quality of Surveillance Wireless Sensor Networks Considering the Effect of Jammers and Coverage Holes［J］.Computer Networks，2010，54（18）：3449-3466.DOI：10.1016/j.comnet. 2010.07.007

［7］孙彦景，林昌林，江海峰.一种能量高效的分布式非均匀分簇路由算法［J］.传感技术学报，2015，28（8）：1194-1200.

［8］Al-Turjman F M，Hassanein H S，Ibnkahla M.Quantifying Connectivity in Wireless Sensor Networks with Grid-Based Deployments［J］.Journal of Network and Computer Applications，2013，36（1）：368-377.DOI：10.1016/j.jnca.2012.05.006

［9］江海峰，钱建生，孙彦景.WSN中基于虚拟静电场的多Sink路由算法［J］.中国矿业大学学报，2011（02）：321-326.

［10］王雪，王晟，马俊杰.无线传感网络布局的虚拟力导向微粒群优化策略［J］.电子学报，2007，35（11）：2038-2042.

［11］张智威，孙子文.基于蚁群算法的无线传感器网络节点可信安全路由［J］.传感技术学报，2016，29（2）：256-263.

［12］Lee H，Kim Y，Han Y，et al.Centroid-Based Movement Assisted Sensor Deployment Schemes in Wireless Sensor Networks［C］// 2009 IEEE 70thVehicular Technology Conference Fall（VTC 2009-Fall）.2009：1-5.DOI：10.1109/VETECF.2009.5379087

［13］冯秀芳，关志艳，全欣娜.基于虚拟力的异构节点网络覆盖增强算法［J］.计算机工程，2009（5）：103-105.

［14］关志艳，耿岩.虚拟力导向群聚智能优化的无线传感器网络覆盖策略［J］.传感器与微系统，2015（1）：40-42.

［15］Wang G，Cao G，La Porta T F.Movement-Assisted Sensor Deployment［J］.IEEE Transactions on Mobile Computing，2006，5（6）：640-653.

［16］S K S，M S.Coverage Rate Calculation in Wireless Sensor Networks［J］.Computing，2012，94（11）：833-856.

［17］A H，Matarimj，Sukhatmegs.An Incremental Self-Deployment Algorithm for Mobile Sensor Networks［J］.Autonomous Robots 2002，2002，13（1）：13-26.DOI：10.1023/A：1019625207705

［18］任孝平，蔡自兴，任清雄.四种虚拟力模型在传感器网络覆盖中的性能分析［J］.信息与控制，2010（4）：441-445.

王婷婷（1986-），女，江苏连云港，博士研究生，主要研究无线传感器网络及智能优化算法等；

孙彦景（1977-），男，山东滕州，博士，教授，博士生导师，主要研究无线传感器网络，信息物理系统及感知物联网等，yjsun@cumt.edu.cn；

徐钊（1955-），男，江苏宿迁，教授，博士生导师，主要研究数字矿山综合传输网络及无线通信系统等；

张晓光（1978-），女，辽宁昌图，副教授，硕导，主要研究无线通信和数字信号处理。

Coverage Optimization Algorithm Based on Virtual Force for Heterogeneous Wireless Sensor Networks*

WANG Tingting1，SUN Yanjing1，2*，XU Zhao1，ZHANG Xiaoguang1
（1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China；2.Coal Mine Electrical Engineering and Automation Laboratory in Jiangsu Province，Xuzhou Jiangsu 221008，China）

In heterogeneous wireless sensor networks with diversified mobility，the global optimization of coverage usually can’t be achieved because that the mobility of mobile sensor nodes will be constrained by the fixed ones.In order to solve this problem，we propose a Centroid-based Attractive Virtual Force Algorithm（CAVFA）inspired by computational geometry theory.The traditional Virtual Forces Algorithm（VFA）has been used to guide mobile nodes to move.And the Centroid-based algorithm（CBA）has potential to improve networks coverage in the whole interest of area.Also parameters including distance thresholds and priorities of virtual forces have been set to adjust the binding effect between fixed nodes and mobile ones.Simulation results are presented to demonstrate that the proposed CAVFA strategy has higher coverage rate and convergent speed than VFA and CBA strategies.

wireless sensor networks；heterogeneous network；network coverage；virtual force；optimization algorithm EEACC：6150P；7230

10.3969/j.issn.1004-1699.2016.08.022

TP393

1004-1699（2016）08-1253-07

项目来源：国家自然科学基金项目（51274202）；国家自然科学基金青年项目（51504255，51504214）；江苏省自然科学基金项目（BK20130199，BK20131124）

2016-02-14修改日期：2016-04-05