无线传感器网络静态节点定位算法综述



无线传感器网络静态节点定位算法综述

李建坡1,钟鑫鑫1,徐 纯2

(1.东北电力大学信息工程学院,吉林吉林132012;2.国家新闻出版广电总局2021台,黑龙江齐齐哈尔161000)

摘 要:针对无线传感器网络静态节点定位算法特点,总结了无线传感器网络节点定位的基本原理、定位算法的最新进展及其评价标准。从基于测距的静态节点定位算法和无需测距的静态节点定位算法两个方面分类讨论了典型的静态节点定位算法,并对各算法的性能进行归纳比较,说明了目前算法存在的问题,并提出未来发展趋势。

关键词:无线传感器网络;静态节点定位;综述

无线传感器网络(Wireless Sensor Networks,WSN)是由部署在监测区域内大量的传感器节点组成,通过无线通信方式形成的一个多跳的自组织网络系统,其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息,并发送给观察者。在WSN中,位置信息对传感器网络的监测活动至关重要,例如在军事应用、环境监测、医疗保健、目标监测与跟踪、智能交通、物流管理等许多应用领域中,如何确定无线传感器网络中节点的位置信息(节点定位)成为必须解决的关键问题之一[1-4]。从1992年AT&T Laboratories Cambridge开发出室内定位系统Active Badge至今[5],针对不同应用领域,人们已经设计了很多无线传感器网络节点定位系统和算法。但是,每种系统和算法都用来解决不同的问题或支持不同的应用,本文对WSN节点定位的基本原理和国内外开展的相关研究工作进行了分析和总结,本文着重分析了WSN节点定位的现状和存在的问题,明确今后的发展趋势,为WSN节点定位的广大研究人员提供参考和借鉴。

1　WSN节点定位的分类

根据不同分类原则和网络结构,常用的WSN节点定位算法可以进行如下划分:

(1)基于测距技术的定位和无需测距技术的定位

基于测距技术(Range-Based)的定位是通过获得节点间的绝对距离或角度信息,使用三边测量法[6]、三角测量法[7]、极大似然估计法[8]等算法计算节点位置。典型算法有基于RSS的定位算法[9]、基于TOA的定位算法[10,11]、基于TDOA的定位算法[10,11]、基于AOA的定位算法[10]、AHLos定位算法[12]、Cooperative ranging定位算法[13]、Two-Phase positioning定位算法[14]等。无需测距技术(Range-Free)的定位,不需要节点间的绝对距离或角度信息,仅根据网络连通范围、节点间的估计距离等信息实现定位。典型算法有DV-hop定位算法[15]、质心算法[16]、APIT定位算法[17]、凸规划定位算法[18]、MDS-MAP定位算法[19]、MCL定位算法[20]等。

(2)静态节点定位和动态节点定位

静态节点定位指网络中的所有节点位置均固定的定位方法。常用算法有AHLos定位算法[12]、DV-hop定位算法[15]、APIT定位算法[17]、凸规划定位算法[18]、Amorphous定位算法[22]、SHARP定位算法[23]等。动态节点定位指网络中的部分或者全部节点处于移动状态的定位,包括锚节点移动待定位节点静止、锚节点静止待定位节点移动、锚节点和待定位节点均移动。常用算法有DLS算法[24]、MBAL算法[25]、Constrained 3D算法[26]、MCL定位算法[20]、CDL算法[27]、3D-ADAL算法[28]等。

(3)集中式定位和分布式定位

集中式定位是指将需要的WSN节点信息传送到某个中心节点进行定位计算。典型的算法有Mapgrowing定位算法[29]、凸规划定位算法[18]、SHARP定位算法[23]等。分布式定位是指依赖节点间的信息交换和协调,由节点自行计算的定位方式。典型的算法有DV-Hop[15]、DV-distance定位算法[30]、APIT定位算法[17]、3D-ADAL算法[28]等。

(4)绝对定位和相对定位

绝对定位的定位结果是一个标准的坐标位置,如经纬度等。目前大部分WSN系统采用这种表示方式。相对定位通常以网络中部分节点为参考,建立整个网络的相对坐标系统。典型的相对定位算法有Cooperative ranging定位算法[13]、SPA定位算法[31]、SHARP定位算法[23]等。有些算法,例如MDS-MAP算法[19],可以根据网络配置情况实现绝对定位或相对定位。

(5)细粒度定位和粗粒度定位

根据接收信号强度、时间、方向和信号模式匹配等完成定位的称为细粒度定位,可细分为基于距离的和基于方向性测量两类,例如Active Badge[5]、AHLos定位算法[12]、Euclidean定位算法[15]等。根据节点接近度等完成的定位称为粗粒度定位,例如DV-Hop定位算法[15]、SHARP定位算法[23]、Amorphous定位算法[22]等。

(6)一次计算定位和循环求精定位

一次计算定位是指根据接收的信息直接计算节点位置坐标,例如质心算法[16]、APIT定位算法[17]、凸规划定位算法[18]、Amorphous定位算法[22]等。循环求精定位算法是在起始阶段得到节点位置的粗略估计,在循环阶段每个节点向其邻居节点广播它的位置估计,并根据从邻居节点接收的位置信息和节点间的测距结果重新计算自身位置,直至两次计算得到的位置估值之差小于一定的域值。典型的算法有N-hop Multilateration Primitive定位算法[32]、Cooperative ranging定位算法[13]、Two-Phase positioning定位算法[14]等。

