基于快速MH变异的遗传粒子滤波的WSN目标跟踪

魏 颖，郭 鲁

(沈阳工学院 信息与控制学院，辽宁 抚顺 113122)

0 引言

无线传感器网(WSN, wireless sensor network)是21世纪最重要的前沿技术之一，它的网络连接是通过无线通信实现的，通过本身的一些传感装置检测并感知相应的环境数据，实现信息的相互融合。目标跟踪是无线传感器网络的一个主要研究领域，如交通监测，捕捉战争状态等。例如，将一个测试目标放置在布置传感器的地点内，它运动时，通过传感器测量，然后反馈到跟踪系统，以此接近预估目标的位置[1]。粒子滤波(PF,particle filter) 是一种蒙特卡罗算法，它是基于递推计算的序列算法，基本思想是在当前系统状态分布中随机抽取一些加权的粒子，通过计算对系统的下一个状态进行更新和估计，适用于所有的测量模型以及状态转换模型，所以在无线传感器的目标跟踪中，上述方法比较适合[2]。粒子滤波算法在多次迭代后会退化，即只有少数粒子具有较大的权重，而大多数粒子的权重很小，几乎为零，这会消耗大量的时间。这类问题通常下列的方法解决：首先是改善意义重大函数，其次是对粒子重新采样。以上的方法主要改善粒子退化效率来解决粒子降解的问题。在新的取样之后，多次选择重要性高的粒子，因此，粒子的多样性已经失去了一些，即所谓的粒子缺失。那么在跟踪目标时，一旦监测的准确性不高或目标丢失，系统很可能不能自动会聚。本文通过利用进化机制保证粒子群优化过程中局部的多样性，并且处理粒子算法中粒子退化的缺陷。本文对于粒子滤波跟踪算法的粒子衰退问题给出了一种快速MH变异遗传的粒子滤波跟踪算法[3]。快速MH变异遗传算法是在遗传粒子滤波算法上，加入遗传进化思想，利用快速移动粒子交叉次数和变异算子，同时与赌轮选择一起产生了一种新的遗传算法,更快地提取到反映目标概率特征的典型粒子。结果显示，该算法能够保护种群的多样性，节省时间，加速收敛速度。

为此，文章用MHGAPF特指用快速MH变异遗传重采样算法的PF算法的无线传感器目标跟踪算法。把快速MH变异遗传算法加入到传统粒子滤波中，用来增加样品组的多样性，减少样品组的衰退。缩短监测时间和提高监测能力后续行动。实验结果表明，算法具有显著的优点[3]。

1 粒子滤波算法

粒子滤波是在蒙特卡洛提出的方法上改进的算法。该算法使用一类的随机加权估量器(也称为粒子)来类似的后概率密度u(xk|z1:k)。

(1)

(2)

(3)

通过上述的公式，代入式(2)，可以确定粒子显著性的递归公式(4):

(4)

通过公式(3)和式(4)形成了一种基于粒子过滤算法的方法，其中重采样算法可以减缓传统粒子过滤算法中粒子所出现的问题。

在现有的重采样算法中，选择高权重粒子进行更新，然而粒子的多样性将丢失。因此，基于粒子滤波算法的遗传算法被插入到重采样过程中。通过使用交叉和变异等运算符来确保粒子多样性的方法。可以保持对粒子权重选择和演变过程的高适应性。它能很好地适应颗粒重量的选择和发展上这样就实现了粒子的有效性[4]。

2 遗传粒子滤波算法

2.1 粒子集合的编码、遗传操作

把遗传算法引进到粒子滤波算法中，可以在粒子群优化中引进新的个体。粒子群多样性继续保持。粒子滤波的精度和鲁棒性有效的提升，所以称为遗传粒子滤波。为了保证计算速度，采用十进制编码。遗传交叉和变异等过程是在十进制的基础上进行的。

通过引进遗传进化理念，可以获得新的基因过滤样品。粒子被视为染色样品，每个粒子的相应加权系数被用作染色体样品的适应性函数。染色体标准粒子滤波算法解决了选择过程中粒子退化和耗尽的问题。并且交叉引用和基因突变算法。通过选择和交叉操作，后代可以继承和调整每个颜色样本的相应匹配功能的大小，而父系一代的变化可以沿着进化方向发展。也就是说，从总体优化的角度来发展。

遗传操作的原始种群一般是在随机时刻生成的粒子群，这个粒子群通过初始状态方程计算得到的。个体的适应性决定目标和模板之间的相似性程度，其被选中的可能性越大是由于其相似度越大，被保留的可能性越大。根据一定的概率选择一对交叉运算。最后，有概率的选取对象进行十进制渐变。然而个体的多样性通过交叉和变异来增强，以防止局部解被混淆[5-6]。

