无线传感器网络中Dv－hop算法的研究及改进

王丽侠

（唐山学院 信息工程系，河北 唐山063000）

1 Dv－hop算法简介

传感器网络中的数据采用多跳路由的方式传送，每一个节点只与其邻居进行通信，通过这种方式，有限的参考节点能够被更多的未知节点利用，从而降低对参考节点的依赖。Dv－hop利用了距离矢量原理，属于无需测距的分布式定位算法［1］。

在Dv－hop算法中，要实现最后的定位计算，每个未知节点需要先获得两个基本信息：①不少于3个参考节点的坐标；②到这些参考节点的距离。Dv－hop算法会将未知节点到参考节点之间的距离用网络平均每跳距离和两者之间最短路径的跳数乘积表示，因此实际用于度量距离和参与计算的最重要的值就是跳数。在原始的Dv－hop算法中，除了孤岛节点外（连通度为0的节点），其余节点几乎都能够获得网络中每一个参考节点的信息。利用这大量的冗余信息，绝大部分节点都能实现有效的定位，这也是Dv－hop与其他算法相比的最大优势。

Dv－hop算法运行过程如文献［2］中所述：首先，参考节点通过距离矢量协议，向网络中广播其坐标和跳数信息；然后，参考节点估计出所有节点间单跳的平均距离，任何一个参考节点均可向整个网络广播此距离，将其作为整个网络的修正值；最后，未知节点就可以利用事先获得的参考节点的坐标和修正值，通过三边计算等方式完成自身的定位工作。

2 对Dv－hop的分析和问题的提出

Dv－hop是目前最典型的多跳定位机制，它充分利用了有限的参考节点信息，避免了测距误差的引入，简单可行，具有很高的实用性，但是相应的，该算法也有不少亟待改进的地方（如文献［3］中所述）。笔者从参考节点对精度的影响以及通信量两个方面，对Dv－hop算法的缺陷进行分析。该算法具体存在以下两个问题。

（1）在计算校正值的阶段，距离过远的参考节点和较近的参考节点所带来的误差影响是有所不同的，尤其是在具有一定各向异性特点的拓扑中尤为明显，而Dv－hop对全网的所有参考节点都配以相同的权重，这往往会使得到的校值偏小，从而影响最后的坐标计算。

（2）原算法中采用了全网洪泛的方式来确保每个节点都能收到所有参考节点的信标，这样虽然可以使未知节点获得足够多的参考节点信息，但是不受控洪泛的方式对传感器网络来说代价过于昂贵，对于参考节点数接近1 000的大规模网络，通信过程会带来巨大的能耗，使用Dv－hop算法不可行，这也将这种算法的应用范围限制在了中小型的网络。如何在保证未知节点能获得足够的参考节点信息的前提下降低通信量成了改进这种定位算法的最关键问题。

3 逐级分区和加权定位算法

下面将针对Dv－hop算法存在的两个问题，提出一种新的定位算法，引入逐级分区概念和加权计算，与文献［4］思路类似，首先通过对网络中的所有参考节点进行分级，按逐渐缩小本地范围的方式进行信标洪泛，以达到既能使节点获得足够参考节点信标，又能极大降低网络通信量的目的；其次在校正值的计算和传播阶段，通过对不同参考节点加权并合理选择参考节点进行坐标计算，来减小最终的定位误差。

3.1 参考节点信标的逐级分区洪泛

逐级分区主要是对参考节点进行分级，并通过各级分别洪泛来限制洪泛的范围，因此，改进后的算法可适用于大规模的传感器网络。算法开始运行之前，所有参考节点b和未知节点u随机分布，参考节点事先划分为几个级别，划分的值与参考节点的ID没有关联，采取随机划分或指定。

算法的实现采用一个通用的信息包结构：UNI＿MESSAGE，在所有节点通信中都发送这样的数据包，包含发送节点的ID号、级别、坐标、校正值（hopsize）和跳数；消息以结构体实现，以omnet的消息类进行封装，字段定义如图1所示。

图1 消息体UNI＿MESSAGE字段定义

分区算法分为4个步骤：

（1）首先，第一级的节点向邻居广播自己的信标。和在Dv－hop算法中一样，这个过程通过距离矢量的方式进行洪泛，所有节点记录下收到的信标中的坐标位置、ID号、Hops字段值，然后将Hops加1转发给自己的邻居节点。

