基于聚类算法的多源信息融合并行处理研究

陆小科

(南京电子技术研究所，南京 210039)

0 引 言

多源信息融合是对多源信息进行综合处理的一项新技术。其利用多源在空间和时间上的冗余与互补，以得到被处理对象更加精确、更加全面的信息。多源信息融合具有以下特点：(1) 可以扩展空间和时间覆盖范围，解决探测、跟踪和识别问题；(2) 提高信息可信度和处理精度；(3) 鲁棒性高，应对单传感器受干扰、变坏等情况，具有较高的生存能力[1]。多源信息融合在反导预警、防空等领域发挥着巨大的作用。随着雷达、飞机、导弹等武器装备的不断进步，对融合系统的处理要求也不断提高，其处理容量要求更大，处理精度要求更高，实时性要求更好。传统的串行处理方式显然无法满足新的作战要求。

聚类分析法是数据挖掘常用的算法之一，根据一定的分类规则，合理地划分数据集合，确定每个数据所在类别的过程，使得同类中的数据之间最大程度地相似，而不同类中的数据之间最大程度地不同。层次聚类是聚类分析的一种，包括自上而下的分裂和自下而上的凝聚。凝聚聚类将每一个对象当作初始类，将这些类合并成一个更粗略的分区，反复合并，直至得到满足一定条件的聚类集合。

本文分析了现有融合处理逻辑，剖析了融合系统并行化处理的重点难点，提出了一种基于凝聚层次聚类算法的并行化融合框架，并使用MPI和OpenMP相结合的编程模型实现该并行框架，在两台多核服务器上验证了该框架，试验结果表明，该并行融合处理比串行处理具有较高的加速比，处理容量更大，实时性更高[4]。

1 数据融合并行化分析

数据融合系统主要包括时空一致性、数据预处理、航迹起始、航迹关联和航迹滤波等功能模块[5]。时空一致性将各雷达探测到的目标位置数据转换到同一坐标系，将各雷达的探测时间统一到相同基准时间上，同时修正各雷达间可能存在的系统位置误差和时间误差；数据预处理在于剔除传感器上报的错误异常数据以及去除杂波虚警；对于预处理后的量测信息，首先进行航迹相关，建立不同传感器量测或同一传感器不同时刻量测之间的匹配关系，判断量测信息与融合航迹是否属于同一目标；未被关联的量测信息进行航迹起始，即判断量测与量测之间的互联关系，对于满足一定起始准则，建立新航迹；对关联成功和新起始的航迹，进行航迹滤波处理，抑制随机误差，精确估计目标位置和相关运动参数(速度和加速度)。数据融合处理逻辑流程如图1所示。

图1 数据融合逻辑流程图

从图1可知，模块之间处理的序贯性高，下级模块的输入对上级模块输出的依存度大，处理过程中，对于航迹与航迹之间存在共享量测或者单批航迹关联多个量测信息等关联模糊性导致了融合处理的数据耦合性高，同时在多雷达多目标处理中雷达上报探测信息的时机随机性大，尤其对于相控阵雷达，这些都是数据融合并行处理的难点[6]。

2 数据融合并行化架构

本文提出的融合并行架构分为框架并行和模块内部并行两个粒度，首先利用层次聚类算法将目标航迹和量测聚类，将各独立聚类单元分发至多计算节点中并行处理；在每个聚类处理单元内，根据各处理模块的特性以及航迹间的耦合关系将各航迹分发到多核中并行处理。

2.1 基于层次聚类数据划分

层次聚类的任务划分是按照航迹间的空间位置关系以及航迹间模糊关联关系将融合航迹和多传感器量测数据动态聚类成多个组，航迹组内各航迹间具有相关性，而不同航迹组之间相互独立。从而可将航迹组分配至不同的计算节点并行处理，而为了数据的完整性，可将航迹组内所有航迹统一处理。

假设序列{xi}为雷达量测集合或者融合航迹当前位置集合，处理步骤如下：

