基于并查集的低復雜度模糊聚類信號分選算法

張悅 司偉建

（1.哈爾濱工程大學信息與通信工程學院，哈爾濱 150001；2.哈爾濱工程大學先進船舶通信與信息技術(shù)工業(yè)和信息化部重點實驗室，哈爾濱 150001）

引 言

雷達信號分選是雷達對抗系統(tǒng)的關(guān)鍵處理過程，也是雷達對抗信息處理的核心內(nèi)容，分選水平是衡量雷達對抗系統(tǒng)和信息處理技術(shù)先進程度的重要標志[1].信號分選方法可分為三類：基于脈間參數(shù)特征的分選方法、基于脈內(nèi)細微特征的分選方法、基于波形匹配的分選方法.其中基于脈間參數(shù)特征的分選方法又可分為基于雷達脈沖重復間隔(pulse repetition interval，PRI)的分選方法與基于多參數(shù)聯(lián)合的分選方法[2].由于現(xiàn)代電子對抗環(huán)境復雜，信號密度越來越大，信號時域交疊嚴重[3]，這使得傳統(tǒng)的基于PRI的信號分選方法已無法適應現(xiàn)代電子對抗環(huán)境.同時有學者針對如何提高脈沖丟失，降低信號被正確分選的概率進行研究[4–6].因此發(fā)展出了多參數(shù)聯(lián)合的信號分選方法，其中聚類分選方法是一種基于脈沖信號之間相似性的無監(jiān)督學習方法，由于其無需先驗信息，適用于未知信號環(huán)境中進行信號分選，成為學者們的研究熱點.

眾多學者都對聚類分選算法進行了研究.Gao Li-peng等人提出了基于K-Means動態(tài)聚類與子線性時間算法相結(jié)合的分選算法，通過K-Means對數(shù)據(jù)動態(tài)聚類后，定時對每類數(shù)據(jù)使用子線性時間算法進行分析得到PRI信息，由PRI信息對各類數(shù)據(jù)進行進一步分類，完成信號分選.該方法計算量小，具有很好的實時性[7].Cao Sheng等人提出了基于密度的模糊C均值(fuzzy C-means, FCM)多中心重聚類雷達信號分選(density-based FCM multi-center re-clustering,DFCMRC)算法，該算法結(jié)合了具有噪聲的基于密度的聚類方法(density-based spatial clustering of applications with noise, DBSCAN)和FCM的優(yōu)點，使用基于密度峰值的快速聚類(clustering by fast search and find of density peaks, CFSFDP)算法產(chǎn)生初始化聚類中心，而不是隨機初始化聚類中心.該算法分選結(jié)果優(yōu)于K-Means、FCM等算法[8].Mohaned Giess Shokrallah Ahmed等人提出了一種基于點對稱的雷達分選(point symmetry based radar sorting, PSBRS)算法，使用對稱測量距離(symmetry measure distance)代替歐氏距離，使得該算法能夠處理各種類型的雷達信號，使用交替模糊C均值(alternative FCM, AFCM)初始化距離測量的參考點，降低了噪聲和錯誤分選的影響；同時引入密度濾波，濾除噪聲和雜波.該算法對噪聲和脈沖丟失不敏感，但需要事先確定信號環(huán)境中輻射源數(shù)量[9].張怡霄等人提出了一種基于數(shù)據(jù)場聯(lián)合PRI變換與聚類的雷達信號分選方法，其結(jié)合數(shù)據(jù)場理論、PRI變換與聚類的優(yōu)勢，綜合實現(xiàn)信號分選.該算法不需要人工設置初始條件，可以自動確定聚類數(shù)目，同時對噪聲、脈沖丟失不敏感，但該算法中使用了PRI變換法，計算量大[10].馮鑫等人提出了基于數(shù)據(jù)場的多模雷達信號分選算法，基于數(shù)據(jù)場理論計算數(shù)據(jù)場勢值，選取距最大值最近的樣本數(shù)據(jù)作為初始聚類中心，之后使用傳統(tǒng)的K-Means聚類完成分選.該算法能夠自動獲取合適的初始聚類中心，確定聚類數(shù)目，對參數(shù)交疊的捷變頻信號仍有較好的分選效果，但需要根據(jù)經(jīng)驗設置合適的影響因子[11].吳連慧等人提出了基于改進排序點以識別聚類結(jié)構(gòu)(ordering points to identify the clustering structure,OPTICS)的雷達信號預分選方法，利用OPTICS算法的核心距離和可達距離實現(xiàn)不同密度的信號分選，并采用兩級處理：第一級處理高密度信號，完成信號稀釋；第二級累積并處理低密度信號.與傳統(tǒng)的DBSCAN算法相比，該算法可以分選具有不同密度分布的雷達信號[12].袁澤恒等人對支持向量聚類(support vector clustering, SVC)用于信號分選進行了深入研究，提出了改進加權(quán)SVC的雷達信號分選新方法，針對參數(shù)交疊時分選正確率不高的問題，在SVC和分層互耦分選算法基礎(chǔ)上，利用變精度粗糙集對標準化的雷達信號數(shù)據(jù)進行加權(quán)處理，分析分選結(jié)果構(gòu)建了有效性評價模型，獲得了最佳的分選參數(shù).該算法在參數(shù)嚴重交疊時，分選正確率顯著提高[13].但這些聚類分選算法大都因為邏輯復雜很難實際應用于工程中，或運算量大很難滿足工程中對分選實時性的需求.

