面向車聯網的時空事件處理語言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.