# STEIM: A Spatiotemporal Event Interaction Model in V2X Systems Based on a Time Period and a Raster Map

Authors: Cheng Xu; Hengjie Luo; Hong Bao; Pengfei Wang
Journal: Mobile Information Systems
 (2020)

---

## Abstract

The Internet of Vehicles (IoV) is an important artificial intelligence research field for intelligent transportation applications. Complex event interactions are important methods for data flow processing in a Vehicle to Everything (V2X) environment. Unlike the classic Internet of Things (IoT) systems, data streams in V2X include both temporal information and spatial information. Thus, effectively expressing and addressing spatiotemporal data interactions in the IoV is an urgent problem. To solve this problem, we propose a spatiotemporal event interaction model (STEIM). STEIM uses a time period and a raster map for its temporal model and spatial model, respectively. In this paper, first, we provide a spatiotemporal operator and a complete STEIM grammar that effectively expresses the spatiotemporal information of the spatiotemporal event flow in the V2X environment. Second, we describe the design of the operational semantics of the STEIM from the formal semantics. In addition, we provide a spatiotemporal event-stream processing algorithm that is based on the Petri net model. The STEIM establishes a mechanism for V2X event-stream temporal and spatial processing. Finally, the effectiveness of the STEIM-based system is demonstrated experimentally.


---

## Body

## 1. Introduction

The Vehicle-to-Everything (V2X), which is the information exchange between vehicular systems and the outside world of information exchange, is a critical technology for future intelligent transportation systems. V2X enables vehicles, base stations, and infrastructure to obtain real-time traffic information, road information, and pedestrian information [1]. V2X improves safety, reduces congestion, improves traffic efficiency, and provides on-board entertainment information [2]. Currently, V2X applications in the Internet of Vehicles (IoV) remains in the exploratory stage as technical applications for traffic safety, information security problems, and all types of application stability, and interoperability problems have not been tested [3].V2X provides a connection with the outside world; thus, it is a basic and key technology for intelligent automobiles, autonomous vehicles, and future intelligent transportation systems [4]. V2X primarily consists of four functions: Vehicle-to-Network (V2N), Vehicle-to-Vehicle (V2V), Vehicle-to-Infrastructure (V2I), and Vehicle-to-Pedestrian (V2P). V2X uses Dedicated Short Range Communications (DSRC) and Long-Term Evolution-Vehicle (LTE-V); both DSRC and LTE-V are well-known technical standards in the industry [5, 6].In the Intelligent Connected Vehicle (ICV) environment, the cooperative intelligent interaction communication mechanism is the interaction mode between each intelligent agent. Data streams in the V2X include both temporal information and spatial information. In applications, vehicles periodically broadcast a Basic Safety Message (BSM) to other intelligent agents, including information such as position, longitude, latitude, posture state, heading angle, velocity, and acceleration to surrounding vehicles. The vehicle simultaneously receives similar information from surrounding intelligent agents. By processing and analysing these data streams, a vehicle can determine the current values of the surrounding agents. Real-time acquisition, interaction, and processing of information from surrounding vehicles and the relative position of the current vehicle, combined with the actual working situation of vehicle traffic, are numerous complex events [7]. As a starting point, to ensure vehicle and public safety, a variety of different conditions may be derived from this information, such as early warning of unknown states, early warning of known states, emergency braking situations, and vehicle lane change warnings [8, 9].Vehicles run in a complex environment in real time. Thus, complex event-processing technology is required to filter the massive data stream generated by event instance flows to obtain those that concern the user via an event-processing model [10, 11]. Events that concern users are sent to a client events library or disposed of based on a user’s predefined rules. The corresponding processing must also occur in real time [12, 13]. Complex event-processing technology has been successfully applied to IoV systems; however, the spatial data model in V2X driving scenarios has two problems: first, it is incompatible with the spatial model in a geographic information system. Without considering the direction of spatial data, a model that is suitable for both time and space is not available. Second, the direction of the spatial data is not considered. In a complex event processing model for the Internet of Things, the adoption of an appropriate temporal and spatial model can reduce the complexity of the model [14, 15].


### 1.1. Our Contributions

How to effectively express and address the spatiotemporal data flow in the IoV in V2X is a critical problem that must be solved to satisfy the challenges of the massive temporal and spatial information data stream produced in a vehicular network. In this paper, a spatiotemporal event interaction model (STEIM) is proposed. The STEIM model establishes the grammar and the operational semantics. The contributions of the current study are summarised as follows:(1)
A spatiotemporal event interaction model is proposed for V2X. This model establishes the model’s syntax and operational semantics.(2)
The raster map model in a geographic information system (GIS) is adopted as the spatial model in V2X. Based on this raster map spatial model, we provide a method for determining the spatial data direction relations in a vehicular network.(3)
An event flow-processing algorithm model that is based on a Petri net is adopted. We expound on the effectiveness of the processing mechanism in the experimental results and analysis section.


### 1.2. Paper Organization

The remainder of this paper is organised as follows: In Section2, we provide an overview of related studies and similar systems that inform this framework. We provide the data model and the temporal and spatial events for V2X in Section 3. Section 4 presents the STEIM grammar. Section 5 describes the design of STEIM and its operational semantics. Section 6 presents the STEIM algorithm based on a Petri net. The experimental results that concern the task performance and efficiency are provided in Section 7. Section 8 presents our concluding remarks.


## 1.1. Our Contributions

How to effectively express and address the spatiotemporal data flow in the IoV in V2X is a critical problem that must be solved to satisfy the challenges of the massive temporal and spatial information data stream produced in a vehicular network. In this paper, a spatiotemporal event interaction model (STEIM) is proposed. The STEIM model establishes the grammar and the operational semantics. The contributions of the current study are summarised as follows:(1)
A spatiotemporal event interaction model is proposed for V2X. This model establishes the model’s syntax and operational semantics.(2)
The raster map model in a geographic information system (GIS) is adopted as the spatial model in V2X. Based on this raster map spatial model, we provide a method for determining the spatial data direction relations in a vehicular network.(3)
An event flow-processing algorithm model that is based on a Petri net is adopted. We expound on the effectiveness of the processing mechanism in the experimental results and analysis section.


## 1.2. Paper Organization

The remainder of this paper is organised as follows: In Section2, we provide an overview of related studies and similar systems that inform this framework. We provide the data model and the temporal and spatial events for V2X in Section 3. Section 4 presents the STEIM grammar. Section 5 describes the design of STEIM and its operational semantics. Section 6 presents the STEIM algorithm based on a Petri net. The experimental results that concern the task performance and efficiency are provided in Section 7. Section 8 presents our concluding remarks.


## 2. Related Work

Many studies have discussed complex event handling in V2X. The approach proposed in Ashok and Vaidehi [16] primarily relies on spatial abstractions of each object and mining frequent temporal patterns in a sequence of frames to form a regular temporal pattern. This process is repeated for each window of sequences, and support for a temporal sequence is obtained to discover the regular patterns of normal events. However, this approach depends on the outcomes of object detection and tracking methods that are applied to videos. Liu and El Kamel [17] used an algorithm that is designed to improve the information throughput by reorganising the surrounding vehicle platoons. The algorithm considers safety, fuel consumption, speed limits, heterogeneous vehicle features, and passenger comfort. However, the algorithm needs to determine when to activate the algorithm. Li and Yixiang [18] proposed a novel spatial-temporal complex event-processing language for vehicular networks that establishes syntax based on modified spatiotemporal relation operators. In addition, they designed an event-instance stream-processing algorithm. However, their approach did not consider the problem of protecting information security or reliable transmission of incident flow. The approaches in [19–22] achieve a reasonable level of privacy protection. In these studies, vehicles are issued pseudonym certificates, and certificate generation and provisioning are divided among multiple organisations. The schemes support anonymous authentication in V2X. Subsequent research includes automatic adaptation and optimisation of the configuration parameters for the selected road network but also involves heuristic optimisation of these parameters during a preprocessing procedure.In terms of visual analysis of traffic data, Wang et al. [23] used visualization technology to design a spatiotemporal data visualization platform for traffic based on points and heat, which could accurately reflect road traffic conditions and provide scientific and reliable data support for urban road traffic planning and management. Sarraf and McGuire[24] conducted visualization research on accident data from sensors and designed an interactive view interface integrating multisource data. So et al. [25] proposed a traffic congestion index visual analysis system based on GPS trajectory. In conclusion, data visual analysis is increasingly used in intelligent transportation. Data visualization has achieved certain results in the application of traffic data such as trajectory data, traffic flow data, and taxi data. However, there are few research results on traffic accident data transmission visualization.In terms of the identification method of accident occurrence, with the continuous increase of car ownership, the road traffic safety situation is particularly serious. Identifying traffic accidents requires traffic police departments to allocate police forces and deploy rescue equipment according to different road sections [26]. It is of great significance to improve the ability of traffic control. The identification of multiple accident sections is based on the safety of sections to determine the dangerous sections of highways. At present, the identification methods of road sections with multiple traffic accidents mainly include the following categories: (1) applying traffic conflict analysis technology [27]. It judges the possible traffic conflict points by predicting the running track of vehicles and judges the more serious traffic conflicts as the road section with frequent accidents. The method relies less on the historical data of traffic accidents, but the workload of traffic conflict analysis method is larger. Therefore, it is only applicable to the identification of traffic accidents on small urban roads. (2) Identification method based on historical traffic accident data. It first segmented the studied road manually. Then the accident number method and the accident rate method are used to identify the road sections with multiple accidents. Or the accident data can be analysed by building models such as Poisson regression, negative binomial regression, and empirical Bayesian method, and the multiaccident sections can be judged according to the prediction of the accident development trend [28]. This kind of method requires manual segmentation of the road before identification, and the result of segmentation will directly affect the prediction of traffic accident-prone sections. On the other hand, time and weather conditions have a significant impact on traffic safety. The above identification methods of traffic accident-prone sections do not take into account time and weather conditions, which greatly reduces the accuracy of the identification results [29].For the visualization of accident-prone road sections, Fan et al. [30] proposed context-aware big data analysis and spatiotemporal visualization methods for traffic data such as road networks, vehicles, drivers, and weather. Shafabakhsh et al. [31] combined geographic information technology and spatial statistical analysis to reveal the influence of spatial factors on fatal, injured, property loss, and other traffic accidents. Among them, nearest neighbor analysis and k-function were used to study the distribution of urban traffic accidents, and kernel density estimation was used to identify the dangerous areas in the urban network. Based on a large amount of human activity data and traffic accident data and combined with real-time data, Li et al. [32] established a universal prediction model for large-scale real-time traffic accident risk simulation.Some event-processing models focus on the spatial relationships between two events. Jin et al. [33] presented a composite subscription model that describes moving events related to mobile objects and detects whether events are matched with subscriptions in a distributed manner. However, some objects do not share GIS spatial information to obtain a global map. Lee et al. [34] designed a road-network-aware spatial alarm processing system by developing a suite of optimisation techniques using motion-aware filters. The system can increase the hibernation time of mobile clients and reduce wakeups and alarm check frequencies while ensuring a high spatial alarm processing accuracy. Zheng et al. [35] used taxi trajectory data to study the spatiotemporal characteristics of urban residents’ travel patterns from popular areas and hotspots. They proposed a spatiotemporal trajectory clustering method to discover hotspots among popular destinations. However, Lee and Zheng did not consider the direction of spatial data.Our project team began researching individual intelligent vehicles in 2012. We began our research on the technology, platform, and transfer of information concerning driving brain cognition for intelligent vehicles in 2014 [36–38]. Since 2016, we have been studying how V2X vehicles and subsystems should authenticate with each other [2, 39, 40–44]. The spatiotemporal event interaction model architecture is shown in Figure 1, which includes both individual intelligent vehicles.Figure 1
The spatiotemporal event interaction model architecture.Based on the actual surrounding vehicles relative to the location of the current vehicle, the vehicle relative location map in Figure2 can be divided into 13 relative positions according to distance and orientation, namely, front, right front, left front, far ahead, far front left, far front right, left, right, left rear, right rear, far behind, far back left, and far back right. The vehicle relative location map in Figure 2 can be divided into 14 relative positions according to distance and orientation, namely, front, right front, left front, far ahead, far front left, far front right, left, right, left rear, right rear, back, far behind, far back left, and far back right.Figure 2
Vehicle relative location map.Statistical analyses of the causes of traffic accidents are based on accident frequency and loss cost factors, such as comprehensive consideration. The working condition of an accident environment can be divided into vehicles that should stop, loss of vehicle control, vehicle turns, slowing down in the absence of light, and vehicle lane changes. Similarly, the system functions in V2X scenarios spawned a variety of applications for emergency cases, such as abnormal vehicle reminders, dangerous road condition reminders, speed limit warnings, warning for running a red light, dangerous traffic participants collision warnings, green wave guide, congestion reminders, and emergency vehicles ahead. These advanced warnings can help improve the safety and efficiency of public traffic and public transportation systems.The specific scene application function of V2X systems involves distinguishing the relative positions of two objects, calculating the distance and time to collision, and providing a warning.In this paper, we focus on generalising our previous work on formalising driving brain cognition for intelligent vehicles. In addition, we adopt a time period and raster map to form a temporal model and a spatial model, respectively, when building the spatiotemporal event interaction model. The result is the establishment of a mechanism that can be formulated in V2X.


