Sage Journals: Discover world-class research

Abstract

In VANETs, frequent beacon broadcasting can lead to high bandwidth consumption and channel congestion. In this paper, a position prediction based beacon approach is proposed to reduce beacon frequency and decrease bandwidth consumption. Vehicles track their neighbors using the predicted position instead of using periodic beacon broadcasting. Only when the prediction error is higher than a predefined tolerance will a beacon broadcasting be triggered. For improving the prediction accuracy, we classify the motion of vehicles into two typical patterns: a constant speed pattern and a maneuvering pattern. A maneuver detection module is responsible for recognizing current motion patterns, and a variable dimension filter that can switch dynamically between the two patterns is employed to generate high accurate position prediction. The simulation results show the proposed scheme can reduce significantly the number of beacons than three existing beacon approaches.

1. Introduction

Vehicular ad hoc networks (VANETs) are receiving more and more attentions from academia and industry, since various kinds of applications can be provided for improvement of road safety and other potential benefits. VANETs generally consist of on-board unit (OBU), roadside unit (RSU), and central trusted authority (TA). Vehicles can communicate with each other (vehicle-to-vehicle, or V2V) as well as with a nearby RSU (vehicle-to-infrastructure, or V2I) [1]. This immediately enables driving safety applications, that is, cooperative collision avoidance, by detecting potentially dangerous situations and making warning messages available beyond the driver's horizon of awareness. Recent researches have shown that road safety can be improved significantly using a V2V communication based cooperative vehicle safety (CVS) system [2].

Two types of messages are used in driving VANETs safety-related applications [3]: periodic vehicle tracking messages and event-driven alert messages. The periodic vehicle tracking messages (beacon messages) are broadcasted by each vehicle to inform its neighbors with its current state (position, velocity, heading, and other necessary measures). Receivers parse these messages, accurately track the position of the target vehicle, and predict potential collisions. When an abnormal condition (such as an airbag explosion, a crash) or a sudden change of vehicular state (such as a hard braking) is detected, alert messages are generated and disseminated with the highest priority.

Due to the high velocity of vehicles, the position information contained in beacon messages becomes outdated very quickly. Existing solutions handle this problem by increasing beacon frequency; that is, a 10 Hz beacon frequency is suggested in [3]. The main issue of this design is that it leads to heavy channel overhead. In very dense areas such as urban regions, frequent beacon broadcasting can cause channel congestion. Moreover, according to the WAVE/IEEE 802.11p standard [4], alert messages and beacon messages are operated on 5.9 GHz band and share a common channel referred to as the “control channel.” Neighbors cannot successfully decode beacon messages, and the reliability of dissemination of alert messages can be degraded. It is particularly critical for the 802.11p standard that is based on the CSMA/CA protocol that could increase its instability and overload its operation. As defined by FCC (Federal Communication Commission of the USA) [5], we assume a single 10 MHz wide control channel is used. The data rate provided by IEEE 802.11p ranges from 3 to 27 Mbps. The size of beacon messages can reach more than 800 bytes due to security-related overhead [6]. In dense areas, for instance, with more than several hundred vehicles broadcasting beacon message at a frequency of 10 Hz at once, the channel load can exceed the available bandwidth provided by 802.11p.

In this paper, we propose a position prediction based beacon rate (PPBR) approach to alleviate high channel occupancy caused by frequent beacon broadcasting. In PPBR, vehicles run a program to predict the position of each neighbor. The predicted position is used to track neighbors when the prediction error is less than a tolerable level. Thus, beacon frequency can be reduced effectively if the prediction accuracy is high enough. Our contribution is threefold in this paper. Firstly, in order to provide accurate enough position predictions, we propose a prediction approach based on a variable dimension filter (VDF). Two vehicular dynamic models are established to capture motion characteristics of vehicles according to two typical motion patterns, nonmaneuvering and maneuvering. A maneuver detector is responsible for recognizing the current pattern and dynamically switching the filter between two dynamic models. Secondly, a large-scale vehicular traces dataset based analysis signifies temporal stability of vehicular mobility. The probability that vehicles do not change their velocity and heading is as high as 84.9% and 40.8% over 1 s and 5 s time window, respectively. This demonstrates that it is feasible to predict vehicular position within the next several seconds in the highly dynamic vehicular mobility scenario. Finally, we test our approach with a simulation to investigate the effects under two different traffic scenarios. Compared to existing approaches using fixed-rate 3 Hz beacons, extended Kalman filter (EKF), and time series forecasting (TSF), the simulation results show that the proposed scheme can reduce significantly the number of beacons.

The remainder of this paper is organized as follows. We discuss the related work in Section 2. Section 3 gives a detailed description of the proposed PPBR approach. Section 4 presents the simulation setup and the results analysis. Finally, we draw concluding remarks in Section 5.

2. Related Work

