您当前的位置:五五电子网电子知识单片机-工控设备DSP/FPGA技术组合着色Petri网空间复合事件检测机制 正文
组合着色Petri网空间复合事件检测机制

组合着色Petri网空间复合事件检测机制

点击数:7973 次   录入时间:03-04 11:37:43   整理:http://www.55dianzi.com   DSP/FPGA技术

摘要:通过建立空间事件模型,扩展定义了空间事件复合算子及其语义;采用组合着色Petri网构造基于空间关系的复合事件检测模型并提出基于该模型的检测算法;通过应用实例验证该检测模型是一个简洁、有效的复合事件检测机制。

        关键词:空间复合事件 组合着色Petri网 复合事件检测

        复合事件及其检测可以应用到股票交易、网络管理、航空交通控制、指挥决策等领域。随着空间信息的广泛应用,在远程监控、LBS、LOCation-aware计算等领域,也需要实现与空间有关的事件检测。传统空间信息应用系统中与空间有关的复合事件检测通过在应用处理逻辑中直接编写事件检测的代码实现。这种解决方案不利于实现开放的、可扩展的通用系统。由于很多事件是通用的,事件检测机制应该是多个应用系统共享,否则系统的维护代价较大。
  
        对复合事件检测的研究最初是在主动数据库领域中进行的。Ode采用有穷自动机实现复合事件检测。SAMOS采用着色Petri网对复合事件检测,可以携带事件流及事件参数等复杂信息。但是SAMOS也没有定义和说明Petri网的组合问题。为解决不满足交换律的复合算子的冲突问题,文献引入了时序算子,提出TRPetri网。文献引入部分检测事件缓冲池和时间缓冲池对原子事件进行高效的过渡。在空间事件检测方面目前尚未展开更多的研究工作,文献使用三元组{OID,TS,LOC}定义空间事件模型,支持简单的空间谓词检测,但是这种方法是基于空间对象而不是基于事件本身的空间属性。文献讨论了从空间完整性约束导出数据库ECA规则的方法,由于ECA条件和动作部分可以分别在数据库中的查询处理和事务处理技术中找到相应的解决方案,而事件部分研究的不是很多。本文将在此基础上,研究基于空间关系的复合事件检测机制。

