改进的被动多传感器数据关联算法*

惠军华，王朝英，关冬冬

(1.空军工程大学 信息与导航学院，陕西 西安 710077； 2.西安通信学院，陕西 西安 710106)

改进的被动多传感器数据关联算法*

惠军华1,2，王朝英1，关冬冬1

(1.空军工程大学 信息与导航学院，陕西 西安 710077； 2.西安通信学院，陕西 西安 710106)

针对被动传感器数据关联的问题，提出了一种基于改进量子粒子群算法的被动传感器数据关联方法。算法采用分层关联的思想，首先通过构造角度检验统计量进行方位粗关联，然后将余下的候选关联组合转化为三维分配问题，继而提出了一种改进的量子粒子群算法求解此问题。仿真实验表明，该算法能够快速消减候选关联集合的数目，快速、准确地排除虚假定位点。

数据关联；被动传感器；量子粒子群算法；分层关联

0 引言

在被动跟踪的情况下，由于被动传感器(如电子支援措施，红外等)本身不发射电磁波，仅通过接受以目标为载体的发动机、通信、雷达等所辐射的红外线、电磁波，或目标所反射的外来电磁波来探测目标的位置，属于非协作测量，测量误差通常比传统雷达测量误差大，因此在被动传感器数据关联中面临很大的不确定性[1-2]。测向交叉定位[3]是无源定位系统中应用较多的一种，它通过高精度的测向设备在多个观测站对目标进行测向，各个测向线的交点就是目标的位置。在复杂环境下采用2个以上的观测站对多个目标进行测向交叉定位时，不同的测向线相交将产生大量虚假定位点，而且虚假定位点的数量随着观测站和目标数目的增多而急剧增多[4]。如何快速、准确地排除这些虚假点一直是多站测向交叉定位研究中的难点。

针对此问题，许多学者进行了研究。文献[5]提出了一种基于多维分配算法的被动数据关联算法，它是一种静态最大寻优数据关联算法，通过建立候选分配树，确定每一候选关联代价，然后寻求一种总关联代价最小的分配方案。文献[6]提出了一种分层的快速数据关联算法，采用统计量检验筛选、分层搜索的方法找出正确关联。文献[7]首先采用方位数据粗关联的方法结合基准线最小距离法排除部分虚假定位点，再利用三维分配算法进行方位细关联，对规模较小的候选关联集求近似最优解。本文在文献[5]和文献[7]的启发下，提出了一种基于量子粒子群的被动数据关联算法。算法采用分层关联的思想，首先利用角度构建检验统计量完成第1层关联，排除大部分的虚假定位点组合，然后将余下的候选关联组合转化为三维分配问题进行方位精关联，继而提出了一种改进的量子粒子群算法求解此问题，最后进行了仿真实验。

1 关联模型

1.1 方位粗关联

如图1所示，先作如下假设：

图1 关联模型Fig.1 Correlation model

(1) 设站S1和站S2为主站，站S3为辅站，(θ1j,θ2k,θ3l)为一候选关联；

(2) 设(x,y)为站S1和站S2的方位角θ1j和θ2k在Oxy平面的交叉定位点P；

(3) 设θ为定位点P与站S3之间所成的方位角，则

(1)

(2)

(3)

经过简单的数学运算，可得

(4)

式中：

(5)

(6)

(7)

式中：σθ1j，σθ2k，σθ3l分别为3个传感器的方位角测量均方根误差。αjkl近似服从自由度为1的χ2分布。当检测统计量αjkl低于由χ2分布获得的某一检测门限时，则认为候选关联可能属于同一目标，予以保留；否则，则认为是一种错误组合，予以删除。

1.2 方位细关联

对满足检验统计的候选集合计算其相应的关联代价

(8)

式中：θi为三观测站的测量值；

(9)

对被动传感器1测得的其他方位角重复上述步骤，则可得到C1j,kl，j=2,3，…,p。进而可将关联问题转换为三维分配问题，即求出使下面代价函数C最小的关联

(10)

满足约束条件：

(11)

式中：

这样，数据关联问题就转换为三维分配问题。下面采用量子粒子群算法求解上述三维分配问题。

2 量子粒子群算法

2.1 PSO(粒子群)基本原理

基本粒子群算法(particle swarm optimiza- tion, PSO)[8]是在1995年由美国社会心里学家James Kennedy和电气工程师Russe Eberhart共同提出的，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利用生物学家Frank Heppner的生物群体模型。与其他进化类算法相类似，也是用“群体”与“进化”的概念，同样也是依据个体(微粒)的目标函数值大小进行操作。区别在于，微粒群算法将每个个体看作是在维搜索空间中的一个无重量无体积的微粒，并在搜索空间以一定的速度飞行，飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。目前，有关PSO算法的研究大多以带惯性权重的PSO算法为基础进行扩展，为此将带惯性权重的PSO算法称为标准PSO算法。

