航空信标辅助WSN三维定位的移动路径规划方法

谭中华，徐 玉

(温州大学 物理与电子信息工程学院，浙江 温州 325035)

航空信标辅助WSN三维定位的移动路径规划方法

谭中华，徐 玉

(温州大学 物理与电子信息工程学院，浙江 温州 325035)

三维定位对于相当多的无线传感器网络(WSN)应用非常重要，但通常复杂度与成本较高。基于移动(航空)信标辅助的三维定位是相对节约成本的一类方法。针对这类方法需要解决的移动路径规划问题，提出了一种实现简单、路径长度短的三维移动路径规划方法。在三维空间中，航空信标只需在两平面上对三维部署区域进行两次相互独立的二维扫描。3D SCAN、3D DOUBLE SCAN、3D HILBERT、3D CIRCLES、3D S-CURVES和3D LMAT是该方法的六种典型实现。仿真实验结果表明，基于该路径规划方法的六种典型路径都能够满足三维定位需要。其中，3D S-CURVES路径长度最短、定位精度最高。

三维；无线传感器网络；定位；航空信标；路径规划

0 引 言

近年来，无线传感器网络(Wireless Sensor Networks,WSNs)在环境监测与保护、军事侦查、目标追踪等领域有着非常广泛的应用。在这些应用中，位置是最基本的上下文信息之一。因此，节点的定位问题受到了研究者的广泛关注。

定位是指节点运用某种技术或方法，确定自身位置。现有的无线传感网络采用更多的是基于信标节点(已知自身位置的节点)的定位方法，如基于测距的RSS[1]、TDoA[2]、TOA[3]和AOA[4-5]和非测距的质心定位[6-7]、DV-Hop[8]、MDS-MAP[9]等。在这些基于静态信标节点的定位方法中，节点的定位精度与其附近信标节点的数量和质量直接相关。为了获得好的定位精度，就需要在部署区域中放置大量的静态信标节点，这势必会导致定位成本的大幅上升。为此，研究者提出了基于移动信标节点的辅助定位方法[10]。移动信标节点沿一定的轨迹扫描整个部署区域，在移动的过程中以一定的频率广播包含自身动态位置信息的虚拟信标；未知节点接收通信范围内的虚拟信标，根据其与虚拟信标的距离或方位信息计算自身位置。在该方法中，可重复利用的移动信标节点取代了大量的静态信标节点，降低了定位成本；移动信标节点给未知节点提供大量的虚拟信标，降低了估测误差，提高了定位精度。

目前，常用的移动信标有两类：基于无线遥控车[11]的地面移动信标和基于无人机(UAV)[12-13]的航空移动信标。相较于地面移动信标，航空移动信标具有如下优势：

(1)装备有GPS/SINS组合导航系统的UAV能够给航空信标提供实时的高精度位置信息。

(2)空中飞行的航空信标具有更好的无线电通信环境和更广阔的信号覆盖。

(3)在几乎没有障碍的空中，航空信标能够准确地跟踪复杂的移动路径。

(4)航空信标能够安全地出入人工干预困难或危险的区域。

1 问题与挑战分析

就基于移动信标节点的辅助定位而言，无论是采用地面移动信标还是航空移动信标，都需要解决移动信标的路径规划问题。路径直接影响节点的定位精度和航空信标的飞行距离。就二维定位，文献[14]对移动信标的路径规划提出了两个基本要求：首先，移动路径应尽可能覆盖整个部署区域；其次，移动路径应确保未知节点能够获得定位所需条件，且让移动信标尽可能近地经过未知节点。文献[15]提出了SCAN、DOUBLE SCAN和HILBERT三种线性路径方案。文献[16]提出了同心圆路径CIRCLES和“S”形路径S-CURVES。文献[17]提出一种等边三角形路径LMAT。然而，就三维定位的路径规划而言，除了满足文献[14]所提出的两个基本要求外，还需要确保未知节点至少能够接收到四个不共面的虚拟信标才能完成自身定位，从而移动信标节点至少需要在两个不同高度的平面中运动；同时，飞行路径的路径长度应尽可能短，以减少航空信标的能量消耗。

