一種基于最長路徑的脈沖序列抽取算法

蘇煥程，張 君，陳昌云，程亦涵

(中國航天科工集團8511研究所，江蘇 南京 210007)

一種基于最長路徑的脈沖序列抽取算法

蘇煥程，張 君，陳昌云，程亦涵

(中國航天科工集團8511研究所，江蘇 南京 210007)

針對傳統(tǒng)的動態(tài)關聯(lián)算法在脈沖序列抽取方面存在的不足，提出了一種基于最長路徑原理的脈沖序列抽取算法。該算法首先將待抽取的脈沖序列轉換為一個經(jīng)過拓撲排序的有向無環(huán)圖，然后求解該有向無環(huán)圖的最長路徑，最后根據(jù)該最長路徑抽取出相應的脈沖序列。相比較于傳統(tǒng)的動態(tài)關聯(lián)算法，基于最長路徑的算法性能受設置的容差大小的影響較小，可以有效地提高脈沖序列抽取的正確率，并且具有較高的穩(wěn)定性，從而能夠更好地滿足信號分選算法的實際工程需要。仿真實驗表明了該算法的有效性。

信號分選；序列抽??；有向無環(huán)圖；最長路徑

0 引言

雷達截獲系統(tǒng)的作用是截獲一定頻域和空域范圍內(nèi)的雷達輻射源信號并確定其特征。如何在密集的電磁環(huán)境中正確地分離出各部雷達輻射源信息，得到正確的參數(shù)，實時地識別、告警,正確引導反輻射導彈進行攻擊或干擾系統(tǒng)進行干擾已變得越來越重要。而信號分選在雷達截獲系統(tǒng)設備中是重要的組成部分之一,信號分選的正確與否直接關系到設備的性能指標。從目前的信號分選技術來看，一般將信號分選分為兩級處理,首先根據(jù)到達方向(DOA)、載頻(RF)等參數(shù)對雷達信號進行預分選,再利用脈沖重復間隔(PRI)對信號做進一步的分選[1]。

傳統(tǒng)的PRI分選算法的處理過程可分為PRI估計和脈沖序列抽取兩部分[2]，即先通過PRI估計得到一個可能的雷達輻射源PRI，再以該可能的PRI數(shù)值為參考對脈沖序列進行抽取，從而實現(xiàn)對雷達輻射源脈沖的分選。目前的研究重點基本都集中在對PRI的快速、準確估計上，這是由于準確的PRI可以提高脈沖抽取的準確率。然而在復雜電磁環(huán)境下，大量的脈沖互相交錯，想要準確地估計出雷達輻射源的PRI是非常困難的，并且由于TOA測量精度偏差較大，即使是估計出準確的PRI也難以保證脈沖序列抽取的準確率。相比較于不斷出現(xiàn)的各種PRI估計算法，對脈沖序列抽取技術的研究相對較少，基本都集中在動態(tài)關聯(lián)算法及其改進算法上。而動態(tài)關聯(lián)算法雖然在簡單環(huán)境下具有較高的性能，但是在復雜電磁環(huán)境下受所選擇的PRI窗口大小影響較大，一旦發(fā)生抽取錯誤可能導致后續(xù)抽取均錯誤，性能波動較大。

為了克服動態(tài)關聯(lián)算法的缺陷，本文提出了一種基于最長路徑的脈沖序列抽取算法。該算法首先將待抽取的脈沖序列轉換為一個拓撲排序的有向無環(huán)圖，然后求解該有向無環(huán)圖的最長路徑，最后根據(jù)該最長路徑抽取出相應的脈沖序列。相比較于傳統(tǒng)的動態(tài)關聯(lián)算法，該算法的性能受PRI窗口大小的影響較小，可以有效地提高脈沖序列抽取的準確性，并且具有較高的穩(wěn)定性，從而能夠更好地滿足信號分選算法的實際需求。仿真實驗表明了該算法的有效性。

1 動態(tài)關聯(lián)法描述

動態(tài)關聯(lián)法又稱為擴展關聯(lián)法或PRI窗口預置法[3-4]，其基本工作原理是：先按一定規(guī)則形成準PRI，然后利用準PRI對脈沖序列進行關聯(lián)匹配，完成對脈沖序列的抽取。算法步驟大致可分為：