2　WSN静态节点定位常用算法

本文将现有的WSN静态节点定位算法按照节点分布特点分为基于测距的静态节点定位算法和无需测距的静态节点定位算法。

2.1 基于测距的静态节点定位算法

2. 1. 1 基于RSS的定位算法

基于信号接收强度(Received Signal Strength,RSS)的节点定位[9]原理是将锚节点到未知节点间的信号强度衰减转化为信号的传播距离,然后利用经验模型或理论模型将信号的传播损耗转化为距离,从而计算出未知节点的位置。

该方法利用对接收无线信号强度的判断即可比较准确地估算出收发节点之间的距离,算法复杂度较低,对锚节点密度要求不高,是一种低功率、廉价的测距技术,适用于大规模的无线传感器网络的节点定位。由于电磁波传输路径中存在的多径、绕射、障碍物干扰等因素的影响,都会对无线信号的传输模型产生不可避免的影响,一旦传输模型发生改变,那么按照模型计算无线信号的传输距离同信号强度衰减之间的关系将产生不可忽略的误差,其测距误差可达±50%[33]。

2. 1. 2 基于TOA的定位算法

基于到达时间(Time of Arrival,TOA)的定位算法[10,11]是指当信号传播的速度已知时,根据其传播时间来计算两个节点间的距离,当未知节点获得与多个锚节点间的距离后,利用三边测量法或其他方法计算未知节点的坐标。

该方法需要节点间必须严格保证时间同步,而通常节点间距离较小,电信号又是以光速传播,这都为节点间信号到达时间的精确测量增加了难度。

2. 1. 3 基于TDOA的定位算法

基于到达时间差(Time Difference of Arrival,TDOA)的定位算法[10,11]是指锚节点同时发射两路速度不同的信号,例如传播速度为C1的无线电信号和传播速度为C2的超声波信号,当未知节点接收到两路信号后,根据它们的到达时间差Δt,计算两节点间的距离d,然后计算节点的位置坐标。

由于该算法测量的是节点间的时间差,与TOA相比,不需要严格的时间同步,因而相对容易实现,并且定位精度也更高。但是该算法受限于超声波传播距离有限(通常情况下WSN安装的超声波传感器传播距离均在10米以内,因而网络需要密集部署)和非视距传输对超声波信号传播的影响,同时还要求传感器节点具备感知两种不同信号的能力。

2. 1. 4 基于AOA的定位算法

基于到达角度(Angle of Arrival,AOA)的定位算法[10]是利用接收节点上的阵列天线来感知发射信号的到达方向,计算锚节点与未知节点间的角度,然后利用交汇法计算节点的位置坐标。该方法不需要严格的时间同步,且能额外提供节点的方位信息,但是易受环境影响,且节点需要配有阵列天线,硬件系统复杂,由于受到硬件尺寸及功耗的限制,不适用于大规模无线传感器网络。

另外,AOA信息还可以与TOA、TDOA信息一起使用成为混合定位法。采用混合定位法可以实现更高的精确度,减小误差,或者可以降低对某一种测量参数数量的需求[34-36]。

2. 1. 5 AHLos定位算法

2001年,加州大学洛杉矶分校的Andreas Savvides等人提出了AHLos定位算法[12],该算法利用测距方法测量每个节点与其邻居锚节点间的距离,根据邻居锚节点的分布情况,利用相应的原子多边算法AM(Atomic Multilateration)、协作多边算法CM(Collaborative Multilateration)和迭代多边算法IM(Iterative Multilateration)计算未知节点的坐标,该算法的核心是迭代思想,将已定位的节点“升级”为锚节点投入新一轮的运算,AHLos算法的迭代思想在获得锚节点带来的高计算精度的同时,在一定程度上缓解了锚节点密度低时的节点定位问题,但是将已定位的未知节点直接升级为锚节点可能会造成误差累积,降低整体的定位精度。

文献[37]将AHLos定位算法扩展到三维空间,提出了ILAH-3D算法,通过采用加权最小二乘法和加入定位节点升级锚节点的验证条件来降低累积误差,并根据三维空间中节点的各种位置关系,给出约束协作算法的执行条件,然后结合升级的锚节点再进行新一轮的定位算法。

2. 1. 6 N-hopMultilateration Primitive定位算法

2002年,Andreas Savvides等人在AHLos算法的基础上提出了N-hop Multilateration Primitive定位算法[32],该算法对AHLos算法的协作多边算法CM进行了完善,给出了判定节点是否可参与协作多边计算的充分条件,并使用卡尔曼滤波技术循环定位求精,减小了误差积累。

