无线传感器网络三维定位算法研究

张欣慧，徐晶晶，许必宵，赵学健，孙知信

(1.南京邮电大学 物联网学院，江苏 南京 210003;2.南京邮电大学 理学院，江苏 南京 210003)

无线传感器网络三维定位算法研究

张欣慧1，徐晶晶1，许必宵2，赵学健1，孙知信1

(1.南京邮电大学 物联网学院，江苏 南京 210003;2.南京邮电大学 理学院，江苏 南京 210003)

节点的位置信息是无线传感器网络应用的基础。节点定位技术作为无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。现有的大多数定位算法针对平面应用设计，而在实际应用中，由于地形限制或者环境限制，使得无线传感器往往在空间上呈立体分布，而不是平面分布，所以需要把定位研究扩展到三维空间中。针对无线传感器网络静态节点定位算法的特点，介绍了二维定位算法的分类，在此基础上系统地研究了近年来最新的三维定位理论和算法。主要根据基于测距的定位和无需测距的定位将三维定位算法分为两大类，每类中再分为集中式定位和分布式定位，其中详细研究了一些热门的三维定位算法并总结了它们的优缺点。在综合分析当前定位算法不足的基础上，指出了未来三维定位算法的研究方向。

无线传感器网络；三维空间；定位算法；节点定位；测距

0 引 言

无线传感器网络(WSNs)如今已经成为日常生活中的重要组成部分，它在军用、民用、工商业等领域都有着广泛的应用前景。节点定位在这些应用中是WSNs配置和运行的关键问题，事件发生的位置和节点所包含的信息都建立在监控消息的基础上，毫无疑问，没有位置信息的监控消息是没有意义的。

尽管现实中的无线传感器网络往往被布置在复杂的三维地形中，但是大多数定位技术都是假定在二维网络部署的情况下提出的，而且一般这些适用于二维地形的定位技术并不能简单扩展到三维环境中。传统的二维定位算法往往分为集中式定位算法和分布式定位算法，或者分为基于测距的定位算法和无需测距的定位算法。此外，在基于测距的定位中常用的测距算法包括ToA、RSSI、AoA、TDoA。这些分类方式同样可以扩展到更符合真实情况的三维环境下的坐标计算和定位算法中。

三维定位算法的研究目前有两个大方向：一是将三维定位的问题降维到二维平面上来解决；二是通过对二维定位算法进行改进，将之扩展到三维定位上来，但这会提高原算法的时间和空间复杂度。大部分二维定位算法的研究文献都是根据定位的实现方式来分类，例如划分为集中式定位和分布式定位、基于测距的定位和无需测距的定位等。也有少部分文献提出根据网络架构进行分类，例如划分为有锚节点的定位和无锚节点的定位等。

文中主要根据基于测距的定位和无需测距的定位将三维定位算法分为两大类，每类中再分为集中式定位和分布式定位，其中详细研究了一些热门的三维定位算法并分析总结了它们的优缺点。

1 基于测距的定位算法

基于测距的定位是指首先通过测距算法测量节点间的距离或者角度信息，之后利用所测信息通过数学计算得出未知节点坐标的方式。下文将基于测距的三维定位算法按照节点处理信息的方式分为集中式定位和分布式定位分别进行研究。

(1)集中式定位。

集中式定位是指将各个节点所收集到的信息传送到服务器节点进行处理，计算出未知节点坐标位置的方式。

文献[1-3]提出了一种被引用较多的Landscape-3D定位算法。如图1所示，它需要借助移动的定位辅助装置LA在监测区域上空周期性地广播自身的位置信息，网络中的未知节点通过接收到的位置信息，再利用RSSI计算其与LA之间的距离来确定自身位置。该算法主要依靠LA装置的灵活性和健壮性，不需为节点配备GPS，但对LA的硬件装备需求较高。

文献[4]提出结合MDESM算法的微差分进化算法，根据收集到的来自UAV的信息计算未知节点的位置坐标。

