无线传感器网络中Dv-Hop定位算法的改进 金纯1,2, 叶诚1 , 韩志斌2，韩刚3，周晓军2 （1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆金瓯科技发展有限责任公司，重庆 400041；3.重庆广通实业发展有限责任公司，重庆400039） 摘要:针对Dv-Hop算法中锚节点与待定位节点的估算距离引入的误差较大，从而影响使用最小二乘法定位的问题，提出了一种改进的算法。该算法主要原理是借助RSSI测距技术，并对锚节点与待定位节点间估算距离排序选出误差较小的一组数据，选用此组数据构建最小二乘法方程组中的被减方程，以提高定位精度。仿真结果表明，与传统的Dv-Hop算法相比，改进后的算法在不增加额外硬件和计算量的前提下，较大的提高了定位精度。 关键词：无线传感器网络；定位算法；接收信号强度指示器测距技术；Dv-Hop算法；matlab仿真 中图法分类号：TP393
	该论文发表于《通信技术》2007年第27卷第4期 刊号为：ISSN 1006-6403

Dv-Hop localization algorithm improvements in wireless sensor networks
Jin Chun1,2 , Ye Cheng1, Han Zhi-bin2 , Han Gang3, Zhou Xiao-jun2
(1.College of Communication and information Engineering.Chongqing University of Posts and Telecommunication, Chongqing 400065, China; 2.Chongqing JinOu Science&Technology Development Co, Ltd, Chongqing 400041, China ; Chongqing?GuangTong?Industrial?Development?Co,Ltd, Chongqing 400039, China )
Abstract：In conventional Dv-Hop algorithm, large error took place in estimated distance between anchor nodes and node to be positioned,which affected the use of least square method. In this paper, an improved algorithm was proposed according to the algorithm RSSI,the principle of which is selecting a group of data with the least error as the reduced equation in the least square equation set in order to improve the accuracy of positioning. The simulation results show that comparing with the traditional Dv-hop algorithm, the improved algorithm greatly improved the positioning accuracy without no additional hardware and computation.

Keywords：Wireless sensor networks; Positioning Algorithm; Received signal strength indicator ranging technology；DV-hop algorithm；matlab simulation

0 引言

无线传感器网络是由大量无线传感器节点以Ad-Hoc的组网方式构成的无线网络，其目的是感知、采集和处理其覆盖区域中感知对象的信息[1][2]。无线传感器网络具有较高的应用前景，现已广泛应用于军事、环境、医疗等领域[3][4]。定位技术是无线传感器网络中多种应用的基础，随着无线传感器网络的蓬勃发展，与其息息相关的定位技术受到了人们较大的关注。
在无线传感器网络中，最简单的定位方法是采用GPS定位系统，在传感器节点内安装GPS接收机，通过GPS接收机与卫星的通信，实现GPS接收机的定位功能。但是在实际应用中，无线传感器网络要求节点价格低廉，功耗和体积小，在这种限制下，通常只会将GPS接收机安装于少数传感器节点，这些传感器节点称为锚节点。无线传感器网络中的定位算法就是未知节点借助这些锚节点的坐标信息来实现节点自身的定位[2]。无线传感器网络中的定位算法分类标准有很多，使用较多的是依据是否需要测量节点间距离或角度等信息来分类，依照这种划分，可以把定位算法分为基于距离的定位[5]和与距离无关的定位[6]。基于距离的定位机制一般定位精度相对较高，对节点的硬件通常也提出了较高要求，基于距离定位机制常用测距方法有RSSI（received signal strength indicator）、TOA(time of arrival )、 TDOA(time difference on arrival)、 AOA(angle of arrival)。与距离无关的定位机制无需实际测量节点间的绝对距离或方位，对节点硬件的要求低，使得节点成本更适合于大规模网络。与距离无关的定位算法主要有质心算法、Dv-Hop算法、APIT算法、MDS-MAP算法[7]等，现有技术中通常使用的是Dv-Hop(distance vector-hop )算法。本文主要是针对Dv-Hop算法的不足提出了改进，并借助仿真工具加以验证得出了较优的性能。

1. Dv-Hop算法