## 3. Driving Brain Cognition Formalization in V2X

In V2X, various sensors continuously generate a large number of multisource and multidimensional data. These data include time, location, direction, speed, acceleration, temperature, license plate numbers, and traffic signals. The majority of these data can be expressed using a common numerical model; for example, velocity can be expressed as a real number. The driving brain formalisation includes a time data model, a spatial data model, and a temporal event instance model.


### 3.1. The Time Data Model of the V2X

In V2X, sensors periodically identify the physical state and generate corresponding data. Therefore, in V2X, the specific time points of data occurrence cannot be obtained; however, they can be inferred from the time interval between two event occurrences. In this paper, the time interval is used to define the time data model for the vehicular network.Definition 1.
The time data model in V2X consists of a time interval, whose value is a pair of sequential time points:(1)TIME=start,end,where start represents the start of the time interval and end represents the end of the time interval. Time is expressed as 24 hours and is accurate to the second.
The temporal relationship among time interval data has been the subject of considerable research. Compared with the classic Allen definition, seven temporal sequence relationships are established based on time periods [45]. Based on the actual demands of V2X, we adopt the simplified Allen time series relationship model shown in Figure 3.
According to Figure3, the temporal relationship of time data can be obtained by comparing the start time and the end time. Given the two time data sets TIME1=start1,end1 and TIME2=start2,end2, the time sequence relationship is determined as follows:(1)
TIME1 BEFORE TIME2Judgement condition:end1<start2(2)
TIME1 EQUAL TIME2Judgement condition:start1=start2 and end1=end2(3)
TIME1 OVERLAP TIME2Judgement condition:end1=start2(4)
TIME1 DURING TIME2Judgement condition:start1<start2 and end1≥start2 and end1<end2(5)
TIME1 DURING TIME2Judgement condition:start1≥start2 and end1≤end2(6)
TIME1 STARTS TIME2Judgement condition:start1=start2 and end1≤end2(7)
TIME1 FINISHES TIME2Judgement condition:start1≥start2 and end1=end2Figure 3
Illustration of the STEIM temporal relationships in V2X.


### 3.2. The Spatial Data Model of the V2X

The spatial data model of V2X needs to be GIS-compatible. In a GIS, the map space can be represented by a raster spatial data model, in which space is considered to be a continuous whole. In addition, the space is divided into an array of uniform ruled grid cells. Each raster is a grid that has a unique number. The number of rows and columns depends on the resolution of the system and the characteristics of the spatial entity. The basic unit in the raster data model is the grid. The points, lines, broken lines, and areas in the raster spatial data model are represented in the black parts of Figures4(a)–4(d), respectively.Figure 4
(a) Point, (b) line, (c) broken line, and (d) areas in the raster spatial data model.
(a)
(b)
(c)
(d)Definition 2.
The V2X spatial data model is a raster spatial data model, whose values are a set of contiguous raster sequence pairs denoted as(2)LOCATION=row1,column1,row2,column2,…,rown,columnn.
This spatial data model is collectively referred to as the “driving brain.” The driving brain model can be formalised in V2X. For example, monitoring the overtaking of a moving vehicle involves judging the directions of the two vehicles. The definition of the direction relationship of the driving brain formalisation spatial data model in V2X is presented as follows:Definition 3.
The formalised driving brain raster spatial data model has seven spatial direction relations: NORTH, EAST, NORTHEAST, NORTHWEST, EQUAL, OVERLAP, and IN, where the NORTH, EAST, NORTHEAST, and NORTHWEST relationships indicate that the directional relationship of the intersection of two spatial data sets is empty. This model can fully describe the disjoint position relations for eight types of spatial data.
The EQUAL, OVERLAP, and IN spatial position relations describe the relationship between two groups of spatial data. EQUAL reflects that the two spatial data are equal. The IN relation describes one spatial data set as a subset of the other spatial data set. The OVERLAP relationship describes non-EQUAL and non-IN relations and represents the direction of the intersection. The spatial orientation relationship in this definition is shown in Figure5.
Based on Figure5, the direction relationship of spatial data can be obtained by comparing the grid collection relations of the spatial data model.
There are two spatial data:(3)LOCATIONa=rowa1,columna1,rowa2,columna2,…,rowan,columnan,LOCATIONb=rowb1,columnb1,rowb2,columnb2,…,rowbn,columnbn.
Here, rowa and columna represent the row value sequence and the column value sequence, respectively, of the spatial data:(4)rowa=rowa1,rowa2,…,rowan,columna=columna1,columna2,…,columnan.
Themin and max function obtain the minimum value and maximum value, respectively. Thus, minrowa and maxrowa represent the minimum value and maximum value, respectively, of the row values in the spatial data LOCATIONa. Similarly, mincolumnb and maxcolumnb represent the minimum value and maximum value, respectively, of the column values in LOCATIONb.
The judgement conditions of the direction relationship of the spatial data in V2X are as follows:LOCATIONa NORTH LOCATIONbJudgement condition:(5)maxrowa<minrowb,mincolumna>mincolumnb,maxcolumna<maxcolumnb.LOCATIONa EAST LOCATIONbJudgement condition:(6)mincolumna>maxcolumnb,maxrowa<maxrowb,minrowa<maxrowb.LOCATIONa NORTHEAST LOCATIONbJudgement condition:(7)maxrowa<minrowb,mincolumna>maxcolumnb.LOCATIONa NORTHWEST LOCATIONbJudgement condition:(8)maxrowa<minrowb,maxcolumna<mincolumnb.LOCATIONa EQUAL LOCATIONbJudgement condition:LOCATIONa=LOCATIONbLOCATIONa OVERLAP LOCATIONbJudgement condition:LOCATIONa∩LOCATIONb≠∅LOCATIONa IN LOCATIONbJudgement condition:LOCATIONa⊂LOCATIONb.Figure 5
Seven spatial direction relations of STEIM. (a) a NORTH b, (b) a EAST b, (c) a NORTHEAST b, (d) a NORTHWEST b, (e) a EQUAL b and a IN b. (f) a OVERLAP b.
(a)
(b)
(c)
(d)
(e)
(f)


### 3.3. Spatial and Temporal Event Instance Model of V2X

In the driving brain architecture of V2X, all data are abstracted into event instances. As the data of V2X is spatiotemporal, the event instances of the system are also spatiotemporal. V2X focuses on the object condition attribute values, such as speed, time, location, direction, status, and value. These attributes are generated by various sensor types, which are embedded in the sensing equipment. Data collection occurs for particular objects, in which an object is a spatial-temporal event instance.Definition 4.
The V2X time event instance contains a sequence of various sensing data of objects in the vehicular network:(9)VehicularEvent=ID,TIME,LOCATION,ATTRIBUTE,where ID is a unique identification value for the object in V2X. The value can be an IP address, a QuickMark code, or an RFID tag. TIME is a time attribute value that uses the time data model in Definition 1. LOCATION is a spatial attribute value that uses the spatial data model in Definition 2:(10)ATTRIBUTE=Attribute1,Attribute2,…,Attributen,where Attribute1, Attribute2, …, Attributen are the values of other types of numeric attributes, including speed, acceleration, temperature, and humidity.
Definition4 emphasises that the event instance in V2X must include the spatial and temporal characteristics. Thus, the time attribute values and spatial attribute values of the event instance are critical. All types of sensors continuously generate data in V2X. Thus, these basic spatiotemporal event instance sequences constitute the instance flow of the spatiotemporal events.


## 3.1. The Time Data Model of the V2X

In V2X, sensors periodically identify the physical state and generate corresponding data. Therefore, in V2X, the specific time points of data occurrence cannot be obtained; however, they can be inferred from the time interval between two event occurrences. In this paper, the time interval is used to define the time data model for the vehicular network.Definition 1.
The time data model in V2X consists of a time interval, whose value is a pair of sequential time points:(1)TIME=start,end,where start represents the start of the time interval and end represents the end of the time interval. Time is expressed as 24 hours and is accurate to the second.
The temporal relationship among time interval data has been the subject of considerable research. Compared with the classic Allen definition, seven temporal sequence relationships are established based on time periods [45]. Based on the actual demands of V2X, we adopt the simplified Allen time series relationship model shown in Figure 3.
According to Figure3, the temporal relationship of time data can be obtained by comparing the start time and the end time. Given the two time data sets TIME1=start1,end1 and TIME2=start2,end2, the time sequence relationship is determined as follows:(1)
TIME1 BEFORE TIME2Judgement condition:end1<start2(2)
TIME1 EQUAL TIME2Judgement condition:start1=start2 and end1=end2(3)
TIME1 OVERLAP TIME2Judgement condition:end1=start2(4)
TIME1 DURING TIME2Judgement condition:start1<start2 and end1≥start2 and end1<end2(5)
TIME1 DURING TIME2Judgement condition:start1≥start2 and end1≤end2(6)
TIME1 STARTS TIME2Judgement condition:start1=start2 and end1≤end2(7)
TIME1 FINISHES TIME2Judgement condition:start1≥start2 and end1=end2Figure 3
Illustration of the STEIM temporal relationships in V2X.


