基于改进布谷鸟粒子滤波算法的WSN目标跟踪

魏 颖，郭 鲁

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

0 引言

无线传感器网络(WSN,wireless sensor network)是当今比较重要的高科技技术，其主要思想是在被测环境中布置相应的无线传感器设备，检测相应的环境数据，并根据检测的信息实时的将信息相融合，构成网络连接。目标跟踪是无线传感器网络的基础研究领域之一，同时也是研究的热点，主要应用于交通监控和战争检测等[1-2]。例如，要实现对一个目标进行及时准确跟踪，可以将其放在布置有无线传感器的环境中，通过无线传感器网络实时采集目标运动中的测量数据，结合跟踪系统的控制，对跟踪目标的位置实时预估，达到准确跟踪的效果。应用WSN进行目标跟踪时，如果监测的准确性不高，系统就可能无法自动集中，导致目标跟踪丢失。粒子滤波(PF,particle filter)通过非参数化的蒙特卡洛模拟实现递推贝叶斯滤波，更新推断系统的下一个状态，精确逼近最优估计值，因此，粒子滤波比较适用于处理目标跟踪等非线性系统的状态估计问题。粒子滤波算法在多次重复迭代后会出现粒子贫化现象，导致目标跟踪的准确性降低。粒子贫化问题一般可以通过改进重要性分布函数或者是改进重新提取粒子来解决，使粒子的多样性得到了保证[3-4]。为了使粒子群优化过程中持续保持具有局部多样性的特性，本文通过对粒子滤波算法加以改进，克服粒子贫化问题，解决了粒子退化的缺陷。

现代粒子滤波领域有多种发展方向，其中群智能优化粒子滤波算法是一个比较新的发展方向。群集智能粒子滤波方法的主要思想是对粒子分布实行反复迭代优化，对于粒子群中低权重粒子不存在放弃问题，从而增加了粒子迭代过程中的多样性，在根本上解决粒子贫化问题。文献[5]在粒子样本更新过程中，将粒子群算法和蚂蚁群算法相结合，实现了信息融合和共享，大大提高了粒子群的全局优化能力。采用文献[6]进行优化的粒子滤波算法应用到自适应粒子群中，对样本粒子数量进行了适应性调整，合理调整了粒子空间分布状态和正确性。

布谷鸟算法(Cuckoo Search)CS算法是剑桥大学学者Yang和Deb提出的一种全局搜索的算法，该种算法实质上是通过对布谷鸟寻窝产卵的行为的模拟过程。CS算法作为最新的智能优化算法之一，还处于早期研究和扩展阶段，与PF融合的报道较少。作为最新的智能优化算法之一，布谷鸟算法还处于早期研究和扩展阶段，关于与PF融合的报道较少。文献[7]表明，布谷鸟算法优化的综合能力比蚂蚁算法，粒子群等算法更强，因而布谷鸟算法和粒子滤波相结合时,智能优化的粒子滤波性能进一步提高,具有重要意义。CS 算法基本上只需要调整宿主发现卵的概率pi的大小，算法较简单，所以通用性很好，鲁棒性较强，但是，该种算法的缺点是在算法的运算后期存在收敛速度慢、精确度低等问题。CS算法的Han 等[8-9]用布谷鸟搜索算法与粒子滤波器(CS-PF)相结合的算法应用于故障检测中，用此来估计测量信号的缺陷轮廓，其结果表明，该算法明显优于单独使用布谷鸟算法，但算法的搜索效率还有待提高。因此，如果将标准的布谷鸟计算方法加入到粒子滤波算法中，通过两者相结合，就不能满足现代高频精密跟踪雷达精度的需要。黄辰等[10]在布谷鸟算法中加入策略差分变异过程，从而改变排队机制，增加优选机制，同时将粒子滤波与改进的布谷鸟算法(ICS-PF)相结合，增加了粒子的多样性，解决了粒子贫化问题。但上述方法中，出现搜索速度慢，精度不高等缺点。为了使布谷鸟算法局部寻优与全局寻优的能力达到相协调的效果，本文对布谷鸟算法进行改进：针对算法中在解向量微调中起主要作用的两个参数，用它们来控制调整算法的收敛速度。一个参数是被宿主鸟发现的概率pi，另一个参数是Le′vy飞行过程中改变步长值α，它们的作用分别是通过对局部随机搜索以获得最优解的能力，通过对全局搜索时以获得种群多样性。将改进的布谷鸟算法和粒子滤波结合，提出一种改进的布谷鸟算法优化粒子滤波方法(ICS-PF, improved cuckoo search algorithm particle filter)，该算法更有效地探索搜索空间算法的局部寻优与全局寻优得到平衡，进一步提高了算法精度。

