A Survey Of Broadcasting Based Routing Protocols For Vanets

A Survey Of Broadcasting Based Routing Protocols For Vanets

Priyanka Tirmare1, S. B. Mule2

Department of Electronics & Telecommunications, Sinhgad College of Engineering, Pune, India

Abstract

Vehicular adhoc networks (VANETs) are emerging as a potential technology for intelligent transportation systems (ITSs). In VANETs, fast moving vehicles form a temporary network between themselves and exchange data. Several protocols have been proposed for the communication between the moving vehicles. This paper studies different type of broadcasting protocols that are used in VANETs. These protocols can be categorized mainly into flooding/ beaconing type and selective type.

In beaconing type of protocol, a moving object propagates the data it carries to encountered objects, and obtains new data in exchange. An epidemic protocol is one such protocol that involves selective beaconing of messages based on certain relevancy parameters.

Event driven or aperiodic message transmission is known as selective broadcast where only a single node is selected from the many nodes in the surrounding region.

We show how different protocol types satisfy the requirements of different scenarios faced in VANETs. The practical application of these protocols will involve hybrid of these main schemes as VANETs become a reality.

1. Introduction

   INTELLIGENT transportation systems (ITSs) use advanced wireless communication technologies to enhance the current surface transportation systems. Their applications include electronic toll collection, emergency notification, traffic congestion notification, parking lot management, etc. In Inter-Vehicle communication (IVC) systems, broadcast is a frequently used method. Possible applications relying on broadcast include sharing emergency, traffic, weather, and road data among vehicles and delivering advertizements and announcements. These applications generate packets of various lengths at different rates. For example, accident warnings are short packets that are generated infrequently. Warning packets reporting slippery road conditions are generally short, but these packets may be sent in bursts. Finally, advertisement packets of restaurants or hotels can be broadcast in very long packets that carry pictures, directions, or even short

   videos. The above applications have been found to work on efficiently certain type of protocols proposed in the literature. At the same time, people have tried to devise protocols that will work equally well in different scenarios and applications.

   Currently, vehicular communications are based on dedicated short-range communications (DSRC) technology, which operates at 5.9-GHz band and offers higher data rates and a communication range up to 1000

   m. It is in the process of standardization as IEEE 802.11p. Therefore, most of the communication protocols proposed in the literature are DSRC-based.

   In recent years, many ITS projects such as the Cooperative Vehicle-Infrastructure Systems Project, the Safespot project, the Coopers project in Europe, the VII project in U.S., and the advanced safety vehicle-phase 2 project in Japan have been undertaken by both the automotive industry and the academia all over the world. Apart from this, several working groups such as eSafety, COMeSafety, and the Car2Car Communication Consortium have been established to support the development, deployment, and use of intelligent- integrated road safety systems.