## 3.2. The Spatial Data Model of the V2X

The spatial data model of V2X needs to be GIS-compatible. In a GIS, the map space can be represented by a raster spatial data model, in which space is considered to be a continuous whole. In addition, the space is divided into an array of uniform ruled grid cells. Each raster is a grid that has a unique number. The number of rows and columns depends on the resolution of the system and the characteristics of the spatial entity. The basic unit in the raster data model is the grid. The points, lines, broken lines, and areas in the raster spatial data model are represented in the black parts of Figures4(a)–4(d), respectively.Figure 4
(a) Point, (b) line, (c) broken line, and (d) areas in the raster spatial data model.
(a)
(b)
(c)
(d)Definition 2.
The V2X spatial data model is a raster spatial data model, whose values are a set of contiguous raster sequence pairs denoted as(2)LOCATION=row1,column1,row2,column2,…,rown,columnn.
This spatial data model is collectively referred to as the “driving brain.” The driving brain model can be formalised in V2X. For example, monitoring the overtaking of a moving vehicle involves judging the directions of the two vehicles. The definition of the direction relationship of the driving brain formalisation spatial data model in V2X is presented as follows:Definition 3.
The formalised driving brain raster spatial data model has seven spatial direction relations: NORTH, EAST, NORTHEAST, NORTHWEST, EQUAL, OVERLAP, and IN, where the NORTH, EAST, NORTHEAST, and NORTHWEST relationships indicate that the directional relationship of the intersection of two spatial data sets is empty. This model can fully describe the disjoint position relations for eight types of spatial data.
The EQUAL, OVERLAP, and IN spatial position relations describe the relationship between two groups of spatial data. EQUAL reflects that the two spatial data are equal. The IN relation describes one spatial data set as a subset of the other spatial data set. The OVERLAP relationship describes non-EQUAL and non-IN relations and represents the direction of the intersection. The spatial orientation relationship in this definition is shown in Figure5.
Based on Figure5, the direction relationship of spatial data can be obtained by comparing the grid collection relations of the spatial data model.
There are two spatial data:(3)LOCATIONa=rowa1,columna1,rowa2,columna2,…,rowan,columnan,LOCATIONb=rowb1,columnb1,rowb2,columnb2,…,rowbn,columnbn.
Here, rowa and columna represent the row value sequence and the column value sequence, respectively, of the spatial data:(4)rowa=rowa1,rowa2,…,rowan,columna=columna1,columna2,…,columnan.
Themin and max function obtain the minimum value and maximum value, respectively. Thus, minrowa and maxrowa represent the minimum value and maximum value, respectively, of the row values in the spatial data LOCATIONa. Similarly, mincolumnb and maxcolumnb represent the minimum value and maximum value, respectively, of the column values in LOCATIONb.
The judgement conditions of the direction relationship of the spatial data in V2X are as follows:LOCATIONa NORTH LOCATIONbJudgement condition:(5)maxrowa<minrowb,mincolumna>mincolumnb,maxcolumna<maxcolumnb.LOCATIONa EAST LOCATIONbJudgement condition:(6)mincolumna>maxcolumnb,maxrowa<maxrowb,minrowa<maxrowb.LOCATIONa NORTHEAST LOCATIONbJudgement condition:(7)maxrowa<minrowb,mincolumna>maxcolumnb.LOCATIONa NORTHWEST LOCATIONbJudgement condition:(8)maxrowa<minrowb,maxcolumna<mincolumnb.LOCATIONa EQUAL LOCATIONbJudgement condition:LOCATIONa=LOCATIONbLOCATIONa OVERLAP LOCATIONbJudgement condition:LOCATIONa∩LOCATIONb≠∅LOCATIONa IN LOCATIONbJudgement condition:LOCATIONa⊂LOCATIONb.Figure 5
Seven spatial direction relations of STEIM. (a) a NORTH b, (b) a EAST b, (c) a NORTHEAST b, (d) a NORTHWEST b, (e) a EQUAL b and a IN b. (f) a OVERLAP b.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.3. Spatial and Temporal Event Instance Model of V2X

In the driving brain architecture of V2X, all data are abstracted into event instances. As the data of V2X is spatiotemporal, the event instances of the system are also spatiotemporal. V2X focuses on the object condition attribute values, such as speed, time, location, direction, status, and value. These attributes are generated by various sensor types, which are embedded in the sensing equipment. Data collection occurs for particular objects, in which an object is a spatial-temporal event instance.Definition 4.
The V2X time event instance contains a sequence of various sensing data of objects in the vehicular network:(9)VehicularEvent=ID,TIME,LOCATION,ATTRIBUTE,where ID is a unique identification value for the object in V2X. The value can be an IP address, a QuickMark code, or an RFID tag. TIME is a time attribute value that uses the time data model in Definition 1. LOCATION is a spatial attribute value that uses the spatial data model in Definition 2:(10)ATTRIBUTE=Attribute1,Attribute2,…,Attributen,where Attribute1, Attribute2, …, Attributen are the values of other types of numeric attributes, including speed, acceleration, temperature, and humidity.
Definition4 emphasises that the event instance in V2X must include the spatial and temporal characteristics. Thus, the time attribute values and spatial attribute values of the event instance are critical. All types of sensors continuously generate data in V2X. Thus, these basic spatiotemporal event instance sequences constitute the instance flow of the spatiotemporal events.


## 4. The STEIM Model

In a vehicular network, various objects continuously generate temporal and spatial event flows. However, the people in the vehicle generally focus only on the event instances that satisfy certain conditions. Different vehicles tend to focus on different event instances, and different users tend to focus on different events. Thus, users need to indicate their interest in processing specific events. In the STEIM architecture, the model supports event-processing selections. These event-processing selections are transformed into the corresponding event instance flow handler by event-processing middleware to complete the processing of the event instance flow. In Figure6, the spatiotemporal event-processing STEIM model for V2X involves the following syntax collection: the model is divided into three modules: vehicular users, on-board computer systems, and a cloud database. Vehicular users transmit their vehicle information to the on-board computer system via data-processing statements. The on-board computer system uses event flow-processing rules to parse the event-processing sentences and upload them to the cloud database. Vehicular users obtain vehicle information from the cloud database for other vehicular users.Figure 6
The STEIM framework.


### 4.1. Constant Collection

The value of an event handler expression is the Boolean set, whose elements are represented byB:(11)BOOLEAN=TRUE,FALSE.A collection of event instances in V2X, whose elements are represented byVE, is represented as(12)VehicularEvent=VE1,VE2,…,VEn.Each event instance can contain several attributes.(13)VE=ID,T,LOC,A.An identity collection of event instances in V2X has elements represented byVEid.(14)VehicularEventID=ID1,ID2,…,IDn.A collection of time attributes for event instances in V2X has elements represented byVEt:(15)VehicularEventTIME=start1,end1,start2,end2,…,startn,endn.A collection of spatial attributes for the spatiotemporal events in V2X has elements that are represented byVEloc:(16)VehicularEventLOCATION=row1,column1,row2,column2,…,rown,columnn.The elements of other numeric attribute values of temporal and spatial events in V2X are represented byVEa:(17)VehicularEventATTRIBUTE=ATTRIBUTE1,ATTRIBUTE2,…,ATTRIBUTEn.


### 4.2. Variables’ Collection

The variable that holds the instance of the space time event is denoted byx, and its variable set is represented by X. The variable x is composed of the object variable xid, the time variable xt, the location variable xloc, and the attribute variable xa, and is expressed as x=xid,xt,xloc,xa.Each subvariable is specifically defined as follows: the variablexid holds the object identification value of the spatiotemporal event instance and is represented by Xid; the variable xt holds the time attribute value of the temporal and spatial event instance and is represented by Xt, while the xloc holds the spatial attribute value of the temporal and spatial event instance and is represented by Xloc. The variable xa holds the other numeric attribute values of a temporal and spatial event instance and is represented by Xa.


### 4.3. Expression Collection

The set of event-processing statements in the STEIM model is referred to as spatiotemporal event interaction (SEI). The elements of SEI are represented bysei. SEI consists of Boolean expressions. The object identification value Boolean expression that determines the occurrence of temporal and spatial events is IBSEI. Its elements are represented by IBsei. The time Boolean expression set is TBSEI, and its elements are represented by TBsei. The space Boolean expression is LBSEI, and its elements are represented by LBsei. The general numeric attribute Boolean expression set is ABSEI, and its elements are represented by ABsei.


### 4.4. Grammar Interaction of STEIM

The STEIM model applies to a known constant set and a variable set. A variable is usually represented by a nonnull string. In addition, variables are not empty or followed by a string.(1)
The object Boolean expressionIBsei is(18)ibsei⩴xid=ID,where “ = ” denotes an “equal” relation. The time Boolean expression is(19)tbsei⩴xtBEFORETxtEQUALTxtOVERLAPTxtDURINGT.In this formula, BEFORE, EQUAL, OVERLAP, and DURING represent the temporal relations of time data.For example, the expressionVehicleTime BEFORE 12:20:30,12:21:10 means to judge whether the time variable VehicleTime value in the data stream of a vehicle is earlier than the time period (12 : 20 : 30, 12 : 21 : 10).(2)
The object Boolean expressionLBsei is(20)lbsei⩴xlocEQUALLOCxlocOVERLAPLOCxlocINLOCxlocEASTLOCxlocNORTHLOCxlocNORTHWESTLOCxlocNORTHEASTLOC,where “EQUAL”,“OVERLAP”, “IN”, “NORTH”,“EAST”,“NORTHWEST,” and “NORTHEAST” are the seven spatial data relations that were previously defined. For example, the expression “VehicleLoc NORTH (985, 266)” determines whether the value of the spatial attribute variable VehicleLoc in a vehicle’s data is located NORTH of (985, 266).(3)
The general numerical attribute Boolean expressionsABsei are described as follows:(21)absei⩴xa=Axa>Axa<A,where “ = ” denotes an “equal” relation, “>” indicates a “greater than” relation, and “<” denotes a “less than” relation. For example, the expression “VehicleV>65” returns a Boolean value that represents whether the value of the speed variable VehicleV in a vehicle’s data is greater than 65 km/h.(4)
Event-handling statement:(22)sei⩴ibseitbseilbseiabseisei;seiseiseisei+sei.The event-processing statement consists of four expressions using three operators “;,” “||,” and “+.” The operator “;” is a sequence combination operator. The operator “||” is a parallel combination operator, and the operator “+” is the selection operator.For example, the event-handling statement,(23)VehicleId=1253VehicleTimeDURING12:20:30,12:21:10VehicleLocNORTH985,358VehicleV<80+VehicleAcc<15,determines whether the vehicle that sent data has an identifier VehicleId equal to 1253, whether the data in the time value of the variable VehicleTime is within the time (12 : 20 : 30, 12 : 21 : 10), whether the value of the position variable VehicleLoc in the data is NORTH of (985, 358), and whether the value of the speed variable in the data is less than 80 km/h or the vehicle acceleration variable value is less than 15 m/s2.