首先根据判定条件,在网络中生成多个由未知节点和信标节点组成的超限制条件或限制条件完整的构形,称为协作子树。每个协作子树可相应生成一组包括n个未知变量的至少n个非线性方程式,并且每个未知变量有唯一解,未被协作子树包含的节点在整个算法的后阶段处理;其次,根据信标节点位置、节点间距离和网络连通性信息对每个节点的位置进行粗略估算,结果作为下一阶段的输入;最后,根据预设的定位精度,使用卡尔曼滤波技术在每个协作子树范围内对上一阶段的结果用分布式或集中式计算模式进行循环求精。该方法突破了至少三个邻居信标节点才能定位的限制,提高了算法覆盖度,缺点是循环求精的循环次数无法预知,锚节点必须部署在网络边缘。

2. 1. 7 DV-distance定位算法

文献[15]和[30]提出了一种DV-distance定位算法,相邻节点使用RSS测量节点间距离,然后利用相似于距离矢量路由方法传播与锚节点的累计距离。当未知节点获得与三个或更多锚节点距离信息后使用三边测量法进行定位。该算法只适用于各向同性的密集网络。实验表明,在网络平均连通度为9,锚节点比例为10%,测距误差小于10%的情况下,定位精度为20%,但是随着测距误差的增大,定位性能下降明显。

2. 1. 8 Euclidean和DV-coordinate定位算法

Euclidean定位算法[15]和[30]给出了计算与锚节点相隔两跳的未知节点位置的方法,该算法假设节点拥有使用RSS测量节点间距离的能力,锚节点首先广播出一个包含自身ID和位置的信标信号,并将该信号的TTL域设置为2,即该信标仅能传送2跳。当一个未知节点可从2个已知相互距离且与锚节点直接相邻的节点处接收到该信号,它就可以计算出自身与该锚节点的距离。当未知节点获得与3个或更多锚节点距离后再定位自身。该算法把用于定位的信标节点由1跳扩展到2跳,提高了算法的覆盖度,降低了对锚节点密度要求,通信开销适当。

在DV-coordinate定位算法[30]中,每个节点首先利用Euclidean定位算法计算两跳邻居节点的距离,以自身位置作为原点建立局部坐标系统。然后相邻节点交换信息,假如一个节点从邻居节点那里接收到锚节点的信息并将其转化为自身坐标系统中的坐标后,便可以估计自身的位置。

Euclidean和DV-coordinate定位算法虽然不受网络各向异性的影响,但对测距精度、节点密度和锚节点密度非常敏感。实验表明,在网络平均连通度为9,锚节点比例为20%,测距误差小于10%的情况下,Euclidean和DV-coordinate的平均定位误差分别为20%和80%。

2. 1. 9 DV-Bearing和DV-Radial定位算法

DV-Bearing和DV-Radial定位算法[30]提出了以逐跳方式跨越两跳甚至三跳来计算与锚节点的相对角度,最后使用三角测量法定位。两者的区别在于,DV-Bearing算法要求每个锚节点和未知节点都安装有指南针,从而获得绝对角度信息。实验表明,DV-Bearing和DV-Radial定位算法在网络平均连通度为10. 5,锚节点比例为20%,AOA测量误差小于5°的情况下,90%以上的节点可以实现定位,定位精度分别为40%和25%。

2. 1. 10 Cooperative ranging和Two-Phase定位算法

Cooperative ranging定位算法[13]和Two-Phase定位算法[14]都分为启始和循环求精两个阶段。起始阶段着重于获得节点位置的粗略估算。而在循环求精阶段,每一次循环开始时每个节点向其邻居节点广播它的位置估算,并根据从邻居节点接收的位置信息和节点间测距结果,重新执行三边测量,计算自身位置,直至位置更新的变化可接受时循环停止。

Cooperative ranging算法的起始阶段又称为TERRAIN (triangulation via extended range and redundant association of intermediate nodes)。首先在所有信标节点上,根据节点间测距结果使用ABC算法(assumption based coordinates algorithm)建立局部坐标系统,然后将结果(以这个信标节点为原点的局部网络拓扑)传播到整个网络。未知节点根据它所获得的网络拓扑确定其与信标节点的距离,使用三边测量定位自身,然后进入循环求精阶段。

与Cooperative ranging算法不同,为了克服信标节点稀疏问题,Two-Phase定位算法在起始阶段使用Hop-TERRAIN算法获得节点位置的粗略估算。在循环求精阶段,使用加权最小二乘法进行三边测量以计算新位置。

实验表明,Cooperative ranging算法定位精度可达到5%(测距误差为5%,而单纯使用TERRAIN算法得到的定位精度约为39%),而Two-Phase算法在锚节点比例为5%,测距误差为5%,网络连通度约为7的条件下,定位精度约为33%[13,14]。

2. 1. 11 Map-growing定位算法

文献[29]提出了Map-growing算法,基本思想是通过递归算法,由三个相邻的节点形成局部初始坐标系并向外广播坐标信息,与此三节点相邻且收集足够信息的节点根据三边测量法计算自身坐标;初始坐标系以此方式扩展,如此反复直至所有节点被定位。该算法实现简单,只需首先确定三个点建立相对坐标系就可实现大部分节点的定位。由于不断升级新的未知节点参与到定位中,该算法对拓扑结构适应性很强,节点覆盖率高。但是该算法使用完成定位的节点协助定位会造成误差累积,一旦测距误差比较大时,距离三个选取的参考点较远的边缘区域节点计算得到的坐标误差就会很大。

2. 1. 12 COLA算法