劉旭波等人提出的改進模糊聚類分選算法[14]，由于算法原理簡單，且能夠有效完成分選，已廣泛應用于工程項目.但在密集信號環(huán)境中，消耗硬件資源大，且分選實時性無法保證，即算法復雜度高.本文針對該算法復雜度高的問題進行研究，結(jié)合并查集提出基于并查集的低復雜度模糊聚類信號分選算法.首先對復雜信號環(huán)境下雷達對抗設備對信號分選實時性的需求進行分析.之后分析原模糊聚類分選算法復雜度高的原因；結(jié)合并查集，提出基于并查集的低復雜度模糊聚類信號分選算法，給出該算法的流程；分析改進算法的復雜度，通過仿真實驗，對比改進算法與原算法的復雜度.最后將該算法在TMS320C6678開發(fā)板上實現(xiàn)，驗證了該算法可基本滿足實時性的需求.該改進算法基本滿足復雜信號環(huán)境下雷達對抗設備對分選實時性的需求，具有較大的應用價值.

1 信號環(huán)境對分選的實時性需求

以被動雷達尋的器為例，其所面臨的信號環(huán)境典型參數(shù)如下：

1)信號密度為1～2百萬脈沖/秒；

2)脈寬(pulse width, PW)范圍為0.2～50 μs ；

3)載頻(carrier frequency, CF)范圍為2～18 GHz；

4)重頻范圍為500 Hz～100 kHz.

這里取信號密度為1百萬脈沖/秒.考慮到被動雷達尋的器天線可對信號進行空域濾波，假設主波束為錐狀波束，覆蓋± 30°，則主波束對應的立體角為

得到進入被動雷達尋的器的信號密度為

式中， η0為環(huán)境中信號密度.

由重頻范圍可得環(huán)境中最大脈沖重復間隔IPR=2ms，為能夠積累到一定數(shù)目低重頻信號，信號序列截取時長T=500ms.同時由于被動雷達尋的器接收機的頻域選通作用，目前接收機瞬時帶寬可達1 GHz，因此單次分選所需處理的脈沖數(shù)為

2 模糊聚類分選算法

2.1 算法原理

模糊聚類算法的輸入數(shù)據(jù)模型：假設有一個數(shù)據(jù)集合X={x1,x2,···,xn}， 每個數(shù)據(jù)點有m維參數(shù)，即xi={xi1,xi2,···,xim}(i=1,2,···,n).當輸入數(shù)據(jù)為雷達信號脈沖時，n為脈沖個數(shù)，X={x1,x2,···,xn}為脈沖串，m為各脈沖的特征參數(shù)數(shù)量，xi={xi1,xi2,···,xim}中的各特征參數(shù)分別對應脈沖描述中的CF、PW、到達方向(direction of arrival, DOA).

