WSN中基于自适应预测聚类的多组群目标的跟踪方法

2016-11-30刘述木杨建黎远松

电信科学 2016年7期

关键词：组群参考文献聚类

刘述木，杨建，黎远松

（1.四川工程职业技术学院，四川德阳 618000；2.四川理工学院，四川自贡 643000）

WSN中基于自适应预测聚类的多组群目标的跟踪方法

刘述木1，杨建1，黎远松2

（1.四川工程职业技术学院，四川德阳 618000；2.四川理工学院，四川自贡 643000）

针对多传感器目标跟踪中的能源使用和跟踪精度之间的不平衡问题，提出了一种权衡网络寿命和精度的方法，即基于自适应预测聚类的多组群目标跟踪方法（APCMT），实现了同时跟踪多个组群。首先进行聚类，即捕捉组群行为属性的改变，例如形成、合并以及分裂；然后选择传感器，激活对组群区域有贡献的传感器，并进行组群跟踪。仿真场景在1 000 m×1 000 m的正方形区域内，随机部署500个传感器，与Kalman、效能节点选择（EENS）方法以及改进的动态簇（IDC）方法相比，提出的方法在跟踪精度方面更高。由于需要激活的传感器更少、计算时间更短，网络寿命得到了明显的提升。

无线传感器网络；目标跟踪；多传感器；预测聚类；多组群；跟踪精度

1 引言

无线传感器网络（wireless sensor network，WSN）[1]是许多应用程序重要的先决条件，例如航海、环境监测以及野生动物跟踪等。这些系统必须具有高灵活性、高容错率、高传感精度以及低成本等特点[2]。本文主要研究WSN的组群目标跟踪，在该应用中，不同组群的目标会一起移动，传感器用以估计组群的位置等信息，这在安防领域具有重要的应用价值。

已有许多研究者对该领域进行了研究。为了跟踪和覆盖所有相似目标的区域，参考文献[3]提出了一种使用二进制传感器网络的区域组群目标跟踪方法。检测组群区域是为了确定传感器节点的子集，当目标出现在感知距离内时，基于二进制的传感模型输出为“1”。但在选择过程中重叠区域缺乏识别信息，同时过度使用传感器资源也会降低网络寿命[4]。

另一种常用的方法是基于进化图的多组群同时跟踪，进化图通过创造一幅连通分支图来使组群的行为属性模型化[5]。图中的每个节点对应一个目标位置。当位置和速度在一些距离判据内下降时，目标会存在于边界位置。进化图模型促进了新节点的整合、不存在节点的移除以及边缘的更新。但是，在没有处理精确度—寿命的权衡时，考虑主动式传感器的数量。因此，估计过程中传感器收集的测量值没有得到利用，浪费了传感器的能量。

还有一种基于区域的跟踪方法，以R树结构[6]为基础组织传感器，使之成为分层拓扑结构，如参考文献[7]从检测分组的所有传感器中确定组群中的边界传感器，并且构建一个相应的顶点链来描述该区域。参考文献[8]通过分—合算法以获得组群区域的整体估计，组群的边界划分为封闭的小凸包，中心节点将会融合小凸包成为可以代表组群轮廓的大凸包，提出了能效节点选择（energy-effective node selection，EENS）方法。

现有的目标跟踪中传感器选择的研究主要集中在跟踪个体的轨迹。然而，在拥挤的组群中对每个个体指标执行传感器选择的代价非常大[9]。因此，组群目标跟踪的主要问题是组群传感器的选择。为此，本文提出了一种基于自适应预测聚类组群跟踪（multi-group tracking of adaptive predictive clustering，APCMT）的方法，满足组群目标跟踪的诸多特点，其主要贡献总结如下：

·本文方法通过估算组群区域可以同时跟踪多组群，每个区域代表一个覆盖了所有预测的分组目标的凸包，使用了传感器能量参数，并选择有贡献的传感器区域覆盖需求；

