无线传感器网络中基于反距离加权的DV-Hop改进算法

汪文明，操小伟，刘桂江，施赵媛

(安庆师范学院 安徽省智能感知与计算重点实验室，安徽 安庆 246133)



无线传感器网络中基于反距离加权的DV-Hop改进算法

汪文明，操小伟，刘桂江，施赵媛

(安庆师范学院 安徽省智能感知与计算重点实验室，安徽 安庆 246133)

摘要：通过分析传统DV-Hop定位算法在对无线传感器网络中节点分布随机性方面的不足，提出了一种改进算法。该算法采用最小均方误差准则代替方差或偏差，求得平均每跳距离。为了体现各信标节点对未知节点的影响程度不同，采用反距离加权法来处理平均每跳距离。实验结果表明，在没有增加原算法复杂度和成本的前提下，定位精度有了一定提高，该算法是一种简单实用的改进定位算法。

关键词：无线传感器网络；DV-Hop；最小均方误差；反距离

无线传感器网络(Wireless Sensor Networks，WSN)是由大量分布在特定检测区域中静止或移动的传感器以Ad hoc和多跳方式构成的无线网络，其目的就是对检测区域中相应对象进行感知、数据采集、处理和网络传输[1-4]，目前，主要应用于军事、环境检测及工业等领域。在无线传感网络中，传感器节点的位置信息非常重要，它能实现对监测目标的实时监视及信息获取[5]。在WSN定位机制中有需要测量各节点间距离或角度信息的基于测距(Range-Based)定位和无需测距(Range-Free)定位[6]。Range-Based定位算法通过相关装置测得节点间的距离、角度等信息，因此定位精度相对较高，但这也是以增加节点成本和功耗为代价的；Range-Free定位算法依靠网络连通性进行定位，其主要有质心算法、凸规划定位算法、DV-Hop算法和APIT算法等[7]。文章针对DV-Hop算法的局限性提出改进，并进行仿真实验。

1DV-Hop定位算法及三边测量法

DV-Hop[8]最初是由Niculescu等人提出的，它是一个典型的利用多跳信标节点信息策略，主要包括3个阶段。以图1所示的小型传感网络为例，详细描述这3个阶段，其中，A，B，C为信标节点，其余为未知节点。

第1阶段，各信标节点向周围节点广播包含其自身位置的信息及初始值为0的跳数值的数据包。接收节点会保留所接受到的数据包中与各信标节点的最小跳数值，并将跳数值加1后转发给邻居节点。利用这种方法，最终让所有节点都能获得与信标节点间的最小跳数值。对于图1网络中的节点R而言，它与信标节点A、B、C间的最小跳数值分别为4，2，3。

图1　网络拓扑结构示意图

第2阶段，在第1阶段中各节点均获得了与各信标节点的位置信息和跳数值。利用下式可估算出平均每跳的距离：

计算出各信标节点的平均每跳距离后，通过广播传到整个无线传感网中。但未知节点只会接收其最近的信标节点的平均每跳距离信息，保存后并会转发给其邻居节点。未知节点会根据接收的信息与之前记录的各节点的跳数值，计算得出它到各个信标节点的距离。在图1中，离未知节点R最近的信标节点是B，因此，节点R会最先接收到B发出的平均每跳距离信息，并保存。据此，可计算出到信标节点A，B，C的距离：

dA=CB×4，dB=CB×2，dC=CB×3。

第3阶段，为了确定未知节点的位置信息，采用3边测量[9]定位法计算。在图1中，假设未知节点R的坐标为(x,y)，测得与其通信的n个信标节点的坐标为(xi,yi)，距离为di(i=1,2,…,n)，则

上式可以转化为AX=b的形式。其中，

用标准的最小二乘法解出位置节点的坐标为

X=(ATA)-1ATb。

2改进的DV-Hop算法

2.1最小均方误差准则求得平均每跳距离

在传统的DV-Hop算法中，由公式

求得信标节点的平均每跳距离，其测量误差均值为零，N为信标节点的个数。

在一般情况下，误差都服从高斯分布，这种情况下使用均方误差比用方差或偏差会更合理，故基于最小均方误差准则计算平均每跳距离：

其中，i,j=1,2,…,N。

2.2反距离加权处理的平均每跳距离计算

在传统的DV-Hop算法中，整个WSN的平均每跳距离即为未知节点从其最近信标节点获取的信息。但这种方法有局限性，不能充分考虑到WSN中节点分布的随机性。如果仅仅利用单个信标节点的平均每跳距离会产生较大偏差，导致未知节点定位精度的降低；另外，未知节点周围不同距离的信标节点对其影响也不同。因此，为了提升定位精度，应充分利用网络中的信息，并赋予近距离信标节点较大的权重，故利用反距离加权处理平均每跳距离，表示为

