一種基于B+樹航跡態(tài)勢(shì)回放系統(tǒng)的設(shè)計(jì)與實(shí)驗(yàn)

張 明 杰

(中國(guó)電子科學(xué)研究院 北京 100041)

0 引 言

態(tài)勢(shì)是指戰(zhàn)場(chǎng)空間中兵力分布和戰(zhàn)場(chǎng)環(huán)境的當(dāng)前狀態(tài)及發(fā)展變化趨勢(shì)的總稱[1]。態(tài)勢(shì)回放是將指定歷史時(shí)間段內(nèi)的態(tài)勢(shì)信息(比如探測(cè)源探測(cè)到的航跡信息、從通信鏈路接收到的航跡信息、戰(zhàn)場(chǎng)元素自身的位置變化信息等)按照時(shí)間順序動(dòng)態(tài)地顯示在計(jì)算機(jī)圖形界面上。態(tài)勢(shì)回放為相關(guān)人員進(jìn)行態(tài)勢(shì)分析提供了一種方便易用的技術(shù)手段，在傳感器探測(cè)效能分析、演習(xí)效果評(píng)估等方面具有重要的作用。

國(guó)外一般將態(tài)勢(shì)回放作為事后回顧和分析的基礎(chǔ)內(nèi)容[2-3]。國(guó)內(nèi)一些學(xué)者也對(duì)態(tài)勢(shì)回放技術(shù)進(jìn)行了研究和實(shí)現(xiàn)，如基于HLA的態(tài)勢(shì)回放系統(tǒng)[4]、基于Skyline態(tài)勢(shì)回放系統(tǒng)[5-6]、基于XSimStudio的態(tài)勢(shì)回放系統(tǒng)[7]、基于數(shù)據(jù)庫(kù)的態(tài)勢(shì)回放系統(tǒng)[8]、基于C/S架構(gòu)的態(tài)勢(shì)回放系統(tǒng)[9]等。但這些態(tài)勢(shì)回放系統(tǒng)大多是對(duì)模擬或仿真產(chǎn)生的態(tài)勢(shì)數(shù)據(jù)進(jìn)行回放，對(duì)真實(shí)態(tài)勢(shì)數(shù)據(jù)進(jìn)行回放的系統(tǒng)目前并不多見(jiàn)，并且，在數(shù)據(jù)量較大時(shí)，存在回放效率不高的問(wèn)題[3，10]。

B+樹是一種高度平衡樹，是在B樹[11]的基礎(chǔ)上由Knuth實(shí)現(xiàn)并由Comer命名的一種索引技術(shù)[12-13]，具有隨機(jī)和順序查詢效率高、更新開銷小、高度自平衡等特點(diǎn)，特別適用于既需要隨機(jī)查找也需要順序查找

的應(yīng)用場(chǎng)景。目前，B+樹已在大數(shù)據(jù)索引[14]、云數(shù)據(jù)索引[15]、數(shù)據(jù)庫(kù)[16]等眾多領(lǐng)域得到廣泛應(yīng)用。

本文提出的基于B+樹的態(tài)勢(shì)回放系統(tǒng)，以某大型電子信息系統(tǒng)運(yùn)行過(guò)程中感知并記錄的真實(shí)態(tài)勢(shì)數(shù)據(jù)文件作為數(shù)據(jù)源，從中提取態(tài)勢(shì)信息(航跡點(diǎn))，使用B+樹文件對(duì)海量的航跡點(diǎn)進(jìn)行組織、查詢，并對(duì)航跡點(diǎn)集合進(jìn)行態(tài)勢(shì)計(jì)算及顯示，實(shí)現(xiàn)了真實(shí)態(tài)勢(shì)數(shù)據(jù)的回放。由于將航跡點(diǎn)作為關(guān)鍵字存儲(chǔ)在B+樹文件中，利用了B+樹隨機(jī)查找和順序讀取數(shù)據(jù)的高效性，使得本文實(shí)現(xiàn)的態(tài)勢(shì)回放系統(tǒng)具有較高的效率。

