_无线传感器网络定位算法

1、无线传感网络定位算法目录、常用定位技术1.1 GPS 与 A-GPS 定位1.2 基站定位（ cell ID 定位）1.3 Wifi AP 定位1.4 FRID 、二维码定位 二、定位算法研究的目的和意义三、 WSN 定位算法分析3.1基于锚节点的定位算法3.1.1 距离相关定位算法3.1.2 距离无关定位算法3.2基于移动锚节点的定位算法四、总结3.2.1 基于移动锚节点的距离相关定位算法3.2.2 基于移动锚节点的距离无关定位算法附：组员及分工情况错误 ! 未定义书签。1113、常用定位技术1.1 GPS 与 A-GPS 定位常见的GPS定位的原理可以简单这样理解：由24颗工作卫星组成，使

2、得在 全球任何地方、任何时间都可观测到 4颗以上的卫星，测量出已知位置的卫星到用户接收机之间的距离，然后综合多颗卫星的数据就可知道接收机的具体位置。在整个天空范围内寻找卫星是很低效的， 因此通过 GPS 进行定位时， 第一次启 动可能需要数分钟的时间。 这也是为啥我们在使用地图的时候经常会出现先出现 一个大的圈， 之后才会精确到某一个点的原因。 不过，如果我们在进行定位之前 能够事先知道我们的粗略位置，查找卫星的速度就可以大大缩短。GPS系统使用的伪码一共有两种，分别是民用的C/A码和军用的P（丫）码。民用精度约为10米，军用精度约为1米。GPS的优点在于无辐射，但是穿透力 很弱，无法穿透钢筋

3、水泥。 通常要在室外看得到天的状态下才行。 信号被遮挡或 者削减时， GPS 定位会出现漂移，在室内或者较为封闭的空间无法使用。正是由于 GPS 的这种缺点，所以经常需要辅助定位系统帮助完成定位，就 是我们说的 A-GPS。例如iPhone就使用了 A GPS,即基站或 WiFi AP初步定位后，根据机器内存储的 GPS 卫星表来快速寻星， 然后进行 GPS 定位。例如在民用的车载 导航设备领域， 目前比较成熟的是 GPS + 加速度传感器补正算法定位。 在日本 的车载导航市场是由 Sony 的便携式车载导航系统 Nav-U1 首先引入量产。例 如在增加了三轴陀螺仪的 iphone4 里可以利

4、用三轴陀螺仪来辅助完成定位，具 体可以参见这篇文章的介绍，不过三轴陀螺仪定位的误差会随着时间逐渐积累。1.2 基站定位（ cell ID 定位）小区识别码（ Cell ID ）通过识别网络中哪一个小区传输用户呼叫并将该信息翻译成纬度和经度来确定用户位置。 Cell ID 实现定位的基本原理：即无线网络上报终端所处的小区号（根据服务的基站来估计），位置业务平台把小区号翻译成经纬度坐标。基本定位流程：设备先从基站获得当前位置（ Cell ID ）第一次定位）设备通过网络将位置传送给A gps位置服务器Agps 服务器根据位置查询区域内当前可用的卫星信息，并返回设备 设备中的GPS接收器根据可用卫星

5、，快速查找可用的 GPS卫星，并返回GPS 定位信息。1.3 Wifi AP 定位设备只要侦听一下附近都有哪些热点，检测一下每个热点的信号强弱，然后 把这些信息发送给网络上的服务端。 服务器根据这些信息， 查询每个热点在数据 库里记录的坐标， 然后进行运算， 就能知道客户端的具体位置了。 一次成功的定 位需要两个先决条件：客户端能上网 ，侦听到的热点的坐标在数据库里有1.4 FRID 、二维码定位通过设置一定数量的读卡器和架设天线，根据读卡器接收信号的强弱、到达 时间、角度来定位。 目前无法做到精准定位， 布设读卡器和天线需要有大量的工 程实践经验难度大，另外从成本上来讲 WIFI 经济实用些

