Title: IntersectionCast: approximation algorithm for multi-directional broadcast storm in VANETs

Authors: Debasis Das; Rajiv Misra

Addresses: Department of Computer Science and Information Systems, Birla Institute of Technology and Science (BITS) Pilani, K.K. Birla Goa Campus, NH 17B, Bypass Road, Zuarinagar, Sancoale, Goa-403726, India ' Department of Computer Science and Engineering, Indian Institute of Technology Patna, Bihta, Patna, Bihar-801103, India

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.

Keywords: multi-directional broadcast; MDB; broadcast storm; vehicular ad-hoc networks; VANETs; road intersection; NP completeness; approximation algorithm.

DOI: 10.1504/IJCNDS.2018.088499

International Journal of Communication Networks and Distributed Systems, 2018 Vol.20 No.1, pp.16 - 35

Accepted: 12 Nov 2016
Published online: 11 Dec 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article