李月武，劉長江，胡建旺，吉 兵，張岐龍

(1.陸軍工程大學石家莊校區(qū)，河北 石家莊 050000；2.解放軍31697部隊，遼寧 大連 116104；3.解放軍95806部隊，北京 100076)

0 引言

信息融合又稱數(shù)據(jù)融合技術(shù)，是一個對單個和多個信息源獲取的數(shù)據(jù)和信息進行關(guān)聯(lián)、相關(guān)和綜合的過程，以獲得精確的位置和身份估計[1-2]，廣泛應用于各個領(lǐng)域。對數(shù)據(jù)源進行融合時選擇不同融合算法會導致不同的融合效果，不同的融合算法也有不同的優(yōu)點和缺點，文獻[3]將算法管理引入到融合的整個過程中，提高了融合效果的有效性和準確性，也對融合系統(tǒng)的性能評估帶來便利，可以從系統(tǒng)和模塊任一角度出發(fā)，進行性能分析。

目前針對航跡融合算法的性能分析，主要是對融合算法進行仿真，分析融合位置誤差[4-8]，對算法的計算量研究較少，但是有些融合算法是以計算量為代價提高精度，會增加所需信息量，增大計算機開銷[4]。位置精度誤差是評價融合算法性能的常用指標[9]，但計算量也是融合算法的一項重要指標，僅分析位置精度誤差，無法全面綜合地評價融合算法的性能。

針對航跡融合算法性能分析，一般只考慮融合誤差而無法全面評價融合算法的問題，本文提出了一種基于計算量的航跡融合算法性能分析方法。

1 問題描述與模型構(gòu)建

1.1 問題描述

正如前文所述，目前文獻對航跡融合算法性能分析時一般只考慮融合誤差，通過劇情設計和計算機仿真得出融合結(jié)果，比較融合精度，而不會考慮提高融合精度所帶來計算量增加、計算機開銷增大的代價，導致在評估算法、選取算法時不能綜合考慮算法的性能。

雖然文獻[10]從計算量和精度兩方面分析算法，但是只是對算法步驟進行了詳細的介紹和分析，并沒有量化計算量。文獻[11]會考慮處理時延來間接評價算法復雜度，但是針對同一算法，不同編程、不同硬件設施會有不同的處理時延，不能從根本上分析算法。文獻[12]雖指出鮮有文獻對算法運算量進行具體分析，但是該文獻只是對算法復雜度進行了簡單的分析。文獻[13]雖對計算量進行了量化，但是該文獻分析的算法不涉及矩陣運算，不適用于航跡融合算法的計算量分析。

本文針對以上問題，提出了以浮點操作數(shù)為單位的計算量理論分析方法實現(xiàn)航跡融合算法計算量的量化。

1.2 模型構(gòu)建

本文針對航跡融合算法進行性能分析，而未針對融合系統(tǒng)，因此不考慮關(guān)聯(lián)精度、丟點率等指標，只考慮計算量和精度兩方面。

對航跡融合算法進行性能分析時，不僅要在算法的基礎上分析航跡融合算法的計算量，還要對航跡融合算法進行仿真得出誤差結(jié)果，最后需要建立性能評估模型進行航跡融合算法進行綜合評價，評估步驟如圖1所示。

由于本文只從兩方面對融合算法進行性能評價，且融合算法計算量是確定值，所以本文采用加權(quán)法對兩個指標進行綜合評價，綜合評價模型為：

(1)

wi為主觀賦值，有些融合系統(tǒng)硬件設施較好，對計算量要求較小，便可將計算量的權(quán)重設置較小，若硬件設施對計算量要求較高，便可將計算量的權(quán)重設置較大些。xi為指標歸一化得分，其中誤差和計算量都為越小越優(yōu)型，即

(2)

式(2)中，R為位置誤差，Q為計算量。

圖1 評估步驟Fig.1 Evaluation step

2 計算量理論分析方法

首先進行航跡融合算法的計算量理論分析，本文以航跡融合算法中常用的簡單凸組合融合算法(Covari-ance Convex，CC)和Bar-Shalom-Campo融合算法(BC)兩種融合算法為例展開研究[4,14-15]。CC算法和BC算法都可以在不同情況下達到最優(yōu)，但兩者所需的信息量和計算量不同。算法的運行時間不僅與運行設備有很大的關(guān)系，并且也會隨著不同的算法編程而不同[16]。本節(jié)將對算法進行理論分析，以浮點操作數(shù)為單位統(tǒng)計原始算法主要步驟的計算量，對計算量進行量化，得到相應的總計算量解析表達式。