2.2 遗传粒子滤波算法

进行重采样GAPF的算法，其算法运行过程可以描述如下：

Step1:在原始种群粒子中u(x0)中采样M个粒子xi0，i=1，2，…，m；

Step2: 计算a时,我们通过前面的定义状态的转移方程来刻的粒子更新xia，i=1，2，…，m；

Step3: 通过量测方程计算a时刻集中各个新粒子的权值xia，i=1，2，…，m；

Step4:同时要考虑到权值系数较大的粒子，也就是重要度较高的粒子选择和粒子的多样性，经过一系列的基因操作，最后决定粒子适应度是通过权值系数大小来判定，权值系数大的则保留下来，并且继续迭代出经过优化的粒子群，完成粒子重新采集[7]。

(5)

Step5：计算a时刻的状态估计；

Step6：令a=a+1，在下一时刻重新转步骤(2)。

3 快速MH变异遗传粒子滤波算法

MCMC(Markov Chain Monte Carlo)是一种随机生成算法，它随机选择后验概率密度函数模型。该算法产生样本速度慢，原因是由于它从全局抽样，因此，V.Cevher[7]提出了一种更好的MH快速算法，该算法以另一种方式生成样本。 这样我们就可以有效地防止粒子运动的速度，并加速全局的收敛。快速MH算法由两部分组成：排序重组和经典MH更新，主要步骤描述如下：

算法1:快速MH更新

1)设定一个粒子集N

2)对于前M-Nt个粒子(新粒子集)中运用算法2得到更新后的前M-Nt个粒子。

3)从更新后的粒子集合中前M-Nt个粒子均匀抽取Nt个候选粒子，重新组合成大小为M的粒子集合。

算法2：经典MH更新是随机变量φ的样本，它是通过构造一个平稳分布为π(φ)的马尔可夫链来获得的，通过这些样本就可以作各种统计推断，其主要步骤描述如下：

1)初始化目标分布函数π(φ)和随机值φ；

2)产生一个候选φ′，根据一个特定的转移函数(建议密度)进行扰动，如:

g(φ,φ′)=g(|φ-φ′|)∝exp[(φ-φ′)2/(2γ2)]

(6)

3)计算接受率:

B(φ,φ′)=min[π(φ′/x)g(φ′,φ)/(π(φ/x)g(φ,φ′)),1]

(7)

4)按照u-U(0,1)采样；

5)如果u≤B(φ,φ′)，则φk+1=φ′，否则，φk+1=φ。

用跳转频度Tjump来选择是否需要排序重组，因此可以控制排序重组的频度。经过快速MH更新后，后验概率大的粒子作为初始随机值产生新粒子的可能性更大，可以产生更符合分布函数π(φ)的φ′来取代初始值φ。在快速MH的遗传突变重采样算法执行期间，可以对运算算法进行修改，以使粒子更符合状态的概率密度函数的分布。 新遗传算法的实现的重采样步骤为：

1)编码方式：PF状态估计是连续参数进行优化的过程。通常采用二进制编码，但是在编码过程中，有点缺陷就是会造成编码串过长，并且需要再解码为实数，整体计算运行时间长，影响学习的精度。为了克服上述缺点，本文直接用实数矩阵方式，有利于遗传算子的对应位置操作，大大简化计算过程，加快运行速度。

3)遗传算子:

(1)选择：用赌轮法选择，适应度大的粒子被选择的概率大。

(2)交叉：以概率Pc作父辈染色体的交叉，交叉算子采用算术相加[7]。

快速MH变异遗传重采样流程，如图1所示。基于快速MH变异的新遗传粒子滤波完整算法描述如下：

算法3：新遗传粒子滤波器算法(NGRPF)

2)令k=1:K进行滤波更新：

粒子状态预测与更新:

(8)

粒子权值归一化:

(9)

计算:

(10)

判断是否需要重采样。

新遗传重采样。

4 快速MH变异遗传粒子滤波的无线传感器网络目标跟踪算法

应用上述算法解决衰败现象，其基本思想是：粒子滤波产生的每一个粒子都被视为一个染色体，利用快速MH变异遗传算法对样本集进行了优化。

MHGAPF算法优化的整个过程如图2所示。

图2中，F(t)代表粒子编码的第t代种群，Q(t)代表第t代的所有构造染色体种群。MHGAPF算法优化实现过程如下：

4)反复执行算法：

While( 条件为真一直执行，不满足终止条件)do //最终用遗传中最大迭代数为结束条件Begin

②t=t+1；

