一种基于EKF的WSN目标跟踪改进算法

李化,朱钾

(1.太原理工大学 信息工程学院,山西 榆次 030600;2.太原理工大学 信息工程学院,山西 榆次 030600)

一种基于EKF的WSN目标跟踪改进算法

李化1,朱钾2*

(1.太原理工大学 信息工程学院,山西 榆次 030600;2.太原理工大学 信息工程学院,山西 榆次 030600)

在目标跟踪领域,无线传感器网络有着广泛的应用。针对EKF算法非线性目标跟踪中存在的问题,在EKF算法的基础上引入RSSI测距加权质心算法，从而提出了一种新的非线性目标跟踪算法,将节点的观测值与RSSI测距加权质心算法对目标的定位值有效的结合运用于EKF算法中,有效地提高了目标跟踪的精度,减小了跟踪误差。通过算法仿真可知,与几种定位算法及非线性滤波算法相比,改进算法在各方面均取得了良好的效果,并且具有较高的实时性。

WSN目标跟踪;EKF算法;加权质心算法

0 引言

无线传感器网络(Wireless Sensor Networks,WSN)由大量传感器节点构成,具有能耗低、自组织、集成化等特点,能够起到监测、监督等作用,在军事、航空、防爆、救灾、环境、医疗等方面均有广泛的应用前景。在目标跟踪领域,WSN也发挥着重要的作用。算法的跟踪精度和复杂度是衡量WSN目标跟踪的两个重要指标,通常采用跟踪时间来表示算法的复杂度,跟踪时间越长也就意味着算法越复杂。目前实现WSN目标跟踪主要有以下两类方法:(1)通过目标定位得到跟踪轨迹。常见的目标定位算法可分为两种:一种是基于测距的目标定位,例如TOA、TDOA、AOA、RSSI等[1-3]算法,这类算法虽具有较高的实时性但跟踪精度较差;另一种为基于非测距的目标定位,例如加权质心[4-5]、DV-Hop、Amorphous、APIT等,这类算法虽然减少了节点对目标测距带来的误差但在目标跟踪过程中仍存在很大的误差。除此之外还有很多定位方法,如数据融合[6]、数据压缩、RFID[7]、ZigBee[8]等。(2)基于采样数据的预测得到跟踪轨迹。常见的预测算法有以下两种:一种是滤波算法,包括卡尔曼滤波(KF)、扩展卡尔曼滤波(EKF)、无迹卡尔曼滤波(UKF)、粒子滤波(PF)等。KF算法仅适用于线性系统,EKF、UKF及PF算法虽适用于非线性系统,但很难兼顾跟踪精度和实时性要求;另一种为基于神经网络算法,例如BP网络、RBF网络、遗传算法[9]等,根据节点观察到的目标信息对目标进行预测跟踪。此外针对WSN目标跟踪过程中存在的问题有很多改进算法,例如文献[10]针对跟踪过程中能耗问题,为了缩短预测时间提出了一种新的唤醒节点方式和跟踪方法,其跟踪时间明显优于EKF和UKF算法;文献[11]针对跟踪过程中数据融合问题提出了一种恒定增益的KF算法,并具有良好的性能;文献[12]中通过采用KF与PF算法相结合的方式减少目标跟踪过程中误差,但由于KF不能应用于非高斯噪声情况而存在缺陷;文献[13]在KF基础上提出了一种新的线性滤波器,其预测精度也高于EKF算法。

由于目标的运动轨迹往往是非线性的,因此在跟踪过程中存在很大的困难。本文针对非线性EKF算法在跟踪中存在的问题,在EKF算法的基础上引入RSSI测距加权质心算法,将节点对目标的观测值与RSSI测距加权质心算法对目标的定位值进行有效地结合,克服了EKF算法中雅克比矩阵计算的困难,同时也提高了非线性目标跟踪的跟踪精度。通过算法仿真对比,与三种目标定位算法(三边测量、极大似然估计、RSSI测距加权质心)和三种非线性滤波算法(极大似然卡尔曼滤波(MLKF)、EKF、UKF)相比,改进算法具有良好的跟踪效果,且在跟踪过程中更加接近于目标的真实状态,具有良好的实时性且跟踪精度接近于UKF算法。

