李慧勇，陳儀香

華東師范大學 教育部軟硬件協(xié)同設計技術與應用工程研究中心，上海 200062

面向車聯(lián)網(wǎng)的時空事件處理語言STEP*

李慧勇，陳儀香+

華東師范大學 教育部軟硬件協(xié)同設計技術與應用工程研究中心，上海 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.

車聯(lián)網(wǎng)是物聯(lián)網(wǎng)技術應用于智能交通領域所形成的重要研究領域。復雜事件處理技術是車聯(lián)網(wǎng)系統(tǒng)數(shù)據(jù)流處理的重要方法。有別于經(jīng)典的物聯(lián)網(wǎng)系統(tǒng)，車聯(lián)網(wǎng)中數(shù)據(jù)流包含大量的時間和空間信息。在復雜事件處理技術中，如何有效地表達和處理車聯(lián)網(wǎng)的時空數(shù)據(jù)流成為亟待解決的問題。針對該問題，提出了一種時空事件處理語言（spatial-temporal event processing language，STEP）。STEP分別采用時間段和柵格地圖作為時間和空間模型?；谠摃r空模型，首先給出STEP語言的相關時空算子和完整語法，從而有效地表達車聯(lián)網(wǎng)中時空事件流的時空信息。然后，分別從形式語義學角度引入STEP語言的操作語義，并且從實現(xiàn)角度給出了基于Petri網(wǎng)模型的時空事件流處理算法，從而建立車聯(lián)網(wǎng)時空事件流處理機制。最后，通過實驗說明了基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制的有效性。

物聯(lián)網(wǎng)；車聯(lián)網(wǎng)；復雜事件處理；事件處理語言；形式語義；時空事件流

1　引言

車聯(lián)網(wǎng)系統(tǒng)（Internet of vehicles，IoV）是物聯(lián)網(wǎng)理論在智能交通領域的重要應用[1-2]。隨著時鐘技術、定位技術以及各種傳感設備在車聯(lián)網(wǎng)系統(tǒng)中的大規(guī)模應用，用戶可以非常方便地得到系統(tǒng)中移動體的時間、位置、方向、速度等數(shù)據(jù)。但是，車聯(lián)網(wǎng)中移動體在移動過程中會產(chǎn)生大量的數(shù)據(jù)流，為了有效處理這些數(shù)據(jù)流，很多學者提出了多種車聯(lián)網(wǎng)信息處理體系結構[3-4]。其中，一些學者將事件驅動體系結構（或復雜事件處理技術）應用到車聯(lián)網(wǎng)系統(tǒng)的數(shù)據(jù)流處理中，取得了良好的效果[5-7]。

復雜事件處理技術是通過事件處理語言，將系統(tǒng)產(chǎn)生的海量數(shù)據(jù)流過濾為用戶所關注的事件實例流。當系統(tǒng)中有用戶關心的事件實例發(fā)生時，該事件實例被發(fā)送到用戶端的事件庫或者根據(jù)用戶預先定義好的處理規(guī)則，實時地或者接近實時地做出相應的處理。復雜事件處理技術已經(jīng)成功地應用于物聯(lián)網(wǎng)系統(tǒng)中[8-9]。在面向物聯(lián)網(wǎng)的復雜事件處理語言中，采用恰當?shù)臅r空模型是非常重要的。

在早期的事件處理語言中，主要關注事件之間的時序關系。Xchange[10]是一種基于條件事件代數(shù)（condition event algebra，CEA）的復雜事件處理語言。該語言屬于類結構化查詢語言（structured query language，SQL），其引入了時間事件以支持含有時間的事件間的運算。ETALIS[11]是一種基于規(guī)則的復雜事件處理語言，該語言關于時間的算子有during、starts、equals、finishes、meet等。RCEDA[12]可以描述一系列順序發(fā)生的事件和在一系列時間段發(fā)生的事件。CE language[13]可以表達選擇、連續(xù)、并行和重復等事件的組合。

近來，也有一些事件處理語言主要關注事件之間的空間關系。文獻[14]設計和實現(xiàn)了一種基于位置的智能服務，其中包含兩個空間關系謂語：Within 和Distance。文獻[15]討論了空間警報的相關問題。例如，用戶首先描述一定的空間范圍，如果有物體運動到該區(qū)域，則敲響警報。

車聯(lián)網(wǎng)系統(tǒng)中的事件同時具有時間和空間特性，因此車聯(lián)網(wǎng)中的事件處理語言應該包含時空算子。文獻[5]提出了一種SpaTec復雜事件處理語言，可以描述監(jiān)視內(nèi)容的時空屬性。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語言應用于倫敦市的公交車監(jiān)控系統(tǒng)。文獻[7]提出了一種事件處理語言CPSL，這種語言可以描述車聯(lián)網(wǎng)中事件的多種時間和空間關系。這兩種語言都采用簡化的Allen時間模型[16]為時間數(shù)據(jù)模型。

SpaTec語言采用以坐標點為中心的圓形區(qū)域為其空間數(shù)據(jù)模型[5-6]。CPSL語言采用點集和凸多邊形的空間數(shù)據(jù)模型[7]。這兩種語言的空間數(shù)據(jù)模型存在如下兩個問題：第一，與地理信息系統(tǒng)的空間模型不兼容。車聯(lián)網(wǎng)系統(tǒng)中各對象可以與地理信息系統(tǒng)共享空間信息并獲得全局地圖，因此應該采用與地理信息系統(tǒng)兼容的空間模型。第二，沒有考慮空間數(shù)據(jù)的方向關系。

