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

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

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

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

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

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

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

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

0 引 言

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

處理極低可觀測目標(biāo)跟蹤的一類重要方法是檢測前跟蹤（track before detect，TBD），即同時實施目標(biāo)的狀態(tài)估計與檢測。TBD與TAD的主要區(qū)別在于，前者使用未經(jīng)過門限的原始數(shù)據(jù)，或門限設(shè)置很低的觀測數(shù)據(jù)，以保證目標(biāo)的高檢測概率。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ù)或門限很低的觀測數(shù)據(jù)，TBD算法的計算量通常遠(yuǎn)大于TAD算法。

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

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

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

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

1 ML-PDA算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 GPU簡介

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

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

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

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

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

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

圖3 PPS求和示意圖

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

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

4 實驗與仿真

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

仿真軟硬件平臺如表1所示。

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

表1 仿真軟硬件平臺

4.2 仿真場景

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

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

4.3 收斂速度對比

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

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

表3 算法收斂效率對比

4.4 計算對比

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

圖5 CPU與GPU平臺下計算精度對比

圖6 CPU與GPU平臺下計算時間對比

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

5 結(jié) 論

本文針對低信噪比、密集雜波條件下的目標(biāo)檢測與跟蹤問題，提出了以觀測引導(dǎo)PSO的ML-PDA算法。并從工程應(yīng)用的實時性角度考慮，提出基于GPU平臺的ML-PDA算法實現(xiàn)。經(jīng)仿真實驗，該算法的搜索效率高于基于GA的ML-PDA算法。所提出的并行實現(xiàn)獲得顯著的加速比，且具有實時性。下一步的工作將著重擴(kuò)展其在多目標(biāo)跟蹤場景［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é)報，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-- ），男，博士研究生，主要研究方向為目標(biāo)跟蹤與信息融合。

E-mail：gaolin_uestc＠126.com

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

E-mail：tangxu＠uestc.edu.cn

魏 平（196-4-- ），男，教授，博士，主要研究方向為自適應(yīng)陣列信號處理、非合作信號處理。

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

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