无线传感器网络DV-Hop 定位算法的改进

邱奉美，李怀忠，2

(1.温州大学物理与电子信息工程学院，浙江 温州 325035;2.埃迪斯科文大学计算机与安全科学学院，澳大利亚 柏斯6050)

1 概述

无线传感器网络(Wireless Sensor Network，WSN)是由部署在监测区域内的大量廉价微型传感器节点，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者［1］。WSN 被广泛应用于诸多领域，已成为计算机和通信领域的研究热点。

基于WSN 的大量应用都离不开节点位置信息。节点定位技术属于WSN 应用支撑技术，在WSN 体系中占有重要地位［2］。无线传感器节点通常随机布放在不同的环境中执行各种监测任务，以自组织的方式互相协调工作。随机布放的传感器节点无法事先预知自身位置，传感器节点必须能在布放后实时进行定位。对大多数的应用，不知道节点位置而感知的数据是没有意义的。WSN 中的节点自定位问题已成为一个重要的研究方向。网络节点定位必须满足低能耗、低成本、低复杂性和高精度的定位性能［3］。

近几年中国学者在非测距定位领域取得了国际领先成果，例如，刘云浩教授领导的科研团队开展了基于非测距的无线网络定位理论与方法研究，率先实现了基于无线射频识别技术的非测距定位系统LANDMARC，突破了无线多跳网络下的非测距定位算法各向异性的瓶颈，在煤矿安全监测、海洋环境监测、森林碳汇和城市碳排放与空气质量监测等应用中进行了实验验证，并在绿野千传和CitySee 系统中进行了成功的大规模应用实践［4］。

目前，应用较广且研究较热的WSN 自定位算法分为2 类:基于测距定位算法与无需测距定位算法［5］。基于测距的定位算法需要外在硬件设备的支持，利用节点间信号强度或者角度信息，计算未知节点坐标;无需测距定位算法，较基于测距定位算法实现简单，无需外在硬件设备，只需通过锚节点信息及整个网络连通度来估计未知节点的坐标。因此，这类定位算法日趋受到关注。典型无需测距定位算法包括质心算法、Amorphous 算法、APIT 算法以及DVHop 算法［6］等。其中，DV-Hop 算法是无需测距定位算法中应用最广泛的算法之一。

本文首先简单介绍传统DV-Hop 算法基本思想，讨论传统算法存在的不足和相关改进方案，针对已有改进算法仍存在的不足提出一种改进算法，并以平均定位误差和覆盖率作为定位性能的主要评价标准，分别对锚节点比例、节点个数以及通信半径等3个因素对平均定位误差的影响进行仿真，同时在不同锚节点比例时对覆盖率的影响进行仿真，并将本文的改进算法与传统DV-Hop 算法及其他改进算法进行比较。

2 DV-Hop 算法

2.1 DV-Hop 算法简介

DV-Hop 算法是利用距离矢量路由和GPS 定位原理的分布式定位算法APS(Ad hoc Positioning System)中的一种。图1 是9 个节点小型网络，其中，L1，L2，L3 为锚节点，D 为未知节点，以此网络为例阐述DV-Hop 算法。

算法定位过程分为3 个阶段:

(1)计算未知节点与每个锚节点的最小跳数。

锚节点向邻居节点广播含锚节点编号IDi，坐标(xi，yi)以及跳数字段di(初始化为0)的数据包。接收节点记录到各锚节点的最小跳数，忽略同一锚节点的较大跳数的数据包。将跳数加1 后转发给邻居节点。所有节点就能够记录到各锚节点的最小跳数。如图1 所示，D 到L1，L2，L3 的最小跳数分别为2，3，3，锚节点Ll，L2，L3 彼此间的跳数分别为2，5，6。

图1 小型网络结构

(2)计算未知节点和锚节点的实际跳段距离。

各锚节点根据一阶段中记录的其他锚节点的位置和跳数信息，利用式(1)估算自身的跳段距离。

其中，(xi，yi)和(xj，yj)是锚节点i，j 的坐标;hj是锚节点i 与j(j≠i)之间的跳段数。

锚节点间距由欧氏距离公式计算，如图1 所示分别为40 m，75 m 和100 m。由式(1)得锚节点L1，L2，L3 的跳段距离分别为:HopSize1=(40+75)/(2 +5)=16.43 m，HopSize2=(100 +40)/(6 +2)=17.5 m，HopSize3=(100 +75)/(6 +5)=15.91 m。然后，锚节点将计算的跳段距离用带生存期字段的分组广播至网络中，未知节点仅记录最近锚节点广播的跳段距离，并转发给邻居节点。未知节点到各锚节点的距离由式(2)计算可得:

以图1 为例，锚节点L1，L2，L3 向整个网络广播它们计算所得的跳段距离，未知节点D 即可收到它们的广播。未知节点D 距L1 的跳数最少，因此，它最先接收到L1 的跳段距离将其作为平均跳距，并忽略其他跳段距离。由式(2)可得:节点D 到L1，L2，L3 的距离分别为2×16.43 m，3×16.43 m，3×16.43 m。

(3)三边测量法或极大似然估计法计算自身位置。

未知节点利用二阶段中记录的到各锚节点的距离，利用三边测量法或极大似然估计法计算自身坐标。极大似然估计法介绍如下:已知n 个锚节点坐标为(xi，yi)，其中，i=1，2，…，n，锚节点到未知节点(x，y)距离分别d1，d2，…，dn，则得式(3):

第1 个方程依次减去最后一个方程得到式(4):

向量表示为AX=B，其中:

由式(5)标准最小均方差估计法可得D 的坐标为:

2.2 DV-Hop 算法存在问题及相关解决方案

针对DV-Hop 算法，国内外研究者提出了很多算法改进，文献［7-8］的算法在未知节点到锚节点的路径中，考虑相邻3 个节点组成的夹角对距离的影响，根据邻近节点重叠度计算夹角。引入网络平均连通度计算节点间跳距，从而更精确地计算距离。在文献［9］的改进算法中，锚节点通过实际距离和估计距离的误差来修正平均跳距，采用新的二维双曲线定位算法计算节点坐标。文献［10］提出基于加权处理的平均跳距估计算法，根据距离未知节点的跳数和环境影响因素进行加权。文献［11］的改进算法通过共线性检查证明锚节点的有效性，分别用最小均方误差准则、归一化加权和总体最小二乘法进行定位，然后升级已定位未知节点为锚节点定位其他未知节点。文献［12］针对存在障碍物情况，引入信任度概念，提出一种基于信任度的改进算法，通过对信任度值的判断筛选合适的平均跳距值。以上改进算法在一定程度上提高了定位精度和覆盖率，但仍存在以下不足:

(1)平均跳距的估算很大程度决定了DV-Hop定位算法的定位误差。目前平均跳距是接收最近锚节点广播的平均每跳校正值。这样所得的平均跳距的估算值很粗糙，有待改进以获得更准确的估计值。

(2)算法对锚节点密度有一定的要求，当锚节点相对稀疏时就需要对算法进行改进，使之能适用于节点稀疏场景的相关应用。

(3)DV-Hop 定位算法对跳数具有一定的依赖，节点间最小跳数的计算对定位精度有很大的影响，当跳数为1 时，存在一跳定位误差问题，如果将未知节点和仅一跳间隔范围的锚节点之间的距离，简单地等同平均跳距值，将导致多个未知节点的定位重合或者定位误差增大。

(4)网络中存在障碍物时，对最短路径选择造成影响，使得跳段距离估算误差较大。

本文针对DV-Hop 节点定位算法三阶段和平均跳距估计误差问题，从以下3 个方面进行改进:

(1)对算法第2 阶段中所得平均跳距进行加权处理，得到一个与实际更为接近的平均跳距。

(2)对最后定位出的未知节点坐标进行修正。

(3)升级已定位未知节点为锚节点定位其他未知节点。相当于增加锚节点密度，从而提高定位覆盖率。

3 本文改进算法

3.1 加权平均跳距

在传统的DV-Hop 算法中，算法主要误差来源于:用跳段数与未知节点接收离其最近的一个锚节点广播的平均跳距的乘积，即由式(2)计算未知节点与锚节点之间的距离。当平均跳距的估计值与实际值偏差较大时，计算所得的未知节点估计距离与实际距离之间的误差会增大。平均跳距误差分析如图2所示。其中，实线表示节点可以直接通信;虚线表示节点不能直接通信，需要中间节点的过度。

图2 平均跳距误差分析示意图

由2.1 节中式(2)计算出未知节点D 到L1，L2和L3 的距离为2 ×16.43=32.86 m，3 ×16.43=49.29 m，3 ×16.43=49.29 m，如图2 中虚线所示，显然虚线距离(即真实距离)与计算所得距离有一定的偏差，因此，本文采用基于未知节点到锚节点跳数的加权来计算平均跳距，即通过式(6)求平均跳距:

其中，ni是未知节点到锚节点的跳数;Hopsizei是传统DV-Hop 算法中各锚节点计算所得跳段距离。

3.2 未知节点位置坐标修正