Niculescu等人提出的Dv-Hop算法[8]主要是利用典型的距离路由协议，得到所有节点之间的最小跳数，然后根据信标节点间的最小跳数估算平均每跳距离，再利用未知节点和信标节点的最小跳数与估算的平均每跳距离乘积代替未知节点与信标节点间的距离，最后利用三边测量法或最小二乘法求未知节点的坐标，完成定位。

1.1 Dv-Hop算法的定位过程

Dv-Hop定位算法主要可以分为以下三个阶段：

a) 计算未知节点与信标节点的最小跳数。

借助典型的距离矢量交换协议，信标节点向邻居节点广播自身位置的信息分组，其中包括跳数字段，初始化为0，接收节点记录到每个信标节点的最小跳数，忽略来自同一信标节点的较大跳数的信息分组，将跳数加1再转发给它的邻居节点。通过这种方式使网络中所有节点获得它到其他节点的最小跳数。

b) 计算未知节点到信标节点间的距离。

信标节点根据第一阶段获得到其他信标节点间的最小跳数跟位置信息，利用公式（1），可以获得平均每跳距离。

                              （1）

其中 ， 是信标节点 和 的坐标， 是信标节点 的平均每跳距离。然后信标节点将这个平均每跳距离利用带有生存限制的分组广播至网络中，使得离它较近的未知节点获得相应的 ，利用公式（2）就可以计算出未知节点到距离较近的几个信标节点距离。

                                   （2）      

其中 代表信标节点， 代表未知节点， 代表 和 的最小跳数。

c) 计算出未知节点的坐标，完成定位。

通过第2阶段得到的未知节点到信标节点的距离，再利用极大似然估计法求出未知节点坐标。

假设未知节点的坐标为 ,信标节点 的坐标为 ，未知节点与信标节点间的距离 由公式（3）计算出：

                                                （3）

对于公式（3）从第一个方程开始分别减去最后一个方程，可得：

                  （4）

公式（4）的线性表达式为:

                                                                （5）

X可以由公式（6）求出。

                                                            （6）

其中：

1.2 Dv-Hop算法的误差分析

无线传感器网络中，节点随机分布，各节点之间的距离长短不一，节点密度分布也稀疏不同。而Dv-Hop算法中利用信标节点间计算得出的平均每跳距离，来代替网络中未知节点到信标节点间的每跳距离，用其乘以跳数的得出的值来作为未知节点到信标节点间的距离，显然计算出的距离将会与真实距离存在较大的误差，这种误差是算法机制所带来的，需要采取某些措施来减小定位误差，提高定位精度。而未知节点与锚节点之间误差的大小通常与估算的平均每跳值、未知节点到信标节点跳数多少等有关。一方面，跳数越多，未知节点与锚节点之间路径偏离两点直线连线的可能性越大，计算出的未知节点与锚节点距离与真实距离误差越大。另一方面，用原本不精确的平均跳距乘以跳数得到的估算距离将随跳数的增加，误差也会累计增加。总的来说，在绝大多数情况下，未知节点与锚节点之间估算误差的大小会随着跳数的增加而增大。

2. Dv-Hop算法的改进

2.1 RRSI测距技术

 RSSI是接收到信号强度大小的指示器，是一种利用信号的衰减来推测距离的测距技术[9]。

                                               （7）

公式（7）是目前使用较多的一种理论模型， 是距离发射处 米接受到的信号功率， 是距离发射处 米接收到的信号功率， 是路径衰减因子， 是均值为0、标准差为 的高斯分布，实际计算中， 通常取1米， 也取1米处的信号强度。而在目前常用的TI公司芯片CC2430中，有以下关系成立：

                                                  公式（8）

借助于以上公式，可以得出如下公式：

                                                       公式（9）

其中 。系数 跟 可以通过采集数据，进行拟合来得到，这样就可以根据RSSI算出对应的距离 。文献[9]对基于RSSI的测距进行了分析，其结论表明，在15米以内，RSSI测距有较高的精度。在15米以内用RSSI测距获得的数据比原算法估算的数据更精确。

2.2 改进后的Dv-Hop算法

目前，已有很多学者和研究人员提出对Dv-Hop算法的改进策略[10]-[12]。文献[10]中将信标节点分成圆形或者半圆形后再进行定位。文献[11]中采用未知节点附近多个锚节点的加权平均跳距代替原算法中的平均跳距减少了跳距带来的定位误差。文献[12]针对锚节点与未知节点之间的估计距离做出了修正，该修正值由多跳的校正者和锚节点平均每跳距离误差所组成，由此提高定位精度。大部分改进都是针对Dv-Hop算法中第一二阶段所进行的，通过修正未知节点与锚节点之间的距离，提高定位精度。

