分布式武器目標(biāo)分配中的實(shí)時(shí)截止期分配

孫亞東 邢昌風(fēng) 吳 玲 盧發(fā)興

(海軍工程大學(xué)電子工程學(xué)院，武漢430033)

多平臺(tái)協(xié)同作戰(zhàn)的背景下，目標(biāo)在其航路上可能需要由分布于不同平臺(tái)的多個(gè)武器進(jìn)行協(xié)同攻擊.由于武器射界的影響，完成對(duì)目標(biāo)的協(xié)同攔截要在一定的窗口時(shí)間內(nèi)完成.為了保證整體攔截任務(wù)的實(shí)時(shí)性，可用的對(duì)目標(biāo)攔截時(shí)間必須合理地分配給實(shí)施攔截的各個(gè)武器系統(tǒng).本文將實(shí)時(shí)系統(tǒng)中的截止期分配技術(shù)引入多武器協(xié)同攔截目標(biāo)問題中，通過分析任務(wù)的特點(diǎn)和時(shí)間屬性，建立任務(wù)調(diào)度模型和截止期分配方法，確定各個(gè)攔截子任務(wù)的最終完成時(shí)間.建立了截止期分配方法的評(píng)價(jià)指標(biāo)，通過仿真試驗(yàn)比較分析了不同分配方法的有效性.本文的方法可為分布式實(shí)時(shí)系統(tǒng)中的任務(wù)協(xié)作實(shí)時(shí)性研究提供參考.

1 截止期分配問題

在引入截止期分配概念之前，首先介紹各類實(shí)時(shí)任務(wù)的概念和相關(guān)模型.

1.1 基本任務(wù)模型

實(shí)時(shí)系統(tǒng)中的任務(wù)分為兩種:本地任務(wù)和全局任務(wù).本地任務(wù)是指在一個(gè)節(jié)點(diǎn)且僅在一個(gè)節(jié)點(diǎn)上執(zhí)行的任務(wù)，全局任務(wù)是指需要在多個(gè)節(jié)點(diǎn)上完成的任務(wù).全局任務(wù)又是由一系列在不同節(jié)點(diǎn)上執(zhí)行的子任務(wù)組成的，根據(jù)全局任務(wù)和子任務(wù)的關(guān)系，一般的全局任務(wù)在結(jié)構(gòu)上可以由“串行子任務(wù)”和“并行子任務(wù)”組成.用符號(hào)T=［T1，T2，…，Tn］表示全局任務(wù)T由n個(gè)串行執(zhí)行的子任務(wù) T1，T2，…，Tn組成，子任務(wù) Ti(i＞1)不能在Ti－1之前執(zhí)行.用 T=［T1‖T2‖…‖Tn］表示全局任務(wù)T包含n個(gè)并行執(zhí)行的子任務(wù)，只有在所有的子任務(wù)都結(jié)束了，全局任務(wù)T才算結(jié)束［1］.圖1所示是一個(gè)具有串并行結(jié)構(gòu)的全局任務(wù)示意圖.

圖1 全局任務(wù)的串/并行結(jié)構(gòu)示意圖

無(wú)論是全局任務(wù)還是子任務(wù)，任務(wù)T都可用一些時(shí)間屬性［1］來描述，如:①到達(dá)時(shí)間ar(T);②截止時(shí)間dl(T);③任務(wù)預(yù)計(jì)執(zhí)行時(shí)間pex(T);④任務(wù)實(shí)際執(zhí)行時(shí)間ex(T)，ex(T)的值一般是未知的，但可利用它的估計(jì)值pex(T)近似;⑤松弛時(shí)間sl(T)，即任務(wù)的截止時(shí)間與任務(wù)的結(jié)束時(shí)間或預(yù)期結(jié)束時(shí)間之間的差值.這些屬性間的關(guān)系為:dl(T)=ar(T)+ex(T)+sl(T).另外任務(wù)T的時(shí)間約束的強(qiáng)弱可以用任務(wù)的松弛時(shí)間與執(zhí)行時(shí)間之比來描述，將這一比值定義為任務(wù) T的靈活度f(wàn)l(T)，即fl(T)=sl(T)/ex(T).顯然，靈活度越大，時(shí)間約束越弱.

