定位算法概述

定位算法概述非距离式定位中心算法:传感器网络中包含参考节点和普通节点.参考节点的位置或坐标都已知为(Xi,Yi),普通节点利用接收到的参考节点的位置或坐标来估算自己的位置或坐标:(Xest,Yest)=[(X1+X2+⋯+Xk)/k,(Y1+Y2+⋯+Yk)/k].非距离式定位APIT(approximationpoint-in-triangulationtest)算法对普通节点在能通信到的所有参考节点中选择3个,然后测试是否在由这3个参考节点所组成的三角形区域中,即PIT检测;改变参考节点组合再进行测试直到所有的组合被测试或达到所需的精度,这些三角形会形成一个重叠区域,计算该区域的中心即为节点的位置.非距离式定位•算法的关键在于PIT检测和区域的融合:•PIT检测判断一点是否在由另外三点组成的三角形区域内,若点M在区域内,则M沿任一个方向移动都会靠近或偏离至少一个顶点;若M在区域外,则至少存在一个方向,当M沿着这个方向移动时会同时靠近或偏离所有的顶点.在实际定位时,不可能让节点M移动,这就需要PIT的逼近方法APIT.APIT是利用M临近的节点代替M的移动进行计算非距离式定位•DV-Hop算法由3步实现:•(1)锚节点根据距离矢量路由协议在整个网络广播其自身位置和跳数的信息包;•(2)锚节点根据获得的其它锚节点位置和相隔跳距来计算网络平均每跳距离,然后将其作为一个校正值泛洪广播至网络中;•(3)未知节点根据接收到的校正值和跳数来计算与锚节点的距离,当获得与3个或更多锚节点距离后就通过三边测量法来确定自身位置。非距离式定位移动信标节点定位算法基本思想是：•多个信标在监控区域内移动。未知节点选择其接收到的信号强度相等的3个信标发射点,认为这三点在以未知节点为圆心的同一个圆上,然后,利用几何方法求解未知节点的位置。基于距离的定位测距机制1)接收信号强度测距机制(receivedsignalstrengthindicator,RSSI)基本思想：利用已知的发射点信号强度、接收节点接收到的信号强度,计算出信号的传播损耗,利用理论或经验信道模型将传播损耗转换为距离来测量距离。基于距离的定位•2)信号传输时间(timeofarrival,TOA)测距:基本思想：根据信号(RF,声音或红外线)的传播时间来计算节点间的距离,通常采用声音或者无线射频信号。基于距离的定位•3)到达时间差(timedifferenceonarrival,TDOA)测距:基本思想：发射节点同时发射2种不同传播速度的无线信号,接收节点根据2种不同信号到达的时间差和已知的2种信号的速率计算2个节点间的距离。常采用超声波信号与无线射频信号。基于距离的定位•4)信号到达角度(angleofarrival,AOA)测距:基本思想是接收节点通过天线阵列或者多个超声波接收机感知发射节点信号的到达方向,计算接收节点和发射节点之间的相对方位或角度,再通过三角测量法计算节点的位置。节点定位方法•a.三边测量原理.三边测量原理是根据3个已知坐标的节点到未知节点的距离来确定节点坐标.已知A,B和C3个节点的坐标分别为(xa,ya),(xb,yb)和(xc,yc),它们到未知节点D的距离分别为da,db和dc,假设节点D的坐标为(x,y),则通过计算可以得到12222222222222()2*2()2acacacaccabcbcbcbccbxxyyxxxyyddxxyyyxxyyddBACdadbdcD基于距离的定位•b.三角测量原理.三角测量原理是根据3个已知坐标的节点到未知节点的相对角度来确定节点坐标的.已知A,B和C3个节点的坐标分别为(xa,ya),(xb,yb)和(xc,yc),假设节点D的坐标为(x,y).对于节点A,C和D,如果弧段AC在△ABC内,那么能够唯一确定一个圆,并存在下•列公式,2211122111222211()()()()()()22cosoaoaococacacxxyyrxxyyrxxyyrr式中:r1为圆半径;O1(xO1,yO1)为圆心;α为圆心角∠AO1C.O1O3O2ABCCD•移动节点的定位算法：•基本思想是用移动机器人投放节点,每次投放一个节点并对该节点进行定位.在投放节点前,需要设定一个坐标系,将三个静止的参考节点分别标定为(0,0),(0,l)和(l,0),投放的第一个节点通过测量与这三个参考节点的距离来确定自己的坐标,然后变为参考节点,作为后续节点定位的参照.这种算法只适用于某些特定的场合,要求投放节点后,节点的位置不能改变,只能进行一次定位.基于距离的定位•MBAL(mobilebeacon-assistedlocalizationscheme)定位方法,•基本思想是利用一个移动的节点对整个网络中的节点进行定位.移动节点随时知道自己的坐标或位置,在移动过程中,发送位置信息,周围的节点测量与移动节点不同位置的距离.当周围节点测量到与移动节点的三个或三个以上的位置信息时,利用三边定位原理确定自己的位置,当节点确定自己位置时,变为参考节点.•Spotlight定位方法:•Spotlight定位系统的基本思想是在传感器节点部署的区域产生可控信号,传感器节点利用自身感应到信号的时间和信号的时空属性来获得自身的位置。Spotlight定位系统利用3个函数,分4步来完成未知节点的定位。产生事件接收并记录事情•(1)Spotlight设备在节点部署的A区域周期性广播事件函数E(t);•(2)在事件广播期间,传感器节点记录检测到的事件时间序列Ti={ti1,ti2,⋯,tin};•(3)事件广播之后,各传感器节点发送自身的检测时间序列到Spotlight设备;•(4)Spotlight设备使用时间序列Ti和已知的E(t)函数来估计节点i的位置。•激光定位系统———LighthouseLocationSystem•Lighthouse定位系统的基站由3个相互垂直的灯塔(lighthouse)组成,每个灯塔发射两条平行的激光束(带宽已知为b),并以恒定速率绕轴旋转。如图2所示。•基站通过下行链路向节点广播。当节点第一次观测到激光时记录下时间t1;在t1后,节点观测不到激光时记录下时间t2;当又可观测到激光时记录下时间t3。据此计算出节点可观测到激光的时间间隔tbeam=t2-t1•和灯塔旋转一周所需时间tturn=t3-t1。然后节点使用公式(1)计算自身与灯塔旋转轴的距离。12sin(/2)2sin(*/)teamturmbbdtt通过上述方法,dust节点可获得与相互垂直的3个灯塔轴的距离,然后以基站为原点确定自身的坐标位置。ab激光发生器d•基于机器学习的传感器定位算法•其基本思想是在一个[0,D]*[0,D]二维区域内部署•N个传感器节点,•其中存在k个信标节点(kN)。而且每个信标节点之间可以互相通信。每个节点的真实坐标位置为•表示从到最短路径的跳数。12,,NSSS1iSik((),())iixSyS(,)ijhSSjSiS每一个传感器节点用一个向量表示支持向量机的训练数据是信标节点的集合。用径向基函数定义一个核函数，1,1iiiSikifScl22(,)ijssijKSSe12(,),(,),,(,)iiiikshSShSShSSiS**1()(,)kKiiihSlKSSbsi(())1SGiKlgnhS则ifDecisiontreem=4icxi+1cxjcy1jcy•目前研究的各类定位算法都是在综合权衡能耗、成本和精度等因素的基础上提出来的。其计算量、精度等方面也存在较大差别,适合的应用范围也各不相同.因此,无线传感器网络中定位算法的应用需要针对不同的场合,综合考虑节点的规模、成本以及系统对定位精度的要求来设计和选择。同时,对于具有分布式、低复杂性、高精度、通用性等特点的无线传感器网络定位方法还有待进一步深入研究谢谢