用于協(xié)同感知的分布式聚類方法研究

李 晨，梁小溪，梁軍利，劉睿愷，葉中華,3

(1. 上海機(jī)電工程研究所，上海 201109； 2. 西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710072； 3. 西安理工大學(xué) 自動化學(xué)院，陜西 西安 710048)

0 引 言

未來“信息化、網(wǎng)絡(luò)化、智能化”的作戰(zhàn)要求將使新一代導(dǎo)彈的作戰(zhàn)方式產(chǎn)生極大變化。網(wǎng)絡(luò)化分布式協(xié)同作戰(zhàn)具有高度集成、自組織、自決策、效費(fèi)比高等特點(diǎn)，勢必將成為未來戰(zhàn)場上行之有效的作戰(zhàn)模式[1]。這種作戰(zhàn)模式對新一代導(dǎo)彈的探測感知能力提出了更高的要求，不僅要求單彈具有較高的探測能力，還要求多彈具有分布式協(xié)同探測能力。近年來，在分布式協(xié)同探測方面取得了一些研究成果[2-3]，但大多基于有融合中心的組網(wǎng)方式。戰(zhàn)場條件下，協(xié)同探測環(huán)境采用融合中心的處理方法存在如下缺陷[4-6]：一旦融合中心受到攻擊，整個(gè)網(wǎng)絡(luò)容易發(fā)生崩潰；要被選為融合中心的節(jié)點(diǎn)的存儲、計(jì)算、通信能力往往無法滿足日益激增的數(shù)據(jù)處理量的需求。而由協(xié)同探測設(shè)備形成無中心的分布式協(xié)同探測網(wǎng)絡(luò)[4-8]則可以避免上述問題，這是由于這種體制更能充分利用整個(gè)探測網(wǎng)絡(luò)所有探測節(jié)點(diǎn)的存儲、計(jì)算和通信能力，同時(shí)也具備更高的可靠性[9-11]。

本文重點(diǎn)研究用于協(xié)同感知的分布式聚類問題[12-13]，即協(xié)同探測時(shí)，需要對一些不具有標(biāo)簽的數(shù)據(jù)按照相似性進(jìn)行分組，完成無訓(xùn)練數(shù)據(jù)的未知目標(biāo)類型的認(rèn)知任務(wù)。然而在無融合中心的情況下，由于各個(gè)探測設(shè)備無法共享采集到的數(shù)據(jù)，因此分布式聚類并不是一件容易的工作。對現(xiàn)有的K-Means聚類算法分析后發(fā)現(xiàn)，如果各個(gè)探測設(shè)備能夠獲得一致的類中心信息，則算法迭代中的歸類步驟可在各探測設(shè)備中獨(dú)立完成。因此分布式聚類的難點(diǎn)在于如何在不交換大量數(shù)據(jù)的前提下獲得一致的類中心估計(jì)。為解決這一難題，本文提出了一種方法：利用上一輪迭代中獲得的暫態(tài)類中心信息進(jìn)行樣本歸類，僅利用各探測設(shè)備上各歸類樣本值的平均值以及該類樣本數(shù)構(gòu)造新穎的類中心一致性估計(jì)數(shù)學(xué)模型；在此基礎(chǔ)上，引入輔助變量促進(jìn)各協(xié)同感知設(shè)備并行計(jì)算并有效保護(hù)數(shù)據(jù)隱私性；最后，通過幾個(gè)簡單的最小二乘計(jì)算以及各鄰近探測設(shè)備之間的信息交換獲得一致的類中心和聚類結(jié)果。

1 用于協(xié)同感知的分布式聚類算法

1.1 集中式K-means聚類算法

集中式K-means聚類算法[12]假設(shè)網(wǎng)絡(luò)中存在某個(gè)融合中心可以把各個(gè)節(jié)點(diǎn)采集或獲得的樣本收集在一起，然后將這些樣本分成K個(gè)靠近彼此的不同樣本集合。K-Means聚類算法描述如下：

1) 步驟1：初始化K個(gè)不同的類中心點(diǎn){μ(1),μ(2),…,μ(K)}；

