A Novel Approach to Reduce the Effect of Broadcast Storm Problem in Vehicular Ad-Hoc Network

A Novel Approach to Reduce the Effect of Broadcast Storm Problem in Vehicular Ad-Hoc Network

1Sunil K. Vithlani, 2Jayesh D. Dhanesha 3Prof. Hemang Kothari

1, 2 P. G. Students, Marwadi Education Foundation Group of institutions, Rajkot, Gujarat.

3Assistant Professor at Marwadi Education Foundation Group of institutions, Rajkot, Gujarat.

Abstract

Vehicular Ad Hoc Network (VANET) is a form of Mobile Ad Hoc Networks (MANET). The field of VANETs started gaining attention in 1980s and has now been an active field of research and development. VANETs are mainly use in safety applications as well as comfort applications. Most applications targeting VANETs rely heavily on broadcast transmission. When a vehicle rebroadcasts a message, it is highly likely that the neighboring vehicles have already received it, and these results in a large number of redundant messages. This affects inter-vehicle communications, since redundant rebroadcasts, contention and collisions can be largely increased as the no. of vehicles increases. Broadcasting packets may lead to frequent contention and collisions in transmission among neighboring vehicles this problem is referred as the broadcast storm problem. In this paper we have proposed a novel approach, Density Based Rebroadcast-DBR to reduce the effect of broadcast storm problem in VANET. The performance of AODV-DBR is also analyzed in terms of routing overhead, end-to-end delay and throughput for varying node density i.e. 25, 50, 75, and 100 no. of nodes and compared with simple AODV routing protocol. From the comparison we have conclude that with the help of AODV-DBR we can reduce the broadcast storm problem and increase the efficiency of VANET.

Keywords: – VANET, MANET, AODV, MOVE, NS-2, SUMO.

1. Introduction

   Vehicular Ad Hoc Network (VANET) is a new challenging network environment that pursues the concept of ubiquitous computing [1] for future. Vehicles equipped with wireless communication technologies and acting like computer nodes will be on the road soon and this will revolutionize the concept of travelling. VANETs bring lots of possibilities for new range of applications which will not only make the travel safer but fun as well. Reaching to a destination or getting help would be much easier. The concept of VANETs is

   quite simple: by incorporating the wireless communication and data sharing capabilities, the vehicles can be turned into a network providing similar services like the ones with which we are used to in our offices or homes. For the wide spread and ubiquitous use of VANETs, a number of technical challenges exist.

   Mobile ad hoc networks (MANETs) are a type of wireless network that does not require any fixed infrastructure. MANETs are attractive for situations where communication is required, but deploying a fixed infrastructure is impossible. Vehicular ad hoc networks (VANETs) are a subset of MANETs, and represent a rapidly emerging research field considered essential for cooperative driving among communicating vehicles. Vehicles function as communication nodes and relays, forming dynamic networks with other near- by vehicles on the road and highways. While Mobile ad hoc Networks (MANETs) are mainly concerned with mobile laptops or wireless handheld devices, VANETs are concerned with vehicles (such as cars, vans, trucks, etc).

   VANETs can be distinguished from other kinds of ad hoc networks as follows [1]:

   • Highly dynamic topology

   • Frequently disconnected network

   • Sufficient energy and storage

   • Geographical type of communication

   • Mobility modeling and predication

   • Various communications environments

   • Hard delay constraints

   • Interaction with on-board sensors

2. Broadcast Storm Problem

   The broadcast storm problem is a side-effect of flooding [4]. For example, Figure-1 depicts a sample network with five nodes, where if node A broadcasts a packet, nodes B, C and D will receive the packet. Nodes B, C and D will then forward the packet and lastly E will also broadcast the packet. In fact, this case clearly shows the broadcast redundancy inherent with

   flooding. Forwarding the broadcast packet by nodes A and D is sufficient for the broadcast operation to cover all the five nodes.

   However, when the size of the network increases and the network becomes dense, more transmission redundancy will be introduced and these transmissions are likely to cause serious drawbacks (i.e. redundant rebroadcast, contention and collision) which can lead to a total collapse in the operation of the network. These drawbacks are collectively referred to as the broadcast storm problem [5]. The detail of each of the drawbacks now follows:

   • Redundant rebroadcast:

     This phenomenon occurs when a node rebroadcasts packets that neighboring nodes have already received [6]. In Figure-1 When node A broadcast a packet to nodes B, C and D, then node B rebroadcast to A, C and D which is clearly redundant as nodes A, C and D have received a copy of the packet already from As transmission.

   • Channel Contention:

     This occurs [6] when a node broadcasts a packet and if the neighbours of the node receive the broadcast packet and try to retransmit the packet, these transmissions may severely contend the shared physical channel with each other. This will cause delay in the dissemination of data packets.

   • Packet Collision:

   As nodes compete for shared medium, if more than one node attempts to transmit at one time on the channel, collision [6] is more likely to occur.

   Figure-1 Simple ad-hoc network with 5 nodes

