DV-Hop定位算法的改进

基于DV-Hop定位算法的改进摘要：提出了一种改进的DV-Hop定位算法，通过对DV-Hop算法的局部优化，减小了定位计算量，并使得改进的DV-Hop算法对不规则形状的节点分布网络具有较强的适应性，克服了原算法只适用于各向同性网络的不足。仿真结果表明，改进的DV-Hop算法减小了用于定位的通信开销，提高了定位精度，从而验证了改进的DV-Hop算法能够适用于节点不规则分布的异性网络。无线传感器网络是当前在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域.对于传感器网络来说，传感器节点的位置信息至关重要，事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息，没有位置信息的监测数据往往毫无意义。因受成本、功耗、扩展性等问题的限制，为每个传感器安装GPS模块等这些传统定位手段并不实际，甚至在某些场合可能根本无法实现，而且GPS定位在定位精度、实时性方面有时并不能满足特定的需求，因此针对具体的定位需求，必须采用一定的算法机制来实现传感器节点的定位。无线传感器网络节点按定位过程中是否需要测距信息，可分为无需测距的定位方法和基于测距技术的定位方法。近年来，关于传感器网络节点定位技术研究成为无线传感网络技术的一重要研究热点并取得大量的研究成果。其中，具有代表性算法研究成果有：凸规划算法及其改进算法,APS算法、CooperativeRanging、AHLos算法、nHopMultilaterationPrimitive算法、MDS-MAP算法等。无需测距的定位方法被认为是一类具有好的成本效益的解决方案。在无需测距定位方法中，DV-Hop节点定位方法由于对信标节点比例要求较少，定位精度较高，目前已成为一种经典的无需测距定位方法。DV-Hop定位方法的主要思想是引入最短路径算法到信标节点的选择过程中，从而在未知节点的位置估计过程中可以有效利用多跳信标节点的位置信息，这种方法可以大大减少实现网络定位所需信标节点的比例（密度），从而大大降低网络的布置成本。1DV-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的位置。图1DV-Hop算法示意图DV-Hop算法采用平均每跳距离来估算实际距离，对节点的硬件要求低，实现简单。其缺点是利用跳段距离代替直线距离，存在一定的误差。2DV-Hop算法误差分析在DV-Hop定位算法中，算法的第1阶段，由于传感器节点随机分布和广播分组过程中可能存在冲突等因素，节点得到的到信标节点的最小跳数存在有一定偏差，且跳数越多，偏差越大。在信标节点采用式（1）估算平均每跳距离时，所利用的是除本节点外所有其他信标节点，所以得到的是全网络范围内的平均每跳距离，不能反映本信标节点局部范围内的网络密度分布情况。因此，采用该方法得出的平均每跳距离在密度均匀的各向同性网络中影响不大，但在密度不均匀的各向异性网络中，就会造成较大的误差。在DV-Hop算法的第3阶段，未知节点利用了到所有信标节点的距离信息，而据前面的分析，未知节点到信标节点的最小跳数可能有偏差，跳数越多，偏差越大，且第2阶段得出的平均每跳距离也只是对实际距离的一种估算，不可避免会存在着误差，这样信标节点距未知节点跳数越多，二者之间的跳段距离估算误差就越大，利用较远信标节点的距离信息参与位置计算，反而可能降低了定位结果的精确度。3DV-Hop算法改进根据上面的分析，本文对DV-Hop算法加以改进，改进后的方法计算过程仍与原DV-Hop算法大致相同，下面仅对改进之处加以说明。在DV-Hop算法的第1阶段，信标节点向邻居节点广播自身位置信息的分组时，该分组加上生存期字段n,其它节点在转发该广播包时，首先检测生存期字段，如果n大于1,则n=n-1,转发广播包；如果n不大于1,则不再转发该广播包，以保证该分组仅在n跳范围内广播。这样每个节点仅收到n跳范围内信标节点信息，降低了原DV-Hop算法全网洪泛造成的高通信开销、高分组冲突概率。在DV-Hop算法的第2阶段，利用式（1）估算平均每跳实际距离时，信标节点j取自该节点n跳范围内跳数最少的m个信标节点。这样处理保证估算的平均每跳实际距离更符合该节点附近的节点分布，提高了距离估计精确度，并使该方法适用于各向异性网络。最后，在未知节点利用极大似然估计法计算自身坐标时，由于信标距离该未知节点跳段越近，二者之间的距离估计越精确（概率意义上），所以这里只取跳段距离最近的l个节点进行极大似然估计法运算。这样既提高了定位精确度，又降低了节点的计算开销。参数n、m、l的取值要综合考虑信标节点比例、网络的连通度、传感器节点分布等因素。一般情况下，n要保证绝大部分未知一个节点能收到3个以上的信标节点分组，而m、l取4~6即可取得相对高的精确度。4仿真分析为了评估所提出的改进算法的可用性和有效性，利用Matlab7.0对DV-Hop算法及本文提出的改进算法（ImprovedDV-Hop,IDVHop）进行了实验仿真，并对相关实验结果进行分析。仿真分析的网络模型的标准参数如下：设定节点射频通信距离是10个长度单位，网络规模为400个节点，均匀随机分布在边长为100个长度单位的正方形中（这时的平均连通度为11左右），其中信标节点比例为5%.在相同的网络场景下，通过改变总节点数来改变网络的连通度，从而实现相同网络场景下不同网络连通度的仿真实验条件。为消除随机性产生的误差，所得仿真结果均为同样参数下仿真100次所得结果的平均值。（1）可定位节点比例。可定位节点比例（也称算法覆盖率）是指通过定位算法成功实现位置估计的未知节点数量占网络中所有未知节点数量的百分比。通过仿真结果（图2,IDV-Hop算法中n取值为3）。图2可定位节点比例可以看出，两种算法的可定位节点比例均和网络的平均连通度、信标节点比例、算法中分组广播的生存期字段的取值都有关系；在同样的参数条件下，IDV-Hop算法的可定位节点比例和DV-Hop算法相比要低若干个百分点，这是因为在算法第1阶段，可控洪泛使得部分未知节点收到的信标节点小于3而不能实施第3阶段的定位运算。图3数据包发送量（2）数据包发送量。图3为网络连通度为9和12时时，DV-Hop算法与IDV-Hop算法在数据包发送量上的比较，其中横坐标表示信标节点所占的比例，分组广播的生存期字段均取3,IDV-Hop算法中的n取值为3.从图中可以看出，络的数据通信量随信标节点比例和网络连通度的增加而增加。而在同样的网络参数下，IDV-Hop算法的数据通信量远小于DV-Hop算法（不到原通信量的20%）,这主要是由于在算法的第1阶段，IDV-Hop采用的部分洪泛代替了DV-Hop算法全网范围洪泛的缘故。另外，IDV-Hop算法的数据通信量与还与n的选择有关，当n较小时，该算法限制洪泛跳数范围内小，所需的数据通信量就小，但n值也不是越小越好，如前面分析，较小的n值会降低算法的可定位节点比例。（3）定位精度。定位误差（LocalizationError,LE）指的是通过定位算法得到的未知节点的估算位置与实际位置的偏差，这种偏差可以用两者之间的欧氏距离除以节点的通信半径来衡量，如式（2）所示。显然定位误差的大小能最直接说明算法的有效性。其中（xea,yea）为未知节点的估算位置，（xa,ya）为未知节点的实际位置，R为节点的通信半径。图4节点均匀分布时的定位精度图4给出了传感器节点均匀分布时，DV-Hop算法和IDV-Hop算法定位精度比较结果。可以看出，在各向同性网络中，在相同的网络连通度和信标节点比例下，改进后的算法比原算法定位精度均有所提高，特别是在大于6%时，IDV-Hop算法的定位精度随着信标节点比例升高而迅速提高，而原DVHop算法提高并不明显，这是由于信标节点比例越高，IDV-Hop算法越有机会采用距离估计精确度较高的邻近信标节点进行定位运算，从而提高了定位精度，验证前面对DV-Hop算法的分析。图5为传感器节点非均匀分布时（节点分布从左到右逐渐由疏变密），DV-Hop算法和IDV-Hop算法定位精度结果。与图4相比，DV-Hop算法定位精度大幅下降，而IDV-Hop算法仅稍有下降。在同样的网络参数下，IDV-Hop算法的定位精度比DV-Hop算法提高了大约20%,可见改进后的算法更适用于各向异性网络。图5节点不均匀分布时的定位精度5结语本文分析了DV-Hop算法只适用于各向同性网络的原因，对DV-Hop算法进行局部性优化，给出了无线传感器网络无需测距DV-Hop定位的改进算法。仿真结果表明，改进后的算法可定位节点比例略有下降，但提高了定位精度，特别是节点非均匀分布时的定位精度，减少了数据包发送量，因此更适用于在实际项目中应用。