面向车联网的时空事件处理语言STEP*

李慧勇，陈仪香

华东师范大学 教育部软硬件协同设计技术与应用工程研究中心，上海 200062

面向车联网的时空事件处理语言STEP*

李慧勇，陈仪香+

华东师范大学 教育部软硬件协同设计技术与应用工程研究中心，上海 200062

LI Huiyong,CHEN Yixiang.STEP:a spatial-temporal event processing language for Internet of vehicles. Journal of Frontiers of Computer Science and Technology,2016,10(7):959-974.

车联网是物联网技术应用于智能交通领域所形成的重要研究领域。复杂事件处理技术是车联网系统数据流处理的重要方法。有别于经典的物联网系统，车联网中数据流包含大量的时间和空间信息。在复杂事件处理技术中，如何有效地表达和处理车联网的时空数据流成为亟待解决的问题。针对该问题，提出了一种时空事件处理语言（spatial-temporal event processing language，STEP）。STEP分别采用时间段和栅格地图作为时间和空间模型。基于该时空模型，首先给出STEP语言的相关时空算子和完整语法，从而有效地表达车联网中时空事件流的时空信息。然后，分别从形式语义学角度引入STEP语言的操作语义，并且从实现角度给出了基于Petri网模型的时空事件流处理算法，从而建立车联网时空事件流处理机制。最后，通过实验说明了基于STEP语言的车联网时空事件流处理机制的有效性。

物联网；车联网；复杂事件处理；事件处理语言；形式语义；时空事件流

1　引言

车联网系统（Internet of vehicles，IoV）是物联网理论在智能交通领域的重要应用[1-2]。随着时钟技术、定位技术以及各种传感设备在车联网系统中的大规模应用，用户可以非常方便地得到系统中移动体的时间、位置、方向、速度等数据。但是，车联网中移动体在移动过程中会产生大量的数据流，为了有效处理这些数据流，很多学者提出了多种车联网信息处理体系结构[3-4]。其中，一些学者将事件驱动体系结构（或复杂事件处理技术）应用到车联网系统的数据流处理中，取得了良好的效果[5-7]。

复杂事件处理技术是通过事件处理语言，将系统产生的海量数据流过滤为用户所关注的事件实例流。当系统中有用户关心的事件实例发生时，该事件实例被发送到用户端的事件库或者根据用户预先定义好的处理规则，实时地或者接近实时地做出相应的处理。复杂事件处理技术已经成功地应用于物联网系统中[8-9]。在面向物联网的复杂事件处理语言中，采用恰当的时空模型是非常重要的。

在早期的事件处理语言中，主要关注事件之间的时序关系。Xchange[10]是一种基于条件事件代数（condition event algebra，CEA）的复杂事件处理语言。该语言属于类结构化查询语言（structured query language，SQL），其引入了时间事件以支持含有时间的事件间的运算。ETALIS[11]是一种基于规则的复杂事件处理语言，该语言关于时间的算子有during、starts、equals、finishes、meet等。RCEDA[12]可以描述一系列顺序发生的事件和在一系列时间段发生的事件。CE language[13]可以表达选择、连续、并行和重复等事件的组合。

近来，也有一些事件处理语言主要关注事件之间的空间关系。文献[14]设计和实现了一种基于位置的智能服务，其中包含两个空间关系谓语：Within 和Distance。文献[15]讨论了空间警报的相关问题。例如，用户首先描述一定的空间范围，如果有物体运动到该区域，则敲响警报。

车联网系统中的事件同时具有时间和空间特性，因此车联网中的事件处理语言应该包含时空算子。文献[5]提出了一种SpaTec复杂事件处理语言，可以描述监视内容的时空属性。SpaTec语言引入6种基本事件操作算子（concurrency,conjunction,remote,sequence,disjunction,samelocation）和4种组合事件操作算子（same location and sequence,remote and sequence,same location and concurrency,remote and concurrency）。文献[6]将SpaTec语言应用于伦敦市的公交车监控系统。文献[7]提出了一种事件处理语言CPSL，这种语言可以描述车联网中事件的多种时间和空间关系。这两种语言都采用简化的Allen时间模型[16]为时间数据模型。

SpaTec语言采用以坐标点为中心的圆形区域为其空间数据模型[5-6]。CPSL语言采用点集和凸多边形的空间数据模型[7]。这两种语言的空间数据模型存在如下两个问题：第一，与地理信息系统的空间模型不兼容。车联网系统中各对象可以与地理信息系统共享空间信息并获得全局地图，因此应该采用与地理信息系统兼容的空间模型。第二，没有考虑空间数据的方向关系。

本文提出了一种针对车联网系统的时空事件处理语言（spatial-temporal event processing，STEP），建立该语言的语法和操作语义。与上述语言相比，主要强调以下两点改进：

（1）采用地理信息系统中栅格地图模型作为车联网系统的空间模型。

（2）基于栅格地图空间模型，给出了车联网空间数据方向关系的判断方法。

另外，事件实例流的处理需要将事件处理语句转化为相应的事件流处理模型并最终编程实现。目前已有的事件流处理模型有：基于树的事件流处理模型、基于图的事件流处理模型、基于Petri网的事件流处理模型、基于自动机的事件流处理模型。因为Petri网模型[17]可用于模拟带有并发性、异步性、分布式、非确定性、并行性等特性的系统，所以在车联网系统中采用基于Petri网的事件流处理模型。

本文内容组织如下：第2章介绍车联网系统的时空数据模型、时空事件实例模型和车联网时空事件实例流处理框架；第3章设计STEP语言的语法；第4章建立STEP语言的操作语义；第5章设计基于Petri网处理模型的车联网时空事件流处理算法；第6章通过实验说明基于STEP语言的时空事件流处理机制的有效性；最后是本文的工作总结以及进一步的工作方向。

2　车联网的数据模型及时空事件实例模型

