一种基于跳数修正的DV-Hop定位算法

肖丽萍，刘晓红

(燕山大学信息科学与工程学院，河北秦皇岛 066004)

无线传感器网络WSN(Wireless Sensor Networks)是由部署在监测区域内的大量廉价微型传感器节点通过无线通信方式形成的一个多跳的自组织的网络系统［1］，其中节点定位技术是其关键技术之一。节点定位是根据本网络内少数位置已知的节点(称为锚节点)，按照某种定位机制来确定其它未知节点位置的过程。根据定位机制可将现有的无线传感器网络定位算法大致分为基于测距(Range-Based)的定位算法和无需测距(Range-Free)的定位算法［2］。前者定位精度相对较高，但需要测量相邻节点之间的绝对距离或方位，且对网络的硬件设施要求也比较高，后者仅根据网络连通性等信息即可实现定位，因此无需测距的定位技术以其低功耗，低成本的优势受到了越来越多的关注。

典型的无需测距的定位算法包括质心算法［3］、DV-Hop 算法［4－5］、APIT 算法［6］和 MDS-MAP［7］算法等，其中DV-hop算法巧妙地将网络的连通信息和距离矢量信息转化为近似的距离测量，是目前研究最广泛的算法之一。文献［8－12］都对该算法进行了不同程度的改进，但是仍然存在较大的定位误差，因此本文提出了一种基于跳数修正的定位算法。

1 DV-Hop算法描述及存在的问题

DV-Hop算法是一种基于距离矢量的分布式定位算法，该算法的实现大致分为3个阶段:

第1阶段 网络中的各锚节点通过典型的距离矢量交换协议向邻居节点广播自身位置信息分组，使得网络中的所有节点获得距锚节点的最小跳数信息。

第2阶段 每个锚节点在获得其它锚节点的位置和相隔的最小跳数信息后，根据下式计算锚节点i自身的平均每跳距离Ci:

式中，(xi，yi)、(xj，yj)为锚节点i与j的实际坐标，dij为锚节点i到其他锚节点的直线距离，且

hopsij为锚节点i与j之间的最小跳数(i≠j)。每个锚节点将计算得到的平均每跳距离以洪泛的方式广播到网络中，未知节点仅记录接收到的第1个平均每跳距离(之后收到的丢弃)，并对该平均每跳距离立即转发，再结合第1阶段记录的最小跳数可近似计算得到与各锚节点的距离。

第3阶段 未知节点得到3个或3个以上锚节点的距离后，再利用三边测量法或极大似然估计算法计算出自身的位置坐标，从而完成定位。

图1 DV-Hop定位算法示意图

假设p为待定位节点，p到锚节点i、j、k的最小跳数分别为hopspi、hopspj和hopspk，其中p与锚节点i之间的距离最短，因此p从锚节点i处获得平均每跳距离值，即Cp=Ci，再结合第1阶段记录的最小跳数便可得到未知节点p到各锚节点的估计距离分别为:Cphopspi、Cphopspj、Cphopspk。然后运用三边测量法计算节点p的位置坐标。

传统的DV-Hop算法不需要直接测量节点之间的距离或角度信息，而是依赖于节点间的跳数。对于各向同性的密集网络，各节点可以得到合理的平均每跳距离，从而达到较高的定位精度，但对于拓扑不规则的网络，定位精度会明显下降。这主要是因为实际应用中WSN的节点一般是随机分布的，锚节点和未知节点之间往往不是直线路径，且节点间实际每跳长度也不尽相同，因此运用相同的平均跳距去估计节点间的距离必定会产生较大的误差。针对上述问题，学者们对其进行了不同的改进，如文献［8］采用最小均方误差法对平均跳距进行修正，并进行了迭代求精；文献［9］引入多维平均跳距的概念来修正平均跳距；文献［10］中对最小二乘法进行了加权；文献［11］利用夹角对平均每跳距离修正；文献［12］用所有锚节点的平均跳距对每个跳距进行修正，同时对不良节点进行了简单处理，这些改进算法在一定程度上都起到了提高定位精度的作用，但仍有不足，本文重点对节点间的跳数进行修正。

2 DV-Hop定位算法的改进