设微粒群粒子总数为N，每个粒子的维数为D，xi=(xi1,xi2,…，xid)和vi=(vi1,vi2,…,vid)分别为粒子的当前位置以及当前飞行速度，粒子i所经历的最好位置为Pi=(Pi1,Pi2,…，Pid)，也就是粒子i所经历的具有最好适应值的位置，即个体最好位置(pbest)。Pg=(Pg1,Pg2,…,Pgd)为粒子群中所有粒子经历的最佳位置(gbest)(gbest是pbest中最好值)，则标准的PSO算法进化方程为

vid(t+1)=w·vid(t)+c1rand()·(Ppbest-xid(t))+

c2rand()·(Pgbest-xid(t))，

(12)

xid(t+1)=xid(t)+v(t+1)，

(13)

式中：w为惯性权重，可以是固定值，也可以是线性变化的；c1和c2为待定常数，通常在(0,2)范围内取值；r1和r2为2个独立的随机数。

式(12)第1部分称为记忆项，表示上次速度大小和方向的影响；第2部分称为自身认知项，表示粒子的动作来源于自己经验的部分；第3部分称为群体认知项，反映了粒子间的协同合作和知识共享。

根据对粒子收敛行为的分析，要保证算法的收敛性，每个粒子必须收敛与各自的P点，这是由粒子的追随性和粒子群的聚集性决定的。在整个收敛过程中，在P点处实际上存在某种形式的势能场吸引着粒子，这正是整个粒子群能保持聚集性的原因。但在标准的PSO系统中，粒子的收敛是以轨道的形式实现的，并且粒子的速度总是有限的，因此在搜索过程中粒子的搜索空间是一个有限的区域，不能覆盖整个可行的空间。所以标准PSO算法并不能保证收敛到全局最优解。

2.2 量子粒子群优化

2004年，Sunday从量子力学的角度出发，认为粒子具有量子行为，并根据这种模型提出了基于量子行为的粒子群优化算法[9]。在量子空间中，粒子在整个可行解空间中进行搜索，因而量子粒子群优化(quantum-behaved particle swarm optimization,QPSO)算法的全局搜索性能远远优于标准PSO算法[10]。粒子的位置由波函数ψ(x,t)决定：

(14)

式中：Q表示粒子在时刻T出现在(x,y,z)位置的概率，通过蒙特卡罗方法的转换，将量子状态转换成传统状态，并经过演变最终得到粒子位置的迭代公式。由此将粒子的速度和位置信息都归结为一个参数，算法方程如下：

(15)

式中：pbest为个体极值；gbest为全局极值；mbest为中值最优位置；M代表群体中所含粒子数；α1，α2，u为(0,1)之间的随机数；β为系数创造力。在迭代过程中，±是由(0,1)之间产生的随机数决定，当产生的随机数大于0.5时取-，其余取+。

量子粒子群算法只用一个参数β决定粒子的收敛速度和位置，能够克服一般粒子群算法在收敛性能上的缺陷[11]，其具有如下几个优点：

(1) 量子系统是一个复杂的非线性系统并且符合状态重叠原理，因此量子系统比一个线性系统具有更多的状态。

(2) 量子系统是一个与典型的随机系统远远不同的不确定性系统，在系统中粒子能够以某一确定的概率出现在搜索空间中的任意一个位置。

(3) 在传统的PSO算法中，有限的搜索范围将粒子限制在了一个固定的区域，而在QPSO算法中，粒子能够以某一确定的概率出现在整个可行的搜索空间中任意一个位置，甚至是一个远离点的位置。而这样的一个位置可能比当前群体中的具有更好的适应值。

在PSO算法搜索的后期，粒子群会向局部最小或全局最小收敛。在这种情况下，如果不通过变异措施来重新初始化粒子群，则粒子群所趋向的那个点即为粒子群算法的最终求解结果的极限值，出现早熟现象。QPSO虽然能够保证算法的全局收敛性，但是在收敛的情况下，由于所有的粒子都向最优解的方向飞去，导致粒子不可避免地趋向同一化(多样性损失)，使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，进而陷入局部最优解。本文在文献[12]的启发下，利用粒子群的适应度方差和空间位置聚集度来判断粒子群是否出现早熟现象，然后根据适者生存的思想，以一定的变异概率对粒子进行变异，从而增加粒子的多样性。下面给出具体的改进方法。

2.3 改进量子粒子群算法

种群中个体的位置决定了个体适应度的大小，因此，可以根据种群中个体的适应度来判断种群状态。

种群的适应度方差定义如下[6]：

(16)

式中：N为种群个体数目；fi为个体i的适应度；favg为当前种群的平均适应度；f为归一化定标因子，其定义如下：

(17)

