针对现有可靠性分析方法不能适应卫星网络中信息传播时延长，业务需求多样，导致计算准确性低的问题。考虑卫星工作的多状态特性，研究了多状态下卫星网络可靠性的问题，提出了一种基于QoS的卫星网络k端可靠性分析算法。首先，进行节点融合，对非融合元素采取置零取非操作，进行网络拓扑邻接矩阵变换，得到连通k个节点的路径。相较于传统方法有效地减少了矩阵变换次数，避免了冗余链路的产生。然后，为提升可靠度计算的准确性，根据不同业务的QoS约束条件和链路当前状态，确定网络中满足条件的可用路径，最后，由链路当前状态的可靠度计算出不同业务下的k端路径可靠度。研究结果表明：相较于其他算法，本算法不仅提升了卫星网络在不同业务下k端路径可靠度计算的准确性，而且计算效率提升了33.3%。
Existing reliability analysis methods cannot solve the problem of low calculation accuracy due to prolonged information transmission time in the satellite network and diverse service requirements. Considering the multi-state characteristics of satellite operation, reliability of satellite network in multi-states is studied, and a k-terminal reliability analysis algorithm is proposed based on Quality of Service(QoS). Firstly, the nodes are fused, and the non-fused elements are set to zero; the network topology adjacency matrix is transformed to get the path connecting K nodes. Compared with the traditional method, the matrix transformation is effectively reduced and the redundant links are avoided. Then, to improve the accuracy of reliability calculation, according to the QoS constraints of different services and the current state of the link, the available paths satisfying the conditions in the network are determined. Finally, the k-terminal path reliability for different services is calculated from the reliability of the current state of the link. The results show that compared with other algorithms, the algorithm proposed can improve not only the accuracy of k-terminal path reliability calculation for different services, but also the calculation efficiency by 33.3%.
[1] 李林郁, 高建国. 基于抗毁性的卫星通信系统可靠性研究[J]. 通讯世界, 2016(1): 68. LI L Y, GAO J G. Research on reliability of satellite communication system based on invulnerability[J]. Telecom World, 2016(1): 68(in Chinese).
[2] 张莉, 赵丽红, 蒋勇, 等. 基于petri网跳面节点的空间信息网可靠性评估[J]. 控制工程, 2016, 23(S1): 66-72. ZHANG L, ZHAO L H, JIANG Y,et al. Reliability evaluation of space information network based on petri net jump surface nodes[J]. Control Engineering of China, 2016, 23(S1): 66-72(in Chinese).
[3] 陈祝允, 赵兵, 郭道省. 信道化卫星通信系统的链路可靠性分析[J]. 现代雷达, 2020, 42(9): 69-74. CHEN Z Y, ZHAO B, GUO D X. Analysis for link reliability of channelized satellite communication system[J]. Modern Radar, 2020, 42(9): 69-74(in Chinese).
[4] RAI S, AGRAWAL D P. Distributed computing network reliability[M]. LOS Alamitos: IEEE Computer Society, 1990: 98-137.
[5] BALL M O. Computational complexity of network reliability analysis: An overview[J]. IEEE Transactions on Reliability, 1986, 35(3): 230-239.
[6] 吴蓉晖. 基于分解定量的网络K终端可靠性分析算法研究[D]. 长沙: 湖南大学, 2001. WU R H. Research on network K terminal reliability analysis algorithm based on decomposition theorem[D]. Changsha: Hunan University, 2001.
[7] CANCELA H, ROBLEDO F, RUBINO G, et al. Monte Carlo estimation of diameter-constrained network reliability conditioned by pathsets and cutsets[J]. Computer Communications, 2013, 36(6): 611-620.
[8] WOOD R K. A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability[J]. Networks, 1985, 15(2): 173-190.
[9] REBAIAIA M L, AIT-KADI D. Reliability evaluation of imperfect K-terminal stochastic networks using polygon-to chain and series-parallel reductions[C]//Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks. New York: ACM, 2015.
[10] KIM Y, KANG W H. Network reliability analysis of complex systems using a non-simulation-based method[J]. Reliability Engineering & System Safety, 2013, 110: 80-88.
[11] KHARBASH S, WANG W Y. Computing two-terminal reliability in mobile ad hoc networks[C]//2007 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE Press, 2007: 2831-2836.
[12] 张本宏. 控制系统中多模冗余与网络可靠性研究[D]. 合肥: 合肥工业大学, 2010. ZHANG B H. Research on multi-module redundancy and network reliability in control systems[D]. Hefei: Hefei University of Technology, 2010(in Chinese).
[13] 宋凤, 莫毓昌, 潘竹生, 等. 带长度约束的k端网络可靠性分析[J]. 计算机工程与科学, 2016, 38(1):84-88. SONG F, MO Y C, PAN Z S,et al. k-terminal network reliability analysis with length constraint[J]. Computer Engineering and Science, 2016, 38(1):84-88(in Chinese).
[14] HARDY G, LUCET C, LIMNIOS N. k-terminal network reliability measures with binary decision diagrams[J]. IEEE Transactions on Reliability, 2007, 56(3): 506-515.
[15] SINGH S, VERMA A, CHATTERJEE S, et al. An efficient methodology to solve the K-terminal network reliability problem[C]//2016 3rd International Conference on Recent Advances in Information Technology(RAIT). Piscataway: IEEE Press, 2016: 25-28.
[16] MO Y C, LIANG M, XING L D, et al. Network simplification and K-terminal reliability evaluation of sensor-cloud systems[J]. IEEE Access, 2020, 8: 177206-177218.
[17] 杨力, 孙晶, 潘成胜, 等. 基于多目标决策的LEO卫星网络多业务路由算法[J]. 通信学报, 2016, 37(10): 25-32. YANG L, SUN J, PAN C S, et al.LEO multi-service routing algorithm based on multi-objective decision making[J]. Journal on Communications, 2016, 37(10): 25-32(in Chinese).
[18] 费培之. 图和网络及其应用[M]. 成都: 四川大学出版社, 1996. FEI P Z. Graph and network and its application[M]. Chengdu: Sichuan University Press, 1996(in Chinese).
[19] 张赵晨子. 基于QoS的软件定义网络路由算法研究[D]. 西安: 西安工业大学, 2019. ZHANG Z C Z. Research on software-defined networking routing algorithm based on QoS[D]. Xi’an: Xi’an Technological University, 2019(in Chinese).
[20] 蔡睿妍, 潘芸, 魏德宾, 等. 基于QoS的卫星网络端-端通信可靠性分析[J]. 航空学报, 2020, 41(3): 323510. CAI R Y, PAN Y, WEI D B, et al.Reliability analysis of end-to-end communication in satellite networks based on QoS[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(3): 323510(in Chinese).
CJA