1.2 截止期及其分配策略

任何一個(gè)實(shí)時(shí)任務(wù)都將受到一定時(shí)間期限的約束，這個(gè)時(shí)間期限稱為任務(wù)的截止期.在分布式實(shí)時(shí)條件下，一個(gè)全局任務(wù)要在給定的開始和結(jié)束時(shí)間內(nèi)進(jìn)行，這個(gè)給定的時(shí)間段稱為端到端截止期(EED，End-to-End Deadline).當(dāng)全局任務(wù)被劃分為多個(gè)子任務(wù)在不同節(jié)點(diǎn)上執(zhí)行時(shí)，全局任務(wù)的截止期要合理地轉(zhuǎn)化為各子任務(wù)的截止期，即子任務(wù)截止期分配(SDA，Subtask Deadline Assignment)，簡(jiǎn)稱截止期分配.截止期分配問題自提出以來不斷得到深入的研究，多種不同的截止期分配策略和方法先后被提出［1－3］，并廣泛應(yīng)用在復(fù)雜分布式實(shí)時(shí)系統(tǒng)如實(shí)時(shí)交易［4］和實(shí)時(shí)數(shù)據(jù)庫(kù)［5］等具體領(lǐng)域.

根據(jù)系統(tǒng)的串-并型結(jié)構(gòu)，可以提出若干對(duì)子任務(wù)進(jìn)行截止期分配的規(guī)則.對(duì)串行子任務(wù)的截止期分配策略如［1］:①最大截止期法(UD，Ultimate Deadline)，即直接把全局任務(wù)的截止期設(shè)置為子任務(wù)的截止期;②有效截止期法(ED，Effective Deadline)，如果子任務(wù)執(zhí)行時(shí)間的估計(jì)值有效，子任務(wù)Ti的截止期就等于全局任務(wù)T的截止期減去Ti之后所有子任務(wù)的總預(yù)計(jì)執(zhí)行時(shí)間;③等松弛時(shí)間法(EQS，Equal Slack)，即在剩下的子任務(wù)中等分剩余松弛時(shí)間;④等靈活度法(EQF，Equal Flexibility)，指對(duì)各子任務(wù)按照相同靈活度的原則分配截止期;⑤比例負(fù)載法(PLO，Proportional Load)，即根據(jù)節(jié)點(diǎn)負(fù)載大小來分配剩余松弛時(shí)間，負(fù)載越大，分配松弛時(shí)間也越多.

并行子任務(wù)的截止期分配相對(duì)較簡(jiǎn)單，除最大截止期法外，還可采用啟發(fā)式算法，如DIV-x法［1］，其中x是可調(diào)整的參數(shù).DIV-x策略是把全局任務(wù)的總時(shí)間簡(jiǎn)單地除以子任務(wù)數(shù)的x倍.

當(dāng)一個(gè)全局任務(wù)同時(shí)具有串行和并行子任務(wù)，則應(yīng)組合使用兩種截止期分配策略.

2 協(xié)同攔截中的截止期分配方法

2.1 問題描述

本文以艦艇編隊(duì)協(xié)同防空為例建立模型.從任務(wù)屬性上看，如果一批目標(biāo)僅由單個(gè)武器實(shí)施攔截，此任務(wù)為本地任務(wù);如果一批目標(biāo)需要由兩座以上的武器交替攔截，此任務(wù)為全局任務(wù)，每座武器對(duì)目標(biāo)的攔截都是它的一個(gè)子任務(wù).

為了分析這一過程，假定一批來襲目標(biāo)由M1和M2兩個(gè)目標(biāo)組成，根據(jù)火力分配方案，有三座不同艦艇平臺(tái)上的武器W1，W2和W3協(xié)同攔截為例，如圖2所示.

