Sage Journals: Discover world-class research

Abstract

To support smart and converged services for autonomous vehicles, reliable vehicular ad hoc networks play important roles. To achieve this goal, this article proposes an application-layer overlay platform for hyper-connected vehicular ad hoc networks. By effectively exploiting redundancy of communication among vehicles and infrastructures on the road, this article aims to provide reliable communications among vehicles with high performance. Furthermore, the proposed approach is built at the application layer, and hence, it is compatible with existing routing protocols. Also, it minimizes communication and computation overheads. To verify the proposed scheme, we evaluate performance of the proposed approach compared with existing routing protocols.

Keywords

Smart vehicles hyper-connected vehicular ad-hoc network overlay application layer

Introduction

Recently, there have been emerged various types of vehicular applications and services such as safety-related vehicle messaging, traffic and congestion monitoring, road side convenience and commercial applications. Furthermore, with emergence of smart and converged services for autonomous vehicles, there has been rapid increase in the need for smart and hyper-connected vehicles. To support such reliable communication among vehicles and infrastructures, reliable vehicular ad-hoc networks (VANETs) play important roles in public safety communications and commercial vehicular applications.

VANET is a specialized form of mobile ad-hoc network (MANET). In traditional MANETs, nodes are usually moving in a random way. However, VANET nodes are vehicles or road side units (RSUs). Most vehicles in VANETs move faster than the mobile nodes in MANETs and they are restricted in the range of motion because they are supposed to follow roads. Also RSUs are most likely stationary and their locations are pre-known. Due to this environmental difference, simply applying MANET routing protocols to VANETs has fundamental limitations. The unique features of VANETs significantly affect the reliability and performance of existing MANET routing protocols.

To overcome these limitations, many researchers have devoted their efforts to build reliable VANETs.^1–11 However, all of these previous studies either rely on static information in advance (e.g. street map and bus routes) or they use very complex algorithms for route decision with a large amount of overheads. Furthermore, each algorithm has its own advantages and drawbacks at the same time depending on its target environments and applications.

To address such limitations, this article proposes an overlay-based VANET routing protocol by effectively exploiting redundancy of communication among vehicles and infrastructures on the road. Specifically, the proposed overlay-based VANET routing protocol is an application-layer method built on top of existing VANET protocols. When transmission failure has been detected, a node attempts to detour the problematic neighbors by explicitly reselecting alternative neighbors based on various metrics such as distance, neighbor history, and/or mobility. The key ideas and design goals behind the proposed approach are summarized as follows:

Compatible with existing protocols. The proposed routing protocol is built at the application layer without requiring modification of underlying protocols such as routing, MAC, and physical layer protocols at all. This implies that the proposed overlay-routing protocol can adaptively accommodate dynamic changes in traffic condition and application-dependent needs.

Effective in utilizing network redundancy. The proposed scheme re-sends the dropped packets along the alternative path detouring problematic nodes. To effectively avoid the failed link and identify the alternative path for retransmission, we develop a multi-criteria decision-making methodology. In this methodology, we define four criteria (i.e. the certainty, distance, diversity, and randomness) for effective overlay construction.

Minimizing communication and computation overhead. The proposed overlay-routing procedure is activated only when the primary path fails. It uses location and time-stamp information of neighbor nodes, which are generally provided at underlying protocols without causing extra messages. As a consequence, the proposed protocol incurs little computation and communication overhead.

The rest of this article is organized as follows. In the next section, concepts of VANETs and overlay structures are summarized. In the following, the proposed application-layer overlay platform is introduced with detailed algorithms. Afterwards, evaluation results compared to other studies are presented with in-depth analysis. Finally, we wrap up the article with conclusion.

Related works

VANET

VANET is an advanced form of MANET. In MANET, nodes are usually mobile or tablet devices. However, nodes in VANET are vehicles or RSUs. Due to this environmental difference, applying MANET routing protocols to VANET has fundamental limitations and hence might cause bad performance in VANET environment. Reflecting such problems, there have been many studies about VANET routing protocols.^1–12