本文提出了一種針對車聯(lián)網(wǎng)系統(tǒng)的時空事件處理語言（spatial-temporal event processing，STEP），建立該語言的語法和操作語義。與上述語言相比，主要強調(diào)以下兩點改進：

（1）采用地理信息系統(tǒng)中柵格地圖模型作為車聯(lián)網(wǎng)系統(tǒng)的空間模型。

（2）基于柵格地圖空間模型，給出了車聯(lián)網(wǎng)空間數(shù)據(jù)方向關系的判斷方法。

另外，事件實例流的處理需要將事件處理語句轉化為相應的事件流處理模型并最終編程實現(xiàn)。目前已有的事件流處理模型有：基于樹的事件流處理模型、基于圖的事件流處理模型、基于Petri網(wǎng)的事件流處理模型、基于自動機的事件流處理模型。因為Petri網(wǎng)模型[17]可用于模擬帶有并發(fā)性、異步性、分布式、非確定性、并行性等特性的系統(tǒng)，所以在車聯(lián)網(wǎng)系統(tǒng)中采用基于Petri網(wǎng)的事件流處理模型。

本文內(nèi)容組織如下：第2章介紹車聯(lián)網(wǎng)系統(tǒng)的時空數(shù)據(jù)模型、時空事件實例模型和車聯(lián)網(wǎng)時空事件實例流處理框架；第3章設計STEP語言的語法；第4章建立STEP語言的操作語義；第5章設計基于Petri網(wǎng)處理模型的車聯(lián)網(wǎng)時空事件流處理算法；第6章通過實驗說明基于STEP語言的時空事件流處理機制的有效性；最后是本文的工作總結以及進一步的工作方向。

2　車聯(lián)網(wǎng)的數(shù)據(jù)模型及時空事件實例模型

在車聯(lián)網(wǎng)系統(tǒng)中，各類傳感設備連續(xù)不斷地產(chǎn)生著大量的多源、多維數(shù)據(jù)。這些數(shù)據(jù)包括時間、位置、方向、速度、加速度、溫度、車牌號、交通信號等，它們大部分可以用常見的數(shù)值模型表示，例如速度可以用實數(shù)表示。下面重點介紹車聯(lián)網(wǎng)中的時空數(shù)據(jù)模型和時空事件實例模型。

2.1車聯(lián)網(wǎng)系統(tǒng)的時間數(shù)據(jù)模型

在車聯(lián)網(wǎng)系統(tǒng)中，傳感器一般是周期性地識別物理狀態(tài)并產(chǎn)生相應數(shù)據(jù)。因此在車聯(lián)網(wǎng)系統(tǒng)中，無法獲得數(shù)據(jù)發(fā)生的具體時間點，而只能獲得事件發(fā)生的時間區(qū)間。本文用時間區(qū)間來定義車聯(lián)網(wǎng)的時間數(shù)據(jù)模型。

定義1車聯(lián)網(wǎng)中的時間數(shù)據(jù)模型是一個時間區(qū)間，其值為兩個時間點組成的序對，記為TIME=(start,end)。其中，start表示時間的起始點，而end表示時間的終止點。本文用24小時制來表示時間，并精確到秒。

例如：（20:14:10,20:14:35）表示車聯(lián)網(wǎng)中的一個時間區(qū)間數(shù)據(jù)。

時間區(qū)間數(shù)據(jù)之間的時序關系已經(jīng)有很多研究成果，比較經(jīng)典的有Allen定義的基于時間段的7種時序關系[16]。根據(jù)車聯(lián)網(wǎng)研究的實際需求，本文采用簡化的Allen時序關系模型，其關系如表1所示。

Table 1　Temporal relationships of STEP表1　STEP語言的時序關系

根據(jù)表1，時間數(shù)據(jù)之間的時序關系可以通過比較時間數(shù)據(jù)模型的起始時間點start和結束時間點end的關系得到。設有兩個時間數(shù)據(jù)分別為TIME1=(start1,end1)和TIME2=(start2,end2)，則車聯(lián)網(wǎng)時間數(shù)據(jù)的時序關系判斷條件分別為：

（1）TIME1BEFORE TIME2

判斷條件：end1

（2）TIME1EQUALTIME2

判斷條件：start1=start2且end1=end2。

（3）TIME1OVERLAPTIME2

判斷條件：start1

（4）TIME1DURING TIME2

判斷條件：start1≥start2且end1≤end2。

例如：時間數(shù)據(jù)（20:14:00,20:14:35）和時間數(shù)據(jù)（22:00:10,22:15:35），因為20:14:35小于22:00:10，所以二者的時序關系為BEFORE。

2.2車聯(lián)網(wǎng)系統(tǒng)的空間數(shù)據(jù)模型

本文車聯(lián)網(wǎng)的空間數(shù)據(jù)模型需要與地理信息系統(tǒng)（geographic information system，GIS）的空間數(shù)據(jù)模型保持兼容。在地理信息系統(tǒng)中，空間數(shù)據(jù)（或稱為地圖空間）可以用柵格空間數(shù)據(jù)模型表示。柵格空間數(shù)據(jù)模型是把空間看作一個處處連續(xù)的整體，并將空間劃分為大小均勻的規(guī)則網(wǎng)格陣列，每個網(wǎng)格為一個柵格，有唯一的行列號。行與列的數(shù)目取決于系統(tǒng)的分辨率及空間實體的特征。柵格數(shù)據(jù)模型中的基本單元是柵格。柵格空間數(shù)據(jù)模型中的點（point）、線（line）和區(qū)域（area）表示分別如圖1中的（a）、（b）和（c）的黑色部分。

Fig.1　Point,line and area of grid saptial data model圖1　柵格空間數(shù)據(jù)中的點、線和面

