态势估计中的目标分群算法设计与实现

张冬宁，艾 伟

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

态势估计中的目标分群算法设计与实现

张冬宁，艾 伟

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

针对态势估计中的目标分群问题，分析了目标的位置、运动状态和属性对分群结果的影响，建立了目标相似度计算模型，并提出了分群策略，包括群的形成、分裂和合并等。采用面向对象软件设计思想建立了分群对象模型，分析了对象间关系。给出了分群算法的主体流程，并对其中的关键步骤进行了详细的说明。开发了目标分群算法模块，实现了对数据的预处理、目标群的更新维护、群属性的计算等功能，通过仿真试验，调整目标分群影响因子及加权因子，得到了较好的分群效果，验证了文中方法的可行性和正确性。

目标分群；群分裂；群合并；目标相似度

0 引言

目标分群是态势估计中的首要任务，能够为进一步识别敌方行为意图、判断敌方威胁情况，以及分析敌方作战协同关系提供有力依据。目标分群是在完成战场空间内的目标航迹融合和属性识别的基础上，综合考虑目标位置、属性和运动状态等信息，自动实现目标的分组聚类，将类型相近、运动状态相近和执行相同作战任务或对我方具有相同威胁的目标进行合并，简化战场情况，给指挥员提供更为简单的战场视图，辅助指挥员进行指挥决策[1]。

很多专家对态势估计中的目标分群问题进行了深入研究，如基于知识和最邻近法的研究[2]、基于模糊理论的研究[3]、基于证据理论的研究[4]和基于相似性测度模型的研究[5]等。本文在对其分析的基础上，建立了一种基于多属性的目标相似度计算模型，并给出了群形成、分裂、合并算法，以及群的图形化显示方法。通过软件实现和仿真试验，验证了该算法可快速有效地实现目标分群。

1 问题分析

式中，ID为目标编号；Attr为目标的敌我属性(包括敌、我、友、中立、不明和其他)；Type为目标类别(包括空、地和水)；Model为目标型号；Lon为目标在某时刻的经度；Lat为纬度；Height为高度；Vx为目标在经度方向上的速度分量；Vy为目标在纬度方向上的速度分量；Vz为目标在高度方向上的速度分量。对于∀Em∈E,En∈E，都有IDEm≠IDEn。

2 算法设计

2.1 目标相似度计算

目标分群以相似性为基础[8]，首先需要计算目标之间的相似度。目标的属性对目标相似度的影响不同，本文称其为影响因子，并且各属性取值对于分群结果的影响也是不完全一致的。例如敌我属性为敌的和敌我属性为我的目标，肯定不能分为一群，而敌我属性为我的和敌我属性为友的，可能是一群。另一个例子，当目标转弯时，一个群内的目标不会同时转弯，总会有先后次序的，这就会造成在同一时刻，一个群内的目标在3个方向上的速度分量会有较大差别。因此，需要对影响因子再设定加权因子，来平衡群内目标的差异。

目标相似度计算方法如下：

① 根据参与相似度计算的目标属性，包括敌我属性、目标类别、目标型号、经度、纬度、高度、速度在经度方向的分量、速度在纬度方向的分量以及速度在高度方向的分量，建立目标相似度矩阵为：

相似度矩阵S的每个元素依次为敌我属性影响因子、目标类别影响因子、目标型号影响因子、经度影响因子、纬度影响因子、高度影响因子、速度在经度方向上的分量影响因子、速度在纬度方向的分量影响因子以及速度在高度方向的分量影响因子，代表目标各属性的取值对目标相似度计算的贡献大小。且所有影响因子的和为100，即sattr+stype+smodel+slon+slat+sheight+svx+svy+svz=100。

② 对敌我属性(敌、我、友、中立和不明)的各取值建立加权矩阵为：

含义为2个目标的敌我属性均为敌、或我、或友、或中立、或不明时，加权因子为1；一个为我，另一个为友时，加权因子为0.8；一个为不明，另一个为敌、或友、或中立时，加权因子为0.5；其他情况的加权因子均为0。

③ 对目标类别(空、地和水)的各取值建立加权矩阵为：

含义为2个目标的目标类别均为空、或地、或水时，加权因子为1；其他情况的加权因子均为0。

⑥ 对2个目标的纬度差、高度差(m)、各方向的速度差(km/h)设置加权因子的方法同⑤。