Most VANET routing algorithms are either topology-based or geography-based. Due to its simplicity, geography-based routing has been proved to be more suited for VANET. The geography-based routing schemes are usually classified into three categories: (1) delay tolerant network (DTN), (2) non-DTN, and (3) hybrid methods. Geographic routing methods usually use position information from global positioning system (GPS) sensors. Geographic source routing (GSR),⁶ greedy perimeter stateless routing (GPSR),⁷ and greedy perimeter coordinator routing (GPCR)⁸ are representative non-DTN routing protocols. Especially in GPSR, each node forwards the packets to the neighbor node closest to the destination using geographic information, which is called greedy forwarding. If a node fails to forward the packets using this scheme, it turns into a perimeter mode. In this mode, a node makes a graph consisting of neighbor nodes and sends the packet along the graph following a left-hand rule algorithm. GPCR’s main idea is to take advantage of the fact that streets and junctions form a natural planar graph. And it does not require any global or external information compared to GPSR. The most critical issue in such location-based approaches is that all nodes in VANET environment including source, destination, and forwarding nodes can move dynamically at a high speed. Hence, the positional information of destination node might need to be propagated by neighbors to all nodes at short intervals. There are two ways to notify the positional information of the destination node as shown in Figure 1. However, both solutions can cause packet congestion at the cost of location accuracy. Also, these geography-based algorithms have inherent limitations in the sense that packets cannot be delivered due to network disconnection or partition under low traffic density. To overcome these limitations, DTN-based methods have been proposed. DTN protocols such as vehicle-assisted data delivery (VADD)⁹ and geographical opportunistic routing (GeOpps)¹⁰ are basically carry-and-forward mechanisms at the cost of end-to-end delay. In VADD method, a moving vehicle carries a packet and wait until a new vehicle moves into its vicinity. To reduce the delay, VADD uses a predictable vehicle mobility model based on traffic patterns and road layouts. However, GeOpps utilizes navigation systems built on vehicles to select the next hop for forwarding. Specifically, it forwards the packet to the vehicle which is likely to move closer to the destination.

Figure 1.

Methods of finding the location of a destination node. (a) Method_A: a source node inquires a destination’s location by broadcasting the request. (b) Method_B: Each node periodically announces its own location to the server.

In addition, there have been another type of studies relying on broadcasting and multi-casting mechanism, in which a source node uses a flooding scheme to send data packets for reliable and fast delivery. For example, in least common neighbor (LCN)¹¹ protocol, each node keeps the list of neighbor nodes. The node with the LCN list is determined as a rebroadcast node to reduce flooding overheads.

However, all of these previous studies either rely on static information in advance (e.g. street map, bus routes, etc.) or they use very complex algorithms for route decision with high overhead. Furthermore, each algorithm has its own advantages and drawbacks depending on its target environments and applications.

Motivated by these observations, this article proposes an application-based overlay VANET routing protocol, which aims to provide better packet delivery rate (PDR) and end-to-end delay by exploiting advantages of existing underlying protocols.

Overlay network

An overlay network is a virtual network on top of a physical network. Each virtual link between overlay nodes consists of several physical links.¹³Figure 2 shows the hierarchical layer of an overlay network, which is logically formed over a physically connected network. Many studies in VANET adopted the concept of overlay networks for various applications.^14–17 Some of them^14,15 have been considered as overlay VANET routing protocols in the sense that these previous studies choose landmarks or junctions as relay nodes and guide packets to traverse via the relay nodes. To effectively discover such overlay paths, these studies developed various algorithms using traffic density, the city map, transportation route information, and so on.

Figure 2.

Overlay network.

Also, several studies^16,17 develop overlay networks for peer-to-peer information retrieval. In particular, these studies focus on cooperative data sharing among nearby vehicles to reduce bandwidth overuse and to minimize redundant information. To do this, these studies propose that the nearby vehicles construct overlay networks for effective information lookup and dissemination.

In contrast to these previous studies, this article adopts the concept of overlay platforms to construct an application-layer VANET protocol. The proposed overlay protocol has several unique features compared to the above previous studies. First, we develop overlay networks to take full advantage of network redundancy of existing networks for more reliable packet delivery. In this article, the proposed overlay-based method attempts to re-send packets along an alternate path when the current primary path becomes unavailable or suffers from congestion. Second, we build overlay networks at an application layer on top of underlying routing protocols, which implies that we use one of the existing VANET routing protocols underneath overlay networks. These features give us more chance to exploit the advantages of the above existing VANET protocols and to complement their drawbacks using the proposed overlay networks.

Application-layer overlay-routing protocols for VANETs

Although many studies have been presented for VANETs, routing in VANETs is a still challenging task due to rapidly changing topology and high-speed mobility of vehicles. To complement the limitations of existing routing protocols, we develop an application-layer overlay-based VANET routing protocol on top of existing physical layer routing protocols.

In what follows, we present challenges to solve and propose detailed algorithms to address the identified problems.

Problem statement

Figure 3 shows the problem of existing VANET routing protocols under the vehicular communication scenario and how the proposed overlay protocol addresses this issue.

Figure 3.

Overlay scenario.

In this example, $nod e_{0}$ is a source node and $nod e_{9}$ is a destination. The first hop (i.e. $nod e_{1}$ ) originally tried to forward the packet to the second hope (i.e. $nod e_{2}$ ). But the packets have been dropped due to some reasons such as collision or network disconnection (i.e. the neighbor node becomes out of communication range). In the detection of such forwarding failure, although there is another alternative route through $nod e_{6}$ represented in a dotted line, the existing routing protocols do not effectively utilize this alternative route.

Motivated by this observation, the proposed overlay-routing mechanism is developed at an application layer to explicitly utilize redundancy of VANET connections to detour the problematic area and pursue more reliable packet delivery.

Overlay-routing algorithm