在车联网系统中，各类传感设备连续不断地产生着大量的多源、多维数据。这些数据包括时间、位置、方向、速度、加速度、温度、车牌号、交通信号等，它们大部分可以用常见的数值模型表示，例如速度可以用实数表示。下面重点介绍车联网中的时空数据模型和时空事件实例模型。

2.1车联网系统的时间数据模型

在车联网系统中，传感器一般是周期性地识别物理状态并产生相应数据。因此在车联网系统中，无法获得数据发生的具体时间点，而只能获得事件发生的时间区间。本文用时间区间来定义车联网的时间数据模型。

定义1车联网中的时间数据模型是一个时间区间，其值为两个时间点组成的序对，记为TIME=(start,end)。其中，start表示时间的起始点，而end表示时间的终止点。本文用24小时制来表示时间，并精确到秒。

例如：（20:14:10,20:14:35）表示车联网中的一个时间区间数据。

时间区间数据之间的时序关系已经有很多研究成果，比较经典的有Allen定义的基于时间段的7种时序关系[16]。根据车联网研究的实际需求，本文采用简化的Allen时序关系模型，其关系如表1所示。

Table 1　Temporal relationships of STEP表1　STEP语言的时序关系

根据表1，时间数据之间的时序关系可以通过比较时间数据模型的起始时间点start和结束时间点end的关系得到。设有两个时间数据分别为TIME1=(start1,end1)和TIME2=(start2,end2)，则车联网时间数据的时序关系判断条件分别为：

（1）TIME1BEFORE TIME2

判断条件：end1

（2）TIME1EQUALTIME2

判断条件：start1=start2且end1=end2。

（3）TIME1OVERLAPTIME2

判断条件：start1

（4）TIME1DURING TIME2

判断条件：start1≥start2且end1≤end2。

例如：时间数据（20:14:00,20:14:35）和时间数据（22:00:10,22:15:35），因为20:14:35小于22:00:10，所以二者的时序关系为BEFORE。

2.2车联网系统的空间数据模型

本文车联网的空间数据模型需要与地理信息系统（geographic information system，GIS）的空间数据模型保持兼容。在地理信息系统中，空间数据（或称为地图空间）可以用栅格空间数据模型表示。栅格空间数据模型是把空间看作一个处处连续的整体，并将空间划分为大小均匀的规则网格阵列，每个网格为一个栅格，有唯一的行列号。行与列的数目取决于系统的分辨率及空间实体的特征。栅格数据模型中的基本单元是栅格。栅格空间数据模型中的点（point）、线（line）和区域（area）表示分别如图1中的（a）、（b）和（c）的黑色部分。

Fig.1　Point,line and area of grid saptial data model图1　栅格空间数据中的点、线和面

定义2车联网的空间数据模型为栅格空间数据模型，其值为一组相邻的栅格行列号序对集合，记为LOCATION={(row1,column1),(row2,column2),…,(rown, columnn)}。

例如：图1（a）中的点空间数据可以记为{(3,3)}，图1（b）中的线空间数据可以记为{(3,3),(3,4),(3,5),(3, 6),(4,6),(5,6),(6,6),(6,7),(6,8)}。

车联网中空间数据模型的方向关系是非常重要的。例如：如果要监控一辆行驶中的汽车是否超车，则需要判断两辆汽车的方向关系。下面给出车联网中空间数据模型的方向关系的定义。

定义3基于栅格空间数据模型，定义7种空间方向关系，分别为NORTH（在北方），EAST（在东方），NORTHEAST（在东北方），NORTHWEST（在西北方），EQ（空间相等），OP（空间相交），IN（在空间内）。

在上述定义中，NORTH、EAST、NORTHEAST、NORTHWEST这4种关系主要描述两个相离（空间数据集合的交集为空）空间数据之间的方向关系。由于空间位置的对称性，“a在b的南方”可以等价表示为“b在a的北方”，上述4种空间关系可以完整描述8种空间数据之间的不相交位置关系。EQ、OP和IN 这3种空间位置关系主要描述两个有交集的空间数据之间的关系，其中EQ关系描述两个相等的空间数据，IN关系描述一个空间数据是另一个空间数据的子集，OP关系描述非EQ和非IN关系的空间数据有交集的方向关系。

该定义中的空间方向关系如表2所示。

根据表2，空间数据之间的方向关系可以通过比较空间数据模型的栅格集合关系得到。设有两个空间数据分别为LOCATIONa={(rowa1,columna1), (rowa2,columna2),…,(rowan,columnan)}和LOCATIONb={(rowb1,columnb1),(rowb2,columnb2),…,(rowbn,columnbn)}。设rowa和columna分别表示空间数据的行值序列和列值序列(即rowa={rowa1,rowa2,…,rowan}，columna={columna1,columna2,…,columnan})，min()和max()两个函数分别为求最小值和最大值运算，则min(rowa) 和max(rowa)分别表示求空间数据LOCATIONa中行值的最小值和最大值。min(columnb)和max(columnb)类似地表示LOCATIONb中列值的最小值和最大值。基于上述假设，车联网空间数据间的方向关系判断

条件分别为：

（1）LOCATIONaNORTH LOCATIONb

判断条件：max(rowa) min(columnb)且max(columna)

（2）LOCATIONaEAST LOCATIONb

判断条件：min(columna)>max(columnb)且max (rowa)

（3）LOCATIONaNORTHEAST LOCATIONb

判断条件：max(rowa) max(columnb)。

（4）LOCATIONaNORTHWEST LOCATIONb

判断条件：max(rowa)

（5）LOCATIONaEQ LOCATIONb

判断条件：LOCATIONa=LOCATIONb。

（6）LOCATIONaOP LOCATIONb

判断条件：LOCATIONa∩LOCATIONb≠∅。

（7）LOCATIONaIN LOCATIONb

判断条件：LOCATIONa⊂LOCATIONb。

