# Routing in Vehicular Ad Hoc Networks: Main Characteristics and Tendencies

Authors: Joilson Alves Junior; Emilio C. G. Wille
Journal: Journal of Computer Networks and Communications
 (2018)

---

## Abstract

The message routing in vehicular ad hoc networks (VANETs) is an attractive and promising area for research. These networks do not have a central coordination, the nodes are mobile, and the topology is highly dynamic, making the routing process a big challenge, since it is responsible for ensuring message delivery with small overhead and delay. In the literature, there are several routing protocols that can be used in VANETs; in this way, the main objective of this work is to classify, discuss, and compare such protocols through a review of research in this field. The protocol classification is based on the following criteria: type of architecture and mode of operation. Moreover, this work emphasizes the potential of the application of bioinspired and bus-based techniques in the routing problem solutions, which has been revealed as a main tendency nowadays. Bioinspired routing protocols are based on the behavior of entities in the nature, and they are meant to work in a distributed mode, using mobile agents to find routes with specific features. In a parallel line of research, the differentiated behavior of urban transport vehicles suggests that a system that makes use of buses to create a communication infrastructure can perform better when compared to a system that does not distinguish between vehicles.


---

## Body

## 1. Introduction

Automobiles are considered the main form of transportation by millions of people around the world. With the growing use of this transport mechanism, it becomes a necessity to allow the communication between the vehicles, with the objective of providing safety and entertainment to their occupants.The widespread use of automobiles has contributed largely to the existence of traffic saturation and danger situations, and it has risen the probability of accident occurring. These facts motivated the development of applications which help the vehicle conductor when taking decisions and provide safety to all the occupants.Besides, these applications can help the conductor to avoid traffic jams while choosing the trajectory, raise the vehicle efficiency, and contribute with the reduction of environmental pollution. Regarding the entertainment area, building a communication system among the vehicles can bring many advantages to the occupants, allowing them to share music, videos, or even the interaction among the people in different vehicles and the interaction with information points existing on roads.A solution able to provide the communication among vehicles is the deploying of a vehicular ad hoc network (VANET) [1]. Ad hoc networks are characterized by being established anywhere because they do not depend on a fixed infrastructure (usually created through access points or base stations) [2]. In ad hoc networks, the units are mostly small, portable, and battery-powered, and they communicate among each other through radiofrequency signals.Since the radio signals’ reach is limited, each node can only communicate directly with other nodes which are inside the range of their signal transmissions. However, a node may need to transmit information to other nodes which are beyond its range. For that reason, the nodes must cooperate among themselves acting as routers, forwarding the information from the source node to the destination node [3]. For information to be transmitted from the source to the destination node, the network must be connected, which means the network nodes must be capable of finding other nodes inside the range of their signals, in such a way that the source and the destination can always find a route to communicate between themselves.VANETs, as a particular case of mobile ad hoc networks, are also characterized by the high mobility of the nodes (vehicles), the scarce or uneven distribution of vehicles, and the limited communication between nodes due to the constraints imposed by the topology of highways and/or urban roads [4].In VANETs, as well as in most networks, the communication among the nodes must follow the Open Systems Interconnection (OSI) standardization. Such a standard is divided into seven layers (physical, data link, network, transport, session, presentation, and application) which define general guidelines for network operation. In vehicular networks, the physical, data link, and network layers were the ones that had the biggest number of definitions, which means that they deserve being highlighted.Regarding physical and data link layers, the communication through radiofrequency must use Dedicated Short-Range Communication (DSRC) standard [5], operating at 5.9 GHz. The Wireless Access in Vehicular Environments (WAVE) pattern [6], developed by the Institute of Electrical and Electronics Engineers (IEEE), should operate in the band defined by the DSRC. The WAVE defines a new family of four protocols dedicated to the communication among vehicles, named IEEE 1609 (IEEE 1609.1, IEEE 1609.2, IEEE 1609.3, and IEEE 1609.4). IEEE 1609.3, as an example, specifies the protocols of the network layer.The WAVE is built considering the specifications on the American DSRC, dividing the frequency spectrum into seven channels of 10 MHz each. As the pattern is being developed for VANETs, it must consider the node velocity, the signal transmission radius, and the transmission data rate. This way, the following characteristics can be highlighted: nodes velocity up to 190 km/h, transmission radius up to 1 km (in the absence of obstacles), and transmission rate between 6 and 27 Mbps. The WAVE also specifies a MAC layer which supports the high speed of the nodes and maintains the latency minimized. Therefore, the MAC layer must follow an adaptation of the IEEE 802.11e MAC layer [5].The network layer, among other attributions, is responsible for defining rules of packet routing. The packet routing process is the service responsible for discovering and keeping the routes among the origin and the destination nodes, and the routing protocols control such a service. The routing protocols can be classified based on the following parameters: type of architecture and operation mode. The operation mode englobes the routing type, and it can be divided into topology, geographic, opportunistic, and dissemination.In this article, the main objective is to classify, discuss, and compare the main routing protocols developed for VANETs, as well as to emphasize the potential of the application of bioinspired and bus-based techniques in the routing problem solutions, which has been revealed as a main tendency nowadays.The rest of this paper is organized as follows. Section2 presents a classification of the routing protocols used in VANETs. Representative classical protocols are examined in Section 3. Some tendencies considering the design of routing protocols considering bioinspired techniques are presented in Section 4 and in Section 5 considering bus-based techniques. The current routing protocols for VANETs are examined in Section 7. Finally, a short comparison between the protocols and conclusions is drawn in Section 7.


## 2. Classification of Routing Protocols in VANETs

In VANETs, routing protocols can be classified based on the following parameters:type of architecture and mode of operation.


### 2.1. Type of Architecture

The type of architecture involves the network topology where the protocol will act, and it can be divided intoad hoc, infrastructured, or hybrid, as shown in Figure 1.Figure 1
Network architectures for VANETs. (a) Infra-structured. (b) Ad hoc. (c) Hybrid.
(a)
(b)
(c)In the infrastructured mode (Figure1(a)), also known as vehicle-to-infrastructure (V2I), the VANET uses fixed access points so that the vehicles can connect to the Internet and can obtain traffic or routing data information. The communication is made only among the vehicles and the fixed access points. This kind of architecture provides connectivity to the mobile nodes; however, it can be unfeasible if considering the costs of infrastructure and edification [7].In the ad hoc mode (Figure1(b)), also known as vehicle-to-vehicle (V2V), all vehicles can be used to build a fully mobile network, exchanging information directly with each other without the need of a central access point. The nodes must be able to cooperate among each other, acting as routers and transmitting messages from the origin to the destination node. For example, such architecture can be used to avoid collisions in intersections without traffic lights, detection of traffic jamming, detection of accidents, and detection of traffic slowdown [7].The hybrid architecture (Figure1(c)), which combines infrastructured and ad hoc architectures, has also been used in VANETs. Among many applications, this type of architecture can be applied so that the vehicles can exchange information among each other and can also be connected to the Internet through the fixed access points [7, 8].


### 2.2. Mode of Operation

