Distance-Based Stable Routing Decision Scheme in Urban Vehicular Ad Hoc Networks

Abstract

A number of ad hoc routing protocols of vehicular ad hoc network (VANET) have been proposed and evaluated based on mobile ad hoc network (MANET) routing protocols. Although a large number of routing protocols have been developed in MANET, the VANET has different environments such as highly dynamic topology, frequently disconnected network, hard delay constraints for safety-related application, and various communications environments (e.g., highway or urban traffic scenarios). Therefore, development of a suitable routing protocol that considers these characteristics of VANET should be needed. In this paper we suggest the improved distance-based VANET routing protocol compared with the previous researches on urban traffic environments. We apply approaches to packet-collisions avoidance scheme in the intersection and to stable route decision scheme based on the adaptive waiting time. The performance is then evaluated under simulation which is implemented with the Manhattan urban traffic model. The results show the improved performance as compared with the previous researches.

1. Introduction

Vehicular ad hoc networks (VANETs) are an instantiation of mobile ad hoc networks (MANETs). Numerous routing protocols (e.g., [1–7]) for VANET have been proposed based on MANET routing protocols. Generally, MANET routing protocols have the main requirement to improve network performance to achieve minimal communication time with minimum consumption of network resources. Although a large number of routing protocols have been developed in MANET, a VANET routing protocol has different requirements [8] compared with the MANET routing protocols because the VANET has particular network environment as follows. A topology of the VANET usually changes due to high speed of movement between vehicles. A network could also be frequently disconnected by the same reason. The VANET is usually operated in two typical communication environments such as highway and urban traffic scenarios.

In urban scenarios, the environmental factors become much more complex than in highway because dissemination of messages could be often interrupted due to dynamic movement of vehicles, various road patterns, and much more obstacles such as buildings and trees. Thus, urban VANET routing protocols are challenged by severe conditions of these environmental factors. However, many of the existing VANET routing protocols have not considered these environmental factors in urban scenarios. Consequently, we focus on an efficient and stable routing decision scheme with a consideration of those urban environmental factors rather than highway in vehicular ad hoc networks.

Recently, we have proposed the position-based on-demand routing protocol (POVRP) [9, 10]. The POVRP applies approaches to a multihop broadcast and a unicast algorithm to establish stable routing path with shorter delay and low overhead in VANET. In VANET scenarios, the POVRP has been evaluated as more efficient VANET routing protocol than other protocols in POVRP because the characteristics and requirements for VANET have been applied in the POVRP. However, it implies some problems with packet-collisions when the nodes are dense because in the intersection every node could compete with the same waiting time to broadcasting.

In this paper, we deal with these problems and propose the improved distance-based VANET routing protocol based on [9, 10]. We apply two major approaches which are the multihop broadcast scheme for fast and reliable packet dissemination in the intersection and more stable route decision scheme based on the prioritized adaptive waiting time using a relative distance and a relative velocity between vehicles in order to select the stable relay node. In addition, we have applied the Manhattan map model including obstacles as well as its realistic traffic movement patterns into the simulation for more reliable performance evaluation in urban environments.

The rest of the paper is organized as follows. The related work is presented in Section 2. In Section 3, the stable route decision scheme that we propose is discussed. Section 4 describes the simulation setting and performance results. Finally, the paper is concluded in Section 5.

2. Related Work

In recent years, various VANET routing protocols have been proposed based on MANET routing protocols. However, a VANET has different requirements compared with MANET because VANET has particular network environment. A VANET is able to be regarded as a special type of MANETs with some unique features such as a highly dynamic topology, a frequently disconnected network, a sufficient energy and storage, a geographical type of communication, a mobility modeling and predication, various communications environments in urban and highway scenarios, and hard delay constraints [8]. These characteristics make the MANET routing protocols such as the ad hoc on-demand distance vector (AODV) [11] and the greedy perimeter stateless routing (GPSR) [12] inefficient in vehicular network.