·APCMT整合了移动目标的PCMT结构[10]，从而可以实现捕捉组群的行为属性，改变了传递个体行为属性数据的方式，大大减少了通信代价和额外的处理操作。

2 模型与假设

2.1 网络模型

本文的网络模型是n个传感器S={s1,s2,…,sn}在一个矩形区域内的任意展开。每个传感器都拥有给定的感知半径Rs。本文采用了定能量的自适应聚类层次结构[11]算法作为路由算法和聚类算法来交换传感器内的数据，或将测量数据从传感器传递到远程基站（base station，BS）。Leach是一种分层次的基于聚类的路由算法，旨在统一分配网络中传感器节点消耗的能量，从而延长网络寿命，即通过周期性循环符合条件节点中的簇头来实现，簇头收集聚群中的局部传感测量并执行局部数据算法来降低整体通信的开销。

2.2 能量模型

本文假设节点初始化能量E相同，且每个传感器si都知道自己当前的剩余能量et(si)。传感器通过测量目标发射出的能量信号检测出目标，如磁场的角度方向。传感器中的能量消耗通过感知单元、处理单元和通信单元表征。参考文献[12]表明一个传感器节点的感知单元能耗最低，可以忽略不计。此外，处理单元消耗的能量与通信单元消耗的能量相比，也相对较低。因此，本文假设只有每个节点的通信单元可以在活跃模式和休眠模式间切换。因此，每个传感器可以感知环境。本文用Leach算法的能量耗散模型来计算一个节点在每个时间单元用于覆盖目标所使用的能量。Eelec表示无线电路所需能量，而Emp和Efs分别代表多路径模式和自由空间模式的放大器能量。一个传感器si在每个时间单元的能量消耗Ct(si)为：

其中，Erx(l)=lEelec是接收l bit信号消耗的能量，且Etx(l,d)=是将一个l bit数据信号发射到距离为d的另一个节点所用的能量。最后，收集到的跟踪数据等于l bit，并且与覆盖的组群数量成比例。

2.3 组群的结构

通过了解组群的结构Gt={G1,G2,…,GnG}来使目标组群模型化，其中，nG表示真实组群的数量。每个组群Gta在时刻t∈T包含了任意数量的目标Gta={set of target rj}⊆R，其中，R={r1,r2,…,rm}表示所有个体的集合。考虑跟踪轨道和测量模型，本文假设t时刻目标rj的实际状态是：

其中，xrj,t和yrj,t表示位置，和是 x、y轴上的速度，目标的轨迹模型采用离散化[7]进行数学建模。

其中，矩阵A是跃迁矩阵，q是方差为Q的零均值高斯噪声。此外，传感器通过测量目标发射的能量信号Zrj,t来检测目标。测量模型作为传感器平台到目标的方位角，即一个非线性模型。在t时刻，从目标rj到位于(x(si),y(si))的传感器si的方位角为：

其中，测量误差w～N(0,Δθ)服从高斯白噪声模型，其中，所有节点误差的标准偏差Δθ都是各向同性的。一个组群中心的初始位置在区域中是随机分布的，且组群的初始位置服从高斯分布。且一个组群的所有成员同时开始、分裂及合并等，在组群轨道中的任意时刻都可能随机发生。

3 自适应预测聚类法

自适应预测聚类法是执行群目标跟踪的步骤组合。为此，首先估计并形成组群，然后选择组群，跟踪各自的传感器。图1为自适应预测聚类法的流程。

图1 自适应预测聚类法的流程

3.1 自适应—PCMT

本文将参考文献 [10]提出的PCMT扩展成一种自适应—PCMT，延伸了取样时间的设定，其中，取样时间是指引发聚类结构的时间。为了精确估计组群，自适应—PCMT的设计专门用于组群目标跟踪的应用程序。

