Keywords

1 Introduction

Vehicular ad hoc network (VANET) is becoming nowadays an attractive topic for the research community with the increase in the number of traffic accidents and the complexity of the roads infrastructure. VANET is a new class of wireless networks that allows vehicle-to-infrastructure communication and vehicle-to-vehicle communications. This technology offers a wide set of applications and services ranging from safety applications and traffic management systems to commercial and marketing services. Safety, emergency, and multimedia applications of VANET require to assure a high level of quality of service (QoS) through the network. Practically, VANET requires real-time message propagation that is able to deliver data in a timely and accurate manner. For example, considering the case of safety applications, any delay in the message delivery may entrain dangerous and mortal accidents. Similarly, exchanging multimedia services such as files and video streams requires a high level of QoS [1].

2 Optimization Techniques

2.1 Ant Colony Optimization

Ant colony optimization is a probabilistic approach that is used to solve several discrete optimization problems. This approach inherits the normal behavior of ants that tend to find the shortest route while searching for food. In fact, the ants that move randomly toward the food indicate the other ants the shortest path to follow by depositing chemical substance called pheromone. Thereafter, paths with higher pheromone values are chosen to be followed.

Thus, the shortest path will be continuously reinforced by more pheromone values since it will get marched repeatedly by the ants [2]. In contrary, the pheromone trails of the not marched paths will decrease due to the evaporation process. The evaporation is important to avoid the convergence for local optimal solution since without evaporation, the routes marched by the first ants will be extremely attractive for the following ants. The behavior of ants has attracted the researchers due to its dynamic nature that makes it adaptive to changes in real-time applications. Therefore, it has been widely used to solve many problems such as vehicle routing, traveling salesman problem (TSP), machine scheduling, telecommunication networks, ad hoc networks routing, and personnel placement in airline companies.

To illustrate how the ant colony optimization algorithm works, we show in the following how ACO can be applied to solve the TSP, which is a routing problem. Given a set of cities and the distances separating each pair of cities, the problem of TSP is concerned with finding the shortest path that visits each city just once and turns back to the original city. This problem could be modeled as a construction graph where the cities represent the vertices and the distances separating the cities are the edges. The ACO solution works as follows: Initially, every ant begins from a randomly selected vertex (city). Next, ants choose their next vertex to get in a probabilistic manner according to the highest pheromone value.

This process continues until each ant has visited all the vertices on the graph only once. Now, pheromone values are updated on all the edges according to the quality of solution to which they belong so that the pheromone values for shorter routes would be greater than other routes. Thereafter, the pheromone values begin to evaporate and only the short tours will be reinforced by more pheromone values. This process is repeated for a specified number of iterations, and the best discovered tour is maintained as final solution. This process is illustrated in Fig. 1.

Fig. 1
figure 1

Ant colony optimization

Full size image

Therefore, in VANET, to guarantee choosing the optimal paths in terms of QoS, mobility, and delay, an ant colony optimization algorithm is used where proactive discovery by ant agents is initiated the find the best paths.

2.2 Dempster–Shafer

Dempster-Shafer is a mathematical theory elaborated by Arthur P. Dempster and Glenn Shafer [3]. This theory combines evidences from independent sources to come up with a degree of belief (belief function). It relies on two main ideas: (1) acquiring degrees of belief from subjective probabilities and (2) combining these beliefs.

To illustrate how these two ideas work, as an example, let us assume that the subjective probabilities for the trustworthiness of Doctor John are known. The probability that John is trustworthy is 0.9, while the probability that he is untrustworthy is 0.1. Suppose that John says that a patient, Bob, suffers from diabetes. This allegation must be true if John is trustworthy but not necessarily false if he is untrustworthy. Thus, his testimony alone justifies a 0.9 degree of belief that Bob suffers from diabetes, but only a zero degree of belief (not a 0.1) that Bob is healthy. This zero does not imply that we are sure that Bob does not suffer from diabetes, but simply implies that John’s testimony gives no reason to believe that Bob is healthy. The 0.9 and the zero together form a belief function.