在传统的DV-Hop 算法定位出未知节点位置坐标的基础上，本文改进算法以最近锚节点坐标作为参照对原算法定位出的未知节点坐标进行修正，其修正方法如下:设定位出未知节点的坐标为(xj，yj)，最近锚节点坐标，在DV-Hop 算法定位机制中，未知节点仅接收距其最近锚节点转发的平均跳距，所以，在修正策略中，以最近锚节点位置作为参照，引入一个与跳数相关的动态权值α，若未知节点估计坐标偏离最近锚节点，通过权值修正策略将坐标修正为相对更接近锚节点的位置。具体修正策略如下:当时，修正坐标为((1+α)xj，yj);当时，修正坐标为((1 -α)xj，yj);当时，修正坐标为(xj，(1 +α)yj);当时，修正坐标为(xj，(1 -α)yj)。

其中，ni是未知节点到锚节点的跳数这样获得的修正未知节点坐标更接近实际坐标。

如图3 所示，当估计位置为E1(x1，y1)时，其在最近锚节点的正右方，故位置修正为((1 -α)x1，y1);当估计位置为E2(x2，y2)时，其在最近锚节点的左上方，故位置修正为((1 +α)x2，(1 -α)y2);当估计位置为E3(x3，y3)时，其在最近锚节点的左下方，故位置修正为((1 +α)x3，(1 +α)y3);当估计位置为E4(x4，y4)时，其在最近锚节点的右下方，故位置修正为((1 -α)x4，(1 +α)y4)。

图3 位置修正策略示意图

3.3 改进算法实现步骤

在本文改进算法的运算过程中，针对传统DVHop 算法平均跳距估算比较粗糙，引入基于未知节点到锚节点跳段数的加权平均跳距，加权平均跳距的估算方法参照3.1 节;同时采用最小二乘法来计算未知节点的位置坐标;最后，由于未知节点接收离其最近的锚节点转发的平均跳距，本文引入坐标修正策略，参照3.2 节。这样获得的修正未知节点的坐标更接近实际坐标。本文改进算法实现步骤如下:

(1)网络初始化。

本文算法相关主要参数变量如下:

anchors_n:网络锚节点的个数;

nodes_n:网络节点的个数;

square_L:方形监测区域边长;

comm_r:节点间通信距离;

all_nodes.true=unifrnd(0，square_L，nodes_n，2):所有节点真实坐标矩阵，包括横纵坐标，与square_L 和nodes_n 有关;

all_nodes.estimated:所有锚节点估计坐标矩阵(考虑到GPS 误差)，包括横纵坐标;

hopsize(1:all_nodes.anchors_n):每个锚节点的跳段距离;

Hopsize:式(6)所求得平均跳距;

alpha:位置修正策略引入的动态权值α。

(2)锚节点广播包含节点ID、自身位置信息、跳数信息的数据包，跳数初始化为0。

(3)未知节点和其他锚节点接收锚节点的数据包，各节点计算最小跳数。

未知节点和其他锚节点接收锚节点的数据包，待广播结束后，判断未知节点是否收到3 个或3 个以上锚节点信息，是则锚节点开始计算与其他锚节点的距离，否则未知节点不能定位。

(4)每个锚节点估计校正值:根据式(1)计算每个锚节点估计校正值HopSizei。

(5)锚节点根据式(6)计算其平均跳距并全网广播。

(6)未知节点根据最小二乘法定位出其位置坐标。

(7)对定位出的未知节点位置坐标进行修正。

参照3.2 节的修正策略根据未知节点与距其最近锚节点的坐标位置关系进行位置修正，并将修正后的坐标作为未知节点最终定位的坐标，整个定位过程结束。本文算法流程如图4 所示。

图4 本文改进算法流程

4 仿真结果与分析

为验证本文改进算法性能，用Matlab7.11.0 软件对改进算法进行仿真，本文将基于100 次仿真统计结果的平均定位误差和覆盖率作为评价指标，并与传统DV-Hop 算法及文献［10］和文献［11］提出的2 种改进算法进行比较。

仿真网络环境如下:传感器节点随机分布在100 m× 100 m 的正方形区域内，设所有节点的通信半径均为R，分别在不同锚节点比例、不同节点个数和不同通信半径等3 个因素下对传统算法、文献［10］改进算法和本文改进算法的定位误差进行研究。在保持节点个数不变，锚节点个数不同时，R 为15 m 和25 m 2 种情况下，对传统算法、文献［11］改进算法和本文改进算法的覆盖率进行研究。对在WSN 中，定义平均定位误差为估计位置到真实位置的欧式距离与通信半径的比值，如式(8)所示:

定位覆盖率定义为:可定位节点数/未知节点总数。

图5 给出了总节点数200 个，通信半径为15 m 情况下节点平均定位误差与锚节点比例的关系曲线。由仿真结果可知，3 种算法的平均定位误差均随总节点数量的增加而减小，并逐渐趋于稳定。本文算法较DV-Hop 算法，平均定位误差整体平均降低12.55%，较文献［10］的改进算法整体平均降低了3.42%。

