基于CVT模型的无线传感器网络覆盖优化*

项馨仪， 赵杰煜， 刘 超

(宁波大学 信息科学与工程学院，浙江 宁波 315211)

0 引 言

覆盖性能是衡量无线传感器网络(wireless sensor networks，WSNs)[1]的重要技术指标，能够描述网络服务质量和网络感知能力[2～4]。基于计算几何学中的Voronoi图[5～7]来提高网络覆盖效率获得广泛的关注和应用。Lee H J等人[8]提出了基于Voronoi图形质心的部署策略(centroid-based scheme，CBS)，通过使用Voronoi多边形及其重心(几何中心)来修复覆盖问题。但CBS无法确保Voronoi多边形的形心位于Voronoi多边形内盲区的中心位置，其覆盖效率有待提升。Mahboubi H[9,10]利用Voronoi图设计了一种基于Minimax 算法和Voronoi图边界的Maxmin-Edge 的混合部署策略(vertex-edge based strategy，VEDGE)，取二者计算结果中覆盖率较高的位置作为节点移动的目标位置。方伟[11]提出了基于Voronoi盲区多边形质心的覆盖控制部署策略(blind-zone centroid-based scheme，BCBS)，将Voronoi盲区多边形的形心替代作为传感器节点移动的候选目标区域来提高网络覆盖率。刘志强等人[12]结合Lloyd算法基于Voronoi图和质心化的Voronoi图(centroidal voronoi tessellation，CVT)理论，通过调整目标覆盖区域边界或调度传感器节点改变覆盖效率，实现了静态和动态边界区域的有效覆盖。上述方法的实验结果中并未出现100%的覆盖率；仍可进行改进。

本文通过结合CVT模型和圆覆盖思想，设计并实现了一种WSNs的覆盖性能增强算法，通过移动WSNs节点有效地提高网络覆盖能力，可以实现网络100 %覆盖。

1 基于CVT模型的WSNs覆盖优化算法

1.1 模型假设

假设N只传感器节点S随机部署在一个大小为L×W的二维矩形平面T内，在WSNs准覆盖区域T范围内合理布置传感器节点和划分区域，可使网络覆盖率最大化。假设：1)无线传感器节点集S={s1,s2,…,sN}，所有节点具有相同的感知半径Rs和通信半径Rc，每个节点的位置记为si=(xi,yi)。

2)Rc为Rs的2倍，移动传感网络具有连通性。

3)节点可以在二维平面上自由移动，并且具有足够的能量移到指定固定位置停止移动。

4)将准覆盖区域T离散化为a×b个目标节点，每个传感器节点的位置记为tj=(xi,yj)，其中j∈[1,a×b]。

定义1采用圆盘感知模型计算目标节点被传感器节点覆盖的概率。假设目标节点tj和传感器节点si之间的距离为

(1)

传感器节点能够覆盖到目标节点的概率如下：

若d(si,tj)≤Rs，则目标节点被该区域传感器节点覆盖，传感器节点对目标节点的感知概率记为1；否则,目标节点未被覆盖，传感器节点对目标节点的感知概率记为0。

定义2分布均匀性U,指传感器节点覆盖是否均匀，是某节点与其邻居节点之间的距离标准差,值越小代表传感器节点分布的覆盖均匀性越好。

定义3覆盖效率(coverage efficiency,CE)用于衡量WSNs覆盖范围的利用率，为节点已覆盖有效范围的并集与每个节点划分的区域面积总和之比，即

(2)

CE越大，传感器节点覆盖效率越高。

1.2 问题描述

由模型假设可知每个传感器节点都能够获取自身位置和感知范围，节点在移动过程中其感知范围(覆盖圆)和Voronoi区域形成如下关系：1)覆盖圆包含了Voronoi区域，感知范围与Voronoi顶点存在一个或多个交点；2)Voronoi区域可能包含了覆盖圆，此时感知范围与Voronoi多边形可能无交点；3)随机部署的传感器节点的感知范围可能存在重叠情况，不同的覆盖圆相交。

受Voronoi图启发来解决传感器节点覆盖区域存在覆盖空洞和重叠覆盖等问题:1)将传感器节点简化为圆心，其覆盖范围假设为一个圆;2)依据Voronoi图划分准覆盖区域，可以得到传感器节点所处位置对应的多个Voronoi多边形;3)通过一定规则移动传感器节点，其对应的圆随即变化位置和大小，直至覆盖圆完全覆盖准覆盖区域,停止移动传感器节点。

Vi={x∈Ω|d(x,xi)≤d(x,xj),∀j≠i}

(3)

如图1所示，采用Voronoi图和圆覆盖结合的方式构建了20个移动传感器节点模型示例。其中，矩形区域为WSNs准覆盖区域，实心点为移动传感器节点，实线覆盖圆为每个传感器节点的感知圆盘，多边形区域为每个实心点构建的Voronoi区域。将无线传感网络准覆盖区域划分成若干个Voronoi区域，可以较好地呈现覆盖情况。

图1 移动传感器节点覆盖模型示意图

1.3 基于CVT模型的WSNs覆盖优化算法

普通的Voronoi图只能研究固定的静态传感器节点网络覆盖情况，针对移动传感网络引进CVT，定义为每个Voronoi区域的生成点是在该Voronoi区域上的质心，即

(4)

