无线传感网络中基于测距修正的定位算法*

田丽芳,徐慧娟

(黄淮学院信息工程学院,河南 驻马店 463000)

项目来源:河南省科技发展计划项目(132102210020)

2017-03-14修改日期2017-06-26

无线传感网络中基于测距修正的定位算法*

田丽芳*,徐慧娟

(黄淮学院信息工程学院,河南 驻马店 463000)

为了提高DV-Hop算法的定位精度,提出基于测距修正的无迹卡尔曼滤波优化定位算法UKF-DV-Hop(Unscented Kalman Filtering Localization algorithm based on modifying average hop distance)。UKF-DV-Hop算法先对信标节点广播的信息包进行改进,然后对跳距误差进行加权处理,进而减少测距误差,再利用最小二乘法估计未知节点位置,最后再利用无迹卡尔曼滤波UKF滤波优化节点位置。实验结果表明,与传统的DV-Hop算法相比,提出的UKF-DV-Hop算法的归一化平均误差率下降了约40%。

无线传感网络;定位;DV-Hop;跳距;无迹卡尔曼滤波

由于在国防军事、环境监测、医疗救护等领域广泛应用,无线传感网络WSNs(Wireless Sensor Networks)的相关研究已受到广泛关注[]。通过WSNs中的传感节点监测环境,再传输感测数据,进而实现对环境监测、控制的目的。由于需要对环境实时、定位监控,传感节点所感测的数据必须提供相应的位置。因此,节点定位已是WSNs应用的关键技术[2-6]。

依据全球定位系统GPS(Global Positioning System),传感节点能够获取自己的位置。然而,由于传感节点属于微型器件,体积较小,给每个传感节点安装GPS系统是不现实的。因此,需要通过一些定位算法,估算传感节点的位置。通常,在WSNs中部署一些已知位置的节点,将这些节点称信标节点。而那些未知位置的传感节点称为未知节点。常用的定位算法就是通过信标节点的信息,例如距离、跳数等信息,估计未知节点的位置。

目前,现有定位技术可划分为测距定位和非测距定位[7-8]。非测距定位算法是通过网络连通等信息估计节点位置,如DV-Hop算法、Amorphous算法;而测距定位是利用离信标节点的距离信息,估计未知节点位置,测距技术主要有AOA(Angle of Arrival)、TOA(Time of Arrival)、RSSI(Received Signal Strong Indicator)等。与测距定位算法相比,非测距定位算法定位精度较低,但是它无需额外的硬件设备,适用于低成本的传感网络。

作为非测距定位算法的典型代表,DV-Hop算法因实施方便、简单,而被广泛应用于WSNs。本文重点讨论DV-Hop算法。然而,DV-Hop算法在定位精度存在较大的提升空间。DV-Hop算法先利用跳数测距,然后常采用三边测量法估计节点位置。因此,可从测距精度和定位算法两个阶段改进传统的DV-Hop算法。

文献[9]提出基于跳距修正粒子群优化的定位算法,先修正测距,然后利用粒子群优化位置估计值。而文献[10]利用簇内RSSI测距代替通过跳数测距,提高测距精度,进而降低定位误差。此外,文献[11]通过引入误差,修正跳距值,进而提高DV-Hop算法的精度。

本文针对DV-Hop定位算法的不足,提出基于测距修正的无迹卡尔曼滤波优化定位算法UKF-DV-Hop。UKF-DV-Hop算法分别从DV-Hop测距阶段和定位阶段进行改进。在测距阶段,引用测距误差,并对测距进行校正;而在定位阶段,先利用最小二乘法估计未知节点位置,然后通过无迹卡尔曼滤波优化节点位置。仿真结果表明,提出的UKF-DV-Hop算法定位算法能够提高定位精度,降低了定位误差。

1 DV-Hop测距原理及问题描述

1.1 DV-Hop测距原理

传统的DV-Hop测距过程主要有两个实施步骤:

①跳数估计

首先,由信标节点广播信息包,其包含信标节点的ID、位置坐标以及跳数。初始跳数值为1。信息包格式如表1所示。

表1 信息包格式

②平均跳距估计