1 相關(guān)概念

為了便于對(duì)系統(tǒng)工作原理進(jìn)行表述，本節(jié)使用集合論的語(yǔ)言對(duì)與態(tài)勢(shì)回放相關(guān)的概念和術(shù)語(yǔ)進(jìn)行形式化定義。

1.1 航跡點(diǎn)

航跡點(diǎn)是態(tài)勢(shì)回放系統(tǒng)的基本數(shù)據(jù)單元，是包含時(shí)間、航跡號(hào)、位置等信息的元組。本文將航跡點(diǎn)表示為一個(gè)具有五維分量的數(shù)據(jù)單元：

p=〈t,n,x,y,z〉

(1)

式中：p表示航跡點(diǎn)；t∈(表示自然數(shù)集合)代表時(shí)間(以公元元年1月1日零時(shí)為時(shí)間起始點(diǎn))，單位是ms；n∈代表航跡號(hào)；x∈(表示實(shí)數(shù)集合)、y∈、z∈，表征航跡點(diǎn)的三維空間坐標(biāo)，單位為m。

p的各組成元素t、n、x、y、z稱為p的分量。

1.2 航跡點(diǎn)之間的基本關(guān)系

(1) 相等關(guān)系 設(shè)pi與pj(i,j∈)是任意兩個(gè)航跡點(diǎn)，若pi與pj的各個(gè)組成分量相等，則稱這兩個(gè)航跡點(diǎn)相等，否則稱這兩個(gè)航跡點(diǎn)不相等。

(2) 大于關(guān)系 設(shè)pi與pj(i,j∈)是兩個(gè)航跡點(diǎn)，若pi的任一分量按從左向右的順序大于pj的相應(yīng)分量，則稱航跡點(diǎn)pi大于pj。

(3) 小于關(guān)系 設(shè)pi與pj(i,j∈)為兩個(gè)航跡點(diǎn)，若pi的任一分量按從左向右的順序小于pj的相應(yīng)分量，則稱航跡點(diǎn)pi小于pj。

(4) 航跡點(diǎn)之間的距離 航跡點(diǎn)pi與pj之間的距離d定義為：

(2)

(5) 航跡點(diǎn)之間的時(shí)間差 航跡點(diǎn)pi與pj之間的時(shí)間差Δt定義為：

Δt(pi,pj)=|pi.t-pj.t|

(3)

1.3 有序航跡點(diǎn)集合與同跡關(guān)系

(1) 有序航跡點(diǎn)集合 設(shè)P={pk|k=1,2,…,K;K∈∧K>0}是一個(gè)有限的航跡點(diǎn)集合，任意兩個(gè)元素pi

(2) 同跡關(guān)系 設(shè)P是一個(gè)有序航跡點(diǎn)集合，pi,pj∈P，若pi與pj的航跡號(hào)相同，且時(shí)間差和距離均不大于相應(yīng)的給定閾值，則稱pi與pj滿足直接同跡關(guān)系DST(Direct Same Track)。形式化表示為：

DST(pi,pj)?(pi.n=pj.n)∧

(Δt(pi,pj)≤Tht)∧(d(pi,pj)≤Thd)

(4)

式中：Tht與Thd是給定的時(shí)間閾值和距離閾值。

若在pi與pj之間存在一個(gè)長(zhǎng)度為l(是正整數(shù))的航跡點(diǎn)列〈pi+a1,pi+a2,…,pi+al〉，使得DST(pi,pi+a1)、DST(pi+a1,pi+a2)、…、DST(pi+al,pj)均成立，則稱pi與pj滿足間接同跡關(guān)系IST(Indirect Same Track)。

直接同跡關(guān)系和間接同跡關(guān)系統(tǒng)稱為同跡關(guān)系ST(Same Track)。容易證明，同跡關(guān)系滿足自反性、對(duì)稱性和傳遞性，從而是有序航跡點(diǎn)集合上的等價(jià)關(guān)系，可以對(duì)有序航跡點(diǎn)集合進(jìn)行劃分，即可使用同跡關(guān)系將有序航跡點(diǎn)集合劃分為若干個(gè)互不相交的子集，每個(gè)子集作為一條航跡的一個(gè)組成部分。

