Keywords

1 Introduction

Nowadays, with the use of new information and communication technologies in smart cities, big quantity of data about human mobility and its environment is provided. These data concern mobile's location and data associated to a smart city environment (date, weather, means of transportation…). Human mobility data are exploited to accomplish several tasks such as mobility prediction, which became a challenging problem, and therefore has an important role in smart cities. Indeed, to enhance the daily life of mobile citizens, mobility prediction is used in several domains such as mobile communication, intelligent transportation, and location-based service recommendation. In this perspective, a context-based mobility prediction approach is highly desirable.

According to the use of mobility traces, we distinguish two types of mobility predic-tion models: historical-based models [1] and knowledge-based models [2].

Moreover, to achieve better mobility prediction results, two main challenges are considered: mobility modeling that refers to the identification, representation and integration of all data required for prediction; and prediction process that defines steps, techniques and algorithms used for prediction.

Trajectory modeling of a mobile object requires data related to its different positions over time (GPS coordinates, date, direction…). Other contextual data of the object's movements are also essential (Our reference, 2020), since they can influence mobility.

The set-up of a trajectory description technique, which aims to define the main items constituting the trajectory, is the base for trajectory modeling. Many trajectory descrip-tion techniques have been proposed in the literature. For example, trajectory is described in terms of places [3] (e.g., cities, streets…), in terms of landmarks [4], etc. These techniques suffer from low accuracy or erroneous description of the trajectory.

In this paper, we focus on the trajectory modeling challenge and propose a conceptual trajectory model for mobility prediction which considers four main context parameters: time, weather, means of displacements and road traffic. Our model allows: i) the representation and the integration of data based on the technique of the grid for a trajectory description; and ii) the storage of data in a database for further analyses and visualization.

The rest of this paper is organized as follows: Sect. 2 focuses on related works of trajectory modelling. Section 3 describes our mobility prediction approach and emphasizes our trajectory model. Section 4 shows the use of our model in a specific domain and exposes an evaluation of our model using a data mining-based prediction algorithm. Section 5 concludes the paper and gives an overview of future works.

2 Related Works

In the context of mobility, trajectory modeling has been the subject of several works in different fields. In [5], authors propose a general framework for modeling trajectory patterns during the conceptual design of a database. In [4], authors propose a method to construct and analyze trajectories of mobile objects and apply it on ship and herbivore movements.

Some works [6,7,8,9] focus on the semantic aspect of trajectory. In [6], authors present a semantic trajectory conceptual data model named CONSTAnT, which defines the most important aspects of semantic trajectories. In [7] a semantic model for trajectories is proposed as well as relationships of trajectories with geographic and environment information. In this model, trajectory relationships are associated with vehicles and roads. Recently, authors propose in [8] a new conceptual model of trajectories, which accounts for semantic and indoor space information and supports the design and implementation of context-aware mobility data mining and statistical analytics methods. In [9], authors designed a multi-aspect and multi-level trajectory model that takes into account: (i) the description of sequences of hierarchical episodes, (ii) the definition of semantic aspects integrating spatial, temporal and thematic dimensions, and (iii) the association of such semantic aspects to positions or to trajectory episodes.

In [3] and [10] authors treat mobility patterns-based models. In [3], authors propose a software framework for modeling, querying and analysing an individual or group’s behavior. In [10], authors propose to describe the trajectories, at the conceptual level, with their geometric, temporal and semantic aspects and their structural components: starting point, ending point, stops and intermediate displacements. The modeling approach is based on modeling patterns, which allow a generic solution to model the standard characteristics of the trajectories. This model named “Stops and Moves” constitutes the basis of several works, such as [5, 6, 11].

Other works [11,12,13] are oriented towards urban human mobility. In [12], authors survey a data driven modeling of urban human mobility. They distinguish three main categories of urban human mobility models: Population Mobility Models (PMMs), Unified Mobility Models (UMMs) and Individual Mobility Models (IMMs). PMMs include gravity model, intervening opportunity model and radiation model. IMMs include Brownian motion, Levy flight, Continuous time random walk and Social-based model. UMMs cover some issues of population and individual mobility models. Among these models, we cite the universal model proposed by [13]. In [11], authors focus on modeling spatiotemporal trajectories from digital traces of mobile phone in order to study the human mobility. For that, a conceptual data model allowing modeling spatiotemporal dimensions of GSM data is proposed.

Recently, authors in [14] propose to model trajectory data with a deep generative model such that: (a) the model is lightweight, (b) the model is of high utility to support the downstream trajectory applications, and (c) the model preserves individual privacy.

Compared to the proposed approaches in the literature, we aim to propose a context based conceptual trajectory model for mobility prediction, which should satisfy the following requirements:

  • Avoid problems of existing trajectory description techniques, such as low precision and ambiguity of trajectory description due to the overlapping problem.

  • General enough to be used by different user centred mobile applications in smart cities, and covers the main contextual entities proposed in the state-of-the-art of mobile applications in smart cities.

In the following, we describe our trajectory modeling approach that we plan to use in a mobility prediction solution to improve the results of Location-Based Services Recommendation (LBSR).

