无线传感器网络质心定位新算法及性能分析

无线传感器网络中TOF测距算法在无线传感器网络<W ire less Sensor Network, WSN >中节点的准确定位对传感器网络应用具有重要的意义.根据定位过程中是否测量实际节点间的距离,可将定位算法划分为与距离无关的定位算法和基于距离的定位算法.与距离无关的如质心算法,凸规划法, DV2Hop算法, APIT算法等,其特点是定位简单, 对节点硬件条件要求低, 但定位精度较差；基于距离的定位算法包括基于信号飞行时间时间< TOF>, 基于到达时间差< TDOA >,基于到达角度<AOA >,基于信号接收强度< RSS的定位算法等等.通常来说,它们对节点硬件要求较高,能耗较大,但具有较高的定位精度.基于测距的方法定位是利用锚节点和未知节点的几何关系来确定未知节点的位置,通过未知节点与三个或三个以上的锚节点距离信息,再根据三边测量法或最大似然估计法可以求得未知节点的位置.所以其关键是准确测量出未知节点与锚节点的距离,本文主要分析TOF的测距方法.1 测距算法基于信号飞行时间的测距算法有：到达时间法< TOA,time of arrival >、双方式法< TWR,tow way ranging >、对称双边双方式法< SDS-TWR,symmetric double-sided two way ranging>等.1.1 TOA算法一对装有无线收发器的节点A、B可以通过电磁波信号从A传播到B 所用的时间来估算.图1为到达时间法的信号传播示意图.设移动节点A在双方约定的时刻发出测距信息,节点A在发送的信号中包含一个同步消息,告知节点B信号发送的时间T0,节点B接受信号的同时接收同步消息,并记录接收时间T1,则信号飞行时间Tp=T1-T0.设电磁波在大气中传播速度为C< 3>,飞行时间为Tp,节点A与B的距离可以估算为S=C TpTOA测距的关键是节点A与节点B时间必须要严格同步.电磁波的速度为3m/s,如果双侧时钟误差为1ns,测量距离误差即为0.3m.如果要求测距误差为1m,则允许双侧的时钟误差不超过3ns.TpA B考虑到当A到达T0时刻时,节点A将包含发送时刻T0的数据包调制到信号波上的时间为T,时间T为一个可测常量,故实际信号飞行时间Tp实=T1-T0-T实际距离S=C Tp实.TOA的误差主要来源于A,B节点时间不同步的误差和B节点晶振频率漂移导致计时时间T1不准的误差.可以选择频率高稳定性高的晶振来减小频率漂移的误差,但相对的能耗和费用就会增加.下面分析频率漂移带来的误差.在节点A,B同步的条件下,假设B的精准时钟脉冲频率为f,实际晶体因为制造工艺,环境温度变化等因素影响下,频率漂移为f,即实际频率为=f+ f其f为一个随时间变化的随机量.则实际测量的时间为=t<1+ >由此可知由于频率漂移使得测量时间与实际时间的误差为t .1.2 TWR算法图2为TWR法的信息交换示意图.节点A发出测距信息,同时启动计时器计时,经过Tp后节点B收到信息,但由于双侧时钟不同步,节点B无法确认Tp.节点B收到信息后立即启动计时,若收到的是本方的测距命令后,则向节点A发出应答信息<信息中包含本方处理时间设为T2>,节点A在<2Tp+T2 >时间后收到应答信息后终止本轮计时.一轮测距所以往返时间为T1T1=2Tp+T2对于节点B,T2为可测常量,因此有飞行时间Tp=ABT1 T2图2TWR测距原理图A与B间的距离S仍然是S=C Tp.可以看出本方法不需要A,B间的时间同步,但是需要A,B分别使用本方的时钟计时,若A,B两侧时钟频率有偏差,将会导致误差,设A,B两侧晶体频率的误差为e A和e B<e=>,可以求得其导致的计时误差为T=e A Tp+<e A -e B >T2由于A,B 间信号飞行时间远小于数据包处理时间,故可以省去上式第一部分得到的误差为T=<e A -e B >T21.3 SDS-TWR 算法为了避免双方式方法中A,B 晶体频率误差引起的计时误差,引入SDS-TWR 算法.如图3所示,A 对B 发起一轮TWR 后,B 再对A 发起一轮TWR,由此可以看出信号飞行四次.T1,T3分别为A,B 所计时的一轮测距所用往返时间,T2,T4为A,B 处理数据的时间,得到的单次飞行时间为 Tp=<T1-T2+T3-T4>图3 SDS-TWR 测距原理图 与TWR 相比,此为两次TWR 法测距,一次由A 发起,另一次由B 发起,由B 发起的测距,引起的计时误差为=<e B -e A >T4所以两次测距的总误差为T 总=<T+>= <e A -e B ><T2-T4>对比TOA 和TWR 可以看出,SDS-TWR 大大降低了由晶体震荡频率的漂移所引起的误差.2测距误差分析T1 A T4 T2BT3对于TOF的测距来说,距离测量误差主要来源于系统误差和非视距与多径效应.系统误差主要是飞行时间的测量误差,如前面所讲的晶振频率漂移带来的误差就属于系统误差.如前面所示,SDS-TWR相比TOA和TWR够很好的克服频率漂移带来的误差.非视距与多径效应带来的误差主要是由于环境障碍物的影响,会使A,B间的信号传播会经过反射,散射,衍射,而不是直线传播,这就导致所测量的A,B间的距离并非直线距离,而是大大超过直线距离.在空旷的室外地区,系统误差是影响测量精度的主要因素,在室内或环境复杂地区,非视距和多径效应是主要因素.目前已有的消除非视距误差的方法分为直接法和间接法.直接法是直接对测量值来处理,来消除误差的.一般是基于先测量出本地区的非视距的统计特性,找出带有误差的测量值与真实值之间的关系,再通过对测量值得预处理,将其恢复真实值.间接法是将消除非视距误差与定位过程相结合,通过设计定位算法,减小非视距在定位过程的影响.一般间接法需要较多基站参与,由多种基站组合得到多种定位结果.然后根据一定的判定准则,舍去由于非视距误差而不准确的结果,或者对所以定位结果加权平均,加权系数与定位准确度有关.3 测距的花费和能耗问题在TOF三种测距方法中,TOA测量移动节点A和主节点B间的距离,只需一次通信即可,而TWR需要发送两次信号,SDS-TWR需发送四次信号,很明显TWR和SDS-TWR测距所耗的能量较多,如果对于移动节点进行实时定位的话,通信频率会大大增加,TWE和SDS-TWR的能耗也会大大增加,故对实时性要求较高的移动节点定位比较适合于用TOA法. TOA测距需要严格要求节点间的时间同步,这就要求选用频率高,稳定性非常好的晶振,而且还要通过不断地通信校正时间误差,这对整个网络来说花费较大.TWR和SDS-TWR不需要节点间的时间同步,相对来说花费较小.。