The GPSR protocol is one of the representative geographical routing protocols and uses the position of routers and a packet's destination to make packet forwarding decisions. The protocol makes a greedy forwarding decision using only information about a router's immediate neighbors in the network topology. Source node does greedy forwarding by selecting the closest node to destination node using position information of neighboring nodes (assume source node already obtained destination node's location). If source node is not able to detect a closer node than itself, GPSR is operated on perimeter mode. The greedy forwarding is appropriate only for the network with many intermediate neighboring nodes with low mobility. Therefore, the GPSR is not suitable for VANET in urban environments.

The geographic source routing (GSR) protocol overcomes the disadvantages of GPSR approaches designed for MANETs when applied to VANET in urban scenarios [1]. Using a street map and position information of each vehicle, this protocol computes a route for forwarding messages to a destination along the street. The source vehicle computes a sequence of intersections that must be traversed in order to reach the destination.

The stable routing protocol for vehicles in urban environments [4] was proposed as a VANET routing protocol that considers the real-time road vehicle density information. In order to provide fast and reliable message delivery, each vehicle computes the real-time traffic density of the road to which it belongs from the beacon messages sent by vehicles on the opposite lane and its road information table. Using the road traffic density information as a routing metric, each vehicle establishes a reliable route for packet delivery.

The vehicle-assisted data delivery (VADD) [6] protocol delivers packets to road segments in high vehicle density. The density is computed by a delay estimation model that relies on preloaded street map and traffic statistics. The static-node-assisted adaptive data dissemination in vehicular networks (SADV) [7] protocol reduces the packet delay of VADD by employing static nodes at intersections. Both VADD and SADV use statistical measurements of the average vehicle density to select the most appropriate routing path to the destination.

The position-based on-demand VANET routing protocol (POVRP) was proposed in [9, 10]. It contains a multihop broadcast algorithm to rapidly propagate packets and a unicast algorithm to maintain a stable routing path. Each vehicle periodically broadcasts to neighbors a routine HELLO packet that contains the vehicle's information (e.g., location, velocity, direction) to establish the routing path. Each vehicle retains its own routing table. The routing table is used to store the vehicle's information received from its neighbors and to maintain the latest one. Every node that receives HELLO packet from a sender waits for rebroadcasting during the waiting time. The waiting time is shorter for more distant receivers due to the distance-based broadcast method. A receiver determines the waiting time depending on the absolute distance to the sender in [13]. A node cancels rebroadcasting the packet if it receives the rebroadcasted packet from another node during its own waiting time. Therefore, the distance-based broadcast method is able to remarkably reduce unnecessary rebroadcast packets in comparison with a flooding method. On the other hand, the adaptive waiting time depending on the relative distance between a sender and a receiver is determined to reduce the unnecessary waiting time in POVRP. The RREQ forwarding zone is also defined in order to set stable routing path. To configure a stable routing path, the neighbor nodes that move out of sender's communication range while establishing a routing path table should be ruled out in routing path setup process. In order to disseminate broadcasting packets into all directions at the intersections, nodes which exist in the intersection area have the shortest waiting time. However, the dissemination efficiency decreases in the case of dense nodes due to packet-collisions because every node which exists in the intersection has the same waiting time.

The stable routing decision scheme is suggested in [5] as our previous work. It is based on distance-based message dissemination using waiting times. It evaluated its effectiveness as compared with other protocols in urban environments. In this paper, we enhance [5] applying two major approaches separated between an intersection and a road area. In intersections, the intersection waiting time mechanism is operated for intersection-based route discovery. It enables disseminating packets toward all directions of an intersection for effective route discovery. Meanwhile, in road area, the adaptive waiting time mechanism is operated for stable relay node decision using a relative distance and a relative velocity between a sender and neighboring nodes. In addition, we modified algorithms for solving the problems of our previous distance-based message dissemination method and for more efficiency.

3. Stable Route Decision Scheme in Urban Vehicular Environments

In this section, we present the broadcasting scheme and the stable route decision scheme for urban intervehicle communication. In this paper, our proposed scheme is focused on using vehicle to vehicle (V2V) communication in urban areas, without any support by using vehicle to infrastructure (V2I) communication. We assume that the communication protocol between the vehicles is IEEE 802.11p [14], and the transmission range is 200 m. The IEEE 802.11p based communication device is equipped with the global positioning system (GPS) or another global navigation satellite system (GNSS) for each vehicle. These devices have geographic information such as map and periodically send HELLO messages (i.e., beacons) announcing their information to their neighbors. Therefore, every vehicle can acquire the neighbor vehicle information, (e.g., position, speed, moving direction) in its neighborhood area. The proposed scheme is based on distance-based broadcasting method using the distance between vehicles based on information of vehicle's position. As the POVRP, every node periodically broadcasts the HELLO message that contains its own position and retains information of its neighbors’ position within a single hop. The proposed scheme is designed to effectively disseminate RREQ packets and select stable forwarding node in the intersection.

3.1. Broadcast Scheme for Urban Intervehicle Communication

On the legacy distance-based broadcast method, the sender transmits a broadcasting packet. Then, the receivers wait to rebroadcast it as soon as their own waiting time is expired. The waiting time is shorter for more distant receivers. When one of the receivers rebroadcasts the received message in advance, other nodes do not rebroadcast the same message and then discard it. Though one of receivers which has the short waiting time fails to rebroadcast, another receiver which has long waiting time would try to rebroadcast when its own waiting time is expired. Equation (1) shows the basic waiting time on distance-based broadcasting method [13, 15, 16]:

$$\begin{array}{cc}& \text{Waiting\hspace{0.17em}\hspace{0.17em}Time}=\frac{-\text{MaxWT}}{Range}·d+\text{MaxWT},\end{array}$$

(1)

where MaxWT: maximum waiting time, $Range$ : radio range, and d: distance between vehicles.

In order to explore a destination node, a RREQ packet is disseminated from a source node by multihopping broadcast until it arrives at the destination node. Although density of vehicles is enough to relay a RREQ packet, it does not ensure that a routing path is successfully established in urban area because RREQ packets should disseminate toward all directions at intersections. However, the influence of obstacles to the dissemination of packets should be considered as shown in Figure 1.

Figure 1

Unsuccessful routing path setup due to obstacles in urban area.

In order to effectively disseminate RREQ packets toward all directions of intersection, the proposed scheme sets up shorter intersection waiting time (IWT) within intersection area than other waiting times out of intersection area. The value of IWT depends on a distance between vehicle's position and the center point of the intersection and is set below the maximum intersection waiting time (MaxIWT). A vehicle has shorter IWT than others when it is located closer to the center of the intersection as described in Figure 2. The reasons are to decrease the probability of packet collisions in the intersection and reduce an influence by obstacles surrounding an intersection.

Figure 2

Calculation of the waiting time within an intersection.

The center point of the intersection area can be calculated based on the center point of the dotted square described in Figure 2. The dotted square means the largest square where borders of all roads are extended inside an intersection. It can be applied for asymmetric intersection patterns as well as T-junctions. The radius (R) is defined as the longest vertex of the square from the center point of the intersection area:

$$\begin{array}{l}\mathrm{I}\mathrm{W}\mathrm{T}=\frac{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{W}\mathrm{T}}{R}·d_{\text{junction}}\\ \left(\text{where}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\le d_{\text{junction}}\le R\right),\end{array}$$

(2)

where IWT: intersection waiting time and $d_{\text{junction}}$ : distance between the vehicle and the center point in the intersection.

The IWT is calculated based on a radius of the intersection (R) and a distance between the vehicle's position and the center point in the intersection ( $d_{\text{junction}}$ ) as denoted in (2). The maximum value of IWT may be set to MaxIWT when a vehicle is located on a border of the intersection area. The minimum value of IWT may be set to zero when the vehicle is located on the center of the intersection area.

Note that there are secondary considerations when there is no obstacle around an intersection. As shown in Figure 3, vehicle V1 intends to disseminate a packet into all directions of an intersection. The V2 located in the intersection from the V1 shall be a relay node to rebroadcast a packet from the V1 based on (2) and then rebroadcast it to the V3, V4, and V5. Upon a reception of the packet from the V2, the next relay node shall be decided to the V3 than others because the V3 is a distant node from the V2 and has shorter waiting time than others. On the other hand, the V4 shall surrender a role of the rebroadcast and discard the received packet due to a packet reception from the V3. Consequently, the packet is not disseminated into the direction of Link7 as well as the V7. The V5 shall also encounter a similar problem that is a reception of the packet from the V1 and subsequent reception from V2.

Figure 3

Problems of distance-based method in urban area.

In order to solve these problems, the proposed scheme assigns a different identification (i.e., LinkID) to each direction of an intersection. When vehicles around an intersection area are waiting to rebroadcast a packet which is received from a vehicle located on an intersection area, they continuously proceed to wait for the rebroadcast without discarding it even though they receive the same packet from a vehicle that has another LinkID. On the other hand, when vehicles around an intersection area are waiting to rebroadcast a packet which is received from a vehicle located out of an intersection area, if they receive the same packet from a vehicle that has zero value of LinkID of the intersection area (i.e., LinkID = 0), they restart the waiting time for new packet of LinkID = 0 and discard the previous proceeding packet.

Vehicles within an intersection have a shorter waiting time (i.e., IWT) than those outside of the intersection. Therefore, vehicles within an intersection are allowed to broadcast or rebroadcast a packet with high priority. In order to apply such a broadcasting priority, the basic waiting time which is presented in (1) is modified as denoted in (3). The value of the basic waiting time shall be set above MaxIWT when the vehicle is located out of the intersection area. The concept of this modified basic waiting time is utilized for the adaptive waiting time in Section 3.2:

$$\begin{array}{cc}& \text{Waiting}\hspace{0.17em}\hspace{0.17em}\text{Time}=\frac{-\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{W}\mathrm{T}}{Range}·d+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T},\end{array}$$