模糊聚類算法通過計算兩脈沖間相似度(或距離)，將任意兩脈沖間的相似度存入相似矩陣R，之后用閾值λ 對相似矩陣進行截取，即將相似度與閾值比較，若相似度高于閾值，則認為兩脈沖為同一類.對截取后的相似矩陣進行提取便可得到聚類信息，進而完成分選.閾值的選取對分選效果至關(guān)重要，本文所使用的閾值確定方法為賀宏洲等人提出的使用F-統(tǒng)計量確定閾值的方法[15].

模糊聚類分選算法流程主要分為下面4步[14].

1)數(shù)據(jù)標準化與歸一化

①標準差變換

經(jīng)過標準差變換后，各維參數(shù)均值為0，標準差為1，消除了信號各維參數(shù)變化范圍與量綱不同對信號分選的影響.

②極差變換

式中， max()和 min(分 別為的最大值與最小值.經(jīng)過極差變換后，信號各維參數(shù)位于[ 0,1].

2)建立模糊相似矩陣R

相似矩陣R是n階方陣，其中各元素是信號序列X={x1,x2,···,xn} 中 兩兩脈沖之間相似系數(shù)rij，rij可通過距離公式得到，這里采用海明距離，也可采用歐式距離等其他距離計算方式.

式中，wk是xi={xi1,xi2,···,xim}的第k個特征的權(quán)重系數(shù)，且滿足.

3)截取相似矩陣R

模糊聚類算法通過設置門限λ 對相似矩陣R進行截取，再根據(jù)截取后的相似矩陣R′中各元素的值判斷行列坐標對應的兩脈沖是否屬于同一類.根據(jù)式(7)，相似系數(shù)rij越接近1，說明數(shù)據(jù)點xi和xj相似度越高.因此當相似系數(shù)rij≥λ時 ，令rij=1，此時可認為數(shù)據(jù)點xi與xj屬于同一類.實際工程中，門限值λ 需根據(jù)實際信號環(huán)境進行選取.

4)使用追蹤法完成聚類信息提取

追蹤法具體步驟如下：

①由于截取后矩陣R′具有對稱性，因此下三角部分包含了脈沖間的聚類信息，記錄該部分中值為1的元素下標，存入數(shù)組A[i][2]中.

②令f=1， 將f存入數(shù)組B[t]中 ，按行搜索A[i][2].若A[i][2]中 有元素與f相等，且同一行另一個元素在B[t]中 不存在，則將這個元素存入B[t]中.

③令f遍歷B[t]，重復步驟②直到?jīng)]有新元素加入B[t]中.

④將B[t]中 的元素按行存入數(shù)組C中，C維數(shù)不定.

⑤令f遍歷1 →n， 取其中任一個C中不存在的元素，重復步驟②～④，直到所有信號分選完成.

2.2 模糊聚類分選算法存在的問題

實際應用中發(fā)現(xiàn)使用模糊聚類分選算法進行分選，在信號數(shù)量較大時，占用大量內(nèi)存，且運行時間較長.內(nèi)存占用高是由于算法運行時需生成n2大小的浮點型相似矩陣.為定位算法運行時間比重最高的模塊，對模糊聚類分選算法中各模塊的運行時間進行了實驗測試.測試環(huán)境：i7-7700K+16GB RAM，Win10+VS2019.

對不同時間長度的信號序列進行分選，統(tǒng)計算法各模塊運行時間比重，結(jié)果見表1.

表1 模糊聚類分選算法各模塊運行時間比重Tab.1 The proportion of running time of each module in fuzzy clustering sorting algorithm

通過分析與測試可以得出，模糊聚類分選算法存在以下問題：

1)生成n2大 小的浮點型相似矩陣，n為信號數(shù)量，占用內(nèi)存空間大；

2)信號數(shù)量n較大(信號序列較長)時，追蹤法提取聚類信息運行時間巨大且比重最高，高達99%.