## 4.1. Constant Collection

The value of an event handler expression is the Boolean set, whose elements are represented byB:(11)BOOLEAN=TRUE,FALSE.A collection of event instances in V2X, whose elements are represented byVE, is represented as(12)VehicularEvent=VE1,VE2,…,VEn.Each event instance can contain several attributes.(13)VE=ID,T,LOC,A.An identity collection of event instances in V2X has elements represented byVEid.(14)VehicularEventID=ID1,ID2,…,IDn.A collection of time attributes for event instances in V2X has elements represented byVEt:(15)VehicularEventTIME=start1,end1,start2,end2,…,startn,endn.A collection of spatial attributes for the spatiotemporal events in V2X has elements that are represented byVEloc:(16)VehicularEventLOCATION=row1,column1,row2,column2,…,rown,columnn.The elements of other numeric attribute values of temporal and spatial events in V2X are represented byVEa:(17)VehicularEventATTRIBUTE=ATTRIBUTE1,ATTRIBUTE2,…,ATTRIBUTEn.


## 4.2. Variables’ Collection

The variable that holds the instance of the space time event is denoted byx, and its variable set is represented by X. The variable x is composed of the object variable xid, the time variable xt, the location variable xloc, and the attribute variable xa, and is expressed as x=xid,xt,xloc,xa.Each subvariable is specifically defined as follows: the variablexid holds the object identification value of the spatiotemporal event instance and is represented by Xid; the variable xt holds the time attribute value of the temporal and spatial event instance and is represented by Xt, while the xloc holds the spatial attribute value of the temporal and spatial event instance and is represented by Xloc. The variable xa holds the other numeric attribute values of a temporal and spatial event instance and is represented by Xa.


## 4.3. Expression Collection

The set of event-processing statements in the STEIM model is referred to as spatiotemporal event interaction (SEI). The elements of SEI are represented bysei. SEI consists of Boolean expressions. The object identification value Boolean expression that determines the occurrence of temporal and spatial events is IBSEI. Its elements are represented by IBsei. The time Boolean expression set is TBSEI, and its elements are represented by TBsei. The space Boolean expression is LBSEI, and its elements are represented by LBsei. The general numeric attribute Boolean expression set is ABSEI, and its elements are represented by ABsei.


## 4.4. Grammar Interaction of STEIM

The STEIM model applies to a known constant set and a variable set. A variable is usually represented by a nonnull string. In addition, variables are not empty or followed by a string.(1)
The object Boolean expressionIBsei is(18)ibsei⩴xid=ID,where “ = ” denotes an “equal” relation. The time Boolean expression is(19)tbsei⩴xtBEFORETxtEQUALTxtOVERLAPTxtDURINGT.In this formula, BEFORE, EQUAL, OVERLAP, and DURING represent the temporal relations of time data.For example, the expressionVehicleTime BEFORE 12:20:30,12:21:10 means to judge whether the time variable VehicleTime value in the data stream of a vehicle is earlier than the time period (12 : 20 : 30, 12 : 21 : 10).(2)
The object Boolean expressionLBsei is(20)lbsei⩴xlocEQUALLOCxlocOVERLAPLOCxlocINLOCxlocEASTLOCxlocNORTHLOCxlocNORTHWESTLOCxlocNORTHEASTLOC,where “EQUAL”,“OVERLAP”, “IN”, “NORTH”,“EAST”,“NORTHWEST,” and “NORTHEAST” are the seven spatial data relations that were previously defined. For example, the expression “VehicleLoc NORTH (985, 266)” determines whether the value of the spatial attribute variable VehicleLoc in a vehicle’s data is located NORTH of (985, 266).(3)
The general numerical attribute Boolean expressionsABsei are described as follows:(21)absei⩴xa=Axa>Axa<A,where “ = ” denotes an “equal” relation, “>” indicates a “greater than” relation, and “<” denotes a “less than” relation. For example, the expression “VehicleV>65” returns a Boolean value that represents whether the value of the speed variable VehicleV in a vehicle’s data is greater than 65 km/h.(4)
Event-handling statement:(22)sei⩴ibseitbseilbseiabseisei;seiseiseisei+sei.The event-processing statement consists of four expressions using three operators “;,” “||,” and “+.” The operator “;” is a sequence combination operator. The operator “||” is a parallel combination operator, and the operator “+” is the selection operator.For example, the event-handling statement,(23)VehicleId=1253VehicleTimeDURING12:20:30,12:21:10VehicleLocNORTH985,358VehicleV<80+VehicleAcc<15,determines whether the vehicle that sent data has an identifier VehicleId equal to 1253, whether the data in the time value of the variable VehicleTime is within the time (12 : 20 : 30, 12 : 21 : 10), whether the value of the position variable VehicleLoc in the data is NORTH of (985, 358), and whether the value of the speed variable in the data is less than 80 km/h or the vehicle acceleration variable value is less than 15 m/s2.


## 5. Operational Semantics of STEIM

### 5.1. Setting Property Variables in STEIM

The value of each expression in the model is determined by the value of each attribute variable. These values are currently stored in the temporal and spatial event instance.The temporal and spatial event state of STEIM is defined as a function of the temporal and spatialEventInstance variable set of the on-board computer system:(24)δ:X⟶VehicularEvent.The object identification subvariable state is defined as the time-space event instance object identified by a function of the setXid to the temporal and spatial event instance object identification value set VehicularEventID:(25)δid:Xid⟶VehicularEventID.The time-dependent variable state is defined as a function of the time attribute value variable setXt to the time attribute value set VehicularEventTIME:(26)δt:Xt⟶VehicularEventTIME.The spatial subvariable state is defined as a function of the spatial attribute value variable setXloc to the spatial value set VehicularEventLOCATION:(27)δloc:Xloc⟶VehicularEventLOCATION.The state of the numerical subvariables is defined as a function of the numeric attribute value setXa to the time-space event instance numeric value set VehicularEventATTRIBUTE:(28)δaXa⟶VehicularEventATTRIBUTE.Thus, in stateδ, the value VE of the space event instance variable x is expressed as δx. In state δid, the value VEid of the object identifier variable xid is expressed as δidxid. In state δt, the value VEt of the time attribute value variable xt is expressed as δtxt. In state δloc, the value VEloc of the spatial attribute variable xloc is expressed as δlocxloc. In state δa, the value VEa of the numeric attribute variable xa is expressed as δaxa.In the STEIM model, event instances of spatial and temporal events in the database are sent to clients. The client database of spatiotemporal events functions as a storage unit for the spatiotemporal event instance setEventInstanceB:(29)δB:MB⟶VehicularEventB.In stateδid, the IBSEI waits for the calculation and evaluates the results to the Boolean TRUE or FALSE, which is expressed as ibsei,δid⟶B. In state δ:ΣB, the time event instance variable x results are stored in the client event database as δ′:ΣB′, which is expressed as ibsei,δ:ΣB⟶δ′:ΣB′, where ibsei,δid and ibsei,δ:ΣB are IBSEI expressions.


### 5.2. Operational Semantics of STEIM

(1)
The assignment rule for an object using the Boolean IBSEI expression is expressed as follows:
(30)
δ
i
d
x
i
d
=
I
D
x
i
d
=
I
D
,
δ
i
d
⟶
T
R
U
E
,
δ
i
d
x
i
d
≠
I
D
x
i
d
=
I
D
,
δ
i
d
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxid=ID. The variable name of the stored time event instance is x, and the stored child variable xid stored is the identifier value of the time event instance. If the variable xid is a constant ID in the current state δid, the value of the expression xid=ID is the Boolean TRUE value. When the variable xid is not a constant ID in the current state xid, the value of the expression xid=ID is the Boolean FALSE value.
(2)
The assignment rule of the time attribute for the Boolean expression TBSEI is
(31)
δ
t
x
t
.
e
n
d
<
T
.
s
t
a
r
t
x
t
B
E
F
O
R
E
T
,
δ
t
⟶
T
R
U
E
,
δ
t
x
t
.
e
n
d
≥
T
.
s
t
a
r
t
x
t
B
E
F
O
R
E
T
,
δ
t
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxtBEFORET. The variable name of the storage time-space event instance is x. In addition, the child variable xt stores the time value of the time-space event instance. If the variable xt is δxt.end<T.start in the current state δt, the value of the expression xtBEFORET is the Boolean TRUE. If the variable xid is δxt.end≥T.start in the current state δt, the value of the expression xtBEFORET is the Boolean value FALSE. The remainder of the time-space attribute value Boolean expressions have the same assignment rule as the previous inference rule.
(3)
The assignment rule of the spatial attribute for the Boolean expression LBSEI is expressed as
(32)
δ
l
o
c
x
l
o
c
=
L
O
C
x
l
o
c
E
Q
U
A
L
L
O
C
,
δ
l
o
c
⟶
T
R
U
E
,
δ
l
o
c
x
l
o
c
≠
L
O
C
x
l
o
c
E
Q
U
A
L
L
O
C
,
δ
l
o
c
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxlocEQUALLOC. The variable name of the stored spatial attribute event instance is x. In addition, the child variable xloc stores the time value of the spatial attribute event instance. If the variable xloc is δxloc=LOC in the current state δloc, the value of the expression xlocEQUALLOC is the Boolean TRUE value. When the variable xloc is δxloc≠LOC in the current state δloc, the value of the expression xlocEQUALLOC is the Boolean FALSE value. The remainder of the spatial attribute value Boolean expressions have the same assignment rule as the previous inference rule.
(4)
The assignment rule of a general numerical attribute for the Boolean expression ABSEI is expressed as follows:
(33)
δ
a
x
a
>
A
x
a
>
A
,
δ
a
⟶
T
R
U
E
,
δ
a
x
a
≤
A
x
a
>
A
,
δ
a
⟶
F
A
L
S
E
,which is the assignment rule for the expression xa>A. The variable name of the stored spatial event instance is x. In addition, the child variable xa stores the number value of the spatial event instance. If the variable xa is δxa>A in the current state δa, the value of the expression xa>A is the Boolean TRUE value. When the variable xa is δxa<A in the current state δa, the value of the expression xa>A is the Boolean FALSE value. The remainder of the spatial value Boolean expressions have the same assignment rule as the previous inference rule.


## 5.1. Setting Property Variables in STEIM