(3)

where MaxIWT: maximum waiting time in the intersection and R: radius of the intersection.

3.2. Prioritizing Scheme for Stable Route Decision

On the table-driven routing protocols, a routing path is able to be established when the route reply (RREP) is successfully responded to the source node from destination node through forwarding nodes which were determined in the RREQ procedure. In order to establish a stable routing path, stable forwarding nodes should be decided in the RREQ procedure. The forwarding node decision based on the legacy distance-based method is described in Figure 4. A routing path between the source and the destination could be disconnected when the forwarding node deviates from the sender's communication range. A probability of disconnection might increase in higher relative velocity between the source and the forwarding node. Therefore, the node which is expected to shortly leave from the sender's communication range should be excluded from the list of potential forwarding nodes as shown in Figure 5.

Figure 4

The forwarding node decision by the legacy distance-based method.

Figure 5

The forwarding node decision by using the relative velocity.

In this section, we describe the stable route decision scheme to select fast and stable forwarding nodes based on the distance-based broadcast method of (3) outside of intersection. Our stable route decision scheme separates a sender's communication range into three prioritized zones as shown in Figure 6.

Figure 6

Prioritized zones separated within sender's communication range.

The distance between the sender and the current nearest node from it is set to the distance of the $d1$ . The area of a circle with a radius of the distance $d1$ forms the $D1$ zone. A node in the $D1$ zone has the lowest priority to broadcast or rebroadcast a packet. Because it is expected that only one node currently exists in the $D1$ zone. However, unexpected nodes could also become a potential forwarding node if they exist in the $D1$ zone.