6、。二、定位算法研究的目的和意义定位是大多数应用的基础。 由于节点工作区域往往是人类不适合进入的区域， 或者是敌对区域， 甚至有时传感器节点需要通过飞行器抛撒， 因此节点的位置通 常是随机并且未知的。 而传感器节点自身的正确定位是提供监测事件位置信息的 前提，没有位置信息的监测消息往往是没有意义的。 传感器节点必须明确自身位 置才能详细说明“在什么位置或区域发生了特定事件 " ，除能报告事件的发生地 外，还能进行目标跟踪，实时监视目标路线，预测目标轨迹等；实现对外部目标 的定位和追踪。另一方面，了解传感器节点位置信息还可以协助路由，提高路由效率，为网 络提供命名空间， 向部署者报告网络

7、的覆盖质量， 实现网络的负载均衡以及网络 拓扑的自配置等网络管理。 因此，确定事件发生的位置或获取消息的节点位置尤 为重要，对传感器网络应用的有效性起着关键的作用。而全球定位系统是目前使用最广泛最成熟的定位系统， 通过卫星的授时和测 距对用户节点进行定位，具有精度高、实时性好、抗干扰能力强等优点，但是定 位适应于无遮挡的室外环境， 用户节点通常能耗高且体积大， 成本也比较高， 需 要固定的基础设施等。人工部署和为所有网络节点安装 GPS 接收器都会受到成 本、功耗、扩展性等问题的限制，甚至在某些场合可能根本无法实现，这使得它 不适用于低成本自组织的传感器网络，因此必须采用一定的机制与算法实现W

8、SN 的自身定位。随着计算机技术、 微电子技术和通信技术的进步， 传感器已朝着集成化、 微 型化、智能化和低能耗的方向快速发展，使其能够在较小体积内集成信息采集、数据处理和信息的传输等多种功能，这为无线传感网（Wireless SensorNetworks WSN） 的产生和发展奠定了基础。无线传感网是由部署在监测区域内大量廉价微型的具有有限数据处理能力和装备有低能耗无线信号收发器的传感器节点通过无线通信方式形成的一个多跳自组织网络，其目的是利用网络节点协作地感知和采集网络覆盖区域内感兴趣的信息，并发送给观察者。 它通过大量随机部署在监测区域的传感器节点来监测和感知周围的物理环境。无线传感网具

9、有布线成本低、监测精度高、系统容错性好、可远程监控以及便于诊断与维护等众多的优点， 它的产生解决了传统传感器网络在应用中遇到的安装、维护等方面的种种困难。其在军事、工业、医疗、交通、环保等领域有着广阔的应用前景。 如果说互联网改变了人与人之间的信息交流方式，那么，无线传感网的产生将改变人与自然界的交互方式。三、 WSN 定位算法分析3.1 基于锚节点的定位算法3.1.1 距离相关定位算法距离相关定位算法一般利用一定的测距技术得到节点间距离，再利用三边测量法、三角测量法或极大似然估计法计算出未知节点的位置。常用的测距技术包括接收信号强度（RSSI）技术、信号传输时间（TOA） 技术、信号到达时间

10、差（TDOA）技术和信号到达角度（AOA）技术。它们需要一些昂贵的辅助测量设备来测量节点间的距离，且受环境影响较大。如RSSI产生的测量误差较大；TDOA需要节点具有超声波发送与接收功能；AOA容易受到环境影响, 功耗较大等。但距离相关定位算法的一个突出优点是定位精度高，因此对定位精 度要求比较高的场合都用基于测距的定位算法实现定位。典型算法：接收信号强度指示法（RSSI）通过信号在传播中的衰减来估计节点之间的距离。假设已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为距离。在自由空间中，距发射机d处的天线接收到的信号强度由下面的公式给出：CC _

11、 ?-? =（4?2 ?2?其中，？?为发射机功率，?是距离d处的接收功率，？猬？?分别是发射天 线和接收天线的增益，d是距离，单位为米（m），L为与传播无关的系统损耗因 子，入是波长，单位为米（m）。由公式可知，在自由空间中，接收机功率随发射 机与接收机距离的平方衰减。这样，通过测量接收信号的强度，再利用上述公式 即可计算出收发节点间的大概距离。3.1.2距离无关定位算法利用节点间的连通情况来估测自己的位置。 其中一部分距离无关算法采用集 中式计算模式，用一些优化方法来提高定位精度，但是集中计算方式需要网络中 有计算中心支持，且计算中心附近节点通信量大，很快能量耗尽，使整个网络不 可用。绝大

