Delay-aware relay selection with heterogeneous communication range in VANETs

Abstract

Vehicular ad hoc networks have been used for improving driving experiences by providing safety, efficiency and infotainment applications. Due to high mobility of vehicles, network topology changes frequently, and highly dynamic topology results in lost connection. The geographic routing protocol is used since it does not rely on the establishment of topology. With the popularity of heterogeneous wireless network links, heterogeneous communication range should be taken into consideration when selecting relay from candidate set. The greedy geographic routing protocol with the principle of selecting nearest node to destination may not ensure high packet delivery ratio and low end-to-end delay in this situation. This paper proposes a GPSR-based routing protocol called ETD-GPSR which incorporates the metric expected transmission delay (ETD) for data dissemination with heterogeneous communication range in VANETs. The neighbor table with asymmetric wireless links is established with the help of acknowledgement lists and intermediate nodes. Thus, potential good forward links overshadowed by poor reverse links can be found during the periodic beacon message exchange. Attaching each link with expected transmission delay which takes link quality, link delay and communication range into consideration, the vehicle with the minimum ETD is selected as next hop. Simulation results show that in urban environment with heterogeneous communication range, using the metric ETD has increased the packet delivery ratio and decreased the end-to-end delay.

1 Introduction

A VANET is a special case of a Mobile Ad Hoc Network (MANET) in which vehicles equipped with wireless and processing capabilities can create a spontaneous network while moving along roads [1]. Flexible rapid network can be organized by vehicles acted as both communication nodes and wireless routers. As an emerging wireless networking technology, VANETs support a variety of intelligent transportation systems applications for safety, traffic efficiency, driver assistance and infotainment [1,2,3]. All these applications require an efficient routing protocol for data forwarding between vehicles with high packet delivery ratio and low end-to-end delay. The high mobility of vehicles will cause highly dynamic topology and frequent disconnection, so efficient routing is a challenging problem.

Heterogeneous wireless networks are common in VANETs. The asymmetric obstacles in the link will cause varying degrees of forwarding signal fading and reverse signal fading. Considering the height of vehicles, experiments from [4] show that taller vehicles with higher antennas can significantly increase the effective communication range, with an improvement of up to 50 percent in certain scenarios. Furthermore, in order to facilitate the different transmitting purposes, vehicles may also be equipped with different capabilities of wireless network interfaces to provide parallel network channels for packet transmission and enhance the network performance. So it’s necessary to take heterogeneous communication range into consideration when selecting rely from candidate set.

The greedy forwarding approach may not perform well when vehicles have heterogeneous communication range. On one hand, inaccurate neighbor table is established, so transmission may suffer great packet loss. In addition, selecting the relay node at the border of communication range regardless of link quality may make the situation worse, and the retransmission will decrease packet delivery ratio and increase delay and communication overhead. On the other hand, neglecting communication range may not achieve the most one-hop message progress, thus minimum hop counts can not be guaranteed. In this paper, the ETD-GPSR is proposed to overcome these problems, the protocol incorporates the metric expected transmission delay (ETD) into greedy perimeter stateless routing (GPSR) with the estimation to the link and one-hop message progress. The neighbor table is established by adding an acknowledgement list to every beacon packet. The exchange of periodic beacon messages between vehicles with asymmetric property of wireless links is assisted by intermediate nodes without introducing any extra active probe packets in the network. A candidate set of relay vehicles can be formed by period beacon messages, the information of neighbors can be used in the calculation. Link quality is analyzed from two aspects: channel fading and channel contention. Link delay is estimated with three parts: contention delay, transmission delay and queuing delay. The metric ETD for relay scheme of routing protocol is proposed aiming to select the most adequate relay node with the minimum ETD to destination.

The rest of the paper is organized as follows. Section 2 provides an overview of the related literature. Section 3 presents the proposed protocol and Sect. 4 describes simulation experiments and simulation results. Finally, Sect. 5 concludes the paper and discusses future work.

2 Related work

