吝繼鋒,周德云,魯華

摘 要：針對數(shù)據(jù)鏈系統(tǒng)中多平臺多目標(biāo)情形下航跡關(guān)聯(lián)較為復(fù)雜的特點，提出一種基于加權(quán)最小二乘估計和蟻群算法的航跡關(guān)聯(lián)算法，并建立了多平臺多目標(biāo)航跡關(guān)聯(lián)處理模型。為了使蟻群算法能夠滿足數(shù)據(jù)鏈實時性的要求，對蟻群算法進行了改進。通過設(shè)置參數(shù)的取值使算法能夠適用于不同的戰(zhàn)場環(huán)境和量測誤差。對新提出的航跡關(guān)聯(lián)算法進行了Monte Carlo仿真，結(jié)果表明了算法的有效性和可行性。

關(guān)鍵詞：數(shù)據(jù)鏈； 加權(quán)最小二乘估計； 蟻群算法； 航跡關(guān)聯(lián)

中圖分類號：TN911-34文獻標(biāo)識碼：A

文章編號：1004-373X(2011)09-0006-04

Method of Track Association in Tactical Datalink

LIN Ji-feng1, ZHOU De-yun1, LU Hua1,2

(1. Northwestern Polytechnical University，Xian 710072，China； 2. Xian Institute of Applied Optics，Xian 710072，China)

Abstract： A track association method based on weighted least-squares estimation and ant colony algorithm is proposed to solve the complicated track association for multiple platforms and multiple targets in the tactical datalink, and the processing model is set up. Ant colony algorithm is improved to satisfy the real-time datalink. The method can set the parameter according to the battlefield circumstance and the measuring error of platforms. Monte Carlo simulation is performed with the constructed model. Results show that this method is feasible and effective.

Keywords： datalink; weighted least-squares estimation; ant colony algorithm; track association

0 引 言

在戰(zhàn)術(shù)數(shù)據(jù)鏈系統(tǒng)中，各個平臺都有自己的信息處理系統(tǒng)，并且各系統(tǒng)中都收集了大量的目標(biāo)航跡信息。那么，一個重要問題是如何判斷來自于不同系統(tǒng)的兩條航跡是否代表同一目標(biāo)，這就是航跡與航跡關(guān)聯(lián)(或互聯(lián))問題，簡稱航跡關(guān)聯(lián)或者相關(guān)問題。在各平臺的航跡間相距很遠(yuǎn)并且沒有干擾、雜波的情況，關(guān)聯(lián)問題比較簡單。但在多目標(biāo)、干擾、雜波、噪聲和交叉、分叉航跡較多的場合下，航跡關(guān)聯(lián)問題就變得比較復(fù)雜。再加上各平臺傳感器之間在距離和方位上的組合失配、傳感器位置誤差、目標(biāo)高度誤差、坐標(biāo)轉(zhuǎn)化誤差等因素的影響，使有效關(guān)聯(lián)變得更加困難。

在數(shù)據(jù)鏈系統(tǒng)中，充分利用各個平臺傳感器獲得的目標(biāo)監(jiān)視消息能大幅度提高整個作戰(zhàn)平臺的覆蓋范圍，并提高系統(tǒng)的定位精度。但由于各平臺的傳感器性能以及各個平臺所受雜波干擾的不同，對同一個目標(biāo)的測量結(jié)果可能不完全相同，因此，需要對目標(biāo)航跡進行相關(guān)處理，以便形成統(tǒng)一的戰(zhàn)場態(tài)勢圖。目前文獻中出現(xiàn)的航跡關(guān)聯(lián)算法主要有最近鄰域法(NN)、K-NN法和修正的K近鄰域法等［1］，這些都是基于統(tǒng)計的方法。數(shù)據(jù)鏈系統(tǒng)中各平臺包含有較大的導(dǎo)航、校準(zhǔn)及轉(zhuǎn)換和延遲誤差時，統(tǒng)計方法就顯得力不從心，需要尋求其他方法。所以，本文從數(shù)據(jù)鏈在信息化戰(zhàn)爭中應(yīng)用的角度出發(fā)，結(jié)合最小二乘和蟻群算法的特點，并將蟻群算法改進后，提出了在數(shù)據(jù)鏈中對多平臺多目標(biāo)航跡數(shù)據(jù)進行關(guān)聯(lián)的一種算法，且建立了關(guān)聯(lián)結(jié)構(gòu)模型。

