VANETs QoS-based routing protocols based on multi-constrained ability to support ITS infotainment services

Abstract

Vehicular ad hoc networks (VANETs) present an intriguing platform for several applications on e.g., intelligent transportation system (ITS) and infotainment applications aspire to be the main pattern of communication among vehicles while travelling. This can significantly impact on the amount of data exchanged by vehicles, increasing the contention on communication links and thus, degrading the quality of service of these applications. So, discrimination of data becomes imperative and forwarding critical information on suitable routes becomes decisive. Hence, a quality of service (QoS)-driven mechanism is needed to handle and assign network resources according to the stringent application data traffic demands. But, VANETs high node mobility and frequent link failure, stuck a big challenge in implementing an effective policy to meet and enforce these QoS requirements. A promising way to tackle this issue is to enforce QoS at the network layer, since it is the crucial point in VANETs’ communication. So, over the years, many QoS-aware routing protocols were specifically conceived for VANETs. In this paper, we present a comprehensive survey of QoS-aware routing protocols in VANETs’ literature. We examined the protocols based on their ability to support ITS infotainment services, their multi-constraint path problem (MCP), protocol’s functionality and weakness, objectives and design challenges. This way, we outline future directions for VANETs QoS-aware protocol research.

1 Introduction

Due to the wide varieties of services vehicular ad hoc network (VANETs) can provide and the proliferation of related applications, recently many research works focused on how to create a reliable, scalable, and effective environment for VANETs technology and services. VANET is a multi-hop ad hoc network that uses wireless technologies such as IEEE 802, General Packet Radio Services (GPRS), and Dedicated Short-Range Communications (DSRC) [1, 2], to communicate with neighboring vehicles with no or insufficient infrastructural support. As an ad hoc network, nodes in VANETs can act as sources, receivers and as transit routers that can relay traffic to other nodes in the network [3]. Research has shown that if deployed VANETs will be able to turn vehicles into productive equipment rather than just a means of transportation as seen by many, and will decrease road accidents and traffic [4,5,6].

VANETs present an intriguing platform for intelligent applications like, intelligent transportation system (ITS) and infotainment applications, such as traffic monitoring, route planning, emergency warning system for vehicles, dynamic traffic light, live video streaming, Internet Protocol Television (IPTV), file sharing, mobile office advertisements and even distributed computer games [7,8,9,10,11]. These conceivable ITS and infotainment applications aspire to be the main means of communication among vehicles. Implying increment on the volume of data exchanged by vehicles, and consequently increased contention on communication links, resulting in fluctuations of network quality parameters reflecting service on applications. Therefore, discriminating data becomes imperative, and forwarding critical information on suitable routes becomes decisive, as a result, a mechanism to handle and assign network resources to meet the application traffic demands is required.

ITS infotainment services are multimedia in nature, which necessitates a real-time and on time information delivery. Due to their real-time transmission necessity, ITS infotainment applications require high bandwidth and stringent performance [12]. However, VANETs resources are limited as there are sections of the network that cannot meet application traffic demands. Thus, a Quality of Service (QoS) mechanism is needed to handle and assign network resources to meet the application end-to-end performance requirements [13, 14]. But, VANETs high node mobility and frequent link failures [15,16,17], pose a big challenge in offering effective policies to meet these application QoS requirements. Nevertheless, since the network level has been identified as the bottleneck for VANETs, recently, researchers mainly focused on dealing with QoS at the network layer, these have led to the proposed of several QoS-aware routing protocols over the years. For effective communication between nodes in VANETs, QoS-aware routing protocols play essential roles on both the complexity of path computation and the QoS requirements that can be supported by such network [18,19,20]. Given the complexity of VANETs technology, to support a steady communication between vehicles, the network must decrease the time needed to converge after a topology change to avoid data loss [21, 22], and to offer the required QoS needed for traffic differentiation.

At present, there are two states of the art routing paradigm (i.e., topology-based and position-based), detailed explanations of these routing protocol classifications can be found in [23,24,25,26,27,28,29,30,31,32,33,34,35,36]. There exists a vast literature in which researchers in [37,38,39,40,41,42,43,44], believe that position-based routing protocols are better suited for operation in networks with high mobility such as VANETs. The grounds for their controversy is founded on the fact that position-based routing protocols have less processing complexity of route calculation, therefore, has low processing overhead [45, 46]. Having stated that, however, it is important to remark that position-based routing protocols do not have link-state features. Their operation entirely depends on geographic information, and they forward data greedily without considering the quality of the path [47]. While topology-based routing protocols are linked-state protocol, this property makes the protocol to be better suited for high dynamic network such as VANETs. Though, they have high processing overhead and storage complexity [48,49,50], but, since vehicles are not constrained to processing and storage space, such complexity can serve as trade-offs for better QoS. Position-based routing protocols maintain routing tables that can record link information towards destinations. Several records of such link-states can extend and enhanced choice of data forwarding for source nodes. By using these protocols, a source node can classify different data and relate them to different links according to their transmission needs. Further classification of topology-based protocols show two subclasses: proactive and reactive routing [51,52,53,54]. It is believed that reactive routing schemes are well-matched for achieving QoS objectives, because of their ability to choose alternative routes in advance, which reduces the time needed for convergence in case of link failure. These features make topology-based and in particular reactive routing protocols more suited for conveying real-time ITS infotainment services. Nonetheless, researchers in [55,56,57] investigated the characteristics of both topology based and position based routing protocols jointly to forge a more reliable hybrid routing protocol that has been demonstrated to be QoS-effective.

In this study, we surveyed the more manifest QoS-aware VANET routing protocols that were developed and proposed over the years. We compared different solutions, providing a taxonomy of the surveyed QoS-aware routing protocols based on their multi constraint (i.e., additive, concave and multiplicative) path choice metrics. Then, we outline open research issues in VANETs QoS at the network layer, paving the way to new research direction on QoS-aware routing. Although, several literatures had surveyed VANETs QoS-aware routing protocols, to the best of our knowledge, this is the first effort ever made to review the major VANETs QoS-aware routing protocols developed over the years. This is likewise the first time to the best of our knowledge that VANETs QoS-aware routing protocols are examined based on their functional ability to support the multi constrain demands of ITS multimedia traffic.

The remainder of the paper is organized as follows; in Sect. 2, we present a brief discussion on vehicular networks and their unique characteristic. In Sect. 3, we focus on QoS provisioning in Vehicular Ad Hoc Networks, including QoS metrics requirements of ITS applications, how these metrics are organized, their performance metric equivalent and the challenges involve in assuring QoS-aware routing in VANETs. Section 4 presents the survey of QoS-aware routing protocols published over the since the first work on the topic in 2006. Each individual protocol strength and weakness were also discussed. In Sect. 5, we evaluate the operation of the protocols through extensive simulation with real time video data transmission under a realistic VANETs topology. We assess their performance by selecting one protocol from each of the metric combinations (i.e., one each from additive, additive plus concave and additive plus multiplicative). We give a general remark on the surveyed protocol, where we scrutinized the protocols based on their ability to handle ITS real-time multimedia traffics, their multi-constraint optimization path problem (MCOP). The potency of each individual protocol as regards to their ability to support ITS multimedia traffics was also highlighted. We summarized each protocol functionality, weaknesses, strength and methods used in their validation in a table format. Section 6, is the conclusion and the discussion on open issues.

2 Characteristics of VANETs

A typical VANETs/ITS topology is illustrated in Fig. 1. There are two prominent communication strategies in VANETs; vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) [58,59,60,61,62,63,64]. In the V2V communications, vehicles interact through other vehicles in a multi-hop fashion. Communication in the V2I is possible through the support of roadside unit infrastructure [65, 66]. VANETs differ from other Mobile Ad Hoc Networks because of some of its specific characteristics, which poses a challenge in assuring an effective QoS for VANETs to meet its application service demands [67,68,69]:

Fig. 1

Illustration of VANETs/ITS scenario

• Rapid network topology changes vehicle moves with high and different speed, changing direction and position frequently. Therefore, VANETs topologies are very dynamic and communication links are not stable, which may lead to network partitions.

• Predictable mobility the trajectory of vehicles in VANETs is constrained by street topologies, traffic light and regulations. Thus, knowing the destination location, the future position of a vehicle can be predicted based on the road information, e.g., street map.

• Sufficient energy unlike mobile ad hoc networks, where power management is a big challenge due to the battery limited life span. In VANETs, this is not an issue, because in-vehicle communication devices are supported by the vehicle batteries and power system.

• Resource capabilities there is relative big space in vehicles, so various devices with significant processing, storage, communication and sensing capabilities can be installed, this make vehicles able to provide computing resource facilities.

• Large scale application scenarios: VANETS are always laid out in the highways or urban environments, which constitute large networks and include a high number of mobile nodes.

3 QoS-aware routing

Traditional routing protocols (i.e., non-QoS routing protocols) are projected to offer best effort, fair delivery of services, with no distinction to the kind of traffic being carried [70]. This type of routing protocols has offered satisfactory service to non-real-time application services such as; e-mailing, web browsing, file transfer, etc. However, real-time multimedia traffic requires certain performance assurances from the underlying network in terms of bandwidth, minimal delay, minimal packet loss, etc., which the traditional routing method cannot adequately support.

To meet the requirement of real-time ITS multimedia applications in VANETs, the network must take into account the QoS requirement of each application data type. As specified in RFC2386 [71], QoS is “a set of service requirement to be met by a network, while transporting a flow” [72]. QoS can be guarantee at different layers of the network stack (i.e., at the physical layer, MAC layer and network layer) [73]. Among them, the key technology for providing traffic flow QoS is at network layer, which is achievable through QoS-aware routing [74, 75]. The QoS-aware routing goal is in twofold: first, to identify an optimal path between source and destination and secondly, to exploit network resources in an efficient and optimized manner [76, 77]. Therefore, a QoS-aware routing protocol aims at discovering and maintaining routes from source to destination that meet QoS objective under a given resource constraints.

3.1 QoS routing parameters

To define QoS routing needs of a network, metrics are needed to associate numerical value with routes, and to compare the different routes [78, 79]. QoS routing constraints are collections of metrics that are controlled to match different application QoS needs. The most significant QoS parameters needed to support ITS multimedia traffics are (Table 1 show some QoS metrics relevant for multimedia applications) [80, 81]:

Table 1 QoS metrics need for real-time and non-real-time multimedia services

• Bandwidth this refers to the rate at which the network must convey data flow.