为此，如何在满足上述四个基本条件的基础上寻找出实现简单、路径长度短,同时又能获得较高定位精度的移动路径成为了关键问题。为了解决这个关键问题，文中提出一种新的三维路径规划方法。下面将对新路径规划方法进行介绍，且给出六种典型实现路径。以最小二乘三维定位算法为例，对六种典型实现路径进行了模拟仿真实验。实验结果表明，该方法能够满足三维定位对移动路径的需要。

2 三维路径规划方法

2.1 基本思想

对于布置在山地、深林、沼泽和水下等环境中的三维WSN定位，可将WSN部署区域看作三维空间底部的一个三维区域，如图1所示。未知节点部署在一个凹凸不平的三维空间中，且移动信标只能在部署区域的上空运动。此时，关键是如何设计航空信标节点的移动路径，既能使能量消耗最少，又能获得良好的定位精度。

图1 航空信标辅助三维定位路径规划说明

文中提出的移动路径规划如图1所示。航空信标只需要在两个不同高度的二维平面上对底部的三维部署区域进行两次相互独立的二维平面扫描。每次二维平面扫描应尽可能覆盖整个部署区域，且航空信标应尽可能近地经过未知节点。不同高度的两次二维扫描应确保部署区域内的未知节点至少接收到4个不共面的虚拟信标。这样的移动路径规划方法既能确保未知节点获得定位自身的条件，又能使移动路径长度相对最短。两次二维平面扫描是相互独立的，这是规划方法灵活性的体现，两次扫描可以是任意的平面扫描路径。例如，下层平面使用Nl阶SCAN路径，上层路径使用Nh阶HILBERT路径。

2.2 典型路径

根据上述的路径规划思想，设计了六种较为典型的路径，当然也可以进行任意组合。

以3D SCAN路径为例，如图2(a)所示，该路径在Z坐标为z和z+dz的XY平面上沿Y轴方向对部署区域进行两次相互独立的平面扫描。两次平面扫描分别以Nl阶和Nh阶SCAN进行。在XY平面路径上，Y轴方向平行路径之间的距离为该层路径的分辨率。因此，3DSCAN的路径分辨率由下层路径分辨率dl和上层路径分辨率dh共同决定。

同理可知，3DDOUBLESCAN、3DHILBERT、3DCIRCLES、3DS-CURVES和3DLMAT都是通过对应的二维扫描路径对三维空间进行两次相互独立的扫描，如图2所示。

图2 六种典型实现路径

假设三维部署区域的XY平面是W×W的正方形区域，路径的分辨率为(dl,dh)，则路径长度L的计算公式如下：

L3D SCAN=(4Nl-1)×dl+(4Nh-1)×dh

(1)

L3D DOUBLE SCAN=(4Nl+2Nl-4)×dl+(4Nh+2Nh- 4)×dh

(2)

L3D HILBERT=4Nl×dl+4Nh×dh

(3)

(4)

(5)

(6)

3 仿真实验

运用MATLAB工具模拟如山地、深林和沼泽等三维WSN定位实现。在这些区域中，所有的未知节点都位于航空信标节点的底部。仿真实验中，三维区域中随机部署N个未知节点，航空移动信标沿着六条典型路径飞行，且在移动过程中以一定的频率广播信号，未知节点接收到至少四个不共面的虚拟信标，并通过最小二乘三维定位算法计算自身位置。

3.1 最小二乘三维定位算法

(7)

消除二项式(前n-1个等式减去第n个等式)得：

Kθ=D+E

(8)

其中：

(9)

(10)

(11)

D=

(12)

由式(8)可得θ的最小二乘估计：

θ=(KTK)-1KTD

(13)

3.2 仿真参数

