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

1、无线传感网络定位算法目录一、常用定位技术11.1 GPS与A-GPS定位11.2 基站定位（cell ID定位）11.3 Wifi AP定位21.4 FRID、二维码定位2二、定位算法研究的目的和意义2三、WSN定位算法分析23.1 基于锚节点的定位算法23.1.1 距离相关定位算法23.1.2 距离无关定位算法33.2 基于移动锚节点的定位算法43.2.1 基于移动锚节点的距离相关定位算法43.2.2 基于移动锚节点的距离无关定位算法6四、总结6附：组员及分工情况7一、常用定位技术1.1 GPS与A-GPS定位常见的GPS定位的原理可以简单这样理解：由24颗工作卫星组成，使得在全球任何地方、

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

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

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

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

6、进入的区域，或者是敌对区域，甚至有时传感器节点需要通过飞行器抛撒，因此节点的位置通常是随机并且未知的。而传感器节点自身的正确定位是提供监测事件位置信息的前提，没有位置信息的监测消息往往是没有意义的。传感器节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件"，除能报告事件的发生地外，还能进行目标跟踪，实时监视目标路线，预测目标轨迹等；实现对外部目标的定位和追踪。另一方面，了解传感器节点位置信息还可以协助路由，提高路由效率，为网络提供命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置等网络管理。因此，确定事件发生的位置或获取消息的节点位置尤为重要，

7、对传感器网络应用的有效性起着关键的作用。而全球定位系统是目前使用最广泛最成熟的定位系统，通过卫星的授时和测距对用户节点进行定位，具有精度高、实时性好、抗干扰能力强等优点，但是定位适应于无遮挡的室外环境，用户节点通常能耗高且体积大，成本也比较高，需要固定的基础设施等。人工部署和为所有网络节点安装GPS接收器都会受到成本、功耗、扩展性等问题的限制，甚至在某些场合可能根本无法实现，这使得它不适用于低成本自组织的传感器网络，因此必须采用一定的机制与算法实现WSN的自身定位。 随着计算机技术、微电子技术和通信技术的进步，传感器已朝着集成化、微型化、智能化和低能耗的方向快速发展，使其能够在较小体积内集成信

8、息采集、数据处理和信息的传输等多种功能，这为无线传感网(Wireless Sensor Networks WSN)的产生和发展奠定了基础。无线传感网是由部署在监测区域内大量廉价微型的具有有限数据处理能力和装备有低能耗无线信号收发器的传感器节点通过无线通信方式形成的一个多跳自组织网络，其目的是利用网络节点协作地感知和采集网络覆盖区域内感兴趣的信息，并发送给观察者。它通过大量随机部署在监测区域的传感器节点来监测和感知周围的物理环境。无线传感网具有布线成本低、监测精度高、系统容错性好、可远程监控以及便于诊断与维护等众多的优点，它的产生解决了传统传感器网络在应用中遇到的安装、维护等方面的种种困难。其在

9、军事、工业、医疗、交通、环保等领域有着广阔的应用前景。如果说互联网改变了人与人之间的信息交流方式，那么，无线传感网的产生将改变人与自然界的交互方式。三、WSN定位算法分析3.1 基于锚节点的定位算法3.1.1 距离相关定位算法距离相关定位算法一般利用一定的测距技术得到节点间距离，再利用三边测量法、三角测量法或极大似然估计法计算出未知节点的位置。常用的测距技术包括接收信号强度(RSSI)技术、信号传输时间(TOA)技术、信号到达时间差(TDOA)技术和信号到达角度(AOA)技术。它们需要一些昂贵的辅助测量设备来测量节点间的距离，且受环境影响较大。如RSSI产生的测量误差较大；TDOA需要节点具有

10、超声波发送与接收功能；AOA容易受到环境影响，功耗较大等。但距离相关定位算法的一个突出优点是定位精度高，因此对定位精度要求比较高的场合都用基于测距的定位算法实现定位。典型算法：接收信号强度指示法（RSSI）通过信号在传播中的衰减来估计节点之间的距离。假设已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为距离。在自由空间中，距发射机d处的天线接收到的信号强度由下面的公式给出：prd=ptGtGr2422L其中，pt为发射机功率，prd是距离d处的接收功率，Gt、Gr分别是发射天线和接收天线的增益，d是距离，单位为米（m），L为与传播无关的系统损耗因子

