崔亚峰，史健芳

（太原理工大学信息工程学院，太原 030024）

基于自适应动态簇和预测机制的WSN目标跟踪算法*

崔亚峰，史健芳*

（太原理工大学信息工程学院，太原 030024）

无线传感器网络由大量能量有限的传感器节点组成，如何高效利用网络中节点的能量是无线传感器网络用于目标跟踪时研究的主要内容。合理构建动态簇可以有效降低网络的能量消耗，延长网络的生命周期，本文通过改进动态簇组建过程中簇头的选举和簇成员的征集过程，达到进一步节能的效果。其中，簇头的选择，综合考虑节点的能量和节点离目标的距离两个因素。簇成员的征集，同时考虑目标的移动速度和网络中节点的分布情况。同时，引入有效的预测机制，通过避免盲目的唤醒网络中的节点和降低跟踪延迟，可以进一步增强网络的跟踪性能，使跟踪过程更加有效和稳定。仿真结果表明本文算法在保证跟踪精度的前提条件下，可以有效节省网络中节点的能量。

无线传感器网络；目标跟踪；动态簇；预测机制；节能

无线传感器网络（Wireless Sensor Network，WSN）是由部署在监测区域内大量的廉价传感器节点通过无线通信方式形成的一个多跳自组织网络［1］。与传统网络相比，无线传感器网络在目标跟踪中的优势明显，它具有跟踪可靠、及时、隐蔽、低成本、低功耗等特点［2］。但同时，由于无线传感器网络中的节点能量有限，所以如何降低网络能量消耗，从而延长网络的生命周期，是无线传感器网络用于目标跟踪时重点研究的问题［3］。

动态簇是在监测目标的周围形成的一个节点群，传统的PDC算法［4］是采用固定半径的动态簇结构来跟踪目标。为了有效跟踪目标，动态簇的半径取值较大，这样在整个跟踪过程中，处于工作状态的簇内节点数较多，能量消耗大。近年来，随着对动态簇结构的研究，有些学者提出了动态簇半径的自适应调整［5-6］，该算法簇半径的调整只考虑到运动目标的移动速度，没有考虑无线传感器网络中节点的分布密度，有可能使簇内节点太少，无法达到有效跟踪［7］。同时，跟踪目标时，没有引入预测机制［8］或使用的预测机制不合理［9］，使网络响应延迟，不利于目标的跟踪。

本文对传统的动态簇无线传感器网络目标跟踪算法［10］进行改进，提出综合考虑运动目标的运动速度和网络中节点的分布情况构建动态簇，在跟踪过程中簇结构的半径根据目标的运动速度和网络中节点的分布情况自适应调整，通过优化簇结构，从而提高网络中能量的使用率。同时，引入预测算法，预测运动目标的移动轨迹，以便动态簇根据目标的预测轨迹，提前唤醒目标周围监测半径内的传感器节点，准备监测目标。该算法模型简单，计算量小，避免了盲目唤醒节点所造成的能量浪费，有效节省了节点的能量，同时降低了响应延迟，延长了网络生命周期。

1 网络的假设与初始状态

1.1 本文中网络的假设

为了简化问题，不失一般性，本文对网络做如下假设：

①目标区域节点之间为覆盖连通的。

②所有节点都具有相同的能力，节点在网络中的地位平等。

③节点具有定位能力，即每个节点能够获得自身的位置信息。

④节点有五种工作状态：CH（Cluster_Header，簇头状态）、CM（Cluster_Member，簇成员状态）、Idle（等待状态）、Sleep（睡眠状态）、Dead（死亡状态），其中CH和CM状态都属于Work状态。Work状态是传感器节点完全激活的状态，具有感知信息、融合信息和传输信息的能力，因此，Work状态的节点消耗能量最大；Idle状态的节点只能感知信息，节点能耗很小；Sleep状态的节点什么都不做，可以认为，处于该状态的节点不消耗能量；处于Dead状态的节点的能量已经耗尽，不能再继续工作。

1.2 节点自身保存信息：

为了算法有效工作，节点保存如下信息：

①节点的ID。

②节点当前所处状态。

③节点所处位置的坐标。

④节点的最大能量值。

⑤节点当前所剩的能量。

⑥邻居节点ID表以及对应节点所剩余的能量。

1.3 网络的初始状态

