高 林，唐 續(xù)，魏 平

（電子科技大學(xué)電子工程學(xué)院，四川成都611731）

基于PSO的ML-PDA算法及其并行實(shí)現(xiàn)

高 林，唐 續(xù)，魏 平

（電子科技大學(xué)電子工程學(xué)院，四川成都611731）

針對(duì)密集雜波條件下的目標(biāo)檢測(cè)與跟蹤問題，開展極大似然-概率數(shù)據(jù)關(guān)聯(lián)（maximum likelihoodprobabilistic data association，ML-PDA）算法優(yōu)化與實(shí)時(shí)計(jì)算問題研究。在算法層面，通過在極大化對(duì)數(shù)似然比（log likelihood ratio，LLR）過程中引入粒子群優(yōu)化（particle swarm optimization，PSO）方法，并進(jìn)一步提出基于觀測(cè)引導(dǎo)的PSO播撒粒子方式，提升算法的計(jì)算效率；在實(shí)現(xiàn)層面，提出基于圖形處理器（graphic processing unit，GPU）的PSO實(shí)現(xiàn)策略。仿真實(shí)驗(yàn)結(jié)果說明了基于觀測(cè)引導(dǎo)PSO算法搜索的有效性。在GPU平臺(tái)上實(shí)現(xiàn)該算法獲得顯著的加速比，驗(yàn)證了所提出方法具有工程實(shí)時(shí)性。

檢測(cè)前跟蹤；極大似然 概率數(shù)據(jù)關(guān)聯(lián)；粒子群優(yōu)化；并行處理

0 引 言

高密度雜波環(huán)境中的極低可觀測(cè)目標(biāo)跟蹤問題一直是困難的研究熱點(diǎn)。極低可觀測(cè)意味著目標(biāo)回波信號(hào)中信號(hào)能量與噪聲功率比值，即信噪比（signal-to-noise ratio，SNR）很低。在傳統(tǒng)的檢測(cè)后跟蹤（track after detect，TAD）算法中，若要維持對(duì)低SNR目標(biāo)的高檢測(cè)概率，勢(shì)必會(huì)降低檢測(cè)算法的檢測(cè)門限。然而，這將導(dǎo)致更多的雜波，使得虛警概率上升，導(dǎo)致后續(xù)跟蹤算法對(duì)目標(biāo)的跟蹤精度下降，甚至失效。

處理極低可觀測(cè)目標(biāo)跟蹤的一類重要方法是檢測(cè)前跟蹤（track before detect，TBD），即同時(shí)實(shí)施目標(biāo)的狀態(tài)估計(jì)與檢測(cè)。TBD與TAD的主要區(qū)別在于，前者使用未經(jīng)過門限的原始數(shù)據(jù)，或門限設(shè)置很低的觀測(cè)數(shù)據(jù)，以保證目標(biāo)的高檢測(cè)概率。TBD算法分兩大類：①基于迭代的TBD算法，如TBD框架下的粒子濾波（particle filter，PF）算法［12］；②基于批處理的TBD算法，如最大似然 概率數(shù)據(jù)互聯(lián)（maximum likelihood-probabilistic data association，ML-PDA）算法［3］、最大似然-概率多假設(shè)跟蹤（maximum likelihood-probabilistic multiple hypothesis tracking，MLPMHT）算法［4］等。由于使用了原始數(shù)據(jù)或門限很低的觀測(cè)數(shù)據(jù)，TBD算法的計(jì)算量通常遠(yuǎn)大于TAD算法。