We illustrate the idea of the proposed application-layer overlay VANET protocol using the example in Figures 3 and 4. In this scenario, $nod e_{0}$ and $nod e_{9}$ are source and destination nodes, respectively, and all vehicles are moving. The detailed procedure for this example is as follows.

Step 1. When $nod e_{1}$ receives a packet from $nod e_{0}$ , it attempts to forward the packet to $nod e_{2}$ , which is selected by an underlying routing protocol. However, since $nod e_{2}$ moves up and so goes out of transmission range at this time, $nod e_{1}$ fails in sending the packet to $nod e_{2}$ .

Step 2. In the proposed approach, $nod e_{1}$ transfers the packet up to the application layer of itself, then it triggers an overlay routing.

Step 3. It then selects an overlay node, which can be one hop or multi-hop away from it. In this example, $nod e_{1}$ chooses $nod e_{6}$ as an overlay node.

Step 4. Once an overlay node is selected, $nod e_{1}$ sends the packet to the selected overlay node through underlying a routing protocol. In this example, the packet travels through $nod e_{1}$ to $nod e_{6}$ via $nod e_{5}$ . Note that the underlying routing from $nod e_{1}$ to $nod e_{6}$ is operated by GPSR in this example.

Step 5. When node₆’s application layer receives the packet, it examines the packet header and finds out that the packet is originally destined to $nod e_{9}$ , not $nod e_{6}$ . Then, it triggers an overlay routing again and sends it to the final destination node, $nod e_{9}$ . Note that the underlying routing from $nod e_{6}$ to $nod e_{9}$ is also operated by GPSR in this example.

Figure 4.

A packet traverse flow through protocol stacks for Figure 3 example.

Specifically, in step 1, the proposed overlay method triggers $nod e_{1}$ to forward this dropped packet up to the application layer of itself and the application layer overlay-routing module on $nod e_{1}$ searches the alternative overlay path. The alternative overlay path is represented as a dotted line in Figure 4. The selected next overlay node can be either the direct neighbor of $nod e_{1}$ or a multi-hop away node. In this example, $nod e_{1}$ selects $nod e_{6}$ as the alternative next overlay node. Then, $nod e_{1}$ stores the original destination (i.e. $nod e_{9}$ ) in an overlay packet header and changes the destination information of an IP header into $nod e_{6}$ . Then, $nod e_{1}$ transmits this packet destined to $nod e_{6}$ via one of its direct neighbors (i.e. $nod e_{5}$ in this example). When $nod e_{6}$ receives the packet, it checks the overlay packet header to find out its original final destination. Then, $nod e_{6}$ recovers the destination of the IP header to $nod e_{9}$ and transmits the data to the original final destination. Overall, the proposed method can detour the problematic link and use an alternative path by exploiting an overlay network. Detailed procedure of the overlay-routing mechanism is described in Algorithms 1 and 2.

Algorithm 1. Application-layer procedure for overlay routing.
1: if destination_node == me then 2: if no hidden_dst then 3: process the packet 4: else then 5: destination_node = hidden_dst 6: transfer the packet to the RTR layer 7: end if 8: else then 9: hidden_dst = destination_node 10: select an overlay node to forward the packet 11: if overlay node is available then 12: destination_node = the selected overlay node 13: transfer the packet to the RTR layer 14: else then 15: drop the packet 16: end if 17: end if

Algorithm 1. Application-layer procedure for overlay routing.

1: if destination_node == me then
2: if no hidden_dst then
3: process the packet
4: else then
5: destination_node = hidden_dst
6: transfer the packet to the RTR layer
7: end if
8: else then
9: hidden_dst = destination_node
10: select an overlay node to forward the packet
11: if overlay node is available then
12: destination_node = the selected overlay node
13: transfer the packet to the RTR layer
14: else then
15: drop the packet
16: end if
17: end if

Algorithm 2. MAC layer procedure for overlay routing.
1: when fail to forward the packet 2: if retransmission_count < limited_count 3: then send the packet to next hop 4: else 5: then transfer the packet to the application layer of itself

In this algorithm, there are two main issues to be addressed: (1) how to select overlay nodes and (2) how to maintain overlay-related information. In the next two subsections, we answer these questions in detail.

How to select overlay nodes?

Selection of an overlay node is one of the main issues in the proposed method. RSUs and even moving vehicles can be overlay nodes. RSUs can be classified as static overlay nodes because their positions are fixed. However, vehicles including buses and trams with pre-known routes are mobile and so they are called as dynamic nodes.

It is easily expected that using a static RSU as an overlay node is more reliable. However, a static overlay node can be a bottleneck and so it can cause congestion around itself. As a consequence, the packet destined for the selected static overlay node can be dropped again making the situation even worse. Furthermore, there is a possibility that any static node is not available or the information of static nodes is not delivered to the failed node. In this situation, the failed forward node cannot build an overlay path through a static overlay node to the final destination. Note that the proposed approach does not construct overlay paths a priori. Only if the primary path becomes unavailable or fails, the forwarding node attempts to build an overlay path on the fly. Overall, an overlay node with a static position is considered more reliable than a dynamic node, while the static overlay node can be a single point of failure as a bottleneck in a congested network.