2.1 算法分析

在算法計算量理論分析之前，首先簡單介紹一下簡單凸組合和Bar-Shalom-Campo兩種航跡融合算法。

2.1.1 簡單凸組合航跡融合算法

簡單凸組合航跡融合算法是一種常用的分布式航跡融合算法[15]，當不存在過程噪聲，且傳感器在初始時刻的估計誤差不相關(guān)時，該算法是最優(yōu)的[17]。

融合中心對于任意兩個傳感器之間的航跡估計融合結(jié)果為：

(3)

協(xié)方差融合方程為：

P=Pi(Pi+Pj)Pj

(4)

對應的信息矩陣形式的表達式為：

(5)

擴展到N>2的情況，假設傳感器之間不存在誤差的相關(guān)性，則融合方程為：

(6)

具體推導過程見文獻[15]。

2.1.2BarShalom-Campo航跡融合算法

當航跡的局部估計誤差存在相關(guān)時，簡單凸組合融合算法就不能達到最優(yōu)，而Bar Shalom-Campo航跡融合算法考慮了各傳感器間誤差的相關(guān)性，可以實現(xiàn)最大似然條件下的最優(yōu)[7]。

假設航跡間的狀態(tài)估計誤差為：

(7)

則Dij的協(xié)方差陣為：

(8)

式(8)中關(guān)于Pij和Pji的計算所需資源，可由卡爾曼濾波估計器給出：

(9)

則兩個傳感器相應的狀態(tài)融合方程及誤差協(xié)方差為：

(10)

具體推導過程見文獻[15]。

當擴展到傳感器數(shù)目N>2時，相應的狀態(tài)融合方程及誤差協(xié)方差表示為[7,18-19]：

(11)

(12)

(13)

(14)

2.2 計算量分析

根據(jù)航跡融合算法的主要步驟，統(tǒng)計計算量，在統(tǒng)計計算量時，遵循以下幾個準則[20-23]：

1) 計算量種類歸納為加法運算、賦值運算、乘法運算和除法運算四種；

2) 一次賦值運算相當于一次加法運算；

3) 矩陣運算按元素來進行操作；

為了定量對融合算法的計算量進行分析，采用浮點操作數(shù)的方法進行統(tǒng)計。其中，將兩個浮點數(shù)的加、減、乘或除法運算定義為一次浮點操作數(shù)[24]。在算法的實現(xiàn)過程中，有些操作是無法通過簡單的加、減、乘、除來實現(xiàn)的，比如矩陣逆運算、矩陣轉(zhuǎn)置運算、指數(shù)運算、開方等，可采用相同時間的浮點操作數(shù)對其進行等效。下面對一些基本運算的浮點操作數(shù)進行說明：

1) 如果A∈Rn×m，B∈Rn×m，則A±B的浮點操作數(shù)為n×m；

2) 如果A∈Rn×m，B∈Rn×m，則AB的浮點操作數(shù)為2mnl-nl；

3) 如果A∈Rn×n，矩陣A-1的浮點操作數(shù)為n3；

4) 如果A∈Rn×m，矩陣AT的浮點操作數(shù)為mn；

在對兩種算法進行計算量統(tǒng)計時，假設系統(tǒng)中有N個p維傳感器跟蹤1個目標進行計算量分析，并記計算量為Q。

2.2.1CC算法的計算量分析

CC算法中計算量主要集中在協(xié)方差矩陣求逆運算上。

1) 求取協(xié)方差融合方程

擴展到N>2的情況，協(xié)方差融合方程為：

(15)

根據(jù)上面提到的浮點操作數(shù)說明，因為有N個p維傳感器跟蹤1個目標，所以協(xié)方差矩陣P為2p階，則(Pi)-1的浮點操作數(shù)為(2p)3，Pi+Pi的浮點操作數(shù)為(2p)2，賦值運算相當于加法運算，則為一次浮點操作數(shù)，矩陣賦值按元素進行操作為(2p)2，則每進行一次協(xié)方差融合運算浮點操作數(shù)的解析表達式為：