传统DV-Hop定位算法在计算节点间跳数时，在通信范围内无论其相距多远，都将其跳数估计为一跳，而每跳的距离不同，利用公式Cphopspi计算时，必然偏离实际距离，造成节点定位出现较大的误差。如图2中的锚节点L1与锚节点L2之间的最短路径，其中每跳的长度都不同，只有最后一跳的长度接近于实际值，即节点的通信半径，但用传统DVHop定位算法计算锚节点间的最小跳数时仍然记为4跳，这必定会给最后的定位引入较大的误差。

图2 两锚节点间的最短路径

针对以上问题，本文提出了一种新的计算跳数的方法来降低由跳数引入的误差。为了说明本文的改进算法，首先定义几个参数。

定义1两锚节点i与j之间的实际距离与所有节点的通信半径R之比定义为理想跳数，用Hij表示，即:

定义2节点间实际跳数与理想跳数的相对误差定义为偏离因子，用αij表示，即:

其中，hopsij为锚节点i与j之间的实际跳数值。偏离因子反映了节点间平均每一跳偏离理想跳数的程度，αij越大，表明实际跳数偏离理想跳数的程度越大，用此实际跳数代替理想跳数时引入的误差就越大。

定义3假设锚节点i与j之间的实际跳数为hopsij，偏离因子为αij，定义跳数修正系数wij为:

其中n取正整数，当n=2时，定位效果最佳，下面给出本文的跳数修正算法。

2.1 锚节点间跳数

为了尽可能使实际跳数接近理想值，按下式对锚节点间跳数进行修正:

其中，hops'ij为锚节点间修正后的跳数，hopsij为锚节点间的实际跳数。

改进后的跳数与理想跳数的偏差为:

2.2 未知节点到锚节点间跳数的改进

传统DV-Hop定位算法中未知节点计算距离锚节点的距离时采用距离矢量交换协议得到的是整数跳数，实际的跳数并非都是整数，因此由整数跳数计算未知节点到各锚节点的距离的必然存在误差。针对这一不足本文对未知节点与锚节点间的跳数进行了修正。

①未知节点计算距其最近锚节点的跳数

假设未知节点p与锚节点i之间的实际跳数为hopspi，锚节点数为n，本文利用如式(7)进行修正，修正后的跳数为:

②未知节点计算距其它锚节点的跳数

未知节点p计算距其它锚节点的跳数时运用如式(8)进行修正:

式中wij由式(5)得到，hopspj为未知节点与其它锚节点间的实际跳数。在实际网络中大多数未知节点到任两锚节点的路径会有部分重叠［13］，因此用两锚节点间的偏离因子更能体现未知节点距离其它锚节点跳数偏离程度。

3 改进后的算法步骤

改进后的DV-Hop算法如下:

第1阶段:与传统算法相同，所有节点获得到各锚节点的距离和跳数信息。

第2阶段:各锚节点首先运用式(6)修正锚节点间的跳数，然后用修正后的跳数根据式(1)计算每个锚节点的平均每跳距离。

第3阶段:未知节点分别运用式(7)、式(8)修正距其最近锚节点和其它锚节点的跳数，然后结合与其最近锚节点的平均每跳距离计算距离个锚节点的距离。最后对计算出的距离采用二维双曲线定位算法［14］得到未知节点的位置估计坐标。

4 实验仿真及结果分析

为了对改进算法进行验证，本文首先对提出的跳数修正系数中的n取不同正整数值时的性能进行了仿真，并对传统的DV-Hop算法、文献［9］和本文的改进算法进行了仿真对比。仿真的网络环境如下:传感器节点随机分布在100 m×100 m的正方形区域内(假设所有节点的通信半径R都相同)，分别研究在不同的锚节点比例、不同节点个数和不同的通信半径的条件下传统算法和改进算法的定位误差。

在无线传感器网络中，定义平均定位误差error为所有未知节点的估计值与实际值的差值的平均值:

式中(x'i，y'i)和(xi，yi)分别为未知节点的估计位置和实际位置，K为仿真次数，un为未知节点总数。为了消除由于节点随机分布造成的误差的不稳定性，在相同的网络环境下分别进行500次仿真实验，然后取平均值。

定义归一化平均定位误差为平均定位误差error与通信半径R(单位:m)的比值:

图3给出了改进算法在取不同跳数修正系数的情况下，定位误差随锚节点比例的变化曲线。从图中可以看出，当跳数修正因子中n=2时，定位精度最优，所以本文算法中n都取2。

图3 不同修正系数下的定位误差

图4给出了总节点数为100，通信半径为20 m的情况下节点归一化平均定位误差与锚节点比例的关系曲线，由仿真结果可以看出，3种定位算法的归一化平均定位误差都随锚节点比例的增加而减小，并逐渐趋于稳定，但本文改进算法的归一化平均定位误差较传统DV-Hop算法降低了约10% ～15%，较文献［9］降低了约4% ～8%。

图4 节点归一化平均定位误差与锚节点比例的关系

图5给出了锚节点比例为10%，节点通信半径为20 m的情况下节点归一化平均定位误差与总节点个数的关系曲线，由仿真结果可以看出，3种算法的归一化平均定位误差都随总节点数量的增加减小，并逐渐趋于稳定。这是因为节点所在区域不变的情况下，节点总数的增加将会使网络中节点密度增大，从而提高了定位精度。同样，本文算法的误差小于传统DV-Hop算法和文献［9］的算法，而且这种优势在总节点数较少的时候更加突出。

图5 节点归一化平均定位误差与总节点个数的关系

图6给出了锚节点比例为10%时节点平均定位误差与通信半径的关系曲线，由仿真结果可以看出，3种定位算法的平均定位误差都随节点通信半径的增加而增大，这是因为通信半径的增大导致了节点间跳数的误差增大，从而使节点平均跳距误差增大，而传统算法和改进算法都是通过跳数和平均跳距来估计未知节点位置的，所以节点的平均定位误差随着节点通信半径的增大而增大。但在相同的通信半径情况下，本文算法的平均定位误差低于传统DV-hop方法和文献［9］的定位误差。

图6 节点平均定位误差与通信半径的关系

5 结束语

本文针对传统DV-Hop定位算法在随机分布网络环境中的局限性进行了改进。首先对锚节点间的最短跳数进行了修正，之后对未知节点与锚节点间的跳数进行了修正，仿真表明，该改进算法的定位误差明显优于传统算法。该算法并没有改变传统DVHop算法的基本定位过程，且无需额外的硬件支持，具有较好的实用价值。

［1］孙利明，李建中，陈瑜，等.无线传感器网络［M］.北京:清华大学出版社，2005:149－151.

［2］王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，5(16):857－868.

［3］Bulusu N，Heidemann J，Estrin D.GPS-Less Low Cost Outdoor Localization for Very Small Devices［J］.IEEE Personal Communications Magazine，2000，7(5):28－34.

［4］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［5］Niculescu D，Nath B.Ad-Hoc Positioning System(AP-S)［C］//Proc of the 2001 IEEE Global Telecommunications Conf.San Antonio:IEEE Communications Society，2001，2926－2931.

［6］He T，Huang C D，Blum B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］//Proc of the 9th Annual Int’1 Conf on Mobile Computingand Networking.San Diego:ACM Press，2003，81－95.

［7］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proc of the 4th ACM Int’1 Symp on Mobile Ad Hoc Networking＆ Computing.Annapolis:ACM Press，2003，201－212.

［8］林金朝，陈晓冰，刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法［J］.通信学报，2009，30(10):107－113.

［9］胡蜂松，孟湘琴.多维平均跳距值的DV-Hop定位算法研究［J］.计算机工程与应用，2011，47(28):42－44，68.

［10］朱敏，刘昊霖，张志宏，等.一种基于DV-Hop改进的无线传感器网络定位算法［J］.四川大学学报(工程科学版)，2012，44(1):93－98.

［11］王新生，赵衍静，李海涛.基于DV-Hop定位算法的改进研究［J］.计算机科学，2011，38(2):76－78，90.

［12］李辉，熊盛武，刘毅，等.无线传感器网络DV-HOP定位算法的改进［J］.传感技术学报，2011，24(1):1782－1785.

［13］沈明玉，张寅.基于改进的平均跳距和估计距离的DV-Hop定位算法［J］.计算机应用研究，2011，28(2):648－650.

［14］石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法［J］.传感技术学报，2011，24(1):83－87.