Keywords

1 Introduction

VANETs hold great potential in enhancing vehicle safety and improving traffic efficiency [4, 7, 17]. In VANETs, each vehicle is equipped with a wireless communication system to exchange information among each other. One of the main information exchange methods in VANETs is beaconing. Based on IEEE 802.11p, beacon messages are broadcasted periodically on the control channel (CCH) by vehicles to inform their current states such as position, direction and speed. These beacon messages can be used by the neighboring vehicles to detect their traffic environment as well as preventing the potential traffic accidents [6, 9, 15].

The bandwidth of the CCH is 10 MHz. Channel load will sharply increase in scenarios with high traffic density. High channel load causes the channel congestion between vehicles, resulting in a high degree of performance degradation of VANETs. In recent years, some researchers have studied the adaptive beaconing schemes to reduce the channel congestion. Two main adaptation approaches have been proposed: the beacon generation rate adaptation [2, 3, 5, 11] and the beacon transmission power adaptation [8, 10, 13]. While most of these researchers just focus on studying one of these two approaches. Through analysis we believe separately adapting the transmission power or adapting the beacon generation rate can not satisfy the requirement of all the scenarios in VANETs. For example, in the highway scenario, due to the high speed of vehicles, to ensure the neighboring vehicles have enough distance to react the potential collision, we have to make sure the beaconing power can transmit the beacon message far enough. As another example, in the congested scenario where the vehicle density is high and the distance between two vehicle is short, we need a high beacon generation rate to ensure the real-time message exchange between vehicles. The other problem we find in existing works is that all the researchers adapt the future beaconing scheme based on the current parameters. As the traffic environment is changing, we believe this kind of beaconing adaption is delayed and inaccurate, especially when the vehicle beacon generation rate is low.

Different from existing works, we propose a new adaptive beaconing scheme based on the short-term traffic environment prediction in this paper. In our new scheme, to reduce the channel congestion, we combine the beacon transmission power adaptation and the beacon generation rate adaption in a certain way and order. In addition, according to the continuous change of the short-term traffic environment, we use the current and historical traffic environment parameters including the traffic density and the vehicle velocity to predict the future vehicle environment parameters. Based on these predicted parameters, we can adapt the beaconing scheme in advance. One important contribution is that we use the Auto Regressive Integrated Moving Average (ARIMA) model [12] based prediction method to guarantee the efficiency and accuracy of our prediction. To the best of our knowledge, this is the first paper to use the parameters prediction to improve the beaconing scheme.

The rest of this paper is organized as follows. In Sect. 2, we briefly present some existing works about the adaptive beaconing scheme. In Sect. 3, we introduce the system structure and give some assumptions used in this paper. In Sect. 3, we describe the online part of our adaptive beaconing scheme. The offline part is described in Sect. 4. In Sect. 5, we make evaluation of the performance of our Scheme. The conclusion is finalized in Sect. 6.

2 Related Works

As stated earlier in the previous section, some works have been proposed to improve the adaptive beaconing schemes. In [11], the authors propose an adaptive beaconing scheme which reduces the beacon generation rate based on two key metrics: message utility and channel quality. The scheme proposed [2] computes the beacon generation rate based on the bandwidth sharing information of the neighboring vehicles. A fuzzy logic approach is used in [5] to classify the moving states of vehicles, and vehicles adapt the beacon generation rate based on the moving states. The author in [3] consider beacon generation rate based on the fairness utilization of the bandwidth resource. [13] selects the beacon transmission power according to the utility of the beacon to be transmitted. In [8], the authors randomly select the beacon transmission power following a given probability distribution. In [10], authors discuss multi-tradeoffs in beacon transmission power adaption. All these works do not consider the combination of the beacon transmission power adaption and the beacon generation rate adaption together, and they adapt the future beaconing scheme based on the current parameters. To cover the shortage of these, we propose the adaptive beaconing scheme based on traffic environment parameters prediction in VANETs.

3 System Description

The basic idea of our proposed scheme is that the vehicle adapts the beaconing scheme based on the predicted traffic environment parameters. To build up a complete adaptive beaconing scheme, we also need to consider when to initiate the adaption, and how we adapt the beaconing scheme.