传统算法中，通常对初始状态有两种假设：一种是假设初始状态下，网络边缘的传感器节点处于等待状态，网络中剩余的节点处于睡眠状态［11-13］。另一种是假设网络中的节点周期性的进入睡眠状态。第一种假设会使网络中节点能量消耗不均匀，处于网络边缘的节点会很快死亡。第二种假设对网络中的所有节点进行周期性的唤醒—睡眠操作，网络的整体能耗较大，而且，可能会发生不能及时发现目标等意外情况。

本文针对上述两种网络初始状态假设的缺陷进行改进，提出当WSN网络中无目标时，网络内的节点使用LEACH-PSOC算法［14］形成动态簇，簇内节点轮流担任簇头，平衡网络中的节点能量。

2 基于自适应动态簇和预测机制的跟踪算法

自适应动态簇的形成和预测机制的合理应用是无线传感器目标跟踪算法的核心内容，本文提出自适应动态簇算法及预测算法。

2.1 自适应动态簇组建算法：

动态簇的组建过程主要包括探测到目标的传感器节点竞选簇头和簇头对簇成员的选择等。本文提出的算法中动态簇的形成过程如下：

①竞选簇头

当目标进入监测区域时，目标可能会被多个节点监测到，监测到目标的节点之间相互交换信息，选出距目标最近的节点，然后，该节点广播消息并唤醒以R为半径的圆内的节点，同时，网络中其它处于工作状态的节点转为睡眠状态，唤醒的节点对目标测距，距离大于设置阈值d和能量低于20%*ei_max的节点重新睡眠。

簇头在当前处于唤醒状态的节点中选取，簇头的选举同时考虑节点当前的剩余能量ei_current［3］和节点距目标的距离ri两个因素，距目标越近、剩余能量越多的节点被选为簇头，因此，本文提出通过式（1）来选择簇头。

式中，ei_current表示节点i当前剩余的能量，ri表示节点i离目标的距离。唤醒节点根据式（1）计算各自的剩余能量和距目标距离的比值Hi，然后相互交换各自的Hi值，选举Hi最大的节点作为簇头节点，其余节点转为睡眠状态。

②自适应动态簇组建

选出的簇头节点以半径R唤醒圆形区域内的节点，唤醒的节点成为簇成员并与簇头协同工作，形成簇，对目标进行跟踪。R的选取非常重要，如果R太小，则簇内节点数目太少，不能有效跟踪；如果R太大，则簇内节点数目较多，造成不必要的能量浪费。

本文提出半径R根据目标的运动状态（如速度v）和传感器的分布密度自适应确定。首先，簇的半径至少应该大于目标移动速度。其次，要达到有效跟踪，簇内传感器节点应该达到一定数目。

为了节省能量和有效跟踪，簇内节点数N应该满足

其中，Nmin和Nmax为两个设定的阈值，Nmin表示要达到有效跟踪簇内至少应该包含的节点数目，Nmax表示簇内节点数目的上限。 Nmax应该设置合理，否则，不但浪费能量，而且增大计算量。本文实验中Nmin和Nmax分别取8和18。

初始时R1是根据具体应用环境及经验或实验设置的一个定值，簇头节点唤醒半径R1内的节点，之后根据簇内节点数目N是否满足式（2）而调整R1，若N＜Nmin，则增大半径R1，若N＞Nmax，则减小半径R1。直到N的取值满足式（2）为止，此时自适应得到的半径R1用于下一步决定最终簇半径R。

目标的运动速度v也会影响半径R的选取，速度v较大，则半径R也较大；速度v较小，则半径R也较小。

综合考虑目标运动速度v和上述半径R1，可以得到，簇头唤醒的半径R为：

其中α为常数，可以根据具体情况设置，本文实验中α=2。由于速度v的量纲为m/s，半径R1的量纲为m，此处目的是比较αv和R1的大小，用来确定半径R，所以统一量纲为m。当目标刚进入监测区域时，无法获得目标的移动速度，此时取R=R1。

由于目标的移动速度v是变化的，且上述R1是自适应的，因此R是根据目标运动状态和网络分布情况自适应调整的。

2.2 预测算法

预测算法可根据目标当前运动状态预测目标下一时刻的状态，从而提前唤醒监测区域的传感器，及时跟踪目标，有效降低传感器网络的能量消耗。预测机制的引入，节点对目标的跟踪不再是被动的跟踪，而是对运动目标主动的感知，本文使用最小二乘估计和二次多项式拟合对目标轨迹进行预测。

设拟合多项式为y=a0+a1x+a2x2，则本文中测出的各点到这条曲线的偏差平方和为：

等式两端对ai求偏导，化简整理得

2.3 基于预测机制的跟踪算法