三座武器的發(fā)射區(qū)分別設(shè)為D1，D2和D3，M1到達(dá)D1，D2的遠(yuǎn)界和近界的時(shí)刻按時(shí)間順序依次為 t1，t2，t3和 t4，M2到達(dá) D2，D3的遠(yuǎn)界和近界的時(shí)刻按時(shí)間順序依次為 t5，t6，t7和 t8.武器對(duì)M1和M2的攔截可看作是兩個(gè)全局任務(wù)，記為T1和T2.其開始時(shí)間分別為兩個(gè)目標(biāo)到達(dá)武器發(fā)射遠(yuǎn)界的時(shí)間t1和t5，任務(wù)截止期分別為兩個(gè)目標(biāo)到達(dá)武器發(fā)射近界的時(shí)間t4和t8.

假定攔截采取“射-看-射”的原則，即只有在先發(fā)射的武器結(jié)束射擊并通過觀測(cè)確定目標(biāo)未毀傷后，第二座武器才射擊，因此兩個(gè)全局任務(wù)都是由串行的子任務(wù)組成.以全局任務(wù)T1為例，它由W1和W2分別對(duì)目標(biāo)攔截兩個(gè)子任務(wù)串聯(lián)組成，分別記為ST1和ST2.每個(gè)子任務(wù)的執(zhí)行都包括2個(gè)階段:解算射擊諸元和實(shí)施發(fā)射;而ST2的執(zhí)行是在ST1發(fā)射之后開始的，包括3個(gè)階段:射后觀效、解算射擊諸元和實(shí)施發(fā)射［6］.顯然，子任務(wù)的實(shí)際執(zhí)行時(shí)間事先不知道，因此在截止期的分配前要對(duì)子任務(wù)的執(zhí)行時(shí)間進(jìn)行估計(jì)，即得到預(yù)期執(zhí)行時(shí)間pex(ST)，預(yù)期執(zhí)行時(shí)間要盡可能地接近于實(shí)際執(zhí)行時(shí)間ex(ST).

2.2 任務(wù)調(diào)度模型

本文建立的分布式實(shí)時(shí)任務(wù)調(diào)度模型是由代表不同處理模塊的若干節(jié)點(diǎn)組成，這些處理模塊主要有武器處理節(jié)點(diǎn)和主調(diào)度程序.圖3所示為任務(wù)調(diào)度模型結(jié)構(gòu)圖.

圖3 任務(wù)調(diào)度模型結(jié)構(gòu)圖

主調(diào)度程序的主要工作是根據(jù)全局任務(wù)和其子任務(wù)的相關(guān)信息，按照既定的分配策略對(duì)全局任務(wù)的端到端截止期進(jìn)行分配，相當(dāng)于給每個(gè)子任務(wù)貼上一個(gè)截止期“標(biāo)簽”，并把截止期信息發(fā)送到相應(yīng)的武器處理節(jié)點(diǎn)上.

武器處理節(jié)點(diǎn)是對(duì)應(yīng)于每個(gè)武器設(shè)置的，每個(gè)處理節(jié)點(diǎn)上都有一個(gè)本地調(diào)度程序，其主要工作是對(duì)節(jié)點(diǎn)上的本地任務(wù)和分配到此節(jié)點(diǎn)上的子任務(wù)按照一定的原則進(jìn)行實(shí)時(shí)調(diào)度.本文采用最早截止期優(yōu)先(EDF，Earliest-Deadline-First)的原則，即所有在此節(jié)點(diǎn)上處理的任務(wù)中，截止期最早的任務(wù)優(yōu)先得到處理.另外對(duì)于已經(jīng)延遲的子任務(wù)，為了不影響后續(xù)子任務(wù)的執(zhí)行，減少不必要的浪費(fèi)，本地調(diào)度程序?qū)?duì)其做放棄處理.

2.3 截止期分配方法