定義2車聯(lián)網(wǎng)的空間數(shù)據(jù)模型為柵格空間數(shù)據(jù)模型，其值為一組相鄰的柵格行列號序對集合，記為LOCATION={(row1,column1),(row2,column2),…,(rown, columnn)}。

例如：圖1（a）中的點空間數(shù)據(jù)可以記為{(3,3)}，圖1（b）中的線空間數(shù)據(jù)可以記為{(3,3),(3,4),(3,5),(3, 6),(4,6),(5,6),(6,6),(6,7),(6,8)}。

車聯(lián)網(wǎng)中空間數(shù)據(jù)模型的方向關系是非常重要的。例如：如果要監(jiān)控一輛行駛中的汽車是否超車，則需要判斷兩輛汽車的方向關系。下面給出車聯(lián)網(wǎng)中空間數(shù)據(jù)模型的方向關系的定義。

定義3基于柵格空間數(shù)據(jù)模型，定義7種空間方向關系，分別為NORTH（在北方），EAST（在東方），NORTHEAST（在東北方），NORTHWEST（在西北方），EQ（空間相等），OP（空間相交），IN（在空間內(nèi)）。

在上述定義中，NORTH、EAST、NORTHEAST、NORTHWEST這4種關系主要描述兩個相離（空間數(shù)據(jù)集合的交集為空）空間數(shù)據(jù)之間的方向關系。由于空間位置的對稱性，“a在b的南方”可以等價表示為“b在a的北方”，上述4種空間關系可以完整描述8種空間數(shù)據(jù)之間的不相交位置關系。EQ、OP和IN 這3種空間位置關系主要描述兩個有交集的空間數(shù)據(jù)之間的關系，其中EQ關系描述兩個相等的空間數(shù)據(jù)，IN關系描述一個空間數(shù)據(jù)是另一個空間數(shù)據(jù)的子集，OP關系描述非EQ和非IN關系的空間數(shù)據(jù)有交集的方向關系。

該定義中的空間方向關系如表2所示。

根據(jù)表2，空間數(shù)據(jù)之間的方向關系可以通過比較空間數(shù)據(jù)模型的柵格集合關系得到。設有兩個空間數(shù)據(jù)分別為LOCATIONa={(rowa1,columna1), (rowa2,columna2),…,(rowan,columnan)}和LOCATIONb={(rowb1,columnb1),(rowb2,columnb2),…,(rowbn,columnbn)}。設rowa和columna分別表示空間數(shù)據(jù)的行值序列和列值序列(即rowa={rowa1,rowa2,…,rowan}，columna={columna1,columna2,…,columnan})，min()和max()兩個函數(shù)分別為求最小值和最大值運算，則min(rowa) 和max(rowa)分別表示求空間數(shù)據(jù)LOCATIONa中行值的最小值和最大值。min(columnb)和max(columnb)類似地表示LOCATIONb中列值的最小值和最大值。基于上述假設，車聯(lián)網(wǎng)空間數(shù)據(jù)間的方向關系判斷

條件分別為：

（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。

例如：判斷兩個空間數(shù)據(jù)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車聯(lián)網(wǎng)系統(tǒng)的時空事件實例模型

在事件驅動體系結構的車聯(lián)網(wǎng)系統(tǒng)中，所有的數(shù)據(jù)都被抽象成事件實例。因為車聯(lián)網(wǎng)系統(tǒng)的數(shù)據(jù)都具有時空特性，所以車聯(lián)網(wǎng)系統(tǒng)的事件實例也同時具有時空特性。設車聯(lián)網(wǎng)系統(tǒng)中要關注的對象（例如行駛中的汽車、交通信號燈、交通限速牌等）的各種狀態(tài)屬性值（例如速度、時間、位置、方向、狀態(tài)值等）可以由各種類型傳感設備感測得到，則某個具體對象某次得到的數(shù)據(jù)集合就是該對象的一個時空事件實例（spatial-temporal event instance）。

定義4車聯(lián)網(wǎng)系統(tǒng)時空事件實例是由車聯(lián)網(wǎng)中對象的各種感測數(shù)據(jù)組成的序列：EventInstance={ID,TIME,LOCATION,ATTRIBUTE}。其中，ID為車聯(lián)網(wǎng)系統(tǒng)中約定對象的唯一標識值，其值可以是IP地址、二維碼、RFID標簽等。TIME為時間屬性值，該值采用定義1中的時間數(shù)據(jù)模型。LOCATION為空間屬性值，該值采用定義2中的空間數(shù)據(jù)模型。ATTRIBUTE={Attribute1,Attribute2,…,Attributen}，Attribute1,Attribute2,…,Attributen分別為其他各類數(shù)值型屬性值，其主要包括速度、加速度、溫度、濕度等。

該定義強調(diào)車聯(lián)網(wǎng)中的事件實例必須具有時空特性，因此事件實例中的時間屬性值和空間屬性值不可或缺。車聯(lián)網(wǎng)中各類傳感器不斷地產(chǎn)生數(shù)據(jù)，因此這些基本時空事件實例序列就構成了時空事件實例流，如圖2所示。

例如：車聯(lián)網(wǎng)中，一輛ID為“10541”的汽車每隔10 s向外發(fā)布一次其行駛速度值，則某個時空事件實例為：

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

{(264,75)},35}

Fig.2　Spatial and temporal event instances stream of Internet of vehicles圖2　車聯(lián)網(wǎng)時空事件實例流示意圖

該時空事件實例表示的含義是該汽車在14點38分30秒至14點38分40秒時，在位置(264,75)處行駛的速度為35 km/h。

