1 Introduction
-
Cooperative Awareness Messages (CAM) provide high frequency status updates of a vehicle’s position, speed, vehicle type, etc.;
-
Map Data Messages (MAP) describe the detailed topology of an intersection, including its lanes and their connections;
-
Signal Phase and Timing Messages (SPaT) give the projected signal phases (e.g., green) for each lane; and
-
Decentralized Environmental Notification Messages (DENM) in
-
Part-Whole relations, e.g., a traffic light is part of an intersection;
-
Spatial relations, e.g., a car is crossing a stop lane that is within an intersection;
-
Connectivity, e.g., one intersection is connected to another intersections via a road;
-
Functionality, e.g., if two objects have the same identifier (ID), they are the same.
-
World Model: our notion of a world model is captured by an LDM ontology, which is based on the W3C standard OWL [31] and simply modifiable and extendable. Extensions can be made without altering the database and its relational schema.
-
Model Properties: the formal models of an ontology and the data have defined properties, which can be used for verification, simplification, and optimization on the conceptual level. For instance, by defining constraints in the ontology, inconsistencies in the data can be found; e.g., by stating disjointness of the concepts car and bicycle, that a an object can not be both a car and a bicycle.
-
Inference: OBDA allows us to infer new information at query time (e.g., class hierarchies), which reveals implicit information and keeps the amount of stored data small.
-
Expressive Queries: the queries are posed through the ontology extending the vocabulary beyond database relations. The query language of conjunctive queries1 (CQ) is simple and yet powerful. Furthermore, by examining the structure of the ontology, we can obtain meaningful combinations of query atoms, which aid in building and validating user queries.
-
Modeling: besides the mentioned ETSI/ISO standards, mobility vocabularies are defined in Schema.org and Mobivoc.2 Yet, there are no comprehensive ontologies available that allow to capture an LDM and related V2X messages. The latter are standardized and thoroughly specified, but based on a different (modeling) language, namely the Abstract Syntax Notation One (ASN.1). The specifications of V2X messages in ASN.1 are tree-like and must be converted into triples of an RDF-graph, as needed by the ontology standards in the Semantic Web.
-
Integration and Annotation: after the conversions to triples is completed, the V2X messages and the GIS database have to be mapped to the given vocabulary of the ontology. Due to the tree-like structure of the messages, not all relations between objects are available, hence we need to calculate the missing relations, e.g., spatial relations. The integration and annotation steps have to handle static and streaming data in a uniform way and should be easily extendable and maintainable.
-
Stream query answering: the combination of the methods and respective techniques for query answering (QA) over streams are challenging regarding performance and scalability. With OBDA, there is a trend to lightweight query answering over ontologies; we thus can benefit from recent results which improve performance and scalability (cf. [15, 40]). On the other hand, for query evaluation on stream database systems such as PipelineDB3, most implementations are designed toward efficiency, but not for complex query evaluation using ontologies and/or geospatial data; both aspects add complexity and diminish scalability.
2 State-of-the-art of the LDM
-
Database-centric: besides DynaMap, all other efforts have a database-centric model of the LDM using a static schema, where the LDM objects are directly mapped to relational tables. New types of objects need a modification of the schema, which makes it harder to add new domains, e.g., traffic regulations. Furthermore, the database schema cannot simply capture and query class hierarchies and the dependencies between the different objects as it is not graph-based.
-
Stream processing: except DynaMap, other efforts are designed to work on top of a GIS database (e.g., PostGIS) and neglect the streaming nature of the LDM data, since it should allow for real-time queries over large amounts of data “in-stream”, i.e., without storing. Stream processing needs a clear data model (e.g., a point-based model) and a defined query language that supports window operators (e.g., having sliding windows), stream joins, and aggregation over streams (e.g., average speed over 30 s). These features are either entirely missing or only considered in external components.
-
Sound integration: the integration of all layers and the model of a complex intersection could lead to incomplete or inconsistent data. A MAP message allows integrity constrains to check for wrongly connected lanes. However they are only implicit in the database definitions and do not cover for all possible integrity cases (e.g., disjointness between classes).
3 Background Technology and Methods
-
Class assertions 〈id1 typeClass〉: states object id1 is of type Class, e.g., Vehicle;
-
Object property assertions 〈id1 property1id2〉: states object id1 is related by property1 to object id2, e.g., 〈lane1 isPartOf intersection2〉;
-
Data property assertions 〈id1 property2value〉: states object id1 has a property2 with a numeric value, e.g., 〈car1 hasSpeed 20〉.
4 Architecture of a Semantically Enriched LDM
-
V2XFeature is the spatial representation of V2X objects;
-
GeoFeature represents the GIS aspects of the LDM including POIs and the road networks;
-
Geometry is the geometrical representation of features;
-
Actor is an individual actor involved in a transport scene;
-
Event describes events that happen in a transport scene;
-
CategoricalValues such as allowed maneuvers or vehicle roles (e.g., emergency vehicle).
-
properties for partonomies, e.g., isPartOf;
-
spatial relations, e.g., intersects;
-
connectivity, e.g., connected; and
-
standard properties, e.g., isAllowed, hasRole, isManaged, or positions.
-
(i) 〈A,F,SA,SF〉 as a “universal” database, which allows for streamed and spatial data;
-
(ii) A,F, 〈SA,SF〉 as a normal database for A, a stream database for F, and a spatial database which allows for time stamps;
-
(iii) A,SA, 〈F,SF〉 as a normal database for A, a spatial database for SA, and a stream database with limited support for spatial data;
-
(iv) A,F,SA,SF as separate databases that are only connected by query atoms at query time.
5 Query Answering over Streams
-
Vehicle(y) and isManaged(x,z) are ontology atoms, which have to be unfolded with respect to the ITS domain that is modeled in the LDM ontology;
-
intersects(u,v) and hasLocation(x,u) are spatial atoms, where the first checks spatial intersection and the second the assignment of geometries to objects;
-
speed[avg,4s](y,v) resp. pos[line,4s](y,r) defines a window operator that aggregates the average speed resp. positions (as points) of the vehicles over the streams speed and pos; hasState[first,−4s](z,Stop) gives us the traffic lights, which switch in 4s to the state “Stop”.
-
each \(Q_{O_{i}}(\mathbf {x},\mathbf {y})\) has the form A(z) or P(z,z′), where A is a class name, P is a property name of the LDM ontology, and z,z′ are from x ∪y;
-
each atom \(Q_{S_{j}}(\mathbf {x},\mathbf {y})\) is from the vocabulary of spatial relations and of the form S(z,z′), where z,z′ is as before and S is one of the following spatial relation rel ∈{intersects,contains,nextTo, equals,inside,disjoint,outside};
-
\(Q_{F_{j}}(\mathbf {x},\mathbf {y})\) is similar to \(Q_{O_{i}}(\mathbf {x},\mathbf {y})\) but adds the vocabulary for stream operators, which are taken from [8] and relate to CQL operators [3]. We have a window [agr,l] over a stream Fj, where l is the window size in time units (positive for past, or negative for future). The aggregate functionagr ∈{count,sum,first,…} (see below for details) is applied to the data items in the window:12
-
[agr,l]: represents the aggregate of last or next l time units of stream Fj;
-
[l]: represents the single tuple of Fj at index l with l = 0 if it is the current tuple;
-
[agr,b,e]: represents the aggregate on a window between b and e in the past/future of a stream. This extension is inspired by [12] and allows to query historic data (e.g., logs), if they are stored as streams.
-
-
point: we evaluate last to get the last available position p1;
-
line: we create p = (p1,…,pn), where p1≠pn and determine a total order on the bag of points, such that we have a starting point using last and iterate backwards finding the next point by Euclidean distance;
-
line_angle: this aggregate function determines angles (in degrees) in a geometry by (1) applying the function line, (2) obtaining a simplified geometry using smoothing, and (3) calculating the angles between the lines of the simplified geometry.
-
polygon: similar to line, but we create a polygon (p1,…,pn), where p1 = pn by: (1) determining the convex hull of the bag of points, and (2) extracting all pairs of points representing the convex hull;
-
trajectory: The simplest approach to calculate a trajectory is by using the function line. However, this is often not sufficient, and more complex smoothing and map matching functions might be needed. For the prediction of the future paths, we allow different projections such a linear or curvature-based models. As additional information, we need to include the maximal distance and step size for each time point, where the current speed could be taken as simple approximation. Also more elaborate models using velocity profiles could be applied.
6 Application Scenarios
7 Implementation and Experiments
/* S1: cars with brands, traveling above 30km/h */ | |
q1 : | |
/* S1: lanes and signal groups switched to red */ | |
q2 : | |
/* S1: vehicles on incoming lanes */ | |
q3 : | |
/* S2: vehicles with crossed paths */ | |
q4 : | |
/* S2: vehicles traveling above 30km/h heading straight */ | |
q5 : _ | |
/* S2: detection of red-light violation */ | |
q6 : Taken from Ex. 9 | |
/* Synthetic: testing many ontology atoms */ | |
\( \small \begin {array}{ll} \mathtt {q_{7}(x,z)}: &\mathtt {LaneIn(x), isPartof(x,u), Intersection(u), u = "I1", hasSignal(x,y),}\\ & \mathtt { SignalGroup(y), signalState(y,r)[last,15], r = "R", connect(x,q), connect(q,v),}\\ & \mathtt { Lane(v), hasSignal(v,z), SignalGroup(z),signalState(z,s)[last,15], s = "R"} \end {array} \)
| |
/* Synthetic: testing many spatial atoms */ | |
\( \small \begin {array}{ll} \mathtt {q_{8}(x,y)}:&\mathtt {Vehicle(x), pos(x,y)[line,20], intersects(y,u), LaneIn(r), hasGeo(r,u),}\\ & \mathtt { intersects(y,v), LaneIn(s), hasGeo(s,v), intersects(y,w), LaneIn(t),}\\ & \mathtt { hasGeo(t,w), within(y,z), hasGeo(q,z), Intersection(q)} \end {array} \)
| |
/* Synthetic: testing many stream atoms */ | |
\( \small \begin {array}{ll} \mathtt {q_{9}(x,q,r,s,t,u)}:&\mathtt {Vehicle(x), speed(x,q)[avg,1], speed(x,r)[avg,5], speed(x,s)[avg,10],}\\ &\mathtt {speed(x,t)[avg,25], speed(x,u)[avg,50]} \end {array} \)
|
Type |
#
Q
|
#
A
| (a)t with # vehicles | (b) t with ms sim. delay | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
10 | 100 | 500 | 1000 | 2500 | 5000 | 0 | 100 | 250 | 500 | ||||
q
1
| O,F | 1 | 1 | 0.85 | 0.82 | 0.91 | 1.05 | 1.22 | 1.58 | 0.78 | 0.74 | 0.73 | 0.71 |
q
2
| O,F∗ | 1 | 6 | 0.83 | 0.83 | 0.83 | 0.83 | 0.83 | 0.83 | 0.77 | 0.77 | 0.72 | 0.71 |
q
3
| O,S,F | 3 | 23 | 0.89 | 0.87 | 1.00 | 1.25 | 1.39 | 1.74 | 0.83 | 0.81 | 0.77 | 0.75 |
q
4
| O,S,F | 3 | 22 | 1.10 | 1.09 | 1.24 | 1.53 | 1.81 | 2.32 | 1.02 | 1.00 | 0.95 | 0.93 |
q
5
| O,S,F | 3 | 42 | 1.11 | 1.10 | 1.26 | 1.39 | 1.90 | 1.92 | 1.05 | 1.00 | 0.98 | 0.96 |
q
6
| O,S,F | 7 | 52 | 1.39 | 1.39 | 1.49 | 1.69 | 2.36 | 2.28 | 1.40 | 1.28 | 1.26 | 1.25 |
q
7
| O,F∗ | 6 | 69 | 1.16 | 1.16 | 1.16 | 1.16 | 1.16 | 1.16 | 1.15 | 1.12 | 1.11 | 1.09 |
q
8
| O,S | 9 | 73 | 0.92 | 0.94 | 1.30 | 1.43 | 1.72 | 2.19 | 0.99 | 0.98 | 0.92 | 0.91 |
q
9
| O,F | 9 | 105 | 1.67 | 1.73 | 1.99 | 2.06 | 2.49 | 2.97 | 1.71 | 1.68 | 1.66 | 1.63 |