③先后依次测量种群F(t)中的个体，以获得一组状态Q(t) ；

④针对每个状态计算其适应度；

改变方法，快速MH变异粒子迭代更新总体P(t)以保持总体F(t+1)；

⑤保存最佳个体及观察其状况。

End

下面是算法的具体实行步骤:

①全部传感器节点向执行MHGAPF以定位和跟踪目标的Sink节点发送测量信息。本文中假定不同传感器节点之间的观测值是无关联的，相互独立的。具体算法实现如下：

②粒子更新和权值更新

Fori=1,…,K；

1)收到M个独立量测。

2)Fori=1,…,N；

(11)

归一化权值:

(12)

③快速MH变异粒子优化；此方法的优化过程允许从最佳重量的样本中获得样本集。

④对状态进行估计；

(13)

对协方差进行估计：

(14)

5 算法仿真与分析

本文在进行分析时，只考虑单个目标在有效的检测区域内做匀速直线运动。其中，它的测量方程和运动状态方程如下：

(15)

针对PF滤波算法、GAPF滤波算法和MHGAPF滤波算法3种方法进行实验，实验中具体的做法是在保留最高重要度权值的基础上，经过遗传操作后，某一部分的新权重应大于原始值，否则在下一次迭代过程中将保留原始粒子。

衡量跟踪精度通常用均方根误差来计算值的大小来表示，它是反映目标跟踪算法中跟踪效果好坏的指标，本文的采用3种算法：普通粒子滤波算法、遗传粒子滤波算法、MHGAPF遗传粒子滤波算法，通过它们的跟踪均方根误差计算数值和对比曲线来分析性能好坏,跟踪均方根误差计算公式如下式[8-10]，

(16)

在仿真实验中比例取0.71，通过运行，得到本次实验中3种算法的状态跟踪曲线如图3所示。

由图3可知, PF算法和MHGAPF算法远离目标。PF算法和GAPF算法跟踪误差大，PF算法跟踪精度最低，其次是GAPF算法。PF算法和GAPF算法不能精确跟踪，而本文提出的MHGAPF算法则能够补充上面的不足，可以能很好地实现稳定跟踪，效果很明显。MHGAPF算法比PF算法、GAPF算法更为接近目标，跟踪精度稍高些，可以能很好地实现稳定跟踪，效果很明显。通过图4和图5可以发现，PF滤波的速度估计误差最大，GAPF 滤波效果稍好些，MHGAPF能最好地估计目标运动速度。PF，GAPF、MHGAPF 算法运行时间分别是50.16 s,42.18 s和29.16 s。全面比较后，跟踪精度与粒子数有关，粒子数越多，跟踪精度越高，但随着粒子数的增加，时间越长，因此，减少工作时间。MHGAPF算法计算时间最短。由于其本身的优越性，MHGAPF算法可以提高实时监控的有效性。本文3种滤波算法PF算法、GAPF算法和MHGAPF 算法分别进行了120次仿真试验，可以得出目标位置和速度的均方根误差，3种滤波算法的均方根误差由表1所示。

表1 3种滤波算法的均方根误差

由表1可知，与GAPF算法和PF算法相比MHGAPF算法位置和算法速度的中均方根误差最低，其中PF算法的跟踪精度最低，MHGAPF跟踪精度最高，进一步表明MHGAPF算法具有良好的跟踪性能。

由图6可知，本文算法的跟踪精度优于PF 和GAPF算法。由于MHGAPF是通过服从状态后验概率分布的粒子集合来进行状态估计，对于非高斯噪声的干扰不敏感，因此其曲线并没有较大的波动。而标准PF的RMSE曲线却变得更加曲折，且跟踪精度变低。

6 结束语

本文提出了一种基于MH快速变异的新遗传粒子滤波算法，并将其用于目标跟踪和无线传感器检测。 该算法用于粒子采样，提出了一种快速的MH算法来生成变异粒子，并且最优粒子在初始粒子集中的较小范围内移动。 由于根据后验概率密度函数创建新粒子，因此可以保证新添加的粒子的效率，并在保留优良粒子的基础上实现粒子的多样性，从而滤波功能得到极大改善。理论分析和实验结果表明，该方法能有效地解决粒子退化问题，该算法的整体滤波效果优于普通粒子滤波，在速度、效率和功能上都有明显的优势，能够较好地应用于实时跟踪[11-12]。本文提出的算法具有较高的实用价值，因此，能够更好地适应于工程应用。但是，粒子滤波算法本身计算量比较大，耗费能量多，这对于能量有限的无线传感器网络是严峻的考验，解决跟踪精度的问题和同时减少能量消耗的问题，这还需要进一步研究[13-14]。