时间Petri网

时间Petri网（共7篇）

时间Petri网 篇1

摘要：工作流Petri网的时间性能分析方法有多种, 本文采用加入时间因素的扩展马尔可夫链, 建立与随机Petri网同构的有穷马尔可夫链, 再根据此过程的稳定概率求解系统的性能参数。

关键词：工作流,Petri网,时间性能分析,马尔可夫链

工作流模型的时间性能分析是工作流研究的重要内容之一, 也是分析资源利用率、成本等指标的基础。目前, 大多数实用的工作流应用系统, 在业务流程的性能分析上, 几乎未给出适合各种工作流模型的有效方法。工作流除了正确性之外, 还要关心它的性能分析, 而这一点又往往被人们所忽视。工作流性能分析主要反映工作流定量方面的特性, 比如过程的完成时间, 资源利用率等等。定量分析模型之前须确认模型的正确性, 即保证模型在业务流程和逻辑结构上没有错误且是合理的。传统的基于马尔可夫链的性能分析方法[1]具有指数时间复杂性, 影响了其实用性。对给定的工作流, 可以生成一个马尔可夫链, 利用它可以分析工作流的某些方面, 而且马尔可夫链的分析[2]非常耗时 (即使是对本来不难处理的问题) 。但是, 根据实际应用可以通过成本或时间的引入来扩展马尔可夫链, 就能获取一系列性能指标。

本文讨论加入时间因素的扩展马尔可夫链, 根据被评价的随机Petri网工作流模型构造出连续时间的马尔可夫链, 即随机模型[3], 对其进行时间性能分析。

1 基本概念

1.1 工作流网

对工作流的控制流建模的Petri网被称作工作流网 (WF-net) , 是Aalst在Petri网的基础上提出的概念。

1.2随机Petri网

随机Petri网 (SPN) :一个连续时间SPN是一个六元组SPN= (P, D, F, W, M0, λ) , 在Petri网基础上, λ={λ1, λ2, …, λm}, 是变迁平均实施速率集合。

在连续时间SPN中, 一个变迁t从变成可实施的时刻到它实施时刻之间的延时被看成一个连续随机变量, 服从以λ为参数的指数分布。λ是变迁t的平均实施速率, 表示在可实施的情况下单位时间内平均实施的次数, 单位是次数/单位时间。平均实施速率的倒数1/λ称为变迁ti的平均实施延时或平均服务时间。

1.3工作流-随机Petri网的定义

工作流-随机Petri网 (WF-SPN) 是在随机Petri网 (SPN) 和工作流网 (WF-net) 的基础上提出的, 目的是将随机触发时间引入工作流网, 使模型具有分析时间性能的能力。

WF-SPN是SPN的真子集, 可递归定义为:由一个基本结构组成的SPN是WF-SPN。WF-SPN满足如下性质: (1) 有一个初始库所i∈P, ·i=φ; (2) 有一个终止库所0∈P, o·=φ; (3) 每个节点x∈P∪T都在从I到o的一条路径上。

2 工作流-随机Petri网时间性能分析

基本Petri网模型不能用于系统的性能评价, 必须对其扩展。可以在每个变迁的可实施和实施之间联系一个随机的时间延迟。应用随机Petri网对系统评价时分三步:1) 构造系统对应的随机Petri网模型。2) 构造出该Petri网所同构的马尔可夫过程。3) 基于马尔可夫过程的稳定概率求解系统的性能参数。

工作流-随机Petri网和一般工作流网的区别:在变迁中引入平均实施速率λi, 每个λi值是从对所模拟系统的实际测量中获得或根据某种要求的预测值, 它们具有实际意义。

定理1[4]任何具有有穷个库所、有穷个变迁的连续时间的随机Petri网同构于一个一维连续时间的马尔可夫链。K-有界的随机Petri网同构于有穷马尔可夫链。

假定一个工作流随机网同构于一个马尔可夫链, 那么工作流随机网的每一个标识可以达到一个动态平衡状态, 即每一个标记有一个确定的值, 称为标记Mi的稳定概率, 记为P (Mi) , (i=1, 2, ..., k) 。根据马尔可夫链平稳分布的有关理论, 得出如下的公式[5]:

其中Q为变迁速率矩阵, 其非对角线上的元素qi, j (i≠j) 是这样确定的:如果在马尔可夫链中从Mi到Mj有一条有向弧连接时, qi, j为弧上的速率值;如果没有弧, 则qi, j (i=j) 是从Mi发出的各条弧速率之和的相反数。将工作流随机网同构为马尔可夫链之后, 利用公式 (1) , 可以解出P (Mi) 的值。由此可以得出工作流模型的一些系统特性和运行特性。

生成一个工作流网的可达图是实现从工作流网到马尔可夫链转换的关键, 但要确保工作流网模型是合理的。工作流网是合理的, 那么工作流随机网必定有界, 该网就可以同构于一个有限的马尔可夫链, 保证了计算的可行性。具体的分析步骤如下:

(1) 从工作流随机网的定义可以看出, 它是工作流网的一个特例。由于任何一个合理的工作流网必将结束于标识 (0, 0, ..., 0, 1) , 也就是在马尔可夫链中该结束标识的稳定概率为1, 其他标识的稳定概率均为0。这样就不能用来分析其性能, 原因是工作流网仅执行一次。因此要将一个工作流网执行多次, 然后得出每个标识的稳定概率。现有的工作流网模型不能反映这一特性, 在文献[6]中提出在库所o和库所i间增加一个瞬间变迁t*, 并连接库所o和变迁t*, 连接变迁t*和库所i, 由于变迁t*是不需要时间的, 实际上标识 (0, 0, ..., 0, 1) 是不存在的。因此, 可以考虑将库所o映射为库所i, 也就是将库所o和库所i合并, 这样在不额外增加变迁的基础上, 也能反映工作流网可任意次执行的特性, 得出的标识稳定概率可用于分析工作流的性能。因此这一步要完成的任务就是将库所i和库所o合并。

(2) 接着要生成可达图。首先可以先生成一个可达树, 再将可达树转换成一个可达图。

(3) 计算Q矩阵的值。在马尔可夫链中, 当从状态Mi到状态Mj有一条弧相连时, 则弧上标注的值即是qi, j的值;如果从状态Mi到状态Mj没有弧相连时, 则qi, j=0。对角线上的元素qi, j (i=j) 是从Mi发出的各条弧速率之和的相反数。证方法[7], 可以得出结论, 图1模型是的马尔可夫链, 保证了计算的可行性。⑴在库所o和库所i之间增加一个示的改进模型。反映工作流网可任意次

根据公式1得到稳定概率P (Mi) 的值;在求得稳定概率的基础上, 可进一步分析系统的以下性能指标, 如变迁的标记流速, 子系统的平均延时时间等, 具体可参考文献[5]。的性能。⑵生成可达图, 得出图2所示的