3. Routing Protocol

   A routing protocol governs the way of exchanging information in two communication entities; it includes the procedure in establishing a route, decision in forwarding, and action in maintaining the route or recovering from routing failure.

   Ad-hoc routing protocols are classified into two main categories [2] [3]: proactive and reactive. Proactive routing protocols continuously update the routing table, thus generating sustained routing overhead, whereas reactive routing protocols do not periodically update the routing table. Instead, when there is some data to send, they initiate route discovery process through flooding which is their main routing overhead. Reactive routing protocols also suffer from the initial latency incurred in the route discovery process, which potentially makes them unsuitable for safety applications. AODV [7], DSR [8] are the examples of reactive routing protocols whereas OLSR [2] and FSR [2] are the examples of proactive routing protocols.

   3.1 AODV

   AODV [7] is the best-known and most studied VANET routing protocol. It is reactive in nature, requesting and establishing routes only when needed and maintaining only those that remain active. As in VANET, nodes (vehicles) have high mobility and moves with high speed. Proactive based routing is not suitable for it. Proactive based routing protocols may fail in VANET due to consumption of more bandwidth and large table information. AODV is a reactive routing protocol, which operates on hop-by-hop pattern. The Ad-hoc On-Demand Distance Vector (AODV) [3] algorithm enables dynamic, self-starting, multi hop routing between participating mobile nodes wishing to establish and maintain an ad-hoc network. AODV allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain routes to destinations that are not in active communication.

   The AODV routing mchanism consists of two phases; route discovery [7] and route maintenance [7]. AODV uses three types of packets for route discovery process and route maintenance process

   1. Route Request Packets (RREQ)

   2. Route Reply Packets (RREP)

   3. Route Error Packets (RERR)

      Phase I: Route Discovery: When a source node wants to send data to a destination and does not already have

      a valid route to the destination, it initiates a route discovery process in order to locate the destination. A route request (RREQ) packet is broadcast throughout the network via simple flooding and in a managed fashion using expanding ring search. The RREQ packet contains the following main fields: source identifier, source sequence number, broadcast identifier, destination identifier, destination sequence number (created by the destination to be included along with any route information it sends to requesting node), and time-to-live. To prevent excessive transmission of the RREQ packets, the source node optimizes its search by using an expanding ring search. In this search process, increasingly larger neighborhoods are included to find the destination. A time-to-live field (TTL) in the header of the RREQ packet controls the search. The destination sequence number is used by AODV to ensure loop-free routes which also contain most recent route information.

      Each intermediate node that forwards an RREQ packet creates a reverse route back to the source node by appending the next hop information in its routing table. Once the RREQ packet reaches the destination or an intermediate node with a valid route, the destination or intermediate node responds by sending a unicast route reply (RREP) packet to the source node using reverse route. The validity of a route at the intermediate is determined by comparing its sequence number with the destination sequence number. Each node that participates in forwarding the RREP packet back to the source creates a forward route to the destination by appending the next hop information in the routing table. However, nodes along the path from source to destination are not required to have knowledge of which nodes are forming the path.

      Figure-2 depicts an example of route discovery process. It shows how the path is determined from the source node (node 2), to the destination node (node 9). Node 2 propagates a route request packet to its neighbours, nodes 1, 3, and 4. These nodes, in turn, disseminate the route request to their neighbours while collecting route data. The route request, along with the path to the source node, is eventually received by the destination node, node 9. Base on the route data that has been collected during the route discovery process, the destination node is able to send its reply message back along the shortest route, as shown by the RREP route.

      Phase-II Route Maintenance: The second phase of AODV routing mechanism is the route maintenance phase. Route maintenance is the process of responding to changes in topology that happen after a route has

      initially been created. After the route discovery process and as long as a discovered route is used, it has to be maintained. To maintain paths, intermediate nodes along the path continuously monitor the active links and maintain an up-to-date list of their 1-hop neighbours (by means of a periodic exchange of hello packets). The routing table entries include a destination, the next hop toward the destination, and a sequence number. Routes are only updated if the sequence number of the incoming message is larger than the existing number. Routing table also maintain a route expiration time. Each time that route is used to forward data packet, the expiration time is updated to the current time plus ACTIVE_ROUTE_TIMEOUT. After the time expires, the routing table is no longer valid. When a broken link occurs or a node receives a data packet for a destination it has no forwarding route for, it must respond with creation of a Route Error (RERR) message. The RERR message holds a list of all of the unreachable nodes. The source node can either try to find a new route by initiating a new route discovery for the destination if there is no intermediate node with an alternative path to destination, or the intermediate node may try to repair the route locally.

      Figure 2 Route Discovery Process

   4. Density Based rebroadcast

      A brief outline of the AODV-DBR algorithm is presented below and operates as follows. On hearing a broadcast RREQ control packet at node X, the node rebroadcast a packet according to a high probability if the packet is received for the first time, and the number of neighbours of node X is less than average number of neighbours typical of its surrounding environment. Hence, if node X has a low degree (in terms of the number of neighbours), retransmission should be likely. Otherwise, if X has a high degree its rebroadcast

      probability is set low. The AODV-DBR for is presented below:

      Density Based Rebroadcast: AODV-DBR

      On hearing a broadcast RREQ packet at node X Get the number of neighbors Nx at node X

      Get the avg. value

      If packet RREQ received for the first time then

      If (Nx< avg) then

      Node X has a low degree i.e. sparse network: high rebroadcast probability p=p1;

      Else if (Nx=avg) then

      Node X has a medium degree i.e. regular network: medium rebroadcast probability p=p2;

      Else

      Node X has a high degree: i.e. dense network: low rebroadcast probability p=p3;

      End_if End_if

      If (p >= 0.5) then

      Rebroadcast the RREQ packet

      Else

      Drop it

      End_if

   5. Simulation and Result Analysis

      SUMO[9] and MOVE[10] tools are used to create road topology and traffic. SUMO used to generate mobility and MOVE is built upon SUMO platform and provides better GUI support to SUMO. Ns-2[11] is used as the simulation platform. NS-2 is a discrete event simulator, it is designed by researcher at Berkeley University and targeted at networking research, NS-2 provides substantial support for simulation of TCP, routing, and multicast protocols over wired and wireless networks. The simulation scenarios consist of different mobile nodes moving in different network area; each node has 250 meter transmission range and having bandwidth of 2Mbps. Each data point in the simulation results represents an average of 30 randomly generated mobility patterns in order to achieve a 95% confidence interval in the collected statistics. The MAC layer protocol is IEEE 802.11. The nodes move according to the random waypoint model.

      The traditional AODV protocol which use blind flooding during route discovery, has been modified by replaced the blind flooding with new density based broadcast scheme. AODV is already implemented in NS-2 packet level simulator. The aim is to reduce the flooding of RREQ packets during the route discovery

      operation, and as a result reduces the broadcast storm problem. The net effect is that overall network improved by reduced the average end-to-end delay and as well as routing overhead.

      Table 1 Simulation Parameters

      Simulation Parameter	Values
      Protocol	AODV,AODV-DBR
      Simulation time	1000 sec
      Mobility model	Random Way Point
      Type of traffic	TCP
      No. of connection	20,40,60,80
      No. of vehicles	25,50,75,100
      Ns2 version	2.34
      Mac layer protocol	IEEE 802.11
      Packet size	512 bytes
      Hello packet size	64 bytes

      The following performance metrics have been used to evaluate the algorithms:

      The routing overhead: The number of RREQ packets transmitted for the purpose of routing data packets duringthe whole simulation time.

      Table 2 Routing Overhead

      Routing Overhead(No. of Packets)
      No. of Nodes	25	50	75	100
      AODV	2035	7313	12494	23494
      AODV-DBR	2033	7075	10493	20801

      Figure 3 Routing Overhead vs No. of Nodes

      The above graph, Figure-3 shows the performance of the AODV and AODV-DBR in terms of routing overhead versus no. of nodes i.e. network density. The RREQ Packets increased as the number of nodes is increase. From above graph it is very clear that routing overhead generated by AODB-DBR is lower compared by normal AODV. The improved performance of AODV-DBR is due to the significant reduction in the number of redundant RREQ packets.

      The average end-to-end delay: End-to-end delay of data packets includes all possible delays caused by buffering during routing discovery, queuing at the interface queue, retransmission at the MAC layer, propagation, and transfer time.

      Table 3 End-to-end delay

      End to end delay (ms)
      No. of Nodes	25	50	75	100
      AODV	589.144	629.515	650.057	690.775
      AODV- DBR	432.525	618.441	630.346	660.753

      Figure 4 End-to-end delay vs No. of Nodes

      The above graph, Figure-4 shows the performance of the AODV and AODV-DBR in terms of average end-to-end delay versus no. of nodes i.e. network density. When network density increase, the number of duplicated RREQ packets which generated by nodes is also increased, and this is increased the number of dropped packets. As a result, packets experience high latencies in the interface queues. From the above graph it is very clear that end-to-end delay generated by AODV-DBR is lower compared by simple AODV.

      Throughput: The ratio of the total amount of data that reaches a receiver from a sender to the time it takes for the receiver to get the last packet is referred to as throughput. It is expressed in bits per second or packets per second. Factors that affect throughput include frequent topology changes, unreliable communication, limited bandwidth and limited energy. A high throughput network is desirable.

      Table 4 Throughput

      Throughput(Data packets/sec)
      No. of Nodes	25	50	75	100
      AODV	504.61	490.4	484.65	443.06
      AODV-DBR	517.16	493.1	488.15	455.67

      Figure 5 Throughput vs No. of Nodes

      The above graph, Figure 5 shows the performance of the AODV and AODV-DBR in terms of throughput versus no. of nodes. In a network where excessive redundant retransmissions of control packets (e.g. RREQ packets) are predominant, channel contention and packet collisions increase thereby lowering the bandwidth available for data transmission. Therefore, if we control the redundant retransmissions of RREQ packets in network, the degradation of the throughput can be reduced. As shown in above graph, AODV- DBR outperformance well compared to AODV. The improved performance of AODV-DBR is due to the significant reduction in the number of retransmissions of RREQ packets.

   6. Conclusion and Future work