Two basic strategies for data forwarding commonly adopted in multi-hop wireless networks are topology-based routing and geographic routing. Topology-based protocols use information about communication paths for packet transmission. Geographic routing protocols are suitable for VANETs since only one hop neighbors’ information is kept tract for relaying. According to the relay node selection scheme, there are two kinds of geographic routing protocols, receiver-oriented and sender-oriented. Using receiver-oriented selection scheme, the candidates compete to be next hop, different waiting time is assigned to the candidates according to their priorities, and the waiting time will increase the one hop delay. Using sender-oriented selection scheme, the sender selects the relay node from neighbor table directly.

Chuang et al. [5] used segmentation to distinguish waiting time. The road within the communication range is divided into several segmentation, faster transmitting can be achieved by allocating less waiting time to the vehicles that reside in the segmentation which are closer to the destination. Chen et al. [6] proposed a Dynamic Search-Assisted Broadcast(DSAB) protocol which dynamically adjusted the transmission power of control messages to estimate the vehicle density and appropriately adopted n-way search to find the best vehicle in the farthest segment. Redundancies and collisions will occur when vehicles at the same segmentation start broadcasting together. Yoo et al. [7] proposed the protocol called RObust and Fast Forwarding (ROFF) which allowed a forwarder candidate to use the waiting time which was inversely proportional to its forwarding priority to avoid the unnecessary delay occurred in the contention process. And it prevented the difference of waiting time from being shorter than the predefined lower bound in order to avoid collisions caused by the short difference between waiting time of forwarder candidates. In the dense urban area, collisions may still occur using ROFF.

Karp et al. [8] proposed a Greedy Perimeter Stateless Routing(GPSR) protocol which was a sender-oriented greedy forwarding geographic routing protocol. Greedy forwarding is achieved by selecting the node in the neighbor table which is nearest to destination. Due to the uneven distribution, unpredictable and variable channel of vehicles, GPSR may not perform well in VANETs. Expected Transmission Count (ETX) is a well known metric of link quality. Ohoud Alzamzami and Imad Mahgoub [9] proposed an enhanced directional greedy forwarding (DGF-ETX) based on ETX. The mechanism incorporates ETX into a multi-metric routing function used for next hop selection, which takes into account distance and direction of candidates. ETX is estimated only by the packet reception rate of periodic beacon messages without considering the mobility of vehicles. When the vehicle is driving at high speed, the inaccurate ETX may affect the performance of DGF-ETX. Dahmane et al. [10] adopted a GPSR-based routing protocol incorporating weighted link quality estimation. A probabilistic reception approximation and moving direction are combined to overcome the countermeasure caused by highly dynamic topology and unstable communication paths of VANETs. Asymmetric wireless links which may result in inaccurate neighbor problem are neglected. Zhu et al. [11] proposed the geographic routing of multilevel scenarios in VANETs. The node distribution and transmission conditions are different when the viaducts, tunnels, and ramps are taken into consideration. The proposed multilevel-scenario-oriented greedy opportunity routing protocol(M-GOR) is used to calculate the connectivity probability. Zhu et al. [12] analyzed the performance of greedy routing under the single-lane road, the multilane road, and the multilevel road. One-hop progress and routing length described by the h-hop coverage are analyzed in these scenarios. Wu et al. [13] studied the routing issue in both vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communications in VANETs, and proposed a Moving dirEction and DestinAtion Location(MEDAL) based routing algorithm, MEDAL takes advantage of the moving directions of vehicles and the destination location to select the next hop.

Wu et al. [14] proposed a path diversity mechanism, where the relay node and the auxiliary supporting node were selected to increase reliability and packet delivery ratio. The relay node is responsible for broadcasting and selecting next hop while the auxiliary node only broadcasts the message. The reliability increases at the cost of the redundancy of broadcasting. Zhang et al. [15] introduced a novel concept called link correlation, it was the influence of different link combinations in network topology. The protocol aims to transmit a packet with less network resource consumption and higher goodput. Zhang et al. [16] proposed a routing protocol based on a novel concept called the microtopology (MT) which consisted of vehicles and wireless links among vehicles along a street as a basic component of routing paths and even the entire network topology. The effect of mobility of vehicles, signal fading, wireless channel contention and existing data traffic are considered to analyze the MT model. Each vehicle is kept informed of the quality of links in the street in [15, 16], result in inducing an addition communication cost. He et al. [17] adopted a cluster based propagation strategy based on bidirectional vehicle traffic for two-dimensional VANETs in sparse VANETs, the lowest expected delay which was quantified by the analytical model of link propagation delay and link transfer delay, then the shortest-path algorithm was used for routing. Long queue of carry-and-forward messages waiting to be transmitted may further increase the overhead of cluster head.

