基于計算量的航跡融合算法性能分析方法

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

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

0 引言

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

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

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

1 問題描述與模型構建

1.1 問題描述

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

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

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

1.2 模型構建

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

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

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

(1)

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

(2)

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

圖1 評估步驟Fig.1 Evaluation step

2 計算量理論分析方法

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

2.1 算法分析

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

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

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

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

(3)

協方差融合方程為：

P=Pi(Pi+Pj)Pj

(4)

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

(5)

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

(6)

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

2.1.2BarShalom-Campo航跡融合算法

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

假設航跡間的狀態估計誤差為：

(7)

則Dij的協方差陣為：

(8)

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

(9)

則兩個傳感器相應的狀態融合方程及誤差協方差為：

(10)

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

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

(11)

(12)

(13)

(14)

2.2 計算量分析

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

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

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

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

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

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

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

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

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

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

2.2.1CC算法的計算量分析

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

1) 求取協方差融合方程

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

(15)

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

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

(16)

2) 航跡狀態估計融合方程

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

(17)

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

(18)

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

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

(19)

2.2.2BC算法的計算量分析

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

1) 互協方差運算

(20)

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

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

(21)

2) 協方差融合方程

(22)

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

(23)

3) 航跡狀態估計融合方程

(24)

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

(25)

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

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

(26)

3 仿真實驗

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

3.1 仿真分析

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

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

首先討論二維的情況，在仿真中取N=2個p=2維雷達傳感器，量測誤差方差分別為100 m2和150 m2，對10批目標進行跟蹤，每1 s跟蹤一次，跟蹤100次。目標均以vx=100 m/s，vy=200 m/s的速度平行勻速直線運動，初值狀態橫坐標均為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

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

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

本次仿真討論三維的情況，在仿真中假設有n=4個目標進行機動運動，取N=3個p=3維傳感器對目標進行跟蹤，量測噪聲分別為100 m2，150 m2和200 m2，四個目標初值狀態坐標分別為：[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分別做機動運動，目標真實軌跡和跟蹤狀態軌跡以及融合軌跡如圖4所示，融合誤差以及傳感器的跟蹤位置精度誤差，如圖5所示。

圖4 目標軌跡Fig.4 Target trajectory

為了證明在此情況下計算量公式的正確性，同樣取不同數目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

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

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

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

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

3.2 評估計算

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

1) 指標計算

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

2) 設置權重

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

3) 綜合評價

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

4 結論

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