Abstract
The vehicular ad hoc network (VANET) is an essential technology that enables the deployment of the intelligent transportation system (ITS), which improves the traffic safety and efficiency. For the efficient message delivery in VANETs, it is desirable to provide a reliable and stable VANET routing protocol. However, VANET routing is challenging since the VANET is fundamentally different from conventional wireless ad hoc networks; vehicles move fast, and the network topology changes rapidly, causing intermittent and dynamic link connectivity. In this paper, we propose a VANET routing protocol that works based on the real-time road vehicle density information in order to provide fast and reliable message delivery so that it can adapt to the dynamic vehicular urban environment. In the proposed mechanism, 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. We compare our proposed mechanism with the well-known GPSR via NS-2 based simulations and show that our mechanism outperforms GPSR in terms of both delivery success rate and routing overhead.
1. Introduction
The intelligent transportation system (ITS) that includes all types of communications in vehicles, rails, and aircrafts is one of the next generation transportation systems. ITS provides fast and safe traffic management to drivers by rafting the intelligent technology such as VANET onto the existing transportation system. The vehicular ad hoc network (VANET) which is an essential technology for ITS has recently received considerable attention [1, 2]. VANET provides safety-related information as well as Internet services to vehicles.
The VANET architecture is proposed for these purposes [3]: vehicle-to-vehicle (V2V) and vehicle-to-roadside (V2R). V2R can provide traffic conditions, weather, and Internet services in real time. V2V can be used in enhancing the driver's safety based on intervehicle wireless communications.
Although VANET is similar to the mobile ad hoc network (MANET), it has different features such as rapid changes of network topology resulting in network disruption, short communication time, and high packet loss rate. Many studies related to these issues have recently been proposed. Since VANET requires critical safety-related information to be quickly and reliably delivered to its users, it is important to design a VANET routing protocol to satisfy the requirement. The MANET routing protocol can be used in VANET, but in a VANET with additional features like no limited power supply and global positioning system (GPS), the geographical routing protocol [4] is more suitable.
The Greedy Perimeter Stateless Routing (GPSR) [5] is one of the most widely known geographical routing protocols for MANET. GPSR makes greedy forwarding decisions based only on the information about immediate neighbours of a node. When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. GPSR suffers from poor performance in VANET because VANET has the characteristics of rapidly changing network topology due to high mobility, variable vehicle density, and driving habits.
In the urban environment VANET, the network topology created by vehicles is based on the road layout, so a packet is forwarded from a source node to a destination through the roads. In this environment, GPSR may provide inefficient or even invalid paths because of the greedy forwarding. That is, a packet can be delivered via the shortest route including a road with low vehicle density, resulting in a delivery failure.
To solve this problem, we propose a VANET routing protocol that considers the real-time road vehicle density information. It enables us to provide stable intervehicle communications in the urban environment by establishing routes with high vehicle density. For a moving vehicle to measure the road vehicle density in real-time is not an easy task since vehicles are moving in various speeds and directions. For measuring the road vehicle density in real-time, we do not require any extra devices such as traffic cameras or Wi-Fi devices to be deployed or involved in. Our mechanism allows vehicles to effectively measure the real-time road vehicle density by counting only on the beacon messages from the vehicles moving in the opposite direction. Here, those beacon messages provide the information on the estimated road vehicle density information of its moving direction and help to estimate the number of vehicles on the opposite lane. The novelty of our proposed mechanism is to separate the number of vehicles on a road into forward direction and reverse (or opposite) direction and simply sum up those two numbers to get the estimated total number of vehicles on the road. Hence, our mechanism works only for the roads with forward and reverse direction lanes. From the obtained real-time road vehicle density information, the source vehicle attains the best route that offers the minimum delay to the destination. The routing mechanism that we adopt is the source routing with road-by-road forwarding. And, on a specific road, the greedy forwarding approach of geographical routing is applied.
The rest of the paper is organized as follows. In Section 2, the related work on GPSR and geographical VANET routing protocols using traffic density information is briefly covered. In Section 3, how to measure the road traffic density information in real time and the proposed VANET routing protocol using the measured traffic density information are described. The simulation results and the performance analysis are presented in Section 4. Finally, the conclusions are summarized in Section 5.
2. Related Work
Many of the existing VANET routing protocols are based on geographical routing protocols for MANET [6, 7]. GPSR is one of the representative geographical routing protocols for MANET which uses greedy forwarding. In GPSR, each node periodically broadcasts beacons to notify its own position to its one-hop neighbours. Based on this position information, a packet is forwarded to the closest neighbour to the destination. Greedy forwarding is appropriate only for the network with many intermediate nodes with low mobility. Therefore, GPSR is not suitable for the rapidly changing VANET with restricted road layout and variable vehicle density.
In the urban environment VANET, packets should be forwarded with considering the road conditions to get better performance. Geographical routing protocols using greedy forwarding such as GPSR may confront dead ends in the urban environment since a packet may be forwarded to the road which is the closest to the destination but with low vehicle density.
The road vehicle density depends on the average number of vehicles passing on the road. An example of the distribution of vehicles is shown in Figure 1. When greedy forwarding is used, the route (the solid line arrow) with low vehicle density is chosen to reach the destination because it is the shortest. In this case, packets may not be delivered to the destination due to low vehicle density, incurring the perimeter mode.
An example of road layout with various road vehicle densities.
Previous VANET routing protocols such as CAR [8] and A-STAR [9] have been proposed based on GPSR, but they have not considered the road vehicle density. Therefore, they can perform very poorly when there are roads with low vehicle density.
VADD [10] routes packets to road segments with high vehicle density. The density is computed by a delay estimation model that relies on preloaded street map and traffic statistics. SADV [11] reduces the packet delay of VADD by employing static nodes at intersections. VADD [10] and SADV [11] both use statistical measurements of the average vehicle density to select the best route to the destination. However, it is well known that the vehicle density is dynamic due to the high speed of vehicles [12]. Therefore, our work focuses on measuring the real-time density of the roads and employing information to the routing scheme. Another interesting VANET routing protocol is the one that considers the wireless interference level to search the routes [13].
In this paper, we propose a VANET routing protocol that considers the real-time road vehicle density to provide fast and reliable communications. In the proposed routing mechanism, each vehicle not only uses the position information but also computes the road vehicle density. Based on the road vehicle density information, each vehicle establishes a reliable route for packet delivery such as the dashed-line arrow in Figure 1.
3. Road Vehicle Density-Based VANET Routing
In this section, we describe our proposed VANET routing protocol that provides stable routes consisting of roads with high traffic density. Since our routing protocol uses the real-time road density information as a routing metric, it is essential to acquire the up-to-date road traffic density information. Therefore, we first propose an efficient protocol to acquire the real-time road traffic density. Then, we present a source routing protocol that utilizes this information. Note that we assume that all vehicles are equipped with GPS but are not provided with preloaded global traffic information.
One may argue that the traffic density information can be obtained via centralized servers [10, 11]. Indeed, there are a plethora of services that provide real-time traffic information on the web. These services are based on traffic estimations by use of traffic cameras or even Wi-Fi devices [14]. However, these services only provide a coarse-grained estimate of the traffic density. For example, the services that use traffic cameras can provide the traffic information on the roads that have the traffic cameras installed.
Furthermore, the real traffic measurements show that the vehicle distribution on roads follows the exponential distribution [15], and this may significantly impact the performance of routing in vehicular networks [16]. Therefore, we propose a simple but effective method to acquire the real-time traffic density.
3.1. Acquiring the Real-Time Traffic Density
The road traffic density should account for all vehicles currently residing on every lane of the road. A naive approach to accomplish this is for each vehicle to simply transmit beacons to its neighbours, but the vehicle may not be aware of the vehicles outside of the broadcast transmission range even if it is on the same road. We use a smarter method to overcome this; each vehicle periodically transmits beacons that contain its direction of movement and the total number of reverse cars (TRC) in addition to its own identifier and position. By using this TRC information, each vehicle estimates the number of vehicles in the forward direction, that is, moving in the same direction as itself, as well as the reverse direction, that is, moving in the opposite direction. For example, vehicle A in Figure 2 should account for the vehicles in the forwarding direction (vehicle A's direction) as well as the reverse direction (vehicle B's direction).
An example of acquiring the real-time traffic density.
The beacon message has the location, the direction, and the TRC fields. The location field is the current geographical position of the vehicle acquired by the GPS, and the direction field is the movement direction in terms of the azimuth angle (0 to 359 degrees) (see Figure 3) of the vehicle. The TRC field is the number of the vehicles moving on the opposite-direction lane of the same road. Each vehicle also maintains the road information (RI) to store the road vehicle density computed from the information in beacons. This is later used in the proposed routing scheme as a routing metric. The fields of the RI are shown in Table 1. The RI is created when the vehicle enters the road and is updated upon receiving a beacon from a vehicle moving in the opposite direction.
Road Information (RI).
The direction of a vehicle in terms of the azimuth angle.
When a vehicle receives a beacon, the value of the number of reverse cars field in its RI is increased by one. For example, as shown in Figure 2, vehicle A counts the number of beacons it receives from the opposite lane. Then, the vehicle computes its own TRC from the number of reverse cars value in its RI to estimate the road vehicle density and sends a beacon containing the computed TRC to its one-hop neighbours. We denote this by 
So far, we have considered only the number of cars in the forward direction lane. Next, we obtain the number of cars in the opposite direction lane. This is denoted by 
3.2. Source Routing Protocol
In our proposed routing protocol, we adopt the source routing mechanism, so the route information has to be gathered from the source to the destination. This is achieved by making the source broadcast Route Request (RREQ) messages in each of which the route information is recorded. Here, the route information is the list of the roads visited by the RREQ message. Once the destination has collected RREQ messages, it chooses the best route in terms of the number of hops (i.e., the number of roads visited) and the road vehicle density and sends a Route Reply (RREP) message with the route information back to the source. If we think of vehicles as the signal carrier of a link, the road vehicle density is similar to the bandwidth in concept. In most QoS routing protocols, bandwidth is the link metric to decide the bottleneck link of a route. Therefore, in our proposed VANET routing protocol, we consider the road vehicle density as the routing metric to determine the bottleneck link of a route. Note that the route information is not vehicle-by-vehicle but road-by-road information. That is, in each data packet, the list of roads to be visited is included. And, on each road, data packets are delivered by using the greedy forwarding approach of the geographical routing.
We introduce new fields in the RREQ message and in the routing table entry as shown in Table 2.
New fields in the RREQ message and the routing table entry.
When a source node wishes to send a data packet, it first checks whether it has the routing information to the destination. If it does not have the information, it generates an RREQ message with RoadList, RoadHop, and MinDensity and broadcasts the RREQ message to its one-hop neighbours after inserting the identity of the road to which it belongs into the RoadList field. The RoadList field in the RREQ message is appended by vehicles along the path until the RREQ reaches the destination. The MinDensity field is used in the RREQ message so that the roads with higher density can be selected in a route to offer a reliable and stable routes. The value in the MinDensity field implies the smallest road vehicle density that the RREQ message has encountered.
Upon receiving an RREQ message, an intermediate vehicle operates as follows.
If the source address in the RREQ message is not in its routing table and the identity of the road which the vehicle belongs to is not in the RoadList, then a new entry with the source address, the road IDs in RoadList, RoadHop, and MinDensity of the RREQ message, is created in the routing table. And the identity of the current road is appended to RoadList, and MinDensity is changed to the RTD value in its RI if the RTD value is smaller than MinDensity, and, then, the vehicle forwards the modified RREQ message. If the source address exists in the routing table and the RoadList in the RREQ message is not equal to that in its routing table, then RoadHop is compared. If the RoadHop in the RREQ message is greater than k (
When the destination receives the first RREQ message, it waits for the RREQ messages forwarded through the other paths for a given time duration. Then, it selects the route with the highest MinDensity and sends an RREP message with the selected route information back to the source.
Once the source vehicle receives the RREP message, it sends data packets to the destination through the route (i.e., RoadList) in the RREP message by using the source routing mechanism; that is, data packets are delivered through the roads in the RoadList of the RREP message. On each road of the chosen route, the greedy forwarding is used for the delivery of data packets to the next-hop road.
The operation of the proposed routing protocol at a node that has received an RREQ message is depicted in Figure 4.
The operation of the proposed VANET routing protocol at a node upon receiving an RREQ message.
4. Performance Evaluation
In order to evaluate the performance of the proposed VANET routing protocol, we implemented our routing protocol by using the NS-2 simulator [17] and compared it with the legacy GPSR [5] and A-STAR [9]. Note that most of the geographical VANET routing protocols are mere variants of GPSR and do not differ much in their essential operations. We did not compare ours with VADD [10] since VADD assumes the global knowledge of the average vehicle traffic and hence always attains the optimal route based on the given information. In contrast, we attain the real-time traffic information and use this as a routing metric.
4.1. Simulation Setup
The simulation area is set to 3000 m × 3000 m, and the road layout is a grid pattern with the length of each road being 300 m. Roads are placed on 10 vertical and 10 horizontal lines. The vehicles on a road are randomly deployed, and the total number of vehicles is varied from 150 to 300. In order to simulate the heterogeneous road vehicle density environment, first, 100 out of 150 vehicles, 140 out of 200 vehicles, 180 out of 250 vehicles, and 200 out of 300 vehicles are randomly placed over all the roads, respectively. Afterwards, 50 out of 150, 60 out of 200, 70 out of 250 and 100 out of 300 vehicles are randomly deployed over the randomly chosen 5 roads in each case. These latter 5 roads are those with high vehicle density.
The vehicle speed is varied from 20 km/h to 55 km/h. The total simulation time is set to 200 seconds, and the transmission range of each vehicle is set to 250 m. The values of α and k are set to 0.5 and 2, respectively. And the beacon interval is set to 1 second.
Source and destination vehicles are chosen from the vertical roads. Three sources are randomly chosen from 5 endpoints of 10 highest vertical roads and three destinations from 5 endpoints of 10 lowest vertical roads. That is, data packets are sent downwards from the highest vertical road to the lowest vertical road, and there are three source-destination pairs. For the sake of simplicity, we have fixed the source and the destination vehicles.
The simulation parameters are summarized in Table 3.
Simulation parameters.
In the following subsections, we show the performance of our mechanism, such as packet delivery ratio, routing overhead, and end-to-end delay, by comparing with A-STAR and GPSR. The packet delivery ratio is the ratio of the successfully delivered data packets to the total number of transmitted data packets. The routing overhead is the overhead caused by routing-related control messages such as RREQ, RREP, and beacon messages. And the end-to-end delay is the average delay experienced by a successfully delivered data packet.
4.2. Packet Delivery Ratio
Figure 5 shows the packet delivery ratio for various vehicle speeds. In all cases, our mechanism significantly outperforms both A-STAR and GPSR. As the vehicle speed increases, the packet delivery ratio of A-STAR and GPSR decreases. On the other hand, ours is not affected by the vehicle mobility. The reason is that our mechanism works based on road-by-road forwarding and GPSR on vehicle-by-vehicle forwarding. Higher vehicle mobility affects the performance of vehicle-by-vehicle forwarding more than that of road-by-road forwarding.
Packet delivery ratio versus vehicle speed.
From Figure 6, we can see how the number of vehicles, that is, the overall vehicle density, affects the performance of all the mechanisms in terms of packet delivery ratio. Higher vehicle density increases the packet delivery ratio of A-STAR and GPSR. However, overall, ours outperforms both schemes, and as the vehicle density decreases, the performance difference between those schemes gets larger because both A-STAR and GPSR have higher chances of selecting roads with low vehicle density.
Packet delivery ratio versus the number of vehicles.
Figure 7 depicts the packet delivery ratio for various CBR rates. The proposed scheme achieves higher packet delivery ratio than both A-STAR and GPSR in all cases. Besides, GPSR yields lower packet delivery ratio for higher CBR rates. This is because the perimeter mode of GPSR increases the possibility of collisions for higher CBR rates.
Packet delivery ratio versus CBR rate.
4.3. Routing Overhead
Figure 8 shows the routing overhead per vehicle as a function of the number of vehicles. The routing overhead per vehicle is the normalized routing overhead obtained by dividing the routing overhead by the number of vehicles. The routing overhead per vehicle of the proposed scheme is kept very low for all cases. In GPSR, as the number of vehicles increases, the number of successfully delivered messages increases; that is, the denominator of the routing overhead increases, and, as a result, the routing overhead decreases in GPSR. Therefore, in GPSR, the routing overhead per vehicle decreases as the vehicle density increases. On the other hand, ours does not change much since the packet delivery ratio of our mechanism is almost the same for all cases.
Routing overhead per vehicle versus the number of vehicles.
4.4. End-to-End Delay
We plot the end-to-end delay results in Figure 9. As expected, the end-to-end delay of GPSR is the largest since it suffers from finding routes that are well connected. Our proposal gives similar, but a slightly higher, end-to-end delay compared with A-STAR. This comes from the fact that the proposed scheme attempts to find paths with higher vehicle density roads, albeit they may be longer, so that it can successfully deliver packets. This is evidenced by the highest packet delivery ratio of the proposed scheme, as shown in Figures 5, 6, and 7.
End-to-end delay versus the number of vehicles.
4.5. Impact of Parameters α and k
In this subsection, we discuss the effect of varying some of the parameters that are used in our proposal: α (Section 3.1 (2)) and k (Section 3.2). Figure 10 shows the packet delivery ratio with variable α. The parameter α is used to compute the moving average of road traffic density (RTD); as α increases, the recent measurement is reflected more to the average RTD. When the vehicle speed is low, it is advantageous to keep a large α to reduce the spikes. When the vehicle speed is high, it is better to keep a smaller α. Therefore, the overall performance should increase if we control α according to the variance of vehicle speed. In other words, if the vehicle speed is high, then we should keep α small to smoothen the spikes and possible miscomputation. This control should give benefit to the PDR.
Packet delivery ratio versus vehicle speed with variable α.
Figure 11 shows the packet delivery ratio as a function of the number of vehicles with variable k. The parameter k decides how much the routing protocol allows the path to diverge from the shortest path. If k increases, the routing overhead would increase, but the PDR should also increase since a route avoids disconnected roads as shown in Figure 11. However, a larger k causes higher routing overhead as shown in Figure 8, so there exists a strict tradeoff.
Packet delivery ratio versus the number of vehicles with variable k.
From the above simulation results, we conclude that our proposed VANET routing mechanism works better than A-STAR and GPSR in the urban environment with heterogeneous roads with various vehicle densities. The main drawback of our scheme is the added complexity in computing the road vehicle density and the reflection of the obtained density information to the routing algorithm. However, this is also the main advantage of ours since it allows to improve the effectiveness of the routing; that is, routing paths are chosen so that they can avoid disconnected roads, resulting in reliable routing paths.
5. Conclusion
The VANET, which is an essential technology in the realization of ITS, has key challenges such as intermittent link connection duration and high packet loss ratio. Therefore, routing protocols that provide stable routes are required. In this paper, we proposed the idea of improving network connectivity by using the roads with higher vehicle density in establishing routes. In order to evaluate the performance of our proposed routing mechanism, we compared ours with A-STAR and GPSR through NS-2 based simulations and showed that our mechanism outperforms A-STAR and GPSR in terms of packet delivery success rate and routing overhead.
Footnotes
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
Acknowledgments
This research was supported by the MSIP, Korea, under the ITRC (Information Technology Research Center) support program (NIPA-2013-H0301-13-1002) supervised by the NIPA (National IT Industry Promotion Agency). This work was also supported by the National Research Foundation of Korea Grant funded by the Korean Government (NRF-2013R1A1A1006823).