无线传感器网络节点定位研究综述*

吕淑芳

(山西农业大学 信息学院，山西 晋中 030800)

综述与评论

无线传感器网络节点定位研究综述*

吕淑芳

(山西农业大学 信息学院，山西 晋中 030800)

摘要:深入探讨分析了无线传感器网络定位技术，从无线传感器网络定位算法分类、评价指标、距离相关和距离无关定位算法等方面进行分析，重点对比了几种典型算法，结果表明：不同的算法具有应用环境单一性，应结合实际需求选择合适的算法。研究分析了新型无线传感器网络定位方法，主要包括移动锚节点定位算法、三维空间定位算法和智能定位优化算法。总结当前无线传感器网络定位研究中存在的问题，并给出未来改进的研究方向。

关键词:无线传感器网络；定位技术；算法分类；新型无线传感器网络定位方法；智能定位

0引言

无线传感器网络(WSNs)[1]研究涉及广泛且多个学科交叉融合，是一种获取、处理信息的全新技术，广泛应用在国防、医疗、环境、目标跟踪、入侵检测等领域。在无线传感器网络中，传感器节点所监测到的信息,如压力、温度、湿度等，如果没有相对应的位置信息是毫无研究价值的，因此，位置信息对监测活动至关重要。

无线传感器网络的节点通常是动态随机地抛洒在一些人类不可到达或比较危险复杂的区域，这样的网络要求能够协作地来感知、采集、处理网络分布区域内的各种环境和监测对象的信息，并传送给监测者。但由于能耗、计算能力、通信能力等因素极大地限制了无线传感器网络节点，因此，具有分布式、低复杂性、高精度、良好通用性等特点的节点定位方法就被极大的需求。

1定位算法的研究现状

1.1定位算法的性能评价指标和算法分类

经典的评价标准[2]有：定位精度、网络规模、节点密度、锚节点密度、功耗、成本代价、容错性、自适应性、网络连通度等。这些性能评价指标不仅可以用来评价无线传感器网络算法和自身定位系统，同时也是其设计并实现的改进目标。考虑到实际应用中，这些性能指标并不是独立，而是相互关联的，需要结合具体的应用背景来权衡设计，实现适合的定位技术。

无线传感器网络的定位方法有很多种，目前比较普遍的分类方法[1]有以下三种：

1)根据是否测量节点之间的距离可划分为：距离相关算法和距离无关算法。距离相关法定位精度高于距离无关法,但对硬件要求较高、在距离难以测量的场合，需要用距离无关法估算节点间距离。

2)根据网络连通度和拓扑结构可划分为：单跳算法和多跳算法。单跳算法适用范围小，但简单易实现；在一些测量范围比较广的场合则需要采用多跳算法。

3)根据处理信息的方式可划分为：集中式算法和分布式算法。集中式算法适用于监测和控制的应用场景，该算法有较高的精度但需要消耗较大的通信量；分布式算法由于其数据处理实现方式的不同，能够降低网络通信量，但却受到节点能量、计算和存储能力的限制。

目前公认的分类算法是距离相关算法和距离无关算法。

1.2距离相关的定位算法

距离相关算法的定位测量方法分为两大类，基于时间的方法有到达时间(time of arrival,TOA)和到达时间差(time difference of arrival,TDOA)；基于角度的方法有到达角(angle of arrival，AOA)和接收信号强度指示(received signal strength indication,RSSI)。

1.2.1TOA

基于TOA定位测量方法简单，有较高的定位精度，但是要做到严格的时间同步比较难，如何精确测量时间也是一大难点且受外界环境影响比较大。

TOA[3]的发展始于双程测距，定位精度受传播距离的限制，只有在视距(line-of-sight,LOS)范围内才有较高的精度。文献[4]Hangoo Kang 等人提出了TOA误差补偿算法，并将其应用到多径环境中，取得了较好的效果。随之，文献[5]中Andreas Lewandowski等人在工业应用背景下，提出了一种加权TOA算法，实验结果表明，该算法使系统容错性有所提高，并且可降低自身对测距系统的干扰。

1.2.2TDOA

