Simplified KF-based Energy-Efficient Vehicle Positioning for Smartphones

1. Introduction

THE accuracy and reliability of the positioning system have a great impact on the performance of location-based applications associated with the intelligent transportation systems (ITSs), including automated toll-collection systems, collision avoidance warning systems, vehicle routing, etc. In such ITS applications, global positioning system (GPS) is the simplest method to observe the position and velocity of the vehicle. However, vehicle networks can easily be affected by the abrupt and frequent change in topology. In addition, road environments in which GPS outliers frequently occur due to multipath GPS signals can seriously degrade the positioning system’s performance.

Land vehicle positioning using vehicle-fixed sensors to improve GPS accuracy in transportation networks is a mature technology with numerous commercial applications [1]. There have been many researches fusing GPS positional information with measurements from inertial navigation system (INS) sensors, such as accelerometer and gyroscope [2]–[5]. It is shown in [6] and [7] that information obtained from the digital camera and laser scanner can be integrated with the GPS/INS positioning system and digital road maps. To provide an accurate estimate of the vehicle position, GPS/INS positional data are combined with measurements gained from the radio localization system [8], [9].

Recently, one of the challenges of vehicle positioning technology is to extend the positioning system using vehicle-fixed sensors to implementations that take advantage of sensor measurements of smart mobile devices with high mobility and flexibility, such as smartphones and tablet PCs [10]–[12]. In general, most of mobile devices are equipped with a set of sensors including GPS modules and INS sensors, and have included more and more features. Furthermore, the mobile devices play an important role in users’ daily routines, and the number of them in active use keeps increasing. For this reason, they can be utilized as a user-friendly positioning device and measurement probe for vehicle navigation systems. Promising applications of smartphone-based GPS/INS systems can be found in the fields of advanced driver-assistance systems [13], traffic state estimation [14], fleet management [15], and insurance telematics [16].

Smartphone-based positioning can be particularly relevant to insurance telematics, where vehicle information about driving trips collected with smartphone built-in sensors is used to provide driver feedback and adjust premiums. For example, insurers can use GPS position measurements to estimate the vehicle’s location and can utilize INS measurements to detect harsh braking. Also, an accurate estimate of the smartphone position can be employed to reduce driver distraction by facilitating positiondependent limitations for smartphone functionality while driving [17].

For mobile devices, the power supply is a main concern. Due to relatively light weight and small size of mobile devices, their power supply depends mostly on the battery. For smartphones, location-based applications (LBAs) require substantial battery power due to high energy consumption of GPS modules and INS sensors. If they request continuous positioning for a long time, the battery may be discharged soon. In addition, inexpensive INS sensors in smartphones can have very inaccurate positional accuracy due to drift errors and biases. The sensor drift errors indicate that small errors in INS measurements are gradually incorporated into larger errors as time progresses. To avoid these issues with regard to INS sensors, we use only the GPS receiver and digital compass without INS sensors. This makes it possible to provide more accurate localization results and to save more battery power required for the vehicle localization, compared to smartphone-based GPS/INS localization algorithms.

However, low-cost micro electro mechanical systems (MEMS) sensors, such as GPS receiver and digital compass on smartphones, can still produce large positioning errors. This is probably because GPS outliers can happen due to the multipath and obstruction of GPS signals in urban environments, and the accuracy of digital compass is subject to degradation in the presence of nearby magnetic sources or disturbances.

Therefore, we propose an enhanced vehicle positioning method that offers more reliable localization results by fusing measurements from GPS receiver and digital compass based on a Bayesian filter, called a simplified Kalman filter (SKF). The SKF algorithm is not a fundamentally novel Kalman filter (KF), but it can provide the formal simplicity for the standard KF by assuming that the measurement model is equal to identity matrix. This assumption makes the SKF simple and intuitive to implement; for example, unlike the standard KF, it can estimate the model state without the calculation of the Kalman gain. Also, the SKF can provide positive effects for saving computational cost, because the number of the computations to be required for state estimation in the SKF is smaller than that of the standard KF. While providing these benefits over the KF, the SKF can accomplish estimation performance comparable to conventional Bayes filters, such as KF, unscented Kalman filter (UKF), and particle filter (PF). Our vehicular positioning algorithm is performed in two different phases: prediction (dead reckoning) and update. During the dead reckoning phase, the position of the vehicle is estimated using traveled distance (displacement) calculated by two GPS positions and heading information from digital compass. In the update step, the position of the vehicle is corrected by integrating both positional information obtained by the prediction phase and positional data of the vehicle observed by GPS through the SKF.

To validate the performance for our localization algorithm based on the SKF, we implemented the algorithm on a smartphone and carried out various road tests using a test vehicle in real environments. Experimental results show that our positioning approach can achieve competitive positioning results with less energy, compared to smartphone-based GPS/INS positioning approaches based on the KF, UKF, and PF.

The rest of this paper is organized as follows. Section II describes a summary of related work. Next, Section III shows a description of the overall system architecture. A description of the SKF is presented in Section IV. Our positioning algorithm based on the SKF is described in Section V. Section VI shows experimental setups and results for our positioning system. Finally, Section VII provides conclusions of this paper.

II. RELATED WORK

Because of the high energy consumption of GPS modules and the use of various positioning sensors including INS sensors (e.g., accelerometer and gyroscope) on mobile devices, the energy efficiency in the localization algorithm based on GPS is a key issue that should be considered. Due to the severity of the issue, energy-efficient positioning techniques have been extensively studied in substantial literature. The main concern of such researches is to provide an accurate position estimate while using minimal energy.

