基于分治贪心思想的联合多站目标关联定位

王冠群， 张春华，3， 张舒然

(1.中国科学院 声学研究所， 北京 100190； 2.中国科学院 先进水下信息技术重点实验室， 北京 100190；3.中国科学院大学， 北京 100049；4.中国船舶工业系统工程研究院， 北京 100036)

0 引言

在水下低信噪比环境中，单一传感器无法提供全面、准确的目标信息，难以实现准确的区域预警。分布式多传感器网络系统[1-3]作为新兴手段，能够提供多角度、多维度的目标观测信息，是当前研究的热点，但是多传感器观测也带来了信息冗余和计算开销等一系列难题[4]。多站方位量测目标关联定位技术，也被称为被动交叉定位技术[5-8]，是传感器网络系统中应用最广泛的技术之一，特别是在复杂的水下环境中，很难通过其他属性对目标进行有效的区分，而随着高分辨率目标方位谱估计方法[9-11]的不断出现，使得基于方位量测的水下目标关联定位方法的应用研究[12]具有更大优势。

对于目标定位问题，解决方法可以分为两大类：一是最大似然估计法[13]，通过建立目标的联合似然函数并求取最大估计值来获得空间中的最优估计；二是通过建立伪线性方程组，并通过最小二乘算法[14]获取近似最优解。这两类方法的定位精度均建立在准确的数据关联之上，由于量测- 目标之间的未知对应关系，导致上述定位方法不能直接应用，否则会产生虚假交点，因此数据关联是定位过程的前提和基础，也是研究的重点。目前常用的关联方法包括最小距离法、最大似然法、周期谱相关法[15]，但它们或有效性低，或计算复杂，或存在需要目标先验信息等缺点[16]。为了改善这些问题，姜亦武等[17]在最小距离交叉定位方法的基础上，通过设置最小距离门限来剔除虚假交点，提高关联效率和准确率。蒋维特等[18]提出一种基于距离的二次聚类方法，通过聚类方式改善了最小距离法关联正确率低的缺点，同时减少了计算量，并且适用于传感器漏检的场景。窦丽华等[19]在概率思想基础上提出一种新的改进单亲遗传数据关联方法，将后验概率的极大值求解问题转化为求解特殊的指派问题，并通过遗传算法来进行搜索优化，提高了目标关联正确率和算法的收敛速度。李猛等[20]提出一种基于角度传感器网络的目标关联定位方法，给出了存在量测误差下目标定位概率的推导，实现在有限计算量下的虚假点剔除，提高了目标关联的正确率和定位的可靠性。

传统的多站方位量测目标关联定位方法将关联和定位拆成两个独立的计算过程，然后分别得到最优估计。这种分步处理并取局部最优的方式，在低检测率、强虚警的水下环境中，存在目标定位精度不高、关联正确率低等问题。为了提高水下多站多目标关联定位技术的关联正确率和目标定位精度，同时降低算法的计算开销，本文提出一种基于分治贪心思想的多站关联定位方法。首先根据分治思想[21]，采用最小距离原则选取每条方位线上的真实交点集合；然后根据贪心思想，对所有的交点集合进行合并，在集合合并的过程中，通过定位过程和关联过程之间的反复验证，从而保证了目标关联的准确率和定位精度；最后根据关联关系，对相互互斥的目标量测集合进行组合，并选取联合关联概率最大的多目标量测集合作为最后的输出。仿真及试验结果表明，在满足一定虚警和漏检的前提下，本文方法具有很高的关联正确率和目标定位精度，并且算法的计算量适中，适用于实际水下场景。

1 数学模型

假设存在一个水下传感器网络系统来实现多目标定位过程，目标数目为D，节点数L，在某个观测时刻，假设所有节点的量测集合为Z1∶L={Z1,…,Zl,…,ZL}，l为节点编号，节点l的观测集合为Zl={Zl,1,…,Zl,nl,…,Zl,Nl}，nl=1,…,Nl表示节点l所获得的目标量测编号。假设节点和目标的位置分别为Xl=[xl,yl]T、Xd=[xd,yd]T，d∈[1,D]，xl、yl和xd、yd分别为节点和目标的东向坐标和北向坐标，并假设目标d相对于节点l的方位角为θl,d，则对于任意目标d均满足如下方程：

(1)

由于节点观测误差的存在，即Z=θ+V，θ为理想方位角，V为节点观测误差，节点方位量测Z与理想方位角θ之间无法直接建立一一对应的关系，因此基于多站方位量测的目标定位过程必然需要分解为关联和定位两个步骤。如图1所示，在区域内布放3个探测节点，并实现对空间中的2个目标进行关联定位过程。

图1 基于多站方位量测的目标关联定位示意图Fig.1 Target association and positioning based on multi-station bearing measurement

2 算法原理

