定位算法学习总结一、无线传感器定位技术分类目前定位技术广泛地应用到各个领域,而且出现了很多定位算法,常用的定位方法有:到达角(AngelofArrival,AOA)定位、到达时间(TimeofArrival,TOA)定位、到达时间差(TimeDifferenceofArrival,TDOA)定位以及AOA/TOA、AOA/TDOA等混合定位的方法。选择哪种定位方法要根据定位精度、硬件条件等因素来确定,但是最终目的是要用优化的方法得到满意的定位精度。在没有时间同步信号时,往往采用TDOA定位方法,TDOA定位法可消除对移动台时间基准的依赖性,因而可以降低成本并仍然保证较高的定位精度,但是需要有较好的延时估计方法,才能保证较高的时延估计精度。(1)基于测距的定位技术基于测距的定位方法依靠测量相邻节点之间的距离或者方向信息。现在有很多成熟的算法被用于基于测距的定位。例如TOA算法通过信号传播时间获取距离,TDOA算法利用接收从多个节点发出信号的时间差估测位置,而AOA算法则通过为每个节点设置天线阵列来测量节点间的相对方向角度值。(2)无需测距的定位技术无需测距的定位方法不要求距离信息,只依靠有关待定位传感器与种子节点之间连通性的测量数据。这种定位方法对硬件要求低,但是测量的准确度容易被节点的密度和网络条件所影响,因此不能被对精度要求高的基于WSN的应用采用。二、三边定位和多变定位(1)信号强度(RSS,ReceivedSignalStrength)通过信号在传播中的衰减来估计节点之间的距离,无线信道的数学模型。尽管这种方法易于实施,但却面临很多挑战。首先信道由于受到信道噪声、多径衰减(Multi-pathFading)和非视距阻挡(Non-of-SightBlockage)的影响[1],具有时变特性,严重偏离上诉模型;其次衰减率会随外界环境的不同而发生相应改变。根据接收到的信号估计出的距离d将有很大误差。(2)信号传播时间/时间差往返时间(TOA/TDOA/RTOF)a)到达时间(TOA,TimeOfArrival)使用发射机到接收机之间往返的时间来计算收发机之间的距离,要求发射机和接收机严格时间同步。b)往返传播时间(RTOF,Roundtrip-Time-Of-Flight)发射机和接收机可属于不同的时钟域,基于信号传播时间的测距精度由时间差的测量精度决定。时间差的精度由参考时钟决定。c)到达时间差(TDOA,TimeDifferenceOfArrival)使用两种不同传播速度的信号,向同一个方向发送即可。图1示意图(3)接收信号相位差(PDOA,phasedifferenceofArrival)通过测量相位差,求出信号往返的传播时间[2],计算出往返距离,其中,是信号频率,是信号的波长,是发送信号和反射信号的相位差,由上式可知d的范围是[0,]。不同的距离如果相差倍,则测量获得的相位相同。通过相位差的方式测量距离,需要知道距离d范围,才能够确定出n的值,估算出距离。(4)近场电磁测距(NFER,NearFieldEMRanging)利用近场与磁场的相位差来测量距离,射频信号包括电场和磁场两部分。例如,当目标距离接近发射天线时相位相差90o;在距离相差1/2波长时,相位差接近0。由此可以通过电场与磁场的相位差,估计到天线的距离。近场电磁测距方法的测距范围在0.05之间,最佳测量范围0.08之间。该方法由于距离限制,现有的定位系统很少采用。三、TDOA算法研究1.基于测距的定位技术算法对比分析算法种类RSSTOARTOFTDOAPDOANFER条件需求信号衰减量发射和接收机之间的往返时间往返传播时间目标发射信号到达各个节点的时间差接收信号相位差相位差与距离的准确关系优点易于实施,对硬件要求较低发射机和接收机可属于不同的时钟域对待测节点没有时间同步要求缺点算法模型受环境影响大,精度较低要求发射机和接收机严格时间同步使用射频信号时要求高精度时钟需要首先知道往返距离范围对测量距离有限制2.TDOA算法特性(1)对目标时间基准无依赖性选用TDOA算法对待测节点没有时间同步要求。在无线传感器网络中,实现节点之间的时间同步较为困难。而且考虑在实际应用中,一般情况下,我们无法获取待测目标的准确时间信息。TDOA算法只需获取目标发射信号到达各个节点的时间差。根据一个时间差信息即可将目标定位在一个双曲面上(如图3所示),那么假如有三个时间差信息,则三个双曲面可交与一点,这一点即为目标位置。由此消除了对目标时间基准的依赖性[3],应用场合得以拓展。图3TDOA双曲面模型(2)适合水下环境要求对于水声定位系统,如果采用电磁波传递信息,则在水下将很快衰减。因此只能够使用声波进行通信。由上述分析可知,TDOA算法必须依靠高精度的参考时钟来保证其精确度。对于低成本、低带宽、无参考时钟的无线传感器网络来说,获得高精度的时钟本身就是一个挑战。如果用射频信号进行测距,的时钟精度就有300m的误差。但使用超声波等低传播速率信号进行测距时,1ms的时钟精度便可达到30cm的精度。可见,用超声波信号实现的TDOA算法不仅可满足水下环境的要求,而且能保证足够的定位精度。3.TDOA算法分析在对目标信源进行定位时,因为无法获得时间同步信号而没有时间基准,常采用TDOA技术得到时延估计值,进而得到目标信源到两个基站之间的距离差,多个TDOA测量值就可以构成一组关于目标信源位置的双曲线方程组,求解该方程组就可以得到目标信源的估计位置[4]。图4TDOA算法模型设目标节点的坐标E为E=(x,y,z),其余N+1个已知位置的节点为P0,P1,...,Pm,...,PN,它们的坐标分别为Pm=(xm,ym,zm),0≤m≤N。则目标与任一节点的距离为(1)为了简化计算可设主节点的坐标为(0,0,0),那么为(2)距离是水中声速v与传播时间的乘积,TDOA算法需要波面到达每个副节点P1,...,Pm,...,PN与到达主节点P0的时间差值,即v=v-v(3)v=-(4)图5为了更好地说明这一过程,如图5所示。P0和P1分别是节点P0,P1接收到E的发射波形,可见P1接收到信号要比P0延迟5ms左右,相当于的值。对P0和P1的波形求互相关函数可得cross-correlation波形。其峰值时刻对应的时间值即为时间差。上述仿真分析针对的是连续时间信号,对于离散时间信号可根据式(f*g)[n]进行计算。1)非线性定位算法通过以上分析知要得到目标的坐标值,至少需要三个时间差信息,因此至少需要P0,P1,P2,P3四个已知位置的节点[5]。设目标到达主站P0(0,0,0)与各副站的距离差为,则化简可得(5)(6)其中:,。对于3个距离差测量值可以组成如下非线性方程组(7)先把r作为常量,求出x,y,z关于r的代数式,然后代入中解出r的值。r的值确定后,x、y、z的值便可确定。由整个计算过程可知这种非线性算法得到的解可能不唯一,需要解模糊。此外计算量过大也是其缺点之一。针对上述非线性算法存在的问题,我们在设计中采用基于最小二乘法的牛顿迭代定位算法对数据进行处理。最小二乘法定位精度不是很高,但可对目标信源的位置作初始估计。有了这一估计值,再使用牛顿迭代法对初始结果进行修正,则不但可以提高定位精度,而且可以加快计算速度,节省时间。①最小二乘法估计初始位置由(8)可得矩阵形式的线性方程组HX=L(8)其中H=,X=,L=要求解X,必须使残差r=HX—L的平方和最小,即f(x)=(9)对上面的方程求导并令其为零,得(10)若为非奇异阵,则得到(11)的最小二乘法估计为(11)②牛顿迭代法修正(1)将用最小二乘法解得的信源位置X设为初始值,代入牛顿迭代法的关系式[3],求解迭代后的位置为(k=0,1,2,…,n-1);(2)分别将和代入n-4个冗余函数表达式(i=5,…,n),利用最优化方法,(i=5,…,n),为根据测距精度要求给定的值,,为给定的精度要求;(3)判断是否满足条件或,如果满足其中的一个条件,则迭代过程结束,输出,否则将结果作为初始值,即,继续上面的步骤,直到满足条件为止。2)线性定位算法以上的非线性算法采用一个主节点和三个副节点,可测得三个时间差信息,即三个方程。虽然这样可用最少的节点数目完成定位任务,节约成本,但是有着需解模糊、计算量大、定位实时性较低等缺点。此时如果增加一个副节点P4,则线性方程组变为(12)此时可把r作为求解变量,直接求解四元一次线性方程组。由(13)可得矩阵形式的线性方程组HX=L(13)其中H=,X=,L=可得X=H\L,由此可得出目标信源的位置。由求解过程可以看出,线性定位算法相比非线性算法解法简单,无模糊,求解精度高。该方法就是常用的五元十字TDOA定位算法。4.仿真与分析基于上述算法分析,我们对基于最小二乘法的牛顿迭代算法和五元十字定位算法进行了Matlab仿真实验。4.1仿真实验(1)基于最小二乘法的牛顿迭代算法图6仿真实验传感器布阵图如图6所示,主节点坐标为=[0,0,0],三个副节点坐标分别为=[2,0,1]、=[0,2,0]、=[2,2,0]。假设待测目标S的位置是S=[3,4,5]。计算可得H=,L=最小二乘法估计=,可见最小二乘法的估计值与目标的实际位置相差较大。但通过牛顿迭代可提高精确度。下面给出牛顿迭代法的部分Matlab代码:%牛顿迭代法解非线性方程组%输入参数:迭代初值,迭代方程,精度要求function[h]=Newton(start_newton,F_newton,p_newton)F_temp=start_newton;temp=[0;0;0];whilesum(abs(temp-F_temp))p_newtontemp=F_temp;F_temp=F_temp-subs(F_newton,{'x','y','z'},{F_temp(1),F_temp(2),F_temp(3)});endh=F_temp;将最小二乘法的估计值代入,通过迭代后可得最终定位结果S’=[2.9998,3.9998,4.9997],S与S’的误差间距为3.9123e-004。(2)五元十字定位算法图7仿真实验传感器布阵图如图7所示,主节点坐标为=[0,0,0],四个副节点坐标分别为=[0,2,1]、=[-2,0,0]、=[0,-2,0]、=[2,0,0]。仍假设待测目标S的位置是S=[3,4,5]。计算可得H=,L=所以X=H\L=,可得最终定位结果S’=[2.9997,3.9993,4.9999],计算可得S与S’的误差间距为7.6811e-004。(3)算法性能比较通过多组上述算法测试实验可列出以下性能参数比较:定位算法传感器节点数目(N)相对误差(X)相对误差(Y)相对误差(Z)程序执行时间(T)/s均方根误差(RMSE)最小二乘法47.84%7.76%8.75%0.5630.586基于最小二乘的牛顿迭代算法46.67e-0055.00e-0056.00e-0055.4323.91e-004五元十字定位算法51.00e-0041.75e-0042.00e-0050.4987.68e-004注:程序执行时间在Intel(R)Core(TM)2DuoCPUT6400@2.00GHz处理器下测得,不同硬件平台结果可能不同。4.2实验结论在仿真实验中我们分别对采用四个传感器节点的非线性TDOA算法和采用五个传感器节点的线性TDOA定位算法在Matlab环境下进行了测试。由实验结果可知五元十字定位法和经牛顿迭代法修正的最小二乘算法可达到同等高的精度数量级。对比两者的程序执行时间可知五元十字定位法因为计算量较小运行快,定位实时性高,但所需节点至少为五个。因此在水声换能器成本较高且对定位实时性要求不高时可采用基于最小二乘的牛顿定位算法。四、参考文献[1]ZhongwenGuo.PerpendicularIntersection:LocatingWirelessSensorswithMobileBeacon.OceanUniversityofC