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

《无线传感网教学课件PPT.ppt》由会员分享，可在线阅读，更多相关《无线传感网教学课件PPT.ppt（48页珍藏版）》请在三一文库上搜索。

1、无线传感器网络,第一章 无线传感器网络概述,定位技术简介,基于距离的定位,距离无关的定位算法,6.1 定位技术简介,在无线传感器网络中，传感器节点自身位置信息的获取是大多数应用的基础。 首先，传感器节点必须明确自身位置才能详细说明“在什么位置发生了什么事件”， 从而实现对外部目标的定位和跟踪； 其次，了解传感器节点的位置分布状况可以对提高网络的路由效率， 从而实现网络的负载均衡以及网络拓扑的自动配置， 改善整个网络的覆盖质量。,6.1 定位技术简介,这种自组织网络定位分为节点自身定位和目标定位。节点自身定位是确定网络节点的坐标位置的过程。目标定位是确定网络覆盖区域内一个事件或者一个目标的坐标位

2、置。 节点自身定位是网络自身属性的确定过程，可以通过人工标定或者各种节点自定位算法完成。目标定位是以位置已知的网络节点作为参考，确定事件或者目标在网络覆盖范围内所在的位置。,6.1 定位技术简介,当前对节点定位问题的研究一般都基于以下前提: (1)有一定比例的节点位置己知或具有GPS定位功能，这些节点的位置可作为 定位参考点; (2)节点具有与邻近节点通信的能力; (3)节点不具有自主移动能力。,6.1 定位技术简介,人工配置每个节点的位置信息 (1)传感器网络通常部属于人类不可达的区域 (2)人工配置大量节点的位置，既容易造成人为错误，又影响网络 的快速部署，并且还违背传感器网络的自组织原则

3、 全球定位系统 GPS (1)成本考虑：传感器节点要求造价低廉以便于大量生产和部署，而 GPS 接收设备成本较高 (2)传感器节点通常依靠电池供电，能量供给有限，GPS 接收设备能耗过高 (3)GPS 设备只能适用于无遮挡的室外环境，而传感器节点可能部署于复杂环境，使得 GPS 设备难以工作。,6.1 定位技术简介,传感网络的定位算法通常需要具备的特点： 自组织性：节点随机分布，不能依靠全局的基础设施协助定位； 健壮性：节点测量数据时有误差，算法需具有良好的容错性； 能量高效：算法计算复杂度要小，减少通信开销，延长网络的生命周期； 分布计算：节点计算自身的位置，不能将信息集中到某个节点进行计算

4、。,6.1.1 基本概念和算法,1.传感器节点定位的基本概念 信标节点：所占比例小，可以通过GPS定位来获得精确位置。 未知节点：通过信标节点位置信息来确定自身位置。,6.1.1 基本概念和算法,2.基本术语 (1) 锚点：指通过其它方式预先获得位置坐标的节点，有时也称作信标节点。网络中相应的其余节点称为非锚点。 (2) 测距：指两个相互通信的节点通过测量方式来估计出彼此之间的距离或角度。 (3) 连接度：包括节点连接度和网络连接度两种含义。 节点连接度是指节点可探测发现的邻居节点个数。网络连接度是所有节点的邻居数目的平均值，它反映了传感器配置的密集程度。 (4) 邻居节点：传感器节点通信半径

5、范围以内的所有其它节点，称为该节点的邻居节点。 (5) 跳数：两个节点之间间隔的跳段总数，称为这两个节点间的跳数。,6.1.1 基本概念和算法,(6) 基础设施：协助传感器节点定位的已知自身位置的固定设备，如卫星、基站等。 (7) 到达时间：信号从一个节点传播到另一个节点所需要的时间，称为信号的到达时间。 (8) 到达时间差(TDOA)：两种不同传播速度的信号从一个节点传播到另一个节点所需要的时间之差，称为信号的到达时间差。 (9) 接收信号强度指示(RSSI)：节点接收到无线信号的强度大小，称为接收信号的强度指示。 (10) 到达角度(Angle of Arrival, AOA)：节点接收到

6、的信号相对于自身轴线的角度，称为信号相对接收节点的到达角度。 (11) 视线关系(Line of Sight, LOS)：如果传感器网络的两个节点之间没有障碍物，能够实现直接通信，则这两个节点间存在视线关系。 (12) 非视线关系：传感器网络的两个节点之间存在障碍物，影响了它们直接的无线通信。,6.1.1 基本概念和算法,3.计算节点位置的基本方法 （1）三边（多变）计算法：已知平面上（空间上）三（多）点的位置A,B,C，以及D点到A,B,C的距离, 利用几何方法可求得D点的坐标。,6.1.1 基本概念和算法,（2）三角（多角）计算法：已知平面（空间）三（多）点的位置A,B,C,以及D点为角顶

7、点，角边的端点为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 基于距离的定位,基于测距的定位技术是通过测量节点之间的距离，根据几何关系计算出网络节点的位置。

