基于动态簇的无线传感器网络加权质心跟踪算法

吴 斌,衣 晓

(海军航空工程学院电子信息工程系,烟台 264001)

基础理论

基于动态簇的无线传感器网络加权质心跟踪算法

吴 斌,衣 晓

(海军航空工程学院电子信息工程系,烟台 264001)

提出了一种适用于无线传感器网络中基于动态簇的目标跟踪算法,解决了无线传感器网络跟踪过程中目标信息传输及状态估计算法复杂度高的问题。该算法通过对目标周围的传感器节点临时组簇,避免了大规模唤醒节点从而降低网络寿命的问题。在目标状态的估计中,该算法基于探测到目标的声信号强度动态的调整节点的阈值,通过不同阈值所对应到目标的距离作为权值,由探测节点的位置作为目标所在多边形的各顶点进行加权质心定位算法。在硬件配置受限的无线传感器网络中,该算法复杂度低,对于节点的硬件不高。在仿真环境中,此跟踪算法的有效性也得到了验证。

无线传感器网络；目标跟踪；分簇；加权质心

0 引 言

无线传感器网络是一门新兴学科，其交叉结合了半导体、微电子、软件等学科理论。作为改变世界的重要新技术，无线传感器网络的发展与研究渐渐成为社会热点。其在灾害预警、检测和决策支持等方面应用前景巨大。与此同时，其在军方面的应用前景也相当巨大。结合无线传感器网络的特点，其在目标监测、预警、跟踪等发面具有很大的潜力。

利用无线传感器网络跟踪目标首先要确立网络的拓扑结构，即明确网络的覆盖范围，感知信息的传输路径，然后根据获得的信息进行目标的状态估计。由于传感器节点数量大、密度高，无线传感器网络常采用簇形结构分布式管理。目前无线传感器网络分簇算法主要可以分为集中式和分布式。然而，集中式跟踪需要节点向管理节点发送信息，节点的大部分能量消耗在通信上。为了克服集中式跟踪的缺点，很多学者研究利用分簇结构进行分布式跟踪[1-6]，文献[7]介绍了基于节点剩余能量和探测信号强度的动态分簇算法。文献[8]介绍了基于簇头分布式调度，簇内节点集中式调度，利用多节点分时跟踪的方法，该方法定位精度好，但对节点密度要求高。文献[9]介绍了基于无线传感器网络动态分簇的构建方法及基于线性规划的跟踪算法。文献[10]介绍了基于固定簇头的无线传感器网络分簇方法。本文结合文献[9]提出了一种新的跟踪算法。

1 目标跟踪结构

N个声音传感器节点均匀布置在监视区域内，节点通信半径为r，为了使网络的寿命延长，除了监视区域边界的节点一直处于激活状态外，内部节点通常处于休眠状态，只有收到激活信号时，才会进入激活状态。由文献[5]，目标的声信号强度一般随距离成指数衰减，当目标进入监视区域后，节点i在t时刻采样的声信号强度可表示为

式中：s表示目标信号源的声强度，di（t）是t时刻目标与节点i的距离，α是信号强度随距离的衰减指数，一般取2，εi是背景噪声，可以近似为高斯白噪声，节点采用三阈值检测，检测阈值记为E1，E2，E3。当目标经过节点i时，其过程一般是从靠近到远离。根据式（1），节点i的探测信号强度也会是一个从弱到强再到弱的过程，信号的峰值则意味着此时目标处在与节点i最近的距离上。

本文提出的目标跟踪过程大致分为以下几步：

（1）布置传感器节点，边界节点发现目标，临时组簇，粗计算目标速度、运动方向；

（2）目标进入监视区域，由内部节点进行精确跟踪；

（3）簇头根据探测到的目标信息估计目标的状态并汇报给管理节点。

2 动态簇的建立

该过程包括探测到目标的边缘传感器节点竞选簇头和簇成员征集，网络内部传感器节点竞选簇头和簇成员征集，具体过程如下：

（1）探测到目标的节点定义为i，i=1，2，3，….N1，节点当前测量到的信号强度为ei，节点当前电量为pi，定义

为参与竞选簇头的时延，其中e0为节点探测目标信号强度的上限，p0为节点携带的最大能量，α，β为参数，tmax为组簇的最大时延。目标离节点越近，节点剩余电量越高，ti就越小，成为簇头的概率越大。

（2）节点i在ti结束前收到其他节点广播成为簇头的消息，取消自身ti时间，并向簇头发送自身位置信息。若节点i在ti结束前未收到其他节点广播成为簇头的消息，则在ti结束时广播自身成为簇头的信息，信息包括成为簇头、自身位置等。

（3）处于簇内休眠状态的节点收到其他簇头当选的信息后，转入激活状态，并向簇头发送自身的位置信息。

