周翔翔， 姚佩陽， 尹忠海

(空軍工程大學(xué)，a.電訊工程學(xué)院，西安 710077;b.理學(xué)院，西安 710051)

0 引言

以網(wǎng)絡(luò)為中心的協(xié)同作戰(zhàn)是現(xiàn)代戰(zhàn)爭的基本作戰(zhàn)形態(tài)和達(dá)成戰(zhàn)爭目的的主要手段［1］。在這種作戰(zhàn)模式下，戰(zhàn)役作戰(zhàn)任務(wù)通常分解為一系列相關(guān)的子作戰(zhàn)任務(wù)，這些子作戰(zhàn)任務(wù)是由多個指揮決策實體(Tactical Command Decision-Making Entity，DM)根據(jù)其控制的作戰(zhàn)平臺資源共同籌劃實施的［2］。指揮決策實體之間進(jìn)行信息共享可以改善決策質(zhì)量、進(jìn)行平臺資源共享以分擔(dān)作戰(zhàn)任務(wù)，有利于提高指揮決策的效能。然而僅僅依靠完全對等的協(xié)作會降低決策效率，這就需要根據(jù)作戰(zhàn)任務(wù)，在指揮決策實體之間建立一定的層次結(jié)構(gòu)［3－5］，使得角色和分工不同的DM在任務(wù)的協(xié)作處理上獲得較高的效率。

面向戰(zhàn)役作戰(zhàn)任務(wù)，生成一個扁平合理的DM層次結(jié)構(gòu)主要有以下兩個優(yōu)點［6－8］:1)降低DM間的協(xié)調(diào)代價，提高DM間的決策速度和效率;2)當(dāng)DM組織遭受打擊時，根據(jù)DM之間的層次關(guān)系，便于設(shè)計有效的指揮決策職責(zé)接替規(guī)則，保證組織功能的有效運作。

文獻(xiàn)［7，9－11］對DM間的層次結(jié)構(gòu)設(shè)計方法進(jìn)行了研究，給出了由協(xié)作交流網(wǎng)生成指揮控制樹的Gomory-Hu樹構(gòu)造算法，該方法屬于一種破圈法。

本文描述了指揮決策實體層次結(jié)構(gòu)設(shè)計的基本概念，建立了數(shù)學(xué)模型，并從并鏈成樹的角度，給出了指揮決策實體(DM)間層次結(jié)構(gòu)的形成方法。

1 基本概念描述

設(shè)計指揮決策實體(DM)間的層次結(jié)構(gòu)涉及以下幾種基本概念。

作戰(zhàn)任務(wù)(Combat Task，T)是作戰(zhàn)單元為完成所賦予的作戰(zhàn)使命而實施的一次行動，是戰(zhàn)場中作戰(zhàn)資源的某一種或幾種功能協(xié)同執(zhí)行的行為集合。

指揮決策實體(Command Decision-Making Entity，DM)是一個具有信息處理并進(jìn)行決策的實體，它根據(jù)其控制的作戰(zhàn)平臺資源，籌劃并實施作戰(zhàn)任務(wù)［12］。

作戰(zhàn)平臺資源(Combat Platform Resource，R)是處理作戰(zhàn)任務(wù)所需的物理資源實體，是決策者執(zhí)行任務(wù)的憑借［2，4］。平臺包括火力實體和感知實體。

決策實體通過對平臺的管理控制來執(zhí)行使命任務(wù)，決策實體間通過平臺在任務(wù)上的協(xié)作便構(gòu)成了協(xié)作交流網(wǎng)。協(xié)作交流網(wǎng)反映了決策實體之間的任務(wù)協(xié)作關(guān)系，并不是決策實體之間的實際組織關(guān)系。

指揮控制樹體現(xiàn)了DM間的層次結(jié)構(gòu)。指揮控制樹確定了DM之間的決策關(guān)系，以DM為節(jié)點，DM間的指揮關(guān)系的鏈接為邊，由根節(jié)點與其他節(jié)點建立起有向鏈接關(guān)系，樹中沒有環(huán)路。