例如：判断两个空间数据LOCATIONa={(502, 1 325),(503,1 325),(504,1 325),(504,1 325),(505, 1 325),(505,1 326),(505,1 327),(505,1 327)}和LOCATIONb={(747,1 324),(747,1 325),(747,1 326), (747,1 327),(747,1 328)}的关系。

解：因为max(rowa)=505，min(rowb)=747

所以max(rowa)

又因为min(columna)=1 325，min(columnb)=1 324

所以min(columna)>min(columnb)

而max(columna)=1 327，max(columnb)=1 328

故max(columna)

合之，有LOCATIONaNORTH LOCATIONb。

Table 2　Spatial relationships of STEP表2　STEP语言的空间关系

2.3车联网系统的时空事件实例模型

在事件驱动体系结构的车联网系统中，所有的数据都被抽象成事件实例。因为车联网系统的数据都具有时空特性，所以车联网系统的事件实例也同时具有时空特性。设车联网系统中要关注的对象（例如行驶中的汽车、交通信号灯、交通限速牌等）的各种状态属性值（例如速度、时间、位置、方向、状态值等）可以由各种类型传感设备感测得到，则某个具体对象某次得到的数据集合就是该对象的一个时空事件实例（spatial-temporal event instance）。

定义4车联网系统时空事件实例是由车联网中对象的各种感测数据组成的序列：EventInstance={ID,TIME,LOCATION,ATTRIBUTE}。其中，ID为车联网系统中约定对象的唯一标识值，其值可以是IP地址、二维码、RFID标签等。TIME为时间属性值，该值采用定义1中的时间数据模型。LOCATION为空间属性值，该值采用定义2中的空间数据模型。ATTRIBUTE={Attribute1,Attribute2,…,Attributen}，Attribute1,Attribute2,…,Attributen分别为其他各类数值型属性值，其主要包括速度、加速度、温度、湿度等。

该定义强调车联网中的事件实例必须具有时空特性，因此事件实例中的时间属性值和空间属性值不可或缺。车联网中各类传感器不断地产生数据，因此这些基本时空事件实例序列就构成了时空事件实例流，如图2所示。

例如：车联网中，一辆ID为“10541”的汽车每隔10 s向外发布一次其行驶速度值，则某个时空事件实例为：

EventInstance={10541,(14:38:30,14:38:40),

{(264,75)},35}

Fig.2　Spatial and temporal event instances stream of Internet of vehicles图2　车联网时空事件实例流示意图

该时空事件实例表示的含义是该汽车在14点38分30秒至14点38分40秒时，在位置(264,75)处行驶的速度为35 km/h。

虽然车联网中的各个对象都在源源不断地产生着时空事件流，但是车联网中的事件用户一般只关注满足特定条件的事件实例。同时，不同的车联网用户往往关注不同的事件实例。

例如：交通管理员A想知道编号为“10541”的汽车在14点20分至14点50分之间车速超过80 km/h的事件实例。环境管理员B想知道编号为“10541”的汽车在18点30分至18点50分之间车速低于10 km/h的事件实例。

不同的用户关注不同的事件，因此用户需要用特定的“事件处理语句”表达其所关注的事件。在事件驱动体系结构中，支持“事件处理语句”的语言被称为事件处理语言或事件查询语言。这些“事件处理语句”通过“事件处理中间件”转化为相应的事件实例流处理程序，从而完成对事件实例流的处理。

Fig.3　Spatial and temporal event stream processing framework of Internet of vehicles图3　车联网时空事件实例流处理框架示意图

如图3所示，用户首先将自己关注的事件写为“事件处理语句”。该“事件处理语句”通过网络传输到车载计算机系统中。在车载计算机系统中，该“事件处理语句”被“事件流处理引擎”转化为“事件流处理规则”。汽车在行驶过程中所产生的“时空事件实例流”通过“事件流处理规则”的处理得到处理结果。这些“时空事件实例流”处理结果再通过网络传输到用户的“事件库”中。因此，用户可以得到自己想要的“事件”。

下面介绍本文提出的能够处理车联网时空事件实例流的事件处理语言STEP。

3　STEP语言的语法

面向车联网系统的时空事件处理语言STEP涉及以下语法集合。

（1）常量集合

事件处理表达式的值属于布尔值集合BOOLEAN={TRUE,FALSE}，其元素用B表示。车联网中事件实例的集合EventInstance={EI1,EI2,…,EIn}，其元素用EI表示。每个事件实例又包含若干属性，即EI=(ID,T,LOC,A)。其中，车联网中事件实例的对象标识集合EventInstanceID={ID1,ID2,…,IDn}，其元素用EIid表示。车联网中事件实例的时间属性集合Event-InstanceTIME={(start1,end1),(start2,end2),…,(startn,endn)}，其元素用EIt表示。时空事件的空间属性集合为EventInstanceLOCATION={(row1,column1),(row2,column2),…,(rown,columnn)}，其元素用EIloc表示。车联网系统中时空事件的其他数值型属性值记为Event-InstanceATTRIBUTE={ATTRIBUTE1,ATTRIBUTE2,…, ATTRIBUTEn}，其中元素记为EIa。

（2）变量集合

存放时空事件实例的变量记为x，其变量集合用X表示。变量x由时空事件的对象变量xid、时间变量xt、位置变量xloc、属性变量xa组成，并表示为x=(xid,xt, xloc,xa)。各分变量具体定义为：xid是存放时空事件实例的对象标识值的变量，该变量集合用Xid表示；xt是存放时空事件实例的时间属性值的变量，该变量集合用Xt表示；xloc是存放时空事件实例的空间属性值的变量，该变量集合用Xloc表示；xa是存放时空事件实例的其他数值型属性值的变量，该变量集合用Xa表示。

（3）表达式集合

