无线传感网中基于特征点集的虚拟力覆盖优化

侯义飞 杨勇

摘要：无线传感网的覆盖率通常利用覆盖区域中稠密的网格点来近似计算，导致了计算量庞大。因此，提出了一种基于特征点集的无线传感网虚拟力覆盖优化算法。该算法引入了特征点集的概念，并结合虚拟力算法，将网络节点对区域网格点的覆盖计算转化为对若干特征点的覆盖计算，利用有限的特征点的覆盖情况去描述整个网络，从而达到减小计算量的目的。实验结果表明：与传统基于网格点的虚拟力算法相比，在满足区域覆盖要求的同时，算法执行效率明显提升，运行时间缩短了56.55%。

关键词：无线传感网;无线传感网;特征点集;虚拟力算法

中图分类号：TP393文献标识码：A

文章编号：1009-3044（2020）16-0003-05

开放科学（资源服务）标识码（OSID）：

Abstract： The coverage of wireless sensor networks is usually approximated by the use of dense grid points in the coverage area， resulting in a lot of computation. Therefore， a virtual force coverage optimization algorithm for wireless sensor networks based on feature point sets is proposed. The algorithm introduces the concept of feature point set， and combines the virtual force algorithm to transform the coverage calculation of the network nodes to the regional grid point into the coverage calculation of several feature points， which uses the coverage of the limited feature points to describe the whole network， so as to reduce the calculation amount. The experimental results show that compared with the traditional grid-based virtual force algorithm， while meeting the regional coverage requirements， the algorithm execution efficiency is significantly improved， and the running time is shortened by 56.55%.

Key words： Wireless sensor network; Network coverage; Feature point set; Virtual force algorithm

無线传感器网络[1]（Wireless Sensor Networks，WSN）是大量具有传感、数据处理、无线通信和计算能力的低成本、低功耗的微型传感器节点通过自组织方式形成的，广泛应用于大型农场的安全监测，环境监测和预报，大型车间和仓库管理等方面。然而，在对大规模监控区域进行节点部署时，通常采用随机部署的方式，容易造成区域内节点过密或过疏[2]，进而导致区域存在覆盖冗余和监测盲点。因此，网络覆盖问题作为WSN中的基本问题，有着重要的研究意义。

目前，有关覆盖问题的许多成果大多是基于布尔感知模型，如文献[3-4]。布尔感知模型是一种理想化的模型，但传感器在实际监测目标时，监测范围与传感和通信半径有一定的概率关系，因此，选用基于概率感知模型更符合实际情况，文献[5]在概率感知模型的基础上提出了一种分布式k重覆盖算法。类似地，文献[6]提出一种基于改进虚拟力算法概率感知模型的部署方法。在选定感知模型后，学者对覆盖优化算法进行了深入的研究，覆盖优化算法有虚拟力算法，人工势场法，群体智能算法等。群体智能算法包括粒子群算法[7-9]，遗传算法等。但是群体智能算法依靠群体合作进行寻优，存在计算量较大的缺点。而且若节点分布不均，监测区域将存在覆盖冗余和监测盲点，不仅影响数据传输的可靠性，且导致不必要的能量消耗。在移动传感器节点部署算法中，虚拟力算法 [10]只依据周围临近节点分布情况动态地调整自身位置，使整个网络覆盖趋向均匀。因此，许多学者对虚拟力优化算法进行了研究，使区域中节点分布均匀，提高网络区域的覆盖率。文献[11]基于虚拟力算法最大化区域的覆盖率。文献[12]在力函数上加约束条件，提出了一种分布式虚拟力算法。在节能方面，文献[13]推导建立了多目标非线性规划数学模型，提出一种节能的虚拟力优化算法。然而，虚拟力算法部署传感器节点时，容易陷入局部受力平衡，使节点来回移动，文献[14]提出一种虚拟力导向微粒群的有向覆盖增强策略，加快收敛到全局最优解。此外，一些新兴的智能算法，如人工蜂群算法[15]也已经应用于覆盖问题当中。

针对传统基于网格点虚拟力算法求解网络覆盖率受网格点的精度影响，导致计算量大的缺点。在特征点集概念的基础上，将特征点集与传统的虚拟力算法结合，将传统的区域覆盖问题转化成了对特征点集优化覆盖问题，通过求解传感器对特征点的覆盖率，等价分析整个区域的覆盖。通过实验证明了文中算法相较于传统虚拟力算法降低了复杂度，减少了运行时间和计算量。这是一种比较新颖的结合方式，并且能够较好地满足覆盖要求。

1网络覆盖模型建立

为了便于研究网络覆盖首先做以下假设：

（1）无线传感器网络中的传感器节点全部是可以自由移动的。（2）移动节点的能源充足，能够完成位置的更新。（3）传感器类型全部是同构类型，通信半径Rc是感知半径Rs的2倍。

