Header menu link for other important links
EASBVN: efficient approximation scheme for broadcasting in vehicular networks
, R. Misra
Published in Springer
Volume: 27
Issue: 1
Pages: 339 - 349
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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
About the journal
JournalData powered by TypesetWireless Networks
PublisherData powered by TypesetSpringer
Open AccessNo