(1) 在每个状态M中的驻留时间:在每个可达标识M∈[M0>的驻留时间是以-γi, i为参数的一个指数分布的随机变量, 平均均

(2) 标记概率密度函数:在稳定状态下, 每个库所中所包含标记数量的概率。对, ∀s∈S, ∀i∈N令P{M (S) =i}表示库所s中包含i个标记的概率, 则可从标识的稳定概率求得库所s的标记概率密度函数: , 其中Mj∈[M0>且Mj (s) =i.

3 实例分析:

本文以ASP平台进销存系统为例对其过程模型进行时间性能分析。此系统的简化过程模型见图1所示, 库所集合P= (p1, p2, …, p6) , 变迁集合T= (t1, t2, …, t5) 。其中变迁标识和含义:标识t1代表客户下订单, 即当收到客户的订货信息就触发变迁t1, 实施创建销售订单的任务;t2表示检查库存, 若当前库存能满足订单需求, 则实施p2分支, 否则实施p3分支;t3代表采购;t4表示出销售单;t5代表出货。标识i是库所开始, o表示库所结束。

因为要采用工作流随机Petri网来分析工作流, 首先要确保模型是合理的, 通过分析验证方法[7], 可以得出结论, 图1模型是正确的、合理的。通过定理1, 该网同构于一个有限的马尔可夫链, 保证了计算的可行性。如前文所述, 对工作流随机Petri网的分析步骤如下:

⑴在库所o和库所i之间增加一个瞬间变迁t*, 将库所o和库所i合并, 形成图2所示的改进模型。反映工作流网可任意次执行的特性, 得出的标识稳定概率可用于分析工作流的性能。

⑵生成可达图, 得出图2所示的工作流网的可达状态标识, 可用表1来表示。将图2所示的工作流Petri网转换成与其等价的马尔可夫链, 见下图3。

⑶Q为变迁速率矩阵, 根据前文计算规则, 得出图3马尔可夫链对应Q矩阵的值见表2

一旦给出λ的具体值, 就可以根据公式 (1) 得到稳定概率P (Mi) 的值。根据对实际问题的预测, 该网中的变迁引入平均实施速率λi。给定随机变量集合λ={λ1, λ2, λ3, λ4, λ5, λ*}={2, 5, 20, 3, 15, 0}。得到P (Mi) ={0.2498, 0.2145, 0.2237, 0.187, 0.1250, 0}。在求得稳定概率P (Mi) 的基础上, 就可以得出上文中提到的工作流网的其他性能指标标

4 结语

本文采用加入时间因素的扩展马尔可夫链对被评价的随机Petri网工作流模型, 首先构造出相应的连续时间的马尔可夫链, 再根据此过程的稳定概率对其进行时间性能分析。通过实例分析得出:此方法是有效、可行的, 对同类问题的分析和评价具有一定的参考价值值

参考文献

[1]王建民, 闻立杰, 等, 译.工作流管理—模型、方法和系统[M].北京:清华大学出版社.2004.

[2]曲扬.基于Petri网的工作流建模和分析方法研究.清华大学学位论文.清华大学, 2004.

[3]卫刚.基于Petri网的工作流建模工具的研究与实现.南京航空航天大学学位论文.南京航空航天大学.2005.

[4]林闯.随机Petri网和系统性能评价[M].北京:清华大学出版社.2000.

[5]林闯.计算机网络和计算机系统的性能评价[M].清华大学出版社.2002, 1:3~202.

[6]Lin C, Marinescu D C, Reachability trees for high level Petri nets with marking variables, Computer Sciences Department, Purdue University, CSD-TR-857, February1989.

[7]沈美.基于高级Petri网的工作流建模研究与仿真分析.计算机工程与应用.2006, 42 (32) :200~203.

时间Petri网 篇2

软件在其自身的发展中出现了很多问题,其中出现的软件危机阻碍了软件的开发与管理,改进软件的开发过程对于缓解软件危机具有重要意义[1]。

软件过程作为一个多元非线性系统,是与活动、约束和资源相关的有顺序的集合[1,2]。

随着物联网、云计算等大规模分布式系统在国内的日益流行,软件工程的应用环境已经不可避免的转向跨地域大规模协作式合作开发的模式。然而,在协作式开发过程中,总会有一些共享资源需要在某一段时刻被某个开发小组独立占用,当各个小组都需要该资源时,不可避免的会出现冲突。针对该问题,很多学者提出了解决方案,大都集中在对软件过程中资源使用以及成本与工期的问题上。然而,软件开发是一个协作式过程,避免各个小组工作计划的冲突是软件工程建模的重点。本文结合petri网理论,提出一种检测冲突方法。

二、Petri网基本知识

Petri网是C.A.Petri博士提出的一种用于并发系统建模和分析的方法。通过使用Petri网对系统进行建模,基于通用网论的思想,可以将系统设计分成整体和局部设计等等,从而在最大限度上简化设计。通过形式语言等方法来分析Petri网模型的可达性、活性、公平性等性质,从而正确地产生系统性能评价,并提出相应的系统改进建议。

假设读者对Petri网的基本概念、基本理论已有所了解,详细内容请参见文献[3]。

三、UML的传统顺序图

顺序图通过描述一些对象的消息交换。其重点关注对象传递消息的时序。消息既可以是同步的,也可以是异步的,通过对象间消息的传递顺序来表示对象间的交互行为。在本节中将介绍一下顺序图中所涉及的主要内容:

1、对象(Object):

对象作为类的实例,在顺序图中显示的对象都是在该消息序列中所涉及的对象,对象依次放置在水平轴上,每一个对象是一个矩形,矩形中的对象名都标有下划线。其中对象的命名表示为“对象名”:“对象所属类”,其中对象名可以省略。

2、生命线(Lifeline):

每个对象下面有一条垂直的虚线,称作对象的生命线,指示对象在消息序列中的执行情况。它代表该对象在某个特定时间的存在现象,通过一条从对象矩形一直向下到图底的虚线来表示。

3、激活(Activation):

对象接收到一个消息,该对象中的活动就会启动,这一过程称作激活。激活显示控制点,显示对象在某一个时间点的执行。一个被激活的对象或者是执行它自身的代码,或者等待另一个对象的返回(该被激活的对象已经向另一个对象发送了消息)。在图形上,激活被绘制为对象生命线上的一个瘦高矩形。

4、消息(Message):

对象之间的通信(即消息)用一些位于各个对象的生命线之间的水平消息线来表示。水平消息线的箭头确定了消息的类型。从一个对象到另一个对象的通信都是消息,例如一个对象调用其他对象的操作,创建或销毁一个对象,向其他对象发送信号等。在顺序图中它由各个对象之间的一条水平消息线来表示。它包括三类:第一类,当一个对象调用操作后暂停执行,只有操作返回时,个体才会恢复执行,使用同步消息箭头。第二类,当一个对象调用操作后运行在其他线程或进程中,并且不等待调用的操作返回,这时候该使用异步消息箭头。第三类,用虚线箭头表示控制权从同步消息返回,从而创建新实体。

5、返回(Ruturn):

当消息返回结果时(同步消息,如操作调用),用箭头(简单消息的箭头)表示,为了区别发送的消息,用带箭头的虚线来表示消息返回。但是要注意,消息的返回不能总被顺序图显示。

6、条件(Condition):

消息能够有条件。当条件为真时,消息才被发送或者被接收。条件决定消息是否发送,在顺序图中,条件常常在消息前以方括号形式给出。

为了更好地描述系统行为,通过将UML的传统顺序图进行扩展,使之能够对在大型异步系统中的并发、选择、同步等性质进行建模。

四、基于时间约束的软件工程资源配置petri网检测模型

通过绘制出各个协作个体在软件工程中使用资源的UML顺序图,之后通过相应的转换方法,将UML顺序图转换成相应的Petri网模型[5,6,7,8,9]。其步骤如下:

Step1:绘制协作个体的顺序图,可用UML顺序图表示;

Step2:将UML顺序图转换成相应的Petri网模型;

Step3:分析Petri网模型冲突等特性;

Step4.发现有色Petri网未发现的漏洞,进行修补,转入Step3。否则,则退出。

五、实验

其中实验主要使用有色Petri网分析工具CPN Tools(2.2.0);采用的程序设计语言为CPN ML,CPN ML是建立在SML(Standard ML)上的一种解释性语言,对于模型中的变量定义、条件转移语句,控制语句等都是通过CPN ML语法进行描述的,对于可视化交互仿真,可视化查询,状态空间分析报告的产生也是通过CPN ML实现的,对有色Petri网进行综合分析。

主要采用测试的手段,对有色Petri网分析出来的系统设计漏洞进行实际检测,以验证本项目提出方法的正确性;对成功修正后的UML模型进行全面检测,已验证不存在有色Petri网未发现的漏洞。我们使用实例[4],对应的基于时间约束的软件工程资源配置使用情况流程图已被描述。通过本文提出的petri网验证方法,可以得到图1.通过生产的报表,可知该模型没有冲突发生。

六、结论

基于时间约束的软件工程资源配置Petri网检测模型成功地解决了协作式软件工程设计中资源合理分配中冲突检测的问题,为软件过程的控制提供了科学而又合理的依据,从而实现了对软件开发的工期、成本的要求,仿真表明该方案是可行的。

参考文献

[1]雒雪芳.基于进化计算的软件过程优化及成本估算研究[D].西北工业大学工学硕士,2005.

[2]刘伟.活动网络费用优化问题及其遗传算法[J].系统工程学报,1999,14(2):72-77.

[3]Park J,Reveliotis S A.Deadlock avoidance in sequentialre-source allocation systems with multiple resource acquisitions andflexible routings[J],IEEE Trans.Automat.Contr.,2001,46:1572-1583.

[4]Lee D Y,Frank D.Scheduling flexible manufacturing sys-tems using Petri nets and heuristic search[J].IEEE Transactions onRobotics and Automation,1994,10(2):123-132.

[5]Kerkouche E,Chaoui A,Khalfaoui K,Transforming UMLModels to Colored Petri Nets Models using Graph Grammars,2009IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS,VOLS 1 AND 2,230-236,2009.

[6]Staines,Anthony Spiteri,A Triple Graph Grammar(TGG)Approach for Mapping UML 2 Activities into Petri Nets.PROCEED-INGS OF THE 9TH WSEAS INTERNATIONAL CONFERENCE ONSOFTWARE ENGINEERING,PARALLEL AND DISTRIBUTEDSYSTEMS,90-95,2010.

[7]杨玉梅,刁永锋,基于UML顺序图的Petri网建模[J],计算机技术与发展,Vol.17 No.10 Oct.2007.

[8]周长红,UML图的Petri网建模[D],山东科技大学,2004.

时间Petri网 篇3

关键词：合同网协议,面向对象Petri网,信任度,阈值

0 引 言

在多Agent系统中,Agent内部的知识、能力、策略和任务在问题的求解过程中会动态变化,各Agent必须通过协商来达到任务求解。合同网协议就是一种非常重要的协作方式[1]。它由Randall Devis和Reid G.Smith于上世纪70年代提出。合同网协议借鉴商业活动中合同招标的运作模式,在一组Agent之间进行任务的合理分配,实现合作问题的求解。

目前,已有众多研究人员对合同网协议和合同网协议模型进行了研究,并取得了一些成果。如中科院的张海俊等结合群体智能提出的动态合同网协议[2],引入信任度以充分利用过去有用的知识,更好地适应环境及Agent能力的动态变化。华科大的宋海刚等通过增设阈值来保证参与者最终只与一个任务发起者建立正式的合同关系[3]。文献[4]采用面向对象Petri网对合同网协议进行了形式化的建模。但是,已有的合同网模型较少考虑Agent角色的可变性和通信开销等问题。本文结合目前合同网协议的研究成果,引入信任度和阈值对协议模型进行了改进。通过将Agent对象化[5],将知识的表示结构与处理方法封起来,使系统模块化,可以在不同的环境中扮演不同的角色,从而使模型具有通用性。通过信任度[2]进行有效任务分配,减少通信量,提高其处理大规模集任务的综合性能。通过阈值[3]来控制参与者收到标书的数量。

1 多Agent系统的社会组织模型

本文的协商方法是针对层次问题的求解,一组Agent通过协作完成整个任务的求解,为此先给出一种多agent系统的社会组织模型。一个具有社会性的多Agent系统由三部分组成:用户接口、系统管理者和多个Agent组。模型图如图1所示。一个Agent组是由多个Agent为协作共同完成任务而构成的。Agent组之间也存在着交互。本文主要讨论Agent组内部的交互。在Agent组中,一般存在一个起组织协调、任务分配作用的Agent,称管理者,其它的为执行任务的承包商。

2 Agent对象模型

结合多Agent系统的社会组织模型和面向对象的观点,将Agent对象化,每个对象都有自己特定的属性和方法。在多Agent系统中,一个Agent组就是一个OOPN(Object-Oriented Petri Net),由相互通信的对象和它们之间的关联关系组成。一个OOPN包含许多子网对象,即Agent对象。一个Agent对象,结构如图2所示,由四部分组成:外部接口位置、任务库、知识库和内部结构。外部接口位置包含对象所有的方法和属性、变量的全局描述,是和其他子网对象通信的唯一接口;任务库用于描述多个Agent需要共同完成的目标任务。知识库是一般性常识和知识的抽象,用来描述环境和Agent本身的状态。内部结构用Petri网描述模块内部的细节设计。Agent对象之间通过方法调用和托肯的转移进行通信。

在系统初始化的时候,为每个Agent对象生成一个唯一的标识ID,放在外部接口位置。Agent对象的内部结构是核心模块。为达到共同的目标制定调度策略并执行相应的操作,内部结构由三部分组成:输入消息处理部分、动作选择与执行部分和输出消息处理部分。输入消息处理将外部消息转化为内部消息;动作选择与执行根据内部消息选择相应的动作并执行,得到执行结果;输出消息处理根据动作的执行结果与外界进行通信。

Agent对象的形式化的描述为一个五元组:AG=(ROLE,EI,TB,KB,IS)。

ROLE为角色的集合,EI(External Interface)为Agent与其他Agent的外部接口,TB(Task Base)为任务,KB(Knowledge Base)为知识库,IS(internal structure)为内部结构。

其中,ROLE={Manager Agent,Application Agent,Free Agent}。IS定义为一个三元组IS=(IMP,TCE,OMP),IMP(In Message Process)为输入消息处理,TCE(Task Choose and Execute)为动作选择与执行,OMP(Out Message Process)为输出消息处理。

IMP,TCE,OMP 定义为一个五元组(P,T;F,W,M0),P是位置的集合,T是变迁的集合,F是弧的集合,W是弧上的权函数,M0是初始标识。

为描述方便,将任务库、知识库、信任度和阈值简化为位置,对象Agent的模型如图3所示。Agent对象的IS是任务驱动的,当一个Agent有任务需要其它Agent协助完成就发起一个会话;它又是消息驱动的,当有其它Agent的消息(外部消息)到来时,消息被输入到IMP进行处理,处理结果有两种:拒绝和接受。处理的结果作为token再次转移到EI,作为内部消息输入给TCE,接着动作选择变迁点火,下一动作位置获得token,Agent根据当前的状态和环境决定忽略或者执行动作。忽略表示一个协商过程结束,执行动作则继续应答收到的消息。在这两种情况下,更新变迁都会点火,更新Agent当前的状态。如果下一位置选择执行动作的话,则动作执行变迁点火,token的标记从内部变为外部,到达OMP,同时修改相应的信任值,Agent之间的一次通信结束。

3 合同网协议的改进模型及特点分析

3.1 合同网协议的改进模型

改进后的合同网协议模型的协商过程为:

(1) 初始化 系统初始化时,为每个agent对象生成一个唯一的标识ID,放在外部接口位置。同时为每个agent对象初始化信任值和阈值。信任值即Manager Agent对Application Agent能够完成某类任务的相信程度,阈值即一个Application Agent能够同时处理标书的最大值。

(2) 分解任务,制定标书 当一个agent有任务需要其它agent协作完成时,它的角色为Manager Agent。Manager Agent对其任务进行分解并指定标书。

(3) 确定Application Agent,发放标书 Manager Agent根据其它agent的当前信任值,确定Application Agent。若agent可信,则并向其发放标书。

(4) Application Agent投标 Application Agent收到标书后,根据当前的阈值和能力决定是否投标,并回复信息。

(5) Manager Agent确定中标的Application Agent,并发出中标通知。

(6) Application Agent执行任务,并返回执行结果。

(7) Manager Agent根据Application Agent的执行任务情况修改其信任度,同时修改本身的任务库和知识库的相应内容。

(8) 会话结束。

下面以两个agent对象,agent A和agent B为例。改进合同网协议模型如图4所示。

3.2 改进模型特点分析

改进后的模型具有以下特点:

(1) 角色可变性 在改进合同网协议模型中,某Agent可以是Manager Agent,也可以是Application Agent。Agent所扮演的角色不同,它对消息的处理,动作的选择,任务的执行都可能不一样。具有角色可变性,能适应系统功能的动态变化。如图4,当p1、p2中有托肯时,agent A为Manager Agent,t6、t10所选择执行的动作就是确定承包商Agent是否中标和修改信任度。下一个时刻,若p1中没有托肯,Agent A变为Application Agent时,t6、t10所要选择和执行的动作就是是否投标和执行管理Agent分配给它的任务。如果Agent即没有任务,因为没有收到标书,它的角色为Free Agent,知道它有任务或收到标书才更改角色。

(2) 通信量减少 根据Manager Agent对其它Agent的信任度,确定承包商变迁t2点火,向它所信任的Agent发放标书,避免了向所有的agent发放标书,从而减少了Agent之间的通信量,也有效地利用历史信息,提高了通信效率和质量。变迁t21根据Agent当前的阈值处理外部消息。若当前收到的标书小于阈值,则接收,否则拒绝。从而有效地控制了处理不必要的消息,减少通信量。

(3) 并发性 由图4可以看出,只要Agent有任务,即p1和p2、p13和p14中有托肯,变迁t1和t14可以根据需要触发多次,表明无论是哪个Agent,都可以并发地发起一个会话,为了完成共同的任务,Agent可以协商多次。

4 结束语

和传统的合同网协议模型相比,本文的改进模型虽然在一定程度上满足了系统功能和环境的动态性的要求,具有角色可变性、并发性和通信量少的特点,但该改进模型只针对友好型的多Agent系统,具有一定的局限性。对历史决策信息的利用也不够充分。这些还需要进一步研究。同时,还要进一步研究面向对象Petri网的分析方法并对该模型进行验证。

参考文献

[1]毛新军.面向主体的软件开发[M].北京.清华大学出版社,2005,6.

[2]张海俊,史忠植.动态合同网协议[J].计算机工程,2004,22(10):44-57.

[3]宋海刚,陈学广.FIPA合同网协议的一种改进方案[J].华中科技大学学报:自然科学版,2004,7(32):31-33.

[4]于振华,蔡远利,韩九强.基于面向对象Petri网的多agent系统交互协议建模[J].计算机集成制造系统,2005,11(8):1064-1068.

[5]王怀民,陈火旺.对象作为智能主体[J].电子学报,1995,23(11):105-108.

时间Petri网 篇4

研究协议测试理论的原因是一个标准化的协议并不不能确保该协议的实现之间能够成功的进行通信。虽然形式化验证的方法尽量的避免了协议实现与协议描述的差距, 但在一个协议入网之前还是需要一种有效的方法来对协议的实现进行判别。协议的测试就是要解决以上问题。协议的测试理论包括了协议测试的整个过程, 其主要研究内容包括测试组织、测试方法、测试生成、测试集描述、测试执行和判决、测试结果分析等多个方面。其中研究的重点是如下几个方面:

1测试生成

主要关注如何从协议标准的描述中获得进行协议测试所需要的测试集。

2测试集描述

目的是寻找一种合适的语言或公式, 从而能以简洁、通用和结构化的方式表达协议测试所需要的测试例。

3测试的执行和判决

这是协议测试过程中的关键阶段, 如何解释测试例的含义以及如何做出测试判决是它的研究内容。

4测试结果分析

协议测试过程的最后一个阶段, 研究如何从测试结果中分析生成测试报告并得出对被测协议实现的结论。

由于协议行为的复杂性, 难以用人为构造测试例的办法覆盖一个协议的所有行为, 所以研究一种测试例自动生成的方法十分必要。测试例经过协议实现的执行之后就要对运行结果进行判断, 有严格语法语义定义的形式化方法是自动、准确判断协议行为的关键。基于Petri网的协议测试技术是解决以上问题的有效方案。

基于Petri网的协议一致性测试方案

一致性测试是一种“功能测试”, 它依据一个协议的描述对协议的某个实现进行测试, 判别一个协议的实现与所对应的协议标准是否相一致。本文对协议的测试主要采取以下几个步骤如图1:

1测试准备:抽象测试集的生成, 是为一个特定的协议产生一个独立于所有协议实现的抽象测试集ATS (Abstract Test Suite) 。

2测试操作:也称为测试实现。在这一阶段, 根据协议实现的“协议实现一致性声明”PICS (Protocol Implement Conformance Statements) 和要测试的内容从ATS中生成可在实际的测试系统上执行的测试例, 最终产生参数化的可执行测试例ITI (Implemental Test Illustration) 。

3测试执行:可执行测试例的执行, 让IUT (被测实现Implementation Under Test) 执行已具体化的测试例, 并对IUT的外部行为响应进行观察和记录。

4测试判定:将IUT的实际响应序列与测试例期望产生的结果比较, 判别IUT的运行结果是否与PICS的描述一致, 如有错误找出错误发生的位置。将测试结果生成测试报告, 便于测试人员对协议实现分析。

测试方案中关键问题的解决

协议测试中涉及的关键技术主要有抽象测试集的生成, 从抽象测试集到可执行测试例的转化和测试判定。本文将利用Petri网的理论解决以上问题, 主要采取以下思路如图2。

测试执行子模块负责测试系统在测试执行阶段的工作。它将测试实现子模块预处理过的可执行测试集ITI的一个个测试例逐步在被测实现IUT上执行, 每一个测试例可能有不同的报文结构组合。对每一个具体的测试例, 测试执行子模块将每一个测试步的动态行为和数据行为输入到被测实现IUT的上侧服务访问点, 激励被测实现并观察被测实现的响应。将被测实现的响应与预期的测试响应序列进行比较, 做出一致性判断。最后根据测试结果生成测试报告。

总结

本文给出了用Petri网理论对协议一致性测试的总体方案, 重点解决了两个难点问题: (1) 测试集和测试例的表示和生成; (2) 被测实现的实际响应序列和预期响应序列的比对。

对于第 (1) 个问题, 测试集合我们用协议的网模型表示, 因为协议网模型的运行可以反映协议的实际运行情况, 从而以简洁、结构化的方式表达出了对协议功能测试的测试集合, 测试例我们用进程表示, 一个进程只能反映Petri网的一种可能运行情况。可以用进程表达式表示一个网系统的所有进程, 这样我们可以用求取进程表达式的方式得到尽可能覆盖协议所有行为的测试例。对于第 (2) 问题, 通过观察代表具体测试例的进程的变迁序列求取协议的预期响应序列。

时间Petri网 篇5

Web服务是一种新型的Web应用程序。随着Web服务技术日趋完善, 利用Web服务组合满足应用需求成为可能。现有的Web服务组合标准BPEL4WS[1]、WSCI[2]等都是基于XML的Web服务组合描述语言, 为描述Web服务组合流程制定了语法规则, 主要依靠设计人员的经验完成组合服务的创建。由于没有流程建模和验证过程, 流程设计者水平决定了流程正确与否。用手工方法进行Web服务组合分析和验证已经变得非常复杂, 且工作效率低, 因此研究利用工具对Web服务组合进行建模, 进而进行分析、验证和仿真成为当前研究的热点。在文献[3]中提出了基于一般Petri网Web服务组合代数, 通过将操作符直接映射到Petri网结构来表达组合操作符的形式语义。任何以该代数结构表达的Web服务组合都能转换成对应的Petri网描述。这种方法能够对服务组合进行验证, 确保组合Web服务逻辑正确性。然而一般Petri网不能精确表达Web服务的数据流。文献[4, 5]中提出了一种方法:借鉴模型驱动体系结构MDA (model driven architecture) 的思想, 用UML活动图模型来描述Web服务组合, 可产生以不同组合语言表示的可执行规范描述。该方法利用扩展的UML来描述Web服务组合, 为Web服务组合提供了一种图形化的描述方式, 但没有提供服务组合正确性验证方法。在文献[6]中给出了一个面向服务的分布式系统的设计与分析框架。该框架的基础是一个基于颜色Petri网的服务模型WSPNet, 该框架还包括一个支持组合模型建模和分析的工具集。WSPNet是描述服务组合一个较粗略的模型, 没有对流程中并行、选择、循环的具体表达做具体描述, 在文中仅针对BPEL4WS可表达的流程模式给出了模型的相应表达, 没有给出主要流程结构的WSPNet模型表达, 不独立于流程描述语言。

针对已有建模方法不独立于流程描述语言且不能全面刻画流程这两个问题, 本文结合模型驱动体系结构和形式化方法思想提出了一种描述Web服务的颜色Petri网模型, 较全面地描述服务组合流程的同时, 还能进行流程正确性分析验证。

1 Web服务组合的颜色Petri网模型

Petri[7]网是一种基于图的形式化描述模型, 用于分析离散的并发系统。由于Petri网严格的数学基础和图形化的规范语义, 在系统建模中得到广泛应用:系统建模分析, 协议分析验证等, 但也存在严重不足:无数据概念。因此在本文中利用颜色Petri网CPN (Colored Petri Net) [8]来对Web服务组合进行形式化建模, CPN中库所的托肯 (token) 是有类型的, 可是不同的数据类型, CPN不仅在描述系统静态模型方面有严格的形式化定义, 而且对系统动态行为的模拟仿真分析也具有形式化定义和描述。

1.1 Web服务的颜色Petri网模型

一个Web服务为一个 (sName, sDescription, sComponent, sModel) , 其中sName是Web服务的名称, 唯一标识该服务;sDescription是Web服务的描述信息, 包括服务功能、输入输出参数、服务质量、服务调用等;sComponent是组成该服务的组件Web服务的集合。如果sComponent={sName}表示该Web服务是一个原子服务, 否则既是一个组合服务;sModel是描述该Web服务的颜色Petri网。

定义1sModel= (∑, P, T, A, C, G, E, I) , 式中:

(1) ∑是Web服务中涉及的数据类型的集合;

(2) P为托肯非空有限库所集, 是Web服务参数的缓冲区;

(3) T=Tc∪T0为非空有限变迁集。其中Tc是普通变迁集, 是调用的Web服务集合;T0是零变迁集, ∀t∈T0不关联到任何Web服务, 不执行任何处理仅辅助流程的表达;

(4) A⊆P×T∪T×P是一有限弧集, 且P∩T=P∩A=T∩A=ϕ;

(5) C是一数据类型函数, 定义为C:P→∑, 指定库所p∈P中的托肯类型为C (p) ;

(6) G是一防卫函数, 定义为G:T→G (t) 。满足∀t∈T:[Type (G (t) ) =B∧Type (Var (G (t) ) ) ⊆∑], 指定变迁引发须满足的前提条件;

(7) E是弧A上的函数, 定义为E:A→E (a) 。满足∀a∈A:[Type (E (a) ) =C (p) MS∧Type (Var (E (a) ) ) ⊆∑, 其中p是A (a) 中的库所, C (p) MS是库所p的数据类型集上的多重集。E表示Web服务的输入、输出;

(8) I是一初始化函数, 定义为从P到一个封闭表达式I (p) , 满足∀p∈P:[Type (I (p) ) =C (p) MS]。

1.2 Web服务组合

Web服务组合由各个小粒度的Web服务相互之间通信和协作来实现大粒度的服务功能;通过有效的联合各种不同功能的Web服务, 服务开发者可以借此解决较为复杂的问题, 实现增值功能。Web服务组合包括五种基本结构:

(1) 调用 调用基本Web服务。

(2) 顺序 一个Web服务在另一Web服务之后执行。

(3) 选择 选择满足条件的分支, 执行该Web服务分支。

(4) 并行 在一个Web服务后多个Web服务同时执行。

(5) 循环 一个或者多个Web服务被重复的执行。

2 Web服务组合验证

使用形式化模型描述Web服务的目标是协助组合流程设计, 对流程设计进行分析验证, 发现流程设计中的错误。Web服务组合被表示为一个颜色Petri网后, 可利用CPN的性质来对其进行分析验证。

2.1 Web服务组合流程逻辑正确性

利用CPN建立了Web服务组合的模型后, 首先要确保组合流程的逻辑正确性。在此将CPN中的托肯都视为一种类型, 将CPN简化成普通Petri网。

Web服务组合流程逻辑正确性可使用Petri网的分析方法[11]加以分析验证。将CPN中所有托肯视为一种类型, 此过程可利用CPN Tools[9]完成, CPN Tool工具由丹麦Aarhus大学开发的CPN建模与仿真工具, 实现CPN的编辑、语法检查、状态空间分析及仿真运行等功能。

2.2 Web服务组合流程实例正确性

确保了Web服务组合流程逻辑正确性后, 通过CPN的初始化函数实例化流程, 利用CPN的动态行为定义来验证流程实例的正确性, 同时仿真流程实例的执行过程。

定义2 给定初始标识M0, 标志Mi称为是可达的, 当且仅当∃M0:Mi∈R (M0) 。

定义3 变迁绑定是定义在Var (t) 上的函数b, 满足:

(1) ∀v∈Var (t) :b<v>∈Type (v) ;

(2) G (t) <b>为“真”。

变迁t的绑定就是把变迁t的每个变量Var (t) 用合适的数值代替, 且防卫表达式G (t) <b>为真。变迁t所有绑定的集合记为B (t) 。

定义4 绑定元素是一 (t, b) 对, 其中t∈T, b∈B (t) , 所有绑定元素的集合用BE表示。

定义5 完全发生图是一有向图OG= (V, A, N) , 其中:

(1) V=[M0>

(2) A={ (M1, b, M2) ∈V×BE×V|M1[b>M2]}

(3) a= (M1, b, M2) ∈A:N (a) = (M1, M2)

其中M1[Y>M2表示:模型在标识M1步Y发生后, 模型的标识变为M2。完全发生图是由从标识M0的所有可达标识作为结点构成的图, 其有向弧线由BE元素标注。节点M1到节点M2的有向弧线标注为b, 当且仅当在绑定b时网标识实现从M1到M2的转变。完全发生图通过描述网标识的转变过程, 仿真了模型实例的动态执行。

利用CPN Tools对Web服务组合流程中变量赋值实例化流程后, 可生成Web服务组合流程对应颜色Petri网模型的状态发生图, 从而验证流程实例的正确性, 同时可仿真组合流程实例的执行过程。

3 建模实例

以行程安排服务组合为例:用户从A地到B地参加一个会议, 希望制定一个会议行程, 包括预订行程的交通方式和酒店房间。这个服务组合涉及以下7个Web服务操作: (1) getDriveTime (A, B) :查询从A到B的行车时间, 返回行车时间; (2) getFlightInfo (A, B) :查询从A到B的航班, 返回航班信息; (3) bookAirline (C, FNo, Date) :订购C航空公司日期为Date航班号为FNo的机票, 返回订票是否成功; (4) getTrainInfo (A, B) :查询从A到B的车次, 返回车次信息; (5) bookTrain (TNo, Date) :订购日期为Date车次为TNo的火车票, 返回订票是否成功; (6) getHotelInfo (B) :查询B地的酒店, 返回酒店信息; (7) bookHotel (H, Date1, Date2) :预定酒店H的一个房间, 时间从Date1到Date2, 返回预定是否成功。

该组合服务包含Sequence和Choice两种控制结构。Choice结构隐含那2种可能的执行序列, 是互斥选择结构, 其中服务 (2, 3) 和 (4, 5) 只需要执行其一即可。而服务1、6、7必须都执行。假设用户在选择交通方式上的约束为:如果两地的行车时间小于等于6小时, 就坐火车去;若两地的行车时间大于6小时则乘飞机去。该服务组合的CPN表示如图6所示。

通过CPN Tools建立会议行程的CPN模型后, 首先将行程模型中的托肯看作一种类型, 利用CPN Tools的家态、活性、公平性分析等功能可验证该行程安排的逻辑正确性。部分验证结果如图7所示, 通过验证结果可得出该流程是逻辑正确的。

接着对流程中的变量进行绑定, 实例化流程。对具体流程通过求解流程的完全发生图来分析验证流程实例的正确性。流程实例的仿真执行过程如图6表示, 可得出该流程实例是正确的。

4 总结与展望

Web服务技术日趋成熟, 利用网上共享的Web服务组合成功能更强大的增值服务可满足实际应用需求。工业界从不同角度出发已给出了多种Web服务组合描述语言, 但是这些语言仅给出了Web服务组合流程的定义, 无法验证流程的正确性。已有的Web服务描述模型不独立于具体的流程描述语言且不能全面地描述Web服务组合, 在本文中提出了一个Web服务的颜色Petri网模型, 在此基础上利用调用、顺序、选择、并行、循环基本组合结构可将Web服务组合成一个服务流程。该模型建立在颜色Petri网基础上, 能较全面描述流程, 同时还能够对流程的逻辑正确性、实例正确性进行分析验证, 最后通过建模实例说明了模型的实用性。在下一步的研究中准备将Web服务的执行时间、服务质量纳入建模中, 寻找最优Web服务组合方案, 结合不同Web服务的调度算法, 计算流程的执行效率, 提供效率最佳、质量最优的Web服务组合。

参考文献

[1] Tony Andrews, Francisco Curbera, Hitesh Dholakia, et al.Business Process Execution Language for Web Services Version 1.1.Specification[S].2003.

[2]Assaf Arkin, Sid Askary, Scott Fordin, et al.Web Service Choreography In-terface (WSCI) 1.0.http://www.w3.org/TR/wsci/.

[3]Rachid Hamadi, Boualem Benatallah.A Petri Net-based Model for WebService Composition[C]//Proceedings of the Fourteenth Australasian da-tabase conference on Database technologies, 2003:191-200, Adelaide, Australia.

[4]David Skogan, Roy Grφnmo, Ida Solheim.Web Service Composition inUML[C]//Proceeding of the 8th International IEEE Enterprise Distrib-uted Object Computing Conference, 2004:47-57, California, USA.

[5]Roy Grφnmo, Ida Solheim.Towards Modeling Web Service Compositionin UML[C]//ProceedingsOf The 2nd Intl.Workshop on Web Services:Modeling, Architecture and Infrastructure, 2004:72-86, Porto, Portugal.

[6]Xiaochuan Yi, Krys J Kochut.A CP-nets-based Design and VerificationFramework for Web Services Composition[C]//Proceedings of the IEEE In-ternational Conference on Web Services, 2004:756-760, San Diego, Califor-nia, USA.

[7] Murata T.Petri nets:Properties, analysis and applications[C]//Proc.IEEE, 1989, 77 (4) :541-580.

[8] Jensen K.Colored Petri Nets.Basic Concepts, Analysis Methods and Practical Use Volume 1, Basic Concepts[M].2nd ed.Monographs in Theoretical Computer Science.Berlin, Heidelberg, New York:Springer-Verlag, 1997.

时间Petri网 篇6

结构复杂的飞机温环控系统是保证飞机安全可靠飞行的重要机载设备, 当系统的某处出现故障功能失常时, 查找故障原因并精确的定位故障功能组件是飞机维修亟待解决的问题。

本文针对飞机环控系统, 提出基于功能的诊断方法, 建立了相应的功能模型, 再结合模糊Petri网建立诊断模型进行故障诊断, 推理结果证明该方法可以有效的提高故障诊断的速度和精确性。

2 功能模型

2.1 功能模型的定义

功能模型[4]具有层次性, 如图1所示, 首先, 为了对主系统进行功能分解, 即将主系统分解为具有结构关系的功能模块, 即与主系统故障相关的各主功能参数。接下来, 功能参数可进一步分解成各子系统。然后, 各子系统又可再分为与其具有结构关系的子功能参数。最后, 根据精确定位故障组件的需要, 可进一步分解, 我们把功能层次中处于底层不能再分的称为功能元, 也就是实际可能发生故障的功能组件。因此, 功能模型可表示为:

式中, 为经过分解后的功能组件;Ri为功能关系。

2.2 温控系统功能模型的建立

飞机温控系统的主要功能是为机组、乘客和设备提供飞机内部环境的温度参数控制, 其子系统包括保证温度功能参数符合要求的加温系统、冷却系统、座舱温度控制系统。其中各系统的主要功能如下:

(1) 加温系统的功能是提供暖空气来给某些区域加温, 其子功能参数为货舱加温功能、客舱增温功能, 对应的功能组件分别是外流活门、是舱门区加温器和应急出口加温毯。

(2) 冷却系统的功能是控制通过空调组件气体的输出温度, 其子功能参数可确定为流量控制功能、输出温度控制功能, 对应的功能组件分别为流量控制活门、空气循环机、冲压空气组件、水分离器、低温限制组件和低温限制活门。

(3) 座舱温度控制系统的功能是控制客舱和驾驶舱的空气温度, 其子功能参数可确定为座舱控温功能, 对应的功能组件是座舱温度传感器、管道温度传感器和空气混合活门。

综上所述, 建立飞机温环控系统的功能模型如图2所示。

3 模糊Petri网

模糊Petri网是一种适用于多系统的图形化、数学化的建模工具, 能够直观地表示系统故障的动态因果行为, 在故障诊断得到了广泛的应用。

一般情况, 用10元组来描述模糊Petri网结构[5]:

其基本推理规则的形式是:

式中:di, dk分别表示前提条件和结论, uÁ0 1为第j条规则的真实度。

4 飞机温控系统故障诊断

4.1 故障诊断模型建立

根据飞机温控系统的功能模型, 建立其故障诊断模糊Petri网, 并进行反向推理[5]的诊断。

对某航空公司提供的可靠性报告进行故障分析和概率统计后, 得到了模糊Petri网推理所需的故障数据, 进而建立故障诊断模型如图3所示。

对推理规则举例说明如下:

R1:IF外流活门故障 (P1) THEN货舱加温功能失常 (P13) (0.91, 0) ;

R2:IF舱门区加温器故障 (P2) THEN客舱增温功能失常 (P14) (0.91, 0) ;

该模糊Petri网的起始库所集合为{p1, p2, …, p12}, 目标库所为p22。

4.2 反向推理故障路径

设所有变迁的启动阈值均为0.7, 具体步骤为:

(1) 系统的已知故障“飞机温控系统故障”p22, 确定引发p22的路径, 有1条:p21→p22。

(2) 反向查找引发p21的路径有3条, 由于t18和t20的可信度最大而且相等, 故选择优先权值大的路径p20→p21。

(3) 反向查找引发p20的路径, 有1条:p17→p20。

(4) 反向查找引发p17的路径有3条, 由于p12的可信度最大, 故选择可信度大的路径p12→p17, 其中p12为起始库所。

(5) 得出故障路径:

P12→p17→p20→p21→p22, 变迁为t12, t27, t35, t38。

推理结束, 后可确定飞机环控系统的最终故障功能组件为空气混合活门故障。结果证明此故障诊断方法快速有效, 能够依据功能模型精确的定位到故障组件。

5 结论

本文首先通过分析飞机温控系统的系统功能特点, 建立了描述功能层次关系的功能模型, 可以从功能的角度来更好的分析系统, 使故障诊断更加直观和有效, 然后发挥模糊Petri网在逻辑推理方面快速性和并行性的优势, 在功能模型的基础上建立了故障诊断模型, 并进行了正反向推理相结合的故障诊断, 精确的定位到发生故障的功能组件, 提高了诊断精度和效率。

摘要：针对飞机温控系统的故障复杂性, 提出了一种基于功能的以模糊Petri网为推理算法的故障诊断方法。首先根据系统分析, 推导出子系统和系统功能参数, 建立了描述功能层次关系的功能模型, 提高了故障诊断的直观性和有效性;然后利用模糊Petri网的快速和并行推理能力, 建立了反映功能模型的故障诊断模型, 定位故障功能组件, 提高了诊断的快速性和精确性;最后通过实例验证了该方法的有效性。

关键词：功能,温控系统,故障诊断,Petri网

参考文献

[1]马存宝, 周方旺, 周建民, 黄爱军.基于有向序图模型的飞机燃油系统故障诊断的系统设计与实现[J].测控技术, 2011, 11:110~113.

[2]付永领, 庞尧, 刘和松, 张晔.基于故障建模的双余度舵机故障诊断技术[J].北京航空航天大学学报, 2011, 11:1~6.

[3]Tzafestas S G, Capkovic F.Petri Net based App roach to Syn-thesis of Intelligent Control Systems for DEDS.Computer AssistedManagement and Control of Manufacturing Systems[D].New York:Springer, 1997:5232531.

[4]袁逸萍, 孙文磊, 朱颖.基于功能需求的虚拟样机模型发现方法[J].中国机械工程, 2010, 4:437~441.

时间Petri网 篇7

电力系统故障诊断是指利用故障发生后所产生的警报信号等信息识别故障元件、评价保护和断路器动作行为,为调度人员快速辨识和清除故障提供辅助决策,以尽可能缩短故障后的系统恢复过程。国内外学者在这一领域开展了大量研究,提出了专家系统[1-3]、解析模型[4-7]、人工神经元网络[8]、信息理论[9]、Petri网和模糊集[10-14]等方法。其中,目前已实际应用的故障诊断系统主要采用了前两种方法。专家系统被较早地应用于电力系统故障诊断,文献[3]发展的警报处理专家系统已成功应用于意大利ENEL电力公司调度中心的能量管理系统中。基于解析模型的故障诊断方法[4-7]则是根据保护和断路器的动作原理,构建使实际警报信息与期望警报信息之间差异最小化的优化模型,把故障诊断问题表示为0-1整数规划;这种方法已经在一些电力系统中得到实际应用。基于Petri网的电力系统故障诊断方法虽然研究历史相对较短,但因其逻辑严密、物理意义清晰、推理过程比较简单而在近年来受到越来越多的关注。

基于传统Petri网的电力系统故障诊断方法比较简单和直观,但其无法处理故障诊断问题中的不确定性,因此一些文献提出了用模糊Petri网来解决[11-13]。文献[11]提出了基于加权模糊推理Petri网的电力系统故障诊断模型,通过优化模型结构来降低模型矩阵的规模,并利用数字型保护数据等措施来提高诊断的准确性和速度;文献[12]发展了一种基于方向性加权模糊Petri网的电力系统故障诊断方法,通过分别在各故障蔓延方向上建模分析和加权计算,以改善模型的容错性和对网络拓扑变化的适应性;文献[13]所构造的模糊Petri网模型中利用了保护和断路器动作的时序信息,提出了动作信息的纠错算法,但容错性不强。

上述基于模糊Petri网的故障诊断模型都考虑了保护/断路器动作和警报的不确定性,但仍存在以下不足:1没有充分利用警报的时序信息;2容错性不强,在处理复杂故障时有可能得不到明确的诊断结果。在上述背景下,本文发展了基于时序模糊Petri网(TRFPN)的电力系统故障诊断模型;通过将时序约束网络[15]和模糊Petri网进行融合,可以适当考虑元件故障、保护动作和断路器跳闸之间的延时约束,能够实现错误警报的自动过滤,同时在Petri网的推理运算过程中借助模糊加权算法,可以有效识别警报信息中的丢失和时序不一致等情况,提高了模型的容错性。

1 TRFPN

1.1 时序约束定义

文献[15]提出了基于时序约束网络的电力系统警报处理模型,其中的时序约束包括时间点约束和时间距离约束。下面简要介绍这两种时序约束。

1)时间点约束

定义时间区间T(t)=[t-,t+]为时间点t的约束,用于描述事件发生时间t的不确定性,即t∈T(t);其中t-和t+对应T(t)的起点和终点。

2)时间距离约束

时间距离是指两个时间点之间的时间长度。用d (ti,tj)表示ti和tj之间的时间距离,即d(ti,tj)=tj-ti。定义D(ti,tj)=[Δti-j,Δti+j]表示时间距离d (ti,tj)的约束,即d (ti,tj)∈D(ti,tj),其中 Δti-j和 Δti+j分别对应区间D(ti,tj)的起点和终点。

1.2 TRFPN的数学描述

根据模糊推理Petri网的定义[11],并考虑信息的时序属性,可将TRFPN定义为十一元组:

式中:P={p1,p2,…,pn},为库所结点(简称库所)的有限集合,表征命题,n为库所数;R={r1,r2,…,rm},为变迁结点的有限集合,表征推理规则,m为变迁数;I=(δij)n×m,为直接输入矩阵,δij∈{0,1},当pi为rj的直接输入(即存在pi到rj的有向弧)时δij=1,否则δij=0;O=(γij)n×m,为输出矩阵,γij∈{0,1},当pi为rj的输出(即存在rj到pi的有向弧)时γij=1,否则γij=0;H=(ξij)n×m,为制衡输入矩阵,ξij∈{0,1},当pi为rj的制衡输入(即存在pi到rj的制衡弧)时ξij=1,否则ξij=0;W=(ωij)n×m,为权值矩阵,ωij∈[0,1],反映命题对相应规则的影响程度,;θ=(θ1,θ2,…,θn)T,为库所对应命题的可信度向量,θi为命题pi为真的可信度,θi∈[0,1],命题初始可信度向量用θ0表示;U=diag(μ1,μ2,…,μm),为规则的可信度矩阵,μj为规则rj的可信度,μj∈[0,1];,为库所初始状态信息的获取时间集合,为库所pi初始状态的获取时间点;,为一元约束的集合,与T中元素一一对应,其元素表示时间点tpi的约束;,为二元约束的集合,其元素表示时间点和之间的时间距离约束。

1.3 时序推理

本文用库所对应命题描述事件,事件间的直接关系则分为触发和制衡两种。假如事件i可以触发事件j,则事件i为事件j的前驱事件,事件j为事件i的后继事件[15]。在文献[15]的基础上,这里进一步假定事件i可以导致事件j发生,但非必然,并用i→j表示;若事件j由事件i触发,则两事件的时间点应满足相应的时序约束。假如事件j可以制衡事件i,则称事件j为事件i的制衡事件。换言之,如果事件j发生了,则事件i就不应该发生,用i→/j表示;若事件i在某时间点发生了,则事件j就不应该在相应的时序约束内发生。

假设库所命题所描述的事件i,j,k,w在时间点ti,tj,tk,tw发生,且事件间关系为i→j,j→k和。 已知tj,tk,tw,D (ti,tj),D (tj,tk)和D(tj,tw)。下面简要说明本文所采用的时序推理方法。

1)反向时序推理

反向时序推理旨在找出事件的前驱事件,以及前驱事件的时间点约束。前驱事件具有传递性,例如:如果事件i为事件j的前驱事件,事件j为事件k的前驱事件,则事件i同样为事件k的前驱事件。如果事件i无前驱事件,则称之为原因事件,对应库所为原因库所。制衡事件不参与反向时序推理。

根据已知条件以及相应的时序运算规则,可得到原因事件的时间点约束如下:

式中:Δtj-k和 Δtj+k分别对应区间D(tj,tk)的起点和终点。

若T(ti)′∩T(ti)″≠Ø,即前驱事件相同且时间点约束有区间重叠,则可将所求前驱事件合并,即事件i的时间点约束为T(ti)′∩T(ti)″。

2)前向时序推理

前向时序推理旨在找出事件的后继事件或制衡事件,以及它们的时间点约束。根据反向时序推理所获得的原因事件时间点约束,可得到后继事件及制衡事件的时间点约束如下:

式中:ti-和ti+分别对应T(ti)的起点和终点;Δtj-w和 Δtj+w分别对应区间D(tj,tw)的起点和终点。

需要指出,时序推理中的前驱、后继及制衡关系与Petri网模型中输出有向弧、输入有向弧及输入制衡弧的连接方向并无直接联系。例如:结合反向时序推理过程和前向时序推理过程,可建立简单的TRFPN,如图1所示。若库所仅通过输入有向弧或输入制衡弧与变迁连接,则称此库所为初始库所,对应图1(a)中的库所p1至p3;若库所仅通过输出有向弧与变迁连接则为原因库所,对应库所p4;对既有输入又有输出的库所,则称之为过渡库所。库所包含时间属性,如图1(a)中的库所j的时间属性为(tj,T(tj)),其中第1项为时间点,表示该库所所描述的事件信息获取时间,若没有获得事件信息,则此项为空;第2项为时间点约束,表示该库所所描述事件如果发生则应出现的时间区间。图1(a)中变迁r1可表示规则“已知事件j,k,w及其发生时间,推理事件i是否发生及其发生时间区间”。

1.4 TRFPN的矩阵运算

本节将信息的时序属性融入模糊Petri网,发展相关的模型和矩阵运算方法。考虑到已有不少文献(如文献[11-12])对模糊加权Petri网的矩阵运算规则及方法做了详细介绍,此处不再赘述,只在附录A中进行了概述。下面仅介绍TRFPN的时序部分的运算方法及步骤。

步骤1:读入库所初始状态信息的获取时间集合T,以及时序约束库。

步骤2:进行反向时序推理,获取原因库所的时间点约束,并合并相关约束。

步骤3:根据步骤2获得的原因事件的时间点约束,进行时序推理,确定Petri网各库所的时间点约束。

步骤4:将初始状态信息的获取时间与步骤3得到的Petri网各库所的时间点约束进行比较和计算,采用式(7)和式(8)的方法得到命题初始可信度向量θ0。

式中:i=1,2,…,n;函数f(Δti)的形式可以根据信息获取的频率与 Δti的统计分布关系来选取,通常可取阶跃函数、线性函数和双曲线函数等,若信息随机出现在对应的时间点约束区间内,极少出现在区间外,则f(Δti)可取阶跃函数形式,若信息出现在对应的时间点约束区间内的频率很高,但仍会出现在区间外,且信息的出现频率随 Δti呈线性或双曲线函数关系,则f(Δti)取相应的函数形式;参数h的取值范围为0~1,其表示信息没有出现时命题的可信度取值,可根据信息的漏报概率调整h的取值,若漏报概率较高,可调高其取值,反之则降低其取值。

综上所述,TRFPN的推理运算的总体框架见附录B图B1。

2 基于TRFPN的电力系统故障诊断模型

以IEEE 10机39节点系统(见附录B图B2)为例,说明基于TRFPN的电力系统故障诊断模型。假设每条线路两端均配置了主保护、近后备保护和远后备保护;每条母线都配置了主保护;每个断路器都配置了断路器失灵保护。用B,L,R,CB分别表示母线、线路、保护和断路器;R0318m表示线路L0318靠近母线B03 的主保护,R1803m表示对侧主保护;R0318p,R0318s,R0318mf,CB0318分别表示相应的近后备保护、远后备保护、失灵保护和断路器。

2.1 故障诊断时序分析

实际系统中的继电保护装置都整定了动作时限。根据保护时间整定值并考虑实际运行时的时间误差可以估计从设备故障到相应保护动作的时间距离/区间。用D(tf,tm),D(tf,tp),D(tf,ts)分别表示设备故障到主保护、近后备保护和远后备保护动作的时间距离。与一般电气量保护(如线路主保护)采用单一电气量方式启动不同,断路器失灵保护采用保护出口动作和电气量方式构成“与”门启动,并延时动作;所以可估计线路主保护等电气量保护动作到断路器失灵保护动作的时间距离,并用D(teqr,tmf)表示。断路器分闸时间是其固有属性,由分闸时间并计及实际运行时的时间误差可估计保护动作到相应断路器分闸的时间距离,并用D(tr,tcb)表示。

2.2 故障诊断模型

首先建立线路的故障诊断模型。基本思路为:首先分别对线路两侧故障蔓延方向的各类保护和断路器进行建模,然后构建线路的综合诊断模型。以附录B图B2中线路L0318为例,其TRFPN故障诊断模型如图2所示。图2中:库所p30表示事件L0318故障,为原因库所;库所p1表示事件主保护R0318m动作,为初始库所;库所p22至p29为过渡库所,无实际物理意义,起连接和置信度流通的作用;p30和p1为触发关系。将各事件编码并生成关系约束库,见附录C。库所的时间点属性为警报获取时间,若没有获取此警报信息,则此项为空。通过时序推理,可获得原因库所的时间点约束T(tL0318),进而获得如表1所示的初始库所的时间点约束。过渡库所由于自身含义的限制,无法获得其时间属性,其时间点属性可理解为空,即时间点无约束。变迁r1表示规则 “主保护R0318m动作跳开断路器CB0318”;变迁r2表示规则“断路器失灵保护R0318mf由主保护R0318m出口启动并延时动作跳开断路器CB0302和CB0304”;r3至r8依此类推;r9至r15为过渡变迁。

类似地,可构建母线的综合故障诊断模型。以母线B04为例,其TRFPN故障诊断模型和库所时间点约束分别如附录D图D1和表D1所示。

2.3 仿真参数确定

将TRFPN应用于电力系统故障诊断时,需要确定如下参数。

1)输入弧权值

