基于CPN的TDRS操作规划建模与仿真*

刘传辉

（绵阳职业技术学院，四川 绵阳 621000）

基于CPN的TDRS操作规划建模与仿真*

刘传辉

（绵阳职业技术学院，四川 绵阳 621000）

以中继卫星（Racking and Data Relay Satellite，TDRS）为研究对象，以有色Petri网（Colored Petri Net，CPN）为数学工具，根据自顶向下的原则和层次化建模思想，提出一种基于CPN的TDRS操作规划模型，该模型分为顶层模型、控制模型、前向链路数据接收任务与发送任务的操作规划模型和返向链路数据接收任务与发送任务的操作规划模型，有效地描述了TDRS的动态行为特性。最后，通过仿真实验得到了TDRS操作规划方案，验证了所建模型的有效性。与PDDL模型比较分析表明：所建模型可以有效引入TDRS的领域知识，能够有效提高求解效率。所建模型可以为TDRS操作规划方案的制定提供理论参考。

TDRS，操作规划，有色Petri网，PDDL

0 引言

中继卫星（Rracking and Data Relay Satellite，TDRS）操作规划问题本质上是一类融合了各种资源和时间等约束的人工智能规划调度问题。其主要目标是在一定时间范围内，根据TDRS的任务需求、星载天线当前的状态和TDRS可以采用的行动集合，在满足资源和时间等约束条件下，通过有效的推理，选择一个行动序列集合形成规划方案，以完成特定的TDRS任务。

目前，TDRS规划建模研究越来越受到各个航天大国的高度重视，国内外众多学者开展了相关研究工作［1-4］，但是所建模型大多偏重TDRS任务调度方面，且模型都是基于一定的简化假设，没有综合考虑任务需求和各种约束条件。

Petri网［5］是一种性能良好的图形化建模工具，得到了航天领域规划建模研究领域的关注与高度重视［6-8］。有色Petri网［9］（Colored Petri Net，CPN）是一种可以用于层次化建模的高级Petri网，特别适用于描述TDRS的各种约束条件和动态行为特性。本文采用CPN作为数学工具建立TDRS的操作规划模型，通过实例研究验证了所建模型的有效性，并与经典规划问题中规划领域定义语言PDDL（Planning Domain Definition Language，PDDL）［11-12］模型比较分析其求解效率的优越性。

1 模型要素分析

按照不同的工作模式［4］，TDRS可以分为测控模式与数据传输模式，分别对应于TDRS的前向链路任务和返向链路任务。在TDRS系统中，数据流按照“地面站→TDRS→用户星”的顺序传播，称为前向链路；相反，按照“用户星→TDRS→地面站”的顺序传播，称为返向链路。

TDRS操作规划问题模型要素有：

任务类型：包括前向链路任务和返向链路任务。其中，前向链路任务分为前向链路数据发送任务和接收子任务;而返向链路任务分为返向链路数据发送任务和接收子任务。

资源类型：主要包括原子型资源和连续型资源。其中，原子型资源主要是指星载天线，包括星地链路天线和星间链路天线；连续型资源主要包括电源和存储器等。

约束类型：主要包括3类约束，其中：资源约束主要包括电源电量（Power Capacity，PC）和存储器容量（Memory Capacity，MC）：星载天线的各种操作都要消耗PC；执行数据发送任务将减少MC，执行数据接收任务将增加MC。操作执行时间约束是指TDRS工作过程中，每个操作都是需要一定时间来完成的。时间窗口约束是指TDRS的4种类型任务必须在其与用户星或地面站之间有可见时间窗口时才能执行并完成。

2 CPN的形式化定义

CPN的形式化定义可以参见文献［6］。在TDRS操作规划建模过程中，用不同的颜色集可以描述TDRS中的资源和工作状态；用位置描述TDRS信息状态和状态的驻留等；用变迁描述星载天线的各种操作和条件的判断等；用标识的流动来模拟TDRS的动态行为。

3 TDRS操作规划建模

根据自顶向下的原则和层次化建模思想，分别建立了TDRS操作规划的顶层模型、控制模型、前向链路数据发送任务的操作规划模型和接收任务的操作规划模型以及返向链路数据发送任务的操作规划模型和接收任务的操作规划模型。

3.1 TDRS操作规划顶层模型

图1 TDRS操作规划顶层模型

如图1所示为TDRS操作规划的顶层模型，用以描述TDRS各种类型任务之间的层次关系。其中，替代变迁CTL表示TDRS操作规划控制模型；替代变迁FI_rt表示前向链路数据接收任务的操作规划模型；替代变迁FI_st表示前向链路数据发送任务的操作规划模型；替代变迁RI_rt表示返向链路数据接收任务的操作规划模型；替代变迁RI_st表示返向链路数据发送任务的操作规划模型；融合位置Ii（1≤i≤4）和Oi（1≤i≤4）表示各个模块模型之间的输入/出接口。