The dynamic tracking activates the GPS receiver when it is considered that the updated GPS positional information would have a great impact on the positioning accuracy. This can be classified into two general categories: dynamic selection and dynamic prediction.

For dynamic prediction, the uncertainty in the positioning is estimated by the sensor that generally consumes less energy than GPS [18]. For instance, the accelerometer can be employed to detect the movement of the mobile device. If the mobile device is not moving, the positioning process is not performed until the movement is detected [19], [20].

For dynamic selection, the positioning method switches between GPS and less power-intensive navigation system, such as localization system based on Wi-Fi, by taking into account the location and time dependence of the localization accuracy required by LBAs and the performance of the navigation system. For instance, the positioning accuracy required by navigation applications is generally increased when cars enter the intersection [21]. Also, the positional measurement obtained by GPS may be inaccurate especially in urban environments [22].

By considering the change in the accuracy requirement, the mobile device is able to select the navigation system that can strike the right balance between energy efficiency and positioning accuracy. For example, Sommer et al. [23] proposes an energy-aware positioning scheme that adapts the duty cycle of the GPS receiver for a trade-off between the localization accuracy and energy consumed for the continuous positioning. This scheme infers positioning errors through dead-reckoning using magnetometer and accelerometer, and employs the GPS receiver if the errors are above a given threshold. The threshold is determined by considering movement patterns and the current battery power. SmartDC [24] uses a mobility prediction-based adaptive GPS duty-cycling scheme that takes advantage of prediction mechanisms for regularities in the target movement.

For dynamic tracking, the lower sampling rate of the GPS module can reduce the energy consumption per time. However, the hot, warm, and cold start-up conditions of GPS can increase the total power consumption needed per GPS sample in the mobile device [21].

To enhance the energy efficiency of the vehicular positioning system based on the mobile device, there are several additional approaches applied to the navigation system. For instance, the positioning filter can be performed by the map-matching (MM) algorithm. When theMMalgorithm is used, the vehicle position estimation that deviates from adjacent road segments can be located within the limits of road segments. For theMMalgorithm, the improvement of the positioning performance generally relies on the density of road segments; that is, the high road density would cause severe degradation in the localization accuracy of the MM approach. Therefore, the characteristics of MM need to be taken into consideration when the GPS sampling method with high energy efficiency is designed [25]. The MM enables less power-intensive INS sensors to be used for the vehicle positioning for a long time, since it can mitigate the increase in the positioning error caused by INS sensors.

Furthermore, MM-based positioning methods can be performed without GPS. CTrack [26] is a low-energy localization approach for mobile devices that executes the MM employing raw positioning data gained from cellular (GSM) base station fingerprints. Because CTrack uses cellular fingerprints instead of power-hungry GPS andWi-Fi, the marginal energy consumption by the MM is zero. Also, this scheme uses measurements obtained by low-power sensors, such as digital compass and accelerometer, available on smartphones. semMatch [27] is an energy-efficient MM-based navigation system that uses INS sensors on the smartphone instead of GPS to identify the different road semantics, such as speed bumps, turns, and tunnels. This enhances the accuracy and efficiency of the MM by leveraging the vehicle’s ambient road semantics combined with the semantics-enriched digital map in a mathematically-principled way to overcome coarse-grained, noisy, and sparse input localization information (e.g., cellular-positioning data and low sampling rate GPS measurements).

However, the MM requires substantial time and cost to create the digital road map; for example, the road maps is generated employing professional approaches based on satellite imagery and exploiting the crowdsourcing via GPS traces collected by drivers with mobile devices. Furthermore, even the best maps can include omissions and errors for road segments and can be out of date because the world around them is changing.

Another strategy is to execute the cooperative localization by sharing sensing data, such as GPS and INS measurements, measured from neighboring smartphones. This can provide satisfactory positioning accuracy, while consuming less power by decreasing the number of GPS updates [28].

RAPS [20] is an energy-efficient positioning algorithm for urban environments with the poor GPS performance due to multipath effects. It uses an adaptively duty-cycled accelerometer to detect the user movement and utilizes Bluetooth to save more energy and to minimize position uncertainty by sharing the newly updated position among neighboring smartphones. Additionally, it uses the received signal strength (RSS) blacklisting of celltower to detect GPS unavailability and to avoid GPS activation only in the case where GPS is unavailable. However, the celltower-RSS blacklist should be prepared for the algorithm. Furthermore, the positional information sharing through Bluetooth communication can cause security concerns.

CEET [29] is a cooperative positioning approach that leverages the coexistence of communication modules, such as Bluetooth and Wi-Fi, on nearby mobile devices grouped in a cluster.

One cluster consists of a dynamically selected group head and regular group members, which communicate with each other by Bluetooth. To avoid the continuous use of communication modules on individual mobile devices, the group head on behalf of the cluster carries out the localization and then shares localization results with regular members that belong to the cluster. Also, the head serves as a gateway between the server and cluster members.

However, the cooperative localization, which is proposed to deal with a problem with the serious energy consumption required by Wi-Fi and GPS positioning, is appropriate for large scale navigation systems in which drivers are expected to move around in groups.

