基于地形修正的无线传感器网络陷阱空洞检测

刘 晔,傅忠谦

(中国科技大学信息科学技术学院,合肥 230027)



基于地形修正的无线传感器网络陷阱空洞检测

刘 晔,傅忠谦*

(中国科技大学信息科学技术学院,合肥 230027)

无线传感器网络中覆盖空洞大小的识别直接影响陷阱空洞的判断。现有陷阱空洞检测算法均基于理想圆盘覆盖模型,在起伏地形条件下不能准确识别空洞实际大小,导致算法失效。本文针对丘陵地形特点,提出一种基于数字高程地图坡度信息的地形修正方法,通过构建传感器节点方向梯度感知模型,实现起伏地形下的陷阱空洞检测。在此基础上,进一步研究了节点间距、坡度和坡向对陷阱空洞检测结果的影响规律,找到一种根据地形确定节点部署间距的近似计算方法。通过仿真实验,验证了本文方法的有效性,并得出了在保证陷阱空洞的发生概率低于5%时的节点间距取值。该结果为在起伏地形下部署传感器网络提供了参考。

无线传感器网络;陷阱空洞;起伏地形;坡度

覆盖性能是衡量无线传感器网络服务质量的关键指标,不断改进和提高覆盖性能成为近年来研究的主要课题[1-3],覆盖空洞的修复是其中的一个重要研究内容。覆盖空洞指区域内未被任何一个传感器监测范围覆盖的点的集合。空洞修复就是通过移动、唤醒现有节点或者增加新节点等方式使空洞区域被传感器监测范围所覆盖。然而,修复空洞达到全覆盖,有时不仅受到实际条件限制无法完成,而且也是不必要的[4],因此允许空洞存在的“陷阱覆盖”方式被提出和研究[5]:监测区域中的任一覆盖空洞的直径不超过某一阈值D,则称传感器网络可以对这个区域提供D-陷阱覆盖。空洞直径是该空洞区域中两点间欧氏距离中的最大值,直径大于D的覆盖空洞为陷阱空洞。

目前针对陷阱空洞的相关算法研究相对较少,文献[6]利用图论技术调整空洞直径达到陷阱覆盖要求,此方法会引起网络拓扑的较大变化。文献[7]在全覆盖网络基础上进行优化形成陷阱覆盖,适用于节点密度和冗余较大的网络。文献[8]采用的空洞检测方法基于最大复形子网,在节点探测半径和通信半径存在特定关系时,可用于检测一定阙值的陷阱空洞。文献[9]中提出基于有效弧检测的陷阱空洞检测方法(THDA算法),通过计算边界弧段查找陷阱空洞,但是起伏地形条件下的弧段描述和计算较复杂,不便于应用。而且,这些研究均是基于圆盘覆盖模型,而起伏的地形条件会影响节点实际探测距离,因此圆周覆盖模型并不能真实反映实际地形条件下的节点覆盖范围。由于陷阱空洞的判断依赖空洞大小的精确计算,一旦节点覆盖范围不规则,算法因不能准确获取空洞大小而失效,所以需要对陷阱空洞检测算法进行地形修正。

地形修正方法在无线传感器网络中已有应用,文献[10]在传感器网络节点部署中考虑大地圆的影响,用球面距离代替直线距离,但大地圆与地形起伏相比还是比较简单。文献[11-12]研究了利用三维定位算法解决在起伏地形下的无线传感器网络问题,用三维计算替代二维计算能有效反映网络的拓扑结构,但是三维空间计算的运算量大,算法相对复杂,尤其是三维空洞大小的计算非常复杂,也不便于解决陷阱覆盖问题。本文引入目前常用的数字高程模型(DEM)坡度、坡向数据,针对丘陵地形特点,通过构建传感器节点方向梯度感知模型,对一种基于边界端点计算的陷阱空洞检测算法进行地形修正,实现起伏地形下的陷阱空洞检测。并在此基础上,进一步研究了地形坡度、坡向和节点间距对陷阱空洞检测结果的影响,通过仿真实验找到根据地形条件确定节点部署间距的近似方法,为实际地形条件下部署传感器网络提供参考。