雖然車聯(lián)網(wǎng)中的各個對象都在源源不斷地產(chǎn)生著時空事件流，但是車聯(lián)網(wǎng)中的事件用戶一般只關注滿足特定條件的事件實例。同時，不同的車聯(lián)網(wǎng)用戶往往關注不同的事件實例。

例如：交通管理員A想知道編號為“10541”的汽車在14點20分至14點50分之間車速超過80 km/h的事件實例。環(huán)境管理員B想知道編號為“10541”的汽車在18點30分至18點50分之間車速低于10 km/h的事件實例。

不同的用戶關注不同的事件，因此用戶需要用特定的“事件處理語句”表達其所關注的事件。在事件驅動體系結構中，支持“事件處理語句”的語言被稱為事件處理語言或事件查詢語言。這些“事件處理語句”通過“事件處理中間件”轉化為相應的事件實例流處理程序，從而完成對事件實例流的處理。

Fig.3　Spatial and temporal event stream processing framework of Internet of vehicles圖3　車聯(lián)網(wǎng)時空事件實例流處理框架示意圖

如圖3所示，用戶首先將自己關注的事件寫為“事件處理語句”。該“事件處理語句”通過網(wǎng)絡傳輸?shù)杰囕d計算機系統(tǒng)中。在車載計算機系統(tǒng)中，該“事件處理語句”被“事件流處理引擎”轉化為“事件流處理規(guī)則”。汽車在行駛過程中所產(chǎn)生的“時空事件實例流”通過“事件流處理規(guī)則”的處理得到處理結果。這些“時空事件實例流”處理結果再通過網(wǎng)絡傳輸?shù)接脩舻摹笆录臁敝小Ｒ虼?，用戶可以得到自己想要的“事件”?/p>

下面介紹本文提出的能夠處理車聯(lián)網(wǎng)時空事件實例流的事件處理語言STEP。

3　STEP語言的語法

面向車聯(lián)網(wǎng)系統(tǒng)的時空事件處理語言STEP涉及以下語法集合。

（1）常量集合

事件處理表達式的值屬于布爾值集合BOOLEAN={TRUE,FALSE}，其元素用B表示。車聯(lián)網(wǎng)中事件實例的集合EventInstance={EI1,EI2,…,EIn}，其元素用EI表示。每個事件實例又包含若干屬性，即EI=(ID,T,LOC,A)。其中，車聯(lián)網(wǎng)中事件實例的對象標識集合EventInstanceID={ID1,ID2,…,IDn}，其元素用EIid表示。車聯(lián)網(wǎng)中事件實例的時間屬性集合Event-InstanceTIME={(start1,end1),(start2,end2),…,(startn,endn)}，其元素用EIt表示。時空事件的空間屬性集合為EventInstanceLOCATION={(row1,column1),(row2,column2),…,(rown,columnn)}，其元素用EIloc表示。車聯(lián)網(wǎng)系統(tǒng)中時空事件的其他數(shù)值型屬性值記為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是存放時空事件實例的其他數(shù)值型屬性值的變量，該變量集合用Xa表示。

（3）表達式集合

STEP語言的事件處理語句構成的集合記為EPS（event processing sentence），其元素記為eps。事件處理語句是由表達式構成的，而表達式都為布爾型表達式。判斷時空事件發(fā)生的對象標識值布爾表達式集合為IBEXP，其中元素記為ibexp。時間布爾表達式集合為TBEXP，其中元素記為tbexp?？臻g布爾表達式集合為LBEXP，其中元素記為lbexp。一般數(shù)值屬性布爾表達式集合為ABEXP，其中元素記為abexp，其定義如下。

現(xiàn)假設已知常量集和變量集的語法結構。例如，變量通常為非空字母或后跟數(shù)字的非空字符串，那么STEP的語法如下。

①對象標識布爾表達式IBEXP

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

例如：表達式“CarId=10584”表示要判斷當前某汽車標識符變量CarId的值是否等于10584。

其中“，BEFORE”“、EQUAL”“、OVERLAP”“、DURING”是4種時間數(shù)據(jù)的時序關系。

例如：表達式“CarTime BEFORE(20:18:20,20: 19:10)”表示要判斷某汽車的數(shù)據(jù)中時間變量Car-Time的值是否早于時間段(20:18:20,20:19:10)。

②空間屬性布爾表達式LBEXP

其中，“EQ”、“OP”、“IN”、“NORTH”、“EAST”、“NORTHWEST”、“NORTHEAST”是7種空間數(shù)據(jù)關系。

例如：表達式“CarLoc NORTH{(1 052,307)}”表示要判斷某汽車的數(shù)據(jù)中空間屬性變量CarLoc的值是否位于{(1 052,307)}的北方。

③一般數(shù)值屬性布爾表達式ABEXP

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

例如：表達式“CarV>50”表示要判斷某汽車的數(shù)據(jù)中車速變量CarV的值是否大于50 km/h。

④事件處理語句EPS

事件處理語句由前述4種表達式的一個或者多個通過3種算子“;”、“||”和“+”組合而成。算子“;”是順序組合算子，算子“||”是并行組合算子，算子“+”是選擇算子。

例如：事件處理語句“((CarV<100);(CarAcc> 30))”表示首先判斷某汽車發(fā)送的數(shù)據(jù)中車速變量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)))”表示要判斷某汽車發(fā)送的數(shù)據(jù)中標識符變量CarId的值是否等于10584，且數(shù)據(jù)中時間變量CarTime的值是否在時間段(19:18:20,19:19:10)內(nèi)，且數(shù)據(jù)中位置變量CarLoc的值是否在{(1 052,307)}的北方，且數(shù)據(jù)中車速變量的值是否小于100 km/h或者汽車加速度變量值是否小于30 m/s2。

