Storage and Computation of Markov Reliability Model for Large-scale Phased-mission System

doi:10.3969/j.issn.1000-1093.2016.09.023

Abstract

Abstract: When Markov model is used to analyzed the reliability of phased-mission system, the system state grows exponentially with the increase in the number of components, thus resulting in a huge storage space and calculated amount resolved by the model. According to the element value rules and sparsity of the transition rate matrix Q in Markov model, the formula of computing the elements q_ij is derived based on binary description of states, and a Q-matrix compressed storage scheme (QMCS) is proposed. A reliability computing algorithm using Krylov subspace method is proposed based on the model compressed storage scheme. Taking a practical phased-mission system for example, the required storage spaces, computation times and reliability results of different compressed storage schemes and different algorithms are compared. The analysis results show that the method combining QMCS and Krylov subspace method has higher efficiency in storage and computation. Especially in the case of a large matrix, the QMCS-Krylov method is superior to other methods both in computation time and accuracy.

Key words: system assessment and feasibility, reliability evaluation, phase-mission system, compressed storage, Krylov subspace

CLC Number:

YAN Hua， GAO Li， WANG Kui， QI Lei. Storage and Computation of Markov Reliability Model for Large-scale Phased-mission System[J]. Acta Armamentarii, 2016, 37(9): 1715-1720.

References

［1］ Alam M, Al-Saggaf U M. Quantitative reliability evaluation of repairable phased-mission systems using Markov approach[J]. IEEE Transactions on Reliability, 1986, 35(5): 498-503.
[2] Peng R, Zhai Q, Xing L D. Reliability of demand-based phased-mission systems subject to fault level coverage[J]. Reliability Engineering and System Safety, 2014, 121(1): 18-25.
[3] Wu X Y, Wu X Y. Extended object-oriented Petri net model for mission reliability simulation of repairable PMS with common cause failures[J]. Reliability Engineering and System Safety, 2015, 136(4): 109-119.
[4] Shahnaz R, Usman A, Chughtai I R. Review of storage techniques for sparse matrices[C]∥ 2005 Pakistan Section Multitopic Conference. Karachi, Pakistan: IEEE, 2005.
[5] Zhang J, Wan J, Li F. Efficient sparse matrix-vector multiplication using cache oblivious extension quadtree storage format[J]. Future Generation Computer Systems, 2016, 54(1): 490-500.
[6] Golub G H, Loan C F V. Matrix computations[M]. 4th ed. Baltimore, US: Johns Hopkins University Press, 2013.
[7] Haque S A. Acomputational study of sparse matrix storage schemes[D]. Lethbridge, Canada: University of Lethbridge, 2008.
[8] 黎丽荣. 基于Markov模型的大型PMS任务可靠性分析方法[D]. 长沙: 国防科学技术大学, 2011.
LI Li-rong. Method of mission reliability analysis of large PMS based on Markov model[D]. Changsha: National University of Defense Technology, 2011. (in Chinese)
[9] Wu X Y, Yan H, Li L R. Numerical method for reliability analysis of phased- mission system using Markov chains[J]. Communications in Statistics—Theory and Methods, 2012, 41(21): 3960-3973.
[10] 石磊, 姚瑶. 马尔可夫预测模型中转移概率矩阵的压缩与应用[J]. 计算机应用, 2007, 27(11): 2746-2749.
SHI Lei, YAO Yao. Compression and application of transiton probability matrix in Markov prediction model[J]. Computer Applications, 2007, 27(11): 2746-2749. (in Chinese)
[11] Moorsel A P V, Sanders W H. Transient solution of Markov models by combining adaptive and standard uniformization[J]. IEEE Transactions on Reliability, 1997, 46(3): 430-440.
[12] Stewart W J. Introduction of thenumerical solution of Markov chains[M]. Princeton, NJ: Princeton University Press, 1994.
[13] Rauzy A. An experimental study on iterative methods to compute transient solutions of large Markov models[J]. Reliability Engineering and System Safety, 2004, 86(1): 105-115.
[14] Lu J M, Wu X Y. Reliability evaluation of generalized phased-mission systems with repairable components[J]. Reliability Engineering and System Safety, 2014, 121(1): 136-145.
[15] Ross S M. Introduction to probability models[M]. Burlington, US: Academic Press, 2006.
[16] Saad Y. Iterative methods for sparse linear systems[M]. New York, US: PWS Publishing Company, 1996.
[17] 闫华, 武小悦. 航天测控通信系统可靠性分析的改进Krylov投影算法[J]. 系统工程与电子技术, 2012, 34(10): 2180-2186.
YAN Hua, WU Xiao-yue. Improved Krylov subspace projection algorithm for reliability analysis of TT & C and communication system[J]. Systems Engineering and Electronics, 2012, 34(10): 2180- 2186. (in Chinese)
[18] Simecek I, Langr D, Tvrdik P. Space-efficient sparse matrix storage formats for massively parallel systems[C]∥Proceedings of 14th IEEE International Conference on High Performance Computing and Communications. Liverpool: IEEE, 2012: 54-60.

