#1楼主：Hop定位算法和RSSI测距技术的定位系统

文章发表于：2008-06-11 11:24

摘要：针对 DVHop算法在实验环境中存在的问题，加入接收信号强度指示器（RSSI）测距模块辅助定位，对算法进行改进。为了实现定位系统，首先，需要建立当前实验环境的RSSI模型；然后，应用该模型，从锚节点和非锚节点两方面分别控制DVHop定位过程。实验证明：改进后的定位系统在增加少量计算复杂度的情况下，改善了系统的稳定性，提高了定位的精度，可以被应用到无线传感器网络中。
　　关键词：DV—Hop定位算法；定位系统；接收信号强度指示器测距技术
　　中图分类号：TP393.06
　　文献标识码：A
　　
　　0引言
　　目前,根据不同的定位需求和环境实现了多种应用的定位系统。例如:室内环境下的Active Badge[1]和Cricket[2]定位系统、APS分布式定位系统[3]、利用测距技术的Calamari定位系统[4]以及在人工部署环境中的移动GPS定位系统[5]等.不同的定位系统有它们自身的应用环境,开发出一种通用的定位系统几乎是不可能的。无线传感器网络（Wireless Sensor Network, WSN）定位研究必须解决好的问题，就是如何实现一种可靠、稳定的适合一定环境的定位系统。
　　DVHop算法是APS定位系统中的一种，主要依赖于距离矢量路由协议定位。该算法的实现简单，对于硬件支持有限的环境是一个很好的选择。仿真试验表明：在网络平均连通度为10，锚节点（已知节点）比例为10%的各向同性网络中平均定位精度可以达到33%[6]，这对于WSN定位应用是足够的。 但是，该算法还存在很多的缺点，在实际的应用环境中，还需要进行多方面的约束。
　　文献[7]中，提出了一种改善DVHop算法的方法，即在算法中加入两个约束条件：1)信息是最新的； 2)信息中的跳数小于转发节点曾经发出信息的最小跳数。仿真结果表明：经过这样的改进，减少了不良节点的影响，降低了平均定位误差。尽管这样，在实际环境中，DVHop定位系统的实现还存在很多问题：节点定位不稳定、非锚节点（未知节点）定位后位置重叠现象严重等。为了解决好这些问题，本文提出在DVHop算法的基础上，引入接收信号强度指示器(Received Signal Strength Indicator, RSSI)测距技术，对算法的定位过程进行限制，保证定位系统能够稳定、可靠地实现定位，并在实验环境中进行了验证。
　　
　　1　DVHop算法及其改进
　　DVHop算法的核心思想是：用平均每跳距离与未知节点到锚节点跳数的乘积，表示未知节点到锚节点的距离。算法的整个过程是：首先，网络中所有的锚节点，使用距离矢量交换协议，将锚节点的位置信息和跳数信息广播到整个网络中，使网络中的所有的节点获取与锚节点的跳数。其次，锚节点根据正确接收到的跳数信息，计算该锚节点的平均每跳距离，并将其广播到整个网络中。非锚节点利用接收到的跳数信息和平均每跳距离值计算与锚节点的距离。最后，非锚节点执行三边测量实现定位。
　　
　　1.1存在的问题
　　由于节点硬件等原因，使得网络中的节点存在以下一些复杂情况：1)同等发射功率，同样的距离下，不同的节点对产生
本文原文
　　分别为α、β的最小二乘估计。
　　当环境发生改变时，还需要对 α、β进行校正。校正^[10]的方法有很多：统一校正、联合校正和自动校正等。在此，采用统一校正的方法，方法类似于α、 β的求解。实验表明：建立的线性模型经过统一校正后，得到了较好的定位效果，满足了定位需要。
　　
　　1.3改进方案
　　当锚节点接收到网络中其他几个(一般为2个)锚节点位置和跳数信息时，计算自己的平均每跳距离值，然后将该值广播到网络中。
　　为了确保跳数信息更合理，需要对锚节点的计算过程进行限制。根据建立的RSSI测距模型，可以计算出当前发射功率下一个合理的平均每跳距离参考值。当锚节点的平均每跳距离值在模型参考值的一定范围之内，则接受该计算值，否则，接受RSSI模型值。这样，就很好地解决了因为跳数不规律，造成的锚节点平均每跳距离不合理的情形。
　　非锚节点接收到经过调整的平均每跳距离之后，就可以减少不合理的平均每跳距离对定位的影响。尽管如此，非锚节点的定位问题并没有得到完美的解决。非锚节点还必须考虑如何在复杂的网络环境中，借助RSSI测距技术调整获取的跳数值。
　　节点之间是以一定的概率连通的。当节点距离很近时，两个节点连通概率较高，反之，则较小。若简单地认为这两种情况下节点之间的跳数均为1，则远、近两种情形就很难分开。为了更好地解决这个问题，将改变跳数的原始概念：跳数值不仅可以是整数值，还可以是一个小数。这个数可以借助RSSI模型来计算，这样可以大大降低定位误差。
　　
　　图1定位系统的流程
　　DV-Hop算法的原则是：节点只接受网络中最小的跳数值。当定位系统趋于稳定时，节点的跳数都有变小的趋势。实验表明：多数节点容易接收到hops=1的情形，而且，这些节点的误差均比较大。重点改善节点hops=1的情形，有助于大大提高整个定位系统的定位精度。非锚节点收集足够的跳数信息之后，对于跳数大于1的，不作任何处理。当跳数为1时，提取从锚节点获取的RSSI值，使用RSSI模型，当模型值在平均每跳距离值的一定范围内，则不修改跳数值；否则，取模型值和平均每跳距离的比值，该值一般是小数。这样，不仅降低了节点的定位误差，还很好地解决了节点位置重叠现象。一旦通过RSSI模型校正的跳数信息，将不会再发生大的改变，这样定位系统就可以稳定、可靠地运行了。
　　
　　2定位算法的实现
　　算法的实现建立在Mica2平台之上，使用CC1000通讯模块和Atmega128处理芯片，RF模块的通信频段为915～998MHz。利用组件化/模块化的nesC语言，在基于事件驱动的操作系统TinyOS环境中进行开发，分别就锚节点和非锚节点在定位过程中的不同作用实现整个系统。为了更快捷、方便地开发定位系统，可以借助于GDB^[11]调试工具和利用TOSSIM^[11]提供的调试功能。
　　DV-Hop定位系统包括两部分：节点定位系统和PC演示系统。节点定位系统主要由锚节点和非锚节点两大模块组成。节点完成定位后，将节点位置信息和定位过程信息，通过基站节点发送到PC端。PC演示系统是通过Java实现的，它解析发送回来的数据包，显示节点位置和定位过程信息，从而达到对整个定位过程进行监测的目的。