To avoid channel overload caused by periodic beacon messages, researchers have focused on the various aspects of the adapted beacon mechanism, and some solutions have been proposed to reduce channel overhead [7]. In our opinion, these existing solutions can be classified into two categories: transmission power control based schemes and frequency control based schemes.

Torrent-Moreno et al. [8] assumed that two types of messages are used for traffic safety-related vehicle-to-vehicle communication: beacon messages and alter messages. Frequent beacon broadcasting leads to saturated channels, while interference and packet collisions can degrade the performance, causing failure of the reception of safety-related information. A distributed transmit power control method was proposed to control channel load caused by periodic beacon messages below a predefined upper bound. A strict fairness criterion was proposed under which not only available bandwidth is reserved for the high priority alter messages, but also vehicles are treated with “equal rights” for channel occupation. A realistic traffic scenario based simulation was drawn using an ns-2 simulator. The results show that the proposed scheme always performs better than existing fixed-power beacon scheme under all simulation scenarios.

Fallah et al. [9] argued that physical dynamics of vehicles, the process of tracking neighbors, and the communication process should be tightly coupled in the design process of adapted beacon mechanisms. A design method of such a system was proposed from a cyber-physical system (CPS) standpoint. The system architecture, subcomponent modeling, and their interaction method were given the design procedure for such a tightly coupled system, for simplicity. The simulation results proved that the tracking accuracy can be significantly improved due to coupling the design of different components of a CPS system.

Since beacon activity is visible to the application layer, it is feasible to dynamically adjust beacon frequency according to vehicular density from an application layer standpoint. Park and Kim [10] proposed an application-level adapted frequency control scheme of beacon broadcasting. The proposed scheme estimates traffic density and adjusts beacon frequency by imposing a timing structure on applications in the absence of feedback information from the MAC layer. The simulation results show that the proposed scheme can increase the delivery ratio by over 20%.

Boukerche et al. [11] attempted to add some historical state information (such as past position, velocity, and heading) into periodic beacons for vehicles to know the sender's current position and for them to predict its position within the next few seconds. If the prediction error is less than a predefined reasonable threshold, the predicted position can be used for tracking neighbors instead of using the one through beacon broadcasting. Thus, beacon frequency can be decreased to a low level. The proposed scheme works well when vehicles are moving under a constant velocity, but it is difficult to precisely predict the position in maneuvering when the vehicular velocity changes suddenly. Rezaei et al. [12] proposed a position prediction based beacon rate adaption scheme. Vehicles run a Kalman filter to predict the future position for vehicles. A beacon is triggered only if the prediction error is higher than a predefined maximum tolerance. For the same reason, it loses accuracy in maneuvering state.

Zrar Ghafoor et al. [13] proposed a fuzzy logic based adaptive beaconing rate control approach. The proposed scheme considered traffic characteristics, the percentage of vehicles traveling in the same direction, and the state of vehicles as the inputs of the fuzzy decision making system in order to tune the beaconing rate according to the vehicular traffic characteristics. Since reducing the beacon rate can decrease the accuracy of shared position information, Schmidt et al. [14] proposed a scheme for an adaptive beacon rate according to the VANET traffic behavior and tried to make a tradeoff between the accuracy of position information and channel occupancy. However, some traffic parameters, such as direction, density, and state of a vehicle, have not been considered in the scheme.

Since vehicular trajectory commonly can be represented by a series of time-ordered position sampling, time series forecasting is an effective method to predict vehicular further position based on its current and past position. Autoregressive moving integrated average model is an early method which assumes every time series can be regarded as the realization of a stochastic process. Its variants and extensions have popularized use in many fields of science and engineering. In recent years, artificial neural networks (ANN) model have exhibited superior performance and attracted a great deal of attention in the time series forecasting field. Its unique characteristics, that is, nonlinear, having no requirement for an explicit underlying model, make it more flexible and universal. Heravi et al. [15] made a comparison study between ANN and linear model using 24 time series measuring the annual change in monthly seasonally industrial production in three countries. Zhang and Kline [16] investigated the effectiveness of several data preprocessing and modeling approaches based on a large data set of 756 quarterly time series. They identified the best models using both parametric and nonparametric statistical analyses, and the analysis results have shown that simpler models achieve higher performance generally than more complex models. Yan [17] proposed an automatic artificial neural networks modeling scheme that is based on a special type of neural network, generalized regression neural network (GRNN). Since multiple GRNNs were fused, the proposed scheme can effectively model large-scale business time series.

3. The Proposed Scheme