The mode of operation comprehends the type of routing. It can be divided intotopology, geographic, opportunistic, and dissemination as illustrated in the flowchart presented in Figure 2, which classifies the operation mode according to the type of architecture.Figure 2
Mode of operation for routing protocols.Routing protocols based on topology work in theunicast mode [9], and they can be classified according to the type of architecture as ad hoc [10]. These protocols are normally classified into two main groups: proactive and reactive.Proactive protocols keep information about the network topology constantly updated in the node’s routing tables, regardless the use of stored routes [11]. When a client needs to send a message through the network, it knows previously which route is assumed to be followed. Proactive protocols present high control message overload because control messages are periodically sent to all nodes in order to keep the routing tables updated. The Destination-Sequenced Distance Vector (DSDV) [11] is an example of a proactive protocol.Reactive protocols do not keep routing information updated, and they find routes only when an origin node needs to transmit data packets to a destination node [12, 13]. When it is necessary to send a message to a destination, a route discovery process is initiated, usually by flooding. If the destination is reached, an answer message is sent back to the origin. When the route is established, it is kept in the routing table until the destination becomes unreachable or the origin does not need the route anymore. Such protocols present low control message overload, even though they raise the latency of the routing discovery procedure. The Ad hoc On-demand Distance Vector (AODV) routing [13] and the Ad hoc On-demand Multipath Distance Vector (AOMDV) routing [12] are examples of reactive protocols.Routing protocols based on geographic position work in the unicast mode [9], and they can be classified according to the type of architecture as hybrid [10]. They are characterized by finding the best route between the origin and the destination based on their geographic positions, which forces each node to have a global position system. On these protocols, an origin node sends the packets to the destination node by multihop. However, so that it can happen, the node needs to know the geographic position of its neighbors.The focus of these protocols is to allow scalability in high-mobility environments since it is not necessary to keep information about the routes of all nodes in the routing tables because all this information is determined at the time the packets are transmitted or retransmitted [14–16]. Among the protocols based on geographic position, the following can be cited: Greedy Perimeter Stateless Routing (GPSR) [14], Geographic Source Routing (GSR) [17], Anchor-based Street and Traffic Aware Routing (A-STAR) [16], and the Connectivity-Aware Routing (CAR) [15].Opportunistic protocols can be classified according to the type of architecture as ad hoc. These protocols consider scenarios with frequent disconnections, and they use the method known ascarry-and-forward to transmit the information. The carry-and-forward method consists in transporting or storing the information during a certain interval of time and return to transmitting whenever possible [18–20].Among the many existing opportunistic protocols, the most important are MaxProp [18], Scalable Knowledge-Based Routing (SKVR) [19], and the Vehicle-Assisted Data Delivery (VADD) [20]. The opportunistic protocols also establish routes between origins and destinations in the unicast mode [9], but they have a great advantage, which is the possibility of having temporary connectivity between different nodes for forwarding messages.Dissemination protocols can be classified according to the type of architecture in infrastructured, and they are characterized by send information inbroadcast [9] or geocast [9], being indicated for several applications in vehicular networks such as safety applications. In these protocols, for example, when a road accident occurs, alarm messages can be transmitted to inform other vehicles about the case. Some examples of dissemination protocols are Urban Multihop Broadcast (UMB) protocol [21] and the Optimized Dissemination of Alarm Messages (ODAM) [22].


## 2.1. Type of Architecture

The type of architecture involves the network topology where the protocol will act, and it can be divided intoad hoc, infrastructured, or hybrid, as shown in Figure 1.Figure 1
Network architectures for VANETs. (a) Infra-structured. (b) Ad hoc. (c) Hybrid.
(a)
(b)
(c)In the infrastructured mode (Figure1(a)), also known as vehicle-to-infrastructure (V2I), the VANET uses fixed access points so that the vehicles can connect to the Internet and can obtain traffic or routing data information. The communication is made only among the vehicles and the fixed access points. This kind of architecture provides connectivity to the mobile nodes; however, it can be unfeasible if considering the costs of infrastructure and edification [7].In the ad hoc mode (Figure1(b)), also known as vehicle-to-vehicle (V2V), all vehicles can be used to build a fully mobile network, exchanging information directly with each other without the need of a central access point. The nodes must be able to cooperate among each other, acting as routers and transmitting messages from the origin to the destination node. For example, such architecture can be used to avoid collisions in intersections without traffic lights, detection of traffic jamming, detection of accidents, and detection of traffic slowdown [7].The hybrid architecture (Figure1(c)), which combines infrastructured and ad hoc architectures, has also been used in VANETs. Among many applications, this type of architecture can be applied so that the vehicles can exchange information among each other and can also be connected to the Internet through the fixed access points [7, 8].


## 2.2. Mode of Operation

The mode of operation comprehends the type of routing. It can be divided intotopology, geographic, opportunistic, and dissemination as illustrated in the flowchart presented in Figure 2, which classifies the operation mode according to the type of architecture.Figure 2
Mode of operation for routing protocols.Routing protocols based on topology work in theunicast mode [9], and they can be classified according to the type of architecture as ad hoc [10]. These protocols are normally classified into two main groups: proactive and reactive.Proactive protocols keep information about the network topology constantly updated in the node’s routing tables, regardless the use of stored routes [11]. When a client needs to send a message through the network, it knows previously which route is assumed to be followed. Proactive protocols present high control message overload because control messages are periodically sent to all nodes in order to keep the routing tables updated. The Destination-Sequenced Distance Vector (DSDV) [11] is an example of a proactive protocol.Reactive protocols do not keep routing information updated, and they find routes only when an origin node needs to transmit data packets to a destination node [12, 13]. When it is necessary to send a message to a destination, a route discovery process is initiated, usually by flooding. If the destination is reached, an answer message is sent back to the origin. When the route is established, it is kept in the routing table until the destination becomes unreachable or the origin does not need the route anymore. Such protocols present low control message overload, even though they raise the latency of the routing discovery procedure. The Ad hoc On-demand Distance Vector (AODV) routing [13] and the Ad hoc On-demand Multipath Distance Vector (AOMDV) routing [12] are examples of reactive protocols.Routing protocols based on geographic position work in the unicast mode [9], and they can be classified according to the type of architecture as hybrid [10]. They are characterized by finding the best route between the origin and the destination based on their geographic positions, which forces each node to have a global position system. On these protocols, an origin node sends the packets to the destination node by multihop. However, so that it can happen, the node needs to know the geographic position of its neighbors.The focus of these protocols is to allow scalability in high-mobility environments since it is not necessary to keep information about the routes of all nodes in the routing tables because all this information is determined at the time the packets are transmitted or retransmitted [14–16]. Among the protocols based on geographic position, the following can be cited: Greedy Perimeter Stateless Routing (GPSR) [14], Geographic Source Routing (GSR) [17], Anchor-based Street and Traffic Aware Routing (A-STAR) [16], and the Connectivity-Aware Routing (CAR) [15].Opportunistic protocols can be classified according to the type of architecture as ad hoc. These protocols consider scenarios with frequent disconnections, and they use the method known ascarry-and-forward to transmit the information. The carry-and-forward method consists in transporting or storing the information during a certain interval of time and return to transmitting whenever possible [18–20].Among the many existing opportunistic protocols, the most important are MaxProp [18], Scalable Knowledge-Based Routing (SKVR) [19], and the Vehicle-Assisted Data Delivery (VADD) [20]. The opportunistic protocols also establish routes between origins and destinations in the unicast mode [9], but they have a great advantage, which is the possibility of having temporary connectivity between different nodes for forwarding messages.Dissemination protocols can be classified according to the type of architecture in infrastructured, and they are characterized by send information inbroadcast [9] or geocast [9], being indicated for several applications in vehicular networks such as safety applications. In these protocols, for example, when a road accident occurs, alarm messages can be transmitted to inform other vehicles about the case. Some examples of dissemination protocols are Urban Multihop Broadcast (UMB) protocol [21] and the Optimized Dissemination of Alarm Messages (ODAM) [22].


## 3. Representative Routing Protocols