Step1 形成準PRI：采用任意一種PRI估計算法得到一個可能的雷達輻射源PRI作為準PRI。

Step2 搜索基準對：在脈沖流內(nèi)選擇兩個脈沖間隔等于準PRI(容差范圍內(nèi))的脈沖對，以這兩個脈沖對作為基準脈沖對，通常稱脈沖對的第一個脈沖為基準脈沖，第二個脈沖為參考脈沖。

Step3 產(chǎn)生預置窗口：預置窗口的中心為參考脈沖的TOA加上準PRI，預置窗口的寬度根據(jù)脈沖的抖動、TOA測量誤差等因素確定。

Step4 移動預置窗口：若沒有脈沖落入預置窗口內(nèi)，則將窗口的中心向右移動一個準PRI的時間長度；如果在規(guī)定的移動次數(shù)內(nèi)均無脈沖落入預置窗口內(nèi)，或預置窗口超出了最后一個脈沖的TOA則結束動態(tài)關聯(lián)算法，并輸出抽取成功的脈沖。

Step5 提取脈沖序列：對于落入預置窗口內(nèi)的脈沖，根據(jù)一定的準則提取其中一個脈沖，并將該脈沖作為新的參考脈沖，同時轉到Step3。

動態(tài)關聯(lián)法的脈沖抽取過程如圖1所示，以第一個參考脈沖開始生成預置窗口，根據(jù)選擇的窗口內(nèi)脈沖作為新的參考脈沖再不斷地生成新的預置窗口，并不斷地進行窗口內(nèi)脈沖抽取。

在動態(tài)關聯(lián)法的脈沖抽取過程中，預置窗口寬度的選擇非常重要，窗口選得較窄可以更準確地抽取到正確的脈沖，但實際雷達脈沖總存在抖動，TOA測量總存在誤差，窗口窄了就會漏失脈沖；窗口選得較寬就可以減少漏失，但是在信號密集環(huán)境下會同時有多個脈沖落入窗口內(nèi)，在沒有其他可靠參考因素的條件下，通常會造成錯選。無論是脈沖的漏失或錯選，都會導致下一次產(chǎn)生的預置窗口的準確性下降，導致漏失或錯選的概率進一步的增加，如圖2所示。

在圖2中，由于真實的雷達脈沖丟失，動態(tài)關聯(lián)算法錯誤地抽取了編號為7的干擾脈沖，結果導致后續(xù)的脈沖抽取全部發(fā)生錯誤。

通過上面的分析可知，動態(tài)關聯(lián)法對所選擇的預置窗口的寬度非常敏感，算法穩(wěn)定性較差，一旦發(fā)生脈沖漏失或錯選就會造成更嚴重的漏失或錯選。

2 基于最長路徑的脈沖序列抽取算法

2.1 最長路徑理論

對于給定的圖G=(V，E，W)，V是節(jié)點集合；E是邊的集合，是二元關系V×V的子集；W是權值的集合，是E上的實值函數(shù)W：E→R。若E是無序的二元關系集合，則稱圖G是無向圖；若E是有序的二元關系集合，則稱圖G是有向圖，若圖G中不存在回路，則稱圖G是有向無環(huán)圖[5]。

在圖論中，圖的最長路徑(Longest path)問題就是在圖中尋找一條無回路的最長路徑的問題。對于無權圖，是求解一條經(jīng)過邊數(shù)最多的路徑；而對于有權圖，是求解一條權值最大的路徑。

在無向圖中求解最長路徑問題是著名的NP難題，但是在有向圖中求解最長路徑卻存在著多項式時間內(nèi)的算法[6]。文獻[7～8]分別在區(qū)間圖(Interval Graphs)、共相似圖(CoComparability Graphs)中，根據(jù)圖中節(jié)點的次序關系采用動態(tài)規(guī)劃的策略在多項式時間內(nèi)求解最長路徑問題。

