赵逢达,默云凤,孔令富,景 荣

(燕山大学 信息科学与工程学院,河北 秦皇岛 066004 河北省计算机虚拟技术与系统集成重点实验室,河北 秦皇岛 066004)

1 引 言

无线传感器网络(Wireless Sensor Network,WSN)是由大量传感器节点以自组织多跳的方式组成的无线网络[1].覆盖率作为WSN 服务质量的重要度量指标,反映了WSN所能提供的“感知”服务,其能够使WSN 的空间资源得到优化分配,更好地完成环境感知、信息获取和有效传输的任务,所以提高覆盖率对WSN 覆盖空洞的修复有着重要意义.

大量中外文献对WSN覆盖空洞的修复问题进行了研究,但是还没有统一的分类标准.在静态WSN中,主要采用调节传感器节点的属性[2,3]和添加传感器节点[4]的方式进行覆盖空洞的修复;在动态WSN中通过节点的移动来完成覆盖空洞的修复.研究方法主要分为网络覆盖空洞修复策略、基于虚拟力以及图论的算法等[5].韩蕊、闰雒恒、Lei Zuo、Jalal Habibi等人[6-9]分别提出基于现有理论的网络覆盖空洞修复方法;文献[10]提出基于虚拟力的覆盖空洞修复方法.文献[11,12]是基于图论的覆盖空洞修复算法,通过最值化图形面积或者两点距离的方式完成覆盖空洞的修复.上面提到的覆盖空洞修复方法假设网络中不同位置被覆盖的重要性是相同的,但是在真实环境中有些位置需要被优先覆盖(如涉及安全问题或重大机密问题).文献[13-15]在覆盖空洞修复方法中考虑到了覆盖优先级.孙泽宇[13]利用贪婪算法和节点调度机制完成具有不同覆盖优先级的监测区域内有效覆盖问题,但未考虑传感器节点异构的情况.景荣等[14]提出通过剔除冗余候选中继节点产生最优部署位置的方法来完成覆盖空洞的修复,但该算法只适用于传感器节点部署均匀的网络.在传感器节点随机部署的情况下,H.Mahboubi等人[15]提出了适用于具有不同覆盖优先级的异构无线传感器网络的最大加权顶点(MWP)方法来获得最大网络覆盖率.但是当覆盖优先级高的点主要集中在某个区域内时,按照该方法将传感器节点移动到具有最大加权值的顶点的位置,此时传感器节点的加权覆盖面积可能不是最大的,可见该方法的适用性受限制.又由于该方法中的局部加权覆盖面积采用中心点权重之和与面积的乘积,在提高算法简洁性的同时降低了所得到覆盖面积的精确度.因此该方法对传感器节点覆盖面积的精确获取以及适用性都有待提高.

为了解决上述问题,本文提出了一种具有覆盖优先级的异构WSN覆盖空洞修复方法,即最佳传感器节点配置的方法(Optimal Sensor Configuration,OSC).为了更好地把握本文结构以及更好地理解此覆盖空洞修复方法(OSC),将覆盖空洞修复方法流程图展示如图1所示.

该方法首先对异构网络进行区域划分,然后根据传感器节点的局部加权覆盖面积计算传感器节点的候选位置,最后根据本文所提策略不断调整传感器节点的位置,使传感器节点移动到最佳部署位置从而完成覆盖空洞修复的任务.与该类问题的其它方法相比,本文贡献主要包括以下几点:

1.将具有覆盖优先级的异构WSN中覆盖空洞修复问题模型化,采用MW-Voronoi图理论对监测区域划分,并利用不定积分的方法准确获取传感器节点局部加权覆盖面积.

2.提出the center multiplicatively weighted voronoi(简称CMWV)算法,它能使传感器节点不断调整自身位置到达最佳部署位置,从而使具有不同覆盖优先级的异构WSN的整体加权覆盖面积最大,完成网络覆盖空洞修复任务.

3.与MWP方法进行对比,验证OSC方法的高效性.

2 覆盖空洞修复数学模型

2.1 前提假设

假设1.网络中传感器节点具有精确的自定位功能.

假设2.传感器节点的感知范围和通信范围都是以节点所在位置为圆心,以定长为半径的圆形区域,且传感器节点的通信半径等于感知半径的两倍,感知范围和通信范围不随时间的变化而变化.

假设3.传感器节点之间的通信内容包括其自身的感知半径和位置信息.

假设4.传感器节点之间实施同步协议,保证所有传感器节点同时开始第一个阶段.同时为了使修复方法更好地发挥作用,规定覆盖周期足够长.