The distance $d2$ is set to the distance between a sender and the most distant stable node from a sender within the sender's communication range. The stable node means the neighboring node that is expected to still exist within the sender's communication range until the packet traversal time ( $T_{\text{traversal}}$ ). In other words, based on a relative velocity between the sender and the neighboring node, the proposed scheme calculates a distance between them which is expected after $T_{\text{traversal}}$ and we define the distance as $d_{\text{traversal}}$ . Then the $d2$ is set to the most $d_{\text{traversal}}$ when the $d_{\text{traversal}}$ is shorter than a radius of sender's communication range. The $T_{\text{traversal}}$ means a packet delivery time when a source delivers a RREQ packet to a destination and then the destination returns a RREP packet to the source in order to establish a routing path. The $T_{\text{traversal}}$ is calculated by a packet time-to-live ( $\mathrm{T}\mathrm{T}\mathrm{L}$ ) and by a packet delivery time per hop ( $t_{\mathrm{h}\mathrm{o}\mathrm{p}}$ ) as denoted in (4). The $\mathrm{T}\mathrm{T}\mathrm{L}$ is the maximum hop count which is allowed to deliver from source to destination and is decreased by one when a packet passes through a hop. If the maximum hop count, $\mathrm{T}\mathrm{T}\mathrm{L}$ , is exceeded, the corresponding RREQ or RREP packet is discarded. We considered that a source node sends a RREQ packet to destination and then the source node receives a RREP packet back from destination. Therefore, a $\mathrm{T}\mathrm{T}\mathrm{L}$ is multiplied by 2. The $t_{\mathrm{h}\mathrm{o}\mathrm{p}}$ is an average packet delivery time per hop. The $D2$ zone is formed by the area with a radius of the distance $d2$ except for the $D1$ zone. A node in the $D2$ zone has the highest priority to broadcast or rebroadcast a packet:

$$\begin{array}{cc}& T_{\text{traversal}}=\mathrm{2}·\mathrm{T}\mathrm{T}\mathrm{L}·t_{\mathrm{h}\mathrm{o}\mathrm{p}},\end{array}$$

(4)

where TTL: hop count for a packet time-to-live and $t_{\mathrm{h}\mathrm{o}\mathrm{p}}$ : packet delivery time per hop.

The CR zone is formed by excluding both $D1$ and $D2$ zones from the sender's communication range. Nodes that exist within the CR zone are unstable because they are expected to leave from the sender's communication range before a routing path is successfully established.

The VANET topology is generally formed along the road. As shown in Figure 7, we distinguish a forward part and a backward part from a sender node and classify $d1$ and $d2$ as forward distance ${d1}_F$ , ${d2}_F$ and backward distance ${d1}_B$ , ${d2}_B$ . The values of ${d1}_F$ and ${d2}_F$ would be different from the values of ${d1}_B$ and ${d2}_B$ if neighboring nodes are deployed without their symmetrical position in both forward and backward parts from a sender. The procedure of a separation of the prioritized zones is described in Algorithm 1. A sender calculates ${d1}_{F/B}$ and ${d2}_{F/B}$ for its forward and backward parts and maintains information from HELLO messages of neighboring nodes. The sender calculates ${d1}_F$ , ${d2}_F$ , ${d1}_B$ , ${d2}_B$ based on Algorithm 1 and then broadcasts a RREQ packet including its communication range ( $Range$ ), position ( $p_s$ ), TTL, and the calculated distances (i.e., ${d1}_F$ , ${d2}_F$ , ${d1}_B$ , ${d2}_B$ ):

$$\begin{array}{cc}& \text{Adaptive}\hspace{0.17em}\hspace{0.17em}\text{Waiting}\hspace{0.17em}\hspace{0.17em}\text{Time}=\left\{\begin{array}{cc}\frac{-\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{W}\mathrm{T}}{Range}·d+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}\hfill & \left(\mathrm{i}\mathrm{f},\mathrm{0}\le d\le d\mathrm{1}\right)\hfill \\ \frac{-\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{W}\mathrm{T}}{Range}·\left(d+Range-d\mathrm{2}\right)+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}\hfill & \left(\mathrm{i}\mathrm{f},d\mathrm{1}<d\le d\mathrm{2}\right)\hfill \\ \frac{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}-\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{I}\mathrm{W}\mathrm{T}}{Range}·\left(d-Range-d\mathrm{1}\right)+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{W}\mathrm{T}\hfill & \left(\mathrm{i}\mathrm{f},d\mathrm{2}<d\le Range\right),\hfill \end{array}\right.\end{array}$$

(5)

where d: forward or backward distance between a sender and a relay node.

Algorithm 1: Separation of prioritized zones.

Input: a sender's communication range Range

   a sender's position $$p_s$$

   a sender's velocity $$v_s$$

   a set of forward neighboring nodes $$N_F=\left\{\right.u_{\mathit{1}},\dots ,u_n\left.\right\}$$ in sender's Range

   a set of backward neighboring nodes $$N_B=\left\{\right.u_{\mathit{1}},\dots ,u_n\left.\right\}$$ in sender's Range

   a neighboring node $$u_i$$ 's position $$p_i$$

   a neighboring node $$u_i$$ 's velocity $$v_i$$

   a TTL which is determined by a source node

Output: $$d{\mathit{1}}_F$$ , $$d{\mathit{2}}_F$$ , $$d{\mathit{1}}_B$$ , $$d{\mathit{2}}_B$$

procedure ForwardPrioritizedZones( )

   if IsMessage( ) then

    $$\forall u_i\in N_F$$ , $$d(i)$$ = CalculateDistance( $$p_s$$ , $$p_i$$ )

    $$d{\mathit{1}}_F=\mathrm{Min}(d(i))$$

    $$\forall u_i\in N_F$$ , $$d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i)$$ = ( $$v_i-v_s$$ ) ⋅   $$T_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}$$ + $$d(i)$$

   if ( $$d{\mathit{1}}_F$$ ≤ $$d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i)$$ ≤ Range) then

       $$d{\mathit{2}}_F$$ = $$\mathrm{Max}(d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i))$$

   end if

   end if

end procedure