• Delay is the time taken for a packet, sent from a source to get to the destination (i.e., the maxim tolerable end to end delay for data flow, also referred to as the latency).

• Jitter is the variance of the delay.

• Loss the average of packets that do not reach their destination within a given time unit.

QoS routing metrics can be grouped into three categories [82]: additive, multiplicative and concave. The values of these QoS routing metric constraints over an entire network path can be defined as follows [83]: let $x_{1} ,x_{2} , \ldots x_{i}$ represent the network nodes, and lets $V(x_{1} ,x_{2} )$ be a metric values of a link $(x_{1} ,x_{2} )$. For any path $p = x_{1} ,x_{2} , \ldots x_{i}$, an additive, concave and multiplicative QoS metric can then be expressed as follows:

• An additive metric is given by the sum of the metric values of all the links in the path. Some good instances of additive metrics are delay, jitter, and hop-count. It is expressed:

  $$V\left( P \right) = V\left( {x_{1} ,x_{2} } \right) + V\left( {x_{2} ,x_{3} } \right) + \cdots + V\left( {x_{i - 1} ,x_{i} } \right)$$

  (1)

• A concave metric is expressed as the maximum or minimum metric values of the links in the network path. Some good examples of this metric are bandwidth, signal strength.

  $$V\left( P \right){{\hbox{min} } \mathord{\left/ {\vphantom {{\hbox{min} } {\hbox{max} }}} \right. \kern-0pt} {\hbox{max} }}\left( {V\left( {V\left( {x_{1} ,x_{2} } \right),V\left( {x_{2} ,x_{3} } \right), \ldots ,V\left( {x_{i - 1} ,x_{i} } \right)} \right)} \right)$$

  (2)

• A multiplicative metric is obtained by the multiplication of the metric values of the links in the network path. Examples are loss probability, reliability.

  $$V\left( P \right) = V\left( {x_{1} ,x_{2} } \right) \times V\left( {x_{2} ,x_{3} } \right) \times \cdots \times V\left( {x_{i - 1} ,x_{i} } \right)$$

  (3)

Remark 1

Different services require different QoS parameters and in order to meet these requirements (i.e., constraints) of applications, routing protocols must used QoS metrics to find QoS satisfied paths. The selection of QoS paths subject to multiple constraints is called Multi-Constrained Path (MCP) problem. The MCP problem is to find a path from a source to a destination such that all the QoS constraints are satisfied. The paths that satisfy these constraints are called feasible paths. So therefore, the purpose of this classification is to show how the designing of QoS routing protocols that find feasible paths that satisfy multiple constraints could improve the performance of the algorithm to support a wide range of QoS requirement concurrently. Bearing in mind that the major role of a QoS routing strategy is to compute paths that are suitable for the different types of traffics generated by various applications, while maximizing the utilization of network resources. Furthermore, given the complexity of VANETs technology, to support a steady communication between vehicles, the network must decrease the time needed to converge after a topology change to avoid data loss. Thus, a routing protocol with the multi constraint ability will be advantageous to the improvement of connectivity. It should be noted here that QoS metrics used for selecting routes is not necessarily the same as QoS constraints. For example, stability metric can be used for selecting routes to meet the bandwidth requirement of applications. Consequently, in order to support a wide range of QoS requirements, routing protocols need to have a more complex model where the network is characterized with multiple metrics.

3.2 Challenges of QoS-aware routing in VANETs

QoS-aware routing in VANETs do not just concern with the link connectivity and network resources availability, but also relate to the mobility and speed of the resources. Unlike in conventional network technologies where the topology seldom changes, the burden on the related routing protocol is minimal. VANETs topology frequent fluctuation introduces a significant overhead on the routing protocol, because the protocol needs to react to constant network topology change. Ideally, QoS is achieved by efficient allocation of network resources, which is enforced through resource reservation with adequate infrastructure. However, in ad hoc network such as VANETs, it is difficult, if not impossible to allocate network resources efficiently. The challenge lies in the fact that there is little or no infrastructure to rely upon for bandwidth assurance, and the high dynamic nature of the network, makes a resource reservation almost impossible [84]. On the other hand, the main data stream expected to be routed in VANETs concerns road safety time constrained application, such as accident information, traffic congestion, warning messages, and infotainment. These applications have stringent QoS requirements being delay sensitive services that require high link stability [85]. Factors such as packet delay, packet loss rate, available bandwidth, node velocity and trajectory, link reliability and jitter, regulate how stable a link could be [86]. So, to keep a steady communication among vehicles, it is important that the underlying networks sustain high data rate and connectivity. Offering such guarantee in VANETs is very challenging because such guarantee requires that information regarding topology change be preserved at each node in the network. But since VANETs are characterized by frequent link failure and path breaking, maintaining reservation and updates in a routing path becomes unmanageable, because such information need to be re-computed every time there is path break.

To this end, we briefly present some major VANETs QoS-aware routing protocols challenges [87, 88].

• High changing network topology the frequent network topology change because of vehicle high speed, density and mobility patterns, results in frequent link disconnection and broken path. Thus, a link initially created with the necessary needed QoS may no longer satisfy QoS any longer because the route through such link no longer exist due to node mobility.

• Failure-prone shared radio channel wireless network signal are unreliable. Their vulnerability to interference, their limited throughput, high packet loss rate, and end-to-end delay can affect both packet delivery ratio and link durability.

• Lack of central control to use network resources in a decentralized, self-organized network such as VANETs is very hard. Lack of central controller to synchronize and manage nodes activities could result in under exploitation of channels.

• Scalability VANETs have a high number of nodes within the transmission range, particularly during rush hours at intersection in urban areas. When network increased in size routing QoS degrades due to excessive routing protocol overhead and unreliability resulting from broadcasts because of wide network flooding. Minimizing routing control message overhead resulting from high nodes mobility and increasing nodes population is a key problem in achieving routing scalability in VANETs.

• Hidden terminal problem the broadcast natures of VANETs safety information exchange are sensitive to the hidden terminal problem. The hidden terminal problem occurs when transmissions from two nodes which do not know of the existence of each other collide at one common neighbor of those nodes.

• Inaccurate state information due to the frequent changing in network topology and the speed at which vehicle travel, maintaining precise network state information is cumbersome. Node information such as available data rate sent to a node could change as the message is being communicated to its adjacent node. Such information could be out of date and so may no longer be up-to-date, thus leading to a wrong routing decision.

3.3 Desired VANETs QoS-aware routing features

Communication in VANET is performed either through a single-hop if the communicating nodes are close enough (i.e., within each other transmission range) or through a multi-hop communication by intermediate nodes if the communication nodes are not within each other transmission range. However, unlike MANETs, discovering and maintaining routes in VANET is challenging, due to the peculiar characteristics such as dynamic topology, multi-hop communication, wireless interface, frequent connectivity changes and real-time/isochronous. Therefore, for efficient data communication, VANETs QoS-aware routing protocols should be:

• Distributed to deal with churning issues.

• Adaptive to the frequent changing topology caused by the high node mobility.

• Fast converging after every topology change.

• Resourceful to optimize the utilization of scarce network resources such as bandwidth.

• QoS-driven to provide a certain level of QoS as demanded applications are usually real-time/isochronous ITS-Infotainment.

4 Major VANETs QoS-aware routing protocols

Due to the numbers of challenges in providing effective QoS-aware routing protocols in VANETs, several solutions in the literature tried to address them. In this segment, we survey notable existing QoS-aware VANETs routing protocols published over the years since the first work on the topic in 2006.

4.1 GVGrid: a QoS routing protocol for VANETs

GVGrid- is a VANETs QoS-aware routing protocol proposed by Sun et al. [89]. GVGrid is a position-based routing protocol with on-demand characteristics. GVGrid protocol main aim is to improve routes reliability by decreasing data delivery delay-time. It uses digital map and Global Position System (GPS) to provide information on node position and direction. GVGrid assumes that each vehicle on the road is equipped with the same wireless devices, and vehicles moving with equal velocity in the same direction have stable wireless connections. Therefore, can be relied upon for QoS oriented routing. To route information from source to destination, GVGrid partition its geographic region into several consistent square sizes known as “grid”, where the route path with higher reliability and lower link delay from source to destination is determined. The size of the grid “w” is chosen based on the cell radius “r”, to allow nodes in every grid to communicate with their adjacent grid nodes. In GVGrid route discovery process, emphasis is given to route with the longest expected lifespan. Such route is determined by observing the mobility patterns within a requested zone (i.e., by noting the number of traffic signals or stop signs on the route at which the node is moving). To find a route from a source node “s” to a destination grid “d”, the source node will forward a Route Request (RREQ) to a selected node in all the adjacent grids that are within the zone. Any node that receives such request, will forward the message in the same manner till it reaches the node in a neighboring grid. This node will then forward the RREQ message to a representative node in the destination grid. To avoid routing loop, sequence of nodes, grids and travel directions are stored in every RREQ message, which contains information of routing path from source to destination. To initiate a route discovery process, a node “d” at a destination area “D” will need to confirm the receipt of an RREQ, the node with the smallest ID in the grid (i.e., leader node in the grid “D”), will then compute the best path from the source to the destination. Specifically, using the RREQ data, it calculates the route lifetime through the number of disconnections. Thereafter, a Route Reply (RREP) is sent to the source node through a chosen path. GVGrid offers route maintenance mechanism that restored earliest route in case the selected route goes down due to node mobility. It ensures that all grids stores information regarding the earliest route, this way the algorithm can get a substitute for the missing node whenever there is a link break. For example, given a grid $A$ with a link $q \leftrightarrow r \leftrightarrow s$. Since this link may breaks because $r$ moved out of the grid $A$. $r$ has to send a “LEAVE” message to node $q$ before leaving. On receiving the LEAVE message node $q$ will locate a new node $r^{\prime}$ to replace node $r$. Through simulation, GVGrid shown outstanding performance over Greedy Perimeter Coordinator Routing (GPCR) in terms of path lifespan, where GVGrid was shown to experience a longer route lifetime.

GVGrid routing protocol is most suitable for a dense traffic environment where nodes mobility is slow, such as in urban areas. It is not suitable for a sparse environment, such as highways where nodes move with high speed, where there are fewer vehicles on the road. The authors based their idea on the assumption that vehicles will travel on equal speed, however, this scenario is not possible in realistic VANETs situation. Furthermore, relying on stable vehicle speed alone is not sufficient, nor practical enough to guarantee a reliable communication between vehicles. Furthermore, relying on grids for stable route may be disappointing, bearing in mind the dynamic nature of VANETs where links are unstable. A node in a grid could have a short lifespan, or may not even exist at the time they are most needed. This situation could lead to high control overhead that may result in a high packet drop [90]. GVGrid can be subjected to higher operating expense and high packet drop due to its exclusive dependence on grids for stable route.

