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.
International Journal of Communication Networks and Distributed Systems, 2018 Vol.20 No.1, pp.16 - 35
Available online: 10 Nov 2017 *Full-text access for editors Access for subscribers Free access Comment on this article