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

陈晶杰，罗 明

(西安电子科技大学，西安 710071)



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

陈晶杰，罗 明

(西安电子科技大学，西安 710071)

针对无线传感器网络中经典定位算法DV-Hop存在定位精度低的缺陷，提出了一种改进算法。在传统DV-Hop算法的基础上，首先采用最小均方误差准则校正信标节点的平均每跳距离，然后对各未知节点到参考信标节点的平均每跳距离进行加权处理，最后通过参数分析，对未知节点进行位置修正。仿真实验结果表明，改进算法相比于传统的DV-Hop定位算法以及已有的改进算法具有很高的定位精度，并且无需增加额外的硬件设施。因此在工程上具有很好的实用性。

无线传感器网络；节点定位；DV-Hop算法；最小均方误差

0 引 言

无线传感器网络(WSN)由大量传感器组成。这些微型传感器彼此合作，对环境中观测对象的参数进行实时的监测、感知和采集，并且通过无线通道，以自组网的形式传送到控制中心[1]。传感器网络在军事国防、环境监测、城市管理、防恐反恐、生物医疗等众多应用领域内发挥着巨大的作用[2-4]。节点定位是实现上述应用的重要前提，没有位置信息的传感数据对用户是没有任何意义的[5]。因此，消息节点位置的获取在传感器网络的实际应用中发挥着至关重要的作用。

无线传感器节点定位算法大体可以分为两大类[6-7]：基于测距的定位算法和无需测距的定位算法。基于测距的定位算法主要是测量点到点之间的绝对距离或者方位信息，这种定位算法虽然有很高的定位精度，但是其计算量比较大，增加了节点系统的通信开销，违背了无线传感器网络低功耗的原则，在现实中很难实现。无需测距的定位算法不需要直接测量节点之间的距离和方位信息，这种算法主要是利用节点之间的网络连通性来确定节点的具体位置，并且无需测距的定位算法在原有的硬件设施上就能够实现节点定位，不需添加额外的硬件设施，对无线传感器的小型化、时效性具有重要意义。DV-Hop是美国路特葛斯大学的Dragos Niculescu等人利用距离矢量路由协议和GPS定位原理提出的一系列无需测距定位算法中的一种节点定位算法[8]。

通过对DV-Hop定位算法的研究，节点定位在网络环境下存在着比较大的定位误差。在对DV-Hop定位算法的改进方面，文献[9]、[10]提出了对各信标节点的平均每跳距离相加取均值的改进算法，即算术平均处理。文献[11]提出基于未知节点对各信标节点平均每跳距离进行加权处理的改进算法，即加权处理。本文则在重点研究分析了Dv-Hop节点定位算法对平均每跳距离以及定位方程解算过程中存在不足的基础上，提出了一种改进方法。通过仿真验证了该方法具有很好的定位性能。

1 DV-Hop节点定位算法

DV-Hop定位算法是一种基于距离矢量路由协议而无需进行测距的定位算法，其主要思想是将未知节点到各个信标节点之间的距离用网络平均每跳距离乘以跳数来表示的，最后再使用三边定位法或最大似然估计法来确定未知节点的的坐标信息[7]。

DV-Hop节点定位算法主要由3个阶段组成：

第1阶段：首先通过距离矢量路由交换协议，使网络环境中的所有节点接收到其距离各个信标节点的最小跳数和位置坐标信息，然后信标节点i根据其收到的距离其他信标节点的最小跳数和坐标信息后，利用公式(1)计算自己的平均每跳距离：

(1)

式中：n为总的信标节点个数；(xi,yi)和(xj,yj)分别为信标节点i和j的坐标信息；hij为信标节点i和j之间的最小跳数。

第2阶段：各个信标节点首先将自己在第一阶段中计算出平均每跳距离，利用可控洪泛法广播至网络中，然后网络中所有的节点只接收距离自己最近信标节点的平均每跳距离。最后网络中的未知节点根据自己信息表中记录的距离各个信标节点的跳数和平均每跳距离，利用公式(2)计算其与信标节点之间的估计值：

dik=Savi×hik

(2)

式中：dik为未知节点k和信标节点i之间的估计值；hik为未知节点k和信标节点i之间的最小跳数。

第3阶段：未知节点利用极大似然估计法估算自己的位置。假设未知节点k的坐标为(x,y)，第i个信标节点的坐标为(xi,yi)，信标节点i和未知节点k之间的估算距离由第2阶段求得为di，则由以下公式求得未知节点的坐标：