The general architecture of the proposed PPBR approach is shown in Figure 1. In this architecture, the target vehicle, denoted by i, runs four modules. A localization module is responsible for obtaining absolute vehicular position using localization devices, that is, GPS. Its position output is called “measured position.” A maneuver detector is used to recognize the current motion pattern of the vehicle. A Kalman filter-based position predictor, called “self-predictor,” generates “predicted position” of the vehicle. The prediction error is defined as the difference between “measured position” and “predicted position” which is calculated by a beacon generator at every discrete timeslot. A beacon message is generated and broadcasted only if the prediction error is higher than a predefined tolerance. On the other hand, the neighbors of vehicle i run a copy of the self-predictor, called “remote-predictor.” If no beacon message is received at a timeslot, the predicted position generated by the remote-predictor is used to track the position of vehicle i. When a beacon message is received, the measured position of vehicle i contained in the beacon is used by its neighbors to correct the prediction error.

Figure 1

System architecture.

In the aforementioned PPBR approach, the difficulty for effectively reducing the beacon frequency can be understood as providing a high enough accuracy of position prediction. Commonly, the motion process of vehicles can be classified into two patterns: nonmaneuvering and maneuvering [18]. In the nonmaneuvering pattern, vehicles keep rectilinear motion with constant velocity. The maneuvering pattern refers to changes in velocity or heading caused by acceleration, braking, or turning operations taken by drivers. Due to the lack of adaptive mechanisms, existing EKF based position prediction schemes [19, 20] cannot cope with rapid changing of vehicular motion pattern; thus, they fail to provide high accuracy prediction position. Firstly, the nonmaneuvering filter is based on the nonmaneuvering model. It loses some accuracy because the filtering gain is too small to capture maneuvers. Moreover, the maneuvering filter results in performance degradation relative to the nonmaneuvering filter whenever the vehicle is moving with constant velocity. In this paper, we employ a variable dimension filter (VDF) [21] in which a maneuver detector (Figure 1) is integrated. The filter can recognize the current motion pattern of vehicles and switch dynamically its work mode. The filter runs in a normal mode in the absence of any maneuvers, when a lower order nonmaneuvering model is used. Upon detecting a maneuver, the filter switches to a higher-order maneuvering model.

3.1. Vehicular Dynamic Models

According to the two aforementioned motion patterns, we establish the nonmaneuvering model and maneuvering model as follows.

Nonmaneuvering Model. In the absence of a maneuver, the vehicular velocity is assumed to be a constant with some process noise that represents small velocity fluctuations and unpredictable modeling error. We assume that vehicular motion can be represented by the following state-space model:

\begin{matrix} X_{k} = Φ X_{k - 1} + W_{k} . \end{matrix}

(1)

Here, $X_{k}$ is the state vector of vehicles at discrete timeslot k, $W_{k}$ is the process noise (assumed to be a white Gaussian noise vector with mean zero), Φ is the state transition matrix, and

\begin{matrix} X_{k} = {[x (k), v_{x} (k), y (k), v_{y} (k)]}^{T}, \end{matrix}

(2)

where

x (k)

y (k)

v_{x} (k)

, and

v_{y} (k)

are the x- and y-components of the vehicular position and velocity at time k. We assume the vehicular absolute position can be measured using the localization module. The measurement equation is established as follows:

\begin{matrix} Z_{k} = H X_{k} + V_{k} . \end{matrix}

(3)

Here, $Z_{k}$ is measurement vector, $V_{k}$ is the measurement noise vector, and H is the measurement transformation matrix. Moreover, we assume that $W_{k}$ and $V_{k}$ are independent, and the covariance is

\begin{matrix} Cov (W_{k}, W_{j}) = E [W_{k} W_{j}] = Q ζ_{k j}, \\ Cov (V_{k}, V_{j}) = E [V_{k} V_{j}] = R ζ_{k j} . \end{matrix}

(4)

Maneuvering Model. When the driver performs a control on the target vehicle, such as braking, turning, or accelerating, the instantaneous acceleration of the target vehicle deviates from zero-mean, and using nonmaneuvering model will lead to high prediction error. For ensuring high accuracy, the instantaneous acceleration of the target vehicle should be estimated in real-time. Considering a maneuver commonly continues for several seconds, for example, when a driver performs an acceleration operation and the target vehicle has a positive value of instantaneous acceleration at time k, it is likely to be accelerating at $t + τ$ for a small time interval τ. Thus, it is reasonable that modeling the instantaneous acceleration as a time series and an autoregression model can be established as follows:

\begin{matrix} a (k) = \sum_{i = 1}^{p} φ (i) a (k - i) + u (k) . \end{matrix}

(5)

Here, p is a positive integer, $φ (1), φ (2), \dots, φ (p)$ are parameters, $\{u (k)\}$ is a white noise series with mean zero. The augmented state vector of the target vehicle can be represented as

\begin{matrix} X_{k}^{m} = [\begin{bmatrix} X_{k} \\ A_{k} \end{bmatrix}], \end{matrix}

(6)

where

A_{k} = {[a_{x} (k), a_{y} (k), a_{x} (k - 1), a_{y} (k - 1), \dots, a_{x} (k - p), a_{y} (k - p)]}^{T}

