一种新的无线传感器网络DV-Hop算法

张 品，孙 岩

(杭州电子科技大学通信工程学院， 杭州310037)

近几十年来，随着通信技术、嵌入式计算机技术、微处理技术和传感器技术的飞速发展与日益成熟，无线传感器网络(WSNs)在无线通信和数字电子技术的促进下迅速发展，由于具有感知能力、通信能力和计算能力，所以开始受到广泛的关注。在大多数应用场景下，没有传感器的位置信息而只感知数据是没有意义的，只有结合了位置信息传感器获取的数据才有实际的意义[2]。另外，了解传感器的节点位置信息还可以提高路由效率，例如设计基于节点位置信息的路由算法以提高路由效率[3-4]，因此，实现节点的自身定位对WSNs有着重要的意义。

到目前为止，已经提出了许多的传感器网络节点定位算法，这些算法大部分都假设网络中包含一小部分的锚节点，所谓的锚节点就是可以通过GPS定位设备[5]或者其他硬件设备来获取自身位置信息的节点。而其他不知道自己的位置信息的节点被称作是未知节点。锚节点可以协助未知节点来进行位置定位。当一个未知节点知道三个或者三个以上的锚节点的位置信息时，它就可以通过三边定位来确定自己的位置。

在WSNs中，根据在定位过程中是否测量节点间的距离，可以将定位算法分为两大类：range-based算法[6](基于测距的算法)和range-free算法[7](无需测距的算法)。Range-based定位算法需要测量节点间的绝对距离或角度信息来进行定位，其中测距技术包括：信号到达时间(time of arrival， TOA)、信号到达角度(angle of arrival， AOA)[6]、信号 到达时间差(time difference on arrival， TDOA)[8]、信 号 强 度(received signal strength indicator， RSSI)等[9]。此类算法对硬件要求较高，需额外的硬件支持。但其中RSSI(基于信号强度的测距)对硬件要求较低，是一种廉价而有效地测距解决方案。Range-free定位算法不需要测量节点间的距离和方位，对硬件要求简单，但定位误差较大，不过可以满足大部分不需要定位精度很高的场合。典型的Range-free算法包括：DV-hop算法、质心算法、MDP-MAP算法及APIT算法等。

1 DV-Hop定位算法的描述

DV-hop算法[10]是为了克服直接三边定位算法的缺点提出的，它有效的避免了对节点的直接测量，由美国路特葛斯大学的Niculescu等人提出的。该算法的核心思想是：将未知节点到锚节点的距离用传感器网络的每跳平均距离和两者之间的距离的乘积表示，然后再用三角计算理论获得未知节点的位置信息。该算法要解决的问题有2：第1，要计算出未知节点到锚节点的跳数；第2，要计算出每跳平均距离。未知节点到锚节点的距离由它们之间的跳数乘以每跳平均距离得到。

DV-hop算法的步骤有三个阶段组成：

第1阶段采用防洪广播的形式广播信息，锚节点在网络中广播一个消息，该消息包含了该信标的标识id，位置坐标以及跳数Hops，初始化Hops为0，接收到此数据的每个节点将Hops+1并记录到一张表格中，然后继续向新的邻居节点广播。当节点接收到一个相同的id数据包时便与表中相同id的数据包的Hops相比较，若新的跳数小于表中已存在的跳数，就用新的跳数更新表中的跳数信息，否则丢弃该数据包，也不再进行转发。这样以泛洪的形式在整个网络中广播每个锚节点的信息，这样锚节点获得了其他所有的锚节点的坐标及跳数，未知节点也知道了其与锚节点的跳数，这样就由每一个锚节点的每跳平均距离可以由此节点到其他的锚节点的总的距离之和除以总的跳数之和得到。

第2阶段求得每个未知节点到锚节点的距离，每个节点到锚节点的距离可以由每跳平均距离乘以此未知节点到锚节点的跳数得到。

第3阶段进行三角计算获得节点的位置坐标。

2 DV-Hop算法的不足之处

DV-hop算法可以获得未知节点无线射程覆盖范围以外的锚节点的距离，并不需要测量节点之间的实际距离，但用每跳平均距离计算出未知节点与锚节点的距离是有误差的，对于那些和锚节点相距只有一跳的未知节点来说，它也需要用每跳平均距离来计算，这样误差将非常的大。例如，如图1所示。

图1 某一种节点分布情况(应用传统DV-Hop算法)

在图中L1， L2， L3均是锚节点， A是需要定位的未知节点。三个锚节点知道它们相互之间的距离，分别如图所示为30， 30和40。 A与L1之间的距离是15，跳数是1。 A到L2和到L3的跳数都是3。假设每一条边的长度为10。

由DV-hop算法可知， L1， L2， L3的计算如下所示：

L1： (30+30)/(4+4)=7.5；

L2： (30+40)/(4+6)=7；

L3： (30+40)/(4+6)=7

在锚节点计算完每跳平均距离之后，锚节点就将这个值在网络中广播，未知节点就将它第一个接收到的值作为每跳平均距离，在此例中L1， L2， L3将分别广播它们计算出的值7.5， 7和7。由于节点A与L1的距离只有一跳，所以节点A将7.5作为每跳平均距离，然后节点A就计算它与其他三个锚节点的距离，与L1的距离为7.5，与L2、L3的距离都为7.5◦3=22.5。接下来用三角计算获得节点A的坐标。

