李慧勇，陳儀香

華東師范大學(xué) 教育部軟硬件協(xié)同設(shè)計(jì)技術(shù)與應(yīng)用工程研究中心，上海 200062

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

李慧勇，陳儀香+

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

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

1　引言

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

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

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

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

車聯(lián)網(wǎng)系統(tǒng)中的事件同時(shí)具有時(shí)間和空間特性，因此車聯(lián)網(wǎng)中的事件處理語言應(yīng)該包含時(shí)空算子。文獻(xiàn)[5]提出了一種SpaTec復(fù)雜事件處理語言，可以描述監(jiān)視內(nèi)容的時(shí)空屬性。SpaTec語言引入6種基本事件操作算子（concurrency,conjunction,remote,sequence,disjunction,samelocation）和4種組合事件操作算子（same location and sequence,remote and sequence,same location and concurrency,remote and concurrency）。文獻(xiàn)[6]將SpaTec語言應(yīng)用于倫敦市的公交車監(jiān)控系統(tǒng)。文獻(xiàn)[7]提出了一種事件處理語言CPSL，這種語言可以描述車聯(lián)網(wǎng)中事件的多種時(shí)間和空間關(guān)系。這兩種語言都采用簡化的Allen時(shí)間模型[16]為時(shí)間數(shù)據(jù)模型。

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

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

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

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

另外，事件實(shí)例流的處理需要將事件處理語句轉(zhuǎn)化為相應(yīng)的事件流處理模型并最終編程實(shí)現(xiàn)。目前已有的事件流處理模型有：基于樹的事件流處理模型、基于圖的事件流處理模型、基于Petri網(wǎng)的事件流處理模型、基于自動(dòng)機(jī)的事件流處理模型。因?yàn)镻etri網(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í)空數(shù)據(jù)模型、時(shí)空事件實(shí)例模型和車聯(lián)網(wǎng)時(shí)空事件實(shí)例流處理框架；第3章設(shè)計(jì)STEP語言的語法；第4章建立STEP語言的操作語義；第5章設(shè)計(jì)基于Petri網(wǎng)處理模型的車聯(lián)網(wǎng)時(shí)空事件流處理算法；第6章通過實(shí)驗(yàn)說明基于STEP語言的時(shí)空事件流處理機(jī)制的有效性；最后是本文的工作總結(jié)以及進(jìn)一步的工作方向。

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

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

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

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

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

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

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

Table 1　Temporal relationships of STEP表1　STEP語言的時(shí)序關(guān)系

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

（1）TIME1BEFORE TIME2

判斷條件：end1

（2）TIME1EQUALTIME2

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

（3）TIME1OVERLAPTIME2

判斷條件：start1

（4）TIME1DURING TIME2

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

例如：時(shí)間數(shù)據(jù)（20:14:00,20:14:35）和時(shí)間數(shù)據(jù)（22:00:10,22:15:35），因?yàn)?0:14:35小于22:00:10，所以二者的時(shí)序關(guān)系為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ù)模型是把空間看作一個(gè)處處連續(xù)的整體，并將空間劃分為大小均勻的規(guī)則網(wǎng)格陣列，每個(gè)網(wǎng)格為一個(gè)柵格，有唯一的行列號。行與列的數(shù)目取決于系統(tǒng)的分辨率及空間實(shí)體的特征。柵格數(shù)據(jù)模型中的基本單元是柵格。柵格空間數(shù)據(jù)模型中的點(diǎn)（point）、線（line）和區(qū)域（area）表示分別如圖1中的（a）、（b）和（c）的黑色部分。

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

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

例如：圖1（a）中的點(diǎn)空間數(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ù)模型的方向關(guān)系是非常重要的。例如：如果要監(jiān)控一輛行駛中的汽車是否超車，則需要判斷兩輛汽車的方向關(guān)系。下面給出車聯(lián)網(wǎng)中空間數(shù)據(jù)模型的方向關(guān)系的定義。

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

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

該定義中的空間方向關(guān)系如表2所示。

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

條件分別為：

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

例如：判斷兩個(gè)空間數(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)}的關(guān)系。

解：因?yàn)閙ax(rowa)=505，min(rowb)=747

所以max(rowa)

又因?yàn)閙in(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語言的空間關(guān)系

2.3車聯(lián)網(wǎng)系統(tǒng)的時(shí)空事件實(shí)例模型

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

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

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

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

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)時(shí)空事件實(shí)例流示意圖

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

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

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

不同的用戶關(guān)注不同的事件，因此用戶需要用特定的“事件處理語句”表達(dá)其所關(guān)注的事件。在事件驅(qū)動(dòng)體系結(jié)構(gòu)中，支持“事件處理語句”的語言被稱為事件處理語言或事件查詢語言。這些“事件處理語句”通過“事件處理中間件”轉(zhuǎn)化為相應(yīng)的事件實(shí)例流處理程序，從而完成對事件實(shí)例流的處理。

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

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

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