文献[5]以节点间的欧氏距离构成的相似度矩阵为基础，结合计算量过高的MDSMAP算法和LMDS算法并加入对测距信息的利用策略后，提出了FastMDSMAP算法，减少了定位时节点的能量消耗和计算时的时间复杂度。

图1 Landscape-3D定位算法

文献[6]提出一种给地震中的幸存者进行3D定位的3DLM算法，以提高在地震后搜索和营救幸存者的速度。该方案首先在塌陷区周围设置移动基站，使用RSSI估计幸存者和移动基站之间的距离，通过三边定位法确定幸存者的粗略位置；通过估计幸存者到三个移动锚节点(被安置在形如等边三角形的设备的三个角上)之间的距离来计算幸存者的精确位置。

文献[7]基于Euclidean算法提出了一种三维定位算法，通过构建立体模型将未知节点与锚节点之间距离的计算问题转化为六面体模型顶点间距离的求解问题，再利用所提出的坐标法求解节点的位置并通过循环迭代求精。

文献[8]提出一种建立在RSSI值基础上、复杂度有所减少的3D-三边定位法COLA。该算法通过使用拥有两个位置的超级锚节点(这两个位置成对，只有z轴坐标不同)来降低复杂度。

文献[9]提出了一种在使用RSSI和三边定位法计算未知节点坐标之前预处理的方案：基于凹凸性划分和分层的3D-CDD算法。该算法首先根据节点的高度将WSNs定位区域水平划分为几个适当的逻辑层，并在每层中根据凹凸性的不同划分为几个分支区域，以减小由于网络地形的凹凸程度不同造成的误差。

基于测距的三维定位算法中需要测量大量的距离信息或角度信息，且与二维定位算法相比增加了一个维度的信息，这恰好迎合了集中式定位算法中服务器节点计算量和存储量没有限制的优点。但同时集中式定位算法需要传感器节点和服务器节点之间的大量通信，导致网络通信量较大，且距离服务器节点距离较近的节点耗能大且易失效，故集中式定位算法不适用于资源受限型网络。

(2)分布式定位。

分布式定位是指未知节点根据与通信范围内的邻居节点交换的信息在后台自行计算自己的坐标位置的方式。

文献[10]提出了基于传统三角计算的Constrained-3D算法。该方案假定锚节点都部署在底部同一平面内，以该平面为中心向上依靠测量与邻居节点之间的距离来推算未知节点的位置。

文献[11]提出的ILAH-3D算法将二维的经典算法AHLos扩展到三维，增加了普通节点升级为锚节点的验证条件，并采用加权最小二乘法来减少累积误差。该算法还通过约束协作算法的执行条件，借助节点间位置关系的同时再利用新升级的锚节点进行重复定位运算，以提高节点定位的精度。

文献[12]提出了两种适用于各向异性无线传感器网络的三维定位算法:混合粒子群算法(HPSO)和基于生物地理学的优化算法(BBO)。HPSO改善了PSO不成熟收敛的问题，BBO在生物有机体在分配的地域集体学习的生物地理学的基础上，应用迁移算子在不同的栖息地之间选择性地分享信息。该方案适用于在高噪声环境下对目标节点进行高精度定位的情况，可以推广应用到救援工作当中。

分布式定位算法中每个节点都根据从通信范围内的邻居节点传来的信息在后台计算自己的位置，降低了网络通信量且节省了网络资源的消耗，可推广至各种规模的无线传感器网络。但由于普通节点资源受限，计算能力和存储能力相对于服务器来说较弱，难以实现复杂算法。

2 无需测距的定位算法

无需测距的定位是指依靠网络连通性即可完成定位，无需测量绝对距离和角度的方式，它通过估计节点间的跳数或确定包含未知节点的可能区域从而求质心的方法来确定未知节点的位置。下文将无需测距的三维定位算法按照节点处理信息的方式分为集中式定位和分布式定位分别进行研究。

(1)集中式定位。

文献[13]提出了一种无需测距的基于球壳交集的APIS算法。该方案将基于三角形的APIT算法扩充到三维，划分空间为球壳并取球壳交集来定位，其定位精度受锚节点密度和分布影响较大。