Hosseininezhad et al. [18] took heterogeneous VANETs into consideration, they assumed that there were at least two kinds of vehicles (buses and ordinary cars) in an urban environment. In this situation, the performance can be significantly influenced by the next hop selection (buses have larger transmission range than cars). Luo et al. [19] proposed a cluster based routing protocol since vehicles moved into clusters due to traffic lights. The bus in the cluster is chosen to be the cluster head because the bus is equipped with two wireless transmission interfaces, while the ordinary car is only equipped with a single type of wireless transmission interface. There may be bottlenecks in buses because of the most communication overhead. Wang et al. [20] proposed a minimum hop counts prediction method to estimate the minimum hop counts required from each neighbor to the destination where cars and buses were used for relaying. The minimum hop counts may not ensure the minimum end-to-end delay.

3 Proposed nexthop selection mechanism

We consider that vehicles are running at the urban area with intersections. Each road segment has bi-directional vehicle traffic. Each vehicle is equipped with a locating system such as Global Positioning System (GPS) receiver for enabling the vehicle to be aware of its location. In addition, each vehicle is equipped with a digital road map for computing the distance along the road between two vehicles. Velocity and heading can be obtained from sensors in vehicles. Each vehicle can be aware of its one-hop neighbors within its communication range by exchanging periodic beacon messages. A few additional fields are added to the beacon package, and these fields are exploited to ensure accurate neighbor table and calculate the metric ETD. Assume that the vehicles in our considered environment have heterogeneous communication range. Asymmetric wireless links are considered in the establishment of neighbor table. The relay vehicle is selected by comparing the ETD of candidates. Messages are sent from source to destination by multi-hop transmission.

The proposed nexthop selection mechanism, referred to this paper as ETD-GPSR, is a distributed and sender-oriented routing protocol. The mechanism is composed of three parts, neighbor table establishment based on periodic one-hop beacon message exchange, link quality and link delay estimation and relay selection mechanism based on the metric ETD. A detailed description of components is in the subsequent sections.

3.1 Neighbor table establishment

Each vehicle maintains a neighbor table and the neighbor table is built with the help of periodic beacon messages. The neighbor table is a candidate set from which the relay node is chosen. When the vehicle receives beacon messages from its neighbor vehicles, the information of neighbor vehicles is added to its neighbor table [10]. This method works well when vehicles have the same communication range. As in Fig. 1, heterogeneous communication range is taken into consideration, vehicle $V_{A}$ has communication range $r_{\scriptscriptstyle A}$, vehicle $V_{B}$ has communication range $r_{\scriptscriptstyle B}$, $r_{\scriptscriptstyle A}$ is bigger than $r_{\scriptscriptstyle B}$ and $V_{A}$ is beyond $r_{\scriptscriptstyle B}$ while $V_{B}$ is in $r_{\scriptscriptstyle A}$. In this situation, using the method mentioned before, $V_{A}$ is in the neighbor table of $V_{B}$ and $V_{B}$ is not in the neighbor table of $V_{A}$, but the fact is reverse. We call the vehicle like $V_{A}$ the mistaken relay vehicle and $V_{B}$ the missed potential relay vehicle. In asymmetric wireless links situation, good performance of forward links may not represent good reverse links and poor reverse links may overshadow the good performance of forward links.

Fig. 1

Vehicles with heterogeneous communication range

