Plummeting Broadcast Storm Problem in Highways by Clustering Vehicles Using Dominating Set and Set Cover
Open Access
Abstract
“Vehicular Ad-hoc Networks” (VANETs): As an active research area in the field of wireless sensor networks, they ensure road safety by exchanging alert messages about unexpected events in a decentralized manner. One of the significant challenges in the design of an efficient dissemination protocol for VANETs is the broadcast storm problem, owing to the large number of rebroadcasts. A generic solution to prevent the broadcast storm problem is to cluster the vehicles based on topology, density, distance, speed, or location in such a manner that only a fewer number of vehicles will rebroadcast the alert message to the next group. However, the selection of cluster heads and gateways of the clusters are the key factors that need to be optimized in order to limit the number of rebroadcasts. Hence, to address the aforementioned issues, this paper presents a novel distributed algorithm CDS_SC: Connected Dominating Set and Set Cover for cluster formation that employs a dominating set to choose cluster heads and set covering to select cluster gateways. The CDS_SC is unique among state-of-the-art algorithms, as it relies on local neighborhood information and constructs clusters incrementally. Hence, the proposed method can be implemented in a distributed manner as an event-triggered protocol. Also, the stability of cluster formation is increased along with a reduction in rebroadcasting by allowing a cluster head to be passive when all its cluster members can receive the message from the gateway vehicles. The simulation was carried out in dense, average, and sparse traffic scenarios by varying the number of vehicles injected per second per lane. Besides, the speed of each individual vehicle in each scenario was varied to test the degree of cohesion between vehicles with different speeds. The simulation results confirmed that the proposed algorithm achieved 99% to 100% reachability of alert messages with only 6% to 10% of rebroadcasting vehicles in average and dense traffic scenarios.Keywords
This publication has 27 references indexed in Scilit:
- Traffic density estimation in vehicular ad hoc networks: A reviewAd Hoc Networks, 2015
- Clustering in vehicular ad hoc networks: Taxonomy, challenges and solutionsVehicular Communications, 2014
- Non-GPS Data Dissemination for VANETInternational Journal of Distributed Sensor Networks, 2014
- Position-based routing in vehicular networks: A surveyJournal of Network and Computer Applications, 2013
- An Optimal ODAM-Based Broadcast Algorithm for Vehicular Ad-Hoc NetworksKSII Transactions on Internet and Information Systems, 2012
- Information dissemination in VANETs based upon a tree topologyAd Hoc Networks, 2011
- Analysis and simulation of a message dissemination algorithm for VANETInternational Journal of Communication Systems, 2011
- Adaptive clustering for mobile wireless networksIEEE Journal on Selected Areas in Communications, 1997
- A cluster-based approach for routing in dynamic networksACM SIGCOMM Computer Communication Review, 1997
- Unit Disk Graphs1991