1 EKF算法

EKF算法是在Kaman滤波算法基础上的拓展,通过对非线性系统的状态方程及测量方程进行Taylor级数展开忽略其高阶项而取一阶项,同时采用雅克比(Jacobian)矩阵替代Kalman滤波线性变换部分,将非线性问题进行有效的线性化处理,然后采用Kaman滤波算法进行估计,实现了非线性运动目标的预测。假设EKF系统的状态方程和测量方程分别如下:

Xi=f(Xi-1,Ui-1)+Wi-1

(1)

Zi=h(Xi,Ui)+Vi

(2)

其中,f(·)、h(·)分别为系统的状态函数和观测函数,且均为非线性,Xi表示i时刻目标的系统状态向量,Zi表示i时刻节点对目标的观测向量,Ui-1表示系统控制的输入向量,Wi-1～N(0,Q),Vi～N(0,R),Wi-1、Vi相互独立,分别为系统的随机噪声和量测噪声。非线性系统的预测方程及更新方程如下所示:

(3)

Pi|i-1=APi-1AT+Q

(4)

Pi=(I-KiHi)Pi|i-1

(5)

(6)

(7)

(8)

(9)

其中,Ki为系统滤波增益,Pi|i-1和Pi分别是系统的预测误差协方差矩阵和估计误差协方差矩阵,初始协方差矩阵P1及I均为四维单位矩阵,系统的状态转移矩阵A=[1,T,0,0;0,1,0,0;0,0,1,T,0,0,0,1],T为采样时间,Q、R分别为高斯白噪声的方差,取Q=e-4*diag([0.25,1,0.5,3]),R=4,T=1[14-15]。

由上述分析可知:EKF算法虽然可以将非线性问题进行有效的线性化处理,但对于一些特殊的非线性系统其雅克比矩阵计算难度较大,而且只有在雅克比矩阵存在情况下才能进行有效的预估,同时算法中的噪声均为高斯白噪声,因此该算法存在一定的缺陷。

2 改进算法

针对EKF算法存在的缺陷,改进算法在EKF算法的基础上引入RSSI测距加权质心算法,通过节点的观测值与目标的定位值构建非线性系统的雅克比矩阵和量测误差,即具有了定位算法的特点同时也结合了非线性滤波算法的特性,这样既可有效地克服EKF算法中雅克比矩阵矩阵计算的困难,同时提高了目标跟踪精度,降低了算法的复杂度。在仿真区域内部署已知位置信息的信标节点、汇聚节点及管理节点。通过信标节点对目标进行检测、采样及定位,由汇聚节点向信标节点发布来自管理节点的检测任务,并把WSN收集到的数据转发到计算机中,以便实时查询目标状态。管理节点每隔一个采样时间发布一次检测命令,由汇聚节点唤醒仿真区域周边的信标节点进行检测,而其他区域节点仍保持睡眠。当信标节点N检测到目标靠近时,汇聚节点则马上唤醒N节点周围的其他信标节点对目标进行检测和采样,改进算法的伪代码如图1所示。

Fig.1 Pseudo Code of the Improved Algorithm
图1改进算法的伪代码

2.1 RSSI测距加权质心算法

由于信号强度随着传输距离的增加而不断衰减,将信号衰减的差值根据特定的模型可转换为相应距离,因此RSSI测距模型可表示为:

(1)

其中,P(d0)表示距离发射信号d0处的接收信号强度值,Pr(dr)表示接收信号的强度值,d0为参考距离,n1为衰减因子,通常取n1=2～4,ξσ～N(0,σ2),则估计距离dr可表示为:

(2)

(3)

由上述可知,虽然RSSI测距加权质心算法在一定程度上提高了目标的定位精度,但由于RSSI测距模型的衰减因子及噪声的取值均易受环境等因素的影响,因此该定位算法仍存在着一定的局限。

2.2 EKF改进

改进算法通过节点对目标的观测及RSSI测距加权质心算法对目标的定位建立EKF算法非线性系统,由目标观测值(xt,yt)及定位值(xwc,ywc)构建改进系统的量测误差e1及测量矩阵H1来替传统EKF算法中的e0和H0,其分别表示如下所示:

(4)

(5)

由上述分析可知:EKF算法通过忽略高阶项将非线性问题进行线性化处理,而改进算法通过引入RSSI测距加权质心算法构建系统测量矩阵将非线性问题进行线性化处理。与EKF算法相比,改进算法有效地减小了在线性化过程在中存在的误差,克服了EKF中雅克比矩阵计算的困难,弥补了EKF算法的不足;与RSSI测距加权质心算法相比,改进算法在RSSI测距加权质心算法对目标定位值的基础上进行实时估计,虽然RSSI测距模型受环境等因素的影响存在一定的误差,但是改进算法通过EKF的预测有效地减小跟踪中的误差。

3 算法仿真与分析

仿真过程中各算法均在win7 64位系统Matalb2013a环境下运行。仿真实验分为两部分:(1)改进算法与三边测量、极大似然估计及RSSI测距加权质心三种定位跟踪算法的对比;(2)改进算法与MLKF、EKF及UKF算法仿真对比分析。为了覆盖整个部署区域,在100 m×100 m的区域内每隔10 m固定安置一个已知位置信息的信标节点。假设目标初始位置为(0,10),目标沿X轴方向上做1.8 m/s的匀速运动,Y轴方向上做变速运动。仿真过程中对目标进行50次采样,由式(12)计算各算法的均方根误差(Root Mean Square Error,RMSE),并通过10次仿真取平均值得到算法的均方根误差均值(ARMSE)、X、Y轴方向上的均方根误差均值和跟踪所用的时间。

(6)

Fig.2 Target tracking trajectory图2 目标跟踪轨迹

3.1 定位算法对比

三边测量、极大似然估计及RSSI测距加权质心是三种目标定位算法,通过WSN节点对各采样时刻对目标的定位,将目标实时定位坐标进行拟合即可得到跟踪轨迹。改进算法与三种定位算法的跟踪轨迹如图2所示,四种算法的RMSE对比结果如图3所示,X轴、Y轴方向上的ARMSE及完成跟踪所用时间的对比如表1所示。

由上述对比结果可知:(1)RSSI测距加权质心算法由于测距模型受环境等因素的影响,其跟踪误差明显高于改进算法和三边测量法,但该算法计算量最小,完成跟踪耗时最少。(2)极大似然估计算法

Fig.3 Localization algorithm RMSE图3 定位算法RMSE

表1 改进算法与定位算法对比Table 1 Comparison of improved algorithm and localization algorithm

虽是在三边测量法基础上的延伸,但在目标与传感器节点距离较近的情况下,由于多个节点检测到目标,反而导致对目标的定位结果产生较大的误差,而且跟踪时间最长。(3)三边测量法通过各采样时刻有效检测到目标的三个传感器节点进行定位,其ARMSE值虽略低于RSSI测距加权质心算法,但与改进算法相比各指标仍有一定的差距。(4)RSSI测距加权质心算法虽然存在较大的误差,但是通过EKF算法的预测,使目标状态的估计值接近于目标真实值,因此改进算法的RMSE、AMNSE、X轴方向上的ARMSE及Y轴方向上的ARMSE均小于其他三种算法,有效地提高了目标跟踪精度,减小了RSSI测距加权质心算法对目标定位的误差。改进算法虽在一定程度上增加了计算但其跟踪时间明显小于三边测量法和极大似然估计算法。

3.2 滤波算法仿真

改进算法在EKF算法的基础上引入RSSI测距加权质心算法,因此该算法在一定程度上具有定位算法特点,同时也具有EKF算法非线性目标跟踪的特性,能够有效地减小跟踪误差,有良好的实时性。对图1中目标进行仿真跟踪,假设跟踪过程中噪声均为高斯白噪声,改进算法与三种滤波算法(MLKF、EKF、UKF)的仿真对比结果如图4-7所示,各算法的对比结果如表2所示。

Fig.4 Filter algorithm RMSE图4 滤波算法RMSE

Fig.5 X axis direction RMSE图5 X轴方向上RMSE