2.1 基于分治思想的最优交点集合选取

1)按照顺序求取所有的方位线交点{Kl1nl1,l2nl2}|∀l1,l2∈[1,L]，其中下标表示该交点由节点l1的Zl1,nl1号方位线与节点l2的Zl2,nl2号方位线相交产生。

2)对于任意一条方位量测线Zl0,nl0，选取该方位线上相邻距离相对较短的M条线段，并寻找线段对应的方位线集合；例如交点Kl0nl0,l1nl1和Kl0nl0,l2nl2之间所夹的线段，与之对应的方位线集合为Wl0,l1,l2={Zl0,nl0,Zl1,nl1,Zl2,nl2}。

3)由于方位线集合中包含3个元素，可通过定位方法给出与该方位线集合相对应的目标位置估计，并计算目标d的关联似然概率为

(2)

2.2 基于贪心思想的量测集合合并

对于任意由真实目标产生的方位量测，在理想条件下，该方位线上最优交点集合对应的方位线集合Wl0,l1,l2={Zl0,nl0,Zl1,nl1,Zl2,nl2}，必然为该目标所对应的方位量测全集的子集。由于很难通过寻找全局最优方式获得真实目标的量测全集，通过对不同节点上的方位线集合Wl0,l1,l2进行合并也不乏是一种次优的处理方式。为了避免集合合并时的组合爆炸问题，本文基于贪心思想提出一种集合合并方法，该方法通过顺序处理所有节点，将寻找全局最优问题分解成一系列局部最优选取过程来解决。为了方便理解，图2中给出该方法的简要流程示意。图2中，∅表示空集，l、l′∈[0，L]，l≠l′.

图2 基于贪心思想的集合合并方法示意Fig.2 Set merging method based on greedy thought

如图2所示，该方法按节点顺序进行集合的合并，同时在合并前判断是否满足以下原则：

1)原集合所包含的方位量测是否已经遍历所有节点；如果是，则不需要将原集合与并入集合进行合并(其中，前l个节点的已合并集合称为原集合，节点l+1的方位量测集合称为并入集合)。

2)原集合和并入集合之间是否存在互斥现象；如果是，则不能与并入集合进行合并(互斥现象是指在两个集合的并集中，来自同一节点的量测数量大于1)。

最大长度Q的选择对算法的复杂度和关联正确率至关重要；当参数Q较大时，意味着保留更多的次优方位线集合，必然能够提高目标关联正确率，同时也增加了算法复杂度；当Q较小时，则结果相反。因此需要进行折中选择，即在保证关联正确率前提下，尽量降低算法的复杂度。实际情况下，可以考虑设置Q的值在目标数D的2～3倍之间；目标数D未知时，可以考虑用各观测节点量测数的平均值来代替目标数D.

2.3 基于贪心思想的量测总集划分

图3 基于贪心思想的量测总集划分Fig.3 Set division method based on greedy thought

(3)

3 计算机仿真

3.1 算法验证

为了验证本文方法的有效性，进行计算机仿真。设置探测节点数为4，相邻节点间距为4 km，并呈正方形拓扑结构放置。每个节点对区域内的目标进行独立观测，同时假设所有节点的目标检测概率均为Pd，虚警概率均服从期望值为λ的泊松分布，经过节点独立检测后，单节点探测系统会输出一系列方位量测信息，包括目标量测和虚警杂波，其中假设所有单节点探测系统的角度探测误差均服从均值为0°、方差为σ2的高斯分布，虚警杂波在观测范围(-π rad,π rad]内服从均匀分布。为了更全面地反映本文方法的关联性能，下面分别设置3个不同的仿真场景。

3.1.1 场景1：低杂波双目标场景

假设在水下探测区域内存在2个静止目标，位置分别为[500 m，-1 500 m]、[-500 m，800 m]，假设探测节点的目标检测率为0.9，虚警期望为1，测向误差为1°.探测节点以及目标位置布置场景示意如图4所示。由于目标漏检、目标虚警以及节点角度探测误差的存在，导致方位量测不能与目标完美对应，因此需要借助关联定位方法来给出最优的目标位置估计。

图4 探测节点以及目标位置布置场景1Fig.4 Detecting nodes and target locations in Scenario 1

图5所示为本文方法对2个目标的关联定位结果，在定位过程中采用最小二乘算法，并且假设目标数未知，设置本文方法中的参数为M=3，Q=10，I=5.从图5中可以看出，在该仿真条件下本文方法能够准确地估计出空间中的目标个数，其目标定位误差约为30 m，表明该方法在低杂波、少量目标场景下能够实现有效的目标关联定位过程。

图5 场景1目标关联定位结果Fig.5 Target association and positioning results in Scenario 1

3.1.2 场景2：高杂波双目标场景