1.4 航 跡

設(shè)P是一個(gè)有序航跡點(diǎn)集合，將P中一個(gè)滿足同跡關(guān)系的有序航跡點(diǎn)子集及其相關(guān)的特征信息(如航跡號(hào)、航跡長(zhǎng)度等)的組合，稱作一條航跡tr(Track)。形式化表示為：

tr=〈No,Len,ts,td,Tp〉

(5)

式中：有序航跡點(diǎn)子集Tp={p1,p2,…,pLen}?P，Tp中任意兩個(gè)航跡點(diǎn)之間滿足同跡關(guān)系，且任意兩個(gè)相鄰航跡點(diǎn)之間滿足直接同跡關(guān)系；No表示航跡號(hào)，與Tp中的航跡點(diǎn)的航跡號(hào)相同；Len表示航跡的長(zhǎng)度，即Tp中元素的個(gè)數(shù)；ts、td表示航跡的起止時(shí)間，即Tp中第一個(gè)航跡點(diǎn)和最后一個(gè)航跡點(diǎn)的時(shí)間。

1.5 航跡與航跡點(diǎn)匹配

一條航跡tr與一個(gè)航跡點(diǎn)p匹配是指tr的最后一個(gè)航跡點(diǎn)與p滿足直接同跡關(guān)系。形式化表示為：

Match(tr,p)?DST(tr.Tp.pLen,p)

(6)

式中：tr.Tp.pLen表示航跡tr的有序航跡點(diǎn)集的最后一個(gè)元素。

1.6 時(shí)間窗

時(shí)間窗即一個(gè)時(shí)間段的別名。形式化表示為：

tw=[tb,te]=[tb,tb+w]

(7)

式中：tw表示時(shí)間窗；tb表示時(shí)間窗的起始時(shí)間；te表示時(shí)間窗的終止時(shí)間；w表示時(shí)間窗的寬度。本文中，tw、tb、w的單位是ms，取值范圍是自然數(shù)集合。

1.7 有序航跡點(diǎn)集合在時(shí)間窗內(nèi)的投影

有序航跡點(diǎn)集合P在時(shí)間窗tw內(nèi)的投影即P中所有時(shí)間值在tw范圍內(nèi)的航跡點(diǎn)的集合。形式化表示為：

proj(P,tw)={p|(p∈P)∧(tw.tb≤p.t≤tw.te)}

(8)

1.8 態(tài) 勢(shì)

態(tài)勢(shì)Sit(Situation)特指由有序航跡點(diǎn)集合P依同跡關(guān)系劃分而得的航跡集合。設(shè)P中的航跡點(diǎn)依同跡關(guān)系可劃分為L(zhǎng)個(gè)子集，則由P產(chǎn)生的態(tài)勢(shì)可形式化表示為：

Sit(P)=P/ST={tr1,tr2,…,trL}

(9)

式中：P/ST表示用同跡關(guān)系ST對(duì)有序航跡點(diǎn)集合P進(jìn)行劃分。

在時(shí)間窗tw內(nèi)由P產(chǎn)生的態(tài)勢(shì)，稱為一幀態(tài)勢(shì)或態(tài)勢(shì)幀。形式化表示為：

Sit(P,tw)=proj(P,tw)/ST={tr1,tr2,…,trLw}

(10)

式中：proj(P,tw)/ST表示用同跡關(guān)系ST對(duì)有序航跡點(diǎn)集合P在時(shí)間段tw內(nèi)的投影的劃分，Lw表示劃分后形成的航跡的條數(shù)。