in which

a_{x} (k)

and

a_{y} (k)

are the x- and y-components of the instantaneous acceleration

a (k)

3.2. Position Prediction and Beaconing Schemes

In the self- and remote-predictor, a Kalman filter is responsible for predicting the future position of the target vehicle based on its past state. The prediction procedure at the target vehicle is as follows. Firstly, the target vehicle predicts the instantaneous acceleration $a (k)$ based on its past value $a (k - 1), a (k - 2), \dots, a (k - p)$ , if the maneuvering model is used currently. For convenience of calculations, we use a constant for parameter p. The target vehicle estimates parameters $φ (1), φ (2), \dots, φ (p)$ using Yule-Walker equation [22]. After the instantaneous acceleration $a (k)$ is predicted, the target vehicle calculates the one-step-ahead state prediction of time k through

\begin{matrix} {\hat{X}}_{k | k - 1} = Φ {\hat{X}}_{k - 1 | k - 1} . \end{matrix}

(7)

The measurement residual ${\tilde{Z}}_{k}$ is calculated through

\begin{matrix} {\tilde{Z}}_{k} = Z_{k} - H {\hat{X}}_{k | k - 1} . \end{matrix}

(8)

If ${‖{\tilde{Z}}_{k}‖}^{2}$ is greater than the predefined position tolerance γ, the target vehicle generates and broadcasts a beacon message to inform its neighbors with new measured position, and the measurement residual also is used to correct the error of the one-step-head state prediction:

\begin{matrix} {\hat{X}}_{k | k} = {\hat{X}}_{k | k - 1} + K_{k} {\tilde{Z}}_{k} . \end{matrix}

(9)

Here, $K_{k}$ is the Kalman gain and can be derived through

\begin{matrix} K_{k} = P_{k | k - 1} H_{k}^{T} {[H_{k} P_{k | k - 1} H_{k}^{T} + R_{k}]}^{- 1}, \\ P_{k | k - 1} = Φ_{k, k - 1} P_{k - 1 | k - 1} {Φ^{T}}_{k, k - 1} + Q_{k - 1}, \\ P_{k | k} = [1 - K_{k} H_{k}] P_{k | k - 1} . \end{matrix}

(10)

Otherwise, ${\hat{X}}_{k | k} = {\hat{X}}_{k | k - 1}$ . Besides, when a new neighbor vehicle just gets into the communication range of the target vehicle, the prediction error commonly is high since no historical information of the target vehicle is available. The prediction error decreases only after several beacons are received. We solve this problem by containing some additional parameters in each beacon message broadcasted by the target vehicle, that is, the Kalman gain $K_{k}$ , the instantaneous acceleration $a (k - 1), \dots, a (k - p)$ , and parameter $φ (1), φ (2), \dots, φ (p)$ .

The prediction procedure at the neighbor vehicle is as follows. If no beacon message is received at time k, the neighbor vehicle calculates one-step-ahead state prediction ${\hat{X}}_{k | k - 1}$ according to 7 and obtains predicted position of the target vehicle. Otherwise, if a beacon is received, the neighbor vehicle obtains the measured position from it, calculates the measurement residual, and updates the filter according to 8 to 10.

3.3. Maneuvering Detection and Model Switching

The maneuvering detection module uses a double logic decision [21] to detect the starting and ending of a maneuver. A typical operation process is shown in Figure 2. Since the velocity of vehicles is assumed to be constant with a small amount of Gaussian noise in the nonmaneuvering model, the measurement residual sequence should have a mean of zero if no maneuver occurs. Thus, it is reasonable to assume a maneuver has occurred if the measurement residual sequence deviates significantly from zero. The target vehicle calculates the measurement residuals at every timeslot and sums them over a sliding window $W_{s}$ . A chi-square test is used to judge if the measurement residual deviates significantly from zero. When a maneuver is detected, a decision window $W_{d}$ with N timeslots is triggered, and a parallel maneuvering model based filter is initialized. At the end of the decision window, a second decision is activated to verify if a maneuver indeed occurred by comparing the prediction errors of the two filters. If the maneuver-based filter is more precise than the nonmaneuver filter, it is supposed that a maneuver has indeed occurred. The nonmaneuver model will stop. Otherwise, the first decision is denied.

Figure 2

Sequencing of operations.

The First Decision. A chi-square significance test is employed to detect if a maneuver has occurred. The target vehicle calculates the measurement residual ${\tilde{Z}}_{k}$ and its normalized squared $δ_{k} = {\tilde{Z}}_{k}^{T} S^{- 1} {\tilde{Z}}_{k}$ at every timeslot. Since it is well known that ${‖y - \bar{y}‖}_{Σ^{- 1}}^{2} = (y - \bar{y})^{T} Σ^{- 1} (y - \bar{y})$ is $χ_{n}^{2}$ distributed for any n-dimensional Gaussian random vector $y ~ N (\bar{y}, Σ)$ , the chi-square test provides a check of the goodness of fit to judge if y indeed has the assumed distribution:

\begin{matrix} δ_{k} ~ χ_{n_{z}}^{2}, δ_{k}^{s} ~ χ_{s n_{z}}^{2} . \end{matrix}

(11)

Here, $n_{z}$ is the dimension of vector z and s is the length of the decision window. $δ_{k}^{s}$ is the sliding sum of the measurement residual ${\tilde{Z}}_{k}$ over the decision window $[k - s + 1, k]$ and is calculated through

\begin{matrix} δ_{k}^{s} = \sum_{j = k - s + 1}^{k} δ_{j} . \end{matrix}

(12)

It is supposed that a maneuver occurs if the following equation holds:

\begin{matrix} δ_{k}^{s} > λ = χ_{s n_{z}}^{2} (α) . \end{matrix}

(13)

Here, $1 - α$ is the level of confidence that commonly is set to 95% or 99%.

The condition for switching to the nonmaneuver model is defined to be when the sliding sum of the measurement residuals of the maneuver model ${\tilde{Z}}_{k}^{m}$ falls below some threshold λ:

\begin{matrix} \sum_{j = k - s + 1}^{k} {\tilde{Z}}_{k}^{m}^{T} S^{- 1} {\tilde{Z}}_{k}^{m} < λ . \end{matrix}

(14)

The Second Decision. This decision compares the sum of the measurement residual sequences for two parallel filters and determines if a model switching is required. The maneuvering filter will be performed if

\begin{matrix} \sum_{j = k - s + 1}^{k} {\tilde{Z}}_{k}^{m} < \sum_{j = k - s + 1}^{k} {\tilde{Z}}_{k} . \end{matrix}

(15)

Otherwise, the nonmaneuvering filter is performed.

Once the target vehicle decides to switch the current model, it generates and broadcasts a beacon message to inform its neighbors to perform a synchronous switching operation.

4. Simulation

In this section, we conduct a large-scale real world vehicular traces based experiment to analyze the characteristics of vehicular mobility. Moreover, we evaluate the performance of the proposed PPBR approach and compare it with three existing beacon approaches.

4.1. Vehicular Mobility Analysis

The vehicular traces dataset, collected by Microsoft China Research Institute [23], contains the GPS trajectories of 10,357 taxis in a period of over 7 days in Beijing, China. The trajectory for each taxi is represented by a sequence of time-ordered sampling points collected by an on-board GPS, each of which contains the timestamp, latitude, and longitude. The total number of sampling points is about 15 million. The sampling interval is between 1 s and 10 minutes, and the intervals below 10 s account for 23.6% of the total. Since we only focus on short-term position prediction, sampling points with an interval above 10 s are abandoned.

We define the normalized velocity change (NVC) [18] as follows:

\begin{matrix} NVC (i, t) ≜ \frac{{‖\vec{v} (i, t) - \vec{v} (i, t - 1)‖}^{2}}{mea n_{i, t} ({‖\vec{v} (i, t)‖}^{2})} . \end{matrix}

(16)

Here, $v (i, t)$ is the velocity vector of vehicle i at time t. ${‖\cdot‖}^{2}$ is the $ℓ_{2}$ -norm and $mea n_{i, t} ({‖\vec{v} (i, t)‖}^{2})$ calculates the mean for all ${‖\vec{v} (i, t)‖}^{2}$ . We calculate the sum of NVC over a time window, and its cumulative distribution function (CDF) is given in Figure 3. It can been seen that the probability that NVC remains zero is 84.9%, 40.8%, and 19.1% over time windows of 1 s, 5 s, and 10 s, respectively. Over a time window of 1 s, NVCs below 0.1 account for more than 99% of the total. It proves that the vehicular motion has temporal stability in real-world traffic scenarios. Since vehicles rarely change velocity, a short-term position prediction is feasible and high accuracy can be achieved in this situation. However, during the rest of the time, the velocity vector changes with time. Moreover, the temporal stability may vary with different traffic scenarios. Once a maneuver occurs, velocity changes make it more difficult to precisely predict vehicular position, and the accuracy may be degraded. Thus, to effectively reduce beacon frequency, an adapted mechanism is necessary to achieve high enough accuracy.

Figure 3

Temporal stability of vehicular mobility.

4.2. Performance Evaluation

4.2.1. Simulation Setting

In this section, we simulate the proposed PPBR approach to evaluate its performance and compare it with existing beacon approaches. We implemented the proposed PPBR approach and integrated it into a NS-2 simulator. All simulations were done on a Linux computer with an Intel Core Duo 2.66 MHz CPU and 4 GB RAM. The version of gcc is 4.6.3. We set maximal beacon interval as 2 s. Moreover, the length of the discrete timeslot is set as 0.1 s. The length of the sliding window $W_{s}$ and the decision window $W_{d}$ is 1 s. In the chi-square significance test, the significance level α is set as 0.05. The simulation parameters are shown in Table 1. Two traffic scenarios are established using the traffic simulation software SUMO [24].