无线传感器网络部署模型中最常用的模型是布尔感知模型，也叫0-1圆盘模型，它是一种理想化的覆盖模型，但传感器在实际监测目标时，传感器的感知能力随着传感器节点与目标距离的增大而逐渐减小甚至无法感知，概率感知模型更符合实际监测环境，因此选用概率感知模型。

首先假设传感器节点s的位置为（x，y），目标物体m的位置（xm ，ym），那么它们之间的距离d（s，m）则可以表示为：

2基于特征点集虚拟力的覆盖优化

在介绍特征点集之前，首先介绍点覆盖问题。通过分析点覆盖问题，可以扩展到研究整个区域覆盖问题。

2.1特征点的定義与选取

传统方法求解网络覆盖率比较难，因为传感器节点之间有重叠且重叠的面积不规则。因此，一些学者就提出基于网格点虚拟力算法[19-20]求解网络的覆盖率，此方法求解覆盖率，会受到网格点大小的影响，网格点越小，算法复杂度越高，算法的运行时间就越长。网格点选取越大，则精度就会不高。在特征点集的基础上，通过计算传感器节点对特征点的联合覆盖率，进而求出整个区域的网络覆盖率。将传统的求区域覆盖率转化为对特征点集的覆盖率，降低了算法的复杂度，缩短了算法的运行时间。因此，本文在特征点、特征点集的概念基础上来求解无线传感器网络中的覆盖率。

通过式（6）可以得出，区域内任意一点都至少被一个特征点所覆盖，能够求出每个特征点的联合覆盖率和其中的最小值。

2.2 传统虚拟力算法模型

虚拟力算法[21]（Virtual Force Algorithm，VFA）是把移动传感器节点看成是带电粒子，节点间有万有引力，也有斥力的作用。当传感器节点间的距离小于某一值时，传感器节点间表现为斥力，当传感器节点间的距离大于某一值时，传感器节点间表现为引力。一个节点所受到的虚拟力是区域内所有传感器节点所施加的虚拟力的合力，合力的大小和方向决定节点的移动距离和方向，节点在合力的作用下移动到合适的位置，使区域内的节点分布比较均匀，进而完成良好的部署。

2.3 基于特征点集虚拟力覆盖优化

传统的虚拟力算法可以使传感器节点更快地从密集区域扩散开来，且每个节点移动的距离更短，节省了节点的能量并延长了网络的寿命。然而，传感器节点可能因受力平衡而产生局部来回移动，使得传感器节点没有移动到合适的位置。还有，节点在移动时存在能耗差异，使得节点能耗不均匀，算法复杂度更高，使算法收敛速度下降。

本文中的算法是基于网格点的虚拟力算法，此算法求解网络覆盖率，精确度取决于选取网格的大小，网格选取的越小，计算复杂度就越大，拓展性也越差。

针对以上问题，通过研究两点间覆盖率的关系，将特征点集的概念与虚拟力算法结合起来，把传统的区域覆盖转化为对特征点集的覆盖优化问题，利用有限的特征点的覆盖情况去描述整个网络，并且能够保证区域内的覆盖要求。同时，降低了算法的复杂度，加快收敛速度，减少计算量。

算法流程如图4所示：

3仿真实验

3.1 仿真设置

在100m×100m的区域大小内，传感器的个数为N=25。传感器感知半径Rs=15 m，传感器参数Re=1/3Rs，α1=β1=β2=1，α2=0，迭代次数为100。传感器节点在网格点作用下移动的最大步长max step=2.5 m，传感器在传感器节点的作用下移动的最大距离max sensor=4.5 m。概率阈值为0.7，由推论1[17]可得 MFPD≤10.42，所以MFPD取10。

3.2 实验结果与分析

对所提的算法进行仿真分析，图5是传感器节点数为25初始化的位置分布图。在进行100次迭代之后，从图6可以看出最终可以满足区域覆盖的要求。图7是迭代100次后的覆盖率变化曲线。

加入特征点集的目的是把传感器对区域的覆盖转化为对特征点的覆盖，可以证明每个被覆盖的传感器节点的覆盖率都大于或等于其周围的覆盖率。因此，通过研究分析求解传感器对特征点的覆盖率，可以清楚整个区域的覆盖情况。

图8是区域内传感器节点对每个特征点进行覆盖的覆盖率，最小覆盖率的大小是0.743。从图中可以看出，每个传感器对区域内的特征点集的覆盖效果好，覆盖率高。

另外，为了防止传感器节点的个数对实验有影响，选取了三种不同传感器节点个数得到了如图9所示的网络覆盖图，结果表明选取传感器节点N=25适合算法的要求，既能满足区域的覆盖要求，又能不造成大量的覆盖冗余。

为了避免实验的随机性对结果造成的误差，选取10次独立实验，求取最小覆盖率和程序运行时间的均值和标准差，从图10的运行时间对比图可以得出加入特征点集后算法的运行时间明显加快。另外，基于网格点虚拟力运行10次的总时间为56.407s，加入特征点集的算法运行10次的总时间为31.9024s，运行时间提高了56.55%。