仿真参数及其取值如表1所示。

表1 仿真参数

其中，WSN三维部署区域的长、宽、高为X,Y,Z；未知节点个数为Nodes，典型路径分辨率为(dl,dh)；下层路径Z坐标为z；上下两层路径的Z坐标差为dz；RSS对数正态阴影衰减模型的标准差为σ；实验仿真次数为times。

4 结果与分析

Aerr(xyz)=

(14)

(15)

(16)

4.1Z坐标对定位精度的影响

典型路径的Z坐标由下层路径z坐标和上下两层路径的z坐标差dz共同决定。它是直接影响信标节点与未知节点实际距离的重要因素。

如图3(a)所示，随着z的增大，各典型路径的平均定位误差都随之增大。由此可知，z取值越小，定位误差越小。z坐标越大，未知节点与虚拟信标节点的实际距离就会增大，定位误差也就会越大。如图3(b)所示，各典型路径的平均定位误差随dz的增加呈现出先

图3 Z坐标对定位精度的影响

减后增的变化，且在dz=15m时定位误差最小。dz对系统定位精度的影响受到了通信距离变大和定位算法的相互影响，所以会呈现出先减后增的变化。

4.2 路径分辨率对定位精度的影响

路径分辨率(dl,dh)由下层路径分辨率dl与上层路径分辨率dh共同决定。图4为9种(dl,dh)取值下各典型路径的平均定位误差变化。

图4 路径分辨率(dl,dh)对定位精度的影响

当路径分辨率(dl,dh)取值越大，系统的平均定位误差越大。比较(60,30)和(30,60)，(60,15)和(15,60)，(30,15)和(15,30)的结果可知，dl>dh的平均定位误差要小于dl

4.3 环境噪声对定位精度的影响

环境噪声直接影响节点之间距离的估测。在仿真环境中，通过RSS对数阴影正态估测模型中的标准差σ来控制环境噪声的影响。σ取值越大，环境噪声影响越严重，距离估测误差就越大。如图5所示，随着变量σ的逐渐增大，各典型路径的平均定位误差都随之增大。

图5 标准差σ对定位精度的影响

5 结束语

文中以三维定位对移动路径规划的基本要求为基础，结合航空信标辅助三维定位的特点，提出了一种实现简单、路径长度最短的新三维移动路径规划方法。该方法适用于航空信标节点辅助三维定位，具有较好的灵活性。设计了六种典型实现路径，且能够任意组合，如SCAN和S-CURVES结合的三维移动路径等。灵活多变的移动路径给人们提供了更多的路径规划选择，较短的移动路径长度降低了航空信标节点的能量消耗。未来的工作方向是寻找到适合该类规划方法的定位方法，从而提高该类三维定位的定位精度。