procedure BackwardPrioritizedZones( )

   if IsMessage( ) then

   ∀ $$u_i\in N_B$$ , $$d(i)$$ = CalculateDistance( $$p_s$$ , $$p_i$$ )

    $$d{\mathit{1}}_B$$ = $$\mathrm{Min}(d(i))$$

   ∀ $$u_i$$ ∈ $$N_B$$ , $$d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i)$$ = ( $$v_i-v_s$$ ) ⋅   $$T_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}$$ + $$d(i)$$

   if ( $$d{\mathit{1}}_B$$ ≤ $$d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i)$$ ≤ Range) then

       $$d{\mathit{2}}_B$$ = $$\mathrm{M}\mathrm{a}\mathrm{x}(d_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{a}\mathrm{l}}(i))$$

   end if

   end if

end procedure

Figure 7

Classification of the forward and backward zone.

The receivers that are neighboring nodes receive the packet from the sender and then calculate a distance from sender's position and set their own adaptive waiting time (AWT) based on ${d1}_F$ , ${d2}_F$ , ${d1}_B$ , ${d2}_B$ which are received from the sender. The AWT is calculated by (5). A receiver has the $\mathrm{A}\mathrm{W}\mathrm{T}$ computed in $0\le d\le d{1}_{F/B}$ if the receiver's current position is located on the $D1$ zone. Similarly, it has the AWT computed in $d{1}_{F/B}<d\le d{2}_{F/B}$ if the receiver's current position is located on the $D2$ zone. Equally, it has the AWT computed in $d{2}_{F/B}<d\le Range$ if the receiver's current position is located on the CR zone. Based on (5), the AWT of the forward part is shown in Figure 8 and the AWT of the backward part is presented in Figure 9. A dotted line presents the basic waiting time based on (3) and solid lines describe the $\mathrm{A}\mathrm{W}\mathrm{T}$ in each zone. After neighboring nodes calculate their own AWTs, they may change the receiver mode into the sender mode in order to rebroadcast the packet. The neighboring nodes also separate their own prioritized zones and add the calculated information to the packet using Algorithm 1 and then try to rebroadcast it when AWT is expired. This procedure of a distance based adaptive rebroadcast method is described in Algorithm 2.

Algorithm 2: Distance based adaptive broadcast method.

Algorithm for node $$u_i$$

Input: a sender's communication range Range received

   a sender's position $$p_s$$ received

    $$u_i$$ 's own position $$p_i$$

    $$d{\mathit{1}}_F$$ , $$d{\mathit{2}}_F$$ , $$d{\mathit{1}}_B$$ , $$d{\mathit{2}}_B$$ received

   a TTL received

Output: a TTL

procedure DistanceBasedAdaptiveBroadcast(received Packet)

   if IsPacket( ) then

   distance = CalculateDistance( $$p_s$$ , $$p_i$$ )

   AWT = SetWaitingTime(distance, $$d{\mathit{1}}_F$$ , $$d{\mathit{2}}_F$$ , $$d{\mathit{1}}_B$$ , $$d{\mathit{2}}_B$$ )

   while IsExpired(AWT) do

      if IsNewReceivedPacket( ) then

         if (receivedPacket == NewReceivedPacket) then

            Delete(receivedPacket, NewReceivedPacket)

            break

         end if

      end if

   end while

   if IsPacket( ) then

       TTL = TTL − 1

       ForwardPrioritizedZones( )

       BackwardPrioritizedZones( )

       SingleBroadcast(receivedPacket)

   end if

   end if

end procedure

Figure 8

Adaptive waiting time of the forward zone.

Figure 9

Adaptive waiting time of the backward zone.

If multiple vehicles are located on the same distance exactly from a sender, they may rebroadcast their received packets simultaneously due to the same waiting time (i.e., AWT as well as IWT). In spite of this packet collision, however, another vehicle which has the next waiting time can rebroadcast because no vehicle received these packets successfully. In other words, if one of the vehicles rebroadcasts the packet in advance, other vehicles which have the next waiting time do not rebroadcast the same message. Then, they reset their waiting times. This distance-based rebroadcasting mechanism makes the packet dissemination reliable without overheads.

Consequently, the most distant node is not usually selected as the forwarding node as compared with the greedy forwarding scheme. However, our proposed scheme selects the stable distant forwarding node and it would reduce the delay for the route repair.

4. Performance Evaluation

4.1. Configuration of Simulation Environments

