无线传感器网络动态覆盖的CVT 算法*

刘志强，沈廼桐，毛 强，魏洪兴

(1.内蒙古工业大学 信息工程学院，内蒙古 呼和浩特010051;2.北京航空航天大学 机械工程及自动化学院，北京100191)

0 引 言

网络覆盖是无线传感器网络研究的基本问题之一，它决定了无线传感器网络对目标区域的监测能力，通过覆盖控制可以使资源得到合理配置。针对无线传感器网络的目标区域覆盖问题，前人已做了一些深入的研究。文献［1］提出了一种虚拟力算法(virtual force algorithm)，通过随机节点的相互作用，实现网络覆盖范围最大化。文献［2］提出了一种基于蜂窝网格的传感器节点部署算法。文献［3］提出基于贪婪算法和Voronoi 图的多媒体节点传感方向调整方案，并为有效降低无线多媒体传感器网络能耗，提出一种基于多目标遗传优化的节能覆盖方法。文献［4］基于Voronoi 图特性和自适应有向传感器节点，提出了一种分布式贪婪算法，它能够提高有向无线传感器网络的覆盖效率。文献［5］针对二维静态随机分布的无线传感器网络，提出了一种通过Voronoi 图判定网络的覆盖性能并在需要时添加覆盖补救节点的方法。文献［6］详细介绍了集中式Voronoi 网格细分(centralized Voronoi tessellation，CVT)算法原理并给出了其在图像压缩、动物领地等方面中的应用。文献［7］基于CVT 方法，提出了一种多传感器节点网络系统算法，通过调节节点分布密度函数使得各个传感器节点按需求分布。然而，面对较复杂的无线传感器网络区域环境，无线传感器网络覆盖问题需要进一步研究。

受Voronoi 图和CVT 的启发，本文提出了一种基于CVT 的无线传感器网络动态覆盖算法。与文献［6，7］通过改变区域分布密度的方法不同，本文结合Voronoi 图特性，不断缩放覆盖区域边界至目标覆盖区域，系统协同调动各传感器节点至目标位置，从而完成目标区域的覆盖，仿真验证了该算法的有效性和可行性。

1 基于CVT 的无线传感器网络覆盖模型和算法分析

1.1 无线传感器网络覆盖假设

本文主要针对二维平面区域的无线传感器网络覆盖进行研究，网络模型和基本假设如下:

1)各个传感器节点初始随机分布在任意二维封闭区域内。

2)各个传感器节点能够随时确定自身的位置和方向，并能准确移动至指定的目标位置，能感知以节点为中心，以Rs为半径的圆形区域。

3)各个传感器节点是同构的，有相同的通信和覆盖能力。

4)Rc≥2Rs，即各个传感器节点的通信半径Rc不小于2 倍的传感器感知半径Rs。

1.2 理论基础

覆盖程度C:是指在目标覆盖区域内，所有传感器节点覆盖的总面积与目标区域总面积的比值。计算公式为

其中，A 为目标覆盖区域总面积，N 为传感器节点总数，Ai为第i 只传感器节点的覆盖面积。

有效覆盖效率(effective coverage efficiency，ECE)用来衡量传感器节点覆盖范围的利用率，用来反映有效覆盖区域的情况，定义为目标覆盖区域中，所有传感器节点有效覆盖区域的并集与所有传感器节点覆盖区域之和的比值，计算公式为

Voronoi 图是由俄国数学家Georgy Fedoseevich Voronoi建立的空间分割算法，它是一种简单有效的能够将二维几何区域用多边形离散化的方法［8］。Voronoi 多边形边界是由任意两点垂直平分线连接而成，可以对二维空间进行划分，能够表示各个节点的邻近关系，Voronoi 图具有势力范围特性、侧向邻近特性、线性特性、局域动态特性、与Delaunay 三角网对偶(dual of Delaunay triangulation)等特性［9］。

CVT:质心Voronoi 结构是Voronoi 结构的一种特殊形式。当Voronoi 结构的质心点与构造Voronoi 结构的初始点重合时，这样的Voronoi 结构称为质心Voronoi 结构［6］。

1.3 覆盖区域模型分析

在一定区域内，根据实际环境需求，需要使各个无线传感器网络节点能够感知目标区域信息，实现全局最优覆盖。这里根据目标覆盖区域边界的变动与否，将覆盖分为两类:1)静态边界区域覆盖;2)动态边界区域覆盖。这里主要分析无线传感器网络动态边界区域覆盖，以初始正方形边界覆盖区域缩放成长方形为例。