图5 平均定位误差与与锚节点比例的关系

图6 给出了锚节点比例为10%，通信半径为15 m情况下节点平均定位误差与总节点个数的关系曲线。

图6 平均定位误差与节点个数的关系

由仿真结果可知，3 种算法的平均定位误差随总节点数量的增加而减小，并逐渐趋于稳定。本文算法较DV-Hop算法，定位误差整体平均降低15.38%，较文献［10］改进算法的整体平均降低3.78%。

图7 给出锚节点比例为15%，即30 个锚节点、节点个数为200 时节点平均定位误差与通信半径的关系曲线。由仿真结果可知，3 种定位算法的平均定位误差随节点通信半径的增加而减小，这是由于增加通信半径相当于增大网络的连通度，节点之间相互通信的机会增加，有效地减小了定位误差。由图7可知随着节点通信半径的增加，3 种定位算法的定位误差都在不断下降。在相同的通信半径情况下，本文算法较DV-Hop 算法，平均定位误差整体平均降低10.26%，较文献［10］改进算法整体平均降低约2.0%。

图7 平均定位误差与通信半径的关系

图8 和图9 给出通信半径R 为15 m 和25 m 2 种情况，节点个数为200 时，锚节点个数在5～40内变化，节点覆盖率与锚节点个数的关系曲线。由仿真结果可知，3 种算法随着锚节点个数增加，覆盖率都有提高。且在相同的锚节点数的情况下，本文的改进算法较传统的DV-Hop 算法及文献［11］改进算法覆盖率更高。这是由于本文改进算法以代替未知节点接收的最近锚节点广播的平均跳距HopSize，将全网广播，这样未接收3 个锚节点信息的未知节点也能接收到再由式(2)计算未知节点到锚节点的距离，同时升级已定位未知节点为锚节点定位其他未知节点，从而提高覆盖率。本文改进算法中R=15 m 时，本文算法较DVHop 算法，随锚节点个数变化覆盖率整体平均提高12.75%，较文献［11］算法整体平均提高1.25%;R=25 m时，本文算法较DV-Hop 算法，覆盖率随锚节点个数变化整体平均提高8.63%，较文献［11］算法整体平均提高1.38%。

图8 覆盖率与锚节点个数的关系(R=15 m)

图9 覆盖率与锚节点个数的关系(R=25 m)

5 结束语

本文算法并没有改变传统DV-Hop 算法的基本定位过程，无需额外的硬件支持，在确保平均跳距估计误差较小的同时，不增加网络通信开销，且对定位出的未知节点坐标进行动态加权修正，在控制计算量的同时，大幅提高了节点的定位精度和覆盖率。仿真结果表明，该算法的定位精度和覆盖率均优于传统DV-Hop 算法和文献［10 -11］改进算法。发现当存在有障碍物时，障碍物将影响未知节点与锚节点之间的最短路径，形成弯曲路径，从而给平均跳距的估算带来误差，影响定位精度。因此，对有障碍物以及稀疏节点场景下DV-Hop 定位算法改进将成为今后主要的研究方向。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(7):102-114.

［2］Qi Hairong，Kuruganti P T，Xu Yingyue.The Development of Localized Algorithms in Wireless Sensor Networks［J］.Sensors，2002，2(7):286-293.

［3］Liu Yunhao，Yang Zheng，Wang Xiaoping，et al.Location，Localization，and Localizability［J］.Journal of Computer Science and Technology，2010，25(2):274-297.

［4］GreenOrbs ［EB/OL］.［2013-09-30］.http://www.greenorbs.org.

［5］Perkins C，Royer E.Ad Hoc on Demand Distance Vector Routing［J］.Mobile System and Applications，1999，24(3):59-81.

［6］Niculescu D，Nath B.DV Based Positioning in Ad-hoc Networks［J］.Journal of Telecommunication Systems，2003，22(4):267-280.

［7］王 颖，石昊旸.改进的无线传感器网络DV-Hop 定位算法［J］.计算机工程，2012，38(7):66-69.

［8］张晓龙，解慧英，赵小建.无线传感器网络中一种改进的DV-Hop 定位算法［J］.计算机应用，2007，27(11):2672-2674.

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

［10］冯 江，朱 强，吴春春.改进的DV-Hop 定位算法研究［J］.计算机工程，2012，38(19):74-77，81.

［11］张 静，曹 敦.DV-Hop 算法定位误差和覆盖率的改进［J］.计算机应用，2011，31(7):1944-1947.

［12］史庭俊，桑 霞，徐力杰，等.一种基于信任度的DVHop 改进定位算法［J］.微电子学与计算机，2008，25(10):101-102.