在正常情况下,断路器跳开是保护动作的结果,这在相当程度上标志了保护的行为,所以断路器部分的权值应大于保护部分的权值。对于某一变迁,其输入库所的保护部分的权值与断路器部分的权值分别设定为0.4和0.6。以图2中的变迁r6为例,其输入库所p13,p15,p16和p17的权重分别为0.2,0.2,0.3和0.3;其中,库所p13和p15及库所p16和p17分别表示变迁r6的保护部分及断路器部分。

2)变迁可信度

前已述及,将保护划分为主保护、近后备保护、远后备保护和断路器失灵保护。由于不同类型的保护原理不同,各类保护的性能及可靠性也不一致,故由此赋予变迁不同的可信度[13]。各类保护的变迁可信度如下:主保护为0.9、近后备保护为0.8、远后备保护为0.7、断路器失灵保护为0.95。过渡变迁无物理意义,可将其可信度置为1。

3)库所初始可信度

实际电力系统发生故障时,保护和断路器可能不正确动作,警报信号也可能误报和漏报。可采用式(8)来计算库所初始可信度。在所发展的基于TRFPN的故障诊断模型中,将f(Δti)定义为阶跃函数,且仅计算初始库所的初始可信度,把其他库所的初始可信度置为零。从容错性的角度出发,当Δti=0,即警报出现且满足时序约束,则说明事件间具有强关联性,就将对应库所的初始可信度置为0.95;当 Δti≠0,即警报出现但不满足时序约束,则说明事件不关联,就将对应库所的初始可信度置为0.1;如果没有出现警报,即 Δti不存在,则把对应库所的初始可信度置为0.2[12]。

