无线传感网定位技术.ppt

无线传感网定位技术 一 引言二 节点定位技术基本概念三 基于距离的定位算法四 与距离无关的定位算法五 总结 引言 无线传感器节点的位置信息对于传感网来说至关重要 没有位置信息的监测数据往往毫无意义 在传感网的各种应用中 监测到事件后关心的一个重要问题就是该事件发生的位置 如在环境监测应用中需要知道采集的环境信息所对应的具体区域位置 对于突发事件 需要知道森林火灾现场位置 战场上敌方车辆运动的区域 天然气管道泄漏的具体地点等 传感器节点自身定位就是根据少数已知位置的节点 按照某种定位机制确定自身位置 只有在传感器节点自身正确定位之后 才能确定传感器节点监测到的事件发生的具体位置 这需要监测到该事件的多个传感器节点之间的相互协作 并利用它们自身的位置信息 使用特定定位机制确定事件发生的位置 引言 全球定位系统GPS GlobalPositionSystem 是目前应用最广泛最成熟的定位系统 通过卫星的授时和测距对用户节点进行定位 具有定位精度高 实时性好 抗干扰能力强等优点 但是GPS定位适应于无遮挡的室外环境 用户节点通常能耗高体积大 成本也比较高 需要固定的基础设施等 这使得不适用于低成本自组织的传感网 在机器人领域中 机器人节点的移动性和自组织等特性 其定位技术与传感网的定位技术具有一定的相似性 但是机器人节点通常携带充足的能量供应和精确的测距设备 系统中机器人的数量很少 所以这些机器人定位算法也不适用于传感网 受到成本 功耗 扩展性等问题的限制 为每个传感器安装GPS模块等这些传统定位手段并不实际 甚至在某些场合可能根本无法实现 因此必须采用一定的机制与算法实现传感器节点的自身定位 返回 节点定位技术基本概念 1 定位的含义无线传感网定位问题是指网络通过特定方法提供节点的位置信息 其定位方式可分为节点自身定位和目标定位 自身定位 是确定网络节点的坐标位置的过程 节点自身定位是网络自身属性的确定过程 可以通过人工标定或者各种节点的自定位算法完成 目标定位 是确定网络覆盖区域内一个事件或者一个目标的坐标位置 目标定位是以位置已知的网络节点作为参考 确定事件或者目标在网络覆盖范围内所在的位置 位置信息有多种分类方法 通常有物理位置和符号位置两大类 物理位置指目标在特定坐标系下的位置数值 表示目标的相对或者绝对位置 符号位置指目标与一个基站或者多个基站接近程度的信息 表示目标与基站之间的连通关系 提供目标大致的所在范围 在很多传感网应用场合中 必须知道各节点物理位置的坐标信息 通过人工测量或配置来获得节点坐标的方法往往不可行 通常传感网能够通过网络内部节点之间的相互测距和信息交换 形成一套全网节点的坐标 这才是经济和可行的定位方案 从广义上来讲 无线传感网的定位问题包括传感器节点的自身定位和对监控目标的定位 目标定位侧重于传感网在目标跟踪方面的应用 是对监控目标的位置估计 它以先期的节点自身定位为基础 从不同的角度出发 无线传感网的定位方法可以进行如下分类 1 根据是否依靠测量距离 分为基于测距的定位和不需要测距的定位 2 根据部署的场合不同 分为室内定位和室外定位 3 根据信息收集的方式 网络收集传感器数据用于节点定位被称为被动定位 节点主动发出信息用于定位被称为主动定位 2 基本术语 1 信标节点 指预先获得位置坐标的节点 也被称作锚点 其余节点被称为非锚点 2 测距 指两个相互通信的节点通过测量的方式来估计出彼此之间的距离或角度 3 连接度 包括节点连接度和网络连接度两种含义 节点连接度是指节点可探测发现的邻居节点个数 网络连接度是所有节点的邻居节点数目的平均值 它反映了传感网节点配置的密集程度 4 邻居节点 传感节点通信半径以内的所有其他节点 被称为该节点的邻居节点 5 接收信号强度指示 ReceivedsignalStrengthIndicator RSSI 节点接收到无线信号的强度大小 被称为接收信号的强度指示 6 到达角度 AngleofArrival AoA 节点接收到的信号相对于自身轴线的角度 被称为信号相对接收节点的到达角度 7 视线关系 Lineofsight LoS 如果两个节点之间没有障碍物 能够实现直接通信 则称这两个节点间存在视线关系 8 非视线关系 NoneLineofsight NLoS 两个节点之间存在障碍物 影响了它们直接的无线通信 3 定位性能的评价指标 1 定位精度 定位精度指提供的位置信息的精确程度 它分为相对精度和绝对精度 绝对精度指以长度为单位度量的精度 例如 GPS的精度为1 10m 现在使用GPS导航系统的精度约5m 一些商业的室内定位系统提供30cm的精度 可以用于工业环境 物流仓储等场合 相对精度通常以节点之间距离的百分比来定义 例如 若两个节点之间距离是20m 定位精度为2m 则相对定位精度为10 由于有些定位方法的绝对精度会随着距离的变化而变化 因而使用相对精度可以很好地表示精度指标 设节点的估计坐标与真实坐标在二维情况下的距离差值为 则个未知位置节点的网络平均定位误差为 2 覆盖范围 覆盖范围和定位精度是一对矛盾性的指标 例如超声波可以达到分米级精度 但是它的覆盖范围只有10多米 Wi Fi和蓝牙的定位精度为3米左右 覆盖范围可以达到100米左右 GSM系统能覆盖千米级的范围 但是精度只能达到100米 由此可见 覆盖范围越大 提供的精度就越低 提供大范围内的高精度通常是难以实现的 3 定位性能的评价指标 3 刷新速度 刷新速度是指提供位置信息的频率 例如 如果GPS每秒刷新1次 则这种频率对于车辆导航已经足够了 能让人体验到实时服务的感觉 对于移动的物体 如果位置信息刷新较慢 就会出现严重的位置信息滞后 直观上感觉已经前进了很长距离 提供的位置还是以前的位置 因此 刷新速度会影响定位系统实际工作提供的精度 它还会影响位置控制者的现场操作 如果刷新速度太低 可能会使得操作者无法实施实时控制 4 功耗 功耗作为传感网设计的一项重要指标 对于定位这项服务功能 需要计算为此所消耗的能量 采用的定位方法不同 功耗的差别会很大 主要原因是定位算法的复杂度不同 需要为定位提供的计算和通信开销方面存在数量上的差别 导致完成定位服务的功耗有所不同 5 代价 定位系统或算法的代价可从几个不同方面来评价 时间代价包括一个系统的安装时间 配置时间 定位所需时间 空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量 硬件尺寸等 资金代价则包括实现一种定位系统或算法的基础设施 节点设备的总费用 返回 基于距离的定位算法 基于测距的定位技术是通过测量节点之间的距离 根据几何关系计算出网络节点的位置 解析几何里有多种方法可以确定一个点的位置 比较常用的方法是多边定位和角度定位 这里重点介绍通过距离测量的方式 它可以用来计算传感网中某一未知位置的节点坐标 测距方法 1 接收信号强度指示 RSSI 2 到达时间 ToA 3 到达时间差 TDoA 4 到达角 AoA 1 接收信号强度指示 RSSI 基于RSSI定位算法 是通过测量发送功率与接收功率 计算传播损耗 利用理论和经验模型 将传播损耗转化为发送器与接收器的距离 该方法易于实现 无需在节点上安装辅助定位设备 当遇到非均匀传播环境 有障碍物造成多径反射或信号传播模型过于粗糙时 RSSI测距精度和可靠性降低 有时测距误差可达到50 一般将RSSI和其他测量方法综合运用来进行定位 2 到达时间 ToA 这类方法通过测量传输时间来估算两节点之间距离 精度较好 但由于无线信号的传输速度快 时间测量上的很小误差就会导致很大的误差值 所以要求传感器节点有较强的计算能力 这两种基于时间的测距方法适用于多种信号 如射频 声学 红外和超声波信号等 ToA机制是已知信号的传播速度 根据信号的传播时间来计算节点间的距离 如图6 1所示为某于ToA测距的简单实现过程示例 采均伪噪声序列信号作为声波信号 根据声波的传播时间来测量节点之间的距离 2 到达时间 ToA 2 假设两个节点预先变现了时间同步 在发送节点发送伪噪声序列信号的同时 无线传输模块通过无线电同步消息通知接收节点伪噪声序列信号发送的时间 接收节点的麦克风模块检测到伪噪声序列信号后 根据声波信号的传播时间和速度来计算节点间的距离 节点在计算出多个邻近的信标节点后 利用多边测量算法和极大似然估计算法算出自身的位置 ToA采用的声波信号进行到达时间测量 由于声波频率低 速度低 对节点硬件的成本和复杂度的要求很低 但声波的传播速度易受大气条件的影响 ToA算法的定位精度高 但要求节点间保持精确的时间同步 对传感器节点的硬件和功耗提出了较高的要求 3 到达时间差 TDoA 在基于TDoA的定位机制中 发射节点同时发射两种不同传播速度的无线信号 接收节点根据两种信号到达的时间差以及这两种信号的传播速度计算两个节点之间的距离 如图6 2所示 发射节点同时发射无线射频信号和超声波信号 接收节点记录下这两种信号的到达时间T1 T2 巳知无线射频信号和超声波的传播速度为c1 c2 那么两点之间的距离为 T2 T1 S 其中S c1c2 c2 c1 3 到达时间差 TDoA 2 由于无线射频信号的传播速度要远大于超声波的传播速度 因而未知节点在收到无线射频信号时 会同时打开超声波信号接收机 根据两种信号的到达时间间隔和各自的传播速度 未知节点算出和该信标节点之间的距离 然后通过比较到各个邻近信标节点的距离 选择出离自身最近的信标节点 从该信标节点广播的信息中取得自身的位置 TDoA技术对节点硬件的要求高 其对成本和功耗的要求使得该技术对低成本 低功耗的传感网设计提出了挑战 当然TDoA技术的测距误差小 具有较高精度 4 到达角 AoA 该方法通过配备特殊天线来估测其他节点发射的无线信号的到达角度 它的硬件要求较高 每个节点要安装昂贵的天线阵列和超声波接收器 在基于AoA的定位机制中 接收节点通过天线阵列或多个超声波接收机 来感知发射节点信号的到达方向 计算接收节点和发射节点之间的相对方位和角度 再通过三角测量法计算节点的位置 如图6 3所示 接收节点通过麦克风阵列 探测发射节点信号的到达方向 AoA定位不仅能够确定节点的坐标 还能够确定节点的方位信息 但是AoA测距技术易受外界环境影响 且需要额外硬件 因此它的硬件尺寸和功耗指标并不适用于大规模的传感网 节点定位计算方法 在传感器节点定位过程中 未知节点在获得对于邻近信标节点的距离 或获得邻近的信标节点与未知节点之间的相对角度后 通常使用下列方法计算自己的坐标 1 三边测量法 2 三角测量法 3 极大似然估计法 1 三边测量法 三边测量法 trilateration 如图6 4所示 已知A B C三个节点的坐标分别为 xa ya xb yb xc yc 以及它们到未知节点D的距离分别为da db dc 假设节点D的坐标为 x y 那么存在下列公式 可以得到节点D的坐标为 2 三角测量法 三角测量法 triangulation 原理如图6 5所示 已知A B C三个节点的坐标分别为 xa ya xb yb xc yc 节点D相对于节点A B C的角度分别为 ADB ADC BDC 假设节点D的坐标为 x y 对于节点A C和角 ADC 如果弧段AC在 ABC内 那么能够惟一确定一个圆 设圆心为O1 xo1 yo1 半径为r1 那么角 AO1C 2 2 ADC 并存在下列公式 由式 6 3 能够确定圆心点的坐标和半径 同理对A B ADB和B C BDC分别确定相应的圆心 半径 最后利用三边测量法 由三个圆心点及其半径确定D点坐标 3 极大似然估计法 极大似然估计法 maximumlikelihoodestimation MLE 如图2 4所示 己知1 2 3等个节点的坐标分别为 x1 y1 x2 y2 xn yn 它们到未知节点的距离分别为d1 d2 dn 假设未知节点的坐标为 x y 有公式 解方程得 其中 返回 与距离无关的定位算法 与距离无关的定位技术不需要直接测量距离和角度信息 它不是通过测量节点之间的距离来定位的 而是仅根据网络的连通性确定网络中节点之间的跳数 同时根据已知位置的参考节点的坐标等信息估计出每一跳的大致距离 然后估计出节点在网络中的位置 与距离无关的定位算法无须测量节点间的绝对距离或方位 降低了对节点硬件的要求 目前主要有两类距离无关的定位方法 一类是先对未知节点和信标节点之间的距离进行估计 然后利用多边定位等方法完成对其他节点的定位 另一类是通过邻居节点和信标节点来确定包含未知节点的区域 然后将这个区域的质心作为未知节点的坐标 距离无关的定位方法精度低 但能满足大多数应用的要求 距离无关的定位算法主要有质心算法 DV Hop算法 Amorphous算法 APIT算法等 1 质心算法 在计算几何学里 多边形的几何中心被称为质心 多边形顶点坐标的平均值就是质心节点的坐标 假设多边形顶点位置的坐标向量表示为 则这个多边形的质心坐标计算方法如下 这种方法的计算与实现都非常简单 可以根据网络的连通性确定信标节点周围的信标参考节点 直接求解信标参考节点构成的多边形的质心 在传感网的质心定位系统的实现中 信标节点周期性地向邻近节点广播分组信息 该信息包含了信标节点的标识和位置 在未知节点接收到来自不同信标节点的分组信息数量超过某一门限或在接收了一定时间之后 就可以计算这些信标节点所组成的多边形的质心 并以此确定自身位置 质心定位算法虽然实现简单 通信开销小 但仅能实现粗精度定位 并且需要信标节点具有较高的密度 各信标节点部署的位置也对定位效果有影响 2 DV Hop算法 距离向量 跳数 distancevector hop DV Hop 算法定位机制非常类似于传统网络中的距离向量路由机制 在距离向量定位机制中 未知节点首先计算与信标节点的最小跳数 然后估算平均跳数的距离 利用最小跳数乘以平均每跳距离 得到未知节点与信标节点之间的估计距离 再利用三边测量法或极大似然估计法计算未知节点的坐标 DV Hop算法的定位过程分为以下三个阶段 1 计算未知节点与信标节点的最小跳数信标节点向邻居节点广播自身的位置信息的分组 其中包括跳数字段 初始化为0 接收节点记录具有到每个信标节点的最小跳数 忽略来自同一个信标节点的最大跳数的分组 然后将跳数值加1 并转发给邻居节点 通过这种方法 网络中的所有节点能够记录下到每个信标节点的最小跳数 如图6 7所示 信标节点A广播的分组以近似于同心圆的方式在网络中逐次传播 图中的数字代表距离信标节点A的跳数 图6 7信标节点广播分组传播过程图示 2 计算未知节点与信标节点的实际跳数距离每个信标节点根据第一个阶段记录的其他信标节点的位置信息和相距跳数 利用式估算平均跳数的实际平均距离值 6 8 其中 xi yi xj yj 是信标节点I j的坐标 hij是信标节点I j与之间的跳数 然后 信标节点将计算的每跳平均距离用带有生存期字段的分组广播到网络中 未知节点仅记录接收到的每一跳平均距离 并转发给邻居节点 这个策略确保了绝大多数节点从最近的信标节点接收每跳平均距离值 未知节点接收到平均值每跳距离后 根据记录的跳数 计算到每个信标节点的跳段距离 3 利用三边测量法或极大似然估计法计算自身位置未知节点利用第二阶段中记录的每个信标节点的跳段距离 利用三边测量法或极大似然估计法计算自身坐标 如图6 8给出了DV Hop算法示例 经过第一阶段和第二阶段 能够计算出信标节点L1 L2 L3间的实际距离和跳数 那么信标节点L2计算的每跳平均距离为d 40 75 2 5 16 42m 假设未知节点A从L2获得每跳平均距离 则节点与三个信标节点之间的距离分别为 3d 2d 3d 最后利用三边测量法计算出节点的坐标 3 DV Distance算法 DV Distance算法类似于DV Hop算法 它们之间的区别就在于DV Hop算法是通过节点的平均每跳距离和跳数算出节点间的距离 而DV Distance算法是通过节点间使用射频通信来测量出节点间的距离 即利用RSSI来测量节点间的距离 然后再应用三角测量法计算出节点的位置 与DV Hop算法相比较 DV Distance算法对传感器节点的功能要求比较低 不要求节点能够储存网络中各个节点的位置信息 同时还较大幅度地减少了节点间的通信量 也就降低了节点工作的能源消耗 不足之处在于 因为它直接测量节点间的距离 这样对距离的敏感性要求较高 尤其对测距的误差很敏感 因此算法的误差较大 4 APIT算法 近似三角形内点测试法 approximatepoint intriangulationtest APIT 首先确定多个包含未知节点的三角形区域 这些三角形区域的交集是一个多边形 它确定了更小的包含未知节点的区域 然后计算这个多边形区域的质心 并将质心作为未知节点的位置 未知节点首先收集其邻近信标节点的信息 然后从这些信标节点组成的集合中任意选取三个信标节点 假设集合中有个元素 那么共有种不同的选取方法 确定个不同的三角形 逐一测试未知节点是否位于每个三角形内部 直到穷尽所有种组合或达到定位所需精度 最后计算包含目标节点所有三角形的重叠区域 将重叠区域的质心作为未知节点的位置 如图6 9所示 阴影部分区域是包含未知节点的所有三角形的重叠区域 黑点指示的质心位置作为未知节点的位置 4 APIT算法 2 APIT算法的理论基础是最佳三角形内点测试法 perfectpoint intriangulationtest PIT PIT测试原理如图6 10所示 假如存在一个方间 节点沿着这个方向移动会同时远离或接近顶点A B C 那么节点M位于ABC外 否则 节点M位三角形ABC内 在传感网中 信标节点通常是静止的 为了在静态的环境中观察三角形内点测试 提出了近似的三角形内点测试法 假如在节点的所有邻居节点里 相对于节点没有同时远