武小悦，男，教授，博士生导师。

基于BDD算法的航天测控系统任务可靠性建模与分析

孟礼，武小悦

(国防科学技术大学 信息系统与管理学院,湖南 长沙 410073)

摘要提出了一种航天测控系统的层次化建模方法，以及测控任务可靠性二元决策图(BDD)分析算法。在模型底层描述了测控系统的结构和任务需求信息，模型顶层将测控资源与任务进行统一，将测控单元任务弧段切割成不同阶段，建立了任务可靠性的故障树模型。采用ITE算法将故障树模型转换为BDD模型，并给出了BDD模型的计算方法。最后，运用实例说明了方法的有效性，进行了测控任务可靠性的灵敏度分析，找出了系统的薄弱环节。

关键词测控系统；可靠性模型；二元决策图；薄弱环节分析

作者简介孟礼(1986-)，男，博士研究生，主要研究方向为装备系统分析与管理决策。mengli0603@163.com

中图分类号TB114.3

文章编号2095-3828(2015)05-0113-07

DOI文献标志码A 10.3783/j.issn.2095-3828.2015.05.025

Mission Reliability Modeling of Spaceflight TT&C System Based on

BDD Algorithm and Relevant Analysis

MENG Li，WU Xiaoyue

(College of Information Systems and Management, National University of Defense Technology, Changsha Hunan 410073, China)

AbstractThis paper proposes a hierarchical modeling approach and binary decision diagram (BDD) evaluating algorithm for the mission reliability analysis of spaceflight telemetry, tracking and command (TT&C) system. The model describes the system structure at the lower level and mission information. At the upper level, components and missions are associated together. By cutting flight phase into many sections, the paper establishes a mission reliability model of fault tree. With if-then-else (ITE) algorithm, the paper transforms fault trees into BDDs, and then expresses BDD evaluation algorithm. In the end, the paper illustrates the practicability and effectiveness of the approach with an example, analyzes the sensitivity of mission reliability and identifies the vulnerable points of system.

Keywordstelemetry, tracking and command system (TT&C system); reliability modeling; binary decision diagram (BDD); vulnerable spot analysis

航天测控系统是执行航天器的跟踪、测量、指挥等功能的系统，包括航天器发射场、地面测控站、测量船等基本测控单元[1]1268-1272。航天测控系统的测控任务包括若干连续、无重叠的时间阶段。例如:对于某卫星发射任务，可以划分为火箭点火前的准备阶段、点火至星箭分离阶段、星箭分离至卫星入轨阶段，这3个基本阶段时间上连续、逻辑上相互依赖，因此航天测控系统是一个典型的多阶段任务系统(Phased-Mission System,PMS)。航天测控系统的任务可靠性是指航天测控系统在所有阶段完成既定测控功能的能力，任何阶段的失败都将导致整个测控任务失败。

状态空间法和组合模型法是PMS可靠性分析的2种基本方法[2]。以马尔科夫为代表的状态空间方法描述系统状态转移行为详细、直接，但在处理大规模系统时容易遇到状态空间组合爆炸问题。假设航天测控系统各测控单元是相互独立的，采用组合模型法可有效避免空间组合爆炸问题。BDD最初是由Lee[3]和Akers[4]基于香农扩展式(Shannon’s decomposition)[5]29-32提出的布尔函数数据结构。文献[5-6]和其他许多研究表明，在大多数情况下，与其他方法相比,BDD算法总能以最少的存储空间表示大规模布尔表达式，可以高效执行布尔操作。因此，对于航天测控系统这样的大规模多阶段任务系统，基于BDD的逻辑关系表达和任务可靠性分析具有直接高效的特点。

尽管对PMS的建模技术已经进行了深入的研究，但是对于航天测控系统可靠性分析的关注仍然很少。Pedar和Sarma[7]运用可靠性框图法分析了航天计算系统的单个阶段任务可靠性。南加州气体动力实验室采用可靠性框图模型和仿真的方式，构建美国国家航空航天局(NASA)空间干涉任务(Space Interferometry Mission,SIM)逻辑结构模型，得出任务可靠性的近似结果[8]。Nathan[9]为系统的性能、可靠性和维修性设置重要度参数，提出以效力描述系统完成任务成功概率的定性方案，并采用马尔可夫方法分析了某载人航天任务的可靠性。Demircioglu和Nefes[1] 1268-1272通过设置系统可靠性下限和设备制造成本上限，建立了航天测控系统设备配置的优化模型。从目前的研究成果看，针对航天测控系统的可靠性建模往往针对某特定的测控任务，解决问题规模较小，可靠性模型的通用性和可扩展性较差，任务可靠性计算方法效率有待提高。