Broadcasting of messages in VANETs can result in increased channel contention and packet collisions due to simultaneous message transmissions, and due to which throughput and efficiency of network is decrease. The proposed Density Based Rebroadcast- DBR approach considers the message rebroadcast process by selecting a limited number of vehicles, acting as forwarders so there is less contention of messages in network due which less probability of collision of messages in network. In Density Based Rebroadcast approach there are less redundant messages in network. Thus with the help of Density Based Rebroadcast scheme broadcast storm problem can be reduced.

By performing simulation for 25, 50, 75, 100 nodes and analyzing that, routing overhead generated by AODB-DBR is lower compared by normal AODV due to reduction in the number of redundant RREQ packets. Average end-to-end delay generated by AODV-DBR is lower compared by normal AODV due to less contention in network. Throughput generated by AODV-DBR is higher compared by normal AODV due to the significant reduction in the number of retransmissions of RREQ packets. AODV-DBR increases efficiency of whole network because lower routing overhead, end-to-end delay and better throughput compared to simple AODV.

This paper has presented an extensive performance analysis of Density Based Rebroadcast algorithms for pure broadcast and application scenarios (e.g. route discovery) based on the reactive AODV routing protocols. It would interesting to investigate the impact of these broadcasting algorithms when used as a route discovery mechanism in other reactive routing protocols, such as DSR.