Chia-Yen Shih等人提出一种基于RSS的三维无线传感器网络三边测量定位方法COLA (Complexity-reached 3D trilateration localization approach)[38],该算法通过将三维三边测量转化为二维三边测量来降低网络复杂度,利用装备有两个收发器和两个高度不同的天线超级锚节点,探测两个仅高度不同的位置信号,该方法在低计算开销的条件下取得了较好的定位效果,但仅适用于室内无线传感器网络。

2. 1. 13 SPA定位算法

Srdjan Capkun等学者针对无基础设施的移动无线网络,提出了一种SPA (Self - Positioning Algorithm)相对定位算法[31]。它选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考群(location reference group),并在其中选择连通度最大的一个节点作为坐标系统的原点。首先根据节点间的测距结果在各个节点建立局部坐标系统,通过节点间的信息交换与协调,以参考节点为基准通过坐标变换建立全局坐标系统。因为所有节点都需要参与坐标的建立和变化运算,因此该方法的通信开销和计算量较大。

2. 1. 14 DGFSL-3D定位算法

马永波等人提出了一种三维空间中基于动态分组筛选的安全定位算法DGFSL-3D (Dynamic Group Filtering Security Localization Algorithm)[39],所有传感器节点均装备全向天线,具有相同的发射半径,节点的物理坐标不变,考虑到信标节点可能失效或者信标节点被捕获后发布虚假定位信息等问题,该算法对信标节点进行安全性检测,将部分节点判定为恶意定位节点,从自己的信标节点列表中剔除,最后进行坐标修正实现精确定位。该算法能够有效地剔除定位干扰节点,能够显著地降低恶意定位节点对网络节点定位过程的负面影响,算法具有较高的定位精度。

2.2 无需测距的静态节点定位算法

2. 2. 1 Centroid算法

2000年,南加州大学的Nirupama Bulusu等学者提出了质心算法(Centroid Algorithm)[16],该算法是一种仅基于网络连通性的室外定位算法,以所有在其通信范围内的锚节点的几何质心作为未知节点的估计位置,不需要锚节点和未知节点之间精确的距离,算法实现比较简单,适用于定位精度要求不高的场合,多边形的面积越小,估计误差也就越小,因此该算法在较高的锚节点密度下方能实现较精确的定位,同时,该算法在定位过程中并没有体现出各连通锚节点对未知节点定位影响力的大小。

针对质心法的不足,国内外学者提出了多种改进的质心算法,例如基于锚节点功率调节的加权质心定位算法[40],基于跳数的加权质心定位算法[41],基于最小包围多边形定位(SEPL)算法[42],文献[43]将质心算法扩展到三维场景,提出了3D-Centroid算法。

2. 2. 2 APIT定位算法

2003年弗吉尼亚大学的Tian He等人提出了APIT (Approximate Point-In-Triangulation Test)定位算法[17],该算法的理论基础是Perfect Point-In-Triangulation Test Theory (PIT):假如存在一个方向,沿着这个方向p点会同时远离或接近A、B、C,那么p位于△ABC外;否则p就位于△ABC内。APIT利用未知节点的临近节点代替其移动进行计算,通过收集所有邻居锚节点的信息,并测试未知节点是否位于不同的三个锚节点组成的三角形内,计算所有包含该未知节点的三角形的交集,即是节点所在的区域,取交集的质心作为未知节点位置,与基本的质心算法相比,有着更小的有效区域,因此在一定程度上提高了定位的精度。不过算法对网络的连通性要求较高,且定位覆盖率不高,如果要达到高的性能,就要求锚节点密度和通信范围增大。实验表明,APIT测试错误概率相对较小(当相邻节点为6个或者6个以上时,误判不超过14%);平均定位误差小于节点无线电射程的40%。

文献[44]基于APIT的思想,提出了环形区域叠加定位算法ROCRSSI (Ring Overlapping based on Comparison of Received Signal Strength Indicator)算法,该算法以APIT算法为基础,网络中每个未知节点通过邻居锚节点形成的一系列环形,然后将所得的环相互叠加,取叠加区域的质心作为其估计位置,该算法在较低锚节点密度的情况下获得较为精确的定位,但锚节点必须提前配置,预先知道自己的位置信息,且需要具有较大的传播功率。

文献[45]采用ROCRSSI算法的思想,将其拓展到三维空间定位,提出了基于球壳定位的APIS (Approximate Point-In-Sphere)算法,实现了立体空间中传感器网络的节点定位。该算法基于划分空间为球壳,未知节点寻找包含自己的最薄一层球壳,取球壳交集进行定位。该算法的优点是仅需锚节点广播信标信息,未知节点无需直接通信,减少了通信开销,同时无需测量节点间的实际距离;缺点是是由于采用球壳分割的方法,计算开销和通信开销大,节点成本高,并且定位覆盖率受锚节点数量变化的影响较大。

2. 2. 3 Convex Optimization定位算法