1 多平臺多目標(biāo)航跡關(guān)聯(lián)模型

戰(zhàn)術(shù)數(shù)據(jù)鏈系統(tǒng)的示意圖如圖1所示，每個平臺都帶有航跡關(guān)聯(lián)模塊，每個平臺必須將本平臺傳感器獲得的本地航跡與數(shù)據(jù)鏈上其他平臺獲得的遠(yuǎn)程航跡進行相關(guān)處理，然后再將關(guān)聯(lián)處理后的航跡通過數(shù)據(jù)鏈發(fā)送給其他平臺［2-3］。航跡關(guān)聯(lián)模型如圖2所示。它類似于分布式結(jié)構(gòu)，主要包括航跡數(shù)據(jù)預(yù)處理和航跡相關(guān)。數(shù)據(jù)預(yù)處理是對數(shù)據(jù)鏈和本平臺的航跡進行時間對準(zhǔn)和坐標(biāo)轉(zhuǎn)換；根據(jù)數(shù)據(jù)鏈系統(tǒng)體系結(jié)構(gòu)特點航跡相關(guān)處理采用本文提出的基于加權(quán)最小二乘和蟻群算法的航跡關(guān)聯(lián)算法；關(guān)聯(lián)結(jié)束后通過數(shù)據(jù)鏈將航跡進行統(tǒng)一管理，以便形成統(tǒng)一的戰(zhàn)場態(tài)勢。

圖1 戰(zhàn)術(shù)數(shù)據(jù)鏈系統(tǒng)示意圖

圖2 航跡關(guān)聯(lián)處理模型

2 航跡關(guān)聯(lián)算法

美國和北約各國應(yīng)用最廣泛的Link-16數(shù)據(jù)鏈采用了時分多址即TDMA協(xié)議，是一種分配通信資源供使用者傳輸數(shù)據(jù)的入網(wǎng)協(xié)議。系統(tǒng)將時間軸劃分為時元，時元劃分為時間幀，時間幀劃分為時隙(Time Slot)。在每個時元中為每個成員分配一定量的時隙，用戶在自己的時隙內(nèi)發(fā)送信息，在其他用戶的時隙時處于監(jiān)聽狀態(tài)。在這用技術(shù)支持下，信息能夠被同步傳輸?shù)饺我庥行枨蟮钠脚_上［4-5］。

本文研究的數(shù)據(jù)鏈采用Link-16的時分多址協(xié)議，在數(shù)據(jù)鏈系統(tǒng)中有n個監(jiān)測平臺而且每個平臺在每個時元內(nèi)都有屬于自己的時隙。結(jié)合數(shù)據(jù)鏈的特點和戰(zhàn)場的需要，提出多平臺多目標(biāo)航跡關(guān)聯(lián)算法如下：

(1) 航跡建立。利用各航跡連續(xù)10次的點跡，采用加權(quán)最小二乘估計算法建立各航跡運動方程，并通過數(shù)據(jù)鏈發(fā)送到其他平臺。

(2) 發(fā)送、接收、記錄目標(biāo)航跡信息。在第i個網(wǎng)絡(luò)周期中，本地目標(biāo)航跡信息在ti時刻發(fā)送到數(shù)據(jù)鏈，在ti以后，每個平臺開始記錄從數(shù)據(jù)鏈接收到的其他平臺監(jiān)測到期開始之前的信息，這樣，每個平臺都記錄了數(shù)據(jù)鏈系統(tǒng)中其他平臺監(jiān)測到的目標(biāo)航跡信息。

(3) 坐標(biāo)轉(zhuǎn)換和時間對準(zhǔn)。通過航跡運動方程得到目標(biāo)在ti+1時刻的點跡，并將其轉(zhuǎn)換到本地坐標(biāo)系中。然后所有目標(biāo)在ti+1時刻的點跡被保存在C中。

(4) 蟻群搜索算法。通過設(shè)置閾值TV，利用蟻群算法就可以找到相同的目標(biāo)點跡集合，將其記錄在target［］中。顯然，TV將影響正確的關(guān)聯(lián)概率。