3 仿真算例验证及比较

以附录B图B2所示的IEEE 10机39节点系统为例来说明所发展的故障诊断模型的基本特征。为描述方便,给定下述定义:1(i,ti)为事件—时间点组,表示在t=ti时事件i发生;2(i,T(ti))为事件—时间点约束组,表示在事件区间T(ti)内事件i发生。

3.1 基于TRFPN的故障诊断过程

下面用一个简单的故障案例来说明诊断过程。该案例的细节为:线路L0318故障,主保护R0318m动作跳开CB0318;另一侧主保护R1803m拒动,由近后备保护R1803p跳开CB1803;得到的警报(以第1个接收

到的警报信号的时标为基准点,并定义其时标为0(单位为ms)) 为: (R0318m,0), (CB0318,47),(R1803p,489),(CB1803,545)。

1)根据警报信息和关系约束库,进行反向时序推理,获得并合并原因库所时间点约束,见附录D表D2。

与现有故障诊断方法一般需要首先进行网络接线分析不同,本文所构造的故障诊断模型能够以关系约束搜索为基础,寻找原因事件,进行下一步的分析和诊断。当故障边界断路器警报信息丢失时,采用接线分析无法得到正确结果,现有的故障诊断方法就无法继续,而本文发展的模型则不受此约束。当然,根据正确的网络接线分析结果可以去除不合理的原因库所,提高诊断速度。