While the dynamic tracking that uses INS sensors to detect the movement of the mobile device is running, it cannot turn off sensors. Therefore, the energy consumed by the sensors can be higher than that needed for such an occasional positioning. Furthermore, low-cost INS sensors on smartphones can result in large localization errors due to sensor drift and bias, and they can consume more energy than the digital compass [30]. Unlike existing approaches using INS sensors, we employ the digital magnetic compass instead of INS sensor. This enables our localization approach to provide more accurate positioning and to save more energy. Unlike MM-based localization schemes, our method does not use the digital road map that requires the high costs due to maintenance and device installment. Also, in contrast to cooperative localization, our scheme is performed independently without belonging to specific groups for the vehicular localization and can offer reliable localization results with low computational cost by fusing sensor measurements based on the SKF.

III. SYSTEM ARCHITECTURE

Fig. 1 presents the architecture of our positioning algorithm proposed in this paper. The individual components of the architecture implemented on the smartphone (iPhone 5S) are composed of the sensor fusion and localization algorithm. The sensor fusion part consists of low-cost sensors on the smartphone, including GPS receiver and digital compass. The localization algorithm based on the SKF, Bayesian filtering proposed in this paper, estimates the vehicle position by integrating measurements obtained from the sensors using the system model that is modeled on the vehicle motion on the road. The system model is described in more detail in Section V.A.

Table 1 represents the notation and main features for the positioning algorithms employed in this paper. In Table 1, while ACC, GYR, DC, and GPS represent the use of an accelerometer, a gyroscope, a digital compass, and a GPS receiver, respectively, GPS/DC (i.e., P1) indicates a positioning approach that predicts the vehicle position using measurements obtained from GPS and the digital compass. The Bayesian filter for the vehicular positioning algorithm can be composed of two different phases: prediction (dead reckoning) and update. The prediction phase typically predicts the vehicle location using both the traveled distance (displacement) calculated according to the magnitude of the acceleration measured by the accelerometer and the heading angle obtained by the accelerometer, gyroscope, and digital compass, as in P2 and P3. On the other hand, P1 in the prediction phase predicts the position of the vehicle using the traveled distance calculated by two GPS positions and the heading information from the digital compass. During the update phase, the vehicle position obtained from the prediction phase is corrected by fusing it and the position measurement from GPS.

As can be seen in Fig. 1 and Table 1, the localization approaches can be classified into two categories depending on the execution phase of the Bayes filtering employed in each approach: localization algorithms operated in only the prediction phase (P1, P2, and P3) and localization schemes performed in both prediction and update phases (PU1, PU2, and PU3). The system model used in the positioning algorithm varies according to the type of the sensor that the algorithm uses. While localization approaches using the accelerometer are based on System Model A (Section V.A.1), algorithms employing GPS/DC calculate the position of the vehicle through System Model B (Section V.A.2). In this paper, the positioning algorithms that we actually propose to improve the performance of the vehicle positioning are approaches P1 and PU1, and other approaches P2, P3, PU2, and PU3 are used to evaluate the performance of methods P1 and PU1. Since P1 and PU1 do not use INS sensors (accelerometer and gyroscope) that are subject to drift errors and require much time and energy for the position estimate, they can provide more accurate positioning results and can save more energy and time than P2, P3, PU2, and PU3.

IV. SIMPLIFIED KALMAN FILTER (SKF)

Suppose we have a linear discrete-time system given as follows:

where the matrix [TeX:] $$F_{k-1}$$ is the state transition model that is applied to the previous state [TeX:] $$\mathbf{X}_{k-1},$$ and the matrix [TeX:] $$H_{k}$$ is the measurement model that maps the state [TeX:] $$\mathbf{X}_{k}$$ into the measurement[TeX:] $$Z k.$$ The matrices [TeX:] $$F_{k-1} \text { and } H_{k}$$ define the nonlinear system. The process noise [TeX:] $$\mathbf{W}_{k-1}$$ and measurement noise [TeX:] $$\mathbf{v}_{k}$$ are white, zero-mean, and uncorrelated, and they have covariance matrices [TeX:] $$Q_{k} \text { and } R_{k},$$respectively.

The SKF algorithm is not a fundamentally new KF for system state estimation, but it can provide formal simplicity for the standard KF by assuming that the measurement matrix [TeX:] $$H_{k}$$ is equal to identity matrix I, as it often is in the linear system. This assumption makes the SKF simple and intuitive to implement. For example, unlike the standard KF, the SKF only needs the a priori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k-1},$$ measurement [TeX:] $$\mathbf{z}_{k},$$ and covariance matrices [TeX:] $$P_{k | k-1} \text { and } R_{k} \text { for } \hat{\mathbf{x}}_{k | k-1} \text { and } \mathbf{z}_{k}$$ without the calculation of the Kalman gain to estimate the state [TeX:] $$\mathbf{x}_{k}.$$ Furthermore, if [TeX:] $$H_{k}=I,$$ then the SKF is functionally equivalent to the standard KF. That is, the output of the SKF equals that of the standard KF when [TeX:] $$H_{k}=I.$$ For the SKF, the a priori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k-1}$$ and its covariance [TeX:] $$P_{k | k-1}$$ are determined in the same manner as the standard KF, but the a posteriori estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ and its covariance [TeX:] $$P_{k | k-1}$$ are obtained by combining [TeX:] $$\hat{\mathbf{x}}_{k | k-1}$$ with [TeX:] $$\mathbf{Z} k$$ by the weighted sum. Suppose that we combine the estimate [TeX:] $$\hat{\mathbf{x}}_{k | k-1}$$ and the measurement [TeX:] $$\mathbf{Z}_{k}$$ using the weight [TeX:] $$W_{p}$$ for [TeX:] $$\hat{\mathbf{X}}_{k | k-1}$$ and weight [TeX:] $$W_{m}$$ for [TeX:] $$\mathbf{z}_{k}$$ to get the estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ as follows:

Note that [TeX:] $$\hat{\mathbf{x}}_{k | k-1} \text { and } \mathbf{z}_{k}$$ are both unbiased since [TeX:] $$\hat{\mathbf{X}}_{k | k-1}$$ is the output of the standard KF and [TeX:] $$E\left[\mathbf{v}_{k}\right]=0.$$ Therefore, if [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ is to be unbiased, the relationship between [TeX:] $$W_{p} \text { and } W_{m}$$ can be expressed as

From (2) and (3), the a posteriori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ is given by

A. Optimal Weights [TeX:] $$W_{p} \text { and } W_{m}$$

From (4), the covariance [TeX:] $$P_{k | k}$$ of the a posteriori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ can be represented by

where [TeX:] $$\mathbf{z}_{k}=\mathbf{x}_{k}+\mathbf{v}_{k},$$ the a priori estimate error [TeX:] $$e_{k | k-1}=\mathbf{x}_{k}- \hat{\mathbf{X}}_{k | k-1},$$ and we use the fact that [TeX:] $$E\left[e_{k | k-1} \mathbf{v}_{k}^{T}\right]=0, E\left[\mathbf{v}_{k} \mathbf{v}_{k}^{T}\right]= R_{k}, \text { and } E\left[e_{k | k-1} e_{k | k-1}^{T}\right]=P_{k | k-1},$$ since [TeX:] $$\hat{\mathbf{x}}_{k | k-1} \text { and } \mathbf{z}_{k}$$ are both unbiased, and [TeX:] $$e_{k | k-1} \text { and } \mathbf{v}_{k}$$ are independent.

We can minimize the trace of [TeX:] $$P_{k | k}$$ with respect to [TeX:] $$W_{p}$$ using results related to matrix calculus from [31] as follows:

Setting (6) to zero, the optimal value of [TeX:] $$W_{p}$$ is calculated by

Rearranging (3) and (7), we find that

From (8), the optimal value of [TeX:] $$W_{m}$$ is denoted by

B. A Posteriori Estimate Error Covariance [TeX:] $$P_{k | k}$$

The inverse of [TeX:] $$\left(P_{k | k-1}+R_{k}\right)$$ always exists since both covariance matrices are positive definite. We can substitute (7) into (5) to find the covariance of the a posteriori estimate as follows:

Using the matrix inversion lemma [32], the second term can be expressed as follows:

Substituting (11) into (10), [TeX:] $$P_{k | k}$$ is given by

C. Alternative Form of A Posteriori State Estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$

Equations (7) and (9) can be substituted into (2) to provide an alternative equation for [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ as follows:

From the matrix inversion lemma [32], the inverse of [TeX:] $$\left(P_{k | k-1}+R_{k}\right)$$ can be expressed as follows:

From both (14) and (15), (13) is denoted by

Using (12), the alternative form of the a posteriori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ can be expressed as

D. Relationship with Standard Kalman Filter

This section shows that the alternative expression for the state estimate of the SKF is the same as the expression of the standard KF when [TeX:] $$H_{k}=I.$$ In order to do this, a few lemmas are needed to establish.

Lemma 1: If the measurement matrix [TeX:] $$H_{k}=I,$$ then the Kalman gain [TeX:] $$K_{k}$$ satisfies the equation

Proof: From the Kalman gain of the standard KF, we see that

where [TeX:] $$S_{k}$$ is the covariance of the measurement residual [TeX:] $$\mathbf{z}_{k}- H_{k} \hat{\mathbf{x}}_{k | k-1}.$$ When [TeX:] $$H_{k}=I,$$ (19) can be written as

Lemma 2: If the measurement matrix [TeX:] $$H_{k}=I$$, then the a posteriori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ satisfies the equation

Proof: From the a posteriori state estimate [TeX:] $$\hat{\mathbf{x}}_{k | k}$$ of the standard KF, we obtain

When [TeX:] $$H_{k}=I,$$ (21) can be expressed as

Lemma 3: If the measurement matrix [TeX:] $$H_{k}=I,$$ then the a posteriori estimate covariance [TeX:] $$P_{k | k}$$ satisfies the equation

Proof: From the a posteriori estimate covariance [TeX:] $$P_{k | k}$$ of the standard KF, we see that

From (19), (23) is given by

Taking the inverse of both sides of this equation and applying the matrix inversion lemma to this equation, we find that

Inverting both sides of (25), the a posteriori estimate covariance [TeX:] $$P_{k | k}$$ is given by

When [TeX:] $$H_{k}=I,$$ (26) can be written as

With the above lemmas, the alternative expression for the state estimate can be derived. Rearranging (18) and (20) results in the same as (13). After some algebraic operations, the alternative expression can be expressed as (17).

Note that the use of the SKF to estimate the state provides three practical advantages: 1) Compared to the standard KF, the SKF is simple and intuitive to implement, since it does not require the calculation of the Kalman gain; 2) the SKF results in positive effects for saving computational time, since the number of the computations to be needed for the state estimation in the SKF is smaller than that of the standard KF; and 3) while having these advantages, the SKF can achieve the estimation performance comparable to the traditional Bayes filters, such as KF, UKF, and PF. The performance of the SKF in terms of the state estimate and computing is discussed in Section VI.

V. POSITIONING ALGORITHM

The following four sections describe the system model and positioning algorithm used for this paper.

