基于UKF区域交叉定位的WSNs Sink节点动态跟踪算法*

姚依翔， 谢俊元

(1.南京大学 计算机科学与技术系, 江苏 南京 210093; 2.计算机软件新技术国家重点实验室,江苏 南京 210093; 3.南京晓庄学院 数学与信息技术学院,江苏 南京211100)

基于UKF区域交叉定位的WSNs Sink节点动态跟踪算法*

姚依翔1,3， 谢俊元1,2

(1.南京大学 计算机科学与技术系, 江苏 南京 210093; 2.计算机软件新技术国家重点实验室,江苏 南京 210093; 3.南京晓庄学院 数学与信息技术学院,江苏 南京211100)

为了提高无线传感器网络(WSNs)使用寿命，对WSNs的目标跟踪方式进行研究，提出基于无迹Kalman滤波(UKF)的WSNs Sink节点动态跟踪算法,以实现高效节能的资源管理和利用方式。首先利用UKF算法对目标节点的下一位置进行预测，然后通过四圆区域定位交叉定位算法对Sink节点的位置区域进行局部准确定位。实验结果表明:这种动态的Sink节点预测定位算法能够有效缩短数据发射传感器和Sink点之间的距离,减少跳数，从而实现负载均衡降低能耗的效果。

无线传感器网络； 无迹卡尔曼滤波； 区域交叉定位； Sink节点； 动态跟踪

0 引 言

目前国内外学者在无线传感器网络(WSNs)的算法层面、网络层面和物理层面做了大量研究[1～3]。对于动态Sink节点WSNs和Sink节点的跟踪算法的研究有很多文献提出可行方案。文献[4]为防止过多的节点被激活从而浪费能量资源，提出一种基于边界检测的Sink节点跟踪算法，但是当对象的速度和方向突然发生变化时会影响边界检测的准确性；文献[5]提出传感器对周围环境进行监测并定期向服务器传送数据，由服务器采用三角测量的方法完成对目标位置的定位，但是这种方法过分依赖于目标发出信号的强度，当噪声或者障碍物存在时会造成信号的衰减，进而造成目标定位的失准；文献[6]提出了一种基于二叉树结构目标跟踪方法，树中的每个节点对应于WSNs中移动的传感器目标，并在运动过程中可以动态地更新节点，根据收集到的传感器信息可以获得关于目标完整和准确的信息，但是当目标运动过快时效果不佳，同时树节点频繁地更新操作反而会增加传感器的能量消耗。

针对上述算法的性能有待提高的问题，本文提出一种基于无迹卡尔曼滤波和区域交叉定位的动态传感器网络Sink节点跟踪算法(dynamic sensor network sink node tracking algorithm based on UKF and regional cross localition，URDST)，该算法对于目标的运动不做限制，并且通过对移动节点的预测定位方式可以更好地管理传感器的能量使用状态，利用UKF算法预测目标可能出现的区域，对该区域内的传感器节点进行激活，然后利用四圆定位算法对目标进行定位，通过这种方式平衡了网络中的能量,从而降低了能源消耗量。

1 动态Sink节点的UKF预测算法

1.1 Sink节点最优位置

假设该算法在实际应用中是不依赖于网络的状态和目标的运动形态，Sink节点是无能量约束可以以有限的速度在区域中移动，并且在Sink层面节点的位置是已知的，相关文献已经证明这种假设不会增加任何特定的限制条件。文献[7]给出了一种用来计算Sink节点最优位置的目标函数，该目标函数已成功应用于静态的Sink节点选取，但当Sink节点移动过快时，由于计算数据信息在大范围区域中是通过随机方式产生的，从而随机的冗余的数据信息会导致Sink节点的移动定位存在延迟，出现定位不准确和较高的丢包率等问题。针对上述问题本文引入一个能量中心计算公式，通过快速移动目标周围传感器剩余能量状况对下一时刻Sink节点的最优位置区域进行提前预测

(1)

