Research Article
Selective Road Hazard Message Dissemination Protocol for VANET
Computer Studies, Rajalakshmi Engineering College, Thandalam, Chennai, India
Sheila Anand
Computer Studies, Rajalakshmi Engineering College, Thandalam, Chennai, India
Intelligent Transportation System provides an emerging technology called Vehicular Ad hoc NETwork (VANET) that enables vehicle to exchange safety and comfort related information. VANET is formed by vehicles which are equipped with on-board communication equipment capable of sending and receiving messages (Zhang et al., 2010). VANET communication can be broadly classified into two categories: Vehicle-to-Vehicle (V2V) and Vehicle-to-Road side units (V2R) (Kumar and Dave, 2012). In V2V communication, the vehicles are used as relay nodes to forward messages between themselves. In V2R communication, Road Side Units act as relay nodes to transmit the information to the vehicles. RSUs are fixed infrastructures which have sufficient memory to store safety and comfort information and have the capability of transmitting the information to vehicles and neighboring RSUs (Ali and Chan, 2011).
One of the principal goals of vehicular communication is to enhance driver and passenger safety by focusing on the development of effective protocols for quick and timely exchange of warning and other safety related messages. VANET applications are broadly classified into safety and comfort applications (Toor et al., 2008). Safety related applications disseminate messages related to traffic congestion, accident warnings, accident reports, emergency warnings, lane-changing assistance, intersection coordination, traffic-sign-violation warnings and road-condition warnings. Comfort applications would include reporting weather information, location of gas stations or restaurants, media streaming, price information, web access (Bi et al., 2009; Berlin and Anand, 2011).
Since, each vehicle has only few hundred meters of communication range (Suryawanshi et al., 2011), V2V communication would need to use multi hops to deliver messages to distant vehicles. In areas where vehicular traffic is sparse, V2V communication would not be feasible. Safety or hazard related information is always critical information that needs to be disseminated in a timely and effective manner to enable drivers to take appropriate safety measures. Moreover, as VANET has irregular network density and frequent dynamic topology of vehicles, enabling speedy delivery of safety information to a specific direction is a challenging task. Due to the rapid movement of vehicles, maintaining a stable routing path would be very difficult in VANETs.
In this paper, we focus on disseminating road hazard information to vehicles travelling on highways where the vehicular density may or may not be high.
RELATED WORK
Safety messages can be disseminated using V2V or V2R communication. V2V communication can use broadcast or selective forwarding approaches. Simple broadcast approach would increase network load, network congestion, packet loss rate and end-to-end delay (Wisitpongphan et al., 2007). Therefore selective forwarding approach is commonly proposed to propagate safety messages to other vehicles by using suitable vehicles as forwarders (Yu and Heijenk, 2008; Akkhara et al., 2008; Lee and Chen, 2010). Some of the key research work related to V2V communication for disseminating safety messages is first discussed.
Yang and Chou (2008), the authors have proposed an event driven protocol for disseminating emergency warning messages to other vehicles. The furthest vehicle is chosen as forwarder to cover the large number of vehicles travelling toward the emergency event. The authors pointed out that they could achieve minimum number of re-transmission of emergency message with few intermediates and low delay. In REACT (Van de Velde et al., 2006), the authors have focused on identifying best forwarder node for disseminating alert message to other vehicles. When a vehicle receives alert message, it would choose suitable forwarder from the neighbor list maintained by the vehicle. If the distance between neighbor and destination vehicle is smaller than the distance between source vehicle and destination, then the particular neighbor would be taken as best forwarder node. The authors could achieve fast delivery of alert messages to destination vehicle with high certainty. In both these approaches, vehicles need to exchange and maintain information about each other using hello and other messages.
Li et al. (2011) have proposed an opportunistic broadcast protocol for disseminating warning messages with the intension of increasing packet reception ratio, fast delivery of messages and also to achieve less number of transmissions of warning message. Each vehicle would calculate broadcast back off delay before broadcasting the warning message to neighbors. If the distance between the vehicle and the previous forwarder is high, then it would become as forwarder node. The authors compared the performance of this protocol with other broadcast suppression techniques such as Slotted-p, CBD and Ideal and they pointed out that this work performed well and satisfied all the design criteria. However, this approach would not work well for roads with less vehicular density and have suggested extending this work for such disconnected areas.
Natarajan and Skelton (2010) presented a Risk Notification Message Dissemination Protocol (RNMDP) for disseminating Risk Notification Messages (RNMs) to the vehicles approaching the risk zone. The node which receives RNMs message would wait for a rebroadcast wait time before broadcasting the message to its neighbors. Priority would be given for the node which is far away from the sender and travelling towards risk zone. The authors compared this work with flooding and could achieve good results in highly dense areas.
Lee et al. (2010) have proposed a selective forwarding scheme to propagate alert messages. The authors have focused on finding suitable forwarder nodes based on the mobility information received from its neighbors. The vehicle travelling in the same direction of source node, smaller relative velocity, larger distance value between source node and itself would be considered as a suitable forwarder node. Each node selects two forwarder nodes for propagating alert message. However, only one forwarder would be allowed to propagate the message; the other one would be suppressed based on the value of message holding time specified in alert message. The authors have compared the performance of their proposed scheme with other broadcast suppression techniques and could find better performance on the suppression of rebroadcasting messages than the other techniques.
Tseng et al. (2010) proposed a Vehicle-Density based Emergency Broadcast (VDEB) scheme for broadcasting emergency messages using ring based approach. Each vehicle maintains a neighbor table to know the vehicles in its transmission range. When the emergency event is observed by a vehicle, then it divides its transmission range into number of rings. The vehicle which is in the outermost ring with waiting time zero would act as a forwarder. The authors pointed that the simulation results produced good delay and very reasonable overhead. This approach also pre-supposes that the vehicular density is reasonable or high to propagate the messages.
Schwartz et al. (2011) have presented a Simple and Robust Dissemination (SRD) using vehicle-to-vehicle communication on dense and sparse networks. In dense network, the number of messages being broadcast is suppressed using broadcast suppression techniques whereas in sparse networks, store-carry-forward techniques are used. The authors have compared the performance of this scheme with DV_CAST (Tonguz et al., 2010) protocol.
Research work related to use of RSU for disseminating safety messages is next discussed. Sou and Tonguz (2011) have suggested two possible ways to deploy RSUs: Ad hoc mode and Infrastructure mode. In Infrastructure mode, the RSUs would be linked via physical connection such as high speed fiber link communication. The initial deployment cost and maintenance of such a scheme would be high. Ad hoc based deployment of RSUs however does not require physical connection. They have proposed the use of RSUs for disseminating safety messages. The authors have investigated the routing performance when a limited number of RSUs are deployed and their results show a significant improvement in VANET connectivity and performance.
Mershad et al. (2012) have proposed CAN DELIVER (Carry and forward mechanism for dependable message delivery) using RSUs. They have suggested the use of virtual waypoints deployed at intersections for sending packets to distant destinations. The source vehicle would pass the message packet to virtual waypoints for forwarding to the RSU nearest to the destination vehicle. The RSU would forward the packet to the destination vehicle. The authors have compared the work with other existing protocols such as TrafRoute (Frank et al., 2010), SADV (Ding et al., 2007) and RBVT-R (Nzouonta et al., 2009). While the authors have concluded that CAN DELIVER produces better results than other protocols, it needs deployment of both RSU and virtual waypoints at intersections.
Our proposed approach suggests the use of an effective combination of V2R and V2V communication to deliver safety information relating to road hazards such as road blocks, tree fall, boulders on road and other obstacles. It is proposed to use selective forwarding in V2V communication to avoid broadcast storm and packet loss. It is also proposed to selectively disseminate the road hazard messages only to vehicles likely to encounter the hazard. The proposed approach is discussed in detail in the next section.
PROPOSED SELECTIVE ROAD HAZARD MESSAGE DISSEMINATION PROTOCOL
The Selective Road Hazard Message Dissemination Protocol (SRHMDP) has been proposed for disseminating road hazard information to distant vehicles approaching the road hazard location on highways. In highways, where vehicular traffic is sparse, V2V communication would not be a viable option to transmit hazard_messages. RSUs are fixed equipments capable of transmitting hazard_messages to the vehicles travelling towards hazard location with minimum delay. It is assumed that each vehicle is equipped with an On Board Unit (OBU) device capable of wireless communication, GPS receiver to obtain the positioning information and sensors for detecting various types of road hazards. It is further assumed that the road hazards are detected by the sensors and this information is sent to OBU. The information available with OBU is used by the protocol.
Previous related work shows that RSUs can be successfully deployed to improve VANET connectivity in areas with sparse vehicle traffic. For cost efficiency purposes, the protocol assumes that the interspacing between the RSUs is relatively high. However, it can be reasonably assumed that the Communication Range (CR) of RSUs would extend to single and multi-lane highways so that all the lanes are within its communication zone. The vehicle which detects the road hazard would need to send the information to RSU. If RSU is within its communication range, it would directly send the hazard_message to the RSU; otherwise it would use V2V communication to locate a suitable forwarder vehicle. The hazard_message would be routed by the selected forwarder vehicle to the RSU which in turn, would broadcast the message to other vehicles to help them to avoid the hazard.
RSUs would broadcast periodic hello_messages to the vehicles and the message would include <RSU_id, GPSlocation_of_RSU, Time>. It is assumed that each RSU (RSU_id) and vehicles (Veh_id) have identifiers that would uniquely identify them. Each vehicle travelling in the transmission range of RSU would receive the hello_message and would reply with the hello_reply message giving details of its <Veh_id, GPSlocation_of_vehicle, Speed, Direction_of_travel, Time>. Each RSU would maintain a Vehicle Table (VT) to store information about vehicles within its communication zone.
The vehicle which detects the road hazard, termed as Hazard Observer (HO), would create a Hazard Message (HM). It is assumed that the sensors would be able to obtain the GPS co-ordinates of the hazard. One of the main design goals of the proposed protocol is to route the hazard_message only in the specific direction to vehicles approaching the hazard location. Since, RSUs are deployed with high interspacing, routing HM directly to a nearest RSU may not be feasible if there is no RSU within the vehicle communication zone. In that case, vehicle detecting the road hazard would find a suitable Hazard Message Forwarder (HMF) vehicle to forward HM to nearest preceding RSU with respect to the hazard location. The HM would be stored by the RSU in a Hazard Table (HT) where the list of hazards along with their location is maintained till the hazard is cleared. It is assumed that RSU would receive information from some appropriate Highway Authority when the hazard is removed. This information would be used by RSU to update HT. The proposed protocol is explained further with sample scenarios.
Sample scenario 1: (RSU is in the vicinity of HO). When a HO finds a RSU within its vicinity, then HO would send the HM directly to the RSU as depicted in Fig. 1.
HM would contain the following information <Veh_id, RSU_id, GPSlocation_of_hazard, GPSlocation_of_vehicle, Speed, Direction_of_travel, Time>Fig. 1a shows that when the vehicle HO detects road hazard (Rh) along its travelling path, it becomes Hazard Observer. Since, the succeeding RSU2 is within the vicinity of HO, HO would send the HM directly to RSU2. RSU2 will verify the HM and transmit the HM to the neighboring preceding RSU with respect to hazard location through vehicles travelling in opposite direction. Figure 1b shows that when the vehicle HO observes road hazard, it would directly send HM to the preceding RSU1 because RSU1 is within the vicinity of HO. RSU1 will verify and in turn transmit the HM to its neighboring RSU and to vehicles which are travelling towards hazard location.
Sample scenario 2: (RSU is located far away; not in the vicinity of HO). If RSU is not in the vicinity of HO, then HO would find suitable forwarder vehicles to forward HM to the preceding RSU with respect to hazard location as shown in Fig. 2.
Fig. 1(a-b): | (a) HO routes HM to succeeding RSU and (b) HO routes HM to preceding RSU |
Fig. 2: | RSUs are located far away from HO |
In the given scenario, HO would detect road hazard and generate HM to send to the preceding RSU1. Since, RSU is not in the vicinity of HO, HO would find suitable forwarder vehicles to send the message. AODV protocol, Amandeep (2012) has been used to forward HM to RSU via., selected forwarder vehicles. AODV routing protocol uses a broadcast route discovery mechanism and dynamically establishes the route from source to destination for sending HM.
The source vehicle HO would first need to discover the route to RSU. It will broadcast Route REQuest (RREQ) packets to the neighboring vehicles. RREQ would include <source_veh_id, dest_id, time>. For the sample scenario, the dest_id would be RSU1. If the neighboring vehicle does not have route for the specified destination, then it would store reverse route with the source_veh_id and broadcast RREQ packet again to its neighbors. This would be continued till RSU1 receives RREQ packet. RSU1 will reply with the Route REPly (RREP) packet giving the possible path to the source vehicle HO. When the neighboring vehicle receives RREP, it would store forward path of RREQ to deliver message to designated destination. This RREP would be routed to the source vehicle through the selected reverse route stored by the neighboring vehicles. Hence, each neighboring vehicle in the routing path of RREP would obtain the forward vehicle and reverse vehicle information for routing HM between the particular source and destination.
Selective forwarding can happen only if the highway has enough vehicles to forward the HM and this procedure minimizes network overhead and improves reliability of the transmission. If there are no other vehicles on the highway, it would not be possible for HO to locate a forwarder node. Then one of two things can happen as shown in Fig. 3.
In the first instance, HO would be able to take a U turn and proceed back in the direction from which it originally came, either in the same lane or in the opposite lane. When it reaches the communication range of RSU1, it would receive the hello_message from RSU1 and reply with the hazard_message. In the second instance, it could proceed further in the same direction in the opposite lane and send hazard_message to RSU2.
The hazard may partially block a multi-lane highway as depicted in Fig. 4.
Fig. 3: | Portion of highway with HO only |
Fig. 4: | HO able to travel forward from hazard location |
The vehicle HO detects road hazard in its travelling path. There is a possibility for the HO to travel forward through other lane in its travelling direction and would send the HM directly to RSU2. RSU2 will in turn transmit the HM to the preceding RSU1 through the vehicles travelling in opposite direction.
Sample scenario 3: (Hazard would not be located by vehicles). One more sample scenario can be considered as given in Fig. 5.
Since, there are no vehicles travelling in the lane where hazard is present, the hazard would not be detected by the vehicles. As the hazard is not in the direction of travel of vehicles, the vehicular movement would also not be affected.
VERIFICATION OF HM AT RSU
Verification of HM is important and essential to know the authenticity of the message. Malicious drivers can send spurious message and legitimate drivers may be duped into taking unnecessary corrective action like alternate routes.
Fig. 5: | Portion of highway only with opposite vehicles |
Hence, RSU would need to verify the correctness of HM before broadcasting to other vehicles. It is assumed that all vehicles would take the HM as authentic only if it receives the HM from RSU.
As RSU updates the hello_reply messages in VT, it would be able to know the vehicles that are within its vicinity and the count of such vehicles. It would be also able to determine how many vehicles have passed the RSU and the direction of travel of these vehicles.
The verification of HM would be done at RSU1 or RSU2 for the scenario shown in Figure 3. RSU1 would have to verify the HM if the vehicle locating the hazard is unable to proceed further and takes a U turn and returns back to RSU1. If the vehicle is able to avoid the hazard and proceed further, then HM would be sent to RSU2 which would do the verification. The verification process steps at RSU1 and RSU2 is explained in detail below.
Verification process at RSU1:
• | RSU1 receives HM from HO. Verification process will begin |
• | From Vehicle Table VT, RSU1 will know whether there are other vehicles travelling on the road and how many vehicles are likely to come across the hazard |
• | If there are other vehicles travelling towards hazard location, then it waits for a time t to receive HM from these vehicles. Time t is calculated as given by Eq. 1: |
(1) |
where, R is the distance between two neighboring RSU, S is the average speed of the vehicles and tr is the HM transmission time to reach RSU1 and would be calculated as shown Eq. 2:
(2) |
where th_rep is computed as the difference between the time RSU1 receives hello_reply from HO and thm is the time RSU1 receives HM from HO
• | During the time t, if it receives the estimated number of HM giving the same hazard location, then HM would be taken as verified else the HM is rejected and the message is removed from HT |
• | If HO is the only vehicle on the road or if the vehicles are travelling only in the opposite direction and not likely to come across the hazard, then: |
• | RSU will wait till it receives a hello_reply from another vehicle travelling in the direction of hazard |
• | It will then wait for time t, as given in Eq. 1 to receive HM from this new vehicle |
• | During this time t, if it receives HM giving the same hazard location from this vehicle, then the message is taken as verified else rejected and the message is removed from table HT |
• | If it receives some other HM that is, with different hazard location, then the verification process repeats |
Verification at RSU2:
• | RSU2 receives HM from HO. Verification process will begin |
• | RSU2 will wait till it receives the same HM that is, the same hazard location, from another vehicle. Then it will take the message as accepted |
• | However, if it receives only a hello_reply from a vehicle travelling in the direction of HO from the hazard location, then it knows the first HM is spurious, so it will reject the HM and remove the message from the table HT |
• | If there are multiple vehicles from which HM can be received, then a preset threshold (TH) is used to verify the count of HM received at RSU. It is feasible to assume that not all the vehicles locating the hazard would send HM to RSU and also some of the HM may be lost due to network transmission error. Hence, it is not possible to receive 100% of HMs. So the threshold can be set at a pre-determined percentage for verification. For example, if TH is set at 50%, then the HM is taken as verified, if messages are obtained from 50% of the vehicles which are likely to send the HM |
If the vehicle traffic is sparse, then RSU has to wait for another vehicle to send HM to verify. It may take a longer time to disseminate information and remove the hazard. As there are no other vehicles travelling on the road, the hazard would anyway not pose a road block causing driver inconvenience. Verification becomes important as the HM may be spurious.
RSUs which verified the presence of hazard will generate a HM with their RSU_id as source. It will send the HM to other RSUs in the preceding direction of hazard location to warn vehicles that are likely to come across the hazard. Vehicles traveling on the highway would take the HM sent by the RSU which verified the presence of the hazard to other RSUs. The HM may be sent to RSUs till a road intersection is reached to enable vehicles receiving the HM to reroute or take other corrective action to reach their destination.
The traffic pattern of the proposed protocol SRHMDP was generated using SUMO (Lan and Chou, 2008) and the performance of the protocol was tested using network simulator NS 2.33. The SUMO simulator produced. tcl file which was given as input to Network Simulator. A fixed node in NS2.33 was assumed as road hazard. The simulation parameters used for testing are given in Table 1.
IEEE 802.11 was used as Medium Access Control (MAC) and the transmission range of vehicles was considered as 250 m (Tatsuaki Osafune et al., 2006). The behavior of the protocol was tested with the interspacing between RSUs is 1 km. The threshold was preset to 50% for verifying HM.
Table 1: | Simulation parameters used in NS2 |
Fig. 6: | Delivery ratio |
The performance of SRHMDP protocol was tested by evaluating the performance metrics such as delivery ratio, end-to-end delay. Delivery ratio is a performance metric which determines the number of messages successfully received by RSU. The performance behavior of the protocol was analyzed for various scenarios discussed earlier and the results are presented in Fig. 6.
For plotting the graph, it was assumed that all vehicles travel at a constant speed of 40 m sec-1. The result shows that the delivery ratio would vary depending on whether the vehicle is within or outside the transmission range of RSU. It can be noted that best delivery ratio is obtained when the vehicle finds RSU within its vicinity.
Hazard message delivery time is calculated as the elapsed time between sending of HM by HO to the time it is received by RSU. Hazard message delivery time has been plotted for different vehicle density and the obtained graph is shown in Fig. 7.
For plotting the graph, it was assumed that all vehicles travel at a constant speed of 40 m sec-1. The delay was calculated for scenarios where hazard is located within and out of the transmission range of RSUs. From the graph, it can be seen that increase in vehicle density does not increase the delivery time as selective forwarding has been used. However, as can be expected, the delivery time is less when the vehicle is within the vicinity of an RSU. The delivery time will also vary depending upon the speed of the vehicle and would be less if the vehicle speed is more.
Fig. 7: | HM delivery time |
Fig. 8: | End-to-end delay |
End-to-end delay is calculated as the elapsed time between sending of hello_reply by HO to the time the hazard message is received by RSU. The end-to-end delay has been plotted for receipt of hazard message at RSU1 and RSU2 for different distances of the hazard from RSU1 for a single vehicle travelling at a speed of 60 m sec-1. The obtained graph is given in Fig. 8.
It can be seen from the graph that if the vehicle HO is nearer to RSU1, time taken for HM to reach RSU1 is less than RSU2. As distance of the hazard location increases with respect to RSU1, time taken for HM to reach RSU2 becomes less. The time becomes the same when the distance of the hazard location is approximately half way between the two RSUs.
In this paper, we have presented the Selective Road Hazard Message Dissemination Protocol for disseminating road hazard information on highways using V2V and V2R. RSUs would enable efficient dissemination of hazard messages to allow vehicle driver to take appropriate corrective action to avoid travel delay and traffic congestion. RSUs provide a cost effective and reliable option with timely delivery of hazard message. Verification of hazard message by RSU is an important aspect which provides protection against spurious and malicious messages. Unlike pure Vehicle-to-Vehicle communication protocols, the proposed solution would be successful on highways with sparse vehicular traffic.