基于改进混合状态保存法的作战仿真回退研究

王伟 胡丹

(1.91550部队,辽宁大连 116023;2.91180部队,辽宁大连 116041)

0 引言

作战仿真是运用计算机仿真技术对作战进程进行仿真推演,用于辅助决策者科学预判和评估作战计划的可行性和优劣性,从而选择合适的作战计划。为了使决策者能够根据仿真实体的状态实时对作战仿真进程进行调整,本文提出调整式回退机制,通过仿真进程的回退,改变调整作战计划后需重新从初始状态开始仿真的做法,达到调整效果快速呈现的目的。

1 调整式回退的特点

在计算机领域中,回退一般用于容错系统中与故障处理有关的操作。目前仿真领域的回退概念一般是指:当并行离散事件仿真(PDES)的时间同步管理采用乐观时间管理机制时[1],因为乐观机制并非严格依照事件发生的时间顺序处理事件,所以当事件顺序违反了因果关系时,需要撤销那些错误执行的事件并恢复系统状态[2]。本文所提出的调整式回退机制不同于以上的回退机制。为了更清晰的说明调整式回退的特点,将其与PDES的回退机制做比较,如表1所示。

1.1 回退目的

PDES回退的目的是因为乐观时间管理机制会发生错误,系统为了保证因果时序的正确性而使用回退机制纠正因果顺序;调整式回退的目的是为了满足决策者调整计划的需求,使仿真系统返回之前的某一事件,更改此处事件的系统状态后继续仿真并观察效果。

1.2 回退方式

PDES回退是仿真系统自动识别出时序错误后,由系统自动执行回退操作以消除错误影响。这一过程在后台运行,并不会以显性的方式展现出来,是一种内部处理机制,且不会让参与仿真的人员察觉到回退的发生。调整式回退是由人主动进行的回退操作,它的控制权掌握在决策者手中。什么时机回退、回退到什么位置都由决策者决定,通过交互式操作达到仿真回退的目的。

1.3 回退事件跨度

事件跨度是指系统当前事件与所要回退到的事件之间相隔的事件数。PDES中,一般采用效率较高的乐观算法进行逻辑进程间的时间同步。乐观算法并不严格按照时间顺序处理事件,接受到因延迟等原因造成的事件掉队消息后,需要进行回退。为了减少系统运行开销,PDES一般会采取措施对乐观程度进行限制,缩小回退的事件跨度[3],所以正常情况下事件跨度被限制在一定范围内。而调整式回退由决策者根据因果分析及自身想法而决定,事件跨度不是其考虑的因素,在事件跨度的选择上没有限制,理论上最大可以从最后一个事件回退至第一个事件,因此调整式回退的事件跨度没有限制。

表1 回退机制的比较Tab.1 Comparison of return mechanisms

通过以上分析可以看出,调整式回退和目前仿真领域的回退概念在回退目的、方式、事件跨度等方面存在较大差异。要完成调整式回退,主要对两个方面进行操作:一是恢复系统之前的状态变量;二是事件的反向恢复。这两方面的操作,可以借鉴PDES回退的相关概念,但具体的实现方法因两者差异而不同,下面对调整式回退的方法进行研究。

2 基于改进混合状态保存的回退算法

2.1 PDES中的状态保存法

要想恢复到之前的状态,只有将之前的状态变量保存起来,才具备恢复的基础。对于PDES来说,状态保存法一般有复制状态保存法(Copy State Saving,CSS)、增值状态保存法(Incremental State Saving,ISS)和混合状态保存法(Multiplexed State Saving,MSS)[4]。CSS是在处置事件前,保存所有的状态变量,在恢复时一次性替换所有状态。这种方法适用于处理事件时状态发生大量改变,不足之处是每个事件在处置之前需要保存所有状态,将消耗较多的空间。ISS是指在处理事件时,只对状态变量产生变化的值进行保留。需要恢复时,按照事件序列的相反顺序依次恢复状态变量,因为回退时每个改变的状态都会被恢复,所以一个状态可能会被多次恢复。ISS的空间和时间消耗只与发生的事件相关,与状态的个数无关。文献[5]的研究表明:如果在事件处理后大部分的状态被改变,则使用CSS会表现出较高效率;如果只有小部分状态被改变,则ISS具有较高效率。MSS是指将CSS和ISS两种方法综合利用。每隔一定数量的事件,就将状态全部保存起来,相当于CSS;而在两次CSS之间,使用ISS保留变化的状态变量。当需要回退时,先回到距离回退点最近的CSS点,在恢复状态后利用ISS最终恢复到回退点。MSS的空间消耗没有CSS大;在回退距离较长时,时间消耗也没有ISS多,是一种折中的方法。

2.2 MSS算法的改进

在调整式回退的操作中,因为回退距离不受限制,所以回退距离可能会较长。综合考虑空间消耗和时间消耗,本文选择MSS进行状态保存。但MSS存在以下问题:MSS是以固定事件间隔将状态全部保存,两事件之间使用ISS法存储变化的状态。在使用CSS时,如果改变的状态占全部状态的比例很少,则CSS显得浪费;而在CSS之间使用ISS时,如果改变的状态占全部状态的比例很大,则ISS的消耗会比较大,无法体现ISS的优势。