11、，是波长，单位为米（m）。由公式可知，在自由空间中，接收机功率随发射机与接收机距离的平方衰减。这样，通过测量接收信号的强度，再利用上述公式即可计算出收发节点间的大概距离。3.1.2 距离无关定位算法利用节点间的连通情况来估测自己的位置。其中一部分距离无关算法采用集中式计算模式，用一些优化方法来提高定位精度，但是集中计算方式需要网络中有计算中心支持，且计算中心附近节点通信量大，很快能量耗尽，使整个网络不可用。绝大多数距离无关定位算法采取分布式计算模式，可扩展性好；由于位置估测基于节点间的连通情况，计算简单而且容易实现；计算在节点本地进行，通信量小。因为基于估测距离，距离无关算法定位精度不如距离相

12、关算法好。典型算法：DV-hop算法距离向量跳段( distance vector-hop，DV-Hop)定位机制非常类似于传 统网络中的距离向量路由机制，DV-Hop 算法的定位过程主要分为 3 个阶段：1) 计算未知节点与每个信标节点的最小跳数，锚节点向邻居节点广播自身位置信息的分组，其中，包括跳数字段，初始化为 0。接收节点记录具有到每个锚节点的最小跳数，忽略来自同一个锚节点的较大跳数的分组。然后，将跳数值加 1，并转发给邻居节点。通过这种方法，网络中的所有节点能够记录下到每个锚节点的最小跳数。2) 计算未知节点与锚节点的实际跳段距离每个锚节点根据第一阶段中记录的其它锚节点的位置信息和相

13、距跳数,并利用下式估算平均每跳的实际距离i=xi-xj2+yi-yj2hj式中(xi, yi)，(xj, yj) 为锚节点 i, j 的坐标; hj 为锚节点 i 与 j( i j) 之间的跳段数，然后，锚节点将计算的平均每跳距用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第一个平均每跳距离，并转发给邻居节点。 这个策略确保了绝大多数节点从最近的锚节点接收平均每跳距离值。未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个锚节点的跳段距离。3) 利用三边测量法计算自身位置未知节点利用第二阶段中记录的到各个锚节点的跳段距离，利用三边测量法计算自身位置。 已知 A,B,C 3 个节

14、点的坐标分别为(xa, ya ) , (xb，yb ) ,( xc，yC ),以及它们到未知节点 D 的距离分别为 a，b，c,假设节点 D 的坐标为( x, y) 。那么，有下列公式: x-xa2+y-ya2=a (1) x-xb2+y-yb2=b (2) x-xc2+y-yC2 =c (3) 由式(1) 、式(2) 、式(3)可得未知节点 D 的坐标为:3.2 基于移动锚节点的定位算法目前移动锚节点定位算法一般包括以下两类：第一类是同时采用移动锚节点和静态锚节点协作来完成未知节点的定位过程；另一类则是只通过移动锚节点来获得未知节点的坐标。利用移动锚节点替代传统的静态锚节点不但降低了无线传感

15、器网络定位技术实现的成本，而且提高了定位精度和定位覆盖率。3.2.1 基于移动锚节点的距离相关定位算法基于测距的移动锚节点发送的信标信号中包含距离信息，然后未知节点通过接受到的距离信息通过特定的计算方法实现定位。典型算法：MBAL 算法MBAL(mobile beacon assisted localization scheme)定位方法是典型的将移动锚节点定位算法与静态锚节点定位算法相结合的一种方法，移动锚节点在移动的同时更新其坐标并周期的广播自身的位置信息。未知节点通过 RSSI 测距方法获得与锚节点之间的距离，当接收到 3 个以上不共线的虚拟锚节点信息包时，就可以使用三边测量法来计算自身

