Information Table based Decision Approach for Broadcast Storm Suppression in Vehicular Ad-Hoc Networks

Information Table based Decision Approach for Broadcast Storm Suppression in Vehicular Ad-Hoc Networks

Aditya Om, Rajat Chandrashekhar Shinde, Sejal Agrawal, Dr. A.S. Raghuvanshi

Department of Electronics & Telecommunication, National Institute of Technology Raipur,

Raipur, India,

Abstract Various multi-hop applications in MANETs in general and VANETS in particular, use broadcasting as a method for propagating useful traffic information, paging a particular host, route discovery etc. to neighboring nodes located within a logical and geographical boundary. However broadcasting via the conventional mechanism leads to high level of network contention, and flooding at Data Link Layer which causes dropping of packets and loss of information. In VANETs the network topology is dynamically changing and self arranging and a minor loss of packet or end to end delay may propagate in time and evolve in a chaotic scenario in real time use case. In this paper we have presented a novel routing algorithm MARS. MARS is based on i-table approach analogous to IP-Table model as decision control mechanism in deciding the next hop node for packet forwarding. It mitigates BSP, specifically in VANET applications and scenario as we have considered the properties of VANET in our use case. A comparison of results with existing routing protocols viz. AODV and EIGRP for the defined performance metrics against that obtained with MARS in EXata Simulation environment has been shown.

Index TermsWSN, Routing, MANET, VANET, BSP Broadcast Storm Problem.

1. INTRODUCTION

   Vehicular ad hoc networks (VANETs) and mobile ad hoc networks (MANETs) differ in many ways. First, VANETs consist of high mobility nodes moving in opposite or same directions. Vehicles moving along different but nearby roads may or may not be able to communicate with one another due to small interaction time and obstacles. Second, the network shape description can be a more or less uniform one dimensional or strip in a non-chaotic scenario. Lastly, almost all applications for VANETs rely heavily on broadcast transmission for dissemination of traffic related information to all reachable nodes within a certain geographical area rather than a search request for route to an intended node.

   Due to factors such as radio power limitation and channel utilization a mobile node may not be able to communicate directly with other nodes in a single-hop method. Particularly in this scenario, a multi-hop transmission occurs, where the packets transmitted by the source node are relayed by several intermediate hosts until the destination host is reached.

   In this paper, we try to identify and propose a solution to the problem of sending messages in a broadcast in a VANET. Broadcasting, a common process in many applications, e.g.,

   Networking and distributed computing problems, is also widely used to resolve graph problems. In a VANET in particular, due to host-node mobility, broadcastings are expected to be performed more rapidly for e.g., paging a particular host, sending hello-packets, and for network discovery to a host-node. Broadcasting may also be used in LAN emulation [2] or serve as a method to provide multicast services in networks with rapid changing topologies, such as in case of VANETs.

   Assumptions for the paper are that mobile nodes in the VANET share a single common channel with CSMA, but no collision detection capability. Synchronization in such a highly mobile network is difficult, and a general network topology information is not available to facilitate the broadcast scheduling. So the only solution is broadcasting by flooding. However, it is observed that redundancy, contention, and collision could exist if flooding is done conventionally. Firstly, because the radio transmission is omnidirectional and a physical node position may be covered by the transmission range of neighboring nodes, similar repetitive rebroadcasts would be considered to be redundant. Second, heavy contention would exist because rebroadcasting nodes are close to each other. Thirdly, collisions are very likely to occur because RTS/CTS dialogue is not applicable and timing of rebroadcasts is highly correlated.

   All the above problems collectively have been considered as BSP. Various mitigation techniques have been introduced before [3] for BSP in reference to MANETS. These methods generally involve reduction of possibility of redundant rebroadcasts by nodes in logical neighborhood and differentiating the rate at which selective rebroadcasting is done at each node. This gives arise to several schemes known as counter based, cluster based, distance based, probability based and location based schemes. In our study we have considered EIGRP and AODVs distance based routing algorithms as our basis for comparison with MARSs algorithm for performance metrics defined in the scenario created in EXata simulation environment.

   Our goal is to show that i-table based approach suggested as in MARS algorithm for packet forwarding in a non-chaotic, steady state VANET scenario such as in Highway, yields better results such as low packet loss, better throughput and optimum end to end delay.

   The rest of the paper is organized as follows In Section II, we provide the necessary research work related to the impact of the broadcast storm problem in VANETs. In Section III, we define the problem and assumptions. In Section IV we propose our routing algorithm- MARS and analyze it in brief. Finally, the performance of the three broadcast techniques is presented, along with the main findings and conclusions drawn from comparison.

