基于IRVFA算法的无线传感器网络节点部署

滕志军，徐苗苗，张　力

(东北电力大学 信息工程学院，吉林 吉林 132012)



基于IRVFA算法的无线传感器网络节点部署

滕志军，徐苗苗，张力

(东北电力大学 信息工程学院，吉林 吉林 132012)

摘要：针对无线传感器网络节点再部署中网络覆盖率和节点的有效利用率低问题，提出基于IRVFA算法的无线传感器网络节点部署策略，建立了节点分布最佳模型，同时在RVFA算法的基础上，引入虚拟引力线，使得网络节点能够快速均匀的分布在整个目标区域内，该策略可以实现同时提高网络覆盖率和节点的有效利用率。实验中通过将IRVFA算法与VFA算法、RVFA算法相比较，其在网络覆盖率和节点的有效利用率方面有明显优势，网络性能得到很大提升。

关键词：无线传感器网络；虚拟引力线；网络覆盖率；有效利用率

近年来专家学者在节点部署优化领域已开展了大量卓有成效的研究[1-2]。金仁成等提出了基于虚拟力算法(Virtual Force Algorithm，VFA)的无线传感器网络分簇部署策略，提高了网络覆盖率，算法增加了网络能量消耗，没能最大化网络生存周期[3]。Novella等提出了改进的虚拟力算法，该算法使得个别节点受到外界入侵损坏时，剩余节点依然能保证整个网络的覆盖率，但增加了节点数目和算法的复杂度[4]。传统的粒子群算法容易提前进入部署优化的极大值，限制了粒子搜索范围，赵娜等提出了改进的粒子群算法，能够实现无线传感器网络节点的最佳布局，该算法的收敛速度慢，节点需要多次移动，导致能量过快消耗[5]。

本文提出一种基于优化的可信度虚拟力算法(Improved Reliability-Based Virtual Force Algorithm，IRVFA)的节点部署策略，其适用于节点数目固定、初始随机中心部署的情况，如在监测区域中心初始随机抛洒一定数量的节点，然后通过该优化算法把节点快速有效地扩散到整个目标区域中。

1数学模型及算法描述

假设所有的传感器节点均具有相同的通信半径rc，当两节点间的欧式距离小于它们的通信半径rc时，两个传感器节点就可以相互通信[6]；当目标区域中的任意点p与节点vi的欧式距离小于节点的感知半径rs时，点p能被节点vi感知覆盖。

1.1覆盖率及节点有效利用率度量

覆盖率是传感器网络部署优化问题中的一个重要性能指标[7-8]，定义覆盖率为每一个传感器节点所覆盖区域的并集与整个监测区域面积的比值。节点的有效利用率为每一个传感器节点所覆盖区域的并集与所有传感器节点所覆盖区域的代数和的比值。

假设目标区域中传感器节点vi的位置坐标是Pi=(xi，yi)，Ci为传感器节点vi在目标区域T中的覆盖范围，目标区域的面积为A，目标区域中节点总数为N，则所有传感器节点总的覆盖范围可以表示为：

(1)

目标区域的覆盖率可表示为：

(2)

目标区域中节点的有效利用率可表示为：

(3)

1.2IRVFA优化算法

RVFA算法虽然提高了网络的覆盖率，降低了网络的移动能耗，但在满足一定覆盖率的条件下，所使用的节点数不是理论上的最小数目，也就是节点的有效利用率并不高。

图1　正六边形节点覆盖模型

图2　辅助虚拟引力线

以提高节点利用率为目的，建立正六边形节点覆盖模型，每个正六边形都是单个传感器节点的感知区域的内接正六边形，也即是每个正六边形的中心就是传感器节点的位置，如图1所示。

在目标区域的边界处假设存在虚拟的主导引力线，如图2中虚线所示，该引力线对目标区域内的各节点具有引力作用，吸引各节点往边界靠拢，同时，由于该主导引力线的引力作用，也能有效地防止节点移出目标区域。从监测区域的一边到另一边将正六边形中心用直线连接起来，这样正六边形都是分布在直线上的。由于正六边形是各传感器节点感知区域的内接正六边形，所以相当于传感器节点分布在直线上。假设这些直线为虚拟存在的辅助引力线，这些辅助引力线对传感器节点也具有一定的引力作用，同时同一引力线上和相邻引力线上的节点具有一定的斥力作用，这样可以促使节点快速均匀的分布在各引力线上。只要传感器节点能均匀分布在辅助引力线上，理论上可以实现对目标区域的无缝覆盖，同时最大化节点利用率，虚拟引力线的构造如图2所示。

