霍永華,昌漢明，曹　毅

(1.中國電子科技集團公司第五十四研究所,河北 石家莊 050081；

2.西安電子科技大學，陜西 西安 710071;

3.總參信息化部石家莊地區(qū)軍事代表室，河北 石家莊 050000)

?

一種基于多約束關(guān)系的任務分解方法

霍永華1,昌漢明2，曹毅3

(1.中國電子科技集團公司第五十四研究所,河北 石家莊 050081；

2.西安電子科技大學，陜西 西安 710071;

3.總參信息化部石家莊地區(qū)軍事代表室，河北 石家莊 050000)

摘要：針對任務分解和分配的實時性和快速性，研究基于多約束關(guān)系的任務分解。首先對任務進行初始化標識，定義任務的唯一標識、開始時間、生命周期及任務重要度。其次定義任務間的約束關(guān)系，包括同步、串行、父子關(guān)系以及同步下受時序和資源約束等，確定任務之間的相互聯(lián)系，為執(zhí)行任務分解做好準備。然后，研究一種基于任務分解樹的算法：依據(jù)任務間約束關(guān)系通過任務分解樹的方法實現(xiàn)對任務的分解。最后附實例驗證。

關(guān)鍵詞：任務重要度；同步關(guān)系；串行關(guān)系；父子關(guān)系；任務分解樹

0引言

針對抗震救災壞境中宏觀任務的下達，任務的分解細化過程，研究一種任務的分解機制[1-3]。該機制首先依據(jù)任務的具體狀況定義任務的唯一標識、開始時間、生命周期及任務重要度，實現(xiàn)對任務的初始化標識。其次定義任務間的約束關(guān)系[4-6]，包括同步、串行、父子關(guān)系以及同步下受時序和資源約束等，確定任務之間的相互聯(lián)系，為執(zhí)行任務分解做好準備。然后，研究一種基于任務分解樹的算法：建立一棵空的任務樹，將任務節(jié)點放入任務隊列中，依據(jù)任務間的約束關(guān)系從任務隊列中提取并放入任務樹的適當位置，直至任務隊列為空，這樣最終依據(jù)任務間約束關(guān)系通過任務分解樹的方法實現(xiàn)對任務的分解。

1任務的四要素

任務可以分為復雜任務和簡單子任務，為了更好地完成某個目標，其對應的任務應該進行分解和調(diào)度，以保障更好更快地完成。

定義每一個任務為一個四元組[7,8]G=(ID,Begin,Time,I)

① 其中ID代表每一個任務的名字，不同的任務具有不同的ID，且不可相同；

② Begin代表任務的開始時間，因為任務的分解與調(diào)度中常有時序約束，所以要考慮不同任務的開始時間；

③ Time代表任務的持續(xù)時間；

④ I代表任務的重要度。所謂重要度指當遇到突發(fā)情況時，每個節(jié)點的緊急情況可能各不相同，重要的節(jié)點應優(yōu)先考慮處理，不同的任務可能具有不同的重要度。

2任務的關(guān)系約束

定義如下幾種關(guān)系約束：

① 同步執(zhí)行任務集 P={T1，T2，T3}，即任務T1、T2、T3可以同步地執(zhí)行，主要是對于同層的節(jié)點，如圖1所示。

圖1　并行任務示意圖　圖2　串行任務示意圖

③ 父子關(guān)系任務集 F={T5，T6，T7}，即任務T5可以進一步分解為T6、T7。表示T5是T6和T7的父節(jié)點，父子關(guān)系任務集中，父節(jié)點可能全面的包含子任務或是部分包含，全面包含指的是子任務全部完成，父任務才可執(zhí)行，用集合表示為：T={T5，A{T6，T7}}，如圖3所示。而部分包含指的是完成部分子任務后即可開始執(zhí)行父任務，用集合表示為T={T5，O{T6，T7}}，如圖4所示。用方框置于外側(cè)是表示這是一個任務分解模塊，T5是由T6和T7組成的。

圖3　全包含父子關(guān)系　　圖4　部分包含父子　示意圖　關(guān)系示意圖

綜合分析上述情況可以把任務分解表示在一個大的集合內(nèi)。

根據(jù)上述定義可以得出任務分解樹，如圖5所示。

圖5　任務分解樹示意圖