通过第1步,信标节点能够获取到其他信标节点的最小跳数值以及它们位置坐标信息。为此,信标节点便可计算自己的平均跳距值。具体而言,假定信标节点Ai,它获取了m个其他信标节点的位置坐标以及最小跳数值。信标节点i计算的平均跳距Hopsizei:

(1)

式中:(xi,yi)表示信标节点Ai的位置坐标,而(xk,yk)表示除信标节点Ai外的第k个信标节点Ak位置坐标。而hik表示Ai离Ak最小跳数值。

然后,未知节点选择离自己最近的信标节点的平均跳距作为自己的平均跳距。

图1描述了DV-Hop测距过程。图中3个黑心圆为3个信标节点。L1离L2、L3的实际距离分别为40 m、100 m,而L2、L3间的实际距离为75m。3个信标节点通过交互信息包,获取了它们间的最小跳数值。如图1所示,L1离L2、L3的最小跳数分别2跳、6跳。而L2离L3的最小跳数分别为5跳。因此,通过式(1)可计算L1、L2、L33个信标节点的平均跳距:

(2)

由于未知节点A离信标节点L2最近,A就选择L2的平均跳距作为自己平均跳距,并由此平均跳距计算距离。

图1 DV-Hop测距原理

1.2 问题描述

从1.1节的分析可知,DV-Hop测距是基于网络拓扑的连通度信息,在测距时存在误差。

首先,跳数越多,测距误差越大。而网络内节点是随机分布的,节点间的跳数值有大有小,差异性大。其次,在估算距离时,是将跳数值与平均跳距的乘积代替实际距离。尽管未知节点是选择离自己最近的信标节点的平均跳距作为自己的平均跳距,但这仍然存在误差。并且通过跳数计算的距离是曲线距离,而不是直线距离。

2 UKF-DV-Hop算法

UKF-DV-Hop算法首先对DV-Hop测距进行了改进。主要从信息包格式和平均跳距两方面进行优化。在定位阶段,先用加权最小二乘法估计节点位置,再利用UKF滤波算法对所估计的位置进行修正。

2.1 测距过程

2.1.1 信息包

依1.2节分析过程,跳数越多,测距误差越大。为了避免跳数值过大,对每个信息包的跳数进行控制。即允许信息包传输的最大跳数。为此,在信息包中添加一个字段,即信息包的最大跳数。修改后的信息包字段格式如表2所示。

表2 修改后信息包格式

当信息包传输跳数已到达最大跳数值时,就不再转发该信息包。限制最大传输跳数,一方面能够降低传输跳数,另一方面,也减少信息包传递的碰撞概率,并降低网络开销。

此外,在信息包中同时添加自己的平均跳距误差ε,其计算过程见2.2.2节。

2.1.2 基于信标节点的平均跳距误差

由于系统已知信标节点位置以及每个信标节点能够通过式(1)计算平均跳距,可计算通过平均跳距所得距离与真实距离间的误差值。此误差反应了在测距值的偏差值。

(3)

(4)

通过式(3)和(4)可估计信标节点Ai的平均每跳距离误差εi:

(5)

2.1.3 权值

每个信标节点通过式(5)计算误差ε,并通过信息包获取其他信标节点的平均跳距误差,便可计算自己所估计的平均跳距的权值λ。具体而言,信标节点Ai的权值定义如式(6)所示:

(6)

从式(6)的定义可知,误差越大,权值越小。即将小误差的平均跳距赋予大权值,反之,赋予小权值。

2.1.4 未知节点估算跳距

最后,由未知节点估计自己跳距,进而测算离信标节点的距离。考虑到离未知节点距离越远的信标节点的误差越大,并且在估算跳距时,并非信标节点越多,跳距越准确。因此,未知节点只选择离自己最近的3个信标节点估计跳距。

具体而言,未知节点j,它选择离自己最近的3个信标节点,且分别表示为Aa、Ab以及Ac。这3个信标节点所估计的平均跳距以及权值分别为Hopsizea、Hopsizeb、Hopsizec以及λa、λb、λc。最终,未知节点j依据式(7)计算跳距:

(7)

从式(7)可知,未知节点所计算的平均跳距考虑了离它最近的3个信标节点所计算的平均跳距和权值,进而降低了测距误差。

2.2 定位算法

2.2.1 最小二乘法算法