2. LITERATURE REVIEW

   These were different categories of schemes, that were reviewed in order to understand the existing approaches by different authors:

   • A probabilistic scheme limits the number of rebroadcasts. When a node receives a broadcast for the first time the message is rebroadcasted with a certain probability P, otherwise, the node discards the packet. Moreover, when P = 1, this scheme tends to the flooding condition [1, 2]. This scheme adopts different methods such as p-persistence, Slotted l-persistence and weighted p-persistence [5]

   • In a Counter-based scheme, a counter is used to track the number of times a message is being heard before a node has a chance to rebroadcast the message. In this scheme, Tseng et al [1] showed that when k is greater than or equal to 4 (k is number of times the message is heard after being rebroadcasted by other nodes) the additional coverage of a rebroadcast decreases rapidly. This scheme basically prohibits the rebroadcast when c C, where c is the number of times a broadcast has been heard and C the counter threshold [1, 3, 4]. The algorithm for counter based scheme is as follows :

     procedure cbscheme(msg)

     if (tcount(msg) == 1) then procedure cbscheme(msg)

     if (tcount(msg) == 1) then

     wait for a random number (0 ~31) of slots send msg

     else

     suspend waiting

     if tcount(msg) < C

     then resume waiting

     else

     cancel waiting inhibit msg

     rebroadcasting

     endif

     endif

     • In Location-based scheme the coverage area is calculated with precision. A GPS device is used to locate the broadcasting nodes. If the additional coverage of a message is greater than a threshold the message is rebroadcasted .One possible solutions to calculate the additional coverage area is based on geometrical modeling using convex polygons[1] .

       Fig. A- Method of convex polygons to determine whether to rebroadcast or not:

       1. X is inside the triangle formed by three sender odes (A, B &C)

       2. X is outside of the polygon.

       3. Analysis of maximum loss of additional coverage

   • In cluster based scheme network is partitioned into clusters. A host with a local minimal ID is self- elected as a cluster head and all neighboring hosts of a head are members of the cluster recognized by the ID of the head. A gateway member is also present within the cluster that can communicate with the head of other clusters and propagates the broadcast message through the head to its corresponding hosts [1, 4].

   • The distance-based scheme rebroadcasts a message depending on the distance between the sender and receiver. A parameter Dmin is used to record the distance between the sender and receiver of the broadcast. If Dmin< Dth ( Dth is the threshold value) , then the broadcast is prohibited from being forwarded[1,4]. EIGRP and AODV protocols against which comparison has been done in our paper, involve distance based routing algorithm for packet forwarding. The algorithm for distance based scheme is as follows :

     procedure dbscheme(msg)

     if (tcount(msg) == 1) then

     dmin = ds

     if (dmin >= Dth) then

     wait for a random number (0 ~31) of slots send msg

     else

     inhibit msg rebroadcasting

     endif else

     if waiting to send then suspend waiting if(dmin>ds) then dmin=ds

     endif

     if(dmin < Dth ) then

     cancel waiting

     inhibit msg rebroadcasting

     else

     endif endif

     resume waiting endif

     IV. PROPOSED SOLUTION

     1. To determine the density of traffic so as to determine the running average of nodes

        >> begin

        where ds is the distance from the sending node.