3.2 TDRS操作规划控制模型

图2 TDRS操作规划控制模型

如图2所示为TDRS操作规划控制模型，用以描述TDRS对4种类型任务的操作规划控制过程。其中：位置Pts表示各种任务集合；位置Pws表示时间窗口集合，包括TDRS与地面站之间的窗口子集合和TDRS与用户星之间的时间窗口子集合；位置Ps表示按照任务优先级和时间窗口约束冲突进行排序后的任务集合；位置Pi表示需要当前执行的任务；位置P表示任务执行权；位置Pfrn（Pfsn）表示有前向链路数据接收任务（发送任务）需要执行；位置Pfri（Pfsi）表示前向链路数据接收任务（发送任务）规划模型正在执行规划；位置Prrn（Prsn）表示有返向链路数据接收任务（发送任务）需要执行；位置Prri（Prsi）表示返向链路数据接收任务（发送任务）规划模型正在执行规划。变迁Ts表示根据任务集合优先级和时间窗口约束对任务进行排序，同时当任务间冲突时，删除低优先级任务；变迁Tti表示执行的当前任务；变迁Tfrj（Tfsj）表示判断当前任务是否前向链路数据接收任务（发送任务）；变迁Tfr（Tfs）表示执行前向链路数据接收任务（发送任务）的规划；变迁Tfrc（Tfsc）表示当前前向链路数据接收任务（发送任务）规划执行结束；变迁Trrj（Trsj）表示判断当前任务是否返向链路数据接收任务（发送任务）；变迁Trr（Trs）表示执行返向链路数据接收任务（发送任务）的规划；变迁Trrc（Trsc）表示当前返向链路数据接收任务（发送任务）规划执行结束。

TDRS操作规划控制模型工作过程：初始时刻，位置Pws、位置Pts和位置P含有标识，只有变迁Ts触发，位置Ps获得1个标识，表明模型以位置Pws中的时间窗口集合和位置Pts中的任务集合为依据对任务进行了排序，当任务间冲突时，低优先级任务将被删除。接着变迁Tti触发，则位置Pi获得1个标识，表明当前存在一个任务需要执行。如果当前任务为前向链路数据接收任务，则变迁Tfrj触发，则位置Pfrn获得1个标识，表明有前向链路数据接收任务需要执行规划。变迁Tfr触发，位置I1获得1个标识，表明执行前向链路数据接收任务规划，同时位置Pfri获得1个标识，表明系统处于前向链路数据接收任务的规划状态，当执行完当前前向链路数据接收任务规划后，位置O1获得1个标识，变迁Tfrc触发，位置P重新获得1个标记，表明模型可以执行下一个任务的规划。

3.3 前向链路数据接收任务的操作规划模型

图3 前向链路数据接收任务的操作规划模型

如图3所示为前向链路数据接收任务模型，用以描述TDRS前向链路数据接收任务的操作规划过程。其中，位置Pfro表示星地接收天线处于上电开机状态；位置Pfrc表示星地接收天线处于数据接收完成状态。变迁Tfro表示星地接收天线上电开机；变迁Tfrj1用于描述系统判断星地接收天线是否处于上电开机状态；变迁Tfri表示如果星载PC满足星地接收天线接收数据的电量需求，则星地接收天线接收数据；变迁Tfrn用于描述假设当星载PC少于星地接收天线接收数据的电量需求时，退出相应任务的操作规划；变迁Tfrj2表示如果在当前操作规划的时间段内还有前向链路数据接收任务，保持星地接收天线上电开机；变迁Tfrf表示如果在当前操作规划的时间段内没有前向链路数据接收任务，则星地接收天线断电关机。

前向链路数据接收任务的操作规划模型工作过程：模型初始化后，位置I1含有1个标识，表明有一个前向链路数据接收任务需要执行操作规划。假设当前星地接收天线处于上电开机状态，如果此时星载PC满足星地接收天线接收数据所需电量，则变迁Tfri触发，同时位置Pfrc获得1个标识，表示星地接收天线接收数据完毕，反之则变迁Tfrn触发，退出该任务的操作规划。如果在当前规划时间段内还有前向链路数据接收任务，则变迁Tfrj2触发，执行下一个任务；如果没有前向链路数据接收任务，变迁Tfrf触发，星地接收天线断电关机，返回顶层模型。

3.4 前向链路数据发送任务的操作规划模型

图4 前向链路数据发送任务的操作规划模型

