基于启发式算法的网络可靠性分配方法

李瑞莹 任武越

（北京航空航天大学 可靠性与系统工程学院，北京 100191）

基于启发式算法的网络可靠性分配方法

李瑞莹 任武越

（北京航空航天大学 可靠性与系统工程学院，北京 100191）

由于网络的结构特殊性，已有的经典可靠性分配方法难以直接应用.在AGREE（Advisory Group on Reliability of Electronic Equipment）方法的基础上，根据网络可靠性与部件可靠性的函数关系确定网络部件重要度，运用启发式算法逐步迭代实现了网络k/N端可靠性分配，解决了无法对网络应用串联模型开展可靠性分配的问题.以中国教育网（CERNET，China Education and Research Network）骨干网为案例，应用该方法实现了75%网络节点连通可靠性指标的分配，并进一步分析了迭代终止条件、网络可靠性指标要求等参数对分配结果的影响，通过绘制可靠性随时间变化的曲线证明了分配结果能满足网络可靠性指标要求，说明了该方法的正确性和适用性.

网络;可靠性;启发式算法;二分搜索法

通过可靠性分配，可以把订购方提出的系统可靠性指标，自上而下，由大到小，从整体到局部，逐步分配到各分系统及设备.可靠性分配是系统论证、方案设计乃至工程研制阶段的重要工作，用于确定分系统、设备可靠性指标.一般，系统可靠性分配方法主要包括等分配法、评分分配法、比例组合法、层次分析法、AGREE（Advisory Group on Reliability of Electronic Equipment）法（即:考虑重要度和复杂度的分配法）等［1］.对网络而言，可靠性分配也是重要工作项目，根据网络可靠性指标来确定网络部件可靠性指标要求.然而，考虑到网络拓扑结构的特殊性，简单地由串联、并联、旁联、n中取r等模型组成的可靠性框图并不能直接应用于网络可靠性建模，这也直接给网络可靠性分配的实现带来了困难.

研究者对网络可靠性分配开展了大量研究.文献［2］通过容斥原理法建立网络可靠性与部件可靠性的函数关系 Rs=f（R1，R2，…，Rn），根据Ii=∂Rs/∂Ri确定部件重要度，并进一步根据最优分配法实现网络可靠性分配.文献［3］对最优分配问题进行了详细的总结，虽然最优分配法在理论计算上表现出诸多优势，但该方法以费用、重量等参数作为约束条件或优化目标，在系统设计早期相关的数据往往难以获取，故而工程上应用并不多.文献［4］针对矿井通风网络研究了可靠性的比例组合分配法，然而，工程实践中使用比例组合法的前提是要有相似系统，对网络来说，其拓扑结构组成形式多样，往往难于找到相似网络.文献［5］针对C4ISR系统应用了AGREE分配法，为了适应网络的拓扑结构，通过频率、交换速度、数据大小定义了部件的重要度，为基于AGREE法的网络可靠性分配提供了新思路.然而，这里的重要度定义并没有考虑网络中大量存在的路径冗余，其可靠性分配结果尚缺少对网络连通能力的考量.

在众多经典的可靠性分配方法中，等分配法完全不考虑网络结构，实际工程上不可用;评分分配法主观性强，极大程度上依赖于专家的智慧;比例组合法能否使用取决于是否存在相似网络，这一前提条件过于苛刻;层次分析法的缺陷与专家评分法类似，只是采用数学验证手段，在一定程度上限制了评分人犯错误的可能性;最优分配法所需考虑因素较多，除可靠性外还需结合费用、重量等信息，在这些信息未知的情况下无法应用;AGREE法综合考虑了部件故障对系统故障的影响（即部件重要度）以及部件设计的复杂度，是工程中大量使用的可靠性分配方法［6］，但其使用前提要求分系统是串联结构，显然网络对象无法满足这一前提条件，这对AGREE分配法在网络可靠性中的应用造成了障碍.