从动态簇建立的过程来看，距离目标越近，剩余能量越大的节点，时延越小，因而成为簇头的概率越大。簇成员包括在竞选簇头中落选的节点以及在簇头通信范围内的休眠节点。由于节点的通信半径为感知半径的两倍，保证了只会形成一个簇。

当目标靠近监测区域时，最先是由处在网络边缘的工作节点发现并计算目标的各项参数，具体如图1所示。

当目标恰好出现在边缘节点1的最大感知半径上，此时节点1向其邻居节点发出广播，激活休眠节点，因为边缘节点时刻处于工作状态，为更好地节约边缘节点的能量，选择距离探测到目标的边缘节点最近的邻居节点2作为第一个动态簇的簇头。假设目标下个时刻以任意角度方向驶向监视区域，令目标进入监视区域的距离为R，A为目标进入监视区域的位置，B为AC的中点，为节约网络能量，尽量减少簇头更换频率，由于簇头担负计算和信息传输的任务，其能量消耗会大大增加，所以也不能使簇头工作过长时间，由图可知，由于节点1，2间距较短，可以近似的认为A到邻居节点2的距离为R，当目标运动到A点时，距离目标为r的节点并不全部包含在以邻居节点2为圆心，半径为R的圆中，所以在目标到达A之前，网络至少再形成一个簇才能达到精确跟踪的目的。取AC的中点B

图1 边缘节点示意图

3 目标状态估计

假设目标在监视区域内做随机运动，估计间隔时间较短时，目标在此间隔时间内可以近似的认为做直线运动。假定在某估计间隔时间内有n个节点探测到声信号强度的变化，其顺序依次记为e1，e2，…，en，下面探讨如何根据这n个节点估计目标的状态。

节点依次记录目标经过时信号强度的最大值ei（t）max和最小值ei（t）min，并发送给簇头，由簇头选取其中的最大值和最小值，

本文提出一个阈值半径的概念，即目标的信号强度达到某个阈值时，节点激活，此时目标位置就在以该阈值为探测信号强度所求的距离半径上。定义式（3）为阈值最大半径R，e（t）min为阈值E1。

本文提出一个基于多阈值半径加权质心算法，当目标信号强度到达阈值En且不超过阈值En+1时，认为目标与节点距离为En的阈值半径。加权质心算法具体如下（为方便表示，下文将不再使用阈值，直接以与阈值相对应的阈值半径表示）

目标运动到阈值范围内即可激活传感器进行工

可得到目标的位置，如图2所示。然而这样求出的目标位置与实际目标位置偏差较大，并且目标处在阈值内的节点可能不止一个，按上述算法会使节点的大部分能量消耗在计算目标位置上，可能使得节点能量提前耗尽，因此提出基于多阈值目标跟踪算法，来解决大量运算带来的能量消耗过大问题。

图2 节点探测示意图

考虑到目标的位置，会存在估计偏大的问题，如图3所示，目标处在某个距离阈值内部，靠近下一个阈值较近，但是计算权值却是用较大的距离权值，这样也会导致计算目标位置产生较大误差，所以再一次进行位置估算，将权值改为1，，如式（8）：

图3 目标位置图

将上述两式所求的坐标求和取中点可解决定位误差较大的问题，所求得的目标最终位置如下：

当目标经过节点时，节点记录所获取信号强度最大值及最小值，并上报给簇头，簇头根据所获得的的信息选取其中的最大值和最小值。当有节点探测到的最大值大于之前簇头选取的最大值时，或最小值小于之前簇头选取的最小值时，簇头将采用此节点的最大值或最小值用来重新计算E1，E2，E3，R，并发送消息给簇内节点，通知改变阈值。

节点1和节点n是一个估计时间间隔内第一个和最后一个探测到目标的节点，记时间为tn，假设此过程中e（t）max或e（t）min发生变化，由此带来R变化，记Rˊ，设与目标距离为ˊ的节点为（），个数为nˊ，距离为ˊ的节点为（，个数为mˊ，距离为R′的节点为（，个数为gˊ。记目标的位置为

4 能量损耗过程

在该无线传感器网络工作过程中，能量损耗主要集中在组簇、簇内节点探测和发送信息、簇头损耗三个方面。组簇的能量损耗是由探测到目标的节点进行临时组簇的能量损耗，包括探测到目标节点的探测损耗，竞选簇头损耗，簇头广播通知簇内节点成簇的通信损耗及簇内节点发送自身信息的通信损耗。簇内节点探测和发送信息的能量损耗包括簇内探测节点的能量损耗，节点发送目标信息的通信损耗。簇头损耗包括接收目标信息的能量损耗，计算目标信息的能量损耗。

节点发送l bit信息的能耗ETX（l，d）为

节点接收l bit信息的能耗ERX（l）为

簇头进行数据处理和融合时，处理l bit数据，需要消耗的能量为Eda-fu（l）

EDA为融合单位比特信息的能耗。

5 目标跟踪性能仿真及结论

