维普资讯 http://www.cqvip.com 兵工自动化 先避麓童与誓理 Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｅ ａｎｄ Ｍａｎａｇｅｍｅｎｔ ０．Ｉ．Ａｕｔｏｍａｔｉｏｎ ２００７年第２６卷第１１期 文章编号：１００６—１５７６（２００７）１卜００５３—０３ ２００７，Ｖｏ１．２６，Ｎｏ．１１ 测向交叉定位中消除虚假点的二次聚类算法 蒋维特，杨露菁，杨亚桥 （海军工程大学指挥自动化系，湖北武汉４３００３３） 摘要：测向交叉定位中消除虚假点的二次聚类算法，先对每条测向线上的交点进行聚类分析，得到几个聚类程 度较高的交点集合，再对该交点集合通过取交集的方法进行二次聚类，得到更少数几个交点集合，最后再对这几个 少数的交点集合进行选优，从而消除虚假交点集合，得到真实交点集合。仿真结果表明，该算法关联正确率很高， 计算量较小，实时程度较高，适用于多传感器存在漏测的情形。 关键词：测向交叉定位；聚类算法；数据关联 中图分类号：ＴＮ９５３，７：ＴＰ３９１．９ 文献标识码：Ａ Ｑｕａｄｒａｔｉｃ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｅｌｉｍｉｎａｔｉｎｇ Ｆａｌｓｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｏｉｎｔｓ ｉｎ Ｄ０Ａ Ｌｏｃａｔｉｏｎ ＪＩＡＮＧ Ｗｅｉ—ｔｅ．ＹＡＮＧ Ｌｕ－ｌｉｎｇ，ＹＡＮＧ Ｙａ—ｑｉａｏ （Ｄｅｐｔ．ｏｆ Ｃｏｍｍａｎｄ Ａｕｔｏｍａｔｉｏｎ，Ｎａｖｙ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ ４３００３３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｒｅａｌｉｚｅ ｑｕａｄｒａｔｉｃ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｅｌｉｍｉｎａｔｉｎｇ ｆａｌｓｅ ｉｎｔｅｒｓｅｃｔｉｏｎ ｐｏｉｎｔｓ ｉｎ ＤＯＡ ｌｏｃａｔｉｏｎ．Ｆｉｒｓｔ，ａｌｌ ｐｏｉｎｔｓ ｏｆ ｉｎｔｅｒｓｅｃｔｉｏｎ ｉｎ ｅａｃｈ ｄｉｒｅｃｔｉｏｎ ｌｉｎｅ ａｒｅ ｃｌｕｓｔｅｒｅｄ ｔｏ ｇｅｔ ａ ｆｅＷ ｉｎｔｅｒｓｅｃｔｉｏｎ ｓｅｔｓ ｔｈａｔ ｈａｖｅ ｈｉｇｈ ｃｌｕｓｔｅｒｉｎｇ ｄｅｇｒｅｅ．Ｔｈｅｎ， ｔｈｅ ｉｎｔｅｒｓｅｃｔｉｏｎ ｓｅｔｓ ａｒｅ ｃｌｕｓｔｅｒｅｄ ａｇａｉｎ ｂｙ ｃａｌｃｕｌａｔｉｎｇ ｔｈｅ ｉｎｔｅｒｓｅｃｔｉｏｎ ｏｆ ａｌｌ ｓｅｔｓ ａｎｄ ｇｅｔ ａ ｆｅＷ ｉｎｔｅｒｓｅｃｔｉｏｎ ｓｅｔｓ．Ａｔ ｌａｓｔ，ｔｈｅ ｂｅｓｔ ｉｎｔｅｒｓｅｃｔｉｏｎ ｓｅｔｓ ａｒｅ ｓｅｌｅｃｔｅｄ ｔｏ ｅｌｉｍｉｎａｔｅ ｆａｕｌｔ ｉｎｔｅｒｓｅｃｔｉｏｎ ｓｅｔｓ ａｎｄ ｇｅｔ ｔｈｅ ｒｅａｌ ｓｅｔｓ，Ｔｈｅ ｃｏｍｐｕｔｅｒ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｅｔｈｏｄ ｈａｓ ｈｉｇｈ ａｓｓｏｃｉａｔｉｏｎ ｃｏｒｒｅｃｔｎｅｓｓ，ｌｏｗ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｇｏｏｄ ｒｅａｌ ｔｉｍｅ ｃａｐａｂｉｌｉｔｙ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｄａｐｔｓ ｔｏ ｔｈｅ ｍｉｓｓ ｄｅｔｅｃｔｉｏｎ ｓｉｔｕａｔｉｏｎ ｏｆ ｍｕｌｔｉ—ｓｅｎｓｏｒ． Ｋｅｙｗｏｒｄｓ：ＤＯＡ ｌｏｃａｔｉｏｎ；Ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ；Ｄａｔａ ａｓｓｏｃｉａｔｉｏｎ Ｏ 引言 针对现有测向交叉定位系统中聚类算法所存在 的计算量大、求解最优解困难等问题，提出一种二 ２二次聚类算法的描述 假定在多传感器多目标测向定位系统中，传感 器个数Ｎ／＞３，目标个数Ｍ＞／３，所有传感器与目标 处于同一坐标平面内。二次聚类算法可描述为： （１）将传感器编号为Ｓｉ（ｉ＝１，２，…，Ｎ）；测向线编 号为Ｌｉｊ（ｉ＝１，２，…，Ｎ’ｊ＝１，２，…，Ｍ），表示第ｉ个传感 器的第Ｊ条测向线；交点编号为Ｐｉｌ．Ｉｋ，表示传感器ｉ 次聚类算法。即先对每条测向线上的交点进行聚类 分析，得到几个聚类程度较高的交点集合，再对这 些交点集合通过取交集的方法进行二次聚类，得到 少数的几个交点集合，最后再对这几个少数的交点 集合进行选优，从而消除虚假交点集合，得到真实 交点集合。通过交点回归计算，保证了真实交点集 合具有很高的关联正确率。 第ｌ条测向线与传感器ｊ的第ｋ条测向线的交点。 （２）对每条测向线上的交点进行一次聚类分 析。其聚类过程为：①选择测向线上相邻距离最 短且不在同一交点集合中的２个交点Ｐｉｌ．ｊｋ与Ｐｉｌ，ｉ『ｋｔ； ②将这２个交点加入到相应的交点集合中，有３ 种情况：第１种，当这２个交点处于２个不同的交 点集合中，则合并这２个交点集合，将１个交点集 合中的交点加入另一个交点集合，并删除该交点集 合，该测向线上的交点集合数减一。如Ｐｉｌ．ｉｋ∈Ａ， Ｐｉｌ。 １ 二次聚类算法的基本原理 为分析多传感器多目标测向交叉定位中交点的 分布情况，假设有Ｎ个传感器对Ｍ个目标进行测 向交叉定位。每条测向线与其它传感器的任何一条 测向线相交，可得到（Ｎ一１）ｘＭ个交点，其中，Ｎ一１ 个交点为真实交点。对其进行分析，对应每个真实 目标的真实交点集合，都有较高的聚类程度，而虚 假交点集合的聚类程度不高。现有的基于聚类分析 ∈Ａ ，则Ａ＝Ａ＋Ａ ，且Ａ ＝［】；第２种情况为 这２个交点中１个处于交点集合中，另一个不属于 任何交点集合，则将新交点加入到交点集合中。如 Ｐｉｌｏｋ∈Ａ，Ｐｉｌｊ＇ｋｔ诺ＶＡ，则Ａ＝Ａ＋｛Ｐｉｌ，ｊ＇ｋ，）；或Ｐｉｌ，ｉ『ｋｔ 。算法都在此基本原理下实现。该规律也适合于每条 测向线上的交点，因此，提出一种二次聚类算法。 收稿日期：２００７—０８—２０；修回日期：２００７—１０—２２ 基金项目：十一五预研项目资助（１０１０３０６０１０３） ∈Ａ，Ｐｉｌｉｋ诺ＶＡ，则Ａ＝Ａ＋｛Ｐｉｌ，ｊｋ）；第３种情况是 ，作者简介：蒋维特（１９８１一），男，湖南人，海军工程大学在读硕士，从事信息处理与信息融合研究。 ・５３・ 维普资讯 http://www.cqvip.com 兵工自动化 先进薯量与一理 Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｅ ａｎｄ Ｍａｎａｇｅｍｅｎｔ Ｏ．Ｉ．Ａｕｔｏｍａｔｉｏｎ ２００７年第２６卷第１１期 ２００７，Ｖｏ１．２６，Ｎｏ．１１ 这２个交点都不属于任何交点集合，则生成一个新 的交点集合，将这２个交点加入其中，该测向线上 的交点集合数加１。如Ｐｉ１，ｊｋ ＶＡ，Ｐｉｌ， ＶＡ，则 ｎｅｗ｛Ａ ），Ａ ＝｛Ｐｉ１，ｊｋ，Ｐｉ１， ）；③对②中第１种和第 １种情况中发生改变的交点集合进行冗余检查，因 为任何交点集合中任意２个传感器只能有１个交点 是真实交点。如果Ｐｎｉ，ｍｊ∈Ａ，则令ｆ．ｉ．ｍｊ一１，计算交 点冗余公式如式（１）： Ｎ Ｍ Ｆｎｍ：∑Ｚｆ ｉ．ｍｊ （１） ｌ＝ｌＦｌ 式中，若Ｆ ＞１，则已找到该测向线的聚类程 度最高的交点集合。删除互相冗余的交点并返回交 点集合。否则返回（１）继续第一次聚类过程。 （３）对所得到的交点集合进行二次聚类分析。 聚类过程描述如下：①对一次聚类得到的来自不 同传感器的交点集合两两求交集，如存在交集，则 将这２个交点集合进行合并；对没有交集的交点集 合，则认为是虚假交点集合而删除；②判断上一 步中聚类后的交点集合是否有冲突，如有，将冗余 的交点集合删赊。具体过程为：对每个交点集合设 置一个冲突计数器，在任意交点集合Ａｐ中，对任 意Ｐ ｉ， ｊ∈Ａｐ，如果存在Ｐ ｉ， ｋ∈Ａｑ，则认为交点集 合Ａｐ与交点集合Ａｑ存在交点冲突，将对应交点集 合的冲突计数器加１，并记录与之发生冲突的交点 集合的编号；③找出冲突计数器的计数值最大、 且集合中交点个数最少的交点集合，并删除此集合， 同时将与之冲突的交点集合的冲突计数器减１，并 将冲突交点集合记录中对应的记录删除，直到各集 合的冲突计数器等于零。对于任何一条测向线，只 对应于一个真实目标，如果一条测向线上存在多个 交点集合，则这些交点集合中必定有一个是真实交 点集合，其它为虚假交点集合，所以对于任意一个 虚假交点的集合，它由几条测向线相交的交点而 成，必然与几个真实交点集合产生冲突。 （４）进行交点回归计算。遍历所有真实交点集 合，根据对应于同一目标的２条测向线确定一个真 实交点，找出交点集合遗漏的真实交点，并计算该 交点与各交点集合聚类中心的距离，将该交点加入 到与之距离最小的交点集合中。从而最大限度提高 各真实交点集合的关联正确率。 如图１，左边方框中的３个交点构成一个真实 交点集合Ａ１，而真实交点集合Ａ２中只有交点Ｐ１２．３２ 与Ｐ２２．３２，通过测向线与交点的关系可找出测向线 Ｌ１２与Ｌ２２应存在１个交点处于交点集合Ａ２中，即 交点Ｐ１２．２２，通过计算交点Ｐ１２．２２与存在的交点集合 ・Ｓ４・ Ａ１与Ａ２的聚类中心间的距离，选择距离最小的交 点集合，并将交点加入到该集合中。 Ｓ１ Ｓ２ 图１ 交点回归计算示意图 ３计算机仿真 为与其它聚类算法作对比，利用Ｍａｔｌａｂ提出的 二次聚类算法与参考文献［４】中基于基准线的最小 距离聚类算法作了仿真比较。即采用与参考文献［４】 中同样的测试条件对２种方法的仿真结果作对比。 仿真条件１：设传感器个数Ｎ＝５；目标个数Ｍ 一３；Ｔ为传感器坐标矩阵，Ｐ为目标坐标矩阵。对 同一批目标，进行１００次实验。０为传感器的 测向误差，当Ｔ１＝［１Ｏ，２５，７０，９０，１００；０，５，８，３０，－７】；Ｐ１＝ ［２１，４７，６７；６７，９３，３８】时，在此条件下提出的二次聚类 算法模拟结果如表１；而基于基准线最小距离聚类 算法仿真结果如表２（数据来源于参考文献［４】）。 表１ 二次聚类算法模拟结果 、＼ 确相关率 测量条件、＼ 目标１ 目标２ 目标３ 时间 ０＝０．５ １００％ ｌ００％ １００％ ０．１１９３ Ｏ＝１ １００％ ｌ００％ ｌ００％ ０．１２ｌ０ ０＝２ ｌ００％ ｌｏｏ％ ９８．７２％ ０．１４０ｌ 表２ 基于基准线的最小距离聚类算法仿真结果 、＼测量条件、＼：正确相关率 目标ｌ 目标２ 目标３ ０＝０．５ １００％ ９９．８９％ ９９．８４％ Ｏ：ｌ ９９．６０％ ９８．９２％ ９９．１２％ ０＝２ ９７．２０％ ８９．８０％ ９３．７２％ 表３ 二次聚类算法仿真结果 、＼ 正确相关率 测量条 ＼ 目标１ 目标２ 目标３ 时间 ＼ ０＝０．５ ｌ００％ １００％ ９８．３８％ ０．２ｌ５３ Ｏ＝ｌ ｌ００％ ９９．５７％ ９６．６２％ ０．２５２０ ０＝２ ｌ００％ ９９．３９％ ９２．１８％ ０．２２４ｌ 表４ 最小距离聚类算法仿真结果 ＼正确相关率 测量条 目标１ 目标２ 目标３ ＼ ０＝０ ５ ９９．６％ ９６．９６％ ９４．３１％ Ｏ＝ｌ ９９．４８％ ９５．９６％ ８８．２０％ ０＝２ ９７．２８％ ９４．４１％ ９１．２４％ 仿真条件２：设传感器个数Ｎ一６；目标个数Ｍ ＝３：Ｔ为传感器坐标矩阵，Ｐ为目标坐标矩阵。对 同一批目标，进行１００次实验。当Ｔ２＝［Ｏ，２０，４０，６０， 维普资讯 http://www.cqvip.com 兵工自动化 先进制瘟与萱理 Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｅ ａｎｄ Ｍａｎａｇｅｍｅｎｔ ０．Ｉ．Ａｕｔｏｍａｔｉｏｎ ２００７年第２６卷第１１期 ２００７，Ｖｏ１．２６，Ｎｏ．１１ ８０，１００；５，１４，７，２０，９，２５］；Ｐｌ＝［２１，４７，６７；６７，９３，３８］时， 类算法正确相关率高于该文献［４］中提出的基于基 准线的最小距离聚类算法，且正确率高。对传感器 存在漏测情况下的二次聚类算法结果也作二次仿 真。条件同上，但存在传感器漏测，、ｌ，为传感器对 在此条件下提出的二次聚类算法模拟结果如表３。 而基于基准线的最小距离聚类算法在同样条件下的 仿真结果如表４（数据来源于参考文献［４］）。 表５二次聚类算法仿真结果（第１种仿真条件下） 每个目标的漏测概率，如表５、表６。可见，二次 ＼ ＼ 丘礴 聚类算法在漏测概率较低时仍具有较高的正确关 关率 目标１ 目标２ 目标３ 时间 测量条件＼ 联率，且计算复杂度无明显增加，具有好的实用性。 ０＝０．５ ９４，７１％ ９３．５８％ ９１，５２％ ０，１０８２ 、Ｊ，＝２０％ Ｏ：１ ９４．３９％ ９２，６１％ ９０，３６％ ０．１３０８ ４ 结论 ０－－２ ９１＿３９％ ９０．９４％ ８９．９７％ ０，１２５９ ０＝０．５ ９０，３９％ ９０．０８％ ８８．６０％ ０，ｌ１６８ 计算机仿真结果表明，该算法具有很高的关联 、Ｊ，：３０％ Ｏ：１ ８９ １９％ ８５．４９％ ８７．６１％ ０．１２６１ ０＝２ ８７，０３％ ８４．６２％ ８２．３４％ ０．１５５０ 正确率，且计算量较小，实时程度较高，适应于多 传感器存在漏测的情形。 表６二次聚类算法仿真结果（第２种仿真条件下） ＼ ｊｆ劈 参考文献： 测量条件＼＼ 日关率 目标１ 目标２ 目标３ 时间 ［１】何友．多传感器信息融合及应用［Ｍ】．北京：电子工业 ０＝０．５ ９２．６１％ ９０．２９％ ８９．１４％ ０．２２５２ 出版社．２００２．１９０—１９４． 、Ｊ，＝２０％ Ｏ＝１ ９１．８０％ ８７．１５％ ８５．１９％ ０．２４８３ ［２】胡来招．无源定位［Ｍ】．北京：国防工业出版社，２００４． ０＝２ ８８．０９％ ８５．９７％ ８３ ５８％ ０，２５６２ ３１—４０． ０＝０．５ ９０．６９％ ８８．９２％ ８６．４９％ ０．２４９４ 、Ｊ，：３０％ Ｏ：１ ８７．９４％ ８４，６２％ ８２．６８％ ０．２６２５ ［３】孙伸康．单多基地有源无源定位技术［Ｍ】．北京：国防 ０＝２ ８４．１９％ ８０．６３％ ７８，９１％ ０．２７０８ 工业出版社．１９９６．１８１—１９５． ［４】李立萍．一种排除无源交叉定位虚假交点的新方法［Ｊ】． 在文献［４］中提到的仿真条件下，提出的二次聚 系统工程与电子技术．１９９９，２１（４）：２０—２３． 丰丰丰丰丰丰木丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰木丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰年丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰丰术丰丰丰丰丰丰丰 （上接第４９页） 兵力行动模型模拟作战兵力的运动 出兵力平台的武器装备硬件配置及其交战方式，是 中，该运动特点及气象条件对其武器装备、行动的 作战兵力自主行动的基础，也是构成兵力控制 影响，计算武器装备的威力和杀伤力。通信模块负 Ａｇｅｎｔ的控制基础。通信模块负责与其他兵力Ａｇｅｎｔ 责与通信Ａｇｅｎｔ和战场环境Ａｇｅｎｔ的交互，如图５。 和通信Ａｇｅｎｔ的交互，如图７。 行为差异模型 通信模块 图５兵力控制Ａｇｅｎｔ结构 器Ｉ墓 ＋ ３．５通信Ａｇｅｎｔ 感知行为模型 通信网络的运行是各种信息从终端设备出发 经一系列处理和传输到达目的设备过程，可认为通 图７作战兵力Ａｇｅｎｔ模块 信网络是对各种与通信有关的信息进行处理和传输 ４ 结束语 的信息处理系统，采用适合于网络通信的Ｐｅｔｒｉ网模 该系统仿真能表现环境和人等活的因素，增强 型对通信Ａｇｅｎｔ建模仿真，如图６。 模型的表达能力和可重用性，同时具备较好的扩展 性和较强的针对性，便于对分系统进行重点仿真。 参考文献： ［１１江汉，等．基于分布式仿真的Ｃ４ＩＳＲ效能评估系统设 图６通信Ａｇｅｎｔ建模 计与实现［Ｊ】’系统仿真学报，２００６，（６）． ３．６作战兵力Ａｇｅｎｔ ［２】杨桂芳，等．基于多主体的舰艇编ｇ．ＬＣ３Ｉ系统建模［Ｊ】＿ 作战兵力是具备自主行动能力的智能体。在作 兵工自动化，２００５，（４）． ［３】侯锋，等 基于多Ａｇｅｎｔ的Ｃ４ ＩＳＲ系统建模与仿真方法 战兵力Ａｇｅｎｔ中，用一个行为器模拟兵力的自主作 研究［Ｊ】＿光电技术应用，２００４，（３） 战行为，其基础是感知、学习、决策行为模型及行 ［４】周彦，等．基于ＨＬＡ的Ｃ４ ＩＳＲ系统仿真环境［Ｊ】．计算 为差异模型；武器装备模拟器、武器交战模型等给 机仿真．２００２，（９） ・５５・