4　STEP語言的操作語義

4.1STEP語言中各屬性變量的設定

STEP語句中各表達式的值由當前存儲時空事件實例的各屬性變量的值決定。

車載計算機系統(tǒng)的時空事件狀態(tài)定義為由車載計算機系統(tǒng)的時空事件實例變量集X到時空事件實例集EventInstance的函數(shù)σ:X→EventInstance，其可用下列子變量的狀態(tài)表示。對象標識子變量狀態(tài)σid定義為：時空事件實例對象標識值變量集Xid到時空事件實例對象標識值集EventInstanceID的函數(shù)σid:Xid→EventInstanceID。時間子變量狀態(tài)σt定義為：時空事件實例時間屬性值變量集Xt到時空事件實例時間屬性值集EventInstanceTIME的函數(shù)σt:Xt→EventInstanceTIME。空間子變量狀態(tài)σloc定義為：時空事件實例空間屬性值變量集Xloc到時空事件實例空間屬性值集EventInstanceLOCATION的函數(shù) σloc: Xloc→EventInstanceLOCATION。數(shù)值子變量狀態(tài)σa定義為：時空事件實例數(shù)值型屬性值變量集Xa到時空事件實例數(shù)值型屬性值集EventInstanceATTRIBUTE的函數(shù)σa：Xa→EventInstanceATTRIBUTE。

于是，σ(x)是狀態(tài)σ下時空事件實例變量x的值EI。σid(xid)是狀態(tài)σid下時空事件實例的對象標識符變量xid的值EIid。同理，σt(xt)是狀態(tài)σt下時空事件實例的時間屬性值變量xt的值EIt。σloc(xloc)是狀態(tài)σloc下時空事件實例的空間屬性值變量xloc的值EIloc。σa(xa)是狀態(tài)σa下時空事件實例的數(shù)值屬性值變量xa的值EIa。有時在不引起混淆的情況下，直接用σ(xid)表示σid(xid)（見第6章的例子）。

另外，經(jīng)過STEP語句處理得到的時空事件實例被傳到用戶端的時空事件庫中，設由用戶端的時空事件庫中的時空事件實例存儲單元集（記為MB）到時空事件實例集（記為EventInstanceB）的函數(shù)σB:MB→EventInstanceB組成。

4.2STEP的操作語義

（1）對象標識布爾表達式IBEXP的賦值規(guī)則

上述規(guī)則是表達式“xid=ID”的賦值規(guī)則。設當前存儲時空事件實例的變量名是x，其子變量xid存放著時空事件實例的標識符值。在第一條規(guī)則中，如果變量xid在當前狀態(tài)σid下其值為常量ID，則表達式“xid=ID”的值為布爾值“TRUE”。在第二條賦值規(guī)則中，如果變量xid在當前狀態(tài)σid下其值不是常量ID，則表達式“xid=ID”的值為布爾值“FALSE”。

（2）時間屬性值布爾表達式TBEXP的賦值規(guī)則

這兩條規(guī)則是表達式“xtBEFORE T”的賦值規(guī)則。設當前存儲時空事件實例的變量名是x，其子變量xt存放著時空事件實例的時間屬性值。在第一條規(guī)則中，如果變量xt在當前狀態(tài)σt下的值與時間常量T的值滿足“BEFORE”關系（即σ(xt).end

其余的時間屬性值布爾表達式的賦值規(guī)則與上述推理規(guī)則類似，不再詳述。

（3）空間屬性值布爾表達式LBEXP的賦值規(guī)則

這兩條規(guī)則是表達式“xlocEQ LOC”的賦值規(guī)則。設當前存儲時空事件實例的變量名是x，其子變量xloc存放著時空事件實例的空間屬性值。在第一條規(guī)則中，如果變量xloc在當前狀態(tài)σloc下的值與空間常量LOC的值滿足“EQ”關系（即σ(xloc)=LOC），則表達式“xlocEQ LOC”的值為布爾值“TRUE”。在第二條賦值規(guī)則中，如果變量xloc在當前狀態(tài)σloc下的值與空間常量LOC的值不滿足“EQ”關系（即σ(xloc)≠LOC），則表達式“xlocEQ LOC”的值為布爾值“FALSE”。

其余的空間屬性值布爾表達式的賦值規(guī)則與上述推理規(guī)則類似，不再詳述。

（4）一般數(shù)值屬性布爾表達式ABEXP的賦值規(guī)則

這兩條規(guī)則是表達式“xa>A”的賦值規(guī)則。設當前存儲時空事件實例的變量名是x，其子變量xa存放著時空事件實例的某數(shù)值型屬性值。在第一條規(guī)則中，如果變量xa在當前狀態(tài)σa下的值大于數(shù)值型常量A的值（即σ(xa)>A），則表達式“xa>A”的值為布爾值“TRUE”。在第二條賦值規(guī)則中，如果變量xa在當前狀態(tài)σa下的值小于或者等于數(shù)值型常量A的值，則表達式“xa>A”的值為布爾值“FALSE”。

其余的數(shù)值型屬性值布爾表達式的賦值規(guī)則與上述賦值規(guī)則類似，不再詳述。

4.3事件處理語句EPS的操作語義

這4條推理規(guī)則是4種原子事件處理語句的操作語義。設當前存儲時空事件實例的變量名是x，以“ibexp”語句為例進行說明：當該原子事件處理語句“ibexp”在當前狀態(tài)σid下的值為布爾值“TRUE”時，則變量x中存儲的時空事件實例值被發(fā)送到用戶端的事件庫中（即ΣB?{σ}），同時變量x存儲單元被清空并準備接收下一個時空事件實例。其他原子事件處理語句類似，不再詳述。