本文主要解決串行子任務(wù)的靜態(tài)截止期分配問題.分布式武器對(duì)目標(biāo)協(xié)同攔截中的截止期分配問題與以往文獻(xiàn)中研究的問題主要有以下兩點(diǎn)不同:①全局任務(wù)的結(jié)構(gòu)不同，不同全局任務(wù)的子任務(wù)數(shù)量和執(zhí)行的節(jié)點(diǎn)都不同;②子任務(wù)的截止期不僅僅取決于截止期分配策略，而且受武器射界的影響.當(dāng)目標(biāo)突破武器的發(fā)射近界時(shí)，此武器就不能再進(jìn)行射擊了，若繼續(xù)進(jìn)行跟蹤濾波和射擊諸元的解算就無(wú)任何意義了.

設(shè)一串行全局任務(wù):T=［ST1，ST1，…，STn］，任務(wù)的截止期為dl(T)，且全局任務(wù)的執(zhí)行時(shí)間不會(huì)超過其端到端截止期.

1)射擊近界法(MFR，Minimum Fire Range).

這是最直觀和簡(jiǎn)便的分配策略，適用于對(duì)任務(wù)的執(zhí)行時(shí)間一無(wú)所知的情況，與最大截止期法相似，即直接以目標(biāo)到達(dá)武器射擊近界的時(shí)間作為當(dāng)前子任務(wù)的截止期，如下式所示:

其中，t(i)mr表示第i個(gè)任務(wù)中目標(biāo)到達(dá)武器射擊近界的時(shí)間.

若以圖2所示的武器W1和W2攔截目標(biāo)M1為例，令 ar(ST1)=t1，ar(ST2)=dl(ST1)，dl(ST2)=t4，假定 pex(ST1)= Δt1，pex(ST2)= Δt2，則用射擊近界法分配的子任務(wù)截止期為

2)等靈活度法.

按照使每個(gè)子任務(wù)擁有相同靈活度的原則，對(duì)全局任務(wù)的剩余松弛時(shí)間進(jìn)行分配，子任務(wù)截止期公式為［1］

在本例中子任務(wù)的截止期為

3)比例負(fù)載法.

根據(jù)處理節(jié)點(diǎn)上的子任務(wù)數(shù)量進(jìn)行分配，子任務(wù)多的節(jié)點(diǎn)上需要排隊(duì)的時(shí)間就越長(zhǎng)，分配的松弛時(shí)間也就越多，截止期計(jì)算公式為

其中，load(STi)表示處理子任務(wù)i的節(jié)點(diǎn)上的負(fù)載數(shù)量.

本例中的子任務(wù)截止期為

3 仿真分析

3.1 仿真模型

設(shè)共有n座防御武器，即n個(gè)處理節(jié)點(diǎn)，用集合{w1，w2，…，wn}表示.目標(biāo)的數(shù)量為 m，用 Mk={wi，…，wj}(k=1，2，…，m)表示武器 wi，…，wj分配給了目標(biāo)Mk.規(guī)定一個(gè)全局任務(wù)最多只能有STmax個(gè)子任務(wù)，即Mk的集合最多有STmax個(gè)元素;同時(shí)定義一個(gè)處理節(jié)點(diǎn)的容量為v，即一個(gè)節(jié)點(diǎn)最多處理v個(gè)子任務(wù)，意味著一個(gè)武器最多對(duì)v個(gè)目標(biāo)實(shí)施攔截.

目標(biāo)依據(jù)參數(shù)為μ的泊松流產(chǎn)生，每次試驗(yàn)總共至少要產(chǎn)生1 000個(gè)任務(wù).本地任務(wù)在總?cè)蝿?wù)中所占的比例稱為本地負(fù)載，用local_load表示.在本試驗(yàn)的基本設(shè)置中，本地負(fù)載為20%，全局任務(wù)中子任務(wù)數(shù)量為2和3的各占40%.

