基于OODA環的分布式作戰仿真時間管理算法*

馬 也 ，常天慶 ，范文慧 ，李 婕 ，孔德鵬

(1.陸軍裝甲兵學院 兵器與控制系，北京 100072；2.清華大學 自動化系，北京 100084；3.解放軍總醫院京南醫療區 杜家坎門診部，北京 100072；4.92942部隊，北京 100161)

0 引言

OODA環理論是由BOYD J提出的軍事作戰中的戰略決策理論[1]，成為對作戰中出現的沖突問題進行描述的一種科學方法。該理論一經提出，便立即被整個西方世界的軍事界所認可，至今仍被廣泛應用于軍事作戰仿真問題的研究[2]。眾多學者對其進行研究并提出模塊化OODA環、智能OODA環及認知OODA環等衍生理論[3-5]。在信息化戰爭時代，對多國聯合軍事演習、協同軍事打擊以及與其他軍兵種部隊的共同作戰需求的增加，使得普通仿真難以應對[6-7]。分布式仿真因其更高的性能及靈活性越來越多地被軍事作戰仿真所采用。分布式仿真的技術難點是如何確保系統的因果邏輯關系，正確及可重復地在并行系統上高效合理地處理事件并推進仿真時間。時間管理技術是分布式仿真的一項重點技術，用于解決分布式仿真的時間推進問題，它決定了分布式仿真系統的整體性能，被該領域的研究者廣泛關注[8-9]。

典型的時間管理算法有保守算法及樂觀算法兩種。保守算法雖可以嚴格保證系統因果約束，正確地進行時間推進。但其依賴前瞻量和空消息機制，給系統帶來無法避免的死鎖問題，嚴重影響系統性能。樂觀算法允許違反系統因果約束，通過回退機制來解決因果關系錯誤。雖能夠積極地處理事件并避免保守算法帶來的死鎖問題，但回退機制會占用系統內存，過度的樂觀又會造成多級回退現象，從而不利于系統的并行性并使性能大幅下降。后續的研究者針對以上問題提出了一些解決方法，大多存在系統實現復雜、在犧牲系統性能的前提上保證因果約束以及需要改變模型來獲取計算性能等缺點。

本文綜合考慮保守及樂觀算法的優缺點，針對OODA環作戰仿真的特點，提出一種基于改進GVT的自適應時間窗混合推進時間管理算法并對全局虛擬時間算法的計算進行改進。算法能夠改善傳統時間窗算法頻繁同步問題，同時避免出現傳統時間管理算法的死鎖及多級回退等缺點。

1 OODA環作戰模型的構建

BOYD J提出的OODA環理論指出，軍事行動基本上是由一系列決策過程或循環組成的?；AOODA環主要包括偵察(Observation)、判斷(Orientation)、決策(Decision)和行動(Action)四部分[10-11]。具有指揮控制特點的軍事作戰OODA環按照上述四部分進行循環的戰斗，在一個循環結束后便開始新的循環，如此往復。循環周期的時間長短與作戰單位的兵力規模、作戰環境的范圍以及作戰的方式相關。

1.1 OODA環作戰因果關系

在作戰過程中，己方和敵方將持續進行戰場觀察獲取作戰信息，對信息進行判斷和分析后進行決策并采取相應的行動。其對抗沖突主要體現在OODA的周期長短上，優先采取行動的一方將獲取主動權和優勢，雙方都將盡可能地縮短自己的循環周期。OODA環作戰雙方交戰因果關系如圖1所示。

圖1 OODA環作戰雙方交戰因果關系

1.2 OODA環作戰模型

模型采用美國海軍分析中心(Center for Naval Analyses，CAN)提出的經典Agent作戰模型EINSTein的框架[12]，在該框架的基礎上構建一個基于多Agent的作戰仿真模型，該模型用于測試分布式仿真時間管理算法的有效性。模型中每個Agent代表一個作戰兵力，它有3種狀態，分別為存活、受傷和死亡。每個Agent賦予一個特征權值向量：

式中，-1 ≤ωx≤1，∑|ωx|=1。x的取值為{x|AF，AE，IF，IE}。每個權值向量由4個分量組成，分別為己方存活權值分量(ωAF)、敵方存活權值分量(ωAE)、己方受傷權值分量(ωIF)、和敵方受傷權值分量(ωIE)。Agent將根據各自特征權值向量的值決定自己在所處戰場環境中的移動策略。當分量值為正時，代表該Agent有靠近分量給定特征的Agent的意愿；當分量值為負時，則為撤退意愿。Agent所有可能進行的移動策略將由懲罰函數z來排序，通過計算懲罰函數z的最小值確定Agent具體的移動方向。懲罰函數z定義為：

