《4125370447第6章wsn定位技术》由会员分享，可在线阅读，更多相关《4125370447第6章wsn定位技术（58页珍藏版）》请在金锄头文库上搜索。
1、第6章 WSN定位技术6.1 定位技术简介6.1.1 基本概念和评价指标 1传感器节点定位的基本概念WSN的定位问题一般指对于一组未知位置坐标的网络节点，依靠有限的位置已知的锚节点，通过测量未知节点至其余节点的距离或跳数，或者通过估计节点可能处于的区域范围，结合节点间交换的信息和锚节点的已知位置，来确定每个节点的位置。在WSN节点定位技术中，根据节点是否已知自身的位置，把传感器节点分为信标节点（beacon node）或锚点（anchor）和未知节点（unknown node）。第6章 WSN定位技术信标节点在网络节点中所占的比例很小，可以通过携带GPS定位设备等手段获得自身的精确位置。信标节
2、点是未知节点定位的参考点。除了信标节点外，其他传感器节点就是未知节点，他们通过信标节点的位置信息来确定自身位置。如图6-1所示的传感器网络中，M代表信标节点，s代表未知节点。S节点通过与邻近M节点或已知得到信息的S节点之间的通信，根据一定的定位算法计算出自身的位置。图6-1WSN中信标节点和未知节点在WSN的各种应用中，监测到事件之后关心的一个重要问题就是该事件发生的位置。第6章 WSN定位技术全球定位系统GPS(global position system)是目前应用得最广泛最成熟的定位系统，通过卫星的授时和测距对用户节点进行定位，具有定位精度高、实时性好、抗干扰能力强等优点，但是GPS定位
3、适应于无遮挡的室外环境，用户节点通常能耗高体积大，成本也比较高，需要固定的基础设施等，这使得它不适用于低成本自组织的无线传感器网络。在机器人领域中，机器人节点的移动性和自组织等特性，使其定位技术与传感器网络的定位技术具有一定的相似性，但是机器人节点通常携带充足的能量供应和精确的测距设备，系统中机器人节点的数量很少，所以这些机器人定位算法也不适用于传感器网络。在传感器网络中，传感器节点能量有限、可靠性差、节点规模大且随机布放、无线模块的通信距离有限，对定位算法和定位技术提出了很高的要求。第6章 WSN定位技术2WSN定位算法特点在传感器网络中，传感器节点能量有限、可靠性差、节点数量规模大且随机布
4、放、无线模块的通信距离有限，对定位算法和定位技术提出了很高的要求。传感器网络的定位算法通常要求具备以下特点：(1)自组织性：传感器网络的节点随机分布，不能依靠全局的基础设施协助定位。(2)健壮性：传感器节点的硬件配置低、能量少、可靠性差、测量距离时会产生误差，算法必须具有良好的容错性。(3)能量高效：尽可能地减少算法中计算的复杂性，减少节点间的通信开销，以尽量延长网络的生存周期。通信开销是传感器网络的主要能量开销。(4)分布式计算：每个节点尽量计算自身位置，不能将所有信息传送到某个节点进行集中计算。第6章 WSN定位技术3传感器节点定位的基本术语（1）邻居节点（Neighbor Nodes）：
5、是指传感器节点通信半径内的所有其他节点，也就是说：在一个节点通信半径内，可以直接通信的所有其他点。（2）跳数（Hop Count）：是指两个节点之间间隔的跳段总数。（3）跳段距离（Hop Distance）：是指两个节点间隔的各跳段距离之和。（4）接收信号强度指示（Received Signal Strength Indicator，RSSI）：是指节点接收到无线信号的强度大小。（5）到达时间（Time of Arrival，TOA）：是指信号从一个节点传播到另一节点所需要的时间。第6章 WSN定位技术（6）到达时间差（Time Difference of Arrival，TDOA）：两种不同
6、传播速度的信号从一个节点传播到另一节点所需要的时间之差。（7）到达角度（Angle of Arrival，AOA）：是指节点接收到的信号相对于自身轴线的角度。（8）视线关系（Line of Sight，LOS）：是指两个节点间没有障碍物间隔，能够直接通信。（9）非视线关系（Non Line of Sight，NLOS）：是指两个节点之间存在障碍物。（10）基础设施（Infrastructure）：是指协助传感器节点定位的已知自身位置的固定设备（如卫星、基站等）。第6章 WSN定位技术4传感器节点定位的评价指标无线传感器网络定位算法的性能直接影响其可用性，如何评价它们是一个需要深入研究的问题。下
7、面定性地讨论几个常用的评价标准（1）定位精度。 （2）规模。（3）锚节点密度。（4）节点密度。（5）容错性和自适应性。（6）功耗。（7）代价上述7个性能指标不仅是评价WSN自身定位系统和算法的标准，也是其设计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需要完成。同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡，以选择和设计合适的定位技术。第6章 WSN定位技术6.1.2 定位算法的分类因功耗和成本因素以及粗精度定位对大多数应用已足够当定性误差小于传感器节点无线通信半径的40%时，定位误差对路由性能和目标追踪精确度的影响不会很大)，无需测距的定位方案备受关注。1基于测
8、距技术的定位和无需测距技术的定位根据定位算法是否需要通过物理测量来获得节点之间的距离(角度)信息，可以把定位算法分为基于测距的定位算法和无需测距的定位算法两类。前者是利用测量得到的距离或角度信息来进行位置计算，而后者一般是利用节点的连通性和多跳路由信息交换等方法来估计节点间的距离或角度，并完成位量估计。基于测距的定位算法总体上能取得较好的定位精度，但在硬件成本和功耗上受到一些限制。基于测距的定位机制使用各种算法来减小测距误差对定位的影响，包括多次测量，循环定位求精，这些都要产生大量计算和通信开销。所以，基于测距的定位机制虽然在定位精度上有可取之处，但并不适用于低功耗、低成本的应用领域。第6章
9、WSN定位技术 室内定位系统Cricket、AHLos（Ad-Hoc Localization System）算法、基于AOA的APS算法（Ad-hoc Positioning System）、RADAR算法、LCB算法（Localizable Collaborative Body）和DPE（Directed Position Estimation）算法等都是基于测距的定位算法；而质心算法（Centroid Algorithm）、DV-Hop（Distance Vector-Hop）算法、移动导标节点（Mobile Anchor Points，MAP）定位算法、HiRLoc算法、凸规划（Con
10、vex Optimization）算法和MDS-MAP算法等就是典型非基于测距的定位算法。第6章 WSN定位技术2基于导标节点的定位算法和非基于导标节点的定位算法根据定性算法是否假设网络中存在一定比例的导标节点，可以将定位算法分为基于导标节点的定位算法和非基于导标节点的定位算法两类。对于前者，各节点在定位过程结束后可以获得相对于某个全局坐标系的坐标，对于后者则只能产生相对的坐标，在需要和某全局坐标系保持一致的时候可以通过引入少数几个导标节点和进行坐际变换的方式来完成。基于导标节点的定位算法很多，例如质心算法、DV-Hop、AHLos、LCB和APIT（Approximate Point-In-
11、Triangulation Test）等；而ABC（Assumption Based Coordinates）和AFL（Anchor-Free Localization）是典型的非基于导标节点的定位算法。第6章 WSN定位技术3物理定位与符号定位定位系统可提供两种类型的定位结果：物理位置和符号位置。例如，某个节点位于经纬度，就是物理位置；而某个节点在建筑物的423号房间就是符号位置。一定条件下，物理定位和符号定位可以相互转换。与物理定位相比，符号定位更适于某些特定的应用场合，例如，在安装有无线烟火传感器网络的智能建筑物中，管理者更关心某个房间或区域是否有火警信号，而不是火警发生地的经纬度。大多
12、数定位系统和算法都提供物理定性服务，符号定位的典型系统和算法有Active Badge、微软的Easy Living等，MIT的Cricket定位系统则可根据配置实现两种不同形式的定位。第6章 WSN定位技术4递增式定位算法和并发式定位算法根据计算节点位置的先后顺序可以将定位算法分为递增式定位算法和并发式定位算法两类。递增式定位算法通常是从3-4个节点开始，然后根据未知节点与已经完成定位的节点之间的距离或角度等信息采用简单的三角法或局部最优策略逐步对未知节点进行位置估计。该类算法的主要不足是具有较大的误差累积。并发式定性算法则是节点以并行的方式同时开始计算位置。有些并发式算法采用迭代优化的方式
13、来减小误差。并发式定位算法能更好地避免局部最小和误差累积。大多数算法属于并发式的，像ABC算法则是递增式的。第6章 WSN定位技术5紧密耦合与松散耦合紧密耦合（Tightly Coupled）定位系统是指信标节点不仅被仔细地部署在固定的位置，并且通过有线介质连接到中心控制器；而松散型定位（Loosely Coupled）系统的节点采用无中心控制器的分布式无线协调方式。紧密耦合定位系统适用于室内环境，具有较高的精确性和实时性，时间同步和信标节点间协调问题容易解决。典型的紧密耦合定位系统包括AT&T的Active Bat系统和Active Badge、Hiball Tracker等。但这种部署策略
14、限制了系统的可扩展性，代价较大，无法应用于布线工作不可行的室外环境。近年来提出的许多定位系统和算法，如Cricket，AHLos等部属于松散耦合型解决方案。 第6章 WSN定位技术6集中式计算与分布式计算集中式计算（Centralized Computation）是指把所需信息传送到某个中心节点（例如一台服务器），并在那里进行节点定位计算的方式：分布式计算（Distributed Computation）指依赖节点间的信息文换和协调，由节点自行计算的定位方式。集中式汁算的优点在于从全局角度统筹规创，计算量和存储量几乎没有限制，可以获得相对精确的位置估算。它的缺点包括与中心节点位置较近的节点会因
15、为通信开销大而过早地消耗完电能，导致整个网络与中心节点信息交流的中断，无法实时定位等。集中式定性算法包括Convex Optionization、MDS-MAP等。N-hop multilateration primitive定位算法可以根据应用需求采用两种不同的计算模式。第6章 WSN定位技术无线传感器网线的分布式定位算法与计算机科学中其它己有的分布式体系结构有所不同，其分布式计算具有如下特点：(1)无线传感器网络本质上与地理位置有关，具有特殊的物理几何特性；(2)有关的通信代价所占比重较高；(3)物理测量的精度受限，因此追求高精确性计算不现实；(4)节点功耗可能是限制计算能力的最大障碍；(
16、5)最关键的是数据采集本身是分布式的且不可预测，因此需要设计新型的感知、通信和计算模型。第6章 WSN定位技术7粗粒度与细粒度依据定位所需信息的粒度可将定位算法和系统分为两类：根据信号强度或时间等来度量与信标节点距离的称为细粒度定位技术；根据与信标节点的接近度来度量的称为粗粒度定价技术。其中细粒度又可细分为基于距离和基于方向性测量两类。另外，应用在Radio-Camera定位系统中的信号模式匹配专利技术（signal pattern matching）也属于细粒度定位。粗粒度定位的原理是利用某种物理现象来感应是否有目标接近一个已知的位置，如Active Badge、Convex Optioni
17、zation、Xeror的Pare TAB系统、佐治亚理工学院的Smart Floor等。Cricker、AHLos、RADAR、LCB等都属于细粒度定位算法。第6章 WSN定位技术8绝对定位与相对定位绝对定位与物理定位类似，定位结果是一个标准的坐标位置，如经纬度。而相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发现，在相对定位的基础上也能够实现部分路由协议，尤其是基于地理应置的路由，而且相对定位不需要信标节点。大多数定位系统和算法都可以实现绝对定位服务，典型的相对定位算法和系统有SPA（S
18、elf Positioning Algorithm）、LPS（Local Positioning System）、SpotON，而MDS-MAP定位算法可以根据网络配置的不同分别实现两种定位。第6章 WSN定位技术9三角测量、场景分析和接近度定位定位技术也可分力三角测量、场景分析和接近度三类。其中，三角测是和接近度定位与粗、细粒度定位相似；而场景分忻定位是根据场景特点来推断目标位置，通常被观测的场景都有易于获得、表示和对比的特点，如信号强度和图像。场景分析的优点在于无需定位目标参与，有利于节能并具有一定的保密性；它的缺点在于：需要事先预制所需的场景数据集，而且当场景发生变化时必须重建该数据集。
19、RADAR系统（基于信号强度分析）和MIT的Sinart Rooms（基于视频图像）就是典型的场景分析定位系统。第6章 WSN定位技术62 测距方法6.2.1 接收信号强度指示法（RSSI）接收信号强度(Receivcd Signal Strength Indicator，RSSI)指示法是接收机通过测量射频信号的能量来确定与发送机的距离。由于RSSI指示已经是现有传感器节点标准功能，因此实现简单并且对节点的成本和功耗没有影响，因此RSSl方法已被广泛采用，不足之处是遮盖或折射会引起接收端产生严重的测量误差，因此精度较低，有时测距误差可达到50第6章 WSN定位技术6.2.2 到达时间法（TO
20、A）到达时间测距：已知信号的传播速度，根据信号的传播时间来汁算节点间的距离。图6-2给出了TOA测距的一个简单实现，采用伪噪声序列信号作为声波信号，根据声波的传播时间来测量节点间的距离。节点的定位部分主要由扬声器模块、麦克风模块、无线电模块和CPU模块组成。假设两个节点间时间同步，发送节点的扬声器模块在发送伪噪声序列信号的同时，无线电模块通过无线电同步信息通知接收节点伪噪声序列信号发送的时间，接收节点的麦克风模块在检测到伪噪声序列信号后，根据声波信号传播时间和速度计算发送节点和接收节点之间的距离。与无线射频信号相比，声波频率低，速度慢，对节点硬件的成本和复杂度的要求都低，但是声波的缺点是传播速
21、度容易受到大气条件的影响。基于TOA的定应精度高，但要求节点间保持精确的时间同步、因此时传感器节点的硬件和功耗提出了较高的要求。到达时间法(Time of Arrival，TOA)该方法通过测量信号传输时间来估算两节点之间的距离，精度较好。缺点是无线信号的传输速度快，时间测量上的很小误差可导致很大的距离误差值，另外要求传感器节点的计算能力较强。第6章 WSN定位技术一种用来测量信号传输所用时间的方法是测量信号单向传播时间。这种方法测量发送和到达接收方的绝对时间差，发送方和接收方的本地时间需精确同步。例如通过测量射频信号到达时间来测距，精度要求分米级时，需要双方时间同步的误差在lns内。另外一种
22、方法是测量信号往返时间差，接收节点在收到信号后直接发回，发送节点测量收发的时间差，由于仅使用发送节点的时钟，因此避免节点间时间同步的要求。这种方法的误差来源于第二个节点的处理延时，可以通过预先校准等方法来获得比较准确的估计。最近精确测量TOA时间的一个趋势是使用超宽带(UWB)。UWB信号有着大于500MHz的带宽和非常短的脉冲，这种特点使得UWB信号容易从多径信号中区分出来，有着良好的时问精度。第6章 WSN定位技术6.2.3 到达时间差法（TDOA）到达时间差法(TDOA，Time Difference of Arrival)是测量不同的接收节点接收到同一个发射信号的时间差。TDOA与TO
23、A不同，无需发送方和接收方时钟同步，而是转为对接收节点之间的时间同步要求。假设发送节点t发射一RF信号，接收节点i，j接收到信号的时间差与节点t，i，j坐标的关系如下： (6-4)由式（6-4）可知，测得 ，待定位节点t的坐标 在已知位置的节点i，j坐标 和 为焦点的双曲线上，如图6-3所示，未知节点在坐标(1.2，1)处，4个锚节点两两组合产生一条双曲线，由这些双曲线的交点可以推算出未知节点的位置。第6章 WSN定位技术第6章 WSN定位技术6.2.4 到达角法（AOA）如图6-4，到达角法(AOA，AngIe of Arrival)方法通过配备天线阵列或多个接收器来估测其它节点发射的无线信
24、号的到达角度。AOA方法需要额外硬件，在体积和功耗上对节点提出更高的要求。第6章 WSN定位技术6.3 常用的定位计算方法测边或测角是WSN定位中应用最为广泛的方法，它能确定节点大概的位置范围，因此值得对它的数学原理进行了解。6.3.1 三边定位与求解三边定位与求解原理如图6-6所示，假设有三个信标节点A、B、C坐标分别为 ，未知节点D的坐标为 ，与三个信标节点的距离分别为 ，那么，存在以下公式，即第6章 WSN定位技术从最后一个方程开始分别减去第一、二个方程得： （6-6）由式（6-6）可得到节点D的坐标为 （6-7） 第6章 WSN定位技术6.3.2 三角定位与求解三角定位与求解原理如图6
25、-7所示，已知三个信标节点A、B、C坐标分别为 ，未知节点D相对于节点A、B、C的角度分别为 、 、 ，节点D的坐标为 。第6章 WSN定位技术对于节点A、B和角 ，如果弧段AB在 内，那么能够唯一确定一个圆。设圆心为 ，半径为 ，那么 ，并且有下列公式，即 （6-8）由式（6-8）能够确定圆心 点的坐标和半径 。同理对B、C和角 与A、C和角 分别确定相应的圆心 和半径 与和半径 。最后利用三边测量法，由点D 、 、 与 确定D点坐标。 第6章 WSN定位技术6.3.4 极大似然估计法 极大似然估计法（maximum likelihood estimation）如图6-8所示，已知1，2，3
26、，n个节点的坐标分别为 ，它们到节点D的距离分别为 ，假设节点D坐标为 。那么有下列公式： （6-9）第6章 WSN定位技术从第一个方程开始分别送去最后一个方程，得： （6-10）式（6-10）的线性方程表示方式为：其中： ，根据最小均方估计方法可求得节点D的坐标为：(6-11）当矩阵求逆不能计算时，单边测量法则不适用，否则即可成功得到位置估计。第6章 WSN定位技术6.4 典型WSN定位系统和算法到目前为止，WSN自身定位系统和算法的研究大致经过了两个阶段：第1阶段主要偏重于紧密藕合型和基于基础设施的定位系统，代表性的研究成果包括RADAR, Active Bat , Active Badg
27、e, RadioCamera, Active Office,Easy Living，SpotON, HiBall Tracker, Parc TAB, Smart Floor, Smart Rooms, 3D-iD, WhereNett等。第6章 WSN定位技术6.4.1 Active Badge定位系统Active Badge定位系统最早为大楼内定位而设计的便携式的定位系统。便携设备发出红外光。因为红外光不能穿过墙壁，所以每一个房间就成为Badge所能分辨的最小单位。每个房间至少有一个红外接收器。便携设备Badge在楼里活动，Badge周期性地主动向周围发出全局唯一的身份标识信息。附近的接收
28、器捕捉到信息并通过网络送往中央服务器。中央服务器不断收集Badge的位置信息。于是，可以从中央服务器上查询出某个Badge的当前所在位置。第6章 WSN定位技术6.4.2 Active Office Ward等人研究了另一种室内定位系统“Active Office”。这里使用了超声波，接收器被放在一个已知位置的地方，以阵列方式安装在天花板上。需要定位的设备作为超声波的发送方，向接收器发射超声波。 需要定位时，中央控制器发出一个无线消息，该消息包含需要定位的设备的地址。需要定位的设备收到无线消息以后，发出一个短时的超声波脉冲。这个脉冲被接收器阵列接收到。并计算各自的到达时间及超声波脉冲与无线消息
29、的到达时间差。根据这些时间差可以计算出定位设备到每个超声波接收器之间的距离，并求解多边问题(在中央控制器内进行)，进而估计出移动设备的位置。无线消息的发送周期为200ms，因此移动设备在大多数时间处于睡眠状态。 该系统通过统计的方法上除那些过分偏离正常的数外，从而提高距离估计的准确性。该系统的准确性很高，平均意义上95%的估计值与真实位置误差在8cm以内。第6章 WSN定位技术6.4.3 Cricket定位系统 为了弥补紧密耦合定位系统的不足，MIT开发了最早的松散耦合定位系统Cricket。它由散布在建筑物内位置固定的锚节点和需要定位的人或物体携带的未知节点(称为Listener)组成。锚节
30、点随机地同时发射RF和超声波信号，RF信号中包含该锚节点的位置和ID。未知节点使用TDOA技术测量其与锚节点的距离，当它能够获得3个以上锚节点距离时即使用三边测量法提供物理定位，精度为44平方英尺（1英尺=0.3048米），否则就以房间为单位提供符号定位。第6章 WSN定位技术6.4.4 APIT APIT算法是一种适用于大规模无线传感器网络的分布式无需测距的定位算法。APIT虽然是无需测距的定位算法，但其利用了电磁波强度大小与距离的相对关系，因此相比于其它无需测距定位算法有着定位精度高，对节点密度要求低，通信量小的优点且适用于电磁波不规则模型。 APIT算法中锚节点定时广播自己的坐标信息，节
31、点与邻居节点相互交换接收到的锚节点定位信号强度并以此来判断节点是否在锚节点组成的三角形内，从而估计节点可能位于的区域。如图6-9, APIT经过大量三角形的交叠来缩小节点可能位于的区域的面积，最终计算交叠区域的质心作为节点位置的近似。第6章 WSN定位技术6.4.5 AHLos AHLOS(Ad-Hoc Localization System)是一个迭代的定位算法。具体定位过程为:未知节点首先利用TDOA方法测量与其邻居节点的距离；当未知节点的邻居节点中信标节点大于或等于3个时，利用极大似然法计算自身位置，随后该节点转变成新的信标节点，称为转化信标节点，并将自身的位置广播给邻居节点；随着系统中
32、转变信标节点数量不断增加，对于原来邻居节点中信标节点数量少于3个的未知节点，将逐渐拥有足够的邻居信标节点，就能够利用极大似然估计方法计算自身的位置。这个过程一直重复到所有节点都计算出自身的位置。第6章 WSN定位技术 1原子多边算法 原子多边算法(atomic multilateration)如图6-10 (a)所示，在未知节点的邻居节点中至少有3个原始信标节点(非转化信标节点)，这个未知节点基于原始信标节点，利用极大似然估计方法计算自身位置。 2迭代多边算法 迭代多边算法(iterative multilateration)是指邻居节点中信标节点数量少于3个，在经过一段时间后，其邻居节点中部
33、分未知节点在计算出自身位置后成为转化信标节点。邻居节点中信标节点数量等于或大于3个时，这个未知节点基于原始信标节点的和转化信标节点，利用极大似然估计方法计算自身位置。第6章 WSN定位技术3协作多边算法协作多边算法(collaborative multilateration)是指在经过多次迭代定位以后，部分未知节点的邻居节点中，信标节点的数量仍然少于3个，此时必须要通过其他节点的协助才能够计算自身位置。如图6-10(b)所示，在经过多次迭代定位以后，未知节点2的邻居节点中只有1和3两个信标节点，节点2要通过计算到信标节点5和6的多跳距离，再利用极大似然估计方法计算自身位置。 第6章 WSN定位
34、技术AHLos算法的缺点为:(1)将己定位的未知节点直接升级为锚节点虽然缓解了锚节点稀疏问题，但会造成误差累计-相对于测距精度，该算法的定位精度降低了一个数量级。(2)在AHLos算法中并没有给出一组节点能否执行collaborative multilateration的充分条件。如图6-10(c)所示，如果执行协作式定位，节点的解并不唯一。AHLos算法对信标节点的密度要求高，不适用于规模大的传感器网络。而且迭代过程中存在累积误差。文献45中引入了N-跳段多边算法(N-hop multilateration)，是对协作多边算法的扩展。在n-跳段多边算法中，未知节点通过计算到信标节点的多跳距离
35、进行定位，减少了非视线关系对定位的影响，对信标节点密度要求也比较低。此外，节点定位之后引入了修正阶段，提高了定位的精度。第6章 WSN定位技术6.4.6 SPA相对定位瑞士洛桑联邦工业大学(EPFL)的Srdjan Capkun等人针对无基础设施的移动无线网络，提出了一种称为SPA(self-positioning algorithm) 的相对定位算法。它选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考点(称为location reference group)，并在其中选择连通度最大的一个节点作为坐标系统的原点。首先根据节点间的测距结果在各个节点建立局部坐标系统，通过节点间的信息交
36、换与协调，以参考点为基准通过坐标变换(旋转与平移)建立全局坐标系统。因为所有节点都需要参与坐标的建立和变换计算，所以SPA的通信开销与节点数量几乎呈指数比。第6章 WSN定位技术针对SPA的缺点，美国仁斯利尔理工学院(Rensselaer Polytechnic Institute)的Rajagopal Iyengar等人提出了一种基于聚类(clustering-based)的定位算法:网络部署后，每个节点都开始运行一个随机定时器。假如与邻居节点相比，节点的定时器最早到期，则成为一个主节点(master)，并向邻居节点广播一个消息，所有接收到该消息的邻居节点终止自己的定时器并成为一个从节点(s
37、lave)，这些节点形成一个域。然后分别以这些主节点为原点使用与SPA类似的方法建立各个域的局部坐标系统。然后以主节点ID较小的局部坐标系统为参考，相邻域进行坐标转换，逐步建立全局坐标系统。因为通信量是随着域的数量而增长的，所以该算法的通信开销与网络中节点数量呈线性比，更适合于大规模网络的部署。很显然，相对定位算法最大的问题是当参考点移动或失效时，整个网络就必须重新定位。第6章 WSN定位技术6.4.7 凸规划加州大学伯克利分校的Doherty等人将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得
38、到一个全局优化的解决方案，确定节点位置。同时也给出了一种计算未知节点有可能存在的矩形区域的方法。如图6-12所示，根据未知节点与锚节点之间的通信连接和节点无线射程，计算出未知节点可能存在的区域(图中阴影部分)，并得到相应矩形区域，然后以矩形的质心作为未知节点的位置。凸规划是一种集中式定位算法，在锚节点比例为10%的条件下，定位精度大约为100%。为了高效工作，锚节点必须部署在网络边缘，否则节点的位置估算会向网络中心偏移。第6章 WSN定位技术6.4.8 APS美国路特葛斯大学(Rutgers University)的Dragos Niculescu等人利用距离矢量路由(distance vec
39、tor routing)和GPS定位的原理提出了一系列分布式定位算法，合称为APS(ad hoc positioning system)。它包括6种定位算法:DV Hop,DV-distance, Euclidean, DV-coordinate, DV-Bearing和DV-Radial。第6章 WSN定位技术1DV Hop定位算法DV Hop算法由3个阶段组成。首先使用典型的距离矢量交换协议，使网络中所有节点获得距锚节点的跳数(distance in hops)。第2阶段，在获得其他锚节点位置和相隔跳距之后，锚节点计算网络平均每跳距离，然后将其作为一个校正值(correction)广播至网
40、络中。校正值采用可控洪泛法在网络中传播，这意味着一个节点仅接收获得的第1个校正值，而丢弃所有后来者，这个策略确保了绝大多数节点可从最近的锚节点接收校正值。在大型网络中，可通过为数据包设置一个TTL域来减少通信量。当接收到校正值之后，节点根据跳数计算与锚节点之间的距离。当未知节点获得与3个或更多锚节点的距离时，则在第3阶段执行三边测量定位。如图6-13所示，已知锚节点L1与L2,L3之间的距离和跳数。L2计算得到校正值(即平均每跳距离)(40+75)/ (2+5)=16.42。在上例中，假设A从L2获得校正值，则它与3个锚节点之间的距离分别为Ll=316.42, L2=216.42, L3=31
41、6.42,然后使用三边测量法确定节点A的位置。第6章 WSN定位技术DV-Hop算法在网络平均连通度为10，锚节点比例为10%的各向同性网络中定位精度约为33%。其缺点是仅在各向同性的密集网络中，校正值才能合理地估算平均每跳距离。第6章 WSN定位技术 2DV-distance定位算法 DV-distance算法与DV-Hop类似，所不同的是相邻节点使用RSSI测量节点间点到点距离，然后利用类似于距离矢量路由的方法传播与锚节点的累计距离。当未知节点获得与3个或更多锚节点的距离后使用三边测量定位。 DV-distance算法也仅适用于各向同性的密集网络。实验显示，该算法的定位精度为20%(网络平
42、均连通度为9，锚节点比例为10%,测距误差小于10%)；但随着测距误差的增大，定位误差也急剧增大。 第6章 WSN定位技术3Euclidean定位算法Euclidean定位算法给出了计算与锚节点相隔两跳的未知节点位置的方法。假设节点拥有RSSI测距能力，如图6-14所示，已知未知节点B, C在锚节点L的无线射程内，BC距离已知或通过RSSI测量获得；节点A与B, C相邻。对于四边形ABCL，所有边长和一条对角线BC已知，根据三角形的性质可以计算出AL的长度(节点A与L的距离)。使用这种方法，当未知节点获得与3个或更多锚节点之间的距离后定位自身。第6章 WSN定位技术5DV-Bearing和DV
43、-Radial定位算法E911系统和智能机器人导航领域都有使用AOA技术确定目标方向和位置的方案，但它们大都使用了高能耗的天线阵列测量信号方向，并不适用于低能耗的WSN领域。针对这个问题，MIT提出了一种融合TDOA和信号到达相位差的硬件解决方案cricket Compass，其原型系统可在140角内以5的误差确定接收信号方向。DV-Bearing和DV-Radial算法提出了以逐跳方式(hop by hop)跨越两跳甚至三跳来计算与锚节点的相对角度，最后使用三角测量定位的方法。两者的区别在于，DV-Radial算法中每个锚节点或节点都安装有指南针(compass)，从而可以获得绝对角度信息(
44、例如与正北方向的夹角)，并达到减少通信量和提高定位精度的目的。实验显示，DV-Bearing和DV-Radial算法在网络平均连通度为10.5，锚节点比例为20%，AOA测量误差小于5的条件下，90%以上的节点可以实现定位，定位精度分别为40%和25%。第6章 WSN定位技术6.4.9 Cooperative ranging和Two-Phase positioning 为了减小测距误差对定位的影响，加州大学伯克利分校的Chris Savarese等人提出了两种循环求精定位算法一一Cooperative ranging和Two-Phasepositioning。 他们都分为启始和循环求精两个阶段
45、。启始阶段着重于获得节点位置的粗略估算。而在循环求精阶段，每一次循环开始时每个节点向其邻居节点广播它的位置估算，并根据从邻居节点接收的位置信息和节点间测距结果，重新执行三边测量，计算自身位置，直至位置更新的变化可接受时循环停止。 Cooperative ranging算法的启始阶段又称为TERRAIN(triangulation via extended range and redundant association of intermediate nodes)。首先在所有锚节点上，根据节点间测距结果使用ABC算法(assumption based coordinates algorithm)
46、建立局部坐标系统，然后将结果(以这个锚节点为原点的局部网络拓扑)传播到整个网络。未知节点根据它所获得的网络拓扑确定其与锚节点的距离，当获得4个与锚节点的距离后，使用三边测量定位自身。然后进入循环求精阶段。第6章 WSN定位技术 与Cooperative ranging算法不同，为了克服锚节点稀疏问题，Two-Phasepositioning算法在启始阶段使用Hop-TERRAIN算法(与DV-hop类似)获得节点位置的粗略估算。在循环求精阶段，使用加权最小二乘法进行三边测量以计算新位置。它有两个特点:(1)给节点的位置估算增加了一个权值属性(锚节点为1，未定位节点为0.1；未知节点每执行一次定
47、位计算后，将自身权值设为参与定位计算的节点的均值)，利用加权最小二乘法进行定位计算，使误差越大的节点对定位计算影响越小。(2)对因连通度低导致定位误差大的节点，通过不让其参与求精过程来消除它们的影响。实验显示，Cooperative ranging算法定位精度可达到5%(测距误差为5%，而单纯使用TERRAIN算法得到的定位精度约为39%)。而Two-Phase positioning算法在锚节点比例为5%,测距误差为5%，网络连通度约为7的条件下，定位精度约为33%。第6章 WSN定位技术6.4.10 Generic Localized Algorithms 前面分析了Cooperative
48、 ranging算法使用循环求精来降低测距误差影响，AHLos算法利用将己定位的未知节点升级为锚节点来解决锚节点稀疏问题。在此基础上，加州大学洛杉矶分校的Seapahn Meguerdichianl等人提出了通用型定位算法(generic localized algorithm)，它的特点在于，详细指定了未知节点接受位置估算并升级为锚节点的条件，以减少误差累计的影响。该算法也由启始和循环两阶段组成。启始阶段中，将相邻节点少于3个的节点标记为orphan，将锚节点标记为gotFinal。在循环阶段，首先相邻节点交换信息，假如一个未知节点的邻居节点中非orphan节点的数量小于3，就将其标记为or
49、phan节点。假如一个节点有3个以上的邻居节点为gotFinal，则该节点就从中随机选择3个执行多次三边测量定位。执行的次数依赖于gotFinal邻居节点的数量，并确定自身位置为多次定位结果的均值。然后，该节点根据多次定位结果的一致性和gotFinal邻居节点的数量计算一个目标函数值。最后，相邻节点比较目标函数值，那些目标函数值最低的节点将接受位置估算并升级为锚节点，而其他节点都丢弃它们的位置估算，进入下一轮循环。因为每次循环都至少会有一个节点成为orphan节点或升级为锚节点，所以循环最终会结束。实验显示，Generic Localized Algorithm在锚节点定位误差为10%，锚节点
50、比例为20%，测距误差在25%条件下，定位精度为40%。第6章 WSN定位技术6.4.11 MDS-MAPMDS-MAP30是一种集中式定位算法，可在range-free和range-based两种情况下运行，并可根据情况实现相对定位和绝对定位。它采用了一种源自心理测量学和精神物理学的数据分析技术多维定标(multidimensional scaling)，该技术常用于探索性数据分析或信息可视化。MDS-MAP算法由3个步骤组成:(1)首先从全局角度生成网络拓扑连通图，并为图中每条边赋予距离值。当节点具有测距能力时，该值就是测距结果。当仅拥有连通性信息时，所有边赋值为1。然后使用最短路径算法，
51、如Dijkstra或Floyd算法，生成节点间距矩阵。第6章 WSN定位技术(2)对节点间距矩阵应用MDS技术，生成整个网络的2维或3维相对坐标系统。(3)当拥有足够的锚节点时(2维最少3个，3维最少4个)，将相对坐标系统转化为绝对坐标系统。实验显示，当网络的节点密度减小时，定位误差增大，并且无法定位的节点数量增加；而当网络连通度达到12.2时，几乎全部节点都可实现定位；在拥有200个节点(其中4个锚节点)，平均连通度为12.1的网络中，在range-free条件下，定位误差约为30%；而在range-based条件下，定位误差为16%(测距误差为5%)。第6章 WSN定位技术6.5 定位算法
52、设计的注意问题6.5.1 典型定位系统和算法比较从整体上看，近年来提出的一些循环求精算法，如Cooperative rangingTwo-phase positioning n-hop multilateration primitive，更加充分发挥了WSN的特点，即利用节点间的协同工作实现单个节点无法完成的任务。它们在初始阶段着重于获得节点位置的粗略估算，并在求精阶段根据用户预设的精度门限循环求精；甚至还可根据应用需求，将整个求精阶段作为一个可选阶段。这些算法不仅提高了定位精度，还给予用户更大的自由度，正逐渐形成一个新的类别。第6章 WSN定位技术但还应看到，现有的定位系统和算法还存在如下一
53、些问题: (1)未知节点必须与锚节点直接相邻，锚节点密度过高，例如Cricket Cooperative ranging。(2)定位精度依赖于网络部署条件。例如，DV-Hop, DV-distance仅适用于密集部署的各向同性网络；N-hop multilateration primitive和凸规划算法要求锚节点必须部署在网络的边缘。(3)没有对距离/角度测量误差采取抑制措施，造成误差传播和误差积累，定位精度依赖于距离/角度测量的精度。例如AHLos, DV distance, DV Bearing, DV Radial, SPA及其改进算法。第6章 WSN定位技术(4)依靠循环求精过程抑制
54、测距误差和提高定位精度。虽然循环求精过程可以明显地减小测距误差的影响，但不仅产生了大量的通信和计算开销，而且因无法预估循环的次数而增加了算法的不确定性。例如，Cooperative ranging, Two-phase positioning, N-hop multilateration primitiveo (5)算法收敛速度较慢。例如，Generic Localized Algorithm算法在每次循环中，相邻节点中仅有一个可实现定位并升级为锚节点。 仿真显示，许多算法和系统的定位精度都还有很大的提高空间69。总之，无线传感器网络定位问题的研究仍然是WSN的一个技术难点，也是关键点之一。第
55、6章 WSN定位技术6.5.2 定位算法设计的注意问题 由前几节内容可知，WSN的定位算法非常多，但是没有一个定位算法是完美的。在实际应用中，如何设计合适的定位算法，需要根据以下的一些因素进行分析。1资源受限2定位算法应用场景3节点密度第6章 WSN定位技术6.6 小结定位是无线传感器网络（WSN）的基本功能之一，根据定位机制的不同，WSN定位算法的分类不同。研究者已经提出了很多定位算法，都具有各自的特点和适用范围，没有那种算法是最优的。目前的定位算法，大都对信标节点密度和网络部置条件的依赖度较高，虽然可以依靠循环求精度等方法抑制测距误差和提高定位精度，但同时增大通信和计算开销，加大了算法的不确定性。针对不同的实际应用，应该通过综合考虑节点的规模、能耗、成本和对定位精度的要求，来选择最合适的定位算法。
