Nothing Special   »   [go: up one dir, main page]

Skip to main content

Timed bargaining-based opportunistic routing model for dynamic vehicular ad hoc network

Abstract

Vehicular ad hoc network (VANET) is a mobile ad hoc network with a dynamic property; the vehicles possess high mobility and undergo fast topology changes. This special type of mobile ad hoc network is a popular topic of research. Owing to the specific features of VANETs, unique routing protocols are required for short-range, high-speed communication among nearby vehicles. In this study, we propose a new opportunistic routing scheme based on the timed bargaining game. In order to dynamically adapt to the current VANET situation, the proposed scheme effectively formulates the opportunistic routing mechanism as an iterative bargaining model with a timed learning approach. Based on a simulation study, it is confirmed that the proposed scheme can achieve better performance than other existing schemes in diverse VANET environments.

1 Introduction

In recent years, the explosive growth of traffic and ubiquitous information service have enabled close integration of communication networks with vehicular networks; thus the vehicular ad hoc network (VANET) emerged and became a popular area of research. In particular, VANET is a self-organized and open-structured inter-vehicular communication network that has dynamic, distributed, and multi-hop characteristics; further, it also possesses unique attributes such as the high speed of vehicles, frequent topology changes, predictable trajectory, and the absence of hardware constraints. These attributes directly affect the transmission performance in VANETs [1–3].

For efficient VANET operations, routing is extremely important; the network performance is strongly related to the routing algorithms. In the last few decades, significant research effort has been devoted to VANETs and many new and tailored routing protocols have been proposed. In order to maximize the network performance, most efforts have focused on determining a method that will reliably transfer messages to vehicles within communication range and in the complete network to avoid congestion, collision, and traffic management. However, owing to the dynamic nature and explicit requirements of VANETs, the adaptation and standardization of such routing protocols is extremely difficult [1, 2].

Nowadays, the game theoretic approach is widely recognized as a practical perspective for the implementation of real-world network operations. Game theory is a field of applied mathematics that provides an effective tool to model the interactions among independent decision makers. It can describe the possibility of reacting to the actions of the other decision makers and analyze the situations of conflict and cooperation. In recent times, game theory has emerged as an effective method for designing routing algorithms and has introduced well-fitted models to describe the interaction among network vehicles [4, 5].

In 1950, John Nash introduced the fundamental notion of the Nash bargaining solution (NBS) to allocate a resource fairly and optimally [4]. The NBS is a field of cooperative game theory and an effective tool to achieve a mutually desirable solution with a good balance between efficiency and fairness [4]. Owing to its numerous desirable properties, the basic concept of NBS has become an interesting research topic in a wider range of real-life situations, such as economics, political science, sociology, psychology, and biology. In recent times, telecommunications and VANET operations have been added to this list. However, traditional NBS models assume that all the information needed by any game player is known completely. In a real-world VANET situation, information about the actions of other vehicles may be uncertain or unknown. Hence, the traditional NBS model cannot be directly applied to real-world VANET routing operations.

Motivated by the facts presented in the above discussion, we design a new routing scheme for VANETs. In order to adapt to the dynamic VANET situations, the classical NBS model is modified based on the sequential bargaining approach. By taking into account the timed game model, the proposed scheme is designed as an iterative routing process in which each iteration involves three key steps: (i) observing the current network environment, (ii) estimating the prospective payoff to select the most adaptable strategy, and (iii) updating the information to adapt to the network dynamics. In the case of incomplete information, our timed game approach can relax the traditional NBS assumption that all information is completely known; this is the main advantage of our proposed scheme. The important features of the proposed scheme are (i) the adjustable dynamics considering the current VANET situation, (ii) the interactive process based on the iterative feedback mechanism, and (iii) the practical distributed method to effectively reach a desirable solution. In the case of significantly different and diversified network situations, the proposed scheme can approximate an optimized VANET performance during real-world routing operations.

1.1 Related work

The area of numerical methods or algorithms for vehicle-to-vehicle-based wireless communications has been extensively studied and has received considerable attention in recent years [6–9].