其中T1對T3有時序或資源方面的約束，在圖中用T1-3來表示這種約束關(guān)系。T3、T4、T5是串行執(zhí)行的。T6、T7全包含于T5。針對不同任務節(jié)點的重要度，可以對任務分解圖進一步優(yōu)化，節(jié)點的重要度可以開始時由更高層級直接指定，若沒有指定，則依據(jù)節(jié)點重要性的算法來衡量。假設圖5中高層級指定了T3的重要度高于T2，則在出現(xiàn)緊急情況時優(yōu)先考慮T3。若沒有指定，以節(jié)點重要性的角度去考慮，T3節(jié)點的度數(shù)高于T2，所以T3重要度大于T2(以節(jié)點的度來衡量重要性)，根據(jù)以上兩種情況，可以把任務分解樹優(yōu)化。

3基于任務樹的任務分解

在進行任務調(diào)度時，首先要考慮節(jié)點間的時序約束，其次當在進行任務調(diào)度出現(xiàn)緊急情況時，同層中左邊節(jié)點的重要度大于右邊，所以優(yōu)先處理左邊節(jié)點出現(xiàn)的情況，這種任務分解樹看上去直觀，且考慮的更加全面。

基于任務樹的任務分解算法[9,10]步驟如圖5所示。

步驟1：初始化任務樹節(jié)點置為空，把每項任務定義為任務樹中的節(jié)點，并把節(jié)點間的相互約束關(guān)系置于節(jié)點關(guān)系表中；

步驟2：為每個節(jié)點分配唯一的ID，初始化任務的開始時間Begin和預估執(zhí)行時間Time，根據(jù)需要判斷是否初始化重要度I，若需要則給定相應等級，否則置為空；

步驟3：設置一個隊列，把所有任務節(jié)點置于隊列中，首先輸出代表源節(jié)點的節(jié)點S；

步驟4：從隊列中依次輸出每個任務節(jié)點；

步驟5：輸出的節(jié)點是否需要進一步分解，若是則符合父子約束關(guān)系，在任務分解樹中生成該節(jié)點的子節(jié)點，其層次為父節(jié)點加一，并由父節(jié)點指向子節(jié)點。若不是則跳轉(zhuǎn)到7；

步驟6：判斷父節(jié)點是全包含還是部分包含，若是全包含則所有子任務執(zhí)行完成才認為父節(jié)點完成，是部分包含則部分子任務完成，父任務就認為完成；

步驟7：以節(jié)點任務表中的約束判斷輸出的節(jié)點是否符合同步執(zhí)行約束，若是則任務分解樹中節(jié)點間層次相同并假設層次為n，且由n-1層節(jié)點同時指向它們。若不是則跳轉(zhuǎn)到步驟8；

步驟8：以節(jié)點任務表中的約束判斷輸出的節(jié)點是否符合串行執(zhí)行約束，若是則任務分解樹中任務節(jié)點的層次逐步遞增，且層次低的節(jié)點指向?qū)哟胃叩墓?jié)點，若不是則跳轉(zhuǎn)到步驟9；

步驟9：按節(jié)點重要性算法計算未置初值的任務節(jié)點的重要度，判斷是否需要優(yōu)化，若是則跳轉(zhuǎn)到步驟10，不是則跳轉(zhuǎn)到步驟11；

步驟10：同層中把沒有時序約束且重要度高的節(jié)點i(包括它的子節(jié)點)不斷左移，直到其左側(cè)節(jié)點對i有約束則停止，所有節(jié)點優(yōu)化完跳到步驟11；

步驟11：重復執(zhí)行步驟3，直到隊列中節(jié)點為空，生成任務分解樹。

4實例驗證

假設某次抗震救災補給災區(qū)運輸車加油，由于搭建基地就只有一個，所以每個運輸車按串行補給，總補給任務稱為S，假設有n輛運輸車，表示為B1、B2…Bn則n輛車之間的關(guān)系為串行關(guān)系，也就是當?shù)?輛車加油完畢后，第2輛車才能加油。

步驟1：對任務進行初始化標識，定義唯一標識為S，任務分為兩類，即運輸油A和加油B，開始時間為ts，生命周期為T，任務重要度為非常重要；

步驟2：定義任務間的約束關(guān)系，只有運輸油到的情況下，才能加油。因此對運輸油任務A對加油任務B有時序約束。在運輸加油任務中，由于加油基地只有一個，所以只能一個一個進行加油，因此加油任務A為同步關(guān)系；運輸油任務B可以并行進行；

