Moving Target Oriented Opportunistic Routing Algorithm in Vehicular Networks

Abstract

In vehicular networks, the multihop message delivery from information source to moving vehicles presents a challenging task due to many factors, including high mobility, frequent disconnection, and real-time requirement for applications. In this paper, we propose a moving target oriented opportunistic routing algorithm in vehicular networks for message delivery from information source to a moving target vehicle. In order to adapt the constantly changing topology of networks, the forwarding decisions are made locally by each intermediate vehicle based on the trajectory information of the target vehicle. The simulation and real trace experiment show that our design provides an efficient message delivery with a higher success ratio, shorter success time, and lower transmission overhead compared with other reference approaches.

1. Introduction

Vehicular networks are consisted of moving vehicles which are equipped with dedicated short-range communication (DSRC) and location-aware modules. Usually, vehicular network nodes also have processing and storage capabilities, which have enabled vehicular network to form a new intelligent network. In recent years, vehicular networks have been envisioned to be useful in traffic management, road safety, and other information provision applications. Prime examples of such applications include potential traffic hazards/jams alert, shortest path detection, interests/goals sharing with vehicles, and real-time information obtainment.

Apart from the applications or expected benefits, the challenges and solutions are also the attractions of vehicular networks. A large number of researches have been devoted to this subject [1–3]. Recently, vehicular networks research has involved multihop message delivery from moving vehicle to infrastructure. VADD [4] is a vehicle-assisted message delivery protocol which forwards a message to the best path with the lowest estimation message delivery delay. Geopps [5] presents a forwarding protocol which makes forwarding decisions based on the encounters and geographical information in navigation systems of vehicles.

At the same time, it is also an important research area for returning the message to the moving target vehicle. In this case, the ultimate destination for the message stays in motion, which involves significant challenges. The simplest solutions, such as flooding and epidemic [6] (one delay-tolerant network routing), require high costs to deliver the message successfully, since the message is randomly forwarded in the whole network. Also, there are many MANET protocols [7] designed for moving targets. However, the high speed nodes, dynamic topology, map-based movement, and long distance of moving of vehicle networks make these protocols not so suitable. Trajectory-based statistical forwarding [8] (TSF) is proposed in order to deal with the infrastructure-to-vehicle message delivery performed through the computation of a target point based on the destination vehicle's trajectory. This target point represents an optimal rendezvous point of the message and the destination vehicle. However, the optimal point computation is based on several assumptions, such as the traffic statistics following the Poisson arrival model (which occurs in optimal situation only). Additionally, the TSF shall apply solely to the situations where stationary nodes are installed at each intersection. A routing protocol is presented in [9] to enable infrastructure-to-vehicle message delivery based on the navigation system. It also requires several APs as infrastructures to provide support, and the mechanism of the protocol is not realized. In spite of that, the above researches are not suitable in actual situation, since infrastructures are not equipped in many cases.

In the majority of cases, a characteristic of the infrastructure-to-vehicle research is the decision of the message transmission path that takes place before the transmission actually starts. However, the traffic condition is also constantly changing; as such, a fixed transmission path may lead to a nonoptimum result. Unlike existing research, the forwarding decisions about the next hop in opportunistic routing (as proposed in this paper) are performed exactly when needed. The transmission path is selected according to the real-time traffic conditions in order to deliver the message with a high success ratio, short success time, and low transmission overhead.

In this paper, we propose a moving target oriented opportunistic routing (MORN) algorithm in vehicular networks, which is designed for delivering messages from an information source to the moving target vehicle. This process will depend on the message's potential being opportunistically carried and forwarded among moving vehicles. In the paper, a problem is formulated for the message delivery, and the subsequent carrier selection is modelled, which is the most important issue in the routing. And then a novel opportunistic routing algorithm employing the unicast strategy is proposed to solve the above problem, in which the next hop is decided according to the trajectory of the subsequent carrier candidate and the target vehicle. In the algorithm, both the success ratio and the success time are taken into account for the subsequent carrier decisions. We evaluate the performance of MORN through the opportunistic network environment (ONE) [10] simulator and real world trace experiment [11–13]. Compared to other reference approaches, MORN has a better performance on message delivery in terms of success ratio, average hops, and overhead.

The rest of this paper is organized as follows. Section 2 gives background of the existing research on multihop infrastructure-to-vehicle message delivery in vehicular networks. The problem formulation of MORN is proposed in Section 3. Section 4 describes how to model the subsequent carrier selection. Section 5 describes the details of MORN. Section 6 provides the evaluation and the result of this research. Finally, Section 7 concludes the paper.

