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

曹广华 张红杰

(东北石油大学电气信息工程学院，黑龙江 大庆 163318)

无线传感器网络(Wireless Sensor Network，WSN)是由大量智能传感器节点构成的具有信息感知、信息传送和信息处理能力的综合型智能信息网络，具有成本低、自组织和环境适应性强的特点[1,2]。节点定位是WSN的关键技术之一，目前使用较多的无线传感器网络定位方法有基于测距的定位算法和无需测距的定位算法。笔者将对无需测距的DV-Hop定位算法进行分析并对其加以改进。

1.1 DV-Hop算法

根据节点是否已知自身的位置，传感器节点分为信标节点和未知节点。信标节点在网络中所占的比例小，可以通过携带GPS定位设备等措施获得自身的精确位置，未知节点利用信标节点的位置信息来确定自身位置。DV-Hop算法是一个典型的利用信标节点间多跳信息来确定未知节点位置的定位策略，传统DV-Hop算法可以分为以下3个步骤[3,4]。

首先获取节点与每个信标节点间的最小跳数。根据典型的距离矢量路由协议，每个信标节点向网络中广播自身的位置信息分组，网络中的全部节点能够记录下到每个信标节点的最小跳数。

然后计算信标节点与未知节点的距离。每一个信标节点按照自身列表中记录的其余信标节点的位置和最小跳数信息，计算平均每跳距离hopsizei，计算式为：

(1)

其中hij为信标节点i和j的最小跳数；(xi,yi)、(xj,yj)分别为信标节点i和j的坐标。

未知节点根据接收到的平均跳距和记录到的每个信标节点的最小跳数，通过下式计算出与每个信标节点的距离：

d=hopsizei×N

(2)

其中，N为未知节点与信标节点的最小跳数。

最后利用三边法或极大似然估计法计算未知节点的自身位置。

1.2 DV-Hop算法误差分析

DV-Hop算法是一种非测距方法，实现简单且能耗适中。在节点分布均匀的各向同性密集网络中，节点的定位精度较高。但在网络节点分布不均匀的网络中，由于节点的随机部署，信标节点相对未知节点的数量和位置分布不均匀，致使信标节点估计的平均每跳距离不能准确地反映全网的平均每跳距离，在使用式(2)时会造成较大的累积误差，对定位精度有很大程度的影响，所以未知节点需要选择合适的信标节点进行定位才能使定位精度更准确[5]。

2 DV-Hop改进算法

笔者针对平均每跳距离误差大的问题，使用文献[6]中提到的跳距误差修正方法，使计算出的每跳距离尽可能地反映网络的平均跳距。对于信标节点分布对定位精度的影响，提出一种基于拟合曲线的未知节点选择最佳信标节点参与定位的方法。

2.1 跳距误差修正方法

每个信标节点先根据传统DV-Hop算法的第二阶段计算出平均每跳距离，将平均跳距广播至网络中，广播数据分组信息为{ID，hopsizei}，ID为信标节点序号，hopsizei为信标节点i计算的平均跳距，每个节点接收所有信标节点的平均跳距并将该跳距信息添加到自己的数据列表中，再将信息分组向邻居节点广播，忽略重复的ID信息分组，然后每个节点将记录的所有平均跳距相加取平均值，得到全网的平均跳距aver为：

(3)

其中，n为信标节点的总数。之后每个信标节点再根据下式得到自身平均跳距误差值ei：

(4)

经过跳距误差修正后最终信标节点i的平均每跳距离hopi为：

hopi=aver+k×ei，-1≤k≤1

(5)

根据文献[6]可知，变量参数k取0.7最佳。最后信标节点将新的校正值hopi广播到网络中。

2.2 最佳信标节点选择算法

在传统DV-Hop算法中，未知节点只要获得与3个或3个以上信标节点的距离时就可进行定位计算[7]，但由于信标节点相对于未知节点的位置分布会对定位精度造成较大的影响，并不是所有信标节点都参与定位计算定位精度就越高，未知节点要有选择地选取最佳的信标节点参与定位计算，才能使定位结果更加准确。信标节点位置分布如图1所示，黑色圆点表示信标节点，空心圆点表示未知节点，实线表示跳段，虚线表示实际距离。未知节点A用信标节点B、C进行定位计算，当用跳距乘以跳数表示AB与AC的距离时，显然AB的估计距离要比AC的估计距离更接近实际距离，因为未知节点A到信标节点B的跳段路径更接近一条直线。基于以上分析，笔者提出一种选择最佳信标节点的方法。

图1 信标节点位置分布

(6)

图2 信标节点选择

使用多个平均跳距计算距离。在新算法中结合跳距误差修正算法，未知节点接收所有信标节点的平均跳距，并将该信息记录在列表中，然后未知节点使用被选择出的信标节点各自的平均跳距乘以跳数作为未知节点与被选择信标节点的距离。

