一种复杂网络可靠度的蒙特卡罗评估方法
一种复杂网络可靠度的蒙特卡罗评估方法
【技术领域】
[0001] 本发明属于计算机技术领域，设及网络可靠度的计算问题，尤其设及一种网络可 靠度的蒙特卡罗评估方法。
【背景技术】
[0002] 随着网络的高速发展，网络已成为人类生产、生活不可或缺的一部分，运些复杂网 络包括医疗网络、教育网络、电网、输油输气管道网络、无线传感器网络等有线网络和无线 网络。随着网络规模的不断扩大，网络的结构越来越复杂。网络的设计可能需要随时根据网 络可靠度的计算结果对网络进行调整和优化，如增删一些链路、结点或者改变一些结点的 位置，如果缺乏可靠性的准确评估，工程人员设计出的网络将面临很多安全隐患，给网络管 理、维护和修复带来很多不确定性，甚至一旦发生故障，将造成重大甚至灾难性影响。网络 可靠性是保证网络安全因素的重要方面，尤其是近年来，网络安全问题日益成为国际社会 关注焦点，针对我国现状急需加强自身网络建设和可靠性评估，提高基础网络的安全性。网 络可靠性评估也是度量网络安全程度的重要手段，通过加强复杂网络可靠性研究能有效提 升网络建设和管理能力，有利于提高网络安全系数，有利于提高网络的生存性和抗毁性，有 利于增强复杂网络可靠性，减少网络的故障概率W及网络资源浪费，因此针对复杂网络可 靠性评估具有极其重要的现实意义。
[0003] 大型复杂网络系统可靠度精确计算是一个NP-hard问题，如何对其进行快速、精确 的计算是可靠度研究的重点与热点。从网络可靠性计算精确性角度分析，现有的网络可靠 度计算方法可分为两类:精确计算和近似计算。精确计算方法主要包括因子分解、二元决策 图，不交最小路方法、不交最小割方法、排序二分决策图、状态枚举法和容斥原理法等方法， 运些精确可靠度求解算法随着网络的增大其复杂程度呈指数增长趋势，运类算法往往大多 只能适用于中、小型网络的可靠度分析，对于大型复杂工程网络系统，会因网络复杂性而无 法求解或者计算量快速膨胀，算法的计算效率变得低下；另一类是近似估计与抽样仿真的 方法，近似计算方法通过计算可靠度边界值来逼近精确值，尤其随着网络规模越来越大的 客观现实，采用近似估计的方法就受到重视和青睐，该类方法主要有可靠度上下界、蒙特卡 罗(MC，Monte化rlo)法等方法，上下界法在确定较理想的可靠度界值范围时，而且往往W 牺牲计算复杂度为代价进行权衡；蒙特卡罗法是W概率统计实验为基础的仿真方法，能够 真实地模拟实际物理过程，解决一些系统过于复杂而难W建立精确数学模型的问题，具有 直观、复杂度低的优点，广泛应用于大型网络的仿真研究。
【发明内容】
[0004] 本发明的目的在于提供一种复杂网络可靠度的评估方法，该方法有利于减少时间 复杂度和提高计算效率。
[0005] 为了实现上述目的，本发明提出了一种复杂网络可靠度的蒙特卡罗评估方法，该 方法采用事件驱动的蒙特卡罗评估法EM(XEvent-driven MC)，为每条链路生成故障事件时 亥Ij，通过寻找最优先的故障时刻和对应事件更新网络状态，进而实现复杂网络的可靠性评 估。
[0006] 本发明提出的一种网络可靠度的蒙特卡罗评估方法，具体包括如下步骤：
[0007] 步骤S1:构建整个网络的无向、无自环图，统计网络中的所有节点和链路(边），为 每个节点顺序编号为VI，设节点总数为N，1 y如;为每条边顺序编号为ei，链路总数为M，1 < i <1。
[000引步骤S2:创建事件驱动模型。
[0009]步骤S3:基于事件驱动的概率分布取样。
[0010]步骤S4:为每条链路生成故障事件时刻，为所有链路ei生成Yi个TPei，并在链路事 件表中插入链路ei事件。
[0011] 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6。
[0012] 步骤S6:置所有链路ei状态是连通的，寻找并返回事件表中最优先的时间指针 TPmino
[0013] 步骤S7:当随机产生链路ei故障事件的时间指针值为TPmin，则链路ei是故障状态， 并在链路事件表中删除链路ei故障事件。
[0014] 步骤S8:获得网络状态X，若X状态是网络连通，则累计其次数，并返回步骤S5。
[0015] 步骤S9:求出网络可靠度估计值。
[0016] 本发明针对复杂网络结构可靠度的评价问题，提出了一种基于网络故障事件驱动 的蒙特卡罗评估方法。该方法通过产生各链路故障事件的时间指针，来构建网络的事件表。 通过更新事件表驱动网络状态的更新，在保持了估计精度的前提下，大幅降低了复杂度，是 处理大型网络和可靠度极值问题的有效仿真方法。
【附图说明】
[0017] 图1为本发明的一种复杂网络可靠度的蒙特卡罗评估方法流程图。
[001引图2为本发明方法的EMC与CMC取样示意图。
[0019] 图3为本发明所采用的Ξ种25节点栅格网络。
[0020] 图4为本发明与其它方法可靠性评估精度对比。
[0021] 图5为本发明与其它方法可靠性评估消耗时间对比。
【具体实施方式】
[0022] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图及具体实施例对 本发明实施方式作进一步地详细描述。
[0023] 本发明是一种复杂网络可靠度的蒙特卡罗评估方法，针对复杂网络可靠度的计算 问题，采用事件驱动的EMC方法，为每条链路生成故障事件时刻，通过寻找最优先的故障时 刻和对应事件更新网络状态，进而驱动仿真，请参阅图1所示，本发明包括W下步骤：
[0024] 步骤S1:构建无向、无自环图G= (V，E)表示网络，V= {vi，V2，···，vi，···vn}为网络中 N个节点的集合，6={61，62，一，61，。'6|?}为1条链路(边）的集合。
[0025] 其中对无向、无自环图G=(V，E)网络做如下假设：
[0026] (1)网络为不可修网络；
[0027] (2)节点vi完全可靠；
[002引（3)链路ei存在"连通'和"故障'两种状态，分别表示为X (ei) = 1、X (ei) = 0。
[00巧](4)各链路状态相互独立。
[0030] (5)链路ei处于x(ei) = r谱通"状态的概率为p(ei)，即p(ei)为ei的连通可靠度； "故障'状态的概率为q(ei) = l-p(e〇。
[003。 网络状态向量记为X={x(ei)|eieE}，可得网络处于状态X的概率为（1)式：
[0032]
(1)
[0033] 定义1网络可靠度为网络处于连通状态的概率，用R(G)表示。
[0034] 定义2网络结构函数为Ψ(Χ)，若X状态是网络连通，记为事件Ψ(Χ) = 1，反之为Ψ (Χ)=〇;并设X的状态空间为S，共2?个元素，它是网络所有可能状态的全集。可得网络可靠 度为(2)式：
[0035]
(2)
[0036] 步骤S2:创建事件驱动模型，利于事件驱动的方法对复杂网络的可靠度进行蒙特 卡罗仿真，为了实现事件驱动的方法，具体包括如下四个部分：
[0037] (1)事件表化T，Event Table);
[0038] (2)用于描述各链路故障事件的时间指针(TP，Time Point);
[0039] (3)事件更新，用于更新网络状态和事件表；
[0040] (4)时间更新，用于更新最优先事件的时间指针。
[0041 ]基于上述设计和分析，定义如下事件表操作：
[00创 1)11136的化1'前，了口60:向61'中插入参数为佔，了口60的故障事件，事件更新。
[0043] 2)Remove化T，ei，TPei):删除ET中参数为(ei，TPei)的故障事件，事件更新。
[0044] 3)Get-TPmin化T):寻找并返回ET中最优先的时间指针TPmin，时间更新。
[0045] 步骤S3:事件驱动的随机分布取样。
[0046] 若对ei的链路状态x(ei)取样K次，用Yi表示链路故障事件的次数，即x(ei)=0的次 数。由于P(ei)恒定，故Yi是服从Binomial分布的随机变量：
[0047]
(3)
[004引取样具体分为两步：
[0049] (1)依据 K 和 p(ei)生成 Binomial 变量 Yi;
[0050] (2)在[0，Κ]区间内随机产生Yi个ei故障事件的时间指针TPei。
[0化1] 对于链路ei，传统的蒙特卡罗(CMC,化udeMC)通过K个随机变量U构造长度为K的状 态序列X(eiKEMC与CMC不同在于，EMC直接通过Yi的分布构造故障事件的时间指针序列 TPei，即隐含确定了X(ei)，如 图2所示。
[0化^ 步骤S4:初始化K，k = 0，为所有链路ei生成Yi个TPei，并Insed化了，ei，TTei)，寻找 最优先的故障时刻和对应事件，从而更新网络状态。
[0053] 其中，Κ是ei的链路状态x(ei)取样Κ次，k是X网络状态是连通时的累计次数。
[0054] 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6。
[00对步骤S6:置所有链路ei状态是连通的，即义佔）=1，了?。山=66*-了?。山化1')，寻找并返 回事件表中最优先的时间指针TPmin。
[0化6] 步骤S7:随机产生链路ei故障事件，若TPei = TPmin，则链路ei是故障状态，置x(e〇 =0，并Remove化T，ei，TPei)，在链路事件表中删除链路ei故障事件。
[0化7] 步骤S8:获得网络状态X，若Ψ (X) = 1，则k++;返回步骤S6。
[0化引步骤S9:求出网络可靠度估计值及。 乂
[0059] 为验证本发明的复杂网络可靠性评估准确性和效率，W25节点的栅格网络为例进 行仿真实验，W比较各种算法的优劣。运种栅格网络生成Ξ种栅格网络，链路总数分别为 40、56、72,网络复杂度逐渐增大，如图3所示，网络A、B、C。
[0060] 在相同硬件环境下，分别采用CMC和EMC方法对网络A进行可靠度仿真。参数:p(ei) = 0.99;θιΕΕ;Κ=106。分别记录Ξ种方法的估计结果和消耗时间，每种方法共仿真30次，并 根据30次统计值计算出各方法的估计标准差，结果如图4和图5所示。估计标准差如公式 (4)：
[0061] .
(4)
[0062] 其中，化r(R)是方差，公式如(5)所示。
[0063]
(5)
[0064] 依据因子定理，参考文献(赵彦，张新锋，徐国华.因子定理在计算机集成制造系统 网络可靠性分析中的应用[J].计算机集成制造系统，2005,11(12) :1621-1625.)可计算网 络A可靠度的精确值为R(G) = 0.99958。实验结果如图4所示，Ξ种方法的估计均值均收敛于 此精确值；同时EMC的标准差要略小。实验结果如图5所示，EMC算法不但消耗时间大幅小于 CMC,而且仿真效率显著提高。
[0065] 为比较各方法效率和网络规模、链路状态之间的关系，采用上述方法分别对图3中 的网络A、B、C和9(6〇=0.9、0.99、0.999进行九次仿真，实验结果如表1所示。
[0066] 表1不同网络状态下的仿真比较
[0067]
[0068] 由表1分析可知，当网络复杂度相同时，随着链路可靠度的增加，四种方法的消耗 时间均逐步减小，但EMC的减幅要远大于CMC、文献[1 ] (ADB化LAH K. Combining Network Reductions and Simulation to Estimate Network Reliability[C].Proceedings of the 2007Winter Simulation Conference ,Washington D.C. USA，Association for Computing Machinery,2007:2301-2305.)和文献[2KMANZI E，LAB邸 M，et al.Fishman's Sampling Plan for Computing Network Reliability[J]IEEE Trans.Reliability, 2001,50(1) :41-46.)的方法。运是由于在相同的样本容量下，EMC仿真需要产生更少的随机 种子；同时当可靠度较高时，EMC跳过了大量的"连通"事件，获得了更高的效率。同时，由于 文献[1]的缩减预处理存在适用局限性，对图3网络拓扑的简化作用有限，导致其时间消耗 与CMC基本相当（网络A与B略小）；文献[2]在取样之前需要进行网络割集计算，时间消耗最 大，且对链路可靠度变化不敏感，并验证了文献[2 ]取样预处理具有较高的复杂度。
[0069] 当链路可靠度相同时，随着网络复杂度的增加，五种方法的消耗时间逐步增大，同 时估计标准差具有逐步减小的趋势。网络复杂度增大，各方法需要处理的状态向量维数将 增大，时间消耗也相应增大。由CMC方法的如下（5)式可W发现，当链路可靠度较大时，p(ei) t，R(G)T，Std?EL与表1仿真结果相吻合。
[0070] 当链路可靠度与网络复杂度均相同时，在运四种方法中，文献[2]估计精度最高， 利用割集的预处理，将问题转化为割集的分部仿真，压缩了取样维度，具有较低的估计方 差。但是，文献[2]估计精度的提升幅度较小，而时间消耗则比EMC高出近一个数量级。运种 通过牺牲效率换取精度提升的策略，需要结合实际应用进行具体权衡。
[0071] W上是本发明的较佳实施例，凡在本发明的精神和原则之内，所作的任何修改、等 同替换等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种复杂网络可靠度的蒙特卡罗评估方法，其特征在于，该方法包括如下步骤： 步骤SI:构建无向、无自环图G= (V，E)表示网络，统计网络中的所有节点和链路(边）， 为每个节点顺序编号为Vi，设节点总数为N，V ={ VI，V2，…，Vi，…vn}为网络中N个节点的集 合，I <i<N，为每条边顺序编号为ei，链路总数为M，E={ei，e2,…， ei，…θμ}为M条链路(边） 的集合，l<i SM; 步骤S2:创建事件驱动模型； 步骤S3:事件驱动的随机分布取样； 步骤S4:为所有链路生成故障事件时刻，并向事件表中插入故障事件； 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6; 步骤S6:置所有链路状态是连通的，获得最优先的时间指针； 步骤S7:将故障链路事件从事件表中删除； 步骤S8:统计网络状态X连通状态的次数k，并返回步骤S6; 步骤S9:求出网络可靠度估计值2. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S2所述 的创建事件驱动模型的建立方法，其特征在于包括如下四个部分： (1) 事件表(ET，Event Table); (2) 用于描述各链路故障事件的时间指针(TP，Time Point); (3) 事件更新，用于更新网络状态和事件表； (4) 时间更新，用于更新最优先事件的时间指针。3. 根据权利要求2所述的创建事件驱动模型的建立方法，其特征在于定义如下事件表 操作： 1. Insert(ET，ei，TPei):向ET中插入参数为(ei，TPei)的故障事件，事件更新。 2. Remove(ET，ei，TPei):删除ET中参数为(ei，TPe i)的故障事件，事件更新。 3. Get-TPmin(ET):寻找并返回ET中最优先的时间指针TPmin，时间更新。4. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S3所述 的事件驱动的随机分布取样，其特征在于： 对01的链路状态x(ei)取样K次，用Y1表示链路故障事件的次数，即x( ei) = 0的次数。由于 P(ei)恒定，故Yi是服从Binomial分布的随机变量：其中，P(ei)为链路ei处于x(ei) = l"连通"状态的概率，即p(ei)为^的连通可靠度；q (ei) = 1-p (ei)为"故障"状态的概率。5. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S3所述 的事件驱动的随机分布取样，具体按如下步骤进行： (3a)依据K和p (ei)生成Binomial变量Yi; (3b)在[0，K ]区间内随机产生Yi个ei故障事件的时间指针TPei。
【专利摘要】本发明公开了一种复杂网络可靠度的蒙特卡罗评估方法，实现该方法主要包括以下步骤：首先构建整个网络的无向、无自环图，创建事件驱动模型，对链路状态随机取样K次，为每条链路生成故障事件时刻，并向事件表中插入故障事件，然后对事件表判断，如果为空，求出网络可靠度估计值，否则，置所有链路状态是连通的，获得最优先的时间指针，当随机产生链路故障事件的时间指针值为最优先的时间指针时，则链路是故障状态，并在链路事件表中删除故障事件，获得网络状态，若网络状态是连通状态，则自动累计其次数，并返回对事件表进行判断。本发明提出的复杂网络可靠度评估方法不但比其他算法更具优越性和更高的仿真效率，而且在保持估计精度的前提下，大幅降低了复杂度。
【IPC分类】H04L12/24, H04L12/26
【公开号】CN105490836
【申请号】CN201510823631
【发明人】陈雪刚, 李明鲜, 王薪竹, 朱颖弘
【申请人】湘南学院
【公开日】2016年4月13日
【申请日】2015年11月19日
【技术领域】
[0001] 本发明属于计算机技术领域，设及网络可靠度的计算问题，尤其设及一种网络可 靠度的蒙特卡罗评估方法。
【背景技术】
[0002] 随着网络的高速发展，网络已成为人类生产、生活不可或缺的一部分，运些复杂网 络包括医疗网络、教育网络、电网、输油输气管道网络、无线传感器网络等有线网络和无线 网络。随着网络规模的不断扩大，网络的结构越来越复杂。网络的设计可能需要随时根据网 络可靠度的计算结果对网络进行调整和优化，如增删一些链路、结点或者改变一些结点的 位置，如果缺乏可靠性的准确评估，工程人员设计出的网络将面临很多安全隐患，给网络管 理、维护和修复带来很多不确定性，甚至一旦发生故障，将造成重大甚至灾难性影响。网络 可靠性是保证网络安全因素的重要方面，尤其是近年来，网络安全问题日益成为国际社会 关注焦点，针对我国现状急需加强自身网络建设和可靠性评估，提高基础网络的安全性。网 络可靠性评估也是度量网络安全程度的重要手段，通过加强复杂网络可靠性研究能有效提 升网络建设和管理能力，有利于提高网络安全系数，有利于提高网络的生存性和抗毁性，有 利于增强复杂网络可靠性，减少网络的故障概率W及网络资源浪费，因此针对复杂网络可 靠性评估具有极其重要的现实意义。
[0003] 大型复杂网络系统可靠度精确计算是一个NP-hard问题，如何对其进行快速、精确 的计算是可靠度研究的重点与热点。从网络可靠性计算精确性角度分析，现有的网络可靠 度计算方法可分为两类:精确计算和近似计算。精确计算方法主要包括因子分解、二元决策 图，不交最小路方法、不交最小割方法、排序二分决策图、状态枚举法和容斥原理法等方法， 运些精确可靠度求解算法随着网络的增大其复杂程度呈指数增长趋势，运类算法往往大多 只能适用于中、小型网络的可靠度分析，对于大型复杂工程网络系统，会因网络复杂性而无 法求解或者计算量快速膨胀，算法的计算效率变得低下；另一类是近似估计与抽样仿真的 方法，近似计算方法通过计算可靠度边界值来逼近精确值，尤其随着网络规模越来越大的 客观现实，采用近似估计的方法就受到重视和青睐，该类方法主要有可靠度上下界、蒙特卡 罗(MC，Monte化rlo)法等方法，上下界法在确定较理想的可靠度界值范围时，而且往往W 牺牲计算复杂度为代价进行权衡；蒙特卡罗法是W概率统计实验为基础的仿真方法，能够 真实地模拟实际物理过程，解决一些系统过于复杂而难W建立精确数学模型的问题，具有 直观、复杂度低的优点，广泛应用于大型网络的仿真研究。
【发明内容】
[0004] 本发明的目的在于提供一种复杂网络可靠度的评估方法，该方法有利于减少时间 复杂度和提高计算效率。
[0005] 为了实现上述目的，本发明提出了一种复杂网络可靠度的蒙特卡罗评估方法，该 方法采用事件驱动的蒙特卡罗评估法EM(XEvent-driven MC)，为每条链路生成故障事件时 亥Ij，通过寻找最优先的故障时刻和对应事件更新网络状态，进而实现复杂网络的可靠性评 估。
[0006] 本发明提出的一种网络可靠度的蒙特卡罗评估方法，具体包括如下步骤：
[0007] 步骤S1:构建整个网络的无向、无自环图，统计网络中的所有节点和链路(边），为 每个节点顺序编号为VI，设节点总数为N，1 y如;为每条边顺序编号为ei，链路总数为M，1 < i <1。
[000引步骤S2:创建事件驱动模型。
[0009]步骤S3:基于事件驱动的概率分布取样。
[0010]步骤S4:为每条链路生成故障事件时刻，为所有链路ei生成Yi个TPei，并在链路事 件表中插入链路ei事件。
[0011] 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6。
[0012] 步骤S6:置所有链路ei状态是连通的，寻找并返回事件表中最优先的时间指针 TPmino
[0013] 步骤S7:当随机产生链路ei故障事件的时间指针值为TPmin，则链路ei是故障状态， 并在链路事件表中删除链路ei故障事件。
[0014] 步骤S8:获得网络状态X，若X状态是网络连通，则累计其次数，并返回步骤S5。
[0015] 步骤S9:求出网络可靠度估计值。
[0016] 本发明针对复杂网络结构可靠度的评价问题，提出了一种基于网络故障事件驱动 的蒙特卡罗评估方法。该方法通过产生各链路故障事件的时间指针，来构建网络的事件表。 通过更新事件表驱动网络状态的更新，在保持了估计精度的前提下，大幅降低了复杂度，是 处理大型网络和可靠度极值问题的有效仿真方法。
【附图说明】
[0017] 图1为本发明的一种复杂网络可靠度的蒙特卡罗评估方法流程图。
[001引图2为本发明方法的EMC与CMC取样示意图。
[0019] 图3为本发明所采用的Ξ种25节点栅格网络。
[0020] 图4为本发明与其它方法可靠性评估精度对比。
[0021] 图5为本发明与其它方法可靠性评估消耗时间对比。
【具体实施方式】
[0022] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图及具体实施例对 本发明实施方式作进一步地详细描述。
[0023] 本发明是一种复杂网络可靠度的蒙特卡罗评估方法，针对复杂网络可靠度的计算 问题，采用事件驱动的EMC方法，为每条链路生成故障事件时刻，通过寻找最优先的故障时 刻和对应事件更新网络状态，进而驱动仿真，请参阅图1所示，本发明包括W下步骤：
[0024] 步骤S1:构建无向、无自环图G= (V，E)表示网络，V= {vi，V2，···，vi，···vn}为网络中 N个节点的集合，6={61，62，一，61，。'6|?}为1条链路(边）的集合。
[0025] 其中对无向、无自环图G=(V，E)网络做如下假设：
[0026] (1)网络为不可修网络；
[0027] (2)节点vi完全可靠；
[002引（3)链路ei存在"连通'和"故障'两种状态，分别表示为X (ei) = 1、X (ei) = 0。
[00巧](4)各链路状态相互独立。
[0030] (5)链路ei处于x(ei) = r谱通"状态的概率为p(ei)，即p(ei)为ei的连通可靠度； "故障'状态的概率为q(ei) = l-p(e〇。
[003。 网络状态向量记为X={x(ei)|eieE}，可得网络处于状态X的概率为（1)式：
[0032]
(1)
[0033] 定义1网络可靠度为网络处于连通状态的概率，用R(G)表示。
[0034] 定义2网络结构函数为Ψ(Χ)，若X状态是网络连通，记为事件Ψ(Χ) = 1，反之为Ψ (Χ)=〇;并设X的状态空间为S，共2?个元素，它是网络所有可能状态的全集。可得网络可靠 度为(2)式：
[0035]
(2)
[0036] 步骤S2:创建事件驱动模型，利于事件驱动的方法对复杂网络的可靠度进行蒙特 卡罗仿真，为了实现事件驱动的方法，具体包括如下四个部分：
[0037] (1)事件表化T，Event Table);
[0038] (2)用于描述各链路故障事件的时间指针(TP，Time Point);
[0039] (3)事件更新，用于更新网络状态和事件表；
[0040] (4)时间更新，用于更新最优先事件的时间指针。
[0041 ]基于上述设计和分析，定义如下事件表操作：
[00创 1)11136的化1'前，了口60:向61'中插入参数为佔，了口60的故障事件，事件更新。
[0043] 2)Remove化T，ei，TPei):删除ET中参数为(ei，TPei)的故障事件，事件更新。
[0044] 3)Get-TPmin化T):寻找并返回ET中最优先的时间指针TPmin，时间更新。
[0045] 步骤S3:事件驱动的随机分布取样。
[0046] 若对ei的链路状态x(ei)取样K次，用Yi表示链路故障事件的次数，即x(ei)=0的次 数。由于P(ei)恒定，故Yi是服从Binomial分布的随机变量：
[0047]
(3)
[004引取样具体分为两步：
[0049] (1)依据 K 和 p(ei)生成 Binomial 变量 Yi;
[0050] (2)在[0，Κ]区间内随机产生Yi个ei故障事件的时间指针TPei。
[0化1] 对于链路ei，传统的蒙特卡罗(CMC,化udeMC)通过K个随机变量U构造长度为K的状 态序列X(eiKEMC与CMC不同在于，EMC直接通过Yi的分布构造故障事件的时间指针序列 TPei，即隐含确定了X(ei)，如 图2所示。
[0化^ 步骤S4:初始化K，k = 0，为所有链路ei生成Yi个TPei，并Insed化了，ei，TTei)，寻找 最优先的故障时刻和对应事件，从而更新网络状态。
[0053] 其中，Κ是ei的链路状态x(ei)取样Κ次，k是X网络状态是连通时的累计次数。
[0054] 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6。
[00对步骤S6:置所有链路ei状态是连通的，即义佔）=1，了?。山=66*-了?。山化1')，寻找并返 回事件表中最优先的时间指针TPmin。
[0化6] 步骤S7:随机产生链路ei故障事件，若TPei = TPmin，则链路ei是故障状态，置x(e〇 =0，并Remove化T，ei，TPei)，在链路事件表中删除链路ei故障事件。
[0化7] 步骤S8:获得网络状态X，若Ψ (X) = 1，则k++;返回步骤S6。
[0化引步骤S9:求出网络可靠度估计值及。 乂
[0059] 为验证本发明的复杂网络可靠性评估准确性和效率，W25节点的栅格网络为例进 行仿真实验，W比较各种算法的优劣。运种栅格网络生成Ξ种栅格网络，链路总数分别为 40、56、72,网络复杂度逐渐增大，如图3所示，网络A、B、C。
[0060] 在相同硬件环境下，分别采用CMC和EMC方法对网络A进行可靠度仿真。参数:p(ei) = 0.99;θιΕΕ;Κ=106。分别记录Ξ种方法的估计结果和消耗时间，每种方法共仿真30次，并 根据30次统计值计算出各方法的估计标准差，结果如图4和图5所示。估计标准差如公式 (4)：
[0061] .
(4)
[0062] 其中，化r(R)是方差，公式如(5)所示。
[0063]
(5)
[0064] 依据因子定理，参考文献(赵彦，张新锋，徐国华.因子定理在计算机集成制造系统 网络可靠性分析中的应用[J].计算机集成制造系统，2005,11(12) :1621-1625.)可计算网 络A可靠度的精确值为R(G) = 0.99958。实验结果如图4所示，Ξ种方法的估计均值均收敛于 此精确值；同时EMC的标准差要略小。实验结果如图5所示，EMC算法不但消耗时间大幅小于 CMC,而且仿真效率显著提高。
[0065] 为比较各方法效率和网络规模、链路状态之间的关系，采用上述方法分别对图3中 的网络A、B、C和9(6〇=0.9、0.99、0.999进行九次仿真，实验结果如表1所示。
[0066] 表1不同网络状态下的仿真比较
[0067]
[0068] 由表1分析可知，当网络复杂度相同时，随着链路可靠度的增加，四种方法的消耗 时间均逐步减小，但EMC的减幅要远大于CMC、文献[1 ] (ADB化LAH K. Combining Network Reductions and Simulation to Estimate Network Reliability[C].Proceedings of the 2007Winter Simulation Conference ,Washington D.C. USA，Association for Computing Machinery,2007:2301-2305.)和文献[2KMANZI E，LAB邸 M，et al.Fishman's Sampling Plan for Computing Network Reliability[J]IEEE Trans.Reliability, 2001,50(1) :41-46.)的方法。运是由于在相同的样本容量下，EMC仿真需要产生更少的随机 种子；同时当可靠度较高时，EMC跳过了大量的"连通"事件，获得了更高的效率。同时，由于 文献[1]的缩减预处理存在适用局限性，对图3网络拓扑的简化作用有限，导致其时间消耗 与CMC基本相当（网络A与B略小）；文献[2]在取样之前需要进行网络割集计算，时间消耗最 大，且对链路可靠度变化不敏感，并验证了文献[2 ]取样预处理具有较高的复杂度。
[0069] 当链路可靠度相同时，随着网络复杂度的增加，五种方法的消耗时间逐步增大，同 时估计标准差具有逐步减小的趋势。网络复杂度增大，各方法需要处理的状态向量维数将 增大，时间消耗也相应增大。由CMC方法的如下（5)式可W发现，当链路可靠度较大时，p(ei) t，R(G)T，Std?EL与表1仿真结果相吻合。
[0070] 当链路可靠度与网络复杂度均相同时，在运四种方法中，文献[2]估计精度最高， 利用割集的预处理，将问题转化为割集的分部仿真，压缩了取样维度，具有较低的估计方 差。但是，文献[2]估计精度的提升幅度较小，而时间消耗则比EMC高出近一个数量级。运种 通过牺牲效率换取精度提升的策略，需要结合实际应用进行具体权衡。
[0071] W上是本发明的较佳实施例，凡在本发明的精神和原则之内，所作的任何修改、等 同替换等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种复杂网络可靠度的蒙特卡罗评估方法，其特征在于，该方法包括如下步骤： 步骤SI:构建无向、无自环图G= (V，E)表示网络，统计网络中的所有节点和链路(边）， 为每个节点顺序编号为Vi，设节点总数为N，V ={ VI，V2，…，Vi，…vn}为网络中N个节点的集 合，I <i<N，为每条边顺序编号为ei，链路总数为M，E={ei，e2,…， ei，…θμ}为M条链路(边） 的集合，l<i SM; 步骤S2:创建事件驱动模型； 步骤S3:事件驱动的随机分布取样； 步骤S4:为所有链路生成故障事件时刻，并向事件表中插入故障事件； 步骤S5:判断事件表是否为空，如果为空，执行步骤S9，否则执行步骤S6; 步骤S6:置所有链路状态是连通的，获得最优先的时间指针； 步骤S7:将故障链路事件从事件表中删除； 步骤S8:统计网络状态X连通状态的次数k，并返回步骤S6; 步骤S9:求出网络可靠度估计值2. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S2所述 的创建事件驱动模型的建立方法，其特征在于包括如下四个部分： (1) 事件表(ET，Event Table); (2) 用于描述各链路故障事件的时间指针(TP，Time Point); (3) 事件更新，用于更新网络状态和事件表； (4) 时间更新，用于更新最优先事件的时间指针。3. 根据权利要求2所述的创建事件驱动模型的建立方法，其特征在于定义如下事件表 操作： 1. Insert(ET，ei，TPei):向ET中插入参数为(ei，TPei)的故障事件，事件更新。 2. Remove(ET，ei，TPei):删除ET中参数为(ei，TPe i)的故障事件，事件更新。 3. Get-TPmin(ET):寻找并返回ET中最优先的时间指针TPmin，时间更新。4. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S3所述 的事件驱动的随机分布取样，其特征在于： 对01的链路状态x(ei)取样K次，用Y1表示链路故障事件的次数，即x( ei) = 0的次数。由于 P(ei)恒定，故Yi是服从Binomial分布的随机变量：其中，P(ei)为链路ei处于x(ei) = l"连通"状态的概率，即p(ei)为^的连通可靠度；q (ei) = 1-p (ei)为"故障"状态的概率。5. 根据权利要求1所述的一种复杂网络可靠度的蒙特卡罗评估方法，其中步骤S3所述 的事件驱动的随机分布取样，具体按如下步骤进行： (3a)依据K和p (ei)生成Binomial变量Yi; (3b)在[0，K ]区间内随机产生Yi个ei故障事件的时间指针TPei。
【专利摘要】本发明公开了一种复杂网络可靠度的蒙特卡罗评估方法，实现该方法主要包括以下步骤：首先构建整个网络的无向、无自环图，创建事件驱动模型，对链路状态随机取样K次，为每条链路生成故障事件时刻，并向事件表中插入故障事件，然后对事件表判断，如果为空，求出网络可靠度估计值，否则，置所有链路状态是连通的，获得最优先的时间指针，当随机产生链路故障事件的时间指针值为最优先的时间指针时，则链路是故障状态，并在链路事件表中删除故障事件，获得网络状态，若网络状态是连通状态，则自动累计其次数，并返回对事件表进行判断。本发明提出的复杂网络可靠度评估方法不但比其他算法更具优越性和更高的仿真效率，而且在保持估计精度的前提下，大幅降低了复杂度。
【IPC分类】H04L12/24, H04L12/26
【公开号】CN105490836
【申请号】CN201510823631
【发明人】陈雪刚, 李明鲜, 王薪竹, 朱颖弘
【申请人】湘南学院
【公开日】2016年4月13日
【申请日】2015年11月19日
最新回复(0)