基于TDOA的测距方法，在视距情况下有较高的定位效果，但对硬件的要求较高且信号在传输过程中极易受环境影响，应用的场合也比较单一。

TDOA最早的应用是结合RF信号与超声波信号。加州大学伯克利分校采用TDOA测距技术开发出了Calamari定位系统[6]。一些学者将TDOA测距原理与NTP协议时间同步机制[7]相结合，提出了一种新的时间同步和节点测距的混合算法，不仅可以将时间同步，甚至可得到相对测距。

1.2.3AOA

基于的AOA测距方法,需要额外的硬件设备如天线阵列或有向天线来支持。

由于其实用性，AOA测距并没有得到广泛的应用，最早的应用是文献[8]提出在室内采集角度信息来实现定位。之后在少数节点有定位能力的应用场景下，有些学者提出了确定全部节点的方向和位置信息的定位算法。

1.2.4RSSI

RSSI的方法由于每个传感器节点都有通信测距的能力，因此,RSSI测距方法成本低，但实际应用中，对锚节点数量的要求很高，也容易受到多路径反射、非视线问题等环境因素的影响。

RSSI测距方法最早源于室内定位系统，目前使用广泛的RSSI测距方法有两种：一种是提前设置好定位区域，该方法计算量很小，只需查表或根据事先做好的拟合曲线进行计算即可，但是对实验环境的要求很苛刻，一旦环境有所变化，原有实验结果将失去价值，需要建立新的模型。另一种方法是现场部署定位区域，引入露珠洪泛思想[9]，结合迭代的分布式算法或双曲线模型法，提出了RSSI机制的HCRL(hop-count-ratio-based localization)算法[10]。该算法计算过程较为繁琐复杂，但有较强的适用性。

上述4种测距方法各有适用范围，但综合考虑其优缺点，多数学者研究RSSI测距方法。表1为距离相关的测距技术的性能比较。

表1　距离相关测距技术比较

1.3距离无关的定位算法

距离无关的定位算法[11]相比较距离相关的定位算法，不需要测量距离或角度信息，而是根据网络连通度来估计未知节点的坐标。以下介绍几种典型的距离无关定位算法。

1.3.1质心定位算法

质心(Centroid)定位算法，是美国加州大学的Bulusu等人研究提出的，虽然实现简单，但对锚节点密度的要求比较高，且定位误差比较大。

1.3.2距离向量—跳段定位算法

距离向量—跳段(distance vector-hop，DV-Hop)定位算法是由Niculescu D等人提出，该算法适用场景比较单一，只能用在各向同性的密集网络中，且定位误差较大。大量实验表明，无线传感器网络中的平均连通度为10时，且锚节点比例为10 %时，定位精准度约为33 %[13]。

1.3.3近似三角形内点测试算法

近似三角形内点测试(approximate point-in-triangulation test，APIT)算法，是由He等人提出的。APIT定位算法的理论基础是最佳三角形内点测试(perfect point-in-triangulation test，PIT)法。APIT定位算法对锚节点密度的要求很高。

上述三种典型的测距无关定位算法可看出，测距无关算法是通过网络连通度来进行定位的，且与节点密度紧密相关，大多偏重于理论研究，定位精度较低，适用范围不是很广。不同算法的侧重点有所不同，DV-Hop算法侧重于估计距离，能相对较好地估计出未知节点与锚节点之间的距离；Centroid、APIT算法侧重于估计位置，能够根据网络连通度得到比较精确的位置信息。三种算法的性能比较如表2。

表2　距离无关定位算法性能比较

1.4计算节点位置的主要方法

由距离相关的测距方法得到未知节点与邻居锚节点之间的距离或者角度信息后，需要用三边测量、三角测量或者极大似然估计法、极大极小定位算法来计算未知节点的实际位置。

在实际环境下，需要根据具体的情况选择合适的计算方法，所有计算的前提都是信标节点是准确无误的。文献[14]提出了一种基于信标优化选择(OBS)的定位算法，通过减小定位过程中可能产生的误差来达到提高定位精度的效果。

2新型无线传感器网络定位算法