其中，Bxy是Agent所處環境的坐標位置；AF、IF、AE、IE、Nx分別定義為當前Agent感知范圍內的己方存活的Agent集合、己方受傷的Agent集合、敵方存活的Agent集合、敵方受傷的Agent集合以及x類型Agent的總數；為己方比例因子；為敵方比例因子；DX，Y為X到Y的距離；懲罰函數z可以有效權衡Agent與其他敵我雙方在內的Agent的距離，其下標與Agent特征權值向量下標相同。通過懲罰函數，Agent將移動到懲罰最低的方向，該方向能最大程度地滿足其特征權值向量的大小所期望的方向。

懲罰函數同時也受μ 規則的限制作出部分改變，Agent將根據環境的動態變化改變個性權值。μ 規則如下式所示：

其中，NF(rF)為在已方觀察范圍內己方的Agent數量；NE(rE)為敵方觀察范圍內敵方的Agent數量；Δ 為戰斗閾值數量。μ 規則可描述為，當Agent的觀察范圍內存在的己方數量比敵方數量具有不到戰斗閾值的優勢，那么該Agent將遠離敵方Agent。

模型中的戰場地形為離散的二維網格，初始狀態下，敵方和我方以中軸線為軸，隨機分布在其所屬的地形中。Agent初始默認狀態為存活狀態，當其被攻擊命中后，Agent的狀態將降級為受傷狀態，若再次受到攻擊，將降級為死亡狀態，死亡狀態的Agent在仿真結束前不會再出現。處于受傷狀態的Agent的作戰命中率為存活狀態的命中率的一半。每個Agent又包括觀察范圍、移動范圍和火力范圍的3種距離范圍，用于進行作戰OODA環的執行。Agent的攻擊目標為其火力范圍內所有的敵方Agent，每次隨機從中挑選一個進行攻擊。

OODA環作戰模型作戰流程如圖2所示。

圖2 OODA環作戰模型流程圖

首先對戰場及作戰兵力進行初始化，隨后進入OODA環循環過程。每個Agent根據觀察范圍觀察戰場情況；隨后通過懲罰函數z對接收到的戰場情況進行判斷，計算移動范圍內所有的移動策略并進行排序；當判斷階段結束，進入決策階段。根據懲罰函數z的最小值確定Agent移動策略并選擇火力范圍內的攻擊目標。若無攻擊目標，則不進行選擇；最后，根據決策內容進行相應的移動和攻擊行動；行動階段結束后對敵方Agent數量進行統計，若還存在敵方Agent，則進入下一輪OODA循環，否則結束作戰。

2 基于改進GVT的自適應移動時間窗算法

2.1 自適應移動時間窗算法

因分布式仿真系統的特點，需要使用時間同步技術(即時間管理算法)對系統時間進行同步，保證仿真的時間推進過程正確高效[13]。保守算法雖能夠嚴格確保時間推進正確，但其效率較低，不能適應分布式作戰仿真的需求，因此仿真將采用樂觀算法。

移動時間窗算法(Moving Time Window，MTW)算法是對樂觀算法的樂觀推進程度進行控制的先進樂觀時間管理算法[14-15]。它能夠控制樂觀執行程度的算法，設置可以超過其他邏輯進程仿真時間的上限，通過上限對時間推進程度進行控制，該算法需要計算全局虛擬時間(Global Virtual time，GVT)。對于樂觀算法，當出現遲到消息時，會進行回退操作保證消息處理按照時間戳有序進行。GVT計算就是得到目前仿真過程中未來可能出現回退操作的時間戳下限。

移動時間窗算法的思想主要是對某個仿真進程的仿真時間能夠超過其他仿真進程的仿真時間的上限進行設置，在尚未達到上限時，仿真可樂觀地推進，一旦有進程達到上限便強制阻塞，直到其他所有落后的進程都推進到上限。普通移動時間窗的下限設置為GVT，上限設置為GVT+W，W為自行設定的時間窗值。所有進程不得超過上限，隨著GVT的推進而移動推進。它操作簡單，可有效解決個別進程推進過快而導致的回退現象，但存在時間窗在程序運行過程中無法改變、頻繁進行GVT同步計算的問題。

