空中无线传感网复杂路径自主部署技术研究①

焦瑶瑶 谭 励 苏维均 杨明华 胡计鹏



空中无线传感网复杂路径自主部署技术研究①

焦瑶瑶②谭 励 苏维均 杨明华 胡计鹏

(北京工商大学 计算机与信息工程学院 北京 100048)

为了能够完成对真实环境中复杂目标路径的监测，提出了一种基于虚拟力的三维空中无线传感器网络复杂路径自主部署算法，该算法创新性地采用由复杂路径产生的“引力曲线”构建虚拟力场，使无线传感器网络中的节点能够自适应地完成对复杂目标路径的覆盖。仿真实验表明，与传统的虚拟力算法相比，该算法的部署过程更为迅速，路径覆盖率、均匀度均有较大提升。

空中无线传感器网络(AWSN)， 三维部署， 复杂路径， 虚拟力

0 引 言

无线传感器网络(wireless sensor network, WSN)技术伴随着通信技术、嵌入式计算等技术的成熟而得到迅猛快速发展。无线传感器网络借助具有无线通信能力的传感器节点，将其感知和采集的环境信息通过自组织方式所形成的多跳网络进行传输，使人们可以不受时间、地点和环境的限制，通过传感器节点便可获得大量真实可靠的物理世界信息，非常适用于条件恶劣或人类无法亲身到达的环境。目前，无线传感器网络已广泛应用于工业、军事、农业、医疗、环境监测等领域，应用前景十分广阔[1-3]。

微小型飞行器与具有感知和通信能力的无线传感器网络结合构成了空中无线传感器网络(aerial WSN，AWSN)。与传统的传感器网络节点部署不同，空中无线传感网的节点不再是静态的，其节点由微小型飞行器组成，不仅具有感知能力，而且还兼有自主飞行能力，因而能够根据实际环境，更加及时准确地获取目标区域数据信息[4-6]。近几年，发生在人口密集地区的地质灾难给人类生命、财产造成了重大损失，非常重要的原因之一是发生灾害期间道路、桥梁被毁，各类通信手段遭到毁灭性破坏，导致灾区内外沟通不畅，外界一时无法了解灾区情况，灾区几乎霎时成了“信息孤岛”,各种救援一时难以展开，由此而错过了“黄金救援时间”。AWSN可以实现快速部署和近距离侦察，能够及时准确地为实现有效的救援获取灾区的第一手现场数据，从而提高救援的成功率。因为好的AWSN部署算法可以节省大量部署时间、节约节点能量、获得更准确的现场数据，所以部署算法的研究一直是研究的热点。面对灾难救援中复杂搜索路径进行三维空间节点部署则更具挑战性。本研究提出了一种基于“引力曲线”的空中复杂路径自主部署算法，该算法能够根据应急救援中路径搜索的实际需要，实现对三维空间复杂路径的自主部署。

1 相关工作

针对动态节点部署问题，最早的研究始于对机器人的路径规划。近年来，研究学者已提出了多种方法和策略，Wang等[7]提出了多种应用计算几何方法实现移动节点自主部署的算法，Du等提出了一种基于网格密度的部署算法[8]。

1986年Khatib提出了人工势场(artificial potential field，APF)法，该方法在机器人控制及路径规划领域被广泛使用[9]，由于该方法可使传感器节点根据实际环境生成路径，系统的适应性得到显著提高，避障性能大大增强。Howard等[10]在2002年率先提出应用人工势场方法实现移动节点的自部署，这种部署可使每个移动节点都受到其他节点的作用力及环境中的障碍物的斥力，类似静电场中带电粒子运动时的受力，在各个力的共同作用下，节点得以在部署环境中扩散展开。