从式(17)可以看出，种群的适应度方差σ2越小，则种群中个体的聚集程度越大，反之，则聚集程度越小。下面从空间角度反应各个个体相互之间的分布离散程度，即聚集度的定义：

(18)

从式(17)可以看出,随着迭代次数的增加，种群个体之间的适应度越来越接近，且空间位置的聚集度h越来越小，容易陷入局部最优，出现早熟收敛现象。为克服早熟收敛，引入变异算子。首先，构造变异概率Pm，其定义如下：

(19)

式中：σ1为事先给定的阈值，一般趋于0。

根据构造的变异概率，采用竞争策略对粒子进行变异。其基本思想是，认为当种群中2个粒子较为相似时，适应度强的粒子则保存下来，而适应度差粒子则进行变异。从而增加粒子的多样性。

产生一个随机数r⊆[0,1]，如果r

(20)

通过计算相似度，将适应度较差的粒子，采用单性繁殖算子进行变异操作，若个体为xi，则经过单性繁殖后代产生的子代种群为

(21)

式中：

(22)

算法步骤如下：

步骤1：初始化粒子种群维数、粒子规模(个体数)、速度、迭代次数等参数。

步骤2：根据定义的目标函数计算每个粒子的适应度，判断是否满足结束条件，若满足，则转至步骤7，若不满足，则继续向下执行。

步骤3：比较当前最优位置对应的适应值与当前目标函数值。如果当前值最好，则用当前粒子的位置取代pbest，否则，pbest保持不变，重新确定全局最优值gbest。从而完成粒子最优位置和全局最优位置的更新。

步骤4：根据量子粒子的概念，用式(15)更新每个粒子的位置，生成新的粒子群体。

步骤5：根据式(16)～(18)进行粒子早熟判断，同时计算出变异概率Pm。

步骤6：产生一个随机数r⊆[0,1]，如果r

步骤7：判断目标函数是否达到收敛条件或者达到最大进化代数，是则退出，否则转至步骤2。

3 仿真实验与分析

3.1 仿真实验

仿真场景采用文献[7]类似的设置。设二位平面内有3个观测站，站1的坐标为(0,-10)km,站2的坐标为(0,0)，站3的坐标为(10,0)km。各观测站的测角误差为10 mrad。空中有5个目标，分水平编队和十字编队2种情况。

(1) 水平编队情况

目标成水平编队，间距为d，目标1位于(30，55) km,目标2位于(30+d,55) km,目标3位于(30-d,55) km,目标4位于(30+2d,55) km,目标5位于(30-2d,55) km。1 000次Monte Carlo仿真结果如图2所示。

图2 水平编队时各目标的正确关联概率Fig.2 Correct association rate of each target in level formation

(2) 十字编队情况

目标成十字编队，间距为d，目标1位于(30,55)km,目标2位于(30+d,55)km,目标3位于(30,55-d)km,目标4位于(30-d,55)km,目标5位于(30,55+d)km。1 000次Monte Carlo仿真结果如图3所示。

图3 十字编队时各目标的正确关联概率Fig.3 Correct association rate of each target in cross formation

为体现算法的优越性，将本文算法与最大似然法进行比较，结果如表1所示。

3.2 结果分析

(1) 图2给出了水平编队时，各目标在不同间距条件下所得到的正确关联概率。从图中可以看出，正确关联概率随着目标间距的增大而逐渐增大，同时，在相同目标间距的情况下，正确关联概率与目标的位置有一定的关系。通常情况下，在目标间距较小时，居中的目标的正确概率较小，而在目标间距较大时，距离观测站最远的目标的关联正确率低。一般的规律为,当目标间距较大时,距观测站较远的目标,正确关联率较低;当目标间距较小时,居中的目标的正确关联概率较低。

(2) 图3给出了在十字编队飞行时，各目标在不同间距条件下所得到的正确关联概率。与图1相比可以看出，与水平编队时相比，目标进行十字编队时,正确关联概率略低。

(3) 表1给出了水平编队飞行时，最大似然法和本文算法一次独立运行所需的时间。从表1可以看出，由于本文算法采用了先粗关联，再细关联的分层关联算法，能够排除一部分虚假候选关联，减少了计算量。而最大似然法由于所有的候选关联都参与目标状态更新，增加了计算量，运行时间较常。

4 结束语

本文对被动传感器系统中的数据关联问题进行了研究，提出了一种基于量子粒子群算法的被动传感器数据关联算法，较好地解决了被动数据关联问题。为排除虚假点，文中给出了分层关联的具体方法，将数据关联问题转化为三维分配问题，然后提出了一种改进的量子粒子群算法求解此问题。仿真实验表明，该算法是一种关联概率高、关联速度快、不容易陷入局部最优的关联算法，具有一定的应用价值。