精确计算未知节点坐标。未知节点利用所选择出来的信标节点使用极大似然估计法再次精确计算自身坐标。由于未知节点与所选择的信标节点的距离不会偏向于曲折的跳段过程，更接近直线，更能反映真实距离，所以再次计算出的未知节点坐标会更加准确。

3 改进算法的仿真和分析

为了验证改进DV-Hop算法在提高节点定位精度方面的有效性和可行性，使用Matlab进行仿真实验。仿真实验的网络区域模型参数为：在100m×100m的区域进行实验，节点通过随机方式布置，所有节点的通信半径都相同，为了取得客观准确的实验数据，所有数据采用100次实验的平均值[10]。对传统算法、已有的基于跳距误差修正的算法和笔者提出的改进算法的定位精度进行比较，分析改进算法的性能。

定位精度C[11]一般用定位误差值与节点通信半径的比值表示，即：

(7)

式中 (xest,yest)——算法计算的节点坐标；

(xture,yture)——节点实际坐标。

由式(7)可知，节点定位精度C值越小表示定位越准确。

图3描述了在相同网络环境下，所有节点的通信半径R=20m，节点总数分别为100和200时，传统DV-Hop算法、基于跳距误差修正的算法与笔者提出的改进算法定位精度随信标节点比例的变化情况。可以看出，与传统算法和基于跳距误差修正的算法相比，当信标节点数较少时，笔者改进算法提高定位精度幅度不大，因为未知节点可选择的最佳信标节点数较少。但随着信标节点比例的增大，由于笔者改进算法充分考虑了信标节点位置的分布情况并且加入了跳距误差修正算法，使距离计算更准确，所以更有效地提高了定位精度，稳定性也越来越强。当网络规模增大时(从100节点增加到200节点)，定位精度也明显提高，如图3a中当信标节点比例为15%时，定位精度大约为44%；而图3b中，信标节点比例同样为15%时，定位精度为33%。

a. 节点总数为100

b. 节点总数为200

图4描述了在相同网络环境下，信标节点比例为15%、节点总数分别为100和200时，传统DV-Hop算法、基于跳距误差修正的算法与笔者提出的改进算法定位精度随节点通信半径变化的情况。

a. 节点总数为100

b. 节点总数为200

可以看出，随着节点总数的增加，3种算法的定位误差都有所减小，在节点通信半径从10变化到40的过程中，笔者提出的改进算法的定位精度均比传统算法和跳距修正的算法的定位精度高，这是由于改进算法在基于跳距误差修正的基础上又充分考虑了信标节点分布对定位精度的影响，选择合适的信标节点参与定位计算，并且使用每个被选择信标节点的每跳跳距进行距离计算，使未知节点与信标节点的估算距离更好地反映网络实际节点间距，定位才更准确。

4 结束语

笔者在分析现有DV-Hop算法原理和产生误差原因的基础上，提出了改进算法，改进的算法考虑了信标节点位置的分布情况，取最接近直线分布的信标节点作为计算用的参考节点，从本质上更接近使用跳距定位算法的定位原理，可以提高定位精度。当网络规模扩大、信标节点数增多时，笔者提出的改进算法的定位精度比传统算法都有明显的提高；当信标节点数比例不变，网络规模扩大时，随着节点通信距离的提高，笔者提出的改进算法对定位精度也有较显著的改善效果。

[1] Akyildiz I F,Su W L,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002,40(8)：102～114.

[2] 任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282～1291.

[3] Xiao J,Chen H, Zhang S.Research of Range-Based Syner-getic Localization Algorithm in Wireless Sensor Networks[C].2008 Control and Decision Conference.Shandong:IEEE,2008:2040～2044.

[4] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857～868.

[5] Mao G Q,Fidan B，Anderson B D O.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529～2553.

[6] 李辉,熊盛武,刘毅,等.无线传感器网络DV-Hop定位算法的改进[J].传感技术学报,2011,24(12):1782～1786.

[7] 张佳,吴延海,石峰,等.基于DV-Hop的无线传感器网络定位算法[J].计算机应用,2010,30(2):323～326.

[8] 刘少强,庞新苗,樊晓平,等.一种有效提高节点定位精度的改进DV-Hop算法[J].传感技术学报,2010,23(8):1179～1183.

[9] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems,2003,22(1-4):267～280.

[10] Basagni S,Carosi A,Melachrinoudis E,et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks[J].ACM SIGMO-BILE Mobile Computing and Communications Review,2006,10(4):28～30.

[11] Poggi C,Mazzini G.Collinearity for Sensor Network Localization[C].Proceedings of 2003 IEEE 58th Vehicular Technology Conference.Piscataway,NJ,USA:IEEE,2004:3040～3044.