如图1 所示，区域边界用外侧实线框线表示，其中最外层为初始覆盖区域边界，最内层实线框线为目标覆盖区域边界，中间的虚线框线为边界迭代缩放过程中的覆盖区域边界。虚线圆代表传感器节点的感知覆盖范围。

图1 正方形边界区域缩放为长方形边界区域Fig 1 A rectangle border region scaled from square boundary region

1.4 无线传感器网络动态边界区域覆盖算法

1.4.1 算法分析

目标区域覆盖控制算法描述如下:

1)设定初始目标覆盖区域参数，如，节点区域初始覆盖边界、目标覆盖区域边界、目标覆盖区域节点个数、各节点距离误差阈值Tol、节点初始位置和方向(区域内随机分布)、最大迭代次数等;

2)根据节点位置生成Voronoi 图，并计算各个对应多边形的质心;

3)计算各个节点距离边界的距离矩阵D，D 中为节点距离各边界的距离;

4)根据各个传感器节点位置P 和迭代区域边界，生成边界虚拟节点R_P，并合并R_P 和P;

5)根据R_P 和P 生成对应的Voronoi 图，并计算对应各个Voronoi 图多边形的质心Pc;

6)用质心位置Pc更新节点位置P，即P=Pc;

7)计算DistMin，DistMin 为各节点距离边界的最小值，同时缩放迭代区域边界，缩放值为(DistMin－1)(防止节点落在目标区域边界上);

8)计算Pc与P 的误差Err，若误差Err 小于Tol 或迭代次数大于最大迭代次数，则输出节点位置;否则，跳到步骤(2)继续执行。

其中，步骤(1)、步骤(5)、步骤(6)运用式(3)～式(5)，步骤(8)运用式(6)计算:

1)Voronoi 图生成与质心计算［7］

对于一个Voronoi 多边形来说，其面积

2)质心位置距离误差计算［10］

其中，Ω 为边界区域，|Ω|为对应边界区域的面积，Vy为对应节点Voronoi 多边形的面积，y，yc分别为对应节点位置及其质心位置。

1.4.2 边界缩放算法

边界缩放算法描述如下:

1)根据任务需求和环境条件，设定目标覆盖区域和相应参数，如，节点区域初始覆盖边界R_I、节点区域目标覆盖边界R_T、节点个数、各节点距离误差、节点位置和方向(区域内随机分布)、最大迭代次数等;

2)取区域R_I 的并集R_U，并计算各个节点距离R_U边界的最小距离DistMin;

3)缩放各个子区域，使各个子区域边界向各自子区域中心缩放(DistMin－1)的距离(防止节点落在区域边界上)，得到缩放后的虚拟子区域并集R_Z;

4)比较R_Z 和R_T，若区域R_Z 为区域R_T 的子集，则将当前缩放区域R_Z 设定为R_C;否则，将目标区域R_T设定为R_C;

5)执行Lloyd 算法，更新各个节点位置;

6)返回到步骤(2)继续执行。

2 仿真实验结果与分析

2.1 仿真实验参数

为了验证控制算法的有效性，本文做了Matlab 实验仿真，假设在初始400 m×400 m 的区域内，随机散布一定数量的感知半径为50 m 的传感器节点，分别就不同类型覆盖区域进行仿真实验分析。基于以上算法，对静态边界的正方形覆盖和正方形—圆形障碍覆盖以及动态边界的正方形—长方形边界覆盖、正方形—十字形边界覆盖、正方形—H 形边界覆盖进行了仿真。假设误差Tol 为10－3m，每种类型覆盖区域对应节点数仿真100 次的统计结果。由于篇幅所限，在此仅以静态边界问题中的正方形覆盖和动态边界的长方形覆盖为例。

2.2 区域覆盖仿真实验结果

2.2.1 静态边界区域覆盖仿真结果

如图2 所示，为正方形静态边界区域覆盖仿真结果图，其中，实心点代表传感器节点，虚线圆代表每个传感器节点的感知区域。仿真实验中，覆盖区域边界不变，通过Lloyd算法，实现了各个节点在对应目标覆盖区域的覆盖。

图2 正方形静态边界区域覆盖Fig 2 Area coverage of square static boundary

2.2.2 动态边界区域覆盖仿真结果