加速大概率事件遠比優(yōu)化小概率事件更能提高性能.下一節(jié)將介紹并查集這種高效、精妙的數(shù)據(jù)結(jié)構(gòu)，并將其應用于模糊聚類分選算法中，代替追蹤法提取聚類信息，使得模糊聚類分選算法復雜度大大降低.

3 基于并查集的改進模糊聚類分選算法

3.1 并查集

一些應用場景涉及將n個不同的元素劃分為一組不相交的集合.如：確定無向圖的連通分量、求最小生成樹的Kruskal算法以及求最近公共祖先等.這些應用場景都需要對不相交集合進行兩種特別的操作：尋找包含給定元素的唯一集合和合并兩個集合[16].并查集(union-find set)就是一種用于實現(xiàn)這些操作的高效、精妙的數(shù)據(jù)結(jié)構(gòu).

并查集維護了一組不相交的動態(tài)集合S={S1,S2,···,Sk}.每個集合可包含一個或多個元素，并使用其中的某一個元素代表該集合.對于每個元素，可以快速找到該元素所在集合的代表，以及快速合并兩個元素所在的集合.

并查集中有三個對數(shù)據(jù)的基本操作：

1)makeset(n)，創(chuàng)建一個并查集，其中包含n個單元素集合；

2)unionset(e1,e2)，對于給定元素e1與e2，若兩者不屬于同一集合，則將其所在的集合合并；

3)find(e)，對于給定元素e，找到其所屬集合，并返回其所在集合的代表元素.

其中unionset(e1,e2)使用find(e)獲得e1與e2所在集合的代表元素，通過比較代表元素是否相同判斷e1與e2是否屬于同一集合.

并查集使用樹表示集合，樹上的各節(jié)點表示集合中的各元素，樹根對應的元素即該集合的代表元素，如圖1所示.

圖1 并查集的表示Fig.1 The representation of union-find set

圖1中有兩棵樹，對應于兩個集合，分別是{a,b,c,d} ，代表元素為a； {e,f,g} ，代表元素為e.樹中各節(jié)點表示集合中的各元素，箭頭表示指向父節(jié)點的指針(與C/C++語言中的指針概念不同，這里的指針指父節(jié)點在數(shù)組中的位置序號)，根節(jié)點指針指向自身，表示其沒有父節(jié)點.查找時沿著各節(jié)點的父節(jié)點不斷向上查找，直到找到根節(jié)點，即該集合的代表元素.

由此可以使用一個長度為n的整型數(shù)組存儲各元素，創(chuàng)建并查集時makeset(n)構(gòu)造出如圖2所示的森林，每個元素都是一個集合，其代表元素為自身，各樹只有根節(jié)點.

圖2 并查集構(gòu)造Fig.2 The construction of union-find set

當進行find(e)操作時，若每次都沿著元素e的父節(jié)點向上進行查找，則查找的時間復雜度為樹高.為降低時間復雜度，可以使用一種簡單高效的策略——路徑壓縮，即在每次查找過程中，將查找路徑上的各節(jié)點直接指向根節(jié)點，如圖3所示.

圖3 路徑壓縮Fig.3 Path compression

最后是歸并操作unionset(e1,e2)，合并兩個集合時，只需將一棵樹的根節(jié)點指針指向另一棵樹的根節(jié)點即可，如圖4所示.

圖4 集合歸并Fig.4 Collections are combined

為降低對合并后集合進行查找時的復雜度，采用啟發(fā)式策略——按秩歸并，即將較矮的樹的根節(jié)點的指針指向較高的樹的根節(jié)點，秩即樹高.也可以使用樹的規(guī)模作為秩，即將節(jié)點少的樹的根節(jié)點指針指向節(jié)點較多的樹的根節(jié)點.

關(guān)于并查集時間復雜度，有如下引理[16].

令T(M,N)為 交錯執(zhí)行M(≥N)次帶路徑壓縮的查找和N?1次按秩歸并的最壞情況時間.則存在正常數(shù)k1和k2，使得

式中， α(M,N)與Ackerman函數(shù)有關(guān)，Ackerman函數(shù)表達式為

經(jīng)數(shù)學家證明：

式中， l b?N為Ackerman反函數(shù)，其值為對N求對數(shù)直到結(jié)果小于等于1的次數(shù).