2.2 覆盖空洞修复理论描述

本文采用使传感器节点向合适的方向移动来进行覆盖空洞修复.在真实世界的许多应用中,传感器节点修复覆盖空洞的最佳部署位置事先是不知道的,但传感器节点的可移动性允许对自身位置进行调整,通过合理部署传感器节点完成修复覆盖空洞的任务.

在空洞修复过程中,由于传感器节点感知半径不完全相同且不同位置点被覆盖的优先级不同,所以本文中覆盖空洞修复的本质是增大网络的总加权覆盖面积,使得空洞范围不断减小到消失.由假设可知,网络中每个传感器节点都能获取其自身及相邻传感器节点的感知半径和位置信息.根据这些信息采用MW-Voronoi 图理论方法对网络进行分块研究,划分后每个子区域中有且仅有一个传感器节点.在本文提出的覆盖空洞修复方法下,每个传感器节点向合适的方向不断移动,使得每个传感器节点局部加权覆盖面积不断增大,从而增大网络的总加权覆盖面积.

2.3 覆盖空洞修复模型化

本节首先对覆盖空洞修复过程中用到的相关概念进行解释说明,然后将具有覆盖优先级的异构WSN中覆盖空洞修复问题进行模型化.为了完成覆盖空洞修复的任务,将网络中某个空洞范围视作监测区域,进行覆盖空洞修复研究.

2.3.1 相关定义

乘法加权泰森多边形可用于定性分析、统计分析、邻近分析等,在分析和设计覆盖空洞的修复过程中此图非常有用,介绍如下.

假设二维平面R2中存在n个具有不同加权值的节点,即(S1,ω1),(S2,ω2),…,(Sn,ωn),这些点的集合用S表示,其中对∀i∈n,Si的加权因子ωi>0.

定义1.节点(Si,ωi)到位置点q的加权距离定义如下:

(1)

其中,d(q,Si)是平面内节点Si和位置点q之间的欧氏距离.

将平面划分为n个区域使得每个区域有且只有一个节点,且这个节点是到它所在区域任何位置点的加权距离最近的节点.这种图划分的方法称为the multiplicatively weighted Voronoi(MW-Voronoi)diagram[16].每个区域的特性用数学公式可表示为:

Πi={q∈R2|dω(q,Si)≤dω(q,Sj),∀j∈n{i}}

(2)

定义2.平面内任意给定两个节点A、B以及正实数k,满足AE/BE=k的所有点E的轨迹,就叫做线段AB形成的Apollonion circle 即ΩAB,k[17].

在本节后规定用Πi来表示第i个MW-Voronoi区域,为了构建Πi,首先找出所有节点Sj∈S{Si}的 Apollonion circle,即ΩSiSj,ωi/ωj.这会形成许多Apollonion circle,其中包含第i个节点的最小闭合区域就是Πi区域,如图2所示.

图2 拥有4个邻点s2,s3,s4,s5的s1节点的MW-Voronoi区域[10]

2.3.2 覆盖空洞修复的建模

假设用一个R2的二维平面区域来表示监测区域,集合S表示随机分布在区域中的N个感知半径为ri的传感器节点,传感器节点的感知半径不完全相同.该区域中不同位置被覆盖的重要性用优先级函数φ(q)来表示.例如q点的重要性大于p点,那么q点比p点被覆盖的优先级高,即φ(q)>φ(p).运用MW-Voronoi图理论对监测区域进行划分,所有传感器节点在提出的方法下向合适的方向移动,尽可能多地覆盖优先级高的区域.即通过传感器节点之间有限信息的交换,提高监测区域的总加权覆盖面积.

定义3.优先级函数在Πi区域(即第i个MW-Voronoi区域)上的积分被称为第i个区域的加权值,用α∏i表示,即

(3)

定义4.在区域Πi中传感器节点Si的感知半径为ri,q是该区域中的任意一点.以q为圆心ri为半径的圆与区域Πi的交集被称为q点的覆盖面积,记做覆盖面积w.r.t.q.同理,覆盖面积w.r.t.传感器Si的位置,则被称为该传感器节点Si的局部覆盖面积.

定义5.在区域Πi中传感器节点Si的感知半径为ri,x是该区域中的任意一点.优先级函数在该区域的覆盖面积w.r.t.x上的积分被称为第i个区域的加权覆盖面积,用数学公式表示为

(4)

其中C(x,ri)是以x为圆心,ri为半径的圆.

(5)

