態勢估計中的目標分群算法設計與實現

張冬寧，艾 偉

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

態勢估計中的目標分群算法設計與實現

張冬寧，艾 偉

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

針對態勢估計中的目標分群問題，分析了目標的位置、運動狀態和屬性對分群結果的影響，建立了目標相似度計算模型，并提出了分群策略，包括群的形成、分裂和合并等。采用面向對象軟件設計思想建立了分群對象模型，分析了對象間關系。給出了分群算法的主體流程，并對其中的關鍵步驟進行了詳細的說明。開發了目標分群算法模塊，實現了對數據的預處理、目標群的更新維護、群屬性的計算等功能，通過仿真試驗，調整目標分群影響因子及加權因子，得到了較好的分群效果，驗證了文中方法的可行性和正確性。

目標分群；群分裂；群合并；目標相似度

0 引言

目標分群是態勢估計中的首要任務，能夠為進一步識別敵方行為意圖、判斷敵方威脅情況，以及分析敵方作戰協同關系提供有力依據。目標分群是在完成戰場空間內的目標航跡融合和屬性識別的基礎上，綜合考慮目標位置、屬性和運動狀態等信息，自動實現目標的分組聚類，將類型相近、運動狀態相近和執行相同作戰任務或對我方具有相同威脅的目標進行合并，簡化戰場情況，給指揮員提供更為簡單的戰場視圖，輔助指揮員進行指揮決策[1]。

很多專家對態勢估計中的目標分群問題進行了深入研究，如基于知識和最鄰近法的研究[2]、基于模糊理論的研究[3]、基于證據理論的研究[4]和基于相似性測度模型的研究[5]等。本文在對其分析的基礎上，建立了一種基于多屬性的目標相似度計算模型，并給出了群形成、分裂、合并算法，以及群的圖形化顯示方法。通過軟件實現和仿真試驗，驗證了該算法可快速有效地實現目標分群。

1 問題分析

式中，ID為目標編號；Attr為目標的敵我屬性(包括敵、我、友、中立、不明和其他)；Type為目標類別(包括空、地和水)；Model為目標型號；Lon為目標在某時刻的經度；Lat為緯度；Height為高度；Vx為目標在經度方向上的速度分量；Vy為目標在緯度方向上的速度分量；Vz為目標在高度方向上的速度分量。對于?Em∈E,En∈E，都有IDEm≠IDEn。

2 算法設計

2.1 目標相似度計算

目標分群以相似性為基礎[8]，首先需要計算目標之間的相似度。目標的屬性對目標相似度的影響不同，本文稱其為影響因子，并且各屬性取值對于分群結果的影響也是不完全一致的。例如敵我屬性為敵的和敵我屬性為我的目標，肯定不能分為一群，而敵我屬性為我的和敵我屬性為友的，可能是一群。另一個例子，當目標轉彎時，一個群內的目標不會同時轉彎，總會有先后次序的，這就會造成在同一時刻，一個群內的目標在3個方向上的速度分量會有較大差別。因此，需要對影響因子再設定加權因子，來平衡群內目標的差異。

目標相似度計算方法如下：

① 根據參與相似度計算的目標屬性，包括敵我屬性、目標類別、目標型號、經度、緯度、高度、速度在經度方向的分量、速度在緯度方向的分量以及速度在高度方向的分量，建立目標相似度矩陣為：

相似度矩陣S的每個元素依次為敵我屬性影響因子、目標類別影響因子、目標型號影響因子、經度影響因子、緯度影響因子、高度影響因子、速度在經度方向上的分量影響因子、速度在緯度方向的分量影響因子以及速度在高度方向的分量影響因子，代表目標各屬性的取值對目標相似度計算的貢獻大小。且所有影響因子的和為100，即sattr+stype+smodel+slon+slat+sheight+svx+svy+svz=100。

② 對敵我屬性(敵、我、友、中立和不明)的各取值建立加權矩陣為：

含義為2個目標的敵我屬性均為敵、或我、或友、或中立、或不明時，加權因子為1；一個為我，另一個為友時，加權因子為0.8；一個為不明，另一個為敵、或友、或中立時，加權因子為0.5；其他情況的加權因子均為0。

③ 對目標類別(空、地和水)的各取值建立加權矩陣為：

含義為2個目標的目標類別均為空、或地、或水時，加權因子為1；其他情況的加權因子均為0。

⑥ 對2個目標的緯度差、高度差(m)、各方向的速度差(km/h)設置加權因子的方法同⑤。