为此，本文在AGREE方法的基础上，根据网络可靠性与部件可靠性的函数关系确定网络部件重要度，运用二分搜索法确定基于重要度和复杂度的部件可靠性分配结果，并通过启发式算法逐步迭代实现网络k/N端可靠性分配结果的收敛，可有效支持网络系统开展可靠性分配工作.

1 基本参数

网络可靠性是指网络在规定条件下和规定时间内，完成规定功能的能力.对网络而言，最重要的就是网络连通功能.连通可靠性［7］成为网络的重要指标，其表示网络在规定条件下和规定时间内的连通能力.

将网络表示为G（V，E），其中V表示网络的节点集合，E表示网络的链路集合.考虑到所度量的节点范围不同，常用的连通可靠性度量参数包括:k/N端可靠度、K端可靠度、全端可靠度和两端可靠度.

其中，k/N 端可靠度［8］表示网络 G（V，E）在规定条件下和规定时间内，节点子集N（含n个节点）中至少k个节点之间能连通的概率（其中，N⊂V;2≤k≤n）.k/N端可靠度可表示为

式中，Rk/N（t）是t时刻网络G（V，E）的k/N端可靠度;ξk/N是节点子集N中能相互连通的节点个数少于k前的工作时间;t是网络规定的时间.

特殊地，当k=n时，k/N端可靠度就是K端可靠度，表示网络中指定节点子集K中所有节点之间保持连通的概率;当N=V，且k=n时，k/N端可靠度就是全端可靠度，表示网络中所有节点之间保持连通的能力;当n=2时，k/N端可靠度就是两端可靠度，表示网络中两个指定节点之间保持连通的能力.也就是说，K端可靠度、全端可靠度和两端可靠度都是k/N端可靠度的特殊情况.

2 算法

2.1AGREE分配法

AGREE分配法根据各单元产品的重要程度、复杂程度进行可靠性指标分配的方法.AGREE方法仅适用于由若干串联的分系统组成的系统，而分系统内部可以由串联、并联、旁联、n中取r等各类关系的部件组成.假设部件的寿命服从指数分布，具体的分配方法如下:

式中，ti为第i个部件的工作时间;Ci为第i个部件的复杂度:

其中，N为整个系统的基本构成单元个数;ni为第i个部件的基本构成单元个数.

ωi为第i个部件的重要度，反应了第i个部件故障影响任务完成的程度:

其中，Ii表示由于第i个部件故障引起系统故障的次数;Fi表示第i个部件故障的次数.

2.2 AGREE分配法的改进

AGREE分配法体现了可靠性分配的2个基本原则:①对复杂程度高的部件，分配较低的可靠性指标;②对重要度高的部件，分配较高的可靠性指标.

由于网络一般无法表示为串联结构，故而无法直接使用式（2）实现可靠性分配.这里仍然假设网络中各个部件的寿命均服从指数分布，为了体现AGREE分配法的2个基本原则，要求:

在网络对象上实现基于式（5）的可靠性分配，需要解决两个问题:一是如何确定网络部件的重要度;二是如何得出部件的分配结果.

对问题一，由于式（4）表达的重要度计算公式是基于统计数据的，无法解析计算，这里运用文献［2］中使用的概率重要度:

上式反映了部件可靠度变化对系统可靠度的影响.

对问题二，由于Ri=exp（－λiti），部件可靠性分配结果和部件重要度在式（5）和式（6）中相互引用，这里应用启发式算法反复迭代计算，算法如下:

1）应用状态枚举法、容斥原理、不交积和、因子分解等方法［9］确定网络系统可靠性与部件可靠性的函数关系 Rs=f（R1，R2，…，Rn）;

2）令部件初始重要度相同ω1=ω2=…=ωm=1，根据部件所包含元件数量应用式（3）确定部件复杂度Ci，并确定部件工作时间ti;

3）根据ai=Ci/（ωiti）计算出部件故障率系数ai，令部件故障率λi=aiX（其中，X为常数），即Ri=exp（－λiti）=exp（－aitiX），应用二分搜索法［10］求解满足式（7）的 X.

3 案例

下面以中国教育网（CERNET，China Education and Research Network）骨干网为例进行可靠性分配，CERNET骨干网拓扑结构如图1所示.

