定位算法概述

1、定位算法概述非距离式定位 中心算法中心算法: : 传感器网络中包含参考节点和普通节点传感器网络中包含参考节点和普通节点. . 参考节点的位参考节点的位置或坐标都已知为置或坐标都已知为( Xi , Yi ) , ( Xi , Yi ) , 普通节点利用接收到普通节点利用接收到的参考节点的位置或坐标来估算自己的位置或坐标的参考节点的位置或坐标来估算自己的位置或坐标: :( Xest , Yest ) = ( X1 + X2 + + Xk ) /k , ( Y1 + Y2 + + Yk ) / k .非距离式定位APIT(approximation point-in-triangulation te

2、st )算法 对普通节点在能通信到的所有参考节点中选择对普通节点在能通信到的所有参考节点中选择3 3个个, ,然后然后测试是否在由这测试是否在由这3 3 个参考节点所组成的三角形区域中个参考节点所组成的三角形区域中, ,即即PITPIT检测检测; ;改变参考节点组合再进行测试直到所有的组改变参考节点组合再进行测试直到所有的组合被测试或达到所需的精度合被测试或达到所需的精度, ,这些三角形会形成一个重这些三角形会形成一个重叠区域叠区域, ,计算该区域的中心即为节点的位置计算该区域的中心即为节点的位置.非距离式定位 算法的关键在于算法的关键在于PIT 检测和区域的融合检测和区域的融合: PIT 检

3、测判断一点是否在由另外三点组成的三角形区域内检测判断一点是否在由另外三点组成的三角形区域内,若点若点M 在区域内在区域内,则则M 沿任一个方向移动都会靠近或偏离沿任一个方向移动都会靠近或偏离至少一个顶点至少一个顶点;若若M 在区域外在区域外,则至少存在一个方向则至少存在一个方向, 当当M 沿着这个方向移动时会同时靠近或偏离所有的顶点沿着这个方向移动时会同时靠近或偏离所有的顶点.在实在实际定位时际定位时,不可能让节点不可能让节点M 移动移动, 这就需要这就需要PIT 的逼近方法的逼近方法APIT. APIT 是利用是利用M 临近的节点代替临近的节点代替M的移动进行计算的移动进行计算非距离式定位

4、DV-Hop算法由算法由3步实现步实现: ( 1)锚节点根据距离矢量路由协议在整个网络广播其自身锚节点根据距离矢量路由协议在整个网络广播其自身位置和跳数的信息包位置和跳数的信息包; (2)锚节点根据获得的其它锚节点位置和相隔跳距来计算锚节点根据获得的其它锚节点位置和相隔跳距来计算网络平均每跳距离网络平均每跳距离,然后将其作为一个校正值泛洪广播至然后将其作为一个校正值泛洪广播至网络中网络中; (3)未知节点根据接收到的校正值和跳数来计算与锚节点未知节点根据接收到的校正值和跳数来计算与锚节点的距离的距离,当获得与当获得与3个或更多锚节点距离后就通过三边测量个或更多锚节点距离后就通过三边测量法来确定

5、自身位置。法来确定自身位置。非距离式定位移动信标节点定位算法移动信标节点定位算法基本思想是：基本思想是： 多个信标在监控区域内移动。未知节点选择其接收到的信多个信标在监控区域内移动。未知节点选择其接收到的信号强度相等的号强度相等的3个信标发射点个信标发射点,认为这三点在以未知节点为认为这三点在以未知节点为圆心的同一个圆上圆心的同一个圆上,然后然后,利用几何方法求解未知节点的位利用几何方法求解未知节点的位置。置。基于距离的定位测距机制测距机制1)接收信号强度测距机制接收信号强度测距机制( received signal strength indicator, RSSI)基本思想：利用已知的发射点

