有向移动传感器网络三维空间目标自主覆盖算法

谭 励,杨朝玉,杨明华,唐小江

(1.北京工商大学 计算机与信息工程学院,北京 100068; 2.火箭军装备研究院,北京 100094)

0 概述

覆盖问题是无线传感器网络领域研究中的重点之一,主要涉及部署环境、节点感知模型和部署算法等,通常需要对多个要素的综合考虑才能实现传感器网络的全覆盖。与常规二维平面环境下的部署问题相比,针对三维空间环境的部署问题虽然实现的复杂度大幅度增加,但更贴近于现实应用环境,因此,研究工作也更有实际意义。近年来,各类危及社会公共安全的突发性事件频繁发生,急需一种有效手段能够第一时间获取事故现场数据。例如对火灾地震等灾情的快速探测、对轮船飞机等大型载人设备发生事故后的人员搜救,处理此类具有突发性和破环性的事件对应急反应速度有极高的要求。空中传感器网络可以根据任务需要携带不同类型的传感器模块,以自主部署的形式在短时间内完成对特定区域、特定目标的全面覆盖和信息采集,对于提高对突发事件的应急处置能力具有重要意义。

空中有向传感器网络是由配备如摄像机、红外等具有方向特性的传感器模块以及可自主留空飞行的传感器节点构成的网络,针对其覆盖问题主要的影响因素有节点感知方向、感知和通信距离、节点移动带来的能耗以及覆盖目标的特征。本文在此基础上研究当监测对象为部署区域内三维立体目标时的均匀覆盖问题。通过构建空间目标部署基准曲面和提出不均衡虚拟势场方法,得到传感器节点的最优部署路线和部署区域。

1 相关工作

近年来相关的研究工作主要集中在全向覆盖、有向覆盖和三维空间覆盖3个方面。

1.1 全向覆盖

文献[1]提出了三维自部署(3D Self-Deployment,3DSD)算法,通过引入协商策略来确保网络的连通性,同时使用密度控制策略用于平衡节点分布。该算法可在有障碍物的三维空间内实现更快、更均匀的节点自动化部署。文献[2]认为虽然全覆盖对于无线传感器网络中监测和监控应用非常重要,然而由于各种原因覆盖空洞的出现是不可避免的,文中使用空心圆属性评估方法识别出现的覆盖空洞。文献[3]根据节点密度采用分布式覆盖盲区修复算法解决传感器网络中由于节点死亡造成的覆盖问题。全向覆盖研究从各角度考虑了对传感器网络覆盖的性能优化,但由于在算法和仿真中采用的是理想化的全向节点感知模型,因此未能考虑到传感器感知视角的局限性对覆盖结果造成的影响。

1.2 有向覆盖

文献[4]提出有向传感器网络中基于约束人工鱼群的覆盖增强算法,建立二维平面节点模型,引入“感知质心”将其作为人工鱼,通过模拟鱼群高度觅食一致性行为在解空间中寻找最优解。文献[5]结合遗传算法和模拟退火算法,提出一种多媒体有向传感器网络的覆盖增强算法,在提高覆盖率的同时降低了迭代计算次数。文献[6]基于Voronoi图和传感器方向可调的特性,提出一种分布式贪婪算法,进一步提高了有向传感器网络的有效区域覆盖。文献[7]讨论区域内监视摄像机传感器具有的有向感知性,总结有向传感器的感知属性和行为,基于栅栏覆盖的研究成果给出解决方案。文献[8]指出可视化传感器网络(Visual Sensor Network,VSN)中摄像机如何判断其视域最大化覆盖目标是一个NP难问题,并提出分层算法,根据传感器网络规模的大小采用不同的集中式和分布式解决方案,对于有向覆盖部署则采用有向节点感知模型,很好地考虑到传感器节点的有向感知能力。文献[9-11]是二维平面环境下的相关研究,尚未针对三维空间下的覆盖部署作进一步展开。

1.3 三维空间覆盖

文献[12]引入移动传感器网络用以解决随机空中部署的覆盖问题,考虑到山区地形的物理特征,如斜率、高度、半径,设计三维螺旋模型控制节点移动,实现节点在山区地形的全覆盖。文献[13]针对不规则地形建立一个数字估计模型(Digital Elevation Model,DEM),使用地区等高线估计相关区域的预计覆盖率。上述研究考虑了实际环境对传感器网络部署的影响,从地形的角度构建有针对性的节点部署模型,但都以全区域覆盖为目的进行考量,未针对监测区域内特殊目标的覆盖要求展开研究。

