无线传感网络定位算法基于移动锚节点的距离无关定位算法一、无线传感网络定位算法简介1.背景及意义2.概念3.相关术语4.技术特点5.相关应用二、基于移动锚节点的距离无关定位算法简介1.距离无关定位算法比较2.距离无关的移动锚节点定位方法三、典型算法：LMAP算法及其改进一、无线传感网络定位算法简介1.背景及意义随着计算机技术、微电子技术和通信技术的进步，传感器已朝着集成化、微型化、智能化和低能耗的方向快速发展，使其能够在较小体积内集成信息采集、数据处理和信息的传输等多种功能，这为无线传感网(Wireless Sensor NetworksW SN)的产生和发展奠定了基础。

无线传感网是由部署在监测区域内大量廉价微型的具有有限数据处理能力和装备有低能耗无线信号收发器的传感器节点通过无线通信方式形成的一个多跳自组织网络，其目的是利用网络节点协作地感知和采集网络覆盖区域内感兴趣的信息，并发送给观察者。

它通过大量随机部署在监测区域的传感器节点来监测和感知周围的物理环境。

无线传感网具有布线成本低、监测精度高、系统容错性好、可远程监控以及便于诊断与维护等众多的优点，它的产生解决了传统传感器网络在应用中遇到的安装、维护等方面的种种困难。

其在军事、工业、医疗、交通、环保等领域有着广阔的应用前景。

如果说互联网改变了人与人之间的信息交流方式，那么，无线传感网的产生将改变人与自然界的交互方式。

位置信息是无线传感网正常工作和应用中不可缺少的部分，缺少位置信息网络很可能无法正常工作，在某些应用中缺少位置信息也将会是致命的。

无线传感网最基本的功能之一就是位置信息(事件发生的位置或采集数据的节点的位置)。

但是，受到无线传感网自身所具有的低能耗、低成本的特点限制，现有传统定位技术(如GPS)对于无线传感网来说并不适用，因此开发出适用于无线传感网的定位技术势在必行。

通常无线传感网节点是随机分布在不同的环境中进行各项监测任务。

节点只有知道了自身的位置信息，才能够提供有效的监测消息。

因此，对于无线传感网的监测活动来说，位置信息至关重要，在很多无线传感网应用中，没有节点位置信息的监测信息往往毫无意义。

监测到事件后关心的一个重要问题就是该事件发生的位置，这是进一步采取措施和做出决策的基础。

如森林火灾监测，天然气管道泄漏监测，战场上敌方车辆运动的区域具体地点等。

定位信息除了用来确定事件发生的地点外，还可以用于目标跟踪、目标轨迹预测、协助路由等。

获取位置信息是无线传感网基本功能之一，定位技术是无线传感网的一项重要支撑技术。

目前针对无线传感网的定位机制和定位算法已经大量涌现。

通常这些算法都在二维情况下使用，但是经过扩展以后，可以很好的在三维情况下运用。

2.无线传感定位的概念对于定位一般的理解就是确定位置。

在无线传感网中，定位是指网络通过特定的方法确定节点的位置信息。

其可分为节点的自身定位和目标定位。

节点自身定位是确定网络中节点位置坐标的过程，它是网络自身属性的确定过程，是网络的支撑，可以通过人工配置或各种节点自定位算法完成，它是整个无线传感网存在的必要的支撑技术之一;目标定位是指在网络覆盖范围内确定一个事件或一个目标的位置坐标，这可以通过把位置已知的网络节点作为参考节点来确定事件或目标在网络中所处的位置，它是无线传感网的一项重要应用方向。

两者可以统一起来考虑，无线传感网定位问题就是寻求利用少量的锚节点来确定网络中未知节点的位置坐标的方法。

位置信息可以分为两种类型:一种是物理位置，它表示目标的相对或者绝对位置，是指目标在特定坐标系下的位置数值。

另一种是符号位置，它表示的是目标与基站之间的连通关系，提供目标大致的所在范围，即指在目标与一个基站或者多个基站接近程度的信息。

3. 无线传感网定位技术有关术语未知节点(Unknown nodes): WSN中不能自主定位，需要依赖定位算法和已知位置信息的节点来定位的节点。

锚节点(Anchor nodes):通过GPS系统或人工部署已知自身位置信息，并且能够协助网络对未知节点定位的节点，又称为信标节点。

邻居节点(Neighbor nodes):在传感器节点通信半径内，可直接相互通信的节点。

跳数(Hop count):两个节点之间间隔的跳段总数。