ML-PDA通過多幀累積的方式獲得檢測(cè)和跟蹤高密度雜波環(huán)境中極低可觀測(cè)目標(biāo)的能力［5］。它基于多幀觀測(cè)數(shù)據(jù)構(gòu)建被跟蹤目標(biāo)狀態(tài)向量的對(duì)數(shù)似然比（log likelihood ratio，LLR）。以LLR最大化時(shí)所對(duì)應(yīng)的目標(biāo)狀態(tài)向量作為被跟蹤目標(biāo)在起始幀時(shí)刻的狀態(tài)估計(jì)。目標(biāo)的LLR搜索面具有很多局部峰值。實(shí)現(xiàn)該最大化尋優(yōu)有3種常用方法［6］：多遍網(wǎng)格（multi-pass grid，MPG）搜索法，基于遺傳算法（genetic algorithm，GA）的優(yōu)化方法和直接子空間搜索（directed subspace search，DSS）法。其中，MPG搜索方法基于梯度優(yōu)化。若起始點(diǎn)選取不當(dāng)，該方法容易收斂于局部而非全局最優(yōu)值；第二種優(yōu)化方法中，首先使用GA算法將目標(biāo)狀態(tài)“粗調(diào)”至全局最優(yōu)附近，再通過梯度收斂方法進(jìn)一步“細(xì)調(diào)”到全局最優(yōu)。該方法的優(yōu)化性能良好，主要問題是迭代次數(shù)多，對(duì)較高的收斂精度需要較多的種子數(shù)，以至于影響實(shí)時(shí)性。DSS算法將觀測(cè)值反映射回參數(shù)空間，作為起始點(diǎn)進(jìn)行搜索。該方法有較快的收斂速度。然而，其使用的前提是量測(cè)空間為參數(shù)空間的子空間。這要求應(yīng)用場(chǎng)景中觀測(cè)值能夠被反映射回參數(shù)空間［6］。但很多應(yīng)用中（如基于角度 多普勒的目標(biāo)跟蹤等），該條件并不滿足?？傊?，計(jì)算量大依然是限制ML-PDA工程應(yīng)用的主要因素。

圖形處理器（graphic processing unit，GPU）能夠并發(fā)執(zhí)行數(shù)萬個(gè)線程。它為通用算法的并行化提供了一個(gè)有效的實(shí)現(xiàn)平臺(tái)［7］。近年來，GPU已成為處理高計(jì)算復(fù)雜度的目標(biāo)檢測(cè)與跟蹤算法的流行工具［89］。

為解決ML-PDA的計(jì)算量問題，本文提出基于觀測(cè)引導(dǎo)粒子群優(yōu)化（particle swarm optimization，PSO）的MLPDA算法及其GPU實(shí)現(xiàn)。相比于GA，PSO每次迭代的步驟少，且不涉及數(shù)據(jù)間的進(jìn)制轉(zhuǎn)換問題，收斂效率更高［10］；基于觀測(cè)引導(dǎo)PSO步驟，提高PSO的收斂效率；基于GPU的算法并行實(shí)現(xiàn)，滿足了ML-PDA的工程實(shí)時(shí)性需求。

本文章節(jié)安排如下：第1節(jié)介紹ML-PDA算法中LLR的構(gòu)建以及已有的LLR優(yōu)化算法；第2節(jié)介紹PSO優(yōu)化及其用于ML-PDA中的策略；第3節(jié)介紹基于GPU的并行計(jì)算，以及基于PSO優(yōu)化算法的ML-PDA的并行實(shí)現(xiàn)策略。本文所提方法的計(jì)算效率將在第4節(jié)中通過仿真驗(yàn)證。第5節(jié)進(jìn)行工作總結(jié)并展望后續(xù)研究。

1 ML-PDA算法

ML-PDA是一種批處理TBD算法。它使用最近的Nw幀數(shù)據(jù)估計(jì)目標(biāo)的狀態(tài)向量。當(dāng)新數(shù)據(jù)到來后，將采用滑窗方式移出前Nw幀數(shù)據(jù)的第一幀，并將最新一幀數(shù)據(jù)作為滑窗中的第Nw幀。ML-PDA算法遵循如下基本假設(shè)：

假設(shè)1已知目標(biāo)的檢測(cè)概率為Pd，且目標(biāo)的檢測(cè)在幀間是獨(dú)立進(jìn)行的；

假設(shè)2每幀數(shù)據(jù)中至多有一個(gè)量測(cè)來源于目標(biāo)；

假設(shè)3已知目標(biāo)狀態(tài)的變化方式；