A routing process is the service responsible for discovering and keeping the routes among origin and destination nodes, being the routing protocols responsible for managing this service. This way, the routing becomes an essential service for network operation. It is important to mention that most of the routing protocols used in VANETs were originally developed for mobile ad hoc networks (MANETs). In this section, a set of representative routing protocols which can be used on vehicular networks are presented.


### 3.1. Ad Hoc On-Demand Distance Vector (AODV)

The Ad hoc On-demand Distance Vector (AODV) [13] was projected to be used in ad hoc networks containing dozens to thousands of mobile nodes. The main objective of the protocol is to adapt quickly and dynamically to the variation of the conditions of network links, finding routes in order to avoid the waste of bandwidth and to minimize memory, and processing usage in nodes which act as routers.The AODV acts on demand, which means it searches for routes only when they are necessary using a route discovery mechanism. Each node owns, in its routing table, only information about the next hop for which the message must be sent to get to the destination. Then, when the nodek wants to send a message to node j, it verifies on its routing table the next hop to get to the node j and sends the message to the node which is the next hop. If node j is not the destination, it repeats the process until the message arrives to the destination. When the origin does not have a next hop to the desired destination, it executes the route discovery process.


#### 3.1.1. Route Discovering

The AODV builds routes using route request (RREQ) and route reply (RREP) messages. When an origin node needs to send a data message to a node whose route is still unknown, an RREQ is sent in broadcast through the network. Nodes that receive this message update their routing tables, adding an input to inform how to get to the origin, and they are assumed to send a message to the node which has just sent the RREQ. The nodes keep control of the origin of the RREQs and the identification of the broadcast. If they receive a message that has already been processed, the message is discarded. A node receiving a RREQ can send a RREP to the origin if it is the destination or if it knows a route to the destination. This RREP is sent in unicast through the reverse path created by the RREQ. As the RREP message must be sent back to the origin, the nodes update their routing tables adding an input to inform the RREQ’s original destination (which now is the RREP’s origin) sending a message to the node which has just sent the RREP. When the origin node receives the RREP, it can then transmit the data packet to the destination, simply by forwarding the message to the node which has delivered the RREP.


#### 3.1.2. Route Maintenance

The displacement of a node can cause a link failure. In this situation, the node which has detected the fault sends a route error (RERR) message to the origin, warning about the link failure. If the origin still wishes to use the route, the route discovering process is restarted.


### 3.2. Urban Multihop Broadcast (UMB) Protocol

Communications among vehicles can use multihop transmissions as a way to send information to places beyond the reach of the origin nodes. However, multihop transmissions can be challenging in urban areas since those areas have several obstacles which difficult the transmission.The Urban Multihop Broadcast (UMB) protocol [21] seeks to overcome problems related to packet collisions, interferences, and hidden nodes while sending messages through multihop in urban areas. This way, UMB uses a process based on the request-to-send (RTS) and clear-to-send (CTS) approaches [23].The UMB protocol works in two distinct ways, in thedirectional diffusion mode and in the intersection mode. In the directional diffusion, the origin node chooses the farthest node in relation to its position to recognize the messages and continue the diffusion. Nevertheless, this operation is made without previous knowledge about the network topology. Hence, the farthest node is selected without previous knowledge of its unique identifier (UID) on the network, or its neighbors’ position. In the intersection mode, the UMB admits installing repeaters on the intersections of roads to conduct the diffusion, and these repeaters must possess a straight view line to all parts in the road. When an intersection is discovered on the way of the packet transmission, new diffusions must be initiated in all directions in this intersection since repeaters have the best view line with the other road segments, mainly when there are high buildings around. In summary, the most important objectives of the UMB are to avoid collisions due to the hidden nodes; make efficient use of the channel; and make the communication through diffusion trustworthy, spreading the messages in all directions in intersections.


### 3.3. MaxProb Protocol (MaxProb)

In MaxProb protocol [18], the knowledge acquired during the connection of the network nodes is used to optimize the message forwarding. All the nodes belonging to the network have a vector of ordered packets, in which the ordering works according to the delivery likelihood of each packet.Besides the vector of ordered packets, the nodes also have a table withweights of all destination nodes. Each weight represents the frequency of a connection and initially it has the same value for all the destinations, but as the meetings among the nodes happen, this weight can be improved.As an example, consider a network with 5 nodes. In this network, all the nodes keep a list with the weights of all the other nodes, being each weight initially equal to 0.25 (the sum of all the weights is equal to 1). At the moment a node meets one of the other four nodes, the weight of the found node is improved in 1 unit at the weight table of the node which has found it. After that, all the nodes in the table are normalized so that the sum becomes 1 again. Table1 illustrates this procedure.Table 1
Examples of meeting frequency.
1
2
3
4
0.25
0.25
0.25
0.25
1
2
3
4
0.25
/
2
0.25
/
2
0.25
+
1
/
2
0.25
/
2
1
2
3
4
0.125
0.125
0.625
0.125During the meetings, weight tables are exchanged between the nodes, and this allows the calculus of the packet delivery probability. For the calculus, a research is made from the origin node, considering all the possible paths to destination since the cost of a path between a pair of nodesI and J equals 1−weightiJ, being weightiJ the weight J has on the table of I. After the cost calculation of all the paths, the smallest calculated value is adopted to attribute the value of the packet delivery probability. Figure 3 illustrates the path cost calculus among the nodes A to D in the MaxProp protocol.Figure 3
Calculus of path costs among the nodesA to D.Besides the structure of packet priority, the MaxProp protocol owns some other interesting mechanisms, such as packets with few hops until the destination have priority; confirmation of messages received by the destination node; a node does not receive the same packet more than once; and a node does not receive packets which have already been stored.


### 3.4. Greedy Perimeter Stateless Routing (GPSR) Protocol

The Greedy Perimeter Stateless Routing (GPSR) protocol [24] makes use of the concept of choosing the neighbor node closest to the destination to forward packets. In GPSR, all the nodes in the network know their geographic position, as well as, the position of their neighbors and that of the destination node. During the route discovering phase, private messages are sent to the nodes located at one hop from the transmitter. These messages, also known as beacons, are responsible for informing the identification of the node and its location.Through the beacons, all the nodes in the network get information about the location of neighbor nodes a one hop from them. Then, in case a node does not receive the beacons from a neighbor during a period of time, it assumes the neighbor is out of the signal reach and it excludes it from its neighbor’s list. The data forwarding by the GPSR protocol can be made by two ways:greedy forwarding and perimeter forwarding.In the greedy forwarding, the packet is sent through multiple hops until it arrives at the node closest to the destination node. However, if the destination is not in the transmission radius of the nearest neighbor, the perimeter forwarding is activated, which has the objective of avoid regions where there are not closer nodes to the destination than the current node. In these situations, the packet must move away from the destination until it finds a new greedy route. Figure4 illustrates an example of the proceeding of the GPSR protocol.Figure 4
Proceeding of the GPSR protocol.As illustrated in Figure4, node A wishes to send data to node L. Node A transmits the packets to node B, which is the closest neighbor to L. The same occurs with nodes B, D, and F. When receiving the packet, node F verifies that none of its neighbors (those in the gray circle) is closer to L than itself; however, node L is out of the reach of node F’s radio signals. This way, node F activates the perimeter mode and sends the data to G. The same way, G uses the perimeter mode to send data to H. Node H finds a node closer to L than node F, and then the packet returns to be transmitted by greedy strategy until it arrives in L.The forwarding in the perimeter mode creates a planar graph to forward the packets to the destination node, using the nodes located in the region of the node which activates the perimeter mode. Once the graph is set, a rule known as the right-hand rule determines which is the next hop of the communication. This rule defines that when a packet arrives to a nodeX coming from Y, the next edge will be the following in the counterclockwise of X in relation to the edge (X, Y).Due to the existence of buildings and other factors which can interrupt the propagation of the radio signals in urban scenarios, the perimeter mode is frequently used; to avoid loops, the planar connectivity graph will avoid crossing among edges. These factors can work on sending the messages to the neighbors which are more distant to the destination node. This way, more nodes will route the messages, causing a larger delay while delivering the messages, as well as a rise in the number of hops to reach the destination.