與態(tài)勢(shì)相關(guān)的說(shuō)明：(1) 因?yàn)橐粭l航跡是滿足某些特性的航跡點(diǎn)集合及其特征描述信息的組合，所以，從本質(zhì)上講，態(tài)勢(shì)也可以看作是航跡點(diǎn)的集合；(2) 將有序航跡點(diǎn)集合依同跡關(guān)系進(jìn)行劃分形成航跡集合的過(guò)程稱為態(tài)勢(shì)計(jì)算；(3) 態(tài)勢(shì)顯示時(shí)，除了顯示航跡點(diǎn)之外，還將屬于同一條航跡的航跡點(diǎn)之間按時(shí)間先后順序使用線段連接，以便于進(jìn)行觀察和分析。

2 B+樹及B+樹文件

為了從海量航跡點(diǎn)中查找到指定時(shí)間窗內(nèi)的航跡點(diǎn)子集，本文將所有航跡點(diǎn)以B+樹文件的形式進(jìn)行組織，利用B+樹隨機(jī)查找和順序讀取數(shù)據(jù)的高效性，保證回放系統(tǒng)的效率。

本節(jié)參照文獻(xiàn)[17-18]中B+樹的描述，對(duì)回放系統(tǒng)使用的以式(1)定義的航跡點(diǎn)作為關(guān)鍵字的B+樹及B+樹文件進(jìn)行介紹。

2.1 B+樹的定義

階數(shù)為M的B+樹要么是空樹，要么是滿足下列特性的M叉樹：

1) 樹中每個(gè)節(jié)點(diǎn)至多有M棵子樹。

2) 若根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則至少有兩棵子樹。

4) 任一節(jié)點(diǎn)的邏輯結(jié)構(gòu)可表示為(n;p0,A0,p1,A1,…,pn-1,An-1;AL,AR)。其中：pi(i=0,1,…,n-1)為航跡點(diǎn)(即關(guān)鍵字)，且pi

5) 所有的葉節(jié)點(diǎn)都出現(xiàn)在同一層次上，且包含了全部航跡點(diǎn)。葉節(jié)點(diǎn)按照航跡點(diǎn)從小到大的順序鏈接，即若當(dāng)前節(jié)點(diǎn)的指針AL、AR非空，則AL指向的節(jié)點(diǎn)中的所有航跡點(diǎn)均小于當(dāng)前節(jié)點(diǎn)的p0，AR指向的節(jié)點(diǎn)中的所有航跡點(diǎn)均大于當(dāng)前節(jié)點(diǎn)的pn-1。

6) 左兄弟節(jié)點(diǎn)指針AL為空的葉節(jié)點(diǎn)，稱為最小葉節(jié)點(diǎn)；右兄弟節(jié)點(diǎn)指針AR為空的葉節(jié)點(diǎn)，稱為最大葉節(jié)點(diǎn)。

7) 從根節(jié)點(diǎn)到某個(gè)葉節(jié)點(diǎn)途經(jīng)的節(jié)點(diǎn)集合，稱為一條葉路徑。

上述定義中，以航跡點(diǎn)作為B+樹節(jié)點(diǎn)的關(guān)鍵字，航跡點(diǎn)之間的大小關(guān)系由式(3)和式(4)定義。

2.2 B+樹文件

B+樹文件是在存儲(chǔ)介質(zhì)(如硬盤)上保存的二進(jìn)制數(shù)據(jù)文件，由文件頭和文件體兩部分組成。其邏輯結(jié)構(gòu)如圖1所示。

圖1 B+樹文件邏輯結(jié)構(gòu)圖

文件頭描述文件中保存的B+樹的特征信息，包含的信息項(xiàng)主要有：

1) 階數(shù)M；

2) 航跡點(diǎn)(即關(guān)鍵字)總數(shù)nTrkPtCount(即所有葉節(jié)點(diǎn)中包含的航跡點(diǎn)的個(gè)數(shù))；

3) 節(jié)點(diǎn)總數(shù)nNodeCount；

梁肇彬供述稱：“鄧強(qiáng)是城投公司的董事長(zhǎng)，對(duì)城投公司及其下屬公司的事務(wù)有決定權(quán)，如果沒(méi)有他的同意，我不可能順利借助城投公司下屬的建筑公司的資質(zhì)承建上述工程項(xiàng)目，在工程款支付方面也不可能那么順利。我送錢給鄧強(qiáng)也是為了和他搞好關(guān)系，以后可以繼續(xù)合作，多承接一些工程?！?/p>