假設(shè)4監(jiān)測(cè)區(qū)域的體積為U，雜波在監(jiān)測(cè)區(qū)域內(nèi)呈均勻分布；

假設(shè)5監(jiān)測(cè)區(qū)域內(nèi)的雜波數(shù)呈泊松分布，且已知該分布的密度為λ，概率強(qiáng)度方程為μf（m），觀測(cè)數(shù)據(jù)的虛警概率為Pfa；

假設(shè)6目標(biāo)回波幅度的服從p1（a）的分布，雜波幅度服從p0（a）的分布，且監(jiān)測(cè)區(qū)域的SNR已知或能夠被實(shí)時(shí)估計(jì)；

假設(shè)7目標(biāo)量測(cè)被加性高斯白噪聲干擾；

假設(shè)8每幀數(shù)據(jù)中目標(biāo)產(chǎn)生的量測(cè)彼此獨(dú)立。

在ML-PDA算法中，假設(shè)待估計(jì)目標(biāo)的參數(shù)為xr，且運(yùn)動(dòng)模型F已知，則目標(biāo)在第i幀的運(yùn)動(dòng)狀態(tài)可由式（1）得到：

目標(biāo)的量測(cè)集由式（2）得到：

式中，i＝1，2，…，Nw表示目標(biāo)觀測(cè)數(shù)據(jù)的幀數(shù)；j＝1，2，…，mi表示對(duì)應(yīng)數(shù)據(jù)幀內(nèi)的量測(cè)個(gè)數(shù)；zij表示目標(biāo)運(yùn)動(dòng)有關(guān)的觀測(cè)數(shù)據(jù)；aij表示對(duì)應(yīng)量測(cè)的幅度。令觀測(cè)站在獲取第i幀量測(cè)時(shí)所處的位置為xs（i），則量測(cè)z與xr，xs（i）間的關(guān)系可由式（3）給出。

式中，H（·）為觀測(cè)方程；wi表示零均值且協(xié)方差矩陣為R的高斯白噪聲。則LLR可由式（4）～式（6）表示。

式中，ρij表示幅度似然比；τ表示檢測(cè)算法所設(shè)置的門限；p1（aij｜τ）表示目標(biāo)存在的假設(shè)；p0（aij｜τ）表示目標(biāo)不存在的假設(shè)；N（·）表示高斯分布。

至此，待估計(jì)的目標(biāo)參數(shù)可由式（7）給出。

式中，t表示目標(biāo)參數(shù)xr的采樣時(shí)刻。

早期的ML-PDA中普遍使用MPG算法來求取^x（t）。文獻(xiàn)［6］證明，GA搜索與DSS方法能夠獲得更高的搜索效率與估計(jì)精度。然而，GA算法的精度與播撒種子的數(shù)量成正比，不利于算法的實(shí)時(shí)實(shí)現(xiàn)；DSS方法的使用條件則在一些實(shí)際應(yīng)用中無法得到滿足。此外，文獻(xiàn)［10］證明，在相同條件下，PSO的搜索效率要高于GA。

2 觀測(cè)引導(dǎo)PSO的ML-PDA算法

2.1 基于PSO優(yōu)化LLR

PSO是一種優(yōu)化算法。給定目標(biāo)方程f（y），其中y代表被搜索向量的參數(shù)，Np個(gè)粒子被播撒在參數(shù)空間中。每個(gè)粒子在搜索時(shí)，將會(huì)考慮到各自的搜索歷史最好點(diǎn)和群體內(nèi)其他粒子的歷史最好點(diǎn)，并在此基礎(chǔ)上變化位置。群中的第n個(gè)粒子由3個(gè)向量組成：當(dāng)前位置yn、歷史最優(yōu)位置pn以及速度vn。yn被看作描述空間點(diǎn)的一套坐標(biāo)。在算法迭代中，yn作為問題解被f（yn）評(píng)價(jià)。整個(gè)粒子群中迄今為止搜索到的最好位置表示為pg。

在一次迭代中，對(duì)于粒子n，其第d維基于式（8）和式（9）變化。