在人工势场理论基础上发展起来的虚拟力(virtual force，VF)算法[11]能够自动使初始阶段聚集的移动节点快速分散，自适应地动态调整节点疏密情况，该方法已经成为当前用于移动节点部署优化的典型策略。Zou 等在文献[12]中提出了虚拟力算法的概念，整个部署过程模拟了物理学中的分子间作用力——范德华力。陶丹等[13]应用虚拟力算法，提出了一种基于虚拟势场的有向节点网络覆盖增强算法。该算法通过引入质心的概念，使传感器节点在虚拟力作用下做扩散运动，消除了网络中的感知重叠区和盲区，进而增强了整个有向节点的网络覆盖。相对地，Zhao等[14]进一步完善了虚拟力算法，引入了负质心的概念。周浦城等[15]提出了一种基于虚拟力的无线传感器网络覆盖增强算法。该算法是在人工势场思想的基础上进行改进，将运动图式理论与人工势场理论相结合，通过节点间作用力和部署边界斥力共同作用，调整整个网络的形态。

空中无线传感网(AWSN)一直受到带载平台稳定性、能量、负载额度等条件的限制，但伴随着相关技术的发展，空中无线传感网已在环境监测方面取得了巨大进步。例如，奥地利亚德里亚综合大学的 Wischounig-Strucl 等[16]利用空间传感器网络构建了区域视频监控系统；Watai等[17]应用空中无线传感网系统监测大气中的二氧化碳浓度，以便对突发的异常情况做出紧急响应。

如上所述，以上算法在实现移动节点自主部署方面都有积极的贡献，但每一种方法都存在其优缺点和适用条件。同时，大部分方法都是针对以区域空间为探测目标所提出的，对于节点覆盖目标是一条路径的情况，上述算法很难进行精确的部署。为此，本文结合灾难救援的需要，在现有虚拟力算法的基础上提出了一种适于空中无线传感器网络的能够对三维空间复杂路径进行精确覆盖的自主部署算法，简称三维空间复杂路径自主部署算法。

2 复杂路径自主部署算法模型

2.1 假设与定义

首先做出如下假设和定义：

假设1：通过算法可以计算出每个节点自身的位置，并得到确定的坐标信息。

假设2：节点的通信半径为Rc，当两个节点间的直线距离dij小于或等于节点本身的通信半径Rc时，这两个节点互为彼此的邻居节点，互相之间可以通信。

假设3：通信半径Rc内能量连续，通信半径外通讯能量为0。

定义1：节点模型为[O(x, y, z), Rm，Rk，Rc，Fmax]。其中O(x, y, z)为节点部署在空间中的三维坐标值，x、y、z分别为直角坐标系中X轴、Y轴、Z轴的坐标值；Rm为节点间产生相互碰撞的最小半径，简称为最小半径；Rk为平衡半径，当两个节点间的直线距离等于平衡半径时，节点受到对方的作用力为0；Rc为通信半径；Fmax为节点间距离小于最小半径Rm时所受到的最大的斥力。

定义2：节点覆盖目标路径曲线模型为[f(x, y, z)LimD P(x, y, z)]，式中，f(x, y, z)为曲线的一般方程，Lim表示曲线在空间区域的x、y、z轴坐标的极大和极小值的集合{xmaxxminymaxyminzmaxzmin}，用以限定所有节点的最大部署范围。d为任一节点到达目标曲线内所有数据元素的距离集合，设其中最短的距离为D，在目标路径上得到最短距离所对应点的坐标则为P。

2.2 作用力模型

空中无线传感器网络中的节点受到三种类型的作用力，下面进行简要分析。

首先，基于群体智能思想，将可移动的空中无线传感器节点看作是带电的微粒，物理学中的带电微粒之间存在引力和斥力。将无线传感器网络中的节点假设为电场中的微粒，那么节点之间就存在电场力的作用，其受力类型取决于两个节点之间的距离。节点间的受力表现为引力时，说明两个节点间的距离过远；相反，如果两个无线传感器节点间的受力表现为斥力时，说明节点间的距离过近。

其次，在实际应用环境中必定存在障碍物，节点会受到障碍物对它的作用力，为了避免节点与障碍物发生碰撞而引起设备损坏或网络瘫痪，设定监测目标区域中的障碍物对节点产生斥力。