式中 Xj(t)和Yj(t)为计算出的新的Sink节点的位置坐标，i为预测区域PRj(t)中所有的活跃节点的标识符，xi(t)和yi(t)为活跃节点为的坐标，Eneri(t)为活跃节点i的剩余能量。上式可以看出新Sink节点的位置重心与活跃节点区域的剩余能量呈反比关系，即新Sink节点将逐渐靠近低剩余能量区域附近。

1.2UKF预测算法

对于非线性的滤波问题，常用的方法有EKF和UKF方法，这种处理方式在对高阶项处理时采取忽略或近似的方式，会导致误差的增加，造成预测值与真实值偏离较多[8]。为此，相关学者提出了几种解决方案，UKF算法便是其中一种，UKF采取UT变换方式确定算法的样本点，并且未对传递系统采取近似简化，可以较高精度地保持传递后的状态量分布，由于无须求解雅可比矩阵可以处理不可导非线性问题。对于离散非线性系统，其状态和量测方程为

(2)

式中k为时间指标，xk状态向量，zk为量测向量，wk,vk为独立的白噪声。UT变换需要通过统计x的特性设计2n+1个σ点，设为ζi(i=0,1,…,2n)，σ点计算公式为

(3)

(4)

量测预测公式为

(5)

状态的更新公式为

(6)

2 目标预测定位算法

2.1 预测周期

在UKF目标预测算法中，目标的移动速度是影响探测效率的关键因素，如果一个低速的目标进入探测区域，就可以使用该目标的前一个位置来预测他将来的位置。通过这两个位置，可以定义一个半径为R的圆形预测区域PR，该预测区域PR内的所有节点都是处于激活状态。此时将Sink节点移向预测区域PR可以有效地降低活跃传感器的传输能量，如果Sink节点前一时刻的位置就处于PR区域内，为了减少不必要的操作，采用下列判别式对Sink节点的移动进行限制

(L(sinkcurr,pospred)>2Range)∧

(min(Eng(i)/i∈Sd)<Δ),

(7)

式中Sd为所有参与传输探测传感器数据的节点；S1为预测区域PR内所有传感器节点的集合；Range为传感器节点的探测范围；Eng(i)为节点i的剩余能量；Δ为能量阈值。

如果目标的速度大幅增加，将导致传感器不能有效地进行跟踪，Sink节点没有足够的时间移动到最佳位置。所以，这里提出一种解决方案，根据公式(1)来激活探测区域，并将Sink节点提前移动到该区域，需要注意的是这种Sink节点的迁移是根据目标的速度而周期进行的。

2.2 定位算法

Sink点可以准确知道每个传感器的具体位置，通过激活区域的传感器探测到的目标相关信息，采用相关算法可以得到目标的具体位置。当探测区域内的传感器密度很大时，每个目标附近的传感器都能够探测到目标的相关信息，如果不加区分的使用这些传感器传送的目标信息进行计算无疑会增加算法的计算复杂度，为了有效地解决这个问题，首先假设每个传感器探测范围的半径是相等的，那么，在计算目标所在区域时没有必要使用所有的传感器信息而是采用本文的方法，采用四圆定位的方法可以有效地确定出目标可能出现的区域,如图1。

假Z是包含有目标的最小区域；D是所有探测到目标的节点集合；ci,cj和ck分别是以Ni,Nj和Nk为圆心的半径相同的圆，那么，目标的定位算法如下：

1)∀Ni,Nj∈D，T1，T2为圆形区域ci和cj边界的交点满足，{T1,T2{=(ci)∩(cj)，由T1,T2计算穿过这两点的直线d1。

2)在所有的节点Nk∈D-{Ni,Nj}中，寻找所有经过直线d1上[T1,T2]区域内的圆形检测区域ck。

3)如果只有一个节点的圆形探测区域经过直线d1上[T1,T2]区域，那么，Z=(cs)∩((ci)∩(cj))，算法结束；如果有两个节点的圆形区域cl,cm穿过直线d1上[T1,T2]区域，则计算这两个圆形区域边界的交点：{R1,R2}=(ci)∩(cm)，并计算经过{R1,R2}两点的直线d2。

