无线传感网络中基于误差椭圆的自适应节点 选择目标跟踪算法*

周 非,安康宁,范馨月,高建军

(重庆邮电大学光通信与网络重点实验室,重庆 400065)

项目来源:国家自然科学基金项目(61471077)

2017-04-26修改日期2017-06-12

无线传感网络中基于误差椭圆的自适应节点 选择目标跟踪算法*

周 非*,安康宁,范馨月,高建军

(重庆邮电大学光通信与网络重点实验室,重庆 400065)

追踪精度与传感器节点能耗是无线传感网络WSN(Wireless Sensor Network)中主要考虑的两个性能指标,现有的许多目标追踪算法在提高追踪精度、降低传感器节点能耗的同时缺乏对传感器节点位置与数目的考虑。因此,提出一种基于误差椭圆的自适应节点选择目标追踪算法,以误差椭圆为基准计算目标最可能出现的区域,然后根据误差判决调整区域内所需激活的传感器节点数量,完成对目标的跟踪。仿真结果表明,该算法可以在保证追踪精度的同时有效降低激活传感器节点数量。

无线传感网络;目标追踪;误差椭圆;误差指示器;扩展卡尔曼滤波

无线传感网络是一种新型的信息获取及处理平台,由部署在监测区域内的大量传感器节点组成,传感器节点之间可以通过无线通信组成一个多跳的自组织网络系统[1-2]。基于无线传感网络的目标跟踪[3]系统具有部署方便、成本低且跟踪精度高等优点,但传感器节点能量有限且电池更换困难,因此选取最优传感器节点参与观测能有效延长无线传感网络系统的使用寿命。

文献[4]提出了一种基于预测机制的低功耗目标追踪算法,以角度为观测量对目标状态进行预测,最后利用最小二乘估计(Least Square Estimation)完成对目标的追踪,但其算法十分简单,并未考虑其他约束,在现实生活中难以应用。Wang等人[5]考虑乘性噪声(Multiplicative Noise)对观测量的影响,以极大似然估计(Maximum Likelihood Estimation)与牛顿-拉夫逊迭代方法(Newton-Raphson Iterative Method)完成对观测量的预处理,最后进行卡尔曼滤波(Kalman Filter)完成目标追踪。但其算法复杂度较高,计算量较大。Li 等人在文献[6]中提出一种基于自适应强跟踪粒子滤波(Particle Filter)的目标追踪算法,通过每一时刻真实观测值与预测观测值之间的冗余使遗忘因子与软化因子达到自适应的状态。该算法的缺点是样本数量较多,计算量较大。Cheng等人在文献[7]中对移动节点的感知质量与网络覆盖率进行了分析,在扩展卡尔曼(Extended Kalman Filter)的基础上提出基于梯度的节点运动控制策略。文献[8]提出一种自适应节点选择扩展卡尔曼滤波算法,以DMR(Delta Measurement Residual)、目标节点移动速度以及追踪时间为参考调整每一次所需观测量的数目。文献[9]中,未避免对系统噪声等先验信息的依赖,作者提出一种基于粒子群有计划地最小剩余定位算法,进而采用数据拟合将非迭代算法转换为迭代算法,完成对目标的追踪定位。Feng等人在文献[10]中提出一种分布式无线传感网络的自适应节点选择方法,根据不同传感器节点的空间相关性,利用联合距离加权观测量来估计观测节点的信息效用,最后根据粒子滤波完成对目标节点的追踪。其算法复杂度较高,计算量较大。文献[11]针对传统容积卡尔曼滤波算法计算量大,求解空间维度高的缺点,将无线传感网络对移动机器人的观测量/机器人自身对环境特征的观测量以及机器人自身运动控制量进行数据融合,并利用相关门限阈阀值对数据进行处理,完成对机器人的定位。

本文内容安排如下:第1部分针对目标追踪系统模型进行描述,并阐述了目前目标追踪算法存在的问题;第2部分针对现有目标追踪算法的不足,提出改进方法;第3部分对本文提出的改进算法进行仿真分析;最后,对本文进行总结。

1 系统模型及问题描述

本文只考虑单个目标节点在二维无线传感网络中的追踪问题,假设在无线传感网中分布N个静态传感器节点和一个汇聚节点。汇聚节点控制静态传感器节点的状态,并且进行相关数据的分析与处理。