最后，目标路径会对节点产生作用力。为了能够使节点准确地覆盖在目标路径上，本文提出了“引力曲线”的概念，将目标路径转变成一条具有引力作用的曲线。这样既保证了节点不会因过分偏离目标路径而无法实现覆盖作用，同时也能够提高覆盖率的准确度，更好地完成信息监测任务。

一般采用矢量表示节点所受到的作用力，节点所受到的合力就是各个作用力的矢量叠加。空中无线传感器网络中的节点在合力的作用下实时对自己的位置进行移动和调整，当节点受力等于零或者达到移动距离上限时，节点则停止移动。节点在三种类型的受力作用下，实现自主部署，完成对目标路径的有效覆盖。

2.2.1 节点间作用力

将空中无线传感器网络中节点的集合假设为一个包含力F和质量m等参数的虚拟物理系统，各个节点之间均可以产生引力或斥力，每个节点i受到来自邻居节点j的作用力。节点i移动的方向和距离取决于该无线传感器节点的自身位置、自身的质量mi及其所受邻居节点的引力与斥力的合力Fi等参数。节点间距离在通信半径Rc范围之内的节点间存在相互作用力，包括斥力和引力。斥力和引力的大小则取决于节点间的距离，距离决定力的性质。存在一距离Rk，当节点间距离大于Rk时它们之间的作用力表现为引力，使得节点相互靠近；当节点间距离小于Rk时它们之间的作用力表现为斥力，使得节点相互远离；当节点间距离恰好等于Rk时，节点间作用力等于0。这样的设定能够使节点之间的距离收敛于距离Rk。而距离Rk在此算法中设定为节点的平衡半径。

如图1所示，空间三维图中有节点A到节点F共6个节点。其中，A节点最小半径为Rm，平衡半径为Rk，通信半径为Rc。

图1 节点间距离关系与受力图

任意两个节点间距离与受力分析如下：

(1) 图1中的节点A和B间的距离满足dAB=Rm(最小半径)时，两节点即将发生碰撞，此时节点间的作用力表现为斥力且达到最大为Fmax。

(2) 图1中的节点A和C间的距离满足Rm

(3) 图1中的节点A和D间的距离满足dAD=Rk时，节点间的引力和斥力相等，合力为0。

(4) 图1中的节点A和E间的距离满足Rk

(5) 图1中的节点A和F间的距离满足dAF>Rc时，两节点间的作用力为0，认为不存在引力和斥力。

节点间所受引力Fα和斥力Fτ的公式如下：

(1)

(2)

其中，Rm为最小半径；Rk为平衡半径；Rc为通信半径，通常设Rm≤Rk≤ Rc；α=10， β=12( α, β为增益系数，为获得最大增益，根据经验，取α=10, β=12)。

2.2.2 障碍物作用力

如前文所述，空中无线传感器网络中的节点不仅受到节点间作用力的影响，在实际应用环境中还会受到监测目标区域内障碍物对节点的作用力。由于在节点部署的路径之中不可避免地会有一些不可预知的障碍物影响节点的运动，倘若节点与障碍物发生相撞则会引起不必要的损失，因此将障碍物的作用力定义为斥力。设定障碍物会对所有节点产生斥力，斥力的大小也由节点与障碍物之间的距离决定[10]。示意图如图2所示。

图2 节点障碍物斥力示意图

障碍物O拥有其本身的斥力场范围，当节点A运动至该范围之内时，会受到由障碍物O指向节点A的斥力，斥力的大小由下式计算得出：

(3)

其中，dAO为节点与障碍物之间的距离，L为障碍物斥力场范围半径，即节点受到障碍物斥力作用的有效距离；通常，α定义为大于10的整数；β=12，使节点在部署中和障碍物之间能够保持相对安全的距离。

2.2.3 目标路径的作用力

