基于路集矩阵与布尔运算的网络可靠度算法

具有节点失效的网络可靠度的信息交互算法武小悦　张维明　沙基昌(国防科技大学系统工程与数学系　长沙　410073) 摘　要　提出了一种用于计算具有节点失效的网络可靠度的新计算方法。

该算法依据不交化代数及协同计算的思想,采用节点信息义互的方法直接获得网络的不交化最小路集。

算法简便易行,具有分布计算的特点,为大型网络系统的可靠性度计算提供了一种新的途径。

关键词　网络可靠度,协同计算,算法,最小路集分类号　O 213.2Information Exchanging Algorithm for Reliability of Network with Node FailureWu Xia oyue Zhang Weiming Sha Jichang(Depar tment of Sy stems Eng ineering and M athematics,NU DT ,Chang sha ,410073)Abstract A new alg or ithm fo r co mputing r elia bility o f netw or k with no de failur e is pr esented in t his paper .Based on t he pr inciple of disjo int alg ebra and sy ner g etic co mput ing,the disjoint minimal path set is go tten directly by means of node info rm atio n ex chang ing .T he algo rithm is simple and chara ct erized by distr ibut ed co mput ing .It pr ov ides a new appr oach to comput ing r eliability of larg e scale netw or k.Key words netw or k reliability,syner getic co mputing,algo rithm,minimal path set网络系统的可靠性有多种含义,端端可靠度是指给定的两个节点能正常连通的概率,反映了网络的连通性,因此一直受到人们的关注,对此已提出了许多算法[1]。

基于二元决策图的网络可靠性分析方法概述【摘要】BDD（二元决策图）是布尔函数图形化的一种表示方法，现已广泛应用于网络可靠度的计算中。

与以往的方法相比，BDD有较高的计算效率。

本文主要介绍了基于BDD的网络可靠度分析方法。

【关键词】网络可靠度最小路集二叉树二元决策图【Abstract】BDD is a diagrammatic representation of Boolean function.It is now widely used in the calculation of network reliability. Com-pared with the methods before, BDD has higher calculation-efficiency. This paper mainly discusses the BDD-based algorithms on network re-liability .【Keywords】network reliability；minimal pathset；binary tree；BDD1引言21世纪以来，以信息技术的飞速发展为基础，人类社会加快了网络化进程。

信息与通信网络被广泛应用于现实生活的各个方面，网络已成为人类生产、生活不可或缺的一部分。

在网络给人们生活带来极大便利的同时，人们对网络的可靠性也提出了更高的要求，所以开展网络可靠性研究具有重大的现实意义。

目前计算网络可靠性度量参数的方法主要有精确法和近似法，其中近似法包括解析近似法和仿真法[1][2]。

精确法主要有状态空间法[3]、因子分解法[4]、最小路集/割集法[5]等。

较为常用且研究较多的方法是基于最小路集/割集的网络可靠性算法。

基于最小路集的网络可靠性分析方法主要分为三类：容斥原理法（Inclusion-Exclusion，IE）、不交积和法(sum-of-disjoint-products, SDP)、以及二叉决策图法(binary-decision-diagram，BDD)。

第８卷第２ｌ期２００８年１１月１６７１—１８１９（２００８）２１－５８９８·０３科学技术与工程ＳｃｉｅｎｃｅＴｅｃｈｎｏｌｏｇｙａｎｄＥｎｇｉｎｅｅｒｉｎｇＶｏＬ８Ｎｏ．２１Ｎｏｖ．２００８＠２００８Ｓｅｌ．Ｔｅｅｌｌ．Ｅｎｇｎｇ．数学一种计算网络可靠度的不交和算法牛义锋徐秀珍１（河南理工大学数学与信息科学学院，焦作４５４０００；华南理工大学２－．商管理学院１，广州５１０６４０）摘要给出了一种计算－网络可靠度的不交和算法，该算法的最大特点是操作简便，易于在计算机上实现，从而适用于大型网络可靠度的计算。

关键词网络可靠度不交和极小路中图法分类号０１５７．５；文献标志码Ａ网络可靠度是通信网络设计与分析的一个重要指标。

计算网络可靠度的方法有：真值表法、卡诺图法、容斥定理、因子分解定理、不交和布尔代数法…。

而利用不交和法求网络可靠度是一种普遍而有效的方法【¨】。

现给出一种计算网络可靠度的不交和算法，该算法能简便地在计算机上实现，从而适用于大型网络可靠度的计算。

