分布式武器目标分配中的实时截止期分配

孙亚东 邢昌风 吴 玲 卢发兴

(海军工程大学电子工程学院，武汉430033)

多平台协同作战的背景下，目标在其航路上可能需要由分布于不同平台的多个武器进行协同攻击.由于武器射界的影响，完成对目标的协同拦截要在一定的窗口时间内完成.为了保证整体拦截任务的实时性，可用的对目标拦截时间必须合理地分配给实施拦截的各个武器系统.本文将实时系统中的截止期分配技术引入多武器协同拦截目标问题中，通过分析任务的特点和时间属性，建立任务调度模型和截止期分配方法，确定各个拦截子任务的最终完成时间.建立了截止期分配方法的评价指标，通过仿真试验比较分析了不同分配方法的有效性.本文的方法可为分布式实时系统中的任务协作实时性研究提供参考.

1 截止期分配问题

在引入截止期分配概念之前，首先介绍各类实时任务的概念和相关模型.

1.1 基本任务模型

实时系统中的任务分为两种:本地任务和全局任务.本地任务是指在一个节点且仅在一个节点上执行的任务，全局任务是指需要在多个节点上完成的任务.全局任务又是由一系列在不同节点上执行的子任务组成的，根据全局任务和子任务的关系，一般的全局任务在结构上可以由“串行子任务”和“并行子任务”组成.用符号T=［T1，T2，…，Tn］表示全局任务T由n个串行执行的子任务 T1，T2，…，Tn组成，子任务 Ti(i＞1)不能在Ti－1之前执行.用 T=［T1‖T2‖…‖Tn］表示全局任务T包含n个并行执行的子任务，只有在所有的子任务都结束了，全局任务T才算结束［1］.图1所示是一个具有串并行结构的全局任务示意图.

图1 全局任务的串/并行结构示意图

无论是全局任务还是子任务，任务T都可用一些时间属性［1］来描述，如:①到达时间ar(T);②截止时间dl(T);③任务预计执行时间pex(T);④任务实际执行时间ex(T)，ex(T)的值一般是未知的，但可利用它的估计值pex(T)近似;⑤松弛时间sl(T)，即任务的截止时间与任务的结束时间或预期结束时间之间的差值.这些属性间的关系为:dl(T)=ar(T)+ex(T)+sl(T).另外任务T的时间约束的强弱可以用任务的松弛时间与执行时间之比来描述，将这一比值定义为任务 T的灵活度fl(T)，即fl(T)=sl(T)/ex(T).显然，灵活度越大，时间约束越弱.

1.2 截止期及其分配策略

任何一个实时任务都将受到一定时间期限的约束，这个时间期限称为任务的截止期.在分布式实时条件下，一个全局任务要在给定的开始和结束时间内进行，这个给定的时间段称为端到端截止期(EED，End-to-End Deadline).当全局任务被划分为多个子任务在不同节点上执行时，全局任务的截止期要合理地转化为各子任务的截止期，即子任务截止期分配(SDA，Subtask Deadline Assignment)，简称截止期分配.截止期分配问题自提出以来不断得到深入的研究，多种不同的截止期分配策略和方法先后被提出［1－3］，并广泛应用在复杂分布式实时系统如实时交易［4］和实时数据库［5］等具体领域.

根据系统的串-并型结构，可以提出若干对子任务进行截止期分配的规则.对串行子任务的截止期分配策略如［1］:①最大截止期法(UD，Ultimate Deadline)，即直接把全局任务的截止期设置为子任务的截止期;②有效截止期法(ED，Effective Deadline)，如果子任务执行时间的估计值有效，子任务Ti的截止期就等于全局任务T的截止期减去Ti之后所有子任务的总预计执行时间;③等松弛时间法(EQS，Equal Slack)，即在剩下的子任务中等分剩余松弛时间;④等灵活度法(EQF，Equal Flexibility)，指对各子任务按照相同灵活度的原则分配截止期;⑤比例负载法(PLO，Proportional Load)，即根据节点负载大小来分配剩余松弛时间，负载越大，分配松弛时间也越多.

并行子任务的截止期分配相对较简单，除最大截止期法外，还可采用启发式算法，如DIV-x法［1］，其中x是可调整的参数.DIV-x策略是把全局任务的总时间简单地除以子任务数的x倍.

当一个全局任务同时具有串行和并行子任务，则应组合使用两种截止期分配策略.

2 协同拦截中的截止期分配方法

2.1 问题描述

本文以舰艇编队协同防空为例建立模型.从任务属性上看，如果一批目标仅由单个武器实施拦截，此任务为本地任务;如果一批目标需要由两座以上的武器交替拦截，此任务为全局任务，每座武器对目标的拦截都是它的一个子任务.

为了分析这一过程，假定一批来袭目标由M1和M2两个目标组成，根据火力分配方案，有三座不同舰艇平台上的武器W1，W2和W3协同拦截为例，如图2所示.