The value of each expression in the model is determined by the value of each attribute variable. These values are currently stored in the temporal and spatial event instance.The temporal and spatial event state of STEIM is defined as a function of the temporal and spatialEventInstance variable set of the on-board computer system:(24)δ:X⟶VehicularEvent.The object identification subvariable state is defined as the time-space event instance object identified by a function of the setXid to the temporal and spatial event instance object identification value set VehicularEventID:(25)δid:Xid⟶VehicularEventID.The time-dependent variable state is defined as a function of the time attribute value variable setXt to the time attribute value set VehicularEventTIME:(26)δt:Xt⟶VehicularEventTIME.The spatial subvariable state is defined as a function of the spatial attribute value variable setXloc to the spatial value set VehicularEventLOCATION:(27)δloc:Xloc⟶VehicularEventLOCATION.The state of the numerical subvariables is defined as a function of the numeric attribute value setXa to the time-space event instance numeric value set VehicularEventATTRIBUTE:(28)δaXa⟶VehicularEventATTRIBUTE.Thus, in stateδ, the value VE of the space event instance variable x is expressed as δx. In state δid, the value VEid of the object identifier variable xid is expressed as δidxid. In state δt, the value VEt of the time attribute value variable xt is expressed as δtxt. In state δloc, the value VEloc of the spatial attribute variable xloc is expressed as δlocxloc. In state δa, the value VEa of the numeric attribute variable xa is expressed as δaxa.In the STEIM model, event instances of spatial and temporal events in the database are sent to clients. The client database of spatiotemporal events functions as a storage unit for the spatiotemporal event instance setEventInstanceB:(29)δB:MB⟶VehicularEventB.In stateδid, the IBSEI waits for the calculation and evaluates the results to the Boolean TRUE or FALSE, which is expressed as ibsei,δid⟶B. In state δ:ΣB, the time event instance variable x results are stored in the client event database as δ′:ΣB′, which is expressed as ibsei,δ:ΣB⟶δ′:ΣB′, where ibsei,δid and ibsei,δ:ΣB are IBSEI expressions.


## 5.2. Operational Semantics of STEIM

(1)
The assignment rule for an object using the Boolean IBSEI expression is expressed as follows:
(30)
δ
i
d
x
i
d
=
I
D
x
i
d
=
I
D
,
δ
i
d
⟶
T
R
U
E
,
δ
i
d
x
i
d
≠
I
D
x
i
d
=
I
D
,
δ
i
d
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxid=ID. The variable name of the stored time event instance is x, and the stored child variable xid stored is the identifier value of the time event instance. If the variable xid is a constant ID in the current state δid, the value of the expression xid=ID is the Boolean TRUE value. When the variable xid is not a constant ID in the current state xid, the value of the expression xid=ID is the Boolean FALSE value.
(2)
The assignment rule of the time attribute for the Boolean expression TBSEI is
(31)
δ
t
x
t
.
e
n
d
<
T
.
s
t
a
r
t
x
t
B
E
F
O
R
E
T
,
δ
t
⟶
T
R
U
E
,
δ
t
x
t
.
e
n
d
≥
T
.
s
t
a
r
t
x
t
B
E
F
O
R
E
T
,
δ
t
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxtBEFORET. The variable name of the storage time-space event instance is x. In addition, the child variable xt stores the time value of the time-space event instance. If the variable xt is δxt.end<T.start in the current state δt, the value of the expression xtBEFORET is the Boolean TRUE. If the variable xid is δxt.end≥T.start in the current state δt, the value of the expression xtBEFORET is the Boolean value FALSE. The remainder of the time-space attribute value Boolean expressions have the same assignment rule as the previous inference rule.
(3)
The assignment rule of the spatial attribute for the Boolean expression LBSEI is expressed as
(32)
δ
l
o
c
x
l
o
c
=
L
O
C
x
l
o
c
E
Q
U
A
L
L
O
C
,
δ
l
o
c
⟶
T
R
U
E
,
δ
l
o
c
x
l
o
c
≠
L
O
C
x
l
o
c
E
Q
U
A
L
L
O
C
,
δ
l
o
c
⟶
F
A
L
S
E
,
which is the assignment rule for the expressionxlocEQUALLOC. The variable name of the stored spatial attribute event instance is x. In addition, the child variable xloc stores the time value of the spatial attribute event instance. If the variable xloc is δxloc=LOC in the current state δloc, the value of the expression xlocEQUALLOC is the Boolean TRUE value. When the variable xloc is δxloc≠LOC in the current state δloc, the value of the expression xlocEQUALLOC is the Boolean FALSE value. The remainder of the spatial attribute value Boolean expressions have the same assignment rule as the previous inference rule.
(4)
The assignment rule of a general numerical attribute for the Boolean expression ABSEI is expressed as follows:
(33)
δ
a
x
a
>
A
x
a
>
A
,
δ
a
⟶
T
R
U
E
,
δ
a
x
a
≤
A
x
a
>
A
,
δ
a
⟶
F
A
L
S
E
,which is the assignment rule for the expression xa>A. The variable name of the stored spatial event instance is x. In addition, the child variable xa stores the number value of the spatial event instance. If the variable xa is δxa>A in the current state δa, the value of the expression xa>A is the Boolean TRUE value. When the variable xa is δxa<A in the current state δa, the value of the expression xa>A is the Boolean FALSE value. The remainder of the spatial value Boolean expressions have the same assignment rule as the previous inference rule.


## 6. STEIM Algorithm Based on Petri Net

Finite automata is a basic computer model with extremely limited storage capacity. It is a better model for small storage devices. Push-down automata (PDA) is a better model for infinite storage devices. It has an additional device stack. The stack provides additional unlimited storage, so the device is used as a “last in, first out” stack. It writes symbols on the stack, then reads and writes a symbol and “pushes down” all the other symbols in the stack. Therefore, finite automata can provide theoretical support for some limited state transformations, such as the design of automatic door controller, and push-down automata can provide context-free language recognition. They can play a role in some limited fields. But, these models have proved that some simple tasks cannot be completed, and are too limited to be used as a general model of computers. However, only by improving them on the basis of the two automata models can we get a more mature and useful automation model— the Turing machine. The Turing machine can be defined as a seven-tupleQ,Σ,Γ,δ,q0,qaccept,qreject, where Q,Σ,Γ are all finite sets. Q is a state set; Γ is an alphabet on an infinite square. Among them, the blank symbol ∈Γ; δ:Q×Γ⟶Q×Γ×L,R is the transfer function, where L and R represent their transfer direction, respectively; q0∈Q is the initial state, qaccept∈Q is the acceptance state; qreject∈Q is the rejection state, and qaccept≠qreject. A real system can be defined as a set or sum of all entities that interact and depend on each other in accordance with certain laws. The system may be natural or artificial, existing or planned for the future. Modeling of these complex systems needs to take into account the system-related factors involved in system changes, including raw materials, components, products, personnel, tools, equipment, data and information, as well as the asynchronous and parallel mode of system state changes. Turing machine is a very effective modeling tool for simple systems with serial algorithms, but it is much more difficult to apply it to complex systems. Petri net is developed from Turing machine. It provides a powerful theoretical basis and modeling tools for complex asynchronous, parallel systems, and modeling. Petri net theory was proposed by Carl A. Petri, a German scholar, in 1962. Since then, this formal description language has been widely used in many fields. Petri net is a graphical tool used to describe the behavior of complex systems. It is different from other graphical system description tools (such as flow chart, logic tree), and it can represent the parallelism, synchronization, conflict, and causal dependence in the system. Petri net is defined as a three-tuple PN=S,T;F, where elements S and T are called Place and Transition sets of PN, respectively. F is Flow-relation. It is a set of ordered pairs composed of elements S and T. The necessary and sufficient conditions are S∩T=∅; S∪T≠∅; FS×T∪T×S(× is Cartesian product); domF∪codF=S∪T, where domF=xy:x,y∈F, codF=yx:x,y∈F, which are, respectively, the definition domain and value domain of F. Automata, Turing machine, and Petri net have one thing in common: there is a state transition process within the system, which can be transformed from one state to another state, and can be expressed by state diagram and correlation matrix. Petri nets are equivalent to automation and Turing machines. Although they are equivalent, automata and Turing machines are not competent for simulating some complex systems with parallel, conflict, and synchronization. Petri nets have good simulation capabilities for these systems, and Petri net is also a good model to solve the reuse problem of software components.To use the STEIM model for temporal and spatial event-stream processing in V2X, we need to compile the statements into a corresponding executable model. According to the corresponding spatiotemporal processing model, we can design an event-stream processing algorithm and a programming implementation.A Petri net, which is also known as a place/transition (PT) net, is one of the several mathematical modeling languages for describing distributed systems. A Petri net consists of places, transitions, and arcs. Arcs run from a place to a transition or vice versa but never run between places or between transitions. The places from which an arc runs to a transition are referred to as the input places of the transition. The places to which arcs run from a transition are referred to as the output places of the transition. Graphically, places in a Petri net may contain a discrete number of marks, termed tokens. Any distribution of tokens over the places represents a net configuration, which is referred to as a “marking.” In an abstract sense, when considering a Petri net diagram, a transition in a Petri net may “fire” (execute) if it is enabled.In the event-stream processing model that is based on Petri nets, the Petri net input is indicated by the place where the event has occurred or an attribute value of one of the basic events. The output is the storage location of the database events. Each token in the place indicates whether an instance of the corresponding event is represented. When an event instance arrives, the token state in the place that represents the event will launch the transition. The transition result is calculated by calculating the transition function. When the function is satisfied, it causes the transition from the state of the input to the output until a change in the token state in the output place is detected.


### 6.1. Spatiotemporal Event Flow-Processing Algorithm

In vehicular networking, space and time are the main functions of the event-stream processing program. Based on event-stream processing, the Petri net model returns the event-stream processing results; the core algorithm is shown in this section. In this algorithm, all transitions in the input Petri net model are divided into four classes: TransitionStart, TransitionMid, TransitionParallel, and TransitionEnd. Among these classes, the function of TransitionStart is to detect the attribute value of the received event instance. The TransitionStart method from the shared place is connected to TransitionMid and TransitionParallel. The method passes information to the output place of the TransitionStart, and the TransitionMid and TransitionParallel places share the same variable. TransitionEnd is a special instance of TransitionMid for which no subsequent transition occurs.This algorithm, from TransitionStart to execution, follows a Petri net structure to TransitionEnd step by step. As the number of transitions between TransitionStart and TransitionEnd in the Petri net is limited, the algorithm can be terminated for a single event instance. In addition, the number of transitions in the Petri net model in this algorithm isn, and the time complexity of the algorithm for a single event instance is On.


### 6.2. Petri Net-Processing Model of STEIM