本文以協(xié)作交流網(wǎng)G(V，E，U)為基礎(chǔ)，設(shè)計DM之間的層次結(jié)構(gòu)，即指揮控制樹，其形式化描述為

其中，F(xiàn)為下文將詳細(xì)描述的DM層次結(jié)構(gòu)設(shè)計算法。

2 層次結(jié)構(gòu)設(shè)計方法

2.1 模型建立

對于協(xié)作交流網(wǎng)G(V，E，U)，其生成樹并不唯一，需要根據(jù)具體問題求解具備某種條件的G(V，E，U)的生成樹。如在通信網(wǎng)絡(luò)中的最小生成樹、Stenier樹等。針對DM層次結(jié)構(gòu)特點，構(gòu)造的指揮控制樹需要描述任務(wù)協(xié)作與指揮控制特性的生成樹越扁平越好，這樣可以減少DM之間交互協(xié)作的復(fù)雜度。下文首先給出一些定義，之后建立DM層次結(jié)構(gòu)模型。

每個DM與其他DM之間的協(xié)作包括信息交換和任務(wù)協(xié)作，本文借鑒文獻(xiàn)［9－11］的工作負(fù)載定義，僅從任務(wù)協(xié)作的角度給出DM協(xié)作量的定義，該協(xié)作量值即為協(xié)作交流網(wǎng)中邊的權(quán)值。

定義1任意兩個DM(vi，vj)之間的任務(wù)協(xié)作量uij為vi和vj協(xié)作完成任務(wù)的工作量之和，則

定義2路徑長度。設(shè)協(xié)作交流網(wǎng)(連通圖)G(V，E，U)中任意兩個節(jié)點vi和vj的最短路徑為Pmin(Vi，Vj)，則 vi到 vj的路徑長度為路徑 Pmin(Vi，Vj)的邊權(quán)值和，即

其中，Line為獲取路徑邊權(quán)值和的算子。兩個節(jié)點vi和vj的路徑長度表示vi和vj之間的協(xié)作功能鏈的任務(wù)協(xié)作總量。

定義3樹高。設(shè) T=T(V，E′，U′)為樹，vb為 T的根節(jié)點，令h為由根節(jié)點vb至樹T的各節(jié)點路徑長度的最大值，即

則h為樹T的樹高。

定義4扁平生成樹。設(shè)協(xié)作交流網(wǎng)G(V，E，U)的生成樹記為T，T的樹高記為H(T)，G的生成樹集合記為Q，樹高最小的生成樹T0稱為扁平生成樹，即T0滿足

傳統(tǒng)意義上將樹中節(jié)點的最大層次定義為樹高，本文定義的樹高是樹中節(jié)點的最大路徑長度。從根節(jié)點DM到其他每個DM都存在一個指揮功能鏈，樹高表示了指揮功能鏈上任務(wù)協(xié)作總量的最大值，而扁平樹是最大路徑長度最小(指揮功能鏈的任務(wù)協(xié)作量總和最大)的生成樹。本文需要構(gòu)造的指揮控制樹即為協(xié)作交流網(wǎng)的扁平生成樹，即

2.2 算法分析

根據(jù)上文構(gòu)造的模型，以下逐步給出扁平指揮控制樹的構(gòu)造方法。

定理1設(shè)協(xié)作交流網(wǎng)G(V，E，U)為連通圖，vs，ve，記 vs，ve間的最短路為 Pmin(vs，ve)，則 Pmin(vs，ve)為鏈。

證明 由于 vs≠ve，設(shè) vs，ve間的最短路 Pmin(vs，ve) 為 vse1v1e2v2…eivi…ejvj…emve，如圖 1a 所示。

若 Pmin(vs，ve)不是鏈，則必有路徑 Pmin(vs，ve)的中間節(jié)點 vi，vj，使得 vi=vj，即 Pmin(vs，ve)如圖 1b 所示。

圖1 路徑示意圖Fig.1 Sketch map of path