Q11=(2p)3N+(2p)2(N-1)+(2p)3+(2p)2=
(8p3+4p2)N+8p3

(16)

2) 航跡狀態(tài)估計融合方程

擴展到N>2的情況，則航跡狀態(tài)融合方程為：

(17)

Q12=[(2p)3+2(2p)2-2p]N+
2p(N-1)+2(2p)2=
(8p3+8p2)N+8p2-2p

(18)

則簡單凸組合融合算法每進行一次總運算計算量以浮點操作數(shù)為單位的解析表達式為：

Qcc=Q11+Q12=
(16p3+12p2)N+8p3+8p2-2p

(19)

2.2.2BC算法的計算量分析

BC算法比CC算法更為復雜，因為考慮了傳感器之間存在的過程噪聲和估計誤差之間的互協(xié)方差，其中計算量主要集中在求互協(xié)方差的運算上。

1) 互協(xié)方差運算

(20)

互協(xié)方差運算一般應用在兩個傳感器之間的融合，假設有N=2個傳感器，p維傳感器跟蹤1個目標。所以根據(jù)浮點操作數(shù)的說明，KH的浮點操作數(shù)為8p3-4p2，F(xiàn)Pij(k-1)FT的浮點操作數(shù)為32p3-4p2，GQGT的浮點操作數(shù)為8p3-2p2，賦值運算浮點操作數(shù)為(2p)2，此互協(xié)方差運算的浮點操作數(shù)解析表達式為88p3-2p2，則擴展到N>2個傳感器時，協(xié)方差運算總計算浮點操作數(shù)解析表達式為：

Q21=(88p3-2p2)(N2-N)

(21)

2) 協(xié)方差融合方程

(22)

Q22=8p3N3+32p3N2-4p2N+8p3

(23)

3) 航跡狀態(tài)估計融合方程

(24)

Q23=16p3N3+32p3N2+32p3N+
4p2N+8p3-4p2

(25)

所以Bar-Shalom-Campo融合算法擴展到N>2時，每進行一次總運算計算量以浮點操作數(shù)為單位的解析表達式為：

QBC=Q21+Q22+Q23=24p3N3+152p3N2-
2p2N2-56p3N+2p2N+16p3-4p2

(26)

3 仿真實驗

本節(jié)通過仿真實驗驗證計算量理論分析的正確性以及對誤差進行仿真分析，并通過評估模型對融合算法進行綜合評價。仿真時所使用計算機的配置為：CPU intel(R) Core(TM) 2.6 GHz；內(nèi)存4.00 GB；運行環(huán)境Matlab R2012b。本節(jié)的各仿真結(jié)果都是100次Monte Carlo仿真的均值。

3.1 仿真分析

本小節(jié)將通過改變傳感器的數(shù)量和維數(shù)，分別比較在兩種情況下CC算法和BC算法的運行時間，驗證計算量公式的正確性，并進行仿真分析兩種算法的位置誤差。

盡管Matlab采用經(jīng)過優(yōu)化以后的計算方式，與浮點操作數(shù)的計算方式不太一樣，仍然可以使用Matlab進行仿真分析，測量算法運行時間與外部條件的關(guān)系，用這些結(jié)果與計數(shù)結(jié)果相比較，雖有誤差，但在一定程度上可以驗證結(jié)論的正確性[25-26]。

首先討論二維的情況，在仿真中取N=2個p=2維雷達傳感器，量測誤差方差分別為100 m2和150 m2，對10批目標進行跟蹤，每1 s跟蹤一次，跟蹤100次。目標均以vx=100 m/s，vy=200 m/s的速度平行勻速直線運動，初值狀態(tài)橫坐標均為1 000 m，縱坐標分別為[1 000,2 000,3 000,4 000,5 000,6 000,7 000,8 000,9 000,10 000]m，過程噪聲方差為100 m2。目標的真實航跡、傳感器跟蹤航跡以及融合航跡如圖2所示，融合誤差以及傳感器的跟蹤位置精度誤差，如圖3所示。

圖2 目標軌跡Fig.2 Target track

圖3 位置精度誤差Fig.3 Position accuracy error

為了驗證計算量公式的正確性，在同種條件下分別對不同數(shù)目N的2維傳感器進行仿真，其中一個傳感器量測誤差方差為100 m2，其余方差全部為150 m2，進行100次Monte Carlo仿真求得均值后，傳感器誤差均值、CC算法和BC算法的誤差和運算時間比值如表1所示。