在传统定位方法—静态的定位技术的基础上，新型的无线传感器网络定位算法应运而生。如，信标节点由静止的变为动态的，用移动的锚节点去定位未知节点；将二维空间的定位拓展到三维空间；定位算法初步定位，智能优化算法实现进一步的优化，提高定位精度等。

2.1移动信标节点定位

移动锚节点定位的应用，最早是Sichitiu M L利用单个移动锚节点与RSSI测距相结合来估计未知节点的位置[15]。

移动锚节点定位采用移动锚节点代替了传统的静止的锚节点，降低了网络中因多跳和传输距离远而产生的定位误差累计，减少了锚节点所需数量，降低了定位成本，提高了定位的精度。如何将路径优化，达到较高的定位性能，并将移动信标节点定位技术广泛应用到大规模的无线传感器网络还需要更加深入的研究。

2.2三维空间定位技术

现有的多数定位技术都是针对二维空间,然而随着传感器网络三维空间定位需求的不断发展,三维空间定位成为研究的趋势与热点。

很多学者将二维空间的定位技术延伸运用到三维空间中,如,四面体质心定位算法、三维DV-Hop，APIT，RSSI定位等，都取得了较好的效果，并得到了一定程度的应用。如，文献[16]提出的三维序列垂心算法；杜巧玲将三边测量法延伸运用到三维空间中进行定位的算法[17]；文献[18]提出的APIS(approximate point in sphere)非距离定位算法等。

三维定位算法将无线传感器网络定位推向了更好更高的前端研究领域，虽取得了一定的研究成果，但仍需要不断完善和进步，如如何缩短定位时间、如何获取优良的锚节点等。

2.3智能优化定位

随着无线传感器网络定位技术的发展，传感器节点本身性能的提升，对定位要求越来越高，智能优化定位算法成为趋势。

文献[19]采用粒子滤波技术，在三维无线传感器网络户外定位中取得了较好的效果；亦可采用神经网络优化定位问题[22]，通过训练建立合适的网络模型，也可通过增加网络节点密度降低定位误差。针对平面空间中节点定位受非视距问题的影响，采用直推式回归的定位算法[20]代替机器学习中的支持向量回归SVR方法，更高的降低定位误差。也有很多智能算法，如遗传算法、模拟退火算法、爬山算法、粒子群算法等，结合定位测量方法和技术用在定位问题中，用作后期优化，达到更好的定位效果。

3结束语

到目前为止，无线传感器网络定位研究已取得了一定的成果，但仍存在很多问题。如何考虑硬件成本的限制；如何平衡节点能耗与定位精度；如何解决算法应用环境单一性问题，寻求更加通用性的定位算法或者系统成为迫切的需求；如何将模拟仿真定位算法应用于具体的现实环境，设计出切合实际的算法或系统尤为重要。

新型的移动无线传感器网络定位、三维空间定位、智能定位技术的研究尚在起步阶段，很多问题需要解决和完善，

这就对算法的适应性和实时性提出了更高的要求；现有算法在安全和隐私问题上都比较脆弱，分布式算法能够有效减少信息被传递的次数，增强安全性，同时也可通过加密、不合法探测与隔离、鲁棒位置计算、位置校验等手段来实现安全性。

随着定位技术的发展、人类生活的需要，无线传感器网络将在能耗、成本、实用性、安全定位、随时变化的节点定位、三维定位等方面着力研究。

参考文献:

[1]王媛媛,周小佳,闫斌.无线传感器网络定位技术研究[J].山东轻工业学院学报，2011,25(1):59-61.

[2]王亮,曹建安.无线传感器网络定位算法研究进展[J].现代电子技术,2011,34(23):27-30.

[3]Sahinoglu Z,Gezici S.Ranging in the IEEE 802.15.4a stan-dard[C]∥IEEE Wireless and Microwave Technology Conference(WAMICON),2006:1-5.

[4]Zafer S,Sinan G.Ranging in the IEEE 802.15.4a standard[C]∥IEEE Wireless and Microwave Technology Conference(WAMICON),2006:1-5.