设计PCMT结构[10]通过加权关系图发现目标组群及其组成成员。当目标穿过网络时，通过目标的距离和运动方向估计可能的关系，目标运动方向可以用于发现重叠组群。PCMT包括3个相关部分：数据收集、定位和聚类（如图2所示）。在PCMT的数据收集阶段，传感器节点收集检测到的目标测量值，并将其传送给BS；然后，基站利用定位算法来估计位置；最后，利用类成分法定位结果寻找各目标组群。

图 2 自适应—PCMT结构

自适应—PCMT结构包括一个PCMT的附加块，是图2中的凸包区域的预测估计。如果可以估计包含所有组群成员的区域，则可以跟踪该目标组群，考虑到组群结构作为一个进化图，基站基于快速凸包算法为每个组群创造了一个凸包[8]。大部分情况下，快速凸包算法的复杂度为O(n lg n)。

为一个组群创建的凸包是覆盖所有组群目标的最小区域（minimum region，MR）。图3给出了一个组群的例子，其中，组群的MR表示为实线多边形。其中，黑三角代表在当下未获得任何测量结果时个体目标的预测位置。贝叶斯结构中的度量模型为，与噪声离散Δθ有关，那么由于目标定位中的误差，MR可能并不是对区域的准确估计。因此，由于定位误差的存在，一个合理的做法是确定一个较大区域以包含定位误差。本文将该较大区域定义为完整区域（full region，FR），如图3所示，将MR的边界向外扩张2Rs的距离，虚线包含的区域即FR。选择2Rs的理由是假设感应区域内的每个部分都有至少有一个传感器节点覆盖。对于1个节点集合覆盖的凸包区域，如果扩展距离RC≥2Rs，通信的连通性就有了保证，根据参考文献[13]中的接收估计误差模型，目标的位置离传感器的距离在Rs范围内时，状态估计中的误差最高，即接收的信号最弱。

图3 关于MR和FR凸包的预测估计示例

3.2 基于区域的传感器选择

本节提出了多组群的传感器选择算法，遵循第2.1节和2.2节的网络和能量模型。由于组群的个体选择传感器的代价非常昂贵，因此选择覆盖FR的传感器是一种合理有效的方法。本文提出的选择方法是一种分散式方法。每个预计的FR都有一个簇头节点和许多跟踪节点，簇头节点就是一个计算和通信中心并且负责选择并激活跟踪节点，跟踪节点收集测量数据并将跟踪信息发送给各自的头节点。

头节点的最优选择是使跟踪节点和头节点间的平均距离最小化的节点。因为节省了给头节点传输信息时跟踪节点的能量，该能量与距离成正比。此外，头节点应当利用较高剩余能量来执行计算和通信任务。鉴于传感器的可用集合表示要覆盖预计的，每个节点的能量感知成本为：

其中，et(si)表示传感器si的剩余能量，d(si,sj)表示可用集合两个传感器之间的欧氏距离，表示传感器的可用集合的基数。

由于每个传感器的感知距离都会与一个或多个相邻传感器的感知距离重叠，因此点p(xy)可能被一个或多个传感器覆盖。为了在保证更长的网络寿命和FR的整个覆盖区域的条件下减少主动式传感器的数量，本文引进了覆盖范围感知成本度量来测量一个传感器在覆盖点p(xy)上的重要性。覆盖范围感知成本度量合并了覆盖冗余Ctot(p(xy))，该覆盖冗余可以从所有重叠传感器中获得。

式（7）测量了覆盖点p(x,y)的传感器数量，其中，传感器必须满足节点（可用集合覆盖的）或者满足可用集合传感器si与覆盖点p(x,y)间的欧式距离小于或等于Rs，式（6）中的范围感知成本度量在考虑节点的剩余能量的情况下用最少的覆盖冗余测量传感器si，et(si)表示传感器 si的剩余能量。

3.3 基于区域的移动组群跟踪

考虑第 2.3节的组群结构 Gt，组群∈Gt在t时刻的所有目标成员的节点位置向量规定为即 ng是组群在 t时刻的大小。在贝叶斯框架下，通过估计先验和后验分布实现对移动组群的循环跟踪，该分布通过如下的预测和更新步骤实现。