图1 θe、Ne、Nr关系图Fig.1 θe、Ne、Nr diagram

如果能够根据事件处理中,改变的状态占全部状态的比例大小决定采用何种方法,则可以更好的发挥各自方法的优势。本文通过对MSS方法进行改进,构建了适用于调整式回退的状态保存法。假设S为处置单个事件时,所有的状态个数,同时假设所有状态大小一致。ts是平均保存一个状态所消耗的时间,tr为平均恢复一个状态所消耗的时间,θ为处理事件时改变的状态占所有状态的平均比例。Ne为已处理的事件个数。Nr为回退的事件跨度。Tc为CSS一次回退总时间消耗,可表示为:

NetsS为保存状态的时间消耗,trS为恢复时的时间消耗。因为CSS是所有状态都保存,所以恢复时与回退事件跨度无关。

Ti为ISS一次回退的总时间消耗,表示为:

NetsθS为ISS保存Ne个事件的时间消耗,NrtrθS为回退Nr个事件的时间消耗。

在Tc=Ti的情况下,CSS和ISS的时间消耗相同。令θe表示此时的θ。则

当θ＞θe,ISS的时间消耗将大于CSS。ts、tr在具体环境下是常量,所以随着回退事件跨度Nr的增加,θe将减小。

式3表示时间消耗相同时θe的取值。其中回退事件跨度Nr的取值由人决定,是式中最主要的变量,Nr取值范围为[1,Ne-1],则θe的取值范围可表示为:

根据文献[6],令ts=3.2×10-2ms,tr=6.35×10-2ms,Ne=30(已处理30个事件)。则θe、Ne、Nr之间的关系,如图1所示。

由图2可以看出:相同回退跨度Nr(不包括1)下,随着Ne增大,θe也增大;相同Ne下,回退跨度Nr越大,θe越小。当Ne→∞时,式4可表示为:

由于回退跨度Nr无法确定具体数值,用Nr的平均数表示可能的回退跨度,则对应的θe平均数如图2所示。

可以根据已处理事件的个数确定当前的θe值。状态改变比例大于等于θe时,采用CSS保存状态;改变比例小于θe时,采用ISS保存状态。使用改进后的MSS方法,可以根据改变状态占全部状态的比例,灵活选择ISS或CSS方法,避免了MSS采用间隔固定时出现的问题。

3 基于事件关联的事件表回退策略

仿真回退不仅涉及系统状态的恢复,还涉及到仿真事件表的恢复。在PDES系统中,事件回退是利用反消息实现的。当事件的逻辑顺序出现错误时,利用输出反消息来回退事件。调整式仿真的回退并不是由事件的逻辑错误造成的,所以回退不能采用反消息方法。为了对事件进行回退,建立两个事件表:一个是未来事件表,用来推进仿真进程的发展;另一个是已发生事件表,用于记录已经发生的事件,便于事件回退。同时利用事件之间调度信息表示事件之间的关联。仿真过程中,从未来事件表中取出最先发生的事件,事件处理完毕后放入已发生事件表。当进行回退处理时,进行以下步骤:

图2 θe平均值Fig.2 Average

图3 事件表回退示意图Fig.3 Event Table Return Diagram

Step1:选定已发生的事件Er为要回退到的事件;

Step2:将未来事件表中每个事件的调度事件与已发生事件表中Er之后发生的事件逐一做比较,如果相同,则将此事件从未来事件表中删除;否则不做改变。如没有调度事件信息,此事件也不做改变;

Step3:从已发生事件表中最后发生的事件开始,将其调度事件与其之前发生的事件做比较(到Er之后的事件为止)。如相同,则从已发生事件表中删除;如不同,则从已发生事件表删除时,加入未来事件表并按时间排序。当没有调度事件信息时,此事件从已发生事件表删除并按时间顺序插入未来事件表,如图3所示。

图3中用有向线段表示某段过程中仿真事件间的触发关系。t1时刻,Er事件发生,触发了Eb事件,Ea事件已存在于未来事件表。t2时,Ea发生,并产生了Ec事件。t3时刻Ec发生并产生事件Ed。设当前时间为t3,要回退至t1时刻。根据上文事件回退的步骤,首先判断未来事件表中的事件是否保留,Eb的触发事件是Er,并非Er之后的事件,所以保留。Ed的触发事件为Ec,Ec位于已发生事件表中Er之后,所以将Ed从未来事件表中删除。然后处理已发生事件表,从最后的Ec事件开始,Ec的触发事件为Ea,因为Ea位于Er之后,所以将Ec删除。Ea没有触发事件,所以将Ea从已发生事件表中删除,并插入未来事件表排序。至此,事件回退完毕。

4 结语

为了实现在作战仿真系统中根据仿真状态快速调整仿真进程的目的,本文设计了调整式回退机制,提出了基于改进MSS的状态保存算法和基于事件关联的事件表回退方式,为作战仿真回退机制的实现提供了理论支持。