The acknowledgement and the intermediate vehicle are used to solve the inaccurate neighbor table problem in asymmetric communication. The acknowledgement is used to solve the mistaken relay vehicle problem, the neighbor is added to neighbor table until the vehicle receives the acknowledgement of its beacon messages from the neighbor. $l_{ack}$ is a acknowledgement list as a part of the beacon package which keeps tract of vehicles from which beacon messages are received. When vehicle $V_{A}$ receives a beacon message from $V_{B}$, then $V_{B}$ is added to the $l_{ack}$ of $V_{A}$. Then $V_{B}$ receives a beacon message from $V_{A}$ and $V_{B}$ is included in the $l_{ack}$ of this beacon message, $V_{A}$ is added to the neighbor table of $V_{B}$.

The intermediate vehicle is used to solve the missed potential relay vehicle problem by assisting the vehicles in forwarding the acknowledgement list. In Fig. 2, when $V_{B}$ receives a beacon message from $V_{A}$, $V_{A}$ is added to the $l_{ack}$ of beacon message of $V_{B}$. There may be a low possibility for $V_{A}$ to receive beacon messages from $V_{B}$ due to out of communication range. Intermediate vehicle $V_{I}$ which connects well with both $V_{A}$ and $V_{B}$ will assist in completing the course of beacon message exchange between $V_{A}$ and $V_{B}$. That is, $V_{I}$ is neighbor of $V_{A}$ and $V_{B}$, and $V_{A}$ and $V_{B}$ have a neighbor $V_{I}$, then $V_{I}$ will help $V_{B}$ to broadcast the information of $V_{B}$ to $V_{A}$.

Fig. 2

Neighbor sensing assisted by the intermediate vehicle

The beacon packet format is represented in Table 1. The vehicle ID, position, velocity, heading, communication range and acknowledgement list are compulsory in the beacon packet. The missed vehicle list is optional in the beacon packet. The optional part is only included in beacon packet of the intermediate vehicle which is consisted of a list of missed potential relay vehicles’ information ($l_{mv}$). The acknowledgement list ($l_{ack}$) contains a list of vehicle IDs. Vehicle ID can be abstracted from the received beacon message. The information of the missed vehicle contains vehicle ID, position, velocity, heading, communication range and acknowledgement list. The missed vehicle list ($l_{mv}$) contains a list of the missed potential relay vehicles. When a vehicle receives a beacon message which is from an intermediate vehicle, the acknowledgement list is checked to find whether it is a neighbor, then the missed vehicle list is checked to find whether the missed vehicle is existed.

The size of vehicle ID, position, velocity, heading, communication range is shown is Table 1, the size of acknowledgement list is decided by the vehicle density , the size of missed vehicle list is influenced by the ratio of vehicles with different communication range.

Table 1 Format of beacon packet

For each vehicle in the network, a neighbor table is required to keep tract of neighbor’s information to have a knowledge of the status of the neighbor. Format of neighbor entry is showed in Table 2. The information like position, velocity, heading, communication range will be used in the calculation in relay selection. Neighbor information source is 0 if the neighbor is the missed vehicle, else it is 1. Timestamp of operation is the timestamp of updating operation to the entry which is used to check whether the neighbor entry is valid. The acknowledgement list is tracked to discover asymmetric wireless links and whether the vehicle should act as an intermediate vehicle or not.

The beacon packet is generated periodically by vehicles at a frequency of $\tau$, $\tau$ is 0.1 s. A neighbor entry is deleted from the neighbor table when the neighbor entry has not been updated for $5\tau$. For the missed relay vehicle, the exchange of beacon message is assisted by the intermediate vehicle, the maximum period of beacon exchange is $2\tau$. If the neighbor entry has not been updated for more than two periods, then it is deleted. The speed in the urban environment is restricted by the speed limit, 50 km/h for example, the maximum distance between two vehicles in $5\tau$ is increased by 13.89 m, it is a tolerable distance. So that if some beacon messages are lost or delayed due to collisions or congestions in the network, the neighbor entry will not be removed immediately from the neighbors table because it could be a suitable forwarder.

Table 2 Format of neighbor entry