2001年,加州大学伯克利分校的Doherty等学者提出了凸规划(Convex Optimization)定位算法[18],该算法将整个网络中点到点的通信模型转化为节点位置的一组几何约束,将整个网络视为一个凸集,从而将节点定位问题转化为凸约束优化问题,利用未知节点与锚节点的连通性计算未知节点的可能区域,进而估计节点位置,该算法是一种集中式定位算法,当信标节点比例为10%的时候,其定位误差约等于节点的无线射程,误差较大,且锚节点必须部署在网络边缘,否则,节点位置估算会向网络中心偏移。

2. 2. 4 Amorphous定位算法

2003年,美国麻省理工的Radhika Nagpal等学者提出了Amorphous定位算法[22],该算法通过估算待测节点与锚节点之间的平均梯度值,根据网络中节点的通信半径,未知节点到每个锚节点的跳段距离,并使用三边测量法或最大似然估计法估算自身位置,Amorphous算法对节点的运算能力要求较小,但是需要预先设定网络的密度,并且随着未知节点与锚节点之间跳数的增加,估算距离与真实距离的误差也随之增大。

2. 2. 5 DV-Hop定位算法

2003年,美国路特葛斯大学的Dragos Niculescu等人利用距离矢量路由和GPS定位的原理提出了DV-Hop定位算法[15]。该算法首先使用典型的距离矢量路由协议使网络中所有节点获得到锚节点的跳数,锚节点计算网络平均每跳距离,并把此值广播至整个网络,节点根据到锚节点的跳数和平均每跳距离计算到锚节点的距离,当未知节点获得与三个或更多锚节点距离时,用三边测量法进行定位。DVHop算法属于分布式算法,实现简单,通信开销小,但是随着跳数的增加,估计距离误差会增大,通信开销大。实验表明,DV-Hop算法在网络平均连通度为10、锚节点比例为10%的各向同性网络中定位精度约为33%。

文献[46]通过考虑通信范围和跳段距离的关系对DV-Hop算法进行了限制和修正,提高了定位精度。

文献[47]提出了基于自适应惯性权重的优化定位算法,在DV-Hop算法的基础上,用改进的粒子群算法做后期优化,根据每次迭代后粒子位置与全局最优位置的距离,对粒子的惯性权重进行动态调整,使其具有动态自适应性,并且利用进化度作为搜索终止条件,加快算法的收敛速度,仿真表明该算法相对于DV-Hop算法,可以减低平均定位误差,提高节点的定位精度。

李辉等人提出基于移动代理的WSN三维MA3D-Hop定位算法[48],对DV-Hop算法进行改进,并推广到三维空间,建立了空间向量模型估计未知节点位置,并对初始估计位置进行迭代求精,来减少定位误差。

2. 2. 6 MDS-MAP定位算法

2003年,密苏里哥伦比亚大学的Yi Shang等人将多维标度(multidimensional scaling,MDS)的数据分析方法应用于无线传感器网络节点定位,提出了MDS-MAP算法[19],该方法根据节点间的不同信息(例如与其它节点的距离)对节点进行定位,然后对距离矩阵进行奇异值分解得到节点初始坐标,再进行优化使这些坐标满足其间的距离关系。首先,从全局角度生成网络拓扑连通图,并为图中每条边赋予距离值,当节点具有测距能力时,该值就是测距结果。当仅拥有连通性信息时,所有边赋值为1。然后使用最短路径算法生成节点间距矩阵;然后,对节点间距矩阵应用MDS技术,生成整个网络的二维或三维相对坐标系统;当拥有足够的锚节点时(二维最少3个,三维最少4个),将相对坐标系统转化为绝对坐标系统。该算法可在基于测距或非测距条件下运行,并可根据情况实现相对定位和绝对定位。该算法采用集中式计算的模式,不需要锚节点或者仅需较少的几个锚节点,但是算法比较复杂,需要采用奇异值分解的方法进行计算之间的平均梯度值。实验显示,当网络的节点密度减小时,定位误差增大,并且无法定位的节点数量增加;而当网络连通度达到12. 2时,几乎全部节点都可实现定位;在拥有200个节点(其中4个信标节点),平均连通度为12. 1的网络中,在range-free条件下,定位误差约为30%;而在range-based条件下,定位误差为16%(测距误差为5%)[19]。

针对MDS-MAP矩阵维数大,计算复杂的缺点,文献[49]提出了基于MDS的局部定位算法,设定跳数范围,网络中的每个节点在该跳数范围内进行局部定位,然后融合局部定位图得到全局定位图。局部定位算法不需要估计相距较远节点的距离,从而提高了定位精度,而且适合于有大量节点的传感器网络。此外,在不同的节点上同时进行局部定位实现分布式计算。

文献[50]提出了基于多维定标的无线传感器网络三维定位算法3D-MDS,将网络在逻辑上划分为许多簇,在每个簇内计算局部坐标,然后将节点的位置信息回送,在后台利用一种集中式的迭代优化算法对初始坐标求精,该算法降低定位误差、计算复杂度和通信开销,适用于大规模无线传感器网络定位问题。

文献[51]在MDS-MAP定位算法的基础上,提出了Isomap定位算法,利用测地线距离代替欧氏距离实现节点定位,提高了定位精度,但是邻近参数K的选择较为复杂。

2. 2. 7 SHARP定位算法