先利用加权最小二乘算法估计未知节点位置,并将此位置作为后续UKF滤波的初始位置。假定未知节点i到m个信标节点的距离分别为d1、d2、d3,…,dm,且m≤n。

(8)

2.2.2UKF滤波算法

最小二乘法所估计的节点位置误差可能较大,为此,进一步利用UKF滤波,获取精确的位置估计值。

θk=Bθk-1+Vk-1

(9)

然后,建立观测方程模型。利用已测量的未知节点离信标节点的距离作为滤波观测量,所建立的观测方程如式(10)所示:

(10)

式中:(xk,yk)表示第k个信标节点位置。ηk是量测噪声向量。而Hk是雅克比矩阵,如式(11)所示。

(11)

相比于EKF算法[12],UKF算法的滤波精度更高,且不增加计算量。因此,有多数情况下,UKF算法代替EKF算法。整个UKF算法流程如图2所示。

UKF算法首先进行初始化,第2步,计算采样点;第3步,进行时间更新;第4步,实现量测更新,最后输出状态量输出。

先生成2n+1个sigma点xi。UKF算法的迭代公式如(12)所示:

(12)

式中:Wi表示sigma点xi的权值。α表示采样点均值的偏差,通常为一个小正数。而λ=α2(n+γ)-n,其中γ为调整参数。

然后,便可计算Z的均值和方差,如式(13)所示:

(13)

最后,建立非线性系统,如式(14)所示。

(14)

式中:Xk、Zk分别为状态量、观测量。而νk、ηk分别为过程噪声、量测噪声,且它们相互独立。

图2 UKF算法流程

2.2.3 定位过程

首先由锚节点广播信息包,其包含ID号和位置信息。未知节点接收后,判断是否是第1次接收该数据包,如果是,就保存该数据,并记录离该数据包的跳数值。否则,就与缓存区内记录的跳数值进行比较,并保存最小跳数值Hop。然后,依据式(7)进行跳距,并计算距离。再利用最小二乘法估计未知节点的位置,并将此位置作为UKF算法的初始值,经迭代后,最终得到未知节点位置,整个流程如图3所示。

图3 UKF-DV-Hop定位算法流程

3 仿真与分析

利用MATLAB建立仿真平台,分析UKF-DV-Hop算法性能。在100 m×100 m的区域内随机分布100个节点,其中信标节点所占比例为p%。而节点通信半径R=30 m。每次实验独立重复100次,取平均值作为最终数据。

此外,选择同类定位算法:传统的DV-Hop算法,以及改进后的基于最优通信半径的DV-Hop算法(Optimization radius DV-Hop,ORDV-Hop)[13]和基于人工蜂群改进的DV-Hop算法(Artificial Bee Colony-DV-Hop,ABDV-Hop)[14]进行同步仿真,并与UKF-DV-Hop进行比较。ORDV-Hop算法先通过网络节点分布特性,寻找最优通信半径,再利用最小二乘法修正平均跳距。而ABDV-Hop算法先将定位问题转化为全局最优问题,然后再利用人工蜂群算法估计节点坐标。

同时,考虑归一化平均定位误差NAE(Normal Average Error)和归一化均方根误差NRMSE(Normal Root Average Error)作为性能指标,定义如式(15)所示[15]。

(15)

3.1 仿真数据

在实验过程中,重点分析信标节点数对NAE、NRMSE性能影响。

首先分析信标节点比例对NAE的性能影响。节点通信半径R=30 m,信标节点百分比p%从10%至35%变化,实验数据分别如图4所示。

图4 NAE随信标节点比例的性能影响

从图4可知,信标节点p%的增加,降低了NAE。原因在于:信标节点百分比的增加,降低了某一个信标节点对定位精度的影响,相应地,减少了NAE。与DV-Hop算法相比,提出的UKF-DV-Hop算法的NAE下降40%,并且也低于ORDV-Hop和ABDV-Hop算法。

图5 NRMSE随通信半径的性能影响

然后,再分析了节点通信半径对NRMSE的影响。信标节点比例p%=20%,节点通信半径R从20～40变化,实验数据如图5所示。

从图5可知,提出的UKF-DV-Hop定位算法的NRMSE最低。原因在于UKF-DV-Hop定位算法有效地修正了DV-Hop测距值,同时通过UKF滤波算法优化位置估计值。此外,从图5可知,通信半径的增加有利于提高定位精度,但是,当通信半径增加到一定值后,NRMSE并没有下降。这说明一味地增加通信半径,并不能降低NRMSE。