火力分配完畢后，任務(wù)都已產(chǎn)生，這時(shí)要定義任務(wù)的時(shí)間屬性.設(shè)本地任務(wù)和子任務(wù)的執(zhí)行時(shí)間服從［λ，2λ］個(gè)時(shí)間單位內(nèi)的均勻分布;全局任務(wù)的到達(dá)時(shí)間一樣;端到端截止期隨子任務(wù)個(gè)數(shù)不同而變化，具體為:包含k個(gè)子任務(wù)的全局任務(wù)端到端截止期 EED服從［2kλ，2kλ+λ］個(gè)時(shí)間單位內(nèi)的均勻分布;目標(biāo)到達(dá)第i個(gè)武器射擊近界的時(shí)間服從均值為EED×i/k的正態(tài)分布.同時(shí)假定對(duì)子任務(wù)執(zhí)行時(shí)間的預(yù)測(cè)是絕對(duì)準(zhǔn)確的，即pex(ST)=ex(ST).本仿真試驗(yàn)中的基本設(shè)置如表1所示.

表1 基本設(shè)置

3.2 仿真結(jié)果

本仿真試驗(yàn)利用任務(wù)的錯(cuò)失率作為主要評(píng)判指標(biāo)，其中又把錯(cuò)失率分為3種分別進(jìn)行分析:

1)本地任務(wù)錯(cuò)失率(LMD，Local Missed Deadline)，表示在所有的本地任務(wù)中，超過截止期的本地任務(wù)所占比例.

2)全局任務(wù)錯(cuò)失率(GMD，Global Missed Deadline)，表示在所有的全局任務(wù)中，錯(cuò)失的全局任務(wù)所占比例.錯(cuò)失的全局任務(wù)是指它的所有子任務(wù)都超出截止期，此時(shí)攔截任務(wù)失敗.

3)總?cè)蝿?wù)錯(cuò)失率(OMD，Overall Missed Deadline)，表示在所有產(chǎn)生的本地任務(wù)和全局任務(wù)中，錯(cuò)失的任務(wù)所占比例.經(jīng)過試驗(yàn)，各截止期分配方法在不同目標(biāo)數(shù)量下的任務(wù)錯(cuò)失率如表2所示.

表2 三種截止期分配方法在不同目標(biāo)數(shù)量下的任務(wù)錯(cuò)失率

為便于對(duì)各種方法進(jìn)行比較，將子任務(wù)錯(cuò)失率和全局任務(wù)錯(cuò)失率的直方圖畫出，見圖4.

為了研究本地任務(wù)和全局任務(wù)所占比重的大小對(duì)總?cè)蝿?wù)錯(cuò)失率的影響，需要做進(jìn)一步的試驗(yàn).為此，以四個(gè)目標(biāo)為例，令本地負(fù)載從10%到80%進(jìn)行變化，得出在不同截止期分配方法下的總?cè)蝿?wù)錯(cuò)失率，如圖5所示.

3.3 仿真結(jié)果分析

由圖4a可知，在本地任務(wù)中，射擊近界法的子任務(wù)錯(cuò)失率最低，等靈活度法的子任務(wù)錯(cuò)失率最高，比例負(fù)載法介于兩者之間，但隨著目標(biāo)數(shù)量的增加，三者的差距基本保持不變.

由圖4b可知，在全局任務(wù)中，射擊近界法的錯(cuò)失率最高，而且隨著目標(biāo)數(shù)量的增加，與其他兩者的差距也有擴(kuò)大的趨勢(shì).比例負(fù)載法的錯(cuò)失率始終小于其他兩種分配方法，等靈活度法接近于比例負(fù)載法，介于其他兩者之間.

圖4 不同截止期分配方法的任務(wù)錯(cuò)失率直方圖

圖5 總?cè)蝿?wù)錯(cuò)失率隨本地負(fù)載變化直方圖

由圖4c可知，比例負(fù)載法在總?cè)蝿?wù)的錯(cuò)失率方面依然優(yōu)于其他兩種，而且隨著目標(biāo)數(shù)量的增加，與其他兩者的差距也有擴(kuò)大的趨勢(shì).