4.2 Differentiated reliable routing in hybrid vehicular ad hoc networks (DRR)

He et al. [91] have used V2V and V2I at highways to propose a differential routing protocol, which uses a novel mechanism of discriminating among links based on the application QoS needs. The idea is based on the concept of differential reliability (DiR), which permits DRR to adaptively allocate multiple link-disjointed paths to support VANETs applications which requires differential reliability. The proposed architecture supports both ad hoc and infrastructure based communication, where Road Side Units (RSUs) are installed across the highway. The transmitting ranges of an RSU form a cluster of vehicles known as Local Peer Group (LPG). The numbers of disjointed links in a cluster are determined ‘locally’, and information on the links is transmitted upon request to the RSU. If the request is acknowledged, depending on the topology of the network, a Differential Reliable Path (DRP) will be established. DDR effectiveness was demonstrated via simulations demonstrated. And it was shown to optimize route reliability with minimal route control overhead, at the same time it was shown to improve the capabilities to discover alternative link disjoint route for diverse applications.

DRR protocol implementation is trivial, as it only considered the variation in the number of link disjoints for its differential reliability. Local identification of an application reliability requirement has a tendency to ignore the correlation among LPG since vehicles can interrupt data transmission if the required number of reliable links is not met. It also lacks the feature of resource reservations on links. Nevertheless, this architecture introduces a novel dimension of routing protocol from the perspective of DiR, which applicability in VANETs still need further exploration.

4.3 Delay-reliability-hop (DeReHQ)

Niu et al. [92] used 802.11e, a wireless LAN standard, to deal with the QoS in VANETs. The authors argue that the life expectation of a route has more weight than its shortest path because shortest path are liable to break in no time, which could result in high routing overhead. Therefore, they proposed a three level constrained QoS routing algorithm (link reliability, end-to-end delays and hop counts) to contain the challenging demands of high reliability and short transmission time delay of VANETs routing. This protocol adopts the Enhanced Distributed Channel Access (ECDA), which is an IEEE 802.11e standard for categorizing data through priorities. Nevertheless, ECDA categorization is only relevant to wireless LANS (WLANS) and can only be applied to improve existing MANETs routing protocols, such as AODV to achieve quality of service. The effectiveness of their proposed protocol was examined via simulation in NS-2 and the result shows that the protocol performs significantly well, as it was able to cut down the routing load and improves the network traffic throughput.

As the authors pointed out, “DeReHQ does not consider service differentiation” and the route choice focused on a “single class link delay and reliability optimization”. This is not sufficient to satisfy the QoS demands of multimedia traffic in ITS. DeReHQ volatile pure ad hoc style of link connection will fail when dealing with ITS situation where a distinctive service needs to be provided for classified data. This implementation shows prospects of service prioritization and traffic classification in VANETs. Consequently, implementing this protocol in V2I mode that support resource reservation facility could be a big achievement.

4.4 Controlled vehicular internet access protocol with QoS support (CVIA-QoS)

Korkmaz et al. [93] proposed a routing protocol for real time Internet applications with QoS provisioning. The authors claim that the schemes adopted in IEEE 802.11e for traffic classification are not sufficient to guarantee QoS. Because they believe that multi hop transmission and possible contention can cause a disparity in quality of service implementation in real time applications. Therefore, they proposed a cross-layer communication protocol spanning VANETs for Medium Access Control (MAC) and network layers. This approach provides a working model for real time Internet accesses with guaranteed throughput. To guarantee throughput on highways, the communication time slot is split into two periods: the high priority period (HPP) and the low priority period (LPP). The HHP is assigned to real-time traffic to satisfy the corresponding bandwidth demand, while the remaining bandwidth is then apportioned to the LPP for best effort traffics. A vehicle transmits a service request to the segment router, which in turn forwards the request to an access point in range. The access points manage and approve all service requests by separating the prioritized time slots and time of communication with vehicles. Segmented routers are used as polling agents for vehicles that need services. By using an approach known as sub-slots, hidden terminal problem can be reduced, as it allows the unique segments to communicate their registration requests towards routers at a given time interval.

CVIA-QoS approach provides a working model for real time Internet accesses with guaranteed throughput. However, it has a tendency to decrease the overall system throughput during increased real time traffic. Using different time slots for different traffic types is not suitable for live streaming applications that are delay sensitive, such as sound recording and video streaming, which might need higher throughput.

4.5 QoS-aware roadside base station assisted routing in vehicular networks (BAR)

BAR is another QoS-aware routing protocol proposed by Huang [94]. They suggested a QoS approach for ad hoc network through infrastructure support to monitor service quality guaranteeing. This protocol implements Fast Learning Neural Network (FLNN) on road-side-units (RSUs) to execute the routing QoS constraints proposed for the schemes. When vehicles placed request for workable path, the protocol proactively calculates the requesting vehicle’s distance and neighbors by using FLNN. In order to work out the expected distance and neighbors of the source node, vehicle information such a distance, road condition and vehicles current speed is use as input to FLNN. This makes it easier for RSUs to comprehend in advance the resource availability of the source vehicle (since the RSU is responsible for determining the deliverable resources for any request). If the available resources cannot be acknowledged for future communications, the RSU shifts the control to its neighbor where the operation goes on. The FLNNs not only get the best generalization performance, but also have real-time learning and prediction ability that help in predicting bandwidth consumption in advance, to avoid packet dropping that may result from bandwidth inadequacy during handoff.

BAR approach decreases the packet drop ratio through proactive requests. Monitoring requests through FLNN makes it suitable for real time applications. All the same, considering its sole reliance on infrastructural support, providing RSU that will sustain the network coverage in a realistic VANET environment may not be feasible.

4.6 Delay and reliability constrained QoS routing algorithm

Delay and Reliability Constrained QoS Routing protocol (DeReQ), is an extended AODV protocol proposed by Niu et al. [95]. The routing protocol is a dual constrained QoS-aware algorithm, which can adaptively map the choice of packet path from reliability bound-to-bound integer. DeReQ QoS-aware routing approach lays more emphasis on two factors; link delay and the reliability of links. The main aim of this algorithm is to find the best route with highest link reliability and link delay that could satisfy the QoS constrained of a flow. DeReQ algorithm assumed that links in vehicular ad hoc networks are symmetrical. So, finding the best route in VANETs that satisfies two QoS metric constraints (link reliability and link delay) is considered an “NP-complete problem”. To solve this problem DeReQ focused on finding a link that is most reliable with acceptable delay as long as the delay is within a tolerable range. DeReQ routing algorithm can extend any MANET routing protocol into a suitable QoS-aware VANETs routing protocol. Through simulation, the proposed protocol was shown to outperform AODV protocol in term of link reliability and maintainability. Out performed the AODV in terms of end-to-end delay with a limit of 40 ms, and when subjected to the varying network topology, it achieved 80% route success rate.

DeReQ is not entirely a routing protocol, rather it algorithm can be used to extend existing routing protocol into providing QoS. As a consequence, it works only when it is combined with other routing algorithms. In DeReQ, VANETs safety characteristics such as high speed and density were not considered, thus, the protocol may not be relevant in a practical VANETs scenario.

4.7 Multi-hop routing protocol for urban VANETs

The Multi-hop Routing Protocol for Urban VANETs known as MURU was proposed by Mo et al. [96]. Its primary objective was to minimize the frequent VANET link disconnection caused by its high node mobility, and it’s likely to fail shared radio channel. To lessen the frequent VANETs link disconnection, MURU assumed that every vehicle is fitted with a static street map, where the source node can obtain information regarding the location of the destination node. To locate the best route with the minimum hop count, the source node uses data obtained from its static map (i.e., knowledge of the source node position and the destination node position) to compute the shortest path from the source node to the destination node. The shortest path is stored in a packet and use as direction for guiding the route request (RREQ) message. The RREQ message broadcast is in a rectangular format within an area known as “broadcast area”. This area is within the shortest path and confirmed within the region of the source and destination node position. Any packet outside this broadcast area is dropped. MURU protocol is a distributed protocol, and so does not need infrastructure support. To estimate the quality of potential paths between the source node and the destination node, a metric known as Expected Disconnection Degree (EDD) was proposed. EDD assess the quality of routes based on some determinant such as; node position, node speed and direction. EDD assumed the possibility that a link might fail within a time frame, so a path with small EDD link is selected. Every RREQ message in MURU contains the cumulative EDD for route found. To prevent message overhead that could be caused by instant RREQ re-broadcasting, MURU provides a pruning mechanism that enables every node that received the RREQ to hold it for a determined delay time (back off delay time in millisecond) before forwarding. The length of the delay time is proportional to the size of the EDD, the bigger the EDD size, the longer the delay. This is to make room for the possibility of locating a path with smaller EDD. During backup delay time, node will decide whether to drop the RREQ message or rebroadcast it. The decision on whether to drop or rebroadcast RREQ message is taken when a node, on listening to RREQ of another node, hear a similar RREQ with the same sequence number but has a lower EDD numbers. To avoid control overhead, it will drop its RREQ, since RREQ with lower EDD is considered the best link (i.e., link likely to have a longer lifetime). Otherwise, the node will rebroadcast the RREQ message.

If the broadcast area of the next hop node is outside the broadcast region, the situation could lead to a compromise that never produces better results (i.e., local optimum). Such situation could downgrade the scalability of the protocol [97]. MURU protocol was validated using AODV, GPSR and DSR, none of this protocol is QoS-aware protocol.

4.8 Prediction-based routing in vehicular ad hoc networks

