The RSU Access Problem Based on Evolutionary Game Theory for VANET

Abstract

We identify some challenges in RSU access problem. There are two main problems in V2R communication. (1) It is difficult to maintain the end-to-end connection between vehicles and RSU due to the high mobility of vehicles. (2) The limited RSU bandwidth resources lead to the vehicles' disorderly competition behavior, which will give rise to multiple RSUs having overlap area environment where RSU access becomes crucial for increasing vehicles' throughput. Focusing on the problems mentioned above, the RSU access question in the paper is formulated as a dynamic evolutionary game for studying the competition of vehicles in the single community and among multiple communities to share the limited bandwidth in the available RSUs, and the evolutionary equilibrium evolutionary stable strategy (ESS) is considered to be the solution to this game. Simulation results based on a realistic vehicular traffic model demonstrate the evolution process of the game and how the ESS can affect the network performance.

1. Introduction

Vehicle ad hoc network (VANET) is a special case of mobile ad hoc network. The motions of vehicles are restricted to a geographical pattern. Further, the communication patterns of VANET include vehicle to vehicle (V2V) and vehicle to road side unit (V2R). RSU is referred to as road side unit, which is a wireless transceivers and receivers and has the characters of data storage, computing power, and router. In recent years, V2R communication has received considerable attentions [1–4]. In this paper, we mainly research the RSU access problem.

When vehicles drive through RSU, it will ask the RSU for service requirements. However in VANET, (1) it is difficult to maintain the end-to-end connection between vehicles and RSU due to the high mobility of vehicles; $(2)$ the limited RSU bandwidth resources lead to the vehicles' disorderly competition behavior, which may reduce the network throughput; $(3)$ due to the uneven distribution of vehicles, RSU's load may become diversification, which will lead to the load imbalance of RSU. In order to solve the problems above and achieve good network throughput, one question needs to be addressed: in the highly dynamic network, when and which RSU should be accessed. Focusing on the problem, the paper puts forward evolutionary game theory.

Game theory provides a mathematical modeling for the study of competition strategies in a game where players have conflicting benefits or goals and consider the rivals' strategy to make their own strategy [5, 6]. Evolutionary game theory describes game models in which players choose their strategies through a trial-and-error process in which they learn over time that some strategies work better than others [7, 8]. In this paper, we analyze the RSU access problem under the framework of game theory as the vehicles are noncooperative and competitive and need to consider the strategy of other vehicles to make their own strategy. In addition, vehicles are controlled by bounded rational entities, such as human or organization [9], and the traditional game theory assumed that the players are perfectly rational, so we adopt the evolutionary game theory to analyze the access problem.

The research scene includes multiple vehicles versus two RSUs and multiple vehicles versus multiple RSUs. We divide the vehicles into different populations according to the strategies. The two RSU's scene belongs to a single-community evolutionary game as all vehicles' strategy set is the same, while the multiple RSU's scene belongs to multiple communities evolutionary game as vehicles in different populations have different strategies. The payoff function of our model is the difference of the throughput and the cost. In our paper, the cost contains two aspects: bandwidth occupation cost and handoff cost. The Nash equilibrium is evolutionarily stable strategy (ESS), that is, the probability of vehicles access to RSU. In order to ensure the accuracy and reliability of research results, the paper adopted the traffic flow simulator VanetMobiSim to generate the real vehicle moving track. The simulation results demonstrate the evolution process of the game and how the ESS can affect the network performance.

The main contributions of this paper can be summarized as follows.

• (1)

An evolutionary game-theoretic approach is presented to solve the RSU access problem in VANET. In particular, the replicator dynamics is quoted to investigate the dynamics of vehicle behavior and solution.

(2)

Under two RSU's scene and multiple RSU's scene, the paper sets up single-community and multiple-community evolutionary game models to analyze the dynamic evolutionary process and the effect on network performance.

The rest of this paper is organized as the following. Section 2 reviewed problem description. In Section 3, we introduced the related work. Section 4 formalized the system model, which includes single-community and multiple-community evolutionary game models. The numerical experiments were performed in Section 5. Finally, we draw our conclusions in Section 6.