预测：

更新：

3.4 凸包区域的预测映射

输入组群结构以及凸包区域

对于每个组群

————在跟踪节点——————

在t-1时刻处收集的测量数据；

做出关于目标进化的局部决定；

将局部决定发送给头节点。

————在头节点—————————

先验分布

如果决定=1

将决定发送给基站来执行自适应—PCMT和凸包区域的预测估计（第3.1节）

否则

对t时刻的预测组群状态映射t-1时刻处的组群区域MR（第 3.4节）。

结束

————在头节点/基站—————————

执行预测区域FR的传感器选择（第3.2节）

结束

输出 FR、估计组群结构、传感器的激活设置

4 仿真实验与性能评估

本节将提出的APCMT方法与参考文献 [4]提出的Kalman滤波方法、参考文献 [8]提出的效能节点选择（EENS）方法以及参考文献[9]提出的改进的动态簇（IDC）方法进行比较。参考文献[4]充分利用了Kalman滤波预测功能的节点自适应调整策略，并引入了事件辅助机制，参考文献[8]通过分—合算法以获得对组群区域的整体估计，参考文献[9]改进了动态簇组建过程的簇头选取和簇成员征集过程。

4.1 仿真设置

仿真场景在1 000 m×1 000 m的方形区域内，随机部署500个传感器，传感器的传输范围设置为Rs=250，每个节点在部署时的初始能量为E=10 J，对10个组群进行了两次仿真，每个组群包括由合成发生器产生的随机数量的目标。根据参考文献 [14]，本文设置的Rao-Blackwellized仿真参数和能量参数见表1。此外，选择阈值 λ使得位于FR(α(rj)=1)之外且距离传感器(d(si,rj))=Rs最远目标的目标进化概率为0.4。由于目标和节点之间的距离较长，节点接收到的信号很弱，给出的结果是100次仿真结果的平均值。

表1 估算参数和能量参数及其设置值

4.2 性能指标

实验仿真的网络寿命为T，定义为从传感器网络发射到第一个节点死亡之间的周期[15]。APCMT方法在跟踪移动组群中的性能方面是以网络寿命的影响因子、跟踪误差以及处理时间指标进行评估。网络寿命的影响因子包括主动式传感器的平均数量和在网络寿命T处的能耗率。本文定义跟踪误差RMSEGa为组群Ga预测中心位置和实际中心位置间的预期距离。

将总跟踪误差RMSEtot定义为组群的总误差，即：

4.3 仿真结果

4.3.1 APCMT方法的能量分析

首先对 APCMT、Kalman[4]、EENS[8]和 IDC[9]4 种方法影响网络寿命的因子进行比较。这些因子包括自助式传感器的平均数量、能耗率以及单一完整的数据周期的处理时间。这里给出的结果是平均网络寿命超过T。

图4给出了不同组群密度情况下主动式传感器的平均数量。可以看出区域覆盖传感器选择方法激活的传感器数比其他方法少。由于式（5）中传感器的选择是为了在最小的覆盖冗余下对预测组群提供全面覆盖，APCMT使用了数量最少的主动式传感器，然而IDC[9]并不考虑覆盖冗余而且覆盖一个区域的可用传感器都是激活传感器。此外，其他方法对每个个体目标执行选择算法。IDC[9]的头节点选择单一，即每个目标都只用一个有着最大信息效用的激活传感器，参考文献[9]中两个传感器的设定可以更好地平衡精确度—寿命。最后，EENS[8]选择了不同程度的传感器，在大多数情况下大约有两个传感器处于激活状态。

图4 网络寿命内主动式传感器的平均数量

此外，由于组群中目标移动地非常接近，因此很难分别定位个体目标。因此，Kalman[4]、EENS[8]和 IDC[9]不能预计组群中目标的精确数量，并且激活了更多传感器。图5给出了APCMT和其他方法的能耗率。APCMT通过激活更少数量的传感器，分别比IDC和Kalman的能量消耗少了62%和55%，这与各方法选择的传感器数量有关。

