一种基于peri网的可靠性分析方法

一种基于peri网的可靠性分析方法

1基于连通性的网络可靠性测度可靠性是规划和设计通信网络的性能评价的重要指标。通信网络的可靠性一般包括网络的生存性、抗毁性及有效性等多个方面,涉及到网络通信设备、拓扑结构、通信协议等许多因素。网络的抗毁性表示破坏网络的困难程度,用粘聚度和连通度来测度,用图论算法可以算出;网络的生存性是指网络在随机故障条件下的连通性;而网络的有效性则是基于网络业务性能的可靠性测度。当网络的节点或链路发生故障时,直接导致网络的连通性变坏,以致无论如何进行网络管理,网络的时延、吞吐量等业务性能指标都会下降。由于目前有关网络有效性测度的定义和算法尚不成熟,问题又十分复杂,因此连通性是测度网络可靠度的较为实用可行的评价指标。通常的连通性指标包括:端端可靠度、K端可靠度、全端可靠度。目前关于它的计算已经提出了一些方法,如计算端端可靠度问题的全概率解法、生成树法、Monte-Carlo方法。但是如果网络的维修人员有限而出现资源竞争时,因为这时网络系统的状态变化是一个离散事件动态系统的变化过程,以上算法大都难以应用。一般的Monte-Carlo法也难以建模。Petri网是进行离散事件动态系统建模与仿真分析的有力工具,它可以清晰自然地描述系统中的各种逻辑关系及常见的同步、资源共享、竞争、冲突等现象。但通常的Petri网的描述能力仍然有限,对复杂系统建模时,容易造成状态组合爆炸现象。因此,又提出了有色Petri网(CPN)、随机Petri网(SPN)、面向对象的Petri网(OOPN)等高级Petri网模型,有的模型已用于进行系统可靠性问题的建模与分析,表现出了一定的优越性。但是目前的Petri网模型对故障过程及其影响的描述方面还不自然,特别是对每一故障的发生都引入库所和变迁进行描述,加大了所建模型的关联复杂性。本文吸取了各种OOPN模型的优点并进行了扩展,引入了信息弧、公共库所等新概念,提出了扩展的OOPN模型GOOPN,可以统一处理上述三种连通性可靠性指标的分析,而且能方便地考虑有限维修人资源、维修申请排队及维修优先权等复杂情况。当网络的拓扑及维修资源发生变化时,模型只需改变参数设置,即可使模型方便地进行不同设计或维修方案的比较,为网络系统的可靠性分析提供一种新的途径。2挖掘模型2.1城市petri网分类目前的OOPN有几种不同的定义和描述,GOOPN进行的扩展主要是引入了信息弧和公共库所,这是现有的各种OOPN模型中没有定义的。信息弧由库所指向变迁,使得库所Token对变迁的使能产生作用,但在变迁激发时库所不发生Token的迁移消耗,公共库所则允许OOPN中的外部对象对其进行操作。信息弧与公共库所的引入,大大简化了Petri网在可靠性问题建模时的关联结构。此外,GOOPN还具有变迁激发优先权及库所排队规则。这些特点使得GOOPN能适用于复杂系统可靠性问题的建模。下面给出GOOPN的形式化定义。定义1GOOPN=(P,O,T,F,FMG,FIH,C,W,Π,D,Que,Pr,M0)。其中P=PL∪PP——库所集;PL——局部库所集;PP——公共库所集;T——变迁集。O={Oi}Ii=1i=1Ι——子GOOPN对象集;OPP={PPi|∀Oi∈O}——GOOPN子对象的公共变迁集,P∪O≠>,P∩T∩O=>,且P,T,O——有限集。F——POPP×T∪T×POPP上的二元关系(称为流关系)。POPP=P∪POPP。FMG:F|POPP×T→{0,1},FMG(p,t)=0时,表示(p,t)为信息弧,FMG(p,t)=1时,表示(p,t)为实体弧(即通常Petri网中的弧)。FIH:F|POPP×T→{0,1},FIH(p,t)=0时,表示(p,t)为禁止弧,FIH(p,t)=1时,表示(p,t)为非禁止弧。F|POPP×T分别表示F在集合POPP上的限制集。C:P∪T→S——颜色函数;S——有限非空集合(颜色集),且C=CP∪CT;Cp(p)⊂S——库所p的颜色集;CT(t)——变迁t的颜色集。W={Pre,Post}——权函数;Pre:CPOPP×CT→N+——输入函数;Post:CPOPP×CT→N+——输出函数;N+——正整数集。Π:CT→|R0→R|——与每个变迁关联的随机时延分布函数;R0——非负实数集。M:P→|CP→N0|——库所的标识;N0——非负整数集;M0——初始标识。D:CT→[M|POPP→{0,1}],其中[M|POPP→{0,1}]——M|POPP上的布尔条件表达式,M|POPP表示M在POPP上的限制。Que:P→{FIFO,LIFO}——定义在库所集上的排队规则,FIFO表示先入先出,LIFO表示后入先出。Pr:CT→N+——变迁激发优先权函数。由于上述定义中允许子对象集O为空集,故上述定义是一个具有递归性质的定义,即同时也包含了对子对象的定义。2.2gpi激发规则GOOPN描述系统的动态行为是通过变迁激发引起GOOPN的标识发生变化来体现的。定义2(变迁使能条件)GOOPN的变迁t∈T在颜色c∈CT(t)下使能的条件为:①?D(t)(c)=1(布尔条件表达式成立);②?∀(pi,t)∈F,∀aih∈CP(pi),当FIH(pi,t)≠0时,M(pi)aih≥Pre(pi,t)(αih,c);当FIH(pi,t)=0时,M(pi)(aik)=0(禁止弧条件成立)。定义3(变迁的激发规则)当变迁t∈T在颜色c∈CT(t)下使能激发时,GOOPN的新标识M′由下式确定。M′(pi)(aih)=M(pi)(aih)-FMG(pi,t)·FIH(pi,t)Pre(pi,t)(aih,c)+Post(pi,t)(aih,c),∀pi∈POPP,∀aih∈CP(pi)定义4GOOPN的冲突消解策略是:①当库所p中的令牌数目多于变迁激发所需的数目时,依Que(p)规定的队列取走相应的令牌;②当有多个变迁激发模式使能时,依Pr规定的优先权大小决定变迁模式激发的优先次序。定义5GOOPN的变迁t在颜色c∈CT(t)下的激发过程为:首先由变迁使能条件检查是否使能,如果使能,则经过由时延分布函数Π(c)(s)规定的延时后激发。当发生激发冲突时按定义4中的冲突消解策略解决。3节点状态改变检查针对通信网的连通可靠性分析,我们将通信网简化为由节点和链路组成的无向网络。设通信网由若干名维修员负责维修。节点或链路发生故障后向网络维修员发出维修申请,维修员依维修申请的优先权和到达队列响应维修申请。图1是通信网可靠性的GOOPN模型。图1中的方框表示GOOPN对象子网,虚线表示信息弧,头端有小圆圈的弧为禁止弧,椭圆表示的是公共库所。各库所及变迁的含义如下。p11,p21:节点(链路)故障维修申请;p12,p22:维修响应信号;p13,p23:维修完成信号;p14:节点(链路)正常;p15:节点(链路)故障待修;p16:正在修理中的节点(链路);p24:维修员闲;p25:维修员忙;p31:节点(链路)状态改变信号(正常转为故障或故障转为正常);p32:接受系统状态检查申请;p33:已完成对p37,p38,p39,p314的初始化;p34:已完成对p36的释放;p35:已完成读取p14中的状态到p27中;p36:禁止读取p14;p37:当前正常的节点(链路);p38:互通的节点集;p39:使网络正常的节点集;p310:网络状态检查结果;p311:网络系统状态;p312:准备读节点(链路)状态改变信号;p313:允许读取系统状态检查结果;p314:禁止聚类;t11:节点(链路)发生故障;t12:节点(链路)修复;t13:节点(链路)开始维修;t21:维修员开始维修;t22:维修员完成维修;t31:接受节点(链路)状态改变检查申请;t32:NET模型初始化;t33:允许启动t35读取系统状态;t34:允许读取系统状态;t35:读取系统节点链路状态;t36:节点聚类;t37:检查是否有符合系统正常条件的节点集;t38:发送系统正常(故障)信号;t39:系统状态变化;t310:发送系统发生故障信号;g1~g3:连接各子对象有关库所的变迁。图1中BLK、RPM分别是描述节点(链路)与维修员的对象模型,为了对网络系统的状态进行描述,我们构造成了标记为NET的对象模型。在BLK中由不同颜色的Token代表网络的节点与链路,故障的发生与修复由变迁模式描述。节点(链路)发生故障后,通过p11发出故障维修申请,由p12得到响应后,进入维修状态p16,修复后再回到正常工作状态p14。在RPM中,用不同颜色的Token代表各维修员,处于空闲状态的维修员接到维修申请后,依申请优先权从p21的队列中响应,并由p22发出响应。当节点(或链路)的状态发生变化后,向NET的p31发出检查系统状态的申请,若NET已处理完上次申请,则依p31队列响应申请,同时通过t32对NET初始化,然后对t35解锁,读入当前正常工作的节点(链路)集到p37,由t36和p38进行聚类(见后述内容)。当t37检测到有使网络正常的节点集时激发,释放一个标志正常的Token进入p310,若聚类结束没有出现使网络正常的节点集,则通过t310释放一个标志故障的Token进入p310。由p310及p311的Token可决定t39的激发模式(例如,当p311的Token标志系统正常时,若p310的Token也正常,则系统状态不发生变化,仅释放一个Token到p312)。p313起读取锁定作用,目的是使聚类过程完成后才检查读取聚类的结果。而p312的锁定作用是使系统的状态完成一次改变后,才进行另一次改变的检查。由p311到t31的信息弧的目的是减少不必要的系统状态检查。例如,如果系统正常,而检查申请是来自某节点由故障转为正常,这时NET不必响应这一信号。由p14到t35的信息弧可以使NET读取BLK中p14的状态,而不影响BLK的状态变化。图中的变迁一般具有相应的判定条件布尔表达式及颜色函数。限于篇幅,不在此详述。对网络系统的状态检查是通过聚类过程完成的,无论是端端可靠度、K端可靠度问题,还是全端可靠度问题,其本质都是网络中某些节点之间是否连通的问题。因此,每当节点(链路)的状态发生变化时,即进行连通性检查。若节点i,j正常,且i,j之间的链路也正常,则将i,j归为一类,这样可以实现对整个网络节点集的剖分。我们将p38初始化为网络的全部节点集,由于p37是正常的节点(链路)集,因此可以经t36实现聚类,使p38不断变化。以不固定K端可靠度问题为例,当t37发现某一个聚类集合中的元素数目大于等于K时,发生激发,并释放Token到p314,使聚类过程停止。采用离散事件动态系统的仿真技术对GOOPN进行仿真,通过对库所p311中Token状态的统计分析,可以得出系统的MTBF指标。而通过对RPM的库所p24中Token状态的统计分析,可以分析网络系统维修人员的忙闲程度,为维修资源的配置提供依据。4基于信息弧的系统可靠性分析技术本文提出了一种扩展的面向对象的Petri网模型