Prediction Based Routing protocol (PBR) protocol proposed by Namboodiri et al. [98], is a QoS-aware routing protocol centred on vehicle internet connectivity in highway scenario. The authors proposed mobile gateways with wireless Wide Area Network (WAN) connections, to act as Internet gateways for vehicle internet connection. This is to replace the static roadside unit, which they imagine will be very expensive to build. PBR algorithm can seek for a new route in a nick of time before the existing link fails. It achieved this based on its presumption that every vehicle pattern of movement on the road could be predicted. Since the information regarding their movement and position can be made available through GPS or whatever means that might be used. Therefore, one can capitalize on such information, to predict the time it may take for a link to stay connected. This allows the protocol to provide alternative route just in time to prevent link disconnection. PBR algorithm is a reactive protocol, thus, it always consults the routing table for information about a route to a destination. If a route to a destination is not found in the table, it broadcasts a Route Request (RREQ) message with a defined number of hops. When the RREQ message reaches the mobile gateway, a confirmed return message using the node sequenced information will be added to the RREQ, and sent as a feedback message to the source node. In a situation where multiple gateways are detected, hops with the shortest number will be selected by the source node if they are moving in a similar direction with most of the hops. Otherwise, it chooses the route that has a link with longer lifetime.

Through simulation PBR algorithm was validated by comparing its functionality with a proactive and a reactive protocol. The comparison was based on the degree of route failure, varying node density and mobility patterns. The protocol shows better performance in terms of minimal route failure, packet delivery ratio and control overhead. However, the authors in PBR did not specify the proactive or reactive protocol used, making their validation incomprehensible and lacks bearing. The protocol demand for the lasting presence of mobile gateways all over the road is not practical. Using a mobile gateway in the PBR algorithm may sound good, particularly for Internet providers, it will be a good business for them since they will charge for their roaming. One may question the protocol workability in VANETs, bearing in mind the cost of internet connection. Nevertheless, to encourage vehicles to share their wireless network access will be very difficult if not unlikely. Further analysis still needs to be done before such conclusion can be drawn.

4.9 Intersection-based geographical routing protocol for VANETs

Intersection-based geographical Routing Protocol (IGRP) is a road-based QoS-aware routing protocol for urban environment proposed by Saleet et al. [99]. To implement this protocol, they assumed that information about available routes is provided by internet gateway. Such information is considered to have the newest updated view of the local network topology. The gateway acts as a location server that stores newest information about vehicles position that is within its surroundings. Each vehicle communicates information regarding their new location every time they change position. Using this information the internet gateway will build a set of paths between itself and the mobile nodes (MNs), which in this case are vehicles. Using the information, the internet gateway chooses the path it considered to be the best path (i.e., the most “connected” road segments) to transmit data. The protocol selects road intersection in a fashion that ensured high network connectivity among vehicles in intersections. It likewise supplies the desired QoS constraint such as efficient bandwidth utilization, tolerable packet delay and bit error rate.

IGRP supports a routing strategy known as “Carry-and-forwarding”, a situation where a node-forwarding packet holds the packet (i.e., buffering) until the next best hop is available or until network connectivity is established. This feature will increase its data delivery rate. The validity of the IGRP routing protocol was determined through numerical analysis and simulation. The result shows a significant performance when compared to well-known VANETs protocol like GPSR, OLSR and GPCR. Nevertheless, the simulation was taken utilizing a customized discrete-event simulator in Matlab. This makes it difficult to compare the results with other simulators.

4.10 A road-based QoS-aware multipath routing for urban VANETs (RMRV)

A Road-based QoS-aware Multipath Routing for Urban Vehicular Ad Hoc Networks (RMRV) is a QoS-aware routing protocol proposed by Hsieh and Wang [100]. They claimed that the current multipath routing protocols are unsuitable for used in VANETs city scenario because they are node base, which are characterized with high route instability. To enhance route stability, they proposed RMRV protocol, which can find numerous routes and used them intelligently. RMRV replenishes route by making sure that an alternative route is instantly available whenever a link fails. If a node need to communicate, a path is created if no path exists for such destination. To create a path, the source node will trigger a multipath discovery message, which will be broadcast over the network to find the destination node. Every node in the network maintained a route discovery (RD) packet table in which information about RD packets received is being kept. Aside the normal routing information such as source address, unique sequence number and destination address stored in the traditional routing table. They also proposed an extra packet called ‘road section list’ to be included in the packet to avoid route broadcast storm. In situation where the destination node receives more than one RD packets with different road section (RS) list, the destination node will respond by sending a route reply (RREP) packet to every node from which it received the RD packets. The RREP is geographically forwarded along every RS path with the estimated lifetime of every RS. RS estimated lifetime is to be used for predicting future connectivity of every route. To work out route future connectivity, they proposed a space–time planar graph, an approach in which path’s future time could be derived. The protocol was validated through simulation. The outcomes demonstrate a better performance when compare with Route-based using vehicular traffic routing protocol (RBVT-R), in terms of the packet delivery ratio and end-to-end packet delay.

The extra packets added to the normal route information could result to high packet overhead (as more packets are being sent, the total overhead packet will increase). Besides, the protocol uses the flooding process for route discovery; this could lead to too many network flooding, which might disorganize communications between nodes [101]. Though, by being beaconless, RMRV protocol could save bandwidth, but its high delay in the route discovery process makes it unsuitable for ITS real time traffic.

4.11 QoS swarm bee routing protocol for VANETs

QoS Swarm Bee Routing Protocol for VANETs (QoSBeeVanet) proposed by Bitam and Mellouk [102]. It is a QoS protocol with multipath link provisioning. The criteria for determining QoS links suitability are based on bandwidth, hop count and delay. By employing a proactive flat routing approach, it creates routing tables on every node in a VANET. The procedure for establishing routing tables and data dissemination is a three-step processes that mimic the communication pattern of bees. At the outset, the neighboring nodes are first discovered using periodic broadcast messages called ‘scouts’. Active links along with the quality of individual link is recorded whenever the round trip reception of the source node is acknowledged. Links are maintained by monitoring the frequency at which a scout message is received and also by using the error in the scout messages. Link status of multi-track routes are varied with respect to the deviation in the link quality, and are monitored through scouts. The proposed protocol was tested using AODV and DSDV via simulation, and the effect was shown to improve the QoS performance.

QoSBeeVanet routing strategy (i.e., the proactive and beacon approach), may introduce extra jitters in applications during route finding. Considering VANETs high node mobility that results in its frequent topology change, using a proactive approach for routing and beacons for route establishment may cause high control overhead [103]. QoSBeeVanet mechanisms for cutting overhead and jitters, is a stochastic broadcast of scout messages. This broadcast, based on random choice among multiple nodes, can be improved by including parameters such as reception rates, packet drop ratios, signal strengths etc.

4.12 Intelligent optimized link state routing (I-OLSR)

Intelligent OLSR routing protocol optimization for VANETs (I-OLSR), is a QoS-aware routing protocol that focus on the optimal setting of OLSR routing protocol parameters. This protocol was proposed by Toutouh et al. [104]. They indicate that an optimal routing strategy that better used network resources is necessary for efficient VANETs deployment. This is due to the facts that most applications in VANETs depend on the routing protocol. The main target of their study was to optimize OLSR routing protocol by way of fine-tuning the OLSR configuration parameter. To determine the best protocol configuration that will increase the network Packet Delivery Ratio (PDR), decrease Normalized Routing Load (NRL) and End-to-End delay (E2ED), for better network QoS. Their choice of using OLSR is purely based on its characteristics, which they saw to be best suited for VANETs. Features such as its competitive delays, its ability to adjust to frequent topology change and its simplicity in terms of the ease at which it can be incorporated into different level of the system. Their approach involves two stages, the optimization process and the simulation level. In the optimization procedure, they use a series of representative metaheuristic algorithm where they test four different techniques; Particle Swarm Optimization (PSO), Differential Evolution (DE), Genetic Algorithm (GA) and Simulated Annealing (SA). NS2 simulator was used to assess the fitness functionality of the solution generated by the optimized algorithm. They define the optimization problem as “a search distance and quality or fitness function” and to solve this problem is to work out “the least-cost configuration of a solution vector”. At the end of the simulation, information about the PDR, NRL and E2ED of the network scenario was generated. The generated information is needed to compute the communication lost function given by: Comm-Cost = w₂. NRL + w₃.E2ED − w₁.PDR. This is assumed to be the fitness part of the optimized problem. To improve the quality of service, is to maximized PDR and lessen NRL and E2ED to a minimal degree. This was achieved by applying the equation above (Comm-Cost). PDR was termed negative and factors w₁, w₂, and w₃ where the influencing weighing of each metric, w₁ was assigned 0.5, w₂ assign 0.2 and w₃ assign 0.3 weights. This is to make PDR take priority over NRL and E2ED, this way, the efficiency of communication is maximized.

The protocol was validated through computer analysis and simulation. The result shows that the optimized solution significantly reduces the network workload. It was shown to generate half of the routing load when compare to the parameters suggested by human experts (IETF RFC3626) [105]. By cutting down the routing load, the routing table complexity is lessening persistently. A Key finding of their work shows that by utilizing the optimization algorithms, NRL is reduced and PDF is increased by a certain fraction as opposed to the defined standard values. Among the four-optimization algorithms used, PSO shows better output of operating time. This makes it useful for time sensitive ITS applications. Although, I-OLSR protocol proves to be more scalable because it is less affected by medium access and congestion complication, and can work with other VANETs protocol in any network scenario. Nevertheless, the impact of obstacles and buildings on routing was not considered. It would be pertinent to know the effect the optimization algorithms will have in urban VANET scenario, where high packet loss due to hurdles is expected. The suitability of the optimization algorithm for a specific VANETs propagation model is another innovative topic for further research. Furthermore, the impact of the algorithm execution time, which might be critical for time sensitive ITS applications is an important aspect that need to be put into consideration.

4.13 A QoS adaptive routing scheme (IGLAR) for highly dynamic vehicular networks

IGLAR is a QoS-aware VANETs routing protocol proposed by Bhatt et al. [106]. The primary focus of IGLAR is to improve geo-location-based QoS-aware routing algorithm, by identifying optimal routes using vehicular traffic at intersections. The authors argue that the traditional protocols such as AODV and GPSR fail to consider vehicle behaviour at intersections. Thus, cannot manage the heavy traffic intensity usually experienced in intersections. To lessen the routing overhead due to VANETs periodic Hello messages, they proposed a beaconless well distributed next-hop routing protocol alternative. By changing the Request-to-Send/Clear-to-Send (RTS/CTS) mechanism in the IEEE 802.11 standard to find the next-best-hop to an optimal multi-criterion prioritization function. Using parameters such as: distance between individual next hop and the destination, required bandwidth, receive power level and distance to the transmitter. In terms of the connecting link between source and destination, IGLAR proposed a VANETs hybrid communication (i.e., V2I and V2V communication scheme). To minimized routing overhead that might result from high speed vehicle. The authors suggested the use of route that is expected to have a longer lifetime with minimal hop count, in place of the shortest path which lifetime might be short and in so doing could introduce high route maintenance overhead. The proposed IGLAR was validated via simulation; the result shows a better IGLAR performance over AODV, DYMO and GPSR. With a 15% throughput increase over AODV and a 30% throughput increase over GPSR, a lower delay of about 80% was also observed when compared with DYMO and GPSR.