由以上对比结果可知:(1)MLKF的RMSE及ARMSE值均明显高于其他三种算法,其虽然是Kalman滤波与极大似然估计算法的有效结合,但对于非线性目标跟踪该算法仍有很大的误差。(2)EKF算法的RMSE及ARMSE值略高于UKF和改进算法,并且由于雅克比矩阵计算而需要消耗很多的时间,而改进算法虽在此基础上引入RSSI测距加权质心算法但并未因此而增加计算量。(3)UKF需要经过UT变换将采样时刻得到的目标样本概率密度函数转换为有限的Sigma样本点,通过非线性变换完成目标状态的估计,所以其需要耗费大量的时间。在本文条件下,改进算法完成跟踪所用的时间接近于UKF算法的一半。(4)虽然改进算法与EKF和UKF的RMSE及ARMSE值均较为接近,但对于目标运动速度RMSE值相比,改进算法明显低于EKF及UKF算法。该算法通过RSSI测距加权质心准确对目标进行定位,以便EKF算法在预测过程中更加精确,提高了目标跟踪精度,并且完成跟踪耗时也较小,因此该算法更加接近目标运动的真实状态且具有较好的实时特性。

Fig.6 Y axis direction RMSE图6 Y轴方向上RMSE

Fig.7 Tracking speed RMSE图7 跟踪速度RMSE

表2 改进算法与滤波算法对比Table 2 Comparison of improved algorithm and filter algorithm

4 结论

通过RSSI测距加权质心算法对目标的定位,改进算法将各采样时刻目标的观测值与定位值有效地应用于EKF中,重新构建EKF系统中的参数,有效地克服了非线性系统中雅克比矩阵计算的困难,缩短了完成跟踪过程所用的时间,提高了跟踪精度并具有较好的实时性。与三种定位算法及三种非线性滤波算法相比,改进算法不仅具有较高的跟踪精度,而且跟踪时间是UKF算法一半左右,其速度ARMSE也明显小于其他三种滤波算法,更加接近目标的真实状态。但由于引入了RSSI测距模型受环境等因素影响,跟踪过程中其RMSE值出现不断起伏的现象。然而在环境较复杂情况下,RSSI测距模型由于受到环境等因素的干扰其衰减因子和噪声的取值将受到很大的影响,目标的定位值和估计距离都将存在较大的误差,并且EKF系统仅适用于高斯噪声情况,因此与适用于非线性非高斯的算法相比,改进算法仍存在一定的局限性。

[1] Jamalabdollahi M,Zekavat S A.Joint Neighbor Discovery and Time of Arrival Estimation in Wireless Sensor Networks via OFDMA[J].IEEESensorsJournal,2015,15(10):5821-5833.DOI:10.1109/JSEN.2015.2449079.

[2] Lopes S I,Vieira J M N,Reis J,etal.Accurate Smartphone Indoor Positioning Using A WSN Infrastructure and Non-invasive Audio for TDoA Estimation[J].PervasiveandMobileComputing,2015,20:29-46.DOI:10.1016/j.pmcj.2014.09.003.

[3] Li Wenling,Jia Yingmin,Du Junping.RSS-base Joint Detection and Tracking in Mixed LOS and NLOS Environments[J].DigitalSignalProcessing,2015,43:38-46.DOI:10.1016/j.dsp.2015.05.001.

[4] Hany U,Wahid K A.An Adaptive Linearized Method for Localizing Video Endoscopic Capsule Using Weighted Centroid Algorithm[J].InternationalJournalofDistributedSensorNetworks,2015,2015:1-19.DOI:10.1155/2015/342428.

[5] Chen Shouwen,Xu Zhouming,Tang Yan,etal.An Improved Particle Swarm Optimization Algorithm Based on Centroid and Exponential Inertia Weight[J].MathematicalProblemsinEngineering,2014,2014:1-15.DOI:10.1155/2014/976486.

[6] Yan Junkun,Liu Hongwei,Pu Wenqiang,etal.Benefit Analysis of Data Fusion for Target Tracking in Multiple Radar System[J].IEEESensorsJournal,2016,16(16):6359-6366.DOI:10.1109/JSEN.2016.2581824.

[7] Sun Lijun,Zhou Shijie,Luo Jiaqing,etal.ARNS:Adaptive RFID Network Scheduling for Device-Free Tracking[C]∥IEEE 9th International Conference on Mobile Ad-hoc and Sensor Networks (MSN),2013:248-253.DOI:10.1109/MSN.2013.29.

