基于粒子群模糊树的移动无线传感器网络的目标跟踪方法

摘要

本发明公开一种基于粒子群模糊树的移动无线传感器网络的目标跟踪方法，应用于无线传感器网络运动目标跟踪领域，针对现有技术存在的计算复杂，跟踪误差较大的问题；本发明引入了一个目标圆来表示目标，并利用此时目标圆圆心“探索”目标，而非“预测”目标；因此本发明只需要知道目标运动的大方向，将处于目标运动大方向之后的传感器向此时的目标圆圆心做超量移动，而处于目标运动大方向之前的传感器向此时的目标圆圆心做小量移动；同时由于每个被选取的传感器自身位置不一样，与目标圆圆心相对位置也不同，故移动后的位置就不会趋于同一点，但均有很大可能探测到目标，做到了“好而不同”；既保证了目标丢失率大幅降低，也提高了目标定位精度。

说明书

技术领域

本发明属于无线传感器网络运动目标跟踪领域，特别涉及一种基于粒子群模糊树的无线传感器网络运动目标跟踪技术。

背景技术

在早期的无线传感器网络研究中，由于传感器无充电能力，为了降低能耗，传感器被设计成静止不动的。随着大规模无线传感器网路的实际应用，人们发现静态无线传感器网络的一个显著弱点是部分传感器因担负着网络中较多负载而成为热点(hot spot)使电池迅速耗尽，从而造成整个无线传感器网络的死亡，这已经成为限制大规模无线传感器网络的一个重要因素。为了解决这个问题，已有许多研究在无线传感器网络中引入了移动节点，并论证了依靠节点移动实现负载平衡、延长无线传感器网络寿命的可行性。

目前，对于无线传感器网络中移动节点的位置与移动模式是否独立，可分为个体移动模型和组移动模型。前者已被研究的较为充分，而针对多移动节点的组移动策略研究较少。多传感器的联合路径规划相比于单节点，能更好的优化无线传感器网络任务分配、减少数据延迟而提高无线传感器网络的时效性，但由于多节点移动算法比单节点多增加了一个维度，计算复杂度显著增加，因此更具有挑战性。

现有的多传感器联合移动方案绝大多数都从减小数据采集的能耗与延迟，平衡负载的角度开展研究，并非以提高目标的精准探测与实时跟踪为出发点。针对目标探测与跟踪的传感器协调移动算法十分匮乏。此外，大量研究假设无线传感器网络中的传感器具有同等的感知与通信能力，因此已有算法并不完全适用于现行的多模态传感信号构成的无线传感器网络。并且，随着无线传感器网络规模的不断扩大，传统算法的复杂性急剧上升，很难满足对于移动目标跟踪的性能要求。

发明内容

为了解决上述技术问题，本发明提出一种基于粒子群模糊树的移动无线传感器网络的目标跟踪算法，在节能的基础上，极大程度减少了跟踪误差。

本发明采用的技术方案为：基于粒子群模糊树的移动无线传感器网络的目标跟踪方法，包括：

采用一个目标圆来表示目标；

读取当前时间的传感器状态，根据探测到目标的传感器集中所有传感器的中心位置，计算目标圆的圆心；

根据目标圆的圆心以及探测到目标的传感器集中所有传感器的探测距离，计算目标圆的半径；

第一级模糊决策树根据其输入参数，输出得到未探测到目标的传感器集中每个传感器的得分；所述第一级模糊决策树的输入参数为：未探测到目标的传感器集中所有传感器的实时剩余电量、移动速度、探测半径、以及与目标圆的圆心的距离；

选取若干个最高得分的传感器组成第一集合；

第一集合中的所有传感器移动方向为当前时间计算出的目标圆的圆心；

根据第一集合中每个传感器的速度及其与目标圆的距离关系计算出该传感器的最大移动距离与最小移动距离；

估计目标运动的大方向，并计算第一集合中每个传感器的与目标运动大方向的夹角；

第二级模糊决策树根据其输入参数，输出得到第一集合中每个传感器的移动距离百分比；所述第二级模糊决策树的输入参数为：第一集合中每个传感器的与目标运动大方向的夹角与目标圆的半径；

根据百分比移动第一集合中的传感器。