即在路徑Pmin(vs，ve)中存在一條由 vi至 vj的回路，顯然，路徑P′min(vs，ve)=vse1v1e2v2…eiviej+1vj+1…emve是一條由vs至ve的最短路徑，與vs至ve的最短路矛盾，故最短路一定是鏈。

定理2設(shè)協(xié)作交流網(wǎng)G(V，E，U)為連通圖，vb為取定的根節(jié)點，vb至圖G中任意節(jié)點vi的最短路徑記為Pmin(vb，vi)，若最短路是唯一的，則所有最短路的并

為圖G的一棵生成樹。

圖2 帶回路的非樹示意圖Fig.2 Sketch map of non-tree with loop

圖2 中 v1→v2→v3→v4→v5→v6→v1構(gòu)成了回路，顯然vb→v1→v2→v3→v4是vb至v4的最短路，同時vb→v1→v6→v5→v4也構(gòu)成vb至v4的最短路，與最短路唯一的假設(shè)矛盾，故T構(gòu)成樹。

定理3按式(7)構(gòu)造的生成樹T0是最扁平生成樹。

證明 設(shè)存在另一棵生成樹T0′使得H(T0)，則必存在某一節(jié)點v0，使得T0′中由根節(jié)點vb至v0的距離小于樹T0中由vb至v0的距離，則T′0中由vb至v0的路徑是一條比T0中由vb至v0距離更短的路徑，這與T0中由vb至v0是最短路的結(jié)論矛盾，故T0是扁平生成樹。

對于給定的協(xié)作交流網(wǎng)G(V，E，U)，取定V中節(jié)點vb為根節(jié)點，vb至G中任一節(jié)點vi的最短路記為Pmin(vb，vi)，則vb到所有其他節(jié)點的最短路的并即為G(V，E，U)的一個生成樹，且該樹為扁平生成樹。即指揮控制樹 TC為 G(V，E，U)的所有最短路 Pmin(vb，vi)的并，則

例如對于具有6個節(jié)點的協(xié)作交流網(wǎng)，取定v3為根節(jié)點，v3到其他節(jié)點的最短路徑分別為:v3→v1、v3→v4→v6→v2、v3→v4、v3→v4→v6→v5、v3→v4→v6，則以 v3為根節(jié)點的指揮控制樹如圖3所示。

圖3 最短路徑并操作示例Fig.3 Example of the shortest path and operation

上述分析為解決指揮控制樹構(gòu)造問題提供了切實可行的方法，但其實現(xiàn)還需要兩個前提:1)保證任意兩個節(jié)點之間的最短路唯一;2)需要確定指揮控制樹的根節(jié)點。下面分別給出這兩個問題的解決方法。

1)節(jié)點之間唯一最短路的選擇方法。

協(xié)作交流網(wǎng)G(V，E，U)中任意兩個節(jié)點vi和vj之間的最短路徑并不一定唯一。為保證求出的最短路徑滿足定理2所要求的唯一性條件，本文對Floyd算法進(jìn)行了限定，限定算法中每次處理的節(jié)點都是滿足條件序號最小的節(jié)點，即每次處理都首先選擇距離最近的節(jié)點，當(dāng)多個節(jié)點的距離相同時選擇序號最小的節(jié)點。

2)指揮控制樹根節(jié)點的確定方法。

定義5最大路徑長度、平均路徑長度。

設(shè)協(xié)作交流網(wǎng)(連通圖)G(V，E，U)中任意vi到其他所有節(jié)點的最大路徑長度為

vi到其他所有節(jié)點的平均路徑長度為

本文確定指揮控制樹根節(jié)點的方法是依次按照3個規(guī)則實施，直到滿足條件的節(jié)點唯一。這3個規(guī)則的目的都是查找滿足一定條件的節(jié)點(或節(jié)點集)，規(guī)則分別為協(xié)作交流網(wǎng)中節(jié)點到其他所有節(jié)點的最大路徑長度最小、節(jié)點到其他所有節(jié)點的平均路徑長度最小、節(jié)點序號最小。