3. PROBLEM FORMULATION AND ASSUMPTIONS

   Although most MANET research typically assume a two- dimensional network with random topology [5], we gather that a one-dimensional line network can best fulfill the topology of a vehicle-based ad-hoc network on a highway or on a city area where nodes have more probability to be on a well-defined path.

   Therefore, we consider a one-dimensional line or single-lane network with regular traffic. A 1500x 6000 m2 area is created for observation in architect tool of Exata cyber 2.0 , where a regular traffic of vehicles is assumed. Six vehicles are scrutinised for their packet transmission and receptance, each being connected to a single cloud network. They have been divided into two groups namely –

   • Group 1 consisting of vehicles with Node Id 4,5 &

     6.

   • Group 2 consisting of vehicles with Node Id 1,2 &

   3.

   Fig. B- Implementation Scenario in EXata Cyber

   Each group is assigned a particular minimum and maximum speed, along with the random waypoint motion within the

   >> at each node (Ni) initialize state (Si) = 0 (i= 1,2,3., k : k is the no. of nodes)

   >> initialize avg1=0;

   >>initialize avg2 =0;

   # here state refers to the value of fields in i-table maintained at each node.

   >>On hearing RREQ packet at node (Ni);

   #on the basis of preliminary scan and Hello packet exchange

   >> Get the Number of neighbors Nx ;

   >> Scan i-table and update Si ;

   >> Obtain Dev_id and update the i-table at Ni ;

   >> compute running average avg1 of Vx ;

   >> compute running average avg2 of Nx ;

   1. Decision criteria for packet forwarding or dropping

      >> If packet RREQ received for the first time then If (Vx < avg1 AND Nx<avg2)

      Node Ni has a sparse traffic, rebroadcast RREQ packet;

      Else if (Vx > avg1 AND Nx > avg2 ) Node Ni has dense traffic,

      Switch header condition

      Compare Si and RREQ ID header; Case 1 : Si & RREQ(j) header same ;

      Drop RREQ packet;

      Case 2 : Si & RREQ(j) header not same ; Update S at N ;

      group. The movement is constrainted with respect to area, as i i

      both the groups have been specified to imitate a non-chaotic scenario on a highway wherein the variance of individual nodes speed is approximately zero to the average speed of group.The aim of transferring packets from Node Id 1 to the Node Id 4, the constant bit rate ( CBR ) is set between the two. Packets are constantly sent by 1 and the number of

      End End

      Update RREQ(i, j); Rebroadcast RREQ Header ;

      packets received by 4 is monitored.

      The entire simulation is done for different simulation time ( i.e. 10 seconds, 20 seconds & 30 seconds ) for applying different routing protocols i.e. AODV, EIGRP and MARS.The different parameters – throughput, total bytes sent, no. of hop counts, no. of packets dropped were monitored using analyzer tool of EXata cyber 2.0 simulator.

      Else Drop RREQ(i, j) packet; End

   2. Implementation of i-tables

      General packet structure:

      sk	Pointer to source socket
      timestamp	Time of arrival
      dev_id	Rx/Tx device pointer
      h	transport layer header pointer
      nh	network layer header pointer
      mac	link layer header pointer
      dst	Pointer to dst_entry
      cb	TCP packet control Info.
      data	data length
      csum	checksum
      protocol	Packet network protocol
      truesize	Buffer size
      head	Pointer to buffer head
      data	Pointer to head of data
      tail	Pointer to tail
      end	Pointer to end
      destruct	Pointer to destruct function

      The Packet structure is defined for each packet that is exchanged between the nodes before data transmission occurs. Upon route discovery the datagram packet is transmitted and the session layer management function ensures due closing of port and making the channel available and also updating the i-table corresponding to each node.

      General structure of an i-table:

      In the scenario proposed, in the immediate local neighborhood, the aim is to update the i-table configured at each node with minimum channel contention and minimum repetition of re-broadcast of redundant information (i.e. Broadcast storm problem). In the i-table approach, consider a node beaming hello packets to the nearest node(s), the following information is exchanged dev_id (i), local speed (j) etc. The aim of the configured scenario is to avoid accident and identify that node in local neighborhood whose speed variance is large in comparison with avg. group velocity and notify the target node at the logical boundary or remote w.r.t. group in advance of probable node clustering i.e. traffic jam .

      Network (IP) layer implementation: The IP layer handles routing between devices/ nodes. At the network layer similar to general TCP/IP protocol stack, three data structures are maintained.

      1.) NIB : Next Information Base 2.) Routing cache &

      3.) I-Table

      The functions of each of these data structures are as follows:

      1. NIB: at each device level, this data structure keeps a record of all possible routes available until this node level of the tree. The NIB is the basic routing reference for nodes covered until now. The NIB has 52 sections. First 48 for 48 bit MAC address and remaining 4 for node count.

      2. Routing cache is a data structure implemented via directed acyclic graph and functions by reorganizing an LC trie, thus reducing depth by packing together tries. It has the following fields defined: neighbor interface ID on the basis of exchnged hello packets, and IP.

      3. I-Table performs routing on the basis of selection drop- forward methodology. At each node level, the I-table maintains the following data in a tabular entry implemented using hash tables and LC Trie. The LC Trie stores only the initial nodeID corresponding to each node, speed value. In a real use case several other values may be considered for forwarding direction decision.

   Node_id	MAC	i-value1(i)	i-value2(j)
   Id1	Mac1	Val_i1	Val_j1
   Id2	Mac 2	Val_i2	Val_j2
   .	.	.	.

   So, when a packet is received by a node, each node checks with its configured i-table update and resets the matching bits of the datagram field to zero. Thus, a reconstructed smaller packet is forwarded to a node with different i-table value.

   The routing and branching of the route discovery may be described via a simple LC Trie method of dynamic updating process, inserting and removing string values stored in a each trie . Here each trie corresponds to storage of data packets.

   node = T[0]; pos = node.skip;

   branch = node.branch; adr = node.adr;

   while (branch != 0) {

   node = T[adr + EXTRACT(pos, branch, s)]; pos = pos + branch + node.skip;

   branch = node.branch; adr = node.adr;

   }

   return adr;

   Note on trie: The trie is a general-purpose data structure which stores strings. A leaf in a tree structure represents a string, and the value of the string corresponds to the path from the root of the tree to the leaf. The binary strings in the routing table correspond to the trie in Figure A.

   1. RESULTS AND DISCUSSION

      After each simulation, EXata generates a statistics file containing information for analyzing the behavior of protocols, network performance, etc. whose naming depends on the scenario defined by the user. This needs to be specified in advance. The statistics file is a text file. It is viewed graphically using EXata Analyzer. Normally, the simulation runs for the configured simulation time. The statistics file is generated in each case. The first two lines of the statistics file indicate the configured simulation time and the simulation time when the simulation actually ended. The values in the statistics file in .txt format is exported to .xls format.

      Using the method defined above, we obtained and defined the following performance metrics Throughput, No. of Packets dropped and End to End delay. These performance metrics were obtained for AODV, EIGRP and MARS routing protocol and the following results were obtained. In the section that follows, an explicit discussion is attempted.

      1. THROUGHPUT

         Throughput Results for AODV, EIGRP and MARS –

         AODV
         S No.	% throughput (10 s)	No. of % bytes throughput sent ( 20 s )		No. of % bytes throughput sent ( 30 s)		No. of bytes sent
         1	40.96	4608	45.51	5120	48.56	6540
         2	40.55	4800	46.2	5200	45.62	6345
         3	41.02	4284	47.45	4820	50.14	6794
         4	39.52	4550	49.89	5475	47.57	6400
         5	41.5	4672	45.84	5312	46.5	6770
         6	40.96	4300	47.89	5684	48.1	6940
         7	40.29	4460	45.33	5050	44.78	6278
         8	41.49	4240	41.9	4956	46.51	6741
         9	39.95	4350	42.8	4754	45.48	6345
         10	40.08	4190	43.66	5069	46.14	6287
         Average values	40.632	45.647		46.94

         Table (a)

         EIGRP
         S. No.	% Throughput ( 10 s)	No. % of bytes Throughput sent (20 s) (10 s)		No. of bytes sent (20 s)	% Throughput (30 s)	No. of bytes sent (30 s)
         1	35.46	3989	38.45	4325	40.89	5520
         2	36.15	4066	34.89	3925	38.47	5793
         3	34.47	3877	36.48	4104	40.14	5418
         4	33.86	3809	35.72	4018	40.45	5460
         5	34.4	3870	39.68	4465	43.57	5881
         6	35.29	3974	41.67	4687	42.96	5799
         7	32.84	3694	40.78	4587	43.79	5911
         8	34.5	3881	39.75	4471	44.48	6007
         9	36.58	4115	42.19	4746	45.72	6172
         10	35.14	3953	42.00	4725	44.47	6001
         Average value	34.869	39.161			42.494

         Table (b)

         MARS
         S. No.	% Throughput ( 10 s)	No. of % bytes Throughput sent ( 20 s) (10 s)		No. of % bytes Throughput sent (30 s) (20 s)		No. of bytes sent (30 s)
         1	38.58	4340	39.47	4441	44.14	5958
         2	40.62	4569	37.64	4234	43.78	5910
         3	37.15	4178	40.82	4592	46.64	6296
         4	36.45	4100	43.48	4891	42.93	5796
         5	34.6	3892	42.36	4765	45.19	6100
         6	38.47	4327	44.79	5038	47.63	6430
         7	35.15	3954	43	4837	46.28	6247
         8	37.94	4268	45.69	5140	43.54	5877
         9	34.66	3899	41.24	4639	47.42	6410
         10	38.45	4325	40.15	4516	48.92	6604
         Average Value	37.207	41.864		45.647

         Table (c)

         Fig. C- Comparison of AODV, EIGRP and MARS.

      2. END-TO-END DELAY (EED)

         This metric is used to measure average transmission time of packets from a node to the node at which rebroadcasting is terminated because all nodes in a logical neighborhood have their i-table updated.

         The values of end-to-end delay were obtained from the .stat file for each simulation run of the scenario. The results are plotted as below for various run time.

         Fig. D- EED comparison plot on scenario for AODV, EIGRP and MARS

      3. AVERAGE NUMBER OF PACKETS DROPPED

         This metric refers to average number of packets dropped/ lost during the process of i-table update and forward cycle until no further broadcast condition during each simulation in case of MARS. In case of EIGRP and AODV this refers to average number of packets dropped. The metric data was obtained from .stat file of EXata analyzer for every simulation.

         Fig. E- No. of packets dropped (out of 100 packets)

         This metric indicates the importance of MARS w.r.t. established AODV, EIGRP and as can be seen its efficiency is comparable to AODV and better than EIGRP.

      4. CONCLUSION

      In this paper, we have showed how to effectively mitigate Broadcast Storm Problem using the i-table approach. The proposed algorithms performance was evaluated in the Exata Cyber versus distance based broadcast algorithms as implicated in industry standard protocols EIGRP and AODV. Proposed algorithm uses i-table based selective packet forwarding criteria instead of blind broadcasting or distance based decision criteria and thus yields lesser contention, packet redundancy and end-to-end delay performance metric values.

   2. REFERENCES