其他还有一些同APIS类似的，将APIT扩展到三维空间来使用的算法，如：基于垂直平分线的PB-APIT算法[14]；可以为周围邻居锚节点少于三个的未知节点定位的RSSI-APIT算法[15]；在APIT中采用目标搜索的算法[16]；适用于立方体空间，利用正中面的APIT-3D算法[17]；使用了蒙特卡洛法和RSSI滤波抽样法的MC-APIT算法[18]。文献[19]总结了上述算法的定位精度，提出了基于费马点分离的FM-APIT-3D算法。如图2所示，利用费马点将三棱锥划分为四块，可以显著改善定位精度和覆盖率。以上与APIT有关的几种方法均易受到锚节点密度及分布的影响。

图2 费马点分离模型

文献[20]研究了最简单的无需测距的3D-质心定位算法。锚节点向周围发送包含自己位置信息的信标，未知节点收集到邻居锚节点发来的信标后通过计算多个锚节点坐标的质心来估计自己的位置。该算法虽成本、耗能较低，但同时定位误差很大。

文献[21-22]提出了3D-加权质心定位算法，在计算质心的过程中引入了锚节点与未知节点之间的边权。文献[23]提出的改进的加权质心定位算法使用一个优化阈值来限制锚节点的数量，提高了定位精度。文献[24]在3D-加权质心定位算法中引入了Mamdani&Suggano模糊推理系统，结合RSSI解决了边权如何寻找和计算的问题。

文献[25]提出了一种基于球面坐标的SBLS算法。未知节点通过与移动锚节点之间交互的信息来构建多元线性方程组，再利用克莱姆法则进行求解并解决多解、无解问题，最终利用最小二乘法进行优化。

无需测距的三维定位算法经常被用于以测控和控制为目的的应用当中，此类应用中大量的数据需要汇总到数据中心进行处理。此外，集中式定位算法定位精度较高，但同时也会因网络资源紧缺而受到限制。

(2)分布式定位。

文献[26]在结合了ROCRSSI算法中锚节点多次广播信标信息的方案和ALS算法中无线电信号强度随传输距离的增加而衰减的特性的基础上，提出了DBRF-3D算法。该算法属于无需测距的定位算法，只需要锚节点广播自身的信标信息，在锚节点一跳通信范围内的未知节点通过监听到的信标信息来估计自身位置。

文献[27]将分布式定位算法Boundingbox扩展到三维空间。未知节点的所有邻居锚节点根据通信范围作球，各在所作球中取一个三边分别与x,y,z轴平行的内接正方体，再取各内接正方体的交集确定出包含有未知节点的限定立方体，之后用该立方体的质心作为未知节点的估计位置。该算法的优点是定位计算量很小，适用于运算复杂的三维定位。

文献[28]在结合DV-Hop和Boundingbox的基础上提出DB算法。该算法克服了Boundingbox算法中因为锚节点通信范围有限而对锚节点数量要求较高的弊端。

文献[29]对定位误差较大的三维DV-Hop算法进行了改进，在充分利用地形特点的基础上提出了基于近似投影校正的三维定位算法。该算法将三维DV-Hop算法所计算出的结果近似投影到靠近地形表面的位置，大幅提高了定位精度。

文献[30]提出了改进的蝙蝠算法(IBA)并将三维定位问题转移到全局优化上来，改善了BA早熟收敛和收敛速度慢的缺点。又利用惯性权因子和Levy飞行策略修改了速度和位置的方程，加快了收敛速度并实现了勘测开发能力的平衡。

分布式定位算法资源利用率较高。三维环境中的节点定位过程相对于二维环境来说资源消耗量较大，所以更倾向于采用分布式方法。但分布式定位算法由于节点资源的紧缺，难以追求高精确度。

3 综合分析

(1)基于测距的定位算法。

基于测距的定位算法相对于无需测距的定位算法来说定位精度较高，但同时也对硬件设备要求高，计算量和通信量开销较大，这会导致网络耗能多、成本高、生命周期短。此外，基于测距的定位算法受锚节点的密度及分布影响较大，且在三维环境中可能会导致空间多解问题。