2.3 算法步驟

基于以上討論，本文給出以下指揮控制樹的構(gòu)造算法步驟。

1)根據(jù)協(xié)作交流網(wǎng)中DM之間關(guān)于作戰(zhàn)任務(wù)的任務(wù)協(xié)作量信息，計算協(xié)作交流網(wǎng)中任意兩個指揮決策實體vi和vj的邊權(quán)值，構(gòu)成網(wǎng)G的邊E的權(quán)值集合U={uij|1≤i，j≤nV，uij=u(ek)，ek∈E}，uij=0 表示兩個節(jié)點之間沒有鏈接，uii=0表示節(jié)點到自己沒有自回路。

2)根據(jù)指揮決策節(jié)點之間唯一最短路的選擇方法，獲得協(xié)作交流網(wǎng)中任意vi、vj的唯一最短路徑，為Pmin(vi，vj)。

3) 根據(jù)任意 vi、vj的 Pmin(vi，vj)，采用式(9)、式(10)，求得vi的和

4)基于3個層次規(guī)則的指揮控制樹根節(jié)點的確定方法，求得指揮控制樹的根節(jié)點為vb。

5) 將根節(jié)點 vb到其他所有節(jié)點 vi，i=1，2，…，nV，的唯一最短路徑進(jìn)行合并，得到指揮控制樹TC。

3 算法應(yīng)用及對比分析

以一次登島戰(zhàn)役作戰(zhàn)為例，其作戰(zhàn)使命任務(wù)為登陸搶占敵方的機場和港口，為后續(xù)部隊向縱深推進(jìn)掃清障礙。根據(jù)這個使命任務(wù)和作戰(zhàn)環(huán)境可以將作戰(zhàn)任務(wù)分解為［2，10］10 個作戰(zhàn)任務(wù)。

本文設(shè)定10個作戰(zhàn)任務(wù)的作戰(zhàn)平臺配置已完成，并對作戰(zhàn)平臺資源進(jìn)行了分組，每組作戰(zhàn)平臺資源設(shè)置一個DM。作戰(zhàn)平臺可分為6個組，故設(shè)置了6個DM。DM之間由于共同執(zhí)行任務(wù)而建立任務(wù)協(xié)作關(guān)系，形成DM之間的協(xié)作交流網(wǎng)如圖4所示。

圖4 協(xié)作交流網(wǎng)算例Fig.4 Collaboration-intercourse net

圖4 中兩個DM之間的值表示兩者協(xié)作的任務(wù)數(shù)量。表1中給出了DM之間的協(xié)作的各個任務(wù)的協(xié)作量。其中表示DM vi與DM vj之間的關(guān)于協(xié)作任務(wù)k的協(xié)作量。

表1 DM之間的任務(wù)協(xié)作量Table 1 Task collaboration value between DMs

根據(jù)表1，計算協(xié)作交流網(wǎng)的邊權(quán)值為

基于圖4所示的協(xié)作交流網(wǎng)，結(jié)合協(xié)作交流網(wǎng)的邊權(quán)值，根據(jù)節(jié)點之間唯一最短路的選擇方法，采用式(3)、式(9)、式(10)可以計算得到DM之間的路徑長度關(guān)系如表2所示。

表2 DM節(jié)點間的路徑長度Table 2 Path length between DMs

根據(jù)表2的結(jié)果，由于到其他節(jié)點的最大路徑長度最小的節(jié)點只有v5，故選擇v5為指揮控制樹的根節(jié)點。以v5為根節(jié)點，采用本文算法得到的指揮控制樹如圖5所示。

圖5 生成的指揮控制樹Fig.5 The created command and control tree