4) 指向根節(jié)點(diǎn)的指針pRootNode(即根節(jié)點(diǎn)在文件中的位置)；

5) 指向最小葉節(jié)點(diǎn)的指針pMinLeafNode(即最小葉節(jié)點(diǎn)在文件中的位置)；

6) 指向最大葉節(jié)點(diǎn)的指針pMaxLeafNode(即最大葉節(jié)點(diǎn)在文件中的位置)。

文件體保存的是一棵B+樹，即B+樹包含的所有節(jié)點(diǎn)數(shù)據(jù)。每個(gè)節(jié)點(diǎn)中的指針表示的是其指向的節(jié)點(diǎn)在文件中的位置。

3 系統(tǒng)的組成、工作流程及關(guān)鍵算法

3.1 系統(tǒng)的組織結(jié)構(gòu)

本文提出的態(tài)勢(shì)回放系統(tǒng)由態(tài)勢(shì)數(shù)據(jù)文件、數(shù)據(jù)文件對(duì)象、航跡點(diǎn)提取器、B+樹文件、B+樹文件對(duì)象、回放控制器、顯示組件等幾部分組成，系統(tǒng)運(yùn)行時(shí)的組織結(jié)構(gòu)如圖2所示。

圖2 態(tài)勢(shì)回放系統(tǒng)組織結(jié)構(gòu)圖

各組成部分的功能簡(jiǎn)述如下：

態(tài)勢(shì)數(shù)據(jù)文件是指由電子信息系統(tǒng)感知并記錄的、包含有航跡點(diǎn)數(shù)據(jù)的二進(jìn)制文件。由于電子信息系統(tǒng)運(yùn)行的網(wǎng)絡(luò)環(huán)境可能采取無(wú)連接的通信協(xié)議，所以不能保證數(shù)據(jù)文件中航跡點(diǎn)的時(shí)間值按存儲(chǔ)順序單調(diào)遞增。

數(shù)據(jù)文件對(duì)象負(fù)責(zé)從態(tài)勢(shì)數(shù)據(jù)文件中將包含航跡點(diǎn)的數(shù)據(jù)報(bào)文按存儲(chǔ)順序讀取出來(lái)，并將其傳輸給航跡點(diǎn)提取器。

航跡點(diǎn)提取器負(fù)責(zé)從數(shù)據(jù)報(bào)文中提取出航跡點(diǎn)。

B+樹文件對(duì)象是系統(tǒng)的關(guān)鍵組成部分。負(fù)責(zé)將航跡點(diǎn)寫入B+樹文件、按回放控制器指定的時(shí)間窗從B+樹文件中讀取航跡點(diǎn)并將其傳輸給顯示組件。

回放控制器是用戶與系統(tǒng)進(jìn)行交互的界面元素，負(fù)責(zé)創(chuàng)建數(shù)據(jù)文件對(duì)象、航跡點(diǎn)提取器、B+樹文件對(duì)象、顯示組件等運(yùn)行時(shí)內(nèi)存對(duì)象。用戶可通過(guò)回放控制器界面上的時(shí)間控制控件(如滑動(dòng)控件)控制態(tài)勢(shì)的計(jì)算與顯示。

顯示組件負(fù)責(zé)態(tài)勢(shì)的計(jì)算和顯示。

3.2 系統(tǒng)的工作流程

系統(tǒng)的工作流程可以分為兩個(gè)階段：第一階段，從態(tài)勢(shì)數(shù)據(jù)文件中提取航跡點(diǎn)，形成B+樹文件，稱作回放文件形成階段或態(tài)勢(shì)回放預(yù)處理階段；第二階段，基于回放文件進(jìn)行態(tài)勢(shì)回放，稱作態(tài)勢(shì)回放階段。兩個(gè)階段的工作流程敘述如下(為了簡(jiǎn)化，未進(jìn)行出錯(cuò)處理的描述)。