为了实现节点对目标路径的有效覆盖率，提出“引力曲线”的概念，即目标路径会对每一个节点产生引力，在此引力的作用下使得节点自主向目标路径移动，实现对目标路径的覆盖。

对任意一节点A，总能够找到一条到达目标路径的最短路径，其最短距离定义为D。最短路径所对应的目标路径上的点，定义为节点在曲线上的投影点P。为此，对目标路径曲线进行有限点分割，搜索距离节点A最近的分割点设定为投影点P，投影点P与节点A间存在引力作用，且引力由投影点P指向节点A。投影点对节点产生引力作用，使得节点在移动过程中能够始终沿“最短路径”不断接近目标路径，最终完成对目标路径的覆盖，示意图如图3所示。

图3 目标路径对节点的作用力计算示意图

节点受到引力曲线的引力的大小由下式计算得出：

(4)

其中，dAP为节点与垂足点之间的距离，D为节点到达目标的“最短路径”；通常，α定义为大于10的整数；β=12，使节点能够最终到达目标路径。

3 三维空间复杂路径自主部署算法

基于上述建立的算法模型，建立三维空间复杂路径自主部署算法。该算法是一个分布式算法，网络中的每个节点都并发执行相同的算法，且节点的移动是同步并发进行的。该算法描述如下：

初始化节点i部署区域范围{xmaxxminymaxyminzmaxzmin}；

初始化移动距离步长△d，时间步长△t；

获得目标路径的曲线方程φ(x, y, z)；

While(1)

{

搜索节点i的所有邻居节点；

按式(1)，式(2)计算节点i所受邻居节点的引力的合力Fai，所有斥力合力Fri；

搜索节点i附近的所有障碍物；

按式(3)计算节点i所受所有障碍物的斥力的合力Foi；

计算节点i的投影点Pi；

按式(4)计算节点i受到的投影点引力Fpi；

计算节点i所受所有作用力的合力

Fi=Fai+ Fri +Foi +Fpi；

if (Fi==0)

StopandWait(△t);//本轮不移动

else

按合力方向移动一个步长距离△d；

}

其中，节点i所受邻居节点作用力计算过程如图4所示。

图4 节点受邻居节点作用力计算过程

4 实验仿真与结果分析

为了检验本算法的有效性，本节采取两组实验来进行验证，并对实验结果进行分析。第一组实验目标路径为一条较为简单的正弦曲线，第二组实验的目标路径为一条较为复杂空间螺旋曲线。每组实验中，首先利用未加入“引力曲线”的基础虚拟力算法对目标路径进行部署，然后利用加入“引力曲线”的部署算法对目标路径进行节点覆盖，最后对比分析算法的有效性。

本文采用具有代表性的部署性能度量指标：路径覆盖率和路径均匀度。

路径覆盖率的定义是：所有节点覆盖路径的总面积与目标路径面积的比值，该值一般小于或等于1，其计算公式如下

(5)

其中Ai代表节点i的感知覆盖范围；Rs为节点的感知半径，一般取2Rs≤Rk；A代表整个覆盖区域的面积，n表示节点数。

均匀度用以衡量节点部署的均衡性，起到了平衡能量负载的作用。一般由节点间距离的标准差表示，标准差越小，均匀度越小，即节点覆盖的均匀性越好，其计算公式如下：

(6)

其中Ki代表节点i的邻居节点数，Dij表示节点i和j的距离，Mi表示节点i与邻居节点的平均距离，n表示节点数。

4.1 在正弦曲线上的部署仿真

4.1.1 仿真实例

在本组实验中，在三维空间内随机产生30个节点，部署目标路径为一条正弦曲线。图5(a)是节点初始状态，图5(b)为节点最终部署状态，图5(c)为算法部署过程(其中蓝色线表示节点的移动路径，粉色圆球表示节点初始位置，红色圆球表示节点最终部署位置)。

(a) 节点初始部署状态

(b) 节点最终部署状态

(c) 节点的移动路径

4.1.2 性能分析