综合考虑上述集中式定位算法和分布式定位算法的优缺点，由于分布式定位算法对节点计算能力和存储能力的要求更具平均性，三维环境中在使用基于测距的定位算法的同时更倾向于采用分布式方法。

(2)无需测距的定位算法。

考虑到三维环境中往往有较多的障碍物阻碍电磁波的传播，无需测距的定位算法排除了测量绝对距离和角度时的测量误差，所受环境干扰较小，成本和功耗较低，扩展性好，更适用于数量级较高的三维环境。但同时无需测距的定位算法定位精度普遍较低，对网络连通度和锚节点密度要求较高。

综合考虑上述集中式定位算法和分布式定位算法的优缺点，由于分布式定位算法资源利用率较高，三维环境中节点定位过程的资源消耗量较大，在使用无需测距的定位算法的同时更倾向于采用分布式方法。

4 结束语

文中对无线传感器网络中的三维定位算法进行了研究。目前所研究的三维定位算法大部分是通过对二维定位算法进行改进得来的，一定程度上会提高原算法的时间和空间复杂度，同时它们在计算量、通信量和精度等方面存在较大的差别，适用范围也有所不同。虽然说三维定位近年来已经取得了长足进步，但还是有一些方面亟待完善：

(1)传统的获得锚节点位置的方法是通过最初为节点配备GPS来实现的，但因为GPS的功耗大、体积大、成本高，并且在严重信号阻碍的环境中信号可能会十分微弱甚至接收不到。无锚节点的定位算法，可以替代多个不同位置的静止锚节点的移动锚节点算法将会解决无线传感器网络定位应用中GPS的配置问题，是今后的一大研究热点。

(2)基于测距的定位算法常借助电磁波信号测量距离，虽然能够实现精确定位，但对硬件设备要求高，计算量和通信量开销较大，电磁波的传播在三维环境中会受到较多障碍物的阻碍。同时无需测距的定位算法对网络连通度和锚节点密度要求较高，定位精度普遍较低。未来的三维定位将把降低基于测距的定位算法的硬件代价，提高无需测距的定位算法的定位精度和鲁棒性作为研究热点。

(3)集中式定位算法中服务器节点的计算量和存储量没有限制，但由于需要传感器节点和服务器节点之间的大量通信，网络通信量较大，虽然定位精度较高，但不适用于资源受限型网络。分布式定位算法资源利用率较高，但由于单个节点资源受限，难以实现复杂算法，定位精度较低。未来的研究方向除了降低集中式方法的通信资源消耗，提高集中式方法的定位精度以外，还可以综合集中式定位和分布式定位的优点形成混合式定位算法，以平衡资源利用率和定位精度之间的矛盾，但实施过程较为复杂。

总体来说，节点的位置信息是无线传感器网络应用的基础。未来三维定位算法的研究热点是进一步提高定位精度、定位覆盖率，增强鲁棒性，降低能耗，以便在无线传感器网络中进行大规模的实际应用。

[1]ZhangL,ZhouX,ChengQ.Landscape-3D:arobustlocalizationschemeforsensornetworksovercomplex3Dterrains[C]//Proceedingsof31stIEEEconferenceonlocalcomputernetworks.[s.l.]:IEEEComputerSociety,2006:239-246.

[2]VillasLA,GuidoniDL,UeyamaJ.3Dlocalizationinwirelesssensornetworksusingunmannedaerialvehicle[C]//12thIEEEinternationalsymposiumonnetworkcomputingandapplications.[s.l.]:IEEE,2013:135-142.

[3]CardosoCB,GuidoniDL,MaiaG,etal.Anenergyconsumptionawaresolutionforthe3DlocalizationandsynchronizationproblemsinWSNs[C]//Braziliansymposiumoncomputernetworksanddistributedsystems.[s.l.]:IEEE,2014:376-385.