1.1 目标运动模型

目标节点在二维平面内以恒定速度(constant velocity)运动,选取目标节点的状态变量[12]如式(1)所示:

(1)

xk+1=Fxk+Bwwk

(2)

T为采样间隔,F及Bw为动态转移矩阵:

(3)

wk为动态加速度噪声,服从零均值正态分布,其协方差为:

(4)

1.2 观测模型

(5)

(xi,yi)为传感器节点i在无线传感网中的位置,(xt(k),yt(k))为目标节点k时刻的位置。则目标节点的观测模型[13]为:

(6)

1.3 问题描述

无线传感网络中目标追踪所面临的主要问题有:①传统方法中,传感器节点持续保持观测状态,造成节点能耗较大,缩短了无线传感网络生命周期;②未对传感器节点的激活数量做具体分析,造成大量节点冗余;③选择传感器节点激活之前,缺乏对其位置的考虑;④大量的观测量涌入汇聚节点,造成数据拥堵。

2 问题解决方法

本节首先利用扩展卡尔曼滤波对目标节点的状态进行预测,根据其预测状态的不稳定性构建误差椭圆,即为预测目标节点最可能出现的区域,规划候选节点;然后依据误差指示器,调整所需激活传感器节点数目,完成目标追踪。

2.1 误差椭圆

借助上述的目标运动模型和观测模型,应用扩展卡尔曼滤波[14-15]对目标的状态进行预测。如式(7)所示:

(7)

因为目标节点受到加速度噪声的影响,所以扩展卡尔曼滤波对目标节点状态的预测存在一定误差,因此确定目标节点预测状态的不确定性可以保证节点对目标节点持续进行观测。文献[16]中,Zhou以预测协方差构建3σ椭圆,对目标预测状态的不确定性进行描述。

扩展卡尔曼滤波对目标节点进行预测后,即可得到目标节点的预测位置以及预测协方差,此时可以根据预测位置以及预测协方差确定目标节点的可能区域[17]PR(probable region),目标出现在可能区域的概率如式(8)所示:

(8)

(9)

当PR所描述的区域为椭圆时,描述方程如式(10)所示[18]:

(10)

进一步展开为:

(11)

c是一个常量,与目标节点出现在椭圆内的概率Pe有关,ρ为相关系数。式即为误差椭圆(Error ellipse)[19],则目标节点出现在误差椭圆的概率如式(12)所示:

(12)

式中:Γ(·)为伽玛函数。因为p=2,所以式(12)结果如式(13)所示:

Pe=1-exp(-c2/2)

(13)

同时可得,c的表达式为:

(14)

此时的误差椭圆是一个倾斜椭圆,其长轴与短轴不能直接获取,因此需要对误差椭圆进行旋转,使其成为标准椭圆。顺时针旋转角度如式(15)所示:

(15)

因为旋转后的椭圆与未经旋转的椭圆形状相同,因此可通过旋转后的误差椭圆,求得其长轴与短轴。其长轴为:

(16)

短轴为:

(17)

由式(16)和(17)可得,误差椭圆的主半轴与c呈正相关,其大小可以根据c进行调节。c随着Pe的变化而改变误差椭圆的大小。

误差椭圆体现了扩展卡尔曼对目标节点位置预测的不确定性,目标节点会以较高的概率出现在误差椭圆内。因此误差椭圆内的传感器节点会以更高的概率观测到目标节点。综上以误差椭圆为界限,设误差椭圆内的传感器节点为候选节点,完成对节点位置的规划。每次对目标节点进行观测时,仅对候选节点进行选择性激活,而误差椭圆外的传感器节点保持休眠状态。同时在确定Pe后,误差椭圆的大小与所在位置会随着目标节点状态而改变,所圈定的候选节点也随之改变,这一过程由汇聚节点进行处理。

2.2 误差指示器

