多阶段任务系统可靠性分析的ROBDD算法

ROBDD algorithm for analyzing the reliability of phased-mission system

针对Markov方法分析多阶段任务系统(Phased-Mission System,PMS)可靠性时的状态空间爆炸问题,基于层次化建模思想,建立了PMS任务可靠性的顶层系统二维决策图(Binary Decision Diagram,BDD)模型和底层部件Markov模型。通过分析BDD中的同构节点和冗余节点,提出顶层模型构造过程中的同构节点合并策略和冗余节点删除策略。利用上述节点压缩策略生成简化模型,提高模型构造和存储效率。基于PMS部件排序规则,给出了层次化模型的递归求解方法,该方法的计算复杂度与顶层模型中的节点总数呈线性关系。通过算例分析,对比采用节点压缩策略前后的模型节点数,以及层次化方法与Markov方法的计算结果,验证了简化层次模型的正确性和有效性。

The reliability analysis approach of PMS(phased-mission system)based on Markov process encounters the state explosion problem for large systems.To avoid the state-explosion problem,the PMS reliability model using hierarchical method was proposed.The hierarchical method uses a low-level continuous time Markov chain and an upper-level binary decision diagrams.The isomorphic nodes consolidation strategy and the redundant nodes removal strategy were given to construct reduced hierarchical model.The above nodes compressing strategies can improve the efficiency of model generation and storage.A recursive computing algorithm solving the hierarchical model was designed on the basis of the PMS components ordering,and its computational complexity was linear with the number of nodes in model.Finally,by a case study,the number of nodes in the original model was compared with the proposed model using nodes compressing strategy,also the mission reliability in the hierarchical model was compared with it in the Markov model.Results show the correctness and effectiveness of the reduced hierarchical model.