[4]SalehinejadH,ZadehR,LiscanoR,etal.3Dlocalizationinlarge-scalewirelesssensornetworks:amicro-differentialevolutionapproach[C]//IEEE25thannualinternationalsymposiumonpersonal,indoor,andmobileradiocommunication.[s.l.]:IEEE,2014.

[5]ZhouZ,HuP,LiuQ,etal.MDS-basedfastlocalizationalgorithmforwirelesssensornetworks[J].ChineseJournalofSensorsandActuators,2007,20(10):2303-2307.

[6]WangJ,ChengZ,JingL,etal.Designofa3DlocalizationmethodforsearchingsurvivorsafteranearthquakebasedonWSN[C]//3rdinternationalconferenceonawarenessscienceandtechnology.[s.l.]:IEEE,2011:221-226.

[7] 唐良瑞,宫 月,罗艺婷,等.一种基于Euclidean的无线传感器网络三维定位算法[J].电子学报,2012,40(4):821-825.

[8]ZhangA,YeX,HuH.Pointintriangletestingbasedtrilaterationlocalizationalgorithminwirelesssensornetworks[J].KsiiTransactionsonInternet&InformationSystems,2012,6(10):2567-2586.

[9]WangRJ,BaoHL,ChenDJ,etal.3D-CCD:anovel3Dlocalizationalgorithmbasedonconcave/convexdecompositionandlayeringschemeinWSNs[J].AdHoc&SensorWirelessNetworks,2014,23(3):235-254.

[10]LiangJ,ShaoJ,XuY,etal.Sensornetworklocalizationinconstrained3-Dspaces[C]//Proceedingsofthe2006IEEEinternationalconferenceonmechatronicsandautomation.[s.l.]:IEEE,2006:49-54.

[11]RongbinQI,SijinLI,TianyiMA,etal.Iteration-basedlocalizationalgorithmforwirelesssensornetworkinthree-dimensionalspace[J].ChineseJournalofSensors&Actuators,2012,25(5):644-650.

[12]KumarA,KhoslaA,SainiJS,etal.Stochasticalgorithmsfor3Dnodelocalizationinanisotropicwirelesssensornetworks[J].AdvancesinIntelligentSystems&Computing,2013,201:1-14.

[13] 吕良彬,曹 阳,高 洵,等.基于球壳交集的传感器网络三维定位算法[C]//2006年全国通信软件学术会议.出版地不详:出版者不详,2006.

[14]YangJ,LiuF.AmodifiedlocalizationalgorithmofAPITbasedonperpendicularbisectorfeatureforwirelesssensornetwork[J].ChineseJournalofSensors&Actuators,2008,21(8):1453-1457.

[15]FengXF,QiHB.ImprovementandsimulationforalocalizationbasedonAPIT[C]//Internationalconferenceoncomputertechnologyanddevelopment.[s.l.]:IEEE,2009:68-72.

[16]LiX,GaoH,LvL.AnimprovedAPITalgorithmbasedondirectionsearching[C]//5thinternationalconferenceonwirelesscommunications,networkingandmobilecomputing.[s.l.]:IEEE,2009:1-4.

[17]LiuZQ,WangXF.WSNthree-dimensionallocalizationmethodbasedonmidperpendicularplanesegmentation[J].ComputerEngineering,2010,36(14):90-92.

[18]WangJ,FuJ.ResearchonAPITandMonteCarlomethodoflocalizationalgorithmforwirelesssensornetworks[M]//Lifesystemmodelingandintelligentcomputing.Berlin:Springer,2010:128-137.

[19]XiongX,YanC.Three-dimensionallocalizationalgorithmofAPITbasedonfermat-pointdividedforwirelesssensornetworks[C]//Seventhinternationalsymposiumoncomputationalintelligenceanddesign.[s.l.]:IEEE,2014:521-524.

[20]BulusuN,HeidemannJ,EstrinD.GPS-lesslowcostoutdoorlocalizationforverysmalldevices[J].RonalOmmnaon,2000,7(5):28-34.

[21]ShiQ,HuoH,FangT,etal.A3Dnodelocalizationschemeforwirelesssensornetworks[J].IEICEElectronicsExpress,2001,666(43):167-172.