2)根据原因库所及时间点约束进行正向时序推理,获得各库所时间点约束。

以(L0318,[-20,-10])为例,将时间点约束值代入表1即可。

3)计算库所命题初始可信度。

以(L0318,[-20,-10])为例,库所初始可信度向量θ0= (0.95,0.95,0.2,0.2,0.2,0.1,0.2,0.1,0.2,0.2,0.2,0.2,0.2,0.1,0.2,0.2,0.1,0.95,0.95,0.2,0.2,0,0,0,0,0,0,0,0,0)T。

4)运用式(A4)进行矩阵运算。

根据图2所示的L0318模型,可得到如附录E图E1所示的模型矩阵形式。

采用式(A4)计算(L0318,[-20,-10])的可信度,经过5次迭代计算达到计算截止条件,结束计算,迭代计算过程见附录F。最后得到的结论为:(L0318,[-20,-10])的可信度为0.807 5(同理可获得其他原因库所的可信度),进而判断L0318 在-20~-10ms期间发生故障。

3.2 继电保护装置评价

通过比较原因库所的可信度判断出故障元件及其时间区间之后,需要对故障的发展进行解释,并对继电保护和断路器动作状况及警报信息进行评价。

以单条线路故障为例,将故障在某蔓延方向上的切除方式分为主保护动作跳开相应断路器、断路器失灵保护由主保护启动并延时动作跳开相应断路器、近后备保护动作跳开相应断路器、远后备保护动作跳开相应断路器4种方式,分别简称为m方式、mf方式、p方式和s方式,并与相应变迁一致。