In order to explain how the combination rule for degrees of belief works, we suppose that we know another doctor, called Alice, and that Alice is trustworthy with probability of 0.9 and untrustworthy with probability of 0.1. Assume that Alice witnesses as well that Bob suffers from diabetes. Since the trustworthiness of John is independent from the trustworthiness of Alice, we may multiply the probabilities of these two events. The probability that both are trustworthy is 0.9 × 0.9 = 0.81. The probability that neither John nor Alice is trustworthy will be 0.1 × 0.1 = 0.01. Finally, the likelihood that at least one is trustworthy is 1 − 0.01 = 0.99. Since both doctors said that Bob suffers from diabetes, at least of them being trustworthy means that Bob really suffers from diabetes, and we may hence assign this event a degree of belief of 0.99 as explained before.

On the other hand, if John’s and Alice’s testimonies were contradictory in the sense that john says that Bob suffers from diabetes, while Alice says that he does not. Now, both cannot be right and hence cannot be both trustworthy. The prior probabilities that only John is trustworthy, that only Alice is trustworthy, and that neither is trustworthy are 0.09, 0.09, and 0.01, respectively, and the posterior probabilities (given that not both are trustworthy) are 9/19, 9/19, and 1/19, respectively. Hence, we have a 9/19° of belief that Bob suffers from diabetes (because John is trustworthy) and a 9/19° of belief that Bob is sound and healthy (because Alice is trustworthy). Thus, Dempster-Shafer gives a weight for each evidence according to the trustworthiness level of the person giving the evidence and is necessary hence to discount evidences from untrustworthy observers upon aggregating the different testimonies. This appealing feature motivated us to use Dempster-Shafer while detecting the misbehaving vehicles since we are proposing a cooperative detection mechanism where evidences from different sources need to be aggregated. Therefore, Dempster-Shafer can be a solution to come up with reliable and credible decisions.

Another important characteristic of Dempster-Shafer is that it supports uncertain evidences. Suppose, for example, that Alice and John witness that a thief got in Bob’s home. However, they might both heard the voice of a noise coming from a cat and thought it is coming from a thief. To express this uncertainty, Bob can consider three evidences: (1) evidence for Alice’s trustworthiness, (2) evidence for John’s trustworthiness, and (3) evidence for the possibility of the presence of a cat. Now, Bob can combine these three items of evidences through Dempster’s rule of combination to come up with the final decision taking into consideration that both observers may be unreliable. This feature can be exploited to improve the detection for misbehaving vehicles in VANET and overcome the problem of ambiguity caused by the high mobility of the vehicles and the channel collisions.

2.3 Repeated Game Theory

Game theory is a formal study of conflict and cooperation that applies whenever the actions of several peers are interdependent in the sense that the strategy of one game’s component depends on the action of another game component [4]. The motivation behind using game theory is arriving at optimal decision. Consider, for example, that a company decides to reduce prices in order to augment its profit. Without considering the other players’ (companies) actions, this action may be counterproductive and the company will lose money if the other companies apply a policy of price cuts. Here lies the importance of considering the different parties’ strategies upon building any strategy. Game theoretical concepts have been widely used to solve problems in the fields of economy, biology, military, and computer science. To be clear and meaningful, each game should describe seven principal elements: players, actions, information, strategies, outcomes, payoff, and equilibrium. The players are the game parties that are responsible for making decisions. The actions are the set of options from which the players have to choose. The information represents the learning of the player upon making decision. The strategies describe the set of principles that control the decisions of the player at each stage of the game. The outcomes are the expected or desired output of the game such as increase in profits. The payoffs describe the utilities yielded by the player in a specific outcome. Finally, the equilibrium represents a stable solution in which no player has an interest to take unilateral decisions and change his strategy.