针对粒子滤波算法粒子退化问题，本文提出了一种改进的布谷鸟与粒子滤波相结合跟踪算法。改进布谷鸟的粒子滤波算法基本思想是在粒子滤波算法的基础上加入改进的布谷鸟算法，代替了粒子滤波重采样过程，通过改进布谷鸟算法中的搜索步长值α和发现外来鸟卵的物种的概率pi的自适应调节，同时在步长更新方程中实时引入函数值的变化趋势，引导粒子整体上向较高的随机区域移动, 有效调整全局探索和局部探索适应能力、改善粒子贫化和局部极值问题，增加粒子群多样化从而提高跟踪性能。结果表明，该算法可以保持种群多样性，收敛速度大大提高。

ICS-PF算法是通过改进的布谷鸟算法优化粒子滤波重采样过程，来实现无线传感器目标跟踪。其主要思想是在传统粒子滤波算法中结合改进布谷鸟算法，增加了粒子多样性，提高了跟踪准确性，减少监测时间，监测能力得到了提高。实验结果表明，该算法具有较好的跟踪性能。

1 粒子滤波算法

粒子滤波主要是采用随机加权随机样本来近似表征的后概率密度u(xg|z1:g)。

(1)

δ是delta 函数。一般通过后验概率密度函数来估计目标状态，按照重要样本的原则,根据重要性分布函数来获得重要性大的即为权值大的粒子。已知的样本分布, 得到粒子对应的重要度(权重)如公式(2)，以及随后的后验概率如公式(3)：

(2)

(3)

通过上述的公式，代入式(2)，可以确加权粒子集的更新过程(4):

(4)

通过公式(3)和式(4)形成基于粒子滤波算法的方法，通过粒子重采样的方法，解决粒子退化问题。重新采样算法将所有粒子的权重值同样更改为1/N,退化问题得到缓解。

但是为了保持样本粒子的集中分布和合理分布功能，通常采用采样算法复制大值粒子，删除小值的方法，结果导致权重大值粒子出现了重复粒子增多的现象，即粒子贫化的现象，最终会导致粒子样本多样性减少，使整个算法的性能变差，因此在重要的采样过程中，为了要保持其多样性，要对粒子进行适当调整。

现有的重新采样算法中，为了保留粒子集中有代表性的粒子，因此，通常只选择高权重值的粒子进行更新，结果使重复性粒子增加较多，粒子群失去多样性，导致出现粒子贫化现象。引入一种改进的布谷鸟算法来取代粒子滤波重采样过程，该算法通过改变改进布谷鸟算法中的搜索步长值α和发现外来鸟卵的物种的概率pi的自适应调节，同时在步长更新方程中实时引入函数值的变化趋势,有效调整全局探索和局部探索适应能力、改善粒子贫化和局部极值问题，增加粒子群多样化从而提高跟踪性能[11]。

2 基于改进布谷鸟算法的粒子滤波方法

目前对于粒子滤波重采样方法，通常保留大权重的粒子，而删除小权重粒子，这样多次迭代后，导致粒子缺乏，出现粒子贫化现象。对于上述问题，本文研究运用改进布谷鸟算法优化了粒子滤波。