Topology-based VANET routing schemes are categorized into proactive and reactive routing protocols [6, 10, 11]. In proactive routing protocols, routing routes are predefined. Therefore, during routing, no route discovery process actually occurs. However, the maintenance of unused routes leads to a higher network control overhead that degrades system performance. Proactive routing protocols incur a control overhead, and hence, reactive routing protocols, in which the routing route discovery takes place on demand, are developed. This approach maintains only the currently used route, thus incurring a lower overhead [6, 10, 11]. The Power and Contention window Joint Adaptation (PCJA) scheme is a new algorithm for dynamic adaptation of transmission power and contention window size to enhance the performance of VANETs [12]. This scheme uses a joint approach to adapt transmission power at the physical layer and QoS parameters at the MAC layer. The Joint Power and Rate Control (JPRC) scheme focuses on analyzing and understanding the fundamental implications of adapting power and rate on the reception performance [13]. The JPRC scheme uses the average packet inter-reception as a metric for reception performance and evaluates this metric with respect to sender-receiver distance [13].

Position-based routing schemes use the geographical location information to forward messages [6, 10, 11]. For the selection of the next hop, these schemes beacon periodically while broadcasting control messages. If topology-based routing is used, routes and routing table are not maintained. However, as the mobility increases, the topology changes frequently, thus potentially degrading the performance with a higher network control overhead [6, 10, 11]. The study in [14] analyzes the effects of adapting the beacon rate with respect to reduced accuracy and changing the offered load. Numerous schemes that consider the offered load and corresponding accuracy have been developed in order to adapt the beacon rate according to the traffic situation [14]. The Feedback Based Power Control (FBPC) scheme [7] considers the problem of adjusting transmission power for vehicle-to-vehicle broadcast safety communication in vehicular ad hoc networks. Given a target communication range designated by a vehicle safety application, the power control algorithm in the FBPC scheme is developed to select a transmission power that is no greater than necessary for the targeted range [7].

Cluster-based routing schemes [6, 10, 11] are designed to provide scalability. Therefore, this approach is suitable for larger networks. In each cluster, every node is identified, and a cluster head sends the message to other nodes. However, the main challenge in cluster-based routing schemes is the delay overhead during the formation of clusters [6, 10, 11].

These existing schemes [6, 7, 10–14] handle the enhancement of multimedia information exchange rate and the reduction of the traffic impact on the environment. However, these existing schemes are strongly specialized for specific routing issues. Therefore, it is difficult and inappropriate to use these as fair and general performance comparison with the proposed scheme.

In recent times, state-of-the-art research has been performed in VANET communication protocols. The Probabilistic Multi-Hop Routing (PMHR) scheme [15] is an algorithm to pre-compute the routing probability. In this scheme, communication is possible between the specified source and destination in VANETs under a certain mathematical assumption. For multi-hop communications, the PMHR scheme refers to a lookup table containing the pre-computed data to quickly determine a good packet forwarder. The Connect Reliability based Efficient Routing (CRER) scheme [16] presents a new routing protocol strategy. In this scheme, the algorithm is implemented based on two network design challenges: node connectivity and channel reliability. The combination of a location-based method and time reservation-based method ensures high packet delivery and lower end-to-end delay of packet transmission.

The Adaptive Secure and Intelligent Routing (ASIR) scheme [8] is a secure and intelligent routing protocol. The ASIR scheme can transmit the data in a quickest path through the authenticated vehicles. Sending the data in a most connected path with less link connection problem enhances the system performance, and selecting the authenticated vehicles in this quickest path protects the system from the malicious attacks [8]. The Bayesian Trusted Effective Routing (BTER) scheme [9] provides a trust management mechanism between the nodes in the VANET routing process. Based on the Bayesian and the opportunistic routing forwarding method, the BTER scheme includes four steps of the routing initialization, the routing discovery, the trusted routing establishment, and the routing deletion. The BTER scheme not only improves the security of routing but also has the lower time complexity [9].

The PMHR, CRER, ASIR, and BTER schemes have attracted considerable attention and have introduced unique challenges. In this study, we compare the performance of our proposed scheme with these existing schemes [8, 9, 15, 16] and confirm the superiority of our approach.

This remainder of this manuscript is organized as follows: In Section 2, the proposed algorithms are described in detail. In Section 3, the performance evaluation results and comparisons with the PMHR, CRER, ASIR, and BTER schemes proposed in [8, 9, 15, 16] are presented. Through simulation, we show the ability of the proposed scheme to achieve high accuracy and promptness in dynamic VANET environments. Finally, the concluding remarks are stated in Section 4.