如图4所示为前向链路数据发送任务的操作规划模型，用以描述TDRS前向链路数据发送任务的操作规划过程。其中，位置Pfso表示星间发送天线处于上电开机状态；位置Pfst表示星间发送天线处于完成转向状态；位置Pfsa表示星间发送天线处于完成捕获跟踪用户星状态；位置Pfss表示星间发送天线处于完成对用户星进行数据发送完成状态。变迁Tfso表示星间发送天线上电开机；变迁Tfsj1用于描述系统判断星间发送天线是否处于上电开机状态；变迁Tfst用于描述假设当前星载PC大于星间发送天线转向瞄准的所需电量时，星间发送天线执行转向瞄准；变迁Tfsn用于描述假设当前星载PC小于星间发送天线转向瞄准的所需电量时，退出相应任务的操作规划；变迁Tfsa用于描述假设当星载PC大于或等于星间发送天线对用户星进行捕获跟踪的电量需求时，星间发送天线对用户星进行捕获跟踪；变迁Tfsan用于描述假如当前PC电量小于星间发送天线对用户星进行捕获跟踪的所需电量时，退出相应任务的操作规划；变迁Tfss表示如果星载PC满足星间发送天线执行数据发送的电量需求，则星间发送天线执行数据发送；变迁Tfssn表示如果星载PC不能满足星间发送天线执行数据发送的电量需求，则退出该任务的操作规划；变迁Tfsj2表示如果在当前规划时间段内还有前向链路数据发送任务，保持星间发送天线上电开机；变迁Tfsf表示如果在当前规划时间段内没有前向链路数据发送任务，则星间发送天线断电关机。

前向链路数据发送任务的操作规划模型工作过程：模型初始化后，位置I2含有1个标识，表明有一个前向链路数据发送任务需要执行操作规划。假设当前星间发送天线处于上电开机状态，如果此时星载PC满足星间发送天线转向瞄准所需电量，则变迁Tfst触发，位置Pfst获得1个标识，表示星间发送天线已经转向瞄准用户星，反之则变迁Tfsn触发，退出该任务的操作规划。此时，如果星载PC满足星间发送天线对用户星进行捕获跟踪所需电量，则变迁Tfsa触发，位置Pfsa获得1个标识，表明星间发送天线已经捕获跟踪用户星，反之则变迁Tfsan触发，退出该任务的操作规划。此时，如果星载PC满足星间发送天线执行数据发送所需电量，则变迁Tfss触发，位置Pfss获得1个标识，表明星间发送天线完成数据发送，反之则变迁Tfssn触发，退出该任务的操作规划。如果在当前规划时间段内还有前向链路数据发送任务，则变迁Tfsj2触发，执行下一个任务；如果没有前向链路数据发送任务，变迁Tfsf触发，星间发送天线断电关机，返回顶层模型。

3.5 返向链路数据接收任务的操作规划模型

图5 返向链路数据接收任务的操作规划模型

如图5所示为返向链路数据接收任务的操作规划模型，用以描述TDRS返向链路数据接收任务的操作规划过程。其中，位置和变迁的定义及模型工作过程与图4中前向链路数据发送任务的操作规划模型类似，限于篇幅这里不再赘述。

3.6 返向链路数据发送任务的操作规划模型

图6 返向链路数据发送任务的操作规划模型

如图6所示为返向链路数据发送任务的操作规划模型，用以描述TDRS返向链路数据发送任务的操作规划过程。其中，位置和变迁的定义及模型工作过程与图3中前向链路数据接收任务的操作规划模型类似。

4 模型仿真及分析

4.1 模型有效性验证

假设一个简单的TDRS配置：一颗TDRS-6，分别携带一个星间数据接收天线、星间数据发送天线、星地数据接收天线和星地数据发送天线，初始状态全为断电关机状态；初始状态时，存储器容量为300 M，电源容量为800 W。如图7所示，在规划时间段230 s～460 s内，TDRS-6首先需接收地面站GS-3的数据（任务优先级为1），其次发送至用户星EO-2（任务优先级为2）。

图7 任务实例

图8 操作规划方案

在CPN Tools软件环境下，实现了TDRS操作规划模型。根据TDRS配置和相应的任务需求，对基于CPN的TDRS操作规划模型进行初始化，模型成功运行，并最终得到了TDRS的操作规划方案，如图8所示。综上，仿真实验验证了所建模型的正确性和有效性。

4.2 与PDDL模型比较分析

如何提高TDRS规划问题的求解效率有两种途径：一是设计高效的求解算法；二是从模型出发，引入领域知识以降低模型求解难度，提高搜索效率。本文仅从模型本身出发，在AMD APU系列双核A6-5400 K的CPU，内存2 G的Windows XP操作系统下，以前向状态空间搜索算法作为求解算法［13］，比较CPN模型和PDDL模型的求解效率。

