吝繼鋒,周德云,魯華

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 加權最小二乘估計

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

X(t)=x(t)

y(t)

z(t)=a0a1…an

b0b1…bn

c0c1…cn1

t1

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

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

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

Z(t)=［1t…t4］

(8)

4 蟻群搜索算法

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

4.1 蟻群算法的改進

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

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

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

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

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

j∈allowk

0,j黙llowk

(9)

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

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

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

(10)

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

(11)

Δτ琸ij=Q/Lik,if螞蟻k經過路徑ij

0,else

(12)

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

4.2 算法流程

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

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

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

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

(4) 計算出所有螞蟻從第一個目標走到最后一個目標的最短路徑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是否進行完畢，若沒有則將所有螞蟻重新置于開始目標點。

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

5 仿真結果與分析

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

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

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

6 結 論

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

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

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

參考文獻

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

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

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

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

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

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

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

［8］張珂馨,黃敬雄,康莉.一種基于蟻群算法的數(shù)據關聯(lián)方法［J］.系統(tǒng)仿真學報,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.

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