在IRVFA算法中，节点vi所受合力大小如公式(4)所示。

(4)

2实验结果及分析

在保证网络连通且节点数目相同的情况下，本文从网络覆盖率、节点的有效利用率方面，利用MATLAB仿真平台对IRVFA算法、RVFA算法和 VFA算法进行仿真对比分析。

在100×100 m2的无障碍目标区域中，随机中心抛撒140个节点。传感器节点的感知半径为8 m，依次执行IRVFA算法、RVFA算法和 VFA算法40次，所得各算法在相同迭代次数下的平均覆盖率和节点的平均有效利用率分别如图3和图4所示。

图3 平均覆盖率图4 节点平均利用率

从上图可以看出IRVFA算法在平均网络覆盖率方面均高于VFA算法和RVFA算法。由此可以看出，IRVFA算法使得监测区域的网络覆盖率得到很大优化。

从上图可以看出IRVFA算法在节点的平均利用率方面均高于VFA算法和RVFA算法。由此可以看出，IRVFA算法使得监测区域内的节点有效利用率得到很大优化。

3结论

本文在通过深入研究RVFA算法的基础上，提出一种基于优化的可信度虚拟力算法(IRVFA算法)，针对节点部署中网络覆盖率和网络节点的有效利用率方面存在的不足之处，建立了节点分布最佳模型，同时在RVFA算法的基础上，引入虚拟引力线，使得网络节点能够快速均匀的分布在整个目标区域内。为了验证该算法是否适应课题的要求，使用MATLAB仿真软件平台分别对该算法、RVFA算法和VFA算法进行仿真，通过实验结果的比对和分析，可以看出相比于RVFA及VFA算法，该优化算法在相同节点数目情况下对目标区域的覆盖率和网络节点的有效利用率方面具有一定的提升。

参考文献

[1]李建坡，钟鑫鑫，徐纯.无线传感器网络动态节点定位算法综述[J].东北电力大学学报，2015，35(1)：52-58.

[2]李建坡，钟鑫鑫，徐纯.无线传感器网络静态节点定位算法综述[J].东北电力大学学报，2015，35(2)：73-82.

[3]金仁成，韦宁，徐浩，王立鼎.基于虚拟力的无线传感器网络分簇部署策略[J].东北大学学报：自然科学版，2014，35(5)：640-644.

[4]Novella Bartolin，Giancarlo Bongiovanni，Thomas F.La Porta，Simone Silvestri.On the Vulnerabilities of the Virtual Force Approach to Mobile Sensor Deployment[J].IEEE Transactions on Mobile Computing，2014，13(11)：2592-2605.

[5]童孟军，俞立，郑立静等.基于蚁群算法的无线传感器网络能量有效路由算法研究[J].传感技术学报，2011，24(11)：1632-1638.

[6]方伟，宋鑫宏.基于Voronoi图盲区的无线传感器网络覆盖控制部署策略[J].物理学报，2014，63(22)：220701.

[7]张文爱，刘丽芳，李孝荣.基于粒子进化的多粒子群优化算法[J].计算机工程与应用，2008，44(7)：51-53.2011，24(11)：1632-1638.

[8]Cheng-Chih Yang，Jyh-Horng Wen.A Hybrid Local Virtual Force Algorithm for Sensing Deployment in Wireless Sensor Network[C].2013 Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing.

Nodes Deployment in Wireless Sensor Networks Based on Improved Reliability Virtual Force Algorithm

TENG Zhi-jun，XU Miao-miao，ZHANG Li

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：In this paper，we propose an improved reliability-based virtual force algorithm for solving the low coverage and low effective utilization of node deployment in wireless sensor network，the best model of node distribution is established，At the same time，the virtual gravity line is introduced，based on the RVFA algorithm，which enables the network nodes to distribute in the entire target area quickly and evenly.This method can improve the network coverage and the effective utilization of the nodes.The simulation results show that IRVFA algorithm has obvious advantages compared with RVFA algorithm and VFA algorithm in coverage rate and effective utilization of the nodes，network performance is improved significantly.

Key words：Wireless sensor network；Virtual gravity line；Coverage；Effective utilization

收稿日期：2016-01-12

基金项目：国家自然科学基金(51277023)

作者简介：滕志军(1973-)，男，吉林省吉林市人，东北电力大学信息工程学院教授，博士，主要研究方向：无线通信技术.

文章编号：1005-2992(2016)02-0086-04

中图分类号：TN915

文献标识码：A