## 3.1. Ad Hoc On-Demand Distance Vector (AODV)

The Ad hoc On-demand Distance Vector (AODV) [13] was projected to be used in ad hoc networks containing dozens to thousands of mobile nodes. The main objective of the protocol is to adapt quickly and dynamically to the variation of the conditions of network links, finding routes in order to avoid the waste of bandwidth and to minimize memory, and processing usage in nodes which act as routers.The AODV acts on demand, which means it searches for routes only when they are necessary using a route discovery mechanism. Each node owns, in its routing table, only information about the next hop for which the message must be sent to get to the destination. Then, when the nodek wants to send a message to node j, it verifies on its routing table the next hop to get to the node j and sends the message to the node which is the next hop. If node j is not the destination, it repeats the process until the message arrives to the destination. When the origin does not have a next hop to the desired destination, it executes the route discovery process.


### 3.1.1. Route Discovering

The AODV builds routes using route request (RREQ) and route reply (RREP) messages. When an origin node needs to send a data message to a node whose route is still unknown, an RREQ is sent in broadcast through the network. Nodes that receive this message update their routing tables, adding an input to inform how to get to the origin, and they are assumed to send a message to the node which has just sent the RREQ. The nodes keep control of the origin of the RREQs and the identification of the broadcast. If they receive a message that has already been processed, the message is discarded. A node receiving a RREQ can send a RREP to the origin if it is the destination or if it knows a route to the destination. This RREP is sent in unicast through the reverse path created by the RREQ. As the RREP message must be sent back to the origin, the nodes update their routing tables adding an input to inform the RREQ’s original destination (which now is the RREP’s origin) sending a message to the node which has just sent the RREP. When the origin node receives the RREP, it can then transmit the data packet to the destination, simply by forwarding the message to the node which has delivered the RREP.


### 3.1.2. Route Maintenance

The displacement of a node can cause a link failure. In this situation, the node which has detected the fault sends a route error (RERR) message to the origin, warning about the link failure. If the origin still wishes to use the route, the route discovering process is restarted.


## 3.1.1. Route Discovering

The AODV builds routes using route request (RREQ) and route reply (RREP) messages. When an origin node needs to send a data message to a node whose route is still unknown, an RREQ is sent in broadcast through the network. Nodes that receive this message update their routing tables, adding an input to inform how to get to the origin, and they are assumed to send a message to the node which has just sent the RREQ. The nodes keep control of the origin of the RREQs and the identification of the broadcast. If they receive a message that has already been processed, the message is discarded. A node receiving a RREQ can send a RREP to the origin if it is the destination or if it knows a route to the destination. This RREP is sent in unicast through the reverse path created by the RREQ. As the RREP message must be sent back to the origin, the nodes update their routing tables adding an input to inform the RREQ’s original destination (which now is the RREP’s origin) sending a message to the node which has just sent the RREP. When the origin node receives the RREP, it can then transmit the data packet to the destination, simply by forwarding the message to the node which has delivered the RREP.


## 3.1.2. Route Maintenance

The displacement of a node can cause a link failure. In this situation, the node which has detected the fault sends a route error (RERR) message to the origin, warning about the link failure. If the origin still wishes to use the route, the route discovering process is restarted.


## 3.2. Urban Multihop Broadcast (UMB) Protocol

Communications among vehicles can use multihop transmissions as a way to send information to places beyond the reach of the origin nodes. However, multihop transmissions can be challenging in urban areas since those areas have several obstacles which difficult the transmission.The Urban Multihop Broadcast (UMB) protocol [21] seeks to overcome problems related to packet collisions, interferences, and hidden nodes while sending messages through multihop in urban areas. This way, UMB uses a process based on the request-to-send (RTS) and clear-to-send (CTS) approaches [23].The UMB protocol works in two distinct ways, in thedirectional diffusion mode and in the intersection mode. In the directional diffusion, the origin node chooses the farthest node in relation to its position to recognize the messages and continue the diffusion. Nevertheless, this operation is made without previous knowledge about the network topology. Hence, the farthest node is selected without previous knowledge of its unique identifier (UID) on the network, or its neighbors’ position. In the intersection mode, the UMB admits installing repeaters on the intersections of roads to conduct the diffusion, and these repeaters must possess a straight view line to all parts in the road. When an intersection is discovered on the way of the packet transmission, new diffusions must be initiated in all directions in this intersection since repeaters have the best view line with the other road segments, mainly when there are high buildings around. In summary, the most important objectives of the UMB are to avoid collisions due to the hidden nodes; make efficient use of the channel; and make the communication through diffusion trustworthy, spreading the messages in all directions in intersections.


## 3.3. MaxProb Protocol (MaxProb)

In MaxProb protocol [18], the knowledge acquired during the connection of the network nodes is used to optimize the message forwarding. All the nodes belonging to the network have a vector of ordered packets, in which the ordering works according to the delivery likelihood of each packet.Besides the vector of ordered packets, the nodes also have a table withweights of all destination nodes. Each weight represents the frequency of a connection and initially it has the same value for all the destinations, but as the meetings among the nodes happen, this weight can be improved.As an example, consider a network with 5 nodes. In this network, all the nodes keep a list with the weights of all the other nodes, being each weight initially equal to 0.25 (the sum of all the weights is equal to 1). At the moment a node meets one of the other four nodes, the weight of the found node is improved in 1 unit at the weight table of the node which has found it. After that, all the nodes in the table are normalized so that the sum becomes 1 again. Table1 illustrates this procedure.Table 1
Examples of meeting frequency.
1
2
3
4
0.25
0.25
0.25
0.25
1
2
3
4
0.25
/
2
0.25
/
2
0.25
+
1
/
2
0.25
/
2
1
2
3
4
0.125
0.125
0.625
0.125During the meetings, weight tables are exchanged between the nodes, and this allows the calculus of the packet delivery probability. For the calculus, a research is made from the origin node, considering all the possible paths to destination since the cost of a path between a pair of nodesI and J equals 1−weightiJ, being weightiJ the weight J has on the table of I. After the cost calculation of all the paths, the smallest calculated value is adopted to attribute the value of the packet delivery probability. Figure 3 illustrates the path cost calculus among the nodes A to D in the MaxProp protocol.Figure 3
Calculus of path costs among the nodesA to D.Besides the structure of packet priority, the MaxProp protocol owns some other interesting mechanisms, such as packets with few hops until the destination have priority; confirmation of messages received by the destination node; a node does not receive the same packet more than once; and a node does not receive packets which have already been stored.


## 3.4. Greedy Perimeter Stateless Routing (GPSR) Protocol