2. Related Work

Multihop message delivery through vehicular networks is complicated by the fact that vehicular networks are highly mobile and have the potential to be frequently disconnected. This issue is complicated further when the destination of a message is also in motion, as the network must locate the position of the moving target vehicle and make sure the message is delivered successfully.

The routing protocol for DTN is one solution to this problem. The epidemic [6] involves message delivery to the target vehicle through the messages exchange throughout the whole vehicular network. While resulting in a maximal spreading speed and maximal delivery success ratio, this approach would also result in a maximal waste of network resources. This process would require the participation of almost all vehicles in the networks, which is impractical. Some kinds of DTN routing [14, 15] deliver the message by estimating the “likelihood” of each vehicle being able to meet the target vehicle, as based on node encounter history. However, the success ratio is not considered satisfactory when the estimation is dependent on few nodes. Conversely, it is also considered a great waste for the computing and storage capability of each vehicle node when the estimation is based on a large number of vehicle nodes.

Among the vehicular networks routing protocols, geographic routing is known to be scalable with respect to the size of network, and as such is a good candidate for intervehicle communications. The geographic routing takes advantage of road map knowledge, calculating the best path between source and destination [16]. GeoDTN + Na [17] is a hybrid Geo-DTN routing solution which incorporates the strength of DTN forwarding in geographic routing to mitigate the impact of intermittent connectivity. Some geographic routing involves a computationally expensive Dijkstra algorithm which leads to each neighbor for each forwarding decision [18]. The best path in geographic routing is the one having the shortest route, the lowest cost, shortest latency, or otherwise optimal attributes of all candidates [19]. A global route is required in the geographic protocols, but it also presents a significant cost with respect to time and network resources. Additionally, there is no guarantee that the computing path is the best one since the traffic conditions are constantly changing. Even more significantly, geographic routings require the coordinates of the target to be known before the message forwarding starts, something which is impossible in vehicular networks when the target vehicle is moving. Some advantaged geographic routing systems assume the coordinates of the target are known at any given time [20, 21]. However, it is still invalid to deliver the message in vehicular networks if the target moves a substantial distance from its known position.

Another solution for the delivery of a message to a moving target involves the calculation of the route before the transmission takes place. This calculation is based on the speed, location, movement, or trajectories of vehicle nodes. A multihop routing approach of a vehicular network in an urban area is presented in [22]. The optimal route from source to destination is selected according to the smallest expected disconnection degree (EDD), which is calculated from the given information on a vehicle's speed, trajectory, and location. The algorithm forwards the message to the vehicle with the smallest EDD value (from route to destination) of all vehicles in the whole vehicular network. The shortest trajectory from source to destination is calculated from the roadway geometry along with the location and movement. There are still two similar algorithms [23, 24] in this process. Although these algorithms result in a relatively good performance, the overhead and massive calculation for the whole network makes the approach unrealistic.

Some advanced research in this area has resulted in improvements to these types of approaches by finding an optimal point on the project path of the target vehicle, which stores the message and waits for the target vehicle to arrive. TSF [8] is designed to find one optimal target point which the vehicle is expected to intersect. This point is also designated as the position where the message is delivered to the destination, and is determined by the distribution of message delay and vehicle delay. When the message is delivered to the target point, a stationary node stores it and waits for the target vehicle. The target point is selected to minimize the delivery delay and satisfy the required message delivery success ratio. Obviously, in this case TSF will work only in the optimal situation that the traffic statistics follow the Poisson arrival models. In [9], a routing protocol which is similar to TSF is presented. Also, there are some data delivery schemes utilizing vehicles' trajectory. STDFS is proposed in [25], which predicts the encounters between vehicles by utilizing shared vehicle trajectories, and an encounter graph is then constructed to aid packet forwarding. STDFS needs access points' help and a precalculation for predicting encounters, which is impractical in vehicular networks.

3. Problem Formulation

In this section, a scenario is described, and then the problem formulation and several related definitions about MORN are provided.

In order to illustrate the problem clearly, let us consider a scenario where a moving vehicle wishes some customized driving information, such as real-time traffic information, as obtained from information source. In this scenario, there are two potential message delivery processes: (1) the vehicle sends the message request to information source, or (2) the message received from information source is forwarded to the moving vehicle reversely. The first process has been studied in the existing research; however, the second process has not been researched in depth as it presents more of a challenge. Here, MORN is proposed for the second process.

