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

金 纯，叶 诚，韩志斌，韩 刚，周晓军

(1.重庆邮电大学通信与信息工程学院，重庆400065;2.重庆金瓯科技发展有限责任公司，重庆400041;3.重庆广通实业发展有限责任公司，重庆400039;4.重庆市旭鼎科技有限公司，重庆400065)

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算法等，现有技术中通常使用的是Dv-Hop(distance vector-hop)算法。近几年，国内外学者主要围绕上述经典算法，提出了许多的改进算法，进一步提高定位性能，使传感器网络能更好的应用于实际。本文主要是针对Dv-Hop算法的不足提出改进，并借助仿真工具加以验证，得出了较优的性能。

1 Dv-Hop算法

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

1.1 Dv-Hop算法的定位过程

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

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

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

(2)计算未知节点到锚节点间的距离。

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

式 中:(xi，yi)，(xj，yj)——锚 节 点 i 和 j 的 坐 标，HopSizei——锚节点i的平均每跳距离。然后锚节点将这个平均每跳距离利用带有生存限制的分组广播至网络中，使得离它较近的未知节点获得相应的HopSizei，利用式 (2)就可以计算出未知节点到距离较近的几个锚节点距离

式中:i——锚节点，j——未知节点，hopij—— i和 j的最小跳数。

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

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

假设未知节点的坐标为(x，y)，锚节点i的坐标为(xi，yi)(i=1，2，…，n)，未知节点与锚节点间的距离 di(i=1，2，…，n)由式 (3)计算出

对于式 (3)从第一个方程开始分别减去最后一个方程，可得

式 (4)的线性表达式为

X可以由式 (6)求出。

其中

1.2 Dv-Hop算法的误差分析

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

2 Dv-Hop算法的改进

2.1 RRSI测距技术

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

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

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

其中A=Pr(1)+RSSI_OFFEST。系数A跟n可以通过采集数据，进行拟合来得到，这样就可以根据RSSI算出对应的距离d。文献［7］对基于RSSI的测距进行了分析，其结论表明，在15米以内，RSSI测距有较高的精度。在15米以内用RSSI测距获得的数据比原算法估算的数据更精确。

2.2 改进后的Dv-Hop算法

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

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

基于以上研究，本文做出如下改进:

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

(2)对未知节点于锚节点之间的估算距离n(i=1，2，…，n)进行排序，选择它们之间距离，最小的一组数据，来构建式 (3)中第n个方程。

3 仿真与分析

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

假设某未知节点实际坐标为 (xr，yr)，估计坐标为(xe，ye)，通信半径为R。

绝对定位误差定义为

相对定位误差定义为

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

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

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

图1 两种算法下误差对比

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

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

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

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

图2 不同通信半径下算法性能比较

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

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

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

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

图3 不同锚节点数目下算法性能比较

4 结束语

国内外学者针对Dv-Hop算法的不足提出了许多改进算法，基本上都是围绕如何减小节点间的估算距离误差做出改进，但是却很少有人关注到这种误差对最后使用最小二乘法定位的影响。本文正是为了减小这种影响而提出的改进算法，通过借助RSSI测距，排序等手段对算法做出改进，减小节点估算距离误差对最后定位的影响。仿真实验证明，改进后的算法在没有增加计算量和额外硬件的情况下，相对于原算法，显著提高了定位性能。

［1］KIM S，KO JG，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.Korea，2007:627-631.

［2］Jennifer Yick，Biswannath Mukherjee，Dipak Ghosal.Wireless sensor network survey ［J］.Computer Networks，2008，52(12):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 MaoBaris，Fidan Localization.Algorithms and strategies for wireless sensor networks［M］.Information Science Reference，Release Date，2009.

［5］XIAO Jun，REN Lirong，TAN Jingdong.Research of TDOA based self-localization approach in wireless sensor network［C］//International Conference on Intelligent Robots and Systems.China，2006:2035-2040.

［6］LI M，LIU Y H.Rendered path:Range-free localization in anisotropic sensor networks with holes［J］.IEEE/ACM Transactions on Networking，2010，18(1):320-332.

［7］FANG Zheng，ZHAO Zhan.Ranging analysis based on RSSI［J］.Chinese Journal of Sensors and Actuators，2007，22(11):2526-2530(in Chinese).［方震，赵湛.基于RSSI测距分析 ［J］.传感技术学报，2007，22(11):2526-2530.］

［8］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.

［9］WAN Xinsheng，ZHAO Yanjing，LI Haitao.Research on improvement of algorithm Dv-Hop ［J］.Computer Science，2011，38(2):76-78(in Chinese).［王新生，赵衍静，李海涛.基于Dv-Hop算法的改进研究 ［J］.计算机科学，2011，38(2):76-78.］

［10］ZHANG Jia，WU Yanhai，SHI Feng，et al.Positioning algorithm based on Dv-Hop wireless sensor net work［J］.Computer Application，2010，30(2):323-326(in Chinese).［张佳，吴延海，石峰，等.基于Dv-Hop无线传感器网络定位算法［J］.计算机应用，2010，30(2):323-326.］