１假设与记号１．１假设根据网络的性质现做如下假设。

（１）整个网络及每条边只有两种状态：工作或失效；（２）网络的点总是正常工作，各边的工作状态在统计上是相互独立的。

１．２记号图Ｇ（Ｖ，Ｅ）是顶点集合为ｙ，边集合为Ｅ的网２００８年６月２３日收到络图；ｓ为网络源点，ｔ为网络汇点，Ｒ．。

（Ｃ）为网络Ｇ的两终端可靠度，即网络由源点ｓ到汇点ｆ能正常通信的概率。

Ａ，Ｂ为布尔项，口，ｂ为网络中的边或布尔变量，其工作的概率和不工作的概率分别为Ｐ。

，Ｐ６，Ｐ。

，Ｐ。

ａ，Ａ为分别表示口和Ａ的补，即分别表示口和Ａ不发生。

只表示网络中的第ｉ条极小路，ｉ为正整数ＩＰ；Ｉ为Ｐ；中所含变量的数目，称为Ｐ；的模。

２预备知识２．１不交和公式系统可靠性分析的一种形式，它代表系统成功的逻辑多项式，由于各个项都是不相交的，故系统的可靠度就是这些项的概率之和。

２．２极小路系统结构单元的一个集合，集合内的各单元构成一条从源点到汇点的通路，但去掉集合内的任何一个单元都不能构成一条通路【６】。

收稿日期:2009-09-16 修回日期:2009-10-26第27卷 第3期计 算 机 仿 真2010年3月文章编号:1006-9348(2010)03-0362-04网络系统可靠度的连接矩阵逻辑扩展算法李东魁(包头师范学院信息科学与技术学院,内蒙古包头014030)摘要:针对网络性能优化技术,着重研究无线网络传输可靠性问题,为有效提高3-状态无圈有向设备网络系统二终端可靠度仿真算法效率;采用网络的连接矩阵表示形式,在定义了连接矩阵列变换后,依据连接矩阵逻辑扩展技术对连接矩阵实施连续的代数变换,得到了求3-状态设备网络二终端可靠度的一个有效快速算法。

仿真示例表明,使网络系统可靠度符号表达式中项数大幅度减少,算法效率显著提高。

由于算法使用了网络系统的代数化表示方法,结合了消除冗余项存储及简化技术,算法具有节约存储空间、执行效率高特点。

对复杂网络系统可靠度评估具有重要参考价值。

关键词:3-状态设备网络;可靠度;连接矩阵;逻辑扩展中图分类号:TN193.2 文献标识码:ANew A lgorith m for Co mputi ng Three -state Devices N et worksR eli ability by U si ngM atrix Colu mn -Transfor mati onL I Dong-ku i(Schoo l o f Infor m ati on Science and T echno l ogy ,Baotou N o r m al U niversit y,B ao tou N e i m enggu 014030,China)ABSTRACT:The ex i sted si m u lati on a l go rith m has a prob l em t hat reducing the e fficiency o f a lgo rith m for computi ng 3-sta te dev ice net wo rk 2-ter m i na l re liab ilit y .In th i s paper ,t he ne t w ork is expressed by the connecti on m atri x ,and so m e new concepts o f 0-co l u m u transfor m ati on ,1-co l um transfor m ati on and add iti on o f t wo co l u m ns have been de fi ned ,the 3-state dev ice net wo rk syste m 2-ter m i na l re li ability can be ob lained by on l y usi ng a l gebraic m ethod .A ne w e ffective a l go rith m has been des i gned for co m puting 3-state acycli c directed dev ice ne t w ork 2-ter m i na l re li abil ity .Si m ulati on exa m ple sho w s t hat the nu mber o f i te m s of the net wo rk syste m reli ability symbo lic expressi on has been si gnificantly reduced ,the e ffi c iency si gn ifican tly i ncreased .A s usi ng the net w ork syste m a l g ebraic representation ,and e li m i nati ng redundancy ,the algor it h m can save st o rage space and ra ise the i m p l ementi ng effi c i ency .It is i m po r tant for the co m plex syste m re liab ility assess m ent .K EY W ORDS :T hree-sta te dev i ces net wo rks ;R eli ability ;The connecti on m atri x ;L og i ca l expand1 引言随着通信、计算机网络、无线传感网络技术的发展,网络可靠度日益受到人们的高度关注,它是进行系统设计、安全规划等必须考虑的性能指标[1-7]。