文獻[5]提出了一種將帶權值的有向無環(huán)圖進行拓撲排序，然后求解最大路徑的算法。有向無環(huán)圖的拓撲排序是指將有向無環(huán)圖的所有節(jié)點排成一個線性序列，若圖中有邊(u，v)∈E，則在最終的排序結果中，節(jié)點u總排在節(jié)點v的前面。圖3是一個有向無環(huán)圖的實例，經(jīng)過上述的拓撲排序后得到如圖4所示的一個線性序列：S、C、A、B、D、E。

如圖4所示，拓撲排序得到了節(jié)點的一個線性排序，且源點S到節(jié)點E的最大路徑是建立在S到節(jié)點B和S到節(jié)點D的基礎上。這表示在求解源點到后面節(jié)點的最長路徑時，根據(jù)有向邊之間的連接關系，可以參照前面已經(jīng)求得最大路徑值的節(jié)點。這意味著如果按照線性序列來求解最長路徑，源點到節(jié)點間的最長路徑滿足最優(yōu)子結構：源點到節(jié)點的最大路徑中的任意節(jié)點的路徑也是最大的。因此可以采用動態(tài)規(guī)劃的方法求解最大路徑問題[5]。

如果將有向無環(huán)圖所有邊的權值均設置為相等的值，則對帶權值的向無環(huán)圖求解最大路徑等效于對無權值的有向無環(huán)圖求解最長路徑。

2.2 脈沖序列抽取分析

下面采用有向無環(huán)圖的相關理論，對基于動態(tài)關聯(lián)法的脈沖序列抽取過程進行分析。

由于脈沖序列是按照TOA順序排列的，所以如果上述轉換過程中嚴格按照各個節(jié)點對應TOA的順序產(chǎn)生相應的有向邊，則可以直接得到經(jīng)過拓撲排序后的有向無環(huán)圖，省去了拓撲排序過程。圖4是一個脈沖序列的轉換實例，其中門限M=2。

如圖5所示，如果脈沖3落在脈沖1形成的預置窗口內(nèi)，則等效于在有向無環(huán)圖中節(jié)點1和節(jié)點3之間存在一條節(jié)點1到節(jié)點3的有向邊。故采用動態(tài)關聯(lián)法的脈沖抽取過程等效于在有向無環(huán)圖中從節(jié)點1找一條到節(jié)點12的路徑，而在該條路徑上的每一個節(jié)點等效于抽取得到的脈沖。

綜上所述，通過采用有向無環(huán)圖模型，可將基于動態(tài)關聯(lián)法的脈沖序列抽取過程轉換為在有向無環(huán)圖中搜索兩個節(jié)點之間路徑的問題。

2.3 脈沖序列抽取算法

通過對大量實際偵測到的脈沖序列深入分析可知，除干擾脈沖外，脈沖序列中其余的每一個脈沖都對應于某一部雷達，并以某一脈沖作為參考脈沖，其對應雷達的幀周期作為準PRI在時間上向前(或向后)進行抽取時，可以抽取到的脈沖個數(shù)多于以其它準PRI抽取得到的脈沖個數(shù)[7]。

反之，如果采用動態(tài)關聯(lián)法進行脈沖抽取，則最優(yōu)的抽取結果應當可以保證最終抽取得到的脈沖數(shù)最多。根據(jù)該分析，在采用動態(tài)關聯(lián)法進行抽取時，落在預置窗口內(nèi)的多個脈沖中能夠保證以該脈沖為參考脈沖繼續(xù)進行抽取，最終抽取得到的脈沖數(shù)最多的那個脈沖就是正確脈沖的概率是最大的。

魏樂村：斗渠長度由2 170 m變?yōu)? 605 m，比原設計增加435 m，1-1農(nóng)渠長度由850 m變?yōu)? 300 m，1-2農(nóng)渠長度由820 m變?yōu)?00 m，1-3農(nóng)渠長度由930 m變?yōu)? 700 m，1-4農(nóng)渠長度由980 m變?yōu)? 410 m，1-5農(nóng)渠長度由990 m變?yōu)? 200 m，變更后農(nóng)渠總長比原設計增加2 740 m。

在上節(jié)中，本文已經(jīng)通過有向無環(huán)圖對基于動態(tài)關聯(lián)法的脈沖序列抽取過程進行描述。故對于脈沖序列的最多脈沖數(shù)抽取問題即可轉換為在相應的有向無環(huán)圖中求解最長路徑的問題。根據(jù)以上分析，可以給出基于最長路徑的脈沖序列抽取處理流程：