图5 网络寿命内的能耗率

对密集组群的节能跟踪决定了需要将计算和处理时间最小化。图6为所有方法处理时间的比较，结果显示，APCMT的计算时间在所有情况下平缓地增长。然而，其他方法的计算时间会随着组群数量的增加而增长明显。例如，在拥挤的场景中，如10个组群，APCMT比其他方法运行快4～6倍。这是由于选择的是区域的传感器而不是个体目标的传感器，因此计算时间得到明显改善。此外，APCMT采用了定位算法来评估组群中心。EENS[8]的处理时间最佳，这是因为其并不适用任何贝叶斯结构来计算分布，在收集传感器测量值后，仅通过发现覆盖目标的凸包区域对一个组群进行估计。

图6 网络寿命内处理时间的对比

4.3.2 跟踪误差（估计精度）

本节比较上述4种方法的估计精度，通过对分组目标的个体估计误差取平均值进行评估。

图7显示了所有方法的总跟踪误差RMSEtot，发现APCMT比其他方法能达到更好的精确度。另一方面，在拥挤场景下，对个体目标使用 Kalman[4]、EENS[8]或者 IDC[9]方法的性能较差的原因是分组目标移动得十分靠近，因此，在对不确定性进行模式化时个体状态估计便不准确。总体来说，APCMT显示出了较好的顽健性，且可以很好地对组群状态的不确定性进行模式化。

图7 不同数量组群间总误差的对比（RMSEtot）

5 结束语

本文提出了一种自适应—PCMT结构的多传感器组群跟踪方法来执行聚类和发现目标组群，选择那些有助于增加网络寿命且对组群的预计区域提供整体覆盖的传感器。具有上述特征的多传感器组群跟踪方法在预计精确度上比其他方法提高了50%～80%。此外，该方法显示出优越的计算时间，且由于需要激活更少的传感器，所以在网络寿命上有重要改善。

未来的工作将集中在通过重新定位来补偿由节点故障导致的覆盖空洞，这需要适当地移动节点选择和运动策略，如传感器—目标分配以及传感器移动方向。此外，还需要考虑环境中的障碍物等。

[1]张希伟,戴海鹏,徐力杰,等.无线传感器网络中移动协助的数据收集策略[J].软件学报,2013,37(2):198-214.ZHANG X W,DAI H P,XU L J,et al.Mobility-assisted data gathering strategies in WSNs[J].Journal of Software,2013,37(2):198-214.

[2]赵建军,王怀宇,赵泽阳,等.WSN中基于多分辨率和压缩感知的数据融合方案[J].电信科学,2014,30(9):92-99.ZHAO J J,WANG H Y,ZHAO Z Y,et al.Data aggregation scheme based on multi-resolution and compressive sensing in wireless sensor network[J].Telecommunications Science,2014,30(9):92-99.

[3]CAO D,JIN B,DAS S K,et al.On collaborative tracking of a target group using binary proximity sensors[J].Journal of Parallel&Distributed Computing,2010,70(8):825-838.