图1 CERNET骨干网拓扑结构

令CERNET的考察节点为全部8个骨干节点，即指定节点集N={北京，沈阳，西安，成都，武汉，南京，上海，广州}，要求该网络在运行1 a时间以后75%骨干网节点的连通可靠度至少要达到0.99，即 R*6/N（365×24）≥0.99.下面采用本文的方法进行可靠性分配，确定各节点可靠度指标Ri.假设节点故障服从指数分布，链路绝对可靠.

首先运用状态空间枚举法，确定网络系统可靠性与部件可靠性的函数关系:

应用2.2节提出的算法，迭代9次达到迭代终止条件ε=0.001.表1是逐次迭代得到的CERNET骨干网各节点可靠性分配结果，表中阴影表示与前次可靠度分配值之差超过ε=0.001的节点.由此看出，随着迭代过程分配结果逐渐趋于稳定.最后一次迭代结果为CERNET可靠性分配结果，即要求各节点运行1 a后的可靠度达到:

表1 CERNET骨干网节点可靠性分配迭代结果

历次迭代过程中各节点的可靠度分配结果与最终分配结果的均方误差随着迭代次数的增多，逐渐减小，如图2所示.这说明本文提出的基于启发式的算法在案例应用中具有良好的收敛性.

图2 CERNET骨干网可靠性分配迭代过程的均方误差

分配完成后，应用 Rs=f（R1，R2，…，Rn）计算出网络可靠度随时间的变化关系如图3所示.由于迭代过程中始终需要满足R*s≤f（R1，R2，…，Rn），故而网络在运行1 a时间后75%骨干网节点的连通可靠度至少达到0.95的指标要求必然可以达到.

迭代终止条件ε的选取对分配效率和分配精度有影响.ε越小，所需迭代次数越大，计算时间越长.当ε小到某种程度时，迭代次数和计算时间会迅速增加，如表2所示.

图3 CERNET骨干网可靠度随时间变化情况

表2 ε取值对迭代次数的影响

这里的计算时间是由MATLAB程序执行得来的.同时，表2的结果还反映出，在本案例中迭代终止条件ε的选取对本文提出的启发式算法的收敛性不产生影响.

当网络可靠性要求值不同时，各节点的分配结果不同，如图4所示.由于北京节点的重要性，随着网络可靠性指标要求的下降，北京节点可靠度分配结果的下降幅度远小于其他节点.

图4 CERNET骨干网可靠性指标不同时的分配结果

4 结束语

可靠性分配是网络系统论证和设计过程中的重要工作，然而目前工程常用的可靠性分配方法要么依赖于相似产品数据、依赖于专家经验;要么受到网络结构限制，并不能直接应用到网络中.本文以经典的AGREE方法为基础，研究了基于启发式算法的网络可靠性分配方法，根据网络可靠性与部件可靠性的函数关系确定网络部件重要度，运用二分搜索法确定基于重要度和复杂度的部件分配结果，通过启发式算法逐次逼近，可有效地解决网络k/N端可靠性分配问题，算法同时考虑了部件重要性和复杂性，并且编写了基于MATLAB的计算程序，兼顾了工程操作性.

本算法的适用条件为:①网络部件寿命服从指数分布;②能够获得网络系统可靠性与部件可靠性的函数关系式.

通过CERNET案例研究，实现了对网络75%节点连通可靠性的分配.随着迭代次数增多，均方误差逐渐减小，表现出良好的收敛性.

本方法具有良好扩充性.对于一些特殊情况，如要求网络中某些部件沿用可靠度已知的老部件，本方法也可将这些部件作为已知条件，参与迭代计算.然而，网络可靠性的解析计算已被证明为NP（Nondeterministic Polynomial）难问题［11］，对于大规模网络往往不容易建立网络可靠性与部件可靠性的函数关系，这导致根据式（6）计算部件重要度的使用受限，可以通过蒙特卡洛仿真统计部件重要度的方式实现，这也是下一步需要研究的问题.

（References）