Step1 形成準PRI：采用任意一種PRI估計算法得到一個可能的雷達輻射源PRI作為準PRI。

Step2 序列轉換：根據(jù)2.2節(jié)提供的方法，將待抽取的脈沖序列轉換為一個拓撲排序的有向無環(huán)圖。

Step3 窗口形成：將有向無環(huán)圖首節(jié)點設置為起點，以起點為基準形成N個預置窗口，預置窗口的寬度根據(jù)容差設置，預置窗口的中心分別為起點對應脈沖的TOA加上i×準PRI數(shù)值(i=1，2，3，…，N)，應當保證第N個窗口的中心點大于脈沖序列最后一個脈沖的TOA數(shù)值，如圖6所示。

Step4 終點設置：從第N個預置窗口開始搜索，如果預置窗口內(nèi)存在脈沖，則選擇與窗口中心點最近的脈沖并設置為終點，轉到Step5；否則搜索第N-1個預置窗口，依次類推。

Step5 路徑搜索：采用文獻[5]的算法，從有向無環(huán)圖起點開始，搜索到終點之間的最長路徑，如果搜索成功則輸出對應的脈沖，否則刪除有向無環(huán)圖的首節(jié)點，將第2個節(jié)點設置為首節(jié)點并轉到Step3。

如圖6所示，根據(jù)首節(jié)點形成了多個預置窗口，并根據(jù)形成的預置窗口確定相應的終點。

3 仿真實驗

為了驗證基于最長路徑的脈沖序列抽取算法的有效性和算法的穩(wěn)定性，本文進行了以下實驗。

實驗1：仿真信號源為5部PRI固定的雷達輻射源，PRI在50μs～50ms之間隨機，TOA測量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動態(tài)關聯(lián)法以及最長路徑法進行脈沖序列抽取，共測試了100組數(shù)據(jù)。抽取時的容差設置為500ns，即PRI預置窗口寬度為1μs，仿真結果見表1。

表1 抽取算法性能比較(簡單環(huán)境)

從表1仿真結果可以得出，在信號環(huán)境較為簡單且測量精度較高的條件下，兩種算法的抽取正確率和性能穩(wěn)定性均較高，算法性能差異較小。

實驗2：設置仿真信號源為20部PRI固定的雷達輻射源，PRI在50μs～50ms之間隨機，TOA測量誤差小于1μs，脈沖丟失率小于30%。分別采用傳統(tǒng)的動態(tài)關聯(lián)法以及最長路徑法進行脈沖抽取，共測試了100組數(shù)據(jù)。抽取時的容差設置為500ns，即PRI預置窗口寬度為1μs，仿真結果見表2。

表2 抽取算法性能比較(復雜環(huán)境)

從表2仿真結果可以得出，在信號環(huán)境較為復雜且測量精度較差的條件下，動態(tài)關聯(lián)法的抽取正確率明顯低于最長路徑法。

實驗3：設置仿真信號源為5部PRI固定的雷達輻射源，PRI在50μs～50ms之間隨機，TOA測量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動態(tài)關聯(lián)法以及最長路徑法進行脈沖抽取，共測試了100組數(shù)據(jù)。抽取時的容差設置為5μs，對應預置窗口寬度為10μs，仿真結果見表3。

表3 抽取算法性能比較(5μs容差)

從表3仿真結果可以得出，在與實驗1同樣的仿真環(huán)境，增大了抽取容差后，動態(tài)關聯(lián)法的穩(wěn)定性發(fā)生了較大的下降，而最長路徑法基本沒有變化。

實驗4：設置仿真信號源為5部PRI固定的雷達輻射源，PRI在50μs～50ms之間隨機，TOA測量誤差小于100ns，脈沖丟失率小于5%。分別采用傳統(tǒng)的動態(tài)關聯(lián)法以及最長路徑法進行脈沖抽取，共測試了100組數(shù)據(jù)。抽取時的容差設置為50ns，對應預置窗口寬度為100ns，仿真結果見表4。

表4 抽取算法性能比較(50ns容差)