Table 1

Simulation parameters setting.

Parameter	Value
Simulation area size	2 × 2 km
Vehicular density	100 vehicles/km
Wireless transmission range	250 m
MAC layer protocol	802.11 DCF
Channel bandwidth	3 M bps
Beacon message size	1000 bytes
Simulation time	720 seconds
Settling time	120 seconds
Maximal beacon interval	2 seconds
Position tolerance	1 m

Traffic Scenario 1. This scenario uses the trajectory of a single vehicle that includes maneuvering and nonmaneuvering motion patterns. As shown in Figure 4, the vehicle keeps rectilinear motion with constant speed $v = 13.9$ m/s until $t = 6.6$ s when it undertakes a braking action. Its velocity drops to zero at 14.4 s and remains at rest until $t = 21$ s. Then, it accelerates and takes a 90-degree left-hand turn. Its velocity reaches 7.7 m/s at $t = 30$ s.

Figure 4

Traffic scenario 1.

Traffic Scenario 2. As shown in Figure 5, an urban traffic scenario is established based on the road topology of Xi'an city, China, using the electronic map provided by the OpenStreetMap project [25]. The size of the simulation area is 2 × 2 kilometers, and all roads are set to be two-way, with three lanes per direction. The maximum velocity of vehicles is set to be 50 km/h, and the traveling route is chosen randomly. For each simulation run, the total simulation time is 720 seconds. We used a settle time of 120 seconds at the beginning of each simulation run to avoid the effect of transient behavior on the results. Each simulation is run 50 times repeatedly and the points in the following plots are the average of all simulation runs.

Figure 5

Urban traffic scenario.

The following metrics are employed to evaluate performance of the proposed PPBR approach. The prediction error is defined as root mean square (RMS) value of the measurement residual. The beacon interval is the average number of timeslots between two consecutive beacons broadcasted by a vehicle. The number of beacons is the average number of beacon messages per vehicle during the simulation. The reception ratio is the probability that the neighboring vehicle located within the communication range of the target vehicle successfully decodes a beacon message.

4.2.2. Simulation Results

Firstly, we evaluate the prediction error and the beacon interval of the proposed PPBR approach under traffic scenario 1 and compare it with the EKF based beacon approach introduced in [12] and the artificial neural network based TSF approach that use a multilayer perceptron model [22]. Figure 6 shows the prediction error of the three approaches with time. It is seen that EKF and PPBR appear to be equally effective when no maneuver occurs (from 14.4 s to 20.4 s). This is due to the fact that the velocity and heading of the vehicle do not change in the nonmaneuvering pattern; thus, both predictors can achieve a high accuracy of prediction. However, PPBR has a significantly lower RMS error than the EKF based predictor during the remaining maneuvering periods. It can be explained by the fact that the PPBR is able to detect maneuvers and to switch the predictor to the maneuvering model for achieving higher accuracy. For the same reasons, PPBR achieves smaller prediction error than TSF. Moreover, since the system parameters are contained in beacons, it is helpful for neighbor vehicles to rapidly converge the filter error; thus, it can be seen that the prediction error of PPBR is smaller significantly than EKF and TSF from 0 s to 6.6 s.

Figure 6

Prediction error.

Figure 7 shows the beacon interval of three approaches as a function of time. It is seen that the beacon interval of the three approaches reaches a predefined maximum of 2 s in the nonmaneuvering period. It proves that the three approaches can achieve sufficient accuracy. Moreover, PPBR achieves significantly higher beacon intervals than the EKF and TSF schemes in remaining maneuvering period.

Figure 7

Beacon interval.

Figure 8 compares the number of beacons generated by PPBR, EKF, TSF, and fixed-rate 3 Hz (FR = 3) beacon schemes under the urban traffic scenario. We notice that the number of beacons in the four approaches is increasing proportionally with time. However, FR = 3 generates many more beacon messages than others. At the end of the simulation, 1800 messages are broadcast for each vehicle in the FR = 3 scheme. On the contrary, only 349, 439, and 490 beacons per vehicle, on average, are generated under the PPBR, TSF, and EKF approaches. Since PPBR can more precisely predict the position of vehicles, it has the smallest number of beacons among four approaches. Compared to FR = 3, EKF and TSF, the proposed PPBR approach can reduce number of beacons by 80.6%, 28.8%, and 20.5%, respectively.

Figure 8

Number of beacons.

