李月武，劉長(zhǎng)江，胡建旺，吉 兵，張岐龍

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

0 引言

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

目前針對(duì)航跡融合算法的性能分析，主要是對(duì)融合算法進(jìn)行仿真，分析融合位置誤差[4-8]，對(duì)算法的計(jì)算量研究較少，但是有些融合算法是以計(jì)算量為代價(jià)提高精度，會(huì)增加所需信息量，增大計(jì)算機(jī)開(kāi)銷[4]。位置精度誤差是評(píng)價(jià)融合算法性能的常用指標(biāo)[9]，但計(jì)算量也是融合算法的一項(xiàng)重要指標(biāo)，僅分析位置精度誤差，無(wú)法全面綜合地評(píng)價(jià)融合算法的性能。

針對(duì)航跡融合算法性能分析，一般只考慮融合誤差而無(wú)法全面評(píng)價(jià)融合算法的問(wèn)題，本文提出了一種基于計(jì)算量的航跡融合算法性能分析方法。

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

1.1 問(wèn)題描述

正如前文所述，目前文獻(xiàn)對(duì)航跡融合算法性能分析時(shí)一般只考慮融合誤差，通過(guò)劇情設(shè)計(jì)和計(jì)算機(jī)仿真得出融合結(jié)果，比較融合精度，而不會(huì)考慮提高融合精度所帶來(lái)計(jì)算量增加、計(jì)算機(jī)開(kāi)銷增大的代價(jià)，導(dǎo)致在評(píng)估算法、選取算法時(shí)不能綜合考慮算法的性能。

雖然文獻(xiàn)[10]從計(jì)算量和精度兩方面分析算法，但是只是對(duì)算法步驟進(jìn)行了詳細(xì)的介紹和分析，并沒(méi)有量化計(jì)算量。文獻(xiàn)[11]會(huì)考慮處理時(shí)延來(lái)間接評(píng)價(jià)算法復(fù)雜度，但是針對(duì)同一算法，不同編程、不同硬件設(shè)施會(huì)有不同的處理時(shí)延，不能從根本上分析算法。文獻(xiàn)[12]雖指出鮮有文獻(xiàn)對(duì)算法運(yùn)算量進(jìn)行具體分析，但是該文獻(xiàn)只是對(duì)算法復(fù)雜度進(jìn)行了簡(jiǎn)單的分析。文獻(xiàn)[13]雖對(duì)計(jì)算量進(jìn)行了量化，但是該文獻(xiàn)分析的算法不涉及矩陣運(yùn)算，不適用于航跡融合算法的計(jì)算量分析。

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

1.2 模型構(gòu)建

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

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

由于本文只從兩方面對(duì)融合算法進(jìn)行性能評(píng)價(jià)，且融合算法計(jì)算量是確定值，所以本文采用加權(quán)法對(duì)兩個(gè)指標(biāo)進(jìn)行綜合評(píng)價(jià)，綜合評(píng)價(jià)模型為：

(1)

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

(2)

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

圖1 評(píng)估步驟Fig.1 Evaluation step

2 計(jì)算量理論分析方法

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

2.1 算法分析

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

2.1.1 簡(jiǎn)單凸組合航跡融合算法

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

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

(3)

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

P=Pi(Pi+Pj)Pj

(4)

對(duì)應(yīng)的信息矩陣形式的表達(dá)式為：

(5)

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

(6)

具體推導(dǎo)過(guò)程見(jiàn)文獻(xiàn)[15]。

2.1.2BarShalom-Campo航跡融合算法

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

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

(7)

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

(8)

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

(9)

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

(10)

具體推導(dǎo)過(guò)程見(jiàn)文獻(xiàn)[15]。

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

(11)

(12)

(13)

(14)

2.2 計(jì)算量分析

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

1) 計(jì)算量種類歸納為加法運(yùn)算、賦值運(yùn)算、乘法運(yùn)算和除法運(yùn)算四種；

2) 一次賦值運(yùn)算相當(dāng)于一次加法運(yùn)算；

3) 矩陣運(yùn)算按元素來(lái)進(jìn)行操作；

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

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

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

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

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

在對(duì)兩種算法進(jìn)行計(jì)算量統(tǒng)計(jì)時(shí)，假設(shè)系統(tǒng)中有N個(gè)p維傳感器跟蹤1個(gè)目標(biāo)進(jìn)行計(jì)算量分析，并記計(jì)算量為Q。

2.2.1CC算法的計(jì)算量分析

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

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

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

(15)

根據(jù)上面提到的浮點(diǎn)操作數(shù)說(shuō)明，因?yàn)橛蠳個(gè)p維傳感器跟蹤1個(gè)目標(biāo)，所以協(xié)方差矩陣P為2p階，則(Pi)-1的浮點(diǎn)操作數(shù)為(2p)3，Pi+Pi的浮點(diǎn)操作數(shù)為(2p)2，賦值運(yùn)算相當(dāng)于加法運(yùn)算，則為一次浮點(diǎn)操作數(shù)，矩陣賦值按元素進(jìn)行操作為(2p)2，則每進(jìn)行一次協(xié)方差融合運(yùn)算浮點(diǎn)操作數(shù)的解析表達(dá)式為：

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

(16)

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

擴(kuò)展到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)

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

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

(19)

2.2.2BC算法的計(jì)算量分析

BC算法比CC算法更為復(fù)雜，因?yàn)榭紤]了傳感器之間存在的過(guò)程噪聲和估計(jì)誤差之間的互協(xié)方差，其中計(jì)算量主要集中在求互協(xié)方差的運(yùn)算上。

1) 互協(xié)方差運(yùn)算

(20)

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

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

(21)

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

(22)

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

(23)

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

(24)

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

(25)

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

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

(26)

3 仿真實(shí)驗(yàn)

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

3.1 仿真分析

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

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

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

圖2 目標(biāo)軌跡Fig.2 Target track

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

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

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

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

圖4 目標(biāo)軌跡Fig.4 Target trajectory

為了證明在此情況下計(jì)算量公式的正確性，同樣取不同數(shù)目N的傳感器，其中一個(gè)傳感器量測(cè)誤差方差為100 m2，其余方差全部為150 m2的三維傳感器進(jìn)行仿真，其中n=4，進(jìn)行100次Monte Carlo仿真求得均值后，傳感器以及兩個(gè)融合算法與真值的距離誤差均值以及CC算法和BC算法的運(yùn)算時(shí)間比值如表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計(jì)算量(跟蹤一次)CC1 3621 9022 4422 982BC18 93650 184101 268176 076時(shí)間比值CC/BC0.126 20.095 20.086 40.074 5

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

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

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

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

3.2 評(píng)估計(jì)算

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

1) 指標(biāo)計(jì)算

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

2) 設(shè)置權(quán)重

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

3) 綜合評(píng)價(jià)

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

4 結(jié)論

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