A. System Model

The schematic of the vehicle model used in this paper is shown in Fig. 2. The position and velocity of the vehicle at time k is described by the linear state space [TeX:] $$\mathbf{x}_{k}=\left[\begin{array}{lll} x_{k} & y_{k} & v_{k} \end{array}\right]^{T},$$ where [TeX:] $$\left(x_{k}, y_{k}\right)$$ is x-axis and y-axis position in the navigation frame, and [TeX:] $$v_{k}$$ is the vehicle velocity. The navigation frame is the local geodetic frame in which it is defined that x-axis, y-axis, and z-axis point east, true north, and up direction, respectively. Note that z-axis information is not considered for land-vehicle navigation. Thus, the state [TeX:] $$x_{k}$$ just has x-axis and y-axis positioning information. The angles and represent the heading of the vehicle at time steps k - 1 and k, respectively. Also, the angle represents a counterclockwise angle between the state vectors [TeX:] $$\mathbf{x}_{k-1} \text { and } \mathbf{x}_{k},$$ and the value of d indicates the traveled distance of the vehicle between time steps k - 1 and k. The vehicle model can be divided into two submodels by whether the accelerometer is used or not: System model A and system model B.

A.1 System Model A

In the vehicle model used to represent the vehicle motion with MEMS sensors, such as accelerometer, gyroscope, and digital compass, the position and velocity of the vehicle can be determined by

where [TeX:] $$\Delta t$$ is the update interval of the accelerometer ([TeX:] $$\Delta t$$ = 0.01s in this paper), and [TeX:] $$d=v_{k-1} \Delta t+\frac{v_{k}-v_{k-1}}{2} \Delta t.$$ In the above equations, a constant acceleration of [TeX:] $$a_{k}$$ is determined by accelerometer, and the values of [TeX:] $$\alpha and \beta$$ are measured by accelerometer, gyroscope, or digital compass. Since [TeX:] $$\Delta t$$ is very small and negligible, we assume that the vehicle has the value of [TeX:] $$a_{k}$$ in time from k - 1 to k, i.e., [TeX:] $$a_{k}=a_{k-1}.$$ Therefore, [TeX:] $$a_{k}$$ can be denoted by [TeX:] $$\frac{v_{k}-v_{k-1}}{\Delta t},$$ and the propagation equations for the position and velocity of the vehicle can be expressed as

where [TeX:] $$d^{\prime}=v_{k-1} \Delta t+\frac{a_{k}}{2} \Delta t^{2}.$$

Applying the sine and cosine rule to (31) and (32) and substituting [TeX:] $$\alpha-\beta$$ with , both (31) and (32) are given by

By assuming that the constant acceleration of [TeX:] $$a_{k}$$ is normally distributed with zero-mean and covariance [TeX:] $$Q_{k},$$ the state transition model and measurement model of the vehicle motion can be written as

where [TeX:] $$H_{k}$$ is [TeX:] $$3 \times 3$$ identity matrix

and

In (36) and (37), process noise [TeX:] $$\mathbf{W}_{k-1}$$ and measurement noise [TeX:] $$\mathbf{v}_{k}$$ are all zero-mean white noise with covariance [TeX:] $$G_{k-1} Q_{k-1} G_{k-1}^{T} \text { and } R_{k},$$ respectively, and measurement [TeX:] $$\mathbf{z}_{k}$$ includes the position and velocity information of the vehicle measured by GPS. This system model can be used to estimate the positional data of the vehicle in the approaches using the accelerometer among the positioning methods described in Section III (i.e., P2, P3, PU2, and PU3). However, the methods P2 and P3 not using GPS positional data calculate the position and velocity of the vehicle through only the state transition model (36) without using the measurement model (37).

A.2 System Model B

Unlike System Model A, the vehicle motion can be modeled using only the digital compass and GPS without the INS sensors (accelerometer and gyroscope) in System Model B. Since System Model B does not use the accelerometer, its state space does not include the velocity information of the vehicle, i.e., [TeX:] $$\mathbf{x}_{k}=\left[\begin{array}{ll} x_{k} & y_{k} \end{array}\right]^{T},$$ and the value of d can be determined by the distance between two positional data obtained from the GPS receiver at time steps k-1 and k, using the haversine formula [33]. Also, the values of and can be determined by the digital compass. The state transition model and measurement model in System model B can be written as

where [TeX:] $$\mathbf{w}_{k-1} \sim \mathcal{N}\left(0, Q_{k-1}\right), \mathbf{v}_{k} \sim \mathcal{N}\left(0, R_{k}\right),$$ and both [TeX:] $$F_{k-1}$$ and [TeX:] $$H_{k}$$ are [TeX:] $$2 \times 2$$ identity matrix. The measurement [TeX:] $$\mathbf{Z}_{k}$$ is determined by the positional data of the vehicle observed by GPS. Applying the sine and cosine rule to (40) and substituting [TeX:] $$\alpha-\beta \text { with } \gamma, G_{k-1}$$ in (40) are denoted by [TeX:] $$G_{k-1}= [\sin (\gamma) \quad \cos (\gamma)]^{T}.$$ System Model B can be employed to estimate the vehicle position in the localization methods P1 and PU1. However, the method P1 performed in only the prediction phase of the Bayes filtering calculates the position of the vehicle through only the state transition model (40) without using the measurement model (41).

B. SKF-based Positioning Algorithm.