1. DYMO as routing protocol for IEEE-802.15.4 enabled Wireless Sensor Networks – By Dr. Ajay Singh Raghuvanshi and Dr. Sudarshan Tiwari.

2. Mitigating Broadcast Storm Problems in Vanets- Khaleel Ur Rahman Khan and Mohd Umar Farooq-DOI 10.5013/IJSSST.a.15.05.04

3. Broadcast Storm Mitigation techniques in vehicular Ad-Hoc Networks- N. Wisitpongphan and O. K. Tonguz, J.S. Parikh , P. Mudalige, F. Bai and V. Sadekar IEEE Wireless Communications, December 2007.

4. The Broadcast Storm Problem in a Mobile Ad Hoc Network- Sze- Yao Ni, Yu-Chee Tseng, Yuh- Shyan Chen, and Jang-Ping Sheu- Wireless Networks 8, 153-167, 2002.

5. A Technique to Mitigate the Broadcast Storm Problem in VANETs : Manoel Rui P. Paula, Daniel Sucupira Lima, Filipe Maciel Roberto, Andre Ribeiro Cardoso, Joaquim Celestino Jr.

6. An Efficient Counter-Based Broadcast Scheme for Mobile Ad Hoc Networks : Aminu Mohammed, Mohamed Ould-Khaoua, and Lewis Mackenzie