這條推理規(guī)則是順序復合事件處理語句“eps1;eps2”的操作語義。首先計算語句“eps1”的值，如果語句“eps1”在當前狀態(tài)σ下的運算結果為ΣB?{σ}，那么就繼續(xù)計算語句“eps2”的值。

這兩條推理規(guī)則是選擇復合事件處理語句“eps1+eps2”的操作語義。同時計算語句“eps1”和“eps2”的值，如果語句“eps1”和“eps2”在當前狀態(tài)σ下的運算結果之一為ΣB?{σ}，那么選擇復合事件處理語句“eps1+eps2”的運算結果就是ΣB?{σ}。

以上從形式語義學角度形式化地描述了車聯(lián)網(wǎng)時空事件處理語言STEP的操作語義，下面從實現(xiàn)角度給出相應的時空事件流處理算法。

5　基于Petri網(wǎng)的STEP時空事件流處理算法

在基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制中，需要將STEP語句經(jīng)編譯器轉化為相應的處理模型，然后根據(jù)處理模型設計相應的時空事件流處理算法并最終編程實現(xiàn)。

在基于Petri網(wǎng)的事件流處理模型中，用Petri網(wǎng)輸入位置的庫所表示已經(jīng)發(fā)生的事件（或基本事件的某一屬性數(shù)據(jù)），輸出位置的庫所表示需檢測的事件（或數(shù)據(jù)）。庫所內(nèi)的token表示所代表的事件（或數(shù)據(jù)）是否有實例產(chǎn)生。當一個事件（或數(shù)據(jù)）的實例到來時，代表該事件的庫所內(nèi)token狀態(tài)將被改變。通過計算變遷函數(shù)來判斷是否滿足變遷條件。若滿足，則引發(fā)變遷并改變輸入和輸出庫所的狀態(tài)，直到要檢測的輸出位置庫所內(nèi)的token狀態(tài)被改變，此時表示要檢測的事件發(fā)生。針對STEP語言的各種語句，分別建立其對應的Petri網(wǎng)處理模型如下。

（1）“基本結構”Petri網(wǎng)模型如圖4所示。

Fig.4　Petri net model of basic structure圖4　“基本結構”Petri網(wǎng)模型

圖4（a）表示有一個事件的屬性數(shù)據(jù)到達輸入庫所p1，這時判斷該事件的屬性數(shù)據(jù)是否滿足guard條件。當該事件的屬性數(shù)據(jù)不滿足guard條件時，事件被刪除，下一個事件的屬性數(shù)據(jù)進入輸入庫所p1位置。當某個事件的屬性數(shù)據(jù)滿足guard條件時，則輸入庫所p1與輸出庫所p2之間發(fā)生躍遷。輸入庫所p1中的token消失，輸出庫所p2中產(chǎn)生token，如圖4（b）所示。

處理模型為“基本結構”Petri網(wǎng)模型的STEP表達式有：ibexp、tbexp、lbexp和abexp。

（2）“順序結構”Petri網(wǎng)模型如圖5所示。

Fig.5　Petri net model of sequential structure圖5　“順序結構”Petri網(wǎng)模型

圖5（a）表示有一個事件的屬性數(shù)據(jù)到達輸入庫所p1，這時判斷該事件的屬性數(shù)據(jù)是否滿足guard1條件。當該事件的屬性數(shù)據(jù)不滿足guard1條件時，事件被刪除，下一個事件的屬性數(shù)據(jù)進入輸入庫所p1位置。當這個事件的屬性數(shù)據(jù)滿足guard1條件時，則輸入庫所p1與輸出庫所p2之間發(fā)生躍遷。輸入庫所p1中的token消失，輸出庫所p2中產(chǎn)生token，如圖5（b）所示。然后，繼續(xù)判斷這個事件的屬性數(shù)據(jù)是否滿足guard2條件。當這個事件的屬性數(shù)據(jù)滿足guard2條件時，則輸入庫所p2與輸出庫所p3之間發(fā)生躍遷。輸入庫所p2中的token消失，輸出庫所p3中產(chǎn)生token，如圖5（c）所示。

處理模型為“順序結構”Petri網(wǎng)模型的STEP語句為：eps1;eps2。

（3）“并行結構”Petri網(wǎng)模型如圖6所示。

Fig.6　Petri net model of parallel structure圖6　“并行結構”Petri網(wǎng)模型

圖6（a）表示一個事件的兩個屬性數(shù)據(jù)分別到達兩個輸入庫所p1和p2，這時判斷二者是否分別滿足guard1條件和guard2條件。當該事件的某屬性數(shù)據(jù)滿足guard1條件時，則輸入庫所p1與輸出庫所p3之間發(fā)生躍遷。輸入庫所p1中的token消失，輸出庫所p3中產(chǎn)生token。同理，當該事件的某屬性數(shù)據(jù)滿足guard2條件時，則輸入庫所p2與輸出庫所p4之間發(fā)生躍遷。輸入庫所p2中的token消失，輸出庫所p4中產(chǎn)生token。只有當p3和p4庫所中都有token時（如圖6（b）所示），p5庫所前才會發(fā)生躍遷。輸入庫所p3和p4中的token消失，輸出庫所p5中產(chǎn)生token，如圖6（c）所示。當該事件的屬性數(shù)據(jù)分別不滿足guard1條件或guard2條件時，事件被刪除，下一個事件的屬性數(shù)據(jù)進入輸入庫所p1和p2。

處理模型為“并行結構”Petri網(wǎng)模型的STEP語句為：。

（4）“選擇結構”Petri網(wǎng)模型如圖7所示。

Fig.7　Petri net model of choice structure圖7　“選擇結構”Petri網(wǎng)模型

