第2讲定位技术

1、第第2讲定位技术讲定位技术 1 WSN: Theory and Applications 一、WSN概述 二、定位技术 三、目标跟踪 四、拓扑控制 五、时间同步 六、路由协议 七、安全技术 八、课程考核 第第2讲定位技术讲定位技术 本节课主要内容提纲 WSN定位技术的概述 基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 第第2讲定位技术讲定位技术 1. WSN定位技术的概述 基本含义 重要意义 性能指标 算法特点 位置计算 算法分类 第第2讲定位技术讲定位技术 1. WSN定位技术的概述-基本含义 定位就是确定位置。 定位的两种意义： 一种是确定自己在系统中的位置； 一种是确定目

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

3、定位技术概述-性能指标 最重要的指标，指定位系统提供的位置信息 的精确程度。 绝对精度，指以长度为单位度量的精度； 相对精度，通常以节点之间距离的百分比来定义。 覆盖范围是另一个重要指标，它和精度是一 对矛盾。 第第2讲定位技术讲定位技术 1. WSN定位技术的概述-算法特点 自组织性：节点随机分布，不能依靠全 局的基础设施协助定位； 健 壮 性：节点测量数据时有误差，算 法需具有良好的容错性； 能量高效：算法计算复杂度要小，减少 通信开销，延长网络的生命周期； 分布计算：节点计算自身的位置，不能 将信息集中到某个节点进行计算。 第第2讲定位技术讲定位技术 已知A、B、C三个节点的坐标，以及它

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

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

6、使用信标节点的位 置信息 ，把定位算法分为： 基于信标节点（beacon-based）定位 以信标节点作为定位中的参考点，各节点定位后产生整体 绝对坐标系统 ； 无信标节点的(beacon-free)定位 各节点先以自身作为参考点，将邻近节点纳入自己定义的 坐标系中，相邻的坐标系统依次转换合并，最后产生整体 相对坐标系统 。 第第2讲定位技术讲定位技术 本节课主要内容提纲 WSN定位技术的概述 基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 第第2讲定位技术讲定位技术 2. 基于测距的定位技术 基本思想： 通过测量相邻节点间的实际距离或方位进行定位。 三个阶段： 测距阶段：未知节

7、点首先测量到邻居节点的距离或角 度，然后进一步计算到邻近信标节点的距离或方位； 定位阶段：未知节点在计算出到达三个或三个以上信 标节点的距离或角度后，利用三边测量法、三角测量 法或极大似然估计法计算未知节点的坐标； 修正阶段：对求得的节点的坐标进行求精，提高定位 精度，减少误差。 第第2讲定位技术讲定位技术 2. 基于测距的定位技术 基于信号传播时间的定位（TOA） 基于信号传播时间差定位（TDOA） 基于接收信号强度的定位（RSSI） 基于接收信号角度的定位 (AOA) 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-TOA 发射机接收机 T0 T1 T2 T3 3021 ()() 2

8、 TTTT V d 基本思想： 已知信号的传播速度，根据信号的传播时间来计算 节点间的距离，然后利用三边或极大似然估计法等 计算出节点的位置。 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-TOA 定位过程： 发送节点的扬声器模块在发送伪噪声序列信号的同时， 无线电模块通过无线电同步消息通知接收节点伪噪声序 列信号发送的时间，接收节点的麦克风模块在检测到伪 噪声序列信号后，根据传播时间和速度计算发送节点和 接收节点之间的距离；利用三边测量算法或极大似然估 计算法计算出自身位置； 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-TDOA 12 21 12 ()* c c dTT c

9、c 基本思想： 发射节点同时发射两种不同传播速度的无线信号，接 收节点根据两种信号到达的时间差以及已知这两种信 号的传播速度，计算两个节点之间的距离，然后利用 三边或极大似然估计法等计算出节点的位置。 第第2讲定位技术讲定位技术 2. 基于测距的定位技术- RSSI ,0, 0 ( )() 10 log r dBr dBdB d PdPdX d 基本思想： 通过信号在传播中的衰减来估计节点之间的距离； 根据信道模型求解距离： 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-AOA 基本思想： 接收节点通过天线阵列或多个超声波接收机 感知发射节点信号的到达方向，计算接收节 点和发射节点之间

10、的相对方位或角度，再通 过三角测量法计算出节点的位置 。 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-AOA 第一步：相邻节点之间方位角的测定 节点A的两个接收机R1、R2间距离是L，接 收机连线中点的位置代表节点A位置；将两 个接收机连线的中垂线作为节点A的轴线， 作为确定邻居节点方位角度基准线 ； 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-AOA 第二步：相对信标节点的方位角测量 目标：计算与信标节点不相邻的未知节点与各信标 节点之间的方位； L节点是信标节点，A、B、C节点互为邻居节点； ABC、LBC的内部角度已经计算，从而能够计 算出四边形ACLB的角度信息，进