In order to analyze performance of the proposed scheme, the Qualnet 4.5 [17] has been used as network simulator. Simulation parameters of the MAC and PHY layer are configured to meet specifications of the IEEE 802.11p wireless access in vehicular environments (WAVE) [14]. The default data rate is set to 6 Mbps and the maximum communication range is set to 200 m because we focus on the intervehicle communication in urban area as configured in [6, 7]. Constant bit rate (CBR) is used in the application layer and then we set up that CBR traffic with a packet size of 512 bytes is continuously generated during simulating time because we intend to evaluate the proposed scheme under the influence of periodic HELLO messages. Simulation parameters are presented in Table 1.

Table 1

Simulation parameters.

Parameters	Values
Simulation area	Manhattan (2200 m × 1500 m)
Vehicle density [cars/Km]	25, 35, 50
MAC and PHY layer	IEEE 802.11p
Frequency [GHz]	5.9
Channel bandwidth [MHz]	10
Data rate [Mbps]	6
Packet size [byte]	512
Communication range [m]	200

We have applied two approaches to the simulation to evaluate more reliable performance under urban environments. First, the Manhattan model is implemented into the QualNet 4.5 network simulation as shown in Figure 10. The Manhattan model has been taken advantage of by many researches (e.g., [15, 16, 18]) for the urban traffic simulation because the Manhattan model consists of a uniform grid of blocks. Obstacles (i.e., buildings in each block) are also deployed in our Manhattan model in order to apply the effect of radio interferences in intersections. Second, urban traffic movement patterns of vehicles are applied into the simulation. In urban area, the traffic movement pattern depends on traffic signals, moving directions, and traffic density as compared with highway. We have applied the Manhattan map model and its traffic movement patterns into the simulation. In other words, we have extracted traffic movement patterns using the simulation of urban mobility (SUMO) [19] and then we have applied them into the QualNet simulator.

Figure 10

A satellite picture of Manhattan and an implemented Manhattan model of simulation.

4.2. Analysis of Simulation Results

In order to evaluate the performance of the proposed protocol, we compare ours with other routing protocols such as AODV [5], GSR [1], POVRP [12, 13], and other urban VANET routing protocols [4] in using the same simulation parameters. AODV is a typical ad hoc routing protocol using the flooding method. The flooding is a simple dissemination method where all nodes that received a RREQ packet rebroadcast the packet and will be compared with our distance-based dissemination scheme. GSR is designed to apply city environments using the greedy forwarding method. We intend to compare the performance between GSR and ours in urban environments. As our previous research, POVRP enables measuring enhancements of the proposed protocol. Last, the proposed protocol is compared with other urban vehicular routing protocols suggested in [4].

Figure 11 shows the average delay time for the establishment of a route path in different node densities. All those protocols excluding AODV reduce the average delay time when in higher node density because the number of nodes is suitable for making a routing path. However, when using AODV, it sharply increases when the node density is 50 vehicles per km. The result assumed is that the most of nodes try retransmissions due to collisions caused by using the flooding broadcast method of AODV. By contrast, the average delay time decreases in higher node density when using GSR, POVRP, and the proposed protocol. It shows similar performances among those protocols.

Figure 11

Average delay time versus vehicle density.

Figure 12 shows the RREQ packet delivery ratio in different node densities. It tends to increase when in higher density in all those protocols because the number of nodes is suitable to deliver packets. Particularly, the proposed protocol shows more outstanding performance than other protocols. The proposed protocol has been improved up to 8 percent as compared with our previous research POVRP because the proposed protocol broadcasts the RREQ packet with low collision probability using the prioritized AWT within the intersection. On the other hand, when using AODV and GSR, it shows relatively low delivery ratio due to a disadvantage of a flooding method of AODV and a greedy forwarding method of GSR in urban environments. In particular, when using AODV, the number of unsuccessful packet delivery is much more than when using others because huge RREQ packets shall be generated by the flooding method.

Figure 12

RREQ packet delivery ratio versus vehicle density.

Figure 13 shows throughputs of the network in different node densities. The throughput of all those protocols excluding AODV tends to be increased when in higher node density. Particularly, the proposed protocol significantly improves the network throughput in high node density scenarios compared with other routing protocols. The result assumed is that the proposed protocol enables selecting more stable forwarding node and guaranteeing the RREQ packet delivery within the intersections. On the other hand, when using AODV and GSR, the result shows relatively low throughput due to a disadvantage of a flooding method of AODV and a greedy forwarding method of GSR in urban environments. In addition, when using POVRP, the result is caused by a generation of many route error packets due to less stability than the proposed protocol.

