基于粒子群優(yōu)化的多數(shù)據(jù)鏈任務(wù)分配模型及方法

田 毅，閻 芳，劉 銳，趙長(zhǎng)嘯，

(1.中國民航大學(xué) 天津市民用航空器適航與維修重點(diǎn)實(shí)驗(yàn)室，天津 300300;2.中國民航大學(xué) 安全科學(xué)與工程學(xué)院，天津 300300)

1 引 言

軍用數(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)互通。

2 問題描述

2.1 任務(wù)模型與數(shù)據(jù)鏈模型

假設(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)度。

2.2 問題提出

在優(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é)問題。

3 粒子群算法求解任務(wù)分配問題

粒子群算法是由Kennedy和Eberhart提出的一種基于population的遺傳算法，該算法在對(duì)動(dòng)物集群活動(dòng)行為觀察基礎(chǔ)上，利用群體中的個(gè)體對(duì)信息的共享使整個(gè)群體的運(yùn)動(dòng)在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得最優(yōu)解。

3.1 粒子群公式

利用粒子群算法的第一步是定義粒子群及求解空間。就求解的任務(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)解。

3.2 適應(yīng)性函數(shù)

適應(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ù)值越小，則此解的性能越好。

3.3 更新粒子位置及速度

在搜尋最優(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。

3.4 算法步驟

粒子群算法步驟如下：

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)。

4 實(shí)驗(yà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ù)分配。

5 結(jié) 論

不同的數(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.