图6所示为正弦曲线在节点个数不同时，通过基础虚拟力算法(以下简称未改进算法)和加入了“引力曲线”的算法(以下简称改进算法)所得到仿真结果的路径覆盖率曲线和路径均匀度曲线。

如图6(a)所示，改进算法所达到的节点覆盖率明显优于未改进算法。特别是在改进算法的仿真中当节点个数等于10时，覆盖率值高达为1，虽然随着节点数目的增加覆盖率有所减小，但整体覆盖效果良好，覆盖率值较高并趋于稳定；未改进算法则因只通过节点间虚拟力的作用完成部署，最终导致节点充斥在整个空间区域，不能准确地覆盖目标路径，造成覆盖率较低。随着节点数目的增加覆盖率稍有提高，原因是空间区域内节点覆盖目标路径的随机性概率增大。

如图6(b)所示，改进算法所获得的路径均匀度明显优于未改进算法，且不会由于节点数目的变化而影响其稳定性，始终保持在0.1左右。未改进算法的均匀度会随着节点个数的增多而越来越小，原因是个数的增多使得每个节点的邻居节点密度变大，增大了相互之间的虚拟力作用，从而使节点可以较为均匀地部署在目标区域。

(a) 路径覆盖率曲线

(b) 路径均匀度

图7所示为正弦曲线在节点数量固定在30个时，未改进算法和改进算法所得到的路径覆盖率随节点部署时长的变化曲线。结果显示改进算法明显优于未改进算法，且会在较短时间内快速得到较优覆盖率，响应速度较快。

图7 路径覆盖率随时间变化曲线

4.2 在螺旋曲线上的部署仿真

4.2.1 仿真实例

在本组实验中，在三维空间内设置随机产生100个节点，部署目标为一条螺旋曲线。图8(a)是节点初始状态，图8(b)为节点最终部署状态，图8(c)为算法部署过程 (其中蓝色线表示节点的移动路径，粉色圆球表示节点初始位置，红色圆球表示节点最终部署位置)。

4.2.2 性能分析

图9所示为螺旋曲线在节点个数不同时，未改进算法和改进算法所得到仿真结果的覆盖率曲线和均匀度曲线。

如图9(a)所示，改进算法的节点覆盖率值接近等于1，基本实现对目标路径的完全覆盖，覆盖效果远远好于未改进算法。

如图9(b)所示，改进算法所获得的节点均匀度优于未改进算法，虽然目标路径复杂使得节点覆盖均匀性有所降低，但随着节点个数的增加覆盖效果有所提高。

图10所示为空间螺旋曲线在节点个数固定在50个时，未改进算法和改进算法所得到的路径覆盖率随节点部署时长的变化曲线。对比图7可以看出，改进算法在复杂曲线的节点覆盖响应速度慢于简单曲线，但是也可以在得到较高覆盖率。

(a) 节点初始部署状态

(b) 节点最终部署状态

(c) 节点的移动路径

(a) 路径覆盖率对比

(b) 路径均匀度对比

图10 路径覆盖率随时间变化曲线

5 结 论

本文提出了一种基于“引力曲线”的空中无线传感器网络复杂路径自主部署算法，与只适用于区域空间部署的传统的虚拟力算法相比，该算法针对应急救援中路径搜索的实际需要，实现了对三维空间复杂路径的自主部署。仿真实验结果表明，该算法可明显改善部署性能。

[ 1] Pakzad S N, Fenves G L, Kim S, et al. Design and implementation of scalable wireless sensor network for structural monitoring. American Society of Civil Engineers, 2014, 14(1):89-101

[ 2] Nadeem A, Hussain M A, Owais O, et al. Application specific study, analysis and classification of body area wireless sensor network applications. Computer Networks, 2015, 83: 363-380

[ 3] Anisi M H, Abdul-Salaam G, Abdullah A H. A survey of wireless sensor network approaches and their energy consumption for monitoring farm fields in precision agriculture. Precision Agriculture, 2014, 16(2):216-238

