Routing Optimization in Vehicular Networks: A New Approach Based on Multiobjective Metrics and Minimum Spanning Tree

Abstract

Recently, distributed mobile wireless computing is becoming a very important communications paradigm, due to its flexibility to adapt to different mobile applications. As many other distributed networks, routing operations assume a crucial importance in system optimization, especially when considering dense urban areas, where interference effects cannot be neglected. In this paper a new routing protocol for VANETs and a new scheme of multichannel management are proposed. In particular, an interference-aware routing scheme, for multiradio vehicular networks, wherein each node is equipped with a multichannel radio interface is investigated. NS-2 has been used to validate the proposed Multiobjective routing protocol (MO-RP) protocol in terms of packet delivery ratio, throughput, end-to-end delay, and overhead.

1. Introduction

Vehicular communication systems represent one of the most desirable technologies when the safety, efficiency, and comfort of everyday road travel need to be improved. VANETs provide wireless communication among vehicles and among vehicle and road-side units (RSU) equipments. Communication performance and Quality of Service (QoS) strongly depend on how the routing takes place in the network, on how protocol overhead affects the available bandwidth, and on how different channels are selected in order to minimize interference levels. When evaluating network topology through its routing table and, in the considered case, the availability of different available channels, a protocol may enhance the quality of communication. So, in this scenario, each node should select the best route in terms of QoS, not only considering a typical cost metric (bandwidth, delay, traffic load, or a combination of them), as in the classical multihop architecture, but also taking into account the benefits that can be obtained if different interference levels, that is different channels, are considered. QoS routing in multi-hop wireless networks is very challenging due to interferences among different transmissions, but VANETs offer the chance to reduce them since multiple simultaneous transmissions are possible.

In detail, a new routing protocol for interference reduction and link-duration enhancement is proposed for VANET environments, taking the advantage of a dynamic allocation of the Dedicated Short Range Communications (DSRC) spectrum, in order to reduce interference level among mobile nodes and to increase the overall link stability in the considered network. The proposed scheme can be integrated with different already-implemented routing protocols and its metric takes into account the best values of cochannel interference (CCI), link duration probability (LDP) and the term of end-to-end delay (e2e_D). Regarding the data dissemination in vehicular networks, our protocol does this purpose through the mechanism of construction of the Minimum Spanning Tree (MST), in order to diffuse the messages to a large number of vehicles. We decided to use the MST technique to minimize the number of transmissions so as reducing interference due to transmissions of neighboring vehicles. Spanning trees are widely used in communication networks as a mean for dissemination information from one node to all other ones and/or to collect information at a single designated node. So, MO-RP aims to choose different channels along the path from a source to a destination, obtaining a global metric minimization for the considered connection. This paper is organized as follows. Section 2 presents an in-depth overview on state-of-the-art routing in VANET; Section 3 gives an overview of the standard and Section 4 introduces the considered scenario and proposed idea; then Section 5 shows the obtained results. Finally, Section 6 concludes the paper.

2. State of the Art and Related Work

There are many efforts in the literature for VANETs and many authors have proposed some routing schemes, but most of them lack the employment of the multichannel availability of the mobile devices.

2.1. QoS Routing Protocols

In [1] authors propose a new geographic routing protocol that does not require proactive transmission of beacon messages. Data packets are broadcast to all direct neighbors, which decide if they should forward the packet. Receivers of the broadcast data would compare their distance to the destination to the last hop's distance to the destination: in that scheme, the bigger is the difference, the larger is the progress and the shorter is the timer. The ad hoc QoS on-demand routing protocol [2] also maintains some information about neighbor nodes, incorporating interference and broadcast route requests. In this way, feasible paths are detected and the final choice is made at the destination. In [3] Distribution-Adaptive Distance with Channel Quality (DADCQ) protocol has been proposed, based on the distance method to select forwarding nodes. In this work, the authors created a decision threshold function that is simultaneously adaptive to the number of neighbors, the node clustering factor, and the Ricean fading parameter. More recently, Zhu and Corson [3] proposed other algorithms to determine the exact schedule of slots for a flow through the network, guaranteeing the bandwidth by taking interference into account. In [4, 5], the problem to find the best multicast tree to distribute data along the source and multicast destinations has been presented. In these works, the authors look for the best solution facing an NP-complete problem considering several constraints on QoS parameters. In order to find the best solution the authors propose an evolutionary genetic algorithm, which does not guarantee finding the optimum due to the nature of the algorithm. However, they demonstrated finding a local optimum closer to the optimum in the available solution space configuring the possible algorithm parameters driving the evolution and avoiding the evolutionary divergence.

2.2. Location-Based Routing Protocols