1 空间事件模型

        在讨论基于空间关系的复合事件检测机制之前,首先必须形式化描述空间事件及空间事件复合算子。空间事件模型采用三元组来表示SE={EID,T,S},其中EID∈N表示参照坐标系统定义的坐标。空间对象和空间谓词SP(Spatial PreDICate)定义如下:

        简单线段L:Sbeginf×Send,Sbegin,Send∈R×R,Sbegin和Send分别表示线段起始点和结束坐标;坐标S在线段L上时IN(S,L)为真。

        封闭区域Z:∪(L×N);坐标S在区域Z内时IN(S,Z)为真。

        假设方向关系是参照坐标系统定义的,即North方向与y轴方向一致,East方向与x轴方向一致。令b表示对象的MBR,则b可以通过其左下角坐标(b.xl,b.yl)和右上角坐标(b.xu,b.yu)定义。如果以s为目标,b和s1分别是参考矩形和参考点,那么采用基于投影的方向模型,s相对于b、s1的方向关系谓词可以由North-South方向(N,S)s,b、(N,S)s,s1‘和East-West方向(E,W)s,b、(E,W)s,s1的组合定义。其中,(N,S)s,b和(E,W)s,b可以通过下面的公式定义,(N,S)s,s1和(E,W)s,s1可以采用类似方式定义:

        如果将(N,S)s1,s2和(E,W)s1,s2的组合记作(N,S,E,W)s1,s2,那么基于四元组(N,S,E,W)s1,s2的不同取值可以定义s1相对于s2的16种方向关系,如NW(s1,s2)=(1,0,0,1)。

        空间事件的语义解释函数φ(SE):T×S→{True,False}定义为:φ(SE(t,s)=True,if an event of type SE oCCurs at time t and location s。

·非空间算子NOS(NonSpatial Operator)

OR(SE1,SE2)(t,2)=SE1(t,s)∨SE2(t,s)

AND(SE1,SE2)(t,s)=∈t1(((SE1(t1,s1)∧SE2(t,s))∨(SE2(t1,s1)∧SE1(t,s)))∧t1≤t)

NOT(SE2,SE2,SE3)(t,s)=∈t1∨t2(SE1(t1,s1)∧~SE2(t2,s2)∧SE3(t,s)∧((t1≤t2<1)→~(SE2(t2,s2)∨SE3(t2,s)))

ANY(m,SE1,SE2,…,SEn)(t,s)=∈t1∈t1…∈tn-1(SEi(t1,s1)∧SEj(t2,s2)∧…SEk(tm-1,sm-1)∧SEl(t,s)∧(t1≤t2≤…≤tm-1≤t)∧(1≤i,…,k,l≤n)∧(i≠...≠k≠1))

SEQ(SE1,SE2)(t,s)=(t,s)=∈t1(SE1(t1,s1)∧SE2(t,2)∧t1≤t)

A(SE1,SE2,SE3)(t,s)=∈t1∨t2(SE1(t1,s1)∧SE2(t,s)∧t1≤t∧((t1≤t2

A*(SE1,SE2,SE3)(t,s)=∈t1(SE1(t1,s1)∧SE3(t,s)∧t1≤t)

P(SE1,T[:param],SE3)(t,s)=∈t1∨t2(SE1(t1,s1)∧SE3(t,s)∧((t1≤t2

P*(SE1,T:param,SE3)(t,s)=∈t1(SE1(t1,s1)∧SE3(t,s)∧(t≥t1+T))

·空间算子SO(Spatial Operator)

拓扑算子:WITHIN(SE1,Z1,Z2,…,Zn)(t,s1)=∈s1(SE1(t,s1)∧(IN(s1,Z1)∨...∨IN(s1,Zn)))

WITHIN(SE1,L1,L2,…,Ln)(t,s1)=∈s1(SE1(t,s1)∧(IN(s1,L1)∨...∨IN(s1,Ln)))

距离算子:DIST(SE1,D,SE3)(t,s2)=∈t1∈s2(((SE1(t1,s1)∧SE2(t,s2))∨(SE2(t1,s1)∧SE1(t,s2)))∧t1≤t∧(||s1-s2||≤D))

方向算子(以NW为例):

NW(SE1,SE2)(t,s)=∈t1(((SE1(t1,s1)∧SE2(t,s)∨(SE2(t1,s1)∧SE1(t,s)))∧t1≤t∧(NW(s1,s)=(1,0,0,1)))

NW(SE1,B)(t,s)=SE1(t,s)∧(s,B)=(1,0,0,1))

        方向和距离算子有参考事件或者区域,因此这些算子是不满足交换律的。从定义来看,这些算子在时间上是以参考事件的出现为检测起始事件的。

2 基于组和着色Petri网的空间复合事件检测模型

2.1 检测模型

        传统的Petri网对于公共事件表达需要构造冗余的Petri网,而且无法对位置信息进行检测,需要对之改造和扩展。本文提出基于组合着色Petri网的复合事件检测模型,既能够利用复合事件的公共表达式,也可以在存储较少事件历史的情况下,保持积聚算子。

        定义(1)——复合事件检测组件Petri网CPU(Component Petri Net)

        CPN的静态结构是一个八元组,CPN=(P,PI,PO,T,A,C,E,W)相关含义如下:

        P是库所的有限集合。将每个原子事件对应到组件Petri网的一个输入库所,复合事件对应到组件Petri网的一个输出库所,则定义PI∈P为有限输入库所集合,定义Po∈P为有限输出库集合。T是变迁的有限集合。A∈P×T∪T×P是连接变迁和库所的孤的有限集合。C是标记类型(即颜色)的有限集合。E为弧函数。将每条弧映射到一个表达式、空间算子或者是缺省的单位权值。Eik表示由Pi到Tk或者Ti到Pk的弧函数。其中权值函数只作用在P×T,空间算子只作用在T×P。W:T→N变迁权值函数,将每个变迁映射到一个自然数表示的权值。

        定义(2)——组件Petri网的联接变迁、联接弧及标记向量

        联接变迁(Connection Transition)集合Tol为联接输出库所和输入库所的变迁,联接弧(Connection Arc)集合Aol定义为Aoi∈Po×Tol∪Tol×PI,同时定义PT为联接输入库所集合,PTO为联接输出库所集合。令Pi∈P,mark(Pi)=(t,s)表示Pi中当前标记的值,其分量分别标记为mark(Pi).t和mark(Pi).s。当mark(Pi).t=0时表示Pi中当前无标记。令Tk∈Tol∪T,°Tk表示Tk所有输入库所的集合,Tk°表示Tk所有输出库所的集合。

        定义(3)——组合着色Petri网CCPN(Compositional Colored Petri Net)

        定义(4)——变迁的授权

        称变迁Tk是授权的,如果对∨i,Pi∈°Tk,mark(Pi).t≠0。授权变迁可被触发,触发时同时执行如下三个步骤:(1)如果Pi中标记数与Ai,k权值相等,mark(Pi)=0,对∨I,Pi∈°Tk,如果Pi中标记数小于权值,则将标记数累加并且库所只保留最近的标记信息;(2)如果Ak,I上未定义空间谓词并且Pi中标记数与Ai,k权值相等,则mark(Pj)=Ekj(MAX{Eik(mark(Pi))|对∨I,Pi∈Tk}),对∨j,Pj∈Tk°,其中MAX{(a1,b1),(a2,b2),…,(an,bn)=a,b},1≤k≤n,1≤i≤n,ai≤ak;(3)如果Ai,k上定义的SP为真,则mark(Pj)=Ekj(MAX{Eik(mark(Pi))|对∨i,Pi∈°Tk}),对∨j,Pj∈T°k,其中MAX{(a1,b1),(a2,b2),…,(an,bn)=a,b},1≤k≤n,1≤i≤n,ai≤ak;如果Ak,I上定义的SP为假,则mark(Pi)=0,对∨i,Pi∈°Tk。

        使用组件Petri网组合CCPN时,用联接弧将组件Petri网的输出库所与一个联接变迁联接,同时将该联接变迁通过联接弧与另一个组件Petri网的输入库所相联。这样的连接不会影响组件Petri网自身的触发过程,而其触发又可以带动整个CCPN的触发,从而简法、有效地组合成了更复杂的事件检测Petri网。可以有两种方式构成CCPN,即事件作为多个复合事件的组件事件,如图1(a);或者复合事件作为进一步复合事件的一个组件事件,如图1(b)。原子事件有可能对应到多个组件Petri网的输入库所,因此进行全局模式的事件检测时,CCPN在递归触发时需要将事件类型及其发生时刻、发生位置在网上传播。这样,对应于同样的原子事件只需要一次检测即可。对于复合事件也是一样的策略,在每个CPN输出库所中都将检测到的复合事件保存到事件链表中。

[1] [2]  下一页


本文关键字:检测  空间  DSP/FPGA技术单片机-工控设备 - DSP/FPGA技术

《组合着色Petri网空间复合事件检测机制》相关文章>>>