11、而计算出信标节 点L相对于节点A的方位 ； 第第2讲定位技术讲定位技术 2. 基于测距的定位技术-AOA 第三步：利用方位信息计算节点的位置 从n个信标节点中任选三个信标节点A、B、C ； 利用三角测量算法或极大似然估计算法计算节 点D坐标 。 第第2讲定位技术讲定位技术 本节课主要内容提纲 WSN定位技术的概述 基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 第第2讲定位技术讲定位技术 3. 无需测距的定位技术 质心定位算法 DV-Hop算法 APIT算法 不定形定位算法 第第2讲定位技术讲定位技术 3. 无需测距的定位技术-质心定位算法 多边形的几何中心，称为质心，多边形顶点

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

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

14、标节点根据记录的其它信标节点的位置信息 和相距跳数，估算平均每跳的实际距离 ； 然后，信标节点将计算的每跳平均距离用带有生存 期字段的分组广播至网络中，未知节点仅记录接收 到的第一个每跳平均距离，并转发给邻居节点 ； 未知节点接收到平均每跳距离后，根据记录的跳数， 计算到每个信标节点的跳段距离； 第第2讲定位技术讲定位技术 3. 无需测距的定位技术- DV-Hop算法 利用三边测量法或极大似然估计法计算 自身位置 未知节点利用第二阶段中记录的到各个信标 节点的跳段距离，利用三边测量法或极大似 然估计法计算自身坐标 第第2讲定位技术讲定位技术 3. 无需测距的定位技术- DV-Hop算法 例子

15、信标节点L2计算的每跳平均距离为(40+75)/(2+5) A从L2获得每跳平均距离，则节点A与三个信标节 点之间的距离分别为L1：316.42，L2：216.42， L3：316.42； L3 A L1 L2 第第2讲定位技术讲定位技术 3. 无需测距的定位技术- APIT算法 近似三角形内点测试法（APIT, Approximate Point- In-Triangulation test）找到若干个由参考节点构成 的三角形，则节点必然在这些三角形的交集内。 使用这个交集的重心估计节点的位置。 APIT算法分四步：（1）信标交换，（2）三角形 内点测试（PIT, Point-In-Tria

16、ngulation testing）， （3） 交集运算计算三角形的重合区域，（4）重 心（COG, Center of Gravity）计算求节点的位置。 第第2讲定位技术讲定位技术 3. 无需测距的定位技术-APIT算法 基本过程 未知节点首先收集其邻近信标节点的位置信息； 从这些信标节点组成的集合中任意选取三个节点， 假设集合中有n个元素，那么共有Cn3种不同选取 方法，确定Cn3个不同三角形，逐一测试未知节点 是否位于每个三角形内部，直到穷尽所有Cn3种组 合或达到定位所需精度； 计算包含目标节点所有三角形的重叠区域，并求 质心； 第第2讲定位技术讲定位技术 3. 无需测距的定位技术-

17、 APIT算法 PIT：最佳三角形内点测试法 PIT原理 假如存在一个方向，节点M沿着这个方向 移动会同时远离或接近顶点A、B、C，那 么节点M位于ABC外；否则，节点M位 于ABC内。 第第2讲定位技术讲定位技术 3. 无需测距的定位技术-APIT算法 收集信息 未知节点收集邻近信标节点的信息，如位置、标识号、接收 到的信号强度等；邻居节点之间交换各自接收到的信标节点 的信息 ； APIT 测试 测试未知节点是否在不同信标节点组合成三角形内部 ； 计算重叠区域 统计包含未知节点三角形，计算所有三角形的重叠区域； 计算未知节点位置 计算重叠区域的质心位置，作为未知节点的位置 第第2讲定位技术讲

18、定位技术 3. 无需测距的定位技术-不定形定位算法 在不定形计算机（Amorphous Computer）上实现 的定位算法。 不定形计算机是一种并行计算结构，和智能群 （蚁群、鸟群、粒子群等）很相似。 本质上，不定形算法是DV-Hop算法的增强，引入 了多参考点测量进行估计求精的步骤。 两个重要的参数修正： 不定形算法通过平滑（smoothing）修正节点到参考节点 的梯度跳数。 采用通信半径作为每跳距离，使得节点到参考节点的最 终估计距离偏大。不定形算法采用下面的公式来修正每 跳距离： 第第2讲定位技术讲定位技术 本节课主要内容提纲 WSN定位技术的概述 基于测距的定位技术 无需测距的定位技术 一篇WSN定位的文献 第第2讲定位技术讲定位