There are two assumptions to be made about the vehicles of the vehicular network: (a) vehicles are equipped with short-range wireless communicate devices (e.g., DSRC device) and GPS navigators with preset destination. With these resources, vehicles are able to disclose their own physical location, destination, and trajectory. Meanwhile, the vehicles can be easily synchronized on the same clock by GPS, and (b) the message needing to be delivered contains the target vehicle's trajectory, the time to live (TTL) of the message, and the message itself. Each vehicle carrying the message can obtain the target vehicle's trajectory and the TTL of the message.

The goal of MORN is to deliver message from information source to a moving target vehicle, as dependent on the ability of the message to be opportunistically carried and forwarded across moving vehicles. The maximum success delivery is the primary consideration, while the minimum success time is also taken into consideration.

Consider a traffic network which is modeled as a directed graph $G(J,E)$ . J represents the set of junctions on the traffic map, and E represents the edge set of roads connecting the junctions. On the traffic graph G, V, and P represent two important factors. V is the vehicle set, while $v_i\in V$ represents a vehicle. P is the set of paths representing the tracks of individual vehicles, and $p_{v_i}\in P$ is the path of vehicle $v_i$ . In this paper, we define IS as information source, which is the source of the message delivery, and $v_{\text{tar}}$ as the target vehicle (being the destination). The position of vehicle $v_i$ at time t is defined as $p_{v_i}(t)$ , which can be represented by geographic information system (GIS) position $(x_{v_i}(t),y_{v_i}(t))$ in the map, where x and y are the latitude and longitude of the position. Table 1 captures the notations used in this paper.

Table 1

Notations used in this paper.

$v_i$	A vehicle node in the network
$p_{v_i}(t)$	The position of $v_i$ at time t
$p_{v_i}$	The path of vehicle $v_i$
$x_{v_i}(t),y_{v_i}(t)$	The latitude and longitude of $v_i(t)$
TTL	The validity of a message
$t_{\text{now}}$ ; time current	The current time of the network
Transmit range	The distance limit of inter vehicle communications
λ	The weight coefficients of success ratio and delay

A special case of MORN is shown in Figure 1. In this case, the variables $v_{\mathrm{1}}$ , $v_{\mathrm{2}}$ , and $v_{\mathrm{3}}$ represent three (nontarget) vehicles, and $v_{\text{tar}}$ represents the target vehicle. Each arrow represents the trajectory of a vehicle, while the icons on the trajectory represent the position of the vehicle at a time point. When the target vehicle wants to receive any kind of message from information source, it issues a request. The request contains the target vehicle's future trajectory as well. The trajectory can be obtained from the navigation system or some routing estimation system. When information source receives the request, the requested message needs to be transferred to the target vehicle as allowed by the opportunistic forwarding capability of the vehicular network. The process by which the message is sent back to the target vehicle is the key point of MORN. The details of the scenario are presented in Figure 1.

Figure 1

MORN delivering message: $v_{\mathrm{1}}\to v_{\mathrm{2}}\to v_{\text{tar}}$ .

First, vehicle $v_{\mathrm{1}}$ receives the message from information source at time $t_{\mathrm{0}}$ . The trajectory of target vehicle $v_{\text{tar}}$ is contained in the message. In the whole process of carrying the message, $v_{\mathrm{1}}$ periodically broadcasts the trajectory of $v_{\text{tar}}$ .

Secondly, vehicle $v_{\mathrm{1}}$ meets vehicle $v_{\mathrm{2}}$ at time $t_{\mathrm{1}}$ . After some calculation and comparison, $v_{\mathrm{1}}$ finds $v_{\mathrm{2}}$ to be “better” in terms of delivering the message to $v_{\text{tar}}$ , since $v_{\mathrm{2}}$ has the ability to deliver the message in a closer place to target vehicle than $v_{\mathrm{1}}$ . As such, the message is forwarded to $v_{\mathrm{2}}$ , and the message carried by $v_{\mathrm{1}}$ is discarded.

Next, the same scenario takes place at time $t_{\mathrm{2}}$ , where $v_{\mathrm{2}}$ meets vehicle $v_{\mathrm{3}}$ . Both $v_{\mathrm{2}}$ and $v_{\mathrm{3}}$ have the ability to deliver the message to $v_{\text{tar}}$ . As could been seen from Figure 1, however, it is obvious that $v_{\mathrm{2}}$ has the ability to forward the message to $v_{\text{tar}}$ at time $t_{\mathrm{3}}$ , while $v_{\mathrm{3}}$ can deliver the message at time $t_{\mathrm{4}}$ . Since the message delivery time for $v_{\mathrm{3}}$ is not “better” in comparison to $v_{\mathrm{2}}$ , the message forward does not take place between $v_{\mathrm{2}}$ and $v_{\mathrm{3}}$ .