[8] Alhmiedat T,Omar F,Abu Taleb A.A Hybrid Tracking System for ZigBee WSNs[C]∥6th International Conference on Computer Science and Information Technology (CSIT),2014:71-74.DOI:10.1109/CSIT.2014.6805981.

[9] Mansouri M,Nounou H,Nounou M.Genetic Algorithm-based Adaptive Optimization for Target Tracking in Wireless Sensor Networks[J].JournalofSignalProcessingSystemsforSignalImageandVideoTechnology,2014,74(2):189-202.DOI:10.1007/s11265-013-0758-y.

[10] Mirsadeghi M,Mahani A.Energy Efficient Fast Predictor for WSN-based Target Tracking[J].AnnalsofTelecommunications,2015,70(1/2):63-71.DOI:10.1007/s12243-014-0430-y.

[11] Yadav A,Naik N,Ananthasayanam M R,etal.A Constant Gain Kalman Filter Approach to Target Tracking in Wireless Sensor Networks[C]∥IEEE International Conference on Industrial and Information Systems 7th,2012:1-7.DOI:10.1109/ICIInfS.2012.6304803.

[12] Éfren L S,Eduardo F N,Horcio A B F D O,etal.Reducing the Impact of Location Errors for Target Tracking in Wireless Sensor Networks[J].JournaloftheBrazilianComputerSociety,2013,19(1):89-104.DOI:10.1007/s13173-012-0084-4.

[14] Su Lingdong,Zhai Mingyue,Mao Qilin.Target Tracking of Binary Wireless Sensor Networks in the Domain of Medicine and Healthcare[J].InternationalJournalofSensorNetworks,2015,17(3):188-194.DOI:10.1504/IJSNET.2015.068183.

[15] Nayebi-astaneh A,Pariz N,Naghibi-sistani M B.Adaptive Node Scheduling under Accuracy Constraint for Wireless Sensor Nodes with Multiple Bearings-only Sensing Units[J].IEEETransactionsonAerospace&ElectronicSystems,2015,51(2):1547-1557.DOI:10.1109/TAES.2014.130476.

[16] Yao Yingbiao,Qi Han,Xu Xiaorong,etal.A RSSI-Based Distributed Weighted Search Localization Algorithm for WSNs[J].InternationalJournalofDistributedSensorNetworks,2015:1-12.DOI:10.1155/2015/293403.

[17] Gao L.Trilateration Based Clustering Target tracking algorithm[J].JournalofComputerApplications,2014,34(6):1578-1581.

[18] Marelli D,Fu Minyue.Asymptotic Optimality of the Maximum-Likelihood Kalman Filter for Bayesian Tracking with Multiple Nonlinear Sensors[J].IEEETransactionsonSignalProcessing,2015,63(17):4502-4515.DOI:10.1109/TSP.2015.2440220.

AnImprovedWSNTargetTrackingAlgorithmBasedonEKF

LI Hua1,ZHU Jia2*

(1.CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Yuci030600,China;2.CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Yuci030600,China)

In the field of target tracking, wireless sensor networks have a wide range of applications. Aiming at the problem of nonlinear target tracking in EKF algorithm, a new improved algorithm is proposed by introducing RSSI distance weighted centroid algorithm based on the EKF algorithm. Combining the observation value of the node and the RSSI distance weighted centroid algorithm to the target's location value effectively in the EKF algorithm, it can effectively improve the accuracy of the target tracking and reduce the tracking error. Through the algorithm simulation, compared with several positioning algorithms and nonlinear filtering algorithms, the improved algorithm can achieve good results in all aspects and has a high real-time performance.

WSN target tracking;EKF algorithm;weighted centroid algorithm

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.013

2016-09-07；

2017-01-03

山西省自然科学基金(2014011019-1);中国国家留学基金委(201606935043)

李化(1972-),女,讲师,博士,主要研究通信及信息处理。E-mail:zhujia0200@link.tyut.edu.cn

*通信作者：朱钾(ZHU Jia),E-mail:18234082115@163.com

TP391

A

0253-2395(2017)04-0743-07