1、定位技术定位技术4.24.2 4.2 定位技术定位技术4.2.1 4.2.1 传感器网络节点定位问题传感器网络节点定位问题1 1、定位的含义、定位的含义 无线传感器网络定位问题的含义是指自组织的网络通过无线传感器网络定位问题的含义是指自组织的网络通过特定方法提供节点的位置信息。特定方法提供节点的位置信息。 这种自组织网络定位分为节点自身定位和目标定位。这种自组织网络定位分为节点自身定位和目标定位。 位置信息有多种分类方法。位置信息有位置信息有多种分类方法。位置信息有物理位置和符号物理位置和符号位置两大类位置两大类。 位置信息有多种分类方法。位置信息有位置信息有多种分类方法。位置信息有物理位置物
2、理位置和和符号位置符号位置两大类。两大类。 物理位置物理位置指目标在特定坐标系下的位置数值，表指目标在特定坐标系下的位置数值，表示目标的相对或者绝对位置。示目标的相对或者绝对位置。 符号位置符号位置指在目标与一个基站或者多个基站接近指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。目标大致的所在范围。 物理位置和符号位置物理位置和符号位置 根据不同的依据，无线传感器网络的定位方法可以进行如下分根据不同的依据，无线传感器网络的定位方法可以进行如下分类：类： (1) (1) 根据是否依靠测量距离根据是否
3、依靠测量距离，分为基于测距的定位和不需要测，分为基于测距的定位和不需要测距的定位；距的定位； (2) (2) 根据部署的场合不同根据部署的场合不同，分为室内定位和室外定位；，分为室内定位和室外定位； (3) (3) 根据信息收集的方式根据信息收集的方式，网络收集传感器数据称为被动定位，网络收集传感器数据称为被动定位，节点主动发出信息，用于定位称为主动定位。节点主动发出信息，用于定位称为主动定位。1 1、定位的含义、定位的含义2 2、基本术语、基本术语 (1) (1) 锚点锚点：指通过其它方式预先获得位置坐标的节点，：指通过其它方式预先获得位置坐标的节点，有时也称作信标节点。网络中相应的其余节点
4、称为非锚点。有时也称作信标节点。网络中相应的其余节点称为非锚点。 (2) (2) 测距测距：指两个相互通信的节点通过测量方式来估计：指两个相互通信的节点通过测量方式来估计出彼此之间的距离或角度。出彼此之间的距离或角度。 (3) (3) 连接度连接度：包括节点连接度和网络连接度两种含义。：包括节点连接度和网络连接度两种含义。 节点连接度是指节点可探测发现的邻居节点个数。网节点连接度是指节点可探测发现的邻居节点个数。网络连接度是所有节点的邻居数目的平均值，它反映了传感络连接度是所有节点的邻居数目的平均值，它反映了传感器配置的密集程度。器配置的密集程度。 (4) (4) 邻居节点邻居节点：传感器节点
5、通信半径范围以内的所有其：传感器节点通信半径范围以内的所有其它节点，称为该节点的邻居节点。它节点，称为该节点的邻居节点。 (5) (5) 跳数跳数：两个节点之间间隔的跳段总数，称为这两个节：两个节点之间间隔的跳段总数，称为这两个节点间的跳数。点间的跳数。 (6) (6) 基础设施基础设施：协助传感器节点定位的已知自身位置的固：协助传感器节点定位的已知自身位置的固定设备，如卫星、基站等。定设备，如卫星、基站等。 (7) (7) 到达时间到达时间：信号从一个节点传播到另一个节点所需要：信号从一个节点传播到另一个节点所需要的时间，称为信号的到达时间。的时间，称为信号的到达时间。 (8) (8) 到达
6、时间差到达时间差(TDoA)(TDoA)：两种不同传播速度的信号：两种不同传播速度的信号（例如，（例如，电波和声波）电波和声波）从一个节点传播到另一个节点所需要的时间之从一个节点传播到另一个节点所需要的时间之差，称为信号的到达时间差。差，称为信号的到达时间差。 ( (9 9) ) 接收信号强度指示接收信号强度指示(RSSI)(RSSI)：节点接收到无线信号的强：节点接收到无线信号的强度大小，称为接收信号的强度指示。度大小，称为接收信号的强度指示。2 2、基本术语、基本术语 (10) (10) 到达角度到达角度(Angle of Arrival, AoA)(Angle of Arrival, A
7、oA)：节点接收：节点接收到的信号相对于自身轴线的角度，称为信号相对接收节到的信号相对于自身轴线的角度，称为信号相对接收节点的到达角度。点的到达角度。 (11) (11) 视线关系视线关系(Line of Sight, LoS)(Line of Sight, LoS)：如果传感器：如果传感器网络的两个节点之间没有障碍物，能够实现网络的两个节点之间没有障碍物，能够实现直接直接通信，通信，则这两个节点间存在视线关系。则这两个节点间存在视线关系。 (12) (12) 非视线关系非视线关系：传感器网络的两个节点之间存在：传感器网络的两个节点之间存在障碍物，障碍物，影响了它们直接的无线通信影响了它们直接
8、的无线通信。2 2、基本术语、基本术语3 3、定位性能的评价指标、定位性能的评价指标 衡量定位性能有多个指标，除了一般性的衡量定位性能有多个指标，除了一般性的位置精度位置精度指标以外，对于资源受到限制的传感器网络，还有指标以外，对于资源受到限制的传感器网络，还有覆覆盖范围盖范围、刷新速度刷新速度和和功耗等功耗等其它指标。其它指标。 1. 1.位置精度是定位系统最重要的指标，精度越高，位置精度是定位系统最重要的指标，精度越高，则技术要求越严，成本也越高。定位精度指提供的位则技术要求越严，成本也越高。定位精度指提供的位置信息的精确程度，它分为置信息的精确程度，它分为相对精度相对精度和和绝对精度绝对
9、精度。 绝对精度指以长度为单位度量的精度。绝对精度指以长度为单位度量的精度。 相对精度通常以节点之间距离的百分比来定义。相对精度通常以节点之间距离的百分比来定义。 设节点设节点i i的估计坐标与真实坐标在二维情况下的距离差值为的估计坐标与真实坐标在二维情况下的距离差值为d di i，则，则N N个未知位置节点的个未知位置节点的网络平均定位误差为网络平均定位误差为：11NiidN 2. 2.覆盖范围和位置精度是一对矛盾性的指标。覆盖范围和位置精度是一对矛盾性的指标。 3. 3.刷新速度是指提供位置信息的频率。刷新速度是指提供位置信息的频率。（刷新速率越快，动（刷新速率越快，动态节点的位置信息的实
10、时性越好）态节点的位置信息的实时性越好） 定位实时性更多的是体现在对动态目标的位置跟踪。定位实时性更多的是体现在对动态目标的位置跟踪。 4. 4.功耗作为传感器网络设计的一项重要指标，对于定位这项功耗作为传感器网络设计的一项重要指标，对于定位这项服务功能，人们需要计算为此所消耗的能量。服务功能，人们需要计算为此所消耗的能量。 定位性能的评价指标定位性能的评价指标4 4、定位系统的设计要点、定位系统的设计要点 在设计定位系统的时候，要根据预定的性能指标，在众多方在设计定位系统的时候，要根据预定的性能指标，在众多方案之中案之中选择能够满足要求的最优算法选择能够满足要求的最优算法，采取，采取最适宜的
11、技术手段最适宜的技术手段来完成定位系统的实现来完成定位系统的实现。通常设计一个定位系统需要考虑两个。通常设计一个定位系统需要考虑两个主要因素，即定位机制的物理特性和定位算法。主要因素，即定位机制的物理特性和定位算法。4.2.2 4.2.2 基于测距的定位技术基于测距的定位技术 基于测距的定位技术是通过测量节点之间的距离，根据几何基于测距的定位技术是通过测量节点之间的距离，根据几何关系计算出网络节点的位置。解析几何里有多种方法可以确定一关系计算出网络节点的位置。解析几何里有多种方法可以确定一个点的位置。比较常用的方法是多边定位和角度定位。个点的位置。比较常用的方法是多边定位和角度定位。1 1、测
12、距方法、测距方法(1)(1)接收信号强度指示接收信号强度指示(RSSI)(RSSI) RSSI RSSI测距的原理如下：测距的原理如下：接收机通过测量射频信号的能量来接收机通过测量射频信号的能量来确定与发送机的距离确定与发送机的距离。将无线信号的发射功率和接收功率之间。将无线信号的发射功率和接收功率之间的关系表述为下式所示，其中的关系表述为下式所示，其中P PR R是无线信号的接收功率，是无线信号的接收功率，P PT T是是无线信号的发射功率，无线信号的发射功率，r r是收发单元之间的距离，是收发单元之间的距离，n n传播因子，传播因子，传播因子的数值大小取决于无线信号传播的环境。传播因子的数
13、值大小取决于无线信号传播的环境。1 1、测距方法、测距方法(1)(1)接收信号强度指示接收信号强度指示(RSSI)(RSSI)0102030405060708090100-100-90-80-70-60-50-40-30-20-100距 离 （ m）RSSI(dBm)无线信号接收强度指示与信号传播距离之间的关系无线信号接收强度指示与信号传播距离之间的关系(2)(2)到达时间到达时间 (ToA (ToA) 这类方法通过测量传输时间来估算两节点之间距离，精度较好。这类方法通过测量传输时间来估算两节点之间距离，精度较好。ToAToA机制机制是已知信号的传播速度，根据信号的传播时间来计算节点间是已知信
14、号的传播速度，根据信号的传播时间来计算节点间的距离。的距离。ToAToA测距原理的过程示例测距原理的过程示例1 1、测距方法、测距方法到达时间到达时间 (ToA (ToA)1.1.假设两个节点都已完成时间同步，节点知道声波的传输速率。假设两个节点都已完成时间同步，节点知道声波的传输速率。2.2.扬声器放出伪噪声，同时无线传输模块，发出伪噪声序列信息发扬声器放出伪噪声，同时无线传输模块，发出伪噪声序列信息发送的时间（送的时间（T1T1）。）。3.3.接收节点根据声波的速度（接收节点根据声波的速度（V V）和到达时间（）和到达时间（T2T2）进行距离的计）进行距离的计算。算。距离距离 d=Vd=V
15、* *（T2-T1T2-T1）优点：对硬件要求的成本和复杂度低优点：对硬件要求的成本和复杂度低缺点：声波速度易受到大气的干扰缺点：声波速度易受到大气的干扰 在基于在基于TDoATDoA的定位机制中，发射节点的定位机制中，发射节点同时发射两种不同传播速度的无线信号，同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及接收节点根据两种信号到达的时间差以及这两种信号的传播速度，计算两个节点之这两种信号的传播速度，计算两个节点之间的距离。间的距离。（注意：硬件要求较高）（注意：硬件要求较高） 发射节点同时发射发射节点同时发射无线射频信号无线射频信号和和超超声波信号声波信号，接收节点
16、记录下这两种信号的，接收节点记录下这两种信号的到达时间到达时间T T1 1、T T2 2，已知无线射频信号和超已知无线射频信号和超声波的传播速度为声波的传播速度为c c1 1、c c2 2, , 那么两点之间那么两点之间的距离为的距离为( (T T2 2-T-T1 1) )* *S S，其中其中S=cS=c1 1* *c c2 2/(c/(c1 1-c-c2 2) )。测距方法测距方法- -基于基于TDoATDoA的定位机制的定位机制 该方法通过配备该方法通过配备特殊天线特殊天线来估测其它节点发射的无线来估测其它节点发射的无线信号的到达角度。信号的到达角度。 AoA AoA测距技术易受外界环境
17、影响，且需要测距技术易受外界环境影响，且需要额外硬件额外硬件（配有特殊天线）（配有特殊天线），它的硬件尺寸和功耗指标不适用于，它的硬件尺寸和功耗指标不适用于大规模的传感器网络，在某些应用领域可以发挥作用。大规模的传感器网络，在某些应用领域可以发挥作用。(3)(3)到达角到达角(AoA)2 2、多边定位、多边定位 多边定位法基于距离测量多边定位法基于距离测量( (如如RSSIRSSI、ToA/TDoA)ToA/TDoA)的结果。的结果。确定二维坐标至少具有三个节点至锚点的距离值；确定三确定二维坐标至少具有三个节点至锚点的距离值；确定三维坐标，则需四个此类测距值。维坐标，则需四个此类测距值。 22
18、2111222()()()()nnnxxyydxxyyd22222211111222222111112()2()2()2()nnnnnnnnnnnnnnnxxxx x yyyy y ddxxxx x yyyy y dd用矩阵和向量表达为形式用矩阵和向量表达为形式Ax=bAx=b，其中：，其中：11112()2().2()2()nnnnnnxxyyxxyyA222222111222222111.nnnnnnnnnxxyyddxxyyddb3 3、Min-maxMin-max定位方法定位方法Min-maxMin-max定位是根据若干锚点位置和至待求节点的测距值，创建多定位是根据若干锚点位置和至待求
19、节点的测距值，创建多个边界框，所有边界框的交集为一矩形，取此矩形的质心作为待定个边界框，所有边界框的交集为一矩形，取此矩形的质心作为待定位节点的坐标。位节点的坐标。 采用三个锚点进行定位的采用三个锚点进行定位的MinmaxMinmax方法示例，即以某锚点方法示例，即以某锚点i i (i=1, 2, 3) (i=1, 2, 3) 坐标坐标( )( )为基础，加上或减去测距值为基础，加上或减去测距值 ，得到锚点得到锚点i i的边界框：的边界框： ,iix yid - ,- ,iiiiiiiix d y dx d y d 在所有位置点在所有位置点 中取最小值、所有中取最小值、所有 中取最大值，则交集
20、矩形取作：中取最大值，则交集矩形取作： 三个锚点共同形成交叉矩形，矩形质心即为所求节点的估计位置。三个锚点共同形成交叉矩形，矩形质心即为所求节点的估计位置。,iiiixdyd,iiiixdydmax(), max() min(), min()iiiiiiiixdydxdyd三个锚点共同形成交叉矩形，三个锚点共同形成交叉矩形，矩形质心即为所求节点的估矩形质心即为所求节点的估计位置。计位置。锚点1锚点2锚点3估计位置( 矩形中心)真实位置4.2.3 4.2.3 无需测距的定位技术无需测距的定位技术1 1、质心算法、质心算法 在计算几何学里多边形的几何中心称为质心，多边形顶点坐标在计算几何学里多边形
21、的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。的平均值就是质心节点的坐标。 假设多边形定点位置的坐标向量表示为假设多边形定点位置的坐标向量表示为p pi i= (x= (xi i，y yi i) )T T，则这个，则这个多边形的质心坐标多边形的质心坐标 为：为：,xy1111,(,)nniiiixyXYnn例如例如，如果四边形，如果四边形 ABCD ABCD 的顶点坐标分别为的顶点坐标分别为 ， ， ， 则它的质心坐标计算如下：则它的质心坐标计算如下： 11,xy22,xy33,xy44,xy12341234,44xxxxyyyyx y2 2、DV-HopDV-Hop算法算法
22、DV-Hop DV-Hop算法解决了低锚点密度引发的问题，算法解决了低锚点密度引发的问题，它根据距离矢量路由协议的原理在全网范围它根据距离矢量路由协议的原理在全网范围内广播跳数和位置。内广播跳数和位置。 如图已知锚点如图已知锚点L1L1与与L2L2、L3L3之间的距离和跳之间的距离和跳数。数。L2L2计算得到校正值计算得到校正值（即平均每跳距离）（即平均每跳距离）为（为（40+7540+75）/ /（2+52+5）=16.42m=16.42m。假设传感器。假设传感器网络中的待定位节点网络中的待定位节点A A从从L2L2获得校正值，则它获得校正值，则它与与3 3个锚点之间的距离分别是个锚点之间的
23、距离分别是L1=3L1=316.4216.42，L2=2L2=216.4216.42，L3=3L3=316.4216.42，然后使用多边，然后使用多边测量法确定节点测量法确定节点A A 的位置。的位置。DV-HopDV-Hop算法算法4.2.4 4.2.4 定位系统的典型应用定位系统的典型应用 位置信息有很多用途，在某些应用中可以起到关键性的作用。定位位置信息有很多用途，在某些应用中可以起到关键性的作用。定位技术的用途大体可分为导航、跟踪、虚拟现实、网络路由等。技术的用途大体可分为导航、跟踪、虚拟现实、网络路由等。 导航是定位最基本的应用，在军事上具有重要用途。导航是定位最基本的应用，在军事上具有重要用途。 除了导航以外，定位技术还有很多应用。例如，办公场所的物品、除了导航以外，定位技术还有很多应用。例如，办公场所的物品、人员跟踪需要室内的精度定位。人员跟踪需要室内的精度定位。 虚拟现实仿真系统中需要实时定位物体的位置和方向。虚拟现实仿真系统中需要实时定位物体的位置和方向。