Repeated game is a type of game theory in which players repeat their actions over and over again. To show the importance of using repeated game models, we present a motivating example based on the Prisoner’s Dilemma [5]. The Prisoner’s Dilemma models the investigation in a crime where two prisoners suspected to be committed a crime together are arrested. The investigator isolates them and suggests a deal saying: (1) if one of them confesses against the other one, the confessor will get free (payoff: 0) and the offender will spend 4 years in prison (payoff: 4), (2) if they both confess, they will bear a less cruel punishment by being jailed 3 years (payoff: 3), and (3) if they both decline to confess, they will both bear a reduced sentence lack of evidences (payoff: 1). This deal can be summarized in the following bimatrix (Table 1):

Table 1 Payoff matrix of the prisoner’s dilemma
Full size table

The question is how should the prisoners behave in such game? Each prisoner will have the following thinking:

  • If the other prisoner confesses, I have to confess (since 3 years are less than 4 years).

  • If the other prisoner refuses to confess, I have to confess (since getting free is better than 1 year in jail).

If the game is played one shot, the best strategy for both players is to confess whatever the opponent did, thus staying 3 years in jail. However, if the game is played repeatedly, then the previous actions of each other become observable and they will know each other’s decisions. Then, they may get a better result by not confessing together (1 year in jail). Here lies the dilemma of the prisoners.

In VANET, the vehicles have to make decisions about cooperating with each other. In making these decisions, nodes may behave selfishly, seeking exclusively for their own interests. This makes the objectives of the different nodes conflicting (some nodes need to be served and others consider that their interests lie in being uncooperative). Thus, the application of game theory may be appropriate, as game theory analyzes situations in which player objectives are in conflict. Moreover, the vehicles’ decision depends on the other vehicles’ decisions. Therefore, the repeated games are the best to model such situation.

3 Clustering in VANET

The communication in VANETs entrains a high level of overhead, collision, and contention. In order to ensure efficient communications and mitigate the channel collision, overhead, and contention, there should be wireless backbone architecture able to elect some nodes to assume the network responsibilities. One solution is to gather the nodes into clusters and elect for each cluster a specified node to serve as cluster head. The function of the cluster head is to achieve both intra-cluster coordination, and inter-cluster communication. The intra-cluster coordination involves the coordination among the nodes within each cluster. In the inter-cluster communication, the cluster members charge the cluster head to communicate with the other cluster heads on behalf on them. The clustering imposes several challenges that should be taken into consideration such as which node has to be elected as cluster head? How the election procedure is done? What are the requirements of the cluster heads? How to increase and maintain the clusters lifetime? Based on these challenges, several clustering algorithms for VANET have been proposed trying to answer these questions. In the following, we present an overview on the main contributions in this context.

APROVE [6] uses the affinity propagation algorithm to perform a clustering that minimizes the distance and the mobility between cluster heads and members. The affinity metric is composed of responsibility and availability factors. Responsibility signals how compatible is one node to become exemplar while availability signals the willingness of the node to become exemplar.

Modified DMAC [7] was proposed on top of the original Basagni’s distributed and mobility-adaptive clustering algorithm. Its basic idea is to increase the stability and avoid re-clustering of the group of vehicles moving in different directions using a freshness parameter. In this algorithm, each node has to know its moving direction, current position, and velocity. The authors in [8] propose a multi-hop clustering that uses the relative mobility between multi-hop away nodes. The beacon delay is used to calculate this metric. The cluster head is elected according to the smallest aggregate mobility value. This approach considers also the problem of re-clustering by postponing it for some time. In [9], the authors use complex metric composed of traffic conditions, connection graph, and link quality. Before assigning a node to a cluster, a check on the node’s reliability is done using the membership lifetime counter. This has the advantage of avoiding needless re-clustering.