本文提出的自適應移動時間窗算法不以仿真時間來定義時間窗，而采用事件。由于在仿真執行的過程中，通常無法準確地推算處理每個事件的時間，結合基于OODA環的作戰仿真的特點，它具有明確的作戰周期及事件，因此，算法將結合OODA環的周期采用周期循環方式進行仿真推進，自行調整時間窗大小。仿真模型中每個Agent都有一個單獨的進程，每個進程的推進周期可以表述為：

(1)將一個推進周期定義為OODA環中四個部分中的一個部分，每個部分有一個待處理事件隊列。每個推進周期產生的所有未處理的事件和其時間戳存放在所述部分的事件隊列中。同時，事件隊列中還包含在每個部分仿真開始和結束階段發送的當前部分開始和結束的標志事件及相應的時間戳。

(2)當收到OODA環下一部分開始標志事件時，停止當前進程的推進。

(3)將下一部分開始標志事件和大于下一部分開始標志事件時間戳的事件從當前待處理事件隊列移至下一部分待處理事件隊列中。按照時間戳對當前部分的待處理事件隊列中的事件進行排序。

(4)開始當前邏輯進程OODA環的下一輪推進周期。

對推進周期進行上述設定，可保證各個推進周期之間不會產生延遲消息造成作戰仿真因果關系錯誤從而引發進程回退。自適應移動時間窗算法對事件處理進行了規定，所有進程推進的虛擬時間小于GVT的待處理事件隊列中的事件可以移動至處理事件隊列中進行樂觀的處理，其他待處理隊列中的事件不允許進行處理；所有事件及事件處理產生的過程結果不進行刪除，保證回退操作能夠順利進行；當某一進程收到OODA環一下部分開始標志事件時，將對其他進程發送消息；若其他所有進程都已收到，將啟動GVT計算，對系統進行時間同步。

算法的計算步驟如下：

(1)仿真中的所有進程按照樂觀的方式同步推進，更新各自的推進周期，若有延遲消息，則進行回退；

(2)當某一進程收到下一推進周期開始標志事件時，對所有進程發送消息并回到步驟(1)，若所有進程都收到下一推進周期開始標志事件，進行GVT計算，同步系統時間；

(3)對上一推進周期的事件隊列及過程結果進行刪除，清理內存；

(4)所有仿真進程回到步驟(1)，開始下一輪仿真。

算法偽代碼如下：

2.2 改進GVT算法

常規GVT計算分為同步法和異步法，同步法在發送開始GVT計算的消息后，會等待所有處理器返回接收消息才會開始計算，同時暫停所有處理器正在進行的事件處理，會造成嚴重的阻塞。異步法不存在阻塞問題，允許在計算GVT的同時繼續處理事件。兩種算法都容易產生暫態消息問題。

為了避免在接到GVT計算消息后還存在已經發送但尚未接收的暫態消息未被統計而導致的GVT計算錯誤問題。較為經典的異步GVT算法為Mattern GVT算法，該算法通過對分布式仿真的每個處理器設置“切分點(Cut Point)”來計算GVT。如圖3所示，CP1和CP2為兩個切分點。在CP1和CP2之間為灰色區域，由白色區域發送的消息為白色消息，灰色區域發送的消息為灰色區域。算法將系統中所有的處理器按照邏輯排列成環結構，由系統中的控制器沿環上的順序發送GVT計算消息得到各自處理器，處理器接收該消息的時刻設置為CP1。CP2的設置是為了將所有暫態消息都包括在GVT計算中。當所有處理的CP1確認后，系統控制器將再次沿著環在各個處理器上確定CP2，當發送給當前處理器的白色消息和當前處理接收的白色消息的數值相等時，設置當前時刻為CP2。在CP1、CP2確認完畢后計算所有灰色消息及CP2之后未處理消息的最小時間戳值，該值即為GVT值。

圖3 Mattern GVT算法切點示意圖

該算法存在需要控制器對處理器構建所有處理器的環結構，并逐一確定CP1、CP2兩個切點的值。同時，Mattern GVT算法還需要區分不同消息的顏色，并統計CP2之后所有未處理消息的時間戳值，計算量較大。根據上述兩個缺點，對Mattern GVT算法進行了兩點改進。

(1)本文提出的自適應移動時間窗算法中，CP1的確定由算法的步驟(2)自動確定，并不需要控制器沿環逐一計算。