本文按照测控单元功能，对航天测控系统进行分解，自下而上分别建立了资源模型、任务模型、分配模型和可靠性模型。通过弧段切割，首先建立各阶段的故障树模型，进而建立可靠性BDD模型，然后根据BDD布尔操作规则建立测控任务BDD模型，并计算任务可靠性。最后，通过对测控任务算例进行灵敏度分析，找出系统薄弱环节并提出改进方案。

1航天测控系统可靠性建模

本节从航天测控系统测控单元功能出发，自下而上依次建立了4个模型用于描述航天测控系统的任务信息，分别为资源模型、任务模型、分配模型和可靠性模型，如图1所示。

图1　航天测控系统可靠性层次模型

资源模型统一描述航天测控系统的测控资源信息，包括测控中心、测控站点等测控单元。在资源模型的第一层次，系统由3类测控单元组成:测控中心、测控站点和通信路由。在模型第二层次，中心和站点配备若干设备，在中心和站点之间则通过路由进行通信。

任务模型统一描述航天测控系统的测控任务信息，包括测控对象、任务的执行弧段等。航天测控系统的每个任务都是在某个测控弧段中，由测控中心、测控站、通信路由等共同完成。

分配模型以资源模型和任务模型为基础，将资源模型中的测控站点配置给每个测控任务。配置给某测控任务的测控站点在该测控任务的执行弧段中必须对测控对象可视，即处于对该测控对象的可视时间窗口内。分配模型主要描述执行测控任务的每个测控站点的运行窗口，以及测控站点所属测控设备的逻辑连接结构。本文假设测控站点所属测控设备的运行时间与站点任务弧段相同，并且设备的逻辑连接关系根据测控任务的不同发生变化。一般情况下，无论测控中心对测控对象是否可视，测控中心在任务执行全过程都处于运行状态，并且通过通信路由与测控站点进行实时通信和数据传输。因此，在设备逻辑关系描述中包括了测控中心和通信路由的相关设备。

由于测控站点所处的地理位置不同，它们对于某一测控对象的可视时间窗口不同，因而执行测控任务的弧段也是不同的。可靠性模型的主要任务是分析测控站点不同任务弧段间的逻辑关系，构建可以直接作为计算机程序输入的可靠性模型。本文采用弧段切割技术对测控站点的任务弧段进行分析，例如，在分配模型中，某测控任务X由测控站点S1、S2、S3和S4共同完成，各站点任务弧段如图2a)所示。采用弧段切割技术对测控任务X中的所有测控站弧段进行切割(在每个测控站点执行弧段的起点和终点对整个任务弧段进行切割)，结果如图2b)所示。

a) 测控任务X执行弧段　　　　　　　　　　　　b) 测控任务X弧段切割结果 图2　测控任务X的可靠性模型

从图中可以看出，测控任务X被切割为4个阶段。在阶段1中，站点S1单独执行测控任务；在阶段2，站点S1和S2共同执行测控任务。本文假设在弧段切割后的每个阶段中，测控站点间为并联关系，即在某一阶段中，任一测控站点完成既定测控任务即可判定该阶段任务成功。本文采取2个步骤构建测控任务X的可靠性模型:步骤1，根据每个阶段测控站点间以及测控站点内设备的逻辑连接关系，建立阶段故障树模型，然后转化为阶段BDD模型；步骤2，将任务失败定义为阶段失败的逻辑“或”关系，最终得到测控任务的BDD可靠性模型。