In the Petri net-processing model for a complex event, the input place of the Petri net indicates that the basic events and the output place of the Petri net expresses the complex events. The number of tokens in the place represents the number of event instances. When an event instance arrives, the token in the place will change. By calculating the transition function, the model can determine whether the transition conditions are satisfies. If the transition rule is satisfied, the transition will fire, and the statuses of the input and output places will change. In Figure7, the event flow transmission rates of the event flow handlers, which correspond to the four STEIM event processing statements, are set to S1,S2,S3, and S4. The processing rates of the event flow handlers are V1,V2,V3, and V4, respectively.Figure 7
The Petri net-processing model of STEIM.The service intensity of the queuing system isI=S/V, and the sufficient and necessary conditions for a stable-state distribution of the queuing system are expressed as follows:(34)I1=S1V1<1,I2=S2V2<1,I3=S3V3<1,I4=S4V4<1.According to the random Petri net of the series structure, the network delay is calculated. We assume that the delay time required forn series transitions involves n independent random variables. In addition, the parameters are the exponential distribution functions λ1,λ2,…,λn. The average delay times for n transitions are 1/λ1,1/λ2,…,1/λn. The total equivalent delay time for the n transitions is 1/λ=∑i=1n1/λn.In the same manner, the random Petri net delay method of parallel structures is calculated. We assume that the delay time required forn parallel transitions involves n independent random variables. The total equivalent delay times for n transitions is(35)1λ=∑i=1n1λn−∑i=1n−1∑j=i+1n1λi+λj+∑i=1n−2∑j=i+1n−1∑k=j+1n1λi+λj+λk+⋯+−1n−11∑i=1nλi.Figure7 shows a comparison of the event flow handler’s performance, which corresponds to the four STEIM models. The parameters for the same types of transitions are set to the same processing rate. The parameters are listed in Table 1.Table 1
How the STEIM model handles the four parameter types.
λ
1
λ
2
λ
3
λ
4
λ
5
λ
Model 1
3
6
12
20
26
1.75
Model 2
3
6
12
20
26
3.66
Model 3
3
6
12
20
26
2.58
Model 4
3
6
12
20
26
2.12The processing rate of the event flow handler isVi=λk. As the service intensity of the queuing system is Ii=Si/Vi=Si/λk, the mathematical expectation of the number of pending events in the team system is MPi=Ii/1−Ii=Si/Vi−Si. The formation system that addresses the mathematical expectation of each event’s time is MTi=1/Vi−Si. The mathematical expectation of the time spent waiting for each event to be processed in a queuing system is MWi=Ii/Vi1−Ii. The wait time ratio for each event in the queuing system is MWi/MTi=Si/λk.To analyse the dynamic performance of the instance, we construct an application scenario in which the arrival rate of event flowS changes. The processing rate of the computer is constant at k (we set k=50). The dynamic performance of the instance system is shown in Table 2.Table 2
How the STEIM model handles the four parameter types.
M
P
i
M
T
i
M
W
i
M
W
i
/
M
T
i
Model 1
S
i
/
88
−
S
i
1
/
88
−
S
i
S
i
/
7656
−
88
S
i
S
i
/
88
Model 2
S
i
/
183
−
S
i
1
/
183
−
S
i
S
i
/
33489
−
183
S
i
S
i
/
183
Model 3
S
i
/
129
−
S
i
1
/
129
−
S
i
S
i
/
16641
−
129
S
i
S
i
/
129
Model 4
S
i
/
106
−
S
i
1
/
106
−
S
i
S
i
/
11236
−
106
S
i
S
i
/
106Figures8–11 show the corresponding expected values of the processed events MP, the expected value of the residence time MT, the expected values of each event wait time MW, and an event waiting time scale drawing MW/MT.Figure 8
Expected value of processed eventM (P).Figure 9
Expected value of residence timeM (T).Figure 10
Expected value of each event wait timeM (W).Figure 11
Event waiting time scale drawing (MW/MT).When the computer processing speed is constant and the event-stream transmission rate increases, the expected system event processing slowly increases. The expected residence time of events in the system slowly increases, and the expected waiting time for each event slowly increases. As the event-stream transmission rate increases, the event waiting time ratio slowly increases. Model 1 is the most expensive model, and Model 2 involves the least amount of time spent by the four event flow handlers to process events.


## 6.1. Spatiotemporal Event Flow-Processing Algorithm

In vehicular networking, space and time are the main functions of the event-stream processing program. Based on event-stream processing, the Petri net model returns the event-stream processing results; the core algorithm is shown in this section. In this algorithm, all transitions in the input Petri net model are divided into four classes: TransitionStart, TransitionMid, TransitionParallel, and TransitionEnd. Among these classes, the function of TransitionStart is to detect the attribute value of the received event instance. The TransitionStart method from the shared place is connected to TransitionMid and TransitionParallel. The method passes information to the output place of the TransitionStart, and the TransitionMid and TransitionParallel places share the same variable. TransitionEnd is a special instance of TransitionMid for which no subsequent transition occurs.This algorithm, from TransitionStart to execution, follows a Petri net structure to TransitionEnd step by step. As the number of transitions between TransitionStart and TransitionEnd in the Petri net is limited, the algorithm can be terminated for a single event instance. In addition, the number of transitions in the Petri net model in this algorithm isn, and the time complexity of the algorithm for a single event instance is On.


## 6.2. Petri Net-Processing Model of STEIM

In the Petri net-processing model for a complex event, the input place of the Petri net indicates that the basic events and the output place of the Petri net expresses the complex events. The number of tokens in the place represents the number of event instances. When an event instance arrives, the token in the place will change. By calculating the transition function, the model can determine whether the transition conditions are satisfies. If the transition rule is satisfied, the transition will fire, and the statuses of the input and output places will change. In Figure7, the event flow transmission rates of the event flow handlers, which correspond to the four STEIM event processing statements, are set to S1,S2,S3, and S4. The processing rates of the event flow handlers are V1,V2,V3, and V4, respectively.Figure 7
The Petri net-processing model of STEIM.The service intensity of the queuing system isI=S/V, and the sufficient and necessary conditions for a stable-state distribution of the queuing system are expressed as follows:(34)I1=S1V1<1,I2=S2V2<1,I3=S3V3<1,I4=S4V4<1.According to the random Petri net of the series structure, the network delay is calculated. We assume that the delay time required forn series transitions involves n independent random variables. In addition, the parameters are the exponential distribution functions λ1,λ2,…,λn. The average delay times for n transitions are 1/λ1,1/λ2,…,1/λn. The total equivalent delay time for the n transitions is 1/λ=∑i=1n1/λn.In the same manner, the random Petri net delay method of parallel structures is calculated. We assume that the delay time required forn parallel transitions involves n independent random variables. The total equivalent delay times for n transitions is(35)1λ=∑i=1n1λn−∑i=1n−1∑j=i+1n1λi+λj+∑i=1n−2∑j=i+1n−1∑k=j+1n1λi+λj+λk+⋯+−1n−11∑i=1nλi.Figure7 shows a comparison of the event flow handler’s performance, which corresponds to the four STEIM models. The parameters for the same types of transitions are set to the same processing rate. The parameters are listed in Table 1.Table 1
How the STEIM model handles the four parameter types.
λ
1
λ
2
λ
3
λ
4
λ
5
λ
Model 1
3
6
12
20
26
1.75
Model 2
3
6
12
20
26
3.66
Model 3
3
6
12
20
26
2.58
Model 4
3
6
12
20
26
2.12The processing rate of the event flow handler isVi=λk. As the service intensity of the queuing system is Ii=Si/Vi=Si/λk, the mathematical expectation of the number of pending events in the team system is MPi=Ii/1−Ii=Si/Vi−Si. The formation system that addresses the mathematical expectation of each event’s time is MTi=1/Vi−Si. The mathematical expectation of the time spent waiting for each event to be processed in a queuing system is MWi=Ii/Vi1−Ii. The wait time ratio for each event in the queuing system is MWi/MTi=Si/λk.To analyse the dynamic performance of the instance, we construct an application scenario in which the arrival rate of event flowS changes. The processing rate of the computer is constant at k (we set k=50). The dynamic performance of the instance system is shown in Table 2.Table 2
How the STEIM model handles the four parameter types.
M
P
i
M
T
i
M
W
i
M
W
i
/
M
T
i
Model 1
S
i
/
88
−
S
i
1
/
88
−
S
i
S
i
/
7656
−
88
S
i
S
i
/
88
Model 2
S
i
/
183
−
S
i
1
/
183
−
S
i
S
i
/
33489
−
183
S
i
S
i
/
183
Model 3
S
i
/
129
−
S
i
1
/
129
−
S
i
S
i
/
16641
−
129
S
i
S
i
/
129
Model 4
S
i
/
106
−
S
i
1
/
106
−
S
i
S
i
/
11236
−
106
S
i
S
i
/
106Figures8–11 show the corresponding expected values of the processed events MP, the expected value of the residence time MT, the expected values of each event wait time MW, and an event waiting time scale drawing MW/MT.Figure 8
Expected value of processed eventM (P).Figure 9
Expected value of residence timeM (T).Figure 10
Expected value of each event wait timeM (W).Figure 11
Event waiting time scale drawing (MW/MT).When the computer processing speed is constant and the event-stream transmission rate increases, the expected system event processing slowly increases. The expected residence time of events in the system slowly increases, and the expected waiting time for each event slowly increases. As the event-stream transmission rate increases, the event waiting time ratio slowly increases. Model 1 is the most expensive model, and Model 2 involves the least amount of time spent by the four event flow handlers to process events.


## 7. Experimental Results and Analysis

To test the effectiveness of the system based on the STEIM model for V2X event-stream processing, the following discussions address two aspects: theoretical derivation and simulation example verification. The experiment results are analysed and compared.Figure12 shows the experimental and test platform of the STEIM model. On the data integration and analysis platform, the data analysis is performed on the industrial personalCcomputer (IPC) and data transmission is conducted via the LTE network.Figure 12
Experimental and test platform of the STEIM model.Figure13 shows the data test vehicle group. During the experiment, IPC was received by each device in the test vehicle on the project team. According to the output results of the STEIM model, vehicle control based on the CAN bus was performed. All tests were performed on campus and the playground.Figure 13
Data test vehicle group of the STEIM model.


### 7.1. Experimental Design

In V2X, a vehicle with an identifier of “11109” generates a spatiotemporal event instance every 1 s during the driving process. The values for the set of time event variables forVehicle include the Car logo for VehicleID, additional variables, event instance time attribute values of variables for VehicleTime, the event instance space attribute values of variables for VehicleLoc, and the event instance speed values of variables for VehicleV:(36)Vehicle=VehicleID,VehicleTime,VehicleLoc,VehicleV.The temporal and spatial event instance in the instance flow of temporal and spatial events is recorded asEI. Table 2 lists the values of a spatial and temporal event stream.Four users (User1,User2,User3, and User4) in V2X that are monitoring the vehicle, respectively. As these users are concerned with different events, they use the following four STEIM statements, which are referred to as EventInstence, to process the spatiotemporal event flow generated by the vehicle. Two spatial data sets are established:(37)ROAD32=998,55,998,56,…,998,150,ROAD65=122,90,122,91,…,122,180.The STEIM statement of vehicleUser1 is EventInstence1:(38)VehicleID=965VehicleTimeDURING20:20:00,20:23:00VehicleLocINROAD32VehicleV>60.The STEIM statement of vehicleUser2 is EventInstence2:(39)VehicleID=965VehicleTimeDURING20:30:00,20:33:00VehicleLocINROAD32VehicleV<90.The STEIM statement of vehicleUser3 is EventInstence3:(40)VehicleID=965VehicleTimeDURINGmx20:40:00,20:43:00VehicleLocINROAD65VehicleV>70.The STEIM statement of vehicleUser4 is EventInstence4:(41)VehicleID=965VehicleTimeDURING20:50:00,20:53:00VehicleLocINROAD65VehicleV<90.


### 7.2. Theoretical Derivation Process and Result