测距(Range:测量相互能够通信的节点之间的距离。

测距误差(Range error):测量距离与真实距离之间的误差。

一般指它与真实距离之间的比值。

到达时间(Time of Arrival, TOA):一种信号从一个节点传播到另一个节点所需的时间。

到达时间差(Time difference of arrival, TDOA):两种不同传播速度的信号从一个节点传播到另一个节点所需时间之差。

到达角度(Angle of arrival, AOA):节点接收到的信号相对于自身轴线的角度。

接收信号强度(Received signal strength indicator, RSSI):节点接收到无线信号强度的大小;视线关系(Line of sight, LOS):没有任何障碍物间隔的两个节点间能够直接通信的关系。

非视线关系(No line of sight，NLO S:两个节点之间存在障碍物。

网络连通度(Network connectivity:网络中所有节点的邻居节点个数的平均值。

覆盖率(Coverage rate:能够确定坐标位置的节点在总节点数中所占的比例。

基础设施(Infrastructure:协助传感器节点定位的已知自身位置的固定设备，如卫星、基站等。

4. 无线传感网定位技术特点①自组织性通常无线传感网中的节点是随机布设的，不能依靠全局的基础设施的协助确定每个节点的位置所在。

②容错性传感器节点的硬件配置低、处理能力弱、可靠性差、能量少以及测距时会产生误差等因素决定了传感器节点本身的脆弱性，因此定位算法必须具有良好的容错性。

③能量高效性为了尽量延长网络的生存周期，要尽可能的减少节点间的通信开销，减少算法中计算的复杂度，用尽量少的能量完成尽可能多的工作。

④分布式计算每个节点自己对自身的位置进行估算，不需要将所有信息传送到某个特定的节点进行集中计算。

5. 无线传感网定位技术相关应用①导航导航是定位最基本的用途。

例如:在军事上，通过事先部署的无线传感网采集到的信息，可以对敌方目标进行准确的定位，为火控系统提供精确的制导;在智能交通系统中可以通过网络节点的布设获取车辆的位置信息可以为道路车辆提供信息反馈，从而实现城内精确导航等。

②目标跟踪目标跟踪是指网络实时监测目标的行动路线，预测目标的前进轨迹。

例如在战场上实时的跟踪并报告敌方运动态势以便及时采取相应的措施。

另外，在工厂、物流管理和医院仪器管理等环境中都有很广泛的应用和迫切的需求。

③事件的监控事件监控是指通过网络对某些感兴趣的事件进行监控。

例如:对森林防火应急监控，目前很多森林的防火监控都是利用无线传感网来实现的，将网络节点部署在监控区域，通过传感网络回传至控制中心的数据一旦发生异常情况，就可以通过该节点的相关地理位置信息判断出是什么地方发生异常，以便工作人员采取相关措施。

④定向信息查询如果管理节点需要知道某一个监测区内的状态或是否有事件发生，可以将监测任务发布到这个区域内的传感器节点进行定向的信息查询。

⑤进行网络管理网络可以利用传感器节点的位置信息构建网络拓扑图，据此实时地统计网络覆盖情况，对覆盖较差的区域及时采取必要的补救措施。

⑥协助路由路由算法可以借助节点的位置信息进行路由选择，基于地理位置的网络路由就是一种利用节点位置信息进行网络路由的优化路由。

此种优化路由需要网络中的节点知晓每个节点或者至少相邻节点的位置信息，据此做出优化的路由选择。

在无线传感网中，优化的路由可以提高系统性能、安全性，从而节省宝贵的电能。

二、基于移动锚节点的距离无关定位算法简介1.距离无关定位算法比较距离无关定位算法不需要使用测距技术, 只利用连通情况来估测自己的位置。

绝大多数距离无关定位算法采取分布式计算模式, 因为其可扩展性好, 每个节点的计算复杂度与网络的规模无关, 计算简单而且容易实现, 同时计算在节点进行, 通信量小。

分布式的距离无关算法可以细分为两种: 基于邻近关系( proximity ) 和基于跳计数( dist ance in hops) 。

(1). 基于邻近关系的算法邻近关系是指两个节点在彼此的通信半径范围内, 节点通常以与锚节点间的邻近关系作为限制条件, 利用一定的几何方法( 如三角形、圆、矩形) 来确定自己所在区域范围, 然后以此区域的质心作为估计位置。

典型的算法有:1) 质心算法 ( centroid) 的核心思想是: 与未知节点处于邻近关系的所有锚节点, 所组成的多边形区域的质心, 作为未知节点的位置估计;2) APIT 算法 ( approximat e point in tr iangulationtest) 的核心思想是: 与未知节点处于邻近关系的3 个锚节点构成1 个三角形, 以多个这样的三角形的交叠区域的质心作为未知节点的位置;3) Bounding Box 算法定义了一个离散通信模型。

整个网络被划分为n ! n 个单元, 若一个节点能够与N 个锚节点通信, 则该节点在这N 个锚节点的正方形通信区域的交叠区域中。

上述3 个算法定位精度严重依赖于锚节点的密度和分布。

但是由于实际传感器网络中锚节点难以均匀分布,同时增加锚节点比例会大大提高网络成本, 加剧通信竞争和冲突( 即锚节点稀疏问题) , 因此他们是典型的受锚节点稀疏问题影响的算法。

(2). 基于跳计数的算法当锚节点的密度不大时, 很多节点无法直接与锚节点通信, 此时节点可以通过一定方式获得距离锚节点的跳数, 同时估算每跳距离, 计算出与锚节点的距离, 然后利用三边测量法或极大似然估计法等方法计算自己的坐标。

典型的算法有:1) DVhop 算法可以分为3 个阶段:使用距离矢量交换协议, 使网络中所有节点获得距锚节点的跳数; 锚节点计算网络平均每跳距离值, 并将其广播至网络中, 未知节点接收到该值后计算与锚节点的距离; 未知节点获得3 个以上距离后, 利用三边测距法或极大似然估计法定位;2) Amorphous 算法和DVhop 相似, 区别在于该法未知节点的跳数使用平均值; 同时假定预先知道网络的密度, 离线计算网络的平均每跳距离;3 )Euclidean 算法围绕在锚节点周围的节点的局部几何拓扑, 给出了计算与锚节点相隔两跳的未知节点位置的方法;4) Robust Posit ion 算法由两个阶段组成: 初始阶段和求精阶段。

初始阶段与DVhop 类似, 粗略估计; 求精阶段, 节点通过测量到所有一跳邻居的距离并依此进行位置计算来更新自己的位置。