Fig. 1.
figure 1

The system diagram of our scheme

Full size image

In Fig. 1, we present the system diagram of our scheme. There are two main parts in our scheme, an offline part and an online part. In the offline part, based on the large numbers of the historical traffic environment data, we built several historical traffic patterns. The completed historical traffic patterns can be pre-stored in all the vehicles. It means one vehicle has no need to repeat the building process individually. The vehicle enters the online part when it is driving on the road. The online part is further divided into two phases, the detection phase and the adaption phase. In the detection phase, the vehicle continuously monitors the channel state to consider whether to initiate a beaconing scheme adaption or not. If not, it goes on monitoring the channel, otherwise it enters the beaconing scheme adaption phase. In the adaption phase, to identify the current traffic pattern, we use the pattern matching mechanism. The vehicle can quickly predict the traffic environment parameters with the last sets of the traffic environment data. Then based on the predicted parameters, it adapts the future beaconing scheme.

There are some assumptions in this paper. The first and also the most important assumption is that all the vehicles adapt their beacon transmission power and beacon generation rates using the same scheme. They have a fair share of the available bandwidth. Therefore, at the same time, the nearby vehicles have the similar beaconing states. The second assumption is that the vehicle can collect its own velocity and location in real time, and it can obtain the velocity and location of the neighboring vehicles from the received beacon messages. The third assumption is that the radio channel is ideal, the bit errors are not considered in this paper. To help understanding our adaptive beaconing scheme, we will introduce the online part first.

4 The Online Part in the Adaptive Beaconing Scheme

4.1 The Detection Phase

Before we adapt the beaconing scheme, we need to detect and confirm the necessity of the adaption. Since the channel congestion is the result of a considerable amount of the data exchange between vehicles which exceeds the network capacity. It is a simple but effective way to judge whether to initiate the adaption or not based on the number of the neighboring vehicles. In many researches, they calculated the number through counting the number of the received beacons. However, we think the beacon-based estimation is not accurate due to the collision of packets especially in congestion-related situations. The collision of packets is the ad-hoc nature of vehicular networks, and it is unavoidable. To tackle this problem, in our scheme, we choose the number of the received packets and the number of the collision packets to estimate the number of the vehicles. These two parameters are easy to collect and they do not need additional information exchange between vehicles. In this subsection, we will introduce our estimation method first. And then we give the judgement standard for initiating the channel scheme adaption.

Estimating the Number of Neighbors. To estimate the number of the neighboring vehicles, the estimation model is shown in Fig. 2. In this paper, we denote that all the vehicle B, C and D within the interference range are the neighboring nodes of vehicle A. Vehicle B and vehicle C are in the communication range of vehicle A. Vehicle D is in the interference range of vehicle A. All vehicles broadcast the beacon messages periodically. The beacon messages sent by vehicle D cannot be decoded by vehicle A and will be considered as collisions by vehicle A. The vehicle monitors the channel state periodically and continuously. Generally, each period takes one second. At the end of each period, we make a statistical analysis of the channel state. In period i, we can obtain the total number of the collisions packets which is denoted as \(n_{i\_{cp}}\), and we can obtain the total number of the received packets which is denoted as \(n_{i\_{rp}}\). Based on the received beacons, we define \(R_{i\_{avg}}\) as the average beaconing rate of neighbors. When one neighbor vehicle is in the interference range, the beacon packets from it are decodable. We define \(n_{i\_{ndp}}\) as the number of this kind of collision packet. When two neighbor vehicle are both in the communication range of the receiver. If they broadcast the beacon packets at the same time, the beacon packets will collide. We define \(n_{i\_{rcp}}\) as the number of this kind of collision packet. Then we have:

Fig. 2.
figure 2

Neighbor number estimation model

Full size image
$$\begin{aligned} n_{i\_{cp}}= n_{i\_{ncp}} + n_{i\_{rcp}}. \end{aligned}$$
(1)

In [1], the author has described that the percentage of \(n_{i\_{rcp}}\) in \(n_{i\_{cp}}\) can be considered as a constant parameter. It is denoted as \(\theta \) in this paper. We have:

$$\begin{aligned} n_{i\_{rcp}}=n_{i\_{cp}} \cdot \theta , \end{aligned}$$
(2)

and

$$\begin{aligned} n_{i\_{rcp}}=n_{i\_{ncp}} \cdot (1-\theta ). \end{aligned}$$
(3)

As the assumption in the estimation model, the situation that three or more packets colliding at a same time is negligible. For one vehicle in period i, we define the number of neighboring vehicles within the interference range as \(N_{i}\). It can be estimated as follows:

$$\begin{aligned} \begin{aligned} N_{i}&=\frac{(n_{i\_{rcp}}+n_{i\_{ncp}}+2 \cdot n_{i\_{rcp}})}{R_{i\_{avg}}}\\&=\frac{(n_{i\_{rcp}}+(1+\theta ) \cdot n_{i\_{cp}})}{R_{i\_{avg}}} \end{aligned} \end{aligned}$$
(4)

Making the Judgement. At the end of each detection phase, we can obtain the number of the neighboring vehicles. The number of the last period is denoted as \(N_{i-1}\). With this two parameters we can make the judgement on whether to initiate a beaconing scheme adaption or not. The following is the judgement process. We have the variable T expressed the change of the the number of the neighboring vehicles:

$$\begin{aligned} C=|N_{i}-N_{i-1}|. \end{aligned}$$
(5)

We define \(C_{t}\) as the threshold of the change. It can be calculated as follows:

$$\begin{aligned} C_{t}= \varepsilon \cdot N_{i-1}, \end{aligned}$$
(6)

where \(\varepsilon \) is a constant which we defined in the system. If C exceeds threshold \(C_{t}\), the vehicle judges that it should initiate the beaconing scheme adaption. Then the vehicle finishes the judgement process.

Obtaining the Parameters Used in the Adaption Phase. At every end of the monitoring periods, the vehicle should recalculate C and \(C_{t}\). To realize the pattern matching prediction in the adaption phase, besides the above parameters, the vehicle acquire another two parameters. The first is the velocity of the vehicle itself denoted as \(v_i\) which can be directly collected from the vehicle. The second is the traffic density denoted as \(d_i\). Generally in vehicle environment, the traffic density is described as the number of vehicles in every kilometre. Defining \(R_{{inter}\,{f}}\) as the interference range of the vehicle, \(d_i\) can be calculated based on \(N_{i}\) and \(R_{{inter}\,{f}}\). The formula is expressed as follows:

$$\begin{aligned} d_i= \frac{N_{i}}{2R_{{inter}\,{f}}}. \end{aligned}$$
(7)

And we can calculate the interference range as follows:

$$\begin{aligned} R_{{inter}\,{f}}=\frac{\lambda }{4\pi \theta }\cdot \sqrt{\frac{G\cdot P_i^t}{P_{rmin}}}, \end{aligned}$$
(8)

where G is the antenna gain, \(P_i^t\) is the transmission power, \(P_{rmin}\) is the minimal received power which can successfully decode the message, \(\lambda \) is the wavelength.

4.2 The Adaption Phase

Different from other researches, we use the predicted parameters to do the beaconing scheme adaption. In the end of the detection phase, we have obtained the parameters \(v_i\) and \(d_i\) which can reflect the traffic environment.

The future parameters can be quickly predicted with the current and historical parameters by using the pattern matching mechanism. In this paper, based on the ARIMA model, we build the traffic patterns. The pattern building process is presented in the next section. Here, we introduce the pattern matching and the prediction process.

Pattern Matching. The target of the pattern matching process is to select a pattern from the historical traffic patterns which is most similar to the current traffic conditions. According to the description in [16], we extract the second-order autoregressive parameters of the current traffic data firstly. And then we apply the Euclid Distance to estimate the similarity between the historical and the identified current traffic patterns. The formula is expressed as follows:

$$\begin{aligned} D_E^2(\phi _T,\phi _R)=(\phi _T-\phi _R)^T\,(\phi _T-\phi _R), \end{aligned}$$
(9)

where \(\phi _R\) and \(\phi _T\) denote the autoregressive parameters of the historical pattern and the identified pattern, respectively.