同理,在某个MW-Voronoi区域中,令pi为传感器节点Si的位置,那么传感器节点Si的加权覆盖面积w.r.t.pi和加权空洞面积w.r.t.pi分别被称为传感器节点Si的局部加权覆盖面积和传感器节点Si的局部加权空洞面积.优先级函数在区域中所有覆盖区域和非覆盖区域上的积分分别称为总加权覆盖面积和总加权空洞面积.

3 OSC方法

本节提出了一种传感器节点部署算法,该算法能使传感器到达最佳部署位置;随后给出了部署协议,遵循该协议能使网络的整体加权覆盖面积最大,最后给出该部署协议的正确性分析.

3.1 CMWV算法

给出如下公式:

(6)

C∏i为第i个传感器节点在第i个MW-Voronoi区域中修复覆盖空洞的最佳部署位置,该算法为CMWV算法,其中α∏i为定义3中的第i个区域的加权值.

CMWV算法能使传感器节点不断调整自身位置到达最佳部署位置,从而使得具有不同覆盖优先级的异构WSN的局部加权覆盖面积最大.

3.2 部署协议

在部署协议中,CMWV算法会一直迭代直到达到协议终止条件后停止运行,该算法每次迭代都要经过五个阶段.

第一阶段,每个传感器节点都要向其邻居传感器节点广播自己的位置和感知半径信息,同时接收来自它们的位置和感知半径的信息,随后每个传感器节点根据这些信息建立自己的MW-Voronoi区域.

第二阶段,按照本节所提出的CMWV算法,每个传感器节点利用所获得的信息可计算出自己所在区域中的候选位置.

第五阶段,当每个传感器节点的局部加权覆盖面积增加都不超过预设值时,算法停止.

算法运行停止后,可获得最大整体加权覆盖面积.

3.3 部署协议的正确性分析

在无线传感器网络覆盖空洞修复过程中,部署协议的关键就是每个传感器节点仅在一种情况下移动,这种情况就是传感器节点候选位置的局部加权覆盖面积在相应MW-Voronoi区域中增加.由此推论,网络的总加权覆盖面积也会增加,理论及证明如下.

(7)

(8)

(9)

(10)

从公式(7),(10)可知,β′>β.

4 仿真实验

鉴于WSN中覆盖空洞修复问题的复杂性,不同的覆盖空洞修复方法的有效性的评估和对比主要通过仿真软件进行的.因为MATLAB仿真软件的实时性控制和精确度较高,能更好地模拟真实环境,本文拟在64位Windows系统上的MATLAB软件上进行仿真.在实验中,将本文中的OSC方法与文献[15]中的MWP方法进行比较.在MWP方法中,每个传感器节点找到相应子区域的最大加权顶点位置,并且不断向此位置点移动直到此位置点被覆盖为止.实验从加权覆盖率和运行时间两方面对两种方法进行对比.实验时,为了排除偶然性因素的影响使结论更具有普遍意义,需要设置重复组求其平均值,以下实验中涉及的所有数据结果都是50次仿真实验的平均值.

4.1 实验设置

在监测区域A上随机部署n个感知半径为ri的传感器节点,传感器节点的感知半径不一定相同,其中区域A为一个面积为50m*50m的二维平面区域.用给定的优先级函数φ(q)表示监测区域A中不同位置被覆盖的重要性,规定网络中通信半径为20m.在MATLAB仿真实验中,当给定的传感器节点的局部加权覆盖面积增加值都不超过1%时算法停止,否则继续执行算法.

4.2 运行实例

初始设置如下:监测区域中随机部署着27个传感器节点:15个感知半径为1m,6个感知半径为5/6m的,3个感知半径为7/6m的,3个感知半径为1.5m的.给定优先级函数为φ1(q)=exp(-k*[(xq-25)2+(yq-25)2]),k=0.4,其中xq和yq分别是q点的横坐标和纵坐标.图3是该方法的运行实例,图中给出了三个特定时间点的图像,区域中各个位置的覆盖优先级用灰度来表示,且该点的灰度和其自身的覆盖优先级成正比,黑色代表最高优先级.图中黑点表示传感器节点的位置,实心灰色圆形表示传感器节点的感知范围,图中其余曲线代表MW-Voronoi子区域的边界.修复覆盖空洞过程中,覆盖优先级高的位置需要优先被覆盖.从图3(c)看出算法停止后传感器节点聚集在覆盖优先级高的区域,由此可知OSC方法对修复覆盖空洞有作用.

图3 OSC方法的运行实例

4.3 实验结果分析