12、多数距离无关定位算法采取分布式计算模式， 可扩展性好；由于位置 估测基于节点间的连通情况，计算简单而且容易实现；计算在节点本地进行，通 信量小。因为基于估测距离，距离无关算法定位精度不如距离相关算法好。典型算法：DV-h op算法距离向量一跳段（distanee vector-hop , DV-Hop）定位机制非常类似于传统网络中的距离向量路由机制，DV-Hop算法的定位过程主要分为 3个阶段: 1）计算未知节点与每个信标节点的最小跳数，锚节点向邻居节点广播自身位置信息的分组，其中，包括跳数字段，初始化为接收节点记录具有到每个锚节点的最小跳数，忽略来自同一个锚节点的较大 跳数的分组。然后，将跳

13、数值加 1，并转发给邻居节点。通过这种方法，网络中的所有节点能够记录下到每个锚节点的最小跳数。2）计算未知节点与锚节点的实际跳段距离每个锚节点根据第一阶段中记录的其它锚节点的位置信息和相距跳数，并利用下式估算平均每跳的实际距离IM?7 ?2 + （?务?）2? ?=式中（?？?，（? ?为锚节点i, j的坐标；？?为锚节点i与j（ i工j）之间的跳段数，然后，锚节点将计算的平均每跳距用带有生存期字段的分组广播至 网络中，未知节点仅记录接收到的第一个平均每跳距离， 并转发给邻居节点。这个策略确保了绝大多数节点从最近的锚节点接收平均每跳距离值。未知节点接收 到平均每跳距离后，根据记录的跳数，计算到