經(jīng)過上述分析可知，使用并查集可以在常數(shù)時間內(nèi)完成對集合的查詢或合并操作，即對集合進行單次查詢或合并操作的時間復雜度為O(1).使用并查集只需長度為n的數(shù)組便可表示所有脈沖，n為脈沖數(shù)量，則空間復雜度為O(n).

3.2 改進方案

將雷達信號聚類分選問題看作求無向圖的連通分量問題.首先將所有數(shù)據(jù)點看作一幅圖中的孤立點，如圖5(a)所示，其對應的并查集示意圖如圖5(b)所示.

若脈沖1與脈沖4為一類，則將圖5(a)中對應節(jié)點連通，此時對集合1與集合4進行歸并，結(jié)果如圖6所示.

圖5 數(shù)據(jù)集初始化Fig.5 The initialization of data set

圖6 脈沖1與脈沖4屬于一類時的歸并結(jié)果Fig.6 The combined result when pulse 1 and pulse 4 belong to one category

假設圖5(a)中脈沖1、4、7為一類，脈沖2、3、5、6為一類，重復上述操作，直到對任意兩脈沖的歸并均已完成即完成分選，分選結(jié)果如圖7所示.

圖7 分選結(jié)果Fig.7 The sorting results of pulses

圖7為分選結(jié)果，可通過如下方式從并查集中查詢分選結(jié)果并輸出：

1)遍歷并查集，找到代表元素(指針指向自身)，并對其分配類別號；

2)遍歷并查集，各元素的類別號與其所在集合代表元素相同.

經(jīng)過此步驟得到分類結(jié)果，類別1：脈沖1、4、7；類別2：脈沖2、3、5、6.

基于上述思想，使用并查集對模糊聚類分選算法做出如下改進：

1)使用并查集代替追蹤法聚類，降低時間復雜度；

2)不生成相似矩陣，直接計算兩脈沖間相似度，相似度高于閾值后，對信號集合完成歸并操作，降低空間復雜度.

綜上，基于并查集的改進模糊聚類分選算法流程如下：

1)數(shù)據(jù)標準化與歸一化；

2)計算兩脈沖間相似度；

3)若相似度高于閾值，對信號進行歸并；

4)若存在兩脈沖沒有進行相似度計算，轉(zhuǎn)入步驟2；

5)遍歷并查集，找到代表元素(指針指向自身)，并對其分配類別號；

6)遍歷并查集，各元素的類別號與其所在集合代表元素相同.

基于并查集改進的模糊聚類分選算法流程圖如圖8所示.

圖8 基于并查集的改進模糊聚類分選算法流程圖Fig.8 The flowchart of improved fuzzy clustering sorting algorithm based on union-find set

3.3 算法復雜度對比

由原模糊聚類分選算法(下文稱原算法)可知，算法運行時生成大小為n2的浮點型相似矩陣，其空間復雜度為O(n2).其中使用追蹤法提取聚類信息算法邏輯過于復雜，無法直接分析其時間復雜度.

基于并查集的改進模糊聚類分選算法(下文稱改進算法)運行時，僅需長度為n的整型數(shù)組，其空間復雜度為O(n).下面對其時間復雜度進行分析：

1)構(gòu)造并查集.構(gòu)造并查集時僅需對數(shù)組進行一遍遍歷，使其各元素指針指向自身即可，時間復雜度為O(n).

2)并查集聚類.需計算任意兩脈沖間相似度，并對相似度高于閾值的兩脈沖進行歸并，最多需n2/2次歸并，時間復雜度為O(n2).

3)聚類結(jié)果輸出.需遍歷兩次數(shù)組，即需對數(shù)組中的各元素進行兩次查詢，時間復雜度為O(n).

綜上，改進算法時間復雜度為O(n2).

下面通過實驗驗證改進算法相較于原算法復雜度大大降低.測試環(huán)境：i7-7700K+16GBRAM，Win10+VS2019.

實驗1 算法復雜度對比實驗