In the paper, we also use the terms “population” and “species” to refer to the VANET community.

2. Problem Definition

In VANET, vehicles have no Internet access and arrive randomly in VANET; vehicles have to access to RSU if they want to obtain the Internet services.

RSU broadcasts the beacon messages to vehicles periodically when the vehicle lies in the coverage area of an RSU, from which the vehicle can get the current state information of the RSU and the network. For simplicity, we assume that RSU's transmission range is equal, and we divide the road into different areas according to the RSUs' coverage area, which is defined as $S=\{S_1,S_2,\dots ,S_K\}$ . As shown in Figure 1, the road is divided into four areas $S=\{S_1,S_2,S_3,S_4\}$ . In different areas, vehicles can access different RSUs. Vehicle requests services from RSU when driving through RSU, and it can get the service profit from RSUs, while it also incurs a cost in requesting for RSU, where the cost can be the price that vehicles spend on RSUs' bandwidth, buffer size, and other resource. Besides, when vehicles drive from an RSU to another, the vehicles have to pay for the handoff cost. The payoff function of vehicles is

$$\begin{array}{cc}& F=Q_i^j-P_i^j-h_i^j,\end{array}$$

(1)

where $Q_i^j$ is the achievable throughput of vehicle i got from RSU j

$$\begin{array}{cc}& Q_i^j=\delta *\left(T_i^j-t^j\right)*c_i^j*N^j\end{array}$$

(2)

$T_i^j$ is the time when vehicle i  is driving in the coverage area of RSU j

$$\begin{array}{cc}& T_i^j=\frac{R^j}{v_i}.\end{array}$$

(3)

$t^j$ represents the communicate delay when vehicles communication with RSU j

$$\begin{array}{cc}& t^j=\frac{N^j}{f_s}.\end{array}$$

(4)

$P_i^j\mathrm{\hspace{0.17em}\hspace{0.17em}}$ stands for the resource cost

$$\begin{array}{cc}& P_i^j=\beta *N^j*{\alpha }_i*\frac{l_i}{c_i^j},\end{array}$$

(5)

where $l_i/c_i^j$ is the time that vehicle i should communicate with RSU j if it wants to finish its request. ${\alpha }_i$ is the importance index of vehicle i's request file. If ${\alpha }_i>2$ , the request file is urgent, such as emergency information, $1<{\alpha }_i<2$ means that the request is less important, such as road information, and the request is video and audio streams if ${\alpha }_i<1$ .

Figure 1

The RSU's access scene.

$c_i^j$ is the transmission rate of vehicle i

$$\begin{array}{cc}& c_i^j=w^j*{\log }_2\left(1+\frac{S/N}{N^j*\stackrel{-}{{{(d}_i^j)}^r}}\right).\end{array}$$

(6)

$h_i^j$ is the handoff cost

$$\begin{array}{cc}& h_i^j=\phi *t_{\text{left}}*T_{\text{left}},\end{array}$$

(7)

where $t_{\text{left}}$ is the request files that have finished and $T_{\text{left}}$ is the distance that vehicles have driven in RSU's coverage. Detailed parameters are listed in Table 1.

Table 1

The parameters.

Symbol	Semantics
$N^j$	The total number of vehicles in the coverage area of RSU j
${\mathrm{R}}^{\mathrm{j}}$	The transmission radius of RSU j
$v_i$	The speed of vehicle i
$l_i$	The request file length of vehicle i
$\mathrm{S}/\mathrm{N}$	The signal-to-noise ratio
$d_i^j$	The distance between vehicle i and RSU j
$w^j$	The link bandwidth of RSU j
$f_s^j$	The communication frequency of RSU j
$\mathrm{\gamma }$	The path loss exponent
$\mathrm{\Phi }$ , $\mathrm{\beta }$ , δ	The weighting coefficient

3. Related Work