场景2中除了提高杂波的密度以外(假设虚警期望为10)，其他场景参数设置与场景1相同。设置参数为M=5，Q=10，I=5，图6～图9分别为场景示意和目标关联定位结果。

图6 探测节点以及目标位置布置场景2(无明显虚假焦点)Fig.6 Detecting nodes and target locations in Scenario 2(without obvious false focus)

图7 场景2目标关联定位结果(无明显虚假焦点)Fig.7 Targets association and positioning results in Scenario 2 (without obvious false focus)

图8 探测节点以及目标位置布置场景2(存在明显虚假焦点)Fig.8 Detecting nodes and target locations in Scenario 2(with obvious false focus)

图9 场景2目标关联定位结果(存在明显虚假焦点)Fig.9 Target association and positioning results in Scenario 2 (with obvious false focus)

对比图6～图9可以看出，在高杂波、少量目标场景下，本文方法能够对真实目标进行正确关联，并输出准确的定位估计结果，但是由于目标数目未知，容易出现虚假关联目标(见图9)。分析图8可知，在高杂波、少量目标场景下，各观测节点的杂波容易汇聚成虚假焦点(见图8)，从而导致出现虚假关联目标。

3.1.3 场景3：高杂波密集目标场景

场景3中假设在水下探测区域内存在6个静止目标，目标位置在场景中随机分布，假设探测节点的目标检测率为0.9，虚警期望为5，测向误差为1°.设置参数为M=5，Q=20，I=10，图10、图11分别为场景示意和目标关联定位结果。

图10 探测节点以及目标位置布置场景3Fig.10 Dectecting nodes and target locations in Scenario 3

图11 场景3目标关联定位结果Fig.11 Target association and positioning results in Scenario 3

观察图10、图11可以看出，在高杂波密集目标场景下，本文方法能够对大部分目标进行正确关联，并输出准确的定位估计结果，但是也正是由于虚假焦点的存在(见图10)，导致少部分目标出现错误关联(见图11)。因此也从侧面反映出本文方法在高杂波、密集目标并且存在虚假焦点的情况下，存在目标错误关联的潜在风险。

3.2 性能分析

为了进一步分析本文方法的关联定位性能，选用文献[18]中的关联定位方法作为对比方法；该方法基于二次聚类思想，并采用最小距离法则寻找最优关联关系，以实现目标关联定位过程。由于这两种方法本质上更侧重于关联技术的创新，先对两种方法的关联正确概率进行对比分析。

在仿真场景1的基础上，针对不同参数影响，分别进行100次蒙特卡洛实验。为了方便统计关联正确率，在计算过程中假设目标数已知，此时对于真实目标只存在正确关联和错误关联两种状态，排除了因目标数目估计错误所导致的关联正确率难以统计的情况，仿真结果如表1～表3所示(除表中可变参数外，其他参数与场景1中参数一致)。

表1 不存在漏检和虚警时关联正确率仿真结果对比Tab.1 Comparison of simulated results without missingdetection and false alarm

表2 只有虚警时关联正确率仿真结果对比Tab.2 Comparison of simulated results with only false alarm

表3 同时存在虚警和漏检时关联正确率仿真结果对比Tab.3 Comparison of simulated results with missingdetection and false alarm

从表1～表3中可知：相对于文献[18]方法，本文方法在存在角度误差、虚警及漏检时的目标正确关联概率均优于文献[18]方法；在不存在漏检时，本文方法的关联正确率均能保持在90%以上；在同时存在虚警和漏检时，本文方法仍能保证70%以上的关联正确率，而文献[18]方法的关联正确率随虚警概率增大而迅速下降，最终导致方法失效。这是因为在建立关联关系的过程中，文献[18]方法仅采用最小距离法则，而本文方法同时结合最小距离法则和最大似然法则，因此本文方法具有更高的关联正确率以及宽容性。同时，由于本文方法采用贪心思想简化关联搜索过程，将原本全排列的整体寻优过程简化为线性连续的局部寻优过程，因此大大减少了计算量。

在进行多站多目标关联定位时，目标的关联正确率同样受多目标的相对空间位置影响；当多个目标相距较远时，节点的目标量测相对分离，关联正确率也相对较高，随着多目标之间的间距缩小，节点的目标量测相互靠近重叠，甚至会导致目标漏检，则此时关联正确率必然下降。下面在场景1的基础上，对多目标间相对位置变化时两种方法目标关联性能进行仿真分析。在定位过程中采用最小二乘算法，设置本文方法的参数为M=3，Q=10，I=5，目标检测率为0.9，虚警期望为1，测向误差为1°.

图12所示为探测节点以及目标位置变化场景示意，场景中假设目标2位置不变，目标1逐渐向目标2靠近。目标间距变化时，两种关联定位方法的仿真结果如表4所示。观察表4可知：两种方法的关联正确率均随着目标间距离缩小而下降，但是相对于文献[18]方法，本文方法的目标正确关联概率相对较高，且仍能保证70%以上的关联正确率。