對常規(guī)、參差、抖動、脈間捷變頻、脈組捷變頻共5種形式，10部雷達，共5 800個脈沖，分別使用原算法與改進算法進行分選.運行時間與內(nèi)存占用情況見表2.由表2可知，改進算法相較原算法復雜度大大降低.

表2 算法復雜度對比Tab.2 The comparison of algorithm complexity

由于原算法時間復雜度無法直接分析得到，僅一組實驗數(shù)據(jù)無法證明改進算法時間復雜度低于原算法，為此進行了覆蓋性實驗.

實驗2 覆蓋性實驗

對不同時長的序列(即脈沖數(shù)不同)使用兩種算法進行分選，分選運行時間見表3.

表3 分選運行時間對比Tab.3 The comparison of sorting time

由表2、表3可知，不同脈沖數(shù)量下改進算法時間復雜度均遠低于原算法，且改進算法相較原算法空間復雜度大大降低.

3.4 算法分選性能對比

由模糊聚類分選算法原理可知，該算法通過分析截取后的相似矩陣獲得脈沖間的聚類信息.截取后的相似矩陣中，屬于同一類的兩脈沖對應位置處值為1，否則為0.原算法使用的追蹤法就是通過不斷的遍歷該矩陣將屬于同一類的脈沖歸為一類實現(xiàn)的；而改進算法中使用了并查集，在計算相似度并與閾值比較后，判斷兩脈沖屬于同一類，并將兩脈沖所屬的集合歸并.因為改進算法不需要反復遍歷矩陣，所以不需要保存整個矩陣，從而降低了空間復雜度；同時，使用并查集歸并兩脈沖所屬集合可在常數(shù)時間內(nèi)完成，因此降低了時間復雜度.

由上可知，改進算法與原算法本質(zhì)上是相同的，改進算法僅在提取聚類信息階段進行了改進，并不會對分選性能造成影響.為驗證上述分析，進行實驗對比.

實驗3 算法改進前后分選結(jié)果對比

分別使用原算法與改進算法對同一組數(shù)據(jù)進行分選，雷達參數(shù)見表4，分選結(jié)果分別見表5與表6.

表4 雷達信號參數(shù)Tab.4 The parameters of radar signal

表5 實驗3原算法分選結(jié)果Tab.5 The result of the original algorithm for experiment 3

表6 實驗3改進算法分選結(jié)果Tab.6 The result of the improved algorithm for experiment 3

由表5和6可知，算法改進前后分選結(jié)果相同，性能并未因算法改進而下降.

3.5 復雜信號環(huán)境分選

為模擬算法在復雜信號環(huán)境中的分選性能，加入干擾脈沖，使用改進算法進行分選.

實驗4 復雜信號環(huán)境分選

在表4所示雷達參數(shù)基礎(chǔ)上，分別加入表7所示的兩個跳頻干擾信號，分選結(jié)果分別見表8與表9.

表7 兩個跳頻干擾信號Tab.7 The parameters of 2 frequency-hopping jam signal

表8 實驗4原算法分選結(jié)果Tab.8 The result of the original algorithm for experiment 4

表9 實驗4改進算法分選結(jié)果Tab.9 The result of the improved algorithm for experiment 4

由表8與表9可知：在雷達信號參數(shù)與干擾信號參數(shù)無重疊的情況下能夠完成分選，此時干擾信號被作為輻射源分選出來；而在干擾信號參數(shù)與雷達信號參數(shù)重疊的情況下，算法將兩種信號聚為一類(表9中類別9為脈組捷變信號2與跳頻干擾信號歸并得到)，因此算法的抗參數(shù)重疊能力有待提高.

4 算法并行化與DSP實現(xiàn)

4.1 OpenMP并行運行

OpenMP是用于共享內(nèi)存并行系統(tǒng)的多處理器程序設計的一套指導性編譯處理方案.OpenMP API支持C、C++、Fortran語言的多平臺共享內(nèi)存并行編程.

由于循環(huán)是程序中運行時間比重最高的部分，也是使用最多的程序執(zhí)行結(jié)構(gòu)，OpenMP主要對程序中的for循環(huán)進行并行化，也可對其他語句進行并行化.改進算法主要由循環(huán)構(gòu)成，基于加速大概率事件的原則，本節(jié)使用OpenMP加速算法中的for循環(huán).