4)在所有的节点Nk∈D-{Ni,Nj,Nl,Nm}中，寻找所有经过直线d2上[R1,R2]区域内的圆形检测区域。

5)如果有两个不同的圆形区域经过直线d2上[R1,R2]区域,则计算区域Z1=((ci)∩(cm)∩Z，算法结束；如果只有一个圆cr经过上述区域，则Z=cr∩((ci)∩(cj)),算法结束。

该算法主要目的是计算出包含有目标的最小的区域，首先任意选取两个探测到目标信息的节点来计算出两个圆形探测区域边界的交线。然后通过迭代的方法寻找到与交线上与[T1,T2]相交的圆形探测区域。经过上述两步，可以寻找到满足条件的节点，并且可以计算出经过{R1,R2}两点的直线d2。然后采用同样的方法计算出经过直线d2上区域[R1,R2]的圆形探测区域。最后可以得到目标所在的区域是ci,cj，ck的交叉区域，如图1所示。“+”代表的是目标位置。

图1 探测定位算法

3 实验与结果分析

图2、图3给出的是URDST，QVF-R和QPF三种算法在目标跟踪精度和均方误差上的对比结果。从图2(a)可以看出:URDST与QVF-R算法在目标跟踪效果上相差不大，都取得了很好的效果，但是总体上URDST算法在与原有轨迹的重合度上要好于QVF-R算法，尤其是当目标轨迹突然发生变化时，URDST算法仍然能够很好地对目标进行有效跟踪。图2(b)比较了URDST与QVF-R算法在跟踪轨迹和原始轨迹之间的均方差，可以直观的看出：URDST算法具有更小并且稳定的均方差值曲线，这说明URDST算法在跟踪性能上更加稳定和精确。

图3给出的是URDST和QPF的跟踪轨迹曲线和均方差曲线，图3(a)的轨迹曲线可以看出:QPF算法的跟踪效果很差，甚至比QVF-R还要差，轨迹偏离原始轨迹较多，图3(b)的均方差曲线则更准确更直观地给出了两种算法的精度差别，QPF均方差曲线更大并且更不稳定，这说明URDST的目标跟踪效果要明显优于QPF的目标跟踪曲线。

图2 URDST与QVF-R跟踪精度对比

图3 URDST与QPF跟踪精度对比

为了对比试验三种算法在能量消耗上的不同表现，本文采用文献[8]提出的能量消耗评价模型，假设：1)活跃传感器之间的数据通信时通过单跳实现的；2)同数据通信所消耗的能量相比，能量的分配和计算过程所消耗的能量可以忽略不计。数据通信所消耗的能量主要包括三部分：数据发射耗能、数据无线传播耗能和数据接收耗能。

URDST,QVF-R和QPF三种算法在不同采样时刻的能量消耗值对比曲线如图4所示。

图4 三种算法能耗对比曲线

从图4(a)URDST和QVF-R能耗对比曲线图中可以看出虽然在个别时刻QVF-R能耗要优于URDST算法，但是总体上看URDST算法能耗明显要优于QVF-R算法的能耗。从图4(b)URDST和QPF能耗对比曲线可以看出虽然在个别时刻QPF算法能耗和URDST算法能耗比较接近，但是其余时刻QPF算法能耗要明显差于URDST算法能耗。从中可以得到以下结论：URDST相对于对比算法能够更有效地节约能量消耗提高跟踪精度，算法的整体性能要明显优于QVF-R算法和QPF算法，这个结果直接证实了URDST算法在实验室条件下的有效性与可行性。

4 结束语