4 总结

传统的DV-Hop定位算法在测距阶段,只是简单地采用单一方式计算平均跳距,增加了测距误差。为此,基于测距修正的无迹卡尔曼滤波优化定位算法UKF-DV-Hop。UKF-DV-Hop算法先优化跳距,降低测距误差,然后通过UKF优化节点位置估计值。实验结果表明,提出的UKF-DV-Hop算法在定位误差性能方面优于传统的DV-Hop算法。

[1] 梁玉琴,曾庆化,刘建业. 基于UKF滤波的WSN节点定位研究[J]. 传感技术学报,2010,23(6):878-883.

[2] Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magazine,2012,7(5):28-34.

[3] Patwari N,Hero A,Perkins M,et al. Relative Location Estimation in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2013,51(8):2137-2148.

[4] 李娟,刘禹,钱志鸿,等. 基于双通信半径的传感器网络DV-Hop定位算法[J]. 吉林大学学报(工学),2014,44(2):502-508.

[5] 金纯,叶诚,韩志斌.无线传感器网络中DV-Hop定位算法的改进[J]. 计算机工程与设计,2013,34(2):401-405.

[6] 王新生,赵衍静,李海涛. 基于DV-Hop算法的改进研究[J]. 计算机科学,2011,38(2):76-78.

[7] Patwari N,Hero A,Perkins M,et al. Relative Location Estimation in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2013,51(8):2137-2148.

[8] Xiao Q,Xiao B,Cao J,et al. Multihop Range-Free Lcalization in Anisotropic Wireless Sensor Networks:A Pattern-Drive Scheme[J]. IEEE Trans. Mobile Comput,2013,9(11):1592-1607.

[9] 赵雁航,钱志鸿,尚小航,等. 基于跳距修正粒子群优化的WSN定位算法[J]. 通信学报,2013,34(9):105-115.

[10] 黄晨钟,许力,叶阿勇. 基于簇内RSSI测距改进的DV-Hop算法[J]. 福建师范大学学报,2010,26(6):29-34.

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

[12] Julier S U,Durrant W H F. A New Method for the Nonlinear Transformation of Means and Covariance in Filters and Estimators[J]. IEEE Transactions on Automatic Control,2010,45(3):477-482.

[13] 吴玉成,李江雯. 基于最优节点通信半径的改进DV-Hop定位算法[J]. 华南理工大学学报(自然科学版),2012,40(6):35-42.

[14] 李牧东,熊伟,梁青. 基于人工蜂群改进算法的无线传感网络定位算法[J]. 传感技术学报,2013,26(2):241-245.

[15] 乔欣,常飞,丁恩杰,等. 基于跳距修正的WSN拟牛顿迭代定位算法[J]. 传感技术学报,2014,27(6):797-801.

LocalizationAlgorithmBasedonModifyingAverageHopDistanceinWirelessSensorNetworks*

TIANLifang*,XUHuijuan

(School of Information Engineering,Huanghuai University,Zhumadian He’nan 463000,China)

In order to improve the localization accuracy of DV-Hop,Unscented Kalman Filtering(UKF)Localization algorithm based on modifying average hop distance(UKF-DV-Hop)is proposed in this paper. Firstly,the he structure of data packets by anchor nodes with broadcasting is changed,then average hop distance error is modified,in order to reduce the ranging error. An inaccurate position coordinate of the unknown node was obtained by least square estimation(LSE),and an accurate node localization method was achieved by using UKF.Numerous simulation results show that normalized average localization error ratio of UKF-DV-Hop algorithm is about 40% less than that of traditional DV-Hop algorithm.

wireless sensor network;localization;DV-Hop algorithm;Hop distance;unscented kalman filtering

TPT393

A

1004-1699(2017)10-1572-06

10.3969/j.issn.1004-1699.2017.10.020

田丽芳(1981-),女,汉族,山西长治人,硕士,讲师,研究方向为数据挖掘、软件测试、系统建模;

徐慧娟(1977-),女,汉族,驻马店人,硕士,副教授,研究方向为数据挖掘、系统分析与建模。