• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2014-02-01 08:49:35趙長(zhǎng)嘯
      電訊技術(shù) 2014年11期
      關(guān)鍵詞:互操作性數(shù)據(jù)鏈分配

      田 毅,閻 芳,劉 銳,趙長(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.

      猜你喜歡
      互操作性數(shù)據(jù)鏈分配
      多平臺(tái)通用數(shù)據(jù)鏈助力未來戰(zhàn)場(chǎng)
      殺傷鏈動(dòng)態(tài)重構(gòu)中的互操作性淺析
      高速公路工程項(xiàng)目實(shí)施中數(shù)據(jù)鏈應(yīng)用探析
      應(yīng)答器THR和TFFR分配及SIL等級(jí)探討
      基于深度學(xué)習(xí)的無人機(jī)數(shù)據(jù)鏈信噪比估計(jì)算法
      遺產(chǎn)的分配
      一種分配十分不均的財(cái)富
      績(jī)效考核分配的實(shí)踐與思考
      一種無人機(jī)數(shù)據(jù)鏈信道選擇和功率控制方法
      韓軍武器系統(tǒng)互操作性現(xiàn)狀及未來發(fā)展
      輕兵器(2017年17期)2017-09-19 12:35:43
      定襄县| 嘉善县| 喜德县| 昭平县| 永昌县| 辽宁省| 德州市| 峨边| 南川市| 简阳市| 黔江区| 焉耆| 宁海县| 嘉祥县| 伽师县| 格尔木市| 富源县| 平江县| 嵩明县| 永寿县| 德昌县| 乌拉特后旗| 临猗县| 黄大仙区| 惠东县| 普定县| 丰城市| 读书| 长寿区| 博湖县| 大安市| 白银市| 响水县| 玛沁县| 新蔡县| 友谊县| 榆林市| 徐州市| 乐业县| 安溪县| 横山县|