3 Trajectory Modeling For Mobility Prediction

Our mobility prediction approach contains three main phases (see Fig. 1). The first phase concerns trajectory modelling and description. The second phase includes data acquisition, transformation, normalization and storage. The last phase is related to the prediction process (learning and prediction algorithms).

Fig. 1.
figure 1

Main steps of our mobility prediction approach

Full size image

3.1 Trajectory Description Technique: Technique of the Grid

Trajectory modeling is based on the technique used for the description of trajectory, allowing to answer the following question: in what terms is the trajectory described?

Many ways for trajectory description were used: trajectory can be described in terms of geographical places as in [3], in terms of landmarks as in [4], and in terms of cells of a cellular network as in [15]. However, some limits are observed with these techniques. The formers are not very precise and the latter suffers from the oscillation phenomenon due to the overlapping cells offering an erroneous description (see Fig. 2).

In cellular networks, theoretically, a network is represented in a hexagonal form where each cell corresponds to a Base Transceiver Station (BTS), known as an antenna. The reality, however, deviates from the theory because of the antennas radiate in a circular form. This causes the famous overlap problem, which causes the oscillation phenomenon. This phenomenon may imply a user movement even if the user does not move at all. A widely adopted solution is cell clustering, but at the expense of precision in mobility prediction, the oscillation deteriorates the prediction performance [15]. To overcome the cited limits, we propose a trajectory description technique, called technique of the grid.

This technique consists of breaking down the geographical study space into regions of identical shapes (a square) of a fixed size. The size of the regions will be defined based on the standards used for the definition of the sizes of cells in cellular networks, which depends on the nature of the geographic area. This size varies from a few tens of meters in urban areas to a few hundred meters or even kilometers in rural and deserted areas. Figure 3 illustrates the region division adopted.

In this technique, we distinguish two types of regions: sojourn regions and transit regions. Sojourn region is a region where the mobile spends a time greater than a given threshold. Departure and arrival regions are always considered as sojourn regions.

Fig. 2.
figure 2

Overlapping cells problem

Full size image
Fig. 3.
figure 3

Overview of a part of a city splitted using the technique of the grid

Full size image

Illustrative Example.

The trajectory illustrated on Fig. 3 is represented by the following sequence: R2 R8 R7 R8 R14 R13 R19 R20 R26 R27 R33 R34 R35 R29 R35 R36 R30 R29, where Ri denotes a region, R2 and R29 are two sojourn regions and the remaining regions are transit regions since they do not satisfy the condition of sojourn region. From this illustrative example, we can notice that each point of trajectory is associated to one region only. This allows avoiding the overlapping problem observed in the Id-Cell based descriptions without losing precision that depends on the requirements of the end application. If the latter requires high precision, the size of the grid elements (regions) needs to be reduced (augmentation of the spatial resolution). Thus, precision depends strongly on the “size” parameter that can be defined empirically.

In addition, our technique allows preserving the user’s privacy since the position of the user is given in terms of regions instead of an exact position defined in terms of a GPS coordinates (latitude and longitude).

3.2 Trajectory Modeling

There are two alternatives of trajectory modeling. The first one is to design the trajectory model based on the needs and the available data; it concerns the data-driven mobility modeling [12]. The second one is to design the model based solely on needs. In this second case, the data will be collected according to the model after its creation. In our work, we adopt the second alternative and propose a trajectory model, which accounts the contextual data and which is oriented for mobility prediction.

Context-Based and Prediction-Oriented Trajectory Model for Location-Based Services Recommendation.

In order to enhance results of location-based services recommendation, we aim to apply trajectory modeling to mobility prediction of a mobile object moving under variable context. Thus, we define three key parameters in our model: context, prediction and location-based services (LBSs) of the city. The context includes time, urban traffic, weather and means of displacement; it is a main parameter that influences mobility. The LBSs tacking place in the city are important because of the final objective attached to services recommendation. The prediction in the model represents prediction algorithm allowing to predict future position (s) based on history.

Our model allows also the identification of significant positions in trajectories, considered as PoIs, through the consideration of stations, representing, possibly, the places where the mobile object practices an activity; and significant transit points, related to the locations of LBSs.

Trajectory Model Description: Principle and Main Classes.

Our trajectory model extends the Stops and Moves model, proposed in [10], with advanced contextual information, and is intended for mobility prediction. Figure 4 shows a meta-model including the main classes and links between them.

Smart City Mobility View (SCMV): Consists of an aggregation of trajectories of the mobile object and allows to express the different possible views on mobility in a city. Through this class, three main views of mobility in a city can be specified and visualized:

  • The past mobility view: gives a view on the mobility of a person or a group of people during a period in the past. This view also allows to visualize the general mobility in the city in a given past period.

  • The real-time mobility view: this view gives real-time mobility in the city. Mobility on a person, a group of people or a district of a city or the whole city can be visualized.

  • The predicted mobility view: This view is used to calculate and display a mobility prediction in the city. It may concern either a person (trajectory prediction) or a neighbourhood in the city (group mobility prediction).

Mobile Object: Consists of the entity performing one or more displacements. The mobile object can be of two types: human and other.

Trajectory: It is composed of a set of displacements.