［1］康锐，石荣德，李瑞莹.型号可靠性维修性保障性技术规范:第2册［M］.北京:国防工业出版社，2010:38－70

Kang Rui，Shi Rongde，Li Ruiying.Reliability，maintainability and supportability specifications for material:volumeⅡ［M］.Beijing:National Defense Industry Press，2010:38－70（in Chinese）

［2］Adamantios Mettas.Reliability allocation and optimization for complex systems［C］//Proceedings Annual Reliability and Maintainability Symposium.Los Angeles，CA，USA:［s.n.］，2000:216－221

［3］Way Kuo，Rui Wan.Recent advances in optimal reliability allocation ［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part A:Systems and Humans，2007，37（2）:143－156

［4］王洪德，马云东.基于网络模型的通风系统可靠性分配方法研究［J］.煤，2003，12（3）:4－6

Wang Hongde，Ma Yundong.Study on reliability and it’s distribution technique of ventilation system based on network model［J］.Coal，2003，12（3）:4－6（in Chinese）

［5］郭浩.基于体系结构的C4ISR系统可靠性建模及分配方法研究［D］.长沙:国防科技大学信息系统与管理学院，2008

Guo Hao.Research on reliability modeling and allocation method of C4ISR system based on architecture［D］.Changsha:School of Information Managment and Systems，National University of Defense Technology，2008（in Chinese）

［6］Wang Yabin，Jia Xisheng，Zhao Jianmin，et al.Improvement of AGREE allocation method［C］//8th International Conference on Reliability，Maintainability and Safety.Chengdu，China:［s.n.］，2009:293－295

［7］Debany W H，Varshney P K，Hartmann C R P.Network reliability evaluation using probability expressions［J］.IEEE Transaction on Reliability，1986，35（2）:161－166

［8］Li Ruiying，Huang Ning，Kang Rui.A new parameter and its algorithm for network connection reliability:k/N-terminal reliability［C］//First International Conference on Future Information Networks.Beijing，China:［s.n.］，2009:259－262

［9］Douglas R Shier.Network reliability and algebraic structures［M］.Oxford:Clarendon Press，1991:8－17

［10］Jon Kleinberg，Eva Tardos.算法设计［M］.张立昂，屈婉玲译.北京:清华大学出版社，2007

Jon Kleinberg，Eva Tardos.Algorithm design［M］.Translated by Zhang Li'ang，Qu Wanling.Beijing:Tsinghua University Press，2007（in Chinese）

［11］Michael O Ball.Complexity of network reliability computations［J］.Networks，1980，10（2）:153－165

Network reliability allocation method based on heuristic algorithm

Li Ruiying Ren Wuyue
（School of Reliability and Systems Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China）

As network structure is difficult to be described with series and parallel models.Those traditional reliability allocation methods cannot be used by networks directly.A new method based on heuristic algorithm was advanced to solve the k/N terminal reliability allocation problem.Like advisory group on reliability of electronic equipment（AGREE）method，the new method also concerns about component importance and complexity.The component importance was calculated by taking partial derivatives of the function that relates component reliabilities to network reliability.The component complexity depends on the parts number which it owns.It solves the problem that the network reliability cannot be allocated by AGREE method with simple series models.This new method was applied to China education and research network（CERNET）backbone.Its reliability requirement，the connection probability among 75%of nodes，was allocated.It also discussed the affection to reliability allocation if some parameters，such as iteration termination value and network reliability requirements，shift.The curve of reliability over time verifies that the allocation results can meet reliability requirement of CERNET.The case study illustrates the applicability and correctness of this new allocation method.

networks;reliability;heuristic algorithms;binary search

TB 114.3

A

1001-5965（2012）02-0228-05

2010-10-29;< class="emphasis_bold">网络出版时间:

时间:2012-02-21 11:47;

CNKI:11-2625/V.20120221.1147.021

www.cnki.net/kcms/detail/11.2625.V.20120221.1147.021.html

北京市自然基金资助项目（4113074）

李瑞莹（1982－），女，四川成都人，讲师，liruiying@buaa.edu.cn.

（编 辑:娄 嘉）