圖7（a）表示一個事件的兩個屬性數(shù)據(jù)分別到達兩個輸入庫所p1和p2，這時判斷二者是否分別滿足guard1條件和guard2條件。當該事件的某屬性數(shù)據(jù)滿足guard1條件時，則輸入庫所p1與輸出庫所p3之間發(fā)生躍遷。輸入庫所p1中的token消失，輸出庫所p3中產(chǎn)生token。同理，當該事件的某屬性數(shù)據(jù)滿足guard2條件時，則輸入庫所p2與輸出庫所p4之間發(fā)生躍遷。輸入庫所p2中的token消失，輸出庫所p4中產(chǎn)生token。只要p3和p4庫所之一有token時（假設p3庫所有token，如圖7（b）所示），guard3條件所代表的躍遷就會發(fā)生。輸入庫所p3中的token消失，輸出庫所p5中產(chǎn)生token，如圖7（c）所示。當該事件的屬性數(shù)據(jù)不滿足guard1條件也不滿足guard2條件時，事件被刪除，下一個事件的屬性數(shù)據(jù)進入輸入庫所p1和p2。

處理模型為“選擇結構”Petri網(wǎng)模型的STEP語句為：eps1+eps2。

根據(jù)上述Petri網(wǎng)處理模型，可得到如下時空事件流處理算法。

算法1基于Petri網(wǎng)模型的事件流處理算法

輸入：時空事件流，STEP語句的Petri網(wǎng)模型。

輸出：滿足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網(wǎng)模型中的所有躍遷被分為3類，分別是“開始躍遷”（TransitionStart）、“中間躍遷”（TransitionMid）和“終結躍遷”（Transition-End）。其中，“開始躍遷”的功能是檢測接收到的事件實例的屬性值。“開始躍遷”通過共享庫所的方法和與其連接的“中間躍遷”傳遞信息，“開始躍遷”的輸出庫所和“中間躍遷”的輸入庫所共享同一變量。“終結躍遷”是一種特殊的“中間躍遷”，該中間躍遷沒有后繼躍遷。在所有的躍遷中，Guard根據(jù)上一節(jié)中的操作語義進行判斷。

在本算法中，從“開始躍遷”開始執(zhí)行，沿著Petri網(wǎng)結構向“終結躍遷”逐步執(zhí)行。因為Petri網(wǎng)中“開始躍遷”到“終結躍遷”之間的躍遷數(shù)是有限的，所以，對于單個事件實例，該算法是可終止的。另設本算法中Petri網(wǎng)模型的躍遷數(shù)為n，則對于單個事件實例該算法的時間復雜度為O(n)。

6　實驗結果與分析

為了檢驗基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制的有效性，下面分別從理論推導和仿真實驗兩個方面對實例進行驗證，并對實驗結果進行分析和比較。

6.1實驗設計

設車聯(lián)網(wǎng)環(huán)境中，一輛標識符為“10584”的汽車在行駛過程中每隔10 s產(chǎn)生一個時空事件實例。其中，設時空事件變量為“Car”，汽車標識符子變量為“CarID”，事件實例的時間屬性值子變量為“Car-Time”，事件實例的空間屬性值子變量為“CarLoc”，事件實例的速度值子變量為“CarV”（即Car=(CarID, CarTime,CarLoc,CarV)）。時空事件實例流中的時空事件實例記為“EI”。設該汽車產(chǎn)生的時空事件實例流中，某連續(xù)的5個時空事件實例如表3所示。

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

在車聯(lián)網(wǎng)系統(tǒng)中，設有4個用戶（User1、User2、User3和User4）分別對該車進行監(jiān)控。由于這些用戶關注的事件不同，他們分別用下面4個STEP語句對該汽車所產(chǎn)生的時空事件流進行處理（STEP語句記為EventStence）。其中，設兩個空間數(shù)據(jù)集合分別為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理論推導過程與結果

根據(jù)STEP語言的操作語義，可以推導出上述4 條STEP語句對表3中的5個時空事件實例的處理結果。下面選取兩個例子說明推導過程。

例1 User2的事件處理語句EventStence2對時空事件實例EI4的處理過程如下。

已知當前時空事件實例為EI4，設當前車載計算機系統(tǒng)中，時空事件變量的狀態(tài)為σ2。用戶User2客戶端的事件庫的狀態(tài)為ΣB2。當前車載計算機系統(tǒng)中，在σ2狀態(tài)下各子變量的值分別為：CarID為“10584”，CarTime為“(19:10:50,19:11:00)”，CarLoc為“{(1052,103)}”，CarV為“93.8”，則有如下推理過程：

從上述推導過程中可以看出，時空事件實例EI4的時間屬性值不滿足事件處理語句EventStence2中的時間表達式，因此EventStence2的計算結果為當前車載計算機系統(tǒng)中，時空事件變量各屬性子變量CarID、CarTime、CarLoc和CarV的值被清空。用戶User2客戶端的事件庫保持原有的狀態(tài)ΣB2不變。

例2 User4的事件處理語句EventStence4對時空事件實例EI4的處理過程如下。

已知當前時空事件實例為EI4，設當前車載計算機系統(tǒng)中，各存儲變量的狀態(tài)為σ4。用戶User4客戶端的事件庫的狀態(tài)為ΣB4。當前車載計算機系統(tǒng)中，在 σ4狀態(tài)下各子變量的值分別為：CarID為“10584”，CarTime為“(19:10:50,19:11:00)”，CarLoc為“{(1 052,103)}”，CarV為“93.8”，則有如下推理過程：