When a vehicle receives a beacon message, the acknowledgement list will be checked to discover whether it is a neighbor. If it is a neighbor, then adding or updating operation will be done in neighbor table. If the beacon message contains the missed vehicle list, the information of missed vehicles is checked to find the potential neighbor. When a vehicle is an intermediate vehicle, it takes responsibility to assist the process of beacon packets exchange. Each vehicle runs the algorithm periodically in Algorithm 1 to discover whether it is an intermediate node. The asymmetric wireless link is firstly discovered and next step is to check whether asymmetric communication has been assisted by an intermediate node for decreasing network overhead.

3.2 Link estimation

We estimate the link between two vehicles from two aspects, link quality and link delay. The quality of a communication link depends essentially on the path attenuation factor and contention of wireless channel. The delay of a communication link depends on contention delay, transmission delay and queuing delay.

• 1. Channel fading: the $Nakagami{\text {-}}m$ distribution with parameter m is used to describe the fading of radio wave propagation. Referred from [21], the successful transmission probability against channel fading can be obtained as follows:

  $$\begin{aligned} \begin{aligned} P_f(x>R_{x})&=1-F_{d}(R_{x};m,\varOmega )\\&=e^{-(mR_{x}/\varOmega )\sum \limits _{i=1}^{m}\frac{((m/\varOmega )R_{x})^{i-1}}{(i-1)!}} \end{aligned} \end{aligned}$$

  (1)

  where $F_{d}(R_{x};m,\varOmega )$ represents the cumulative density function of receiving signal power, $R_{x}$ is the reception threshold of a signal, $\varOmega$ is an average reception power and m denotes the fading parameter. The value of fading parameter m is decided by the distance of two vehicles [16]. $R_{x}$ is the reception threshold of a signal with communication range $r_{c}$, it can be expressed as follows:

  $$\begin{aligned} \begin{aligned} R_{x}=\frac{P_{t}G_{s}G_{r}h^{2}_{s}h^{2}_{r}}{r^{4}_{c}} \end{aligned} \end{aligned}$$

  (2)

  $P_{t}$ is the transmission power,$G_{s}$ is the antenna gains of the sender, $G_{r}$ is the antenna gains of the receiver, $h_{s}$ is the height of the sender antenna, $h_{r}$ is the height of the receiver antenna, $r_{c}$ is the communication range of the vehicle. Assuming that the height of the bus is 3 m, the height of the car is 1.5 m, the communication range of the bus is $r_{bus}$, the communication range of the bus is $r_{car}$, for the same $R_{x}$, $r_{bus}=\sqrt{2}r_{car}$.