文献[23]提出一种SHARP (Simple Hybrid Absolute Relative Positioning)定位方法。这种方法先在传感器网络节点中利用随机法或者外围结点法选择一定数量的节点,将这些节点作为参考节点但不要求知道其坐标。利用相对定位方法MDS确定一个相对坐标系,以及它们在这个坐标系中的坐标,最后网络中的其它节点利用DV-distance定位方法确定自身在上述坐标系中的坐标。

SHARP结合了MDS和DV-distance算法的优点:用MDS确定参考节点相对坐标精度较高,并且避免了计算所有节点组成的距离矩阵;DV-distance算法易于实现。经实验验证,在节点密度高连通性好的传感器网络中,SHARP算法的定位精度要高于DV-distance和MDS。

2. 2. 8 HiRLoc安全定位算法

2006年,L. Lazos等学者提出HiRLoc安全定位算法[52],该算法基于区域覆盖逼近,假设未知节点和锚节点配有最大发射功率的全方向天线,锚节点通过改变发射功率和定向天线的方向,重新广播锚节点信息,减小多个覆盖区域的重叠面积来确定节点位置,该算法主要侧重于安全方面,可以抵御漏洞攻击、Sybil攻击等,对系统硬件需求较大。

2. 2. 9 3D-DRL算法

文献[53]提出了一种基于网格划分思想的非测距三维定位(3D-DRL)算法,锚节点广播包括ID、位置、发射功率级别、传播范围等信标信息,未知节点对接收到的信标信息进行存储,记录能够监听到的锚节点数量,用以判断是否有足够的信标信息进行定位。然后以所有能监听到的锚节点的质心为中心将仿真区域划分为立体网格,若一个锚节点判定某个小格子在其有效覆盖范围内,就会对该格子投一票,投票结束后,将得票值最高的网格作为未知节点的最大可能定位区域,选取该区域的质心作为未知节点的估计位置。3D-DRL算法[54-55]无需未知节点间相互通信,具有较小的通信开销,不依赖于锚节点比例,且对网络拓扑结构具有鲁棒性。定位区域网格化表示与投票机制减少了无线信号传输不规则性对算法定位精度的不利影响,但仅限于网络中节点位置固定的情况。

2.3 WSN节点定位常用算法特点比较

对于上述代表性的WSN节点定位算法,其特点归纳如表1所示。

表1　常用静态节点定位算法的特点比较

3　总 结

本文主要介绍了无线传感器网络静态节点定位算法的基本原理和国内外研究现状,从基于测距的静态节点定位算法和无需测距的静态节点定位算法两个方面分类讨论了常用的节点定位及其改进算法,通过上面的分析总结可以看出,目前研究的各类定位算法在网络结构、计算量、定位精度、应用范围等方面存在较大差别,也取得了丰硕的研究成果,但仍有一些问题有待解决。

1)大部分定位算法均是在理想条件下进行分析和验证,但是无线传感器网络往往部署在山地、丛林或者水下等复杂环境中,实际环境中的很多因素,例如无线电传播路径损耗、地形遮挡物、无线信号传输不规则性、大气折射误差等因素在算法中很少被考虑,算法缺少在实际应用环境中的测试效果。

2)定位精度是目前大部分定位算法首先考虑的性能指标,算法复杂度、硬件成本、系统的能耗等参数考虑不多,这也在一定程度上限制了其应用范围。

3)无线传感器网络定位技术已经逐步从二维空间向三维空间扩展,从静态节点定位向动态节点定位扩展,这方面的研究有待加强。

因此,研究低成本、高能效、易于系统化的节点定位技术,研究能够有效延长网络生命周期的低复杂度、低开销、低能耗的节点定位技术,研究考虑到无线电传播路径损耗、地形遮挡物、无线信号传输不规则性、大气折射误差等因素的贴近现实场景的定位技术,研究高精度的动态节点定位及复杂三维空间中的节点定位技术,将是未来研究的技术重点。

参 考 文 献

[1] LOWELL J R. Military application of localization,tracking,and targeting[J]. IEEE Wireless Communications,2011,18(2):60-65.

[2] LIJianpo,ZHONG Xinxin,Lu I-Tai. Three-dimensional node localization algorithm for WSN based on differential RSS irregular transmission model[J]. Journal of Communications,2014,9(5):391-397.

[3] CHAO Long,Meng Shuai. Wireless sensor networks:traffic information providers for intelligent transportation system[C]. 18th International Conference on Geoinformatics,Beijing,2010,6:1-5.

[4] LIJianpo,JIANG Xue,LU I-Tai. Energy balance routing algorithm based on virtual MIMO scheme for wireless sensor networks[J]. Journal of Sensors,2014 (2014),1-7.

[5] HARTER A,HOPPER A. A distributed location system for the active office[J]. IEEE Network,1994,8(1):62-70.

[6] THOMAS F,ROS L. Revisitingtrilateration for robot localization[J]. IEEE Transactions on Robotics,2005,21(1):93-101.

[7] YORK G,PACK D. Comparative study on time-varying target localization methods using multiple unmanned aerial vehicles:Kalman estimation and triangulation techniques[C]. IEEE International Conference on Networking,Sensing and Control,Tucson,2005,3:305-310.