假设一颗TDRS-6，分别携带一个星间数据接收天线、星间数据发送天线、星地数据接收天线和星地数据发送天线，初始状态全为断电关机状态；初始状态时，存储器容量为2 000 M，电源容量为5 000 W。假设任务时间窗口不存在冲突，任务个数从1到10逐个增加，分析两种模型的求解效率。

如图9所示，为CPN模型和PDDL模型的求解时间，在任务个数从1到10的变化范围内，随着任务个数的增加，CPN模型所花费的时间要明显少于PDDL模型。这说明CPN模型较PDDL模型具有更快的求解速度，原因是PDDL模型仅能描述独立的操作知识，无法描述操作和任务之间的知识关系，这样扩大了解的搜索空间，增加了大量无关的搜索，从而降低了模型求解效率；而CPN模型可以有效地描述TDRS任务和操作之间层级知识，有效地避免大量的无关搜索，减少搜索空间，进而提高了模型求解效率。

图9 求解时间对比图

5 结论

本文以TDRS为研究对象，以CPN为数学工具，提出了一种基于CPN的TDRS操作规划模型。实例研究验证了所建模型的有效性，与PDDL模型比较，进一步说明了所建模型可以有效描述TDRS的领域知识，能够提高求解效率。所建模型为TDRS操作规划研究与制定提供了新的思路。下一步将针对一些相对复杂的任务情况，开展相关实验研究，进一步验证本文所建模型。

［1］ Marco A，Amedeo C.Heuristic Scheduling of the DRS Communication System［J］.Engineering Applications of Artificial Intelligence，1995，8（2）：147-156.

［2］Rojanasoonthon S，Bard J，Reddy S.Algorithms for Parallel Machine Scheduling：A Case Study of the Tracking and Data Relay Satellite System ［J］.Journal of the Operational Research Society，2003，54（8）：806-821.

［3］张彦，孙占军，李剑.TDRS动态调度问题研究［J］.系统仿真学报，2011，23（7）：1464-1468.

［4］程思微，张辉，沈林成，等.基于状态-动态模型的TDRS操作规划问题建模［J］.系统工程与电子技术，2010，32（5）：1001-1006.

［5］林闯.随机Petri网和系统性能评价［M］.北京：清华大学出版社，2005：10-40.

［6］Suresh K V，Srinivasan R，Amaresh N，et al.Modeling of Various Phases of Micro Satellite Using Timed Petri Nets［C］// International Conference on Signal Processing，Communications and Networking，Chennai，India，2007：195-198.

［7］贺宇峰，赵光恒，吕从民，等.基于改进OOPN的系统工作模式分析方法［J］.宇航学报，2011，32（5）：1163-1170.

［8］Eduardo C，Paulo C V，Osamu S，et al.Petri Net and UML for the V&V of ITASAT Satellite Prototype［C］//10th Brazilian Workshop On Rreal Time and Embedded Systems，Rio de janeiro，Brazil，2008：121-124.

［9］Jensen K，Kristensen L M.Colcoured Petri Nes-Modeling and Validation of Concurrent Systems［M］.Berlin：Spring-Verlag Berlin，2009.

［10］Jensen K，Kristensen L M，Wells L.Colcoured Petri Nes and CPN Tools for Modeling and Validation of Concurrent Systems［J］.International Journal on Software tools for Technology Transfer（STTT），2007，9（3）：213-254.

［11］Fox M，Long D.PDDL2.1：An Extension to PDDL for Expressing Temporal Planning Domains［J］.Journal of AI Research，2003（20）：61-124.

［12］张正强，谭跃进.自主航天器的规划系统建模研究［J］.计算机工程与应用，2006，42（32）：197-199.

［13］Russell S，Norvig P.人工智能——一种现代方法［M］.第2版.北京：人民邮电出版社，2004.

Simulation and Modeling of Operation Planning for Tracking and Data Relay Satellite Using Colored Petri Net

LIU Chuan-hui
（Mianyang Vocational and Technical College,Mianyang 621000，China）

According to the top-to-bottom concept and level modeling idea，and a new model of operation planning for Tracking and Data Relay Satellite（TDRS）is proposed by using Colored Petri Net（CPN）.The model were divided into six modules as follows:top model，control model，operation planning model of forward and backward link data reception and transmission task，and it can describe dynamic behavior of TDRS.The scheme is obtained by designing typical example，and the proposed model is validated.Compared with Planning Domain Definition Language（PDDL）model，the proposed model can describe the domain knowledge of TDRS and has good solution efficiency.This work can provide theoretical basis for the scheme establishment of operation planning for TDRS.

tracking and data relay satellite（TDRS），operation planning，colored Petri net，PDDL

TP391

A

1002-0640（2015）05-0152-05

2014-03-04

2014-04-22

四川省教育厅科研基金资助项目（14ZB0400）

刘传辉（1981- ），男，重庆人，硕士，讲师。研究方向：任务规划、信号处理等。