At last, $v_{\mathrm{2}}$ forwards the message to $v_{\text{tar}}$ at time $t_{\mathrm{3}}$ , and the target vehicle has received the message.

4. Subsequent Carrier Selection

Since the MORN is based on the idea of opportunistically unicast routing a message to a moving target vehicle, the most important issue involves the selection of a succession of carriers that are most likely to carry the message to the moving target vehicle. This opportunistic routing will involve exploiting information from the navigation system (NS) in each vehicle. The selection of the subsequent carrier for a vehicle should be considered from 2 items as follows for an efficient message transmission.

• (1)

The nearness of the candidate and the target vehicle's trajectory.

(2)

The possible time of delivery.

More detailed description is as follows.

Definition 1 (trajectory nearest distance $d_{\min }(v_i,v_j)$ ).

The trajectory nearest distance of two vehicles $v_i$ , $v_j$ at any time $\mathrm{0}\le t\le \text{TTL}$ is defined as $d_{\min }(v_i,v_j)={\min }_{\mathrm{0}\le t\le \text{TTL}}{d}_{v_i,v_j}(t)$ .

Note. The distance of two cars at time t can be calculated as

$$\begin{array}{l}{d}_{v_i,v_j}\left(t\right)=\mathrm{dist}\left(v_i\left(t\right),v_j\left(t\right)\right)\\ \hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}=\sqrt{{\left(x_{v_i}\left(t\right)-x_{v_j}\left(t\right)\right)}^{\mathrm{2}}+{\left(y_{v_i}\left(t\right)-y_{v_j}\left(t\right)\right)}^{\mathrm{2}}}.\end{array}$$

(1)

Definition 2 (nearness of trajectory $d_{\min }^{\star }(v_i,v_j)$ ).

The nearness of the two vehicles' trajectory is defined as

$$\begin{array}{cc}& d_{\min }^{\star }\left(v_i,v_j\right)=\underset{\mathrm{0}\le t\le \text{TTL}}{\min }\frac{d_{v_i,v_j}\left(t\right)}{d_{\text{IS},v_{\text{tar}}}\left(\mathrm{0}\right)}=\frac{d_{\min }\left(v_i,v_j\right)}{d_{\text{IS},v_{\text{tar}}}\left(\mathrm{0}\right)}\end{array}$$

(2)

which represents the nearest degree of two vehicles at any available time.

In this way, we can denote the nearness of the candidate and the target vehicle's trajectory as $d^{\star }(v_i)$

$$\begin{array}{l}{d}^{\star }\left(v_i\right)=d_{\min }^{\star }\left(v_i,v_{\text{tar}}\right)=\underset{\mathrm{0}\le t\le \text{TTL}}{\min }\frac{d_{v_i,v_{\text{tar}}}\left(t\right)}{d_{\text{IS},v_{\text{tar}}}\left(\mathrm{0}\right)}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\frac{d_{\min }\left(v_i,v_{\text{tar}}\right)}{d_{\text{IS},v_{\text{tar}}}\left(\mathrm{0}\right)}.\end{array}$$

(3)

Definition 3 (minimum time for nearest distance $t_{\min }(v_i,v_j)$ ).

The $t_{\min }(v_i,v_j)$ is defined as the earliest time when two vehicles $v_i$ , $v_j$ intersect at the nearest distance $d_{\min }(v_i,v_j)$ .

Definition 4 (possible success time $t_{\min }^{\star }(v_i,v_j)$ ).

The possible success time is defined as $t_{\min }^{\star }(v_i,v_j)=t_{\min }(v_i,v_j)/\text{TTL}$ , which represents the earliest degree of two vehicles at the nearest distance.

Hence, the possible success time of the candidate vehicle is

$$\begin{array}{cc}& t^{\star }\left(v_i\right)=t_{\min }^{\star }\left(v_i,v_{\text{tar}}\right)=\frac{t_{\min }\left(v_i,v_{\text{tar}}\right)}{\text{TTL}}.\end{array}$$

(4)

Definition 5 (relative nearness $\sigma (v_i,v_j)$ ).

Consider that