在算法第三阶段中，用最小二乘法公式（3）计算时，每个方程都将减去最后一个方程，可见最后一个方程中估算的距离 与真实距离之间误差的大小将对计算出的未知节点坐标有很大的影响，如果最后的一组数据误差很大，前面的 组数据再怎么精确，也会让算出的结果跟真实位置之间存在很大的误差。因此，本文的改进思路是基于选取一组误差最小的数据构建第 个方程。

为了，使选取出来误差尽可能小的一组数据，本文做出如下改进：

a) RSSI在15米以内，有较高的精确度，当未知节点与锚节点在15米以内时候采用RSSI算得的距离比原算法估算的距离误差更小。因此，锚节点发起广播信息时，在一跳范围内的未知节点将根据RSSI计算它们之间的距离，如果计算出的值在15米以内，将直接用这个值作为它们之间的估算距离。

b) 对未知节点于锚节点之间的估算距离 进行排序，选择它们之间距离，最小的一组数据，来构建公式（3）中第 个方程。

3. 仿真与分析

为了验证改进后算法的性能，使用了matlab对Dv-Hop算法和改进后的Dv-Hop算法性能进行了仿真对比，并对结果进行了分析。

假设某未知节点实际坐标为 ，估计坐标为 ，通信半径为 。

绝对定位误差定义为:

                                                  公式（10）

相对定位误差定义为 ：

                                                           公式（11）

3.1 同一场景下，两算法性能对比

为了最直观的比较两种算法的性能，在同一网络场景下用两种算法定位，分别给出了每个点在每种算法下的绝对误差。图一所示，是在100*100的网络环境下进行仿真实验，节点总数200个，信标节点20，通信半径 为15。

 从图1可看出改进后的Dv-Hop算法绝大部分节点绝对定位误差比原算法小，而且改进后算法的方差也比原算法小。相对于原算法，改进后的Dv-Hop算法能有效的提高定位性能。

图 1

3.2 不同通信半径下，算法性能对比

为了更全面的分析、评价改进后算法的性能。将节点通信半径依次改变，比较算法在不同通信半径下的性能。

图2所示，也是在100*100的网络环境下进行仿真实验，节点总数200个，信标节点20，但通信半径 由15依次累加，每个数据都是程序独立运行500次后取的平均值。为了更好分析引入RSSI的作用，特意也将改进算法中引入RSSI的相关部分剔除作为一种新的算法对比，称之为不完整改进算法以示区别。

图2可以看出，不完整改进算法在通信半径较小时候相对原算法能较大幅度的提高定位精度，但在 超过65后，不完整改进算法已不能提高算法性能。这是因为 较小时候，算法的平均每跳距离也较小，待定位节点一跳范围内锚节点很少，甚至没有，此时选择离待定节点最近的锚节点，能保证未知节点与锚节点之间估算误差较小。然而随着 的增大，网络平均每跳距离变大，待定节点一跳范围内锚节点越来越多，因为一跳内的锚节点到待定节点的估计距离都由网络平均每跳距离决定，此时只有距离跟网络平均每跳距离数值越接近误差才会越小，显而易见再选择f离待定位节点较近的点已不能保证它们误差最小，算法的性能亦不能得到提高。

改进后的Dv-Hop算法，在引入较高精确度的RSSI测距，一跳范围15米以内的点，其距离将不再依靠网络平均每跳距离估算，直接RSSI测量，在用二乘法定位中采用此组数据构建第 个方程，对半径的改变并没有那么敏感。在 较小时候，改进算法虽然跟不完整改进算法差距不大，但随着 的增加，改进算法性能提高较为明显。

图 2

3.3 不同锚节点个数，算法性能对比

依旧在100*100的网络环境下进行仿真实验，节点总数200个，通信半径为20，改变网络中锚节点的个数，仿真算法在不同数目锚节点下的性能。