We evaluate the tradeoff between accuracy and cost under various average velocities and the result is shown in Figure 9. The result follows the expected behavior where the number of beacons decreases with increasing position tolerance. Even under a minimal position tolerance (0.5 m) only 446 beacons are generated by PPBR when average vehicular velocity is 50 km/h. Comparing to 1800 beacons in the FR approach, 75.2% of beacons are reduced. This demonstrates that the proposed PPBR approach does not lead to significant accuracy loss; thus, it is suitable for high-accuracy tracking applications. Moreover, it can be seen that increasing average vehicular velocity does not lead to significant increase in number of beacons. When velocity reaches 70 km/h, only 478 beacons are generated under 0.5 m position tolerance.

Figure 9

Tradeoff between accuracy and cost.

Figure 10 evaluates the impact of increasing vehicular density on the reception ratio. Since high density of vehicles can aggravate hidden node interference and packet collision, reception ratio decreases significantly with increasing density in all four beacon approaches. PPBR has the highest reception ratio under all values of vehicular density because fewer beacons are generated. Even though the density of vehicles is as high as 200 vehicle/km, 86% of beacons are decoded successfully. The reception ratio is the lowest in the FR = 3 scheme, where only 35% of beacons are decoded under the same vehicular density. This demonstrates that the reliability of beacon dissemination is improved by reduced beacon frequency.

Figure 10

Reception ratio.

Since some beacons are missed, vehicles cannot track the position of targets in real time. We define tracking error as the distance between the vehicular position obtained from beacons and its real position at each discrete timeslot. We evaluate the impact of increasing vehicular density on tracking error of PPBR and make comparison with the FR = 3 approach. The results are shown in Figure 11. As shown in the figure, when vehicular density is at a low level, the position tracking error is smaller than PPBR. It is mainly due to the fact that FR = 3 generates many more beacons than PPBR, and not many of them are lost under low vehicle density. However, its tracking error rapidly increases with increasing vehicle density, while the tracking error of PPBR only increases slightly. The simulation results proved the validity of the proposed PPBR scheme.

Figure 11

Impact of vehicular density.

5. Conclusion

In VANET, vehicles need to exchange information to support various applications. Frequent beacon broadcasting leads to heavy channel load and channel congestion. Since vehicular mobility exhibits temporal stability, a short-term position prediction can be used to update the position of the neighbors; thus, beacon frequency can be reduced effectively. This paper proposes a position prediction based beacon approach. Each vehicle runs a position prediction algorithm to obtain real-time position estimation for its neighbors. Only when the prediction error is higher than a predefined tolerance will beacon broadcasting be triggered. To decrease the error of the position prediction, we classify the vehicular motion process into constant speed patterns and maneuvering patterns. A maneuvering detector module is responsible for dynamically recognizing the current motion pattern and a variable dimension filter is employed to generate position predictions which can switch dynamically between the two patterns, improving accuracy. A real world vehicular traces based analysis shows that the temporal stability of vehicular mobility and the probability that the vehicles do not change speed and heading are 84.9% and 40.8% under 1 s and 5 s time windows, respectively. It proves that a short-term position prediction is feasible and high accuracy can be achieved. The simulation results show that the proposed scheme can reduce significantly the number of beacons than three existing approaches.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Hartenstein

VANET: Vehicular Applications and Inter-Networking Technologies 2010

Chichester, UK

Wiley

Fallah

Y. P.

Huang

C.-L.

Sengupta

Krishnan

Analysis of information dissemination in vehicular ad-hoc networks with application to cooperative vehicle safety systems

IEEE Transactions on Vehicular Technology 2011 60 1 233 247

10.1109/TVT.2010.2085022

2-s2.0-78751677465

CAMP Vehicle Safety Communications Consortium Vehicle Safety Communications Project: Task 3 Final Report: Identify Intelligent Vehicle Safety Applications Enabled by DSRC 2005

Washington, DC, USA

National Highway Traffic Safety Administration, US Department of Transportation

Wireless Access in Vehicular Environment (WAVE) in Standard 802.11, Specific Requirements, IEEE Std. 802.11p/D1.0, February 2006

Federal Communications Commision

Memorandum opinion and order

FCC 2006 06-110

Schmidt-Eisenlohr

Torrent-Moreno

Mittag

Hartenstein

Simulation platform for inter-vehicle communications and analysis of periodic information exchange

Proceedings of the 4th Annual Conference on Wireless on Demand Network Systems and Services (WONS ′07)

January 2007

Obergurgl, Austria

IEEE

50 58

10.1109/wons.2007.340475

2-s2.0-34547498542

Ghafoor

K. Z.

Lloret

Bakar

K. A.

Sadiq

A. S.

Mussa

S. A. B.

Beaconing approaches in vehicular Ad hoc networks: a survey

Wireless Personal Communications 2013 73 3 885 912

10.1007/s11277-013-1222-9

2-s2.0-84890550551

Torrent-Moreno

Mittag

Santi

Hartenstein

Vehicle-to-vehicle communication: fair transmit power control for safety-critical information

IEEE Transactions on Vehicular Technology 2009 58 7 3684 3703