The grid location service (GLS) [6] divides the network area in a hierarchical structure known as a quadtree, which is a square area divided recursively into squares of equal size. Squares of the same size are said to belong to the same order. Each network node maintains a list of all the positions of the nodes belonging to its first-order square (smallest possible), broadcasting periodically this information. A node periodically sends updates of its position to a node in each adjacent first-order square. The Anchor-based Street and Traffic Aware Routing (A-STAR) [7] is a position-based routing protocol; the words “anchor-based” refer to the fact that a source node includes in each packet an array containing a list of geographical points (anchors), through which the packet must pass to reach the destination. A-STAR is based on the assumption that each vehicle knows its position via GPS, the location of the destination through a location service, and is equipped with a digital map of the city that includes statistical information on road traffic. This last aspect has been faced in a recent contribution [8] where authors proposed interference-aware metrics in the context of UWB channel model. However, the different context of VANET environment suggests applying other strategies based on the specific MAC, later associated with vehicular communications. The intersection-based geographical routing protocol is proposed in [9]; it is based on a smart selection process, during which some road intersections are considered as positions where packets have to flow to reach the gateway. The idea is very suitable because it guarantees, through the formulation of an optimization problem solved by genetic algorithms, network connectivity among the road intersections, satisfying QoS constraints, considering a geographical place where to forward packets, instead of single nodes. But if all nodes in the network focus their behavior on this routing strategy, there will eventually be a great amount of data traffic on particular higher rated roads. In [10], the authors propose an RFID-assisted localization system. The proposed system employs the DGPS concept to improve GPS accuracy. A vehicle obtains two different position data: GPS coordinates from its own GPS receiver and accurate physical position via RFID communication. Then, it computes GPS error and shares it with neighbors to help them correct inaccurate GPS coordinates. In [11], the authors considered the effects of mobility, which causes frequent and rapid topology variations, with a consequent increase in routing overhead. The proposed idea mitigates these undesired effects, considering a reactive location-based approach each time the location information degrades. In [12], the authors present a fault tolerant location based service discovery protocol for Vehicular Networks. The main advantages of this protocol are its ability to tolerate service providers failure, communication links failure, and roadside routers failure. The authors of [13] introduced a new greedy routing protocol named Greedy Routing with Abstract Neighbor Table, based on the knowledge of the n-hop neighborhood. This protocol operates a smart network subdivision, in the sense that it separates the geographical area into several regions, considering only one representative neighbor for each region.

2.3. MAC Layer Protocols

In [14] a novel multichannel TDMA MAC protocol (VeMAC) has been proposed for a VANET scenario. The VeMAC supports efficient one-hop and multi-hop broadcast services on the control channel by using implicit acknowledgments and eliminating the hidden terminal problem. The protocol reduces transmission collisions due to node mobility on the control channel by assigning disjoint sets of time slots to vehicles moving in opposite directions and to road side units. In [15] an adaptive medium access control (MAC) retransmission limit selection scheme is proposed to improve the performance of IEEE 802.11p standard MAC protocol for video streaming applications over vehicular ad hoc networks (VANETs). A multiobjective optimization framework, which jointly minimizes the probability of playback freezes and startup delay of the streamed video at the destination vehicle by tuning the MAC retransmission limit with respect to channel statistics as well as packet transmission rate, is applied at road side unit (RSU).

2.4. Multiobjective Routing Protocols

In [16] a contextual cooperative congestion control policy that exploits the traffic context information of each vehicle to reduce the channel load has been proposed to reduce the load on the communications channel while satisfying the strict application's reliability requirements. In [17], the authors present the profile-driven adaptive warning dissemination scheme (PAWDS) designed to improve the warning message dissemination process. Regarding traffic safety applications for VANETs, warning messages have to be quickly and smartly disseminated in order to reduce the required dissemination time and to increase the number of vehicles receiving the traffic warning information. In [18], the authors propose a novel approach for the sanitary resources allocation in traffic accidents. This approach is based on the use of multiobjective genetic algorithms, and it is able to generate a list of optimal solutions accounting for the most representative factors. In [19], the authors propose a QoS routing protocol for MANET with specialized encoding, initialization, crossovers, mutations, fitness selections, and route search using genetic algorithm with multiple objectives. In [20] the authors present a new modeling framework for routing in ad hoc networks which, used in conjunction with metaheuristic multi-objective search algorithms, will result in a better understanding of network behavior and performance when multiple criteria are relevant. The authors of [21] introduced an intervehicular ad hoc wireless network content exchange system. It is composed by two novel communication protocols, using multi-objective genetic algorithms. In [22], the authors introduce the notion of multi-objective route selection in mobile ad hoc networks (MANET) using an evolutionary fuzzy cost function (it is a continuous function of the metrics describing the state of a route) to deliberately calculate cost adaptively.

2.5. Interference-Aware Protocols

Another important issue in VANETs is the choice of an appropriate transmission channel, not only considering the type of traffic (emergency, security, platooning, etc.) but, mainly, focusing on the reduction of the internode interference. In our previous works [23–26] an enhancement of the Ad hoc On-demand Distance Vector has been proposed, in terms of metric optimization. In particular, it has been modified in order to take consideration of the availability of different transmission channels with an integrated metric, which takes into account the interference level over the different channels. In particular, it allows the management of the multichannel capability of the WAVE standard at the routing layer through a higher-level channel selection, which is based on an interference-aware algorithm. The proposed protocol periodically estimates the Signal to Interference Ratio (SIR) on the available channels, reducing the interference level among nearby mobile nodes. In this way, the new considered metric gives the opportunity to choose the next hop in routing operations depending on the best perceived SIR value on the link. It has been shown how, despite a negligible increase in terms of protocol overhead, there are good enhancements in terms of throughput and packet delivery ratio.

2.6. Other Protocols

