IntersectionCast: approximation algorithm for multi-directional broadcast storm in VANETs. (2018)

• Record Type: Journal Article
• Authors: Das, Debasis; Misra, Rajiv
• Is Part Of: International journal of communication networks and distributed systems. Volume 20:Number 1(2018)
• Page Start: 16
• Page End: 35
• Publication Date: 2018
• Subjects: multi-directional broadcast -- MDB -- broadcast storm -- vehicular ad-hoc networks -- VANETs -- road intersection -- NP completeness -- approximation algorithm; Computer networks -- Periodicals; Telecommunication systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-3916

Abstract

We formulate a multi-directional broadcast (MDB) storm problem arising in dense vehicular ad-hoc networks (VANETs) when the multiple nodes (moving in multiple directions) forward broadcast packets meet at the road intersections, resulting in severe packet collisions inducing delays at medium access control. In this work, we have proposed a mechanism for partitioning the graph of vehicles in an intersection into multiple bipartite directional sub-graphs, such that each sub-graph aggregates messages using short range communication and make one long range communication of aggregated message. The k balanced graph partitioning problem contains partitions of size ≤ | V |/ k nodes. For a graph G = ( V, E ), a partitioning P, is ( k, 1 + ε) balanced if V is partitioned into k disjoint subsets each containing at most (1 + ε) n / k vertices. Our proposed approximation algorithm for intersection-cast problem uses a balanced partition with Θ (log^2 n ) approximation for balance constant, v > 1. We have given simulation results for the performance analysis of our intersection-cast protocol compared to the existing competitive schemes and found improvement in terms of broadcast success rate, reachability and message overhead in the networks.