The protocol consideration for hybrid VANETs scenario (i.e., combining V2V and V2I), could lessen the frequent VANETs link failure. This will maximize throughput, which will reduce communication overhead and lessen the packet loss rate. Since vehicle within signal range could act as relay node by extending connection to other vehicle outside the signal range via V2V communication. But, the protocol, sole reliance on traffic in the intersection, implies that VANETs high node mobility constraint, which have huge influenced on its link stability (link lifetime) was not considered. Introducing algorithms that could consider the trade-off between high density intersection VANETs scenario and sparse mode VANETs scenario could improve the protocol functionality.

4.14 VANET QoS-OLSR: QoS-based clustering protocol for VANETs

Wahab et al. [107], proposed a VANET QoS-OLSR, alleged to extend the QoS-OLSR [108]. They argue that the existing QoS-based clustering algorithm lacks multi-point relay recovery (MPRR) mechanism. That can choose alternative multi-point relays (MPRs) in situation of link failures. QoS-OLSR is inefficient in dealing with the VANETs node mobility problem, as it fails to consider node mobility metric in its QoS function computation. To overcome this setback, they proposed a QoS-aware clustering algorithm that is based on Ant Colony Optimization, which accommodate both the QoS constraints and the high VANETs node mobility constraint. VANET QoS-OLSR, main objective is to set up a stable cluster that could bring about stable communication links while satisfying the QoS needs of such communication. To extend the link lifetime and to reduce overhead, they introduced an MPRR algorithm that can choose alternative MPR nodes. The effectiveness of their proposed protocol was shown through performance analysis and simulation. The result indicates a vast increase in packet delivery ration to approximately 10%. The elongation of the network lifetime was also observed to be up by 12% when compared with the existing QoS-OLSR and the classical QOLSR.

VANET QoS-OLSR algorithm has the potential of assuring seamless VANETs connectivity (as it can achieve better scalability by the manner at which the nodes are clustered and its aggregation of the network topology based on hierarchical structure). Its ability to accommodate factors such as traffic density, node speed and resource management could create a stable cluster that will support communication stability and reduce link failure. Nevertheless, considering the highly dynamic VANETs environment, it will be difficult to get up-to-date network state information (as the cluster state information in use could be out-dated). Because the network state information accuracy is a function of the number of aggregation performed and these state information decreases as the number of aggregation increases [109]. Furthermore, sending ants to compute feasible routes and return the optimal one may not be practical in VANETs environment. As the time incurred waiting for the ants to finish their tours could introduce longer delay that could render the discovered solution worthless (since connections in VANETs have least link residual time and link establishment takes longer as the network becomes more mobile).

4.15 QoS aware node selection algorithm for routing protocols in VANETs

Ahmad et al. [110], proposed a QoS Aware node Selection Algorithm for routing protocol in VANETs (QASA). QASA is a QoS aware routing protocol developed for partly connected vehicular network. The proposed algorithm was used opportunistically to choose the next-hop vehicle for effective V2V communication. QASA protocol permits node forwarding packet to hold the packet for a next best hop yet to be available. By buffering the packets and send it in a later available opportunity (i.e., stored-carry-and-forward approach). The authors indicated that the method exploit a so called “bridging approach”. A technique which they believed could opportunistically be exploited to link the partition that may exist among vehicles in a cluster formation to support connectivity. Using this technique as claimed by the authors will prevent the network from being flooded with duplicates of the same packet, which will improve the network bandwidth and minimizes the end-to-end delay. In their simulated experiment, throughput was observed to be enhanced when the transmission range is shorter, but delay was on the increase. The Long transmission range was observed to incur minimal delay. To overcome the trade-off, the algorithm needs to allow the vehicles to choose the furthest possible vehicle within its range of transmission, while considering the QoS metrics. VANETs applications are bound to have different QoS needs and to cater for each application unique QoS needs, the protocol offered a system known as “Full Range Portion” (FRP). FRP is used to restrict the network functionality to be stuck on the applications QoS needs.

Though the bridging approach adopted by the protocol might be effective in finding an intermediate node for data transmission. Nevertheless, broadcasting a Request-to-Broadcast (RTB) and a Clear-to-Broadcast (CTB) messages over the entire network could introduce a situation known as “Broadcast Storm”, which could increase the network communication overhead. Thus, the protocol might not be suitable for ITS delay sensitive applications such as emergency warning information.

4.16 Adaptive routing protocol based on QoS and vehicular density (ARP-QD)

Authors in [111], proposes V2V QoS-based approach to find a connected path in urban vehicular scenarios. Their approach assumed that every vehicle is fitted with a digital street map and holds information about the road statistics. Given these premises, the ARP-QD uses the optimal forwarding path algorithm to find best next hop towards the destination. Since the next hop can either be within a road segment or at an intersection, the choice of metric for relay selection differs. To relay any selection, within a road segment, the hop count and link time are applied in a linear combination to deduce the state of the connection. It follows that, the higher value shows a link with less hop count and high link stability and vice versa. To allow QoS, for high priority data (such as video on-demand), the hop count is weighted higher than the link stability metric. For low priority data (such as text file transfers), connection stability is afforded a higher weight than the hop count. For relay selection at intersections, the ARP-QD uses a different strategy which includes additional metrics of the angle between the sender vehicle and the next potential road segment. The idea is to choose a road segment, which has the minimal angle, because the smallest angle shows a better quality of next intersection of data. If a relay node is not found during transmission, the ARP-QD will use an approach known as carry-and-forward [99]. Through numerical simulations, the proposed protocol was shown to have achieved a higher delivery ratio with less delay when compared with two other prominent VANETs routing protocols.

ARP-QD adaptive neighbor discovery strategy that is applied to acquire neighbors information based on QoS and vehicle density, will increase reliability at the same time balance the network traffic load. Its recovery strategy (i.e., store-carry-and-forward scheme), which relied on the vehicle mobility and the sequence of their contact will compensate for VANETs lacks of continuous connectivity and could lead to efficient end-to-end message delivery. This routing scheme uses multiple relay nodes and distributes each copy of the message to the relay nodes. Since multiple relay nodes in the network will carry a copy of the message, the destination node can get the message from any of the relay nodes. This way, the overall network delivery performance will improve. However, it’s proactive and beacon approach may introduce extra jitters in applications during route finding. Considering VANETs high node mobility that leads to frequent change in topology, using a proactive approach for routing and beacons for route establishment will introduce a high control overhead [103]. ARP-QD protocol, exclusive reliance on traffic in intersection implies that VANETs high node mobility constraint that have big influenced on its link stability (link lifetime) is not considered. To this end, the protocol may not be suitable for a sparse VANETs environment, such as highways where vehicles move with high speed and where fewer vehicles on the road. We suggest the inclusion of algorithm that could look at the trade-off between high density intersection VANETs scenario and sparse mode VANETs scenario as this will improve the protocol functionality.

4.17 Secure and robust multi constrained QoS aware routing algorithm for VANETs (SAMCQ)

Eiza et al. [112], proposed a multi-constraint optimal path routing, which can locate the optimal route that satisfies application QoS constraints based on optimization function. The idea behind the optimization function is to associate an optimization factor with multiple QoS constraints as needed by applications. The optimization function is open to change at runtime for different application data. SAMCQ protocol uses ant colony optimization (ACO) to traverse links and translate the link statistics into meaningful information through the objective function. A concept of pheromone is used to work out the neighboring hop where the absence of pheromone shows lack of information about the link status of the next hop. Under such conditions, the ants (i.e., the control messages) are disseminated to populate the pheromone table (i.e., it holds the link status information). Before ant dissemination, the residual link time of the next hop is also considered to avoid traversing a link with minimal link life time. Unlike the classic ACO algorithm, the pheromones are assigned a lifespan, essential for tracing back the traces of pheromones. The protocol also caters for securing the control information from adversaries through different checks. To support the QoS metric, each vehicle is required to sign the ACO route request message before transmitting. By so doing, each request will contain the travelled route information. Thus, the authors presumed that every vehicle have a map of the entire course. Therefore, any attempt to alter the QoS metrics by any intruder can be verified easily by the receiving vehicle. To avoid exploitation of the broadcast feature in the ACO route request, a tab is maintained, which stops further dissemination of the message. The routing is designed in a manner that only the source and the intermediate nodes can broadcast the ACO route request when the entry for a link does not exist. Thus, a received ACO request is first examined by the receiving vehicle to know if such request is actually from the source or the intermediate node within the routing link. If otherwise, it will be discarded. To prevent the spread of false information about a failed link, each node relies upon the pheromone lifetime information. Whenever control information about a failed link is received, each vehicle through their local information verifies to know if the pheromone lifetime for the advertised link genuinely is expired. Their simulation result shows that QoS can be guaranteed alongside security to better insure a dependable and robust routing in VANETs.

In a highly dynamic mobile network such as VANETs, the pheromone lifetime will decrease and as a result, vehicles will need to spread pheromones at a more frequent rate. Although, the protocol avoids traversing the links with minimal residual time but due to the proactive path discovery, consistent pheromone distribution for link discovery cannot be avoided even when there is no need for data transmission. The implication of associating a lifetime to pheromones can introduce a high degree of overhead control on the channels.

4.18 QoS aware data dissemination for dense urban region in vehicular ad hoc networks

Dua et al. [113], proposed a reward penalty based routing approach for achieving higher packet delivery rate in urban road scenarios. The main objective is to achieve higher PDR with reduced overhead under sparse as well as dense networks. The protocol operation can be classified into four main categories: (a) reward penalty assignment, (b) intelligent forwarding phase, (c) weight assignment, and (d) construction phase. In reward penalty phase, a linear mapping is used to determine the resilience of a link with the neighbor. The idea is to give a higher reward to link that persists over time and vice versa for link that is fragile. In order to determine the link quality, the protocol uses vehicular speed and distance. That is to say, a less distance and minimum relative speeds between the sender and the relay is an indication of a persistent link. In the intelligent forwarding phase, relay selection depend on the link bandwidth information, minimum distance of a relay from the destination, the speed of the relay towards destination and a relay approaching a dense network. Therefore, given the values of metrics from reward penalty phase and intelligent forwarding phase, weights are assigned to all the known connections from source to destination. The weights indicate the ratio of the metric calculation in the intelligent forwarding phase to the ratio of the metric calculated in the reward penalty phase. Finally, the construction phase uses the weights and the associated paths to calculate the shortest path using Dijikstra’s algorithm, which gives the shortest path from source to destination.

