DV-Hop定位算法的改进..doc

基于DV-Hop定位算法的改进 摘要：提出了一种改进的DV-Hop 定位算法，通过对DV-Hop算法的局部优化， 减小了定位计算量，并使得改进的DV-Hop算法对不规则形状的节点分布网络具有较强的适应性，克服了原算法只适用于各向同性网络的不足。仿真结果表明，改进的DV-Hop 算法减小了用于定位的通信开销，提高了定位精度，从而验证了改进的DV?-Hop算法能够适用于节点不规则分布的异性网络。 　　无线传感器网络是当前在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域 .对于传感器网络来说， 传感器节点的位置信息至关重要，事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没有位置信息的监测数据往往毫无意义。因受成本、功耗、扩展性等问题的限制，为每个传感器安装GPS模块等这些传统定位手段并不实际，甚至在某些场合可能根本无法实现，而且GPS定位在定位精度、实时性方面有时并不能满足特定的需求，因此针对具体的定位需求，必须采用一定的算法机制来实现传感器节点的定位。 　　无线传感器网络节点按定位过程中是否需要测距信息，可分为无需测距的定位方法和基于测距技术的定位方法。近年来，关于传感器网络节点定位技术研究成为无线传感网络技术的一重要研究热点并取得大量的研究成果。其中，具有代表性算法研究成果有：凸规划算法及其改进算法 , APS 算法、Cooperative Ranging 、AHLos 算法、nHopMultilateration Primitive 算法、MDS-MAP 算法等。 　　无需测距的定位方法被认为是一类具有好的成本效益的解决方案。在无需测距定位方法中，DV-Hop节点定位方法由于对信标节点比例要求较少，定位精度较高，目前已成为一种经典的无需测距定位方法。 　　DV-Hop定位方法的主要思想是引入最短路径算法到信标节点的选择过程中，从而在未知节点的位置估计过程中可以有效利用多跳信标节点的位置信息，这种方法可以大大减少实现网络定位所需信标节点的比例（密度），从而大大降低网络的布置成本。 　　　1?? DV-Hop 定位算法 　　DV-Hop定位算法是APS算法系列中使用最为广泛的定位方法，其定位过程不依赖于测距方法，利用多跳信标节点信息来参与节点定位，定位覆盖率较大。DV-Hop 算法非常类似于传统网络中的距离向量路由机制，在该定位机制中，未知节点首先计算与信标节点的最小跳数，然后估算平均每跳距离，利用最小跳数乘以平均每跳距离，估算得到未知节点与信标节点之间的距离，再利用三边测量法或极大似然估计法计算未知节点的坐标。 　　DV-Hop定位算法可以分为以下3个阶段： 　　（ 1） 计算未知节点与每个信标节点的最小跳数。 　　信标节点向邻居节点广播自身位置信息的分组，其中包括跳数字段，初始化为0.接收节点记录具有到每个信标节点的最小跳数，忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加1,并转发给邻居节点。通过这个方法网络中的所有节点能够记录下到每个信标节点的最小跳数。 　　（ 2） 计算未知节点与信标节点的实际跳段距离。 　　每个信标节点根据第1阶段中记录的其他信标节点的位置信息和相距跳数，利用式（1）估算平均每跳的实际距离： 　　其中，（ xi, yi ）、（ xj, yj ）是信标节点i、j 的坐标，hj 是信标节点i与j（ i≠j）之间的跳段数。 　　然后，信标节点将计算的每跳平均距离用带有生存期的字段的分组广播到网络中，未知节点仅记录接收到的第1个每跳平均距离，并转发给邻居节点。这个策略可以确保绝大多数未知节点从最近的信标节点接收每跳平均距离。未知节点接收到平均每跳距离后，根据记录的跳数，计算到每个信标节点之间的距离。 　　（ 3） 未知节点计算自身位置。 　　未知节点利用第2阶段中记录的到各个信标节点的跳段距离，利用三边测量法或极大似然估计法计算出自身坐标。 　　如图1所示，经过第1和第2阶段，能够计算出信标节点L1 与L2、L3 之间的距离和跳数。信标节点L2 计算得到校正值（即每跳平均距离）为（ 40 +75） / （ 2+ 5） = 16. 42.假设未知节点A 从L2 获得校正值，则它与3 个信标节点之间的距离分别为L1: 3?×16. 42, L2: 2?×16. 42, L3: 3×16. 42, 最后可利用三边测量法确定节点A 的位置。 图1?? DV-Hop算法示意图 　　DV?-Hop算法采用平均每跳距离来估算实际距离，对节点的硬件要求低，实现简单。其缺点是利用跳段距离代替直线距离，存在一定的误差。 　　2?? DV-Hop算法误差分析 　　在DV-Hop定位算法中，算法的第1阶段，由于传感器节点随机分布和广播分组过程中可能存在冲突等因素，节点得