Options
EASBVN: efficient approximation scheme for broadcasting in vehicular networks
ISSN
10220038
Date Issued
2021-01-01
Author(s)
Das, Debasis
Misra, Rajiv
DOI
10.1007/s11276-020-02455-4
Abstract
Vehicular ad-hoc networks (VANETs) suffer from dis-connectivity due to very high mobility, node sparseness, and lossy link. Thus, the broadcasting algorithms in the vehicular multi-hop scenario have to operate in all extreme scenarios as dense, sparse, and disconnected topologies that are changeable dynamically due to different traffic conditions. The store-and-carry-forward scheme for disconnected topologies with dynamic nodes can be model as a Steiner-tree problem due to link weight change dynamically. The Steiner tree has to be recomputed to obtain the new Steiner tree, making it more difficult for broadcasting algorithms in VANETs. We show that broadcasting in VANETs (i.e., given graph G(V1, E1) with the terminal set, T1⊆ V1), modeled as to find as many (maximum) disjoint Steiner trees as possible that are disjoint on the non-terminal nodes and the edges are APX-hard even for small T1. If all the nodes in G are terminal nodes, i.e., T1= V1, the trouble is finding a maximum cardinality set of edge-disjoint spanning trees and encountering a considerable lot of edge-disjoint spanning tree. We then propose an O(log n) -Approximation Algorithm for Broadcasting in VANETs via bipartite graph (G= ((T1, V1/ T1) , E1)) and using projection. We compared the performance of the proposed scheme (i.e., EASBVN) with existing state-of-the-scheme and found it to be better than the state-of-the-art schemes (i.e., DV-CAST, UVCAST, DPPEMB, MoZo, and MobiVNDN) in terms of end-to-end delay and re-healing time.