STEP语言的事件处理语句构成的集合记为EPS（event processing sentence），其元素记为eps。事件处理语句是由表达式构成的，而表达式都为布尔型表达式。判断时空事件发生的对象标识值布尔表达式集合为IBEXP，其中元素记为ibexp。时间布尔表达式集合为TBEXP，其中元素记为tbexp。空间布尔表达式集合为LBEXP，其中元素记为lbexp。一般数值属性布尔表达式集合为ABEXP，其中元素记为abexp，其定义如下。

现假设已知常量集和变量集的语法结构。例如，变量通常为非空字母或后跟数字的非空字符串，那么STEP的语法如下。

①对象标识布尔表达式IBEXP

其中，“=”表示“等于”关系。

例如：表达式“CarId=10584”表示要判断当前某汽车标识符变量CarId的值是否等于10584。

其中“，BEFORE”“、EQUAL”“、OVERLAP”“、DURING”是4种时间数据的时序关系。

例如：表达式“CarTime BEFORE(20:18:20,20: 19:10)”表示要判断某汽车的数据中时间变量Car-Time的值是否早于时间段(20:18:20,20:19:10)。

②空间属性布尔表达式LBEXP

其中，“EQ”、“OP”、“IN”、“NORTH”、“EAST”、“NORTHWEST”、“NORTHEAST”是7种空间数据关系。

例如：表达式“CarLoc NORTH{(1 052,307)}”表示要判断某汽车的数据中空间属性变量CarLoc的值是否位于{(1 052,307)}的北方。

③一般数值属性布尔表达式ABEXP

其中，“=”表示“等于”关系，“>”表示“大于”关系，“<”表示“小于”关系。

例如：表达式“CarV>50”表示要判断某汽车的数据中车速变量CarV的值是否大于50 km/h。

④事件处理语句EPS

事件处理语句由前述4种表达式的一个或者多个通过3种算子“;”、“||”和“+”组合而成。算子“;”是顺序组合算子，算子“||”是并行组合算子，算子“+”是选择算子。

例如：事件处理语句“((CarV<100);(CarAcc> 30))”表示首先判断某汽车发送的数据中车速变量CarV的值是否小于100 km/h，然后再判断汽车加速度变量CarAcc的值是否大于30 m/s2。

再如，事件处理语句“(CarId=10584||CarTime DURING(19:18:20,19:19:10)||CarLoc NORTH{(1 052, 307)}||((CarV<100)+(CarAcc<2)))”表示要判断某汽车发送的数据中标识符变量CarId的值是否等于10584，且数据中时间变量CarTime的值是否在时间段(19:18:20,19:19:10)内，且数据中位置变量CarLoc的值是否在{(1 052,307)}的北方，且数据中车速变量的值是否小于100 km/h或者汽车加速度变量值是否小于30 m/s2。

4　STEP语言的操作语义

4.1STEP语言中各属性变量的设定

STEP语句中各表达式的值由当前存储时空事件实例的各属性变量的值决定。

车载计算机系统的时空事件状态定义为由车载计算机系统的时空事件实例变量集X到时空事件实例集EventInstance的函数σ:X→EventInstance，其可用下列子变量的状态表示。对象标识子变量状态σid定义为：时空事件实例对象标识值变量集Xid到时空事件实例对象标识值集EventInstanceID的函数σid:Xid→EventInstanceID。时间子变量状态σt定义为：时空事件实例时间属性值变量集Xt到时空事件实例时间属性值集EventInstanceTIME的函数σt:Xt→EventInstanceTIME。空间子变量状态σloc定义为：时空事件实例空间属性值变量集Xloc到时空事件实例空间属性值集EventInstanceLOCATION的函数 σloc: Xloc→EventInstanceLOCATION。数值子变量状态σa定义为：时空事件实例数值型属性值变量集Xa到时空事件实例数值型属性值集EventInstanceATTRIBUTE的函数σa：Xa→EventInstanceATTRIBUTE。

于是，σ(x)是状态σ下时空事件实例变量x的值EI。σid(xid)是状态σid下时空事件实例的对象标识符变量xid的值EIid。同理，σt(xt)是状态σt下时空事件实例的时间属性值变量xt的值EIt。σloc(xloc)是状态σloc下时空事件实例的空间属性值变量xloc的值EIloc。σa(xa)是状态σa下时空事件实例的数值属性值变量xa的值EIa。有时在不引起混淆的情况下，直接用σ(xid)表示σid(xid)（见第6章的例子）。

另外，经过STEP语句处理得到的时空事件实例被传到用户端的时空事件库中，设由用户端的时空事件库中的时空事件实例存储单元集（记为MB）到时空事件实例集（记为EventInstanceB）的函数σB:MB→EventInstanceB组成。

4.2STEP的操作语义

（1）对象标识布尔表达式IBEXP的赋值规则

上述规则是表达式“xid=ID”的赋值规则。设当前存储时空事件实例的变量名是x，其子变量xid存放着时空事件实例的标识符值。在第一条规则中，如果变量xid在当前状态σid下其值为常量ID，则表达式“xid=ID”的值为布尔值“TRUE”。在第二条赋值规则中，如果变量xid在当前状态σid下其值不是常量ID，则表达式“xid=ID”的值为布尔值“FALSE”。

（2）时间属性值布尔表达式TBEXP的赋值规则

这两条规则是表达式“xtBEFORE T”的赋值规则。设当前存储时空事件实例的变量名是x，其子变量xt存放着时空事件实例的时间属性值。在第一条规则中，如果变量xt在当前状态σt下的值与时间常量T的值满足“BEFORE”关系（即σ(xt).end

其余的时间属性值布尔表达式的赋值规则与上述推理规则类似，不再详述。

（3）空间属性值布尔表达式LBEXP的赋值规则