本文提出了一种新的传感器网络目标跟踪定位算法，主要的算法思想是通过目标的跟踪和Sink节点的重新定位来降低网络的平均传输能耗，从而有效延长WSNs的生存周期。算法包含预测和跟踪两个步骤,分别采用UKF一步预测算法和四圆定位算法实现了目标的准确跟踪和定位。通过与已有的两种跟踪定位算法对比实验表明：该算法的跟踪精度和能耗节约均优于对比算法，验证了该算法的有效性。

[1] Read J,Achutegui K.A distributed particle filter for nonlinear tracking in wireless sensor networks[J].Signal Processing,2014,98(5):121-134.

[2] Sivaranjani S,Radhakrishnan S,Thangaraj C.Adaptive delay and energy aware data aggregation technique in wireless sensor networks[J].Mobile Communication and Power Engineering,2013,296(5):41-49.

[3] Jacob J M,John A.Improving lifetime of structured deployed wireless sensor networks using sleepy algorithm[J].Eco-friendly Computing and Communication Systems,2012,305(3):47-53.

[4] Li Q L,Zhao Z J,Xu X F,et al.A flexible boundary sensing mo-del for group target tracking in wireless sensor networks[J].Green Communications and Networking,2012,51(5):25-36.

[5] Zoghi M R,Kahaei M H.Sensor management under tracking accuracy and energy constraints in wireless sensor networks[J].Ara-bian Journal for Science and Engineering,2012,37(3):721-734.

[6] Mansouri M,Ilham O,Snoussi H.Adaptive quantized target tra-cking in wireless sensor networks[J].Wireless Networks,2011,17(7):1625-1639.

[7] 吴三斌，柳 强，李成博.基于能量均衡的无线传感器网络路由算法[J].计算机应用研究,2012,29(4):1465-1469.

[8] 莫尚丰，陈丁洁，陈 红.无线传感器网络中Top-K连接查询处理[J].计算机学报,2013,36(3):557-570.

[9] Akkaya K,Younis M.Sink repositioning for enhanced perfor-mance in wireless sensor networks[J].Computer Networks,2005,49(4):512-534.

[10] Redondi A,Chirico M,Borsani L.An integrated system based on wireless sensor networks for patient monitoring, localization and tracking[J].Ad Hoc Networks,2013,11(1):39-53.

[11] Xu E Y,Ding Z,Dasgupta S.Target tracking and mobile sensor navigation in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2013,12(1):177-186.

[12] 万国峰，钟 俊.基于三角形理论的无线传感器网络定位算法[J].计算机应用研究,2013,30(1):249-251.

Dynamic tracking algorithm for WSNs sink node based on

UKF and regional cross localization*YAO Yi-xiang1,3, XIE Jun-yuan1,2

(1.Department of Computer Science and Technology,Nanjing University,Nanjing 210093, China; 2.National Key Laboratory for Novel Technology,Nanjing 210093,China; 3.School of Mathematics and Information Technology,Nanjing Xiaozhuang University,Nanjing 211100,China)

In order to improve wireless sensor networks(WSNs) lifetime,research on target tracking method in WSNs,and propose an unscented Kalman filtering(UKF)-based WSNs sink node dynamic tracking algorithm,in order to realize high efficient and energy-saving resource management and utilization mode.Firstly,use UKF algorithm to predict next position of target node,and then through the four circle regional positioning algorithm of cross locationing,so as to locally and accurately locate location area of sink node.The experimental results show that the dynamic prediction localization algorithm for sink node can effectively shorten distance between data transmission sensor and sink node,and reduce hop count, so as to achieve load balancing and energy consumption reducing effect.

WSNs; unscented Kalman filtering(UKF); regional cross localization; sink node; dynamic tracking

2014—08—15

国家自然科学基金资助项目(60721002, 60875038); 教育部重点研究计划资助项目(108151)

10.13873/J.1000—9787(2015)04—0123—04

TP 18

A

1000—9787(2015)04—0123—04

姚依翔(1979-),男,江苏泰兴人,博士研究生,高级工程师,主要研究领域为逆向工程、组织网络和人工智能。