由圖5可知，隨著本地負(fù)載增加，射擊近界法的劣勢(shì)逐漸減弱，并最終占據(jù)略微的優(yōu)勢(shì).而且總?cè)蝿?wù)錯(cuò)失率會(huì)隨著本地負(fù)載的增加而升高.

綜上可知，對(duì)于全局任務(wù)的調(diào)度，比例負(fù)載法有一定的優(yōu)勢(shì)，而由于射擊近界法不考慮子任務(wù)的屬性和節(jié)點(diǎn)上的負(fù)載情況，只是簡(jiǎn)單地以武器的射擊近界作為子任務(wù)截止期，因此對(duì)于全局任務(wù)的調(diào)度錯(cuò)失率比較高.對(duì)于本地任務(wù)的調(diào)度，由于比例負(fù)載法和等靈活度法都對(duì)本地任務(wù)有所“排擠”，因此射擊近界法的表現(xiàn)要優(yōu)于二者.在總的任務(wù)錯(cuò)失率方面，各方法的表現(xiàn)與在全局任務(wù)中的表現(xiàn)相似，但差距有所減小，原因是在全局任務(wù)中等靈活度法的優(yōu)勢(shì)要大于其在本地任務(wù)中的劣勢(shì)，而且在總的任務(wù)數(shù)量中全局任務(wù)所占比例較大.

因此，對(duì)于子任務(wù)截止期的分配:

1)若難以預(yù)測(cè)子任務(wù)的執(zhí)行時(shí)間，或本地負(fù)載較高，可以采取射擊近界法進(jìn)行分配.

2)若子任務(wù)執(zhí)行時(shí)間有較準(zhǔn)確的預(yù)測(cè)或本地負(fù)載不高，則應(yīng)采取比例負(fù)載法進(jìn)行分配.

4 結(jié)論

試驗(yàn)結(jié)果證明，不同截止期分配方法對(duì)任務(wù)錯(cuò)失率有很大的影響，因此在分布式武器目標(biāo)分配問題中給全局任務(wù)的子任務(wù)分配合理的截止期是有必要的.

本文假定武器目標(biāo)的分配早于截止期的分配，而當(dāng)武器目標(biāo)的分配需要其截止期信息以及動(dòng)態(tài)環(huán)境中任務(wù)的截止期類型發(fā)生變化時(shí)，應(yīng)如何對(duì)截止期進(jìn)行分配，還需做進(jìn)一步的研究.

References)

［1］Kao B，Garcia-Molina H.Deadline assignment in a distributed soft real-time system［J］.IEEE Transaction on Parallel and Distributed Systems，1997，8(12):1268－1274

［2］Jan Jonsson，Kang G Shin.Robust adaptive metrics for deadline assignment in distributed hard real-time systems［J］.Real-Time Systems，2002，23(3):239－271

［3］Wang Zhigang，Wang Wei，Liu Quanli.An improved feedback deadline assignment algorithm for real-time control tasks scheduling［C］//Proceedings of the 6th World Congress on Intelligent Control and Automation.Dalian，China:［s.n.］，2006:6724－6727

［4］Pellizzoni R，Lipari G.Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling［J］.Journal of Computer and System Sciences，2007，73(2):186－206

［5］Zhou Yan，Kang Kyoung-Don.Deadline assignment and tardiness control for real-time data services［C］//22ndEuromicro Conference on Real-Time Systems.Washington，DC，USA:IEEE Computer Society，2010:100－109

［6］吳玲，盧發(fā)興.WTA問題的截止期定義及Anytime算法分析［J］.武漢理工大學(xué)學(xué)報(bào)，2010，32(6):140－143

Wu Ling，Lu Faxing.Analysis ofdeadlines and Anytime algorithms for weapon-target allocation problem［J］.Journal of Wuhan University of Technology，2010，32(6):140 －143(in Chinese)