In contrast, a dynamic overlay method can have a large variety of overlay node choices because vehicles in the vicinity or buses with pre-known routes can be the overlay nodes. This feature can prevent the bottleneck problem of a static overlay scheme. However, the position of a dynamic node is not accurate because its position is not fixed and keeps changing.

Considering all things, we propose the hybrid overlay-routing method that combines the two aforementioned types of overlay nodes. In the proposed hybrid scheme, a forwarding node can adaptively choose either a static or dynamic overlay node with considering its traffic conditions and surrounding environment.

Specifically, the proposed approach constructs an overlay network considering the following requirements.

Certainty: to successfully transfer the packet to the overlay node, the current position of the overlay node should be accurately informed.

Variance: to avoid failed links, the overlay node should be diverse from the failed primary path.

Distance: the closer an overlay node is, the more successful packet delivery is.

Randomness: to prevent a single point of failure, selection of an overlay node should have randomness feature.

To satisfy the first requirement, each node tends to select an overlay node whose location information is the most up-to-date. Choosing static nodes such as RSUs would be one extreme. Selecting currently or immediately preceding neighbors as overlay nodes might be also suitable solution because location information of these recent neighbors are relatively more up-to-date than aged previous neighbors. Respecting the second requirement, each node considers additional mobility information such as its current location, moving direction, speed, or its pre-known route, if available. Using such high-level information, it can choose an overlay node which is diverse from the problematic area. For the third condition, we prefer the closely located overlay nodes to the far-most ones Finally, the proposed hybrid overlay algorithm attempts to avoid the bottleneck situation by balancing the traffic load among overlay nodes.

Note that the above conditions might conflict with each other and so we need to develop a solution to handle mult-objective problems. To do this, we adopt the concept of Skyline operator.¹⁸ Skyline operator is mainly used to make intelligent decisions over complex data with multiple requirements. Skyline analysis is known to be a very useful tool for multi-criterion decision-making in various range of applications including database¹⁹ and mobile networks.²⁰

In this article, the Skyline operator computes the “Skyline,” which is a set of selected overlay candidate nodes. Each overlay node $n_{a}$ is denoted as a tuple $p_{a} = (C_{a}, V_{a}, D_{a})$ . In this article, $C_{a}$ , $V_{a}$ , and $D_{a}$ are dimensions which are criteria used to identify a set of overlay candidate nodes. Specifically, $C_{a}$ , $V_{a}$ , and $D_{a}$ are correspondent to metrics for aforementioned conditions: certainty, variance, and distance, respectively. Using these conditions, we first form a Skyline list (i.e. a set of overlay candidates). When the Skyline list is identified, we randomly select the overly node out of the Skyline list to reforward the failed packets with avoiding the problematic primary path.

This article tentatively formulate $C_{a}$ , $V_{a}$ , and $D_{a}$ as below. Note that this formulation can be further extended and modified depending on target area and its environment.

C_{a} = {\begin{matrix} 1 & if n_{a} is stationary \\ 1 / t_{age} & else if t_{age} < age_threshold \\ 0 & otherwise \end{matrix}

(1)

V_{a}^{b, c} = \arccos (\frac{\vec{ab} \cdot \vec{bc}}{| | ab | | \cdot | | bc | |)})

(2)

D_{a} = distance to an overlay node n_{a}

(3)

where $t_{age} = tim e_{current} - ti m_{stamp}$ and $V_{a}^{b, c}$ is defined to measure diversity between an overlay path through $n_{a}$ and a failed previous path through a neighbor node $n_{c}$ from a forwarding node n_b’s point of view.

With these multi-criteria, we check whether or not an overlay node $n_{a}$ is “much better” than the other overlay node $n_{a'}$ . To do this, we formulate preference and indifference relations²¹ between node $n_{a}$ and $n_{a'}$ as follows

aP a'_{certainty} if C_{a} - C_{a'} > certaint y_{pref}

(4)

aP a'_{distance} if D_{a'} - D_{a} > distanc e_{pref}

(5)

aI a'_{certainty} if C_{a} - C_{a'} < certaint y_{indiff}

(6)

aI a'_{distance} if D_{a'} - D_{a} < distanc e_{indiff}

(7)

where $aP a'_{certainty}$ , $aP a'_{distance}$ , $aI a'_{certainty}$ , and $aI a'_{distance}$ are preference and indifference relations of certainty and distance requirements. And $certaint y_{pref}$ , $certaint y_{indiff}$ , $distanc e_{pref}$ , and $distanc e_{indiff}$ are thresholds for these four preference and indifference relations. Note that we use a diversity requirement, $V_{a}$ as a veto element, that is, if the diversity of the target overlay node $n_{a}$ is less than the veto threshold, we exclude $n_{a}$ from our Skyline list regardless of other criteria.