在实际应用中,被监测对象通常会是空间中的三维立体目标[14],如一幢失火的楼房或一座发生雪崩的雪山,对于空中有向传感器网络,如何快速高效地实现对三维立体目标的全覆盖,是实现灾情感知、人员救援的前提。根据现有资料表明,类似研究主要集中在全向覆盖、二维有向覆盖和区域覆盖方面,针对有向移动传感器网络对三维空间立体目标表面的覆盖部署问题,现有研究成果在节点模型、算法实现、计算复杂度等方面大多都有不适用性。

2 基于虚拟力的三维空间立体目标覆盖模型

针对覆盖目标为建筑物等立体目标,考虑到算法实时性强、复杂度低的现实需要,本文基于虚拟力方法提出一种三维空间下的立体目标自主覆盖方法,将有向移动传感器网络自主部署过程转化为节点在特定虚拟力场中受虚拟力作用而自主移动、自主转动的过程。

2.1 有向传感器节点感知模型

目前针对三维空间覆盖的研究所采用的节点感知模型为三维全向感知模型,对节点的有向感知属性普遍仍采用平面模型加以辅助说明。该方法不能很好地体现三维空间内有向传感器的部署情况。为此,本文建立面向三维空间环境的有向传感器节点感知模型,参考节点质心原理,以球体为节点框架,对传感器节点以球心为基准进行移动和视角变换。

设有向移动传感器网络节点的感知范围为一个圆锥体,节点位于圆锥体锥顶,感知范围可以在空间平移,也可以以锥顶为中心进行旋转,如图1所示。

图1 有向移动传感器节点感知模型

节点感知模型用一个八元组〈P,θ,C,Rattr,Rrep,CT,RT,S〉表示。其中:P表示三维空间中的有向移动传感器节点P的位置坐标;θ表示节点的有向传感器的感知角度;Rattr表示节点最大通信距离,即节点间产生虚拟引力的最大距离;Rrep表示产生虚拟斥力的最大距离,Rout≤Rrep≤Rattr;Rout为外接球半径,计算公式如式(1)所示;C表示节点P的感知范围的外接球的球心坐标;CT表示被监测的目标的外接球球心;RT表示被监测的大目标的外接球半径;S表示节点P的邻居节点集合,所谓邻居节点是指与节点P之间的距离小于等于最大通信距离Rattr的节点。

(1)

在部署过程中,节点之间根据距离的远近产生虚拟引力或者虚拟斥力或者没有虚拟作用力。由于传统虚拟力方法严格按牛顿定律定义,无法避免局部最小点问题,从而导致覆盖漏洞的出现。事实上,构建虚拟物理系统并不需要严格按物理理论进行直接映射。本文根据有向移动传感器节点特点提出不均衡虚拟势场的概念,每个节点产生独立的不均衡虚拟势场:以节点作为引力中心点,以节点感知模型中外接球球心,作为斥力中心点,即引力中心与斥力中心不重叠。由相互偏离的2个虚拟力中心点分别对其监测对象和邻近节点施加虚拟作用力,从而克服均衡虚拟势场设计容易产生的覆盖重叠和覆盖空洞问题。不均衡虚拟势场示例如图2所示。

图2 节点不均衡虚拟势场分布示意图

设当前节点为Pn,节点Pn所有邻居节点集合S={P1,P2,…},节点Pn对应的外接球球心Cn,每一个邻居节点对应的外接球的球心集合C={C1,C2,…}。当前节点Pn与每一邻居节点Pm∈S之间的距离为:

(2)

当前节点Pn的外接球球心Cn与每一邻居节点Pm∈S的外接球的球心Cm之间的距离为:

(3)

对于节点的运动规律,本文采用近似牛顿运动定律重新定义节点的作用力方程。根据2个节点之间以及节点与监测目标之间的距离,以相距Rout、Rrep和Rattr作为分界线,分别计算当节点远离监测目标时受到的虚拟引力、节点到达部署范围时与其他节点之间的虚拟作用力以及节点进入目标内区域时受到的虚拟斥力。当前节点Pn的所有相邻节点Pm∈S对节点Pn的虚拟力计算公式如下:

(4)

其中,krep、λrep为斥力系数,kattr、λattr为引力系数,α(n,m)为单位向量,分别表示由节点Pn指向邻居节点Pm∈S的引力方向,以及由节点Pn的外接球球心Cn指向邻居节点Pm∈S的外接球球心Cm的斥力方向。

节点Pn所受所有邻居节点虚拟引力和斥力的合力计算公式如下:

(5)

2.2 三维空间立体目标覆盖模型

实际情况中三维空间立体目标的体积和形状存在多种情况,为了降低问题复杂度,本文将该目标的覆盖问题分解为对多个具有一定体积(少量有向传感器网络节点无法完成覆盖)且表面积连续的单一目标的覆盖,如图3所示。