式中，c1，c2是兩個(gè)非負(fù)值，代表移動(dòng)常數(shù)，它們使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)的全局最優(yōu)點(diǎn)靠近；r1，r2是在［0，1］中取值的隨機(jī)函數(shù)；為限制粒子單次移動(dòng)距離，設(shè)移動(dòng)距離上限［Vmax］d：若vnd＜－［Vmax］d，則令vnd＝－［Vmax］d，反之，若vnd＞［Vmax］d，則令vnd＝［Vmax］d。基于PSO優(yōu)化ML-PDA的LLR流程如下：

步驟2評(píng)價(jià)粒子：對(duì)每一個(gè)粒子，通過LLR公式Λ（Z，a｜xn）評(píng)價(jià)其適應(yīng)指數(shù)。

步驟3按照式（8）和式（9）改變粒子的速度和位置。

步驟4更新最優(yōu)：比較粒子適應(yīng)指數(shù)與其個(gè)體最優(yōu)值，若優(yōu)于個(gè)體最優(yōu)，則將個(gè)體最優(yōu)更新為當(dāng)前粒子位置；比較粒子適用值與全局最優(yōu)值，若優(yōu)于全局最優(yōu)，則將全局最優(yōu)值更新為當(dāng)前粒子位置。

步驟5停止條件：若滿足收斂條件，則停止；若不滿足，則返回步驟2。

2.2 基于觀測(cè)引導(dǎo)的PSO優(yōu)化算法

在文獻(xiàn)［6］提出的兩種算法中，GA在參數(shù)空間里隨機(jī)撒種，而DSS要求參數(shù)空間與觀測(cè)空間一一對(duì)應(yīng)。前者雖然有一定的收斂效率，但在對(duì)目標(biāo)位置沒有任何先驗(yàn)信息的環(huán)境中隨機(jī)撒種，收斂效率將會(huì)很低。究其原因，在LLR表面，局部最優(yōu)值相關(guān)的部分只占約30%［11］，即有約0.7× Np數(shù)量的種子被撒在LLR底部，起不到任何作用。然而，若目標(biāo)在第一幀觀測(cè)數(shù)據(jù)中未被檢測(cè)，通過隨機(jī)撒種將有更大的可能性將其檢出。基于以上考慮，本文提出在充分考慮LLR以及觀測(cè)數(shù)據(jù)的特性基礎(chǔ)上，由觀測(cè)引導(dǎo)撒種來進(jìn)一步提升PSO的收斂效率，從而在算法層面多普勒減少計(jì)算時(shí)間。如圖1（b）所示，使用角度 多普勒作引導(dǎo)，PSO的撒種變得有針對(duì)性。如圖1（c）所示，若加上距離觀測(cè)信息作引導(dǎo)，進(jìn)入目標(biāo)高似然區(qū)域的粒子進(jìn)一步增加，可以更少的迭代次數(shù)完成優(yōu)化。

圖1 基于觀測(cè)引導(dǎo)PSO播撒粒子示意圖

觀測(cè)引導(dǎo)的PSO優(yōu)化步驟如下：

步驟1初始化：接收第一幀觀測(cè)數(shù)據(jù)，假設(shè)一共接收到m1個(gè)量測(cè)；

步驟2假設(shè)為每個(gè)量測(cè)分配的種子數(shù)為Ns，角度觀測(cè)標(biāo)準(zhǔn)差為φθ，則在以每個(gè)量測(cè)為中心，加減φθ的范圍內(nèi)均勻播撒Ns個(gè)種子。此外，為捕獲第一幀量測(cè)可能的目標(biāo)漏檢，額外播撒Nd個(gè)種子，則共產(chǎn)生Nd＋Ns×m1個(gè)種子。

步驟3～步驟6參照第2.1節(jié)基于PSO優(yōu)化ML-PDA的LLR算法步驟2～步驟5。

3 基于GPU實(shí)現(xiàn)觀測(cè)引導(dǎo)PSO的ML-PDA