⑦ 对目标数据进行预处理，统一量纲。

2.2 算法流程

本文所用目标分群算法的基本思想是对航迹融合后的每一个目标航迹数据，先获取其所属群，判断该群是否分裂，再判断与其它群或离散目标是否合并。具体算法流程，如图1所示。

图1 目标分群算法流程

在判断群是否分裂时，先将群内目标看作未分群的离散目标集合，再对这些目标进行遍历计算，算法步骤如下：

步骤1：找到第一个(下一个)离散目标；

步骤2：从该离散目标向后寻找到能与该离散目标合并的离散目标，并记做一个群；

步骤3：在该群内部遍历，找到群内的下一个目标；从该目标向后寻找到能与该目标合并的离散目标，记录到该群内。

步骤1～步骤3循环，直到遍历完离散目标集合，若新群内目标与原群不一样，则判定为群分裂。

在判断群是否合并时，只要Gj和Gk满足条件∀Em∈Gj,∃En∈Gk,s.t.SCOREEmEn>Grouplimit，则2个群可合并。

2.3 算法比较

国内外关于目标分群的算法主要是利用目标或群之间的空间距离作为聚类依据，在复杂战场环境中，只考虑空间距离是不够的，还必须综合考虑目标群体的多属性。本算法在计算目标相似度时，通过设定目标各属性的影响因子，明确了参与计算的各种属性对目标相似度的贡献；对各属性建立加权矩阵，通过设定属性各种取值的加权因子，明确了属性的各种取值对属性相似度的贡献；再通过影响因子和加权因子综合计算得出目标的相似度得分。计算中利用了较多的目标属性，并且能够根据实际使用环境灵活调整影响因子和加权因子，从而提高相似度计算的准确性，既能确保相似目标不被错判，又能平衡目标之间的差异，具有较好的实用性。

3 软件实现

3.1 建立对象模型

目标分群问题涉及到的主要业务对象包括：目标元素CElement、目标元素集合CElementSet、目标群CGroup、目标群集合CGroupSet、输入的数据报DataPack和分群计算的控制CGroupingCtrl，目标分群对象之间的关系如图2所示。

图2 目标分群对象模型

3.2 数据预处理

对于输入的数据报，首先进行预处理，主要包括以下几方面：

① 野值剔除。将接收的数据报DataPack进行解包，判断目标的各运动状态值及各属性值是否在值域范围内，并在本次作战范围内，若不在，则剔除。

② 数据校准。根据接口规定，若输入数据为航向和航速，则校准为3个方向的速度分量。

③ 单位转换。将空中目标、海上目标及陆地目标的速度单位统一转换为km/h。

④ 目标对象更新。根据输入的数据，新建或更新目标对象各属性值。

3.3 群的动态维护

创建3个目标元素集合CElementSet的对象，分别为空中目标集合airElementSet、水面目标集合seaElementSet和陆地目标集合landElementSet。对于每一个目标元素CElement，根据目标类型存放到相应的目标集合中。

当计算出群后，创建目标群CGroup的对象，并将该群对象加入到目标群集合CGroupSet中。将群内目标对象指针加入到该群的链表中，并设定每一个目标对象的群指针为该群。

群更新时，将更新群的标识回调给主程序，主程序可以根据接收的群标识获得如下信息：

① 调用CGroup::getCircumPolygon()函数，获得群的外接凸多边形定位点；

② 调用CGroup::getGroupCenter()函数，获得群重心点；

③ 调用CGroup::getGroupDirection()函数，获得群方向；

④ 调用CGroup::getElementInGroup()函数，获得群内目标。

3.4 群外接凸多边形计算

步骤1：找出点集P中y轴最小的点p0，该点必为凸包的顶点；

步骤5：初始化堆栈Hs，令Hs(0)=pn-1，Hs(1)=p0；初始化堆栈指针Hsp使其指向p0，数组P′的下标记为k，令k=0；

步骤6：若k≥n，算法结束；

步骤7：判断Hs(i)、Hs(j)和Hs(l)三点构成的路径是左旋还是右旋，若为左旋，令Hsp=Hsp+1，Hs(Hsp)=P′(k)，k=k+1，然后跳转到步骤6；若为右旋，则令Hsp=Hsp-1，然后跳转到步骤6。

3.5 群图形显示