4.19 QoS-Vanet: cluster-based artificial bee colony algorithm for QoS routing protocol in VANETs

Fekair et al. [114], proposed a CBQoS-Vanet: Cluster-Based Artificial Bee Colony Algorithm for QoS Routing Protocol for VANETs. Their proposed protocol is based on the combination of QoS-based Clustering algorithm and Bio-inspired Artificial Bee Colony (ABC) algorithm. CBQoS-Vanet uses the cluster algorithm to organize and optimize route information exchange among various clusters. While the bio-inspired Artificial Bee Colony algorithm is used to locate optimum route from source to destination that satisfy QoS metric combinations. CBQoS-Vanet is a reactive routing protocol that uses the concept of bee behavior when they are in search for food, the manner in which swarms of bee communicate and forage for food. The protocol uses two kinds of packets: scout packet and forage in its route discovery strategy. The scout packet is made up of a forward and backward scout operation which mimics the strategy bees uses to pinpoint various food locations from their hive. The forward and backward scout strategy is used for locating routes between cluster head that satisfies QoS metric combination of bandwidth, delay and link stability, while the forage packet is used to transmit information between nodes. CBQoS-Vanet is equipped with a catching scheme that permits the protocol to proactively search for new routes even before the completing scouting process. CBQoS-Vanet was validated via OMNET++ simulation and the protocol was shown to have improved in packet delivery ratio, end-to-end delay and experiences a minimal overhead.

4.20 Adaptive quality-of-service-based routing for vehicular ad hoc networks with ant colony optimization (AQRV)