(3)

公式(3)中用前n-1项减去最后一项，方程可以写成AX=B的形式，其中：

(4)

(5)

利用标准最小二乘法可得未知节点估计坐标：

X=(A′A)-1A′B

(6)

2 DV-Hop节点定位算法的改进

DV-Hop节点定位算法的改进主要由以下3个部分组成：

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

本文采用最小均方误差准则对计算出的平均每跳距离进行改进。由DV-Hop定位算法原理可以知道，信标节点在接收到其他信标节点的位置信息后，平均每跳距离Savi满足公式(7)：

(7)

式中：dij为信标节点i和j之间的真实距离；(xi,yi)和(xj,yj)分别为信标节点i和j的坐标；hij为信标节点i和j之间的最小跳数；εij为进行估值所带来的误差，平均每跳距离的合理选择应该使得εij的值最小。

(8)

(9)

2.2 对未知节点到各个信标节点的平均每跳距离进行统一的加权处理

通过分析，传统Dv-Hop定位算法在计算节点的平均每跳距离中仅仅考虑距离自己最近的信标节点广播的信息，即每个节点只接收距离自己最近信标节点广播的平均每跳距离和跳数，这样的接收机具有一定的局限性，为了统筹整个网络对节点的影响，本文采用对未知节点到各个信标节点的距离进行统一加权处理的思想。即未知节点在接收到各个信标节点的信息后，利用跳数通过公式(10)计算每个信标节点的权值：

(10)

式中：λi为未知节点到第i个信标节点所对应的权值;hi为未知节点到第i个信标节点的跳数。

结合公式(9)、(10)可求得新的平均每跳距离Savk：

(11)

则未知节点k到每个信标节点的距离为：

dki=Savk×hki

(12)

式中：Savk为未知节点k所对应的平均每跳距离；hki为未知节点k到第i个信标节点的跳数；dki为未知节点k到第i个信标节点的估计距离。

未知节点k从多个信标节点中通过不同的权值得到平均每跳距离，使得定位节点的平均每跳距离更加符合网络的实际平均每跳距离。

2.3 对未知节点的估值进行修正，进一步提高定位精度

未知节点利用极大似然估计法估算自己的位置:

(13)

在公式(13)中，用离未知节点p最近的那项信标节点k去除其余n-1项，得到：

∀i=1,2,…,n且i≠k

(14)

简化公式(14)得到n-1项公式：

(15)

公式(15)的矩阵形式为：

GZ=D

(16)

利用标准最小二乘法对方程GZ=D进行求解得：

Z=(G′G)-1G′D

(17)

通过式(17)求得的未知节点具有很好的定位精度，可以使用公式(17)中求出的s(s=x2+y2)对得到的未知节点进行更新，以提高定位精度。

根据公式(17)未知节点可以估算出自己的坐标(xu,yu)，并且求出s的值。但是由于未知节点与各信标节点之间距离dpi计算误差的影响，未知节点并不满足s=x2+y2。未知节点的估算坐标如图1所示。

图1 未知节点的估算坐标

A为由公式(17)计算出的未知节点的坐标，B和C分别为当s>x2+y2和s

(18)

(19)

未知节点的更新通过(xu,yu)和(xs,ys)的均值来表示。因此，未知节点的更新坐标可以表示为：

(20)

3 算法仿真

为了检测比较本文改进算法的性能，本次仿真在MATLAB平台上对传统DV-Hop定位算法，文献[9]、[10]提出的算术平均处理算法，文献[11]提出的加权处理算法以及本文提出的改进算法在基于节点定位误差方面进行仿真评估。网络仿真的模型参数如下假设：在100 m×100 m的区域里随机生成传感器节点的坐标，并且假设各传感器节点的感知、计算以及通信能力一致。

衡量DV-Hop节点定位算法中最重要的一个性能指标就是定位精度[11]:

(21)

从公式(20)中可以看到，总的节点数(N)、信标节点数(n)、节点通信距离(R)都会对DV-Hop的定位精度产生影响。因此，本次仿真主要考虑以下3种情况，即信标节点比率与相对定位误差的关系、网络节点总个数与相对定位误差的关系、节点的通信距离与相对定位误差的关系。

3.1 信标节点比率与定位误差的关系