1 陷阱空洞检测算法的地形修正

传感器网络部署区域的地形起伏变化,对传感器节点实际探测效果产生的影响主要表现在两个方面:地形起伏和地物地貌。地形起伏影响传感器实际探测范围的外形,在不同方向上可能造成实际探测距离的缩小,从而导致各向异性;而地物地貌影响传感器地点的选择,水洼、植被的存在会导致某些位置并不能实际部署传感器节点。

1.1 陷阱空洞算法描述

为了研究地形起伏对传感器网络陷阱空洞检测算法的影响,选取一种适合起伏地形条件下应用的陷阱空洞算法。由于依赖弧段检测的方法在实际地形条件下应用困难,因此,采用一种基于空洞边界端点计算的陷阱空洞检测算法,描述如下:①以传感器节点为顶点对监测区域进行delaunay三角形[13-14]划分,如图1(a)所示;②计算相邻节点覆盖范围边界的交点坐标,根据该交点是否被其他节点检测到,判断这对相邻节点的连线是否为空洞边界,如图1(a),点P不被Si、Sj之外的节点所覆盖,则SiSj为空洞边界,P为空洞的一个边界端点;③根据②的结果对三角形网进行聚类,去掉不是空洞边界的三角形边,形成多边形网。如图1(b),根据区域内是否存在一个边界端点P,判断其是连通区域(Ⅰ区域)还是空洞(Ⅱ区域),从而找到空洞的边界节点链。④对找出的空洞,根据②得到的边界端点坐标,计算两两之间的最大距离,按照陷阱空洞的定义判断其是否陷阱空洞。

图1 陷阱空洞检测算法示意图

1.2 方向梯度感知模型

如无特殊申明,本文均基于以下假设:①传感器节点的探测能力各向同性,理想探测半径为r;②为了接近实际应用,本文中坐标如未特别说明,均指大地坐标;③不考虑地形曲面的影响造成的衍射变化。

在地学研究中,用坡度描述地表单元陡缓的程度。通常把坡面的垂直高度h和水平距离l的比叫做坡度(或坡比),用字母i表示,坡向是斜坡面对的方向,亦即高程下降最快的方向[15]。

如图2所示,该地形的坡度i为:

i=h/l=tanθ

(1)

其中,θ为坡面与水平面的夹角。

图2 坡度概念与方向梯度感知模型示意图

为了区别,本文把沿坡面上任一方向上高程变化的程度称为沿该方向上的方向梯度,用g表示。由数学中方向导数的计算方法可知,坡面上点P(x0,y0)处沿ωp方向的方向梯度g为:

(2)

其中,ωp为方向角,h(x,y)为坐标(x,y)处的高程,通过GIS软件可以方便地从DEM地图数据中提取高程数据和坡度信息。显然,当ωp方向与该点的坡向方向一致时,方向梯度等于坡度,即在坡向上的方向梯度等于坡度。

下面基于坡度和方向梯度这两个概念,求解起伏地形下的传感器节点沿任意方向的实际感知距离。为了方便计算,以坡向为起始方向,并按顺时针方向度量,将任一方向与坡向的夹角ω作为该方向的方向角。

我国南方多为丘陵地形,这种地形起伏变化平缓,适宜部署无线传感器监控网络。丘陵地形的特点是二阶坡面因子坡度变率和坡向变率较小,对于每个节点,在其探测范围内,可近似看成理想坡面,即范围内各点的坡度和坡向一致。如图2所示,在这样的近似下,沿ω方向上的方向梯度[15]g为:

g=tanβ

(3)

其中,β称为沿ω方向的方向梯度角。由式(1)、式(3),可知:

g=icosω

(4)

节点沿ω方向的实际探测半径r′受到地形影响,与理想探测半径r存在关系:

r′=rcosβ

(5)

将式(3)、式(4)代入式(5),得:

r′=rcos(arctan(g))=rcos(arctan(icosω))

(6)

特别的,当ω=0时,β=θ,则r′=rcosθ。

令A=cos(arctan(icosω)),式(6)表示为:

r′=rA

(7)

这表明平面距离和坡面距离的转换关系,A为转换因子,且0