由于误差椭圆内的候选节点数目较多,激活所有候选节点进行观测会造成不必要的能量浪费,同时,受噪声干扰目标节点在不同时刻所表现出的非线性程度不同,如果目标节点本时刻运动近似线性运动时,仅需很少的观测量即可完成对目标节点状态的修正;如果目标节点本时刻运动非线性程度较高,则需要更多的传感器节点对目标节点进行观测,修正目标节点状态。因此,需要根据目标节点不同时刻所需观测量的不同,灵活的调整激活候选节点的数目能有效节省传感器节点的能量,延长无线传感网络的生命周期。

误差指示器(Error indicator)根据目标真实位置与预测位置之间误差的大小增加或减少激活节点的数目。但是位置误差往往不能直接获取,需要通过与位置误差相关的变量进行指示。常用的误差指示器[8]有协方差矩阵指示器PI(covariancematrix P Indicator),几何精度因子GDOP(Geometric Dilution Of Precision),平均测量残差MR(average Measurement Residual),预测与校正之间距离DPC(Distance between Prediction and Correction)。

本文所用误差指示器为平均测量残差MR(average Measurement Residual)。MR与位置误差的斯皮尔曼等级相关系数更大,接近强相关性,且MR容易获取。MR具体表达式如式(18)所示:

(18)

SNk为当前时刻所需激活候选节点的数目,Hi为观测矩阵。

为避免激活传感器节点数目剧增或者骤减,定义误差指示器在k时刻的决策公式如式(19)所示:

(19)

式中:DVk=|MRk-MRk-1|,Φu为上阈值,Φl为下阈值。

如果DVk仅简单设定为MRk,则有可能因测量噪声的影响使MRk一直保持较高的值,致使需要激活的传感器节点数目持续增加,造成传感器节点能量的浪费。如果DVk设定为|MRk-MRk-1|,则可以减少测量噪声对DVk的影响,需要激活的传感器节点数目增减也更加平稳。

当DVk达到预设上限值Φu时,即目标估计位置与目标真实位置之间差距过大,需要激活更多的传感器节点对目标进行观测,此时在上一时刻选择激活候选节点数目的基础上加1。当DVk达到下限值Φl时,即目标估计位置与真实位置之间误差很小,为节省传感器节点能量,在上一时刻选择激活候选节点数目的基础上减1。

当激活候选节点数目确定后,激活相应数目的候选节点,根据所激活候选节点提供的观测量即可进行扩展卡尔曼滤波的修正阶段,完成对目标节点预测状态的更新。如公式所示:

(20)

本文所提出的改进算法流程如下:

输入:x0|0P0|0SN0

输出:xk|k

1.Fork=1 tondo;

3.构建误差椭圆,规划候选节点

4.If DVk>Φuthen

5.SNk=SNk-1+1

6.Else if DVk<Φlthen

7.SNk=SNk-1-1

8.Else

9.SNk=SNk-1

10.End if

12.End for

首先根据扩展卡尔曼滤波对目标节点进行状态预测,通过式(11)与式(13)确定误差椭圆的大小;以误差椭圆为界限,挑选出候选节点;然后根据式(19)确定本时刻所需激活节点的数目,最后激活候选节点,完成卡尔曼滤波的修正过程。

3 仿真分析

3.1 追踪精度分析

本节主要分析误差指示器对追踪精度的影响。在有无误差指示器判决的情况下,分别进行仿真分析,初始激活节点数目分别设置为1,2,3,4,5,Φu=1.5,Φl=0.5,即DV上限为步长的30%,下限为步长的10%。跟踪精度设为累计均方误差:

(21)

图1为本文所提出的算法,无误差指示器判决的算法以及基于最小二乘[20]的目标追踪3种算法的累计误差对比。前两者都是基于误差椭圆的目标追踪算法。其中k=15,M=100。从图中可看出随着激活节点的增加,误差逐渐降低。但存在误差指示器判决的时候目标追踪累计均方误差基本保持不变,因为误差指示器能够及时的调节激活节点的数目,无论初始激活节点数目为多少,都可以在追踪过程中对激活节点数目进行修正,既可以满足精度的需要,又能减少激活节点数目,节省传感器能量。基于最小二乘的目标追踪算法在激活节点数目较少时,因观测量较少累计误差较大,当激活节点数目为4时,达到其算法理论最优值,与本文所提出的基于误差椭圆但无误差指示器的追踪算法精度基本一致。

图1 累计误差分析