2. Discussion

   Figure 1

   The categorization of protocols is shown in figure 1 .

   1. Beaconing type broadcasting

      In Beaconing type broadcasts, the aim is to disseminate relevant information to other vehicles in a single-hop fashion. No startegies are formed to further disseminate the information to one vehicle to other and so on. The transfer of information is based on the source of the information or the direct recipient(s) of the same. These type one-to- many broadcasting can be further categorized into different forms based on the transmission strategies.

      1. Transmission strategies

         The flooding strategy: In VANETs, flooding the network blindly is the first approach to achieve

         broadcasting since flooding can operate without local or global topology information. This involves the vehicle to communicate all the known events to all the peers within communication range or simply flood the region with information. However, if pure flooding is employed, it has been shown that serious redundancy, contention, and collision problems occur as a result of flooding.

         The proximity strategy: This involves the vehicle to simply inform only the peers within a certain distance of the location of the event. But this strategy may prove to be unsuccessful under certain scenarios.

         The epidemic strategy: The epidemic routing involves the vehicle to only inform a certain number of peers. This is also called the Situation-adaptive beaconing that basically depends on the vehicles own status and the road traffic situation in consideration with the currently offered load. Accordingly, there are schemes for rate adaptation, depending on the vehicles own movement, depending on surrounding vehicles movement and the ones depending on both [3]. Content-Based Dissemination protocol for VANETs is one such protocol that involves selective beaconing of messages based on certain parameters. Opportunistic Data Dissemination in Mobile Peer-to- Peer Networks is another such protocol that disseminates data based on spatio-temporal factors [2]. This mechanism inspired by the field of epidemiology, where vehicles with a certain piece of information act as disease carriers by contaminating (i.e., transmitting that information to the nearby vehicles along their routes.

      2. Content-Based Dissemination: An Epidemic protocol

         The approach is to maintain a suitable dynamic dissemination area is based on a concept of what is called EP, which represents the probability that a vehicle meets a certain event [1]. If the EP of an event for a certain vehicle is high, then the event could be considered particularly

         relevant for the vehicle because it is likely that the vehicle will encounter that event. Thus, each vehicle would decide dynamically if it should rediffuse the information about an event received or not. The main objective is to ensure that each vehicle for which an information is interesting will receive it. Thus, the use of the EP to determine vehicles that have to rediffuse an information they received allows diffusing the messages toward the vehicles for which such messages may be relevant.

         Using the mobility vector of the vehicle in relation to the event, the position of the vehicle, and the position of the event, we can deduce four elements that have an influence on the encounter probability [1]:

         1. The geographical distance between the vehicle and the event when the vehicle is expected to be at the closest distance (d). The value of d can be computed as

            where vehicle_event is a segment linking the location of the vehicle and the location of the event, and vehicle_Nevent is a segment linking the location of the vehicle and the closest point to the event regarding the direction marked by the mobility vector of the vehicle in relation to the event.

         2. The difference between the current time and the time when the vehicle will be closest to the event (t). The value of t can be computed by considering the distance between the vehicle and the closest point to the event and taking into account the temporal dimension of the mobilityvector of the vehicle in relation to the event.

         3. The difference between the time when the event is generated and the moment when the vehicle will be closest to the event (g). This information is obtained from the message received (considering the events generation time stored in the CurrentPosition attribute) and the t previously computed.

         4. The angle between the vehicles direction vector and the events direction vector (represented by a colinearity coefficient c). For direction-dependent events, this allows us to determine whether the directions of the vehicle and the event match. For non direction- dependent events (identified because the DirectionRefPosition attribute is null), c is set to 0.

         Once these d, t, g, and c values have been calculated, they are used to estimate an EP between a vehicle and an event.

         Thus, the higher the value of the EP, the higher the likelihood that the vehicle will meet the event. The EP is a value between 0 and 1.

   2. Selective or Multi-hop broadcasting

      Event driven or aperiodic message transmission is triggered by detection of any unwanted situation such as accident on roads, unsafe road surface, etc. As a result, multihop broadcasting is used to realize the dissemination of event driven warning messages. The vehicle that detects the event immediately sends a warning message to the following vehicles allowing the drivers to take appropriate action. Because of limited transmission range of the vehicles, the message needs to be relayed by intermediate vehicles to cover an area of interest. As a result, multihop broadcasting is used to realize the dissemination of event driven warning messages. Here, a protocol is established between the sender/ source and the possible candidates for the receipt of the data. Based on the protocol, only a single node is selected from the many nodes in the surrounding region and the sender sends the data to that particular node. The process is repeated where the receipt node acts as the sender and looks for the optimal node to further disseminate the information. The aim here is to disseminate the information in the shortest possible time and therefore to select the best candidate for carrying the information further.

      Partition based protocols have been proposed that prove effective in selecting the right node for transmitting the information. Here the transmission region is partitioned into segments and nodes in the rejected segments are eliminated.

      In Binary-Partition-Assisted MAC-Layer Broadcast for Emergency Message Dissemination (BPAB) [4] in VANETs, researchers introduce a binary-partition based approach which is applied iteratively in order to find a furthest segment containing potential relay nodes. Each iteration takes a segment as input, divides it into two equal halves. Black burst is used to select the potential half which is alsopassed as the input segment for next iteration. The other half is eliminated from further consideration. The segment obtained after certain number of iterations is a narrow and farthest one.

      An Ad-Hoc Multi-Hop Broadcast Protocol for Inter-Vehicle Communication Systems (AMB) has been proposed in which is a black-burst based multihop broadcast protocol for vehicular networks. In the proposed protocols, the functions of forwarding and acknowledging the broadcast packet are assigned to only one vehicle by dividing the road portion inside the transmission range into segments and choosing the vehicle in the furthest nonempty segment without a priori topology information, ie, without knowing the identification of its neighbours.

      1. Intersection Broadcast

         In this section, we discuss efficient IEEE 802.11-based

         multihop broadcast protocols, namely urban multihop broadcast (UMB) and ad hoc multihop broadcast (AMB), for vehicular networks. The proposed protocols are designed to address the broadcast storm, hidden node, and reliability problems in multihop broadcast.

         The proposed protocol handles intersections without infrastructure support when there is line of sight among all road segments. In the AMB protocol, a new intersection broadcast mechanism is proposed, where vehicles find the best candidate among themselves to branch the packet dissemination to other road segments. The vehicle closest to the intersection is a good candidate for this function because it is likely that vehicles closer to the intersection have a better coverage of the other road segments.

         The new intersection broadcast mechanism is composed of two phases. The first phase is choosing a hunter vehicle, which tries to select the closest vehicle to the intersection. For this purpose, we will define an intersection region. In the second phase, the hunter vehicle initiates a search to find the closest vehicle, and in response to this search, vehicles reply with a black- burst according to their distance to the intersection. Once the hunter vehicle selects the closest vehicle to the intersection, this vehicle becomes responsible for branching the message to the other road segments.

         1. Selecting the Hunter Vehicle:

            In the directional broadcast protocol, as described in Section II, the dissemination of messages is controlled by a subset of vehicles in the network. These vehicles are assigned the function of forwarding the message after the RTB/CTB handshake. Since each of these vehicles chooses a new vehicle in the transmission range R to forward the message, at least one vehicle is chosen in every R meters. Keeping this fact in mind, we have defined an intersection region around each intersection starting at R/2 meters before and extending to R/2 meters beyond the intersection. Note that at least one vehicle is chosen inside this region during the directional broadcast when the intersection region length is at least R meters. As shown in figure 2 [4], the first vehicle chosen in the intersection region becomes the hunter vehicle. Another reason to choose the intersection region starting at R/2 meters before the intersection is as follows: Since the hunter vehicle tries to select a closer vehicle than itself, its transmission range should cover the points closer to the intersection than itself. When we use a transmission region with the proposed borders, in the worst case, the hunter vehicle is R/2 meters away from the intersection, and it can cover the points up to R/2 meters away at the other side of the intersection.

      2. Directional Broadcast

Figure 2

1. Selecting a Vehicle for Branching the Packet Dissemination:

Having being selected inside the intersection region, the hunter vehicle sends an RTB packet that is different from the regular RTB, as defined in Section II-A. This new type of RTB packet that is employed to select the closest vehicle to the intersection is called intersection RTB (I-RTB). The black-burst response to an I-RTB is different from the response to a regular RTB that is employed in the directional broadcast; that is, when vehicles receive a regular RTB, the furthest vehicle from the source sends the longest black-burst. On the other hand, when vehicles receive an I-RTB, the vehicle closest to the intersection sends the longest black-burst.

An example of intersection handling is illustrated in figure

1. In this figure, since vehicle A is outside the intersection region, it uses the directional broadcast to reach vehicle B. Vehicle B is the first selected vehicle inside the intersection region; therefore, it becomes the hunter and initiates a vehicle selection process by sending the I-RTB packet. Being closest to the intersection, vehicle C sends the longest black-burst and then the CTB packet. After vehicle B assigns the function of branching the packet dissemination to vehicle C, vehicle C initiates directional broadcasts to east, north, and south directions. As a special case, if the hunter vehicle becomes unsuccessful in selecting a vehicle, the hunter vehicle itself ecomes responsible for forwarding the packet to the other road segments.

It is a binary-partition based approach which is applied iteratively in order to find a furthest segment containing potential relay nodes. Each iteration takes a segment as input, divides it into two equal halves. Black burst is used to select the potential half which is also passed as the input segment for next iteration. The other half is eliminated from further consideration. The segment obtained after certain number of iterations is a narrow and farthest one. Note that at each iteration the segment size is decreased multiplicatively by a factor of 2. It implies that very few number of iterations (same as the number of binary divisions) is needed to obtain a narrow segment. The process starts by considering the coverage area, R as the input segment for the first iteration. If we apply N binary divisions iteratively, then the final output segment will be of width R/2N.

During multihop broadcasting, presence of hidden node can not be ruled out. Consequently, packet delivery to all nodes can not be guaranteed. In order to ensure reliability during safety message dissemination, we have used two MAC layer control packets RTB (Request-To- Broadcast) and CTB (Clear- To-Broadcast). The basic mechanism behind forward node selection process is described as follows: Before broadcasting the warning message, source node transmits Request-to-Broadcast (RTB) packet specifying its geographical position and message propagation direction. Nodes which are behind the sender along the message propagation direction begin to participate in the forward node selection procedure and execute the binary-partition algorithm.

As mentioned above, in the first iteration of binary partition algorithm, the coverage area, R is divided into two equal parts having width R/2 each. Out of the two parts, the part closer to the sender is termed as Inner Segment and the other part is termed as Outer Segment. This terminology remains same in all iterations. Here, one segment is eliminated letting the other segment to become input in the next iteration. Outer segment has higher priority because it is away from the sender. But in case it is devoid of nodes, inner segment is chosen. The selection of appropriate segment is carried out by using black burst approach.

Black burst is emitted by nodes in the outer segment for one slot duration [5]. At the same time, nodes in the left segment sense the channel. On detecting black burst they exit the contention assuming presence of nodes in the outer segment and thus the inner segment is eliminated. Outer segment, if contains at least one node, is chosen automatically as the potential input segment for 2nd iteration.

If no black burst is detected, it implies that the outer segment is devoid of nodes and hence inner segment

becomes the potential input segment for 2nd iteration. In this manner, the binary-partition algorithm proceeds outputting segments of width R/4, R/8.in subsequent iterations. It terminates by producing a segment of width R/2N as the output of last iteration, where N is the total number of binary divisions.

Nodes in the final output segment choose a random back off time from a CW = {0, 1…cw-1}, where cw is a parameter which is set during simulation. The back off timers implementation conforms to the CSMA/CA policy of IEEE 802.11. According to this policy, the timers are decremented during idle channel. Once the channel is found busy, countdown stops and the timers resume again after the channel has been idle for a DIFS period.

Node that times out first transmits Clear-to-Broadcast (CTB) packet specifying its ID in the header.

The contending nodes, if any, overhearing a CTB packet destined to the same source, exit the random contention phase. Source node on receiving a valid CTB packet transmits a MAC layer broadcast frame containing the emergency message. The header carries the ID of the chosen relay node. The node which finds its ID in the header relays the message in the next hop along the propagation direction using the same procedure as

sender. In the first iteration, the area inside transmission range R is divided into two segments of size R/2. Nodes in the outer segment start black burst transmission. On detecting black bursts nodes in the inner segment exit the process.

Now in the 2nd iteration, the outer segment is divided into two parts of size R/4. Here, inner segment is selected as no black burst is detected due to lack of nodes in the outer segment. In the 3rd iteration, nodes in the inner segment detect black burst and exit the contention. The outer segment becomes the final segment having width R/23. It contains the candidate relay nodes which then contend with each other and one of them will send CTB to the sender.

1. Conclusion

   In this paper, we have attempted to present varied approaches of routing mechanisms proposed to meet VANETs requirements. In particular, we choose broadcasting based protocols that are widely explored due to their more realistic approach to the on-road situations. We have shown how two different methods of broadcasting- beaconing and selective can have special benefits under different scenarios. The practical application of these protocols will involve hybrid of these main schemes as VANETs become a reality.

2. References

described above.

Figure 3

1. Nicolas Cenerario, Thierry Delot, and Sergio Ilarri, A Content-Based Dissemination Protocol for VANETs: Exploiting the Encounter Probability, IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 12, NO. 3,

   SEPTEMBER 2011

2. Ting Zhong, Bo Xu, Ouri Wolfson, Disseminating Real- Time Traffic Information in Vehicular Ad-Hoc Networks,, 2008 IEEE Intelligent Vehicles Symposium

3. B. Xu, A. M. Ouksel, and O. Wolfson, Opportunistic

   Let us consider a suitable example shown in figure 3 [5] to explain the operation of BPAB for N=3.

   Iteration	Black Burst	Selected Segment	Width
   1st	Yes	Outer Segment	R/2
   2nd	No	Inner Segment	R/4
   3rd	Yes	Outer Segment	R/8

   Table 1

   Suppose the nodes have received RTB packet from the

   resource exchange in inter-vehicle ad-hoc networks, in

   Proc. 5th IEEE Int. Conf. MDM, 2004, pp. 412.

4. Binary-Partition-Assisted MAC-Layer Broadcast for Emergency Message Dissemination in VANETs, Jagruti Sahoo, Eric Hsiao-Kuang Wu, Pratap Kumar Sahu, and Mario Gerla, IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS, VOL. 12, NO. 3, SEPTEMBER 2011.

5. Black-Burst-Based Multihop Broadcast protocols for Vehicular Networks, Gökhan Korkmaz, Eylem Ekici, and Füsun Özgüner, IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 56, NO. 5, SEPTEMBER 2007