在这4个模型中，资源模型和任务模型分别用于统一管理航天测控系统中的测控资源信息和测控任务信息，处于基础地位。在实际工程中，可以采用XML等标记语言对资源和任务信息进行集中管理，作为测控系统任务可靠性分析的数据输入。分配模型将测控资源配属给不同的测控弧段，以完成相应的测控任务，是对航天测控系统具体运行情况的反映。可靠性模型是对分配模型的逻辑分析，是进行测控任务可靠性分析的基础，其中作为核心步骤的弧段切割过程可以通过计算机编程自动实现。

2航天测控系统可靠性BDD算法

以可靠性模型为基础，可以构建测控任务各阶段的故障树模型，并将其转化为BDD模型。根据BDD布尔操作规则，将各阶段BDD模型合并为任务BDD可靠性模型，然后在BDD可靠性计算过程中处理设备在不同阶段间的依赖关系。

2.1BDD建模

2.1.1单阶段BDD模型

假设执行测控任务X的测控中心、各测控站点以及通信路由的设备逻辑连接关系如图3所示。其中，B为测控中心计算机系统；C，D为公用通信路由设备；A、E、H、K分别为各测控站的监视跟踪设备；F、G、I、J和L、M分别为站点S2、S3、S4与测控中心进行数据通信的链路设备，站点S1与测控中心直接相连。

图3　测控任务X的各测控站点设备逻辑连接关系

图4　测控任务X各阶段故障树模型

图5　测控任务X第2阶段的BDD模型

2.1.2任务BDD模型

P=FΘG=ITE(x,F1,F2)ΘITE(y,G1,G2)=

式中:Θ为任意布尔操作；index(x)为单元x的排序结果。本文采用后向阶段依赖(Backward Phased Dependent Operations,BPDO)排序策略[10]。BDD模型布尔操作算法流程如图6所示。算法的输入为2个BDD模型F、G及二者间的布尔操作。首先判断F和G中是否存在0或1节点，若存在，则直接返回F、G间的逻辑操作结果。若不存在，则根据BPDO排序策略比较F、G的根节点顺序。然后基于根节点排序结果和BDD布尔操作规则，通过对算法的递归调用，将F、G间的布尔操作分解为各自子BDD模型间的布尔操作，直到分解为0或1节点为止。

图6　BDD布尔操作算法流程图

在航天测控系统中，任意阶段的失败均会导致整个测控任务失败，因此，测控任务X的BDD可靠性模型为所有阶段BDD模型进行逻辑“或”运算的结果。

2.2BDD模型可靠性计算

(1)

式(1)的前半部分表示设备A在前(j-1)个阶段已经失效的概率，后半部分表示设备A在阶段j的寿命概率分布。

(2)

(3)

(4)

图7为BDD模型的可靠性分析算法流程。

图7　可靠性分析流程图

算法的输入是BDD模型G，输出是该BDD的可靠性分析结果。因为G和G2的顶变量由0边连接，总是不同的，所以在默认情况下采用式(2)计算0边可靠性。算法的关键步骤是判断G和G1的顶变量是否相同，如果相同，即G和G1的顶变量表示相同的测控设备，则采用式(4)计算1边的可靠性；反之用式(3)。最后，计算根节点的可靠性。

3算例及分析

以图2中的测控任务X为例，共有13个设备参加任务，假设13个参加任务的测控设备可靠性参数如表1所示。

表1　测控设备可靠性参数

根据图6构建的测控任务BDD模型，采用图7中的算法对BDD模型进行可靠性分析，计算该测控任务可靠性为0.988 613 8。

为了分析航天测控系统的薄弱环节，为系统顶层设计和改进提供可靠性数据支撑，需要分析不同测控单元对于任务可靠性的重要程度。以测控任务X为例，采用改变一套设备可靠性参数，固定其他设备可靠性参数的方式，分析测控任务对于设备可靠性参数变化的灵敏度。选取任务X中具有代表性的设备B、C、F和H，在固定其他设备可靠性参数的条件下，分别将这几套设备的可靠性以0.01为步长下调6次，计算测控任务X可靠性结果如表2所示。

从表2中可以看出，设备B可靠性参数下降对任务可靠性影响最大，而设备C、F、H对任务可靠性影响均在10-3数量级以下。如图8所示，随着设备B可靠性下降，测控任务X可靠性衰减速度明显高于其他3条曲线，因此，可以判定测控设备B，即测控中心计算机系统为任务X的薄弱环节。在同等条件下，提高设备B的可靠性参数对提高任务可靠性贡献最大。