图2是初始激活节点为1,k=15的目标追踪误差对比图。根据图2分析可得:当无误差指示器判决时,目标追踪算法累计均方误差为23.8,整个过程中的激活节点数目始终为1;当存在误差指示器判决时,目标追踪算法累计均方误差为12.9,整个过程中平均激活节点数目为1.8个。虽然存在误差判决机制的情况下平均激活节点数目较无误差判决多0.8个,但是精度提升了45%。而且可以从图1中看出,存在误差判决的情况下,累计均方误差基本维持在12.5左右;而无误差判决的情况下,累计均方误差最小为13.9。表明本文所提出改进算法的有效性。

图2 X轴、Y轴误差分析

3.2 激活节点数目分析

本节主要分析误差指示器的阈值与激活节点数目的关系。图3为在Φu为1.5,Φl,为0.5,初始节点分别为1,2,3,4,5的条件下对目标追踪进行带有误差值时判决的仿真。

从图3中可以得出,虽然初始激活候选节点数目不同,但是随着仿真的进行,激活候选节点数目变化趋于一致。平均激活节点数目分别为1.8,1.9,1.7,2.4,3.2.,后两项平均激活候选节点数目较大是因为初始激活节点数较大,且k较小,如果k足够大,平均节点激活数应接近一致。

图3 激活节点数目变化

图4与图5针对Φu与Φl进行分析,取k等于15,初始激活节点数目为1。图4中Φi固定为0.5。随着Φu的增大,误差指示器灵敏度越来越低,对DV值的变化越来越不敏感,造成激活节点数量改变的迟缓,累计误差增大。图5中Φu固定为1.5。随着Φl的减少,同样会造成误差指示器灵敏度降低。当Φl为步长的1%时,激活节点数目几乎不会减少,因为此时要求DV值小于0.05,这在观测噪声的干扰下很难实现。

图4 DV上限分析

图5 DV下限分析

因此,灵活的选取的Φu与Φl才能使误差指示器起到更好的指示作用,及时增加或减少激活节点的数目,节省节点的能量,进而延长无线传感网络的生命周期。

4 结论

本文提出一种基于误差椭圆与误差指示器判决的改进目标追踪算法。通过EKF构建误差椭圆,以误差椭圆圈定候选节点,然后根据误差指示器对激活节点数目进行调节。本文提出的改进算法仍有不足之处:没有针对候选节点对追踪贡献度进行考虑,只是随机选取节点数目;同时并没有考虑到在稀疏无线传感网络中,误差椭圆内不存在候选节点的情况。今后将针对上述几个缺陷进行改进。

[1] Yick J,Mukherjee B,Ghosal D. Wireless Sensor Network Survey[J]. Computer Networks the International Journal of Computer and Telecommunications Networking,2008,52(12):2292-2330.

[2] Han G,Xu H,Duong T Q,et al. Localization Algorithms of Wireless Sensor Networks:A Survey[J]. Telecommunication Systems,2013,52(4):1-18.

[3] Patwari N,Ash J N,Kyperountas S,et al. Locating the Nodes[J]. IEEE Signal Processing Magazine,2005,22(4):54-69.

[4] Mirsadeghi M. Mahani a Low Power Prediction Mechanism for WSN-Based Object Tracking[J]. Procedia Technology,2014,17:692-698.

[5] Wang X,Fu M,Zhang H. Target Tracking in Wireless Sensor Networks Based on the Combination of KF and MLE Using Distance Measurements[J]. IEEE Transactions on Mobile Computing,2012,11(4):567-576.

[6] Li J,Zhao R,Chen J,et al. Target Tracking Algorithm Based on Adaptive Strong Tracking Particle Filter[J]. IET Science Measurement and Technology,2016,10(7):704-710.

[7] Cheng P,Cao X,Bai J,et al. On Optimizing Sensing Quality with Guaranteed Coverage in Autonomous Mobile Sensor Networks[J]. Computer Communications,2012,35(9):1107-1114.

[8] Robles J J,Cardenas-Mansilla G,Lehnert R. Adaptive Selection of Anchors in the Extended Kalman Filter Tracking Algorithm[C]//2014 Positioning,Navigation and Communication(WPNC). IEEE Press,2014:1-7.