(5) 關(guān)聯(lián)判斷準(zhǔn)則。從第i到第i+m個網(wǎng)絡(luò)周期，如果target［］出現(xiàn)了x次，那么target［］中的目標(biāo)就認(rèn)為關(guān)聯(lián)成功。x/m也將影響正確的關(guān)聯(lián)概率。

3 加權(quán)最小二乘估計

平臺測量得到的目標(biāo)信息是采樣值，如果要得到采樣點之外的目標(biāo)信息，就必須建立目標(biāo)的運動方程。本文采用加權(quán)最小二乘法估計目標(biāo)運動方程。假設(shè)目標(biāo)運動方程是由n階多項式描述的，可以表示成如下矩陣形式：

X(t)=x(t)

y(t)

z(t)=a0a1…an

b0b1…bn

c0c1…cn1

t1

式中:(x(t),y(t),z(t))是目標(biāo)在t時刻的坐標(biāo)值。若能確定上述方程的系數(shù)矩陣，就可以解出目標(biāo)的運動方程?？紤]到精確性需要和高階多項式賦值引起的數(shù)值不穩(wěn)定性，取n=5，將10個以前的觀測值代入運動方程中。觀測方程假設(shè)如下：

式中:H為已知t的冪函數(shù);X為5個待定的未知數(shù);V是測量誤差，E(V)=0。

因此t時刻目標(biāo)的狀態(tài)為:

Z(t)=［1t…t4］

(8)

4 蟻群搜索算法

遺傳算法等仿生算法是近年研究的熱點。意大利學(xué)者Dorigo于1991年首次提出了蟻群算法。該方法已經(jīng)應(yīng)用到許多實際問題中，諸如車輛路徑問題、電力系統(tǒng)、航跡規(guī)劃、空戰(zhàn)決策等。這些研究成果得益于蟻群算法的內(nèi)在機制，螞蟻的內(nèi)在生理特征使得螞蟻能夠發(fā)現(xiàn)蟻穴到食物之間的最短路徑。這種內(nèi)在特征是通過螞蟻在經(jīng)過的路上留下的揮發(fā)性分泌物信息素來實現(xiàn)的。當(dāng)螞蟻選擇一條路徑后，后來的螞蟻會根據(jù)各條路徑上信息素的強弱來選擇所要經(jīng)過的路徑，這就是算法的選擇機制。信息素隨著時間的推移會逐漸揮發(fā)消失，但是對于螞蟻選擇的路徑而言，該路徑上留下的信息素濃度會越來越大；反之，信息素濃度大路徑會吸引更多的螞蟻。這種能夠收斂到最優(yōu)解的方式被稱為更新機制，一開始的路徑幾乎不可能是最優(yōu)的，甚至是最差的。當(dāng)大量的螞蟻通過信息素的更新后，最終是可以發(fā)現(xiàn)最佳路徑的，這就是協(xié)調(diào)機制。由此可見，蟻群算法的優(yōu)化機制對于多目標(biāo)航跡關(guān)聯(lián)問題而言業(yè)提供了一種很好的解決思路。其詳細(xì)原理可見文獻［6］。

4.1 蟻群算法的改進

數(shù)據(jù)鏈系統(tǒng)對實時性有著嚴(yán)格的要求，所以為了盡快地找到蟻群算法的最優(yōu)解，本文對蟻群算法進行了兩點改進：

(1) 在螞蟻進行下一個節(jié)點的選擇時加入閾值TV；

(2) 在螞蟻每走一步之后都進行信息素的更新。

每只螞蟻每個節(jié)點必須且只能經(jīng)過一次，因此給每只螞蟻構(gòu)造一個允許列表allowk，該列表中存放螞蟻還沒有走過的節(jié)點，tabuk列表存放螞蟻已經(jīng)走過的節(jié)點。在算法的初始時刻，將m只螞蟻放在起始節(jié)點，此時各路徑上的信息素相同，設(shè)τij(0)=c。每只螞蟻根據(jù)路徑上的信息素的量獨立地選擇下一個城市，螞蟻k由節(jié)點i轉(zhuǎn)向節(jié)點j的狀態(tài)轉(zhuǎn)移概率如下：

p琸ij(t)=ταij(t)ηβij(t)∑v∈allowkταiv(t)ηβiv(t),