仿真参数：节点数为300，通信半径为25 m，信标节点比例为5%、10%、15%、20%、25%、30%。由图2明显可知，随着信标节点比率的不断增加，4种节点定位算法的相对定位误差都呈递减趋势；并且在相同条件下，本文改进算法的平均定位精度明显优于传统DV-Hop定位算法、算术平均定位算法以及加权处理定位算法。

图2 信标节点比率与定位误差的关系

3.2 网络节点总个数与定位误差的关系

图3 网络节点总个数与定位误差的关系

仿真参数：通信半径为25 m，信标节点数为30，总节点数依次为150、200、250、300、350、400、450。由图3可知，在网络节点总个数相同的情况下，本文改进算法的定位误差较低；并且随着节点总个数的增加，4种定位算法的定位误差均有所降低。本文改进定位算法误差比DV-Hop传统定位算法平均降低了8%～10%。

3.3 节点的通信距离与定位误差的关系

仿真参数：在原有网络仿真环境区域内随机产生200个传感器节点，并且使得信标节点的个数为40。为了研究节点通信半径与定位误差的关系，使节点的通信距离依次为20 m、25 m、30 m、35 m、40 m、45 m。从图4的仿真结果可以看出，本文提出改进算法的定位精度比传统的DV-Hop算法、算术平均改进算法以及加权改进算法都要高，相比传统DV-Hop定位误差降低了约7%。

图4 节点通信距离与定位误差的关系

4 结束语

本文在分析传统DV-Hop定位算法的基础上，结合已有改进算法提出了一种基于最小均方误差准则，采用对平均每跳距离进行加权处理的算法，并且对未知节点的估值位置重新进行修正。因而，本改进算法的位置估计偏差较传统的DV-Hop算法、算术平均算法以及加权处理算法都要小。仿真实验表明，本文改进算法相比传统的DV-Hop定位算法以及已有的改进算法具有很高的定位精度，并且无需增加额外的硬件设施，因此在工程上具有较强的实用性。

[1] 崔莉,鞠海玲,苗勇.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174.

[2] Corken P,Wark T,Jurdak R.Environmental Wireless Sensor Networks[J].IEEE,2010,98(11):1903- 1917.

[3] Sun G,Xu G Q B.Corrosion monitoring sensor networks with energy harvesting[J].Sensors Journal,IEEE,2011,11(6):1476-1477.

[4] Raty T D.Survey on contemporary remote surveillance systems for public safety[J].IEEE,2010,40(5):493- 515.

[5] Cenedese G，Bertinato Ortolan M.Low-density wireless sensor networks for localization and tracking in critical environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[6] NIculescu D,Nath B.Ad-hoc positioning system[A].Global Telecommunications Conference(GlobeCom),IEEE[C],2001:2926-2931.

[7] Hui Qu,Wicker Stephen B.Co-designed anchor-free localization and location-based routing algorithm for rapidly-deployed wireless sensor networks[J].Information Fusion,2007(9):425-439.

[8] Zhang S G,Cao J N,Chen L J,et al.Accurate and energy efficient range-free localization for mobile sensor networks[J].IEEE Transactions on Mobile Computing,2010,9(6):897-910.

[9] Hongyang C,SeZaki K.An improved DV-Hop localization algorithm for wireless sensor networks[A].IEEE International Conference on Industrial Electronics and Application[C],2008:1557-1561.

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

[11]Ahn H,Hong J.DV-Hop localization algorithm with multipower beacons under noisy environment[J].IEEE,2011(3):7-12.

An Improved Algorithm Based on DV-Hop Localization in Wireless Sensor Networks

CHEN Jing-jie,LUO Ming

(Xidian University,Xi'an 710071,China)

Aiming at the defect of low localization accuracy in classical localization algorithm DV-Hop in wireless sensor networks,an improved algorithm is proposed in this paper.Based on the traditional DV-Hop algorithm,this paper first adopts the minimum mean square error calibration to revise average per jump distance of beacon nodes,then performs weight to the average per jump distance from each unknown node to the reference beacon node;finally modifies the positions of unknown nodes through parameter analysis.The simulation experiment results show that the improved algorithm has high location accuracy and needs no added hardware facility compared with the traditional DV-Hop localization algorithm and previous improved algorithms,so the algorithm has good practicability in the engineering.

wireless sensor network;node localization;DV-Hop algorithm;minimum mean square error

2014-08-02

TN914

A

CN32-1413(2015)01-0070-05

10.16426/j.cnki.jcdzdk.2015.01.017