態(tài)勢(shì)回放預(yù)處理階段的工作流程為：

1) 用戶通過(guò)回放控制器指定態(tài)勢(shì)數(shù)據(jù)文件名、欲保存的B+樹文件名；

2) 回放控制器為態(tài)勢(shì)數(shù)據(jù)文件創(chuàng)建數(shù)據(jù)文件對(duì)象，并創(chuàng)建航跡點(diǎn)提取器及B+樹文件對(duì)象；

3) 數(shù)據(jù)文件對(duì)象判斷文件讀取是否讀取完畢，若讀取完畢，則轉(zhuǎn)7)；否則，讀取一個(gè)數(shù)據(jù)報(bào)文；

4) 數(shù)據(jù)文件對(duì)象將讀取的數(shù)據(jù)報(bào)文傳輸給航跡點(diǎn)提取器；

5) 航跡點(diǎn)提取器從數(shù)據(jù)報(bào)文中提取航跡點(diǎn)，并將航跡點(diǎn)傳輸給B+樹文件對(duì)象；

6) B+樹文件對(duì)象將航跡點(diǎn)寫入B+樹文件；轉(zhuǎn)步驟3)；

7) 銷毀創(chuàng)建的內(nèi)存對(duì)象，態(tài)勢(shì)回放預(yù)處理工作完成。

態(tài)勢(shì)回放階段的工作流程為：

1) 用戶通過(guò)回放控制器指定需要進(jìn)行回放的B+樹文件名；

2) 回放控制器為指定的文件創(chuàng)建B+樹文件對(duì)象；

3) 回放控制器通過(guò)B+樹文件對(duì)象獲得態(tài)勢(shì)的起止時(shí)間，并設(shè)置時(shí)間控制控件的范圍；

4) 用戶通過(guò)回放控制器，設(shè)置時(shí)間窗的寬度及起止時(shí)間；

5) B+樹文件對(duì)象根據(jù)時(shí)間窗的起止時(shí)間，將B+樹中在時(shí)間窗內(nèi)的航跡點(diǎn)傳輸給顯示組件；

6) 顯示組件基于接收到的航跡點(diǎn)集合進(jìn)行態(tài)勢(shì)計(jì)算(航跡形成算法詳見(jiàn)4.2節(jié))和態(tài)勢(shì)顯示。

4 關(guān)鍵算法

4.1 航跡點(diǎn)批量插入算法

為了提高態(tài)勢(shì)回放預(yù)處理階段的工作效率，設(shè)計(jì)并實(shí)現(xiàn)了航跡點(diǎn)批量插入算法。該算法在B+樹文件對(duì)象中實(shí)現(xiàn)，用于態(tài)勢(shì)回放預(yù)處理階段的步驟6)。具體描述如下：

算法1航跡點(diǎn)批量插入算法

輸入：航跡點(diǎn)集合P。

輸出：將P中的航跡點(diǎn)插入B+樹文件。

Step1將P中的航跡點(diǎn)按從小到大順序進(jìn)行排序，形成有序航跡點(diǎn)集合PT。

Step2將PT整批插入B+樹文件中。對(duì)于非葉節(jié)點(diǎn)，利用節(jié)點(diǎn)上的航跡點(diǎn)將PT劃分為若干有序子集，把各子集插入該節(jié)點(diǎn)的相應(yīng)子節(jié)點(diǎn)；對(duì)于葉節(jié)點(diǎn)，則將該節(jié)點(diǎn)中的航跡點(diǎn)和待插入的航跡點(diǎn)合并排序，形成臨時(shí)節(jié)點(diǎn)。

Step3若臨時(shí)節(jié)點(diǎn)中包含的航跡點(diǎn)個(gè)數(shù)NL不大于B+樹的階數(shù)M，則將臨時(shí)節(jié)點(diǎn)寫入文件，完成節(jié)點(diǎn)更新；否則，將臨時(shí)節(jié)點(diǎn)分裂為NL/M個(gè)節(jié)點(diǎn)，并把這些節(jié)點(diǎn)的指針和最小關(guān)鍵字插入父節(jié)點(diǎn)；若父節(jié)點(diǎn)需要分裂，則繼續(xù)向上分裂，直到無(wú)需分裂為止。

