用于协同感知的分布式聚类方法研究

李 晨，梁小溪，梁军利，刘睿恺，叶中华,3

(1. 上海机电工程研究所，上海 201109； 2. 西北工业大学 电子信息学院，陕西 西安 710072； 3. 西安理工大学 自动化学院，陕西 西安 710048)

0 引 言

未来“信息化、网络化、智能化”的作战要求将使新一代导弹的作战方式产生极大变化。网络化分布式协同作战具有高度集成、自组织、自决策、效费比高等特点，势必将成为未来战场上行之有效的作战模式[1]。这种作战模式对新一代导弹的探测感知能力提出了更高的要求，不仅要求单弹具有较高的探测能力，还要求多弹具有分布式协同探测能力。近年来，在分布式协同探测方面取得了一些研究成果[2-3]，但大多基于有融合中心的组网方式。战场条件下，协同探测环境采用融合中心的处理方法存在如下缺陷[4-6]：一旦融合中心受到攻击，整个网络容易发生崩溃；要被选为融合中心的节点的存储、计算、通信能力往往无法满足日益激增的数据处理量的需求。而由协同探测设备形成无中心的分布式协同探测网络[4-8]则可以避免上述问题，这是由于这种体制更能充分利用整个探测网络所有探测节点的存储、计算和通信能力，同时也具备更高的可靠性[9-11]。

本文重点研究用于协同感知的分布式聚类问题[12-13]，即协同探测时，需要对一些不具有标签的数据按照相似性进行分组，完成无训练数据的未知目标类型的认知任务。然而在无融合中心的情况下，由于各个探测设备无法共享采集到的数据，因此分布式聚类并不是一件容易的工作。对现有的K-Means聚类算法分析后发现，如果各个探测设备能够获得一致的类中心信息，则算法迭代中的归类步骤可在各探测设备中独立完成。因此分布式聚类的难点在于如何在不交换大量数据的前提下获得一致的类中心估计。为解决这一难题，本文提出了一种方法：利用上一轮迭代中获得的暂态类中心信息进行样本归类，仅利用各探测设备上各归类样本值的平均值以及该类样本数构造新颖的类中心一致性估计数学模型；在此基础上，引入辅助变量促进各协同感知设备并行计算并有效保护数据隐私性；最后，通过几个简单的最小二乘计算以及各邻近探测设备之间的信息交换获得一致的类中心和聚类结果。

1 用于协同感知的分布式聚类算法

1.1 集中式K-means聚类算法

集中式K-means聚类算法[12]假设网络中存在某个融合中心可以把各个节点采集或获得的样本收集在一起，然后将这些样本分成K个靠近彼此的不同样本集合。K-Means聚类算法描述如下：

1) 步骤1：初始化K个不同的类中心点{μ(1),μ(2),…,μ(K)}；

k=

(1)

则将样本xn(n=1,…,N)归入集合Sk(k=1,…,K)。

3) 步骤3：利用集合Sk中的Pk个样本计算其平均值作为第k类新的类中心点，即

(2)

4) 步骤4：重复步骤2～3，直至收敛。

1.2 用于协同感知的聚类算法

从以上的集中式聚类算法可以看出，步骤2需要计算样本到各类中心点的距离。如果每个探测设备能够获得类中心点，则步骤2中的任务完全可以在各节点上并行独立完成。然而步骤3中需要计算的类中心点即平均值，需要用到各个不同节点上的同类样本。显然，在不交换或收集各节点测量数据的前提下，无法在分布式网络环境中完成步骤3。

为解决这一难题，本文考虑发展新颖的无需交换数据的分布式类中心更新计算方法，并结合步骤2形成完整的分布式K-Means聚类算法。

式(2)本质上是式(3)所示优化问题的解，即

(3)

如果能够将所有归属于集合Sk的Pk个样本收集在一起，则求平均值容易实现。然而在分布式协同探测环境下，属于集合μ(k)的这Pk个样本存储于M个节点上，即

(4)

(5)

(6)

式中，m′∈Ne(m)表示可以与节点m通信的邻近节点。

交替方向乘子法(alternating direction method of multiplier, ADMM)是现有的分布式计算中的一种常用方法[6]，具备了拉格朗日乘子法的收敛性以及对偶方法的精度。本文考虑基于ADMM完成以上第k类类中心的计算。