图12 探测节点以及目标位置变化Fig.12 Dectecting nodes and change of target locations

表4 目标间距变化时关联正确率仿真结果对比

由于本文方法和文献[18]方法的创新之处更侧重于关联技术，并且均能与不同的定位方法进行组合，因此下面就结合两种不同的定位技术对目标定位精度展开讨论。表5所示为组合方法与其编号的对应关系。

图13所示为表5中4种组合方法在不同角度观测误差下，100次蒙特卡洛仿真后的目标平均定位精度结果。图5中假设不存在目标漏检和虚警杂

图13 不同方法组合时的目标定位精度分析Fig.13 Positioning accuracy with the combination of different methods

表5 组合方法与其编号对应关系Tab.5 Correspondence between algorithm and number

波，并假设目标关联错误时的定位误差上限为1 km，即定位误差超过1 km时按1 km进行统计。分析可知，当节点的角度观测误差较小时，本文方法与对比方法的关联正确率都较高，因此影响定位精度的主要因素就是搭载的定位方法。由于基于最大似然思想的定位方法在理论上能给出系统的最优估计，而基于最小二乘算法的定位方法则是将非线性的定位方程改写成伪线性的方程组并求取次优解，原则上最大似然算法的定位方法的定位精度要高于最小二乘算法的定位方法。随着节点的角度观测误差增大，由关联错误会导致定位精度迅速下滑，并逐渐成为影响定位精度的主导因素，而在同等条件下，本文方法的关联正确率优于对比方法，定位精度也相对更高。

4 试验验证

利用2020年11月在浙江省千岛湖进行的分布式多节点联合处理试验来验证本文方法性能。试验中采用3条悬浮在水中的水平阵对试验区域内的合作声源进行探测。在某观测时间段内，取时长为10 s的观测数据进行处理，期间合作声源目标相对处于静止状态。通过对该时间段内探测节点、合作声源的全球定位系统信息进行提取，其位置关系如图14所示。

对试验时间内阵列的接收信号进行目标方位谱估计(包括常规波束形成、高分辨谱估计方法)，各个接收阵在10 s观测时间内的方位历程图如图15所示。对场景中的目标进行阈值检测，并根据阵列姿态信息对目标检测结果进行空间上的校正，以获得各个观测节点的方位量测结果，如图16所示。

图15 两种不同方法的方位谱估计结果Fig.15 DOA results of two different methods

图16 节点、目标、方位量测间相对关系Fig.16 Relative relationship among node，target and azimuth measurement

利用本文方法加上最小二乘算法(即表5中组合方法2)来实现目标关联定位过程，结果如图17所示。从图17中可以看出，利用本文方法在实际水下环境中能够实现有效的目标关联定位过程。

图17 试验中目标关联定位结果Fig.17 Target association and positioning results in experiment

为了统计分析本文方法的实际关联定位性能，对109 s观测时间内的接收数据进行滑动积分和阈值检测处理。实际处理时每帧的积分时长为10 s，帧与帧之间的滑动长度为1 s，即第n帧的积分时间段为[n-1 s,n+9 s]，n=1,2,…,100. 各节点方位历程图如图18所示。在观测时间内，目标和观测节点均处于静止状态，通过阈值检测和空间校正，以获得各个观测节点的方位量测结果，如图19所示，图中纵轴为大地坐标系下的角度(即以正北为0°，按顺时针为正)。

图18 两种不同方法的方位谱估计结果Fig.18 DOA results of two different methods

用图19中的目标方位检测结果作为关联定位方法的输入来分析本文方法在实际环境下的目标关联定位性能，并同样选择文献[18]方法进行对比分析，结果如表6所示。从表6中可以看出：在实际单目标场景中，两种方法均有良好的关联定位性能，且目标定位误差与节点平均间距之比均小于4%. 对比两种方法的平均单帧运算时间，可以看出本文方法的运算速度更快，计算量更小。

图19 各节点方位检测结果Fig.19 DOA results of nodes

表6 目标定位结果分析Tab.6 Analysis of target positioning results

5 结论

本文针对多站多目标关联定位问题，提出一种基于分治贪心思想的多站关联定位方法。该方法先根据分治思想并采用最小距离原则选取每条方位线上的真实交点集合；再根据贪心思想对所有的交点集合进行合并，以及目标量测集合间的组合，并选取联合关联概率最大的多目标量测集合作为最优的关联定位估计结果。仿真结果表明，在一定虚警率和漏检情况下，本文方法有很高的关联正确率和定位精度，同时利用贪心思想降低了计算复杂度，适用于实际水下场景。仿真结果及湖试数据均验证了该关联定位方法的有效性。