OpenMP對可以并行化的循環(huán)有如下要求：

1)循環(huán)變量是有符號整形數(shù)據(jù)；

2)循環(huán)條件的關(guān)系運算必須是<、<=、>、>=中的一種；

3)循環(huán)變量的增量為常數(shù)；

4)如果關(guān)系運算是<、<=，那每次循環(huán)變量應該增加，反之應該減?。?/p>

5)循環(huán)中不能使用break、goto等跳轉(zhuǎn)語句.

改進算法中的循環(huán)都滿足上述條件，可使用OpenMP使其并行化，在for循環(huán)前加入“#pragma omp parallel for”預編譯指令即可.而原算法中追蹤法部分涉及while循環(huán)，且存在大量的break，因此無法使用OpenMP使其并行化.

下面通過實驗對比OpenMP開啟與否對算法的加速效果.

實驗5 OpenMP加速測試

測試環(huán)境：i7-7700K+16GBRAM，Win10+VS2019.

對常規(guī)、參差、抖動、脈間捷變頻、脈組捷變頻共5種形式，10部雷達，分別測試OpenMP禁用與啟用時改進算法在不同信號數(shù)量下的運行時間.測試結(jié)果見表10.

表10 OpenMP并行運行時間測試Tab.10 Parallel running time test based on OpenMP

由表10可知，改進算法可使用OpenMP技術(shù)并行運行，數(shù)據(jù)量較大時，使用8個核心并行運行可加速5～6倍.

4.2 算法的DSP實現(xiàn)

在TI公司的TMDSEVM6678LE開發(fā)板上實現(xiàn)改進算法，采用優(yōu)化方式后，對表4所列信號進行分選.

實驗6 運行時間測試

使用TMDSEVM6678LE開發(fā)板，單核心，核心頻率1 GHz，對表4中所列雷達信號進行分選.截取信號時長：100 ms，共5 840個脈沖，800個噪點.分選運行時間1.1 s，分選結(jié)果見表11.分選結(jié)果中，部分雷達信號分選正確率未達到100%是由于在信號簇附近存在噪點.由表11可知，改進算法在數(shù)字信號處理(digital signal processing, DSP)開發(fā)板上成功運行，且能在較短時間內(nèi)完成分選，證明了算法的硬件可實現(xiàn)性.

表11 改進算法分選準確率Tab.11 The accuracy signal sorting of the improved algorithm

由第1節(jié)單次分選需完成對1 966個信號的分選及3.3節(jié)時間復雜度為O(n2)，可估算單次分選耗時1.1×(1966/5840)2=0.125s，因此改進算法已達到工程應用的實時性要求.

由4.1節(jié)中OpenMP并行測試，8核并行運算可加速5～6倍，若在DSP上使用OpenMP技術(shù)可使運行時間縮短至原有運行時間的1/6～1/5.盡管TMS320C6678支持OpenMP，但在TMDSEVM6678LE開發(fā)板上無法實現(xiàn)裸機OpenMP，因此無法對OpenMP并行進行測試.被動雷達尋的器一般要求500 ms內(nèi)完成首次分選，若能夠?qū)崿F(xiàn)在DSP上的OpenMP并行運行，則一次可對更多數(shù)據(jù)點進行分析，即可增大數(shù)據(jù)積累時長，這將是下一步研究的重點.

5 結(jié) 論

模糊聚類算法可有效在復雜信號環(huán)境下進行分選，但在信號密度較大的情況下，單次需分選的信號數(shù)量大，模糊聚類算法消耗硬件資源大，分選耗時長.本文結(jié)合并查集與模糊聚類算法，提出了基于并查集的低復雜度模糊聚類信號分選算法，經(jīng)過實驗與硬件實現(xiàn)，該算法已初步達到工程應用的實時性要求.但目前仍無法在DSP上實現(xiàn)OpenMP并行化，這將是下一步研究的重點；同時如何合理快速地設置閾值與權(quán)重、提高算法的抗參數(shù)交疊能力等問題也仍需深入研究.