步驟3：建立一棵空的任務樹S，將任務節(jié)點(任務A和任務B)放入任務隊列中，依據(jù)兩個任務間的約束關(guān)系(任務A對任務B有時序約束)，從任務隊列中提取并放入任務樹的適當位置，任務分解樹如圖6所示。

圖6　抗震救災運輸車加油任務分解圖

5結(jié)束語

為保證抗震救災環(huán)境下任務的執(zhí)行，提出了救災網(wǎng)絡任務分解方法。文中提出的幾種約束關(guān)系，考慮到了任務和任務間，總?cè)蝿蘸妥尤蝿臻g的關(guān)系。而重要度的提出也是考慮到作戰(zhàn)任務的特殊性，所謂重要度是指任務節(jié)點分主次，當出現(xiàn)緊急情況時優(yōu)先考慮重要度高的任務，這可以保證在救災環(huán)境下作戰(zhàn)任務能最大限度地不受其他因素的影響。

參考文獻

[1]肖增良,樂曉波.基于與或依賴圖的多Agent系統(tǒng)任務分解算法[J].計算機工程與設計,2009，40(2):267-272.

[2]鐘琪.基于啟發(fā)式算法的任務分解策略[J].煤炭技術(shù)，2010,30(12)：25-29.

[3]秦娜,樂曉波,劉武.基于 Petri 網(wǎng)模型的 JSP 粒子群優(yōu)化調(diào)度[J].計算機應用,2008,28(8):2167-2169.

[4]White J E.Mobile Agents In：Bradshaw，Jeffrey eds.Software Agents，Menlo Pork [M]. California:Press / The MIT Press，1996.

[5]Lange D B.Mobile Objects and Mobile agents：The Future of Distributed Computing[C]∥Proc of the European Conf on Object Oriented Programming’98.Brussels，1998:49-52.

[6]楊學會,王精業(yè).基于任務分解的作戰(zhàn)仿真研究[J].系統(tǒng)仿真學報,2006,18(10):18-21.

[7]劉波,羅軍舟.大規(guī)模網(wǎng)絡管理中的任務分解與調(diào)度[J].通信學報,2010,42(6):48-51.

[8]劉波,羅軍舟.網(wǎng)絡管理中多agent的半在線調(diào)度算法[J].計算機研究與發(fā)展,2006，27(3)：65-72.

[9]王紅霞,劉治國,潘成勝．分布式網(wǎng)絡管理中的任務管理與任務調(diào)度的研究[J]．沈陽工業(yè)學院學報，2009,30(11):15-19.

[10]金黎黎,孔令富．協(xié)同設計環(huán)境中任務分解與調(diào)度的研究[J].計算機工程與設計，2009，25(2)：22-25.

Task Decomposition Method Based on Multiple Constraint Relations

HUO Yong-hua1,CHANG Han-ming2,CAO Yi3

(1.The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China;

2.Xidian University,Xi’an Shaanxi 710071,China;

3.Military Representative Office of Information Technology Department of General Staff Headquarters Stationed in Shijiazhuang,

Shijiazhuang Hebei 050081,China)

Abstract：In view of timeliness and quickness of task decomposition,this paper studies the task decomposition based on multiple constraint relations.Firstly the initialization identifier is defined on task,including unique identification and start time and life cycle and importance of missions.Secondly the constraint relations between tasks are defined,including synchronous relations and serial relations,father and son relations,time and resource constraints in synchronization,the inter-relationship between tasks are determined for preparation for task decomposition.Lastly an algorithm based on task decomposition tree is studied,which uses task decomposition tree to implement task decomposition according to constraint relations between tasks.Finally this algorithm is verified by an instance.

Key words：importance of Missions;synchronous relations;serial relations;father and son relations;task decomposition tree

作者簡介：霍永華(1977 —)，女，高級工程師，主要研究方向：通信網(wǎng)絡管理。昌漢明(1989— )，男，碩士研究生，主要研究方向：通信網(wǎng)絡管理。

基金項目：國防基礎科研計劃基金項目資助

收稿日期：2015-09-08

中圖分類號：TP393

文獻標識碼：A

文章編號：1003-3114(2016)01-35-3

doi:10.3969/j.issn.1003-3114.2016.01.09

引用格式：霍永華,昌漢明，曹毅.一種基于多約束關(guān)系的任務分解方法[J].無線電通信技術(shù),2016,42(1):35-37.