田 毅,閻 芳,劉 銳,趙長(zhǎng)嘯,
(1.中國民航大學(xué) 天津市民用航空器適航與維修重點(diǎn)實(shí)驗(yàn)室,天津 300300;2.中國民航大學(xué) 安全科學(xué)與工程學(xué)院,天津 300300)
軍用數(shù)據(jù)鏈?zhǔn)加?0世紀(jì)50年代,并首先裝備于地面防空系統(tǒng)、海軍艦艇,而后逐步擴(kuò)展到飛機(jī)。在戰(zhàn)術(shù)數(shù)據(jù)鏈的發(fā)展過程中,以美國為首的西方各國在不同的歷史時(shí)期,根據(jù)當(dāng)時(shí)的技術(shù)水平和不同的作戰(zhàn)需求開發(fā)了種類繁多的戰(zhàn)術(shù)數(shù)據(jù)鏈。數(shù)據(jù)鏈 已經(jīng)在近年來的歷次局部戰(zhàn)爭(zhēng)中大顯身手:在敘以貝卡谷地的空戰(zhàn)中,以色列預(yù)警機(jī)利用數(shù)據(jù)鏈指揮空戰(zhàn)以損失1架戰(zhàn)機(jī)的代價(jià)摧毀了敘利亞81架同等性能戰(zhàn)機(jī)和19個(gè)地對(duì)空導(dǎo)彈基地;海灣戰(zhàn)爭(zhēng)中,美國利用數(shù)據(jù)鏈?zhǔn)挂晾?0余枚飛毛腿導(dǎo)彈大部分被攔截。因此,數(shù)據(jù)鏈技術(shù)受到各國的重視。
然而,不同的數(shù)據(jù)鏈有不同的特性,想要實(shí)現(xiàn)不同數(shù)據(jù)鏈的互聯(lián)互通需要專門的設(shè)計(jì)[1]。已經(jīng)有學(xué)者著手改善不同的數(shù)據(jù)鏈之間的互操作性。Asenstorfer[2]首先討論了數(shù)據(jù)鏈的互操作性問題,通過改進(jìn)的數(shù)據(jù)調(diào)制解調(diào)器(Improved Data Modem)以提高Link-16、Link-22和CDL(Common Data Link )之間的互操作性;Hoekstra[3]指出了在不同的數(shù)據(jù)鏈之間實(shí)現(xiàn)互聯(lián)互通的重要性,研究了數(shù)據(jù)鏈各層互操作的可能性,提供了一個(gè)實(shí)現(xiàn)和保持互操作性的概述性方法。提高互操作性的關(guān)鍵因素是支持多種數(shù)據(jù)鏈的平臺(tái),它們負(fù)責(zé)轉(zhuǎn)換不同的數(shù)據(jù)格式并在多數(shù)據(jù)鏈間進(jìn)行任務(wù)分發(fā)。因此,如何為不同的數(shù)據(jù)鏈之間分配不同的任務(wù),且同時(shí)滿足任務(wù)的要求,并遵守?cái)?shù)據(jù)鏈的限制是本文的研究目標(biāo)。
關(guān)于任務(wù)分配問題,已有很多學(xué)者在許多領(lǐng)域進(jìn)行了研究,如多媒體流應(yīng)用[4]、社交網(wǎng)絡(luò)[5]、多智能體系統(tǒng)[6],一些集中[7]和分布式的[8]的方法被應(yīng)用到解決任務(wù)分配問題。任務(wù)分配一個(gè)流行的做法是使用談判或拍賣機(jī)制。一個(gè)談判問題是由多個(gè)用戶試圖來達(dá)成一個(gè)協(xié)議或交易,每個(gè)用戶都希望最大限度地發(fā)揮自己的效用,但他們也面臨著故障風(fēng)險(xiǎn)。遺傳算法作為進(jìn)化類算法的典型代表,近年來在無人機(jī)任務(wù)分配問題領(lǐng)域得到了廣泛應(yīng)用[9],但遺傳算法由于其本質(zhì)上的隨機(jī)性,求解過程中存在較多劣質(zhì)搜索過程,導(dǎo)致其在大規(guī)模組合優(yōu)化問題的求解中效率和精度不高。與遺傳算法采用群體解的競(jìng)爭(zhēng)機(jī)制來迭代產(chǎn)生最優(yōu)解不同,粒子群算法采用群體解的合作機(jī)制來迭代產(chǎn)生最優(yōu)解,因此大大提高了收斂速度。此外,粒子群算法概念簡(jiǎn)單、容易實(shí)現(xiàn),需要調(diào)節(jié)的參數(shù)偏少。本文提出了一種基于粒子群優(yōu)化(PSO)[10]的算法來解決多數(shù)據(jù)鏈間的任務(wù)分配問題,最后給出了算例,結(jié)果表明本算法可以在滿足系統(tǒng)限制的條件下完成任務(wù)分配,有效地實(shí)現(xiàn)多數(shù)據(jù)鏈間的互聯(lián)互通。
假設(shè)一個(gè)平臺(tái)支持N種不同的數(shù)據(jù)鏈L= {l1,l2,…,lN},我們使用一個(gè)數(shù)組來描述數(shù)據(jù)鏈li(Fi,Bi,Si,Pi),其中Fi為通信頻段,Bi為頻譜寬度,Si是數(shù)據(jù)鏈的傳輸速率,Pi是數(shù)據(jù)鏈傳輸信息的消息格式。消息在不同格式之間的轉(zhuǎn)換代價(jià)用如下矩陣記錄:
為簡(jiǎn)化描述,將節(jié)點(diǎn)要處理的消息定義為其要完成的一個(gè)任務(wù)。假設(shè)節(jié)點(diǎn)有M個(gè)任務(wù)要處理,任務(wù)集合={1,2,…,M}。模型化任務(wù)為[t,D,p,l],t是任意連續(xù)兩個(gè)任務(wù)間的最小時(shí)間間隔,D是任務(wù)允許的最大延遲,p為當(dāng)前的消息格式,l為任務(wù)的負(fù)載長(zhǎng)度。
在優(yōu)化后的綜合集成數(shù)據(jù)鏈中,被分配到每條數(shù)據(jù)鏈的最多任務(wù)數(shù)應(yīng)該被限制以滿足各條數(shù)據(jù)鏈間的負(fù)載平衡。另一方面,最好將任務(wù)分配到相同的數(shù)據(jù)鏈中,這樣會(huì)減少在不同數(shù)據(jù)鏈間的消息格式的轉(zhuǎn)換代價(jià)。因此,在不同數(shù)據(jù)鏈間的任務(wù)分配要在兩個(gè)沖突目標(biāo)間進(jìn)行權(quán)衡。在綜合數(shù)據(jù)鏈間分配任務(wù)即是找到一個(gè)帶有約束的分配問題:
A:?!鶯
(1)
(2)
目標(biāo)函數(shù)(2)第一部分代表分配到單條數(shù)據(jù)鏈任務(wù)的最大數(shù)目,第二部分代表任務(wù)在不同數(shù)據(jù)鏈間消息格式轉(zhuǎn)換的代價(jià)函數(shù),目標(biāo)函數(shù)即最小化總代價(jià)。為平衡目標(biāo)函數(shù)中的兩個(gè)目標(biāo),α、β為各部分的權(quán)重值。任務(wù)分配中,還需滿足其他的一些限制。
(1)帶寬限制
分配到一條數(shù)據(jù)鏈的所有任務(wù)所需的帶寬總和不能超過本數(shù)據(jù)鏈的最大傳輸帶寬,Size為數(shù)據(jù)包大?。?/p>
(3)
(2)唯一性
不考慮容錯(cuò)即冗余性,所有的任務(wù)同一時(shí)刻只能被分配到一條數(shù)據(jù)鏈,且所有的任務(wù)都需要被分配:
(4)
(3)實(shí)時(shí)性要求
網(wǎng)絡(luò)中的任務(wù)有實(shí)時(shí)性要求,即所有的任務(wù)都需在規(guī)定時(shí)限內(nèi)完成,這進(jìn)一步要求分配到一條數(shù)據(jù)鏈的任務(wù)數(shù)要被限制,以滿足任務(wù)完成的實(shí)時(shí)性要求:
(5)
其中,hp(i)為分配到數(shù)據(jù)鏈lj上的所有優(yōu)先級(jí)高于τi的任務(wù)集合,Di是任務(wù)τi的任務(wù)時(shí)限。
綜上,任務(wù)分配問題可以被描述為
(6)
因此,我們將多數(shù)據(jù)鏈間的任務(wù)分配問題轉(zhuǎn)化為了求解此優(yōu)化方程的數(shù)學(xué)問題。
粒子群算法是由Kennedy和Eberhart提出的一種基于population的遺傳算法,該算法在對(duì)動(dòng)物集群活動(dòng)行為觀察基礎(chǔ)上,利用群體中的個(gè)體對(duì)信息的共享使整個(gè)群體的運(yùn)動(dòng)在問題求解空間中產(chǎn)生從無序到有序的演化過程,從而獲得最優(yōu)解。
利用粒子群算法的第一步是定義粒子群及求解空間。就求解的任務(wù)分配問題,將粒子的求解空間定義為M緯空間,X={xi,x2,…,xM},其中xi為數(shù)據(jù)鏈的索引值,xi∈[1,N]。粒子的位置即任務(wù)的分配結(jié)果A:→L。粒子的速度向量為V={vi,v2,…,vN},vi取值范圍為在 (-N+1,N-1)的整數(shù),代表距當(dāng)前位置的最遠(yuǎn)距離。算法會(huì)生成ρ個(gè)粒子,隨機(jī)的初始化各粒子的初始位置和初始速度,算法通過迭代在解空間中尋找最優(yōu)解。
適應(yīng)性函數(shù)評(píng)價(jià)算法中粒子位置的性能,即本文中任務(wù)分配結(jié)果的性能。目標(biāo)函數(shù)Q(A) 是適應(yīng)性函數(shù)中一項(xiàng),其他限制條件作為懲罰函數(shù)構(gòu)成適應(yīng)函數(shù)的其他部分。懲罰函數(shù)定義為
(7)
則適應(yīng)性函數(shù)定義為
Fit(A)=Q(A)+γPE(A)
(8)
其中,γ為懲罰函數(shù)的權(quán)重值。適應(yīng)函數(shù)值越小,則此解的性能越好。
在搜尋最優(yōu)解的過程中,粒子記錄兩個(gè)最優(yōu)值,Pbest代表粒子在搜尋過程中記錄的最優(yōu)值,Gbest是整個(gè)粒子群所經(jīng)歷的最優(yōu)解。粒子位置和速度的更新公式為
Vt+1=ωVt+c1r1(Pbest-Xt)+c2r2(Gbest-Xt)
Xt+1=Xt+Vt
(9)
式中,ω是粒子保持原來速度的系數(shù),稱為慣性權(quán)重;c1是粒子跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù),它表示粒子自身的認(rèn)識(shí),稱為“認(rèn)知(Cognition)”部分;c2是粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù),它表示粒子對(duì)整個(gè)群體知識(shí)的認(rèn)識(shí),稱為“社會(huì)(Social)”部分[11];r1、r2是 [0,1] 區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)。“認(rèn)知”部分可以由 Thorndike 的效應(yīng)法則(Law of Effect) 所解釋,即一個(gè)得到加強(qiáng)的隨機(jī)行為在將來更有可能出現(xiàn)。這里的行為即“認(rèn)知”,并假設(shè)獲得正確的知識(shí)是得到加強(qiáng)的,這樣的一個(gè)模型假定微粒被激勵(lì)著去減小誤差?!吧鐣?huì)”部分可以由 Bandura 的替代強(qiáng)化(Vicarious Reinforcement) 所解釋。根據(jù)該理論的預(yù)期,當(dāng)觀察者觀察到一個(gè)模型在加強(qiáng)某一行為時(shí),將增加它實(shí)行該行為的幾率,即微粒本身的認(rèn)知將被其他微粒所模仿。在文獻(xiàn)[12] 文中的推薦值為ω=0.9,c1=c2=2。
粒子群算法步驟如下:
Step 2:設(shè)置粒子數(shù)及迭代次數(shù);隨機(jī)初始化各粒子初始位置及速度;
Step 3:計(jì)算各粒子的適應(yīng)性函數(shù);記錄各粒子的最佳狀態(tài)Pbest;記錄整個(gè)粒子群的最佳狀態(tài)Gbest,依據(jù)公式(9)更新各粒子的速度和位置;
Step 4:檢查該狀態(tài)是否滿足式(3)~(5)的限制要求;不能滿足,則重復(fù)Step 3,直至達(dá)到所設(shè)置的迭代次數(shù)。
首先,輸入任務(wù)集和數(shù)據(jù)鏈的特性;其次,輸入粒子算法所需的初始化參數(shù),如粒子的初始位置X和初始速度V;第三,該算法將計(jì)算出每個(gè)粒子的適應(yīng)值,并記錄最佳解決方案的粒子位置;最后判斷所得方案是否滿足分配約束。在此算法中,不可行的解決方案在迭代過程中沒有被丟棄,它們被用來作為適應(yīng)函數(shù)中的懲罰函數(shù)。因此,有必要仔細(xì)檢查是否滿足約束條件,如果解決方案不滿足所有的約束,將開始一個(gè)新的循環(huán)。
使用仿真方法評(píng)估任務(wù)分配算法。考慮一個(gè)網(wǎng)絡(luò),其中有3種類型的數(shù)據(jù)鏈,數(shù)據(jù)鏈參數(shù)如表1所示。在表2中給出了預(yù)先定義的任務(wù)集合。我們使用消息類型代表該消息的目的平臺(tái)。參數(shù)設(shè)置為α=5,β=0.1,γ=300。在粒子群算法中,粒子數(shù)和迭代次數(shù)分別為20和150。
表1 數(shù)據(jù)鏈信息Table 1 The parameters of TDLs
表2 任務(wù)信息Table 2 The task set
不同數(shù)據(jù)鏈消息模式之間的格式轉(zhuǎn)換的代價(jià)被定義如下:定義為轉(zhuǎn)換1 000 b數(shù)據(jù)所耗的時(shí)間代價(jià)。例如,將花費(fèi)0.95 ms將1 000 b的數(shù)據(jù)從模式1轉(zhuǎn)換到模式2:
迭代結(jié)束時(shí),可以得到任務(wù)分配的結(jié)果,如表3所示。
表3 任務(wù)分配結(jié)果Table 3 Task allocation results
網(wǎng)絡(luò)中總負(fù)載為
和數(shù)據(jù)鏈的總?cè)萘肯啾?,這是一個(gè)中等的流量負(fù)荷。因此,如果經(jīng)過精心設(shè)計(jì),所有的任務(wù)能夠滿足其時(shí)間期限。實(shí)驗(yàn)結(jié)果表明,本算法可以在滿足所有的約束條件下實(shí)現(xiàn)多數(shù)據(jù)鏈的任務(wù)分配。
不同的數(shù)據(jù)鏈有不同的設(shè)計(jì),以滿足多樣化的戰(zhàn)術(shù)需求,多數(shù)據(jù)鏈間的互操作性是發(fā)揮協(xié)同作戰(zhàn)能力的關(guān)鍵。本文模型化數(shù)據(jù)鏈和任務(wù),給出了多數(shù)據(jù)鏈間任務(wù)分配問題的數(shù)學(xué)模型,并基于粒子群算法對(duì)該問題進(jìn)行了求解。通過模擬計(jì)算表明,該算法可滿足在不違反任何任務(wù)約束條件下實(shí)現(xiàn)多數(shù)據(jù)鏈間的任務(wù)分配,對(duì)提高多單位戰(zhàn)斗協(xié)同效能具有理論指導(dǎo)意義。
下一步的工作包括兩個(gè)方面:一是尋找求解該問題的最優(yōu)算法,并比較各算法在執(zhí)行效率、有效性等方面的優(yōu)劣;二是求解在給定多數(shù)據(jù)鏈性能的條件下,可分配任務(wù)數(shù)量的上界,在實(shí)現(xiàn)多數(shù)據(jù)鏈互聯(lián)互通的同時(shí)提高資源利用率。
[1] 焦廣倫,孫治水.一種數(shù)據(jù)鏈集成架構(gòu)[J].電訊技術(shù),2013,53(11):1401-1405.
JIAO Guang-lun,SUN Zhi-shui.An Architecture of Data Link Integration [J].Telecommunication Engineering,2013,53(11):1401-1405.(in Chinese)
[2] Tactical Data Link Systems and the Australian Defence Force(ADF)-Technology Developments and Interoperability Issues[R].DSTO-TR-1470,2004.
[3] NATO C3 Agency.Tactical Data Links and Interoperability,The Glue between Systems[R].[S.l.]:NATO C3 Agency,2008.
[4] Paterna F,Acquaviva A,Caprara A,et al.Variability-aware task allocation for energy-efficient quality of service provisioning in embedded streaming multimedia applications[J].IEEE Transactions on Computers,2012,61(7):939-953.
[5] de Weerdt M,Zhang Y,Klos T B.Distributed task allocation in social networks[C]//Proceedings of the 6th International Conference on Autonomous Agents and Multiagent Systems.Honolulu,Hawaii,USA:ACM,2007:17-24.
[6] Ferreira P,dos Santos F,Bazzan A,et al. Robocup rescue as multiagent task allocation among teams:Experiments with task interdependencies[J].Autonomous Agents and Multi-Agent Systems,2010(20):421-443.
[7] Scerri P,Farinelli A,Okamoto S,et al.Allocating tasks in extreme teams[C]//Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems.Utrecht,Holland:ACM,2005:727-734,
[8] Zheng X,Koenig S.Reaction functions for task allocation to cooperative agents [C]//Proceedings of the 7th International Joint conference on Autonomous Agents and Multiagent Systems.Estoril,Portugal:ACM,2008:559-566.
[9] Shima T,asmussen S J,Sparks A G,et al.Multiple task assignmentsfor cooperating uninhabited aerial vehicles using genetic algorithms[J].Computers & Operations Research,2006,33(11):3252-3269.
[10] Kennedy J,Eberhart R.Particle swarm optimization[C]//Proceedings of 1995 IEEE International Conference on Neural Networks.Perth,Australia:IEEE,1995:1942-1948.
[11] Poli R,Kennedy J,Blackwell T.Particle Swarm Optimization:An Overview[J].Swarm Intelligence,2007(1):33-57.
[12] Shi Y,Eberhart R C.Parameter Selection in Particle Swarm Optimization[C]//Proceedings of the 7th International Conference on Evolutionary Programming VII.San Diego,California,USA:Springer-Verlag,1998:1-5.