[1]BahlP,PadmanabhanVN.RADAR:anin-buildingRF-baseduserlocationandtrackingsystem[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2000:775-784.

[2]WengY,XiaoW,XieL.TotalleastsquaresmethodforrobustsourcelocalizationinsensornetworksusingTDOAmeasurements[J].InternationalJournalofDistributedSensorNetworks,2011(3):1063-1067.

[3]GirodL,EstrinD.Robustrangeestimationusingacousticandmultimodalsensing[C]//ProceedingsofIEEE/RSJinternationalconferenceontheintelligentrobotsandsystems.[s.l.]:IEEE,2001.

[4]WangJ,ChenY,FuX,etal.3DLoc:threedimensionalwirelesslocalizationtoolkit[C]//IEEE30thinternationalconferenceondistributedcomputingsystems.[s.l.]:IEEE,2010:30-39.

[5]ChenY,LiuZ,FuX,etal.TheoryunderlyingmeasurementofAOAwitharotatingdirectionalantenna[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2013:2490-2498.

[6] 林 玮,陈传峰.基于RSSI的无线传感器网络三角形质心定位算法[J].现代电子技术,2009,32(2):180-182.

[7] 唐明虎,张长宏,昝风彪.无线传感器网络APIT定位算法[J].微型机与应用,2010,29(21):1-4.

[8] 张 震,闫连山,刘江涛,等.基于DV-hop的无线传感器网络定位算法研究[J].传感技术学报,2011,24(10):1469-1472.

[9] 马 震,刘 云,沈 波.分布式无线传感器网络定位算法MDS-MAP(D)[J].通信学报,2008,29(6):57-62.

[10]PriyanthaNB,BalakrishnanH,DemaineED,etal.Mobile-assistedlocalizationinwirelesssensornetworks[C]//ProceedingsoftheIEEEINFOCOM.Miami,FL:IEEE,2005.

[11]SichitiuML,RamaduraiV.Localizationofwirelesssensornetworkswithamobilebeacon[C]//IEEEinternationalconferenceonmobilead-hocandsensorsystems.[s.l.]:IEEE,2004:174-183.

[12]KimK,LeeW.MBAL:amobilebeacon-assistedlocalizationschemeforwirelesssensornetworks[C]//Proceedingsof16thinternationalconferenceoncomputercommunicationsandnetworks.[s.l.]:IEEE,2007:57-62.

[13]LiuZ,ChenY,LiuB,etal.HAWK:anunmannedminihelicopter-basedaerialwirelesskitforlocalization[C]//ProceedingsofIEEEINFOCOM.[s.l.]:IEEE,2012:2219-2227.

[14]SsuKF,OuCH,JiauHC.Localizationwithmobileanchorpointsinwirelesssensornetworks[J].IEEETransactionsonVehicularTechnology,2005,54(3):1187-1197.

[15]KoutsonikolasD,DasSM,HuYC.Pathplanningofmobilelandmarksforlocalizationinwirelesssensornetworks[J].ComputerCommunications,2006,30(13):86.

[16]HuangR,ZarubaGV.Staticpathplanningformobilebeaconstolocalizesensornetworks[C]//IEEEinternationalconferenceonpervasivecomputingandcommunicationsworkshops.[s.l.]:IEEE,2007:323-330.

[17]JiangJ,HanG,XuH,etal.LMAT:localizationwithamobileanchornodebasedontrilaterationinwirelesssensornetworks[C]//Globaltelecommunicationsconference.[s.l.]:IEEE,2011:1-6.

A Path Planning Method of Aerial Beacon Assisted Localization in Three-dimensional Wireless Sensor Network

TAN Zhong-hua,XU Yu

(College of Physics and Electronic Information Engineering,Wenzhou University, Wenzhou 325035,China)

Three-dimensional localization methods play a major role in many WSN applications but usually have high complexity and cost.The method based on mobile (aerial) beacon assisted three-dimensional localization is relatively cost-saving.Path planning for mobile is the fundamental problem for that.A novel three-dimensional mobile planning method is proposed,which is simple implementation and short path.The method is based on the basic requirements of the travel path for three-dimensional localization,and just two-dimensional scanning at two planes of the three-dimensional deployment area.3D SCAN,3D DOUBLE SCAN,3D HILBERT,3D CIRCLES,3D S-CURVES and 3D LMAT are typical implementation of that.Simulation shows that the six type of path based on path planning method proposed can meet the requirements of three-dimensional localization,of which 3D S-CURVES has shortest path length and highest positioning accuracy.

3D;wireless sensor network;localization;aerial beacon;path planning

2016-03-03

2016-06-15

时间：2016-11-22

国家自然科学基金资助项目(61303211)；浙江省自然科学基金资助项目(LQ13F020010)；温州大学研究生创新基金研究项目(3162014038)

谭中华(1990-)，男，研究生，研究方向为无线传感器网络定位；徐 玉,副教授,研究方向为空中飞行机器人与无线传感网络。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1228.046.html

TP393

A

1673-629X(2017)01-0134-05

10.3969/j.issn.1673-629X.2017.01.030