According to the operational semantics of the STEIM model, the results of the four STEIM statements are listed in Table3.Table 3
Values of a spatial and temporal event stream.
V
e
h
i
c
l
e
V
e
h
i
c
l
e
I
D
V
e
h
i
c
l
e
T
i
m
e
V
e
h
i
c
l
e
L
o
c
V
e
h
i
c
l
e
V
V
E
1
11109
(20 : 20 : 20, 20 : 20 : 30)
(998, 120)
63.5
V
E
2
11109
(20 : 20 : 30, 20 : 20 : 40)
(998, 121)
69.8
V
E
3
11109
(20 : 20 : 40, 20 : 20 : 50)
(998, 122)
72.7
V
E
4
11109
(20 : 20 : 50, 20 : 21 : 00)
(998, 123)
85.3
V
E
5
11109
(20 : 21 : 00, 20 : 21 : 20)
(998, 124)
77.0
V
E
6
11109
(20 : 21 : 20, 20 : 21 : 30)
(998, 125)
71.9
V
E
7
11109
(20 : 21 : 30, 20 : 21 : 40)
(998, 126)
68.3Two examples are selected to illustrate the derivation process.Formula derivation 1:User2′s event processing statement EventInstence2 handles the processing of the time event instance EI2 as follows.The current temporal and spatial event instance isEI2. In the current on-board computer system, the state of the temporal and spatial event variable is δ2. User2′s client event library status is ΣB2. The values of each subvariable in state δ2 are listed as follows: VehicleID is 965; VehicleTime is (20 : 20 : 50, 20 : 21 : 00); VehicleLoc is (998, 123); and VehicleV is 85.3. The following logical process is conducted:(42)δ2VehicleID=965VehicleID=965,δ2⟶TRUE⟹VehicleID=965,δ2:ΣB2⟶ΣB2∪δ2δ2VehicleTime.end<20:20:50VehicleTimeDURING20:20:50,20:21:00,δ2⟶FALSE⟹VehicleTimeDURING20:20:50,20:21:00,δ2:ΣB2⟶ΣB2δ2VehicleLoc⊂ROAD47VehicleLocINROAD32,δ2⟶TRUE⟹VehicleLocINROAD32,δ2:ΣB2⟶ΣB2∪δ2δ2VehicleV<90VehicleV<90,δ2⟶TURE⟹VehicleV<90,δ2:ΣB2⟶ΣB2∪δ2VehicleID=965VehicleTimeDURING20:20:50,20:21:00VehicleLocINROAD32VehicleV<90,δ2:ΣB2⟶ΣB2.This derivation, the spatiotemporal event instanceEI2 time attribute value does not satisfy the event-processing statement EventInstence2 time expression. Thus, in the EventInstence2 calculation results of the on-board computer system, the spatial and temporal event variable for each attribute variable (VehicleID,VehicleTime,VehicleLoc, and VehicleV) value is empty, and User2 client’s event library remains unchanged.Formula derivation 2:User4's event processing statement EventInstence4 handles the processing of the time event instance EI4 as follows.The current temporal and spatial event instance isEI4, and in the current on-board computer system, the state of the temporal and spatial event variable is δ4. Vehicle User4's client event library status is ΣB4. The values of each subvariable in state δ4 are as follows: VehicleID is 965, VehicleTime is (20 : 20 : 50, 20 : 21 : 00), VehicleLoc is (998, 123), and VehicleV is 85.3, and the following logical process is conducted:(43)δ4VehicleID=965VehicleID=965,δ4⟶TRUE⟹VehicleID=965,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleTime.start>20:20:50andδ4VehicleTime⋅end<20:21:00VehicleTimeDURING20:20:50,20:21:00,δ4⟶TRUE⟹VehicleTimeDURING20:20:50,20:21:00,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleLoc⊂ROAD65VehicleLocINROAD65,δ4⟶TRUEtitletarrowVehicleLocINROAD65,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleV<90VehicleV<90,δ4⟶TURE⟹VehicleV<90,δ4:ΣB4⟶ΣB4∪δ4VehicleID=965VehicleTimeDURING20:20:50,20:21:00VehicleLocINROAD65VehicleV<90δ4:ΣB4⟶ΣB4∪δ4,.As shown by this derivation, the spatiotemporal event instanceEI4 time attribute values satisfy the event-processing statement EventInstence4 time expression. Thus, in the EventInstence4 calculation results of the on-board computer system, the spatial and temporal event variable for attribute variable (VehicleID,VehicleTime,VehicleLoc, and VehicleV) value is empty. Thus, vehicle User4 client’s event library remains unchanged.Based on the corresponding operational semantics, other STEIM statements are similar to the reasoning process of the five temporal and spatial event instances listed in Table3. The set of four user events store the initial state of ΣB1,ΣB2,ΣB3, and ΣB4. Using the spatiotemporal event instance flow theory in Table 3, the results shown in Table 4 are obtained.Table 4
Reasoning results of example.
UserName
UserEventBase
U
s
e
r
1
Σ
B
1
∪
δ
2
∪
δ
3
∪
δ
4
U
s
e
r
2
Σ
B
2
U
s
e
r
3
Σ
B
3
U
s
e
r
4
Σ
B
1
∪
δ
1
∪
δ
2
∪
δ
6
∪
δ
7
This theoretical derivation and derivation indicate that the operational semantics of the STEIM language are effective.


### 7.3. Performance Analysis

We run experiments in the proposed scheme in terms of computation costs of the RSU and the vehicles and communication overhead of the RSU and the vehicles. The experimental hardware includes an Intel Core i7-7900 processor with a 3.60 GHz clock frequency and 64 GB of memory. The performance results of the proposed scheme and the relevant models are shown in Table5.Table 5
Performance analysis.
Dimension of data report
STEIM
The scheme proposed in [22]
Traditional scheme
Computational cost of a vehicle during data collection
10
976
700
10
20
1864
1450
28
30
2832
2220
41
40
3657
2955
58
Computational cost of an RSU during data acquisition
10
621
411
12
20
1076
825
32
30
1571
1175
45
40
2113
1586
58In Figure14, we plot and compare the computation cost of the vehicle in terms of the data dimension, which ranges from 5 to 40, during the data collection phase. Meanwhile, in Figure 15, we plot and compare the computation cost of RSU in the three schemes in terms of the data dimension that ranges from 5 to 40, during the data acquisition phase. The comparison results show that compared with the [22] scheme and traditional scheme, STEIM can greatly reduce the computation complexity of the involved entities.Figure 14
Computational cost of a vehicle during data collection.Figure 15
Computational cost of an RSU during data acquisition.


### 7.4. Simulation Results and Analysis

Based on the operational semantics of the STEIM model and the spatiotemporal event flow processing (Algorithm1), which are based on a Petri net, the following experiment is performed. First, we implemented the STEIM model compiler using the open source tool ANTLRWorks 1.5. ANTLER is a for language recognition that provides a framework for constructing recognisers, interpreters, compilers, and translators from grammatical descriptions that contain actions in a variety of target languages. The experimental hardware includes an Intel Core i7-4790 processor with a 3.60 GHz clock frequency and 32 GB of memory. Figure 16 shows the syntax of the STEIM model based on the ANTLRWorks tool.Algorithm 1: Based on the Petri Net Model of Event Flow-Processing Algorithm.
Input: temporal and spatial event flow, STEIM statement Petri net model
Output: an event instance that satisfies the STEIM statement condition
(1)
while TRUE do
(2)
Event⟵ it is an instance of an Event that the current pointer points to.
for each Event.Attribute do
(3)
TransitionStart.InputToken⟵ Event.Attribute;
(4)
end
(5)
for each TransitionStart do
(6)
if InputToken satisfies Guard then
(7)
OutputToken⟵ InputToken;
(8)
else
(9)
Clear the Event value, Event pointer ++;
(10)
end
(11)
end
(12)
for each TransitionMid do
(13)
if TransitionMid.InputToken satisfies Guard then
(14)
OutputToken⟵ OutputToken ⊙ InputToken;
(15)
else
(16)
Clear the Event value, Event pointer ++;
(17)
end
(18)
end
(19)
for each TransitionParallel do
(20)
if TransitionParallel.InputToken satisfies Guard
then
(21)
OutputToken⟵ OutputToken ∪ InputToken;
(22)
else
(23)
Clear the Event value, Event pointer ++;
(24)
end
(25)
end
(26)
for each TransitionEnd do
(27)
if TransitionEnd.InputToken satisfies Guard then
(28)
OutputToken⟵ OutputToken ⊙ InputToken;
return OutputToken;
(29)
else
(30)
Clear the Event value, Event pointer ++;
(31)
end
(32)
end
(33)
Clear the Event value, Event pointer ++;
(34)
endFigure 16
Syntax of STEIM model based on the ANTLRWorks tool.In the simulation experiment, a STEIM statement is entered into the event editor interface, and a unique number is set for each STEIM statement. The statement is activated, and the number of events represented by the STEIM statement is displayed in the event query result list. The user can select the number of events to obtain a detailed listing of the events in the event query result details.The initial state of the event library with 4 users is an empty set. The simulation results of the spatiotemporal event instance flow listed in Table3 are shown in Table 6.Table 6
Example simulation results.
UserName
UserEventBase
U
s
e
r
1
V
E
2
+
V
E
3
+
V
E
4
U
s
e
r
2
∅
U
s
e
r
3
∅
U
s
e
r
4
V
E
1
+
V
E
2
+
V
E
6
+
V
E
7As shown in Table6, the spatiotemporal event flow algorithm based on a Petri net is effective. A comparison of the results of Tables 4 and 6 reveals that the results after theoretically deriving the STEIM operation semantics of the model and the experimental results from the simulation program using the structure shown in Algorithm 1 are consistent and support each other. These results demonstrate that processing a vehicular networking spatiotemporal event stream based on the STEIM model proposed in this paper is effective.


## 7.1. Experimental Design

In V2X, a vehicle with an identifier of “11109” generates a spatiotemporal event instance every 1 s during the driving process. The values for the set of time event variables forVehicle include the Car logo for VehicleID, additional variables, event instance time attribute values of variables for VehicleTime, the event instance space attribute values of variables for VehicleLoc, and the event instance speed values of variables for VehicleV:(36)Vehicle=VehicleID,VehicleTime,VehicleLoc,VehicleV.The temporal and spatial event instance in the instance flow of temporal and spatial events is recorded asEI. Table 2 lists the values of a spatial and temporal event stream.Four users (User1,User2,User3, and User4) in V2X that are monitoring the vehicle, respectively. As these users are concerned with different events, they use the following four STEIM statements, which are referred to as EventInstence, to process the spatiotemporal event flow generated by the vehicle. Two spatial data sets are established:(37)ROAD32=998,55,998,56,…,998,150,ROAD65=122,90,122,91,…,122,180.The STEIM statement of vehicleUser1 is EventInstence1:(38)VehicleID=965VehicleTimeDURING20:20:00,20:23:00VehicleLocINROAD32VehicleV>60.The STEIM statement of vehicleUser2 is EventInstence2:(39)VehicleID=965VehicleTimeDURING20:30:00,20:33:00VehicleLocINROAD32VehicleV<90.The STEIM statement of vehicleUser3 is EventInstence3:(40)VehicleID=965VehicleTimeDURINGmx20:40:00,20:43:00VehicleLocINROAD65VehicleV>70.The STEIM statement of vehicleUser4 is EventInstence4:(41)VehicleID=965VehicleTimeDURING20:50:00,20:53:00VehicleLocINROAD65VehicleV<90.