Li et al. [115], proposed an adaptive quality of service based routing for Vehicular Ad Hoc Network with ant colony optimization. In their work, they recognize the challenge of developing highly efficient routing protocol for VANET and the grounds for such challenge was attributed to the exceptional characteristic of VANET such as its large scale size, it’s frequent link disconnection and it repeats topology change caused by vehicle high speed. To cope with these challenges, the authors proposed a new routing protocol which can adaptively choose the intersection through which data packets can be transmitted from source to the destination, and the selected route have to satisfy the QoS constraints. To achieve their objective, the mathematicaly formulate the routing selection problem as a constraint optimization problem by regarding dynamic QoS-based routing selection to be a multiobjective optimization problem. An ant colony optimization (ACO) based algorithm was then use to solve the problem. To decrease the routing exploration time and lleviate network congestion they employed what they identified as terminal intersection (TI) concept, and to reduce the network overhead, the proposed a local QoS model (LQM) to estimate the real time and complete QoS of the urban road segments. In their work, connectivity probability, packet delivery ration and delay were the three QoS metrics adopted. The proposed ARQV protocol was validated through extensive simulations, and the result was shown to outperform the reference protocols used (i.e., (GSR and CAR).

5 Protocol performance evaluation

In this section, we assess the operation of the QoS-aware routing protocols in meeting the QoS requirement of the real-time multimedia application, through extensive simulation with video data transmission. Due to resource limitation the evaluation is limited to three selected protocols. We evaluate their performance by choosing one protocol from each of the metric combinations (i.e., one each from additive, additive plus concave and additive plus multiplicative). The protocols selected are: I-OLSR for addictive metrics, QoSBeeVanet for additive plus concave, and DeReQH for additive plus multiplicative. The simulation tool adopted in this experiment is NS3, therefore, we ensured that the selected protocol for each of the metric combinations are protocols that were evaluated using either NS2 or NS3 (see Table 4). It should be noted that the result presented in this section are average values of each of the QoS metrics computed over 10 runs for each simulation scenario with different random number seeds. The scenarios employed were used to determine the extent at which the network topology, the vehicular speed and the application (i.e., the multimedia data exchange) affect the performance of the selected QoS-aware protocols.

5.1 Simulation setup

Several communications network simulators exist that provide platform for testing and evaluating VANETs protocols such as NS2, NS3, OPNET, NCTUNest, OPNET++, etc. However, in this paper, the following simulation tools were used: Simulation of Urban Mobility (SUMO) [116]; Mobility model generator for vehicular network (MOVE) [117]; and Network Simulator version 3 (NS3) [118]. We choose NS3 simulator because it is an open source network simulator, which provide wide-ranging library of networking units and technology. Since NS3 is a discrete event simulator, in this paper unless otherwise stated, 10 runs were performed for each simulation.

The vehicular network scenario as used in this paper was created using SUMO and MOVE. The road topologies were created using the Map Editor Component of MOVE and vehicles movements were generated using the MOVE Vehicle Movement Editor. The vehicle editor allows for the specification of the several properties of vehicle routes such as; number of vehicles in a specific route, vehicle departure time, vehicle origin and destination, vehicle speed, etc. The output generated by MOVE is the mobility trace files that contain all relevant information regarding real-world vehicle movements.

To evaluate the protocol performance under a realistic VANETs topology, we downloaded the open street map of Petaling Jaya (PJ), Malaysia, and extract the partial streets of PJ using MOVE and SUMO. A grid view map of PJ with total area of 3 km × 2 km was created using the Java Open Street Map Editor [119]. The use of PJ open street map paves the way to explore a more realistic VANETs topology by making it possible for us to observe the characteristic and protocol behavior under network traffic that almost fit the ones in a real life deployment. Three procedures were used in order to execute the traffic simulation in this partially used area. These procedures are listed below:

• The mobility file of the map from Open Street Map (OSM) was generated. Most of the road segments in the map were retained for satisfactory simulation results. The tag depiction of the properties of the streets in OMS was reviewed. A manual correction of the intersection values is done so that the simulation results at appropriate location can be presented. For example, OSM output has to be reformatted and manually updated to match the formats required by NS3. In doing so, special attention is given to the intersection, redefining locations by using alternate coordinates. Subsequently, the anticipated element of the map was determined and exported in an OSM file.

• Outset of traffic flows for the generated partial map is obtained after the removal of the redundant objects from the anticipated specifics, and after identifying the end-nodes.

• The network is then simulated through NetConvert.

Figure 2 shows an Open Street Map of PJ city, which was downloaded from Google earth. The extracted PJ partial OSM image is provided in Fig. 3. OSM provides the required system with the longitude and latitude data from the PJ partial street map. The longitudes provided by OSM are mapped onto the necessary coordinate with aspired origins in the 2D area [120]. Recalculating the 2D coordinates in the first quadrant of the plane is done by manually shifting the geometric origins to the desired location using the MOVE map configuration editor. The mathematical equation in Eq. 4 was used to determine the interpreted coordinates (X, Y) in the first quadrant.

$$X = x + a;\quad Y = y + b$$

(4)

where

• (x, y) are the 2D coordinates before shifting the plane.

• (a, b) are the origin and destination.

• (X, Y) are the new 2D coordinates after shifting the plane.

Fig. 2

Petaling Jaya map using OpenStreetMap

Fig. 3

Petaling Jaya extracted streets map

The data extracted from the OSM database are compiled into an XML structure file named as (map-9.osm. xml). Map-9.osm. xml comprises of all data primitives, such as roads, intersections and relations. All the intersections generated in OSM are identified by their longitude and latitude values. The minimum bound latitude and longitude; maximum bound longitude and latitude of the values of the partial PJ city map are shown below:

• minlat = “3.10052” maxlat = “3.09804”

• minlon = “− 101.64725” maxlon = “− 101.64304”

The above set of points defines the polygon zones of roads, and the Meta data embedded within map-9.osm.xml file helps in defining the stream of signal rules on roads with other characteristic objects. The extracted OSM data is then manually fed into the map intersection editor to be configured. The significances of the street vehicles are defined using the MOVE’s road editor. This is done in order to provide one or more lane setups. The depiction of the street is studied in the road editor; these include attributes such as number of lanes, average speed and the road priority. For straight forwardness, a system of default streets was adopted and their attributes are as follows:

• Default number of lanes: 2

• Default maximum speed (m/s): 30 m/s or 108 km/h

• Default priority (%):80%

• Subsequently, the configured map is created as a final map (map-9.net.xml).

By engaging SUMO, the representation of traffic infrastructure was then observed. The mobility traces obtained by SUMO is exported into NS3 using the Trace Exporter. The two simulators are then launched concurrently, where the NS3 act as the client and the SUMO as the application server. NS3 reads from the generated mobility trace and sends commands to SUMO through the Traffic Control Interface (TraCI) to implement the simulation phases in order to stay synchronized with the time (see Fig. 4 for the illustration of the simulation flows).

Fig. 4

Flow of simulation of the generated mobility and traffic file as input to NS3

To simulate multimedia traffics as realistic as possible, three MPEG-4 video traces data: Jurassic Park 1, Star War IV and Mr. Bean were used. These video trace files are freely available at [121]. These three video trace files were concurrently streamed to generate an aggregated multimedia traffic (the three video traces data are simulated as real-time multimedia applications). Each video clip is set in motion at a random designated time of 0.2 s. Other significant information regarding the trace video files used in the simulation experiment is detailed in Table 2. Each simulation was run for 1000 s, and each simulation scenario is repeated 10 times with different seeds to guarantee good confidence interval for the results. User Datagram Protocol (UDP) was used as the traffic source. Both the RSUs and vehicles are referred to as nodes, where the RSUs are identified as static nodes at a stationary position, while vehicles are set to be mobile nodes. We presumed that all vehicles have a wireless connection that conformed to IEEE 802.11p standard with channel capacity of 3 Mbps for V2Vand V2I communications. The underlying network is constructed exclusively as an ad hoc network and the communication technique used is a hybrid VANETs (i.e., combination of V2V and V2I VANETs scenarios, see Fig. 1). Intelligent Driver Model was used as the mobility model and the radio propagation model used is the Two Ray Ground. Other parameters used in the experiments are detailed in Table 3.

Table 2 Frame statistic of MPEG-4 traces [121]

Table 3 Simulation parameters

5.2 Performance evaluation metrics

The investigation of the QoS-aware routing performance was done based on three key QoS metrics: Average packet delivery ratio, normalized routing load or overhead and average end-to-end delay. The main motivations behind the choice of these three metrics for evaluating the QoS-aware routing performance is as follows: (1) The metrics are highly dependent on the communication parameters such as wireless channel fading, communication range, road segment length, vehicle density and distribution, etc., which reflect the complete traffic information on a road segment. (2) The metrics may antagonize each other in different VANET scenarios. For instance, ascending vehicle density is advantageous to link connectivity improvement and delay decrease, but may aggravate end-to-end packet delivery ratio due to more influences from the channel congestion. (3) The three metrics are common to all the routing protocols that were surveyed. Therefore, the three metrics are selected to evaluate the complete and accurate realistic route QoS.

• Packet delivery ratio reflects the efficiency and reliability of a designed routing protocol, and in this paper, Average packet delivery ratio (APDR) is defined as the average ratio of the packets successfully delivered at the destination to the number of packets generated by the CBR sources [122].

• Normalized Routing Load: is the ratio of all routing control packets sent by all nodes in the network to the number of data packets in the network. It gives a measure of the routing protocol overhead (i.e., how many control packets are required for route discovery/maintenance to successfully transport data packets to their destination. The lesser the normalize routing load the better the routing performance.

• Delay, is an important metric of QoS, the delay can indirectly reflect current transmission channels loads, vehicle density and vehicle distribution over a road sector. Here we defined average end-to-end delay as the average time taken by a data packet to travel from source node (i.e., source vehicle) to destination node. The end-to-end delay includes all possible cause of network delay such as transmission delay, queuing delay, propagation delay, etc.

5.3 Results and discussion

The protocol considered are; I-OLSR for addictive metrics, QoSBeeVanet for additive along with concave, and DeReQ for additive along with multiplicative. The routing ability is estimated using three network topology size scenarios: scenario with 50 nodes is considered scenario one, scenario two has 100 nodes and scenario three has 150 nodes.

5.3.1 Average packet delivery ratio

Figure 5a–c present the result of the average packet delivery ratio as a function of vehicle speed at three different vehicle density scenarios. From the figures, one could observe that the packet delivery ration decreases with the rise in vehicle speed and vehicle density. The reasons are as follows: (1) higher vehicle density leads to better network connectivity, resulting in higher packet transmission rate. However, higher packet transmission rate increases the network traffic load that can result to congestion, packet collisions, packet loss, etc., which in effect lower the capacity per flow of the network. (2) As the number vehicles rises, the broadcast messages increase as well. The impact of the excessive broadcast messages emanating from vehicles as a result of the rise in the number of vehicles is bound to raise the degree of contention on communication links. This could result in what is known as broadcast storm, a situation where sufficient network resources is consumed in a way that can render the network unable to transport normal traffic [123, 124]. (3) As the speed of the vehicle increases, the inter vehicle gap widens and the pace at which the nodes move away from transmission range also increases. This situation can significantly inflate link disconnection probability in a manner that can affect the stability of the links. Furthermore, in Fig. 5a–c, it can be observed that QoSBeeVanet achieves a higher packet delivery ratio compared to both DeReQ and I-OLSR protocols, over different vehicle density and varied vehicle speed. There are three main reasons to explain such results. Firstly, when establishing the best routing path, QoSBeeVanet protocol searches for the best accessible routing paths utilizing its ACO algorithm. QoSBeeVanet ACO algorithm offers a more dynamic routing adaptation, as different communication pairs cooperate with each other to update latest pheromone to cope with the rapid VANET topology changes [125]. Secondly, when forwarding data packets, QoSBeeVanet adopts an adaptive path selection, due to its ability to prioritize the path selection in accordance with the data traffic type and their QoS requirements. Therefore, different feasible routes are selected for each data type transmission and congested routes are avoided, using the parameter of the state transmission rule and dynamic evaporation process [126].Thirdly, real-time multimedia traffic requires more reliable route with slightest cost. When the number of nodes in the network rises, the established routes cost increases as well, thus, decreasing the network reliability. Nevertheless, QoSBeeVanet was able to attain the highest packet delivery ratio because QoSBeeVanet does not only select practicable paths that guarantee better QoS. But also supervises the routes condition and ensured that their pheromone levels all through the data transmission processes is sustained [127]. I-OLSR, on the other hand, experience better delivery ratio compared to DeReQ in Fig. 5a, b. This is due its high optimization ability to choose alternative multi-point relays (MPRs) in situation of link failures. But, in Fig. 5c, I-OLSR packet delivery ration could be seen to decrease exponentially as the network density increases. This is because I-OLSR relies on periodic message forwarding to get the real time QoS associated with the network node’s resources. In a dense network, however, relaying the message over a large number of hops could result in flooding the network, thus significantly affecting the network performance. This is particularly true for real-time applications, which create a continuous flow of messages [128].

Fig. 5

Average packet delivery ratio with respect to varied vehicle speed for a scenario one, b scenario two and c scenario three

5.3.2 Normalized routing overhead

In this simulation, we compared the amount of overhead generated by the three routing protocols. Figure 6a–c represent the overhead of the three examined routing protocols. As shown in the figures, it could be observed that the overhead for all the protocols increases with the rise in vehicle speed and decreases with increasing density. The increase in routing load as a result of vehicle speed is caused by high maintenance that results from the frequent network topology instability. More link connection and disconnection is experienced as the vehicle speed increases. This will invoke immediate and increasing rate of route re-discovery that could result in high RREQ being flooded into the network. Therefore, results in high routing load. On the other hand, the rise in the number of vehicles will increase connection duration and the number of feasible routes to exchange routing information among neighboring vehicles. Having more paths readily available to switch to, and longer connection duration implies longer path life span. Path re-discovery will be less frequent and therefore results in less routing load. In the figures, QoSBeeVanet could be observed to have the lowest normalize routing loads in all the three scenarios. This is due to QoSBeeVanet novel stochastic broadcasting technique, which primary objective is to lessen the number of broadcast routing packets being exchanged to minimize network congestion, by distributing the routing packets only to a restricted number of neighbors [102]. Conversely, I-OLSR protocol experience lower routing overhead compared to DeReQ, because it uses a proactive approach for route discovery and maintains only the information related to the subset of the links instead of the whole links. This cut down the number of control packets generation as well as the flooding over the network.

Fig. 6

Normalized routing overhead with respect to varied vehicle speed for a scenario one, b scenario two and c scenario three

5.3.3 Average end-to-end delay

Figure 7a–c show the average end-to-end delay with varied vehicles speed and density. In the figures, it could be seen that the packet delay for all the three routing protocols increases as the vehicle speed and density rises. This is due to countless contentions and collision. As the number of node increases, the connectivity among the nodes increased as well. But higher connectivity between nodes brings about higher packet contention and collision, which cuts down the chance of successful data packet delivery. Consequently, as the vehicle speed increases, the inter-vehicle space lengthen, therefore, the number of nodes undergoing handoffs increases. Packet delay strongly can be influenced by the amount of handoff experience by a network. Because, higher handoff leads to higher frequency at which the routing protocol will converge, and this result into more delays. Furthermore, as could be observed in the figures, the QoSBeeVanet protocol experienced the lowest end-to-end delay rate in the entire three scenarios. This is because QoSBeeVanet can dynamically make routing decisions based on the latest global routing QoS, allowing it to cope with the rapid VANETs topology changes. More also, QoSBeeVanet uses a chosen path as long as it remains feasible and handles link disconnections locally, with no demand for packet retransmission. [129]. In the case of DeReQ, it experiences the highest packet delay rate (see Fig. 7a–c) because data packets are forwarded using the same path due to its shortest distance rule. And it does not consider service differentiation between different traffic flows [92]. Thus, in a distributed network topology such as VANET, forwarding packets suffer from longer time lag. In the case of I-OLSR, the routing path selection depends entirely on the number of hops and neighboring nodes along the links. This is not enough to reflect the accurate delay, as link breakage can unacceptably happen corresponding to vehicle movement, which results in a high topology change. Furthermore, I-OLSR is a source routing protocol whose best feasible paths are selected at route setup, and does not provide any backup path. Hence, in dynamic VANET environments, this routing protocol has to implement the routing recovery scheme repeatedly, which results in longer end-to-end delay.

Fig. 7

Average end-to-end delay with respect to varied vehicle speed for a scenario one, b scenario two and c scenario three

5.4 General remarks

A QoS routing protocol could be assessed in terms of their multi constraint path selection metrics, such as: multiplicative, concave and additive. Assessed in terms of network topology such as flat, hierarchical, hybrid [130], or in terms of their rout discovery approaches such as proactive, reactive and hybrid [131]. However, each QoS routing protocol possessed distinctive features, and requirement suitable for diverse situations. Nevertheless, in this article, we compared the QoS-aware routing protocol based on their multi constraint path selection metrics, and their performance in terms of their ability to handle ITS real-time infotainment services. Table 4 outlines the peculiarities deducible from the reviewed protocols. As could be observed in the table (i.e., Table 4), 90% of the surveyed protocols are position based. Position based routing protocols are better protocols at achieving a higher packet delivery rate (i.e., low latency). However, not all the protocols are able to accomplish a low latency of packet delivery rate. DRR and BAR, both have the ability to achieve a high data delivery rate. This is due to their support for vehicle to infrastructure communication (high rate of data delivery can easily be achieved with fixed infrastructure). Consequently, DRR has a novel mechanism that allows it to differentiate links based on application requirements and BAR ability to monitor requests through FLNN, makes them better suited for intelligent ITS communication such as emergency warning. GVGrid will experience low latency because of its ability to offer route maintenance mechanism, which restored earliest route if current route fails. Nevertheless, it is susceptible to high overhead packets due to its effort to mend broken route. CVIA-QoS on the other hand, do not differentiate between priority levels traffics; therefore, cannot achieve significant latency reduction in the delivery of real-time ITS information. Even so, it is capable of providing QoS differentiation between data traffic and soft real-time traffic. In that respect, can better guaranteed end-to-end throughput as fair bandwidth utilization among the users is assured by the manner its break the route into segments to evenly support bandwidth distribution. IGRP uses Carry-and-forwarding strategy (a situation where a node-forwarding packet holds the packet for a next optimum hop yet to be available). This act not really guarantees better packet delivery, but also ensures that the forwarding plan of activity does not fail because of link disconnection, which in turn improves communication. MURU, VANETs QoS-OLSR and PBR will experience low latency, as they mutually have the ability to search for a new path in a nick of time before the existing link fails. In addition, MURU general consideration for node position, node speed and direction, will improve the overall network latency, and minimized the time required for the network to converge after a topology change. Thus, allowing the network to maintain a steady communication between vehicles. This characteristic makes it best suited for intelligent real-time communication. The Ant Colony Optimization technique as used in VANETs QoS-OLSR to accommodate the QoS constraints, and the MPRR algorithm introduced to extend the link lifetime, will generally minimize the network communication overhead. By considering the trade-off between application QoS requirement and node mobility constraint, VANETs QoS-OLSR protocol has the ability to effectively manage ITS link connectivity constraint. The protocol possesses a great solution to guarantee communication continuity in VANETs irrespective of the traffic situation (i.e., the case of VANETs sparse scenario on highways and dense scenario in the city). Its ability to differentiate traffic in accordance with application QoS demands makes it an ideal protocol that can effectively support the stringent QoS needs of ITS infotainment services.

Table 4 Comparative summaries of VANETs QoS-aware routing protocols

DDR and CVIA-QoS are both single constraint QoS metric protocols (see Fig. 8 and Table 4). This characteristic makes these protocols inadequate for ITS infotainment services, which requires that the communication meet tight multiple QoS metric constraints. RMRV, I-OSR, MURU and BAR, are multiple constraints, with all metrics being addictive (Fig. 8 and Table 4). These combinations could lead to multiple constrained optimization problems. Multiple constrained optimization problem popularly known as ‘NP-complete’, is a situation where the routing algorithm is channeled toward a singular problem, and lack simple general ability that can extend easily to cater for new problem [132,133,134,135]. For example, MURU QoS metrics are packet delay ratio and end-to-end delay, which are both addictive (Fig. 8 and Table 4). Finding a path that satisfies these multiple constraints could be difficult and may not be workable, as the polynomial-time algorithms for the problem may not exist [136]. GVGrid, DeReQ, and PBR are multi constraint QoS-aware routing, with both multiplicative and additive constrained in their metric combination (Fig. 8 and Table 4). These combinations are also subject to Multi-constrained routing optimization problem (MCOP), which have been proven to be NP-complete [10, 11, 137]. Usually, several metric combinations are necessary to define the QoS required of multimedia services. However, many of the combinations are computationally so complicated to an extent of not being feasible. Any combination of two or more of either additive or multiplicative is NP-complete [138]. The only workable combinations of path determination with reduced computational complexity are combinations that involve metrics, like concave with any of multiplicative or additive (for example, bandwidth and delay or any other metric). Because the multi-constraint metrics problem of such combination can be solved in polynomial time [139].

Fig. 8

Taxonomy of VANETs QoS-aware routing protocol based on their metric constraints

For instance, QoSBeeVanet, IGLAR, VANET QoS-OLSR, IGRP, QASA, and SAMCQ, are multiple constraints, and they are a combination of concave and addictive constraints (Fig. 8 and Table 4). This combination is workable because they fall in the category of polynomial time composite problem [140]. These features make these protocols suited for ITS infotainment applications because they can support the wide range of the multimedia traffic QoS needs. ITS application services are heterogeneous traffics, thus, requires a multi-constrained QoS routing that could find potential path that entertains multiple QoS metric constraints concurrently. Routing protocols that support multiple constraints QoS metrics can support VANETs ITS communication more accurately.

Over the years, a number of heuristic techniques have been suggested in the literature to solve the MCOP problem. Some good examples can be found in [141,142,143]. But, owing to VANETs high link instability, the exact QoS-aware routing algorithms proposed in the literatures are not suitable for solving the MCOP problem. Different approaches such as: nonlinear definition of the path length [144], look-ahead feature [145], non-dominal paths [146], Dijkstra-like path search [147], and k shortest path [148], are few examples of the approaches employed in the literature to solve the MCOP problem. Nevertheless, these schemes are not applicable to real-time ITS applications. For example, the nonlinear definition of the route length is seen as one of the fundamental approaches to reaching an accurate answer to an MCOP problem (Eq. 5 explains the nonlinear depiction of path $P_{t}$, derived from the Holder’s q-vector norm) [149].

$$l_{q} \left( {P_{t} } \right) = \left[ {\mathop \sum \limits_{j = 1}^{N} \left( {\frac{{w_{j} \left( {P_{t} } \right)}}{{L_{j} }}} \right)^{q} } \right]^{{\frac{1}{q}}}$$

(5)

Where $l_{q} \left( {P_{t} } \right)$ is the length of the path, $w_{j} \left( {P_{t} } \right)$ is the weighted cost of $P_{t}$ with respect to constraint $j$, where $j = 1, 2, 3, \ldots , N$ and $L_{j}$ represent the constraint cost. This way, the multi-constrained complexity is translate into a single constraint problem that can be worked out using the Dijkstra’s shortest path algorithm. However, as could be seen in Eq. 5, the nonlinear definition does not permit the ranking of a one constraint over the others. The ranking of a constraint over the other is an essential feature needed in ITS multimedia applications such as video, which demands for a highly dependable route but could tolerate some amount of jitter. Therefore, applying Dijkstra’s algorithm by employing the nonlinear definition of route in multiple dimensions does not guarantee that the sub divisions of the shortest routes are actually the shortest path [150]. Hence, the k-shortest path approach needs to be used alongside the Dijkstra’s algorithm, which adds more complication to the routing scheme. Moreover, by applying the look-ahead approach, the Dijkstra’s algorithms need to be executed $N$ number of times [150]. In so doing, the computational complication becomes $N$ time Dijkstra’s algorithm complication, and $N$ time nonlinear length computation complication. This as well, is not appropriate for ITS infotainment applications, as the process put in additional time complication to the routing scheme.

Distributed heuristic algorithms such as swam intelligence based algorithms demonstrate numerous attributes suitable for solving the MCOP problem in high dynamic networks such as VANETs. Swarm intelligence based algorithms are fully spread; hold no single failing point, and the executive operations required at every node are straight forward. They are self-organized, robust, fault tolerant algorithms that can conform to traffic variations with no need for complex mechanism [151]. One of the most adopted swarm intelligent techniques is the Ant Colony Optimization (ACO) [152]. ACO is considered to be an efficient technique that could easily work out the QoS-aware routing MCOP problem [153]. In ACO, several artificial ants build solutions to the optimization difficulty and exchange information regarding the quality of their solution through a communication system similar to the ones adopted by real ants [154]. All the same, to what degree and how the ACO procedure can enhance the multi-constrained QoS-aware routing protocols in ITS network still remains an open issue.

6 Conclusion

A considerable amount of research has been done in the area of VANETs QoS-aware routings, which have led to the development of many multi-constraint QoS routing protocols. While these protocols might be sufficient for certain ITS applications, most of them cannot adequately support the stringent QoS requirement of real-time ITS infotainment applications. The evolution of routing protocol that could support intelligent ITS communication over VANETs, necessitates that such routing protocol possess the ability to determine the routes that satisfies multiple QoS constraint concurrently with minimal computational complexity. However, finding multiple paths that satisfy QoS constraint is difficult, as it could lead to a Multi-Constrained Path problem that cannot be solved in polynomial time.

In the course of our study, we remark that prior to 2011, all the existing VANETs QoS-aware routing protocols lack the features that could support effective ITS infotainment communication. They lack the attributes required to fend for the stringent QoS need of these applications. The year 2011 (the year IGRP and SWARM BEE QoS-aware routing protocol were published), ushered in a novel paradigm in QoS-aware routing. Where emphases on routing algorithms shifted from merely supplying an efficient path between nodes with minimal overhead control and reduce delays. To better define QoS-aware routing that is based on finding a path that satisfies multiple QoS constraints, at the same time maintain high network resources utilization. The basic problem with these QoS-aware routing is that they are not efficient in finding this path (i.e., the route that satisfies multiple QoS constraints). Equally, we outlined in Sect. 5.4, the difficulties that exist in finding these paths (i.e., the NP-complete issue). Nevertheless, the complexity introduced by the QoS-aware routing protocol diminishes over the years. This can be seen in later protocol development (like the case of IGLAR, VANET QoS-OLSR, QASA and S-AMCQ), proposed in the year 2013 to date.

6.1 Open research areas/future direction

Despite the significance of QoS need for VANETs safety and non-safety related applications, only few studies have attempted to discourse QoS resolutions of these applications. Since the efficiency of VANETs successful deployment depends on the performance of its routing protocols, in this section, we highlighted some open research areas that if well harnessed, could improve the performance of VANETs QoS routing protocols.

• Network status changeability VANETs routing solution must recognize that it can be run in different situations, from a highly congestion to sparse connectivity. So efficient routing protocol that could adapt to such dynamic topology changing needs, is still an open issue.

• Forwarding strategies In our reviewed protocols, almost all the QoS-based routing protocols depend on the traditional geographic forwarding in selecting their next hop. Considering the uncertainty of wireless network signal, which are unreliable due to their vulnerability to interference, their limited throughput, high rate of packet loss and end-to-end delay varying. This approach might not be the best suited approach for effective ITS communication, bearing in mind that an increase in vehicle distance apart could lead to lower reception. Hence new forwarding strategies that will cater for real physical conditions are required for successful VANETs deployment. For example, consider a situation where the farthest known neighbor is out of range by the time information is being forwarded to it, due to an instant change in the vehicle acceleration or deceleration, causing vehicles to move closer or further away from their expected position. A situation like that could generate more overhead, and may also lead to higher interference that might increase the chance of transmission collision. The trade-off needs to be investigated further.

• Taking advantage of the infrastructure Preexisting infrastructure such as mobile telecommunication masks deployed along the road by private telecommunication could serve as a storehouse for essentially needed information. Routing protocols could profit from them, if properly utilized, they could act as buffers, relays, etc. This could help routing algorithm make more intelligent decisions. We believe that research in this area, where vehicles can exploit pre-existing road infrastructure into use, is still an open research to explore.

The problem of QoS routing has still many undecided issues, since there are many tradeoffs that must be accomplished for a full successful deployment. I can look to witness the flow-based QoS routing of intra-domain routing, using algorithms satisfying multiple constraints, and class-based QoS routing in inter-domain routing, using algorithms base in a single metric resulting from the compounding of multiple metrics regarding the characteristics of the classes used within the QoS framework. Moreover, the problem of QoS routing for nowadays and upcoming VANET networks needs further studies due to the uniqueness of network environments.