DV-HOP定位算法.ppt

无线传感器网络的定位技术,主要内容,1引言,2定位技术分类,3DV-HOP定位算法,4性能指标,引言,无线传感器网络：指一种在监测区域内随机部署的传感器节点通过无线通信方式形成的多跳、自组织的分布式网络。定位技术的研究意义：节点的感知数据必须与位置相结合，离开位置信息，感知数据是没有意义的，如环境监测、医疗、森林火灾监控等。,引言,当前对节点定位问题的研究一般都基于以下前提:(1)网络中有一定比例的节点位置己知或具有GPS定位功能，这些位置已知的节点可作为定位参考点。因为GPS模块价格昂贵、能量消耗大，而且受工作环境的限制，所以网络中少数节点通过GPS定位。(2)节点具有与邻近节点通信的能力。(3)节点不具有自主移动能力。,主要内容,1引言,2定位技术分类,3DV-HOP定位算法,4性能指标,定位技术的分类,根据定位过程中是否需要测量实际节点间的距离，定位算法可分为基于测距(Range-Based)的定位算法和无需测距(Range-Free)的定位算法。,Range-Based&Range-Free,特点比较,基于测距的算法,基于信号传播时间差定位（TDOA）,基于信号传播时间的定位（TOA）,基于测距的定位算法,无需测距,DV-HOP定位算法,质心定位算法,无需测距的定位算法,集中式计算&分布式计算,根据在定位过程中是否把信息传送到某个后台中心或服务器进行节点坐标的计算,定位的基本方法,三边测量法三角测量法极大似然估计法Min-max算法,三边测量法,已知A、B、C三个节点的坐标，以及它们到未知节点D的距离，确定节点D的坐标。,若在测距过程中存在误差，上述三个圆无法交于一点，用存在误差的d1、d2、d3去解上述方程时便无法得到正确解。因此，在实际计算坐标时，一般不采用上述解方程的方法，而采用极大似然估计或其他数值解法。,三边测量法缺点,三角测量法,已知A、B、C三个节点的坐标，节点D相对于节点A、B、C的角度，确定节点D的坐标；转换为三边测量法。,极大似然估计法,已知1、2、3等n个节点的坐标，及它们到未知节点D到距离，确定节点D的坐标；最小均方差估计算法。,极大似然估计法,使用标准的最小二乘法可以得到未知节点的坐标为,Min-max算法,Min-Max算法的基本思想是依据未知节点到各锚节点的距离测量值及其坐标构造若干个限制框(bounding-box)，即以锚节点为圆心，未知节点到该锚节点的距离测量值为半径所构成圆的外接正方形，正方行交叉区域的几何中心即为未知节点的估计坐标。如下图所示，说明了有3个锚节点估计距离时的工作原理，锚节点A（xi,yi)的限制框的4个顶点的计算如下式所示：为未知节点M到锚节点A的测量距离。,Min-Max算法,这些限制框的交集通过下式计算。当未知节点可利用的锚节点多于3个时，将其转化为组分别计算并取其平均值。,主要内容,1引言,2定位技术分类,3DV-HOP定位算法,4性能指标,DV-HOP算法,DV-HOP定位算法具有方法简单，定位精度较高的特点，它是利用距离矢量路由和GPS定位的思想提出的一系列分布式定位方法之一。,DV-HOP算法的3个阶段,第1阶段：网络中的各参考节点通过典型的距离矢量交换协议向邻居节点广播自身位置信息分组，使得网络中的所有节点获得距参考节点的最小跳数信息。,左图是一个由9个节点组成的小型传感器网络。L1L2L3为三个参考节点剩余的都为未知节点，对节点A定位,DV-HOP算法的3个阶段,：为锚节点i与锚节点j的坐标,：为锚节点i与锚节点j之间的实际距离,：为锚节点i到锚节点j之间的跳数,：以锚节点i为基准，计算出的平均每跳距离,M：锚节点总个数,：锚节点i的平均每跳距离的权值,DV-HOP算法的3个阶段-无偏估计准则,第2阶段：每个参考节点利用其它参考节点的位置信息和相隔最小跳数来计算平均每跳距离，并将其作为一个校正值广播至网络中。当接收到校正值后，节点根据跳数计算与参考节点之间的距离。,平均每跳距离,当获得每个参考节点的平均每跳距离后，需要将其广播至网络中的其他节点。未知节点接收到的平均每跳距离有两种方法：方法1中未知节点仅记录接收到的第1个平均每跳距离，并转发给邻居节点；方法2中未知节点记录其到每个参考节点的不同的平均每跳距离。方法1确保了绝大多数节点从最近的参考节点接收平均每跳距离值，也就是说，在方法1中将从最近参考节点接收的平均每跳距离作为整个网络的平均每跳距离。但由于网络中节点分布的随机性，需要尽可能多地利用网络中的信息，采用方法2将具有比采用方法1更优越的性能。,平均每跳距离,归一化处理得到权值,通过这个加权过程，使得定位节点的平均每跳距离能从多个信标节点的平均每跳距离中得到反映，使得定位节点的平均每跳距离更接近于网络的实际平均每跳距离。,DV-HOP算法的3个阶段-最小均方误差准则,第2阶段：每个参考节点利用其它参考节点的位置信息和相隔最小跳数来计算平均每跳距离，并将其作为一个校正值广播至网络中。当接收到校正值后，节点根据跳数计算与参考节点之间的距离。,DV-HOP算法的3个阶段,第3阶段：当未知节点获得与3个或更多参考节点的距离时，根据三边测量法或极大似然估计法来计算未知节点的位置。,分析：在通信范围内无论其相距多远，都将其跳数估计为一跳，而每跳的距离不同，用跳数乘以平均跳距来计算锚节点与未知节点的距离，必然偏离实际距离，造成节点定位出现较大的误差。如图2中的锚节点L1与锚节点L2之问的最短路径，其中每跳的长度都不同，只有最后一跳的长度接近于实际值，即节点的通信半径。,DV-HOP算法的改进1-跳数修正,DV-HOP算法的改进1-跳数修正,定义1：两锚节点i与j之间的实际距离与所有节点的通信半径R之比定义为理想跳数，用Hij表示，即：Hij=dij/R。定义2：节点间实际跳数与理想跳数的相对误差定义为偏离因子，用表示，即：定义3：假设锚节点i与j之间的实际跳数为，偏离因子为，定义跳数修正系数为其中n取正整数，仿真结果表明，n为2时，定位效果最佳。,DV-HOP算法的改进1-跳数修正,锚节点间的跳数：未知节点计算距其最近锚节点的跳数未知节点计算距其他锚节点的跳数,未知节点计算距其最近锚节点的跳数,DV-HOP算法的改进1-跳数修正,为距离未知节点最近的锚节点i与其它锚节点偏离因子的平均值，该平均值充分利用了各个锚节点的跳数信息，更能反映节点在整个网络的特性。由于未知节点p距离锚节点i最近，所以它与锚节点i的网络特性更接近，因此用锚节点i的平均偏离因子近似代替未知节点p与锚节点i之间的跳数偏离因子，造成的跳数误差更小。,DV-HOP算法的改进1-跳数修正,未知节点计算距其他锚节点的跳数,在实际网络中大多数未知节点到任两锚节点的路径会有部分重叠，因此用两锚节点间的偏离因子更能体现未知节点距离其它锚节点跳数偏离程度。,DV-HOP算法的改进2-估计坐标的迭代求精,未知节点到各个参考节点的初步估计距离为d1d2,对（2）式在估计坐标（x0,y0）处进行泰勒展开，并忽略高阶偏导数的影响，得到,（3）,（1）,（2）,将(3)代入(1)中，求解方程组，可得到坐标修正步长h,k。设定判断条件：,DV-HOP算法的改进2-估计坐标的迭代求精,（4）,若上式成立，则停止计算，否则取步长为，即,代入式（3）重新计算，直到满足式（4）的精度门限要求，最后迭代结果即为所求节点坐标,三维DV-HOP算法,主要是对传统的DV-Hop算法的三维扩展，并在其基础上分别通过引入移动代理、用均方误差和归一化加权处理平均每跳距离、判断参与定位的信标节点的有效性等方法分情况采用总体最小二乘法、平移坐标法和画圆法进行定位。,平移坐标法,P1P2P3为选取的三个信标节点，m为待定位的节点，对原三维坐标系进行平移变换，使得P1为新坐标系的坐标原点，P1P2P3全在或近似在XY平面上。根据几何知识可以得到m点的坐标。,画圆法,用三边测量法和极大似然估计法来计算待定位节点的坐标需要三个或三个以上的锚节点位置信息。当未知节点通信范围内的锚节点数为2或者通信范围内的任三个锚节点共线时，可采用画圆法进行定位。未知节点与两个锚节点在一个平面上，分别以锚节点为圆心，以它们到未知节点的距离为半径画圆。如果交与一点，则为所求点坐标；若交与两点，则取两交点的中点为所求点坐标。二维或者三维空间都可以使用画圆法，这样可以减少不可定位的节点以及定位误差。,主要内容,1引言,2定位技术分类,3DV-HOP定位算法,4性能指标,性能指标,定位精度一般用误差值与节点无线通信半径的比值来表示传感器节点的定位精度。定位精度只要不大于40，就能够满足绝大多数应用的要求。,定义平均定位误差eerror为所有未知节点的估计值与实际值的差值的平均值：定义归一化平均定位误差为平均定位误差error与通信半径R的比值：,性能指标,(2)节点密度一般来说，网络中节点密度越大，定位精度越高。DV-Hop算法只能在节点分布比较密集的无线传感器网络中才能合理地估算平均每跳距离，然后才能较准确地估算出节点的位置。,(3)锚节点密度因为人工部署锚节点的方式受到网络所处自然环境的限制；而搭载GPS模块的锚节点成本会