标准粒子滤波通常是通过后验概率密度函数对样本进行采样，在此过程中，如果不考虑当前的观测值，结果就会导致发生粒子加权值减小退化。为了克服权重值退化问题，主要通过重采样过程中放弃小权重值粒子来实现。但是这样经过多次重复迭代，最终会导致粒子退化。针对以上问题，本文采用粒子滤波算法结合改进布谷鸟算法的新方法，为了保持粒子分布的合理性，在样本的粒子集在权值更新前，通过全局最优值逐渐引导大部分粒子向于高似然区域移动，同时高似然区域附近不会是全体粒子集。通过此方法优化重采样过程，最终可以改善粒子的分布，提高跟踪精度算法[[12-14]。

布谷鸟搜索CS算法一种适用于全局搜索能力的算法。在文献[15] 对于标准CS假设条件：①每个布谷鸟产卵方式是通过随机选择一个可用的巢穴方式进行的，同时在飞行中执行Le′vy(λ)方式寻找新窝；②能够延续到下一代通常是有高质量卵的巢穴；③巢穴数量是固定的，宿主巢中每个布谷鸟的卵都有可能被宿主鸟发现，被发现后舍弃。在上述假设中，寻找宿主鸟窝的位置和路径的更新公式为

(5)

(6)

改进布谷鸟算法:

CS 算法的优点是参数少，简单，鲁棒性强，易于实现，缺点是算法后期存在搜索速度慢、精度低等问题。为了克服其缺点，通常需要通过优化CS来提高算法的性能[16-17]。为了使布谷鸟算法的全局搜索能力得到提高，在CS 算法中有两个参数Pi和α，它们是用于解向量微调的非常重要的参数，分别用来帮助算法找到全局和局部改进的解，提高算法的收敛速度。在标准的CS算法中，使用固定值设置Pi和α。但是这些值在新一代中不能更改，导致需要更多次迭代才能找到最优解。如果适当调整两个参数值的大小，则能提高算法的寻优能力。设定Pi的值很小，同时设定α的值很大，导致算法迭代次数的明显增加。相反，使得收敛速度变快，最终结果可能无法找到最佳解。所以在算法中调整Pi和α值的大小，达到最佳设定值，可以提高CS 算法的性能，因此，改进的算法使用变量Pi和α。

针对标准布谷鸟算法的收敛速度慢、精度不高等缺点，本文提出改进的布谷鸟算法，一方面通过采用动态发现概率替换原来的固定发现概率，使算法迭代后可获得最优解，另一方面，在步长更新公式中，为了平衡搜索精度和搜索速度之间的关系，引入动态变化的函数值的变化趋势。

改进的布谷鸟算法中采用动态发现概率Pi后，用数值s与发现概率Pi进行比较，其中s为[0,1]之间的随机数，通过在寄主鸟发现鸟蛋的这个过程中，确定是否产生新个体，公式如下：

(7)

通过新的鸟窝位置迭代更新，能够保证个体集合理分布在高似然区域。为了便于跳出局部最优解，在该算法初始迭代前期取较大值，但随着运算的迭代次数的增多，个体质量渐渐增强，这时适当减小Pi的取值，该算法的收敛性可以加快。本文采用余割策略实现Pi动态变化：

(8)

式中，n表示最大迭代次数；c表示当前迭代次数；Pi，max和Pi，min为Pi的控制参数，Pi，max为0.3，Pi，min为0.01。

该算法的步长因子α的取值可以有效的控制搜索范围，步长取值大搜索范围就越大，搜索最优解的速度就越快，反之，很容易偏离最优解的位置。传统的CS算法步长值是完全随机的，理由是它由μ和v共同决定，并且它们都满足正态分布。随机步长的好处是既可以避免陷入局部最优解，又可以满足解的多样性，但在局部范围内步长的m大小不确定，则导致全局算法的收敛速度逐渐变差，影响算法的性能。为了实现算法综合最优性能，前期采用大步长，后期采用小步长，这样可以加快全局搜索速度，同时提高了算法的搜索精度。同时实现步长随着迭代次数的增加而调整其值，根据公式(9)即可实现。

(9)

式中,fmax为最大步长因子,fmax= 0.5;fmin为最小步长因子，αmin=0.01。

因此，调整搜索精度和速度之间的关系后的位置更新公式为：

(10)

在公式中，要同时考虑函数值的变化趋势和位置更新公式的计算。计算的步长跟随变化趋势Δk改变而改变，当Δk变大，步长也变大，保证较快的搜索速度；反之，当Δk变小，步长也变小保证搜索的精度。

改进布谷鸟算法具体步骤如下。

步骤一：进行初始化条件相关参数的设定，算法的终止条件；使用F(x)表示目标函数，其中x=(x1,x2…x3)T,用xq(q=1,2,3…N)表示N个鸟窝初始化种群；

步骤二：随机初始化的鸟窝用x=(x1,x2…x3)T,的N个解来表示，同时计算每个解的目标函数值；

步骤三：当计算迭代次数为c时，通过公式(9)计算出上一代最优解同时保留下来，同时再计算步长因子值，将其步长因子结果带入公式(10)中，更新得到最新解，同时与上一代通过比较函数值大小，保留最优值；

对于算法的收敛性来说，改进的布谷鸟的收敛性比较CS 算法大大提高。通过自适应调整pi和α的值大小，使算法避免因其值过大或过小而导致算法的收敛性降低设定Pi的值很小，若设定α的值过大，迭代次数增加较大，性能变差。反之，导致收敛速度很快，但可能无法找到最佳解。

改进的布谷鸟算法的优点是明显增加种群的多样性。本文算法的方法是在鸟窝更新迭代后，进行算法的改进，通过实时调整概率的大小控制各个时期的种群多样性，具有实时动态性，提高了算法的收敛速度，效果较显著。

3 改进布谷鸟和粒子滤波算法相结合

针对PF算法中的粒子贫化问题，本文将改进的布谷鸟算法来取代原来PF算法中的重采样过程。改进CS-PF 算法具体实现步骤如下：

1)初始化。设定j=0是初始时刻，进行初始样本采样按照分布p(x0) 进行，使用产生的N个粒子作为初始样本{xg(0)}(g=1,2,3…N)，xg(j)服从重要性密度函数。