实验1.本实验的初始设置与运行实例中的完全相同.图4描绘了每个周期算法执行后的加权覆盖率,图中数据显示两种算法都进行一次迭代后,OSC方法的加权覆盖率可达到40%,MWP方法的加权覆盖率在25%左右;随着迭代周期的增加OSC方法所获得加权覆盖率都要比MWP方法高,且运用OSC方法获得的最终加权覆盖率要远远大于运用MWP方法达到的最终加权覆盖率.

图4 每个周期的覆盖率

实验2.运行时间是评估覆盖空洞修复方法优劣性的重要标准之一.鉴于不同算法每个周期中传感器节点的部署时间相差不了多少,因此达到截止条件时算法的运行周期数可作为评估运行时间的标准.给出四个场景,都用实验1中的优先级函数φ1(q).第一个场景中随机部署9个传感器节点:5个感知半径为1m,2个感知半径为5/6m,1个感知半径为7/6m,1个感知半径为1.5m.第二个场景中不同感知半径的传感器节点个数变为场景一中的两倍,即有10个感知半径为1m,4个感知半径为5/6m,2个感知半径为7/6m,2个感知半径为1.5m.类似地,场景三中不同感知半径的传感器节点数目为场景一中的3倍,场景四中不同感知半径的传感器节点数目为场景一中的4倍.图5描述了在达到截止条件时每个算法的运行周期数都随传感器节点数目的增多而减少.这是因为当监测区域存在大量传感器节点时,划分后的部分子区域范围小于传感器节点的感知范围,传感器节点覆盖了大部分子区域,算法达到截止条件的时间更快.图示OSC方法的运行周期数要小于MWP方法,因此OSC方法运行时间更短.

图5 满足不同传感器节点数目达到截止条件时需要的周期数

实验3.实验1优先级函数的至高点仅有一个,但现实中可能会出现多个至高点同时存在的情况.为进一步比较两种算法,实验设置与实验1相同,只是优先级函数改变为

φ2(q)=exp(-k*[(xq-10)2+(yq-40)2])+exp(-k*[(xq-25)2+(yq-7.5)2])+exp(-k*[(xq-37.5)2+(yq-32.5)2])

其中k=0.4,图6描绘了在算法执行完每个周期时,两种算法的加权覆盖率.从图中可以看出,OSC方法所达到的加权覆盖率都要比MWP方法的加权覆盖率要高.说明在优先级函数具有多个至高点时,OSC方法比MWP方法加权覆盖率高,可得OSC方法与优先级函数的至高点个数无关.

实验4.本实验应用优先级函数φ1(q),其他设置与实验1相同,通过讨论优先级函数的平滑程度对网络加权覆盖率的影响来分析所提算法的性能.图7描述了不同k值时的最终加权覆盖率.

图6 每个周期的加权覆盖率

从图7可以看出,在优先级函数比较平滑时,由MWP方法所得到的加权覆盖率要高.随着优先级函数变得尖锐,即不同位置被修复的重要程度不同时OSC方法比MWP方法更占优势.可得OSC方法的性能与覆盖优先级函数的平滑程度有关,且更适合优先级函数非平滑的情况.

图7 场景一中k值不同时的最终加权覆盖面积

通过上述实验设置和实验结果分析可以看出,我们所提出的OSC方法能够在异构和优先级两种实际条件约束下,从覆盖率、效率两个评价指标上优于对比算法MWP,即OSC方法的约束条件更加非理想化,更加接近于实际应用环境,故其在实际环境中的适用性更占优势.

5 结束语

WSN中覆盖空洞修复问题一直是该领域的热点,覆盖率对网络的服务质量有着直接影响,所以提高覆盖率是覆盖空洞修复中的重要内容.针对具有覆盖优先级的异构WSN中覆盖空洞的修复问题,提出了最佳传感器节点配置的方法.该方法采用MW-Voronoi图理论对监测区域的划分,运用CMWV算法使传感器节点不断调整位置到达最佳部署位置,此时无线传感器网络的整体加权覆盖面积最大.实验表明,在不同覆盖优先级及不同网络规模下,OSC方法比MWP方法不仅在加权覆盖率至少提高10%,且减少了空洞修复时间;特殊情况下,在网络不同位置的覆盖优先级(即重要性)几乎相同时,MWP方法效果更好一些,但是在实际应用中不同位置被覆盖的重要性不可能完全相同.因此在修复覆盖空洞的实际应用中OSC方法适用性更强.本文的下一步工作重点是研究具有覆盖优先级的异构WSN中存在障碍物时的覆盖空洞的修复问题.