2 Proposed VANET routing algorithms

In this section, the proposed routing scheme for VANETs is explained in detail. By using the distributed timed game approach, the proposed scheme can be suitable for the fast-changing VANET environments while avoiding complex implementation mechanism.

2.1 Wireless link estimation

Generally, the formal game model consists of players, the possible strategies of the players, and utility functions of the strategies [4, 5]. Therefore, to represent a traditional game G, the game model components are given by \( G=\kern0.5em <N,\kern0.5em \mathbb{S},\left\{{U}_1,..,{U}_n\right\}> \), where N is the number of players, \( \mathbb{S} \) is a non-empty set of the strategies, U i  ∈ {U 1,.., U n } is the utility function of player i, and \( \mathbf{optimiz}{\mathbf{e}}_{S_i}:{U}_i\left({S}_i\right)\to \mathrm{\Re},\kern0.5em {S}_i\in \mathbb{S} \). In this study, we change the definition of the utility function. We introduce the concept of time by considering a timed utility function that changes with time [17]. Formally, the timed utility function is defined to map the actions and times to the player-level satisfaction (i.e., a real number) as follows:

$$ {U}_i\left({S}_i(t),t\right)={\displaystyle \underset{0}{\overset{t}{\int }}}{U}_i\left({S}_i(t)\right)dt \cong {\displaystyle \sum_{n=0}^{n=t}}{U}_i\left({S}_i(n)\right),\kern1em \mathrm{s}.\mathrm{t}.,\kern0.75em {S}_i(t),{S}_i(n)\in {\mathbb{S}}_i $$
(1)

where S i (t) is the strategy of player i at time t. Therefore, the utility function is shaped based on the time variation.

Owing to the dynamic nature of VANET—high dynamic topology and communication environment—the wireless links among vehicles varies continually. Therefore, it is important to estimate the current link status by considering several control factors. For the estimation of the degree of communication adaptability, the proposed algorithm defines a link cost (L_P) for each link. In order to handle dynamic VANET conditions, the L_P value from the vehicle i to the vehicle j is obtained as

$$ \begin{array}{l}L\_{P}_{ij}=\left[\alpha \times \left(1-\raisebox{1ex}{$\left({D}_M-{d}_{ij}\right)$}\!\left/ \!\raisebox{-1ex}{${D}_M$}\right.\right)\right]+\kern0.5em \left[\left(1-\alpha \right)\times \left(1-{\varPsi}_{ij}(t)\right)\right] + {\zeta}_{ij}(t)\\ {}\kern24.5em \mathrm{s}.\mathrm{t}.,\kern2em \alpha \kern0.5em =\frac{\mathbf{min}\ \left\{\ \left|\overrightarrow{v_i}\left({t}_i\right)\right|,\left|\overrightarrow{v_j}\left({t}_j\right)\right|\ \right\}}{\mathbf{max}\kern0.5em \left\{\ \left|\overrightarrow{v_i}\left({t}_i\right)\right|,\left|\overrightarrow{v_j}\left({t}_j\right)\right|\ \right\}}\kern3em \end{array} $$
(2)

where D M is the maximum coverage range of each vehicle and d ij is the distance between the vehicles i and j. \( \overrightarrow{v_i}\left({t}_i\right) \) and \( \overrightarrow{v_j}\left({t}_j\right) \) are the velocity vectors of vehicle i and j, respectively, at time t. Therefore, the first term in Eq. (2) is the relative distance ratio between the vehicles i and j. A closer neighboring vehicle is more suitable for routing. Therefore, if the first term is close to 0, it is preferred for stable routing. Ψ ij (t) is the entropy for vehicle j at time (t). In general, entropy is the uncertainty and a measure of the disorder in a system. It represents the topological change, which is a natural quantification of the effect of vehicle mobility on the connectivity service of VANET [18]. In this study, the basic concept of entropy is adopted for supporting and evaluating stable routing routes. For the mobile vehicle j, the entropy Ψ ij (t) is calculated as follows [18]:

$$ {\varPsi}_{ij}(t) = \frac{-{\displaystyle {\sum}_{k\in {F}_j}}{P}_k\left(t,\ {\varDelta}_t\right)\kern0.5em \times \kern0.5em \log\ {P}_k\left(t,\ {\varDelta}_t\right)}{ \log\ C\left({F}_j\right)},\kern1.25em \mathrm{s}.\kern0.5em \mathrm{t}.,\kern0.75em {P}_k\left(t,\ {\varDelta}_t\right)=\frac{a_{j,\ k}}{{\displaystyle {\sum}_{i\in {F}_j}}{a}_{j,\ i}} $$
(3)