$$\begin{array}{l}\sigma \left(v_i,v_j\right)=\lambda *\left(d^{\star }\left(v_i\right)-d^{\star }\left(v_j\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(\mathrm{1}-\lambda \right)*\left(t^{\star }\left(v_i\right)-t^{\star }\left(v_j\right)\right)\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le \lambda \le \mathrm{1}\end{array}$$

(5)

is called relative nearness.

Relative Nearness is a value for comparison of the two vehicles' ( $v_i$ and $v_j$ ) nearness of trajectory, $d^{\star }(v_i)$ and $d^{\star }(v_j)$ . It is also used for comparing the two vehicles' possible success times, $t^{\star }(v_i)$ and $t^{\star }(v_j)$ . Different values of λ are used to construct three typical cases: when λ equals 1, and relative nearness considers only the nearness of two vehicles' trajectory transmission, while the success time is only considered when λ equals to 0, and the nearness of trajectory and the success time are both taken into account with λ being other values.

The decision of message validity is also one of the important issues for MORN. If a valid message is misjudged, the message may be not received by target vehicle as expected. On the contrary, if an invalid message is misjudged, a redundant message will be transferred throughout vehicular networks. In MORN, we define the message validity as follows.

• (1)

The message validity has a close connection with the following track of the vehicle which carries the message. If the following track is far off the trajectory of the target vehicle, the message becomes invalid as its potential possibility to be received by the target vehicle becomes small. The distance validity of the message can be calculated as:

$$\begin{array}{l}{M}_d\left(v_i\right)=\underset{t_{\text{now}}\le t\le \text{TTL}}{\min }\frac{d_{v_i,v_{\text{tar}}}\left(t\right)}{d_{\text{IS},v_{\text{tar}}}\left(t_{\text{now}}\right)}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\frac{d_{\min }\left(v_i,v_{\text{tar}}\right)}{d_{\text{IS},v_{\text{tar}}}\left(t_{\text{now}}\right)}.\end{array}$$

(6)

(2)

The travel time of the message is another item related to message validity. We compare the travel time and the TTL of a message in order to judge if the message is outdated. In order to compute the time validity of the message, we defined the time validity as follows:

$$\begin{array}{cc}& M_t\left(v_i\right)=\{\begin{array}{cc}\frac{t_{\text{now}}}{\text{TTL}}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le t_{\text{now}}\le \text{TTL},\hfill \\ \mathrm{1}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{t}_{\text{now}}\ge \text{TTL}.\hfill \end{array}\end{array}$$

(7)

Definition 6 (message validity $M^{\star }(v_i)$ ).

Consider that

$$\begin{array}{cc}& M^{\star }\left(v_i\right)=\left(\mathrm{1}-M_d\left(v_i\right)\right)*\left(\mathrm{1}-M_t\left(v_i\right)\right)\end{array}$$

(8)

is defined as the message validity of vehicle $v_i$ at time $t_{\text{now}}$ .

5. Moving Target Oriented Opportunistic Routing Design

In this section, we propose the framework of MORN, the opportunistic routing system which delivers message from information source to a moving target vehicle using the trajectory information available in vehicle navigation systems. Following the MORN framework, the key algorithm is explained in detail.

5.1. Framework Design

The main purpose of MORN is to keep looking for vehicles that can potentially deliver the message closer and earlier to the moving target vehicle. It requires the subsequent carrier to be closer to the target vehicle at time t than the present carrier, which means that the trajectory nearest distance of the new candidate is smaller than that of the present carrier. In another instance, the subsequent carrier candidate having the trajectory nearest distance at an earlier time t can also be chosen as the subsequent carrier. The framework can be explained as follows.

• (1)

A vehicle carrying the message periodically broadcasts the trajectory of the target vehicle.

(2)

One-hop neighboring vehicles calculate the nearness of trajectory (3) and possible success time (4) of themselves according to the trajectory of the target vehicle.

(3)

The present carrier make decisions, either keeping the message or forwarding it to a one-hop neighbor based on comparing the relative nearness (5) of the neighbor and itself.

(4)

The present carrier monitors the message validity (8). If the message is invalid, the present carrier will discard the message.

(5)

This process is repeated until the target vehicle receives the message or until the message is invalid.

5.2. Algorithm for Subsequent Carrier Selection

In this subsection, key algorithm of computing the nearness of the $v_i$ and $v_{\text{tar}}$ 's trajectory ( $d^{\star }(v_i)$ ) and possible success time of $v_i$ ( $t^{\star }(v_i)$ ) is described. On this basis, the procedure of choosing the subsequent carrier is proposed.

5.2.1. Relative Nearness Computing

To choose the subsequent carrier, we need to calculate the $d^{\star }(v_i)$ and $t^{\star }(v_i)$ of each vehicle $v_i$ , as shown in Algorithm 1. The distance limitation of vehicle-to-vehicle communications is represented as transmit range, and the current time of the network is represented as time current. Initially, the $d_{\min }(v_i,v_{\text{tar}})$ is defined as the current distance of $v_i$ and $v_{\text{tar}}$ , while the $t_{\min }(v_i,v_{\text{tar}})$ is the current time (Line 1-2). Secondly, if the current $d_{\min }(v_i,v_{\text{tar}})$ is smaller than transmit range, which means that the $v_{\text{tar}}$ can receive the message from $v_i$ directly, and there is no need to find a smaller $d_{\min }(v_i,v_{\text{tar}})$ (Line 3–5). If the current $d_{\min }(v_i,v_{\text{tar}})$ is not small enough, the smallest distance of $v_i$ and $v_{\text{tar}}$ will be calculated at each valid time. The process is ended when any distance of time t is smaller than transmit range, or when each distance is computed (Line 6–14). At the end, $d^{\star }$ and $t^{\star }$ are calculated with $d_{\min }(v_i,v_{\text{tar}})$ and $t_{\min }(v_i,v_{\text{tar}})$ (Line 15-16).

Algorithm 1: Relative nearness computing.

Input

 Vehicle node $v_i$ ;

Output

 The nearness of $v_i$ and $v_{\text{tar}}$ 's trajectory, $d^{\star }(v_i)$ ;

 The possible success time of $v_i$ , $t^{\star }(v_i)$ ;

(1)   $d_{\min }(v_i,v_{\text{tar}})=d_{v_i,v_{\text{tar}}}(TimeCurrent)$ ;

(2)   $t_{\min }(v_i,v_{\text{tar}})=TimeCurrent$ ;

(3)  if   $d_{\min }(v_i,v_{\text{tar}})<TransmitRange$   then

(4)    $t=\text{TTL}$ ;

(5)  end if

(6)  for  each $t\in TimeCurrent\le t<\text{TTL}$   do

(7)  if   $d_{v_i,v_{\text{tar}}}(t)<d_{\min }(v_i,v_{\text{tar}})$   then

(8)    $d_{\min }(v_i,v_{\text{tar}})=d_{v_i,v_{\text{tar}}}(t)$ ;

(9)    $t_{\min }(v_i,v_{\text{tar}})=t$ ;

(10)   if   $d_{\min }(v_i,v_{\text{tar}})<TransmitRange$   then

(11)    Break;

(12)   end if

(13)  end if

(14)  end for

(15)   $d^{\star }(v_i)=\frac{d_{\min }(v_i,v_{\text{tar}})}{d_{\text{IS},v_{\text{tar}}}(\mathrm{0})}$ ;

(16)   $t^{\star }(v_i)=\frac{t_{\min }(v_i,v_{\text{tar}})}{\text{TTL}}$ ;

5.2.2. Subsequent Carrier Selection

The procedure of choosing the subsequent carrier is shown in Algorithm 2, in which the present carrier is $v_i$ . Initially, $v_i$ calculates the $d^{\star }(v_i)$ (nearness of the $v_i$ and $v_{\text{tar}}$ 's trajectory) and $t^{\star }(v_i)$ (possible success time of $v_i$ ) (Line 1). Then a decision is made to either chose the neighbor, $v_j$ , as the subsequent carrier, or to keep the message with the current carrier (Line 2–11). This includes the following steps. (i) Make the $d^{\star }(v_j)$ and $t^{\star }(v_j)$ of each vehicle $v_j$ meet during the trip of $v_i$ and then find the optimum $v_j^{\star }$ with the optimum value of $d^{\star }(v_j)$ and $t^{\star }(v_j)$ (Line 3–5). (ii) Compute the $\sigma (v_i,v_j^{\star })$ according to the definition of relative nearness. If the $\sigma (v_i,v_j^{\star })$ is larger than a certain threshold, $v_j^{\star }$ is chosen as the subsequent carrier, and the message is transferred from $v_i$ to $v_j^{\star }$ ; otherwise, nothing happens (Line 6–10).

Algorithm 2: Subsequent carrier selection for $v_i$ .

Input

  Current message carrier, vehicle node $v_i$ ;

Output

 Subsequent message carrier, vehicle node $v_j$

(1)  Read the $d^{\star }(v_i)$ and $t^{\star }(v_i)$ ;

(2)  while  $\neg ((TargetReceiveMsg)\hspace{0.17em}\text{or}\hspace{0.17em}(t\ge \text{TTL}))$   do

(3)  Get each neighbor $v_j$ of $v_i$ ;

(4)  Get $d^{\star }(v_j)$ and $t^{\star }(v_j)$ from $v_j$ ;

(5)  Find the optimum $v_j^{\star }$ ;

(6)  if   $\sigma (v_i,v_j^{\star })>c$   then

(7)   Transfer Message from $v_i$ to $v_j^{\star }$ ;

(8)   Delete Message on $v_i$ ;

(9)   Break;

(10)  end if

(11)  end while

Now, we analyze the computation complexity of MORN. In a vehicular network, the number of vehicles met during the whole transmission process is $n=|V_{\text{met}}|$ , and the number of update times is $m=|t|$ . For each encounter, a relative nearness is computed having the complexity of $O(m)$ and is required for each of the comparing vehicles. In the whole process of message transmission, an n number of encounters happen. As a result, the overall computation complexity of MORN is $O(mn)$ .

6. Performance Evaluation

In this section, we evaluate the performance of MORN through extensive simulations using the ONE [10] simulator. Since DTN routing is one of the possible solutions for message delivery to moving target without the help of stationary nodes, we have compared the performance of MORN with two alternate DTN routing mechanisms—FirstContact [26] and PRoPHET [14]. In the case of the former alternate mechanism, FirstContact, a meeting of two (or more) vehicle nodes, triggers transmission of the message from one node to another as it has time. Then, it removes the message from the first node after it has been transferred. As a result, only one copy of every message is retained in the network—similar to MORN. PRoPHET, the latter alternate mechanism, performs variants of flooding. It estimates the “likelihood” of each vehicle node's ability to deliver a message to the target vehicle based on node encounter history.

We conducted 101 rounds of simulations with different random seeds for each vehicle number N. The scenario chosen for simulation was the road map of Helsinki, Finland. Each vehicle's movement pattern is determined by ShortestPathMapBasedMovement model. In this model, vehicles take the shortest path on the road of the map exactly. For each simulation, a vehicle node was selected randomly as the target vehicle, and the simulation was repeated 10 times with different target vehicles for each random seed. Only a transmission message was considered in the simulation, and the loss of transmission during the communication procedure was not taken into consideration. The weight coefficients of the success ratio and the success time is represented as λ, and the weight of success ratio and the success time of MORN's consideration varied with the value of λ. Referring to some previous works [4, 27], we set the values for related simulations parameters. The simulations parameters are listed in Table 2.

Table 2

Simulation parameters.

Parameter	Value
Size of network area	$\mathrm{4500}\mathrm{*}\mathrm{3400}$  m2
Simulation time	500 s
Transmit range	100 m
Transmit speed	2 Mbps
Vehicle number N	25; 50; 75; 100; 125; 150; 175; 200
Average node speed	15~80 MPH
Message size	7 kB
λ	0; 0.1; 0.5; 0.9; 1

When $\lambda =\mathrm{0}$ , only success time is taken into consideration. This results in a very low success ratio and a short success time. It is a special case with stochastic character for MORN. Therefore, the result of MORN with $\lambda =\mathrm{0}$ is not explicable compared with other cases.

In Figure 2, we have plotted the average hops of algorithms with the vehicles number N increases. For different values of λ of MORN, the average hops decrease as the λ increases. It is obviously that the success ratio has a higher weight in MORN as λ increases. The choice for subsequent carrier shows more characteristics of success ratio. That means that some possible forwardings which may gain shorter success time are canceled. Hence, the forwarding number is dwindling when λ increases. From Figure 2, we can see that FirstContact has a larger number of average hops whenever the density is low or high, and the gap between FirstContact and the other two algorithms is even greater when the density is high. This is primarily caused by the stochastic of the message forwarding in the whole network. At a high vehicle density, the average hops are high as a result of the high vehicle number met during the message trip. The PRoPHET's average hops are similar to the MORN's. That means that MORN and PRoPHET have a similar forwarding number.

Figure 2

The average hops comparison for different densities.

Figure 3 demonstrates the transmission overhead (number of message replicas) for different densities. Since both the FirstContact and MORN employ unicast strategy, the overhead of FirstContact and MORN has the same characteristic with the average hops. While the PRoPHET employs multicast strategy, the overhead of PRoPHET is obviously higher than the others. From Figure 3, it is obvious that MORN has the lowest overhead of the three, and the gap between MORN and the others increases as the density increases.

Figure 3

The overhead comparison for different densities.

The average success time (ST) comparison is shown in Figure 4. It is obvious that the smaller the λ of MORN, the shorter the average success time. This verifies the effectiveness of the possible success time ( $t^{\star }(v_i)$ ) in the definition of relative nearness. FirstContact has a relatively lower success time with a lower success ratio (see Figure 7), which means that the FirstContact can only deliver the message successfully when the target vehicle has a relative near distance to the information source in most cases. MORN with $\lambda =\mathrm{1}$ and PRoPHET have the similar average success time. However, MORN has a much lower success time than PRoPHET with other λ values. The result shows that the opportunistic forwarding in MORN has a better performance in success time compared with the forwarding based on node encounter history in PRoPHET.

Figure 4

The average success time comparison for different densities.

Figure 5 shows the impact of vehicle number on the direct transmission distance as calculated by FirstContact, PRoPHET, and MORN. From Figure 5, we can see that FirstContact has the lowest direct transmission distance, while MORN has the highest direct distance. The lowest direct transmission distance of FirstContact again demonstrates that FirstContact can only deliver the message successfully when the target vehicle has a relative near distance to the information source in most cases, while the multicast strategy helps PRoPHET to obtain a lower direct distance obviously. For MORN, the direct distance increases as the success ratio has a higher weight due to the λ increases, which means that MORN selects a forwarding strategy which concerns more on success ratio instead of direct transmission distance. Figure 6 shows the vehicle number met during the message trip for different densities. The vehicle number met during the message trip increases as the density of the vehicular network increases.

Figure 5

The direct distance comparison for different densities.

Figure 6

The vehicle number met during the message trip for different densities.

Figure 7

The success ratio comparison for different densities.

Figure 7 shows the success ratio (SR) of various algorithms for different densities. The SR of FirstContact is lower than the other routing algorithms and has no obvious change as determined by the vehicle number. PRoPHET performs better than FirstContact, especially when the vehicle number is larger, meaning that it performs well with greater density of vehicles. For MORN, the SR increases as the λ increases. It is obvious that MORN shows the best performance of all, especially when $\lambda \ge \mathrm{0.5}$ .

The performance of the three algorithms is due to the fact that FirstContact delivers the message without optional choice, while both PRoPHET and MORN can deliver the message based on some kind of estimation mechanism. Another reason for the underperformance of FirstContact is that it has only one copy of each message existing in the network, similar to MORN, which results in a “random walk” search for target vehicle. Hence, the SR is not varying too much.

The three algorithms performance evaluations are also carried out by exchanging packets on six different vehicular network instances from real area of Málaga, Spain (Figure 8). Two different sizes of the same metropolitan area and two traffic densities are defined as [11–13]. The road traffic is generated by SUMO [28], in which the vehicles move following the realistic mobility and traffic rules. At the same time, five sources exist for messages generation. The results in Table 3 show that MORN also has a better performance in this situations.

Table 3

Simulation results.

	Routing type	SR (%)	Hops	Overhead	ST (s)
	FirstContact	0.6	6	7.67	57.8
$U_{\mathrm{1}}$ with 10 vehicles	PRoPHET	0.8	1	3.75	60.65
	MORN $\lambda =\mathrm{0.5}$	0.8	1	0	62.42
	FirstContact	0.71	5	7.25	31.2
$U_{\mathrm{1}}$ with 15 vehicles	PRoPHET	0.85	4	10.3	42.6
	MORN $\lambda =\mathrm{0.5}$	0.85	2	1	30.25
	FirstContact	0.5	7	17.4	56.14
$U_{\mathrm{2}}$ with 20 vehicles	PRoPHET	0.9	3	13	99.36
	MORN $\lambda =\mathrm{0.5}$	1	1	0	70.26
	FirstContact	0.8	5	6.75	28.8
$U_{\mathrm{2}}$ with 30 vehicles	PRoPHET	1.0	2	6.6	29.08
	MORN $\lambda =\mathrm{0.5}$	1.0	1	0	28.2

Figure 8

Map of Málaga, Spain.

7. Conclusion

In this paper, we present and discuss MORN, an opportunistic routing unicast algorithm in vehicular networks. The main idea of MORN is to identify a “better” message carrier with the potential to deliver a message closer and earlier to the moving target vehicle. And the transmission procedure of MORN is implemented completely through the message carrying and forwarding across vehicles, without any help of infrastructures. In MORN, there is no global route from source to destination that must be created and maintained, and the forwarding decision is made on a per-hop basis. Even the path of the message is not determined before the transmission starts. The evaluation results show that, when compared to the existing algorithms, MORN has a good performance in various vehicle densities in terms of success ratio, average hops, overhead, and success time. Most notably when the vehicle density is high, MORN had an impressive performance.