xg(j)_p(xg(j)|xg(j-1),z(j))

(11)

3)采用改进的CS 来优化粒子进行全局搜索。

①进入优化的初始粒子

{i(j)}={xg(j)}(i=1,2,…,N)

(12)

②在CS算法中加入粒子样本，根据步骤1～5

每次重复都能得到新的粒子集合，鸟窝离最佳位置越近，步长就越小，而鸟窝离最佳位置越远，步幅就越大。因此，每一次更新移动步长都是根据上一次重复的结果而进行的，提高了搜索速度和精度。改进后的布谷鸟算法采用的适应度函数是:

(13)

③改进的CS搜索算法用来执行粒子滤波重新采样过程。

4)计算新粒子的重要性权值，同时进行归一化处理。

(14)

5)输出粒子状态,即求ICS-PF 后输出粒子的均值。

对于ICS-PF收敛性来说，首先ICS-PF算法每重复一次就使群体有一次最佳位置，这样可以使随机算法具有收敛性。ICS-PF算法经过多次重复迭代后，使得鸟窝位置的群体序列具有更好的状态，即最佳状态。因此，无法连续无限次搜索全局最佳解的可能性为0。因此，ICS-PF算法会收敛到全局的最佳值。

对于ICS-PF时间复杂度来说，粒子滤波时间复杂程度主要受两个因素影响：一个是初始化种群粒子数，另一个是重新采样粒子集,通常来说，时间复杂度与粒子数成比例，粒子也多，复杂度越高。另一个影响算法计算效率的因素是宿主发现卵的概率为pi和随机步长α。在通常情况下，给定个体的目标函数执行时间较小，因此ICS-PF的时间复杂度较低。

4 仿真实验

4.1 基础性能测试

选择过程模型和测量的非静态增长模型，模型如下:

8cos[1.2(u-1)]+w(u)

(15)

(16)

在这里，w(u)和v(u)是零均值高斯噪声,系统噪声方差Q=1,x(u)是系统u时刻的状态，z(u)是系统u时刻的测量值。初始状态x=0.1,过程噪声和测量噪声都是1，将其应用于PF、CS-PF和ICS-PF用于非线性系统的状态估算、跟踪。

平方根差公式为:

(17)

4.1.1 精度测试

1)当粒子数为N=30，Q=1时，模拟结果如图1和图2所示。

图1 滤波状态估计

图2 滤波误差绝对值

2) 当粒子数为N=100，Q=1时，模拟结果如图3和图4所示。

图3 滤波状态估计

图4 滤波误差绝对值

从图1～4可以看出，3种滤波算法相比，改进布谷鸟粒子滤波算法效果最好，得到了优化。