三座武器的发射区分别设为D1，D2和D3，M1到达D1，D2的远界和近界的时刻按时间顺序依次为 t1，t2，t3和 t4，M2到达 D2，D3的远界和近界的时刻按时间顺序依次为 t5，t6，t7和 t8.武器对M1和M2的拦截可看作是两个全局任务，记为T1和T2.其开始时间分别为两个目标到达武器发射远界的时间t1和t5，任务截止期分别为两个目标到达武器发射近界的时间t4和t8.

假定拦截采取“射-看-射”的原则，即只有在先发射的武器结束射击并通过观测确定目标未毁伤后，第二座武器才射击，因此两个全局任务都是由串行的子任务组成.以全局任务T1为例，它由W1和W2分别对目标拦截两个子任务串联组成，分别记为ST1和ST2.每个子任务的执行都包括2个阶段:解算射击诸元和实施发射;而ST2的执行是在ST1发射之后开始的，包括3个阶段:射后观效、解算射击诸元和实施发射［6］.显然，子任务的实际执行时间事先不知道，因此在截止期的分配前要对子任务的执行时间进行估计，即得到预期执行时间pex(ST)，预期执行时间要尽可能地接近于实际执行时间ex(ST).

2.2 任务调度模型

本文建立的分布式实时任务调度模型是由代表不同处理模块的若干节点组成，这些处理模块主要有武器处理节点和主调度程序.图3所示为任务调度模型结构图.

图3 任务调度模型结构图

主调度程序的主要工作是根据全局任务和其子任务的相关信息，按照既定的分配策略对全局任务的端到端截止期进行分配，相当于给每个子任务贴上一个截止期“标签”，并把截止期信息发送到相应的武器处理节点上.

武器处理节点是对应于每个武器设置的，每个处理节点上都有一个本地调度程序，其主要工作是对节点上的本地任务和分配到此节点上的子任务按照一定的原则进行实时调度.本文采用最早截止期优先(EDF，Earliest-Deadline-First)的原则，即所有在此节点上处理的任务中，截止期最早的任务优先得到处理.另外对于已经延迟的子任务，为了不影响后续子任务的执行，减少不必要的浪费，本地调度程序将对其做放弃处理.

2.3 截止期分配方法

本文主要解决串行子任务的静态截止期分配问题.分布式武器对目标协同拦截中的截止期分配问题与以往文献中研究的问题主要有以下两点不同:①全局任务的结构不同，不同全局任务的子任务数量和执行的节点都不同;②子任务的截止期不仅仅取决于截止期分配策略，而且受武器射界的影响.当目标突破武器的发射近界时，此武器就不能再进行射击了，若继续进行跟踪滤波和射击诸元的解算就无任何意义了.

设一串行全局任务:T=［ST1，ST1，…，STn］，任务的截止期为dl(T)，且全局任务的执行时间不会超过其端到端截止期.

1)射击近界法(MFR，Minimum Fire Range).

这是最直观和简便的分配策略，适用于对任务的执行时间一无所知的情况，与最大截止期法相似，即直接以目标到达武器射击近界的时间作为当前子任务的截止期，如下式所示:

其中，t(i)mr表示第i个任务中目标到达武器射击近界的时间.

若以图2所示的武器W1和W2拦截目标M1为例，令 ar(ST1)=t1，ar(ST2)=dl(ST1)，dl(ST2)=t4，假定 pex(ST1)= Δt1，pex(ST2)= Δt2，则用射击近界法分配的子任务截止期为

2)等灵活度法.

按照使每个子任务拥有相同灵活度的原则，对全局任务的剩余松弛时间进行分配，子任务截止期公式为［1］

在本例中子任务的截止期为

3)比例负载法.

根据处理节点上的子任务数量进行分配，子任务多的节点上需要排队的时间就越长，分配的松弛时间也就越多，截止期计算公式为

其中，load(STi)表示处理子任务i的节点上的负载数量.

本例中的子任务截止期为

3 仿真分析

3.1 仿真模型

设共有n座防御武器，即n个处理节点，用集合{w1，w2，…，wn}表示.目标的数量为 m，用 Mk={wi，…，wj}(k=1，2，…，m)表示武器 wi，…，wj分配给了目标Mk.规定一个全局任务最多只能有STmax个子任务，即Mk的集合最多有STmax个元素;同时定义一个处理节点的容量为v，即一个节点最多处理v个子任务，意味着一个武器最多对v个目标实施拦截.

目标依据参数为μ的泊松流产生，每次试验总共至少要产生1 000个任务.本地任务在总任务中所占的比例称为本地负载，用local_load表示.在本试验的基本设置中，本地负载为20%，全局任务中子任务数量为2和3的各占40%.