所述计算目标圆的圆心，具体过程为：计算探测到目标的传感器集中所有传感器的中心位置，然后判断该计算出的中心位置是否在探测到目标的传感器集中所有传感器的探测距离内；若是则以该中心位置作为目标的圆心；否则对该中心位置进行修正，直至新的中心位置在探测到目标的传感器集中所有传感器的探测距离内。

所述对该中心位置进行修正，具体为当探测到目标的传感器集中某个传感器与当前中心位置的距离大于该传感器的探测半径时，将当前中心位置向该传感器修正，使得该传感器与修正后的中心位置的距离小于该传感器的探测半径。

所述计算目标圆的半径，具体为：探测到目标的传感器集中每个传感器的探测半径与探测到目标的传感器集中每个传感器到目标圆的圆心距离之差的平均值。

所述第一级模糊决策树的输入参数采用隶属度函数进行归一化，第一级模糊决策树输出各等级的中心位置，然后根据输出各等级的中心位置，计算未探测到目标的传感器集中每个传感器的得分；

所述第二级模糊决策树的输入参数采用隶属度函数进行归一化，最终输出各等级的中心位置，根据输出各等级的中心位置，计算第一集合中每个传感器的移动距离百分比。

所述第一级模糊决策树的输入参数对应的隶属度函数、第一级模糊决策树输出各等级的中心位置、第二级模糊决策树的输入参数对应的隶属度函数、第二级模糊决策树输出各等级的中心位置以及规则库均通过粒子群算法进行调优训练。

所述粒子群算法进行调优训练，具体过程为：

A1、将每组参数均看做D维解空间中的一个粒子，首先初始化N个粒子形成一个群落；第j个粒子搜索到的最优位置称为个体最优值；整个粒子群搜索到的最优位置称为全局最优值；

A2、利用两级模糊决策树进行仿真跟踪，计算各例子的适应度；具体为：引入模拟目标，利用群落中的各个粒子对该模拟目标进行跟踪，计算各个粒子的跟踪误差与丢失率；根据粒子的跟踪误差与丢失率，计算该粒子的适应度；

A3、根据粒子的最优适应度对应的粒子位置，更新粒子个体最优值；

A4、根据全部粒子中的最优适应度对应的那个粒子的位置，更新粒子群全局最优值；

A5、更新粒子速度及位置；

A6、若达到预设代数或达到预设精度，则训练结束；否则将更新后的群落返回步骤A2，继续训练。

步骤A2所述粒子的适应度计算式如下：

Fv＝w₁*err+w₂*lost_ratio

其中，err表示粒子的跟踪误差，lost_ratio表示粒子的丢失率，w₁表示err的权重，w₂表示lost_ratio的权重。

本发明的有益效果：本发明基于粒子群模糊树的移动节点联合调度算法，引入了一个目标圆来表示目标，并采用当前的目标圆圆心“探索”目标；在节能的基础上，极大程度减少了跟踪误差和丢失概率；具备以下优点：

1、计算简单，不需要额外大量的信息通信与计算；

2、采用目标圆来表示目标很好地平衡了目标预测准确性和追踪难度的矛盾；

3、采用当前的目标圆圆心“探索”目标，做到了“好而不同”，既保证了目标丢失率大幅降低，也提高了目标定位精度；

4、采用目标圆来表示目标结合采用当前的目标圆圆心“探索”目标，使得本发明的方法鲁棒性更强，目标速度和轨迹变化对跟踪结果影响较小。

附图说明

图1为本发明的方案流程图；

图2为本发明实施例提供的粒子群算法对网络参数进行训练的算法流程图；

图3为本发明实施例提供的本发明方法对目标丢失率的影响；

图3(a)为目标运动轨迹为直线，目标速度为2m/s；图3(b)为目标运动轨迹为直线，移动传感器数量为40；图3(c)为目标运动轨迹为圆，目标速度为2m/s；图3(d)为目标运动轨迹为圆，移动传感器数量为40；图3(e)为目标运动模式完全随机，目标的方向和速度随意变化，速度范围：0-8m/s。

具体实施方式

为便于本领域技术人员理解本发明的技术内容，下面结合附图对本发明内容进一步阐释。

步骤1.在监测区域部署无线传感器网络：监测区域边界部署一定数量的静态节点，实现边界全覆盖，方便能检测到入侵目标，在监测区域内部随机部署一定数量的移动节点和静态节点。为了方便模型的泛化，本发明不限制传感器类型，可使用各种模态传感器，且只需检测是否有目标在自己的探测区域内出现，不需要目标的其它信息。

