第37卷第3期 2021年3月
信号处理
Journal of Signal Processing
V ol.37 No.3
Mar.2021
文章编号：1003-0530(2021)03-0390-09
一种高效的分布式多传感器多目标跟踪算法
范建德谢维信幼儿园大班下学期班务计划
(深圳大学A TR国防科技重点实验室，广东深圳518060)
摘要：现有的多传感器多目标跟踪算法大都基于马尔科夫-贝叶斯模型，需要诸如目标运动、杂波、传感器检测概率等先验信息，但是在恶劣的环境中，这些先验信息不准确并导致目标跟踪精度下降。为了解决该情况下的多目标跟踪问题，我们提出了一个高效的分布式多目标跟踪算法，该算法通过泛洪（Flod
m g)共识算法在分布式网络的传感器之间迭代的传输、共享各自的量测集信息，并通过改进的密度峰值聚类（Improed Densty Peaks
四大古典名著
CluStem g，IDPC)算法对量测集聚类，聚类得到的簇的个数即目标的个数，簇的中心即目标的位置。我们将IDPC 算法与前沿的分布式概率密度假设（probability density hypothesis，PHD)滤波器在三个场景中进行对比，实验结果证明了 IDPC算法的有效性和可靠性。
关键词：传感器融合；分布式传感器网络；泛洪共识算法；密度峰值聚类
中图分类号：TN713 文献标识码：A D O I：10. 16798/j. issn. 1003-0530.2021.03.009
引用格式：范建德，谢维信.一种高效的分布式多传感器多目标跟踪算法[J].信号处理，2021，37(3): 390-398.
D0I：10.16798/j. issn. 1003-0530. 2021.03. 009.
Reference form at：FAN Jiande，XIE Weixin. An Efficient Distributed Multi-Sensor Multi-Target Tracking Algorithm[J].
Journal of Signal Processing，2021，37(3)：390-398. D0I：10. 16798/j. issn. 1003-0530. 2021.03. 009.
An Efficient Distributed Multi-Sensor Multi-Target Tracking Algorithm
(ATR Key Laboratory，FAN Jiande XIE Weixin
Shenzhen University，Shenzhen，Guangdong 518060，China)
A bstract：The existing multi-nsor multi-target trackingalgorithms are mostly bad on Markov-Bayes model，which requires prior information such as target motion，clutter，and nsor detection probability，but in harsh environments，the prior information are not accurate and lead to a decrea in target tracking accuracy. To solve the MTT problem in such situation，we propo an efficient distributed multi-target tracking algorithm，which us a flooding connsus algorithm to iteratively transmit and s hare the measurement t information between nsors in the distributed network，and cluster the measurement t through an Improved density peaks clustering ( IDPC) algorithm. The number of clusters obtained by clustering is the number of targets，and the center of the clusters is target * s position. We compare the IDPC algorithmwith cutting edge distributed probability density hypothesis (PHD) filters in three scenarios，the experiment effectiveness and reliability of the IDPC algorithm.
Key words：nsor fusion；distributed tracking; flooding; density peaks clustering
i引言
用分布式多传感器网络跟踪多个目标，相对于用集中式多传感器跟踪多个目标，有着不依赖任意 网络节点、增加/删除节点灵活、鲁棒性强等方面的 优势[13]。因此，用分布式传感器网络跟踪多个目
收稿日期：2020-08-12；修回日期：2020-09-18
基金项目：深圳市基础研究计划项目（JCYJ20170818102503604)；国家自然科学基金项目（61271107, 61703280)
第3期范建德等：一种高效的分布式多传感器多目标跟踪算法391
标运动是如今的研究热点。
在分布式传感器网络中，每个传感器都有信息感
知、计算和信息传递的功能。在每个时刻，每个传感
器生成一组量测信息（包括目标的量测和杂波），并
迭代的向其邻居传感器传递并共享信息，该信息可能
是量测信息[4—5]、目标的先验/后验密度信息[6—W]、目
标的估计或航迹[114!]。在达到最大的迭代次数后，所
有的传感器达成共识，即便经过更多次迭代，分布式
网络上的各个传感器的量测信息不再变化。
现有的多传感器多目标跟踪算法，大多是基于
马尔科夫-贝叶斯模型，如分布式PHD滤波器[1416]，
这些滤波器的跟踪性能依赖先验信息与实际场景
的一致程度，在实际应用中存在以下问题：高中数学老师
(1$需要诸如目标的数目、出现和消失的时间、
运动模型等先验信息，而这些先验信息在实际目标
运动场景中可能因环境噪声过大而不准确并造成
目标跟踪精度下降。
(2)运行比较复杂，这意味着当传感器的功率
受限时，运行复杂的滤波器不能对目标实时跟踪。
为了解决上述问题，文献[17]提出了一种仅依
赖传感器量测的数据驱动算法，泛洪聚类（flodrng
then clustering，FTC)算法，FTC 算法通过泛洪（Flood
忍组词ing)#] 共识算法，将共享的量测集通过 DBSCAN算
法[19]和<means算法™进行聚类，聚类得到的簇的
中心即估计的目标的位置，簇的个数为目标的个
数。相对于分布式PHD算法，FTC算法在计算速度
和跟踪精度上均取得了较好的效果[17]。但是，FTC
算法依赖DBSCAN算法的聚类效果。分布式传感
器在不同的迭代次数，共享的量测数据点的局部密
度变化较大，用同样的参数，DBSCAN算法的聚类性
能会有所下降，而DBSCAN算法的参数推断是DB-SCAN算法的一个固有难题。当传感器的量测为非
线性时下降更为严重，参考文献[17]第5节。为了
改善以上问题，本文提出了一种改进的密度峰值聚
类[21](Improved density peaks clustering，IDPC)算
法，如37节所示，改进后的算法更加高效。本文提
出的算法包括以下三个步骤！
(1) 通过分布式泛洪共识算法[1?]在每个传感 器之间迭代的传递、共享量测数据。
(2) 每个传感器将共享的量测数据转换为二维 笛卡尔坐标系中的点。(3)将这些数据点的集合用IDPC算法进行聚
类，聚类得到的每个簇为某个目标的观测集，簇的 个数即为目标的个数、聚类中心即为目标的位置。
本文提出的算法在三种场景中与迭代校正PHD (iterated corrector PHD，IC-PHD)滤波器[15]，FTC 算 法[17]，算术平均 PHD(aathmetic average PHD，AA-PHD)滤波器[22-23]进行对比，对于AA-PHD滤波器和 IC-PHD滤波器，提供了满足其最佳性能所需的先验 信息。相反，IDPC算法和FTC算法不需要上述先 验信息，仅仅通过各个传感器的量测即可检测和估 计各个目标。
2问题描述
2.1符号与假设
分布式传感器网络可以用图的形式来表示，该 图由传感器的集合〇= 11，2,…，/和边的集合+3S
x〇组成。边是由两个有序的传感器对（5，j') !+组 成的，传感器J可以直接连接传感器5，其中传感器j
是传感器i的外邻居（〇ut-neighbor)传感器，传感器Z
是传感器j的内邻居（in-neighbor)传感器。我们定 义内邻居传感器的量测集$，$, 1j〇I(i，J) ! +，i*j'2。此外，传感器J'的第^ ! "=11，2,…丨次迭
代构成的传感器的集合表示为$( (2
(5，则 $(1) = $，$(〇)==。
如果分布式传感器网络中任意一个传感器经 过有限次的迭代，可以到达传感器网络中的另一个 传感器，则称该传感器网络构成的图为强连接(strong connected，S C)网络。两个传感器之间的最 大距离称为图的直径。
对于存在漏检和虚警情况下的多目标跟踪问 题，我们有以下假设：
(1) 在任意时刻，目标的数目$和状态！是随机的；
(2) 每个目标只产生一个量测数据，各个传器的量测数据相互独立；
(3) 每一时刻每个传感器的杂波个数由泊松控制，随机产生且杂波的密度远小于目标的量测的 密度。
2.2分布式传感器网络及泛洪共识算法
在本文中，我们采用分布式泛洪算法[1?]在传感 器网络上传递各自的量测数据，通过该方法，所有
392信号处理
第37卷
传感器都将信息同步的传递到相邻的传感器。假 设网络是S C 网络，则分布式传感器网络中的每个 传感器能够在次迭代之后达成共识（即每一个 传感器具有完全相同的量测集）。尽管泛洪共识算 法对本地传感器的存储和通信能力提出了很大的 挑战，但在传感器具有足够的存储和通信能力的某 些应用中，有收敛速度快的优点。
简而言之，每个传感器都存储了当前所有已知 传感器的初始数据表（每个传感器的0)。在第f !11，2,…丨次通信迭代时，分布式传感器网络上的每 个传感器向其第f 个互连的邻居传感器更新数据表 的内容，并传递/共享数据表中传感器的量测数据 集。具体而言，每个具有0=!!1，!$，…丨，
的传
感器的量测集将在第《 ! "+ = 11，2，…丨次迭代更新 为0(f 。我们使用0(〇) = 0表示在传感器 的初始测量值[18]。
当f 1时，每个传感器从其内邻传感器接受量 测集。
0(1)=0(〇) 2.2.0(〇)=M A y (1)0(〇)
⑴
当^2时，每个传感器收集其内邻居传感器在 先前迭代中已收到的新的量测集。疫苗分类
0(f 1) = 0⑴ U U l 0()\0(f -1)2
=
U 0(0)
(2)
其中，31代表集合3和：的集合差，即属于3而 不属于：的所有元素的集合。
当
时
，分布式传感器网络中每一个传感
器中的量测数据将全部相同。
0()+>2〇0(〇)
(3)
2.3基于量测数据的推断^
我们将分布式多目标跟踪问题定义为通过量 测数据来估计目标的位置和个数。为了简化问题， 我们将研究重点放在两种类型的传感器上!线性传 感器和非线性传感器，这两种类型的传感器的量测 数据均被投影在二维平面上，并进行聚类[M]。
线性位置量测模型如下
1 0■
P %k
V ，1
_!B ，k _
0#1
_P ，k _
+
_ %k ，2 _
(>)
其中，[E ，<，E ，< ]<；是目标的位置，％，1和％，$是相互独
立的量测噪声。
线性量测在状态空间的无偏估计如下
P大榕树
其中，G [%1]和£[%<,$]为量测噪声％,1和％,2的平 均值。非线性量测模型如下
L
其中，[l ，l ]t 是传感器的位置，％和％是影响范 围和角度的噪声。
非线性量测在二维空间的投影如下！
槡（E ,t -L )2 + ( P r ,k ~m r )2
arctan ( (e ,<-l b )/(E ,<-l J )
G [%<,
(5)
5n (p ,<)6<
5n ( p y ,k ) A n ( I * ~E [ Vg k ] \b < <
好莱坞艳照(7)
,
,
I ()-E [ V ) ])2
p
其中，6 =槡+一(|*為]1))2，5n (P ,k )和^^(八^依赖目标在传感器感应范围的象限…，24]。
2.4聚类约束
经过f a 次量测数据迭代传输后，每个传感器 汇总的量测集（杂波和目标的量测）将达成共识。 将汇总的量测集投影到二维空间，可以发现：目标 的量测集聚集的地方，局部密度较高；杂波的局部
密度较低。则可以通过一种密度聚类算法对量测 集进行聚类，滤除杂波，从而筛选出目标的量测形 成的簇，簇的中心即目标的状态、簇的个数即为目 标的个数。为了得到更准确的聚类结果，需要遵守 以下几个约束条件。
(1) 聚类得到的每一个簇"，其期望的大小E
[I " I ]应该在 L $((f a J /2」和
I 之
间，在已知迭代次数和给定传感器目标检测概率的 情况下，可以认定E [ I " I ]=)为一个常数。
(2)
重叠簇是指相互靠近的两个或者更多个
标的量测相互重叠，造成簇的大小特别大，需要将 其划分为满足约束（1)的子簇。
(3)
聚类后目标的量测形成的簇，来自每个
感器的量测数据点应该小于等于1。
3本文提出的算法
3.1密度峰值聚类算法
2014年，密度峰值聚类算法[21] (density
peaks
第3期范建德等：一种高效的分布式多传感器多目标跟踪算法393
clustering,DPC)发表在《科学》杂志上。DPC算法 属于密度聚类算法范畴，其核心思想是聚类中心具 有较高的局部密度和相对较远的距离。截断距离 ，&是唯一需要的参数，可以通过用户自定义或者在 线学习来计算得到。DPC算法需要计算两个量：局 部密度（和距离.。局部密度（定义为：
P5="x(d5; U(8)
其中,5是数据点的距离矩阵A G)是一个分段函 数，当*<0 时，，—％)= 1；当*)0 时，，—％)= 0。,&是
截断距离，可以通过预定义或从数据集中学
习[17,21]。（在数值上等于数据点截断距离内的点 的个数。P，越大，表明数据点i的局部密度越大，其 是目标的量测的可能性越大。
DPC算法定义.为数据点5与局部密度更高的
数据点J的最小距离
.=min(d l]')(9)
i'-p j>p i
自DPC算法发表以来，诸多学者提出了基于 Q2S算法的改进算法，如：边缘检测密度峰值[$;] (boundary detection density peaks clustering，BD-DPC)和密度峰值 < 最近邻[26](86+80卩631»3)814- *ng< nearest neighbor，DPC-KNN)。纵观这些改进 的算法可以发现，这些算法基本都是在DPC算法上 做“加法”，如BDDPC算法将DPC算法与不对称度 量相结合;DPC-K丽算法将DPC算法与KN N算法 相结合。以上这些改进算法无疑又增加了 DPC算 法的运算耗时。分析DPC算法，其运算耗时主要是 局部密度P i和距离.的计算耗时。根据文献[21] 的数据集，经过计算我们发现：计算变量P i的耗时 2与计算变量.的耗时2二者的关系为：2-0.5622。如何在不降低跟踪效率的情况下减少2 和2，是加速DPC算法的关键。
3.2本文所提出的算法
本文提出一种改进的DPC算法（improved den
sity peaks clustering，IDPC)，该算法仅仅通过局部
密度P i即可求得多个传感器量测数据的聚类中心，与原始的DPC算法相比，在保证聚类精度的同时，
节省了计算距离.的时间。在二维空间中，目标的 量测围绕在目标真实位置周围，而杂波服从泊松分 布，随机分散在空间中，多个传感器的量测叠加，会 造成目标的量测局部密度较大，而杂波的局部密度较小。我们可以设定阈值，当量测数据点的局部密 度大于阈值时，判定其为目标的量测，当量测数据 点的局部密度小于阈值时，则判定其为杂波。在给 定传感器检测概率的情况下，目标的量测的集合可 以定义为：
CT =U z M(10)
其中C是目标的量测集，9是传感器的数目，/是一 个常数，[0.2，0.4]。Z的选取依赖目标生成的量 测数据点的局部密度，在非线性传感器组成的分布 式传感器网络中，目标生成的量测数据点在空间上 更为分散，导致截断距离内的数据点的个数较少，即P i相对较小，〗！ [0. 2,0. 3]；在线性传感器网络 中，目标的量测数据点在空间上较为集中，导致截 断距离内的数据点相对较多，P i相对较大，〗！ [0. 3, 0.4]。（是指数据点i截断距离内的数据点 的数目必须大于阈值>9。
在求得C的情况下，可以通过公式（11)来求 得目标的个数，目标的个数正确与否直接关系着聚 类的精度和准确度。
"< =[爐](11)
r
对于任意一个目标生成的量测数据点形成的 簇，其目标的个数为
c.
<=(12)在给定C和"<；条件下，通常情况下优先考 虑用<-means算法[20]进行聚类，但在实验的过程中，我们发现，在数据集中有重叠簇的情况下，< means算法得到的聚类结果往往不满足C L约束。为了解决这个问题，文献[27]提出了多源密度峰值聚类（multi-source density peaks clustering，MSDPC)算法，MSDPC算法首先判断"中有无重叠簇，然后 根据有重叠簇和无重叠簇两种情况分别进行处理: 在数据集中无重叠簇的时候，通过<-means算法对 C进行聚类，< 可以通过公式（11 )计算得到；在数 据集中有重叠簇的情况下，要先计算P i和.来确定初始聚类中心，再对重叠簇进行二次聚类，详细过 程参考文献[27]第3节。MSDPC算法的不足之处 是:<-means算法是一个多次迭代的过程，比较耗
394信号处理第37卷
时，且在同样的参数"和"< 条件下，多次聚类
其聚类结果可能有差异；其次，当数据集中有重叠
簇时，需要计算.，增加了耗时。IDPC算法可以有
效解决MSDPC算法的上述问题。
在本文中，在得到"•和的情况下，根据
这样一个先验规律:"中（最大的数据点max(p,)
为局部密度最大的点，也是当前局部密度最大的某
个簇的中心。通过迭代的查找"•中局部密度最大
的数据点max(()及其截断距离内的数据点的集 合，即可将"中的数据点分配给多个簇，根据每个
簇的数据点的数目，判断该簇是否为重叠簇。对于
非重叠簇，每个簇的数据点的坐标平均值即为估计
的目标的位置；对于有重叠簇的情况，通过<means
算法对重叠簇进行二次聚类。IDPC算法的具体步
骤如下所示。
IDPC算法__________________________________
输入:"和"<。
输出：簇"及其聚类中心P k |1，2,…，<。
1.查找"中的局部密度最大的点（，并求点•/'的
截断距离，&内的点集"，，& = L,。，L! (1 1，
1.5]。"= "\"。
2.重复步骤1，直到c r=0。检查簇q与其他簇
"有无交集，J'，eis (1，2,…，<]，j*e。如果"
n c e#0，则 = C}u c e,c e=0〇
3.根据每个簇"的大小，如果"为重叠簇，则用
<means算法求子簇及其聚类中心，如果"为
非重叠簇，则簇"的聚类中心为各个点的横
纵坐标平均值。___________________________
4实验对比
本节的主要目的是将ID P C算法与F T C算
法[17]、分布式PHD算法[15,22-23]在三个不同场景进
行对比，来证明IDPC算法的有效性和可靠性。目
标运行的区域范围为（-1000, 1〇〇〇]e( -1000, 1000](m)，实验所用到的目标模型、参数、实验场景
多英文以及传感器拓扑和文献（17]—致。考虑了具有不
同网络拓扑和目标轨迹的两种情况。实验一和实验二的分布式传感器网络是由20个具有线性或非 线性测量模型的传感器(+l=4)组成，如图1所示，实验三的分布式传感器网络是由1?个传感器（线 性和非线性传感器各占一半，+l= 5)组成，如图4 所示。
新生目标的状态：(％)= "i=1!"(%;l，S)，人=!$ =^3 =0. 05，其高斯分量分别为:L= (-100, 10，-800,30]
t，l2= [-800,20，-500,0]t，l3= (0, 0,950，-30]T，S= Fiag([100,25，100,25]T)。S 为其方差。每一个目标的生存概率均为0.98，且每一 个目标有一个恒定的速度，其值与文献[17]相同。状态转移噪声为="(02，25=)。
以上有关目标的统计信息是提供给P H D滤波 器的，以获得最佳性能，FTC算法和ID P C算法仅仅 需要各个传感器的量测集，截断距离可以实现给定 或从传感器的量测中学习得到[2?]。每个场景均使 用随机生成的量测数据但目标轨迹相同，进行了 100次蒙特卡洛实验。每次运行包含60个时刻。我们用最佳子模式分配（optimal sub-pattem assignment，OSPA)度量[29]用于评估位置估计精度，其中 截止参数& = 1000，顺序参数p= 2。此外，我们将网 络0SPA定义为分布式网络中所有传感器在每个采 样步骤获得的0S P A的平均值，而时间平均网络0SPA则定义为所有过滤步骤中网络0S P A的平 均值[22—23]。
为了评估通信成本，一个高斯分量由权重参数 (1个元组），4维矢量均值（4个元组）和4x4对称 矩阵协方差（10个元组），共15个元组组成。目标 个数参数为1个元组，每个加权粒子取5个元组（状 态向量为4个元组，权重为1个元组）。
4.1线性传感器网络
图1给出了传感器网络拓扑和目标的轨迹，每个 传感器运行一个线性量测模型，其中％< ~"(0, 100)，
％，2 ~"(0，100)。我们假设每个传感器的目标 检测概率为E(%)= 0.95，对于P H D滤波器来说，权 重小于10^的高斯分量被裁剪掉，马氏距离小于4的两个高斯分量参与融合，最大的高斯分量数目为100。分布式PH D滤波器在每次迭代过程中按照部分共识 传递部分权重较大的高斯分量[22]，融合后权重大于 0.1的高斯分量在相邻的传感器之间互相传递。