Presented clustering algorithms are proposed for different purposes such as clusters stability and overhead minimization. However, these algorithms ignore the QoS which is important for safety, emergency, and multimedia services in VANET [10]. The QoS relies primarily on connectivity, reliability, and end-to-end delay. Thus, any clustering protocol in VANET is to maintain the stability of the vehicular network while achieving a trade-off between QoS requirements and mobility constraints.

3.1 Routing in VANET

After the clusters are formed, it is important to develop a routing algorithm able to achieve the communications among clusters. Routing refers to the process of carrying a packet from source to destination. In ad hoc networks, this process encounters several challenges. These challenges range from the dynamic topology of the network, scalability, and limited physical security, to bandwidth and energy constraints. Based on these challenges, several routing protocols are presented MANETs and VANETs.

Routing based on ant colony optimization routing algorithm using ant agents for MANETs (RAAM) [11] was proposed to reduce the end-to-end delay. This can be done by creating multiple ant colonies that will travel through different paths to select the optimal one. Nevertheless, the overhead is the shortcoming that encounters this algorithm.

Ant-colony-based routing algorithm (ARA) [12] gets several paths from source to destination to transfer the packets. The drawback of ARA is that it cannot respond directly to topology change because of its passive nature. Probabilistic emergent routing algorithm (PERA) [13] is, in contrary, an active method that periodically broadcasts ants so as to avoid the local best solution. However, the overhead of the routing table and the periodic broadcasts is a drawback that faces PERA.

The idea of AntHocNet [14] is to achieve a dynamic traffic loading balance for the whole network in order to reveal the importance of the quality-of-service issue. Nevertheless, AntHocNet suffers from several limitations such as the long search time and the early convergence for large scales.

3.2 Routing Based on Multi-point Relay Nodes

The classical OLSR [15] protocol has been modeled to cope with mobile ad hoc networks (MANETs). Its basic idea is to elect a cluster head for each group of neighbor nodes and divides hence the network into clusters. These heads then select a set of specialized nodes called MultiPoints relay (MPRs). The function of the MPR nodes is to reduce the overhead of flooding messages by minimizing the duplicate transmissions within the same zone.

QOLSR [16] was design on top of OLSR to consider the QoS of the nodes during the election of heads and the selection of MPRs. In fact, QOLSR focuses on choosing optimal paths satisfying the QoS constraints. Though the QOLSR is unable to deal with VANETs, it considers exclusively the nodes’ bandwidth ignoring thus some other important metrics such as mobility.

Then came QoS-OLSR [17], a cluster-based protocol that aims to prolong the network lifetime. When electing heads and choosing MPRs, this protocol considers, in addition to the bandwidth, some metrics that may affect the network lifetime such as the residual energy. Nevertheless, the QoS-OLSR has many limitations that make it inadequate to achieve the VANET requirements since it ignores the mobility of nodes while computing the QoS.

In summary, VANETs have some characteristics that make them unique among other types of networks. Practically, VANET is characterized by the very high mobility of its nodes and the frequent disconnections. Numerous routing protocols have been proposed for MANETs, and some of them could be applied to VANETs. Nevertheless, simulation results proved that they suffer from bad performances due to the specific features of VANET such as rapid vehicles movement, dynamic packets exchange, and high speed of nodes. Thus, finding and maintaining routes is a very challenging task in VANETs.

4 Conclusion

Various optimization and QoS protocols have been developed that works in IEEE 802.11p which is suitable for the VANETs. This paper gives the review of various optimization techniques and QoS protocols in VANETs. Every protocol has its own advantages and disadvantages. Moreover, the existing routing algorithms are unable to select and maintain the optimal paths in terms of QoS, stability, delay, and overhead. Concerning the misbehaving vehicles, the existing approaches have several limitations that make them inefficient to deal with the selfish nodes such as lack for scalability and centralization, ambiguous collisions, and false alarms. We hope that this concise work will help in better understanding of QoS protocols in VANETs and pave their way to develop a new protocol to overcome the drawbacks of existing protocols.