The effects of mobility are considered in [27], in which a new metric is introduced in order to proactively adapt to a constantly changing topology. The scheme proposed by Sofra et al. considers the lifetime of a link and the forwarding operation is carried out on the basis of how much a link can be considered stable during routing operations. A precise mobility model evaluates link duration; moreover, the model is able to capture the trend of link degradation and fluctuations. In [28] the authors propose a predictive technique based on sequential patterns and two mechanisms used to prepare data for this technique, as well as some performance evaluation for these mechanisms to determine the most feasible choice in terms of communication overhead. VANETs have been also considered for new applications [29], like security and smart operations in vehicular environments or optimized data delivery [30]. In [31] the Delay-Tolerant concept has been investigated for vehicular networks, considering the opportunity of carrying opportunistic and asynchronous communications, based on the store-and-forward paradigm. The authors have shown how by introducing some fragmentation approaches network performance can be improved, also in terms of delivery ratio.

3. Vehicular Communications Standards Overview

A Vehicular Ad hoc NETwork (VANET) represents an ad hoc technology in which each node is represented by a moving car, so each vehicle can send and receive messages through the distributed wireless network with each other. With VANET, each participating car is turned into a wireless router, able to transmit within a coverage range of hundreds of meters with other mobile nodes (vehicle-2-vehicle communications (V2V)). Vehicles are equipped with advanced wireless communication devices without any base stations. This type of network can provide a wide range of services such as intelligent transportation system (ITS, for example, if a vehicle detects a traffic accident, it informs all the surrounding vehicles about the event). VANETs allow the use of advanced driver assistance systems (ADAS) and use of ad hoc communications for performing efficient driver assistance. Since the first standard drafts proposal, there has been a lot of research activity on VANETs, aimed at obtaining more intelligent transportation systems, in order to provide car drivers with vital information, such as critical situations, dangers, accidents, and congestion levels. In ITS, when mobile nodes have to communicate with road side units (RSUs), that is to say, vehicle-2-roadside infrastructure (V2I), vehicles must be equipped with some radio devices, called on-board unit (OBU), which enables short-range transmissions. In general, proposing a standard for a particular technology is aimed at simplifying products development, helping to reduce global costs. In addition, only the employment of international standards can ensure rapid implementation of new technologies. In VANETs, there are many standards that regulate wireless access: they range from protocols to security specification, from routing to addressing services and interoperability.

3.1. Direct Short Range Communication (DSRC)

This is a short/medium range communication standard, providing some services that were developed to support V2V and V2R communications. DSRC covers a wide range of applications, including safety messages, traffic information, platooning, and many others. DSRC is aimed at providing data transfers at high rates, with low latency. Draft and proposals for DSRC started in 1999 by the Federal Communications Commission (FCC), which allocated a spectrum of 75 MHz at 5.9 MHz, as illustrated in Figure 1. Later, the FCC established the licensing rules about the DSRC (it is a free bandwidth because the FCC does not charge for usage of that spectrum, but it is licensed, with a restricted utilization) [32]. In fact, (DSRC) spectrum [33] is now divided into seven channels, each one with a 10 MHz bandwidth; it is allocated in the upper 5 GHz range.

Figure 1

International standards for DSRC.

Each station continuously alternates between the Control Channel (CCH) and one of the Service Channels (SCHs) or safety channels. SCHs can be used for either safety (with higher priority) or nonsafety applications. For more details see [34].

3.2. Wireless Access in Vehicular Environments (WAVE-IEEE 1609-IEEE 802.11p)

As written previously, VANETs traffic scenarios have more issues than fixed wireless networks, caused by mobile effects (changing speeds and different driving environments).

In these environments, beaconing mechanisms, with many required handshakes, lead the overhead to be very high. At this aim, the working groups renamed the DSRC to IEEE 802.11p WAVE [35], which is able to be universally adopted across the world. Figure 2 shows the layering that has been provided for the IEEE 802.11p, limited by the scope of IEEE 802.11 which strictly works at the MAC and PHY layers. The WAVE standard defines the devices introduced previously, OBU and RSU, which reside on the vehicle (mobile device) or on the road (stationary device). Generally, RSUs provide services to mobile nodes, which utilize a peer application that uses such a service. The MAC layer in WAVE is equivalent to the IEEE 802.11e Enhanced Distributed Channel Access QoS extension. The PHY layer employs 64 subcarrier OFDM, 52 of them are used for actual transmission, consisting of 48 data subcarriers and 4 pilot subcarriers. There are four possible modulation schemes: BPSK, QPSK, 16-QAM, and 64-QAM, with coding rates equal to 1/2, 1/3, 3/4 1/2, 1/3, and 3/4 and an OFDM symbol duration of 8 μs. The WAVE standard relies on a multi-channel concept which can be used for both safety-related and entertainment messages. The standard accounts for the priority of the packets using different Access Classes (ACs), having different channel access settings. This shall ensure that highly relevant safety packets can be exchanged timely and reliably even when operating in a dense urban scenario.

Figure 2

WAVE layering compared to ISO reference model.

3.3. Security and Privacy Challenges in VANET

Security and privacy are two main aspects in vehicular communications, which must be ensured for the successful acceptance and deployment of that technology. As illustrated in [36], there are many threats and possible attacks in vehicular environments, like denial of service, message suppression, fabrication or replay attack, and so on. Recently, there have been a lot of research and proposals, based on different techniques. For example, there can be hardware security implementation, equipping the vehicle with two modules: event data recorder (which provides tamperproof storage, in the sense that it stores some kind of critical data, like position, speed and time, useful in case of accident) and tamperproof device (which enables cryptography into the system). There can be, also, some kind of identification mechanisms, based on the possibility of recognizing a node from the beginning, when the vehicle is manufactured. Each vehicle will have a unique identifier, called Vehicle Identification Number or an Electronic License Plate (which allows the vehicle to be identified and to authenticate itself).