3仿真实验

通过MATLAB R2012b平台对传统DV-Hop定位算法及改进算法进行仿真测试，并以平均定位误差作为评价标准对两种算法进行对比分析。

3.1仿真实验

在100 m×100 m的区域中由rand函数随机产生200个节点，节点半径R分为20 m，25 m，信标节点数量从5个增长到40个(每次增长5个)，每种状态均仿真50次，最终取其平均值。作为评价标准的平均定位误差定义为所有被成功定位的未知节点的误差之和与通信半径的比值，公式为

3.2结果分析

从图2和图3可以看出，在不同的通信半径下，改进的定位算法与传统DV-Hop算法相比，定位精度更高。在通信半径一定的情况下，定位误差与节点中信标节点所占比重成反比例关系，当信标节点比重达到一定值后，定位误差趋于稳定。这是由于节点总数不变，在信标节点数目较低时，未知节点数量远多于信标节点。在进行定位时，每个未知节点的距离只能通过少量的信标节点来计算获得，必然会产生计算误差。另外，信标节点和未知节点之间的距离较大，跳数较多也会产生较大的误差。

图2 信标节点数目在通信半径R=20m时误差变化图3 信标节点数目在通信半径R=25m时误差变化

当信标节点所占比例相等时，随着通信半径的增大，定位误差也有明显的降低。

4结束语

针对WSN中传感器节点分布的随机性问题，提出了基于反距离加权的DV-Hop改进算法。通过理论分析与实验仿真可以得出，改进的算法与传统DV-Hop算法相比，在没有增大原算法复杂度和成本的前提下，定位性能有较大改善。

参考文献:

[1] 孙利民, 李建中, 陈渝, 等. 无线传感器网络[M]. 北京: 清华大学出版社, 2005.

[2] 张静, 曹敦, 傅明, 等.DV-Hop算法定位误差和覆盖率的改进[J]. 计算机应用, 2011, 31(7): 1944-1947.

[3] 刘锋, 张翰, 杨骥. 一种基于加权处理的无线传感器网络平均跳距离估计算法[J]. 电子与信息学报, 2008, 30(5): 1221-1225.

[4] 王振宇, 江克勤, 方木云, 等.REET无线传感器网络路由协议[J]. 安庆师范学院学报(自然科学版), 2008, 14(3): 45-47.

[5] 尚志军, 曾鹏, 于海斌. 无线传感网络节点定位问题[J].计算机科学, 2004, 31(10): 35-38.

[6]YangMian,QingQianqing.Researchoncurrentlocalizationtechnologyofsensornetworks[J].MicrocomputerDevelopment, 2005, 15(3): 26-28.

[7] 李云飞, 江明, 娄柯, 等. 无线传感网络中DV-Hop定位算法的改进[J]. 计算机工程与应用, 2014, 50(3): 79-81.

[8] 嵇玮玮, 刘中.DV-Hop定位算法在随机传感器网络中的应用研究[J]. 电子与信息学报, 2008, 30(4): 970-973.

[9]D.Niculescu.PositioninginAdHocsensornetworks[J].IEEENetwork, 2004, 18(4): 24-29.

Study on Improved DV-Hop Algorithm Based on Inverse Distance Weighting Method in Wireless Sensor Networks

WANG Wen-ming, CAO Xiao-wei, LIU Gui-jiang, SHI Zhao-yuan

(The University Key Laboratory of Intelligent Perception and Computing of Anhui Province,Anqing Teachers College, Anqing, Anhui 246133, China)

Abstract:An improved algorithm was proposed by analyzing the deficiencies of traditional DV-Hop algorithm in terms of random distribution， which owns improvements over two aspects. Firstly, instead of variance or deviation, the average one-hop distance is estimated by minimum mean-squared error criterion (MMSE). Secondly, in order to reflect the different effects of each beacon node on unknown nodes, inverse distance weighting method is adopted to deal with the average one-hop distance. Improved algorithm is simulated on MATLAB platform, and the results show that the positioning accuracy is improved on the condition of no increasing complexity and cost. The improved algorithm is a simple and practical algorithm.

Key words:wireless sensor networks, DV-Hop, minimum mean-squared error criterion(MMSE), inverse distance

文章编号：1007-4260(2016)01-0034-03

中图分类号：TP393

文献标识码：A

DOI：10.13757/j.cnki.cn34-1150/n.2016.01.010

作者简介：汪文明，男，安徽怀宁人，硕士，安庆师范学院计算机与信息学院教师，研究方向为无线传感器网络。E-mail: 772067486@qq.com

基金项目：安庆师范学院青年基金(KJ201406,KJ201303)和“智能感知与计算”安徽省高校科研创新平台项目。

*收稿日期：2015-07-29

网络出版时间：2016-03-15 17:05网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.010.html