Displacement: Consists of an aggregation of transit regions. Each displacement is delimited by two consecutive stations (source and destination) and happens in a specific context that can be variable for the same displacement.

Context: Includes specific data that can influence mobile user displacements. We consider the following data: Time (as standard contextual data), weather, means of displacement and road traffic (as advanced contextual data). As we can see in Fig. 4, each movement of a mobile object is linked to a context through the association class Context.

Station: Represents a sojourn region where the mobile object stays a time superior to a given threshold.

Transit Region: Represents the regions through which the mobile object passes without staying in. The transit region contains two types of transit points: standard points and significant points. These latter are very important in our work because it concerns relevant locations related to specific location-based services taking place in the city.

Location-Based Service. Concerns all services of the city, for which the location is a key parameter. These services are relevant for a recommendation to specific profiles.

Prediction: Associates the mobile object to the SCMV. It is about making predictions according to context filtering, a current date and place, and opting for a defined prediction model.

3.3 Comparative Study

In this section, we compare our model with those of the cited works based on five criteria that are: application domain, respect of the Stops and Moves principle, context and semantic consideration and items used for the description technique (see Table 1).

Comparatively to the cited models, innovative ideas, such as the consideration of the technique of the grid and the explicit integration of the prediction, have been added to our model. The advantages derived from other models (consideration of the semantic aspect, adoption of the Stops and Moves principle, etc.) have been retained. As a result, we obtained a personalized model with respect to prediction purpose, but generic with respect to trajectory modeling in urban places and with respect to service recommendation, which is not limited to a particular type of service. Our model is easier to understand, but also more complete in terms of the diversity of data required to meet our needs (predict to recommend).

Fig. 4.
figure 4

Context-based and prediction-oriented trajectory model

Full size image

4 Application of the Model in Road Traffic Field

In this section, we present an example related to the application of mobility prediction to intelligent transportation and road traffic systems. For that, we are working on the design of a mobile application for road anomaly detection and notification. This application serves to collect anomalies happening on roads and to notify citizens about those situated in their future trajectories. This latter will be obtained using our mobility prediction approach. We focus in this scenario on trajectory modeling and data acquisition steps, allowing construction of users’ trajectories.

The construction and storage of a user's trajectory is performed based on the grid technique and according to the proposed trajectory model. In fact, first, the study area is delimited and broken down into regions. Subsequently, the necessary data will be collected, processed and projected onto the study area in order to determine the key elements of the trajectory (station, transit region, etc.). These data will then be transformed according to the model and finally recorded in the associated database.

At the mobile application level, a data collection module will collect all data required for the model. These data can be collected when users install the application on their mobile devices and agree to the terms of use. Positions, date and time will be extracted implicitly. Advanced contextual data can be extracted implicitly, explicitly or inferred.

Table 1. Trajectory models comparison
Full size table

When enough quantities of data is available, they will be recorded, in form of trajectories, in the database conformably to the trajectory model. These trajectories will be used in the prediction process (learning and prediction algorithms).

At this stage, the mobility prediction will serve to improve the dissemination of alerts to affected users whenever a traffic anomaly occurs in the city. The users concerned are those whose predicted trajectory, from their current position, contains significant waypoints corresponding to the location of anomalies stored in the LBS classe of the model.

4.1 Model Evaluation

The performance of our model is evaluated on a prediction algorithm using real user movements. For that, we developed a data mining-based prediction algorithm using Generalized sequential pattern (GSP) algorithm. To show the impact of our model on the prediction algorithm, we executed the algorithm according to two alternatives and we compared the prediction accuracy values obtained for each case. In the first alternative, we used our model to describe the trajectories with the consideration of standard contextual data (date and time) only. In the second alternative, no trajectory model was taken into account. We have described the trajectories as being a succession of positions with the consideration of the PoIs.

The evaluation was made on 33 persons. For each alternative, we calculated the following values: the average precision of all the users, the maximum precision value corresponding to the user U1, and the minimum precision value corresponding to the user U2. The precision is measured as the ratio of correctly predicted transitions to the number of computed predictions. Results showed that all values of precision of the first alternative outperforms the values of the second alternative. The best value of precision (82%) is obtained for the user U1 (having a regular mobility) with the first alternative.

5 Conclusion and Future Works

We proposed a model based on the grid technique to obtain more precise and unambiguous trajectories. Our model adopts the Stops and Moves approach, allowing to integrate the semantic aspect by identifying sojourn regions. The contextual aspect, reflecting the travel conditions (e.g., weather,) is also present in the model.

Compared to other models, data present in the model are sufficient for the construction of fairly rich trajectories, in terms of information on the travel conditions, as well as for the prediction process. The model is scalable as it tolerates the addition of other contextual data and takes into consideration any type of LBS belonging to any domain. Moreover, the model is intended for service recommendation, which became very popular among citizens, especially those moving in smart cities. An example of application of our model was presented. The results of evaluation showed the positive contribution of our trajectory model on the prediction algorithm.

Our future work aims to integrate all the contextual data present in our trajectory model (climate, means of transport, etc.) in the prediction phase of our prediction process to improve accuracy.