由于ICS-PF 在PF的基础上的原因，ICS-PF模拟以PF为基础的个体或群体寻找布谷鸟产卵与CS-PF相比，ICS-PF可精确控制全局优化能力和局部优化能力其算法具有更高的状态值预测准确度，从而优化粒子在状态空间的分布，可以粒子分布更合理，使用更少重复迭代次数，达到寻优，用较少的粒子并进一步提高粒子过滤的精度。从表1可以看出，ICS-PF的运算精度在粒子数为20时，就高于PF算法粒子数为100的运算精度，并且运算时间与CS-PF差不多。ICS-PF同时还可以提高综合性价比的滤波精度和保持较快的计算速度。

从表1还可以看出，如果粒子数为20和50，则PF、CS-PF、ICS-PF三种算法相比较，ICS-PF的精确度有了很大的提高，但当粒子数为100时，ICS-PF的准确度没有太大的提高。这是因为当粒子数量非常少时，各粒子的平均权重较大，各粒子的质量会对预测结果产生很大影响。这就体现了对ICS-PF的全局优化能力和局部优化能力的精确控制优势。但是，当粒子数量较大时，各粒子质量的平均重要度就会降低，因此ICS-PF的自适应探索机制的优势不会很大。这表明ICS-PF非常适合于快速、精确的预测，如果粒子数量少，如雷达、无线传感器目标跟踪等。

表1 实验结果对比

4.1.2 粒子多样性测试

在ICS-PF滤波估算中，为测定样本的多样性，得出了以下结果：

当g=10,g=30,g=90时，PF,CS-PF,ICS-PF的粒子分布如图5～7所示。从5～7图可以看出，PF、CS-PF、ICS-PF算法相比，标准PF算法按重复采样进行的滤波过程中，粒子的多样性明显减少。在这个阶段，大部分粒子只集中在几个状态值上，可能会严重影响滤波器的估计性能。而在CS-PF、ICS-PF的情况中，大部分粒子集中向高似然区域移动，与此同时，部分粒子在低相似性区域被合理地保存了下来，其中，ICS-PF算法合理优化了每个阶段的粒子分布，具有粒子相对最集中的优点，利用ICS-PF采样可以有效地清除每个阶段多余的粒子，并稳定地控制粒子的规模。ICS-PF算法的情况比CS-PF算法的情况更为明显，ICS-PF粒子在空间的分布更加广泛,以粒子群体目前的最佳位置为目标，以提高整个群体的重复搜索效率和粒子分布的多样性。本文提出的算法大大提高了粒子的多样性，而使用CS-PF算法，粒子的多样性略有增加。ICS-PF证明了通过减小粒子大小和布谷鸟算法优化稳定性，可以提高计算效率。结果表明，虽然ICS-PF采样可以减少粒子的数量，但根据动态粒子数，ICS-PF采样可以去除不必要的粒子，改进布谷鸟算法可以获得更好的优化性能。

图5 g=10时粒子状态分布情况

图6 g=30时粒子状态分布情况

图7 g=90时粒子状态分布情况

4.2 WSN目标跟踪性能测试

本文在进行性能测试分析时，主要针对单个目标做匀速直线运动，在设定的有效监测范围内。其中，它的测量方程和运动状态方程如下：

(18)

通常反映目标跟踪算法性能好坏用跟踪精度的大小来表示，通常用平均平方根误差来表示。本文采用3种算法分别为PF算法、CS-PF算法、ICS-PF算法，通过它们的平均平方根误差的计算数值和比较曲线分析性能。平均平方根误差跟踪的计算公式为(15～16)。

(19)

在仿真实验中，取比值为0.72，在本实验中得到跟踪轨迹曲线图，如图8所示。