动态簇形成以后，对目标进行预测跟踪，本文提出的算法跟踪过程如下：

①当前簇的簇成员节点将使用RSSI算法［15］测出的到目标的距离ri和自身的坐标（ ）xi,yi发送给簇头节点，簇头节点选取距目标最近的三个节点信息，使用三边测量法［16］，计算出目标的位置坐标P（x,y）并存储在簇头节点中。

②若簇头节点距目标距离小于d（本文中d取为0.5R），当前簇对目标进行跟踪，目标前一时刻的位置坐标记为Old（x,y），目标当前时刻的位置坐标信息，记为Now（x,y），当簇头节点储存目标的三个位置坐标信息时，使用最小二乘预测算法和二次多项式拟合，计算出目标下一时刻的位置坐标Next（ ）x,y 。

③若簇头节点距目标距离不小于d（本文中d取为0.5R），簇头迁移。新的簇头符合式（1），然后，新簇头广播一个信息给其他节点，宣称自己成为簇头，其他节点自动转换为该簇头的簇成员节点。旧簇头在接收到新簇头发来的簇头当选信息后，将自己储存的P（x,y）位置信息传送给新簇头，同时，旧簇头转换为簇成员节点。新的动态簇根据2.1节式（2）中的方法自适应调整簇成员，以便有效跟踪和节能。新形成的动态簇重复步骤①、步骤②中的过程，继续进行跟踪。

④重复步骤②、步骤③，这样，在新的簇头节点中总会存储三个坐标信息，即：Old1（ ）x,y，Old2（x,y）和Now（x,y）。根据这三个坐标信息，使用最小二乘预测算法和二次多项式拟合，计算出目标下一时刻的位置坐标Next（ ）x,y。⑤簇头节点通过路由唤醒坐标Next（ ）x,y附近的节点进入等待状态。

⑥随着目标的移动，重复步骤④、步骤⑤，即可实现目标的跟踪。

基于预测机制的跟踪算法流程图见图1。

图1 工作流程图

3 仿真实验

为了验证本文提出的基于预测机制的跟踪算法，本文利用MATLAB对算法的能量消耗和跟踪精度进行仿真实验。假设1 000个节点随机分布在500 m×500 m的区域，目标在区域内做变速运动，在1 s～40 s内，目标运动速度为［vx, vy］=［3 m /s,3 m/s］，41 s～80 s内，目标的运动速度为［vx, vy］=［8 m/s，4 m/s］，目标初始位置为（0，0），取 Nmax=18，Nmax=18，每个传感器的检测半径为30 m，通信半径为50 m，传感器采样周期为1 s。

为了证明算法的有效性，本文对算法跟踪误差，每一时刻跟踪节点的数目以及能量节约百分比进行了仿真实验。依次为图2～图4。

图2 跟踪性能对比

图2为跟踪性能比较图，可以看出，本文的算法在跟踪误差为0.2～2.6，基本维持在1.2左右，传统误差为0.1～2.3，基本在1.0上下。本文算法略大于无预测机制且簇半径固定的传统算法，这是因为传统算法的簇内参加跟踪的节点数目一般要大于本文提出的算法，因此在牺牲传感器节点能量的条件下，会提高跟踪的精度。但是，本文算法的跟踪精度同样也可以满足要求，而且可以延长网络的生命期。较无预测机制且簇半径固定的传统算法及文献［5-9］中提出的算法有明显改进。

簇内传感器节点数仿真结果如图3所示。

图3可以看出，本文所采用的簇结构动态调整方法，可以使簇内节点数基本稳定在一定范围内，簇内节点数较传统算法少，这样既可以有效跟踪，同时有效节省网络的能量，延长网络的生命。而传统算法由于簇半径固定，所以为了达到有效跟踪目标的目的，需要设置簇半径较大，这样会浪费节点的能量。

图4 每一时刻能量节约百分比

图4为本文算法比传统算法每一时刻网络中的能量节约百分比。可以看出，本文算法有效节省了网络中节点的能量，可以达到延长网络生命周期的目的。

4 结语

无线传感器网络由大量能量有限的传感器节点组成，因此，如何高效利用网络中的节点能量是传感器网络面临的主要挑战之一。本文通过改进动态簇的组建过程中簇头的选举和簇成员的征集过程，来达到进一步节能的效果。簇头的选择，综合考虑节点的能量和节点离目标的距离两个因素。簇成员的征集，同时考虑到目标的移动速度和网络中节点的分布情况。此外，引入有效的预测机制，使跟踪过程更加有效和稳定。仿真实验表明，与传统算法相比，本文算法在保证跟踪精度的前提条件下，可以有效节省网络中节点的能量。