The Greedy Perimeter Stateless Routing (GPSR) protocol [24] makes use of the concept of choosing the neighbor node closest to the destination to forward packets. In GPSR, all the nodes in the network know their geographic position, as well as, the position of their neighbors and that of the destination node. During the route discovering phase, private messages are sent to the nodes located at one hop from the transmitter. These messages, also known as beacons, are responsible for informing the identification of the node and its location.Through the beacons, all the nodes in the network get information about the location of neighbor nodes a one hop from them. Then, in case a node does not receive the beacons from a neighbor during a period of time, it assumes the neighbor is out of the signal reach and it excludes it from its neighbor’s list. The data forwarding by the GPSR protocol can be made by two ways:greedy forwarding and perimeter forwarding.In the greedy forwarding, the packet is sent through multiple hops until it arrives at the node closest to the destination node. However, if the destination is not in the transmission radius of the nearest neighbor, the perimeter forwarding is activated, which has the objective of avoid regions where there are not closer nodes to the destination than the current node. In these situations, the packet must move away from the destination until it finds a new greedy route. Figure4 illustrates an example of the proceeding of the GPSR protocol.Figure 4
Proceeding of the GPSR protocol.As illustrated in Figure4, node A wishes to send data to node L. Node A transmits the packets to node B, which is the closest neighbor to L. The same occurs with nodes B, D, and F. When receiving the packet, node F verifies that none of its neighbors (those in the gray circle) is closer to L than itself; however, node L is out of the reach of node F’s radio signals. This way, node F activates the perimeter mode and sends the data to G. The same way, G uses the perimeter mode to send data to H. Node H finds a node closer to L than node F, and then the packet returns to be transmitted by greedy strategy until it arrives in L.The forwarding in the perimeter mode creates a planar graph to forward the packets to the destination node, using the nodes located in the region of the node which activates the perimeter mode. Once the graph is set, a rule known as the right-hand rule determines which is the next hop of the communication. This rule defines that when a packet arrives to a nodeX coming from Y, the next edge will be the following in the counterclockwise of X in relation to the edge (X, Y).Due to the existence of buildings and other factors which can interrupt the propagation of the radio signals in urban scenarios, the perimeter mode is frequently used; to avoid loops, the planar connectivity graph will avoid crossing among edges. These factors can work on sending the messages to the neighbors which are more distant to the destination node. This way, more nodes will route the messages, causing a larger delay while delivering the messages, as well as a rise in the number of hops to reach the destination.


## 4. Tendencies to Routing Protocols: Bioinspired Protocols

The use of bioinspired routing protocols to optimize route discovery and route maintenance tasks is a tendency emphasized nowadays. These routing protocols get inspiration from the behavior of entities in the nature, and they are meant to work in a distributed mode, using mobile agents to find routes with specific features [25–27].The Ant-Colony Optimization (ACO) approach is used in the resolution of optimization problems using schemes bioinspired by ant colonies, and it can be applied when designing a routing protocol [26]. These protocols get inspired in the behavior of the ants to find routes with specific features, as an example, the shortest route between origin and destination. Routing protocols based on ACO explore the optimization mechanisms from the algorithm to build and maintain routes.Moreover, the ACO technique can be adapted to work with other aims depending on the problem to be taken care of, for example, using mobile agents to find the route with the highest connectivity degree instead of the shortest route. From the computational point of view, the main advantages in using algorithms based on ACO are low computational costs, reduced execution times, search in reduced space of executions, and dispensable global information about the system.Among the bioinspired protocols, ARA, ANTNET, and POSANT are relevant to researches involving routing in VANETs.


### 4.1. Ant-Colony-Based Routing Algorithm (ARA)

The Ant-Colony-Based Routing Algorithm (ARA) is a reactive routing protocol based on ACO for mobile networks [26]. This protocol has two well-defined phases: route discovery and route maintenance. In the discovery phase, the origin sends an ant in the direction to the destination and the same is retransmitted to each intermediate node until reaching it. After that, the ant is sent back to the origin through the same way, only on the contrary way.When returning, the ant improves a value (pheromone) correspondent to the destination in each intermediate node until it gets to the origin. When the origin receives this ant, the route maintenance starts and the data packets are transmitted. With the path between the origin and the destination already established, based on the value of the pheromone, the subsequent data packets will perform the route maintenance, adjusting its value.


### 4.2. Ant-Based Routing in Networks (ANTNET) Protocol

The Ant-based Routing in Networks (ANTNET) protocol is an example of routing protocol which uses the ACO [25]. The main focus of this protocol is to find the shortest path among the nodes of origin and destination, as well as keeping the routing tables always updated.The ANTNET applies a proactive routing approach, which is based on regular releases of mobile agents (ants) toward nodes chosen randomly. According to the ACO algorithm, ants search randomly for the destination node using a stochastic policy. After locating the destination, the ants go back to the anthill following the same path used to find the destination. This way, the routing tables in the path are updated with the most recent routing information about the location of the destination.To avoid saturation in the network, the ANTNET creates new agents based on a probabilityPd considering the traffic conditions. The routing tables are represented by Tk, which defines the routing probability adopted by the k node. For each destination d and for each neighbor n, Tk keeps a probabilistic value Pnd, which expresses the convenience of choosing n as the next hop in the direction to the destination d.


### 4.3. Position-Based Ant-Colony Routing Algorithm (POSANT)

The Position-Based Ant-Colony Routing Algorithm (POSANT) is also based on ACO, and it can find optimal or almost optimal routes [27]. This routing protocol gets inspiration from ants’ behavior and in the nodes’ position to find the best route between origin and destination nodes.In this protocol, each node is assumed to know its position, the position of its neighbors, and the position of the destination. The POSANT is a reactive protocol, so one path is only established when there are data packets to be sent from an origin to a destination node. Data sending will only be initiated after that the path between the origin and the destination nodes is confirmed. Before that, the ants are entrusted to find this path, being released from the origin node in the direction to the destination and returning in the opposite way to the found path.Aiming to minimize the time POSANT needs to find a route, keeping the number of ants the lowest possible, information about the position of the nodes is applied as a heuristic value. The use of the information of the location as a heuristic parameter results in a significant decrease in the time needed to establish routes, besides a reduction in the number of control messages and a benefit on packet delivery rate.


## 4.1. Ant-Colony-Based Routing Algorithm (ARA)

The Ant-Colony-Based Routing Algorithm (ARA) is a reactive routing protocol based on ACO for mobile networks [26]. This protocol has two well-defined phases: route discovery and route maintenance. In the discovery phase, the origin sends an ant in the direction to the destination and the same is retransmitted to each intermediate node until reaching it. After that, the ant is sent back to the origin through the same way, only on the contrary way.When returning, the ant improves a value (pheromone) correspondent to the destination in each intermediate node until it gets to the origin. When the origin receives this ant, the route maintenance starts and the data packets are transmitted. With the path between the origin and the destination already established, based on the value of the pheromone, the subsequent data packets will perform the route maintenance, adjusting its value.


## 4.2. Ant-Based Routing in Networks (ANTNET) Protocol

The Ant-based Routing in Networks (ANTNET) protocol is an example of routing protocol which uses the ACO [25]. The main focus of this protocol is to find the shortest path among the nodes of origin and destination, as well as keeping the routing tables always updated.The ANTNET applies a proactive routing approach, which is based on regular releases of mobile agents (ants) toward nodes chosen randomly. According to the ACO algorithm, ants search randomly for the destination node using a stochastic policy. After locating the destination, the ants go back to the anthill following the same path used to find the destination. This way, the routing tables in the path are updated with the most recent routing information about the location of the destination.To avoid saturation in the network, the ANTNET creates new agents based on a probabilityPd considering the traffic conditions. The routing tables are represented by Tk, which defines the routing probability adopted by the k node. For each destination d and for each neighbor n, Tk keeps a probabilistic value Pnd, which expresses the convenience of choosing n as the next hop in the direction to the destination d.


## 4.3. Position-Based Ant-Colony Routing Algorithm (POSANT)