如图8所示，ICS-PF算法相比较PF算法和CS-PF算法更接近目标的真实轨迹。PF算法和CS-PF算法跟踪性能不够理想，效果较差，不能实时准确跟踪，但本文提出的ICS-PF算法更接近目标，跟踪精度、性能更好，效果显著，可以实现稳定的准确的跟踪。如图9～10所示，ICS-PF算法跟踪精度最高，跟踪误差最小，其次为CS-PF算法，PF算法的跟踪精度最低，PF算法与CS-PF算法的跟踪误差较大。同时从图9和图10可以看出，PF的滤波速度估计误差最大，CS-PF比PF的滤波效果好些，ICS-PF滤波误差最小，效果最好，最能推算目标运动速度。PF、CS-PF和ICS-PF算法的运行时间分别为50.36秒、35.32秒和28.36秒。全面比较后，通过ICS-PF控制，合理兼顾了全局寻优能力和局部寻优能力，使粒子趋于更合理的分布，提高了滤波的精度，提高了跟踪性能。本文用3种滤波PF算法、CS-PF算法和ICS-PF算法分别进行了100次模拟实验，得到目标位置和速度的平均平方根误差。通过对比分析，评价算法的性能，3种过滤算法的平均平方根误差如表2所示。

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

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

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

在表2中ICS-PF算法和PF算法、CS-PF算法相比,其中跟踪精度最低是PF算法,其次是PF算法CS-PF算法，ICS-PF的跟踪精度最高,可以看出具有较好的跟踪性能。

从图11可以看出，本文所提出的跟踪算法的准确性优于PF和CS-PF算法。由于ICS-PF是根据状态后验的概率分布的粒子集合来推测状态，所以对非高斯的杂音没有太大反应，因此曲线几乎没有变化。标准PF算法的RMSE曲线弯曲程度最明显，精度更低。实验结果表明，本文提出的改进布谷鸟粒子滤波的无线传感器的目标跟踪方法。主要思想是用改进的布谷鸟算法取代粒子滤波的重采样过程，通过改进的布谷鸟算法代替粒子滤波的重采样过程，主要通过改进布谷鸟算法中的搜索步长值α和发现外来鸟卵的物种的概率pi的自适应调节，同时在步长更新方程中实时引入函数值的变化趋势,使粒子向整体上较高的随机区域移动，有效调整全局探索和局部探索适应能力、改善粒子贫化和局部极值问题，增加粒子群多样化从而提高跟踪性能。改进布谷鸟粒子滤波算法重采样方法可以防止粒子的退化,增加粒子的多样性,减少跟踪误差,可以减少算法的运行时间,实时追踪性能大幅提高。ICS-PF算法的计算时间最短。与CS-PF算法和PF算法相比，ICS-PF算法的位置和速度的平均平方根误差最小(位置0.030 6、0.021 3、速度0.025 3、0.010 2)，ICS-PF的跟踪精度最高，表明了ICS-PF算法跟踪性能较好。

图11 3种算法的跟踪精度

5 结束语

针对粒子滤波中的粒子贫化问题和采用群体智能优化算法后的计算效率低下问题，本文提出了一种改进布谷鸟粒子滤波算法，用于无线传感器网络中的目标跟踪。通过修改后的pi和α值来提高布谷鸟算法性能，通过ICS搜索策略代替粒子滤波重采样阶段，均衡局部和全局优化能力，避免粒子样本的贫化。采用改进的布谷鸟算法，使粒子模仿布谷鸟个体，在全局搜索范围内更精确地分布在最佳位置，即实际值附近。采用改进的布谷鸟算法替代粒子滤波重采样过程，使整体粒子向更高的随机区域移动，有效调整全局探索和局部探索适应能力、改善粒子退化和局部极值问题，提高无线传感器网络目标跟踪性能。由于后验概率密度函数通过不断更新产生新粒子，维持较优粒子，持续保持了粒子的多样性，有效缓解样本枯竭问题，从而大大改善了滤波功能。结果表明，该算法的整体滤波效果比普通粒子滤波效果增强，可很好地实现准确的目标跟踪，具有一定的实用价值。但是，粒子滤波算法具有运算量较大，能耗较大的缺点，需要在有限能量无线传感器网络、高精度测试、跟踪问题、能耗等方面进行深入研究[18-20]。由粒子滤波不断重复迭代更新，改进布谷鸟算法使粒子的分布更为集中在最优点且分布合理，可以稳定控制粒子集规模在较小的范围内，提高粒子滤波的计算精度和效率。ICS-PF算法可实现粒子间的信息交换可以有效地压缩粒子的规模，与人工智能进一步结合跟踪领域将得到更好的发展和应用。