计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 211200259-7.doi: 10.11896/jsjkx.211200259
徐秀珍, 吴国林, 张媛媛, 牛义锋
XU Xiu-zhen, WU Guo-lin, ZHANG Yuan-yuan, NIU Yi-feng
摘要： 多状态网络是指网络及其组成单元具有多种不同的性能水平,该网络模型已被广泛应用于描述现实中众多技术网络的行为特征。费用约束下的多状态网络可靠性Rel(d,b)是指网络能够把d单位的需求流量从源点成功输送到汇点且总的流传输费用不超过给定预算b的概率,该可靠性指标可以通过费用约束下的极小容量向量(简称(d,b)-MCV)来计算。由于(d,b)-MCV问题是典型的 NP-hard 问题,求解时间会随着网络规模增加呈指数增长,为提高求解效率,利用边的容量下限建立了关于(d,b)-MCV的改进数学模型,并从求解复杂度方面证明了该模型的优势;并且,利用超越数的概念,建立了(d,b)-MCV与实数之间的一一映射关系;基于此关系,提出了一种新的(d,b)-MCV去重方法。复杂度分析表明,该去重方法比现有方法更实用、更高效。最后,利用数值实验对提出的(d,b)-MCV算法的性能进行了检验;结果表明,该算法在求解(d,b)-MCV方面具有明显的效率优势,从而为费用约束下的多状态网络可靠性评估提供了一种新方法。
中图分类号:
| [1]AVEN T.The reliability science:its foundation and link to risk science and other sciences [J].Reliability Engineering & System Safety,2021:107863. [2]WANG H G,DONG R S,QIAN J Y.An MDD algorithm for computing the reliability of node unreliable networks [J].Computer Science,2016,43(1):154-158. [3]NIU Y F,HE C,FU D Q.Reliability assessment of a multi-state distribution network under cost and spoilage considerations[J].Annals of Operations Research,2021,309(1):189-208. [4]JANE C C,LAIH Y W.Evaluating cost and reliability integrated performance of stochastic logistics systems [J].Naval Research Logistics,2012,59:577-586. [5]ZIO E.Some challenges and opportunities in reliability enginee-ring [J].IEEE Transactions on Reliability,2016,65(4):1769-1782. [6]LIN Y K.System reliability evaluation for a multi-state supply chain network with failure nodes using minimal paths [J].IEEE Transactions on Reliability,2009,58(1):34-40. [7]NIU Y F,GAO Z Y,LAM W H K.Evaluating the reliability of a stochastic distribution network in terms of minimal cuts [J].Transportation Research Part E,2017,100:75-97. [8]NIU Y F,LAM W H K,GAO Z Y.An efficient algorithm for evaluating logistics network reliability subject to distribution cost [J].Transportation Research Part E,2014,67:175-189. [9]LIN J S.Reliability evaluation of capacitated-flow networks with budget constraints [J].IIE Transactions,1998,30(12):1175-1180. [10]LIN Y K.Reliability of a stochastic-flow network with unreliable branches & nodes under budget constraints [J].IEEE Transactions on Reliability,2004,53(3):381-387. [11]YEH W C.A new approach to evaluate reliability of multistate networks under the cost constraint [J].Omega,2005,33(3):203-209. [12]FORGHANI-ELAHABAD M,KAGAN N.Reliability evalua-tion of a stochastic-flow network in terms of minimal paths with budget constraint [J].IISE Transactions,2019,51(5):547-558. [13]XU X Z,NIU Y F,SONG Y F.Computing the reliability of a stochastic distribution network subject to budget constraint [J].Reliability Engineering & System Safety,2021,216:107947. [14]BAI G H,ZUO M J,TIAN Z G.Ordering heuristics for reliability evaluation of multi-state networks [J].IEEE Transactions on Reliability,2015,64(3):1015-1023. [15]BAI G H,TIAN Z,ZUO M J.Reliability evaluation of multi-state networks:An improved algorithm using state-space decomposition and experimental comparison [J].IISE Transactions,2018,50(5):407-418. [16]LIU T,BAI G H,TAO J Y,et al.An improved bounding algorithm for approximating multi-state network reliability based on state-space decomposition method [J].Reliability Engineering &System Safety,2021,210:107500. [17]CHEN S G,LIN Y K.Searching for d-MPs with fast enumeration [J].Journal of Computational Science,2016,17:139-147. [18]LAMALEM Y,HOUSNI K.An improved algorithm to search all d-MPs for a multi-state systems [C]//IEEE 2nd Interna-tional Conference on Electronics,Control,Optimization and Computer Science.IEEE,2020:1-6. [19]SIEGEL C L.Transcendental Numbers [M].Harbin:Harbin Institute of Technology Press,2011. [20]BAI G,TIAN Z,ZUO M J.An improved algorithm for finding all minimal paths in a network [J].Reliability Engineering & System Safety,2016,150:1-10. |
| [1] | 王鑫, 周泽宝, 余芸, 陈禹旭, 任昊文, 蒋一波, 孙凌云. 一种面向电能量数据的联邦学习可靠性激励机制 Reliable Incentive Mechanism for Federated Learning of Electric Metering Data 计算机科学, 2022, 49(3): 31-38. https://doi.org/10.11896/jsjkx.210700195 |
| [2] | 包春晖, 庄毅, 郭黎烨. 一种面向SDN的移动网络可靠性评估算法 SDN Oriented Mobile Network Reliability Evaluation Algorithm 计算机科学, 2022, 49(11A): 211000080-8. https://doi.org/10.11896/jsjkx.211000080 |
| [3] | 程稳, 李焱, 曾令仿, 王芳, 唐士程, 杨力平, 冯丹, 曾文君. 面向Lustre集群存储的错误日志分析及系统优化 Error Log Analysis and System Optimization for Lustre Cluster Storage 计算机科学, 2022, 49(10): 1-9. https://doi.org/10.11896/jsjkx.220100134 |
| [4] | 房婷, 宫傲宇, 张帆, 林艳, 贾林琼, 张一晋. 一种传输时限下认知无线电网络的动态广播策略 Dynamic Broadcasting Strategy in Cognitive Radio Networks Under Delivery Deadline 计算机科学, 2021, 48(7): 340-346. https://doi.org/10.11896/jsjkx.200900001 |
| [5] | 亓慧, 史颖, 李灯熬, 穆晓芳, 侯明星. 基于连续型深度置信神经网络的软件可靠性预测 Software Reliability Prediction Based on Continuous Deep Confidence Neural Network 计算机科学, 2021, 48(5): 86-90. https://doi.org/10.11896/jsjkx.210200055 |
| [6] | 冯凯, 马鑫玉. (n,k)-冒泡排序网络的子网络可靠性 Subnetwork Reliability of (n,k)-bubble-sort Networks 计算机科学, 2021, 48(4): 43-48. https://doi.org/10.11896/jsjkx.201100139 |
| [7] | 冯凯, 李婧. k元n方体的子网络可靠性研究 Study on Subnetwork Reliability of k-ary n-cubes 计算机科学, 2020, 47(7): 31-36. https://doi.org/10.11896/jsjkx.190700170 |
| [8] | 王慧妍, 徐经纬, 许畅. 环境感知自适应软件的运行时输入验证技术综述 Survey on Runtime Input Validation for Context-aware Adaptive Software 计算机科学, 2020, 47(6): 1-7. https://doi.org/10.11896/jsjkx.200400081 |
| [9] | 程煜, 刘伟, 孙童心, 魏志刚, 杜薇. 近阈值电压下可容错的一级缓存结构设计 Design of Fault-tolerant L1 Cache Architecture at Near-threshold Voltage 计算机科学, 2020, 47(4): 42-49. https://doi.org/10.11896/jsjkx.190300088 |
| [10] | 李苏婷,张严. GSOS算子下共变-异变模拟的公理刻画 Axiomatizing Covariation-Contravariation Simulation Under GSOS Operators 计算机科学, 2020, 47(1): 51-58. https://doi.org/10.11896/jsjkx.181102026 |
| [11] | 李蜜, 庄毅, 胡镡文. 一种结合AADL与Z的嵌入式软件可靠性建模与评估方法 Embedded Software Reliability Model and Evaluation Method Combining AADL and Z 计算机科学, 2019, 46(8): 217-223. https://doi.org/10.11896/j.issn.1002-137X.2019.08.036 |
| [12] | 弋泽龙,温玉梅,林燕敏,陈伟庭,吕冠宇. 多层缺陷关联效应对软件可靠性增长过程的影响 Impacts of Correlation Effects among Multi-layer Faults on Software Reliability Growth Processes 计算机科学, 2018, 45(2): 241-248. https://doi.org/10.11896/j.issn.1002-137X.2018.02.042 |
| [13] | 吴文华, 宋亚飞, 刘晶. 直觉模糊框架内的证据动态可靠性评估及应用 Dynamic Reliability Evaluation Method of Evidence Based on Intuitionistic Fuzzy Sets and Its Applications 计算机科学, 2018, 45(12): 160-165. https://doi.org/10.11896／j.issn.1002-137X.2018.12.025 |
| [14] | 赵冉, 潘根梅. 能量捕获无线传感器网络中高可靠数据收集策略 High Reliable Data Collection Algorithm in Energy Harvesting Wireless Sensor Networks 计算机科学, 2018, 45(11A): 303-307. |
| [15] | 刘凯, 梁欣, 张俊萍. 基于软硬系统综合方法的软件失效问题分析 Analysis on Technical Support Equipments’ Software Invalidation Based on Soft and Hard Integrated System Methodology 计算机科学, 2018, 45(11A): 494-496. |
|
||
首页