[1]	XIA Xin-tao, YE Liang, LI Yun-fei, CHANG Zhen. Reliability Evaluation Based on Hierarchical Bootstrap Maximum Entropy Method [J]. Acta Armamentarii, 2016, 37(7): 1317-1329.
[2]	TIAN Heng, DUAN Fu-hai, JIANG Xiu-hong, SANG Yong. A Novel Fault Diagnosis Algorithm of Testability D matrix Based on Quasi Information Entropy [J]. Acta Armamentarii, 2016, 37(5): 923-928.
[3]	ZHANG Wen-jie， YANG Hua-bo， ZHANG Shi-feng. Reliability Assessment for Device with Only Safe-or-failure Pattern Based on Bayesian Hyprid Prior Approach [J]. Acta Armamentarii, 2016, 37(3): 505-511.
[4]	GAO Ang, HU Yan-su. The Optimization and Evaluation of Ballistic Missile Defense System Interception Scheme Based on Probability Model [J]. Acta Armamentarii, 2016, 37(2): 379-384.
[5]	ZHU Sai, CAI Jin-yan, MENG Ya-feng, LI Dan-yang, PAN Gang. Evaluation of Target Circuit Realized on Embryonics Array with Faulty Cells [J]. Acta Armamentarii, 2016, 37(11): 2120-2127.
[6]	SHI Xiao-bin, GU Hong, SU Wei-min, DONG Tian-qi, CHEN Xu-long. Study of Target Threat Assessment for Ground Surveillance Radar [J]. Acta Armamentarii, 2015, 36(6): 1128-1135.
[7]	GAI Jing-bo， KONG Yao. Reliability Assessment Based on Physical Parameters [J]. Acta Armamentarii, 2015, 36(6): 1104-1109.
[8]	SUO Zhong-ying， CHENG Si-yi， YUAN Xiu-jiu， LI Yan-ming. Rule Acquisition Method and Application of Dominance Decision-making Information System [J]. Acta Armamentarii, 2015, 36(3): 539-544.
[9]	JIANG Xiu-hong， DUAN Fu-hai， CHEN Pu， JIN Xia. Design of Predictive Maintenance Platform for INS Based on GO Methodology and RCM [J]. Acta Armamentarii, 2014, 35(9): 1443-1450.
[10]	WANG Min-le, LI Yong. Modeling and Research on Penetration Effectiveness Evaluation of Ballistic Missile Considering the Effect of Decoys [J]. Acta Armamentarii, 2014, 35(8): 1318-1323.
[11]	ZHENG Zhi-gang， HU Yun-an， WU Liang. Study of on-line Diagnosis Strategy for Multiple faults [J]. Acta Armamentarii, 2014, 35(6): 921-926.
[12]	DENG Ke-bo, CHENG Wen-di, LEI Ming, RAO Jia-ren. Evaluation of Air-defense C⁴ISR System Structure Based on Discrete-event Simulation [J]. Acta Armamentarii, 2014, 35(10): 1721-1728.
[13]	HUANG Chang-qiang, TANG Chuan-lin, HUANG Han-qiao, WANG Yong, DU Hai-wen. Mission Decision-Making Method of UAV Considering Target Importance and Historical Mission Trust Value [J]. Acta Armamentarii, 2013, 34(3): 339-345.
[14]	LI Jun, MENG Tao, ZHANG Li-xin, ZHAO Shao-ping. Research on Evaluation Method for Quality and Performance of Missile Weapon Based on Rough Set Rule Extraction [J]. Acta Armamentarii, 2013, 34(12): 1529-1535.
[15]	TANG Zheng, SUN Chao₁, LIU Zong-wei₁, MENG Di₁. Research on Efficiency Evaluation for Underwater Acoustic Countermeasure System Based on GreyHierarchy Analysis [J]. Acta Armamentarii, 2012, 33(4): 432-436.