（2）收到了第一级参考节点的信标后，未知节点记录下数据包中的ID号和坐标；同时，收到信标的每一个节点包括其他参考节点，都计算出一个自己所属的区域，这个区域的序号即是它所收到的信标中跳数值（Hops字段）最小的那个参考节点的ID号，如果有两个或两个以上信标中的跳数值相同，则取最先收到的一个。这样形成的结果就是，第一级的参考节点在它的附近一定范围内，划分出了一个以自己的ID号为序号的“虚拟”本地区域，这几个区域也是对全局的一个完整划分。

（3）从第二级的参考节点开始，均设置计时器，以收到上一级的信标起开始计时，当计时器溢出后，即认为上级节点的洪泛已经结束，然后开始自己的洪泛。第二级开始的参考节点在发送信标前，先根据前面收到的所有参考节点的信息（坐标值、跳数）计算校正值（与原算法不同，新校正值的计算方式在3.2节阐述），然后将计算出的校正值置入 UNI＿MESSAGE的hopsize字段，以“捎带”的方式与它的信标一起发送出去。与前一级参考节点不同，后一级参考节点信标的洪泛范围将被限制在它当时所处的区域内部，这也是算法能保证通信量大幅降低的关键。

对于来自同一区域的信标，判断是否需要更新自己当前所处区域的依据是：如果当前保存的Region＿hop值大于新参考节点到自己的跳数，就执行更新，然后将Region更新为新收到的参考节点ID。这样，新的参考节点就在它原来所属区域里面划分出了一个子区域。这个过程重复执行，直到各级的洪泛全部完成。最后的结果是，如果网络中分布了n个参考节点，网络将被划分为n个子区域，每个区域逐渐缩小，并且以一个相应的参考节点为中心。

（4）洪泛全部结束后，参考节点已经将信标和校正值广播到了网络中，未知节点在一段时间没有收到信标后，计时溢出，并开始坐标计算：首先将收到的校正值进行计算，得到最终的校正值，并选取参考节点，通过公式dn≈hopsizen×Hn将跳数距离转换为估计距离，然后采用三边计算或最大似然估计法求得坐标值。

3.2 基于权重的校正值计算和传播

在校正值的计算过程中应该考虑到参考节点的距离远近问题，对于过远的节点，在校正值的计算中要进行修正，配以较小的权重加以限制，使跳距过远的参考节点对校正值的影响迅速减小。

在3.1节分区算法步骤（3）中所述，从第二级的参考节点开始计算校正值，并且以“捎带”的方式将校正值随信标一起发送。假设第i个参考节点计时溢出后（Time＿up函数返回true）在其参考节点链表anchor＿list中有j个上级节点的信标，相应的跳数值分别为 Hij，相应坐标表示为（Xj，Yj），校正值hopsizei的计算公式为：

Hin为参考节点n到i的跳数。通过这种改进的校正值计算方式，可以提供更符合实际的校正值，从而提高最终的节点定位精度。

在新算法中，参考节点的信标和校正值是放在同一个数据包UNI＿MESSAGE里一起洪泛到网络中的，所以不存在第二次通信开销的问题，另外，当未知节点收到第一个校正值时，发出这个值的参考节点必然与它处于同一个子区域内（即一级节点划分的区域），后续节点也是如此，而且会逐渐靠近收到该值的未知节点，所以此算法可以确保校正值均来自未知节点附近。在本算法中，未知节点会接收到多个来自附近的校正值，最后通过取平均的方式进行处理，以充分利用这些冗余信息：hopsize＝，hopsize即未知节点用来估算到参考节点距离的校正值，n为节点最终收到的校正值数目。通过将校正值取平均，避免了因某个参考节点的值出现严重失真带来的影响。

3.3 参考节点的选取

新算法中，在坐标值计算方面，采取不同的策略：洪泛完成之后，节点首先在一级参考节点当中排除自己所属区域以外的其他几个节点，利用所有剩下的节点信标计算其坐标值；如果剩下的信标总数小于等于3，再在排除的参考节点中依照跳数值，按从小到大的顺序选择其他参考节点，直到信标数大于3为止。这样做可以保证定位计算只基于本地网络拓扑，目的同样是避免网络的非均匀性对坐标计算带来的影响，而且一级节点数目越多，用于坐标计算的参考节点离得越近，网络的不均匀性带来的影响也就越小。

4 定位算法的仿真验证与分析

分区加权算法主要针对定位精度和通信开销问题进行了改进。下面在OMNet＋＋和Matlab组成的环境下，对算法的相对定位误差、通信量，以及在各向异性拓扑下的性能进行对比仿真。