8、解析几何里有多种方法可以确定一个点的位置。比较常用的方法是多边定位和角度定位。,6.2 基于距离的定位,具体过程分为三个阶段： 第一个阶段是测距阶段 第二个阶段是定位阶段 第三个阶段是修正阶段,6.2.1 基于TOA的定位,TOA机制是已知信号的传播速度，根据信号的传播时间来计算节点间的距离。,TOA测距原理的过程示例,6.2.1 基于TOA的定位,假设两个节点时间同步, 发送节点A在发送信号的同时发送一个同步消息告知接收节点信号发送时间为t0 ,节点接收信号的同时接收同步消息并记录接收信号的时间t1,则两节点间的距离 c(t1- t0), c为信号在介质中的传播速度.,6.2.1 基于TOA

9、的定位,使用T O A 技术检测标签在二维平面的位置，则至少需要3个基 站。标签发射测量信号到达 3个 以上的基站，且必须保证时 间的同步。 由于电磁波的传播速率很 高， 微小的误差将会在算 法中放大，使定位精度大 大降低。传播中的多径干扰、非视距以及噪声等干 扰造成的误差会使各圆无法交汇，或者交汇处不是一个点而是一 个区域。因此，T O A对系统同步的要求很高，并且需要在信号中加时间戳，而实际参加定位的基站一般在 3个以上，误差是不可 避免的。单纯的T O A 算法在实际中的应用很少。,6.2.2 基于TDOA的定位,在基于TDoA的定位机制中，发射节点同时发射两种不同传播速度的无线信号，接

10、收节点根据两种信号到达的时间差以及这两种信号的传播速度，计算两个节点之间的距离。 发射节点同时发射无线射频信号和超声波信号，接收节点记录下这两种信号的到达时间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的定位,通过阵列天线或多个

11、接收器得到信号到达的方向。 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的

12、角度信息，进而计算出信标节点L相对于节点A的方位 ；,6.2.3 基于AOA的定位,第三步：利用方位信息计算节点的位置 从n个信标节点中任选三个信标节点A、B、C ；利用三角测量算法或极大似然估计算法计算节点D坐标 。,6.2.4 基于RSSI的定位,已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验的信号传播模型将传播损耗转化为距离。 该技术主要使用RF信号。因传感器节点本身具有无线通信能力，故其是一种低功率、廉价的测距技术。 主要误差来源：无线信号的反射、多径传播、非视距，天线增益等问题都会对相同距离产生显著不同的传播损耗。所以常将RSSI看作一种粗糙的测距技术，有可能产生

13、+/-50%的测距误差。,6.2.4 基于RSSI的定位,基本思想：通过信号在传播中的衰减来估计 节点之间的距离； 根据信道模型求解距离：,测距方法小结,各种测距方法都有自身的优缺点，单独使用都达不到很好的性能要求，结合不同方法会使性能提高，现实应用中比较经典的结合方法是TDOA和AOA方法的结合。,6.3 距离无关的定位算法,距离定位能够实现精确定位，硬件要求高。 距离无关定位无需测量节点间的绝对距离或方位，降低了硬件要求，但定位误差也增加了。,6.3 距离无关的定位算法,两类距离无关的定位方法： 一类对未知节点和信标节点之间的距离进行估计，三边或极大似然估计法进行定位。 另一类通过邻居节点

14、和信标节点确定未知节点的区域，然后把质心作为未知节点的坐标。,6.3 距离无关的定位算法,质心定位算法 DV-Hop算法 Amorphous算法 APIT算法,6.3.1 质心算法,多边形的几何中心，称为质心，多边形顶点坐标的平均值就是质心节点的坐标。 质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将其作为未知节点的位置。,6.3.1 质心算法,基本过程： 信标节点周期性向邻近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息； 当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。,6.3.2

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

16、点的实际跳段距离 每个信标节点根据记录的其它信标节点的位置信息和相距跳数，估算平均每跳的实际距离 ； 然后，信标节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第一个每跳平均距离，并转发给邻居节点 ； 未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个信标节点的跳段距离；,6.3.2 DV-Hop算法,3.利用三边测量法或极大似然估计法计算自身位置 未知节点利用第二阶段中记录的到各个信标节点的跳段距离，利用三边测量法或极大似然估计法计算自身坐标,6.3.2 DV-Hop算法,例子 信标节点L2计算的每跳平均距离为(40+75)/(2+5) A从L2获得每

17、跳平均距离，则节点A与三个信标节点之间的距离分别为L1：316.42，L2：216.42，L3：316.42；,6.3.3 Amorphous算法,在不定形计算机（Amorphous Computer）上实现的定位算法。 不定形计算机是一种并行计算结构，和智能群（蚁群、鸟群、粒子群等）很相似。 本质上，不定形算法是DV-Hop算法的增强，引入了多参考点测量进行估计求精的步骤。 两个重要的参数修正： 不定形算法通过平滑（smoothing）修正节点到参考节点的梯度跳数。 采用通信半径作为每跳距离，使得节点到参考节点的最终估计距离偏大。不定形算法采用下面的公式来修正每跳距离：,6.3.4 APIT

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

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