⑦ 對目標數據進行預處理，統一量綱。

2.2 算法流程

本文所用目標分群算法的基本思想是對航跡融合后的每一個目標航跡數據，先獲取其所屬群，判斷該群是否分裂，再判斷與其它群或離散目標是否合并。具體算法流程，如圖1所示。

圖1 目標分群算法流程

在判斷群是否分裂時，先將群內目標看作未分群的離散目標集合，再對這些目標進行遍歷計算，算法步驟如下：

步驟1：找到第一個(下一個)離散目標；

步驟2：從該離散目標向后尋找到能與該離散目標合并的離散目標，并記做一個群；

步驟3：在該群內部遍歷，找到群內的下一個目標；從該目標向后尋找到能與該目標合并的離散目標，記錄到該群內。

步驟1～步驟3循環，直到遍歷完離散目標集合，若新群內目標與原群不一樣，則判定為群分裂。

在判斷群是否合并時，只要Gj和Gk滿足條件?Em∈Gj,?En∈Gk,s.t.SCOREEmEn>Grouplimit，則2個群可合并。

2.3 算法比較

國內外關于目標分群的算法主要是利用目標或群之間的空間距離作為聚類依據，在復雜戰場環境中，只考慮空間距離是不夠的，還必須綜合考慮目標群體的多屬性。本算法在計算目標相似度時，通過設定目標各屬性的影響因子，明確了參與計算的各種屬性對目標相似度的貢獻；對各屬性建立加權矩陣，通過設定屬性各種取值的加權因子，明確了屬性的各種取值對屬性相似度的貢獻；再通過影響因子和加權因子綜合計算得出目標的相似度得分。計算中利用了較多的目標屬性，并且能夠根據實際使用環境靈活調整影響因子和加權因子，從而提高相似度計算的準確性，既能確保相似目標不被錯判，又能平衡目標之間的差異，具有較好的實用性。

3 軟件實現

3.1 建立對象模型

目標分群問題涉及到的主要業務對象包括：目標元素CElement、目標元素集合CElementSet、目標群CGroup、目標群集合CGroupSet、輸入的數據報DataPack和分群計算的控制CGroupingCtrl，目標分群對象之間的關系如圖2所示。

圖2 目標分群對象模型

3.2 數據預處理

對于輸入的數據報，首先進行預處理，主要包括以下幾方面：

① 野值剔除。將接收的數據報DataPack進行解包，判斷目標的各運動狀態值及各屬性值是否在值域范圍內，并在本次作戰范圍內，若不在，則剔除。

② 數據校準。根據接口規定，若輸入數據為航向和航速，則校準為3個方向的速度分量。

③ 單位轉換。將空中目標、海上目標及陸地目標的速度單位統一轉換為km/h。

④ 目標對象更新。根據輸入的數據，新建或更新目標對象各屬性值。

3.3 群的動態維護

創建3個目標元素集合CElementSet的對象，分別為空中目標集合airElementSet、水面目標集合seaElementSet和陸地目標集合landElementSet。對于每一個目標元素CElement，根據目標類型存放到相應的目標集合中。

當計算出群后，創建目標群CGroup的對象，并將該群對象加入到目標群集合CGroupSet中。將群內目標對象指針加入到該群的鏈表中，并設定每一個目標對象的群指針為該群。

群更新時，將更新群的標識回調給主程序，主程序可以根據接收的群標識獲得如下信息：

① 調用CGroup::getCircumPolygon()函數，獲得群的外接凸多邊形定位點；

② 調用CGroup::getGroupCenter()函數，獲得群重心點；

③ 調用CGroup::getGroupDirection()函數，獲得群方向；

④ 調用CGroup::getElementInGroup()函數，獲得群內目標。

3.4 群外接凸多邊形計算

步驟1：找出點集P中y軸最小的點p0，該點必為凸包的頂點；

步驟5：初始化堆棧Hs，令Hs(0)=pn-1，Hs(1)=p0；初始化堆棧指針Hsp使其指向p0，數組P′的下標記為k，令k=0；

步驟6：若k≥n，算法結束；

步驟7：判斷Hs(i)、Hs(j)和Hs(l)三點構成的路徑是左旋還是右旋，若為左旋，令Hsp=Hsp+1，Hs(Hsp)=P′(k)，k=k+1，然后跳轉到步驟6；若為右旋，則令Hsp=Hsp-1，然后跳轉到步驟6。

3.5 群圖形顯示