4. Problem Statement, Contribution, and Proposed Protocol Scheme

This paper focuses its attention on the enhancement of routing operations in VANETs, taking into consideration both neighbors' interference level and link duration, in addition to classical end-to-end delay term. The proposed idea, called multiobjective routing protocol (MO-RP), is general and does not depend on the considered routing protocol. It can be integrated with the majority part of existing routing protocols and it is based on the following

• (i)

analysis of interference dynamics for choosing an appropriate transmission channel in order to minimize Co-Channel Interference (CCI);

(ii)

periodical refresh, in order to evaluate the updated interference value available on each channel;

(iii)

definition of Link Duration Probability (LDP), in order to choose more stable paths;

(iv)

periodical calculation of delay end-to-end on each couple of mobile nodes that build a path;

(v)

transmission of synchronization packets in order to advise the receiving node of a new channel selection.

As introduced and explained in [14], we considered that each VANET node has two interfaces (transceivers): the first (transceiver1), which is always tuned to the control channel (CCH), and the second one (transceiver2), which can be tuned to any of the 6 service channels (SCH). Using the information carried out in the messages sent and received on CCH, in each time slot a node can switch on selected service channels.

As illustrated in the next subsections, the novel idea is proposed in the form of optimization problem, based on the discovery of the appropriate spanning tree.

The proposed protocol is based on a multi-objective metric related to LDP, e2e-delay and CCI; these three factors, dimensioned through an objective function, are aimed at building paths more robust to CCI and more stable in time (considering vehicular mobility) and, finally, selecting the paths which minimize the e2e delay, (due to the multi-hop scheme). First of all, the node which wants to transmit data sends a hello packet for the activation of the neighbor discovery process. In this packet, information about weights and metric is inserted and exchanged. Once the node which wants to transmit data has collected the information about all the possible paths, the best one is chosen.

4.1. Scenario Description

Let us consider the VANET topology illustrated in Figure 3. A path discovery phase is initiated each time a source node $v_i\in V$ needs to transmit to a destination node $v_i\in V$ . The terms ${\rho }_{x,y}$ , ${\chi }_{x,y}$ , ${\theta }_{x,y}$ are, respectively, the evaluation of the metric parameters (end-to-end delay, cochannel interference, and link duration probability).

Figure 3

An example of a VANET scenario.

When dealing with wireless communications (especially in vehicular environments), classical metrics become inadequate, since they do not consider all the negative effects that are present when paths from sources to destinations are built. If only the hop count is considered, the obtained paths may suffer huge interference levels and/or short duration and, on the contrary, minimizing the interference may bring the considered protocol to obtain longer paths with scarce duration. As in [37] where a multi-objective metric has been proposed in the MANET scenario, in this paper a joint metric to account for more parameters considered useful in the VANET scenario is introduced.

4.2. The Main Terms of the MO-RP

This work focuses the attention on the proposal of a new multi-objective metric, which combines co-channel interference, link duration probability, and End-to-End delay. The number of signaling packets should be changed in order to take into account the new concepts; the main attention, instead, is focused on the definition of the key elements of a new metric.

The proposed solution works in a distributed manner and exploits protocol messages to perform routing decisions and update routing table entries. This approach needs more time than a centralized approach to reach a stable routing path (converged network), but it is possible to initiate session faster. In fact, some paths could be changed during sessions for several reasons. In the transitory period, some paths can change because routing tables are not completely converged, so they lack information about complete network configuration. MO-RP is a distributed protocol and it works like the (DVMRP) distance vector multipath routing protocol. In particular, a mobile node sends a neighbour discovery message to know its neighbours. The neighbour responds to this message sending its identification number (ID) and its routing table information. The node that sends neighbour discovery receives several messages from its neighbours for building its own routing table. Once a node changes its routing table, then it propagates changes to its neighbours. In order to maintain the presence of the node as neighbour, it has to receive periodically (each 500 ms) an alive message from its neighbours. If a node does not receive an alive message until that amount of time, then it erases the entry related to the neighbour from its routing table and propagates this information to its neighbour nodes. When a new path information is coming from a neighbour, the node checks in its routing table if it has the entry related to the destination. If it is not present, then a new entry will be inserted into the routing table; otherwise the node performs the execution of a routing decision algorithm, taking into account three different terms in a metric, which will be faced in the next subsections, performing the update of the routing table. The flow chart in Figure 4 resumes the main phases of the protocol. In order to maintain an updated VANET topology, periodically, nodes exchange also information about links information, such as end-to-end delay, LDP, and CCI. Therefore, each node keeps a snapshot of the topology into its memory. This knowledge is used to perform the routing decision algorithm when multiple paths are available to reach a destination. The routing algorithm can be viewed as a linear optimization problem and its formulation is presented into next section.

Figure 4

Flow chart of neighbor discovery process.

4.3. Linear Optimization

In order to present the linear optimization problem, used in the construction of the best path from a source to a destination, some key concepts about the Graph Theory need to be recalled, with some analytic representations. A generic graph can be presented as $G(V,E)$ , where V is the set of nodes that compose the graph (including OBU and RSU) and E is the set of edges. Each edge has three associated terms, as shown in Figure 5:

• (i)