Step4根據(jù)更新節(jié)點(diǎn)及新建節(jié)點(diǎn)的情況，修改B+樹文件頭。

該算法在一般情況下，相對(duì)于每次只插入一個(gè)航跡點(diǎn)的算法，可大大提高系統(tǒng)的性能，縮短回放預(yù)處理的時(shí)間。算法性能的具體分析請(qǐng)參閱文獻(xiàn)[20]。

4.2 航跡形成算法

為了有效地將某個(gè)時(shí)間窗內(nèi)的航跡點(diǎn)集合形成航跡集合(即態(tài)勢(shì)幀)，本文提出了基于航跡表的航跡形成算法，描述如下：

算法2航跡形成算法

輸入：航跡點(diǎn)集合P。

輸出：航跡表TR。

Step1初始化TR為空。

Step2順序掃描P中的所有航跡點(diǎn)pi(i=0,1,…,N-1)，N為P中元素的個(gè)數(shù)。

Step3將TR中的航跡與pi進(jìn)行匹配。若匹配不成功，則新建一個(gè)航跡tr，插入航跡表TR中；若某個(gè)航跡tr與pi匹配成功，則使用pi的信息修改pi，比如將航跡長(zhǎng)度加1、更改航跡的終止時(shí)間、使用pi代替最后一個(gè)航跡點(diǎn)等。

航跡形成算法在顯示組件中實(shí)現(xiàn)。該算法空間復(fù)雜度為O(N)，時(shí)間復(fù)雜度在一般情況下為O(N2)，若對(duì)航跡表中的元素進(jìn)行排序，則時(shí)間復(fù)雜度可改善為O(Nlog2N)。

5 系統(tǒng)實(shí)現(xiàn)及實(shí)驗(yàn)

5.1 運(yùn)行環(huán)境

在通用的個(gè)人臺(tái)式計(jì)算機(jī)上，使用Visual Studio 2010的C++語(yǔ)言對(duì)系統(tǒng)進(jìn)行了實(shí)現(xiàn)(背景地圖使用第三方軟件)。

臺(tái)式計(jì)算機(jī)的詳細(xì)配置信息為如下：

臺(tái)式計(jì)算機(jī)型號(hào)：Dell XPS 8300。

操作系統(tǒng)：Windows XP Professional with SP3。

CPU：英特爾第二代酷睿i5-2310，主頻2.9 GHz，四核。

內(nèi)存：4 GB，南亞易勝DDR3，1.333 GHz。

硬盤：西部數(shù)據(jù)WDC WD10EALX-759BA1，容量1 TB，每分鐘7 200轉(zhuǎn)。

顯卡：獨(dú)立顯卡，ATI Radeon HD 6700 Series。

5.2 系統(tǒng)性能評(píng)價(jià)指標(biāo)

為了對(duì)態(tài)勢(shì)回放系統(tǒng)的性能進(jìn)行評(píng)價(jià)，本文提出了繪點(diǎn)數(shù)據(jù)率的概念，即一幀態(tài)勢(shì)所含的航跡點(diǎn)數(shù)與繪制該幀態(tài)勢(shì)的核心代碼運(yùn)行所需時(shí)間的比值，單位為點(diǎn)/s。繪制一幀態(tài)勢(shì)的核心代碼完成的功能主要包括：(1) B+樹文件對(duì)象根據(jù)時(shí)間控制器給定的時(shí)間窗起止時(shí)間，從B+樹的根節(jié)點(diǎn)(駐留在硬盤上)到葉節(jié)點(diǎn)進(jìn)行搜索，找到起始時(shí)間對(duì)應(yīng)的葉節(jié)點(diǎn)的位置；(2) 從起始時(shí)間對(duì)應(yīng)的葉節(jié)點(diǎn)開始，到終止時(shí)間對(duì)應(yīng)的葉節(jié)點(diǎn)為止，順序訪問(wèn)各葉節(jié)點(diǎn)中的在起止時(shí)間范圍內(nèi)的航跡點(diǎn)，并將這些航跡點(diǎn)傳輸給顯示組件進(jìn)行態(tài)勢(shì)計(jì)算和顯示。