　3实验验证
　　测距实验是在一个2m×4m的室内环境中进行的。随机部署4个节点，每一个节点对之间收集多于10次的数据，4个节点之间收集3组数据。为了减少个别节点的影响，任意选择一个节点为中心，收集与其他3个节点的RSSI数据。收集的RSSI值与实际距离d的分布如图2。
　　图3　5个锚节点(2个未显示出)，13个非锚节点的定位效果
　　在已收集的测距数据基础上，建立一个RSSI模型。当环境发生变化时，进行适当的校正。DV-Hop算法加入该测距模型，对定位过程进行控制。在实验环境中部署15～30个节点实行定位，其中，锚节点为4～6个，其他均为非锚节点。为了能够在较小的实验环境中实现DVHop算法，需要对节点的发射功率进行严格的控制，功率值的设定依赖于实验环境，不能设置得过大，确保更多的节点能够收集到hops>1的情形。定位的效果通过PC端演示系统表现出来。图3是一组定位效果。
　　
　　定位精度以测量值与实际值之间差值的绝对值，再与实际值的比值表示。经过多次试验，对测得的实验结果进行了详细的分析：离基站越近的节点，定位精度值偏大；离基站越远的定位精度值也偏大，但小于离基站近的误差值；总体的平均定位误差较小。实验数据表明：定位系统的平均定位误差大约为32%；当使用去除最大、最小值的均值统计方法时，定位精度可以达到20%以内。
　　
　　4结语
　　文章在DV-Hop算法的基础上，加入了RSSI测距技术，作为对DVHop算法的一种改进方法。下面，将对DV-Hop定位系统改进前后进行比较，如表1。
　　改进后的定位系统不需要任何额外的硬件支持，建立了RSSI模型，在没有增加过多计算量的情况下，却达到了较高的定位精度，保证了系统稳定、可靠。因此，对于精度要求不高，硬件环境不足的定位应用，它是一种实用，有效的选择。
　　
　　RSSI测距技术作为一种辅助定位技术，不仅能解决过多节点跳数为1给定位带来的影响，同时还可以对节点定位过程的每一个细节进行控制，但这样会增加RSSI测距值收集难度和计算复杂度。将来的工作，可以拓展这一技术，并在已有的定位系统框架中，选择适当的定位算法，实现不同应用环境的定位系统。