${\rho }_{x,y}$ is the term related to the delay along the link that connects a node $(x)$ with a neighbor $(y)$ ;

(ii)

${\chi }_{x,y}$ is the term related to the CCI among the node $(x)$ and a neighbor node $(y)$ ;

(iii)

${\theta }_{x,y}$ is the term related to the Link Duration Probability (LDP) among the node $(x)$ and a neighbor node $(y)$ .

Figure 5

An example of a generic link and its related weights between two generic nodes $(x,y)$ .

Once a source node $s\in V$ is chosen it is possible to define a set S defined as herein shown:

$$\begin{array}{cc}& S=\left\{s\right\}.\end{array}$$

(1)

Moreover, a set of nodes D is composed of all the remaining nodes (vehicles). It is defined as shown in what follows:

$$\begin{array}{cc}& D=V-S={{\displaystyle \bigcup }}_{i=\mathrm{1}}^n{V}_i\mid i\ne s,\end{array}$$

(2)

where N is the set of the nodes that compose the vehicular network and therefore we define n and z as $n=|V|$ and $z=|D|$ , that is to say, the cardinalities of nodes, and destination nodes sets. Given a source node s, the related tree $(T_S)$ is defined as $T_s=G(V_T,E_T)\subset G(V,E)$ in particular

$$\begin{array}{cc}& V_T=V=S\cup D\mid S\cap D=\varnothing ,\\ E_T\subset E.\end{array}$$

(3)

Given a tree $(T)$ it is possible to define a unique path between the node s and all remaining nodes, so

$$\begin{array}{cc}& z=\left|D_T\right|,\\ {\forall }_{j=\mathrm{1}}^z{d}_j\in D_T\mathrm{\hspace{0.17em}\hspace{0.17em}}\exists \mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Path}{\left(s,d_j\right)}_T\subset V_T,\\ m_j=\left|\text{Path}{\left(s,d_j\right)}_T\right|.\end{array}$$

(4)

Hence, $m_j$ is the number of the nodes (HOPs) that a generic packet has to pass through to go from node s to node $d_j$ . Additionally, z is the size of the set D related to a generic tree T.

4.3.1. Constraints Definition

Let us define the CCI contributing as derived from the expression of the received power, for all the available channels. It strictly depends on the transmission power and radio propagation phenomena. Using the theory of [38, 39] for DSRC channels, it can be calculated as the signal attenuation of the received power, using the Rayleigh channel model that does not take under consideration the transmission channel but only the distance between transmitter and receiver:

$$\begin{array}{l}{P}_{\text{loss}}\left(v_i,v_j\right)=\mathrm{40}·\log \left(d_{ij}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-\left[\mathrm{10}·\log \left(G_t*G_r\right)+\mathrm{20}·\log \left(h_t*h_r\right)\right],\end{array}$$

(5)

which indicates the loss in signal strength (in dB) among the couple of nodes $v_i$ , $v_j\in V$ . The terms $G_t$ and $G_r$ are the TX and RX antenna gains, respectively, while $h_t$ and $h_r$ are the TX and RX antenna heights. From (5), the expression of the received signal strength (in dB) by node $v_i$ , for the signal transmitted by node $v_j$ , on channel $c_l\in \text{CHAN}$ , where $\text{CHAN}$ is the set of available transmission channels, with $\parallel \text{CHAN}\parallel =6$ (DSRC channels are 7 in total, but we are not considering the CCH), can be easily written as follows:

$$\begin{array}{cc}& P_r\left(v_i,v_j,c_l\right)=P_t-P_{\text{loss}}\left(v_i,v_j\right),\end{array}$$

(6)

where $P_t$ is the transmission power (the same for each node on each channel). In real environments, the value of $P_r$ can be easily evaluated via hardware, but for our simulation purposes, the expression of (6) is very suitable. It can be used for accounting path loss effects, which are dominant in VANET environments, because channel coding and frequency interleaving make the bit error performance of an OFDM link in a frequency selective channel depend more on the average received power than on the power of the weakest subcarrier. From the value of (7), the expression of the CCI term for node $v_i$ on channel $c_l$ is obtained as follows:

$$\begin{array}{cc}& \chi \left(v_i,c_l\right)={{\displaystyle \sum }}_j^{\parallel \text{neigh}\_\text{nodes}\left(v_i\right)\parallel }{P}_r\left(v_i,v_j,c_l\right),\end{array}$$

(7)

where $\text{neigh}\_\text{nodes}(v_i)$ is the set of neighbor nodes of $v_i$ . At this point, each node $v_i$ can evaluate the best value of CCI associated with a particular channel:

$$\begin{array}{cc}& c_{l_{\text{MIN}}}\left(v_i\right)=\text{index}\left\{\underset{c_l}{\min }\left(\chi \left(v_i,c_l\right)\right)\right\},\\ {\chi }_{\text{MIN}}\left(v_i\right)=\underset{c_l\in \text{channels}}{\min }\left\{\chi \left(v_i,c_l\right)\right\}.\end{array}$$

(8)

The End-to-End delay between two nodes is given in (9). Here the source node is the radix of the tree; instead, the destination node is one of the nodes that belong to the set D. However, the cumulative delay is carried out considering each edge that belongs to the path between the source (s) and the considered destination (d):

$$\begin{array}{cc}& {\mathrm{\Delta }}_{s,d_j}={{\displaystyle \sum }}_{k=\mathrm{1}}^{m_j-\mathrm{1}}{\rho }_{k,k+\mathrm{1}}\mid s\in S,d_j\in D,k\in \text{Path}{\left(s,d_j\right)}_T.\end{array}$$

(9)

In order to present the LDP term $({\theta }_{s,d_j})$ , some additional terms have to be introduced, as shown in [40]. First of all we present the ${\beta }^{e_l}$ , which indicates the signal attenuation on the edge $e_l$ that it is composed of two factors:

$$\begin{array}{cc}& {\beta }^{e_l}={\beta }_{\mathrm{1}}^{e_l}+{\beta }_{\mathrm{2}}^{e_l}.\end{array}$$

(10)

The first term ${\beta }_{\mathrm{1}}^{e_l}$ is related to the distance between nodes:

$$\begin{array}{cc}& {\beta }_{\mathrm{1}}^{e_l}=\alpha \mathrm{10}\log \left(d_{xy}\right)=\alpha \mathrm{10}\log \left(\frac{a{v}_s·\tau }{L}\right).\end{array}$$

(11)

In (11), α is the evanescence exponent, which depends on the environment (generally $\alpha =4$ ), $d{}_{xy}$ is the distance among the considered couple of nodes x and y, $a{v}_s$ is the average node speed, τ is the average time lag between two vehicles, L is the number of considered lanes, and σ is a fading factor. The second term, ${\beta }_{\mathrm{2}}^{e_l}$ , is related to the fading contribution and can be considered as a random variable, normally distributed, with zero mean and ${\sigma }^{\mathrm{2}}$ variance, whose pdf is

$$\begin{array}{cc}& f\left({\beta }_{\mathrm{2}}^{e_l}\right)=\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi }\sigma }\exp \left(-\frac{{{\beta }_{\mathrm{2}}^{e_l}}^2}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right).\end{array}$$