References

1. J. Jakubiak and Y. Koucheryavy, State of the art and research challenges for VANETs, Consumer Communications and Networking Conference, 2008. CCNC 2008, pp. 912-916, Jan. 2008.

2. Lee, K. C., Lee, U., & Gerla, M., Survey of Routing Protocols in Vehicular Ad-Hoc Networks, Advances in Vehicular Ad-Hoc Networks: Developments and Challenge, Watfa, pp.149-170, 2010.

3. Fan Li and Yu Wang, Routing in Vehicular Ad Hoc Networks: A Survey, IEEE Vehicular Technology Magazine, vol. 10, no. 3, pp. 12-22, JUNE 2007.

4. Ozan Tonguz, Nawaporn Wisitpongphan, FanBai, Priyantha Mudalige, and Varsha Sadekar Broadcasting in VANET, IEEE INFOCOM 2008,

5. Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. Wireless Networks, vol. no.8: pp.153- 167, Feb.2002.

6. N. Wisitpongphan, O.K. Tonguz, J.S. Parikh, P. Mudalige, F. Bai, and V. Sadekar. Broadcast storm mitigation techniques in vehicular ad hoc networks, Wireless Communications, IEEE, vol. 14, no. 6, pp. 84-94, December 2007.

7. C. Perkins, E. Belding-Royer, and S. Das, "Ad-hoc On-Demand Distance Vector (AODV) Routing" IETF Mobile Ad-Hoc Networking Working Group INTERNET DRAFT, RFC 3561, July-2003. http://www.ietf.org/rfc/rfc3561.txt

8. D. Johnson, Y. Hu, and D. Maltz, "The Dynamic Source Routing Protocol (DSR) for Mobile Ad-Hoc Networks," IETF Mobile Ad Hoc Networking Working Group INTERNET DRAFT. http://www.ietf.org/rfc/rfc4728.txt

9. D. Krajzewicz and C. Rossel. Simulation of Urban MObility (SUMO). German Aerospace Centre, 2007. http://sumo.sourceforge.net/index.html.

10. MOVE (MObility model generator for VEhicular networks): Rapid Generation of Realistic Simulation for VANET-2007. http://lens1.csie.ncku.edu.tw/MOVE/index.htm.