• 2. Channel contention: denote $p_{b}$ as the probability that the channel is sensed busy, denote $q_{i}$ as the steady state probability that the packet service time is $i\sigma$ ($\sigma$ is a time slot), let Q(z) be the probability generating function of $q_{i}$. We refer the result in [21]:

  $$\begin{aligned} \begin{aligned}&p_{b}=1-e^{-2p_{0} n_{cs}/(w_{0}+1)}\\&Q(z)=\sum \limits _{i}{q_{i}z^{i}} =\frac{z^{\left\lfloor \frac{T(p)}{\sigma } \right\rfloor }}{w_{0}} \sum \limits _{i=0}^{w_{0}-1}{G^i(z)} \end{aligned} \end{aligned}$$

  (3)

  where $p_{0}$ is the probability that there exists a transmission on a vehicle, which can be obtained by iteration of Q(z), $n_{cs}$ is the number of vehicles with packets in the buffer in the carrier sensing area, the network density is $\rho$, and $n_{cs}=2\rho r_{c}$, $w_{0}$ is the size of contention window. T(p) is the required time for the entire transmission of packet p. G(z) is the probability generating function of transition for backoff counter decremented by one, $G(z) = (1-p_{b})z+p_{b}z^{\lfloor \frac{T}{\sigma } \rfloor }$, T is the suspending time period of backoff timer. Then the successful channel access probability and service time which contains contention delay and transmission time can be obtained based on the Eq. (4).

  $$\begin{aligned} \begin{aligned} P_c&=1-p_{b}\\ D_c&=Q^{'}(z)|_{z=1} \end{aligned} \end{aligned}$$

  (4)

• 3. Queuing delay: the queuing delay of a packet is the time when the packets in the buffer has been served. As referred in [16],we can get queuing delay as follows:

  $$\begin{aligned} \begin{aligned} D_{q}=\sum \limits ^{p\in buf}\frac{l_p}{\mu } \end{aligned} \end{aligned}$$

  (5)

  where p is the packet in buffer, $l_p$ is the packet size of p, $\mu$ is the service rate, $\mu$ can be obtained by the iteration of Q(z). Therefore, we can get the link quality and the link delay as follows:

  $$\begin{aligned} \begin{aligned} P_{l}&=P_{f}\times P_{c}\\ D_{l}&=D_c+D_{q} \end{aligned} \end{aligned}$$

  (6)

3.3 Relay selection mechanism with the metric ETD

For each link from packet-carrying vehicle to candidates, we can get the expect delay ($E(D_{l})$) as follows:

$$\begin{aligned} \begin{aligned} E(D_{l})=\frac{D_{l}}{P_{l}} \end{aligned} \end{aligned}$$

(7)

Since in VANETs with heterogeneous communication, the communication range of candidates have an great influence on one-hop message progress. The relay node with larger communication range may result in less hop counts and end-to-end delay. So we propose a metric ETD (expected transmission delay) which combines the expect delay and communication range, it is used to estimate the delay from current packet-carrying vehicle to destination. The candidate with minimum ETD will be chosen as the relay node.

$$\begin{aligned} \begin{aligned} ETD=E(D_{l}) \times \left( \frac{d_{cd}}{r_{c}}+1\right) \end{aligned} \end{aligned}$$

(8)

where ${d_{cd}}$ is the shortest distance from the candidate to destination along the road which can be obtained using Dijkstra algorithm, $r_{c}$ is the communication range of the candidate, $\frac{d_{cd}}{r_{c}}+1$ is the estimated hop counts.

At first, the candidate set is formed by the exchange of beacon messages, then the ETD of links from the current vehicle to the candidates is compared to find the candidate with minimum ETD. The relay node selection algorithm is showed in Algorithm 2.

4 Simulation and results

We evaluate the performance of ETD-GPSR and compare it to weighted probabilistic next-hop forwarder decision-making (P-GPSR) [10]. P-GPSR is an opportunistic routing protocol which takes link quality and link stability into consideration. Compared with P-GPSR, the advantages of ETD-GPSR in heterogeneous communication range can be easily discovered.

4.1 Simulation scenarios

ETD-GPSR is simulated using NS-2.35 as a network simulator, while the urban traffic mobility is simulated using VanetMobiSim. A Manhattan grid is used to model a common road network for an urban scenario formed by streets and crossroads. The size of the road network is $3\times 3$ where the length of each road segment is 1 km. To make the simulation more realistic, we use VanetMobiSim to generate the movement of vehicles that is restricted by the road network. Table 3 shows the simulation parameters.

Table 3 Format of neighbor entry

We assume that there are two types of vehicles, taking ordinary cars and buses for example. The transmission range for the two types of vehicles are $r_{car}$ (250 m) and $r_{bus}$ (350 m) respectively. The vehicle density in our simulations is given as 10 car/km, 15 car/km, 20 car/km and 25 car/km. There are two scenarios where the number of ordinary cars versus the number of buses is set as 4:1 and 9:1. The simulation is carried out using the IEEE 802.11p standard implementation for physical and MAC layer, the channel data rate is 6 Mb/s. Periodic beacon messages are utilized to iterate the one-hop information with an interval of 0.1 s. The interval of 0.1 s can ensure the real-time neighbor information without causing congestion. Constant Bit Rate (CBR) emits fixed-size packets of 512 bytes for every 0.5 s.

At first, we evaluate the overhead of beacon messages of the proposed method. Then in order to evaluate the performance of our proposed method against the routing protocol P-GPSR, we investigate performance factors (the packet delivery ratio, average end-to-end delay) in the above two simulation scenarios. Packet delivery ratio represents the ratio of packets that are successfully received by CBR destinations. Average end-to-end delay represents the average delay of packets that are successfully delivered from source vehicles to destination vehicles. Each simulation instance is simulated 30 times and then we take the average of the resulting values.

4.2 Simulation results analysis

Figure 3 shows the average overhead of beacon messages for the vehicle in the simulation time when the number of ordinary cars versus the number of buses is set as 4:1 and 9:1. As vehicle density increases, the size of the beacon package increases due to the increase of the acknowledgement list. Compared to 9:1, when the number of ordinary cars versus the number of buses is 4:1, there are more asymmetric links caused by heterogeneous communication range, the size of the beacon package increases due to the increase of the missed vehicle list.

Fig. 3

Average overhead of beacon messages

Figures 4 and 5 show the packet delivery ratio and average end-to-end delay where the number of ordinary cars versus the number of buses is set as 4:1. In Fig. 4, an increase density in the network results in an increase in the network connectivity, which increases the opportunities for packets to find out the next hop and reduces the packet-dropping rate due to a case of encountering the network partition. Thus, the packet delivery ratio of the two protocols increases as the number of vehicles increases. When the network density is sparse, the connectivity of the network topology mainly restricts the successful delivery of packets from the source to destination. Thus, the packet delivery ratio increases quickly as the density of vehicles increases from 10 to 15 car/km. Compared to P-GPSR, ETD-GPSR not only considers signal fading , but also estimates the contention of the link, and ETD-GPSR is more likely to choose bus as relay node so ETD-GPSR outperforms P-GPSR.

Fig. 4

Packet delivery ratio for varying vehicle densities where ordinary cars versus the number of buses is set as 4:1

In Fig. 5, an increase in network density results in selecting the relay node with more one-hop message progress and decreasing hops from source to destination. Thus, the average end-to-end delay of the two protocols decreases with an increase in the numbers of vehicles. When the density of vehicles is sparse, the connectivity of the network topology mainly restricts the end-to-end delay. Thus, the density of vehicles increases from 10 to 15 car/km, the average end-to-end delay decreases quickly. ETD-GPSR outperforms P-GPSR because the communication range and link delay have been taken into consideration when selecting the relay node. ETD-GPSR is more likely to choose the bus as next hop and the end-to-end delay decreases.

Fig. 5

Average end-to-end delay for varying vehicle densities where the number of ordinary cars versus the number of buses is set as 4:1

Figures 6 and 7 show the packet delivery ratio and average end-to-end delay for varying the number of vehicles where the number of ordinary cars versus the number of buses is set as 9:1. The packet delivery ratio of ETD-GPSR and P-GPSR in Fig. 6 is lower compared to the results in Fig. 4. The decrease of the number of bus may cause the increase of hop count which leads to the increase of probability of package loss.

Fig. 6

Packet delivery ratio for varying vehicle densities where ordinary cars versus the number of buses is set as 9:1

In Fig. 7, the overall average end-to-end delay increases compared to the results in Fig. 5 since the decrease of the number of bus has influence on the hops from source to destination. The advantage of ETD-GPSR has been reduced but it still outperforms P-GPSR because the contention delay, queuing delay and transmission delay are well utilized to estimate the delay of one hop.

Fig. 7

Average end-to-end delay for varying vehicle densities where the number of ordinary cars versus the number of buses is set as 9:1

Overall, the results confirm that the relay selection mechanism using ETD as metric for routing in VANETs with heterogeneous communication range leads to a better selection of next-hop nodes for increasing the packet delivery ratio and decreasing the average end-to-end delay.

5 Conclusion

In this paper, we propose a GPSR-based routing protocol called ETD-GPSR which incorporating with the metric expected transmission delay (ETD) for data dissemination with consideration of heterogeneous communication range in VANETs. ETD-GPSR is simulated using NS-2.35 as a network simulator and VanetMobiSim as a traffic simulator. The overhead of beacon messages is evaluated, and then it is compared with P-GPSR. Our simulation results show that ETD-GPSR outperforms P-GPSR in urban environments. Our proposed protocol, ETD-GPSR shows performance improvement in terms of PDR and average end-to-end delay over P-GPSR. In the future, the packet size of beacon packet and frequency of beacon packet will be taken into consideration to reduce the communication overhead [22].