(12)

At this point, the sensitivity of the receiver can be defined through a threshold of the attenuation level ${\beta }_{\text{th}}$ ; that is to say, a link among a couple of VANET nodes on the edge $e_l$ is still valid if ${\beta }^{e_l}\le {\beta }_{\text{th}}$ and the probability on a generic path between tree source node (s) and a generic destination (d) is presented in the following:

$$\begin{array}{l}{\theta }_{s,d_j}\\ =\frac{\mathrm{1}}{\mathrm{2}}·{\displaystyle \prod }_{k=\mathrm{1}}^{m_j-\mathrm{1}}[\mathrm{1}+\mathrm{erf}(\phantom{\underset{0}{\overset{0}{{\displaystyle \int }}}}(\phantom{{\displaystyle \sum }_0^0}{\beta }_{\text{th}}\left(k,k+\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{-\alpha \mathrm{10}\log \left(\frac{v_{k,k+\mathrm{1}}·{\tau }_{k,k+\mathrm{1}}}{L}\right)\phantom{{\displaystyle \sum }_0^0})\left(\sqrt{\mathrm{2}}·\sigma \right)\phantom{\underset{0}{\overset{0}{{\displaystyle \int }}}})}^{-1}].\end{array}$$

(13)

4.3.2. What about Mobility

The nodes mobility is considered in several terms that are involved into path discovery process. The first important concept to recall is that the neighbor discovery process is performed continuously and some dedicated messages of keep alive are sent as WSMP to know if a neighbor is still present or not. Moreover, new nodes are discovered by the neighbors discovery process and a new edge is built on the graph, allowing us to consider a new connection. In addition, since the link-duration concept is inserted in the metric, more stable paths are chosen as preferred links. This allows the system to consider mobility in terms of speed and direction updating, in a real-time manner, the weight of the edges, and adding or removing connection on the graph. So the resultant path is reliable and can distribute packets.

4.3.3. Minimum Spanning Tree (MST)

Considering QoS constraints, it is possible to define the Minimum Spanning Tree (MST) finding problem like an optimization problem as follows:

$$\begin{array}{l}\underset{x\in X}{\mathrm{Min}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}f\left(x\right)\\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}:\hspace{1em}{\mathrm{Max}}_{j=\mathrm{1}}^z\left\{{{\displaystyle \sum }}_{k=\mathrm{1}}^{m_j-\mathrm{1}}{\mathrm{\Delta }}_{k,k+\mathrm{1}}\mid k\in \text{Path}\left(s,d_j\right)\right\}\le \mathrm{\Theta }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}{\mathrm{Max}}_{j=\mathrm{1}}^z\left\{{\forall }_{k=\mathrm{1}}^{m_j-\mathrm{1}}{\chi }_{k,k+\mathrm{1}}\mid k\in \text{Path}\left(s,d_j\right)\right\}<Z\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}{\mathrm{Max}}_{j=\mathrm{1}}^z\left\{{\forall }_{k=\mathrm{1}}^{m_j-\mathrm{1}}{\theta }_{k,k+\mathrm{1}}\mid k\in \text{Path}\left(s,d_j\right)\right\}>H,\end{array}$$

(14)

where the Θ, Z, and H are the End-to-End delay, CCI, and LDP bounds, respectively. $x\in X$ are the paths between the source node and destination set along the tree $T_x$ , while X is the set of all available trees. Moreover, $f(x)$ is the objective function which has to be minimized and it is given by the following:

$$\begin{array}{cc}& f\left(x\right)={\gamma }_{\mathrm{\Delta }}·a\left(x\right)+{\gamma }_{\chi }·b\left(x\right)+{\gamma }_{\theta }·c\left(x\right).\end{array}$$

(15)

In (15) the $a(x)$ is the evaluation of the delay along the path in $T_x$ , $b(x)$ is the evaluation of the Co-Channel Interference along the path in $T_x$ , and at last the $c(x)$ is the evaluation of the LDP along the path in $T_x$ . The proposed protocol, now, has three degrees of freedom ( ${\gamma }_{\mathrm{\Delta }}$ called End-to-End delay weight, ${\gamma }_{\chi }$ called CCI weight, and ${\gamma }_{\theta }$ called LDP weight), which have to be set adequately. We know that X is the set of the found solutions (Trees); therefore, let us declare $p=|X|$ as the size of the set X. At this point, it is possible to define the $g(x)$ , $h(x)$ , and $t(x)$ as

$$\begin{array}{l}a\left(x_j\right)=\frac{\overline{\text{Delay}\left(x_j\right)}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^p\overline{\text{Delay}\left(x_i\right)}}·{\sigma }^{\mathrm{2}}\left(\text{Delay}\left(x_j\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}·\frac{{{\displaystyle \sum }}_{i=\mathrm{1}}^p\left[D_{\mathrm{Max}}\left(x_i\right)-D_{\mathrm{Min}}\left(x_i\right)\right]}{D_{\mathrm{Max}}\left(x_j\right)-D_{\mathrm{Min}}\left(x_j\right)}.\end{array}$$

(16)

In (16) the delay evaluation function is presented. It is possible to note that the solution feasibility is related to the mean value, variance, and bound values about min and max delay. In order to understand how $a(x)$ works we have to explain some utilized terms. The mean values of the solutions give us the possibility to achieve an overall evaluation, while the variance term permits to consider those solutions where the end-to-end delay is commonly closer between destinations. Last term, instead, permits to consider those solutions where the distance between the Max Delay and the Min delay is close enough that all destinations receive information into a narrowed time window. This permits to receive information avoiding that old information travelling through the network. In (17) the CCI function also called $b(x)$ is presented. In this function, we considered the mean value about the CCI along all paths between the source node and the destinations. Moreover, the difference between the minimum available CCI and the imposed bound is also considered. In the presented function, the higher is the difference, the lesser is the $b(x)$ value:

$$\begin{array}{cc}& b\left(x_j\right)=\frac{\overline{\text{CCI}\left(x_j\right)}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^p\overline{\text{CCI}\left(x_i\right)}·\left(Z-\overline{\text{CCI}\left(x_j\right)}\right)}.\end{array}$$

(17)

In (18) the LDP function is shown. It is related to the mean value of the LDP, considering all paths between source and destinations nodes. Moreover, also the constraint bound is considered, in order to evaluate the solution:

$$\begin{array}{cc}& c\left(x_j\right)=\frac{{{\displaystyle \sum }}_{i=\mathrm{1}}^p\overline{\text{LDP}\left(x_i\right)}}{\left[\overline{\text{LDP}\left(x_j\right)}·-H\right]}.\end{array}$$

(18)

The [ ${\gamma }_{\mathrm{\Delta }},{\gamma }_{\chi },{\gamma }_{\theta }$ ] is the array of the weight costs related to delay, Co-Channel Interference, and LDP function, respectively; moreover they are also a normalizing factor and therefore they follow the following law:

$$\begin{array}{cc}& {\gamma }_{\mathrm{\Delta }}={\alpha }_{\mathrm{\Delta }}·\frac{\mathrm{1}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^{p}a\left(x_i\right)},\\ {\gamma }_{\lambda }={\alpha }_{\lambda }·\frac{\mathrm{1}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^{p}b\left(x_i\right)},\\ {\gamma }_{\theta }={\alpha }_{\theta }·\frac{\mathrm{1}}{{{\displaystyle \sum }}_{i=\mathrm{1}}^{p}c\left(x_i\right)}.\end{array}$$

(19)

These weight costs have to be greater than zero and they permit to normalize the objective function components. Next section shows some considerations about them. Before observing performance evaluation, it must be said that due to the presence of mobility and wireless phenomena, some degradations are dynamically introduced into the system, so once the optimal channels have been chosen for data transmission, they have to be checked and refreshed each δ amount of time, verifying if some better conditions (in terms of channels and paths) exist.

5. Performance Evaluation

Network Simulator-2 (NS-2) has been used to integrate the proposed idea with different existing protocols. First of all, the QoS MAC of IEEE802.11e has been introduced and then it has been extended in order to include all the functionalities of the multi-channel IEEE802.11p standard. The SUMO [41] mobility generator with a user friendly GUI has been used to create mobility log files, with the following parameters: map dimensions 2000 m × 2000 m, maximum vehicle speed 15 m/s. Transmission rate has been fixed to 4 Mbps and the transmission range has been fixed to 300 meters. The number of concurrent connections has been fixed to 15. An example on how the signaling packets are changed in order to take into account the additional fields can be found in [23]. The optimal values of some simulation parameters have been determined through different campaigns of simulation.

In this work some setup campaigns have been carried out in order to find the right parameters for the route finding problem. In particular, once a scenario is defined, it is important to well design the related bounds, otherwise it will be not possible to find admissible solutions. This step is made at simulation beginning and in future works it will be studied as an automatic procedure to self-configure the bounds of the networks.

In order to evaluate the linear optimization proposal some dedicated campaigns have been carried out. In particular, we test the capabilities of algorithm to find the best solution that satisfies QoS constraints and spreads information among source and destinations. To make these campaigns we have utilized the parameters presented in Table 1 at Simulation no.1 related row.

Table 1

Simulation parameters.

Sim number	Delay bound (10−3 sec)	LDP bound (sec)	CCI bound (dB)	${\alpha }_{\mathrm{\Delta }}$	${\alpha }_{\lambda }$	${\alpha }_{\theta }$	$T_x$ rate (Mbps)	Vehicles number
1	300	40	300	1	1	1	4	40
2	300	40	300	0.6; 0.3	[ $\mathrm{0,1},\dots ,\mathrm{0,9}$ ]	[ $\mathrm{0,1},\dots ,\mathrm{0,9}$ ]	4	40
3	1100	40	300	0.6; 0.3; 0.9	[ $\mathrm{0,1},\dots ,\mathrm{0,9}$ ]	[ $\mathrm{0,1},\dots ,\mathrm{0,9}$ ]	4	[ $\mathrm{40},\dots ,\mathrm{100}$ ]

In Figures 6 and 7, the results of the simulation campaigns are shown: it is possible to observe that the more feasible solution is $x_4$ , because it represents the better combination of QoS matching requirements. In fact, the chosen solution shows a lower delay, the second higher LDP value and a CCI value that is good enough to make the solution with the higher fitness value. However, all solutions that have been carried out respect the constraints over the delay, LDP, and CCI.

Figure 6

Delay, SIR, and LDP average values versus available solutions.

Figure 7

Feasibility of the found solutions.

First addicted campaign of simulations has been carried out, considering a transmission rate of 4 Mbps, in order to evaluate protocol performance (in terms of Packet Delivery Ratio PDR and Aggregate Throughput) and different weights values $\{{\alpha }_{\mathrm{\Delta }},{\alpha }_{\chi },{\alpha }_{\theta }\}$ , belonging to the set of values $[\mathrm{0,1},\dots ,\mathrm{0,9}]$ ; see Table 1 at Simulation no.2 related row.

Figure 8 shows the trend of PDR: it is shown that, fixing the values of ${\alpha }_i$ , there are some values that lead to maximum point on the surfaces. Therefore, it can be concluded that if a higher weight is given to the interference term and to the link duration probability ( ${\alpha }_{\mathrm{\Delta }}=\mathrm{0.6}$ ; ${\alpha }_{\lambda }=\mathrm{0.7}$ ; ${\alpha }_{\theta }=\mathrm{0.7}$ ), then the system will observe a higher percentage of correctly delivered packets.

Figure 8

PDR trend for different values of ${\alpha }_i$ .

Figure 9 shows a similar trend for the average system throughput as the one shown in the previous figure. Also in this case, an optimal value can be obtained for the configuration ( ${\alpha }_{\mathrm{\Delta }}=\mathrm{0.6}$ ; ${\alpha }_{\lambda }=\mathrm{0.7}$ ; ${\alpha }_{\theta }=\mathrm{0.7}$ ), for which the maximum performance is obtained.

Figure 9

Average throughput trend for different values of ${\alpha }_i$ .

At this point, the metric of MO-RP protocol is completely defined and it can be used to evaluate the performance of the proposed protocol scheme. We compared the MO-RP scheme to classical AODV protocol, A-STAR, and DSR. Simulation parameters are the same of the previous campaign, but in this case the number of mobile vehicles change from 40 to 100.

In Figures 10 and 11, how the MO-RP outperforms the other protocols in terms of PDR is shown. Some considerations can be made about the aggregated throughput (the sum of the throughputs of all connections): introducing a composite metric, interference level and link duration are taken into account, so more stable paths are chosen, reducing the probability of packet loss and retransmissions. Therefore, this is evident when considering the percentage of correctly delivered packets and system throughput.

Figure 10

Average PDR versus the number of mobile nodes.

Figure 11

Average aggregated throughput versus the number of mobile nodes.

Referring to the overhead performance, as illustrated in Figure 12, the MO-RP protocol performs slightly worse than the other ones, due to the new signaling packets that are introduced into the network. These packets are utilized for the construction of alternative paths.

Figure 12

System overhead for 40 mobile nodes.

The introduction of new protocol messages makes the overhead (evaluated as the ratio between the number of signaling packets and the number of total packets) of MO-RP higher than classical AODV schemes.

Figure 13 shows the trend of the average End-to-End (e2e) delay observed by mobile nodes. In this case, the proposed protocol obtains the best results compared to other protocols.

Figure 13

The average e2e for the proposed protocol.

6. Conclusions

This paper proposed a new routing protocol for VANETs, dedicated to the optimization of path length, interference level, and link duration. It is based on a dynamic allocation mechanism of the DSRC spectrum, aimed at the reduction of the co-channel interference and the maximization of link duration (two key issues in vehicular environments). A new multi-objective metric, based on the evaluation of co-channel interference levels, end-to-end delay, and link duration along the different links from sources towards destinations, has been proposed and modeled through an optimization problem. Through an NS2 implementation of the IEEE802.11p standard, with the simulation of vehicles mobility in an urban environment, it has been shown that the proposed idea overcomes classical protocols performance in terms of throughput, packet delivery ratio, and end-to-end delay, despite a slight increase in protocol overhead.