[4]夏候凯顺,严娟,叶小朋,等.基于Kalman滤波的无线传感器网络多目标跟踪[J].中山大学学报(自然科学版),2014,32(2):18-22.XIAHOU K S,YAN J,YE X P,et al.Multi-target tracking based on kalman filterand WSN [J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2014,32(2):18-22.

[5]GNING A,MIHAYLOVA L,MASKELL S,et al.Group object structure and state estimation with evolving networks and Monte Carlo methods[J].IEEE Transactions on Signal Processing,2011,59(4):1383-1396.

[6]张明波,陆锋,申排伟,等.R树家族的演变和发展 [J].计算机学报,2005,28(3):289-300.ZHANG M B,LU F,SHEN P W,et al.The evolvement and progress of R-tree family[J].Chinese Journal of Computers,2005,28(3):289-300.

[7]AVCIB,TRAJCEVSKIG,SCHEUERMANNP.Managing evolving shapes in sensor networks[C]//The 26th International Conference on Scientific and Statistical Database Management,June 30-July 2,2014,Aalborg,Denmark.New York:ACM Press,2014:1-12.

[8]CORPORATION H P.An energy-efficientnode selection algorithm in bearings-only target tracking sensor networks[J].International Journal of Distributed Sensor Networks,2014,41(1):118-121.

[9]崔亚峰.无线传感器网络目标跟踪算法的研究 [D].太原:太原理工大学,2015.CUIY F.Research targettrackingalgorithm ofwireless sensor networks [D]. Taiyuan: Taiyuan University of Technology,2015.

[10]ARMAGHANI F R,GONDAL I,KAMRUZZAMAN J,et al.Dynamic clusters graph for detecting moving targets using WSNs[C]//IEEE 38th Vehicular Technology Conference,Sept 3-6,2012,Quebec City,QC,Canada.New Jersey:IEEE Press,2012:1-5.

[11]徐翠.复杂网络中基于数据场的自适应聚类算法研究[D].武汉:华中师范大学,2014.XU C.Research on adaptive clustering algorithm based on data field in complex network[D].Wuhan:Central China Normal University,2014.

[12]张军强,王汝传,黄海平.基于分簇的无线多媒体传感器网络数据聚合方案研究[J].电子与信息学报,2014,35(1):8-14.ZHANG J Q,WANG R C,HUANG H P.Researchon cluster-based data aggregation for wireless multimedia sensor networks[J].Journal of Electronics&Information Technology,2014,35(1):8-14.

[13]ZHAO W,HAN Y,WU H,et al.Weighted distance based sensor selection for target tracking in wireless sensor networks[J].IEEE Signal Processing Letters,2009,16(8):647-650.

[14]张万里,何金刚,赵红梅.改进的Rao-Blackwellized粒子滤波算法在目标跟踪中的应用 [J].四川兵工学报,2014,36(7):82-86.ZHANG W L,HE J G,ZHAO H M.Target track based on improved Rao-Blackwellized particle filter algorithm[J].Journal of Sichuan Ordnance,2014,36(7):82-86.

[15]杨小军.基于性能边界和量化数据的 WSN目标跟踪传感器选择算法[J].电子学报,2014,42(6):1081-1085.YANG X J.Sensor selection for target tracking in wireless sensor networks based on performance bounds and quantized data[J].Acta Electronica Sinica,2014,42(6):1081-1085.

Multi-group target tracking method based on adaptive predictive clustering in WSN

LIU Shumu1,YANG Jian1,LI Yuansong2
1.Sichuan Engineering Vocational Technical College,Deyang 618000,China 2.Sichuan University of Science&Engineering,Zigong 643000,China

Aiming at the imbalance between energy using and tracking accuracy in multi-sensor target tracking,a method of trade-off network lifetime and accuracy was proposed.It was a multi-group target tracking method based on adaptive predictive clustering (APCMT),realizing the simultaneous tracking of multiple groups.Firstly,cluster was realized,which was to capture the changes of group behavior attributes,such as forming,mergering and spliting.Then,sensors were selected,which were expected to contribute to the group area sensor activation,and the sensors were used for group tracking.Scene simulation was in a square area of 1 000 m×1 000 m with 500 randomly deployed sensors.The effectiveness of the proposed method was verified by the simulation results.Compared with Kalman,energy-effective node selection (EENS)method and the improved dynamic cluster (IDC)method,the tracking precision of proposed method was higher.And because of the number of activate sensors was less,the computational time was less,the network lifetime had been improved significantly.

wireless sensor network,target tracking,multi-sensor,predictive clustering,multi-group,tracking accuracy

TP393

10.11959/j.issn.1000-0801.2016128

2016-03-04；

2016-04-08