式中V为区域；x为生成点;ρ(x)>0为定义在区域Ω的密度函数。已知传感器节点集合{ci|i=1,2,…,n|，集合中的每一个点表示一个Voronoi区域Ωi⊂Ω。一个非常明显的结论是：准覆盖区域的外接圆的半径的上确界即为覆盖圆。

针对网络覆盖问题的优化方法是迭代更新上一次的候选传感器节点对应的Voronoi区域的外接圆的圆心。问题求解的目标是优化传感器节点{ci}的位置，使覆盖圆盘的半径达到极限。更确切的表述如下问题：给定一个二维区域的最优覆盖，求解已知数目的覆盖圆盘的最小半径，根据数学理论推导，定义覆盖圆盘的半径R如下

(5)

理论上，准覆盖区域Ω可近似为ε-dense的采样集合。外接圆心Ωi等价于针对Ωi的采样点集合求解的Voronoi图的其中一个顶点。通过针对准覆盖区域点集不断迭代求解半径逐渐增大的封闭圆盘，直到所求的圆盘完全覆盖准覆盖区域内所有的点。

1.4 算法描述

1)确定带有边界的准覆盖区域(欧氏空间)T，给定的覆盖圆盘数目n。

2)对准覆盖区域通过离散采样技术得到采样点集合{sj}，以此实现近似Voronoi区域的表达。在生成采样点集{sj}中，设定公差ε控制采样点集的密度。

3)对准覆盖区域进行Voronoi图划分，将划分后得到所有Voronoi图区域的集合记为V，V={v1,v2,…,vN}。针对点集{sj}构建三角剖分，以便于任意两点间的欧氏距离的查找访问。

8)保存求解的圆心半径、覆盖圆盘半径和覆盖结果。

2 实验与结果分析

2.1 实验环境配置

根据准覆盖区域进行离散采样初始化数据，同时初始化覆盖圆盘的数目和初始圆心，以及设定程序终止条件；对准覆盖区域进行Delaunay三角化；进行迭代求解。搭建的实验环境平台是Windows 7系统，英特尔双核处理器、2.4 GHz主频、6 GB内存的计算机，以C++编程实现。

2.2 实验结果分析

实验结果中，以9个节点覆盖方形区域和8个节点覆盖圆形区域为例，准覆盖区域的离散表示、迭代过程和求解结果如图2和图3所示。

图2(a)给出了节点对方形准覆盖区域的网络覆盖情况，以离散技术对准覆盖区域进行充分采样并初始化节点位置，灰色点表示该子区域内的采样点集，黑色点表示节点随机初始位置。图2(b)为节点覆盖过程的中间迭代。本文算法具有较快的收敛性，当节点少于5时，迭代2次基本能够达到90 %以上的覆盖率；给定数目较多的节点，迭代10次可以基本达到理想的覆盖率。每个节点对应的Voronoi区域大小随着迭代次数的增加会趋于均匀。覆盖结果如图2(c)所示，节点覆盖率随着迭代次数的增加大幅提高，最终达到了100 %，可以直观看出节点分布趋于均匀，此时每个Voronoi区域面积基本一致。

图2 方形区域的覆盖过程

图3给出了8个节点对圆形区域的覆盖过程，证明区域形状的多样性未对本算法产生影响。

图3 圆形区域的覆盖过程

根据实验结果，不同数目的圆盘个数实现准覆盖区域的覆盖情况如表1所示，N为圆盘的个数，R为圆盘的半径，D为对准覆盖区域的覆盖率。可以看出：在同样的准覆盖区域，随着节点数目增加，圆盘平均半径不断减小，对准覆盖区域的最终覆盖率均能达到100 %。与文献[7，11]对比，本算法覆盖率优于基于连通性BCBS(connectivity considered BCBS，CC-BCBS)算法和BCBS算法。

表1 不同数目节点的覆盖效率表

3 结束语

通过实验表明:该模型能够调整移动传感器节点至最佳位置，合理划分准覆盖区域，有效提高准覆盖区域网络覆盖率至100 %，减少网络拥塞和覆盖盲区，提供了更高的网络通信服务。本文忽略了外部复杂环境因素对传感器节点规划的影响，下一步要做的工作是将算法进行改进，使其适合更复杂环境下的移动传感网络的覆盖优化。

参考文献:

[1] 仲元昌,陈 锋,李发传,等.大规模无线传感器网络覆盖优化算法[J].传感器与微系统,2014,33(11):117-120.

[2] 凡高娟,郭拯危.无线传感器网络节点部署研究进展[J].传感器与微系统,2012,31(4):1-3.

[3] Li F,Luo J,Xin S,et al.Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing mo-del[J].Computer Networks,2016,108(10):120-132.

[4] 祁育仙,李国勇.混合WSNs中基于多目标优化的覆盖控制算法[J].传感器与微系统,2016,35(2):136-139.

[5] Du Q,Gunzburger M,Ju L.Advances in studies and applications of centroidal voronoi tessellations[J].Numerical Mathematics Theory Methods & Applications,2010,3(2):119-142.

[6] Abo-Zahhad M,Sabor N,Sasaki S,et al.A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J].Information Fusion,2016,30(C):36-51.

[7] 梅希薇,宋鑫宏,方 伟.基于连通性的无线传感器网络覆盖优化算法[J].传感器与微系统,2017,36(5):145-148.

[8] Lee H J,Kim Y H,Han Y H,et al.Centroid-based movement assisted sensor deployment schemes in wireless sensor net-works[C]∥Vehicular Technology Conference,IEEE,2009:1-5.

[9] Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for improved coverage in mobile sensor net-works[J].IEEE Transactions on Industrial Informatics,2011,10(6):1244-1249.

[10] Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J].IEEE Transactions on Industrial Informatics,2014,10(1):163-174.

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

[12] 刘志强,沈廼桐,毛 强,等.无线传感器网络动态覆盖的CVT算法[J].传感器与微系统,2015,34(6):115-118.