A number of previous results have been reported on the RSU access problems. In [10], a distributed association algorithm according to the number of mobile users (MUs) associated with APs was introduced. Besides, reference [11] built a game model according to the potential link rate and the number of WSs access to RSU, which can ensure that each WS gets achievable throughput. Reference [12] presented a new load balancing technique by controlling the size of WLANs (i.e., APs' coverage range) to ensure the load balancing among APs. As we know, vehicles in VANET are highly mobile and the network typology changes dynamically, which demonstrated that the approaches ignore VANET's mobile properties. Besides, these approaches only consider the profit of RSU but vehicles and the papers above all assumed that the players are perfectly rational, which did not fit the realities that human and organizations and other players are bounded rationality. In a word, these methods were not applicable for VANET.

In recent years, evolutionary game theory has been used in wireless network in many fields. Reference [13] that showed the evolutionary game is used to obtain the forward probability of nodes in two-hop DTN and analyze the stability of ESS. In [14], the authors presented two algorithms, namely, population evolution and reinforcement-learning algorithms, for network selection and formulated the game to model the competition among populations of users in the different service areas in heterogeneous wireless networks. Reference [15] presented a model based on evolutionary game theory (EGT) in which it demonstrated that the model was able to encourage selfish nodes to cooperate and forward packets from others with only one period of punishment if nodes are sufficiently patient. As we know, the traditional game theory has been used in VANET for some applications [16–18]; however, the evolutionary game theory's applications in VANET are growing due to the following reasons. (1) The evolutionary equilibrium of evolutionary game is a refined solution, which ensures stability (i.e., population of players will not change their chosen strategies over time). (2) An evolutionary game changes their strategies slowly to achieve the solution eventually, and the traditional game makes decisions immediately. (3) The replicator dynamics is useful for investigating the trajectory of the players' strategies [14]. In our paper, we solve the RSU access problem in VANET by using evolutionary game.

4. Evolutionary Game Model

The evolutionary game for our paper can be described as follows.

• (i)

Players: the vehicle in the coverage area of RSU is a player of the game.

(ii)

Population: the vehicles that have the same strategy set are a population. In different populations, the number of vehicles is defined separately as $N=\{N^1,N^2,\dots ,N^j,\dots \}$ .

(iii)

Strategy: the strategy set is $X^j=\{x_0^j,x_1^j,\dots ,x_i^j,\dots ,x_N^j\},\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2}\dots ,N$ , where $x_i^j$ means the access probability that player i chooses RSU j.

(iv)

Payoff: the payoff function is ${F=Q}_i^j-P_i^j-h_i^j$ , which is the difference of the throughput of that strategy and the cost. In multiple communities, the payoff of the vehicle depends on not only the strategy played by the number of vehicles from the same population but also other populations that participate to the game.

In this section, we present the evolutionary game model in two RSU's scene and multiple RSU's scene, respectively.

4.1. Two RSUs' Scene

As shown in Figure 2, in two RSU's scene, there is a set of vehicles who want to request services from RSU1 and RSU2. Vehicles can only access RSU2 when they enter S1 and may change its selection when they enter S2. We assume that the vehicle needs to pay for the handover cost if it does not finish its service request while it performs the handoff operation. On the contrary, If the vehicles' requested services have been finished, the handoff cost is zero and vehicles get their strategy based on their location, the file size, service type, and so on. The vehicles in RSU1 and RSU2's coverage area are a single-community evolutionary game, in which all vehicles' strategy set is the same. The payoff matrix is as described in Table 2.

Table 2

Two RSUs' payoff matrix.

	RSU1	RSU2	None
RSU1	${\theta }^1-\phi (P^1+h^1)$	${\theta }^1-(P^1+h^1)$	${\theta }^1-(P^1+h^1)$
RSU2	${\theta }^2-(P^2+h^2)$	${\theta }^2-\phi (P^2+h^2)$	${\theta }^2-(P^2+h^2)$
None	0	0	0

Figure 2

The two RSUs' scene.

