DV—Hop算法及改进

1、传感网DV-Hop定位算法研究与改进Part1项 目 背 景01010202是一种全新的信息获取和处理技术,可以自组织网络拓扑结构,节点间通过协同工作能够实时监测，感知和采集各种环境或监测对象的信息，并对其进行处理。是无线传感器网络众多研究领域中的核心技术之一，是无线传感器网络用于目标监测、目标识别以及目标跟踪等应用的支撑。无线传感器网络及节点定位无线传感器网络（WSN）节点定位技术0303定位算法从定位手段上分有两大类，基于测距算法(range-based)和无需测距算法(range-free)。虽然基于测距的算法能够实现精确定位，但对无线传感器节点的硬件要求高。出于硬件成本、能耗等考虑，人

2、们提出了无需测距算法，如质心算法、DV-Hop 算法、Amorphous 算法、APIT 算法等，不需要测量节点间的绝对距离或方位，可降低对节点硬件的要求，但定位误差也将相应有所增加。定位技术现状DV-Hop 算法是由算法是由D.Niculescu和和B.Nath等人提出的。等人提出的。DV-Hop 定位算法的原理与经典的距离矢定位算法的原理与经典的距离矢量路由算法比较相似。在量路由算法比较相似。在DV-Hop算法中，锚节点向网络广播一个信标，信标中包含有此锚节点算法中，锚节点向网络广播一个信标，信标中包含有此锚节点的位置信息和一个初始值为的位置信息和一个初始值为1的表示跳数的参数。此信标在网

3、络中被以泛洪的方式传播出去，信的表示跳数的参数。此信标在网络中被以泛洪的方式传播出去，信标每次被转发时跳数都增加标每次被转发时跳数都增加1。接收节点在它收到的关于某一个锚节点的所有信标中保存具有最。接收节点在它收到的关于某一个锚节点的所有信标中保存具有最小跳数值的信标，丢弃具有较大跳数值的同一锚节点的信标。通过这一机制，网络中所有小跳数值的信标，丢弃具有较大跳数值的同一锚节点的信标。通过这一机制，网络中所有节点都节点都获得了到每一个锚节点的最小跳数值。获得了到每一个锚节点的最小跳数值。为了将跳数值转换成物理距离，系统需要估计网络中平均每跳的距离。锚节点具有到网络内为了将跳数值转换成物理距离，系

4、统需要估计网络中平均每跳的距离。锚节点具有到网络内部其他锚节点的跳数值以及这些锚节点的位置信息，因此锚节点可以通过计算得到距其他锚节点部其他锚节点的跳数值以及这些锚节点的位置信息，因此锚节点可以通过计算得到距其他锚节点的实际距离。经过计算，一个锚节点得到网络的平均每跳距离，并将此估计值广播到网络中，称的实际距离。经过计算，一个锚节点得到网络的平均每跳距离，并将此估计值广播到网络中，称作校正值。任何节点一旦接收到此校正值，就可以估计自己到这个锚节点的距离如果一个节点能作校正值。任何节点一旦接收到此校正值，就可以估计自己到这个锚节点的距离如果一个节点能够获得到够获得到3个以上锚节点的估计距离个以上

5、锚节点的估计距离，DV-Hop算法与基于测距算法具有相似之处，就是都需要获算法与基于测距算法具有相似之处，就是都需要获得未知节点到锚节点的距离，但是得未知节点到锚节点的距离，但是DV-Hop 获得距离的方法是通过网络中拓扑结构信息的计算而获得距离的方法是通过网络中拓扑结构信息的计算而不是通过无线电波信号的测量。不是通过无线电波信号的测量。DV-Hop算法简介DV-Hop算法流程泛洪各节点收集最小跳数信标节点计算平均每跳距离未知节点获取最近信标节点的平均每跳距离未知节点用最小二乘法估算位置未知节点估算到信标节点的距离Part2研 究 概 况DV-Hop算法的误差分析由于传感器节点随机分布和广播分

6、组过程中可能存在冲突等因素，节点得到的到信标节点的最小跳数存在有一定偏差，且跳数越多，偏差越大。1 1在信标节点估算平均每跳距离时，所利用的是除本节点外所有其他信标节点，所以得到的是全网络范围内的平均每跳距离，不能反映本信标节点局部范围内的网络分布情况。2 2位置节点在最后阶段估算自身位置时，利用最近的信标节点的平均每跳距离，不能反映出该未知节点局部范围内的网络分布情况。3 31利用全部信标节点的平均每跳距离求平均作为标准2设置跳数阀值，筛选对未知节点影响最大的信标节点3采取加权利用信标节点的平均每跳距离4Matlab自动随机生成无线传感器拓扑仿真改进方案引入加权系数引入临界值临界值的作用是排

7、除不合法的数据或是会对结果产生过多负面影响的数据。引入临界值的好处是使结果更加精确，符合实际。临界值即为跳数。在定位过程中，未知节点A利用距离其最近的三个信标节点的平均每跳距离。然而，当信标节点与未知节点间跳数很多，即认为此信标节点距离未知节点很远，对其位置的影响甚微或是会对未知节点的最终位置估计产生负面影响，此时，可排除此信标节点参与未知节点的定位。Part3成 果 展 示平均误差： 3.3247m平均平均误差： 3.1m改进前01020304050607080901000102030405060708090100* 红 色 信 标 节 点 . 黑 色 未 知 节 点01020304050607080900123456每 个 未 知 节 点 的 误 差平均误差： 2.5354m平均平均误差： 2.6m改进后01020304050607080901000102030405060708090100* 红 色 信 标 节 点 . 黑 色 未 知 节 点010203040506070809000.511.522.533.544.55每 个 未 知 节 点 的 误 差1 1引入加权系数，突出锚节点在定位过程中的作用，以及最近锚节点对未知节点的定位影响程度。2 2算法改进灵活