表1 實驗數(shù)據(jù)(情況1)Tab.1 Experimental data (Case 1)

本次仿真討論三維的情況，在仿真中假設有n=4個目標進行機動運動，取N=3個p=3維傳感器對目標進行跟蹤，量測噪聲分別為100 m2，150 m2和200 m2，四個目標初值狀態(tài)坐標分別為：[1 000,1 000,1 000]，[3 000,3 000,3 000]，[-4 000,4 000,2 000]，[-4 000,4 000,0]，目標1和目標2以vx=100 m/s，vy=200 m/s,vz=10 m/s的速度做勻速直線運動，目標3和目標4分別做機動運動，目標真實軌跡和跟蹤狀態(tài)軌跡以及融合軌跡如圖4所示，融合誤差以及傳感器的跟蹤位置精度誤差，如圖5所示。

圖4 目標軌跡Fig.4 Target trajectory

為了證明在此情況下計算量公式的正確性，同樣取不同數(shù)目N的傳感器，其中一個傳感器量測誤差方差為100 m2，其余方差全部為150 m2的三維傳感器進行仿真，其中n=4，進行100次Monte Carlo仿真求得均值后，傳感器以及兩個融合算法與真值的距離誤差均值以及CC算法和BC算法的運算時間比值如表2所示。

圖5 位置精度誤差Fig.5 Position accuracy error

p=3N=2N=3N=4N=5誤差/m傳感器196.50212.92213.20219.80CC140.34121.71109.17108.59BC138.29120.30108.79100.82計算量(跟蹤一次)CC1 3621 9022 4422 982BC18 93650 184101 268176 076時間比值CC/BC0.126 20.095 20.086 40.074 5

本小節(jié)從兩種情況下對簡單凸組合融合算法和Bar-Shalom-Campo融合算法進行了仿真分析，可以得出以下結(jié)論：

1) 在最小均方誤差估計的條件下，CC融合算法和BC融合算法都要優(yōu)于單個傳感器的跟蹤效果，在勻速直線運動時，CC算法的融合效果要略優(yōu)于BC算法，在機動條件下，BC算法的融合效果要略優(yōu)于CC算法。

2) 在計算量方面，簡單凸組合融合算法的計算量要比Bar-Shalom-Campo融合算法低很多，并且隨著傳感器維數(shù)的增加以及傳感器數(shù)目的增加，計算量差距越來越明顯。

3) 運行時間仿真結(jié)果與理論分析結(jié)果基本一致，雖然由于matlab本身原因，運行時間比值存在一定誤差，但在誤差允許范圍內(nèi)證明了計算量公式的正確性。

3.2 評估計算

本小節(jié)對情況2中N=2，p=3仿真結(jié)果進行評估計算，使用評估模型對兩種融合算法進行綜合評價得出結(jié)果。

1) 指標計算

根據(jù)越小越優(yōu)型計算方法，結(jié)合實驗仿真結(jié)果，求得CC算法和BC算法兩個指標歸一化得分分別為：xCC={0.48,1}，xBC={0.58,0}。

2) 設置權(quán)重

權(quán)重設置具有很強的主觀性，根據(jù)應用條件和環(huán)境進行設置。假如硬件設施對計算量要求較高，便將w2設置較高一些，此處取w1=0.45，w2=0.55。

3) 綜合評價

根據(jù)2)中假設的背景，使用式(1)中加權(quán)法對兩種融合算法綜合評價得出結(jié)果：CC算法得分0.766，BC算法得分0.261，由于對計算量要求較高，且BC算法和CC算法融合精度相差不大，經(jīng)綜合評價得出CC優(yōu)于BC算法，工程實踐中選擇CC算法。

4 結(jié)論

本文提出了基于計算量的航跡融合算法性能分析方法，該方法通過采用以浮點操作數(shù)為單位的方法統(tǒng)計算法主要步驟的計算量進行計算量理論分析，通過計算機仿真進行誤差仿真分析，最后通過綜合評估模型實現(xiàn)對融合算法的全面評價。仿真實驗結(jié)果表明，算法運行時間比值在一定誤差范圍內(nèi)驗證了計算量理論分析的正確性，新的性能分析方法可以有效地評價融合算法性能，為融合算法的性能分析提供參考。