在優(yōu)化過程中，LLR被作為優(yōu)化算法的評(píng)價(jià)函數(shù)。由于構(gòu)建LLR會(huì)用到多幀觀測(cè)數(shù)據(jù)，并且粒子的維度較高，因此評(píng)價(jià)單個(gè)粒子的適應(yīng)程度會(huì)耗費(fèi)一定的時(shí)間。此外，為達(dá)到較高的搜索精度，播撒的種子數(shù)一般較大，需要的迭代次數(shù)也多。ML-PDA算法的實(shí)時(shí)性難以保證。本節(jié)將PSO算法特點(diǎn)與ML-PDA結(jié)合起來，提出基于GPU平臺(tái)的ML-PDA實(shí)現(xiàn)策略，使ML-PDA得以實(shí)時(shí)實(shí)施。

3.1 GPU簡(jiǎn)介

GPU擁有一簇流多處理器，每個(gè)SM內(nèi)有多個(gè)流處理器。它們能夠被用于并行執(zhí)行計(jì)算任務(wù)。CUDA（computer unified device architecture）是一個(gè)通用計(jì)算框架。它能夠高效地協(xié)調(diào)GPU和CPU共同處理復(fù)雜的計(jì)算任務(wù)。在CUDA中，CPU被認(rèn)為是Host，GPU被認(rèn)為是Device。其中，Host一般用于執(zhí)行串行任務(wù)以及初始化GPU核函數(shù)，而GPU則用于執(zhí)行高度并行化的計(jì)算任務(wù)。GPU核函數(shù)一般可啟用上萬個(gè)并發(fā)線程，這些線程分為兩個(gè)層次：網(wǎng)格以及塊。同一個(gè)塊內(nèi)的線程可通過共享存儲(chǔ)器交互數(shù)據(jù)，不同塊內(nèi)的線程可通過全局存儲(chǔ)器交互數(shù)據(jù)。一般來說，共享存儲(chǔ)器的訪問速度遠(yuǎn)高于全局存儲(chǔ)器。CUDA的結(jié)構(gòu)如圖2所示。其中，Gdx，Gdy，Bdx，Bdy分別表示網(wǎng)格內(nèi)每行、列分配的最多塊數(shù)量，以及每個(gè)塊內(nèi)行、列分配的最多線程數(shù)。這4個(gè)參數(shù)在初始化核函數(shù)時(shí)被指定。

3.2 基于觀測(cè)引導(dǎo)PSO的ML-PDA算法在GPU上的實(shí)現(xiàn)

考慮到需要存儲(chǔ)的數(shù)據(jù)較多，本文將粒子的位置、速度信息以及接收到的觀測(cè)數(shù)據(jù)等存儲(chǔ)在全局存儲(chǔ)器中。由于全局存儲(chǔ)器是按一維存儲(chǔ)數(shù)據(jù)的，本文基于文獻(xiàn)［12］的數(shù)據(jù)存儲(chǔ)形式，將算法中所有的二維矩陣數(shù)據(jù)映射成一維向量，方便GPU存取。

圖2 CUDA結(jié)構(gòu)圖

PSO算法在撒種以及粒子遷移時(shí)需要使用隨機(jī)數(shù)。現(xiàn)有的GPU實(shí)現(xiàn)PSO算法的文獻(xiàn)［12- 13］中采用空間換取時(shí)間的策略：在CPU端生成大量隨機(jī)數(shù)，并預(yù)先傳入GPU。然而，在ML-PDA算法中，觀測(cè)數(shù)據(jù)較多，并需要較多的高維度種子，對(duì)存儲(chǔ)的需求非常大，以至于上述策略不再有效。因此，本文采用在GPU端生成隨機(jī)數(shù)的方法［14］。