这两条规则是表达式“xlocEQ LOC”的赋值规则。设当前存储时空事件实例的变量名是x，其子变量xloc存放着时空事件实例的空间属性值。在第一条规则中，如果变量xloc在当前状态σloc下的值与空间常量LOC的值满足“EQ”关系（即σ(xloc)=LOC），则表达式“xlocEQ LOC”的值为布尔值“TRUE”。在第二条赋值规则中，如果变量xloc在当前状态σloc下的值与空间常量LOC的值不满足“EQ”关系（即σ(xloc)≠LOC），则表达式“xlocEQ LOC”的值为布尔值“FALSE”。

其余的空间属性值布尔表达式的赋值规则与上述推理规则类似，不再详述。

（4）一般数值属性布尔表达式ABEXP的赋值规则

这两条规则是表达式“xa>A”的赋值规则。设当前存储时空事件实例的变量名是x，其子变量xa存放着时空事件实例的某数值型属性值。在第一条规则中，如果变量xa在当前状态σa下的值大于数值型常量A的值（即σ(xa)>A），则表达式“xa>A”的值为布尔值“TRUE”。在第二条赋值规则中，如果变量xa在当前状态σa下的值小于或者等于数值型常量A的值，则表达式“xa>A”的值为布尔值“FALSE”。

其余的数值型属性值布尔表达式的赋值规则与上述赋值规则类似，不再详述。

4.3事件处理语句EPS的操作语义

这4条推理规则是4种原子事件处理语句的操作语义。设当前存储时空事件实例的变量名是x，以“ibexp”语句为例进行说明：当该原子事件处理语句“ibexp”在当前状态σid下的值为布尔值“TRUE”时，则变量x中存储的时空事件实例值被发送到用户端的事件库中（即ΣB⋃{σ}），同时变量x存储单元被清空并准备接收下一个时空事件实例。其他原子事件处理语句类似，不再详述。

这条推理规则是顺序复合事件处理语句“eps1;eps2”的操作语义。首先计算语句“eps1”的值，如果语句“eps1”在当前状态σ下的运算结果为ΣB⋃{σ}，那么就继续计算语句“eps2”的值。

这两条推理规则是选择复合事件处理语句“eps1+eps2”的操作语义。同时计算语句“eps1”和“eps2”的值，如果语句“eps1”和“eps2”在当前状态σ下的运算结果之一为ΣB⋃{σ}，那么选择复合事件处理语句“eps1+eps2”的运算结果就是ΣB⋃{σ}。

以上从形式语义学角度形式化地描述了车联网时空事件处理语言STEP的操作语义，下面从实现角度给出相应的时空事件流处理算法。

5　基于Petri网的STEP时空事件流处理算法

在基于STEP语言的车联网时空事件流处理机制中，需要将STEP语句经编译器转化为相应的处理模型，然后根据处理模型设计相应的时空事件流处理算法并最终编程实现。

在基于Petri网的事件流处理模型中，用Petri网输入位置的库所表示已经发生的事件（或基本事件的某一属性数据），输出位置的库所表示需检测的事件（或数据）。库所内的token表示所代表的事件（或数据）是否有实例产生。当一个事件（或数据）的实例到来时，代表该事件的库所内token状态将被改变。通过计算变迁函数来判断是否满足变迁条件。若满足，则引发变迁并改变输入和输出库所的状态，直到要检测的输出位置库所内的token状态被改变，此时表示要检测的事件发生。针对STEP语言的各种语句，分别建立其对应的Petri网处理模型如下。

（1）“基本结构”Petri网模型如图4所示。

Fig.4　Petri net model of basic structure图4　“基本结构”Petri网模型

图4（a）表示有一个事件的属性数据到达输入库所p1，这时判断该事件的属性数据是否满足guard条件。当该事件的属性数据不满足guard条件时，事件被删除，下一个事件的属性数据进入输入库所p1位置。当某个事件的属性数据满足guard条件时，则输入库所p1与输出库所p2之间发生跃迁。输入库所p1中的token消失，输出库所p2中产生token，如图4（b）所示。

处理模型为“基本结构”Petri网模型的STEP表达式有：ibexp、tbexp、lbexp和abexp。

（2）“顺序结构”Petri网模型如图5所示。

Fig.5　Petri net model of sequential structure图5　“顺序结构”Petri网模型

图5（a）表示有一个事件的属性数据到达输入库所p1，这时判断该事件的属性数据是否满足guard1条件。当该事件的属性数据不满足guard1条件时，事件被删除，下一个事件的属性数据进入输入库所p1位置。当这个事件的属性数据满足guard1条件时，则输入库所p1与输出库所p2之间发生跃迁。输入库所p1中的token消失，输出库所p2中产生token，如图5（b）所示。然后，继续判断这个事件的属性数据是否满足guard2条件。当这个事件的属性数据满足guard2条件时，则输入库所p2与输出库所p3之间发生跃迁。输入库所p2中的token消失，输出库所p3中产生token，如图5（c）所示。

处理模型为“顺序结构”Petri网模型的STEP语句为：eps1;eps2。

（3）“并行结构”Petri网模型如图6所示。

Fig.6　Petri net model of parallel structure图6　“并行结构”Petri网模型

图6（a）表示一个事件的两个属性数据分别到达两个输入库所p1和p2，这时判断二者是否分别满足guard1条件和guard2条件。当该事件的某属性数据满足guard1条件时，则输入库所p1与输出库所p3之间发生跃迁。输入库所p1中的token消失，输出库所p3中产生token。同理，当该事件的某属性数据满足guard2条件时，则输入库所p2与输出库所p4之间发生跃迁。输入库所p2中的token消失，输出库所p4中产生token。只有当p3和p4库所中都有token时（如图6（b）所示），p5库所前才会发生跃迁。输入库所p3和p4中的token消失，输出库所p5中产生token，如图6（c）所示。当该事件的属性数据分别不满足guard1条件或guard2条件时，事件被删除，下一个事件的属性数据进入输入库所p1和p2。

处理模型为“并行结构”Petri网模型的STEP语句为：。