The Position-Based Ant-Colony Routing Algorithm (POSANT) is also based on ACO, and it can find optimal or almost optimal routes [27]. This routing protocol gets inspiration from ants’ behavior and in the nodes’ position to find the best route between origin and destination nodes.In this protocol, each node is assumed to know its position, the position of its neighbors, and the position of the destination. The POSANT is a reactive protocol, so one path is only established when there are data packets to be sent from an origin to a destination node. Data sending will only be initiated after that the path between the origin and the destination nodes is confirmed. Before that, the ants are entrusted to find this path, being released from the origin node in the direction to the destination and returning in the opposite way to the found path.Aiming to minimize the time POSANT needs to find a route, keeping the number of ants the lowest possible, information about the position of the nodes is applied as a heuristic value. The use of the information of the location as a heuristic parameter results in a significant decrease in the time needed to establish routes, besides a reduction in the number of control messages and a benefit on packet delivery rate.


## 5. Tendencies to Routing Protocols: Bus-Based Protocols

In urban environments, there are basically four kinds of transport: private vehicles, heavy transport vehicles, urban trains, and urban transport vehicles (buses). Among these, the urban transport vehicles present a different traffic behavior in relation to the other ones. In particular, in big cities, buses belonging to the express lines travel through exclusive roads, according to a relatively regular schedule, in a path with few obstacles. These characteristics suggest that a system that makes use of these buses to create a communication infrastructure can perform better when compared to a system that does not distinguish between vehicles [28].The work in [28] proposes the construction of a mobile ad hoc data transport network (MOB-NET), a bus-based communication infrastructure whose objective is to provide infrastructure and provide excellent connectivity, guaranteeing end-to-end message delivery in a given region. In order to explore the MOB-NET, the authors proposed the P-AODV and P-AOMDV routing protocols. Therefore, the P-AODV and P-AOMDV are relevant to researches involving bus-based routing protocols in VANETs.


### 5.1. P-AODV

The Priority Ad Hoc On-Demand Distance Vector (P-AODV) [29] is a modification of the AODV protocol. It was developed to work together with MOB-NET at the moment the nodes are discovering the routes, having the ability to build the routes prioritizing the nodes (buses) belonging to MOB-NET. The general AODV operation was presented in Section 3.1. The main modification was carried out in the route discovery process of AODV.


#### 5.1.1. P-AODV Route Discovery Process

The source initiates a route discovery process sending a RREQ message in broadcast. A node can receive multiple copies of RREQ. Usually, only the first RREQ is used to form reverse routes between the node that received the RREQ and the source, and the duplicate copies that arrive later are simply discarded. In P-AODV, all duplicate copies are examined, and some of them can be used to form alternative paths that prioritize the MOB-NET.When an intermediate node receives an RREQ message, it checks if the RREQ is duplicated. If the message is not duplicated, the node that received the RREQ updates its routing table, having the node that sent the RREQ as the next hop in reverse path and forwards the message over the network.If the RREQ is duplicated, the intermediate node checks if the RREQ source is a node belonging to MOB-NET. If the RREQ source is a node belonging to MOB-NET, the intermediate node checks if the prerequisites are satisfied and updates its routing table (excludes the old route and creates the new route), with the node that originated the RREQ (node belonging to MOB-NET) as the next hop in the reverse direction. The prerequisites for updating the route table are preserve loop-free paths, being the current route, and have fewer or equal intermediate nodes.A more efficient protocol corresponds to P-AOMDV which is analyzed in depth below.


### 5.2. P-AOMDV

The Priority Ad Hoc On-Demand Multipath Distance Vector (P-AOMDV) [30] is a modification of the AOMDV protocol. In this protocol, the data messages travel through routes that try to have the largest possible number of buses belonging to the MOB-NET, where there is greater connectivity and reliability. The modification was made mainly in the route discovery process of the AOMDV.In the AOMDV, the source begins a discovering route process by sending a route request (RREQ) message in broadcast. From the moment the RREQ is sent to the whole network, a node may receive many copies of the same RREQ. In single-path protocols, only the first RREQ is used in order to form inverse routes between the node that had received the RREQ and the source, and the duplicated copies that arrive later are simply discarded. Yet, some of these duplicated copies can be used to form alternative inverse routes. Hence, all the duplicated copies are examined by the AOMDV; those copies, which preserve loop-free and link-disjoint paths between the source and the destination, may be used to form alternative routes. When an intermediate node receives a copy of a RREQ message, it verifies on its routing table if there is one or more valid routes for the destination required on the RREQ message. In case there is, the node creates a route reply message (RREP) and sends it back to the source on the inverse route. Otherwise, the RREQ message is reforwarded by the intermediate node in the network. When the destination node receives copies of the RREQ, it builds inverse routes as the intermediate nodes. The destination node creates a RREP in response to each arriving RREQ, through a loop-free route with the source [12].


#### 5.2.1. Route Discovery Process

The route discovery process of P-AOMDV is similar to that of AOMDV; when a node needs to send a message to another node to which it yet does not know the route, a RREQ message is sent in broadcast and RREP messages are sent in response by the destination or by an intermediate node which knows the route to the source. The RREP messages have a new field, namedcount_bus, whose function is to keep the quantity of buses belonging to MOB-NET that each route has. So, when the RREP is covering the destination route to the source through the reverse route, it will improve the count_bus variable in one unit every time it was received by a bus belonging to MOB-NET. It is assumed that all nodes in the network know how to identify the buses belonging to the MOB-NET, through a unique identification (ID).The structure of the proposed RREP message for P-AOMDV can be seen in Table2.Table 2
Structure of the proposed RREP message for P-AOMDV.
scr
dst
dst_seqno
hop_count
liftime
count_busIn the route discovery process, RREP messages are used to update the routing tables of the nodes with information about the routing, as an example, to update thenext_hop field with the address of the next node in direction to the destination. On P-AOMDV, one new field was included on the routing table, named num_bus, whose function is to store the number of nodes belonging to the MOB-NET. With this, when the RREP travels from a destination to the source, all nodes in the path will update the num_bus variable in their routing tables to the value of count_bus.The structure of AOMDV and P-AOMDV routing tables is illustrated in Table3.Table 3
Structure of the AOMDV and the P-AOMDV routing tables.
AOMDV
P-AOMDV
Destination address
Destination address
Sequence number
Sequence number
Advertised-hop count
Advertised-hop count
RouteList [(next_hop1, hop_count1), (next_hop2, hop_count2), …]
RouteList [(next_hop1, hop_count1,num_bus1), (next_hop2, hop_count2, num_bus2), …]
Expiration time out
Expiration time outWith this new routing table, the nodes running the P-AOMDV protocol are able to arrange the routes in their tables following a crescent order, having as parameter for the arrangement of the number of nodes belonging to MOB-NET. If two routes have the same number of nodes, the one which presents fewer hops to the destination will have priority. Table4 gives an example. As it can be observed, the routes are classified primarily by the number of nodes belonging to the MOB-NET. In the case of identical values, the routes are arranged by the number of hops to the destination.Table 4
Data from the route table of a node running P-AOMDV.
Destination
Sequence number
Advertised hop count
Next hop
Count bus
Hop count
100
2
1683
3
5
8
40
5
9
51
4
7
12
3
6
33
2
7The change on the RREP message header may lead to a traffic overload in the network, as well as a change on the routing table may create the need of more storage space. However, VANETs own less hardware restrictions in relation to the other ad hoc networks, for example, MANETs, because they are implemented in vehicles, which do not have energy restrictions, withstanding a more powerful hardware. It is worth pointing out that no new packet type was created, and for that reason, any overload is small, being balanced with the improvement of several performance metrics.