In the game, we let $X:=\{(x,x-)\mid x+x-=1\}$ be the set of probabilities distributions of population i. x and y represent the probabilities of vehicles in population i accessing RSU1 and RSU2, respectively, $1-x-y$ means vehicles do not access any RSUs' probability, and φ is the congestion index. The payoff function is as follows.

•  

The profit of vehicles accessing RSU1 is

$$\begin{array}{l}F\left(x,1\right)=x*\left({\theta }^1-\phi *\left(P^1+h^1\right)\right)+y\left({\theta }^1-\left(P^1+h^1\right)\right)\\ \hspace{1em}+\left(1-x-y\right)*\left({\theta }^1-\left(P^1+h^1\right)\right).\end{array}$$

(8)

 

The profit of vehicles accessing RSU2 is

$$\begin{array}{l}F\left(y,2\right)=x*\left({\theta }^2-\left(P^2+h^2\right)\right)+y*\left({\theta }^2-\phi *\left(P^2+h^2\right)\right)\\ \hspace{1em}+\left(1-x-y\right)*\left({\theta }^2-\left(P^2+h^2\right)\right).\end{array}$$

(9)

 

The payoff of vehicles in population 1 and population 2 which do not choose any RSU is 0.

The average payoff of populations is

$$\begin{array}{cc}& \stackrel{-}{F}=x*F\left(x,1\right)+y*F\left(y,2\right)+\left(1-x-y\right)*0.\end{array}$$

(10)

In a dynamic evolutionary game, an individual from a population, who is able to replicate itself through the process of mutation and selection, is called replicator. In this case, a replicator with a higher payoff can reproduce itself faster. The game is a repeated game, and in each period, a player observes the payoff of other players in the same community. Then, in the next period, the player adopts a strategy that gives a higher payoff. The speed of the vehicle in observing and adapting the RSU access is controlled by the parameter $\mathrm{\hspace{0.17em}\hspace{0.17em}}\mu$ .

In the case of single community, the replicator dynamics is:

$$\begin{array}{cc}& \frac{dx}{dt}=\mu \left[F\left(x,1\right)-\stackrel{-}{F}\right]*x,\\ \frac{dy}{dt}=\mu \left[F\left(y,2\right)-\stackrel{-}{F}\right]*y.\end{array}$$

(11)

4.2. Multiple RSUs' Scene

Figure 3 depicts the multiple RSUs' scene, in which vehicles in different populations have different strategies. So it is a multiple-community evolutionary game. As shown in Figure 3, area 1 is the overlap area of RSU1 and RSU2, and area 2 is the overlap area of RSU1, RSU2, and RSU3. The set of strategies for the players in area 1 is $\{\text{RSU}1,\text{RSU}2\}$ , while that for the players in area 2 is $\{\text{RSU}1\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{RSU}2,\text{RSU}3\}$ . Area 1 and area 2 depict a two community evolutionary game. The vehicles in multiple-community evolutionary game will compete with each other within population and also carry on the competition among the populations. During the evolutionary process, the vehicles adjust their strategies according to their payoff until all the vehicle's strategies maintain stable, and the strategy is ESS at this time.

Figure 3

Multiple RSUs' scene.

The payoff function of vehicles in population i accessing RSU j is

$$\begin{array}{cc}& F_i^j={\theta }_i^j-P_i^j-h_i^j.\end{array}$$

(12)

The payoff of vehicles in population i which do not access any RSU is 0.

The average payoff of all populations is

$$\begin{array}{cc}& \stackrel{-}{F^i}=\sum _{j=1}^M{x}_j^i*F_j^i.\end{array}$$

(13)

The replicator dynamics of population  i  is

$$\begin{array}{cc}& \frac{{dx}_j^i}{dt}=\mu \left[F_j^j-\stackrel{-}{F^i}\right]*x_j^i.\end{array}$$

(14)

5. Simulations and Evaluations

VANET is a special network, it has a highly dynamic typology, vehicles are highly mobile, and the motions of vehicles are restricted to a geographical pattern. In order to make the simulation results more realistic, we use VanetMobiSim and Google Earth map tools to simulate traffic track. As shown in Figure 4, the paper chooses Zhongshan district, Dalian, as the simulation area, and the area size is 2.0 km by 2.0 km. VanetMobiSim is a simulation tool which can generate vehicle trajectory. In our simulation, we need to use the VanetMobiSim to get the movement trajectory of vehicles.