表2　测控任务X灵敏度分析计算结果

a) 设备B、C可靠性灵敏度对比　　　　b) 设备B、F可靠性灵敏度对比　　　　c) 设备B、H可靠性灵敏度对比 图8　测控任务X可靠性衰减对比曲线

为保证测控任务X顺利执行，降低失败概率，决定对原测控方案进行改进，采取措施对系统薄弱环节测控中心计算机系统进行备份操作，增加一套与设备B完全相同的设备B0，使B0与B形成双机热备份关系，即并联关系。在固定其他测控设备(包括B0)的可靠性参数，只改变设备B可靠性参数的条件下，计算任务X可靠性如表3所示，2种测控方案任务可靠性衰减曲线如图9所示。

表3　新旧方案下测控任务 X灵敏度对比分析计算结果

图9　新旧测控方案下任务X可靠性衰减曲线

从表3和图9中可以看出，通过为测控设备B增加备份，在B可靠性降低的情况下，有效降低了任务可靠性衰减速度，提高了任务成功率。

4结 束 语

本文采用自下而上的方式建立了航天测控系统的可靠性分析模型，给出了采用BDD模型计算任务可靠性的算法。航天测控系统可靠性模型包括4个部分:资源模型、任务模型、分配模型和可靠性模型。资源模型和任务模型分别描述了测控单元信息和任务执行弧段信息。在分配模型中，将资源模型和任务模型统一起来，同时构建测控设备间的逻辑结构。对分配模型进行弧段切割，首先建立测控任务各阶段的故障树模型，然后采用ITE算法将阶段故障树模型转化为BDD模型，再根据BDD布尔操作规则构建测控任务可靠性模型，并提出基于BDD的测控任务可靠性分析算法。最后，以某测控任务为例，计算任务可靠性，分析任务对于测控设备的灵敏度，找出系统中的薄弱环节，并提出改进方案。从算法的运行过程和计算结果看，BDD模型具有占用存储空间小、布尔逻辑操作速度快、计算结果准确的特点，适用于以航天测控系统为代表的大规模多阶段任务系统可靠性建模与分析。

参考文献(References)

[1]DEMIRCIOGLU E,NEFES M M.Reliability-based TT&C subsystem design methodology for complex spacecraft missions[C]//Information Sciences and Systems,2008.CISS 2008.42nd Annual Conference on.Princeton,NJ:IEEE,2008:1268-1272.

[2]WANG D Z,TRIVEDI K S.Reliability analysis of phased-mission system with independent component repairs[J].IEEE Transaction on Reliability,2007,56(3):540-551.

[3]LEE C Y.Representation of switching circuits by binary decision programs[J].Bell Syst Tech,1959,38(4):985-999.

[4]AKERS B.Binary decision diagrams[J].IEEE Transaction on Compute,1978,27(6):509-516.

[5]MEINEL C,THEOBALD T.Algorithms and data structures in VLSI design:BDD foundations and applications[M].New York:Springer-Verlag Berlin Heidelberg,1998.

[6]BRYANT R.Graph based algorithms for boolean function manipulation[J].IEEE Transaction on Compute,1986,35(8):677-691.

[7]PEDAR A,SARMA V V S.Phased-mission analysis for evaluating the effectiveness of aerospace computing systems[J].IEEE Transaction on Reliability,1981,30(5):429-437.

[8]ARON K M A,FOX G,EBBELER D H,et al.Reliability modeling for the space interferometry mission[C]//Aerospace Conference Proceedings,2002.IEEE,2002:689-704 .

[9]NATHAN I.Mission effectiveness model manned space flight[J].IEEE Transaction on Reliability,1965，R-14(2):84-93.

[10]MO Y C.New insights into the BDD-based reliability analysis of phased-mission systems[J].IEEE Transaction on Reliability,2009,58(4):667-678.

[11]ZANG X Y,SUN H R,TRIVEDI K S.A BDD-based algorithm for reliability analysis of phased-mission systems[J].IEEE Transactions on Reliability,1999,48(1):50-60.

(编辑：李江涛)