j∈allowk

0,j黙llowk

(9)

為了多目標(biāo)航跡關(guān)聯(lián)的需要，取allowk=［j1,j2,…,js,…,jw］，其中js黷abuk，衚，1≤k≤i，d(k,js)≤TV。TV是影響航跡關(guān)聯(lián)正確概率的閾值，使得螞蟻不會經(jīng)過與節(jié)點距離遠(yuǎn)的節(jié)點，從而加快算法的收斂，快速找到最優(yōu)解。

當(dāng)螞蟻找到下一步的解時，各路徑上的信息素將會按照下式進行更新：

τij(t+1)=(1－ρ)τij(t)+Δτij,ρ∈(0,1)

(10)

Δτij=∑mk=1Δτ琸ij

(11)

Δτ琸ij=Q/Lik,if螞蟻k經(jīng)過路徑ij

0,else

(12)

式中：Δτ琸ij表示螞蟻k經(jīng)過(i,j)時信息素的增量；Δτij表示路徑(i,j)總的信息素增量；當(dāng)t=0時，τ琸ij(0)=c，Δτ琸ij=0;ρ表示信息素?fù)]發(fā)系數(shù)，ρ∈(0,1); Q為調(diào)節(jié)常數(shù);Lik表示第一個目標(biāo)到當(dāng)前目標(biāo)之間的距離。在每一步之后都更新信息素，是為了加快算法的收斂，快速找到最優(yōu)解。

4.2 算法流程

根據(jù)上述原理和規(guī)則，采用蟻群算法求解多目標(biāo)航跡關(guān)聯(lián)問題的具體步驟如下：

(1) 設(shè)置初始參數(shù)，C表示所有目標(biāo)點跡集合，Nc表示循環(huán)次數(shù)，將所有螞蟻置于起始節(jié)點，并將起始節(jié)點加入tabuk列表，計算出allowk列表。

(2) 螞蟻根據(jù)式(9)選擇下一節(jié)點，更新tabuk和allowk列表，并根據(jù)式(10)進行信息素更新。

(3) 判斷螞蟻allowk是否為空，若否執(zhí)行步驟(2)，否則在最后一個目標(biāo)處待命；等到所有的螞蟻allowk列表為空，執(zhí)行步驟(4)。

(4) 計算出所有螞蟻從第一個目標(biāo)走到最后一個目標(biāo)的最短路徑Lkmin=min Lk；之后各個路徑上的信息素將按照式(13),式(14)計算：

τ琻extij=(1－α)τ琧urrentij+αΔτij

(13)

Δτij=1/Lk,Lij∈Lkmin

0,else

(14)

式中:Lk表示螞蟻走過的最短路徑的長度。

(5) 判斷Lkmin是否是最優(yōu)解，即與之前的L對比。如果Lkmin

(6) 判斷循環(huán)次數(shù)Nc是否進行完畢，若沒有則將所有螞蟻重新置于開始目標(biāo)點。

(7) 在Nc次循環(huán)完成之后，輸出最優(yōu)解，將最相近的一組目標(biāo)從集合C中刪除；重復(fù)上述步驟繼續(xù)尋找下一組相近的目標(biāo)，直到集合C變成空集。

5 仿真結(jié)果與分析

為了驗證本文提出的航跡關(guān)聯(lián)算法，采用Monte Carlo方法在一定的情形下進行仿真。假設(shè)數(shù)據(jù)鏈系統(tǒng)由30個平臺構(gòu)成，100個目標(biāo)在數(shù)據(jù)鏈系統(tǒng)的監(jiān)測范圍之內(nèi)。根據(jù)最小二乘法得到每個目標(biāo)的真實運動軌跡。為了充分檢驗關(guān)聯(lián)算法的關(guān)聯(lián)效果，平臺每10 s監(jiān)測得到一次目標(biāo)的位置坐標(biāo)，假設(shè)隨機測量誤差為［0,50］m，考慮參數(shù)TV和x/m對正確關(guān)聯(lián)目標(biāo)航跡概率的影響，采樣航跡上50個點進行100次仿真。仿真結(jié)果如表1所示。