2-s2.0-69749093972

10.1109/tvt.2009.2017545

Fallah

Y. P.

Huang

C. L.

Sengupta

Krishnan

Design of cooperative vehicle safety systems based on tight coupling of communication, computing and physical vehicle dynamics

Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS ′10)

April 2010

Stockholm, Sweden

ACM Press

159 167

10.1145/1795194.1795217

2-s2.0-77954566972

10.

Park

Kim

Application-level frequency control of periodic safety messages in the IEEE WAVE

IEEE Transactions on Vehicular Technology 2012 61 4 1854 1862

2-s2.0-84861108532

10.1109/TVT.2012.2190119

11.

Boukerche

Rezende

Pazzi

R. W.

Improving neighbor localization in vehicular Ad Hoc networks to avoid overhead from periodic messages

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′09)

December 2009

Honolulu, Hawaii, USA

Association for Computing Machinery

1 6

10.1109/glocom.2009.5425636

2-s2.0-77951648976

12.

Rezaei

Sengupta

Krishnan

Reducing the communication required by DSRC-based vehicle safety systems

Proceedings of the 10th International IEEE Conference on Intelligent Transportation Systems (ITSC ′07)

October 2007

Seattle, Wash, USA

IEEE Press

361 366

10.1109/itsc.2007.4357633

2-s2.0-49249102609

13.

Zrar Ghafoor

Abu Bakar

van Eenennaam

Khokhar

R. H.

Gonzalez

A. J.

A fuzzy logic approach to beaconing for vehicular ad hoc networks

Telecommunication Systems 2013 52 1 139 149

10.1007/s11235-011-9466-8

2-s2.0-84878789394

14.

Schmidt

R. K.

Leinmüller

Schoch

Kargl

Schäfer

Exploration of adaptive beaconing for efficient intervehicle safety communication

IEEE Network 2010 24 1 14 19

10.1109/MNET.2010.5395778

2-s2.0-77954977641

15.

Heravi

Osborn

D. R.

Birchenhall

C. R.

Linear versus neural network forecasts for European industrial production series

International Journal of Forecasting 2004 20 3 435 446

10.1016/s0169-2070(03)00062-1

2-s2.0-4344586989

16.

Zhang

G. P.

Kline

D. M.

Quarterly time-series forecasting with neural networks

IEEE Transactions on Neural Networks 2007 18 6 1800 1814

10.1109/TNN.2007.896859

2-s2.0-36348935677

17.

Yan

Toward automatic time-series forecasting using neural networks

IEEE Transactions on Neural Networks and Learning Systems 2012 23 7 1028 1039

10.1109/tnnls.2012.2198074

2-s2.0-84875899507

18.

Rallapalli

Qiu

Zhang

Chen

Y.-C.

Exploiting temporal stability and low-rank structure for localization in mobile networks

Proceedings of the 16th Annual Conference on Mobile Computing and Networking

September 2010

Chicago, Ill, USA

ACM

161 172

10.1145/1859995.1860015

2-s2.0-78649262078

19.

Rutan

S. C.

Adaptive Kalman filtering

Analytical Chemistry 1991 63 22 1103A 1109A

10.1021/ac00022a739

2-s2.0-0001727339

20.

X. R.

Jilkov

V. P.

Survey of maneuvering target tracking. Part V: multiple-model methods

IEEE Transactions on Aerospace and Electronic Systems 2005 41 4 1255 1321

10.1109/taes.2005.1561886

2-s2.0-27544508858

21.

Cloutier

J. R.

Lin

C. F.

Yang

Enhanced variable dimension filter for measuring target tracking

IEEE Transactions on Aerospace and Electronic Systems 1993 29 3 786 797

10.1109/7.220930

2-s2.0-0027624715

22.

Box

G. E.

Jenkins

G. M.

Reinsel

Time Series Analysis: Forecasting and Control 1994 3rd

Englewood Cliffs, NJ, USA

Prentice-Hall

MR1312604

23.

Yuan

Zheng

Xie

Sun

Driving with knowledge from the physical world

Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ′11)

August 2011

ACM

316 324

10.1145/2020408.2020462

2-s2.0-80052688627

24.

Institute of Transportation Systems German Aerospace Center, http://sumosim.org

25.

OpenStreetMap May 2014, http://www.openstreetmap.org

Position Prediction Based Frequency Control of Beacons in Vehicular Ad Hoc Networks

Abstract

1. Introduction

2. Related Work

3. The Proposed Scheme

3.1. Vehicular Dynamic Models

3.2. Position Prediction and Beaconing Schemes

3.3. Maneuvering Detection and Model Switching

4. Simulation

4.1. Vehicular Mobility Analysis

4.2. Performance Evaluation

4.2.1. Simulation Setting

4.2.2. Simulation Results

5. Conclusion

Footnotes

Conflict of Interests

References