一種基于多約束關系的任務分解方法

霍永華,昌漢明，曹　毅

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

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

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

?

一種基于多約束關系的任務分解方法

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

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

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

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

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

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

0引言

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

1任務的四要素

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

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

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

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

③ Time代表任務的持續時間；

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

2任務的關系約束

定義如下幾種關系約束：

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

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

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

圖3　全包含父子關系　　圖4　部分包含父子　示意圖　關系示意圖

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

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

圖5　任務分解樹示意圖

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

3基于任務樹的任務分解

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

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

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

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

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

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

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

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

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

步驟8：以節點任務表中的約束判斷輸出的節點是否符合串行執行約束，若是則任務分解樹中任務節點的層次逐步遞增，且層次低的節點指向層次高的節點，若不是則跳轉到步驟9；

步驟9：按節點重要性算法計算未置初值的任務節點的重要度，判斷是否需要優化，若是則跳轉到步驟10，不是則跳轉到步驟11；

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

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

4實例驗證

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

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

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

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

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

5結束語

為保證抗震救災環境下任務的執行，提出了救災網絡任務分解方法。文中提出的幾種約束關系，考慮到了任務和任務間，總任務和子任務間的關系。而重要度的提出也是考慮到作戰任務的特殊性，所謂重要度是指任務節點分主次，當出現緊急情況時優先考慮重要度高的任務，這可以保證在救災環境下作戰任務能最大限度地不受其他因素的影響。

參考文獻

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

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

[3]秦娜,樂曉波,劉武.基于 Petri 網模型的 JSP 粒子群優化調度[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]楊學會,王精業.基于任務分解的作戰仿真研究[J].系統仿真學報,2006,18(10):18-21.

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

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

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

[10]金黎黎,孔令富．協同設計環境中任務分解與調度的研究[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 —)，女，高級工程師，主要研究方向：通信網絡管理。昌漢明(1989— )，男，碩士研究生，主要研究方向：通信網絡管理。

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

收稿日期：2015-09-08

中圖分類號：TP393

文獻標識碼：A

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

doi:10.3969/j.issn.1003-3114.2016.01.09

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