3 算法的改进——新的DV-Hop算法

A与L1的实际距离为15，用DV-hop算法估算出来的距离却为 7.5， 这样定位误差就达到了200%。因此在最后用三角计算获得的节点A的实际位置坐标的误差将会很大。节点A与锚节点L1之间的距离在一跳之内， 可以很容易的获得，但用DV-hop却用曲线平均来计算它们之间的距离，因此增大了误差。所以在本文中介绍了一种新的基于RSSI的DV-hop节点定位算法，名字叫做RDV-hop算法，这种算法同时运用了DV-hop算法和RSSI技术，改善了未知节点定位的误差减小了用DV-hop算法在锚节点附近的未知节点定位的误差。例如，如图2所示。

图2 新的DV-Hop算法

在图2中，我们假设L1， L2和L3均为锚节点，节点M为需要定位的未知节点。三个锚节点的实际距离分别为15， 30， 30。假设每条边的长度为10。用DV-hop算法三个锚节点将分别计算每跳平均距离：

L1： (15+30)/(2+4)=7.5；

L2： (15+30)/(2+4)=7.5；

L3： (30+30)/(4+4)=7.5

同时所有的锚节点产生并在网络中广播RSSI数据包，任何一个接收到RSSI数据报的节点都可以计算出它与此锚节点的距离。在图2 中，节点M距L1、L2都只有一条的距离，所以节点M可以直接获得从L1、L2发出的RSSI数据包，从而计算出它与L1、L2的距离(假设为10)。节点M所得到的锚节点的信息少于三个，然后用DV-hop算法计算节点M与其他锚节点的距离，节点M计算出它与L3的距离是7.5×3=22.5。最后节点M就可以用三边定位来计算自己的坐标了。

4 仿真

200个节点随机的分布在10 000 m×10 000 m的区域内，如图3所示每个节点的无线覆盖范围设为1 500 m。锚节点以适当的比例分布在其中。

图3 200个节点随机分布

我们将未知节点的实际位置与估算出的位置坐标的误差作为衡量两种算法的标准，如图4 ～图7所示为在不同的锚节点比例下的DV-hop算法与改进后的RDV-hop算法之间定位误差的比较，图4中的下边的一条曲线表示新算法的定位误差曲线，而图4中上边的曲线则表示老的DV-hop算法的定位误差曲线。图4 ～图7分别表示了在锚节点的比例为5%， 10 %， 15%和20%的情况下两种算法定位误差的比较，图中上边的曲线均表示老的DV-hop算法的定位误差曲线，而下边的曲线则表示新算法的定位误差曲线。

图4 锚节点的比例为5 %

图5 锚节点的比例为10 %

图6 锚节点的比例为15 %

图7 锚节点的比例为20 %

如图4 ～图7所示，我们可以看出新的DV-hop算法在不同的锚节点比例的情况下的定位误差都要好于老的DV-hop算法。另外在图中可以看到，随着锚节点的增加可以用RSSI来计算距离的邻居节点越来越多，所以随着锚节点的增加算法的精确度有所提高。

5 结论

定位成本和定位的精确度是衡量定位算法好坏的两个重要标准。本文介绍了一种新的定位算法，这种定位算法将DV-hop算法与RSSI结合起来，用RSSI的优点来改善DV-hop算法，提高了DV-hop算法的精确度。用这种新的算法在计算那些与锚节点只有一跳距离的未知节点时用RSSI来替代DV-hop算法，此时定位误差明显减小。仿真实验已表明此种方法的正确性。但是这种算法有局限性，只有在那些与锚节点只有一跳距离的未知节点的定位误差可以减小，如何改善整个网络所有的未知节点的定位误差还需进一步的研究。

[ 1] Akyildiz F， SuW， Sandarasurbramaniam Y， et al.Wireless Sensor Networks：a Survey[ J] .Computer Networks Journal， 2002，38(4)：393-422.

[ 2] 王焱欣，王培康.一种无线传感器网络定位算法的分析和改进[ D] .中国科技大学， 2007.

[ 3] 王珊珊，殷建平，蔡志平，等.基于RSSI的无线传感器网络的节点自身定位算法[ D] .国防科技大学， 2008.

[ 4] 陈浩.无线传感器网络路由协议的研究[ D] .吉林大学硕士学位论文， 30-35.

[ 5] 孙利民，李建中，等.无线传感器网络[ M] .北京：清华大学出版社， 2005.

[ 6] Bahl P， Padmanabhan V N.RADAR：An In-building RF-based User Location and Tracking System[ C] //Proc.of IEEE INFOCOM， March， 2000.

[ 7]He T， Huang C， Blum B M， et al.Range-free Localization Schemes in Large Scale Sensor Networks[ C] //Proceedings of ACM MobiCom.Canada， 2003.

[ 8] Harter A， Hopper A， Steggles P， et al.The Anatomy of a Context-a Ware Application[ J] .Proc.Of MOBICON， 1999.

[ 9] Tian S， Zhang X， Liu P， etal.A RSSI-based DV-hop A lgorithms for Wireless Sensor Networks[ C] //W ireless Communications，Network and Mobile Computing， 2007.China：Hefei， 2007：2555-2558.

[ 10] Niculescu D， Nath B.Ad Hoc Positioning System(APS)Using AOA[ C] //Proceedings of IEEE IN FOCOM.Sarrfransisco， 2003.