（4）“选择结构”Petri网模型如图7所示。

Fig.7　Petri net model of choice structure图7　“选择结构”Petri网模型

图7（a）表示一个事件的两个属性数据分别到达两个输入库所p1和p2，这时判断二者是否分别满足guard1条件和guard2条件。当该事件的某属性数据满足guard1条件时，则输入库所p1与输出库所p3之间发生跃迁。输入库所p1中的token消失，输出库所p3中产生token。同理，当该事件的某属性数据满足guard2条件时，则输入库所p2与输出库所p4之间发生跃迁。输入库所p2中的token消失，输出库所p4中产生token。只要p3和p4库所之一有token时（假设p3库所有token，如图7（b）所示），guard3条件所代表的跃迁就会发生。输入库所p3中的token消失，输出库所p5中产生token，如图7（c）所示。当该事件的属性数据不满足guard1条件也不满足guard2条件时，事件被删除，下一个事件的属性数据进入输入库所p1和p2。

处理模型为“选择结构”Petri网模型的STEP语句为：eps1+eps2。

根据上述Petri网处理模型，可得到如下时空事件流处理算法。

算法1基于Petri网模型的事件流处理算法

输入：时空事件流，STEP语句的Petri网模型。

输出：满足STEP语句条件的事件实例。

1.While TRUE do

2.Event←当前指针指向的事件实例;

3.foreach Event.Attribute do

4.TransitionStart.Input←Event.Attribute;

5.end

6.foreach TransitionStart do

7.if InputToken满足Guard then

8.OutputToken←InputToken;

9.end

10.foreach TransitionMid do

11.if InputToken满足Guard then

12.OutputToken←OutputToken+InputToken;

13.end

14.foreach TransitionEnd do

15.if InputToken满足Guard then

16.OutputToken←OutputToken+InputToken

且return OutputToken;

17.end

18.清空Event值，事件指针++;

19.end

在该算法中，输入的Petri网模型中的所有跃迁被分为3类，分别是“开始跃迁”（TransitionStart）、“中间跃迁”（TransitionMid）和“终结跃迁”（Transition-End）。其中，“开始跃迁”的功能是检测接收到的事件实例的属性值。“开始跃迁”通过共享库所的方法和与其连接的“中间跃迁”传递信息，“开始跃迁”的输出库所和“中间跃迁”的输入库所共享同一变量。“终结跃迁”是一种特殊的“中间跃迁”，该中间跃迁没有后继跃迁。在所有的跃迁中，Guard根据上一节中的操作语义进行判断。

在本算法中，从“开始跃迁”开始执行，沿着Petri网结构向“终结跃迁”逐步执行。因为Petri网中“开始跃迁”到“终结跃迁”之间的跃迁数是有限的，所以，对于单个事件实例，该算法是可终止的。另设本算法中Petri网模型的跃迁数为n，则对于单个事件实例该算法的时间复杂度为O(n)。

6　实验结果与分析

为了检验基于STEP语言的车联网时空事件流处理机制的有效性，下面分别从理论推导和仿真实验两个方面对实例进行验证，并对实验结果进行分析和比较。

6.1实验设计

设车联网环境中，一辆标识符为“10584”的汽车在行驶过程中每隔10 s产生一个时空事件实例。其中，设时空事件变量为“Car”，汽车标识符子变量为“CarID”，事件实例的时间属性值子变量为“Car-Time”，事件实例的空间属性值子变量为“CarLoc”，事件实例的速度值子变量为“CarV”（即Car=(CarID, CarTime,CarLoc,CarV)）。时空事件实例流中的时空事件实例记为“EI”。设该汽车产生的时空事件实例流中，某连续的5个时空事件实例如表3所示。

Table 3　Value of a spatial and temporal event stream表3　某时空事件实例流的值

在车联网系统中，设有4个用户（User1、User2、User3和User4）分别对该车进行监控。由于这些用户关注的事件不同，他们分别用下面4个STEP语句对该汽车所产生的时空事件流进行处理（STEP语句记为EventStence）。其中，设两个空间数据集合分别为ROAD47={(1 052,50),(1 052,51),…,(1 052,200)}和ROAD35={(97,150),(97,151),…,(97,200)}。

User1的STEP语句为:

EventStence1:CarID=10584||CarTimeDURING (19:10:00,19:15:00)||CarLoc IN ROAD47||CarV>90

User2的STEP语句为:

EventStence2:CarID=10584||CarTimeDURING (19:30:00,20:00:00)||CarLoc IN ROAD47||CarV<100

User3的STEP语句为:

EventStence3:CarID=10584||CarTimeDURING (19:10:00,19:15:00)||CarLoc IN ROAD35||CarV<100

User4的STEP语句为:

EventStence4:CarID=10584||CarTimeDURING (19:10:00,19:15:00)||CarLoc IN ROAD47||CarV<100

6.2理论推导过程与结果

根据STEP语言的操作语义，可以推导出上述4 条STEP语句对表3中的5个时空事件实例的处理结果。下面选取两个例子说明推导过程。

例1 User2的事件处理语句EventStence2对时空事件实例EI4的处理过程如下。

已知当前时空事件实例为EI4，设当前车载计算机系统中，时空事件变量的状态为σ2。用户User2客户端的事件库的状态为ΣB2。当前车载计算机系统中，在σ2状态下各子变量的值分别为：CarID为“10584”，CarTime为“(19:10:50,19:11:00)”，CarLoc为“{(1052,103)}”，CarV为“93.8”，则有如下推理过程：

从上述推导过程中可以看出，时空事件实例EI4的时间属性值不满足事件处理语句EventStence2中的时间表达式，因此EventStence2的计算结果为当前车载计算机系统中，时空事件变量各属性子变量CarID、CarTime、CarLoc和CarV的值被清空。用户User2客户端的事件库保持原有的状态ΣB2不变。