4.1 定位精度

为了检验算法的定位精度，采用随机分布的网络拓扑进行仿真，参考节点的分级均采用3.1中的划分方式，一级节点都为4个。下面各图中每一个数据点是在相同参数下5次仿真的平均值。

图2为Dv－hop算法和改进算法的定位误差曲线，参考节点的比例从5%到30%。从图中可以看到，在参考节点仅为5%时，改进算法的定位精度不如Dv－hop算法，平均相对误差达到了140%以上；参考节点多于10%时，改进算法的误差明显小于Dv－hop算法，且相对误差随参考节点增加而下降的趋势略快于Dv－hop算法；在参考节点取15%时，其误差平均值为47．9%。图2表明，根据参考节点的跳数远近决定其权重的大小来计算校正值的方式，明显改善了节点定位的精度。

图2 不同参考节点比例下的定位精度比较

4.2 通信量

对分区加权算法通信开销的仿真分两步，首先要验证通信量与参考节点的关系。图3中上面为Dv－hop的通信量曲线，虚线为其理论值；下面为分区加权算法通信量，虚线是其理论值。由仿真可见，Dv－hop中总节点数不变，参考节点从5%到30%变化时，通信量呈线性增加，增幅较大。

图3 不同参考节点比例下的通信量

图4为不同节点总数时的通信量曲线，参考节点比例固定为15%，节点每增加100，分布区域相应增加100，其他参数与前面相同，仿真次数均为1次。对于Dv－hop算法，其理论通信量计算为pn2＋n，p为参考节点比例。从仿真结果可以看到，其实际的通信量基本呈指数级增加；而分区加权算法中，通信量与理论值相近，呈对数特性，增加非常缓慢，在网络达到1 000个节点时，发送包数仍然小于10 000，而Dvhop算法的相应值却是它的14倍。

4.3 各向异性拓扑下的对比仿真

由于分区加权方式的采用，算法对网络拓扑的依赖性比Dv－hop算法要小。现对一个“C”形的网络进行仿真，其代表了各向异性网络拓扑。图5为对网络取不同的参考节点比例时，分别运行Dv－hop算法和分区加权算法得到的定位精度曲线图。最上面为Dv－hop算法的误差曲线，其相对误差都在110%以上，平均误差值为138．6%，并且没有随参考节点增加而降低。可见Dv－hop算法的确仅适用于各向同性网络拓扑［5］，在“C”形网络结构中，拓扑呈明显的各向异性，“空洞”效应在这里非常明显。中间的曲线为分区加权算法，一级节点数目为4时的结果，在所有参考节点比例下，定位精度都有明显的提高。最下边一条曲线为一级节点数目为6时的结果，即按照6，6，12，24…的方式划分，可以看到，在这种情况下，当参考节点比例增加到20%时，定位精度有非常明显的提高，其相对误差降低到了53．2%，与Dv－hop算法在各向同性网络中的性能相近。但图中曲线也同时表明，要在这种完全各向异性的拓扑中取得较高的定位精度，需要更高的参考节点比例。

图4 不同节点总数下的通信量（15%Anchor）

图5 “C”形网络的定位精度

5 仿真总结

以上的仿真实验表明，在节点随机分布的网络中，分区加权算法的定位精度优于Dv－hop算法，更关键的是，它极大地降低了定位过程中的通信开销，因此从这个方面讲，它能够应用于节点数目较多的大规模传感器网络，是对Dv－hop算法的有效扩展。另外，在各向异性网络中，分区加权算法的定位精度与Dv－hop算法相比有非常明显的提高，在仿真中采用的“C”形网络，当参考节点数目达到20%以上时，其定位相对误差降低到了53．2%。

［1］ 张品，孙岩．一种新的无线传感器网络DV－Hop算法［J］．电子器件，2010，33（1）：117－120．

［2］ Niculescu D，Nath B．DV based positioning in Ad Hoc networks［J］．Telecommunication Systems，2003，22（1－4）：267－280．

［3］ 石为人，贾传江，梁焕焕．一种改进的无线传感器网络DV－Hop定位算法［J］．传感技术学报，2011，24（1）：83－87．

［4］ 戴莹，王建平，张崇巍．无线传感器网络节点定位算法的研 究 与 改 进 ［J］．传 感 技 术 学 报，2010，23（4）：567－570．

［5］ 卫开夏，田金鹏，王克谦．无线传感器网络DV－Hop定位 改 进 算 法 ［J］．传 感 技 术 学 报，2010，23（12）：1820－1824．