6、信号强度、接收节点接收基本思想：利用已知的发射点信号强度、接收节点接收到的信号强度到的信号强度,计算出信号的传播损耗计算出信号的传播损耗,利用理论或经验信利用理论或经验信道模型将传播损耗转换为距离来测量距离。道模型将传播损耗转换为距离来测量距离。基于距离的定位 2)信号传输时间信号传输时间( time of arrival , TOA)测距测距: 基本思想：根据信号基本思想：根据信号(RF,声音或红外线声音或红外线)的传播时间来计算的传播时间来计算节点间的距离节点间的距离,通常采用声音或者无线射频信号。通常采用声音或者无线射频信号。基于距离的定位 3)到达时间差到达时间差( time diff

7、erence on arrival , TDOA)测距测距: 基本思想：基本思想： 发射节点同时发射发射节点同时发射2种不同传播速度的无线信号种不同传播速度的无线信号,接收节点接收节点根据根据2种不同信号到达的时间差和已知的种不同信号到达的时间差和已知的2种信号的速率计种信号的速率计算算2个节点间的距离。常采用超声波信号与无线射频个节点间的距离。常采用超声波信号与无线射频 信号。信号。基于距离的定位 4)4)信号到达角度信号到达角度( angle of arrival,AOA)( angle of arrival,AOA)测距测距: : 基本思想是接收节点通过天线阵列或者多个超声波接收机基本思

8、想是接收节点通过天线阵列或者多个超声波接收机感知发射节点信号的到达方向感知发射节点信号的到达方向, ,计算接收节点和发射节点计算接收节点和发射节点之间的相对方位或角度之间的相对方位或角度, ,再通过三角测量法计算节点的位再通过三角测量法计算节点的位置。置。节点定位方法 a a. . 三边测量原理三边测量原理. . 三边测量原理是根据三边测量原理是根据3 3 个已知坐标的个已知坐标的节点到未知节点的距离来确定节点坐标节点到未知节点的距离来确定节点坐标. . 已知已知A , B A , B 和和C C 3 3 个节点的坐标分别为个节点的坐标分别为( xa ,ya ) , ( xb , yb) (

9、xa ,ya ) , ( xb , yb) 和和( xc , yc ) , ( xc , yc ) , 它们到未知节点它们到未知节点D D 的距离分别为的距离分别为d a , db d a , db 和和dc ,dc ,假设节点假设节点D D 的坐标为的坐标为( x ,y) ,( x ,y) ,则通过计算可以得则通过计算可以得到到12222222222222()2*2()2acacacaccabcbcbcbccbxxyyxxxyyddxxyyyxxyydd BACdadbdcD基于距离的定位 b.b.三角测量原理三角测量原理. . 三角测量原理三角测量原理是根据是根据3 3 个已知坐标的节点到

10、未个已知坐标的节点到未知节点的相对角度来确定节点坐知节点的相对角度来确定节点坐标的标的. . 已知已知A , B A , B 和和C C 3 3 个节点个节点的坐标分别为的坐标分别为( xa , ya) , ( xa , ya) , ( xb , yb ) ( xb , yb ) 和和( xc , yc ) , ( xc , yc ) , 假设节点假设节点D D 的坐标为的坐标为( x , y) . ( x , y) . 对于节点对于节点A , C A , C 和和D , D , 如果弧段如果弧段A CA C在在A B C A B C 内内, ,那么能够唯一那么能够唯一确 定 一 个 圆确 定

11、 一 个 圆, , 并 存 在 下并 存 在 下 列公式列公式, ,2211122111222211()()()()()()22cosoaoaococacacxxyyrxxyyrxxyyrr式中式中: r1为圆半径为圆半径;O1 ( xO1 , yO1 ) 为圆心为圆心;为圆心角为圆心角A O1 C.O1O3O2ABCCD 移动节点的定位算法：移动节点的定位算法： 基本思想是用移动机器人投放节点基本思想是用移动机器人投放节点, ,每次投放一个节点并每次投放一个节点并对该节点进行定位对该节点进行定位. . 在投放节点前在投放节点前, ,需要设定一个坐标系需要设定一个坐标系, ,将三个静止的参考节

12、点分别标定为将三个静止的参考节点分别标定为(0 ,0) , (0 ,l) (0 ,0) , (0 ,l) 和和(l ,0) ,(l ,0) ,投放的第一个节点通过测量与这三个参考节点的投放的第一个节点通过测量与这三个参考节点的距离来确定自己的坐标距离来确定自己的坐标, ,然后变为参考节点然后变为参考节点, ,作为后续节点作为后续节点定位的参照定位的参照. . 这种算法只适用于某些特定的场合这种算法只适用于某些特定的场合, ,要求投要求投放节点后放节点后, ,节点的位置不能改变节点的位置不能改变, ,只能进行一次定位只能进行一次定位. .基于距离的定位 MBAL(mobile beacon-as

13、sisted localization scheme)MBAL(mobile beacon-assisted localization scheme)定定位方法位方法, , 基本思想是利用一个移动的节点对整个网络中的节点进行基本思想是利用一个移动的节点对整个网络中的节点进行定位定位. . 移动节点随时知道自己的坐标或位置移动节点随时知道自己的坐标或位置, ,在移动过程在移动过程中中, ,发送位置信息发送位置信息, ,周围的节点测量与移动节点不同位置的周围的节点测量与移动节点不同位置的距离距离. . 当周围节点测量到与移动节点的三个或三个以上的当周围节点测量到与移动节点的三个或三个以上的位置信息