With respect to these preference and indifference relations, the node $n_{a}$ is considered to be much better than $n_{a'}$ (i.e. $n_{a}$ dominates $n_{a'}$ ) only if at least one of the following conditions is satisfied

aP a'_{certainty} \land aP a'_{distance}

(8)

aP a'_{certainty} \land aI a'_{distance}

(9)

aI a'_{certainty} \land aP a'_{distance}

(10)

The Skyline contains the tuples which are not dominated by any other tuple. Thus, each tuple in the Skyline is at least as good as any other tuple outside of the Skyline for all the dimensions. The detailed algorithm implemented in this article is presented in Algorithm 3. The proposed algorithm is based on a block-nested loop (BNL), which is originally developed to join two relations in a relational database.²² Using this algorithm, only dominating overlay nodes are kept in the Skyline list at the end of all iterations. Once the Skyline list is determined, then, we randomly select one out of the Skyline list so that we can spread the overlay traffic over the Skyline and avoid a bottleneck situation.

Algorithm 3. Skyline list computation.
1: for each $a$ in overlay node candidate pools Do 2: ifSkylineList is empty then 3: $SkylineList = {a}$ 4: else 5: for each a′ in $SkylineList$ Do 6: if $a$ dominates $a'$ then 7: $SkylineList = SkylineList - {a'}$ 8: else if $a'$ dominates $a$ then 9: goto line 14; 10: else 11: goto line 5; 12: end for each 13: $SkylineList = SkylineList \cup {a}$ ] 14: end if 15: end for each

Management of node information table

To develop the overlay selection mechanism explained in the previous subsection, each node needs to maintain and update information about an overlay node such as its location, connectivity, time stamp, and mobility pattern. Specifically, the proposed overlay network requires each node to build and keep up-to-date node information table (NIT). Figure 5 illustrates the scenario in detail. A vehicle in the shaded circle receives control packets from neighbor moving cars, buses with fixed routine, and/or stationary RSUs. Based on these control packets, a node records and updates neighbor vehicles’ locations, time stamps, and neighbor status in its NIT. Note that we maintain the “direct neighbor” field of NIT considering the type of vehicles.

Figure 5.

Node information table.

To increase success ratio of node-to-node packet transmission, this article introduces the concept of a “virtual” radio range to reflect its own and its neighbor’s mobility using speed and direction information recorded in the NIT. The original existing GPSR routing protocol relies on the positions of its neighbors assuming that these positions would not change during a forwarding procedure. However, in VANET environment, nodes are not likely to be present at the same position at the time of packet forwarding because a VANET node moves at a high speed. To alleviate this problem, we define a “virtual” radio range, which is adaptive to its target environment and mobility features. Specifically, each node uses not only the position, but also other mobility information such as moving direction and speed with time stamp to define a virtual radio range for each neighbor as shown in Figure 6. Each node can obtain speeds and directions of neighbor cars in two ways. First, if underlying routing protocols provide velocity information of neighbor nodes, then each node simply uses this information. If not, each node indirectly computes velocities of neighbor nodes using location and time stamps in NIT of Figure 5.

Figure 6.

Detection and decision forwarding node.

For example, $ca r_{A}$ in Figure 6 can receive the location information packets from $ca r_{B}$ and $ca r_{C}$ at time $t_{a}$ before $ca r_{A}$ moves. At this time, $ca r_{A}$ recognizes $ca r_{B}$ and $ca r_{C}$ as neighboring nodes. But, at time $t_{b}$ after $ca r_{A}, ca r_{B}$ , and $ca r_{C}$ have moved, $ca r_{B}$ cannot receive the data packet from $ca r_{A}$ anymore because $ca r_{B}$ is out of transmission range of $ca r_{A}$ at time $t_{b}$ . To prevent $ca r_{A}$ from forwarding data packets to $ca r_{B}$ in this scenario, this article makes $ca r_{A}$ dynamically reduce “neighbor range” for $ca r_{B}$ . However, $ca r_{C}$ is still within a transmission range of $ca r_{A}$ even after cars have moved. To reflect this feature, this article proposes each forwarding node $n_{a}$ to calculate its “relative virtual” transmission range per each neighbor $n_{b}$ as follows

{virtualR}_{b}^{a} = org R_{a} + | \vec{V_{a}} - \vec{V_{b}} | * tim e_{gap}

(11)

where $org R_{a}$ is node n_a’s radio range for transmission and $tim e_{gap}$ is a time duration which can be determined based on its surrounding environment such as control packet intervals.

With this virtual range information, each node adaptively reidentifies a list of direct neighbors and determines its next node to forward the packet. However, current locations of buses and trams are predicted with considering their fixed time schedules and routines. Although the buses go out of a radio range and are not direct neighbors anymore, we periodically update their locations and their time stamps corresponding to their fixed routines.

As we mentioned before, the proposed hybrid overlay-routing scheme is built at an application layer on top of underlying routing protocols. Hence, the NIT mechanism is maintained at an overlay-layer without requiring major changes in existing routing protocols.