1)警报信息分组。将满足故障元件及其时间区间的时序约束的警报信息放入评价表,不满足约束的警报信息放入待评价表,将评价表上的警报信息按故障切除方式进行分组。

2)通过比较过渡库所最终置信度,确定故障切除方式,并进入下述的故障判定过程。

m方式:判定主保护及相应断路器正常动作,并将mf,p,s分组中的警报信息放入待评价表。

mf方式:判定主保护正确动作,主保护对应的断路器拒动,断路器失灵保护及其对应的断路器正确动作。 将p和s分组中的警报信息放入待评价表。

p方式:判定近后备保护及相应断路器正常动作,将s分组中的警报信息放入待评价表。若m分组中包含警报信息,则判定主保护正常动作,相应断路器拒动,断路器失灵保护拒动;否则判定主保护拒动。

s方式:判定远后备保护及相应断路器正常动作。若m分组中包含警报信息,则判定主保护正常动作,相应断路器拒动,断路器失灵保护拒动;否则,判定主保护拒动。若p分组中包含警报信息,则判定近后备保护正常动作,相应断路器拒动;否则,判定近后备保护拒动。

3)对评价表中的警报进行评价:若判定继电保护装置拒动,而警报信号出现,则警报属于误报;若判定继电保护装置动作,而警报信号未出现,则警报信息系漏报。