k=

(1)

則將樣本xn(n=1,…,N)歸入集合Sk(k=1,…,K)。

3) 步驟3：利用集合Sk中的Pk個(gè)樣本計(jì)算其平均值作為第k類新的類中心點(diǎn)，即

(2)

4) 步驟4：重復(fù)步驟2～3，直至收斂。

1.2 用于協(xié)同感知的聚類算法

從以上的集中式聚類算法可以看出，步驟2需要計(jì)算樣本到各類中心點(diǎn)的距離。如果每個(gè)探測設(shè)備能夠獲得類中心點(diǎn)，則步驟2中的任務(wù)完全可以在各節(jié)點(diǎn)上并行獨(dú)立完成。然而步驟3中需要計(jì)算的類中心點(diǎn)即平均值，需要用到各個(gè)不同節(jié)點(diǎn)上的同類樣本。顯然，在不交換或收集各節(jié)點(diǎn)測量數(shù)據(jù)的前提下，無法在分布式網(wǎng)絡(luò)環(huán)境中完成步驟3。

為解決這一難題，本文考慮發(fā)展新穎的無需交換數(shù)據(jù)的分布式類中心更新計(jì)算方法，并結(jié)合步驟2形成完整的分布式K-Means聚類算法。

式(2)本質(zhì)上是式(3)所示優(yōu)化問題的解，即

(3)

如果能夠?qū)⑺袣w屬于集合Sk的Pk個(gè)樣本收集在一起，則求平均值容易實(shí)現(xiàn)。然而在分布式協(xié)同探測環(huán)境下，屬于集合μ(k)的這Pk個(gè)樣本存儲于M個(gè)節(jié)點(diǎn)上，即

(4)

(5)

(6)

式中，m′∈Ne(m)表示可以與節(jié)點(diǎn)m通信的鄰近節(jié)點(diǎn)。

交替方向乘子法(alternating direction method of multiplier, ADMM)是現(xiàn)有的分布式計(jì)算中的一種常用方法[6]，具備了拉格朗日乘子法的收斂性以及對偶方法的精度。本文考慮基于ADMM完成以上第k類類中心的計(jì)算。

基于式(6)，構(gòu)造如下拉格朗日函數(shù)：

(7)

式中：ρ表示步長；λm,m表示對應(yīng)于等式μ(k,m)=v(k,m)的拉格朗日乘子向量；λm,m′表示對應(yīng)于等式μ(k,m)=v(k,m′)的拉格朗日乘子向量；符號〈?，?〉表示兩個(gè)向量的內(nèi)積。

本文基于以下迭代步驟求解{μ(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)可分解為在各節(jié)點(diǎn)獨(dú)立并行求解的M個(gè)子問題,即

(9)

顯然可以通過最小二乘方法獲得式(9)的解，即

(10)

式(10)中，C(m)表示節(jié)點(diǎn)m的近鄰數(shù)。

2) 步驟2：基于給定的{μ(k,m)(t+1),λm,m(t),λm,m′(t)}，通過求解式(7)獲得v(k,m)(t+1)，為

(11)

相似地，式(11)也可分解為在各節(jié)點(diǎn)獨(dú)立并行求解的M個(gè)子問題,即