從表4仿真結果可以得出，在與實驗1同樣的仿真環(huán)境下，通過減小抽取容差，動態(tài)關聯(lián)法的抽取正確率和算法性能穩(wěn)定性均發(fā)生了明顯的下降，而最長路徑法的抽取正確率均雖然也發(fā)生了下降，但是算法性能仍然保持較為穩(wěn)定。

通過對實驗1～4的仿真結果進行分析，可得出結論：在復雜環(huán)境或測量精度較低的情況下，動態(tài)關聯(lián)算法的抽取正確率明顯低于最長路徑法。當對抽取的容差進行調(diào)整后，動態(tài)關聯(lián)算法的抽取正確率發(fā)生較大波動，而最長路徑法的算法性能較為穩(wěn)定。這是由于動態(tài)關聯(lián)算法對抽取錯誤的敏感度較強，一旦發(fā)生脈沖抽取就會影響到下一次的抽取，甚至導致后續(xù)的抽取全部錯誤，而最長路徑法則具有較強的自我“糾錯”能力，一旦抽取到錯誤的脈沖，導致后續(xù)可抽取脈沖數(shù)減少，算法就會回到抽取錯誤的位置重新進行脈沖抽取，保證算法最終抽取到的脈沖數(shù)最多。

4 結束語

本文提出了一種基于最長路徑的脈沖序列抽取算法，該算法能夠克服傳統(tǒng)關聯(lián)比較法的不足，受算法容差影響較小，可以有效地提高脈沖序列抽取的正確率，且具有較高的穩(wěn)定性，能夠更好地滿足信號分選算法的實際需求。但是，該算法也具有自身的局限性，即該算法所要求的計算量相對較大，算法的實時性還有待進一步優(yōu)化和提升?！?/p>

[1] 楊文華, 高梅國. 基于PRI的雷達脈沖序列分選方法[J].現(xiàn)代雷達, 2005, 27(3):50-59.

[2] 關一夫,張國毅,劉志鵬. 一種基于脈沖樣本序列的PRI 周期信號分選算法[J]. 電訊技術,2014,54(7):915-920.

[3] 朱紅亮. 脈沖重頻分選算法的研究[D]. 西安：西安電子科技大學, 2010.

[4] 何煒. 雷達信號分選關鍵算法研究[D]. 成都：電子科技大學,2007.

[5] 尤磊, 符利勇, 宋新宇. 最大路徑算法在原條量材優(yōu)化中的應用及其優(yōu)化[J]. 信陽師范學院學報,2014,27(4):605-624.

[6] Sedgewick R,Wayne K. Algorithms [M]. 4th ed. Pearson Education, 2011.

[7] Ioannidou K,Mertzios GB,Nikolopoulos SD. The longest path problem has a polynomial solution on interval graphs[J]. Algorithmica，2011, 61(2):320-341．

[8] Mertzios GB,Corneil DG. A simple polynomial algorithm for the longest path problem on cocomparability graphs[J]. SIAM Journal on Discrete Mathematics，2012, 26(3):940-963．

[9] 李英達,肖立志.一種脈沖重復間隔復雜調(diào)制雷達信號分選方法[J]. 電子與信息學報, 2013, 35(10):2493-2497.

An algorithm of extracting pulse sequence based on longest path

Su Huancheng, Zhang Jun, Chen Changyun, Cheng Yihan

(No.8511 Research Institute of CASIC, Nanjing 210007, Jiangsu, China)

For the defects in pulses sequence drawing out of traditional dynamic association algorithm, a new algorithm of pulses sequence drawing out based on longest path is put forward. The algorithm firstly transforms the pulses sequence to directed acyclic graph which topological sorted, then searches the longest path, extracting the pulse sequence based on the longest path at last. Compared with the traditional dynamic association algorithm, the performance of this algorithm is not fluctuate on toler vary, and increase the pulse extracting accurate rate, which satisfies the requirement of the signal sorting process. Simulation results verify the validity of the proposed algorithm.

signal sorting; pulse extracting; directed acyclic graph; longest path

2017-01-11；2017-03-06修回。

蘇煥程(1983-)，男，高工，主要研究方向為電子對抗信息處理。

TJ76;TN972

A