此外，在PSO算法中需要更新全局最優(yōu)種子。全局的歷史最優(yōu)值被動(dòng)態(tài)更新需要引入遍歷過程。在CPU中執(zhí)行此步驟時(shí)通過循環(huán)完成。遍歷Nd＋Ns×m1個(gè)元素需用到Nd＋Ns×m1－1次循環(huán)，并在歸一化的時(shí)候也需要用到Nd＋Ns×m1－1求和。而在GPU中，由于多個(gè)線程并行工作，將有Nd＋Ns×m1個(gè)線程同時(shí)訪問全局最優(yōu)值。若同時(shí)做更改操作，會(huì)產(chǎn)生沖突。因此，本文首先將全局最優(yōu)值復(fù)制Nd＋Ns×m1次，每個(gè)線程更新其中一個(gè)全局最優(yōu)值。待所有線程更新完后再選出其中的最大值，作為新的全局最優(yōu)估計(jì)值。實(shí)現(xiàn)中，引入并行前綴求和（parallel prefix sum，PPS）［15］，使循環(huán)次數(shù)降至log2（Nd＋Ns×m1－1）次。PPS的實(shí)施如圖3所示（以8個(gè)元素求和為例）。

圖3 PPS求和示意圖

同樣地，在求取最終狀態(tài)時(shí)（需要求得所有種子參數(shù)的平均值），也通過多次運(yùn)用PPS減少計(jì)算時(shí)間。

基于GPU實(shí)現(xiàn)觀測(cè)引導(dǎo)PSO的ML-PDA算法流程如圖4所示。

4 實(shí)驗(yàn)與仿真

4.1 仿真的硬件以及軟件環(huán)境

仿真軟硬件平臺(tái)如表1所示。

圖4 GPU實(shí)現(xiàn)觀測(cè)引導(dǎo)PSO的ML-PDA算法流程圖

表1 仿真軟硬件平臺(tái)

4.2 仿真場(chǎng)景

考慮一個(gè)基于主動(dòng)聲吶的水下運(yùn)動(dòng)目標(biāo)探測(cè)場(chǎng)景［3］。目標(biāo)的狀態(tài)向量為［x，y，˙x，˙y］，其中（x，y）與（˙x，˙y）分別代表目標(biāo)的二維空間位置與速度（笛卡爾坐標(biāo)下）。該聲吶可觀測(cè)到目標(biāo)與聲吶位置的角度、距離和多普勒頻率。其觀測(cè)方程按式（10）給出。

式中，c為聲波在水中的傳播速度；γ為聲吶信號(hào)的發(fā)射頻率；γz為經(jīng)目標(biāo)反射后帶多普勒信息的信號(hào)頻率，傳感器接收信號(hào)的頻率范圍Uγ＝［296 Hz，300 Hz］，角度觀測(cè)范圍Uθ＝［0°，50°］，距離觀測(cè)范圍Ur＝［12 700 m，14 200 m］。假設(shè)目標(biāo)檢測(cè)概率為Pd＝0.8，量測(cè)標(biāo)準(zhǔn)差分別為σγ＝0.01 Hz，σθ＝1°，σr＝100 m。采樣間隔為10 s，共采集15個(gè)周期。令Nw＝10，目標(biāo)真實(shí)的初始狀態(tài)為［10 000 m，10 000 m／s，－5 m，－1 m／s］，聲吶發(fā)射的信號(hào)頻率γ＝300 Hz。設(shè)監(jiān)視區(qū)域內(nèi)的SNR為8 dB。觀測(cè)空間中的雜波數(shù)期望值NFA與雜波密度λ關(guān)系如式（11）所示。

4.3 收斂速度對(duì)比

本節(jié)就所提出的優(yōu)化算法與GA搜索算法進(jìn)行對(duì)比。PSO算法及GA搜索算法參數(shù)設(shè)置如表2所示。分別令NFA＝10，20，40，獨(dú)立仿真200次，并記錄其收斂時(shí)的迭代次數(shù)。若搜索發(fā)散則記錄算法迭代次數(shù)為100。各算法平均迭代次數(shù)如表3所示。由表3可知，在未加入觀測(cè)信息時(shí)，使用PSO尋找最優(yōu)解的循環(huán)次數(shù)要少于GA。但隨著雜波密度的增加，算法需要更多的迭代次數(shù)來保證收斂到全局最優(yōu)值。在加入觀測(cè)引導(dǎo)之后，PSO撒種更有針對(duì)性，全局最優(yōu)值出現(xiàn)更早，更有利于算法收斂。