[22]LiuL,ChongJS,WangXQ,etal.Adaptivesourcelocationestimationbasedoncompressedsensinginwirelesssensornetworks[J].InternationalJournalofDistributedSensorNetworks,2012,2012:141-149.

[23]XuL,WangK,JiangY,etal.Astudyon2Dand3Dweightedcentroidlocalizationalgorithminwirelesssensornetworks[C]//3rdinternationalconferenceonadvancedcomputercontrol.[s.l.]:IEEE,2011:155-159.

[24]NandaM,KumarA,KumarS.Localizationof3DWSNusingMamdaniSuganofuzzyweightedcentriodapproaches[C]//IEEEstudents’conferenceonelectrical,electronicsandcomputerscience.[s.l.]:IEEE,2012:1-5.

[25]DaiGuilan,ZhaoChongchong,QiuYan.Alocalizationschemebasedonsphereforwirelesssensornetworkin3D[J].ActaElectronicaSinica,2008,36(7):1297-1303.

[26]ZhuH.Anoveldistributedandrange-freelocalizationalgorithminthree-dimensionalwirelesssensornetworks[J].ChineseJournalofSensors&Actuators,2009,22(11):1655-1660.

[27]LiJuan,WangKe,LuChanggang.Boundingcube:alocalizationschemeforwirelesssensornetworksin3D[J].PeriodicalofOceanUniversityofChina,2009,39(6):1265-1268.

[28]YangS,ZhangB,WangK,etal.DB:adeveloped3DpositioningalgorithminWSNbasedonDV-Hopandboundingcube[C]//Internationalconferenceoncomputerandmanagement.[s.l.]:IEEE,2011:1-4.

[29] 胡中栋,谢金伟.基于近似投影校正的无线传感器网络三维定位机制[J].传感技术学报,2014,27(11):1573-1577.

[30]SharmaSPKM.Radiallyoptimizedzone-dividedenergy-awareWirelessSensorNetworks(WSN)protocolusingBA(BatAlgorithm)[J].IETEJournalofResearch,2015,61(2):170-179.

Survey of 3D-localization Algorithms in Wireless Sensor Networks

ZHANG Xin-hui1,XU Jing-jing1,XU Bi-xiao2,ZHAO Xue-jian1,SUN Zhi-xin1

(1.College of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The information of node localization is the base in applications of Wireless Sensor Networks (WSNs).Node localization,as a critical technology of WSN,has been the basis of most applications of WSN.At present,the research on sensor network localization commonly on two-dimensional,but in practical application,because of limit to terrain or environment,the wireless sensor sometimes distribute in three-dimensional,not on plane,so expanding the research to three-dimensional is need.According to the characteristics of static node localization algorithm for wireless sensor network,the classification of 2D-localization algorithms are introduced.On this basis,the state-of-the-art researches of 3D-localization theories and algorithms are systematically summarized.The 3D-localization algorithms are mainly divided into range-based and range-free.Each category is divided into centralized and distributed again.Then some popular 3D-localization algorithms are introduced in detail and summarized the advantages and disadvantages.Based on analysis of the disadvantages of existing localization algorithms,the future research directions of 3D-localization algorithms in WSNs are also pointed out.

Wireless Sensor Networks (WSNs)；Three-Dimensional (3D) space；localization algorithms；node-positioning；distance measurement

2016-02-25

2016-06-04

时间：2016-11-22

国家自然科学基金资助项目(60973140，61170276，61373135)；江苏省产学研项目(BY2013011)；江苏省科技型企业创新基金(BC2013027)；江苏省高校自然科学研究重大项目(12KJA520003)

张欣慧(1994-)，女，研究方向为无线传感器网络三维定位；赵学健，博士，副教授，硕士生导师，研究方向为无线网络关键技术、大数据关键技术；孙知信，博士，教授，博士生导师，研究方向为计算机网络与安全、多媒体通信、移动互联网。

http://www.cnki.net/kcms/detail/61.1450.tp.20161122.1227.008.html

TP393

A

1673-629X(2016)12-0195-05

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