基于式(6)，构造如下拉格朗日函数：

(7)

式中：ρ表示步长；λm,m表示对应于等式μ(k,m)=v(k,m)的拉格朗日乘子向量；λm,m′表示对应于等式μ(k,m)=v(k,m′)的拉格朗日乘子向量；符号〈•，•〉表示两个向量的内积。

本文基于以下迭代步骤求解{μ(k,m),v(k,m),λm,m,λm,m′}：

1)步骤1：基于给定的{v(k,m)(t),λm,m(t),λm,m′(t)}，通过求解式(7)获得μ(k,m)为

μ(k,m)(t+1)=

(8)

注意，式(8)可分解为在各节点独立并行求解的M个子问题,即

(9)

显然可以通过最小二乘方法获得式(9)的解，即

(10)

式(10)中，C(m)表示节点m的近邻数。

2) 步骤2：基于给定的{μ(k,m)(t+1),λm,m(t),λm,m′(t)}，通过求解式(7)获得v(k,m)(t+1)，为

(11)

相似地，式(11)也可分解为在各节点独立并行求解的M个子问题,即

(12)

相似地，也可以通过最小二乘方法获得式(12)的闭式解

(13)

3) 步骤3：更新拉格朗日乘子向量{λm,m(t+1),λm,m′(t+1)}：

λm,m(t+1)=λm,m(t)+ρ(μ(k,m)(t+1)-v(k,m)(t+1)),m=1,…,M

(14)

λm,m′(t+1)=λm,m′(t)+ρ(μ(k,m)(t+1)-v(k,m′)(t+1)),m=1,…,M；m′∈Ne(m)

(15)

4) 步骤4：重复步骤1～3直至收敛。

至此得到了分布式K-Means聚类算法，如下所示：

步骤2：令k=1；

步骤3：令q=1，q为一致性内循环迭代次数；

每个节点利用邻近节点交换的信息计算μ(k,m)(q+1)，并传送至邻近节点；

每个节点利用邻近节点交换的信息计算v(k,m)(q+1)，并传送至邻近节点；

每个节点计算拉格朗日乘子向量λm,m(q+1)、λm,m′(q+1)；

步骤5：令k=k+1，q=1,重复步骤3～4直至k=K；

步骤6：t=t+1,重复步骤1～5直至t=T；

2 算法收敛性分析

2.1 K-Means算法收敛性分析

K-Means算法本质上是求解式(16)所示的优化问题

(16)

h(μ(k)(0),rn,k(1))≥h(μ(k)(1),rn,k(1))≥

h(μ(k)(1),rn,k(2))≥…≥h(μ(k)(∞),rn,k(∞))

(17)

因此，步骤2至步骤5的交替优化步骤使得目标函数呈非递增形式下降。

2.2 一致类中心估计算法收敛性分析

μ(k,1)(∞)=μ(k,2)(∞)=…=μ(k,M)(∞)

(18)

因此，上述经过分布式计算方式获得相同的类中心估计值，依然可以保证式(17)成立。显然，式(17)和式(18)支撑上述分布式K-Means聚类的收敛性保证。

3 仿真实验及结果分析

3.1 仿真数据聚类

一个典型的由5个探测设备构成的分布式感知网络如图1所示：每个圆点表示一个设备，由直线连接的两个探测设备之间可以进行通信(距离小于12的节点有连接，可以相互通信；大于12的节点无连接，无法通信)。5个探测设备能够分别采集、存储目标数据和信息，可以和邻近设备进行信息交互，进而对这些数据和信息各自进行处理并提取有用信息，最终完成对多类目标探测信息的协同聚类任务。

图1 5个探测设备组成的无中心协同探测网络Fig.1 Decentralized cooperative network by 5 sensing equipment

通过仿真产生4类高斯分布数据，每类50个数据，共200个数据点，如图2所示。将200个数据点平均分配给5个节点，模拟作为5个探测设备的独立采集数据。在算法运行中，设置T=50,Q=4 000,K=4,M=5,ρ=0.1。

为检验各节点是否获得一致的类中心，定义指标