(2)對GVT的計算方法進行改進，不進行消息顏色判斷及CP2之后所有未處理消息的最小時間戳統計。當所有處理器的兩個切點確定后，若下一個事件的時間戳值大于CP1時，則GVT設置為所有進程中最小的本地虛擬時間。

通過對Mattern GVT算法的改進，可避免控制器對處理器構造環結構，能夠自發地進行切點確認及GVT計算。同時，無需進行消息顏色判斷及統計所有未處理事件的時間戳造成的計算冗余，防止計算阻塞，有效優化GVT計算的復雜度。算法偽代碼如下：

2.3 分布式作戰仿真運行機制

仿真將采用基于改進GVT的自適應移動時間窗算法進行推進，其運行機制如圖4所示。

圖4 分布式作戰仿真的運行機制

仿真中由時間管理控制Agent對時間推進線程的啟動和關閉進行管理和控制；時間管理算法對仿真的步長進行約束；仿真的狀態由不同的線程進行初始化和設置；最終時間管理服務將作用在仿真模型中，保證分布式仿真在運行的過程中，事件因果邏輯及消息收發正確且高效。

3 算法分析

3.1 時間異常問題

對于分布式作戰仿真，尤其重視仿真可能出現的時間異常問題。主要的時間異常有內部延時異常和信息延遲異常兩種。

兩種時間異常都會帶來嚴重的因果關系錯誤問題，本文提出的算法可有效防止該問題的出現，如圖5所示。算法將所有事件存放在OODA四部分的事件隊列中，在上一部分處理完畢后，會觸發GVT計算，同時對待處理事件隊列進行排序，避免出現時間異常及回退。

圖5 本文算法對時間異常的修復示意圖

3.2 內存過載問題

樂觀算法使用時間彎曲邏輯進程(TWLP)并構成時間彎曲系統，TWLP與串行仿真的區別在于，當前邏輯進程(LP)的事件可以是其他LP調度產生的，同時，處理完畢的事件不進行立即刪除操作，會存在暫時隊列中。經典樂觀算法能夠對保守算法的效率進行改善，但會隨著仿真的推進帶來內存占用過量及多級回退問題。

本文提出的算法只需要保存上一部分的事件處理數據，在GVT計算過后，將對之前所有處理事件產生的數據進行清除，釋放內存，開始新一輪推進周期，有效解決樂觀算法帶來的內存過載問題。

4 算法分析

對作戰仿真模型的參數進行設置用于測試算法性能。模型的戰場由二維離散點構成，戰場大小為100×100。戰場中分布兩種作戰Agent，分為紅軍和藍軍，每個Agent代表一個兵力，數量各100個。當Agent死亡，在本輪仿真中將永久退出戰場。雙方觀察范圍均為15，運動范圍為1，火力范圍為5，戰斗閾值為1，特征權值為w→=(0.25，0.25，0.25，0.25)。仿真運行500步并重復實驗100次。仿真基于分布式Agent開發技術框架JADE平臺，用Java語言編寫。每個Agent為一個單獨進程，并被劃分在3個JADE容器中，模擬3臺計算機進行分布式仿真。對100次仿真結果進行平均，得到的存活Agent數量趨勢如圖6所示。

圖6 仿真過程中存活Agent數量趨勢圖

由于紅藍軍設置的參數基本相同，其存活Agent數量趨勢大致相同，在仿真運行至300步時人數趨于穩定，雙方不再交戰。

分別使用4種時間管理算法對模型進行仿真測試，4種算法分別為本文提出的算法、普通移動時間窗算法、樂觀算法及保守算法，實驗結果如圖7所示。

圖7 4種算法實驗結果對比圖

本文提出的自適應時間窗管理算法在基于OODA環的仿真中運行效果最好，所需時間最短。該算法與其他3種算法相比運行時間分別提高了7%、11%和16%。

5 結論

并行分布式仿真能夠提高仿真的運行效率，其重難點在于時間管理算法的性能。針對OODA環作戰仿真的特點，本文提出一種自適應移動時間窗算法，仿真結果優于其他經典時間管理算法。算法無需修改模型內部結構，緊貼模型邏輯流程，自適應調整時間窗大?。粚ν七M周期進行設定，避免并行仿真的多級回退及死鎖問題，同時可定期精準清除內存；改進GVT計算算法，無需頻繁進行GVT同步并能自發確定切點，改善GVT計算復雜度。算法可為并行作戰仿真的研究提供支持，對未來大規模集群仿真作戰提供新的思路和參考。