为验证跟踪算法的有效性，本文进行了两组仿真，分别研究了目标斜向穿过监测区域及网络剩余能量。仿真条件设置如下，1000个传感器节点均匀分布在500×500 m的二维监视区域内，节点的探测半径r=20 m，信号强度s∈[6，100]，衰减系数α= 2，背景噪声均值ε=4，目标速度为5 m/s，探测及通信损耗为0.00005 J，系统总能量为10 J。仿真结果如图4，5所示。

图4 误差对比图

由图5可知，基于多阈值的目标跟踪算法定位误差显然更小，其误差大概分布在[2，6]m之间，相对于节点20 m的探测距离，这样的误差值是可以接受的。理论上讲，随着时间的推移，定位精度应该越来越高，因为随着不断地探测计算，目标的状态信息会更加精确，但是考虑到节点分布的不确定性，所以在中间时刻会出现一些定位误差偏高的情况，总体来说，在部署节点数量为1000个时，该算法的定位误差在2至4m左右，当节点数量增多时，定位误差会更小，这是因为随着节点的密度变大，探测不到目标的概率会大大降低。从图6中可以看出，基于本文算法的网络剩余能量是最大的。相比较于全网工作与固定簇工作，基于动态组簇能充分利用探测到目标的节点，而不是盲目的大范围的唤醒其周围的节点进行工作，从而节省了网络的能量。

图5 剩余能量对比图

6 结 语

目标跟踪是无线传感器网络的重要应用之一，包括网络组织和信号处理两个方面。增强系统生命力、延长网络寿命和提高跟踪精度是设计目标跟踪系统的重要目标。本文提出了基于动态组簇的无线传感器网络加权质心跟踪算法。该跟踪算法具有计算复杂度低和跟踪精度高等优点。

[1] ZHAO F，LIU J.Information-Driven Dynamic Sensor Collaboration[J].IEEE Signal Processing Magazine，2002，19（2）：61-72.

[2] LID，HU Y H.Energy Based Collaborative Source Localization Using Acoustic Micro-sensor Array[J].Journal EUROSIPApplied Signal Processing，2003（4）：321-337.

[3] JING T，et al.Binary Variational Filtering for Target Tracking in Sensor Networks[C].Proc of 14th IEEE/SP Workshop on Statistical Signal Processing.Madsion，2007：685-689.

[4] DURIC PM，et al.Target Tracking by Particle Filtering in Binary Sensor Networks[J].IEEE Trans on signal Processing，2008，56（6）：2229-2238.

[5] 孙超，赵路路，张影等.无线传感器网络分簇拓扑的覆盖区域节点调度优化算法[J].传感技术学报，2010（1）：166-121.

[6] 衣晓，邓露，刘瑜.基于基站划分网格的无线传感器网络分簇算法[J].控制理论与应用，2012，29（2）：145-150.

[7] 周红波，邢昌风，万福.面向目标跟踪的无线传感器网络动态分簇[J].电光与控制，2013（20）：14-18.

[8] 李迅，李洪峻.基于簇结构的无线传感器网络移动目标精确跟踪[J].传感技术学报，2009，22（12）：1814-1817.

[9] 邓克波，刘中.基于无线传感器网络动态簇的目标跟踪[J].兵工学报，2008，29（10）：1197-1202.

[10]邓露.无线传感器网络分簇算法研究[D].山东烟台：海军航空工程学院，2010

[11]Rappaport T，Wireless Communications：Principle& Practice[M].Englewood Cliff，NJ：Prentice-Hall，1996.

吴 斌(1992—),男,江苏泰州人,硕士研究生,主要研究方向为无线传感器网络目标跟踪；

E-mail：1031927070@qq.com

衣 晓(1976—),男,山东烟台人,教授,硕士研究生导师,主要研究方向为信息融合、无线传感器网络。

A W ireless Sensor Network-weighted-centroid Tracking A lgorithm Based on the Dynam ic Cluster

WU Bin，YIXiao
（Naval Aeronautical Engineering Institute，Department Of Electronic And Information Engineering，Shandong Yantai264001，China）

A suitable algorithm which is based on dynamic cluster forwireless sensor network in the target tracking is proposed to solve the problem of high complexity algorithm，which is target information transmission and state estimation in the process of wireless sensor network.By setting of sensor nodes of the cluster around the target temporarily，the algorithm avoidswaking up nodesmassively which will lead to reduce the network life.In the target state estimation，the algorithm based on the detected target acoustic signal intensity dynamically adjusts node’s threshold，through the different thresholds corresponded to the distance to the target as a weight，and by detecting node location as a target in each vertex weighted centroid of polygon for localization algorithm.In the limited hardware configuration of wireless sensor network，the algorithm complexity is low，and the node demand is not high.In the simulation environment，the effectiveness of the algorithm is proved.

wireless sensor network；target tracking；cluster；weighted centroid

TP393

A

1673-5692（2015）04-355-06

10.3969/j.issn.1673-5692.2015.04.005

2015-05-25

2015-07-30