针对上述目标分群算法进行了软件实现。使用二维仿真数据来模拟敌方空中编队的联合作战场景。当所关注的区域里出现较多目标时，用户难以确定要关注的目标，在显示时也显得比较复杂凌乱，仿真目标图形显示如图3所示，以圆形符号表示空中单个目标。

图3 仿真目标图形显示

经过对目标进行分群处理后，出现了5个目标群，作战环境中的重要情况可以由目标群的运动情况来判断得出。目标群的图形显示方式有2种[12]：一种为在群中心上显示一个带方向的群符号，并用数字显示架次数，这种方式更利于简化整体态势展现，如图4所示；另一种为显示群的外接凸多边形，这种方式有利于展现目标队形，如图5所示。

图4 群中心简化图形显示

图5 群外接多边形图形显示

4 结束语

目标分群过程中，不同的影响因子和加权因子对分群结果的影响较大，因此需要大量数据，并且是各种类型数据的仿真训练来确定较为合理的影响因子和加权因子。通过仿真试验，本文的方法能够较为准确地对目标进行分群。但由于仿真脚本只包含二维数据，没有在高度上进行充分训练，并且仿真场景中目标的飞行路线较有规律，没有包含更复杂的行动路线。这些将在下一步工作中继续研究。

[1] 张 芬，贾 则，生佳根，等.态势估计中目标分群方法的研究[J].电光与控制，2008，15(4)：21-23，69.

[2] 李伟生，王宝树.态势估计的目标编群问题研究[J].计算机科学，2003，30(8)：136-138.

[3] 李伟生，王宝树.态势估计中基于模糊集理论的目标编群方法[J].系统工程与电子技术，2005，27(3)：1 235-1 237.

[4] 王 铮，刘高峰.基于证据理论态势估计中的目标分组方法[J].舰船电子工程，2006，26(2)：46-48.

[5] 刘洁莉，韩元杰，董彦佼.态势评估中的目标编群问题研究[J].光电与控制，2010，17(1)：26-29.

[6] 龙真真，张 策，王维平.基于层次聚类态势估计中的目标分群算法[J].弹箭与制导学报，2009，29(3)：209-211.

[7] 黄 雷，郭 雷.一种面向态势估计中分群问题的聚类方法[J].计算机应用，2006，26(5)：1 109-1 110.

[8] 张松良，王付明，鲁 柯，等.城市战场目标分群的组合聚类方法[J].指挥控制与仿真，2009，31(5)：37-41.

[9] GRAHAM R L.An Efficient Algorithm for Determining the Convex Hull of A Finite Planar Set[J].Information Processing Letters，1972，1(4)：132-133.

[10]JARVIS R A.On the Identification of The Convex Hull of a Finite Set of Points in The Plane[J].Information Processing Letters,1973,2(1)：18-21.

[11]毛 鹏.快速凸包计算实现及其应用[D].西安：电子科技大学，2013.

[12]段同乐，张冬宁.二叉树多分类SVM在目标分群中的应用[J].无线电工程，2015，45(6)：88-91.

张冬宁 女，(1981—)，高级工程师。主要研究方向：智能信息处理。

艾 伟 男，(1977—)，高级工程师。主要研究方向：信息融合、态势仿真。

Design and Realization of Target Grouping in Situation Assessment

ZHANG Dong-ning,AI Wei

(The54thResearchInstituteofCECT,ShijiazhuangHebei050081,China)

Situation assessment is one component of data fusion.And target grouping is one of the main tasks of situation assessment.The factors of target,such as position and attribute,which influence the result of grouping,are analyzed.The grouping strategy is also presented for initialization,split,and combination.We used object-oriented technology to build grouping object model.The algorithms are brought forward for calculating target grouping.Particularly,the key steps in algorithms are described.We developed grouping dynamic link library program.The program can provide pretreatment of data,group updating,and group attribute calculation.The algorithm parameters and weighting factors are adjusted by simulation experimentation.Simulation results validate the feasibility and correctness of the grouping algorithms.

target grouping;group split;group combination;situation assessment;data fusion

10.3969/j.issn.1003-3106.2016.11.11

张冬宁,艾 伟.态势估计中的目标分群算法设计与实现[J].无线电工程,2016,46(11):42-46.

2016-08-13

国家部委基金资助项目。

TP391.4

A

1003-3106(2016)11-0042-05