16、的位置。未知节点定位完成以后，就转换成为其他未知节点提供坐标信息的静态锚节点。MBAL 算法假设锚节点始终能知道自身的位置，未知节点可以利用 3 个及更多的来自移动锚节点或静态锚节点的数据包计算出自身的位置。MBAL 定位可分为以下 3 个阶段：锚节点初始移动阶段：为了保证在传感器网络中存在交叉区域，将移动锚节点的初始位置设置在网络的中心附近。如图 3.16 所示，交叉区域是一个边长为 R的等边三角形。锚节点运动结束后，节点移动的距离长度为 2R，参考节点的数目是 3 个。经过这个步骤，处于交叉区域的未知节点能够计算出自身位置，从而转化为广播自身位置数据包的静态锚节点，进行递增式定位。锚节点初

17、始运动路径（The initial path of a mobile beacon）未知节点定位阶段：静态参考节点为其他未知节点提供包括自身位置的数据包，使更多的节点被定位，从而递归的产生更多的静态参考节点。三边测量法至少需要 3 个锚节点的位置信息，但 MBAL 使用距离检查技术（The range check technique）来计算接收到两个数据包的节点位置。如下图所示，一个未知节点接收到来自参考节点 A 和 B 的两个数据包，估计自身到 A 和 B 的距离，从而可以得到两个可能的位置1P 和2P 。图中灰色点是参考节点 A 和 B 的邻居节点，也是未知节点的两跳节点。这个未知节点只有

18、两个邻居节点，不能成为两跳节点的邻居节点，而其中一个可能的位置2P 是在节点 C 的范围内被定位。因此，1P 是未知节点唯一的位置。 距离检查技术（The range check technique）锚节点移动路径决策阶段：经过前两个步骤之后，有些未知节点接收到的位置信息仍然少于 3 个，这些节点被称为请求节点，向移动锚节点请求更多的位置信息。根据请求节点已接收到的数据包个数，可将这些节点分为 0-型（已接收到参考节点信息的个数为 0）、1-型（已接收到参考节点信息的个数为 1）和 2-型（已接收到参考节点信息的个数为 2）。根据不同类型未知节点的请求，移动锚节点选择合适的路径来完成整个网络的

19、定位。MBAL 算法提出的路径规划方法比随机路径规划的定位效果好，但它在尽可能减小锚节点移动路径的同时，也降低了定位的精度。对于小规模传感器网络，MBAL 算法通过上述的路径规划方法缩短了移动锚节点运动的路径，减小了锚节点能耗；采用递增式的定位算法，降低了定位实现的成本；使用距离检查技术，减少网络中不能定位的节点。但对于大规模的网络，MBAL 算法会产生严重的累积误差且全网定位的执行周期较长；网络中节点分布均匀且密度较大时，采用递增式定位能够满足所有未知节点都被定位的需求，不需要再使用距离检查技术。因此，MBAL 算法不适用于大规模无线传感器网络定位。 3.2.2 基于移动锚节点的距离无关定位

20、算法距离无关的移动锚节点定位算法，无需测距。典型算法：LMAP 算法LMAP 算法是根据“圆的任何一条弦的垂直平分线都经过该圆的圆心”这个理论提出的，它是一种非基于测距的算法，在定位的过程中不需要任何距离或者角度的信息。LMAP 定位原理如图 3.18 所示，圆心是未知节点所在的位置，圆的半径是未知节点能够与锚节点之间进行通信的最大距离，移动锚节点经过弦的中点。未知节点接收到 3 个虚拟参考节点的信息后，就在以未知节点为圆心的圆中产生了两条弦。如上图所示，Bi，Bj，Bk分别表示3个虚拟锚节点，假设它们的坐标为 （xi，yi），（xj，yj）和（xk，yk），未知节点S的坐标设为（x，y） 。BiBj 和 BjBk 是3个锚节点产生的两条弦，Lij 和 Lik 分别是两条弦的垂直平分线，通过数学运算，可以得到以下的方程组：Lij:aijx+bijy=cijLjk:ajkx+bjky=cjk （1）其中，aij=xi-xj ，bij=yi-yj ajk=xj-xk ，bjk=yj-yk cij=xj-xixj+xi2+（yj-yi）yi+yi2 cjk=xk-xjxk