表2 算法參數(shù)設(shè)置

表3 算法收斂效率對(duì)比

4.4 計(jì)算對(duì)比

本節(jié)分別使用GPU及CPU進(jìn)行仿真，進(jìn)一步驗(yàn)證3.2節(jié)提出的PSO并行化策略。令Ns＝15，Nd＝20，當(dāng)NFA＝5時(shí)，在200次獨(dú)立實(shí)驗(yàn)的情況下統(tǒng)計(jì)出計(jì)算精度

圖5 CPU與GPU平臺(tái)下計(jì)算精度對(duì)比

圖6 CPU與GPU平臺(tái)下計(jì)算時(shí)間對(duì)比

由圖5可知，本文提出的并行化策略中，跟蹤精度與CPU平臺(tái)一致，但計(jì)算速度明顯提升。隨著種子數(shù)量增加，本文提出的GPU并行化策略的計(jì)算時(shí)間只少量增加。這是因?yàn)樵贕PU中只需增加一定數(shù)量的（并行）線程。即是說，無論種子數(shù)有多少，只要在GPU硬件限制的線程數(shù)（普通的GPU平臺(tái)中可達(dá)數(shù)萬個(gè)）內(nèi)，均只需一次循環(huán)即可完成。略上升的計(jì)算時(shí)間來自種子數(shù)增加后所需數(shù)據(jù)拷貝時(shí)間的增加。如圖6所示，在本仿真場(chǎng)景中，若平均雜波數(shù)如圖5所示。改變NFA＝5，10，15，20，25（對(duì)應(yīng)平均粒子數(shù)分別為：95，170，245，320，375），算法迭代限定16次。在500次平均的情況下，每次迭代執(zhí)行時(shí)間以及加速比如圖6所示。為25，所提出的方法在GPU平臺(tái)上獲得相比于CPU平臺(tái)接近290倍的加速比。而從絕對(duì)計(jì)算時(shí)間看，該方法的單次迭代執(zhí)行時(shí)間未超過1 s，遠(yuǎn)小于采樣時(shí)間間隔，能夠滿足實(shí)時(shí)應(yīng)用需求。

5 結(jié) 論

本文針對(duì)低信噪比、密集雜波條件下的目標(biāo)檢測(cè)與跟蹤問題，提出了以觀測(cè)引導(dǎo)PSO的ML-PDA算法。并從工程應(yīng)用的實(shí)時(shí)性角度考慮，提出基于GPU平臺(tái)的ML-PDA算法實(shí)現(xiàn)。經(jīng)仿真實(shí)驗(yàn)，該算法的搜索效率高于基于GA的ML-PDA算法。所提出的并行實(shí)現(xiàn)獲得顯著的加速比，且具有實(shí)時(shí)性。下一步的工作將著重?cái)U(kuò)展其在多目標(biāo)跟蹤場(chǎng)景［16］中的應(yīng)用。

［1］Salmond D，Birch H.A particle filter for track-before-detect［C］∥Proc.of the American Control Conference，2001：3755- 3760.

［2］Boers Y，Driessen J.Particle filter based detection for tracking［C］∥Proc.of the American Control Conference，2001：4393- 4397.

［3］Kirubarajan T，Bar-Shalom Y.Low observable target motion analysis using amplitude information［J］.IEEE Trans.on Aerospace and Electronic Systems，1996，32（4）：1367- 1384.

［4］Streit R L，Luginbuhl T E.Maximum likelihood method for probabilistic multihypothesis tracking［C］∥Proc.of the SPIE International Symposium on Optical Engineering and Photonics in Aerospace Sensing，1994：394- 405.

［5］Schoenecker S，Willett P，Bar-Shalom Y.Comparing multitarget multisensor ML-PMHT with ML-PDA for VLO targets［C］∥Proc. of the 16th International Conference on Information Fusion，2013：250- 257.