Step1 计算待聚类序列{x1,x2,...,xN}内任意两点xi和xj之间的空间距离dij，得到序列点间的关联矩阵D=(dij)N×N，同时对任意两批融合航迹xi和xj，若关联上共享量测则相关性标志sij为1，否则为0，得到航迹相关矩阵S=(sij)N×N。

Step2从航迹相关性矩阵S的行向量Si中找出与航迹xi相关的各元素，同时剩余航迹中，找出与xi距离小于门限Gate的各元素形成聚类Ci。

Ci(xi)={xj|dij

Step3 对于任意两个聚类Ci和Cj，若满足D(i,j)=dij=d(Ci,Cj)=minr,s=1,...N,r≠sd(Cr,Cs)或者S(i,j)=sij=∏r,s=1,…,N,r≠sS(Cr,Cs)=1

则可将聚类Ci和Cj合并为新的聚类Cq。

Step4 聚类合并Cq=Ci∪Cj，在关联矩阵D和航迹相关性矩阵S中，删除元素Ci和Cj对应的行和列，将Ci和Cj从集合C中删除，重新计算新类Cq与C中其他所有元素的空间距离d以及判断航迹相关性标志s，将新行和新列分别插入关联矩阵D和航迹相关性矩阵S对应的q行和q列中。

Step5 判断若所有满足条件的元素合并至同一聚类中，则终止，否则执行step3。

该方法与数据融合中的起始关联门限相结合，以航迹相关和起始的基本原理为依据，自适应将任务划分为能独立处理的子问题，适宜并行处理。

2.2 负载均衡分析

对于聚类生成的航迹组，组内的航迹批数和航迹间关联模糊性都不一样，导致融合处理的计算量也不一致；且由于多节点间存在同步问题，最大计算量节点的性能会影响到整个系统的处理时延。考虑到以上两点问题，如下给出了目标分配的方法。

统筹考虑组内航迹批数和航迹关联模糊性，以及多目标关联算法、航迹滤波算法的复杂性，估算出完成航迹组融合处理的计算量，假设航迹组为Gi，其对应的计算量为M(Gi)。

Step2 若航迹组个数小于处理器个数，即K≤N，则将各组单独分配到不同处理器处理；或者处理器只剩一个，即N=1，结束。

Step4 去除已分配航迹组，更新集合M及航迹组个数K，N=N-1,跳转Step1

层次聚类及负载均衡处理效果如图2所示。

图2 目标聚类及资源分配示意图

从图2可知，左上图为融合航迹当前位置或雷达量测当前位置在经纬度平面上的投影，根据投影点之间的空间位置，利用聚类算法，可得到7个航迹聚类，分析聚类的目标批数和彼此关联关系可得处理复杂性，根据负载均衡算法，将各个聚类分发到不同的处理器上处理。

航迹群内，对于航迹关联或航迹起始后的航迹，考虑到滤波处理时航迹间不存在耦合性，采用以单批航迹为单元的并行处理。可在每个计算节点上采用OpenMP的多线程并行模型完成航迹滤波处理。综合以上两个层次的并行措施，可得融合并行处理的架构图如图3所示。

2.3 融合并行架构实现

基于以上并行架构的分析，本文采用主从模式的多机并行架构模式，主节点实现数据整理和多计算节点的统一管理，计算节点实现融合的起始、关联、滤波等计算密集模块。处理步骤如下：

Step1 初始化操作，完成MPI模型的初始化

图3 数据融合并行架构示意图

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Comm_size(MPI_COMM_WORLD,&size);

Step2 主节点实现航迹粗相关和聚类分发。

(1) 接收雷达量测，完成时空一致性和数据预处理；

(2) 航迹粗相关：TrackRawCorrelate();

(3) 关联成功的融合航迹，完成航迹聚类TrackMerging()，用于下一步的航迹精关联和航迹滤波;

未被融合航迹粗关联上的量测完成量测聚类MeasureMerging()，用于下一步的航迹起始和滤波;

(4) 综合考虑组内航迹或量测的处理复杂度，MPI_Send将聚类分发到指定的计算节点中处理；

Step3 计算节点采用MPI_Recv通信方式接收融合航迹组和量测组，完成航迹精关联、航迹起始和航迹滤波。

(1) 对于融合航迹组对组内航迹做航迹精关联：

TrackPrecisCorrelate();

(2) 未被关联上的雷达量测组完成航迹起始：

TrackInit();

(3) 完成航迹精关联和航迹起始后的多批融合航迹，利用OpenMP多线程模式完成航迹滤波的并行处理：

#pragma omp parallel for

for(i=0;i

TrackFilter(systrks[i]);

(4) 各计算节点将完成处理后的融合航迹通过MPI_Send发送至主节点。

Step4 主节点MPI_Recv方式收集计算节点信息。为避免多目标处理时间节点紊乱导致死锁或者数据错误，MPI_Barrier控制各计算节点的同步，完成航迹汇总上报。循环处理step2到step4直至程序退出， MPI_Finalize结束MPI环境。

3 试验分析

针对基于MPI和OpenMP相结合的数据融合并行框架，利用防空系统大区域数据验证融合并行系统的功能和性能。试验采用两台曙光A840-G10服务器(两颗CPU A6212 主频2.6G，8核心，64G内存，操作系统为RedHat6.2，编译器为gcc 4.4.6，并行环境Openmpi 1.6.5)。

(a) 试验场景

接入雷达5部，雷达扫描周期为10 s，处理作战空域4800 km×4800 km,同时处理目标为6000批，雷达输入目标为28000批航迹信息。基于MPI模型的并行模式采用双机集群，分别为管理节点和计算节点，OpenMP共生成20个线程并行处理。

(b) 处理效果对比

融合并行处理软件能同时跟踪6000批目标，处理时延均值为0.7秒，并串行处理效果比较如图4、图5所示。

图4 并行效果图

图5 串行效果图

从图4可知，并行处理时，6000批目标能快速起始并稳定跟踪，目标都有长尾迹；串行处理时由于处理目标多，航迹起始占用资源过多，时延大，后续的航迹相关和航迹滤波无法实时处理，导致航迹后续无法稳定跟踪，如图5可知，航迹起始后无跟踪的长尾迹。

(c) 处理时延对比

图6、图7分别给出同时处理6000批目标的并行和串行时延对比图以及针对不同目标数量并行和串行处理平均时延对比图。

图6 6000批目标时延比较图

图7 不同目标数时延比较图

从图6可知，同时处理6000批目标，并行架构处理时延能较稳定地维持在1秒左右，而串行程序时延均值达到7秒以上，严重影响融合处理的实时性，且存在大量数据积压，最大处理时延达25 s，易引起融合系统崩溃，影响系统稳定性。从图7可知，当跟踪目标数较少时，由于MPI和OpenMP需要多进程和多线程管理，存在系统开销，导致并行处理时延稍大于串行处理，当处理目标数稳定增加时，并行处理时延缓慢增加，而串行处理处理时延激增，并行的加速比随着处理容量的增加而增大。

(d) 资源利用率对比

采用串行和并行处理架构，CPU核心的负载和使用率存在明显区别。并行和串行CPU使用情况见图8和图9。

图8 并行CPU负载

图9 串行CPU负载

并行框架下，通过对融合任务分割及并发执行，将计算机资源充分利用起来，且都存在一定的资源冗余，发挥出了高性能计算的优势，提高了系统的稳定性和扩展性，CPU利用情况如图8。串行框架下所有处理流程按顺序处理，无法将融合处理分配到其它核心上去，导致某个CPU核心满负荷工作，而其它核心却处于空闲状态，极大的浪费计算机资源，也容易超过单核极限处理能力导致处理滞后。串行处理框架下CPU的负载情况如图9。

4 结 语

数据耦合性高，处理逻辑序贯性强，处理时机存在随机性是多雷达数据融合系统并行化的难题。本文提出了一种基于层次聚类的航迹分组方法，将在空间域上相互独立的航迹划分为同一组，不同组采用MPI多进程并行处理，同一组内航迹采用OpenMP多线程并行处理。该方法有效的克服了多雷达数据的耦合性，规避了融合系统的处理逻辑序贯性，提高了处理实时性，增加了融合处理容量，具有良好的可扩展性。