從蟻群搜索算法的原理可以看出，在一定的仿真條件下，目標(biāo)航跡和測量誤差確定，x/m和TV對航跡的正確關(guān)聯(lián)概率有很大的影響。如果TV太大，算法就可能把不同的目標(biāo)航跡關(guān)聯(lián)在一起。相反，如果TV太小，算法就可能把同一個目標(biāo)的航跡關(guān)聯(lián)不到一起。同樣，x/m也影響信息的可靠度，對航跡的正確關(guān)聯(lián)率也有一定影響作用。如表1的仿真結(jié)果所示，當(dāng)TV=0.2，x/m=0.6時，正確關(guān)聯(lián)概率達到最大值93.4%。實際上，在真實的戰(zhàn)場環(huán)境中，如果平臺對目標(biāo)的分辨能力相對較強，測量誤差較小，當(dāng)TV取值過大的情況下，算法就有可能分辨不出相近的目標(biāo)。相反，如果平臺對目標(biāo)的分辨能力較弱，測量誤差較大的話，關(guān)聯(lián)算法就有可能關(guān)聯(lián)不到目標(biāo)的正確航跡。因此，仿真結(jié)果與理論和實際的戰(zhàn)場環(huán)境是相符的。

圖3是改進后的蟻群算法在TV=0.2，x/m=06時的最優(yōu)路徑和平均路徑的長度隨循環(huán)次數(shù)增加的變化情況，從結(jié)果可以出，改進后的蟻群算法收斂速度較快，符合數(shù)據(jù)鏈系統(tǒng)的實時性要求。本文中的仿真條件是一般情況，可以根據(jù)戰(zhàn)場環(huán)境和平臺的測量誤差設(shè)置TV和x/m。當(dāng)數(shù)據(jù)鏈系統(tǒng)中有大量的平臺和目標(biāo)時，蟻群算法能夠表現(xiàn)出優(yōu)勢，說明本文提出的算法具有很好的適應(yīng)性。

6 結(jié) 論

對于數(shù)據(jù)鏈的應(yīng)用來說，多平臺多目標(biāo)的航跡關(guān)聯(lián)不僅是重點，也是難點。本文從戰(zhàn)場需要和數(shù)據(jù)鏈的實際應(yīng)用環(huán)境出發(fā)，以最小二乘和蟻群算法為基礎(chǔ)，提出了一種應(yīng)用于數(shù)據(jù)鏈系統(tǒng)的多平臺多目標(biāo)航跡關(guān)聯(lián)算法。通過建立關(guān)聯(lián)模型進行Monte Carlo仿真，仿真結(jié)

果表明了算法與理論和實際戰(zhàn)場環(huán)境是一致的，也表明了新算法的有效性與可行性，從而為數(shù)據(jù)鏈的研制打下了一定的基礎(chǔ)。

圖3 改進后的蟻群算法仿真

參考文獻

［1］何友，王國宏，陸大金，等.多傳感器信息融合及應(yīng)用［M］.北京：電子工業(yè)出版社，2007.

［2］王文政,周經(jīng)綸,羅鵬程,等.戰(zhàn)術(shù)數(shù)據(jù)鏈仿真研究綜述［J］.系統(tǒng)仿真學(xué)報,2008,20(14)：3623-3627.

［3］田斌鵬.戰(zhàn)術(shù)數(shù)據(jù)鏈實時性研究［D］.成都：西南交通大學(xué)，2007.

［4］任培,周經(jīng)綸,羅鵬程,等.美軍數(shù)據(jù)鏈發(fā)展概況與啟示［J］.裝備指揮技術(shù)學(xué)院學(xué)報,2008,19(1):43-47.

［5］孫義明,楊麗萍.信息化戰(zhàn)爭中的戰(zhàn)術(shù)數(shù)據(jù)鏈［M］.北京:北京郵電大學(xué)出版社，2005.

［6］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社,2005.

［7］秦衛(wèi)華,胡飛,秦超英.多平臺多目標(biāo)航跡關(guān)聯(lián)方法［J］.火力與指揮控制,2006,31(10):18-21.

［8］張珂馨,黃敬雄,康莉.一種基于蟻群算法的數(shù)據(jù)關(guān)聯(lián)方法［J］.系統(tǒng)仿真學(xué)報,2009,21(22):7127-7129.

［9］THOMAS S, HOLGER H H. MAX-MIN ant system [J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文