Future Parameters Prediction. After matching the traffic pattern, combining with the current parameters, the future parameters \(v_{i+1}\) and \(d_{i+1}\) can be quickly obtained by one-step or multistep prediction shown in Eq. 10.

$$\begin{aligned} \hat{x}_t(l)= {\left\{ \begin{array}{ll} \phi _0+\sum _{i=1}^{p}(\phi _i\,\hat{x}_{i-1}(l))-\sum _{j=1}^{q}(\theta _i\,\varepsilon _{i+l-j}) &{}\text {l} \le \text {q},\\ \phi _0+\sum _{i=1}^{p}(\phi _i\,\hat{x}_{i-1}(l)) &{}\text {l} \ge \text {q}. \end{array}\right. } \end{aligned}$$
(10)

where \(\phi _i,i=1,2,\dots ,p\) is the autoregressive parameter, \(\theta _j,j=1,2,\dots ,q\) are the moving average parameters, p is the order of autoregressive parameters, q is the order of moving average parameters, \(\varepsilon _t\) are variances of the residual series and l is the step-size of the backward prediction. By using the predicted traffic parameters, we can avoid some channel congestion caused by the delayed beaconing scheme adaption.

Beaconing Scheme Adaption. We present our beaconing scheme adaption method in this subsection. In the introduction of this paper, we have introduced the disadvantages of separately adapting the transmission power and separately adapting the beacon generation rate. Fortunately, the situation that high density of vehicles driving with a high speed dose not exist. So it is possible to design a beaconing adaption method to satisfy the requirement of all the scenarios in VANETs.

In our scheme, we combine the transmission power adaption and the beacon generation rate adaption together. This is also one of the main contributions of this paper. The adaption method can be summarized as: we adapt the beacon generation rate until it reaches the minimum beacon transmission power, and then we adapt the beacon generation rate. The minimum beacon transmission power denoted as \(P_{i+1}^{tmin}\) is calculated based on the current vehicle velocity. We have

$$\begin{aligned} P_{i+1}^{tmin}=\frac{64\pi ^2 {v_{i+1}}^2 P_{rmin}}{G \lambda ^2}. \end{aligned}$$
(11)

The core idea of our adaption method is to make our best effort to maintain the beacon generation rate. We believe that most of the safety applications enquire a high beaconing rate. Frequently reducing the beaconing rate will affect the vehicle safey. While reducing the transmission power only means reducing the number of vehicles in the communication range, the most important vehicles relating to the safey are these nearest ones, the slight adaption on the transmission power will not affect these vehicles. So adapting the beaconing transmission power before the beacon generation rate is appropriate. At the same time, the calculated minimum beacon transmission power can ensure that the nearest vehicles are in the awareness region. We believe the proposed beaconing scheme adaption method can satisfy various requirements of VANETs.

5 The Offline Part in the Adaptive Beaconing Scheme

In the offline part, using the historical traffic environment data, the vehicle builts the historical traffic patterns based on the ARIMA model. The ARIMA model is a common used model for time series analysis which is also known as the famous Box-Jenkins model. In our scheme, the pattern building have 4 steps:

Step1: Data smoothing. In our scheme, the historical traffic environment data mainly include the number of neighboring vehicles and vehicle velocity in different areas and at different times. It is unavoidable that there are some error or inaccurate data. For the time series, these data are noises and will affect the quality of the pattern building. Hence, it is necessary to smooth the date. In this paper, due to the features of simplicity and high efficiency, we use the exponential smoothing method to smooth the data.

Step2: Stationarity test. Since the modeling process require the stationarity of the time series, we need to do the stationarity test. If one series shows the evidence of non-stationarity, we can use the difference method to reduce the non-stationarity. Sometimes, the second-difference is also needed.

Step3: Traffic state classification. In the research of the paper [14], the author has proved that the traffic state classification can improve the modeling accuracy. In our paper, based on the velocity-density relation, we classify the traffic states into three states, the free flowing state, the high traffic state and the congested state. Before building the traffic patterns, all the historical traffic environment data are classified based on the three states.

Step4: Pattern building. After finish the above data preprocessing steps, we can formally start building the traffic patterns. In this step, we will do the model recognition, the parameter estimation, the model diagnostics, and the patterns storage. According to [16], the ARIMA (p, d, q) model of the time series \(\{X_1,X_2,\ldots ,X_t\}\) can be defined as:

$$\begin{aligned} \begin{aligned} X_t=&\phi _1\,X_{t-1}+\phi _2\,X_{t-2}+\dots +\phi _p\,X_{t-p}+a_t-\theta _1\,a_{t-1}-\theta _2\,a_{t-2}-\dots -\theta _q\,a_{t-q} \end{aligned} \end{aligned}$$
(12)

\(X_t\) is obtained by differencing the original time series d times, \(a_t\) is the white noise component at t, \(\phi _i,i=1,2\dots p\) are the autoregressive parameters, \(\theta _j,j=1,2\dots q\) are the moving average parameters, p is the order of autoregressive parameters and q is the order of moving average parameters.

According to the different characters of these historical traffic environment data, we can choose a suitable ARIMA model for these data. The model recognition process is equivalent to the process that determining the value of p, d, and q. The parameter estimation process is equivalent to process that determining the value of the parameters in Eq. 12. In this paper, we use the maximum likelihood estimation method to obtain all the value of these parameters. The model diagnostics phase, we test the estimated parameters in the model, and diagnose whether the residual series error is white noise or not. In [12], they have given the detailed explanations and computing methods of the ARIMA model. So we do not repeat them here. Based on the diagnosis, we can know the appropriateness of the model. After all the processes, we can store the builded historical traffic patterns and they will be used in the online part.

6 Performance Evaluation

In this section we evaluate the performance of our adaptive beaconing scheme. The simulation is based on the IEEE 802.11p Medium Access Control model (MAC) with 10 MHz wide channels. All simulation results are averaged from 100 different simulation tries.

Fig. 3.
figure 3

The traditional parameters used to adapt the beaconing scheme

Full size image
Fig. 4.
figure 4

The predicted parameters used to adapt the beaconing scheme

Full size image
Fig. 5.
figure 5

The collection rate of different beaconing scheme (Color figure online)

Full size image

Figures 3 and 4 show the relationship between the actual density time-series and the future density parameters used in the beaconing scheme adaption. The future density parameters in Fig. 4 are the predicted parameters after the ARIMA model based prediction, and the future density parameters in Fig. 3 are calculated just according to the current traffic density. Figure 5 shows the collision rate with these two kinds parameters to do the beaconing scheme adaption. We can find that, the beaconing scheme with predicted parameters has better performance than the other beaconing scheme. Especially when the traffic environment has a large change, the beaconing scheme without parameters prediction cause a obvious increase in beaconing collision rate. The simulation proves the advantage of our adaptive beaconing scheme based on traffic environment parameters prediction. With the pattern matching technology, our beaconing scheme can adapt in advance to avoid the channel congestion.

Fig. 6.
figure 6

Packets collision rate

Full size image
Fig. 7.
figure 7

Average received beacons

Full size image

We analyze the relationship between the packets collision rate and the vehicle density of different adaption methods in Fig. 6. We can find that, when the vehicle density is more than 50 vehicles per kilometer, there is a obvious increase in the collision rate of the beaconing scheme which separately adapting the transmission power or adapting the beacon generation rate. Since we combine the beacon transmission power adaptation and the beacon generation rate adaption together in our adaption methods, we have a distinct advantage in the collision rate especially when the vehicle density is high. We also analyze the relationship between the number of the average received beacons and the vehicle density of different adaption methods in Fig. 7. Similarly, our combined scheme has a distinct advantage in number of the average received beacons when the vehicle density is high. From these simulations, we can find that the ARIMA model based prediction method and the combined beaconing adaption method are effective to reduce the channel congestion and enhance the utilization of the limited channel resource.

7 Conclusion

In this paper, we study the problem of how to adapt the beaconing scheme. We propose an adaptive beaconing scheme based on traffic environment parameters prediction. The ARIMA model based prediction method is used to do the prediction. And we combine the beacon transmission power adaptation and the beacon generation rate adaption in our adaption method. Simulation results confirm the benefits of our scheme. In our future research, we plan to study the relationship between the beaconing scheme adaption and the contentiom window adaptation.