例2 User4的事件处理语句EventStence4对时空事件实例EI4的处理过程如下。

已知当前时空事件实例为EI4，设当前车载计算机系统中，各存储变量的状态为σ4。用户User4客户端的事件库的状态为ΣB4。当前车载计算机系统中，在 σ4状态下各子变量的值分别为：CarID为“10584”，CarTime为“(19:10:50,19:11:00)”，CarLoc为“{(1 052,103)}”，CarV为“93.8”，则有如下推理过程：

从推导过程中可以看出，时空事件实例EI4的各属性值都满足事件处理语句EventStence4，因此EventStence4的计算结果为当前车载计算机系统中，各存储变量CarID、CarTime、CarLoc和CarV的值（即时空事件实例EI4）被发送到用户User4客户端的事件库，则该事件库的状态由ΣB4变为ΣB4⋃{σ4}。最后，当前车载计算机系统中各存储变量CarID、CarTime、CarLoc和CarV的值被清空，准备接收下一个时空事件实例。

根据相应的操作语义，其他STEP语句对表3中的5个时空事件实例的推理过程类似。设4个用户的事件库的初始状态分别为ΣB1、ΣB2、ΣB3和ΣB4，则表3中的时空事件实例流的理论推导结果如表4所示。

Table 4　Reasoning results of example表4　实例的理论推导结果

从上述理论推导过程和推导结果可以看出，STEP语言的操作语义是有效的。

6.3仿真实验结果与分析

根据STEP语言的操作语义和第4章的基于Petri网的时空事件流处理算法1构造仿真程序进行实验。首先，STEP语言的编译器由开源工具ANTLRWorks1.5实现（ANTLR提供强大的语言分析功能，能够实现词法和语法解析器的自动生成）。

基于ANTLRWorks工具实现的STEP语言的语法如图8所示。

Fig.8　Syntax of STEP language based on ANTLRWorks tool图8　基于ANTLRWorks工具实现的STEP语言的语法

其次，基于STEP语言的词法和语法解析器以及算法1，采用Java语言实现了基于STEP语言的车联网时空事件流处理仿真程序。仿真程序运行过程及结果如图9所示。

Fig.9　Result of simulation program图9　仿真程序的运行过程及结果

仿真实验过程中，首先在事件编辑器界面中输入STEP语句，并且给每个STEP语句设置唯一的编号；然后激活该语句，则在事件查询结果列表中会显示出该STEP语句所代表的事件发生的次数；用户可以选中该事件的编号，从而在事件查询结果详情中看到该事件的详细清单。

设4个用户的事件库的初始状态都为空集，则表3中时空事件实例流的仿真实验结果如表5所示。

从表5中可以看出，第4章基于Petri网时空事件流处理算法1是有效的。另外，通过比较表4和表5的结果，可以看出根据STEP语言的操作语义的理论推导结果与根据算法1构造的仿真程序的实验结果是一致的，且可以相互印证，从而说明本文提出的基于STEP语言的车联网时空事件流处理机制是有效的。

Table 5　Simulation results of example表5　实例的仿真实验结果

7　总结和展望

本文针对车联网环境中移动体所产生的带有时空特性的数据流处理问题，采用事件驱动体系结构将这些时空数据流抽象为时空事件实例流进行处理。首先，提出了与车联网相适应的时间数据模型（简化的Allen时间数据模型）和空间数据模型（与地理信息系统兼容的栅格空间数据模型），从而建立了时空事件实例模型。其次，基于上述模型提出了一种新的时空事件处理语言STEP。在该语言中，基于上述时空事件实例的时空关系给出了相应的时空运算符和语法，并给出了相应的操作语义。然后，基于STEP语言给出了基于Petri网的车联网时空事件流处理算法。最后，通过实验说明了基于STEP语言的车联网时空事件流处理机制的有效性。

需要指出的是，本文在设计基于STEP语言的车联网时空事件流处理机制时尚未考虑车联网事件流的信息安全保护问题和事件流的可靠传输问题，这些问题需要进一步研究。另外，本文事件流的处理过程采用的是集中式处理方法，但随着车联网事件流规模的不断增加，如何在车联网环境中进行分布式事件流处理也是需要进一步研究的。

[1]Gerla M,Lee E K,Pau G.Internet of vehicles:from intelligent grid to autonomous cars and vehicular clouds[C]//Proceedings of the 2014 IEEE World Forum on Internet of Things,Seoul,Korea,Mar 6-8,2014.Piscataway,USA: IEEE,2014:241-246.

[2]Wu Jianjia,Zhao Wei.WInternet:from net of things to Internet of things[J].Journal of Computer Research and Development,2013,50(6):1127-1134.

[3]Chen Haiming,Cui Li,Xie Kaibin,et al.A comparative study on architectures and implementation methodologies of Internet of things[J].Chinese Journal of Computers,2013,36 (1):168-188.

[4]Xie Kaibin,Chen Haiming,Cui Li,et al.PMDA:a physical model driven software architecture for Internet of things[J]. Journal of Computer Research and Development,2013,50 (6):1185-1197.

[5]Schwiderski-Grosche S,Moody K.The SpaTeC composite event language for spatio-temporal reasoning in mobile systems[C]//Proceedings of the 3rd ACM International Conference on Distributed Event-Based Systems,Nashville,USA, Jul 6-9,2009.New York,USA:ACM,2009:11-18.

[6]Moody K,Bacon J,Evans D.Implementing a practical spatiotemporal composite event language[M]//LNCS 6462:From Active Data Management to Event-Based Systems and More.Berlin,Heidelberg:Springer,2010:108-123.

[7]Jin Beihong,Zhuo Wei,Hu Jiafeng,et al.Specifying and detecting spatio-temporal events in the Internet of things[J]. Decision Support Systems,2013,55(1):256-269.

