Location prediction and mobility modelling for enhanced localization solution

Abstract

Current and future mobile applications massively exploit the knowledge of the user’s location to improve the offered services. However, user localization is by far one of the oldest and most difficult issues, due to its dynamism and to unavailability of some technologies in indoor environments. The enhanced localization solution (ELS) proposed in this paper is an innovative self adaptive solution that smartly combines standard location tracking techniques (e.g., GPS, GSM and WiFi localization), newly built-in technologies, as well as human mobility modelling and machine learning techniques. The main purposes of this solution are: to reduce the impact the service has, on the mobile device resources usage (mainly the battery consumption), when it is asked to provide a continuous localization; to help in preserving the privacy of the user, by running the whole system on the mobile device, without relying on a back-end server; and furthermore, to offer an ubiquitous coverage. The aspects mainly explored in this paper are: location prediction and mobility modelling, required to optimally estimate the current location with ELS. We are finding that people tend to move, for most of the time, among a limited set of places and that this can be modelled with a user prediction graph, which is further used to predict the next movement. Performing experiments on real users data, we show that the proposed prediction and the mobility model method of ELS are able to successfully predict the next location, even if we do not account for time features.

Appendices

Appendix 1: Activity inferences: preliminary experiments

In line with the state on the art (Kim et al. 2010; Miluzzo et al. 2008; Ofstad et al. 2008; Reddy et al. 2010), we also performed some experiments for studying how to differentiate between different human activities. We performed a real experiment by asking a user to collect sensors data with two different devices (HTC NexusOne running Android 2.3.6 and a Samsung GT I9100 running Android 2.3.3), while performing three different activities (walking, running, driving). The data was collected sampling three different embedded sensors: accelerometer, magnetic field and orientation sensor. The average sampling rate (the fastest possible according to the devices themselves and the versions of the operating system installed onto the devices) is equal to 25 Hz (sampling period of 40 ms). While collecting data the phones have been positioned respectively into the left and right pockets of the user’s jacket, when the user was walking and running; instead, while driving, the user positioned the phones on a car’s seat.

Some mining over the sampled data has been performed off-line to understand if it is possible to recognise the user’s activity. A set of features have been calculated over the data for sliding windows of 5 s. We show here some of the most significant calculated features by means of which it is possible to clearly differentiate the activity of the user among three predefined categories: walking, running, driving. In each figure presented below, the blue line represents the data collected while walking, the green data has been collected while running, and the red data while driving.

Figures 14 and 15 represent respectively the value of the y and z axis of the accelerometer raw data. Both of them are represented in ms⁻².

Fig. 14

Acceleratio raw data: mean (y-axis)

Fig. 15

Acceleratio raw data: mean (z-axis)

Figures 16 and 17 represent respectively the standard deviation value calculated over the y and z axis of the accelerometer raw data.

Fig. 16

Acceleratio raw data: standard deviation (y-axis)

Fig. 17

Acceleratio raw data: standard deviation (z-axis)

Finally Fig. 18 represents the peak–peak amplitude of the accelerometer data on the y axis. This value consists basically on the distance between consecutive local maximum and minimum values.

Fig. 18

Acceleratio raw data: peak–peak amplitude (y-axis)

Figures 19 and 20 represent respectively the standard deviation and the average peak–peak amplitude calculated over the magnitude of the acceleration data. This feature has been considered to tolerate the random position of the mobile device with respect to the user body. The magnitude of the acceleration data is defined with the formula $\sqrt{x^{2} + y^{2} + z^{2}},$ where x, y and z are the values of the raw accelerometer data, over the three axis.

Fig. 19

Acceleratio magnitude: standard deviation

Fig. 20

Acceleratio magnitude: peak–peak amplitude

Also some features calculated over the orientation sensor data allow a straightforward differentiation of the user activity among the three predefined classes. The orientation sensor provide information in degrees about the azimuth (x-axis), pitch (y-axis) and roll (z-axis) of the device. Figures 21, 22 and 23 represent respectively the mean, the standard deviation and the average peak–peak amplitude value for the orientation value raw data over the y-axis (pitch in degrees).

Fig. 21

Orientation sensor: mean (y axis)

Fig. 22

Orientation sensor: standard deviation (y axis)

Fig. 23

Orientation sensor: peak–peak amplitude (y axis)

Analysing the figures presented in this paragraph, we can conclude that only calculating a small set of features over sensors’ data allows a straightforward inference of the user activity among predefined categories. This is a promising conclusion considering the inferential study of the ELS, which is however interested in the classification of the user’s activity over a set of only two possibilities: static and moving.

Appendix 2: Transposition of the sensed data from the device to the globe coordinate system

Equation 10 represents the quaternion which performs a rotation about the unit vector $\bar{u}$ and by an angle α.

$$ q= w+x\bar{i}+y\bar{j}+z\bar{k}= \left ( s,\bar{v} \right ) $$

(10)

where

$$ s= w = \cos \frac{\alpha}{2} $$

(11)

and

$$ \bar{v} =\bar{u}\sin \frac{\alpha }{2} $$

(12)

with

$$ \bar{u}=x\bar{i}+y\bar{j}+z\bar{k} $$

(13)

The quaternion q is then used to rotate a vector from the device coordinate system ($\bar{y_{d}}$) to the globe coordinate system ($\bar{y_{g}}$), as shown in Eq. (14).

$$ \bar{y_{g}} = q\bar{y_{d}}q^{-1} $$

(14)

An example of rotated accelerometer data is reported in Fig. 24 where it is easily possible to visualize the whole gravitational component on a single axis (plot at row 3, column 2 in Fig. 24): we can hence decide to study the displacement of the mobile device on a 2D surface.

Fig. 24

On the left the acceleration data referred to the coordinate system in Fig. 6a; on the right the same data referred to the coordinate system in Fig. 6b. The three rows show respectively the three components of acceleration row data (x, y, z) in ms⁻²