4)对待评价表中的警报进行评价:1判定警报漏报,而在待评价表中出现了该警报,则改判该警报时标错误;2若待评价警报中,保护和断路器警报满足时序约束,则判定保护误动;3判定不满足时序约束的保护警报信息为误报;4判定不满足时序约束的断路器警报为误报,并请求进一步确定。

母线发生故障时,评价过程与此类似。对于多元件发生故障的情形,则需考虑多故障蔓延方向上存在交界时,与交界相关的保护和断路器的评价问题。

3.3 算例分析与比较

3.1节中用简单案例说明了所发展的故障诊断方法的诊断过程。这里给出一些更为复杂的案例以及采用不同的诊断方法所得到的诊断结果,列于附录G表G1。

在附录G表G1中,故障案例1至3的警报信息是完备的。可以发现,在保护/断路器存在误动/拒动等复杂状况下,依然可以得到正确的诊断结果,表明所提出的方法对这种情形有较好的容错性。案例4至7包括了警报误报、丢失或时标错误等复杂场景,其中案例6和7均为两个元件先后故障情况。算例结果表明,警报丢失或其时标错误会使正确诊断结果的可信度降低,而错误警报则会导致错误诊断结果的可信度上升。不过,从这些故障案例的整体诊断结果可以看出,由于本文方法具有加权效应且融合了时序约束,警报不完备和错误警报对故障诊断结果的影响相对较小,表明其对这种情形也有较好的容错性。

综上所述,基于TRFPN的故障诊断模型能够处理保护/断路器发生误动/拒动以及警报信息错误与不完备的情况,且具有较高的容错性。

此外,将本文方法与文献[12]和文献[15]的方法进行了比较,结果如表2所示。

4 结语

本文首先将时序约束融入模糊Petri网,在此基础上提出了基于TRFPN的电力系统故障诊断方法。大量诊断案例表明,所提出的方法能够处理保护/断路器发生误动/拒动以及警报信息错误与不完备的情况,并可以对继电保护的动作情况进行适当评价。本文提出的方法可自动生成故障诊断模型,且可跟踪网络拓扑变化;通过与现有方法的定性比较分析可知,在增加少量计算量的情况下,故障诊断的容错能力有了较大提高,可用于大规模复杂电力系统的在线故障诊断。