3　STEP語言的語法

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

（1）常量集合

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

（2）變量集合

存放時(shí)空事件實(shí)例的變量記為x，其變量集合用X表示。變量x由時(shí)空事件的對象變量xid、時(shí)間變量xt、位置變量xloc、屬性變量xa組成，并表示為x=(xid,xt, xloc,xa)。各分變量具體定義為：xid是存放時(shí)空事件實(shí)例的對象標(biāo)識值的變量，該變量集合用Xid表示；xt是存放時(shí)空事件實(shí)例的時(shí)間屬性值的變量，該變量集合用Xt表示；xloc是存放時(shí)空事件實(shí)例的空間屬性值的變量，該變量集合用Xloc表示；xa是存放時(shí)空事件實(shí)例的其他數(shù)值型屬性值的變量，該變量集合用Xa表示。

（3）表達(dá)式集合

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

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

①對象標(biāo)識布爾表達(dá)式IBEXP

其中，“=”表示“等于”關(guān)系。

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

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

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

②空間屬性布爾表達(dá)式LBEXP

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

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

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

其中，“=”表示“等于”關(guān)系，“>”表示“大于”關(guān)系，“<”表示“小于”關(guān)系。

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

④事件處理語句EPS

事件處理語句由前述4種表達(dá)式的一個(gè)或者多個(gè)通過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ù)中標(biāo)識符變量CarId的值是否等于10584，且數(shù)據(jù)中時(shí)間變量CarTime的值是否在時(shí)間段(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語言中各屬性變量的設(shè)定

STEP語句中各表達(dá)式的值由當(dāng)前存儲時(shí)空事件實(shí)例的各屬性變量的值決定。

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

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

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

4.2STEP的操作語義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：滿足STEP語句條件的事件實(shí)例。

1.While TRUE do

2.Event←當(dāng)前指針指向的事件實(shí)例;

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）和“終結(jié)躍遷”（Transition-End）。其中，“開始躍遷”的功能是檢測接收到的事件實(shí)例的屬性值。“開始躍遷”通過共享庫所的方法和與其連接的“中間躍遷”傳遞信息，“開始躍遷”的輸出庫所和“中間躍遷”的輸入庫所共享同一變量?！敖K結(jié)躍遷”是一種特殊的“中間躍遷”，該中間躍遷沒有后繼躍遷。在所有的躍遷中，Guard根據(jù)上一節(jié)中的操作語義進(jìn)行判斷。

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

6　實(shí)驗(yàn)結(jié)果與分析

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

6.1實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

Table 4　Reasoning results of example表4　實(shí)例的理論推導(dǎo)結(jié)果

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

6.3仿真實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

Fig.9　Result of simulation program圖9　仿真程序的運(yùn)行過程及結(jié)果

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

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

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

Table 5　Simulation results of example表5　實(shí)例的仿真實(shí)驗(yàn)結(jié)果

7　總結(jié)和展望

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

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

附中文參考文獻(xiàn)：

[2]武建佳,趙偉.WInternet:從物網(wǎng)到物聯(lián)網(wǎng)[J].計(jì)算機(jī)研究與發(fā)展,2013,50(6):1127-1134.

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

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

[8]曹科寧,王永恒,李仁發(fā),等.面向物聯(lián)網(wǎng)的分布式上下文敏感復(fù)雜事件處理方法[J].計(jì)算機(jī)研究與發(fā)展,2013,50 (6):1163-1176.

[9]孟由,欒鐘治,謝明,等.一種基于算子的可擴(kuò)展復(fù)雜事件處理模型[J].軟件學(xué)報(bào),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—），男，山西太原人，華東師范大學(xué)軟件學(xué)院博士研究生，主要研究領(lǐng)域?yàn)槲锫?lián)網(wǎng)理論與技術(shù)，移動(dòng)計(jì)算。

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—），男，江蘇徐州人，華東師范大學(xué)教育部軟硬件協(xié)同設(shè)計(jì)技術(shù)與應(yīng)用工程研究中心博士生導(dǎo)師，主要研究領(lǐng)域?yàn)樾问交碚摚锫?lián)網(wǎng)理論，可信計(jì)算理論。

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(國家自然科學(xué)基金);the National Basic Research Program of China under Grant No.2011CB302802(國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the Shanghai Knowledge Service Platform Project under Grant No.ZF1213(上海知識服務(wù)平臺計(jì)劃);the Project of Shanghai Municipal Science and Technology Commission under Grant No.14511100400(上海市科委項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-09-25,http://www.cnki.net/kcms/detail/11.5602.TP.20150925.1653.002.htmlnism based on STEP language.