Performance evaluations

In this section, we evaluate the performance of the proposed overlay-routing mechanism. Since the proposed overlay approach is built at an application layer on top of routing protocols, we can adopt any existing routing protocol as an underlying routing mechanism. In this article, we build two overlay networks: (1) an overlay with multipath greedy perimeter stateless routing (mGPSR) (Overlay_G) and (2) an overlay with ad hoc on-demand distance vector (AODV; Overlay_A). For example, Overlay_G uses mGPSR for underlying communication mechanism between vehicles, and it uses an overlay routing at an application layer among overlay nodes. We compare Overlay_G and Overlay_A with existing VANET and MANET routing protocols such as GPCR, AODV, and GPSR. Note that we also simulate “mGPSR,” which is an extended version of the original GPSR with the proposed virtual range mechanism explained in the previous subsection.

To simulate a VANET environment scenario, we use mobility model generator for vehicular networks (MOVE)²³ and simulation of urban mobility (SUMO).²⁴ With these tools, we realistically generate movements of vehicles driving on the roads in the two-dimensional (2D) plane. For the simulations, we assume an urban scenario with a grid pattern map where there are 100 intersection points regularly and all intersections have traffic lights. We also assume that nodes participating in the topology can be either moving vehicles or RSUs. In this scenario, we include 100 nodes including 9 RSUs. Every node except RSUs has to follow the posted speed limit by the road sign and move at the speed of 0–15 m/s as shown in Figure 7. The output of these tools is then used by network simulator version 2 (NS-2) for network simulations among vehicles and RSUs. The parameters used in this simulation are summarized in Table 1. With this simulation, this article presents performance results of the proposed approach with three metrics: PDRs, end-to-end delays, and overhead.

Figure 7.

Screenshots of MOVE and SUMO scenarios in the simulation.

Table 1.

Simulation setup.

Simulation parameter	Value
Simulation area	1000 × 1000 m²
Number of nodes	100
Communication range	250 m
MAC protocol	IEEE 802.11
Traffic type	CBR
Beacon interval	1 s
Speed	0–15 m/s
Query interval	5 s (default)
Pair	20 (default)

CBR: Constant Bit Rate.

Packet delivery rate

We first examine PDRs for GPSR, mGPSR, AODV, Overlay_G, and Overlay_A with varying speed and congestion degrees.

The x-axes in the left and right graphs of Figure 8 represent speeds and the number of source and destination pairs, respectively. As shown in Figure 8, packet transmission rates of traditional GPSR, AODV, and GPCR are significantly decreased in proportion to the average speed of nodes. In the case of GPSR, an intermediate node forwards packets using the positional information of the destination node. However, as a node moves faster, the error probability of the positional information is increased. Even on-demand AODV and junction-based GPCR protocols still suffer from the same problem at the high speed. However, mGPSR provides a little bit better PDRs even at the high speed than these traditional protocols. It is explained by the fact that intermediate nodes in mGPSR consider speed and direction information of neighbors as well as their locations. As a consequence, the error probability of the positional information of neighbors is reduced even if nodes are moving at high speeds. However, mGPSR still shows about 10% of packet loss at the high speed and in high congested scenarios. It is because routing-layer protocols do not have an ability to explicitly detour the congested or problematic path and hence it does not get improved any further due to such limitations.

Figure 8.

Comparison of packet delivery rate.

In contrast, the proposed overlay-routing protocols, Overlay_G and Overlay_A, can give an another opportunity of forwarding packets by detouring the unreliable or congested paths. As a result, the proposed overlay-based approaches outperform other routing-layer protocols. We also observe that Overlay_G shows better performance than Overlay_A. This is because overlay networks are built on top of underlying routing protocols and so the overall performance is also dependent on underlying protocols as well. In VANET scenarios, mGPSR seems to show better PDRs than AODV. We also observe that both AODV and Overlay_A suffer from sharp packet drops in the most congested scenario (i.e. rightmost data with 35 pairs of packet transmission in the right graph). It is also correspondent with our argument that performance of underlying protocols affects the corresponding overlay network performance.

Overall, we showed that the proposed overlay routing with mGPSR provides the best PDR. The performance gain is even larger at the high speed and in the high congested scenario.

End-to-end delay

Next, we present end-to-end delays of the above six approaches in Figure 9. Most importantly, we observe that the proposed Overlay_G causes longer delay than traditional routing-layer protocols. This is explained by the fact that the proposed overlay-routing protocol basically tries to re-transmit the originally dropped packets one more time along the alternative route. Due to such second trials, end-to-end delays of the proposed overlay approach are longer especially when cars move at high speed. Also, the results show that Overlay_G causes longer delay than Overlay_A at a high speed. This is related to the fact that Overlay_G successfully recovers failed transmission much more than Overlay_A does. The more second trials succeed, the longer overall end-to-end delays are. As a consequence, the delays due to second trials affect overall end-to-end delays.