Positioning errors obtained by low-cost INS sensors, such as accelerometer and gyroscope, due to sensor drift are typically larger than those obtained from GPS receiver and digital compass. The sensor drift error means that small errors of INS sensors are gradually integrated into larger errors as time passes. Therefore, in order to solve issues related to inaccuracies that INS sensors inevitably suffer, the integrated GPS/DC method (i.e., P1) is proposed in this paper. This scheme employs the traveled distance calculated by two GPS positions obtained from GPS receiver at time steps k - 1 and k and the heading information from the digital compass as inputs for the state transition model in the prediction phase of the Bayes filtering.

However, the low-cost MEMS sensors still cause the position estimation of the vehicle to have large errors. Thus, we propose the other approach GPS/DC+GPS (i.e., PU1) as a positioning algorithm for improving the accuracy of the position estimate. The GPS/DC+GPS method can provide more reliable localization results by fusing noisy vehicle position data obtained from GPS/DC and measurements of the vehicle position gained by the GPS receiver via the Bayesian filter. A pseudo-code description of the positioning algorithm SKF-based PU1 using System Model B is given by Algorithm 1. In next section, we will focus on the stability analysis for this algorithm.

Since SKF-based PU1 is focused on enhancing the accuracy of the position estimate in the case where GPS signals are available and the initial position of the vehicle for the positioning in our methods can provide reasonable accuracy, it may have two limitations. One limitation is that the positioning algorithms may have large errors during GPS blockage. The other limitation is that the positioning approaches can provide reliable accuracy when the vehicle’s initial position for the position estimate closely matches the actual position. If the initial position of the vehicle deviates from the actual position, the performance of the algorithms may deteriorate.

C. Stability Analysis

Vehicle networks can easily be affected by the abrupt and frequent change in topology. Furthermore, the performance of the positioning algorithm may be disappointing in road environment where GPS outliers due to the multipath or obstruction of GPS signals frequently appear. In this transport network, to consider whether SKF-based PU1 can provide the stable performance for the vehicle state estimation, we need to investigate the stability of SKF-based PU1. From (2) and Algorithm 1, SKF-based PU1 can be written as the following discrete-time state equation.

SKF-based PU1 is defined as a stable positioning system, if

all the eigenvalues of [TeX:] $$W_{p} F_{k-1}$$ in (42) are less than one in magnitude [TeX:] $$\text { (i.e., }\left.\left|\operatorname{eig}\left(W_{p} F_{k-1}\right)\right|<1\right).$$ Since all the eigenvalues of [TeX:] $$W_{p}=R_{k}\left(P_{k | k-1}+R_{k}\right)^{-1}$$ always have the magnitude less than one, and [TeX:] $$F_{k-1}$$ is identity matrix, SKF-based PU1 is asymptotically stable.

VI. EXPERIMENTAL RESULT

In this section, we focus on the performance evaluation of our localization approaches P1 and PU1 proposed in this paper. A set of experiments of road segments in real traffic conditions were performed to validate whether our algorithms can provide an accurate estimate of the vehicle position, using the differential global positioning system (DGPS) and MEMS sensors as in [34], [35].

A. Experimental Setup

Our positioning algorithm was implemented on the smartphone (iPhone 5S) equipped with MEMS sensors, including 3-axis accelerometer (STMicroelectronics LIS331DLH), gy

roscope (STMicroelectronics L3G4200DH), digital compass (AKM AK8975), and GPS receiver (Broadcom BCM4750). The update interval of the positioning sensors (accelerometer, gyroscope, and digital compass) and GPS receiver on the smartphone was 0.01 s and 1 s, respectively. The performance parameters of MEMS sensors are shown in Table 2 and Table 3. Since the Broadcom BCM4750 chip is an assisted GPS (A-GPS) chip, the GPS-based positioning on iPhone5S is operated in the mobile station based (MSB) mode where the location information of the device is calculated with the assistance of cellular andWi- Fi network data. In Table 3, the time to first fix (TTFF) indicates the time required for the GPS receiver to acquire the signals and status information for satellites and to calculate the device’s position, when the GPS receiver is turned on.

Furthermore, we used a pair of DGPS receivers to obtain a reference trajectory: Trimble R8s and Leica ATX-1230 GG. The update rate of the DGPS receivers was 1 Hz. The performance parameters of DGPS receivers are summarized in Table 4. In Table 4, the real-time kinematic (RTK) refers to a technique that uses the carrier-based ranging to improve the positioning accuracy of satellite-based navigation systems.

Fig. 3 shows the configuration of the positioning system implemented with the smartphone and DGPS receivers inside the road test vehicle and DGPS antennas outside the road test ve-

hicle. The reference trajectory of the test vehicle could be determined by the average value of the positional information obtained from the two DGPS receivers. This value was used to evaluate the positioning accuracy of localization methods by comparing it as assumed ground truth with the vehicle position estimated by positioning approaches.

B. Performance Analysis for P1

To verify the performance of the prediction method P1, the results obtained from its position estimate are analyzed through comparisons with those obtained by different prediction meth

ods P2 and P3, in terms of the localization accuracy and computational time.

Fig. 4 shows a map that consists of the road segments used to evaluate the performance of P1. The yellow, violet, and green lines represent the results of the position estimate obtained by P1, P2, and P3, respectively. The red line indicates the reference trajectory as an assumed ground truth, which is determined by two DGPS receivers.