針對上述目標分群算法進行了軟件實現。使用二維仿真數據來模擬敵方空中編隊的聯合作戰場景。當所關注的區域里出現較多目標時，用戶難以確定要關注的目標，在顯示時也顯得比較復雜凌亂，仿真目標圖形顯示如圖3所示，以圓形符號表示空中單個目標。

圖3 仿真目標圖形顯示

經過對目標進行分群處理后，出現了5個目標群，作戰環境中的重要情況可以由目標群的運動情況來判斷得出。目標群的圖形顯示方式有2種[12]：一種為在群中心上顯示一個帶方向的群符號，并用數字顯示架次數，這種方式更利于簡化整體態勢展現，如圖4所示；另一種為顯示群的外接凸多邊形，這種方式有利于展現目標隊形，如圖5所示。

圖4 群中心簡化圖形顯示

圖5 群外接多邊形圖形顯示

4 結束語

目標分群過程中，不同的影響因子和加權因子對分群結果的影響較大，因此需要大量數據，并且是各種類型數據的仿真訓練來確定較為合理的影響因子和加權因子。通過仿真試驗，本文的方法能夠較為準確地對目標進行分群。但由于仿真腳本只包含二維數據，沒有在高度上進行充分訓練，并且仿真場景中目標的飛行路線較有規律，沒有包含更復雜的行動路線。這些將在下一步工作中繼續研究。

[1] 張 芬，賈 則，生佳根，等.態勢估計中目標分群方法的研究[J].電光與控制，2008，15(4)：21-23，69.

[2] 李偉生，王寶樹.態勢估計的目標編群問題研究[J].計算機科學，2003，30(8)：136-138.

[3] 李偉生，王寶樹.態勢估計中基于模糊集理論的目標編群方法[J].系統工程與電子技術，2005，27(3)：1 235-1 237.

[4] 王 錚，劉高峰.基于證據理論態勢估計中的目標分組方法[J].艦船電子工程，2006，26(2)：46-48.

[5] 劉潔莉，韓元杰，董彥佼.態勢評估中的目標編群問題研究[J].光電與控制，2010，17(1)：26-29.

[6] 龍真真，張 策，王維平.基于層次聚類態勢估計中的目標分群算法[J].彈箭與制導學報，2009，29(3)：209-211.

[7] 黃 雷，郭 雷.一種面向態勢估計中分群問題的聚類方法[J].計算機應用，2006，26(5)：1 109-1 110.

[8] 張松良，王付明，魯 柯，等.城市戰場目標分群的組合聚類方法[J].指揮控制與仿真，2009，31(5)：37-41.

[9] GRAHAM R L.An Efficient Algorithm for Determining the Convex Hull of A Finite Planar Set[J].Information Processing Letters，1972，1(4)：132-133.

[10]JARVIS R A.On the Identification of The Convex Hull of a Finite Set of Points in The Plane[J].Information Processing Letters,1973,2(1)：18-21.

[11]毛 鵬.快速凸包計算實現及其應用[D].西安：電子科技大學，2013.

[12]段同樂，張冬寧.二叉樹多分類SVM在目標分群中的應用[J].無線電工程，2015，45(6)：88-91.

張冬寧 女，(1981—)，高級工程師。主要研究方向：智能信息處理。

艾 偉 男，(1977—)，高級工程師。主要研究方向：信息融合、態勢仿真。

Design and Realization of Target Grouping in Situation Assessment

ZHANG Dong-ning,AI Wei

(The54thResearchInstituteofCECT,ShijiazhuangHebei050081,China)

Situation assessment is one component of data fusion.And target grouping is one of the main tasks of situation assessment.The factors of target,such as position and attribute,which influence the result of grouping,are analyzed.The grouping strategy is also presented for initialization,split,and combination.We used object-oriented technology to build grouping object model.The algorithms are brought forward for calculating target grouping.Particularly,the key steps in algorithms are described.We developed grouping dynamic link library program.The program can provide pretreatment of data,group updating,and group attribute calculation.The algorithm parameters and weighting factors are adjusted by simulation experimentation.Simulation results validate the feasibility and correctness of the grouping algorithms.

target grouping;group split;group combination;situation assessment;data fusion

10.3969/j.issn.1003-3106.2016.11.11

張冬寧,艾 偉.態勢估計中的目標分群算法設計與實現[J].無線電工程,2016,46(11):42-46.

2016-08-13

國家部委基金資助項目。

TP391.4

A

1003-3106(2016)11-0042-05