[8]Cao Kening,Wang Yongheng,Li Renfa,et al.A distributed context-aware complex event processing method for Internet of things[J].Journal of Computer Research and Development,2013,50(6):1163-1176.

[9]Meng You,Luan Zhongzhi,Xie Ming,et al.Operator-based extendable complex event processing model[J].Journal of Software,2014,25(11):2715-2730.

[10]Eckert M.Complex event processing with XChange EQ: language design,formal semantics,and incremental evaluation for querying events[M].LMU München:Faculty of Mathematics,2008.

[11]Anicic D,Rudolph S,Fodor P,et al.Stream reasoning and complex event processing in ETALIS[J].Semantic Web, 2012,3(4):397-407.

[12]Wang Fusheng,Liu Shaorong,Liu Peiya,et al.Bridging physical and virtual worlds:complex event processing for RFID data streams[C]//LNCS 3896:Proceedings of the 10th International Conference on Extending Database Technology,Munich,Germany,Mar 26-31,2006.Berlin,Heidelberg:Springer,2006:588-607.

[13]Pietzuch P R,Shand B,Bacon J.A framework for event composition in distributed systems[C]//Proceedings of the 2003 ACM/IFIP/USENIX International Conference on Middleware,Rio de Janeiro,Brazil,Jun 16-20,2003.New York,USA:Springer-Verlag,2003:62-82.

[14]Chen Xiaoyan,Chen Ying,Rao Fangyan.An efficient spatial publish/subscribe system for intelligent location-based services[C]//Proceedings of the 2nd Iternational Workshop on Distributed Event-Based Systems,San Diego,USA,Jun8,2003.New York,USA:ACM,2003:1-6.

[15]Bamba B,Liu Ling,Yu P S.Scalable processing of spatial alarms[C]//Proceedings of the 15th International Conference on High Performance Computing,Bangalore,India, Dec 17-20,2008.Berlin,Heidelberg:Springer,2008:232-244.

[16]Allen J F.Maintaining knowledge about temporal intervals[J]. Communications of theACM,1983,26(11):832-843.

[17]Hu Wenhui,Ye Wei,Huang Yu,et al.Complex event processing in RFID middleware:a three layer perspective[C]// Proceedings of the 3rd International Conference on Convergence and Hybrid Information Technology,Busan,Korea, Nov 11-13,2008.Piscataway,USA:IEEE,2008:1121-1125.

附中文参考文献：

[2]武建佳,赵伟.WInternet:从物网到物联网[J].计算机研究与发展,2013,50(6):1127-1134.

[3]陈海明,崔莉,谢开斌,等.物联网体系结构与实现方法的比较研究[J].计算机学报,2013,36(1):168-188.

[4]谢开斌,陈海明,崔莉,等.PMDA:一种物理模型驱动的物联网软件体系结构[J].计算机研究与发展,2013,50 (6):1185-1197.

[8]曹科宁,王永恒,李仁发,等.面向物联网的分布式上下文敏感复杂事件处理方法[J].计算机研究与发展,2013,50 (6):1163-1176.

[9]孟由,栾钟治,谢明,等.一种基于算子的可扩展复杂事件处理模型[J].软件学报,2014,25(11):2715-2730.

LI Huiyong was born in 1980.He is a Ph.D.candidate at Software Engineering Institute,East China Normal University.His research interests include Internet of things and mobile computing.

李慧勇（1980—），男，山西太原人，华东师范大学软件学院博士研究生，主要研究领域为物联网理论与技术，移动计算。

CHEN Yixiang was born in 1961.He is a Ph.D.supervisor at MoE Engineering Research Center for Software/ Hardware Co-design Technology andApplication,East China Normal University.His research interests include formal methods of software,Internet of things and trust computing.

陈仪香（1961—），男，江苏徐州人，华东师范大学教育部软硬件协同设计技术与应用工程研究中心博士生导师，主要研究领域为形式化理论，物联网理论，可信计算理论。

STEP:ASpatial-Temporal Event Processing Language for Internet of Vehicles*

LI Huiyong,CHEN Yixiang+
MoE Engineering Research Center for Software/Hardware Co-design Technology and Application,East China Normal University,Shanghai 200062,China +Corresponding author:E-mail:yxchen@sei.ecnu.edu.cn

The Internet of vehicles(IoV)is an important research area of the intelligent transportation systems using Internet of things theory.The complex event processing technology is a basic issue for processing the data stream in IoV,in which the spatial and temporal information is the character of the data stream of IoV,which is different from the classical ones in Internet of things.It is one of the core issues of the complex event processing technology in IoV, how to effectively represent and process these temporal and spatial information of the data stream.To solve this problem,this paper proposes a novel spatial-temporal complex event processing language(STEP)for the IoV.In STEP, time intervals are used to denote the temporal model and grid map is used to denote the spatial models.This paper firstly establishes the syntax of STEP based on the modified spatial-temporal relation operators,which can effectively express the spatial and temporal relationships of event instance stream of IoV.Then this paper defines the operational semantics of STEP language,and also designs the event instance stream processing algorithm based on the Petri net model.Finally,this paper uses some examples to demonstrate the effectiveness of the event stream processing mecha-

2015-07,Accepted 2015-09.

Internet of things;Internet of vehicles;complex event processing;event processing language;formal semantics;spatial-temporal event stream

10.3778/j.issn.1673-9418.1508048

A

TP391

*The National Natural Science Foundation of China under Grant No.61370100(国家自然科学基金);the National Basic Research Program of China under Grant No.2011CB302802(国家重点基础研究发展计划(973计划));the Shanghai Knowledge Service Platform Project under Grant No.ZF1213(上海知识服务平台计划);the Project of Shanghai Municipal Science and Technology Commission under Grant No.14511100400(上海市科委项目).

CNKI网络优先出版:2015-09-25,http://www.cnki.net/kcms/detail/11.5602.TP.20150925.1653.002.htmlnism based on STEP language.