同时,受地物地貌因素影响,某些位置即使理论计算结果很好,也不能在此部署节点。因此,增加二值部署可行性因子p,在不适合部署节点的位置值为0,否则为1。

因此,得到传感器节点在ω方向上的实际探测半径r′的计算公式如下:

r′=prcos[arctan(icosω)]

(8)

1.3 陷阱空洞检测算法实现

传感器节点圆周覆盖模型修改为方向梯度模型,陷阱空洞检测算法进行相应修正,主要有以下两个方面:

①相邻节点覆盖边界的交点

由1.2的丘陵地形特点分析,可近似认为相邻节点的覆盖范围平面在同一个切空间内[16],即节点相邻节点的覆盖圆近似在同一个切平面上,因此,无论整体地形变化多大,在考虑相邻节点间的相关计算时,均可近似按照平面处理。对于节点Si、Sj,其公共切平面的坡度取Si、Sj两点的坡度平均值,坡向取Si、Sj两点的坡向夹角的角平分线方向。如图3所示,Si、Sj两点大地坐标为(xi,yi)、(xj,yj),Si、Sj公共的切平面坡度为i,则:

(9)

图3 山坡地形交点和距离计算示意图

(10)

其中,A为转换因子,由(7)定义。

在加入地形因素前,Si、Sj两节点覆盖范围交点P的计算式为:

(11)

将式(11)代入式(10),得到交点P的坡面坐标(x′,y′),将其映射回大地坐标系得到P的大地坐标(x,y):

(12)

②点是否被传感器节点感测范围所覆盖的判断

理想圆盘覆盖模型中,根据点到传感器节点位置的距离是否小于r来判断该点是否被这个传感器节点所覆盖,而受地形坡度影响,用实际探测半径r′替换r。如图3所示,为判断Sj是否被Si探测范围所覆盖,先求SiSj的水平投影方向上的方向角ω:

(13)

代入式(6)求出Si在SiSj的水平投影方向上的实际探测半径r′,以此判断Sj是否在Si的探测范围内。

2 地形修正的影响及仿真分析

引入方向梯度感知模型对陷阱空洞检测算法进行地形修正后,节点实际探测距离缩小且各向异性。为研究对检测结果的影响,进行实验仿真。本文仿真均是基于MATLAB 2012仿真平台,在处理器为Intel Core i3-2330M 2.2 GHz、内存2 GB的计算机环境下运行。

2.1 地形修正前后检测结果比较

在50 m×50 m的区域内,部署传感器节点数目N=40,节点的理想探测半径r=6 m,陷阱空洞阙值dmax=2r=12 m,进行陷阱空洞检测算法仿真。

①从网上下载的SRTM DATA VERSION 4.1地图数据我国东南部(纬度25 N～30 N,经度115°～120°E)地图中随机选取大小为50 m×50 m的方格为例,如图4所示,其中,图4(a)为三维地形图,图4(b)为等高线地形图。

图4 仿真区域地形示意图

图5 地形修正的陷阱空洞检测示意图

②随机产生传感器节点部署图,如图5(a)所示。图中圆形表示传感器节点的覆盖范围。

分别在是否加入地形修正的情况下进行仿真,结果如图5(b)、(c)、(d)所示。其中,图5(b)、(c)分别为加入地形修正前、后陷阱空洞检测情况,图中粗线表示检测过程中的封闭多边形边界;图5(d)为检测结果比较图,图中实线表示加入地形修正前检测出的陷阱空洞外形,虚线表示加入地形修正后检测出的陷阱空洞外形的增加部分。通过比较可以看出:

①原有陷阱空洞直径增加。修正前后虽然均能检测出陷阱空洞Ⅰ、Ⅱ,但直径大小并不相同。修正后检测到的空洞范围增加了一部分,直径变大,如图3(d)中A、B所示。

②产生新的陷阱空洞。陷阱空洞Ⅲ在修正前的空洞检测过程中由于直径较小并不是陷阱空洞,修正后直径超过陷阱空洞阙值,成为新的陷阱空洞。

2.2 坡度、坡向及节点间距的影响

地形修正改变了节点间的相邻关系。通常将覆盖范围相交的传感器节点,即节点间的距离d与节点探测半径满足:

d≤2r

(14)

称为相邻节点。加入地形修正后,由式(6)知相邻节点需要满足的条件转变为:

d≤2r′=2rA=2rcos[arctan(icosω)]=f(i,ω)

(15)

式中,若i一定,f(i,w)在ω=kπ时取得最小值。因此,在坡度为i的坡面上等间距部署的无线传感器网络节点,节点间距d应满足的必要条件为:

d≤2rcos(arctani)

(16)

实际应用中对于人员不便进入的野外环境随机部署传感器节点通常采取空投方式进行,而空投布撒的节点实际落点往往具有随机性,一般认为服从以理想落点为中心的二维正态分布。这种随机性增加了出现覆盖空洞的可能性。为了抵消这个影响,加入修正因子k(0

d≤2krcos(arctani)

(17)

如果当k取某值时,使得按均匀间距d空投布撒,单位面积区域内出现陷阱空洞的概率pt小于某个百分比p,则认为符合要求。下面通过仿真实验进行研究,找出合适的k值。

假设传感器节点探测半径r=6 m,按照间距d0=10 m均匀部署40个节点,陷阱空洞的阙值仍为dmax=2r=12 m,考虑落点的随机性,其分布规律按照标准正态分布计算,对陷阱空洞检测算法进行仿真,结果如下:

①在无起伏的理想平面上,进行100次仿真实验,出现陷阱空洞的次数为2次。

②在坡向一致、坡度均为i的山坡地形下,是否会出现陷阱空洞,与坡度i的大小以及空投方向与坡向的夹角有关。地学研究中,通常以坡度25°即46.6%为界,将丘陵按坡度陡峻程度分为陡丘陵和缓丘陵,故在不同区间内取3种具有代表性的坡度值,进行100次实验,结果如表1。

表1 空投间距为10 m时出现陷阱空洞次数

结果表明,加入地形修正后,陷阱空洞出现概率大幅度提高,验证了地形因素对陷阱空洞检测的显著影响。并且在相同空投间距下,坡度越大,空投方向与坡向方向越不一致,出现陷阱空洞的可能性也越大。

③以坡度46.6为例,间隔0.05取不同k值,按式(16)计算相应d值,在不同空投方向下重复100次实验,结果如表2。

表2 坡度46.6时不同空投间距下出现陷阱空洞的次数

可见,若取p=5%,当k=0.8时,出现陷阱空洞的概率pt低于p,明显改善了网络覆盖性能,满足要求。且k值越小,pt越小。

为验证之,将k=0.8代入其他坡度情况,即

d≤1.6rcos(arctani)

(18)

在不同的坡度和空投方向下,各重复100次仿真实验,结果如表3。

表3 按k=0.8调整间距出现陷阱空洞的次数

如表3所示,当k=0.8时,在不同的坡度条件和空投方向下,出现陷阱空洞的概率pt均低于p,满足要求。因此,k=0.8是通过实验仿真得到的较为理想的取值。

3 结论

本文结合丘陵地形实际特点,建立了节点方向梯度感知模型,实现了起伏地形下的陷阱空洞检测。仿真实验验证了方法的有效性,同时也反映了地形因素对陷阱空洞检测的影响非常明显,证明了地形修正的必要性。实验得出了按照式(18)调整节点间距能有效降低出现陷阱空洞的可能,当k=0.8时,可将出现陷阱空洞的概率控制在5%以内。该结果适用于坡度变化平缓的起伏地形,为在这种地形条件下随机部署传感器网络提供了有益的参考。下步可考虑坡度变化较大、更加复杂的地形条件下的模型修改,对于节点探测范围内不能近似作为理想坡面处理的地形,用曲面代替平面进行两点距离计算,提高检测算法的准确性,增强其对复杂地形的适用能力。

[1] Jia J,Chen J,Chang G,et al.Energy Efficient Coverage Control in Wireless Sensor Networks Based on Multi-Objective Genetic Algorithm[J].Computers and Mathematics with Applications,2009,57(11):1756-1766.

[2]Younis M,Akkaya K.Strategies and Techniques for Node Placement in Wireless Sensor Networks:A Survey[J].Ad Hoc Networks,2008,6(4):621-655.

[3]Yao J,Zhang G,Kanno J,et al.Decentralized Detection and Patching of Coverage Holes in Wireless Sensor Networks[C]//SPIE Defense,Security,and Sensing.International Society for Optics and Photonics,2009:73520V-73520V-10.

[4]Liu Y,Liang W.Approximate Coverage in Wireless Sensor Networks[C]//Local Computer Networks,2005.30th Anniversary.The IEEE Conference on IEEE,2005:68-75.

[5]Balister P,Zheng Z,Kumar S,et al.Trap Coverage:Allowing Coverage Holes of Bounded Diameter in Wireless Sensor Networks[C]//Infocom 2009,IEEE.IEEE,2009:136-144.

[6]Dogruel M,Ozgunzer U.Distributed Coverage in Wirelessad Hoc and Sensor Networks by Topological Graphapproaches[C]//Proc of IEEE Int Conf on ICDCS.Genova:IEEE Press,2010:106-115.

[7]Li J,Chen J,He S,et al.On Energy-Efficient Trap Coverage in Wireless Sensor Networks[C]//Real-Time Systems Symposium(RTSS),2011 IEEE 32nd.IEEE,2011:139-148.

[8]胥楚贵,邓晓衡,邹豪杰.无线传感器网络覆盖空洞修复策略[J].传感技术学报,2010,23(2):256-259.

[9]王力立,吴晓蓓.传感器网络中陷阱空洞的分布式检测及修复[J].控制与决策,2012,27(12):1810-1815.

[10]Pescaru D,Curiac D I.Anchor Node Localization for Wireless Sensor Networks Using Video and Compass Information Fusion[J].Sensors,2014,14(3):4211-4224.

[11]夏明,毛科技,何文秀,等.基于空间角度传递的多跳AOA三维定位算法研究与在地形建模上的应用[J].传感技术学报,2012,25(5):651-658.

[12]胡中栋,曾珽,肖红.基于地形改正的无线传感器网络DV-Hop定位算法[J].传感器与微系统,2013,32(6):147-149.

[13]武晓波,王世新,肖春生.Delaunay三角网的生成算法研究[J].测绘学报,1999,28(1):28-35.

[14]Tsai V J D.Delaunay Triangulations in TIN Creation:An Overview and a Linear-Time Algorithm[J].International Journal of Geographical Information Science,1993,7(6):501-524.

[15]刘学军,任志峰,王彦芳,等.基于DEM的任意方向坡度计算方法[J].地域研究与开发,2009,28(4):139-141.

[16]曹文明,王瑞.传感器网络覆盖定位模糊信息处理方法[M].北京:电子工业出版社2010:113-115

刘晔(1982-),男,安徽安庆人,中国科技大学信息科学技术学院硕士研究生,研究方向为无线传感器网络,liuye114@mail.ustc.edu.cn;

傅忠谦(1959-),男,江苏南京人,中国科技大学信息科学技术学院副教授,从事复杂系统和复杂网络理论、系统仿真研究。

DetectionofTrapCoverageHolesinWSNsBasedonTopographicCorrection

LIUYe,FUZhongqian*

(School of Information,University of Science and Technology of China,Hefei 230027,China)

How to get the size of the holes in wireless sensor networks directly affects trap hole detection.Previous hole detection algorithms always base on the disk coverage model,and it can not get the actual size of the holes in rugged terrain.For the case of hilly terrain,this paper put forward a topographic correction algorithm based on the slope information in digital elevation maps to detect trap holes in rugged terrain by constructing directional sensing model for the sensor nodes.Based on this method,this paper further studies on the influence on trap holes detection of slope,aspect and node spacing,and finds a approximate method to determine the node spacing according to the terrain.The simulation result demonstrates the algorithm and help to find out the value of the node spacing to make the rate of trap holes below 5%.This result can provide reference for the deployment of sensor networks in rugged terrain.

wireless sensor networks;trap holes;rugged terrain;slope

2014-03-20修改日期:2014-05-13

10.3969/j.issn.1004-1699.2014.06.015

TP393

:A

:1004-1699(2014)06-0785-06