图3 三维空间立体目标覆盖模型

部署完毕后应最大限度覆盖目标的表面积。设目标的所有外凸点集合Sa={S1,S2,…,Sk},目标的质心为CT,计算公式如下:

(6)

其中,k表示目标外凸点的数目。

设外凸点与质心点的最大距离为RT,计算公式如下:

(7)

以质心CT为球心、RT为半径确定目标外接球,作为部署的基准曲面。

设当前节点为Pn,其根据与目标的距离远近产生虚拟引力或者虚拟斥力。设节点Pn对应的外接球球心为Cn,Pn与目标外接球球心CT的距离为:

(8)

针对传感器节点与监测目标之间的虚拟作用力计算,同样采用近似牛顿运动定律,以相距RT为临界点。目标外接球球心CT对节点Pn的虚拟作用力计算公式为:

(9)

其中,α(n,T)为单位向量,表示由节点Pn的外接球球心Cn指向目标外接球球心CT的作用力方向。

为保证节点方向始终指向目标,设节点Pn指向其外接球球心Cn的单位向量为v,设由当前节点Pn指向目标外接球球心CT的单位向量为t,v与t的夹角为α,计算如式(10)所示。

(10)

若β≤π,节点顺时针转动β,否则逆时针旋转2π-β。

3 三维空间立体目标全覆盖算法

3.1 问题假设与需求

基于上述节点感知模型与目标覆盖模型,做如下假设:

假设1传感器网络的监测区域为理想状态空间,排除一切可能影响部署结果的环境因素。

假设2监测区域内出现的所有传感器节点均由同等规格的设备构建,因此,具有相同的感知范围、通信距离等节点属性。

假设3传感器节点均认为设备完好,因此,不考虑因节点软硬件故障引发的部署失败、部署错误等问题。

设定在某一指定三维空间环境内,存在体积远大于传感器个体的监测目标(即仅靠单一节点无法完成对该目标的监测任务)。传感器集群随机抛洒入环境后,要求以最优部署状态完成对大型监测目标的完全覆盖和全面监测,而非区域性覆盖。本文针对上述需求,设计以监测目标为中心的三维传感器节点自主覆盖算法TOSA。

3.2 覆盖算法

算法将有向移动传感器网络协同自主部署过程转化为节点在虚拟力场中受虚拟力作用而自主移动、自主转动的过程。此算法为分布式算法,每个节点并行执行以下步骤完成自主覆盖:

1)初始化。节点获得需要部署到的目标外凸点集合,计算目标的质心点,并由此得到以质心点为球心,以距离集合内外凸点最远距离为半径的目标外接球作为节点部署的基准曲面。

2)目标与节点间虚拟力的计算。为使节点能够在不与目标发生碰撞的情况下尽可能接近目标基准曲面,根据节点与目标之间的距离,目标对节点产生虚拟作用力:目标的外接球的球心产生引力使节点能够向目标汇聚,目标的外接球边界(基准曲面)产生虚拟斥力使靠近目标的节点受到斥力作用不致碰撞目标。

3)节点间虚拟力的计算。为了防止部署过程中发生节点间的碰撞,节点间产生虚拟作用力:节点间产生引力使可能离散的节点相互靠拢,节点间产生斥力使可能发生碰撞的节点相互远离。

4)节点受到来自邻居节点和目标的虚拟力的合力,沿合力方向移动一个单位步长。

5)节点方向与目标外接球球心方向的角度偏差的计算,即计算节点的有向传感器方向与节点指向目标外接球球心方向之间的角度偏差。

6)调整节点的有向传感器的方向,使有向传感器方向指向大目标外接球球心。

7)返回步骤2)继续执行。

4 实验与结果分析

实验采用MATLAB仿真环境,监测区域设为30 m×30 m×40 m的三维空间,覆盖目标为三维空间内长宽高均为10 m的立方体。在监测区域内随机部署300个传感器节点,节点初始参数如表1所示。

表1 传感器节点参数

节点部署过程示意图如图4所示。初始时300个节点以设定的三维空间为边界随机分布于空间内(如图4(a)所示)。在部署过程中,所有节点向目标移动且监测方向指向目标中心点(如图4(b)所示)。最终所有节点在算法的驱动下完成对目标的全覆盖(如图4(c)和图4(d)所示)。

图4 节点部署过程示意图

在相关研究中,比较接近且较新的研究成果,如文献[15-16],其中提到为使传感器网络在尽可能全覆盖的同时延长生命周期,可将三维空间以同等规格的多面体进行划分,使节点部署在每个多面体的中心点来达到最佳覆盖和连接效果。本文比较TOSA算法和空间划分算法的如下指标:

1)覆盖率,评估传感器网络性能的重要指标之一,反映了传感器网络对监测对象的全面监测能力。

2)平均移动距离,指整个部署过程中平均每个节点移动的距离,同等时间内移动距离越小,显示传感器网络的能耗越低。

3)为进一步观察部署算法能耗的使用情况,比较了2种算法在完成相同覆盖率使用的部署时间和已达到部署范围的节点数量,若能在更短的时间内用更少的节点达到指定的覆盖率,则表示该传感器网络在部署过程中更节约能耗。

上述性能指标的对比结果如图5所示。

图5 2种部署算法的性能比较

根据对比结果可知,各项性能指标TOSA算法整体均要优于空间划分算法。空间划分算法中目标的外接球部署区域被划分为多个子分区,每一个子分区的中心点都会影响到节点的移动,可能产生多个节点向同一个子分区集中的现象,造成节点的覆盖冗余和覆盖率的降低。同时,节点在部署初期受到子分区中心点影响而产生的移动也增加了节点移动的距离和能耗。TOSA算法中所有节点的移动只根据目标中心点移动,越靠近目标的部署范围,节点之间越可能由于部署距离过近而进行调整。由于节点部署的移动调整主要集中在目标周边,能够在更快到达部署范围的前提下移动距离更短,因此TOSA算法相比空间划分算法在节约能耗和提高覆盖率方面性能均有较大提高。

5 结束语

针对现实环境中面向大型建筑物等三维空间立体目标的监测需求,本文提出一种有向移动传感器网络三维空间目标自主覆盖算法。采用基于外凸点集合计算三维目标质心的方法构建部署基准曲面,给出不均衡虚拟势场的概念,通过目标与节点、节点与节点之间的虚拟作用力,实现传感器网络的自主部署。下一步将对本文算法进行优化,使其能够适应节点异构等更复杂的部署条件。

[1] MIAO C,DAI G,ZHAO X,et al.3D Self-deployment algorithm in mobile wireless sensor networks[C]//Proceedings of CWSN’14.Berlin,Germany:Springer,2014:27-41.

[2] LI W,ZHANG W.Coverage hole and boundary nodes detection in wireless sensor networks[J].Journal of Network and Computer Applications,2015,48:35-43.

[3] SAHOO P K,LIAO W.HORA:a distributed coverage hole repair algorithm for wireless sensor networks[J].IEEE Transactions on Mobile Computing,2015,14(7):1397-1410.

[4] TAO D,TANG S,LIU L.A coverage enhancement algorithm based on constrained artificial fish-swarm in directional sensor networks[J].Journal of Internet Technology,2014,15(1):43-52.

[5] ZHANG K,DUAN C,JIA H.Genetic simulated annealing-based coverage-enhancing algorithm for multimedia directional sensor networks[J].International Journal of Communication Systems,2015,28(9):1598-1609.

[6] SUNG T,YANG C.Voronoi-based coverage improvement approach for wireless directional sensor networks[J].Journal of Network and Computer Applications,2014,39:202-213.

[7] TAO D,WL T.A survey on barrier coverage problem in directional sensor networks[J].IEEE Sensors Journal,2015,15(2):876-885.

[8] MUNISHWAR V P,ABU-GHAZALEH N B.Coverage algorithms for visual sensor networks[J].ACM Transactions on Sensor Networks,2013,9(4):1-36.

[9] WANG H,ROMAN H E,YUAN L,et al.Connectivity,coverage and power consumption in large-scale wireless sensor networks[J].Computer Networks,2014,75:212-225.

[10] SONG Y,WANG B,SHI Z,et al.Distributed algorithms for energy-efficient even self-deployment in mobile sensor networks[J].IEEE Transactions on Mobile Computing,2014,13(5):1035-1047.

[11] 朱继华,武 俊,陶 洋.基于覆盖率的传感器优化部署算法[J].计算机工程,2010,36(3):94-96.

[12] KIM K.Mountainous terrain coverage in mobile sensor networks[J].IET Communications,2015,9(5):613-620.

[13] LIU L,MA H.On coverage of wireless sensor networks for rolling terrains[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(1):118-125.

[14] NAZARZEHI V,SAVKIN A V,BARANZADEH A.Distributed 3D dynamic search coverage for mobile wireless sensor networks[J].IEEE Communications Letters,2015,19(4):633-636.

[15] ALAM S M N,HAAS Z J.Coverage and connectivity in three-dimensional networks with random node deploy-ment[J].Ad Hoc Networks,2015,34(C):157-169.

[16] 钟永信,黄建国,韩 晶.三维传感器网络部署、覆盖和连接问题研究[J].控制与决策,2011,26(10):1447-1451.