[9] Xu N,Zhang Y,Zhang D,et al. Moving Target Tracking in Three Dimensional Space with Wireless Sensor Network[J]. Wireless Personal Communications,2016(2016):1-11.

[10] Feng J,Zhao H,Lian B. Efficient and Adaptive Node Selection for Target Tracking in Wireless Sensor Network[J]. Journal of Sensors,2016(2016):1-9.

[11] 陈晓飞,凌有铸,陈孟元. WSNs环境下基于高斯混合容积卡尔曼滤波的移动机器人定位算法[J]. 传感技术学报,2017,30(1):133-138.

[12] Li X R,Jilkov V P. Survey of Maneuvering Target Tracking. Part I. Dynamic Models[J]. IEEE Transactions on Aerospace and Electronic Systems,2003,39(4):1333-1364.

[13] Li X R,Jilkov V P. A Survey of Maneuvering Target Tracking-Part Ⅲ:Measurement Models[J]. Proceedings of SPIE—The International Society for Optical Engineering,2001,4473(4):423-446.

[14] Faragher R. Understanding the Basis of the Kalman Filter Via a Simple and Intuitive Derivation[Lecture Notes][J]. IEEE Signal Processing Magazine,2012,29(5):128-132.

[15] Welch G,Bishop G. An Introduction to the Kalmanfilter[J]. University of North Carolina at Chapel Hill,2006,8(7):127-132.

[16] Zhou K,Roumeliotis S I. Optimal Motion Strategies for Range-Only Constrained Multisensor Target Tracking[J]. IEEE Transactions on Robotics,2008,24(5):1168-1185.

[17] Chan Y T,Chan F,Read W,et al. Probable Regions for Emitter Localization[C]//IEEE Military Communications Conference,Milcom. IEEE,2015:222-227.

[18] Qi Y,Cheng P,Bai J,et al. Energy-Efficient Target Tracking by Mobile Sensors with Limited Sensing Range[J]. IEEE Transactions on Industrial Electronics,2016,63(11):6949-6961.

[19] Paradowski L R. Uncertainty Ellipses and their Application to Interval Estimation of Emitter Position[J]. IEEE Transactions on Aerospace and Electronic Systems,1997,33(1):126-133.

[20] Mauro C,Pierfrancesco L,Matteo S. A Weighted Least Squares Approach for Multi-Target Doppler-Only Localization[C]//2013 IEEE Radar Conference(RADAR). IEEE Press,2013:1-6.

TargetTrackinginWirelessSensorNetworkBasedonErrorEllipseandAdaptiveSelectionofNodes*

ZHOUFei*,ANKangning,FANXinyue,GAOJianjun

(Chongqing Key Laboratory of Optical Communication and Networks,Chongqing University of Posts and Telecommunications,Chongqing 40065,China)

In the Wireless Sensor Network,tracking accuracy and energy consumption of nodes are two main performance indicators.Although many target tracking algorithms improved the tracking accuracy and reduced the energy consumption of the sensor nodes,few of them considered the distribution number and position of sensor nodes.Therefore,a target tracking algorithm based on error ellipse and adaptive selection of nodes is proposed. Firstly,proposed algorithm calculates the most possible region for target based on error ellipse. Then determines the number of sensor nodes by using the error indicator.Finally,activating the sensor nodes to complete the target tracking. The simulations demonstrate that proposed algorithm can effectively reduce the number of activated sensor nodes in the premise high tracking accuracy.

wireless sensor network;target tracking;error ellipse;error indicator;extended Kalman filter

TP393

A

1004-1699(2017)10-1548-06

10.3969/j.issn.1004-1699.2017.10.016

周非(1977-),男,湖北浠水人,博士,重庆邮电大学教授,主要研究方向为无线定位,信号处理,信息安全,图像处理,zhoufei@cqupt.edu.cn;

安康宁(1992-),男,河北石家庄人,重庆邮电大学硕士研究生,主要研究方向为无线传感网络,ankangning@163.com;

范馨月(1979-),女,四川犍为人,硕士,重庆邮电大学副教授,主要研究方向为认知无线电,信号处理,图像处理;

高建军(1990-),男,山西朔州人,重庆邮电大学硕士研究生,主要研究方向为无线传感网络。