EASBVN: efficient approximation scheme for broadcasting in vehicular networks
- PDF / 1,699,554 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 3 Downloads / 213 Views
(0123456789().,-volV)(0123456789(). ,- volV)
EASBVN: efficient approximation scheme for broadcasting in vehicular networks Debasis Das1
•
Rajiv Misra2
Ó Springer Science+Business Media, LLC, part of Springer Nature 2020
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 storeand-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. Keywords Vehicular ad-hoc networks (VANETs) Broadcasting algorithms Steiner-tree problem (STP)
1 Introduction The rapid growth in the transportation system increases eminence traffic on the streets. Consequently, plenty of road accidents and traffic congestion have been noticed in recent times. A report by the world health organization (WHO) affirms that road traffic accidents touched 1.35 million deaths per year. Thus, the vehicular ad hoc networks (VANETs) [1] aims to enhance road safety, information dissemination, and traffic management applications & Debasis Das [email protected] Rajiv Misra [email protected] 1
Department of Computer Science and Engineering, Indian Institute of Technology (IIT) Jodhpur, Jodhpur, Rajasthan, India
2
Department of Computer Science and Engineering, Indian Institute of Technology (IIT) Patna, Patna, Bihar, India
[2, 3]. Through VANETs, we can provide Vehicle to Vehicle (V2V) communication [4], which can avoid a crash and hazardous condition by warning messages and propagating alert messages to another vehicle in the network using broadcasting [5]. There had been many traditional mobile ad-hoc routing protocols [6–8], which may be considered to be used in VANETs. A routing process in VANETs is liable for identifying and maintaining the routes between
Data Loading...