［6］Blanding W R，Willett P，Bar-Shalom Y，et al.Directed subspace search ML-PDA with application to active sonar tracking［J］.IEEE Trans.on Aerospace and Electronic Systems，2008，44（1）：201- 206.

［7］Sanders J，Kandrot E.CUDA by example：an introduction to general-purpose GPU programming［M］.Boston，MA：Addison-Wesley，2010.

［8］Tang X，Su J Z，Zhao F B，et al.Particle filter track-before-detect implementation on GPU［J］.EURASIP Journal on Wireless Communications and Networking，2013，2013（1）：1- 9.

［9］Goodrum M A，Trotter M J，Aksel A，et al.Parallelization of particle filter algorithms［J］.Computer Architecture，2010，6161：139- 149.

［10］Shen Y，Guo B，Gu T X.Particle swarm optimization algorithm and comparison with genetic algorithm［J］.Journal of University of Electronic Science and Technology of China，2005，34（5）：696-699.（沈艷，郭兵，古天祥.粒子群優(yōu)化算法及其與遺傳算法的比較［J］.電子科技大學(xué)學(xué)報(bào)，2006，34（5）：696- 699.）

［11］Blanding W R，Willett P K，Bar-Shalom Y.Offline and realtime methods for ML-PDA track validation［J］.IEEE Trans. on Signal Processing，2007，55（5）：1994- 2006.

［12］Zhou Y，Tan Y.GPU-based parallel particle swarm optimization［C］∥Proc.of the IEEE Congress on Evolutionary Computation，2009：1493- 1500.

［13］Mussi L，Daolio F，Cagnoni S.Evaluation of parallel particle swarm optimization algorithms within the CUDATMarchitecture［J］.Information Sciences，2011，181（20）：4642- 4657.

［14］Langdon W B.A fast high quality pseudo random number generator for n Vidia CUDA［C］∥Proc.of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference，2009：2511- 2513.

［15］Newcombe R A，Izadi S，Hilliges O，et al.KinectFusion：realtime dense surface mapping and tracking［C］∥Proc.of the 10th IEEE International Symposium on Mixed and Augmented Reality（ISMAR），2011：127- 136.

［16］Blanding W R，Willett P K，Bar-Shalom Y.ML-PDA：advances and a new multitarget approach［J］.EURASIP Journal on Advances in Signal Processing，2008：38- 56.

PSO based ML-PDA and its parallelized implementation

GAO Lin，TANG Xu，WEI Ping
（School of Electronics Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China）

The target detection and tracking problems when involved in high dense clutter are addressed.Specifically，we propose to solve the optimization and computation problems of maximum likelihood-probabilistic data association（ML-PDA）.The particle swarm optimization（PSO）algorithm to maximize the log likelihood ratio（LLR）is adopted.We propose to initialize the particles of PSO based on measurements，which improves the computation efficiency.Furthermore，we propose a scheme which allows implementing PSO in parallel on graphic processing unit（GPU）.The efficiency of the proposed algorithm and the parallelized scheme are illustrated based on simulations.

track before detect；maximum likelihood-probabilistic data association（ML-PDA）；particle swarm optimization（PSO）；parallel processing

TN 953

A

10.3969／j.issn.1001-506X.2015.12.02

高 林（199-0-- ），男，博士研究生，主要研究方向?yàn)槟繕?biāo)跟蹤與信息融合。

E-mail：gaolin_uestc＠126.com

唐 續(xù)（1975-- ），通訊作者，男，副教授，博士，主要研究方向?yàn)槟繕?biāo)跟蹤與信息融合。

E-mail：tangxu＠uestc.edu.cn

魏 平（196-4-- ），男，教授，博士，主要研究方向?yàn)樽赃m應(yīng)陣列信號(hào)處理、非合作信號(hào)處理。

E-mail：pwei＠uestc.edu.cn

1001-506X（2015）12-2677-06

2014- 12- 21；

2015- 05- 27；網(wǎng)絡(luò)優(yōu)先出版日期：2015- 07- 27。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150727.1626.008.html

中國(guó)博士后科學(xué)基金（2015M572463）資助課題