Table 5 represents the average positioning error and computational time obtained from the experimental result of the prediction algorithms in road segments represented in Fig. 4. In this paper, the positioning error denotes the distance difference between the position value of the test vehicle obtained from DGPS receivers and the vehicle position calculated by the positioning algorithms in Table 1, which is measured in meters. Also, the computational time refers the wall-clock time in seconds required to perform the localization methods on the smartphone. As can be shown in Table 5, the value of the positioning error obtained by P1 is much smaller than that obtained from P2 and P3. We can analyze in more detail the value of positioning error by observing Fig. 5, which indicates the value of the positioning error over time for each method. In this figure, the values of the positioning error of all the methods rise starting from 200 s due to sensors drift errors, especially in P2 and P3. The values of the localization error in Fig. 5 denote that P1 has higher positioning accuracy than P2 and P3 in the same road section.

Furthermore, as can be seen in Table 5, the average value of the computational time obtained from P1 is much smaller than that of P2 and P3. These results indicate that P1 is more appropriate for the real-time processing of the vehicle positioning with high accuracy, compared to P2 and P3. Unlike P2 and P3, because P1 does not leverage INS sensors (accelerometer and gyroscope) that are subject to sensor drift errors and require much time for the position estimate, it can offer more accurate positioning results and can save more computational time than P2 and P3.

C. Performance Analysis for SKF-based PU1

In this subsection, the performance of SKF-based PU1 is compared with positioning algorithms PU2 and PU3 based on Bayesian filters, such as KF, UKF, SKF, and PF, in terms of the positioning accuracy and computational time.

Fig. 6 shows several road configurations used to evaluate the performance of SKF-based PU1: Teheran Street (a), an intersection (b), a normal road (c), and a tunnel (d). Teheran Street (a) represents the road environment in which outliers in GPS measurements can be easily caused by the multipath effect and frequent blocking on GPS signals due to many tall buildings. Therefore, the test vehicle in this road environment is slowly moving to avoid the problems due to the poor GPS signal condition. The intersection (b) indicates curved road where the vehicle is moving at low speed with good GPS signal, and the normal road (c) indicates straight road configuration with good GPS signal condition. On the contrary, the tunnel (d) reflects the road condition where the GPS signal is completely blocked. Table 6 summarizes the main features of the different road scenarios used in our experiments.

C.1 Performance Evaluation of SKF

Table 7 represents the average positioning error obtained from positioning algorithms PU1, PU2, and PU3 based on Bayesian filters in road configurations in Fig. 6. As can be seen in Table 7, the values of the vehicle positioning error from the SKF closely match those from the KF for all the road scenarios, since both SKF and KF are functionally equivalent when [TeX:] $$H_{k}=I$$ as described in Section IV. Moreover, since the positioning algorithms used for the vehicle navigation in this paper are based on a linear system model as described in Section V.A, the accuracy of the position estimate calculated using both KF and SKF can provide a more accurate value than that of both UKF and PF that are typically suitable for nonlinear system environments. These results denote that while the SKF is simple and intuitive to implement, it can achieve competitive performance compared to KF, UKF, and PF.

Table 8 indicates the average value of the computational time for positioning algorithms PU1, PU2, and PU3 based on Bayesian filters. For all the positioning approaches, the difference between the average values of the computational time required for the estimate of the vehicle position using the SKF and other filtering approaches except PF is not so significant. Nevertheless, as shown in Fig. 7, which shows cumulative distribution function (CDF) distribution for the average value of the computational time for filtering methods using PU1, particularly in the zoomed view of this figure, the use of the SKF is still beneficial. These results indicate that the SKF is more appropriate for the vehicle navigation system that requires faster real-time process compared with KF, UKF, and PF.

As shown in Algorithm 1, the SKF algorithm can provide the formal simplicity for the KF that requires less computational time than UKF and PF. For example, the model state in the SKF is estimated without the calculation of the Kalman gain used in the KF. Therefore, the SKF requires less computational cost than the KF, because the number of the computations required for the state estimation in the SKF is smaller than that of the KF.

C.2 Performance Evaluation of PU1

To verify the validity of PU1, the positioning results of PU1 are compared with those of PU2 and PU3. As shwon in Table 7, apart from PU2 in intersection scenario, the positioning errors of PU1 for all Bayes filters and road configurations are smaller than those of PU2 and PU3. Although PU2 has the localization performance comparable to PU1, it consumes more energy for the position estimate due to the use of the additional INS sensor (i.e., accelerometer) than PU1. Thus, PU2 may not be suitable to be implemented on mobile devices (e.g., smartphone and tablet PC) that require the high energy-efficiency. The energyefficiency of positioning algorithms is addressed in more detail in the next subsection.

Fig. 8 represents the zoomed view of the vehicle position estimate for PU1, PU2, and PU3 based on the SKF in road conditions in Table 6 and Fig. 6. In Fig. 8, positional data obtained from low-cost GPS receiver on iPhone 5S and two DGPS receivers (Trimble R8 Model 3 GPS and Leica ATX-1230 GG) are schematically represented by triangle and placemark square symbols, respectively. The results of the position estimate of PU1, PU2, and PU3 are illustrated by diamond, polygon, and circle symbols, respectively. As can be seen in Fig. 8, PU1 can provide the higher positioning accuracy compared with measurements of the low-cost GPS receiver and positioning results of PU3. The improvements in the accuracy of the position estimate are much clearer in the figure of the experiments carried out in Teheran Street [i.e., Fig. 8(a)] where outliers in GPS measurements can be easily caused by the multipath effect and frequent blocking on GPS signals due to many tall buildings.