[8] HOWARD A,MATARIC M J,SUKHATME G S. Localization for mobile robot teams using maximum likelihood estimation[C]. IEEE/ RSJ International Conference on Intelligent Robots and Systems,Algarve,2002,10:434-439.

[9] ABID M A,CHERKAOUI S. 3D compressive sensing for nodes localization in WNs based on RSS [C]. IEEE International Conference on Communications,Beijing,2012,6:5195- 5199.

[10] KAUNE R. Accuracy studies for TDOA and TOA localization[C]. 15th International Conference on Information Fusion,Singapore,2012,7: 408-415.

[11] HARA S,ANZAI D,YABU T. A perturbation analysis on the performance of TOA and TDOA localization in mixed LOS/ NLOS environments [J]. IEEE Transaction on Communications,2013,61(2):679-689.

[12] SAVVIDES A,HAN C,STRIVASTAVA M B. Dynamic fine - grained localization in Ad - Hoc networks of sensors [ C]. 7th Annual International Conference on Mobile Computing and Networking,Rome,2001,7:166-179.

[13] SAVARESE C,RAVAEY J M,BEUTEL J. Location in distributed ad-hoc wireless sensor networks[C]. IEEE International Conference on A-coustics,Speech,and Signal Processing,Salt Lake City,2001,5:2037-2040.

[14] SAVARESE C,RAVAEY J M,LANGENDOEN K. Robust positioning algorithms for distributed ad-hoc wireless sensor network[C]. Proceedings of the USENIX Annual Technical Conference,California,2002,6:317-327.

[15] NICULESCU D,NATH B. Ad Hoc positioning system (APS)[C]. IEEE Global Telecommunications Conference,San Antonio,2001,11: 2926-2931.

[16] BULUSU N,HEIDEMANN J,ESTRIN D. GPS-less low-cost outdoor localization for very small devices[J]. IEEE Personal Communications, 2000,7(5):28-34.

[17] HETian,HUANG Chengdu,BLUM B M,et al. Range-free localization schemes for large scale sensor networks [C].9th Annual International Conference on Mobile Computing and Networking,San Diego,2003,9:81- 95.

[18] DOHERTY L,PISTER K S,GHAOUI L E. Convex position estimation in wireless sensor networks[C].20th Annual Joint Conference of the IEEE Computer and Communications Societies,Anchorage,2001,4:1655-1663.

[19] SHANG Yi,RUML W,ZHANG Ying,et al. Localization from mere connectivity[C]. 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing,New York,2003,6:201-212.

[20]李建坡,时明,谢岩,等.一种基于模糊理论的蒙特卡洛移动节点定位算法[J].计算机应用与软件,2013,30(12):147-150.

[21]李建坡,时明,钟鑫鑫.自适应蒙特卡罗无线传感器网络移动节点定位算法[J].吉林大学学报(工学版),2014,44(4):1191-1196.

[22] NAGOAL R,SHROBE H,BACHRACH J. Organizing a global coordinate system from local information an Ad hoc sensor network [C].2nd International Workshop on Information Processing in Sensor Networks,Palo Alto,2003,4:333-348.

[23] AHMED AA,SHI Hongchi,SHANG Yi. SHARP:a new approach to relative localization in wireless sensor networks[C]. 25th International Conference on Distributed Computing System Workshops,Columbus,2005,6:892-898.

[24] CHEN Xun,HAN Peng,HE Qiusheng. A viable localization scheme for dynamic wireless sensor networks[C]. First International Multi-Symposiums on Computer and Computational Science,Hangzhou,2006,6:587-593.

[25] KIM K,LEE W. MBAL:a mobile beacon-assisted localization scheme for wireless sensor networks[C]. 16th International Conference on Computer Communications and Networks,Honolulu,2007,8:57-62.

[26] LIANG Jianlin,SHAO Jun,XU Ying,et al. Sensor network localization in constrained 3-D spaces[C]. IEEE International Conference on Mechatronics and Automation,Zhengzhou,2006,6:49-54.

[27] CHANG T C,WANGKuochen,HSIEH Y L,et al. Color-theory-based dynamic localization in mobile wireless sensor networks[C].1st Workshop on Wireless Ad Hoc Sensor Networks,London,2005,5:73-78.

[28] GUERRERO E,ALVAREZ J,RIVERO L.3D-ADAL:A three-dimensional distributed range-free localization algorithm for wireless sensor networks based on unmanned aerial vehicles [C].5th International Conference on Digital Information Management,Thunder Bay,2010,7: 332-338.

[29] LI Xiaoli,SHI Hongchi,SHANG Yi. A map-growing localization algorithm for ad-hoc wireless sensor networks[C].10th International Conference on Parallel and Distributed System,California,2004,7:395-402.

[30] NICULESCU D,NATH B. DV based positioning in Ad Hoc networks[J]. Journal of Telecommunication Systems,2003,22(1):267-280.

[31] CAPKUN S,HAMDI M,HUBAUX J P. GPS-free positioning in mobile ad-hoc networks[C].34th Annual Hawaii International Conference on System Sciences,Maui,2001,1:1-10.

[32] SAVVIDES A,PARK H,STRIVASTAVA M. The bits and flops of the N-hopmultilateration primitive for node localization problems[C].1stACM International Workshop on Wireless Sensor Networks and Applications,New York,2002,112-121.