质心定位算法基本原理
质心定位算法是一种常用的无线定位算法，广泛应用于室内定位、物流追踪等领域。

其基本思想是利用接收信号强度指示（RSSI）来估计设备与基站之间的距离，并通过多个基站的距离估计来计算设备在平面上的位置。

具体来说，质心定位算法需要多个基站（至少三个）设备来提供信号。

设备在每个基站处测量到的信号强度指示（RSSI）可以用来估计设备与基站之间的距离。

常用的距离估计模型有Log-distance path loss（LDPL）模型、Free-space path loss（FSPL）模型等。

通过多个基站提供的距离估计，可以得到设备在平面上的位置估计。

质心定位算法的基本原理是将估计出的位置坐标作为点集的重心。

重心是指在平面上各点坐标的平均值。

设有n个位置点
(x1,y1),(x2,y2),...,(xn,yn)，那么其重心坐标为：
G = ( (x1+x2+...+xn)/n, (y1+y2+...+yn)/n )
质心定位算法的优点是简单易实现，但其缺点也很明显，即距离估计误差较大，不适用于高精度定位。

因此，在实际应用中，常常需要与其他定位算法结合使用。

- 1 -。

随着计算机网络技术、通信技术、嵌入式技术和传感器技术的飞速发展和日益成熟，具有感知能力、计算能力和通信能力的微型传感器及其构成的无线传感器网络WSN(Wireless Sensor Network)引起了人们的极大关注。

这种传感器网络具有低功耗、低成本、自组织的能力，能够自动进行配置和适应环境的变化，具有动态可重构性等特点，能够通过协作实时监测、感知和采集网络，分布区域内的各种环境或监测对象的信息并传送到控制中心，因而被广泛应用于国防军事、国家安全、精细农业、环境监测、智能家居、城市交通以及预防与减灾、人员营救、目标跟踪等方面，适用于在人们无法接近的极端恶劣或特殊环境下监测事件发生的地点[1]。

传感器节点通过飞行器撒播、人工埋置和火箭弹射等方式任意撒落在被监测区域内。

节点的位置信息都是随机的，节点所采集到的数据，若没有位置信息几乎没有应用价值[1]。

所以在无线传感器网络应用中，节点的定位一直是关键问题，同时也是人们研究的热点。

由于传感器节点采用电池供电，节点数量巨大，成本太高，能量有限。

因而利用GPS或其他方式先对网络中的少量节点(锚节点)进行定位，其他大部分节点以锚节点位置为参考，应用各种定位算法实现自身定位。

根据目前出现的定位算法对节点位置估测机制的不同可以分为两大类：基于距离相关的定位算法(Range-Based Localization Schemes)和基于距离无关的定位算法(Range-Free Localization Schemes)。

前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者不需要自己与锚节点之间的距离或角度信息，而是根据网络连通性等信息估算出自己与锚节点间的距离。

基于距离相关的定位算法使得传感器节点造价增高，消耗了有限的电池资源，而且在测量距离和角度的准确性方面需要大量的研究。

基于距离无关的定位算法则不需要知道未知节点到锚节点的距离或者不需要直接测量此距离，在成本和功耗方面比基于测距的方法具有优势[1]。