在步骤1中出现的“一定数量”是指可以根据具体应用时的监测面积、每个传感器的探测半径以及模态可以动态选择适合的传感器数量。

具体仿真的时候，本实施例监测区域为500m*500m，移动传感器探测半径为15-20m。本实施例中移动传感器选取了30个，40个，50个，60个做效果对比，覆盖率为15％-30％。结果表明，在本实施例中，采用本发明的方法，40个传感器就能达到预期的效果。

但是，本领域的技术人员应注意，本实施例中的仿真是模拟极端情况，为了更好地衡量算法的性能，因此把传感器数量布的很少，覆盖率很低，从而说明本发明的方法在极端的情况下也具有很好的性能。实际应用中布置传感器的数量，可以根据性能需求进行选择。

步骤2.读取传感器状态：记开始时间为t，每period秒，(本模型暂定为1s)读取所有传感器的缓存状态信息，将探测到目标的传感器集记为{N_s}，未探测到目标的传感器集记为{N_m}，且认为第i个传感器sensor(i)的探测区域是半径为R(i)的圆。

步骤3.计算目标圆：在预测目标方面，传统方法多数是在各种轨迹预测方法的基础上，用目标预测点来表示目标，这种做法的劣势明显：

1、无论是采用何种方法，无线传感器网络所预测的目标轨迹和真实轨迹总存在一定误差。尤其是当目标轨迹较为复杂且传感器分布稀疏的情况下，预测轨迹和真实轨迹往往存在较大误差。

2、误差的累积，随着目标在监测区域的持续运动，无线传感器网络对其的定位误差会逐渐增大。

3、容错率低，当某步的目标预测误差较大时，移动传感器向预测位置移动，可直接导致跟踪目标的丢失。

本发明为了克服传统方法的缺点，同时为了不增加无线传感器网络中的通信及计算负担，所以不考虑{N_s}中传感器探测区域交集的各种复杂情况，引入了一个目标圆来表示目标。

先计算{N_s}中所有传感器的中心位置E(t)，然后判断E(t)是否在{N_s}中所有传感器的探测距离内，若

s.t.dis[sensor(i),E(t)]>R(i)

则记：

sensor(i)→sensor_remote

让E(t)向sensor_remote修正，使得

dis[sensor(i),E(t)]≤R(i)

for all sensor(i)∈{N_s}

目标圆的圆心即为E(t)，接着计算目标圆的半径r：

r＝mean{R(i)-dis[sensor(i),E(t)]}

for all sensor(i)∈{N_s}

本发明对目标圆引入及计算的优势主要有：

1、计算简单，相比于目标预测点不需要额外大量的信息通信与计算。

2、很好的平衡了目标预测准确性和追踪难度的矛盾，目标圆越大则包含目标真实位置的几率越大，但同时导致追踪难度的增加。

3、结合“探索”式目标跟踪方法，使得模型鲁棒性很强，目标速度和轨迹变化对跟踪结果影响较小。

4、用目标圆表示目标是整体权衡之后的考虑与调整，也是整个发明对目标跟踪的基础。

步骤4.利用第一级模糊决策树选取需要移动的传感器集{N_c}：将{N_m}中所有传感器的实时剩余电量、移动速度、探测半径、以及与目标圆的圆心E(t)的距离作为第一级模糊决策树的输入。每个参数的具体值输入后，首先会被模糊成低、中、较高和高四级及各级的隶属度。(其参数使用粒子群算法进行调优训练，训练过程会在下文说明。)

本发明中模糊决策树均采用高斯函数作为各隶属度函数(member function)的基础，先将输入的具体数值代入到各个级别对应的高斯函数中，再将其归一化，使其对应的四个等级隶属度之和为1。

完成输入值模糊化后，将其与规则库进行匹配，规则是对输入与输出非线性对应关系的描述，常用“if-then”语句描述，如：

“If剩余电量为高，移动速度为高，探测半径为高，且与E(t)距离为低，

Then得分为高”

规则的输出结果也是用低、中、较高、高四级表示，每个结果的FS(Fire strength)为对应隶属度乘积。带入所有符合的规则计算后，得到四个得分等级的总FS，则每个传感器最终得分利用中心法计算：