14、时位置信息时, ,利用三边定位原理确定自己的位置利用三边定位原理确定自己的位置, ,当节点确当节点确定自己位置时定自己位置时, ,变为参考节点变为参考节点. . Spotlight Spotlight 定位方法定位方法: : Spotlight Spotlight 定位系统的基本思想是在传感器节点部署的区定位系统的基本思想是在传感器节点部署的区域产生可控信号域产生可控信号, ,传感器节点利用自身感应到信号的时间传感器节点利用自身感应到信号的时间和信号的时空属性来获得自身的位置。和信号的时空属性来获得自身的位置。SpotlightSpotlight定位系定位系统利用统利用3 3个函数个函数, ,

15、分分4 4步来完成未知节点的定位。步来完成未知节点的定位。产生事件接收并记录事情 (1) Spotlight(1) Spotlight设备在节设备在节点部署的点部署的A A区域周期性广区域周期性广播事件函数播事件函数E ( t) ;E ( t) ; (2)(2)在事件广播期间在事件广播期间, ,传感传感器节点记录检测到的事件器节点记录检测到的事件时间序列时间序列Ti = ti1 , Ti = ti1 , ti2 , ti2 , , tin ;, tin ; (3)(3)事件广播之后事件广播之后, ,各传感各传感器节点发送自身的检测时器节点发送自身的检测时间序列到间序列到SpotlightSpo

16、tlight设备设备; ; (4) Spotlight(4) Spotlight设备使用设备使用时间序列时间序列Ti Ti 和已知的和已知的E E ( t)( t)函数来估计节点函数来估计节点i i的的位置。位置。 激光定位系统Lighthouse Location System Lighthouse定位系统的基站由定位系统的基站由3个相互垂直的灯塔个相互垂直的灯塔( lighthouse)组成组成,每个灯塔发射两条平行的激光束每个灯塔发射两条平行的激光束(带宽带宽已知为已知为b) ,并以恒定速率绕轴旋转。如图并以恒定速率绕轴旋转。如图2所示。所示。 基站通过下行链路向节点广播。当节点第一次观

17、测到激光基站通过下行链路向节点广播。当节点第一次观测到激光时记录下时间时记录下时间t1 ;在在t1 后后,节点观测不到激光时记录下时间节点观测不到激光时记录下时间t2 ;当又可观测到激光时记录下时间当又可观测到激光时记录下时间t3。据此计算出节点。据此计算出节点可观测到激光的时间间隔可观测到激光的时间间隔tbeam = t2 - t1 和灯塔旋转一周所需时间和灯塔旋转一周所需时间tturn = t3 - t1。然后节点使用公。然后节点使用公式式(1)计算自身与灯塔旋转轴的距离。计算自身与灯塔旋转轴的距离。12sin(/ 2)2sin( */)teamturmbbdtt通过上述方法通过上述方法,

18、 dust节点可获得与相互垂直的节点可获得与相互垂直的3个灯塔轴个灯塔轴的距离的距离,然后以基站为原点确定自身的坐标位置。然后以基站为原点确定自身的坐标位置。ab激光发生器激光发生器d 基于机器学习的传感器定位算法 其基本思想是在一个 0,D*0,D二维区域内部署 N个传感器节点 , 其中存在k个信标节点 (kN)。而且每个信标节点之间可以互相通信。 每个节点的真实坐标位置为 表示从 到 最短路径的跳数。12,NS SS 1iSik ( (), ()iix Sy S(,)ijh S SjSiS每一个传感器节点 用一个向量表示支持向量机的训练数据是信标节点的集合。用径向基函数定义一个核函数， 1,1iiiSikifSc l 22(,)ijssijK SSe12(,), (,), (,)iiiiksh S Sh S Sh S SiS*1( )( ,)kKi iihSl K S Sbsi( )1SGiKlgn hS则ifDecision tree m=4 icxi+1cxjcy1jcy 目前研究的各类定位算法都是在综合权衡能耗、成本和精目前研究的各类定位算法都是在综合权衡能耗、成本和精度等因素