M1(k,m,m′)=10×log10‖μ(m,k)(Q)-μ(m′,k)(Q)‖2k=1,…,4;m,m′=1，…，5;m≠m′

(19)

为检验收敛后的类中心是否与集中体制下获得的类中心一致，定义指标

k=1,…,4;m=1,…,5

(20)

每个节点均可获得4类类中心估计值。本文将各节点获得的类中心估计值和集中式方式获得的真值进行比较，按照式(20)计算的结果随迭代次数的变化曲线如图3～6所示。从这些结果可以看出，所有误差低于-283 dB,即误差均小于10-14.15，工程应用可认同于0。除此之外，按照{(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}这样的节点对，基于式(19)计算一致性误差，如图7所示。可以看出所有误差均低于-282 dB，即一致性误差均小于10-14，可认同各节点获得的类中心相同。另外需要指出，图7中线段不连续点的数值为0，取20×log10后为负无穷大,图中没有显示出来。基于上述算法，最终获得的聚类结果如图8所示，可见对于这种可分性好的数据，本文算法可以获得100%的聚类识别结果，证实了方法的有效性。

图2 200个仿真数据点Fig.2 200 simulation data points

图3 各节点对第一类类中心估计误差Fig.3 The 1st class center estimation error from all nodes

图4 各节点对第二类类中心估计误差Fig.4 The 2nd class center estimation error from all nodes

图5 各节点对第3类类中心估计误差Fig.5 The 3nd class center estimation error from all nodes

图6 各节点对第四类类中心估计误差Fig.6 The 4th class center estimation error from all nodes

图7 节点对(m,m′)的一致性误差Fig.7 Consensus error for (m,m’) from all nodes

图8 本文算法聚类结果Fig.8 Clustering results by proposed method

3.2 多目标编号关联

该实验考虑多目标编号关联问题。每个探测器依据目标对发射信号的反射时间先后顺序进行编号。由于多个任务机位置不同，接收到的多个目标反射信号时间不同，进而得到的目标编号不同。为便于后续实施对目标的联合打击，需要对目标实施编号关联，获得一致的编号，同时可以利用类中心作为更精确的目标位置估计值，即多目标编号关联问题。

假设探测区域有6个目标(每个目标位置经2 000×rand(1,3)随机产生)：[1 959.0,2 718.8,1 361.6]m，[1 782.4,3 620.4,2 341.0]m，[2 585.2,650.4,895.2]m，[2 837.4,476.0,3 005.0]m，[3 018.8,1 993.4,1 020.4]m，[1 104.2,3 839.0,2 023.8]m。执行探测任务的6个探测器形成如图9所示的环形网络结构，每个探测器探测到的6个目标的标号如表1所示,位置如图10所示(各位置估计在真值基础上添加均值为0、方差为30的高斯白噪声仿真产生)。通常，每个探测器获得的6个目标的编号各不相同，且6个探测器获得的同一目标的位置估计值不同。图11给出了分布式聚类结果，此时各个探测器获得一致的目标编号，同时获得了6类聚类中心[1 956.5,2 716.8,1 362.5]m，[1 783.0,3 612.4,2 338.9]m，[2 587.8,643.3,891.1]m，[2 834.6,483.2,3 004.7]m，[3 018.3,1 996.0,1 021.3]m，[1 097.1,3 836.1,2 029.6]m，改善了目标估计精度，可为后续6个探测器对6个目标实施联合打击提供重要依据。

表1 各探测器探测目标编号Tab.1 The target numbers of each sensor

图9 环形网络示意图Fig.9 Ring network

图10 6个目标位置估计值Fig.10 6 target position estimates

图11 聚类结果Fig.11 Clustering result

4 结束语

本文提出了一种有效利用各协同设备的存储、计算、通信能力且在不交换测量数据的前提下实现协同感知的聚类方法。通过构造一致性类中心计算数据模型，引入辅助变量促进各协同感知设备并行计算自身采集的数据，有效保护数据隐私性，最终所有感知设备获得一致的类中心和聚类结果。实验结果证实了本文所提方法的有效性，特别是在解决协同感知多目标编号关联问题时，不仅改善了多目标定位精度，还使得各无人机获得一致编号，有利于执行后续精确打击任务。后续研究将考虑如何减少通信数据量，以保证执行任务的实时性。