Figure 4

(a) The effect on ESS of packet size. (b) The effect on ESS of vehicle speed.

We study the access problem through the following two aspects: the evolutionary process of the ESS and the effect of resource cost parameters on network performance. We set the simulation parameters as described in Table 3.

Table 3

Simulation parameter values.

Parameter	Value
RSU's transmission radius R	1000 m
$S/N$	30 dB
Bandwidth W	20 MHz
Path loss exponent γ	2
The congestion index φ	1.2
Weight coefficient β	0.15
Weight coefficient δ	0.1
Weight coefficient $\mathrm{\Phi }$	0.1

In Figures 4 and 5, the horizontal axis stands for the number of evolution, while the vertical axis stands for the ESS.

Figure 5

(a) The number of vehicles in community is 100. (b) The number of vehicles in community is 70.

Figure 4 demonstrates the influence on ESS along with the vehicle speed, package size changing. In the simulation we set the number of vehicles as 150, the vehicles speed as 15 m/s for Figure 4(a), and the package size as 20 for Figure 4(b). With size increment, the probability that vehicles finish their service within RSU's coverage area decreases, leading to the decrease in the probability that vehicles access RSU. Similarly, the probability of vehicles accessing to RSU increases if the speed decreases or the number of vehicles having accessed RSU decreases.

Figure 5 shows the influence of $N^j,\hspace{0.17em}\hspace{0.17em}j=\mathrm{1,2}$ , on ESS in two-community evolutionary game. Figure 5(a) shows the ESS when $N^j=100$ while Figure 5(a) shows the ESS when $N^j=70$ . As the simulation result demonstrates that the traffic load and the cost of RSU1, RSU2, and RSU3 in population 2 decrease when $N^2$ reduces, which makes the vehicles in population 2 would like to access RSU1, RSU2, and RSU3, vehicles in population 1 are also more inclined to access RSU1 and RSU2 as they thought the number of vehicles accessing RSU1 and RSU2 decreases. As shown in Figure 5, the ESS $x=(0.14,0.06,0.23,0.14,0.06)$ in Figure 5(a) increases to Figure 5(b)   $x=(0.68,0.3,0.22,0.33,0.42)$ if $N^2$ decreases.

Figure 6 shows the service types' effect on average throughput. The RSU's price increases along with the increase of the request file importance index (a), which makes the number of vehicles accessing RSU decreases. Meanwhile, the average bandwidth which the RSU assigned to vehicles increases as the population did not change, which makes the average throughput increase.

Figure 6

The request service type on throughput.

Figure 7 represents the load balancing of RSUs. RSU's pricing and the average bandwidth maintain stable when the number of vehicles in communities is the same, which makes the traffic load balancing; RSU's traffic load retained around 0.99. The number changing leads to the changing of RSU's pricing and the probability of accessing RSU, so the RSU's balance index decreased to 0.92.

Figure 7

The effect on balance index of the number of vehicles in community.

6. Conclusions

In this paper, we have set up an evolutionary game model to formulate the competition among vehicles in the same community and different communities with bounded rationality in VANET for RSU access problem. We have investigated the dynamic evolutionary process of ESS when vehicles drive through RSU. A vehicle accesses RSU based on its payoff, which is a function of throughput and cost. The dynamics of RSU access has been mathematically modeled by the replicator dynamics that describes the adaptation in proportions of vehicles accessing different RSUs. The ESS has been considered to be the stable solution for which all vehicles receive identical payoff from difference RSUs. Detailed analyses have shown the evolutionary process. Besides, in the simulation result we can know that the package size, vehicle speed, and the number of vehicles in community have effects on the ESS, which then affect the network throughput and load balancing.

Due to the limited communication time between vehicles and RSU, in the future work, we can use cooperative download method to improve the network throughput.