where Δ t is a time interval, F j denotes the set of the neighboring vehicles of vehicle j, and C(F j ) is the cardinality (degree) of set F j . In order to estimate the stability of a part of a specific route, a ji represents a measure of the relative mobility between two vehicles j and i as follows:

$$ {a}_{j,\ i}=\frac{1}{I\_T}\times {\displaystyle \sum_{l=1}^{I\_T}}v\left(j,\ i,\ {t}_l\right), \kern1.25em \mathrm{s}.\mathrm{t}.,v\left(j,\ i,\ t\right)=\left|\overrightarrow{v_j}(t)-\overrightarrow{v_i}(t)\right| $$
(4)

where I_T is the number of discrete times t l . The mobility information can be calculated and disseminated to other neighboring vehicles within time interval Δ t . I_T is defined as integer multiples of Δ t . v(jit) is the relative velocity between vehicles j and i at time t. Any change can be described as a change of variable values a ji over time t, e.g., a ji (t) → a ji (t + Δ t ). The entropy Ψ ij (t) is normalized as 0 ≤ Ψ ij (t) ≤ 1. If the value of Ψ ij (t) is close to 1, the part of the route that represents the links of the path associated with an intermediate vehicle j is stable. If the value of Ψ ij (t) is close to 0, the local route is unstable [18]. The third term, ζ ij (t), is defined as a timed reinforcement function, which dynamically indicates the adaptability of the link ij from the source vehicle to the destination vehicle. As time elapses, the outcome of ζ ij (t) is dynamically adjusted. This function is explained in detail in Section 2.2.

In order to relatively estimate the current link situation, the control parameter α controls the relative weights assigned to the relative speed ratio and the entropy of the corresponding relay vehicle. In diverse network environments, a fixed value of α cannot effectively adapt to the changing conditions. In this study, we treat this scenario as an online decision problem and adaptively modify the value of α. When the relative speed of two neighbor vehicles is high, we can place more emphasis on the relative distance ratio. In this case, a higher value of α is more suitable. If the relative speed of two neighbor vehicles is low, we can place more emphasis on (1 − Ψ ij (t)). In this case, the path selection should strongly depend on a lower value of α. In the proposed algorithm, the value of α of the vehicle i is dynamically adjusted according to the relative speed ratio \( \left(\mathrm{i}.\mathrm{e}.,\frac{\mathbf{min}\ \left\{\ \left|\overrightarrow{v_i}\left({t}_i\right)\right|,\left|\overrightarrow{v_j}\left({t}_j\right)\right|\ \right\}}{\mathbf{max}\kern0.5em \left\{\ \left|\overrightarrow{v_i}\left({t}_i\right)\right|,\left|\overrightarrow{v_j}\left({t}_j\right)\right|\ \right\}}\right) \). Therefore, the system can be more responsive to current VANET conditions by using real-time network monitoring.

2.2 Opportunistic packet forwarding algorithm

In the proposed scheme, the L_P value can represent the normalized communication cost of each link. Using the L_P value, we define the path cost (PC) parameter to calculate the total routing path cost; PC is computed as the sum of all link costs from the source vehicle to the current vehicle. Based on the PC value, the proposed routing algorithm opportunistically constructs adaptive multi-hop routing paths to reach the destination vehicle.

At the start of routing operations, the source vehicle broadcasts its initial PC value (i.e., PC = 0). Within the communication coverage area, message-receiving relay vehicles individually estimate the link cost according to Eq. (2) and update the PC value to PC + log(L_P). Some relay vehicles can receive multiple PC values from different reachable neighbor vehicles. Each relay vehicle stores this information for self-organizing and independent-effective controlling. For example, the vehicle i may receive multiple PC values, \( \mathrm{i}.\mathrm{e}.,{\mathrm{PC}}_1,,,{\mathrm{PC}}_k,,,{\mathrm{PC}}_{N_i} \), where the PC k value is received from the message-sending neighbor vehicle k (1 ≤ k ≤ N i ) and N i is the total number of reachable neighbor vehicles for the vehicle i. In this case, the vehicle i calculates its minimum PC i value as follows:

$$ {\mathrm{PC}}_i= \arg\ \underset{k\in {N}_i}{\mathbf{min}}\ \left({\mathrm{PC}}_k+ \log \left(L\_{P}_{ik}\right)\right)= \arg\ \underset{k\in {N}_i}{\mathbf{min}}\left({\displaystyle \sum_{L\_{P}_{\ell}\in\ {\mathbb{I}}_k}} \log \left(L\_{P}_{\ell}\right)+ \log \left(L\_{P}_{ik}\right)\right) $$
(5)

where \( {\mathbb{I}}_k \) is the set of selected links between the source vehicle and the relay vehicle k. According to Eq. (5), the vehicle i adaptively selects one neighbor vehicle while minimizing the value of PC i , which potentially incorporates more global network information.

In this study, we model the relay vehicle selections as an iterative bargaining game according to Eq. (5). Therefore, our opportunistic link selection and route establishment process is formulated in a sequential bargaining manner. During the step-by-step iteration, the estimated PC value is recursively forwarded while opportunistically selecting the most adaptable relay nodes. This route formation process is repeated until a multi-hop path from the source to the destination vehicle is established. Finally, multiple packets are received at the destination vehicle. Owing to the opportunistic link selection approach, multiple routing paths can be configured; packets from different routing paths have different PC values. Based on the packet forwarding history, the destination vehicle can select the most adaptable routing path (Γ) as follows:

$$ \begin{array}{l}\varGamma = \arg \underset{\left\{\begin{array}{c}\hfill\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}},\kern0.75em {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}\in S\ \hfill \\ {}\hfill L\_{P}_k\in\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}\hfill \end{array}\right\}}{ \min }{\displaystyle \underset{t = {\mathcal{T}}_s}{\overset{t = {\mathcal{T}}_e}{\int }}} \log \left(L\_{P}_k\right)dt = \kern0.5em \arg \underset{\left\{\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}},\kern0.75em {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}\in \mathbb{S}\right\}}{ \min }{\displaystyle \sum_{L\_{P}_k\in\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}}} \log \left(L\_{P}_k\right)\kern3.75em \\ {}\kern1.5em = \arg \underset{\left\{\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}},\kern0.75em {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}\in \mathbb{S}\right\}}{ \min } \log {\displaystyle \prod_{L\_{P}_k\in\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}}}\left(L\_{P}_k\right) \cong \kern0.75em \arg \underset{\left\{\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}},\kern0.75em {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}\in \mathbb{S}\right\}}{ \min }{\displaystyle \prod_{L\_{P}_k\in\ {\mathbf{\mathcal{P}}}_{\boldsymbol{i}}}}\left(L\_{P}_k\right)\end{array} $$
(6)

where \( \mathbb{S} \) is the set of established routing paths and \( {\mathbf{\mathcal{P}}}_{\boldsymbol{i}} \) is the ith routing path from the source vehicle to the destination vehicle. \( {\mathcal{T}}_s \) and \( {\mathcal{T}}_e \) are the packet forwarding start time and end time, respectively. Therefore, Γ is the path with the minimum product value of link costs. In the proposed game model, the payoff of players (i.e., routing source and destination vehicles) is assumed to be the sum of (1/log(L_P k )), i.e., \( {U}_i\left({S}_i(t),t\right)\kern0.5em =\kern0.5em {\displaystyle \underset{t = {\mathcal{T}}_s}{\overset{t = {\mathcal{T}}_e}{\int }}}\left(1/ \log \left(L\_{P}_k\right)\right)dt \). In order to maximize their payoff, the players want to select the routing path while minimizing the sum of log(L_P k ) by using Eq. (6).

In the proposed scheme, each link selection decision is made in a myopic online manner. Therefore, as time elapses, the selected strategies are no longer the best ones. In order to induce relay vehicles to select globally desirable links, the destination vehicle should reinforce the most desirable path (Γ) for the next opportunistic routing decision. Periodically, the destination vehicle sends a backward packet to modify the result of the ζ(t) function of the relay vehicles in the desirable Γ path as follows:

$$ \begin{array}{l}{\zeta}_{ij}(t)=\vartheta (t)=\left\{\begin{array}{l}\vartheta (t) = \vartheta \left(t-1\right)-{\varDelta}_{\vartheta },\kern0.75em \mathrm{if}\kern0.75em {l}_{ij}\in \varGamma \\ {}\vartheta (t) = \vartheta \left(t-1\right)\kern2em ,\kern0.75em \mathrm{otherwise}\end{array}\right.\kern0.75em \\ {}\kern13.5em \end{array} $$
(7)

where l ij is the link ij and Δ ϑ is a discount factor. If l ij is in the Γ path, the outcome of ζ ij (t) monotonically decreases with Δ ϑ over time. In addition, we define a particular period of time, \( {\mathcal{P}}^{\mathrm{\mathcal{M}}} \). After every period \( {\mathcal{P}}^{\mathrm{\mathcal{M}}} \), ϑ(·) is reset to the initial value (η). Therefore, at the beginning of every period \( {\mathcal{P}}^{\mathrm{\mathcal{M}}} \), ζ(t) value is initialized. This periodic refreshment mechanism helps in adaptively reflecting the constantly changing network conditions.

2.3 Proposed scheme steps

The goal of this study is to design a completely distributed, low-complexity routing scheme for VANETs. The main novelty of our proposed scheme is to define a timed strategic game model based on the sequential bargaining approach. As mentioned earlier, traditional NBS is unsuitable for real-world VANET operations; game players do not have all the knowledge and, hence, lack the complete information to maximize their payoffs. In order to overcome this limitation, we transform the traditional NBS game into a sequential bargaining model based on a step-by-step decision process. This method can provide a good trade-off between optimized network performance and the complexity of practical implementation.

During real-world VANET operations, the payoff for the packet routing changes. As time elapses, the payoff is adjusted according to selected strategies. By considering the final payoff, we reinforce the most desirable strategies to be opportunistically reselected. Based on our timed strategic game approach, the proposed scheme can effectively approximate the optimized VANET performance. The proposed algorithm is described by the following pseudo-code and major steps.

figure a
  1. Step 1:

    Control parameters, i.e., Δ t , I_T, D M , Δ Ï‘ , \( {\mathcal{P}}^{\mathrm{\mathcal{M}}} \), η , and α, are listed in the Tables 1, 2, and 3.

  2. Step 2:

    At the start, ϑ(·) is set to the initial value (η). This initial value guarantees that each vehicle enjoys the same selection probability at the beginning of the game when routing history is unavailable.

  3. Step 3:

    Each vehicle collects the routing control information (i.e., D, d, Ψ, and ζ) individually and estimates the link cost (L_P) according to Eq. (2).

  4. Step 4:

    For relative estimation of the current link situation, the control parameter α is dynamically adjusted according to the relative speed ratio.

  5. Step 5:

    The source vehicle sends packets to the destination vehicle. Based on the opportunistic routing mechanism, our sequential bargaining process is iteratively applied to select the routing path.

  6. Step 6:

    By using (5), each relay vehicle is selected while minimizing the PC. This decision is made sequentially in an entirely distributed manner.

  7. Step 7:

    After the packets are received at the destination vehicle, the most adaptable routing path (Γ) is selected based on Eq. (6). The selected path is reinforced by using the timed reinforcement function ζ(·) in Eq. (7).

  8. Step 8:

    Each vehicle self-monitors the current VANET situation in a distributed online manner. Periodically, D, d, Ψ, and ζ values are adaptively adjusted.

  9. Step 9:

    The routing process continues based on the timed game model; the next iteration resumes at step 3.

Table 1 System parameters used in the simulation experiments
Table 2 System parameters used in the simulation experiments
Table 3 System parameters used in the simulation experiments

3 Performance evaluation

In this section, we evaluate the performance of the proposed scheme by using a simulation model; a simulation analysis allows a complex realistic modeling. In this study, we used the simulation tool MATLAB to develop our simulation model. MATLAB is one of the most widely used tools in a number of scientific simulation fields, such as digital processing, telecommunications, and mathematical analysis. In particular, the high-level syntax and dynamic types of MATLAB are ideal for model prototyping. In order to ensure that the model is sufficiently generic to be valid in the real world, the assumptions used in our simulation model were as follows:

  • The simulated system was assumed to be a TDMA packet system for VANETs.

  • The source and destination vehicles were randomly selected.

  • One hundred vehicles were distributed randomly over the 10-km road area, and the velocity of each mobile vehicle was randomly selected to be 10 m/s (36 km/h), 20 m/s (72 km/h), or 30 m/s (108 km/h).

  • The process for new message transmission was Poisson with rate λ (messages/s), and the range of offered traffic load was varied from 0 to 5.0.

  • The capacity of the network bandwidth was 30 Mbps, and each message consisted of CBR packets.

  • Network performance measures obtained on the basis of 50 simulation runs were plotted as a function of the offered traffic load.

  • The size of messages was exponentially distributed with different means for different message applications.

  • For simplicity, we assumed the absence of physical obstacles in the experiments.

Tables 1, 2, and 3 shows the system parameters used in the simulation. In order to emulate a real network system and perform a fair comparison, we used the system parameters for a realistic simulation model [5].

Based on a simulation study, we compare the performance of our scheme with other existing schemes [8, 9, 15, 16] and can confirm the performance superiority of the proposed approach. Performance measures obtained through simulation are normalized packet delay, network throughput, and Service Fail Ratio (SFR) for packet transmissions. In this study, we compare the performance of the proposed scheme with existing schemes—the PMHR scheme [15], CRER scheme [16], ASIR scheme [8], and BTER scheme [9]. These existing schemes are also developed as effective VANET routing algorithms. Although these existing schemes possess some novel features for VANETs, they have several disadvantages. First, these existing schemes cannot adaptively estimate the current VANET conditions. Therefore, each vehicle is unaware of effective routing paths to reach the destination vehicle. Second, they resolve the routing problem by using fixed system parameters. In dynamic VANET environments, routing algorithms using static parameters can potentially cause erroneous decisions.

Figure 1 shows a comparison of the performance of each scheme in terms of the normalized packet delay. In this study, transmission delay is called packet delay. It is estimated as the amount of time required to push all the packet bits into the wireless communication. Therefore, packet delay is proportional to the packet length in bits, routing path length, and number of relay nodes. As the traffic load increases, traffic congestions inevitably occur owing to the large number of packet exchanges. Therefore, the packet delay increases linearly with the traffic load. All the schemes show similar trends. However, the proposed scheme has lower packet delay than other schemes as the traffic load intensity increases from low to high.

Fig. 1
figure 1

Average packet delay

Figure 2 shows the normalized network throughput. From the simulation results obtained, it is observed that the proposed scheme can adapt to the current VANET situation and demonstrates better throughput owing to the iterative bargaining approach. In general, excellent network throughput is a highly desirable property for real-world VANET operations.

Fig. 2
figure 2

Normalized network throughput

The curves in Fig. 3 represent the SFR for packet transmissions under different network traffic loads. When the traffic load is low (λ < 0.3), the performance of all the schemes is identical. However, the SFR constantly increases with an increase in the network traffic load. In various traffic load conditions, the proposed scheme achieves a lower SFR than other schemes.

Fig. 3
figure 3

SFR for emergency messages

The simulation results shown in Figs. 1, 2, and 3 demonstrate that the proposed scheme generally exhibits superior performance than the other existing schemes in significantly different VANET traffic load situations. In order to approximate the optimized network performance, we modified the traditional NBS model, which cannot be directly applied to the VANET routing problem. For practical implementations in real-world VANET routing operations, the proposed scheme is designed by using the sequential bargaining model and timed game approach. For diverse VANET environment changes, the proposed scheme constantly monitors the current network conditions and can achieve good network performance.

4 Conclusions

In recent years, the field of VANETs has received significant attention, and an increasing number of VANET-related studies have been performed. One of the notoriously difficult challenges in VANETs is the configuration of effective routing paths. This problem is a difficult one because the network topology changes constantly and the routing links are inherently unstable. In this study, we propose a new routing scheme to select a stable routing path in a vehicular network environment. In order to adapt to the dynamic VANET scenarios, our proposed scheme is developed as a timed strategic game based on the sequential bargaining approach. By applying the step-by-step bargaining process, the proposed scheme can effectively approximate the optimized VANET performance in an entirely distributed manner. From the simulation results, the proposed scheme significantly outperforms existing schemes in terms of network throughput, delay and packet transmission ratio, etc.

References

  1. W Zhaoran, X Xianzhong, Z Dingxin, Cross-layer design for TCP performance improvement in vehicular communication networks. International Conference on Advanced Communication Technology (ICACT’2012), 2012, pp. 400–405

    Google Scholar 

  2. MC Morales, R Haw, E Cho, C Hong, S Lee, An adaptable destination-based dissemination algorithm using a publish/subscribe model in vehicular networks. JCSE 6(3), 227–242 (2012)

    Google Scholar 

  3. JH Kim, KJ Lee, TH Kim, SB Yang, Effective routing schemes for double-layered peer-to-peer systems in MANET. JCSE 5(1), 19–31 (2011)

    Google Scholar 

  4. S Kim, Cellular network bandwidth management scheme by using Nash bargaining solution. IET Communications 5(3), 371–380 (2011)

    Article  Google Scholar 

  5. S Kim, Adaptive ad-hoc network routing scheme by using incentive-based model. Ad hoc & Sensor Wireless Networks 15(2), 107–125 (2012)

    Google Scholar 

  6. F Li, Y Wang, Routing in vehicular ad hoc networks: a survey. IEEE Vehicular Technology Magazine 2(2), 12–22 (2007)

    Article  Google Scholar 

  7. X Guan, R Sengupta, H Krishnan, F Bai, A feedback-based power control algorithm design for VANET. IEEE Mobile Networking for Vehicular Environments, 2007, pp. 67–72

    Google Scholar 

  8. SK Bhoi, PM Khilar, SIR: a secure and intelligent routing protocol for vehicular ad hoc network. IET Networks 4(3), 185–194 (2015)

    Article  Google Scholar 

  9. Q Wu, L Qingzi, Z Long, Z Zhiming, A trusted routing protocol based on GeoDTN+Nav in VANET. China Communications 11(14), 166–174 (2014)

    Article  Google Scholar 

  10. U Nagaraj, MU Kharat, P Dhamal, Study of various routing protocols in VANET. International Journal of Computer Science & Technology 2(4), 45–52 (2011)

    Google Scholar 

  11. SK Bhoi, PM Khilar, Vehicular communication: a survey. IET Networks 3(3), 204–217 (2014)

    Article  Google Scholar 

  12. DB Rawat, DC Popescu, Y Gongjun, S Olariu, Enhancing VANET performance by joint adaptation of transmission power and contention window size. IEEE Transactions on Parallel and Distributed Systems 22(9), 1528–1535 (2011)

    Article  Google Scholar 

  13. T Tielert, D Jiang, H Hartenstein, L Delgrossi, Joint power/rate congestion control optimizing packet reception in vehicle safety communications. ACM MobiSys 13, 51–60 (2013)

    Google Scholar 

  14. R Schmidt, T Leinmuller, E Schoch, F Kargl, G Schafer, Exploration of adaptive beaconing for efficient intervehicle safety communication. IEEE Network 24(1), 14–19 (2010)

    Article  Google Scholar 

  15. J Fukuyama, A probabilistic protocol for multi-hop routing in VANETs. IEEE ICC’2009, 2009, pp. 1–6

    Google Scholar 

  16. MD Nuri, HH Nuri, Strategy for efficient routing in VANET. International Symposium in Information Technology (ITSim’2010), 2010, pp. 903–908

    Google Scholar 

  17. SA Sarcia', Timed strategic games A new game theory for managing strategic plans in the time dimension. IEEE CogSIMA, 2013, pp. 187–194

    Google Scholar 

  18. H Shen, B Shi, L Zou, H Gong, A distributed entropy-based long-life QoS routing algorithm in ad hoc network. IEEE CCECE 2003, 1535–1538 (2003)

    Google Scholar 

Download references

Acknowledgements

This research was supported by the MSIP (Ministry of Science, ICT and Future Planning), Korea, under the ITRC (Information Technology Research Center) support program (IITP-2015-H8501-15-1018) supervised by the IITP (Institute for Information & Communications Technology Promotion) and was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (NRF-2015R1D1A1A01060835).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sungwook Kim.

Additional information

Competing interests

The author declares that he has no competing interests.

Authors’ contribution

Sungwook Kim is a sole author of this work and ES (i.e., participated in the design of the study and performed the statistical analysis).

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, S. Timed bargaining-based opportunistic routing model for dynamic vehicular ad hoc network. J Wireless Com Network 2016, 14 (2016). https://doi.org/10.1186/s13638-016-0516-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1186/s13638-016-0516-5

Keywords