Figure 9.

Comparison of end-to-end delay.

One interesting thing is that both AODV and Overlay_A experience a sudden increase in delays at the crowded scenario. Once again, it is because AODV operates in a reactive method—a node makes a route by exchanging route request (RREQ)–route reply (RREP) messages when it wishes to send data packets. So, if networks are crowded, route discovery procedure itself might take a long time. Therefore, by nature of reactive protocols, an end-to-end delay of AODV is longer than GPSR and this phenomenon is magnified in the crowded scenario.

In GPCR, its end-to-end delay is very high although it does not try overlay transmission. This is because intermediate nodes are supposed to forward packets via a junction node to another intermediate node lying on the street between junction nodes. If there is no node between the junction nodes that is closer to destination, the packet will be forwarded to another junction node that is not closer. It will cause a longer delay compared to the traditional GPSR.

Overall, we found that the proposed overlay-based approaches experience slightly longer delay than traditional routing protocols. However, this symptom is a trade-off with PDR gains as explained in the previous section.

Control packet overhead

Now, we examine overheads of the proposed overlay approach in detail. As shown in Figure 10, GPSR-based and AODV-based protocols cause two different patterns of overheads. Basically, with location-based routing protocols such as GPSR, GPCR, mGPSR, and Overlay_G, each node is supposed to periodically transmit the control packets such as location and other related information packets. The proposed overlay routing with mGPSR also inherits such overhead issues from the original GPSR.

Figure 10.

Comparison of control packet overhead.

In contrast, reactive routing protocols like AODV are on-demand—they transmit control packets only when it has packets to send. Therefore, AODV-based approaches cause less amount of overheads than GPSR-based protocols in most cases with the exception of the crowded scenario. With 35 transmission pairs, AODV shows the similar amount of overheads because both control and data packets have dropped due to collisions. Then, AODV route discovery procedure would be repeated and repeated, which might make the situation even worse. As a consequence, packet overheads significantly increase in the crowded scenario.

Overall, from these results, we found that overheads of the proposed overlay-based approaches are not much more than the original routing protocols. For example, Overlay_G causes less than 1% more than original GPSR. Also, Overlay_A causes 2%–3% more overhead than AODV. Hence, we argue that the proposed overlay-based approaches achieve PDR gains without generating much overheads.

Overlay selection strategies

Finally, we explore several overlay selection strategies and observe their effects on the performance of the proposed overlay approach.

As we mentioned earlier in the previous section, we use Skyline operation to effectively select overlay nodes. The choice of overlay nodes in this scheme is dependent on several threshold values such as $certaint y_{pref}$ , $certaint y_{indiff}$ , $distanc e_{pref}$ , and $d i s t a n c e_{i n d i f f}$ in equations (4)–(7). Finding the optimized values for these thresholds is known to be a nondeterministic polynomial (NP)-hard problem. In this article, we setup these values as shown in Table 2. The proposed method chooses either (1) the nearest node or (2) the least mobile node. We call each of these two strategies as Overlay_N and Overlay_S. In addition, we propose the third scheme called Overlay_H, which chooses the nearest node and the least mobile node in turn.

Table 2.

Overlay selection strategies.

Preference threshold	Indifference threshold	Strategy
$Certaint y_{pref} >> Distanc e_{pref}$	$Certaint y_{indiff} >> Distanc e_{indiff}$	Nearest first (Overlay_N)
$Certaint y_{pref} << Distanc e_{pref}$	$Certaint y_{indiff} << Distanc e_{indiff}$	Stationary first (Overlay_S)

Figure 11 shows the performance of the proposed overlay mechanism with these three different overlay selection strategies: Overlay_N, Overlay_S, and Overlay_H. Since the positions of static nodes are fixed, a location error probability of a static node is lower than the error probability of a dynamic mobile node. It implies that packets destined to the static overlay node such as RSUs can arrive more successfully. However, Overlay_N with the nearest node selection shows lower PDRs because mobile nodes are moving at high speeds. However, a overlay-routing method with the nearest mobile node is sometimes more useful than a static node selection strategy, especially when static nodes are located way too far or even do not exist around. Furthermore, the static nodes are likely to be bottle-necked points in some crowded scenarios. In these situations, choosing the dynamic mobile node as an overlay node is helpful.

Figure 11.

Comparison of overlay selection strategies.

To complement these two extreme strategies, this article tries a hybrid option by changing overlay selection strategy from one to each other dynamically. For example, a hybrid overlay routing transmits packets to the static node first. If it experiences failure, it changes its strategy and transmits packets to the nearest node instead of a static node. Thanks to such features, the hybrid strategy shows the best performance even at the highest speed as shown in Figure 11.

Conclusion