4 结论

本文在基于特征点集概念的基础上，将特征点集与虚拟力算法结合在一起，将传统区域覆盖问题转化为对特征点集的覆盖，也是求解覆盖率的一种新的方法。实验仿真结果表明，本文所提出的方法相比较传统的网格点求覆盖率能明显减少算法的运行时间，能够较快地使网络达到稳定状态，并且具有较高的覆盖率。今后将进一步研究特征点集的选取对覆盖率的影响。

参考文献：

[1] 陈宇晨. 基于AUV的无线传感器网络覆盖研究及应用[D]. 南京： 南京邮电大学， 2014.

[2] 邵晶. 基于地理位置的WSN拓扑控制研究[D]. 成都： 电子科技大学， 2010.

[3] Hefeeda M，Bagheri M.Randomized k-coverage algorithms for dense sensor networks[C]//IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications，May 6-12， 2007. Anchorage， AK， USA. IEEE， 2007： 2376-2380.

[4] 刘明，曹建农，郑源，等.无线传感器网络多重覆盖问题分析[J].软件学报，2007，18（1）：127-136

[5] 蒋丽萍，王良民，熊书明，等.基于感知概率的无线传感器网络k重覆盖算法[J].计算机应用研究，2009，26（9）：3484-3486，3489.

[6] 李強懿，马冬前，张聚伟.基于感知概率的无线传感器网络节点部署算法[J].计算机测量与控制，2014，22（2）：643-645.

[7] Wan Ismail W Z，Abd Manaf S.Study on coverage in Wireless Sensor Network using grid based strategy and Particle Swarm Optimization[C]//2010 IEEE Asia Pacific Conference on Circuits and Systems，December 6-9， 2010. Kuala Lumpur， Malaysia. IEEE， 2010： 1175-1178.

[8] Kennedy J，Eberhart R.Particle swarm optimization[C]//Proceedings of ICNN'95 - International Conference on Neural Networks，Perth， WA， Australia. IEEE， 10.1109/icnn.1995.488968.

[9] 谢佳华，刘军.无线网络通信覆盖优化仿真研究[J].计算机仿真，2015，32（6）：271-275.

[10] 张涛，余翔宇，蓝俊健，等.改进的无线传感器网络节点虚拟力部署方法[J].计算机应用研究，2015，32（11）：3356-3358，3363.

[11] Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces[J].Proceedings - IEEE INFOCOM，2003，2（1）：1293-1303.

[12] Tsai R G，Kuo H C，Wang H L，et al.Target coverage QoS control with multiple sensing units in wireless heterogeneous sensor networks[C]//2012 Sixth International Conference on Sensing Technology （ICST），December 18-21， 2012. Kolkata. IEEE， 2012： 428-433.

[13] 田一鸣，陆阳，魏臻，等.无线传感器网络虚拟力覆盖控制及节能优化研究[J].电子测量与仪器学报，2009，23（11）：65-71.

[14] 范兴刚，王恒，张兆娟，等.一种基于虚拟力导向微粒群的有向传感器网络覆盖增强策略[J].传感技术学报，2015，28（11）：1720-1726.

[15] 文政颖，翟红生.基于混沌人工蜂群算法的无线传感器网络覆盖优化[J].计算机测量与控制，2014，22（5）：1609-1612.

[16] 刘维亭，范洲远.基于混沌粒子群算法的无线传感器网络覆盖优化[J].计算机应用，2011，31（2）：338-341.

[17] 丁旭，吴晓蓓，黄成.基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[J].电子学报，2016，44（4）：967-973.

[18] Yang Q Q，He S B，Li J K，et al.Energy-efficient probabilistic full coverage in wireless sensor networks[C]//2012 IEEE Global Communications Conference （GLOBECOM），December 3-7， 2012. Anaheim， CA， USA. IEEE， 2012： 591-596.

[19] LI Hui， ZHANG Xiao-guang， et al. A hybrid deployment algorithm based on clonal selection and artificial physics optimization for wireless sensor network[J]. Information Technology Journal， 2013， 12（5）： 917-925.

[20] Shen X F，Chen J M，Sun Y X.Grid scan：a simple and effective approach for coverage issue in wireless sensor networks[C]//2006 IEEE International Conference on Communications，June 11-15， 2006. Istanbul. IEEE， 2006： 3480-3484.

[21] Wang X B，Han S H，Wu Y B，et al.Coverage and energy consumption control in mobile heterogeneous wireless sensor networks[J].IEEE Transactions on Automatic Control， 2013，58（4）：975-988.

[22] 李贤，何启丽，唐秋玲，等.一种基于网格划分的虚拟力部署算法的研究[J].广西大学学报（自然科学版），2012，37（6）：1164-1169.

【通联编辑：梁书】