5.3 系統(tǒng)運(yùn)行實(shí)驗(yàn)

系統(tǒng)運(yùn)行時(shí)，將B+樹文件的階數(shù)設(shè)置為256，航跡點(diǎn)批量插入算法的航跡點(diǎn)集合的個(gè)數(shù)設(shè)置為1 024，即在B+樹文件的形成過(guò)程中，每次最多向其中插入1 024個(gè)航跡點(diǎn)。態(tài)勢(shì)回放時(shí)時(shí)間窗寬度為100 s。

系統(tǒng)運(yùn)行的圖形界面如圖3所示，用戶可通過(guò)態(tài)勢(shì)回放控制器上的滑動(dòng)條控件改變時(shí)間窗的起止時(shí)間，實(shí)現(xiàn)態(tài)勢(shì)動(dòng)態(tài)顯示。

圖3 態(tài)勢(shì)回放系統(tǒng)運(yùn)行界面圖

態(tài)勢(shì)回放預(yù)處理階段，對(duì)某大型電子信息系統(tǒng)在某年運(yùn)行過(guò)程中記錄的態(tài)勢(shì)數(shù)據(jù)文件集進(jìn)行處理，形成B+樹文件，B+樹文件中的航跡點(diǎn)個(gè)數(shù)超過(guò)1.2億(具體數(shù)字為126 259 363)。

態(tài)勢(shì)回放階段，繪點(diǎn)數(shù)據(jù)率約為20萬(wàn)點(diǎn)/s，即每一秒可完成約20萬(wàn)個(gè)航跡點(diǎn)及航跡點(diǎn)連線的繪制。假設(shè)一條航跡的長(zhǎng)度為1 000點(diǎn)，則一秒內(nèi)可完成約2 000條航跡的繪制。該結(jié)果表明本文提出的態(tài)勢(shì)回放系統(tǒng)具有較高的性能。

6 結(jié) 語(yǔ)

本文首先對(duì)與態(tài)勢(shì)回放相關(guān)的概念和術(shù)語(yǔ)進(jìn)行了形式化定義；然后描述了系統(tǒng)的組織架構(gòu)、工作流程及關(guān)鍵算法；最后提出了繪點(diǎn)數(shù)據(jù)率的概念用于衡量系統(tǒng)的運(yùn)行性能，實(shí)驗(yàn)結(jié)果顯示了系統(tǒng)進(jìn)行態(tài)勢(shì)回放的高效性。

在該系統(tǒng)的基礎(chǔ)上，擬繼續(xù)在以下幾個(gè)方面開展下一步的研究工作：

(1) 優(yōu)化內(nèi)部組件。對(duì)大數(shù)據(jù)索引技術(shù)進(jìn)行研究和開發(fā)，以提高數(shù)據(jù)存儲(chǔ)組件的空間利用率和查找效率。

(2) 拓展新的應(yīng)用方向。比如接入通信網(wǎng)絡(luò)，在線實(shí)時(shí)接收態(tài)勢(shì)數(shù)據(jù)進(jìn)行存儲(chǔ)和回放；可通過(guò)對(duì)數(shù)據(jù)存儲(chǔ)組件的并發(fā)訪問(wèn)控制技術(shù)的研發(fā)進(jìn)行實(shí)現(xiàn)。

(3) 作為算法研究和實(shí)驗(yàn)的平臺(tái)?？蓪⒑桔E融合、目標(biāo)識(shí)別等算法集成到回放系統(tǒng)中，對(duì)算法的執(zhí)行效果進(jìn)行檢驗(yàn)和評(píng)估，以促進(jìn)相關(guān)算法的研究和改善。