for all sensor(i)∈{N_m}

其中，c_l为第l等级输出的中心位置，通过粒子群算法训练得到。

比如本实施例中“剩余电量、移动速度、探测半径、与E(t)距离”这四个输入都对应有四个等级，规则库就是所有的可能组合，即有4的4次方＝256条规则。上述例子中的，“高高高低”对应得分为高，这个对应关系的选取是通过下文的粒子群算法寻优得到最优的方案。通过这种智能算法寻得最优参数，就是本发明方法的优点之一。避免了人为设置所引起各种偏差。

选取得分最高的k个传感器组成集合{N_c}。k取值越小，即每步的移动传感器数量就少，总的耗电量小，而联合跟踪效果就稍微差一点；k取值越大，移动传感器的数量越多，耗电量就大，联合规则效果就好。可以根据具体实施中的要求而定。

在本实施例的仿真实验条件下，可以认为k取值为2是最佳方案，即保证了很好的跟踪效果，又避免了多传感器移动带来耗电量的增加。可以根据每种应用对性能和耗电的要求，动态调整，但是一般不需要超过4就应该能达到要求。

步骤5.规划移动策略，“探索”目标位置：选取的传感器集{N_c}移动方向为此时目标圆的圆心E(t)，而非下一时间点的目标预测位置。

传统方法为“预测”目标位置，并使移动传感器趋于目标的下一预测点。而预测目标位置，尤其是预测下一时刻的目标位置，想要得到较好的结果必须建立在：

1、对目标的历史轨迹拟合较为精确，这样预测下一时刻目标位置才能保证有一定的参考价值。

2、目标运动策略较为简单，速度及目标前进方向必须保证一定的稳定性。

而这两点在实际情况中都是很难满足的，无线传感器网络若没有配置能精确探测目标位置的设备，就很难精确拟合目标轨迹；同时，实际情况下目标的移动是很难预测的，甚至没有任何规律。一旦目标速度或移动方向发生变化，预测下一时刻目标位置就十分困难，就会导致“预测”的方法风险极大，很容易丢失目标。而在很多重要的应用场景中，丢失目标所带来的代价是巨大的。

所以本发明利用此时目标圆的圆心E(t)“探索”目标，而非“预测”目标。只需要知道目标运动的大方向，处于目标运动大方向之后的传感器向E(t)做超量移动，而处于目标运动大方向之前的传感器向E(t)做小量移动。

具体的当前目标运动大方向可以根据前几次目标圆的圆心来确定总体的前进方向，即为当前目标估计得到的运动大方向。若前几步丢失或者当前为第一步的话，则默认这一步中传感器与目标运动大方向的夹角为中等。

同时由于每个被选取的传感器自身位置不一样，与目标圆的圆心E(t)相对位置也不同，故移动后的位置就不会趋于同一点，但均有很大可能探测到目标，做到了“好而不同”。既保证了目标丢失率大幅降低，也提高了目标定位精度。

首先，利用前n步的跟踪，估计目标的速度v_estimate。本发明采用了目标圆+“探测”的目标跟踪模式，使得模型对目标圆以及速度估计v_estimate都没有很高的精度要求。

第i个传感器的速度为v(i)，则{N_c}中每个传感器最大移动距离应为：

最小移动距离为：

接着计算{N_c}中每个传感器与目标运动大方向的夹角：

然后将angle和目标圆半径r输入到第二级模糊决策树中，(若E(t-1)丢失，则angle在第二级模糊决策树中默认为中级)和第一级模糊决策树一样的计算流程，输入模糊为四级，利用归一化的高斯函数作为隶属度函数，最后输出移动距离百分比p(i)。则{N_c}中第i个传感器sensor(i)的移动距离为：

S(i)＝p(i)*[S_max(i)-S_min(i)]+S_min(i)

步骤6.{Nc}中传感器移动，并更新网络参数。

利用粒子群算法对网络参数进行训练具体包括下分步骤：

1.初始化参数：本发明中需要训练的参数主要由三方面构成：

1)模糊决策树中隶属度函数的均值和方差；

2)输出结果的四个模糊等级的中心；

3)模糊规则库中的输入和输出对应规则。

将每组参数均看做D维解空间中的一个粒子，首先初始化N个粒子形成一个群落，其中第j个粒子表示为：

