无线传感网教学课件PPT.ppt

无线传感器网络 第一章无线传感器网络概述 定位技术简介 基于距离的定位 距离无关的定位算法 6 1定位技术简介 在无线传感器网络中 传感器节点自身位置信息的获取是大多数应用的基础 首先 传感器节点必须明确自身位置才能详细说明 在什么位置发生了什么事件 从而实现对外部目标的定位和跟踪 其次 了解传感器节点的位置分布状况可以对提高网络的路由效率 从而实现网络的负载均衡以及网络拓扑的自动配置 改善整个网络的覆盖质量 6 1定位技术简介 这种自组织网络定位分为节点自身定位和目标定位 节点自身定位是确定网络节点的坐标位置的过程 目标定位是确定网络覆盖区域内一个事件或者一个目标的坐标位置 节点自身定位是网络自身属性的确定过程 可以通过人工标定或者各种节点自定位算法完成 目标定位是以位置已知的网络节点作为参考 确定事件或者目标在网络覆盖范围内所在的位置 6 1定位技术简介 当前对节点定位问题的研究一般都基于以下前提 1 有一定比例的节点位置己知或具有gps定位功能 这些节点的位置可作为定位参考点 2 节点具有与邻近节点通信的能力 3 节点不具有自主移动能力 6 1定位技术简介 人工配置每个节点的位置信息 1 传感器网络通常部属于人类不可达的区域 2 人工配置大量节点的位置 既容易造成人为错误 又影响网络的快速部署 并且还违背传感器网络的自组织原则全球定位系统gps 1 成本考虑 传感器节点要求造价低廉以便于大量生产和部署 而gps接收设备成本较高 2 传感器节点通常依靠电池供电 能量供给有限 gps接收设备能耗过高 3 gps设备只能适用于无遮挡的室外环境 而传感器节点可能部署于复杂环境 使得gps设备难以工作 6 1定位技术简介 传感网络的定位算法通常需要具备的特点 自组织性 节点随机分布 不能依靠全局的基础设施协助定位 健壮性 节点测量数据时有误差 算法需具有良好的容错性 能量高效 算法计算复杂度要小 减少通信开销 延长网络的生命周期 分布计算 节点计算自身的位置 不能将信息集中到某个节点进行计算 6 1 1基本概念和算法 1 传感器节点定位的基本概念信标节点 所占比例小 可以通过gps定位来获得精确位置 未知节点 通过信标节点位置信息来确定自身位置 6 1 1基本概念和算法 2 基本术语 1 锚点 指通过其它方式预先获得位置坐标的节点 有时也称作信标节点 网络中相应的其余节点称为非锚点 2 测距 指两个相互通信的节点通过测量方式来估计出彼此之间的距离或角度 3 连接度 包括节点连接度和网络连接度两种含义 节点连接度是指节点可探测发现的邻居节点个数 网络连接度是所有节点的邻居数目的平均值 它反映了传感器配置的密集程度 4 邻居节点 传感器节点通信半径范围以内的所有其它节点 称为该节点的邻居节点 5 跳数 两个节点之间间隔的跳段总数 称为这两个节点间的跳数 6 1 1基本概念和算法 6 基础设施 协助传感器节点定位的已知自身位置的固定设备 如卫星 基站等 7 到达时间 信号从一个节点传播到另一个节点所需要的时间 称为信号的到达时间 8 到达时间差 tdoa 两种不同传播速度的信号从一个节点传播到另一个节点所需要的时间之差 称为信号的到达时间差 9 接收信号强度指示 rssi 节点接收到无线信号的强度大小 称为接收信号的强度指示 10 到达角度 angleofarrival aoa 节点接收到的信号相对于自身轴线的角度 称为信号相对接收节点的到达角度 11 视线关系 lineofsight los 如果传感器网络的两个节点之间没有障碍物 能够实现直接通信 则这两个节点间存在视线关系 12 非视线关系 传感器网络的两个节点之间存在障碍物 影响了它们直接的无线通信 6 1 1基本概念和算法 3 计算节点位置的基本方法 1 三边 多变 计算法 已知平面上 空间上 三 多 点的位置a b c 以及d点到a b c的距离 利用几何方法可求得d点的坐标 6 1 1基本概念和算法 2 三角 多角 计算法 已知平面 空间 三 多 点的位置a b c 以及d点为角顶点 角边的端点为a b c的角度 可求出d点的坐标 6 1 1基本概念和算法 3 极大似然估计法 已知很多节点d的相邻节点坐标以及他们到节点d的距离或方位 使用最小均方差估计方法得到节点d的坐标 6 1 2定位算法分类 1 根据定位过程中实际测量节点间的距离和角度与否 6 1 2定位算法分类 2 根据各节点定位的先后次序 6 1 2定位算法分类 3 定位过程是否使用信标 6 1 2定位算法分类 4 根据在定位过程中是否把信息传送到某个后台中心或服务器进行节点坐标的计算 6 2基于距离的定位 基于测距的定位技术是通过测量节点之间的距离 根据几何关系计算出网络节点的位置 解析几何里有多种方法可以确定一个点的位置 比较常用的方法是多边定位和角度定位 6 2基于距离的定位 具体过程分为三个阶段 第一个阶段是测距阶段第二个阶段是定位阶段第三个阶段是修正阶段 6 2 1基于toa的定位 toa机制是已知信号的传播速度 根据信号的传播时间来计算节点间的距离 toa测距原理的过程示例 6 2 1基于toa的定位 假设两个节点时间同步 发送节点a在发送信号的同时发送一个同步消息告知接收节点 信号发送时间为t0 节点 接收信号的同时接收同步消息并记录接收信号的时间t1 则两节点间的距离 c t1 t0 c为信号在介质中的传播速度 6 2 1基于toa的定位 使用toa技术检测标签在二维平面的位置 则至少需要3个基站 标签发射测量信号到达3个以上的基站 且必须保证时间的同步 由于电磁波的传播速率很高 微小的误差将会在算法中放大 使定位精度大大降低 传播中的多径干扰 非视距以及噪声等干扰造成的误差会使各圆无法交汇 或者交汇处不是一个点而是一个区域 因此 toa对系统同步的要求很高 并且需要在信号中加时间戳 而实际参加定位的基站一般在3个以上 误差是不可避免的 单纯的toa算法在实际中的应用很少 6 2 2基于tdoa的定位 在基于tdoa的定位机制中 发射节点同时发射两种不同传播速度的无线信号 接收节点根据两种信号到达的时间差以及这两种信号的传播速度 计算两个节点之间的距离 发射节点同时发射无线射频信号和超声波信号 接收节点记录下这两种信号的到达时间t1 t2 已知无线射频信号和超声波的传播速度为c1 c2 那么两点之间的距离为 t2 t1 s 其中s c1 c2 c1 c2 6 2 2基于tdoa的定位 6 2 3基于aoa的定位 该方法通过配备特殊天线来估测其它节点发射的无线信号的到达角度 aoa测距技术易受外界环境影响 且需要额外硬件 它的硬件尺寸和功耗指标不适用于大规模的传感器网络 在某些应用领域可以发挥作用 6 2 3基于aoa的定位 通过阵列天线或多个接收器得到信号到达的方向 b1 b2为信标节点 a接收b1 b2发送的信号 以自己的参考轴为准 记录两个信号来源的角度 从而能实现自身定位 6 2 3基于aoa的定位 第一步 相邻节点之间方位角的测定节点a的两个接收机r1 r2间距离是l 接收机连线中点的位置代表节点a位置 将两个接收机连线的中垂线作为节点a的轴线 作为确定邻居节点方位角度基准线 6 2 3基于aoa的定位 第二步 相对信标节点的方位角测量目标 计算与信标节点不相邻的未知节点与各信标节点之间的方位 l节点是信标节点 a b c节点互为邻居节点 abc lbc的内部角度已经计算 从而能够计算出四边形aclb的角度信息 进而计算出信标节点l相对于节点a的方位 6 2 3基于aoa的定位 第三步 利用方位信息计算节点的位置从n个信标节点中任选三个信标节点a b c 利用三角测量算法或极大似然估计算法计算节点d坐标 6 2 4基于rssi的定位 已知发射功率 在接收节点测量接收功率 计算传播损耗 使用理论或经验的信号传播模型将传播损耗转化为距离 该技术主要使用rf信号 因传感器节点本身具有无线通信能力 故其是一种低功率 廉价的测距技术 主要误差来源 无线信号的反射 多径传播 非视距 天线增益等问题都会对相同距离产生显著不同的传播损耗 所以常将rssi看作一种粗糙的测距技术 有可能产生 50 的测距误差 6 2 4基于rssi的定位 基本思想 通过信号在传播中的衰减来估计节点之间的距离 根据信道模型求解距离 测距方法小结 各种测距方法都有自身的优缺点 单独使用都达不到很好的性能要求 结合不同方法会使性能提高 现实应用中比较经典的结合方法是tdoa和aoa方法的结合 6 3距离无关的定位算法 距离定位能够实现精确定位 硬件要求高 距离无关定位无需测量节点间的绝对距离或方位 降低了硬件要求 但定位误差也增加了 6 3距离无关的定位算法 两类距离无关的定位方法 一类对未知节点和信标节点之间的距离进行估计 三边或极大似然估计法进行定位 另一类通过邻居节点和信标节点确定未知节点的区域 然后把质心作为未知节点的坐标 6 3距离无关的定位算法 质心定位算法dv hop算法amorphous算法apit算法 6 3 1质心算法 多边形的几何中心 称为质心 多边形顶点坐标的平均值就是质心节点的坐标 质心定位算法首先确定包含未知节点的区域 计算这个区域的质心 并将其作为未知节点的位置 6 3 1质心算法 基本过程 信标节点周期性向邻近节点广播信标分组 信标分组中包含信标节点的标识号和位置信息 当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限k或接收一定时间后 就确定自身位置为这些信标节点所组成的多边形的质心 6 3 2dv hop算法 基本思想 首先 计算未知节点与每个信标节点的最小跳数 然后 估算平均每跳的距离 利用最小跳数乘以平均每跳距离 得到未知节点与信标节点之间的估计距离 最后 利用三边测量法或极大似然估计法计算未知节点的坐标 6 3 2dv hop算法 1 计算未知节点与每个信标节点的最小跳数信标节点向邻居节点广播自身位置信息的分组 其中包括跳数字段 初始化为0 接收节点记录具有到每个信标节点的最小跳数 忽略来自同一个信标节点的较大跳数的分组 然后将跳数值加1 并转发给邻居节点 网络中所有节点能够记录下到每个信标节点最小跳数 6 3 2dv hop算法 2 计算未知节点与信标节点的实际跳段距离每个信标节点根据记录的其它信标节点的位置信息和相距跳数 估算平均每跳的实际距离 然后 信标节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中 未知节点仅记录接收到的第一个每跳平均距离 并转发给邻居节点 未知节点接收到平均每跳距离后 根据记录的跳数 计算到每个信标节点的跳段距离 6 3 2dv hop算法 3 利用三边测量法或极大似然估计法计算自身位置未知节点利用第二阶段中记录的到各个信标节点的跳段距离 利用三边测量法或极大似然估计法计算自身坐标 6 3 2dv hop算法 例子信标节点l2计算的每跳平均距离为 40 75 2 5 a从l2获得每跳平均距离 则节点a与三个信标节点之间的距离分别为l1 3 16 42 l2 2 16 42 l3 3 16 42 6 3 3amorphous算法 在不定形计算机 amorphouscomputer 上实现的定位算法 不定形计算机是一种并行计算结构 和智能群 蚁群 鸟群 粒子群等 很相似 本质上 不定形算法是dv hop算法的增强 引入了多参考点测量进行估计求精的步骤 两个重要的参数修正 不定形算法通过平滑 smoothing 修正节点到参考节点的梯度跳数 采用通信半径作为每跳距离 使得节点到参考节点的最终估计距离偏大 不定形算法采用下面的公式来修正每跳距离 6 3 4apit算法 近似三角形内点测试法 apit approximatepoint in triangulationtest 找到若干个由参考节点构成的三角形 则节点必然在这些三角形的交集内 使用这个交集的重心估计节点的位置 apit算法分四步 1 信标交换 2 三角形内点测试 pit point in triangulationtesting 3 交集运算计算三角形的重合区域 4 重心 cog centerofgravity 计算求节点的位置 6 3 4apit算法 基本过程未知节点首先收集其邻近信标节点的位置信息 从这些信标节点组成的集合中任意选取三个节点 假设集合中有n个元素 那么共有cn3种不同选取方法 确定cn3个不同三角形 逐一测试未知节点是否位于每个三角形内部 直到穷尽所有cn3种组合或达到定位所需精度 计算包含目标节点所有三角形的