[33] YOKOO K,NISHIDOI T,URABE H. RSS-based localization considering topographical feature for pasturing [C].10th Workshop on Positioning Navigation and Communication,Dresden,2013,3:1-5.

[34] BEN-Shimol Y,BLAUNSTEIN N. Localization and positioning of any subscriber in indoor environments on the basis of analysis of joint AOA -TOA signal distribution[C]. IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communications,Torino,2011,9: 1420-1423.

[35] LIU Chongfeng,YANG Jie,WANG Fengshuai,et al. Joint TDOA and AOA location algorithm[J]. Journal of Systems Engineering and Electronics,2013,24(2):183-188.

[36] MIKHALEV A,ORMONDROYD R. Passive emitter geolocation using agent-based data fusion of AOA,TDOA and FDOA measurements [C].10th International Conference on Information Fusion,Quebec,2007,7:1-6.

[37]祁荣宾,李思瑾,马天义.基于迭代的无线传感器网络三维定位算法研究[J].传感技术学报,2012,25(5):644-650.

[38] SHIH C Y,MARRON P J. COLA:complexity reduced trilateration approach for 3D localization in wireless sensor networks[C].4th International Conference on Sensor Technologies and Applications,Venice,2010,7:24-32.

[39]马永波.无线传感器网络精确动态定位及其安全性问题研究[D].吉林:吉林大学,2010.

[40]吴磊,侯忠伟,许登元.无线传感器网络中基于锚节点功率调节的加权质心定位算法[J].微电子学与计算机,2012,29(10):177 -180.

[41]孟祥衷,宋保业.无线传感器网络中的HWC定位算法[J].计算机工程,2009,35(7):104-106.

[42]张爱清,叶新荣,胡海峰.无线传感器网络质心定位新算法及性能分析[J].计算机应用,2012,32(9):2429-2431,2435.

[43]王丹.三维无线传感器网络节点自定位算法研究[D].成都:西南交通大学,2007.

[44] LIU Chong,WUKui,HE Tian. Sensor localization with ring overlapping based on comparison of received signal strength indicator[C]. IEEE International Conference on Mobile Ad-hoc and Sensor Systems,Fort Lauderdale,2004,10:516-518.

[45]吕良彬,曹阳,高洵.基于球壳交集的传感器网络三维定位算法[J].北京邮电大学学报,2006,29(S1):48-51.

[46] JIWeiwei,LIU Zhong. An Improvement of DV-Hop Algorithm in Wireless Sensor Networks[C]. International Conference on Wireless Communications,Networking and Mobile Computing,Wuhan,2006,9:1-4.

[47]季必晔,顾燕.无线传感器网络节点自适应惯性权重定位算法[J].科学技术与工程,2012,12(27):6967-6973.

[48]李辉.无线传感器网络节点定位技术的研究[D].武汉:武汉理工大学,2010.

[49] SHANG Yi,RUML W. Improved MDS-based localization[C].23rd Annual Joint Conference of the IEEE Computer and Communications Societies,Hong Kong,2004,3:2640-2651.

[50]张荣磊,刘琳岚,舒坚.基于多维定标的无线传感器网络三维定位算法[J].计算机应用研究,2009,26(8):3100-3104.

[51] WANG Chenqiu,CHEN Jiming,SUN Youxian,et al. Wireless sensor networks localization with isomap[C]. IEEE International Conference on Communications,Dresden,2009,6:1-5.

[52] LAZOS L,POOVENDRAN R. HiRLoc:High-resolution robust localization for wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications,2006,24(2):233-246.

[53]王德华.无线传感器网络非测距三维定位算法的研究[D].济南:山东大学,2010.

[54]陈杰香,张恒,赵丽萍.基于蒙特卡罗方法的边界检测不确定度估计[J].东北电力大学学报,2013,32(3):75-78.

[55]李建坡,朱绪宁,隋吉生.基于ZigBee技术的无线指纹考勤系统[J].东北电力大学学报:自然科学版,2009,29(6):33-37.

Review of Statical Node Localization Algorithm for Wireless Sensor Networks

LI Jian-po1,ZHONG Xin-xin1,XU Chun2

(1. School of Information Engineering,Northeast Dianli University,Jilin Jilin 132012;2. Station 2021,State Administration of Press,Publication,Radio,Film and Television,Qiqihaer Hei Longjiang 161000)

Abstract:The principle of node localization,the latest development of related algorithms and the evaluation standards of Wireless Sensor Network (WSN)were introduced in this paper. Furthermore,based on the detailed performance analysis and comparison of typical localization algorithms (range-based static node,rangefree static node),the problems of current researches and further directions were pointed out.

Key words:Wireless sensor networks;Statical node localization;Review

作者简介:李建坡(1980-),男,河北省定州市人,东北电力大学信息工程学院副教授,博士,主要研究方向:嵌入式系统、智能信息处理.

基金项目:国家留学基金项目([2012]3043);吉林省教育厅科学技术研究项目([2009]101);东北电力大学青年学术骨干科研促进计划项目

收稿日期:2014-10-15

文章编号:1005-2992(2015)02-0073-10

文献标识码:A

中图分类号:TP393