(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：重復(fù)步驟1～3直至收斂。

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

步驟2：令k=1；

步驟3：令q=1，q為一致性內(nèi)循環(huán)迭代次數(shù)；

每個(gè)節(jié)點(diǎn)利用鄰近節(jié)點(diǎn)交換的信息計(jì)算μ(k,m)(q+1)，并傳送至鄰近節(jié)點(diǎn)；

每個(gè)節(jié)點(diǎn)利用鄰近節(jié)點(diǎn)交換的信息計(jì)算v(k,m)(q+1)，并傳送至鄰近節(jié)點(diǎn)；

每個(gè)節(jié)點(diǎn)計(jì)算拉格朗日乘子向量λm,m(q+1)、λm,m′(q+1)；

步驟5：令k=k+1，q=1,重復(fù)步驟3～4直至k=K；

步驟6：t=t+1,重復(fù)步驟1～5直至t=T；

2 算法收斂性分析

2.1 K-Means算法收斂性分析

K-Means算法本質(zhì)上是求解式(16)所示的優(yōu)化問題

(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的交替優(yōu)化步驟使得目標(biāo)函數(shù)呈非遞增形式下降。

2.2 一致類中心估計(jì)算法收斂性分析

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

(18)

因此，上述經(jīng)過分布式計(jì)算方式獲得相同的類中心估計(jì)值，依然可以保證式(17)成立。顯然，式(17)和式(18)支撐上述分布式K-Means聚類的收斂性保證。

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 仿真數(shù)據(jù)聚類

一個(gè)典型的由5個(gè)探測設(shè)備構(gòu)成的分布式感知網(wǎng)絡(luò)如圖1所示：每個(gè)圓點(diǎn)表示一個(gè)設(shè)備，由直線連接的兩個(gè)探測設(shè)備之間可以進(jìn)行通信(距離小于12的節(jié)點(diǎn)有連接，可以相互通信；大于12的節(jié)點(diǎn)無連接，無法通信)。5個(gè)探測設(shè)備能夠分別采集、存儲目標(biāo)數(shù)據(jù)和信息，可以和鄰近設(shè)備進(jìn)行信息交互，進(jìn)而對這些數(shù)據(jù)和信息各自進(jìn)行處理并提取有用信息，最終完成對多類目標(biāo)探測信息的協(xié)同聚類任務(wù)。

圖1 5個(gè)探測設(shè)備組成的無中心協(xié)同探測網(wǎng)絡(luò)Fig.1 Decentralized cooperative network by 5 sensing equipment

通過仿真產(chǎn)生4類高斯分布數(shù)據(jù)，每類50個(gè)數(shù)據(jù)，共200個(gè)數(shù)據(jù)點(diǎn)，如圖2所示。將200個(gè)數(shù)據(jù)點(diǎn)平均分配給5個(gè)節(jié)點(diǎn)，模擬作為5個(gè)探測設(shè)備的獨(dú)立采集數(shù)據(jù)。在算法運(yùn)行中，設(shè)置T=50,Q=4 000,K=4,M=5,ρ=0.1。

為檢驗(yàn)各節(jié)點(diǎn)是否獲得一致的類中心，定義指標(biāo)

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

(19)

為檢驗(yàn)收斂后的類中心是否與集中體制下獲得的類中心一致，定義指標(biāo)

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

(20)

每個(gè)節(jié)點(diǎn)均可獲得4類類中心估計(jì)值。本文將各節(jié)點(diǎn)獲得的類中心估計(jì)值和集中式方式獲得的真值進(jìn)行比較，按照式(20)計(jì)算的結(jié)果隨迭代次數(shù)的變化曲線如圖3～6所示。從這些結(jié)果可以看出，所有誤差低于-283 dB,即誤差均小于10-14.15，工程應(yīng)用可認(rèn)同于0。除此之外，按照{(diào)(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}這樣的節(jié)點(diǎn)對，基于式(19)計(jì)算一致性誤差，如圖7所示?？梢钥闯鏊姓`差均低于-282 dB，即一致性誤差均小于10-14，可認(rèn)同各節(jié)點(diǎn)獲得的類中心相同。另外需要指出，圖7中線段不連續(xù)點(diǎn)的數(shù)值為0，取20×log10后為負(fù)無窮大,圖中沒有顯示出來?；谏鲜鏊惴?，最終獲得的聚類結(jié)果如圖8所示，可見對于這種可分性好的數(shù)據(jù)，本文算法可以獲得100%的聚類識別結(jié)果，證實(shí)了方法的有效性。

圖2 200個(gè)仿真數(shù)據(jù)點(diǎn)Fig.2 200 simulation data points

圖3 各節(jié)點(diǎn)對第一類類中心估計(jì)誤差Fig.3 The 1st class center estimation error from all nodes

圖4 各節(jié)點(diǎn)對第二類類中心估計(jì)誤差Fig.4 The 2nd class center estimation error from all nodes

圖5 各節(jié)點(diǎn)對第3類類中心估計(jì)誤差Fig.5 The 3nd class center estimation error from all nodes

圖6 各節(jié)點(diǎn)對第四類類中心估計(jì)誤差Fig.6 The 4th class center estimation error from all nodes

圖7 節(jié)點(diǎn)對(m,m′)的一致性誤差Fig.7 Consensus error for (m,m’) from all nodes

圖8 本文算法聚類結(jié)果Fig.8 Clustering results by proposed method

3.2 多目標(biāo)編號關(guān)聯(lián)

該實(shí)驗(yàn)考慮多目標(biāo)編號關(guān)聯(lián)問題。每個(gè)探測器依據(jù)目標(biāo)對發(fā)射信號的反射時(shí)間先后順序進(jìn)行編號。由于多個(gè)任務(wù)機(jī)位置不同，接收到的多個(gè)目標(biāo)反射信號時(shí)間不同，進(jìn)而得到的目標(biāo)編號不同。為便于后續(xù)實(shí)施對目標(biāo)的聯(lián)合打擊，需要對目標(biāo)實(shí)施編號關(guān)聯(lián)，獲得一致的編號，同時(shí)可以利用類中心作為更精確的目標(biāo)位置估計(jì)值，即多目標(biāo)編號關(guān)聯(lián)問題。

假設(shè)探測區(qū)域有6個(gè)目標(biāo)(每個(gè)目標(biāo)位置經(jīng)2 000×rand(1,3)隨機(jī)產(chǎn)生)：[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。執(zhí)行探測任務(wù)的6個(gè)探測器形成如圖9所示的環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)，每個(gè)探測器探測到的6個(gè)目標(biāo)的標(biāo)號如表1所示,位置如圖10所示(各位置估計(jì)在真值基礎(chǔ)上添加均值為0、方差為30的高斯白噪聲仿真產(chǎn)生)。通常，每個(gè)探測器獲得的6個(gè)目標(biāo)的編號各不相同，且6個(gè)探測器獲得的同一目標(biāo)的位置估計(jì)值不同。圖11給出了分布式聚類結(jié)果，此時(shí)各個(gè)探測器獲得一致的目標(biāo)編號，同時(shí)獲得了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，改善了目標(biāo)估計(jì)精度，可為后續(xù)6個(gè)探測器對6個(gè)目標(biāo)實(shí)施聯(lián)合打擊提供重要依據(jù)。

表1 各探測器探測目標(biāo)編號Tab.1 The target numbers of each sensor

圖9 環(huán)形網(wǎng)絡(luò)示意圖Fig.9 Ring network

圖10 6個(gè)目標(biāo)位置估計(jì)值Fig.10 6 target position estimates

圖11 聚類結(jié)果Fig.11 Clustering result

4 結(jié)束語

本文提出了一種有效利用各協(xié)同設(shè)備的存儲、計(jì)算、通信能力且在不交換測量數(shù)據(jù)的前提下實(shí)現(xiàn)協(xié)同感知的聚類方法。通過構(gòu)造一致性類中心計(jì)算數(shù)據(jù)模型，引入輔助變量促進(jìn)各協(xié)同感知設(shè)備并行計(jì)算自身采集的數(shù)據(jù)，有效保護(hù)數(shù)據(jù)隱私性，最終所有感知設(shè)備獲得一致的類中心和聚類結(jié)果。實(shí)驗(yàn)結(jié)果證實(shí)了本文所提方法的有效性，特別是在解決協(xié)同感知多目標(biāo)編號關(guān)聯(lián)問題時(shí)，不僅改善了多目標(biāo)定位精度，還使得各無人機(jī)獲得一致編號，有利于執(zhí)行后續(xù)精確打擊任務(wù)。后續(xù)研究將考慮如何減少通信數(shù)據(jù)量，以保證執(zhí)行任務(wù)的實(shí)時(shí)性。