X_j＝(x_j1,x_j2,…,x_jD),j＝1,2,…,N

同时，第j个粒子的速度也是一个D维向量：

V_j＝(v_j1,v_j2,…,v_jD),j＝1,2,…,N

第j个粒子搜索到的最优位置称为个体最优值：

P_j＝(p_j1,p_j2,…,p_jD),j＝1,2,…,N

整个粒子群的搜索到的最优位置称为全局最优值：

G_best＝(g₁,g₂,…,g_D)

2.利用模糊树进行仿真跟踪：引入模拟目标，利用群落中的各个粒子对其进行跟踪，计算各个粒子的跟踪误差err和丢失率lost_ratio，利用跟踪效果计算各个粒子的适应度(Fitness Value)：

Fv＝w₁*err+w₂*lost_ratio

其中，w₁和w₂是对精度和丢失率衡量的权重；w₁和w₂根据实际应用中的需求进行选择具体取值，如果任务需求是不能丢失目标，那么w₁就可以为0，w₂可以为1；如果是追求精度，那么w₂就可以为0，w₁可以为1；如果需要同时考虑丢失率跟精度，那么可以根据实际应用中的具体需求，以及二者的量级，调整权重来求得目标模型。

3.更新粒子的个体最优值P_j，即粒子的最优Fv所对应的位置；

4.更新粒子群历史最优值G_best，即全部的粒子中，最高Fv对应的那个粒子的位置；

本实施例中可以将Fv看作是粒子的得分，某个粒子得分最高对应的位置，即为该粒子的个体最优值；粒子群中所有粒子中得分最高对应的那个粒子的位置，即为全局最优值。

5.粒子的速度与位置更新：

V_j′＝w*V_j+rand*r₁*(P_j-X_j)+rand*r₂*(G_best-X_j)j＝1,2,…,N

X_j＝X_j+V_j′j＝1,2,…,N

其中，w为惯性因子，r₁和r₂为学习因子，rand表示随机数。

6.若达到预设代数或达到预设精度，则训练结束；否则将获得的新群落返回2继续训练。

7.利用训练好的参数布置无线传感器网络，利用模糊决策树进行实时目标跟踪。

为了更好的描述算法性能，本实施例以如图3所示，传感器(30-60)较少，监测区域覆盖率(15％-30％)很低的情况下，静止状态下的丢失率特别高，达到了80％左右，因此本实施例此处以丢失率代表跟踪性能比精度更有意义；如图3所示给出了不同目标运动轨迹时所选取的k值对丢失率的影响，图3(a)为目标运动轨迹为直线，目标速度为2m/s；图3(b)为目标运动轨迹为直线，移动传感器数量为40；图3(c)为目标运动轨迹为圆，目标速度为2m/s；图3(d)为目标运动轨迹为圆，移动传感器数量为40；图3(e)为目标运动模式完全随机，目标的方向和速度随意变化，速度范围：0-8m/s；从图3(a)、图3(c)、图3(e)可见当传感器(30-60)较少时，监测区域覆盖率(15％-30％)很低的情况下，静止状态下丢失率在80％左右，而利用本发明的方法，能使得丢失率大幅度降低；随着移动传感器的数量增多，丢失率随之减低；更重要的是，k的增大，能使丢失率迅速降低到极低的水平；一般k取2时就能保证很好的跟踪效果，同时保证了较低的能耗，延长了网络的寿命。从图3(b)、图3(d)、图3(e)可见算法对不同的目标运动模式(包括速度和方向的变化)具有很高的鲁棒性。在仿真条件下，移动传感器数量为40，k为2时就能保持良好的跟踪效果。可见本发明采用目标圆来表示目标结合采用当前的目标圆圆心“探索”目标，使得本发明的方法鲁棒性更强，使得目标丢失率大幅降低，目标速度和轨迹变化对跟踪结果影响较小。

本领域的技术人员应知，本实施例图3所示是为了阐述本发明方法的适用性，模拟的极端情况，只用到了二进制信息，没有目标的其他信息，如方向，距离，速度等，所以跟踪效果的提升受到网络的限制；但是在真实的跟踪过程中，在采用本发明方法的前提下，当传感器的其他信息在相应模块加入时，跟踪效果可以进一步提升。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的权利要求范围之内。