［1］ 孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版社，2005：391-402.

［2］ 李凤保，李凌.无线传感器网络技术综述［J］.仪器仪表学报，2005（z2）：559-561.

［3］ 彭勇，王国军，邢萧飞.无线传感器网络中一种自适应目标跟踪协议［J］.传感技术学报，2009，22（3）：427-432.

［4］ 李芳芳，韩冰，单娇娇.WSN中基于预测机制动态簇的目标跟踪算法［J］.计算机与数字工程，2012：40（11）：55-59.

［5］ Enam R N.Energy Efficient Differential Data Aggregation in a Dynamic Cluster Based WSN［C］//2013 International Conference on Collaboration Technologies and Systems（CTS），IEEE，2013：580-583.

［6］ Hu B，He N H.WSN Collaborative Target Tracking Based on Dynamic Clustering［J］.Advanced Materials Research，2013，712：1868-1871.

［7］ Rabia Noor Enam.Energy Efficient Differential Data Aggregation in a Dynamic Cluster Based WSN［C］//International Conference on Collaboration Technologies and Systems（CTS），2013：580-583.

［8］ Dan Liu，Nihong Wang，Yi An.Dynamic Cluster Based Object Tracking Algorithm in WSN.Intelligent Systems（GCIS），2010 Second WRI Global Congress on（Volume：1），2010（1）：397-399.

［9］ Jing Teng，Hichem Snoussi，Cedric Richard.Prediction-Based Cluster Management for Target Tracking in Wireless Sensor Net-Works［J］.Wireless Communications and Mobile Computing，2012（12）：797-812.

［10］Huiyong Yuan，Yongyi Liu，Jianping Yu.A New Energy-Efficientunequal Clustering Algorithm for Wireless Sensor Networks［C］// IEEE Conference on Computer Science and Automation Engineering（CSAE），2011（1）：431-434.

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

［12］刘军，刘晖，叶宁，等.无线传感器网络自适应动态簇目标跟踪策略［J］.东北大学学报：自然科学版，2011：32（8）：1080-1083.

［13］刘立阳，张金成，吴中林.基于分布式动态簇结构的WSN自适应目标跟踪算法［J］.传感技术学报，2012，25（1）：110-113.

［14］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26（1）：116-121.

［15］杨文铂，邢鹏康，刘彦华.一种基于自适应RSSI测距模型的无线传感器网络定位方法［J］.传感技术学报，2015，28（1）：137-141.

［16］王小平，罗军，沈昌祥.三边测量法的结果稳定性研究［J］.计算机工程与科学，2012，34（6）：12-17.

崔亚峰（1990-），男，硕士研究生，主要研究方向为无线传感器网络目标跟踪，lsky.cyf@163.com；

史健芳（1966-），教授，博士，硕导，主要致力于智能仪器及检测技术、智能信息处理等方向研究。

Target Tracking Based on Adaptive Dynamic Clusters and Prediction Mechanism in WSN*

CUI Yafeng，SHI Jianfang*
（Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China）

Wireless sensor network is composed of a lot of energy limited sensor nodes，therefore，how to use the energy of nodes in network efficiently is one of the major challenges for target tracking in sensor network.It proves the reasonable construction of dynamic cluster structure can not only reduce the network energy consumption effectively but also reinforce the lifecycle of the network.By improving methods of the choose of cluster heads and the selection of the cluster members in the process of dynamic cluster construction，this paper is aimed to achieve the further effect of energy saving.The choose of cluster heads is based on the energy of the nodes and the distance from node to target.The selection of the cluster members takes the target's movement speed and the distribution of network nodes into consideration.And the introduction of effective prediction mechanism which can avoid waking up nodes in the network blindly and reduce the time delay of tracking process can further enhance the tracking performance of the network.In addition，the effective prediction mechanism makes the tracking process more effective and stable.The simulations show that the algorithm in this paper can save the energy of the nodes in the network effectively under the tracking precision condition.

wireless sensor network；target tracking；dynamic cluster；prediction mechanism；energy conservation EEACC：6150P；7950

TP393

A

1004-1699（2015）07-1046-05

10.3969/j.issn.1004-1699.2015.07.18

项目来源：国家自然科学基金（50905169）；武器装备探索研究项目（7131017）；山西省自然科学基金项目（2014011019-1）

2014-11-19 修改日期：2015-03-17