第3课 定位技术

1、1WSN: Theory and Applications一、I o T概述二、WSN概述三、路由协议四、拓扑控制五、定位技术六、目标跟踪七、时间同步八、信息融合 九、安全技术2第三课、定位技术物联网工程学院吴治海Email: Phoneddress:C4232011-9-22本节课主要内容提纲WSN定位技术的概述 定位算法的几种分类基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 1. WSN定位技术的概述-基本含义 定位就是确定位置。定位的两种意义：一种是确定自己在系统中的位置；一种是确定目标在系统中的位置。位置信息的类型：物理位置指目标在特定坐标系下

2、的位置数值，表示目标的相对或者绝对位置；符号位置指在目标与一个基站或者多个基站接近程度的信息，表示目标与基站之间的连通关系，提供目标大致的所在范围。1. WSN定位技术的概述-基本含义 定位机制是定位机制是WSN的基本机制的基本机制 没有位置信息的检测消息是没有意义的； 应用：战场侦查、目标跟踪、入侵检测、灾难预报等。 节点定位是基本的定位机制节点定位是基本的定位机制 随机部署的网络，需要确定节点位置； 只有节点定位以后，才能确定节点检测事件的位置。1. WSN定位技术概述-技术指标 最重要的指标，指定位系统提供的位置信息的精确程度。 绝对精度指以长度为单位度量的精度；相对精度，通常以节点之间

3、距离的百分比来定义。覆盖范围是另一个重要指标，它和精度是一对矛盾。刷新速度是提供位置信息的频率。比如GPS每秒钟刷新1次。 精度覆盖范围超声波分米级十多米Wi-Fi和蓝牙3米100米GSMC系统100米公里级1. WSN定位技术的概述-算法特点 自组织性：节点随机分布，不能依靠全局的基础设施协助定位； 健壮性：节点测量数据时有误差，算法需具有良好的容错性； 能量高效：算法计算复杂度要小，减少通信开销，延长网络的生命周期； 分布计算：节点计算自身的位置，不能将信息集中到某个节点进行计算。本节课主要内容提纲WSN定位技术的概述 定位算法的几种分类基于测距的定位技术 无需测距的定位技术 一篇WSN定

4、位的文献 2.定位算法的几种分类节点位置计算方法定位算法分类（1）定位算法分类（2）定位算法分类（3）2.定位算法的几种分类：节点位置计算方法 已知A、B、C三个节点的坐标，以及它们到节点D的距离，确定节点D的坐标。三边测量算法2.定位算法的几种分类：节点位置计算方法 已知A、B、C三个节点的坐标，节点D相对于节点A、B、C的角度，确定节点D的坐标； 转换为三边测量法。三角测量算法2.定位算法的几种分类：节点位置计算方法 知1、2、3等n个节点的坐标，及它们到节点D到距离，确定节点D的坐标； 最小均方差估计算法。极大似然估计法2.定位算法的几种分类（1） 根据定位过程中是否测量实际节点间的距离

5、，把定位算法分为： 基于距离的（range-based）定位 利用测量节点间实际距离或方位计算未知节点位置； 距离无关的（range-free）定位 利用节点间的估计距离计算未知节点位置 。2.定位算法的几种分类（2） 根据定位过程中节点定位先后次序的不同，把定位算法分为： 递增式的（Incremental）定位 信标节点附近的节点首先开始定位，依次向外延伸，各节点逐次进行定位 ； 并发式的（Concurrent）定位 所有的节点同时进行位置计算 。2.定位算法的几种分类（3） 根据定位过程中是否使用信标节点的位置信息 ，把定位算法分为： 基于信标节点（beacon-based）定位 以信标节

