马 也 ，常天庆 ，范文慧 ，李 婕 ，孔德鹏

(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环理论指出，军事行动基本上是由一系列决策过程或循环组成的。基础OODA环主要包括侦察(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环作战仿真的特点，本文提出一种自适应移动时间窗算法，仿真结果优于其他经典时间管理算法。算法无需修改模型内部结构，紧贴模型逻辑流程，自适应调整时间窗大小；对推进周期进行设定，避免并行仿真的多级回退及死锁问题，同时可定期精准清除内存；改进GVT计算算法，无需频繁进行GVT同步并能自发确定切点，改善GVT计算复杂度。算法可为并行作战仿真的研究提供支持，对未来大规模集群仿真作战提供新的思路和参考。