图3 为正方形—长方形动态边界区域覆盖仿真结果，其中实心点代表各个传感器节点的迭代轨迹，对应的有各个Voronoi 多边形迭代变化。仿真实验中，结合Lloyd 算法，由正方形区域缩放至长方形目标覆盖区域，实现了各个节点目标覆盖区域的动态变化。

图3 正方形—长方形动态边界区域覆盖Fig 3 Rectangle-shaped area coverage with square dynamic boundary

2.3 区域覆盖仿真实验分析

覆盖区域形状、节点数、平均覆盖程度的统计结果如图4所示，在覆盖区域一定的情况下，随着节点数的不断增加，目标覆盖区域平均覆盖程度不断增加至100%，即完成目标区域的全覆盖，同时，在覆盖区域改变的过程中，随着传感器节点数量的增加，长方形目标覆盖区域的平均覆盖程度增加速度比H 形目标覆盖区域、十字形目标覆盖区域速度快;在覆盖区域不变的情况下，随着传感器节点数量的增加，正方形—圆形障碍区域覆盖程度增加速度比正方形目标覆盖区域增加速度快。

图4 平均覆盖程度随节点数变化的曲线Fig 4 Curve of average coverage level change with number of nodes

覆盖区域形状、节点数、平均覆盖效率的统计结果如图5所示，在覆盖区域一定的情况下，随着节点数的不断增加，目标覆盖区域平均覆盖效率不断减小，即目标区域内K重覆盖的重数增加，同时，在覆盖区域改变的过程中，随着传感器节点数量的增加，长方形目标覆盖区域的平均覆盖效率的减小速度比H 形目标覆盖区域、十字形目标覆盖区域速度快，十字形目标覆盖区域平均覆盖效率的减小速度比H 形目标覆盖区域快。与平均覆盖程度进行比较，当节点数较少时，尽管平均覆盖效率高，但相应的覆盖程度低，同样，若平均覆盖效率低，覆盖程度高。

图5 平均覆盖效率随节点数变化的曲线Fig 5 Curve of average coverage rate change with number of nodes

3 结 论

本文围绕无线传感器网络覆盖控制进行了研究，基于Voronoi 图和CVT 理论，结合Lloyd 算法，提出了一种无线传感器网络动态覆盖算法，分别实现了多种无线传感器网络目标静态边界区域和动态边界区域的有效覆盖，对控制算法的有效性进行了验证。通过对不同目标覆盖区域形状、节点数量、覆盖程度进行了分析可知，在目标覆盖区域一定的情况下，随着粒子数的增多，区域平均覆盖程度逐渐趋近于100%，覆盖冗余度越高，对应K 重覆盖重数越高;反之，亦然。实际应用中需要根据环境和任务需求，在覆盖程度和覆盖效率之间进行平衡或有所侧重。

［1］ Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces［C］∥Twenty－Second Annual Joint Conference of the IEEE Computer and Communications INFOCOM 2003，IEEE Societies，2003:1293－1303.

［2］ 凡志刚，郭文生，桑 楠.一种基于蜂窝网格的传感器节点部署算法［J］.传感器与微系统，2008，27(4):15－17.

［3］ 沙 超.无线多媒体传感器网络节能关键技术研究［D］.南京:南京邮电大学，2011.

［4］ Sung T，Yang C.Voronoi－based coverage improvement approach for wireless directional sensor networks［J］.Journal of Network and Computer Applications，2014，39(3):202－213.

［5］ Lin J W，Chen Y T.Improving the coverage of randomized scheduling in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2008，7(12):4807－4812.

［6］ Du Q，Faber V，Gunzburger M.Centroidal voronoi tessellations:Applications and algorithms［J］.SIAM Review，1999，41(4):637－676.

［7］ Cortes J，Martinez S，Karatas T，et al.Coverage control for mobile sensing networks［C］∥Proceedings of IEEE International Conference on Robotics and Automation，ICRA’02，IEEE，2002:1327－1332.

［8］ 陈 军.Voronoi 动态空间数据模型［M］.1 版.北京:测绘出版社，2002.

［9］ Okabe A，Boots B，Sugihara K，et al.Spatial tessellations:Concepts and applications of Voronoi diagrams［M］.Now York:John Wiley＆Sons，2009.

［10］Talischi C，Paulino G H，Pereira A，et al.PolyMesher:A generalpurpose mesh generator for polygonal elements written in Matlab［J］.Structural and Multidisciplinary Optimization，2012，45(3):309－328.