14、每个锚节点的跳段距离。3）利用三边测量法计算自身位置未知节点利用第二阶段中记录的到各个锚节点的跳段距离，利用三边测量法计算自身位置。已知A,B,C 3个节点的坐标分别为（?, ?） , （?爲?） ,（ ?假设节点D的坐标?）,以及它们到未知节点D的距离分别为？?,为（X, y）。那么，有下列公式：v(? ?)2 + (? ?)2v(? ?)2 + (? ?科2 = ?v(? ?)2 + (? ?5)2 = ?由式（1）、式、式可得未知节点D的坐标为:2（© -攵2（儿-儿F20& - 亿）2（7i -儿）丿3.2基于移动锚节点的定位算法2 . . 3. 2 .2 _r- -

15、一 -a2.22. J 2,2一九+几一儿+心一%丿-1/22 ,32 , n 2 r兀一兀+儿一儿+N芒一£2目前移动锚节点定位算法一般包括以下两类：第一类是同时采用移动锚节点和静态锚节点协作来完成未知节点的定位过程； 另一类则是只通过移动锚节点来获得未知节点的坐标。利用移动锚节点替代传统的静态锚节点不但降低了无线传感器网络定位技术实现的成本，而且提高了定位精度和定位覆盖率。3.2.1 基于移动锚节点的距离相关定位算法基于测距的移动锚节点发送的信标信号中包含距离信息， 然后未知节点通过 接受到的距离信息通过特定的计算方法实现定位。典型算法： MBAL 算法MBAL(mobile b

16、eacon assisted localization scheme) 定位方法是典型的将移动锚节点定位算法与静态锚节点定位算法相结合的一种方法， 移动锚节点在移动的同时更新其坐标并周期的广播自身的位置信息。未知节点通过 RSSI 测距方法获得与锚节点之间的距离，当接收到 3 个以上不共线的虚拟锚节点信息包 时，就可以使用三边测量法来计算自身的位置。 未知节点定位完成以后， 就转换 成为其他未知节点提供坐标信息的静态锚节点。 MBAL 算法假设锚节点始终能 知道自身的位置，未知节点可以利用 3 个及更多的来自移动锚节点或静态锚节 点的数据包计算出自身的位置。 MBAL 定位可分为以下 3 个阶

17、段： 锚节点初始移动阶段 ：为了保证在传感器网络中存在交叉区域， 将移动锚节点的 初始位置设置在网络的中心附近。如图 3.16 所示，交叉区域是一个边长为 R的等边三角形。锚节点运动结束后，节点移动的距离长度为2R，参考节点的数目是 3 个。经过这个步骤，处于交叉区域的未知节点能够计算出自身位置，从 而转化为广播自身位置数据包的静态锚节点，进行递增式定位。锚节点初始运动路径(The initial path of a mobile beacon )未知节点定位阶段：静态参考节点为其他未知节点提供包括自身位置的数据包, 使更多的节点被定位，从而递归的产生更多的静态参考节点。 三边测量法至少需 要

18、3个锚节点的位置信息，但 MBAL使用距离检查技术（The range check technique ）来计算接收到两个数据包的节点位置。如下图所示，一个未知节点 接收到来自参考节点 A和B的两个数据包，估计自身到 A和B的距离，从而可以得到两个可能的位置 1P和2P。图中灰色点是参考节点 A和B的邻居节点，也是未知节点的两跳节点。这个未知节点只有两个邻居节点， 不能成为 两跳节点的邻居节点，而其中一个可能的位置2P是在节点C的范围内被定位。因此，1P是未知节点唯一的位置。参海节点节点可能ea距离检查技术(The range check technique )锚节点移动路径决策阶段 ：经过前

19、两个步骤之后， 有些未知节点接收到的位置信 息仍然少于 3 个，这些节点被称为请求节点，向移动锚节点请求更多的位置信 息。根据请求节点已接收到的数据包个数，可将这些节点分为 0- 型（已接收到 参考节点信息的个数为 0）、1- 型（已接收到参考节点信息的个数为 1）和 2-型（已接收到参考节点信息的个数为 2）。根据不同类型未知节点的请求，移动锚节点选择合适的路径来完成整个网络的定位。 MBAL 算法提出的路径规划方 法比随机路径规划的定位效果好， 但它在尽可能减小锚节点移动路径的同时， 也 降低了定位的精度。对于小规模传感器网络， MBAL 算法通过上述的路径规划方法缩短了移动 锚节点运动的

20、路径， 减小了锚节点能耗； 采用递增式的定位算法， 降低了定位实 现的成本； 使用距离检查技术， 减少网络中不能定位的节点。 但对于大规模的网 络， MBAL 算法会产生严重的累积误差且全网定位的执行周期较长；网络中节 点分布均匀且密度较大时， 采用递增式定位能够满足所有未知节点都被定位的需 求，不需要再使用距离检查技术。因此， MBAL 算法不适用于大规模无线传感 器网络定位。3.2.2 基于移动锚节点的距离无关定位算法距离无关的移动锚节点定位算法，无需测距。典型算法： LMAP 算法LMAP 算法是根据“圆的任何一条弦的垂直平分线都经过该圆的圆心”这 个理论提出的， 它是一种非基于测距的算

21、法， 在定位的过程中不需要任何距离或 者角度的信息。 LMAP 定位原理如图 3.18 所示，圆心是未知节点所在的位置，圆的半径是未知节点能够与锚节点之间进行通信的最大距离，移动锚节点经过弦 的中点。未知节点接收到 3个虚拟参考节点的信息后，就在以未知节点为圆心的圆中产生了两条弦。如上图所示，? ? ?身分别表示3个虚拟锚节点，假设它们的坐标为（?），（ ? ?和（？?，?），未知节点S的坐标设为（? ? 。?和?是3个锚节点产生的两条弦，？?和?分别是两条弦的垂直平分线，通过数学运算，可以得到以下的方程组:?：?+?+?= ?= ?其中，?= ?- ?，?= ?- ?= ?- ?，?= ?- ?+?2?+?2 ?+?>?=(?- ?r+( ?- ? F?+?>?*?+?=(?>?