In this article, we have proposed an application-layer overlay platform for smart and hyper-connected vehicular networks. The proposed overlay approach is built on underlying existing routing protocols so it does not require any change in existing routing protocols. Also, the proposed overlay mechanism has ability to explicitly detour a congested or unreliable path by effectively exploiting redundancy of networks. To effectively construct an overlay structure, we apply Skyline operation, which is based on the outranking algorithm for multi-criteria decision-making. Finally, this article evaluated the performance of the proposed overlay approach compared to existing routing protocols and showed that PDR has been significantly increased with keeping end-to-end delays and overheads within a tolerable range.

Footnotes

Handling Editor: Paolo Bellavista

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The corresponding author is Junghee Han. This work was funded by the Ministry of Science, ICT and Future Planning (Award Number: NRF-2015R1C1A2A01055444).

References

. Routing in vehicular ad hoc networks: a survey. IEEE Veh Technol Mag 2007; 2(2): 12–22.

Fubler

Widmer

Kasemann

et al . Contention-based forwarding for mobile ad-hoc networks. Ad Hoc Netw 2003; 1: 351–369.

Heissenbuttel

Buaun

Bernoulli

et al . BLR: beacon-less routing algorithm for mobile ad-hoc networks. Comp Commun 2004; 27: 1076–1086.

Sadeghian

Farahani

Abbaspour

et al . Dynamic forwarding delay in contention-based forwarding protocols. In: Proceedings of the international conference on computational problem-solving, Chengdu, China, 21–23 October 2011, pp.688–691. New York: IEEE.

Sanchez

Marin-perez

Ruiz

. Beacon-less geographic routing in real wireless sensor networks. J Comput Sci Technol 2008; 23: 438–450.

Lochert

Hartenstein

Tian

et al . A routing strategy for vehicular ad hoc networks in city environments. In: Proceedings of the IEEE intelligent vehicles symposium, Columbus, OH, 9–11 June 2003. New York: IEEE.

Karp

Kung

. GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th annual international conference on mobile computing and networking, Boston, MA, 6–11 August 2000, pp.243–254. New York: ACM.

Lochert

Mauve

Füßler

et al . Geographic routing in city scenarios. ACM SIGMOBILE Mob Comput Commun Rev 2005; 9(1): 69–72.

Zhao

Cao

. VADD: vehicle-assisted data delivery in vehicular ad hoc networks. IEEE T Veh Technol 2008; 57(3): 1910–1922.

10.

Leontiadis

Mascolo

. GeOpps: geographical opportunistic routing for vehicular networks. In: Proceedings of the IEEE international symposium on a world of wireless, mobile and multimedia networks, Espoo, 18–21 June 2007, pp.1–6. New York: IEEE.

11.

Cho

. A selective flooding method for propagating emergency messages in vehicle safety communications. In: Proceedings of the international conference on hybrid information technology, Cheju Island, South Korea, 9–11 November 2006, pp.556–561. New York: IEEE.

12.

Sharef

Alsaqour

Ismail

. Comparative study of variant position-based VANET routing protocols. Proc Tech 2013; 11: 523–539.

13.

Han

Watson

Jahanian

. Topology aware overlay networks. In: Proceedings of the IEEE conference on computer communications, Miami, FL, 13–18 March 2005. New York: IEEE.

14.

Jerbi

Meraihi

Senouci

et al . GyTAR: improved greedy traffic aware routing protocol for vehicular ad hoc networks in city environments. In: Proceedings of the 3rd international workshop on vehicular ad hoc networks, Los Angeles, CA, 24–29 September 2006. New York: ACM.

15.

Lee

Harri

et al . LOUVRE: landmark overlays for urban vehicular routing environments. In: Proceedings of the IEEE 68th vehicular technology conference, Calgary, BC, 21–24 September 2008. New York: IEEE.

16.

Qadri

Fleury

Altaf

et al . Multi-source video streaming in a wireless vehicular ad hoc network. IET Commun 2010; 4: 1300–1311.

17.

Zhu

Chen

et al . On dynamic video source decision in VANETs: an on-demand clustering approach. Int J Distrib Sens N 2015; 2015: 6.

18.

Borzsonyi

Kossmann

Stocker

. The skyline operator. In: Proceedings of the 17th international conference on data engineering, Washington, DC, 2–6 April 2001, pp.421–430. New York: ACM.

19.

Bouguettaya

. Efficient service skyline computation for composite service selection. IEEE T Knowl Data En 2013; 25(4): 776–789.

20.

Kwon

Choi

Chung

et al . In-network processing for skyline queries in sensor networks. IEICE T Commun 2007; E90-B(12): 3452–3459.

21.

Roy

. The outranking approach and the foundations of electre methods. Theory Decis 1991; 31(1): 49–73.

22.

8.2.1.14. Block nested-loop batched key access joins. MySQL 5.6 reference manual, Oracle Corporation, Redwood City, CA, 2015.

23.

Khairnar

Pradhan

. Mobility models for vehicular ad-hoc network simulation. Int J Comput Appl 2010; 11(4): 8–12.

24.

Institute of Transportation Systems. SUMO: simulation of urban mobility. Berlin: Institute of Transportation Systems, 2017.