Figure 13

Throughputs versus vehicle density.

Figure 14 shows accumulative overheads according to the simulation time. AODV incurs the highest total overhead because every node which has received RREQ packets has to rebroadcast into its neighboring nodes within the maximum hop count due to the flooding method. GSR also incurs quite lots of overhead because in low vehicle density area, most packets may not be delivered to the destination due to the greedy forwarding method. The total overheads of the proposed protocol are similar to POVRP. However, the proposed protocol has generated less overhead after several seconds than POVRP. We assume that the result is caused by the number of route error (RERR) packets which are generated by different routing decision scheme between the POVRP and the proposed protocol.

Figure 14

Comparison of total overheads in the network.

Figure 15 shows the number of RERR packets between AODV, POVRP, and the proposed protocol. The occurrence of a RERR packet indicates that the routing path has been broken by changes of a topology when the forwarding node leaves from sender's communication range. A local repair of AODV operates when the hop count between the forwarding node and the destination node is less than MAX_REPAIR_TTL. The proposed protocol applies the local repair algorithm of POVRP in [10]. Although the POVRP and the proposed protocol use the same local repair algorithm, the number of RERR packets has been reduced about 25 percent in the proposed protocol because the proposed protocol decreases the number of breakaway nodes than POVRP by using the stable routing decision scheme.

Figure 15

The number of route error packets generated from protocols.

Figures 16 and 17 show the date packet delivery ratio and the overheads for different number of vehicles as compared with [4]. The stable routing protocol proposed in [4] is a VANET routing protocol that considers the real-time road vehicle density information. We call this routing protocol SRP in this paper. The SRP also works based on the source routing mechanism by using exchange of RREQ and RREP packets for route setup. For a fair comparison, our proposed protocol is evaluated under simulation parameters applied in [4]. The simulation area is set to 3000 m × 3000 m, and the road layout is a grid pattern. Roads are placed on 10 vertical and 10 horizontal lines. Obstacles are not considered in the simulation area although our protocol is designed to reduce the effect of obstacles around intersections as one of its novelties. The total number of vehicles is varied from 150 to 300. The communication range is set to 250 m. The average velocity is set to 35 km/h. The date packet delivery ratio is the ratio of the successfully delivered data packets to the total number of transmitted data packets. Vehicles might deliver their data packets after accomplishment of route setup. In other words, the data packet delivery ratio can be decreased by environmental factors such as lack of vehicle density, instability of route setup, and network congestion.

Figure 16

Data packet delivery ratio versus vehicle density.

Figure 17

Overheads per vehicle versus vehicle density.

As shown in Figure 16, the SRP achieves higher data packet delivery ratio than ours when the number of vehicles is from 150 to 250. However, the proposed protocol performs over 91.3 percents in all cases and outperforms SRP for 300 vehicles. It is assumed that SRP selected denser roads to find routing path in sparse vehicular network. However, our protocol also performs high data packet delivery ratio although the simulation scenario does not reflect the effect of obstacles.

The overheads per vehicle are caused by routing-related control messages such as RREQ, RREP, and beacon messages. In [4], the parameter k was defined for SRP. It decides how much the routing protocol allows the path to diverge from the shortest path. As shown in Figure 17, the proposed protocol outperforms SRP in terms of the overheads per vehicle for all cases. In all cases, the SRP generates more overheads than in our proposed protocol. This result assumed that our protocol is effective in reducing network overheads because each vehicle avoids the duplicated RREQ message forwarding by using the distance-based waiting time.

5. Conclusion

A VANET routing protocol has different requirements compared with the MANET routing protocols because the VANET has particular network environments. In this paper, we have proposed the enhanced distance-based VANET routing protocol and have applied two major approaches which are the multihop broadcast scheme for fast and reliable packet dissemination in the intersection and more stable route decision scheme based on the prioritized adaptive waiting time using a relative distance and a relative velocity between vehicles in order to select the stable relay node. In addition, we have applied the Manhattan map model including obstacles as well as its realistic traffic movement patterns into the simulation for more reliable performance evaluation in urban environments. As a result, our proposed protocol improves the performance as compared with AODV, GSR, and POVRP in urban vehicular scenarios. The proposed protocol shows that it reduces the average delay in making a routing path with low overhead and also performs high throughput and high probability of successful delivery by the stable routing decision.