火力分配完毕后，任务都已产生，这时要定义任务的时间属性.设本地任务和子任务的执行时间服从［λ，2λ］个时间单位内的均匀分布;全局任务的到达时间一样;端到端截止期随子任务个数不同而变化，具体为:包含k个子任务的全局任务端到端截止期 EED服从［2kλ，2kλ+λ］个时间单位内的均匀分布;目标到达第i个武器射击近界的时间服从均值为EED×i/k的正态分布.同时假定对子任务执行时间的预测是绝对准确的，即pex(ST)=ex(ST).本仿真试验中的基本设置如表1所示.

表1 基本设置

3.2 仿真结果

本仿真试验利用任务的错失率作为主要评判指标，其中又把错失率分为3种分别进行分析:

1)本地任务错失率(LMD，Local Missed Deadline)，表示在所有的本地任务中，超过截止期的本地任务所占比例.

2)全局任务错失率(GMD，Global Missed Deadline)，表示在所有的全局任务中，错失的全局任务所占比例.错失的全局任务是指它的所有子任务都超出截止期，此时拦截任务失败.

3)总任务错失率(OMD，Overall Missed Deadline)，表示在所有产生的本地任务和全局任务中，错失的任务所占比例.经过试验，各截止期分配方法在不同目标数量下的任务错失率如表2所示.

表2 三种截止期分配方法在不同目标数量下的任务错失率

为便于对各种方法进行比较，将子任务错失率和全局任务错失率的直方图画出，见图4.

为了研究本地任务和全局任务所占比重的大小对总任务错失率的影响，需要做进一步的试验.为此，以四个目标为例，令本地负载从10%到80%进行变化，得出在不同截止期分配方法下的总任务错失率，如图5所示.

3.3 仿真结果分析

由图4a可知，在本地任务中，射击近界法的子任务错失率最低，等灵活度法的子任务错失率最高，比例负载法介于两者之间，但随着目标数量的增加，三者的差距基本保持不变.

由图4b可知，在全局任务中，射击近界法的错失率最高，而且随着目标数量的增加，与其他两者的差距也有扩大的趋势.比例负载法的错失率始终小于其他两种分配方法，等灵活度法接近于比例负载法，介于其他两者之间.

图4 不同截止期分配方法的任务错失率直方图

图5 总任务错失率随本地负载变化直方图

由图4c可知，比例负载法在总任务的错失率方面依然优于其他两种，而且随着目标数量的增加，与其他两者的差距也有扩大的趋势.

由图5可知，随着本地负载增加，射击近界法的劣势逐渐减弱，并最终占据略微的优势.而且总任务错失率会随着本地负载的增加而升高.

综上可知，对于全局任务的调度，比例负载法有一定的优势，而由于射击近界法不考虑子任务的属性和节点上的负载情况，只是简单地以武器的射击近界作为子任务截止期，因此对于全局任务的调度错失率比较高.对于本地任务的调度，由于比例负载法和等灵活度法都对本地任务有所“排挤”，因此射击近界法的表现要优于二者.在总的任务错失率方面，各方法的表现与在全局任务中的表现相似，但差距有所减小，原因是在全局任务中等灵活度法的优势要大于其在本地任务中的劣势，而且在总的任务数量中全局任务所占比例较大.

因此，对于子任务截止期的分配:

1)若难以预测子任务的执行时间，或本地负载较高，可以采取射击近界法进行分配.

2)若子任务执行时间有较准确的预测或本地负载不高，则应采取比例负载法进行分配.

4 结论

试验结果证明，不同截止期分配方法对任务错失率有很大的影响，因此在分布式武器目标分配问题中给全局任务的子任务分配合理的截止期是有必要的.

本文假定武器目标的分配早于截止期的分配，而当武器目标的分配需要其截止期信息以及动态环境中任务的截止期类型发生变化时，应如何对截止期进行分配，还需做进一步的研究.

References)

［1］Kao B，Garcia-Molina H.Deadline assignment in a distributed soft real-time system［J］.IEEE Transaction on Parallel and Distributed Systems，1997，8(12):1268－1274

［2］Jan Jonsson，Kang G Shin.Robust adaptive metrics for deadline assignment in distributed hard real-time systems［J］.Real-Time Systems，2002，23(3):239－271

［3］Wang Zhigang，Wang Wei，Liu Quanli.An improved feedback deadline assignment algorithm for real-time control tasks scheduling［C］//Proceedings of the 6th World Congress on Intelligent Control and Automation.Dalian，China:［s.n.］，2006:6724－6727

［4］Pellizzoni R，Lipari G.Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling［J］.Journal of Computer and System Sciences，2007，73(2):186－206

［5］Zhou Yan，Kang Kyoung-Don.Deadline assignment and tardiness control for real-time data services［C］//22ndEuromicro Conference on Real-Time Systems.Washington，DC，USA:IEEE Computer Society，2010:100－109

［6］吴玲，卢发兴.WTA问题的截止期定义及Anytime算法分析［J］.武汉理工大学学报，2010，32(6):140－143

Wu Ling，Lu Faxing.Analysis ofdeadlines and Anytime algorithms for weapon-target allocation problem［J］.Journal of Wuhan University of Technology，2010，32(6):140 －143(in Chinese)