從推導過程中可以看出，時空事件實例EI4的各屬性值都滿足事件處理語句EventStence4，因此EventStence4的計算結果為當前車載計算機系統(tǒng)中，各存儲變量CarID、CarTime、CarLoc和CarV的值（即時空事件實例EI4）被發(fā)送到用戶User4客戶端的事件庫，則該事件庫的狀態(tài)由ΣB4變?yōu)棣睟4?{σ4}。最后，當前車載計算機系統(tǒng)中各存儲變量CarID、CarTime、CarLoc和CarV的值被清空，準備接收下一個時空事件實例。

根據(jù)相應的操作語義，其他STEP語句對表3中的5個時空事件實例的推理過程類似。設4個用戶的事件庫的初始狀態(tài)分別為ΣB1、ΣB2、ΣB3和ΣB4，則表3中的時空事件實例流的理論推導結果如表4所示。

Table 4　Reasoning results of example表4　實例的理論推導結果

從上述理論推導過程和推導結果可以看出，STEP語言的操作語義是有效的。

6.3仿真實驗結果與分析

根據(jù)STEP語言的操作語義和第4章的基于Petri網(wǎng)的時空事件流處理算法1構造仿真程序進行實驗。首先，STEP語言的編譯器由開源工具ANTLRWorks1.5實現(xiàn)（ANTLR提供強大的語言分析功能，能夠實現(xiàn)詞法和語法解析器的自動生成）。

基于ANTLRWorks工具實現(xiàn)的STEP語言的語法如圖8所示。

Fig.8　Syntax of STEP language based on ANTLRWorks tool圖8　基于ANTLRWorks工具實現(xiàn)的STEP語言的語法

其次，基于STEP語言的詞法和語法解析器以及算法1，采用Java語言實現(xiàn)了基于STEP語言的車聯(lián)網(wǎng)時空事件流處理仿真程序。仿真程序運行過程及結果如圖9所示。

Fig.9　Result of simulation program圖9　仿真程序的運行過程及結果

仿真實驗過程中，首先在事件編輯器界面中輸入STEP語句，并且給每個STEP語句設置唯一的編號；然后激活該語句，則在事件查詢結果列表中會顯示出該STEP語句所代表的事件發(fā)生的次數(shù)；用戶可以選中該事件的編號，從而在事件查詢結果詳情中看到該事件的詳細清單。

設4個用戶的事件庫的初始狀態(tài)都為空集，則表3中時空事件實例流的仿真實驗結果如表5所示。

從表5中可以看出，第4章基于Petri網(wǎng)時空事件流處理算法1是有效的。另外，通過比較表4和表5的結果，可以看出根據(jù)STEP語言的操作語義的理論推導結果與根據(jù)算法1構造的仿真程序的實驗結果是一致的，且可以相互印證，從而說明本文提出的基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制是有效的。

Table 5　Simulation results of example表5　實例的仿真實驗結果

7　總結和展望

本文針對車聯(lián)網(wǎng)環(huán)境中移動體所產(chǎn)生的帶有時空特性的數(shù)據(jù)流處理問題，采用事件驅動體系結構將這些時空數(shù)據(jù)流抽象為時空事件實例流進行處理。首先，提出了與車聯(lián)網(wǎng)相適應的時間數(shù)據(jù)模型（簡化的Allen時間數(shù)據(jù)模型）和空間數(shù)據(jù)模型（與地理信息系統(tǒng)兼容的柵格空間數(shù)據(jù)模型），從而建立了時空事件實例模型。其次，基于上述模型提出了一種新的時空事件處理語言STEP。在該語言中，基于上述時空事件實例的時空關系給出了相應的時空運算符和語法，并給出了相應的操作語義。然后，基于STEP語言給出了基于Petri網(wǎng)的車聯(lián)網(wǎng)時空事件流處理算法。最后，通過實驗說明了基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制的有效性。

需要指出的是，本文在設計基于STEP語言的車聯(lián)網(wǎng)時空事件流處理機制時尚未考慮車聯(lián)網(wǎng)事件流的信息安全保護問題和事件流的可靠傳輸問題，這些問題需要進一步研究。另外，本文事件流的處理過程采用的是集中式處理方法，但隨著車聯(lián)網(wǎng)事件流規(guī)模的不斷增加，如何在車聯(lián)網(wǎng)環(huán)境中進行分布式事件流處理也是需要進一步研究的。

[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:從物網(wǎng)到物聯(lián)網(wǎng)[J].計算機研究與發(fā)展,2013,50(6):1127-1134.

[3]陳海明,崔莉,謝開斌,等.物聯(lián)網(wǎng)體系結構與實現(xiàn)方法的比較研究[J].計算機學報,2013,36(1):168-188.

[4]謝開斌,陳海明,崔莉,等.PMDA:一種物理模型驅動的物聯(lián)網(wǎng)軟件體系結構[J].計算機研究與發(fā)展,2013,50 (6):1185-1197.

[8]曹科寧,王永恒,李仁發(fā),等.面向物聯(lián)網(wǎng)的分布式上下文敏感復雜事件處理方法[J].計算機研究與發(fā)展,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—），男，山西太原人，華東師范大學軟件學院博士研究生，主要研究領域為物聯(lián)網(wǎng)理論與技術，移動計算。

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—），男，江蘇徐州人，華東師范大學教育部軟硬件協(xié)同設計技術與應用工程研究中心博士生導師，主要研究領域為形式化理論，物聯(lián)網(wǎng)理論，可信計算理論。

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(國家重點基礎研究發(fā)展計劃(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網(wǎng)絡優(yōu)先出版:2015-09-25,http://www.cnki.net/kcms/detail/11.5602.TP.20150925.1653.002.htmlnism based on STEP language.