Since GPS signals are completely blocked in tunnel scenario, the estimate of positioning error of the positioning methods using GPS and DGPS receivers is not feasible. Therefore, when the vehicle goes into tunnel, positioning algorithms using GPS and DGPS positional information (PU1, PU2, and PU3) are converted into the dead-reckoning algorithm that consists of the accelerometer and digital compass (i.e., P2). Since the sampling rate of the accelerometer and digital compass is 100 Hz, the time interval of the vehicle positioning in tunnel is very short, as shown in Fig. 8(d). Moreover, until the vehicle passes through tunnel, i.e., until the next valid GPS update, the uncertainty (error covariance) of the positioning algorithm increases exponentially, since the algorithm cannot update GPS measurements due to the blockage of the GPS signal, as shown in Fig. 9.

For the computational time, PU1 requires shorter computational time compared with PU2 and PU3, as shown in Table 8. This result indicates that PU1 is suitable for the vehicle positioning system in vehicle networks featuring the abrupt and frequent change in topology. Unlike PU2 and PU3, since PU1 does not employ any INS sensors (accelerometer and gyroscope) that result in large localization errors due to sensor drift and bias and require much time for the positioning, it can achieve higher positioning accuracy and can consume less computational time, compared to PU2 and PU3.

D. Aspects of Energy-Efficiency

In this subsection, our positioning algorithm PU1 is evaluated in terms of the energy-efficiency. Fig. 10 represents the energy consumption rate and CPU usage rate of localization approaches based on Bayesian filters for 10 minutes. The energy consumption rate and CPU usage rate are obtained from some statistics recorded in log messages reported after the positioning process completion through the specialized tool used to profile iOS applications, known as Instruments [36]. As can be seen in Fig. 10(a) and Fig. 10(b), the use of INS sensors (accelerometer and gyroscope) and a high CPU usage rate have a great influence on the energy consumption. Since most smartphones use CPU to directly control the sensors, the continuous use of the INS sensors with higher data rate than digital compass (see Table 2) induces considerable energy overhead and CPU usage [37]. Therefore, both PU2 and PU3 using the INS

sensors lead to higher power consumption and CPU usage than PU1 not using INS sensors. Furthermore, the PF with a high percentage of CPU usage consumes more energy than KF, SKF, and UKF, particularly in PU2 and PU3. These results indicate that PU1 based on the SKF with a low CPU usage rate is suitable to be implemented on mobile devices that require high energyefficiency.

VII. CONCLUSION

For mobile devices, energy efficiency is one of the main concerns. Location-based services on smartphones require considerable battery power due to high energy consumption of INS sensors and GPS modules. Prolonged use may accelerate the battery consumption of your smartphone. We have shown that smartphone-based GPS/INS localization schemes (PU2 and PU3) can consume much energy. In addition, INS sensors of a smartphone can lead to very noisy localization results, since small errors in INS measurements are gradually integrated into larger error over time.

To solve the problems with INS sensors, we have introduced a navigation system that utilizes only the GPS receiver and digital compass without INS sensor. This can provide better positioning accuracy and can consume less battery power than smartphone-based GPS/INS localization algorithms. Nonetheless, GPS receiver and digital compass on smartphones can still cause large localization errors because of GPS outliers due to multipath and obstruction of GPS signals in urban environments, and the accuracy of digital compass is vulnerable to surrounding magnetic sources or disturbances.

For this reason, we have proposed the positioning method that achieves more reliable positioning accuracy by integrating noisy measurements obtained from GPS module and digital compass using the SKF algorithm. The SKF algorithm can provide the formal simplicity for the KF by assuming that the measurement model H is equal to identity matrix. For instance, the model state in the SKF is estimated without the calculation of the Kalman gain used in the KF. Hence, the SKF requires less computational cost than the KF, since the number of the computations needed for state estimation in the SKF is smaller than that of the KF. The SKF-based vehicle positioning system consists of two phases: prediction and update. For the prediction step, the position of the vehicle is obtained through both the traveled distance computed by two GPS positions and heading information from digital compass. During the update phase, the position of the vehicle is corrected by combining both the positional information obtained by the prediction phase and the GPS position of the vehicle using the SKF.

To evaluate the performance for our scheme, we have implemented the algorithm on the smartphone and have carried out various road tests using the test vehicle in real environments. Experimental results show that the SKF-based localization approach can provide competitive localization results while using less energy, compared with smartphone-based GPS/INS positioning approaches based on conventional Bayes filters, such as KF, UKF, and PF.

Despite the benefits of the SKF for the vehicle position estimate, the SKF requires the linear state transition model F and linear measurement model H, and it even assumes that the measurement model is equal to identity matrix. This may limit the effectiveness of the SKF in some real world situations, in which nonlinear models appear frequently. That is, when the model dynamics are nonlinear, or when the measurements are nonlinearly related to the model state, the SKF has to linearize state transition and measurement models on the assumption that the measurement model is equal to identity matrix.

The UKF can overcome the shortcomings of the SKF, which require linear models and make an unnecessary assumption about measurement model. The UKF provides a couple of practical advantages over the SKF: 1) It need not to compute the Jacobian or tangent linear model for nonlinear models with a high computational cost to linearize nonlinear models; and 2) it estimates the model state through fully nonlinear model operators using the deterministic sampling scheme that requires no linearization regarding nonlinear models [38].

As future work, we will improve the UKF to accomplish reliable and accurate positioning performance with less computational cost for nonlinear models, eliminating the need for model linearization and making no assumption about the measurement model as in the SKF.