图3所示仿真结果，随着锚节点数目的提高，原算法和改进算法的性能都得到很大的提高。当锚节点达到一定比例，再提高锚节点数目，算法性能提高较缓慢，但改进后的Dv-Hop算法性能始终优于原算法。

图 3

4. 结论

本文对Dv-Hop算法做了相关的研究，针对算法中锚节点与待定位节点的估算距离引入较大误差影响使用最小二乘法定位问题，提出了一种改进算法。RSSI测距技术在15米以内有较高的精确度，本文改进思想借助RSSI测距技术减小15米以内锚节点与待定位节点之间的估算误差，对待定位节点到附近所有锚节点距离进行排序，得出锚节点与待测节点误差较小的一组数据，在最小二乘法中方程组中用此组数据构建被减方程。仿真实验证明，改进后的算法在没有增加计算量和额外硬件的情况下，显著提高了定位性能。

参考文献
[1]KIM S, KO J G, YOON J, et al. Multiple-objective metric for placing multiple base station in wireless sensor network[C]//Proceeding of the 2rd International Symposium on Wireless Pervasive Computing.
[2]Jennifer Yick, Biswannath Mukherjee, Dipak Ghosal. Wireless Sensor Network Survey[J].Computer Networks, 2008, 52: 2292-2230.
[3] MIZUGAKI K, FUJIWARA R, NAKAGAWA T, et al. Accurate wireless location/communication system with 22-cm error using UWB-IR[C]//Radio and Wireless Symposium. Washington, DC: IEEE, 2007:455-458.
[4] Guoqiang MaoBar?s, Fidan Localization. Algorithms and Strategies for Wireless Sensor Networks [M]. Information Science Reference , Release Date: May, 2009.
[5] Xiao J, Ren L R, Tan J D. Research of TDOA Based Self-Localization Approach in Wireless Sensor Network[J]. Intelli-Gent Robots and Systems, 2006,(10):2035-2040.
[6] Li M, Liu Y H. Rendered Path: Range-Free Localization in Aniso-tropic Sensor Networks with Holes[J]. IEEE/ACM Transactions on Networking, 2010, 18(1): 320-332.
[7] SHANG TIAN, RUMI W, ZHANG Y, et al. Localization from mere connectivity[C]//Proceedings of the 4th ACM Intel Symp on Mobile Ad Hoc Networking & Computing. Annapolis: ACM PRESS, 2003:201-212.
[8] Nicolescu D, Nath B. DV based positioning in ad-hoc networks[J]. Journal of Telecommunication Systems, 2003.1-4, Vol 22(NO 11-3). pp.267-280.2006.10
[9]Fang Zheng,Zhao Zhan,et al. Ranging Analysis Based On RSSI[J] Chinese Journal of Sensors and Actuators, 2007.11 22（11）2526-2530.[方震，赵湛，等.基于RSSI测距分析[J].传感技术学报，2007.11 22（11）2526-2530.]
[10]YASSINE F, SAFA H. A hybrid Dv-Hop for localization in large scale wireless sensor network[C]//Proceeding of the 6th International Conference on Mobile Technology, Application and Systems. New York: ACM, 2009: 1-6.
[11]Wan Xin-sheng,Zhao Yan-jing,Li Hai-tao.Research On Improvement Of Algorithm Dv-Hop[J] computer science, 2011.2 38（2）：76-78.[王新生，赵衍静，李海涛.基于Dv-Hop算法的改进研究[J].计算机科学，2011.2 38（2）：76-78.]
[12] Zhang Jia, Wu Yan-hai, Shi Feng, et al. Positioning Algorithm Based On Dv-Hop Wireless Sensor Net Work [J]computer application, 2010.2 30（2）323-326.[张佳，吴延海，石峰，等.基于Dv-Hop无线传感器网络定位算法[J].计算机应用，2010.2 30（2）323-326]

作者简介：
金 纯（1966—）重庆市，博士，教授，主要研究方向为无线传感器网络等；
叶 诚（1987—）湖南省益阳市，硕士，主要研究方向为无线传感器网络；
韩智斌 (1978-) 重庆市，学士, 主要研究方向为无线传感器网络；
韩 刚（1976—）重庆市，学士,主要研究方向为无线传感器网络；
周晓军（1975—）重庆市，学士,主要研究方向为无线传感器网络；

下一页：基于Bluetooth和智能手机的无绳电话应用方案