7. Simulation and Performance Analysis of Routing Protocols in Wireless Sensor Network using QualNet By Anjali Goyal , Dharmendra Kumar Jhariya , Sandeep Vijay.

8. New Adaptive Counter Based Broadcast Using Neighborhood Information in MANETS- A. Al-Dubai, M. Bani Yassein, M. Ould Khaoua, Omar M. Al-Jarrah-2009 ieee.

9. An Effective Way of Broadcasting Alert Messages in Vehicular Ad hoc Network- Mohd Umar Farooq ,Junaid Ahmed Shadab, Khaleel Ur Rahman Khan-Proceedings of the International Conference on Communication and Computational Intelligence 2010 ,Kongu Engineering College, Perundurai, Erode, T.N.,India.27 29 December,2010.pp.132-137

10. Inspired Counter Based Broadcasting for Dynamic Source Routing in Mobile Networks- Muneer Bani Yassein ,Ahmed Y. Al-Dubai-2015 IEEE International Conference on Computer and Information Technology; Ubiquitous Computing and Communications;Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing.

11. ProbT: A Temporal Probabilistic Protocol to Mitigate the Broadcast Storm Problem in VANETs- Daniel Sucupira Lima, Manoel Rui P. Paula, Filipe Maciel Roberto,Andr´ e Ribeiro Cardoso and Joaquim Celestino J´unior- ieee 2015

12. Intelligent Broadcast in Wireless Ad Hoc Networks Using Live Packet Information- Chun-Hsin Wu and Chi a-Wei Li- ieee 2013.

13. EXata 5.2 Users Guide- By Scalable Technologies Networks.

14. http://www.drdobbs.com/cpp/fast-ip-routing-with-lc-tries/184410638