［５］Ｂｅｒｇｍａｎ Ｎ，Ｄｏｕｃｅｔ Ａ．Ｍａｒｋｏｖ ｃｈａｉｎ Ｍｏｎｔｅ Ｃａｒｌｏ
ｄａｔａ ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ．ＩＥＥＥ Ｉｎｔ．Ｃｏｎｆ． ｏｎ Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ ａｎｄ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＡＳ—
ＳＰ），Ｉｓｔａｎｂｕｌ，Ｔｕｒｋｅｙ，２０００：５－９
令００一［１ ０ ０３，上述分析中的第１，２，３，４，６ 种情况出现，具体为
１）［１ ０ ０３， ２）［１ ２ ｏ］，Ｅ１ ０ ２］，ｆ－１ ０ ３］，Ｉ－１ ０ ４］． ３）［－ｏ ０ ｏ］． ４）［１ ２ ３］，［１ ２ ４］． ６）Ｅｏ ２ ｏ］，Ｅｏ ０ ２］，［ｏ ０ ３－１，ｒ－ｏ ０ ４３．
针对ＪＰＤＡ算法存在的问题，本文提出了一 种基于马尔可夫链蒙特卡洛方法的数据关联算法
（ＭＣＭＣＤＡ）．该算法以统计抽样思想近似估计 关联概率，解决了ＪＰＤＡ算法以解析思想处理数 据关联问题所引发的“组合爆炸”问题［５］．仿真算 例表明，在保持较高跟踪性能的同时，ＭＣＭＣＤＡ 算法大大降低了计算负荷，具有很高的工程实用 价值．
０ 引
言
数据关联是杂波环境下多目标跟踪问题的难 点之一．一直以来，联合概率数据关联算法 （ＪＰＤＡ）是解决数据关联问题的经典算法Ⅱ砣］．但 是，当目标数目增多、杂波概率提高、观测值数目 增大时，目标与观测值之间的假设关联事件的数 目将呈指数增长甚至出现“组合爆炸”现象，从而 极大地加重了（ＪＰＤＡ）算法的计算负荷，使其无法 满足实际工程应用的需要．
第３１卷 第６期 ２００７年１２月
武汉理工大学学报（鸯望霾差）
Ｊｏｕｒｎａｌ ｏｆ Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌ＆Ｅｎｇｉｎｅｅｒｉｎｇ）
Ｖ０１．３ｌ Ｎｏ．６ Ｄｅｃ．２００７
基于马尔可夫链蒙特卡洛方法的 数据关联算法研究＊
４结
论
通过理论分析和仿真算例，可以看出，ＪＰＤＡ 算法在低探测、高杂波、多目标的条件下计算负荷 过大（当关联事件总数超过１０ ０００时，计算时间以 小时计），难以满足实时性的要求；ＭＣＭＣＤＡ算 法根据统计抽样思想，以马尔可夫链蒙特卡洛方 法为基础近似估计关联概率，并可以根据实际情 况的需要在概率精度和计算负荷之间寻求折中， 因此具有非常广阔的应用前景［９］．
［６］Ｃｈａｕｖｅａｕ Ｄ，Ｖａｎｄｅｋｅｒｋｈｏｖｅ Ｐ．Ｉｍｐｒｏｖｉｎｇ ｃｏｎｖｅｒ— ｇｅｎｃｅ ｏｆ ｔｈｅ ｈａｓｔｉｎｇｓ—ｍｅｔｒｏｐｏｌｉｓ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｎ
１０）０。中原有零元素保持不变，某两非零元 素原有的值均转变为新的值，出现这种情况的前 提是某两个目标具有多个量测值．５）～ｌＯ）中０，与 瓯的海明距离为Ｚ．
对于任意的咿。，Ｄ（Ｏ。）中的元素可能会涵盖上 述全部的１０种情况，也可能只包含其中几种情 况．为更好地理解Ｄ（氏）的构成情况和上述分析， 仍根据三层标四观测值数据关联问题举例说盟如 下．
万方数据
第６期
李景熹，等：基于马尔可夫链蒙特卡洛方法的数据关联算法研究
·１０４７·
上述ＭＣＭＣＤＡ算法中，步骤４里集合Ｄ（Ｏ。） 的获取是整个算法的核心和难点，为有效降低计 算负荷、准确生成新的联合事件０。，充分发挥 ＭＣＭＣＤＡ算法的优势，根据＿Ｄ（吼）的定义，对任 意０。可能产生的集合Ｄ（Ｏ。）的构成情况进行了分 析总结．Ｄ（吼）中所有的元素，即伊。可分为１０种情 况，
·１０４６·
武汉理工大学学报（交通科学与工程版）
２００７年第３１卷
个联合事件中源于目标ｔ（１≤￡≤丁）的事件，ｉ为总 数为玩的联合事件集合的序号；ｍ（志）为ｋ时刻观 测值的个数。为表示目标未被探测到的情况，弓｛入 ｚ。（是）表示“空”观测值，％（点）为目标ｔ在第ｉ个联
合事件中未被探测到．
关联事件０ｊ，（屉）为第Ｊ个观测值与目标ｔ关联 的事件
李景熹１’２’ 王树宗Ｄ 王航宇３’
（海军工程大学海军兵器新技术应用研究所＂ 武汉４３００３３） （海军驻４２６厂军代室２’大连 １１６００５） （海军工程大学电子工程学院∞武汉４３００３３）
摘要：数据关联是杂波环境下多目标跟踪问题的难点之一．文中提出了一种基于马尔可夫链蒙特 卡洛（ＭＣＭＣ）方法的数据关联算法（ＭＣＭＣＤＡ），该算法通过在相应的关联事件空问中采样，可以 有效地估计数据的边际关联概率，而且算法的估计精度可根据需要进行调节．仿真结果表明。在需 要跟踪的目标数目较多．探测概率较低、杂波概率较高的情况下，ＪＰＤＡ算法因出现“组合爆炸”问 题而难以在实际中应用；ＭＣＭＣＤＡ算法则能在保持较高估计精度的情况下降低计算负荷，从而能 够较好地满足实时跟踪系统的要求． 关键词：数据关联；马尔可夫链蒙特卡洛；多目标跟踪；杂波 中图法分类号：ＴＰ３０１．６
万方数据
３ 仿真算例
假设观测站固定于原点，８个目标分别按照 不同的速度从各自初始位置开始做匀速直线运 动，具体情况如图３所示．探测概率、杂波概率、杂 波密度分别为：０．７４４ １，０．０３８ ７，１．４．过程噪声 和观测噪声均为零均值高斯噪声，过程噪声方差 为０．００１ ｍ，观测噪声方差为０．１ ｒａｄ和２０ ｍ．滤波 算法采用粒子滤波，粒子数Ｎ一７００；采样间隔丁 一４ Ｓ．ＭＣＭＣＤＡ算法总的采样次数分为１ ０００ 次稷４ ０００次２种情况，算例仿真结果表１所列．
＼量 删 迥 ￡ 钕 Ｘ
ｚ方向位置／ｍ
图３ 目标运动及观测值情况示意图 表１ ＪＰＤＡ和ＭＣＭＣＤＡ算法的滤波误差和运算时间
在该算例中，共有８个目标２１个观测值，关联 事件总数为３３ ６９６．由表１可见，ＪＰＤＡ算法虽然 滤波误差最小，但是计算时间过长；ＭＣＭＣＤＡ算 法的滤波误差虽然高于ＪＰＤＡ算法，但是在计算 负荷上大大降低，而且可以根据精度要求对采样 次数进行调节．
集合．式中：巩为侈（奄）中元素的个数
坍（｛）
矾（屉）一ｎ只。（志）
』皇０
（１）
为第ｉ个联合事件．其中：以（志）为观测值７在第ｉ
收稿ａ期｛２００７—０５—２２ 李景熹：男，２８岁，博士生．主要研究领域为武器系统仿真试验技术、机动目标跟踪 ’国防顼研项目资助（批准号：４０１０８０４０４０１０１）
万方数据
参考文献 ［１］Ｂａｒ—Ｓｈａｌｏｍ Ｙ，Ｌｉ Ｘ Ｒ．Ｍｕｌｔｉｔａｒｇｅｔ—ｍｕｌｔｉｓｅｎｓｏｒ
‘１０４８‘
武汉理工大学学报（交通科学与工程版）
２００７年第３１卷
ｔｒａｃｋｉｎｇ：ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｔｅｃｈｎｉｑｕｅｓ．Ｓｔｏｒｒｓ，ＣＴ： ＹＢＳ，１９９５
［２３党宏社，张震强．一种道路条件下车辆跟踪的多目标 数据关联方法．武汉理工大学学报：交通科学与工程 版，２００４，２８（６）：９０３—９０６
Ｊ＝０
式中：ｐ口（尼）为ｋ时刻观测值歹与目标ｔ的关联概
率，数据关联算法的核心就是计算艮（足）．为更加
直观地对问题进行描述，举一个三目标四观测值
的数据关联问题作为例子进行说明．图ｌ中，印Ｊ
为目 标状态预测值；ｚ，为观测值．在各自的门限之
中，目标１的观测值为ｚ，，目标２的观测值为ｚｚ，目
标３的观测值则包含ｇ：，２。和孙令口一［ｏ ０ ｏ－１为
＾，疗、
２，…，Ｎ，．令ｐ（歹，ｏ（ｊ））一ｐ（歹，０。（歹））＋第裂， ‘＾＼”０，
且０。一０。．重复步骤４）至步骤６）共Ⅳｉ次． ７）Ｐ＝Ｐ／Ｎ． ＭＣＭＣＤＡ算法的基本思路是在包含所有可
能联合事件的空间中构建刻画联合事件运动的马 尔可夫链Ｍ，可以证明，当采样次数Ⅳ足够大时， 关联估计矩阵ｐ将收敛于真实的关联概率．这是 因为首先所有的状态都可以通过臼＝０（即所有观 测值都是空值）而实现关联，所以Ｍ是不可约分 的；其次由于Ｄ（口）中包含口，因此经过若干次运动 之后总能重新回到０，也就是说自循环概率非零， 所以Ｍ是非周期的；最后由于Ｍ中的转换是通过 ＭＨ法烈实现的，所以Ｍ是可逆的．综上所述，根 据ＭＣＭＣＤＡ遍历性定理，根据算法构建的马尔 可夫链Ｍ将收敛于它的平稳分布，即真实的关联 概率‘引．
事件，该事件中仅包含ｉ个非零元素． ４）通过从集合Ｄ（Ｏ。）中均匀随机抽取一个元
素而生成一个新的联合事件０。． ５）根据ＭＨ算法确定是否接受０。． ６）如果步骤５的执行结果是拒绝ｐ，，则关联
估计矩阵ｐ保持不变且０。不移动；如果是完全接 受０，，则对于每一个０。（歹）＞０，Ｊ；１，２，…，Ⅳ，令 Ｐ（ｊ，０。（歹））＝Ｐ（ｊ，０。（歹））＋１且００一０，；如果是 部分接受口。，则对于每一个０。（歹）＞０，Ｊ一１，
ｄ女
目＾（走）一Ｕ％（足）
ｃ＝ｌ
Ｊ＝１，２，…，ＩＴＩ（志）（２）
令Ｚ（ｋ）全｛２（１），…，ｚ（志）），为直到ｋ时刻的
所有观测值序列，通过分析可知目标ｔ的状态估
计为
幺（志Ｉ正）一Ｅ［毛（足）ＩＺ（五）］＝
ｒｅ（ｋ）
∑Ｅ［ｘ，（是）怫（矗），ｚ（五）］艮（是）一
Ｊ＝Ｏ
掣
∑毛（是ｌｋ）ｆｉｊ，（ｋ）
（３）
５）护。中原有非零元素保持不变，某两个零元 素转变为非零元素．
６）岛中原有零元素保持不变，莱两个菲零元
素转 变为零元素，
７）口。中菜～非零元素转变为零元素，某一零 元素转变为非零元素．
８）％中原有零元素保持不变，某一非零元素 原有的值转变为一个新的值，同时某一非零元素 转变为零元素．
９）０。中某一非零元素原有的值转变为一个 新的值，同时某一零元素转变为非零元素，出现这 种情况的前提是某一目标具有多个量测值．
１）０。中原有所有元素均保持不变．上述情况 中０。与０。的海明距离是０．
２）０。中原有非零元素保持不变，某一零元素 转变为非零元素．
３）０。中原有零元素保持不变，某一非零元素 转变为零元素．
４）曰。中原有零元素保持不变，某一非零元素 原有的值转变为一个新的值，出现这种情况的前 提是某一目标具有多个量测值．２）～４）中０，与０。 的海明距离为１．