## 7.2. Theoretical Derivation Process and Result

According to the operational semantics of the STEIM model, the results of the four STEIM statements are listed in Table3.Table 3
Values of a spatial and temporal event stream.
V
e
h
i
c
l
e
V
e
h
i
c
l
e
I
D
V
e
h
i
c
l
e
T
i
m
e
V
e
h
i
c
l
e
L
o
c
V
e
h
i
c
l
e
V
V
E
1
11109
(20 : 20 : 20, 20 : 20 : 30)
(998, 120)
63.5
V
E
2
11109
(20 : 20 : 30, 20 : 20 : 40)
(998, 121)
69.8
V
E
3
11109
(20 : 20 : 40, 20 : 20 : 50)
(998, 122)
72.7
V
E
4
11109
(20 : 20 : 50, 20 : 21 : 00)
(998, 123)
85.3
V
E
5
11109
(20 : 21 : 00, 20 : 21 : 20)
(998, 124)
77.0
V
E
6
11109
(20 : 21 : 20, 20 : 21 : 30)
(998, 125)
71.9
V
E
7
11109
(20 : 21 : 30, 20 : 21 : 40)
(998, 126)
68.3Two examples are selected to illustrate the derivation process.Formula derivation 1:User2′s event processing statement EventInstence2 handles the processing of the time event instance EI2 as follows.The current temporal and spatial event instance isEI2. In the current on-board computer system, the state of the temporal and spatial event variable is δ2. User2′s client event library status is ΣB2. The values of each subvariable in state δ2 are listed as follows: VehicleID is 965; VehicleTime is (20 : 20 : 50, 20 : 21 : 00); VehicleLoc is (998, 123); and VehicleV is 85.3. The following logical process is conducted:(42)δ2VehicleID=965VehicleID=965,δ2⟶TRUE⟹VehicleID=965,δ2:ΣB2⟶ΣB2∪δ2δ2VehicleTime.end<20:20:50VehicleTimeDURING20:20:50,20:21:00,δ2⟶FALSE⟹VehicleTimeDURING20:20:50,20:21:00,δ2:ΣB2⟶ΣB2δ2VehicleLoc⊂ROAD47VehicleLocINROAD32,δ2⟶TRUE⟹VehicleLocINROAD32,δ2:ΣB2⟶ΣB2∪δ2δ2VehicleV<90VehicleV<90,δ2⟶TURE⟹VehicleV<90,δ2:ΣB2⟶ΣB2∪δ2VehicleID=965VehicleTimeDURING20:20:50,20:21:00VehicleLocINROAD32VehicleV<90,δ2:ΣB2⟶ΣB2.This derivation, the spatiotemporal event instanceEI2 time attribute value does not satisfy the event-processing statement EventInstence2 time expression. Thus, in the EventInstence2 calculation results of the on-board computer system, the spatial and temporal event variable for each attribute variable (VehicleID,VehicleTime,VehicleLoc, and VehicleV) value is empty, and User2 client’s event library remains unchanged.Formula derivation 2:User4's event processing statement EventInstence4 handles the processing of the time event instance EI4 as follows.The current temporal and spatial event instance isEI4, and in the current on-board computer system, the state of the temporal and spatial event variable is δ4. Vehicle User4's client event library status is ΣB4. The values of each subvariable in state δ4 are as follows: VehicleID is 965, VehicleTime is (20 : 20 : 50, 20 : 21 : 00), VehicleLoc is (998, 123), and VehicleV is 85.3, and the following logical process is conducted:(43)δ4VehicleID=965VehicleID=965,δ4⟶TRUE⟹VehicleID=965,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleTime.start>20:20:50andδ4VehicleTime⋅end<20:21:00VehicleTimeDURING20:20:50,20:21:00,δ4⟶TRUE⟹VehicleTimeDURING20:20:50,20:21:00,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleLoc⊂ROAD65VehicleLocINROAD65,δ4⟶TRUEtitletarrowVehicleLocINROAD65,δ4:ΣB4⟶ΣB4∪δ4δ4VehicleV<90VehicleV<90,δ4⟶TURE⟹VehicleV<90,δ4:ΣB4⟶ΣB4∪δ4VehicleID=965VehicleTimeDURING20:20:50,20:21:00VehicleLocINROAD65VehicleV<90δ4:ΣB4⟶ΣB4∪δ4,.As shown by this derivation, the spatiotemporal event instanceEI4 time attribute values satisfy the event-processing statement EventInstence4 time expression. Thus, in the EventInstence4 calculation results of the on-board computer system, the spatial and temporal event variable for attribute variable (VehicleID,VehicleTime,VehicleLoc, and VehicleV) value is empty. Thus, vehicle User4 client’s event library remains unchanged.Based on the corresponding operational semantics, other STEIM statements are similar to the reasoning process of the five temporal and spatial event instances listed in Table3. The set of four user events store the initial state of ΣB1,ΣB2,ΣB3, and ΣB4. Using the spatiotemporal event instance flow theory in Table 3, the results shown in Table 4 are obtained.Table 4
Reasoning results of example.
UserName
UserEventBase
U
s
e
r
1
Σ
B
1
∪
δ
2
∪
δ
3
∪
δ
4
U
s
e
r
2
Σ
B
2
U
s
e
r
3
Σ
B
3
U
s
e
r
4
Σ
B
1
∪
δ
1
∪
δ
2
∪
δ
6
∪
δ
7
This theoretical derivation and derivation indicate that the operational semantics of the STEIM language are effective.


## 7.3. Performance Analysis

We run experiments in the proposed scheme in terms of computation costs of the RSU and the vehicles and communication overhead of the RSU and the vehicles. The experimental hardware includes an Intel Core i7-7900 processor with a 3.60 GHz clock frequency and 64 GB of memory. The performance results of the proposed scheme and the relevant models are shown in Table5.Table 5
Performance analysis.
Dimension of data report
STEIM
The scheme proposed in [22]
Traditional scheme
Computational cost of a vehicle during data collection
10
976
700
10
20
1864
1450
28
30
2832
2220
41
40
3657
2955
58
Computational cost of an RSU during data acquisition
10
621
411
12
20
1076
825
32
30
1571
1175
45
40
2113
1586
58In Figure14, we plot and compare the computation cost of the vehicle in terms of the data dimension, which ranges from 5 to 40, during the data collection phase. Meanwhile, in Figure 15, we plot and compare the computation cost of RSU in the three schemes in terms of the data dimension that ranges from 5 to 40, during the data acquisition phase. The comparison results show that compared with the [22] scheme and traditional scheme, STEIM can greatly reduce the computation complexity of the involved entities.Figure 14
Computational cost of a vehicle during data collection.Figure 15
Computational cost of an RSU during data acquisition.


## 7.4. Simulation Results and Analysis

Based on the operational semantics of the STEIM model and the spatiotemporal event flow processing (Algorithm1), which are based on a Petri net, the following experiment is performed. First, we implemented the STEIM model compiler using the open source tool ANTLRWorks 1.5. ANTLER is a for language recognition that provides a framework for constructing recognisers, interpreters, compilers, and translators from grammatical descriptions that contain actions in a variety of target languages. The experimental hardware includes an Intel Core i7-4790 processor with a 3.60 GHz clock frequency and 32 GB of memory. Figure 16 shows the syntax of the STEIM model based on the ANTLRWorks tool.Algorithm 1: Based on the Petri Net Model of Event Flow-Processing Algorithm.
Input: temporal and spatial event flow, STEIM statement Petri net model
Output: an event instance that satisfies the STEIM statement condition
(1)
while TRUE do
(2)
Event⟵ it is an instance of an Event that the current pointer points to.
for each Event.Attribute do
(3)
TransitionStart.InputToken⟵ Event.Attribute;
(4)
end
(5)
for each TransitionStart do
(6)
if InputToken satisfies Guard then
(7)
OutputToken⟵ InputToken;
(8)
else
(9)
Clear the Event value, Event pointer ++;
(10)
end
(11)
end
(12)
for each TransitionMid do
(13)
if TransitionMid.InputToken satisfies Guard then
(14)
OutputToken⟵ OutputToken ⊙ InputToken;
(15)
else
(16)
Clear the Event value, Event pointer ++;
(17)
end
(18)
end
(19)
for each TransitionParallel do
(20)
if TransitionParallel.InputToken satisfies Guard
then
(21)
OutputToken⟵ OutputToken ∪ InputToken;
(22)
else
(23)
Clear the Event value, Event pointer ++;
(24)
end
(25)
end
(26)
for each TransitionEnd do
(27)
if TransitionEnd.InputToken satisfies Guard then
(28)
OutputToken⟵ OutputToken ⊙ InputToken;
return OutputToken;
(29)
else
(30)
Clear the Event value, Event pointer ++;
(31)
end
(32)
end
(33)
Clear the Event value, Event pointer ++;
(34)
endFigure 16
Syntax of STEIM model based on the ANTLRWorks tool.In the simulation experiment, a STEIM statement is entered into the event editor interface, and a unique number is set for each STEIM statement. The statement is activated, and the number of events represented by the STEIM statement is displayed in the event query result list. The user can select the number of events to obtain a detailed listing of the events in the event query result details.The initial state of the event library with 4 users is an empty set. The simulation results of the spatiotemporal event instance flow listed in Table3 are shown in Table 6.Table 6
Example simulation results.
UserName
UserEventBase
U
s
e
r
1
V
E
2
+
V
E
3
+
V
E
4
U
s
e
r
2
∅
U
s
e
r
3
∅
U
s
e
r
4
V
E
1
+
V
E
2
+
V
E
6
+
V
E
7As shown in Table6, the spatiotemporal event flow algorithm based on a Petri net is effective. A comparison of the results of Tables 4 and 6 reveals that the results after theoretically deriving the STEIM operation semantics of the model and the experimental results from the simulation program using the structure shown in Algorithm 1 are consistent and support each other. These results demonstrate that processing a vehicular networking spatiotemporal event stream based on the STEIM model proposed in this paper is effective.


## 8. Conclusion

In this paper, we propose the spatiotemporal operator and the complete grammar of STEIM. This approach effectively expresses the spatiotemporal information of the spatiotemporal event flow in V2X. The formal semantics of the STEIM model is used to design the operational semantics. In addition, we provide a spatiotemporal event-stream processing algorithm that is based on a Petri net model. This algorithm establishes a working mechanism for processing the V2X event-temporal and spatial event stream. In addition, we demonstrate the effectiveness of the system based on STEIM via experiments. Future work should consider protecting the security of information and ensuring the reliable transmission of event streams. As the scale of event flows in V2X increases, conducting distributed event flow processing in vehicular network environments requires further study.



---

*Source: 1375426-2020-02-10.xml*