基于量子遗传粒子滤波的无线传感器网络的目标跟踪算法的研究

魏 颖，郭 鲁

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

0 引言

无线传感器网(WSN,wireless sensor network)是21世纪最重要的前沿技术之一，目标跟踪是无线传感器网络的一个主要研究领域，如交通监测，捕捉战争状态等。例如，将一个测试目标放置在布置传感器的地点内，它运动时，通过传感器测量，然后反馈到跟踪系统，以此接近预估目标的位置[1]。粒子滤波(PF,particle filter) 是一种蒙特卡罗算法，它是基于递推计算的序列算法，不受非线性等因素的限制，适用于所有的测量模型以及状态转换模型，基本思想是在当前系统状态分布中随机抽取一些加权的粒子，通过计算对系统的下一个状态进行更新和估计，所以在无线传感器的目标跟踪中，上述方法比较适合，但不足之处是存在粒子群出现退化现象[2]。如何对多个传感器的测量值进行有效的处理，以实现对目标的精确跟踪。粒子滤波算法在多次迭代后会退化，即只有少数粒子具有较大的权重，而大多数粒子的权重很小，几乎为零，这会消耗大量的时间。这些时间消耗是在大多数权重小的粒子上，这些粒子对系统状态的评估几乎没有影响。这类问题通常下列的方法解决：首先是改善意义重大函数，其次是对粒子重新采样。粒子回收是处理粒子衰变的重要手段。粒子累积分布、系统采样和节余采样是常用的重采样算法。以上的方法主要改善粒子退化效率来解决粒子降解的问题。在新的取样之后，多次选择重要性高的粒子，因此，粒子的多样性已经失去了一些，即所谓的粒子缺失。那么在跟踪目标时，一旦监测的准确性不高或目标丢失，系统很可能不能自动会聚。本文通过提供一种基于遗传算法的再采样策略来解决粒子退化问题，同时存储有用的粒子。利用进化机制保证粒子群优化过程中局部的多样性，并且处理粒子算法中粒子退化的缺陷。本文对于粒子滤波跟踪算法的粒子衰退问题给出了一种量子遗传的粒子滤波跟踪算法[3-5]。量子遗传算法(QGA,quantum genetic algorithm) 的染色体由量子密码决定。因此，通过量子门户用于在重叠态上执行进化操作。结果显示，算法能够保护种群的多样性，节省时间。计算通过量子并行性加速收敛速度。

为此，文章应用基于量子遗传粒子滤波(QGPF,quantum genetic particle filter) 的无线传感器目标跟踪算法[6]。把量子遗传算法加入到传统粒子滤波中，用来增加样品组的多样性，减少样品组的衰退。缩短监测时间和提高监测能力后续行动。实验结果表明，算法具有显著的优点。

1 粒子滤波算法

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

(1)

(2)

(3)

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

(4)

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

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

2 遗传粒子滤波算法

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

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

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

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

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

(5)

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

Step6：令a=a+1，在下一时刻重新转Step2。

3 量子遗传粒子滤波算法

量子遗传粒子滤波算法(QGA)是在算法中加入遗传算法同时在计算的概率变化算法结合量子计算概念和理论基础上，更增强了优点，保护了良好的种群多样性。它对染色体进行编码通过量子比特的概率深度计算，从而达到了使染色体能够体现出多个状态的重叠。然后通过量子旋转门和非量子门更新染色体，以优化种群。QGA群体由比特编码的量子染色体组成。量子遗传算法中较小的信息单位是量子比特。与传统的比特相比，它不仅可以是0或1的状态，也可以是重复出现的状态。因为这个原因具有多样性。个体数为n，则用长度为m的种群代表量子染色体。

(j=1,…,n)

(6)

(7)

式中,量子转子为：

(8)

4 基于量子遗传粒子滤波(QGPF)的无线传感器网络目标跟踪算法

QGPF算法优化的整个过程如图1所示。

图1 QGPF算法优化过程

图1中，F(t)代表量子编码的第t代种群，Q(t)代表第t代的所有构造染色体种群，L(t)代表第t代量子旋转门。QGPF算法优化实现过程如下：

4)反复执行算法。

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

(1)t=t+1 ；

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

(3)针对每个状态计算其适应度；改变方法，利用量子门L(t)迭代更新总体P(t)以保持总体F(t+1)；

(4)保存最佳个体及观察其状况。

End

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

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

2)粒子更新和权值更新

Fori=1,…,K；

1)收到M个独立量测。

2)Fori=1,…,N；

(9)

归一化权值:

(10)

3)量子遗传优化；此方法的优化过程允许从最佳重量的样本中获得样本集。

4)对状态进行估计；

(11)

对协方差进行估计：

(12)

5 算法仿真运行和分析

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

(13)

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

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

(14)

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

图2 目标运动轨迹比较

图3 目标运动速在x轴的分量比较

图4 目标运动速度在y轴的分量比较

由图2可知,PF算法和GAPF算法远离目标。QGPF算法更为接近目标。但PF算法GAPF算法比QGPF 算法跟踪精度稍低。PF算法和GAPF算法不能精确跟踪，跟踪误差大，跟踪精度明显降低，而本文提出的GAPF算法则能够补充上面的不足，能很好地实现稳定跟踪，效果很明显。PF，GAPF、QGPF 算法运行时间分别是56.16 s,46.71 s和30.46 s。全面比较后，QGPF算法计算时间最短。由于其本身的优越性，QGPF算法可以提高实时监控的有效性。通过图3和图4可以发现，跟踪精度与粒子数有关，粒子数越多，跟踪精度越高，但随着粒子数的增加，时间越长，因此，量子遗传粒子滤波可以减少所需粒子数，减少工作时间。本文改进算法的跟踪均方误差小于PF和GAPF算法，由于QGPF算法引入了上述方法，因此它可以有效地提高算法的效率。在样本改进了粒子的多样性，提高了算法的可追溯性。使用PF算法、GAPF算法和QGPF 算法分别进行了99次仿真试验，可以得出目标位置和速度的均方根误差，3种滤波算法的均方根误差由表1所示。

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

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

6 结束语

本文涉及的量子遗传粒子滤波的无线传感器网络目标跟踪算法，该算法用于粒子采样，粒子恢复和粒子多样性是在保留优良粒子的基础上进行的，理论分析和实验结果表明，该方法能有效地解决粒子退化问题，为了避免粒子的稀缺性，该算法的整体滤波效果优于普通粒子滤波。它只需要少量的粒子，其效果相当于大多数粒子的普通粒子过滤的精度。同时，显著提高了颗粒过滤器算法的计算速度。有效缩短了微粒过滤器与实际应用的距离。并且跟踪的正确率会保持稳定的同时，粒子的数量也会降低，以此减少运行时间，能够较好的应用于实时跟踪。

与过去的跟踪算法相比，该算法在速度、效率和功能上都有明显的优势。本文提出的算法具有较高的实用价值。因此能够更好的适应于工程应用。本文将 QGA 引入 PF 中，提高了粒子的多样性，有效地解决了粒子滤波严重的退化问题。同时由于量子的在运行时具有并行性，其跟踪的实时性有了大大提高。通过目标在有效监测区域内仿真运行实验证明，能有效精准跟踪目标。但是，粒子滤波算法本身计算量比较大，耗费能量多，这对于能量有限的无线传感器网络是严峻的考验，解决跟踪精度的问题和同时减少能量消耗的问题，这还需要进一步研究。