## 5.1. P-AODV

The Priority Ad Hoc On-Demand Distance Vector (P-AODV) [29] is a modification of the AODV protocol. It was developed to work together with MOB-NET at the moment the nodes are discovering the routes, having the ability to build the routes prioritizing the nodes (buses) belonging to MOB-NET. The general AODV operation was presented in Section 3.1. The main modification was carried out in the route discovery process of AODV.


### 5.1.1. P-AODV Route Discovery Process

The source initiates a route discovery process sending a RREQ message in broadcast. A node can receive multiple copies of RREQ. Usually, only the first RREQ is used to form reverse routes between the node that received the RREQ and the source, and the duplicate copies that arrive later are simply discarded. In P-AODV, all duplicate copies are examined, and some of them can be used to form alternative paths that prioritize the MOB-NET.When an intermediate node receives an RREQ message, it checks if the RREQ is duplicated. If the message is not duplicated, the node that received the RREQ updates its routing table, having the node that sent the RREQ as the next hop in reverse path and forwards the message over the network.If the RREQ is duplicated, the intermediate node checks if the RREQ source is a node belonging to MOB-NET. If the RREQ source is a node belonging to MOB-NET, the intermediate node checks if the prerequisites are satisfied and updates its routing table (excludes the old route and creates the new route), with the node that originated the RREQ (node belonging to MOB-NET) as the next hop in the reverse direction. The prerequisites for updating the route table are preserve loop-free paths, being the current route, and have fewer or equal intermediate nodes.A more efficient protocol corresponds to P-AOMDV which is analyzed in depth below.


## 5.1.1. P-AODV Route Discovery Process

The source initiates a route discovery process sending a RREQ message in broadcast. A node can receive multiple copies of RREQ. Usually, only the first RREQ is used to form reverse routes between the node that received the RREQ and the source, and the duplicate copies that arrive later are simply discarded. In P-AODV, all duplicate copies are examined, and some of them can be used to form alternative paths that prioritize the MOB-NET.When an intermediate node receives an RREQ message, it checks if the RREQ is duplicated. If the message is not duplicated, the node that received the RREQ updates its routing table, having the node that sent the RREQ as the next hop in reverse path and forwards the message over the network.If the RREQ is duplicated, the intermediate node checks if the RREQ source is a node belonging to MOB-NET. If the RREQ source is a node belonging to MOB-NET, the intermediate node checks if the prerequisites are satisfied and updates its routing table (excludes the old route and creates the new route), with the node that originated the RREQ (node belonging to MOB-NET) as the next hop in the reverse direction. The prerequisites for updating the route table are preserve loop-free paths, being the current route, and have fewer or equal intermediate nodes.A more efficient protocol corresponds to P-AOMDV which is analyzed in depth below.


## 5.2. P-AOMDV

The Priority Ad Hoc On-Demand Multipath Distance Vector (P-AOMDV) [30] is a modification of the AOMDV protocol. In this protocol, the data messages travel through routes that try to have the largest possible number of buses belonging to the MOB-NET, where there is greater connectivity and reliability. The modification was made mainly in the route discovery process of the AOMDV.In the AOMDV, the source begins a discovering route process by sending a route request (RREQ) message in broadcast. From the moment the RREQ is sent to the whole network, a node may receive many copies of the same RREQ. In single-path protocols, only the first RREQ is used in order to form inverse routes between the node that had received the RREQ and the source, and the duplicated copies that arrive later are simply discarded. Yet, some of these duplicated copies can be used to form alternative inverse routes. Hence, all the duplicated copies are examined by the AOMDV; those copies, which preserve loop-free and link-disjoint paths between the source and the destination, may be used to form alternative routes. When an intermediate node receives a copy of a RREQ message, it verifies on its routing table if there is one or more valid routes for the destination required on the RREQ message. In case there is, the node creates a route reply message (RREP) and sends it back to the source on the inverse route. Otherwise, the RREQ message is reforwarded by the intermediate node in the network. When the destination node receives copies of the RREQ, it builds inverse routes as the intermediate nodes. The destination node creates a RREP in response to each arriving RREQ, through a loop-free route with the source [12].


### 5.2.1. Route Discovery Process

The route discovery process of P-AOMDV is similar to that of AOMDV; when a node needs to send a message to another node to which it yet does not know the route, a RREQ message is sent in broadcast and RREP messages are sent in response by the destination or by an intermediate node which knows the route to the source. The RREP messages have a new field, namedcount_bus, whose function is to keep the quantity of buses belonging to MOB-NET that each route has. So, when the RREP is covering the destination route to the source through the reverse route, it will improve the count_bus variable in one unit every time it was received by a bus belonging to MOB-NET. It is assumed that all nodes in the network know how to identify the buses belonging to the MOB-NET, through a unique identification (ID).The structure of the proposed RREP message for P-AOMDV can be seen in Table2.Table 2
Structure of the proposed RREP message for P-AOMDV.
scr
dst
dst_seqno
hop_count
liftime
count_busIn the route discovery process, RREP messages are used to update the routing tables of the nodes with information about the routing, as an example, to update thenext_hop field with the address of the next node in direction to the destination. On P-AOMDV, one new field was included on the routing table, named num_bus, whose function is to store the number of nodes belonging to the MOB-NET. With this, when the RREP travels from a destination to the source, all nodes in the path will update the num_bus variable in their routing tables to the value of count_bus.The structure of AOMDV and P-AOMDV routing tables is illustrated in Table3.Table 3
Structure of the AOMDV and the P-AOMDV routing tables.
AOMDV
P-AOMDV
Destination address
Destination address
Sequence number
Sequence number
Advertised-hop count
Advertised-hop count
RouteList [(next_hop1, hop_count1), (next_hop2, hop_count2), …]
RouteList [(next_hop1, hop_count1,num_bus1), (next_hop2, hop_count2, num_bus2), …]
Expiration time out
Expiration time outWith this new routing table, the nodes running the P-AOMDV protocol are able to arrange the routes in their tables following a crescent order, having as parameter for the arrangement of the number of nodes belonging to MOB-NET. If two routes have the same number of nodes, the one which presents fewer hops to the destination will have priority. Table4 gives an example. As it can be observed, the routes are classified primarily by the number of nodes belonging to the MOB-NET. In the case of identical values, the routes are arranged by the number of hops to the destination.Table 4
Data from the route table of a node running P-AOMDV.
Destination
Sequence number
Advertised hop count
Next hop
Count bus
Hop count
100
2
1683
3
5
8
40
5
9
51
4
7
12
3
6
33
2
7The change on the RREP message header may lead to a traffic overload in the network, as well as a change on the routing table may create the need of more storage space. However, VANETs own less hardware restrictions in relation to the other ad hoc networks, for example, MANETs, because they are implemented in vehicles, which do not have energy restrictions, withstanding a more powerful hardware. It is worth pointing out that no new packet type was created, and for that reason, any overload is small, being balanced with the improvement of several performance metrics.


## 5.2.1. Route Discovery Process