[5]Andreas L,Christian W.A comprehensive approach for optimizing TOA-localization in harsh industrial environments[C]∥Position Location and Navigation Symposium(PLANS),2010 IEEE/ION,2010:516-525.

[6]Whitehouse K,Karlof C,Woo A,et al.The effects of ranging noise on multihop localization:An empirical study[C]∥The Fourth International Conference on Information Processing in Sensor Networks,IPSN’05,2005:73-80.

[7]Prakash Ranganathan,Kendall Nygard.Time synchronization in wireless sensor networks:A survey[J].Internation Journal of UbiComp(IJU),2010,1(2):92-100.

[8]Niculescu D,Nath B.Ad Hoc positioning system(APS)using AOA[C]∥Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,2003:1734-1743.

[9]王晟.无线传感器网络节点定位与覆盖控制理论及技术研究[D].武汉:武汉理工大学,2006:40-42.

[10] 杜存功,丁恩杰,苗曙光.无线传感器网络改进型节点定位算法的研究[J].传感器与微系统,2010,29(1):52-54.

[11] 肖忠义,冯秀芳.无线传感器网络四面质心定位算法研究[D].太原:太原理工大学,2012:31-33.

[12] 胡咏梅,张欢.一种改进的无线传感器网络质心定位算法[J].计算机工程与科学,2012,34(2):45-49.

[13] Niculescu D,Nath B.DV-based positioning in Ad Hoc network-s[J].Journal of Telecommunication Systems,2003,22(1/4):267-280.

[14] 肖硕,魏学业,王钰.基于信标优化选择的无线传感网络定位方法研究[J].电子测量与仪器学报,2009,23(3):65-68.

[15] Sichitiu M L,Ramadurai V.Localization of wireless sensor networks with a mobile beacon[C]∥2004 IEEE International Conference on Mobile Ad Hoc and Sensor Systems,Fort Lauderdale,2004:174-183.

[16] 刘志华,赵寿君,齐冬梅.三维无线传感器网络节点的序列垂心定位[J].信息系统与网络,2010,40(4):4-6.

[17] 杜巧玲.无线传感器网络三维节点定位问题的研究[D].长春:吉林大学,2009:34-46.

[18] 戴桂兰,赵冲冲,邱岩.一种基于球面坐标的无线传感器网络三维定位机制[J].电子学报,2008,36(7):1297-1303.

[19] Shareef A,Zhu Y F,Musavi M.Localization using neural networks in wireless sensor networks[C]∥Mobilware’08,Innsbruck,Austria,2008:12-15.

[20] Shaifu R,Mohammad R,Youngil P,et al.Localization of wireless sensor networks using artificial neural networks[C]∥9th International Symposium on Communications and Information Technology,ISCIT 2009,2009:639-642.

Research review on wireless sensor networks node localization*

LÜ Shu-fang

(College of Information,Shanxi Agricultural University,Jinzhong 030800,China)

Abstract:Localization technology of wiress sensor networks(WSNs)is deeply discussed and analyzed in some aspects such as classification of WSNs localization algorithms,evaluation criteria,range-based and range-free localization algorithms.Several typical algorithms are mainly compared,analysis results show that different algorithms adapt to a single application environment,appropriate algorithm should be selected combined with actual needs.Several new-style localization methods including mobile beacons node localization algorithm,three dimensional space localization algorithm and intelligent localization optimization algorithms are analyzed.Problems exist in WSNs localization research is summarized and improved research direction in the future is given.

Key words:wireless sensor networks(WSNs);localization technology;algorithms classification;new type WSNs localization method;intelligent localization

DOI:10.13873/J.1000—9787(2016)05—0001—03 10.13873/J.1000—9787(2016)05—0009—04

收稿日期：2015—09—06

*基金项目：山西省科技基础条件平台建设项目(20110910003—0103)；山西省回国留学人员科研资助项目(2011—029)

中图分类号:TP 393

文献标识码:A

文章编号:1000—9787(2016)05—0001—03

作者简介:

吕淑芳(1988-)，女，山西吕梁人，硕士研究生，研究方向为无线传感器网络定位、物联网。