[ 4] Costa F G, Ueyama J, Colombo A, et al. The use of unmanned aerial vehicles and wireless sensor networks for spraying pesticides. Journal of Systems Architecture, 2014, 60(4):393-404

[ 5] Ueyama J, Freitas H, Faical B S, et al. Exploiting the use of unmanned aerial vehicles to provide resilience in wireless sensor networks. IEEE Communications Magazine, 2014, 52(12):81-87

[ 6] Ahmed N, Kanhere S S, Jha S. Link characterization for aerial wireless sensor networks. In: Proceedings of the 2011 IEEE GLOBECOM Workshops (GC Wkshps), Houston, USA, 2011.1274-1279

[ 7] Wang X W, Shen Y, Wu J R, et al. A k-coverage algorithm in three dimensional wireless sensor networks. In: Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology (IC-BNMT), Beijing, China, 2010. 1089-1093

[ 8] Du X, Lin F. Improving sensor network performance by deploying mobile sensors. In: Proceedings of the 24th IEEE International Conference on Performance, Computing and Communications, Phoenix, USA, 2005. 67-71

[ 9] 方华京, 魏然. 人工势场法在多机器人运动中的研究. 控制工程, 2007, 14(2): 115-117

[10] Howard A, Mataric M J, Sukhatme G S. Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In: Proceedings of the 6th International Conference on Distributed Autonomous Robotic Systems, Fukuoka, Japan, 2002. 299-308

[11] Zou Y, Charkrabarty K. Sensor deployment and target localization in distributed sensor networks. ACM Transactions on Embedded Computing Systems, 2014, 3(1): 61-91

[12] Zou Y, Chakrabarty K. Sensor deployment and target localization based on virtual forces. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications, San Francisco, USA, 2003, 2: 1293-1303

[13] 陶丹,马华东,刘亮. 基于虚拟势场的有向传感器网络覆盖增强算法. 软件学报, 2007,18(5): 1152-1163

[14] Zhao J, Zeng J C. A virtual potential field based coverage algorithm for directional networks. In: Proceedings of the 21st Annual International Conference on Chinese Control & Decision Conference, Guilin, China, 2009. 4590- 4595

[15] 周浦城,崔逊学,王书敏等. 基于虚拟力的无线传感器网络覆盖增强算法. 系统仿真学报, 2009 (5): 1416-1419

[16] Wischounig-Strucl D, Quartisch M, Rinner B. Prioritized data transmission in airborne camera networks for wide area surveillance and image mosaicking. In: Proceedings of the 2011 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), Colorado Springs, USA, 2011. 17-24

[17] Watai T, Machida T, Ishizaki N, et al. A lightweight observation system for atmospheric carbon dioxide concentration using a small unmanned aerial vehicle. Journal of Atmospheric & Oceanic Technology, 2006, 23(5):700-710

Research on complex path self-deployment for aerial wireless sensor networks

Jiao Yaoyao, Tan Li, Su Weijun, Yang Minghua, Hu Jipeng

(School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048)

To realize the monitoring of the complex path of a target in a real environment, a virtual force based three-dimensional complex path self-deployment algorithm for aerial wireless sensor networks was proposed. The algorithm innovatively adopts the “gravity-curve” generated by the complex path to build the virtual force field, thus the nodes in a wireless sensor network can accomplish the coverage of the target path adaptively. The simulation results showed that, compared with traditional virtual force algorithms, the proposed algorithm achieved the faster deployment process as well as the higher path coverage faster, and reach and evenness.

aerial wireless sensor network (AWSN), three-dimensional deployment, complex path, virtual force

10.3772/j.issn.1002-0470.2016.01.012

① 国家自然科学基金(61402022)，北京市自然科学基金(4132025)，北京市青年英才计划(YETP1448)和北京市哲学社科规划(14JGB033)资助项目。

2015-07-01)

② 女，1991年生，硕士生；研究方向：无线传感网技术；联系人，E-mail:jiaoyaoyao11@126.com(