[1] 修建娟,何友,王国宏,等.被动定位系统中的方位数据关联[J].系统工程与电子技术,2003,25(3):280-283. XIU Jian-juan,HE You，WANG Guo-hong,et al. Bearing Measurements Association in Passive Location Systems[J]. Systems Engineering and Electronics, 2003,25(3):280-283.

[2] LI Bin-bin,WANG Zhao-ying,WEN Xi. Fast Data Association Algorithm for Passive Sensors[J]. Chinese Journal of Sensors and Actuators,2008,21(7):1160-1163.

[3] 汪珺.测向交叉定位技术[J].电子科技,2011,24(7):129-132. WANG Jun. Crossing Location Technology[J]. Electronic Science and Technology,2011,24(7):129-132.

[4] 王成，李少洪，黄槐.测向交叉定位系统的多目标测量数据关联[J].系统工程与电子技术，2002，24(9)：104-106. WANG Cheng, LI Shao-hong, HUANG Huai. Multi-Target Measurement Data Association for Passive Location Systems Based on Direction of Arrival[J]. Systems Engineering and Electronics,2002,24(9): 104-106.

[5] PATTIPATI K R, DEB S, Bar-Shalom Y, et al. A New Relaxation Algorithm and Passive Sensor Data Association [J].IEEE Trans on AC (S0018-9286), 1992, 37(2): 198-213.

[6] 刘宗香，谢维信，杨煊. 被动传感器系统分层快速关联算法[J].电子学报，2004，32 (12):2038-2040. LIU Zong-xiang ,XIE Wei-xin，YANG Xuan. Hierarchical Fast Data Association in the Passive Sensor System[J]. Acta Electronica Sinica, 2004，32 (12):2038-2040.

[7] 李彬彬，王朝英，文曦.被动传感器快速数据关联算法研究[J].传感技术学报，2008，21(7):1160-1163. LI Bin-bin,WANG Zhao-ying,WEN Xi.Fast Data Association Algorithm for Passive Sensors [J].Chinese Journal of Sensors and Actuators, 2008，21(7):1160-1163.

[8] KENNEDY J, EBERHART R C. Particle Swarm Optimization [EB/OL]. Proc. of the IEEE Conf. on Neural Networks, IV. Perth: IEEE Press, 1995.1942-1948. http://www.engr.iupui.edu/～shi/Coference/psopap4.html.

[9] 杨维,李歧强.粒子群优化算法综述[J]. 中国工程科学,2004,6(5):89-94. YANG Wei, LI Qi-qiang. Survey on Particle Swarm Optimization Algorithm[J]. Engineering Science, 2004,6(5):89-94.

[10] 龙海侠,须文波,孙俊. 基于QPSO的数据聚类[J]. 计算机应用研究, 2006(12):40-45. LONG Hai-xia,XU Wen-bo,SUN Jun. Data Clustering Based on Quantum-Behaved Particle Swarm Optimization[J]. Application Research of Computers, 2006(12):40-45.

[11] 刘淳安.一种求解动态多目标优化问题的粒子群算法[J].系统仿真学报，2011，23(2)：288-293. LIU Chun-an. Particle Swarm Algorithm for Solving Dynamic Multi-Objective Optimization Problems[J]. Journal of System Simulation, 2011,23(2):288-293.

[12] 刘俊芳，高岳林.带自适应变异的量子粒子群优化算法[J].计算机工程与应用，2011，47(3):41-43. LIU Jun-fang,GAO Yue-lin. Quantum Particle Swarm Optimization Algorithm with Adaptive Mutation. Computer Engineering and Applications ,2011,47(3):41-43.

Improved Data Association for Passive Sensor

XI Jun-hua1,2, WANG Zhao-ying1, GUAN Dong-dong1

(1.AFEU，Institute of Information and Navigation, Shaanxi Xi’an 710077,China；2.Xi’an Communications Institute， Shaanxi Xi’an 710106,China)

For the data association problem in the passive sensor system, a new data association with two steps for passive sensor based on quantum particle swarm algorithm is proposed. Firstly, angle statistics is constructed to eliminate most false points. Then the problem of data association is transformed into a 3D assignment problem. Finally, an improved quantum particle swarm algorithm is proposed to solve it. Simulation results show that the method can eliminate false intersection points more quickly and correctly.

data association; passive sensor; quantum particle swarm algorithm; hierarchical association

2013-11-14；

2014-07-20

陕西省自然科学基金(2011JM8023)

惠军华(1990-)，女,陕西西安人。硕士生,研究方向为信息融合。

10.3969/j.issn.1009-086x.2015.03.028

TP212；TP391.9

A

1009-086X(2015)-03-0158-07

通信地址：710106 陕西西安长安区王曲镇西安通信学院信息服务系信息资源管理教研室

E-mail：1011009123@163.com