6、点作为定位中的参考点，各节点定位后产生整体绝对坐标系统 ； 无信标节点的(beacon-free)定位 各节点先以自身作为参考点，将邻近节点纳入自己定义的坐标系中，相邻的坐标系统依次转换合并，最后产生整体相对坐标系统 。本节课主要内容提纲WSN定位技术的概述 定位算法的几种分类基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 3. 基于测距的定位技术 基本思想：通过测量相邻节点间的实际距离或方位进行定位。 三个阶段： 测距阶段：未知节点首先测量到邻居节点的距离或角度，然后进一步计算到邻近信标节点的距离或方位； 定位阶段：未知节点在计算出到达三个或三个以上信标节点的距离或角度后，利用

7、三边测量法、三角测量法或极大似然估计法计算未知节点的坐标； 修正阶段：对求得的节点的坐标进行求精，提高定位精度，减少误差。3. 基于测距的定位技术 基于信号传播时间的定位（TOA）基于信号传播时间差定位（TDOA）基于接收信号强度的定位（RSSI） 基于接收信号角度的定位 (AOA) 3. 基于测距的定位技术-TOA 发射机接收机T0T1T2T32*)()(1203VTTTTd 基本思想： 已知信号的传播速度，根据信号的传播时间来计算节点间的距离，然后利用三边或极大似然估计法等计算出节点的位置。3. 基于测距的定位技术-TOA 定位过程： 发送节点的扬声器模块在发送伪噪声序列信号的同时，无线电

8、模块通过无线电同步消息通知接收节点伪噪声序列信号发送的时间，接收节点的麦克风模块在检测到伪噪声序列信号后，根据传播时间和速度计算发送节点和接收节点之间的距离；利用三边测量算法或极大似然估计算法计算出自身位置；3. 基于测距的定位技术-TDOA122112()*c cdTTcc 基本思想： 发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种信号到达的时间差以及已知这两种信号的传播速度，计算两个节点之间的距离，然后利用三边或极大似然估计法等计算出节点的位置。3. 基于测距的定位技术- RSSI,0,0( )() 10 logr dBr dBdBdPdPdXd 基本思想：通过信号在传播中的

9、衰减来估计节点之间的距离； 根据信道模型求解距离：3. 基于测距的定位技术-AOA 基本思想： 接收节点通过天线阵列或多个超声波接收机感知发射节点信号的到达方向，计算接收节点和发射节点之间的相对方位或角度，再通过三角测量法计算出节点的位置 。3. 基于测距的定位技术-AOA 第一步：相邻节点之间方位角的测定 节点A的两个接收机R1、R2间距离是L，接收机连线中点的位置代表节点A位置；将两个接收机连线的中垂线作为节点A的轴线，作为确定邻居节点方位角度基准线 ；3. 基于测距的定位技术-AOA 第二步：相对信标节点的方位角测量 目标：计算与信标节点不相邻的未知节点与各信标节点之间的方位； L节点是

10、信标节点，A、B、C节点互为邻居节点； ABC、LBC的内部角度已经计算，从而能够计算出四边形ACLB的角度信息，进而计算出信标节点L相对于节点A的方位 ；3. 基于测距的定位技术-AOA 第三步：利用方位信息计算节点的位置 从n个信标节点中任选三个信标节点A、B、C ；利用三角测量算法或极大似然估计算法计算节点D坐标 。本节课主要内容提纲WSN定位技术的概述 定位算法的几种分类基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 4. 无需测距的定位技术质心定位算法 DV-Hop算法 APIT算法 不定形定位算法 4. 无需测距的定位技术-质心定位算法 多边形的几何中心，称为质心，多

11、边形顶点坐标的平均值就是质心节点的坐标。 质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置。4. 无需测距的定位技术-质心定位算法 基本过程： 信标节点周期性向邻近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息； 当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。4. 无需测距的定位技术- DV-Hop算法 基本思想： 首先：计算未知节点与每个信标节点的最小跳数； 然后：估算平均每跳的距离，利用最小跳数乘以平均每跳距离，得到未知节点与信标节点之间的估计距离； 最后：利

12、用三边测量法或极大似然估计法计算未知节点的坐标。4. 无需测距的定位技术- DV-Hop算法 计算未知节点与每个信标节点的最小跳数 信标节点向邻居节点广播自身位置信息的分组，其中包括跳数字段，初始化为0； 接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加1，并转发给邻居节点； 网络中所有节点能够记录下到每个信标节点最小跳数4. 无需测距的定位技术- DV-Hop算法 计算未知节点与信标节点的实际跳段距离 每个信标节点根据记录的其它信标节点的位置信息和相距跳数，估算平均每跳的实际距离 ； 然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播

13、至网络中，未知节点仅记录接收到的第一个每跳平均距离，并转发给邻居节点 ； 未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个信标节点的跳段距离；4. 无需测距的定位技术- DV-Hop算法 利用三边测量法或极大似然估计法计算自身位置 未知节点利用第二阶段中记录的到各个信标节点的跳段距离，利用三边测量法或极大似然估计法计算自身坐标4. 无需测距的定位技术- DV-Hop算法 例子 信标节点L2计算的每跳平均距离为(40+75)/(2+5) A从L2获得每跳平均距离，则节点A与三个信标节点之间的距离分别为L1：316.42，L2：216.42，L3：316.42； L3AL1L24. 无需测

14、距的定位技术- APIT算法 近似三角形内点测试法（APIT, Approximate Point-In-Triangulation test）找到若干个由参考节点构成的三角形，则节点必然在这些三角形的交集内。使用这个交集的重心估计节点的位置。 APIT算法分四步：（1）信标交换，（2）三角形内点测试（PIT, Point-In-Triangulation testing），（3） 交集运算计算三角形的重合区域，（4）重心（COG, Center of Gravity）计算求节点的位置。 4. 无需测距的定位技术-APIT算法 基本过程 未知节点首先收集其邻近信标节点的位置信息； 从这些信标节

15、点组成的集合中任意选取三个节点，假设集合中有n个元素，那么共有Cn3种不同选取方法，确定Cn3个不同三角形，逐一测试未知节点是否位于每个三角形内部，直到穷尽所有Cn3种组合或达到定位所需精度； 计算包含目标节点所有三角形的重叠区域，并求质心；4. 无需测距的定位技术- APIT算法 PIT：最佳三角形内点测试法 PIT原理 假如存在一个方向，节点M沿着这个方向移动会同时远离或接近顶点A、B、C，那么节点M位于ABC外；否则，节点M位于ABC内。4. 无需测距的定位技术-APIT算法 收集信息 未知节点收集邻近信标节点的信息，如位置、标识号、接收到的信号强度等；邻居节点之间交换各自接收到的信标节

16、点的信息 ； APIT 测试 测试未知节点是否在不同信标节点组合成三角形内部 ； 计算重叠区域 统计包含未知节点三角形，计算所有三角形的重叠区域； 计算未知节点位置 计算重叠区域的质心位置，作为未知节点的位置3. 无需测距的定位技术-不定形定位算法 在不定形计算机（Amorphous Computer）上实现的定位算法。 不定形计算机是一种并行计算结构，和智能群（蚁群、鸟群、粒子群等）很相似。本质上，不定形算法是DV-Hop算法的增强，引入了多参考点测量进行估计求精的步骤。两个重要的参数修正：不定形算法通过平滑（smoothing）修正节点到参考节点的梯度跳数。采用通信半径作为每跳距离，使得节点到参考节点的最终估计距离偏大。不定形算法采用下面的公式来修正每跳距离： 本节课主要内容提纲WSN定位技术的概述 定位算法的几种分类基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 6.一篇文献标题：简明扼要标题：简明扼要 编辑：审稿周期编辑：审稿周期6.一篇文献研究什么问题研究什么问题Consider 使用什么方法、得到什么结果使用什么方法、得到什么结果First, Then, By applying 仿真验证理论仿真验证理论Simulations 关键词：研究对象、研究方法关键词：研究对