The route discovery process of P-AOMDV is similar to that of AOMDV; when a node needs to send a message to another node to which it yet does not know the route, a RREQ message is sent in broadcast and RREP messages are sent in response by the destination or by an intermediate node which knows the route to the source. The RREP messages have a new field, namedcount_bus, whose function is to keep the quantity of buses belonging to MOB-NET that each route has. So, when the RREP is covering the destination route to the source through the reverse route, it will improve the count_bus variable in one unit every time it was received by a bus belonging to MOB-NET. It is assumed that all nodes in the network know how to identify the buses belonging to the MOB-NET, through a unique identification (ID).The structure of the proposed RREP message for P-AOMDV can be seen in Table2.Table 2
Structure of the proposed RREP message for P-AOMDV.
scr
dst
dst_seqno
hop_count
liftime
count_busIn the route discovery process, RREP messages are used to update the routing tables of the nodes with information about the routing, as an example, to update thenext_hop field with the address of the next node in direction to the destination. On P-AOMDV, one new field was included on the routing table, named num_bus, whose function is to store the number of nodes belonging to the MOB-NET. With this, when the RREP travels from a destination to the source, all nodes in the path will update the num_bus variable in their routing tables to the value of count_bus.The structure of AOMDV and P-AOMDV routing tables is illustrated in Table3.Table 3
Structure of the AOMDV and the P-AOMDV routing tables.
AOMDV
P-AOMDV
Destination address
Destination address
Sequence number
Sequence number
Advertised-hop count
Advertised-hop count
RouteList [(next_hop1, hop_count1), (next_hop2, hop_count2), …]
RouteList [(next_hop1, hop_count1,num_bus1), (next_hop2, hop_count2, num_bus2), …]
Expiration time out
Expiration time outWith this new routing table, the nodes running the P-AOMDV protocol are able to arrange the routes in their tables following a crescent order, having as parameter for the arrangement of the number of nodes belonging to MOB-NET. If two routes have the same number of nodes, the one which presents fewer hops to the destination will have priority. Table4 gives an example. As it can be observed, the routes are classified primarily by the number of nodes belonging to the MOB-NET. In the case of identical values, the routes are arranged by the number of hops to the destination.Table 4
Data from the route table of a node running P-AOMDV.
Destination
Sequence number
Advertised hop count
Next hop
Count bus
Hop count
100
2
1683
3
5
8
40
5
9
51
4
7
12
3
6
33
2
7The change on the RREP message header may lead to a traffic overload in the network, as well as a change on the routing table may create the need of more storage space. However, VANETs own less hardware restrictions in relation to the other ad hoc networks, for example, MANETs, because they are implemented in vehicles, which do not have energy restrictions, withstanding a more powerful hardware. It is worth pointing out that no new packet type was created, and for that reason, any overload is small, being balanced with the improvement of several performance metrics.


## 6. Current Routing Protocols for VANETs

Recently new routing protocols for VANETs have been developed, and some of these protocols are described below.In [31], Dynamic Vehicle Ontology-Based Routing (DVOR) protocol was proposed. In this protocol, the shortest path routing that reduces the waiting time for vehicles at traffic jams is found. It uses RSU-based scheme and activity file for finding the optimal path. The DVOR mainly focused on trip duration time, so automatically waiting time is decreased. The DVOR is compared with two proactive routing protocols: OLSR and DSDV. The proposed protocol is evaluated by three parameters: packet delivery ratio, mean delay (MD), and trip duration.In [32], Beaconless Packet Forwarding Protocol (B-PFP) was proposed. In this work, the authors use a beaconless packet forwarding method for packet transmission. At the time of packet transmission, vehicle direction and link quality are considered. The protocol has two modes of data forwarding: one is at the intersection and the other is between the intersections. The B-PFP is compared with four protocols (CAIR, IGRP, BRAVE, and LIATHON) and evaluated by the packet delivery ratio. The simulation results show that Beaconless Packet Forwarding Protocol outperforms in terms of thepacket delivery ratio.In [33], a Traffic Light Aware Routing (ETAR) protocol was proposed for VANET. This protocol finds the most stable route for exchanging data packets based on traffic lights and traffic density of vehicles. With hello packets, it determines the density and connectivity of the vehicles. To deliver the data packets to their destinations, three steps are used; they are path selection, greedy forwarding, and carry-and-forward method. The proposed protocol is compared with topology-based protocol AODV and position-based protocol GyTAR and evaluated by packet delivery ratio and end-to-end delay. A simulation result shows that ETAR outperforms in terms of delivery ratio and end-to-end delay.In [34], the Road Perception-Based Geographical Routing (RPGR) protocol was proposed for VANET. It considers midrange node, distance, and direction as metrics to select the next hop node in the network. To overcome the disconnectivity problem, it uses carry-and-forward mechanism. The proposed RPGR has been analyzed in simulation with three existing routing protocols GeoSVR, SDR, and GMGR. The simulation results show that RPGR outperforms all the three existing protocols in terms of path length and packet size.In [35], a Routing Table Learning and Maintenance (RTLM) protocol was proposed for junction-based V2V communication in VANET. This protocol is mainly focused on effective routing table learning and maintenance. It avoids unnecessary packet dropping. The RTLM provides better stable route and lower transmission cost. The simulation results show that RTLM has a low average delay time and packet drop ratio.Although the presented protocols are current, we believe that application of bioinspired and bus-based techniques to routing problem solutions are a tendency nowadays. The use of bioinspired routing protocols can optimize route discovery, these protocols work in a distributed mode using mobile agents to find routes with specific features. Similarly, the system that makes use of buses to create a communication infrastructure can perform better when compared to a system that does not distinguish between vehicles. The urban transport vehicles present a different traffic behavior in relation to the other ones’ vehicles.


## 7. Conclusion

This article has highlighted the main characteristics and tendencies concerning routing in vehicular ad hoc networks. A classification to routing protocols based on the type of architecture and mode of operation was presented. The topology of the network where the protocol will operate is defined as the type of architecture, which can be divided into ad hoc, infrastructured, and hybrid. The operation mode involves the type of routing, and it can be divided into topologic, geographic, opportunistic, and dissemination.The analysis of the literature showed that the use of bioinspired ideas in the designing of routing protocols is a tendency emphasized nowadays. Thus, routing protocols get inspiration from the behavior of entities in the nature, and they are meant to work in a distributed mode, using mobile agents to find routes with specific features. In a parallel line of research, the differentiated behavior of urban transport vehicles suggests that a system that makes use of buses to create a communication infrastructure can perform better when compared to a system that does not distinguish between vehicles. This way, new routing protocols have been proposed within this context.As shown in Table5, the routing protocols for the VANETs can operate in several ways, having their performance associated with each one of them. At the same time, the mobility model, the driving environment, and the vehicle density also affect the performance of the protocols. Therefore, obtaining a universal routing solution for all application scenarios or a standard evaluation criterion for routing protocols in VANETs is extremely difficult. In other words, for each application or need in VANETs, it is necessary to design specific routing protocols.Table 5
Routing protocols: comparative table.
Protocols
Architecture
Operation
Forwarding
GPS
AODV
Ad hoc
Based on topology
Unicast
No
AOMDV
Ad hoc
Based on topology
Unicast
No
UMB
Infrastructured
Dissemination
Broadcast
Yes
MaxProb
Ad hoc
Based on topology
Unicast
No
GPSR
Hybrid
Geographic
Unicast
Yes
ANTNET
Ad hoc
Based on topology
Unicast
No
ARA
Ad hoc
Based on topology
Unicast
No
POSANT
Hybrid
Geographic
Unicast
Yes
P-AODV
Ad hoc
Based on topology
Unicast
No
P-AOMDV
Ad hoc
Based on topology
Unicast
NoIn this context, the project of a routing protocol must take into consideration the problem to be solved, the location where the network will be established, and the monetary costs that are associated with each adopted routing model. In general, infrastructure and hybrid architectures with the geographic or dissemination mode with GPS equipment are the ones which need a larger infrastructure; hence, they have a higher associated monetary cost.



---

*Source: 1302123-2018-03-18.xml*