在現(xiàn)實中，擔(dān)負(fù)一個戰(zhàn)役任務(wù)的決策實體間的組織關(guān)系可以是層次式、網(wǎng)絡(luò)式或混合式的，本文設(shè)計的指揮控制樹作為一種層次結(jié)構(gòu)，明確了決策實體間的決策與交流結(jié)構(gòu)，為之后的多實體間的作戰(zhàn)計劃制定奠定了基礎(chǔ)。若某個任務(wù)由單個決策實體擔(dān)負(fù)，則該決策實體具有該任務(wù)的獨立決策權(quán);若某個任務(wù)由多個決策實體擔(dān)負(fù)，則根據(jù)決策實體在指揮控制樹中的位置，明確在該任務(wù)的計劃制定中的信息流向、指令流向和決策權(quán)。比如任務(wù)t9由4個決策實體v2、v3、v4、v5共同擔(dān)負(fù)，信息由 v2、v3、v4流向 v5，指令由 v5流向 v2、v3、v4，v5負(fù)責(zé)作戰(zhàn)任務(wù)t9計劃制定中的協(xié)調(diào)和各決策實體作戰(zhàn)方案的融合。

4 結(jié)論

本文以設(shè)計適應(yīng)現(xiàn)代戰(zhàn)爭需求的指揮決策實體的層次結(jié)構(gòu)為目標(biāo)，建立了協(xié)作交流網(wǎng)的扁平生成樹模型;從并鏈成樹的視角，給出了扁平生成樹構(gòu)造算法;在算法實現(xiàn)的技術(shù)處理上，給出了確定網(wǎng)中任意兩個節(jié)點之間唯一最短路徑的方法，以及基于3個層次規(guī)則的指揮控制樹根節(jié)點的確定方法。實驗結(jié)果表明本文方法是有效的。

［1］ 陽曙光，時劍，李為民.聯(lián)合火力打擊協(xié)同式指揮控制模式及其軍事概念建模［J］.電光與控制，2008，15(2):1-4.

［2］ 陽東升，劉忠，張維明.組織模型與自適應(yīng)機理分析［J］.系統(tǒng)工程與電子技術(shù)，2008，30(10):1929-1933.

［3］ LEVCHUK Y N，LUO J，LEVCHUK G M，et al.A multifunctional software environment for modelling complex mission and devising adaptive organizations［R］.Arlington:Office of Naval Research，2005.

［4］ LEVCHUK G M，LEVCHUK Y N，WEIL S A，et al.Persuade:Modeling framework for the design of modular army organizations［C］//Proceedings of the 2006 Command and Control Research and Technology Symposium，San Diego，CA，2006:1-24.

［5］ 周道安，張東戈，常樹春.C2組織指揮控制關(guān)系的形式化描述［J］.指揮控制與仿真，2008，30(4):13-17.

［6］ 陽東升，張維明，劉忠，等.指控組織設(shè)計方法［M］.北京:國防工業(yè)出版社，2010.

［7］ LEVCHUK G M，LEVCHUK Y N，LUO J，et al.Normative design of organizations-part II:Organizational structure［J］.IEEE Transactions on Systems，Man and Cybernetics，2002，32(3):360-375.

［8］ WANG L，KANG Q，WU Q D.Nature-inspired computation effective realization of artificial intelligence［J］.Systems Engineering Theory ＆ Practice，2007，27(5):126-134.

［9］ 修保新，張維明，劉忠，等.基于粒度計算和遺傳算法的C2組織結(jié)構(gòu)設(shè)計方法［J］.自然科學(xué)進(jìn)展，2007，17(5):662-671.

［10］ YU F.Advanced optimization techniques with applications to organizational design and graph-based inference［D］.University of Connecticut，2007.

［11］ 劉宏芳，陽東升，劉忠，等.兵力編成結(jié)構(gòu)裁剪中指揮關(guān)系優(yōu)化研究［J］.國防科技大學(xué)學(xué)報，2006，28(4):99-104.

［12］ YU F，TU F，PATTIPATI K R.Integration of a holonic organizational control architecture and multiobjective evolutionary algorithm for flexible distributed scheduling［J］.IEEE Transactions on Systems，Man and Cybernetics，Part A:Systems and Humans，2008，38(5):1001-1017.